changeset 5026:b11561111585

Remove FrameStateAccess: Make FrameState immutable and move all modification logic into FrameStateBuilder
author Christian Wimmer <Christian.Wimmer@Oracle.com>
date Mon, 05 Mar 2012 09:55:54 -0800
parents df0deec2af08
children b0fe44319c71
files graal/com.oracle.max.cri/src/com/oracle/max/cri/xir/XirSite.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/DebugInfoBuilder.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InsertStateAfterPlaceholderPhase.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/Phase.java graal/com.oracle.max.graal.hotspot/src/com/oracle/max/graal/hotspot/ri/HotSpotRuntime.java graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/BciBlockMapping.java graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/FrameStateBuilder.java graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/GraphBuilderPhase.java graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/FrameState.java graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/PlaceholderNode.java graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/spi/FrameStateAccess.java
diffstat 13 files changed, 714 insertions(+), 890 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.max.cri/src/com/oracle/max/cri/xir/XirSite.java	Mon Mar 05 14:38:43 2012 +0100
+++ b/graal/com.oracle.max.cri/src/com/oracle/max/cri/xir/XirSite.java	Mon Mar 05 09:55:54 2012 -0800
@@ -22,8 +22,6 @@
  */
 package com.oracle.max.cri.xir;
 
-import com.oracle.max.cri.ci.*;
-
 /**
  * Encapsulates the notion of a site where XIR can be supplied. It is supplied to the {@link RiXirGenerator} by the
  * compiler for each place where XIR can be generated. This interface allows a number of queries, including the
@@ -32,13 +30,6 @@
 public interface XirSite {
 
     /**
-     * Gets the {@link CiCodePos code position} associated with this site. This is useful for inserting
-     * instrumentation at the XIR level.
-     * @return the code position if it is available; {@code null} otherwise
-     */
-    CiCodePos getCodePos();
-
-    /**
      * Checks whether the specified argument is guaranteed to be non-null at this site.
      * @param argument the argument
      * @return {@code true} if the argument is non null at this site
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java	Mon Mar 05 14:38:43 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java	Mon Mar 05 09:55:54 2012 -0800
@@ -186,6 +186,7 @@
     public static boolean OptReorderLoops                    = true;
     public static boolean OptEliminateGuards                 = true;
     public static boolean OptImplicitNullChecks              = true;
+    public static boolean OptLivenessAnalysis                = false;
 
     /**
      * Flag to turn on SSA-based register allocation, which is currently under development.
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/DebugInfoBuilder.java	Mon Mar 05 14:38:43 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/DebugInfoBuilder.java	Mon Mar 05 09:55:54 2012 -0800
@@ -106,13 +106,16 @@
     }
 
     private CiFrame computeFrameForState(FrameState state, LockScope locks) {
+        int numLocals = state.localsSize();
+        int numStack = state.stackSize();
         int numLocks = (locks != null && locks.callerState == state.outerFrameState()) ? locks.stateDepth + 1 : 0;
 
-        CiValue[] values = new CiValue[state.valuesSize() + numLocks];
-        int valueIndex = 0;
-
-        for (int i = 0; i < state.valuesSize(); i++) {
-            values[valueIndex++] = toCiValue(state.valueAt(i));
+        CiValue[] values = new CiValue[numLocals + numStack + numLocks];
+        for (int i = 0; i < numLocals; i++) {
+            values[i] = toCiValue(state.localAt(i));
+        }
+        for (int i = 0; i < numStack; i++) {
+            values[numLocals + i] = toCiValue(state.stackAt(i));
         }
 
         LockScope nextLock = locks;
@@ -122,7 +125,7 @@
             CiValue owner = toCiValue(nextLock.monitor.object());
             CiValue lockData = nextLock.lockData;
             boolean eliminated = nextLock.monitor.eliminated();
-            values[state.valuesSize() + nextLock.stateDepth] = new CiMonitorValue(owner, lockData, eliminated);
+            values[numLocals + numStack + nextLock.stateDepth] = new CiMonitorValue(owner, lockData, eliminated);
 
             nextLock = nextLock.outer;
         }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Mon Mar 05 14:38:43 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Mon Mar 05 09:55:54 2012 -0800
@@ -347,7 +347,7 @@
                 } else {
                     TTY.println("STATE CHANGE (singlePred)");
                     if (GraalOptions.TraceLIRGeneratorLevel >= 3) {
-                        TTY.println(fs.toDetailedString());
+                        TTY.println(fs.toString(Node.Verbosity.Debugger));
                     }
                 }
             }
@@ -400,7 +400,7 @@
                 if (GraalOptions.TraceLIRGeneratorLevel >= 2) {
                     TTY.println("STATE CHANGE");
                     if (GraalOptions.TraceLIRGeneratorLevel >= 3) {
-                        TTY.println(stateAfter.toDetailedString());
+                        TTY.println(stateAfter.toString(Node.Verbosity.Debugger));
                     }
                 }
             }
@@ -428,8 +428,7 @@
     private boolean checkStateReady(FrameState state) {
         FrameState fs = state;
         while (fs != null) {
-            for (int i = 0; i < fs.valuesSize(); i++) {
-                ValueNode v = fs.valueAt(i);
+            for (ValueNode v : fs.values()) {
                 if (v != null && !(v instanceof VirtualObjectNode)) {
                     assert operand(v) != null : "Value " + v + " in " + fs + " is not ready!";
                 }
@@ -1054,7 +1053,15 @@
         FrameState stateAfter = x.stateAfter();
         if (stateAfter != null) {
             // TODO change back to stateBeforeReturn() when RuntimeCallNode uses a CallTargetNode
-            FrameState stateBeforeReturn = stateAfter.duplicateModified(stateAfter.bci, stateAfter.rethrowException(), x.kind());
+            // (cwi) I made the code that modifies the operand stack conditional. My scenario: runtime calls to, e.g.,
+            // CreateNullPointerException have no equivalent in the bytecodes, so there is in invoke bytecode.
+            // Therefore, the result of the runtime call was never pushed to the stack, and we cannot pop it here.
+            FrameState stateBeforeReturn = stateAfter;
+            if ((stateAfter.stackSize() > 0 && stateAfter.stackAt(stateAfter.stackSize() - 1) == x) ||
+                (stateAfter.stackSize() > 1 && stateAfter.stackAt(stateAfter.stackSize() - 2) == x)) {
+
+                stateBeforeReturn = stateAfter.duplicateModified(stateAfter.bci, stateAfter.rethrowException(), x.kind());
+            }
 
             // TODO is it correct here that the pointerSlots are not passed to the oop map generation?
             info = stateFor(stateBeforeReturn);
@@ -1451,19 +1458,6 @@
         ValueNode current;
         ValueNode receiver;
 
-        XirSupport() {
-        }
-
-        public CiCodePos getCodePos() {
-            if (current instanceof StateSplit) {
-                FrameState stateAfter = ((StateSplit) current).stateAfter();
-                if (stateAfter != null) {
-                    return stateAfter.toCodePos();
-                }
-            }
-            return null;
-        }
-
         public boolean isNonNull(XirArgument argument) {
             return false;
         }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InsertStateAfterPlaceholderPhase.java	Mon Mar 05 14:38:43 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InsertStateAfterPlaceholderPhase.java	Mon Mar 05 09:55:54 2012 -0800
@@ -22,10 +22,24 @@
  */
 package com.oracle.max.graal.compiler.phases;
 
+import com.oracle.max.graal.graph.*;
 import com.oracle.max.graal.nodes.*;
+import com.oracle.max.graal.nodes.spi.*;
+import com.oracle.max.graal.nodes.type.*;
 
 public class InsertStateAfterPlaceholderPhase extends Phase {
 
+    private static class PlaceholderNode extends AbstractStateSplit implements Node.IterableNodeType, LIRLowerable {
+        public PlaceholderNode() {
+            super(StampFactory.illegal());
+        }
+
+        @Override
+        public void generate(LIRGeneratorTool gen) {
+            // nothing to do
+        }
+    }
+
     @Override
     protected void run(StructuredGraph graph) {
         for (ReturnNode ret : graph.getNodes(ReturnNode.class)) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/Phase.java	Mon Mar 05 14:38:43 2012 +0100
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/Phase.java	Mon Mar 05 09:55:54 2012 -0800
@@ -55,6 +55,7 @@
                 if (dumpGraph) {
                     Debug.dump(graph, "After phase %s", name);
                 }
+                assert graph.verify();
             }
         });
     }
