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, 232 insertions, 127 deletions

diff --git a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java
index cd52aadd..132705aa 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/Opto.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java
@@ -1,10 +1,12 @@
 package com.seaofnodes.simple.codegen;
 
-import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
 import com.seaofnodes.simple.util.Ary;
+import com.seaofnodes.simple.util.Utils;
+
 import java.util.Arrays;
+import java.util.BitSet;
 
 // Optimistic Algorithm
 abstract public class Opto {
@@ -24,38 +26,22 @@ abstract public class Opto {
     // get a fairly precise set of Call Graph edges between CallNodes and
     // FunNodes.
     public static void opto(CodeGen code) {
-
-        // Pessimistic peephole optimization on a worklist - this completes
-        // whatever peepholes can run after parsing.
-        code._iter.iterate(code);
-
         // Reset Types before running the worklist algorithm
         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`.
-        boolean wholeWorld = code.link(code._main) != null;
-
-
-        // If wholeWorld, remove the Start inputs to functions - they are not
-        // called unless they get linked (hence go dead and can be removed).
-        // If not wholeWorld, keep only public methods (and not the std lib).
-        unlinkStart(wholeWorld,code);
-
+        unlinkStart(code);
 
         // OPTIMISTIC INTERPROCEDURAL SCCP
         sccp(code, oldTypes);
 
+        // SCCP can leave a recursive numeric component at BOTTOM with no
+        // arithmetic mode selected.  Resolve the whole component from all
+        // available int/float evidence before IterPeeps consumes the types.
+        resolveNumericModes(code);
+
+        if( !code._iter._work.isEmpty() )
+            sccp(code, oldTypes);
+
         // After SCCP add everything changed to the worklist and see if
         // peepholes can make more progress.
         moveChangesToWorklist(code, oldTypes);
@@ -73,15 +59,23 @@ abstract public class Opto {
         // Propagate field size constants
         code._iter.iterate(code);
 
-        // Throw away the Call Graph
 
-        // The remaining passes assume all calls are unlinked; i.e. we are
-        // throwing away the Call Graph here.  Functions only reachable from
-        // internal calls need to be re-hooked to stop/start less they go dead.
-        removeCallGraph(code);
+        // Retain surviving functions in their CompUnits for later code
+        // emission.  Start inputs are semantic: they mean unknown callers.
+        for( FunNode fun : code._linker )
+            if( fun != null && !fun.isDead() && !fun._type.isHigh() )
+                keepInCompUnit(code,fun);
+
+        for( CompUnit cu : code._compunits.values() ) {
+            ProjNode mem = cu._start.proj(1);
+            if( mem != null ) mem.unkeep();
+        }
 
         // To help with testing, sort StopNode Returns by NID
-        Arrays.sort(code._stop._inputs._es,0,code._stop.nIns(),(x,y) -> x._nid - y._nid );
+        for( Node stop : code._stop._inputs )
+            Arrays.sort(stop._inputs._es,0,stop.nIns(),
+                        (x,y) -> ((((ReturnNode)x).fun().isClz() ? -1 : x._nid) -
+                                  (((ReturnNode)y).fun().isClz() ? -1 : y._nid) ));
     }
 
     // Reset Types before running the worklist algorithm
@@ -90,9 +84,6 @@ abstract public class Opto {
                 oldTypes.setX(x._nid,x._type); // Record original types for asserts
                 x._type = Type.TOP;            // Reset all Nodes to TOP
                 code._iter.add(x); // Visit everybody at least once; most Nodes produce better than TOP
-                // Unlink all existing (conservative) linkages.
-                if( x instanceof CallNode call )
-                    call.unlink_all();
                 return null;
             } );
     }
@@ -101,44 +92,55 @@ abstract public class Opto {
     // If wholeWorld, remove the Start inputs to functions - they are not
     // 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) {
-        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
-                fun.removeDeadPath(1);
-                // By same logic, remove stop->return linkage, without
-                // remove the (now dead) ReturnNode; it awaits in limbo
-                // for the opto phase to link to some valid call
-                code._stop._inputs.del(code._stop._inputs.find(fun.ret()));
-                fun.ret().delUse(code._stop);
-            }
+    private static void unlinkStart(CodeGen code) {
+        // Keep the Start & Start.ProjMem alive even as we remove all uses
+        for( CompUnit cu : code._compunits.values() ) {
+            ProjNode mem = cu._start.proj(1);
+            if( mem!=null ) mem.keep();
         }
-    }
 
-    // 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.
-        if( fun.hasPtr() ) return true;
-        // Never true for stdlib or anonymous functions
-        if( fun._name == null || fun._name.startsWith("sys.") )
-            return false;
-        // Named functions (and not stdlib) are callable if not whole-world.
-        return !wholeWorld;
+        // Iterate the Stop-of-Stops
+        for( Node stop : code._stop._inputs ) {
+            for( int i=0; i<stop.nIns(); i++ ) {
+                ReturnNode ret = (ReturnNode)stop.in(i);
+                FunNode fun = ret.fun();
+                // Start is a semantic unknown-caller edge.  Public functions
+                // keep it; closed-world functions must be reached by a
+                // concrete Call edge discovered during SCCP.
+                if( !(code.owns(fun) && fun.isClz()) &&
+                    !code.publicFIDX(fun.sig().fidx()) &&
+                    fun.in(1) instanceof StartNode ) {
+                    fun.removeDeadPath(1);
+                    // Unhook from Stop without treating the ReturnNode as
+                    // DEAD.  It stays in limbo until Opto links when a caller
+                    // is discovered (or not, and the function is really dead).
+                    stop._inputs.del(i--);
+                    ret.delUse(stop);
+                }
+                // Unlink the existing conservative call linkages.
+                for( int j=1; j<fun.nIns(); j++ )
+                    if( fun.in(j) instanceof CallNode call )
+                        call.unlink(fun,j--);
+            }
+        }
     }
 
     // As part of building a CallGraph, when opto finds a function ptr flowing
     // 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
-        for( long fidxs=tfp.fidxs(); fidxs!=0; fidxs=TypeFunPtr.nextFIDX(fidxs) ) {
-            int fidx = Long.numberOfTrailingZeros(fidxs);
-            FunNode fun = code.link(fidx);
+        int[] fidxs = tfp.fidxs();
+        // An unresolved forward call can still carry the infinite, inferred
+        // function set into Opto.  There is no finite call graph to link yet;
+        // type checking will report the unresolved reference afterwards.  This
+        // can yet be valid if the call is eventually dead.
+        //   `if( false ) frefCall(args);`
+        if( XInt.isHigh(fidxs) ) return;
+        for( int fidx = XInt.next(fidxs,0); fidx >=0; fidx = XInt.next(fidxs,fidx) ) {
+            // unlinkStart deliberately leaves uncalled functions in a
+            // temporarily dead limbo.  A newly discovered call revives them;
+            // do not use the cleanup lookup which removes dead linker entries.
+            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) ) {
@@ -149,6 +151,56 @@ abstract public class Opto {
         }
     }
 
+    // Start added some FIDXs, the same functions now can be reached from start
+    // and called by anybody.  Add the CG edges.
+    private static void linkStart( CodeGen code, TypeTuple tt  ) {
+        TypeMem tmem = (TypeMem)tt._types[1];
+        int[] fidxs = tmem._escFs;
+        if( XInt.isHigh(fidxs) ) {
+            // A scalar BOTTOM can flow into memory while compiling an error
+            // program.  It exposes all public functions, not private fields.
+            for( FunNode fun : code._linker )
+                if( fun != null && code.publicFIDX(fun.sig().fidx()) )
+                    linkStart(code,fun);
+            return;
+        }
+        for( int fidx = XInt.next(fidxs,0); fidx >=0; fidx = XInt.next(fidxs,fidx) ) {
+            FunNode fun = code._linker.atX(fidx);
+            if( fun==null )  assert code._externFunc.containsKey(fidx);
+            else             linkStart(code,fun);
+        }
+    }
+
+    // Function is now reachable by unknown callers through Start.  The
+    // default inputs must therefore use conservative declared types.
+    private static void linkStart( CodeGen code, FunNode fun ) {
+        assert !fun.isDead();
+        StartCUNode start = fun._compunit._start;
+        if( fun.nIns() < 2 ) {
+            assert fun.nIns() < 2 || fun.in(1) != start;
+            assert !start.isDead();
+            keepInCompUnit(code,fun);
+            // Function is reachable by any *remote* caller who gets the pointer!
+            fun.insertDef(1,start);
+            code._iter.add(fun);
+            for( Node p : fun._outputs )
+                if( p instanceof ParmNode parm ) {
+                    Node defalt = parm._idx==1 ? start.proj(1) : ConstantNode.seed(parm._declaredType).peephole();
+                    parm.insertDef(1,defalt);
+                    code.add(parm);
+                }
+        }
+    }
+
+    // Keep a surviving function rooted in its compilation unit without
+    // claiming that it has unknown callers.
+    private static void keepInCompUnit(CodeGen code, FunNode fun) {
+        StopCUNode stop = fun._compunit._stop;
+        if( stop._inputs.find(fun.ret()) == -1 )
+            code.add(stop).addDef(fun.ret());
+    }
+
+
     // The core SCCP algorithm
     private static void sccp( CodeGen code, Ary<Type> oldTypes ) {
         // Iter workList is empty at this point
@@ -160,108 +212,161 @@ 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) : "Non-monotonic SCCP: "+n.getClass().getSimpleName()+"#"+n._nid+" "+n+" old="+oval+" new="+nval;    // Types start high and always fall
+            Type pesiVal = oldTypes.atX(n._nid);
+            assert pesiVal==null || nval.isa(pesiVal) : "SCCP below pessimistic type: "+n.getClass().getSimpleName()+"#"+n._nid+" "+n+" 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
+            // Now we have a series of stanzas where we lazily create the Call
+            // Graph - adding graph edges between every call site and called
+            // function, including external (unknown) callers.  These edges are
+            // not in from the start because they are *too many*; we would get
+            // O(n^2) edges.  So all along we have been treating them as
+            // "virtual" CFG edges - a FunNode taking a Start input is treated
+            // as if every call on the planet might call it.  Now we make these
+            // CG edges *concrete*, adding them back as we discover that a call
+            // calls a particular function.
+
+            // If a TFP adds a new function input to a call, link to the new
+            // Fun.  This adds new edges to the graph allowing argument values
+            // to flow from calls into functions.  The added edges are
+            // effectively a refined Call Graph.
             if( nval instanceof TypeFunPtr tfp ) {
                 for( Node use : n._outputs )
                     if( !use._type.isHigh() && use instanceof CallNode call && call.fptr() == n )
                         linkCG(code,tfp,call);
             }
 
-            // Link a Call which becomes alive
-            if( n instanceof CallNode call && oval.isHigh() && !nval.isHigh() && call.fptr()._type instanceof TypeFunPtr )
+            // Link a Call which becomes alive.  Like above, adds new Call
+            // Graph edges to the graph.
+            if( n instanceof CallNode call && nval == Type.CONTROL && call.fptr()._type instanceof TypeFunPtr )
                 linkCG(code,call.tfp(),call);
 
+            // If an otherwise-dead function pointer escapes, any future linked
+            // caller might find and call it.  Force the function to be alive
+            // and called by Start.
+            if( n instanceof StartNode )
+                linkStart(code,(TypeTuple)n._type);
+
             // Since n._type changed, visit all output neighbors
             code._iter.addAll(n._outputs);
             n.moveDepsToWorklist(code._iter);
-            // Quadratic (expensive) small-step assert
-            assert check(code);
+            // Quadratic (expensive) small-step assert.
+            assert !CodeGen.expensiveAssert(count) || worklistCheck(code);
         }
     }
 
-    // Quadratic (expensive) small-step assert
-    private static boolean check(CodeGen code) {
-        code._start.walk( x -> {
+    // Quadratic (expensive) fixed-point assert
+    public static boolean fixedPointCheck(CodeGen code) {
+        return fixedPointCheck(code,code._stop);
+    }
+    public static boolean fixedPointCheck(CodeGen code, Node root) {
+        root.walk( x -> {
                 Type xval = x.compute();
-                assert xval == x._type || (x._type.isa( xval ) && code._iter._work.on( x ));
+                assert xval == x._type;
                 return null;
             });
         return true;
     }
 
+    // Quadratic (expensive) small-step assert for SCCP, where changed nodes
+    // may already be on the worklist.
+    private static boolean worklistCheck(CodeGen code) {
+        code._midAssert = true;
+        Node root = code._start;
+        root.walk( x -> {
+                Type xval = x.compute();
+                assert xval == x._type || (x._type.isa( xval ) && code._iter._work.on( x ))
+                    : "Non-monotonic or missed SCCP work: "+x.getClass().getSimpleName()+"#"+x._nid+" "+x+" old="+x._type+" new="+xval;
+            return null;
+            });
+        code._midAssert = false;
+        return true;
+    }
+
     // After SCCP add everything changed to the worklist and see if peepholes
     // can make more progress.
     private static void moveChangesToWorklist(CodeGen code, Ary<Type> oldTypes) {
         code._start.walk( x -> {
                 assert x.compute() == x._type;      // Hit the fixed point
                 assert x._nid >= oldTypes._len || x._type.isa(oldTypes.at(x._nid)); // Hit at least the bottom-up type
-                code._iter.add(x);
+                code.add(x);
                 return null;
             });
     }
 
+    // Resolve arithmetic modes which are ambiguous only because they belong to
+    // a recursive component.  Float wins because integer operands can be
+    // converted to float.
+    private static void resolveNumericModes(CodeGen code) {
+        final BitSet visited = new BitSet();
+        code._stop.walk(n -> {
+            if( n instanceof ModeNode modeNode && modeNode.mode()==0 ) {
+                visited.clear();
+                visited.set(n._nid); // Inspect inputs, not Bool's integer result
+                int mode = 0;
+                for( int i=1; i<n.nIns(); i++ )
+                    mode |= numericEvidence(n.in(i),visited);
+                // A closed recursive numeric component can have no remaining
+                // concrete evidence after SCCP, e.g. dead all-integer loops.
+                // With no float evidence, settle to integer.
+                if( mode == 0 )
+                    mode = 1;
+                if( mode != 0 )  {
+                    // If both evidence, FP wins
+                    modeNode.setMode((byte)((mode&2)==2 ? 2 : 1));
+                    code.add(n);
+                    code.addAll(n.outs());
+                }
+            }
+            return null;
+        });
+    }
+
+    // Gather numeric evidence through Phi and interprocedural return cycles.
+    // The visited set makes self- and mutually-recursive calls finite.
+    private static int numericEvidence(Node n, BitSet visited) {
+        if( n == null ) return 0;
+        if( visited.get(n._nid) ) return 0;
+        visited.set(n._nid);
+
+        Type t = n._type;
+        if( t instanceof TypeFloat   ) return 2;
+        if( t instanceof TypeInteger ) return 1;
+        if( t!=Type.BOTTOM && !(t instanceof TypeTuple) )
+            return 0; // Something unrelated, like a ptr
+
+        int evidence = 0;
+        assert !(n instanceof ConvertNode); // No test case
+        switch( n ) {
+        case ModeNode modeNode when modeNode.mode() != 0 -> { return modeNode.mode(); }
+        case ModeNode modeNode -> {}
+        case PhiNode phi -> {}
+        case ReturnNode ret -> {}
+        case ProjNode proj when proj.in(0) instanceof CallEndNode cend -> {
+            for( int i=1; i<cend.nIns(); i++ )
+                evidence |= numericEvidence(cend.in(i),visited);
+        }
+        default -> { return 0; }
+        }
+        for( int i=1; i<n.nIns(); i++ )
+            evidence |= numericEvidence(n.in(i),visited);
+
+        return evidence;
+    }
+
+
     // Freeze field sizes; do struct layouts; convert field offsets into
     // constants.
     private static void fieldSizes( CodeGen code ) {
         for( int i=0; i<code._start.nOuts(); i++ ) {
             Node use = code._start.out(i);
             if( use instanceof ConFldOffNode off ) {
-                TypeMemPtr tmp = (TypeMemPtr) Parser.TYPES.get(off._name);
-                off.subsume( off.asOffset(tmp._obj) );
+                Node con = off.asOffset();
+                assert con != null; // Can be null for trying to reference missing field
+                off.subsume( con );
                 i--;
             }
         }
     }
-
-    // The remaining passes assume all calls are unlinked; i.e. we are throwing
-    // away the Call Graph here.  Functions only reachable from internal calls
-    // need to be re-hooked to stop/start less they go dead.
-    private static void removeCallGraph(CodeGen code) {
-        code._start.walk( x -> {
-                // Unlink all existing (conservative) linkages.
-                if( x instanceof CallNode call ) {
-                    for( Node y : call._outputs ) {
-                        // Keep function alive and hooked to Start so it gets
-                        // codegen'd.  Function is callable by this call via
-                        // TFP, although perhaps not by any other means.
-                        if( y instanceof FunNode fun && !(fun.in(1) instanceof StartNode) ) {
-                            ParmNode rpc = fun.rpc();
-                            if( rpc==null ) // Ensure valid RPC
-                                rpc = makeRPC(fun);
-                            // Insert a hook to Start and Stop
-                            fun.insertDef(1,code._start);
-                            for( Node use : fun._outputs )
-                                if( use instanceof ParmNode parm )
-                                    parm.insertDef(1,ConstantNode.make(parm._type).peephole());
-                            code._stop.addDef(fun.ret());
-                        }
-                    }
-                    call.unlink_all();
-                }
-                return null;
-            } );
-
-    }
-
-    // Make a valid Parm RPC.
-    // First make sure a valid RPC; single-call into multi-fun will have each
-    // function having a single call site, so the RPC becomes a constant and
-    // folds - but since multiple targets, the Call never inlines.  Recreate a
-    // valid RPC so codegen (and Eval2) understands the calling convention.
-    private static ParmNode makeRPC( FunNode fun ) {
-        ParmNode rpc = new ParmNode("$rpc",0,fun.ret().rpc()._type,fun);
-        for( int i=1; i<fun.nIns(); i++ ) {
-            CallEndNode cend = ((CallNode)fun.in(i)).cend();
-            rpc.addDef(ConstantNode.make(cend._rpc).peephole());
-        }
-        fun.ret().setDef(3,rpc.init());
-        return rpc;
-    }
-
-
 }