# HG changeset patch
# User Thomas Wuerthinger <thomas@wuerthinger.net>
# Date 1307638768 -7200
# Node ID 41318fcb6b5694dac8184e5c42dd30fff2684725
# Parent  cc4b538852e3ab0e73686f616797caa40f738dfd
Added two algorithms for identifying Java-level blocks.

diff -r cc4b538852e3 -r 41318fcb6b56 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java	Thu Jun 09 17:34:10 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java	Thu Jun 09 18:59:28 2011 +0200
@@ -112,9 +112,9 @@
     public void print(Graph graph, String title, boolean shortNames) {
         stream.printf(" <graph name='%s'>%n", escape(title));
         noBlockNodes.clear();
-        Schedule schedule = null;
+        IdentifyBlocksPhase schedule = null;
         try {
-            schedule = new Schedule();
+            schedule = new IdentifyBlocksPhase(true);
             schedule.apply(graph);
         } catch (Throwable t) {
             // nothing to do here...
diff -r cc4b538852e3 -r 41318fcb6b56 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java	Thu Jun 09 17:34:10 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java	Thu Jun 09 18:59:28 2011 +0200
@@ -91,9 +91,11 @@
             new DeadCodeEliminationPhase().apply(compilation.graph);
         }
 
+        new LoweringPhase().apply(graph);
+
         new SplitCriticalEdgesPhase().apply(graph);
 
-        Schedule schedule = new Schedule();
+        IdentifyBlocksPhase schedule = new IdentifyBlocksPhase(true);
         schedule.apply(graph);
 
 
diff -r cc4b538852e3 -r 41318fcb6b56 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java	Thu Jun 09 17:34:10 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java	Thu Jun 09 18:59:28 2011 +0200
@@ -30,7 +30,7 @@
  * The {@code Phi} instruction represents the merging of dataflow
  * in the instruction graph. It refers to a join block and a variable.
  */
-public final class Phi extends FixedNode {
+public final class Phi extends FloatingNode {
 
     private static final int DEFAULT_MAX_VALUES = 2;
 
diff -r cc4b538852e3 -r 41318fcb6b56 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java	Thu Jun 09 17:34:10 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java	Thu Jun 09 18:59:28 2011 +0200
@@ -1262,7 +1262,7 @@
             traceInstruction(bci, opcode, blockStart);
             processBytecode(bci, opcode);
 
-            if (Schedule.isBlockEnd(lastInstr) || lastInstr.next() != null) {
+            if (IdentifyBlocksPhase.isBlockEnd(lastInstr) || lastInstr.next() != null) {
                 break;
             }
 
diff -r cc4b538852e3 -r 41318fcb6b56 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoweringPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoweringPhase.java	Thu Jun 09 17:34:10 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoweringPhase.java	Thu Jun 09 18:59:28 2011 +0200
@@ -25,6 +25,7 @@
 import java.util.*;
 
 import com.oracle.max.graal.compiler.*;
+import com.oracle.max.graal.compiler.debug.*;
 import com.oracle.max.graal.compiler.ir.*;
 import com.oracle.max.graal.compiler.schedule.*;
 import com.oracle.max.graal.graph.*;
@@ -32,54 +33,100 @@
 public class LoweringPhase extends Phase {
     @Override
     protected void run(Graph graph) {
+        IdentifyBlocksPhase s = new IdentifyBlocksPhase(false);
+        s.apply(graph);
+
+//        for (Block b : s.getBlocks()) {
+//            TTY.println("Java block for block " + b.blockID() + " is " + b.javaBlock().blockID());
+//        }
+
         NodeMap<Node> javaBlockNodes = graph.createNodeMap();
+        NodeMap<Node> dominators = graph.createNodeMap();
         for (Node n : graph.getNodes()) {
-            if (n instanceof FixedNode) {
-                LoweringOp op = n.lookup(LoweringOp.class);
-                if (op != null) {
-                    Node javaBlockNode = getJavaBlockNode(javaBlockNodes, n);
-                }
+            if (IdentifyBlocksPhase.isFixed(n)) {
+                //LoweringOp op = n.lookup(LoweringOp.class);
+                //if (op != null) {
+                    Node javaBlockNode = getJavaBlockNode(javaBlockNodes, dominators, n);
+
+                    //TTY.println("Java block node for " + n.id() + " is " + ((javaBlockNode == null) ? "null" : javaBlockNode.id()));
+                //}
             }
 
         }
     }
 
-    private Node getJavaBlockNode(NodeMap<Node> javaBlockNodes, Node n) {
-        assert n instanceof FixedNode;
+    private Node getJavaBlockNode(NodeMap<Node> javaBlockNodes, NodeMap<Node> dominators, final Node n) {
+        assert IdentifyBlocksPhase.isFixed(n);
+        if (n == n.graph().start()) {
+            return null;
+        }
+
         if (javaBlockNodes.get(n) == null) {
 
             Node truePred = null;
             int count = 0;
             for (Node pred : n.predecessors()) {
-                if (pred instanceof FixedNode) {
+                if (pred instanceof FixedNode || pred == n.graph().start()) {
                     truePred = pred;
                     count++;
                 }
             }
 
-            assert count > 0;
+            assert count > 0 : n + "; " + IdentifyBlocksPhase.isFixed(n);
             if (count == 1) {
-                if (Schedule.trueSuccessorCount(truePred) == 1) {
-                    javaBlockNodes.set(n, getJavaBlockNode(javaBlockNodes, truePred));
+                if (IdentifyBlocksPhase.trueSuccessorCount(truePred) == 1) {
+                    javaBlockNodes.set(n, getJavaBlockNode(javaBlockNodes, dominators, truePred));
                 } else {
-                    // Single predecessor is a split => we are our own Java block node.
-                    javaBlockNodes.set(n, n);
+                    // Single predecessor is a split => this is our Java block node.
+                    javaBlockNodes.set(n, truePred);
                 }
             } else {
                 Node dominator = null;
                 for (Node pred : n.predecessors()) {
-                    if (pred instanceof FixedNode) {
-                       dominator = getCommonDominator(javaBlockNodes, dominator, pred);
+                    if (IdentifyBlocksPhase.isFixed(pred)) {
+                       dominator = getCommonDominator(javaBlockNodes, dominators, dominator, pred);
                     }
                 }
+
+                final Node finalDominator = dominator;
+                final List<Node> visitedNodesList = new ArrayList<Node>();
+                NodeBitMap visitedNodes = NodeIterator.iterate(EdgeType.PREDECESSORS, n, null, new NodeVisitor() {
+                    @Override
+                    public boolean visit(Node curNode) {
+                        if((curNode instanceof FixedNode) || finalDominator != curNode) {
+                            visitedNodesList.add(curNode);
+                            return true;
+                        }
+                        return false;
+                    }
+                });
+
+                visitedNodes.mark(finalDominator);
+                visitedNodesList.add(finalDominator);
+
+                Node result = getJavaBlockNode(javaBlockNodes, dominators, finalDominator);
+                L1: for (Node curNode : visitedNodesList) {
+                    if (curNode != n) {
+                        for (Node succ : curNode.successors()) {
+                            if (succ instanceof FixedNode && !visitedNodes.isMarked(succ)) {
+                                result = n;
+                                break L1;
+                            }
+                        }
+                    }
+                }
+
+                if (result != finalDominator) {
+                    dominators.set(n, finalDominator);
+                }
+                javaBlockNodes.set(n, result);
             }
         }
 
-        assert Schedule.truePredecessorCount(javaBlockNodes.get(n)) == 1;
         return javaBlockNodes.get(n);
     }
 
-    private Node getCommonDominator(NodeMap<Node> javaBlockNodes, Node a, Node b) {
+    private Node getCommonDominator(NodeMap<Node> javaBlockNodes, NodeMap<Node> dominators, Node a, Node b) {
         if (a == null) {
             return b;
         }
@@ -88,7 +135,30 @@
             return a;
         }
 
-        Node cur = getJavaBlockNode(javaBlockNodes, a);
+        NodeBitMap visitedNodes = a.graph().createNodeBitMap();
+        Node cur = a;
+        while (cur != null) {
+            visitedNodes.mark(cur);
+            cur = getDominator(javaBlockNodes, dominators, cur);
+        }
+
+        cur = b;
+        while (cur != null) {
+            if (visitedNodes.isMarked(cur)) {
+                return cur;
+            }
+            cur = getDominator(javaBlockNodes, dominators, cur);
+        }
+
+        throw new IllegalStateException("no common dominator between " + a + " and " + b);
+    }
+
+    private Node getDominator(NodeMap<Node> javaBlockNodes, NodeMap<Node> dominators, Node cur) {
+        Node n = getJavaBlockNode(javaBlockNodes, dominators, cur);
+        if (dominators.get(cur) != null) {
+            return dominators.get(cur);
+        }
+        return n;
     }
 
     public interface LoweringOp extends Op {
diff -r cc4b538852e3 -r 41318fcb6b56 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/SplitCriticalEdgesPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/SplitCriticalEdgesPhase.java	Thu Jun 09 17:34:10 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/SplitCriticalEdgesPhase.java	Thu Jun 09 18:59:28 2011 +0200
@@ -36,10 +36,10 @@
         List<Node> nodes = graph.getNodes();
         for (int i = 0; i < nodes.size(); ++i) {
             Node n = nodes.get(i);
-            if (Schedule.trueSuccessorCount(n) > 1) {
+            if (IdentifyBlocksPhase.trueSuccessorCount(n) > 1) {
                 for (int j = 0; j < n.successors().size(); ++j) {
                     Node succ = n.successors().get(j);
-                    if (Schedule.truePredecessorCount(succ) > 1) {
+                    if (IdentifyBlocksPhase.truePredecessorCount(succ) > 1) {
                         Anchor a = new Anchor(graph);
                         a.successors().setAndClear(1, n, j);
                         n.successors().set(j, a);
diff -r cc4b538852e3 -r 41318fcb6b56 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java	Thu Jun 09 17:34:10 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java	Thu Jun 09 18:59:28 2011 +0200
@@ -35,6 +35,7 @@
     private final List<Block> predecessors = new ArrayList<Block>();
     private List<Node> instructions = new ArrayList<Node>();
     private Block dominator;
+    private Block javaBlock;
     private final List<Block> dominators = new ArrayList<Block>();
 
     private Node firstNode;
@@ -48,6 +49,14 @@
         this.firstNode = node;
     }
 
+    public Block javaBlock() {
+        return javaBlock;
+    }
+
+    public void setJavaBlock(Block javaBlock) {
+        this.javaBlock = javaBlock;
+    }
+
     public Node lastNode() {
         return lastNode;
     }
diff -r cc4b538852e3 -r 41318fcb6b56 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java	Thu Jun 09 18:59:28 2011 +0200
@@ -0,0 +1,530 @@
+/*
+ * Copyright (c) 2011, 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.max.graal.compiler.schedule;
+
+import java.util.*;
+
+import com.oracle.max.graal.compiler.debug.*;
+import com.oracle.max.graal.compiler.ir.*;
+import com.oracle.max.graal.compiler.phases.*;
+import com.oracle.max.graal.compiler.value.*;
+import com.oracle.max.graal.graph.*;
+import com.sun.cri.ci.*;
+
+
+public class IdentifyBlocksPhase extends Phase {
+    private final List<Block> blocks = new ArrayList<Block>();
+    private NodeMap<Block> nodeToBlock;
+    private Graph graph;
+    private boolean scheduleAllNodes;
+
+    public IdentifyBlocksPhase(boolean scheduleAllNodes) {
+        super(scheduleAllNodes ? "FullSchedule" : "PartSchedule");
+        this.scheduleAllNodes = scheduleAllNodes;
+    }
+
+
+    @Override
+    protected void run(Graph graph) {
+        this.graph = graph;
+        nodeToBlock = graph.createNodeMap();
+        identifyBlocks();
+    }
+
+    public List<Block> getBlocks() {
+        return Collections.unmodifiableList(blocks);
+    }
+
+    public NodeMap<Block> getNodeToBlock() {
+        return nodeToBlock;
+    }
+
+    private Block createBlock() {
+        Block b = new Block(blocks.size());
+        blocks.add(b);
+        return b;
+    }
+
+    private Block assignBlock(Node n) {
+        Block curBlock = nodeToBlock.get(n);
+        if (curBlock == null) {
+            curBlock = createBlock();
+            return assignBlock(n, curBlock);
+        }
+        return curBlock;
+    }
+
+
+    private Block assignBlock(Node n, Block b) {
+        assert nodeToBlock.get(n) == null;
+        nodeToBlock.set(n, b);
+        if (b.firstNode() == null) {
+            b.setFirstNode(n);
+            b.setLastNode(n);
+        } else {
+            if (b.lastNode() != null) {
+                b.getInstructions().add(b.lastNode());
+            }
+            b.setLastNode(n);
+        }
+        b.setLastNode(n);
+        return b;
+    }
+
+    public static boolean isFixed(Node n) {
+        return n != null && ((n instanceof FixedNode) || n == n.graph().start());
+    }
+
+    public static boolean isBlockEnd(Node n) {
+        return trueSuccessorCount(n) > 1 || n instanceof Anchor || n instanceof Return || n instanceof Unwind;
+    }
+
+    private void identifyBlocks() {
+        // Identify blocks.
+        final ArrayList<Node> blockBeginNodes = new ArrayList<Node>();
+        NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), null, new NodeVisitor() {
+            @Override
+            public boolean visit(Node n) {
+                if (!isFixed(n)) {
+                    return false;
+                }
+
+                if (n instanceof LoopBegin) {
+                    // a LoopBegin is always a merge
+                    assignBlock(n);
+                    blockBeginNodes.add(n);
+                    return true;
+                }
+
+                Node singlePred = null;
+                for (Node pred : n.predecessors()) {
+                    if (isFixed(pred)) {
+                        if (singlePred == null) {
+                            singlePred = pred;
+                        } else {
+                            // We have more than one predecessor => we are a merge block.
+                            assignBlock(n);
+                            blockBeginNodes.add(n);
+                            return true;
+                        }
+                    }
+                }
+
+                if (singlePred == null) {
+                    // We have no predecessor => we are the start block.
+                    assignBlock(n);
+                    blockBeginNodes.add(n);
+                } else {
+                    // We have a single predecessor => check its successor count.
+                    if (isBlockEnd(singlePred)) {
+                        assignBlock(n);
+                        blockBeginNodes.add(n);
+                    } else {
+                        assignBlock(n, nodeToBlock.get(singlePred));
+                    }
+                }
+                return true;
+            }}
+        );
+
+        // Connect blocks.
+        for (Node n : blockBeginNodes) {
+            Block block = nodeToBlock.get(n);
+            for (Node pred : n.predecessors()) {
+                if (isFixed(pred)) {
+                    Block predBlock = nodeToBlock.get(pred);
+                    predBlock.addSuccessor(block);
+                }
+            }
+
+            if (n instanceof Merge) {
+                for (Node usage : n.usages()) {
+                    if (usage instanceof Phi) {
+                        nodeToBlock.set(usage, block);
+                    }
+                }
+            }
+        }
+
+        for (Node n : graph.getNodes()) {
+            if (n instanceof FrameState) {
+                FrameState f = (FrameState) n;
+                if (f.predecessors().size() == 1) {
+                    Block predBlock = nodeToBlock.get(f.predecessors().get(0));
+                    assert predBlock != null;
+                    nodeToBlock.set(f, predBlock);
+                    predBlock.getInstructions().add(f);
+                } else {
+                    assert f.predecessors().size() == 0;
+                }
+            }
+        }
+
+        computeDominators();
+
+
+        if (scheduleAllNodes) {
+
+            // Add successors of loop end nodes. Makes the graph cyclic.
+            for (Node n : blockBeginNodes) {
+                Block block = nodeToBlock.get(n);
+                if (n instanceof LoopBegin) {
+                    LoopBegin loopBegin = (LoopBegin) n;
+                    nodeToBlock.get(loopBegin.loopEnd()).addSuccessor(block);
+                }
+            }
+
+            assignLatestPossibleBlockToNodes();
+            sortNodesWithinBlocks();
+        } else {
+            computeJavaBlocks();
+        }
+
+        //print();
+    }
+
+    private void computeJavaBlocks() {
+
+        for (Block b : blocks) {
+            computeJavaBlock(b);
+        }
+    }
+
+    private Block computeJavaBlock(Block b) {
+        if (b.javaBlock() == null) {
+            if (b.getPredecessors().size() == 0) {
+                b.setJavaBlock(b);
+            } else if (b.getPredecessors().size() == 1) {
+                Block pred = b.getPredecessors().get(0);
+                if (pred.getSuccessors().size() > 1) {
+                    b.setJavaBlock(b);
+                } else {
+                    b.setJavaBlock(computeJavaBlock(pred));
+                }
+            } else {
+                Block dominatorBlock = b.getPredecessors().get(0);
+                for (int i=1; i<b.getPredecessors().size(); ++i) {
+                    dominatorBlock = getCommonDominator(dominatorBlock, b.getPredecessors().get(i));
+                }
+                CiBitMap blockMap = new CiBitMap(blocks.size());
+                markPredecessors(b, dominatorBlock, blockMap);
+
+                Block result = dominatorBlock;
+                L1: for (Block curBlock : blocks) {
+                    if (curBlock != b && blockMap.get(curBlock.blockID())) {
+                        for (Block succ : curBlock.getSuccessors()) {
+                            if (!blockMap.get(succ.blockID())) {
+                                result = b;
+                                break L1;
+                            }
+                        }
+                    }
+                }
+                b.setJavaBlock(result);
+            }
+        }
+        return b.javaBlock();
+    }
+
+    private void markPredecessors(Block b, Block stopBlock, CiBitMap blockMap) {
+        if (blockMap.get(b.blockID())) {
+            return;
+        }
+        blockMap.set(b.blockID());
+        if (b != stopBlock) {
+            for (Block pred : b.getPredecessors()) {
+                markPredecessors(pred, stopBlock, blockMap);
+            }
+        }
+    }
+
+    private void assignLatestPossibleBlockToNodes() {
+        for (Node n : graph.getNodes()) {
+            assignLatestPossibleBlockToNode(n);
+        }
+    }
+
+    private Block assignLatestPossibleBlockToNode(Node n) {
+        if (n == null) {
+            return null;
+        }
+
+        Block prevBlock = nodeToBlock.get(n);
+        if (prevBlock != null) {
+            return prevBlock;
+        }
+
+        Block block = null;
+        for (Node succ : n.successors()) {
+            block = getCommonDominator(block, assignLatestPossibleBlockToNode(succ));
+        }
+        for (Node usage : n.usages()) {
+            if (usage instanceof Phi) {
+                Phi phi = (Phi) usage;
+                Merge merge = phi.merge();
+                Block mergeBlock = nodeToBlock.get(merge);
+                assert mergeBlock != null : "no block for merge " + merge.id();
+                for (int i = 0; i < phi.valueCount(); ++i) {
+                    if (phi.valueAt(i) == n) {
+                        if (mergeBlock.getPredecessors().size() == 0) {
+                            TTY.println(merge.toString());
+                            TTY.println(phi.toString());
+                            TTY.println(merge.predecessors().toString());
+                            TTY.println("value count: " + phi.valueCount());
+                        }
+                        block = getCommonDominator(block, mergeBlock.getPredecessors().get(i));
+                    }
+                }
+            } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) {
+                Merge merge = ((FrameState) usage).block();
+                for (Node pred : merge.predecessors()) {
+                    if (isFixed(pred)) {
+                        block = getCommonDominator(block, nodeToBlock.get(pred));
+                    }
+                }
+            } else {
+                block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage));
+            }
+        }
+
+        nodeToBlock.set(n, block);
+        if (block != null) {
+            block.getInstructions().add(n);
+        }
+        return block;
+    }
+
+    private Block getCommonDominator(Block a, Block b) {
+        if (a == null) {
+            return b;
+        }
+        if (b == null) {
+            return a;
+        }
+        return commonDominator(a, b);
+    }
+
+    private void sortNodesWithinBlocks() {
+        NodeBitMap map = graph.createNodeBitMap();
+        for (Block b : blocks) {
+            sortNodesWithinBlocks(b, map);
+        }
+    }
+
+    private void sortNodesWithinBlocks(Block b, NodeBitMap map) {
+        List<Node> instructions = b.getInstructions();
+        List<Node> sortedInstructions = new ArrayList<Node>();
+        assert !map.isMarked(b.firstNode()) && nodeToBlock.get(b.firstNode()) == b;
+
+        boolean scheduleFirst = true;
+
+        if (b.firstNode() == b.lastNode()) {
+            Node node = b.firstNode();
+            if (!(node instanceof Merge)) {
+                scheduleFirst = false;
+            }
+        }
+        if (scheduleFirst) {
+            addToSorting(b, b.firstNode(), sortedInstructions, map);
+        }
+        for (Node i : instructions) {
+            addToSorting(b, i, sortedInstructions, map);
+        }
+        addToSorting(b, b.lastNode(), sortedInstructions, map);
+        //assert b.firstNode() == sortedInstructions.get(0) : b.firstNode();
+    //    assert b.lastNode() == sortedInstructions.get(sortedInstructions.size() - 1);
+        b.setInstructions(sortedInstructions);
+//        TTY.println("Block " + b);
+//        for (Node n : sortedInstructions) {
+//            TTY.println("Node: " + n);
+//        }
+    }
+
+    private void addToSorting(Block b, Node i, List<Node> sortedInstructions, NodeBitMap map) {
+        if (i == null || map.isMarked(i) || nodeToBlock.get(i) != b || i instanceof Phi || i instanceof Local) {
+            return;
+        }
+
+        for (Node input : i.inputs()) {
+            addToSorting(b, input, sortedInstructions, map);
+        }
+
+        for (Node pred : i.predecessors()) {
+            addToSorting(b, pred, sortedInstructions, map);
+        }
+
+        map.mark(i);
+
+        for (Node succ : i.successors()) {
+            if (succ instanceof FrameState) {
+                addToSorting(b, succ, sortedInstructions, map);
+            }
+        }
+
+        // Now predecessors and inputs are scheduled => we can add this node.
+        if (!(i instanceof FrameState)) {
+            sortedInstructions.add(i);
+        }
+    }
+
+    private void computeDominators() {
+        Block dominatorRoot = nodeToBlock.get(graph.start());
+        assert dominatorRoot.getPredecessors().size() == 0;
+        CiBitMap visited = new CiBitMap(blocks.size());
+        visited.set(dominatorRoot.blockID());
+        LinkedList<Block> workList = new LinkedList<Block>();
+        workList.add(dominatorRoot);
+
+        while (!workList.isEmpty()) {
+            Block b = workList.remove();
+
+            List<Block> predecessors = b.getPredecessors();
+            if (predecessors.size() == 1) {
+                b.setDominator(predecessors.get(0));
+            } else if (predecessors.size() > 0) {
+                boolean delay = false;
+                for (Block pred : predecessors) {
+                    if (pred != dominatorRoot && pred.dominator() == null) {
+                        delay = true;
+                        break;
+                    }
+                }
+
+                if (delay) {
+                    workList.add(b);
+                    continue;
+                }
+
+                Block dominator = null;
+                for (Block pred : predecessors) {
+                    if (dominator == null) {
+                        dominator = pred;
+                    } else {
+                        dominator = commonDominator(dominator, pred);
+                    }
+                }
+                b.setDominator(dominator);
+            }
+
+            for (Block succ : b.getSuccessors()) {
+                if (!visited.get(succ.blockID())) {
+                    visited.set(succ.blockID());
+                    workList.add(succ);
+                }
+            }
+        }
+    }
+
+    public Block commonDominator(Block a, Block b) {
+        CiBitMap bitMap = new CiBitMap(blocks.size());
+        Block cur = a;
+        while (cur != null) {
+            bitMap.set(cur.blockID());
+            cur = cur.dominator();
+        }
+
+        cur = b;
+        while (cur != null) {
+            if (bitMap.get(cur.blockID())) {
+                return cur;
+            }
+            cur = cur.dominator();
+        }
+
+        throw new IllegalStateException("no common dominator between " + a + " and " + b);
+    }
+
+    private void print() {
+        TTY.println("============================================");
+        TTY.println("%d blocks", blocks.size());
+
+        for (Block b : blocks) {
+           TTY.println();
+           TTY.print(b.toString());
+
+           TTY.print(" succs=");
+           for (Block succ : b.getSuccessors()) {
+               TTY.print(succ + ";");
+           }
+
+           TTY.print(" preds=");
+           for (Block pred : b.getPredecessors()) {
+               TTY.print(pred + ";");
+           }
+
+           if (b.dominator() != null) {
+               TTY.print(" dom=" + b.dominator());
+           }
+           TTY.println();
+
+           if (b.getInstructions().size() > 0) {
+               TTY.print("first instr: " + b.getInstructions().get(0));
+               TTY.print("last instr: " + b.getInstructions().get(b.getInstructions().size() - 1));
+           }
+        }
+
+/*
+        TTY.println("============================================");
+        TTY.println("%d nodes", nodeToBlock.size());
+        for (Node n : graph.getNodes()) {
+            if (n != null) {
+                TTY.print("Node %d: %s", n.id(), n.getClass().toString());
+                Block curBlock = nodeToBlock.get(n);
+                if (curBlock != null) {
+                    TTY.print(" %s", curBlock);
+                }
+                TTY.println();
+            }
+        }*/
+    }
+
+    public static int trueSuccessorCount(Node n) {
+        if (n == null) {
+            return 0;
+        }
+        int i = 0;
+        for (Node s : n.successors()) {
+            if (isFixed(s)) {
+                i++;
+            }
+        }
+        return i;
+    }
+
+    public static int truePredecessorCount(Node n) {
+        if (n == null) {
+            return 0;
+        }
+        int i = 0;
+        for (Node s : n.predecessors()) {
+            if (isFixed(s)) {
+                i++;
+            }
+        }
+
+        if (n instanceof LoopBegin) {
+            i++;
+        }
+        return i;
+    }
+}
diff -r cc4b538852e3 -r 41318fcb6b56 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Schedule.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Schedule.java	Thu Jun 09 17:34:10 2011 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,467 +0,0 @@
-/*
- * Copyright (c) 2011, 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.max.graal.compiler.schedule;
-
-import java.util.*;
-
-import com.oracle.max.graal.compiler.debug.*;
-import com.oracle.max.graal.compiler.ir.*;
-import com.oracle.max.graal.compiler.phases.*;
-import com.oracle.max.graal.compiler.value.*;
-import com.oracle.max.graal.graph.*;
-import com.sun.cri.ci.*;
-
-
-public class Schedule extends Phase {
-    private final List<Block> blocks = new ArrayList<Block>();
-    private NodeMap<Block> nodeToBlock;
-    private Graph graph;
-
-
-    @Override
-    protected void run(Graph graph) {
-        this.graph = graph;
-        nodeToBlock = graph.createNodeMap();
-        identifyBlocks();
-    }
-
-    public List<Block> getBlocks() {
-        return Collections.unmodifiableList(blocks);
-    }
-
-    public NodeMap<Block> getNodeToBlock() {
-        return nodeToBlock;
-    }
-
-    private Block createBlock() {
-        Block b = new Block(blocks.size());
-        blocks.add(b);
-        return b;
-    }
-
-    private Block assignBlock(Node n) {
-        Block curBlock = nodeToBlock.get(n);
-        if (curBlock == null) {
-            curBlock = createBlock();
-            return assignBlock(n, curBlock);
-        }
-        return curBlock;
-    }
-
-
-    private Block assignBlock(Node n, Block b) {
-        assert nodeToBlock.get(n) == null;
-        nodeToBlock.set(n, b);
-        if (b.firstNode() == null) {
-            b.setFirstNode(n);
-            b.setLastNode(n);
-        } else {
-            if (b.lastNode() != null) {
-                b.getInstructions().add(b.lastNode());
-            }
-            b.setLastNode(n);
-        }
-        b.setLastNode(n);
-        return b;
-    }
-
-    public static boolean isFixed(Node n) {
-        return n != null && ((n instanceof FixedNode) || n == n.graph().start());
-    }
-
-    public static boolean isBlockEnd(Node n) {
-        return trueSuccessorCount(n) > 1 || n instanceof Anchor || n instanceof Return || n instanceof Unwind;
-    }
-
-    private void identifyBlocks() {
-        // Identify blocks.
-        final ArrayList<Node> blockBeginNodes = new ArrayList<Node>();
-        NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), null, new NodeVisitor() {
-            @Override
-            public boolean visit(Node n) {
-                if (!isFixed(n)) {
-                    return false;
-                }
-
-                if (n instanceof LoopBegin) {
-                    // a LoopBegin is always a merge
-                    assignBlock(n);
-                    blockBeginNodes.add(n);
-                    return true;
-                }
-
-                Node singlePred = null;
-                for (Node pred : n.predecessors()) {
-                    if (isFixed(pred)) {
-                        if (singlePred == null) {
-                            singlePred = pred;
-                        } else {
-                            // We have more than one predecessor => we are a merge block.
-                            assignBlock(n);
-                            blockBeginNodes.add(n);
-                            return true;
-                        }
-                    }
-                }
-
-                if (singlePred == null) {
-                    // We have no predecessor => we are the start block.
-                    assignBlock(n);
-                    blockBeginNodes.add(n);
-                } else {
-                    // We have a single predecessor => check its successor count.
-                    if (isBlockEnd(singlePred)) {
-                        assignBlock(n);
-                        blockBeginNodes.add(n);
-                    } else {
-                        assignBlock(n, nodeToBlock.get(singlePred));
-                    }
-                }
-                return true;
-            }}
-        );
-
-        // Connect blocks.
-        for (Node n : blockBeginNodes) {
-            Block block = nodeToBlock.get(n);
-            for (Node pred : n.predecessors()) {
-                if (isFixed(pred)) {
-                    Block predBlock = nodeToBlock.get(pred);
-                    predBlock.addSuccessor(block);
-                }
-            }
-
-            if (n instanceof Merge) {
-                for (Node usage : n.usages()) {
-                    if (usage instanceof Phi) {
-                        nodeToBlock.set(usage, block);
-                    }
-                }
-            }
-        }
-
-        for (Node n : graph.getNodes()) {
-            if (n instanceof FrameState) {
-                FrameState f = (FrameState) n;
-                if (f.predecessors().size() == 1) {
-                    Block predBlock = nodeToBlock.get(f.predecessors().get(0));
-                    assert predBlock != null;
-                    nodeToBlock.set(f, predBlock);
-                    predBlock.getInstructions().add(f);
-                } else {
-                    assert f.predecessors().size() == 0;
-                }
-            }
-        }
-
-        computeDominators();
-
-
-
-        // Add successors of loop end nodes. Makes the graph cyclic.
-        for (Node n : blockBeginNodes) {
-            Block block = nodeToBlock.get(n);
-            if (n instanceof LoopBegin) {
-                LoopBegin loopBegin = (LoopBegin) n;
-                nodeToBlock.get(loopBegin.loopEnd()).addSuccessor(block);
-            }
-        }
-
-        assignLatestPossibleBlockToNodes();
-        sortNodesWithinBlocks();
-
-        //print();
-    }
-
-    private void assignLatestPossibleBlockToNodes() {
-        for (Node n : graph.getNodes()) {
-            assignLatestPossibleBlockToNode(n);
-        }
-    }
-
-    private Block assignLatestPossibleBlockToNode(Node n) {
-        if (n == null) {
-            return null;
-        }
-
-        Block prevBlock = nodeToBlock.get(n);
-        if (prevBlock != null) {
-            return prevBlock;
-        }
-
-        Block block = null;
-        for (Node succ : n.successors()) {
-            block = getCommonDominator(block, assignLatestPossibleBlockToNode(succ));
-        }
-        for (Node usage : n.usages()) {
-            if (usage instanceof Phi) {
-                Phi phi = (Phi) usage;
-                Merge merge = phi.merge();
-                Block mergeBlock = nodeToBlock.get(merge);
-                assert mergeBlock != null : "no block for merge " + merge.id();
-                for (int i = 0; i < phi.valueCount(); ++i) {
-                    if (phi.valueAt(i) == n) {
-                        if (mergeBlock.getPredecessors().size() == 0) {
-                            TTY.println(merge.toString());
-                            TTY.println(phi.toString());
-                            TTY.println(merge.predecessors().toString());
-                            TTY.println("value count: " + phi.valueCount());
-                        }
-                        block = getCommonDominator(block, mergeBlock.getPredecessors().get(i));
-                    }
-                }
-            } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) {
-                Merge merge = ((FrameState) usage).block();
-                for (Node pred : merge.predecessors()) {
-                    if (isFixed(pred)) {
-                        block = getCommonDominator(block, nodeToBlock.get(pred));
-                    }
-                }
-            } else {
-                block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage));
-            }
-        }
-
-        nodeToBlock.set(n, block);
-        if (block != null) {
-            block.getInstructions().add(n);
-        }
-        return block;
-    }
-
-    private Block getCommonDominator(Block a, Block b) {
-        if (a == null) {
-            return b;
-        }
-        if (b == null) {
-            return a;
-        }
-        return commonDominator(a, b);
-    }
-
-    private void sortNodesWithinBlocks() {
-        NodeBitMap map = graph.createNodeBitMap();
-        for (Block b : blocks) {
-            sortNodesWithinBlocks(b, map);
-        }
-    }
-
-    private void sortNodesWithinBlocks(Block b, NodeBitMap map) {
-        List<Node> instructions = b.getInstructions();
-        List<Node> sortedInstructions = new ArrayList<Node>();
-        assert !map.isMarked(b.firstNode()) && nodeToBlock.get(b.firstNode()) == b;
-
-        boolean scheduleFirst = true;
-
-        if (b.firstNode() == b.lastNode()) {
-            Node node = b.firstNode();
-            if (!(node instanceof Merge)) {
-                scheduleFirst = false;
-            }
-        }
-        if (scheduleFirst) {
-            addToSorting(b, b.firstNode(), sortedInstructions, map);
-        }
-        for (Node i : instructions) {
-            addToSorting(b, i, sortedInstructions, map);
-        }
-        addToSorting(b, b.lastNode(), sortedInstructions, map);
-        //assert b.firstNode() == sortedInstructions.get(0) : b.firstNode();
-    //    assert b.lastNode() == sortedInstructions.get(sortedInstructions.size() - 1);
-        b.setInstructions(sortedInstructions);
-//        TTY.println("Block " + b);
-//        for (Node n : sortedInstructions) {
-//            TTY.println("Node: " + n);
-//        }
-    }
-
-    private void addToSorting(Block b, Node i, List<Node> sortedInstructions, NodeBitMap map) {
-        if (i == null || map.isMarked(i) || nodeToBlock.get(i) != b || i instanceof Phi || i instanceof Local) {
-            return;
-        }
-
-        for (Node input : i.inputs()) {
-            addToSorting(b, input, sortedInstructions, map);
-        }
-
-        for (Node pred : i.predecessors()) {
-            addToSorting(b, pred, sortedInstructions, map);
-        }
-
-        map.mark(i);
-
-        for (Node succ : i.successors()) {
-            if (succ instanceof FrameState) {
-                addToSorting(b, succ, sortedInstructions, map);
-            }
-        }
-
-        // Now predecessors and inputs are scheduled => we can add this node.
-        if (!(i instanceof FrameState)) {
-            sortedInstructions.add(i);
-        }
-    }
-
-    private void computeDominators() {
-        Block dominatorRoot = nodeToBlock.get(graph.start());
-        assert dominatorRoot.getPredecessors().size() == 0;
-        CiBitMap visited = new CiBitMap(blocks.size());
-        visited.set(dominatorRoot.blockID());
-        LinkedList<Block> workList = new LinkedList<Block>();
-        workList.add(dominatorRoot);
-
-        while (!workList.isEmpty()) {
-            Block b = workList.remove();
-
-            List<Block> predecessors = b.getPredecessors();
-            if (predecessors.size() == 1) {
-                b.setDominator(predecessors.get(0));
-            } else if (predecessors.size() > 0) {
-                boolean delay = false;
-                for (Block pred : predecessors) {
-                    if (pred != dominatorRoot && pred.dominator() == null) {
-                        delay = true;
-                        break;
-                    }
-                }
-
-                if (delay) {
-                    workList.add(b);
-                    continue;
-                }
-
-                Block dominator = null;
-                for (Block pred : predecessors) {
-                    if (dominator == null) {
-                        dominator = pred;
-                    } else {
-                        dominator = commonDominator(dominator, pred);
-                    }
-                }
-                b.setDominator(dominator);
-            }
-
-            for (Block succ : b.getSuccessors()) {
-                if (!visited.get(succ.blockID())) {
-                    visited.set(succ.blockID());
-                    workList.add(succ);
-                }
-            }
-        }
-    }
-
-    public Block commonDominator(Block a, Block b) {
-        CiBitMap bitMap = new CiBitMap(blocks.size());
-        Block cur = a;
-        while (cur != null) {
-            bitMap.set(cur.blockID());
-            cur = cur.dominator();
-        }
-
-        cur = b;
-        while (cur != null) {
-            if (bitMap.get(cur.blockID())) {
-                return cur;
-            }
-            cur = cur.dominator();
-        }
-
-        print();
-        assert false : "no common dominator between " + a + " and " + b;
-        return null;
-    }
-
-    private void print() {
-        TTY.println("============================================");
-        TTY.println("%d blocks", blocks.size());
-
-        for (Block b : blocks) {
-           TTY.println();
-           TTY.print(b.toString());
-
-           TTY.print(" succs=");
-           for (Block succ : b.getSuccessors()) {
-               TTY.print(succ + ";");
-           }
-
-           TTY.print(" preds=");
-           for (Block pred : b.getPredecessors()) {
-               TTY.print(pred + ";");
-           }
-
-           if (b.dominator() != null) {
-               TTY.print(" dom=" + b.dominator());
-           }
-           TTY.println();
-
-           if (b.getInstructions().size() > 0) {
-               TTY.print("first instr: " + b.getInstructions().get(0));
-               TTY.print("last instr: " + b.getInstructions().get(b.getInstructions().size() - 1));
-           }
-        }
-
-/*
-        TTY.println("============================================");
-        TTY.println("%d nodes", nodeToBlock.size());
-        for (Node n : graph.getNodes()) {
-            if (n != null) {
-                TTY.print("Node %d: %s", n.id(), n.getClass().toString());
-                Block curBlock = nodeToBlock.get(n);
-                if (curBlock != null) {
-                    TTY.print(" %s", curBlock);
-                }
-                TTY.println();
-            }
-        }*/
-    }
-
-    public static int trueSuccessorCount(Node n) {
-        if (n == null) {
-            return 0;
-        }
-        int i = 0;
-        for (Node s : n.successors()) {
-            if (isFixed(s)) {
-                i++;
-            }
-        }
-        return i;
-    }
-
-    public static int truePredecessorCount(Node n) {
-        if (n == null) {
-            return 0;
-        }
-        int i = 0;
-        for (Node s : n.predecessors()) {
-            if (isFixed(s)) {
-                i++;
-            }
-        }
-
-        if (n instanceof LoopBegin) {
-            i++;
-        }
-        return i;
-    }
-}
diff -r cc4b538852e3 -r 41318fcb6b56 graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/VMExitsNative.java
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/VMExitsNative.java	Thu Jun 09 17:34:10 2011 +0200
+++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/VMExitsNative.java	Thu Jun 09 18:59:28 2011 +0200
@@ -77,7 +77,6 @@
     public void startCompiler() {
         originalOut = System.out;
         originalErr = System.err;
-        TTY.println("startCompiler: " + originalOut);
     }
 
     public void shutdownCompiler() throws Throwable {