Remove a extra calls to classInitDependencies

5 files changed, 54 insertions, 61 deletions

diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java
index 46a726b3..d95f55f2 100644
--- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java
+++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java
@@ -28,6 +28,7 @@ public class ClassInitDependencies {
     private final int[] _pres;
     private final int[] _lows;
     private final int[] _stk ;
+    private final int[] _spos; // Stack position; FIDX -> stack slot + 1, or 0 when absent.
     private int _sp;
     private int _pre;
 
@@ -39,6 +40,7 @@ public class ClassInitDependencies {
         _pres = new int[code._linker._len];
         _lows = new int[code._linker._len];
         _stk  = new int[code._linker._len];
+        _spos = new int[code._linker._len];
 
         //
         BitSet visit = code.visit();                   // Visit set per-fcn
@@ -136,7 +138,8 @@ public class ClassInitDependencies {
     // Return an error string, or null if no cycle contains multiple clinits.
     public String check() {
         Arrays.fill(_pres,0);
-        _sp = 0;
+        // A prior check may have stopped with a cycle still on the stack.
+        while( _sp>0 ) _spos[_stk[--_sp]] = 0;
         _pre = 1;
 
         int idx = -1;
@@ -149,9 +152,9 @@ public class ClassInitDependencies {
 
     // A condition-producing helper outside the SCC can eliminate a cycle.
     // Before reporting one, restore the full-IR precision of the original check.
+    // Called only after check() has found a cycle.
     Ary<CompUnit> cycleImports() {
         Ary<CompUnit> units = new Ary<>(CompUnit.class);
-        if( check()==null ) return units;
         for( FunNode fun : _code._linker )
             if( fun!=null && fun.summary()!=null && units.find(fun._compunit)==-1 ) units.add(fun._compunit);
         return units;
@@ -205,6 +208,7 @@ public class ClassInitDependencies {
     int scc( int fidx ) {
         // Assign pre-order number
         _lows[fidx] = _pres[fidx] = _pre++;
+        _spos[fidx] = _sp+1;
         _stk[_sp++] = fidx;
         // walk outbound edges
         if( _edgess[fidx]!=null ) {
@@ -214,28 +218,22 @@ public class ClassInitDependencies {
                     int idx = scc(edge);
                     if( idx != -1 ) return idx; // Found a cycle
                     _lows[fidx] = Math.min(_lows[fidx],_lows[edge]);
-                } else if( _edgess[edge]!=null && onStk(edge) ) {
+                } else if( _edgess[edge]!=null && _spos[edge]!=0 ) {
                     _lows[fidx] = Math.min(_lows[fidx],_pres[edge]);
                 }
             }
         }
         // Found a cycle
         if( _lows[fidx] == _pres[fidx] ) {
-            int idx = find(fidx);
+            int idx = _spos[fidx]-1;
             if( hasClzCycle(idx) )
                 return idx;     // Found a class cycle
-            // Pop stack, including fidx
-            _sp = idx;
+            // Pop stack, including fidx, should be a really short loop
+            while( _sp>idx ) _spos[_stk[--_sp]] = 0;
         }
         return -1;              // No cycle
     }
 
-    private int find(int e) {
-        for( int i=0; i<_sp; i++ )  if( _stk[i] == e ) return i;
-        return -1;
-    }
-    private boolean onStk(int e) { return find(e) != -1; }
-
     private boolean hasClzCycle(int idx) {
         int clinits = 0;
         for( int i=idx; i<_sp; i++ ) {
diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index dea75b2e..ddcdba3c 100644
--- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -97,37 +97,21 @@ public class CodeGen {
         return null;
     }
 
-    // True when fidx is published through a public class or instance field.
+    // Frozen after ParseAll: public initializers and function-valued fields.
     public boolean publicFIDX(int fidx) {
-        if( fidx < GlobalBits.RESERVED ) return false;
-        // A public class initializer is itself an external root; unlike
-        // constructors and methods, it is not reached through a class field.
-        FunNode fun = _linker.atX(fidx);
-        if( fun != null && fun.isClz() && fun.isPublic() )
-            return true;
-        // Include instance methods even while their constant function fields
-        // are stored in each instance rather than on the class object.
-        for( Type t : Parser.TYPES.values() )
-            if( t instanceof TypeStruct clz &&
-                Parser.startsClzPrefix(clz._name) &&
-                Parser.isPublicClassName(clz._name) &&
-                resolvedClass(clz) ) {
-                if( publicFieldFIDX(clz,fidx) ) return true;
-                Type self = Parser.TYPES.get(clz._name.substring(Parser.CLZ.length()));
-                if( self instanceof TypeStruct ts && publicFieldFIDX(ts,fidx) ) return true;
-            }
-        return false;
+        return fidx >= GlobalBits.RESERVED && XInt.bit(publicFIDXs(),fidx);
     }
 
-    private static boolean publicFieldFIDX(TypeStruct clz, int fidx) {
+    private void gatherPublicFields(TypeStruct clz, boolean classFields) {
         boolean hasCtor = clz.field("<ctor>") != null;
-        for( Field fld : clz._fields )
-            if( fld._fname.charAt(0)!='_' && fld._t instanceof TypeFunPtr tfp &&
-                // With a user constructor, class:N.N is the private <init>.
-                !(hasCtor && clz.hiddenInit(fld)) &&
-                XInt.bit(tfp._fidxs,fidx) )
-                return true;
-        return false;
+        for( Field fld : clz._fields ) {
+            // With a user constructor, class:N.N is the private <init>.
+            if( fld._fname.charAt(0)=='_' || fld._t==Type.TOP ||
+                (hasCtor && clz.hiddenInit(fld)) ) continue;
+            if( classFields ) _publicAliases = XInt.make(_publicAliases,fld._alias);
+            if( fld._t instanceof TypeFunPtr tfp )
+                _publicFIDXs = XInt.meet(_publicFIDXs,tfp._fidxs);
+        }
     }
 
     public static boolean hasUserConstructor(TypeStruct self) {
@@ -135,8 +119,7 @@ public class CodeGen {
         return t instanceof TypeStruct clz && clz.field("<ctor>") != null;
     }
 
-    // A forward reference gets a class object and constructor signature so
-    // parsing can proceed, but it has no callable definition yet.
+    // A forward reference has a placeholder class, not a definition yet.
     private static boolean resolvedClass(TypeStruct clz) {
         Type t = Parser.TYPES.get(clz._name.substring(Parser.CLZ.length()));
         return !(t instanceof TypeStruct ts) || !ts._fref;
@@ -154,24 +137,27 @@ public class CodeGen {
      */
     void freezePublicInterface() {
         assert _publicFIDXs==null && _publicAliases==null;
-        int[] fidxs = XInt.EMPTY;
-        for( int fidx=GlobalBits.RESERVED; fidx<_linker._len; fidx++ )
-            if( publicFIDX(fidx) )
-                fidxs = XInt.make(fidxs,fidx);
-        int[] aliases = XInt.EMPTY;
+        _publicFIDXs = _publicAliases = XInt.EMPTY;
         for( Type t : Parser.TYPES.values() )
             if( t instanceof TypeStruct clz &&
                 Parser.startsClzPrefix(clz._name) &&
                 Parser.isPublicClassName(clz._name) &&
                 resolvedClass(clz) ) {
-                boolean hasCtor = clz.field("<ctor>") != null;
-                for( Field fld : clz._fields )
-                    if( fld._fname.charAt(0)!='_' && fld._t!=Type.TOP &&
-                        !(hasCtor && clz.hiddenInit(fld)) )
-                        aliases = XInt.make(aliases,fld._alias);
+                // Gather function pointers from public fields of both class
+                // and instance objects.
+                gatherPublicFields(clz,true);
+                Type self = Parser.TYPES.get(clz._name.substring(Parser.CLZ.length()));
+                if( self instanceof TypeStruct ts ) gatherPublicFields(ts,false);
             }
+        // Limit broad function types to known FIDXs, excluding reserved bits.
+        // Public class initializers are roots without needing a field reference.
+        int[] fidxs = XInt.EMPTY;
+        for( int fidx = GlobalBits.RESERVED; fidx<_linker._len; fidx++ ) {
+            FunNode fun = _linker.atX(fidx);
+            if( XInt.bit(_publicFIDXs,fidx) || (fun!=null && fun.isClz() && fun.isPublic()) )
+                fidxs = XInt.make(fidxs,fidx);
+        }
         _publicFIDXs = fidxs;
-        _publicAliases = aliases;
     }
 
     public int[] publicFIDXs()  { assert _publicFIDXs !=null; return _publicFIDXs;  }
@@ -314,6 +300,8 @@ public class CodeGen {
     // Record elapsed time even on failure, but report completion only on success.
     CodeGen phase(Phase next, boolean ordered, Runnable work) {
         assert ordered : "Cannot run "+next+" after "+_phase;
+        // Serialize reads the checked graph; other phases can change it.
+        if( next!=Phase.Serialize ) _classInitDependencies = null;
         _phase = next;
         long t0 = System.currentTimeMillis();
         work.run();             // Do The Phase
@@ -534,10 +522,18 @@ public class CodeGen {
         } finally { _phase=prior; }
     }
 
-    void resolveInitCycles() {
+    // TypeCheck saves its successful analysis for Serialize. Loading bodies
+    // or entering another graph-changing phase discards it; no stale edges
+    // survive a later Iter/FinalizeIR/TypeCheck sequence.
+    ClassInitDependencies _classInitDependencies;
+
+    ClassInitDependencies resolveInitCycles() {
         while( true ) {
-            Ary<CompUnit> units = new ClassInitDependencies(this).cycleImports();
-            if( units.isEmpty() ) return;
+            ClassInitDependencies deps = new ClassInitDependencies(this);
+            String cycle = deps.check();
+            if( cycle==null ) return deps;
+            Ary<CompUnit> units = deps.cycleImports();
+            if( units.isEmpty() ) throw Parser.error(cycle,null);
             for( CompUnit cu : units ) ParseAll.loadCompUnit(this,cu);
             Phase prior = _phase;
             try {
diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java
index 1f0e803d..1dced3a8 100644
--- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java
+++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java
@@ -102,6 +102,7 @@ public class ElfReader {
 
     // Loads the entire IR
     public TypeStruct loadSimple(CodeGen code) {
+        code._classInitDependencies = null; // Loaded bodies can change init edges.
         Serialize.readAll(code, this, code._aliases, code._fidxs, code._rpcs);
         return _clz;
     }
diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java
index b33ad012..3e4adf5f 100644
--- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java
+++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java
@@ -15,7 +15,8 @@ public class Serialize {
     private final HashMap<CompUnit,Ary<TypeStruct>> _classes = new HashMap<>();
 
     private Serialize(CodeGen code) {
-        _init = new ClassInitDependencies(code);
+        _init = code._classInitDependencies;
+        assert _init!=null; // TypeCheck checked this same, still-unmodified graph.
         // Preserve the canonical declarations, distinct from sharper graph
         // types with the same names.  Gather/sort them once for all objects.
         TreeMap<String,TypeStruct> named = new TreeMap<>();
diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java
index fb82ef0c..78794096 100644
--- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java
+++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java
@@ -9,12 +9,9 @@ import com.seaofnodes.simple.util.Ary;
 // obligations. Queue surviving CLInits during the same walk for Lower's Iter.
 abstract class TypeCheck {
     static void run(CodeGen code) {
-        code.resolveInitCycles();
         // Check for class-init cycles first; such a cycle can prevent other
-        // things from resolving types. The dependency graph is temporary.
-        String clzInitCycle = new ClassInitDependencies(code).check();
-        if( clzInitCycle != null )
-            throw Parser.error(clzInitCycle,null);
+        // things from resolving types. Serialize can reuse the final graph.
+        code._classInitDependencies = code.resolveInitCycles();
 
         Ary<Node> errs = new Ary<>(Node.class);
         code._stop.walk( n -> {