--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/MemoryScheduleTest.java	Tue Feb 26 17:04:17 2013 +0100
@@ -0,0 +1,218 @@
+/*
+ * Copyright (c) 2011, 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.compiler.test;
+
+import java.util.concurrent.*;
+
+import org.junit.*;
+
+import com.oracle.graal.api.code.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.graph.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.extended.*;
+import com.oracle.graal.nodes.util.*;
+import com.oracle.graal.phases.common.*;
+import com.oracle.graal.phases.schedule.*;
+
+/**
+ * In these test the FrameStates are explicitly cleared out, so that the scheduling of
+ * FloatingReadNodes depends solely on the scheduling algorithm. The FrameStates normally keep the
+ * FloatingReadNodes above a certain point, so that they (most of the time...) magically do the
+ * right thing.
+ * 
+ * The scheduling shouldn't depend on FrameStates, which is tested by this class.
+ */
+public class MemoryScheduleTest extends GraphScheduleTest {
+
+    private static enum TestMode {
+        WITH_FRAMESTATES, WITHOUT_FRAMESTATES
+    }
+
+    public static class Container {
+
+        public int a;
+        public int b;
+        public int c;
+    }
+
+    private static final Container container = new Container();
+
+    public static int testSimpleSnippet() {
+        // in this test the read should be scheduled before the write
+        try {
+            return container.a;
+        } finally {
+            container.a = 15;
+        }
+    }
+
+    @Test
+    public void testSimple() {
+        for (TestMode mode : TestMode.values()) {
+            SchedulePhase schedule = getFinalSchedule("testSimpleSnippet", mode);
+            assertReadAfterWrite(schedule, false);
+        }
+    }
+
+    /**
+     * In this case the read should be scheduled in the first block.
+     */
+    public static int testSplitSnippet1(int a) {
+        try {
+            return container.a;
+        } finally {
+            if (a < 0) {
+                container.a = 15;
+            } else {
+                container.b = 15;
+            }
+        }
+    }
+
+    @Test
+    public void testSplit1() {
+        for (TestMode mode : TestMode.values()) {
+            SchedulePhase schedule = getFinalSchedule("testSplitSnippet1", mode);
+            assertReadWithinStartBlock(schedule, true);
+        }
+    }
+
+    /**
+     * Here the read should float to the end.
+     */
+    public static int testSplit2Snippet(int a) {
+        try {
+            return container.a;
+        } finally {
+            if (a < 0) {
+                container.c = 15;
+            } else {
+                container.b = 15;
+            }
+        }
+    }
+
+    @Test
+    public void testSplit2() {
+        SchedulePhase schedule = getFinalSchedule("testSplit2Snippet", TestMode.WITHOUT_FRAMESTATES);
+        assertReadWithinStartBlock(schedule, false);
+    }
+
+    /**
+     * Here the read should not float to the end.
+     */
+    public static int testLoop1Snippet(int a, int b) {
+        try {
+            return container.a;
+        } finally {
+            for (int i = 0; i < a; i++) {
+                if (b < 0) {
+                    container.b = 10;
+                } else {
+                    container.a = 15;
+                }
+            }
+        }
+    }
+
+    @Test
+    public void testLoop1() {
+        SchedulePhase schedule = getFinalSchedule("testLoop1Snippet", TestMode.WITHOUT_FRAMESTATES);
+        assertEquals(7, schedule.getCFG().getBlocks().length);
+        assertReadWithinStartBlock(schedule, true);
+    }
+
+    /**
+     * Here the read should float to the end.
+     */
+    public static int testLoop2Snippet(int a, int b) {
+        try {
+            return container.a;
+        } finally {
+            for (int i = 0; i < a; i++) {
+                if (b < 0) {
+                    container.b = 10;
+                } else {
+                    container.c = 15;
+                }
+            }
+        }
+    }
+
+    @Test
+    public void testLoop2() {
+        SchedulePhase schedule = getFinalSchedule("testLoop2Snippet", TestMode.WITHOUT_FRAMESTATES);
+        assertEquals(7, schedule.getCFG().getBlocks().length);
+        assertReadWithinStartBlock(schedule, false);
+    }
+
+    private void assertReadAfterWrite(SchedulePhase schedule, boolean readAfterWrite) {
+        boolean writeEncountered = false;
+        assertEquals(1, schedule.getCFG().getBlocks().length);
+        for (Node node : schedule.getBlockToNodesMap().get(schedule.getCFG().getStartBlock())) {
+            if (node instanceof WriteNode) {
+                writeEncountered = true;
+            } else if (node instanceof FloatingReadNode) {
+                assertEquals(readAfterWrite, writeEncountered);
+            }
+        }
+    }
+
+    private void assertReadWithinStartBlock(SchedulePhase schedule, boolean withinStartBlock) {
+        boolean readEncountered = false;
+        for (Node node : schedule.getBlockToNodesMap().get(schedule.getCFG().getStartBlock())) {
+            if (node instanceof FloatingReadNode) {
+                readEncountered = true;
+            }
+        }
+        assertEquals(withinStartBlock, readEncountered);
+    }
+
+    private SchedulePhase getFinalSchedule(final String snippet, final TestMode mode) {
+        return Debug.scope("FloatingReadTest", new DebugDumpScope(snippet), new Callable<SchedulePhase>() {
+
+            @Override
+            public SchedulePhase call() throws Exception {
+                StructuredGraph graph = parse(snippet);
+                if (mode == TestMode.WITHOUT_FRAMESTATES) {
+                    for (Node node : graph.getNodes()) {
+                        if (node instanceof StateSplit) {
+                            FrameState stateAfter = ((StateSplit) node).stateAfter();
+                            if (stateAfter != null) {
+                                ((StateSplit) node).setStateAfter(null);
+                                GraphUtil.killWithUnusedFloatingInputs(stateAfter);
+                            }
+                        }
+                    }
+                }
+                new LoweringPhase(null, runtime(), new Assumptions(false)).apply(graph);
+                new FloatingReadPhase().apply(graph);
+
+                SchedulePhase schedule = new SchedulePhase();
+                schedule.apply(graph);
+                return schedule;
+            }
+        });
+    }
+}

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java	Wed Feb 13 18:06:19 2013 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java	Tue Feb 26 17:04:17 2013 +0100
@@ -72,6 +72,10 @@
         assert !isNew(node) : "this node was added to the graph after creating the node map : " + node;
     }
 
