Chapter 27: Escape Analysis and Unknown Callerslinear-chapter27

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: Claude Opus 5 <noreply@anthropic.com>

16 files changed, 236 insertions, 64 deletions

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<ids.length; i++ ) {
             Type t = sig.arg(i);
@@ -1103,7 +1103,7 @@ public class Parser {
         fun._name=shape._name+".<new>"; 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<nargs; i++ ) args[i+2]=new ParmNode("arg"+i,i+2,types[i],fun,con(types[i])).init();
         Node alloc=new NewNode(ptr,fun,null,off(shape," len")).init();
diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index a49299e1..d3895b08 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -101,6 +101,7 @@ public class CodeGen {
         _callingConv = null;
         _start = new StartNode(arg);
         _stop = new StopNode(src);
+        _start.setDef(1,_stop);
         _src = src;
         _arg = arg;
         _iter = new IterPeeps(workListSeed);
@@ -145,6 +146,8 @@ public class CodeGen {
     // Start and stop; end points of the generated IR
     public StartNode _start;
     public StopNode  _stop;
+    // Native calls are exposure roots even on paths with no live Return.
+    public final Ary<CallNode> _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<Type> 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<Type> 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<nIns(); i++ ) {
+            Type state=in(i)._type;
+            if( state instanceof TypeTuple tt ) mem=(TypeMem)mem.meet(tt._types[1]);
+            else if( !state.isHigh() ) mem=TypeMem.BOT;
+        }
+        boolean known=false, external=false;
+        if( ftype instanceof TypeFunPtr tfp && !XInt.isHigh(tfp.fidxs()) ) {
+            int locals=0;
+            for( int fidx=XInt.next(tfp.fidxs(),-1); fidx>=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.Opto.ordinal() ||
+                             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<nIns()-1; i++ ) escaped=escaped.escapes(dep.addDepForwards(arg(i))._type);
+        return escaped.withContents(1,Type.BOTTOM);
+    }
 
 
     // Find the Call End from the Call
diff --git a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java
index 75ecce64..849c552f 100644
--- a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java
@@ -4,8 +4,8 @@ import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.*;
 
 /** Publish one initialized field: {control, public memory, private memory, self}.
- *  This is an explicit construction boundary, not escape discovery. The next
- *  chapter will discover which objects and functions unknown code can reach.
+ *  This explicit construction boundary publishes a completed field. Stop and
+ *  Start separately discover whether unknown code can reach that field.
  */
 public class EscapeNode extends Node {
     public Field _field;
@@ -27,7 +27,9 @@ public class EscapeNode extends Node {
     }
     @Override public Type compute() {
         if( in(0)._type.isHigh() || priv()._type.isHigh() || pub()._type.isHigh() ) return TypeMem.TOP;
-        return TypeMem.make(_field._alias,value().meet(MemMergeNode.contents(pub(),_field._alias,this)).join(_field._t));
+        Type t=value().meet(MemMergeNode.contents(pub(),_field._alias,this)).join(_field._t);
+        TypeMem prior=pub()._type instanceof TypeMem m ? m : TypeMem.BOT;
+        return prior.withContents(_field._alias,t).escapes(value());
     }
     @Override public Node idealize() {
         if( priv() instanceof MemMergeNode merge ) {
diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java
index e405d152..a43667ff 100644
--- a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java
@@ -84,10 +84,14 @@ public class MemMergeNode extends Node {
             }
             return TypeMem.makePrivate(TypeStruct.make(shape._name,shape._open,fields));
         }
-        for( Node n : _inputs )
-            if( n != null && !n._type.isHigh() )
-                return TypeMem.BOT;
-        return TypeMem.TOP;
+        TypeMem mem=in(1)==null ? TypeMem.START : in(1)._type instanceof TypeMem m ? m :
+            in(1)._type.isHigh() ? TypeMem.TOP : TypeMem.BOT;
+        // Only memory visible outside this graph contributes to the external
+        // summary. Newly exposed aliases feed back through Start on the next
+        // SCCP visit, including chains of pointers stored in other objects.
+        for( int i=2; i<nIns(); i++ )
+            if( in(i)!=null && XInt.bit(mem._escAs,i) ) mem=mem.escapes(in(i)._type);
+        return mem;
     }
 
     @Override public Node idealize() {
diff --git a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java
index ba53cfd8..bca85e0d 100644
--- a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java
@@ -25,10 +25,13 @@ public class MemPhiNode extends PhiNode {
             return (region()._type==Type.XCONTROL || region()._type==Type.TOP) ? TypeMem.TOP : _type;
         if( r.inProgress() ) return r instanceof LoopNode ? TypeMem.make(_alias,Type.BOTTOM) : TypeMem.BOT;
         Type t = Type.TOP;
+        TypeMem escapes=TypeMem.START;
         for( int i=1; i<nIns(); i++ )
-            if( addDep(r.in(i))._type!=Type.XCONTROL && r.in(i)._type!=Type.TOP )
+            if( addDep(r.in(i))._type!=Type.XCONTROL && r.in(i)._type!=Type.TOP ) {
                 t = t.meet(MemMergeNode.contents(in(i),_alias,this));
-        return TypeMem.make(_alias,t);
+                escapes=escapes.escapes(in(i)._type);
+            }
+        return escapes.withContents(_alias,t);
     }
 
     @Override public Node idealize() {
diff --git a/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/src/main/java/com/seaofnodes/simple/node/ParmNode.java
index 52fe5704..37f049e5 100644
--- a/src/main/java/com/seaofnodes/simple/node/ParmNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ParmNode.java
@@ -10,7 +10,7 @@ import com.seaofnodes.simple.type.TypeMemPtr;
 public class ParmNode extends PhiNode {
 
     // Argument indices are mapped one-to-one on CallNode inputs
-    private Type _declaredType;
+    public Type _declaredType;
     public final int _idx;             // Argument index
 
     public ParmNode(String label, int idx, Type declaredType, Node... inputs) {
@@ -39,7 +39,15 @@ public class ParmNode extends PhiNode {
 
     @Override
     public Type compute() {
-        Type t = inProgress() ? _declaredType : super.compute().join(_declaredType);
+        Type t;
+        if( _idx==1 && region() instanceof FunNode fun ) {
+            // Even an unknown caller supplies Start's discovered escape set.
+            // Its heap contents are arbitrary, but its addresses are not.
+            t=Type.TOP;
+            for( int i=1; i<nIns(); i++ )
+                if( !addDep(fun.in(i))._type.isHigh() ) t=t.meet(in(i)._type);
+            t=t.join(_declaredType);
+        } else t = inProgress() ? _declaredType : super.compute().join(_declaredType);
         // 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.
diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index ce3feef2..ecfd2cde 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -45,7 +45,7 @@ public class ReturnNode extends CFGNode {
     public Type compute() {
         if( inProgress () ) return TypeTuple.RET; // In progress
         // Inlining can delete the entry while callers still use this return.
-        return TypeTuple.make(ctrl()._type,TypeMem.BOT,expr()._type);
+        return TypeTuple.make(ctrl()._type,mem()._type,expr()._type);
     }
 
     @Override public Node idealize() {
diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java
index e13d35c0..2c913b88 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -3,18 +3,29 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.print.ExprPrinter;
 
 import com.seaofnodes.simple.codegen.CodeGen;
-import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.*;
-import java.util.HashSet;
-import static com.seaofnodes.simple.util.Utils.TODO;
 
-/** Start supplies control, whole memory, and the argument, in that order. */
+/** Unknown callers: control, exposed memory, and the entry argument.
+ *  Stop feeds discovered addresses back here during SCCP. This closes the
+ *  cycle between known code and unknown callers without a runtime loop.
+ */
 public class StartNode extends LoopNode implements MultiNode {
 
     final Type _arg;
+    private TypeTuple _closed;
 
     public StartNode(Type arg) { super(null,null); _arg = arg; _type = compute(); }
-    public StartNode(StartNode start) { super(start); _arg = start==null ? null : start._arg; }
+    public StartNode(StartNode start) { super(start); _arg = start==null ? null : start._arg; _closed=start==null ? null : start._closed; }
+
+    public void close() {
+        _closed=(TypeTuple)_type;
+        ProjNode mem=proj(1);
+        if( mem!=null ) mem.subsume(new ConstantNode(mem._type).peephole());
+        // Stop is a graph root even after the analysis feedback edge is gone.
+        Node stop=in(1).keep();
+        setDef(1,null);
+        stop.unkeep();
+    }
 
     @Override public String label() { return "Start"; }
 
@@ -37,7 +48,16 @@ public class StartNode extends LoopNode implements MultiNode {
 
 
     @Override public TypeTuple compute() {
-        return TypeTuple.make(Type.CONTROL,TypeMem.BOT,_arg);
+        if( _closed!=null ) return _closed;
+        TypeMem mem = in(1)==null || CodeGen.CODE._phase==null ||
+            CodeGen.CODE._phase.ordinal()<CodeGen.Phase.Opto.ordinal() ? TypeMem.BOT :
+            in(1)._type instanceof TypeMem m ? m : in(1)._type.isHigh() ? TypeMem.START : TypeMem.BOT;
+        return TypeTuple.make(Type.CONTROL,mem,_arg);
+    }
+
+    public boolean escapedFIDX(int fidx) {
+        if( !(_type instanceof TypeTuple tt) ) return !_type.isHigh();
+        return XInt.bit(tt.mem()._escFs,fidx);
     }
 
     @Override public Node idealize() { return null; }
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 9f7a925b..83acc8e3 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -2,19 +2,22 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.print.ExprPrinter;
 
-import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.util.Utils;
 
 public class StopNode extends CFGNode {
 
     public final String _src;
+    private Type _closed;
+    public void close() { _closed=_type; }
 
     public StopNode(String src) {
         super();
         _src = src;
         _type = compute();
     }
-    public StopNode(StopNode stop) { super(stop);  _src = stop==null ? null : stop._src; }
+    public StopNode(StopNode stop) { super(stop);  _src = stop==null ? null : stop._src; _closed=stop==null ? null : stop._closed; }
 
     @Override
     public String label() {
@@ -53,7 +56,24 @@ public class StopNode extends CFGNode {
 
     @Override
     public Type compute() {
-        return Type.BOTTOM;
+        if( _closed!=null ) return _closed;
+        CodeGen code=CodeGen.CODE;
+        if( code._phase==null || code._phase.ordinal()<CodeGen.Phase.Opto.ordinal() ) return TypeMem.BOT;
+        TypeMem mem=TypeMem.START;
+        for( Node n : _inputs ) {
+            ReturnNode ret=(ReturnNode)n;
+            if( !ret.fun().unknownCallers() ) continue;
+            // An external caller already holds its arguments. Writes through
+            // those pointers are visible even if this function returns a scalar.
+            for( Node use : ret.fun()._outputs )
+                if( use instanceof ParmNode p && p._idx>=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<TypeMem> 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<Type> 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<TypeTuple> FREE = new Ary<>(TypeTuple.class);