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 --- src/main/java/com/seaofnodes/simple/Parser.java | 4 +- .../com/seaofnodes/simple/codegen/CodeGen.java | 3 + .../com/seaofnodes/simple/codegen/FinalizeIR.java | 4 ++ .../java/com/seaofnodes/simple/codegen/Opto.java | 59 +++++++++++------ .../com/seaofnodes/simple/node/CallEndNode.java | 24 ++++++- .../java/com/seaofnodes/simple/node/CallNode.java | 23 ++++++- .../com/seaofnodes/simple/node/EscapeNode.java | 8 ++- .../com/seaofnodes/simple/node/MemMergeNode.java | 12 ++-- .../com/seaofnodes/simple/node/MemPhiNode.java | 7 +- .../java/com/seaofnodes/simple/node/ParmNode.java | 12 +++- .../com/seaofnodes/simple/node/ReturnNode.java | 2 +- .../java/com/seaofnodes/simple/node/StartNode.java | 32 +++++++-- .../java/com/seaofnodes/simple/node/StopNode.java | 26 +++++++- .../java/com/seaofnodes/simple/node/StoreNode.java | 5 +- .../java/com/seaofnodes/simple/type/TypeMem.java | 77 +++++++++++++++++----- .../java/com/seaofnodes/simple/type/TypeTuple.java | 2 + 16 files changed, 236 insertions(+), 64 deletions(-) (limited to 'src/main/java') diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 45c429d8..145feb15 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -270,7 +270,7 @@ public class Parser { _scope.push(new Kind.Func(_privateFun!=null)); ctrl(fun); // Scope control from function // Unknown callers supply whole memory; field aliases are discovered lazily. - _scope.mem(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).peephole()); + _scope.mem(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,new ProjNode(_code._start,1,ScopeNode.MEM0).peephole()).peephole()); // All args, "as-if" called externally for( int i=0; i"; fun._constructor=true; _code.link(fun); Node rpc=new ParmNode("$rpc",0,TypeRPC.BOT,fun,con(TypeRPC.BOT)).init(); - Node pub=new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).init(); + Node pub=new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,new ProjNode(_code._start,1,ScopeNode.MEM0).peephole()).init(); Node[] args=new Node[nargs+2]; for( int i=0; i _calls = new Ary<>(CallNode.class); // Global Value Numbering. Hash over opcode and inputs; hits in this table // are structurally equal. diff --git a/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java index 9e3b3e32..4adb2fa4 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java +++ b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java @@ -10,6 +10,10 @@ abstract class FinalizeIR { static void run(CodeGen code) { fieldSizes(code); code._iter.iterate(code); + // The external-world cycle is an analysis edge, not runtime control. + // Freeze its facts before replacing call edges with emission roots. + code._stop.close(); + code._start.close(); removeCallGraph(code); Arrays.sort(code._stop._inputs._es,0,code._stop.nIns(),(x,y) -> x._nid - y._nid); } diff --git a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 82646a25..3c34b44c 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -29,17 +29,9 @@ abstract public class Opto { Ary oldTypes = new Ary<>(Type.class); // Used for asserts only resetToTop(code,oldTypes); - // The whole-world assumption: we use it if compiling `main`, and not otherwise. - // The assumption is no unknown callers into functions: - // - during or past an Opto phase (but not before, since parse through - // pessimistic must assume somebody calls an unknown function which - // calls everybody). - // - Have a `main` to start tracing the Call Graph from - // - - True for most test cases - // - - False for lacking a main; we assume the linker will call all public functions - - // True if we can make the "whole world" assumption, which means we are - // compiling the program entry: `main`. + // Main seeds a whole program. Without main, named exported functions + // seed discovery. Either way, escaping addresses can add more unknown + // callers as Start and Stop reach their shared fixed point. boolean wholeWorld = code.link(code._main) != null; @@ -54,6 +46,9 @@ abstract public class Opto { resolveNumericModes(code); if( !code._iter._work.isEmpty() ) sccp(code, oldTypes); + ProjNode startMem=code._start.proj(1); + if( startMem!=null ) { startMem.unkeep(); code.add(startMem); } + // After SCCP add everything changed to the worklist and see if // peepholes can make more progress. moveChangesToWorklist(code, oldTypes); @@ -79,6 +74,8 @@ abstract public class Opto { // called unless they get linked (hence go dead and can be removed). If // not wholeWorld, keep only public methods (and not the std lib). private static void unlinkStart(boolean wholeWorld, CodeGen code) { + ProjNode startMem=code._start.proj(1); + if( startMem!=null ) startMem.keep(); for( FunNode fun : code._linker ) { if( fun != null && !fun.isDead() && !funIsPublic(code,wholeWorld,fun) ) { assert fun.in(1)==code._start; // Start always in slot 1 @@ -94,15 +91,15 @@ abstract public class Opto { // Function is public (callable from Start directly). // - Always true for main - // - True for function addresses used as values // - Otherwise false for stdlib or anonymous functions // - Named functions use `!wholeWorld` private static boolean funIsPublic( CodeGen code, boolean wholeWorld, FunNode fun ) { // Always true for main if( fun.sig().fidx() == code._main.fidx() ) return true; - // No escape analysis yet: a surviving address may be called from outside. + // Hidden allocation helpers are never external entry points. if( fun._constructor ) return false; - if( fun.hasPtr() ) return true; + // Taking an address does not expose it. Stop discovers escapes from + // reachable returns and memory; linkStart restores only those callers. // Never true for stdlib or anonymous functions if( fun._name == null || fun._name.startsWith("sys.") ) return false; @@ -114,8 +111,11 @@ abstract public class Opto { // into a Call, link the Call and Fun. private static void linkCG(CodeGen code, TypeFunPtr tfp, CallNode call) { if( tfp.nargs() != call.nargs() ) return; // Error calls hit this + if( XInt.isHigh(tfp.fidxs()) ) return; for( int fidx=XInt.next(tfp.fidxs(),-1); fidx>=0; fidx=XInt.next(tfp.fidxs(),fidx) ) { - FunNode fun = code.link(fidx); + // A disconnected function can still be revived by a discovered + // call or escaping address. Do not clean the linker entry here. + FunNode fun = code._link(fidx); // null here means an external function; i.e. this Call // calls to an outside library and all its arguments escape. if( fun != null && !call.linked(fun) ) { @@ -126,6 +126,24 @@ abstract public class Opto { } } + // Exposure is a call edge from the unknown world. Restore conservative + // declared arguments, never the narrower values inferred from known calls. + private static void linkStart(CodeGen code, TypeTuple state) { + for( FunNode fun : code._linker ) { + if( fun==null || fun.isDead() || fun._constructor || fun.unknownCallers() || + !XInt.bit(state.mem()._escFs,fun.sig().fidx()) ) continue; + fun.insertDef(1,code._start); + if( !code._stop._inputs.contains(fun.ret()) ) code._stop.addDef(fun.ret()); + code.add(fun); code.add(code._stop); + for( Node n : fun._outputs ) + if( n instanceof ParmNode parm ) { + Node def=parm._idx==1 ? code._start.proj(1) : new ConstantNode(parm._declaredType).peephole(); + parm.insertDef(1,def); + code.add(parm); + } + } + } + // The core SCCP algorithm private static void sccp( CodeGen code, Ary oldTypes ) { // Iter workList is empty at this point @@ -137,9 +155,9 @@ abstract public class Opto { count++; Type oval = n._type, nval = n.compute(); if( oval == nval ) continue; - assert oval.isa(nval); // Types start high and always fall - Type pesiVal = oldTypes.at(n._nid); - assert nval.isa(pesiVal); // Never fall worse than the pessimistic pass + assert oval.isa(nval) : n.label()+"#"+n._nid+" old="+oval+" new="+nval; // Types start high and always fall + Type pesiVal = oldTypes.atX(n._nid); + assert pesiVal==null || nval.isa(pesiVal) : n.label()+"#"+n._nid+" pessimistic="+pesiVal+" new="+nval; // Never fall worse than the pessimistic pass n._type = nval; // If a TFP adds a new function input to a call, link to the new Fun @@ -153,6 +171,8 @@ abstract public class Opto { if( n instanceof CallNode call && oval.isHigh() && !nval.isHigh() && call.fptr()._type instanceof TypeFunPtr ) linkCG(code,call.tfp(),call); + if( n instanceof StartNode && nval instanceof TypeTuple tt ) linkStart(code,tt); + // Since n._type changed, visit all output neighbors code._iter.addAll(n._outputs); n.moveDepsToWorklist(code._iter); @@ -165,7 +185,8 @@ abstract public class Opto { private static boolean check(CodeGen code) { code._start.walk( x -> { Type xval = x.compute(); - assert xval == x._type || (x._type.isa( xval ) && code._iter._work.on( x )); + assert xval == x._type || (x._type.isa( xval ) && code._iter._work.on( x )) + : x.label()+"#"+x._nid+" old="+x._type+" new="+xval+" queued="+code._iter._work.on(x); return null; }); return true; diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 604bb9da..86c6c79d 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -69,7 +69,29 @@ public class CallEndNode extends CFGNode implements MultiNode { ret = ti.same_but_slightly_wider_than(TypeInteger.BOT).join(tfp.ret()); } } - return TypeTuple.make(call._type,TypeMem.BOT,ret); + TypeMem mem=TypeMem.TOP; + for( int i=1; i=0; fidx=XInt.next(tfp.fidxs(),fidx) ) { + if( CodeGen.CODE.externFunc(tfp.makeFrom(fidx))!=null ) external=true; + else locals++; + } + known=locals==nIns()-1; + } + if( external || (ftype instanceof TypeFunPtr tfp && XInt.isHigh(tfp.fidxs())) ) { + // Unknown code may retain arguments and all addresses already + // exposed to it. Heap values are arbitrary after this call; + // exposure itself still has a useful finite summary. + mem=(TypeMem)mem.meet(call.exposed(this)); + } else if( !known && (CodeGen.CODE._phase.ordinal()CodeGen.Phase.FinalizeIR.ordinal()) ) mem=TypeMem.BOT; + return TypeTuple.make(call._type,mem,ret); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java index 21f438da..44ad8e83 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -8,6 +8,7 @@ import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.XInt; import com.seaofnodes.simple.type.TypeFunPtr; +import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.util.Utils; /** @@ -21,7 +22,7 @@ public class CallNode extends CFGNode { // us whether this is a method or an ordinary function stored in a field. public String _method; - public CallNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; } + public CallNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; CodeGen.CODE._calls.add(this); } public CallNode(CallNode call) { super(call); _loc = call._loc; _method=call._method; } @Override public String label() { return "Call"; } @@ -58,7 +59,25 @@ public class CallNode extends CFGNode { public TypeFunPtr tfp() { return (TypeFunPtr)fptr()._type; } // Call is to an externally supplied code - public boolean external() { return false; } + public boolean external() { + if( !(fptr()._type instanceof TypeFunPtr tfp) ) return false; + if( XInt.isHigh(tfp.fidxs()) ) return true; + for( int fidx=XInt.next(tfp.fidxs(),-1); fidx>=0; fidx=XInt.next(tfp.fidxs(),fidx) ) + if( CodeGen.CODE.externFunc(tfp.makeFrom(fidx))!=null ) return true; + return false; + } + + // Unknown code can retain arguments without ever returning. Stop uses + // this summary directly as well as through the call's memory result. + TypeMem exposed(Node dep) { + dep.addDepForwards(this); + dep.addDepForwards(fptr()); + if( _type!=Type.CONTROL || !external() ) return TypeMem.START; + Type input=dep.addDepForwards(mem())._type; + TypeMem escaped=input instanceof TypeMem m ? m : input.isHigh() ? TypeMem.TOP : TypeMem.BOT; + for( int i=2; i=2 ) + mem=mem.escapes(addDepForwards(p)._type); + if( !(ret._type instanceof TypeTuple tt) || tt._types[0].isHigh() ) continue; + mem=mem.escapes(tt.ret()).escapes(tt._types[1]); + } + for( CallNode call : code._calls ) + if( !call.isDead() ) mem=mem.escapes(call.exposed(this)); + return mem; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index caba7bdd..06ff51fc 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -48,10 +48,11 @@ public class StoreNode extends MemOpNode { // Initializing Stores are emitted at helper exits for a fresh object. // They replace this private field; Escape later joins it with public // memory. Keep an unwritten BOTTOM visible to the completion check. - if( _init ) return TypeMem.make(_alias,val); + if( _init ) return TypeMem.make(_alias,val,XInt.EMPTY,XInt.EMPTY).escapes(val); assert !_declaredType.isFRef(); Type t = val.join(_declaredType).meet(MemMergeNode.contents(mem(),_alias,this)); - return TypeMem.make(_alias,t); + TypeMem prior=mem()._type instanceof TypeMem m ? m : mem()._type.isHigh() ? TypeMem.TOP : TypeMem.BOT; + return prior.withContents(_alias,t).escapes(val); } @Override diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 5539e1cf..cc287922 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -20,12 +20,18 @@ public class TypeMem extends Type { public int _alias; public Type _t; // Scalar public contents, or private field values. + // Addresses reachable through this memory. EMPTY means no exposed address; + // FULL means any address. These discovery sets join by union, independently + // of the field contents. They use the same interned sets as function types. + public int[] _escFs, _escAs; + private static final Ary FREE = new Ary<>(TypeMem.class); - private TypeMem(int alias, Type t) { super(TMEM); init(alias,t); } - private TypeMem init(int alias, Type t) { + private TypeMem(int alias, Type t, int[] fs, int[] as) { super(TMEM); init(alias,t,fs,as); } + private TypeMem init(int alias, Type t, int[] fs, int[] as) { assert alias>1 || (t==null || t==Type.TOP || t==Type.BOTTOM || t instanceof TypeStruct); _alias = alias; _t = t; + _escFs=fs; _escAs=as; return this; } @Override TypeMem free(Type t) { @@ -38,11 +44,14 @@ public class TypeMem extends Type { } @Override boolean isFree() { return _alias == -99; } - public static TypeMem malloc(int alias, Type t) { - return FREE.isEmpty() ? new TypeMem(alias,t) : FREE.pop().init(alias,t); + public static TypeMem malloc(int alias, Type t, int[] fs, int[] as) { + return FREE.isEmpty() ? new TypeMem(alias,t,fs,as) : FREE.pop().init(alias,t,fs,as); } public static TypeMem make(int alias, Type t) { - TypeMem f = malloc(alias,t); + return make(alias,t,t.isHigh() ? XInt.EMPTY : XInt.FULL,t.isHigh() ? XInt.EMPTY : XInt.FULL); + } + public static TypeMem make(int alias, Type t, int[] fs, int[] as) { + TypeMem f = malloc(alias,t,fs,as); TypeMem f2 = f.intern(); if( f2==f ) return f; return VISIT.isEmpty() ? f2.free(f) : f2.delayFree(f); @@ -50,7 +59,36 @@ public class TypeMem extends Type { // Private memory describes one allocation. It is passed explicitly to // initializers; it never joins the public heap until EscapeNode. - public static TypeMem makePrivate(TypeStruct shape) { return make(1,shape); } + public static TypeMem makePrivate(TypeStruct shape) { + return make(1,shape,XInt.EMPTY,XInt.EMPTY).escapes(shape); + } + + public TypeMem escapes(Type value) { + int[] fs=_escFs, as=_escAs; + if( value instanceof TypeMem m ) { + fs=XInt.meet(fs,m._escFs); as=XInt.meet(as,m._escAs); + } else if( value instanceof TypeFunPtr f ) { + fs=XInt.meet(fs,f.fidxs()); + } else if( value instanceof TypeMemPtr p ) { + return escapes(p._obj); + } else if( value instanceof TypeStruct s ) { + if( s._open && !s.isAry() ) return make(_alias,_t,XInt.FULL,XInt.FULL); + for( Field f : s._fields ) { + // A constructor has a hidden memory result, never a public + // callable address. Constant methods need no memory Store. + if( f._t instanceof TypeFunPtr fn && fn.ret() instanceof TypeMem ) continue; + as=XInt.make(as,f._alias); + if( f._one && f._t instanceof TypeFunPtr fn ) fs=XInt.meet(fs,fn.fidxs()); + } + } else if( value==Type.BOTTOM || value==TypeScalar.BOT ) { + fs=XInt.FULL; as=XInt.FULL; + } + return make(_alias,_t,fs,as); + } + + public TypeMem withContents(int alias, Type contents) { + return make(alias,contents,_escFs,_escAs); + } public static TypeStruct empty(TypeStruct shape) { Field[] fields = new Field[shape._fields.length]; @@ -71,9 +109,11 @@ public class TypeMem extends Type { public static final TypeMem TOP = make(1, Type.TOP ); public static final TypeMem BOT = make(1, Type.BOTTOM); + public static final TypeMem START = make(1,Type.BOTTOM,XInt.EMPTY,XInt.EMPTY); public static void gather(ArrayList ts) { ts.add(make(2,Type.NIL)); ts.add(make(2,TypeInteger.ZERO)); ts.add(BOT); + ts.add(START); ts.add(make(2,TypeInteger.ZERO,XInt.make(3),XInt.make(5))); ts.add(makePrivate(TypeStruct.TEST)); ts.add(makePrivate(empty(TypeStruct.TEST))); } @@ -86,19 +126,20 @@ public class TypeMem extends Type { if( that==BOT ) return BOT; // Different slices lose their alias and contents together. Their // scalar meet alone cannot describe the unsplit bulk memory. - if( _alias!=that._alias ) return BOT; - int alias = _alias; - Type mt = _t.meet(that._t); - return make(alias,mt); + int alias = _alias==that._alias ? _alias : + (_alias==1 && _t==Type.TOP) ? that._alias : + (that._alias==1 && that._t==Type.TOP) ? _alias : 1; + Type mt = _alias==that._alias || alias!=1 ? _t.meet(that._t) : Type.BOTTOM; + return make(alias,mt,XInt.meet(_escFs,that._escFs),XInt.meet(_escAs,that._escAs)); } @Override - Type xdual() { return _t._dual==_t ? this : malloc(_alias,_t.dual()); } + Type xdual() { return malloc(_alias,_t.dual(),XInt.dual(_escFs),XInt.dual(_escAs)); } @Override TypeMem rdual() { if( _dual!=null ) return dual(); assert !_terned; - TypeMem d = malloc(_alias,null); + TypeMem d = malloc(_alias,null,XInt.dual(_escFs),XInt.dual(_escAs)); (_dual = d)._dual = this; // Cross link duals d._t = _t._terned ? _t.dual() : _t.rdual(); return d; @@ -110,16 +151,16 @@ public class TypeMem extends Type { @Override boolean _isGLB(boolean mem) { return _t instanceof TypeStruct s ? s.isGLB2() : _t._isGLB(true); } @Override public Type _glb(boolean mem) { return make(_alias,_t instanceof TypeStruct s ? s.glb2() : _t._glb(true)); } - @Override int hash() { return 9876543 + _alias + _t.hashCode(); } + @Override int hash() { return 9876543 + _alias + _t.hashCode() + XInt.hash(_escFs) + XInt.hash(_escAs); } @Override boolean eq(Type t) { TypeMem that = (TypeMem) t; // Invariant - return _alias == that._alias && _t == that._t; + return _alias == that._alias && _t == that._t && _escFs==that._escFs && _escAs==that._escAs; } @Override boolean cycle_eq(Type t) { TypeMem that = (TypeMem) t; // Invariant - return _alias == that._alias && _t.cycle_eq(that._t); + return _alias == that._alias && _escFs==that._escFs && _escAs==that._escAs && _t.cycle_eq(that._t); } @Override int nkids() { return 1; } @@ -131,7 +172,9 @@ public class TypeMem extends Type { if( this==TOP ) return sb.p("MemTop"); sb.p("#"); if( _alias==0 ) return sb.p(_t._type==TTOP ? "TOP" : "BOT"); - return _t.print(sb.p(_alias).p(":"),visit,html); + _t.print(sb.p(_alias).p(":"),visit,html); + XInt.str(sb.p(" f="),_escFs); + return XInt.str(sb.p(" a="),_escAs); } @Override public String str() { return toString(); } @@ -149,6 +192,6 @@ public class TypeMem extends Type { } return makePrivate(TypeStruct.make(shape._name,shape._open,fields)); } - return make(_alias,_t._upgradeType(types)); + return make(_alias,_t._upgradeType(types),_escFs,_escAs); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 27a0a9d9..ed137182 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -7,6 +7,8 @@ import java.util.*; public class TypeTuple extends Type { + public TypeMem mem() { return (TypeMem)_types[1]; } + public Type[] _types; private static final Ary FREE = new Ary<>(TypeTuple.class); -- cgit v1.2.3