Unify GCM across chapters

Remove the _anti field.
Remove the isPinned() call.
Add a copyEmpty call.

7 files changed, 88 insertions, 74 deletions

diff --git a/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index 99f2f0ea..53f51f86 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -1,5 +1,6 @@
  package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.IterPeeps.WorkList;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
 import java.util.*;
@@ -13,7 +14,7 @@ public abstract class GlobalCodeMotion {
         fixLoops(stop);
         schedEarly();
         Parser.SCHEDULED = true;
-        schedLate(Parser.START);
+        schedLate(stop);
     }
 
     // ------------------------------------------------------------------------
@@ -65,15 +66,13 @@ public abstract class GlobalCodeMotion {
             cfg.loopDepth();
             for( Node n : cfg._inputs )
                 _schedEarly(n,visit);
-            // Strictly for dead infinite loops, we can have entire code blocks
-            // not reachable from below - so we reach down, from above, one
-            // step.  Since _schedEarly modifies the output arrays, the normal
-            // region._outputs ArrayList iterator throws CME.  The extra edges
-            // are always *added* after any Phis, so just walk the Phi prefix.
-            if( cfg instanceof RegionNode region ) {
-                int len = region.nOuts();
+            // In dead infinite loops, entire code blocks may be unreachable
+            // from below.  Reach down from the CFG to their Phis so their
+            // inputs are scheduled too.
+            if( cfg instanceof RegionNode ) {
+                int len = cfg.nOuts();
                 for( int i=0; i<len; i++ )
-                    if( region.out(i) instanceof PhiNode phi )
+                    if( cfg.out(i) instanceof PhiNode phi )
                         _schedEarly(phi,visit);
             }
         }
@@ -92,70 +91,99 @@ public abstract class GlobalCodeMotion {
     private static void _schedEarly(Node n, BitSet visit) {
         if( n==null || visit.get(n._nid) ) return; // Been there, done that
         visit.set(n._nid);
-        // Schedule not-pinned not-CFG inputs before self.  Since skipping
-        // Pinned, this never walks the backedge of Phis (and thus spins around
-        // a data-only loop, eventually attempting relying on some pre-visited-
-        // not-post-visited data op with no scheduled control.
+        // Schedule inputs first, except Phis: following their backedges would
+        // enter a data cycle before its control has been scheduled.
         for( Node def : n._inputs )
-            if( def!=null && !def.isPinned() )
+            if( def!=null && !(def instanceof PhiNode) )
                 _schedEarly(def,visit);
-        // If not-pinned (e.g. constants, projections, phi) and not-CFG
-        if( !n.isPinned() ) {
+        // An existing edge 0 already supplies control (or a Phi/Proj binding).
+        if( n.in(0)==null ) {
             // Schedule at deepest input
             CFGNode early = Parser.START; // Maximally early, lowest idepth
             for( int i=1; i<n.nIns(); i++ )
-                if( n.in(i).cfg0().idepth() > early.idepth() )
+                if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() )
                     early = n.in(i).cfg0(); // Latest/deepest input
             n.setDef(0,early);              // First place this can go
         }
     }
 
     // ------------------------------------------------------------------------
-    private static void schedLate(StartNode start) {
+    private static void schedLate( StopNode stop) {
         CFGNode[] late = new CFGNode[Node.UID()];
         Node[] ns = new Node[Node.UID()];
-        _schedLate(start,ns,late);
+        // 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()];
+        // Breadth-first scheduling
+        breadth(stop,ns,late,anti);
+
+        // Copy the best placement choice into the control slot
         for( int i=0; i<late.length; i++ )
-            if( ns[i] != null )
+            if( ns[i] != null && !(ns[i] instanceof ProjNode) )
                 ns[i].setDef(0,late[i]);
     }
 
-    // Forwards post-order pass.  Schedule all outputs first, then draw an
-    // idom-tree line from the LCA of uses to the early schedule.  Schedule is
-    // legal anywhere on this line; pick the most control-dependent (largest
-    // idepth) in the shallowest loop nest.
-    private static void _schedLate(Node n, Node[] ns, CFGNode[] late) {
-        if( late[n._nid]!=null ) return; // Been there, done that
-        // These I know the late schedule of, and need to set early for loops
-        if( n instanceof CFGNode cfg ) late[n._nid] = cfg.blockHead() ? cfg : cfg.cfg(0);
-        if( n instanceof PhiNode phi ) late[n._nid] = phi.region();
-
-        // Walk Stores before Loads, so we can get the anti-deps right
-        for( Node use : n._outputs )
-            if( isForwardsEdge(use,n) &&
-                use._type instanceof TypeMem )
-                _schedLate(use,ns,late);
-        // Walk everybody now
-        for( Node use : n._outputs )
-            if( isForwardsEdge(use,n) )
-                _schedLate(use,ns,late);
-        // Already implicitly scheduled
-        if( n.isPinned() ) return;
-        // Need to schedule n
+    private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) {
+        // Things on the worklist have some (but perhaps not all) uses done.
+        WorkList<Node> work = new WorkList<>();
+        work.push(stop);
+        Node n;
+        outer:
+        while( (n = work.pop()) != null ) {
+            assert late[n._nid]==null; // No double visit
+            // These I know the late schedule of, and need to set early for loops
+            if( n instanceof CFGNode cfg ) late[n._nid] = cfg.blockHead() ? cfg : cfg.cfg(0);
+            else if( n instanceof PhiNode phi ) late[n._nid] = phi.region();
+            // These nodes have a fixed late placement at their original control.
+            else if( n instanceof ProjNode || n instanceof NewNode || n==Parser.ZERO ) late[n._nid] = n.cfg0();
+            else {
+
+                // All uses done?
+                for( Node use : n._outputs )
+                    if( use!=null && late[use._nid]==null )
+                        continue outer; // Nope, await all uses done
+
+                // Loads need their memory inputs' uses also done
+                if( n instanceof LoadNode ld )
+                    for( Node memuse : ld.mem()._outputs )
+                        if( late[memuse._nid]==null && memuse._type instanceof TypeMem )
+                            continue outer;
+
+                // All uses done, schedule
+                _doSchedLate(n,ns,late,anti);
+            }
 
+            // 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);
+                for( Node out : def._outputs )
+                    if( out instanceof LoadNode ld && late[ld._nid]==null )
+                        work.push(ld);
+            }
+            if( n instanceof LoopNode loop )
+                for( Node phi : loop._outputs )
+                    if( phi instanceof PhiNode && late[phi._nid]==null )
+                        work.push(phi);
+        }
+    }
+
+    private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) {
         // Walk uses, gathering the LCA (Least Common Ancestor) of uses
-        CFGNode early = (CFGNode)n.in(0);
+        CFGNode early = n.in(0) instanceof CFGNode cfg ? cfg : n.in(0).cfg0();
         assert early != null;
         CFGNode lca = null;
         for( Node use : n._outputs )
-            lca = use_block(n,use, late).domLCA(lca);
+            if( use != null )
+              lca = use_block(n,use, late).domLCA(lca);
 
         // Loads may need anti-dependencies, raising their LCA
         if( n instanceof LoadNode load )
-            lca = find_anti_dep(lca,load,early,late);
+            lca = find_anti_dep(lca,load,early,late,anti);
 
-        // Walk up from the LCA to the early, looking for best place.  This is the
-        // lowest execution frequency, approximated by least loop depth and
+        // Walk up from the LCA to the early, looking for best place.  This is
+        // the lowest execution frequency, approximated by least loop depth and
         // deepest control flow.
         CFGNode best = lca;
         lca = lca.idom();       // Already found best for starting LCA
@@ -175,8 +203,7 @@ public abstract class GlobalCodeMotion {
         CFGNode found=null;
         for( int i=1; i<phi.nIns(); i++ )
             if( phi.in(i)==n )
-                if( found==null ) found = phi.region().cfg(i);
-                else Utils.TODO(); // Can be more than once
+                found = phi.region().cfg(i).domLCA(found); // Can be more than one matching input.
         assert found!=null;
         return found;
     }
@@ -184,33 +211,29 @@ public abstract class GlobalCodeMotion {
 
     // Least loop depth first, then largest idepth
     private static boolean better( CFGNode lca, CFGNode best ) {
-        return lca._loopDepth < best._loopDepth ||
-                (lca.idepth() > best.idepth() || best instanceof IfNode);
-    }
-
-    // Skip iteration if a backedge
-    private static boolean isForwardsEdge(Node use, Node def) {
-        return use != null && def != null &&
-            !(use.nIns()>2 && use.in(2)==def && (use instanceof LoopNode || (use instanceof PhiNode phi && phi.region() instanceof LoopNode)));
+        return lca.loopDepth() < best.loopDepth() ||
+            lca instanceof NeverNode ||
+            lca.idepth() > best.idepth() ||
+            best instanceof IfNode;
     }
 
-    private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late) {
+    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() )
-            cfg._anti = load._nid;
+            anti[cfg._nid] = load._nid;
         // Walk load->mem uses, looking for Stores causing an anti-dep
         for( Node mem : load.mem()._outputs ) {
             switch( mem ) {
             case StoreNode st:
-                lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st);
+                lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti);
                 break;
             case PhiNode phi:
                 // Repeat anti-dep for matching Phi inputs.
                 // No anti-dep edges but may raise the LCA.
                 for( int i=1; i<phi.nIns(); i++ )
                     if( phi.in(i)==load.mem() )
-                        lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null);
+                        lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null,anti);
                 break;
             case LoadNode ld: break; // Loads do not cause anti-deps on other loads
             case ReturnNode ret: break; // Load must already be ahead of Return
