Mercurial > hg > truffle

changeset 19575:b017118b412b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Ensure a canonical ordering of inputs for commutative binary operations
author Tom Rodriguez <tom.rodriguez@oracle.com>
date Wed, 18 Feb 2015 10:36:31 -0800
parents ea8e0540da95
children 4eb793cfec27
files graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BinaryOpLogicNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AddNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatEqualsNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerEqualsNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerTestNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/MulNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/XorNode.java
diffstat 11 files changed, 64 insertions(+), 12 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BinaryOpLogicNode.java	Wed Feb 18 10:19:17 2015 -0800
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BinaryOpLogicNode.java	Wed Feb 18 10:36:31 2015 -0800
@@ -58,4 +58,28 @@
     @Override
     public void generate(NodeLIRBuilderTool gen) {
     }
+
+    /**
+     * 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.
+     *
+     * @return the original node or another node with the same input ordering
+     */
+    @SuppressWarnings("deprecation")
+    public LogicNode maybeCommuteInputs() {
+        if (x.getId() > y.getId()) {
+            ValueNode tmp = x;
+            x = y;
+            y = tmp;
+            if (graph() != null) {
+                // See if this node already exists
+                LogicNode duplicate = graph().findDuplicate(this);
+                if (duplicate != null) {
+                    return duplicate;
+                }
+            }
+        }
+        return this;
+    }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AddNode.java	Wed Feb 18 10:19:17 2015 -0800
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AddNode.java	Wed Feb 18 10:36:31 2015 -0800
@@ -53,7 +53,7 @@
         if (tryConstantFold != null) {
             return tryConstantFold;
         } else {
-            return new AddNode(x, y);
+            return new AddNode(x, y).maybeCommuteInputs();
         }
     }
 
@@ -103,7 +103,7 @@
         } else if (forY instanceof NegateNode) {
             return BinaryArithmeticNode.sub(forX, ((NegateNode) forY).getValue());
         }
-        return this;
+        return this.maybeCommuteInputs();
     }
 
     @Override
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java	Wed Feb 18 10:19:17 2015 -0800
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java	Wed Feb 18 10:36:31 2015 -0800
@@ -51,7 +51,7 @@
         if (tryConstantFold != null) {
             return tryConstantFold;
         } else {
-            return new AndNode(x, y);
+            return new AndNode(x, y).maybeCommuteInputs();
         }
     }
 
@@ -95,7 +95,7 @@
 
             return reassociate(this, ValueNode.isConstantPredicate(), forX, forY);
         }
-        return this;
+        return this.maybeCommuteInputs();
     }
 
     @Override
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryNode.java	Wed Feb 18 10:19:17 2015 -0800
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryNode.java	Wed Feb 18 10:36:31 2015 -0800
@@ -68,4 +68,29 @@
         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	Wed Feb 18 10:19:17 2015 -0800
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java	Wed Feb 18 10:36:31 2015 -0800
@@ -125,6 +125,9 @@
                 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/FloatEqualsNode.java	Wed Feb 18 10:19:17 2015 -0800
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatEqualsNode.java	Wed Feb 18 10:36:31 2015 -0800
@@ -47,7 +47,7 @@
         if (result != null) {
             return result;
         } else {
-            return new FloatEqualsNode(x, y);
+            return new FloatEqualsNode(x, y).maybeCommuteInputs();
         }
     }
 
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerEqualsNode.java	Wed Feb 18 10:19:17 2015 -0800
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerEqualsNode.java	Wed Feb 18 10:36:31 2015 -0800
@@ -65,7 +65,7 @@
                 }
             }
 
-            return new IntegerEqualsNode(x, y);
+            return new IntegerEqualsNode(x, y).maybeCommuteInputs();
         }
     }
 
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerTestNode.java	Wed Feb 18 10:19:17 2015 -0800
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerTestNode.java	Wed Feb 18 10:36:31 2015 -0800
@@ -55,6 +55,6 @@
                 return LogicConstantNode.contradiction();
             }
         }
-        return this;
+        return this.maybeCommuteInputs();
     }
 }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/MulNode.java	Wed Feb 18 10:19:17 2015 -0800
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/MulNode.java	Wed Feb 18 10:36:31 2015 -0800
@@ -54,7 +54,7 @@
         if (tryConstantFold != null) {
             return tryConstantFold;
         } else {
-            return new MulNode(x, y);
+            return new MulNode(x, y).maybeCommuteInputs();
         }
     }
 
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java	Wed Feb 18 10:19:17 2015 -0800
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java	Wed Feb 18 10:36:31 2015 -0800
@@ -51,7 +51,7 @@
         if (tryConstantFold != null) {
             return tryConstantFold;
         } else {
-            return new OrNode(x, y);
+            return new OrNode(x, y).maybeCommuteInputs();
         }
     }
 
@@ -83,7 +83,7 @@
             }
             return reassociate(this, ValueNode.isConstantPredicate(), forX, forY);
         }
-        return this;
+        return this.maybeCommuteInputs();
     }
 
     @Override
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/XorNode.java	Wed Feb 18 10:19:17 2015 -0800
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/XorNode.java	Wed Feb 18 10:36:31 2015 -0800
@@ -52,7 +52,7 @@
         if (tryConstantFold != null) {
             return tryConstantFold;
         } else {
-            return new XorNode(x, y);
+            return new XorNode(x, y).maybeCommuteInputs();
         }
     }
 
@@ -84,7 +84,7 @@
             }
             return reassociate(this, ValueNode.isConstantPredicate(), forX, forY);
         }
-        return this;
+        return this.maybeCommuteInputs();
     }
 
     @Override