Mercurial > hg > truffle
changeset 19600:b92530cb27df
Move commutative GVN into CanonicalizerPhase.
line wrap: on
line diff
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Thu Feb 26 11:26:34 2015 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java Thu Feb 26 17:22:08 2015 +0100 @@ -41,6 +41,7 @@ import com.oracle.graal.graph.Node.OptionalInput; import com.oracle.graal.graph.Node.Successor; import com.oracle.graal.graph.spi.*; +import com.oracle.graal.graph.spi.Canonicalizable.BinaryCommutative; import com.oracle.graal.nodeinfo.*; /** @@ -118,6 +119,11 @@ private final boolean isCanonicalizable; /** + * Determines if this node type implements {@link BinaryCommutative}. + */ + private final boolean isCommutative; + + /** * Determines if this node type implements {@link Simplifiable}. */ private final boolean isSimplifiable; @@ -133,6 +139,7 @@ assert NODE_CLASS.isAssignableFrom(clazz); this.isCanonicalizable = Canonicalizable.class.isAssignableFrom(clazz); + this.isCommutative = BinaryCommutative.class.isAssignableFrom(clazz); if (Canonicalizable.Unary.class.isAssignableFrom(clazz) || Canonicalizable.Binary.class.isAssignableFrom(clazz)) { assert Canonicalizable.Unary.class.isAssignableFrom(clazz) ^ Canonicalizable.Binary.class.isAssignableFrom(clazz) : clazz + " should implement either Unary or Binary, not both"; } @@ -238,6 +245,13 @@ } /** + * Determines if this node type implements {@link BinaryCommutative}. + */ + public boolean isCommutative() { + return isCommutative; + } + + /** * Determines if this node type implements {@link Simplifiable}. */ public boolean isSimplifiable() {
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/spi/Canonicalizable.java Thu Feb 26 11:26:34 2015 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/spi/Canonicalizable.java Thu Feb 26 17:22:08 2015 +0100 @@ -128,4 +128,27 @@ return canonical(tool, getX(), getY()); } } + + /** + * This sub-interface of {@link Canonicalizable.Binary} is for nodes with two inputs where the + * operation may be commutative. It is used to improve GVN by trying to merge nodes with the + * same inputs in different order. + */ + public interface BinaryCommutative<T extends Node> extends Binary<T> { + + /** + * Test whether this node is commutative. + */ + boolean isCommutative(); + + /** + * Ensure a canonical ordering of inputs for commutative nodes to improve GVN results. Order + * the inputs by increasing {@link Node#id} and call {@link Graph#findDuplicate(Node)} on + * the node if it's currently in a graph. It's assumed that if there was a constant on the + * left it's been moved to the right by other code and that ordering is left alone. + * + * @return the original node or another node with the same input ordering + */ + Node maybeCommuteInputs(); + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BinaryOpLogicNode.java Thu Feb 26 11:26:34 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BinaryOpLogicNode.java Thu Feb 26 17:22:08 2015 +0100 @@ -28,7 +28,7 @@ import com.oracle.graal.nodes.spi.*; @NodeInfo -public abstract class BinaryOpLogicNode extends LogicNode implements LIRLowerable, Canonicalizable.Binary<ValueNode> { +public abstract class BinaryOpLogicNode extends LogicNode implements LIRLowerable, Canonicalizable.BinaryCommutative<ValueNode> { public static final NodeClass<BinaryOpLogicNode> TYPE = NodeClass.create(BinaryOpLogicNode.class); @Input protected ValueNode x;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AddNode.java Thu Feb 26 11:26:34 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AddNode.java Thu Feb 26 17:22:08 2015 +0100 @@ -103,7 +103,7 @@ } else if (forY instanceof NegateNode) { return BinaryArithmeticNode.sub(forX, ((NegateNode) forY).getValue()); } - return this.maybeCommuteInputs(); + return this; } @Override
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java Thu Feb 26 11:26:34 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java Thu Feb 26 17:22:08 2015 +0100 @@ -95,7 +95,7 @@ return reassociate(this, ValueNode.isConstantPredicate(), forX, forY); } - return this.maybeCommuteInputs(); + return this; } @Override
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryArithmeticNode.java Thu Feb 26 11:26:34 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryArithmeticNode.java Thu Feb 26 17:22:08 2015 +0100 @@ -37,7 +37,7 @@ import com.oracle.graal.nodes.spi.*; @NodeInfo -public abstract class BinaryArithmeticNode<OP> extends BinaryNode implements ArithmeticLIRLowerable { +public abstract class BinaryArithmeticNode<OP> extends BinaryNode implements ArithmeticLIRLowerable, Canonicalizable.BinaryCommutative<ValueNode> { @SuppressWarnings("rawtypes") public static final NodeClass<BinaryArithmeticNode> TYPE = NodeClass.create(BinaryArithmeticNode.class); @@ -62,6 +62,11 @@ } @Override + public boolean isCommutative() { + return getOp(getX(), getY()).isCommutative(); + } + + @Override public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) { ValueNode result = tryConstantFold(getOp(forX, forY), forX, forY, stamp()); if (result != null) { @@ -252,4 +257,29 @@ } return false; } + + /** + * Ensure a canonical ordering of inputs for commutative nodes to improve GVN results. Order the + * inputs by increasing {@link Node#id} and call {@link Graph#findDuplicate(Node)} on the node + * if it's currently in a graph. It's assumed that if there was a constant on the left it's been + * moved to the right by other code and that ordering is left alone. + * + * @return the original node or another node with the same input ordering + */ + @SuppressWarnings("deprecation") + public BinaryNode maybeCommuteInputs() { + if (!y.isConstant() && x.getId() > y.getId()) { + ValueNode tmp = x; + x = y; + y = tmp; + if (graph() != null) { + // See if this node already exists + BinaryNode duplicate = graph().findDuplicate(this); + if (duplicate != null) { + return duplicate; + } + } + } + return this; + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryNode.java Thu Feb 26 11:26:34 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryNode.java Thu Feb 26 17:22:08 2015 +0100 @@ -68,29 +68,4 @@ this.x = x; this.y = y; } - - /** - * Ensure a canonical ordering of inputs for commutative nodes to improve GVN results. Order the - * inputs by increasing {@link Node#id} and call {@link Graph#findDuplicate(Node)} on the node - * if it's currently in a graph. It's assumed that if there was a constant on the left it's been - * moved to the right by other code and that ordering is left alone. - * - * @return the original node or another node with the same input ordering - */ - @SuppressWarnings("deprecation") - public BinaryNode maybeCommuteInputs() { - if (!y.isConstant() && x.getId() > y.getId()) { - ValueNode tmp = x; - x = y; - y = tmp; - if (graph() != null) { - // See if this node already exists - BinaryNode duplicate = graph().findDuplicate(this); - if (duplicate != null) { - return duplicate; - } - } - } - return this; - } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java Thu Feb 26 11:26:34 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java Thu Feb 26 17:22:08 2015 +0100 @@ -65,6 +65,11 @@ return condition; } + @Override + public boolean isCommutative() { + return condition.isCommutative(); + } + /** * Checks whether unordered inputs mean true or false (only applies to float operations). * @@ -125,9 +130,6 @@ return duplicateModified(convertX.getValue(), convertY.getValue()); } } - if (condition.isCommutative()) { - return this.maybeCommuteInputs(); - } return this; }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerTestNode.java Thu Feb 26 11:26:34 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerTestNode.java Thu Feb 26 17:22:08 2015 +0100 @@ -55,6 +55,11 @@ return LogicConstantNode.contradiction(); } } - return this.maybeCommuteInputs(); + return this; + } + + @Override + public boolean isCommutative() { + return true; } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java Thu Feb 26 11:26:34 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java Thu Feb 26 17:22:08 2015 +0100 @@ -83,7 +83,7 @@ } return reassociate(this, ValueNode.isConstantPredicate(), forX, forY); } - return this.maybeCommuteInputs(); + return this; } @Override
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CanonicalizerPhase.java Thu Feb 26 11:26:34 2015 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CanonicalizerPhase.java Thu Feb 26 17:22:08 2015 +0100 @@ -30,6 +30,7 @@ import com.oracle.graal.graph.Graph.NodeEventListener; import com.oracle.graal.graph.Graph.NodeEventScope; import com.oracle.graal.graph.spi.*; +import com.oracle.graal.graph.spi.Canonicalizable.BinaryCommutative; import com.oracle.graal.nodeinfo.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; @@ -261,6 +262,12 @@ Node canonical; try (AutoCloseable verify = getCanonicalizeableContractAssertion(node)) { canonical = ((Canonicalizable) node).canonical(tool); + if (canonical == node && nodeClass.isCommutative()) { + Canonicalizable.BinaryCommutative<?> commutative = (BinaryCommutative<?>) node; + if (commutative.isCommutative()) { + canonical = commutative.maybeCommuteInputs(); + } + } } if (performReplacement(node, canonical)) { return true;