From d5352268a0a1355262eed78e3263c18486fb9d8a Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 2 Oct 2026 11:20:00 -0700 Subject: Fix bug loop tree depth on inf loops --- .../java/com/seaofnodes/simple/Chapter18Test.java | 35 ++++++++++++++++++++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 32 ++++++++++++++++++++ .../com/seaofnodes/simple/MemoryEncodingTest.java | 6 ++-- .../simple/codegen/RegAllocTestSupport.java | 27 ++++++++++++++++- 4 files changed, 96 insertions(+), 4 deletions(-) (limited to 'chapter22/src/test/java') diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 7d48db49..452f5386 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -11,6 +11,41 @@ import static org.junit.Assert.*; import static org.junit.Assert.fail; public class Chapter18Test { + @Test public void testNeverExitLoopDepth() { + String[] sources = { + "if(arg) while(1) {} return 7;", + "if(arg==1) while(1) {} if(arg==2) while(1) {} return 7;", + "while(1) {}", + "int x=0; while(arg) { if(arg==2) while(1) { x++; } x++; arg--; } return x;" + }; + for( String src : sources ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.LoopTree); + int[] nevers = {0}; + code._stop.walk(n -> { + if( n instanceof FunNode fun ) + assertEquals("Function entry is outside its loops",0,fun.loopDepth()); + if( n instanceof ReturnNode ret ) { + assertEquals(ret.fun().loopDepth(),ret.loopDepth()); + assertEquals(ret.fun().loopDepth(),ret.cfg0().loopDepth()); + } + if( n instanceof LoopNode loop && !(loop instanceof StartNode) && + loop.back() instanceof CProjNode back && back.in(0) instanceof NeverNode never ) { + nevers[0]++; + assertSame(loop,never.loop()); + assertSame(loop,back.loop()); + CProjNode exit = never.cproj(1-back._idx); + CFGNode fun = loop; + while( !(fun instanceof FunNode) ) fun=fun.idom(); + assertSame(fun.loop(),exit.loop()); + assertEquals(fun.loopDepth(),exit.loopDepth()); + assertTrue(loop.loopDepth()>fun.loopDepth()); + } + return null; + }); + assertTrue("Exercise a synthetic exit",nevers[0]>0); + } + } + @Test public void testFunctionLocalConstantChains() { String src = "val f = { int x -> x ? f(x-1)*305420988+x/305420988 : 1; }; "+ "val g = { int x -> x ? g(x-1)/305420988+x*305420988 : 1; }; "+ diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 0d46afb5..c37543e6 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -11,6 +11,38 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter20Test { + @Test public void testAllocatorTopPhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.topPhi(); } + + @Test public void testNeverReturnAllocation() { + String[] sources = { + // A real integer return merged with a synthetic exit. + "if(arg) while(1) {} return arg+1;", + // TOP must not widen a non-null pointer or constrain a float register. + "struct S { int x; }; S !s=new S; if(arg) while(1) {} return s;", + "if(arg) while(1) {} return 1.5;", + // Several synthetic exits into the same return. + "if(arg==1) while(1) {} if(arg==2) while(1) {} return arg+3;", + // No real return, including a merge of only synthetic exits. + "while(1) { arg+=1; }", + "if(arg) while(1) {} while(1) {}", + // Loop-carried memory and scalar self-conflicts exercise spilling. + "struct S { int x; int y; }; S !a=new S; if(arg) while(1) { a.x+=arg; a.y+=a.x; } return a.x+a.y;" + }; + for( String target : new String[]{"x86_64_v2","riscv","arm"} ) + for( String src : sources ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.RegAlloc,target,"SystemV"); + com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); + assertNotNull(code._stop.walk(n -> { + if( n._type!=com.seaofnodes.simple.type.Type.TOP ) return null; + assertEquals(-1,code._regAlloc.regnum(n)); + for( var use : n.outs() ) + assertFalse(use instanceof com.seaofnodes.simple.node.SplitNode); + return n; + })); + code.encode(); + } + } + @Test public void testAllocatorFixedNeighbor() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.uncoloredFixedNeighbor(); } @Test public void testNarrowStoreMasks() { diff --git a/chapter22/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java b/chapter22/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java index f20fe6f5..bae73d6e 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java @@ -143,8 +143,6 @@ public class MemoryEncodingTest { @Test public void testNeverMemory() { // A synthetic exit must retain both precise slices of a no-exit loop. - // Stop at scheduling: the existing allocator cannot coalesce TOP on - // the synthetic scalar return arm. for( String target : new String[]{"x86_64_v2","riscv","arm"} ) { CodeGen code = new CodeGen(""" struct S { int x; int y; }; @@ -162,7 +160,9 @@ public class MemoryEncodingTest { } return null; })); - code.instSelect(target,"SystemV").GCM().localSched(); + code.instSelect(target,"SystemV").GCM().localSched().regAlloc(); + RegAllocTestSupport.checkRegisters(code); + code.encode(); } } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 0c5edaa1..2d9860a6 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -128,6 +128,28 @@ public class RegAllocTestSupport { } } + public static void topPhi() { + // Either arm can be the synthetic exit. Both predecessors share a + // block here so making TOP live would conflict with the real value. + for( int slot=1; slot<=2; slot++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(A,null,null,false,code._start); + Node top = new ConstantNode(com.seaofnodes.simple.type.Type.TOP); + RegionNode region = new RegionNode(null,code._start,code._start); + PhiNode phi = new PhiNode("value",TypeInteger.BOT,region,slot==1 ? top : def,slot==2 ? top : def); + phi._type = TypeInteger.BOT; + new Op(null,A,null,false,region,phi); + code._cfg.add(region); + assertTrue(BuildLRG.run(0,alloc)); + assertNull(alloc.lrg(top)); + assertSame(alloc.lrg(def),alloc.lrg(phi)); + assertTrue(IFG.build(0,alloc)); + alloc.insertBefore(phi,slot,"test",(byte)0,alloc.lrg(phi)); + assertSame(top,phi.in(slot)); + } + } + public static void checkRegisters(CodeGen code) { assertTrue(code._regAlloc.verifyFunctionLocalEdges()); for( CFGNode bb : code._cfg ) @@ -143,7 +165,10 @@ public class RegAllocTestSupport { } if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 ) for( int i=n instanceof ParmNode ? 2 : 1; i