+    public void clear() {
+        Arrays.fill(values, null);
+    }
+
     public Iterable<Entry<Node, T>> entries() {
         return new Iterable<Entry<Node, T>>() {
 

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java	Wed Feb 13 18:06:19 2013 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java	Tue Feb 26 17:04:17 2013 +0100
@@ -108,9 +108,38 @@
         return loops;
     }
 
+    public void clearNodeToBlock() {
+        nodeToBlock.clear();
+        for (Block block : reversePostOrder) {
+            identifyBlock(block, block.beginNode);
+        }
+    }
+
     protected static final int BLOCK_ID_INITIAL = -1;
     protected static final int BLOCK_ID_VISITED = -2;
 
+    private void identifyBlock(Block block, BeginNode begin) {
+        block.beginNode = begin;
+        Node cur = begin;
+        Node last;
+        do {
+            assert !cur.isDeleted();
+
+            assert nodeToBlock.get(cur) == null;
+            nodeToBlock.set(cur, block);
+            if (cur instanceof MergeNode) {
+                for (PhiNode phi : ((MergeNode) cur).phis()) {
+                    nodeToBlock.set(phi, block);
+                }
+            }
+
+            last = cur;
+            cur = cur.successors().first();
+        } while (cur != null && !(cur instanceof BeginNode));
+
+        block.endNode = (FixedNode) last;
+    }
+
     private void identifyBlocks() {
         // Find all block headers
         int numBlocks = 0;
@@ -118,26 +147,7 @@
             if (node instanceof BeginNode) {
                 Block block = new Block();
                 numBlocks++;
-
-                block.beginNode = (BeginNode) node;
-                Node cur = node;
-                Node last;
-                do {
-                    assert !cur.isDeleted();
-
-                    assert nodeToBlock.get(cur) == null;
-                    nodeToBlock.set(cur, block);
-                    if (cur instanceof MergeNode) {
-                        for (PhiNode phi : ((MergeNode) cur).phis()) {
-                            nodeToBlock.set(phi, block);
-                        }
-                    }
-
-                    last = cur;
-                    cur = cur.successors().first();
-                } while (cur != null && !(cur instanceof BeginNode));
-
-                block.endNode = (FixedNode) last;
+                identifyBlock(block, (BeginNode) node);
             }
         }
 

--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java	Wed Feb 13 18:06:19 2013 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java	Tue Feb 26 17:04:17 2013 +0100
@@ -168,6 +168,8 @@
     public static boolean CanOmitFrame                       = true;
     public static int     SafepointPollOffset                = 256;
 
+    public static boolean MemoryAwareScheduling              = true;
+
     // Translating tableswitch instructions
     public static int     MinimumJumpTableSize               = 5;
     public static int     RangeTestsSwitchDensity            = 5;

--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Wed Feb 13 18:06:19 2013 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Tue Feb 26 17:04:17 2013 +0100
@@ -28,12 +28,102 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.graph.Node.Verbosity;
 import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.cfg.*;
 import com.oracle.graal.nodes.extended.*;
 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 class SchedulePhase extends Phase {
+public final class SchedulePhase extends Phase {
+
+    public static enum SchedulingStrategy {
+        EARLIEST, LATEST, LATEST_OUT_OF_LOOPS
+    }
+
+    /**
+     * This closure iterates over all nodes of a scheduled graph (it expects a
+     * {@link SchedulingStrategy#EARLIEST} schedule) and keeps a list of "actuve" reads. Whenever it
+     * encounters a read, it adds it to the active reads. Whenever it encounters a memory
+     * checkpoint, it adds all reads that need to be committed before this checkpoint to the
+     * "phantom" usages and inputs, so that the read is scheduled before the checkpoint afterwards.
+     * 
+     * At merges, the intersection of all sets of active reads is calculated. A read that was
+     * committed within one predecessor branch cannot be scheduled after the merge anyway.
+     * 
+     * Similarly for loops, all reads that are killed somewhere within the loop are removed from the
+     * exits' active reads, since they cannot be scheduled after the exit anyway.
+     */
+    private class MemoryScheduleClosure extends BlockIteratorClosure<HashSet<FloatingReadNode>> {
+
+        @Override
+        protected void processBlock(Block block, HashSet<FloatingReadNode> currentState) {
+            for (Node node : getBlockToNodesMap().get(block)) {
+                if (node instanceof FloatingReadNode) {
+                    currentState.add((FloatingReadNode) node);
+                } else if (node instanceof MemoryCheckpoint) {
+                    Object identity = ((MemoryCheckpoint) node).getLocationIdentity();
+                    for (Iterator<FloatingReadNode> iter = currentState.iterator(); iter.hasNext();) {
+                        FloatingReadNode read = iter.next();
+                        FixedNode fixed = (FixedNode) node;
+                        if (identity == LocationNode.ANY_LOCATION || read.location().locationIdentity() == identity) {
+                            addPhantomReference(read, fixed);
+                        }
+                    }
+                }
+            }
+        }
+
+        public void addPhantomReference(FloatingReadNode read, FixedNode fixed) {
+            List<FixedNode> usageList = phantomUsages.get(read);
+            if (usageList == null) {
+                phantomUsages.put(read, usageList = new ArrayList<>());
+            }
+            usageList.add(fixed);
+            List<FloatingNode> inputList = phantomInputs.get(fixed);
+            if (inputList == null) {
+                phantomInputs.put(fixed, inputList = new ArrayList<>());
+            }
+            inputList.add(read);
+        }
+
+        @Override
+        protected HashSet<FloatingReadNode> merge(MergeNode merge, List<HashSet<FloatingReadNode>> states) {
+            HashSet<FloatingReadNode> state = new HashSet<>(states.get(0));
+            for (int i = 1; i < states.size(); i++) {
+                state.retainAll(states.get(i));
+            }
+            return state;
+        }
+
+        @Override
+        protected HashSet<FloatingReadNode> afterSplit(FixedNode node, HashSet<FloatingReadNode> oldState) {
+            return new HashSet<>(oldState);
+        }
+
+        @Override
+        protected List<HashSet<FloatingReadNode>> processLoop(Loop loop, HashSet<FloatingReadNode> state) {
+            LoopInfo<HashSet<FloatingReadNode>> info = ReentrantBlockIterator.processLoop(this, loop, new HashSet<>(state));
+
+            List<HashSet<FloatingReadNode>> loopEndStates = info.endStates;
+
+            // collect all reads that were killed in some branch within the loop
+            Set<FloatingReadNode> killedReads = new HashSet<>(state);
+            Set<FloatingReadNode> survivingReads = new HashSet<>(loopEndStates.get(0));
+            for (int i = 1; i < loopEndStates.size(); i++) {
+                survivingReads.retainAll(loopEndStates.get(i));
+            }
+            killedReads.removeAll(survivingReads);
+
+            // reads that were killed within the loop cannot be scheduled after the loop anyway
+            for (HashSet<FloatingReadNode> exitState : info.exitStates) {
+                exitState.removeAll(killedReads);
+            }
+            return info.exitStates;
+        }
+    }
 
     private ControlFlowGraph cfg;
     private NodeMap<Block> earliestCache;
@@ -42,6 +132,8 @@
      * Map from blocks to the nodes in each block.
      */
     private BlockMap<List<ScheduledNode>> blockToNodesMap;
+    private final Map<FloatingNode, List<FixedNode>> phantomUsages = new IdentityHashMap<>();
+    private final Map<FixedNode, List<FloatingNode>> phantomInputs = new IdentityHashMap<>();
 
     public SchedulePhase() {
         super("Schedule");
@@ -49,12 +141,26 @@
 
     @Override
     protected void run(StructuredGraph graph) {
+        SchedulingStrategy strategy = GraalOptions.OptScheduleOutOfLoops ? SchedulingStrategy.LATEST_OUT_OF_LOOPS : SchedulingStrategy.LATEST;
+
         cfg = ControlFlowGraph.compute(graph, true, true, true, false);
         earliestCache = graph.createNodeMap();
         blockToNodesMap = new BlockMap<>(cfg);
 
-        assignBlockToNodes(graph);
-        sortNodesWithinBlocks(graph);
+        if (GraalOptions.MemoryAwareScheduling && graph.getNodes(FloatingReadNode.class).isNotEmpty()) {
+
+            assignBlockToNodes(graph, SchedulingStrategy.EARLIEST);
+            sortNodesWithinBlocks(graph, SchedulingStrategy.EARLIEST);
+
+            MemoryScheduleClosure closure = new MemoryScheduleClosure();
+            ReentrantBlockIterator.apply(closure, getCFG().getStartBlock(), new HashSet<FloatingReadNode>(), null);
+
+            cfg.clearNodeToBlock();
+            blockToNodesMap = new BlockMap<>(cfg);
+        }
+
+        assignBlockToNodes(graph, strategy);
+        sortNodesWithinBlocks(graph, strategy);
     }
 
     /**
@@ -94,7 +200,7 @@
         return blockToNodesMap.get(block);
     }
 
-    private void assignBlockToNodes(StructuredGraph graph) {
+    private void assignBlockToNodes(StructuredGraph graph, SchedulingStrategy strategy) {
         for (Block block : cfg.getBlocks()) {
             List<ScheduledNode> nodes = new ArrayList<>();
             assert blockToNodesMap.get(block) == null;
@@ -106,7 +212,7 @@
 
         for (Node n : graph.getNodes()) {
             if (n instanceof ScheduledNode) {
-                assignBlockToNode((ScheduledNode) n);
+                assignBlockToNode((ScheduledNode) n, strategy);
             }
         }
     }
@@ -115,7 +221,7 @@
      * Assigns a block to the given node. This method expects that PhiNodes and FixedNodes are
      * already assigned to a block.
      */
-    private void assignBlockToNode(ScheduledNode node) {
+    private void assignBlockToNode(ScheduledNode node, SchedulingStrategy strategy) {
         assert !node.isDeleted();
 
         Block prevBlock = cfg.getNodeToBlock().get(node);
@@ -126,17 +232,26 @@
         // ControlFlowGraph.identifyBlocks
         assert !(node instanceof PhiNode) : node;
         assert !(node instanceof FixedNode) : node;
-        // if in CFG, schedule at the latest position possible in the outermost loop possible
-        Block latestBlock = latestBlock(node);
+
         Block block;
-        if (latestBlock == null) {
-            block = earliestBlock(node);
-        } else if (GraalOptions.OptScheduleOutOfLoops && !(node instanceof VirtualObjectNode)) {
-            Block earliestBlock = earliestBlock(node);
-            block = scheduleOutOfLoops(node, latestBlock, earliestBlock);
-            assert earliestBlock.dominates(block) : "Graph can not be scheduled : inconsistent for " + node + " (" + earliestBlock + " needs to dominate " + block + ")";
-        } else {
-            block = latestBlock;
+        switch (strategy) {
+            case EARLIEST:
+                block = earliestBlock(node);
+                break;
+            case LATEST:
+            case LATEST_OUT_OF_LOOPS:
+                block = latestBlock(node, strategy);
+                if (block == null) {
+                    block = earliestBlock(node);
+                } else if (strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS && !(node instanceof VirtualObjectNode)) {
+                    // schedule at the latest position possible in the outermost loop possible
+                    Block earliestBlock = earliestBlock(node);
+                    block = scheduleOutOfLoops(node, block, earliestBlock);
+                    assert earliestBlock.dominates(block) : "Graph can not be scheduled : inconsistent for " + node + " (" + earliestBlock + " needs to dominate " + block + ")";
+                }
+                break;
+            default:
+                throw new GraalInternalError("unknown scheduling strategy");
         }
         cfg.getNodeToBlock().set(node, block);
         blockToNodesMap.get(block).add(node);
@@ -145,17 +260,27 @@
     /**
      * 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
      */
-    private Block latestBlock(ScheduledNode node) {
+    private Block latestBlock(ScheduledNode node, SchedulingStrategy strategy) {
         CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(null);
         for (Node succ : node.successors().nonNull()) {
             assert cfg.getNodeToBlock().get(succ) != null;
             cdbc.apply(cfg.getNodeToBlock().get(succ));
         }
-        ensureScheduledUsages(node);
+        ensureScheduledUsages(node, strategy);
         for (Node usage : node.usages()) {
-            blocksForUsage(node, usage, cdbc);
+            blocksForUsage(node, usage, cdbc, strategy);
         }
+        List<FixedNode> usages = phantomUsages.get(node);
+        if (usages != null) {
+            for (FixedNode usage : usages) {
+                assert cfg.getNodeToBlock().get(usage) != null;
+                cdbc.apply(cfg.getNodeToBlock().get(usage));
+            }
+        }
+
         return cdbc.block;
     }
 
@@ -204,7 +329,12 @@
         assert node.predecessor() == null;
         for (Node input : node.inputs().nonNull()) {
             assert input instanceof ValueNode;
-            Block inputEarliest = earliestBlock(input);
+            Block inputEarliest;
+            if (input instanceof InvokeWithExceptionNode) {
+                inputEarliest = cfg.getNodeToBlock().get(((InvokeWithExceptionNode) input).next());
+            } else {
+                inputEarliest = earliestBlock(input);
+            }
             if (!dominators.get(inputEarliest.getId())) {
                 earliest = inputEarliest;
                 do {
@@ -242,7 +372,7 @@
      * @param usage the usage whose blocks need to be considered
      * @param closure the closure that will be called for each block
      */
-    private void blocksForUsage(ScheduledNode node, Node usage, BlockClosure closure) {
+    private void blocksForUsage(ScheduledNode node, Node usage, BlockClosure closure, SchedulingStrategy strategy) {
         assert !(node instanceof PhiNode);
 
         if (usage instanceof PhiNode) {
@@ -274,7 +404,7 @@
                 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.
-                    blocksForUsage(node, unscheduledUsage, closure);
+                    blocksForUsage(node, unscheduledUsage, closure, strategy);
                 } else if (unscheduledUsage instanceof MergeNode) {
                     // Only FrameStates can be connected to MergeNodes.
                     assert usage instanceof FrameState;
@@ -288,20 +418,20 @@
                     assert usage instanceof FrameState;
                     assert unscheduledUsage instanceof StateSplit;
                     // Otherwise: Put the input into the same block as the usage.
-                    assignBlockToNode((ScheduledNode) unscheduledUsage);
+                    assignBlockToNode((ScheduledNode) unscheduledUsage, strategy);
                     closure.apply(cfg.getNodeToBlock().get(unscheduledUsage));
                 }
             }
         } else {
             // All other types of usages: Put the input into the same block as the usage.
-            assignBlockToNode((ScheduledNode) usage);
+            assignBlockToNode((ScheduledNode) usage, strategy);
             closure.apply(cfg.getNodeToBlock().get(usage));
         }
     }
 
-    private void ensureScheduledUsages(Node node) {
+    private void ensureScheduledUsages(Node node, SchedulingStrategy strategy) {
         for (Node usage : node.usages().filter(ScheduledNode.class)) {
-            assignBlockToNode((ScheduledNode) usage);
+            assignBlockToNode((ScheduledNode) usage, strategy);
         }
         // now true usages are ready
     }
@@ -316,27 +446,43 @@
         return ControlFlowGraph.commonDominator(a, b);
     }
 
-    private void sortNodesWithinBlocks(StructuredGraph graph) {
+    private void sortNodesWithinBlocks(StructuredGraph graph, SchedulingStrategy strategy) {
         NodeBitMap visited = graph.createNodeBitMap();
         for (Block b : cfg.getBlocks()) {
-            sortNodesWithinBlock(b, visited);
+            sortNodesWithinBlock(b, visited, strategy);
         }
     }
 
+    private void sortNodesWithinBlock(Block b, NodeBitMap visited, SchedulingStrategy strategy) {
+        assert !visited.isMarked(b.getBeginNode()) && cfg.blockFor(b.getBeginNode()) == b;
+        assert !visited.isMarked(b.getEndNode()) && cfg.blockFor(b.getEndNode()) == b;
+
+        List<ScheduledNode> sortedInstructions;
+        switch (strategy) {
+            case EARLIEST:
+                sortedInstructions = sortNodesWithinBlockEarliest(b, visited);
+                break;
+            case LATEST:
+            case LATEST_OUT_OF_LOOPS:
+                sortedInstructions = sortNodesWithinBlockLatest(b, visited);
+                break;
+            default:
+                throw new GraalInternalError("unknown scheduling strategy");
+        }
+        blockToNodesMap.put(b, sortedInstructions);
+    }
+
     /**
      * 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 void sortNodesWithinBlock(Block b, NodeBitMap visited) {
+    private List<ScheduledNode> sortNodesWithinBlockLatest(Block b, NodeBitMap visited) {
         List<ScheduledNode> instructions = blockToNodesMap.get(b);
-        List<ScheduledNode> sortedInstructions = new ArrayList<>(instructions.size() + 2);
-
-        assert !visited.isMarked(b.getBeginNode()) && cfg.blockFor(b.getBeginNode()) == b;
-        assert !visited.isMarked(b.getEndNode()) && cfg.blockFor(b.getEndNode()) == b;
+        List<ScheduledNode> sortedInstructions = new ArrayList<>(blockToNodesMap.get(b).size() + 2);
 
         for (ScheduledNode i : instructions) {
-            addToSorting(b, i, sortedInstructions, visited);
+            addToLatestSorting(b, i, sortedInstructions, visited);
         }
 
         // Make sure that last node gets really last (i.e. when a frame state successor hangs off
@@ -363,25 +509,25 @@
                 sortedInstructions.add(b.getEndNode());
             }
         }
-        blockToNodesMap.put(b, sortedInstructions);
+        return sortedInstructions;
     }
 
-    private void addUnscheduledToSorting(Block b, VirtualState state, List<ScheduledNode> sortedInstructions, NodeBitMap visited) {
+    private void addUnscheduledToLatestSorting(Block b, VirtualState state, List<ScheduledNode> sortedInstructions, NodeBitMap visited) {
         if (state != null) {
             // UnscheduledNodes should never be marked as visited.
             assert !visited.isMarked(state);
 
             for (Node input : state.inputs()) {
                 if (input instanceof VirtualState) {
-                    addUnscheduledToSorting(b, (VirtualState) input, sortedInstructions, visited);
+                    addUnscheduledToLatestSorting(b, (VirtualState) input, sortedInstructions, visited);
                 } else {
-                    addToSorting(b, (ScheduledNode) input, sortedInstructions, visited);
+                    addToLatestSorting(b, (ScheduledNode) input, sortedInstructions, visited);
                 }
             }
         }
     }
 
-    private void addToSorting(Block b, ScheduledNode i, List<ScheduledNode> sortedInstructions, NodeBitMap visited) {
+    private void addToLatestSorting(Block b, ScheduledNode i, List<ScheduledNode> sortedInstructions, NodeBitMap visited) {
         if (i == null || visited.isMarked(i) || cfg.getNodeToBlock().get(i) != b || i instanceof PhiNode || i instanceof LocalNode) {
             return;
         }
@@ -396,17 +542,74 @@
                 assert state == null;
                 state = (FrameState) input;
             } else {
-                addToSorting(b, (ScheduledNode) input, sortedInstructions, visited);
+                addToLatestSorting(b, (ScheduledNode) input, sortedInstructions, visited);
+            }
+        }
+        List<FloatingNode> inputs = phantomInputs.get(i);
+        if (inputs != null) {
+            for (FloatingNode input : inputs) {
+                addToLatestSorting(b, input, sortedInstructions, visited);
             }
         }
 
-        addToSorting(b, (ScheduledNode) i.predecessor(), sortedInstructions, visited);
+        addToLatestSorting(b, (ScheduledNode) i.predecessor(), sortedInstructions, visited);
         visited.mark(i);
-        addUnscheduledToSorting(b, state, sortedInstructions, visited);
+        addUnscheduledToLatestSorting(b, state, sortedInstructions, visited);
         assert write == null || !visited.isMarked(write);
-        addToSorting(b, write, sortedInstructions, visited);
+        addToLatestSorting(b, write, sortedInstructions, visited);
 
         // Now predecessors and inputs are scheduled => we can add this node.
         sortedInstructions.add(i);
     }
+
+    /**
+     * Sorts the nodes within a block by adding the nodes to a list in a post-order iteration over
+     * all usages. The resulting list is reversed to create an earliest-possible scheduling of
+     * nodes.
+     */
+    private List<ScheduledNode> sortNodesWithinBlockEarliest(Block b, NodeBitMap visited) {
+        List<ScheduledNode> sortedInstructions = new ArrayList<>(blockToNodesMap.get(b).size() + 2);
+        addToEarliestSorting(b, b.getEndNode(), sortedInstructions, visited);
+        Collections.reverse(sortedInstructions);
+        return sortedInstructions;
+    }
+
+    private void addToEarliestSorting(Block b, ScheduledNode i, List<ScheduledNode> sortedInstructions, NodeBitMap visited) {
+        if (i == null || visited.isMarked(i) || cfg.getNodeToBlock().get(i) != b || i instanceof PhiNode || i instanceof LocalNode) {
+            return;
+        }
+
+        visited.mark(i);
+        for (Node usage : i.usages()) {
+            if (usage instanceof VirtualState) {
+                // only fixed nodes can have VirtualState -> no need to schedule them
+            } else {
+                if (i instanceof LoopExitNode && usage instanceof ValueProxyNode) {
+                    // value proxies should be scheduled before the loopexit, not after
+                } else {
+                    addToEarliestSorting(b, (ScheduledNode) usage, sortedInstructions, visited);
+                }
+            }
+        }
+
+        if (i instanceof BeginNode) {
+            ArrayList<ValueProxyNode> proxies = (i instanceof LoopExitNode) ? new ArrayList<ValueProxyNode>() : null;
+            for (ScheduledNode inBlock : blockToNodesMap.get(b)) {
+                if (!visited.isMarked(inBlock)) {
+                    if (inBlock instanceof ValueProxyNode) {
+                        proxies.add((ValueProxyNode) inBlock);
+                    } else {
+                        addToEarliestSorting(b, inBlock, sortedInstructions, visited);
+                    }
+                }
+            }
+            sortedInstructions.add(i);
+            if (proxies != null) {
+                sortedInstructions.addAll(proxies);
+            }
+        } else {
+            sortedInstructions.add(i);
+            addToEarliestSorting(b, (ScheduledNode) i.predecessor(), sortedInstructions, visited);
+        }
+    }
 }