# HG changeset patch
# User Tom Rodriguez <tom.rodriguez@oracle.com>
# Date 1438041450 25200
# Node ID 8c6bc650d7facbecb2fe427f1ebb6b5dae4378b7
# Parent  7d48038267b473cefa4274a24357e68e87dc1200# Parent  1b0304bcf7014fa0542c14fd7e22ceefbeb5b448
Merge

diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/BackendOptions.java
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/BackendOptions.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/BackendOptions.java	Mon Jul 27 16:57:30 2015 -0700
@@ -25,7 +25,7 @@
 import static com.oracle.graal.compiler.common.BackendOptions.UserOptions.*;
 import static com.oracle.graal.compiler.common.GraalOptions.*;
 import jdk.internal.jvmci.options.*;
-import jdk.internal.jvmci.options.DerivedOptionValue.*;
+import jdk.internal.jvmci.options.DerivedOptionValue.OptionSupplier;
 
 /**
  * Options to control the backend configuration.
@@ -36,27 +36,44 @@
         // @formatter:off
         @Option(help = "Destruct SSA LIR eagerly (before other LIR phases).", type = OptionType.Debug)
         public static final OptionValue<Boolean> LIREagerSSADestruction = new OptionValue<>(false);
+        @Option(help = "Enable Linear Scan on SSI form.", type = OptionType.Debug)
+        public static final OptionValue<Boolean> LIROptSSILinearScan = new OptionValue<>(false);
+        @Option(help = "Enable experimental Trace Register Allocation.", type = OptionType.Debug)
+        public static final OptionValue<Boolean> TraceRA = new OptionValue<>(false);
         // @formatter:on
     }
 
+    /* Enable SSI Construction. */
+    public static final DerivedOptionValue<Boolean> EnableSSIConstruction = new DerivedOptionValue<>(new OptionSupplier<Boolean>() {
+        private static final long serialVersionUID = -7375589337502162545L;
+
+        public Boolean get() {
+            return LIROptSSILinearScan.getValue() || TraceRA.getValue();
+        }
+    });
+
     /* Create SSA LIR during LIR generation. */
     public static final DerivedOptionValue<Boolean> ConstructionSSAlirDuringLirBuilding = new DerivedOptionValue<>(new OptionSupplier<Boolean>() {
         private static final long serialVersionUID = 7657622005438210681L;
 
         public Boolean get() {
-            return SSA_LIR.getValue();
+            return SSA_LIR.getValue() || EnableSSIConstruction.getValue();
         }
     });
 
     public enum LSRAVariant {
         NONSSA_LSAR,
-        SSA_LSRA
+        SSA_LSRA,
+        SSI_LSRA
     }
 
     public static final DerivedOptionValue<LSRAVariant> LinearScanVariant = new DerivedOptionValue<>(new OptionSupplier<LSRAVariant>() {
         private static final long serialVersionUID = 364925071685235153L;
 
         public LSRAVariant get() {
+            if (LIROptSSILinearScan.getValue()) {
+                return LSRAVariant.SSI_LSRA;
+            }
             if (SSA_LIR.getValue() && !LIREagerSSADestruction.getValue()) {
                 return LSRAVariant.SSA_LSRA;
             }
@@ -71,9 +88,14 @@
         public Boolean get() {
             switch (LinearScanVariant.getValue()) {
                 case SSA_LSRA:
+                case SSI_LSRA:
                     return true;
             }
+            if (TraceRA.getValue()) {
+                return true;
+            }
             return false;
         }
     });
+
 }
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilder.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilder.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,168 @@
+/*
+ * 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.compiler.common.alloc;
+
+import java.util.*;
+
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.debug.Debug.Scope;
+
+public final class TraceBuilder<T extends AbstractBlockBase<T>> {
+
+    public static final class TraceBuilderResult<T extends AbstractBlockBase<T>> {
+        private final List<List<T>> traces;
+        private final int[] blockToTrace;
+
+        private TraceBuilderResult(List<List<T>> traces, int[] blockToTrace) {
+            this.traces = traces;
+            this.blockToTrace = blockToTrace;
+        }
+
+        public int getTraceForBlock(AbstractBlockBase<?> block) {
+            return blockToTrace[block.getId()];
+        }
+
+        public List<List<T>> getTraces() {
+            return traces;
+        }
+    }
+
+    /**
+     * Build traces of sequentially executed blocks.
+     */
+    public static <T extends AbstractBlockBase<T>> TraceBuilderResult<T> computeTraces(T startBlock, List<T> blocks) {
+        return new TraceBuilder<>(blocks).build(startBlock);
+    }
+
+    private final PriorityQueue<T> worklist;
+    private final BitSet processed;
+    /**
+     * Contains the number of unprocessed predecessors for every {@link AbstractBlockBase#getId()
+     * block}.
+     */
+    private final int[] blocked;
+    private final int[] blockToTrace;
+
+    private TraceBuilder(List<T> blocks) {
+        processed = new BitSet(blocks.size());
+        worklist = new PriorityQueue<T>(TraceBuilder::compare);
+        blocked = new int[blocks.size()];
+        blockToTrace = new int[blocks.size()];
+        for (T block : blocks) {
+            blocked[block.getId()] = block.getPredecessorCount();
+        }
+    }
+
+    private static <T extends AbstractBlockBase<T>> int compare(T a, T b) {
+        return Double.compare(b.probability(), a.probability());
+    }
+
+    private boolean processed(T b) {
+        return processed.get(b.getId());
+    }
+
+    private TraceBuilderResult<T> build(T startBlock) {
+        try (Scope s = Debug.scope("TraceBuilder"); Indent i = Debug.logAndIndent("start trace building: " + startBlock)) {
+            ArrayList<List<T>> traces = buildTraces(startBlock);
+
+            assert verify(traces);
+            return new TraceBuilderResult<>(traces, blockToTrace);
+        }
+    }
+
+    private boolean verify(ArrayList<List<T>> traces) {
+        assert traces.stream().flatMap(l -> l.stream()).distinct().count() == blocked.length : "Not all blocks assigned to traces!";
+        for (List<T> trace : traces) {
+            T last = null;
+            for (T current : trace) {
+                assert last == null || current.getPredecessors().contains(last);
+                last = current;
+            }
+        }
+        return true;
+    }
+
+    protected ArrayList<List<T>> buildTraces(T startBlock) {
+        ArrayList<List<T>> traces = new ArrayList<>();
+        // add start block
+        worklist.add(startBlock);
+        // process worklist
+        while (!worklist.isEmpty()) {
+            T block = worklist.poll();
+            assert block != null;
+            traces.add(startTrace(block, traces.size()));
+        }
+        return traces;
+    }
+
+    /**
+     * Build a new trace starting at {@code block}.
+     */
+    private List<T> startTrace(T block, int traceNumber) {
+        assert block.getPredecessors().stream().allMatch(this::processed) : "Predecessor unscheduled: " + block.getPredecessors().stream().filter(this::processed).findFirst().get();
+        ArrayList<T> trace = new ArrayList<>();
+        int blockNumber = 0;
+        try (Indent i = Debug.logAndIndent("StartTrace: " + block)) {
+            for (T currentBlock = block; currentBlock != null; currentBlock = selectNext(currentBlock)) {
+                Debug.log("add %s (prob: %f)", currentBlock, currentBlock.probability());
+                processed.set(currentBlock.getId());
+                worklist.remove(currentBlock);
+                trace.add(currentBlock);
+                unblock(currentBlock);
+                currentBlock.setLinearScanNumber(blockNumber++);
+                blockToTrace[currentBlock.getId()] = traceNumber;
+            }
+        }
+        return trace;
+    }
+
+    /**
+     * Decrease the {@link #blocked} count for all predecessors and add them to the worklist once
+     * the count reaches 0.
+     */
+    private void unblock(T currentBlock) {
+        for (T successor : currentBlock.getSuccessors()) {
+            if (!processed(successor)) {
+                int blockCount = --blocked[successor.getId()];
+                assert blockCount >= 0;
+                if (blockCount == 0) {
+                    worklist.add(successor);
+                }
+            }
+        }
+    }
+
+    /**
+     * @return The unprocessed predecessor with the highest probability, or {@code null}.
+     */
+    private T selectNext(T currentBlock) {
+        T next = null;
+        for (T succ : currentBlock.getSuccessors()) {
+            if (!processed(succ) && (next == null || succ.probability() > next.probability())) {
+                next = succ;
+            }
+        }
+        return next;
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -64,7 +64,7 @@
             emitBlock(nodeLirBuilder, lirGenRes, (Block) b, graph, schedule.getBlockToNodesMap());
         }
         context.lirGen.beforeRegisterAllocation();
