diff options
Diffstat (limited to 'chapter25/src/main/java/com')
10 files changed, 68 insertions, 65 deletions
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java index d2611b32..d4b84828 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -52,6 +52,7 @@ public class IterPeeps { public final WorkList<Node> _work; final WorkList<CallEndNode> _workInline; + private int _cnt; public IterPeeps( long seed ) { _work = new WorkList<>(seed); @@ -98,13 +99,12 @@ public class IterPeeps { // Run all the code-reduction and type-lifting peeps as possible private void iteratePeeps( CodeGen code ) { - assert !CodeGen.expensiveAssert(1) || (progressOnList(code, _work) && schedulableUses(code)); - int cnt=0; + 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 + _cnt++; // Useful for debugging, searching which peephole broke things Node x = n.peepholeOpt(); if( n instanceof CallEndNode cend ) _workInline.push(cend); @@ -135,7 +135,7 @@ public class IterPeeps { n.moveDepsToWorklist(); JSViewer.show(); // Show again // Very expensive assert. - assert !CodeGen.expensiveAssert(cnt) || (progressOnList(code, _work) && schedulableUses(code)); + assert !CodeGen.expensiveAssert(_cnt) || (progressOnList(code, _work) && schedulableUses(code)); } if( n.isUnused() ) { assert !(n instanceof StopNode); // StopNodes can die if all code in the compunit dies @@ -162,13 +162,11 @@ public class IterPeeps { public static boolean progressOnList(CodeGen code, WorkList<Node> list ) { code._midAssert = true; Node changed = code._stop.walk( n -> { - Node m = n; - Type nval = n.compute(); // Ignore most in-progress things if( n.iskeep() ) return null; - // Types must be forwards, even if on the worklist. - assert nval.isa(n._type) : "Non-monotonic peep: "+n+"#"+n._nid+" old="+n._type+" new="+nval+" inputs="+inputTypes(n)+" peep="+m; + 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 ) { @@ -176,9 +174,10 @@ public class IterPeeps { 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; - m = n.peepholeOpt(); + 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; }); @@ -197,25 +196,26 @@ public class IterPeeps { // 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) { - IdentityHashMap<Node,CFGNode> earlyCache = new IdentityHashMap<>(); + 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; - CFGNode early = CFGNode.earlyCFG(n,code._start,earlyCache,new BitSet()); - if( early == null || early == code._start ) - 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._idom(lca,null); } - if( lca == null ) - return null; - if( !early.sameFun(lca) ) - return null; + if( lca == null ) return null; + if( !early.sameFun(lca) ) return null; assert early.dominates(lca) : badSchedule(n,early,lca); return null; }); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java index c5ceda41..cde88ffa 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -94,7 +94,18 @@ public abstract class CFGNode extends Node { // Safe read of the control input of a data node. public static CFGNode safeCFG(Node n) { - return n != null && n.in(0) instanceof CFGNode cfg ? cfg : null; + if( n==null ) return null; + if( !(n.in(0) instanceof CFGNode cfg) ) return null; + return cfg._safeCFG(); + } + private CFGNode _safeCFG() { + return switch(this) { + case CallNode call when call.cend()._folding -> call.cfg0()._safeCFG(); + case CallEndNode cend when cend._folding -> cend.cfg(1)._safeCFG(); + case FunNode fun when fun._folding -> fun.cfg(1)._safeCFG(); + case ReturnNode ret when ret.fun()._folding -> ret.cfg0()._safeCFG(); + default -> this; + }; } // True when this node dominates `sub` in the current idom tree. @@ -105,56 +116,44 @@ public abstract class CFGNode extends Node { return false; } - public boolean sameFun(CFGNode that) { - FunNode fun = fun(); - return fun != null && fun == that.fun(); - } - - public static boolean sameFun(CFGNode a, CFGNode b) { - return a != null && b != null && a.sameFun(b); - } - public static CFGNode deepest(CFGNode a, CFGNode b) { if( a == null ) return b; if( b == null ) return a; return b.idepth() > a.idepth() ? b : a; } - public static CFGNode earlyCFG(Node n, CFGNode start) { - return earlyCFG(n,start,new IdentityHashMap<>(),new BitSet()); + public static CFGNode earlyCFG(Node n) { + return earlyCFG(n,new IdentityHashMap<>(),new BitSet()); } - public static CFGNode earlyCFG(Node n, CFGNode start, IdentityHashMap<Node,CFGNode> cache, BitSet active) { - if( n == null ) - return null; + public static CFGNode earlyCFG(Node n, IdentityHashMap<Node,CFGNode> cache, BitSet active) { + if( n == null ) return null; CFGNode cached = cache.get(n); - if( cached != null ) - return cached; + if( cached != null ) return cached; if( active.get(n._nid) ) return safeCFG(n); active.set(n._nid); - CFGNode early = start; - if( n.in(0) instanceof CFGNode cfg ) - early = cfg; - for( int i=1; i<n.nIns(); i++ ) - early = deepest(early,defCFG(n.in(i),start,cache,active)); + CFGNode early = null; + for( Node x : n._inputs ) + early = deepest(early,defCFG(x,cache,active)); active.clear(n._nid); cache.put(n,early); return early; } - private static CFGNode defCFG(Node n, CFGNode start, IdentityHashMap<Node,CFGNode> cache, BitSet active) { - if( n == null ) - return null; - if( n instanceof PhiNode phi ) - return phi.region(); - if( n instanceof CFGNode cfg ) - return cfg; - if( n instanceof ProjNode ) - return safeCFG(n); - if( n.isConst() ) - return start; - return earlyCFG(n,start,cache,active); + private static CFGNode defCFG(Node n, IdentityHashMap<Node,CFGNode> cache, BitSet active) { + if( n == null || n.isConst() ) return null; // no impact on early cfg + return switch( n ) { + case PhiNode phi -> phi.region(); + case CFGNode cfg -> cfg; + case ProjNode projNode -> safeCFG( n ); + default -> earlyCFG( n, cache, active ); + }; + } + + public boolean sameFun(CFGNode that) { + FunNode fun = fun(); + return fun != null && fun == that.fun(); } // Anti-dependence field support diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java index 9ce97ac6..51d10702 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -128,11 +128,11 @@ public class CallNode extends CFGNode { // Link so this calls fun public Node link( FunNode fun ) { assert !linked(fun); - fun.addDef(this); + CodeGen.CODE.add(fun).addDef(this); for( Node use : fun._outputs ) if( use instanceof ParmNode parm ) { Node def = parm._idx==0 ? ConstantNode.seed(cend()._rpc).peephole() : arg(parm._idx); - parm.addDef(def); + CodeGen.CODE.add(parm).addDef(def); // Linking can happen during post-SCCP inlining. Keep an RPC // Parm's cached finite set synchronized with its newly added // input instead of waiting for the next worklist visit. diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/EscapeNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/EscapeNode.java index d1ff3f65..5be4d3e8 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/EscapeNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/EscapeNode.java @@ -90,7 +90,8 @@ public class EscapeNode extends TypeNode { } // New allocation is dead if( self()._type.isHigh() ) - return pub(); + if( pub()._type.isa(_type) ) return pub(); + else addDep(pub()); return null; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java index d9d3e451..274cc146 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -94,8 +94,8 @@ public class FunNode extends RegionNode { for( Node use : ret().outs() ) if( use instanceof CallEndNode || use instanceof FunPtrNode ) CODE.add(use); - _sig = sig; unlock(); + _sig = sig; } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/GuardNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/GuardNode.java index e3c6f0e2..16b83f22 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/GuardNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/GuardNode.java @@ -39,6 +39,12 @@ public class GuardNode extends Node { } @Override public Type compute() { + // Guard is a pinned, path-local fact. If its control path is not + // executable, the fact is not executable either, regardless of how the + // value input sharpens later. + Type c = in(0)._type; + if( c != Type.CONTROL && c != Type.BOTTOM ) + return Type.TOP; Type t = in(1)._type; if( t==Type.BOTTOM || t==Type.TOP ) return t; // The scalar envelope does not identify a value family. Preserve it @@ -50,6 +56,8 @@ public class GuardNode extends Node { } @Override public Node idealize() { + if( in(0)._type != Type.CONTROL && in(0)._type != Type.BOTTOM ) + return null; if( in(1)._type==Type.BOTTOM || in(1)._type==Type.TOP ) return null; if( _type.isHighOrConst() && in(1)._type.isa(_type) ) return in(1); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 3c144b6e..d625b898 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -269,10 +269,7 @@ public class LoadNode extends MemOpNode { Node px = memphi.in(idx); if( px==null ) return false; assert !(px._type instanceof TypeMem mem && mem._t.isHighOrConst() ); - //// To avoid cyclic pushing a Load up then down, getting here means - //// the load *must* replace with the high/constant. - //return true; - if( px instanceof StoreNode st1 && ptr()==addDep(st1.nnptr() ) && off()==st1.off() && st1.val()._type.isa(_type) ) + if( px instanceof StoreNode st1 && ptr()==addDep(st1.nnptr() ) && off()==st1.off() && addDep(st1.val())._type.isa(_type) ) // To avoid cyclic pushing a Load up then down, getting here means // the load *must* match against the Store return true; @@ -304,6 +301,4 @@ public class LoadNode extends MemOpNode { Node shl = new ShlNode(null,val,shf.keep()).peephole(); return new SarNode(null,shl,shf.unkeep()); } - - //@Override public int log_size() { return declaredType().log_size(); } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 1ad9d7a2..4112a977 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -149,7 +149,7 @@ public class PhiNode extends Node { n = guard.in(1); throw Utils.TODO("test and remove TODO"); } - CFGNode early = CFGNode.earlyCFG(n,null); + CFGNode early = CFGNode.earlyCFG(n); return iff.pred()==cast.in(1) && (early==null || early.dominates(r)) ? n : null; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 36765981..57dcd66b 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -535,7 +535,7 @@ public class ScopeNode extends MemMergeNode { private void _addGuards( CFGNode ctrl, Node pred, boolean invert ) { if( pred==null || pred.isDead() ) return; - CFGNode early = CFGNode.earlyCFG(pred,null); + CFGNode early = CFGNode.earlyCFG(pred); if( early != null && !early.dominates(ctrl) ) return; // Short-circuit logic is represented by a Phi. For `a || b` being diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java index f140f28f..faa3d17b 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -146,7 +146,7 @@ public class StoreNode extends MemOpNode { if( useAlias(use)==fld._alias ) { int idx = use._inputs.find(this); assert idx != -1; - use.setDef(idx,st); + CodeGen.CODE.add(use).setDef(idx,st); i--; // setDef removed use from this Store's outputs } } |