Fix bug loop tree depth on inf loops

5 files changed, 31 insertions, 7 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;
     }
 }