--- a/graal/com.oracle.max.graal.hotspot/src/com/oracle/max/graal/hotspot/ri/HotSpotRuntime.java	Mon Mar 05 14:38:43 2012 +0100
+++ b/graal/com.oracle.max.graal.hotspot/src/com/oracle/max/graal/hotspot/ri/HotSpotRuntime.java	Mon Mar 05 09:55:54 2012 -0800
@@ -437,7 +437,7 @@
 
     private CiTargetMethod createCallbackStub(RiResolvedMethod method, CiGenericCallback callback) {
         StructuredGraph graph = new StructuredGraph();
-        FrameStateBuilder frameState = new FrameStateBuilder(method, method.maxLocals(), method.maxStackSize(), graph, false);
+        FrameStateBuilder frameState = new FrameStateBuilder(method, graph, false);
         ValueNode local0 = frameState.loadLocal(0);
 
         FrameState initialFrameState = frameState.create(0);
--- a/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/BciBlockMapping.java	Mon Mar 05 14:38:43 2012 +0100
+++ b/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/BciBlockMapping.java	Mon Mar 05 09:55:54 2012 -0800
@@ -29,6 +29,8 @@
 import com.oracle.max.cri.ci.*;
 import com.oracle.max.cri.ri.*;
 import com.oracle.max.graal.compiler.*;
+import com.oracle.max.graal.debug.*;
+import com.oracle.max.graal.graph.*;
 import com.oracle.max.graal.nodes.*;
 
 /**
@@ -121,6 +123,7 @@
         public int blockID;
 
         public FixedWithNextNode firstInstruction;
+        public FrameStateBuilder entryState;
 
         public ArrayList<Block> successors = new ArrayList<>(2);
         public int normalSuccessors;
@@ -136,6 +139,11 @@
         public Block retSuccessor;
         public boolean endsWithRet = false;
 
+        public BitMap localsLiveIn;
+        public BitMap localsLiveOut;
+        private BitMap localsLiveGen;
+        private BitMap localsLiveKill;
+
         public Block copy() {
             try {
                 Block block = (Block) super.clone();
@@ -182,6 +190,8 @@
 
     public final RiResolvedMethod method;
 
+    private final BytecodeStream stream;
+
     private final RiExceptionHandler[] exceptionHandlers;
 
     private Block[] blockMap;
@@ -201,6 +211,7 @@
     public BciBlockMapping(RiResolvedMethod method, boolean useBranchPrediction) {
         this.method = method;
         exceptionHandlers = method.exceptionHandlers();
+        stream = new BytecodeStream(method.code());
         this.blockMap = new Block[method.codeSize()];
         this.canTrap = new BitSet(blockMap.length);
         this.blocks = new ArrayList<>();
@@ -232,6 +243,15 @@
 
         // Discard big arrays so that they can be GCed
         blockMap = null;
+
+        if (GraalOptions.OptLivenessAnalysis) {
+            Debug.scope("LivenessAnalysis", new Runnable() {
+                @Override
+                public void run() {
+                    computeLiveness();
+                }
+            });
+        }
     }
 
     private void initializeBlockIds() {
@@ -640,4 +660,187 @@
 
         return loops;
     }
+
+
+    private void computeLiveness() {
+        for (Block block : blocks) {
+            computeLocalLiveness(block);
+        }
+
+        boolean changed;
+        int iteration = 0;
+        do {
+            Debug.log("Iteration %d", iteration);
+            changed = false;
+            for (int i = blocks.size() - 1; i >= 0; i--) {
+                Block block = blocks.get(i);
+                Debug.log("  start B%d  [%d, %d]  in: %s  out: %s  gen: %s  kill: %s", block.blockID, block.startBci, block.endBci, block.localsLiveIn, block.localsLiveOut, block.localsLiveGen, block.localsLiveKill);
+
+                boolean blockChanged = (iteration == 0);
+                for (Block sux : block.successors) {
+                    Debug.log("    Successor B%d: %s", sux.blockID, sux.localsLiveIn);
+                    blockChanged = block.localsLiveOut.setUnionWithResult(sux.localsLiveIn) || blockChanged;
+                }
+
+                if (blockChanged) {
+                    block.localsLiveIn.setFrom(block.localsLiveOut);
+                    block.localsLiveIn.setDifference(block.localsLiveKill);
+                    block.localsLiveIn.setUnion(block.localsLiveGen);
+
+                    for (Block sux : block.successors) {
+                        if (sux instanceof ExceptionBlock) {
+                            // Exception handler blocks can be reached from anywhere within the block jumping to them,
+                            // so we conservatively assume local variables require by the exception handler are live both
+                            // at the beginning and end of the block.
+                            blockChanged = block.localsLiveIn.setUnionWithResult(sux.localsLiveIn) || blockChanged;
+                        }
+                    }
+                    Debug.log("  end   B%d  [%d, %d]  in: %s  out: %s  gen: %s  kill: %s", block.blockID, block.startBci, block.endBci, block.localsLiveIn, block.localsLiveOut, block.localsLiveGen, block.localsLiveKill);
+                }
+                changed |= blockChanged;
+            }
+            iteration++;
+        } while (changed);
+    }
+
+    private void computeLocalLiveness(Block block) {
+        block.localsLiveIn = new BitMap(method.maxLocals());
+        block.localsLiveOut = new BitMap(method.maxLocals());
+        block.localsLiveGen = new BitMap(method.maxLocals());
+        block.localsLiveKill = new BitMap(method.maxLocals());
+
+        if (block.startBci < 0 || block.endBci < 0) {
+            return;
+        }
+
+        stream.setBCI(block.startBci);
+        while (stream.currentBCI() <= block.endBci) {
+            switch (stream.currentBC()) {
+                case RETURN:
+                    if (method.isConstructor() && method.holder().superType() == null) {
+                        // return from Object.init implicitly registers a finalizer
+                        // for the receiver if needed, so keep it alive.
+                        loadOne(block, 0);
+                    }
+                    break;
+
+                case LLOAD:
+                case DLOAD:
+                    loadTwo(block, stream.readLocalIndex());
+                    break;
+                case LLOAD_0:
+                case DLOAD_0:
+                    loadTwo(block, 0);
+                    break;
+                case LLOAD_1:
+                case DLOAD_1:
+                    loadTwo(block, 1);
+                    break;
+                case LLOAD_2:
+                case DLOAD_2:
+                    loadTwo(block, 2);
+                    break;
+                case LLOAD_3:
+                case DLOAD_3:
+                    loadTwo(block, 3);
+                    break;
+                case ILOAD:
+                case IINC:
+                case FLOAD:
+                case ALOAD:
+                case RET:
+                    loadOne(block, stream.readLocalIndex());
+                    break;
+                case ILOAD_0:
+                case FLOAD_0:
+                case ALOAD_0:
+                    loadOne(block, 0);
+                    break;
+                case ILOAD_1:
+                case FLOAD_1:
+                case ALOAD_1:
+                    loadOne(block, 1);
+                    break;
+                case ILOAD_2:
+                case FLOAD_2:
+                case ALOAD_2:
+                    loadOne(block, 2);
+                    break;
+                case ILOAD_3:
+                case FLOAD_3:
+                case ALOAD_3:
+                    loadOne(block, 3);
+                    break;
+
+                case LSTORE:
+                case DSTORE:
+                    storeTwo(block, stream.readLocalIndex());
+                    break;
+                case LSTORE_0:
+                case DSTORE_0:
+                    storeTwo(block, 0);
+                    break;
+                case LSTORE_1:
+                case DSTORE_1:
+                    storeTwo(block, 1);
+                    break;
+                case LSTORE_2:
+                case DSTORE_2:
+                    storeTwo(block, 2);
+                    break;
+                case LSTORE_3:
+                case DSTORE_3:
+                    storeTwo(block, 3);
+                    break;
+                case ISTORE:
+                case FSTORE:
+                case ASTORE:
+                    storeOne(block, stream.readLocalIndex());
+                    break;
+                case ISTORE_0:
+                case FSTORE_0:
+                case ASTORE_0:
+                    storeOne(block, 0);
+                    break;
+                case ISTORE_1:
+                case FSTORE_1:
+                case ASTORE_1:
+                    storeOne(block, 1);
+                    break;
+                case ISTORE_2:
+                case FSTORE_2:
+                case ASTORE_2:
+                    storeOne(block, 2);
+                    break;
+                case ISTORE_3:
+                case FSTORE_3:
+                case ASTORE_3:
+                    storeOne(block, 3);
+                    break;
+            }
+            stream.next();
+        }
+    }
+
+    private static void loadTwo(Block block, int local) {
+        loadOne(block, local);
+        loadOne(block, local + 1);
+    }
+
+    private static void loadOne(Block block, int local) {
+        if (!block.localsLiveKill.get(local)) {
+            block.localsLiveGen.set(local);
+        }
+    }
+
+    private static void storeTwo(Block block, int local) {
+        storeOne(block, local);
+        storeOne(block, local + 1);
+    }
+
+    private static void storeOne(Block block, int local) {
+        if (!block.localsLiveGen.get(local)) {
+            block.localsLiveKill.set(local);
+        }
+    }
 }
--- a/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/FrameStateBuilder.java	Mon Mar 05 14:38:43 2012 +0100
+++ b/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/FrameStateBuilder.java	Mon Mar 05 09:55:54 2012 -0800
@@ -29,32 +29,29 @@
 
 import com.oracle.max.cri.ci.*;
 import com.oracle.max.cri.ri.*;
+import com.oracle.max.graal.graph.*;
+import com.oracle.max.graal.graph.Node.Verbosity;
+import com.oracle.max.graal.graph.iterators.*;
 import com.oracle.max.graal.nodes.*;
 import com.oracle.max.graal.nodes.PhiNode.PhiType;
-import com.oracle.max.graal.nodes.spi.*;
 import com.oracle.max.graal.nodes.type.*;
 
-
-public class FrameStateBuilder implements FrameStateAccess {
-
+public class FrameStateBuilder {
+    private final RiResolvedMethod method;
     private final StructuredGraph graph;
 
     private final ValueNode[] locals;
     private final ValueNode[] stack;
-
-    private int stackIndex;
+    private int stackSize;
     private boolean rethrowException;
 
-    private final RiResolvedMethod method;
-
-    public FrameStateBuilder(RiResolvedMethod method, int maxLocals, int maxStackSize, StructuredGraph graph, boolean eagerResolve) {
+    public FrameStateBuilder(RiResolvedMethod method, StructuredGraph graph, boolean eagerResolve) {
         assert graph != null;
         this.method = method;
         this.graph = graph;
-        this.locals = new ValueNode[maxLocals];
+        this.locals = new ValueNode[method.maxLocals()];
         // we always need at least one stack slot (for exceptions)
-        int stackSize = Math.max(1, maxStackSize);
-        this.stack = new ValueNode[stackSize];
+        this.stack = new ValueNode[Math.max(1, method.maxStackSize())];
 
         int javaIndex = 0;
         int index = 0;
@@ -88,33 +85,256 @@
         }
     }
 
+    private FrameStateBuilder(RiResolvedMethod method, StructuredGraph graph, ValueNode[] locals, ValueNode[] stack, int stackSize, boolean rethrowException) {
+        assert locals.length == method.maxLocals();
+        assert stack.length == Math.max(1, method.maxStackSize());
+
+        this.method = method;
+        this.graph = graph;
+        this.locals = locals;
+        this.stack = stack;
+        this.stackSize = stackSize;
+        this.rethrowException = rethrowException;
+    }
+
     @Override
     public String toString() {
-        return String.format("FrameStateBuilder[stackSize=%d]", stackIndex);
-    }
-
-    public void initializeFrom(FrameState other) {
-        assert locals.length == other.localsSize() : "expected: " + locals.length + ", actual: " + other.localsSize();
-        assert stack.length >= other.stackSize() : "expected: <=" + stack.length + ", actual: " + other.stackSize();
-
-        this.stackIndex = other.stackSize();
-        for (int i = 0; i < other.localsSize(); i++) {
-            locals[i] = other.localAt(i);
+        StringBuilder sb = new StringBuilder();
+        sb.append("[locals: [");
+        for (int i = 0; i < locals.length; i++) {
+            sb.append(i == 0 ? "" : ",").append(locals[i] == null ? "_" : locals[i].toString(Verbosity.Id));
         }
-        for (int i = 0; i < other.stackSize(); i++) {
-            stack[i] = other.stackAt(i);
+        sb.append("] stack: [");
+        for (int i = 0; i < stackSize; i++) {
+            sb.append(i == 0 ? "" : ",").append(stack[i] == null ? "_" : stack[i].toString(Verbosity.Id));
         }
-        this.rethrowException = other.rethrowException();
+        sb.append("]");
+        if (rethrowException) {
+            sb.append(" rethrowException");
+        }
+        sb.append("]");
+        return sb.toString();
     }
 
     public FrameState create(int bci) {
-        return graph.add(new FrameState(method, bci, locals, stack, stackIndex, rethrowException, false));
+        return graph.add(new FrameState(method, bci, locals, stack, stackSize, rethrowException, false));
     }
 
-    public FrameState duplicateWithException(int bci, ValueNode exceptionObject) {
-        FrameState frameState = graph.add(new FrameState(method, bci, locals, new ValueNode[]{exceptionObject}, 1, true, false));
-        frameState.setOuterFrameState(outerFrameState());
-        return frameState;
+    public FrameState duplicateWithoutStack(int bci) {
+        return graph.add(new FrameState(method, bci, locals, new ValueNode[0], 0, false, false));
+    }
+
+
+    public FrameStateBuilder copy() {
+        return new FrameStateBuilder(method, graph, Arrays.copyOf(locals, locals.length), Arrays.copyOf(stack, stack.length), stackSize, rethrowException);
+    }
+
+    public FrameStateBuilder copyWithException(ValueNode exceptionObject) {
+        ValueNode[] newStack = new ValueNode[stack.length];
+        newStack[0] = exceptionObject;
+        return new FrameStateBuilder(method, graph, Arrays.copyOf(locals, locals.length), newStack, 1, true);
+    }
+
+
+    public boolean isCompatibleWith(FrameStateBuilder other) {
+        assert method == other.method && graph == other.graph && localsSize() == other.localsSize() : "Can only compare frame states of the same method";
+
+        if (stackSize() != other.stackSize()) {
+            return false;
+        }
+        for (int i = 0; i < stackSize(); i++) {
+            ValueNode x = stackAt(i);
+            ValueNode y = other.stackAt(i);
+            if (x != y && ValueUtil.typeMismatch(x, y)) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    public void merge(MergeNode block, FrameStateBuilder other) {
+        assert isCompatibleWith(other);
+
+        for (int i = 0; i < localsSize(); i++) {
+            storeLocal(i, merge(localAt(i), other.localAt(i), block));
+        }
+        for (int i = 0; i < stackSize(); i++) {
+            storeStack(i, merge(stackAt(i), other.stackAt(i), block));
+        }
+    }
+
+    private ValueNode merge(ValueNode currentValue, ValueNode otherValue, MergeNode block) {
+        if (currentValue == null) {
+            return null;
+
+        } else if (block.isPhiAtMerge(currentValue)) {
+            if (otherValue == null || currentValue.kind() != otherValue.kind()) {
+                deletePhi(currentValue);
+                return null;
+            }
+            ((PhiNode) currentValue).addInput(otherValue);
+            return currentValue;
+
+        } else if (currentValue != otherValue) {
+            assert !(block instanceof LoopBeginNode) : "Phi functions for loop headers are create eagerly for all locals and stack slots";
+            if (otherValue == null || currentValue.kind() != otherValue.kind()) {
+                return null;
+            }
+
+            PhiNode phi = graph.unique(new PhiNode(currentValue.kind(), block, PhiType.Value));
+            for (int i = 0; i < block.phiPredecessorCount(); i++) {
+                phi.addInput(currentValue);
+            }
+            phi.addInput(otherValue);
+            assert phi.valueCount() == block.phiPredecessorCount() + 1 : "valueCount=" + phi.valueCount() + " predSize= " + block.phiPredecessorCount();
+            return phi;
+
+        } else {
+            return currentValue;
+        }
+    }
+
+    private void deletePhi(Node phi) {
+        // Collect all phi functions that use this phi so that we can delete them recursively (after we delete ourselfs to avoid circles).
+        List<Node> phiUsages = phi.usages().filter(NodePredicates.isA(PhiNode.class)).snapshot();
+
+        // Remove the phi function from all FrameStates where it is used and then delete it.
+        assert phi.usages().filter(NodePredicates.isNotA(FrameState.class)).filter(NodePredicates.isNotA(PhiNode.class)).isEmpty() : "phi function that gets deletes must only be used in frame states";
+        phi.replaceAtUsages(null);
+        phi.safeDelete();
+
+        for (Node phiUsage : phiUsages) {
+            deletePhi(phiUsage);
+        }
+    }
+
+    public void insertLoopPhis(LoopBeginNode loopBegin) {
+        for (int i = 0; i < localsSize(); i++) {
+            storeLocal(i, createLoopPhi(loopBegin, localAt(i)));
+        }
+        for (int i = 0; i < stackSize(); i++) {
+            storeStack(i, createLoopPhi(loopBegin, stackAt(i)));
+        }
+    }
+
+    private PhiNode createLoopPhi(MergeNode block, ValueNode value) {
+        if (value == null) {
+            return null;
+        }
+        assert !block.isPhiAtMerge(value) : "phi function for this block already created";
+
+        PhiNode phi = graph.unique(new PhiNode(value.kind(), block, PhiType.Value));
+        phi.addInput(value);
+        return phi;
+    }
+
+    public void cleanupDeletedPhis() {
+        for (int i = 0; i < localsSize(); i++) {
+            if (localAt(i) != null && localAt(i).isDeleted()) {
+                assert localAt(i) instanceof PhiNode : "Only phi functions can be deleted during parsing";
+                storeLocal(i, null);
+            }
+        }
+    }
+
+    public void clearNonLiveLocals(BitMap liveness) {
+        if (liveness == null) {
+            return;
+        }
+        assert liveness.size() == locals.length;
+        for (int i = 0; i < locals.length; i++) {
+            if (!liveness.get(i)) {
+                locals[i] = null;
+            }
+        }
+    }
+
+    public boolean rethrowException() {
+        return rethrowException;
+    }
+
+    public void setRethrowException(boolean b) {
+        rethrowException = b;
+    }
+
+
+    /**
+     * Returns the size of the local variables.
+     *
+     * @return the size of the local variables
+     */
+    public int localsSize() {
+        return locals.length;
+    }
+
+    /**
+     * Gets the current size (height) of the stack.
+     */
+    public int stackSize() {
+        return stackSize;
+    }
+
+    /**
+     * Gets the value in the local variables at the specified index, without any sanity checking.
+     *
+     * @param i the index into the locals
+     * @return the instruction that produced the value for the specified local
+     */
+    protected final ValueNode localAt(int i) {
+        return locals[i];
+    }
+
+    /**
+     * Get the value on the stack at the specified stack index.
+     *
+     * @param i the index into the stack, with {@code 0} being the bottom of the stack
+     * @return the instruction at the specified position in the stack
+     */
+    protected final ValueNode stackAt(int i) {
+        return stack[i];
+    }
+
+    /**
+     * Loads the local variable at the specified index, checking that the returned value is non-null
+     * and that two-stack values are properly handled.
+     *
+     * @param i the index of the local variable to load
+     * @return the instruction that produced the specified local
+     */
+    public ValueNode loadLocal(int i) {
+        ValueNode x = locals[i];
+        assert !x.isDeleted();
+        assert !isTwoSlot(x.kind()) || locals[i + 1] == null;
+        assert i == 0 || locals[i - 1] == null || !isTwoSlot(locals[i - 1].kind());
+        return x;
+    }
+
+    /**
+     * Stores a given local variable at the specified index. If the value is a {@linkplain CiKind#isDoubleWord() double word},
+     * then the next local variable index is also overwritten.
+     *
+     * @param i the index at which to store
+     * @param x the instruction which produces the value for the local
+     */
+    public void storeLocal(int i, ValueNode x) {
+        assert x == null || x.kind() != CiKind.Void && x.kind() != CiKind.Illegal : "unexpected value: " + x;
+        locals[i] = x;
+        if (x != null && isTwoSlot(x.kind())) {
+            // if this is a double word, then kill i+1
+            locals[i + 1] = null;
+        }
+        if (x != null && i > 0) {
+            ValueNode p = locals[i - 1];
+            if (p != null && isTwoSlot(p.kind())) {
+                // if there was a double word at i - 1, then kill it
+                locals[i - 1] = null;
+            }
+        }
+    }
+
+    private void storeStack(int i, ValueNode x) {
+        assert x == null || stack[i] == null || x.kind() == stack[i].kind() : "Method does not handle changes from one-slot to two-slot values";
+        stack[i] = x;
     }
 
     /**
@@ -123,7 +343,7 @@
      * @param x the instruction to push onto the stack
      */
     public void push(CiKind kind, ValueNode x) {
-        assert kind != CiKind.Void;
+        assert !x.isDeleted() && x.kind() != CiKind.Void && x.kind() != CiKind.Illegal;
         xpush(assertKind(kind, x));
         if (isTwoSlot(kind)) {
             xpush(null);
@@ -135,9 +355,8 @@
      * @param x the instruction to push onto the stack
      */
     public void xpush(ValueNode x) {
-        assert x == null || !x.isDeleted();
-        assert x == null || (x.kind() != CiKind.Void && x.kind() != CiKind.Illegal) : "unexpected value: " + x;
-        stack[stackIndex++] = x;
+        assert x == null || (!x.isDeleted() && x.kind() != CiKind.Void && x.kind() != CiKind.Illegal);
+        stack[stackSize++] = x;
     }
 
     /**
@@ -215,7 +434,7 @@
      * @return x the instruction popped off the stack
      */
     public ValueNode xpop() {
-        ValueNode result = stack[--stackIndex];
+        ValueNode result = stack[--stackSize];
         assert result == null || !result.isDeleted();
         return result;
     }
@@ -276,7 +495,7 @@
      * @return an array containing the arguments off of the stack
      */
     public ValueNode[] popArguments(int slotSize, int argSize) {
-        int base = stackIndex - slotSize;
+        int base = stackSize - slotSize;
         ValueNode[] r = new ValueNode[argSize];
         int argIndex = 0;
         int stackindex = 0;
@@ -286,7 +505,7 @@
             r[argIndex++] = element;
             stackindex += stackSlots(element.kind());
         }
-        stackIndex = base;
+        stackSize = base;
         return r;
     }
 
@@ -309,173 +528,10 @@
     }
 
     /**
-     * Truncates this stack to the specified size.
-     * @param size the size to truncate to
-     */
-    public void truncateStack(int size) {
-        stackIndex = size;
-        assert stackIndex >= 0;
-    }
-
-    /**
      * Clears all values on this stack.
      */
     public void clearStack() {
-        stackIndex = 0;
-    }
-
-    /**
-     * Loads the local variable at the specified index.
-     *
-     * @param i the index of the local variable to load
-     * @return the instruction that produced the specified local
-     */
-    public ValueNode loadLocal(int i) {
-        ValueNode x = locals[i];
-        if (x != null) {
-            if (x instanceof PhiNode) {
-                assert ((PhiNode) x).type() == PhiType.Value;
-                if (x.isDeleted()) {
-                    return null;
-                }
-            }
-            assert !isTwoSlot(x.kind()) || locals[i + 1] == null || locals[i + 1] instanceof PhiNode;
-        }
-        return x;
-    }
-
-    /**
-     * Stores a given local variable at the specified index. If the value is a {@linkplain CiKind#isDoubleWord() double word},
-     * then the next local variable index is also overwritten.
-     *
-     * @param i the index at which to store
-     * @param x the instruction which produces the value for the local
-     */
-    public void storeLocal(int i, ValueNode x) {
-        assert x.kind() != CiKind.Void && x.kind() != CiKind.Illegal : "unexpected value: " + x;
-        locals[i] = x;
-        if (isTwoSlot(x.kind())) {
-            // (tw) if this was a double word then kill i+1
-            locals[i + 1] = null;
-        }
-        if (i > 0) {
-            // if there was a double word at i - 1, then kill it
-            ValueNode p = locals[i - 1];
-            if (p != null && isTwoSlot(p.kind())) {
-                locals[i - 1] = null;
-            }
-        }
-    }
-
-    /**
-     * Get the value on the stack at the specified stack index.
-     *
-     * @param i the index into the stack, with {@code 0} being the bottom of the stack
-     * @return the instruction at the specified position in the stack
-     */
-    public final ValueNode stackAt(int i) {
-        return stack[i];
-    }
-
-    /**
-     * Gets the value in the local variables at the specified index.
-     *
-     * @param i the index into the locals
-     * @return the instruction that produced the value for the specified local
-     */
-    public final ValueNode localAt(int i) {
-        return locals[i];
-    }
-
-    /**
-     * Returns the size of the local variables.
-     *
-     * @return the size of the local variables
-     */
-    public int localsSize() {
-        return locals.length;
-    }
-
-    /**
-     * Gets the current size (height) of the stack.
-     */
-    public int stackSize() {
-        return stackIndex;
-    }
-
-    public Iterator<ValueNode> locals() {
-        return new ValueArrayIterator(locals);
-    }
-
-    public Iterator<ValueNode> stack() {
-        return new ValueArrayIterator(locals);
-    }
-
-
-    private static class ValueArrayIterator implements Iterator<ValueNode> {
-        private final ValueNode[] array;
-        private int index;
-
-        public ValueArrayIterator(ValueNode[] array, int length) {
-            assert length <= array.length;
-            this.array = array;
-            this.index = 0;
-        }
-
-        public ValueArrayIterator(ValueNode[] array) {
-            this(array, array.length);
-        }
-
-        @Override
-        public boolean hasNext() {
-            return index < array.length;
-        }
-
-        @Override
-        public ValueNode next() {
-            return array[index++];
-        }
-
-        @Override
-        public void remove() {
-            throw new UnsupportedOperationException("cannot remove from array");
-        }
-
-    }
-
-
-    @Override
-    public FrameState duplicate(int bci) {
-        return create(bci);
-    }
-
-    @Override
-    public ValueNode valueAt(int i) {
-        if (i < locals.length) {
-            return locals[i];
-        } else {
-            return stack[i - locals.length];
-        }
-    }
-
-    @Override
-    public FrameState outerFrameState() {
-        return null;
-    }
-
-    public FrameState duplicateWithoutStack(int bci) {
-        FrameState frameState = graph.add(new FrameState(method, bci, locals, new ValueNode[0], 0, false, false));
-        frameState.setOuterFrameState(outerFrameState());
-        return frameState;
-    }
-
-    @Override
-    public boolean rethrowException() {
-        return rethrowException;
-    }
-
-    public void setRethrowException(boolean b) {
-        rethrowException = b;
+        stackSize = 0;
     }
 
     public static int stackSlots(CiKind kind) {
--- a/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/GraphBuilderPhase.java	Mon Mar 05 14:38:43 2012 +0100
+++ b/graal/com.oracle.max.graal.java/src/com/oracle/max/graal/java/GraphBuilderPhase.java	Mon Mar 05 09:55:54 2012 -0800
@@ -47,7 +47,7 @@
 import com.oracle.max.graal.nodes.extended.*;
 import com.oracle.max.graal.nodes.java.*;
 import com.oracle.max.graal.nodes.java.MethodCallTargetNode.InvokeKind;
-import com.oracle.max.graal.nodes.spi.*;
+import com.oracle.max.graal.nodes.type.*;
 
 /**
  * The {@code GraphBuilder} class parses the bytecode of a method and builds the IR graph.
@@ -80,30 +80,32 @@
     private FrameStateBuilder frameState;          // the current execution state
     private Block currentBlock;
 
-    private int nextBlockNumber;
-
     private ValueNode methodSynchronizedObject;
     private ExceptionBlock unwindBlock;
     private Block returnBlock;
 
-    // the worklist of blocks, sorted by depth first number
-    private final PriorityQueue<Block> workList = new PriorityQueue<>(10, new Comparator<Block>() {
-        public int compare(Block o1, Block o2) {
-            return o1.blockID - o2.blockID;
-        }
-    });
-
     private FixedWithNextNode lastInstr;                 // the last instruction added
 
-    private Set<Block> blocksOnWorklist;
-    private Set<Block> blocksVisited;
-
     private BitSet canTrapBitSet;
 
     public static final Map<RiMethod, StructuredGraph> cachedGraphs = new WeakHashMap<>();
 
     private final GraphBuilderConfiguration config;
 
+
+    /**
+     * Node that marks the begin of block during bytecode parsing.  When a block is identified the first
+     * time as a jump target, the placeholder is created and used as the successor for the jump.  When the
+     * block is seen the second time, a MergeNode is created to correctly merge the now two different
+     * predecessor states.
+     */
+    private static class BlockPlaceholderNode extends FixedWithNextNode implements Node.IterableNodeType {
+        public BlockPlaceholderNode() {
+            super(StampFactory.illegal());
+        }
+    }
+
+
     public GraphBuilderPhase(RiRuntime runtime) {
         this(runtime, GraphBuilderConfiguration.getDefault());
     }
@@ -121,14 +123,12 @@
         assert method.code() != null : "method must contain bytecodes: " + method;
         this.stream = new BytecodeStream(method.code());
         this.constantPool = method.getConstantPool();
-        this.blocksOnWorklist = new HashSet<>();
-        this.blocksVisited = new HashSet<>();
         unwindBlock = null;
         returnBlock = null;
         methodSynchronizedObject = null;
         exceptionHandlers = null;
         this.currentGraph = graph;
-        this.frameState = new FrameStateBuilder(method, method.maxLocals(), method.maxStackSize(), graph, config.eagerResolving());
+        this.frameState = new FrameStateBuilder(method, graph, config.eagerResolving());
         build();
     }
 
@@ -140,12 +140,8 @@
     private BciBlockMapping createBlockMap() {
         BciBlockMapping map = new BciBlockMapping(method, config.useBranchPrediction());
         map.build();
+        Debug.dump(map, CiUtil.format("After block building %f %R %H.%n(%P)", method));
 
-//        if (currentContext.isObserved()) {
-//            String label = CiUtil.format("BlockListBuilder %f %R %H.%n(%P)", method);
-//            currentContext.observable.fireCompilationEvent(label, map);
-//        }
-        // TODO(tw): Reinstall this logging code when debug framework is finished.
         return map;
     }
 
@@ -161,8 +157,6 @@
 
         exceptionHandlers = blockMap.exceptionHandlers();
 
-        nextBlockNumber = blockMap.blocks.size();
-
         lastInstr = currentGraph.start();
         if (isSynchronized(method.accessFlags())) {
             // add a monitor enter to the start block
@@ -170,6 +164,7 @@
             methodSynchronizedObject = synchronizedObject(frameState, method);
             lastInstr = genMonitorEnter(methodSynchronizedObject);
         }
+        frameState.clearNonLiveLocals(blockMap.startBlock.localsLiveIn);
 
         // finish the start block
         ((AbstractStateSplit) lastInstr).setStateAfter(frameState.create(0));
@@ -177,14 +172,21 @@
             appendGoto(createTarget(blockMap.startBlock, frameState));
         } else {
             blockMap.startBlock.firstInstruction = lastInstr;
+            blockMap.startBlock.entryState = frameState;
         }
