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 --- .../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 ++++++++++++++++++++++ 6 files changed, 107 insertions(+), 4 deletions(-) create mode 100644 chapter32/src/test/java/com/seaofnodes/simple/WorklistTest.java (limited to 'chapter32/src') 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