# HG changeset patch
# User Tom Rodriguez <tom.rodriguez@oracle.com>
# Date 1424737403 28800
# Node ID f7c6b33489c957eee9860ac1d8dbb07e19e10108
# Parent  8a764553675d0a75632d53cda0c6c3f4fb4bcb76# Parent  4eb793cfec273990949eedf9d53c8995596e6f4c
Merge

diff -r 8a764553675d -r f7c6b33489c9 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/GraphChangeMonitoringPhase.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/GraphChangeMonitoringPhase.java	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/GraphChangeMonitoringPhase.java	Mon Feb 23 16:23:23 2015 -0800
@@ -22,12 +22,14 @@
  */
 package com.oracle.graal.compiler.phases;
 
+import java.util.*;
 import java.util.stream.*;
 
 import com.oracle.graal.debug.*;
 import com.oracle.graal.debug.Debug.Scope;
 import com.oracle.graal.graph.Graph.NodeEvent;
 import com.oracle.graal.graph.Graph.NodeEventScope;
+import com.oracle.graal.graph.Node;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.phases.*;
 import com.oracle.graal.phases.common.util.*;
@@ -72,7 +74,11 @@
                 Debug.handle(t);
             }
         }
-        if (!listener.getNodes().isEmpty()) {
+        /*
+         * Ignore LogicConstantNode since those are sometimes created and deleted as part of running
+         * a phase.
+         */
+        if (listener.getNodes().stream().filter(e -> !(e instanceof LogicConstantNode)).findFirst().get() != null) {
             /* rerun it on the real graph in a new Debug scope so Dump and Log can find it. */
             listener = new HashSetNodeEventListener();
             try (NodeEventScope s = graph.trackNodeEvents(listener)) {
@@ -81,10 +87,11 @@
                         Debug.dump(BasePhase.PHASE_DUMP_LEVEL, graph, "*** Before phase %s", getName());
                     }
                     super.run(graph, context);
+                    Set<Node> collect = listener.getNodes().stream().filter(e -> !e.isAlive()).filter(e -> !(e instanceof LogicConstantNode)).collect(Collectors.toSet());
                     if (Debug.isDumpEnabled(BasePhase.PHASE_DUMP_LEVEL)) {
-                        Debug.dump(BasePhase.PHASE_DUMP_LEVEL, graph, "*** After phase %s", getName());
+                        Debug.dump(BasePhase.PHASE_DUMP_LEVEL, graph, "*** After phase %s %s", getName(), collect);
                     }
-                    Debug.log("*** %s %s %s\n", message, graph, listener.getNodes().stream().filter(e -> !e.isAlive()).collect(Collectors.toSet()));
+                    Debug.log("*** %s %s %s\n", message, graph, collect);
                 }
             }
         } else {
diff -r 8a764553675d -r f7c6b33489c9 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Mon Feb 23 16:23:23 2015 -0800
@@ -452,18 +452,17 @@
         return uniqueHelper(node, true);
     }
 
-    @SuppressWarnings("unchecked")
     <T extends Node> T uniqueHelper(T node, boolean addIfMissing) {
         assert node.getNodeClass().valueNumberable();
-        Node other = this.findDuplicate(node);
+        T other = this.findDuplicate(node);
         if (other != null) {
-            return (T) other;
+            return other;
         } else {
-            Node result = addIfMissing ? addHelper(node) : node;
+            T result = addIfMissing ? addHelper(node) : node;
             if (node.getNodeClass().isLeafNode()) {
                 putNodeIntoCache(result);
             }
-            return (T) result;
+            return result;
         }
     }
 
@@ -484,32 +483,36 @@
         return result;
     }
 
