diff options
Diffstat (limited to 'chapter25/src/main/java')
9 files changed, 79 insertions, 186 deletions
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; } |