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 --- .../java/com/seaofnodes/simple/Chapter13Test.java | 4 +- .../java/com/seaofnodes/simple/SchedulingTest.java | 39 +++++++++++++++++ .../java/com/seaofnodes/simple/WorklistTest.java | 49 ++++++++++++++++++++++ 3 files changed, 91 insertions(+), 1 deletion(-) create mode 100644 chapter32/src/test/java/com/seaofnodes/simple/WorklistTest.java (limited to 'chapter32/src/test') 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