--- a/graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TestNode.java	Thu Jan 10 16:04:25 2013 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,37 +0,0 @@
-/*
- * Copyright (c) 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;
-
-
-public class TestNode extends Node implements Node.IterableNodeType {
-    private String name;
-
-    public TestNode(String name) {
-        this.name = name;
-    }
-
-
-    public String getName() {
-        return name;
-    }
-}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TestNodeInterface.java	Thu Jan 10 17:05:42 2013 +0100
@@ -0,0 +1,28 @@
+/*
+ * Copyright (c) 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;
+
+
+public interface TestNodeInterface {
+    String getName();
+}

--- a/graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TypedNodeIteratorTest.java	Thu Jan 10 16:04:25 2013 +0100
+++ b/graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TypedNodeIteratorTest.java	Thu Jan 10 17:05:42 2013 +0100
@@ -31,6 +31,16 @@
 
 public class TypedNodeIteratorTest {
 
+    private static class TestNode extends Node implements Node.IterableNodeType, TestNodeInterface {
+        private final String name;
+        public TestNode(String name) {
+            this.name = name;
+        }
+        public String getName() {
+            return name;
+        }
+    }
+
     @Test
     public void singleNodeTest() {
         Graph graph = new Graph();
@@ -144,9 +154,9 @@
         assertEquals(3, z);
     }
 
-    private static String toString(Iterable<TestNode> nodes) {
+    public static String toString(Iterable<? extends TestNodeInterface> nodes) {
         StringBuilder sb = new StringBuilder();
-        for (TestNode tn : nodes) {
+        for (TestNodeInterface tn : nodes) {
             sb.append(tn.getName());
         }
         return sb.toString();

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.graph.test/src/com/oracle/graal/graph/TypedNodeIteratorTest2.java	Thu Jan 10 17:05:42 2013 +0100
@@ -0,0 +1,93 @@
+/*
+ * Copyright (c) 2013, 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 static org.junit.Assert.*;
+
+import org.junit.*;
+
+
+public class TypedNodeIteratorTest2 {
+
+    private static class NodeA extends Node implements TestNodeInterface {
+        private final String name;
+        public NodeA(String name) {
+            this.name = name;
+        }
+        public String getName() {
+            return name;
+        }
+    }
+
+    private static class NodeB extends NodeA implements Node.IterableNodeType {
+        public NodeB(String name) {
+            super(name);
+        }
+    }
+
+    private static class NodeC extends NodeB {
+        public NodeC(String name) {
+            super(name);
+        }
+    }
+
+    private static class NodeD extends NodeC {
+        public NodeD(String name) {
+            super(name);
+        }
+    }
+
+    @Test
+    public void simpleSubclassTest() {
+        Graph graph = new Graph();
+        graph.add(new NodeB("b"));
+        graph.add(new NodeD("d"));
+
+        Assert.assertEquals("bd", TypedNodeIteratorTest.toString(graph.getNodes(NodeB.class)));
+        Assert.assertEquals("d", TypedNodeIteratorTest.toString(graph.getNodes(NodeD.class)));
+    }
+
+    @Test
+    public void addingNodeDuringIterationTest() {
+        Graph graph = new Graph();
+        graph.add(new NodeB("b1"));
+        NodeD d1 = graph.add(new NodeD("d1"));
+        StringBuilder sb = new StringBuilder();
+        for (NodeB tn : graph.getNodes(NodeB.class)) {
+            if (tn == d1) {
+                graph.add(new NodeB("b2"));
+            }
+            sb.append(tn.getName());
+        }
+        assertEquals("b1d1b2", sb.toString());
+        for (NodeB tn : graph.getNodes(NodeB.class)) {
+            if (tn == d1) {
+                graph.add(new NodeB("b3"));
+            }
+            assertNotNull(tn);
+        }
+        assertEquals(4, graph.getNodes(NodeB.class).count());
+        assertEquals(1, graph.getNodes(NodeD.class).count());
+    }
+
+}

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Thu Jan 10 16:04:25 2013 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Thu Jan 10 17:05:42 2013 +0100
@@ -310,51 +310,99 @@
         };
     }
 
-    private static class TypedNodeIterator<T extends IterableNodeType> implements Iterator<T> {
-        private Node current;
-        private final Node start;
+    private static class PlaceHolderNode extends Node {}
+    private static final PlaceHolderNode PLACE_HOLDER = new PlaceHolderNode();
+
+    private class TypedNodeIterator<T extends IterableNodeType> implements Iterator<T> {
+        private final int[] ids;
+        private final Node[] current;
+
+        private int currentIdIndex;
+        private boolean needsForward;
+
+        public TypedNodeIterator(NodeClass clazz) {
+            ids = clazz.iterableIds();
+            currentIdIndex = 0;
+            current = new Node[ids.length];
+            Arrays.fill(current, PLACE_HOLDER);
+            needsForward = true;
+        }
+
+        private Node findNext() {
+            if (needsForward) {
+                forward();
+            } else {
+                Node c = current();
+                Node afterDeleted = skipDeleted(c);
+                if (afterDeleted == null) {
+                    needsForward = true;
+                } else if (c != afterDeleted) {
+                    setCurrent(afterDeleted);
+                }
+            }
+            if (needsForward) {
+                return null;
+            }
+            return current();
+        }
 
-        public TypedNodeIterator(Node start) {
-            if (start != null && start.isDeleted()) {
-                this.current = start;
-            } else {
-                this.current = null;
+        private Node skipDeleted(Node node) {
+            Node n = node;
+            while (n != null && n.isDeleted()) {
+                n = n.typeCacheNext;
             }
-            this.start = start;
+            return n;
+        }
+
+        private void forward() {
+            needsForward = false;
+            int startIdx = currentIdIndex;
+            while (true) {
+                Node next;
+                if (current() == PLACE_HOLDER) {
+                    next = getStartNode(ids[currentIdIndex]);
+                } else {
+                    next = current().typeCacheNext;
+                }
+                next = skipDeleted(next);
+                if (next == null) {
+                    currentIdIndex++;
+                    if (currentIdIndex >= ids.length) {
+                        currentIdIndex = 0;
+                    }
+                    if (currentIdIndex == startIdx) {
+                        needsForward = true;
+                        return;
+                    }
+                } else {
+                    setCurrent(next);
+                    break;
+                }
+            }
+        }
+
+        private Node current() {
+            return current[currentIdIndex];
+        }
+
+        private void setCurrent(Node n) {
+            current[currentIdIndex] = n;
         }
 
         @Override
         public boolean hasNext() {
-            if (current != null) {
-                Node next = current.typeCacheNext;
-                if (next != null) {
-                    while (next.isDeleted()) {
-                        next = next.typeCacheNext;
-                        if (next == null) {
-                            return false;
-                        }
-                        current.typeCacheNext = next;
-                    }
-                    return true;
-                }
-                return false;
-            } else {
-                return start != null;
-            }
+            return findNext() != null;
         }
 
         @Override
         @SuppressWarnings("unchecked")
         public T next() {
-            if (current == null) {
-                Node result = start;
-                current = result;
-                return (T) result;
-            } else {
-                Node result = current.typeCacheNext;
-                current = result;
-                return (T) result;
+            Node result = findNext();
+            if (result == null) {
+                throw new NoSuchElementException();
             }
+            needsForward = true;
+            return (T) result;
         }
 
         @Override
@@ -369,11 +417,11 @@
      * @return an {@link Iterable} providing all the matching nodes.
      */
     public <T extends Node & IterableNodeType> NodeIterable<T> getNodes(final Class<T> type) {
-        final Node start = getStartNode(type);
+        final NodeClass nodeClass = NodeClass.get(type);
         return new AbstractNodeIterable<T>() {
             @Override
             public Iterator<T> iterator() {
-                return new TypedNodeIterator<>(start);
+                return new TypedNodeIterator<>(nodeClass);
             }
         };
     }
