# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1426246027 -3600
# Node ID 79682c7f2ec7b18f56728c8e40b6f8ae9123469a
# Parent  5d624638e8a55b14ac680af58a368f48bc84f017# Parent  e87d55dfbbbb579b16654bcddd0adfac901a36a0
Merge.

diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/LocationIdentity.java
--- a/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/LocationIdentity.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/LocationIdentity.java	Fri Mar 13 12:27:07 2015 +0100
@@ -59,4 +59,8 @@
     default boolean isImmutable() {
         return false;
     }
+
+    default boolean isMutable() {
+        return !isImmutable();
+    }
 }
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java	Fri Mar 13 12:27:07 2015 +0100
@@ -89,6 +89,14 @@
     }
 
     /**
+     * True if block {@code a} dominates block {@code b} and {@code a} is not identical block to
+     * {@code b}.
+     */
+    static boolean strictlyDominates(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
+        return a != b && dominates(a, b);
+    }
+
+    /**
      * True if block {@code a} dominates block {@code b}.
      */
     static boolean dominates(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java	Fri Mar 13 12:27:07 2015 +0100
@@ -305,7 +305,6 @@
 
     protected static String getCanonicalGraphString(StructuredGraph graph, boolean excludeVirtual, boolean checkConstants) {
         SchedulePhase schedule = new SchedulePhase(SchedulingStrategy.EARLIEST);
-        schedule.setScheduleConstants(true);
         schedule.apply(graph);
 
         NodeMap<Integer> canonicalId = graph.createNodeMap();
@@ -325,7 +324,7 @@
             }
             result.append("\n");
             for (Node node : schedule.getBlockToNodesMap().get(block)) {
-                if (node.isAlive()) {
+                if (node instanceof ValueNode && node.isAlive()) {
                     if (!excludeVirtual || !(node instanceof VirtualObjectNode || node instanceof ProxyNode)) {
                         if (node instanceof ConstantNode) {
                             String name = checkConstants ? node.toString(Verbosity.Name) : node.getClass().getSimpleName();
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraphScheduleTest.java
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraphScheduleTest.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraphScheduleTest.java	Fri Mar 13 12:27:07 2015 +0100
@@ -45,7 +45,7 @@
         Block aBlock = nodeToBlock.get(a);
 
         if (bBlock == aBlock) {
-            List<ValueNode> instructions = ibp.nodesFor(bBlock);
+            List<Node> instructions = ibp.nodesFor(bBlock);
             Assert.assertTrue(instructions.indexOf(b) > instructions.indexOf(a));
         } else {
             Block block = bBlock;
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java	Fri Mar 13 12:27:07 2015 +0100
@@ -23,10 +23,12 @@
 package com.oracle.graal.compiler.test;
 
 import static com.oracle.graal.compiler.common.GraalOptions.*;
+
 import java.util.*;
 
 import org.junit.*;
 
+import com.oracle.graal.api.directives.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.debug.Debug.Scope;
 import com.oracle.graal.graph.*;
@@ -251,6 +253,62 @@
     }
 
     /**
+     * Here the read should not float out of the loop.
+     */
+    public static int testLoop6Snippet(int a, int b, MemoryScheduleTest obj) {
+        int ret = 0;
+        int bb = b;
+        for (int i = 0; i < a; i++) {
+            ret = obj.hash;
+            if (a > 10) {
+                bb++;
+            } else {
+                bb--;
+                for (int j = 0; j < b; ++j) {
+                    obj.hash = 3;
+                }
+            }
+            ret = ret / 10;
+        }
+        return ret + bb;
+    }
+
+    @Test
+    public void testLoop6() {
+        SchedulePhase schedule = getFinalSchedule("testLoop6Snippet", TestMode.WITHOUT_FRAMESTATES);
+        assertDeepEquals(13, schedule.getCFG().getBlocks().size());
+        assertReadWithinStartBlock(schedule, false);
+        assertReadWithinAllReturnBlocks(schedule, false);
+    }
+
+    /**
+     * Here the read should not float to the end.
+     */
+    public static int testLoop7Snippet(int a, int b) {
+        int result = container.a;
+        for (int i = 0; i < a; i++) {
+            if (b < 0) {
+                container.b = 10;
+                break;
+            } else {
+                for (int j = 0; j < b; j++) {
+                    container.a = 0;
+                }
+            }
+        }
+        GraalDirectives.controlFlowAnchor();
+        return result;
+    }
+
+    @Test
+    public void testLoop7() {
+        SchedulePhase schedule = getFinalSchedule("testLoop7Snippet", TestMode.WITHOUT_FRAMESTATES);
+        assertDeepEquals(10, schedule.getCFG().getBlocks().size());
+        assertReadWithinStartBlock(schedule, true);
+        assertReadWithinAllReturnBlocks(schedule, false);
+    }
+
+    /**
      * Here the read should float to the end (into the same block as the return).
      */
     public static int testArrayCopySnippet(Integer intValue, char[] a, char[] b, int len) {
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SchedulingTest.java
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SchedulingTest.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SchedulingTest.java	Fri Mar 13 12:27:07 2015 +0100
@@ -60,10 +60,10 @@
         NodeMap<Block> nodeToBlock = schedule.getCFG().getNodeToBlock();
         assertTrue(graph.getNodes().filter(LoopExitNode.class).count() == 1);
         LoopExitNode loopExit = graph.getNodes().filter(LoopExitNode.class).first();
-        List<ValueNode> list = schedule.nodesFor(nodeToBlock.get(loopExit));
+        List<Node> list = schedule.nodesFor(nodeToBlock.get(loopExit));
         for (BinaryArithmeticNode<?> node : graph.getNodes().filter(BinaryArithmeticNode.class)) {
             if (!(node instanceof AddNode)) {
-                assertTrue(nodeToBlock.get(node) == nodeToBlock.get(loopExit));
+                assertTrue(node.toString(), nodeToBlock.get(node) == nodeToBlock.get(loopExit));
                 assertTrue(list.indexOf(node) + " < " + list.indexOf(loopExit) + ", " + node + ", " + loopExit, list.indexOf(node) < list.indexOf(loopExit));
             }
         }
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Fri Mar 13 12:27:07 2015 +0100
@@ -269,7 +269,6 @@
             graph.maybeCompress();
 
             SchedulePhase schedule = new SchedulePhase();
-            schedule.setScheduleConstants(true);
             schedule.apply(graph);
             Debug.dump(schedule, "Final HIR schedule");
             return schedule;
@@ -284,7 +283,6 @@
             // Repeatedly run the LIR code generation pass to improve statistical profiling results.
             for (int i = 0; i < EmitLIRRepeatCount.getValue(); i++) {
                 SchedulePhase dummySchedule = new SchedulePhase();
-                dummySchedule.setScheduleConstants(true);
                 dummySchedule.apply(graph);
                 emitLIR(backend, target, dummySchedule, graph, stub, cc, registerConfig, lirSuites);
             }
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java	Fri Mar 13 12:27:07 2015 +0100
@@ -26,6 +26,7 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.graph.*;
 import com.oracle.graal.lir.gen.*;
 import com.oracle.graal.lir.phases.*;
 import com.oracle.graal.nodes.*;
@@ -61,7 +62,7 @@
         context.lirGen.beforeRegisterAllocation();
     }
 
-    private static void emitBlock(NodeLIRBuilderTool nodeLirGen, LIRGenerationResult lirGenRes, Block b, StructuredGraph graph, BlockMap<List<ValueNode>> blockMap) {
+    private static void emitBlock(NodeLIRBuilderTool nodeLirGen, LIRGenerationResult lirGenRes, Block b, StructuredGraph graph, BlockMap<List<Node>> blockMap) {
         if (lirGenRes.getLIR().getLIRforBlock(b) == null) {
             for (Block pred : b.getPredecessors()) {
                 if (!b.isLoopHeader() || !pred.isLoopEnd()) {
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/NodeLIRBuilder.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/NodeLIRBuilder.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/NodeLIRBuilder.java	Fri Mar 13 12:27:07 2015 +0100
@@ -92,7 +92,7 @@
     private ValueNode currentInstruction;
     private ValueNode lastInstructionPrinted; // Debugging only
 
-    private Map<Class<? extends ValueNode>, List<MatchStatement>> matchRules;
+    private Map<Class<? extends Node>, List<MatchStatement>> matchRules;
 
     public NodeLIRBuilder(StructuredGraph graph, LIRGeneratorTool gen) {
         this.gen = gen;
@@ -116,18 +116,18 @@
      * @param node A node that produces a result value.
      */
     @Override
-    public Value operand(ValueNode node) {
+    public Value operand(Node node) {
         Value operand = getOperand(node);
         assert operand != null : String.format("missing operand for %1s", node);
         return operand;
     }
 
     @Override
-    public boolean hasOperand(ValueNode node) {
+    public boolean hasOperand(Node node) {
         return getOperand(node) != null;
     }
 
-    private Value getOperand(ValueNode node) {
+    private Value getOperand(Node node) {
         if (nodeOperands == null) {
             return null;
         }
@@ -162,7 +162,7 @@
      * Used by the {@link MatchStatement} machinery to override the generation LIR for some
      * ValueNodes.
      */
-    public void setMatchResult(ValueNode x, Value operand) {
+    public void setMatchResult(Node x, Value operand) {
         assert operand.equals(ComplexMatchValue.INTERIOR_MATCH) || operand instanceof ComplexMatchValue;
         assert operand instanceof ComplexMatchValue || x.getUsageCount() == 1 : "interior matches must be single user";
         assert nodeOperands != null && nodeOperands.get(x) == null : "operand cannot be set twice";
@@ -191,7 +191,7 @@
         gen.append(op);
     }
 
-    public void doBlock(Block block, StructuredGraph graph, BlockMap<List<ValueNode>> blockMap) {
+    public void doBlock(Block block, StructuredGraph graph, BlockMap<List<Node>> blockMap) {
         gen.doBlockStart(block);
 
         if (block == gen.getResult().getLIR().getControlFlowGraph().getStartBlock()) {
@@ -201,41 +201,44 @@
             assert block.getPredecessorCount() > 0;
         }
 
-        List<ValueNode> nodes = blockMap.get(block);
+        List<Node> nodes = blockMap.get(block);
 
         // Allow NodeLIRBuilder subclass to specialize code generation of any interesting groups
         // of instructions
         matchComplexExpressions(nodes);
 
         for (int i = 0; i < nodes.size(); i++) {
-            ValueNode valueNode = nodes.get(i);
-            if (Options.TraceLIRGeneratorLevel.getValue() >= 3) {
-                TTY.println("LIRGen for " + valueNode);
-            }
-            Value operand = getOperand(valueNode);
-            if (operand == null) {
-                if (!peephole(valueNode)) {
-                    try {
-                        doRoot(valueNode);
-                    } catch (GraalInternalError e) {
-                        throw GraalGraphInternalError.transformAndAddContext(e, valueNode);
-                    } catch (Throwable e) {
-                        throw new GraalGraphInternalError(e).addContext(valueNode);
+            Node node = nodes.get(i);
+            if (node instanceof ValueNode) {
+                ValueNode valueNode = (ValueNode) node;
+                if (Options.TraceLIRGeneratorLevel.getValue() >= 3) {
+                    TTY.println("LIRGen for " + valueNode);
+                }
+                Value operand = getOperand(valueNode);
+                if (operand == null) {
+                    if (!peephole(valueNode)) {
+                        try {
+                            doRoot(valueNode);
+                        } catch (GraalInternalError e) {
+                            throw GraalGraphInternalError.transformAndAddContext(e, valueNode);
+                        } catch (Throwable e) {
+                            throw new GraalGraphInternalError(e).addContext(valueNode);
+                        }
                     }
+                } else if (ComplexMatchValue.INTERIOR_MATCH.equals(operand)) {
+                    // Doesn't need to be evaluated
+                    Debug.log("interior match for %s", valueNode);
+                } else if (operand instanceof ComplexMatchValue) {
+                    Debug.log("complex match for %s", valueNode);
+                    ComplexMatchValue match = (ComplexMatchValue) operand;
+                    operand = match.evaluate(this);
+                    if (operand != null) {
+                        setResult(valueNode, operand);
+                    }
+                } else {
+                    // There can be cases in which the result of an instruction is already set
+                    // before by other instructions.
                 }
-            } else if (ComplexMatchValue.INTERIOR_MATCH.equals(operand)) {
-                // Doesn't need to be evaluated
-                Debug.log("interior match for %s", valueNode);
-            } else if (operand instanceof ComplexMatchValue) {
-                Debug.log("complex match for %s", valueNode);
-                ComplexMatchValue match = (ComplexMatchValue) operand;
-                operand = match.evaluate(this);
-                if (operand != null) {
-                    setResult(valueNode, operand);
-                }
-            } else {
-                // There can be cases in which the result of an instruction is already set
-                // before by other instructions.
             }
         }
 
@@ -256,19 +259,19 @@
         gen.doBlockEnd(block);
     }
 
-    protected void matchComplexExpressions(List<ValueNode> nodes) {
+    protected void matchComplexExpressions(List<Node> nodes) {
         if (matchRules != null) {
             try (Scope s = Debug.scope("MatchComplexExpressions")) {
                 if (LogVerbose.getValue()) {
                     int i = 0;
-                    for (ValueNode node : nodes) {
+                    for (Node node : nodes) {
                         Debug.log("%d: (%s) %1S", i++, node.getUsageCount(), node);
                     }
                 }
 
                 // Match the nodes in backwards order to encourage longer matches.
                 for (int index = nodes.size() - 1; index >= 0; index--) {
-                    ValueNode node = nodes.get(index);
+                    Node node = nodes.get(index);
                     if (getOperand(node) != null) {
                         continue;
                     }
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchContext.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchContext.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchContext.java	Fri Mar 13 12:27:07 2015 +0100
@@ -30,7 +30,7 @@
 import com.oracle.graal.compiler.gen.*;
 import com.oracle.graal.compiler.match.MatchPattern.Result;
 import com.oracle.graal.debug.*;
-import com.oracle.graal.nodes.*;
+import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.virtual.*;
 
@@ -39,15 +39,15 @@
  */
 public class MatchContext {
 
-    private final ValueNode root;
+    private final Node root;
 
-    private final List<ValueNode> nodes;
+    private final List<Node> nodes;
 
     private final MatchStatement rule;
 
     private Map<String, NamedNode> namedNodes;
 
-    private ArrayList<ValueNode> consumed;
+    private ArrayList<Node> consumed;
 
     private int startIndex;
 
@@ -56,16 +56,16 @@
     private final NodeLIRBuilder builder;
 
     private static class NamedNode {
-        final Class<? extends ValueNode> type;
-        final ValueNode value;
+        final Class<? extends Node> type;
+        final Node value;
 
-        NamedNode(Class<? extends ValueNode> type, ValueNode value) {
+        NamedNode(Class<? extends Node> type, Node value) {
             this.type = type;
             this.value = value;
         }
     }
 
-    public MatchContext(NodeLIRBuilder builder, MatchStatement rule, int index, ValueNode node, List<ValueNode> nodes) {
+    public MatchContext(NodeLIRBuilder builder, MatchStatement rule, int index, Node node, List<Node> nodes) {
         this.builder = builder;
         this.rule = rule;
         this.root = node;
@@ -75,11 +75,11 @@
         startIndex = endIndex = index;
     }
 
-    public ValueNode getRoot() {
+    public Node getRoot() {
         return root;
     }
 
-    public Result captureNamedValue(String name, Class<? extends ValueNode> type, ValueNode value) {
+    public Result captureNamedValue(String name, Class<? extends Node> type, Node value) {
         if (namedNodes == null) {
             namedNodes = new HashMap<>(2);
         }
@@ -99,7 +99,7 @@
     public Result validate() {
         // Ensure that there's no unsafe work in between these operations.
         for (int i = startIndex; i <= endIndex; i++) {
-            ValueNode node = nodes.get(i);
+            Node node = nodes.get(i);
             if (node instanceof VirtualObjectNode || node instanceof FloatingNode) {
                 // The order of evaluation of these nodes controlled by data dependence so they
                 // don't interfere with this match.
@@ -108,7 +108,7 @@
                 if (LogVerbose.getValue()) {
                     Debug.log("unexpected node %s", node);
                     for (int j = startIndex; j <= endIndex; j++) {
-                        ValueNode theNode = nodes.get(j);
+                        Node theNode = nodes.get(j);
                         Debug.log("%s(%s) %1s", (consumed != null && consumed.contains(theNode) || theNode == root) ? "*" : " ", theNode.getUsageCount(), theNode);
                     }
                 }
@@ -131,7 +131,7 @@
             Debug.log("with nodes %s", rule.formatMatch(root));
         }
         if (consumed != null) {
-            for (ValueNode node : consumed) {
+            for (Node node : consumed) {
                 // All the interior nodes should be skipped during the normal doRoot calls in
                 // NodeLIRBuilder so mark them as interior matches. The root of the match will get a
                 // closure which will be evaluated to produce the final LIR.
@@ -146,7 +146,7 @@
      *
      * @return Result.OK if the node can be safely consumed.
      */
-    public Result consume(ValueNode node) {
+    public Result consume(Node node) {
         assert node.getUsageCount() <= 1 : "should have already been checked";
 
         // Check NOT_IN_BLOCK first since that usually implies ALREADY_USED
@@ -174,7 +174,7 @@
      * @return the matched node
      * @throws GraalInternalError is the named node doesn't exist.
      */
-    public ValueNode namedNode(String name) {
+    public Node namedNode(String name) {
         if (namedNodes != null) {
             NamedNode value = namedNodes.get(name);
             if (value != null) {
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchPattern.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchPattern.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchPattern.java	Fri Mar 13 12:27:07 2015 +0100
@@ -25,7 +25,6 @@
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodeinfo.*;
-import com.oracle.graal.nodes.*;
 
 /**
  * A simple recursive pattern matcher for a DAG of nodes.
@@ -50,11 +49,11 @@
     static class Result {
         final MatchResultCode code;
 
-        final ValueNode node;
+        final Node node;
 
         final MatchPattern matcher;
 
-        Result(MatchResultCode result, ValueNode node, MatchPattern matcher) {
+        Result(MatchResultCode result, Node node, MatchPattern matcher) {
             this.code = result;
             this.node = node;
             this.matcher = matcher;
@@ -75,32 +74,32 @@
         private static final Result CACHED_NOT_SAFE = new Result(MatchResultCode.NOT_SAFE, null, null);
         private static final Result CACHED_ALREADY_USED = new Result(MatchResultCode.ALREADY_USED, null, null);
 
-        static Result wrongClass(ValueNode node, MatchPattern matcher) {
+        static Result wrongClass(Node node, MatchPattern matcher) {
             MatchResult_WRONG_CLASS.increment();
             return Debug.isEnabled() ? new Result(MatchResultCode.WRONG_CLASS, node, matcher) : CACHED_WRONG_CLASS;
         }
 
-        static Result namedValueMismatch(ValueNode node, MatchPattern matcher) {
+        static Result namedValueMismatch(Node node, MatchPattern matcher) {
             MatchResult_NAMED_VALUE_MISMATCH.increment();
             return Debug.isEnabled() ? new Result(MatchResultCode.NAMED_VALUE_MISMATCH, node, matcher) : CACHED_NAMED_VALUE_MISMATCH;
         }
 
-        static Result tooManyUsers(ValueNode node, MatchPattern matcher) {
+        static Result tooManyUsers(Node node, MatchPattern matcher) {
             MatchResult_TOO_MANY_USERS.increment();
             return Debug.isEnabled() ? new Result(MatchResultCode.TOO_MANY_USERS, node, matcher) : CACHED_TOO_MANY_USERS;
         }
 
-        static Result notInBlock(ValueNode node, MatchPattern matcher) {
+        static Result notInBlock(Node node, MatchPattern matcher) {
             MatchResult_NOT_IN_BLOCK.increment();
             return Debug.isEnabled() ? new Result(MatchResultCode.NOT_IN_BLOCK, node, matcher) : CACHED_NOT_IN_BLOCK;
         }
 
-        static Result notSafe(ValueNode node, MatchPattern matcher) {
+        static Result notSafe(Node node, MatchPattern matcher) {
             MatchResult_NOT_SAFE.increment();
             return Debug.isEnabled() ? new Result(MatchResultCode.NOT_SAFE, node, matcher) : CACHED_NOT_SAFE;
         }
 
-        static Result alreadyUsed(ValueNode node, MatchPattern matcher) {
+        static Result alreadyUsed(Node node, MatchPattern matcher) {
             MatchResult_ALREADY_USED.increment();
             return Debug.isEnabled() ? new Result(MatchResultCode.ALREADY_USED, node, matcher) : CACHED_ALREADY_USED;
         }
@@ -121,7 +120,7 @@
     /**
      * The expected type of the node. It must match exactly.
      */
-    private final Class<? extends ValueNode> nodeClass;
+    private final Class<? extends Node> nodeClass;
 
     /**
      * An optional name for this node. A name can occur multiple times in a match and that name must
@@ -151,7 +150,7 @@
         this(null, name, singleUser);
     }
 
-    public MatchPattern(Class<? extends ValueNode> nodeClass, String name, boolean singleUser) {
+    public MatchPattern(Class<? extends Node> nodeClass, String name, boolean singleUser) {
         this.nodeClass = nodeClass;
         this.name = name;
         this.singleUser = singleUser;
@@ -159,7 +158,7 @@
         this.inputs = null;
     }
 
-    private MatchPattern(Class<? extends ValueNode> nodeClass, String name, boolean singleUser, MatchPattern[] patterns, Position[] inputs) {
+    private MatchPattern(Class<? extends Node> nodeClass, String name, boolean singleUser, MatchPattern[] patterns, Position[] inputs) {
         assert inputs == null || inputs.length == patterns.length;
         this.nodeClass = nodeClass;
         this.name = name;
@@ -168,23 +167,23 @@
         this.inputs = inputs;
     }
 
-    public MatchPattern(Class<? extends ValueNode> nodeClass, String name, MatchPattern first, Position[] inputs, boolean singleUser) {
+    public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, Position[] inputs, boolean singleUser) {
         this(nodeClass, name, singleUser, new MatchPattern[]{first}, inputs);
     }
 
-    public MatchPattern(Class<? extends ValueNode> nodeClass, String name, MatchPattern first, MatchPattern second, Position[] inputs, boolean singleUser) {
+    public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, MatchPattern second, Position[] inputs, boolean singleUser) {
         this(nodeClass, name, singleUser, new MatchPattern[]{first, second}, inputs);
     }
 
-    public MatchPattern(Class<? extends ValueNode> nodeClass, String name, MatchPattern first, MatchPattern second, MatchPattern third, Position[] inputs, boolean singleUser) {
+    public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, MatchPattern second, MatchPattern third, Position[] inputs, boolean singleUser) {
         this(nodeClass, name, singleUser, new MatchPattern[]{first, second, third}, inputs);
     }
 
-    Class<? extends ValueNode> nodeClass() {
+    Class<? extends Node> nodeClass() {
         return nodeClass;
     }
 
-    private Result matchType(ValueNode node) {
+    private Result matchType(Node node) {
         if (nodeClass != null && node.getClass() != nodeClass) {
             return Result.wrongClass(node, this);
         }
@@ -198,7 +197,7 @@
      * @param context
      * @return Result.OK is the pattern can be safely matched.
      */
-    Result matchUsage(ValueNode node, MatchContext context) {
+    Result matchUsage(Node node, MatchContext context) {
         Result result = matchUsage(node, context, true);
         if (result == Result.OK) {
             result = context.validate();
@@ -206,7 +205,7 @@
         return result;
     }
 
-    private Result matchUsage(ValueNode node, MatchContext context, boolean atRoot) {
+    private Result matchUsage(Node node, MatchContext context, boolean atRoot) {
         Result result = matchType(node);
         if (result != Result.OK) {
             return result;
@@ -240,11 +239,11 @@
      * @param statement
      * @return Result.OK if the shape of the pattern matches.
      */
-    public Result matchShape(ValueNode node, MatchStatement statement) {
+    public Result matchShape(Node node, MatchStatement statement) {
         return matchShape(node, statement, true);
     }
 
-    private Result matchShape(ValueNode node, MatchStatement statement, boolean atRoot) {
+    private Result matchShape(Node node, MatchStatement statement, boolean atRoot) {
         Result result = matchType(node);
         if (result != Result.OK) {
             return result;
@@ -271,7 +270,7 @@
      * rule. It's assumed that a match has already succeeded against this rule, otherwise the
      * printing may produce exceptions.
      */
-    public String formatMatch(ValueNode root) {
+    public String formatMatch(Node root) {
         String result = String.format("%s", root);
         if (patterns.length == 0) {
             return result;
@@ -288,8 +287,8 @@
         }
     }
 
-    private ValueNode getInput(int index, ValueNode node) {
-        return (ValueNode) inputs[index].get(node);
+    private Node getInput(int index, Node node) {
+        return inputs[index].get(node);
     }
 
     @Override
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchRuleRegistry.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchRuleRegistry.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchRuleRegistry.java	Fri Mar 13 12:27:07 2015 +0100
@@ -32,7 +32,6 @@
 import com.oracle.graal.debug.*;
 import com.oracle.graal.debug.Debug.Scope;
 import com.oracle.graal.graph.*;
-import com.oracle.graal.nodes.*;
 
 public class MatchRuleRegistry {
 
@@ -45,7 +44,7 @@
      * @param names
      * @return an array of Position objects corresponding to the named fields.
      */
-    public static Position[] findPositions(NodeClass<? extends ValueNode> nodeClass, String[] names) {
+    public static Position[] findPositions(NodeClass<? extends Node> nodeClass, String[] names) {
         Position[] result = new Position[names.length];
         for (int i = 0; i < names.length; i++) {
             Edges edges = nodeClass.getInputEdges();
@@ -61,7 +60,7 @@
         return result;
     }
 
-    private static final HashMap<Class<? extends NodeLIRBuilder>, Map<Class<? extends ValueNode>, List<MatchStatement>>> registry = new HashMap<>();
+    private static final HashMap<Class<? extends NodeLIRBuilder>, Map<Class<? extends Node>, List<MatchStatement>>> registry = new HashMap<>();
 
     /**
      * Collect all the {@link MatchStatement}s defined by the superclass chain of theClass.
@@ -69,11 +68,11 @@
      * @param theClass
      * @return the set of {@link MatchStatement}s applicable to theClass.
      */
-    public static synchronized Map<Class<? extends ValueNode>, List<MatchStatement>> lookup(Class<? extends NodeLIRBuilder> theClass) {
-        Map<Class<? extends ValueNode>, List<MatchStatement>> result = registry.get(theClass);
+    public static synchronized Map<Class<? extends Node>, List<MatchStatement>> lookup(Class<? extends NodeLIRBuilder> theClass) {
+        Map<Class<? extends Node>, List<MatchStatement>> result = registry.get(theClass);
 
         if (result == null) {
-            Map<Class<? extends ValueNode>, List<MatchStatement>> rules = createRules(theClass);
+            Map<Class<? extends Node>, List<MatchStatement>> rules = createRules(theClass);
             registry.put(theClass, rules);
             assert registry.get(theClass) == rules;
             result = rules;
@@ -81,7 +80,7 @@
             if (LogVerbose.getValue()) {
                 try (Scope s = Debug.scope("MatchComplexExpressions")) {
                     Debug.log("Match rules for %s", theClass.getSimpleName());
-                    for (Entry<Class<? extends ValueNode>, List<MatchStatement>> entry : result.entrySet()) {
+                    for (Entry<Class<? extends Node>, List<MatchStatement>> entry : result.entrySet()) {
                         Debug.log("  For node class: %s", entry.getKey());
                         for (MatchStatement statement : entry.getValue()) {
                             Debug.log("    %s", statement.getPattern());
@@ -101,7 +100,7 @@
      * This is a separate, public method so that external clients can create rules with a custom
      * lookup and without the default caching behavior.
      */
-    public static Map<Class<? extends ValueNode>, List<MatchStatement>> createRules(Class<? extends NodeLIRBuilder> theClass) {
+    public static Map<Class<? extends Node>, List<MatchStatement>> createRules(Class<? extends NodeLIRBuilder> theClass) {
         HashMap<Class<? extends NodeLIRBuilder>, MatchStatementSet> matchSets = new HashMap<>();
         Iterable<MatchStatementSet> sl = Services.load(MatchStatementSet.class);
         for (MatchStatementSet rules : sl) {
@@ -110,14 +109,14 @@
 
         // Walk the class hierarchy collecting lists and merge them together. The subclass
         // rules are first which gives them preference over earlier rules.
-        Map<Class<? extends ValueNode>, List<MatchStatement>> rules = new HashMap<>();
+        Map<Class<? extends Node>, List<MatchStatement>> rules = new HashMap<>();
         Class<?> currentClass = theClass;
         do {
             MatchStatementSet matchSet = matchSets.get(currentClass);
             if (matchSet != null) {
                 List<MatchStatement> statements = matchSet.statements();
                 for (MatchStatement statement : statements) {
-                    Class<? extends ValueNode> nodeClass = statement.getPattern().nodeClass();
+                    Class<? extends Node> nodeClass = statement.getPattern().nodeClass();
                     List<MatchStatement> current = rules.get(nodeClass);
                     if (current == null) {
                         current = new ArrayList<>();
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchStatement.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchStatement.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchStatement.java	Fri Mar 13 12:27:07 2015 +0100
@@ -33,11 +33,10 @@
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodeinfo.*;
-import com.oracle.graal.nodes.*;
 
 /**
  * A named {@link MatchPattern} along with a {@link MatchGenerator} that can be evaluated to replace
- * one or more {@link ValueNode}s with a single {@link Value}.
+ * one or more {@link Node}s with a single {@link Value}.
  */
 
 public class MatchStatement {
@@ -80,7 +79,7 @@
      * @return true if the statement matched something and set a {@link ComplexMatchResult} to be
      *         evaluated by the NodeLIRBuilder.
      */
-    public boolean generate(NodeLIRBuilder builder, int index, ValueNode node, List<ValueNode> nodes) {
+    public boolean generate(NodeLIRBuilder builder, int index, Node node, List<Node> nodes) {
         assert index == nodes.indexOf(node);
         // Check that the basic shape matches
         Result result = pattern.matchShape(node, this);
@@ -115,8 +114,7 @@
 
     /**
      * @param context
-     * @return the ValueNodes captured by the match rule in the order expected by the
-     *         generatorMethod
+     * @return the Nodes captured by the match rule in the order expected by the generatorMethod
      */
     private Object[] buildArgList(MatchContext context) {
         Object[] result = new Object[arguments.length];
@@ -133,7 +131,7 @@
         return result;
     }
 
-    public String formatMatch(ValueNode root) {
+    public String formatMatch(Node root) {
         return pattern.formatMatch(root);
     }
 
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryArithmeticNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryArithmeticNode.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryArithmeticNode.java	Fri Mar 13 12:27:07 2015 +0100
@@ -246,7 +246,7 @@
 
     protected static boolean livesLonger(ValueNode after, ValueNode value, NodeMappableLIRBuilder builder) {
         for (Node usage : value.usages()) {
-            if (usage != after && usage instanceof ValueNode && builder.hasOperand(((ValueNode) usage))) {
+            if (usage != after && usage instanceof ValueNode && builder.hasOperand(usage)) {
                 return true;
             }
         }
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java	Fri Mar 13 12:27:07 2015 +0100
@@ -24,9 +24,11 @@
 
 import java.util.*;
 
+import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.extended.*;
 
 public final class Block extends AbstractBlockBase<Block> {
 
@@ -39,6 +41,8 @@
 
     protected Block postdominator;
     protected Block distancedDominatorCache;
+    private LocationSet killLocations;
+    private LocationSet killLocationsBetweenThisAndDominator;
 
     protected Block(AbstractBeginNode node) {
         this.beginNode = node;
@@ -189,4 +193,85 @@
         }
         return result;
     }
+
+    public boolean canKill(LocationIdentity location) {
+        if (location.isImmutable()) {
+            return false;
+        }
+        return getKillLocations().contains(location);
+    }
+
+    public LocationSet getKillLocations() {
+        if (killLocations == null) {
+            killLocations = calcKillLocations();
+        }
+        return killLocations;
+    }
+
+    private LocationSet calcKillLocations() {
+        LocationSet result = new LocationSet();
+        for (FixedNode node : this.getNodes()) {
+            if (node instanceof MemoryCheckpoint.Single) {
+                LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
+                result.add(identity);
+            } else if (node instanceof MemoryCheckpoint.Multi) {
+                for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
+                    result.add(identity);
+                }
+            }
+            if (result.isKillAll()) {
+                break;
+            }
+        }
+        return result;
+    }
+
+    public boolean canKillBetweenThisAndDominator(LocationIdentity location) {
+        if (location.isImmutable()) {
+            return false;
+        }
+        return this.getKillLocationsBetweenThisAndDominator().contains(location);
+    }
+
+    private LocationSet getKillLocationsBetweenThisAndDominator() {
+        if (this.killLocationsBetweenThisAndDominator == null) {
+            LocationSet dominatorResult = new LocationSet();
+            Block stopBlock = getDominator();
+            for (Block b : this.getPredecessors()) {
+                if (b != stopBlock && (!this.isLoopHeader() || b.getLoopDepth() < this.getLoopDepth())) {
+                    dominatorResult.addAll(b.getKillLocations());
+                    if (dominatorResult.isKillAll()) {
+                        break;
+                    }
+                    b.calcKillLocationsBetweenThisAndTarget(dominatorResult, stopBlock);
+                    if (dominatorResult.isKillAll()) {
+                        break;
+                    }
+                }
+            }
+            this.killLocationsBetweenThisAndDominator = dominatorResult;
+        }
+        return this.killLocationsBetweenThisAndDominator;
+    }
+
+    private void calcKillLocationsBetweenThisAndTarget(LocationSet result, Block stopBlock) {
+        assert AbstractControlFlowGraph.dominates(stopBlock, this);
+        if (stopBlock == this || result.isKillAll()) {
+            // We reached the stop block => nothing to do.
+            return;
+        } else {
+            if (stopBlock == this.getDominator()) {
+                result.addAll(this.getKillLocationsBetweenThisAndDominator());
+            } else {
+                // Divide and conquer: Aggregate kill locations from this to the dominator and then
+                // from the dominator onwards.
+                calcKillLocationsBetweenThisAndTarget(result, this.getDominator());
+                result.addAll(this.getDominator().getKillLocations());
+                if (result.isKillAll()) {
+                    return;
+                }
+                this.getDominator().calcKillLocationsBetweenThisAndTarget(result, stopBlock);
+            }
+        }
+    }
 }
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java	Fri Mar 13 12:27:07 2015 +0100
@@ -40,7 +40,7 @@
 
     public final StructuredGraph graph;
 
-    private final NodeMap<Block> nodeToBlock;
+    private NodeMap<Block> nodeToBlock;
     private List<Block> reversePostOrder;
     private List<Loop<Block>> loops;
 
@@ -365,4 +365,8 @@
         }
         return iterA;
     }
+
+    public void setNodeToBlock(NodeMap<Block> nodeMap) {
+        this.nodeToBlock = nodeMap;
+    }
 }
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/HIRLoop.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/HIRLoop.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/HIRLoop.java	Fri Mar 13 12:27:07 2015 +0100
@@ -22,11 +22,14 @@
  */
 package com.oracle.graal.nodes.cfg;
 
+import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.nodes.*;
 
 public class HIRLoop extends Loop<Block> {
 
+    private LocationSet killLocations;
+
     protected HIRLoop(Loop<Block> parent, int index, Block header) {
         super(parent, index, header);
     }
@@ -35,4 +38,29 @@
     public long numBackedges() {
         return ((LoopBeginNode) getHeader().getBeginNode()).loopEnds().count();
     }
+
+    protected LocationSet getKillLocations() {
+        if (killLocations == null) {
+            killLocations = new LocationSet();
+            for (Block b : this.getBlocks()) {
+                if (b.getLoop() == this) {
+                    killLocations.addAll(b.getKillLocations());
+                    if (killLocations.isKillAll()) {
+                        break;
+                    }
+                }
+            }
+        }
+        for (Loop<Block> child : this.getChildren()) {
+            if (killLocations.isKillAll()) {
+                break;
+            }
+            killLocations.addAll(((HIRLoop) child).getKillLocations());
+        }
+        return killLocations;
+    }
+
+    public boolean canKill(LocationIdentity location) {
+        return getKillLocations().contains(location);
+    }
 }
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/LocationSet.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/LocationSet.java	Fri Mar 13 12:27:07 2015 +0100
@@ -0,0 +1,137 @@
+/*
+ * Copyright (c) 2015, 2015, 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.nodes.cfg;
+
+import java.util.*;
+
+import com.oracle.graal.api.meta.*;
+
+public class LocationSet {
+    private LocationIdentity firstLocation;
+    private List<LocationIdentity> list;
+
+    public LocationSet() {
+        list = null;
+    }
+
+    public LocationSet(LocationSet other) {
+        this.firstLocation = other.firstLocation;
+        if (other.list != null && other.list.size() > 0) {
+            list = new ArrayList<>(other.list);
+        }
+    }
+
+    private void initList() {
+        if (list == null) {
+            list = new ArrayList<>(4);
+        }
+    }
+
+    public boolean isKillNone() {
+        return firstLocation == null;
+    }
+
+    public boolean isKillAll() {
+        return LocationIdentity.ANY_LOCATION.equals(firstLocation);
+    }
+
+    public void add(LocationIdentity location) {
+        if (this.isKillAll()) {
+            return;
+        } else if (LocationIdentity.ANY_LOCATION.equals(location)) {
+            firstLocation = location;
+            list = null;
+        } else {
+            if (firstLocation == null) {
+                firstLocation = location;
+            } else if (location.equals(firstLocation)) {
+                return;
+            } else {
+                initList();
+                for (int i = 0; i < list.size(); ++i) {
+                    LocationIdentity value = list.get(i);
+                    if (location.equals(value)) {
+                        return;
+                    }
+                }
+                list.add(location);
+            }
+        }
+    }
+
+    public void addAll(LocationSet other) {
+        if (other.firstLocation != null) {
+            add(other.firstLocation);
+        }
+        List<LocationIdentity> otherList = other.list;
+        if (otherList != null) {
+            for (LocationIdentity l : otherList) {
+                add(l);
+            }
+        }
+    }
+
+    public boolean contains(LocationIdentity locationIdentity) {
+        assert locationIdentity != null;
+        assert !locationIdentity.equals(LocationIdentity.ANY_LOCATION);
+        assert locationIdentity.isMutable();
+        if (LocationIdentity.ANY_LOCATION.equals(firstLocation)) {
+            return true;
+        }
+        if (locationIdentity.equals(firstLocation)) {
+            return true;
+        }
+        if (list != null) {
+            for (int i = 0; i < list.size(); ++i) {
+                LocationIdentity value = list.get(i);
+                if (locationIdentity.equals(value)) {
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    public List<LocationIdentity> getCopyAsList() {
+        ArrayList<LocationIdentity> result = new ArrayList<>();
+        if (firstLocation != null) {
+            result.add(firstLocation);
+        }
+        if (list != null) {
+            result.addAll(list);
+        }
+        return result;
+    }
+
+    @Override
+    public String toString() {
+        if (this.isKillAll()) {
+            return "KILLALL";
+        } else if (this.isKillNone()) {
+            return "KILLNONE";
+        } else {
+            List<LocationIdentity> copyAsList = getCopyAsList();
+            return Arrays.toString(copyAsList.toArray(new LocationIdentity[0]));
+        }
+    }
+}
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeLIRBuilderTool.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeLIRBuilderTool.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeLIRBuilderTool.java	Fri Mar 13 12:27:07 2015 +0100
@@ -28,6 +28,7 @@
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.compiler.common.type.*;
+import com.oracle.graal.graph.*;
 import com.oracle.graal.lir.*;
 import com.oracle.graal.lir.gen.*;
 import com.oracle.graal.nodes.*;
@@ -71,5 +72,5 @@
 
     Value[] visitInvokeArguments(CallingConvention cc, Collection<ValueNode> arguments);
 
-    void doBlock(Block block, StructuredGraph graph, BlockMap<List<ValueNode>> blockMap);
+    void doBlock(Block block, StructuredGraph graph, BlockMap<List<Node>> blockMap);
 }
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeMappableLIRBuilder.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeMappableLIRBuilder.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeMappableLIRBuilder.java	Fri Mar 13 12:27:07 2015 +0100
@@ -24,13 +24,14 @@
 package com.oracle.graal.nodes.spi;
 
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 
 public interface NodeMappableLIRBuilder {
 
-    Value operand(ValueNode object);
+    Value operand(Node object);
 
-    boolean hasOperand(ValueNode object);
+    boolean hasOperand(Node object);
 
     Value setResult(ValueNode x, Value operand);
 }
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java	Fri Mar 13 12:27:07 2015 +0100
@@ -289,7 +289,7 @@
             final LoweringToolImpl loweringTool = new LoweringToolImpl(context, startAnchor, activeGuards, b.getBeginNode());
 
             // Lower the instructions of this block.
-            List<ValueNode> nodes = schedule.nodesFor(b);
+            List<Node> nodes = schedule.nodesFor(b);
             for (Node node : nodes) {
 
                 if (node.isDeleted()) {
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ProfileCompiledMethodsPhase.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ProfileCompiledMethodsPhase.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ProfileCompiledMethodsPhase.java	Fri Mar 13 12:27:07 2015 +0100
@@ -46,7 +46,7 @@
  * a method and at each loop header.
  *
  * A schedule is created so that floating nodes can also be taken into account. The weight of a node
- * is determined heuristically in the {@link ProfileCompiledMethodsPhase#getNodeWeight(ValueNode)}
+ * is determined heuristically in the {@link ProfileCompiledMethodsPhase#getNodeWeight(Node)}
  * method.
  *
  * Additionally, there's a second counter that's only increased for code sections without invokes.
@@ -117,14 +117,14 @@
         double count = 0;
         for (Block block : blocks) {
             double blockProbability = probabilities.applyAsDouble(block.getBeginNode());
-            for (ValueNode node : schedule.getBlockToNodesMap().get(block)) {
+            for (Node node : schedule.getBlockToNodesMap().get(block)) {
                 count += blockProbability * getNodeWeight(node);
             }
         }
         return count;
     }
 
-    private static double getNodeWeight(ValueNode node) {
+    private static double getNodeWeight(Node node) {
         if (node instanceof AbstractMergeNode) {
             return ((AbstractMergeNode) node).phiPredecessorCount();
         } else if (node instanceof AbstractBeginNode || node instanceof AbstractEndNode || node instanceof MonitorIdNode || node instanceof ConstantNode || node instanceof ParameterNode ||
@@ -150,6 +150,8 @@
             return node.successors().count();
         } else if (node instanceof AbstractNewObjectNode) {
             return 10;
+        } else if (node instanceof VirtualState) {
+            return 0;
         }
         return 2;
     }
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ScheduledNodeIterator.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ScheduledNodeIterator.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ScheduledNodeIterator.java	Fri Mar 13 12:27:07 2015 +0100
@@ -40,7 +40,7 @@
 
     private FixedWithNextNode lastFixed;
     private FixedWithNextNode reconnect;
-    private ListIterator<ValueNode> iterator;
+    private ListIterator<Node> iterator;
 
     public void processNodes(Block block, SchedulePhase shedule) {
         lastFixed = block.getBeginNode();
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Fri Mar 13 12:27:07 2015 +0100
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011, 2013, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2011, 2015, 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
@@ -22,26 +22,19 @@
  */
 package com.oracle.graal.phases.schedule;
 
-import static com.oracle.graal.api.meta.LocationIdentity.*;
 import static com.oracle.graal.compiler.common.GraalOptions.*;
 import static com.oracle.graal.compiler.common.cfg.AbstractControlFlowGraph.*;
 
 import java.util.*;
 
 import com.oracle.graal.api.meta.*;
-import com.oracle.graal.compiler.common.*;
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.cfg.*;
 import com.oracle.graal.nodes.extended.*;
-import com.oracle.graal.nodes.spi.*;
-import com.oracle.graal.nodes.virtual.*;
 import com.oracle.graal.phases.*;
-import com.oracle.graal.phases.graph.*;
-import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
-import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo;
 
 public final class SchedulePhase extends Phase {
 
@@ -75,234 +68,14 @@
         LATEST_OUT_OF_LOOPS
     }
 
-    private class LocationSet {
-        private LocationIdentity firstLocation;
-        private List<LocationIdentity> list;
-
-        public LocationSet() {
-            list = null;
-        }
-
-        public LocationSet(LocationSet other) {
-            this.firstLocation = other.firstLocation;
-            if (other.list != null && other.list.size() > 0) {
-                list = new ArrayList<>(other.list);
-            }
-        }
-
-        private void initList() {
-            if (list == null) {
-                list = new ArrayList<>(4);
-            }
-        }
-
-        public void add(LocationIdentity location) {
-            if (LocationIdentity.ANY_LOCATION.equals(location)) {
-                firstLocation = location;
-                list = null;
-            } else {
-                if (firstLocation == null) {
-                    firstLocation = location;
-                } else if (LocationIdentity.ANY_LOCATION.equals(firstLocation)) {
-                    return;
-                } else if (location.equals(firstLocation)) {
-                    return;
-                } else {
-                    initList();
-                    for (int i = 0; i < list.size(); ++i) {
-                        LocationIdentity value = list.get(i);
-                        if (location.equals(value)) {
-                            return;
-                        }
-                    }
-                    list.add(location);
-                }
-            }
-        }
-
-        public void addAll(LocationSet other) {
-            if (other.firstLocation != null) {
-                add(other.firstLocation);
-            }
-            List<LocationIdentity> otherList = other.list;
-            if (otherList != null) {
-                for (LocationIdentity l : otherList) {
-                    add(l);
-                }
-            }
-        }
-
-        public boolean contains(LocationIdentity locationIdentity) {
-            assert locationIdentity != null;
-            assert !locationIdentity.equals(LocationIdentity.ANY_LOCATION);
-            assert !locationIdentity.equals(LocationIdentity.FINAL_LOCATION);
-            if (LocationIdentity.ANY_LOCATION.equals(firstLocation)) {
-                return true;
-            }
-            if (locationIdentity.equals(firstLocation)) {
-                return true;
-            }
-            if (list != null) {
-                for (int i = 0; i < list.size(); ++i) {
-                    LocationIdentity value = list.get(i);
-                    if (locationIdentity.equals(value)) {
-                        return true;
-                    }
-                }
-            }
-            return false;
-        }
-
-        public List<LocationIdentity> getCopyAsList() {
-            ArrayList<LocationIdentity> result = new ArrayList<>();
-            if (firstLocation != null) {
-                result.add(firstLocation);
-            }
-            if (list != null) {
-                result.addAll(list);
-            }
-            return result;
-        }
-    }
-
-    private class NewMemoryScheduleClosure extends BlockIteratorClosure<LocationSet> {
-        private Node excludeNode;
-        private Block upperBoundBlock;
-
-        public NewMemoryScheduleClosure(Node excludeNode, Block upperBoundBlock) {
-            this.excludeNode = excludeNode;
-            this.upperBoundBlock = upperBoundBlock;
-        }
-
-        public NewMemoryScheduleClosure() {
-            this(null, null);
-        }
-
-        @Override
-        protected LocationSet getInitialState() {
-            return cloneState(blockToKillSet.get(getCFG().getStartBlock()));
-        }
-
-        @Override
-        protected LocationSet processBlock(Block block, LocationSet currentState) {
-            assert block != null;
-            currentState.addAll(computeKillSet(block, block == upperBoundBlock ? excludeNode : null));
-            return currentState;
-        }
-
-        @Override
-        protected LocationSet merge(Block merge, List<LocationSet> states) {
-            assert merge.getBeginNode() instanceof AbstractMergeNode;
-
-            LocationSet initKillSet = new LocationSet();
-            for (LocationSet state : states) {
-                initKillSet.addAll(state);
-            }
-
-            return initKillSet;
-        }
-
-        @Override
-        protected LocationSet cloneState(LocationSet state) {
-            return new LocationSet(state);
-        }
-
-        @Override
-        protected List<LocationSet> processLoop(Loop<Block> loop, LocationSet state) {
-            LoopInfo<LocationSet> info = ReentrantBlockIterator.processLoop(this, loop, cloneState(state));
-
-            assert loop.getHeader().getBeginNode() instanceof LoopBeginNode;
-            LocationSet headerState = merge(loop.getHeader(), info.endStates);
-
-            // second iteration, for propagating information to loop exits
-            info = ReentrantBlockIterator.processLoop(this, loop, cloneState(headerState));
-
-            return info.exitStates;
-        }
-    }
-
-    /**
-     * gather all kill locations by iterating trough the nodes assigned to a block.
-     *
-     * assumptions: {@link MemoryCheckpoint MemoryCheckPoints} are {@link FixedNode FixedNodes}.
-     *
-     * @param block block to analyze
-     * @param excludeNode if null, compute normal set of kill locations. if != null, don't add kills
-     *            until we reach excludeNode.
-     * @return all killed locations
-     */
-    private LocationSet computeKillSet(Block block, Node excludeNode) {
-        // cache is only valid if we don't potentially exclude kills from the set
-        if (excludeNode == null) {
-            LocationSet cachedSet = blockToKillSet.get(block);
-            if (cachedSet != null) {
-                return cachedSet;
-            }
-        }
-
-        // add locations to excludedLocations until we reach the excluded node
-        boolean foundExcludeNode = excludeNode == null;
-
-        LocationSet set = new LocationSet();
-        LocationSet excludedLocations = new LocationSet();
-        if (block.getBeginNode() instanceof AbstractMergeNode) {
-            AbstractMergeNode mergeNode = (AbstractMergeNode) block.getBeginNode();
-            for (MemoryPhiNode phi : mergeNode.usages().filter(MemoryPhiNode.class)) {
-                if (foundExcludeNode) {
-                    set.add(phi.getLocationIdentity());
-                } else {
-                    excludedLocations.add(phi.getLocationIdentity());
-                    foundExcludeNode = phi == excludeNode;
-                }
-            }
-        }
-
-        AbstractBeginNode startNode = cfg.getStartBlock().getBeginNode();
-        assert startNode instanceof StartNode;
-
-        LocationSet accm = foundExcludeNode ? set : excludedLocations;
-        for (Node node : block.getNodes()) {
-            if (!foundExcludeNode && node == excludeNode) {
-                foundExcludeNode = true;
-            }
-            if (node != startNode) {
-                if (node instanceof MemoryCheckpoint.Single) {
-                    LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
-                    accm.add(identity);
-                } else if (node instanceof MemoryCheckpoint.Multi) {
-                    for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
-                        accm.add(identity);
-                    }
-                }
-                assert MemoryCheckpoint.TypeAssertion.correctType(node);
-            }
-
-            if (foundExcludeNode) {
-                accm = set;
-            }
-        }
-
-        // merge it for the cache entry
-        excludedLocations.addAll(set);
-        blockToKillSet.put(block, excludedLocations);
-
-        return set;
-    }
-
-    private LocationSet computeKillSet(Block block) {
-        return computeKillSet(block, null);
-    }
-
     private ControlFlowGraph cfg;
-    private NodeMap<Block> earliestCache;
 
     /**
      * Map from blocks to the nodes in each block.
      */
-    private BlockMap<List<ValueNode>> blockToNodesMap;
+    private BlockMap<List<Node>> blockToNodesMap;
     private BlockMap<LocationSet> blockToKillSet;
     private final SchedulingStrategy selectedStrategy;
-    private boolean scheduleConstants;
     private NodeMap<Block> nodeToBlockMap;
 
     public SchedulePhase() {
@@ -313,41 +86,366 @@
         this.selectedStrategy = strategy;
     }
 
-    public void setScheduleConstants(boolean value) {
-        scheduleConstants = value;
-    }
-
     @Override
     protected void run(StructuredGraph graph) {
         // assert GraphOrder.assertNonCyclicGraph(graph);
         cfg = ControlFlowGraph.compute(graph, true, true, true, false);
-        earliestCache = graph.createNodeMap();
-        blockToNodesMap = new BlockMap<>(cfg);
+
+        if (selectedStrategy == SchedulingStrategy.EARLIEST) {
+            this.nodeToBlockMap = graph.createNodeMap();
+            this.blockToNodesMap = new BlockMap<>(cfg);
+            NodeBitMap visited = graph.createNodeBitMap();
+            scheduleEarliestIterative(cfg, blockToNodesMap, nodeToBlockMap, visited, graph);
+            return;
+        } else {
+            boolean isOutOfLoops = selectedStrategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS;
+            if (selectedStrategy == SchedulingStrategy.LATEST || isOutOfLoops) {
+                NodeMap<Block> currentNodeMap = graph.createNodeMap();
+                BlockMap<List<Node>> earliestBlockToNodesMap = new BlockMap<>(cfg);
+                NodeBitMap visited = graph.createNodeBitMap();
+                scheduleEarliestIterative(cfg, earliestBlockToNodesMap, currentNodeMap, visited, graph);
+                BlockMap<List<Node>> latestBlockToNodesMap = new BlockMap<>(cfg);
+
+                for (Block b : cfg.getBlocks()) {
+                    latestBlockToNodesMap.put(b, new ArrayList<Node>());
+                }
+
+                BlockMap<ArrayList<FloatingReadNode>> watchListMap = null;
+                for (Block b : cfg.postOrder()) {
+                    List<Node> blockToNodes = earliestBlockToNodesMap.get(b);
+                    LocationSet killed = null;
+                    int previousIndex = blockToNodes.size();
+                    for (int i = blockToNodes.size() - 1; i >= 0; --i) {
+                        Node currentNode = blockToNodes.get(i);
+                        assert currentNodeMap.get(currentNode) == b;
+                        assert !(currentNode instanceof PhiNode) && !(currentNode instanceof ProxyNode);
+                        assert visited.isMarked(currentNode);
+                        if (currentNode instanceof FixedNode) {
+                            // For these nodes, the earliest is at the same time the latest block.
+                        } else {
+                            Block currentBlock = b;
+                            assert currentBlock != null;
+                            Block latestBlock = calcLatestBlock(b, isOutOfLoops, currentNode, currentNodeMap);
+                            assert AbstractControlFlowGraph.dominates(currentBlock, latestBlock) || currentNode instanceof VirtualState : currentNode + " " + currentBlock + " " + latestBlock;
+                            if (latestBlock != currentBlock) {
+                                if (currentNode instanceof FloatingReadNode) {
+
+                                    FloatingReadNode floatingReadNode = (FloatingReadNode) currentNode;
+                                    LocationIdentity location = floatingReadNode.getLocationIdentity();
+                                    if (location.isMutable()) {
+                                        if (currentBlock.canKill(location)) {
+                                            if (killed == null) {
+                                                killed = new LocationSet();
+                                            }
+                                            fillKillSet(killed, blockToNodes.subList(i + 1, previousIndex));
+                                            previousIndex = i;
+                                            if (killed.contains(location)) {
+                                                latestBlock = currentBlock;
+                                            }
+                                        }
 
-        if (selectedStrategy != SchedulingStrategy.EARLIEST && graph.isAfterFloatingReadPhase()) {
-            blockToKillSet = new BlockMap<>(cfg);
+                                        if (latestBlock != currentBlock) {
+                                            // We are not constraint within currentBlock. Check if
+                                            // we are contraint while walking down the dominator
+                                            // line.
+                                            Block newLatestBlock = adjustLatestForRead(currentBlock, latestBlock, location);
+                                            assert dominates(newLatestBlock, latestBlock);
+                                            assert dominates(currentBlock, newLatestBlock);
+                                            latestBlock = newLatestBlock;
+
+                                            if (newLatestBlock != currentBlock && latestBlock.canKill(location)) {
+                                                if (watchListMap == null) {
+                                                    watchListMap = new BlockMap<>(cfg);
+                                                }
+                                                if (watchListMap.get(latestBlock) == null) {
+                                                    watchListMap.put(latestBlock, new ArrayList<>());
+                                                }
+                                                watchListMap.get(latestBlock).add(floatingReadNode);
+                                            }
+                                        }
+                                    }
+                                }
+                                currentNodeMap.set(currentNode, latestBlock);
+                                currentBlock = latestBlock;
+                            }
+                            latestBlockToNodesMap.get(currentBlock).add(currentNode);
+                        }
+                    }
+                }
+
+                sortNodesLatestWithinBlock(cfg, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited);
+
+                this.blockToNodesMap = latestBlockToNodesMap;
+                this.nodeToBlockMap = currentNodeMap;
+
+                assert verifySchedule(cfg, latestBlockToNodesMap, currentNodeMap);
+                cfg.setNodeToBlock(currentNodeMap);
+            }
+        }
+    }
+
+    private static boolean verifySchedule(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodesMap, NodeMap<Block> nodeMap) {
+        for (Block b : cfg.getBlocks()) {
+            List<Node> nodes = blockToNodesMap.get(b);
+            for (Node n : nodes) {
+                assert n.isAlive();
+                assert nodeMap.get(n) == b;
+            }
+        }
+        return true;
+    }
+
+    private static Block adjustLatestForRead(Block earliestBlock, Block latestBlock, LocationIdentity location) {
+        assert strictlyDominates(earliestBlock, latestBlock);
+        Block current = latestBlock.getDominator();
+
+        // Collect dominator chain that needs checking.
+        List<Block> dominatorChain = new ArrayList<>();
+        dominatorChain.add(latestBlock);
+        while (current != earliestBlock) {
+            // Current is an intermediate dominator between earliestBlock and latestBlock.
+            assert strictlyDominates(earliestBlock, current) && strictlyDominates(current, latestBlock);
+            if (current.canKill(location)) {
+                dominatorChain.clear();
+            }
+            dominatorChain.add(current);
+            current = current.getDominator();
         }
 
-        if (selectedStrategy == SchedulingStrategy.EARLIEST) {
-            scheduleEarliestIterative(blockToNodesMap, graph);
+        // The first element of dominatorChain now contains the latest possible block.
+        assert dominatorChain.size() >= 1;
+        assert dominatorChain.get(dominatorChain.size() - 1).getDominator() == earliestBlock;
+
+        Block lastBlock = earliestBlock;
+        for (int i = dominatorChain.size() - 1; i >= 0; --i) {
+            Block currentBlock = dominatorChain.get(i);
+            if (lastBlock.getLoop() != currentBlock.getLoop()) {
+                // We are crossing a loop boundary. Both loops must not kill the location for the
+                // crossing to be safe.
+                if (lastBlock.getLoop() != null && ((HIRLoop) lastBlock.getLoop()).canKill(location)) {
+                    break;
+                }
+                if (currentBlock.getLoop() != null && ((HIRLoop) currentBlock.getLoop()).canKill(location)) {
+                    break;
+                }
+            }
+
+            if (currentBlock.canKillBetweenThisAndDominator(location)) {
+                break;
+            }
+            lastBlock = currentBlock;
+        }
+
+        return lastBlock;
+    }
+
+    private static void fillKillSet(LocationSet killed, List<Node> subList) {
+        if (!killed.isKillAll()) {
+            for (Node n : subList) {
+                // Check if this node kills a node in the watch list.
+                if (n instanceof MemoryCheckpoint.Single) {
+                    LocationIdentity identity = ((MemoryCheckpoint.Single) n).getLocationIdentity();
+                    killed.add(identity);
+                    if (killed.isKillAll()) {
+                        return;
+                    }
+                } else if (n instanceof MemoryCheckpoint.Multi) {
+                    for (LocationIdentity identity : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
+                        killed.add(identity);
+                        if (killed.isKillAll()) {
+                            return;
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    private static void sortNodesLatestWithinBlock(ControlFlowGraph cfg, BlockMap<List<Node>> earliestBlockToNodesMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeMap<Block> currentNodeMap,
+                    BlockMap<ArrayList<FloatingReadNode>> watchListMap, NodeBitMap visited) {
+        for (Block b : cfg.getBlocks()) {
+            sortNodesLatestWithinBlock(b, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited);
+        }
+    }
+
+    private static void sortNodesLatestWithinBlock(Block b, BlockMap<List<Node>> earliestBlockToNodesMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeMap<Block> nodeMap,
+                    BlockMap<ArrayList<FloatingReadNode>> watchListMap, NodeBitMap unprocessed) {
+        ArrayList<Node> result = new ArrayList<>();
+        ArrayList<FloatingReadNode> watchList = null;
+        if (watchListMap != null) {
+            watchList = watchListMap.get(b);
+            assert watchList == null || !b.getKillLocations().isKillNone();
+        }
+        AbstractBeginNode beginNode = b.getBeginNode();
+        if (beginNode instanceof LoopExitNode) {
+            LoopExitNode loopExitNode = (LoopExitNode) beginNode;
+            for (ProxyNode proxy : loopExitNode.proxies()) {
+                unprocessed.clear(proxy);
+                ValueNode value = proxy.value();
+                if (nodeMap.get(value) == b) {
+                    sortIntoList(value, b, result, nodeMap, unprocessed, null);
+                }
+            }
+        }
+        FixedNode endNode = b.getEndNode();
+        for (Node n : earliestBlockToNodesMap.get(b)) {
+            if (n != endNode) {
+                if (n instanceof FixedNode) {
+                    assert nodeMap.get(n) == b;
+                    checkWatchList(b, nodeMap, unprocessed, result, watchList, n);
+                    sortIntoList(n, b, result, nodeMap, unprocessed, null);
+                } else if (nodeMap.get(n) == b && n instanceof FloatingReadNode) {
+                    FloatingReadNode floatingReadNode = (FloatingReadNode) n;
+                    LocationIdentity location = floatingReadNode.getLocationIdentity();
+                    if (b.canKill(location)) {
+                        // This read can be killed in this block, add to watch list.
+                        if (watchList == null) {
+                            watchList = new ArrayList<>();
+                        }
+                        watchList.add(floatingReadNode);
+                    }
+                }
+            }
+        }
+
+        for (Node n : latestBlockToNodesMap.get(b)) {
+            assert nodeMap.get(n) == b;
+            assert !(n instanceof FixedNode);
+            if (unprocessed.isMarked(n)) {
+                sortIntoList(n, b, result, nodeMap, unprocessed, endNode);
+            }
+        }
+
+        if (unprocessed.isMarked(endNode)) {
+            sortIntoList(endNode, b, result, nodeMap, unprocessed, null);
+        }
+
+        latestBlockToNodesMap.put(b, result);
+    }
+
+    private static void checkWatchList(Block b, NodeMap<Block> nodeMap, NodeBitMap unprocessed, ArrayList<Node> result, ArrayList<FloatingReadNode> watchList, Node n) {
+        if (watchList != null && !watchList.isEmpty()) {
+            // Check if this node kills a node in the watch list.
+            if (n instanceof MemoryCheckpoint.Single) {
+                LocationIdentity identity = ((MemoryCheckpoint.Single) n).getLocationIdentity();
+                checkWatchList(watchList, identity, b, result, nodeMap, unprocessed);
+            } else if (n instanceof MemoryCheckpoint.Multi) {
+                for (LocationIdentity identity : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
+                    checkWatchList(watchList, identity, b, result, nodeMap, unprocessed);
+                }
+            }
+        }
+    }
+
+    private static void checkWatchList(ArrayList<FloatingReadNode> watchList, LocationIdentity identity, Block b, ArrayList<Node> result, NodeMap<Block> nodeMap, NodeBitMap unprocessed) {
+        assert identity.isMutable();
+        if (LocationIdentity.ANY_LOCATION.equals(identity)) {
+            for (FloatingReadNode r : watchList) {
+                if (unprocessed.isMarked(r)) {
+                    sortIntoList(r, b, result, nodeMap, unprocessed, null);
+                }
+            }
+            watchList.clear();
+        } else {
+            int index = 0;
+            while (index < watchList.size()) {
+                FloatingReadNode r = watchList.get(index);
+                LocationIdentity locationIdentity = r.getLocationIdentity();
+                assert !LocationIdentity.FINAL_LOCATION.equals(locationIdentity);
+                if (unprocessed.isMarked(r)) {
+                    if (LocationIdentity.ANY_LOCATION.equals(identity) || LocationIdentity.ANY_LOCATION.equals(locationIdentity) || identity.equals(locationIdentity)) {
+                        sortIntoList(r, b, result, nodeMap, unprocessed, null);
+                    } else {
+                        ++index;
+                        continue;
+                    }
+                }
+                int lastIndex = watchList.size() - 1;
+                watchList.set(index, watchList.get(lastIndex));
+                watchList.remove(lastIndex);
+            }
+        }
+    }
+
+    private static void sortIntoList(Node n, Block b, ArrayList<Node> result, NodeMap<Block> nodeMap, NodeBitMap unprocessed, Node excludeNode) {
+        assert unprocessed.isMarked(n) : n;
+        unprocessed.clear(n);
+
+        assert nodeMap.get(n) == b;
+
+        if (n instanceof PhiNode) {
             return;
         }
 
-        assignBlockToNodes(graph, selectedStrategy);
-        printSchedule("after assign nodes to blocks");
+        for (Node input : n.inputs()) {
+            if (nodeMap.get(input) == b && unprocessed.isMarked(input) && input != excludeNode) {
+                sortIntoList(input, b, result, nodeMap, unprocessed, excludeNode);
+            }
+        }
 
-        sortNodesWithinBlocks(graph, selectedStrategy);
-        printSchedule("after sorting nodes within blocks");
+        if (n instanceof ProxyNode) {
+            // Skip proxy nodes.
+        } else {
+            result.add(n);
+        }
+
     }
 
-    private void scheduleEarliestIterative(BlockMap<List<ValueNode>> blockToNodes, StructuredGraph graph) {
-        NodeMap<Block> nodeToBlock = graph.createNodeMap();
-        NodeBitMap visited = graph.createNodeBitMap();
+    private static Block calcLatestBlock(Block earliestBlock, boolean scheduleOutOfLoops, Node currentNode, NodeMap<Block> currentNodeMap) {
+        Block block = null;
+        assert currentNode.hasUsages();
+        for (Node usage : currentNode.usages()) {
+            block = calcBlockForUsage(currentNode, usage, block, currentNodeMap);
+            if (scheduleOutOfLoops) {
+                while (block.getLoopDepth() > earliestBlock.getLoopDepth()) {
+                    block = block.getDominator();
+                }
+            }
+            if (block == earliestBlock) {
+                // No need to search further. The earliest block *must* be a valid schedule block.
+                break;
+            }
+        }
+        assert block != null : currentNode;
+        return block;
+    }
+
+    private static Block calcBlockForUsage(Node node, Node usage, Block startCurrentBlock, NodeMap<Block> currentNodeMap) {
+        assert !(node instanceof PhiNode);
+        Block currentBlock = startCurrentBlock;
+        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.
+            PhiNode phi = (PhiNode) usage;
+            AbstractMergeNode merge = phi.merge();
+            Block mergeBlock = currentNodeMap.get(merge);
+            for (int i = 0; i < phi.valueCount(); ++i) {
+                if (phi.valueAt(i) == node) {
+                    currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, mergeBlock.getPredecessors().get(i));
+                }
+            }
+        } else if (usage instanceof AbstractBeginNode) {
+            AbstractBeginNode abstractBeginNode = (AbstractBeginNode) usage;
+            if (abstractBeginNode instanceof StartNode) {
+                currentBlock = currentNodeMap.get(abstractBeginNode);
+            } else {
+                currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, currentNodeMap.get(abstractBeginNode).getDominator());
+            }
+        } else {
+            // All other types of usages: Put the input into the same block as the usage.
+            currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, currentNodeMap.get(usage));
+        }
+        return currentBlock;
+    }
+
+    private static void scheduleEarliestIterative(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, StructuredGraph graph) {
+
+        BlockMap<Boolean> floatingReads = new BlockMap<>(cfg);
 
         // Add begin nodes as the first entry and set the block for phi nodes.
         for (Block b : cfg.getBlocks()) {
             AbstractBeginNode beginNode = b.getBeginNode();
-            ArrayList<ValueNode> nodes = new ArrayList<>();
+            ArrayList<Node> nodes = new ArrayList<>();
             nodeToBlock.set(beginNode, b);
             nodes.add(beginNode);
             blockToNodes.put(b, nodes);
@@ -374,10 +472,9 @@
             nodeToBlock.set(endNode, b);
         }
 
-        processStack(blockToNodes, nodeToBlock, visited, stack);
+        processStack(cfg, blockToNodes, nodeToBlock, visited, floatingReads, stack);
 
         // Visit back input edges of loop phis.
-
         boolean changed;
         boolean unmarkedPhi;
         do {
@@ -391,7 +488,7 @@
                             if (node != null && !visited.isMarked(node)) {
                                 changed = true;
                                 stack.push(node);
-                                processStack(blockToNodes, nodeToBlock, visited, stack);
+                                processStack(cfg, blockToNodes, nodeToBlock, visited, floatingReads, stack);
                             }
                         }
                     } else {
@@ -424,16 +521,80 @@
             }
         }
 
-        this.blockToNodesMap = blockToNodes;
-        this.nodeToBlockMap = nodeToBlock;
+        for (Block b : cfg.getBlocks()) {
+            if (floatingReads.get(b) == Boolean.TRUE) {
+                resortEarliestWithinBlock(b, blockToNodes, nodeToBlock, visited);
+            }
+        }
     }
 
-    private static void addNode(BlockMap<List<ValueNode>> blockToNodes, Block b, ValueNode endNode) {
+    private static void resortEarliestWithinBlock(Block b, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap unprocessed) {
+        ArrayList<FloatingReadNode> watchList = new ArrayList<>();
+        List<Node> oldList = blockToNodes.get(b);
+        AbstractBeginNode beginNode = b.getBeginNode();
+        for (Node n : oldList) {
+            if (n instanceof FloatingReadNode) {
+                FloatingReadNode floatingReadNode = (FloatingReadNode) n;
+                LocationIdentity locationIdentity = floatingReadNode.getLocationIdentity();
+                if (locationIdentity.isMutable()) {
+                    ValueNode lastAccessLocation = floatingReadNode.getLastLocationAccess().asNode();
+                    if (nodeToBlock.get(lastAccessLocation) == b && lastAccessLocation != beginNode) {
+                        // This node's last access location is within this block. Add to watch list
+                        // when processing the last access location.
+                    } else {
+                        watchList.add(floatingReadNode);
+                    }
+                }
+            }
+        }
+
+        ArrayList<Node> newList = new ArrayList<>();
+        assert oldList.get(0) == beginNode;
+        unprocessed.clear(beginNode);
+        newList.add(beginNode);
+        for (int i = 1; i < oldList.size(); ++i) {
+            Node n = oldList.get(i);
+            if (unprocessed.isMarked(n)) {
+                if (n instanceof MemoryCheckpoint) {
+                    assert n instanceof FixedNode;
+                    if (watchList.size() > 0) {
+                        // Check whether we need to commit reads from the watch list.
+                        checkWatchList(b, nodeToBlock, unprocessed, newList, watchList, n);
+                    }
+
+                    // Add potential dependent reads to the watch list.
+                    for (Node usage : n.usages()) {
+                        if (usage instanceof FloatingReadNode) {
+                            FloatingReadNode floatingReadNode = (FloatingReadNode) usage;
+                            if (nodeToBlock.get(floatingReadNode) == b && floatingReadNode.getLastLocationAccess() == n) {
+                                watchList.add(floatingReadNode);
+                            }
+                        }
+                    }
+                }
+                assert unprocessed.isMarked(n);
+                unprocessed.clear(n);
+                newList.add(n);
+            } else {
+                // This node was pulled up.
+                assert !(n instanceof FixedNode);
+            }
+        }
+
+        for (Node n : newList) {
+            unprocessed.mark(n);
+        }
+
+        assert newList.size() == oldList.size();
+        blockToNodes.put(b, newList);
+    }
+
+    private static void addNode(BlockMap<List<Node>> blockToNodes, Block b, Node endNode) {
         assert !blockToNodes.get(b).contains(endNode) : endNode;
         blockToNodes.get(b).add(endNode);
     }
 
-    private void processStack(BlockMap<List<ValueNode>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, Stack<Node> stack) {
+    private static void processStack(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, BlockMap<Boolean> floatingReads, Stack<Node> stack) {
         Block startBlock = cfg.getStartBlock();
         while (!stack.isEmpty()) {
             Node current = stack.peek();
@@ -494,32 +655,25 @@
                         curBlock = earliest;
                     }
                     assert curBlock != null;
-                    if (current instanceof ValueNode) {
-                        addNode(blockToNodes, curBlock, (ValueNode) current);
+                    addNode(blockToNodes, curBlock, current);
+                    nodeToBlock.set(current, curBlock);
+                    if (current instanceof FloatingReadNode) {
+                        FloatingReadNode floatingReadNode = (FloatingReadNode) current;
+                        if (curBlock.canKill(floatingReadNode.getLocationIdentity())) {
+                            floatingReads.put(curBlock, Boolean.TRUE);
+                        }
                     }
-                    nodeToBlock.set(current, curBlock);
                 }
             }
         }
     }
 
-    private Block blockForMemoryNode(MemoryNode memory) {
-        MemoryNode current = memory;
-        while (current instanceof MemoryProxy) {
-            current = ((MemoryProxy) current).getOriginalMemoryNode();
-        }
-        Block b = cfg.getNodeToBlock().get(current.asNode());
-        assert b != null : "all lastAccess locations should have a block assignment from CFG";
-        return b;
+    @Override
+    public String toString() {
+        return printScheduleHelper("Schedule");
     }
 
-    private void printSchedule(String desc) {
-        if (Debug.isLogEnabled()) {
-            printScheduleHelper(desc);
-        }
-    }
-
-    private void printScheduleHelper(String desc) {
+    private String printScheduleHelper(String desc) {
         Formatter buf = new Formatter();
         buf.format("=== %s / %s / %s ===%n", getCFG().getStartBlock().getBeginNode().graph(), selectedStrategy, desc);
         for (Block b : getCFG().getBlocks()) {
@@ -548,7 +702,7 @@
             }
         }
         buf.format("%n");
-        Debug.log("%s", buf);
+        return buf.toString();
     }
 
     private static void printNode(Node n) {
@@ -579,7 +733,7 @@
     /**
      * Gets the map from each block to the nodes in the block.
      */
-    public BlockMap<List<ValueNode>> getBlockToNodesMap() {
+    public BlockMap<List<Node>> getBlockToNodesMap() {
         return blockToNodesMap;
     }
 
@@ -590,660 +744,7 @@
     /**
      * Gets the nodes in a given block.
      */
-    public List<ValueNode> nodesFor(Block block) {
+    public List<Node> nodesFor(Block block) {
         return blockToNodesMap.get(block);
     }
-
-    private void assignBlockToNodes(StructuredGraph graph, SchedulingStrategy strategy) {
-        for (Block block : cfg.getBlocks()) {
-            List<ValueNode> nodes = new ArrayList<>();
-            if (blockToNodesMap.get(block) != null) {
-                throw new SchedulingError();
-            }
-            blockToNodesMap.put(block, nodes);
-            for (FixedNode node : block.getNodes()) {
-                nodes.add(node);
-            }
-        }
-
-        for (Node n : graph.getNodes()) {
-            if (n instanceof ValueNode) {
-                assignBlockToNode((ValueNode) n, strategy);
-            }
-        }
-    }
-
-    /**
-     * Assigns a block to the given node. This method expects that PhiNodes and FixedNodes are
-     * already assigned to a block.
-     */
-    private void assignBlockToNode(ValueNode node, SchedulingStrategy strategy) {
-        assert !node.isDeleted();
-
-        if (cfg.getNodeToBlock().containsKey(node)) {
-            return;
-        }
-        if (!scheduleConstants && node instanceof ConstantNode) {
-            return;
-        }
-        if (node instanceof VirtualObjectNode) {
-            return;
-        }
-        // PhiNodes, ProxyNodes and FixedNodes should already have been placed in blocks by
-        // ControlFlowGraph.identifyBlocks
-        if (node instanceof PhiNode || node instanceof ProxyNode || node instanceof FixedNode) {
-            throw new SchedulingError("%s should already have been placed in a block", node);
-        }
-
-        Block earliestBlock = earliestBlock(node);
-        Block block = null;
-        Block latest = null;
-        switch (strategy) {
-            case EARLIEST:
-                block = earliestBlock;
-                break;
-            case LATEST:
-            case LATEST_OUT_OF_LOOPS:
-                boolean scheduleRead = node instanceof FloatingReadNode && !((FloatingReadNode) node).location().getLocationIdentity().isImmutable();
-                if (scheduleRead) {
-                    FloatingReadNode read = (FloatingReadNode) node;
-                    block = optimalBlock(read, strategy);
-                    Debug.log("schedule for %s: %s", read, block);
-                    assert dominates(earliestBlock, block) : String.format("%s (%s) cannot be scheduled before earliest schedule (%s). location: %s", read, block, earliestBlock,
-                                    read.getLocationIdentity());
-                } else {
-                    block = latestBlock(node, strategy, earliestBlock);
-                }
-                if (block == null) {
-                    // handle nodes without usages
-                    block = earliestBlock;
-                } else if (strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS && !(node instanceof VirtualObjectNode)) {
-                    // schedule at the latest position possible in the outermost loop possible
-                    latest = block;
-                    block = scheduleOutOfLoops(node, block, earliestBlock);
-                }
-
-                assert assertReadSchedule(node, earliestBlock, block, latest, scheduleRead);
-                break;
-            default:
-                throw new GraalInternalError("unknown scheduling strategy");
-        }
-        if (!dominates(earliestBlock, block)) {
-            throw new SchedulingError("%s: Graph cannot be scheduled : inconsistent for %s, %d usages, (%s needs to dominate %s)", node.graph(), node, node.getUsageCount(), earliestBlock, block);
-        }
-        cfg.getNodeToBlock().set(node, block);
-        blockToNodesMap.get(block).add(node);
-    }
-
-    private boolean assertReadSchedule(ValueNode node, Block earliestBlock, Block block, Block latest, boolean scheduleRead) {
-        if (scheduleRead) {
-            FloatingReadNode read = (FloatingReadNode) node;
-            MemoryNode lastLocationAccess = read.getLastLocationAccess();
-            Block upperBound = blockForMemoryNode(lastLocationAccess);
-            assert dominates(upperBound, block) : String.format("out of loop movement voilated memory semantics for %s (location %s). moved to %s but upper bound is %s (earliest: %s, latest: %s)",
-                            read, read.getLocationIdentity(), block, upperBound, earliestBlock, latest);
-        }
-        return true;
-    }
-
-    /**
-     * this method tries to find the "optimal" schedule for a read, by pushing it down towards its
-     * latest schedule starting by the earliest schedule. By doing this, it takes care of memory
-     * dependencies using kill sets.
-     *
-     * In terms of domination relation, it looks like this:
-     *
-     * <pre>
-     *    U      upperbound block, defined by last access location of the floating read
-     *    &and;
-     *    E      earliest block
-     *    &and;
-     *    O      optimal block, first block that contains a kill of the read's location
-     *    &and;
-     *    L      latest block
-     * </pre>
-     *
-     * i.e. <code>upperbound `dom` earliest `dom` optimal `dom` latest</code>.
-     *
-     */
-    private Block optimalBlock(FloatingReadNode n, SchedulingStrategy strategy) {
-        LocationIdentity locid = n.location().getLocationIdentity();
-        assert !locid.isImmutable();
-
-        Block upperBoundBlock = blockForMemoryNode(n.getLastLocationAccess());
-        Block earliestBlock = earliestBlock(n);
-        assert dominates(upperBoundBlock, earliestBlock) : "upper bound (" + upperBoundBlock + ") should dominate earliest (" + earliestBlock + ")";
-
-        Block latestBlock = latestBlock(n, strategy, earliestBlock);
-        assert latestBlock != null && dominates(earliestBlock, latestBlock) : "earliest (" + earliestBlock + ") should dominate latest block (" + latestBlock + ")";
-
-        Debug.log("processing %s (accessing %s): latest %s, earliest %s, upper bound %s (%s)", n, locid, latestBlock, earliestBlock, upperBoundBlock, n.getLastLocationAccess());
-        if (earliestBlock == latestBlock) {
-            // read is fixed to this block, nothing to schedule
-            return latestBlock;
-        }
-
-        Deque<Block> path = computePathInDominatorTree(earliestBlock, latestBlock);
-        Debug.log("|path| is %d: %s", path.size(), path);
-
-        // follow path, start at earliest schedule
-        while (path.size() > 0) {
-            Block currentBlock = path.pop();
-            Block dominatedBlock = path.size() == 0 ? null : path.peek();
-            if (dominatedBlock != null && !currentBlock.getSuccessors().contains(dominatedBlock)) {
-                // the dominated block is not a successor -> we have a split
-                assert dominatedBlock.getBeginNode() instanceof AbstractMergeNode;
-
-                NewMemoryScheduleClosure closure = null;
-                if (currentBlock == upperBoundBlock) {
-                    assert earliestBlock == upperBoundBlock;
-                    // don't treat lastLocationAccess node as a kill for this read.
-                    closure = new NewMemoryScheduleClosure(ValueNodeUtil.asNode(n.getLastLocationAccess()), upperBoundBlock);
-                } else {
-                    closure = new NewMemoryScheduleClosure();
-                }
-                Map<FixedNode, LocationSet> states;
-                states = ReentrantBlockIterator.apply(closure, currentBlock, new LocationSet(), block -> block == dominatedBlock);
-
-                LocationSet mergeState = states.get(dominatedBlock.getBeginNode());
-                if (mergeState.contains(locid)) {
-                    // location got killed somewhere in the branches,
-                    // thus we've to move the read above it
-                    return currentBlock;
-                }
-            } else {
-                if (currentBlock == upperBoundBlock) {
-                    assert earliestBlock == upperBoundBlock;
-                    LocationSet ks = computeKillSet(upperBoundBlock, ValueNodeUtil.asNode(n.getLastLocationAccess()));
-                    if (ks.contains(locid)) {
-                        return upperBoundBlock;
-                    }
-                } else if (dominatedBlock == null || computeKillSet(currentBlock).contains(locid)) {
-                    return currentBlock;
-                }
-            }
-        }
-        throw new SchedulingError("should have found a block for " + n);
-    }
-
-    /**
-     * compute path in dominator tree from earliest schedule to latest schedule.
-     *
-     * @return the order of the stack is such as the first element is the earliest schedule.
-     */
-    private static Deque<Block> computePathInDominatorTree(Block earliestBlock, Block latestBlock) {
-        Deque<Block> path = new LinkedList<>();
-        Block currentBlock = latestBlock;
-        while (currentBlock != null && dominates(earliestBlock, currentBlock)) {
-            path.push(currentBlock);
-            currentBlock = currentBlock.getDominator();
-        }
-        assert path.peek() == earliestBlock;
-        return path;
-    }
-
-    /**
-     * Calculates the last block that the given node could be scheduled in, i.e., the common
-     * dominator of all usages. To do so all usages are also assigned to blocks.
-     *
-     * @param strategy
-     * @param earliestBlock
-     */
-    private Block latestBlock(ValueNode node, SchedulingStrategy strategy, Block earliestBlock) {
-        Block block = null;
-        for (Node usage : node.usages()) {
-            block = blocksForUsage(node, usage, block, earliestBlock, strategy);
-            if (block == earliestBlock) {
-                break;
-            }
-        }
-
-        assert assertLatestBlockResult(node, block);
-        return block;
-    }
-
-    private boolean assertLatestBlockResult(ValueNode node, Block block) throws SchedulingError {
-        if (block != null && !dominates(earliestBlock(node), block)) {
-            throw new SchedulingError("failed to find correct latest schedule for %s. cdbc: %s, earliest: %s", node, block, earliestBlock(node));
-        }
-        return true;
-    }
-
-    /**
-     * Determines the earliest block in which the given node can be scheduled.
-     */
-    private Block earliestBlock(Node node) {
-        Block earliest = cfg.getNodeToBlock().get(node);
-        if (earliest != null) {
-            return earliest;
-        }
-        earliest = earliestCache.get(node);
-        if (earliest != null) {
-            return earliest;
-        }
-        return earliestBlockHelper(node, earliest);
-    }
-
-    private Block earliestBlockHelper(Node node, Block earliestStart) throws SchedulingError {
-        /*
-         * All inputs must be in a dominating block, otherwise the graph cannot be scheduled. This
-         * implies that the inputs' blocks have a total ordering via their dominance relation. So in
-         * order to find the earliest block placement for this node we need to find the input block
-         * that is dominated by all other input blocks.
-         */
-        Block earliest = earliestStart;
-
-        if (node.predecessor() != null) {
-            throw new SchedulingError();
-        }
-        for (Node input : node.inputs()) {
-            if (input != null) {
-                assert input instanceof ValueNode;
-                Block inputEarliest;
-                if (input instanceof InvokeWithExceptionNode) {
-                    inputEarliest = cfg.getNodeToBlock().get(((InvokeWithExceptionNode) input).next());
-                } else {
-                    inputEarliest = earliestBlock(input);
-                }
-                if (earliest == null || earliest.getDominatorDepth() < inputEarliest.getDominatorDepth()) {
-                    earliest = inputEarliest;
-                }
-            }
-        }
-        if (earliest == null) {
-            earliest = cfg.getStartBlock();
-        }
-        earliestCache.set(node, earliest);
-        return earliest;
-    }
-
-    /**
-     * Schedules a node out of loop based on its earliest schedule. Note that this movement is only
-     * valid if it's done for <b>every</b> other node in the schedule, otherwise this movement is
-     * not valid.
-     *
-     * @param n Node to schedule
-     * @param latestBlock latest possible schedule for {@code n}
-     * @param earliest earliest possible schedule for {@code n}
-     * @return block schedule for {@code n} which is not inside a loop (if possible)
-     */
-    private static Block scheduleOutOfLoops(Node n, Block latestBlock, Block earliest) {
-        if (latestBlock == null) {
-            throw new SchedulingError("no latest : %s", n);
-        }
-        Block cur = latestBlock;
-        Block result = latestBlock;
-        Loop<?> earliestLoop = earliest.getLoop();
-        while (true) {
-            Loop<?> curLoop = cur.getLoop();
-            if (curLoop == earliestLoop) {
-                return result;
-            } else {
-                Block dom = cur.getDominator();
-                if (dom.getLoopDepth() < result.getLoopDepth()) {
-                    result = dom;
-                }
-                cur = dom;
-            }
-        }
-    }
-
-    /**
-     * 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 earliestBlock
-     */
-    private Block blocksForUsage(ValueNode node, Node usage, Block startCurrentBlock, Block earliestBlock, SchedulingStrategy strategy) {
-        assert !(node instanceof PhiNode);
-        Block currentBlock = startCurrentBlock;
-        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;
-            AbstractMergeNode merge = phi.merge();
-            Block mergeBlock = cfg.getNodeToBlock().get(merge);
-            for (int i = 0; i < phi.valueCount(); ++i) {
-                if (phi.valueAt(i) == node) {
-                    currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, mergeBlock.getPredecessors().get(i));
-                    if (currentBlock == earliestBlock) {
-                        break;
-                    }
-                }
-            }
-        } else if (usage instanceof VirtualState) {
-            // The following logic does not work if node is a PhiNode, but this method is never
-            // called for PhiNodes.
-            for (Node unscheduledUsage : usage.usages()) {
-                if (unscheduledUsage instanceof VirtualState) {
-                    // If a FrameState is an outer FrameState this method behaves as if the inner
-                    // FrameState was the actual usage, by recursing.
-                    currentBlock = blocksForUsage(node, unscheduledUsage, currentBlock, earliestBlock, strategy);
-                } else if (unscheduledUsage instanceof AbstractBeginNode) {
-                    // Only FrameStates can be connected to BeginNodes.
-                    if (!(usage instanceof FrameState)) {
-                        throw new SchedulingError(usage.toString());
-                    }
-                    if (unscheduledUsage instanceof StartNode) {
-                        currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(unscheduledUsage));
-                    } else {
-                        // If a FrameState belongs to a BeginNode then it's inputs will be placed at
-                        // the common dominator of all EndNodes.
-                        for (Node pred : unscheduledUsage.cfgPredecessors()) {
-                            currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(pred));
-                        }
-                    }
-                } else {
-                    // For the time being, FrameStates can only be connected to NodeWithState.
-                    if (!(usage instanceof FrameState)) {
-                        throw new SchedulingError(usage.toString());
-                    }
-                    if (!(unscheduledUsage instanceof NodeWithState)) {
-                        throw new SchedulingError(unscheduledUsage.toString());
-                    }
-                    // Otherwise: Put the input into the same block as the usage.
-                    assignBlockToNode((ValueNode) unscheduledUsage, strategy);
-                    currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(unscheduledUsage));
-                }
-                if (currentBlock == earliestBlock) {
-                    break;
-                }
-            }
-        } else {
-            // All other types of usages: Put the input into the same block as the usage.
-            assignBlockToNode((ValueNode) usage, strategy);
-            currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(usage));
-        }
-        return currentBlock;
-    }
-
-    private void sortNodesWithinBlocks(StructuredGraph graph, SchedulingStrategy strategy) {
-        NodeBitMap visited = graph.createNodeBitMap();
-        NodeBitMap beforeLastLocation = graph.createNodeBitMap();
-        for (Block b : cfg.getBlocks()) {
-            sortNodesWithinBlock(b, visited, beforeLastLocation, strategy);
-            assert noDuplicatedNodesInBlock(b) : "duplicated nodes in " + b;
-        }
-    }
-
-    private boolean noDuplicatedNodesInBlock(Block b) {
-        List<ValueNode> list = blockToNodesMap.get(b);
-        Set<ValueNode> hashset = Node.newSet(list);
-        return list.size() == hashset.size();
-    }
-
-    private void sortNodesWithinBlock(Block b, NodeBitMap visited, NodeBitMap beforeLastLocation, SchedulingStrategy strategy) {
-        if (visited.isMarked(b.getBeginNode()) || cfg.blockFor(b.getBeginNode()) != b) {
-            throw new SchedulingError();
-        }
-        if (visited.isMarked(b.getEndNode()) || cfg.blockFor(b.getEndNode()) != b) {
-            throw new SchedulingError();
-        }
-
-        List<ValueNode> sortedInstructions;
-        assert strategy == SchedulingStrategy.LATEST || strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS;
-        sortedInstructions = sortNodesWithinBlockLatest(b, visited, beforeLastLocation);
-        assert filterSchedulableNodes(blockToNodesMap.get(b)).size() == removeProxies(sortedInstructions).size() : "sorted block does not contain the same amount of nodes: " +
-                        filterSchedulableNodes(blockToNodesMap.get(b)) + " vs. " + removeProxies(sortedInstructions);
-        assert sameOrderForFixedNodes(blockToNodesMap.get(b), sortedInstructions) : "fixed nodes in sorted block are not in the same order";
-        blockToNodesMap.put(b, sortedInstructions);
-    }
-
-    private static List<ValueNode> removeProxies(List<ValueNode> list) {
-        List<ValueNode> result = new ArrayList<>();
-        for (ValueNode n : list) {
-            if (!(n instanceof ProxyNode)) {
-                result.add(n);
-            }
-        }
-        return result;
-    }
-
-    private static List<ValueNode> filterSchedulableNodes(List<ValueNode> list) {
-        List<ValueNode> result = new ArrayList<>();
-        for (ValueNode n : list) {
-            if (!(n instanceof PhiNode)) {
-                result.add(n);
-            }
-        }
-        return result;
-    }
-
-    private static boolean sameOrderForFixedNodes(List<ValueNode> fixed, List<ValueNode> sorted) {
-        Iterator<ValueNode> fixedIterator = fixed.iterator();
-        Iterator<ValueNode> sortedIterator = sorted.iterator();
-
-        while (sortedIterator.hasNext()) {
-            ValueNode sortedCurrent = sortedIterator.next();
-            if (sortedCurrent instanceof FixedNode) {
-                if (!(fixedIterator.hasNext() && fixedIterator.next() == sortedCurrent)) {
-                    return false;
-                }
-            }
-        }
-
-        while (fixedIterator.hasNext()) {
-            if (fixedIterator.next() instanceof FixedNode) {
-                return false;
-            }
-        }
-
-        return true;
-    }
-
-    private static class SortState {
-        private Block block;
-        private NodeBitMap visited;
-        private NodeBitMap beforeLastLocation;
-        private List<ValueNode> sortedInstructions;
-        private List<FloatingReadNode> reads;
-
-        SortState(Block block, NodeBitMap visited, NodeBitMap beforeLastLocation, List<ValueNode> sortedInstructions) {
-            this.block = block;
-            this.visited = visited;
-            this.beforeLastLocation = beforeLastLocation;
-            this.sortedInstructions = sortedInstructions;
-            this.reads = null;
-        }
-
-        public Block currentBlock() {
-            return block;
-        }
-
-        void markVisited(Node n) {
-            visited.mark(n);
-        }
-
-        boolean isVisited(Node n) {
-            return visited.isMarked(n);
-        }
-
-        void markBeforeLastLocation(FloatingReadNode n) {
-            beforeLastLocation.mark(n);
-        }
-
-        void clearBeforeLastLocation(FloatingReadNode frn) {
-            beforeLastLocation.clear(frn);
-        }
-
-        boolean isBeforeLastLocation(FloatingReadNode n) {
-            return beforeLastLocation.isMarked(n);
-        }
-
-        void addRead(FloatingReadNode n) {
-            if (reads == null) {
-                reads = new ArrayList<>();
-            }
-            reads.add(n);
-        }
-
-        int readsSize() {
-            if (reads == null) {
-                return 0;
-            }
-            return reads.size();
-        }
-
-        void removeRead(ValueNode i) {
-            assert reads != null;
-            reads.remove(i);
-        }
-
-        List<FloatingReadNode> readsSnapshot() {
-            assert reads != null;
-            return new ArrayList<>(reads);
-        }
-
-        List<ValueNode> getSortedInstructions() {
-            return sortedInstructions;
-        }
-
-        boolean containsInstruction(ValueNode i) {
-            return sortedInstructions.contains(i);
-        }
-
-        void addInstruction(ValueNode i) {
-            sortedInstructions.add(i);
-        }
-    }
-
-    /**
-     * Sorts the nodes within a block by adding the nodes to a list in a post-order iteration over
-     * all inputs. This means that a node is added to the list after all its inputs have been
-     * processed.
-     */
-    private List<ValueNode> sortNodesWithinBlockLatest(Block b, NodeBitMap visited, NodeBitMap beforeLastLocation) {
-        SortState state = new SortState(b, visited, beforeLastLocation, new ArrayList<>(blockToNodesMap.get(b).size() + 2));
-        List<ValueNode> instructions = blockToNodesMap.get(b);
-
-        for (ValueNode i : instructions) {
-            if (i instanceof FloatingReadNode) {
-                FloatingReadNode frn = (FloatingReadNode) i;
-                if (!frn.location().getLocationIdentity().isImmutable()) {
-                    state.addRead(frn);
-                    if (nodesFor(b).contains(frn.getLastLocationAccess())) {
-                        assert !state.isBeforeLastLocation(frn);
-                        state.markBeforeLastLocation(frn);
-                    }
-                }
-            }
-        }
-
-        for (ValueNode i : instructions) {
-            addToLatestSorting(i, state);
-        }
-        assert state.readsSize() == 0 : "not all reads are scheduled";
-
-        // Make sure that last node gets really last (i.e. when a frame state successor hangs off
-        // it).
-        List<ValueNode> sortedInstructions = state.getSortedInstructions();
-        Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1);
-        if (lastSorted != b.getEndNode()) {
-            sortedInstructions.remove(b.getEndNode());
-            sortedInstructions.add(b.getEndNode());
-        }
-        return sortedInstructions;
-    }
-
-    private void processKillLocation(Node node, LocationIdentity identity, SortState state) {
-        for (FloatingReadNode frn : state.readsSnapshot()) {
-            LocationIdentity readLocation = frn.location().getLocationIdentity();
-            assert !readLocation.isImmutable();
-            if (frn.getLastLocationAccess() == node) {
-                assert identity.equals(ANY_LOCATION) || readLocation.equals(identity) || node instanceof MemoryCheckpoint.Multi : "location doesn't match: " + readLocation + ", " + identity;
-                state.clearBeforeLastLocation(frn);
-            } else if (!state.isBeforeLastLocation(frn) && (readLocation.equals(identity) || (node != getCFG().graph.start() && ANY_LOCATION.equals(identity)))) {
-                state.removeRead(frn);
-                addToLatestSorting(frn, state);
-            }
-        }
-    }
-
-    private void addUnscheduledToLatestSorting(VirtualState state, SortState sortState) {
-        if (state != null) {
-            // UnscheduledNodes should never be marked as visited.
-            if (sortState.isVisited(state)) {
-                throw new SchedulingError();
-            }
-
-            for (Node input : state.inputs()) {
-                if (input instanceof VirtualState) {
-                    addUnscheduledToLatestSorting((VirtualState) input, sortState);
-                } else {
-                    addToLatestSorting((ValueNode) input, sortState);
-                }
-            }
-        }
-    }
-
-    private void addToLatestSorting(ValueNode i, SortState state) {
-        if (i == null || state.isVisited(i) || cfg.getNodeToBlock().get(i) != state.currentBlock() || i instanceof PhiNode) {
-            return;
-        }
-
-        if (i instanceof ProxyNode) {
-            ProxyNode proxyNode = (ProxyNode) i;
-            addToLatestSorting(proxyNode.value(), state);
-            return;
-        }
-
-        if (i instanceof LoopExitNode) {
-            LoopExitNode loopExitNode = (LoopExitNode) i;
-            for (ProxyNode proxy : loopExitNode.proxies()) {
-                addToLatestSorting(proxy, state);
-            }
-        }
-
-        addToLatestSortingHelper(i, state);
-    }
-
-    private void addToLatestSortingHelper(ValueNode i, SortState state) {
-        FrameState stateAfter = null;
-        if (i instanceof StateSplit) {
-            stateAfter = ((StateSplit) i).stateAfter();
-        }
-
-        addInputsToLatestSorting(i, state, stateAfter);
-
-        if (state.readsSize() != 0) {
-            if (i instanceof MemoryCheckpoint.Single) {
-                LocationIdentity identity = ((MemoryCheckpoint.Single) i).getLocationIdentity();
-                processKillLocation(i, identity, state);
-            } else if (i instanceof MemoryCheckpoint.Multi) {
-                for (LocationIdentity identity : ((MemoryCheckpoint.Multi) i).getLocationIdentities()) {
-                    processKillLocation(i, identity, state);
-                }
-            }
-            assert MemoryCheckpoint.TypeAssertion.correctType(i);
-        }
-
-        addToLatestSorting((ValueNode) i.predecessor(), state);
-        state.markVisited(i);
-        addUnscheduledToLatestSorting(stateAfter, state);
-
-        // Now predecessors and inputs are scheduled => we can add this node.
-        if (!state.containsInstruction(i)) {
-            state.addInstruction(i);
-        }
-
-        if (state.readsSize() != 0 && i instanceof FloatingReadNode) {
-            state.removeRead(i);
-        }
-    }
-
-    private void addInputsToLatestSorting(ValueNode i, SortState state, FrameState stateAfter) {
-        for (Node input : i.inputs()) {
-            if (input instanceof FrameState) {
-                if (input != stateAfter) {
-                    addUnscheduledToLatestSorting((FrameState) input, state);
-                }
-            } else {
-                addToLatestSorting((ValueNode) input, state);
-            }
-        }
-    }
 }
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java	Fri Mar 13 12:27:07 2015 +0100
@@ -147,7 +147,7 @@
 
                 @Override
                 protected NodeBitMap processBlock(final Block block, final NodeBitMap currentState) {
-                    final List<ValueNode> list = schedule.getBlockToNodesMap().get(block);
+                    final List<Node> list = schedule.getBlockToNodesMap().get(block);
 
                     /*
                      * A stateAfter is not valid directly after its associated state split, but
@@ -155,7 +155,7 @@
                      * will be checked at the correct position.
                      */
                     FrameState pendingStateAfter = null;
-                    for (final ValueNode node : list) {
+                    for (final Node node : list) {
                         FrameState stateAfter = node instanceof StateSplit ? ((StateSplit) node).stateAfter() : null;
                         if (node instanceof FullInfopointNode) {
                             stateAfter = ((FullInfopointNode) node).getState();
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java	Fri Mar 13 12:27:07 2015 +0100
@@ -140,7 +140,7 @@
             }
         }
         ControlFlowGraph cfg = schedule == null ? null : schedule.getCFG();
-        BlockMap<List<ValueNode>> blockToNodes = schedule == null ? null : schedule.getBlockToNodesMap();
+        BlockMap<List<Node>> blockToNodes = schedule == null ? null : schedule.getBlockToNodesMap();
         List<Block> blocks = cfg == null ? null : cfg.getBlocks();
         writeNodes(graph);
         writeBlocks(blocks, blockToNodes);
@@ -468,11 +468,18 @@
         }
     }
 
-    private void writeBlocks(List<Block> blocks, BlockMap<List<ValueNode>> blockToNodes) throws IOException {
+    private void writeBlocks(List<Block> blocks, BlockMap<List<Node>> blockToNodes) throws IOException {
         if (blocks != null) {
+            for (Block block : blocks) {
+                List<Node> nodes = blockToNodes.get(block);
+                if (nodes == null) {
+                    writeInt(0);
+                    return;
+                }
+            }
             writeInt(blocks.size());
             for (Block block : blocks) {
-                List<ValueNode> nodes = blockToNodes.get(block);
+                List<Node> nodes = blockToNodes.get(block);
                 writeInt(block.getId());
                 writeInt(nodes.size());
                 for (Node node : nodes) {
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java	Fri Mar 13 12:27:07 2015 +0100
@@ -604,7 +604,7 @@
         printedNodes = null;
     }
 
-    private void printScheduledBlock(Block block, List<ValueNode> nodesFor) {
+    private void printScheduledBlock(Block block, List<Node> nodesFor) {
         printBlockProlog(block);
         begin("IR");
         out.println("HIR");
diff -r e87d55dfbbbb -r 79682c7f2ec7 graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Fri Mar 13 11:26:37 2015 +0100
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Fri Mar 13 12:27:07 2015 +0100
@@ -119,7 +119,7 @@
     @Override
     protected boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
         boolean isMarked = usages.isMarked(node);
-        if (isMarked || node instanceof VirtualizableRoot) {
+        if ((isMarked && node instanceof ValueNode) || node instanceof VirtualizableRoot) {
             VirtualUtil.trace("[[%s]] ", node);
             FixedNode nextFixedNode = lastFixedNode == null ? null : lastFixedNode.next();
             return processNode((ValueNode) node, nextFixedNode, state, effects, isMarked);