Chapter 25: Modules, Separate Compilation, and SSA Constructionlinear

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>

1 files changed, 231 insertions, 144 deletions

diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
index 115f70c6..35180fea 100644
--- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
@@ -2,9 +2,13 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.print.ExprPrinter;
 
-import com.seaofnodes.simple.*;
+import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.codegen.*;
 import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.util.BAOS;
+
+import java.util.HashMap;
+import java.util.IdentityHashMap;
 
 /**
  *  CallEnd
@@ -12,17 +16,48 @@ import com.seaofnodes.simple.type.*;
 public class CallEndNode extends CFGNode implements MultiNode {
 
     // When set true, this Call/CallEnd/Fun/Return is being trivially inlined
-    private boolean _folding;
-    public boolean folding() { return _folding; }
+    boolean _folding;
+    // +2 must clone, so await all cleanup but OK
+    // +1 trivial now,
+    //  0: take a look,
+    // -1: somethings wrong, but might improve
+    // -2: never and stop asking,
+    private byte _inline;
     public final TypeRPC _rpc;
 
-    public CallEndNode(CallNode call) { super(new Node[]{call}); _rpc = TypeRPC.constant(_nid); }
+    public CallEndNode(CallNode call, TypeRPC rpc) {
+        super(new Node[]{call});
+        _rpc = rpc;
+    }
     public CallEndNode(CallEndNode cend) { super(cend); _rpc = cend._rpc; }
+    public CallEndNode(TypeRPC rpc) {
+        super(new Node[0]);
+        _rpc = TypeRPC.constant(CodeGen.CODE._rpcs.next(rpc.rpc()));
+    }
+    private CallEndNode(int nIns, TypeRPC rpc) {
+        super(new Node[nIns]);
+        _rpc = rpc;
+    }
+    @Override public Tag serialTag() { return Tag.CallEnd; }
+    public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) {
+        baos.packed1(nIns());
+        // Linked CallEnds depend on Return types which depend on CallEnds;
+        // break the cycle
+        baos.packed2(types.get(_type));
+        baos.packed2(types.get(_rpc));
+    }
+    static Node make( BAOS bais, Type[] types )  {
+        int nIns = bais.packed1();
+        Type type = types[bais.packed2()];
+        Node cend = new CallEndNode(nIns,(TypeRPC)types[bais.packed2()]);
+        cend._type = type;
+        return cend;
+    }
 
-    @Override public String label() { return "CallEnd"; }
     @Override public boolean blockHead() { return true; }
 
     public CallNode call() { return (CallNode)in(0); }
+    public boolean folding() { return _folding; }
 
     @Override public CFGNode idom(Node dep) {
         // Folding the idom is the one inlining Return
@@ -41,182 +76,234 @@ public class CallEndNode extends CFGNode implements MultiNode {
     @Override
     public Type compute() {
         if( !(in(0) instanceof CallNode call) || call._type != Type.CONTROL )
-            return TypeTuple.RET.dual();
-        // Mid-fold, just take the one single callers' return type
-        if( _folding ) return in(1)._type;
+            return TypeTuple.STATE.dual();
         // Grab the TFP and use the functions declared return type.
+        // If the call.fptr() is a FRef, return will be BOTTOM.
         Type ftype = addDep(call.fptr())._type;
-        Type ret = ftype.isHigh() ? Type.TOP : Type.BOTTOM;
-        if( ftype instanceof TypeFunPtr tfp ) {
-            ret = tfp.ret();
-            // Here, if I can figure out I've found *all* callers, then I can meet
-            // across the linked returns and join with the function return type.
-            if( 1+tfp.nfcns() == nIns() ) { // A linked function for every concrete function
-                ret = Type.TOP;
-                for( int i=1; i<nIns(); i++ ) {
-                    Type tret = in(i)._type instanceof TypeTuple rtt ? rtt.ret() : in(i)._type;
-                    ret = ret.meet(tret);
-                }
-            }
+        if( !(ftype instanceof TypeFunPtr tfp) )
+            return ftype.isHigh() ? TypeTuple.STATE.dual() : TypeTuple.STATE;
+        // Mid-fold, just take the one single callers' return type
+        if( _folding ) {
+            TypeTuple tt = (TypeTuple)in(1)._type;
+            return tt.makeFrom(2,tt.ret());
+        }
+
+        // Here, if I can figure out I've linked *all* callers, then I can meet
+        // across the linked returns and join with the function return type.
+
+        // External functions have an exact FIDX but deliberately no local
+        // FunNode/Return edge.  They conservatively crush public memory and
+        // 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) )
+                if( CodeGen.CODE.externFunc(fidx)!=null )
+                    externs++;
+        boolean hasExtern = externs != 0;
+
+        // If we have an error-call, e.g. wrong args, then we never link.
+        // Pre-Opto this looks like a missing target fcn, and we assume it will
+        // appear later - meanwhile, we use a conservative approx of memory
+        // effects.
+        if( (nIns()-1)+externs < tfp.nfcns() ) {
+            // If during Opto, assume call won't be called and thus won't return anything.
+            boolean opto = CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal();
+            Type tmem = opto ? TypeMem.TOP : TypeMem.BOT;
+            Type ret  = opto ? Type.TOP    : tfp.ret();
+            return TypeTuple.make(Type.CONTROL,tmem,ret);
         }
-        return TypeTuple.make(call._type,TypeMem.BOT,ret);
+
+        // A linked function for every concrete function
+        TypeTuple state = hasExtern
+            ? TypeTuple.make(Type.CONTROL,TypeMem.BOT,tfp.ret())
+            : TypeTuple.STATE.dual();
+        for( int i=1; i<nIns(); i++ )
+            state = (TypeTuple)state.meet(in(i)._type);
+        // A reachable call whose presently linked exits are all unreachable
+        // keeps a conservative continuation.  In particular, do not let a
+        // transient no-return result tear down the caller during SCCP.
+        if( state.ctl()==Type.XCONTROL &&
+            CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() )
+            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()));
     }
 
     @Override
     public Node idealize() {
+        return null;
+    }
 
-        // Trivial inlining: call site calls a single function; single function
-        // is only called by this call site.
-        if( !_folding && nIns()==2 && in(0) instanceof CallNode call ) {
-            Node fptr = call.fptr();
-            if( fptr.nOuts() == 1 && // Only user is this call
-                fptr instanceof ConstantNode && // We have an immediate call
-                // Function is being called, and its not-null
-                fptr._type instanceof TypeFunPtr tfp && tfp.notNull() &&
-                // Arguments are correct
-                call.err()==null ) {
-                ReturnNode ret = (ReturnNode)in(1);
-                FunNode fun = ret.fun();
-                // Expecting Start, and the Call
-                if( fun.nIns()==3 ) {
-                    assert fun.in(1) instanceof StartNode && fun.in(2)==call;
-                    // Disallow self-recursive inlining (loop unrolling by another name).
-                    // Disallow if still folding other things, as it makes other
-                    // dependency checks carry long chains of half-folded calls.
-                    // Dead control may end the walk before an enclosing function.
-                    CFGNode idom = call;
-                    while( idom!=null ) {
-                        idom = idom.idom();
-                        if( idom instanceof FunNode ) break;
-                        if( idom instanceof CallEndNode cend && cend._folding ) break;
-                    }
-                    // Inline?
-                    if( idom instanceof FunNode fun2 && fun2 != fun && !fun2._folding ) {
-                        // Trivial inline: rewrite
-                        _folding = true;
-                        // Rewrite Fun so the normal RegionNode ideal collapses
-                        fun._folding = true;
-                        fun.setDef(1,Parser.XCTRL); // No default/unknown StartNode caller
-                        fun.setDef(2,call.ctrl());  // Bypass the Call;
-                        fun.ret().setDef(3,null);   // Return is folding also
-                        CodeGen.CODE.addAll(fun._outputs);
-                        // Repeat defs 1 layer down, for users of Parm (Phis)
-                        for( Node parm : fun._outputs )
-                            if( parm instanceof ParmNode )
-                                CodeGen.CODE.addAll(parm._outputs);
-
-                        // Inlining immediately blows all cache idepth fields past the inline point.
-                        // Bump the global version number invalidating them en-masse.
-                        CodeGen.CODE.invalidateIDepthCaches();
-                        return this;
-                    } else if( idom!=null ) {
-                        addDep(idom);
-                    }
-                } else {
-                    addDep(fun);
-                }
-            } else { // Function ptr has multiple users (so maybe multiple call sites)
-                addDep(fptr);
-            }
-        }
+    public byte maybeInline() {
+        byte inline = inlineCandidate();
+        if( CodeGen.CODE._midAssert )
+            return inline;
+        _inline = inline;
+        if( _inline > 0 )
+            doInline();
 
-        return null;
+        return _inline;
     }
 
-    // Clone only tiny, straight-line boilerplate, after ordinary peeps settle.
-    // Larger bodies still use the existing single-caller, non-cloning inline.
-    public boolean inlineSmall() {
-        if( isDead() || _folding || nIns()!=2 || !(in(0) instanceof CallNode call) ) return false;
-        Node fptr = call.fptr();
-        if( !(fptr instanceof ConstantNode) ||
-            !(fptr._type instanceof TypeFunPtr tfp && tfp.notNull() && tfp.isConstant()) )
-            { addDep(fptr); return false; }
-        if( call.err()!=null ) return false;
+    // Check if candidate right now, sets no flags
+    private byte inlineCandidate() {
+        if( _inline < -2 ) return -2; // Never
+        if( _folding ) return -2;     // No, and will collapse anyways
+        if( !(in(0) instanceof CallNode call) ) return -2; // malformed because mid-death
+
+        if( nIns()!=2 ) return -1;    // Not exactly 1 link, but can change
+
+        // Have exactly 1 linked function
         ReturnNode ret = (ReturnNode)in(1);
         FunNode fun = ret.fun();
-        if( fun._folding ) return false;
-        int len = smallBody(fun);
-        if( len==0 ) return false;
-        // All callers consume the three normal return projections.
-        for( Node use : _outputs )
-            if( !((use instanceof ProjNode p && p._idx>=0 && p._idx<3) ||
-                  (use instanceof CProjNode cp && cp._idx==0)) ) return false;
-
-        // Substitute control and arguments directly; no new function identity,
-        // parameter Phis, or return address is needed for this straight line.
-        Node[] copy = new Node[len];
-        for( int i=0; i<len; i++ ) {
-            Node n = TINYBODY[i];
-            copy[i] = n==fun ? call.ctrl() :
-                n instanceof ParmNode parm ? (parm._idx==0 ? null : call.arg(parm._idx)) :
-                n==ret ? null : n.copyEmpty();
-        }
-        for( int i=0; i<len; i++ ) {
-            Node n = TINYBODY[i];
-            if( n instanceof StoreNode || n instanceof MemMergeNode ) {
-                for( Node in : n._inputs ) copy[i].addDef(mapped(in,copy));
-                CodeGen.CODE.add(copy[i]);
-            }
-        }
-        Node[] result = new Node[3];
-        for( int i=0; i<3; i++ ) result[i] = mapped(ret.in(i),copy).keep();
-        keep();
-        call.unlink_all();
-        CodeGen.CODE.add(fun);
-        CodeGen.CODE.addAll(fun._outputs);
-        // subsume kills each projection; retain CallEnd until all are replaced.
-        while( nOuts()>1 ) {
-            Node use = out(0)==null ? out(1) : out(0);
-            int idx = use instanceof ProjNode p ? p._idx : ((CProjNode)use)._idx;
-            CodeGen.CODE.addAll(use._outputs);
-            use.subsume(result[idx]);
-        }
-        unkill();
-        for( Node n : result ) n.unkill();
-        CodeGen.CODE.invalidateIDepthCaches();
-        return true;
-    }
 
-    private static Node mapped(Node n, Node[] copy) {
-        for( int i=0; i<copy.length; i++ )
-            if( TINYBODY[i]==n ) return copy[i];
-        return n;               // Constants outside the body are shared.
+        // Heuristic forced inlining off via name
+        if( fun._name != null &&
+            fun._name.endsWith("_noInline") )
+            return -2;          // Never, stop asking
+
+        // Disallow self-recursive inlining (loop unrolling by another name).
+        for( int i=1; i < fun.nIns(); i++ )
+            if( fun.cfg(i).fun()==fun ) // Check for linked call input inside "fun"
+                { addDep(fun); return -1; } // No, but can lose the recursive edge
+
+        // Things that might improve, so not now a candidate
+        Node fptr = call.fptr();
+        // Constant Function is being called, and its not-null
+        if( !(fptr._type instanceof TypeFunPtr tfp && tfp.notNull() && tfp.isConstant()) )
+            { addDep(fptr); return -1; }
+
+        // Arguments are correct
+        if( call.nargs()!=tfp.nargs() || !goodArgs(call,tfp) )
+            { addDep(fptr); return -1; }
+
+        // Encouraged inlining because small size and constructor.
+        int maxSize = fun.inlineLimit();
+        // A large parse can leave only a tiny initializer.  Recognize that
+        // without repeatedly walking the whole body while it shrinks.
+        if( fun._approxUIDs >= maxSize ) {
+            if( !smallBody(fun) ) return -1;
+        } else if( fun.body().cardinality() >= maxSize )
+            return -1;          // Try later (if cleanup makes the real body small enough)
+
+        // Can be cloned but not trivial
+        if( fun.nIns() > 2 ) { addDep(fun); return 2; }
+
+        // A candidate right now
+        return 1;
     }
 
-    // Bounded recognition of initializer boilerplate. Walk uses from the entry
-    // and stop at Return, never following callers or constant inputs. This also
-    // avoids scanning sparse MemMerge input arrays while a large body shrinks.
-    // Watch this small prefix, including an unsupported node that may fold.
+    // Bounded, conservative recognition of straight-line initializer boilerplate.
+    // Walk uses from the entry and stop at Return, never following callers or
+    // constant inputs.  This also avoids scanning sparse MemMerge input arrays.
+    // Watch only this small prefix, including an unsupported node that may fold.
     private static final Node[] TINYBODY = new Node[15]; // Tiny worklist
-    private int smallBody(FunNode fun) {
+    private boolean smallBody(FunNode fun) {
         ReturnNode ret = fun.ret();
         for( Node in : ret._inputs )
             if( in!=null ) addDep(in);
-        if( ret.ctrl()!=fun ) return 0;
+        if( ret.ctrl()!=fun ) return false;
         TINYBODY[0] = fun;
         int len=1;
         for( int i=0; i<len; i++ ) {
             Node n = TINYBODY[i];
             addDep(n);
             if( n==ret ) continue;
-            if( n instanceof ParmNode parm && parm.region()!=fun ) return 0;
+            if( n instanceof ParmNode parm && parm.region()!=fun ) return false;
             if( n!=fun && !(n instanceof ParmNode) &&
                 !(n instanceof StoreNode) && !(n instanceof MemMergeNode) )
-                return 0;
-            if( n.nOuts()>TINYBODY.length ) return 0;
+                return false;                             // Something unexpected
+            if( n.nOuts()>TINYBODY.length ) return false; // Too big
             for( Node use : n._outputs ) {
                 if( use==null ) continue;
                 int j=0;
                 while( j<len && TINYBODY[j]!=use ) j++;
-                if( j<len ) continue;
-                if( len==TINYBODY.length ) { addDep(use); return 0; }
-                TINYBODY[len++] = use;
+                if( j<len ) continue; // Already in TINYBODY
+                if( len==TINYBODY.length ) { addDep(use); return false; } // Too big
+                TINYBODY[len++] = use;  // Add to worklist
             }
         }
-        return len;
+        return true;
+    }
+
+    public void doInline() {
+        assert _inline > 0;    // Only called when possible to inline
+
+        ReturnNode ret = (ReturnNode)in(1);
+        FunNode fun = ret.fun();
+        CallNode call = call();
+        assert fun.sig().isa(call.fptr()._type);
+
+        // Clone first
+        if( _inline==2 ) {
+            assert !CodeGen.CODE._midAssert; // Triggered inlining
+            // Remove the existing function linkage
+            call.unlink_all();
+            // Clone the function body
+            FunNode fun2 = fun.copyBody();
+            // Call uses the unique new function
+            Node fptr2 = new FunPtrNode(fun2.sig(),CodeGen.CODE._start,fun2.ret()).peephole();
+            call.setDef(call.nIns()-1,fptr2);
+            // Link to the new function
+            call.link(fun2);
+            fun = fun2;
+        }
+
+        // Trivial inlining: call site calls a single function; single function
+        // is only called by this call site.
+        doTrivialInlining(fun);
+    }
+
+    boolean goodArgs( CallNode call, TypeFunPtr tfp ) {
+        for( int i=0; i<tfp.nargs(); i++ ) {
+            Node arg = call.arg(i+2);
+            // The graph's function-pointer type can still contain open forward
+            // references here.  Compare against its recursively upgraded form,
+            // so deep mutability requirements participate before inlining.
+            Type formal = tfp.arg(i).upgradeType(Parser.TYPES);
+            if( !arg._type.isa(formal) || !arg._type.accessISA(formal) )
+                { addDep(arg); return  false; }
+        }
+        return true;
+    }
+
+
+    // Do trivial inlining.  Inlining does not need to clone code, merely
+    // triggers folding the Call/Fun and Return/CallEnd away.
+    private boolean doTrivialInlining( FunNode fun ) {
+        assert !CodeGen.CODE._midAssert; // Triggered inlining
+        // Trivial inline: rewrite
+        _folding = true;
+        // Rewrite Fun so the normal RegionNode ideal collapses
+        fun._folding = true;
+        fun.setDef(1,call().ctrl());// Bypass the Call;
+        fun.ret().setDef(3,null);   // Return is folding also
+
+        CodeGen.CODE.addAll(fun._outputs);
+        // Repeat defs 1 layer down, for users of Parm (Phis)
+        for( Node parm : fun._outputs )
+            if( parm instanceof ParmNode )
+                CodeGen.CODE.addAll(parm._outputs);
+
+        // Inlining immediately blows all cache idepth fields past the inline point.
+        // Bump the global version number invalidating them en-masse.
+        CodeGen.CODE.invalidateIDepthCaches();
+        // More peeps
+        CodeGen.CODE.add(fun);
+        CodeGen.CODE.add(this);
+        CodeGen.CODE.addAll(_outputs);
+        CodeGen.CODE.addAll(_inputs);
+        return true;            // Always return true
     }
 
+
     @Override public Node pcopy(int idx) {
         return _folding ? in(1).in(idx) : null;
     }
+
+    @Override public Node copy() {
+        return _folding ? super.copy() : new CallEndNode(_rpc);
+    }
+
 }