@@ -387,10 +435,8 @@
         return getNodes(type).iterator().hasNext();
     }
 
-    private <T> Node getStartNode(final Class<T> type) {
-        int nodeClassId = NodeClass.get(type).iterableId();
-        assert nodeClassId != -1 : type + " is not iterable within graphs (missing \"implements IterableNodeType\"?)";
-        Node start = nodeCacheFirst.size() <= nodeClassId ? null : nodeCacheFirst.get(nodeClassId);
+    private Node getStartNode(int iterableId) {
+        Node start = nodeCacheFirst.size() <= iterableId ? null : nodeCacheFirst.get(iterableId);
         return start;
     }
 

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java	Thu Jan 10 16:04:25 2013 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java	Thu Jan 10 17:05:42 2013 +0100
@@ -47,8 +47,7 @@
         }
     }
 
-
-    public static final int NOT_ITERABLE = -1;
+    static final int NOT_ITERABLE = -1;
 
     private static final Class<?> NODE_CLASS = Node.class;
     private static final Class<?> INPUT_LIST_CLASS = NodeInputList.class;
@@ -66,6 +65,7 @@
     private final String shortName;
     private final String nameTemplate;
     private final int iterableId;
+    private int[] iterableIds;
 
 
     public NodeClass(Class<?> clazz) {
@@ -110,14 +110,27 @@
         this.shortName = newShortName;
         if (Node.IterableNodeType.class.isAssignableFrom(clazz)) {
             this.iterableId = nextIterableId++;
-            // TODO (lstadler) add type hierarchy - based node iteration
-//            for (NodeClass nodeClass : nodeClasses.values()) {
-//                if (clazz.isAssignableFrom(nodeClass.clazz)) {
-//                    throw new UnsupportedOperationException("iterable non-final Node classes not supported: " + clazz);
-//                }
-//            }
+            List<NodeClass> existingClasses = new LinkedList<>();
+            for (FieldIntrospection nodeClass : allClasses.values()) {
+                if (clazz.isAssignableFrom(nodeClass.clazz)) {
+                    existingClasses.add((NodeClass) nodeClass);
+                }
+                if (nodeClass.clazz.isAssignableFrom(clazz) && Node.IterableNodeType.class.isAssignableFrom(nodeClass.clazz)) {
+                    NodeClass superNodeClass = (NodeClass) nodeClass;
+                    superNodeClass.iterableIds = Arrays.copyOf(superNodeClass.iterableIds, superNodeClass.iterableIds.length + 1);
+                    superNodeClass.iterableIds[superNodeClass.iterableIds.length - 1] = this.iterableId;
+                }
+            }
+            int[] ids = new int[existingClasses.size() + 1];
+            ids[0] = iterableId;
+            int i = 1;
+            for (NodeClass other : existingClasses) {
+                ids[i++] = other.iterableId;
+            }
+            this.iterableIds = ids;
         } else {
             this.iterableId = NOT_ITERABLE;
+            this.iterableIds = null;
         }
     }
 
@@ -145,6 +158,10 @@
         return shortName;
     }
 
+    public int[] iterableIds() {
+        return iterableIds;
+    }
+
     public int iterableId() {
         return iterableId;
     }