-        addToWorkList(blockMap.startBlock);
 
-        iterateAllBlocks();
+        for (Block block : blockMap.blocks) {
+            processBlock(block);
+        }
+        processBlock(returnBlock);
+        processBlock(unwindBlock);
+
+        Debug.dump(currentGraph, "After bytecode parsing");
+
         connectLoopEndToBegin();
 
         // remove Placeholders (except for loop exits)
-        for (PlaceholderNode n : currentGraph.getNodes(PlaceholderNode.class)) {
+        for (BlockPlaceholderNode n : currentGraph.getNodes(BlockPlaceholderNode.class)) {
             currentGraph.removeFixed(n);
         }
 
@@ -200,18 +202,13 @@
         }
     }
 
-    private int nextBlockNumber() {
-        return nextBlockNumber++;
-    }
-
     private Block unwindBlock(int bci) {
         if (unwindBlock == null) {
             unwindBlock = new ExceptionBlock();
             unwindBlock.startBci = -1;
             unwindBlock.endBci = -1;
             unwindBlock.deoptBci = bci;
-            unwindBlock.blockID = nextBlockNumber();
-            addToWorkList(unwindBlock);
+            unwindBlock.blockID = Integer.MAX_VALUE;
         }
         return unwindBlock;
     }
@@ -221,80 +218,11 @@
             returnBlock = new Block();
             returnBlock.startBci = bci;
             returnBlock.endBci = bci;
