Chapter 24b: SCCP Across Functionslinear-chapter24b

Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
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: Hadházy Tamás <helsgithub15@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

3 files changed, 162 insertions, 51 deletions

diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index 7a24ca30..af670bda 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -24,7 +24,7 @@ public class CodeGen {
     public enum Phase {
         Parse,                  // Build ideal IR from source
         Iter,                   // Pessimistic peepholes
-        Opto,                   // Optimistic SCCP within each function
+        Opto,                   // Optimistic interprocedural SCCP
         IterPostOpto,           // Peepholes and inlining using SCCP results
         FinalizeIR,             // Finish function cleanup and layouts
         TypeCheck,              // Check the surviving ideal graph
diff --git a/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java
index 14cf56ba..9e3b3e32 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java
@@ -8,24 +8,6 @@ import java.util.Arrays;
 // Settle layouts and detach the analyzed call graph before the backend.
 abstract class FinalizeIR {
     static void run(CodeGen code) {
-        // SCCP kept conservative entries. Rewrites have now relinked the
-        // surviving calls, so remove uncalled bodies just as before SCCP.
-        int progress = -1;
-        while( progress != code._start.nOuts() ) {
-            progress = code._start.nOuts();
-            FunNode main = code.link(code._main);
-            for( int i=0; i<code._start.nOuts(); i++ ) {
-                Node use = code._start.out(i);
-                if( use instanceof FunNode fun && fun != main &&
-                    fun.nIns()==2 && fun.in(1)==code._start && !fun.hasPtr() &&
-                    (main!=null || fun._name==null || fun._name.startsWith("sys.")) ) {
-                    code.add(fun).setDef(1,Parser.XCTRL);
-                    code.addAll(fun._outputs);
-                    i--;
-                }
-            }
-            code._iter.iterate(code);
-        }
         fieldSizes(code);
         code._iter.iterate(code);
         removeCallGraph(code);
diff --git a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java
index e6334414..9f07c1d1 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/Opto.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java
@@ -1,53 +1,182 @@
 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;
 
-// Sparse conditional constant propagation within each function.
+// Optimistic Algorithm
 abstract public class Opto {
 
+    // Optimistic analysis - extended SCCP
+
+    // Start all Types at TOP, and propagate changes until stable.  Unlike a
+    // normal Sparse Conditional Constant Propagation, this version is
+    // interprocedural, computing effectively CFA0 in linear time using the
+    // normal SCCP algorithm.
+
+    // This algo also builds a Call Graph; as Calls become reachable (CONTROL
+    // not TOP nor XCONTROL), they "link" against the reaching function
+    // pointers - adding edges from the Call to the Fun, and from the Return to
+    // the CallEnd.  This allows the normal algorithm to use the normal edge
+    // propagation rules as function argument types stabilize.  In the end, we
+    // get a fairly precise set of Call Graph edges between CallNodes and
+    // FunNodes.
     public static void opto(CodeGen code) {
-        Ary<Type> oldTypes = new Ary<>(Type.class);
-        code._start.walk(n -> {
-            oldTypes.setX(n._nid,n._type);
-            if( n instanceof CallEndNode cend ) cend.freezeResult();
-            n._type = Type.TOP;
-            code.add(n);
-            // Calls retain their signature and whole-memory effects, but do
-            // not pass optimistic values between functions in this chapter.
-            if( n instanceof CallNode call ) call.unlink_all();
-            return null;
-        });
-        // Keep each function's unknown-caller Start input. Its parameters
-        // receive their declared types, independently of the actual calls.
-        // The next chapter removes those inputs and discovers call edges.
+
+        // 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);
+
+
+        // OPTIMISTIC INTERPROCEDURAL SCCP
+        sccp(code, oldTypes);
+
+        // After SCCP add everything changed to the worklist and see if
+        // peepholes can make more progress.
+        moveChangesToWorklist(code, oldTypes);
+
+
+    }
+
+    // Reset Types before running the worklist algorithm
+    private static void resetToTop(CodeGen code, Ary<Type> oldTypes ) {
+        code._start.walk( x -> {
+                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;
+            } );
+    }
+
+
+    // 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);
+            }
+        }
+    }
+
+    // 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;
+    }
+
+    // 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);
+            // 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) ) {
+                call.link( fun );
+                code._iter.add(fun);
+                code._iter.addAll(fun._outputs);
+            }
+        }
+    }
+
+    // The core SCCP algorithm
+    private static void sccp( CodeGen code, Ary<Type> oldTypes ) {
+        // Iter workList is empty at this point
+        // OPTIMISTIC PASS
         Node n;
+        int count = 0;          // Debug counter
         while( (n = code._iter._work.pop()) != null ) {
             if( n.isDead() ) continue;
-            Type old = n._type, next = n.compute();
-            if( old == next ) continue;
-            assert old.isa(next); // Optimistic types only fall.
-            assert next.isa(oldTypes.at(n._nid)) : n.getClass().getSimpleName()+"#"+n._nid+" old="+oldTypes.at(n._nid)+" next="+next;
-            n._type = next;
-            code.addAll(n._outputs);
+            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
+            n._type = nval;
+
+            // If a TFP adds a new function input to a call, link to the new Fun
+            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 )
+                linkCG(code,call.tfp(),call);
+
+            // 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);
         }
-        code._start.walk(x -> {
-            assert x.compute() == x._type;
-            assert x._type.isa(oldTypes.at(x._nid));
-            code.add(x); // Run the rewrites enabled by the new types.
-            return null;
-        });
     }
 
+    // Quadratic (expensive) small-step assert
     private static boolean check(CodeGen code) {
-        code._start.walk(n -> {
-            Type next = n.compute();
-            assert next == n._type || (n._type.isa(next) && code._iter._work.on(n));
-            return null;
-        });
+        code._start.walk( x -> {
+                Type xval = x.compute();
+                assert xval == x._type || (x._type.isa( xval ) && code._iter._work.on( x ));
+                return null;
+            });
         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);
+                return null;
+            });
+    }
+
 }