# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1424278342 -3600
# Node ID 7837f7aab5ed3baf4874dd84618bb9a2be337a66
# Parent  076cb9f9bdbcd394dd5f5e41c90d019467e52828
Split bci block mapping and local liveness analysis. Clean up bci block mapping. Always sort loop blocks to be consecutive.

diff -r 076cb9f9bdbc -r 7837f7aab5ed graal/com.oracle.graal.java/src/com/oracle/graal/java/AbstractFrameStateBuilder.java
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/AbstractFrameStateBuilder.java	Wed Feb 18 15:10:57 2015 +0100
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/AbstractFrameStateBuilder.java	Wed Feb 18 17:52:22 2015 +0100
@@ -26,7 +26,6 @@
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.java.BciBlockMapping.BciBlock;
-import com.oracle.graal.java.BciBlockMapping.LocalLiveness;
 
 public abstract class AbstractFrameStateBuilder<T extends KindProvider, S extends AbstractFrameStateBuilder<T, S>> {
 
diff -r 076cb9f9bdbc -r 7837f7aab5ed 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	Wed Feb 18 15:10:57 2015 +0100
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java	Wed Feb 18 17:52:22 2015 +0100
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2009, 2015, 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
@@ -32,7 +32,6 @@
 import com.oracle.graal.bytecode.*;
 import com.oracle.graal.compiler.common.*;
 import com.oracle.graal.debug.*;
-import com.oracle.graal.debug.Debug.Scope;
 import com.oracle.graal.nodes.*;
 
 /**
@@ -424,20 +423,15 @@
     private BciBlock[] blocks;
     public final ResolvedJavaMethod method;
     public boolean hasJsrBytecodes;
-    public BciBlock startBlock;
 
-    private final BytecodeStream stream;
     private final ExceptionHandler[] exceptionHandlers;
-    private BciBlock[] blockMap;
+    private BciBlock startBlock;
     private BciBlock[] loopHeaders;
 
     private static final int LOOP_HEADER_MAX_CAPACITY = Long.SIZE;
     private static final int LOOP_HEADER_INITIAL_CAPACITY = 4;
 
-    private final boolean doLivenessAnalysis;
-    public LocalLiveness liveness;
     private int blocksNotYetAssignedId;
-    private final boolean consecutiveLoopBlocks;
     public int returnCount;
 
     /**
@@ -445,14 +439,9 @@
      *
      * @param method the compiler interface method containing the code
      */
-    private BciBlockMapping(ResolvedJavaMethod method, boolean doLivenessAnalysis, boolean consecutiveLoopBlocks) {
-        this.doLivenessAnalysis = doLivenessAnalysis;
-        this.consecutiveLoopBlocks = consecutiveLoopBlocks;
+    private BciBlockMapping(ResolvedJavaMethod method) {
         this.method = method;
         this.exceptionHandlers = method.getExceptionHandlers();
-        this.stream = new BytecodeStream(method.getCode());
-        int codeSize = method.getCodeSize();
-        this.blockMap = new BciBlock[codeSize];
     }
 
     public BciBlock[] getBlocks() {
@@ -466,37 +455,30 @@
     /**
      * Builds the block map and conservative CFG and numbers blocks.
      */
-    public void build() {
-        makeExceptionEntries();
-        iterateOverBytecodes();
+    public void build(BytecodeStream stream) {
+        int codeSize = method.getCodeSize();
+        BciBlock[] blockMap = new BciBlock[codeSize];
+        makeExceptionEntries(blockMap);
+        iterateOverBytecodes(blockMap, stream);
         if (hasJsrBytecodes) {
             if (!SupportJsrBytecodes.getValue()) {
                 throw new JsrNotSupportedBailout("jsr/ret parsing disabled");
             }
-            createJsrAlternatives(blockMap[0]);
+            createJsrAlternatives(blockMap, blockMap[0]);
         }
         if (Debug.isLogEnabled()) {
-            this.log("Before BlockOrder");
+            this.log(blockMap, "Before BlockOrder");
         }
-        computeBlockOrder();
-        fixLoopBits();
-
-        startBlock = blockMap[0];
+        computeBlockOrder(blockMap);
+        fixLoopBits(blockMap);
 
         assert verify();
 
         // Discard big arrays so that they can be GCed
+        startBlock = blockMap[0];
         blockMap = null;
         if (Debug.isLogEnabled()) {
-            this.log("Before LivenessAnalysis");
-        }
-        if (doLivenessAnalysis) {
-            try (Scope s = Debug.scope("LivenessAnalysis")) {
-                liveness = method.getMaxLocals() <= 64 ? new SmallLocalLiveness() : new LargeLocalLiveness();
-                liveness.computeLiveness();
-            } catch (Throwable e) {
-                throw Debug.handle(e);
-            }
+            this.log(blockMap, "Before LivenessAnalysis");
         }
     }
 
@@ -515,15 +497,15 @@
         return true;
     }
 
-    private void makeExceptionEntries() {
+    private void makeExceptionEntries(BciBlock[] blockMap) {
         // start basic blocks at all exception handler blocks and mark them as exception entries
         for (ExceptionHandler h : this.exceptionHandlers) {
-            BciBlock xhandler = makeBlock(h.getHandlerBCI());
+            BciBlock xhandler = makeBlock(blockMap, h.getHandlerBCI());
             xhandler.isExceptionEntry = true;
         }
     }
 
-    private void iterateOverBytecodes() {
+    private void iterateOverBytecodes(BciBlock[] blockMap, BytecodeStream stream) {
         // iterate over the bytecodes top to bottom.
         // mark the entrypoints of basic blocks and build lists of successors for
         // all bytecodes that end basic blocks (i.e. goto, ifs, switches, throw, jsr, returns, ret)
@@ -533,9 +515,9 @@
             int bci = stream.currentBCI();
 
             if (current == null || blockMap[bci] != null) {
-                BciBlock b = makeBlock(bci);
+                BciBlock b = makeBlock(blockMap, bci);
                 if (current != null) {
-                    addSuccessor(current.endBci, b);
+                    addSuccessor(blockMap, current.endBci, b);
                 }
                 current = b;
             }
@@ -555,9 +537,9 @@
                 }
                 case ATHROW: {
                     current = null;
-                    ExceptionDispatchBlock handler = handleExceptions(bci);
+                    ExceptionDispatchBlock handler = handleExceptions(blockMap, bci);
                     if (handler != null) {
-                        addSuccessor(bci, handler);
+                        addSuccessor(blockMap, bci, handler);
                     }
                     break;
                 }
@@ -578,24 +560,24 @@
                 case IFNULL:    // fall through
                 case IFNONNULL: {
                     current = null;
-                    addSuccessor(bci, makeBlock(stream.readBranchDest()));
-                    addSuccessor(bci, makeBlock(stream.nextBCI()));
+                    addSuccessor(blockMap, bci, makeBlock(blockMap, stream.readBranchDest()));
+                    addSuccessor(blockMap, bci, makeBlock(blockMap, stream.nextBCI()));
                     break;
                 }
                 case GOTO:
                 case GOTO_W: {
                     current = null;
-                    addSuccessor(bci, makeBlock(stream.readBranchDest()));
+                    addSuccessor(blockMap, bci, makeBlock(blockMap, stream.readBranchDest()));
                     break;
                 }
                 case TABLESWITCH: {
                     current = null;
-                    addSwitchSuccessors(bci, new BytecodeTableSwitch(stream, bci));
+                    addSwitchSuccessors(blockMap, bci, new BytecodeTableSwitch(stream, bci));
                     break;
                 }
                 case LOOKUPSWITCH: {
                     current = null;
-                    addSwitchSuccessors(bci, new BytecodeLookupSwitch(stream, bci));
+                    addSwitchSuccessors(blockMap, bci, new BytecodeLookupSwitch(stream, bci));
                     break;
                 }
                 case JSR:
@@ -605,11 +587,11 @@
                     if (target == 0) {
                         throw new JsrNotSupportedBailout("jsr target bci 0 not allowed");
                     }
-                    BciBlock b1 = makeBlock(target);
+                    BciBlock b1 = makeBlock(blockMap, target);
                     current.setJsrSuccessor(b1);
                     current.setJsrReturnBci(stream.nextBCI());
                     current = null;
-                    addSuccessor(bci, b1);
+                    addSuccessor(blockMap, bci, b1);
                     break;
                 }
                 case RET: {
@@ -622,11 +604,11 @@
                 case INVOKESTATIC:
                 case INVOKEVIRTUAL:
                 case INVOKEDYNAMIC: {
-                    ExceptionDispatchBlock handler = handleExceptions(bci);
+                    ExceptionDispatchBlock handler = handleExceptions(blockMap, bci);
                     if (handler != null) {
                         current = null;
-                        addSuccessor(bci, makeBlock(stream.nextBCI()));
-                        addSuccessor(bci, handler);
+                        addSuccessor(blockMap, bci, makeBlock(blockMap, stream.nextBCI()));
+                        addSuccessor(blockMap, bci, handler);
                     }
                     break;
                 }
@@ -648,11 +630,11 @@
                 case SALOAD:
                 case PUTFIELD:
                 case GETFIELD: {
-                    ExceptionDispatchBlock handler = handleExceptions(bci);
+                    ExceptionDispatchBlock handler = handleExceptions(blockMap, bci);
                     if (handler != null) {
                         current = null;
-                        addSuccessor(bci, makeBlock(stream.nextBCI()));
-                        addSuccessor(bci, handler);
+                        addSuccessor(blockMap, bci, makeBlock(blockMap, stream.nextBCI()));
+                        addSuccessor(blockMap, bci, handler);
                     }
                 }
             }
@@ -660,7 +642,7 @@
         }
     }
 
-    private BciBlock makeBlock(int startBci) {
+    private BciBlock makeBlock(BciBlock[] blockMap, int startBci) {
         BciBlock oldBlock = blockMap[startBci];
         if (oldBlock == null) {
             BciBlock newBlock = new BciBlock();
@@ -694,7 +676,7 @@
         }
     }
 
-    private void addSwitchSuccessors(int predBci, BytecodeSwitch bswitch) {
+    private void addSwitchSuccessors(BciBlock[] blockMap, int predBci, BytecodeSwitch bswitch) {
         // adds distinct targets to the successor list
         Collection<Integer> targets = new TreeSet<>();
         for (int i = 0; i < bswitch.numberOfCases(); i++) {
@@ -702,11 +684,11 @@
         }
         targets.add(bswitch.defaultTarget());
         for (int targetBci : targets) {
-            addSuccessor(predBci, makeBlock(targetBci));
+            addSuccessor(blockMap, predBci, makeBlock(blockMap, targetBci));
         }
     }
 
-    private void addSuccessor(int predBci, BciBlock sux) {
+    private static void addSuccessor(BciBlock[] blockMap, int predBci, BciBlock sux) {
         BciBlock predecessor = blockMap[predBci];
         if (sux.isExceptionEntry) {
             throw new BailoutException("Exception handler can be reached by both normal and exceptional control flow");
@@ -716,7 +698,7 @@
 
     private final ArrayList<BciBlock> jsrVisited = new ArrayList<>();
 
-    private void createJsrAlternatives(BciBlock block) {
+    private void createJsrAlternatives(BciBlock[] blockMap, BciBlock block) {
         jsrVisited.add(block);
         JsrScope scope = block.getJsrScope();
 
@@ -763,14 +745,14 @@
         }
         for (BciBlock successor : block.getSuccessors()) {
             if (!jsrVisited.contains(successor)) {
-                createJsrAlternatives(successor);
+                createJsrAlternatives(blockMap, successor);
             }
         }
     }
 
     private HashMap<ExceptionHandler, ExceptionDispatchBlock> initialExceptionDispatch = CollectionsFactory.newMap();
 
-    private ExceptionDispatchBlock handleExceptions(int bci) {
+    private ExceptionDispatchBlock handleExceptions(BciBlock[] blockMap, int bci) {
         ExceptionDispatchBlock lastHandler = null;
 
         for (int i = exceptionHandlers.length - 1; i >= 0; i--) {
@@ -805,14 +787,14 @@
 
     private boolean loopChanges;
 
-    private void fixLoopBits() {
+    private void fixLoopBits(BciBlock[] blockMap) {
         do {
             loopChanges = false;
             for (BciBlock b : blocks) {
                 b.visited = false;
             }
 
-            long loop = fixLoopBits(blockMap[0]);
+            long loop = fixLoopBits(blockMap, blockMap[0]);
 
             if (loop != 0) {
                 // There is a path from a loop end to the method entry that does not pass the loop
@@ -825,7 +807,7 @@
         } while (loopChanges);
     }
 
-    private void computeBlockOrder() {
+    private void computeBlockOrder(BciBlock[] blockMap) {
         int maxBlocks = blocksNotYetAssignedId;
         this.blocks = new BciBlock[blocksNotYetAssignedId];
         long loop = computeBlockOrder(blockMap[0]);
@@ -855,7 +837,7 @@
             if (b != null) {
                 b.setId(next);
                 newBlocks[next++] = b;
-                if (consecutiveLoopBlocks && b.isLoopHeader) {
+                if (b.isLoopHeader) {
                     next = handleLoopHeader(newBlocks, next, i, b);
                 }
             }
@@ -882,7 +864,7 @@
         return next;
     }
 
-    public void log(String name) {
+    public void log(BciBlock[] blockMap, String name) {
         if (Debug.isLogEnabled()) {
             String n = System.lineSeparator();
             StringBuilder sb = new StringBuilder(Debug.currentScope()).append("BlockMap ").append(name).append(" :");
@@ -1018,7 +1000,7 @@
         return loops;
     }
 
-    private long fixLoopBits(BciBlock block) {
+    private long fixLoopBits(BciBlock[] blockMap, BciBlock block) {
         if (block.visited) {
             // Return cached loop information for this block.
             if (block.isLoopHeader) {
@@ -1032,7 +1014,7 @@
         long loops = block.loops;
         for (BciBlock successor : block.getSuccessors()) {
             // Recursively process successors.
-            loops |= fixLoopBits(successor);
+            loops |= fixLoopBits(blockMap, successor);
         }
         if (block.loops != loops) {
             loopChanges = true;
@@ -1047,241 +1029,9 @@
         return loops;
     }
 
-    /**
-     * Encapsulates the liveness calculation, so that subclasses for locals &le; 64 and locals &gt;
-     * 64 can be implemented.
-     */
-    public abstract class LocalLiveness {
-
-        private void computeLiveness() {
-            for (BciBlock block : blocks) {
-                computeLocalLiveness(block);
-            }
-
-            boolean changed;
-            int iteration = 0;
-            do {
-                Debug.log("Iteration %d", iteration);
-                changed = false;
-                for (int i = blocks.length - 1; i >= 0; i--) {
-                    BciBlock block = blocks[i];
-                    int blockID = block.getId();
-                    // log statements in IFs because debugLiveX creates a new String
-                    if (Debug.isLogEnabled()) {
-                        Debug.logv("  start B%d  [%d, %d]  in: %s  out: %s  gen: %s  kill: %s", block.getId(), block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID),
-                                        debugLiveGen(blockID), debugLiveKill(blockID));
-                    }
-
-                    boolean blockChanged = (iteration == 0);
-                    if (block.getSuccessorCount() > 0) {
-                        int oldCardinality = liveOutCardinality(blockID);
-                        for (BciBlock sux : block.getSuccessors()) {
-                            if (Debug.isLogEnabled()) {
-                                Debug.log("    Successor B%d: %s", sux.getId(), debugLiveIn(sux.getId()));
-                            }
-                            propagateLiveness(blockID, sux.getId());
-                        }
-                        blockChanged |= (oldCardinality != liveOutCardinality(blockID));
-                    }
-
-                    if (blockChanged) {
-                        updateLiveness(blockID);
-                        if (Debug.isLogEnabled()) {
-                            Debug.logv("  end   B%d  [%d, %d]  in: %s  out: %s  gen: %s  kill: %s", block.getId(), block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID),
-                                            debugLiveGen(blockID), debugLiveKill(blockID));
-                        }
-                    }
-                    changed |= blockChanged;
-                }
-                iteration++;
-            } while (changed);
-        }
-
-        /**
-         * Returns whether the local is live at the beginning of the given block.
-         */
-        public abstract boolean localIsLiveIn(BciBlock block, int local);
-
-        /**
-         * Returns whether the local is set in the given loop.
-         */
-        public abstract boolean localIsChangedInLoop(int loopId, int local);
-
-        /**
-         * Returns whether the local is live at the end of the given block.
-         */
-        public abstract boolean localIsLiveOut(BciBlock 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);
-
-        private void computeLocalLiveness(BciBlock block) {
-            if (block.startBci < 0 || block.endBci < 0) {
-                return;
-            }
-            int blockID = block.getId();
-            int localIndex;
-            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 IINC:
-                        localIndex = stream.readLocalIndex();
-                        loadOne(blockID, localIndex);
-                        storeOne(blockID, localIndex);
-                        break;
-                    case ILOAD:
-                    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);
-        }
-    }
-
-    public static BciBlockMapping create(ResolvedJavaMethod method, boolean doLivenessAnalysis, boolean consecutiveLoopBlocks) {
-        BciBlockMapping map = new BciBlockMapping(method, doLivenessAnalysis, consecutiveLoopBlocks);
-        map.build();
+    public static BciBlockMapping create(BytecodeStream stream, ResolvedJavaMethod method) {
+        BciBlockMapping map = new BciBlockMapping(method);
+        map.build(stream);
         if (Debug.isDumpEnabled()) {
             Debug.dump(map, method.format("After block building %f %R %H.%n(%P)"));
         }
@@ -1289,228 +1039,15 @@
         return map;
     }
 
-    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;
-        private final long[] localsChangedInLoop;
-
-        public SmallLocalLiveness() {
-            int blockSize = blocks.length;
-            localsLiveIn = new long[blockSize];
-            localsLiveOut = new long[blockSize];
-            localsLiveGen = new long[blockSize];
-            localsLiveKill = new long[blockSize];
-            localsChangedInLoop = new long[BciBlockMapping.this.nextLoop];
-        }
-
-        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]);
-        }
-
-        @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;
-            }
-
-            BciBlock block = blocks[blockID];
-            long tmp = block.loops;
-            int pos = 0;
-            while (tmp != 0) {
-                if ((tmp & 1L) == 1L) {
-                    this.localsChangedInLoop[pos] |= bit;
-                }
-                tmp >>= 1;
-                ++pos;
-            }
-        }
-
-        @Override
-        public boolean localIsLiveIn(BciBlock block, int local) {
-            int blockID = block.getId();
-            return blockID >= Integer.MAX_VALUE ? false : (localsLiveIn[blockID] & (1L << local)) != 0L;
-        }
-
-        @Override
-        public boolean localIsLiveOut(BciBlock block, int local) {
-            int blockID = block.getId();
-            return blockID >= Integer.MAX_VALUE ? false : (localsLiveOut[blockID] & (1L << local)) != 0L;
-        }
-
-        @Override
-        public boolean localIsChangedInLoop(int loopId, int local) {
-            return (localsChangedInLoop[loopId] & (1L << local)) != 0L;
-        }
-    }
-
-    public final class LargeLocalLiveness extends LocalLiveness {
-        private BitSet[] localsLiveIn;
-        private BitSet[] localsLiveOut;
-        private BitSet[] localsLiveGen;
-        private BitSet[] localsLiveKill;
-        private BitSet[] localsChangedInLoop;
-
-        public LargeLocalLiveness() {
-            int blocksSize = blocks.length;
-            localsLiveIn = new BitSet[blocksSize];
-            localsLiveOut = new BitSet[blocksSize];
-            localsLiveGen = new BitSet[blocksSize];
-            localsLiveKill = new BitSet[blocksSize];
-            int maxLocals = method.getMaxLocals();
-            for (int i = 0; i < blocksSize; i++) {
-                localsLiveIn[i] = new BitSet(maxLocals);
-                localsLiveOut[i] = new BitSet(maxLocals);
-                localsLiveGen[i] = new BitSet(maxLocals);
-                localsLiveKill[i] = new BitSet(maxLocals);
-            }
-            localsChangedInLoop = new BitSet[nextLoop];
-            for (int i = 0; i < nextLoop; ++i) {
-                localsChangedInLoop[i] = new BitSet(maxLocals);
-            }
-        }
-
-        @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();
-        }
-
-        @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);
-            }
-
-            BciBlock block = blocks[blockID];
-            long tmp = block.loops;
-            int pos = 0;
-            while (tmp != 0) {
-                if ((tmp & 1L) == 1L) {
-                    this.localsChangedInLoop[pos].set(local);
-                }
-                tmp >>= 1;
-                ++pos;
-            }
-        }
-
-        @Override
-        public boolean localIsLiveIn(BciBlock block, int local) {
-            return block.getId() >= Integer.MAX_VALUE ? true : localsLiveIn[block.getId()].get(local);
-        }
-
-        @Override
-        public boolean localIsLiveOut(BciBlock block, int local) {
-            return block.getId() >= Integer.MAX_VALUE ? true : localsLiveOut[block.getId()].get(local);
-        }
-
-        @Override
-        public boolean localIsChangedInLoop(int loopId, int local) {
-            return localsChangedInLoop[loopId].get(local);
-        }
-    }
-
     public BciBlock[] getLoopHeaders() {
         return loopHeaders;
     }
+
+    public BciBlock getStartBlock() {
+        return startBlock;
+    }
+
+    public int getLoopCount() {
+        return nextLoop;
+    }
 }
diff -r 076cb9f9bdbc -r 7837f7aab5ed 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	Wed Feb 18 15:10:57 2015 +0100
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Wed Feb 18 17:52:22 2015 +0100
@@ -40,13 +40,13 @@
 import com.oracle.graal.compiler.common.calc.*;
 import com.oracle.graal.compiler.common.type.*;
 import com.oracle.graal.debug.*;
+import com.oracle.graal.debug.Debug.*;
 import com.oracle.graal.graph.Graph.Mark;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.graph.Node.ValueNumberable;
 import com.oracle.graal.graph.iterators.*;
 import com.oracle.graal.java.BciBlockMapping.BciBlock;
 import com.oracle.graal.java.BciBlockMapping.ExceptionDispatchBlock;
-import com.oracle.graal.java.BciBlockMapping.LocalLiveness;
 import com.oracle.graal.java.GraphBuilderPlugin.AnnotatedInvocationPlugin;
 import com.oracle.graal.java.GraphBuilderPlugin.InlineInvokePlugin;
 import com.oracle.graal.java.GraphBuilderPlugin.InvocationPlugin;
@@ -247,20 +247,30 @@
                 try (Indent indent = Debug.logAndIndent("build graph for %s", method)) {
 
                     // compute the block map, setup exception handlers and get the entrypoint(s)
-                    BciBlockMapping blockMap = BciBlockMapping.create(method, graphBuilderConfig.doLivenessAnalysis(), explodeLoops);
+                    BciBlockMapping blockMap = BciBlockMapping.create(stream, method);
                     loopHeaders = blockMap.getLoopHeaders();
-                    liveness = blockMap.liveness;
+
+                    if (graphBuilderConfig.doLivenessAnalysis()) {
+                        try (Scope s = Debug.scope("LivenessAnalysis")) {
+                            int maxLocals = method.getMaxLocals();
+                            liveness = LocalLiveness.compute(stream, blockMap.getBlocks(), maxLocals, blockMap.getLoopCount());
+                        } catch (Throwable e) {
+                            throw Debug.handle(e);
+                        }
+                    }
                     returnCount = blockMap.getReturnCount();
 
                     lastInstr = startInstruction;
                     this.setCurrentFrameState(startFrameState);
+                    stream.setBCI(0);
 
+                    BciBlock startBlock = blockMap.getStartBlock();
                     if (startInstruction == currentGraph.start()) {
                         StartNode startNode = currentGraph.start();
                         if (method.isSynchronized()) {
                             startNode.setStateAfter(frameState.create(BytecodeFrame.BEFORE_BCI));
                         } else {
-                            frameState.clearNonLiveLocals(blockMap.startBlock, liveness, true);
+                            frameState.clearNonLiveLocals(startBlock, liveness, true);
                             assert bci() == 0;
                             startNode.setStateAfter(frameState.create(bci()));
                         }
@@ -270,7 +280,7 @@
                         // add a monitor enter to the start block
                         methodSynchronizedObject = synchronizedObject(frameState, method);
                         MonitorEnterNode monitorEnter = genMonitorEnter(methodSynchronizedObject);
-                        frameState.clearNonLiveLocals(blockMap.startBlock, liveness, true);
+                        frameState.clearNonLiveLocals(startBlock, liveness, true);
                         assert bci() == 0;
                         monitorEnter.setStateAfter(frameState.create(bci()));
                     }
@@ -279,12 +289,12 @@
                         append(createInfoPointNode(InfopointReason.METHOD_START));
                     }
 
-                    currentBlock = blockMap.startBlock;
-                    blockMap.startBlock.setEntryState(0, frameState);
-                    if (blockMap.startBlock.isLoopHeader && !explodeLoops) {
-                        appendGoto(blockMap.startBlock);
+                    currentBlock = blockMap.getStartBlock();
+                    startBlock.setEntryState(0, frameState);
+                    if (startBlock.isLoopHeader && !explodeLoops) {
+                        appendGoto(startBlock);
                     } else {
-                        blockMap.startBlock.setFirstInstruction(0, lastInstr);
+                        startBlock.setFirstInstruction(0, lastInstr);
                     }
 
                     int index = 0;
diff -r 076cb9f9bdbc -r 7837f7aab5ed graal/com.oracle.graal.java/src/com/oracle/graal/java/HIRFrameStateBuilder.java
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/HIRFrameStateBuilder.java	Wed Feb 18 15:10:57 2015 +0100
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/HIRFrameStateBuilder.java	Wed Feb 18 17:52:22 2015 +0100
@@ -31,7 +31,6 @@
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.type.*;
 import com.oracle.graal.debug.*;
-import com.oracle.graal.java.BciBlockMapping.LocalLiveness;
 import com.oracle.graal.java.GraphBuilderPlugin.ParameterPlugin;
 import com.oracle.graal.nodeinfo.*;
 import com.oracle.graal.nodes.*;
diff -r 076cb9f9bdbc -r 7837f7aab5ed graal/com.oracle.graal.java/src/com/oracle/graal/java/LargeLocalLiveness.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/LargeLocalLiveness.java	Wed Feb 18 17:52:22 2015 +0100
@@ -0,0 +1,133 @@
+/*
+ * Copyright (c) 2009, 2015, 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.graal.java;
+
+import java.util.*;
+
+import com.oracle.graal.java.BciBlockMapping.*;
+
+public final class LargeLocalLiveness extends LocalLiveness {
+    private BitSet[] localsLiveIn;
+    private BitSet[] localsLiveOut;
+    private BitSet[] localsLiveGen;
+    private BitSet[] localsLiveKill;
+    private BitSet[] localsChangedInLoop;
+
+    public LargeLocalLiveness(BciBlock[] blocks, int maxLocals, int loopCount) {
+        super(blocks);
+        int blocksSize = blocks.length;
+        localsLiveIn = new BitSet[blocksSize];
+        localsLiveOut = new BitSet[blocksSize];
+        localsLiveGen = new BitSet[blocksSize];
+        localsLiveKill = new BitSet[blocksSize];
+        for (int i = 0; i < blocksSize; i++) {
+            localsLiveIn[i] = new BitSet(maxLocals);
+            localsLiveOut[i] = new BitSet(maxLocals);
+            localsLiveGen[i] = new BitSet(maxLocals);
+            localsLiveKill[i] = new BitSet(maxLocals);
+        }
+        localsChangedInLoop = new BitSet[loopCount];
+        for (int i = 0; i < loopCount; ++i) {
+            localsChangedInLoop[i] = new BitSet(maxLocals);
+        }
+    }
+
+    @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();
+    }
+
+    @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);
+        }
+
+        BciBlock block = blocks[blockID];
+        long tmp = block.loops;
+        int pos = 0;
+        while (tmp != 0) {
+            if ((tmp & 1L) == 1L) {
+                this.localsChangedInLoop[pos].set(local);
+            }
+            tmp >>= 1;
+            ++pos;
+        }
+    }
+
+    @Override
+    public boolean localIsLiveIn(BciBlock block, int local) {
+        return block.getId() >= Integer.MAX_VALUE ? true : localsLiveIn[block.getId()].get(local);
+    }
+
+    @Override
+    public boolean localIsLiveOut(BciBlock block, int local) {
+        return block.getId() >= Integer.MAX_VALUE ? true : localsLiveOut[block.getId()].get(local);
+    }
+
+    @Override
+    public boolean localIsChangedInLoop(int loopId, int local) {
+        return localsChangedInLoop[loopId].get(local);
+    }
+}
diff -r 076cb9f9bdbc -r 7837f7aab5ed graal/com.oracle.graal.java/src/com/oracle/graal/java/LocalLiveness.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/LocalLiveness.java	Wed Feb 18 17:52:22 2015 +0100
@@ -0,0 +1,272 @@
+/*
+ * Copyright (c) 2009, 2015, 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.graal.java;
+
+import static com.oracle.graal.bytecode.Bytecodes.*;
+
+import com.oracle.graal.bytecode.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.java.BciBlockMapping.*;
+
+/**
+ * Encapsulates the liveness calculation, so that subclasses for locals &le; 64 and locals &gt; 64
+ * can be implemented.
+ */
+public abstract class LocalLiveness {
+    protected final BciBlock[] blocks;
+
+    public static LocalLiveness compute(BytecodeStream stream, BciBlock[] blocks, int maxLocals, int loopCount) {
+        LocalLiveness liveness = maxLocals <= 64 ? new SmallLocalLiveness(blocks, maxLocals, loopCount) : new LargeLocalLiveness(blocks, maxLocals, loopCount);
+        liveness.computeLiveness(stream);
+        return liveness;
+    }
+
+    protected LocalLiveness(BciBlock[] blocks) {
+        this.blocks = blocks;
+    }
+
+    void computeLiveness(BytecodeStream stream) {
+        for (BciBlock block : blocks) {
+            computeLocalLiveness(stream, block);
+        }
+
+        boolean changed;
+        int iteration = 0;
+        do {
+            Debug.log("Iteration %d", iteration);
+            changed = false;
+            for (int i = blocks.length - 1; i >= 0; i--) {
+                BciBlock block = blocks[i];
+                int blockID = block.getId();
+                // log statements in IFs because debugLiveX creates a new String
+                if (Debug.isLogEnabled()) {
+                    Debug.logv("  start B%d  [%d, %d]  in: %s  out: %s  gen: %s  kill: %s", block.getId(), block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID),
+                                    debugLiveGen(blockID), debugLiveKill(blockID));
+                }
+
+                boolean blockChanged = (iteration == 0);
+                if (block.getSuccessorCount() > 0) {
+                    int oldCardinality = liveOutCardinality(blockID);
+                    for (BciBlock sux : block.getSuccessors()) {
+                        if (Debug.isLogEnabled()) {
+                            Debug.log("    Successor B%d: %s", sux.getId(), debugLiveIn(sux.getId()));
+                        }
+                        propagateLiveness(blockID, sux.getId());
+                    }
+                    blockChanged |= (oldCardinality != liveOutCardinality(blockID));
+                }
+
+                if (blockChanged) {
+                    updateLiveness(blockID);
+                    if (Debug.isLogEnabled()) {
+                        Debug.logv("  end   B%d  [%d, %d]  in: %s  out: %s  gen: %s  kill: %s", block.getId(), block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID),
+                                        debugLiveGen(blockID), debugLiveKill(blockID));
+                    }
+                }
+                changed |= blockChanged;
+            }
+            iteration++;
+        } while (changed);
+    }
+
+    /**
+     * Returns whether the local is live at the beginning of the given block.
+     */
+    public abstract boolean localIsLiveIn(BciBlock block, int local);
+
+    /**
+     * Returns whether the local is set in the given loop.
+     */
+    public abstract boolean localIsChangedInLoop(int loopId, int local);
+
+    /**
+     * Returns whether the local is live at the end of the given block.
+     */
+    public abstract boolean localIsLiveOut(BciBlock 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);
+
+    private void computeLocalLiveness(BytecodeStream stream, BciBlock block) {
+        if (block.startBci < 0 || block.endBci < 0) {
+            return;
+        }
+        int blockID = block.getId();
+        int localIndex;
+        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 IINC:
+                    localIndex = stream.readLocalIndex();
+                    loadOne(blockID, localIndex);
+                    storeOne(blockID, localIndex);
+                    break;
+                case ILOAD:
+                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);
+    }
+}
diff -r 076cb9f9bdbc -r 7837f7aab5ed graal/com.oracle.graal.java/src/com/oracle/graal/java/SmallLocalLiveness.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/SmallLocalLiveness.java	Wed Feb 18 17:52:22 2015 +0100
@@ -0,0 +1,143 @@
+/*
+ * Copyright (c) 2009, 2015, 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.graal.java;
+
+import com.oracle.graal.java.BciBlockMapping.*;
+
+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;
+    private final long[] localsChangedInLoop;
+    private final int maxLocals;
+
+    public SmallLocalLiveness(BciBlock[] blocks, int maxLocals, int loopCount) {
+        super(blocks);
+        this.maxLocals = maxLocals;
+        int blockSize = blocks.length;
+        localsLiveIn = new long[blockSize];
+        localsLiveOut = new long[blockSize];
+        localsLiveGen = new long[blockSize];
+        localsLiveKill = new long[blockSize];
+        localsChangedInLoop = new long[loopCount];
+    }
+
+    private String debugString(long value) {
+        StringBuilder str = new StringBuilder("{");
+        long current = value;
+        for (int i = 0; i < maxLocals; 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]);
+    }
+
+    @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;
+        }
+
+        BciBlock block = blocks[blockID];
+        long tmp = block.loops;
+        int pos = 0;
+        while (tmp != 0) {
+            if ((tmp & 1L) == 1L) {
+                this.localsChangedInLoop[pos] |= bit;
+            }
+            tmp >>= 1;
+            ++pos;
+        }
+    }
+
+    @Override
+    public boolean localIsLiveIn(BciBlock block, int local) {
+        int blockID = block.getId();
+        return blockID >= Integer.MAX_VALUE ? false : (localsLiveIn[blockID] & (1L << local)) != 0L;
+    }
+
+    @Override
+    public boolean localIsLiveOut(BciBlock block, int local) {
+        int blockID = block.getId();
+        return blockID >= Integer.MAX_VALUE ? false : (localsLiveOut[blockID] & (1L << local)) != 0L;
+    }
+
+    @Override
+    public boolean localIsChangedInLoop(int loopId, int local) {
+        return (localsChangedInLoop[loopId] & (1L << local)) != 0L;
+    }
+}