--- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/Node.java	Wed Oct 09 20:03:43 2013 +0200
+++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/Node.java	Wed Oct 09 22:21:49 2013 +0200
@@ -39,6 +39,8 @@
 
     private SourceSection sourceSection;
 
+    private Node replacedWith;
+
     /**
      * Marks array fields that are children of this node.
      */
@@ -170,8 +172,8 @@
      * @param reason a description of the reason for the replacement
      * @return the new node
      */
-    @SuppressWarnings({"unchecked"})
     public final <T extends Node> T replace(T newNode, String reason) {
+        CompilerDirectives.transferToInterpreter();
         if (this.getParent() == null) {
             throw new IllegalStateException("This node cannot be replaced, because it does not yet have a parent.");
         }
@@ -180,13 +182,31 @@
             newNode.assignSourceSection(sourceSection);
         }
         onReplace(newNode, reason);
-        return (T) this.getParent().replaceChild(this, newNode);
+        if (NodeUtil.replaceChild(parent, this, newNode)) {
+            parent.adoptChild(newNode);
+            this.replacedWith = newNode;
+        } else if (replacedWith != null) {
+            replaceFailedHelper(newNode);
+        } else {
+            throw new IllegalStateException("Child not found in parent.");
+        }
+        return newNode;
     }
 
-    private <T extends Node> T replaceChild(T oldChild, T newChild) {
-        NodeUtil.replaceChild(this, oldChild, newChild);
-        adoptChild(newChild);
-        return newChild;
+    private void replaceFailedHelper(Node newNode) {
+        Node lastReplacedWith = replacedWith;
+        assert lastReplacedWith != this;
+        while (lastReplacedWith.replacedWith != null) {
+            lastReplacedWith = lastReplacedWith.replacedWith;
+            assert lastReplacedWith != this;
+        }
+        newNode.parent = parent;
+        newNode.replacedWith = lastReplacedWith;
+        for (Node child : newNode.getChildren()) {
+            if (child != null) {
+                child.parent = lastReplacedWith;
+            }
+        }
     }
 
     /**

--- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeUtil.java	Wed Oct 09 20:03:43 2013 +0200
+++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeUtil.java	Wed Oct 09 22:21:49 2013 +0200
@@ -347,14 +347,14 @@
         return nodes;
     }
 
-    public static void replaceChild(Node parent, Node oldChild, Node newChild) {
+    public static boolean replaceChild(Node parent, Node oldChild, Node newChild) {
         NodeClass nodeClass = NodeClass.get(parent.getClass());
 
         for (long fieldOffset : nodeClass.getChildOffsets()) {
             if (unsafe.getObject(parent, fieldOffset) == oldChild) {
                 assert assertAssignable(nodeClass, fieldOffset, newChild);
                 unsafe.putObject(parent, fieldOffset, newChild);
-                return;
+                return true;
             }
         }
 
@@ -367,11 +367,12 @@
                     if (array[i] == oldChild) {
                         assert assertAssignable(nodeClass, fieldOffset, newChild);
                         array[i] = newChild;
-                        return;
+                        return true;
                     }
                 }
             }
         }
+        return false;
     }
 
     private static boolean assertAssignable(NodeClass clazz, long fieldOffset, Object newValue) {
@@ -798,4 +799,21 @@
         }
         return "";
     }
+
+    public static boolean verify(Node root) {
+        Iterable<Node> children = root.getChildren();
+        for (Node child : children) {
+            if (child != null) {
+                if (child.getParent() != root) {
+                    throw new AssertionError(toStringWithClass(child) + ": actual parent=" + toStringWithClass(child.getParent()) + " expected parent=" + toStringWithClass(root));
+                }
+                verify(child);
+            }
+        }
+        return true;
+    }
+
+    private static String toStringWithClass(Object obj) {
+        return obj == null ? "null" : obj + "(" + obj.getClass().getName() + ")";
+    }
 }