Backport some minor speedups

3 files changed, 48 insertions, 18 deletions

diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index 2019b714..2a1ca2f5 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -125,24 +125,41 @@ public abstract class GlobalCodeMotion {
     }
 
     // ------------------------------------------------------------------------
+    private static final BitSet WAKE_VISIT = new BitSet();
+
+    // 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 ArrayList<Node> TOUCHED = new ArrayList<>();
+    private static final ArrayList<Node> PLACED = new ArrayList<>();
+    private static final WorkList<Node> WORK = new WorkList<>();
+
     private static void schedLate( StopNode stop) {
-        CFGNode[] late = new CFGNode[Node.UID()];
-        Node[] ns = new Node[Node.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[Node.UID()];
+        assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty();
+        if( Node.UID() > LATE.length ) {
+            int len = Math.max(Node.UID(),LATE.length<<1);
+            LATE = new CFGNode[len];
+            ANTI = new int[len];
+        }
+        WORK.clear();
         // Breadth-first scheduling
-        breadth(stop,ns,late,anti);
+        breadth(stop,PLACED,LATE,ANTI,WAKE_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( Node n : TOUCHED )
+            LATE[n._nid] = null;
+        TOUCHED.clear();
+        PLACED.clear();
     }
 
-    private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) {
+    private static void breadth(Node stop, ArrayList<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:
@@ -166,16 +183,19 @@ public abstract class GlobalCodeMotion {
                             continue outer;
 
                 // All uses done, schedule
-                _doSchedLate(n,ns,late,anti);
+                _doSchedLate(n,placed,late,anti);
             }
 
+            TOUCHED.add(n);
+
             // 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 )
@@ -183,7 +203,7 @@ public abstract class GlobalCodeMotion {
         }
     }
 
-    private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) {
+    private static void _doSchedLate(Node n, ArrayList<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;
@@ -205,7 +225,7 @@ public abstract class GlobalCodeMotion {
             if( better(lca,best) )
                 best = lca;
         assert !(best instanceof IfNode);
-        ns  [n._nid] = n;
+        placed.add(n);
         late[n._nid] = best;
     }
 
@@ -246,7 +266,8 @@ public abstract class GlobalCodeMotion {
     private static CFGNode find_anti_dep(CFGNode lca, LoadNode 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() ) {
@@ -274,6 +295,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/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java
index 1792dada..46bdd4e1 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -187,7 +187,7 @@ public abstract 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
@@ -197,11 +197,13 @@ public abstract 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/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index 49398838..93c86ff6 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -100,9 +100,13 @@ public abstract class CFGNode extends Node {
     // Tag all CFG Nodes with their containing LoopNode; LoopNodes themselves
     // also refer to *their* containing LoopNode, as well as have their depth.
     // Start contains the function bodies at depth 0; real loops add depth.
+    private static final BitSet POST = new BitSet();
+
     public void buildLoopTree(StopNode stop) {
         _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this);
-        _bltWalk(2,null,stop, new BitSet());
+        BitSet post = POST;
+        _bltWalk(2,null,stop, post);
+        post.clear();
     }
     int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) {
         // Pre-walked?