Chapter 24a: SCCP Within a Functionlinear-chapter24a

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>

5 files changed, 181 insertions, 30 deletions

diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index 0e4ae3cb..7a24ca30 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -9,6 +9,7 @@ import com.seaofnodes.simple.print.*;
 import com.seaofnodes.simple.type.*;
 import com.seaofnodes.simple.util.Ary;
 import com.seaofnodes.simple.util.SB;
+import com.seaofnodes.simple.util.Utils;
 import java.io.IOException;
 import java.util.*;
 
@@ -23,6 +24,8 @@ public class CodeGen {
     public enum Phase {
         Parse,                  // Build ideal IR from source
         Iter,                   // Pessimistic peepholes
+        Opto,                   // Optimistic SCCP within each function
+        IterPostOpto,           // Peepholes and inlining using SCCP results
         FinalizeIR,             // Finish function cleanup and layouts
         TypeCheck,              // Check the surviving ideal graph
         LoopTree,               // Discover loops and connect nonreturning paths
@@ -45,6 +48,8 @@ public class CodeGen {
         if( target==Phase.Export ) throw new IllegalArgumentException("Use exportELF with an output file or null for memory linking");
         step(target, Phase.Parse, this::parse, dump);
         step(target, Phase.Iter, this::iter, dump);
+        step(target, Phase.Opto, this::opto, dump);
+        step(target, Phase.IterPostOpto, this::iterPostOpto, dump);
         step(target, Phase.FinalizeIR, this::finalizeIR, dump);
         step(target, Phase.TypeCheck, this::typeCheck, dump);
         step(target, Phase.LoopTree, this::loopTree, dump);
@@ -145,7 +150,7 @@ public class CodeGen {
     // are structurally equal.
     public final HashMap<Node,Node> _gvn = new HashMap<>();
 
-    //
+    // Source of unique function indices
     private int _fidx =0;
     public TypeFunPtr makeFun( TypeFunPtr fun ) {
         int fidx = _fidx++;
@@ -153,23 +158,36 @@ public class CodeGen {
         return fun.makeFrom(fidx);
     }
     // Signature for MAIN
-    public final TypeFunPtr _main;
-    // Reverse from a constant function pointer to the IR function being called
-    public FunNode link( TypeFunPtr tfp ) {
-        assert tfp.isConstant();
-        return _linker.get(tfp.makeFrom(Type.BOTTOM));
+    public TypeFunPtr _main;
+    public void setMain(FunNode main) {
+        _main = main.sig();
+        link(main);
+    }
+    // Reverse from a constant function pointer to the IR function being called.
+    // Error to call with a non-constant TFP
+    public FunNode link( TypeFunPtr tfp ) { return link(tfp.fidx());  }
+    // Read-only diagnostic lookup; preserve stale entries.
+    public FunNode _link(TypeFunPtr tfp) { return _link(tfp.fidx()); }
+    public FunNode _link(int fidx) { return _linker.atX(fidx); }
+    // Return the FunNode from a fidx, cleaning up dead entries.
+    public FunNode link( int fidx ) {
+        FunNode fun =_linker.atX(fidx);
+        if( fun!=null && fun.isDead() ) {
+            _linker.setX(fidx,null); fun = null; }
+        return fun;
     }
 
     // Insert linker mapping from constant function signature to the function
     // being called.
     public void link(FunNode fun) {
-        _linker.put(fun.sig().makeFrom(Type.BOTTOM),fun);
+        int fidx = fun.sig().fidx();
+        _linker.setX(fidx,fun);
     }
 
     // "Linker" mapping from constant TypeFunPtrs to heads of function.  These
     // TFPs all have exact single fidxs and their return is wiped to BOTTOM (so
     // the return is not part of the match).
-    private final HashMap<TypeFunPtr,FunNode> _linker = new HashMap<>();
+    final Ary<FunNode> _linker = new Ary<>(FunNode.class);
 
     // Native symbols belong to function identities, not to one ExternNode.
     // Selection and spill copies can turn that node into an ordinary constant.
@@ -202,11 +220,14 @@ public class CodeGen {
     // Pessimistic peepholes reach a fixed point after parsing.
     public CodeGen iter() { return phase(Phase.Iter, _phase==Phase.Parse, () -> _iter.iterate(this)); }
 
-    public CodeGen finalizeIR() { return phase(Phase.FinalizeIR, _phase==Phase.Iter, () -> FinalizeIR.run(this)); }
+    // SCCP computes types and queues changed nodes; Iter applies their rewrites.
+    public CodeGen opto() { return phase(Phase.Opto, _phase==Phase.Iter, () -> Opto.opto(this)); }
+    public CodeGen iterPostOpto() { return phase(Phase.IterPostOpto, _phase==Phase.Opto, () -> _iter.iterate(this)); }
+
+    public CodeGen finalizeIR() { return phase(Phase.FinalizeIR, _phase==Phase.IterPostOpto, () -> FinalizeIR.run(this)); }
     public <N extends Node> N add( N n ) { return _iter.add(n); }
     public void addAll( Ary<Node> ary ) { _iter.addAll(ary); }
 
-
     // ---------------------------
     // Last check for bad programs
     public CodeGen typeCheck() { return phase(Phase.TypeCheck, _phase==Phase.FinalizeIR, () -> TypeCheck.run(this)); }
diff --git a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
index 5c28e85b..019e3892 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
@@ -197,12 +197,16 @@ public class Encoding implements com.seaofnodes.isa.CodeSink {
         rpos.put(_code._start.loop(),rpo);
         BitSet visit = _code.visit();
         rpo.add(_code._stop);
+        FunNode main = _code.link(_code._main);
         for( Node n : _code._start._outputs )
-            if( n instanceof FunNode fun ) {
+            if( n instanceof FunNode fun && fun != main ) {
                 int x = rpo._len;
                 _rpo_cfg(fun, visit, rpos );
                 assert rpo.at(x) instanceof ReturnNode;
             }
+        // Do any main function last... so it lands at offset 0 in the RPO
+        if( main!=null )
+            _rpo_cfg(main, visit, rpos );
         rpo.add(_code._start);
 
         // Reverse in-place
diff --git a/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java
index 55553393..14cf56ba 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java
@@ -5,22 +5,20 @@ import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
 import java.util.Arrays;
 
-// Finish the ideal graph before type checking and scheduling.
+// Settle layouts and detach the analyzed call graph before the backend.
 abstract class FinalizeIR {
     static void run(CodeGen code) {
-        // Not really a true optimistic pass, but look for unlinked functions.
-        // This can be removed, which may trigger another round of pessimistic.
-        // This is the point where we flip from a virtual Call Graph (any call
-        // can call any function) to having a correct (but conservative) CG.
-        int progress = 0;
+        // 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.nIns()==2 && fun.in(1)==code._start && fun != main && !fun.hasPtr() &&
-                    (fun._name==null || fun._name.startsWith("sys.")) ) {
+                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--;
@@ -28,9 +26,15 @@ abstract class FinalizeIR {
             }
             code._iter.iterate(code);
         }
+        fieldSizes(code);
+        code._iter.iterate(code);
+        removeCallGraph(code);
+        Arrays.sort(code._stop._inputs._es,0,code._stop.nIns(),(x,y) -> x._nid - y._nid);
+    }
 
-        // Freeze field sizes; do struct layouts; convert field offsets into
-        // constants.
+    // 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 ) {
@@ -39,10 +43,52 @@ abstract class FinalizeIR {
                 i--;
             }
         }
-        code._iter.iterate(code);
+    }
+
+    // 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;
+            } );
 
-        // 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 );
+    }
 
+    // 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;
     }
+
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java
new file mode 100644
index 00000000..e6334414
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java
@@ -0,0 +1,53 @@
+package com.seaofnodes.simple.codegen;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.util.Ary;
+
+// Sparse conditional constant propagation within each function.
+abstract public class Opto {
+
+    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.
+        Node n;
+        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);
+            n.moveDepsToWorklist(code._iter);
+            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;
+        });
+    }
+
+    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;
+        });
+        return true;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index 51ca3a1a..565fa6ba 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -60,6 +60,9 @@ public class RegAlloc {
     // -----------------------
     // Live ranges with self-conflicts or no allowed registers
     private final IdentityHashMap<LRG,String> _failed = new IdentityHashMap<>();
+    // Loop Phis get one chance to color after only cold self-conflict splits.
+    // If the same Phi self-conflicts again, split its hot def/backedge also.
+    private final IdentityHashMap<PhiNode,String> _deferredLoopSelf = new IdentityHashMap<>();
     void fail( LRG lrg ) {
         assert lrg.leader();
         _failed.put(lrg,"");
@@ -341,6 +344,7 @@ public class RegAlloc {
         rclass.push(rmask);
     }
 
+
     // Self conflicts require Phis (or two-address).
     // Insert a split after every def.
     boolean splitSelfConflict( byte round, LRG lrg ) {
@@ -348,6 +352,19 @@ public class RegAlloc {
         Node[] conflicts = lrg._selfConflicts.keySet().toArray(new Node[0]);
         Arrays.sort(conflicts, (x,y) -> x._nid - y._nid );
 
+        // First encounter with a loop Phi: try only cold splits this round.
+        // Remember the Phi across rounds so a persistent self-conflict forces
+        // the hot def/backedge splits on the next encounter.
+        IdentityHashMap<PhiNode,String> deferred = new IdentityHashMap<>();
+        for( Node def : conflicts ) {
+            if( def instanceof PhiNode phi && phi.region() instanceof LoopNode )
+                deferLoopSelf(phi,deferred);
+            for( Node use : def._outputs )
+                if( use instanceof PhiNode phi && phi.region() instanceof LoopNode &&
+                    phi._inputs.find(def)==2 )
+                    deferLoopSelf(phi,deferred);
+        }
+
         // For all conflicts
         for( Node def : conflicts ) {
             assert lrg(def)==lrg; // Might be conflict use-side
@@ -356,6 +373,7 @@ public class RegAlloc {
             for( int i=0; i<def._outputs._len; i++ ) {
                 Node use = def.out(i);
                 if( (use instanceof PhiNode phi &&
+                     !(deferred.containsKey(phi) && phi.region() instanceof LoopNode && phi._inputs.find(def)==2) &&
                      !(phi.region() instanceof LoopNode loop && phi.in(2)==def && def.cfg0().idepth() > loop.idepth() ) ) ||
                         (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) )
                     insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg );
@@ -364,11 +382,13 @@ public class RegAlloc {
             // shared with another Phi: otherwise the shared input keeps the
             // conflicting live ranges joined, even after splitting the entry.
             if( def instanceof PhiNode phi && !(def instanceof ParmNode) ) {
-                SplitNode split = makeSplit("def/self",round,lrg);
-                insertAfterAndReplace(split,def,false);
-                if( split.nOuts()==0 )
-                    split.killOrdered();
-                for( int i=1; i<phi.nIns(); i++ )
+                if( !deferred.containsKey(phi) ) {
+                    SplitNode split = makeSplit("def/self",round,lrg);
+                    insertAfterAndReplace(split,def,false);
+                    if( split.nOuts()==0 )
+                        split.killOrdered();
+                }
+                for( int i=1; i<(deferred.containsKey(phi) ? 2 : phi.nIns()); i++ )
                     if( i==1 || sharedPhiInput(phi,i) )
                         insertBefore(phi,i,"use/self/phi",round,lrg);
             }
@@ -379,6 +399,13 @@ public class RegAlloc {
         return true;
     }
 
+    private void deferLoopSelf(PhiNode phi, IdentityHashMap<PhiNode,String> deferred) {
+        if( !_deferredLoopSelf.containsKey(phi) ) {
+            _deferredLoopSelf.put(phi,"");
+            deferred.put(phi,"");
+        }
+    }
+
 
     private static boolean sharedPhiInput(PhiNode phi, int i) {
         for( Node use : phi.in(i)._outputs )