diff options
Diffstat (limited to 'chapter10b/src/main/java')
5 files changed, 111 insertions, 25 deletions
diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 55822722..5f096ef7 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -26,6 +26,24 @@ public class LoadNode extends MemOpNode { _declaredType = glb; } + @Override boolean canDrop(MemOpNode other, Node dep) { + return super.canDrop(other,dep) && _declaredType==((LoadNode)other)._declaredType && !clobbered(dep); + } + + // Check only immediate memory users. Stores clobber memory; Phis and + // aggregates might lead to a clobber, so stop rather than search further. + private boolean clobbered(Node dep) { + Node mem = mem(); + mem.addDepForwards(dep); + for( Node use : mem._outputs ) { + if( use==null ) continue; + use.addDepForwards(dep); + if( use instanceof StoreNode || use instanceof PhiNode || + use instanceof MemMergeNode ) return true; + } + return false; + } + @Override public String label() { return "Load"; } diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 08e08bbf..44304bcb 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -21,6 +21,13 @@ public abstract class MemOpNode extends Node { public Node mem() { return in(1); } public Node ptr() { return in(2); } + // Extra conditions for factoring matching memory operations through a Phi. + // The caller has already checked the opcode, input shape and control. + boolean canDrop(MemOpNode other, Node dep) { + ptr().addDep(dep); + return _alias==other._alias && err()==null; + } + @Override boolean eq(Node n) { MemOpNode mem = (MemOpNode)n; // Invariant diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java index f4972f96..55fa6efd 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -15,14 +15,14 @@ import java.util.function.Function; * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public abstract class Node { +public abstract class Node implements Cloneable { /** * Each node has a unique dense Node ID within a compilation context * The ID is useful for debugging, for using as an offset in a bitvector, * as well as for computing equality of nodes (to be implemented later). */ - public final int _nid; + public int _nid; /** * Inputs to the node. These are use-def references to Nodes. @@ -31,7 +31,7 @@ public abstract class Node { * Ordering is required because e.g. "a/b" is different from "b/a". * The first input (offset 0) is often a {@link #isCFG} node. */ - public final ArrayList<Node> _inputs; + public ArrayList<Node> _inputs; /** * Outputs reference Nodes that are not null and have this Node as an @@ -42,7 +42,7 @@ public abstract class Node { * walked in either direction. These outputs are typically used for * efficient optimizations but otherwise have no semantics meaning. */ - public final ArrayList<Node> _outputs; + public ArrayList<Node> _outputs; /** @@ -210,6 +210,7 @@ public abstract class Node { // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { Utils.del(_outputs, Utils.find(_outputs, use)); + moveDepsToWorklist(); // User-count and anti-dependence queries can now change. return _outputs.isEmpty(); } @@ -598,6 +599,20 @@ public abstract class Node { // Does not need to be implemented in isCFG() nodes. Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } + // Exact-class copy preserving operation attributes, with fresh identity + // and no edges, dependencies, or GVN membership. + public final Node copyEmpty() { + Node n; + try { n = (Node)clone(); } + catch( CloneNotSupportedException e ) { throw new AssertionError(e); } + n._nid = UNIQUE_ID++; + n._inputs = new ArrayList<>(); + n._outputs = new ArrayList<>(); + n._deps = null; + n._hash = 0; + return n; + } + // Report any post-optimize errors String err() { return null; } diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 650edd6b..cdb4b7cc 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -70,23 +70,9 @@ public class PhiNode extends Node { if (live != null) return live; - // Pull "down" a common data op. One less op in the world. One more - // Phi, but Phis do not make code. - // Phi(op(A,B),op(Q,R),op(X,Y)) becomes - // op(Phi(A,Q,X), Phi(B,R,Y)). - Node op = in(1); - if( !isMem() && op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { - Node[] lhss = new Node[nIns()]; - Node[] rhss = new Node[nIns()]; - lhss[0] = rhss[0] = in(0); // Set Region - for( int i=1; i<nIns(); i++ ) { - lhss[i] = in(i).in(1); - rhss[i] = in(i).in(2); - } - Node phi_lhs = new PhiNode(_label, _declaredType,lhss).peephole(); - Node phi_rhs = new PhiNode(_label, _declaredType,rhss).peephole(); - return op.copy(phi_lhs,phi_rhs); - } + // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). + Node down; + if( same_op() && (down=drop_same_op())!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -116,12 +102,72 @@ public class PhiNode extends Node { } private boolean same_op() { - for( int i=2; i<nIns(); i++ ) - if( in(1).getClass() != in(i).getClass() ) - return false; + Node op = in(1); + if( op.isCFG() || op instanceof ConstantNode || op instanceof PhiNode || + op instanceof ProjNode || op instanceof NewNode || op instanceof ScopeNode || op instanceof MemMergeNode ) return false; + // A bulk Phi must split its aliases before factoring precise Stores. + if( this instanceof BulkMemPhiNode ) return false; + // Bulk splitting currently identifies parallel slices by Region/alias. + // Factoring can introduce another slice at a different memory point; + // wait until that Region's bulk partitioning has finished. + if( op instanceof MemOpNode ) + for( Node use : region()._outputs ) + if( use instanceof BulkMemPhiNode ) { + use.addDepForwards(this); + return false; + } + Node busy = null; + for( int i=1; i<nIns(); i++ ) { + Node n = in(i); + if( region().in(i).addDep(this)._type==Type.XCONTROL || + op.getClass()!=n.getClass() || n.nIns()!=op.nIns() || n.in(0)!=null || !op.eq(n) ) return false; + if( n instanceof MemOpNode mem && !mem.canDrop((MemOpNode)op,this) ) return false; + // Moving a Store must remove the old effect, not duplicate it. + // Allow one shared arm: the other arms disappear into the single + // factored operation, usually reducing the total operation count. + n.addDepForwards(this); + if( n.nOuts()>1 ) { + for( Node use : n._outputs ) + if( use!=null && use!=this ) use.addDepForwards(this); + if( n instanceof StoreNode || busy!=null ) return false; + busy=n; + } + for( int j=1; j<n.nIns(); j++ ) + if( n.in(j) instanceof ScopeNode || ((n.in(j)==null) != (op.in(j)==null)) ) return false; + } return true; } + private Node drop_same_op() { + Node op = in(1), cp = op.copyEmpty(); + cp._type = null; + cp.addDef(null); + for( int j=1; j<op.nIns(); j++ ) { + Node x = op.in(j); + boolean different = false; + for( int i=2; i<nIns(); i++ ) + if( in(i).in(j)!=x ) different=true; + if( different ) { + Node[] ins = new Node[nIns()]; + ins[0] = region(); + Type t = Type.TOP; + for( int i=1; i<nIns(); i++ ) { + ins[i] = in(i).in(j); + t = t.meet(ins[i]._type); + } + PhiNode phi = j==1 && op instanceof MemOpNode mem + ? new MemPhiNode(_label,mem._alias,ins) + : PhiNode.make(_label,t.glb(),ins); + x = phi.peephole(); + } + cp.addDef(x); + } + // Factoring must not widen the result (e.g. correlated And operands). + if( cp.compute().isa(compute()) ) return cp; + cp.kill(); + return null; + } + /** * If only single unique input, return it */ diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index f7a56503..a6b8d834 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -67,7 +67,7 @@ public class RegionNode extends Node { if( !hasPhi() && // No Phi users, just a control user in(1) instanceof ProjNode p1 && in(2) instanceof ProjNode p2 && - p1.in(0)==p2.in(0) && + p1.addDepForwards(this).in(0)==p2.addDepForwards(this).in(0) && p1.in(0) instanceof IfNode iff ) return iff.ctrl(); |