--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java	Wed Jun 13 15:11:19 2012 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java	Wed Jun 13 19:09:14 2012 +0200
@@ -381,7 +381,7 @@
             lastState = fs;
         }
 
-        List<Node> nodes = lir.nodesFor(block);
+        List<ScheduledNode> nodes = lir.nodesFor(block);
         for (int i = 0; i < nodes.size(); i++) {
             Node instr = nodes.get(i);
 

--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/schedule/SchedulePhase.java	Wed Jun 13 15:11:19 2012 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/schedule/SchedulePhase.java	Wed Jun 13 19:09:14 2012 +0200
@@ -41,7 +41,7 @@
     /**
      * Map from blocks to the nodes in each block.
      */
-    private BlockMap<List<Node>> blockToNodesMap;
+    private BlockMap<List<ScheduledNode>> blockToNodesMap;
 
     public SchedulePhase() {
         super("Schedule");
@@ -57,17 +57,20 @@
         sortNodesWithinBlocks(graph);
     }
 
+    /**
+     * Sets {@link ScheduledNode#scheduledNext} on all scheduled nodes in all blocks using the scheduling built by @link {@link #run(StructuredGraph)}.
+     * This method should thus only be called when run has been successfully executed.
+     */
     public void scheduleGraph() {
+        assert blockToNodesMap != null : "cannot set scheduledNext before run has been executed";
         for (Block block : cfg.getBlocks()) {
-            List<Node> nodeList = blockToNodesMap.get(block);
+            List<ScheduledNode> nodeList = blockToNodesMap.get(block);
             ScheduledNode last = null;
-            for (Node node : nodeList) {
-                if (!(node instanceof FrameState)) {
-                    if (last != null) {
-                        last.setScheduledNext((ScheduledNode) node);
-                    }
-                    last = (ScheduledNode) node;
+            for (ScheduledNode node : nodeList) {
+                if (last != null) {
+                    last.setScheduledNext(node);
                 }
+                last = node;
             }
         }
     }
@@ -79,79 +82,86 @@
     /**
      * Gets the map from each block to the nodes in the block.
      */
-    public BlockMap<List<Node>> getBlockToNodesMap() {
+    public BlockMap<List<ScheduledNode>> getBlockToNodesMap() {
         return blockToNodesMap;
     }
 
     /**
      * Gets the nodes in a given block.
      */
-    public List<Node> nodesFor(Block block) {
+    public List<ScheduledNode> nodesFor(Block block) {
         return blockToNodesMap.get(block);
     }
 
     private void assignBlockToNodes(StructuredGraph graph) {
         for (Block block : cfg.getBlocks()) {
-            List<Node> nodes = new ArrayList<>();
+            List<ScheduledNode> nodes = new ArrayList<>();
             assert blockToNodesMap.get(block) == null;
             blockToNodesMap.put(block, nodes);
-            for (Node node : block.getNodes()) {
+            for (FixedNode node : block.getNodes()) {
                 nodes.add(node);
             }
         }
 
         for (Node n : graph.getNodes()) {
-            assignBlockToNode(n);
+            if (n instanceof ScheduledNode) {
+                assignBlockToNode((ScheduledNode) n);
+            }
         }
     }
 
-    private void assignBlockToNode(Node n) {
-        if (n == null) {
-            return;
-        }
+    /**
+     * Assigns a block to the given node. This method expects that PhiNodes and FixedNodes are already assigned to a
+     * block, since they should already have been placed by {@link ControlFlowGraph#identifyBlocks()}.
+     * This method will also try to
+     */
+    private void assignBlockToNode(ScheduledNode node) {
+        assert !node.isDeleted();
 
-        assert !n.isDeleted();
-
-        Block prevBlock = cfg.getNodeToBlock().get(n);
+        Block prevBlock = cfg.getNodeToBlock().get(node);
         if (prevBlock != null) {
             return;
         }
-        assert !(n instanceof PhiNode) : n;
-        assert !(n instanceof MergeNode);
+        // PhiNodes and FixedNodes should already have been placed in blocks by 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(n);
+        Block latestBlock = latestBlock(node);
         Block block;
         if (latestBlock == null) {
-            block = earliestBlock(n);
-        } else if (GraalOptions.ScheduleOutOfLoops && !(n instanceof VirtualObjectFieldNode) && !(n instanceof VirtualObjectNode)) {
-            Block earliestBlock = earliestBlock(n);
-            block = scheduleOutOfLoops(n, latestBlock, earliestBlock);
-            assert earliestBlock.dominates(block) : "Graph can not be scheduled : inconsistent for " + n + " (" + earliestBlock + " needs to dominate " + block + ")";
+            block = earliestBlock(node);
+        } else if (GraalOptions.ScheduleOutOfLoops && !(node instanceof VirtualObjectFieldNode) && !(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;
         }
-        cfg.getNodeToBlock().set(n, block);
-        blockToNodesMap.get(block).add(n);
+        cfg.getNodeToBlock().set(node, block);
+        blockToNodesMap.get(block).add(node);
     }
 
-    private Block latestBlock(Node n) {
-        Block block = null;
-        for (Node succ : n.successors()) {
-            if (succ == null) {
-                continue;
-            }
-            assignBlockToNode(succ);
-            block = getCommonDominator(block, cfg.getNodeToBlock().get(succ));
+    /**
+     * 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.
+     */
+    private Block latestBlock(ScheduledNode node) {
+        CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(null);
+        for (Node succ : node.successors().nonNull()) {
+            assert cfg.getNodeToBlock().get(succ) != null;
+            cdbc.apply(cfg.getNodeToBlock().get(succ));
         }
-        ensureScheduledUsages(n);
-        CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(block);
-        for (Node usage : n.usages()) {
-            blocksForUsage(n, usage, cdbc);
+        ensureScheduledUsages(node);
+        for (Node usage : node.usages()) {
+            blocksForUsage(node, usage, cdbc);
         }
         return cdbc.block;
     }
 
-    private class CommonDominatorBlockClosure implements BlockClosure {
+    /**
+     * A closure that will calculate the common dominator of all blocks passed to its {@link #apply(Block)} method.
+     */
+    private static class CommonDominatorBlockClosure implements BlockClosure {
         public Block block;
         public CommonDominatorBlockClosure(Block block) {
             this.block = block;
@@ -162,42 +172,45 @@
         }
     }
 
-    private Block earliestBlock(Node n) {
-        Block earliest = cfg.getNodeToBlock().get(n);
+    /**
+     * 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(n);
+        earliest = earliestCache.get(node);
         if (earliest != null) {
             return earliest;
         }
-        BitSet bits = new BitSet(cfg.getBlocks().length);
-        ArrayList<Node> before = new ArrayList<>();
-        if (n.predecessor() != null) {
-            before.add(n.predecessor());
-        }
-        for (Node input : n.inputs()) {
-            before.add(input);
-        }
-        for (Node pred : before) {
-            if (pred == null) {
-                continue;
-            }
-            Block b = earliestBlock(pred);
-            if (!bits.get(b.getId())) {
-                earliest = b;
+        /*
+         * 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.
+         *
+         * While iterating over the inputs a set of dominator blocks of the current earliest placement is maintained.
+         * When the block of an input is not within this set, it becomes the current earliest placement and the list of
+         * dominator blocks is updated.
+         */
+        BitSet dominators = new BitSet(cfg.getBlocks().length);
+
+        assert node.predecessor() == null;
+        for (Node input : node.inputs().nonNull()) {
+            assert input instanceof ValueNode;
+            Block inputEarliest = earliestBlock(input);
+            if (!dominators.get(inputEarliest.getId())) {
+                earliest = inputEarliest;
                 do {
-                    bits.set(b.getId());
-                    b = b.getDominator();
-                } while(b != null && !bits.get(b.getId()));
+                    dominators.set(inputEarliest.getId());
+                    inputEarliest = inputEarliest.getDominator();
+                } while(inputEarliest != null && !dominators.get(inputEarliest.getId()));
             }
         }
         if (earliest == null) {
-            Block start = cfg.getNodeToBlock().get(((StructuredGraph) n.graph()).start());
-            assert start != null;
-            return start;
+            earliest = cfg.getStartBlock();
         }
-        earliestCache.set(n, earliest);
+        earliestCache.set(node, earliest);
         return earliest;
     }
 
@@ -224,8 +237,9 @@
      * @param usage the usage whose blocks need to be considered
      * @param closure the closure that will be called for each block
      */
-    private void blocksForUsage(Node node, Node usage, BlockClosure closure) {
+    private void blocksForUsage(ScheduledNode node, Node usage, BlockClosure closure) {
         assert !(node instanceof PhiNode);
+
         if (usage instanceof PhiNode) {
             // An input to a PhiNode is used at the end of the predecessor block that corresponds to the PhiNode input.
             // One PhiNode can use an input multiple times, the closure will be called for each usage.
@@ -246,26 +260,34 @@
                     closure.apply(mergeBlock.getPredecessors().get(i));
                 }
             }
-        } else if (usage instanceof FrameState && ((FrameState) usage).block() != null && !(node instanceof FrameState)) {
-            // If a FrameState belongs to a MergeNode then it's inputs will be placed at the common dominator of all EndNodes.
-            // BUT only if the input is neither a PhiNode (this method is never called for PhiNodes) nor a FrameState.
-            // A FrameState input is an outer FrameState. They should be placed into the same block as the usage, which is handled by the else.
-            MergeNode merge = ((FrameState) usage).block();
-            Block block = null;
-            for (Node pred : merge.cfgPredecessors()) {
-                block = getCommonDominator(block, cfg.getNodeToBlock().get(pred));
+        } else if (usage instanceof FrameState) {
+            // The following logic does not work if node is a PhiNode, but this method is never called for PhiNodes.
+            for (Node frameStateUsage : usage.usages()) {
+                if (frameStateUsage instanceof FrameState) {
+                    // If a FrameState is an outer FrameState this method behaves as if the inner FrameState was the actual usage, by recursing.
+                    blocksForUsage(node, frameStateUsage, closure);
+                } else if (frameStateUsage instanceof MergeNode) {
+                    // If a FrameState belongs to a MergeNode then it's inputs will be placed at the common dominator of all EndNodes.
+                    for (Node pred : frameStateUsage.cfgPredecessors()) {
+                        closure.apply(cfg.getNodeToBlock().get(pred));
+                    }
+                } else {
+                    // Otherwise: Put the input into the same block as the usage.
+                    assert frameStateUsage instanceof StateSplit;
+                    assignBlockToNode((ScheduledNode) frameStateUsage);
+                    closure.apply(cfg.getNodeToBlock().get(frameStateUsage));
+                }
             }
-            closure.apply(block);
         } else {
-            // All other types of usages: Just put the input into the same block as the usage.
-            assignBlockToNode(usage);
+            // All other types of usages: Put the input into the same block as the usage.
+            assignBlockToNode((ScheduledNode) usage);
             closure.apply(cfg.getNodeToBlock().get(usage));
         }
     }
 
     private void ensureScheduledUsages(Node node) {
-        for (Node usage : node.usages().snapshot()) {
-            assignBlockToNode(usage);
+        for (Node usage : node.usages().filter(ScheduledNode.class)) {
+            assignBlockToNode((ScheduledNode) usage);
         }
         // now true usages are ready
     }
@@ -281,21 +303,25 @@
     }
 
     private void sortNodesWithinBlocks(StructuredGraph graph) {
-        NodeBitMap map = graph.createNodeBitMap();
+        NodeBitMap visited = graph.createNodeBitMap();
         for (Block b : cfg.getBlocks()) {
-            sortNodesWithinBlocks(b, map);
+            sortNodesWithinBlock(b, visited);
         }
     }
 
-    private void sortNodesWithinBlocks(Block b, NodeBitMap map) {
-        List<Node> instructions = blockToNodesMap.get(b);
-        List<Node> sortedInstructions = new ArrayList<>(instructions.size() + 2);
+    /**
+     * 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) {
+        List<ScheduledNode> instructions = blockToNodesMap.get(b);
+        List<ScheduledNode> sortedInstructions = new ArrayList<>(instructions.size() + 2);
 
-        assert !map.isMarked(b.getBeginNode()) && cfg.blockFor(b.getBeginNode()) == b;
-        assert !map.isMarked(b.getEndNode()) && cfg.blockFor(b.getEndNode()) == b;
+        assert !visited.isMarked(b.getBeginNode()) && cfg.blockFor(b.getBeginNode()) == b;
+        assert !visited.isMarked(b.getEndNode()) && cfg.blockFor(b.getEndNode()) == b;
 
-        for (Node i : instructions) {
-            addToSorting(b, i, sortedInstructions, map);
+        for (ScheduledNode i : instructions) {
+            addToSorting(b, i, sortedInstructions, visited);
         }
 
         // Make sure that last node gets really last (i.e. when a frame state successor hangs off it).
@@ -325,32 +351,44 @@
         blockToNodesMap.put(b, sortedInstructions);
     }
 
-    private void addToSorting(Block b, Node i, List<Node> sortedInstructions, NodeBitMap map) {
-        if (i == null || map.isMarked(i) || cfg.getNodeToBlock().get(i) != b || i instanceof PhiNode || i instanceof LocalNode) {
+    private void addFrameStateToSorting(Block b, FrameState state, List<ScheduledNode> sortedInstructions, NodeBitMap visited) {
+        if (state != null) {
+            assert !visited.isMarked(state);
+
+            for (Node input : state.inputs()) {
+                if (input instanceof FrameState) {
+                    addFrameStateToSorting(b, (FrameState) input, sortedInstructions, visited);
+                } else {
+                    addToSorting(b, (ScheduledNode) input, sortedInstructions, visited);
+                }
+            }
+        }
+    }
+
+    private void addToSorting(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;
         }
 
         FrameState state = null;
-        WriteNode writeNode = null;
+        WriteNode write = null;
         for (Node input : i.inputs()) {
-            if (input instanceof WriteNode && !map.isMarked(input) && cfg.getNodeToBlock().get(input) == b) {
-                writeNode = (WriteNode) input;
+            if (input instanceof WriteNode && !visited.isMarked(input) && cfg.getNodeToBlock().get(input) == b) {
+                assert write == null;
+                write = (WriteNode) input;
             } else if (input instanceof FrameState) {
+                assert state == null;
                 state = (FrameState) input;
             } else {
-                addToSorting(b, input, sortedInstructions, map);
+                addToSorting(b, (ScheduledNode) input, sortedInstructions, visited);
             }
         }
 
-        if (i.predecessor() != null) {
-            addToSorting(b, i.predecessor(), sortedInstructions, map);
-        }
-
-        map.mark(i);
-
-        addToSorting(b, state, sortedInstructions, map);
-        assert writeNode == null || !map.isMarked(writeNode);
-        addToSorting(b, writeNode, sortedInstructions, map);
+        addToSorting(b, (ScheduledNode) i.predecessor(), sortedInstructions, visited);
+        visited.mark(i);
+        addFrameStateToSorting(b, state, sortedInstructions, visited);
+        assert write == null || !visited.isMarked(write);
+        addToSorting(b, write, sortedInstructions, visited);
 
         // Now predecessors and inputs are scheduled => we can add this node.
         sortedInstructions.add(i);

--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java	Wed Jun 13 15:11:19 2012 +0200
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java	Wed Jun 13 19:09:14 2012 +0200
@@ -30,7 +30,6 @@
 
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.debug.*;
-import com.oracle.graal.graph.*;
 import com.oracle.graal.graph.Node.Verbosity;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.PhiNode.PhiType;

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java	Wed Jun 13 15:11:19 2012 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java	Wed Jun 13 19:09:14 2012 +0200
@@ -29,6 +29,7 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.lir.asm.*;
 import com.oracle.graal.lir.cfg.*;
+import com.oracle.graal.nodes.*;
 
 /**
  * This class implements the overall container for the LIR graph
@@ -42,7 +43,7 @@
      * The nodes for the blocks.
      * TODO: This should go away, we want all nodes connected with a next-pointer.
      */
-    private final BlockMap<List<Node>> blockToNodesMap;
+    private final BlockMap<List<ScheduledNode>> blockToNodesMap;
 
     /**
      * The linear-scan ordered list of blocks.
@@ -87,7 +88,7 @@
      * @param numLoops number of loops
      * @param compilation the compilation
      */
-    public LIR(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodesMap, List<Block> linearScanOrder, List<Block> codeEmittingOrder) {
+    public LIR(ControlFlowGraph cfg, BlockMap<List<ScheduledNode>> blockToNodesMap, List<Block> linearScanOrder, List<Block> codeEmittingOrder) {
         this.cfg = cfg;
         this.blockToNodesMap = blockToNodesMap;
         this.codeEmittingOrder = codeEmittingOrder;
@@ -99,7 +100,7 @@
     /**
      * Gets the nodes in a given block.
      */
-    public List<Node> nodesFor(Block block) {
+    public List<ScheduledNode> nodesFor(Block block) {
         return blockToNodesMap.get(block);
     }
 

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/Block.java	Wed Jun 13 15:11:19 2012 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/Block.java	Wed Jun 13 19:09:14 2012 +0200
@@ -24,7 +24,6 @@
 
 import java.util.*;
 
-import com.oracle.graal.graph.*;
 import com.oracle.graal.lir.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.java.*;
@@ -33,7 +32,7 @@
     protected int id;
 
     protected BeginNode beginNode;
-    protected Node endNode;
+    protected FixedNode endNode;
     protected Loop loop;
     protected double probability;
 
@@ -62,7 +61,7 @@
         return beginNode;
     }
 
-    public Node getEndNode() {
+    public FixedNode getEndNode() {
         return endNode;
     }
 
@@ -122,8 +121,8 @@
         return postdominator;
     }
 
-    private class NodeIterator implements Iterator<Node> {
-        private Node cur;
+    private class NodeIterator implements Iterator<FixedNode> {
+        private FixedNode cur;
 
         public NodeIterator() {
             cur = getBeginNode();
@@ -135,8 +134,8 @@
         }
 
         @Override
-        public Node next() {
-            Node result = cur;
+        public FixedNode next() {
+            FixedNode result = cur;
             if (cur == getEndNode()) {
                 cur = null;
             } else {
@@ -152,10 +151,10 @@
         }
     }
 
-    public Iterable<Node> getNodes() {
-        return new Iterable<Node>() {
+    public Iterable<FixedNode> getNodes() {
+        return new Iterable<FixedNode>() {
             @Override
-            public Iterator<Node> iterator() {
+            public Iterator<FixedNode> iterator() {
                 return new NodeIterator();
             }
         };

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/ControlFlowGraph.java	Wed Jun 13 15:11:19 2012 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/cfg/ControlFlowGraph.java	Wed Jun 13 19:09:14 2012 +0200
@@ -118,9 +118,9 @@
 
                 block.beginNode = (BeginNode) node;
                 Node cur = node;
+                Node last;
                 do {
                     assert !cur.isDeleted();
-                    block.endNode = cur;
 
                     assert nodeToBlock.get(cur) == null;
                     nodeToBlock.set(cur, block);
@@ -137,15 +137,11 @@
                         }
                     }
 
-                    Node next = null;
-                    for (Node sux : cur.successors()) {
-                        if (sux != null && !(sux instanceof BeginNode)) {
-                            assert next == null;
-                            next = sux;
-                        }
-                    }
-                    cur = next;
-                } while (cur != null);
+                    last = cur;
+                    cur = cur.successors().first();
+                } while (cur != null && !(cur instanceof BeginNode));
+
+                block.endNode = (FixedNode) last;
             }
         }
 

--- a/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/GraphScheduleTest.java	Wed Jun 13 15:11:19 2012 +0200
+++ b/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/GraphScheduleTest.java	Wed Jun 13 19:09:14 2012 +0200
@@ -40,7 +40,7 @@
         Block aBlock = nodeToBlock.get(a);
 
         if (bBlock == aBlock) {
-            List<Node> instructions = ibp.nodesFor(bBlock);
+            List<ScheduledNode> instructions = ibp.nodesFor(bBlock);
             Assert.assertTrue(instructions.indexOf(b) > instructions.indexOf(a));
         } else {
             Block block = bBlock;