# HG changeset patch
# User Thomas Wuerthinger <thomas@wuerthinger.net>
# Date 1308152825 -7200
# Node ID cbece91420af3a93b84cb61ef4b792b8aa0382d6
# Parent  d69b4d2eb49999bc9933b5ad0303944e47cbf03b# Parent  4a64ffd60c03066b404ee0b4e4f5d1fb1aa6b9a9
Merge.

diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/EdgeMoveOptimizer.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/EdgeMoveOptimizer.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/EdgeMoveOptimizer.java	Wed Jun 15 17:47:05 2011 +0200
@@ -25,8 +25,10 @@
 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.lir.*;
+import com.oracle.max.graal.graph.*;
 
 /**
  * This class optimizes moves, particularly those that result from eliminating SSA form.
@@ -190,6 +192,12 @@
         List<LIRInstruction> instructions = block.lir().instructionsList();
 
         assert numSux == 2 : "method should not be called otherwise";
+
+        if ( instructions.get(instructions.size() - 1).code != LIROpcode.Branch) {
+            for (Node n : block.getInstructions()) {
+                TTY.println("instr: " + n);
+            }
+        }
         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 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Wed Jun 15 17:47:05 2011 +0200
@@ -246,7 +246,7 @@
                     }
                 }
             }
-            if (!(instr instanceof Merge) && instr != instr.graph().start()) {
+            if (instr != instr.graph().start()) {
                 walkState(instr, stateAfter);
                 doRoot((Value) instr);
             }
@@ -260,9 +260,8 @@
                 }
             }
         }
-        if (block.blockSuccessors().size() >= 1 && (block.getInstructions().size() == 0  || !jumpsToNextBlock(block.getInstructions().get(block.getInstructions().size() - 1)))) {
-            moveToPhi();
-            block.lir().jump(block.blockSuccessors().get(0));
+        if (block.blockSuccessors().size() >= 1 && !jumpsToNextBlock(block.lastInstruction())) {
+            block.lir().jump(getLIRBlock((FixedNode) block.lastInstruction().successors().get(0)));
         }
 
         if (GraalOptions.TraceLIRGeneratorLevel >= 1) {
@@ -274,8 +273,13 @@
         blockDoEpilog();
     }
 
+    @Override
+    public void visitMerge(Merge x) {
+        // Nothing to do.
+    }
+
     private static boolean jumpsToNextBlock(Node node) {
-        return node instanceof BlockEnd || node instanceof Anchor;
+        return node instanceof BlockEnd || node instanceof EndNode || node instanceof LoopEnd;
     }
 
     @Override
@@ -455,12 +459,6 @@
     @Override
     public void visitAnchor(Anchor x) {
         setNoResult(x);
-
-        // emit phi-instruction moves after safepoint since this simplifies
-        // describing the state at the safepoint.
-
-        moveToPhi();
-        lir.jump(getLIRBlock(x.next()));
     }
 
     @Override
@@ -697,7 +695,7 @@
         }
     }
 
-    protected LIRBlock getLIRBlock(Instruction b) {
+    protected LIRBlock getLIRBlock(FixedNode b) {
         if (b == null) {
             return null;
         }
@@ -1403,50 +1401,44 @@
         return null;
     }
 
-    protected void moveToPhi() {
-        // Moves all stack values into their phi position
-        LIRBlock bb = currentBlock;
-        if (bb.numberOfSux() == 1) {
-            LIRBlock sux = bb.suxAt(0);
-            assert sux.numberOfPreds() > 0 : "invalid CFG";
-
-            // a block with only one predecessor never has phi functions
-            if (sux.numberOfPreds() > 1) {
+    @Override
+    public void visitEndNode(EndNode end) {
+        setNoResult(end);
+        Merge merge = end.merge();
+        moveToPhi(merge, merge.endIndex(end));
+        lir.jump(getLIRBlock(end.merge()));
+    }
 
 
-                List<Phi> phis = getPhis(sux);
-
-                if (phis != null) {
-
-                    int predIndex = 0;
-                    for (; predIndex < sux.numberOfPreds(); ++predIndex) {
-                        if (sux.predAt(predIndex) == bb) {
-                            break;
-                        }
-                    }
-                    assert predIndex < sux.numberOfPreds();
+    @Override
+    public void visitLoopEnd(LoopEnd x) {
+        setNoResult(x);
+        moveToPhi(x.loopBegin(), x.loopBegin().endCount());
+        lir.jump(getLIRBlock(x.loopBegin()));
+    }
 
-                    PhiResolver resolver = new PhiResolver(this);
-                    for (Phi phi : phis) {
-                        if (!phi.isDead()) {
-                            Value curVal = phi.valueAt(predIndex);
-                            if (curVal != null && curVal != phi) {
-                                if (curVal instanceof Phi) {
-                                    operandForPhi((Phi) curVal);
-                                }
-                                CiValue operand = curVal.operand();
-                                if (operand.isIllegal()) {
-                                    assert curVal instanceof Constant || curVal instanceof Local : "these can be produced lazily" + curVal + "/" + phi;
-                                    operand = operandForInstruction(curVal);
-                                }
-                                resolver.move(operand, operandForPhi(phi));
-                            }
+    private void moveToPhi(Merge merge, int nextSuccIndex) {
+        PhiResolver resolver = new PhiResolver(this);
+        for (Node n : merge.usages()) {
+            if (n instanceof Phi) {
+                Phi phi = (Phi) n;
+                if (!phi.isDead()) {
+                    Value curVal = phi.valueAt(nextSuccIndex);
+                    if (curVal != null && curVal != phi) {
+                        if (curVal instanceof Phi) {
+                            operandForPhi((Phi) curVal);
                         }
+                        CiValue operand = curVal.operand();
+                        if (operand.isIllegal()) {
+                            assert curVal instanceof Constant || curVal instanceof Local : "these can be produced lazily" + curVal + "/" + phi;
+                            operand = operandForInstruction(curVal);
+                        }
+                        resolver.move(operand, operandForPhi(phi));
                     }
-                    resolver.dispose();
                 }
             }
         }
+        resolver.dispose();
     }
 
     /**
diff -r 4a64ffd60c03 -r cbece91420af 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	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java	Wed Jun 15 17:47:05 2011 +0200
@@ -69,6 +69,8 @@
      */
     public void build() {
         new GraphBuilderPhase(compilation, compilation.method, false, false).apply(compilation.graph);
+
+
         printGraph("After GraphBuilding", compilation.graph);
 
         if (GraalOptions.TestGraphDuplication) {
@@ -98,8 +100,6 @@
 
         new LoweringPhase().apply(graph);
 
-        new SplitCriticalEdgesPhase().apply(graph);
-
         IdentifyBlocksPhase schedule = new IdentifyBlocksPhase(true);
         schedule.apply(graph);
 
@@ -135,7 +135,7 @@
                 valueToBlock.put(i, b);
             }
         }
