# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1426200500 -3600
# Node ID e89ca1d8ab5a37f7e1df88b55c5bf279d24f1c45
# Parent  2fcc5ea8c1100ab2d9c424aab14f3b37b54254b5
Remove code of the old schedule algorithm.

diff -r 2fcc5ea8c110 -r e89ca1d8ab5a 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	Thu Mar 12 23:25:19 2015 +0100
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/GraalCompilerTest.java	Thu Mar 12 23:48:20 2015 +0100
@@ -305,7 +305,6 @@
 
     protected static String getCanonicalGraphString(StructuredGraph graph, boolean excludeVirtual, boolean checkConstants) {
         SchedulePhase schedule = new SchedulePhase(SchedulingStrategy.EARLIEST);
-        schedule.setScheduleConstants(true);
         schedule.apply(graph);
 
         NodeMap<Integer> canonicalId = graph.createNodeMap();
diff -r 2fcc5ea8c110 -r e89ca1d8ab5a graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Thu Mar 12 23:25:19 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Thu Mar 12 23:48:20 2015 +0100
@@ -269,7 +269,6 @@
             graph.maybeCompress();
 
             SchedulePhase schedule = new SchedulePhase();
-            schedule.setScheduleConstants(true);
             schedule.apply(graph);
             Debug.dump(schedule, "Final HIR schedule");
             return schedule;
@@ -284,7 +283,6 @@
             // Repeatedly run the LIR code generation pass to improve statistical profiling results.
             for (int i = 0; i < EmitLIRRepeatCount.getValue(); i++) {
                 SchedulePhase dummySchedule = new SchedulePhase();
-                dummySchedule.setScheduleConstants(true);
                 dummySchedule.apply(graph);
                 emitLIR(backend, target, dummySchedule, graph, stub, cc, registerConfig, lirSuites);
             }
diff -r 2fcc5ea8c110 -r e89ca1d8ab5a 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	Thu Mar 12 23:25:19 2015 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Thu Mar 12 23:48:20 2015 +0100
@@ -22,26 +22,19 @@
  */
 package com.oracle.graal.phases.schedule;
 
-import static com.oracle.graal.api.meta.LocationIdentity.*;
 import static com.oracle.graal.compiler.common.GraalOptions.*;
 import static com.oracle.graal.compiler.common.cfg.AbstractControlFlowGraph.*;
 
 import java.util.*;
 
 import com.oracle.graal.api.meta.*;
-import com.oracle.graal.compiler.common.*;
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.cfg.*;
 import com.oracle.graal.nodes.extended.*;
-import com.oracle.graal.nodes.spi.*;
-import com.oracle.graal.nodes.virtual.*;
 import com.oracle.graal.phases.*;
-import com.oracle.graal.phases.graph.*;
-import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
-import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo;
 
 public final class SchedulePhase extends Phase {
 
@@ -75,136 +68,7 @@
         LATEST_OUT_OF_LOOPS
     }
 
-    private class NewMemoryScheduleClosure extends BlockIteratorClosure<LocationSet> {
-        private Node excludeNode;
-        private Block upperBoundBlock;
-
-        public NewMemoryScheduleClosure(Node excludeNode, Block upperBoundBlock) {
-            this.excludeNode = excludeNode;
-            this.upperBoundBlock = upperBoundBlock;
-        }
-
-        public NewMemoryScheduleClosure() {
-            this(null, null);
-        }
-
-        @Override
-        protected LocationSet getInitialState() {
-            return cloneState(blockToKillSet.get(getCFG().getStartBlock()));
-        }
-
-        @Override
-        protected LocationSet processBlock(Block block, LocationSet currentState) {
-            assert block != null;
-            currentState.addAll(computeKillSet(block, block == upperBoundBlock ? excludeNode : null));
-            return currentState;
-        }
-
-        @Override
-        protected LocationSet merge(Block merge, List<LocationSet> states) {
-            assert merge.getBeginNode() instanceof AbstractMergeNode;
-
-            LocationSet initKillSet = new LocationSet();
-            for (LocationSet state : states) {
-                initKillSet.addAll(state);
-            }
-
-            return initKillSet;
-        }
-
-        @Override
-        protected LocationSet cloneState(LocationSet state) {
-            return new LocationSet(state);
-        }
-
-        @Override
-        protected List<LocationSet> processLoop(Loop<Block> loop, LocationSet state) {
-            LoopInfo<LocationSet> info = ReentrantBlockIterator.processLoop(this, loop, cloneState(state));
-
-            assert loop.getHeader().getBeginNode() instanceof LoopBeginNode;
-            LocationSet headerState = merge(loop.getHeader(), info.endStates);
-
-            // second iteration, for propagating information to loop exits
-            info = ReentrantBlockIterator.processLoop(this, loop, cloneState(headerState));
-
-            return info.exitStates;
-        }
-    }
-
-    /**
-     * gather all kill locations by iterating trough the nodes assigned to a block.
-     *
-     * assumptions: {@link MemoryCheckpoint MemoryCheckPoints} are {@link FixedNode FixedNodes}.
-     *
-     * @param block block to analyze
-     * @param excludeNode if null, compute normal set of kill locations. if != null, don't add kills
-     *            until we reach excludeNode.
-     * @return all killed locations
-     */
-    private LocationSet computeKillSet(Block block, Node excludeNode) {
-        // cache is only valid if we don't potentially exclude kills from the set
-        if (excludeNode == null) {
-            LocationSet cachedSet = blockToKillSet.get(block);
-            if (cachedSet != null) {
-                return cachedSet;
-            }
-        }
-
-        // add locations to excludedLocations until we reach the excluded node
-        boolean foundExcludeNode = excludeNode == null;
-
-        LocationSet set = new LocationSet();
-        LocationSet excludedLocations = new LocationSet();
-        if (block.getBeginNode() instanceof AbstractMergeNode) {
-            AbstractMergeNode mergeNode = (AbstractMergeNode) block.getBeginNode();
-            for (MemoryPhiNode phi : mergeNode.usages().filter(MemoryPhiNode.class)) {
-                if (foundExcludeNode) {
-                    set.add(phi.getLocationIdentity());
-                } else {
-                    excludedLocations.add(phi.getLocationIdentity());
-                    foundExcludeNode = phi == excludeNode;
-                }
-            }
-        }
-
-        AbstractBeginNode startNode = cfg.getStartBlock().getBeginNode();
-        assert startNode instanceof StartNode;
-
-        LocationSet accm = foundExcludeNode ? set : excludedLocations;
-        for (Node node : block.getNodes()) {
-            if (!foundExcludeNode && node == excludeNode) {
-                foundExcludeNode = true;
-            }
-            if (node != startNode) {
-                if (node instanceof MemoryCheckpoint.Single) {
-                    LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
-                    accm.add(identity);
-                } else if (node instanceof MemoryCheckpoint.Multi) {
-                    for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
-                        accm.add(identity);
-                    }
-                }
-                assert MemoryCheckpoint.TypeAssertion.correctType(node);
-            }
-
-            if (foundExcludeNode) {
-                accm = set;
-            }
-        }
-
-        // merge it for the cache entry
-        excludedLocations.addAll(set);
-        blockToKillSet.put(block, excludedLocations);
-
-        return set;
-    }
-
-    private LocationSet computeKillSet(Block block) {
-        return computeKillSet(block, null);
-    }
-
     private ControlFlowGraph cfg;