-            returnBlock.blockID = nextBlockNumber();
-            addToWorkList(returnBlock);
+            returnBlock.blockID = Integer.MAX_VALUE;
         }
         return returnBlock;
     }
 
-    private void markOnWorkList(Block block) {
-        blocksOnWorklist.add(block);
-    }
-
-    private boolean isOnWorkList(Block block) {
-        return blocksOnWorklist.contains(block);
-    }
-
-    private void markVisited(Block block) {
-        blocksVisited.add(block);
-    }
-
-    private boolean isVisited(Block block) {
-        return blocksVisited.contains(block);
-    }
-
-    public void mergeOrClone(Block target, FrameStateAccess newState, StateSplit first) {
-
-        int bci = target.startBci;
-        if (target instanceof ExceptionBlock) {
-            bci = ((ExceptionBlock) target).deoptBci;
-        }
-
-        FrameState existingState = first.stateAfter();
-        if (existingState == null) {
-            // There was no state : new target
-            // copy state because it is modified
-            first.setStateAfter(newState.duplicate(bci));
-            return;
-        } else {
-            if (!GraalOptions.AssumeVerifiedBytecode && !existingState.isCompatibleWith(newState)) {
-                // stacks or locks do not match--bytecodes would not verify
-                TTY.println(existingState.toString());
-                TTY.println(newState.duplicate(0).toString());
-                throw new CiBailout("stack or locks do not match");
-            }
-            assert existingState.localsSize() == newState.localsSize();
-            assert existingState.stackSize() == newState.stackSize();
-
-            if (first instanceof PlaceholderNode) {
-                // there is no merge yet here
-                PlaceholderNode p = (PlaceholderNode) first;
-                if (p.predecessor() == null) {
-                    //nothing seems to come here, yet there's a state?
-                    Debug.log("Funky control flow going to @bci %d : we already have a state but no predecessor", bci);
-                    p.setStateAfter(newState.duplicate(bci));
-                    return;
-                } else {
-                    //create a merge
-                    MergeNode merge = currentGraph.add(new MergeNode());
-                    FixedNode next = p.next();
-                    if (p.predecessor() != null) {
-                        EndNode end = currentGraph.add(new EndNode());
-                        p.setNext(end);
-                        merge.addForwardEnd(end);
-                    }
-                    merge.setNext(next);
-                    FrameState mergeState = existingState.duplicate(bci);
-                    merge.setStateAfter(mergeState);
-                    mergeState.merge(merge, newState);
-                    target.firstInstruction = merge;
-                }
-            } else {
-                existingState.merge((MergeNode) first, newState);
-            }
-        }
-    }
-
     public BytecodeStream stream() {
         return stream;
     }
