diff options
Diffstat (limited to 'chapter22/src/main')
5 files changed, 29 insertions, 9 deletions
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) { |