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. --- .../com/seaofnodes/simple/GlobalCodeMotion.java | 152 ++++++++------ .../java/com/seaofnodes/simple/node/CFGNode.java | 4 - .../com/seaofnodes/simple/node/ConstantNode.java | 1 - .../java/com/seaofnodes/simple/node/NewNode.java | 1 - .../main/java/com/seaofnodes/simple/node/Node.java | 2 - .../java/com/seaofnodes/simple/node/PhiNode.java | 1 - .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - .../com/seaofnodes/simple/GlobalCodeMotion.java | 150 ++++++++------ .../java/com/seaofnodes/simple/node/CFGNode.java | 4 - .../com/seaofnodes/simple/node/ConstantNode.java | 1 - .../java/com/seaofnodes/simple/node/NewNode.java | 1 - .../main/java/com/seaofnodes/simple/node/Node.java | 2 - .../java/com/seaofnodes/simple/node/PhiNode.java | 1 - .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - .../com/seaofnodes/simple/GlobalCodeMotion.java | 92 +++++---- .../java/com/seaofnodes/simple/node/CFGNode.java | 4 - .../java/com/seaofnodes/simple/node/CastNode.java | 2 - .../com/seaofnodes/simple/node/ConstantNode.java | 1 - .../java/com/seaofnodes/simple/node/NewNode.java | 1 - .../main/java/com/seaofnodes/simple/node/Node.java | 2 - .../java/com/seaofnodes/simple/node/PhiNode.java | 1 - .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - .../com/seaofnodes/simple/GlobalCodeMotion.java | 92 +++++---- .../java/com/seaofnodes/simple/node/CFGNode.java | 4 - .../java/com/seaofnodes/simple/node/CastNode.java | 2 - .../com/seaofnodes/simple/node/ConstantNode.java | 1 - .../java/com/seaofnodes/simple/node/NewNode.java | 1 - .../main/java/com/seaofnodes/simple/node/Node.java | 2 - .../java/com/seaofnodes/simple/node/PhiNode.java | 1 - .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - .../com/seaofnodes/simple/GlobalCodeMotion.java | 83 ++++---- .../java/com/seaofnodes/simple/node/CFGNode.java | 3 - .../java/com/seaofnodes/simple/node/CastNode.java | 2 - .../main/java/com/seaofnodes/simple/node/Node.java | 2 - .../java/com/seaofnodes/simple/node/PhiNode.java | 1 - .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - .../com/seaofnodes/simple/GlobalCodeMotion.java | 85 ++++---- .../java/com/seaofnodes/simple/node/CFGNode.java | 3 - .../java/com/seaofnodes/simple/node/CastNode.java | 1 - .../main/java/com/seaofnodes/simple/node/Node.java | 2 - .../java/com/seaofnodes/simple/node/PhiNode.java | 1 - .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - .../com/seaofnodes/simple/GlobalCodeMotion.java | 75 ++++--- .../java/com/seaofnodes/simple/node/CFGNode.java | 3 - .../java/com/seaofnodes/simple/node/CastNode.java | 1 - .../main/java/com/seaofnodes/simple/node/Node.java | 2 - .../java/com/seaofnodes/simple/node/PhiNode.java | 1 - .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - .../com/seaofnodes/simple/GlobalCodeMotion.java | 123 +++++++++--- .../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 - .../java/com/seaofnodes/simple/Chapter18Test.java | 46 +++++ .../com/seaofnodes/simple/GlobalCodeMotion.java | 123 +++++++++--- .../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 - .../java/com/seaofnodes/simple/Chapter18Test.java | 46 +++++ .../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 - .../java/com/seaofnodes/simple/Chapter18Test.java | 46 +++++ .../com/seaofnodes/simple/codegen/Encoding.java | 2 +- .../simple/codegen/GlobalCodeMotion.java | 186 ++++++++--------- .../java/com/seaofnodes/simple/node/CFGNode.java | 3 - .../java/com/seaofnodes/simple/node/CastNode.java | 1 - .../main/java/com/seaofnodes/simple/node/Node.java | 8 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 1 - .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - .../java/com/seaofnodes/simple/BrainFuckTest.java | 2 +- .../java/com/seaofnodes/simple/Chapter18Test.java | 38 ++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 4 +- .../simple/codegen/GlobalCodeMotion.java | 186 ++++++++--------- .../java/com/seaofnodes/simple/node/CFGNode.java | 3 - .../java/com/seaofnodes/simple/node/CastNode.java | 1 - .../main/java/com/seaofnodes/simple/node/Node.java | 8 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 1 - .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - .../java/com/seaofnodes/simple/Chapter18Test.java | 38 ++++ .../simple/codegen/GlobalCodeMotion.java | 186 ++++++++--------- .../java/com/seaofnodes/simple/node/CFGNode.java | 3 - .../java/com/seaofnodes/simple/node/CastNode.java | 1 - .../main/java/com/seaofnodes/simple/node/Node.java | 8 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 1 - .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - .../java/com/seaofnodes/simple/Chapter18Test.java | 38 ++++ .../simple/codegen/GlobalCodeMotion.java | 186 ++++++++--------- .../java/com/seaofnodes/simple/node/CFGNode.java | 3 - .../java/com/seaofnodes/simple/node/CastNode.java | 1 - .../main/java/com/seaofnodes/simple/node/Node.java | 8 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 1 - .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - .../java/com/seaofnodes/simple/Chapter18Test.java | 38 ++++ .../com/seaofnodes/simple/codegen/CodeGen.java | 23 --- .../simple/codegen/GlobalCodeMotion.java | 223 +++++++-------------- .../java/com/seaofnodes/simple/node/CFGNode.java | 3 - .../com/seaofnodes/simple/node/FunPtrNode.java | 1 - .../java/com/seaofnodes/simple/node/GuardNode.java | 1 - .../main/java/com/seaofnodes/simple/node/Node.java | 8 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 1 - .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - .../simple/node/cpus/x86_64_v2/TFPX86.java | 4 - .../java/com/seaofnodes/simple/Chapter18Test.java | 38 ++++ docs/chapter-backports.md | 72 ++++++- skills/chapter25-codex-notes.md | 45 +++++ 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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(); + var cons = new ArrayList(); + 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>(); + for( Node con : cons ) + for( Node use : con._outputs.asAry() ) { + if( use==null || globals.containsKey(use) ) continue; + for( int i=0; i 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 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 @@ -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 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 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 @@ -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 _outputs; + public Ary _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(); + 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(); + var seen = new java.util.IdentityHashMap(); + todo.add(n); + for( int j=0; j=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(); + 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; + for( int i=0; i 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 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 @@ -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 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 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 @@ -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 _outputs; + public Ary _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(); + 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(); + var seen = new java.util.IdentityHashMap(); + todo.add(n); + for( int j=0; j=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(); + 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() { 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(); + 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(); + var seen = new java.util.IdentityHashMap(); + todo.add(n); + for( int j=0; j=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(); + 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 @@ -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 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; iearly, 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 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(); + 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(); + var seen = new java.util.IdentityHashMap(); + todo.add(n); + for( int j=0; j=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(); + 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 @@ -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 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; iearly, 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 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(); + 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(); + var seen = new java.util.IdentityHashMap(); + todo.add(n); + for( int j=0; j=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(); + 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 @@ -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 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; iearly, 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 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(); + 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(); + var seen = new java.util.IdentityHashMap(); + todo.add(n); + for( int j=0; j=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(); + 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 @@ -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 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; iearly, 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 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(); + 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(); + var seen = new java.util.IdentityHashMap(); + todo.add(n); + for( int j=0; j=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