@@ -371,9 +299,9 @@
         } else {
             currentExceptionObject = exceptionObject;
         }
-        FrameState stateWithException = frameState.duplicateWithException(bci, currentExceptionObject);
+        FrameStateBuilder stateWithException = frameState.copyWithException(currentExceptionObject);
         if (newObj != null) {
-            newObj.setStateAfter(stateWithException);
+            newObj.setStateAfter(stateWithException.create(bci));
         }
         FixedNode target = createTarget(dispatchBlock, stateWithException);
         if (exceptionObject == null) {
@@ -596,7 +524,7 @@
     private void genIncrement() {
         int index = stream().readLocalIndex();
         int delta = stream().readIncrement();
-        ValueNode x = frameState.localAt(index);
+        ValueNode x = frameState.loadLocal(index);
         ValueNode y = append(ConstantNode.forInt(delta, currentGraph));
         frameState.storeLocal(index, append(currentGraph.unique(new IntegerAddNode(CiKind.Int, x, y))));
     }
@@ -757,7 +685,7 @@
             InstanceOfNode instanceOfNode = new InstanceOfNode(hub, (RiResolvedType) type, object, hints, Util.isFinalClass(resolvedType), false);
             frameState.ipush(append(MaterializeNode.create(currentGraph.unique(instanceOfNode), currentGraph)));
         } else {
-            PlaceholderNode trueSucc = currentGraph.add(new PlaceholderNode());
+            BlockPlaceholderNode trueSucc = currentGraph.add(new BlockPlaceholderNode());
             DeoptimizeNode deopt = currentGraph.add(new DeoptimizeNode(DeoptAction.InvalidateRecompile));
             IfNode ifNode = currentGraph.add(new IfNode(currentGraph.unique(new NullCheckNode(object, true)), trueSucc, deopt, 1));
             append(ifNode);
@@ -861,8 +789,8 @@
     }
 
     private ExceptionInfo emitNullCheck(ValueNode receiver) {
-        PlaceholderNode trueSucc = currentGraph.add(new PlaceholderNode());
-        PlaceholderNode falseSucc = currentGraph.add(new PlaceholderNode());
+        BlockPlaceholderNode trueSucc = currentGraph.add(new BlockPlaceholderNode());
+        BlockPlaceholderNode falseSucc = currentGraph.add(new BlockPlaceholderNode());
         IfNode ifNode = currentGraph.add(new IfNode(currentGraph.unique(new NullCheckNode(receiver, false)), trueSucc, falseSucc, 1));
 
         append(ifNode);
@@ -873,15 +801,15 @@
             return new ExceptionInfo(falseSucc, exception);
         } else {
             RuntimeCallNode call = currentGraph.add(new RuntimeCallNode(CiRuntimeCall.CreateNullPointerException));
-            call.setStateAfter(frameState.duplicate(bci()));
+            call.setStateAfter(frameState.create(bci()));
             falseSucc.setNext(call);
             return new ExceptionInfo(call, call);
         }
     }
 
     private ExceptionInfo emitBoundsCheck(ValueNode index, ValueNode length) {
-        PlaceholderNode trueSucc = currentGraph.add(new PlaceholderNode());
-        PlaceholderNode falseSucc = currentGraph.add(new PlaceholderNode());
+        BlockPlaceholderNode trueSucc = currentGraph.add(new BlockPlaceholderNode());
+        BlockPlaceholderNode falseSucc = currentGraph.add(new BlockPlaceholderNode());
         IfNode ifNode = currentGraph.add(new IfNode(currentGraph.unique(new CompareNode(index, Condition.BT, length)), trueSucc, falseSucc, 1));
 
         append(ifNode);
@@ -892,7 +820,7 @@
             return new ExceptionInfo(falseSucc, exception);
         } else {
             RuntimeCallNode call = currentGraph.add(new RuntimeCallNode(CiRuntimeCall.CreateOutOfBoundsException, new ValueNode[] {index}));
-            call.setStateAfter(frameState.duplicate(bci()));
+            call.setStateAfter(frameState.create(bci()));
             falseSucc.setNext(call);
             return new ExceptionInfo(call, call);
         }
@@ -922,7 +850,7 @@
                     merge.addForwardEnd(end);
                     phi.addInput(info.exception);
                 }
-                merge.setStateAfter(frameState.duplicate(bci()));
+                merge.setStateAfter(frameState.create(bci()));
                 exception = new ExceptionInfo(merge, phi);
             }
 
@@ -930,7 +858,7 @@
             if (entry != null) {
                 exception.exceptionEdge.setNext(entry);
             } else {
-                exception.exceptionEdge.setNext(createTarget(unwindBlock(bci()), frameState.duplicateWithException(bci(), exception.exception)));
+                exception.exceptionEdge.setNext(createTarget(unwindBlock(bci()), frameState.copyWithException(exception.exception)));
             }
             Debug.metric("ExplicitExceptions").increment();
         }
@@ -1098,6 +1026,10 @@
                 result = append(invoke);
                 frameState.pushReturn(resultType, result);
                 Block nextBlock = currentBlock.successors.get(0);
+
+                assert bci() == currentBlock.endBci;
+                frameState.clearNonLiveLocals(currentBlock.localsLiveOut);
+
                 invoke.setNext(createTarget(nextBlock, frameState));
                 invoke.setStateAfter(frameState.create(nextBlock.startBci));
             } else {
@@ -1251,130 +1183,148 @@
         return x;
     }
 
