diff options
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/codegen')
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 ) |