--- a/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/VirtualStackSlot.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/VirtualStackSlot.java	Wed Jan 28 19:32:47 2015 +0100
@@ -44,7 +44,7 @@
 
     @Override
     public String toString() {
-        return "vstack(" + id + ")" + getKindSuffix();
+        return "vstack:" + id + getKindSuffix();
     }
 
     @Override

--- a/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.baseline/src/com/oracle/graal/baseline/BaselineBytecodeParser.java	Wed Jan 28 19:32:47 2015 +0100
@@ -44,6 +44,7 @@
 import com.oracle.graal.lir.StandardOp.BlockEndOp;
 import com.oracle.graal.lir.framemap.*;
 import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.stackslotalloc.*;
 import com.oracle.graal.phases.*;
 
 public class BaselineBytecodeParser extends AbstractBytecodeParser<Value, BaselineFrameStateBuilder> implements BytecodeParserTool {
@@ -128,7 +129,6 @@
 
             RegisterConfig registerConfig = null;
             FrameMapBuilder frameMapBuilder = backend.newFrameMapBuilder(registerConfig);
-            frameMapBuilder.requireMapping(lir);
             TargetDescription target = backend.getTarget();
             CallingConvention cc = CodeUtil.getCallingConvention(backend.getProviders().getCodeCache(), CallingConvention.Type.JavaCallee, method, false);
             this.lirGenRes = backend.newLIRGenerationResult(lir, frameMapBuilder, method, null);
@@ -153,22 +153,17 @@
                 try (Scope s = Debug.scope("Allocator")) {
                     if (backend.shouldAllocateRegisters()) {
                         LinearScan.allocate(target, lirGenRes);
-                    } else if (!LocationMarker.Options.UseLocationMarker.getValue()) {
-                        // build frame map for targets that do not allocate registers
-                        lirGenRes.buildFrameMap();
                     }
                 }
-                if (LocationMarker.Options.UseLocationMarker.getValue()) {
-                    try (Scope s1 = Debug.scope("BuildFrameMap")) {
-                        // build frame map
-                        lirGenRes.buildFrameMap();
-                        Debug.dump(lir, "After FrameMap building");
-                    }
-                    try (Scope s1 = Debug.scope("MarkLocations")) {
-                        if (backend.shouldAllocateRegisters()) {
-                            // currently we mark locations only if we do register allocation
-                            LocationMarker.markLocations(lir, lirGenRes.getFrameMap());
-                        }
+                try (Scope s1 = Debug.scope("BuildFrameMap")) {
+                    // build frame map
+                    lirGenRes.buildFrameMap(new SimpleStackSlotAllocator());
+                    Debug.dump(lir, "After FrameMap building");
+                }
+                try (Scope s1 = Debug.scope("MarkLocations")) {
+                    if (backend.shouldAllocateRegisters()) {
+                        // currently we mark locations only if we do register allocation
+                        LocationMarker.markLocations(lir, lirGenRes.getFrameMap());
                     }
                 }
 

--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Wed Jan 28 19:32:47 2015 +0100
@@ -46,6 +46,7 @@
 import com.oracle.graal.lir.constopt.*;
 import com.oracle.graal.lir.framemap.*;
 import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.stackslotalloc.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.cfg.*;
 import com.oracle.graal.nodes.spi.*;
@@ -323,7 +324,6 @@
         }
         try (Scope ds = Debug.scope("BackEnd", lir)) {
             FrameMapBuilder frameMapBuilder = backend.newFrameMapBuilder(registerConfig);
-            frameMapBuilder.requireMapping(lir);
             LIRGenerationResult lirGenRes = backend.newLIRGenerationResult(lir, frameMapBuilder, graph.method(), stub);
             LIRGeneratorTool lirGen = backend.newLIRGenerator(cc, lirGenRes);
             NodeLIRBuilderTool nodeLirGen = backend.newNodeLIRBuilder(graph, lirGen);
@@ -351,25 +351,26 @@
             try (Scope s = Debug.scope("Allocator", nodeLirGen)) {
                 if (backend.shouldAllocateRegisters()) {
                     LinearScan.allocate(target, lirGenRes);
-                } else if (!LocationMarker.Options.UseLocationMarker.getValue()) {
-                    // build frame map for targets that do not allocate registers
-                    lirGenRes.buildFrameMap();
                 }
             } catch (Throwable e) {
                 throw Debug.handle(e);
             }
 
-            if (LocationMarker.Options.UseLocationMarker.getValue()) {
-                try (Scope s1 = Debug.scope("BuildFrameMap")) {
-                    // build frame map
-                    lirGenRes.buildFrameMap();
-                    Debug.dump(lir, "After FrameMap building");
+            try (Scope s1 = Debug.scope("BuildFrameMap")) {
+                // build frame map
+                final StackSlotAllocator allocator;
+                if (LSStackSlotAllocator.Options.EnableLSStackSlotAllocation.getValue()) {
+                    allocator = new LSStackSlotAllocator();
+                } else {
+                    allocator = new SimpleStackSlotAllocator();
                 }
-                try (Scope s1 = Debug.scope("MarkLocations")) {
-                    if (backend.shouldAllocateRegisters()) {
-                        // currently we mark locations only if we do register allocation
-                        LocationMarker.markLocations(lir, lirGenRes.getFrameMap());
-                    }
+                lirGenRes.buildFrameMap(allocator);
+                Debug.dump(lir, "After FrameMap building");
+            }
+            try (Scope s1 = Debug.scope("MarkLocations")) {
+                if (backend.shouldAllocateRegisters()) {
+                    // currently we mark locations only if we do register allocation
+                    LocationMarker.markLocations(lir, lirGenRes.getFrameMap());
                 }
             }
 

--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Wed Jan 28 19:32:47 2015 +0100
@@ -1640,67 +1640,6 @@
         return new IntervalWalker(this, oopIntervals, nonOopIntervals);
     }
 
-    /**
-     * Visits all intervals for a frame state. The frame state use this information to build the OOP
-     * maps.
-     */
-    private void markFrameLocations(IntervalWalker iw, LIRInstruction op, LIRFrameState info, FrameMap frameMap) {
-        Debug.log("creating oop map at opId %d", op.id());
-
-        // walk before the current operation . intervals that start at
-        // the operation (i.e. output operands of the operation) are not
-        // included in the oop map
-        iw.walkBefore(op.id());
-
-        // TODO(je) we could pass this as parameter
-        AbstractBlock<?> block = blockForId(op.id());
-
-        // Iterate through active intervals
-        for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) {
-            Value operand = interval.operand;
-
-            assert interval.currentFrom() <= op.id() && op.id() <= interval.currentTo() : "interval should not be active otherwise";
-            assert isVariable(interval.operand) : "fixed interval found";
-
-            // Check if this range covers the instruction. Intervals that
-            // start or end at the current operation are not included in the
-            // oop map, except in the case of patching moves. For patching
-            // moves, any intervals which end at this instruction are included
-            // in the oop map since we may safepoint while doing the patch
-            // before we've consumed the inputs.
-            if (op.id() < interval.currentTo() && !isIllegal(interval.location())) {
-                // caller-save registers must not be included into oop-maps at calls
-                assert !op.destroysCallerSavedRegisters() || !isRegister(operand) || !isCallerSave(operand) : "interval is in a caller-save register at a call . register will be overwritten";
-
-                info.markLocation(interval.location(), frameMap);
-
-                // Spill optimization: when the stack value is guaranteed to be always correct,
-                // then it must be added to the oop map even if the interval is currently in a
-                // register
-                int spillPos = interval.spillDefinitionPos();
-                if (interval.spillState() != SpillState.SpillInDominator) {
-                    if (interval.alwaysInMemory() && op.id() > interval.spillDefinitionPos() && !interval.location().equals(interval.spillSlot())) {
-                        assert interval.spillDefinitionPos() > 0 : "position not set correctly";
-                        assert spillPos > 0 : "position not set correctly";
-                        assert interval.spillSlot() != null : "no spill slot assigned";
-                        assert !isRegister(interval.operand) : "interval is on stack :  so stack slot is registered twice";
-                        info.markLocation(interval.spillSlot(), frameMap);
-                    }
-                } else {
-                    AbstractBlock<?> spillBlock = blockForId(spillPos);
-                    if (interval.alwaysInMemory() && !interval.location().equals(interval.spillSlot())) {
-                        if ((spillBlock.equals(block) && op.id() > spillPos) || dominates(spillBlock, block)) {
-                            assert spillPos > 0 : "position not set correctly";
-                            assert interval.spillSlot() != null : "no spill slot assigned";
-                            assert !isRegister(interval.operand) : "interval is on stack :  so stack slot is registered twice";
-                            info.markLocation(interval.spillSlot(), frameMap);
-                        }
-                    }
-                }
-            }
-        }
-    }
-
     private boolean isCallerSave(Value operand) {
         return attributes(asRegister(operand)).isCallerSave();
     }
@@ -1744,20 +1683,11 @@
         return result;
     }
 
-    private void computeDebugInfo(IntervalWalker iw, final LIRInstruction op, LIRFrameState info) {
-        if (!LocationMarker.Options.UseLocationMarker.getValue()) {
-            FrameMap frameMap = res.getFrameMap();
-            info.initDebugInfo(frameMap, !op.destroysCallerSavedRegisters() || !callKillsRegisters);
-            markFrameLocations(iw, op, info, frameMap);
-        }
-
+    private void computeDebugInfo(final LIRInstruction op, LIRFrameState info) {
         info.forEachState(op, this::debugInfoProcedure);
-        if (!LocationMarker.Options.UseLocationMarker.getValue()) {
-            info.finish(op, res.getFrameMap());
-        }
     }
 
-    private void assignLocations(List<LIRInstruction> instructions, final IntervalWalker iw) {
+    private void assignLocations(List<LIRInstruction> instructions) {
         int numInst = instructions.size();
         boolean hasDead = false;
 
@@ -1792,7 +1722,7 @@
             op.forEachOutput(assignProc);
 
             // compute reference map and debug information
-            op.forEachState((inst, state) -> computeDebugInfo(iw, inst, state));
+            op.forEachState((inst, state) -> computeDebugInfo(inst, state));
 
             // remove useless moves
             if (move != null) {
@@ -1810,41 +1740,15 @@
     }
 
     private void assignLocations() {
-        IntervalWalker iw = initIntervalWalker(IS_STACK_INTERVAL);
         try (Indent indent = Debug.logAndIndent("assign locations")) {
             for (AbstractBlock<?> block : sortedBlocks) {
                 try (Indent indent2 = Debug.logAndIndent("assign locations in block B%d", block.getId())) {
-                    assignLocations(ir.getLIRforBlock(block), iw);
+                    assignLocations(ir.getLIRforBlock(block));
                 }
             }
         }
     }
 
-    private class Mapper implements FrameMappable {
-
-        public void map(FrameMappingTool tool) {
-            try (Scope scope = Debug.scope("StackSlotMappingLSRA")) {
-                for (Interval current : intervals) {
-                    if (current != null) {
-                        if (isVirtualStackSlot(current.location())) {
-                            VirtualStackSlot value = asVirtualStackSlot(current.location());
-                            StackSlot stackSlot = tool.getStackSlot(value);
-                            Debug.log("map %s -> %s", value, stackSlot);
-                            current.assignLocation(stackSlot);
-                        }
-                        if (current.isSplitParent() && current.spillSlot() != null && isVirtualStackSlot(current.spillSlot())) {
-                            VirtualStackSlot value = asVirtualStackSlot(current.spillSlot());
-                            StackSlot stackSlot = tool.getStackSlot(value);
-                            Debug.log("map %s -> %s", value, stackSlot);
-                            current.setSpillSlot(stackSlot);
-                        }
-                    }
-                }
-            }
-        }
-
-    }
-
     public static void allocate(TargetDescription target, LIRGenerationResult res) {
         new LinearScan(target, res).allocate();
     }
@@ -1892,16 +1796,6 @@
                 printIntervals("After register allocation");
                 printLir("After register allocation", true);
 
-                // register interval mapper
-                frameMapBuilder.requireMapping(new Mapper());
-
-                if (!LocationMarker.Options.UseLocationMarker.getValue()) {
-                    // build frame map
-                    res.buildFrameMap();
-                }
-
-                printLir("After FrameMap building", true);
-
                 sortIntervalsAfterAllocation();
 
                 if (DetailedAsserts.getValue()) {

--- a/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64FrameMapBuilder.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64FrameMapBuilder.java	Wed Jan 28 19:32:47 2015 +0100
@@ -36,14 +36,14 @@
      * runtime for walking/inspecting frames of such methods.
      */
     public StackSlot allocateRBPSpillSlot() {
-        return ((AMD64FrameMap) frameMap).allocateRBPSpillSlot();
+        return ((AMD64FrameMap) getFrameMap()).allocateRBPSpillSlot();
     }
 
     public void freeRBPSpillSlot() {
-        ((AMD64FrameMap) frameMap).freeRBPSpillSlot();
+        ((AMD64FrameMap) getFrameMap()).freeRBPSpillSlot();
     }
 
     public StackSlot allocateDeoptimizationRescueSlot() {
-        return ((AMD64FrameMap) frameMap).allocateDeoptimizationRescueSlot();
+        return ((AMD64FrameMap) getFrameMap()).allocateDeoptimizationRescueSlot();
     }
 }

--- a/graal/com.oracle.graal.lir.sparc/src/com/oracle/graal/lir/sparc/SPARCFrameMapBuilder.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.lir.sparc/src/com/oracle/graal/lir/sparc/SPARCFrameMapBuilder.java	Wed Jan 28 19:32:47 2015 +0100
@@ -32,6 +32,6 @@
     }
 
     public StackSlot allocateDeoptimizationRescueSlot() {
-        return ((SPARCFrameMap) frameMap).allocateDeoptimizationRescueSlot();
+        return ((SPARCFrameMap) getFrameMap()).allocateDeoptimizationRescueSlot();
     }
 }

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java	Wed Jan 28 19:32:47 2015 +0100
@@ -22,24 +22,18 @@
  */
 package com.oracle.graal.lir;
 
-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.debug.Debug.Scope;
 import com.oracle.graal.lir.StandardOp.BlockEndOp;
 import com.oracle.graal.lir.StandardOp.LabelOp;
-import com.oracle.graal.lir.framemap.*;
 
 /**
  * This class implements the overall container for the LIR graph and directs its construction,
  * optimization, and finalization.
  */
-public class LIR implements FrameMappable {
+public class LIR {
 
     private final AbstractControlFlowGraph<?> cfg;
 
@@ -226,30 +220,4 @@
         }
     }
 
-    public void map(FrameMappingTool tool) {
-        try (Scope scope = Debug.scope("StackSlotMappingLIR")) {
-            ValueProcedure updateProc = (value, mode, flags) -> {
-                if (isVirtualStackSlot(value)) {
-                    StackSlot stackSlot = tool.getStackSlot(asVirtualStackSlot(value));
-                    Debug.log("map %s -> %s", value, stackSlot);
-                    return stackSlot;
-                }
-                return value;
-            };
-            for (AbstractBlock<?> block : getControlFlowGraph().getBlocks()) {
-                try (Indent indent0 = Debug.logAndIndent("block: %s", block)) {
-                    for (LIRInstruction inst : getLIRforBlock(block)) {
-                        try (Indent indent1 = Debug.logAndIndent("Inst: %d: %s", inst.id(), inst)) {
-                            inst.forEachAlive(updateProc);
-                            inst.forEachInput(updateProc);
-                            inst.forEachOutput(updateProc);
-                            inst.forEachTemp(updateProc);
-                            inst.forEachState(updateProc);
-                        }
-                    }
-                }
-            }
-        }
-    }
-
 }

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMap.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMap.java	Wed Jan 28 19:32:47 2015 +0100
@@ -256,7 +256,7 @@
      * @param kind The kind of the spill slot to be reserved.
      * @return A spill slot denoting the reserved memory area.
      */
-    protected StackSlot allocateSpillSlot(LIRKind kind) {
+    public StackSlot allocateSpillSlot(LIRKind kind) {
         assert frameSize == -1 : "frame size must not yet be fixed";
         int size = spillSlotSize(kind);
         spillSize = NumUtil.roundUp(spillSize + size, size);
@@ -264,6 +264,16 @@
     }
 
     /**
+     * Returns the size of the stack slot range for {@code slots} objects.
+     *
+     * @param slots The number of slots.
+     * @return The size in byte
+     */
+    public int spillSlotRangeSize(int slots) {
+        return slots * getTarget().wordSize;
+    }
+
+    /**
      * Reserves a number of contiguous slots in the frame of the method being compiled. If the
      * requested number of slots is 0, this method returns {@code null}.
      *
@@ -274,12 +284,12 @@
      *            collector could see garbage object values.
      * @return the first reserved stack slot (i.e., at the lowest address)
      */
-    protected StackSlot allocateStackSlots(int slots, BitSet objects) {
+    public StackSlot allocateStackSlots(int slots, BitSet objects) {
         assert frameSize == -1 : "frame size must not yet be fixed";
         if (slots == 0) {
             return null;
         }
-        spillSize += (slots * getTarget().wordSize);
+        spillSize += spillSlotRangeSize(slots);
 
         if (!objects.isEmpty()) {
             assert objects.length() <= slots;

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilder.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilder.java	Wed Jan 28 19:32:47 2015 +0100
@@ -27,6 +27,7 @@
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.stackslotalloc.*;
 
 /**
  * A {@link FrameMapBuilder} is used to collect all information necessary to
@@ -72,14 +73,8 @@
     void callsMethod(CallingConvention cc);
 
     /**
-     * Registers a FrameMappable class so that virtual stack slots can be changed to real stack
-     * slots.
-     */
-    void requireMapping(FrameMappable mappable);
-
-    /**
      * Creates a {@linkplain FrameMap} based on the information collected by this
      * {@linkplain FrameMapBuilder}.
      */
-    FrameMap buildFrameMap(LIRGenerationResult result);
+    FrameMap buildFrameMap(LIRGenerationResult result, StackSlotAllocator allocator);
 }

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderImpl.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderImpl.java	Wed Jan 28 19:32:47 2015 +0100
@@ -27,16 +27,19 @@
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.debug.Debug.Scope;
 import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.stackslotalloc.*;
 
 /**
  * A FrameMapBuilder that records allocation.
  */
-public class FrameMapBuilderImpl implements FrameMapBuilder {
+public class FrameMapBuilderImpl implements FrameMapBuilderTool {
 
     private final RegisterConfig registerConfig;
     private final CodeCacheProvider codeCache;
-    protected final FrameMap frameMap;
+    private final FrameMap frameMap;
     private final List<VirtualStackSlot> stackSlots;
     private final List<CallingConvention> calls;
     private int numStackSlots;
@@ -48,12 +51,9 @@
         this.frameMap = frameMap;
         this.stackSlots = new ArrayList<>();
         this.calls = new ArrayList<>();
-        this.mappables = new ArrayList<>();
         this.numStackSlots = 0;
     }
 
-    private final List<FrameMappable> mappables;
-
     public VirtualStackSlot allocateSpillSlot(LIRKind kind) {
         SimpleVirtualStackSlot slot = new SimpleVirtualStackSlot(numStackSlots++, kind);
         stackSlots.add(slot);
@@ -80,10 +80,10 @@
         return codeCache;
     }
 
-    /**
-     * Returns the number of {@link VirtualStackSlot}s created by this {@link FrameMapBuilder}. Can
-     * be used as an upper bound for an array indexed by {@link VirtualStackSlot#getId()}.
-     */
+    public FrameMap getFrameMap() {
+        return frameMap;
+    }
+
     public int getNumberOfStackSlots() {
         return numStackSlots;
     }
@@ -92,23 +92,18 @@
         calls.add(cc);
     }
 
-    public FrameMap buildFrameMap(LIRGenerationResult res) {
-        FrameMappingTool mapper = new SimpleStackSlotAllocator().allocateStackSlots(this);
+    public FrameMap buildFrameMap(LIRGenerationResult res, StackSlotAllocator allocator) {
+        try (Scope s = Debug.scope("StackSlotAllocation")) {
+            allocator.allocateStackSlots(this, res);
+        }
         for (CallingConvention cc : calls) {
             frameMap.callsMethod(cc);
         }
-        // rewrite
-        mappables.forEach(m -> m.map(mapper));
-
         frameMap.finish();
         return frameMap;
     }
 
-    public void requireMapping(FrameMappable mappable) {
-        this.mappables.add(mappable);
-    }
-
-    List<VirtualStackSlot> getStackSlots() {
+    public List<VirtualStackSlot> getStackSlots() {
         return stackSlots;
     }
 

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMapBuilderTool.java	Wed Jan 28 19:32:47 2015 +0100
@@ -0,0 +1,44 @@
+/*
+ * Copyright (c) 2014, 2014, 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.framemap;
+
+import java.util.*;
+
+import com.oracle.graal.api.code.*;
+
+/**
+ * A {@link FrameMapBuilder} that allows access to the underlying {@link FrameMap}.
+ */
+public interface FrameMapBuilderTool extends FrameMapBuilder {
+
+    /**
+     * Returns the number of {@link VirtualStackSlot}s created by this {@link FrameMapBuilder}. Can
+     * be used as an upper bound for an array indexed by {@link VirtualStackSlot#getId()}.
+     */
+    int getNumberOfStackSlots();
+
+    List<VirtualStackSlot> getStackSlots();
+
+    FrameMap getFrameMap();
+
+}

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMappable.java	Wed Jan 28 15:01:21 2015 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,32 +0,0 @@
-/*
- * Copyright (c) 2014, 2014, 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.framemap;
-
-/**
- * This interface should be implemented by all classes that store virtual stack slots to convert
- * them into real stack slots when {@link FrameMapBuilder#buildFrameMap} is called. Implementors
- * should register themselves using {@link FrameMapBuilder#requireMapping(FrameMappable)}.
- */
-public interface FrameMappable {
-    void map(FrameMappingTool tool);
-}

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/FrameMappingTool.java	Wed Jan 28 15:01:21 2015 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,33 +0,0 @@
-/*
- * Copyright (c) 2014, 2014, 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.framemap;
-
-import com.oracle.graal.api.code.*;
-
-/**
- * A tool to get the real stack slot from a virtual stack slot.
- */
-@FunctionalInterface
-public interface FrameMappingTool {
-    StackSlot getStackSlot(VirtualStackSlot slot);
-}

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/SimpleStackSlotAllocator.java	Wed Jan 28 15:01:21 2015 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,53 +0,0 @@
-/*
- * Copyright (c) 2014, 2014, 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.framemap;
-
-import com.oracle.graal.api.code.*;
-import com.oracle.graal.compiler.common.*;
-
-public class SimpleStackSlotAllocator implements StackSlotAllocator {
-
-    public FrameMappingTool allocateStackSlots(FrameMapBuilderImpl builder) {
-        StackSlot[] mapping = new StackSlot[builder.getNumberOfStackSlots()];
-        for (VirtualStackSlot virtualSlot : builder.getStackSlots()) {
-            final StackSlot slot;
-            if (virtualSlot instanceof SimpleVirtualStackSlot) {
-                slot = mapSimpleVirtualStackSlot(builder, (SimpleVirtualStackSlot) virtualSlot);
-            } else if (virtualSlot instanceof VirtualStackSlotRange) {
-                slot = mapVirtualStackSlotRange(builder, (VirtualStackSlotRange) virtualSlot);
-            } else {
-                throw GraalInternalError.shouldNotReachHere("Unknown VirtualStackSlot: " + virtualSlot);
-            }
-            mapping[virtualSlot.getId()] = slot;
-        }
-        return v -> mapping[v.getId()];
-    }
-
-    protected StackSlot mapSimpleVirtualStackSlot(FrameMapBuilderImpl builder, SimpleVirtualStackSlot virtualStackSlot) {
-        return builder.frameMap.allocateSpillSlot(virtualStackSlot.getLIRKind());
-    }
-
-    protected StackSlot mapVirtualStackSlotRange(FrameMapBuilderImpl builder, VirtualStackSlotRange virtualStackSlot) {
-        return builder.frameMap.allocateStackSlots(virtualStackSlot.getSlots(), virtualStackSlot.getObjects());
-    }
-}

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/SimpleVirtualStackSlot.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/SimpleVirtualStackSlot.java	Wed Jan 28 19:32:47 2015 +0100
@@ -28,7 +28,7 @@
 /**
  * Represents a {@link VirtualStackSlot virtual stack slot} for a specific {@link LIRKind kind}.
  */
-class SimpleVirtualStackSlot extends VirtualStackSlot {
+public class SimpleVirtualStackSlot extends VirtualStackSlot {
 
     private static final long serialVersionUID = 7654295701165421750L;
 

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/StackSlotAllocator.java	Wed Jan 28 15:01:21 2015 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,33 +0,0 @@
-/*
- * Copyright (c) 2014, 2014, 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.framemap;
-
-import com.oracle.graal.api.code.*;
-
-/**
- * A {@link StackSlotAllocator} is responsible for translating {@link VirtualStackSlot virtual}
- * stack slots into {@link StackSlot real} stack slots.
- */
-public interface StackSlotAllocator {
-    FrameMappingTool allocateStackSlots(FrameMapBuilderImpl builder);
-}

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/VirtualStackSlotRange.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/framemap/VirtualStackSlotRange.java	Wed Jan 28 19:32:47 2015 +0100
@@ -31,7 +31,7 @@
  * Represents a {@link #getSlots() numbered} range of {@link VirtualStackSlot virtual stack slot} of
  * size {@link TargetDescription#wordSize}.
  */
-class VirtualStackSlotRange extends VirtualStackSlot {
+public class VirtualStackSlotRange extends VirtualStackSlot {
 
     private static final long serialVersionUID = 5152592950118317121L;
     private final BitSet objects;

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResult.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResult.java	Wed Jan 28 19:32:47 2015 +0100
@@ -24,6 +24,7 @@
 
 import com.oracle.graal.lir.*;
 import com.oracle.graal.lir.framemap.*;
+import com.oracle.graal.lir.stackslotalloc.*;
 
 public interface LIRGenerationResult {
 
@@ -31,7 +32,7 @@
      * Returns the {@link FrameMapBuilder} for collecting the information to build a
      * {@link FrameMap}.
      *
-     * This method can only be used prior calling {@link #buildFrameMap()}.
+     * This method can only be used prior calling {@link #buildFrameMap}.
      */
     FrameMapBuilder getFrameMapBuilder();
 
@@ -41,12 +42,12 @@
      *
      * @see FrameMapBuilder#buildFrameMap
      */
-    void buildFrameMap();
+    void buildFrameMap(StackSlotAllocator allocator);
 
     /**
      * Returns the {@link FrameMap} associated with this {@link LIRGenerationResult}.
      *
-     * This method can only be called after {@link #buildFrameMap()}.
+     * This method can only be called after {@link #buildFrameMap}.
      */
     FrameMap getFrameMap();
 

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResultBase.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/LIRGenerationResultBase.java	Wed Jan 28 19:32:47 2015 +0100
@@ -24,6 +24,7 @@
 
 import com.oracle.graal.lir.*;
 import com.oracle.graal.lir.framemap.*;
+import com.oracle.graal.lir.stackslotalloc.*;
 
 public class LIRGenerationResultBase implements LIRGenerationResult {
     private final LIR lir;
@@ -59,9 +60,9 @@
         return frameMapBuilder;
     }
 
-    public void buildFrameMap() {
+    public void buildFrameMap(StackSlotAllocator allocator) {
         assert frameMap == null : "buildFrameMap() can only be called once!";
-        frameMap = frameMapBuilder.buildFrameMap(this);
+        frameMap = frameMapBuilder.buildFrameMap(this, allocator);
     }
 
     public FrameMap getFrameMap() {

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/InstructionNumberer.java	Wed Jan 28 19:32:47 2015 +0100
@@ -0,0 +1,104 @@
+/*
+ * Copyright (c) 2014, 2014, 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;
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/LSStackSlotAllocator.java	Wed Jan 28 19:32:47 2015 +0100
@@ -0,0 +1,506 @@
+/*
+ * Copyright (c) 2014, 2014, 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 java.util.function.*;
+
+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.debug.Debug.Scope;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.LIRInstruction.OperandFlag;
+import com.oracle.graal.lir.LIRInstruction.OperandMode;
+import com.oracle.graal.lir.framemap.*;
+import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.options.*;
+
+/**
+ * Linear Scan {@link StackSlotAllocator}.
+ */
+public class LSStackSlotAllocator implements StackSlotAllocator {
+
+    public static class Options {
+        // @formatter:off
+        @Option(help = "Enable linear scan stack slot allocation.")
+        public static final OptionValue<Boolean> EnableLSStackSlotAllocation = new OptionValue<>(true);
+        // @formatter:on
+    }
+
+    public void allocateStackSlots(FrameMapBuilderTool builder, LIRGenerationResult res) {
+        new Allocator(res.getLIR(), builder).allocate();
+    }
+
+    static final class Allocator extends InstructionNumberer {
+        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 Allocator(LIR lir, FrameMapBuilderTool frameMapBuilder) {
+            this.lir = lir;
+            this.frameMapBuilder = frameMapBuilder;
+            this.stackSlotMap = new StackInterval[frameMapBuilder.getNumberOfStackSlots()];
+        }
+
+        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();
+            try (Scope s = Debug.scope("StackSlotAllocationBuildIntervals"); Indent indent = Debug.logAndIndent("BuildIntervals")) {
+                buildIntervalsSlow();
+            }
+            if (Debug.isEnabled()) {
+                verifyIntervals();
+            }
+            if (Debug.isDumpEnabled()) {
+                dumpIntervals("Before stack slot allocation");
+            }
+            // allocate stack slots
+            allocateStackSlots();
+            if (Debug.isDumpEnabled()) {
+                dumpIntervals("After stack slot allocation");
+            }
+
+            // assign stack slots
+            assignStackSlots();
+            Debug.dump(lir, "After StackSlot assignment");
+            StackSlotAllocator.allocatedFramesize.add(frameMapBuilder.getFrameMap().currentFrameSize() - currentFrameSize);
+        }
+
+        private void buildIntervalsSlow() {
+            new SlowIntervalBuilder().build();
+        }
+
+        private 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.
+                        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());
+                }
+
+            }
+        }
+
+        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;
+        }
+
+        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 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;
+        }
+
+        private void verifyIntervals() {
+            forEachInterval(interval -> {
+                assert interval.verify(this);
+            });
+        }
+
+        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());
+        }
+
+        private void allocateStackSlots() {
+            // create interval lists
+            createUnhandled();
+
+            for (StackInterval current = activateNext(); current != null; current = activateNext()) {
+                try (Indent indent = Debug.logAndIndent("allocate %s", current)) {
+                    allocateSlot(current);
+                }
+            }
+
+        }
+
+        private void allocateSlot(StackInterval current) {
+            VirtualStackSlot virtualSlot = current.getOperand();
+            final StackSlot location;
+            if (virtualSlot instanceof VirtualStackSlotRange) {
+                // No reuse of ranges (yet).
+                VirtualStackSlotRange slotRange = (VirtualStackSlotRange) virtualSlot;
+                location = frameMapBuilder.getFrameMap().allocateStackSlots(slotRange.getSlots(), slotRange.getObjects());
+                StackSlotAllocator.virtualFramesize.add(frameMapBuilder.getFrameMap().spillSlotRangeSize(slotRange.getSlots()));
+                StackSlotAllocator.allocatedSlots.increment();
+            } else {
+                assert virtualSlot instanceof SimpleVirtualStackSlot : "Unexpexted VirtualStackSlot type: " + virtualSlot;
+                StackSlot slot = findFreeSlot((SimpleVirtualStackSlot) virtualSlot);
+                if (slot != null) {
+                    /*
+                     * Free stack slot available. Note that we create a new one because the kind
+                     * might not match.
+                     */
+                    location = StackSlot.get(current.kind(), slot.getRawOffset(), slot.getRawAddFrameSize());
+                    StackSlotAllocator.reusedSlots.increment();
+                    Debug.log(1, "Reuse stack slot %s (reallocated from %s) for virtual stack slot %s", location, slot, virtualSlot);
+                } else {
+                    // Allocate new stack slot.
+                    location = frameMapBuilder.getFrameMap().allocateSpillSlot(virtualSlot.getLIRKind());
+                    StackSlotAllocator.virtualFramesize.add(frameMapBuilder.getFrameMap().spillSlotSize(virtualSlot.getLIRKind()));
+                    StackSlotAllocator.allocatedSlots.increment();
+                    Debug.log(1, "New stack slot %s for virtual stack slot %s", location, virtualSlot);
+                }
+            }
+            Debug.log("Allocate location %s for interval %s", location, current);
+            current.setLocation(location);
+        }
+
+        private static enum SlotSize {
+            Size1,
+            Size2,
+            Size4,
+            Size8,
+            Illegal;
+        }
+
+        private SlotSize forKind(LIRKind kind) {
+            switch (frameMapBuilder.getFrameMap().spillSlotSize(kind)) {
+                case 1:
+                    return SlotSize.Size1;
+                case 2:
+                    return SlotSize.Size2;
+                case 4:
+                    return SlotSize.Size4;
+                case 8:
+                    return SlotSize.Size8;
+                default:
+                    return SlotSize.Illegal;
+            }
+        }
+
+        private EnumMap<SlotSize, LinkedList<StackSlot>> freeSlots = new EnumMap<>(SlotSize.class);
+
+        private StackSlot findFreeSlot(SimpleVirtualStackSlot slot) {
+            assert slot != null;
+            SlotSize size = forKind(slot.getLIRKind());
+            LinkedList<StackSlot> freeList = size == SlotSize.Illegal ? null : freeSlots.get(size);
+            if (freeList == null) {
+                return null;
+            }
+            return freeList.pollFirst();
+        }
+
+        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);
+        }
+
+        private StackInterval activateNext() {
+            if (unhandled.isEmpty()) {
+                return null;
+            }
+            StackInterval next = unhandled.pollFirst();
+            for (int id = next.from(); activePeekId() < id;) {
+                finished(active.pollFirst());
+            }
+            Debug.log("activte %s", next);
+            insertSortedByTo(next);
+            return next;
+        }
+
+        private int activePeekId() {
+            StackInterval first = active.peekFirst();
+            if (first == null) {
+                return Integer.MAX_VALUE;
+            }
+            return first.to();
+        }
+
+        private void finished(StackInterval interval) {
+            StackSlot location = interval.location();
+            Debug.log("finished %s (freeing %s)", interval, location);
+            freeSlot(location);
+        }
+
+        private void assignStackSlots() {
+            for (AbstractBlock<?> block : sortedBlocks) {
+                lir.getLIRforBlock(block).forEach(op -> {
+                    op.forEachInput(this::assignSlot);
+                    op.forEachAlive(this::assignSlot);
+                    op.forEachState(this::assignSlot);
+
+                    op.forEachTemp(this::assignSlot);
+                    op.forEachOutput(this::assignSlot);
+                });
+            }
+        }
+
+        /**
+         * @see ValueProcedure
+         * @param value
+         * @param mode
+         * @param flags
+         */
+        private Value assignSlot(Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
+            if (isVirtualStackSlot(value)) {
+                VirtualStackSlot slot = asVirtualStackSlot(value);
+                StackInterval interval = get(slot);
+                assert interval != null;
+                return interval.location();
+            }
+            return value;
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/SimpleStackSlotAllocator.java	Wed Jan 28 19:32:47 2015 +0100
@@ -0,0 +1,93 @@
+/*
+ * Copyright (c) 2014, 2014, 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 com.oracle.graal.api.code.*;
+import com.oracle.graal.compiler.common.*;
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.debug.Debug.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.framemap.*;
+import com.oracle.graal.lir.gen.*;
+
+public class SimpleStackSlotAllocator implements StackSlotAllocator {
+
+    public void allocateStackSlots(FrameMapBuilderTool builder, LIRGenerationResult res) {
+        StackSlot[] mapping = new StackSlot[builder.getNumberOfStackSlots()];
+        long currentFrameSize = Debug.isMeterEnabled() ? builder.getFrameMap().currentFrameSize() : 0;
+        for (VirtualStackSlot virtualSlot : builder.getStackSlots()) {
+            final StackSlot slot;
+            if (virtualSlot instanceof SimpleVirtualStackSlot) {
+                slot = mapSimpleVirtualStackSlot(builder, (SimpleVirtualStackSlot) virtualSlot);
+                virtualFramesize.add(builder.getFrameMap().spillSlotSize(virtualSlot.getLIRKind()));
+            } else if (virtualSlot instanceof VirtualStackSlotRange) {
+                VirtualStackSlotRange slotRange = (VirtualStackSlotRange) virtualSlot;
+                slot = mapVirtualStackSlotRange(builder, slotRange);
+                virtualFramesize.add(builder.getFrameMap().spillSlotRangeSize(slotRange.getSlots()));
+            } else {
+                throw GraalInternalError.shouldNotReachHere("Unknown VirtualStackSlot: " + virtualSlot);
+            }
+            allocatedSlots.increment();
+            mapping[virtualSlot.getId()] = slot;
+        }
+        updateLIR(res, mapping);
+        allocatedFramesize.add(builder.getFrameMap().currentFrameSize() - currentFrameSize);
+    }
+
+    protected void updateLIR(LIRGenerationResult res, StackSlot[] mapping) {
+        try (Scope scope = Debug.scope("StackSlotMappingLIR")) {
+            ValueProcedure updateProc = (value, mode, flags) -> {
+                if (isVirtualStackSlot(value)) {
+                    StackSlot stackSlot = mapping[asVirtualStackSlot(value).getId()];
+                    Debug.log("map %s -> %s", value, stackSlot);
+                    return stackSlot;
+                }
+                return value;
+            };
+            for (AbstractBlock<?> block : res.getLIR().getControlFlowGraph().getBlocks()) {
+                try (Indent indent0 = Debug.logAndIndent("block: %s", block)) {
+                    for (LIRInstruction inst : res.getLIR().getLIRforBlock(block)) {
+                        try (Indent indent1 = Debug.logAndIndent("Inst: %d: %s", inst.id(), inst)) {
+                            inst.forEachAlive(updateProc);
+                            inst.forEachInput(updateProc);
+                            inst.forEachOutput(updateProc);
+                            inst.forEachTemp(updateProc);
+                            inst.forEachState(updateProc);
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    protected StackSlot mapSimpleVirtualStackSlot(FrameMapBuilderTool builder, SimpleVirtualStackSlot virtualStackSlot) {
+        return builder.getFrameMap().allocateSpillSlot(virtualStackSlot.getLIRKind());
+    }
+
+    protected StackSlot mapVirtualStackSlotRange(FrameMapBuilderTool builder, VirtualStackSlotRange virtualStackSlot) {
+        return builder.getFrameMap().allocateStackSlots(virtualStackSlot.getSlots(), virtualStackSlot.getObjects());
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackInterval.java	Wed Jan 28 19:32:47 2015 +0100
@@ -0,0 +1,134 @@
+/*
+ * Copyright (c) 2014, 2014, 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 com.oracle.graal.api.code.*;
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.debug.*;
+
+public class StackInterval {
+
+    private static final int INVALID_START = Integer.MAX_VALUE;
+    private static final int INVALID_END = Integer.MIN_VALUE;
+    private final VirtualStackSlot operand;
+    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());
+        return true;
+    }
+
+    public VirtualStackSlot getOperand() {
+        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;
+        }
+    }
+
+    protected void addFrom(int opId) {
+        if (from > opId) {
+            from = opId;
+            // set opId also as to if it has not yet been set
+            if (to == INVALID_END) {
+                to = opId;
+            }
+        }
+    }
+
+    public LIRKind kind() {
+        return kind;
+    }
+
+    public StackSlot location() {
+        return location;
+    }
+
+    public void setLocation(StackSlot location) {
+        this.location = location;
+    }
+
+    public StackInterval locationHint() {
+        return null;
+    }
+
+    public int from() {
+        return from;
+    }
+
+    public int to() {
+        return to;
+    }
+
+    public StackUsePosList usePosList() {
+        return usePos;
+    }
+
+    public void fixFrom() {
+        if (from == INVALID_START) {
+            from = 0;
+        }
+    }
+
+    public boolean isFixed() {
+        return from == 0;
+    }
+
+    @Override
+    public String toString() {
+        return String.format("SI[%d-%d] k=%s o=%s l=%s", from, to, kind, operand, location);
+    }
+
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackSlotAllocator.java	Wed Jan 28 19:32:47 2015 +0100
@@ -0,0 +1,53 @@
+/*
+ * Copyright (c) 2014, 2014, 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 com.oracle.graal.api.code.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.lir.framemap.*;
+import com.oracle.graal.lir.gen.*;
+
+/**
+ * A {@link StackSlotAllocator} is responsible for translating {@link VirtualStackSlot virtual}
+ * stack slots into {@link StackSlot real} stack slots. This includes changing all occurrences of
+ * {@link VirtualStackSlot} in the {@link LIRGenerationResult#getLIR() LIR} to {@link StackSlot}.
+ */
+public interface StackSlotAllocator {
+    /**
+     * The number of allocated stack slots.
+     */
+    static final DebugMetric allocatedSlots = Debug.metric("StackSlotAllocator[allocatedSlots]");
+    /**
+     * The number of reused stack slots.
+     */
+    static final DebugMetric reusedSlots = Debug.metric("StackSlotAllocator[reusedSlots]");
+    /**
+     * The size (in bytes) required for all allocated stack slots. Note that this number
+     * corresponds to the actual frame size and might include alignment.
+     */
+    static final DebugMetric allocatedFramesize = Debug.metric("StackSlotAllocator[AllocatedFramesize]");
+    /** The size (in bytes) required for all virtual stack slots. */
+    static final DebugMetric virtualFramesize = Debug.metric("StackSlotAllocator[VirtualFramesize]");
+
+    void allocateStackSlots(FrameMapBuilderTool builder, LIRGenerationResult res);
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/stackslotalloc/StackUsePosList.java	Wed Jan 28 19:32:47 2015 +0100
@@ -0,0 +1,101 @@
+/*
+ * Copyright (c) 2014, 2014, 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;
+    }
+
+}

--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java	Wed Jan 28 19:32:47 2015 +0100
@@ -37,6 +37,7 @@
 import com.oracle.graal.java.*;
 import com.oracle.graal.java.BciBlockMapping.BciBlock;
 import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.stackslotalloc.*;
 import com.oracle.graal.nodeinfo.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
@@ -560,6 +561,46 @@
         out.println();
     }
 
+    public void printStackIntervals(String label, StackInterval[] intervals) {
+        begin("intervals");
+        out.println(String.format("name \"%s\"", label));
+
+        for (StackInterval interval : intervals) {
+            if (interval != null) {
+                printStackInterval(interval);
+            }
+        }
+
+        end("intervals");
+    }
+
+    private void printStackInterval(StackInterval interval) {
+        out.printf("%s %s ", interval.getOperand(), interval.isFixed() ? "fixed" : interval.kind().getPlatformKind());
+        if (interval.location() != null) {
+            out.printf("\"[%s|%c]\"", interval.location(), interval.location().getKind().getTypeChar());
+        } else {
+            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("[%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.println();
+    }
+
     public void printSchedule(String message, SchedulePhase theSchedule) {
         schedule = theSchedule;
         cfg = schedule.getCFG();

--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java	Wed Jan 28 15:01:21 2015 +0100
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java	Wed Jan 28 19:32:47 2015 +0100
@@ -35,6 +35,7 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.java.*;
 import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.stackslotalloc.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.cfg.*;
 import com.oracle.graal.phases.schedule.*;
@@ -181,7 +182,8 @@
             cfgPrinter.printMachineCode(codeCache.disassemble((CompilationResult) tuple[0], (InstalledCode) tuple[1]), message);
         } else if (object instanceof Interval[]) {
             cfgPrinter.printIntervals(message, (Interval[]) object);
-
+        } else if (object instanceof StackInterval[]) {
+            cfgPrinter.printStackIntervals(message, (StackInterval[]) object);
         }
 
         cfgPrinter.target = null;