-    private FixedNode createTarget(Block block, FrameStateAccess stateAfter) {
+    private FixedNode createTarget(Block block, FrameStateBuilder 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();
+        assert !block.isExceptionEntry || stateAfter.stackSize() == 1;
 
-        if (block.isExceptionEntry) {
-            assert stateAfter.stackSize() == 1;
+        if (block.firstInstruction == null) {
+            // This is the first time we see this block as a branch target.
+            // Create and return a placeholder that later can be replaced with a MergeNode when we see this block again.
+            block.firstInstruction = currentGraph.add(new BlockPlaceholderNode());
+            block.entryState = stateAfter.copy();
+            block.entryState.clearNonLiveLocals(block.localsLiveIn);
+
+            Debug.log("createTarget %s: first visit, result: %s", block, block.firstInstruction);
+            return block.firstInstruction;
         }
 
-        if (block.firstInstruction == null) {
-            if (block.isLoopHeader) {
-                LoopBeginNode loop = currentGraph.add(new LoopBeginNode());
-                EndNode end = currentGraph.add(new EndNode());
-                loop.addForwardEnd(end);
-                PlaceholderNode p = currentGraph.add(new PlaceholderNode());
-                p.setNext(end);
-                block.firstInstruction = p;
-            } else {
-                block.firstInstruction = currentGraph.add(new PlaceholderNode());
-            }
-        }
-        LoopEndNode loopend = null;
-        StateSplit mergeAt = null;
-        if (block.isLoopHeader && isVisited(block)) { // backedge
-            loopend = currentGraph.add(new LoopEndNode(loopBegin(block)));
-            mergeAt = loopBegin(block);
-        } else {
-            mergeAt = (StateSplit) block.firstInstruction;
+        // We already saw this block before, so we have to merge states.
+        if (!block.entryState.isCompatibleWith(stateAfter)) {
+            throw new CiBailout("stacks do not match; bytecodes would not verify");
         }
 
-        mergeOrClone(block, stateAfter, mergeAt);
-        addToWorkList(block);
+        if (block.firstInstruction instanceof LoopBeginNode) {
+            assert block.isLoopHeader && currentBlock.blockID >= block.blockID : "must be backward branch";
+            // Backward loop edge. We need to create a special LoopEndNode and merge with the loop begin node created before.
+            LoopBeginNode loopBegin = (LoopBeginNode) block.firstInstruction;
+            LoopEndNode result = currentGraph.add(new LoopEndNode(loopBegin));
+            block.entryState.merge(loopBegin, stateAfter);
 
-        FixedNode result = null;
-        if (loopend != null) {
-            result = loopend;
-        } else {
-            result = block.firstInstruction;
+            Debug.log("createTarget %s: merging backward branch to loop header %s, result: %s", block, loopBegin, result);
+            return result;
+        }
+        assert currentBlock == null || currentBlock.blockID < block.blockID : "must not be backward branch";
+        assert block.firstInstruction.next() == null : "bytecodes already parsed for block";
+
+        if (block.firstInstruction instanceof BlockPlaceholderNode) {
+            // This is the second time we see this block. Create the actual MergeNode and the End Node for the already existing edge.
+            // For simplicity, we leave the placeholder in the graph and just append the new nodes after the placeholder.
+            BlockPlaceholderNode placeholder = (BlockPlaceholderNode) block.firstInstruction;
+
+            // The EndNode for the already existing edge.
+            EndNode end = currentGraph.add(new EndNode());
+            // The MergeNode that replaces the placeholder.
+            MergeNode mergeNode  = currentGraph.add(new MergeNode());
+            FixedNode next = placeholder.next();
+
+            placeholder.setNext(end);
+            mergeNode.addForwardEnd(end);
+            mergeNode.setNext(next);
+
+            block.firstInstruction = mergeNode;
         }
 
-        if (result instanceof MergeNode) {
-            EndNode end = currentGraph.add(new EndNode());
-            ((MergeNode) result).addForwardEnd(end);
-            result = end;
-        }
-        assert !(result instanceof MergeNode);
-        Debug.log("createTarget(%s, state) = %s", block, result);
+        MergeNode mergeNode = (MergeNode) block.firstInstruction;
+
+        // The EndNode for the newly merged edge.
+        EndNode result = currentGraph.add(new EndNode());
+        block.entryState.merge(mergeNode, stateAfter);
+        mergeNode.addForwardEnd(result);
+
+        Debug.log("createTarget %s: merging state, result: %s", block, result);
         return result;
     }
 
-    private ValueNode synchronizedObject(FrameStateAccess state, RiResolvedMethod target) {
+    private ValueNode synchronizedObject(FrameStateBuilder state, RiResolvedMethod target) {
         if (isStatic(target.accessFlags())) {
             return append(ConstantNode.forCiConstant(target.holder().getEncoding(Representation.JavaClass), runtime, currentGraph));
         } else {
-            return state.localAt(0);
+            return state.loadLocal(0);
         }
     }
 
-    private void iterateAllBlocks() {
-        Block block;
-        while ((block = removeFromWorkList()) != null) {
-            // remove blocks that have no predecessors by the time it their bytecodes are parsed
-            if (block.firstInstruction == null) {
-                markVisited(block);
-                continue;
+    private void processBlock(Block block) {
+        // Ignore blocks that have no predecessors by the time it their bytecodes are parsed
+        if (block == null || block.firstInstruction == null) {
+            Debug.log("Ignoring block %s", block);
+            return;
+        }
+        Debug.log("Parsing block %s  firstInstruction: %s  loopHeader: %b", block, block.firstInstruction, block.isLoopHeader);
+
+        lastInstr = block.firstInstruction;
+        frameState = block.entryState;
+        currentBlock = block;
+
+        frameState.cleanupDeletedPhis();
+        if (lastInstr instanceof MergeNode) {
+            int bci = block.startBci;
+            if (block instanceof ExceptionBlock) {
+                bci = ((ExceptionBlock) block).deoptBci;
             }
+            ((MergeNode) lastInstr).setStateAfter(frameState.create(bci));
+        }
 
-            if (!isVisited(block)) {
-                markVisited(block);
-                // now parse the block
-                if (block.isLoopHeader) {
-                    LoopBeginNode begin = loopBegin(block);
-                    FrameState preLoopState = ((StateSplit) block.firstInstruction).stateAfter();
-                    FrameState loopState = preLoopState.duplicate(preLoopState.bci);
-                    begin.setStateAfter(loopState);
-                    loopState.insertLoopPhis(begin);
-                    lastInstr = begin;
-                } else {
-                    lastInstr = block.firstInstruction;
-                }
-                frameState.initializeFrom(((StateSplit) lastInstr).stateAfter());
-                assert lastInstr.next() == null : "instructions already appended at block " + block.blockID;
-
-                if (block == returnBlock) {
-                    frameState.setRethrowException(false);
-                    createReturn();
-                } else if (block == unwindBlock) {
-                    frameState.setRethrowException(false);
-                    createUnwind();
-                } else if (block instanceof ExceptionBlock) {
-                    createExceptionDispatch((ExceptionBlock) block);
-                } else if (block instanceof DeoptBlock) {
-                    createDeopt();
-                } else {
-                    frameState.setRethrowException(false);
-                    iterateBytecodesForBlock(block);
-                }
-            }
+        if (block == returnBlock) {
+            frameState.setRethrowException(false);
+            createReturn();
+        } else if (block == unwindBlock) {
+            frameState.setRethrowException(false);
+            createUnwind();
+        } else if (block instanceof ExceptionBlock) {
+            createExceptionDispatch((ExceptionBlock) block);
+        } else if (block instanceof DeoptBlock) {
+            createDeopt();
+        } else {
+            frameState.setRethrowException(false);
+            iterateBytecodesForBlock(block);
         }
     }
 
     private void connectLoopEndToBegin() {
         for (LoopBeginNode begin : currentGraph.getNodes(LoopBeginNode.class)) {
             if (begin.loopEnds().isEmpty()) {
-//              This can happen with degenerated loops like this one:
-//              for (;;) {
-//                  try {
-//                      break;
-//                  } catch (UnresolvedException iioe) {
-//                  }
-//              }
-
-                // Remove the loop begin or transform it into a merge.
-                assert begin.forwardEndCount() > 0;
+                // Remove loop header without loop ends.
+                // This can happen with degenerated loops like this one:
+                // for (;;) {
+                //     try {
+                //         break;
+                //     } catch (UnresolvedException iioe) {
+                //     }
+                // }
+                assert begin.forwardEndCount() == 1;
                 currentGraph.reduceDegenerateLoopBegin(begin);
             } else {
-                begin.stateAfter().simplifyLoopState();
+                // Delete unnecessary loop phi functions, i.e., phi functions where all inputs are either the same or the phi itself.
+                for (PhiNode phi : begin.stateAfter().values().filter(PhiNode.class).snapshot()) {
+                    checkRedundantPhi(phi);
+                }
             }
         }
     }
 
-    private static LoopBeginNode loopBegin(Block block) {
-        LoopBeginNode loopBegin = (LoopBeginNode) ((EndNode) block.firstInstruction.next()).merge();
-        return loopBegin;
+    private static void checkRedundantPhi(PhiNode phiNode) {
+        if (phiNode.isDeleted() || phiNode.valueCount() == 1) {
+            return;
+        }
+
+        ValueNode singleValue = phiNode.singleValue();
+        if (singleValue != null) {
+            Collection<PhiNode> phiUsages = phiNode.usages().filter(PhiNode.class).snapshot();
+            ((StructuredGraph) phiNode.graph()).replaceFloating(phiNode, singleValue);
+            for (PhiNode phi : phiUsages) {
+                checkRedundantPhi(phi);
+            }
+        }
     }
 
     private void createDeopt() {
@@ -1472,9 +1422,30 @@
     }
 
     private void iterateBytecodesForBlock(Block block) {
-        assert frameState != null;
+        if (block.isLoopHeader) {
+            // Create the loop header block, which later will merge the backward branches of the loop.
+            EndNode preLoopEnd = currentGraph.add(new EndNode());
+            LoopBeginNode loopBegin = currentGraph.add(new LoopBeginNode());
+            lastInstr.setNext(preLoopEnd);
+            // Add the single non-loop predecessor of the loop header.
+            loopBegin.addForwardEnd(preLoopEnd);
+            lastInstr = loopBegin;
 
-        currentBlock = block;
+            // Create phi functions for all local variables and operand stack slots.
+            frameState.insertLoopPhis(loopBegin);
+            loopBegin.setStateAfter(frameState.create(block.startBci));
+
+            // We have seen all forward branches. All subsequent backward branches will merge to the loop header.
+            // This ensures that the loop header has exactly one non-loop predecessor.
+            block.firstInstruction = loopBegin;
+            // We need to preserve the frame state builder of the loop header so that we can merge values for
+            // phi functions, so make a copy of it.
+            block.entryState = frameState.copy();
+
+            Debug.log("  created loop header %s", loopBegin);
+        }
+        assert lastInstr.next() == null : "instructions already appended at block " + block;
+        Debug.log("  frameState: %s", frameState);
 
         int endBCI = stream.endBCI();
 
@@ -1761,31 +1732,4 @@
     private void genArrayLength() {
         frameState.ipush(append(currentGraph.add(new ArrayLengthNode(frameState.apop()))));
     }
-
-    /**
-     * Adds a block to the worklist, if it is not already in the worklist.
-     * This method will keep the worklist topologically stored (i.e. the lower
-     * DFNs are earlier in the list).
-     * @param block the block to add to the work list
-     */
-    private void addToWorkList(Block block) {
-        if (!isOnWorkList(block)) {
-            markOnWorkList(block);
-            sortIntoWorkList(block);
-        }
-    }
-
-    private void sortIntoWorkList(Block top) {
-        workList.offer(top);
-    }
-
-    /**
-     * Removes the next block from the worklist. The list is sorted topologically, so the
-     * block with the lowest depth first number in the list will be removed and returned.
-     * @return the next block from the worklist; {@code null} if there are no blocks
-     * in the worklist
-     */
-    private Block removeFromWorkList() {
-        return workList.poll();
-    }
 }
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/FrameState.java	Mon Mar 05 14:38:43 2012 +0100
+++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/FrameState.java	Mon Mar 05 09:55:54 2012 -0800
@@ -28,7 +28,6 @@
 import com.oracle.max.cri.ri.*;
 import com.oracle.max.graal.graph.*;
 import com.oracle.max.graal.graph.iterators.*;
-import com.oracle.max.graal.nodes.PhiNode.PhiType;
 import com.oracle.max.graal.nodes.spi.*;
 import com.oracle.max.graal.nodes.virtual.*;
 
@@ -36,7 +35,7 @@
  * The {@code FrameState} class encapsulates the frame state (i.e. local variables and
  * operand stack) at a particular point in the abstract interpretation.
  */
-public final class FrameState extends Node implements FrameStateAccess, Node.IterableNodeType, LIRLowerable {
+public final class FrameState extends Node implements Node.IterableNodeType, LIRLowerable {
 
     protected final int localsSize;
 
@@ -114,9 +113,11 @@
         this.stackSize = stackSize;
         final ValueNode[] newValues = new ValueNode[locals.length + stackSize];
         for (int i = 0; i < locals.length; i++) {
+            assert locals[i] == null || !locals[i].isDeleted();
             newValues[i] = locals[i];
         }
         for (int i = 0; i < stackSize; i++) {
+            assert stack[i] == null || !stack[i].isDeleted();
             newValues[localsSize + i] = stack[i];
         }
         this.values = new NodeInputList<>(this, newValues);
@@ -126,6 +127,10 @@
         assert !rethrowException || stackSize == 1 : "must have exception on top of the stack";
     }
 
+    public NodeIterable<ValueNode> values() {
+        return values;
+    }
+
     public FrameState outerFrameState() {
         return outerFrameState;
     }
@@ -135,15 +140,7 @@
         this.outerFrameState = x;
     }
 
-    public FrameState outermostFrameState() {
-        FrameState fs = this;
-        while (fs.outerFrameState() != null) {
-            fs = fs.outerFrameState();
-        }
-        return fs;
-    }
-
-    public void setValueAt(int i, ValueNode x) {
+    private void setValueAt(int i, ValueNode x) {
         values.set(i, x);
     }
 
@@ -199,18 +196,22 @@
         return other;
     }
 
-    @Override
-    public FrameState duplicateWithException(int newBci, ValueNode exceptionObject) {
-        return duplicateModified(newBci, true, CiKind.Void, exceptionObject);
-    }
-
     /**
      * Creates a copy of this frame state with one stack element of type popKind popped from the stack and the
      * values in pushedValues pushed on the stack. The pushedValues are expected to be in slot encoding: a long
      * or double is followed by a null slot.
      */
     public FrameState duplicateModified(int newBci, boolean newRethrowException, CiKind popKind, ValueNode... pushedValues) {
-        int popSlots = popKind == CiKind.Void ? 0 : isTwoSlot(popKind) ? 2 : 1;
+        int popSlots = 0;
+        if (popKind != CiKind.Void) {
+            if (stackAt(stackSize() - 1) == null) {
+                popSlots = 2;
+            } else {
+                popSlots = 1;
+            }
+            assert stackAt(stackSize() - popSlots).kind().stackKind() == popKind.stackKind();
+        }
+
         int pushSlots = pushedValues.length;
         FrameState other = graph().add(new FrameState(method, newBci, localsSize, stackSize - popSlots + pushSlots, newRethrowException, false));
         for (int i = 0; i < localsSize; i++) {
@@ -228,40 +229,6 @@
         return other;
     }
 
-    public boolean isCompatibleWith(FrameStateAccess other) {
-        if (stackSize() != other.stackSize() || localsSize() != other.localsSize()) {
-            return false;
-        }
-        for (int i = 0; i < stackSize(); i++) {
-            ValueNode x = stackAt(i);
-            ValueNode y = other.stackAt(i);
-            if (x != y && ValueUtil.typeMismatch(x, y)) {
-                return false;
-            }
-        }
-        if (other.outerFrameState() != outerFrameState()) {
-            return false;
-        }
-        return true;
-    }
-
-    public boolean equals(FrameStateAccess other) {
-        if (stackSize() != other.stackSize() || localsSize() != other.localsSize()) {
-            return false;
-        }
-        for (int i = 0; i < stackSize(); i++) {
-            ValueNode x = stackAt(i);
-            ValueNode y = other.stackAt(i);
-            if (x != y) {
-                return false;
-            }
-        }
-        if (other.outerFrameState() != outerFrameState()) {
-            return false;
-        }
-        return true;
-    }
-
     /**
      * Gets the size of the local variables.
      */
@@ -277,52 +244,14 @@
     }
 
     /**
-     * Invalidates the local variable at the specified index. If the specified index refers to a doubleword local, then
-     * invalidates the high word as well.
-     *
-     * @param i the index of the local to invalidate
-     */
-    public void invalidateLocal(int i) {
-        // note that for double word locals, the high slot should already be null
-        // unless the local is actually dead and the high slot is being reused;
-        // in either case, it is not necessary to null the high slot
-        setValueAt(i, null);
-    }
-
-    /**
-     * Stores a given local variable at the specified index. If the value is a {@linkplain CiKind#isDoubleWord() double word},
-     * then the next local variable index is also overwritten.
-     *
-     * @param i the index at which to store
-     * @param x the instruction which produces the value for the local
-     */
-    // TODO this duplicates code in FrameStateBuilder and needs to go away
-    public void storeLocal(int i, ValueNode x) {
-        assert i < localsSize : "local variable index out of range: " + i;
-        invalidateLocal(i);
-        setValueAt(i, x);
-        if (isTwoSlot(x.kind())) {
-            // (tw) if this was a double word then kill i+1
-            setValueAt(i + 1, null);
-        }
-        if (i > 0) {
-            // if there was a double word at i - 1, then kill it
-            ValueNode p = localAt(i - 1);
-            if (p != null && isTwoSlot(p.kind())) {
-                setValueAt(i - 1, null);
-            }
-        }
-    }
-
-    /**
      * Gets the value in the local variables at the specified index.
      *
      * @param i the index into the locals
      * @return the instruction that produced the value for the specified local
      */
     public ValueNode localAt(int i) {
-        assert i < localsSize : "local variable index out of range: " + i;
-        return valueAt(i);
+        assert i >= 0 && i < localsSize : "local variable index out of range: " + i;
+        return values.get(i);
     }
 
     /**
@@ -332,233 +261,38 @@
      * @return the instruction at the specified position in the stack
      */
     public ValueNode stackAt(int i) {
-        assert i >= 0 && i < (localsSize + stackSize);
-        return valueAt(localsSize + i);
-    }
-
-    /**
-     * Inserts a phi statement into the stack at the specified stack index.
-     * @param block the block begin for which we are creating the phi
-     * @param i the index into the stack for which to create a phi
-     */
-    public PhiNode setupLoopPhiForStack(MergeNode block, int i) {
-        ValueNode p = stackAt(i);
-        if (p != null) {
-            if (p instanceof PhiNode) {
-                PhiNode phi = (PhiNode) p;
-                if (phi.merge() == block) {
-                    return phi;
-                }
-            }
-            PhiNode phi = graph().unique(new PhiNode(p.kind(), block, PhiType.Value));
-            phi.addInput(p);
-            setValueAt(localsSize + i, phi);
-            return phi;
-        }
-        return null;
-    }
-
-    /**
-     * Inserts a phi statement for the local at the specified index.
-     * @param block the block begin for which we are creating the phi
-     * @param i the index of the local variable for which to create the phi
-     */
-    public PhiNode setupLoopPhiForLocal(MergeNode block, int i) {
-        ValueNode p = localAt(i);
-        if (p instanceof PhiNode) {
-            PhiNode phi = (PhiNode) p;
-            if (phi.merge() == block) {
-                return phi;
-            }
-        }
-        PhiNode phi = graph().unique(new PhiNode(p.kind(), block, PhiType.Value));
-        phi.addInput(p);
-        storeLocal(i, phi);
-        return phi;
-    }
-
-    /**
-     * Gets the value at a specified index in the set of operand stack and local values represented by this frame.
-     * This method should only be used to iterate over all the values in this frame, irrespective of whether
-     * they are on the stack or in local variables.
-     * To iterate the stack slots, the {@link #stackAt(int)} and {@link #stackSize()} methods should be used.
-     * To iterate the local variables, the {@link #localAt(int)} and {@link #localsSize()} methods should be used.
-     *
-     * @param i a value in the range {@code [0 .. valuesSize()]}
-     * @return the value at index {@code i} which may be {@code null}
-     */
-    public ValueNode valueAt(int i) {
-        assert i < (localsSize + stackSize);
-        return values.isEmpty() ? null : values.get(i);
-    }
-
-    /**
-     * The number of operand stack slots and local variables in this frame.
-     * This method should typically only be used in conjunction with {@link #valueAt(int)}.
-     * To iterate the stack slots, the {@link #stackAt(int)} and {@link #stackSize()} methods should be used.
-     * To iterate the local variables, the {@link #localAt(int)} and {@link #localsSize()} methods should be used.
-     *
-     * @return the number of local variables in this frame
-     */
-    public int valuesSize() {
-        return localsSize + stackSize;
-    }
-
-    private boolean checkSize(FrameStateAccess other) {
-        assert other.stackSize() == stackSize() : "stack sizes do not match";
-        assert other.localsSize() == localsSize : "local sizes do not match";
-        return true;
-    }
-
-    public void merge(MergeNode block, FrameStateAccess other) {
-        assert checkSize(other);
-        for (int i = 0; i < valuesSize(); i++) {
-            ValueNode currentValue = valueAt(i);
-            ValueNode otherValue = other.valueAt(i);
-            if (currentValue != otherValue || block instanceof LoopBeginNode) {
-                if (block.isPhiAtMerge(currentValue)) {
-                    addToPhi((PhiNode) currentValue, otherValue, block instanceof LoopBeginNode);
-                } else {
-                    setValueAt(i, combineValues(currentValue, otherValue, block));
-                }
-            }
-        }
-    }
-
-    public void simplifyLoopState() {
-        for (PhiNode phi : values.filter(PhiNode.class).snapshot()) {
-            checkRedundantPhi(phi);
-        }
-    }
-
-    private static ValueNode combineValues(ValueNode currentValue, ValueNode otherValue, MergeNode block) {
-        if (currentValue == null || otherValue == null || currentValue.kind() != otherValue.kind()) {
-            return null;
-        }
-
-        PhiNode phi = currentValue.graph().add(new PhiNode(currentValue.kind(), block, PhiType.Value));
-        for (int j = 0; j < block.phiPredecessorCount(); ++j) {
-            phi.addInput(currentValue);
-        }
-        phi.addInput(otherValue);
-        assert phi.valueCount() == block.phiPredecessorCount() + 1 : "valueCount=" + phi.valueCount() + " predSize= " + block.phiPredecessorCount();
-        return phi;
-    }
-
-    private static void addToPhi(PhiNode phiNode, ValueNode otherValue, boolean recursiveInvalidCheck) {
-        if (otherValue == null || otherValue.kind() != phiNode.kind()) {
-            if (recursiveInvalidCheck) {
-                deleteInvalidPhi(phiNode);
-            } else {
-                phiNode.replaceAtUsages(null);
-                phiNode.safeDelete();
-            }
-        } else {
-            phiNode.addInput(otherValue);
-        }
-    }
-
-    public static void deleteRedundantPhi(PhiNode redundantPhi, ValueNode phiValue) {
-        Collection<PhiNode> phiUsages = redundantPhi.usages().filter(PhiNode.class).snapshot();
-        ((StructuredGraph) redundantPhi.graph()).replaceFloating(redundantPhi, phiValue);
-        for (PhiNode phi : phiUsages) {
-            checkRedundantPhi(phi);
-        }
-    }
-
-    private static void checkRedundantPhi(PhiNode phiNode) {
-        if (phiNode.isDeleted() || phiNode.valueCount() == 1) {
-            return;
-        }
-
-        ValueNode singleValue = phiNode.singleValue();
-        if (singleValue != null) {
-            deleteRedundantPhi(phiNode, singleValue);
-        }
-    }
-
-    private static void deleteInvalidPhi(PhiNode phiNode) {
-        if (!phiNode.isDeleted()) {
-            Collection<PhiNode> phiUsages = phiNode.usages().filter(PhiNode.class).snapshot();
-            phiNode.replaceAtUsages(null);
-            phiNode.safeDelete();
-            for (Node n : phiUsages) {
-                deleteInvalidPhi((PhiNode) n);
-            }
-        }
+        assert i >= 0 && i < stackSize;
+        return values.get(localsSize + i);
     }
 
     public MergeNode block() {
         return usages().filter(MergeNode.class).first();
     }
 
-    public StateSplit stateSplit() {
-        return (StateSplit) usages().filterInterface(StateSplit.class).first();
-    }
-
     public NodeIterable<FrameState> innerFrameStates() {
         return usages().filter(FrameState.class);
     }
 
-    /**
-     * The interface implemented by a client of {@link FrameState#forEachPhi(MergeNode, PhiProcedure)} and
-     * {@link FrameState#forEachLivePhi(MergeNode, PhiProcedure)}.
-     */
-    public interface PhiProcedure {
-        boolean doPhi(PhiNode phi);
-    }
-
-    /**
-     * Checks whether this frame state has any {@linkplain PhiNode phi} statements.
-     */
-    public boolean hasPhis() {
-        for (int i = 0; i < valuesSize(); i++) {
-            ValueNode value = valueAt(i);
-            if (value instanceof PhiNode) {
-                return true;
-            }
-        }
-        return false;
-    }
-
-    public String toDetailedString() {
-        StringBuilder sb = new StringBuilder();
-        String nl = String.format("%n");
-        sb.append("[bci: ").append(bci).append("]");
-        if (rethrowException()) {
-            sb.append(" rethrows Exception");
-        }
-        sb.append(nl);
-        for (int i = 0; i < localsSize(); ++i) {
-            ValueNode value = localAt(i);
-            sb.append(String.format("  local[%d] = %-8s : %s%n", i, value == null ? "bogus" : value.kind().javaName, value));
-        }
-        for (int i = 0; i < stackSize(); ++i) {
-            ValueNode value = stackAt(i);
-            sb.append(String.format("  stack[%d] = %-8s : %s%n", i, value == null ? "bogus" : value.kind().javaName, value));
-        }
-        return sb.toString();
-    }
-
     @Override
     public void generate(LIRGeneratorTool gen) {
         // Nothing to do, frame states are processed as part of the handling of AbstractStateSplit nodes.
     }
 
-    public static String toString(FrameState frameState) {
+    private static String toString(FrameState frameState) {
         StringBuilder sb = new StringBuilder();
         String nl = CiUtil.NEW_LINE;
         FrameState fs = frameState;
         while (fs != null) {
             CiUtil.appendLocation(sb, fs.method, fs.bci).append(nl);
-            for (int i = 0; i < fs.localsSize(); ++i) {
-                ValueNode value = fs.localAt(i);
-                sb.append(String.format("  local[%d] = %-8s : %s%n", i, value == null ? "bogus" : value.kind().javaName, value));
+            sb.append("locals: [");
+            for (int i = 0; i < fs.localsSize(); i++) {
+                sb.append(i == 0 ? "" : ", ").append(fs.localAt(i) == null ? "_" : fs.localAt(i).toString(Verbosity.Id));
             }
-            for (int i = 0; i < fs.stackSize(); ++i) {
-                ValueNode value = fs.stackAt(i);
-                sb.append(String.format("  stack[%d] = %-8s : %s%n", i, value == null ? "bogus" : value.kind().javaName, value));
+            sb.append("]").append(nl).append("stack: ");
+            for (int i = 0; i < fs.stackSize(); i++) {
+                sb.append(i == 0 ? "" : ", ").append(fs.stackAt(i) == null ? "_" : fs.stackAt(i).toString(Verbosity.Id));
             }
+            sb.append(nl);
             fs = fs.outerFrameState();
         }
         return sb.toString();
@@ -575,22 +309,6 @@
         }
     }
 
-    public void insertLoopPhis(LoopBeginNode loopBegin) {
-        for (int i = 0; i < stackSize(); i++) {
-            // always insert phis for the stack
-            ValueNode x = stackAt(i);
-            if (x != null) {
-                setupLoopPhiForStack(loopBegin, i);
-            }
-        }
-        for (int i = 0; i < localsSize(); i++) {
-            ValueNode x = localAt(i);
-            if (x != null) {
-                setupLoopPhiForLocal(loopBegin, i);
-            }
-        }
-    }
-
     @Override
     public Map<Object, Object> getDebugProperties() {
         Map<Object, Object> properties = super.getDebugProperties();
@@ -600,41 +318,27 @@
         } else {
             properties.put("method", "None");
         }
-        StringBuilder str = new StringBuilder();
+        StringBuilder sb = new StringBuilder();
         for (int i = 0; i < localsSize(); i++) {
-            str.append(i == 0 ? "" : ", ").append(localAt(i) == null ? "_" : localAt(i).toString(Verbosity.Id));
+            sb.append(i == 0 ? "" : ", ").append(localAt(i) == null ? "_" : localAt(i).toString(Verbosity.Id));
         }
-        properties.put("locals", str.toString());
-        str = new StringBuilder();
+        properties.put("locals", sb.toString());
+        sb = new StringBuilder();
         for (int i = 0; i < stackSize(); i++) {
-            str.append(i == 0 ? "" : ", ").append(stackAt(i) == null ? "_" : stackAt(i).toString(Verbosity.Id));
+            sb.append(i == 0 ? "" : ", ").append(stackAt(i) == null ? "_" : stackAt(i).toString(Verbosity.Id));
         }
-        properties.put("stack", str.toString());
+        properties.put("stack", sb.toString());
         properties.put("rethrowException", rethrowException);
         properties.put("duringCall", duringCall);
         return properties;
     }
 
-    public CiCodePos toCodePos() {
-        FrameState caller = outerFrameState();
-        CiCodePos callerCodePos = null;
-        if (caller != null) {
-            callerCodePos = caller.toCodePos();
-        }
-        return new CiCodePos(callerCodePos, method, bci);
-    }
-
     @Override
     public boolean verify() {
         for (ValueNode value : values) {
+            assert assertTrue(value == null || !value.isDeleted(), "frame state must not contain deleted nodes");
             assert assertTrue(value == null || value instanceof VirtualObjectNode || (value.kind() != CiKind.Void && value.kind() != CiKind.Illegal), "unexpected value: %s", value);
         }
         return super.verify();
     }
-
-    // TODO this duplicates code in FrameStateBuilder and needs to go away
-    public static boolean isTwoSlot(CiKind kind) {
-        assert kind != CiKind.Void && kind != CiKind.Illegal;
-        return kind == CiKind.Long || kind == CiKind.Double;
-    }
 }
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/PlaceholderNode.java	Mon Mar 05 14:38:43 2012 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,40 +0,0 @@
-/*
- * 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.nodes;
-
-import com.oracle.max.graal.graph.*;
-import com.oracle.max.graal.nodes.spi.*;
-import com.oracle.max.graal.nodes.type.*;
-
-
-public class PlaceholderNode extends AbstractStateSplit implements Node.IterableNodeType, LIRLowerable {
-
-    public PlaceholderNode() {
-        super(StampFactory.illegal());
-    }
-
-    @Override
-    public void generate(LIRGeneratorTool gen) {
-        // nothing to do
-    }
-}
--- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/spi/FrameStateAccess.java	Mon Mar 05 14:38:43 2012 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,47 +0,0 @@
-/*
- * Copyright (c) 2012, 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.nodes.spi;
-
-import com.oracle.max.graal.nodes.*;
-
-public interface FrameStateAccess {
-
-    FrameState duplicate(int newBci);
-
-    int localsSize();
-
-    int stackSize();
-
-    boolean rethrowException();
-
-    ValueNode valueAt(int i);
-
-    ValueNode localAt(int i);
-
-    ValueNode stackAt(int i);
-
-    FrameState outerFrameState();
-
-    FrameState duplicateWithException(int bci, ValueNode exceptionObject);
-
-}