--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Mon Sep 16 23:17:56 2013 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Tue Sep 17 00:30:01 2013 +0200
@@ -188,7 +188,7 @@
      */
     public Graph copy(String newName) {
         Graph copy = new Graph(newName);
-        copy.addDuplicates(getNodes(), (Map<Node, Node>) null);
+        copy.addDuplicates(getNodes(), this, this.getNodeCount(), (Map<Node, Node>) null);
         return copy;
     }
 
@@ -712,14 +712,14 @@
      * @param replacementsMap the replacement map (can be null if no replacement is to be performed)
      * @return a map which associates the original nodes from {@code nodes} to their duplicates
      */
-    public Map<Node, Node> addDuplicates(Iterable<Node> newNodes, Map<Node, Node> replacementsMap) {
+    public Map<Node, Node> addDuplicates(Iterable<Node> newNodes, final Graph oldGraph, int estimatedNodeCount, Map<Node, Node> replacementsMap) {
         DuplicationReplacement replacements;
         if (replacementsMap == null) {
             replacements = null;
         } else {
             replacements = new MapReplacement(replacementsMap);
         }
-        return addDuplicates(newNodes, replacements);
+        return addDuplicates(newNodes, oldGraph, estimatedNodeCount, replacements);
     }
 
     public interface DuplicationReplacement {
@@ -744,7 +744,7 @@
     }
 
     @SuppressWarnings("all")
-    public Map<Node, Node> addDuplicates(Iterable<Node> newNodes, DuplicationReplacement replacements) {
-        return NodeClass.addGraphDuplicate(this, newNodes, replacements);
+    public Map<Node, Node> addDuplicates(Iterable<Node> newNodes, final Graph oldGraph, int estimatedNodeCount, DuplicationReplacement replacements) {
+        return NodeClass.addGraphDuplicate(this, oldGraph, estimatedNodeCount, newNodes, replacements);
     }
 }

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java	Mon Sep 16 23:17:56 2013 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java	Tue Sep 17 00:30:01 2013 +0200
@@ -26,7 +26,6 @@
 
 import java.lang.reflect.*;
 import java.util.*;
-import java.util.Map.Entry;
 import java.util.concurrent.*;
 
 import com.oracle.graal.debug.*;
@@ -1048,8 +1047,8 @@
         return nameTemplate;
     }
 
