--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/schedule/SchedulePhase.java	Wed Jun 13 14:55:49 2012 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/schedule/SchedulePhase.java	Wed Jun 13 14:57:26 2012 +0200
@@ -126,7 +126,7 @@
         } else if (GraalOptions.ScheduleOutOfLoops && !(n instanceof VirtualObjectFieldNode) && !(n instanceof VirtualObjectNode)) {
             Block earliestBlock = earliestBlock(n);
             block = scheduleOutOfLoops(n, latestBlock, earliestBlock);
-            assert earliestBlock.dominates(block) : "Graph can not be scheduled : inconsistent for " + n;
+            assert earliestBlock.dominates(block) : "Graph can not be scheduled : inconsistent for " + n + " (" + earliestBlock + " needs to dominate " + block + ")";
         } else {
             block = latestBlock;
         }
@@ -216,8 +216,19 @@
         return result;
     }
 
+    /**
+     * Passes all blocks that a specific usage of a node is in to a given closure.
+     * This is more complex than just taking the usage's block because of of PhiNodes and FrameStates.
+     *
+     * @param node the node that needs to be scheduled
+     * @param usage the usage whose blocks need to be considered
+     * @param closure the closure that will be called for each block
+     */
     private void blocksForUsage(Node node, Node usage, BlockClosure closure) {
+        assert !(node instanceof PhiNode);
         if (usage instanceof PhiNode) {
+            // An input to a PhiNode is used at the end of the predecessor block that corresponds to the PhiNode input.
+            // One PhiNode can use an input multiple times, the closure will be called for each usage.
             PhiNode phi = (PhiNode) usage;
             MergeNode merge = phi.merge();
             Block mergeBlock = cfg.getNodeToBlock().get(merge);
@@ -235,7 +246,10 @@
                     closure.apply(mergeBlock.getPredecessors().get(i));
                 }
             }
-        } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) {
+        } else if (usage instanceof FrameState && ((FrameState) usage).block() != null && !(node instanceof FrameState)) {
+            // If a FrameState belongs to a MergeNode then it's inputs will be placed at the common dominator of all EndNodes.
+            // BUT only if the input is neither a PhiNode (this method is never called for PhiNodes) nor a FrameState.
+            // A FrameState input is an outer FrameState. They should be placed into the same block as the usage, which is handled by the else.
             MergeNode merge = ((FrameState) usage).block();
             Block block = null;
             for (Node pred : merge.cfgPredecessors()) {
@@ -243,6 +257,7 @@
             }
             closure.apply(block);
         } else {
+            // All other types of usages: Just put the input into the same block as the usage.
             assignBlockToNode(usage);
             closure.apply(cfg.getNodeToBlock().get(usage));
         }

--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java	Wed Jun 13 14:55:49 2012 +0200
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java	Wed Jun 13 14:57:26 2012 +0200
@@ -33,6 +33,7 @@
 import com.oracle.graal.graph.Node.Verbosity;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.PhiNode.PhiType;
+import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.type.*;
 
 public class FrameStateBuilder {
@@ -155,7 +156,7 @@
 
         } else if (block.isPhiAtMerge(currentValue)) {
             if (otherValue == null || currentValue.kind() != otherValue.kind()) {
-                deletePhi((PhiNode) currentValue);
+                propagateDelete((PhiNode) currentValue);
                 return null;
             }
             ((PhiNode) currentValue).addInput(otherValue);
@@ -180,45 +181,21 @@
         }
     }
 
-    private void deletePhi(PhiNode phi) {
-        if (phi.isDeleted()) {
+    private void propagateDelete(FloatingNode node) {
+        assert node instanceof PhiNode || node instanceof ValueProxyNode;
+        if (node.isDeleted()) {
             return;
         }
         // Collect all phi functions that use this phi so that we can delete them recursively (after we delete ourselfs to avoid circles).
-        List<PhiNode> phiUsages = phi.usages().filter(PhiNode.class).snapshot();
-        List<ValueProxyNode> vpnUsages = phi.usages().filter(ValueProxyNode.class).snapshot();
+        List<FloatingNode> propagateUsages = node.usages().filter(FloatingNode.class).filter(isA(PhiNode.class).or(ValueProxyNode.class)).snapshot();
 
         // Remove the phi function from all FrameStates where it is used and then delete it.
-        assert phi.usages().filter(isNotA(FrameState.class).nor(PhiNode.class).nor(ValueProxyNode.class)).isEmpty() : "phi function that gets deletes must only be used in frame states";
-        phi.replaceAtUsages(null);
-        phi.safeDelete();
-
-        for (PhiNode phiUsage : phiUsages) {
-            deletePhi(phiUsage);
-        }
-        for (ValueProxyNode proxyUsage : vpnUsages) {
-            deleteProxy(proxyUsage);
-        }
-    }
+        assert node.usages().filter(isNotA(FrameState.class).nor(PhiNode.class).nor(ValueProxyNode.class)).isEmpty() : "phi function that gets deletes must only be used in frame states";
+        node.replaceAtUsages(null);
+        node.safeDelete();
 
-    private void deleteProxy(ValueProxyNode proxy) {
-        if (proxy.isDeleted()) {
-            return;
-        }
-        // Collect all phi functions that use this phi so that we can delete them recursively (after we delete ourselfs to avoid circles).
-        List<PhiNode> phiUsages = proxy.usages().filter(PhiNode.class).snapshot();
-        List<ValueProxyNode> vpnUsages = proxy.usages().filter(ValueProxyNode.class).snapshot();
-
-        // Remove the proxy function from all FrameStates where it is used and then delete it.
-        assert proxy.usages().filter(isNotA(FrameState.class).nor(PhiNode.class).nor(ValueProxyNode.class)).isEmpty() : "phi function that gets deletes must only be used in frame states";
-        proxy.replaceAtUsages(null);
-        proxy.safeDelete();
-
-        for (PhiNode phiUsage : phiUsages) {
-            deletePhi(phiUsage);
-        }
-        for (ValueProxyNode proxyUsage : vpnUsages) {
-            deleteProxy(proxyUsage);
+        for (FloatingNode phiUsage : propagateUsages) {
+            propagateDelete(phiUsage);
         }
     }
 
@@ -262,7 +239,7 @@
     public void cleanupDeletedPhis() {
         for (int i = 0; i < localsSize(); i++) {
             if (localAt(i) != null && localAt(i).isDeleted()) {
-                assert localAt(i) instanceof PhiNode : "Only phi functions can be deleted during parsing";
+                assert localAt(i) instanceof PhiNode || localAt(i) instanceof ValueProxyNode : "Only phi and value proxies can be deleted during parsing: " + localAt(i);
                 storeLocal(i, null);
             }
         }