# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1379288392 -7200
# Node ID 317036da1f295b4a778966c1c5a7f04861d4c908
# Parent  64a9ed9f1e8dd51342e62b2f12a84e560d6e25ba
Improve global value numbering algorithm.

diff -r 64a9ed9f1e8d -r 317036da1f29 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	Mon Sep 16 01:14:33 2013 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Mon Sep 16 01:39:52 2013 +0200
@@ -318,8 +318,9 @@
     }
 
     public Node findDuplicate(Node node) {
-        assert node.getNodeClass().valueNumberable();
-        if (node.getNodeClass().isLeafNode()) {
+        NodeClass nodeClass = node.getNodeClass();
+        assert nodeClass.valueNumberable();
+        if (nodeClass.isLeafNode()) {
             Node cachedNode = findNodeInCache(node);
             if (cachedNode != null) {
                 return cachedNode;
@@ -327,16 +328,28 @@
                 return null;
             }
         } else {
+
+            int minCount = Integer.MAX_VALUE;
+            Node minCountNode = null;
             for (Node input : node.inputs()) {
                 if (input != null) {
-                    for (Node usage : input.usages()) {
-                        if (usage != node && node.getNodeClass().valueEqual(node, usage) && node.getNodeClass().edgesEqual(node, usage)) {
-                            return usage;
-                        }
+                    int estimate = input.getUsageCountUpperBound();
+                    if (estimate == 0) {
+                        return null;
+                    } else if (estimate < minCount) {
+                        minCount = estimate;
+                        minCountNode = input;
                     }
-                    return null;
                 }
             }
+            if (minCountNode != null) {
+                for (Node usage : minCountNode.usages()) {
+                    if (usage != node && nodeClass == usage.getNodeClass() && nodeClass.valueEqual(node, usage) && node.getNodeClass().edgesEqual(node, usage)) {
+                        return usage;
+                    }
+                }
+                return null;
+            }
             return null;
         }
     }
diff -r 64a9ed9f1e8d -r 317036da1f29 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	Mon Sep 16 01:14:33 2013 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Mon Sep 16 01:39:52 2013 +0200
@@ -237,6 +237,16 @@
         }
     }
 
+    int getUsageCountUpperBound() {
+        if (usage0 == null) {
+            return 0;
+        }
+        if (usage1 == null) {
+            return 1;
+        }
+        return 2 + extraUsages.length;
+    }
+
     /**
      * Gets the list of nodes that use this node (e.g., as an input).
      */