Fix a missed int-widening around recursion

4 files changed, 51 insertions, 5 deletions

diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
index cfc58ce9..36a012e1 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
@@ -96,10 +96,18 @@ public class CallEndNode extends CFGNode implements MultiNode {
         // produce their declared return type.  A missing non-external target
         // is still an unresolved/error call.
         int externs = 0;
-        if( !XInt.isHigh(tfp.fidxs()) )
-            for( int fidx = XInt.next(tfp.fidxs(),0); fidx >= 0; fidx = XInt.next(tfp.fidxs(),fidx) )
+        // The signature bounds widening (e.g. an i32 result stays i32).
+        // Use the callee signature, not FunPtrNode's live recursive range.
+        Type bound = tfp.ret();
+        if( !XInt.isHigh(tfp.fidxs()) ) {
+            bound = Type.TOP;
+            for( int fidx = XInt.next(tfp.fidxs(),0); fidx >= 0; fidx = XInt.next(tfp.fidxs(),fidx) ) {
                 if( CodeGen.CODE.externFunc(fidx)!=null )
                     externs++;
+                FunNode fun = CodeGen.CODE._link(fidx);
+                bound = bound.meet(fun==null ? tfp.ret() : addDep(fun).sig().ret());
+            }
+        }
         boolean hasExtern = externs != 0;
 
         // If we have an error-call, e.g. wrong args, then we never link.
@@ -113,7 +121,8 @@ public class CallEndNode extends CFGNode implements MultiNode {
                            CodeGen.CODE._phase.ordinal() <  CodeGen.Phase.Lower.ordinal();
             Type tmem = opto ? TypeMem.TOP : TypeMem.BOT;
             Type ret  = opto ? Type.TOP    : tfp.ret();
-            return TypeTuple.make(Type.CONTROL,tmem,ret);
+            // Use the same widening before and after linking a callee.
+            return TypeTuple.make(Type.CONTROL,tmem,widenResult(ret,bound));
         }
 
         // A linked function for every concrete function
@@ -129,8 +138,20 @@ public class CallEndNode extends CFGNode implements MultiNode {
         // contribute class-init dependencies even though it never executes.
         if( state.ctl()==Type.XCONTROL )
             return TypeTuple.make(Type.CONTROL,TypeMem.TOP,Type.TOP);
-        // At least as good as the TFP
-        return state.makeFrom(2,state.ret().join(tfp.ret()));
+        // Join before widening: FunPtrNode follows the live Return type, so
+        // joining it afterward would undo the widening.
+        return state.makeFrom(2,widenResult(state.ret().join(tfp.ret()),bound));
+    }
+
+    private static Type widenResult(Type ret, Type bound) {
+        // Recursion is a loop in disguise. For f(x-1)+1, the result
+        // flows Return -> CallEnd -> Add -> Phi -> Return, without
+        // crossing ParmNode.compute's widening point. Widen here too,
+        // using the loop rule in PhiNode.compute. Keep constants and
+        // above-center ranges narrow.
+        if( ret instanceof TypeInteger ti && !ti.isHigh() && !ti.isConstant() )
+            ret = ti.same_but_slightly_wider_than().join(bound);
+        return ret;
     }
 
     @Override
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java
index 278c5308..91c471c0 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java
@@ -80,6 +80,13 @@ public class ParmNode extends PhiNode {
                 t = t.meet(in(i)._type);
             }
         }
+        // Recursion is a loop in disguise. A Parm merges the first argument
+        // with those from recursive calls, just as a loop Phi merges its entry
+        // and backedge. Use the widening rule in PhiNode.compute here too.
+        // CallEndNode.compute handles the separate cycle through return values;
+        // widening this Parm alone cannot stop f(x-1)+1 from growing its result.
+        if( t instanceof TypeInteger ti && !ti.isHigh() && !ti.isConstant() )
+            t = ti.same_but_slightly_wider_than();
         return t.join(_declaredType);
     }
 
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 0097c773..3cf6f854 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -80,6 +80,10 @@ public class PhiNode extends Node {
             }
         }
 
+        // Widen loop Phis so integer ranges cannot grow one step per trip forever.
+        // Recursion is a loop in disguise: ParmNode.compute widens arguments,
+        // and CallEndNode.compute widens results. Both are needed because the
+        // recursive result can feed itself without passing through a Parm.
         // Above-center ranges may still fall to unwidened constants.
         // Widen only below-center ranges to preserve monotonicity.
         if( r instanceof LoopNode && // Only around loops
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java
index 2f125ed0..2bc2ce7f 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java
+++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java
@@ -17,6 +17,20 @@ import org.junit.Test;
 import static org.junit.Assert.*;
 
 public class Chapter24Test {
+    @Test public void testRecursiveWidening() {
+        String[] srcs = {
+            // Parm(x) must widen even though the recursive result is constant.
+            "val f = { int x, int limit -> x >= limit ? 0 : f(x+1,limit); }; return f(0,arg);",
+            // The growing result has its own cycle, which never crosses Parm(x).
+            "val f = { int x -> x <= 0 ? 0 : f(x-1)+1; }; return f(3);"
+        };
+        for( int i=0; i<srcs.length; i++ )
+            for( long seed : new long[]{0,42,126} ) {
+                var code = new CodeGen(srcs[i],seed,true).driver(CodeGen.Phase.LocalSched);
+                assertEquals(i==0 ? "0" : "3",Eval2.eval(code,3));
+            }
+    }
+
     @Test public void testColdLoopSelfConflict() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coldLoopSelfConflict(); }
 
     @Test public void testPrintingDeadFunction() throws Exception {