# HG changeset patch
# User Tom Rodriguez <tom.rodriguez@oracle.com>
# Date 1424284591 28800
# Node ID b017118b412beee83fddd6f6174e708b966b4be6
# Parent  ea8e0540da95ff7b0b5a04b177c8ac39f17cef08
Ensure a canonical ordering of inputs for commutative binary operations

diff -r ea8e0540da95 -r b017118b412b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BinaryOpLogicNode.java
--- 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;
+    }
 }
diff -r ea8e0540da95 -r b017118b412b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AddNode.java
--- 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
diff -r ea8e0540da95 -r b017118b412b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java
--- 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
diff -r ea8e0540da95 -r b017118b412b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryNode.java
--- 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;
+    }
 }
diff -r ea8e0540da95 -r b017118b412b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java
--- 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;
     }
 
diff -r ea8e0540da95 -r b017118b412b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatEqualsNode.java
--- 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();
         }
     }
 
diff -r ea8e0540da95 -r b017118b412b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerEqualsNode.java
--- 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();
         }
     }
 
diff -r ea8e0540da95 -r b017118b412b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerTestNode.java
--- 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();
     }
 }
diff -r ea8e0540da95 -r b017118b412b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/MulNode.java
--- 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();
         }
     }
 
diff -r ea8e0540da95 -r b017118b412b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java
--- 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
diff -r ea8e0540da95 -r b017118b412b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/XorNode.java
--- 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