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/node/CFGNode.java | 10 ++- .../java/com/seaofnodes/simple/node/LoopNode.java | 9 ++- .../java/com/seaofnodes/simple/Chapter18Test.java | 36 +++++++++ .../java/com/seaofnodes/simple/node/CFGNode.java | 10 ++- .../java/com/seaofnodes/simple/node/LoopNode.java | 9 ++- .../java/com/seaofnodes/simple/Chapter18Test.java | 36 +++++++++ .../com/seaofnodes/simple/codegen/BuildLRG.java | 9 ++- .../java/com/seaofnodes/simple/codegen/IFG.java | 4 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 10 ++- .../java/com/seaofnodes/simple/node/LoopNode.java | 9 ++- .../java/com/seaofnodes/simple/Chapter18Test.java | 36 +++++++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 2 + .../simple/codegen/RegAllocTestSupport.java | 27 ++++++- .../com/seaofnodes/simple/codegen/BuildLRG.java | 9 ++- .../java/com/seaofnodes/simple/codegen/IFG.java | 3 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 10 ++- .../java/com/seaofnodes/simple/node/LoopNode.java | 10 +-- .../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 ++++++- .../com/seaofnodes/simple/codegen/BuildLRG.java | 9 ++- .../java/com/seaofnodes/simple/codegen/IFG.java | 3 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 10 ++- .../java/com/seaofnodes/simple/node/LoopNode.java | 10 +-- .../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 ++++++- .../com/seaofnodes/simple/codegen/BuildLRG.java | 9 ++- .../java/com/seaofnodes/simple/codegen/IFG.java | 3 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 10 ++- .../java/com/seaofnodes/simple/node/LoopNode.java | 10 +-- .../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 ++++++- .../com/seaofnodes/simple/codegen/BuildLRG.java | 9 ++- .../java/com/seaofnodes/simple/codegen/IFG.java | 3 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 10 ++- .../java/com/seaofnodes/simple/node/LoopNode.java | 10 +-- .../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 ++++++- .../com/seaofnodes/simple/codegen/BuildLRG.java | 9 ++- .../java/com/seaofnodes/simple/codegen/IFG.java | 3 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 86 +++++++++++----------- .../java/com/seaofnodes/simple/node/LoopNode.java | 10 +-- .../java/com/seaofnodes/simple/Chapter18Test.java | 35 +++++++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 32 ++++++++ .../java/com/seaofnodes/simple/Chapter25Test.java | 9 +++ .../simple/codegen/RegAllocTestSupport.java | 27 ++++++- docs/chapter-backports.md | 48 +++++++++--- skills/chapter25-codex-notes.md | 21 +++++- 61 files changed, 922 insertions(+), 129 deletions(-) diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java index ece46e80..49398838 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -99,7 +99,7 @@ public abstract class CFGNode extends Node { // ------------------------------------------------------------------------ // Tag all CFG Nodes with their containing LoopNode; LoopNodes themselves // also refer to *their* containing LoopNode, as well as have their depth. - // Start is a LoopNode which contains all at depth 1. + // Start contains the function bodies at depth 0; real loops add depth. public void buildLoopTree(StopNode stop) { _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); _bltWalk(2,null,stop, new BitSet()); @@ -108,6 +108,14 @@ public abstract class CFGNode extends Node { // Pre-walked? if( _pre!=0 ) return pre; _pre = pre++; + // Seed the function's outer tree before walking its body. Synthetic + // exits can be added before the post-order walk reaches the entry. + if( this instanceof FunNode ) _ltree = stop._ltree; + if( this instanceof ReturnNode ) { + _ltree = fun._ltree; + post.set(_nid); + return pre; // Stop/Start links describe the outside world, not a loop. + } // Pre-walk for( Node use : _outputs ) if( use instanceof CFGNode usecfg && !skip(usecfg) ) diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 097ddea7..f26df076 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -30,7 +30,7 @@ public class LoopNode extends RegionNode { // If this is an unreachable loop, it may not have an exit. If it does not // (i.e., infinite loop), force an exit to make it reachable. - public StopNode forceExit( FunNode fun, StopNode stop ) { + public FunNode forceExit( FunNode fun, StopNode stop ) { // Walk the backedge, then immediate dominator tree util we hit this // Loop again. If we ever hit a CProj from an If (as opposed to // directly on the If) we found our exit. @@ -39,7 +39,7 @@ public class LoopNode extends RegionNode { if( x instanceof CProjNode exit && exit.in(0) instanceof IfNode iff ) { CFGNode other = iff.cproj(1-exit._idx); if( other!=null && other.loopDepth() < loopDepth() ) - return stop; // Found an exit, not an infinite loop + return fun; // Found an exit, not an infinite loop } x = x.idom(); } @@ -56,6 +56,8 @@ public class LoopNode extends RegionNode { // XCtrl or a bunch of prior NeverNode exits. Node top = new ConstantNode(Type.TOP).peephole(); ReturnNode ret = fun.ret(); + iff._ltree = f._ltree = _ltree; + ret._ltree = t._ltree = fun._ltree; Node ctrl = ret.ctrl(), mem = ret.mem(), expr = ret.expr(); if( ctrl._type != Type.XCONTROL ) { // Perfect aligned exit? @@ -76,10 +78,11 @@ public class LoopNode extends RegionNode { mem = top; expr = top; } + ((CFGNode)ctrl)._ltree = fun._ltree; ret.setDef(0,ctrl); ret.setDef(1,mem ); ret.setDef(2,expr); - return stop; + return fun; } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java index d13514b5..c08bc5b2 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -9,6 +9,42 @@ import static org.junit.Assert.fail; import org.junit.Ignore; 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).parse().opto().typeCheck(); + code._start.buildLoopTree(code._stop); + 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/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java index d57c3e8c..383f18d0 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -106,7 +106,7 @@ public abstract class CFGNode extends Node { // ------------------------------------------------------------------------ // Tag all CFG Nodes with their containing LoopNode; LoopNodes themselves // also refer to *their* containing LoopNode, as well as have their depth. - // Start is a LoopNode which contains all at depth 1. + // Start contains the function bodies at depth 0; real loops add depth. public void buildLoopTree(StopNode stop) { _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); _bltWalk(2,null,stop, new BitSet()); @@ -115,6 +115,14 @@ public abstract class CFGNode extends Node { // Pre-walked? if( _pre!=0 ) return pre; _pre = pre++; + // Seed the function's outer tree before walking its body. Synthetic + // exits can be added before the post-order walk reaches the entry. + if( this instanceof FunNode ) _ltree = stop._ltree; + if( this instanceof ReturnNode ) { + _ltree = fun._ltree; + post.set(_nid); + return pre; // Stop/Start links describe the outside world, not a loop. + } // Pre-walk for( Node use : _outputs ) if( use instanceof CFGNode usecfg && !skip( usecfg ) ) diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 5482a737..db353c1d 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -31,7 +31,7 @@ public class LoopNode extends RegionNode { // If this is an unreachable loop, it may not have an exit. If it does not // (i.e., infinite loop), force an exit to make it reachable. - public StopNode forceExit( FunNode fun, StopNode stop ) { + public FunNode forceExit( FunNode fun, StopNode stop ) { // Walk the backedge, then immediate dominator tree util we hit this // Loop again. If we ever hit a CProj from an If (as opposed to // directly on the If) we found our exit. @@ -40,7 +40,7 @@ public class LoopNode extends RegionNode { if( x instanceof CProjNode exit && exit.in(0) instanceof IfNode iff ) { CFGNode other = iff.cproj(1-exit._idx); if( other!=null && other.loopDepth() < loopDepth() ) - return stop; // Found an exit, not an infinite loop + return fun; // Found an exit, not an infinite loop } x = x.idom(); } @@ -57,6 +57,8 @@ public class LoopNode extends RegionNode { // XCtrl or a bunch of prior NeverNode exits. Node top = new ConstantNode(Type.TOP).peephole(); ReturnNode ret = fun.ret(); + iff._ltree = f._ltree = _ltree; + ret._ltree = t._ltree = fun._ltree; Node ctrl = ret.ctrl(), mem = ret.mem(), expr = ret.expr(); if( ctrl._type != Type.XCONTROL ) { // Perfect aligned exit? @@ -77,10 +79,11 @@ public class LoopNode extends RegionNode { mem = top; expr = top; } + ((CFGNode)ctrl)._ltree = fun._ltree; ret.setDef(0,ctrl); ret.setDef(1,mem ); ret.setDef(2,expr); - return stop; + return fun; } } diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 81be3379..3ec63951 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -9,6 +9,42 @@ import static org.junit.Assert.fail; import org.junit.Ignore; 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).parse().opto().typeCheck(); + code._start.buildLoopTree(code._stop); + 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/chapter20/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index 2bd64c50..746a0e6a 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; abstract public class BuildLRG { @@ -17,8 +18,10 @@ abstract public class BuildLRG { public static boolean run(int round, RegAlloc alloc) { for( Node bb : alloc._code._cfg ) for( Node n : bb.outs() ) { + // A synthetic never-exit value has no runtime definition. + if( n._type==Type.TOP ) continue; if( n instanceof PhiNode phi && !(phi._type instanceof TypeMem) ) { - // All Phi inputs end up with the same LRG. + // All real Phi inputs end up with the same LRG. // Pass 1: find any pre-existing LRG, to avoid make-then-Union a LRG LRG lrg = alloc.lrg(phi); if( lrg == null ) @@ -31,7 +34,9 @@ abstract public class BuildLRG { // Pass 2: everybody uses the same LRG lrg=alloc.union(lrg,phi); for( int i=phi instanceof ParmNode ? 2 : 1; i= 0 ) return bias; // Advance def side defSplit = defSplit.in(tidx); + if( alloc.lrg(defSplit)==null ) defSplit=null; } if( useSplit != null ) { diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 84575709..420f1007 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import java.util.Arrays; import java.util.IdentityHashMap; @@ -321,7 +322,8 @@ public class RegAlloc { // PhiNodes check all CFG inputs if( n instanceof PhiNode phi ) { for( int i=1; i { + 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/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 7cdcd739..19854767 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -10,6 +10,8 @@ import static com.seaofnodes.simple.Main.PORTS; import static org.junit.Assert.*; public class Chapter20Test { + @Test public void testAllocatorTopPhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.topPhi(); } + @Test public void testAllocatorFixedNeighbor() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.uncoloredFixedNeighbor(); } @Test public void testNarrowStoreMasks() { diff --git a/chapter20/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter20/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 1b3963c5..2966cb00 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -119,6 +119,28 @@ public class RegAllocTestSupport { assertTrue(BuildLRG.run(0,new RegAlloc(code))); } + 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 ) @@ -134,7 +156,10 @@ public class RegAllocTestSupport { } if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 ) for( int i=n instanceof ParmNode ? 2 : 1; i { + 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/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 8112917e..3dc95ab9 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -9,6 +9,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/chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java b/chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java index 98e0311d..3ad7c4cb 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java @@ -142,8 +142,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; }; @@ -160,7 +158,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/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 3f624fcd..739eba3b 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -118,6 +118,28 @@ public class RegAllocTestSupport { assertTrue(BuildLRG.run(0,new RegAlloc(code))); } + 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 ) @@ -133,7 +155,10 @@ public class RegAllocTestSupport { } if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 ) for( int i=n instanceof ParmNode ? 2 : 1; i { + 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 { + 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/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 1489b9ac..8dce8629 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter23/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/chapter23/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java b/chapter23/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java index 11881194..611d8184 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java +++ b/chapter23/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/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 5b61d3b3..ad898be3 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -171,6 +171,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 ) @@ -186,7 +208,10 @@ public class RegAllocTestSupport { } if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 ) for( int i=n instanceof ParmNode ? 2 : 1; i { + 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/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 2035ef9b..937e24e6 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter24/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/chapter24/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java b/chapter24/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java index c5ad164e..e83e3c0e 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java @@ -142,8 +142,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; }; @@ -161,7 +159,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/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 0ccd9741..1ffdb3d0 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -171,6 +171,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 ) @@ -186,7 +208,10 @@ public class RegAllocTestSupport { } if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 ) for( int i=n instanceof ParmNode ? 2 : 1; i funs, StopNode stop) { _ltree = stop._ltree = CodeGen.CODE.XCTRL._ltree = new LoopTree((StartNode)this); Ary work = new Ary<>(FunNode.class); @@ -210,7 +210,7 @@ public abstract class CFGNode extends Node { work.push(fun); if(fun.in(1) instanceof StartCUNode start && start._pre==0 ) { start._pre = pre++; - start._ltree = _ltree; + start._ltree = start.cfg(1)._ltree = _ltree; post.set(start._nid); } }; @@ -224,6 +224,14 @@ public abstract class CFGNode extends Node { // Pre-walked? if( _pre!=0 ) return pre; _pre = pre++; + // Seed the function's outer tree before walking its body. Synthetic + // exits can be added before the post-order walk reaches the entry. + if( this instanceof FunNode ) _ltree = stop._ltree; + if( this instanceof ReturnNode ) { + _ltree = fun._ltree; + post.set(_nid); + return pre; // Stop/Start links describe the outside world, not a loop. + } // Pre-walk for( Node use : _outputs ) if( use instanceof CFGNode usecfg ) { @@ -233,46 +241,42 @@ public abstract class CFGNode extends Node { pre = usecfg._bltWalk( pre, use instanceof FunNode fuse ? fuse : fun, stop, post, work ); } - if( this instanceof ReturnNode ret ) { - ret._ltree = stop._ltree; - } else { - // Post-order work: find innermost loop - LoopTree inner = null, ltree; - for( Node use : _outputs ) { - if( !(use instanceof CFGNode usecfg) ) continue; - if( skip(usecfg) ) continue; - if( usecfg._type == Type.XCONTROL || // Do not walk dead control - usecfg._type == TypeTuple.IF_NEITHER ) // Nor dead IFs - continue; - // Child visited but not post-visited? - if( !post.get(usecfg._nid) ) { - // Must be a backedge to a LoopNode then - ltree = usecfg._ltree = new LoopTree((LoopNode)usecfg); - } else { - // Take child's loop choice, which must exist - ltree = usecfg._ltree; - // If falling into a loop, use the target loop's parent instead - if( ltree._head == usecfg ) { - if( ltree._par == null ) - // This loop never had an If test choose to take its - // exit, i.e. it is a no-exit infinite loop. - ltree._par = ltree._head.forceExit(fun,stop)._ltree; - ltree = ltree._par; - } - } - // Sort inner loops. The decision point is some branch far removed - // from either loop head OR either backedge so requires pre-order - // numbers to figure out innermost. - if( inner == null ) { inner = ltree; continue; } - if( inner == ltree ) continue; // No change - LoopTree outer = ltree._head._pre > inner._head._pre ? inner : ltree; - inner = ltree._head._pre > inner._head._pre ? ltree : inner; - inner._par = outer; - } - // Set selected loop - if( inner!=null ) - _ltree = inner; + // Post-order work: find innermost loop + LoopTree inner = null, ltree; + for( Node use : _outputs ) { + if( !(use instanceof CFGNode usecfg) ) continue; + if( skip(usecfg) ) continue; + if( usecfg._type == Type.XCONTROL || // Do not walk dead control + usecfg._type == TypeTuple.IF_NEITHER ) // Nor dead IFs + continue; + // Child visited but not post-visited? + if( !post.get(usecfg._nid) ) { + // Must be a backedge to a LoopNode then + ltree = usecfg._ltree = new LoopTree((LoopNode)usecfg); + } else { + // Take child's loop choice, which must exist + ltree = usecfg._ltree; + // If falling into a loop, use the target loop's parent instead + if( ltree._head == usecfg ) { + if( ltree._par == null ) + // This loop never had an If test choose to take its + // exit, i.e. it is a no-exit infinite loop. + ltree._par = ltree._head.forceExit(fun,stop)._ltree; + ltree = ltree._par; + } + } + // Sort inner loops. The decision point is some branch far removed + // from either loop head OR either backedge so requires pre-order + // numbers to figure out innermost. + if( inner == null ) { inner = ltree; continue; } + if( inner == ltree ) continue; // No change + LoopTree outer = ltree._head._pre > inner._head._pre ? inner : ltree; + inner = ltree._head._pre > inner._head._pre ? ltree : inner; + inner._par = outer; } + // Set selected loop + if( inner!=null ) + _ltree = inner; // Tag as post-walked post.set(_nid); return pre; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java index e8464353..df686bcf 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -31,7 +31,7 @@ public class LoopNode extends RegionNode { // If this is an unreachable loop, it may not have an exit. If it does not // (i.e., infinite loop), force an exit to make it reachable. - public StopNode forceExit( FunNode fun, StopNode stop ) { + public FunNode forceExit( FunNode fun, StopNode stop ) { // Walk the backedge, then immediate dominator tree util we hit this // Loop again. If we ever hit a CProj from an If (as opposed to // directly on the If) we found our exit. @@ -40,7 +40,7 @@ public class LoopNode extends RegionNode { if( x instanceof CProjNode exit && exit.in(0) instanceof IfNode iff ) { CFGNode other = iff.cproj(1-exit._idx); if( other!=null && other._ltree != _ltree && nested(_ltree,other._ltree) ) - return stop; // Found an exit, not an infinite loop + return fun; // Found an exit, not an infinite loop } x = x.idom(); } @@ -51,7 +51,7 @@ public class LoopNode extends RegionNode { setDef(2,t); // True continues loop, False (never) exits loop ReturnNode ret = fun.ret(); iff._ltree = t._ltree = _ltree; - ret._ltree = f._ltree = stop._ltree; + ret._ltree = f._ltree = fun._ltree; // Now fold control into the exit. Might have 1 valid exit, or an // XCtrl or a bunch of prior NeverNode exits. @@ -72,7 +72,7 @@ public class LoopNode extends RegionNode { expr instanceof PhiNode prez && prez.region()==r ) ) { // Nope, insert an aligned exit layer RegionNode r = new RegionNode(_loc,null,ctrl).init(); - ctrl = r; r._ltree = stop._ltree; + ctrl = r; r._ltree = fun._ltree; mem = new BulkMemPhiNode(r,mem).init(); expr = new PhiNode(r,expr).init(); } @@ -95,7 +95,7 @@ public class LoopNode extends RegionNode { CodeGen.CODE.add(CodeGen.CODE._start); CodeGen.CODE.add(mem); - return stop; + return fun; } private static boolean nested(LoopTree inner, LoopTree outer) { diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 815a035f..2c61fb44 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter25/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/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java index e39c09e7..245ea745 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -8,6 +8,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/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java index c05c13f1..cad16f2b 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java @@ -25,6 +25,15 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter25Test { + @Test public void testNeverReturnPointerRiscV() { + new CodeGen(""" + struct _S { int x; }; + _S !s = new _S; + if(arg) while(1) { s.x += arg; } + return s; + """).driver(CodeGen.Phase.Encoding,"riscv","SystemV"); + } + @Test public void testExternData() throws IOException { String src = """ diff --git a/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 873578c2..93380c87 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -175,6 +175,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",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 ) @@ -190,7 +212,10 @@ public class RegAllocTestSupport { } if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 ) for( int i=n instanceof ParmNode ? 2 : 1; i