--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Tue Apr 30 19:54:37 2013 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Tue Apr 30 19:56:36 2013 +0200
@@ -477,7 +477,11 @@
     }
 
     public <T> NodeMap<T> createNodeMap() {
-        return new NodeMap<>(this);
+        return createNodeMap(false);
+    }
+
+    public <T> NodeMap<T> createNodeMap(boolean autoGrow) {
+        return new NodeMap<>(this, autoGrow);
     }
 
     public NodeFlood createNodeFlood() {

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java	Tue Apr 30 19:54:37 2013 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java	Tue Apr 30 19:56:36 2013 +0200
@@ -29,19 +29,23 @@
 public final class NodeMap<T> {
 
     private final Graph graph;
+    private final boolean autogrow;
     private Object[] values;
-    private int size;
 
     public NodeMap(Graph graph) {
+        this(graph, false);
+    }
+
+    public NodeMap(Graph graph, boolean autogrow) {
         this.graph = graph;
-        values = new Object[graph.nodeIdCount()];
-        size = values.length;
+        this.values = new Object[graph.nodeIdCount()];
+        this.autogrow = autogrow;
     }
 
     public NodeMap(NodeMap<T> copyFrom) {
         this.graph = copyFrom.graph;
         this.values = Arrays.copyOf(copyFrom.values, copyFrom.values.length);
-        this.size = copyFrom.size;
+        this.autogrow = copyFrom.autogrow;
     }
 
     @SuppressWarnings("unchecked")
@@ -60,14 +64,21 @@
     }
 
     public int size() {
-        return size;
+        return values.length;
     }
 
     public boolean isNew(Node node) {
-        return node.id() >= size;
+        return node.id() >= size();
+    }
+
+    public void grow() {
+        this.values = Arrays.copyOf(values, graph.nodeIdCount());
     }
 
     private void check(Node node) {
+        if (autogrow && isNew(node)) {
+            grow();
+        }
         assert node.graph() == graph : "this node is not part of the graph";
         assert !isNew(node) : "this node was added to the graph after creating the node map : " + node;
     }

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java	Tue Apr 30 19:54:37 2013 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java	Tue Apr 30 19:56:36 2013 +0200
@@ -58,7 +58,7 @@
 
     protected ControlFlowGraph(StructuredGraph graph) {
         this.graph = graph;
-        this.nodeToBlock = graph.createNodeMap();
+        this.nodeToBlock = graph.createNodeMap(true);
     }
 
     public Block[] getBlocks() {