--- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/Node.java	Sun Oct 20 01:00:02 2013 +0200
+++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/Node.java	Sun Oct 20 03:26:03 2013 +0200
@@ -170,7 +170,6 @@
      * @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) {
         if (this.getParent() == null) {
             throw new IllegalStateException("This node cannot be replaced, because it does not yet have a parent.");
@@ -180,13 +179,35 @@
             newNode.assignSourceSection(sourceSection);
         }
         onReplace(newNode, reason);
-        return (T) this.getParent().replaceChild(this, newNode);
+        ((Node) newNode).parent = this.parent;
+        if (!NodeUtil.replaceChild(this.parent, this, newNode)) {
+            fixupTree();
+        }
+        return newNode;
     }
 
-    private <T extends Node> T replaceChild(T oldChild, T newChild) {
-        NodeUtil.replaceChild(this, oldChild, newChild);
-        adoptChild(newChild);
-        return newChild;
+    /**
+     * Rewrite has failed; the tree is likely inconsistent, so fix any stale parent references.
+     * 
+     * This is a rather expensive operation but rare to occur.
+     */
+    private void fixupTree() {
+        Node rootNode = NodeUtil.findParent(this, RootNode.class);
+        if (rootNode == null) {
+            throw new UnsupportedOperationException("Tree does not have a root node.");
+        }
+        rootNode.fixupChildren();
+    }
+
+    private void fixupChildren() {
+        for (Node child : getChildren()) {
+            if (child != null) {
+                if (child.parent != this) {
+                    child.parent = this;
+                }
+                child.fixupChildren();
+            }
+        }
     }
 
     /**