diff options
| author | Cliff Click <cliffc@acm.org> | 2026-09-20 10:04:48 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-09-20 10:04:48 -0700 |
| commit | db3ca780c26b78cbe129a5c1bdf0d8ff7d867d1b (patch) | |
| tree | aa12f702c8b558446b06944ed5301dc826245c8f | |
| parent | 6e59fc1b71f2098c8baf90a6c54e5a33b7291e94 (diff) | |
| download | Simple-db3ca780c26b78cbe129a5c1bdf0d8ff7d867d1b.tar.gz Simple-db3ca780c26b78cbe129a5c1bdf0d8ff7d867d1b.zip | |
Unify GCM across chapters
Remove the _anti field.
Remove the isPinned() call.
Add a copyEmpty call.
113 files changed, 1627 insertions, 1182 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() { diff --git a/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index c44503ae..bf7d1baa 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter12/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.*; @@ -12,7 +13,7 @@ public abstract class GlobalCodeMotion { public static void buildCFG( StopNode stop ) { schedEarly(); Parser.SCHEDULED = true; - schedLate(Parser.START); + schedLate(stop); } // ------------------------------------------------------------------------ @@ -64,15 +65,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); } } @@ -91,70 +90,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 a - // 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,null); + if( use != null ) + lca = use_block(n,use, late).domLCA(lca,null); // 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 - // lowest execution frequency, approximated by least loop depth and + // 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 @@ -174,8 +202,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,null); // Can be more than one matching input. assert found!=null; return found; } @@ -183,33 +210,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,null); // 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/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 07ff0b15..c690a83c 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter12/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); } @@ -78,9 +77,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/chapter12/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index bbd0ce8a..37a529d1 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter12/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/chapter12/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/NewNode.java index 0724ec56..c00fee62 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter12/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/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java index 3e77f1db..352257a9 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java @@ -541,8 +541,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; } // 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 diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java index ebed8dd1..02a4020f 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter12/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/chapter12/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/ProjNode.java index f94e98a7..93239a61 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter12/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() { diff --git a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 865f7036..a270f026 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -69,15 +69,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); } } @@ -96,19 +94,17 @@ 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 } @@ -118,8 +114,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++ ) @@ -127,7 +126,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); @@ -138,12 +137,13 @@ public abstract class GlobalCodeMotion { // 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(); - else if( n.isPinned() ) late[n._nid] = n.cfg0(); + // These nodes have a fixed late placement at their original control. + else if( n instanceof ProjNode || n instanceof NewNode || n==Parser.ZERO || n instanceof CastNode ) late[n._nid] = n.cfg0(); else { // All uses done? for( Node use : n._outputs ) - if( late[use._nid]==null ) + if( use!=null && late[use._nid]==null ) continue outer; // Nope, await all uses done // Loads need their memory inputs' uses also done @@ -153,22 +153,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 = (CFGNode)n.in(0); assert early != null; @@ -178,7 +182,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 @@ -201,8 +205,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,null); // Can be more than one matching input. assert found!=null; return found; } @@ -210,28 +213,30 @@ 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); + 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: 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 LoadNode ld: break; // Loads do not cause anti-deps on other loads case ReturnNode ret: break; // Load must already be ahead of Return @@ -243,11 +248,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 && Utils.find(st._inputs,load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 07ff0b15..c690a83c 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter13/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); } @@ -78,9 +77,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/chapter13/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/CastNode.java index fbf0e518..38d6a126 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -21,8 +21,6 @@ public class CastNode extends Node { @Override public String uniqueName() { return "Cast_" + _nid; } - @Override - public boolean isPinned() { return true; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index bbd0ce8a..37a529d1 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/NewNode.java index 0724ec56..c00fee62 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter13/src/main/java/com/seaofnodes/simple/node/Node.java index 766349ce..c738205b 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/Node.java @@ -541,8 +541,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; } // 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 diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/PhiNode.java index ebed8dd1..02a4020f 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter13/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/chapter13/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/ProjNode.java index f94e98a7..93239a61 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter13/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() { diff --git a/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 865f7036..a270f026 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -69,15 +69,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); } } @@ -96,19 +94,17 @@ 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 } @@ -118,8 +114,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++ ) @@ -127,7 +126,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); @@ -138,12 +137,13 @@ public abstract class GlobalCodeMotion { // 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(); - else if( n.isPinned() ) late[n._nid] = n.cfg0(); + // These nodes have a fixed late placement at their original control. + else if( n instanceof ProjNode || n instanceof NewNode || n==Parser.ZERO || n instanceof CastNode ) late[n._nid] = n.cfg0(); else { // All uses done? for( Node use : n._outputs ) - if( late[use._nid]==null ) + if( use!=null && late[use._nid]==null ) continue outer; // Nope, await all uses done // Loads need their memory inputs' uses also done @@ -153,22 +153,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 = (CFGNode)n.in(0); assert early != null; @@ -178,7 +182,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 @@ -201,8 +205,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,null); // Can be more than one matching input. assert found!=null; return found; } @@ -210,28 +213,30 @@ 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); + 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: 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 LoadNode ld: break; // Loads do not cause anti-deps on other loads case ReturnNode ret: break; // Load must already be ahead of Return @@ -243,11 +248,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 && Utils.find(st._inputs,load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 07ff0b15..c690a83c 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter14/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); } @@ -78,9 +77,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/chapter14/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/CastNode.java index fbf0e518..38d6a126 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -21,8 +21,6 @@ public class CastNode extends Node { @Override public String uniqueName() { return "Cast_" + _nid; } - @Override - public boolean isPinned() { return true; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index bbd0ce8a..37a529d1 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter14/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/chapter14/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/NewNode.java index 0724ec56..c00fee62 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter14/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/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java index 2ef37518..3956ed6b 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java @@ -539,8 +539,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; } // 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 diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 05584423..42f8c86e 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter14/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/chapter14/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/ProjNode.java index f94e98a7..93239a61 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter14/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() { diff --git a/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 27f69c42..27307d32 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -69,6 +69,15 @@ 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 ) { + int len = cfg.nOuts(); + for( int i=0; i<len; i++ ) + if( cfg.out(i) instanceof PhiNode phi ) + _schedEarly(phi,visit); + } } } @@ -86,20 +95,17 @@ 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 ) _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).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 } @@ -109,8 +115,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++ ) @@ -118,7 +127,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); @@ -148,22 +157,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; @@ -174,7 +187,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 @@ -197,8 +210,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,null); // Can be more than one matching input. assert found!=null; return found; } @@ -206,32 +218,34 @@ 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); + 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: 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 NewNode 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 LoadNode ld: break; // Loads do not cause anti-deps on other loads case ReturnNode ret: break; // Load must already be ahead of Return @@ -243,11 +257,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 && Utils.find(st._inputs,load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 704dea8d..06596ce0 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -75,9 +75,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/chapter15/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/CastNode.java index fbf0e518..38d6a126 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -21,8 +21,6 @@ public class CastNode extends Node { @Override public String uniqueName() { return "Cast_" + _nid; } - @Override - public boolean isPinned() { return true; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter15/src/main/java/com/seaofnodes/simple/node/Node.java index 7c22a50e..b65630bb 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/Node.java @@ -535,8 +535,6 @@ public abstract class Node implements OutNode { /** Return block start from a isCFG() */ public Node getBlockStart() { return null; } - /** 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 diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 139e80a3..ddca3034 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter15/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/chapter15/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 73c1fa15..cd57b85c 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -29,7 +29,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() { diff --git a/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 6a4728c3..31302ffd 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -69,10 +69,15 @@ public abstract class GlobalCodeMotion { cfg.loopDepth(); // Pre-compute loop depth for( Node n : cfg._inputs ) _schedEarly(n,visit); - if( cfg instanceof RegionNode ) - for( Node phi : cfg._outputs ) - if( phi instanceof PhiNode ) + // 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( cfg.out(i) instanceof PhiNode phi ) _schedEarly(phi,visit); + } } } @@ -90,20 +95,17 @@ 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).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 } @@ -113,8 +115,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++ ) @@ -122,7 +127,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); @@ -153,22 +158,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; @@ -179,7 +188,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 @@ -202,8 +211,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,null); // Can be more than one matching input. assert found!=null; return found; } @@ -211,32 +219,34 @@ 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); + 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: 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 NewNode 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 LoadNode ld: break; // Loads do not cause anti-deps on other loads case ReturnNode ret: break; // Load must already be ahead of Return @@ -249,11 +259,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; stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence - if( !(stblk instanceof IfNode) && stblk._anti==load._nid ) { + if( !(stblk instanceof IfNode) && 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/chapter16/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 704dea8d..06596ce0 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -75,9 +75,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/chapter16/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/CastNode.java index 462d6cba..38d6a126 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter16/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 StringBuilder _print1(StringBuilder sb, BitSet visited) { diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter16/src/main/java/com/seaofnodes/simple/node/Node.java index e1e6283a..daf5994c 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/Node.java @@ -542,8 +542,6 @@ public abstract class Node implements OutNode { /** Return block start from a isCFG() */ public Node getBlockStart() { return null; } - /** 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 diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java index f0140ce6..6cd9efb0 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter16/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/chapter16/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 73c1fa15..cd57b85c 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -29,7 +29,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() { diff --git a/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 8cfbe509..ee6e1f1a 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -32,6 +32,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 ) @@ -53,20 +56,17 @@ 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).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 } @@ -76,8 +76,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++ ) @@ -85,7 +88,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); @@ -115,22 +118,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; @@ -141,7 +148,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 @@ -164,8 +171,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,null); // Can be more than one matching input. assert found!=null; return found; } @@ -174,31 +180,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 NewNode 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 LoadNode ld: break; // Loads do not cause anti-deps on other loads case ReturnNode ret: break; // Load must already be ahead of Return @@ -211,11 +219,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/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 8e063205..e85fc6ae 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -62,9 +62,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/chapter17/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/CastNode.java index 462d6cba..38d6a126 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter17/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 StringBuilder _print1(StringBuilder sb, BitSet visited) { diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java index 09180899..08033df0 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java @@ -544,8 +544,6 @@ public abstract class Node implements OutNode { /** 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 diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java index cb266ca3..4962f4f4 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter17/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/chapter17/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 73c1fa15..cd57b85c 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -29,7 +29,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() { 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() { diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java index e4a9e409..0ea32a20 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -9,6 +9,52 @@ import static org.junit.Assert.fail; import org.junit.Ignore; public class Chapter18Test { + @Test public void testFunctionLocalConstantChains() { + String src = "val f = { int x -> x ? f(x-1)*305420988+x/305420988 : 1; }; "+ + "val g = { int x -> x ? g(x-1)/305420988+x*305420988 : 1; }; "+ + "return f(arg)+g(arg);"; + CodeGen code = new CodeGen(src); + code.parse().opto().typeCheck(); + Node con = code._stop.walk(n -> n instanceof ConstantNode && + n._type==TypeInteger.constant(305420988) ? n : null); + assertNotNull(con); + Node[] uses = con._outputs.asAry(); + // Preserve a stacked Cast/Constant chain through scheduling. + Node cast = new CastNode(TypeInteger.BOT,code._start,con); + cast = new CastNode(TypeInteger.BOT,code._start,cast); + for( Node use : uses ) + for( int i=1; i<use.nIns(); i++ ) + if( use.in(i)==con ) use.setDef(i,cast); + code.GCM(); + var owners = new java.util.IdentityHashMap<CFGNode,Boolean>(); + code._stop.walk(n -> { + if( !(n instanceof CastNode) || !(n.in(1) instanceof CastNode) ) return null; + CFGNode fun = n.cfg0(); + while( fun!=null && !(fun instanceof FunNode) ) fun = fun.idom(); + assertTrue("Constant must belong to a function",fun instanceof FunNode); + assertNull("Share one constant chain within each function",owners.put(fun,true)); + // Follow all parts of the constant chain, including shared inputs. + var todo = new java.util.ArrayList<Node>(); + var seen = new java.util.IdentityHashMap<Node,Boolean>(); + todo.add(n); + for( int j=0; j<todo.size(); j++ ) { + Node part = todo.get(j); + if( seen.put(part,true)!=null ) continue; + CFGNode owner = part.cfg0(); + while( owner!=null && !(owner instanceof FunNode) ) owner = owner.idom(); + assertSame("Every constant-building operation is function-local",fun,owner); + for( int i=1; i<part.nIns(); i++ ) { + Node def = part.in(i); + if( def==null || def instanceof CFGNode ) continue; + assertTrue("Copies must register their data edges",def._outputs.find(part)!=-1); + if( def._type.isConstant() ) todo.add(def); + } + } + return null; + }); + assertTrue("Exercise constants shared across functions",owners.size()>=2); + } + @Test public void testReachableMixedReturns() { for( String[] test : new String[][] { {"if(arg) return 7; else return 2.5;", "No common type amongst int and f64"}, diff --git a/chapter19/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter19/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 1ad7d29b..955f20df 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -24,6 +24,7 @@ public abstract class GlobalCodeMotion { code._cfg = rpo; schedEarly(code); + breakUpGlobalConstants(code._start); code._visit.clear(); schedLate (code); } @@ -40,6 +41,56 @@ public abstract class GlobalCodeMotion { rpo.add(cfg); } + // 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() || con instanceof MachNode mach && mach.outregmap()!=null) ) { + 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 @@ -51,6 +102,9 @@ public abstract class GlobalCodeMotion { cfg.loopDepth(); for( Node n : cfg._inputs ) _schedEarly(n,code._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 ) @@ -62,19 +116,16 @@ 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 = CodeGen.CODE._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 @@ -86,8 +137,11 @@ public abstract class GlobalCodeMotion { 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()]; // Breadth-first scheduling - breadth(code._stop,ns,late); + breadth(code._stop,ns,late,anti); // Copy the best placement choice into the control slot for( int i=0; i<late.length; i++ ) @@ -95,7 +149,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); @@ -127,22 +181,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; @@ -153,7 +211,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 @@ -176,7 +234,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; @@ -186,31 +244,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 @@ -224,11 +284,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/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java index d2e70cd7..d57c3e8c 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -85,9 +85,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/chapter19/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/CastNode.java index d8a968c1..6438abb5 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter19/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/chapter19/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter19/src/main/java/com/seaofnodes/simple/node/Node.java index 5d099785..846aaa22 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/Node.java @@ -13,14 +13,14 @@ import static com.seaofnodes.simple.CodeGen.CODE; * 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. @@ -29,7 +29,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 @@ -40,7 +40,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; /** @@ -547,8 +547,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 @@ -603,6 +601,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 = CODE.getUID(); // 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/chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 17748afe..10dfe648 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -46,7 +46,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/chapter19/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/ProjNode.java index ef7b17e4..9e49f67a 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -37,7 +37,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() { diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 05364d49..bf639316 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -9,6 +9,52 @@ import static org.junit.Assert.fail; import org.junit.Ignore; public class Chapter18Test { + @Test public void testFunctionLocalConstantChains() { + String src = "val f = { int x -> x ? f(x-1)*305420988+x/305420988 : 1; }; "+ + "val g = { int x -> x ? g(x-1)/305420988+x*305420988 : 1; }; "+ + "return f(arg)+g(arg);"; + CodeGen code = new CodeGen(src); + code.parse().opto().typeCheck(); + Node con = code._stop.walk(n -> n instanceof ConstantNode && + n._type==TypeInteger.constant(305420988) ? n : null); + assertNotNull(con); + Node[] uses = con._outputs.asAry(); + // Preserve a stacked Cast/Constant chain through scheduling. + Node cast = new CastNode(TypeInteger.BOT,code._start,con); + cast = new CastNode(TypeInteger.BOT,code._start,cast); + for( Node use : uses ) + for( int i=1; i<use.nIns(); i++ ) + if( use.in(i)==con ) use.setDef(i,cast); + code.GCM(); + var owners = new java.util.IdentityHashMap<CFGNode,Boolean>(); + code._stop.walk(n -> { + if( !(n instanceof CastNode) || !(n.in(1) instanceof CastNode) ) return null; + CFGNode fun = n.cfg0(); + while( fun!=null && !(fun instanceof FunNode) ) fun = fun.idom(); + assertTrue("Constant must belong to a function",fun instanceof FunNode); + assertNull("Share one constant chain within each function",owners.put(fun,true)); + // Follow all parts of the constant chain, including shared inputs. + var todo = new java.util.ArrayList<Node>(); + var seen = new java.util.IdentityHashMap<Node,Boolean>(); + todo.add(n); + for( int j=0; j<todo.size(); j++ ) { + Node part = todo.get(j); + if( seen.put(part,true)!=null ) continue; + CFGNode owner = part.cfg0(); + while( owner!=null && !(owner instanceof FunNode) ) owner = owner.idom(); + assertSame("Every constant-building operation is function-local",fun,owner); + for( int i=1; i<part.nIns(); i++ ) { + Node def = part.in(i); + if( def==null || def instanceof CFGNode ) continue; + assertTrue("Copies must register their data edges",def._outputs.find(part)!=-1); + if( def._type.isConstant() ) todo.add(def); + } + } + return null; + }); + assertTrue("Exercise constants shared across functions",owners.size()>=2); + } + @Test public void testReachableMixedReturns() { for( String[] test : new String[][] { {"if(arg) return 7; else return 2.5;", "No common type amongst int and f64"}, diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 02f40974..4ebd86c0 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -24,7 +24,7 @@ public abstract class GlobalCodeMotion { schedEarly(code); // Break up shared global constants by functions - breakUpGlobalConstants(code); + breakUpGlobalConstants(code._start); code._visit.clear(); schedLate (code); @@ -44,42 +44,56 @@ public abstract class GlobalCodeMotion { rpo.add(cfg); } - // Break up shared global constants by functions - private static void breakUpGlobalConstants( CodeGen code ) { - // For all global constants - for( int i=0; i< code._start.nOuts(); i++ ) { - Node con = code._start.out(i); - if( con instanceof MachNode mach && mach.isClone() ) { - // While constant has users in different functions - while( true ) { - // Find a function user, and another function - FunNode fun = null; - boolean done=true; - for( Node use : con.outs() ) { - FunNode fun2 = use.cfg0().fun(); - if( fun==null || fun==fun2 ) fun=fun2; - else { done=false; break; } - } - // Single function user, so this constant is not shared - if( done ) { i--; con.setDef(0,fun); break; } - // Move function users to a private constant - Node con2 = mach.copy(); // Private constant clone - con2._inputs.set(0,null); // Preserve edge invariants from clone - con2.setDef(0,fun); - // Move function users to this private constant - for( int j=0; j<con._outputs._len; j++ ) { - Node use = con.out(j); - FunNode fun2 = use.cfg0().fun(); - if( fun2==fun ) { - use.setDef(use._inputs.find(con),con2); - j--; - } - } - } + // 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() || con instanceof MachNode mach && mach.outregmap()!=null) ) { + 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; + FunNode fun = useFun(use); + if( fun==null ) continue; // Global metadata has no function owner. + var local = copies.computeIfAbsent(fun,f -> new IdentityHashMap<>()); + Node copy = cloneGlobal(con,fun,globals,local); + for( int i=0; i<use.nIns(); i++ ) + if( use.in(i)==con ) + use.setDef(i,copy); + } + 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) { + if( use instanceof ReturnNode ret ) return ret.fun(); + if( use instanceof ParmNode parm ) return parm.fun(); + CFGNode cfg = 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 @@ -91,6 +105,9 @@ public abstract class GlobalCodeMotion { cfg.loopDepth(); for( Node n : cfg._inputs ) _schedEarly(n,code ); + // 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 ) @@ -102,19 +119,16 @@ public abstract class GlobalCodeMotion { if( n==null || code._visit.get(n._nid) ) return; // Been there, done that assert !(n instanceof CFGNode); code._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,code); - // 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 = code._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 @@ -126,8 +140,11 @@ public abstract class GlobalCodeMotion { 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()]; // Breadth-first scheduling - breadth(code._stop,ns,late); + breadth(code._stop,ns,late,anti); // Copy the best placement choice into the control slot for( int i=0; i<late.length; i++ ) @@ -135,7 +152,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); @@ -167,22 +184,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; @@ -193,7 +214,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 @@ -211,12 +232,13 @@ public abstract class GlobalCodeMotion { // Block of use. Normally from late[] schedule, except for Phis, which go // to the matching Region input. private static CFGNode use_block(Node n, Node use, CFGNode[] late) { + if( use instanceof ParmNode ) return late[use._nid]; if( !(use instanceof PhiNode phi) ) return late[use._nid]; 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; @@ -226,31 +248,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 @@ -264,11 +288,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/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 8638d581..c12fc377 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -97,9 +97,6 @@ public abstract class CFGNode extends Node { return lhs; } - // Anti-dependence field support - public int _anti; // Per-CFG field to help find anti-deps - // Find nearest enclosing FunNode public FunNode fun() { CFGNode cfg = this; diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/CastNode.java index 5a92802c..f3ee1aa2 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -27,7 +27,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/chapter20/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter20/src/main/java/com/seaofnodes/simple/node/Node.java index e8043854..55ffe378 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/Node.java @@ -16,14 +16,14 @@ import static com.seaofnodes.simple.codegen.CodeGen.CODE; * 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. @@ -32,7 +32,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 @@ -43,7 +43,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; /** @@ -620,8 +620,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 @@ -676,6 +674,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 = CODE.getUID(); // 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/chapter20/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 16f38d45..34d7afc7 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -45,7 +45,6 @@ public class PhiNode extends Node { public CFGNode region() { return (CFGNode)in(0); } @Override public boolean isMem() { return _declaredType instanceof TypeMem; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 3d9db4ed..83044156 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -36,7 +36,6 @@ public class ProjNode extends Node { } @Override public boolean isMem() { return _type instanceof TypeMem; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 8d612ae3..50485526 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -10,6 +10,52 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testFunctionLocalConstantChains() { + String src = "val f = { int x -> x ? f(x-1)*305420988+x/305420988 : 1; }; "+ + "val g = { int x -> x ? g(x-1)/305420988+x*305420988 : 1; }; "+ + "return f(arg)+g(arg);"; + CodeGen code = new CodeGen(src); + code.parse().opto().typeCheck(); + Node con = code._stop.walk(n -> n instanceof ConstantNode && + n._type==TypeInteger.constant(305420988) ? n : null); + assertNotNull(con); + Node[] uses = con._outputs.asAry(); + // Preserve a stacked Cast/Constant chain through scheduling. + Node cast = new CastNode(TypeInteger.BOT,code._start,con); + cast = new CastNode(TypeInteger.BOT,code._start,cast); + for( Node use : uses ) + for( int i=1; i<use.nIns(); i++ ) + if( use.in(i)==con ) use.setDef(i,cast); + code.GCM(); + var owners = new java.util.IdentityHashMap<CFGNode,Boolean>(); + code._stop.walk(n -> { + if( !(n instanceof CastNode) || !(n.in(1) instanceof CastNode) ) return null; + CFGNode fun = n.cfg0(); + while( fun!=null && !(fun instanceof FunNode) ) fun = fun.idom(); + assertTrue("Constant must belong to a function",fun instanceof FunNode); + assertNull("Share one constant chain within each function",owners.put(fun,true)); + // Follow all parts of the constant chain, including shared inputs. + var todo = new java.util.ArrayList<Node>(); + var seen = new java.util.IdentityHashMap<Node,Boolean>(); + todo.add(n); + for( int j=0; j<todo.size(); j++ ) { + Node part = todo.get(j); + if( seen.put(part,true)!=null ) continue; + CFGNode owner = part.cfg0(); + while( owner!=null && !(owner instanceof FunNode) ) owner = owner.idom(); + assertSame("Every constant-building operation is function-local",fun,owner); + for( int i=1; i<part.nIns(); i++ ) { + Node def = part.in(i); + if( def==null || def instanceof CFGNode ) continue; + assertTrue("Copies must register their data edges",def._outputs.find(part)!=-1); + if( def._type.isConstant() ) todo.add(def); + } + } + return null; + }); + assertTrue("Exercise constants shared across functions",owners.size()>=2); + } + @Test public void testReachableMixedReturns() { for( String[] test : new String[][] { {"if(arg) return 7; else return 2.5;", "No common type amongst int and f64"}, diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index 2021c795..c7f8f4bc 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -303,7 +303,7 @@ public class Encoding { private static boolean forwardsEmptyScan( CFGNode c, int bld ) { if( c.nOuts()!=1 || c.loopDepth()!=bld ) return false; return c.uctrl() instanceof RegionNode cfg && - (cfg instanceof LoopNode || forwardsEmptyScan(cfg,bld)); + ((cfg instanceof LoopNode && cfg._ltree==c._ltree) || forwardsEmptyScan(cfg,bld)); } // Is the CFG from "next" to the end empty? This means jumping to "next" diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index da045925..5c119251 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -44,47 +44,56 @@ public abstract class GlobalCodeMotion { rpo.add(cfg); } - // Break up shared global constants by functions - private static void breakUpGlobalConstants( Node start ) { - // For all global constants - for( int i=0; i< start.nOuts(); i++ ) { - Node con = start.out(i); - if( con instanceof MachNode mach && mach.isClone() ) { - breakUpGlobalConstants(con); - // While constant has users in different functions - while( true ) { - // Find a function user, and another function - FunNode fun = null; - boolean done=true; - for( Node use : con.outs() ) { - FunNode fun2 = use instanceof ReturnNode ret ? ret.fun() : use.cfg0().fun(); - if( fun==null || fun==fun2 ) fun=fun2; - else { done=false; break; } - } - // Single function user, so this constant is not shared - if( done ) { - if( con.in(0)==start ) i--; - con.setDef(0,fun); - break; - } - // Move function users to a private constant - Node con2 = mach.copy(); // Private constant clone - con2._inputs.set(0,null); // Preserve edge invariants from clone - con2.setDef(0,fun); - // Move function users to this private constant - for( int j=0; j<con._outputs._len; j++ ) { - Node use = con.out(j); - FunNode fun2 = use.cfg0().fun(); - if( fun2==fun ) { - use.setDef(use._inputs.find(con),con2); - j--; - } - } - } + // 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() || con instanceof MachNode mach && mach.outregmap()!=null) ) { + 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; + FunNode fun = useFun(use); + if( fun==null ) continue; // Global metadata has no function owner. + var local = copies.computeIfAbsent(fun,f -> new IdentityHashMap<>()); + Node copy = cloneGlobal(con,fun,globals,local); + for( int i=0; i<use.nIns(); i++ ) + if( use.in(i)==con ) + use.setDef(i,copy); } + 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) { + if( use instanceof ReturnNode ret ) return ret.fun(); + if( use instanceof ParmNode parm ) return parm.fun(); + CFGNode cfg = 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 @@ -96,6 +105,9 @@ public abstract class GlobalCodeMotion { cfg.loopDepth(); for( Node n : cfg._inputs ) _schedEarly(n,code ); + // 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 ) @@ -107,19 +119,16 @@ public abstract class GlobalCodeMotion { if( n==null || code._visit.get(n._nid) ) return; // Been there, done that assert !(n instanceof CFGNode); code._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,code); - // 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 = code._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 @@ -131,8 +140,11 @@ public abstract class GlobalCodeMotion { 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()]; // Breadth-first scheduling - breadth(code._stop,ns,late); + breadth(code._stop,ns,late,anti); // Copy the best placement choice into the control slot for( int i=0; i<late.length; i++ ) @@ -140,7 +152,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); @@ -174,22 +186,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 out : def._outputs ) - if( out instanceof MemOpNode ld && ld._isLoad && 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 MemOpNode ld && ld._isLoad && 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; @@ -200,34 +216,8 @@ public abstract class GlobalCodeMotion { // Loads may need anti-dependencies, raising their LCA if( n instanceof MemOpNode load && load._isLoad ) - lca = find_anti_dep(lca,load,early,late); - - - // Nodes setting a single register and getting killed will stay close - // to the uses, since they will be forced to spill anyway. The kill - // check is very weak, and some may be hoisted only to spill in the RA. - if( n instanceof MachNode mach ) { - RegMask out = mach.outregmap(); - if( out!=null && out.size1() ) { - int reg = mach.outregmap().firstReg(); - // Look for kills - outer: - for( CFGNode lca2=lca; lca2 != early; lca2 = lca2.idom() ) { - if( lca2 instanceof MachNode mach2 ) { - for( int i=1; i<lca2.nIns(); i++ ) { - RegMask mask = mach2.regmap(i); - if( mask!=null && mask.test(reg) ) { - early = lca2 instanceof IfNode ? lca2.idom() : lca2; - break outer; - } - } - RegMask kill = mach2.killmap(); - if( kill != null ) - throw Utils.TODO(); - } - } - } - } + 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 @@ -245,12 +235,13 @@ public abstract class GlobalCodeMotion { // Block of use. Normally from late[] schedule, except for Phis, which go // to the matching Region input. private static CFGNode use_block(Node n, Node use, CFGNode[] late) { + if( use instanceof ParmNode ) return late[use._nid]; if( !(use instanceof PhiNode phi) ) return late[use._nid]; 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; @@ -265,30 +256,30 @@ public abstract class GlobalCodeMotion { best instanceof IfNode; } - private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late) { + private static CFGNode find_anti_dep(CFGNode lca, MemOpNode 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 MemOpNode st: if( !st._isLoad ) { assert late[mem._nid] != null; - lca = anti_dep( load, late[mem._nid], mem.cfg0(), lca, st ); + lca = anti_dep(load,late[mem._nid],lca,st,anti); } break; // Loads do not cause anti-deps on other loads case CallNode call: assert late[call._nid]!=null; - lca = anti_dep(load,late[call._nid],call.cfg0(),lca,call); + lca = anti_dep(load,late[call._nid],lca,call,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),lca,null,anti); break; case NewNode st: break; case ReturnNode ret: break; // Load must already be ahead of Return @@ -301,13 +292,12 @@ public abstract class GlobalCodeMotion { } // - private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { - // Store and Load overlap, need anti-dependence - if( stblk._anti==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 - return lca; // Cap this stores' anti-dep to here + private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode lca, Node st, int[] anti ) { + // Stores are already placed. Constrain the load at that block only. + if( anti[stblk._nid]==load._nid ) { + lca = stblk.domLCA(lca,null); + if( lca==stblk && st!=null && st._inputs.find(load) == -1 ) + st.addDef(load); // Same-block load must precede the store. } return lca; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 6f533ae0..fdf09d98 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -103,9 +103,6 @@ public abstract class CFGNode extends Node { return lhs; } - // Anti-dependence field support - public int _anti; // Per-CFG field to help find anti-deps - // Find nearest enclosing FunNode public FunNode fun() { CFGNode cfg = this; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CastNode.java index 0947bcf0..42e461e5 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -27,7 +27,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/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java index 4ca95cae..a83ca6c1 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java @@ -619,8 +619,6 @@ public abstract class Node implements Cloneable { /** 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 @@ -675,7 +673,11 @@ public abstract class Node implements Cloneable { // Does not need to be implemented in isCFG() nodes. Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } - public Node copy() { + public Node copy() { return copyEmpty(); } + + // 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); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 0579ecd0..24a766d6 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -45,7 +45,6 @@ public class PhiNode extends Node { public CFGNode region() { return (CFGNode)in(0); } @Override public boolean isMem() { return _declaredType instanceof TypeMem; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ProjNode.java index a0394e5b..48f92525 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -36,7 +36,6 @@ public class ProjNode extends Node { } @Override public boolean isMem() { return _type instanceof TypeMem; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { diff --git a/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index 2733620e..1e1a1dc3 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -16,7 +16,7 @@ public class BrainFuckTest { String brain_fuck = "Hello World!\n"; TestC.run("brain_fuck", brain_fuck, 40); - EvalRisc5 R5 = TestRisc5.build("brain_fuck", 0, 44, false); + EvalRisc5 R5 = TestRisc5.build("brain_fuck", 0, 28, false); int trap = R5.step(100000); assertEquals(0,trap); int ptr = (int)R5.regs[riscv.A0]; diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java index d5d5c2ef..b3d81f0f 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -11,6 +11,44 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testFunctionLocalConstantChains() { + String src = "val f = { int x -> x ? f(x-1)*305420988+x/305420988 : 1; }; "+ + "val g = { int x -> x ? g(x-1)/305420988+x*305420988 : 1; }; "+ + "return f(arg)+g(arg);"; + CodeGen code = new CodeGen(src); + code.driver(CodeGen.Phase.Schedule,"riscv","SystemV"); + var owners = new java.util.IdentityHashMap<CFGNode,Boolean>(); + code._stop.walk(n -> { + if( !(n instanceof com.seaofnodes.simple.node.cpus.riscv.AddIRISC add) || + !(add.in(1) instanceof com.seaofnodes.simple.node.cpus.riscv.LUI upper) || + ((TypeInteger)upper._con).value()+((add._imm12<<20)>>20)!=305420988 ) + return null; + CFGNode fun = n.cfg0(); + while( fun!=null && !(fun instanceof FunNode) ) fun = fun.idom(); + assertTrue("Constant must belong to a function",fun instanceof FunNode); + assertNull("Share one constant chain within each function",owners.put(fun,true)); + // Follow all parts of a machine constant, including shared inputs. + var todo = new java.util.ArrayList<Node>(); + var seen = new java.util.IdentityHashMap<Node,Boolean>(); + todo.add(n); + for( int j=0; j<todo.size(); j++ ) { + Node part = todo.get(j); + if( seen.put(part,true)!=null ) continue; + CFGNode owner = part.cfg0(); + while( owner!=null && !(owner instanceof FunNode) ) owner = owner.idom(); + assertSame("Every constant-building operation is function-local",fun,owner); + for( int i=1; i<part.nIns(); i++ ) { + Node def = part.in(i); + if( def==null || def instanceof CFGNode ) continue; + assertTrue("Copies must register their data edges",def._outputs.find(part)!=-1); + if( def._type.isConstant() ) todo.add(def); + } + } + return null; + }); + assertTrue("Exercise constants shared across functions",owners.size()>=2); + } + @Test public void testReachableMixedReturns() { for( String[] test : new String[][] { {"if(arg) return 7; else return 2.5;", "No common type amongst int and f64"}, diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 21f096b9..d6bf1f4f 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -107,8 +107,8 @@ return sqrt(arg) + sqrt(arg+2); public void testString() throws IOException { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); testCPU(src,"x86_64_v2", "SystemV", 9,null); - testCPU(src,"riscv" , "SystemV", 5,null); - testCPU(src,"arm" , "SystemV", 6,null); + testCPU(src,"riscv" , "SystemV", 3,null); + testCPU(src,"arm" , "SystemV", 3,null); } @Test diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java index a5d86fa5..fd91770a 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -93,8 +93,8 @@ public class Chapter21Test { public void testString() throws IOException { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); testCPU(src,"x86_64_v2", "SystemV", 9,null); - testCPU(src,"riscv" , "SystemV", 5,null); - testCPU(src,"arm" , "SystemV", 6,null); + testCPU(src,"riscv" , "SystemV", 3,null); + testCPU(src,"arm" , "SystemV", 3,null); } @Test public void testStringExport() throws IOException { diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 1542c04d..68b310bf 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -43,47 +43,56 @@ public abstract class GlobalCodeMotion { rpo.add(cfg); } - // Break up shared global constants by functions - private static void breakUpGlobalConstants( Node start ) { - // For all global constants - for( int i=0; i< start.nOuts(); i++ ) { - Node con = start.out(i); - if( con instanceof MachNode mach && mach.isClone() ) { - breakUpGlobalConstants(con); - // While constant has users in different functions - while( true ) { - // Find a function user, and another function - FunNode fun = null; - boolean done=true; - for( Node use : con.outs() ) { - FunNode fun2 = use instanceof ReturnNode ret ? ret.fun() : use.cfg0().fun(); - if( fun==null || fun==fun2 ) fun=fun2; - else { done=false; break; } - } - // Single function user, so this constant is not shared - if( done ) { - if( con.in(0)==start ) i--; - con.setDef(0,fun); - break; - } - // Move function users to a private constant - Node con2 = mach.copy(); // Private constant clone - con2._inputs.set(0,null); // Preserve edge invariants from clone - con2.setDef(0,fun); - // Move function users to this private constant - for( int j=0; j<con._outputs._len; j++ ) { - Node use = con.out(j); - FunNode fun2 = use.cfg0().fun(); - if( fun2==fun ) { - use.setDef(use._inputs.find(con),con2); - j--; - } - } - } + // 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() || con instanceof MachNode mach && mach.outregmap()!=null) ) { + 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; + FunNode fun = useFun(use); + if( fun==null ) continue; // Global metadata has no function owner. + var local = copies.computeIfAbsent(fun,f -> new IdentityHashMap<>()); + Node copy = cloneGlobal(con,fun,globals,local); + for( int i=0; i<use.nIns(); i++ ) + if( use.in(i)==con ) + use.setDef(i,copy); } + 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) { + if( use instanceof ReturnNode ret ) return ret.fun(); + if( use instanceof ParmNode parm ) return parm.fun(); + CFGNode cfg = 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 @@ -95,6 +104,9 @@ public abstract class GlobalCodeMotion { cfg.loopDepth(); for( Node n : cfg._inputs ) _schedEarly(n,code ); + // 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 ) @@ -106,19 +118,16 @@ public abstract class GlobalCodeMotion { if( n==null || code._visit.get(n._nid) ) return; // Been there, done that assert !(n instanceof CFGNode); code._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,code); - // 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 = code._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 @@ -130,8 +139,11 @@ public abstract class GlobalCodeMotion { 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()]; // Breadth-first scheduling - breadth(code._stop,ns,late); + breadth(code._stop,ns,late,anti); // Copy the best placement choice into the control slot for( int i=0; i<late.length; i++ ) @@ -139,7 +151,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); @@ -173,30 +185,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 + // 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 && late[def._nid]==null ) - work.push(def); - // if the def has a load use, maybe the load can fire - if( def!=null ) - for( Node out : def._outputs ) - if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null ) - work.push(ld); + if( def==null ) continue; + if( late[def._nid]==null ) work.push(def); + for( Node out : def._outputs ) + if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null ) + work.push(ld); } - - if( n instanceof LoopNode loop ) { - for( Node phi : loop._outputs ) { + 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; @@ -207,34 +215,8 @@ public abstract class GlobalCodeMotion { // Loads may need anti-dependencies, raising their LCA if( n instanceof MemOpNode load && load._isLoad ) - lca = find_anti_dep(lca,load,early,late); - - - // Nodes setting a single register and getting killed will stay close - // to the uses, since they will be forced to spill anyway. The kill - // check is very weak, and some may be hoisted only to spill in the RA. - if( n instanceof MachNode mach ) { - RegMask out = mach.outregmap(); - if( out!=null && out.size1() ) { - int reg = mach.outregmap().firstReg(); - // Look for kills - outer: - for( CFGNode lca2=lca; lca2 != early; lca2 = lca2.idom() ) { - if( lca2 instanceof MachNode mach2 ) { - for( int i=1; i<lca2.nIns(); i++ ) { - RegMask mask = mach2.regmap(i); - if( mask!=null && mask.test(reg) ) { - early = lca2 instanceof IfNode ? lca2.idom() : lca2; - break outer; - } - } - RegMask kill = mach2.killmap(); - if( kill != null ) - throw Utils.TODO(); - } - } - } - } + 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 @@ -252,12 +234,13 @@ public abstract class GlobalCodeMotion { // Block of use. Normally from late[] schedule, except for Phis, which go // to the matching Region input. private static CFGNode use_block(Node n, Node use, CFGNode[] late) { + if( use instanceof ParmNode ) return late[use._nid]; if( !(use instanceof PhiNode phi) ) return late[use._nid]; 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; @@ -272,30 +255,30 @@ public abstract class GlobalCodeMotion { best instanceof IfNode; } - private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late) { + private static CFGNode find_anti_dep(CFGNode lca, MemOpNode 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 MemOpNode st: if( !st._isLoad && load._alias == st._alias ) { assert late[mem._nid] != null; - lca = anti_dep( load, late[mem._nid], mem.cfg0(), lca, st ); + lca = anti_dep(load,late[mem._nid],lca,st,anti); } break; // Loads do not cause anti-deps on other loads case CallNode call: assert late[call._nid]!=null; - lca = anti_dep(load,late[call._nid],call.cfg0(),lca,call); + lca = anti_dep(load,late[call._nid],lca,call,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),lca,null,anti); break; case NewNode st: break; case ReturnNode ret: break; // Load must already be ahead of Return @@ -308,13 +291,12 @@ public abstract class GlobalCodeMotion { } // - private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { - // Store and Load overlap, need anti-dependence - if( stblk._anti==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 - return lca; // Cap this stores' anti-dep to here + private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode lca, Node st, int[] anti ) { + // Stores are already placed. Constrain the load at that block only. + if( anti[stblk._nid]==load._nid ) { + lca = stblk.domLCA(lca,null); + if( lca==stblk && st!=null && st._inputs.find(load) == -1 ) + st.addDef(load); // Same-block load must precede the store. } return lca; } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java index cad3b5e2..efdb4440 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -103,9 +103,6 @@ public abstract class CFGNode extends Node { return lhs; } - // Anti-dependence field support - public int _anti; // Per-CFG field to help find anti-deps - // Find nearest enclosing FunNode public FunNode fun() { CFGNode cfg = this; diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/CastNode.java index 8d8f0257..beec825c 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -29,7 +29,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/chapter22/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter22/src/main/java/com/seaofnodes/simple/node/Node.java index 064f295f..eee5ad7e 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/Node.java @@ -623,8 +623,6 @@ public abstract class Node implements Cloneable { /** 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 @@ -679,7 +677,11 @@ public abstract class Node implements Cloneable { // Does not need to be implemented in isCFG() nodes. Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } - public Node copy() { + public Node copy() { return copyEmpty(); } + + // 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); } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 971b52ae..f0845066 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -45,7 +45,6 @@ public class PhiNode extends Node { public CFGNode region() { return (CFGNode)in(0); } @Override public boolean isMem() { return _declaredType instanceof TypeMem; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/ProjNode.java index a0394e5b..48f92525 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -36,7 +36,6 @@ public class ProjNode extends Node { } @Override public boolean isMem() { return _type instanceof TypeMem; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java index c8a613a1..3dce3760 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -11,6 +11,44 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testFunctionLocalConstantChains() { + String src = "val f = { int x -> x ? f(x-1)*305420988+x/305420988 : 1; }; "+ + "val g = { int x -> x ? g(x-1)/305420988+x*305420988 : 1; }; "+ + "return f(arg)+g(arg);"; + CodeGen code = new CodeGen(src); + code.driver(CodeGen.Phase.Schedule,"riscv","SystemV"); + var owners = new java.util.IdentityHashMap<CFGNode,Boolean>(); + code._stop.walk(n -> { + if( !(n instanceof com.seaofnodes.simple.node.cpus.riscv.AddIRISC add) || + !(add.in(1) instanceof com.seaofnodes.simple.node.cpus.riscv.LUI upper) || + ((TypeInteger)upper._con).value()+((add._imm12<<20)>>20)!=305420988 ) + return null; + CFGNode fun = n.cfg0(); + while( fun!=null && !(fun instanceof FunNode) ) fun = fun.idom(); + assertTrue("Constant must belong to a function",fun instanceof FunNode); + assertNull("Share one constant chain within each function",owners.put(fun,true)); + // Follow all parts of a machine constant, including shared inputs. + var todo = new java.util.ArrayList<Node>(); + var seen = new java.util.IdentityHashMap<Node,Boolean>(); + todo.add(n); + for( int j=0; j<todo.size(); j++ ) { + Node part = todo.get(j); + if( seen.put(part,true)!=null ) continue; + CFGNode owner = part.cfg0(); + while( owner!=null && !(owner instanceof FunNode) ) owner = owner.idom(); + assertSame("Every constant-building operation is function-local",fun,owner); + for( int i=1; i<part.nIns(); i++ ) { + Node def = part.in(i); + if( def==null || def instanceof CFGNode ) continue; + assertTrue("Copies must register their data edges",def._outputs.find(part)!=-1); + if( def._type.isConstant() ) todo.add(def); + } + } + return null; + }); + assertTrue("Exercise constants shared across functions",owners.size()>=2); + } + @Test public void testReachableMixedReturns() { for( String[] test : new String[][] { {"if(arg) return 7; else return 2.5;", "No common type amongst int and f64"}, diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 144a9f8e..b8a8d2b3 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -43,47 +43,56 @@ public abstract class GlobalCodeMotion { rpo.add(cfg); } - // Break up shared global constants by functions - private static void breakUpGlobalConstants( Node start ) { - // For all global constants - for( int i=0; i< start.nOuts(); i++ ) { - Node con = start.out(i); - if( con instanceof MachNode mach && mach.isClone() ) { - breakUpGlobalConstants(con); - // While constant has users in different functions - while( true ) { - // Find a function user, and another function - FunNode fun = null; - boolean done=true; - for( Node use : con.outs() ) { - FunNode fun2 = use instanceof ReturnNode ret ? ret.fun() : use.cfg0().fun(); - if( fun==null || fun==fun2 ) fun=fun2; - else { done=false; break; } - } - // Single function user, so this constant is not shared - if( done ) { - if( con.in(0)==start ) i--; - con.setDef(0,fun); - break; - } - // Move function users to a private constant - Node con2 = mach.copy(); // Private constant clone - con2._inputs.set(0,null); // Preserve edge invariants from clone - con2.setDef(0,fun); - // Move function users to this private constant - for( int j=0; j<con._outputs._len; j++ ) { - Node use = con.out(j); - FunNode fun2 = use.cfg0().fun(); - if( fun2==fun ) { - use.setDef(use._inputs.find(con),con2); - j--; - } - } - } + // 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() || con instanceof MachNode mach && mach.outregmap()!=null) ) { + 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; + FunNode fun = useFun(use); + if( fun==null ) continue; // Global metadata has no function owner. + var local = copies.computeIfAbsent(fun,f -> new IdentityHashMap<>()); + Node copy = cloneGlobal(con,fun,globals,local); + for( int i=0; i<use.nIns(); i++ ) + if( use.in(i)==con ) + use.setDef(i,copy); } + 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) { + if( use instanceof ReturnNode ret ) return ret.fun(); + if( use instanceof ParmNode parm ) return parm.fun(); + CFGNode cfg = 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 @@ -95,6 +104,9 @@ public abstract class GlobalCodeMotion { cfg.loopDepth(); for( Node n : cfg._inputs ) _schedEarly(n,code ); + // 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 ) @@ -106,19 +118,16 @@ public abstract class GlobalCodeMotion { if( n==null || code._visit.get(n._nid) ) return; // Been there, done that assert !(n instanceof CFGNode); code._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,code); - // 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 = code._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 @@ -130,8 +139,11 @@ public abstract class GlobalCodeMotion { 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()]; // Breadth-first scheduling - breadth(code._stop,ns,late); + breadth(code._stop,ns,late,anti); // Copy the best placement choice into the control slot for( int i=0; i<late.length; i++ ) @@ -139,7 +151,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); @@ -173,30 +185,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 + // 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 && late[def._nid]==null ) - work.push(def); - // if the def has a load use, maybe the load can fire - if( def!=null ) - for( Node out : def._outputs ) - if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null ) - work.push(ld); + if( def==null ) continue; + if( late[def._nid]==null ) work.push(def); + for( Node out : def._outputs ) + if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null ) + work.push(ld); } - - if( n instanceof LoopNode loop ) { - for( Node phi : loop._outputs ) { + 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; @@ -207,34 +215,8 @@ public abstract class GlobalCodeMotion { // Loads may need anti-dependencies, raising their LCA if( n instanceof MemOpNode load && load._isLoad ) - lca = find_anti_dep(lca,load,early,late); - - - // Nodes setting a single register and getting killed will stay close - // to the uses, since they will be forced to spill anyway. The kill - // check is very weak, and some may be hoisted only to spill in the RA. - if( n instanceof MachNode mach ) { - RegMask out = mach.outregmap(); - if( out!=null && out.size1() ) { - int reg = mach.outregmap().firstReg(); - // Look for kills - outer: - for( CFGNode lca2=lca; lca2 != early; lca2 = lca2.idom() ) { - if( lca2 instanceof MachNode mach2 ) { - for( int i=1; i<lca2.nIns(); i++ ) { - RegMask mask = mach2.regmap(i); - if( mask!=null && mask.test(reg) ) { - early = lca2 instanceof IfNode ? lca2.idom() : lca2; - break outer; - } - } - RegMask kill = mach2.killmap(); - if( kill != null ) - throw Utils.TODO(); - } - } - } - } + 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 @@ -252,12 +234,13 @@ public abstract class GlobalCodeMotion { // Block of use. Normally from late[] schedule, except for Phis, which go // to the matching Region input. private static CFGNode use_block(Node n, Node use, CFGNode[] late) { + if( use instanceof ParmNode ) return late[use._nid]; if( !(use instanceof PhiNode phi) ) return late[use._nid]; 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; @@ -272,30 +255,30 @@ public abstract class GlobalCodeMotion { best instanceof IfNode; } - private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late) { + private static CFGNode find_anti_dep(CFGNode lca, MemOpNode 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 MemOpNode st: if( !st._isLoad && load._alias == st._alias ) { assert late[mem._nid] != null; - lca = anti_dep( load, late[mem._nid], mem.cfg0(), lca, st ); + lca = anti_dep(load,late[mem._nid],lca,st,anti); } break; // Loads do not cause anti-deps on other loads case CallNode call: assert late[call._nid]!=null; - lca = anti_dep(load,late[call._nid],call.cfg0(),lca,call); + lca = anti_dep(load,late[call._nid],lca,call,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),lca,null,anti); break; case NewNode st: break; case ReturnNode ret: break; // Load must already be ahead of Return @@ -308,13 +291,12 @@ public abstract class GlobalCodeMotion { } // - private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { - // Store and Load overlap, need anti-dependence - if( stblk._anti==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 - return lca; // Cap this stores' anti-dep to here + private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode lca, Node st, int[] anti ) { + // Stores are already placed. Constrain the load at that block only. + if( anti[stblk._nid]==load._nid ) { + lca = stblk.domLCA(lca,null); + if( lca==stblk && st!=null && st._inputs.find(load) == -1 ) + st.addDef(load); // Same-block load must precede the store. } return lca; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java index d9452b6d..420c8117 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -103,9 +103,6 @@ public abstract class CFGNode extends Node { return lhs; } - // Anti-dependence field support - public int _anti; // Per-CFG field to help find anti-deps - // Find nearest enclosing FunNode public FunNode fun() { CFGNode cfg = this; diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/CastNode.java index 6dc8e9fe..f3436f56 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -28,7 +28,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/chapter23/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter23/src/main/java/com/seaofnodes/simple/node/Node.java index 8981ab0d..715f4e14 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/Node.java @@ -626,8 +626,6 @@ public abstract class Node implements Cloneable { /** 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 @@ -682,7 +680,11 @@ public abstract class Node implements Cloneable { // Does not need to be implemented in isCFG() nodes. Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } - public Node copy() { + public Node copy() { return copyEmpty(); } + + // 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); } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/PhiNode.java index fcbacbc9..c86b3345 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -54,7 +54,6 @@ public class PhiNode extends Node { public CFGNode region() { return (CFGNode)in(0); } @Override public boolean isMem() { return _minType instanceof TypeMem; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/ProjNode.java index a0394e5b..48f92525 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -36,7 +36,6 @@ public class ProjNode extends Node { } @Override public boolean isMem() { return _type instanceof TypeMem; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 41b7d139..8e0181b3 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -11,6 +11,44 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testFunctionLocalConstantChains() { + String src = "val f = { int x -> x ? f(x-1)*305420988+x/305420988 : 1; }; "+ + "val g = { int x -> x ? g(x-1)/305420988+x*305420988 : 1; }; "+ + "return f(arg)+g(arg);"; + CodeGen code = new CodeGen(src); + code.driver(CodeGen.Phase.Schedule,"riscv","SystemV"); + var owners = new java.util.IdentityHashMap<CFGNode,Boolean>(); + code._stop.walk(n -> { + if( !(n instanceof com.seaofnodes.simple.node.cpus.riscv.AddIRISC add) || + !(add.in(1) instanceof com.seaofnodes.simple.node.cpus.riscv.LUI upper) || + ((TypeInteger)upper._con).value()+((add._imm12<<20)>>20)!=305420988 ) + return null; + CFGNode fun = n.cfg0(); + while( fun!=null && !(fun instanceof FunNode) ) fun = fun.idom(); + assertTrue("Constant must belong to a function",fun instanceof FunNode); + assertNull("Share one constant chain within each function",owners.put(fun,true)); + // Follow all parts of a machine constant, including shared inputs. + var todo = new java.util.ArrayList<Node>(); + var seen = new java.util.IdentityHashMap<Node,Boolean>(); + todo.add(n); + for( int j=0; j<todo.size(); j++ ) { + Node part = todo.get(j); + if( seen.put(part,true)!=null ) continue; + CFGNode owner = part.cfg0(); + while( owner!=null && !(owner instanceof FunNode) ) owner = owner.idom(); + assertSame("Every constant-building operation is function-local",fun,owner); + for( int i=1; i<part.nIns(); i++ ) { + Node def = part.in(i); + if( def==null || def instanceof CFGNode ) continue; + assertTrue("Copies must register their data edges",def._outputs.find(part)!=-1); + if( def._type.isConstant() ) todo.add(def); + } + } + return null; + }); + assertTrue("Exercise constants shared across functions",owners.size()>=2); + } + @Test public void testReachableMixedReturns() { for( String[] test : new String[][] { {"if(arg) return 7; else return 2.5;", "No common type amongst int and f64"}, diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 144a9f8e..b8a8d2b3 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -43,47 +43,56 @@ public abstract class GlobalCodeMotion { rpo.add(cfg); } - // Break up shared global constants by functions - private static void breakUpGlobalConstants( Node start ) { - // For all global constants - for( int i=0; i< start.nOuts(); i++ ) { - Node con = start.out(i); - if( con instanceof MachNode mach && mach.isClone() ) { - breakUpGlobalConstants(con); - // While constant has users in different functions - while( true ) { - // Find a function user, and another function - FunNode fun = null; - boolean done=true; - for( Node use : con.outs() ) { - FunNode fun2 = use instanceof ReturnNode ret ? ret.fun() : use.cfg0().fun(); - if( fun==null || fun==fun2 ) fun=fun2; - else { done=false; break; } - } - // Single function user, so this constant is not shared - if( done ) { - if( con.in(0)==start ) i--; - con.setDef(0,fun); - break; - } - // Move function users to a private constant - Node con2 = mach.copy(); // Private constant clone - con2._inputs.set(0,null); // Preserve edge invariants from clone - con2.setDef(0,fun); - // Move function users to this private constant - for( int j=0; j<con._outputs._len; j++ ) { - Node use = con.out(j); - FunNode fun2 = use.cfg0().fun(); - if( fun2==fun ) { - use.setDef(use._inputs.find(con),con2); - j--; - } - } - } + // 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() || con instanceof MachNode mach && mach.outregmap()!=null) ) { + 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; + FunNode fun = useFun(use); + if( fun==null ) continue; // Global metadata has no function owner. + var local = copies.computeIfAbsent(fun,f -> new IdentityHashMap<>()); + Node copy = cloneGlobal(con,fun,globals,local); + for( int i=0; i<use.nIns(); i++ ) + if( use.in(i)==con ) + use.setDef(i,copy); } + 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) { + if( use instanceof ReturnNode ret ) return ret.fun(); + if( use instanceof ParmNode parm ) return parm.fun(); + CFGNode cfg = 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 @@ -95,6 +104,9 @@ public abstract class GlobalCodeMotion { cfg.loopDepth(); for( Node n : cfg._inputs ) _schedEarly(n,code ); + // 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 ) @@ -106,19 +118,16 @@ public abstract class GlobalCodeMotion { if( n==null || code._visit.get(n._nid) ) return; // Been there, done that assert !(n instanceof CFGNode); code._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,code); - // 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 = code._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 @@ -130,8 +139,11 @@ public abstract class GlobalCodeMotion { 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()]; // Breadth-first scheduling - breadth(code._stop,ns,late); + breadth(code._stop,ns,late,anti); // Copy the best placement choice into the control slot for( int i=0; i<late.length; i++ ) @@ -139,7 +151,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); @@ -173,30 +185,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 + // 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 && late[def._nid]==null ) - work.push(def); - // if the def has a load use, maybe the load can fire - if( def!=null ) - for( Node out : def._outputs ) - if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null ) - work.push(ld); + if( def==null ) continue; + if( late[def._nid]==null ) work.push(def); + for( Node out : def._outputs ) + if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null ) + work.push(ld); } - - if( n instanceof LoopNode loop ) { - for( Node phi : loop._outputs ) { + 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; @@ -207,34 +215,8 @@ public abstract class GlobalCodeMotion { // Loads may need anti-dependencies, raising their LCA if( n instanceof MemOpNode load && load._isLoad ) - lca = find_anti_dep(lca,load,early,late); - - - // Nodes setting a single register and getting killed will stay close - // to the uses, since they will be forced to spill anyway. The kill - // check is very weak, and some may be hoisted only to spill in the RA. - if( n instanceof MachNode mach ) { - RegMask out = mach.outregmap(); - if( out!=null && out.size1() ) { - int reg = mach.outregmap().firstReg(); - // Look for kills - outer: - for( CFGNode lca2=lca; lca2 != early; lca2 = lca2.idom() ) { - if( lca2 instanceof MachNode mach2 ) { - for( int i=1; i<lca2.nIns(); i++ ) { - RegMask mask = mach2.regmap(i); - if( mask!=null && mask.test(reg) ) { - early = lca2 instanceof IfNode ? lca2.idom() : lca2; - break outer; - } - } - RegMask kill = mach2.killmap(); - if( kill != null ) - throw Utils.TODO(); - } - } - } - } + 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 @@ -252,12 +234,13 @@ public abstract class GlobalCodeMotion { // Block of use. Normally from late[] schedule, except for Phis, which go // to the matching Region input. private static CFGNode use_block(Node n, Node use, CFGNode[] late) { + if( use instanceof ParmNode ) return late[use._nid]; if( !(use instanceof PhiNode phi) ) return late[use._nid]; 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; @@ -272,30 +255,30 @@ public abstract class GlobalCodeMotion { best instanceof IfNode; } - private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late) { + private static CFGNode find_anti_dep(CFGNode lca, MemOpNode 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 MemOpNode st: if( !st._isLoad && load._alias == st._alias ) { assert late[mem._nid] != null; - lca = anti_dep( load, late[mem._nid], mem.cfg0(), lca, st ); + lca = anti_dep(load,late[mem._nid],lca,st,anti); } break; // Loads do not cause anti-deps on other loads case CallNode call: assert late[call._nid]!=null; - lca = anti_dep(load,late[call._nid],call.cfg0(),lca,call); + lca = anti_dep(load,late[call._nid],lca,call,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),lca,null,anti); break; case NewNode st: break; case ReturnNode ret: break; // Load must already be ahead of Return @@ -308,13 +291,12 @@ public abstract class GlobalCodeMotion { } // - private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { - // Store and Load overlap, need anti-dependence - if( stblk._anti==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 - return lca; // Cap this stores' anti-dep to here + private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode lca, Node st, int[] anti ) { + // Stores are already placed. Constrain the load at that block only. + if( anti[stblk._nid]==load._nid ) { + lca = stblk.domLCA(lca,null); + if( lca==stblk && st!=null && st._inputs.find(load) == -1 ) + st.addDef(load); // Same-block load must precede the store. } return lca; } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/CFGNode.java index d9452b6d..420c8117 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -103,9 +103,6 @@ public abstract class CFGNode extends Node { return lhs; } - // Anti-dependence field support - public int _anti; // Per-CFG field to help find anti-deps - // Find nearest enclosing FunNode public FunNode fun() { CFGNode cfg = this; diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/CastNode.java index 6dc8e9fe..f3436f56 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -28,7 +28,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/chapter24/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter24/src/main/java/com/seaofnodes/simple/node/Node.java index 458a3407..f45a1aa8 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/Node.java @@ -627,8 +627,6 @@ public abstract class Node implements Cloneable { /** 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 @@ -683,7 +681,11 @@ public abstract class Node implements Cloneable { // Does not need to be implemented in isCFG() nodes. Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } - public Node copy() { + public Node copy() { return copyEmpty(); } + + // 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); } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java index bdc0d0fa..b2483218 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -56,7 +56,6 @@ public class PhiNode extends Node { public CFGNode region() { return (CFGNode)in(0); } @Override public boolean isMem() { return _minType instanceof TypeMem; } - @Override public boolean isPinned() { return true; } boolean isRPC() { return false; } @Override diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 586527c8..fd67f1b1 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -36,7 +36,6 @@ public class ProjNode extends Node { } @Override public boolean isMem() { return _type instanceof TypeMem; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 5dbbf0f1..e748752e 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -11,6 +11,44 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testFunctionLocalConstantChains() { + String src = "val f = { int x -> x ? f(x-1)*305420988+x/305420988 : 1; }; "+ + "val g = { int x -> x ? g(x-1)/305420988+x*305420988 : 1; }; "+ + "return f(arg)+g(arg);"; + CodeGen code = new CodeGen(src); + code.driver(CodeGen.Phase.Schedule,"riscv","SystemV"); + var owners = new java.util.IdentityHashMap<CFGNode,Boolean>(); + code._stop.walk(n -> { + if( !(n instanceof com.seaofnodes.simple.node.cpus.riscv.AddIRISC add) || + !(add.in(1) instanceof com.seaofnodes.simple.node.cpus.riscv.LUI upper) || + ((TypeInteger)upper._con).value()+((add._imm12<<20)>>20)!=305420988 ) + return null; + CFGNode fun = n.cfg0(); + while( fun!=null && !(fun instanceof FunNode) ) fun = fun.idom(); + assertTrue("Constant must belong to a function",fun instanceof FunNode); + assertNull("Share one constant chain within each function",owners.put(fun,true)); + // Follow all parts of a machine constant, including shared inputs. + var todo = new java.util.ArrayList<Node>(); + var seen = new java.util.IdentityHashMap<Node,Boolean>(); + todo.add(n); + for( int j=0; j<todo.size(); j++ ) { + Node part = todo.get(j); + if( seen.put(part,true)!=null ) continue; + CFGNode owner = part.cfg0(); + while( owner!=null && !(owner instanceof FunNode) ) owner = owner.idom(); + assertSame("Every constant-building operation is function-local",fun,owner); + for( int i=1; i<part.nIns(); i++ ) { + Node def = part.in(i); + if( def==null || def instanceof CFGNode ) continue; + assertTrue("Copies must register their data edges",def._outputs.find(part)!=-1); + if( def._type.isConstant() ) todo.add(def); + } + } + return null; + }); + assertTrue("Exercise constants shared across functions",owners.size()>=2); + } + @Test public void testReachableMixedReturns() { for( String[] test : new String[][] { {"if(arg) return 7; else return 2.5;", "No common type amongst int and f64"}, diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 317fff71..aafaf7ed 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -733,7 +733,6 @@ public class CodeGen { if( n instanceof MachNode ) { for( int i=0; i < n.nIns(); i++ ) n._inputs.set(i, _instSelect(n.in(i),map) ); - pinGlobalValue(n); return n; } @@ -747,7 +746,6 @@ public class CodeGen { // Walk machine op and replace inputs with mapped inputs for( int i=0; i < x.nIns(); i++ ) x._inputs.set(i, _instSelect(x.in(i),map) ); - pinGlobalValue(x); // Post selection action if( x instanceof MachNode mach ) { if( n instanceof ReturnNode ret ) @@ -759,27 +757,6 @@ public class CodeGen { } - // Some machine values are Start-pinned globals or zero-code wrappers around - // them, e.g. pointer/function constants and PtrToInt/ReadOnly-style adapters. - // Before output edges are rebuilt, make ownership explicit: every global value - // chain member is Start-pinned in slot 0 and data-linked in later slots. - private void pinGlobalValue(Node n) { - if( n instanceof CFGNode || !(n instanceof MachNode mach) || mach.outregmap()==null || n.isPinned() ) - return; - if( n.nIns()==0 ) - return; - if( !(n.in(0)==null || n.in(0)==_start) ) - return; - for( int i=1; i<n.nIns(); i++ ) { - Node def = n.in(i); - if( def==null ) continue; - if( def.isConst() ) continue; - if( def.nIns()==0 ) return; - if( def.in(0) != _start ) return; - } - n._inputs.set(0,_start); - } - // Walk all machine Nodes, and set their output edges private void _instOuts( Node n, BitSet visit ) { if( visit.get(n._nid) ) return; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index a72dde97..ecd23c1e 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -42,127 +42,54 @@ public abstract class GlobalCodeMotion { rpo.add(cfg); } - // Break up shared global constants by functions + // 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 ) { - - // For all explicitly Start-pinned global values. Instruction - // selection keeps each zero-code/global chain member hooked to Start, - // so no later pass has to infer hidden global chains from data inputs. - for( int i=0; i< start.nOuts(); i++ ) { - Node con = start.out(i); - if( isStartPinnedGlobalValue(con) ) { - breakUpGlobalConstantSingle(con); - if( con.in(0) != start ) - i--; // Removed a global constant, re-run same index + var globals = new IdentityHashMap<Node,Boolean>(); + var cons = new ArrayList<Node>(); + for( Node con : start._outputs ) + if( con!=null && !(con instanceof CFGNode) && + (con.isConst() || con instanceof MachNode mach && mach.outregmap()!=null) ) { + globals.put(con,true); + cons.add(con.keep()); // Preserve original inputs while rewiring users. } - } - } - - private static void breakUpGlobalConstantSingle( Node con ) { - // Split dependent global values first; cloning a later chain member - // will recursively clone its Start-pinned inputs on demand. - for( Node use : con.outs() ) - if( use != null && useFun(use)==null ) { - assert isStartPinnedGlobalValue(use); - breakUpGlobalConstantSingle(use); - } - // While constant has users in different functions - while( true ) { - // Find a function user, and another function - FunNode fun = null; - boolean done=true; - for( Node use : con.outs() ) { - if( use == null ) continue; - FunNode fun2 = useFun(use); - assert fun2 != null && CodeGen.CODE.owns(fun2); - if( fun==null || fun==fun2 ) fun=fun2; - else { done=false; break; } + 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; + FunNode fun = useFun(use); + if( fun==null ) continue; // Global metadata has no function owner. + assert CodeGen.CODE.owns(fun); + var local = copies.computeIfAbsent(fun,f -> new IdentityHashMap<>()); + Node copy = cloneGlobal(con,fun,globals,local); + for( int i=0; i<use.nIns(); i++ ) + if( use.in(i)==con ) + use.setDef(i,copy); } - // No direct function users: keep this global value at Start. - if( fun==null ) - return; - // Single function user, so this constant is not shared - if( done ) { - con.setDef(0,fun); - return; - } - // Move function users to a private constant - Node con2 = cloneGlobalForFun(con,fun,new IdentityHashMap<>()); - // Move function users to this private constant - for( int j=0; j<con._outputs._len; j++ ) { - Node use = con.out(j); - if( use == null ) continue; - FunNode fun2 = useFun(use); - if( fun2==null || !CodeGen.CODE.owns(fun2) ) continue; - if( fun2==fun ) { - use.setDef(use._inputs.find(con),con2); - j--; - } - } - } + for( Node con : cons ) con.unkill(); } - private static Node cloneGlobalForFun(Node con, FunNode fun, IdentityHashMap<Node,Node> memo) { - Node memoized = memo.get(con); - if( memoized != null ) return memoized; - Node con2 = con.copy(); // Private constant clone - // Node copies made through Node(Node) carry unregistered inputs, while - // some machine copies construct fresh registered edges. The default - // Node.copy path gives an input-less clone. Normalize all of them to - // the original data inputs, pinned to the owning function. - memo.put(con,con2); - if( con2.nIns()==0 ) { - con2.addDef(fun); - for( int i=1; i<con.nIns(); i++ ) - con2.addDef(cloneInputForFun(con.in(i),fun,memo)); - } else { - Node oldCtrl = con2.in(0); - if( oldCtrl != null && oldCtrl._outputs.find(con2) != -1 ) - con2.setDef(0,null); - else - con2._inputs.set(0,null); - con2.setDef(0,fun); - for( int i=1; i<con2.nIns(); i++ ) - con2.setDef(i,cloneInputForFun(con.in(i),fun,memo)); + 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 con2; - } - - private static Node cloneInputForFun(Node def, FunNode fun, IdentityHashMap<Node,Node> memo) { - return isStartPinnedGlobalValue(def) - ? cloneGlobalForFun(def,fun,memo) - : def; - } - - private static boolean isStartPinnedGlobalValue(Node n) { - return n != null && n._type != null && !(n instanceof CFGNode) && - n.nIns() > 0 && n.in(0) instanceof StartNode && - (n.isConst() || n instanceof MachNode mach && mach.outregmap()!=null); + return copy; } private static FunNode useFun(Node use) { - if( use instanceof ReturnNode ret ) - return ret.fun(); - if( use instanceof ParmNode parm ) - return parm.fun(); + if( use instanceof ReturnNode ret ) return ret.fun(); + if( use instanceof ParmNode parm ) return parm.fun(); CFGNode cfg = use.cfg0(); - if( cfg!=null ) { - FunNode fun = cfg.fun(); - if( fun != null ) return fun; - } - // Use itself is not in a function... which makes it a 2-part - // constant such as happens on some chips where large constants have - // to be built up in parts. PtrToInt followed by the array-body Add is - // another zero-code/global-value chain, so walk through any number of - // single-use pieces until reaching the function-owned use. - FunNode fun = null; - for( Node out : use.outs() ) { - FunNode f = useFun(out); - if( f != null && fun != null && f != fun ) return null; - if( f != null ) fun = f; - } - return fun; + while( cfg!=null && !(cfg instanceof FunNode) ) + cfg = cfg.idom(); + return (FunNode)cfg; } @@ -177,6 +104,9 @@ public abstract class GlobalCodeMotion { cfg.loopDepth(); for( Node n : cfg._inputs ) _schedEarly(n,code ); + // 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 ) @@ -188,19 +118,16 @@ public abstract class GlobalCodeMotion { if( n==null || code._visit.get(n._nid) ) return; // Been there, done that assert !(n instanceof CFGNode); code._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,code); - // 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 = code._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 @@ -212,8 +139,11 @@ public abstract class GlobalCodeMotion { 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()]; // Breadth-first scheduling - breadth(code._stop,ns,late); + breadth(code._stop,ns,late,anti); // Copy the best placement choice into the control slot for( int i=0; i<late.length; i++ ) @@ -221,7 +151,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); @@ -255,30 +185,26 @@ public abstract class GlobalCodeMotion { } // 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 + // 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 && late[def._nid]==null ) - work.push(def); - // if the def has a load use, maybe the load can fire - if( def!=null ) - for( Node out : def._outputs ) - if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null ) - work.push(ld); + if( def==null ) continue; + if( late[def._nid]==null ) work.push(def); + for( Node out : def._outputs ) + if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null ) + work.push(ld); } - - if( n instanceof LoopNode loop ) { - for( Node phi : loop._outputs ) { + 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; @@ -289,7 +215,7 @@ public abstract class GlobalCodeMotion { // Loads may need anti-dependencies, raising their LCA if( n instanceof MemOpNode load && load._isLoad ) - 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 @@ -314,7 +240,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; @@ -329,36 +255,36 @@ public abstract class GlobalCodeMotion { best instanceof IfNode; } - private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late) { + private static CFGNode find_anti_dep(CFGNode lca, MemOpNode 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; 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 MemOpNode st: if( !st._isLoad && load._alias == st._alias ) { assert late[mem._nid] != null; - lca = anti_dep( load, late[mem._nid], mem.cfg0(), lca, st ); + lca = anti_dep(load,late[mem._nid],lca,st,anti); } break; // Loads do not cause anti-deps on other loads case EscapeNode esc: if( load._alias == esc.fld()._alias ) { assert late[mem._nid] != null; - lca = anti_dep( load, late[mem._nid], mem.cfg0(), lca, mem ); + lca = anti_dep(load,late[mem._nid],lca,mem,anti); } break; case CallNode call: assert late[call._nid]!=null; - lca = anti_dep(load,late[call._nid],call.cfg0(),lca,call); + lca = anti_dep(load,late[call._nid],lca,call,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),lca,null,anti); break; case ReturnNode ret: break; // Load must already be ahead of Return case MemMergeNode ret: break; // Mem uses now on ScopeMin @@ -369,13 +295,12 @@ public abstract class GlobalCodeMotion { } // - private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { - // Store and Load overlap, need anti-dependence - if( stblk._anti==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 - return lca; // Cap this stores' anti-dep to here + private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode lca, Node st, int[] anti ) { + // Stores are already placed. Constrain the load at that block only. + if( anti[stblk._nid]==load._nid ) { + lca = stblk.domLCA(lca,null); + if( lca==stblk && st!=null && st._inputs.find(load) == -1 ) + st.addDef(load); // Same-block load must precede the store. } return lca; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java index b40f4204..15531c78 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -166,9 +166,6 @@ public abstract class CFGNode extends Node { return fun != null && fun == that.fun(); } - // Anti-dependence field support - public int _anti; // Per-CFG field to help find anti-deps - // Find nearest enclosing FunNode public FunNode fun() { CFGNode cfg = this; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java index 7f0b2b7d..6e9b0a70 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java @@ -42,7 +42,6 @@ public class FunPtrNode extends TypeNode { } @Override public boolean isConst() { return true; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { ReturnNode ret = ret(); if( ret == null ) return _con; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/GuardNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/GuardNode.java index 16b83f22..076a8388 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/GuardNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/GuardNode.java @@ -32,7 +32,6 @@ public class GuardNode extends Node { @Override public String label() { return _nonZero ? "(!=0)" : "(==0)"; } @Override public String uniqueName() { return "Guard_"+_nid; } - @Override public boolean isPinned() { return true; } @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { return in(1)._print0(sb.append(label()),visited); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java index 873716da..e884251c 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java @@ -728,8 +728,6 @@ public abstract class Node implements Cloneable { /** 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; } // ------------------------------------------------------------------------ // Peephole utilities @@ -763,7 +761,11 @@ public abstract class Node implements Cloneable { // Does not need to be implemented in isCFG() nodes. Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } - public Node copy() { + public Node copy() { return copyEmpty(); } + + // 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); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 4d357fda..54cfc3ad 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -66,7 +66,6 @@ public class PhiNode extends Node { public CFGNode region() { return (CFGNode)in(0); } @Override public boolean isMem() { return _type instanceof TypeMem; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 97b9ed45..5e3c7080 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -47,7 +47,6 @@ public class ProjNode extends Node implements Proj { } @Override public boolean isMem() { return _type instanceof TypeMem; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java index 8d8d3950..fe2060ba 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java @@ -20,10 +20,6 @@ public class TFPX86 extends FunPtrNode implements MachNode, RIPRelSize { TFPX86( TypeFunPtr fptr, String ext ) { super(fptr,CodeGen.CODE._start,null); _type = fptr; _ext = ext; } @Override public String op() { return "ldx"; } @Override public String label() { return op(); } - // The ideal FunPtrNode is pinned because its Return input is a lifetime - // hook. After selection this is an ordinary cloneable load-address - // instruction and must be scheduled down near its actual use. - @Override public boolean isPinned() { return false; } @Override public boolean isClone() { return true; } @Override public TFPX86 copy() { return new TFPX86(this); } @Override public RegMask regmap(int i) { return null; } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 4cf19746..82529019 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -11,6 +11,44 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testFunctionLocalConstantChains() { + String src = "val f = { int x -> x ? f(x-1)*305420988+x/305420988 : 1; }; "+ + "val g = { int x -> x ? g(x-1)/305420988+x*305420988 : 1; }; "+ + "return f(arg)+g(arg);"; + CodeGen code = new CodeGen(src); + code.driver(CodeGen.Phase.Schedule,"riscv","SystemV"); + var owners = new java.util.IdentityHashMap<CFGNode,Boolean>(); + code._stop.walk(n -> { + if( !(n instanceof com.seaofnodes.simple.node.cpus.riscv.AddIRISC add) || + !(add.in(1) instanceof com.seaofnodes.simple.node.cpus.riscv.LUI upper) || + ((TypeInteger)upper._con).value()+((add._imm12<<20)>>20)!=305420988 ) + return null; + CFGNode fun = n.cfg0(); + while( fun!=null && !(fun instanceof FunNode) ) fun = fun.idom(); + assertTrue("Constant must belong to a function",fun instanceof FunNode); + assertNull("Share one constant chain within each function",owners.put(fun,true)); + // Follow all parts of a machine constant, including shared inputs. + var todo = new java.util.ArrayList<Node>(); + var seen = new java.util.IdentityHashMap<Node,Boolean>(); + todo.add(n); + for( int j=0; j<todo.size(); j++ ) { + Node part = todo.get(j); + if( seen.put(part,true)!=null ) continue; + CFGNode owner = part.cfg0(); + while( owner!=null && !(owner instanceof FunNode) ) owner = owner.idom(); + assertSame("Every constant-building operation is function-local",fun,owner); + for( int i=1; i<part.nIns(); i++ ) { + Node def = part.in(i); + if( def==null || def instanceof CFGNode ) continue; + assertTrue("Copies must register their data edges",def._outputs.find(part)!=-1); + if( def._type.isConstant() ) todo.add(def); + } + } + return null; + }); + assertTrue("Exercise constants shared across functions",owners.size()>=2); + } + @Test public void testReachableMixedReturns() { for( String[] test : new String[][] { {"if(arg) return 7; else return 2.5;", "No common type amongst int and f64"}, diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index a6fe5a76..eae47295 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -69,7 +69,6 @@ Chapter 25 suite, including `make -j 4 tests`. | Group | Eventual home | Why not in the small queue yet | |---|---|---| -| Scheduling and global constant cloning | 11 / 19 as applicable | Separate scheduling and compilation-unit ownership changes; need reduced old-IR failures. | | Register allocation and spilling | 20 onward | Need constrained-register/spill regressions; changed golden spill counts are insufficient evidence. | | Conditional Store and array Load control | Memory/arrays chapters | Reproduce under the earlier alias model before extracting fixes from the new memory implementation. | | SCCP dependencies, function revival, reachability | 24; some foundations may fit 18 | Separate old-IR corrections from new Guard/Escape/BulkMemPhi and external-caller machinery. | @@ -77,7 +76,6 @@ Chapter 25 suite, including `make -j 4 tests`. | TypeScalar, numeric modes, guards, symbolic fields, open/forward types | Revisit earlier homes later | A connected incomplete-types architecture, including phase ordering and errors. | | BulkMemPhi/MemPhi, private constructor memory, allocation helpers | Revisit memory / constructors / methods | Move invariants and regressions together. | | Serialization, global identity remapping, module escape summaries | Separate compilation | Remain with modules. | -| Remove CFGNode._anti | move the field into a temp array during GCM | ## Review and test protocol @@ -119,6 +117,76 @@ Historical results below are dated evidence, not a substitute for a fresh baseline. Logs live in ignored build directories and may no longer exist. Reusable implementation lessons are in `skills/chapter25-codex-notes.md`. +### Scheduling without isPinned: complete locally, 2026-09-20 + +Removed `isPinned()` and all overrides in 11-25. Early scheduling walks inputs, +then assigns a block only when input 0 is null. Existing control and Phi/Proj +bindings stay intact. For ordinary values, that control is an earliest-placement +bound, not a prohibition on sinking during late scheduling. + +Chapters 11-14 also used the predicate for late placement; GCM now preserves +those cases explicitly (Proj, New, Parser.ZERO, and Cast from 13), alongside its +existing CFG/Phi handling. From 15, late scheduling already handles its fixed +CFG/Phi/Proj cases structurally. + +The preceding GCM suites supplied the passing baseline. After forced Java +rebuilds, every full snapshot suite in 11-25 passed `make -j 4 tests`, with +assertions enabled and unchanged expectations/counts (449 total in 25). Existing +constant-chain, guard, loop, allocation, native, and emulator tests all pass. +No remaining `isPinned` declaration or call exists in the chapter sources. +Edited files retain LF endings; `git diff --check` passes. +Logs: `chapter25/build/pinned-review/{chapter25,backports}.log`. + +### GCM and global constant cloning: unified locally, 2026-09-20 + +GCM starts in 11; functions make constant ownership relevant in 18. Chapters +11-25 now share the early definitions-first / late uses-first worklist strategy, +including Region/Loop Phi discovery, waiting-load wakeups, and LCA over every +matching Phi input. Anti-dependence marks moved from CFGNode into a temporary +GCM array. Removed the obsolete fixed-register placement heuristic in 21-24. + +Chapters 18-25 clone entire global constant-building graphs with one identity +map per function, reusing shared subgraphs within that function. Originals stay +intact until all rewrites finish. `Node.copyEmpty()` supplies exact-class clones +with fresh IDs and empty edges, avoiding incompatible machine `copy()` contracts. +Removed 25's redundant instruction-selection pinning to the old ideal Start. + +Necessary chapter differences remain explicit: 18-19's linked Parm inputs +belong to their callers; from 20, unlinked Parms belong to the callee. In 11-20, +the evaluator independently reschedules nodes, so anti-dependencies retain the +full store placement range. Trying the later single-block rule fails the existing +`SchedulerTest.testStoreInIf2`. Alias/tuple memory representations stay local to +their chapters; 25 retains its compilation-unit ownership check. + +The new Chapter18Test regression in every snapshot 18-25 exercises two surviving +recursive functions, repeated uses, registered edges, and function-local chains: +stacked Cast/Constant nodes in 18-20 and RISC LUI/AddI expansions in 21-25. It +fails against isolated original GCM classes in 18 and 20, and passes afterward. +Original 21 and 25 already pass the machine-chain case; those changes simplify +and unify the implementation rather than correcting that particular case. + +Changed ordering exposed 21's existing empty-block layout bug: entering a nested +loop was mistaken for a backedge, producing a bad native Sieve branch. Backported +22's same-loop-tree check; native and emulated Sieve pass. Updated 21's tighter +scaled spill expectations: stringHash RISC 5->3 and ARM 6->3; BrainFuck RISC +44->28. BrainFuck executes on both emulators; a separate direct-entry RISC +hashCode probe verifies both initial hashing and the cached result. + +Validation: unmodified full baselines passed in 11-25. After forced Java rebuilds, +all full chapter targets pass with assertions and `make -j 4 tests`: ordinary +counts in 11-24 are 166, 169, 184, 204, 215, 233, 285, 316, 358, 368, 385, 397, +416, and 439, plus the separately invoked fuzzer wrappers where applicable. +Chapter 25 passes 449 tests across its groups. All edited files use LF endings. +Logs: `chapter25/build/gcm-review/{baseline,before-test,focus-all,final,final25}.log`; +`final.log` covers successful 11-24 runs and `final25.log` the final 25 rebuild/run. + +Independent follow-up: a direct-entry ARM emulator probe of 21's exported +`hashCode` traps with code 3 under both original and updated GCM. It uses the +existing stringHash.smp library, a String containing the u8 array "test", and a +zero cached hash; the cause is not diagnosed. Do not claim the green suite or +lower spill count validates this extra case. Scratch reproducer: `StringProof.java` +in the same review directory; the RISC equivalent returns/caches 3556498. + ### Dominator caches: unified locally, 2026-09-19 Real dominator searches begin in 6. The original Region pointer cache in 6-9 diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index ea794c8b..fd5ab9d9 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -18,6 +18,7 @@ lessons rather than duplicating that history. concrete node-number traces are preferred over speculative broad rewrites. - Printers are valid debugging tools. If printing changes behavior, fixing the printer/accessor side effect is immediately high priority. +- Keep edited text files LF-only, including on Windows. - Preserve unrelated dirty changes. Emacs lock/backup files are common and are not permission to clean the tree. - Do not push without explicit approval. Prefer commits at meaningful test @@ -76,6 +77,50 @@ lessons rather than duplicating that history. - Keep single-return accessors and overrides compact on one line, including `idepth()` and `validIDepth()`. + +## Global code motion and constant ownership + +- GCM starts in 11; function-local constant graphs start with functions in 18. + Use an early definitions-first walk and a late uses-first worklist. Visit + Region/Loop Phis during early scheduling, and wake loop Phis and waiting loads + during late scheduling. The two walks must agree: otherwise late scheduling + can reach unscheduled arithmetic through a loop Phi. For ArrayList-backed + outputs, walk the original index range when early scheduling appends uses. +- `isPinned()` is unnecessary: early scheduling preserves an existing input 0 + and computes a block only for nodes with a null input 0, after walking their + inputs. Proj input 0 names its producer, so it must not be replaced by control. + For ordinary values, existing control is an earliest-placement bound; late + scheduling can still move them downward. Chapters 11-14 retain their fixed + late-placement cases explicitly in GCM (Proj, New, Parser.ZERO, and Cast from + 13). Later GCM already handles fixed CFG/Phi/Proj placement structurally. +- After early scheduling, global constant-building operations have Start in + input 0. Snapshot and keep those originals, then clone their input graphs with + one identity map per function. Reuse each copy throughout its function; keep + originals intact until all users are rewritten. This covers Cast/Constant + stacks and machine expansions without recursively inferring users' ownership. +- `Node.copyEmpty()` makes an exact-class clone with fresh ID and empty edges. + GCM wires it with `addDef`; do not use machine `copy()` overrides here, whose + rematerialization contracts differ about whether input edges are registered. + Preserve ordinary copy/cache fields; clear graph edges, dependencies and hash. +- In 18-19, calls remain linked: a Parm input is evaluated in its caller, and + the unknown-caller input stays global. From 20, unlinked Parm values belong to + the callee. Preserve 25's compilation-unit ownership checks. +- Let early scheduling place machine constant expansions. Pinning them during + instruction selection can attach them to the old ideal Start rather than the + selected Start, forcing later code to recover from the wrong root. +- Keep anti-dependence marks in a pass-local array, not CFGNode. In 11-20 the + evaluator independently reschedules nodes, so retain the full store placement + range when constraining loads; using only GCM's final store block breaks + `SchedulerTest.testStoreInIf2`. From 21, the chosen store block suffices. + Preserve each chapter's alias/tuple memory representation when finding stores. +- Changes in node order can expose encoding bugs. Chapter 21's empty-block scan + mistook entry to a nested loop for a backedge; require the same loop-tree node, + as in 22 onward. Native Sieve is sensitive to this and must actually execute. +- Test function-local chains with two surviving function bodies. In 24, returning + function pointers alone does not put their bodies in the scheduled graph; + recursive calls keep this regression meaningful. Check all chain members, + registered data edges, and one shared copy per function. + ## Null guards: B13 / issue #246 lessons - Null refinement starts in Chapter 10; arrays in 15; scoped expression guards |