@@ -221,11 +244,12 @@ public abstract class GlobalCodeMotion {
     }
 
     //
-    private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) {
-        // Walk store blocks "reach" from its scheduled location to its earliest
+    private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st, int[] anti ) {
+        // Preserve the full store range for the earlier evaluator scheduler.
+        // It places nodes independently of GCM and may hoist this store.
         for( ; stblk != defblk.idom(); stblk = stblk.idom() ) {
             // Store and Load overlap, need anti-dependence
-            if( stblk._anti==load._nid ) {
+            if( anti[stblk._nid]==load._nid ) {
                 lca = stblk.domLCA(lca); // Raise Loads LCA
                 if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved,
                     st.addDef(load);   // Add anti-dep as well
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index e02dd1e1..ea67d17d 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -24,7 +24,6 @@ public abstract class CFGNode extends Node {
     public CFGNode(Node... nodes) { super(nodes); }
 
     @Override public boolean isCFG() { return true; }
-    @Override public boolean isPinned() { return true; }
 
     public CFGNode cfg(int idx) { return (CFGNode)in(idx); }
 
@@ -77,9 +76,6 @@ public abstract class CFGNode extends Node {
     public int _loopDepth;
     public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(0).loopDepth()) : _loopDepth; }
 
-    // Anti-dependence field support
-    public int _anti;           // Per-CFG field to help find anti-deps
-
     // ------------------------------------------------------------------------
     // Support routines for Global Code Motion
 
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index bbd0ce8a..37a529d1 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -37,7 +37,6 @@ public class ConstantNode extends Node {
 
     @Override public boolean isMultiTail() { return true; }
     // The special forever-zero is pinned, all others can sink
-    @Override public boolean isPinned() { return this==Parser.ZERO; }
 
     @Override
     public Type compute() { return _con; }
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java
index 0724ec56..c00fee62 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java
@@ -26,7 +26,6 @@ public class NewNode extends Node {
         return sb.append(_ptr._obj.str());
     }
 
-    @Override public boolean isPinned() { return true; }
 
     @Override
     public Type compute() { return _ptr; }
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java
index e095fbfc..e5bad801 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -540,8 +540,6 @@ public abstract class Node implements OutNode {
     /** Return block start from a isCFG() */
     public Node getBlockStart() { return null; }
 
-    /** Pinned in the schedule */
-    public boolean isPinned() { return false; }
 
     // ------------------------------------------------------------------------
     // Peephole utilities
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index a07dc140..ddd0ca72 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -38,7 +38,6 @@ public class PhiNode extends Node {
     public CFGNode region() { return (CFGNode)in(0); }
     @Override public boolean isMultiTail() { return true; }
     @Override public boolean isMem() { return _declaredType instanceof TypeMem; }
-    @Override public boolean isPinned() { return true; }
 
     @Override
     public Type compute() {
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index f94e98a7..93239a61 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -28,7 +28,6 @@ public class ProjNode extends Node {
 
     @Override public boolean isMultiTail() { return in(0).isMultiHead(); }
     @Override public boolean isMem() { return _type instanceof TypeMem; }
-    @Override public boolean isPinned() { return true; }
 
     @Override
     public Type compute() {