Mercurial > hg > truffle
changeset 11654:317036da1f29
Improve global value numbering algorithm.
author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
---|---|
date | Mon, 16 Sep 2013 01:39:52 +0200 |
parents | 64a9ed9f1e8d |
children | 58b2ae907046 |
files | graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java |
diffstat | 2 files changed, 30 insertions(+), 7 deletions(-) [+] |
line wrap: on
line diff
--- 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; } }
--- 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). */