Backport some minor speedups

3 files changed, 52 insertions, 18 deletions

diff --git a/chapter23/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter23/src/main/java/com/seaofnodes/simple/IterPeeps.java
index c4b96c5c..fbbdf5e6 100644
--- a/chapter23/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/chapter23/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -198,7 +198,7 @@ public class IterPeeps {
          * True if Node is on the WorkList
          */
         boolean on( E x ) { return _on.get(x._nid); }
-        boolean isEmpty() { return _len==0; }
+        public boolean isEmpty() { return _len==0; }
 
         /**
          * Removes a random Node from the WorkList; null if WorkList is empty
@@ -208,11 +208,13 @@ public class IterPeeps {
             int idx = _R.nextInt(_len);
             E x = (E)_es[idx];
             _es[idx] = _es[--_len]; // Compress array
+            _es[_len] = null;
             _on.clear(x._nid);
             return x;
         }
 
         public void clear() {
+            Arrays.fill(_es,0,_len,null);
             _len = 0;
             _on.clear();
             _R.setSeed(_seed);
diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
index da45db4f..205a5cb2 100644
--- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
+++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
@@ -4,6 +4,7 @@ import com.seaofnodes.simple.IterPeeps.WorkList;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
 import com.seaofnodes.simple.util.Ary;
+import com.seaofnodes.simple.util.AryInt;
 import com.seaofnodes.simple.util.Utils;
 import java.util.*;
 
@@ -136,24 +137,46 @@ public abstract class GlobalCodeMotion {
     }
 
     // ------------------------------------------------------------------------
+    // Scheduling is not recursive. Retain scratch capacity between schedules,
+    // but release graph references and reset only the entries we used.
+    private static CFGNode[] LATE = new CFGNode[1];
+    // Load NIDs at their CFG block choices, checked against Store blocks.
+    private static int[] ANTI = new int[1];
+    private static final AryInt TOUCHED = new AryInt();
+    private static final Ary<Node> PLACED = new Ary<>(Node.class);
+    private static final WorkList<Node> WORK = new WorkList<>();
+
     private static void schedLate( CodeGen code ) {
-        CFGNode[] late = new CFGNode[code.UID()];
-        Node[] ns = new Node[code.UID()];
-        // Record Load NIDs at all their CFG block choices, then check against
-        // Store block choices to force a Load above an anti-dependent Store.
-        int[] anti = new int[code.UID()];
+        assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty();
+        if( code.UID() > LATE.length ) {
+            int len = Math.max(code.UID(),LATE.length<<1);
+            LATE = new CFGNode[len];
+            ANTI = new int[len];
+        }
+        WORK.clear();
         // Breadth-first scheduling
-        breadth(code._stop,ns,late,anti);
+        // Early scheduling has released the shared visit bits.
+        breadth(code._stop,PLACED,LATE,ANTI,code.visit());
 
         // Copy the best placement choice into the control slot
-        for( int i=0; i<late.length; i++ )
-            if( ns[i] != null && !(ns[i] instanceof ProjNode) )
-                ns[i].setDef(0,late[i]);
+        for( Node n : PLACED )
+            if( !(n instanceof ProjNode) )
+                n.setDef(0,LATE[n._nid]);
+        for( int i=0; i<TOUCHED.len(); i++ )
+            LATE[TOUCHED.at(i)] = null;
+        TOUCHED.clear();
+        clear(PLACED);
     }
 
-    private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) {
+    // Ary.clear retains references; static scratch must release them as well.
+    private static void clear(Ary<Node> nodes) {
+        Arrays.fill(nodes._es,0,nodes._len,null);
+        nodes.clear();
+    }
+
+    private static void breadth(Node stop, Ary<Node> placed, CFGNode[] late, int[] anti, BitSet visit) {
         // Things on the worklist have some (but perhaps not all) uses done.
-        WorkList<Node> work = new WorkList<>();
+        WorkList<Node> work = WORK;
         work.push(stop);
         Node n;
         outer:
@@ -177,16 +200,19 @@ public abstract class GlobalCodeMotion {
                             continue outer;
 
                 // All uses done, schedule
-                _doSchedLate(n,ns,late,anti);
+                _doSchedLate(n,placed,late,anti);
             }
 
+            TOUCHED.push(n._nid);
+
             // A use just finished; reconsider its inputs and waiting loads,
             // even when the shared memory input was already scheduled.
             for( Node def : n._inputs ) {
                 if( def==null ) continue;
                 if( late[def._nid]==null ) work.push(def);
-                wakeLoads(def,late,work,new BitSet());
+                wakeLoads(def,late,work,visit);
             }
+            visit.clear();
             if( n instanceof LoopNode loop )
                 for( Node phi : loop._outputs )
                     if( phi instanceof PhiNode && late[phi._nid]==null )
@@ -194,7 +220,7 @@ public abstract class GlobalCodeMotion {
         }
     }
 
-    private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) {
+    private static void _doSchedLate(Node n, Ary<Node> placed, CFGNode[] late, int[] anti) {
         // Walk uses, gathering the LCA (Least Common Ancestor) of uses
         CFGNode early = n.in(0) instanceof CFGNode cfg ? cfg : n.in(0).cfg0();
         assert early != null;
@@ -217,7 +243,7 @@ public abstract class GlobalCodeMotion {
             if( better(lca,best) )
                 best = lca;
         assert !(best instanceof IfNode);
-        ns  [n._nid] = n;
+        placed.push(n);
         late[n._nid] = best;
     }
 
@@ -259,7 +285,8 @@ public abstract class GlobalCodeMotion {
     private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) {
         // We could skip final-field loads here.
         // Walk LCA->early, flagging Load's block location choices
-        for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() )
+        CFGNode marked = lca;
+        for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() )
             anti[cfg._nid] = load._nid;
         // Walk load->mem uses, looking for Stores causing an anti-dep
         for( Node mem : load.antiDeps() ) {
@@ -287,6 +314,9 @@ public abstract class GlobalCodeMotion {
             default: throw Utils.TODO();
             }
         }
+        // Release this load's marks before another compilation reuses IDs.
+        for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() )
+            anti[cfg._nid] = 0;
         return lca;
     }
 
diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index 6805c1ef..95aa3dc0 100644
--- a/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -147,7 +147,9 @@ public abstract class CFGNode extends Node {
         }
 
         _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this);
-        _bltWalk(2,null,stop, new BitSet());
+        BitSet post = CodeGen.CODE.visit();
+        _bltWalk(2,null,stop, post);
+        post.clear();
     }
     int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) {
         // Pre-walked?