diff options
| author | Cliff Click <cliffc@acm.org> | 2026-10-02 11:20:00 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-02 11:20:00 -0700 |
| commit | d5352268a0a1355262eed78e3263c18486fb9d8a (patch) | |
| tree | f28474bb1e4333867214834e6abdeea729be68c7 | |
| parent | bd0ef17d0f9563ed9579fe060b785211e8378006 (diff) | |
| download | Simple-d5352268a0a1355262eed78e3263c18486fb9d8a.tar.gz Simple-d5352268a0a1355262eed78e3263c18486fb9d8a.zip | |
Fix bug loop tree depth on inf loops
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<n.nIns(); i++ ) - lrg=alloc.union(lrg,n.in(i)); + // TOP keeps the type merge neutral, but needs no register. + if( n.in(i)._type!=Type.TOP ) + lrg=alloc.union(lrg,n.in(i)); if( lrg._mask!=null && lrg._mask.isEmpty() ) alloc.fail(lrg); diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java index 71a96d94..849d256e 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.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.BitSet; import java.util.IdentityHashMap; @@ -235,6 +236,8 @@ abstract public class IFG { assert i!=0; def = phi.in( i ); } + // The synthetic exit carries no value on this Phi arm. + if( def._type==Type.TOP ) continue; Node def_bb = lrgs.get(lrg); if( def_bb==null ) { lrgs.put(lrg,def); @@ -451,6 +454,7 @@ abstract public class IFG { if( bias >= 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<n.nIns(); i++ ) - ld = ldepth(ld, phi.in(i), phi.region().cfg(i)); + if( phi.in(i)._type!=Type.TOP ) + ld = ldepth(ld, phi.in(i), phi.region().cfg(i)); } else { // Others check uses for( int i=1; i<n.nIns(); i++ ) @@ -421,6 +423,8 @@ public class RegAlloc { void insertBefore(Node n, int i, String kind, byte round, LRG lrg) { insertBefore(n,i,kind,round,lrg,true); } void insertBefore(Node n, int i, String kind, byte round, LRG lrg, boolean skip) { Node def = n.in(i); + // Phi splitting may visit the synthetic never-exit arm. + if( def._type==Type.TOP ) return; // Effective block for use CFGNode cfg = n instanceof PhiNode phi ? phi.region().cfg(i) : n.cfg0(); // Def is a split ? diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java index c12fc377..0e770659 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -126,7 +126,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()); @@ -135,6 +135,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/chapter20/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 5482a737..db353c1d 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter20/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/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java index b9ca9cd3..75b18cf3 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -10,6 +10,42 @@ 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).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/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<n.nIns(); i++ ) - assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); + if( n.in(i)._type==com.seaofnodes.simple.type.Type.TOP ) + assertNull(code._regAlloc.lrg(n.in(i))); + else + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); } } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index f4ce4366..2319714b 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; abstract public class BuildLRG { @@ -16,8 +17,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 ) @@ -30,7 +33,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<n.nIns(); i++ ) - lrg=alloc.union(lrg,n.in(i)); + // TOP keeps the type merge neutral, but needs no register. + if( n.in(i)._type!=Type.TOP ) + lrg=alloc.union(lrg,n.in(i)); if( lrg._mask!=null && lrg._mask.isEmpty() ) alloc.fail(lrg); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java index 546844b0..bc5fae8d 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.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.BitSet; import java.util.IdentityHashMap; @@ -241,6 +242,8 @@ abstract public class IFG { assert i!=0; def = phi.in( i ); } + // The synthetic exit carries no value on this Phi arm. + if( def._type==Type.TOP ) continue; Node def_bb = lrgs.get(lrg); if( def_bb==null ) { lrgs.put(lrg,def); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index fc60a385..6a9798b3 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter21/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.BitSet; import java.util.IdentityHashMap; @@ -336,7 +337,8 @@ public class RegAlloc { // PhiNodes check all CFG inputs if( n instanceof PhiNode phi ) { for( int i=1; i<n.nIns(); i++ ) - ld = ldepth(ld, phi.in(i), phi.region().cfg(i)); + if( phi.in(i)._type!=Type.TOP ) + ld = ldepth(ld, phi.in(i), phi.region().cfg(i)); } else { // Others check uses for( int i=1; i<n.nIns(); i++ ) @@ -453,6 +455,8 @@ public class RegAlloc { void insertBefore(Node n, int i, String kind, byte round, LRG lrg, boolean skip) { Node def = n.in(i); + // Phi splitting may visit the synthetic never-exit arm. + if( def._type==Type.TOP ) return; // Effective block for use CFGNode cfg = n instanceof PhiNode phi ? phi.region().cfg(i) : n.cfg0(); // Def is a split ? diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java index fdf09d98..47dfa311 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -132,7 +132,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()); @@ -141,6 +141,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/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java index bb82fe1a..f86d7518 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -32,7 +32,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. @@ -41,7 +41,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(); } @@ -52,7 +52,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(ScopeNode.MEM0,r,mem).init(); expr = new PhiNode(r,expr).init(); } @@ -89,7 +89,7 @@ public class LoopNode extends RegionNode { ret.setDef(1,mem ); ret.setDef(2,expr); - return stop; + return fun; } private static boolean nested(LoopTree inner, LoopTree outer) { diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java index e1e254fe..89aae28e 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter21/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/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<n.nIns(); i++ ) - assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); + if( n.in(i)._type==com.seaofnodes.simple.type.Type.TOP ) + assertNull(code._regAlloc.lrg(n.in(i))); + else + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); } } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index f4ce4366..2319714b 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; abstract public class BuildLRG { @@ -16,8 +17,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 ) @@ -30,7 +33,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<n.nIns(); i++ ) - lrg=alloc.union(lrg,n.in(i)); + // TOP keeps the type merge neutral, but needs no register. + if( n.in(i)._type!=Type.TOP ) + lrg=alloc.union(lrg,n.in(i)); if( lrg._mask!=null && lrg._mask.isEmpty() ) alloc.fail(lrg); diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java index c73f1035..89850c8c 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.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.BitSet; import java.util.IdentityHashMap; @@ -241,6 +242,8 @@ abstract public class IFG { assert i!=0; def = phi.in( i ); } + // The synthetic exit carries no value on this Phi arm. + if( def._type==Type.TOP ) continue; Node def_bb = lrgs.get(lrg); if( def_bb==null ) { lrgs.put(lrg,def); diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index ea911007..b7e105ba 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter22/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.BitSet; import java.util.IdentityHashMap; @@ -336,7 +337,8 @@ public class RegAlloc { // PhiNodes check all CFG inputs if( n instanceof PhiNode phi ) { for( int i=1; i<n.nIns(); i++ ) - ld = ldepth(ld, phi.in(i), phi.region().cfg(i)); + if( phi.in(i)._type!=Type.TOP ) + ld = ldepth(ld, phi.in(i), phi.region().cfg(i)); } else { // Others check uses for( int i=1; i<n.nIns(); i++ ) @@ -453,6 +455,8 @@ public class RegAlloc { void insertBefore(Node n, int i, String kind, byte round, LRG lrg, boolean skip) { Node def = n.in(i); + // Phi splitting may visit the synthetic never-exit arm. + if( def._type==Type.TOP ) return; // Effective block for use CFGNode cfg = n instanceof PhiNode phi ? phi.region().cfg(i) : n.cfg0(); // Use-side RegMask, if available diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java index efdb4440..4f346ee3 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -132,7 +132,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(StartNode start, StopNode stop) { // Unlink all linked calls. This can remove RPC constants which // shuffled the StartNode outputs so requires a while loop. @@ -153,6 +153,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/chapter22/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/LoopNode.java index c645968e..265132dc 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -32,7 +32,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. @@ -41,7 +41,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(); } @@ -52,7 +52,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(ScopeNode.MEM0,r,mem).init(); expr = new PhiNode(r,expr).init(); } @@ -89,7 +89,7 @@ public class LoopNode extends RegionNode { ret.setDef(1,mem ); ret.setDef(2,expr); - return stop; + return fun; } private static boolean nested(LoopTree inner, LoopTree outer) { 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<n.nIns(); i++ ) - assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); + if( n.in(i)._type==com.seaofnodes.simple.type.Type.TOP ) + assertNull(code._regAlloc.lrg(n.in(i))); + else + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); } } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index f4ce4366..2319714b 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; abstract public class BuildLRG { @@ -16,8 +17,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 ) @@ -30,7 +33,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<n.nIns(); i++ ) - lrg=alloc.union(lrg,n.in(i)); + // TOP keeps the type merge neutral, but needs no register. + if( n.in(i)._type!=Type.TOP ) + lrg=alloc.union(lrg,n.in(i)); if( lrg._mask!=null && lrg._mask.isEmpty() ) alloc.fail(lrg); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/IFG.java index ecff9aac..bcd1957d 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.Utils; import java.util.BitSet; @@ -241,6 +242,8 @@ abstract public class IFG { assert i!=0; def = phi.in( i ); } + // The synthetic exit carries no value on this Phi arm. + if( def._type==Type.TOP ) continue; Node def_bb = lrgs.get(lrg); if( def_bb==null ) { lrgs.put(lrg,def); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 793732b4..43180b64 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.Utils; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import java.util.Arrays; import java.util.BitSet; import java.util.IdentityHashMap; @@ -391,7 +392,8 @@ public class RegAlloc { // PhiNodes check all CFG inputs if( n instanceof PhiNode phi ) { for( int i=1; i<n.nIns(); i++ ) - ld = ldepth(ld, phi.in(i), phi.region().cfg(i)); + if( phi.in(i)._type!=Type.TOP ) + ld = ldepth(ld, phi.in(i), phi.region().cfg(i)); } else { // Others check uses for( int i=1; i<n.nIns(); i++ ) @@ -508,6 +510,8 @@ public class RegAlloc { void insertBefore(Node n, int i, String kind, byte round, LRG lrg, boolean skip) { Node def = n.in(i); + // Phi splitting may visit the synthetic never-exit arm. + if( def._type==Type.TOP ) return; // Effective block for use CFGNode cfg = n instanceof PhiNode phi ? phi.region().cfg(i) : n.cfg0(); // Use-side RegMask, if available diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 420c8117..6805c1ef 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -132,7 +132,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(StartNode start, StopNode stop) { // Unlink all linked calls. This can remove RPC constants which // shuffled the StartNode outputs so requires a while loop. @@ -153,6 +153,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/chapter23/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/LoopNode.java index db52c156..1d493db7 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -32,7 +32,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. @@ -41,7 +41,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(); } @@ -52,7 +52,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(ScopeNode.MEM0,r,mem).init(); expr = new PhiNode(r,expr).init(); } @@ -91,7 +91,7 @@ public class LoopNode extends RegionNode { ret._type = null; // This may LIFT the Return type, from [XCtrl,mem,expr] to [Ctrl,mem,expr] ret.setType(ret.compute()); - return stop; + return fun; } private static boolean nested(LoopTree inner, LoopTree outer) { diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 1c1d011e..91a0b700 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter23/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/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<n.nIns(); i++ ) - assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); + if( n.in(i)._type==com.seaofnodes.simple.type.Type.TOP ) + assertNull(code._regAlloc.lrg(n.in(i))); + else + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); } } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index f4ce4366..2319714b 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; abstract public class BuildLRG { @@ -16,8 +17,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 ) @@ -30,7 +33,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<n.nIns(); i++ ) - lrg=alloc.union(lrg,n.in(i)); + // TOP keeps the type merge neutral, but needs no register. + if( n.in(i)._type!=Type.TOP ) + lrg=alloc.union(lrg,n.in(i)); if( lrg._mask!=null && lrg._mask.isEmpty() ) alloc.fail(lrg); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java index ecff9aac..bcd1957d 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.Utils; import java.util.BitSet; @@ -241,6 +242,8 @@ abstract public class IFG { assert i!=0; def = phi.in( i ); } + // The synthetic exit carries no value on this Phi arm. + if( def._type==Type.TOP ) continue; Node def_bb = lrgs.get(lrg); if( def_bb==null ) { lrgs.put(lrg,def); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index b2b861e2..0899099e 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.Utils; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import java.util.Arrays; import java.util.BitSet; import java.util.IdentityHashMap; @@ -418,7 +419,8 @@ public class RegAlloc { // PhiNodes check all CFG inputs if( n instanceof PhiNode phi ) { for( int i=1; i<n.nIns(); i++ ) - ld = ldepth(ld, phi.in(i), phi.region().cfg(i)); + if( phi.in(i)._type!=Type.TOP ) + ld = ldepth(ld, phi.in(i), phi.region().cfg(i)); } else { // Others check uses for( int i=1; i<n.nIns(); i++ ) @@ -535,6 +537,8 @@ public class RegAlloc { void insertBefore(Node n, int i, String kind, byte round, LRG lrg, boolean skip) { Node def = n.in(i); + // Phi splitting may visit the synthetic never-exit arm. + if( def._type==Type.TOP ) return; // Effective block for use CFGNode cfg = n instanceof PhiNode phi ? phi.region().cfg(i) : n.cfg0(); // Use-side RegMask, if available diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 420c8117..6805c1ef 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -132,7 +132,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(StartNode start, StopNode stop) { // Unlink all linked calls. This can remove RPC constants which // shuffled the StartNode outputs so requires a while loop. @@ -153,6 +153,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/chapter24/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/LoopNode.java index db52c156..1d493db7 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -32,7 +32,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. @@ -41,7 +41,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(); } @@ -52,7 +52,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(ScopeNode.MEM0,r,mem).init(); expr = new PhiNode(r,expr).init(); } @@ -91,7 +91,7 @@ public class LoopNode extends RegionNode { ret._type = null; // This may LIFT the Return type, from [XCtrl,mem,expr] to [Ctrl,mem,expr] ret.setType(ret.compute()); - return stop; + return fun; } private static boolean nested(LoopTree inner, LoopTree outer) { diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 6e027312..02d4df6b 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter24/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/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<n.nIns(); i++ ) - assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); + if( n.in(i)._type==com.seaofnodes.simple.type.Type.TOP ) + assertNull(code._regAlloc.lrg(n.in(i))); + else + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index aa33a7ec..0b314978 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; abstract public class BuildLRG { @@ -19,10 +20,12 @@ abstract public class BuildLRG { if( bb instanceof FunNode fun2 ) fun = fun2; 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) ) { if( phi instanceof MachNode mach && mach.outregmap()==null ) continue; - // 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 ) @@ -35,7 +38,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<n.nIns(); i++ ) - lrg=alloc.union(lrg,n.in(i)); + // TOP keeps the type merge neutral, but needs no register. + if( n.in(i)._type!=Type.TOP ) + lrg=alloc.union(lrg,n.in(i)); if( lrg._mask!=null && lrg._mask.isEmpty() ) alloc.fail(lrg); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java index 8649b68c..6145910c 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.Utils; import java.util.BitSet; @@ -247,6 +248,8 @@ abstract public class IFG { assert i!=0; def = phi.in( i ); } + // The synthetic exit carries no value on this Phi arm. + if( def._type==Type.TOP ) continue; Node def_bb = lrgs.get(lrg); if( def_bb==null ) { lrgs.put(lrg,def); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 97bde2c9..756262ee 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.Utils; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import java.util.Arrays; import java.util.BitSet; import java.util.IdentityHashMap; @@ -491,7 +492,8 @@ public class RegAlloc { // PhiNodes check all CFG inputs if( n instanceof PhiNode phi ) { for( int i=1; i<n.nIns(); i++ ) - ld = ldepth(ld, phi.in(i), phi.region().cfg(i)); + if( phi.in(i)._type!=Type.TOP ) + ld = ldepth(ld, phi.in(i), phi.region().cfg(i)); } else { // Others check uses for( int i=1; i<n.nIns(); i++ ) @@ -611,6 +613,8 @@ public class RegAlloc { void insertBefore(Node n, int i, String kind, byte round, LRG lrg, boolean skip) { Node def = n.in(i); + // Phi splitting may visit the synthetic never-exit arm. + if( def._type==Type.TOP ) return; // Effective block for use CFGNode cfg = n instanceof PhiNode phi ? phi.region().cfg(i) : n.cfg0(); // Use-side RegMask, if available diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 15531c78..fe3382a6 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -197,7 +197,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( Ary<FunNode> funs, StopNode stop) { _ltree = stop._ltree = CodeGen.CODE.XCTRL._ltree = new LoopTree((StartNode)this); Ary<FunNode> 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<n.nIns(); i++ ) - assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); + if( n.in(i)._type==com.seaofnodes.simple.type.Type.TOP ) + assertNull(code._regAlloc.lrg(n.in(i))); + else + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); } } diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index ec6a727a..4b549771 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -361,15 +361,6 @@ lines beyond the original extraction. suite passes, including its current String programs. -- **Chapter 21 synthetic TOP return allocation.** The original compiler at - `f01ee052` and the memory port both fail in `Coalesce.coalesce`: a Split of - TOP has no input live range. Reproduction: `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;` - through Encoding on x86/SystemV. The new memory regression checks both - precise slices of the synthetic exit, then schedules all three targets; - allocation of its scalar TOP arm remains separate work. Do not hide the - missing live range with a null guard in coalescing. - - **Existing Chapter 18 floating-array assertion.** The unchanged `TypeStruct.makeAry` assertion accepts integers and nullable references but excludes TypeFloat; `return new flt[1];` fails under `-ea`. The Chapter 18 @@ -565,6 +556,45 @@ The top-level runner accepts explicit chapter lists, e.g. ## Validation record +- **Function loop-tree boundaries, Chapters 18-25.** Stop the post-order loop + walk at Return, seed each function's outer tree before visiting its body, and + use that tree for synthetic exit projections, return Regions and the parent + of otherwise exitless loops. In Chapter 25, walking through Return/StopCU/Stop + into Start mistook the external-world cycle for another loop: the function + entry had depth 1 while its return Region retained depth 0. Function bodies + now consistently have depth 0, with real loops adding depth. Chapters 18-20 + also assign the tree to the newly created Never and both projections. + `Chapter18Test.testNeverExitLoopDepth`, forwarded through 25, covers single, + multiple, unconditional and nested synthetic exits. The RISC-V pointer-store + reproducer `Chapter25Test.testNeverReturnPointerRiscV` now runs through + Encoding without changing the spill heuristic or eight-round limit; its + `@Ignore` is removed. Baseline failures are recorded in + `build/loop-tree18-baseline.log` and `build/loop-tree25-baseline.log`. + Full Make suites pass in `build/loop-tree-all.log`: 18 **333+1**, 19 **377+1**, + 20 **399+1**, 21 **438+1**, 22 **459+1**, 23 **481+1**, 24 **511+1**, and + 25 **403+39+9+23+1+14**, plus shared printer/ISA tests. Spill goldens remain + unchanged. + +- **Synthetic TOP returns, Chapters 20-25.** TOP remains neutral in the type + merge but has no runtime register value. BuildLRG excludes TOP definitions + and Phi inputs; IFG does not propagate TOP arms into predecessor liveness; + spilling ignores TOP for loop depth and inserts no copies for it. Chapter + 20's register-bias walk also stops when a Phi arm has no LRG. Coalesce keeps + its normal requirement that both ends of a real copy have live ranges. + `Chapter20Test.testAllocatorTopPhi` checks either Phi slot in scheduled graphs + from Chapter 20 onward. Source regressions in 21-25 (where loop repair precedes + instruction selection) cover integer, non-null pointer and floating returns, + multiple synthetic exits, no real exit, and the original two-field memory + reproducer. Existing `testNeverMemory` tests now continue through Encoding. + Full Make suites pass: 20 **398+1**, 21 **437+1**, 22 **458+1**, 23 **480+1**, + 24 **510+1**, and 25 **402+39+9+22+1+14**, plus shared printer/ISA tests. + Spill goldens were unchanged. The RISC-V pointer-store convergence test was + ignored in that run; the subsequent loop-tree correction above enables it. + Chapter 21 ARM/RISC-V execution + of the original reproducer returns 0 for `arg=0` and stays in the loop for + 10,000 instructions for `arg=1`. Logs: `build/top-ra-all.log` (20-24 and + shared modules), `build/top-ra25-final.log`, `build/top-ra-execution.log`. + - **GCM conditional-writer ordering, Chapters 21-25.** Restored the `idom()` walk from a writer's late block through its early bound, including matching memory-Phi predecessor paths. Chapters 11-20 already retained this walk. diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index c409cd55..10729bf3 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -126,8 +126,25 @@ For shared viewer work, read [the graph viewer notes](graph-viewer-codex-notes.m bank, preserving integer bits when allocated to XMM. ARM's emulator needs MOVK and full MOVZ immediate/shift support. The 91-entry spill cohort changes 840 / 1,456 to 845 / 1,559; read-before-New ordering explains most of the - RISC-V BrainFuck increase. No allocator heuristics changed. Synthetic scalar - TOP exit allocation already failed before this port; see the pending queue. + RISC-V BrainFuck increase. No allocator heuristics changed in that port. + +- Synthetic never-exit TOP values remain in the graph for neutral type merges, + but have no runtime value to allocate. Chapters 20-25 exclude TOP definitions + and Phi arms from LRG construction, Phi-input liveness and spill copies; TOP + arms also do not contribute to spill loop-depth estimates. Register-bias walks + must stop at an input with no LRG. Do not give TOP a permissive register mask: + that still creates false liveness, interference and spills. Coalescing assumes + both ends of every actual copy have LRGs; fix the creation of bogus copies, + rather than adding a null guard there. + +- From Chapter 18, stop loop-tree discovery at each Return. Seed the function's + outer tree before the post-order body walk, since `forceExit` can add a return + Region and projections before the walk reaches the function entry. Those + exits inherit the function's outer tree; Never and the backedge projection + inherit the actual loop. Function bodies are depth 0, real loops add depth. + In Chapter 25, Stop/Start and StopCU/StartCU links describe external-world + type propagation, not executable loop backedges. Walking through them created + inconsistent depths and caused the RISC-V pointer-return spill-round failure. - Chapter 21's Load search is separate from the one-step factoring guard. It creates no nodes or rewiring, but records dependencies and returns folding |