diff options
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. |