diff options
Diffstat (limited to 'src')
9 files changed, 218 insertions, 85 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; + }); + } + } diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 3321301b..aa586b17 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -15,22 +15,9 @@ public class CallEndNode extends CFGNode implements MultiNode { private boolean _folding; public boolean folding() { return _folding; } public final TypeRPC _rpc; - // Pessimistic analysis may know more than the written signature. Preserve - // that summary when local SCCP disconnects the callee's return edges. - private Type _retType = Type.BOTTOM; public CallEndNode(CallNode call) { super(new Node[]{call}); _rpc = TypeRPC.constant(_nid); } - public CallEndNode(CallEndNode cend) { super(cend); _rpc = cend._rpc; _retType = cend._retType; } - - public void freezeResult() { - if( _type instanceof TypeTuple tt ) { - unlock(); - _retType = tt.ret(); - } - } - - @Override public boolean eq(Node n) { return _retType==((CallEndNode)n)._retType; } - @Override int hash() { return _retType.hashCode(); } + public CallEndNode(CallEndNode cend) { super(cend); _rpc = cend._rpc; } @Override public String label() { return "CallEnd"; } @Override public boolean blockHead() { return true; } @@ -61,7 +48,7 @@ public class CallEndNode extends CFGNode implements MultiNode { Type ftype = addDep(call.fptr())._type; Type ret = ftype.isHigh() ? Type.TOP : Type.BOTTOM; if( ftype instanceof TypeFunPtr tfp ) { - ret = tfp.ret().join(_retType); + 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 @@ -70,6 +57,16 @@ public class CallEndNode extends CFGNode implements MultiNode { Type tret = in(i)._type instanceof TypeTuple rtt ? rtt.ret() : in(i)._type; ret = ret.meet(tret); } + // Recursion is a loop in disguise. For f(x-1)+1, the result + // flows Return -> CallEnd -> Add -> Phi -> Return, without + // crossing ParmNode.compute's widening point. Widen here too, + // using the loop rule in PhiNode.compute. Keep constants and + // above-center ranges narrow, and stay within the return type. + Type oldret = _type instanceof TypeTuple tt ? tt.ret() : Type.TOP; + if( ret instanceof TypeInteger ti && ret != oldret && + !ti.isHigh() && !ti.isConstant() && + (!(oldret instanceof TypeInteger oldi) || ti._widen <= oldi._widen) ) + ret = ti.same_but_slightly_wider_than(TypeInteger.BOT).join(tfp.ret()); } } return TypeTuple.make(call._type,TypeMem.BOT,ret); diff --git a/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 95934e4b..cc654abb 100644 --- a/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMemPtr; public class ParmNode extends PhiNode { @@ -35,6 +36,21 @@ public class ParmNode extends PhiNode { @Override public boolean inProgress() { return in(0) instanceof FunNode fun && fun.inProgress(); } @Override + public Type compute() { + Type t = super.compute(); + // Recursion is a loop in disguise. A Parm merges the first argument + // with those from recursive calls, just as a loop Phi merges its entry + // and backedge. Use the widening rule in PhiNode.compute here too. + // CallEndNode.compute handles the separate cycle through return values; + // widening this Parm alone cannot stop f(x-1)+1 from growing its result. + if( t instanceof TypeInteger ti && t != _type && + !ti.isHigh() && !ti.isConstant() && + (!(_type instanceof TypeInteger oldi) || ti._widen <= oldi._widen) ) + return ti.same_but_slightly_wider_than(_minType); + return t; + } + + @Override public Node idealize() { if( !(region() instanceof FunNode) ) return in(1); // Input has collapse to e.g. starting control. diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 953e009e..7f2bb1f4 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -81,8 +81,9 @@ public class PhiNode extends Node { Type newt = t.join( _minType ); // Widen loop Phis so integer ranges cannot grow one step per trip forever. - // Calls are opaque during SCCP here. The next chapter also widens at - // ParmNode and CallEndNode when solving through recursive calls. + // Recursion is a loop in disguise: ParmNode.compute widens arguments, + // and CallEndNode.compute widens results. Both are needed because the + // recursive result can feed itself without passing through a Parm. // Above-center ranges may still fall to unwidened constants. // Widen only below-center ranges to preserve monotonicity. if( region() instanceof LoopNode && // Only around loops diff --git a/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/src/test/java/com/seaofnodes/simple/Chapter18Test.java index e5dd259b..b6a0ab57 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -406,8 +406,7 @@ return g(); } - // Local SCCP cannot infer this recursive return type. The next chapter - // solves across calls and checks the same program's execution results. + // Mutual recursion: check results, independent of how much gets inlined. @Test public void testFcnMutRec() { CodeGen code = new CodeGen( @@ -416,8 +415,11 @@ val is_even = { int x -> x ? is_odd (x-1) : true ; }; val is_odd = { int x -> x ? is_even(x-1) : false; }; return is_even(arg); """); - try { code.driver(CodeGen.Phase.TypeCheck); fail(); } - catch( Parser.ParseException e ) { assertEquals("No defined return type",e.getMessage()); } + code.driver(CodeGen.Phase.FinalizeIR); + assertEquals("1", Eval2.eval(code, 0)); + assertEquals("0", Eval2.eval(code, 1)); + assertEquals("1", Eval2.eval(code, 2)); + assertEquals("0", Eval2.eval(code, 3)); } // Forward ref to 'x' means that diff --git a/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/src/test/java/com/seaofnodes/simple/Chapter24Test.java index 4eb1324d..6e0fd95f 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -17,6 +17,20 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter24Test { + @Test public void testRecursiveWidening() { + String[] srcs = { + // Parm(x) must widen even though the recursive result is constant. + "val f = { int x, int limit -> x >= limit ? 0 : f(x+1,limit); }; return f(0,arg);", + // The growing result has its own cycle, which never crosses Parm(x). + "val f = { int x -> x <= 0 ? 0 : f(x-1)+1; }; return f(3);" + }; + for( int i=0; i<srcs.length; i++ ) + for( long seed : new long[]{0,42,126} ) { + var code = new CodeGen(srcs[i],TypeInteger.BOT,seed,true).driver(CodeGen.Phase.LocalSched); + assertEquals(i==0 ? "0" : "3",Eval2.eval(code,3)); + } + } + @Test public void testColdLoopSelfConflict() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coldLoopSelfConflict(); } @Test public void testPrintingDeadFunction() throws Exception { diff --git a/src/test/java/com/seaofnodes/simple/SccpTest.java b/src/test/java/com/seaofnodes/simple/SccpTest.java index afa0ec58..cad1b7de 100644 --- a/src/test/java/com/seaofnodes/simple/SccpTest.java +++ b/src/test/java/com/seaofnodes/simple/SccpTest.java @@ -7,25 +7,17 @@ import org.junit.Test; import static org.junit.Assert.*; public class SccpTest { - @Test public void testLoopFixedPoint() { - var code = new CodeGen("int x=1; while(arg) { x=2-x; arg--; } return x;").parse().iter(); - assertFalse(code.link(code._main).ret().expr()._type.isConstant()); - code.opto(); - assertSame(TypeInteger.TRUE,code.link(code._main).ret().expr()._type); - code.driver(CodeGen.Phase.LocalSched); - assertEquals("1",Eval2.eval(code,4)); - } - - @Test public void testConservativeCalls() { + @Test public void testCallArgumentFlow() { var code = new CodeGen("val f={ int x -> x+1; }; return f(1)+f(2);").parse().iter().opto(); int[] parms = {0}; code._start.walk(n -> { if( n instanceof ParmNode p && "x".equals(p._label) ) { parms[0]++; - assertSame(TypeInteger.BOT,p._type); - assertTrue(p.fun().in(1) instanceof StartNode); + TypeInteger t = (TypeInteger)p._type; + assertEquals(1,t._min); + assertEquals(2,t._max); + assertFalse(p.fun().in(1) instanceof StartNode); } - if( n instanceof CallEndNode cend ) assertEquals(1,cend.nIns()); return null; }); assertEquals(1,parms[0]); |