diff options
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/codegen')
12 files changed, 364 insertions, 16 deletions
diff --git a/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java index 9a544685..3547b86c 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Lexer; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; @@ -76,7 +77,7 @@ public class ClassInitDependencies { // Return the outgoing init edge set for this function private static int[] walk( CodeGen code, FunNode fun, Ary<CFGNode> work, IntHashMap iset, BitSet visit, - Ary<Parser.Lexer> sites) { + Ary<Lexer> sites) { if( fun.summary()!=null ) return fun.summary()._classDependencyFIDXs; // Walk function body, looking for outgoing init edges assert iset .isEmpty(); // int hash set for de-dup @@ -164,7 +165,7 @@ public class ClassInitDependencies { Ary<CFGNode> work = new Ary<>(CFGNode.class); IntHashMap iset = new IntHashMap(0); BitSet visit = new BitSet(); - Ary<Parser.Lexer> sites = new Ary<>(Parser.Lexer.class); + Ary<Lexer> sites = new Ary<>(Lexer.class); for( int i=idx; i<_sp; i++ ) { int src = _stk[i]; FunNode fun = _code.link(src); @@ -175,7 +176,7 @@ public class ClassInitDependencies { for( int dst : _edgess[src] ) if( members.get(dst) ) { sb.p("\n ").p(name(src)).p(" -> ").p(name(dst)); - Parser.Lexer loc = sites.atX(dst); + Lexer loc = sites.atX(dst); if( loc!=null && loc._cu!=null ) sb.p('\n').p(SourceError.format(loc._cu,loc.pos(),"cyclic class initialization")); else if( fun!=null && fun.isClz() && dst!=0 && fun._compunit._par==_code.link(dst)._compunit ) diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 67176710..bdb510b4 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -1,8 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.graph.GraphObserver; -import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.*; import com.seaofnodes.simple.type.*; diff --git a/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java index 8b303008..2b091b3c 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeStruct; diff --git a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index 067f431a..8b868218 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.IRPrinter; import com.seaofnodes.simple.type.*; diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index a1ac4e67..86cb2e98 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.IterPeeps.WorkList; +import com.seaofnodes.simple.codegen.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; diff --git a/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java b/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java new file mode 100644 index 00000000..543a69df --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java @@ -0,0 +1,349 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.node.*; +import java.util.Arrays; +import java.util.BitSet; +import java.util.IdentityHashMap; +import java.util.Random; + +/** + * The IterPeeps runs after parsing. It iterates the peepholes to a fixed point + * so that no more peepholes apply. This should be linear because peepholes rarely + * (never?) increase code size. The graph should monotonically reduce in some + * dimension, which is usually size. It might also reduce in e.g. number of + * MulNodes or Load/Store nodes, swapping out more "expensive" Nodes for cheaper + * ones. + * <br> + * The theoretical overall worklist is mindless just grabbing the next thing and + * doing it. If the graph changes, put the neighbors on the worklist. + * <br> + * Lather, Rinse, Repeat until the worklist runs dry. + * <p> + * The main issues we have to deal with: + * + * <ul> + * <li>Nodes have uses; replacing some set of Nodes with another requires more graph + * reworking. Not rocket science, but it can be fiddly. Its helpful to have a + * small set of graph munging utilities, and the strong invariant that the graph + * is stable and correct between peepholes. In our case `Node.subsume` does + * most of the munging, building on our prior stable Node utilities.</li> + * + * <li>Changing a Node also changes the graph "neighborhood". The neighbors need to + * be checked to see if THEY can also peephole, and so on. After any peephole + * or graph update we put a Nodes uses and defs on the worklist.</li> + * + * <li>Our strong invariant is that for all Nodes, either they are on the worklist + * OR no peephole applies. This invariant is easy to check, although expensive. + * Basically the normal "iterate peepholes to a fixed point" is linear, and this + * check is linear at each peephole step... so quadratic overall. It's a useful + * assert, but one we can disable once the overall algorithm is stable - and + * then turn it back on again when some new set of peepholes is misbehaving. + * The code for this is turned on in `IterPeeps.iterate` as `assert + * progressOnList(stop);`</li> + * </ul> + */ +public class IterPeeps { + + public final WorkList<Node> _work; + final WorkList<CallEndNode> _workInline; + private int _cnt; + + public IterPeeps( long seed ) { + _work = new WorkList<>(seed); + _workInline = new WorkList<>(seed); + } + + @SuppressWarnings("unchecked") + public <N extends Node> N add( N n ) { return (N)_work.push(n); } + + public void addAll( Ary<Node> ary ) { _work.addAll(ary); } + + /** + * Iterate peepholes and inlining to a fixed point + */ + public void iterate( CodeGen code ) { + boolean didInline = false; + Ary<Node> defer = new Ary<>(Node.class); + while( true ) { + // Clean up everything that does not grow the code + iteratePeeps(code); + + // Pick an inline candidate, no real heuristic, first come, first served + boolean inlined = false; + CallEndNode cend; + while( (cend = _workInline.pop()) != null) { + if( cend.isDead() ) continue; + if( cend.loadForInline() ) { inlined = true; break; } + byte inline = cend.maybeInline(); + if( inline == -1 ) defer.add(cend); + if( inline > 0 ) { + inlined = true; + break; + } + } + // Inlined, run peeps until clean again + if( inlined ) { didInline = true; continue; } + // No more candidates, check the defer list + if( !didInline ) break; // No more progress, so all the "maybe inline after cleanup" do not progress + // Some inlining happened, retry all the "try again after cleanup" calls + didInline = false; + code.addAll(defer); + defer.clear(); + } + } + + // Run all the code-reduction and type-lifting peeps as possible + private void iteratePeeps( CodeGen code ) { + assert !CodeGen.expensiveAssert(0) || (progressOnList(code, _work) && schedulableUses(code)); + + Node n; + while( (n = _work.pop()) != null ) { + if( n.isDead() ) continue; + _cnt++; // Useful for debugging, searching which peephole broke things + var obs = code._obs; // Collect peephole neighbors for graph display + if( obs != null ) obs.before(n); + Node x = n.peepholeOpt(); + if( n instanceof CallEndNode cend ) + _workInline.push(cend); + if( x != null ) { + assert !x.isDead(); // Peepholes return alive answers + // peepholeOpt can return brand-new nodes, needing an initial type set + if( x._type==null ) x.setType(x.compute()); + // Changes require neighbors onto the worklist + if( x != n || !(x instanceof ConstantNode) ) { + // All outputs of n (changing node) not x (prior existing node). + for( Node z : n._outputs ) _work.push(z); + // Everybody gets a free "go again" in case they didn't get + // made in their final form. + _work.push(x); + // A self-returning peephole can have rewritten its input + // edges. The new defs gained a user and may have + // backwards, user-sensitive peepholes of their own. + for( Node z : x._inputs ) _work.push(z); + // If the result is not self, revisit all inputs (because + // there's a new user), and replace in the graph. + if( x != n ) { + //for( Node z : n. _inputs ) _work.push(z); + for( Node z : x._outputs ) _work.push(z); + n.subsume(x); + } + } + // If there are distant neighbors, move to worklist + n.moveDepsToWorklist(); + // Very expensive assert. + assert !CodeGen.expensiveAssert(_cnt) || (progressOnList(code, _work) && schedulableUses(code)); + } + boolean unused = n.isUnused(); + if( unused ) { + assert !(n instanceof StopNode); // StopNodes can die if all code in the compunit dies + n.kill(); // Just plain dead + } + if( obs != null ) obs.after(n, x!=null ? x : unused ? n : null, true); + } + assert !CodeGen.expensiveAssert(0) || schedulableUses(code); + + } + + // Visit ALL nodes and confirm the invariant: + // Either you are on the _work worklist OR running `iter()` makes no progress. + + // This invariant ensures that no progress is missed, i.e., when the + // worklist is empty we have indeed done all that can be done. To help + // with debugging, the {@code assert} is broken out in a place where it is easy to + // stop if a change is found. + + // Also, the normal usage of `iter()` may attempt peepholes with distance + // neighbors and these should fail, but will then try to add dependencies + // {@link #Node.addDep} which is a side effect in an assert. The {@link + // #midAssert} is used to stop this side effect. + // Pessimistic solver assert + public static boolean progressOnList(CodeGen code, WorkList<Node> list ) { + code._midAssert = true; + Node changed = code._stop.walk( n -> { + // Ignore most in-progress things + if( n.iskeep() ) return null; + // Types must be forwards, even if on the worklist. + Type nval = n.compute(); + assert nval.isa(n._type) : "Non-monotonic peep: "+n+"#"+n._nid+" old="+n._type+" new="+nval+" inputs="+inputTypes(n)+" peep="+n; + if( list.on(n) ) + return null; // On worklist is ok! + if( n instanceof CallEndNode cend ) { + if( code._iter._workInline.on(cend) ) + return null; // On inline worklist is ok! + assert cend.maybeInline() <= 0 : "Inline fired and not on worklist, CallEndNode#"+cend._nid; + } + // Off list: must be live, in GVN table, and no peeps. + assert n.nOuts() > 0 : "Unused live node: "+n; + assert code._gvn.get(n)==n : "Not in GVN table: "+n; + Node m = n.peepholeOpt(); + assert m==null : "Peep fired and not on worklist, "+n.getClass().getSimpleName()+"#"+n._nid+" -> "+m; + return m; + }); + code._midAssert = false; + return changed==null; + } + + private static String inputTypes(Node n) { + StringBuilder sb = new StringBuilder("["); + for( Node in : n._inputs ) + sb.append(in==null ? "null" : in.getClass().getSimpleName()+"#"+in._nid+"="+in+":"+in._type+":keep="+in.iskeep()).append(','); + return sb.append(']').toString(); + } + + // GCM assumes every movable node can be placed no earlier than its inputs + // and no later than the LCA of its uses. Catch graphs where a use escapes + // above an input-defined branch before the later scheduling pass walks off + // the top of the idom tree. + private static final IdentityHashMap<Node,CFGNode> earlyCache = new IdentityHashMap<>(); + private static final BitSet VISIT = new BitSet(); + public static boolean schedulableUses(CodeGen code) { + earlyCache.clear(); + Node bad = code._stop.walk( n -> { + if( n.iskeep() || n.isDead() || n.isConst() || + n instanceof CFGNode || n instanceof PhiNode || n instanceof ProjNode ) + return null; + assert VISIT.isEmpty(); + CFGNode early = CFGNode.earlyCFG(n,earlyCache,VISIT); + VISIT.clear(); + if( early == null ) return null; + CFGNode lca = null; + for( Node use : n._outputs ) { + CFGNode ublk = useBlock(n,use); + if( ublk != null ) + lca = ublk.domLCA(lca,null); + } + if( lca == null ) return null; + if( !early.sameFun(lca) ) return null; + assert early.dominates(lca,null) : badSchedule(n,early,lca); + return null; + }); + return bad == null; + } + + private static CFGNode useBlock(Node n, Node use) { + if( use == null ) + return null; + if( use instanceof PhiNode phi ) { + CFGNode found = null; + for( int i = 1; i<phi.nIns(); i++ ) + if( phi.in(i)==n ) { + if( i >= phi.region().nIns() ) + return null; + found = phi.region().cfg(i).domLCA(found,null); + } + return found; + } + return CFGNode.safeCFG(use); + } + + private static String badSchedule(Node n, CFGNode early, CFGNode lca) { + StringBuilder sb = new StringBuilder("Unschedulable data node ") + .append(n.getClass().getSimpleName()).append('#').append(n._nid) + .append(" early=").append(cfg(early)) + .append(" use-lca=").append(cfg(lca)) + .append(" node=").append(n).append("\ninputs:"); + for( int i = 0; i<n.nIns(); i++ ) { + Node in = n.in(i); + sb.append("\n in").append(i).append(": ").append(node(in)) + .append(" cfg=").append(cfg(CFGNode.safeCFG(in))); + } + sb.append("\noutputs:"); + for( Node use : n._outputs ) + if( use != null ) + sb.append("\n use ").append(node(use)) + .append(" block=").append(cfg(useBlock(n,use))); + return sb.toString(); + } + + private static String node(Node n) { + return n==null ? "null" : n.getClass().getSimpleName()+"#"+n._nid+" "+n; + } + + private static String cfg(CFGNode cfg) { + return cfg==null ? "null" : cfg.getClass().getSimpleName()+"#"+cfg._nid+" "+cfg; + } + + /** + * Classic WorkList, with a fast add/remove, dup removal, random pull. + * The Node's nid is used to check membership in the worklist. + */ + @SuppressWarnings("unchecked") + public static class WorkList<E extends Node> { + + private Node[] _es; + private int _len; + private final BitSet _on; // Bit set if Node._nid is on WorkList + private final Random _R; // For randomizing pull from the WorkList + private final long _seed; + + /* Useful stat - how many nodes are processed in the post parse iterative opt */ + private long _totalWork = 0; + + public WorkList() { this(123); } + WorkList(long seed) { + _es = new Node[1]; + _len=0; + _on = new BitSet(); + _seed = seed; + _R = new Random(); + _R.setSeed(_seed); + } + + /** + * Pushes a Node on the WorkList, ensuring no duplicates + * If Node is null it will not be added. + */ + public E push( E x ) { + if( x==null ) return null; + int idx = x._nid; + if( !_on.get(idx) ) { + _on.set(idx); + if( _len==_es.length ) + _es = Arrays.copyOf(_es,_len<<1); + _es[_len++] = x; + _totalWork++; + } + return x; + } + + public void addAll( Ary<E> ary ) { + for( E n : ary ) + push(n); + } + public void addAll( E[] es ) { + for( E n : es ) + push(n); + } + + + /** + * True if Node is on the WorkList + */ + public boolean on( E x ) { return _on.get(x._nid); } + + /** + * Removes a random Node from the WorkList; null if WorkList is empty + */ + public E pop() { + if( _len == 0 ) return null; + int idx = _R.nextInt(_len); + E x = (E)_es[idx]; + _es[idx] = _es[--_len]; // Compress array + _es[_len] = null; + _on.clear(x._nid); + return x; + } + + public boolean isEmpty() { return _len==0; } + public void clear() { + Arrays.fill(_es,0,_len,null); + _len = 0; + _on.clear(); + _R.setSeed(_seed); + _totalWork = 0; + } + } +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java index 3b1d3182..c3b603e5 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.IterPeeps.WorkList; +import com.seaofnodes.simple.codegen.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; diff --git a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 511e0027..aa997204 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.IterPeeps.WorkList; +import com.seaofnodes.simple.codegen.IterPeeps.WorkList; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; diff --git a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 1d9731fc..1218c956 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.*; import com.seaofnodes.simple.type.*; diff --git a/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index 98350a95..76829151 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; diff --git a/src/main/java/com/seaofnodes/simple/codegen/StaticData.java b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java index a4147576..f813fab5 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/StaticData.java +++ b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.BAOS; diff --git a/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java index a5eaa5ca..c9e53311 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java +++ b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.util.Ary; |