Unify GCM across chapters

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

6 files changed, 110 insertions, 43 deletions

diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index f68043c4..d96bd178 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -12,10 +12,61 @@ public abstract class GlobalCodeMotion {
     // following block).  There are no unreachable infinite loops.
     public static void buildCFG( StartNode start, StopNode stop ) {
         schedEarly(start);
+        breakUpGlobalConstants(start);
         schedLate(stop);
     }
 
 
+    // After early scheduling, every global chain member has Start in slot 0.
+    // Give each function one private copy of the entire dependency graph.
+    private static void breakUpGlobalConstants( StartNode start ) {
+        var globals = new IdentityHashMap<Node,Boolean>();
+        var cons = new ArrayList<Node>();
+        for( Node con : start._outputs )
+            if( con!=null && !(con instanceof CFGNode) &&
+                con.isConst() ) {
+                globals.put(con,true);
+                cons.add(con.keep()); // Preserve original inputs while rewiring users.
+            }
+
+        var copies = new IdentityHashMap<FunNode,IdentityHashMap<Node,Node>>();
+        for( Node con : cons )
+            for( Node use : con._outputs.asAry() ) {
+                if( use==null || globals.containsKey(use) ) continue;
+                for( int i=0; i<use.nIns(); i++ ) {
+                    if( use.in(i)!=con ) continue;
+                    FunNode fun = useFun(use,i);
+                    if( fun==null ) continue; // Unknown-caller types stay global.
+                    var local = copies.computeIfAbsent(fun,f -> new IdentityHashMap<>());
+                    use.setDef(i,cloneGlobal(con,fun,globals,local));
+                }
+            }
+        for( Node con : cons ) con.unkill();
+    }
+
+    private static Node cloneGlobal(Node con, FunNode fun, IdentityHashMap<Node,Boolean> globals,
+                                    IdentityHashMap<Node,Node> copies) {
+        Node copy = copies.get(con);
+        if( copy!=null ) return copy;
+        copies.put(con,copy=con.copyEmpty());
+        copy.addDef(fun);
+        for( int i=1; i<con.nIns(); i++ ) {
+            Node def = con.in(i);
+            copy.addDef(globals.containsKey(def) ? cloneGlobal(def,fun,globals,copies) : def);
+        }
+        return copy;
+    }
+
+    private static FunNode useFun(Node use, int idx) {
+        if( use instanceof ReturnNode ret ) return ret.fun();
+        // Calls are still linked: a Parm input is evaluated in its caller.
+        CFGNode cfg = use instanceof ParmNode parm ? parm.fun().cfg(idx) : use.cfg0();
+        while( cfg!=null && !(cfg instanceof FunNode) )
+            cfg = cfg.idom();
+        return (FunNode)cfg;
+    }
+
+
     // ------------------------------------------------------------------------
     // Visit all nodes in CFG Reverse Post-Order, essentially defs before uses
     // (except at loops).  Since defs are visited first - and hoisted as early
@@ -31,6 +82,9 @@ public abstract class GlobalCodeMotion {
             cfg.loopDepth();
             for( Node n : cfg._inputs )
                 _schedEarly(n,visit);
+            // 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 )
                 for( Node phi : cfg._outputs )
                     if( phi instanceof PhiNode )
@@ -54,18 +108,15 @@ public abstract class GlobalCodeMotion {
         if( n==null || visit.get(n._nid) ) return; // Been there, done that
         assert !(n instanceof CFGNode);
         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 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
-            if( n.in(0) instanceof CFGNode cfg ) early = cfg;
             for( int i=1; i<n.nIns(); i++ )
                 if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() )
                     early = n.in(i).cfg0(); // Latest/deepest input
@@ -77,8 +128,11 @@ public abstract class GlobalCodeMotion {
     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()];
         // Breadth-first scheduling
-        breadth(stop,ns,late);
+        breadth(stop,ns,late,anti);
 
         // Copy the best placement choice into the control slot
         for( int i=0; i<late.length; i++ )
@@ -86,7 +140,7 @@ public abstract class GlobalCodeMotion {
                 ns[i].setDef(0,late[i]);
     }
 
-    private static void breadth(Node stop, Node[] ns, CFGNode[] late) {
+    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);
@@ -118,22 +172,26 @@ public abstract class GlobalCodeMotion {
                             continue outer;
 
                 // All uses done, schedule
-                _doSchedLate(n,ns,late);
+                _doSchedLate(n,ns,late,anti);
             }
 
-            // Walk all inputs and put on worklist, as their last-use might now be done
-            for( Node def : n._inputs )
-                if( def!=null && late[def._nid]==null ) {
-                    work.push(def);
-                    // if the def has a load use, maybe the load can fire
-                    for( Node ld : def._outputs )
-                        if( ld instanceof LoadNode && late[ld._nid]==null )
-                            work.push(ld);
-                }
+            // 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) {
+    private static void _doSchedLate(Node n, Node[] ns, 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;
@@ -144,7 +202,7 @@ public abstract class GlobalCodeMotion {
 
         // 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
@@ -167,7 +225,7 @@ public abstract class GlobalCodeMotion {
         CFGNode found=null;
         for( int i=1; i<phi.nIns(); i++ )
             if( phi.in(i)==n )
-                found = phi.region().cfg(i).domLCA(found,null);
+                found = phi.region().cfg(i).domLCA(found,null); // Can be more than one matching input.
 
         assert found!=null;
         return found;
@@ -177,31 +235,33 @@ 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);
+            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:
                 assert late[st._nid]!=null;
-                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 CallNode st:
                 assert late[st._nid]!=null;
-                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 NewNode st: break;
             case LoadNode ld: break; // Loads do not cause anti-deps on other loads
@@ -215,11 +275,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,null); // Raise Loads LCA
                 if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved,
                     st.addDef(load);   // Add anti-dep as well
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 dc486549..ece46e80 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -78,9 +78,6 @@ public abstract class CFGNode extends Node {
         return lhs;
     }
 
-    // Anti-dependence field support
-    public int _anti;           // Per-CFG field to help find anti-deps
-
     // ------------------------------------------------------------------------
     // Loop nesting
     public LoopNode loop() { return _ltree._head; }
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CastNode.java
index d8a968c1..6438abb5 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/CastNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CastNode.java
@@ -21,7 +21,6 @@ public class CastNode extends Node {
     @Override
     public String uniqueName() { return "Cast_" + _nid; }
 
-    @Override public boolean isPinned() { return true; }
     @Override public boolean isConst() { return true; }
 
     @Override
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java
index c9369742..02b95669 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -11,14 +11,14 @@ import java.util.function.Function;
  * The Node class provides common functionality used by all subtypes.
  * Subtypes of Node specialize by overriding methods.
  */
-public abstract class Node {
+public abstract class Node implements Cloneable {
 
     /**
      * Each node has a unique dense Node ID within a compilation context
      * The ID is useful for debugging, for using as an offset in a bitvector,
      * as well as for computing equality of nodes (to be implemented later).
      */
-    public final int _nid;
+    public int _nid;
 
     /**
      * Inputs to the node. These are use-def references to Nodes.
@@ -27,7 +27,7 @@ public abstract class Node {
      * Ordering is required because e.g. "a/b" is different from "b/a".
      * The first input (offset 0) is often a {@link CFGNode} node.
      */
-    public final Ary<Node> _inputs;
+    public Ary<Node> _inputs;
 
     /**
      * Outputs reference Nodes that are not null and have this Node as an
@@ -38,7 +38,7 @@ public abstract class Node {
      * walked in either direction.  These outputs are typically used for
      * efficient optimizations but otherwise have no semantics meaning.
      */
-    public final Ary<Node> _outputs;
+    public Ary<Node> _outputs;
 
 
     /**
@@ -556,8 +556,6 @@ public abstract class Node {
     /** Is this Node Memory related */
     public boolean isMem() { return false; }
 
-    /** Pinned in the schedule; these are data nodes whose input#0 is not allowed to change */
-    public boolean isPinned() { return false; }
 
     // Semantic change to the graph (so NOT a peephole), used by the Parser.
     // If any input is a float, flip to a float-flavored opcode and widen any
@@ -612,6 +610,20 @@ public abstract class Node {
     // Does not need to be implemented in isCFG() nodes.
     Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); }
 
+    // Exact-class copy with fresh identity and no edges.  Unlike machine
+    // rematerialization copies, this never registers or copies input edges.
+    public final Node copyEmpty() {
+        Node n;
+        try { n = (Node)clone(); }
+        catch( Exception e ) { throw new RuntimeException(e); }
+        n._nid = UNIQUE_ID++; // allocate unique dense ID
+        n._inputs  = new Ary<>(Node.class);
+        n._outputs = new Ary<>(Node.class);
+        n._deps = null;
+        n._hash = 0;
+        return n;
+    }
+
     // Report any post-optimize errors
     public Parser.ParseException err() { return null; }
 
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 9aed8287..4ca50a3c 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -44,7 +44,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/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index ea211dd2..81917bef 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -37,7 +37,6 @@ public class ProjNode extends Node implements MultiUse {
 
     @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() {