diff options
78 files changed, 1543 insertions, 356 deletions
diff --git a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index b431f82c..888c1a5e 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -111,24 +111,38 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final ArrayList<Node> TOUCHED = new ArrayList<>(); + private static final ArrayList<Node> PLACED = new ArrayList<>(); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( Node.UID() > LATE.length ) { + int len = Math.max(Node.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(stop,ns,late,anti); + breadth(stop,PLACED,LATE,ANTI); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + n.setDef(0,LATE[n._nid]); + for( Node n : TOUCHED ) + LATE[n._nid] = null; + TOUCHED.clear(); + PLACED.clear(); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + private static void breadth(Node stop, ArrayList<Node> placed, CFGNode[] late, int[] anti) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -153,9 +167,11 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.add(n); + // A use just finished; reconsider its inputs and waiting loads, // even when the shared memory input was already scheduled. for( Node def : n._inputs ) { @@ -172,7 +188,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, ArrayList<Node> placed, CFGNode[] late, int[] anti) { // Walk uses, gathering the LCA (Least Common Ancestor) of uses CFGNode early = (CFGNode)n.in(0); assert early != null; @@ -193,7 +209,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.add(n); late[n._nid] = best; } @@ -233,7 +249,8 @@ public abstract class GlobalCodeMotion { 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() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.mem()._outputs ) { @@ -254,6 +271,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java index 7075d526..f7be3ad8 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -194,11 +194,15 @@ public abstract class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } + public boolean isEmpty() { return _len==0; } + public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); diff --git a/chapter13/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter13/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..6acdcd52 --- /dev/null +++ b/chapter13/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + struct Box { int x; }; + Box b = new Box; + b.x = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = b.x; + b.x = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + StopNode stop = new Parser(src).parse().iterate(); + assertEquals(6L,Evaluator.evaluate(stop,0)); + assertEquals(7L,Evaluator.evaluate(stop,1)); + assertEquals(8L,Evaluator.evaluate(stop,2)); + } + } +} diff --git a/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index b431f82c..888c1a5e 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -111,24 +111,38 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final ArrayList<Node> TOUCHED = new ArrayList<>(); + private static final ArrayList<Node> PLACED = new ArrayList<>(); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( Node.UID() > LATE.length ) { + int len = Math.max(Node.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(stop,ns,late,anti); + breadth(stop,PLACED,LATE,ANTI); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + n.setDef(0,LATE[n._nid]); + for( Node n : TOUCHED ) + LATE[n._nid] = null; + TOUCHED.clear(); + PLACED.clear(); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + private static void breadth(Node stop, ArrayList<Node> placed, CFGNode[] late, int[] anti) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -153,9 +167,11 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.add(n); + // A use just finished; reconsider its inputs and waiting loads, // even when the shared memory input was already scheduled. for( Node def : n._inputs ) { @@ -172,7 +188,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, ArrayList<Node> placed, CFGNode[] late, int[] anti) { // Walk uses, gathering the LCA (Least Common Ancestor) of uses CFGNode early = (CFGNode)n.in(0); assert early != null; @@ -193,7 +209,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.add(n); late[n._nid] = best; } @@ -233,7 +249,8 @@ public abstract class GlobalCodeMotion { 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() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.mem()._outputs ) { @@ -254,6 +271,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter14/src/main/java/com/seaofnodes/simple/IterPeeps.java index 7075d526..f7be3ad8 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -194,11 +194,15 @@ public abstract class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } + public boolean isEmpty() { return _len==0; } + public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); diff --git a/chapter14/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter14/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..6acdcd52 --- /dev/null +++ b/chapter14/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + struct Box { int x; }; + Box b = new Box; + b.x = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = b.x; + b.x = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + StopNode stop = new Parser(src).parse().iterate(); + assertEquals(6L,Evaluator.evaluate(stop,0)); + assertEquals(7L,Evaluator.evaluate(stop,1)); + assertEquals(8L,Evaluator.evaluate(stop,2)); + } + } +} diff --git a/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 4c9fc779..4e836ca4 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -112,24 +112,41 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + private static final BitSet WAKE_VISIT = new BitSet(); + + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final ArrayList<Node> TOUCHED = new ArrayList<>(); + private static final ArrayList<Node> PLACED = new ArrayList<>(); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( Node.UID() > LATE.length ) { + int len = Math.max(Node.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(stop,ns,late,anti); + breadth(stop,PLACED,LATE,ANTI,WAKE_VISIT); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( Node n : TOUCHED ) + LATE[n._nid] = null; + TOUCHED.clear(); + PLACED.clear(); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + private static void breadth(Node stop, ArrayList<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -153,16 +170,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.add(n); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -170,7 +190,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, ArrayList<Node> placed, 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; @@ -192,7 +212,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.add(n); late[n._nid] = best; } @@ -232,7 +252,8 @@ public abstract class GlobalCodeMotion { 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() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -256,6 +277,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter15/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter15/src/main/java/com/seaofnodes/simple/IterPeeps.java index 7075d526..f7be3ad8 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -194,11 +194,15 @@ public abstract class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } + public boolean isEmpty() { return _len==0; } + public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); diff --git a/chapter15/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter15/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..b3984f15 --- /dev/null +++ b/chapter15/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + StopNode stop = new Parser(src).parse().iterate(); + assertEquals(6L,Evaluator.evaluate(stop,0)); + assertEquals(0L,Evaluator.evaluate(stop,1)); + assertEquals(8L,Evaluator.evaluate(stop,2)); + } + } +} diff --git a/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index e153fcc7..73c53123 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -112,24 +112,41 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + private static final BitSet WAKE_VISIT = new BitSet(); + + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final ArrayList<Node> TOUCHED = new ArrayList<>(); + private static final ArrayList<Node> PLACED = new ArrayList<>(); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( Node.UID() > LATE.length ) { + int len = Math.max(Node.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(stop,ns,late,anti); + breadth(stop,PLACED,LATE,ANTI,WAKE_VISIT); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( Node n : TOUCHED ) + LATE[n._nid] = null; + TOUCHED.clear(); + PLACED.clear(); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + private static void breadth(Node stop, ArrayList<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -153,16 +170,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.add(n); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -170,7 +190,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, ArrayList<Node> placed, 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; @@ -192,7 +212,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.add(n); late[n._nid] = best; } @@ -232,7 +252,8 @@ public abstract class GlobalCodeMotion { 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() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -256,6 +277,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter16/src/main/java/com/seaofnodes/simple/IterPeeps.java index cabc4a15..415f85e6 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -194,11 +194,15 @@ public abstract class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } + public boolean isEmpty() { return _len==0; } + public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); diff --git a/chapter16/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter16/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..b3984f15 --- /dev/null +++ b/chapter16/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + StopNode stop = new Parser(src).parse().iterate(); + assertEquals(6L,Evaluator.evaluate(stop,0)); + assertEquals(0L,Evaluator.evaluate(stop,1)); + assertEquals(8L,Evaluator.evaluate(stop,2)); + } + } +} diff --git a/chapter17a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter17a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index c6d02b27..8dc1a626 100644 --- a/chapter17a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter17a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -73,24 +73,41 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + private static final BitSet WAKE_VISIT = new BitSet(); + + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final ArrayList<Node> TOUCHED = new ArrayList<>(); + private static final ArrayList<Node> PLACED = new ArrayList<>(); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( Node.UID() > LATE.length ) { + int len = Math.max(Node.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(stop,ns,late,anti); + breadth(stop,PLACED,LATE,ANTI,WAKE_VISIT); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( Node n : TOUCHED ) + LATE[n._nid] = null; + TOUCHED.clear(); + PLACED.clear(); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + private static void breadth(Node stop, ArrayList<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -114,16 +131,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.add(n); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -131,7 +151,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, ArrayList<Node> placed, 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 +173,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.add(n); late[n._nid] = best; } @@ -193,7 +213,8 @@ public abstract class GlobalCodeMotion { 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() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -217,6 +238,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter17a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter17a/src/main/java/com/seaofnodes/simple/IterPeeps.java index 5a80698a..792fd507 100644 --- a/chapter17a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter17a/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -197,11 +197,15 @@ public abstract class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } + public boolean isEmpty() { return _len==0; } + public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); diff --git a/chapter17a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter17a/src/main/java/com/seaofnodes/simple/node/CFGNode.java index e85fc6ae..37240b18 100644 --- a/chapter17a/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter17a/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -84,9 +84,13 @@ public abstract class CFGNode extends Node { // Tag all CFG Nodes with their containing LoopNode; LoopNodes themselves // also refer to *their* containing LoopNode, as well as have their depth. // Start is a LoopNode which contains all at depth 1. + private static final BitSet POST = new BitSet(); + public void buildLoopTree(StopNode stop) { _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,stop, new BitSet()); + BitSet post = POST; + _bltWalk(2,stop, post); + post.clear(); } private int _bltWalk(int pre, StopNode stop, BitSet post) { // Pre-walked? diff --git a/chapter17a/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter17a/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..b3984f15 --- /dev/null +++ b/chapter17a/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + StopNode stop = new Parser(src).parse().iterate(); + assertEquals(6L,Evaluator.evaluate(stop,0)); + assertEquals(0L,Evaluator.evaluate(stop,1)); + assertEquals(8L,Evaluator.evaluate(stop,2)); + } + } +} diff --git a/chapter17b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter17b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index c6d02b27..8dc1a626 100644 --- a/chapter17b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter17b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -73,24 +73,41 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + private static final BitSet WAKE_VISIT = new BitSet(); + + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final ArrayList<Node> TOUCHED = new ArrayList<>(); + private static final ArrayList<Node> PLACED = new ArrayList<>(); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( Node.UID() > LATE.length ) { + int len = Math.max(Node.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(stop,ns,late,anti); + breadth(stop,PLACED,LATE,ANTI,WAKE_VISIT); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( Node n : TOUCHED ) + LATE[n._nid] = null; + TOUCHED.clear(); + PLACED.clear(); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + private static void breadth(Node stop, ArrayList<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -114,16 +131,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.add(n); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -131,7 +151,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, ArrayList<Node> placed, 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 +173,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.add(n); late[n._nid] = best; } @@ -193,7 +213,8 @@ public abstract class GlobalCodeMotion { 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() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -217,6 +238,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter17b/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter17b/src/main/java/com/seaofnodes/simple/IterPeeps.java index 5a80698a..792fd507 100644 --- a/chapter17b/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter17b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -197,11 +197,15 @@ public abstract class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } + public boolean isEmpty() { return _len==0; } + public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); diff --git a/chapter17b/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter17b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index e85fc6ae..37240b18 100644 --- a/chapter17b/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter17b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -84,9 +84,13 @@ public abstract class CFGNode extends Node { // Tag all CFG Nodes with their containing LoopNode; LoopNodes themselves // also refer to *their* containing LoopNode, as well as have their depth. // Start is a LoopNode which contains all at depth 1. + private static final BitSet POST = new BitSet(); + public void buildLoopTree(StopNode stop) { _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,stop, new BitSet()); + BitSet post = POST; + _bltWalk(2,stop, post); + post.clear(); } private int _bltWalk(int pre, StopNode stop, BitSet post) { // Pre-walked? diff --git a/chapter17b/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter17b/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..91e00906 --- /dev/null +++ b/chapter17b/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + StopNode stop = new Parser(src).parse().iterate(); + assertEquals(6L,Evaluator.evaluate(stop,0)); + assertEquals(0L,Evaluator.evaluate(stop,1)); + assertEquals(8L,Evaluator.evaluate(stop,2)); + } + } +} diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 2019b714..2a1ca2f5 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -125,24 +125,41 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + private static final BitSet WAKE_VISIT = new BitSet(); + + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final ArrayList<Node> TOUCHED = new ArrayList<>(); + private static final ArrayList<Node> PLACED = new ArrayList<>(); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( Node.UID() > LATE.length ) { + int len = Math.max(Node.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(stop,ns,late,anti); + breadth(stop,PLACED,LATE,ANTI,WAKE_VISIT); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( Node n : TOUCHED ) + LATE[n._nid] = null; + TOUCHED.clear(); + PLACED.clear(); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + private static void breadth(Node stop, ArrayList<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -166,16 +183,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.add(n); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -183,7 +203,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, ArrayList<Node> placed, 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; @@ -205,7 +225,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.add(n); late[n._nid] = best; } @@ -246,7 +266,8 @@ public abstract class GlobalCodeMotion { 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() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -274,6 +295,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java index 1792dada..46bdd4e1 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -187,7 +187,7 @@ public abstract class IterPeeps { * True if Node is on the WorkList */ boolean on( E x ) { return _on.get(x._nid); } - boolean isEmpty() { return _len==0; } + public boolean isEmpty() { return _len==0; } /** * Removes a random Node from the WorkList; null if WorkList is empty @@ -197,11 +197,13 @@ public abstract class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 49398838..93c86ff6 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -100,9 +100,13 @@ public abstract class CFGNode extends Node { // Tag all CFG Nodes with their containing LoopNode; LoopNodes themselves // also refer to *their* containing LoopNode, as well as have their depth. // Start contains the function bodies at depth 0; real loops add depth. + private static final BitSet POST = new BitSet(); + public void buildLoopTree(StopNode stop) { _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,null,stop, new BitSet()); + BitSet post = POST; + _bltWalk(2,null,stop, post); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) { // Pre-walked? diff --git a/chapter18/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter18/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..3927d517 --- /dev/null +++ b/chapter18/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,29 @@ +package com.seaofnodes.simple; + +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter19/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 9454e968..0f53ce36 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -134,24 +134,40 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final ArrayList<Node> TOUCHED = new ArrayList<>(); + private static final ArrayList<Node> PLACED = new ArrayList<>(); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( code.UID() > LATE.length ) { + int len = Math.max(code.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(code._stop,ns,late,anti); + // Early scheduling has released the shared visit bits. + breadth(code._stop,PLACED,LATE,ANTI,code.visit()); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( Node n : TOUCHED ) + LATE[n._nid] = null; + TOUCHED.clear(); + PLACED.clear(); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + private static void breadth(Node stop, ArrayList<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -175,16 +191,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.add(n); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -192,7 +211,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, ArrayList<Node> placed, 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; @@ -214,7 +233,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.add(n); late[n._nid] = best; } @@ -255,7 +274,8 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -283,6 +303,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter19/src/main/java/com/seaofnodes/simple/IterPeeps.java index 087a990b..14a7cb67 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -177,7 +177,7 @@ public class IterPeeps { * True if Node is on the WorkList */ boolean on( E x ) { return _on.get(x._nid); } - boolean isEmpty() { return _len==0; } + public boolean isEmpty() { return _len==0; } /** * Removes a random Node from the WorkList; null if WorkList is empty @@ -187,11 +187,13 @@ public class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 383f18d0..d7b2f362 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -109,7 +109,9 @@ public abstract class CFGNode extends Node { // Start contains the function bodies at depth 0; real loops add depth. public void buildLoopTree(StopNode stop) { _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,null,stop, new BitSet()); + BitSet post = CodeGen.CODE.visit(); + _bltWalk(2,null,stop, post); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) { // Pre-walked? diff --git a/chapter19/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter19/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..d7173612 --- /dev/null +++ b/chapter19/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple; + +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + // A small graph after many earlier node allocations. + if( round==0 ) code._uid += 100_000; + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } +} diff --git a/chapter20/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter20/src/main/java/com/seaofnodes/simple/IterPeeps.java index a21fb517..f68d83f8 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -194,7 +194,7 @@ public class IterPeeps { * True if Node is on the WorkList */ boolean on( E x ) { return _on.get(x._nid); } - boolean isEmpty() { return _len==0; } + public boolean isEmpty() { return _len==0; } /** * Removes a random Node from the WorkList; null if WorkList is empty @@ -204,11 +204,13 @@ public class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); 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 225e5fb8..95da525b 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -137,24 +137,40 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final ArrayList<Node> TOUCHED = new ArrayList<>(); + private static final ArrayList<Node> PLACED = new ArrayList<>(); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( code.UID() > LATE.length ) { + int len = Math.max(code.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(code._stop,ns,late,anti); + // Early scheduling has released the shared visit bits. + breadth(code._stop,PLACED,LATE,ANTI,code.visit()); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( Node n : TOUCHED ) + LATE[n._nid] = null; + TOUCHED.clear(); + PLACED.clear(); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + private static void breadth(Node stop, ArrayList<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -178,16 +194,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.add(n); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -195,7 +214,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, ArrayList<Node> placed, 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; @@ -217,7 +236,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.add(n); late[n._nid] = best; } @@ -259,7 +278,8 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -287,6 +307,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 0e770659..6c708814 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -129,7 +129,9 @@ public abstract class CFGNode extends Node { // Start contains the function bodies at depth 0; real loops add depth. public void buildLoopTree(StopNode stop) { _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,null,stop, new BitSet()); + BitSet post = CodeGen.CODE.visit(); + _bltWalk(2,null,stop, post); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) { // Pre-walked? diff --git a/chapter20/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter20/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..319c94b0 --- /dev/null +++ b/chapter20/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + // A small graph after many earlier node allocations. + if( round==0 ) code._uid += 100_000; + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } +} diff --git a/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java index 7c2f1b0c..2655b423 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -196,7 +196,7 @@ public class IterPeeps { * True if Node is on the WorkList */ boolean on( E x ) { return _on.get(x._nid); } - boolean isEmpty() { return _len==0; } + public boolean isEmpty() { return _len==0; } /** * Removes a random Node from the WorkList; null if WorkList is empty @@ -206,11 +206,13 @@ public class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); 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 d4db558a..7f1e98d2 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -137,24 +137,40 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final ArrayList<Node> TOUCHED = new ArrayList<>(); + private static final ArrayList<Node> PLACED = new ArrayList<>(); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( code.UID() > LATE.length ) { + int len = Math.max(code.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(code._stop,ns,late,anti); + // Early scheduling has released the shared visit bits. + breadth(code._stop,PLACED,LATE,ANTI,code.visit()); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( Node n : TOUCHED ) + LATE[n._nid] = null; + TOUCHED.clear(); + PLACED.clear(); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + private static void breadth(Node stop, ArrayList<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -178,16 +194,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.add(n); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -195,7 +214,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, ArrayList<Node> placed, 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; @@ -218,7 +237,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.add(n); late[n._nid] = best; } @@ -260,7 +279,8 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -288,6 +308,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 47dfa311..1cf1946a 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -135,7 +135,9 @@ public abstract class CFGNode extends Node { // Start contains the function bodies at depth 0; real loops add depth. public void buildLoopTree(StopNode stop) { _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,null,stop, new BitSet()); + BitSet post = CodeGen.CODE.visit(); + _bltWalk(2,null,stop, post); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) { // Pre-walked? diff --git a/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index 97d33b70..40eb9719 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -20,7 +20,7 @@ public class BrainFuckTest { String brain_fuck = "Hello World!\n"; TestC.run("brain_fuck", brain_fuck, 40); - EvalRisc5 R5 = TestRisc5.build("brain_fuck", 0, 42, false); + EvalRisc5 R5 = TestRisc5.build("brain_fuck", 0, 114, false); int trap = R5.step(100000); assertEquals(0,trap); int ptr = (int)R5.regs[riscv.A0]; diff --git a/chapter21/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter21/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..319c94b0 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + // A small graph after many earlier node allocations. + if( round==0 ) code._uid += 100_000; + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } +} diff --git a/chapter22/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter22/src/main/java/com/seaofnodes/simple/IterPeeps.java index 7c2f1b0c..2655b423 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -196,7 +196,7 @@ public class IterPeeps { * True if Node is on the WorkList */ boolean on( E x ) { return _on.get(x._nid); } - boolean isEmpty() { return _len==0; } + public boolean isEmpty() { return _len==0; } /** * Removes a random Node from the WorkList; null if WorkList is empty @@ -206,11 +206,13 @@ public class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); 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 1818be73..dbe6e786 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -136,24 +136,40 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final ArrayList<Node> TOUCHED = new ArrayList<>(); + private static final ArrayList<Node> PLACED = new ArrayList<>(); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( code.UID() > LATE.length ) { + int len = Math.max(code.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(code._stop,ns,late,anti); + // Early scheduling has released the shared visit bits. + breadth(code._stop,PLACED,LATE,ANTI,code.visit()); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( Node n : TOUCHED ) + LATE[n._nid] = null; + TOUCHED.clear(); + PLACED.clear(); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + private static void breadth(Node stop, ArrayList<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -177,16 +193,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.add(n); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -194,7 +213,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, ArrayList<Node> placed, 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; @@ -217,7 +236,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.add(n); late[n._nid] = best; } @@ -259,7 +278,8 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -287,6 +307,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 4f346ee3..6317166e 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -147,7 +147,9 @@ public abstract class CFGNode extends Node { } _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,null,stop, new BitSet()); + BitSet post = CodeGen.CODE.visit(); + _bltWalk(2,null,stop, post); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) { // Pre-walked? diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 4bce96ab..b603f6ce 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -389,7 +389,7 @@ public class Chapter21Test { String sprimes = sb.p("]").toString(); // Compile, link against native C; expect the above string of primes to be printed out by C - TestC.run("sieve",sprimes, 185); + TestC.run("sieve",sprimes, 113); // Evaluate on RISC5 emulator; expect return of an array of primes in // the simulated heap. diff --git a/chapter22/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter22/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..319c94b0 --- /dev/null +++ b/chapter22/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + // A small graph after many earlier node allocations. + if( round==0 ) code._uid += 100_000; + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } +} diff --git a/chapter23/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter23/src/main/java/com/seaofnodes/simple/IterPeeps.java index c4b96c5c..fbbdf5e6 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -198,7 +198,7 @@ public class IterPeeps { * True if Node is on the WorkList */ boolean on( E x ) { return _on.get(x._nid); } - boolean isEmpty() { return _len==0; } + public boolean isEmpty() { return _len==0; } /** * Removes a random Node from the WorkList; null if WorkList is empty @@ -208,11 +208,13 @@ public class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); 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 da45db4f..205a5cb2 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.Utils; import java.util.*; @@ -136,24 +137,46 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final AryInt TOUCHED = new AryInt(); + private static final Ary<Node> PLACED = new Ary<>(Node.class); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( code.UID() > LATE.length ) { + int len = Math.max(code.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(code._stop,ns,late,anti); + // Early scheduling has released the shared visit bits. + breadth(code._stop,PLACED,LATE,ANTI,code.visit()); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( int i=0; i<TOUCHED.len(); i++ ) + LATE[TOUCHED.at(i)] = null; + TOUCHED.clear(); + clear(PLACED); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + // Ary.clear retains references; static scratch must release them as well. + private static void clear(Ary<Node> nodes) { + Arrays.fill(nodes._es,0,nodes._len,null); + nodes.clear(); + } + + private static void breadth(Node stop, Ary<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -177,16 +200,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.push(n._nid); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -194,7 +220,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, Ary<Node> placed, 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; @@ -217,7 +243,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.push(n); late[n._nid] = best; } @@ -259,7 +285,8 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -287,6 +314,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 6805c1ef..95aa3dc0 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -147,7 +147,9 @@ public abstract class CFGNode extends Node { } _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,null,stop, new BitSet()); + BitSet post = CodeGen.CODE.visit(); + _bltWalk(2,null,stop, post); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) { // Pre-walked? diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java index f25a881a..cfd09502 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -416,7 +416,7 @@ public class Chapter21Test { String sprimes = sb.p("]").toString(); // Compile, link against native C; expect the above string of primes to be printed out by C - TestC.run("sieve",sprimes, 186); + TestC.run("sieve",sprimes, 113); // Evaluate on RISC5 emulator; expect return of an array of primes in // the simulated heap. diff --git a/chapter23/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter23/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..319c94b0 --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + // A small graph after many earlier node allocations. + if( round==0 ) code._uid += 100_000; + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } +} diff --git a/chapter24a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter24a/src/main/java/com/seaofnodes/simple/IterPeeps.java index a3b66e09..66afe451 100644 --- a/chapter24a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter24a/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -206,7 +206,7 @@ public class IterPeeps { * True if Node is on the WorkList */ public boolean on( E x ) { return _on.get(x._nid); } - boolean isEmpty() { return _len==0; } + public boolean isEmpty() { return _len==0; } /** * Removes a random Node from the WorkList; null if WorkList is empty @@ -216,11 +216,13 @@ public class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); diff --git a/chapter24a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter24a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index da45db4f..205a5cb2 100644 --- a/chapter24a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter24a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.Utils; import java.util.*; @@ -136,24 +137,46 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final AryInt TOUCHED = new AryInt(); + private static final Ary<Node> PLACED = new Ary<>(Node.class); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( code.UID() > LATE.length ) { + int len = Math.max(code.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(code._stop,ns,late,anti); + // Early scheduling has released the shared visit bits. + breadth(code._stop,PLACED,LATE,ANTI,code.visit()); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( int i=0; i<TOUCHED.len(); i++ ) + LATE[TOUCHED.at(i)] = null; + TOUCHED.clear(); + clear(PLACED); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + // Ary.clear retains references; static scratch must release them as well. + private static void clear(Ary<Node> nodes) { + Arrays.fill(nodes._es,0,nodes._len,null); + nodes.clear(); + } + + private static void breadth(Node stop, Ary<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -177,16 +200,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.push(n._nid); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -194,7 +220,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, Ary<Node> placed, 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; @@ -217,7 +243,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.push(n); late[n._nid] = best; } @@ -259,7 +285,8 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -287,6 +314,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter24a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter24a/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 6805c1ef..95aa3dc0 100644 --- a/chapter24a/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter24a/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -147,7 +147,9 @@ public abstract class CFGNode extends Node { } _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,null,stop, new BitSet()); + BitSet post = CodeGen.CODE.visit(); + _bltWalk(2,null,stop, post); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) { // Pre-walked? diff --git a/chapter24a/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter24a/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..319c94b0 --- /dev/null +++ b/chapter24a/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + // A small graph after many earlier node allocations. + if( round==0 ) code._uid += 100_000; + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } +} diff --git a/chapter24b/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter24b/src/main/java/com/seaofnodes/simple/IterPeeps.java index a3b66e09..66afe451 100644 --- a/chapter24b/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter24b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -206,7 +206,7 @@ public class IterPeeps { * True if Node is on the WorkList */ public boolean on( E x ) { return _on.get(x._nid); } - boolean isEmpty() { return _len==0; } + public boolean isEmpty() { return _len==0; } /** * Removes a random Node from the WorkList; null if WorkList is empty @@ -216,11 +216,13 @@ public class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); diff --git a/chapter24b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter24b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index da45db4f..205a5cb2 100644 --- a/chapter24b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter24b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.Utils; import java.util.*; @@ -136,24 +137,46 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final AryInt TOUCHED = new AryInt(); + private static final Ary<Node> PLACED = new Ary<>(Node.class); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( code.UID() > LATE.length ) { + int len = Math.max(code.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(code._stop,ns,late,anti); + // Early scheduling has released the shared visit bits. + breadth(code._stop,PLACED,LATE,ANTI,code.visit()); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( int i=0; i<TOUCHED.len(); i++ ) + LATE[TOUCHED.at(i)] = null; + TOUCHED.clear(); + clear(PLACED); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + // Ary.clear retains references; static scratch must release them as well. + private static void clear(Ary<Node> nodes) { + Arrays.fill(nodes._es,0,nodes._len,null); + nodes.clear(); + } + + private static void breadth(Node stop, Ary<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -177,16 +200,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.push(n._nid); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -194,7 +220,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, Ary<Node> placed, 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; @@ -217,7 +243,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.push(n); late[n._nid] = best; } @@ -259,7 +285,8 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -287,6 +314,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter24b/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter24b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 6805c1ef..95aa3dc0 100644 --- a/chapter24b/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter24b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -147,7 +147,9 @@ public abstract class CFGNode extends Node { } _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,null,stop, new BitSet()); + BitSet post = CodeGen.CODE.visit(); + _bltWalk(2,null,stop, post); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) { // Pre-walked? diff --git a/chapter24b/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter24b/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..319c94b0 --- /dev/null +++ b/chapter24b/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + // A small graph after many earlier node allocations. + if( round==0 ) code._uid += 100_000; + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } +} diff --git a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java index 2fe4e172..66afe451 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -216,11 +216,13 @@ public class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index da45db4f..205a5cb2 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.Utils; import java.util.*; @@ -136,24 +137,46 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final AryInt TOUCHED = new AryInt(); + private static final Ary<Node> PLACED = new Ary<>(Node.class); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( code.UID() > LATE.length ) { + int len = Math.max(code.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(code._stop,ns,late,anti); + // Early scheduling has released the shared visit bits. + breadth(code._stop,PLACED,LATE,ANTI,code.visit()); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( int i=0; i<TOUCHED.len(); i++ ) + LATE[TOUCHED.at(i)] = null; + TOUCHED.clear(); + clear(PLACED); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + // Ary.clear retains references; static scratch must release them as well. + private static void clear(Ary<Node> nodes) { + Arrays.fill(nodes._es,0,nodes._len,null); + nodes.clear(); + } + + private static void breadth(Node stop, Ary<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -177,16 +200,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.push(n._nid); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -194,7 +220,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, Ary<Node> placed, 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; @@ -217,7 +243,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.push(n); late[n._nid] = best; } @@ -259,7 +285,8 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -287,6 +314,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 6805c1ef..95aa3dc0 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -147,7 +147,9 @@ public abstract class CFGNode extends Node { } _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,null,stop, new BitSet()); + BitSet post = CodeGen.CODE.visit(); + _bltWalk(2,null,stop, post); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) { // Pre-walked? diff --git a/chapter25/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter25/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..319c94b0 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + // A small graph after many earlier node allocations. + if( round==0 ) code._uid += 100_000; + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } +} diff --git a/chapter26/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter26/src/main/java/com/seaofnodes/simple/IterPeeps.java index 2fe4e172..66afe451 100644 --- a/chapter26/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter26/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -216,11 +216,13 @@ public class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); diff --git a/chapter26/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter26/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 9be662e8..d4a1966d 100644 --- a/chapter26/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter26/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.Utils; import java.util.*; @@ -136,24 +137,46 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final AryInt TOUCHED = new AryInt(); + private static final Ary<Node> PLACED = new Ary<>(Node.class); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( code.UID() > LATE.length ) { + int len = Math.max(code.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(code._stop,ns,late,anti); + // Early scheduling has released the shared visit bits. + breadth(code._stop,PLACED,LATE,ANTI,code.visit()); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( int i=0; i<TOUCHED.len(); i++ ) + LATE[TOUCHED.at(i)] = null; + TOUCHED.clear(); + clear(PLACED); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + // Ary.clear retains references; static scratch must release them as well. + private static void clear(Ary<Node> nodes) { + Arrays.fill(nodes._es,0,nodes._len,null); + nodes.clear(); + } + + private static void breadth(Node stop, Ary<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -177,16 +200,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.push(n._nid); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -194,7 +220,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, Ary<Node> placed, 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; @@ -217,7 +243,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.push(n); late[n._nid] = best; } @@ -259,7 +285,8 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -287,6 +314,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter26/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter26/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 6805c1ef..95aa3dc0 100644 --- a/chapter26/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter26/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -147,7 +147,9 @@ public abstract class CFGNode extends Node { } _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,null,stop, new BitSet()); + BitSet post = CodeGen.CODE.visit(); + _bltWalk(2,null,stop, post); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) { // Pre-walked? diff --git a/chapter26/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter26/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..319c94b0 --- /dev/null +++ b/chapter26/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + // A small graph after many earlier node allocations. + if( round==0 ) code._uid += 100_000; + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } +} diff --git a/chapter27/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter27/src/main/java/com/seaofnodes/simple/IterPeeps.java index 2fe4e172..66afe451 100644 --- a/chapter27/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter27/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -216,11 +216,13 @@ public class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public void clear() { + Arrays.fill(_es,0,_len,null); _len = 0; _on.clear(); _R.setSeed(_seed); diff --git a/chapter27/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter27/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 9be662e8..d4a1966d 100644 --- a/chapter27/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter27/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.Utils; import java.util.*; @@ -136,24 +137,46 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final AryInt TOUCHED = new AryInt(); + private static final Ary<Node> PLACED = new Ary<>(Node.class); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( code.UID() > LATE.length ) { + int len = Math.max(code.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(code._stop,ns,late,anti); + // Early scheduling has released the shared visit bits. + breadth(code._stop,PLACED,LATE,ANTI,code.visit()); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( int i=0; i<TOUCHED.len(); i++ ) + LATE[TOUCHED.at(i)] = null; + TOUCHED.clear(); + clear(PLACED); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { + // Ary.clear retains references; static scratch must release them as well. + private static void clear(Ary<Node> nodes) { + Arrays.fill(nodes._es,0,nodes._len,null); + nodes.clear(); + } + + private static void breadth(Node stop, Ary<Node> placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -177,16 +200,19 @@ public abstract class GlobalCodeMotion { continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,placed,late,anti); } + TOUCHED.push(n._nid); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -194,7 +220,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, Ary<Node> placed, 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; @@ -217,7 +243,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.push(n); late[n._nid] = best; } @@ -259,7 +285,8 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -287,6 +314,9 @@ public abstract class GlobalCodeMotion { default: throw Utils.TODO(); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter27/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter27/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 6805c1ef..95aa3dc0 100644 --- a/chapter27/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter27/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -147,7 +147,9 @@ public abstract class CFGNode extends Node { } _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,null,stop, new BitSet()); + BitSet post = CodeGen.CODE.visit(); + _bltWalk(2,null,stop, post); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) { // Pre-walked? diff --git a/chapter27/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter27/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..319c94b0 --- /dev/null +++ b/chapter27/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + // A small graph after many earlier node allocations. + if( round==0 ) code._uid += 100_000; + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } +} diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter28a/src/main/java/com/seaofnodes/simple/IterPeeps.java index e65ef6d9..39230eb2 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -333,17 +333,18 @@ public class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public boolean isEmpty() { return _len==0; } - //Node[] asAry() { return Arrays.copyOf(_es,_len); } - //public void clear() { - // _len = 0; - // _on.clear(); - // _R.setSeed(_seed); - // _totalWork = 0; - //} + public void clear() { + Arrays.fill(_es,0,_len,null); + _len = 0; + _on.clear(); + _R.setSeed(_seed); + _totalWork = 0; + } } } diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter28a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 4477025b..ba3743e3 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.Utils; import java.util.*; @@ -136,25 +137,53 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between schedules, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final AryInt TOUCHED = new AryInt(); + private static final Ary<Node> PLACED = new Ary<>(Node.class); + private static final Ary<Node> ANTIDEPS = new Ary<>(Node.class); + private static final WorkList<Node> WORK = new WorkList<>(); + 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()]; - Ary<Node> antideps = new Ary<>(Node.class); + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( code.UID() > LATE.length ) { + int len = Math.max(code.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(code._stop,ns,late,anti, antideps); + // Early scheduling has released the shared visit bits. + breadth(code._stop,PLACED,LATE,ANTI,ANTIDEPS,code.visit()); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( int i=0; i<TOUCHED.len(); i++ ) + LATE[TOUCHED.at(i)] = null; + TOUCHED.clear(); + clear(PLACED); + clear(ANTIDEPS); + } + + // Ary.clear retains references; static scratch must release them as well. + private static void clear(Ary<Node> nodes) { + Arrays.fill(nodes._es,0,nodes._len,null); + nodes.clear(); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti, Ary<Node> antideps) { + private static Ary<Node> antiDeps(MemOpNode load, Ary<Node> antideps) { + clear(antideps); + return load.antiDeps(antideps); + } + + private static void breadth(Node stop, Ary<Node> placed, CFGNode[] late, int[] anti, Ary<Node> antideps, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -173,21 +202,24 @@ public abstract class GlobalCodeMotion { // Loads need their memory inputs' uses also done if( n instanceof MemOpNode ld && ld._isLoad ) - for( Node memuse : ld.antiDeps(antideps) ) + for( Node memuse : antiDeps(ld,antideps) ) if( late[memuse._nid]==null ) continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti,antideps); + _doSchedLate(n,placed,late,anti,antideps); } + TOUCHED.push(n._nid); + // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -195,7 +227,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti, Ary<Node> antideps) { + private static void _doSchedLate(Node n, Ary<Node> placed, CFGNode[] late, int[] anti, Ary<Node> antideps) { // 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; @@ -217,7 +249,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.push(n); late[n._nid] = best; } @@ -260,10 +292,11 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti, Ary<Node> antideps) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; cfg!=early.idom(); cfg = cfg.idom() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep - for( Node mem : load.antiDeps(antideps) ) { + for( Node mem : antiDeps(load,antideps) ) { if( mem instanceof PhiNode phi ) { // Inputs carrying different memory might overwrite this alias. // Raise the LCA for those paths; the unchanged-memory paths @@ -279,6 +312,9 @@ public abstract class GlobalCodeMotion { lca = anti_dep(load,late[mem._nid],mem.cfg0(),lca,mem,anti); } } + // Release this load's marks before another compilation reuses IDs. + for( CFGNode cfg = marked; cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 4f225fbe..e07b241b 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -203,7 +203,7 @@ public abstract class CFGNode extends Node { _ltree = stop._ltree = CodeGen.CODE.XCTRL._ltree = new LoopTree((StartNode)this); Ary<FunNode> work = new Ary<>(FunNode.class); - BitSet post = new BitSet(); + BitSet post = CodeGen.CODE.visit(); int pre = 1; _pre = pre++; for( FunNode fun : funs ) { @@ -219,6 +219,7 @@ public abstract class CFGNode extends Node { for( int i=0; i<work._len; i++ ) pre = work.at(i)._bltWalk(pre,work.at(i),stop, post, work); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post, Ary<FunNode> work ) { diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java b/chapter28a/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java new file mode 100644 index 00000000..319c94b0 --- /dev/null +++ b/chapter28a/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; + +public class SchedulingScratchTest { + @Test public void testScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + int i = 0; + while( i<5 ) { + int old = xs[arg&1]; + xs[0] = i; + sum = sum + old; + i = i + 1; + } + return sum; + """; + // Each fresh compilation reuses node IDs and the scheduler's scratch. + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + // A small graph after many earlier node allocations. + if( round==0 ) code._uid += 100_000; + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } +} diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java index 42e6695e..a018c3ee 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -334,17 +334,18 @@ public class IterPeeps { int idx = _R.nextInt(_len); E x = (E)_es[idx]; _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; _on.clear(x._nid); return x; } public boolean isEmpty() { return _len==0; } - //Node[] asAry() { return Arrays.copyOf(_es,_len); } - //public void clear() { - // _len = 0; - // _on.clear(); - // _R.setSeed(_seed); - // _totalWork = 0; - //} + public void clear() { + Arrays.fill(_es,0,_len,null); + _len = 0; + _on.clear(); + _R.setSeed(_seed); + _totalWork = 0; + } } } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 42999894..a1ac4e67 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.Utils; import java.util.*; @@ -152,25 +153,53 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Scheduling is not recursive. Retain scratch capacity between objects, + // but release graph references and reset only the entries we used. + private static CFGNode[] LATE = new CFGNode[1]; + // Load NIDs at their CFG block choices, checked against Store blocks. + private static int[] ANTI = new int[1]; + private static final AryInt TOUCHED = new AryInt(); + private static final Ary<Node> PLACED = new Ary<>(Node.class); + private static final Ary<Node> ANTIDEPS = new Ary<>(Node.class); + private static final WorkList<Node> WORK = new WorkList<>(); + private static void schedLate( CodeGen code, StopNode stop ) { - 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()]; - Ary<Node> antideps = new Ary<>(Node.class); + assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); + if( code.UID() > LATE.length ) { + int len = Math.max(code.UID(),LATE.length<<1); + LATE = new CFGNode[len]; + ANTI = new int[len]; + } + WORK.clear(); // Breadth-first scheduling - breadth(stop,ns,late,anti, antideps); + // Early scheduling has released the shared visit bits. + breadth(stop,PLACED,LATE,ANTI,ANTIDEPS,code.visit()); // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); + for( Node n : PLACED ) + if( !(n instanceof ProjNode) ) + n.setDef(0,LATE[n._nid]); + for( int i=0; i<TOUCHED.len(); i++ ) + LATE[TOUCHED.at(i)] = null; + TOUCHED.clear(); + clear(PLACED); + clear(ANTIDEPS); + } + + // Ary.clear retains references; static scratch must release them as well. + private static void clear(Ary<Node> nodes) { + Arrays.fill(nodes._es,0,nodes._len,null); + nodes.clear(); + } + + private static Ary<Node> antiDeps(MemOpNode load, Ary<Node> antideps) { + clear(antideps); + return load.antiDeps(antideps); } - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti, Ary<Node> antideps) { + private static void breadth(Node stop, Ary<Node> placed, CFGNode[] late, int[] anti, Ary<Node> antideps, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); + WorkList<Node> work = WORK; work.push(stop); Node n; outer: @@ -189,21 +218,23 @@ public abstract class GlobalCodeMotion { // Loads need their memory inputs' uses also done if( n instanceof MemOpNode ld && ld._isLoad ) - for( Node memuse : ld.antiDeps(antideps) ) + for( Node memuse : antiDeps(ld,antideps) ) if( late[memuse._nid]==null ) continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti,antideps); + _doSchedLate(n,placed,late,anti,antideps); } + TOUCHED.push(n._nid); // 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); - wakeLoads(def,late,work,new BitSet()); + wakeLoads(def,late,work,visit); } + visit.clear(); if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) if( phi instanceof PhiNode && late[phi._nid]==null ) @@ -211,7 +242,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti, Ary<Node> antideps) { + private static void _doSchedLate(Node n, Ary<Node> placed, CFGNode[] late, int[] anti, Ary<Node> antideps) { // 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; @@ -233,7 +264,7 @@ public abstract class GlobalCodeMotion { if( better(lca,best) ) best = lca; assert !(best instanceof IfNode); - ns [n._nid] = n; + placed.push(n); late[n._nid] = best; } @@ -276,10 +307,11 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti, Ary<Node> antideps) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; cfg!=early.idom(); cfg = cfg.idom() ) + CFGNode marked = lca; + for( CFGNode cfg = marked; cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep - for( Node mem : load.antiDeps(antideps) ) { + for( Node mem : antiDeps(load,antideps) ) { if( mem instanceof PhiNode phi ) { // Inputs carrying different memory might overwrite this alias. // Raise the LCA for those paths; the unchanged-memory paths @@ -295,6 +327,10 @@ public abstract class GlobalCodeMotion { lca = anti_dep(load,late[mem._nid],mem.cfg0(),lca,mem,anti); } } + // This load's marks are no longer needed; leave scratch clean even + // when the next compilation reuses these node IDs. + for( CFGNode cfg = marked; cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = 0; return lca; } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/IFG.java index bcdb14bf..d15e66da 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -172,6 +172,16 @@ abstract public class IFG { // Check use-side for self-conflict; if so we MUST split selfConflict(alloc,def,lrg1); + // All operands are live together, regardless of their input order. + TMP.put(lrg1,def); + } + + // Check fixed-register uses after gathering every operand. An indirect + // call's target comes after its arguments, but must also avoid their + // fixed registers (and may need to move from its incoming register). + for( int i=1; i<n.nIns(); i++ ) { + Node def = n.in(i); + if( def==null || alloc.lrg(def)==null ) continue; // Look for a must-use single register conflicting with some other must-def. if( n instanceof MachNode m ) { RegMask ni_mask = m.regmap(i); @@ -190,10 +200,6 @@ abstract public class IFG { } } } - - // All inputs live - except in self conflicts, where we keep the prior def alive - // until it goes. - TMP.put(lrg1,def); } } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 2e8c3ff9..cb406e5b 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -203,7 +203,7 @@ public abstract class CFGNode extends Node { _ltree = stop._ltree = CodeGen.CODE.XCTRL._ltree = new LoopTree((StartNode)this); Ary<FunNode> work = new Ary<>(FunNode.class); - BitSet post = new BitSet(); + BitSet post = CodeGen.CODE.visit(); int pre = 1; _pre = pre++; for( FunNode fun : funs ) { @@ -221,6 +221,7 @@ public abstract class CFGNode extends Node { for( int i=0; i<work._len; i++ ) pre = work.at(i)._bltWalk(pre,work.at(i),stop, post, work); + post.clear(); } int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post, Ary<FunNode> work ) { diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/PhaseTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/PhaseTest.java index ee262d6c..f2d09c7c 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/PhaseTest.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/PhaseTest.java @@ -42,6 +42,29 @@ public class PhaseTest { } } + @Test public void testSchedulingScratchAcrossCompilations() { + String src = """ + int[] !xs = new int[2]; + xs[0] = arg; + int sum = 0; + for( int i=0; i<5; i++ ) { + int old = xs[arg&1]; + xs[0] = i; + sum += old; + } + return sum; + """; + for( int round=0; round<3; round++ ) { + CodeGen code = new CodeGen(src).driver(Phase.TypeCheck); + // A small graph after many earlier node allocations, then fresh + // compilations which reuse its IDs and scheduling scratch. + if( round==0 ) code._uid += 100_000; + assertEquals("6",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); + assertEquals("8",Eval2.eval(code,2)); + } + } + @Test public void testExplicitSerializationAndMemoryExport() { CodeGen code = new CodeGen(SRC).driver(Phase.Serialize); assertNotNull(code._serial); diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java index d56d5c89..fa14fc2c 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java @@ -134,7 +134,10 @@ public class SelectiveLoadingTest { @Test public void testUnknownCallbackEncoding() { for( String cpu : new String[]{"x86_64_v2","arm","riscv"} ) - new CodeGen("val apply = { {int->int} f,int n -> f(n); };") + new CodeGen(""" + val apply = { {int->int} f,int n -> f(n); }; + val apply_noInline = { {int->int} f,int n -> f(n); }; + """) .driver(CodeGen.Phase.Encoding,cpu,"SystemV"); } diff --git a/docs/roadmap.md b/docs/roadmap.md index ae450d82..88f35654 100644 --- a/docs/roadmap.md +++ b/docs/roadmap.md @@ -13,9 +13,10 @@ design decisions and chapter boundaries. Remaining work: -- Remove Eval2 scheduling scratch costs proportional to all previously - allocated node IDs. Scheduling a newly loaded object should cost only for - that graph and any affected existing nodes. +- Review the remaining node-ID bitset costs in Eval2 scheduling. Scratch + arrays now retain capacity and reset only touched entries, but bitsets + still span previously allocated node IDs. Scheduling a newly loaded + object should cost only for that graph and any affected existing nodes. - Reduce repeated scans of all calls and unloaded function summaries in `StopCUNode.compute()`. Review its phase-dependent escape normalization and reliance on the previous result before changing propagation. |