summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2026-09-20 10:04:48 -0700
committerCliff Click <cliffc@acm.org>2026-09-20 10:04:48 -0700
commitdb3ca780c26b78cbe129a5c1bdf0d8ff7d867d1b (patch)
treeaa12f702c8b558446b06944ed5301dc826245c8f
parent6e59fc1b71f2098c8baf90a6c54e5a33b7291e94 (diff)
downloadSimple-db3ca780c26b78cbe129a5c1bdf0d8ff7d867d1b.tar.gz
Simple-db3ca780c26b78cbe129a5c1bdf0d8ff7d867d1b.zip
Unify GCM across chapters
Remove the _anti field. Remove the isPinned() call. Add a copyEmpty call.
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java152
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java4
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java1
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java1
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/Node.java2
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java150
-rw-r--r--chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java4
-rw-r--r--chapter12/src/main/java/com/seaofnodes/simple/node/ConstantNode.java1
-rw-r--r--chapter12/src/main/java/com/seaofnodes/simple/node/NewNode.java1
-rw-r--r--chapter12/src/main/java/com/seaofnodes/simple/node/Node.java2
-rw-r--r--chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter12/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java92
-rw-r--r--chapter13/src/main/java/com/seaofnodes/simple/node/CFGNode.java4
-rw-r--r--chapter13/src/main/java/com/seaofnodes/simple/node/CastNode.java2
-rw-r--r--chapter13/src/main/java/com/seaofnodes/simple/node/ConstantNode.java1
-rw-r--r--chapter13/src/main/java/com/seaofnodes/simple/node/NewNode.java1
-rw-r--r--chapter13/src/main/java/com/seaofnodes/simple/node/Node.java2
-rw-r--r--chapter13/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter13/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java92
-rw-r--r--chapter14/src/main/java/com/seaofnodes/simple/node/CFGNode.java4
-rw-r--r--chapter14/src/main/java/com/seaofnodes/simple/node/CastNode.java2
-rw-r--r--chapter14/src/main/java/com/seaofnodes/simple/node/ConstantNode.java1
-rw-r--r--chapter14/src/main/java/com/seaofnodes/simple/node/NewNode.java1
-rw-r--r--chapter14/src/main/java/com/seaofnodes/simple/node/Node.java2
-rw-r--r--chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter14/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java83
-rw-r--r--chapter15/src/main/java/com/seaofnodes/simple/node/CFGNode.java3
-rw-r--r--chapter15/src/main/java/com/seaofnodes/simple/node/CastNode.java2
-rw-r--r--chapter15/src/main/java/com/seaofnodes/simple/node/Node.java2
-rw-r--r--chapter15/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter15/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java85
-rw-r--r--chapter16/src/main/java/com/seaofnodes/simple/node/CFGNode.java3
-rw-r--r--chapter16/src/main/java/com/seaofnodes/simple/node/CastNode.java1
-rw-r--r--chapter16/src/main/java/com/seaofnodes/simple/node/Node.java2
-rw-r--r--chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter16/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java75
-rw-r--r--chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java3
-rw-r--r--chapter17/src/main/java/com/seaofnodes/simple/node/CastNode.java1
-rw-r--r--chapter17/src/main/java/com/seaofnodes/simple/node/Node.java2
-rw-r--r--chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter17/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java123
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java3
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/CastNode.java1
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/Node.java24
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java46
-rw-r--r--chapter19/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java123
-rw-r--r--chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java3
-rw-r--r--chapter19/src/main/java/com/seaofnodes/simple/node/CastNode.java1
-rw-r--r--chapter19/src/main/java/com/seaofnodes/simple/node/Node.java24
-rw-r--r--chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter19/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java46
-rw-r--r--chapter20/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java153
-rw-r--r--chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java3
-rw-r--r--chapter20/src/main/java/com/seaofnodes/simple/node/CastNode.java1
-rw-r--r--chapter20/src/main/java/com/seaofnodes/simple/node/Node.java24
-rw-r--r--chapter20/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter20/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java46
-rw-r--r--chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java2
-rw-r--r--chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java186
-rw-r--r--chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java3
-rw-r--r--chapter21/src/main/java/com/seaofnodes/simple/node/CastNode.java1
-rw-r--r--chapter21/src/main/java/com/seaofnodes/simple/node/Node.java8
-rw-r--r--chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter21/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java2
-rw-r--r--chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java38
-rw-r--r--chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java4
-rw-r--r--chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java4
-rw-r--r--chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java186
-rw-r--r--chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java3
-rw-r--r--chapter22/src/main/java/com/seaofnodes/simple/node/CastNode.java1
-rw-r--r--chapter22/src/main/java/com/seaofnodes/simple/node/Node.java8
-rw-r--r--chapter22/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter22/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java38
-rw-r--r--chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java186
-rw-r--r--chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java3
-rw-r--r--chapter23/src/main/java/com/seaofnodes/simple/node/CastNode.java1
-rw-r--r--chapter23/src/main/java/com/seaofnodes/simple/node/Node.java8
-rw-r--r--chapter23/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter23/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java38
-rw-r--r--chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java186
-rw-r--r--chapter24/src/main/java/com/seaofnodes/simple/node/CFGNode.java3
-rw-r--r--chapter24/src/main/java/com/seaofnodes/simple/node/CastNode.java1
-rw-r--r--chapter24/src/main/java/com/seaofnodes/simple/node/Node.java8
-rw-r--r--chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter24/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java38
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java23
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java223
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java3
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java1
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/GuardNode.java1
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/Node.java8
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java1
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/ProjNode.java1
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java4
-rw-r--r--chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java38
-rw-r--r--docs/chapter-backports.md72
-rw-r--r--skills/chapter25-codex-notes.md45
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