-        assert !ConstructionSSAlirDuringLirBuilding.getValue() || SSAUtils.verifySSAForm(lirGenRes.getLIR());
+        assert !ConstructionSSAlirDuringLirBuilding.getValue() || SSAUtil.verifySSAForm(lirGenRes.getLIR());
     }
 
     private static void emitBlock(NodeLIRBuilderTool nodeLirGen, LIRGenerationResult lirGenRes, Block b, StructuredGraph graph, BlockMap<List<Node>> blockMap) {
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRFrameState.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRFrameState.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRFrameState.java	Mon Jul 27 16:57:30 2015 -0700
@@ -45,7 +45,7 @@
     public final LabelRef exceptionEdge;
     protected DebugInfo debugInfo;
 
-    private IntValueMap liveBasePointers;
+    private IndexedValueMap liveBasePointers;
 
     public LIRFrameState(BytecodeFrame topFrame, VirtualObject[] virtualObjects, LabelRef exceptionEdge) {
         this.topFrame = topFrame;
@@ -181,11 +181,11 @@
         debugInfo = new DebugInfo(topFrame, virtualObjects);
     }
 
-    public IntValueMap getLiveBasePointers() {
+    public IndexedValueMap getLiveBasePointers() {
         return liveBasePointers;
     }
 
-    public void setLiveBasePointers(IntValueMap liveBasePointers) {
+    public void setLiveBasePointers(IndexedValueMap liveBasePointers) {
         this.liveBasePointers = liveBasePointers;
     }
 
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRVerifier.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRVerifier.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRVerifier.java	Mon Jul 27 16:57:30 2015 -0700
@@ -131,7 +131,7 @@
                 assert last instanceof StandardOp.JumpOp : "block with successor must end with unconditional jump";
             }
             if (block.getPredecessorCount() > 1) {
-                SSAUtils.verifyPhi(lir, block);
+                SSAUtil.verifyPhi(lir, block);
             }
 
             for (LIRInstruction op : lir.getLIRforBlock(block)) {
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/Interval.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/Interval.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/Interval.java	Mon Jul 27 16:57:30 2015 -0700
@@ -291,7 +291,7 @@
     /**
      * Constants used in optimization of spilling of an interval.
      */
-    enum SpillState {
+    public enum SpillState {
         /**
          * Starting state of calculation: no definition found yet.
          */
@@ -577,7 +577,7 @@
         return first;
     }
 
-    int from() {
+    public int from() {
         return first.from;
     }
 
@@ -593,11 +593,11 @@
         return usePosList.size();
     }
 
-    void setLocationHint(Interval interval) {
+    public void setLocationHint(Interval interval) {
         locationHint = interval;
     }
 
-    boolean isSplitParent() {
+    public boolean isSplitParent() {
         return splitParent == this;
     }
 
@@ -646,22 +646,22 @@
         return splitParent().spillState;
     }
 
-    int spillDefinitionPos() {
+    public int spillDefinitionPos() {
         return splitParent().spillDefinitionPos;
     }
 
-    void setSpillState(SpillState state) {
+    public void setSpillState(SpillState state) {
         assert state.ordinal() >= spillState().ordinal() : "state cannot decrease";
         splitParent().spillState = state;
     }
 
-    void setSpillDefinitionPos(int pos) {
+    public void setSpillDefinitionPos(int pos) {
         assert spillState() == SpillState.SpillInDominator || spillState() == SpillState.NoDefinitionFound || spillDefinitionPos() == -1 : "cannot set the position twice";
         splitParent().spillDefinitionPos = pos;
     }
 
     // returns true if this interval has a shadow copy on the stack that is always correct
-    boolean alwaysInMemory() {
+    public boolean alwaysInMemory() {
         return (splitParent().spillState == SpillState.SpillInDominator || splitParent().spillState == SpillState.StoreAtDefinition || splitParent().spillState == SpillState.StartInMemory) &&
                         !canMaterialize();
     }
@@ -1051,7 +1051,7 @@
         }
     }
 
-    void addRange(int from, int to) {
+    public void addRange(int from, int to) {
         assert from < to : "invalid range";
         assert first() == Range.EndMarker || to < first().next.from : "not inserting at begin of interval";
         assert from <= first().to : "not inserting at begin of interval";
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java	Mon Jul 27 16:57:30 2015 -0700
@@ -53,20 +53,7 @@
  * >"Optimized Interval Splitting in a Linear Scan Register Allocator"</a> by Christian Wimmer and
  * Hanspeter Moessenboeck.
  */
-class LinearScan {
-
-    final LIRGenerationResult res;
-    final LIR ir;
-    final FrameMapBuilder frameMapBuilder;
-    final RegisterAttributes[] registerAttributes;
-    final Register[] registers;
-    final RegisterAllocationConfig regAllocConfig;
-    private final SpillMoveFactory moveFactory;
-
-    final boolean callKillsRegisters;
-
-    public static final int DOMINATOR_SPILL_MOVE_ID = -2;
-    static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1;
+public class LinearScan {
 
     public static class Options {
         // @formatter:off
@@ -107,15 +94,25 @@
         public BitSet liveKill;
     }
 
+    public static final int DOMINATOR_SPILL_MOVE_ID = -2;
+    private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1;
+
+    private final LIR ir;
+    private final FrameMapBuilder frameMapBuilder;
+    private final RegisterAttributes[] registerAttributes;
+    private final Register[] registers;
+    private final RegisterAllocationConfig regAllocConfig;
+    private final SpillMoveFactory moveFactory;
+
     private final BlockMap<BlockData> blockData;
 
     /**
      * List of blocks in linear-scan order. This is only correct as long as the CFG does not change.
      */
-    final List<? extends AbstractBlockBase<?>> sortedBlocks;
+    private final List<? extends AbstractBlockBase<?>> sortedBlocks;
 
     /** @see #intervals() */
-    protected Interval[] intervals;
+    private Interval[] intervals;
 
     /**
      * The number of valid entries in {@link #intervals}.
@@ -152,8 +149,8 @@
      */
     private final int firstVariableNumber;
 
-    LinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, List<? extends AbstractBlockBase<?>> sortedBlocks) {
-        this.res = res;
+    protected LinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig,
+                    List<? extends AbstractBlockBase<?>> sortedBlocks) {
         this.ir = res.getLIR();
         this.moveFactory = spillMoveFactory;
         this.frameMapBuilder = res.getFrameMapBuilder();
@@ -162,30 +159,24 @@
         this.regAllocConfig = regAllocConfig;
 
         this.registers = target.arch.getRegisters();
-        this.firstVariableNumber = registers.length;
+        this.firstVariableNumber = getRegisters().length;
         this.blockData = new BlockMap<>(ir.getControlFlowGraph());
-
-        /*
-         * If all allocatable registers are caller saved, then no registers are live across a call
-         * site. The register allocator can save time not trying to find a register at a call site.
-         */
-        this.callKillsRegisters = regAllocConfig.getRegisterConfig().areAllAllocatableRegistersCallerSaved();
     }
 
-    int getFirstLirInstructionId(AbstractBlockBase<?> block) {
+    public int getFirstLirInstructionId(AbstractBlockBase<?> block) {
         int result = ir.getLIRforBlock(block).get(0).id();
         assert result >= 0;
         return result;
     }
 
-    int getLastLirInstructionId(AbstractBlockBase<?> block) {
+    public int getLastLirInstructionId(AbstractBlockBase<?> block) {
         List<LIRInstruction> instructions = ir.getLIRforBlock(block);
         int result = instructions.get(instructions.size() - 1).id();
         assert result >= 0;
         return result;
     }
 
-    SpillMoveFactory getSpillMoveFactory() {
+    public SpillMoveFactory getSpillMoveFactory() {
         return moveFactory;
     }
 
@@ -228,7 +219,7 @@
         return firstVariableNumber - 1;
     }
 
-    BlockData getBlockData(AbstractBlockBase<?> block) {
+    public BlockData getBlockData(AbstractBlockBase<?> block) {
         return blockData.get(block);
     }
 
@@ -287,7 +278,7 @@
     /**
      * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals.
      */
-    Interval[] intervals() {
+    public Interval[] intervals() {
         return intervals;
     }
 
@@ -334,11 +325,11 @@
     }
 
     // access to block list (sorted in linear scan order)
-    int blockCount() {
+    public int blockCount() {
         return sortedBlocks.size();
     }
 
-    AbstractBlockBase<?> blockAt(int index) {
+    public AbstractBlockBase<?> blockAt(int index) {
         return sortedBlocks.get(index);
     }
 
@@ -347,7 +338,7 @@
      * block. These sets do not include any operands allocated as a result of creating
      * {@linkplain #createDerivedInterval(Interval) derived intervals}.
      */
-    int liveSetSize() {
+    public int liveSetSize() {
         return firstDerivedIntervalIndex == -1 ? operandSize() : firstDerivedIntervalIndex;
     }
 
@@ -359,13 +350,13 @@
         return intervals[operandNumber];
     }
 
-    Interval intervalFor(Value operand) {
+    public Interval intervalFor(Value operand) {
         int operandNumber = operandNumber(operand);
         assert operandNumber < intervalsSize;
         return intervals[operandNumber];
     }
 
-    Interval getOrCreateInterval(AllocatableValue operand) {
+    public Interval getOrCreateInterval(AllocatableValue operand) {
         Interval ret = intervalFor(operand);
         if (ret == null) {
             return createInterval(operand);
@@ -407,7 +398,7 @@
      * @param opId an instruction {@linkplain LIRInstruction#id id}
      * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id}
      */
-    LIRInstruction instructionForId(int opId) {
+    public LIRInstruction instructionForId(int opId) {
         assert isEven(opId) : "opId not even";
         LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)];
         assert instr.id() == opId;
@@ -420,7 +411,7 @@
      * @param opId an instruction {@linkplain LIRInstruction#id id}
      * @return the block containing the instruction denoted by {@code opId}
      */
-    AbstractBlockBase<?> blockForId(int opId) {
+    public AbstractBlockBase<?> blockForId(int opId) {
         assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range";
         return opIdToBlockMap[opIdToIndex(opId)];
     }
@@ -515,7 +506,7 @@
         return new Interval.Pair(list1, list2);
     }
 
-    void sortIntervalsBeforeAllocation() {
+    protected void sortIntervalsBeforeAllocation() {
         int sortedLen = 0;
         for (Interval interval : intervals) {
             if (interval != null) {
@@ -585,7 +576,7 @@
 
     // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode
     // instead of returning null
-    Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) {
+    public Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) {
         Interval result = interval.getSplitChildAtOpId(opId, mode, this);
 
         if (result != null) {
@@ -622,8 +613,8 @@
         return attributes(asRegister(operand)).isCallerSave();
     }
 
-    <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory,
-                    RegisterAllocationConfig registerAllocationConfig) {
+    protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder,
+                    SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) {
 
         /*
          * This is the point to enable debug logging for the whole register allocation.
@@ -688,7 +679,7 @@
         return new LinearScanAssignLocationsPhase(this);
     }
 
-    void printIntervals(String label) {
+    protected void printIntervals(String label) {
         if (Debug.isLogEnabled()) {
             try (Indent indent = Debug.logAndIndent("intervals %s", label)) {
                 for (Interval interval : intervals) {
@@ -708,7 +699,7 @@
         Debug.dump(Arrays.copyOf(intervals, intervalsSize), label);
     }
 
-    void printLir(String label, @SuppressWarnings("unused") boolean hirValid) {
+    protected void printLir(String label, @SuppressWarnings("unused") boolean hirValid) {
         Debug.dump(ir, label);
     }
 
@@ -731,7 +722,7 @@
         }
     }
 
-    void verifyIntervals() {
+    protected void verifyIntervals() {
         try (Indent indent = Debug.logAndIndent("verifying intervals")) {
             int len = intervalsSize;
 
@@ -872,4 +863,28 @@
         }
     }
 
+    public LIR getLIR() {
+        return ir;
+    }
+
+    public FrameMapBuilder getFrameMapBuilder() {
+        return frameMapBuilder;
+    }
+
+    public List<? extends AbstractBlockBase<?>> sortedBlocks() {
+        return sortedBlocks;
+    }
+
+    public Register[] getRegisters() {
+        return registers;
+    }
+
+    public RegisterAllocationConfig getRegisterAllocationConfig() {
+        return regAllocConfig;
+    }
+
+    public boolean callKillsRegisters() {
+        return regAllocConfig.getRegisterConfig().areAllAllocatableRegistersCallerSaved();
+    }
+
 }
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanAssignLocationsPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanAssignLocationsPhase.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanAssignLocationsPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -45,7 +45,7 @@
 /**
  * Phase 7: Assign register numbers back to LIR.
  */
-final class LinearScanAssignLocationsPhase extends AllocationPhase {
+public final class LinearScanAssignLocationsPhase extends AllocationPhase {
 
     private final LinearScan allocator;
 
@@ -80,7 +80,7 @@
                      * before the branch instruction. So the split child information for this branch
                      * would be incorrect.
                      */
-                    LIRInstruction instr = allocator.ir.getLIRforBlock(block).get(allocator.ir.getLIRforBlock(block).size() - 1);
+                    LIRInstruction instr = allocator.getLIR().getLIRforBlock(block).get(allocator.getLIR().getLIRforBlock(block).size() - 1);
                     if (instr instanceof StandardOp.JumpOp) {
                         if (allocator.getBlockData(block).liveOut.get(allocator.operandNumber(operand))) {
                             assert false : String.format(
@@ -125,10 +125,10 @@
              * is a branch, spill moves are inserted before this branch and so the wrong operand
              * would be returned (spill moves at block boundaries are not considered in the live
              * ranges of intervals).
-             *
+             * 
              * Solution: use the first opId of the branch target block instead.
              */
-            final LIRInstruction instr = allocator.ir.getLIRforBlock(block).get(allocator.ir.getLIRforBlock(block).size() - 1);
+            final LIRInstruction instr = allocator.getLIR().getLIRforBlock(block).get(allocator.getLIR().getLIRforBlock(block).size() - 1);
             if (instr instanceof StandardOp.JumpOp) {
                 if (allocator.getBlockData(block).liveOut.get(allocator.operandNumber(operand))) {
                     tempOpId = allocator.getFirstLirInstructionId(block.getSuccessors().iterator().next());
@@ -208,9 +208,9 @@
 
     private void assignLocations() {
         try (Indent indent = Debug.logAndIndent("assign locations")) {
-            for (AbstractBlockBase<?> block : allocator.sortedBlocks) {
+            for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
                 try (Indent indent2 = Debug.logAndIndent("assign locations in block B%d", block.getId())) {
-                    assignLocations(allocator.ir.getLIRforBlock(block));
+                    assignLocations(allocator.getLIR().getLIRforBlock(block));
                 }
             }
         }
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanEliminateSpillMovePhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanEliminateSpillMovePhase.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanEliminateSpillMovePhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -42,7 +42,7 @@
 import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
 import com.oracle.graal.lir.phases.*;
 
-class LinearScanEliminateSpillMovePhase extends AllocationPhase {
+public class LinearScanEliminateSpillMovePhase extends AllocationPhase {
 
     private static final IntervalPredicate mustStoreAtDefinition = new LinearScan.IntervalPredicate() {
 
@@ -54,7 +54,7 @@
 
     protected final LinearScan allocator;
 
-    LinearScanEliminateSpillMovePhase(LinearScan allocator) {
+    protected LinearScanEliminateSpillMovePhase(LinearScan allocator) {
         this.allocator = allocator;
     }
 
@@ -88,9 +88,9 @@
             }
 
             LIRInsertionBuffer insertionBuffer = new LIRInsertionBuffer();
-            for (AbstractBlockBase<?> block : allocator.sortedBlocks) {
+            for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
                 try (Indent indent1 = Debug.logAndIndent("Handle %s", block)) {
-                    List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block);
+                    List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
                     int numInst = instructions.size();
 
                     // iterate all instructions of the block.
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanLifetimeAnalysisPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanLifetimeAnalysisPhase.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanLifetimeAnalysisPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -50,14 +50,14 @@
 import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
 import com.oracle.graal.lir.phases.*;
 
-class LinearScanLifetimeAnalysisPhase extends AllocationPhase {
+public class LinearScanLifetimeAnalysisPhase extends AllocationPhase {
 
     protected final LinearScan allocator;
 
     /**
      * @param linearScan
      */
-    LinearScanLifetimeAnalysisPhase(LinearScan linearScan) {
+    protected LinearScanLifetimeAnalysisPhase(LinearScan linearScan) {
         allocator = linearScan;
     }
 
@@ -74,7 +74,7 @@
     /**
      * Bit set for each variable that is contained in each loop.
      */
-    BitMap2D intervalInLoop;
+    private BitMap2D intervalInLoop;
 
     boolean isIntervalInLoop(int interval, int loop) {
         return intervalInLoop.at(interval, loop);
@@ -96,8 +96,8 @@
 
         // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node.
         int numInstructions = 0;
-        for (AbstractBlockBase<?> block : allocator.sortedBlocks) {
-            numInstructions += allocator.ir.getLIRforBlock(block).size();
+        for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
+            numInstructions += allocator.getLIR().getLIRforBlock(block).size();
         }
 
         // initialize with correct length
@@ -105,10 +105,10 @@
 
         int opId = 0;
         int index = 0;
-        for (AbstractBlockBase<?> block : allocator.sortedBlocks) {
+        for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
             allocator.initBlockData(block);
 
-            List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block);
+            List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
 
             int numInst = instructions.size();
             for (int j = 0; j < numInst; j++) {
@@ -139,13 +139,13 @@
         intervalInLoop = new BitMap2D(allocator.operandSize(), allocator.numLoops());
 
         // iterate all blocks
-        for (final AbstractBlockBase<?> block : allocator.sortedBlocks) {
+        for (final AbstractBlockBase<?> block : allocator.sortedBlocks()) {
             try (Indent indent = Debug.logAndIndent("compute local live sets for block %s", block)) {
 
                 final BitSet liveGen = new BitSet(liveSize);
                 final BitSet liveKill = new BitSet(liveSize);
 
-                List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block);
+                List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
                 int numInst = instructions.size();
 
                 ValueConsumer useConsumer = (operand, mode, flags) -> {
@@ -249,7 +249,7 @@
          * sets. This is checked by these assertions to be sure about it. The entry block may have
          * incoming values in registers, which is ok.
          */
-        if (isRegister(operand) && block != allocator.ir.getControlFlowGraph().getStartBlock()) {
+        if (isRegister(operand) && block != allocator.getLIR().getControlFlowGraph().getStartBlock()) {
             if (allocator.isProcessed(operand)) {
                 assert liveKill.get(allocator.operandNumber(operand)) : "using fixed register that is not defined in this block";
             }
@@ -260,7 +260,7 @@
      * Performs a backward dataflow analysis to compute global live sets (i.e.
      * {@link BlockData#liveIn} and {@link BlockData#liveOut}) for each block.
      */
-    void computeGlobalLiveSets() {
+    protected void computeGlobalLiveSets() {
         try (Indent indent = Debug.logAndIndent("compute global live sets")) {
             int numBlocks = allocator.blockCount();
             boolean changeOccurred;
@@ -313,7 +313,7 @@
                             /*
                              * liveIn(block) is the union of liveGen(block) with (liveOut(block) &
                              * !liveKill(block)).
-                             *
+                             * 
                              * Note: liveIn has to be computed only in first iteration or if liveOut
                              * has changed!
                              */
@@ -341,7 +341,7 @@
             }
 
             // check that the liveIn set of the first block is empty
-            AbstractBlockBase<?> startBlock = allocator.ir.getControlFlowGraph().getStartBlock();
+            AbstractBlockBase<?> startBlock = allocator.getLIR().getControlFlowGraph().getStartBlock();
             if (allocator.getBlockData(startBlock).liveIn.cardinality() != 0) {
                 if (DetailedAsserts.getValue()) {
                     reportFailure(numBlocks);
@@ -356,7 +356,7 @@
         try (Scope s = Debug.forceLog()) {
             try (Indent indent = Debug.logAndIndent("report failure")) {
 
-                BitSet startBlockLiveIn = allocator.getBlockData(allocator.ir.getControlFlowGraph().getStartBlock()).liveIn;
+                BitSet startBlockLiveIn = allocator.getBlockData(allocator.getLIR().getControlFlowGraph().getStartBlock()).liveIn;
                 try (Indent indent2 = Debug.logAndIndent("Error: liveIn set of first block must be empty (when this fails, variables are used before they are defined):")) {
                     for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) {
                         Interval interval = allocator.intervalFor(operandNum);
@@ -382,11 +382,11 @@
 
                         Deque<AbstractBlockBase<?>> definedIn = new ArrayDeque<>();
                         HashSet<AbstractBlockBase<?>> usedIn = new HashSet<>();
-                        for (AbstractBlockBase<?> block : allocator.sortedBlocks) {
+                        for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
                             if (allocator.getBlockData(block).liveGen.get(operandNum)) {
                                 usedIn.add(block);
                                 try (Indent indent3 = Debug.logAndIndent("used in block B%d", block.getId())) {
-                                    for (LIRInstruction ins : allocator.ir.getLIRforBlock(block)) {
+                                    for (LIRInstruction ins : allocator.getLIR().getLIRforBlock(block)) {
                                         try (Indent indent4 = Debug.logAndIndent("%d: %s", ins.id(), ins)) {
                                             ins.forEachState((liveStateOperand, mode, flags) -> {
                                                 Debug.log("operand=%s", liveStateOperand);
@@ -399,7 +399,7 @@
                             if (allocator.getBlockData(block).liveKill.get(operandNum)) {
                                 definedIn.add(block);
                                 try (Indent indent3 = Debug.logAndIndent("defined in block B%d", block.getId())) {
-                                    for (LIRInstruction ins : allocator.ir.getLIRforBlock(block)) {
+                                    for (LIRInstruction ins : allocator.getLIR().getLIRforBlock(block)) {
                                         Debug.log("%d: %s", ins.id(), ins);
                                     }
                                 }
@@ -441,7 +441,7 @@
          * Check that fixed intervals are not live at block boundaries (live set must be empty at
          * fixed intervals).
          */
-        for (AbstractBlockBase<?> block : allocator.sortedBlocks) {
+        for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
             for (int j = 0; j <= allocator.maxRegisterNumber(); j++) {
                 assert !allocator.getBlockData(block).liveIn.get(j) : "liveIn  set of fixed register must be empty";
                 assert !allocator.getBlockData(block).liveOut.get(j) : "liveOut set of fixed register must be empty";
@@ -536,7 +536,7 @@
      * Optimizes moves related to incoming stack based arguments. The interval for the destination
      * of such moves is assigned the stack slot (which is in the caller's frame) as its spill slot.
      */
-    void handleMethodArguments(LIRInstruction op) {
+    protected void handleMethodArguments(LIRInstruction op) {
         if (op instanceof MoveOp) {
             MoveOp move = (MoveOp) op;
             if (optimizeMethodArgument(move.getInput())) {
@@ -564,7 +564,7 @@
         }
     }
 
-    void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) {
+    protected void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) {
         if (flags.contains(OperandFlag.HINT) && LinearScan.isVariableOrRegister(targetValue)) {
 
             op.forEachRegisterHint(targetValue, mode, (registerHint, valueMode, valueFlags) -> {
@@ -662,7 +662,7 @@
         return RegisterPriority.MustHaveRegister;
     }
 
-    void buildIntervals() {
+    protected void buildIntervals() {
 
         try (Indent indent = Debug.logAndIndent("build intervals")) {
             InstructionValueConsumer outputConsumer = (op, operand, mode, flags) -> {
@@ -708,7 +708,7 @@
             };
 
             // create a list with all caller-save registers (cpu, fpu, xmm)
-            Register[] callerSaveRegs = allocator.regAllocConfig.getRegisterConfig().getCallerSaveRegisters();
+            Register[] callerSaveRegs = allocator.getRegisterAllocationConfig().getRegisterConfig().getCallerSaveRegisters();
 
             // iterate all blocks in reverse order
             for (int i = allocator.blockCount() - 1; i >= 0; i--) {
@@ -716,7 +716,7 @@
                 AbstractBlockBase<?> block = allocator.blockAt(i);
                 try (Indent indent2 = Debug.logAndIndent("handle block %d", block.getId())) {
 
-                    List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block);
+                    List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
                     final int blockFrom = allocator.getFirstLirInstructionId(block);
                     int blockTo = allocator.getLastLirInstructionId(block);
 
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanOptimizeSpillPositionPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanOptimizeSpillPositionPhase.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanOptimizeSpillPositionPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -40,7 +40,7 @@
 import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
 import com.oracle.graal.lir.phases.*;
 
-final class LinearScanOptimizeSpillPositionPhase extends AllocationPhase {
+public final class LinearScanOptimizeSpillPositionPhase extends AllocationPhase {
 
     private static final DebugMetric betterSpillPos = Debug.metric("BetterSpillPosition");
     private static final DebugMetric betterSpillPosWithLowerProbability = Debug.metric("BetterSpillPositionWithLowerProbability");
@@ -60,7 +60,7 @@
 
     private void optimizeSpillPosition() {
         try (Indent indent0 = Debug.logAndIndent("OptimizeSpillPositions")) {
-            LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.ir.linearScanOrder().size()];
+            LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.getLIR().linearScanOrder().size()];
             for (Interval interval : allocator.intervals()) {
                 optimizeInterval(insertionBuffers, interval);
             }
@@ -118,7 +118,7 @@
             /*
              * The spill block is the begin of the first split child (aka the value is on the
              * stack).
-             * 
+             *
              * The problem is that if spill block has more than one predecessor, the values at the
              * end of the predecessors might differ. Therefore, we would need a spill move in all
              * predecessors. To avoid this we spill in the dominator.
@@ -154,7 +154,7 @@
             if (insertionBuffer == null) {
                 insertionBuffer = new LIRInsertionBuffer();
                 insertionBuffers[spillBlock.getId()] = insertionBuffer;
-                insertionBuffer.init(allocator.ir.getLIRforBlock(spillBlock));
+                insertionBuffer.init(allocator.getLIR().getLIRforBlock(spillBlock));
             }
             int spillOpId = allocator.getFirstLirInstructionId(spillBlock);
             // insert spill move
@@ -189,8 +189,8 @@
         public AbstractBlockBase<?> next() {
             AbstractBlockBase<?> currentBlock = block;
             int nextBlockIndex = block.getLinearScanNumber() + 1;
-            if (nextBlockIndex < allocator.sortedBlocks.size()) {
-                block = allocator.sortedBlocks.get(nextBlockIndex);
+            if (nextBlockIndex < allocator.sortedBlocks().size()) {
+                block = allocator.sortedBlocks().get(nextBlockIndex);
                 if (range.to <= allocator.getFirstLirInstructionId(block)) {
                     range = range.next;
                     if (range == Range.EndMarker) {
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -31,6 +31,8 @@
 
 import com.oracle.graal.compiler.common.alloc.*;
 import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.lir.alloc.lsra.ssa.*;
+import com.oracle.graal.lir.alloc.lsra.ssi.*;
 import com.oracle.graal.lir.gen.*;
 import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
 import com.oracle.graal.lir.phases.*;
@@ -42,6 +44,9 @@
                     RegisterAllocationConfig registerAllocationConfig) {
         final LinearScan allocator;
         switch (LinearScanVariant.getValue()) {
+            case SSI_LSRA:
+                allocator = new SSILinearScan(target, lirGenRes, spillMoveFactory, registerAllocationConfig, linearScanOrder);
+                break;
             case SSA_LSRA:
                 allocator = new SSALinearScan(target, lirGenRes, spillMoveFactory, registerAllocationConfig, linearScanOrder);
                 break;
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanRegisterAllocationPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanRegisterAllocationPhase.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanRegisterAllocationPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -33,7 +33,7 @@
 import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
 import com.oracle.graal.lir.phases.*;
 
-final class LinearScanRegisterAllocationPhase extends AllocationPhase {
+public final class LinearScanRegisterAllocationPhase extends AllocationPhase {
 
     private final LinearScan allocator;
 
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanResolveDataFlowPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanResolveDataFlowPhase.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanResolveDataFlowPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -41,11 +41,11 @@
  *
  * Insert moves at edges between blocks if intervals have been split.
  */
-class LinearScanResolveDataFlowPhase extends AllocationPhase {
+public class LinearScanResolveDataFlowPhase extends AllocationPhase {
 
     protected final LinearScan allocator;
 
-    LinearScanResolveDataFlowPhase(LinearScan allocator) {
+    protected LinearScanResolveDataFlowPhase(LinearScan allocator) {
         this.allocator = allocator;
     }
 
@@ -55,7 +55,7 @@
         resolveDataFlow();
     }
 
-    void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) {
+    protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) {
         assert moveResolver.checkEmpty();
         assert midBlock == null ||
                         (midBlock.getPredecessorCount() == 1 && midBlock.getSuccessorCount() == 1 && midBlock.getPredecessors().get(0).equals(fromBlock) && midBlock.getSuccessors().get(0).equals(
@@ -87,7 +87,7 @@
                 Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId());
             }
 
-            List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(fromBlock);
+            List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(fromBlock);
             LIRInstruction instr = instructions.get(instructions.size() - 1);
             if (instr instanceof StandardOp.JumpOp) {
                 // insert moves before branch
@@ -102,7 +102,7 @@
             }
 
             if (DetailedAsserts.getValue()) {
-                assert allocator.ir.getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label";
+                assert allocator.getLIR().getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label";
 
                 /*
                  * Because the number of predecessor edges matches the number of successor edges,
@@ -114,7 +114,7 @@
                 }
             }
 
-            moveResolver.setInsertPosition(allocator.ir.getLIRforBlock(toBlock), 1);
+            moveResolver.setInsertPosition(allocator.getLIR().getLIRforBlock(toBlock), 1);
         }
     }
 
@@ -122,7 +122,7 @@
      * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals that
      * have been split.
      */
-    void resolveDataFlow() {
+    protected void resolveDataFlow() {
         try (Indent indent = Debug.logAndIndent("resolve data flow")) {
 
             MoveResolver moveResolver = allocator.createMoveResolver();
@@ -136,11 +136,11 @@
     }
 
     protected void optimizeEmptyBlocks(MoveResolver moveResolver, BitSet blockCompleted) {
-        for (AbstractBlockBase<?> block : allocator.sortedBlocks) {
+        for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
 
             // check if block has only one predecessor and only one successor
             if (block.getPredecessorCount() == 1 && block.getSuccessorCount() == 1) {
-                List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block);
+                List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
                 assert instructions.get(0) instanceof StandardOp.LabelOp : "block must start with label";
                 assert instructions.get(instructions.size() - 1) instanceof StandardOp.JumpOp : "block with successor must end with unconditional jump";
 
@@ -174,7 +174,7 @@
 
     protected void resolveDataFlow0(MoveResolver moveResolver, BitSet blockCompleted) {
         BitSet alreadyResolved = new BitSet(allocator.blockCount());
-        for (AbstractBlockBase<?> fromBlock : allocator.sortedBlocks) {
+        for (AbstractBlockBase<?> fromBlock : allocator.sortedBlocks()) {
             if (!blockCompleted.get(fromBlock.getLinearScanNumber())) {
                 alreadyResolved.clear();
                 alreadyResolved.or(blockCompleted);
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanWalker.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanWalker.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanWalker.java	Mon Jul 27 16:57:30 2015 -0700
@@ -84,12 +84,12 @@
         super(allocator, unhandledFixedFirst, unhandledAnyFirst);
 
         moveResolver = allocator.createMoveResolver();
-        spillIntervals = Util.uncheckedCast(new List[allocator.registers.length]);
-        for (int i = 0; i < allocator.registers.length; i++) {
+        spillIntervals = Util.uncheckedCast(new List[allocator.getRegisters().length]);
+        for (int i = 0; i < allocator.getRegisters().length; i++) {
             spillIntervals[i] = EMPTY_LIST;
         }
-        usePos = new int[allocator.registers.length];
-        blockPos = new int[allocator.registers.length];
+        usePos = new int[allocator.getRegisters().length];
+        blockPos = new int[allocator.getRegisters().length];
     }
 
     void initUseLists(boolean onlyProcessUsePos) {
@@ -268,7 +268,7 @@
         // numbering of instructions is known.
         // When the block already contains spill moves, the index must be increased until the
         // correct index is reached.
-        List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(opBlock);
+        List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(opBlock);
         int index = (opId - instructions.get(0).id()) >> 1;
         assert instructions.get(index).id() <= opId : "error in calculation";
 
@@ -845,7 +845,7 @@
                          * errors
                          */
                         allocator.assignSpillSlot(interval);
-                        Debug.dump(allocator.ir, description);
+                        Debug.dump(allocator.getLIR(), description);
                         allocator.printIntervals(description);
                         throw new OutOfRegistersException("LinearScan: no register found", description);
                     }
@@ -892,7 +892,7 @@
     }
 
     boolean noAllocationPossible(Interval interval) {
-        if (allocator.callKillsRegisters) {
+        if (allocator.callKillsRegisters()) {
             // fast calculation of intervals that can never get a register because the
             // the next instruction is a call that blocks all registers
             // Note: this only works if a call kills all registers
@@ -917,7 +917,7 @@
     }
 
     void initVarsForAlloc(Interval interval) {
-        AllocatableRegisters allocatableRegisters = allocator.regAllocConfig.getAllocatableRegisters(interval.kind().getPlatformKind());
+        AllocatableRegisters allocatableRegisters = allocator.getRegisterAllocationConfig().getAllocatableRegisters(interval.kind().getPlatformKind());
         availableRegs = allocatableRegisters.allocatableRegisters;
         minReg = allocatableRegisters.minRegisterNumber;
         maxReg = allocatableRegisters.maxRegisterNumber;
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/MoveResolver.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/MoveResolver.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/MoveResolver.java	Mon Jul 27 16:57:30 2015 -0700
@@ -36,14 +36,14 @@
 
 /**
  */
-class MoveResolver {
+public class MoveResolver {
 
     private final LinearScan allocator;
 
     private int insertIdx;
     private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted
 
-    protected final List<Interval> mappingFrom;
+    private final List<Interval> mappingFrom;
     private final List<Value> mappingFromOpr;
     private final List<Interval> mappingTo;
     private boolean multipleReadsAllowed;
@@ -58,6 +58,14 @@
         }
     }
 
+    protected Interval getMappingFrom(int i) {
+        return mappingFrom.get(i);
+    }
+
+    protected int mappingFromSize() {
+        return mappingFrom.size();
+    }
+
     protected int valueBlocked(Value location) {
         if (isRegister(location)) {
             return registerBlocked[asRegister(location).number];
@@ -81,7 +89,7 @@
         return allocator;
     }
 
-    MoveResolver(LinearScan allocator) {
+    protected MoveResolver(LinearScan allocator) {
 
         this.allocator = allocator;
         this.multipleReadsAllowed = false;
@@ -90,12 +98,12 @@
         this.mappingTo = new ArrayList<>(8);
         this.insertIdx = -1;
         this.insertionBuffer = new LIRInsertionBuffer();
-        this.registerBlocked = new int[allocator.registers.length];
+        this.registerBlocked = new int[allocator.getRegisters().length];
     }
 
-    boolean checkEmpty() {
+    protected boolean checkEmpty() {
         assert mappingFrom.size() == 0 && mappingFromOpr.size() == 0 && mappingTo.size() == 0 : "list must be empty before and after processing";
-        for (int i = 0; i < getAllocator().registers.length; i++) {
+        for (int i = 0; i < getAllocator().getRegisters().length; i++) {
             assert registerBlocked[i] == 0 : "register map must be empty before and after processing";
         }
         checkMultipleReads();
@@ -351,7 +359,7 @@
         // one stack slot to another can happen (not allowed by LIRAssembler
         StackSlotValue spillSlot = fromInterval.spillSlot();
         if (spillSlot == null) {
-            spillSlot = getAllocator().frameMapBuilder.allocateSpillSlot(fromInterval.kind());
+            spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval.kind());
             fromInterval.setSpillSlot(spillSlot);
         }
         spillInterval(spillCandidate, fromInterval, spillSlot);
@@ -420,7 +428,7 @@
         this.insertIdx = newInsertIdx;
     }
 
-    void addMapping(Interval fromInterval, Interval toInterval) {
+    public void addMapping(Interval fromInterval, Interval toInterval) {
 
         if (isIllegal(toInterval.location()) && toInterval.canMaterialize()) {
             if (Debug.isLogEnabled()) {
@@ -446,7 +454,7 @@
         mappingTo.add(toInterval);
     }
 
-    void addMapping(Value fromOpr, Interval toInterval) {
+    public void addMapping(Value fromOpr, Interval toInterval) {
         if (Debug.isLogEnabled()) {
             Debug.log("add move mapping from %s to %s", fromOpr, toInterval);
         }
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/OptimizingLinearScanWalker.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/OptimizingLinearScanWalker.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/OptimizingLinearScanWalker.java	Mon Jul 27 16:57:30 2015 -0700
@@ -74,7 +74,7 @@
     @Override
     void walk() {
         try (Scope s = Debug.scope("OptimizingLinearScanWalker")) {
-            for (AbstractBlockBase<?> block : allocator.sortedBlocks) {
+            for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
                 optimizeBlock(block);
             }
         }
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/RegisterVerifier.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/RegisterVerifier.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/RegisterVerifier.java	Mon Jul 27 16:57:30 2015 -0700
@@ -120,7 +120,7 @@
 
     protected void printState(Interval[] inputState) {
         for (int i = 0; i < stateSize(); i++) {
-            Register reg = allocator.registers[i];
+            Register reg = allocator.getRegisters()[i];
             assert reg.number == i;
             if (inputState[i] != null) {
                 Debug.log(" %6s %4d  --  %s", reg, inputState[i].operandNumber, inputState[i]);
@@ -202,7 +202,7 @@
     }
 
     void processOperations(AbstractBlockBase<?> block, final Interval[] inputState) {
-        List<LIRInstruction> ops = allocator.ir.getLIRforBlock(block);
+        List<LIRInstruction> ops = allocator.getLIR().getLIRforBlock(block);
         InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
 
             @Override
@@ -242,7 +242,7 @@
             op.visitEachInput(useConsumer);
             // invalidate all caller save registers at calls
             if (op.destroysCallerSavedRegisters()) {
-                for (Register r : allocator.regAllocConfig.getRegisterConfig().getCallerSaveRegisters()) {
+                for (Register r : allocator.getRegisterAllocationConfig().getRegisterConfig().getCallerSaveRegisters()) {
                     statePut(inputState, r.asValue(), null);
                 }
             }
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinarScanResolveDataFlowPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinarScanResolveDataFlowPhase.java	Mon Jul 27 16:26:41 2015 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,89 +0,0 @@
-/*
- * 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.alloc.lsra;
-
-import static jdk.internal.jvmci.code.ValueUtil.*;
-
-import java.util.*;
-
-import com.oracle.graal.debug.*;
-import jdk.internal.jvmci.meta.*;
-
-import com.oracle.graal.compiler.common.cfg.*;
-import com.oracle.graal.lir.*;
-import com.oracle.graal.lir.ssa.*;
-import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor;
-
-class SSALinarScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase {
-
-    private static final DebugMetric numPhiResolutionMoves = Debug.metric("SSA LSRA[numPhiResolutionMoves]");
-    private static final DebugMetric numStackToStackMoves = Debug.metric("SSA LSRA[numStackToStackMoves]");
-
-    SSALinarScanResolveDataFlowPhase(LinearScan allocator) {
-        super(allocator);
-    }
-
-    @Override
-    void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) {
-        super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver);
-
-        if (toBlock.getPredecessorCount() > 1) {
-            int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock);
-            int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1;
-
-            AbstractBlockBase<?> phiOutBlock = midBlock != null ? midBlock : fromBlock;
-            List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(phiOutBlock);
-            int phiOutIdx = SSAUtils.phiOutIndex(allocator.ir, phiOutBlock);
-            int phiOutId = midBlock != null ? fromBlockLastInstructionId : instructions.get(phiOutIdx).id();
-            assert phiOutId >= 0;
-
-            PhiValueVisitor visitor = new PhiValueVisitor() {
-
-                public void visit(Value phiIn, Value phiOut) {
-                    assert !isRegister(phiOut) : "phiOut is a register: " + phiOut;
-                    assert !isRegister(phiIn) : "phiIn is a register: " + phiIn;
-                    Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF);
-                    if (isConstant(phiOut)) {
-                        numPhiResolutionMoves.increment();
-                        moveResolver.addMapping(phiOut, toInterval);
-                    } else {
-                        Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), phiOutId, LIRInstruction.OperandMode.DEF);
-                        if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) {
-                            numPhiResolutionMoves.increment();
-                            if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) {
-                                moveResolver.addMapping(fromInterval, toInterval);
-                            } else {
-                                numStackToStackMoves.increment();
-                                moveResolver.addMapping(fromInterval, toInterval);
-                            }
-                        }
-                    }
-                }
-            };
-
-            SSAUtils.forEachPhiValuePair(allocator.ir, toBlock, phiOutBlock, visitor);
-            SSAUtils.removePhiOut(allocator.ir, phiOutBlock);
-        }
-    }
-
-}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScan.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScan.java	Mon Jul 27 16:26:41 2015 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,80 +0,0 @@
-/*
- * 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.alloc.lsra;
-
-import java.util.*;
-
-import jdk.internal.jvmci.code.*;
-import com.oracle.graal.debug.*;
-import com.oracle.graal.debug.Debug.*;
-
-import com.oracle.graal.compiler.common.alloc.*;
-import com.oracle.graal.compiler.common.cfg.*;
-import com.oracle.graal.lir.gen.*;
-import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
-import com.oracle.graal.lir.ssa.*;
-
-final class SSALinearScan extends LinearScan {
-
-    SSALinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, List<? extends AbstractBlockBase<?>> sortedBlocks) {
-        super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks);
-    }
-
-    @Override
-    protected MoveResolver createMoveResolver() {
-        SSAMoveResolver moveResolver = new SSAMoveResolver(this);
-        assert moveResolver.checkEmpty();
-        return moveResolver;
-    }
-
-    @Override
-    protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() {
-        return new SSALinearScanLifetimeAnalysisPhase(this);
-    }
-
-    @Override
-    protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() {
-        return new SSALinarScanResolveDataFlowPhase(this);
-    }
-
-    @Override
-    protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() {
-        return new SSALinearScanEliminateSpillMovePhase(this);
-    }
-
-    @Override
-    protected void beforeSpillMoveElimination() {
-        /*
-         * PHI Ins are needed for the RegisterVerifier, otherwise PHIs where the Out and In value
-         * matches (ie. there is no resolution move) are falsely detected as errors.
-         */
-        try (Scope s1 = Debug.scope("Remove Phi In")) {
-            for (AbstractBlockBase<?> toBlock : sortedBlocks) {
-                if (toBlock.getPredecessorCount() > 1) {
-                    SSAUtils.removePhiIn(ir, toBlock);
-                }
-            }
-        }
-    }
-
-}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScanEliminateSpillMovePhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScanEliminateSpillMovePhase.java	Mon Jul 27 16:26:41 2015 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,89 +0,0 @@
-/*
- * 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.alloc.lsra;
-
-import static com.oracle.graal.compiler.common.BackendOptions.*;
-import static com.oracle.graal.lir.LIRValueUtil.*;
-import static jdk.internal.jvmci.code.ValueUtil.*;
-import com.oracle.graal.debug.*;
-
-import com.oracle.graal.compiler.common.cfg.*;
-import com.oracle.graal.lir.*;
-import com.oracle.graal.lir.StandardOp.LabelOp;
-import com.oracle.graal.lir.StandardOp.MoveOp;
-
-public class SSALinearScanEliminateSpillMovePhase extends LinearScanEliminateSpillMovePhase {
-
-    SSALinearScanEliminateSpillMovePhase(LinearScan allocator) {
-        super(allocator);
-    }
-
-    @Override
-    protected int firstInstructionOfInterest() {
-        // also look at Labels as they define PHI values
-        return 0;
-    }
-
-    @Override
-    protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) {
-        assert isVariable(move.getResult()) || LinearScanVariant.getValue() == LSRAVariant.SSA_LSRA : "Move should not be produced in a non-SSA compilation: " + move;
-
-        if (super.canEliminateSpillMove(block, move)) {
-            // SSA Linear Scan might introduce moves to stack slots
-            Interval curInterval = allocator.intervalFor(move.getResult());
-            assert !isRegister(curInterval.location()) && curInterval.alwaysInMemory();
-            if (!isPhiResolutionMove(block, move, curInterval)) {
-                assert isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location();
-                return true;
-            }
-        }
-        return false;
-    }
-
-    private boolean isPhiResolutionMove(AbstractBlockBase<?> block, MoveOp move, Interval toInterval) {
-        assert LinearScanVariant.getValue() == LSRAVariant.SSA_LSRA;
-        if (!toInterval.isSplitParent()) {
-            return false;
-        }
-        if ((toInterval.from() & 1) == 1) {
-            // phi intervals start at even positions.
-            return false;
-        }
-        if (block.getSuccessorCount() != 1) {
-            return false;
-        }
-        LIRInstruction op = allocator.instructionForId(toInterval.from());
-        if (!(op instanceof LabelOp)) {
-            return false;
-        }
-        AbstractBlockBase<?> intStartBlock = allocator.blockForId(toInterval.from());
-        assert allocator.ir.getLIRforBlock(intStartBlock).get(0).equals(op);
-        if (!block.getSuccessors().get(0).equals(intStartBlock)) {
-            return false;
-        }
-        try (Indent indet = Debug.indent()) {
-            Debug.log("Is a move (%s) to phi interval %s", move, toInterval);
-        }
-        return true;
-    }
-}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScanLifetimeAnalysisPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScanLifetimeAnalysisPhase.java	Mon Jul 27 16:26:41 2015 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,87 +0,0 @@
-/*
- * 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.alloc.lsra;
-
-import java.util.*;
-
-import com.oracle.graal.debug.*;
-import jdk.internal.jvmci.meta.*;
-
-import com.oracle.graal.lir.*;
-import com.oracle.graal.lir.LIRInstruction.OperandFlag;
-import com.oracle.graal.lir.LIRInstruction.OperandMode;
-import com.oracle.graal.lir.StandardOp.LabelOp;
-import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority;
-import com.oracle.graal.lir.ssa.*;
-
-public class SSALinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase {
-
-    SSALinearScanLifetimeAnalysisPhase(LinearScan linearScan) {
-        super(linearScan);
-    }
-
-    @Override
-    void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) {
-        super.addRegisterHint(op, targetValue, mode, flags, hintAtDef);
-
-        if (hintAtDef && op instanceof LabelOp) {
-            LabelOp label = (LabelOp) op;
-
-            Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue);
-
-            SSAUtils.forEachPhiRegisterHint(allocator.ir, allocator.blockForId(label.id()), label, targetValue, mode, (ValueConsumer) (registerHint, valueMode, valueFlags) -> {
-                if (LinearScan.isVariableOrRegister(registerHint)) {
-                    Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint);
-
-                    setHint(op, to, from);
-                    setHint(op, from, to);
-                }
-            });
-        }
-    }
-
-    static void setHint(final LIRInstruction op, Interval target, Interval source) {
-        Interval currentHint = target.locationHint(false);
-        if (currentHint == null || currentHint.from() > target.from()) {
-            /*
-             * Update hint if there was none or if the hint interval starts after the hinted
-             * interval.
-             */
-            target.setLocationHint(source);
-            if (Debug.isLogEnabled()) {
-                Debug.log("operation at opId %d: added hint from interval %d to %d", op.id(), source.operandNumber, target.operandNumber);
-            }
-        }
-    }
-
-    @Override
-    protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) {
-        if (op instanceof LabelOp) {
-            LabelOp label = (LabelOp) op;
-            if (label.isPhiIn()) {
-                return RegisterPriority.None;
-            }
-        }
-        return super.registerPriorityOfOutputOperand(op);
-    }
-}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSAMoveResolver.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSAMoveResolver.java	Mon Jul 27 16:26:41 2015 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,169 +0,0 @@
-/*
- * 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.alloc.lsra;
-
-import static jdk.internal.jvmci.code.ValueUtil.*;
-
-import java.util.*;
-
-import jdk.internal.jvmci.code.*;
-import jdk.internal.jvmci.common.*;
-import jdk.internal.jvmci.meta.*;
-
-import com.oracle.graal.lir.*;
-import com.oracle.graal.lir.framemap.*;
-
-final class SSAMoveResolver extends MoveResolver {
-
-    private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1;
-    private int[] stackBlocked;
-    private final int firstVirtualStackIndex;
-
-    SSAMoveResolver(LinearScan allocator) {
-        super(allocator);
-        FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) allocator.frameMapBuilder;
-        FrameMap frameMap = frameMapBuilderTool.getFrameMap();
-        this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()];
-        this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1;
-    }
-
-    @Override
-    boolean checkEmpty() {
-        for (int i = 0; i < stackBlocked.length; i++) {
-            assert stackBlocked[i] == 0 : "stack map must be empty before and after processing";
-        }
-        return super.checkEmpty();
-    }
-
-    @Override
-    protected void checkMultipleReads() {
-        // multiple reads are allowed in SSA LSRA
-    }
-
-    @Override
-    protected void verifyStackSlotMapping() {
-        // relax disjoint stack maps invariant
-    }
-
-    @Override
-    protected boolean areMultipleReadsAllowed() {
-        return true;
-    }
-
-    @Override
-    protected boolean mightBeBlocked(Value location) {
-        if (super.mightBeBlocked(location)) {
-            return true;
-        }
-        if (isStackSlotValue(location)) {
-            return true;
-        }
-        return false;
-    }
-
-    private int getStackArrayIndex(StackSlotValue stackSlotValue) {
-        if (isStackSlot(stackSlotValue)) {
-            return getStackArrayIndex(asStackSlot(stackSlotValue));
-        }
-        if (isVirtualStackSlot(stackSlotValue)) {
-            return getStackArrayIndex(asVirtualStackSlot(stackSlotValue));
-        }
-        throw JVMCIError.shouldNotReachHere("Unhandled StackSlotValue: " + stackSlotValue);
-    }
-
-    private int getStackArrayIndex(StackSlot stackSlot) {
-        int stackIdx;
-        if (stackSlot.isInCallerFrame()) {
-            // incoming stack arguments can be ignored
-            stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX;
-        } else {
-            assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot;
-            int offset = -stackSlot.getRawOffset();
-            assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex);
-            stackIdx = offset;
-        }
-        return stackIdx;
-    }
-
-    private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) {
-        return firstVirtualStackIndex + virtualStackSlot.getId();
-    }
-
-    @Override
-    protected void setValueBlocked(Value location, int direction) {
-        assert direction == 1 || direction == -1 : "out of bounds";
-        if (isStackSlotValue(location)) {
-            int stackIdx = getStackArrayIndex(asStackSlotValue(location));
-            if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
-                // incoming stack arguments can be ignored
-                return;
-            }
-            if (stackIdx >= stackBlocked.length) {
-                stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1);
-            }
-            stackBlocked[stackIdx] += direction;
-        } else {
-            super.setValueBlocked(location, direction);
-        }
-    }
-
-    @Override
-    protected int valueBlocked(Value location) {
-        if (isStackSlotValue(location)) {
-            int stackIdx = getStackArrayIndex(asStackSlotValue(location));
-            if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
-                // incoming stack arguments are always blocked (aka they can not be written)
-                return 1;
-            }
-            if (stackIdx >= stackBlocked.length) {
-                return 0;
-            }
-            return stackBlocked[stackIdx];
-        }
-        return super.valueBlocked(location);
-    }
-
-    @Override
-    protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) {
-        if (isStackSlotValue(toLocation) && isStackSlotValue(fromLocation)) {
-            return getAllocator().getSpillMoveFactory().createStackMove(toOpr, fromOpr);
-        }
-        return super.createMove(fromOpr, toOpr, fromLocation, toLocation);
-    }
-
-    @Override
-    protected void breakCycle(int spillCandidate) {
-        if (spillCandidate != -1) {
-            super.breakCycle(spillCandidate);
-            return;
-        }
-        assert mappingFrom.size() > 1;
-        // Arbitrarily select the first entry for spilling.
-        int stackSpillCandidate = 0;
-        Interval fromInterval = mappingFrom.get(stackSpillCandidate);
-        assert isStackSlotValue(fromInterval.location());
-        // allocate new stack slot
-        StackSlotValue spillSlot = getAllocator().frameMapBuilder.allocateSpillSlot(fromInterval.kind());
-        spillInterval(stackSpillCandidate, fromInterval, spillSlot);
-    }
-}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinarScanResolveDataFlowPhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinarScanResolveDataFlowPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,91 @@
+/*
+ * 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.alloc.lsra.ssa;
+
+import static jdk.internal.jvmci.code.ValueUtil.*;
+
+import java.util.*;
+
+import com.oracle.graal.debug.*;
+
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.alloc.lsra.*;
+import com.oracle.graal.lir.ssa.*;
+import com.oracle.graal.lir.ssa.SSAUtil.PhiValueVisitor;
+
+class SSALinarScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase {
+
+    private static final DebugMetric numPhiResolutionMoves = Debug.metric("SSA LSRA[numPhiResolutionMoves]");
+    private static final DebugMetric numStackToStackMoves = Debug.metric("SSA LSRA[numStackToStackMoves]");
+
+    SSALinarScanResolveDataFlowPhase(LinearScan allocator) {
+        super(allocator);
+    }
+
+    @Override
+    protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) {
+        super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver);
+
+        if (toBlock.getPredecessorCount() > 1) {
+            int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock);
+            int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1;
+
+            AbstractBlockBase<?> phiOutBlock = midBlock != null ? midBlock : fromBlock;
+            List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(phiOutBlock);
+            int phiOutIdx = SSAUtil.phiOutIndex(allocator.getLIR(), phiOutBlock);
+            int phiOutId = midBlock != null ? fromBlockLastInstructionId : instructions.get(phiOutIdx).id();
+            assert phiOutId >= 0;
+
+            PhiValueVisitor visitor = new PhiValueVisitor() {
+
+                public void visit(Value phiIn, Value phiOut) {
+                    assert !isRegister(phiOut) : "phiOut is a register: " + phiOut;
+                    assert !isRegister(phiIn) : "phiIn is a register: " + phiIn;
+                    Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF);
+                    if (isConstant(phiOut)) {
+                        numPhiResolutionMoves.increment();
+                        moveResolver.addMapping(phiOut, toInterval);
+                    } else {
+                        Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), phiOutId, LIRInstruction.OperandMode.DEF);
+                        if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) {
+                            numPhiResolutionMoves.increment();
+                            if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) {
+                                moveResolver.addMapping(fromInterval, toInterval);
+                            } else {
+                                numStackToStackMoves.increment();
+                                moveResolver.addMapping(fromInterval, toInterval);
+                            }
+                        }
+                    }
+                }
+            };
+
+            SSAUtil.forEachPhiValuePair(allocator.getLIR(), toBlock, phiOutBlock, visitor);
+            SSAUtil.removePhiOut(allocator.getLIR(), phiOutBlock);
+        }
+    }
+
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinearScan.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinearScan.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,82 @@
+/*
+ * 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.alloc.lsra.ssa;
+
+import java.util.*;
+
+import jdk.internal.jvmci.code.*;
+
+import com.oracle.graal.debug.*;
+import com.oracle.graal.debug.Debug.*;
+import com.oracle.graal.compiler.common.alloc.*;
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.lir.alloc.lsra.*;
+import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
+import com.oracle.graal.lir.ssa.*;
+
+public final class SSALinearScan extends LinearScan {
+
+    public SSALinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig,
+                    List<? extends AbstractBlockBase<?>> sortedBlocks) {
+        super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks);
+    }
+
+    @Override
+    protected MoveResolver createMoveResolver() {
+        SSAMoveResolver moveResolver = new SSAMoveResolver(this);
+        assert moveResolver.checkEmpty();
+        return moveResolver;
+    }
+
+    @Override
+    protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() {
+        return new SSALinearScanLifetimeAnalysisPhase(this);
+    }
+
+    @Override
+    protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() {
+        return new SSALinarScanResolveDataFlowPhase(this);
+    }
+
+    @Override
+    protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() {
+        return new SSALinearScanEliminateSpillMovePhase(this);
+    }
+
+    @Override
+    protected void beforeSpillMoveElimination() {
+        /*
+         * PHI Ins are needed for the RegisterVerifier, otherwise PHIs where the Out and In value
+         * matches (ie. there is no resolution move) are falsely detected as errors.
+         */
+        try (Scope s1 = Debug.scope("Remove Phi In")) {
+            for (AbstractBlockBase<?> toBlock : sortedBlocks()) {
+                if (toBlock.getPredecessorCount() > 1) {
+                    SSAUtil.removePhiIn(getLIR(), toBlock);
+                }
+            }
+        }
+    }
+
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinearScanEliminateSpillMovePhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinearScanEliminateSpillMovePhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,90 @@
+/*
+ * 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.alloc.lsra.ssa;
+
+import static com.oracle.graal.compiler.common.BackendOptions.*;
+import static com.oracle.graal.lir.LIRValueUtil.*;
+import static jdk.internal.jvmci.code.ValueUtil.*;
+
+import com.oracle.graal.debug.*;
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.StandardOp.LabelOp;
+import com.oracle.graal.lir.StandardOp.MoveOp;
+import com.oracle.graal.lir.alloc.lsra.*;
+
+public class SSALinearScanEliminateSpillMovePhase extends LinearScanEliminateSpillMovePhase {
+
+    SSALinearScanEliminateSpillMovePhase(LinearScan allocator) {
+        super(allocator);
+    }
+
+    @Override
+    protected int firstInstructionOfInterest() {
+        // also look at Labels as they define PHI values
+        return 0;
+    }
+
+    @Override
+    protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) {
+        assert isVariable(move.getResult()) || LinearScanVariant.getValue() == LSRAVariant.SSA_LSRA : "Move should not be produced in a non-SSA compilation: " + move;
+
+        if (super.canEliminateSpillMove(block, move)) {
+            // SSA Linear Scan might introduce moves to stack slots
+            Interval curInterval = allocator.intervalFor(move.getResult());
+            assert !isRegister(curInterval.location()) && curInterval.alwaysInMemory();
+            if (!isPhiResolutionMove(block, move, curInterval)) {
+                assert isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location();
+                return true;
+            }
+        }
+        return false;
+    }
+
+    private boolean isPhiResolutionMove(AbstractBlockBase<?> block, MoveOp move, Interval toInterval) {
+        assert LinearScanVariant.getValue() == LSRAVariant.SSA_LSRA;
+        if (!toInterval.isSplitParent()) {
+            return false;
+        }
+        if ((toInterval.from() & 1) == 1) {
+            // phi intervals start at even positions.
+            return false;
+        }
+        if (block.getSuccessorCount() != 1) {
+            return false;
+        }
+        LIRInstruction op = allocator.instructionForId(toInterval.from());
+        if (!(op instanceof LabelOp)) {
+            return false;
+        }
+        AbstractBlockBase<?> intStartBlock = allocator.blockForId(toInterval.from());
+        assert allocator.getLIR().getLIRforBlock(intStartBlock).get(0).equals(op);
+        if (!block.getSuccessors().get(0).equals(intStartBlock)) {
+            return false;
+        }
+        try (Indent indet = Debug.indent()) {
+            Debug.log("Is a move (%s) to phi interval %s", move, toInterval);
+        }
+        return true;
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinearScanLifetimeAnalysisPhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinearScanLifetimeAnalysisPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,89 @@
+/*
+ * 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.alloc.lsra.ssa;
+
+import java.util.*;
+
+import com.oracle.graal.debug.*;
+
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.LIRInstruction.OperandFlag;
+import com.oracle.graal.lir.LIRInstruction.OperandMode;
+import com.oracle.graal.lir.StandardOp.LabelOp;
+import com.oracle.graal.lir.alloc.lsra.*;
+import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority;
+import com.oracle.graal.lir.ssa.*;
+
+public class SSALinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase {
+
+    SSALinearScanLifetimeAnalysisPhase(LinearScan linearScan) {
+        super(linearScan);
+    }
+
+    @Override
+    protected void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) {
+        super.addRegisterHint(op, targetValue, mode, flags, hintAtDef);
+
+        if (hintAtDef && op instanceof LabelOp) {
+            LabelOp label = (LabelOp) op;
+
+            Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue);
+
+            SSAUtil.forEachPhiRegisterHint(allocator.getLIR(), allocator.blockForId(label.id()), label, targetValue, mode, (ValueConsumer) (registerHint, valueMode, valueFlags) -> {
+                if (LinearScan.isVariableOrRegister(registerHint)) {
+                    Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint);
+
+                    setHint(op, to, from);
+                    setHint(op, from, to);
+                }
+            });
+        }
+    }
+
+    public static void setHint(final LIRInstruction op, Interval target, Interval source) {
+        Interval currentHint = target.locationHint(false);
+        if (currentHint == null || currentHint.from() > target.from()) {
+            /*
+             * Update hint if there was none or if the hint interval starts after the hinted
+             * interval.
+             */
+            target.setLocationHint(source);
+            if (Debug.isLogEnabled()) {
+                Debug.log("operation at opId %d: added hint from interval %d to %d", op.id(), source.operandNumber, target.operandNumber);
+            }
+        }
+    }
+
+    @Override
+    protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) {
+        if (op instanceof LabelOp) {
+            LabelOp label = (LabelOp) op;
+            if (label.isPhiIn()) {
+                return RegisterPriority.None;
+            }
+        }
+        return super.registerPriorityOfOutputOperand(op);
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSAMoveResolver.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSAMoveResolver.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,170 @@
+/*
+ * 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.alloc.lsra.ssa;
+
+import static jdk.internal.jvmci.code.ValueUtil.*;
+
+import java.util.*;
+
+import jdk.internal.jvmci.code.*;
+import jdk.internal.jvmci.common.*;
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.alloc.lsra.*;
+import com.oracle.graal.lir.framemap.*;
+
+public final class SSAMoveResolver extends MoveResolver {
+
+    private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1;
+    private int[] stackBlocked;
+    private final int firstVirtualStackIndex;
+
+    public SSAMoveResolver(LinearScan allocator) {
+        super(allocator);
+        FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) allocator.getFrameMapBuilder();
+        FrameMap frameMap = frameMapBuilderTool.getFrameMap();
+        this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()];
+        this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1;
+    }
+
+    @Override
+    public boolean checkEmpty() {
+        for (int i = 0; i < stackBlocked.length; i++) {
+            assert stackBlocked[i] == 0 : "stack map must be empty before and after processing";
+        }
+        return super.checkEmpty();
+    }
+
+    @Override
+    protected void checkMultipleReads() {
+        // multiple reads are allowed in SSA LSRA
+    }
+
+    @Override
+    protected void verifyStackSlotMapping() {
+        // relax disjoint stack maps invariant
+    }
+
+    @Override
+    protected boolean areMultipleReadsAllowed() {
+        return true;
+    }
+
+    @Override
+    protected boolean mightBeBlocked(Value location) {
+        if (super.mightBeBlocked(location)) {
+            return true;
+        }
+        if (isStackSlotValue(location)) {
+            return true;
+        }
+        return false;
+    }
+
+    private int getStackArrayIndex(StackSlotValue stackSlotValue) {
+        if (isStackSlot(stackSlotValue)) {
+            return getStackArrayIndex(asStackSlot(stackSlotValue));
+        }
+        if (isVirtualStackSlot(stackSlotValue)) {
+            return getStackArrayIndex(asVirtualStackSlot(stackSlotValue));
+        }
+        throw JVMCIError.shouldNotReachHere("Unhandled StackSlotValue: " + stackSlotValue);
+    }
+
+    private int getStackArrayIndex(StackSlot stackSlot) {
+        int stackIdx;
+        if (stackSlot.isInCallerFrame()) {
+            // incoming stack arguments can be ignored
+            stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX;
+        } else {
+            assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot;
+            int offset = -stackSlot.getRawOffset();
+            assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex);
+            stackIdx = offset;
+        }
+        return stackIdx;
+    }
+
+    private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) {
+        return firstVirtualStackIndex + virtualStackSlot.getId();
+    }
+
+    @Override
+    protected void setValueBlocked(Value location, int direction) {
+        assert direction == 1 || direction == -1 : "out of bounds";
+        if (isStackSlotValue(location)) {
+            int stackIdx = getStackArrayIndex(asStackSlotValue(location));
+            if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
+                // incoming stack arguments can be ignored
+                return;
+            }
+            if (stackIdx >= stackBlocked.length) {
+                stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1);
+            }
+            stackBlocked[stackIdx] += direction;
+        } else {
+            super.setValueBlocked(location, direction);
+        }
+    }
+
+    @Override
+    protected int valueBlocked(Value location) {
+        if (isStackSlotValue(location)) {
+            int stackIdx = getStackArrayIndex(asStackSlotValue(location));
+            if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
+                // incoming stack arguments are always blocked (aka they can not be written)
+                return 1;
+            }
+            if (stackIdx >= stackBlocked.length) {
+                return 0;
+            }
+            return stackBlocked[stackIdx];
+        }
+        return super.valueBlocked(location);
+    }
+
+    @Override
+    protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) {
+        if (isStackSlotValue(toLocation) && isStackSlotValue(fromLocation)) {
+            return getAllocator().getSpillMoveFactory().createStackMove(toOpr, fromOpr);
+        }
+        return super.createMove(fromOpr, toOpr, fromLocation, toLocation);
+    }
+
+    @Override
+    protected void breakCycle(int spillCandidate) {
+        if (spillCandidate != -1) {
+            super.breakCycle(spillCandidate);
+            return;
+        }
+        assert mappingFromSize() > 1;
+        // Arbitrarily select the first entry for spilling.
+        int stackSpillCandidate = 0;
+        Interval fromInterval = getMappingFrom(stackSpillCandidate);
+        assert isStackSlotValue(fromInterval.location());
+        // allocate new stack slot
+        StackSlotValue spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval.kind());
+        spillInterval(stackSpillCandidate, fromInterval, spillSlot);
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScan.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScan.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,72 @@
+/*
+ * 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.alloc.lsra.ssi;
+
+import java.util.*;
+
+import jdk.internal.jvmci.code.*;
+
+import com.oracle.graal.compiler.common.alloc.*;
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.lir.alloc.lsra.*;
+import com.oracle.graal.lir.alloc.lsra.ssa.*;
+import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
+import com.oracle.graal.lir.ssi.*;
+
+public final class SSILinearScan extends LinearScan {
+
+    public SSILinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig,
+                    List<? extends AbstractBlockBase<?>> sortedBlocks) {
+        super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks);
+    }
+
+    @Override
+    protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder,
+                    SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) {
+        assert SSIVerifier.verify(lirGenRes.getLIR()) : "LIR not in SSI form.";
+        super.allocate(target, lirGenRes, codeEmittingOrder, linearScanOrder, spillMoveFactory, registerAllocationConfig);
+    }
+
+    @Override
+    protected MoveResolver createMoveResolver() {
+        SSAMoveResolver moveResolver = new SSAMoveResolver(this);
+        assert moveResolver.checkEmpty();
+        return moveResolver;
+    }
+
+    @Override
+    protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() {
+        return new SSILinearScanLifetimeAnalysisPhase(this);
+    }
+
+    @Override
+    protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() {
+        return new SSILinearScanResolveDataFlowPhase(this);
+    }
+
+    @Override
+    protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() {
+        return new SSILinearScanEliminateSpillMovePhase(this);
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScanEliminateSpillMovePhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScanEliminateSpillMovePhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,46 @@
+/*
+ * 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.alloc.lsra.ssi;
+
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.lir.StandardOp.MoveOp;
+import com.oracle.graal.lir.alloc.lsra.*;
+
+public class SSILinearScanEliminateSpillMovePhase extends LinearScanEliminateSpillMovePhase {
+
+    public SSILinearScanEliminateSpillMovePhase(LinearScan allocator) {
+        super(allocator);
+    }
+
+    @Override
+    protected int firstInstructionOfInterest() {
+        // also look at Labels as they define PHI values
+        return 0;
+    }
+
+    @Override
+    protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) {
+        // TODO (je) do not eliminate spill moves yet!
+        return false;
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScanLifetimeAnalysisPhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScanLifetimeAnalysisPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,123 @@
+/*
+ * 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.alloc.lsra.ssi;
+
+import static com.oracle.graal.lir.alloc.lsra.ssa.SSALinearScanLifetimeAnalysisPhase.*;
+
+import java.util.*;
+
+import jdk.internal.jvmci.code.*;
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.LIRInstruction.OperandFlag;
+import com.oracle.graal.lir.LIRInstruction.OperandMode;
+import com.oracle.graal.lir.StandardOp.LabelOp;
+import com.oracle.graal.lir.alloc.lsra.*;
+import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority;
+import com.oracle.graal.lir.alloc.lsra.Interval.SpillState;
+import com.oracle.graal.lir.ssi.*;
+
+public class SSILinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase {
+
+    public SSILinearScanLifetimeAnalysisPhase(LinearScan linearScan) {
+        super(linearScan);
+    }
+
+    @Override
+    protected void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) {
+        super.addRegisterHint(op, targetValue, mode, flags, hintAtDef);
+
+        if (hintAtDef && op instanceof LabelOp) {
+            LabelOp label = (LabelOp) op;
+
+            Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue);
+
+            SSIUtil.forEachRegisterHint(allocator.getLIR(), allocator.blockForId(label.id()), label, targetValue, mode, (ValueConsumer) (registerHint, valueMode, valueFlags) -> {
+                if (LinearScan.isVariableOrRegister(registerHint)) {
+                    Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint);
+
+                    setHint(op, to, from);
+                    setHint(op, from, to);
+                }
+            });
+        }
+    }
+
+    @Override
+    protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, Interval interval, int defPos) {
+        assert interval.isSplitParent() : "can only be called for split parents";
+
+        switch (interval.spillState()) {
+            case NoDefinitionFound:
+                // assert interval.spillDefinitionPos() == -1 : "must no be set before";
+                interval.setSpillDefinitionPos(defPos);
+                if (!(op instanceof LabelOp)) {
+                    // Do not update state for labels. This will be done afterwards.
+                    interval.setSpillState(SpillState.NoSpillStore);
+                }
+                break;
+
+            case NoSpillStore:
+                assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created";
+                if (defPos < interval.spillDefinitionPos() - 2) {
+                    // second definition found, so no spill optimization possible for this interval
+                    interval.setSpillState(SpillState.NoOptimization);
+                } else {
+                    // two consecutive definitions (because of two-operand LIR form)
+                    assert allocator.blockForId(defPos) == allocator.blockForId(interval.spillDefinitionPos()) : "block must be equal";
+                }
+                break;
+
+            case NoOptimization:
+                // nothing to do
+                break;
+
+            default:
+                throw new BailoutException("other states not allowed at this time");
+        }
+    }
+
+    @Override
+    protected void buildIntervals() {
+        super.buildIntervals();
+        for (Interval interval : allocator.intervals()) {
+            if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) {
+                // there was a definition in a phi/sigma
+                interval.setSpillState(SpillState.NoSpillStore);
+            }
+        }
+    }
+
+    @Override
+    protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) {
+        if (op instanceof LabelOp) {
+            LabelOp label = (LabelOp) op;
+            if (label.id() != 0) {
+                // skip method header
+                return RegisterPriority.None;
+            }
+        }
+        return super.registerPriorityOfOutputOperand(op);
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScanResolveDataFlowPhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScanResolveDataFlowPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,128 @@
+/*
+ * 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.alloc.lsra.ssi;
+
+import static jdk.internal.jvmci.code.ValueUtil.*;
+
+import java.util.*;
+
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.compiler.common.*;
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.alloc.lsra.*;
+import com.oracle.graal.lir.ssa.SSAUtil.PhiValueVisitor;
+import com.oracle.graal.lir.ssi.*;
+
+public class SSILinearScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase {
+
+    private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]");
+    private static final DebugMetric numStackToStackMoves = Debug.metric("SSI LSRA[numStackToStackMoves]");
+
+    public SSILinearScanResolveDataFlowPhase(LinearScan allocator) {
+        super(allocator);
+    }
+
+    @Override
+    protected void resolveDataFlow() {
+        super.resolveDataFlow();
+        /*
+         * Incoming Values are needed for the RegisterVerifier, otherwise SIGMAs/PHIs where the Out
+         * and In value matches (ie. there is no resolution move) are falsely detected as errors.
+         */
+        for (AbstractBlockBase<?> toBlock : allocator.sortedBlocks()) {
+            if (toBlock.getPredecessorCount() != 0) {
+                SSIUtil.removeIncoming(allocator.getLIR(), toBlock);
+            } else {
+                assert allocator.getLIR().getControlFlowGraph().getStartBlock().equals(toBlock);
+            }
+            SSIUtil.removeOutgoing(allocator.getLIR(), toBlock);
+        }
+    }
+
+    @Override
+    protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) {
+        super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver);
+
+        if (midBlock != null) {
+            HashMap<Value, Value> map = CollectionsFactory.newMap();
+            SSIUtil.forEachValuePair(allocator.getLIR(), midBlock, fromBlock, (to, from) -> map.put(to, from));
+
+            MyPhiValueVisitor visitor = new MyPhiValueVisitor(moveResolver, toBlock, fromBlock);
+            SSIUtil.forEachValuePair(allocator.getLIR(), toBlock, midBlock, (to, from) -> {
+                Value phiOut = isConstant(from) ? from : map.get(from);
+                assert phiOut != null : "No entry for " + from;
+                visitor.visit(to, phiOut);
+            });
+        } else {
+            // default case
+            SSIUtil.forEachValuePair(allocator.getLIR(), toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock));
+        }
+
+    }
+
+    private class MyPhiValueVisitor implements PhiValueVisitor {
+        final MoveResolver moveResolver;
+        final int toId;
+        final int fromId;
+
+        public MyPhiValueVisitor(MoveResolver moveResolver, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock) {
+            this.moveResolver = moveResolver;
+            toId = allocator.getFirstLirInstructionId(toBlock);
+            fromId = allocator.getLastLirInstructionId(fromBlock);
+            assert fromId >= 0;
+        }
+
+        public void visit(Value phiIn, Value phiOut) {
+            assert !isRegister(phiOut) : "Out is a register: " + phiOut;
+            assert !isRegister(phiIn) : "In is a register: " + phiIn;
+            if (Value.ILLEGAL.equals(phiIn)) {
+                // The value not needed in this branch.
+                return;
+            }
+            if (isVirtualStackSlot(phiIn) && isVirtualStackSlot(phiOut) && phiIn.equals(phiOut)) {
+                // no need to handle virtual stack slots
+                return;
+            }
+            Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toId, LIRInstruction.OperandMode.DEF);
+            if (isConstant(phiOut)) {
+                numSSIResolutionMoves.increment();
+                moveResolver.addMapping(phiOut, toInterval);
+            } else {
+                Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), fromId, LIRInstruction.OperandMode.DEF);
+                if (fromInterval != toInterval) {
+                    numSSIResolutionMoves.increment();
+                    if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) {
+                        moveResolver.addMapping(fromInterval, toInterval);
+                    } else {
+                        numStackToStackMoves.increment();
+                        moveResolver.addMapping(fromInterval, toInterval);
+                    }
+                }
+            }
+        }
+    }
+
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceGlobalMoveResolver.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceGlobalMoveResolver.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,408 @@
+/*
+ * Copyright (c) 2009, 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.alloc.trace;
+
+import static jdk.internal.jvmci.code.ValueUtil.*;
+
+import java.util.*;
+
+import jdk.internal.jvmci.code.*;
+import jdk.internal.jvmci.common.*;
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.debug.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.alloc.lsra.*;
+import com.oracle.graal.lir.framemap.*;
+import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
+
+/**
+ */
+class TraceGlobalMoveResolver {
+
+    private int insertIdx;
+    private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted
+
+    private final List<Value> mappingFrom;
+    private final List<AllocatableValue> mappingTo;
+    private final int[] registerBlocked;
+    private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1;
+    private int[] stackBlocked;
+    private final int firstVirtualStackIndex;
+    private final SpillMoveFactory spillMoveFactory;
+    private final FrameMapBuilder frameMapBuilder;
+
+    private void setValueBlocked(Value location, int direction) {
+        assert direction == 1 || direction == -1 : "out of bounds";
+        if (isStackSlotValue(location)) {
+            int stackIdx = getStackArrayIndex(asStackSlotValue(location));
+            if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
+                // incoming stack arguments can be ignored
+                return;
+            }
+            if (stackIdx >= stackBlocked.length) {
+                stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1);
+            }
+            stackBlocked[stackIdx] += direction;
+        } else {
+            assert direction == 1 || direction == -1 : "out of bounds";
+            if (isRegister(location)) {
+                registerBlocked[asRegister(location).number] += direction;
+            } else {
+                throw JVMCIError.shouldNotReachHere("unhandled value " + location);
+            }
+        }
+    }
+
+    private int valueBlocked(Value location) {
+        if (isStackSlotValue(location)) {
+            int stackIdx = getStackArrayIndex(asStackSlotValue(location));
+            if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) {
+                // incoming stack arguments are always blocked (aka they can not be written)
+                return 1;
+            }
+            if (stackIdx >= stackBlocked.length) {
+                return 0;
+            }
+            return stackBlocked[stackIdx];
+        }
+        if (isRegister(location)) {
+            return registerBlocked[asRegister(location).number];
+        }
+        throw JVMCIError.shouldNotReachHere("unhandled value " + location);
+    }
+
+    private static boolean areMultipleReadsAllowed() {
+        return true;
+    }
+
+    private boolean hasMappings() {
+        return mappingFrom.size() > 0;
+    }
+
+    private SpillMoveFactory getSpillMoveFactory() {
+        return spillMoveFactory;
+    }
+
+    private Register[] getRegisters() {
+        return frameMapBuilder.getRegisterConfig().getAllocatableRegisters();
+    }
+
+    public TraceGlobalMoveResolver(LIRGenerationResult res, SpillMoveFactory spillMoveFactory, Architecture arch) {
+
+        this.mappingFrom = new ArrayList<>(8);
+        this.mappingTo = new ArrayList<>(8);
+        this.insertIdx = -1;
+        this.insertionBuffer = new LIRInsertionBuffer();
+
+        this.frameMapBuilder = res.getFrameMapBuilder();
+        this.spillMoveFactory = spillMoveFactory;
+        this.registerBlocked = new int[arch.getRegisters().length];
+
+        FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) frameMapBuilder;
+        this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()];
+
+        FrameMap frameMap = frameMapBuilderTool.getFrameMap();
+        this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1;
+    }
+
+    private boolean checkEmpty() {
+        for (int i = 0; i < stackBlocked.length; i++) {
+            assert stackBlocked[i] == 0 : "stack map must be empty before and after processing";
+        }
+        assert mappingFrom.size() == 0 && mappingTo.size() == 0 : "list must be empty before and after processing";
+        for (int i = 0; i < getRegisters().length; i++) {
+            assert registerBlocked[i] == 0 : "register map must be empty before and after processing";
+        }
+        return true;
+    }
+
+    private boolean verifyBeforeResolve() {
+        assert mappingFrom.size() == mappingTo.size() : "length must be equal";
+        assert insertIdx != -1 : "insert position not set";
+
+        int i;
+        int j;
+        if (!areMultipleReadsAllowed()) {
+            for (i = 0; i < mappingFrom.size(); i++) {
+                for (j = i + 1; j < mappingFrom.size(); j++) {
+                    assert mappingFrom.get(i) == null || mappingFrom.get(i) != mappingFrom.get(j) : "cannot read from same interval twice";
+                }
+            }
+        }
+
+        for (i = 0; i < mappingTo.size(); i++) {
+            for (j = i + 1; j < mappingTo.size(); j++) {
+                assert mappingTo.get(i) != mappingTo.get(j) : "cannot write to same interval twice";
+            }
+        }
+
+        for (i = 0; i < mappingTo.size(); i++) {
+            Value to = mappingTo.get(i);
+            assert !isStackSlotValue(to) || getStackArrayIndex(asStackSlotValue(to)) != STACK_SLOT_IN_CALLER_FRAME_IDX : "Cannot move to in argument: " + to;
+        }
+
+        HashSet<Value> usedRegs = new HashSet<>();
+        if (!areMultipleReadsAllowed()) {
+            for (i = 0; i < mappingFrom.size(); i++) {
+                Value from = mappingFrom.get(i);
+                if (from != null && !isIllegal(from)) {
+                    boolean unique = usedRegs.add(from);
+                    assert unique : "cannot read from same register twice";
+                }
+            }
+        }
+
+        usedRegs.clear();
+        for (i = 0; i < mappingTo.size(); i++) {
+            Value to = mappingTo.get(i);
+            if (isIllegal(to)) {
+                // After insertion the location may become illegal, so don't check it since multiple
+                // intervals might be illegal.
+                continue;
+            }
+            boolean unique = usedRegs.add(to);
+            assert unique : "cannot write to same register twice";
+        }
+
+        return true;
+    }
+
+    // mark assignedReg and assignedRegHi of the interval as blocked
+    private void block(Value location) {
+        if (mightBeBlocked(location)) {
+            assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location;
+            setValueBlocked(location, 1);
+            Debug.log("block %s", location);
+        }
+    }
+
+    // mark assignedReg and assignedRegHi of the interval as unblocked
+    private void unblock(Value location) {
+        if (mightBeBlocked(location)) {
+            assert valueBlocked(location) > 0 : "location already marked as unused: " + location;
+            setValueBlocked(location, -1);
+            Debug.log("unblock %s", location);
+        }
+    }
+
+    /**
+     * Checks if the {@linkplain Interval#location() location} of {@code to} is not blocked or is
+     * only blocked by {@code from}.
+     */
+    private boolean safeToProcessMove(Value fromLocation, Value toLocation) {
+        if (mightBeBlocked(toLocation)) {
+            if ((valueBlocked(toLocation) > 1 || (valueBlocked(toLocation) == 1 && !isMoveToSelf(fromLocation, toLocation)))) {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+    public static boolean isMoveToSelf(Value from, Value to) {
+        assert to != null;
+        if (to.equals(from)) {
+            return true;
+        }
+        if (from != null && isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) {
+            assert LIRKind.verifyMoveKinds(to.getLIRKind(), from.getLIRKind()) : String.format("Same register but Kind mismatch %s <- %s", to, from);
+            return true;
+        }
+        return false;
+    }
+
+    private static boolean mightBeBlocked(Value location) {
+        return isRegister(location) || isStackSlotValue(location);
+    }
+
+    private void createInsertionBuffer(List<LIRInstruction> list) {
+        assert !insertionBuffer.initialized() : "overwriting existing buffer";
+        insertionBuffer.init(list);
+    }
+
+    private void appendInsertionBuffer() {
+        if (insertionBuffer.initialized()) {
+            insertionBuffer.finish();
+        }
+        assert !insertionBuffer.initialized() : "must be uninitialized now";
+
+        insertIdx = -1;
+    }
+
+    private void insertMove(Value fromOperand, AllocatableValue toOperand) {
+        assert !fromOperand.equals(toOperand) : "from and to are equal: " + fromOperand + " vs. " + toOperand;
+        assert LIRKind.verifyMoveKinds(fromOperand.getLIRKind(), fromOperand.getLIRKind()) : "move between different types";
+        assert insertIdx != -1 : "must setup insert position first";
+
+        insertionBuffer.append(insertIdx, createMove(fromOperand, toOperand));
+
+        if (Debug.isLogEnabled()) {
+            Debug.log("insert move from %s to %s at %d", fromOperand, toOperand, insertIdx);
+        }
+    }
+
+    /**
+     * @param fromOpr {@link Interval#operand operand} of the {@code from} interval
+     * @param toOpr {@link Interval#operand operand} of the {@code to} interval
+     */
+    private LIRInstruction createMove(Value fromOpr, AllocatableValue toOpr) {
+        if (isStackSlotValue(toOpr) && isStackSlotValue(fromOpr)) {
+            return getSpillMoveFactory().createStackMove(toOpr, fromOpr);
+        }
+        return getSpillMoveFactory().createMove(toOpr, fromOpr);
+    }
+
+    private void resolveMappings() {
+        try (Indent indent = Debug.logAndIndent("resolveMapping")) {
+            assert verifyBeforeResolve();
+            if (Debug.isLogEnabled()) {
+                printMapping();
+            }
+
+            // Block all registers that are used as input operands of a move.
+            // When a register is blocked, no move to this register is emitted.
+            // This is necessary for detecting cycles in moves.
+            for (int i = mappingFrom.size() - 1; i >= 0; i--) {
+                Value from = mappingFrom.get(i);
+                block(from);
+            }
+
+            int spillCandidate = -1;
+            while (mappingFrom.size() > 0) {
+                boolean processedInterval = false;
+
+                for (int i = mappingFrom.size() - 1; i >= 0; i--) {
+                    Value fromInterval = mappingFrom.get(i);
+                    AllocatableValue toInterval = mappingTo.get(i);
+
+                    Value fromLocation = fromInterval;
+                    AllocatableValue toLocation = toInterval;
+                    if (safeToProcessMove(fromLocation, toLocation)) {
+                        // this interval can be processed because target is free
+                        insertMove(fromLocation, toLocation);
+                        unblock(fromLocation);
+                        mappingFrom.remove(i);
+                        mappingTo.remove(i);
+
+                        processedInterval = true;
+                    } else if (fromInterval != null && isRegister(fromLocation)) {
+                        // this interval cannot be processed now because target is not free
+                        // it starts in a register, so it is a possible candidate for spilling
+                        spillCandidate = i;
+                    }
+                }
+
+                if (!processedInterval) {
+                    breakCycle(spillCandidate);
+                }
+            }
+        }
+
+        // check that all intervals have been processed
+        assert checkEmpty();
+    }
+
+    private void breakCycle(int spillCandidate) {
+        // no move could be processed because there is a cycle in the move list
+        // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory
+        assert spillCandidate != -1 : "no interval in register for spilling found";
+
+        // create a new spill interval and assign a stack slot to it
+        Value from = mappingFrom.get(spillCandidate);
+        try (Indent indent = Debug.logAndIndent("BreakCycle: %s", from)) {
+            StackSlotValue spillSlot = frameMapBuilder.allocateSpillSlot(from.getLIRKind());
+            if (Debug.isLogEnabled()) {
+                Debug.log("created new slot for spilling: %s", spillSlot);
+            }
+            // insert a move from register to stack and update the mapping
+            insertMove(from, spillSlot);
+            block(spillSlot);
+            mappingFrom.set(spillCandidate, spillSlot);
+            unblock(from);
+        }
+    }
+
+    private void printMapping() {
+        try (Indent indent = Debug.logAndIndent("Mapping")) {
+            for (int i = mappingFrom.size() - 1; i >= 0; i--) {
+                Debug.log("move %s <- %s", mappingTo.get(i), mappingFrom.get(i));
+            }
+        }
+    }
+
+    public void setInsertPosition(List<LIRInstruction> insertList, int insertIdx) {
+        assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set";
+
+        createInsertionBuffer(insertList);
+        this.insertIdx = insertIdx;
+    }
+
+    public void addMapping(Value from, AllocatableValue to) {
+        if (Debug.isLogEnabled()) {
+            Debug.log("add move mapping from %s to %s", from, to);
+        }
+
+        assert !from.equals(to) : "from and to interval equal: " + from;
+        assert LIRKind.verifyMoveKinds(to.getLIRKind(), from.getLIRKind()) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", from.getLIRKind(), to.getLIRKind(), from, to);
+        mappingFrom.add(from);
+        mappingTo.add(to);
+    }
+
+    public void resolveAndAppendMoves() {
+        if (hasMappings()) {
+            resolveMappings();
+        }
+        appendInsertionBuffer();
+    }
+
+    private int getStackArrayIndex(StackSlotValue stackSlotValue) {
+        if (isStackSlot(stackSlotValue)) {
+            return getStackArrayIndex(asStackSlot(stackSlotValue));
+        }
+        if (isVirtualStackSlot(stackSlotValue)) {
+            return getStackArrayIndex(asVirtualStackSlot(stackSlotValue));
+        }
+        throw JVMCIError.shouldNotReachHere("Unhandled StackSlotValue: " + stackSlotValue);
+    }
+
+    private int getStackArrayIndex(StackSlot stackSlot) {
+        int stackIdx;
+        if (stackSlot.isInCallerFrame()) {
+            // incoming stack arguments can be ignored
+            stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX;
+        } else {
+            assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot;
+            int offset = -stackSlot.getRawOffset();
+            assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex);
+            stackIdx = offset;
+        }
+        return stackIdx;
+    }
+
+    private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) {
+        return firstVirtualStackIndex + virtualStackSlot.getId();
+    }
+
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,126 @@
+/*
+ * 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.alloc.trace;
+
+import static com.oracle.graal.compiler.common.GraalOptions.*;
+
+import java.util.*;
+
+import jdk.internal.jvmci.code.*;
+
+import com.oracle.graal.compiler.common.alloc.*;
+import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult;
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.debug.Debug.Scope;
+import com.oracle.graal.lir.alloc.lsra.*;
+import com.oracle.graal.lir.alloc.lsra.ssa.*;
+import com.oracle.graal.lir.alloc.lsra.ssi.*;
+import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
+import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext;
+
+public final class TraceLinearScan extends LinearScan {
+
+    private final TraceBuilderResult<?> traceBuilderResult;
+
+    public TraceLinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig,
+                    List<? extends AbstractBlockBase<?>> sortedBlocks, TraceBuilderResult<?> traceBuilderResult) {
+        super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks);
+        this.traceBuilderResult = traceBuilderResult;
+    }
+
+    @Override
+    protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder,
+                    SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) {
+
+        /*
+         * This is the point to enable debug logging for the whole register allocation.
+         */
+        try (Indent indent = Debug.logAndIndent("LinearScan allocate")) {
+            AllocationContext context = new AllocationContext(spillMoveFactory, registerAllocationConfig);
+
+            createLifetimeAnalysisPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
+
+            try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals())) {
+                sortIntervalsBeforeAllocation();
+
+                createRegisterAllocationPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
+
+                if (LinearScan.Options.LSRAOptimizeSpillPosition.getValue()) {
+                    createOptimizeSpillPositionPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
+                }
+                // resolve intra-trace data-flow
+                LinearScanResolveDataFlowPhase dataFlowPhase = createResolveDataFlowPhase();
+                dataFlowPhase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
+                Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks(), "%s", dataFlowPhase.getName());
+
+                LinearScanAssignLocationsPhase assignPhase = createAssignLocationsPhase();
+                assignPhase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
+
+                if (DetailedAsserts.getValue()) {
+                    verifyIntervals();
+                }
+            } catch (Throwable e) {
+                throw Debug.handle(e);
+            }
+        }
+    }
+
+    @Override
+    protected MoveResolver createMoveResolver() {
+        SSAMoveResolver moveResolver = new SSAMoveResolver(this);
+        assert moveResolver.checkEmpty();
+        return moveResolver;
+    }
+
+    @Override
+    protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() {
+        return new TraceLinearScanLifetimeAnalysisPhase(this, traceBuilderResult);
+    }
+
+    @Override
+    protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() {
+        return new TraceLinearScanResolveDataFlowPhase(this);
+    }
+
+    @Override
+    protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() {
+        return new SSILinearScanEliminateSpillMovePhase(this);
+    }
+
+    @Override
+    protected void printIntervals(String label) {
+        if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) {
+            super.printIntervals(label);
+        }
+    }
+
+    @Override
+    protected void printLir(String label, boolean hirValid) {
+        if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) {
+            Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks(), label);
+        }
+    }
+
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,286 @@
+/*
+ * 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.alloc.trace;
+
+import static com.oracle.graal.compiler.common.GraalOptions.*;
+import static com.oracle.graal.lir.LIRValueUtil.*;
+import static com.oracle.graal.lir.alloc.trace.TraceRegisterAllocationPhase.Options.*;
+import static jdk.internal.jvmci.code.ValueUtil.*;
+
+import java.util.*;
+
+import jdk.internal.jvmci.code.*;
+import jdk.internal.jvmci.common.*;
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult;
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.StandardOp.BlockEndOp;
+import com.oracle.graal.lir.StandardOp.LabelOp;
+import com.oracle.graal.lir.StandardOp.MoveOp;
+import com.oracle.graal.lir.alloc.lsra.*;
+import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority;
+import com.oracle.graal.lir.alloc.lsra.Interval.SpillState;
+import com.oracle.graal.lir.alloc.lsra.LinearScan.BlockData;
+import com.oracle.graal.lir.ssi.*;
+
+public class TraceLinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase {
+
+    private final TraceBuilderResult<?> traceBuilderResult;
+
+    public TraceLinearScanLifetimeAnalysisPhase(LinearScan linearScan, TraceBuilderResult<?> traceBuilderResult) {
+        super(linearScan);
+        this.traceBuilderResult = traceBuilderResult;
+    }
+
+    private boolean sameTrace(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
+        return traceBuilderResult.getTraceForBlock(b) == traceBuilderResult.getTraceForBlock(a);
+    }
+
+    private boolean isAllocatedOrCurrent(AbstractBlockBase<?> currentBlock, AbstractBlockBase<?> other) {
+        return traceBuilderResult.getTraceForBlock(other) <= traceBuilderResult.getTraceForBlock(currentBlock);
+    }
+
+    static void setHint(final LIRInstruction op, Interval target, Interval source) {
+        Interval currentHint = target.locationHint(false);
+        if (currentHint == null || currentHint.from() > target.from()) {
+            /*
+             * Update hint if there was none or if the hint interval starts after the hinted
+             * interval.
+             */
+            target.setLocationHint(source);
+            if (Debug.isLogEnabled()) {
+                Debug.log("operation at opId %d: added hint from interval %d (%s) to %d (%s)", op.id(), source.operandNumber, source, target.operandNumber, target);
+            }
+        }
+    }
+
+    @Override
+    protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, Interval interval, int defPos) {
+        assert interval.isSplitParent() : "can only be called for split parents";
+
+        switch (interval.spillState()) {
+            case NoDefinitionFound:
+                // assert interval.spillDefinitionPos() == -1 : "must no be set before";
+                interval.setSpillDefinitionPos(defPos);
+                if (!(op instanceof LabelOp)) {
+                    // Do not update state for labels. This will be done afterwards.
+                    interval.setSpillState(SpillState.NoSpillStore);
+                }
+                break;
+
+            case NoSpillStore:
+                assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created";
+                if (defPos < interval.spillDefinitionPos() - 2) {
+                    // second definition found, so no spill optimization possible for this interval
+                    interval.setSpillState(SpillState.NoOptimization);
+                } else {
+                    // two consecutive definitions (because of two-operand LIR form)
+                    assert allocator.blockForId(defPos) == allocator.blockForId(interval.spillDefinitionPos()) : "block must be equal";
+                }
+                break;
+
+            case NoOptimization:
+                // nothing to do
+                break;
+
+            default:
+                throw new BailoutException("other states not allowed at this time");
+        }
+    }
+
+    @Override
+    protected void buildIntervals() {
+        super.buildIntervals();
+        // fix spill state for phi/sigma intervals
+        for (Interval interval : allocator.intervals()) {
+            if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) {
+                // there was a definition in a phi/sigma
+                interval.setSpillState(SpillState.NoSpillStore);
+            }
+        }
+        if (TraceRAuseInterTraceHints.getValue()) {
+            addInterTraceHints();
+        }
+    }
+
+    private void addInterTraceHints() {
+        // set hints for phi/sigma intervals
+        LIR lir = allocator.getLIR();
+        for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
+            LabelOp label = SSIUtil.incoming(lir, block);
+            for (AbstractBlockBase<?> pred : block.getPredecessors()) {
+                if (isAllocatedOrCurrent(block, pred)) {
+                    BlockEndOp outgoing = SSIUtil.outgoing(lir, pred);
+                    for (int i = 0; i < outgoing.getOutgoingSize(); i++) {
+                        Value toValue = label.getIncomingValue(i);
+                        if (!isIllegal(toValue)) {
+                            Value fromValue = outgoing.getOutgoingValue(i);
+                            assert sameTrace(block, pred) || !isVariable(fromValue) : "Unallocated variable: " + fromValue;
+
+                            if (!isStackSlotValue(fromValue) && !isConstant(fromValue)) {
+                                Interval from = allocator.getOrCreateInterval((AllocatableValue) fromValue);
+                                Interval to = allocator.getOrCreateInterval((AllocatableValue) toValue);
+                                setHint(label, to, from);
+                            }
+                        }
+                    }
+                }
+            }
+        }
+        /*
+         * Set the first range for fixed intervals to [-1, 0] to avoid intersection with incoming
+         * values.
+         */
+        for (Interval interval : allocator.intervals()) {
+            if (interval != null && isRegister(interval.operand)) {
+                Range range = interval.first();
+                if (range == Range.EndMarker) {
+                    interval.addRange(-1, 0);
+                } else if (range.from == 0 && range.to == 1) {
+                    range.from = -1;
+                    range.to = 0;
+                }
+            }
+        }
+    }
+
+    @Override
+    protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) {
+        if (op instanceof LabelOp) {
+            // skip method header
+            return RegisterPriority.None;
+        }
+        return super.registerPriorityOfOutputOperand(op);
+    }
+
+    @Override
+    protected void handleMethodArguments(LIRInstruction op) {
+        if (op instanceof MoveOp) {
+            // do not optimize method arguments
+            return;
+        }
+        super.handleMethodArguments(op);
+    }
+
+    /**
+     * Performs a backward dataflow analysis to compute global live sets (i.e.
+     * {@link BlockData#liveIn} and {@link BlockData#liveOut}) for each block.
+     */
+    @Override
+    protected void computeGlobalLiveSets() {
+        try (Indent indent = Debug.logAndIndent("compute global live sets")) {
+            int numBlocks = allocator.blockCount();
+            boolean changeOccurred;
+            boolean changeOccurredInBlock;
+            int iterationCount = 0;
+            BitSet liveOut = new BitSet(allocator.liveSetSize()); // scratch set for calculations
+
+            /*
+             * Perform a backward dataflow analysis to compute liveOut and liveIn for each block.
+             * The loop is executed until a fixpoint is reached (no changes in an iteration).
+             */
+            do {
+                changeOccurred = false;
+
+                try (Indent indent2 = Debug.logAndIndent("new iteration %d", iterationCount)) {
+
+                    // iterate all blocks in reverse order
+                    for (int i = numBlocks - 1; i >= 0; i--) {
+                        AbstractBlockBase<?> block = allocator.blockAt(i);
+                        BlockData blockSets = allocator.getBlockData(block);
+
+                        changeOccurredInBlock = false;
+
+                        /* liveOut(block) is the union of liveIn(sux), for successors sux of block. */
+                        int n = block.getSuccessorCount();
+                        if (n > 0) {
+                            liveOut.clear();
+                            // block has successors
+                            if (n > 0) {
+                                for (AbstractBlockBase<?> successor : block.getSuccessors()) {
+                                    if (allocator.sortedBlocks().contains(successor)) {
+                                        liveOut.or(allocator.getBlockData(successor).liveIn);
+                                    }
+                                }
+                            }
+
+                            if (!blockSets.liveOut.equals(liveOut)) {
+                                /*
+                                 * A change occurred. Swap the old and new live out sets to avoid
+                                 * copying.
+                                 */
+                                BitSet temp = blockSets.liveOut;
+                                blockSets.liveOut = liveOut;
+                                liveOut = temp;
+
+                                changeOccurred = true;
+                                changeOccurredInBlock = true;
+                            }
+                        }
+
+                        if (iterationCount == 0 || changeOccurredInBlock) {
+                            /*
+                             * liveIn(block) is the union of liveGen(block) with (liveOut(block) &
+                             * !liveKill(block)).
+                             *
+                             * Note: liveIn has to be computed only in first iteration or if liveOut
+                             * has changed!
+                             */
+                            BitSet liveIn = blockSets.liveIn;
+                            liveIn.clear();
+                            liveIn.or(blockSets.liveOut);
+                            liveIn.andNot(blockSets.liveKill);
+                            liveIn.or(blockSets.liveGen);
+
+                            if (Debug.isLogEnabled()) {
+                                Debug.log("block %d: livein = %s,  liveout = %s", block.getId(), liveIn, blockSets.liveOut);
+                            }
+                        }
+                    }
+                    iterationCount++;
+
+                    if (changeOccurred && iterationCount > 50) {
+                        throw new BailoutException("too many iterations in computeGlobalLiveSets");
+                    }
+                }
+            } while (changeOccurred);
+
+            if (DetailedAsserts.getValue()) {
+                verifyLiveness();
+            }
+
+            // check that the liveIn set of the first block is empty
+            AbstractBlockBase<?> startBlock = allocator.blockAt(0);
+            if (allocator.getBlockData(startBlock).liveIn.cardinality() != 0) {
+                if (DetailedAsserts.getValue()) {
+                    reportFailure(numBlocks);
+                }
+                // bailout if this occurs in product mode.
+                throw new JVMCIError("liveIn set of first block must be empty: " + allocator.getBlockData(startBlock).liveIn);
+            }
+        }
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,108 @@
+/*
+ * 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.alloc.trace;
+
+import static jdk.internal.jvmci.code.ValueUtil.*;
+
+import java.util.*;
+
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.alloc.lsra.*;
+import com.oracle.graal.lir.ssa.SSAUtil.PhiValueVisitor;
+import com.oracle.graal.lir.ssi.*;
+
+public class TraceLinearScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase {
+
+    private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]");
+    private static final DebugMetric numStackToStackMoves = Debug.metric("SSI LSRA[numStackToStackMoves]");
+
+    public TraceLinearScanResolveDataFlowPhase(LinearScan allocator) {
+        super(allocator);
+    }
+
+    @Override
+    protected void optimizeEmptyBlocks(MoveResolver moveResolver, BitSet blockCompleted) {
+        // do not optimize
+    }
+
+    @Override
+    protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) {
+        assert midBlock == null;
+        if (containedInTrace(fromBlock) && containedInTrace(toBlock)) {
+            super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver);
+            SSIUtil.forEachValuePair(allocator.getLIR(), toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock));
+        }
+
+    }
+
+    private boolean containedInTrace(AbstractBlockBase<?> block) {
+        return allocator.sortedBlocks().contains(block);
+    }
+
+    private class MyPhiValueVisitor implements PhiValueVisitor {
+        final MoveResolver moveResolver;
+        final int toId;
+        final int fromId;
+
+        public MyPhiValueVisitor(MoveResolver moveResolver, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock) {
+            this.moveResolver = moveResolver;
+            toId = allocator.getFirstLirInstructionId(toBlock);
+            fromId = allocator.getLastLirInstructionId(fromBlock);
+            assert fromId >= 0;
+        }
+
+        public void visit(Value phiIn, Value phiOut) {
+            assert !isRegister(phiOut) : "Out is a register: " + phiOut;
+            assert !isRegister(phiIn) : "In is a register: " + phiIn;
+            if (Value.ILLEGAL.equals(phiIn)) {
+                // The value not needed in this branch.
+                return;
+            }
+            if (isVirtualStackSlot(phiIn) && isVirtualStackSlot(phiOut) && phiIn.equals(phiOut)) {
+                // no need to handle virtual stack slots
+                return;
+            }
+            Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toId, LIRInstruction.OperandMode.DEF);
+            if (isConstant(phiOut)) {
+                numSSIResolutionMoves.increment();
+                moveResolver.addMapping(phiOut, toInterval);
+            } else {
+                Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), fromId, LIRInstruction.OperandMode.DEF);
+                if (fromInterval != toInterval) {
+                    numSSIResolutionMoves.increment();
+                    if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) {
+                        moveResolver.addMapping(fromInterval, toInterval);
+                    } else {
+                        numStackToStackMoves.increment();
+                        moveResolver.addMapping(fromInterval, toInterval);
+                    }
+                }
+            }
+        }
+    }
+
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceRegisterAllocationPhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceRegisterAllocationPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,168 @@
+/*
+ * 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.alloc.trace;
+
+import static jdk.internal.jvmci.code.ValueUtil.*;
+
+import java.util.*;
+
+import jdk.internal.jvmci.code.*;
+import jdk.internal.jvmci.meta.*;
+import jdk.internal.jvmci.options.*;
+
+import com.oracle.graal.compiler.common.alloc.*;
+import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult;
+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.StandardOp.MoveOp;
+import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
+import com.oracle.graal.lir.phases.*;
+import com.oracle.graal.lir.ssa.SSAUtil.PhiValueVisitor;
+import com.oracle.graal.lir.ssi.*;
+
+public class TraceRegisterAllocationPhase extends AllocationPhase {
+    public static class Options {
+        // @formatter:off
+        @Option(help = "Use inter-trace register hints.", type = OptionType.Debug)
+        public static final OptionValue<Boolean> TraceRAuseInterTraceHints = new OptionValue<>(true);
+        // @formatter:on
+    }
+
+    static final int TRACE_DUMP_LEVEL = 3;
+
+    @Override
+    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory,
+                    RegisterAllocationConfig registerAllocationConfig) {
+        LIR lir = lirGenRes.getLIR();
+        assert SSIVerifier.verify(lir) : "LIR not in SSI form.";
+        B startBlock = linearScanOrder.get(0);
+        assert startBlock.equals(lir.getControlFlowGraph().getStartBlock());
+        TraceBuilderResult<B> resultTraces = TraceBuilder.computeTraces(startBlock, linearScanOrder);
+
+        Debug.dump(lir, "Before TraceRegisterAllocation");
+        int traceNumber = 0;
+        for (List<B> trace : resultTraces.getTraces()) {
+            try (Indent i = Debug.logAndIndent("Allocating Trace%d: %s", traceNumber, trace); Scope s = Debug.scope("AllocateTrace", trace)) {
+                Debug.dump(TRACE_DUMP_LEVEL, trace, "Trace" + traceNumber + ": " + trace);
+                TraceLinearScan allocator = new TraceLinearScan(target, lirGenRes, spillMoveFactory, registerAllocationConfig, trace, resultTraces);
+                allocator.allocate(target, lirGenRes, codeEmittingOrder, linearScanOrder, spillMoveFactory, registerAllocationConfig);
+                Debug.dump(TRACE_DUMP_LEVEL, trace, "After Trace" + traceNumber + ": " + trace);
+                traceNumber++;
+            } catch (Throwable e) {
+                throw Debug.handle(e);
+            }
+            unnumberInstructions(trace, lir);
+        }
+        Debug.dump(lir, "After trace allocation");
+
+        resolveGlobalDataFlow(resultTraces, lirGenRes, spillMoveFactory, target.arch);
+        Debug.dump(lir, "After global dataflow resolution");
+
+        if (replaceStackToStackMoves(lir, spillMoveFactory)) {
+            Debug.dump(lir, "After fixing stack to stack moves");
+        }
+        /*
+         * Incoming Values are needed for the RegisterVerifier, otherwise SIGMAs/PHIs where the Out
+         * and In value matches (ie. there is no resolution move) are falsely detected as errors.
+         */
+        for (AbstractBlockBase<?> toBlock : lir.getControlFlowGraph().getBlocks()) {
+            if (toBlock.getPredecessorCount() != 0) {
+                SSIUtil.removeIncoming(lir, toBlock);
+            } else {
+                assert lir.getControlFlowGraph().getStartBlock().equals(toBlock);
+            }
+            SSIUtil.removeOutgoing(lir, toBlock);
+        }
+    }
+
+    /**
+     * Fixup stack to stack moves introduced by stack arguments.
+     *
+     * TODO (je) find a better solution.
+     */
+    private static boolean replaceStackToStackMoves(LIR lir, SpillMoveFactory spillMoveFactory) {
+        boolean changed = false;
+        for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
+            List<LIRInstruction> instructions = lir.getLIRforBlock(block);
+            for (int i = 0; i < instructions.size(); i++) {
+                LIRInstruction inst = instructions.get(i);
+
+                if (inst instanceof MoveOp) {
+                    MoveOp move = (MoveOp) inst;
+                    if (isStackSlotValue(move.getInput()) && isStackSlotValue(move.getResult())) {
+                        instructions.set(i, spillMoveFactory.createStackMove(move.getResult(), move.getInput()));
+                        changed = true;
+                    }
+                }
+            }
+        }
+        return changed;
+    }
+
+    private static <B extends AbstractBlockBase<B>> void resolveGlobalDataFlow(TraceBuilderResult<B> resultTraces, LIRGenerationResult lirGenRes, SpillMoveFactory spillMoveFactory, Architecture arch) {
+        LIR lir = lirGenRes.getLIR();
+        /* Resolve trace global data-flow mismatch. */
+        TraceGlobalMoveResolver moveResolver = new TraceGlobalMoveResolver(lirGenRes, spillMoveFactory, arch);
+        PhiValueVisitor visitor = (Value phiIn, Value phiOut) -> {
+            if (!isIllegal(phiIn) && !TraceGlobalMoveResolver.isMoveToSelf(phiOut, phiIn)) {
+                moveResolver.addMapping(phiOut, (AllocatableValue) phiIn);
+            }
+        };
+
+        try (Indent indent = Debug.logAndIndent("Trace global move resolution")) {
+            for (List<B> trace : resultTraces.getTraces()) {
+                for (AbstractBlockBase<?> fromBlock : trace) {
+                    for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) {
+                        if (resultTraces.getTraceForBlock(fromBlock) != resultTraces.getTraceForBlock(toBlock)) {
+                            try (Indent indent0 = Debug.logAndIndent("Handle trace edge from %s (Trace%d) to %s (Trace%d)", fromBlock, resultTraces.getTraceForBlock(fromBlock), toBlock,
+                                            resultTraces.getTraceForBlock(toBlock))) {
+
+                                final List<LIRInstruction> instructions;
+                                final int insertIdx;
+                                if (fromBlock.getSuccessorCount() == 1) {
+                                    instructions = lir.getLIRforBlock(fromBlock);
+                                    insertIdx = instructions.size() - 1;
+                                } else {
+                                    assert toBlock.getPredecessorCount() == 1;
+                                    instructions = lir.getLIRforBlock(toBlock);
+                                    insertIdx = 1;
+                                }
+
+                                moveResolver.setInsertPosition(instructions, insertIdx);
+                                SSIUtil.forEachValuePair(lir, toBlock, fromBlock, visitor);
+                                moveResolver.resolveAndAppendMoves();
+                            }
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    private static void unnumberInstructions(List<? extends AbstractBlockBase<?>> trace, LIR lir) {
+        trace.stream().flatMap(b -> lir.getLIRforBlock(b).stream()).forEach(op -> op.setId(-1));
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/dfa/MarkBasePointersPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/dfa/MarkBasePointersPhase.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/dfa/MarkBasePointersPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -51,14 +51,14 @@
 
         private final class BasePointersSet extends ValueSet<Marker<T>.BasePointersSet> {
 
-            private final IntValueMap variables;
+            private final IndexedValueMap variables;
 
             public BasePointersSet() {
-                variables = new IntValueMap();
+                variables = new IndexedValueMap();
             }
 
             private BasePointersSet(BasePointersSet s) {
-                variables = new IntValueMap(s.variables);
+                variables = new IndexedValueMap(s.variables);
             }
 
             @Override
@@ -118,7 +118,7 @@
 
         @Override
         protected void processState(LIRInstruction op, LIRFrameState info, BasePointersSet values) {
-            info.setLiveBasePointers(new IntValueMap(values.variables));
+            info.setLiveBasePointers(new IndexedValueMap(values.variables));
         }
     }
 }
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/dfa/RegStackValueSet.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/dfa/RegStackValueSet.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/dfa/RegStackValueSet.java	Mon Jul 27 16:57:30 2015 -0700
@@ -36,20 +36,20 @@
 final class RegStackValueSet extends ValueSet<RegStackValueSet> {
 
     private final FrameMap frameMap;
-    private final IntValueMap registers;
-    private final IntValueMap stack;
+    private final IndexedValueMap registers;
+    private final IndexedValueMap stack;
     private Set<Value> extraStack;
 
     public RegStackValueSet(FrameMap frameMap) {
         this.frameMap = frameMap;
-        registers = new IntValueMap();
-        stack = new IntValueMap();
+        registers = new IndexedValueMap();
+        stack = new IndexedValueMap();
     }
 
     private RegStackValueSet(FrameMap frameMap, RegStackValueSet s) {
         this.frameMap = frameMap;
-        registers = new IntValueMap(s.registers);
-        stack = new IntValueMap(s.stack);
+        registers = new IndexedValueMap(s.registers);
+        stack = new IndexedValueMap(s.stack);
         if (s.extraStack != null) {
             extraStack = new HashSet<>(s.extraStack);
         }
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/BlockValueMap.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/BlockValueMap.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,35 @@
+/*
+ * 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.gen;
+
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.compiler.common.cfg.*;
+
+public interface BlockValueMap {
+
+    void accessOperand(Value operand, AbstractBlockBase<?> block);
+
+    void defineOperand(Value operand, AbstractBlockBase<?> block);
+
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/AllocationStage.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/AllocationStage.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/AllocationStage.java	Mon Jul 27 16:57:30 2015 -0700
@@ -22,7 +22,10 @@
  */
 package com.oracle.graal.lir.phases;
 
+import static com.oracle.graal.compiler.common.BackendOptions.UserOptions.*;
+
 import com.oracle.graal.lir.alloc.lsra.*;
+import com.oracle.graal.lir.alloc.trace.*;
 import com.oracle.graal.lir.dfa.*;
 import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext;
 import com.oracle.graal.lir.stackslotalloc.*;
@@ -30,7 +33,11 @@
 public class AllocationStage extends LIRPhaseSuite<AllocationContext> {
     public AllocationStage() {
         appendPhase(new MarkBasePointersPhase());
-        appendPhase(new LinearScanPhase());
+        if (TraceRA.getValue()) {
+            appendPhase(new TraceRegisterAllocationPhase());
+        } else {
+            appendPhase(new LinearScanPhase());
+        }
 
         // build frame map
         if (LSStackSlotAllocator.Options.LIROptLSStackSlotAllocator.getValue()) {
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/PreAllocationOptimizationStage.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/PreAllocationOptimizationStage.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/PreAllocationOptimizationStage.java	Mon Jul 27 16:57:30 2015 -0700
@@ -23,11 +23,13 @@
 package com.oracle.graal.lir.phases;
 
 import static com.oracle.graal.compiler.common.GraalOptions.*;
+import static com.oracle.graal.compiler.common.BackendOptions.*;
 
 import com.oracle.graal.compiler.common.*;
 import com.oracle.graal.lir.constopt.*;
 import com.oracle.graal.lir.phases.PreAllocationOptimizationPhase.PreAllocationOptimizationContext;
 import com.oracle.graal.lir.ssa.*;
+import com.oracle.graal.lir.ssi.*;
 
 public class PreAllocationOptimizationStage extends LIRPhaseSuite<PreAllocationOptimizationContext> {
     public PreAllocationOptimizationStage() {
@@ -37,5 +39,8 @@
         if (ConstantLoadOptimization.Options.LIROptConstantLoadOptimization.getValue()) {
             appendPhase(new ConstantLoadOptimization());
         }
+        if (EnableSSIConstruction.getValue()) {
+            appendPhase(new SSIConstructionPhase());
+        }
     }
 }
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/profiling/MoveProfiling.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/profiling/MoveProfiling.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/profiling/MoveProfiling.java	Mon Jul 27 16:57:30 2015 -0700
@@ -51,7 +51,8 @@
         STACK2REG("Reg", "Stack"),
         CONST2REG("Reg", "Const"),
         REG2STACK("Stack", "Reg"),
-        CONST2STACK("Stack", "Const");
+        CONST2STACK("Stack", "Const"),
+        STACK2STACK("Stack", "Stack");
 
         private final String name;
 
@@ -84,6 +85,9 @@
                 if (isConstant(src)) {
                     return CONST2STACK;
                 }
+                if (isStackSlot(src)) {
+                    return STACK2STACK;
+                }
             }
             throw JVMCIError.shouldNotReachHere(String.format("Unrecognized Move: %s dst=%s, src=%s", move, dst, src));
         }
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSADestructionPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSADestructionPhase.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSADestructionPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -48,15 +48,15 @@
 
                 List<LIRInstruction> instructions = lir.getLIRforBlock(pred);
 
-                int insertBefore = SSAUtils.phiOutIndex(lir, pred);
+                int insertBefore = SSAUtil.phiOutIndex(lir, pred);
 
                 PhiResolver resolver = PhiResolver.create(lirGen, new LIRInsertionBuffer(), instructions, insertBefore);
-                SSAUtils.forEachPhiValuePair(lir, block, pred, resolver::move);
+                SSAUtil.forEachPhiValuePair(lir, block, pred, resolver::move);
                 resolver.dispose();
 
-                SSAUtils.removePhiOut(lir, pred);
+                SSAUtil.removePhiOut(lir, pred);
             }
-            SSAUtils.removePhiIn(lir, block);
+            SSAUtil.removePhiIn(lir, block);
         }
     }
 
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSAUtil.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSAUtil.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,176 @@
+/*
+ * 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.ssa;
+
+import java.util.*;
+
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.LIRInstruction.OperandMode;
+import com.oracle.graal.lir.StandardOp.BlockEndOp;
+import com.oracle.graal.lir.StandardOp.JumpOp;
+import com.oracle.graal.lir.StandardOp.LabelOp;
+
+/**
+ * Utilities for working with Static-Single-Assignment LIR form.
+ *
+ * <h2>Representation of <code>PHI</code>s</h2>
+ *
+ * There is no explicit <code>PHI</code> {@linkplain LIRInstruction}. Instead, they are implemented
+ * as parallel copy that span across a control-flow edge.
+ *
+ * The variables introduced by <code>PHI</code>s of a specific {@linkplain AbstractBlockBase merge
+ * block} are {@linkplain LabelOp#setIncomingValues attached} to the {@linkplain LabelOp} of the
+ * block. The outgoing values from the predecessor are {@link JumpOp#setOutgoingValues input} to the
+ * {@linkplain BlockEndOp} of the predecessor. Because there are no critical edges we know that the
+ * {@link BlockEndOp} of the predecessor has to be a {@link JumpOp}.
+ *
+ * <h3>Example:</h3>
+ *
+ * <pre>
+ * B0 -> B1
+ *   ...
+ *   v0|i = ...
+ *   JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1
+ * ________________________________________________
+ * 
+ * B2 -> B1
+ *   ...
+ *   v1|i = ...
+ *   v2|i = ...
+ *   JUMP ~[v1|i, v2|i] destination: B2 -> B1
+ * ________________________________________________
+ * 
+ * B1 <- B0,B2
+ *   [v3|i, v4|i] = LABEL
+ *   ...
+ * </pre>
+ */
+public final class SSAUtil {
+
+    public interface PhiValueVisitor {
+        /**
+         * @param phiIn the incoming value at the merge block
+         * @param phiOut the outgoing value from the predecessor block
+         */
+        void visit(Value phiIn, Value phiOut);
+    }
+
+    /**
+     * Visits each phi value pair of an edge, i.e. the outgoing value from the predecessor and the
+     * incoming value to the merge block.
+     */
+    public static void forEachPhiValuePair(LIR lir, AbstractBlockBase<?> merge, AbstractBlockBase<?> pred, PhiValueVisitor visitor) {
+        if (merge.getPredecessorCount() < 2) {
+            return;
+        }
+        assert merge.getPredecessors().contains(pred) : String.format("%s not in predecessor list: %s", pred, merge.getPredecessors());
+        assert pred.getSuccessorCount() == 1 : String.format("Merge predecessor block %s has more than one successor? %s", pred, pred.getSuccessors());
+        assert pred.getSuccessors().get(0) == merge : String.format("Predecessor block %s has wrong successor: %s, should be: %s", pred, pred.getSuccessors().get(0), merge);
+
+        JumpOp jump = phiOut(lir, pred);
+        LabelOp label = phiIn(lir, merge);
+
+        assert label.getIncomingSize() == jump.getOutgoingSize() : String.format("Phi In/Out size mismatch: in=%d vs. out=%d", label.getIncomingSize(), jump.getOutgoingSize());
+
+        for (int i = 0; i < label.getIncomingSize(); i++) {
+            visitor.visit(label.getIncomingValue(i), jump.getOutgoingValue(i));
+        }
+    }
+
+    private static JumpOp phiOut(LIR lir, AbstractBlockBase<?> block) {
+        assert block.getSuccessorCount() == 1;
+        List<LIRInstruction> instructions = lir.getLIRforBlock(block);
+        int index = instructions.size() - 1;
+        LIRInstruction op = instructions.get(index);
+        return (JumpOp) op;
+    }
+
+    public static int phiOutIndex(LIR lir, AbstractBlockBase<?> block) {
+        assert block.getSuccessorCount() == 1;
+        List<LIRInstruction> instructions = lir.getLIRforBlock(block);
+        int index = instructions.size() - 1;
+        assert instructions.get(index) instanceof JumpOp;
+        return index;
+    }
+
+    private static LabelOp phiIn(LIR lir, AbstractBlockBase<?> block) {
+        assert block.getPredecessorCount() > 1;
+        LabelOp label = (LabelOp) lir.getLIRforBlock(block).get(0);
+        return label;
+    }
+
+    public static void removePhiOut(LIR lir, AbstractBlockBase<?> block) {
+        JumpOp jump = phiOut(lir, block);
+        jump.clearOutgoingValues();
+    }
+
+    public static void removePhiIn(LIR lir, AbstractBlockBase<?> block) {
+        LabelOp label = phiIn(lir, block);
+        label.clearIncomingValues();
+    }
+
+    public static boolean verifySSAForm(LIR lir) {
+        return new SSAVerifier(lir).verify();
+    }
+
+    public static void verifyPhi(LIR lir, AbstractBlockBase<?> merge) {
+        assert merge.getPredecessorCount() > 1;
+        for (AbstractBlockBase<?> pred : merge.getPredecessors()) {
+            forEachPhiValuePair(lir, merge, pred, (phiIn, phiOut) -> {
+                assert phiIn.getLIRKind().equals(phiOut.getLIRKind()) ||
+                                (phiIn.getPlatformKind().equals(phiOut.getPlatformKind()) && phiIn.getLIRKind().isUnknownReference() && phiOut.getLIRKind().isValue());
+            });
+        }
+    }
+
+    public static void forEachPhiRegisterHint(LIR lir, AbstractBlockBase<?> block, LabelOp label, Value targetValue, OperandMode mode, ValueConsumer valueConsumer) {
+        assert mode == OperandMode.DEF : "Wrong operand mode: " + mode;
+        assert lir.getLIRforBlock(block).get(0).equals(label) : String.format("Block %s and Label %s do not match!", block, label);
+
+        if (!label.isPhiIn()) {
+            return;
+        }
+        int idx = indexOfValue(label, targetValue);
+        assert idx >= 0 : String.format("Value %s not in label %s", targetValue, label);
+
+        for (AbstractBlockBase<?> pred : block.getPredecessors()) {
+            JumpOp jump = phiOut(lir, pred);
+            Value sourceValue = jump.getOutgoingValue(idx);
+            valueConsumer.visitValue(jump, sourceValue, null, null);
+        }
+
+    }
+
+    private static int indexOfValue(LabelOp label, Value value) {
+        for (int i = 0; i < label.getIncomingSize(); i++) {
+            if (label.getIncomingValue(i).equals(value)) {
+                return i;
+            }
+        }
+        return -1;
+    }
+
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSAUtils.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSAUtils.java	Mon Jul 27 16:26:41 2015 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,176 +0,0 @@
-/*
- * 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.ssa;
-
-import java.util.*;
-
-import jdk.internal.jvmci.meta.*;
-
-import com.oracle.graal.compiler.common.cfg.*;
-import com.oracle.graal.lir.*;
-import com.oracle.graal.lir.LIRInstruction.OperandMode;
-import com.oracle.graal.lir.StandardOp.BlockEndOp;
-import com.oracle.graal.lir.StandardOp.JumpOp;
-import com.oracle.graal.lir.StandardOp.LabelOp;
-
-/**
- * Utilities for working with Static-Single-Assignment LIR form.
- *
- * <h2>Representation of <code>PHI</code>s</h2>
- *
- * There is no explicit <code>PHI</code> {@linkplain LIRInstruction}. Instead, they are implemented
- * as parallel copy that span across a control-flow edge.
- *
- * The variables introduced by <code>PHI</code>s of a specific {@linkplain AbstractBlockBase merge
- * block} are {@linkplain LabelOp#setIncomingValues attached} to the {@linkplain LabelOp} of the
- * block. The outgoing values from the predecessor are {@link JumpOp#setOutgoingValues input} to the
- * {@linkplain BlockEndOp} of the predecessor. Because there are no critical edges we know that the
- * {@link BlockEndOp} of the predecessor has to be a {@link JumpOp}.
- *
- * <h3>Example:</h3>
- *
- * <pre>
- * B0 -> B1
- *   ...
- *   v0|i = ...
- *   JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1
- * ________________________________________________
- * 
- * B2 -> B1
- *   ...
- *   v1|i = ...
- *   v2|i = ...
- *   JUMP ~[v1|i, v2|i] destination: B2 -> B1
- * ________________________________________________
- * 
- * B1 <- B0,B2
- *   [v3|i, v4|i] = LABEL
- *   ...
- * </pre>
- */
-public final class SSAUtils {
-
-    public interface PhiValueVisitor {
-        /**
-         * @param phiIn the incoming value at the merge block
-         * @param phiOut the outgoing value from the predecessor block
-         */
-        void visit(Value phiIn, Value phiOut);
-    }
-
-    /**
-     * Visits each phi value pair of an edge, i.e. the outgoing value from the predecessor and the
-     * incoming value to the merge block.
-     */
-    public static void forEachPhiValuePair(LIR lir, AbstractBlockBase<?> merge, AbstractBlockBase<?> pred, PhiValueVisitor visitor) {
-        if (merge.getPredecessorCount() < 2) {
-            return;
-        }
-        assert merge.getPredecessors().contains(pred) : String.format("%s not in predecessor list: %s", pred, merge.getPredecessors());
-        assert pred.getSuccessorCount() == 1 : String.format("Merge predecessor block %s has more than one successor? %s", pred, pred.getSuccessors());
-        assert pred.getSuccessors().get(0) == merge : String.format("Predecessor block %s has wrong successor: %s, should be: %s", pred, pred.getSuccessors().get(0), merge);
-
-        JumpOp jump = phiOut(lir, pred);
-        LabelOp label = phiIn(lir, merge);
-
-        assert label.getIncomingSize() == jump.getOutgoingSize() : String.format("Phi In/Out size mismatch: in=%d vs. out=%d", label.getIncomingSize(), jump.getOutgoingSize());
-
-        for (int i = 0; i < label.getIncomingSize(); i++) {
-            visitor.visit(label.getIncomingValue(i), jump.getOutgoingValue(i));
-        }
-    }
-
-    private static JumpOp phiOut(LIR lir, AbstractBlockBase<?> block) {
-        assert block.getSuccessorCount() == 1;
-        List<LIRInstruction> instructions = lir.getLIRforBlock(block);
-        int index = instructions.size() - 1;
-        LIRInstruction op = instructions.get(index);
-        return (JumpOp) op;
-    }
-
-    public static int phiOutIndex(LIR lir, AbstractBlockBase<?> block) {
-        assert block.getSuccessorCount() == 1;
-        List<LIRInstruction> instructions = lir.getLIRforBlock(block);
-        int index = instructions.size() - 1;
-        assert instructions.get(index) instanceof JumpOp;
-        return index;
-    }
-
-    private static LabelOp phiIn(LIR lir, AbstractBlockBase<?> block) {
-        assert block.getPredecessorCount() > 1;
-        LabelOp label = (LabelOp) lir.getLIRforBlock(block).get(0);
-        return label;
-    }
-
-    public static void removePhiOut(LIR lir, AbstractBlockBase<?> block) {
-        JumpOp jump = phiOut(lir, block);
-        jump.clearOutgoingValues();
-    }
-
-    public static void removePhiIn(LIR lir, AbstractBlockBase<?> block) {
-        LabelOp label = phiIn(lir, block);
-        label.clearIncomingValues();
-    }
-
-    public static boolean verifySSAForm(LIR lir) {
-        return new SSAVerifier(lir).verify();
-    }
-
-    public static void verifyPhi(LIR lir, AbstractBlockBase<?> merge) {
-        assert merge.getPredecessorCount() > 1;
-        for (AbstractBlockBase<?> pred : merge.getPredecessors()) {
-            forEachPhiValuePair(lir, merge, pred, (phiIn, phiOut) -> {
-                assert phiIn.getLIRKind().equals(phiOut.getLIRKind()) ||
-                                (phiIn.getPlatformKind().equals(phiOut.getPlatformKind()) && phiIn.getLIRKind().isUnknownReference() && phiOut.getLIRKind().isValue());
-            });
-        }
-    }
-
-    public static void forEachPhiRegisterHint(LIR lir, AbstractBlockBase<?> block, LabelOp label, Value targetValue, OperandMode mode, ValueConsumer valueConsumer) {
-        assert mode == OperandMode.DEF : "Wrong operand mode: " + mode;
-        assert lir.getLIRforBlock(block).get(0).equals(label) : String.format("Block %s and Label %s do not match!", block, label);
-
-        if (!label.isPhiIn()) {
-            return;
-        }
-        int idx = indexOfValue(label, targetValue);
-        assert idx >= 0 : String.format("Value %s not in label %s", targetValue, label);
-
-        for (AbstractBlockBase<?> pred : block.getPredecessors()) {
-            JumpOp jump = phiOut(lir, pred);
-            Value sourceValue = jump.getOutgoingValue(idx);
-            valueConsumer.visitValue(jump, sourceValue, null, null);
-        }
-
-    }
-
-    private static int indexOfValue(LabelOp label, Value value) {
-        for (int i = 0; i < label.getIncomingSize(); i++) {
-            if (label.getIncomingValue(i).equals(value)) {
-                return i;
-            }
-        }
-        return -1;
-    }
-
-}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIBlockValueMapImpl.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIBlockValueMapImpl.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,252 @@
+/*
+ * 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.ssi;
+
+import static com.oracle.graal.lir.LIRValueUtil.*;
+import static jdk.internal.jvmci.code.ValueUtil.*;
+
+import java.util.*;
+
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.LIRInstruction.OperandMode;
+import com.oracle.graal.lir.StandardOp.BlockEndOp;
+import com.oracle.graal.lir.StandardOp.LabelOp;
+import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.util.*;
+
+public final class SSIBlockValueMapImpl implements BlockValueMap {
+
+    private static final class BlockData {
+
+        /** Mapping from value to index into {@link #incoming}. */
+        private final ValueMap<Value, Integer> valueIndexMap;
+        private final ArrayList<Value> incoming;
+        private final ArrayList<Value> outgoing;
+
+        private BlockData(int initialVariableCapacity, int initialStackSlotCapacity) {
+            valueIndexMap = new VariableVirtualStackValueMap<>(initialVariableCapacity, initialStackSlotCapacity);
+            incoming = new ArrayList<>();
+            outgoing = new ArrayList<>();
+        }
+
+        public Integer getIndex(Value operand) {
+            return valueIndexMap.get(operand);
+        }
+
+        public Value getIncoming(int index) {
+            return incoming.get(index);
+        }
+
+        public void setIncoming(int index, Value value) {
+            incoming.set(index, value);
+        }
+
+        public int addIncoming(Value operand) {
+            assert isVariable(operand) || isVirtualStackSlot(operand) : "Not a variable or vstack: " + operand;
+            int index = incoming.size();
+            incoming.add(Value.ILLEGAL);
+            valueIndexMap.put(operand, index);
+            return index;
+        }
+
+        public boolean contains(Value operand) {
+            return getIndex(operand) != null;
+        }
+
+        public int addOutgoing(Value operand) {
+            int index = outgoing.size();
+            outgoing.add(operand);
+            return index;
+        }
+
+    }
+
+    /** Mapping from value to definition block. */
+    private final ValueMap<Value, AbstractBlockBase<?>> valueToDefBlock;
+    private final BlockMap<BlockData> blockData;
+    private final int initialVariableCapacity;
+    private final int initialStackSlotCapacity;
+
+    public SSIBlockValueMapImpl(AbstractControlFlowGraph<?> cfg, int initialVariableCapacity, int initialStackSlotCapacity) {
+        this.initialVariableCapacity = initialVariableCapacity;
+        this.initialStackSlotCapacity = initialStackSlotCapacity;
+        valueToDefBlock = new VariableVirtualStackValueMap<>(initialVariableCapacity, initialStackSlotCapacity);
+        blockData = new BlockMap<>(cfg);
+    }
+
+    @Override
+    public void accessOperand(Value operand, AbstractBlockBase<?> block) {
+        assert block != null : "block is null";
+        if (operand instanceof CompositeValue) {
+            ((CompositeValue) operand).forEachComponent(null, OperandMode.USE, (op, value, mode, flag) -> {
+                accessOperand(value, block);
+                return value;
+            });
+        } else if (processValue(operand)) {
+            AbstractBlockBase<?> defBlock = getDefinitionBlock(operand);
+            assert defBlock != null : "Value is not defined: " + operand;
+            assert AbstractControlFlowGraph.dominates(defBlock, block) : "Block " + defBlock + " does not dominate " + block;
+            accessRecursive(operand, defBlock, block);
+        }
+    }
+
+    @Override
+    public void defineOperand(Value operand, AbstractBlockBase<?> block) {
+        assert block != null : "block is null";
+        if (processValue(operand)) {
+            AbstractBlockBase<?> defBlock = getDefinitionBlock(operand);
+            if (defBlock == null) {
+                setDefinitionBlock(operand, block);
+            } else {
+                /*
+                 * Redefinition: this can happen for nodes that do not produce a new value but proxy
+                 * another one (PiNode, reinterpret).
+                 */
+                assert AbstractControlFlowGraph.dominates(defBlock, block) : String.format("Definition of %s in %s does not dominate the redefinition %s", operand, defBlock, block);
+            }
+        }
+    }
+
+    private static boolean processValue(Value operand) {
+        return isVariable(operand) || isVirtualStackSlot(operand);
+    }
+
+    // setter getter for internal data structures
+
+    private AbstractBlockBase<?> getDefinitionBlock(Value operand) {
+        return valueToDefBlock.get(operand);
+    }
+
+    private void setDefinitionBlock(Value operand, AbstractBlockBase<?> block) {
+        valueToDefBlock.put(operand, block);
+    }
+
+    private BlockData getOrInit(AbstractBlockBase<?> block) {
+        BlockData data = blockData.get(block);
+        if (data == null) {
+            data = new BlockData(initialVariableCapacity, initialStackSlotCapacity);
+            blockData.put(block, data);
+        }
+        return data;
+    }
+
+    // implementation
+
+    private void accessRecursive(Value operand, AbstractBlockBase<?> defBlock, AbstractBlockBase<?> block) {
+        try (Indent indent = Debug.logAndIndent("get operand %s in block %s", operand, block)) {
+            if (block.equals(defBlock)) {
+                Debug.log("found definition!");
+                return;
+            }
+            BlockData data = getOrInit(block);
+            Integer index = data.getIndex(operand);
+            if (index != null) {
+                // value is live at block begin but might not be initialized
+                Value in = data.getIncoming(index);
+                if (Value.ILLEGAL.equals(in)) {
+                    data.setIncoming(index, operand);
+                    Debug.log("uninitialized incoming value -> initialize!");
+                } else {
+                    Debug.log("incoming value already initialized!");
+                }
+                return;
+            }
+
+            // the value is not yet live a current block
+            int idx = addLiveValueToBlock(operand, block);
+            data.setIncoming(idx, operand);
+
+            for (AbstractBlockBase<?> pred : block.getPredecessors()) {
+                accessRecursive(operand, defBlock, pred);
+            }
+        }
+    }
+
+    private int addLiveValueToBlock(Value operand, AbstractBlockBase<?> block) {
+        try (Indent indent = Debug.logAndIndent("add incoming value!")) {
+            int index = -1;
+            for (AbstractBlockBase<?> pred : block.getPredecessors()) {
+                try (Indent indent1 = Debug.logAndIndent("Add outgoing operand to %s", pred)) {
+                    BlockData predData = getOrInit(pred);
+                    int predIndex = predData.addOutgoing(operand);
+
+                    if (index == -1) {
+                        index = predIndex;
+                    } else {
+                        assert predIndex == index;
+                    }
+
+                    for (AbstractBlockBase<?> succ : pred.getSuccessors()) {
+                        Debug.log("Add incoming operand to %s", succ);
+                        BlockData succData = getOrInit(succ);
+                        if (!succData.contains(operand)) {
+                            int succIndex = succData.addIncoming(operand);
+                            assert succIndex == predIndex;
+                        }
+                    }
+                }
+            }
+            Debug.log("new index: %d", index);
+            return index;
+        }
+    }
+
+    // finish
+
+    public void finish(LIRGeneratorTool gen) {
+        Debug.dump(gen.getResult().getLIR(), "Before SSI operands");
+        AbstractControlFlowGraph<?> cfg = gen.getResult().getLIR().getControlFlowGraph();
+        for (AbstractBlockBase<?> block : cfg.getBlocks()) {
+            // set label
+            BlockData data = blockData.get(block);
+            if (data != null) {
+                if (data.incoming != null && data.incoming.size() > 0) {
+                    LabelOp label = getLabel(gen, block);
+                    label.addIncomingValues(data.incoming.toArray(new Value[data.incoming.size()]));
+                }
+                // set block end
+                if (data.outgoing != null && data.outgoing.size() > 0) {
+                    BlockEndOp blockEndOp = getBlockEnd(gen, block);
+                    blockEndOp.addOutgoingValues(data.outgoing.toArray(new Value[data.outgoing.size()]));
+                }
+            }
+        }
+    }
+
+    private static List<LIRInstruction> getLIRforBlock(LIRGeneratorTool gen, AbstractBlockBase<?> block) {
+        return gen.getResult().getLIR().getLIRforBlock(block);
+    }
+
+    private static LabelOp getLabel(LIRGeneratorTool gen, AbstractBlockBase<?> block) {
+        return (LabelOp) getLIRforBlock(gen, block).get(0);
+    }
+
+    private static BlockEndOp getBlockEnd(LIRGeneratorTool gen, AbstractBlockBase<?> block) {
+        List<LIRInstruction> instructions = getLIRforBlock(gen, block);
+        return (BlockEndOp) instructions.get(instructions.size() - 1);
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIConstructionPhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIConstructionPhase.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,120 @@
+/*
+ * 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.ssi;
+
+import java.util.*;
+
+import jdk.internal.jvmci.code.*;
+
+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.framemap.*;
+import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.phases.*;
+import com.oracle.graal.lir.ssa.*;
+
+public final class SSIConstructionPhase extends PreAllocationOptimizationPhase {
+
+    @Override
+    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, LIRGeneratorTool lirGen) {
+        assert SSAUtil.verifySSAForm(lirGenRes.getLIR());
+        LIR lir = lirGenRes.getLIR();
+        new SSIBuilder(lir, lirGenRes.getFrameMapBuilder()).build(lirGen);
+    }
+
+    private static final class SSIBuilder {
+        private final SSIBlockValueMapImpl valueMap;
+        private final LIR lir;
+        private final BitSet processed;
+
+        private SSIBuilder(LIR lir, FrameMapBuilder frameMapBuilder) {
+            this.lir = lir;
+            valueMap = new SSIBlockValueMapImpl(lir.getControlFlowGraph(), lir.nextVariable(), ((FrameMapBuilderTool) frameMapBuilder).getNumberOfStackSlots());
+            processed = new BitSet(lir.getControlFlowGraph().getBlocks().size());
+        }
+
+        private void build(LIRGeneratorTool lirGen) {
+            Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>(lir.getControlFlowGraph().getBlocks());
+            while (!worklist.isEmpty()) {
+                AbstractBlockBase<?> block = worklist.poll();
+                if (!processed.get(block.getId())) {
+                    try (Indent indent = Debug.logAndIndent("Try processing Block %s", block)) {
+                        // check predecessors
+                        boolean reschedule = false;
+                        for (AbstractBlockBase<?> pred : block.getPredecessors()) {
+                            if (!processed.get(pred.getId()) && !isLoopBackEdge(pred, block)) {
+                                Debug.log("Schedule predecessor: %s", pred);
+                                worklist.addLast(pred);
+                                reschedule = true;
+                            }
+                        }
+                        if (reschedule) {
+                            Debug.log("Reschedule block %s", block);
+                            worklist.addLast(block);
+                        } else {
+                            processBlock(block);
+                        }
+                    }
+                }
+            }
+            valueMap.finish(lirGen);
+        }
+
+        public void processBlock(AbstractBlockBase<?> block) {
+            assert !processed.get(block.getId()) : "Block already processed " + block;
+            try (Indent indent = Debug.logAndIndent("Process Block %s", block)) {
+                // track values
+                ValueConsumer useConsumer = (value, mode, flags) -> {
+                    if (flags.contains(OperandFlag.UNINITIALIZED)) {
+                        AbstractBlockBase<?> startBlock = lir.getControlFlowGraph().getStartBlock();
+                        Debug.log("Set definition of %s in block %s", value, startBlock);
+                        valueMap.defineOperand(value, startBlock);
+                    } else {
+                        Debug.log("Access %s in block %s", value, block);
+                        valueMap.accessOperand(value, block);
+                    }
+                };
+                ValueConsumer defConsumer = (value, mode, flags) -> {
+                    Debug.log("Set definition of %s in block %s", value, block);
+                    valueMap.defineOperand(value, block);
+                };
+                for (LIRInstruction op : lir.getLIRforBlock(block)) {
+                    // use
+                    op.visitEachInput(useConsumer);
+                    op.visitEachAlive(useConsumer);
+                    op.visitEachState(useConsumer);
+                    // def
+                    op.visitEachTemp(defConsumer);
+                    op.visitEachOutput(defConsumer);
+                }
+                processed.set(block.getId());
+            }
+        }
+
+        private static boolean isLoopBackEdge(AbstractBlockBase<?> from, AbstractBlockBase<?> to) {
+            return from.isLoopEnd() && to.isLoopHeader() && from.getLoop().equals(to.getLoop());
+        }
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIUtil.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIUtil.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,191 @@
+/*
+ * 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.ssi;
+
+import java.util.*;
+
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.StandardOp.BlockEndOp;
+import com.oracle.graal.lir.LIRInstruction.*;
+import com.oracle.graal.lir.StandardOp.*;
+import com.oracle.graal.lir.ssa.SSAUtil.*;
+
+/**
+ * Utilities for working with Static-Single-Information LIR form.
+ *
+ * <h2>Representation of &phi; and &sigma;</h2>
+ *
+ * There are no explicit &phi;/&sigma; {@link LIRInstruction}s. Instead, they are implemented as
+ * parallel copy that spans across a control-flow edge.
+ *
+ * The variables introduced by &phi;/&sigma; of a specific {@linkplain AbstractBlockBase block} are
+ * {@linkplain LabelOp#setIncomingValues attached} to the {@link LabelOp} of the block. The outgoing
+ * values from the predecessor are {@linkplain BlockEndOp#setOutgoingValues input} to the
+ * {@link BlockEndOp} of the predecessor.
+ *
+ * When it does not matter whether we are talking about a &phi; or a &sigma; we call the values that
+ * are defined by a label {@linkplain LabelOp#setIncomingValues incoming} and the values that are
+ * input to the {@link BlockEndOp} of the predecessor {@linkplain BlockEndOp#setOutgoingValues
+ * outgoing}.
+ *
+ * <h2>Implementation Details</h2>
+ *
+ * For our purposes we want a <em>maximal</em> SSI form, which means that all values that are alive
+ * across basic block boundaries are gated with a &phi;/&sigma;. In other words the outgoing and
+ * incoming values of the {@link BlockEndOp} and {@link LabelOp} are equivalent to the live-out and
+ * live-in set of the corresponding block.
+ *
+ * As a side effect variables are local to a block. We reuse the name of the predecessor if they
+ * represent the same value (i.e. not a real &phi; definition).
+ *
+ * <h2>Examples</h2>
+ *
+ * <h3>Merge (&phi;)</h3>
+ *
+ * <pre>
+ * B0 -> B1
+ *   ...
+ *   v0|i = ...
+ *   JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1
+ * ________________________________________________
+ *
+ * B2 -> B1
+ *   ...
+ *   v1|i = ...
+ *   v2|i = ...
+ *   JUMP ~[v1|i, v2|i] destination: B2 -> B1
+ * ________________________________________________
+ *
+ * B1 <- B0,B2
+ *   [v3|i, v4|i] = LABEL
+ *   ...
+ * </pre>
+ *
+ * Note: the outgoing values of a block can contain constants (see <code>B0</code>).
+ *
+ * <h3>Split (&sigma;)</h3>
+ *
+ * <pre>
+ * B0 -> B1,B2
+ *   ...
+ *   v0|i = ...
+ *   v1|i = ...
+ *   v2|i = ...
+ *   TEST (x: v1|i, y: v1|i)
+ *   BRANCH ~[v2|i, v0|j] condition: <, true: B1 false: B2
+ * ________________________________________________
+ *
+ * B1 <- B0
+ *   [-, v0|j] = LABEL
+ *   ...
+ * ________________________________________________
+ *
+ * B2 <- B0
+ *   [v2|i, v0|j] = LABEL
+ *   ...
+ * </pre>
+ *
+ * Note: If a incoming value is not needed in a branch it is {@link Value#ILLEGAL ignored} (see
+ * <code>B1<code>).
+ */
+public final class SSIUtil {
+
+    public static BlockEndOp outgoing(LIR lir, AbstractBlockBase<?> block) {
+        return (BlockEndOp) outgoingInst(lir, block);
+    }
+
+    public static LIRInstruction outgoingInst(LIR lir, AbstractBlockBase<?> block) {
+        List<LIRInstruction> instructions = lir.getLIRforBlock(block);
+        int index = instructions.size() - 1;
+        LIRInstruction op = instructions.get(index);
+        return op;
+    }
+
+    public static LabelOp incoming(LIR lir, AbstractBlockBase<?> block) {
+        return (LabelOp) incomingInst(lir, block);
+    }
+
+    private static LIRInstruction incomingInst(LIR lir, AbstractBlockBase<?> block) {
+        return lir.getLIRforBlock(block).get(0);
+    }
+
+    public static void removeIncoming(LIR lir, AbstractBlockBase<?> block) {
+        incoming(lir, block).clearIncomingValues();
+    }
+
+    public static void removeOutgoing(LIR lir, AbstractBlockBase<?> block) {
+        outgoing(lir, block).clearOutgoingValues();
+    }
+
+    /**
+     * Visits each SIGMA/PHI value pair of an edge, i.e. the outgoing value from the predecessor and
+     * the incoming value to the merge block.
+     */
+    public static void forEachValuePair(LIR lir, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock, PhiValueVisitor visitor) {
+        assert toBlock.getPredecessors().contains(fromBlock) : String.format("%s not in predecessor list: %s", fromBlock, toBlock.getPredecessors());
+        assert fromBlock.getSuccessorCount() == 1 || toBlock.getPredecessorCount() == 1 : String.format("Critical Edge? %s has %d successors and %s has %d predecessors", fromBlock,
+                        fromBlock.getSuccessorCount(), toBlock, toBlock.getPredecessorCount());
+        assert fromBlock.getSuccessors().contains(toBlock) : String.format("Predecessor block %s has wrong successor: %s, should contain: %s", fromBlock, fromBlock.getSuccessors(), toBlock);
+
+        BlockEndOp blockEnd = outgoing(lir, fromBlock);
+        LabelOp label = incoming(lir, toBlock);
+
+        assert label.getIncomingSize() == blockEnd.getOutgoingSize() : String.format("In/Out size mismatch: in=%d vs. out=%d, blocks %s vs. %s", label.getIncomingSize(), blockEnd.getOutgoingSize(),
+                        toBlock, fromBlock);
+
+        for (int i = 0; i < label.getIncomingSize(); i++) {
+            visitor.visit(label.getIncomingValue(i), blockEnd.getOutgoingValue(i));
+        }
+    }
+
+    public static void forEachRegisterHint(LIR lir, AbstractBlockBase<?> block, LabelOp label, Value targetValue, OperandMode mode, ValueConsumer valueConsumer) {
+        assert mode == OperandMode.DEF : "Wrong operand mode: " + mode;
+        assert lir.getLIRforBlock(block).get(0).equals(label) : String.format("Block %s and Label %s do not match!", block, label);
+
+        if (!label.isPhiIn()) {
+            return;
+        }
+        int idx = indexOfValue(label, targetValue);
+        assert idx >= 0 : String.format("Value %s not in label %s", targetValue, label);
+
+        for (AbstractBlockBase<?> pred : block.getPredecessors()) {
+            BlockEndOp blockEnd = outgoing(lir, pred);
+            Value sourceValue = blockEnd.getOutgoingValue(idx);
+            valueConsumer.visitValue((LIRInstruction) blockEnd, sourceValue, null, null);
+        }
+
+    }
+
+    private static int indexOfValue(LabelOp label, Value value) {
+        for (int i = 0; i < label.getIncomingSize(); i++) {
+            if (label.getIncomingValue(i).equals(value)) {
+                return i;
+            }
+        }
+        return -1;
+    }
+
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIVerifier.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIVerifier.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,158 @@
+/*
+ * 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.ssi;
+
+import static jdk.internal.jvmci.code.ValueUtil.*;
+
+import java.util.*;
+
+import jdk.internal.jvmci.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.StandardOp.BlockEndOp;
+import com.oracle.graal.lir.StandardOp.LabelOp;
+
+public final class SSIVerifier {
+
+    public static boolean verify(LIR lir) {
+        return new SSIVerifier(lir).verify();
+    }
+
+    private final LIR lir;
+
+    private SSIVerifier(LIR lir) {
+        this.lir = lir;
+    }
+
+    private boolean verify() {
+        try (Scope s = Debug.scope("SSIVerifier", lir)) {
+            for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) {
+                doBlock(block);
+            }
+        } catch (Throwable e) {
+            throw Debug.handle(e);
+        }
+        return true;
+    }
+
+    private void doBlock(AbstractBlockBase<?> block) {
+        for (AbstractBlockBase<?> succ : block.getSuccessors()) {
+            verifyEdge(block, succ);
+        }
+        verifyInstructions(block);
+    }
+
+    private void verifyEdge(AbstractBlockBase<?> from, AbstractBlockBase<?> to) {
+        BlockEndOp out = SSIUtil.outgoing(lir, from);
+        LabelOp in = SSIUtil.incoming(lir, to);
+        int outgoingSize = out.getOutgoingSize();
+        int incomingSize = in.getIncomingSize();
+        assert outgoingSize == incomingSize : String.format("Outgoing size %d and incoming size %d do not match", outgoingSize, incomingSize);
+
+        for (int i = 0; i < outgoingSize; i++) {
+            Value incomingValue = in.getIncomingValue(i);
+            Value outgoingValue = out.getOutgoingValue(i);
+            LIRKind inLIRKind = incomingValue.getLIRKind();
+            LIRKind outLIRKind = outgoingValue.getLIRKind();
+            assert LIRKind.verifyMoveKinds(inLIRKind, outLIRKind) || incomingValue.equals(Value.ILLEGAL) : String.format("Outgoing LIRKind %s (%s) an and incoming LIRKind %s (%s) do not match",
+                            outgoingValue, outLIRKind, incomingValue, inLIRKind);
+        }
+    }
+
+    private void verifyInstructions(AbstractBlockBase<?> block) {
+        List<LIRInstruction> instructions = lir.getLIRforBlock(block);
+        HashMap<Value, LIRInstruction> defined = new HashMap<>();
+
+        InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
+            public void visitValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
+                if (checkUsage(value)) {
+                    assert defined.containsKey(value) || flags.contains(OperandFlag.UNINITIALIZED) : String.format("Value %s is used by instruction %s in block %s but not defined.", value,
+                                    instruction, block);
+                }
+            }
+        };
+        InstructionValueConsumer stateConsumer = new InstructionValueConsumer() {
+            public void visitValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
+                if (checkUsage(value)) {
+                    /*
+                     * TODO (je): There are undefined stack values used for locks. Ignore them for
+                     * the time being.
+                     */
+                    assert defined.containsKey(value) || isVirtualStackSlot(value) : String.format("Value %s is used in state of instruction %s in block %s but not defined.", value, instruction,
+                                    block);
+                }
+            }
+        };
+
+        InstructionValueConsumer defConsumer = new InstructionValueConsumer() {
+            public void visitValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
+                if (trackDefinition(value)) {
+                    assert !defined.containsKey(value) : String.format("Value %s is redefined by instruction %s in block %s but already defined by %s.", value, instruction, block, defined.get(value));
+                    defined.put(value, instruction);
+                }
+            }
+        };
+
+        for (LIRInstruction op : instructions) {
+            op.visitEachAlive(useConsumer);
+            op.visitEachInput(useConsumer);
+            op.visitEachState(stateConsumer);
+
+            op.visitEachTemp(defConsumer);
+            op.visitEachOutput(defConsumer);
+        }
+    }
+
+    private static boolean trackDefinition(Value value) {
+        if (isRegister(value)) {
+            // registers can be redefined
+            return false;
+        }
+        if (value.equals(Value.ILLEGAL)) {
+            // Don't care about illegal values
+            return false;
+        }
+        return true;
+    }
+
+    private static boolean checkUsage(Value value) {
+        if (value instanceof Constant) {
+            // Constants do not need to be defined
+            return false;
+        }
+        if (isRegister(value)) {
+            // Assume fixed registers are correct
+            return false;
+        }
+        if (value.equals(Value.ILLEGAL)) {
+            // Don't care about illegal values
+            return false;
+        }
+        return true;
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/util/IndexedValueMap.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/util/IndexedValueMap.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,163 @@
+/*
+ * 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.util;
+
+import java.util.*;
+
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.LIRInstruction.OperandFlag;
+import com.oracle.graal.lir.LIRInstruction.OperandMode;
+
+public final class IndexedValueMap {
+    private Value[] values;
+
+    public IndexedValueMap() {
+        values = Value.NO_VALUES;
+    }
+
+    public IndexedValueMap(IndexedValueMap other) {
+        int limit = other.values.length;
+        while (limit > 0) {
+            if (other.values[limit - 1] == null) {
+                limit--;
+                continue;
+            }
+            break;
+        }
+        values = new Value[limit];
+        System.arraycopy(other.values, 0, values, 0, values.length);
+    }
+
+    public Value get(int index) {
+        return values[index];
+    }
+
+    public void put(int index, Value value) {
+        if (values.length <= index) {
+            if (value == null) {
+                return;
+            }
+            Value[] newValues = new Value[index + 1];
+            System.arraycopy(values, 0, newValues, 0, values.length);
+            values = newValues;
+            values[index] = value;
+        } else {
+            values[index] = value;
+        }
+    }
+
+    public void putAll(IndexedValueMap stack) {
+        Value[] otherValues = stack.values;
+        int limit = otherValues.length;
+        if (limit > values.length) {
+            while (limit > 0) {
+                if (otherValues[limit - 1] == null) {
+                    limit--;
+                    continue;
+                }
+                break;
+            }
+            if (limit > values.length) {
+                Value[] newValues = new Value[limit];
+                System.arraycopy(values, 0, newValues, 0, values.length);
+                values = newValues;
+            }
+        }
+        for (int i = 0; i < limit; i++) {
+            Value value = otherValues[i];
+            if (value != null) {
+                values[i] = value;
+            }
+        }
+    }
+
+    @Override
+    public boolean equals(Object other) {
+        if (other instanceof IndexedValueMap) {
+            IndexedValueMap that = (IndexedValueMap) other;
+            int limit = Math.min(values.length, that.values.length);
+            for (int i = 0; i < limit; i++) {
+                if (!Objects.equals(values[i], that.values[i])) {
+                    return false;
+                }
+            }
+            for (int i = limit; i < values.length; i++) {
+                if (values[i] != null) {
+                    return false;
+                }
+            }
+            for (int i = limit; i < that.values.length; i++) {
+                if (that.values[i] != null) {
+                    return false;
+                }
+            }
+            return true;
+        }
+        return false;
+    }
+
+    public void forEach(LIRInstruction inst, OperandMode mode, EnumSet<OperandFlag> flags, InstructionValueProcedure proc) {
+        for (int i = 0; i < values.length; i++) {
+            if (values[i] != null) {
+                values[i] = proc.doValue(inst, values[i], mode, flags);
+            }
+        }
+    }
+
+    public void forEach(LIRInstruction inst, OperandMode mode, EnumSet<OperandFlag> flags, InstructionValueConsumer consumer) {
+        for (Value v : values) {
+            if (v != null) {
+                consumer.visitValue(inst, v, mode, flags);
+            }
+        }
+    }
+
+    @Override
+    public int hashCode() {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder sb = new StringBuilder("[");
+        boolean comma = false;
+
+        for (int i = 0; i < values.length; i++) {
+            if (values[i] != null) {
+                if (comma) {
+                    sb.append(", ");
+                } else {
+                    comma = true;
+                }
+
+                sb.append(i);
+                sb.append(": ");
+                sb.append(values[i]);
+            }
+        }
+        sb.append(']');
+        return sb.toString();
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/util/IntValueMap.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/util/IntValueMap.java	Mon Jul 27 16:26:41 2015 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,163 +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.util;
-
-import java.util.*;
-
-import jdk.internal.jvmci.meta.*;
-
-import com.oracle.graal.lir.*;
-import com.oracle.graal.lir.LIRInstruction.OperandFlag;
-import com.oracle.graal.lir.LIRInstruction.OperandMode;
-
-public final class IntValueMap {
-    private Value[] values;
-
-    public IntValueMap() {
-        values = Value.NO_VALUES;
-    }
-
-    public IntValueMap(IntValueMap other) {
-        int limit = other.values.length;
-        while (limit > 0) {
-            if (other.values[limit - 1] == null) {
-                limit--;
-                continue;
-            }
-            break;
-        }
-        values = new Value[limit];
-        System.arraycopy(other.values, 0, values, 0, values.length);
-    }
-
-    public Value get(int index) {
-        return values[index];
-    }
-
-    public void put(int index, Value value) {
-        if (values.length <= index) {
-            if (value == null) {
-                return;
-            }
-            Value[] newValues = new Value[index + 1];
-            System.arraycopy(values, 0, newValues, 0, values.length);
-            values = newValues;
-            values[index] = value;
-        } else {
-            values[index] = value;
-        }
-    }
-
-    public void putAll(IntValueMap stack) {
-        Value[] otherValues = stack.values;
-        int limit = otherValues.length;
-        if (limit > values.length) {
-            while (limit > 0) {
-                if (otherValues[limit - 1] == null) {
-                    limit--;
-                    continue;
-                }
-                break;
-            }
-            if (limit > values.length) {
-                Value[] newValues = new Value[limit];
-                System.arraycopy(values, 0, newValues, 0, values.length);
-                values = newValues;
-            }
-        }
-        for (int i = 0; i < limit; i++) {
-            Value value = otherValues[i];
-            if (value != null) {
-                values[i] = value;
-            }
-        }
-    }
-
-    @Override
-    public boolean equals(Object other) {
-        if (other instanceof IntValueMap) {
-            IntValueMap that = (IntValueMap) other;
-            int limit = Math.min(values.length, that.values.length);
-            for (int i = 0; i < limit; i++) {
-                if (!Objects.equals(values[i], that.values[i])) {
-                    return false;
-                }
-            }
-            for (int i = limit; i < values.length; i++) {
-                if (values[i] != null) {
-                    return false;
-                }
-            }
-            for (int i = limit; i < that.values.length; i++) {
-                if (that.values[i] != null) {
-                    return false;
-                }
-            }
-            return true;
-        }
-        return false;
-    }
-
-    public void forEach(LIRInstruction inst, OperandMode mode, EnumSet<OperandFlag> flags, InstructionValueProcedure proc) {
-        for (int i = 0; i < values.length; i++) {
-            if (values[i] != null) {
-                values[i] = proc.doValue(inst, values[i], mode, flags);
-            }
-        }
-    }
-
-    public void forEach(LIRInstruction inst, OperandMode mode, EnumSet<OperandFlag> flags, InstructionValueConsumer consumer) {
-        for (Value v : values) {
-            if (v != null) {
-                consumer.visitValue(inst, v, mode, flags);
-            }
-        }
-    }
-
-    @Override
-    public int hashCode() {
-        throw new UnsupportedOperationException();
-    }
-
-    @Override
-    public String toString() {
-        StringBuilder sb = new StringBuilder("[");
-        boolean comma = false;
-
-        for (int i = 0; i < values.length; i++) {
-            if (values[i] != null) {
-                if (comma) {
-                    sb.append(", ");
-                } else {
-                    comma = true;
-                }
-
-                sb.append(i);
-                sb.append(": ");
-                sb.append(values[i]);
-            }
-        }
-        sb.append(']');
-        return sb.toString();
-    }
-}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.lir/src/com/oracle/graal/lir/util/VariableVirtualStackValueMap.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/util/VariableVirtualStackValueMap.java	Mon Jul 27 16:57:30 2015 -0700
@@ -0,0 +1,98 @@
+/*
+ * 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.util;
+
+import static com.oracle.graal.lir.LIRValueUtil.*;
+import static jdk.internal.jvmci.code.ValueUtil.*;
+import jdk.internal.jvmci.common.*;
+import jdk.internal.jvmci.meta.*;
+
+public class VariableVirtualStackValueMap<K extends Value, T> extends ValueMap<K, T> {
+
+    private final Object[] variables;
+    private final Object[] slots;
+
+    public VariableVirtualStackValueMap(int initialVariableCapacity, int initialStackSlotCapacity) {
+        variables = new Object[initialVariableCapacity];
+        slots = new Object[initialStackSlotCapacity];
+    }
+
+    @Override
+    public T get(K value) {
+        if (isVariable(value)) {
+            return get(variables, asVariable(value).index);
+        }
+        if (isVirtualStackSlot(value)) {
+            return get(slots, asVirtualStackSlot(value).getId());
+        }
+        throw JVMCIError.shouldNotReachHere("Unsupported Value: " + value);
+    }
+
+    @Override
+    public void remove(K value) {
+        if (isVariable(value)) {
+            remove(variables, asVariable(value).index);
+        } else if (isVirtualStackSlot(value)) {
+            remove(slots, asVirtualStackSlot(value).getId());
+        } else {
+            throw JVMCIError.shouldNotReachHere("Unsupported Value: " + value);
+        }
+    }
+
+    @Override
+    public void put(K value, T object) {
+        if (isVariable(value)) {
+            put(variables, asVariable(value).index, object);
+        } else if (isVirtualStackSlot(value)) {
+            put(slots, asVirtualStackSlot(value).getId(), object);
+        } else {
+            throw JVMCIError.shouldNotReachHere("Unsupported Value: " + value);
+        }
+    }
+
+    @SuppressWarnings("unchecked")
+    private static <T> T get(Object[] array, int index) {
+        if (index >= array.length) {
+            return null;
+        }
+        return (T) array[index];
+    }
+
+    private static void remove(Object[] array, int index) {
+        if (index >= array.length) {
+            return;
+        }
+        array[index] = null;
+    }
+
+    private static <T> Object[] put(Object[] array, int index, T object) {
+        if (index >= array.length) {
+            Object[] newArray = new Object[index + 1];
+            System.arraycopy(array, 0, newArray, 0, array.length);
+            newArray[index] = object;
+            return newArray;
+        }
+        array[index] = object;
+        return null;
+    }
+}
diff -r 7d48038267b4 -r 8c6bc650d7fa graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CompilationPrinter.java
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CompilationPrinter.java	Mon Jul 27 16:26:41 2015 -0700
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CompilationPrinter.java	Mon Jul 27 16:57:30 2015 -0700
@@ -114,7 +114,7 @@
     /**
      * Formats given debug info as a multi line string.
      */
-    protected String debugInfoToString(BytecodePosition codePos, ReferenceMap refMap, IntValueMap liveBasePointers, RegisterSaveLayout calleeSaveInfo) {
+    protected String debugInfoToString(BytecodePosition codePos, ReferenceMap refMap, IndexedValueMap liveBasePointers, RegisterSaveLayout calleeSaveInfo) {
         StringBuilder sb = new StringBuilder();
         if (refMap != null) {
             sb.append("reference-map: ");
diff -r 7d48038267b4 -r 8c6bc650d7fa mx.graal/mx_graal.py
--- a/mx.graal/mx_graal.py	Mon Jul 27 16:26:41 2015 -0700
+++ b/mx.graal/mx_graal.py	Mon Jul 27 16:57:30 2015 -0700
@@ -1339,6 +1339,10 @@
     with VM('server', 'product'):
         with Task('UnitTestsNonSSA:hosted-product', tasks) as t:
             if t: unittest(['--enable-timing', '--verbose', '--fail-fast', '-G:-SSA_LIR'])
+    # Run unit tests on server-hosted-jvmci with TraceRA
+    with VM('server', 'product'):
+        with Task('UnitTestsTraceRA:hosted-product', tasks) as t:
+            if t: unittest(['--enable-timing', '--verbose', '--fail-fast', '-G:+TraceRA'])
     # Run ctw against rt.jar on server-hosted-jvmci
     with VM('server', 'product'):
         with Task('CTW:hosted-product', tasks) as t:
@@ -1388,6 +1392,11 @@
                 vm(['-XX:-TieredCompilation', '-G:-SSA_LIR', '-G:RegisterPressure=' + registers, '-esa', '-version'])
 
     with VM('jvmci', 'product'):
+        with Task('BootstrapTraceRAWithRegisterPressure:product', tasks) as t:
+            if t:
+                vm(['-XX:-TieredCompilation', '-G:+TraceRA', '-G:RegisterPressure=' + registers, '-esa', '-version'])
+
+    with VM('jvmci', 'product'):
         with Task('BootstrapWithImmutableCode:product', tasks) as t:
             if t: vm(['-XX:-TieredCompilation', '-G:+ImmutableCode', '-G:+VerifyPhases', '-esa', '-version'])
 
diff -r 7d48038267b4 -r 8c6bc650d7fa mx.graal/suite.py