--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Wed Feb 18 10:10:00 2015 -0800
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Wed Feb 18 10:19:17 2015 -0800
@@ -496,20 +496,23 @@
                 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;
                     }
                 }