Fix bug loop tree depth on inf loops

9 files changed, 125 insertions, 13 deletions

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)));
             }
     }