--- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/Node.java	Thu Mar 20 00:16:39 2014 +0100
+++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/Node.java	Wed Mar 19 23:11:46 2014 +0100
@@ -133,11 +133,36 @@
      * @param newChildren the array of new children whose parent should be updated
      * @return the array of new children
      */
-    protected final <T extends Node> T[] adoptChildren(T[] newChildren) {
-        if (newChildren != null) {
-            for (T n : newChildren) {
-                adoptChild(n);
-            }
+    @SuppressWarnings("static-method")
+    @Deprecated
+    protected final <T extends Node> T[] adoptChildren(final T[] newChildren) {
+        return newChildren;
+    }
+
+    /**
+     * Method that updates the link to the parent in the specified new child node to this node.
+     * 
+     * @param newChild the new child whose parent should be updated
+     * @return the new child
+     */
+    @SuppressWarnings("static-method")
+    @Deprecated
+    protected final <T extends Node> T adoptChild(final T newChild) {
+        return newChild;
+    }
+
+    /**
+     * Method that updates the link to the parent in the array of specified new child nodes to this
+     * node.
+     * 
+     * @param newChildren the array of new children whose parent should be updated
+     * @return the array of new children
+     */
+    protected final <T extends Node> T[] insert(final T[] newChildren) {
+        CompilerDirectives.transferToInterpreterAndInvalidate();
+        assert newChildren != null;
+        for (Node newChild : newChildren) {
+            adoptHelper(newChild);
         }
         return newChildren;
     }
@@ -148,14 +173,52 @@
      * @param newChild the new child whose parent should be updated
      * @return the new child
      */
-    protected final <T extends Node> T adoptChild(T newChild) {
-        if (newChild != null) {
-            if (newChild == this) {
-                throw new IllegalStateException("The parent of a node can never be the node itself.");
+    protected final <T extends Node> T insert(final T newChild) {
+        CompilerDirectives.transferToInterpreterAndInvalidate();
+        assert newChild != null;
+        adoptHelper(newChild);
+        return newChild;
+    }
+
+    public final void adoptChildren() {
+        CompilerDirectives.transferToInterpreterAndInvalidate();
+        adoptHelper();
+    }
+
+    private void adoptHelper(final Node newChild) {
+        assert newChild != null;
+        if (newChild == this) {
+            throw new IllegalStateException("The parent of a node can never be the node itself.");
+        }
+        newChild.parent = this;
+        newChild.adoptHelper();
+    }
+
+    private void adoptHelper() {
+        Iterable<Node> children = this.getChildren();
+        for (Node child : children) {
+            if (child != null && child.getParent() != this) {
+                this.adoptHelper(child);
             }
-            ((Node) newChild).parent = this;
+        }
+    }
+
+    private void adoptUnadoptedHelper(final Node newChild) {
+        assert newChild != null;
+        if (newChild == this) {
+            throw new IllegalStateException("The parent of a node can never be the node itself.");
         }
-        return newChild;
+        newChild.parent = this;
+        newChild.adoptUnadoptedHelper();
+    }
+
+    private void adoptUnadoptedHelper() {
+        Iterable<Node> children = this.getChildren();
+        for (Node child : children) {
+            if (child != null && child.getParent() == null) {
+                this.adoptUnadoptedHelper(child);
+            }
+        }
     }
 
     /**
@@ -186,54 +249,13 @@
      * @param reason a description of the reason for the replacement
      * @return the new node
      */
-    public final <T extends Node> T replace(T newNode, CharSequence reason) {
+    public final <T extends Node> T replace(final T newNode, final CharSequence reason) {
         CompilerDirectives.transferToInterpreterAndInvalidate();
-        if (this.getParent() == null) {
-            throw new IllegalStateException("This node cannot be replaced, because it does not yet have a parent.");
-        }
-        if (sourceSection != null && newNode.getSourceSection() == null) {
-            // Pass on the source section to the new node.
-            newNode.assignSourceSection(sourceSection);
-        }
-        onReplace(newNode, reason);
-        ((Node) newNode).parent = this.parent;
-        if (!NodeUtil.replaceChild(this.parent, this, newNode)) {
-            fixupTree();
-        }
-        reportReplace(this, newNode, reason);
+        replaceHelper(newNode, reason);
         return newNode;
     }
 
     /**
-     * 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 = getRootNode();
-        if (rootNode == null) {
-            throw new UnsupportedOperationException("Tree does not have a root node.");
-        }
-        int fixCount = rootNode.fixupChildren();
-        assert fixCount != 0 : "sanity check failed: missing @Child[ren] or adoptChild?";
-        // if nothing had to be fixed, rewrite failed due to node not being a proper child.
-    }
-
-    private int fixupChildren() {
-        int fixCount = 0;
-        for (Node child : getChildren()) {
-            if (child != null) {
-                if (child.parent != this) {
-                    child.parent = this;
-                    fixCount++;
-                }
-                fixCount += child.fixupChildren();
-            }
-        }
-        return fixCount;
-    }
-
-    /**
      * Replaces this node with another node. If there is a source section (see
      * {@link #getSourceSection()}) associated with this node, it is transferred to the new node.
      * 
@@ -244,6 +266,27 @@
         return replace(newNode, "");
     }
 
+    private void replaceHelper(Node newNode, CharSequence reason) {
+        CompilerAsserts.neverPartOfCompilation();
+        if (this.getParent() == null) {
+            throw new IllegalStateException("This node cannot be replaced, because it does not yet have a parent.");
+        }
+        if (sourceSection != null && newNode.getSourceSection() == null) {
+            // Pass on the source section to the new node.
+            newNode.assignSourceSection(sourceSection);
+        }
+        // (aw) need to set parent *before* replace, so that (unsynchronized) getRootNode()
+        // will always find the root node
+        newNode.parent = this.parent;
+        if (NodeUtil.replaceChild(this.parent, this, newNode)) {
+            this.parent.adoptHelper(newNode);
+        } else {
+            this.parent.adoptUnadoptedHelper(newNode);
+        }
+        reportReplace(this, newNode, reason);
+        onReplace(newNode, reason);
+    }
+
     /**
      * Checks if this node is properly adopted by a parent and can be replaced.
      *