Fix a missed int-widening around recursion

10 files changed, 116 insertions, 6 deletions

diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
index 115f70c6..aa586b17 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
@@ -57,6 +57,16 @@ public class CallEndNode extends CFGNode implements MultiNode {
                     Type tret = in(i)._type instanceof TypeTuple rtt ? rtt.ret() : in(i)._type;
                     ret = ret.meet(tret);
                 }
+                // 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, and stay within the return type.
+                Type oldret = _type instanceof TypeTuple tt ? tt.ret() : Type.TOP;
+                if( ret instanceof TypeInteger ti && ret != oldret &&
+                    !ti.isHigh() && !ti.isConstant() &&
+                    (!(oldret instanceof TypeInteger oldi) || ti._widen <= oldi._widen) )
+                    ret = ti.same_but_slightly_wider_than(TypeInteger.BOT).join(tfp.ret());
             }
         }
         return TypeTuple.make(call._type,TypeMem.BOT,ret);
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ParmNode.java
index 95934e4b..cc654abb 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/node/ParmNode.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ParmNode.java
@@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter;
 
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
 import com.seaofnodes.simple.type.TypeMemPtr;
 
 public class ParmNode extends PhiNode {
@@ -35,6 +36,21 @@ public class ParmNode extends PhiNode {
     @Override public boolean inProgress() { return in(0) instanceof FunNode fun && fun.inProgress(); }
 
     @Override
+    public Type compute() {
+        Type t = super.compute();
+        // 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 && t != _type &&
+            !ti.isHigh() && !ti.isConstant() &&
+            (!(_type instanceof TypeInteger oldi) || ti._widen <= oldi._widen) )
+            return ti.same_but_slightly_wider_than(_minType);
+        return t;
+    }
+
+    @Override
     public Node idealize() {
         if( !(region() instanceof FunNode) )
             return in(1);       // Input has collapse to e.g. starting control.
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 6cfeecfe..7f2bb1f4 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -80,6 +80,10 @@ public class PhiNode extends Node {
         }
         Type newt = t.join( _minType );
 
+        // 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( region() instanceof LoopNode && // Only around loops
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java
index 8cd300c2..3e5dc2a9 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java
+++ b/chapter24/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],TypeInteger.BOT,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 {
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 {
diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md
index 15bf73e6..76c2f06c 100644
--- a/docs/chapter-backports.md
+++ b/docs/chapter-backports.md
@@ -7,7 +7,6 @@ live in the [AI notes](../skills/chapter25-codex-notes.md).
 ## Investigate next
 
 Establish an earlier-chapter failure before changing compiler behavior.
-The remaining candidate below is not yet confirmed.
 
 ### SCCP function revival: Chapter 24
 
@@ -24,6 +23,20 @@ Dependency propagation already exists in Chapter 24's SCCP; only port a
 specific missing dependency with a reproducer. Keep Chapter 25's escape and
 external-caller machinery out of this investigation.
 
+Investigation on 2026-10-19 found no cleanup loss. A shadow Opto checked the
+linker entry before and after every `linkCG` lookup while running all 513
+Chapter 24 tests: 787 SCCP runs, 297 lookups, 74 links to functions with only
+their null input remaining, and zero structurally dead targets or removed
+entries. All tests passed. The remaining null lookups are not evidence of a
+cleanup loss: their entries were already null before the lookup.
+
+The factorial trace shows the distinction: FunNode#1309 loses Start and has
+one input, four uses, and type TOP; it then reaches XCONTROL before a real
+call links it. `isDead()` stays false, since it requires no inputs, no uses,
+and a null type. Thus the observed temporary lack of callers does not trigger
+`link()` cleanup. Keep this candidate unconfirmed rather than backporting the
+Chapter 25 lookup change on textual differences alone.
+
 ## Deferred until the Chapter 25 split
 
 ### Deterministic inlining
diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md
index f16407e7..9b861a18 100644
--- a/skills/chapter25-codex-notes.md
+++ b/skills/chapter25-codex-notes.md
@@ -757,6 +757,13 @@ Consequences:
   widen only below-center nonconstant ranges: above-center widening can fall to
   an unwidened constant, violating SCCP monotonicity. Existing Chapter14/21 tests
   exposed this during the backport.
+- Recursion needs two widening points in Chapters 24-25: ParmNode for arguments,
+  and CallEndNode for results. The return cycle in `f(x-1)+1` never crosses the
+  Parm. Keep the comments at both sites and PhiNode cross-linked. Chapter 25's
+  FunPtrNode follows the live Return range; join that range before widening,
+  then bound widening by the callee signatures, not that live range. Apply the
+  same rule before and after linking, and retain narrow results such as i32.
+  `Chapter24Test.testRecursiveWidening` checks both cycles in both chapters.
 - TypeConAry's `_make(any,widen)` shares the backing array and returns an
   uninterned type. `xdual()` must leave interning to Type.intern's dual-pair setup;
   ordinary factories and ymeet's widening replacement intern their results.