From db3ca780c26b78cbe129a5c1bdf0d8ff7d867d1b Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 20 Sep 2026 10:04:48 -0700 Subject: Unify GCM across chapters Remove the _anti field. Remove the isPinned() call. Add a copyEmpty call. --- .../simple/codegen/GlobalCodeMotion.java | 153 ++++++++++++--------- .../java/com/seaofnodes/simple/node/CFGNode.java | 3 - .../java/com/seaofnodes/simple/node/CastNode.java | 1 - .../main/java/com/seaofnodes/simple/node/Node.java | 24 +++- .../java/com/seaofnodes/simple/node/PhiNode.java | 1 - .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - 6 files changed, 107 insertions(+), 76 deletions(-) (limited to 'chapter20/src/main/java/com') 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(); + var cons = new ArrayList(); + 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>(); + 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 globals, + IdentityHashMap 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 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 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 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 _inputs; + public Ary _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 _outputs; + public Ary _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() { -- cgit v1.2.3