--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Wed Apr 15 10:21:02 2015 -0700
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Wed Apr 15 11:07:53 2015 -0700
@@ -725,11 +725,68 @@
         return getNodes(type).iterator().hasNext();
     }
 
-    Node getStartNode(int iterableId) {
-        Node start = iterableNodesFirst.size() <= iterableId ? null : iterableNodesFirst.get(iterableId);
+    /**
+     * @param iterableId
+     * @return the first live Node with a matching iterableId
+     */
+    Node getIterableNodeStart(int iterableId) {
+        if (iterableNodesFirst.size() <= iterableId) {
+            return null;
+        }
+        Node start = iterableNodesFirst.get(iterableId);
+        if (start == null || !start.isDeleted()) {
+            return start;
+        }
+        return findFirstLiveIterable(iterableId, start);
+    }
+
+    private Node findFirstLiveIterable(int iterableId, Node node) {
+        assert iterableNodesFirst.get(iterableId) == node;
+        Node start = node;
+        while (start != null && start.isDeleted()) {
+            start = start.typeCacheNext;
+        }
+        iterableNodesFirst.set(iterableId, start);
+        if (start == null) {
+            iterableNodesLast.set(iterableId, start);
+        }
         return start;
     }
 
+    /**
+     * @param node
+     * @return return the first live Node with a matching iterableId starting from {@code node}
+     */
+    Node getIterableNodeNext(Node node) {
+        if (node == null) {
+            return null;
+        }
+        Node n = node;
+        if (n == null || !n.isDeleted()) {
+            return n;
+        }
+
+        return findNextLiveiterable(node);
+    }
+
+    private Node findNextLiveiterable(Node start) {
+        Node n = start;
+        while (n != null && n.isDeleted()) {
+            n = n.typeCacheNext;
+        }
+        if (n == null) {
+            // Only dead nodes after this one
+            start.typeCacheNext = null;
+            int nodeClassId = start.getNodeClass().iterableId();
+            assert nodeClassId != Node.NOT_ITERABLE;
+            iterableNodesLast.set(nodeClassId, start);
+        } else {
+            // Everything in between is dead
+            start.typeCacheNext = n;
+        }
+        return n;
+    }
+
     public NodeBitMap createNodeBitMap() {
         return new NodeBitMap(this);
     }

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/TypedGraphNodeIterator.java	Wed Apr 15 10:21:02 2015 -0700
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/TypedGraphNodeIterator.java	Wed Apr 15 11:07:53 2015 -0700
@@ -47,7 +47,7 @@
             forward();
         } else {
             Node c = current();
-            Node afterDeleted = skipDeleted(c);
+            Node afterDeleted = graph.getIterableNodeNext(c);
             if (afterDeleted == null) {
                 needsForward = true;
             } else if (c != afterDeleted) {
@@ -60,25 +60,16 @@
         return current();
     }
 
-    private static Node skipDeleted(Node node) {
-        Node n = node;
-        while (n != null && n.isDeleted()) {
-            n = n.typeCacheNext;
-        }
-        return n;
-    }
-
     private void forward() {
         needsForward = false;
         int startIdx = currentIdIndex;
         while (true) {
             Node next;
             if (current() == Graph.PLACE_HOLDER) {
-                next = graph.getStartNode(ids[currentIdIndex]);
+                next = graph.getIterableNodeStart(ids[currentIdIndex]);
             } else {
-                next = current().typeCacheNext;
+                next = graph.getIterableNodeNext(current().typeCacheNext);
             }
-            next = skipDeleted(next);
             if (next == null) {
                 currentIdIndex++;
                 if (currentIdIndex >= ids.length) {