# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1422958224 -3600
# Node ID 5e33637f5e5abda5bf23a766137250a306bd0d31
# Parent  336adcd0070b9cfba433c244a33fc1f569babb9b# Parent  684612ee6abbaf52e57fbcbf088c3add7df78446
Merge StackSlotAllocation cleanups.

diff -r 336adcd0070b -r 5e33637f5e5a graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Tue Feb 03 04:17:06 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Tue Feb 03 11:10:24 2015 +0100
@@ -356,7 +356,7 @@
             try (Scope s1 = Debug.scope("BuildFrameMap")) {
                 // build frame map
                 final StackSlotAllocator allocator;
-                if (LSStackSlotAllocator.Options.EnableLSStackSlotAllocation.getValue()) {
+                if (LSStackSlotAllocator.Options.LSStackSlotAllocation.getValue()) {
                     allocator = new LSStackSlotAllocator();
                 } else {
                     allocator = new SimpleStackSlotAllocator();
diff -r 336adcd0070b -r 5e33637f5e5a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/FixPointIntervalBuilder.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/FixPointIntervalBuilder.java	Tue Feb 03 11:10:24 2015 +0100
@@ -0,0 +1,266 @@
+/*
+ * Copyright (c) 2015, 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.lir.stackslotalloc;
+
+import static com.oracle.graal.api.code.ValueUtil.*;
+
+import java.util.*;
+
+import com.oracle.graal.api.code.*;
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.LIRInstruction.OperandFlag;
+import com.oracle.graal.lir.LIRInstruction.OperandMode;
+
+/**
+ * Calculates the stack intervals using a worklist-based backwards data-flow analysis.
+ */
+final class FixPointIntervalBuilder {
+    private final BlockMap<BitSet> liveInMap;
+    private final BlockMap<BitSet> liveOutMap;
+    private final LIR lir;
+    private final int maxOpId;
+    private final StackInterval[] stackSlotMap;
+
+    /**
+     * The number of allocated stack slots.
+     */
+    private static final DebugMetric uninitializedSlots = Debug.metric("StackSlotAllocator[uninitializedSlots]");
+
+    FixPointIntervalBuilder(LIR lir, StackInterval[] stackSlotMap, int maxOpId) {
+        this.lir = lir;
+        this.stackSlotMap = stackSlotMap;
+        this.maxOpId = maxOpId;
+        liveInMap = new BlockMap<>(lir.getControlFlowGraph());
+        liveOutMap = new BlockMap<>(lir.getControlFlowGraph());
+    }
+
+    void build() {
+        Deque<AbstractBlock<?>> worklist = new ArrayDeque<>();
+        for (int i = lir.getControlFlowGraph().getBlocks().size() - 1; i >= 0; i--) {
+            worklist.add(lir.getControlFlowGraph().getBlocks().get(i));
+        }
+        for (AbstractBlock<?> block : lir.getControlFlowGraph().getBlocks()) {
+            liveInMap.put(block, new BitSet(stackSlotMap.length));
+        }
+        while (!worklist.isEmpty()) {
+            AbstractBlock<?> block = worklist.poll();
+            processBlock(block, worklist);
+        }
+    }
+
+    /**
+     * Merge outSet with in-set of successors.
+     */
+    private boolean updateOutBlock(AbstractBlock<?> block) {
+        BitSet union = new BitSet(stackSlotMap.length);
+        block.getSuccessors().forEach(succ -> union.or(liveInMap.get(succ)));
+        BitSet outSet = liveOutMap.get(block);
+        // check if changed
+        if (outSet == null || !union.equals(outSet)) {
+            liveOutMap.put(block, union);
+            return true;
+        }
+        return false;
+    }
+
+    private void processBlock(AbstractBlock<?> block, Deque<AbstractBlock<?>> worklist) {
+        if (updateOutBlock(block)) {
+            try (Indent indent = Debug.logAndIndent("handle block %s", block)) {
+                List<LIRInstruction> instructions = lir.getLIRforBlock(block);
+                // get out set and mark intervals
+                BitSet outSet = liveOutMap.get(block);
+                markOutInterval(outSet, getBlockEnd(instructions));
+                printLiveSet("liveOut", outSet);
+
+                // process instructions
+                BlockClosure closure = new BlockClosure((BitSet) outSet.clone());
+                for (int i = instructions.size() - 1; i >= 0; i--) {
+                    LIRInstruction inst = instructions.get(i);
+                    closure.processInstructionBottomUp(inst);
+                }
+
+                // add predecessors to work list
+                worklist.addAll(block.getPredecessors());
+                // set in set and mark intervals
+                BitSet inSet = closure.getCurrentSet();
+                liveInMap.put(block, inSet);
+                markInInterval(inSet, getBlockBegin(instructions));
+                printLiveSet("liveIn", inSet);
+            }
+        }
+    }
+
+    private void printLiveSet(String label, BitSet liveSet) {
+        if (Debug.isLogEnabled()) {
+            try (Indent indent = Debug.logAndIndent(label)) {
+                Debug.log("%s", liveSetToString(liveSet));
+            }
+        }
+    }
+
+    private String liveSetToString(BitSet liveSet) {
+        StringBuilder sb = new StringBuilder();
+        for (int i = liveSet.nextSetBit(0); i >= 0; i = liveSet.nextSetBit(i + 1)) {
+            StackInterval interval = getIntervalFromStackId(i);
+            sb.append(interval.getOperand()).append(" ");
+        }
+        return sb.toString();
+    }
+
+    private void markOutInterval(BitSet outSet, int blockEndOpId) {
+        for (int i = outSet.nextSetBit(0); i >= 0; i = outSet.nextSetBit(i + 1)) {
+            StackInterval interval = getIntervalFromStackId(i);
+            Debug.log("mark live operand: %s", interval.getOperand());
+            interval.addTo(blockEndOpId);
+        }
+    }
+
+    private void markInInterval(BitSet inSet, int blockFirstOpId) {
+        for (int i = inSet.nextSetBit(0); i >= 0; i = inSet.nextSetBit(i + 1)) {
+            StackInterval interval = getIntervalFromStackId(i);
+            Debug.log("mark live operand: %s", interval.getOperand());
+            interval.addFrom(blockFirstOpId);
+        }
+    }
+
+    private final class BlockClosure {
+        private final BitSet currentSet;
+
+        private BlockClosure(BitSet set) {
+            currentSet = set;
+        }
+
+        private BitSet getCurrentSet() {
+            return currentSet;
+        }
+
+        /**
+         * Process all values of an instruction bottom-up, i.e. definitions before usages. Values
+         * that start or end at the current operation are not included.
+         */
+        private void processInstructionBottomUp(LIRInstruction op) {
+            try (Indent indent = Debug.logAndIndent("handle op %d, %s", op.id(), op)) {
+                // kills
+                op.visitEachTemp(this::defConsumer);
+                op.visitEachOutput(this::defConsumer);
+
+                // gen - values that are considered alive for this state
+                op.visitEachAlive(this::useConsumer);
+                op.visitEachState(this::useConsumer);
+                // mark locations
+                // gen
+                op.visitEachInput(this::useConsumer);
+            }
+        }
+
+        /**
+         * @see InstructionValueConsumer
+         *
+         * @param inst
+         * @param operand
+         * @param mode
+         * @param flags
+         */
+        private void useConsumer(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
+            if (isVirtualStackSlot(operand)) {
+                VirtualStackSlot vslot = asVirtualStackSlot(operand);
+                addUse(vslot, inst, flags);
+                Debug.log("set operand: %s", operand);
+                currentSet.set(vslot.getId());
+            }
+        }
+
+        /**
+         *
+         * @see InstructionValueConsumer
+         *
+         * @param inst
+         * @param operand
+         * @param mode
+         * @param flags
+         */
+        private void defConsumer(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
+            if (isVirtualStackSlot(operand)) {
+                VirtualStackSlot vslot = asVirtualStackSlot(operand);
+                addDef(vslot, inst);
+                Debug.log("clear operand: %s", operand);
+                currentSet.clear(vslot.getId());
+            }
+
+        }
+
+        private void addUse(VirtualStackSlot stackSlot, LIRInstruction inst, EnumSet<OperandFlag> flags) {
+            StackInterval interval = getOrCreateInterval(stackSlot);
+            if (flags.contains(OperandFlag.UNINITIALIZED)) {
+                // Stack slot is marked uninitialized so we have to assume it is live all
+                // the time.
+                if (Debug.isMeterEnabled() && !(interval.from() == 0 && interval.to() == maxOpId)) {
+                    uninitializedSlots.increment();
+                }
+                interval.addFrom(0);
+                interval.addTo(maxOpId);
+            } else {
+                interval.addTo(inst.id());
+            }
+        }
+
+        private void addDef(VirtualStackSlot stackSlot, LIRInstruction inst) {
+            StackInterval interval = getOrCreateInterval(stackSlot);
+            interval.addFrom(inst.id());
+        }
+
+    }
+
+    private StackInterval get(VirtualStackSlot stackSlot) {
+        return stackSlotMap[stackSlot.getId()];
+    }
+
+    private void put(VirtualStackSlot stackSlot, StackInterval interval) {
+        stackSlotMap[stackSlot.getId()] = interval;
+    }
+
+    private StackInterval getOrCreateInterval(VirtualStackSlot stackSlot) {
+        StackInterval interval = get(stackSlot);
+        if (interval == null) {
+            interval = new StackInterval(stackSlot, stackSlot.getLIRKind());
+            put(stackSlot, interval);
+        }
+        return interval;
+    }
+
+    private StackInterval getIntervalFromStackId(int id) {
+        return stackSlotMap[id];
+    }
+
+    private static int getBlockBegin(List<LIRInstruction> instructions) {
+        return instructions.get(0).id();
+    }
+
+    private static int getBlockEnd(List<LIRInstruction> instructions) {
+        return instructions.get(instructions.size() - 1).id() + 1;
+    }
+
+}
diff -r 336adcd0070b -r 5e33637f5e5a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/InstructionNumberer.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/InstructionNumberer.java	Tue Feb 03 04:17:06 2015 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,104 +0,0 @@
-/*
- * Copyright (c) 2014, 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.lir.stackslotalloc;
-
-import static com.oracle.graal.api.code.CodeUtil.*;
-
-import java.util.*;
-
-import com.oracle.graal.compiler.common.cfg.*;
-import com.oracle.graal.lir.*;
-
-public class InstructionNumberer {
-
-    private LIRInstruction[] opIdToInstructionMap;
-    private AbstractBlock<?>[] opIdToBlockMap;
-
-    /**
-     * Converts an {@linkplain LIRInstruction#id instruction id} to an instruction index. All LIR
-     * instructions in a method have an index one greater than their linear-scan order predecesor
-     * with the first instruction having an index of 0.
-     */
-    private static int opIdToIndex(int opId) {
-        return opId >> 1;
-    }
-
-    /**
-     * Retrieves the {@link LIRInstruction} based on its {@linkplain LIRInstruction#id id}.
-     *
-     * @param opId an instruction {@linkplain LIRInstruction#id id}
-     * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id}
-     */
-    protected LIRInstruction instructionForId(int opId) {
-        assert isEven(opId) : "opId not even";
-        LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)];
-        assert instr.id() == opId;
-        return instr;
-    }
-
-    /**
-     * Numbers all instructions in all blocks.
-     */
-    protected void numberInstructions(LIR lir, List<? extends AbstractBlock<?>> sortedBlocks) {
-
-        // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node.
-        int numInstructions = 0;
-        for (AbstractBlock<?> block : sortedBlocks) {
-            numInstructions += lir.getLIRforBlock(block).size();
-        }
-
-        // initialize with correct length
-        opIdToInstructionMap = new LIRInstruction[numInstructions];
-        opIdToBlockMap = new AbstractBlock<?>[numInstructions];
-
-        int opId = 0;
-        int index = 0;
-        for (AbstractBlock<?> block : sortedBlocks) {
-
-            List<LIRInstruction> instructions = lir.getLIRforBlock(block);
-
-            int numInst = instructions.size();
-            for (int j = 0; j < numInst; j++) {
-                LIRInstruction op = instructions.get(j);
-                op.setId(opId);
-
-                opIdToInstructionMap[index] = op;
-                opIdToBlockMap[index] = block;
-                assert instructionForId(opId) == op : "must match";
-
-                index++;
-                opId += 2; // numbering of lirOps by two
-            }
-        }
-        assert index == numInstructions : "must match";
-        assert (index << 1) == opId : "must match: " + (index << 1);
-    }
-
-    /**
-     * Gets the highest instruction id allocated by this object.
-     */
-    public int maxOpId() {
-        assert opIdToInstructionMap.length > 0 : "no operations";
-        return (opIdToInstructionMap.length - 1) << 1;
-    }
-}
diff -r 336adcd0070b -r 5e33637f5e5a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java	Tue Feb 03 04:17:06 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java	Tue Feb 03 11:10:24 2015 +0100
@@ -53,329 +53,122 @@
 
     public static class Options {
         // @formatter:off
-        @Option(help = "Enable linear scan stack slot allocation.", type = OptionType.Debug)
-        public static final OptionValue<Boolean> EnableLSStackSlotAllocation = new OptionValue<>(true);
+        @Option(help = "Use linear scan stack slot allocation.", type = OptionType.Debug)
+        public static final OptionValue<Boolean> LSStackSlotAllocation = new OptionValue<>(true);
         // @formatter:on
     }
 
