diff options
Diffstat (limited to 'chapter20/src')
8 files changed, 95 insertions, 8 deletions
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))); } } |