Backport some minor speedups

2 files changed, 39 insertions, 15 deletions

diff --git a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index b431f82c..888c1a5e 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -111,24 +111,38 @@ 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 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);
 
         // Copy the best placement choice into the control slot
-        for( int i=0; i<late.length; i++ )
-            if( ns[i] != null )
-                ns[i].setDef(0,late[i]);
+        for( Node n : PLACED )
+            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) {
         // 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:
@@ -153,9 +167,11 @@ 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 ) {
@@ -172,7 +188,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 = (CFGNode)n.in(0);
         assert early != null;
@@ -193,7 +209,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;
     }
 
@@ -233,7 +249,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.mem()._outputs ) {
@@ -254,6 +271,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/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java
index 7075d526..f7be3ad8 100644
--- a/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -194,11 +194,15 @@ 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 boolean isEmpty() { return _len==0; }
+
         public void clear() {
+            Arrays.fill(_es,0,_len,null);
             _len = 0;
             _on.clear();
             _R.setSeed(_seed);