-    /**
-     * The number of allocated stack slots.
-     */
-    static final DebugMetric uninitializedSlots = Debug.metric("StackSlotAllocator[uninitializedSlots]");
-
     public void allocateStackSlots(FrameMapBuilderTool builder, LIRGenerationResult res) {
         new Allocator(res.getLIR(), builder).allocate();
     }
 
-    static final class Allocator extends InstructionNumberer {
+    private static final class Allocator {
         private final LIR lir;
         private final FrameMapBuilderTool frameMapBuilder;
         private final StackInterval[] stackSlotMap;
-        private LinkedList<StackInterval> unhandled;
-        private LinkedList<StackInterval> active;
-
-        private List<? extends AbstractBlock<?>> sortedBlocks;
+        private final PriorityQueue<StackInterval> unhandled;
+        private final PriorityQueue<StackInterval> active;
+        private final List<? extends AbstractBlock<?>> sortedBlocks;
+        private final int maxOpId;
 
         private Allocator(LIR lir, FrameMapBuilderTool frameMapBuilder) {
             this.lir = lir;
             this.frameMapBuilder = frameMapBuilder;
             this.stackSlotMap = new StackInterval[frameMapBuilder.getNumberOfStackSlots()];
+            this.sortedBlocks = lir.getControlFlowGraph().getBlocks();
+
+            // insert by from
+            this.unhandled = new PriorityQueue<>((a, b) -> a.from() - b.from());
+            // insert by to
+            this.active = new PriorityQueue<>((a, b) -> a.to() - b.to());
+
+            // step 1: number instructions
+            this.maxOpId = numberInstructions(lir, sortedBlocks);
         }
 
         private void allocate() {
-            // create block ordering
-            List<? extends AbstractBlock<?>> blocks = lir.getControlFlowGraph().getBlocks();
-            assert blocks.size() > 0;
-
-            sortedBlocks = lir.getControlFlowGraph().getBlocks();
-            numberInstructions(lir, sortedBlocks);
             Debug.dump(lir, "After StackSlot numbering");
 
             long currentFrameSize = Debug.isMeterEnabled() ? frameMapBuilder.getFrameMap().currentFrameSize() : 0;
-            // build intervals
-            // buildIntervals();
+            // step 2: build intervals
             try (Scope s = Debug.scope("StackSlotAllocationBuildIntervals"); Indent indent = Debug.logAndIndent("BuildIntervals")) {
-                buildIntervalsSlow();
+                buildIntervals();
             }
+            // step 3: verify intervals
             if (Debug.isEnabled()) {
                 verifyIntervals();
             }
             if (Debug.isDumpEnabled()) {
                 dumpIntervals("Before stack slot allocation");
             }
-            // allocate stack slots
+            // step 4: allocate stack slots
             allocateStackSlots();
             if (Debug.isDumpEnabled()) {
                 dumpIntervals("After stack slot allocation");
             }
 
-            // assign stack slots
+            // step 5: assign stack slots
             assignStackSlots();
             Debug.dump(lir, "After StackSlot assignment");
-            StackSlotAllocator.allocatedFramesize.add(frameMapBuilder.getFrameMap().currentFrameSize() - currentFrameSize);
-        }
-
-        private void buildIntervalsSlow() {
-            new SlowIntervalBuilder().build();
-        }
-
-        /**
-         * Calculates the stack intervals using a worklist-based backwards data-flow analysis.
-         */
-        private final class SlowIntervalBuilder {
-            final BlockMap<BitSet> liveInMap;
-            final BlockMap<BitSet> liveOutMap;
-
-            private SlowIntervalBuilder() {
-                liveInMap = new BlockMap<>(lir.getControlFlowGraph());
-                liveOutMap = new BlockMap<>(lir.getControlFlowGraph());
-            }
-
-            private void build() {
-                Deque<AbstractBlock<?>> worklist = new ArrayDeque<>();
-                for (int i = lir.getControlFlowGraph().getBlocks().size() - 1; i >= 0; i--) {
-                    worklist.add(lir.getControlFlowGraph().getBlocks().get(i));
-                }
-                for (AbstractBlock<?> block : lir.getControlFlowGraph().getBlocks()) {
-                    liveInMap.put(block, new BitSet(frameMapBuilder.getNumberOfStackSlots()));
-                }
-                while (!worklist.isEmpty()) {
-                    AbstractBlock<?> block = worklist.poll();
-                    processBlock(block, worklist);
-                }
-            }
-
-            /**
-             * Merge outSet with in-set of successors.
-             */
-            private boolean updateOutBlock(AbstractBlock<?> block) {
-                BitSet union = new BitSet(frameMapBuilder.getNumberOfStackSlots());
-                block.getSuccessors().forEach(succ -> union.or(liveInMap.get(succ)));
-                BitSet outSet = liveOutMap.get(block);
-                // check if changed
-                if (outSet == null || !union.equals(outSet)) {
-                    liveOutMap.put(block, union);
-                    return true;
-                }
-                return false;
-            }
-
-            private void processBlock(AbstractBlock<?> block, Deque<AbstractBlock<?>> worklist) {
-                if (updateOutBlock(block)) {
-                    try (Indent indent = Debug.logAndIndent("handle block %s", block)) {
-                        List<LIRInstruction> instructions = lir.getLIRforBlock(block);
-                        // get out set and mark intervals
-                        BitSet outSet = liveOutMap.get(block);
-                        markOutInterval(outSet, getBlockEnd(instructions));
-                        printLiveSet("liveOut", outSet);
-
-                        // process instructions
-                        BlockClosure closure = new BlockClosure((BitSet) outSet.clone());
-                        for (int i = instructions.size() - 1; i >= 0; i--) {
-                            LIRInstruction inst = instructions.get(i);
-                            closure.processInstructionBottomUp(inst);
-                        }
-
-                        // add predecessors to work list
-                        worklist.addAll(block.getPredecessors());
-                        // set in set and mark intervals
-                        BitSet inSet = closure.getCurrentSet();
-                        liveInMap.put(block, inSet);
-                        markInInterval(inSet, getBlockBegin(instructions));
-                        printLiveSet("liveIn", inSet);
-                    }
-                }
-            }
-
-            private void printLiveSet(String label, BitSet liveSet) {
-                if (Debug.isLogEnabled()) {
-                    try (Indent indent = Debug.logAndIndent(label)) {
-                        Debug.log("%s", liveSetToString(liveSet));
-                    }
-                }
-            }
-
-            private String liveSetToString(BitSet liveSet) {
-                StringBuilder sb = new StringBuilder();
-                for (int i = liveSet.nextSetBit(0); i >= 0; i = liveSet.nextSetBit(i + 1)) {
-                    StackInterval interval = getIntervalFromStackId(i);
-                    sb.append(interval.getOperand()).append(" ");
-                }
-                return sb.toString();
-            }
-
-            protected void markOutInterval(BitSet outSet, int blockEndOpId) {
-                for (int i = outSet.nextSetBit(0); i >= 0; i = outSet.nextSetBit(i + 1)) {
-                    StackInterval interval = getIntervalFromStackId(i);
-                    Debug.log("mark live operand: %s", interval.getOperand());
-                    interval.addTo(blockEndOpId);
-                }
-            }
-
-            protected void markInInterval(BitSet inSet, int blockFirstOpId) {
-                for (int i = inSet.nextSetBit(0); i >= 0; i = inSet.nextSetBit(i + 1)) {
-                    StackInterval interval = getIntervalFromStackId(i);
-                    Debug.log("mark live operand: %s", interval.getOperand());
-                    interval.addFrom(blockFirstOpId);
-                }
-            }
-
-            private final class BlockClosure {
-                private final BitSet currentSet;
-
-                private BlockClosure(BitSet set) {
-                    currentSet = set;
-                }
-
-                private BitSet getCurrentSet() {
-                    return currentSet;
-                }
-
-                /**
-                 * Process all values of an instruction bottom-up, i.e. definitions before usages.
-                 * Values that start or end at the current operation are not included.
-                 */
-                private void processInstructionBottomUp(LIRInstruction op) {
-                    try (Indent indent = Debug.logAndIndent("handle op %d, %s", op.id(), op)) {
-                        // kills
-                        op.visitEachTemp(this::defConsumer);
-                        op.visitEachOutput(this::defConsumer);
-                        // forEachDestroyedCallerSavedRegister(op, this::defConsumer);
-
-                        // gen - values that are considered alive for this state
-                        op.visitEachAlive(this::useConsumer);
-                        op.visitEachState(this::useConsumer);
-                        // mark locations
-                        // gen
-                        op.visitEachInput(this::useConsumer);
-                    }
-                }
-
-                /**
-                 * @see InstructionValueConsumer
-                 *
-                 * @param inst
-                 * @param operand
-                 * @param mode
-                 * @param flags
-                 */
-                private void useConsumer(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
-                    if (isVirtualStackSlot(operand)) {
-                        VirtualStackSlot vslot = asVirtualStackSlot(operand);
-                        addUse(vslot, inst, flags);
-                        Debug.log("set operand: %s", operand);
-                        currentSet.set(vslot.getId());
-                    }
-                }
-
-                /**
-                 *
-                 * @see InstructionValueConsumer
-                 *
-                 * @param inst
-                 * @param operand
-                 * @param mode
-                 * @param flags
-                 */
-                private void defConsumer(LIRInstruction inst, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
-                    if (isVirtualStackSlot(operand)) {
-                        VirtualStackSlot vslot = asVirtualStackSlot(operand);
-                        addDef(vslot, inst);
-                        Debug.log("clear operand: %s", operand);
-                        currentSet.clear(vslot.getId());
-                    }
-
-                }
-
-                private void addUse(VirtualStackSlot stackSlot, LIRInstruction inst, EnumSet<OperandFlag> flags) {
-                    StackInterval interval = getOrCreateInterval(stackSlot);
-                    if (flags.contains(OperandFlag.UNINITIALIZED)) {
-                        // Stack slot is marked uninitialized so we have to assume it is live all
-                        // the time.
-                        if (Debug.isMeterEnabled() && !(interval.from() == 0 && interval.to() == maxOpId())) {
-                            uninitializedSlots.increment();
-                        }
-                        interval.addDef(0);
-                        interval.addUse(maxOpId());
-                    } else {
-                        interval.addUse(inst.id());
-                    }
-                }
-
-                private void addDef(VirtualStackSlot stackSlot, LIRInstruction inst) {
-                    StackInterval interval = getOrCreateInterval(stackSlot);
-                    interval.addDef(inst.id());
-                }
-
+            if (Debug.isMeterEnabled()) {
+                StackSlotAllocator.allocatedFramesize.add(frameMapBuilder.getFrameMap().currentFrameSize() - currentFrameSize);
             }
         }
 
-        private static int getBlockBegin(List<LIRInstruction> instructions) {
-            return instructions.get(0).id();
-        }
+        // ====================
+        // step 1: number instructions
+        // ====================
+
+        /**
+         * Numbers all instructions in all blocks.
+         *
+         * @return The id of the last operation.
+         */
+        private static int numberInstructions(LIR lir, List<? extends AbstractBlock<?>> sortedBlocks) {
+            int opId = 0;
+            int index = 0;
+            for (AbstractBlock<?> block : sortedBlocks) {
 
-        private static int getBlockEnd(List<LIRInstruction> instructions) {
-            return instructions.get(instructions.size() - 1).id() + 1;
+                List<LIRInstruction> instructions = lir.getLIRforBlock(block);
+
+                int numInst = instructions.size();
+                for (int j = 0; j < numInst; j++) {
+                    LIRInstruction op = instructions.get(j);
+                    op.setId(opId);
+
+                    index++;
+                    opId += 2; // numbering of lirOps by two
+                }
+            }
+            assert (index << 1) == opId : "must match: " + (index << 1);
+            return opId - 2;
         }
 
-        private StackInterval getOrCreateInterval(VirtualStackSlot stackSlot) {
-            StackInterval interval = get(stackSlot);
-            if (interval == null) {
-                interval = new StackInterval(stackSlot, stackSlot.getLIRKind());
-                put(stackSlot, interval);
-            }
-            return interval;
+        // ====================
+        // step 2: build intervals
+        // ====================
+
+        private void buildIntervals() {
+            new FixPointIntervalBuilder(lir, stackSlotMap, maxOpId()).build();
         }
 
-        private StackInterval get(VirtualStackSlot stackSlot) {
-            return stackSlotMap[stackSlot.getId()];
-        }
-
-        private StackInterval getIntervalFromStackId(int id) {
-            return stackSlotMap[id];
-        }
-
-        private void put(VirtualStackSlot stackSlot, StackInterval interval) {
-            stackSlotMap[stackSlot.getId()] = interval;
-        }
+        // ====================
+        // step 3: verify intervals
+        // ====================
 
         private void verifyIntervals() {
             forEachInterval(interval -> {
-                assert interval.verify(this);
+                assert interval.verify(maxOpId());
             });
         }
 
-        private void forEachInterval(Consumer<StackInterval> proc) {
-            for (StackInterval interval : stackSlotMap) {
-                if (interval != null) {
-                    proc.accept(interval);
-                }
-            }
-        }
-
-        public void dumpIntervals(String label) {
-            Debug.dump(stackSlotMap, label);
-        }
-
-        private void createUnhandled() {
-            unhandled = new LinkedList<>();
-            active = new LinkedList<>();
-            forEachInterval(this::insertSortedByFrom);
-        }
-
-        private void insertSortedByFrom(StackInterval interval) {
-            unhandled.add(interval);
-            unhandled.sort((a, b) -> a.from() - b.from());
-        }
-
-        private void insertSortedByTo(StackInterval interval) {
-            active.add(interval);
-            active.sort((a, b) -> a.to() - b.to());
-        }
+        // ====================
+        // step 4: allocate stack slots
+        // ====================
 
         private void allocateStackSlots() {
-            // create interval lists
-            createUnhandled();
+            // create unhandled lists
+            forEachInterval(unhandled::add);
 
             for (StackInterval current = activateNext(); current != null; current = activateNext()) {
                 try (Indent indent = Debug.logAndIndent("allocate %s", current)) {
@@ -395,7 +188,7 @@
                 StackSlotAllocator.virtualFramesize.add(frameMapBuilder.getFrameMap().spillSlotRangeSize(slotRange.getSlots()));
                 StackSlotAllocator.allocatedSlots.increment();
             } else {
-                assert virtualSlot instanceof SimpleVirtualStackSlot : "Unexpexted VirtualStackSlot type: " + virtualSlot;
+                assert virtualSlot instanceof SimpleVirtualStackSlot : "Unexpected VirtualStackSlot type: " + virtualSlot;
                 StackSlot slot = findFreeSlot((SimpleVirtualStackSlot) virtualSlot);
                 if (slot != null) {
                     /*
@@ -440,58 +233,108 @@
             }
         }
 
-        private EnumMap<SlotSize, LinkedList<StackSlot>> freeSlots = new EnumMap<>(SlotSize.class);
+        private EnumMap<SlotSize, Deque<StackSlot>> freeSlots;
+
+        /**
+         * @return The list of free stack slots for {@code size} or {@code null} if there is none.
+         */
+        private Deque<StackSlot> getOrNullFreeSlots(SlotSize size) {
+            if (freeSlots == null) {
+                return null;
+            }
+            return freeSlots.get(size);
+        }
 
+        /**
+         * @return the list of free stack slots for {@code size}. If there is none a list is
+         *         created.
+         */
+        private Deque<StackSlot> getOrInitFreeSlots(SlotSize size) {
+            assert size != SlotSize.Illegal;
+            Deque<StackSlot> freeList;
+            if (freeSlots != null) {
+                freeList = freeSlots.get(size);
+            } else {
+                freeSlots = new EnumMap<>(SlotSize.class);
+                freeList = null;
+            }
+            if (freeList == null) {
+                freeList = new ArrayDeque<>();
+                freeSlots.put(size, freeList);
+            }
+            assert freeList != null;
+            return freeList;
+        }
+
+        /**
+         * Gets a free stack slot for {@code slot} or {@code null} if there is none.
+         */
         private StackSlot findFreeSlot(SimpleVirtualStackSlot slot) {
             assert slot != null;
             SlotSize size = forKind(slot.getLIRKind());
-            LinkedList<StackSlot> freeList = size == SlotSize.Illegal ? null : freeSlots.get(size);
+            if (size == SlotSize.Illegal) {
+                return null;
+            }
+            Deque<StackSlot> freeList = getOrNullFreeSlots(size);
             if (freeList == null) {
                 return null;
             }
-            return freeList.pollFirst();
+            return freeList.pollLast();
         }
 
+        /**
+         * Adds a stack slot to the list of free slots.
+         */
         private void freeSlot(StackSlot slot) {
             SlotSize size = forKind(slot.getLIRKind());
             if (size == SlotSize.Illegal) {
                 return;
             }
-            LinkedList<StackSlot> freeList = freeSlots.get(size);
-            if (freeList == null) {
-                freeList = new LinkedList<>();
-                freeSlots.put(size, freeList);
-            }
-            freeList.add(slot);
+            getOrInitFreeSlots(size).addLast(slot);
         }
 
+        /**
+         * Gets the next unhandled interval and finishes handled intervals.
+         */
         private StackInterval activateNext() {
             if (unhandled.isEmpty()) {
                 return null;
             }
-            StackInterval next = unhandled.pollFirst();
+            StackInterval next = unhandled.poll();
+            // finish handled intervals
             for (int id = next.from(); activePeekId() < id;) {
-                finished(active.pollFirst());
+                finished(active.poll());
             }
-            Debug.log("activte %s", next);
-            insertSortedByTo(next);
+            Debug.log("active %s", next);
+            active.add(next);
             return next;
         }
 
+        /**
+         * Gets the lowest {@link StackInterval#to() end position} of all active intervals. If there
+         * is none {@link Integer#MAX_VALUE} is returned.
+         */
         private int activePeekId() {
-            StackInterval first = active.peekFirst();
+            StackInterval first = active.peek();
             if (first == null) {
                 return Integer.MAX_VALUE;
             }
             return first.to();
         }
 
+        /**
+         * Finishes {@code interval} by adding its location to the list of free stack slots.
+         */
         private void finished(StackInterval interval) {
             StackSlot location = interval.location();
             Debug.log("finished %s (freeing %s)", interval, location);
             freeSlot(location);
         }
 
+        // ====================
+        // step 5: assign stack slots
+        // ====================
+
         private void assignStackSlots() {
             for (AbstractBlock<?> block : sortedBlocks) {
                 lir.getLIRforBlock(block).forEach(op -> {
@@ -520,5 +363,33 @@
             }
             return value;
         }
+
+        // ====================
+        //
+        // ====================
+
+        /**
+         * Gets the highest instruction id.
+         */
+        private int maxOpId() {
+            return maxOpId;
+        }
+
+        private StackInterval get(VirtualStackSlot stackSlot) {
+            return stackSlotMap[stackSlot.getId()];
+        }
+
+        private void forEachInterval(Consumer<StackInterval> proc) {
+            for (StackInterval interval : stackSlotMap) {
+                if (interval != null) {
+                    proc.accept(interval);
+                }
+            }
+        }
+
+        private void dumpIntervals(String label) {
+            Debug.dump(stackSlotMap, label);
+        }
+
     }
 }
diff -r 336adcd0070b -r 5e33637f5e5a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackInterval.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackInterval.java	Tue Feb 03 04:17:06 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackInterval.java	Tue Feb 03 11:10:24 2015 +0100
@@ -24,9 +24,8 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
-import com.oracle.graal.debug.*;
 
-public class StackInterval {
+public final class StackInterval {
 
     private static final int INVALID_START = Integer.MAX_VALUE;
     private static final int INVALID_END = Integer.MIN_VALUE;
@@ -34,25 +33,16 @@
     private final LIRKind kind;
     private int from = INVALID_START;
     private int to = INVALID_END;
-    private final StackUsePosList usePos;
     private StackSlot location;
 
-    public enum UseType {
-        // Prefixes for c1viz
-        M_USE,
-        S_DEF
-    }
-
     public StackInterval(VirtualStackSlot operand, LIRKind kind) {
         this.operand = operand;
         this.kind = kind;
-        this.usePos = new StackUsePosList();
     }
 
-    public boolean verify(LSStackSlotAllocator.Allocator allocator) {
-        assert usePosList().verify();
-        // maxOpId + 1 it the last position in the last block (i.e. the "write position")
-        assert from >= 0 && to <= allocator.maxOpId() + 1 : String.format("from %d, to %d, maxOpId %d", from, to, allocator.maxOpId());
+    public boolean verify(int maxOpId) {
+        // maxOpId + 1 is the last position in the last block (i.e. the "write position")
+        assert 0 <= from && from <= to && to <= maxOpId + 1 : String.format("from %d, to %d, maxOpId %d", from, to, maxOpId);
         return true;
     }
 
@@ -60,18 +50,6 @@
         return operand;
     }
 
-    public void addUse(int opId) {
-        addTo(opId);
-        Debug.log("Adding use pos: %d", opId);
-        usePos.add(opId, UseType.M_USE);
-    }
-
-    public void addDef(int opId) {
-        addFrom(opId);
-        Debug.log("Adding def pos: %d", opId);
-        usePos.add(opId, UseType.S_DEF);
-    }
-
     public void addTo(int opId) {
         if (opId >= to) {
             to = opId;
@@ -100,10 +78,6 @@
         this.location = location;
     }
 
-    public StackInterval locationHint() {
-        return null;
-    }
-
     public int from() {
         return from;
     }
@@ -112,10 +86,6 @@
         return to;
     }
 
-    public StackUsePosList usePosList() {
-        return usePos;
-    }
-
     public void fixFrom() {
         if (from == INVALID_START) {
             from = 0;
diff -r 336adcd0070b -r 5e33637f5e5a graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackUsePosList.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackUsePosList.java	Tue Feb 03 04:17:06 2015 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,101 +0,0 @@
-/*
- * Copyright (c) 2014, 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.lir.stackslotalloc;
-
-import java.util.*;
-
-import com.oracle.graal.compiler.common.*;
-import com.oracle.graal.lir.stackslotalloc.StackInterval.*;
-
-public class StackUsePosList {
-
-    LinkedList<Integer> usePosList;
-    LinkedList<UseType> typeList;
-
-    StackUsePosList() {
-        this.usePosList = new LinkedList<>();
-        this.typeList = new LinkedList<>();
-    }
-
-    public int size() {
-        return usePosList.size();
-    }
-
-    public int usePos(int i) {
-        return usePosList.get(i);
-    }
-
-    public void add(int opId, UseType type) {
-        if (usePosList.isEmpty() || opId <= usePosList.getLast()) {
-            usePosList.add(opId);
-            typeList.add(type);
-        } else if (opId >= usePosList.getFirst()) {
-            usePosList.addFirst(opId);
-            typeList.addFirst(type);
-        } else {
-            int size = usePosList.size();
-
-            assert size >= 2 : "Should be handled by the cases above";
-            assert size == typeList.size() : "types and use pos out of sync";
-
-            ListIterator<Integer> posIt = usePosList.listIterator(size - 1);
-            ListIterator<UseType> typeIt = typeList.listIterator(size - 1);
-
-            // we start with size-2 because we know it will not inserted at the end
-            while (posIt.hasPrevious()) {
-                assert posIt.nextIndex() == typeIt.nextIndex();
-                int current = posIt.previous();
-
-                if (current >= opId) {
-                    posIt.next();
-                    posIt.add(opId);
-                    typeIt.add(type);
-                    assert verify();
-                    return;
-                }
-                typeIt.previous();
-            }
-            GraalInternalError.shouldNotReachHere(String.format("Unable to insert %d into %s", opId, usePosList));
-        }
-    }
-
-    public UseType getType(int i) {
-        return typeList.get(i);
-    }
-
-    @Override
-    public String toString() {
-        return usePosList.toString() + System.lineSeparator() + typeList.toString();
-    }
-
-    public boolean verify() {
-        int prev = -1;
-        for (int i = usePosList.size() - 1; i >= 0; --i) {
-            int current = usePosList.get(i);
-            assert prev <= current : String.format("use positions not sorted: %d after %d", current, prev);
-            prev = current;
-        }
-        return true;
-    }
-
-}
diff -r 336adcd0070b -r 5e33637f5e5a graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java	Tue Feb 03 04:17:06 2015 +0100
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java	Tue Feb 03 11:10:24 2015 +0100
@@ -582,22 +582,12 @@
             out.printf("\"[%s|%c]\"", interval.getOperand(), interval.getOperand().getKind().getTypeChar());
         }
 
-        StackInterval hint = interval.locationHint();
-        out.printf("%s %s ", interval.getOperand(), hint != null ? hint.getOperand() : -1);
+        out.printf("%s -1 ", interval.getOperand());
 
         out.printf("[%d, %d[", interval.from(), interval.to());
 
-        // print use positions
-        int prev = -1;
-        StackUsePosList usePosList = interval.usePosList();
-        for (int i = usePosList.size() - 1; i >= 0; --i) {
-            assert prev <= usePosList.usePos(i) : "use positions not sorted";
-            out.printf("%d %s ", usePosList.usePos(i), usePosList.getType(i));
-            prev = usePosList.usePos(i);
-        }
-
         // print spill state
-        out.printf(" \"%s\"", "NOT_SUPPORTED");
+        out.printf(" \"NOT_SUPPORTED\"");
         out.println();
     }