Backport some minor speedupsmain

4 files changed, 97 insertions, 27 deletions

diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter28a/src/main/java/com/seaofnodes/simple/IterPeeps.java
index e65ef6d9..39230eb2 100644
--- a/chapter28a/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/chapter28a/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -333,17 +333,18 @@ 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 boolean isEmpty() { return _len==0; }
-        //Node[] asAry() { return Arrays.copyOf(_es,_len); }
-        //public void clear() {
-        //    _len = 0;
-        //    _on.clear();
-        //    _R.setSeed(_seed);
-        //    _totalWork = 0;
-        //}
+        public void clear() {
+            Arrays.fill(_es,0,_len,null);
+            _len = 0;
+            _on.clear();
+            _R.setSeed(_seed);
+            _totalWork = 0;
+        }
     }
 }
diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter28a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
index 4477025b..ba3743e3 100644
--- a/chapter28a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
+++ b/chapter28a/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,25 +137,53 @@ 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 Ary<Node> ANTIDEPS = 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()];
-        Ary<Node> antideps = new Ary<>(Node.class);
+        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, antideps);
+        // Early scheduling has released the shared visit bits.
+        breadth(code._stop,PLACED,LATE,ANTI,ANTIDEPS,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);
+        clear(ANTIDEPS);
+    }
+
+    // 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, Node[] ns, CFGNode[] late, int[] anti, Ary<Node> antideps) {
+    private static Ary<Node> antiDeps(MemOpNode load, Ary<Node> antideps) {
+        clear(antideps);
+        return load.antiDeps(antideps);
+    }
+
+    private static void breadth(Node stop, Ary<Node> placed, CFGNode[] late, int[] anti, Ary<Node> antideps, 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:
@@ -173,21 +202,24 @@ public abstract class GlobalCodeMotion {
 
                 // Loads need their memory inputs' uses also done
                 if( n instanceof MemOpNode ld && ld._isLoad )
-                    for( Node memuse : ld.antiDeps(antideps) )
+                    for( Node memuse : antiDeps(ld,antideps) )
                         if( late[memuse._nid]==null )
                             continue outer;
 
                 // All uses done, schedule
-                _doSchedLate(n,ns,late,anti,antideps);
+                _doSchedLate(n,placed,late,anti,antideps);
             }
 
+            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 )
@@ -195,7 +227,7 @@ public abstract class GlobalCodeMotion {
         }
     }
 
-    private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti, Ary<Node> antideps) {
+    private static void _doSchedLate(Node n, Ary<Node> placed, CFGNode[] late, int[] anti, Ary<Node> antideps) {
         // 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 +249,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;
     }
 
@@ -260,10 +292,11 @@ public abstract class GlobalCodeMotion {
     private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti, Ary<Node> antideps) {
         // We could skip final-field loads here.
         // Walk LCA->early, flagging Load's block location choices
-        for( CFGNode cfg=lca; cfg!=early.idom(); cfg = cfg.idom() )
+        CFGNode marked = lca;
+        for( CFGNode cfg = marked; 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(antideps) ) {
+        for( Node mem : antiDeps(load,antideps) ) {
             if( mem instanceof PhiNode phi ) {
                 // Inputs carrying different memory might overwrite this alias.
                 // Raise the LCA for those paths; the unchanged-memory paths
@@ -279,6 +312,9 @@ public abstract class GlobalCodeMotion {
                 lca = anti_dep(load,late[mem._nid],mem.cfg0(),lca,mem,anti);
             }
         }
+        // Release this load's marks before another compilation reuses IDs.
+        for( CFGNode cfg = marked; cfg!=early.idom(); cfg = cfg.idom() )
+            anti[cfg._nid] = 0;
         return lca;
     }
 
diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index 4f225fbe..e07b241b 100644
--- a/chapter28a/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -203,7 +203,7 @@ public abstract class CFGNode extends Node {
         _ltree = stop._ltree = CodeGen.CODE.XCTRL._ltree = new LoopTree((StartNode)this);
         Ary<FunNode> work = new Ary<>(FunNode.class);
 
-        BitSet post = new BitSet();
+        BitSet post = CodeGen.CODE.visit();
         int pre = 1;
         _pre = pre++;
         for( FunNode fun : funs ) {
@@ -219,6 +219,7 @@ public abstract class CFGNode extends Node {
 
         for( int i=0; i<work._len; i++ )
             pre = work.at(i)._bltWalk(pre,work.at(i),stop, post, work);
+        post.clear();
     }
 
     int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post, Ary<FunNode> work ) {
diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter28a/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java
new file mode 100644
index 00000000..319c94b0
--- /dev/null
+++ b/chapter28a/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java
@@ -0,0 +1,32 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.CodeGen;
+import org.junit.Test;
+import static org.junit.Assert.assertEquals;
+
+public class SchedulingScratchTest {
+    @Test public void testScratchAcrossCompilations() {
+        String src = """
+            int[] !xs = new int[2];
+            xs[0] = arg;
+            int sum = 0;
+            int i = 0;
+            while( i<5 ) {
+                int old = xs[arg&1];
+                xs[0] = i;
+                sum = sum + old;
+                i = i + 1;
+            }
+            return sum;
+            """;
+        // Each fresh compilation reuses node IDs and the scheduler's scratch.
+        for( int round=0; round<3; round++ ) {
+            CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck);
+            // A small graph after many earlier node allocations.
+            if( round==0 ) code._uid += 100_000;
+            assertEquals("6",Eval2.eval(code,0));
+            assertEquals("0",Eval2.eval(code,1));
+            assertEquals("8",Eval2.eval(code,2));
+        }
+    }
+}