-    private NodeMap<Block> earliestCache;
 
     /**
      * Map from blocks to the nodes in each block.
@@ -212,7 +76,6 @@
     private BlockMap<List<Node>> blockToNodesMap;
     private BlockMap<LocationSet> blockToKillSet;
     private final SchedulingStrategy selectedStrategy;
-    private boolean scheduleConstants;
     private NodeMap<Block> nodeToBlockMap;
 
     public SchedulePhase() {
@@ -223,12 +86,6 @@
         this.selectedStrategy = strategy;
     }
 
-    public void setScheduleConstants(boolean value) {
-        scheduleConstants = value;
-    }
-
-    private static final boolean USE_NEW_STRATEGY = true;
-
     @Override
     protected void run(StructuredGraph graph) {
         // assert GraphOrder.assertNonCyclicGraph(graph);
@@ -240,7 +97,7 @@
             NodeBitMap visited = graph.createNodeBitMap();
             scheduleEarliestIterative(cfg, blockToNodesMap, nodeToBlockMap, visited, graph);
             return;
-        } else if (USE_NEW_STRATEGY) {
+        } else {
             boolean isOutOfLoops = selectedStrategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS;
             if (selectedStrategy == SchedulingStrategy.LATEST || isOutOfLoops) {
                 NodeMap<Block> currentNodeMap = graph.createNodeMap();
@@ -324,20 +181,6 @@
                 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");
         }
     }
 
@@ -825,23 +668,12 @@
         }
     }
 
-    private Block blockForMemoryNode(MemoryNode memory) {
-        MemoryNode current = memory;
-        while (current instanceof MemoryProxy) {
-            current = ((MemoryProxy) current).getOriginalMemoryNode();
-        }
-        Block b = cfg.getNodeToBlock().get(current.asNode());
-        assert b != null : "all lastAccess locations should have a block assignment from CFG";
-        return b;
+    @Override
+    public String toString() {
+        return printScheduleHelper("Schedule");
     }
 
-    private void printSchedule(String desc) {
-        if (Debug.isLogEnabled()) {
-            printScheduleHelper(desc);
-        }
-    }
-
-    private void printScheduleHelper(String desc) {
+    private String printScheduleHelper(String desc) {
         Formatter buf = new Formatter();
         buf.format("=== %s / %s / %s ===%n", getCFG().getStartBlock().getBeginNode().graph(), selectedStrategy, desc);
         for (Block b : getCFG().getBlocks()) {
@@ -870,7 +702,7 @@
             }
         }
         buf.format("%n");
-        Debug.log("%s", buf);
+        return buf.toString();
     }
 
     private static void printNode(Node n) {
@@ -915,657 +747,4 @@
     public List<Node> nodesFor(Block block) {
         return blockToNodesMap.get(block);
     }
-
-    private void assignBlockToNodes(StructuredGraph graph, SchedulingStrategy strategy) {
-        for (Block block : cfg.getBlocks()) {
-            List<Node> nodes = new ArrayList<>();
-            if (blockToNodesMap.get(block) != null) {
-                throw new SchedulingError();
-            }
-            blockToNodesMap.put(block, nodes);
-            for (FixedNode node : block.getNodes()) {
-                nodes.add(node);
-            }
-        }
-
-        for (Node n : graph.getNodes()) {
-            if (n instanceof ValueNode) {
-                assignBlockToNode((ValueNode) n, strategy);
-            }
-        }
-    }
-
-    /**
-     * Assigns a block to the given node. This method expects that PhiNodes and FixedNodes are
-     * already assigned to a block.
-     */
-    private void assignBlockToNode(ValueNode node, SchedulingStrategy strategy) {
-        assert !node.isDeleted();
-
-        if (cfg.getNodeToBlock().containsKey(node)) {
-            return;
-        }
-        if (!scheduleConstants && node instanceof ConstantNode) {
-            return;
-        }
-        if (node instanceof VirtualObjectNode) {
-            return;
-        }
-        // PhiNodes, ProxyNodes and FixedNodes should already have been placed in blocks by
-        // ControlFlowGraph.identifyBlocks
-        if (node instanceof PhiNode || node instanceof ProxyNode || node instanceof FixedNode) {
-            throw new SchedulingError("%s should already have been placed in a block", node);
-        }
-
-        Block earliestBlock = earliestBlock(node);
-        Block block = null;
-        Block latest = null;
-        switch (strategy) {
-            case EARLIEST:
-                block = earliestBlock;
-                break;
-            case LATEST:
-            case LATEST_OUT_OF_LOOPS:
-                boolean scheduleRead = node instanceof FloatingReadNode && !((FloatingReadNode) node).location().getLocationIdentity().isImmutable();
-                if (scheduleRead) {
-                    FloatingReadNode read = (FloatingReadNode) node;
-                    block = optimalBlock(read, strategy);
-                    Debug.log("schedule for %s: %s", read, block);
-                    assert dominates(earliestBlock, block) : String.format("%s (%s) cannot be scheduled before earliest schedule (%s). location: %s", read, block, earliestBlock,
-                                    read.getLocationIdentity());
-                } else {
-                    block = latestBlock(node, strategy, earliestBlock);
-                }
-                if (block == null) {
-                    // handle nodes without usages
-                    block = earliestBlock;
-                } else if (strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS && !(node instanceof VirtualObjectNode)) {
-                    // schedule at the latest position possible in the outermost loop possible
-                    latest = block;
-                    block = scheduleOutOfLoops(node, block, earliestBlock);
-                }
-
-                assert assertReadSchedule(node, earliestBlock, block, latest, scheduleRead);
-                break;
-            default:
-                throw new GraalInternalError("unknown scheduling strategy");
-        }
-        if (!dominates(earliestBlock, block)) {
-            throw new SchedulingError("%s: Graph cannot be scheduled : inconsistent for %s, %d usages, (%s needs to dominate %s)", node.graph(), node, node.getUsageCount(), earliestBlock, block);
-        }
-        cfg.getNodeToBlock().set(node, block);
-        blockToNodesMap.get(block).add(node);
-    }
-
-    private boolean assertReadSchedule(ValueNode node, Block earliestBlock, Block block, Block latest, boolean scheduleRead) {
-        if (scheduleRead) {
-            FloatingReadNode read = (FloatingReadNode) node;
-            MemoryNode lastLocationAccess = read.getLastLocationAccess();
-            Block upperBound = blockForMemoryNode(lastLocationAccess);
-            assert dominates(upperBound, block) : String.format("out of loop movement voilated memory semantics for %s (location %s). moved to %s but upper bound is %s (earliest: %s, latest: %s)",
-                            read, read.getLocationIdentity(), block, upperBound, earliestBlock, latest);
-        }
-        return true;
-    }
-
-    /**
-     * this method tries to find the "optimal" schedule for a read, by pushing it down towards its
-     * latest schedule starting by the earliest schedule. By doing this, it takes care of memory
-     * dependencies using kill sets.
-     *
-     * In terms of domination relation, it looks like this:
-     *
-     * <pre>
-     *    U      upperbound block, defined by last access location of the floating read
-     *    &and;
-     *    E      earliest block
-     *    &and;
-     *    O      optimal block, first block that contains a kill of the read's location
-     *    &and;
-     *    L      latest block
-     * </pre>
-     *
-     * i.e. <code>upperbound `dom` earliest `dom` optimal `dom` latest</code>.
-     *
-     */
-    private Block optimalBlock(FloatingReadNode n, SchedulingStrategy strategy) {
-        LocationIdentity locid = n.location().getLocationIdentity();
-        assert !locid.isImmutable();
-
-        Block upperBoundBlock = blockForMemoryNode(n.getLastLocationAccess());
-        Block earliestBlock = earliestBlock(n);
-        assert dominates(upperBoundBlock, earliestBlock) : "upper bound (" + upperBoundBlock + ") should dominate earliest (" + earliestBlock + ")";
-
-        Block latestBlock = latestBlock(n, strategy, earliestBlock);
-        assert latestBlock != null && dominates(earliestBlock, latestBlock) : "earliest (" + earliestBlock + ") should dominate latest block (" + latestBlock + ")";
-
-        Debug.log("processing %s (accessing %s): latest %s, earliest %s, upper bound %s (%s)", n, locid, latestBlock, earliestBlock, upperBoundBlock, n.getLastLocationAccess());
-        if (earliestBlock == latestBlock) {
-            // read is fixed to this block, nothing to schedule
-            return latestBlock;
-        }
-
-        Deque<Block> path = computePathInDominatorTree(earliestBlock, latestBlock);
-        Debug.log("|path| is %d: %s", path.size(), path);
-
-        // follow path, start at earliest schedule
-        while (path.size() > 0) {
-            Block currentBlock = path.pop();
-            Block dominatedBlock = path.size() == 0 ? null : path.peek();
-            if (dominatedBlock != null && !currentBlock.getSuccessors().contains(dominatedBlock)) {
-                // the dominated block is not a successor -> we have a split
-                assert dominatedBlock.getBeginNode() instanceof AbstractMergeNode;
-
-                NewMemoryScheduleClosure closure = null;
-                if (currentBlock == upperBoundBlock) {
-                    assert earliestBlock == upperBoundBlock;
-                    // don't treat lastLocationAccess node as a kill for this read.
-                    closure = new NewMemoryScheduleClosure(ValueNodeUtil.asNode(n.getLastLocationAccess()), upperBoundBlock);
-                } else {
-                    closure = new NewMemoryScheduleClosure();
-                }
-                Map<FixedNode, LocationSet> states;
-                states = ReentrantBlockIterator.apply(closure, currentBlock, new LocationSet(), block -> block == dominatedBlock);
-
-                LocationSet mergeState = states.get(dominatedBlock.getBeginNode());
-                if (mergeState.contains(locid)) {
-                    // location got killed somewhere in the branches,
-                    // thus we've to move the read above it
-                    return currentBlock;
-                }
-            } else {
-                if (currentBlock == upperBoundBlock) {
-                    assert earliestBlock == upperBoundBlock;
-                    LocationSet ks = computeKillSet(upperBoundBlock, ValueNodeUtil.asNode(n.getLastLocationAccess()));
-                    if (ks.contains(locid)) {
-                        return upperBoundBlock;
-                    }
-                } else if (dominatedBlock == null || computeKillSet(currentBlock).contains(locid)) {
-                    return currentBlock;
-                }
-            }
-        }
-        throw new SchedulingError("should have found a block for " + n);
-    }
-
-    /**
-     * compute path in dominator tree from earliest schedule to latest schedule.
-     *
-     * @return the order of the stack is such as the first element is the earliest schedule.
-     */
-    private static Deque<Block> computePathInDominatorTree(Block earliestBlock, Block latestBlock) {
-        Deque<Block> path = new LinkedList<>();
-        Block currentBlock = latestBlock;
-        while (currentBlock != null && dominates(earliestBlock, currentBlock)) {
-            path.push(currentBlock);
-            currentBlock = currentBlock.getDominator();
-        }
-        assert path.peek() == earliestBlock;
-        return path;
-    }
-
-    /**
-     * Calculates the last block that the given node could be scheduled in, i.e., the common
-     * dominator of all usages. To do so all usages are also assigned to blocks.
-     *
-     * @param strategy
-     * @param earliestBlock
-     */
-    private Block latestBlock(ValueNode node, SchedulingStrategy strategy, Block earliestBlock) {
-        Block block = null;
-        for (Node usage : node.usages()) {
-            block = blocksForUsage(node, usage, block, earliestBlock, strategy);
-            if (block == earliestBlock) {
-                break;
-            }
-        }
-
-        assert assertLatestBlockResult(node, block);
-        return block;
-    }
-
-    private boolean assertLatestBlockResult(ValueNode node, Block block) throws SchedulingError {
-        if (block != null && !dominates(earliestBlock(node), block)) {
-            throw new SchedulingError("failed to find correct latest schedule for %s. cdbc: %s, earliest: %s", node, block, earliestBlock(node));
-        }
-        return true;
-    }
-
-    /**
-     * Determines the earliest block in which the given node can be scheduled.
-     */
-    private Block earliestBlock(Node node) {
-        Block earliest = cfg.getNodeToBlock().get(node);
-        if (earliest != null) {
-            return earliest;
-        }
-        earliest = earliestCache.get(node);
-        if (earliest != null) {
-            return earliest;
-        }
-        return earliestBlockHelper(node, earliest);
-    }
-
-    private Block earliestBlockHelper(Node node, Block earliestStart) throws SchedulingError {
-        /*
-         * All inputs must be in a dominating block, otherwise the graph cannot be scheduled. This
-         * implies that the inputs' blocks have a total ordering via their dominance relation. So in
-         * order to find the earliest block placement for this node we need to find the input block
-         * that is dominated by all other input blocks.
-         */
-        Block earliest = earliestStart;
-
-        if (node.predecessor() != null) {
-            throw new SchedulingError();
-        }
-        for (Node input : node.inputs()) {
-            if (input != null) {
-                assert input instanceof ValueNode;
-                Block inputEarliest;
-                if (input instanceof InvokeWithExceptionNode) {
-                    inputEarliest = cfg.getNodeToBlock().get(((InvokeWithExceptionNode) input).next());
-                } else {
-                    inputEarliest = earliestBlock(input);
-                }
-                if (earliest == null || earliest.getDominatorDepth() < inputEarliest.getDominatorDepth()) {
-                    earliest = inputEarliest;
-                }
-            }
-        }
-        if (earliest == null) {
-            earliest = cfg.getStartBlock();
-        }
-        earliestCache.set(node, earliest);
-        return earliest;
-    }
-
-    /**
-     * Schedules a node out of loop based on its earliest schedule. Note that this movement is only
-     * valid if it's done for <b>every</b> other node in the schedule, otherwise this movement is
-     * not valid.
-     *
-     * @param n Node to schedule
-     * @param latestBlock latest possible schedule for {@code n}
-     * @param earliest earliest possible schedule for {@code n}
-     * @return block schedule for {@code n} which is not inside a loop (if possible)
-     */
-    private static Block scheduleOutOfLoops(Node n, Block latestBlock, Block earliest) {
-        if (latestBlock == null) {
-            throw new SchedulingError("no latest : %s", n);
-        }
-        Block cur = latestBlock;
-        Block result = latestBlock;
-        Loop<?> earliestLoop = earliest.getLoop();
-        while (true) {
-            Loop<?> curLoop = cur.getLoop();
-            if (curLoop == earliestLoop) {
-                return result;
-            } else {
-                Block dom = cur.getDominator();
-                if (dom.getLoopDepth() < result.getLoopDepth()) {
-                    result = dom;
-                }
-                cur = dom;
-            }
-        }
-    }
-
-    /**
-     * Passes all blocks that a specific usage of a node is in to a given closure. This is more
-     * complex than just taking the usage's block because of of PhiNodes and FrameStates.
-     *
-     * @param node the node that needs to be scheduled
-     * @param usage the usage whose blocks need to be considered
-     * @param earliestBlock
-     */
-    private Block blocksForUsage(ValueNode node, Node usage, Block startCurrentBlock, Block earliestBlock, SchedulingStrategy strategy) {
-        assert !(node instanceof PhiNode);
-        Block currentBlock = startCurrentBlock;
-        if (usage instanceof PhiNode) {
-            // An input to a PhiNode is used at the end of the predecessor block that corresponds to
-            // the PhiNode input.
-            // One PhiNode can use an input multiple times, the closure will be called for each
-            // usage.
-            PhiNode phi = (PhiNode) usage;
-            AbstractMergeNode merge = phi.merge();
-            Block mergeBlock = cfg.getNodeToBlock().get(merge);
-            for (int i = 0; i < phi.valueCount(); ++i) {
-                if (phi.valueAt(i) == node) {
-                    currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, mergeBlock.getPredecessors().get(i));
-                    if (currentBlock == earliestBlock) {
-                        break;
-                    }
-                }
-            }
-        } else if (usage instanceof VirtualState) {
-            // The following logic does not work if node is a PhiNode, but this method is never
-            // called for PhiNodes.
-            for (Node unscheduledUsage : usage.usages()) {
-                if (unscheduledUsage instanceof VirtualState) {
-                    // If a FrameState is an outer FrameState this method behaves as if the inner
-                    // FrameState was the actual usage, by recursing.
-                    currentBlock = blocksForUsage(node, unscheduledUsage, currentBlock, earliestBlock, strategy);
-                } else if (unscheduledUsage instanceof AbstractBeginNode) {
-                    // Only FrameStates can be connected to BeginNodes.
-                    if (!(usage instanceof FrameState)) {
-                        throw new SchedulingError(usage.toString());
-                    }
-                    if (unscheduledUsage instanceof StartNode) {
-                        currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(unscheduledUsage));
-                    } else {
-                        // If a FrameState belongs to a BeginNode then it's inputs will be placed at
-                        // the common dominator of all EndNodes.
-                        for (Node pred : unscheduledUsage.cfgPredecessors()) {
-                            currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(pred));
-                        }
-                    }
-                } else {
-                    // For the time being, FrameStates can only be connected to NodeWithState.
-                    if (!(usage instanceof FrameState)) {
-                        throw new SchedulingError(usage.toString());
-                    }
-                    if (!(unscheduledUsage instanceof NodeWithState)) {
-                        throw new SchedulingError(unscheduledUsage.toString());
-                    }
-                    // Otherwise: Put the input into the same block as the usage.
-                    assignBlockToNode((ValueNode) unscheduledUsage, strategy);
-                    currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(unscheduledUsage));
-                }
-                if (currentBlock == earliestBlock) {
-                    break;
-                }
-            }
-        } else {
-            // All other types of usages: Put the input into the same block as the usage.
-            assignBlockToNode((ValueNode) usage, strategy);
-            currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, cfg.getNodeToBlock().get(usage));
-        }
-        return currentBlock;
-    }
-
-    private void sortNodesWithinBlocks(StructuredGraph graph, SchedulingStrategy strategy) {
-        NodeBitMap visited = graph.createNodeBitMap();
-        NodeBitMap beforeLastLocation = graph.createNodeBitMap();
-        for (Block b : cfg.getBlocks()) {
-            sortNodesWithinBlock(b, visited, beforeLastLocation, strategy);
-            assert noDuplicatedNodesInBlock(b) : "duplicated nodes in " + b;
-        }
-    }
-
-    private boolean noDuplicatedNodesInBlock(Block b) {
-        List<Node> list = blockToNodesMap.get(b);
-        Set<Node> hashset = Node.newSet(list);
-        return list.size() == hashset.size();
-    }
-
-    private void sortNodesWithinBlock(Block b, NodeBitMap visited, NodeBitMap beforeLastLocation, SchedulingStrategy strategy) {
-        if (visited.isMarked(b.getBeginNode()) || cfg.blockFor(b.getBeginNode()) != b) {
-            throw new SchedulingError();
-        }
-        if (visited.isMarked(b.getEndNode()) || cfg.blockFor(b.getEndNode()) != b) {
-            throw new SchedulingError();
-        }
-
-        List<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: " +
-                        filterSchedulableNodes(blockToNodesMap.get(b)) + " vs. " + removeProxies(sortedInstructions);
-        assert sameOrderForFixedNodes(blockToNodesMap.get(b), sortedInstructions) : "fixed nodes in sorted block are not in the same order";
-        blockToNodesMap.put(b, sortedInstructions);
-    }
-
-    private static List<Node> removeProxies(List<Node> list) {
-        List<Node> result = new ArrayList<>();
-        for (Node n : list) {
-            if (!(n instanceof ProxyNode)) {
-                result.add(n);
-            }
-        }
-        return result;
-    }
-
-    private static List<Node> filterSchedulableNodes(List<Node> list) {
-        List<Node> result = new ArrayList<>();
-        for (Node n : list) {
-            if (!(n instanceof PhiNode)) {
-                result.add(n);
-            }
-        }
-        return result;
-    }
-
-    private static boolean sameOrderForFixedNodes(List<Node> fixed, List<Node> sorted) {
-        Iterator<Node> fixedIterator = fixed.iterator();
-        Iterator<Node> sortedIterator = sorted.iterator();
-
-        while (sortedIterator.hasNext()) {
-            Node sortedCurrent = sortedIterator.next();
-            if (sortedCurrent instanceof FixedNode) {
-                if (!(fixedIterator.hasNext() && fixedIterator.next() == sortedCurrent)) {
-                    return false;
-                }
-            }
-        }
-
-        while (fixedIterator.hasNext()) {
-            if (fixedIterator.next() instanceof FixedNode) {
-                return false;
-            }
-        }
-
-        return true;
-    }
-
-    private static class SortState {
-        private Block block;
-        private NodeBitMap visited;
-        private NodeBitMap beforeLastLocation;
-        private List<Node> sortedInstructions;
-        private List<FloatingReadNode> reads;
-
-        SortState(Block block, NodeBitMap visited, NodeBitMap beforeLastLocation, List<Node> sortedInstructions) {
-            this.block = block;
-            this.visited = visited;
-            this.beforeLastLocation = beforeLastLocation;
-            this.sortedInstructions = sortedInstructions;
-            this.reads = null;
-        }
-
-        public Block currentBlock() {
-            return block;
-        }
-
-        void markVisited(Node n) {
-            visited.mark(n);
-        }
-
-        boolean isVisited(Node n) {
-            return visited.isMarked(n);
-        }
-
-        void markBeforeLastLocation(FloatingReadNode n) {
-            beforeLastLocation.mark(n);
-        }
-
-        void clearBeforeLastLocation(FloatingReadNode frn) {
-            beforeLastLocation.clear(frn);
-        }
-
-        boolean isBeforeLastLocation(FloatingReadNode n) {
-            return beforeLastLocation.isMarked(n);
-        }
-
-        void addRead(FloatingReadNode n) {
-            if (reads == null) {
-                reads = new ArrayList<>();
-            }
-            reads.add(n);
-        }
-
-        int readsSize() {
-            if (reads == null) {
-                return 0;
-            }
-            return reads.size();
-        }
-
-        void removeRead(Node i) {
-            assert reads != null;
-            reads.remove(i);
-        }
-
-        List<FloatingReadNode> readsSnapshot() {
-            assert reads != null;
-            return new ArrayList<>(reads);
-        }
-
-        List<Node> getSortedInstructions() {
-            return sortedInstructions;
-        }
-
-        boolean containsInstruction(Node i) {
-            return sortedInstructions.contains(i);
-        }
-
-        void addInstruction(Node i) {
-            sortedInstructions.add(i);
-        }
-    }
-
-    /**
-     * Sorts the nodes within a block by adding the nodes to a list in a post-order iteration over
-     * all inputs. This means that a node is added to the list after all its inputs have been
-     * processed.
-     */
-    private List<Node> sortNodesWithinBlockLatest(Block b, NodeBitMap visited, NodeBitMap beforeLastLocation) {
-        SortState state = new SortState(b, visited, beforeLastLocation, new ArrayList<>(blockToNodesMap.get(b).size() + 2));
-        List<Node> instructions = blockToNodesMap.get(b);
-
-        for (Node i : instructions) {
-            if (i instanceof FloatingReadNode) {
-                FloatingReadNode frn = (FloatingReadNode) i;
-                if (!frn.location().getLocationIdentity().isImmutable()) {
-                    state.addRead(frn);
-                    if (nodesFor(b).contains(frn.getLastLocationAccess())) {
-                        assert !state.isBeforeLastLocation(frn);
-                        state.markBeforeLastLocation(frn);
-                    }
-                }
-            }
-        }
-
-        for (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<Node> sortedInstructions = state.getSortedInstructions();
-        Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1);
-        if (lastSorted != b.getEndNode()) {
-            sortedInstructions.remove(b.getEndNode());
-            sortedInstructions.add(b.getEndNode());
-        }
-        return sortedInstructions;
-    }
-
-    private void processKillLocation(Node node, LocationIdentity identity, SortState state) {
-        for (FloatingReadNode frn : state.readsSnapshot()) {
-            LocationIdentity readLocation = frn.location().getLocationIdentity();
-            assert !readLocation.isImmutable();
-            if (frn.getLastLocationAccess() == node) {
-                assert identity.equals(ANY_LOCATION) || readLocation.equals(identity) || node instanceof MemoryCheckpoint.Multi : "location doesn't match: " + readLocation + ", " + identity;
-                state.clearBeforeLastLocation(frn);
-            } else if (!state.isBeforeLastLocation(frn) && (readLocation.equals(identity) || (node != getCFG().graph.start() && ANY_LOCATION.equals(identity)))) {
-                state.removeRead(frn);
-                addToLatestSorting(frn, state);
-            }
-        }
-    }
-
-    private void addUnscheduledToLatestSorting(VirtualState state, SortState sortState) {
-        if (state != null) {
-            // UnscheduledNodes should never be marked as visited.
-            if (sortState.isVisited(state)) {
-                throw new SchedulingError();
-            }
-
-            for (Node input : state.inputs()) {
-                if (input instanceof VirtualState) {
-                    addUnscheduledToLatestSorting((VirtualState) input, sortState);
-                } else {
-                    addToLatestSorting(input, sortState);
-                }
-            }
-        }
-    }
-
-    private void addToLatestSorting(Node i, SortState state) {
-        if (i == null || state.isVisited(i) || cfg.getNodeToBlock().get(i) != state.currentBlock() || i instanceof PhiNode) {
-            return;
-        }
-
-        if (i instanceof ProxyNode) {
-            ProxyNode proxyNode = (ProxyNode) i;
-            addToLatestSorting(proxyNode.value(), state);
-            return;
-        }
-
-        if (i instanceof LoopExitNode) {
-            LoopExitNode loopExitNode = (LoopExitNode) i;
-            for (ProxyNode proxy : loopExitNode.proxies()) {
-                addToLatestSorting(proxy, state);
-            }
-        }
-
-        addToLatestSortingHelper(i, state);
-    }
-
-    private void addToLatestSortingHelper(Node i, SortState state) {
-        FrameState stateAfter = null;
-        if (i instanceof StateSplit) {
-            stateAfter = ((StateSplit) i).stateAfter();
-        }
-
-        addInputsToLatestSorting(i, state, stateAfter);
-
-        if (state.readsSize() != 0) {
-            if (i instanceof MemoryCheckpoint.Single) {
-                LocationIdentity identity = ((MemoryCheckpoint.Single) i).getLocationIdentity();
-                processKillLocation(i, identity, state);
-            } else if (i instanceof MemoryCheckpoint.Multi) {
-                for (LocationIdentity identity : ((MemoryCheckpoint.Multi) i).getLocationIdentities()) {
-                    processKillLocation(i, identity, state);
-                }
-            }
-            assert MemoryCheckpoint.TypeAssertion.correctType(i);
-        }
-
-        addToLatestSorting(i.predecessor(), state);
-        state.markVisited(i);
-        addUnscheduledToLatestSorting(stateAfter, state);
-
-        // Now predecessors and inputs are scheduled => we can add this node.
-        if (!state.containsInstruction(i)) {
-            state.addInstruction(i);
-        }
-
-        if (state.readsSize() != 0 && i instanceof FloatingReadNode) {
-            state.removeRead(i);
-        }
-    }
-
-    private void addInputsToLatestSorting(Node i, SortState state, FrameState stateAfter) {
-        for (Node input : i.inputs()) {
-            if (input instanceof FrameState) {
-                if (input != stateAfter) {
-                    addUnscheduledToLatestSorting((FrameState) input, state);
-                }
-            } else {
-                addToLatestSorting(input, state);
-            }
-        }
-    }
 }