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