# HG changeset patch
# User Gilles Duboscq <gilles.duboscq@oracle.com>
# Date 1306766108 -7200
# Node ID ac4b086cbd728373415e7322aae853c326f59470
# Parent  530366123e46cb24c45abd4f01305b0ecc4e8c91# Parent  774d2bc061484254cb4dfddeaa4dd72455cd6fbb
Merge

diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java	Mon May 30 16:35:08 2011 +0200
@@ -24,6 +24,7 @@
 
 import java.util.*;
 
+import com.oracle.graal.graph.*;
 import com.sun.c1x.ir.*;
 
 
@@ -32,14 +33,46 @@
     private int blockID;
     private final List<Block> successors = new ArrayList<Block>();
     private final List<Block> predecessors = new ArrayList<Block>();
-    private final List<Instruction> instructions = new ArrayList<Instruction>();
+    private List<Node> instructions = new ArrayList<Node>();
     private boolean exceptionEntry;
+    private Block dominator;
+    private final List<Block> dominators = new ArrayList<Block>();
+
+    private Node firstNode;
+    private Node lastNode;
+
+    public Node firstNode() {
+        return firstNode;
+    }
+
+    public void setFirstNode(Node node) {
+        this.firstNode = node;
+    }
+
+    public Node lastNode() {
+        return lastNode;
+    }
+
+    public void setLastNode(Node node) {
+        this.lastNode = node;
+    }
 
     public List<Block> getSuccessors() {
         return Collections.unmodifiableList(successors);
     }
 
-    public List<Instruction> getInstructions() {
+    public void setDominator(Block dominator) {
+        assert this.dominator == null;
+        assert dominator != null;
+        this.dominator = dominator;
+        dominator.dominators.add(this);
+    }
+
+    public List<Block> getDominators() {
+        return Collections.unmodifiableList(dominators);
+    }
+
+    public List<Node> getInstructions() {
         return instructions;
     }
 
@@ -97,4 +130,12 @@
     public String toString() {
         return "B" + blockID;
     }
+
+    public Block dominator() {
+        return dominator;
+    }
+
+    public void setInstructions(List<Node> instructions) {
+        this.instructions = instructions;
+    }
 }
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Mon May 30 16:35:08 2011 +0200
@@ -27,6 +27,8 @@
 import com.oracle.graal.graph.*;
 import com.sun.c1x.debug.*;
 import com.sun.c1x.ir.*;
+import com.sun.c1x.value.*;
+import com.sun.cri.ci.*;
 
 
 public class Schedule {
@@ -66,9 +68,16 @@
     private Block assignBlock(Node n, Block b) {
         assert nodeToBlock.get(n) == null;
         nodeToBlock.set(n, b);
-        if (n != n.graph().start()) {
-            b.getInstructions().add((Instruction) n);
+        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;
     }
 
@@ -90,6 +99,13 @@
                     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 (isCFG(pred)) {
@@ -131,22 +147,245 @@
                     predBlock.addSuccessor(block);
                 }
             }
+
+            if (n instanceof Merge) {
+                for (Node usage : n.usages()) {
+                    if (usage instanceof Phi) {
+                        nodeToBlock.set(usage, block);
+                    }
+                }
+            }
         }
 
