From 8d90d2292bbdb23596849c3c3d1cda2f6cad783e Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 10 Aug 2026 11:11:18 -0700 Subject: Chapter 27: Escape Analysis and Unknown Callers 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 Co-authored-by: Claude Opus 5 --- .../java/com/seaofnodes/simple/Chapter18Test.java | 7 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 4 +- .../java/com/seaofnodes/simple/EscapeTest.java | 84 ++++++++++++++++++++++ 4 files changed, 91 insertions(+), 6 deletions(-) create mode 100644 src/test/java/com/seaofnodes/simple/EscapeTest.java (limited to 'src/test/java') diff --git a/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/src/test/java/com/seaofnodes/simple/Chapter18Test.java index a8cf3f11..732d4fa1 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -223,7 +223,8 @@ var fcn = arg ? { int x -> x*x; } : { int x -> x+x; }; return fcn(3); """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return #2; return (Parm_x($fun35,i64)*x); return (Parm_x($fun36,i64)<<1); ]", code._stop.toString()); + // Both addresses stay local, so both callees see only x=3. + assertEquals("Stop[ return #2; return 9; return 6; ]", code._stop.toString()); assertEquals("6", Eval2.eval(code, 0)); assertEquals("9", Eval2.eval(code, 1)); } @@ -283,7 +284,7 @@ for(;;) { } """); code.driver(Phase.LocalSched); - assertEquals("Stop[ return Phi(Loop,arg,3); return Parm_i(x,i64); ]", code._stop.toString()); + assertEquals("return Phi(Loop,arg,3);", code._stop.toString()); assertEquals("3", Eval2.eval(code, 0)); } @@ -454,7 +455,7 @@ if (i2i) return i2i(arg); return f2f(o)(1); """); code.driver(Phase.LocalSched); - assertEquals("Stop[ return Phi(Region,arg,1); return Parm_i(i2i.o,i64); ]", code._stop.toString()); + assertEquals("return Phi(Region,arg,1);", code._stop.toString()); assertEquals("1", Eval2.eval(code, 2)); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 88155e5b..337dbc62 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -415,7 +415,7 @@ val fcn = arg ? { int x -> x*x; } : { int x -> x+x; }; return fcn(2)*10 + fcn(3); """); code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); - assertEquals("Stop[ return (add,#2,(muli,#2)); return (mul,Parm_x($fun35,i64),x); return (shli,Parm_x($fun36,i64)); ]", code.print()); + assertEquals("Stop[ return (add,#2,(muli,#2)); return (mul,Parm_x($fun35,[2-3]),x); return (shli,Parm_x($fun36,[2-3])); ]", code.print()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 4800b180..c5e4c583 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -244,8 +244,8 @@ s.cs[1] = 108; // l hashCode(s); """; testTarget(src,"x86_64_v2", "SystemV",9,null); - testTarget(src,"riscv" , "SystemV",3,null); - testTarget(src,"arm" , "SystemV",0,null); + testTarget(src,"riscv" , "SystemV",1,null); + testTarget(src,"arm" , "SystemV",1,null); } @Test diff --git a/src/test/java/com/seaofnodes/simple/EscapeTest.java b/src/test/java/com/seaofnodes/simple/EscapeTest.java new file mode 100644 index 00000000..6d778350 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/EscapeTest.java @@ -0,0 +1,84 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import org.junit.Test; +import static org.junit.Assert.*; + +public class EscapeTest { + private static final String POWER = """ + val power = { int base, int exponent -> + if (exponent <= 0) return 1; + int smaller=power(base,exponent-1); + return base * smaller; + }; + """; + private static final String SUM = """ + val sumPowers = { int n, {int int -> int} f -> + if (n <= 0) return 0; + return f(2,n) + sumPowers(n-1,f); + }; + """; + private static ParmNode base(CodeGen code) { + ParmNode parm=code._start.walk(n -> n instanceof ParmNode p && p._label.equals("base") ? p : null); + assertNotNull(parm); + return parm; + } + private static CodeGen analyze(String src, long seed) { + return new CodeGen(src,TypeInteger.BOT,seed,true).driver(CodeGen.Phase.Opto); + } + + @Test public void testKnownRecursiveCallback() { + String src=POWER+SUM+"return sumPowers(arg,power);"; + for( long seed : new long[]{2,13,123} ) { + CodeGen code=analyze(src,seed); + ParmNode base=base(code); + assertSame(TypeInteger.constant(2),base._type); + assertFalse(base.fun().unknownCallers()); + assertNotNull(code._start.walk(n -> n instanceof CallNode c && "power".equals(c.name()) ? c : null)); + code.driver(CodeGen.Phase.TypeCheck); + assertEquals("14",Eval2.eval(code,3)); + } + } + + @Test public void testReturnedAddresses() { + // Returning the address, or a chain of objects containing it, restores + // arbitrary callers even when every visible call passes base=2. + String holder="struct Holder { {int int -> int} f; }; val h=new Holder { f=power; };"; + for( String tail : new String[]{ + "return power;", + holder+"return h;", + holder+"struct Wrap { Holder child; }; return new Wrap { child=h; };", + "struct Cell { {int int -> int}? !f; }; val h=new Cell; while(arg--) h.f=power; return h;" + } ) { + CodeGen code=analyze(POWER+SUM+"sumPowers(arg,power);"+tail,123); + ParmNode base=base(code); + assertSame(TypeInteger.BOT,base._type); + assertTrue(base.fun().unknownCallers()); + assertTrue(code._start.escapedFIDX(base.fun().sig().fidx())); + code.driver(CodeGen.Phase.TypeCheck); + } + } + + @Test public void testNativeExposure() { + for( String tail : new String[]{ + "retain(power); return sumPowers(arg,power);", + "if(arg) { retain(power); while(true) {} } return sumPowers(arg,power);" + } ) { + String src=POWER+SUM+"{ {int int -> int} -> int } retain=\"C\";"+tail; + CodeGen code=analyze(src,123); + ParmNode base=base(code); + assertSame(TypeInteger.BOT,base._type); + assertTrue(base.fun().unknownCallers()); + code.driver(CodeGen.Phase.TypeCheck); + } + // An external caller can inspect a field written through its argument, + // even though the exposed function itself returns only an integer. + String src="struct Holder { {int int -> int}? !f; };"+POWER+ + "val expose={!Holder h -> h.f=power; return 0;}; return expose;"; + CodeGen code=analyze(src,123); + assertTrue(base(code).fun().unknownCallers()); + code.driver(CodeGen.Phase.TypeCheck); + } +} -- cgit v1.2.3