-    public Node findDuplicate(Node node) {
+    @SuppressWarnings("unchecked")
+    public <T extends Node> T findDuplicate(T node) {
         NodeClass<?> nodeClass = node.getNodeClass();
         assert nodeClass.valueNumberable();
         if (nodeClass.isLeafNode()) {
             // Leaf node: look up in cache
             Node cachedNode = findNodeInCache(node);
             if (cachedNode != null) {
-                return cachedNode;
+                return (T) cachedNode;
             } else {
                 return null;
             }
         } else {
-            // Non-leaf node: look for another usage of the node's inputs that
-            // has the same data, inputs and successors as the node. To reduce
-            // the cost of this computation, only the input with estimated highest
-            // usage count is considered.
-
+            /*
+             * Non-leaf node: look for another usage of the node's inputs that has the same data,
+             * inputs and successors as the node. To reduce the cost of this computation, only the
+             * input with lowest usage count is considered. If this node is the only user of any
+             * input then the search can terminate early. The usage count is only incremented once
+             * the Node is in the Graph, so account for that in the test.
+             */
+            final int earlyExitUsageCount = node.graph() != null ? 1 : 0;
             int minCount = Integer.MAX_VALUE;
             Node minCountNode = null;
             for (Node input : node.inputs()) {
                 if (input != null) {
-                    int estimate = input.getUsageCount();
-                    if (estimate == 0) {
+                    int usageCount = input.getUsageCount();
+                    if (usageCount == earlyExitUsageCount) {
                         return null;
-                    } else if (estimate < minCount) {
-                        minCount = estimate;
+                    } else if (usageCount < minCount) {
+                        minCount = usageCount;
                         minCountNode = input;
                     }
                 }
@@ -518,7 +521,7 @@
                 for (Node usage : minCountNode.usages()) {
                     if (usage != node && nodeClass == usage.getNodeClass() && node.valueEquals(usage) && nodeClass.getInputEdges().areEqualIn(node, usage) &&
                                     nodeClass.getEdges(Successors).areEqualIn(node, usage)) {
-                        return usage;
+                        return (T) usage;
                     }
                 }
                 return null;
diff -r 8a764553675d -r f7c6b33489c9 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Mon Feb 23 16:23:23 2015 -0800
@@ -426,6 +426,7 @@
 
     private void clearUsages() {
         incUsageModCount();
+        maybeNotifyZeroUsages(this);
         usage0 = null;
         usage1 = null;
         extraUsages = NO_NODES;
diff -r 8a764553675d -r f7c6b33489c9 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeWorkList.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeWorkList.java	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeWorkList.java	Mon Feb 23 16:23:23 2015 -0800
@@ -157,7 +157,7 @@
         }
 
         private boolean checkInfiniteWork(Node node) {
-            if (lastPull == node) {
+            if (lastPull == node && !node.hasNoUsages()) {
                 if (firstNoChange == null) {
                     firstNoChange = node;
                     lastChain = node;
diff -r 8a764553675d -r f7c6b33489c9 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	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BinaryOpLogicNode.java	Mon Feb 23 16:23:23 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 8a764553675d -r f7c6b33489c9 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	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AddNode.java	Mon Feb 23 16:23:23 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 8a764553675d -r f7c6b33489c9 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	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java	Mon Feb 23 16:23:23 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 8a764553675d -r f7c6b33489c9 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	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryNode.java	Mon Feb 23 16:23:23 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 8a764553675d -r f7c6b33489c9 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	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java	Mon Feb 23 16:23:23 2015 -0800
@@ -125,6 +125,9 @@
                 return duplicateModified(convertX.getValue(), convertY.getValue());
             }
         }
+        if (condition.isCommutative()) {
+            return this.maybeCommuteInputs();
+        }
         return this;
     }
 
diff -r 8a764553675d -r f7c6b33489c9 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	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatEqualsNode.java	Mon Feb 23 16:23:23 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 8a764553675d -r f7c6b33489c9 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	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerEqualsNode.java	Mon Feb 23 16:23:23 2015 -0800
@@ -65,7 +65,7 @@
                 }
             }
 
-            return new IntegerEqualsNode(x, y);
+            return new IntegerEqualsNode(x, y).maybeCommuteInputs();
         }
     }
 
diff -r 8a764553675d -r f7c6b33489c9 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	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerTestNode.java	Mon Feb 23 16:23:23 2015 -0800
@@ -55,6 +55,6 @@
                 return LogicConstantNode.contradiction();
             }
         }
-        return this;
+        return this.maybeCommuteInputs();
     }
 }
diff -r 8a764553675d -r f7c6b33489c9 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	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/MulNode.java	Mon Feb 23 16:23:23 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 8a764553675d -r f7c6b33489c9 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	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java	Mon Feb 23 16:23:23 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 8a764553675d -r f7c6b33489c9 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	Tue Feb 24 00:00:24 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/XorNode.java	Mon Feb 23 16:23:23 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