Chapter 24b: SCCP Across Functionslinear-chapter24b

Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Hadházy Tamás <helsgithub15@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

3 files changed, 31 insertions, 17 deletions

diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
index 3321301b..aa586b17 100644
--- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
@@ -15,22 +15,9 @@ public class CallEndNode extends CFGNode implements MultiNode {
     private boolean _folding;
     public boolean folding() { return _folding; }
     public final TypeRPC _rpc;
-    // Pessimistic analysis may know more than the written signature. Preserve
-    // that summary when local SCCP disconnects the callee's return edges.
-    private Type _retType = Type.BOTTOM;
 
     public CallEndNode(CallNode call) { super(new Node[]{call}); _rpc = TypeRPC.constant(_nid); }
-    public CallEndNode(CallEndNode cend) { super(cend); _rpc = cend._rpc; _retType = cend._retType; }
-
-    public void freezeResult() {
-        if( _type instanceof TypeTuple tt ) {
-            unlock();
-            _retType = tt.ret();
-        }
-    }
-
-    @Override public boolean eq(Node n) { return _retType==((CallEndNode)n)._retType; }
-    @Override int hash() { return _retType.hashCode(); }
+    public CallEndNode(CallEndNode cend) { super(cend); _rpc = cend._rpc; }
 
     @Override public String label() { return "CallEnd"; }
     @Override public boolean blockHead() { return true; }
@@ -61,7 +48,7 @@ public class CallEndNode extends CFGNode implements MultiNode {
         Type ftype = addDep(call.fptr())._type;
         Type ret = ftype.isHigh() ? Type.TOP : Type.BOTTOM;
         if( ftype instanceof TypeFunPtr tfp ) {
-            ret = tfp.ret().join(_retType);
+            ret = tfp.ret();
             // Here, if I can figure out I've found *all* callers, then I can meet
             // across the linked returns and join with the function return type.
             if( 1+tfp.nfcns() == nIns() ) { // A linked function for every concrete function
@@ -70,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/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/src/main/java/com/seaofnodes/simple/node/ParmNode.java
index 95934e4b..cc654abb 100644
--- a/src/main/java/com/seaofnodes/simple/node/ParmNode.java
+++ b/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/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 953e009e..7f2bb1f4 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -81,8 +81,9 @@ public class PhiNode extends Node {
         Type newt = t.join( _minType );
 
         // Widen loop Phis so integer ranges cannot grow one step per trip forever.
-        // Calls are opaque during SCCP here. The next chapter also widens at
-        // ParmNode and CallEndNode when solving through recursive calls.
+        // 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