From 8b80d94ce545060c09dab9487393f64acbc3e6fe Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 15 Nov 2026 16:54:06 -0800 Subject: Bunch of unrelated speedups And some modest tracking bugs --- chapter32/README.md | 59 ++++++++++++++++++++++ .../com/seaofnodes/simple/codegen/IterPeeps.java | 12 ++++- .../java/com/seaofnodes/simple/node/IfNode.java | 4 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 3 ++ .../java/com/seaofnodes/simple/Chapter13Test.java | 4 +- .../java/com/seaofnodes/simple/SchedulingTest.java | 39 ++++++++++++++ .../java/com/seaofnodes/simple/WorklistTest.java | 49 ++++++++++++++++++ 7 files changed, 166 insertions(+), 4 deletions(-) create mode 100644 chapter32/src/test/java/com/seaofnodes/simple/WorklistTest.java diff --git a/chapter32/README.md b/chapter32/README.md index 53847ea4..4cb1d79b 100644 --- a/chapter32/README.md +++ b/chapter32/README.md @@ -162,6 +162,65 @@ also wake on use-count changes. Any narrower filter must preserve the topology and use-count changes that actually enable a rewrite; deleting subscriptions just because a sample showed no progress is not enough. +### MemPhi and IfNode follow-up + +The next trace records the notifying node as well as the enqueue stack. +BulkMemPhi splitting and MemMerge cleanup repeatedly queue precise memory Phis +as inputs of successful peepholes. Removing memory Phis also changes a Region's +users, waking IfNodes which subscribed while walking the dominator chain. +Unlinking callers produces similar notifications from CallNodes. + +Two small filters are retained. A type-only update of a user no longer queues +an already-used, stable MemPhi input. New or edited inputs and first-use Phis +remain eligible; replacement and edge-edit notifications retain their existing +behavior. `IfNode.idealize` searches dominators only when both branches remain +possible. Known branches already fold through CProj and need no new distant +subscriptions. + +On the same 794-method profiling sweep, MemPhi visits fell from 474,510 to +469,866, IfNode visits from 254,787 to 249,609, and total visits from 3,695,609 +to 3,661,560. The total reduction is 0.9%; whole-suite elapsed times of 91.88 +and 91.64 seconds do not establish a meaningful timing improvement. Existing +spill expectations still pass. One graph expectation loses a redundant integer +narrowing; both branches also have execution checks. + +A broader experiment separated dependency use-count notifications from type +and input-edge notifications, and filtered more MemPhi use-count revisits. +That version changed optimizer ordering enough to increase the Sieve spill +score from 216 to 343 and the forward-field example from 23 to 31. It is not +enabled: reducing compiler work is not a reason to silently raise code-quality +expectations. The broader filter also requires notifying a node's dependents +when `delDef` changes its inputs, rather than redundantly notifying the old +input's use-count listeners. + +In the 302-method non-chapter group, that isolated experiment reduced MemPhi +visits from 367,387 to 205,245 and IfNode visits from 144,652 to 59,185. Total +visits fell 9.7%, but elapsed time was essentially unchanged at 57.48 versus +57.75 seconds. Fewer visits alone do not demonstrate a runtime improvement. + +These measurements precede the verifier fixes below. + +### Every-step verifier fixes + +Checking every progress step exposed two bugs, both reproducible before the +MemPhi/IfNode filters: + +- `Chapter05Test.testMerge4` fails at iteration 38: replacing `Phi#44` with + `arg` changes `If#52`'s predicate and enables `Phi#75`'s guard-merge rewrite. + `matchingGuardMerge` had no dependency on that predicate comparison. It now + subscribes to the If for direct input edits and to its predicate for replacement + through `subsume`. Tests cover both notification paths. +- `Chapter15Test.testArrayLoadDominatingControl` fails at iteration 30, when a + bulk memory Phi splits into a MemMerge. The verifier treated the consuming + load's earlier range-check control as its execution block. A memory operation's + control is only a lower bound: its data inputs can force it later. The check + now includes those inputs, matching early scheduling. Regression tests accept + this legal placement and still reject a load used before its memory is ready. + +After these fixes, all 802 suite executions pass at log 8; 444 chapter tests and +34 focused worklist, scheduling, and memory tests pass at log 1. Existing spill +expectations are unchanged. + ## Build and test From `chapter32`, using the existing offline dependency caches: diff --git a/chapter32/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java b/chapter32/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java index ba6cb5d8..fe935a69 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java @@ -125,7 +125,13 @@ public class IterPeeps { // A self-returning peephole can have rewritten its input // edges. The new defs gained a user and may have // backwards, user-sensitive peepholes of their own. - for( Node z : x._inputs ) _work.push(z); + boolean edited = x!=n || x.isUnlocked(); + for( Node z : x._inputs ) + // A type-only update adds no users. A stable memory + // Phi has no backwards rewrite based on user types. + // Keep first-use and edited/unprocessed Phis queued. + if( edited || !(z instanceof MemPhiNode) || z.nOuts()<=1 || z.isUnlocked() ) + _work.push(z); // If the result is not self, revisit all inputs (because // there's a new user), and replace in the graph. if( x != n ) { @@ -237,7 +243,9 @@ public class IterPeeps { } return found; } - return CFGNode.safeCFG(use); + // A memory op can execute after its control (e.g. a range check). + // Like schedEarly, include its data inputs before constraining its defs. + return use instanceof MemOpNode ? CFGNode.earlyCFG(use,earlyCache,VISIT) : CFGNode.safeCFG(use); } private static String badSchedule(Node n, CFGNode early, CFGNode lca) { diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/IfNode.java index c83c81d0..ad8de653 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -56,7 +56,9 @@ public class IfNode extends CFGNode implements MultiNode { public Node idealize() { // Hunt up the immediate dominator tree. If we find an identical if // test on either the true or false branch, that side wins. - if( !pred()._type.isHighOrConst() ) + // Known branches fold through CProj; they need no dominator search + // or subscriptions to changes higher up the control flow. + if( _type==TypeTuple.IF_BOTH ) for( CFGNode dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) if( addDep(dom) instanceof IfNode iff && prior instanceof CProjNode prj && diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/PhiNode.java index f45c7325..7544962f 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -147,6 +147,9 @@ public class PhiNode extends Node { return null; if( !(r.in(3-nzIdx) instanceof CProjNode z && z._idx==1 && z.ctrl()==iff) ) return null; + // A rewritten predicate can make this guard match without changing the Phi inputs. + addDep(iff); + addDep(iff.pred()); // subsume wakes the replaced predicate's dependents. // Predicate was guarded? Node n = cast.in(1), tested = null; while( true ) { diff --git a/chapter32/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter32/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 70cfe25e..738a4d15 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -116,7 +116,9 @@ if (v1) { return v0.f; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("return ((Phi(Region,((.f<<32)>>32),2)<<32)>>32);", code.print()); + assertEquals("return Phi(Region,((.f<<32)>>32),2);", code.print()); + assertEquals("2",Eval2.eval(code,0)); + assertEquals("0",Eval2.eval(code,1)); } diff --git a/chapter32/src/test/java/com/seaofnodes/simple/SchedulingTest.java b/chapter32/src/test/java/com/seaofnodes/simple/SchedulingTest.java index 16e12b0f..28b84ee1 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/SchedulingTest.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/SchedulingTest.java @@ -1,8 +1,47 @@ package com.seaofnodes.simple; import org.junit.Test; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.IterPeeps; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import static org.junit.Assert.*; public class SchedulingTest { + @Test public void verifierAllowsLoadAfterMemoryMerge() { + CodeGen code = loadAfterMemoryMerge(); + assertTrue(IterPeeps.schedulableUses(code)); + } + + @Test public void verifierRejectsLoadUsedBeforeMemoryMerge() { + CodeGen code = loadAfterMemoryMerge(); + ReturnNode ret = (ReturnNode)code._stop.walk(n -> n instanceof ReturnNode ? n : null); + LoadNode load = (LoadNode)ret.expr(); + // The load may move below its check, but cannot serve a use above its memory. + ret.setDef(0,load.in(0)); + try { + IterPeeps.schedulableUses(code); + fail("A load cannot execute before its memory is available"); + } catch( AssertionError error ) { + assertTrue(error.getMessage(),error.getMessage().contains("Unschedulable data node LoadNode")); + } + } + + private static CodeGen loadAfterMemoryMerge() { + CodeGen code = new CodeGen("return arg;").parse(); + ReturnNode ret = (ReturnNode)code._stop.walk(n -> n instanceof ReturnNode ? n : null); + Node ctrl = ret.ctrl(); + IfNode iff = new IfNode(ctrl,ret.expr()).init(); + Node yes = new CProjNode(iff,0,"True").init(); + Node no = new CProjNode(iff,1,"False").init(); + RegionNode region = new RegionNode(null,null,yes,no).init(); + Node phi = new BulkMemPhiNode("mem",region,ret.mem(),ret.mem()).init(); + Node mem = new MemMergeNode(null,phi).init(); + Node load = new LoadNode(null,"[]",2,ctrl,mem,code.con(TypeMemPtr.BOT),code.con(TypeInteger.ZERO)).init(); + ret.setDef(0,region); + ret.setDef(2,load); + return code; + } @Test public void nativeFoldedLoadsWithLaterOperands() throws Exception { TestC.runSYS(""" val compare_noInline={ i64[] a, int flag -> diff --git a/chapter32/src/test/java/com/seaofnodes/simple/WorklistTest.java b/chapter32/src/test/java/com/seaofnodes/simple/WorklistTest.java new file mode 100644 index 00000000..fce15418 --- /dev/null +++ b/chapter32/src/test/java/com/seaofnodes/simple/WorklistTest.java @@ -0,0 +1,49 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import org.junit.Test; +import static org.junit.Assert.*; + +public class WorklistTest { + @Test public void testGuardMergeAfterPredicateRewrite() { guardMergeAfterPredicateRewrite(false); } + @Test public void testGuardMergeAfterPredicateSubsume() { guardMergeAfterPredicateRewrite(true); } + + private static void guardMergeAfterPredicateRewrite(boolean subsume) { + CodeGen code = new CodeGen(""); + Node ctrl = new CProjNode(code._start,0,"Ctrl").init(); + Node old = code.con(TypeInteger.BOOL), value = code.con(TypeInteger.BOT); + IfNode iff = new IfNode(ctrl,old).init(); + Node yes = new CProjNode(iff,0,"True").init(); + Node no = new CProjNode(iff,1,"False").init(); + RegionNode region = new RegionNode(null,null,yes,no).init(); + Node guard = new GuardNode(true,yes,value).init(); + PhiNode phi = new PhiNode("guard",region,guard,code.con(TypeInteger.ZERO)).init(); + phi.keep(); + code._iter._work.clear(); + assertNull(phi.idealize()); + assertFalse(code._iter._work.on(phi)); + // Neither edit changes a Phi input; its predicate dependency must wake it. + if( subsume ) old.subsume(value); + else iff.setDef(1,value); + assertTrue("Predicate rewrite must requeue the guard merge",code._iter._work.on(phi)); + assertSame(value,phi.idealize()); + phi.unkeep(); + } + @Test public void testKnownIfDoesNotSearchDominators() { + CodeGen code = new CodeGen(""); + Node ctrl = new CProjNode(code._start,0,"Ctrl").init(); + IfNode outer = new IfNode(ctrl,code.con(TypeInteger.BOOL)).init(); + Node yes = new CProjNode(outer,0,"True").init(); + // Nonconstant, but already known to be nonzero. + IfNode inner = new IfNode(yes,code.con(TypeInteger.make(1,2))).init(); + assertSame(TypeTuple.IF_TRUE,inner._type); + assertNull(inner.idealize()); + for( int i=0; i