-        orderBlocks();
+        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 orderBlocks() {
-       /* List<Block> orderedBlocks = new ArrayList<Block>();
-        Block startBlock = nodeToBlock.get(graph.start().start());
-        List<Block> toSchedule = new ArrayList<Block>();
-        toSchedule.add(startBlock);
+    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.block();
+                Block mergeBlock = nodeToBlock.get(merge);
+                assert mergeBlock != null;
+                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 (isCFG(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;
 
-        while (toSchedule.size() != 0) {
+        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() {
@@ -169,6 +408,10 @@
            for (Block pred : b.getPredecessors()) {
                TTY.print(pred + ";");
            }
+
+           if (b.dominator() != null) {
+               TTY.print(" dom=" + b.dominator());
+           }
            TTY.println();
 
            if (b.getInstructions().size() > 0) {
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/C1XCompilation.java
--- a/graal/GraalCompiler/src/com/sun/c1x/C1XCompilation.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/C1XCompilation.java	Mon May 30 16:35:08 2011 +0200
@@ -287,7 +287,7 @@
             }
 
             if (compiler.isObserved()) {
-                compiler.fireCompilationEvent(new CompilationEvent(this, "After code generation", hir.getHIRStartBlock(), false, true, targetMethod));
+                compiler.fireCompilationEvent(new CompilationEvent(this, "After code generation", graph, false, true, targetMethod));
             }
 
             if (C1XOptions.PrintTimers) {
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/alloc/EdgeMoveOptimizer.java
--- a/graal/GraalCompiler/src/com/sun/c1x/alloc/EdgeMoveOptimizer.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/alloc/EdgeMoveOptimizer.java	Mon May 30 16:35:08 2011 +0200
@@ -190,7 +190,7 @@
         List<LIRInstruction> instructions = block.lir().instructionsList();
 
         assert numSux == 2 : "method should not be called otherwise";
-        assert instructions.get(instructions.size() - 1).code == LIROpcode.Branch : "block with successor must end with branch";
+        assert instructions.get(instructions.size() - 1).code == LIROpcode.Branch : "block with successor must end with branch block=B" + block.blockID();
         assert instructions.get(instructions.size() - 1) instanceof LIRBranch : "branch must be LIROpBranch";
         assert ((LIRBranch) instructions.get(instructions.size() - 1)).cond() == Condition.TRUE : "block must end with unconditional branch";
 
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScan.java
--- a/graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScan.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScan.java	Mon May 30 16:35:08 2011 +0200
@@ -849,9 +849,15 @@
                     LIRBlock block = blockAt(j);
                     if (block.liveGen.get(operandNum)) {
                         TTY.println("  used in block B%d", block.blockID());
+                        for (LIRInstruction ins : block.lir().instructionsList()) {
+                            TTY.println(ins.id + ": " + ins.result() + " " + ins.toString());
+                        }
                     }
                     if (block.liveKill.get(operandNum)) {
                         TTY.println("  defined in block B%d", block.blockID());
+                        for (LIRInstruction ins : block.lir().instructionsList()) {
+                            TTY.println(ins.id + ": " + ins.result() + " " + ins.toString());
+                        }
                     }
                 }
             }
@@ -2146,7 +2152,7 @@
         }
 
         if (compilation.compiler.isObserved()) {
-            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, label, compilation.hir().getHIRStartBlock(), hirValid, true));
+            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, label, compilation.graph, hirValid, true));
         }
     }
 
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/debug/BlockPrinter.java
--- a/graal/GraalCompiler/src/com/sun/c1x/debug/BlockPrinter.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/debug/BlockPrinter.java	Mon May 30 16:35:08 2011 +0200
@@ -22,6 +22,7 @@
  */
 package com.sun.c1x.debug;
 
+import com.oracle.graal.graph.*;
 import com.oracle.max.graal.schedule.*;
 import com.sun.c1x.graph.*;
 import com.sun.c1x.ir.*;
@@ -44,7 +45,7 @@
     public void apply(Block block) {
         if (cfgOnly) {
             if (block.getInstructions().size() > 0) {
-                ip.printInstruction(block.getInstructions().get(0));
+                ip.printInstruction((Instruction) block.getInstructions().get(0));
             } else {
                 ip.out().println("Empty block");
             }
@@ -60,8 +61,10 @@
 
         ip.printInstructionListingHeader();
 
-        for (Instruction i : block.getInstructions()) {
-            ip.printInstructionListing(i);
+        for (Node i : block.getInstructions()) {
+            if (i instanceof Instruction) {
+                ip.printInstructionListing((Instruction) i);
+            }
         }
         out.println();
 
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java
--- a/graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java	Mon May 30 16:35:08 2011 +0200
@@ -25,6 +25,7 @@
 import java.io.*;
 import java.util.*;
 
+import com.oracle.graal.graph.*;
 import com.oracle.max.graal.schedule.*;
 import com.sun.c1x.*;
 import com.sun.c1x.alloc.*;
@@ -407,8 +408,10 @@
         begin("IR");
         out.println("HIR");
         out.disableIndentation();
-        for (Instruction i : block.getInstructions()) {
-            printInstructionHIR(i);
+        for (Node i : block.getInstructions()) {
+            if (i instanceof Instruction) {
+                printInstructionHIR((Instruction) i);
+            }
         }
         out.enableIndentation();
         end("IR");
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinterObserver.java
--- a/graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinterObserver.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinterObserver.java	Mon May 30 16:35:08 2011 +0200
@@ -39,8 +39,14 @@
     private C1XCompilation currentCompilation;
     private CFGPrinter cfgPrinter;
     private ByteArrayOutputStream buffer = null;
+    private final OutputStream stream;
 
     public CFGPrinterObserver() {
+        this(CFGPrinter.cfgFileStream());
+    }
+
+    public CFGPrinterObserver(OutputStream stream) {
+        this.stream = stream;
     }
 
     @Override
@@ -96,13 +102,13 @@
 
         cfgPrinter.flush();
 
-        OutputStream cfgFileStream = CFGPrinter.cfgFileStream();
-        if (cfgFileStream != null) {
-            synchronized (cfgFileStream) {
+        if (stream != null) {
+            synchronized (stream) {
                 try {
-                    cfgFileStream.write(buffer.toByteArray());
+                    stream.write(buffer.toByteArray());
+                    stream.flush();
                 } catch (IOException e) {
-                    TTY.println("WARNING: Error writing CFGPrinter output for %s to disk: %s", event.getMethod(), e);
+                    TTY.println("WARNING: Error writing CFGPrinter output for %s: %s", event.getMethod(), e);
                 }
             }
         }
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/debug/GraphvizPrinterObserver.java
--- a/graal/GraalCompiler/src/com/sun/c1x/debug/GraphvizPrinterObserver.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/debug/GraphvizPrinterObserver.java	Mon May 30 16:35:08 2011 +0200
@@ -28,6 +28,7 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.graph.vis.*;
 import com.sun.c1x.*;
+import com.sun.c1x.ir.*;
 import com.sun.c1x.observer.*;
 import com.sun.c1x.value.*;
 
@@ -56,8 +57,8 @@
     }
 
     public void compilationEvent(CompilationEvent event) {
-        if (event.getStartBlock() != null && !TTY.isSuppressed()) {
-            Graph graph = event.getStartBlock().graph();
+        if (event.getGraph() != null && !TTY.isSuppressed()) {
+            Graph graph = event.getGraph();
 
             String name = event.getMethod().holder().name();
             name = name.substring(1, name.length() - 1).replace('/', '.');
@@ -70,26 +71,14 @@
             try {
                 if (pdf) {
                     ByteArrayOutputStream buffer = new ByteArrayOutputStream();
-                    GraphvizPrinter printer = new GraphvizPrinter(buffer);
-                    if (C1XOptions.OmitDOTFrameStates) {
-                        printer.addOmittedClass(FrameState.class);
-                    }
-                    printer.begin(name);
-                    printer.print(graph, true);
-                    printer.end();
+                    printGraph(graph, name, buffer);
 
                     out = new FileOutputStream(filename + ".pdf");
                     GraphvizRunner.process(GraphvizRunner.DOT_LAYOUT, new ByteArrayInputStream(buffer.toByteArray()), out, "pdf");
                 } else {
                     out = new FileOutputStream(filename + ".gv");
 
-                    GraphvizPrinter printer = new GraphvizPrinter(out);
-                    if (C1XOptions.OmitDOTFrameStates) {
-                        printer.addOmittedClass(FrameState.class);
-                    }
-                    printer.begin(name);
-                    printer.print(graph, true);
-                    printer.end();
+                    printGraph(graph, name, out);
                 }
             } catch (IOException e) {
                 e.printStackTrace();
@@ -103,4 +92,20 @@
             }
         }
     }
+
+    private static void printGraph(Graph graph, String name, OutputStream buffer) {
+        GraphvizPrinter printer = new GraphvizPrinter(buffer);
+        if (C1XOptions.OmitDOTFrameStates) {
+            printer.addOmittedClass(FrameState.class);
+        }
+        printer.addClassColor(StartNode.class, "snow3");
+        printer.addClassColor(EndNode.class, "snow3");
+        printer.addClassColor(LoopBegin.class, "skyblue");
+        printer.addClassColor(LoopEnd.class, "skyblue3");
+        printer.addClassColor(Unwind.class, "red");
+        printer.addClassColor(Return.class, "indianred1");
+        printer.begin(name);
+        printer.print(graph, true);
+        printer.end();
+    }
 }
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/debug/IdealGraphPrinter.java
--- a/graal/GraalCompiler/src/com/sun/c1x/debug/IdealGraphPrinter.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/debug/IdealGraphPrinter.java	Mon May 30 16:35:08 2011 +0200
@@ -27,6 +27,8 @@
 import java.util.Map.Entry;
 
 import com.oracle.graal.graph.*;
+import com.oracle.max.graal.schedule.*;
+import com.sun.c1x.ir.*;
 
 /**
  * Generates a representation of {@link Graph Graphs} that can be visualized and inspected with the <a
@@ -50,6 +52,7 @@
 
     private final HashSet<Class<?>> omittedClasses = new HashSet<Class<?>>();
     private final PrintStream stream;
+    private final List<Node> noBlockNodes = new LinkedList<Node>();
 
     /**
      * Creates a new {@link IdealGraphPrinter} that writes to the specified output stream.
@@ -109,8 +112,10 @@
     public void print(Graph graph, String title, boolean shortNames) {
         stream.printf(" <graph name='%s'>%n", escape(title));
 
+        Schedule schedule = new Schedule(graph);
+
         stream.println("  <nodes>");
-        List<Edge> edges = printNodes(graph.getNodes(), shortNames);
+        List<Edge> edges = printNodes(graph.getNodes(), shortNames, schedule.getNodeToBlock());
         stream.println("  </nodes>");
 
         stream.println("  <edges>");
@@ -119,14 +124,21 @@
         }
         stream.println("  </edges>");
 
+        stream.println("  <controlFlow>");
+        for (Block block : schedule.getBlocks()) {
+            printBlock(graph, block);
+        }
+        printNoBlock();
+        stream.println("  </controlFlow>");
+
         stream.println(" </graph>");
     }
 
-    private List<Edge> printNodes(Collection<Node> nodes, boolean shortNames) {
+    private List<Edge> printNodes(Collection<Node> nodes, boolean shortNames, NodeMap<Block> nodeToBlock) {
         ArrayList<Edge> edges = new ArrayList<Edge>();
 
         for (Node node : nodes) {
-            if (node == Node.Null || omittedClasses.contains(node)) {
+            if (node == Node.Null || omittedClasses.contains(node.getClass())) {
                 continue;
             }
 
@@ -143,6 +155,13 @@
                 }
                 stream.printf("    <p name='name'>%s</p>%n", escape(name));
             }
+            Block block = nodeToBlock.get(node);
+            if (block != null) {
+                stream.printf("    <p name='block'>%d</p>%n", block.blockID());
+            } else {
+                stream.printf("    <p name='block'>noBlock</p>%n");
+                noBlockNodes.add(node);
+            }
             for (Entry<Object, Object> entry : props.entrySet()) {
                 String key = entry.getKey().toString();
                 String value = entry.getValue().toString();
@@ -177,6 +196,67 @@
         stream.printf("   <edge from='%d' fromIndex='%d' to='%d' toIndex='%d'/>%n", edge.from, edge.fromIndex, edge.to, edge.toIndex);
     }
 
+    private void printBlock(Graph graph, Block block) {
+        stream.printf("   <block name='%d'>%n", block.blockID());
+        stream.printf("    <successors>%n");
+        for (Block sux : block.getSuccessors()) {
+            if (sux.firstNode() instanceof LoopBegin && block.lastNode() instanceof LoopEnd) {
+                // Skip back edges.
+            } else {
+                stream.printf("     <successor name='%d'/>%n", sux.blockID());
+            }
+        }
+        stream.printf("    </successors>%n");
+        stream.printf("    <nodes>%n");
+
+        ArrayList<Node> nodes = new ArrayList<Node>(block.getInstructions());
+        // if this is the first block: add all locals to this block
+        if (nodes.get(0) == graph.start()) {
+            for (Node node : graph.getNodes()) {
+                if (node instanceof Local) {
+                    nodes.add(node);
+                }
+            }
+        }
+        // add all framestates and phis to their blocks
+        for (Node node : block.getInstructions()) {
+            if (node instanceof Instruction && ((Instruction) node).stateAfter() != null) {
+                nodes.add(((Instruction) node).stateAfter());
+            }
+            if (node instanceof Merge) {
+                Merge merge = (Merge) node;
+                if (merge.stateBefore() != null) {
+                    nodes.add(merge.stateBefore());
+                }
+                for (Node usage : merge.usages()) {
+                    if (usage instanceof Phi) {
+                        nodes.add(usage);
+                    }
+                }
+            }
+        }
+
+        for (Node node : nodes) {
+            if (!omittedClasses.contains(node.getClass())) {
+                stream.printf("     <node id='%d'/>%n", node.id());
+            }
+        }
+        stream.printf("    </nodes>%n");
+        stream.printf("   </block>%n", block.blockID());
+    }
+
+    private void printNoBlock() {
+        if (!noBlockNodes.isEmpty()) {
+            stream.printf("   <block name='noBlock'>%n");
+            stream.printf("    <nodes>%n");
+            for (Node node : noBlockNodes) {
+                stream.printf("     <node id='%d'/>%n", node.id());
+            }
+            stream.printf("    </nodes>%n");
+            stream.printf("   </block>%n");
+        }
+    }
+
     private String escape(String s) {
         s = s.replace("&", "&amp;");
         s = s.replace("<", "&lt;");
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/debug/IdealGraphPrinterObserver.java
--- a/graal/GraalCompiler/src/com/sun/c1x/debug/IdealGraphPrinterObserver.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/debug/IdealGraphPrinterObserver.java	Mon May 30 16:35:08 2011 +0200
@@ -140,8 +140,8 @@
 
     @Override
     public void compilationEvent(CompilationEvent event) {
-        if (printer != null && event.getStartBlock() != null) {
-            Graph graph = event.getStartBlock().graph();
+        if (printer != null && event.getGraph() != null) {
+            Graph graph = event.getGraph();
             printer.print(graph, event.getLabel(), true);
         }
     }
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java
--- a/graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java	Mon May 30 16:35:08 2011 +0200
@@ -198,8 +198,6 @@
         variablesForConstants = new ArrayList<CiVariable>();
 
         this.operands = new OperandPool(compilation.target);
-
-        new PhiSimplifier(ir);
     }
 
     public ArrayList<DeoptimizationStub> deoptimizationStubs() {
@@ -230,8 +228,15 @@
             TTY.println("BEGIN Generating LIR for block B" + block.blockID());
         }
 
-        for (Instruction instr : block.getInstructions()) {
-            FrameState stateAfter = instr.stateAfter();
+        if (block.blockPredecessors().size() > 1) {
+            lastState = null;
+        }
+
+        for (Node instr : block.getInstructions()) {
+            FrameState stateAfter = null;
+            if (instr instanceof Instruction) {
+                stateAfter = ((Instruction) instr).stateAfter();
+            }
             FrameState stateBefore = null;
             if (instr instanceof StateSplit && ((StateSplit) instr).stateBefore() != null) {
                 stateBefore = ((StateSplit) instr).stateBefore();
@@ -245,9 +250,9 @@
                     }
                 }
             }
-            if (!(instr instanceof Merge)) {
+            if (!(instr instanceof Merge) && instr != instr.graph().start()) {
                 walkState(instr, stateAfter);
-                doRoot(instr);
+                doRoot((Value) instr);
             }
             if (stateAfter != null) {
                 lastState = stateAfter;
@@ -273,8 +278,8 @@
         blockDoEpilog();
     }
 
-    private static boolean jumpsToNextBlock(Instruction instr) {
-        return instr instanceof BlockEnd;
+    private static boolean jumpsToNextBlock(Node node) {
+        return node instanceof BlockEnd;
     }
 
     @Override
@@ -695,11 +700,11 @@
         }
     }
 
-    protected CiValue emitXir(XirSnippet snippet, Instruction x, LIRDebugInfo info, RiMethod method, boolean setInstructionResult) {
+    protected CiValue emitXir(XirSnippet snippet, Value x, LIRDebugInfo info, RiMethod method, boolean setInstructionResult) {
         return emitXir(snippet, x, info, null, method, setInstructionResult, null);
     }
 
-    protected CiValue emitXir(XirSnippet snippet, Instruction instruction, LIRDebugInfo info, LIRDebugInfo infoAfter, RiMethod method, boolean setInstructionResult, List<CiValue> pointerSlots) {
+    protected CiValue emitXir(XirSnippet snippet, Value instruction, LIRDebugInfo info, LIRDebugInfo infoAfter, RiMethod method, boolean setInstructionResult, List<CiValue> pointerSlots) {
         if (C1XOptions.PrintXirTemplates) {
             TTY.println("Emit XIR template " + snippet.template.name);
         }
@@ -1225,12 +1230,11 @@
         return res.toArray(new SwitchRange[res.size()]);
     }
 
-    void doRoot(Instruction instr) {
+    void doRoot(Value instr) {
         if (C1XOptions.TraceLIRGeneratorLevel >= 2) {
-            TTY.println("Emitting LIR for instruction " + instr.toString());
+            TTY.println("Emitting LIR for instruction " + instr);
         }
         currentInstruction = instr;
-        assert !instr.hasSubst() : "shouldn't have missed substitution";
 
         if (C1XOptions.TraceLIRVisit) {
             TTY.println("Visiting    " + instr);
@@ -1299,7 +1303,7 @@
 
     private List<Phi> getPhis(LIRBlock block) {
         if (block.getInstructions().size() > 0) {
-            Instruction i = block.getInstructions().get(0);
+            Node i = block.firstInstruction();
             if (i instanceof Merge) {
                 List<Phi> result = new ArrayList<Phi>();
                 for (Node n : i.usages()) {
@@ -1441,7 +1445,7 @@
         }
     }
 
-    protected void walkState(Instruction x, FrameState state) {
+    protected void walkState(Node x, FrameState state) {
         if (state == null) {
             return;
         }
@@ -1463,7 +1467,6 @@
 
     private void walkStateValue(Value value) {
         if (value != null) {
-            assert !value.hasSubst() : "missed substitution on " + value.toString();
             if (value instanceof Phi && !value.isIllegal()) {
                 // phi's are special
                 operandForPhi((Phi) value);
@@ -1475,12 +1478,12 @@
         }
     }
 
-    protected LIRDebugInfo stateFor(Instruction x) {
+    protected LIRDebugInfo stateFor(Value x) {
         assert lastState != null : "must have state before instruction for " + x;
         return stateFor(x, lastState);
     }
 
-    protected LIRDebugInfo stateFor(Instruction x, FrameState state) {
+    protected LIRDebugInfo stateFor(Value x, FrameState state) {
         if (compilation.placeholderState != null) {
             state = compilation.placeholderState;
         }
@@ -1549,7 +1552,7 @@
             }
         }
         // the value must be a constant or have a valid operand
-        assert operand.isLegal() : "this root has not been visited yet";
+        assert operand.isLegal() : "this root has not been visited yet; instruction=" + instruction;
         return operand;
     }
 
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/gen/PhiSimplifier.java
--- a/graal/GraalCompiler/src/com/sun/c1x/gen/PhiSimplifier.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/gen/PhiSimplifier.java	Mon May 30 16:35:08 2011 +0200
@@ -45,7 +45,7 @@
         }
         Phi phi = (Phi) x;
 
-        if (phi.valueCount() == 1) {
+        if (phi.valueCount() == 1 && !phi.checkFlag(Value.Flag.PhiCannotSimplify)) {
             return (Value) phi.replace(phi.valueAt(0));
         }
 
@@ -105,6 +105,10 @@
             // successfully simplified the phi
             assert phiSubst != null : "illegal phi function";
             phi.clearFlag(Value.Flag.PhiVisited);
+
+            phi.replace(phiSubst);
+//            System.out.printf("replaced phi with %d inputs\n", max);
+
             return phiSubst;
         }
     }
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/graph/CriticalEdgeFinder.java
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/CriticalEdgeFinder.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/graph/CriticalEdgeFinder.java	Mon May 30 16:35:08 2011 +0200
@@ -105,9 +105,10 @@
 
         // This goto is not a safepoint.
         Anchor e = new Anchor(null, graph);
-        Instruction sourceInstruction = source.getInstructions().get(source.getInstructions().size() - 1);
-        Instruction targetInstruction = target.getInstructions().get(0);
+        Node sourceInstruction = source.lastInstruction();
+        Node targetInstruction = target.firstInstruction();
         int sourceInstructionPredIndex = targetInstruction.predecessors().indexOf(sourceInstruction);
+        assert sourceInstructionPredIndex != -1 : "must find source instruction " + sourceInstruction + " in predecessor array of target instruction " + targetInstruction;
         int replacedIndex = targetInstruction.predecessorsIndex().get(sourceInstructionPredIndex);
         assert replacedIndex != -1 && sourceInstruction.successors().get(replacedIndex) != null;
         e.successors().setAndClear(1, sourceInstruction, replacedIndex);
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java	Mon May 30 16:35:08 2011 +0200
@@ -288,6 +288,9 @@
 
     public void mergeOrClone(Block target, FrameStateAccess newState) {
         Instruction first = target.firstInstruction;
+        if (target.isLoopHeader && isVisited(target)) {
+            first = ((LoopBegin) first).loopEnd();
+        }
         assert first instanceof StateSplit;
 
         int bci = target.startBci;
@@ -295,13 +298,13 @@
         FrameState existingState = ((StateSplit) first).stateBefore();
 
         if (existingState == null) {
-            assert first instanceof Merge ^ !target.isLoopHeader : "isLoopHeader: " + target.isLoopHeader;
+//            assert first instanceof Merge ^ !target.isLoopHeader : "isLoopHeader: " + target.isLoopHeader;
 
             // copy state because it is modified
             FrameState duplicate = newState.duplicate(bci);
 
             // if the block is a loop header, insert all necessary phis
-            if (target.isLoopHeader) {
+            if (first instanceof LoopBegin && target.isLoopHeader) {
                 assert first instanceof Merge;
                 insertLoopPhis((Merge) first, duplicate);
                 ((Merge) first).setStateBefore(duplicate);
@@ -319,16 +322,18 @@
             assert existingState.stackSize() == newState.stackSize();
 
             if (first instanceof Placeholder) {
-                Merge merge = new Merge(existingState.bci, target.isLoopHeader, graph);
+                assert !target.isLoopHeader;
+                Merge merge = new Merge(graph);
 
                 Placeholder p = (Placeholder) first;
                 assert p.next() == null;
                 p.replace(merge);
                 target.firstInstruction = merge;
                 merge.setStateBefore(existingState);
+                first = merge;
             }
 
-            existingState.merge((Merge) target.firstInstruction, newState);
+            existingState.merge((Merge) first, newState);
         }
 
         for (int j = 0; j < frameState.localsSize() + frameState.stackSize(); ++j) {
@@ -1027,13 +1032,17 @@
     }
 
     private Value appendConstant(CiConstant constant) {
-        return appendWithBCI(new Constant(constant, graph));
+        return append(new Constant(constant, graph));
     }
 
     private Value append(Instruction x) {
         return appendWithBCI(x);
     }
 
+    private Value append(Value v) {
+        return v;
+    }
+
     private Value appendWithBCI(Instruction x) {
         if (x.isAppended()) {
             // the instruction has already been added
@@ -1057,7 +1066,6 @@
     }
 
     private Instruction createTarget(Block block, FrameStateAccess stateAfter) {
-
         assert block != null && stateAfter != null;
         assert block.isLoopHeader || block.firstInstruction == null || block.firstInstruction.next() == null : "non-loop block must be iterated after all its predecessors";
 
@@ -1067,20 +1075,30 @@
 
         if (block.firstInstruction == null) {
             if (block.isLoopHeader) {
-                block.firstInstruction = new Merge(block.startBci, block.isLoopHeader, graph);
+//                block.firstInstruction = new Merge(block.startBci, graph);
+
+                LoopBegin loopBegin = new LoopBegin(graph);
+                LoopEnd loopEnd = new LoopEnd(graph);
+                loopEnd.setLoopBegin(loopBegin);
+                block.firstInstruction = loopBegin;
             } else {
                 block.firstInstruction = new Placeholder(graph);
             }
         }
         mergeOrClone(block, stateAfter);
         addToWorkList(block);
-        return block.firstInstruction;
+
+        if (block.firstInstruction instanceof LoopBegin && isVisited(block)) {
+            return ((LoopBegin) block.firstInstruction).loopEnd();
+        } else {
+            return block.firstInstruction;
+        }
     }
 
     private Value synchronizedObject(FrameStateAccess state, RiMethod target) {
         if (isStatic(target.accessFlags())) {
             Constant classConstant = new Constant(target.holder().getEncoding(Representation.JavaClass), graph);
-            return appendWithBCI(classConstant);
+            return append(classConstant);
         } else {
             return state.localAt(0);
         }
@@ -1136,6 +1154,28 @@
                 }
             }
         }
+        for (Block b : blocksVisited) {
+            if (b.isLoopHeader) {
+                LoopBegin begin = (LoopBegin) b.firstInstruction;
+                LoopEnd end = begin.loopEnd();
+
+//              This can happen with degenerated loops like this one:
+//                for (;;) {
+//                    try {
+//                        break;
+//                    } catch (UnresolvedException iioe) {
+//                    }
+//                }
+                if (end.stateBefore() != null) {
+                    begin.stateBefore().merge(begin, end.stateBefore());
+                } else {
+                    end.delete();
+                    Merge merge = new Merge(graph);
+                    merge.successors().setAndClear(merge.nextIndex(), begin, begin.nextIndex());
+                    begin.replace(merge);
+                }
+            }
+        }
     }
 
     private void createExceptionDispatch(ExceptionBlock block) {
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/graph/IR.java
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java	Mon May 30 16:35:08 2011 +0200
@@ -24,9 +24,11 @@
 
 import java.util.*;
 
+import com.oracle.graal.graph.*;
 import com.oracle.max.graal.schedule.*;
 import com.sun.c1x.*;
 import com.sun.c1x.debug.*;
+import com.sun.c1x.gen.*;
 import com.sun.c1x.ir.*;
 import com.sun.c1x.lir.*;
 import com.sun.c1x.observer.*;
@@ -62,7 +64,7 @@
         this.compilation = compilation;
     }
 
-    public Map<Value, LIRBlock> valueToBlock;
+    public Map<Node, LIRBlock> valueToBlock;
 
     /**
      * Builds the graph, optimizes it, and computes the linear scan block order.
@@ -79,6 +81,7 @@
             C1XTimers.HIR_OPTIMIZE.start();
         }
 
+        new PhiSimplifier(this);
         Schedule schedule = new Schedule(this.compilation.graph);
         List<Block> blocks = schedule.getBlocks();
         List<LIRBlock> lirBlocks = new ArrayList<LIRBlock>();
@@ -89,6 +92,9 @@
             map.put(b, block);
             block.setInstructions(b.getInstructions());
             block.setLinearScanNumber(b.blockID());
+
+            block.setFirstInstruction(b.firstNode());
+            block.setLastInstruction(b.lastNode());
             lirBlocks.add(block);
         }
 
@@ -116,9 +122,9 @@
 
         orderedBlocks = lirBlocks;
 
-        valueToBlock = new HashMap<Value, LIRBlock>();
+        valueToBlock = new HashMap<Node, LIRBlock>();
         for (LIRBlock b : orderedBlocks) {
-            for (Instruction i : b.getInstructions()) {
+            for (Node i : b.getInstructions()) {
                 valueToBlock.put(i, b);
             }
         }
@@ -188,7 +194,7 @@
         }
 
         if (compilation.compiler.isObserved()) {
-            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, phase, getHIRStartBlock(), true, false));
+            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, phase, compilation.graph, true, false));
         }
     }
 
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/ArrayLength.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/ArrayLength.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/ArrayLength.java	Mon May 30 16:35:08 2011 +0200
@@ -31,10 +31,33 @@
 /**
  * The {@code ArrayLength} instruction gets the length of an array.
  */
-public final class ArrayLength extends AccessArray {
+public final class ArrayLength extends Value {
+
+    private static final int INPUT_COUNT = 1;
+    private static final int INPUT_ARRAY = 0;
+
+    private static final int SUCCESSOR_COUNT = 0;
+
+    @Override
+    protected int inputCount() {
+        return super.inputCount() + INPUT_COUNT;
+    }
 
-    private static final int INPUT_COUNT = 0;
-    private static final int SUCCESSOR_COUNT = 0;
+    @Override
+    protected int successorCount() {
+        return super.successorCount() + SUCCESSOR_COUNT;
+    }
+
+    /**
+     * The instruction that produces the array object.
+     */
+     public Value array() {
+        return (Value) inputs().get(super.inputCount() + INPUT_ARRAY);
+    }
+
+    public Value setArray(Value n) {
+        return (Value) inputs().set(super.inputCount() + INPUT_ARRAY, n);
+    }
 
     /**
      * Constructs a new ArrayLength instruction.
@@ -42,7 +65,8 @@
      * @param newFrameState the state after executing this instruction
      */
     public ArrayLength(Value array, Graph graph) {
-        super(CiKind.Int, array, INPUT_COUNT, SUCCESSOR_COUNT, graph);
+        super(CiKind.Int, INPUT_COUNT, SUCCESSOR_COUNT, graph);
+        setArray(array);
     }
 
     @Override
@@ -56,7 +80,7 @@
     }
 
     @Override
-    public boolean valueEqual(Instruction i) {
+    public boolean valueEqual(Node i) {
         if (i instanceof ArrayLength) {
             ArrayLength o = (ArrayLength) i;
             return array() == o.array();
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/BlockEnd.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/BlockEnd.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/BlockEnd.java	Mon May 30 16:35:08 2011 +0200
@@ -58,7 +58,6 @@
 
     public Instruction setBlockSuccessor(int index, Instruction n) {
         assert index >= 0 && index < blockSuccessorCount;
-//        assert n == null || n instanceof BlockBegin : "only BlockBegins, for now... " + n.getClass();
         return (Merge) successors().set(super.successorCount() + SUCCESSOR_COUNT + index, n);
     }
 
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/CheckCast.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/CheckCast.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/CheckCast.java	Mon May 30 16:35:08 2011 +0200
@@ -78,7 +78,7 @@
     }
 
     @Override
-    public boolean valueEqual(Instruction i) {
+    public boolean valueEqual(Node i) {
         if (i instanceof CheckCast) {
             CheckCast o = (CheckCast) i;
             return targetClass == o.targetClass && object() == o.object();
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/Constant.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Constant.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Constant.java	Mon May 30 16:35:08 2011 +0200
@@ -33,7 +33,7 @@
  * The {@code Constant} instruction represents a constant such as an integer value,
  * long, float, object reference, address, etc.
  */
-public final class Constant extends Instruction {
+public final class Constant extends Value {
 
     private static final int INPUT_COUNT = 0;
     private static final int SUCCESSOR_COUNT = 0;
@@ -164,7 +164,7 @@
     }
 
     @Override
-    public boolean valueEqual(Instruction i) {
+    public boolean valueEqual(Node i) {
         return i instanceof Constant && ((Constant) i).value.equivalent(this.value);
     }
 
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/Convert.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Convert.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Convert.java	Mon May 30 16:35:08 2011 +0200
@@ -31,7 +31,7 @@
 /**
  * The {@code Convert} class represents a conversion between primitive types.
  */
-public final class Convert extends Instruction {
+public final class Convert extends Value {
 
     private static final int INPUT_COUNT = 1;
     private static final int INPUT_VALUE = 0;
@@ -88,7 +88,7 @@
     }
 
     @Override
-    public boolean valueEqual(Instruction i) {
+    public boolean valueEqual(Node i) {
         if (i instanceof Convert) {
             Convert o = (Convert) i;
             return opcode == o.opcode && value() == o.value();
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/IfOp.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/IfOp.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/IfOp.java	Mon May 30 16:35:08 2011 +0200
@@ -119,7 +119,7 @@
     }
 
     @Override
-    public boolean valueEqual(Instruction i) {
+    public boolean valueEqual(Node i) {
         if (i instanceof IfOp) {
             IfOp o = (IfOp) i;
             return opcode == o.opcode && x() == o.x() && y() == o.y() && trueValue() == o.trueValue() && falseValue() == o.falseValue();
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/InstanceOf.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/InstanceOf.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/InstanceOf.java	Mon May 30 16:35:08 2011 +0200
@@ -59,7 +59,7 @@
     }
 
     @Override
-    public boolean valueEqual(Instruction i) {
+    public boolean valueEqual(Node i) {
         if (i instanceof InstanceOf) {
             InstanceOf o = (InstanceOf) i;
             return targetClass == o.targetClass && object() == o.object();
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/Instruction.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Instruction.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Instruction.java	Mon May 30 16:35:08 2011 +0200
@@ -46,7 +46,7 @@
     private static final int INPUT_COUNT = 0;
 
     private static final int SUCCESSOR_COUNT = 1;
-    private static final int SUCCESSOR_NEXT = 0;
+    public static final int SUCCESSOR_NEXT = 0;
 
     @Override
     protected int inputCount() {
@@ -70,6 +70,10 @@
         return successors().set(super.successorCount() + SUCCESSOR_NEXT, next);
     }
 
+    public int nextIndex() {
+        return super.successorCount() + SUCCESSOR_NEXT;
+    }
+
 
     public static final int SYNCHRONIZATION_ENTRY_BCI = -1;
 
@@ -105,7 +109,7 @@
     public final Instruction appendNext(Instruction next) {
         setNext(next);
         if (next != null) {
-            assert !(this instanceof BlockEnd);
+            //assert !(this instanceof BlockEnd);
             next.isAppended = true;
         }
         return next;
@@ -141,38 +145,6 @@
         return (Instruction) predecessors().get(j);
     }
 
-    @Override
-    public Merge block() {
-        Instruction cur = this;
-        while (!(cur instanceof Merge)) {
-            List<Node> preds = cur.predecessors();
-            cur = (Instruction) preds.get(0);
-        }
-        return (Merge) cur;
-    }
-
-    /**
-     * Compute the value number of this Instruction. Local and global value numbering
-     * optimizations use a hash map, and the value number provides a hash code.
-     * If the instruction cannot be value numbered, then this method should return
-     * {@code 0}.
-     * @return the hashcode of this instruction
-     */
-    public int valueNumber() {
-        return 0;
-    }
-
-    /**
-     * Checks that this instruction is equal to another instruction for the purposes
-     * of value numbering.
-     * @param i the other instruction
-     * @return {@code true} if this instruction is equivalent to the specified
-     * instruction w.r.t. value numbering
-     */
-    public boolean valueEqual(Instruction i) {
-        return false;
-    }
-
     /**
      * Gets the state after the instruction, if it is recorded. Typically only
      * instances of {@link BlockEnd} have a non-null state after.
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/Local.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Local.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Local.java	Mon May 30 16:35:08 2011 +0200
@@ -46,11 +46,6 @@
         this.inputs().set(0, graph.start());
     }
 
-    @Override
-    public Merge block() {
-        return null;
-    }
-
     /**
      * Gets the index of this local.
      * @return the index
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/LoopBegin.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/LoopBegin.java	Mon May 30 16:35:08 2011 +0200
@@ -0,0 +1,60 @@
+/*
+ * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.sun.c1x.ir;
+
+import com.oracle.graal.graph.*;
+import com.sun.c1x.debug.*;
+
+public class LoopBegin extends Merge {
+
+    private static final int INPUT_COUNT = 0;
+    private static final int SUCCESSOR_COUNT = 0;
+
+    public LoopBegin(Graph graph) {
+        super(INPUT_COUNT, SUCCESSOR_COUNT, graph);
+    }
+
+    public LoopEnd loopEnd() {
+        for (Node usage : usages()) {
+            if (usage instanceof LoopEnd) {
+                LoopEnd end = (LoopEnd) usage;
+                if (end.loopBegin() == this) {
+                    return end;
+                }
+            }
+        }
+        assert false : "Begin should always have a LoopEnd";
+        return null;
+    }
+
+    @Override
+    public void accept(ValueVisitor v) {
+        v.visitLoopBegin(this);
+    }
+
+    @Override
+    public void print(LogStream out) {
+        out.print("loopBegin");
+    }
+
+}
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/LoopEnd.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/LoopEnd.java	Mon May 30 16:35:08 2011 +0200
@@ -0,0 +1,72 @@
+/*
+ * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.sun.c1x.ir;
+
+import com.oracle.graal.graph.*;
+import com.sun.c1x.debug.*;
+
+
+public class LoopEnd extends Merge {
+
+    private static final int INPUT_COUNT = 1;
+    private static final int INPUT_LOOP_BEGIN = 0;
+
+    private static final int SUCCESSOR_COUNT = 0;
+
+    @Override
+    protected int inputCount() {
+        return super.inputCount() + INPUT_COUNT;
+    }
+
+    @Override
+    protected int successorCount() {
+        return super.successorCount() + SUCCESSOR_COUNT;
+    }
+
+    /**
+     * The instruction which produces the input value to this instruction.
+     */
+     public LoopBegin loopBegin() {
+        return (LoopBegin) inputs().get(super.inputCount() + INPUT_LOOP_BEGIN);
+    }
+
+    public LoopBegin setLoopBegin(LoopBegin n) {
+        return (LoopBegin) inputs().set(super.inputCount() + INPUT_LOOP_BEGIN, n);
+    }
+
+    public LoopEnd(Graph graph) {
+        super(INPUT_COUNT, SUCCESSOR_COUNT, graph);
+    }
+
+    @Override
+    public void accept(ValueVisitor v) {
+        v.visitLoopEnd(this);
+    }
+
+    @Override
+    public void print(LogStream out) {
+        out.print("loopEnd ").print(loopBegin());
+    }
+
+
+}
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/Merge.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Merge.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Merge.java	Mon May 30 16:35:08 2011 +0200
@@ -33,7 +33,7 @@
  * about the basic block, including the successor and
  * predecessor blocks, exception handlers, liveness information, etc.
  */
-public final class Merge extends StateSplit {
+public class Merge extends StateSplit {
 
     private static final int INPUT_COUNT = 0;
 
@@ -54,32 +54,18 @@
         return false;
     }
 
-    public final boolean isLoopHeader;
-
-    /**
-     * Index of bytecode that generated this node when appended in a basic block.
-     * Negative values indicate special cases.
-     */
-    private int bci;
-
     /**
      * Constructs a new Merge at the specified bytecode index.
      * @param bci the bytecode index of the start
      * @param blockID the ID of the block
      * @param graph
      */
-    public Merge(int bci, boolean isLoopHeader, Graph graph) {
+    public Merge(Graph graph) {
         super(CiKind.Illegal, INPUT_COUNT, SUCCESSOR_COUNT, graph);
-        this.bci = bci;
-        this.isLoopHeader = isLoopHeader;
     }
 
-    /**
-     * Gets the bytecode index of this instruction.
-     * @return the bytecode index of this instruction
-     */
-    public int bci() {
-        return bci;
+    protected Merge(int inputCount, int successorCount, Graph graph) {
+        super(CiKind.Illegal, inputCount + INPUT_COUNT, successorCount + SUCCESSOR_COUNT, graph);
     }
 
     @Override
@@ -95,21 +81,22 @@
         builder.append(" [");
 
         builder.append("]");
-        //if (end() != null) {
-            builder.append(" -> ");
-            boolean hasSucc = false;
-            for (Node s : this.successors()) {
-                if (s == null) {
-                    continue;
-                }
-                if (hasSucc) {
-                    builder.append(", ");
-                }
-                builder.append("#");
+
+        builder.append(" -> ");
+        boolean hasSucc = false;
+        for (Node s : this.successors()) {
+            if (hasSucc) {
+                builder.append(", ");
+            }
+            builder.append("#");
+            if (s != null) {
                 builder.append(s.id());
-                hasSucc = true;
+            } else {
+                builder.append("null");
             }
-        //}
+            hasSucc = true;
+        }
+
         return builder.toString();
     }
 
@@ -139,12 +126,12 @@
         //}
 
         // print predecessors
-        if (!blockPredecessors().isEmpty()) {
-            out.print(" pred:");
-            for (Instruction pred : blockPredecessors()) {
-                out.print(pred.block());
-            }
-        }
+//        if (!blockPredecessors().isEmpty()) {
+//            out.print(" pred:");
+//            for (Instruction pred : blockPredecessors()) {
+//                out.print(pred.block());
+//            }
+//        }
     }
 
     @Override
@@ -261,9 +248,6 @@
                 sb.append("] ");
             }
         }
-        if (value != null && value.hasSubst()) {
-            sb.append("alias ").append(Util.valueString(value.subst()));
-        }
         return sb.toString();
     }
 
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/MonitorAddress.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/MonitorAddress.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/MonitorAddress.java	Mon May 30 16:35:08 2011 +0200
@@ -29,7 +29,7 @@
 /**
  * Instruction that is used to refer to the address of an on-stack monitor.
  */
-public final class MonitorAddress extends Instruction {
+public final class MonitorAddress extends Value {
 
     private static final int INPUT_COUNT = 0;
     private static final int SUCCESSOR_COUNT = 0;
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/NegateOp.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/NegateOp.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/NegateOp.java	Mon May 30 16:35:08 2011 +0200
@@ -30,7 +30,7 @@
 /**
  * The {@code NegateOp} instruction negates its operand.
  */
-public final class NegateOp extends Instruction {
+public final class NegateOp extends Value {
 
     private static final int INPUT_COUNT = 2;
     private static final int INPUT_X = 0;
@@ -79,7 +79,7 @@
     }
 
     @Override
-    public boolean valueEqual(Instruction i) {
+    public boolean valueEqual(Node i) {
         if (i instanceof NegateOp) {
             NegateOp o = (NegateOp) i;
             return x() == o.x();
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/NewArray.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/NewArray.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/NewArray.java	Mon May 30 16:35:08 2011 +0200
@@ -28,7 +28,7 @@
 /**
  * The {@code NewArray} class is the base of all instructions that allocate arrays.
  */
-public abstract class NewArray extends StateSplit {
+public abstract class NewArray extends Instruction {
 
     private static final int INPUT_COUNT = 1;
     private static final int INPUT_LENGTH = 0;
@@ -69,9 +69,4 @@
         setFlag(Flag.NonNull);
         setLength(length);
     }
-
-    @Override
-    public boolean needsStateAfter() {
-        return false;
-    }
 }
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/NewInstance.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/NewInstance.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/NewInstance.java	Mon May 30 16:35:08 2011 +0200
@@ -30,7 +30,7 @@
 /**
  * The {@code NewInstance} instruction represents the allocation of an instance class object.
  */
-public final class NewInstance extends StateSplit {
+public final class NewInstance extends Value {
 
     private static final int INPUT_COUNT = 0;
     private static final int SUCCESSOR_COUNT = 0;
@@ -81,9 +81,4 @@
     public void print(LogStream out) {
         out.print("new instance ").print(CiUtil.toJavaName(instanceClass()));
     }
-
-    @Override
-    public boolean needsStateAfter() {
-        return false;
-    }
 }
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/NullCheck.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/NullCheck.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/NullCheck.java	Mon May 30 16:35:08 2011 +0200
@@ -31,7 +31,7 @@
 /**
  * The {@code NullCheck} class represents an explicit null check instruction.
  */
-public final class NullCheck extends Instruction {
+public final class NullCheck extends Value {
 
     private static final int INPUT_COUNT = 1;
     private static final int INPUT_OBJECT = 0;
@@ -82,7 +82,7 @@
     }
 
     @Override
-    public boolean valueEqual(Instruction i) {
+    public boolean valueEqual(Node i) {
         if (i instanceof NullCheck) {
             NullCheck o = (NullCheck) i;
             return object() == o.object();
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/Op2.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Op2.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Op2.java	Mon May 30 16:35:08 2011 +0200
@@ -30,7 +30,7 @@
 /**
  * The {@code Op2} class is the base of arithmetic and logic operations with two inputs.
  */
-public abstract class Op2 extends Instruction {
+public abstract class Op2 extends Value {
 
     private static final int INPUT_COUNT = 2;
     private static final int INPUT_X = 0;
@@ -105,7 +105,7 @@
     }
 
     @Override
-    public boolean valueEqual(Instruction i) {
+    public boolean valueEqual(Node i) {
         if (i instanceof Op2) {
             Op2 o = (Op2) i;
             return opcode == o.opcode && x() == o.x() && y() == o.y();
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/Phi.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Phi.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Phi.java	Mon May 30 16:35:08 2011 +0200
@@ -49,7 +49,6 @@
     /**
      * The join block for this phi.
      */
-     @Override
     public Merge block() {
         return (Merge) inputs().get(super.inputCount() + INPUT_BLOCK);
     }
@@ -120,7 +119,18 @@
 
     @Override
     public String shortName() {
-        return "Phi: (" + valueCount() + ")";
+        StringBuilder str = new StringBuilder();
+        for (int i = 1; i < inputs().size(); ++i) {
+            if (i != 1) {
+                str.append(' ');
+            }
+            if (inputs().get(i) != null) {
+                str.append(inputs().get(i).id());
+            } else {
+                str.append("-");
+            }
+        }
+        return "Phi: (" + str + ")";
     }
 
     public Phi addInput(Node y) {
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/TypeCheck.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/TypeCheck.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/TypeCheck.java	Mon May 30 16:35:08 2011 +0200
@@ -29,7 +29,7 @@
 /**
  * The {@code TypeCheck} instruction is the base class of casts and instanceof tests.
  */
-public abstract class TypeCheck extends Instruction {
+public abstract class TypeCheck extends Value {
 
     private static final int INPUT_COUNT = 2;
     private static final int INPUT_OBJECT = 0;
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/Value.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Value.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Value.java	Mon May 30 16:35:08 2011 +0200
@@ -57,13 +57,6 @@
     protected CiValue operand = CiValue.IllegalValue;
 
     /**
-     * Used by {@link InstructionSubstituter}.
-     */
-    public Value subst;
-
-    public abstract Merge block();
-
-    /**
      * Creates a new value with the specified kind.
      * @param kind the type of this value
      * @param inputCount
@@ -89,30 +82,6 @@
         throw new CloneNotSupportedException();
     }
 
-    /////////////////
-
-    /**
-     * Gets the instruction that should be substituted for this one. Note that this
-     * method is recursive; if the substituted instruction has a substitution, then
-     * the final substituted instruction will be returned. If there is no substitution
-     * for this instruction, {@code this} will be returned.
-     * @return the substitution for this instruction
-     */
-    public final Value subst() {
-        if (subst == null) {
-            return this;
-        }
-        return subst.subst();
-    }
-
-    /**
-     * Checks whether this instruction has a substitute.
-     * @return {@code true} if this instruction has a substitution.
-     */
-    public final boolean hasSubst() {
-        return subst != null;
-    }
-
     /**
      * Check whether this instruction has the specified flag set.
      * @param flag the flag to test
@@ -295,6 +264,28 @@
     }
 
     /**
+     * Compute the value number of this Instruction. Local and global value numbering
+     * optimizations use a hash map, and the value number provides a hash code.
+     * If the instruction cannot be value numbered, then this method should return
+     * {@code 0}.
+     * @return the hashcode of this instruction
+     */
+    public int valueNumber() {
+        return 0;
+    }
+
+    /**
+     * Checks that this instruction is equal to another instruction for the purposes
+     * of value numbering.
+     * @param i the other instruction
+     * @return {@code true} if this instruction is equivalent to the specified
+     * instruction w.r.t. value numbering
+     */
+    public boolean valueEqual(Node i) {
+        return false;
+    }
+
+    /**
      * This method supports the visitor pattern by accepting a visitor and calling the
      * appropriate {@code visit()} method.
      *
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/ir/ValueVisitor.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/ValueVisitor.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/ValueVisitor.java	Mon May 30 16:35:08 2011 +0200
@@ -70,4 +70,6 @@
     public abstract void visitDeoptimize(Deoptimize deoptimize);
     public abstract void visitExceptionDispatch(ExceptionDispatch exceptionDispatch);
     public abstract void visitUnwind(Unwind unwind);
+    public abstract void visitLoopBegin(LoopBegin loopBegin);
+    public abstract void visitLoopEnd(LoopEnd loopEnd);
 }
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java
--- a/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java	Mon May 30 16:35:08 2011 +0200
@@ -24,10 +24,10 @@
 
 import java.util.*;
 
+import com.oracle.graal.graph.*;
 import com.oracle.max.asm.*;
 import com.sun.c1x.alloc.*;
 import com.sun.c1x.debug.*;
-import com.sun.c1x.ir.*;
 import com.sun.c1x.util.*;
 import com.sun.c1x.value.*;
 import com.sun.cri.ci.*;
@@ -41,7 +41,7 @@
     private LIRList lir;
     private final int blockID;
     private FrameState lastState;
-    private List<Instruction> instructions = new ArrayList<Instruction>(4);
+    private List<Node> instructions = new ArrayList<Node>(4);
     private List<LIRBlock> predecessors = new ArrayList<LIRBlock>(4);
     private List<LIRBlock> successors = new ArrayList<LIRBlock>(4);
     private List<LIRBlock> exceptionHandlerSuccessors = new ArrayList<LIRBlock>(4);
@@ -89,7 +89,7 @@
         linearScanNumber = blockID;
     }
 
-    public List<Instruction> getInstructions() {
+    public List<Node> getInstructions() {
         return instructions;
     }
 
@@ -248,7 +248,7 @@
         predecessors.clear();
     }
 
-    public void setInstructions(List<Instruction> list) {
+    public void setInstructions(List<Node> list) {
         instructions = list;
     }
 
@@ -277,4 +277,25 @@
     public FrameState lastState() {
         return lastState;
     }
+
+    private Node first;
+    private Node last;
+
+    public Node firstInstruction() {
+        return first;
+    }
+
+
+    public Node lastInstruction() {
+        return last;
+    }
+
+    public void setFirstInstruction(Node n) {
+        first = n;
+    }
+
+
+    public void setLastInstruction(Node n) {
+        last = n;
+    }
 }
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/observer/CompilationEvent.java
--- a/graal/GraalCompiler/src/com/sun/c1x/observer/CompilationEvent.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/observer/CompilationEvent.java	Mon May 30 16:35:08 2011 +0200
@@ -24,10 +24,10 @@
 
 import java.util.*;
 
+import com.oracle.graal.graph.*;
 import com.sun.c1x.*;
 import com.sun.c1x.alloc.*;
 import com.sun.c1x.graph.*;
-import com.sun.c1x.ir.*;
 import com.sun.cri.ci.*;
 import com.sun.cri.ri.*;
 
@@ -43,7 +43,7 @@
 
     private final C1XCompilation compilation;
     private final String label;
-    private Instruction startBlock;
+    private Graph graph;
 
     private BlockMap blockMap;
     private int codeSize = -1;
@@ -67,15 +67,15 @@
         this.compilation = compilation;
     }
 
-    public CompilationEvent(C1XCompilation compilation, String label, Instruction startBlock, boolean hirValid, boolean lirValid) {
+    public CompilationEvent(C1XCompilation compilation, String label, Graph graph, boolean hirValid, boolean lirValid) {
         this(compilation, label);
-        this.startBlock = startBlock;
+        this.graph = graph;
         this.hirValid = hirValid;
         this.lirValid = lirValid;
     }
 
-    public CompilationEvent(C1XCompilation compilation, String label, Instruction startBlock, boolean hirValid, boolean lirValid, CiTargetMethod targetMethod) {
-        this(compilation, label, startBlock, hirValid, lirValid);
+    public CompilationEvent(C1XCompilation compilation, String label, Graph graph, boolean hirValid, boolean lirValid, CiTargetMethod targetMethod) {
+        this(compilation, label, graph, hirValid, lirValid);
         this.targetMethod = targetMethod;
     }
 
@@ -108,8 +108,8 @@
         return blockMap;
     }
 
-    public Instruction getStartBlock() {
-        return startBlock;
+    public Graph getGraph() {
+        return graph;
     }
 
     public LinearScan getAllocator() {
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/target/amd64/AMD64LIRAssembler.java
--- a/graal/GraalCompiler/src/com/sun/c1x/target/amd64/AMD64LIRAssembler.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/target/amd64/AMD64LIRAssembler.java	Mon May 30 16:35:08 2011 +0200
@@ -529,9 +529,10 @@
         if (op.cond() == Condition.TRUE) {
             if (op.info != null) {
                 int codePos = codePos();
-                if (codePos > tasm.lastSafepointPos()) {
-                    tasm.recordImplicitException(codePos, op.info);
+                if (codePos <= tasm.lastSafepointPos()) {
+                    masm.nop();
                 }
+                tasm.recordImplicitException(codePos(), op.info);
             }
             masm.jmp(op.label());
         } else {
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/target/amd64/AMD64LIRGenerator.java
--- a/graal/GraalCompiler/src/com/sun/c1x/target/amd64/AMD64LIRGenerator.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/target/amd64/AMD64LIRGenerator.java	Mon May 30 16:35:08 2011 +0200
@@ -531,4 +531,20 @@
         lir.jump(getLIRBlock(x.otherSuccessor()));
     }
 
+    @Override
+    public void visitLoopBegin(LoopBegin x) {
+        visitMerge(x);
+    }
+
+    @Override
+    public void visitLoopEnd(LoopEnd x) {
+        setNoResult(x);
+
+        // emit phi-instruction moves after safepoint since this simplifies
+        // describing the state at the safepoint.
+
+        moveToPhi();
+        lir.jump(getLIRBlock(x.loopBegin()));
+    }
+
 }
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalCompiler/src/com/sun/c1x/value/FrameState.java
--- a/graal/GraalCompiler/src/com/sun/c1x/value/FrameState.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/value/FrameState.java	Mon May 30 16:35:08 2011 +0200
@@ -371,12 +371,26 @@
                         }
                     }
 
-                    assert phi.valueCount() == block.predecessors().size() + 1 : "valueCount=" + phi.valueCount() + " predSize= " + block.predecessors().size();
+                    if (block instanceof LoopBegin) {
+//                        assert phi.valueCount() == ((LoopBegin) block).loopEnd().predecessors().size() + 1 : "loop, valueCount=" + phi.valueCount() + " predSize= " + ((LoopBegin) block).loopEnd().predecessors().size();
+                    } else {
+                        assert phi.valueCount() == block.predecessors().size() + 1 : "valueCount=" + phi.valueCount() + " predSize= " + block.predecessors().size();
+                    }
                }
             }
         }
     }
 
+    public Merge block() {
+        if (usages().size() > 0) {
+            assert usages().size() == 1;
+            Node node = usages().get(0);
+            if (node instanceof Merge) {
+                return (Merge) node;
+            }
+        }
+        return null;
+    }
 
     /**
      * The interface implemented by a client of {@link FrameState#forEachPhi(Merge, PhiProcedure)} and
@@ -441,11 +455,6 @@
     }
 
     @Override
-    public Merge block() {
-        return null;
-    }
-
-    @Override
     public void accept(ValueVisitor v) {
         v.visitFrameState(this);
     }
diff -r 530366123e46 -r ac4b086cbd72 graal/GraalGraphviz/src/com/oracle/graal/graph/vis/GraphvizPrinter.java
--- a/graal/GraalGraphviz/src/com/oracle/graal/graph/vis/GraphvizPrinter.java	Fri May 27 15:41:10 2011 +0200
+++ b/graal/GraalGraphviz/src/com/oracle/graal/graph/vis/GraphvizPrinter.java	Mon May 30 16:35:08 2011 +0200
@@ -25,6 +25,7 @@
 import java.awt.Color;
 import java.io.OutputStream;
 import java.io.PrintStream;
+import java.util.HashMap;
 import java.util.HashSet;
 
 import com.oracle.graal.graph.Graph;
@@ -46,6 +47,7 @@
 
     private final PrintStream out;
     private final HashSet<Class<?>> omittedClasses = new HashSet<Class<?>>();
+    private final HashMap<Class<?>, String> classColors = new HashMap<Class<?>, String>();
 
     /**
      * Creates a new {@link GraphvizPrinter} that writes to the specified output stream.
@@ -58,6 +60,10 @@
         omittedClasses.add(clazz);
     }
 
+    public void addClassColor(Class<?> clazz, String color) {
+        classColors.put(clazz, color);
+    }
+
     /**
      * Opens a graph with the specified title (label). Call this before printing any nodes, but not more than once
      * without calling {@link #end()} first.
@@ -104,10 +110,12 @@
         NodeArray inputs = node.inputs();
         NodeArray successors = node.successors();
 
+        String color = classColors.get(node.getClass());
+
         if (shortNames) {
-            printNode(name, node.shortName(), inputs.size(), successors.size());
+            printNode(name, node.id(), excapeLabel(node.shortName()), color, inputs.size(), successors.size());
         } else {
-            printNode(name, node.toString(), inputs.size(), successors.size());
+            printNode(name, node.id(), excapeLabel(node.toString()), color, inputs.size(), successors.size());
         }
 
         for (int i = 0; i < successors.size(); ++i) {
@@ -128,8 +136,8 @@
         }
     }
 
-    private void printNode(String name, String label, int ninputs, int nsuccessors) {
-        int minWidth = Math.min(label.length() / 3, 10);
+    private void printNode(String name, Number number, String label, String color, int ninputs, int nsuccessors) {
+        int minWidth = Math.min(1 + label.length() / 3, 10);
         minWidth = Math.max(minWidth, Math.max(ninputs + 1, nsuccessors + 1));
         out.println(name + "  [shape=plaintext,");
         out.println("   label=< <TABLE BORDER=\"0\" CELLSPACING=\"0\"><TR>");
@@ -144,11 +152,11 @@
             printPort("in" + i, "lightgrey");
         }
 
-        label = label.replace("&", "&amp;");
-        label = label.replace("<", "&lt;");
-        label = label.replace(">", "&gt;");
-        label = label.replace("\"", "&quot;");
-        out.println("    </TR><TR><TD BORDER=\"1\" COLSPAN=\"" + minWidth + "\" BGCOLOR=\"" + NODE_BGCOLOR_STRING + "\">" + label + "</TD></TR><TR>");
+        if (number != null) {
+            label = "<FONT POINT-SIZE=\"8\">" + number + "</FONT> " + label;
+        }
+
+        out.println("    </TR><TR><TD BORDER=\"1\" COLSPAN=\"" + minWidth + "\" BGCOLOR=\"" + (color != null ? color : NODE_BGCOLOR_STRING) + "\">" + label + "</TD></TR><TR>");
 
         for (int i = 0; i < nsuccessors; i++) {
             printPort("succ" + i, "rosybrown1");
@@ -163,6 +171,14 @@
         out.println("    </TR></TABLE>>]; ");
     }
 
+    private static String excapeLabel(String label) {
+        label = label.replace("&", "&amp;");
+        label = label.replace("<", "&lt;");
+        label = label.replace(">", "&gt;");
+        label = label.replace("\"", "&quot;");
+        return label;
+    }
+
     private void printPort(String name, String color) {
         out.print("    <TD CELLPADDING=\"0\" WIDTH=\"15\"><TABLE BORDER=\"0\" CELLSPACING=\"2\" CELLPADDING=\"0\"><TR><TD WIDTH=\"15\" HEIGHT=\"5\" PORT=\"");
         out.print(name);
@@ -176,7 +192,7 @@
     }
 
     private void printControlEdge(int from, int fromPort, int to) {
-        out.println("n" + from + ":succ" + fromPort + " -> n" + to + ":predecessors:n [color=red, weight=2];");
+        out.println("n" + from + ":succ" + fromPort + ":s -> n" + to + ":predecessors:n [color=red, weight=2];");
     }
 
     private void printDataEdge(int from, int fromPort, int to) {
diff -r 530366123e46 -r ac4b086cbd72 runscimark.sh
--- a/runscimark.sh	Fri May 27 15:41:10 2011 +0200
+++ b/runscimark.sh	Mon May 30 16:35:08 2011 +0200
@@ -23,5 +23,5 @@
 for (( i = 1; i <= ${COUNT}; i++ ))      ### Outer for loop ###
 do
   echo "$i "
-  ${JDK7}/jre/bin/java -client -d64 -graal -esa -ea -Xms32m -Xmx100m -Xbootclasspath/a:${SCIMARK} -C1X:+PrintTimers $@ jnt.scimark2.commandline -large
+  ${JDK7}/jre/bin/java -client -d64 -graal -esa -ea -Xms32m -Xmx100m -Xbootclasspath/a:${SCIMARK} -C1X:+PrintTimers $@ jnt.scimark2.commandline
 done
diff -r 530366123e46 -r ac4b086cbd72 runtests.sh
--- a/runtests.sh	Fri May 27 15:41:10 2011 +0200
+++ b/runtests.sh	Mon May 30 16:35:08 2011 +0200
@@ -12,4 +12,4 @@
   exit 1;
 fi
 TESTDIR=${MAXINE}/com.oracle.max.vm/test
-${JDK7}/bin/java -client -d64 -graal -ea -esa -Xcomp -C1X:PrintIdealGraphLevel=0 -C1X:-PrintCFGToFile -C1X:-PrintAssembly -XX:-TraceSignals -XX:-TraceDeoptimization -XX:-TraceExceptions -XX:+PrintCompilation -XX:CompileOnly=jtt -Xbootclasspath/p:"${MAXINE}/com.oracle.max.vm/bin" -Xbootclasspath/p:"${MAXINE}/com.oracle.max.base/bin" $1 test.com.sun.max.vm.compiler.JavaTester -verbose=1 -gen-run-scheme=false -run-scheme-package=all ${TESTDIR}/jtt/bytecode ${TESTDIR}/jtt/except ${TESTDIR}/jtt/hotpath ${TESTDIR}/jtt/jdk ${TESTDIR}/jtt/lang ${TESTDIR}/jtt/loop ${TESTDIR}/jtt/micro ${TESTDIR}/jtt/optimize ${TESTDIR}/jtt/reflect ${TESTDIR}/jtt/threads
+${JDK7}/bin/java -client -d64 -graal -ea -esa -Xcomp -C1X:PrintIdealGraphLevel=4 -C1X:PrintFilter=anewarray -C1X:-PrintCFGToFile -C1X:-PrintAssembly -XX:-TraceSignals -XX:-TraceDeoptimization -XX:-TraceExceptions -XX:+PrintCompilation -XX:CompileOnly=jtt -Xbootclasspath/p:"${MAXINE}/com.oracle.max.vm/bin" -Xbootclasspath/p:"${MAXINE}/com.oracle.max.base/bin" $1 test.com.sun.max.vm.compiler.JavaTester -verbose=1 -gen-run-scheme=false -run-scheme-package=all ${TESTDIR}/jtt/bytecode ${TESTDIR}/jtt/except ${TESTDIR}/jtt/hotpath ${TESTDIR}/jtt/jdk ${TESTDIR}/jtt/lang ${TESTDIR}/jtt/loop ${TESTDIR}/jtt/micro ${TESTDIR}/jtt/optimize ${TESTDIR}/jtt/reflect ${TESTDIR}/jtt/threads
diff -r 530366123e46 -r ac4b086cbd72 src/share/vm/compiler/compilerOracle.cpp
--- a/src/share/vm/compiler/compilerOracle.cpp	Fri May 27 15:41:10 2011 +0200
+++ b/src/share/vm/compiler/compilerOracle.cpp	Mon May 30 16:35:08 2011 +0200
@@ -471,7 +471,7 @@
   line += bytes_read;
 
   if (command == UnknownCommand) {
-    tty->print_cr("CompilerOracle: unrecognized line");
+    tty->print_cr("CompilerOracle: UnknownCommand");
     tty->print_cr("  \"%s\"", original_line);
     return;
   }