# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1426199043 -3600
# Node ID 6b73ce815fc2e8eb0bbc7a7e3a2b4766e718c112
# Parent  29916dcee0b84eac8bf1195532c0e443240396ce
Add a new algorithm for latest possible schedule. Fix earliest possible schedule for the case of floating reads. Add scheduling test cases.

diff -r 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/LocationIdentity.java	Thu Mar 12 23:24:03 2015 +0100
@@ -59,4 +59,8 @@
     default boolean isImmutable() {
         return false;
     }
+
+    default boolean isMutable() {
+        return !isImmutable();
+    }
 }
diff -r 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java	Thu Mar 12 23:24:03 2015 +0100
@@ -324,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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraphScheduleTest.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/SchedulingTest.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/NodeLIRBuilder.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchContext.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchPattern.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchRuleRegistry.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/match/MatchStatement.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryArithmeticNode.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/HIRLoop.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeLIRBuilderTool.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/NodeMappableLIRBuilder.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ProfileCompiledMethodsPhase.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ScheduledNodeIterator.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Thu Mar 12 23:24:03 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
@@ -75,96 +75,6 @@
         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;
@@ -299,7 +209,7 @@
     /**
      * 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;
@@ -317,37 +227,382 @@
         scheduleConstants = value;
     }
 
+    private static final boolean USE_NEW_STRATEGY = true;
+
     @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 if (USE_NEW_STRATEGY) {
+            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 (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 (selectedStrategy != SchedulingStrategy.EARLIEST && graph.isAfterFloatingReadPhase()) {
-            blockToKillSet = new BlockMap<>(cfg);
+                                            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);
+            }
+        } else {
+
+            earliestCache = graph.createNodeMap();
+            blockToNodesMap = new BlockMap<>(cfg);
+
+            if (selectedStrategy != SchedulingStrategy.EARLIEST && graph.isAfterFloatingReadPhase()) {
+                blockToKillSet = new BlockMap<>(cfg);
+            }
+
+            assignBlockToNodes(graph, selectedStrategy);
+            printSchedule("after assign nodes to blocks");
+
+            sortNodesWithinBlocks(graph, selectedStrategy);
+            printSchedule("after sorting nodes within blocks");
+        }
+    }
+
+    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,7 +629,7 @@
             nodeToBlock.set(endNode, b);
         }
 
-        processStack(blockToNodes, nodeToBlock, visited, stack);
+        processStack(cfg, blockToNodes, nodeToBlock, visited, floatingReads, stack);
 
         // Visit back input edges of loop phis.
         for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) {
@@ -384,7 +639,7 @@
                         Node node = phi.valueAt(i + loopBegin.forwardEndCount());
                         if (node != null && !visited.isMarked(node)) {
                             stack.push(node);
-                            processStack(blockToNodes, nodeToBlock, visited, stack);
+                            processStack(cfg, blockToNodes, nodeToBlock, visited, floatingReads, stack);
                         }
                     }
                 }
@@ -409,16 +664,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();
@@ -479,10 +798,14 @@
                         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);
                 }
             }
         }
@@ -564,7 +887,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;
     }
 
@@ -575,13 +898,13 @@
     /**
      * 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<>();
+            List<Node> nodes = new ArrayList<>();
             if (blockToNodesMap.get(block) != null) {
                 throw new SchedulingError();
             }
@@ -956,8 +1279,8 @@
     }
 
     private boolean noDuplicatedNodesInBlock(Block b) {
-        List<ValueNode> list = blockToNodesMap.get(b);
-        Set<ValueNode> hashset = Node.newSet(list);
+        List<Node> list = blockToNodesMap.get(b);
+        Set<Node> hashset = Node.newSet(list);
         return list.size() == hashset.size();
     }
 
@@ -969,7 +1292,7 @@
             throw new SchedulingError();
         }
 
-        List<ValueNode> sortedInstructions;
+        List<Node> 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: " +
@@ -978,9 +1301,9 @@
         blockToNodesMap.put(b, sortedInstructions);
     }
 
-    private static List<ValueNode> removeProxies(List<ValueNode> list) {
-        List<ValueNode> result = new ArrayList<>();
-        for (ValueNode n : list) {
+    private static List<Node> removeProxies(List<Node> list) {
+        List<Node> result = new ArrayList<>();
+        for (Node n : list) {
             if (!(n instanceof ProxyNode)) {
                 result.add(n);
             }
@@ -988,9 +1311,9 @@
         return result;
     }
 
-    private static List<ValueNode> filterSchedulableNodes(List<ValueNode> list) {
-        List<ValueNode> result = new ArrayList<>();
-        for (ValueNode n : list) {
+    private static List<Node> filterSchedulableNodes(List<Node> list) {
+        List<Node> result = new ArrayList<>();
+        for (Node n : list) {
             if (!(n instanceof PhiNode)) {
                 result.add(n);
             }
@@ -998,12 +1321,12 @@
         return result;
     }
 
-    private static boolean sameOrderForFixedNodes(List<ValueNode> fixed, List<ValueNode> sorted) {
-        Iterator<ValueNode> fixedIterator = fixed.iterator();
-        Iterator<ValueNode> sortedIterator = sorted.iterator();
+    private static boolean sameOrderForFixedNodes(List<Node> fixed, List<Node> sorted) {
+        Iterator<Node> fixedIterator = fixed.iterator();
+        Iterator<Node> sortedIterator = sorted.iterator();
 
         while (sortedIterator.hasNext()) {
-            ValueNode sortedCurrent = sortedIterator.next();
+            Node sortedCurrent = sortedIterator.next();
             if (sortedCurrent instanceof FixedNode) {
                 if (!(fixedIterator.hasNext() && fixedIterator.next() == sortedCurrent)) {
                     return false;
@@ -1024,10 +1347,10 @@
         private Block block;
         private NodeBitMap visited;
         private NodeBitMap beforeLastLocation;
-        private List<ValueNode> sortedInstructions;
+        private List<Node> sortedInstructions;
         private List<FloatingReadNode> reads;
 
-        SortState(Block block, NodeBitMap visited, NodeBitMap beforeLastLocation, List<ValueNode> sortedInstructions) {
+        SortState(Block block, NodeBitMap visited, NodeBitMap beforeLastLocation, List<Node> sortedInstructions) {
             this.block = block;
             this.visited = visited;
             this.beforeLastLocation = beforeLastLocation;
@@ -1073,7 +1396,7 @@
             return reads.size();
         }
 
-        void removeRead(ValueNode i) {
+        void removeRead(Node i) {
             assert reads != null;
             reads.remove(i);
         }
@@ -1083,15 +1406,15 @@
             return new ArrayList<>(reads);
         }
 
-        List<ValueNode> getSortedInstructions() {
+        List<Node> getSortedInstructions() {
             return sortedInstructions;
         }
 
-        boolean containsInstruction(ValueNode i) {
+        boolean containsInstruction(Node i) {
             return sortedInstructions.contains(i);
         }
 
-        void addInstruction(ValueNode i) {
+        void addInstruction(Node i) {
             sortedInstructions.add(i);
         }
     }
@@ -1101,11 +1424,11 @@
      * 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) {
+    private List<Node> 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);
+        List<Node> instructions = blockToNodesMap.get(b);
 
-        for (ValueNode i : instructions) {
+        for (Node i : instructions) {
             if (i instanceof FloatingReadNode) {
                 FloatingReadNode frn = (FloatingReadNode) i;
                 if (!frn.location().getLocationIdentity().isImmutable()) {
@@ -1118,14 +1441,14 @@
             }
         }
 
-        for (ValueNode i : instructions) {
+        for (Node 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();
+        List<Node> sortedInstructions = state.getSortedInstructions();
         Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1);
         if (lastSorted != b.getEndNode()) {
             sortedInstructions.remove(b.getEndNode());
@@ -1159,13 +1482,13 @@
                 if (input instanceof VirtualState) {
                     addUnscheduledToLatestSorting((VirtualState) input, sortState);
                 } else {
-                    addToLatestSorting((ValueNode) input, sortState);
+                    addToLatestSorting(input, sortState);
                 }
             }
         }
     }
 
-    private void addToLatestSorting(ValueNode i, SortState state) {
+    private void addToLatestSorting(Node i, SortState state) {
         if (i == null || state.isVisited(i) || cfg.getNodeToBlock().get(i) != state.currentBlock() || i instanceof PhiNode) {
             return;
         }
@@ -1186,7 +1509,7 @@
         addToLatestSortingHelper(i, state);
     }
 
-    private void addToLatestSortingHelper(ValueNode i, SortState state) {
+    private void addToLatestSortingHelper(Node i, SortState state) {
         FrameState stateAfter = null;
         if (i instanceof StateSplit) {
             stateAfter = ((StateSplit) i).stateAfter();
@@ -1206,7 +1529,7 @@
             assert MemoryCheckpoint.TypeAssertion.correctType(i);
         }
 
-        addToLatestSorting((ValueNode) i.predecessor(), state);
+        addToLatestSorting(i.predecessor(), state);
         state.markVisited(i);
         addUnscheduledToLatestSorting(stateAfter, state);
 
@@ -1220,14 +1543,14 @@
         }
     }
 
-    private void addInputsToLatestSorting(ValueNode i, SortState state, FrameState stateAfter) {
+    private void addInputsToLatestSorting(Node 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);
+                addToLatestSorting(input, state);
             }
         }
     }
diff -r 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java	Thu Mar 12 23:24:03 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 29916dcee0b8 -r 6b73ce815fc2 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	Tue Mar 10 22:18:53 2015 -0700
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Thu Mar 12 23:24:03 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);