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>

10 files changed, 125 insertions, 26 deletions

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