From b59f51486393b2fae7b0015bc5099c5514c7335a Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 13 Jun 2025 15:42:08 -0700 Subject: Chapter 24b: SCCP Across Functions MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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 Co-authored-by: Hadházy Tamás Co-authored-by: Claude Opus 5 --- .../com/seaofnodes/simple/codegen/CodeGen.java | 2 +- .../com/seaofnodes/simple/codegen/FinalizeIR.java | 18 -- .../java/com/seaofnodes/simple/codegen/Opto.java | 193 +++++++++++++++++---- 3 files changed, 162 insertions(+), 51 deletions(-) (limited to 'src/main/java/com/seaofnodes/simple/codegen') 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 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 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 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 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 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; + }); + } + } -- cgit v1.2.3