From 3df967056bf48bd9f87900f3a1ad9af2aedce948 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 28 Oct 2026 16:14:30 -0700 Subject: Backport some minor speedups --- .../main/java/com/seaofnodes/simple/IterPeeps.java | 4 +- .../simple/codegen/GlobalCodeMotion.java | 62 ++++++++++++++++------ .../java/com/seaofnodes/simple/node/CFGNode.java | 4 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 2 +- .../seaofnodes/simple/SchedulingScratchTest.java | 32 +++++++++++ 5 files changed, 85 insertions(+), 19 deletions(-) create mode 100644 chapter23/src/test/java/com/seaofnodes/simple/SchedulingScratchTest.java (limited to 'chapter23') 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 PLACED = new Ary<>(Node.class); + private static final WorkList 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 nodes) { + Arrays.fill(nodes._es,0,nodes._len,null); + nodes.clear(); + } + + private static void breadth(Node stop, Ary placed, CFGNode[] late, int[] anti, BitSet visit) { // Things on the worklist have some (but perhaps not all) uses done. - WorkList work = new WorkList<>(); + WorkList 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 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)); + } + } +} -- cgit v1.2.3