Fix bug loop tree depth on inf loops

3 files changed, 64 insertions, 1 deletions

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