-        startBlock = lirBlocks.get(0);
+        startBlock = valueToBlock.get(graph.start());
         assert startBlock != null;
         assert startBlock.blockPredecessors().size() == 0;
 
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/BlockEnd.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/BlockEnd.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/BlockEnd.java	Wed Jun 15 17:47:05 2011 +0200
@@ -51,14 +51,14 @@
     /**
      * The list of instructions that produce input for this instruction.
      */
-    public Instruction blockSuccessor(int index) {
+    public FixedNode blockSuccessor(int index) {
         assert index >= 0 && index < blockSuccessorCount;
-        return (Instruction) successors().get(super.successorCount() + SUCCESSOR_COUNT + index);
+        return (FixedNode) successors().get(super.successorCount() + SUCCESSOR_COUNT + index);
     }
 
-    public Instruction setBlockSuccessor(int index, Instruction n) {
+    public FixedNode setBlockSuccessor(int index, FixedNode n) {
         assert index >= 0 && index < blockSuccessorCount;
-        return (Merge) successors().set(super.successorCount() + SUCCESSOR_COUNT + index, n);
+        return (FixedNode) successors().set(super.successorCount() + SUCCESSOR_COUNT + index, n);
     }
 
     public int blockSuccessorCount() {
@@ -87,19 +87,6 @@
     }
 
     /**
-     * Gets the block begin associated with this block end.
-     * @return the beginning of this basic block
-     */
-    public Merge begin() {
-        for (Node n : predecessors()) {
-            if (n instanceof Merge) {
-                return (Merge) n;
-            }
-        }
-        return null;
-    }
-
-    /**
      * Substitutes a successor block in this block end's successor list. Note that
      * this method updates all occurrences in the list.
      * @param oldSucc the old successor to replace
@@ -121,7 +108,7 @@
      * Gets the successor corresponding to the default (fall through) case.
      * @return the default successor
      */
-    public Instruction defaultSuccessor() {
+    public FixedNode defaultSuccessor() {
         return blockSuccessor(blockSuccessorCount - 1);
     }
 
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Condition.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Condition.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Condition.java	Wed Jun 15 17:47:05 2011 +0200
@@ -121,7 +121,7 @@
             case AT: return BE;
             case AE: return BT;
         }
-        throw new IllegalArgumentException();
+        throw new IllegalArgumentException(this.toString());
     }
 
     /**
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java	Wed Jun 15 17:47:05 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.oracle.max.graal.compiler.ir;
+
+import com.oracle.max.graal.compiler.debug.*;
+import com.oracle.max.graal.graph.*;
+import com.sun.cri.ci.*;
+
+
+public final class EndNode extends FixedNode {
+    public static final int SUCCESSOR_COUNT = 0;
+    public static final int INPUT_COUNT = 0;
+    public EndNode(Graph graph) {
+        super(CiKind.Illegal, INPUT_COUNT, SUCCESSOR_COUNT, graph);
+    }
+
+    @Override
+    public void accept(ValueVisitor v) {
+        v.visitEndNode(this);
+    }
+
+    @Override
+    public void print(LogStream out) {
+        out.print("end");
+    }
+
+    @Override
+    public Node copy(Graph into) {
+        return new EndNode(into);
+    }
+
+    public Merge merge() {
+        if (usages().size() == 0) {
+            return null;
+        } else {
+            assert usages().size() == 1;
+            return (Merge) usages().get(0);
+        }
+    }
+}
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ExceptionDispatch.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ExceptionDispatch.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ExceptionDispatch.java	Wed Jun 15 17:47:05 2011 +0200
@@ -64,7 +64,7 @@
     /**
      * Constructs a new ExceptionDispatch instruction.
      */
-    public ExceptionDispatch(Value exception, Instruction catchSuccessor, Instruction otherSuccessor, RiType catchType, Graph graph) {
+    public ExceptionDispatch(Value exception, FixedNode catchSuccessor, FixedNode otherSuccessor, RiType catchType, Graph graph) {
         super(CiKind.Int, 2, INPUT_COUNT, SUCCESSOR_COUNT, graph);
         setException(exception);
         setBlockSuccessor(0, otherSuccessor);
@@ -80,7 +80,7 @@
      * Gets the block corresponding to the catch block.
      * @return the true successor
      */
-    public Instruction catchSuccessor() {
+    public FixedNode catchSuccessor() {
         return blockSuccessor(1);
     }
 
@@ -88,7 +88,7 @@
      * Gets the block corresponding to the rest of the dispatch chain.
      * @return the false successor
      */
-    public Instruction otherSuccessor() {
+    public FixedNode otherSuccessor() {
         return blockSuccessor(0);
     }
 
@@ -97,7 +97,7 @@
      * @param istrue {@code true} if the true successor is requested, {@code false} otherwise
      * @return the corresponding successor
      */
-    public Instruction successor(boolean istrue) {
+    public FixedNode successor(boolean istrue) {
         return blockSuccessor(istrue ? 1 : 0);
     }
 
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/If.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/If.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/If.java	Wed Jun 15 17:47:05 2011 +0200
@@ -67,7 +67,7 @@
      * Gets the block corresponding to the true successor.
      * @return the true successor
      */
-    public Instruction trueSuccessor() {
+    public FixedNode trueSuccessor() {
         return blockSuccessor(0);
     }
 
@@ -75,7 +75,7 @@
      * Gets the block corresponding to the false successor.
      * @return the false successor
      */
-    public Instruction falseSuccessor() {
+    public FixedNode falseSuccessor() {
         return blockSuccessor(1);
     }
 
@@ -84,7 +84,7 @@
      * @param istrue {@code true} if the true successor is requested, {@code false} otherwise
      * @return the corresponding successor
      */
-    public Instruction successor(boolean istrue) {
+    public FixedNode successor(boolean istrue) {
         return blockSuccessor(istrue ? 0 : 1);
     }
 
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Instruction.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Instruction.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Instruction.java	Wed Jun 15 17:47:05 2011 +0200
@@ -22,8 +22,6 @@
  */
 package com.oracle.max.graal.compiler.ir;
 
-import java.util.*;
-
 import com.oracle.max.graal.compiler.*;
 import com.oracle.max.graal.compiler.value.*;
 import com.oracle.max.graal.graph.*;
@@ -62,11 +60,11 @@
      * Links to next instruction in a basic block, to {@code null} if this instruction is the end of a basic block or to
      * itself if not in a block.
      */
-    public Instruction next() {
-        return (Instruction) successors().get(super.successorCount() + SUCCESSOR_NEXT);
+    public FixedNode next() {
+        return (FixedNode) successors().get(super.successorCount() + SUCCESSOR_NEXT);
     }
 
-    public Node setNext(Instruction next) {
+    public Node setNext(FixedNode next) {
         return successors().set(super.successorCount() + SUCCESSOR_NEXT, next);
     }
 
@@ -88,28 +86,6 @@
         GraalMetrics.HIRInstructions++;
     }
 
-
-    /**
-     * Gets the list of predecessors of this block.
-     * @return the predecessor list
-     */
-    @SuppressWarnings({ "unchecked", "rawtypes" })
-    public List<Instruction> blockPredecessors() {
-        return (List) Collections.unmodifiableList(predecessors());
-    }
-
-    /**
-     * Get the number of predecessors.
-     * @return the number of predecessors
-     */
-    public int numberOfPreds() {
-        return predecessors().size();
-    }
-
-    public Instruction predAt(int j) {
-        return (Instruction) predecessors().get(j);
-    }
-
     /**
      * Gets the state after the instruction, if it is recorded.
      * @return the state after the instruction
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Local.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Local.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Local.java	Wed Jun 15 17:47:05 2011 +0200
@@ -26,7 +26,6 @@
 
 import com.oracle.max.graal.compiler.debug.*;
 import com.oracle.max.graal.graph.*;
-import com.sun.cri.bytecode.*;
 import com.sun.cri.ci.*;
 import com.sun.cri.ri.*;
 
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java	Wed Jun 15 17:47:05 2011 +0200
@@ -73,6 +73,23 @@
         v.visitMerge(this);
     }
 
+    public int endIndex(EndNode end) {
+        assert inputs().variablePart().contains(end);
+        return inputs().variablePart().indexOf(end);
+    }
+
+    public void addEnd(EndNode end) {
+        inputs().variablePart().add(end);
+    }
+
+    public int endCount() {
+        return inputs().variablePart().size();
+    }
+
+    public EndNode endAt(int index) {
+        return (EndNode) inputs().variablePart().get(index);
+    }
+
     @Override
     public String toString() {
         StringBuilder builder = new StringBuilder();
@@ -96,7 +113,6 @@
             }
             hasSucc = true;
         }
-
         return builder.toString();
     }
 
@@ -263,18 +279,17 @@
     @Override
     public Node copy(Graph into) {
         assert getClass() == Merge.class : "copy of " + getClass();
-        Merge x = new Merge(into);
-        return x;
+        return new Merge(into);
     }
 
-    public void removePhiPredecessor(Node pred) {
-        int predIndex = predecessors().lastIndexOf(pred);
+    public void removeEnd(EndNode pred) {
+        int predIndex = inputs().variablePart().indexOf(pred);
         assert predIndex != -1;
+        inputs().variablePart().remove(predIndex);
 
         for (Node usage : usages()) {
             if (usage instanceof Phi) {
                 Phi phi = (Phi) usage;
-//                assert phi.valueCount() == predecessors().size();
                 phi.removeInput(predIndex);
             }
         }
diff -r 4a64ffd60c03 -r cbece91420af 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	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java	Wed Jun 15 17:47:05 2011 +0200
@@ -37,16 +37,13 @@
     private static final int INPUT_COUNT = 1;
     private static final int INPUT_MERGE = 0;
 
-    private final int maxValues;
-
     private static final int SUCCESSOR_COUNT = 0;
 
-    private int usedInputCount;
     private boolean isDead;
 
     @Override
     protected int inputCount() {
-        return super.inputCount() + INPUT_COUNT + maxValues;
+        return super.inputCount() + INPUT_COUNT;
     }
 
     @Override
@@ -61,24 +58,12 @@
         return (Merge) inputs().get(super.inputCount() + INPUT_MERGE);
     }
 
-    public Value setMerge(Value n) {
-        return (Merge) inputs().set(super.inputCount() + INPUT_MERGE, n);
+    public void setMerge(Value n) {
+        inputs().set(super.inputCount() + INPUT_MERGE, n);
     }
 
-    /**
-     * Create a new Phi for the specified join block and local variable (or operand stack) slot.
-     * @param kind the type of the variable
-     * @param merge the join point
-     * @param graph
-     */
     public Phi(CiKind kind, Merge merge, Graph graph) {
-        this(kind, merge, DEFAULT_MAX_VALUES, graph);
-    }
-
-    public Phi(CiKind kind, Merge merge, int maxValues, Graph graph) {
-        super(kind, INPUT_COUNT + maxValues, SUCCESSOR_COUNT, graph);
-        this.maxValues = maxValues;
-        usedInputCount = 0;
+        super(kind, INPUT_COUNT, SUCCESSOR_COUNT, graph);
         setMerge(merge);
     }
 
@@ -89,11 +74,11 @@
      * @return the instruction that produced the value in the i'th predecessor
      */
     public Value valueAt(int i) {
-        return (Value) inputs().get(INPUT_COUNT + i);
+        return (Value) inputs().variablePart().get(i);
     }
 
-    public Node setValueAt(int i, Node x) {
-        return inputs().set(INPUT_COUNT + i, x);
+    public void setValueAt(int i, Value x) {
+        inputs().set(INPUT_COUNT + i, x);
     }
 
     /**
@@ -101,7 +86,7 @@
      * @return the number of inputs in this phi
      */
     public int valueCount() {
-        return usedInputCount;
+        return inputs().variablePart().size();
     }
 
     @Override
@@ -144,36 +129,17 @@
         return "Phi: (" + str + ")";
     }
 
-    public Phi addInput(Node y) {
-        assert !this.isDeleted() && !y.isDeleted();
-        Phi phi = this;
-        if (usedInputCount == maxValues) {
-            phi = new Phi(kind, merge(), maxValues * 2, graph());
-            for (int i = 0; i < valueCount(); ++i) {
-                phi.addInput(valueAt(i));
-            }
-            phi.addInput(y);
-            this.replace(phi);
-        } else {
-            setValueAt(usedInputCount++, y);
-        }
-        return phi;
+    public void addInput(Node y) {
+        inputs().variablePart().add(y);
     }
 
     public void removeInput(int index) {
-        assert index < valueCount() : "index: " + index + ", valueCount: " + valueCount() + "@phi " + id();
-        setValueAt(index, Node.Null);
-        for (int i = index + 1; i < valueCount(); ++i) {
-            setValueAt(i - 1, valueAt(i));
-        }
-        setValueAt(valueCount() - 1, Node.Null);
-        usedInputCount--;
+        inputs().variablePart().remove(index);
     }
 
     @Override
     public Node copy(Graph into) {
-        Phi x = new Phi(kind, null, maxValues, into);
-        x.usedInputCount = usedInputCount;
+        Phi x = new Phi(kind, null, into);
         x.isDead = isDead;
         return x;
     }
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Value.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Value.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Value.java	Wed Jun 15 17:47:05 2011 +0200
@@ -134,19 +134,6 @@
         return null; // default: unknown declared type
     }
 
-    /**
-     * Apply the specified closure to all the input values of this instruction.
-     * @param closure the closure to apply
-     */
-    public void inputValuesDo(ValueClosure closure) {
-        for (int i = 0; i < inputs().size(); i++) {
-            inputs().set(i, closure.apply((Value) inputs().get(i)));
-        }
-        for (int i = 0; i < successors().size(); i++) {
-            successors().set(i, closure.apply((Value) successors().get(i)));
-        }
-    }
-
     @Override
     public String toString() {
         StringBuilder builder = new StringBuilder();
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ValueVisitor.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ValueVisitor.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ValueVisitor.java	Wed Jun 15 17:47:05 2011 +0200
@@ -39,6 +39,7 @@
     public abstract void visitConstant(Constant i);
     public abstract void visitConvert(Convert i);
     public abstract void visitExceptionObject(ExceptionObject i);
+    public abstract void visitEndNode(EndNode i);
     public abstract void visitFrameState(FrameState i);
     public abstract void visitAnchor(Anchor i);
     public abstract void visitIf(If i);
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java	Wed Jun 15 17:47:05 2011 +0200
@@ -22,8 +22,6 @@
  */
 package com.oracle.max.graal.compiler.phases;
 
-import java.util.*;
-
 import com.oracle.max.graal.compiler.*;
 import com.oracle.max.graal.compiler.gen.*;
 import com.oracle.max.graal.compiler.ir.*;
@@ -78,7 +76,6 @@
 
         new PhiSimplifier(graph);
 
-
         if (GraalOptions.TraceDeadCodeElimination) {
             System.out.printf("dead code elimination finished\n");
         }
@@ -90,28 +87,28 @@
 
     private void iterateSuccessors() {
         for (Node current : flood) {
-            for (Node successor : current.successors()) {
-                flood.add(successor);
+            if (current instanceof EndNode) {
+                EndNode end = (EndNode) current;
+                flood.add(end.merge());
+            } else {
+                for (Node successor : current.successors()) {
+                    flood.add(successor);
+                }
             }
         }
     }
 
     private void disconnectCFGNodes() {
         for (Node node : graph.getNodes()) {
+            if (node != Node.Null && !flood.isMarked(node) && node instanceof EndNode) {
+                EndNode end = (EndNode) node;
+                Merge merge = end.merge();
+                merge.removeEnd(end);
+            }
+        }
+
+        for (Node node : graph.getNodes()) {
             if (node != Node.Null && !flood.isMarked(node) && isCFG(node)) {
-                if (node instanceof LoopEnd) {
-                    assert ((LoopEnd) node).loopBegin() != null : "node " + node;
-                    brokenLoops.add(((LoopEnd) node).loopBegin());
-                }
-                // iterate backwards so that the predecessor indexes in removePhiPredecessor are correct
-                for (int i = node.successors().size() - 1; i >= 0; i--) {
-                    Node successor = node.successors().get(i);
-                    if (successor != Node.Null && flood.isMarked(successor)) {
-                        if (successor instanceof Merge) {
-                            ((Merge) successor).removePhiPredecessor(node);
-                        }
-                    }
-                }
                 node.successors().clearAll();
                 node.inputs().clearAll();
             }
diff -r 4a64ffd60c03 -r cbece91420af 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	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java	Wed Jun 15 17:47:05 2011 +0200
@@ -162,7 +162,7 @@
         // 1. create the start block
         Block startBlock = nextBlock(Instruction.SYNCHRONIZATION_ENTRY_BCI);
         markOnWorkList(startBlock);
-        lastInstr = createTarget(startBlock, frameState);
+        lastInstr = (Instruction) createTarget(startBlock, frameState);
         graph.start().setStart(lastInstr);
 
         if (isSynchronized(method.accessFlags())) {
@@ -193,11 +193,7 @@
         for (Node n : graph.getNodes()) {
             if (n instanceof Placeholder) {
                 Placeholder p = (Placeholder) n;
-                assert p.blockPredecessors().size() == 1;
-                Node pred = p.blockPredecessors().get(0);
-                int predIndex = p.predecessorsIndex().get(0);
-                pred.successors().setAndClear(predIndex, p, 0);
-                p.delete();
+                p.replace(p.next());
             }
         }
 
@@ -264,8 +260,7 @@
 
     private void finishStartBlock(Block startBlock) {
         assert bci() == 0;
-        Instruction target = createTargetAt(0, frameState);
-        appendGoto(target);
+        appendGoto(createTargetAt(0, frameState));
     }
 
     public void mergeOrClone(Block target, FrameStateAccess newState) {
@@ -305,9 +300,16 @@
                 assert !target.isLoopHeader;
                 Merge merge = new Merge(graph);
 
+
+
                 Placeholder p = (Placeholder) first;
+                assert p.predecessors().size() == 1;
                 assert p.next() == null;
-                p.replace(merge);
+
+                EndNode end = new EndNode(graph);
+                p.replace(end);
+                merge.addEnd(end);
+                //end.setNext(merge);
                 target.firstInstruction = merge;
                 merge.setStateBefore(existingState);
                 first = merge;
@@ -423,8 +425,7 @@
             }
             FrameState stateWithException = entryState.duplicateModified(bci, CiKind.Void, currentExceptionObject);
 
-            Instruction successor = createTarget(dispatchBlock, stateWithException);
-            currentNext.setNext(successor);
+            currentNext.setNext(createTarget(dispatchBlock, stateWithException));
             return entry;
         }
         return null;
@@ -657,14 +658,14 @@
         If ifNode = new If(new Compare(x, cond, y, graph), graph);
         append(ifNode);
         BlockMap.BranchOverride override = branchOverride.get(bci());
-        Instruction tsucc;
+        FixedNode tsucc;
         if (override == null || override.taken == false) {
             tsucc = createTargetAt(stream().readBranchDest(), frameState);
         } else {
             tsucc = createTarget(override.block, frameState);
         }
         ifNode.setBlockSuccessor(0, tsucc);
-        Instruction fsucc;
+        FixedNode fsucc;
         if (override == null || override.taken == true) {
             fsucc = createTargetAt(stream().nextBCI(), frameState);
         } else {
@@ -1110,11 +1111,11 @@
         return x;
     }
 
-    private Instruction createTargetAt(int bci, FrameStateAccess stateAfter) {
+    private FixedNode createTargetAt(int bci, FrameStateAccess stateAfter) {
         return createTarget(blockFromBci[bci], stateAfter);
     }
 
-    private Instruction createTarget(Block block, FrameStateAccess stateAfter) {
+    private FixedNode 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. startBci=" + block.startBci + ", " + block.getClass().getSimpleName() + ", " + block.firstInstruction.next();
@@ -1125,8 +1126,6 @@
 
         if (block.firstInstruction == null) {
             if (block.isLoopHeader) {
-//                block.firstInstruction = new Merge(block.startBci, graph);
-
                 LoopBegin loopBegin = new LoopBegin(graph);
                 LoopEnd loopEnd = new LoopEnd(graph);
                 loopEnd.setLoopBegin(loopBegin);
@@ -1138,11 +1137,22 @@
         mergeOrClone(block, stateAfter);
         addToWorkList(block);
 
+        FixedNode result = null;
         if (block.firstInstruction instanceof LoopBegin && isVisited(block)) {
-            return ((LoopBegin) block.firstInstruction).loopEnd();
+            result = ((LoopBegin) block.firstInstruction).loopEnd();
         } else {
-            return block.firstInstruction;
+            result = block.firstInstruction;
         }
+
+        assert result instanceof Merge || result instanceof Placeholder : result;
+
+        if (result instanceof Merge) {
+            EndNode end = new EndNode(graph);
+            //end.setNext(result);
+            ((Merge) result).addEnd(end);
+            result = end;
+        }
+        return result;
     }
 
     private Value synchronizedObject(FrameStateAccess state, RiMethod target) {
@@ -1201,7 +1211,8 @@
                 } else {
                     end.delete();
                     Merge merge = new Merge(graph);
-                    merge.successors().setAndClear(merge.nextIndex(), begin, begin.nextIndex());
+                    merge.setNext(begin.next());
+                    begin.setNext(null);
                     begin.replace(merge);
                 }
             }
@@ -1245,20 +1256,20 @@
 
             Block nextBlock = block.next == null ? unwindBlock() : block.next;
             if (block.handler.catchType().isResolved()) {
-                Instruction catchSuccessor = createTarget(blockFromBci[block.handler.handlerBCI()], frameState);
-                Instruction nextDispatch = createTarget(nextBlock, frameState);
+                FixedNode catchSuccessor = createTarget(blockFromBci[block.handler.handlerBCI()], frameState);
+                FixedNode nextDispatch = createTarget(nextBlock, frameState);
                 append(new ExceptionDispatch(frameState.stackAt(0), catchSuccessor, nextDispatch, block.handler.catchType(), graph));
             } else {
                 Deoptimize deopt = new Deoptimize(DeoptAction.InvalidateRecompile, graph);
                 deopt.setMessage("unresolved " + block.handler.catchType().name());
                 append(deopt);
-                Instruction nextDispatch = createTarget(nextBlock, frameState);
+                FixedNode nextDispatch = createTarget(nextBlock, frameState);
                 appendGoto(nextDispatch);
             }
         }
     }
 
-    private void appendGoto(Instruction target) {
+    private void appendGoto(FixedNode target) {
         lastInstr.setNext(target);
     }
 
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java	Wed Jun 15 17:47:05 2011 +0200
@@ -236,6 +236,7 @@
             System.out.println("inlining " + name + ": " + frameStates.size() + " frame states, " + nodes.size() + " nodes");
         }
 
+        assert invoke.successors().get(0) != null : invoke;
         assert invoke.predecessors().size() == 1 : "size: " + invoke.predecessors().size();
         Instruction pred;
         if (withReceiver) {
@@ -243,7 +244,7 @@
             clipNode.setNode(new IsNonNull(parameters[0], compilation.graph));
             pred = clipNode;
         } else {
-            pred = new Merge(compilation.graph);
+            pred = new Placeholder(compilation.graph);//(Instruction) invoke.predecessors().get(0);//new Merge(compilation.graph);
         }
         invoke.predecessors().get(0).successors().replace(invoke, pred);
         replacements.put(startNode, pred);
@@ -261,6 +262,10 @@
             }
         }
 
+        if (pred instanceof Placeholder) {
+            pred.replace(((Placeholder)pred).next());
+        }
+
         if (returnNode != null) {
             List<Node> usages = new ArrayList<Node>(invoke.usages());
             for (Node usage : usages) {
@@ -272,18 +277,8 @@
             }
             Node returnDuplicate = duplicates.get(returnNode);
             returnDuplicate.inputs().clearAll();
-
-            Merge mergeAfter = new Merge(compilation.graph);
-
-            assert returnDuplicate.predecessors().size() == 1;
-            Node returnPred = returnDuplicate.predecessors().get(0);
-            int index = returnDuplicate.predecessorsIndex().get(0);
-            mergeAfter.successors().setAndClear(0, invoke, 0);
-            returnPred.successors().set(index, mergeAfter);
-
-            returnDuplicate.delete();
-
-            mergeAfter.setStateBefore(stateAfter);
+            returnDuplicate.replace(invoke.next());
+            invoke.setNext(null);
         }
 
         if (exceptionEdge != null) {
@@ -298,14 +293,7 @@
                     usage.inputs().replace(obj, unwindDuplicate.exception());
                 }
                 unwindDuplicate.inputs().clearAll();
-
-                assert unwindDuplicate.predecessors().size() == 1;
-                Node unwindPred = unwindDuplicate.predecessors().get(0);
-                int index = unwindDuplicate.predecessorsIndex().get(0);
-                unwindPred.successors().setAndClear(index, obj, 0);
-
-                obj.inputs().clearAll();
-                unwindDuplicate.delete();
+                unwindDuplicate.replace(obj.next());
             }
         }
 
diff -r 4a64ffd60c03 -r cbece91420af 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	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoweringPhase.java	Wed Jun 15 17:47:05 2011 +0200
@@ -24,6 +24,7 @@
 
 import com.oracle.max.graal.compiler.ir.*;
 import com.oracle.max.graal.compiler.schedule.*;
+import com.oracle.max.graal.compiler.util.*;
 import com.oracle.max.graal.graph.*;
 
 public class LoweringPhase extends Phase {
@@ -33,21 +34,22 @@
         s.apply(graph);
 
         for (Block b : s.getBlocks()) {
-            final Node firstNode = b.firstNode();
+            //final Node firstNode = b.firstNode();
 
             final LoweringTool loweringTool = new LoweringTool() {
                 @Override
                 public Node createStructuredBlockAnchor() {
-                    if (!(firstNode instanceof Anchor) && !(firstNode instanceof Merge)) {
-                        Anchor a = new Anchor(graph);
-                        assert firstNode.predecessors().size() == 1;
-                        Node pred = firstNode.predecessors().get(0);
-                        int predIndex = firstNode.predecessorsIndex().get(0);
-                        a.successors().setAndClear(Instruction.SUCCESSOR_NEXT, pred, predIndex);
-                        pred.successors().set(predIndex, a);
-                        return a;
-                    }
-                    return firstNode;
+                    throw Util.unimplemented();
+//                    if (!(firstNode instanceof Anchor) && !(firstNode instanceof Merge)) {
+//                        Anchor a = new Anchor(graph);
+//                        assert firstNode.predecessors().size() == 1;
+//                        Node pred = firstNode.predecessors().get(0);
+//                        int predIndex = firstNode.predecessorsIndex().get(0);
+//                        a.successors().setAndClear(Instruction.SUCCESSOR_NEXT, pred, predIndex);
+//                        pred.successors().set(predIndex, a);
+//                        return a;
+//                    }
+//                    return firstNode;
                 }
             };
 
diff -r 4a64ffd60c03 -r cbece91420af 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	Wed Jun 15 17:41:00 2011 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,51 +0,0 @@
-/*
- * Copyright (c) 2009, 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.phases;
-
-import java.util.*;
-
-import com.oracle.max.graal.compiler.ir.*;
-import com.oracle.max.graal.compiler.schedule.*;
-import com.oracle.max.graal.graph.*;
-
-
-public class SplitCriticalEdgesPhase extends Phase {
-
-    @Override
-    protected void run(Graph graph) {
-        List<Node> nodes = graph.getNodes();
-        for (int i = 0; i < nodes.size(); ++i) {
-            Node n = nodes.get(i);
-            if (IdentifyBlocksPhase.trueSuccessorCount(n) > 1) {
-                for (int j = 0; j < n.successors().size(); ++j) {
-                    Node succ = n.successors().get(j);
-                    if (IdentifyBlocksPhase.truePredecessorCount(succ) > 1) {
-                        Anchor a = new Anchor(graph);
-                        a.successors().setAndClear(Instruction.SUCCESSOR_NEXT, n, j);
-                        n.successors().set(j, a);
-                    }
-                }
-            }
-        }
-    }
-}
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java	Wed Jun 15 17:47:05 2011 +0200
@@ -78,6 +78,13 @@
     private Block assignBlock(Node n, Block b) {
         assert nodeToBlock.get(n) == null;
         nodeToBlock.set(n, b);
+        for (Node input : n.inputs()) {
+            if (input instanceof FrameState) {
+                assert nodeToBlock.get(n) == null;
+                nodeToBlock.set(n, b);
+            }
+        }
+
         if (b.firstNode() == null) {
             b.setFirstNode(n);
             b.setLastNode(n);
@@ -91,6 +98,26 @@
         return b;
     }
 
+    private Block assignBlockNew(Node n, Block b) {
+        if (b == null) {
+            b = createBlock();
+        }
+
+        assert nodeToBlock.get(n) == null;
+        nodeToBlock.set(n, b);
+        if (b.lastNode() == null) {
+            b.setFirstNode(n);
+            b.setLastNode(n);
+        } else {
+            if (b.firstNode() != b.lastNode()) {
+                b.getInstructions().add(0, b.firstNode());
+            }
+            b.setFirstNode(n);
+        }
+
+        return b;
+    }
+
     public static boolean isFixed(Node n) {
         return n != null && ((n instanceof FixedNode) || n == n.graph().start());
     }
@@ -100,69 +127,51 @@
     }
 
     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;
+        for (Node n : graph.getNodes()) {
+            if (n != null) {
+                if (n instanceof EndNode || n instanceof Return || n instanceof Unwind || n instanceof LoopEnd) {
+                    Block block = null;
+                    while (nodeToBlock.get(n) == null) {
+                        if (block != null && IdentifyBlocksPhase.trueSuccessorCount(n) > 1) {
+                            // We are at a split node => start a new block.
+                            block = null;
                         }
+                        block = assignBlockNew(n, block);
+                        if (n.predecessors().size() == 0) {
+                            // Either dead code or at a merge node => stop iteration.
+                            break;
+                        }
+                        assert n.predecessors().size() == 1 : "preds: " + n;
+                        n = n.predecessors().get(0);
                     }
                 }
-
-                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);
-                }
-            }
-
+        for (Block block : blocks) {
+            Node n = block.firstNode();
             if (n instanceof Merge) {
                 for (Node usage : n.usages()) {
                     if (usage instanceof Phi) {
                         nodeToBlock.set(usage, block);
                     }
                 }
+                Merge m = (Merge) n;
+                for (int i=0; i<m.endCount(); ++i) {
+                    EndNode end = m.endAt(i);
+                    Block predBlock = nodeToBlock.get(end);
+                    predBlock.addSuccessor(block);
+                }
+            } else {
+                for (Node pred : n.predecessors()) {
+                    if (isFixed(pred)) {
+                        Block predBlock = nodeToBlock.get(pred);
+                        predBlock.addSuccessor(block);
+                    }
+                }
             }
         }
 
@@ -186,8 +195,8 @@
         if (scheduleAllNodes) {
 
             // Add successors of loop end nodes. Makes the graph cyclic.
-            for (Node n : blockBeginNodes) {
-                Block block = nodeToBlock.get(n);
+            for (Block block : blocks) {
+                Node n = block.firstNode();
                 if (n instanceof LoopBegin) {
                     LoopBegin loopBegin = (LoopBegin) n;
                     nodeToBlock.get(loopBegin.loopEnd()).addSuccessor(block);
@@ -295,10 +304,9 @@
                 }
             } 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));
-                    }
+                for (int i=0; i<merge.endCount(); ++i) {
+                    EndNode pred = merge.endAt(i);
+                    block = getCommonDominator(block, nodeToBlock.get(pred));
                 }
             } else {
                 block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage));
@@ -335,6 +343,8 @@
         assert !map.isMarked(b.firstNode()) && nodeToBlock.get(b.firstNode()) == b;
 
         boolean scheduleFirst = true;
+        assert !instructions.contains(b.lastNode());
+        assert !instructions.contains(b.firstNode());
 
         if (b.firstNode() == b.lastNode()) {
             Node node = b.firstNode();
@@ -349,6 +359,7 @@
             addToSorting(b, i, sortedInstructions, map);
         }
         addToSorting(b, b.lastNode(), sortedInstructions, map);
+        assert sortedInstructions.get(sortedInstructions.size() - 1) == b.lastNode() : "lastNode=" + b.lastNode() + ", firstNode=" + b.firstNode();
         b.setInstructions(sortedInstructions);
     }
 
@@ -357,8 +368,13 @@
             return;
         }
 
+        FrameState state = null;
         for (Node input : i.inputs()) {
-            addToSorting(b, input, sortedInstructions, map);
+//            if (input instanceof FrameState) {
+//               state = (FrameState) input;
+//            } else {
+                addToSorting(b, input, sortedInstructions, map);
+//            }
         }
 
         for (Node pred : i.predecessors()) {
@@ -367,6 +383,10 @@
 
         map.mark(i);
 
+        if (state != null) {
+            addToSorting(b, state, sortedInstructions, map);
+        }
+
         for (Node succ : i.successors()) {
             if (succ instanceof FrameState) {
                 addToSorting(b, succ, sortedInstructions, map);
@@ -458,21 +478,4 @@
         }
         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 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java	Wed Jun 15 17:47:05 2011 +0200
@@ -466,11 +466,6 @@
     }
 
     @Override
-    public void visitMerge(Merge x) {
-        // nothing to do for now
-    }
-
-    @Override
     public void visitExceptionDispatch(ExceptionDispatch x) {
         // TODO ls: this needs some more work...
 
@@ -494,17 +489,6 @@
     }
 
     @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()));
-    }
-
-    @Override
     public void visitValueAnchor(ValueAnchor valueAnchor) {
         // nothing to do for ValueAnchors
     }
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java	Wed Jun 15 17:47:05 2011 +0200
@@ -377,28 +377,20 @@
                         phi = setupPhiForStack(block, i - localsSize);
                     }
 
-                    Phi originalPhi = phi;
                     if (phi.valueCount() == 0) {
-                        int size = block.predecessors().size();
+                        int size = block.endCount();
                         for (int j = 0; j < size; ++j) {
-                            phi = phi.addInput(x);
+                            phi.addInput(x);
                         }
-                        phi = phi.addInput((x == y) ? phi : y);
+                        phi.addInput((x == y) ? phi : y);
                     } else {
-                        phi = phi.addInput((x == y) ? phi : y);
-                    }
-                    if (originalPhi != phi) {
-                        for (int j = 0; j < other.localsSize() + other.stackSize(); ++j) {
-                            if (other.valueAt(j) == originalPhi) {
-                                other.setValueAt(j, phi);
-                            }
-                        }
+                        phi.addInput((x == y) ? phi : y);
                     }
 
                     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();
+                        assert phi.valueCount() == block.endCount() + 1 : "valueCount=" + phi.valueCount() + " predSize= " + block.endCount();
                     }
                }
             }
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java	Wed Jun 15 17:47:05 2011 +0200
@@ -171,7 +171,7 @@
                 if (target == null) {
                     target = newNodes.get(input);
                 }
-                node.inputs().set(i, target);
+                node.inputs().setOrExpand(i, target);
             }
         }
         for (Entry<Node, Node> entry : replacements.entrySet()) {
@@ -180,32 +180,31 @@
             for (int i = 0; i < oldNode.inputs().size(); i++) {
                 Node input = oldNode.inputs().get(i);
                 if (newNodes.containsKey(input)) {
-                    node.inputs().set(i, newNodes.get(input));
+                    node.inputs().setOrExpand(i, newNodes.get(input));
                 }
             }
         }
+        
         // re-wire successors
         for (Entry<Node, Node> entry : newNodes.entrySet()) {
             Node oldNode = entry.getKey();
             Node node = entry.getValue();
-            for (int i = 0; i < oldNode.predecessors().size(); i++) {
-                Node pred = oldNode.predecessors().get(i);
-                int predIndex = oldNode.predecessorsIndex().get(i);
-                Node source = replacements.get(pred);
-                if (source == null) {
-                    source = newNodes.get(pred);
+            for (int i = 0; i < oldNode.successors().size(); i++) {
+                Node succ = oldNode.successors().get(i);
+                Node target = replacements.get(succ);
+                if (target == null) {
+                    target = newNodes.get(succ);
                 }
-                source.successors().set(predIndex,  node);
+                node.successors().setOrExpand(i, target);
             }
         }
         for (Entry<Node, Node> entry : replacements.entrySet()) {
             Node oldNode = entry.getKey();
             Node node = entry.getValue();
-            for (int i = 0; i < oldNode.predecessors().size(); i++) {
-                Node pred = oldNode.predecessors().get(i);
-                int predIndex = oldNode.predecessorsIndex().get(i);
-                if (newNodes.containsKey(pred)) {
-                    newNodes.get(pred).successors().set(predIndex, node);
+            for (int i = 0; i < oldNode.successors().size(); i++) {
+                Node succ = oldNode.successors().get(i);
+                if (newNodes.containsKey(succ)) {
+                    node.successors().setOrExpand(i, newNodes.get(succ));
                 }
             }
         }
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java	Wed Jun 15 17:47:05 2011 +0200
@@ -39,7 +39,6 @@
     final NodeArray successors;
     final ArrayList<Node> usages;
     final ArrayList<Node> predecessors;
-    final ArrayList<Integer> predecessorsIndex;
 
     public Node(int inputCount, int successorCount, Graph graph) {
         assert graph != null : "cannot create a node for a null graph";
@@ -47,19 +46,14 @@
         this.id = graph.register(this);
         this.inputs = new NodeArray(this, inputCount);
         this.successors = new NodeArray(this, successorCount);
-        this.predecessors = new ArrayList<Node>();
-        this.usages = new ArrayList<Node>();
-        this.predecessorsIndex = new ArrayList<Integer>();
+        this.predecessors = new ArrayList<Node>(1);
+        this.usages = new ArrayList<Node>(4);
     }
 
     public List<Node> predecessors() {
         return Collections.unmodifiableList(predecessors);
     }
 
-    public List<Integer> predecessorsIndex() {
-        return Collections.unmodifiableList(predecessorsIndex);
-    }
-
     public List<Node> usages() {
         return Collections.unmodifiableList(usages);
     }
@@ -96,18 +90,19 @@
         }
         int z = 0;
         for (Node predecessor : predecessors) {
-            int predIndex = predecessorsIndex.get(z);
-            predecessor.successors.nodes[predIndex] = other;
+            for (int i=0; i<predecessor.successors.size(); i++) {
+                if (predecessor.successors.get(i) == this) {
+                    predecessor.successors.silentSet(i, other);
+                }
+            }
             ++z;
         }
         if (other != null) {
             other.usages.addAll(usages);
             other.predecessors.addAll(predecessors);
-            other.predecessorsIndex.addAll(predecessorsIndex);
         }
         usages.clear();
         predecessors.clear();
-        predecessorsIndex.clear();
         delete();
         return other;
     }
@@ -125,14 +120,12 @@
         }
         usages.clear();
         predecessors.clear();
-        predecessorsIndex.clear();
-        delete();
     }
 
     public void delete() {
         assert !isDeleted();
-        assert checkDeletion();
-        assert predecessorsIndex.size() == 0;
+        assert checkDeletion() : "Could not delete " + this;
+
         for (int i = 0; i < inputs.size(); ++i) {
             inputs.set(i, Null);
         }
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeArray.java
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeArray.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeArray.java	Wed Jun 15 17:47:05 2011 +0200
@@ -29,11 +29,14 @@
 public class NodeArray extends AbstractList<Node> {
 
     private final Node node;
-    final Node[] nodes;
+    private Node[] nodes;
+    private final int fixedLength;
+    private int variableLength;
 
     public NodeArray(Node node, int length) {
         this.node = node;
         this.nodes = new Node[length];
+        this.fixedLength = length;
     }
 
     @Override
@@ -50,14 +53,84 @@
         nodes[index] = node;
         return result;
     }
+    
+    public AbstractList<Node> variablePart() {
+        return new AbstractList<Node>() {
+
+            @Override
+            public Node get(int index) {
+                checkIndex(index);
+                return NodeArray.this.get(fixedLength + index);
+            }
+
+            @Override
+            public int size() {
+                return variableLength;
+            }
+
+            public Node set(int index, Node element) {
+                checkIndex(index);
+                return NodeArray.this.set(fixedLength + index, element);
+            }
+
+            public void add(int index, Node element) {
+                variableLength++;
+                checkIndex(index);
+                NodeArray.this.ensureSize();
+                for (int i=size() - 1; i > index; i--) {
+                    NodeArray.this.nodes[fixedLength + i] = NodeArray.this.nodes[fixedLength + i-1];
+                }
+                set(index, element);
+            }
+            
+            private void checkIndex(int index) {
+                if (index < 0 || index >= size()) {
+                    throw new IndexOutOfBoundsException();
+                }
+            }
+            
+            @Override
+            public Node remove(int index) {
+                checkIndex(index);
+                Node n = get(index);
+                set(index, Node.Null);
+                for (int i=index; i < size() - 1; i++) {
+                    NodeArray.this.nodes[fixedLength + i] = NodeArray.this.nodes[fixedLength + i + 1];
+                }
+                NodeArray.this.nodes[fixedLength + size() - 1] = Node.Null;
+                variableLength--;
+                assert variableLength >= 0;
+                return n;
+            }
+        };
+    }
+
+    private void ensureSize() {
+        if (size() > nodes.length) {
+            nodes = Arrays.copyOf(nodes, (nodes.length + 1)*2);
+        }
+    }
+    
+    public void setOrExpand(int index, Node node) {
+        if (index < 0) {
+            throw new IndexOutOfBoundsException();
+        }
+        
+        while (index >= size()) {
+            variablePart().add(Node.Null);
+        }
+        
+        set(index, node);
+    }
 
     @Override
     public Node set(int index, Node node) {
         assert !self().isDeleted() : "trying to set input/successor of deleted node: " + self().shortName();
         assert node == Node.Null || node.graph == self().graph : "node is from different graph: (this=" + self() + ") and (node=" + node + ")";
         assert node == Node.Null || node.id() != Node.DeletedID : "inserted node must not be deleted";
-        Node old = nodes[index];
-
+        assert node != self() || node.getClass().toString().contains("Phi") : "No direct circles allowed in the graph! " + node;
+        
+        Node old = get(index);
         if (old != node) {
             silentSet(index, node);
             if (self().inputs == this) {
@@ -72,15 +145,14 @@
                 if (old != null) {
                     for (int i = 0; i < old.predecessors.size(); ++i) {
                         Node cur = old.predecessors.get(i);
-                        if (cur == self() && old.predecessorsIndex.get(i) == index) {
+                        if (cur == self()) {
                             old.predecessors.remove(i);
-                            old.predecessorsIndex.remove(i);
+                            break;
                         }
                     }
                 }
                 if (node != null) {
                     node.predecessors.add(self());
-                    node.predecessorsIndex.add(index);
                 }
             }
         }
@@ -94,19 +166,26 @@
             set(i, other.get(i));
         }
     }
+    
+    private void checkIndex(int index) {
+        if (index < 0 || index >= size()) {
+            throw new IndexOutOfBoundsException();
+        }
+    }
 
     @Override
     public Node get(int index) {
+        checkIndex(index);
         return nodes[index];
     }
 
     @Override
     public Node[] toArray() {
-        return Arrays.copyOf(nodes, nodes.length);
+        return Arrays.copyOf(nodes, size());
     }
 
     boolean replaceFirstOccurrence(Node toReplace, Node replacement) {
-        for (int i = 0; i < nodes.length; i++) {
+        for (int i = 0; i < size(); i++) {
             if (nodes[i] == toReplace) {
                 nodes[i] = replacement;
                 return true;
@@ -121,7 +200,7 @@
 
     public int replace(Node toReplace, Node replacement) {
         int result = 0;
-        for (int i = 0; i < nodes.length; i++) {
+        for (int i = 0; i < size(); i++) {
             if (nodes[i] == toReplace) {
                 set(i, replacement);
                 result++;
@@ -136,7 +215,7 @@
 
     int silentReplace(Node toReplace, Node replacement) {
         int result = 0;
-        for (int i = 0; i < nodes.length; i++) {
+        for (int i = 0; i < size(); i++) {
             if (nodes[i] == toReplace) {
                 silentSet(i, replacement);
                 result++;
@@ -145,32 +224,13 @@
         return result;
     }
 
-    public void setAndClear(int index, Node clearedNode, int clearedIndex) {
-        assert !self().isDeleted() : "trying to setAndClear successor of deleted node: " + self().shortName();
-        assert self().successors == this;
-        Node value = clearedNode.successors.get(clearedIndex);
-        assert value != Node.Null;
-        clearedNode.successors.nodes[clearedIndex] = Node.Null;
-        set(index, Node.Null);
-        nodes[index] = value;
-
-        for (int i = 0; i < value.predecessors.size(); ++i) {
-            if (value.predecessors.get(i) == clearedNode && value.predecessorsIndex.get(i) == clearedIndex) {
-                value.predecessors.set(i, self());
-                value.predecessorsIndex.set(i, index);
-                return;
-            }
-        }
-        assert false;
-    }
-
     @Override
     public int size() {
-        return nodes.length;
+        return fixedLength + variableLength;
     }
 
     public void clearAll() {
-        for (int i = 0; i < nodes.length; i++) {
+        for (int i = 0; i < size(); i++) {
             set(i, Node.Null);
         }
     }
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java	Wed Jun 15 17:47:05 2011 +0200
@@ -77,6 +77,7 @@
     private void check(Node node) {
         assert node.graph == graph : "this node is not part of the graph";
         assert !isNew(node) : "this node (" + node.id() + ") was added to the graph after creating the node bitmap (" + bitMap.length() + ")";
+        assert !node.isDeleted() : "node " + node + " is deleted!";
     }
 
     @Override
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/Compiler.java
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/Compiler.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/Compiler.java	Wed Jun 15 17:47:05 2011 +0200
@@ -23,11 +23,13 @@
 package com.oracle.max.graal.runtime;
 
 import com.oracle.max.graal.compiler.*;
+import com.sun.cri.ri.*;
 
 public interface Compiler {
 
     VMEntries getVMEntries();
     VMExits getVMExits();
     GraalCompiler getCompiler();
+    RiType lookupType(String returnType, HotSpotTypeResolved accessingClass);
 
 }
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/CompilerImpl.java
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/CompilerImpl.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/CompilerImpl.java	Wed Jun 15 17:47:05 2011 +0200
@@ -155,4 +155,42 @@
         return vmExits;
     }
 
+    @Override
+    public RiType lookupType(String returnType, HotSpotTypeResolved accessingClass) {
+        if (returnType.length() == 1 && vmExits instanceof VMExitsNative) {
+            VMExitsNative exitsNative = (VMExitsNative) vmExits;
+            CiKind kind = CiKind.fromPrimitiveOrVoidTypeChar(returnType.charAt(0));
+            switch(kind) {
+                case Boolean:
+                    return exitsNative.typeBoolean;
+                case Byte:
+                    return exitsNative.typeByte;
+                case Char:
+                    return exitsNative.typeChar;
+                case Double:
+                    return exitsNative.typeDouble;
+                case Float:
+                    return exitsNative.typeFloat;
+                case Illegal:
+                    break;
+                case Int:
+                    return exitsNative.typeInt;
+                case Jsr:
+                    break;
+                case Long:
+                    return exitsNative.typeLong;
+                case Object:
+                    break;
+                case Short:
+                    return exitsNative.typeShort;
+                case Void:
+                    return exitsNative.typeVoid;
+                case Word:
+                    break;
+
+            }
+        }
+        return vmEntries.RiSignature_lookupType(returnType, accessingClass);
+    }
+
 }
diff -r 4a64ffd60c03 -r cbece91420af graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotSignature.java
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotSignature.java	Wed Jun 15 17:41:00 2011 +0200
+++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotSignature.java	Wed Jun 15 17:47:05 2011 +0200
@@ -117,7 +117,7 @@
         }
         RiType type = argumentTypes[index];
         if (type == null) {
-            type = compiler.getVMEntries().RiSignature_lookupType(arguments.get(index), (HotSpotTypeResolved) accessingClass);
+            type = compiler.lookupType(arguments.get(index), (HotSpotTypeResolved) accessingClass);
             argumentTypes[index] = type;
         }
         return type;
@@ -136,7 +136,7 @@
     @Override
     public RiType returnType(RiType accessingClass) {
         if (returnTypeCache == null) {
-            returnTypeCache = compiler.getVMEntries().RiSignature_lookupType(returnType, (HotSpotTypeResolved) accessingClass);
+            returnTypeCache = compiler.lookupType(returnType, (HotSpotTypeResolved) accessingClass);
         }
         return returnTypeCache;
     }