diff options
Diffstat (limited to 'chapter18/src/main/java')
6 files changed, 110 insertions, 43 deletions
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index f68043c4..d96bd178 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -12,10 +12,61 @@ public abstract class GlobalCodeMotion { // following block). There are no unreachable infinite loops. public static void buildCFG( StartNode start, StopNode stop ) { schedEarly(start); + breakUpGlobalConstants(start); schedLate(stop); } + // After early scheduling, every global chain member has Start in slot 0. + // Give each function one private copy of the entire dependency graph. + private static void breakUpGlobalConstants( StartNode start ) { + var globals = new IdentityHashMap<Node,Boolean>(); + var cons = new ArrayList<Node>(); + for( Node con : start._outputs ) + if( con!=null && !(con instanceof CFGNode) && + con.isConst() ) { + globals.put(con,true); + cons.add(con.keep()); // Preserve original inputs while rewiring users. + } + + var copies = new IdentityHashMap<FunNode,IdentityHashMap<Node,Node>>(); + for( Node con : cons ) + for( Node use : con._outputs.asAry() ) { + if( use==null || globals.containsKey(use) ) continue; + for( int i=0; i<use.nIns(); i++ ) { + if( use.in(i)!=con ) continue; + FunNode fun = useFun(use,i); + if( fun==null ) continue; // Unknown-caller types stay global. + var local = copies.computeIfAbsent(fun,f -> new IdentityHashMap<>()); + use.setDef(i,cloneGlobal(con,fun,globals,local)); + } + } + for( Node con : cons ) con.unkill(); + } + + private static Node cloneGlobal(Node con, FunNode fun, IdentityHashMap<Node,Boolean> globals, + IdentityHashMap<Node,Node> copies) { + Node copy = copies.get(con); + if( copy!=null ) return copy; + copies.put(con,copy=con.copyEmpty()); + copy.addDef(fun); + for( int i=1; i<con.nIns(); i++ ) { + Node def = con.in(i); + copy.addDef(globals.containsKey(def) ? cloneGlobal(def,fun,globals,copies) : def); + } + return copy; + } + + private static FunNode useFun(Node use, int idx) { + if( use instanceof ReturnNode ret ) return ret.fun(); + // Calls are still linked: a Parm input is evaluated in its caller. + CFGNode cfg = use instanceof ParmNode parm ? parm.fun().cfg(idx) : use.cfg0(); + while( cfg!=null && !(cfg instanceof FunNode) ) + cfg = cfg.idom(); + return (FunNode)cfg; + } + + // ------------------------------------------------------------------------ // Visit all nodes in CFG Reverse Post-Order, essentially defs before uses // (except at loops). Since defs are visited first - and hoisted as early @@ -31,6 +82,9 @@ public abstract class GlobalCodeMotion { cfg.loopDepth(); for( Node n : cfg._inputs ) _schedEarly(n,visit); + // In dead infinite loops, entire code blocks may be unreachable + // from below. Reach down from the CFG to their Phis so their + // inputs are scheduled too. if( cfg instanceof RegionNode ) for( Node phi : cfg._outputs ) if( phi instanceof PhiNode ) @@ -54,18 +108,15 @@ public abstract class GlobalCodeMotion { if( n==null || visit.get(n._nid) ) return; // Been there, done that assert !(n instanceof CFGNode); visit.set(n._nid); - // Schedule not-pinned not-CFG inputs before self. Since skipping - // Pinned, this never walks the backedge of Phis (and thus spins around - // a data-only loop), eventually attempting relying on some pre-visited- - // not-post-visited data op with no scheduled control. + // Schedule inputs first, except Phis: following their backedges would + // enter a data cycle before its control has been scheduled. for( Node def : n._inputs ) if( def!=null && !(def instanceof PhiNode) ) _schedEarly(def,visit); - // If not-pinned (e.g. constants, projections, phi) and not-CFG - if( !n.isPinned() ) { + // An existing edge 0 already supplies control (or a Phi/Proj binding). + if( n.in(0)==null ) { // Schedule at deepest input CFGNode early = Parser.START; // Maximally early, lowest idepth - if( n.in(0) instanceof CFGNode cfg ) early = cfg; for( int i=1; i<n.nIns(); i++ ) if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() ) early = n.in(i).cfg0(); // Latest/deepest input @@ -77,8 +128,11 @@ public abstract class GlobalCodeMotion { private static void schedLate( StopNode stop) { CFGNode[] late = new CFGNode[Node.UID()]; Node[] ns = new Node[Node.UID()]; + // Record Load NIDs at all their CFG block choices, then check against + // Store block choices to force a Load above an anti-dependent Store. + int[] anti = new int[Node.UID()]; // Breadth-first scheduling - breadth(stop,ns,late); + breadth(stop,ns,late,anti); // Copy the best placement choice into the control slot for( int i=0; i<late.length; i++ ) @@ -86,7 +140,7 @@ public abstract class GlobalCodeMotion { ns[i].setDef(0,late[i]); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late) { + private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { // Things on the worklist have some (but perhaps not all) uses done. WorkList<Node> work = new WorkList<>(); work.push(stop); @@ -118,22 +172,26 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late); + _doSchedLate(n,ns,late,anti); } - // Walk all inputs and put on worklist, as their last-use might now be done - for( Node def : n._inputs ) - if( def!=null && late[def._nid]==null ) { - work.push(def); - // if the def has a load use, maybe the load can fire - for( Node ld : def._outputs ) - if( ld instanceof LoadNode && late[ld._nid]==null ) - work.push(ld); - } + // A use just finished; reconsider its inputs and waiting loads, + // even when the shared memory input was already scheduled. + for( Node def : n._inputs ) { + if( def==null ) continue; + if( late[def._nid]==null ) work.push(def); + for( Node out : def._outputs ) + if( out instanceof LoadNode ld && late[ld._nid]==null ) + work.push(ld); + } + if( n instanceof LoopNode loop ) + for( Node phi : loop._outputs ) + if( phi instanceof PhiNode && late[phi._nid]==null ) + work.push(phi); } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late) { + private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { // Walk uses, gathering the LCA (Least Common Ancestor) of uses CFGNode early = n.in(0) instanceof CFGNode cfg ? cfg : n.in(0).cfg0(); assert early != null; @@ -144,7 +202,7 @@ public abstract class GlobalCodeMotion { // Loads may need anti-dependencies, raising their LCA if( n instanceof LoadNode load ) - lca = find_anti_dep(lca,load,early,late); + lca = find_anti_dep(lca,load,early,late,anti); // Walk up from the LCA to the early, looking for best place. This is // the lowest execution frequency, approximated by least loop depth and @@ -167,7 +225,7 @@ public abstract class GlobalCodeMotion { CFGNode found=null; for( int i=1; i<phi.nIns(); i++ ) if( phi.in(i)==n ) - found = phi.region().cfg(i).domLCA(found,null); + found = phi.region().cfg(i).domLCA(found,null); // Can be more than one matching input. assert found!=null; return found; @@ -177,31 +235,33 @@ public abstract class GlobalCodeMotion { // Least loop depth first, then largest idepth private static boolean better( CFGNode lca, CFGNode best ) { return lca.loopDepth() < best.loopDepth() || - (lca.idepth() > best.idepth() || best instanceof IfNode); + lca instanceof NeverNode || + lca.idepth() > best.idepth() || + best instanceof IfNode; } - private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late) { + private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) - cfg._anti = load._nid; + anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.mem()._outputs ) { switch( mem ) { case StoreNode st: assert late[st._nid]!=null; - lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st); + lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); break; case CallNode st: assert late[st._nid]!=null; - lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st); + lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); break; case PhiNode phi: // Repeat anti-dep for matching Phi inputs. // No anti-dep edges but may raise the LCA. for( int i=1; i<phi.nIns(); i++ ) if( phi.in(i)==load.mem() ) - lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null); + lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null,anti); break; case NewNode st: break; case LoadNode ld: break; // Loads do not cause anti-deps on other loads @@ -215,11 +275,12 @@ public abstract class GlobalCodeMotion { } // - private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { - // Walk store blocks "reach" from its scheduled location to its earliest + private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st, int[] anti ) { + // Preserve the full store range for the earlier evaluator scheduler. + // It places nodes independently of GCM and may hoist this store. for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence - if( stblk._anti==load._nid ) { + if( anti[stblk._nid]==load._nid ) { lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java index dc486549..ece46e80 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -78,9 +78,6 @@ public abstract class CFGNode extends Node { return lhs; } - // Anti-dependence field support - public int _anti; // Per-CFG field to help find anti-deps - // ------------------------------------------------------------------------ // Loop nesting public LoopNode loop() { return _ltree._head; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CastNode.java index d8a968c1..6438abb5 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -21,7 +21,6 @@ public class CastNode extends Node { @Override public String uniqueName() { return "Cast_" + _nid; } - @Override public boolean isPinned() { return true; } @Override public boolean isConst() { return true; } @Override diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java index c9369742..02b95669 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java @@ -11,14 +11,14 @@ import java.util.function.Function; * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public abstract class Node { +public abstract class Node implements Cloneable { /** * Each node has a unique dense Node ID within a compilation context * The ID is useful for debugging, for using as an offset in a bitvector, * as well as for computing equality of nodes (to be implemented later). */ - public final int _nid; + public int _nid; /** * Inputs to the node. These are use-def references to Nodes. @@ -27,7 +27,7 @@ public abstract class Node { * Ordering is required because e.g. "a/b" is different from "b/a". * The first input (offset 0) is often a {@link CFGNode} node. */ - public final Ary<Node> _inputs; + public Ary<Node> _inputs; /** * Outputs reference Nodes that are not null and have this Node as an @@ -38,7 +38,7 @@ public abstract class Node { * walked in either direction. These outputs are typically used for * efficient optimizations but otherwise have no semantics meaning. */ - public final Ary<Node> _outputs; + public Ary<Node> _outputs; /** @@ -556,8 +556,6 @@ public abstract class Node { /** Is this Node Memory related */ public boolean isMem() { return false; } - /** Pinned in the schedule; these are data nodes whose input#0 is not allowed to change */ - public boolean isPinned() { return false; } // Semantic change to the graph (so NOT a peephole), used by the Parser. // If any input is a float, flip to a float-flavored opcode and widen any @@ -612,6 +610,20 @@ public abstract class Node { // Does not need to be implemented in isCFG() nodes. Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } + // Exact-class copy with fresh identity and no edges. Unlike machine + // rematerialization copies, this never registers or copies input edges. + public final Node copyEmpty() { + Node n; + try { n = (Node)clone(); } + catch( Exception e ) { throw new RuntimeException(e); } + n._nid = UNIQUE_ID++; // allocate unique dense ID + n._inputs = new Ary<>(Node.class); + n._outputs = new Ary<>(Node.class); + n._deps = null; + n._hash = 0; + return n; + } + // Report any post-optimize errors public Parser.ParseException err() { return null; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 9aed8287..4ca50a3c 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -44,7 +44,6 @@ public class PhiNode extends Node { public CFGNode region() { return (CFGNode)in(0); } @Override public boolean isMultiTail() { return true; } @Override public boolean isMem() { return _declaredType instanceof TypeMem; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java index ea211dd2..81917bef 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -37,7 +37,6 @@ public class ProjNode extends Node implements MultiUse { @Override public boolean isMultiTail() { return in(0).isMultiHead(); } @Override public boolean isMem() { return _type instanceof TypeMem; } - @Override public boolean isPinned() { return true; } @Override public Type compute() { |