# HG changeset patch
# User Christian Wirth <christian.wirth@oracle.com>
# Date 1394807357 -3600
# Node ID f659d019d3ab9153631e7c419a1392c4efbc36e5
# Parent  47b775458982c5d000c4ac9a931f3ae39ceabf76# Parent  360beb9b3c50c7e7919616847ee16eb2d17a1e53
Merged

diff -r 47b775458982 -r f659d019d3ab graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java	Fri Mar 14 09:58:31 2014 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java	Fri Mar 14 15:29:17 2014 +0100
@@ -45,8 +45,8 @@
         this.nodeOperands = nodeOperands;
     }
 
-    protected HashMap<VirtualObjectNode, VirtualObject> virtualObjects = new HashMap<>();
-    protected IdentityHashMap<VirtualObjectNode, EscapeObjectState> objectStates = new IdentityHashMap<>();
+    protected final HashMap<VirtualObjectNode, VirtualObject> virtualObjects = new HashMap<>();
+    protected final IdentityHashMap<VirtualObjectNode, EscapeObjectState> objectStates = new IdentityHashMap<>();
 
     public LIRFrameState build(FrameState topState, LabelRef exceptionEdge) {
         assert virtualObjects.size() == 0;
diff -r 47b775458982 -r f659d019d3ab graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeList.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeList.java	Fri Mar 14 09:58:31 2014 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeList.java	Fri Mar 14 15:29:17 2014 +0100
@@ -257,7 +257,7 @@
     }
 
     @Override