-    static Map<Node, Node> addGraphDuplicate(final Graph graph, Iterable<Node> nodes, final DuplicationReplacement replacements) {
-        final IdentityHashMap<Node, Node> newNodes = new IdentityHashMap<>();
+    static Map<Node, Node> addGraphDuplicate(final Graph graph, final Graph oldGraph, int estimatedNodeCount, Iterable<Node> nodes, final DuplicationReplacement replacements) {
+        final Map<Node, Node> newNodes = (estimatedNodeCount > (oldGraph.getNodeCount() + oldGraph.getDeletedNodeCount() >> 4)) ? new NodeNodeMap(oldGraph) : new IdentityHashMap<Node, Node>();
         createNodeDuplicates(graph, nodes, replacements, newNodes);
 
         DuplicationReplacement replacementClosure = new DuplicationReplacement() {
@@ -1074,9 +1073,8 @@
         };
 
         // re-wire inputs
-        for (Entry<Node, Node> entry : newNodes.entrySet()) {
-            Node oldNode = entry.getKey();
-            Node node = entry.getValue();
+        for (Node oldNode : nodes) {
+            Node node = newNodes.get(oldNode);
             NodeClass oldNodeClass = oldNode.getNodeClass();
             NodeClass nodeClass = node.getNodeClass();
             if (oldNodeClass == nodeClass && (replacements == null || replacements.replacement(oldNode) == oldNode)) {
@@ -1089,7 +1087,7 @@
         return newNodes;
     }
 
-    private static void createNodeDuplicates(final Graph graph, Iterable<Node> nodes, final DuplicationReplacement replacements, final IdentityHashMap<Node, Node> newNodes) {
+    private static void createNodeDuplicates(final Graph graph, Iterable<Node> nodes, final DuplicationReplacement replacements, final Map<Node, Node> newNodes) {
         for (Node node : nodes) {
             if (node != null) {
                 assert !node.isDeleted() : "trying to duplicate deleted node: " + node;
@@ -1110,8 +1108,8 @@
         }
     }
 
-    private static void transferValuesDifferentNodeClass(final Graph graph, final DuplicationReplacement replacements, final IdentityHashMap<Node, Node> newNodes, Node oldNode, Node node,
-                    NodeClass oldNodeClass, NodeClass nodeClass) {
+    private static void transferValuesDifferentNodeClass(final Graph graph, final DuplicationReplacement replacements, final Map<Node, Node> newNodes, Node oldNode, Node node, NodeClass oldNodeClass,
+                    NodeClass nodeClass) {
         for (NodeClassIterator iter = oldNode.inputs().iterator(); iter.hasNext();) {
             Position pos = iter.nextPosition();
             if (!nodeClass.isValid(pos, oldNodeClass)) {

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java	Mon Sep 16 23:17:56 2013 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java	Tue Sep 17 00:30:01 2013 +0200
@@ -26,11 +26,11 @@
 import java.util.*;
 import java.util.Map.Entry;
 
-public final class NodeMap<T> {
+public class NodeMap<T> {
 
     private final Graph graph;
     private final boolean autogrow;
-    private Object[] values;
+    protected Object[] values;
 
     public NodeMap(Graph graph) {
         this(graph, false);
@@ -54,6 +54,29 @@
         return (T) values[node.id()];
     }
 
+    public boolean isEmpty() {
+        return !entries().iterator().hasNext();
+    }
+
+    public boolean containsKey(Object key) {
+        if (key instanceof Node) {
+            Node node = (Node) key;
+            if (node.graph() == graph()) {
+                return get(node) != null;
+            }
+        }
+        return false;
+    }
+
+    public boolean containsValue(Object value) {
+        for (Object o : values) {
+            if (o == value) {
+                return true;
+            }
+        }
+        return false;
+    }
+
     public Graph graph() {
         return graph;
     }

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeNodeMap.java	Tue Sep 17 00:30:01 2013 +0200
@@ -0,0 +1,75 @@
+/*
+ * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.graph;
+
+import java.util.*;
+
+public final class NodeNodeMap extends NodeMap<Node> implements Map<Node, Node> {
+
+    public NodeNodeMap(Graph graph) {
+        super(graph, true);
+    }
+
+    public NodeNodeMap(NodeNodeMap copyFrom) {
+        super(copyFrom);
+    }
+
+    public Node get(Object key) {
+        return super.get((Node) key);
+    }
+
+    public Node put(Node key, Node value) {
+        Node oldValue = super.get(key);
+        super.set(key, value);
+        return oldValue;
+    }
+
+    public Node remove(Object key) {
+        throw new UnsupportedOperationException("Cannot remove keys from this map");
+    }
+
+    public void putAll(Map<? extends Node, ? extends Node> m) {
+        for (Entry<? extends Node, ? extends Node> entry : m.entrySet()) {
+            put(entry.getKey(), entry.getValue());
+        }
+    }
+
+    public Set<Node> keySet() {
+        throw new UnsupportedOperationException("Cannot get key set from this map");
+    }
+
+    public Collection<Node> values() {
+        ArrayList<Node> result = new ArrayList<>(this.size());
+        for (int i = 0; i < values.length; ++i) {
+            Object v = values[i];
+            if (v != null) {
+                result.add((Node) v);
+            }
+        }
+        return result;
+    }
+
+    public Set<java.util.Map.Entry<Node, Node>> entrySet() {
+        throw new UnsupportedOperationException("Cannot get entry set for this map");
+    }
+}

--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java	Mon Sep 16 23:17:56 2013 +0200
+++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java	Tue Sep 17 00:30:01 2013 +0200
@@ -131,7 +131,8 @@
             } else {
                 dr = null;
             }
-            duplicationMap = graph().addDuplicates(original().nodes(), dr);
+            NodeIterable<Node> nodesIterable = original().nodes();
+            duplicationMap = graph().addDuplicates(nodesIterable, graph(), nodesIterable.count(), dr);
             finishDuplication();
             nodesReady = true;
         } else {

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java	Mon Sep 16 23:17:56 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java	Tue Sep 17 00:30:01 2013 +0200
@@ -178,7 +178,7 @@
         StructuredGraph copy = new StructuredGraph(newName, newMethod, graphId, entryBCI);
         HashMap<Node, Node> replacements = new HashMap<>();
         replacements.put(start, copy.start);
-        copy.addDuplicates(getNodes(), replacements);
+        copy.addDuplicates(getNodes(), this, this.getNodeCount(), replacements);
         return copy;
     }
 

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java	Mon Sep 16 23:17:56 2013 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java	Tue Sep 17 00:30:01 2013 +0200
@@ -1334,7 +1334,7 @@
         assert invoke.asNode().successors().first() != null : invoke;
         assert invoke.asNode().predecessor() != null;
 
-        Map<Node, Node> duplicates = graph.addDuplicates(nodes, localReplacement);
+        Map<Node, Node> duplicates = graph.addDuplicates(nodes, inlineGraph, inlineGraph.getNodeCount(), localReplacement);
         FixedNode firstCFGNodeDuplicate = (FixedNode) duplicates.get(firstCFGNode);
         invoke.asNode().replaceAtPredecessor(firstCFGNodeDuplicate);
 
@@ -1377,7 +1377,8 @@
         if (stateAfter != null) {
             FrameState outerFrameState = null;
             int callerLockDepth = stateAfter.nestedLockDepth();
-            for (Node node : duplicates.values()) {
+            for (Node inlinedNode : inlineGraph.getNodes()) {
+                Node node = duplicates.get(inlinedNode);
                 if (node instanceof FrameState) {
                     FrameState frameState = (FrameState) node;
                     assert frameState.bci != FrameState.BEFORE_BCI : frameState;
@@ -1420,7 +1421,7 @@
         if (returnNode != null) {
             if (returnNode.result() instanceof LocalNode) {
                 returnValue = localReplacement.replacement(returnNode.result());
-            } else {
+            } else if (returnNode.result() != null) {
                 returnValue = duplicates.get(returnNode.result());
             }
             invoke.asNode().replaceAtUsages(returnValue);

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java	Mon Sep 16 23:17:56 2013 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java	Tue Sep 17 00:30:01 2013 +0200
@@ -260,11 +260,11 @@
             for (final AbstractEndNode forwardEnd : merge.forwardEnds()) {
                 Map<Node, Node> duplicates;
                 if (replacements == null || replacements.get(endIndex) == null) {
-                    duplicates = graph.addDuplicates(duplicatedNodes, (DuplicationReplacement) null);
+                    duplicates = graph.addDuplicates(duplicatedNodes, graph, duplicatedNodes.size(), (DuplicationReplacement) null);
                 } else {
                     HashMap<Node, Node> replace = new HashMap<>();
                     replace.put(replacements.get(endIndex).object(), replacements.get(endIndex));
-                    duplicates = graph.addDuplicates(duplicatedNodes, replace);
+                    duplicates = graph.addDuplicates(duplicatedNodes, graph, duplicatedNodes.size(), replace);
                 }
                 for (Map.Entry<ValueNode, PhiNode> phi : bottomPhis.entrySet()) {
                     phi.getValue().initializeValueAt(merge.forwardEndIndex(forwardEnd), (ValueNode) duplicates.get(phi.getKey()));

--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java	Mon Sep 16 23:17:56 2013 +0200
+++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java	Tue Sep 17 00:30:01 2013 +0200
@@ -420,7 +420,7 @@
                 placeholders[i] = placeholder;
             }
         }
-        snippetCopy.addDuplicates(snippetGraph.getNodes(), nodeReplacements);
+        snippetCopy.addDuplicates(snippetGraph.getNodes(), snippetGraph, snippetGraph.getNodeCount(), nodeReplacements);
 
         Debug.dump(snippetCopy, "Before specialization");
         if (!nodeReplacements.isEmpty()) {
@@ -750,7 +750,7 @@
             FixedNode firstCFGNode = entryPointNode.next();
             StructuredGraph replaceeGraph = replacee.graph();
             IdentityHashMap<Node, Node> replacements = bind(replaceeGraph, runtime, args);
-            Map<Node, Node> duplicates = replaceeGraph.addDuplicates(nodes, replacements);
+            Map<Node, Node> duplicates = replaceeGraph.addDuplicates(nodes, snippet, snippet.getNodeCount(), replacements);
             Debug.dump(replaceeGraph, "After inlining snippet %s", snippetCopy.method());
 
             // Re-wire the control flow graph around the replacee
@@ -791,7 +791,7 @@
             if (returnNode != null) {
                 if (returnNode.result() instanceof LocalNode) {
                     returnValue = (ValueNode) replacements.get(returnNode.result());
-                } else {
+                } else if (returnNode.result() != null) {
                     returnValue = (ValueNode) duplicates.get(returnNode.result());
                 }
                 Node returnDuplicate = duplicates.get(returnNode);
@@ -844,7 +844,7 @@
             FixedNode firstCFGNode = entryPointNode.next();
             StructuredGraph replaceeGraph = replacee.graph();
             IdentityHashMap<Node, Node> replacements = bind(replaceeGraph, runtime, args);
-            Map<Node, Node> duplicates = replaceeGraph.addDuplicates(nodes, replacements);
+            Map<Node, Node> duplicates = replaceeGraph.addDuplicates(nodes, snippet, snippet.getNodeCount(), replacements);
             Debug.dump(replaceeGraph, "After inlining snippet %s", snippetCopy.method());
 
             FixedWithNextNode lastFixedNode = tool.lastFixedNode();