-    public void snapshotTo(List<T> to) {
+    public void snapshotTo(Collection<T> to) {
         for (int i = 0; i < size; i++) {
             to.add(get(i));
         }
diff -r 47b775458982 -r f659d019d3ab graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/AbstractNodeIterable.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/AbstractNodeIterable.java	Fri Mar 14 09:58:31 2014 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/AbstractNodeIterable.java	Fri Mar 14 15:29:17 2014 +0100
@@ -74,7 +74,7 @@
     }
 
     @Override
-    public void snapshotTo(List<T> to) {
+    public void snapshotTo(Collection<T> to) {
         for (T n : this) {
             to.add(n);
         }
diff -r 47b775458982 -r f659d019d3ab graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java	Fri Mar 14 09:58:31 2014 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java	Fri Mar 14 15:29:17 2014 +0100
@@ -44,7 +44,7 @@
 
     List<T> snapshot();
 
-    void snapshotTo(List<T> to);
+    void snapshotTo(Collection<T> to);
 
     T first();
 
diff -r 47b775458982 -r f659d019d3ab graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java	Fri Mar 14 09:58:31 2014 +0100
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java	Fri Mar 14 15:29:17 2014 +0100
@@ -99,11 +99,6 @@
         public Block retSuccessor;
         public boolean endsWithRet = false;
 
-        public BitSet localsLiveIn;
-        public BitSet localsLiveOut;
-        private BitSet localsLiveGen;
-        private BitSet localsLiveKill;
-
         public Block exceptionDispatchBlock() {
             if (successors.size() > 0 && successors.get(successors.size() - 1) instanceof ExceptionDispatchBlock) {
                 return successors.get(successors.size() - 1);
@@ -167,6 +162,8 @@
     private Block[] blockMap;
     public Block[] loopHeaders;
 
+    public LocalLiveness liveness;
+
     /**
      * Creates a new BlockMap instance from bytecode of the given method .
      * 
@@ -212,7 +209,8 @@
         }
         if (OptLivenessAnalysis.getValue()) {
             try (Scope s = Debug.scope("LivenessAnalysis")) {
-                computeLiveness();
+                liveness = method.getMaxLocals() <= 64 ? new SmallLocalLiveness() : new LargeLocalLiveness();
+                liveness.computeLiveness();
             } catch (Throwable e) {
                 throw Debug.handle(e);
             }
@@ -729,153 +727,225 @@
         return loops;
     }
 
-    private void computeLiveness() {
-        for (Block block : blocks) {
-            computeLocalLiveness(block);
-        }
+    /**
+     * Encapsulates the liveness calculation, so that subclasses for locals <= 64 and locals > 64
+     * can be implemented.
+     */
+    public abstract class LocalLiveness {
+
+        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 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);
+                    int blockID = block.blockID;
+                    // log statements in IFs because debugLiveX creates a new String
+                    if (Debug.isLogEnabled()) {
+                        Debug.log("  start B%d  [%d, %d]  in: %s  out: %s  gen: %s  kill: %s", block.blockID, block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID),
+                                        debugLiveGen(blockID), debugLiveKill(blockID));
+                    }
 
-                boolean blockChanged = (iteration == 0);
-                if (block.successors.size() > 0) {
-                    int oldCardinality = block.localsLiveOut.cardinality();
-                    for (Block sux : block.successors) {
-                        Debug.log("    Successor B%d: %s", sux.blockID, sux.localsLiveIn);
-                        block.localsLiveOut.or(sux.localsLiveIn);
+                    boolean blockChanged = (iteration == 0);
+                    if (block.successors.size() > 0) {
+                        int oldCardinality = liveOutCardinality(blockID);
+                        for (Block sux : block.successors) {
+                            if (Debug.isLogEnabled()) {
+                                Debug.log("    Successor B%d: %s", sux.blockID, debugLiveIn(sux.blockID));
+                            }
+                            propagateLiveness(blockID, sux.blockID);
+                        }
+                        blockChanged |= (oldCardinality != liveOutCardinality(blockID));
                     }
-                    blockChanged |= (oldCardinality != block.localsLiveOut.cardinality());
+
+                    if (blockChanged) {
+                        updateLiveness(blockID);
+                        if (Debug.isLogEnabled()) {
+                            Debug.log("  end   B%d  [%d, %d]  in: %s  out: %s  gen: %s  kill: %s", block.blockID, block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID),
+                                            debugLiveGen(blockID), debugLiveKill(blockID));
+                        }
+                    }
+                    changed |= blockChanged;
                 }
-
-                if (blockChanged) {
-                    block.localsLiveIn.clear();
-                    block.localsLiveIn.or(block.localsLiveOut);
-                    block.localsLiveIn.andNot(block.localsLiveKill);
-                    block.localsLiveIn.or(block.localsLiveGen);
-                    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 BitSet(method.getMaxLocals());
-        block.localsLiveOut = new BitSet(method.getMaxLocals());
-        block.localsLiveGen = new BitSet(method.getMaxLocals());
-        block.localsLiveKill = new BitSet(method.getMaxLocals());
-
-        if (block.startBci < 0 || block.endBci < 0) {
-            return;
+                iteration++;
+            } while (changed);
         }
 
-        stream.setBCI(block.startBci);
-        while (stream.currentBCI() <= block.endBci) {
-            switch (stream.currentBC()) {
-                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;
+        /**
+         * Returns whether the local is live at the beginning of the given block.
+         */
+        public abstract boolean localIsLiveIn(Block block, int local);
+
+        /**
+         * Returns whether the local is live at the end of the given block.
+         */
+        public abstract boolean localIsLiveOut(Block block, int local);
+
+        /**
+         * Returns a string representation of the liveIn values of the given block.
+         */
+        protected abstract String debugLiveIn(int blockID);
+
+        /**
+         * Returns a string representation of the liveOut values of the given block.
+         */
+        protected abstract String debugLiveOut(int blockID);
+
+        /**
+         * Returns a string representation of the liveGen values of the given block.
+         */
+        protected abstract String debugLiveGen(int blockID);
+
+        /**
+         * Returns a string representation of the liveKill values of the given block.
+         */
+        protected abstract String debugLiveKill(int blockID);
+
+        /**
+         * Returns the number of live locals at the end of the given block.
+         */
+        protected abstract int liveOutCardinality(int blockID);
+
+        /**
+         * Adds all locals the are in the liveIn of the successor to the liveOut of the block.
+         */
+        protected abstract void propagateLiveness(int blockID, int successorID);
+
+        /**
+         * Calculates a new liveIn for the given block from liveOut, liveKill and liveGen.
+         */
+        protected abstract void updateLiveness(int blockID);
+
+        /**
+         * Adds the local to liveGen if it wasn't already killed in this block.
+         */
+        protected abstract void loadOne(int blockID, int local);
+
+        /**
+         * Add this local to liveKill if it wasn't already generated in this block.
+         */
+        protected abstract void storeOne(int blockID, int local);
 
-                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;
+        private void computeLocalLiveness(Block block) {
+            if (block.startBci < 0 || block.endBci < 0) {
+                return;
             }
-            stream.next();
+            int blockID = block.blockID;
+            stream.setBCI(block.startBci);
+            while (stream.currentBCI() <= block.endBci) {
+                switch (stream.currentBC()) {
+                    case LLOAD:
+                    case DLOAD:
+                        loadTwo(blockID, stream.readLocalIndex());
+                        break;
+                    case LLOAD_0:
+                    case DLOAD_0:
+                        loadTwo(blockID, 0);
+                        break;
+                    case LLOAD_1:
+                    case DLOAD_1:
+                        loadTwo(blockID, 1);
+                        break;
+                    case LLOAD_2:
+                    case DLOAD_2:
+                        loadTwo(blockID, 2);
+                        break;
+                    case LLOAD_3:
+                    case DLOAD_3:
+                        loadTwo(blockID, 3);
+                        break;
+                    case ILOAD:
+                    case IINC:
+                    case FLOAD:
+                    case ALOAD:
+                    case RET:
+                        loadOne(blockID, stream.readLocalIndex());
+                        break;
+                    case ILOAD_0:
+                    case FLOAD_0:
+                    case ALOAD_0:
+                        loadOne(blockID, 0);
+                        break;
+                    case ILOAD_1:
+                    case FLOAD_1:
+                    case ALOAD_1:
+                        loadOne(blockID, 1);
+                        break;
+                    case ILOAD_2:
+                    case FLOAD_2:
+                    case ALOAD_2:
+                        loadOne(blockID, 2);
+                        break;
+                    case ILOAD_3:
+                    case FLOAD_3:
+                    case ALOAD_3:
+                        loadOne(blockID, 3);
+                        break;
+
+                    case LSTORE:
+                    case DSTORE:
+                        storeTwo(blockID, stream.readLocalIndex());
+                        break;
+                    case LSTORE_0:
+                    case DSTORE_0:
+                        storeTwo(blockID, 0);
+                        break;
+                    case LSTORE_1:
+                    case DSTORE_1:
+                        storeTwo(blockID, 1);
+                        break;
+                    case LSTORE_2:
+                    case DSTORE_2:
+                        storeTwo(blockID, 2);
+                        break;
+                    case LSTORE_3:
+                    case DSTORE_3:
+                        storeTwo(blockID, 3);
+                        break;
+                    case ISTORE:
+                    case FSTORE:
+                    case ASTORE:
+                        storeOne(blockID, stream.readLocalIndex());
+                        break;
+                    case ISTORE_0:
+                    case FSTORE_0:
+                    case ASTORE_0:
+                        storeOne(blockID, 0);
+                        break;
+                    case ISTORE_1:
+                    case FSTORE_1:
+                    case ASTORE_1:
+                        storeOne(blockID, 1);
+                        break;
+                    case ISTORE_2:
+                    case FSTORE_2:
+                    case ASTORE_2:
+                        storeOne(blockID, 2);
+                        break;
+                    case ISTORE_3:
+                    case FSTORE_3:
+                    case ASTORE_3:
+                        storeOne(blockID, 3);
+                        break;
+                }
+                stream.next();
+            }
+        }
+
+        private void loadTwo(int blockID, int local) {
+            loadOne(blockID, local);
+            loadOne(blockID, local + 1);
+        }
+
+        private void storeTwo(int blockID, int local) {
+            storeOne(blockID, local);
+            storeOne(blockID, local + 1);
         }
     }
 
@@ -889,25 +959,182 @@
         return map;
     }
 
-    private static void loadTwo(Block block, int local) {
-        loadOne(block, local);
-        loadOne(block, local + 1);
-    }
+    public final class SmallLocalLiveness extends LocalLiveness {
+        /*
+         * local n is represented by the bit accessible as (1 << n)
+         */
+
+        private final long[] localsLiveIn;
+        private final long[] localsLiveOut;
+        private final long[] localsLiveGen;
+        private final long[] localsLiveKill;
+
+        public SmallLocalLiveness() {
+            localsLiveIn = new long[blocks.size()];
+            localsLiveOut = new long[blocks.size()];
+            localsLiveGen = new long[blocks.size()];
+            localsLiveKill = new long[blocks.size()];
+        }
+
+        private String debugString(long value) {
+            StringBuilder str = new StringBuilder("{");
+            long current = value;
+            for (int i = 0; i < method.getMaxLocals(); i++) {
+                if ((current & 1L) == 1L) {
+                    if (str.length() > 1) {
+                        str.append(", ");
+                    }
+                    str.append(i);
+                }
+                current >>= 1;
+            }
+            return str.append('}').toString();
+        }
+
+        @Override
+        protected String debugLiveIn(int blockID) {
+            return debugString(localsLiveIn[blockID]);
+        }
+
+        @Override
+        protected String debugLiveOut(int blockID) {
+            return debugString(localsLiveOut[blockID]);
+        }
+
+        @Override
+        protected String debugLiveGen(int blockID) {
+            return debugString(localsLiveGen[blockID]);
+        }
 
-    private static void loadOne(Block block, int local) {
-        if (!block.localsLiveKill.get(local)) {
-            block.localsLiveGen.set(local);
+        @Override
+        protected String debugLiveKill(int blockID) {
+            return debugString(localsLiveKill[blockID]);
+        }
+
+        @Override
+        protected int liveOutCardinality(int blockID) {
+            return Long.bitCount(localsLiveOut[blockID]);
+        }
+
+        @Override
+        protected void propagateLiveness(int blockID, int successorID) {
+            localsLiveOut[blockID] |= localsLiveIn[successorID];
+        }
+
+        @Override
+        protected void updateLiveness(int blockID) {
+            localsLiveIn[blockID] = (localsLiveOut[blockID] & ~localsLiveKill[blockID]) | localsLiveGen[blockID];
+        }
+
+        @Override
+        protected void loadOne(int blockID, int local) {
+            long bit = 1L << local;
+            if ((localsLiveKill[blockID] & bit) == 0L) {
+                localsLiveGen[blockID] |= bit;
+            }
+        }
+
+        @Override
+        protected void storeOne(int blockID, int local) {
+            long bit = 1L << local;
+            if ((localsLiveGen[blockID] & bit) == 0L) {
+                localsLiveKill[blockID] |= bit;
+            }
+        }
+
+        @Override
+        public boolean localIsLiveIn(Block block, int local) {
+            int blockID = block.blockID;
+            return blockID >= Integer.MAX_VALUE ? false : (localsLiveIn[blockID] & (1L << local)) != 0L;
+        }
+
+        @Override
+        public boolean localIsLiveOut(Block block, int local) {
+            int blockID = block.blockID;
+            return blockID >= Integer.MAX_VALUE ? false : (localsLiveOut[blockID] & (1L << local)) != 0L;
         }
     }
 
-    private static void storeTwo(Block block, int local) {
-        storeOne(block, local);
-        storeOne(block, local + 1);
-    }
+    public final class LargeLocalLiveness extends LocalLiveness {
+        private BitSet[] localsLiveIn;
+        private BitSet[] localsLiveOut;
+        private BitSet[] localsLiveGen;
+        private BitSet[] localsLiveKill;
+
+        public LargeLocalLiveness() {
+            localsLiveIn = new BitSet[blocks.size()];
+            localsLiveOut = new BitSet[blocks.size()];
+            localsLiveGen = new BitSet[blocks.size()];
+            localsLiveKill = new BitSet[blocks.size()];
+            for (int i = 0; i < blocks.size(); i++) {
+                localsLiveIn[i] = new BitSet(method.getMaxLocals());
+                localsLiveOut[i] = new BitSet(method.getMaxLocals());
+                localsLiveGen[i] = new BitSet(method.getMaxLocals());
+                localsLiveKill[i] = new BitSet(method.getMaxLocals());
+            }
+        }
+
+        @Override
+        protected String debugLiveIn(int blockID) {
+            return localsLiveIn[blockID].toString();
+        }
+
+        @Override
+        protected String debugLiveOut(int blockID) {
+            return localsLiveOut[blockID].toString();
+        }
+
+        @Override
+        protected String debugLiveGen(int blockID) {
+            return localsLiveGen[blockID].toString();
+        }
+
+        @Override
+        protected String debugLiveKill(int blockID) {
+            return localsLiveKill[blockID].toString();
+        }
 
-    private static void storeOne(Block block, int local) {
-        if (!block.localsLiveGen.get(local)) {
-            block.localsLiveKill.set(local);
+        @Override
+        protected int liveOutCardinality(int blockID) {
+            return localsLiveOut[blockID].cardinality();
+        }
+
+        @Override
+        protected void propagateLiveness(int blockID, int successorID) {
+            localsLiveOut[blockID].or(localsLiveIn[successorID]);
+        }
+
+        @Override
+        protected void updateLiveness(int blockID) {
+            BitSet liveIn = localsLiveIn[blockID];
+            liveIn.clear();
+            liveIn.or(localsLiveOut[blockID]);
+            liveIn.andNot(localsLiveKill[blockID]);
+            liveIn.or(localsLiveGen[blockID]);
+        }
+
+        @Override
+        protected void loadOne(int blockID, int local) {
+            if (!localsLiveKill[blockID].get(local)) {
+                localsLiveGen[blockID].set(local);
+            }
+        }
+
+        @Override
+        protected void storeOne(int blockID, int local) {
+            if (!localsLiveGen[blockID].get(local)) {
+                localsLiveKill[blockID].set(local);
+            }
+        }
+
+        @Override
+        public boolean localIsLiveIn(Block block, int local) {
+            return block.blockID >= Integer.MAX_VALUE ? true : localsLiveIn[block.blockID].get(local);
+        }
+
+        @Override
+        public boolean localIsLiveOut(Block block, int local) {
+            return block.blockID >= Integer.MAX_VALUE ? true : localsLiveOut[block.blockID].get(local);
         }
     }
 }
diff -r 47b775458982 -r f659d019d3ab graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java	Fri Mar 14 09:58:31 2014 +0100
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java	Fri Mar 14 15:29:17 2014 +0100
@@ -32,6 +32,8 @@
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.Node.Verbosity;
+import com.oracle.graal.java.BciBlockMapping.Block;
+import com.oracle.graal.java.BciBlockMapping.LocalLiveness;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.java.*;
@@ -315,13 +317,21 @@
         }
     }
 
-    public void clearNonLiveLocals(BitSet liveness) {
+    public void clearNonLiveLocals(Block block, LocalLiveness liveness, boolean liveIn) {
         if (liveness == null) {
             return;
         }
-        for (int i = 0; i < locals.length; i++) {
-            if (!liveness.get(i)) {
-                locals[i] = null;
+        if (liveIn) {
+            for (int i = 0; i < locals.length; i++) {
+                if (!liveness.localIsLiveIn(block, i)) {
+                    locals[i] = null;
+                }
+            }
+        } else {
+            for (int i = 0; i < locals.length; i++) {
+                if (!liveness.localIsLiveOut(block, i)) {
+                    locals[i] = null;
+                }
             }
         }
     }
diff -r 47b775458982 -r f659d019d3ab graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Fri Mar 14 09:58:31 2014 +0100
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Fri Mar 14 15:29:17 2014 +0100
@@ -42,6 +42,7 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.java.BciBlockMapping.Block;
 import com.oracle.graal.java.BciBlockMapping.ExceptionDispatchBlock;
+import com.oracle.graal.java.BciBlockMapping.LocalLiveness;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.calc.FloatConvertNode.FloatConvert;
@@ -159,6 +160,7 @@
         }
 
         private Block[] loopHeaders;
+        private LocalLiveness liveness;
 
         /**
          * Gets the current frame state being processed by this builder.
@@ -225,6 +227,7 @@
             // compute the block map, setup exception handlers and get the entrypoint(s)
             BciBlockMapping blockMap = BciBlockMapping.create(method);
             loopHeaders = blockMap.loopHeaders;
+            liveness = blockMap.liveness;
 
             lastInstr = currentGraph.start();
             if (isSynchronized(method.getModifiers())) {
@@ -233,7 +236,7 @@
                 methodSynchronizedObject = synchronizedObject(frameState, method);
                 lastInstr = genMonitorEnter(methodSynchronizedObject);
             }
-            frameState.clearNonLiveLocals(blockMap.startBlock.localsLiveIn);
+            frameState.clearNonLiveLocals(blockMap.startBlock, liveness, true);
             ((StateSplit) lastInstr).setStateAfter(frameState.create(0));
 
             if (graphBuilderConfig.eagerInfopointMode()) {
@@ -1228,7 +1231,7 @@
                 createInvoke(callTarget, resultType);
             } else {
                 assert bci() == currentBlock.endBci;
-                frameState.clearNonLiveLocals(currentBlock.localsLiveOut);
+                frameState.clearNonLiveLocals(currentBlock, liveness, false);
 
                 InvokeWithExceptionNode invoke = createInvokeWithException(callTarget, resultType);
 
@@ -1544,7 +1547,7 @@
                 Target target = checkLoopExit(block.firstInstruction, block, state);
                 FixedNode result = target.fixed;
                 block.entryState = target.state == state ? state.copy() : target.state;
-                block.entryState.clearNonLiveLocals(block.localsLiveIn);
+                block.entryState.clearNonLiveLocals(block, liveness, true);
 
                 Debug.log("createTarget %s: first visit, result: %s", block, block.firstInstruction);
                 return result;
@@ -1823,7 +1826,7 @@
                 bci = stream.currentBCI();
 
                 if (bci > block.endBci) {
-                    frameState.clearNonLiveLocals(currentBlock.localsLiveOut);
+                    frameState.clearNonLiveLocals(currentBlock, liveness, false);
                 }
                 if (lastInstr instanceof StateSplit) {
                     if (lastInstr.getClass() == AbstractBeginNode.class) {
diff -r 47b775458982 -r f659d019d3ab graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Fri Mar 14 09:58:31 2014 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Fri Mar 14 15:29:17 2014 +0100
@@ -222,7 +222,8 @@
                 }
             } else if (b instanceof InstanceOfNode) {
                 InstanceOfNode instanceOfB = (InstanceOfNode) b;
-                if (instanceOfA.object() == instanceOfB.object() && !instanceOfA.type().isAssignableFrom(instanceOfB.type()) && !instanceOfB.type().isAssignableFrom(instanceOfA.type())) {
+                if (instanceOfA.object() == instanceOfB.object() && !instanceOfA.type().isInterface() && !instanceOfB.type().isInterface() &&
+                                !instanceOfA.type().isAssignableFrom(instanceOfB.type()) && !instanceOfB.type().isAssignableFrom(instanceOfA.type())) {
                     // Two instanceof on the same value with mutually exclusive types.
                     JavaTypeProfile profileA = instanceOfA.profile();
                     JavaTypeProfile profileB = instanceOfB.profile();
diff -r 47b775458982 -r f659d019d3ab graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/FrameStateAssignmentPhase.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/FrameStateAssignmentPhase.java	Fri Mar 14 09:58:31 2014 +0100
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/FrameStateAssignmentPhase.java	Fri Mar 14 15:29:17 2014 +0100
@@ -59,8 +59,9 @@
 
             if (node instanceof StateSplit) {
                 StateSplit stateSplit = (StateSplit) node;
-                if (stateSplit.stateAfter() != null) {
-                    FrameState newState = stateSplit.stateAfter();
+                FrameState stateAfter = stateSplit.stateAfter();
+                if (stateAfter != null) {
+                    FrameState newState = stateAfter;
                     stateSplit.setStateAfter(null);
                     return newState;
                 }
diff -r 47b775458982 -r f659d019d3ab graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Fri Mar 14 09:58:31 2014 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Fri Mar 14 15:29:17 2014 +0100
@@ -292,7 +292,7 @@
     }
 
     private void printSchedule(String desc) {
-        if (Debug.isEnabled()) {
+        if (Debug.isLogEnabled()) {
             Debug.printf("=== %s / %s / %s (%s) ===\n", getCFG().getStartBlock().getBeginNode().graph(), selectedStrategy, memsched, desc);
             for (Block b : getCFG().getBlocks()) {
                 Debug.printf("==== b: %s (loopDepth: %s). ", b, b.getLoopDepth());
@@ -388,8 +388,7 @@
     private void assignBlockToNode(ScheduledNode node, SchedulingStrategy strategy) {
         assert !node.isDeleted();
 
-        Block prevBlock = cfg.getNodeToBlock().get(node);
-        if (prevBlock != null) {
+        if (cfg.getNodeToBlock().containsKey(node)) {
             return;
         }
         // PhiNodes, ProxyNodes and FixedNodes should already have been placed in blocks by
@@ -418,6 +417,7 @@
                     block = latestBlock(node, strategy);
                 }
                 if (block == null) {
+                    // handle nodes without usages
                     block = earliestBlock;
                 } else if (strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS && !(node instanceof VirtualObjectNode)) {
                     // schedule at the latest position possible in the outermost loop possible
@@ -752,10 +752,14 @@
                     if (!(usage instanceof FrameState)) {
                         throw new SchedulingError(usage.toString());
                     }
-                    // If a FrameState belongs to a BeginNode then it's inputs will be placed at the
-                    // common dominator of all EndNodes.
-                    for (Node pred : unscheduledUsage.cfgPredecessors()) {
-                        closure.apply(cfg.getNodeToBlock().get(pred));
+                    if (unscheduledUsage instanceof StartNode) {
+                        closure.apply(cfg.getNodeToBlock().get(unscheduledUsage));
+                    } else {
+                        // If a FrameState belongs to a BeginNode then it's inputs will be placed at
+                        // the common dominator of all EndNodes.
+                        for (Node pred : unscheduledUsage.cfgPredecessors()) {
+                            closure.apply(cfg.getNodeToBlock().get(pred));
+                        }
                     }
                 } else {
                     // For the time being, FrameStates can only be connected to NodeWithState.
diff -r 47b775458982 -r f659d019d3ab graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java	Fri Mar 14 09:58:31 2014 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java	Fri Mar 14 15:29:17 2014 +0100
@@ -26,7 +26,12 @@
 
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.VirtualState.NodeClosure;
+import com.oracle.graal.nodes.cfg.*;
 import com.oracle.graal.phases.graph.*;
+import com.oracle.graal.phases.graph.ReentrantBlockIterator.*;
+import com.oracle.graal.phases.schedule.*;
+import com.oracle.graal.phases.schedule.SchedulePhase.*;
 
 public final class GraphOrder {
 
@@ -34,9 +39,9 @@
     }
 
     /**
-     * Asserts that there are no (invalid) cycles in the given graph. First, an ordered list of all
-     * nodes in the graph (a total ordering) is created. A second run over this list checks whether
-     * inputs are scheduled before their usages.
+     * Quick (and imprecise) assertion that there are no (invalid) cycles in the given graph. First,
+     * an ordered list of all nodes in the graph (a total ordering) is created. A second run over
+     * this list checks whether inputs are scheduled before their usages.
      * 
      * @param graph the graph to be checked.
      * @throws AssertionError if a cycle was detected.
@@ -62,7 +67,6 @@
             }
             visited.mark(node);
         }
-
         return true;
     }
 
@@ -80,34 +84,161 @@
     }
 
     private static void visitForward(ArrayList<Node> nodes, NodeBitMap visited, Node node, boolean floatingOnly) {
-        if (node != null && !visited.isMarked(node)) {
-            assert !floatingOnly || !(node instanceof FixedNode) : "unexpected reference to fixed node: " + node + " (this indicates an unexpected cycle)";
-            visited.mark(node);
-            FrameState stateAfter = null;
-            if (node instanceof StateSplit) {
-                stateAfter = ((StateSplit) node).stateAfter();
-            }
-            for (Node input : node.inputs()) {
-                if (input != stateAfter) {
-                    visitForward(nodes, visited, input, true);
+        try {
+            assert node.isAlive() : node + " not alive";
+            if (node != null && !visited.isMarked(node)) {
+                if (floatingOnly && node instanceof FixedNode) {
+                    throw new GraalInternalError("unexpected reference to fixed node: %s (this indicates an unexpected cycle)", node);
+                }
+                visited.mark(node);
+                FrameState stateAfter = null;
+                if (node instanceof StateSplit) {
+                    stateAfter = ((StateSplit) node).stateAfter();
+                }
+                for (Node input : node.inputs()) {
+                    if (input != stateAfter) {
+                        visitForward(nodes, visited, input, true);
+                    }
+                }
+                if (node instanceof EndNode) {
+                    EndNode end = (EndNode) node;
+                    for (PhiNode phi : end.merge().phis()) {
+                        visitForward(nodes, visited, phi.valueAt(end), true);
+                    }
+                }
+                nodes.add(node);
+                if (node instanceof MergeNode) {
+                    for (PhiNode phi : ((MergeNode) node).phis()) {
+                        visited.mark(phi);
+                        nodes.add(phi);
+                    }
+                }
+                if (stateAfter != null) {
+                    visitForward(nodes, visited, stateAfter, true);
                 }
             }
-            if (node instanceof EndNode) {
-                EndNode end = (EndNode) node;
-                for (PhiNode phi : end.merge().phis()) {
-                    visitForward(nodes, visited, phi.valueAt(end), true);
-                }
-            }
-            nodes.add(node);
-            if (node instanceof MergeNode) {
-                for (PhiNode phi : ((MergeNode) node).phis()) {
-                    visited.mark(phi);
-                    nodes.add(phi);
-                }
-            }
-            if (stateAfter != null) {
-                visitForward(nodes, visited, stateAfter, true);
-            }
+        } catch (GraalInternalError e) {
+            e.addContext(node);
+            throw e;
         }
     }
+
+    /**
+     * This method schedules the graph and makes sure that, for every node, all inputs are available
+     * at the position where it is scheduled. This is a very expensive assertion.
+     * 
+     * Also, this phase assumes ProxyNodes to exist at LoopExitNodes, so that it cannot be run after
+     * phases that remove loop proxies or move proxies to BeginNodes.
+     */
+    public static boolean assertSchedulableGraph(final StructuredGraph graph) {
+        try {
+            final SchedulePhase schedule = new SchedulePhase(SchedulingStrategy.LATEST_OUT_OF_LOOPS, MemoryScheduling.NONE);
+            final IdentityHashMap<LoopBeginNode, NodeBitMap> loopEntryStates = new IdentityHashMap<>();
+            schedule.apply(graph, false);
+
+            BlockIteratorClosure<NodeBitMap> closure = new BlockIteratorClosure<NodeBitMap>() {
+
+                @Override
+                protected List<NodeBitMap> processLoop(Loop loop, NodeBitMap initialState) {
+                    return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates;
+                }
+
+                @Override
+                protected NodeBitMap processBlock(final Block block, final NodeBitMap currentState) {
+                    final List<ScheduledNode> list = schedule.getBlockToNodesMap().get(block);
+
+                    /*
+                     * A stateAfter is not valid directly after its associated state split, but
+                     * right before the next fixed node. Therefore a pending stateAfter is kept that
+                     * will be checked at the correct position.
+                     */
+                    FrameState pendingStateAfter = null;
+                    for (final ScheduledNode node : list) {
+                        FrameState stateAfter = node instanceof StateSplit ? ((StateSplit) node).stateAfter() : null;
+
+                        if (pendingStateAfter != null && node instanceof FixedNode) {
+                            pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() {
+                                public void apply(Node usage, Node nonVirtualNode) {
+                                    assert currentState.isMarked(nonVirtualNode) : nonVirtualNode + " not available at virtualstate " + usage + " before " + node + " in block " + block + " \n" + list;
+                                }
+                            });
+                            pendingStateAfter = null;
+                        }
+
+                        if (node instanceof MergeNode) {
+                            // phis aren't scheduled, so they need to be added explicitly
+                            currentState.markAll(((MergeNode) node).phis());
+                            if (node instanceof LoopBeginNode) {
+                                // remember the state at the loop entry, it's restored at exits
+                                loopEntryStates.put((LoopBeginNode) node, currentState.copy());
+                            }
+                        } else if (node instanceof ProxyNode) {
+                            for (Node input : node.inputs()) {
+                                if (input != ((ProxyNode) node).proxyPoint()) {
+                                    assert currentState.isMarked(input) : input + " not available at " + node + " in block " + block + "\n" + list;
+                                }
+                            }
+                        } else if (node instanceof LoopExitNode) {
+                            // the contents of the loop are only accessible via proxies at the exit
+                            currentState.clearAll();
+                            currentState.markAll(loopEntryStates.get(((LoopExitNode) node).loopBegin()));
+                            // Loop proxies aren't scheduled, so they need to be added explicitly
+                            currentState.markAll(((LoopExitNode) node).proxies());
+                        } else {
+                            for (Node input : node.inputs()) {
+                                if (input != stateAfter) {
+                                    assert currentState.isMarked(input) : input + " not available at " + node + " in block " + block + "\n" + list;
+                                }
+                            }
+                        }
+                        if (node instanceof AbstractEndNode) {
+                            MergeNode merge = ((AbstractEndNode) node).merge();
+                            for (PhiNode phi : merge.phis()) {
+                                assert currentState.isMarked(phi.valueAt((AbstractEndNode) node)) : phi.valueAt((AbstractEndNode) node) + " not available at phi " + phi + " / end " + node +
+                                                " in block " + block;
+                            }
+                        }
+                        if (stateAfter != null) {
+                            assert pendingStateAfter == null;
+                            pendingStateAfter = stateAfter;
+                        }
+                        currentState.mark(node);
+                    }
+                    if (pendingStateAfter != null) {
+                        pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() {
+                            public void apply(Node usage, Node nonVirtualNode) {
+                                assert currentState.isMarked(nonVirtualNode) : nonVirtualNode + " not available at virtualstate " + usage + " at end of block " + block + " \n" + list;
+                            }
+                        });
+                    }
+                    return currentState;
+                }
+
+                @Override
+                protected NodeBitMap merge(Block merge, List<NodeBitMap> states) {
+                    NodeBitMap result = states.get(0);
+                    for (int i = 1; i < states.size(); i++) {
+                        result.intersect(states.get(i));
+                    }
+                    return result;
+                }
+
+                @Override
+                protected NodeBitMap getInitialState() {
+                    return graph.createNodeBitMap();
+                }
+
+                @Override
+                protected NodeBitMap cloneState(NodeBitMap oldState) {
+                    return oldState.copy();
+                }
+            };
+
+            ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock());
+
+        } catch (Throwable t) {
+            throw new AssertionError("unschedulable graph", t);
+        }
+        return true;
+    }
 }