# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1437728133 -7200
# Node ID 06a9e6737dcfcd6b8077612b305b6e702ffc7dd5
# Parent  681c04ce9db2f0fb4521829d2bbeb6c9b5e5a09f
Drop initial version of the trace based register allocator.

diff -r 681c04ce9db2 -r 06a9e6737dcf 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	Fri Jul 24 16:20:56 2015 +0200
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/BackendOptions.java	Fri Jul 24 10:55:33 2015 +0200
@@ -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 681c04ce9db2 -r 06a9e6737dcf 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	Fri Jul 24 10:55:33 2015 +0200
@@ -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 681c04ce9db2 -r 06a9e6737dcf 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	Fri Jul 24 16:20:56 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java	Fri Jul 24 10:55:33 2015 +0200
@@ -42,6 +42,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 681c04ce9db2 -r 06a9e6737dcf graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/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/SSILinearScan.java	Fri Jul 24 10:55:33 2015 +0200
@@ -0,0 +1,70 @@
+/*
+ * 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.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.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 681c04ce9db2 -r 06a9e6737dcf graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/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/SSILinearScanEliminateSpillMovePhase.java	Fri Jul 24 10:55:33 2015 +0200
@@ -0,0 +1,45 @@
+/*
+ * 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 com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.lir.StandardOp.MoveOp;
+
+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 681c04ce9db2 -r 06a9e6737dcf graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/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/SSILinearScanLifetimeAnalysisPhase.java	Fri Jul 24 10:55:33 2015 +0200
@@ -0,0 +1,122 @@
+/*
+ * 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.lir.alloc.lsra.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.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);
+
+            SSIUtils.forEachRegisterHint(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);
+                }
+            });
+        }
+    }
+
+    @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 681c04ce9db2 -r 06a9e6737dcf graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/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/SSILinearScanResolveDataFlowPhase.java	Fri Jul 24 10:55:33 2015 +0200
@@ -0,0 +1,127 @@
+/*
+ * 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.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.ssa.SSAUtils.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) {
+                SSIUtils.removeIncoming(allocator.ir, toBlock);
+            } else {
+                assert allocator.ir.getControlFlowGraph().getStartBlock().equals(toBlock);
+            }
+            SSIUtils.removeOutgoing(allocator.ir, 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();
+            SSIUtils.forEachValuePair(allocator.ir, midBlock, fromBlock, (to, from) -> map.put(to, from));
+
+            MyPhiValueVisitor visitor = new MyPhiValueVisitor(moveResolver, toBlock, fromBlock);
+            SSIUtils.forEachValuePair(allocator.ir, 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
+            SSIUtils.forEachValuePair(allocator.ir, 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 681c04ce9db2 -r 06a9e6737dcf graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceGlobalMoveResolver.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceGlobalMoveResolver.java	Fri Jul 24 10:55:33 2015 +0200
@@ -0,0 +1,407 @@
+/*
+ * 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.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.debug.*;
+import com.oracle.graal.lir.*;
+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 681c04ce9db2 -r 06a9e6737dcf graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceLinearScan.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceLinearScan.java	Fri Jul 24 10:55:33 2015 +0200
@@ -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;
+
+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.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
+    void printIntervals(String label) {
+        if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) {
+            super.printIntervals(label);
+        }
+    }
+
+    @Override
+    void printLir(String label, boolean hirValid) {
+        if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) {
+            Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks, label);
+        }
+    }
+
+}
diff -r 681c04ce9db2 -r 06a9e6737dcf graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceLinearScanLifetimeAnalysisPhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceLinearScanLifetimeAnalysisPhase.java	Fri Jul 24 10:55:33 2015 +0200
@@ -0,0 +1,288 @@
+/*
+ * 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.GraalOptions.*;
+import static com.oracle.graal.lir.LIRValueUtil.*;
+import static com.oracle.graal.lir.alloc.lsra.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.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.ir;
+        for (AbstractBlockBase<?> block : allocator.sortedBlocks) {
+            LabelOp label = SSIUtils.incoming(lir, block);
+            for (AbstractBlockBase<?> pred : block.getPredecessors()) {
+                if (isAllocatedOrCurrent(block, pred)) {
+                    BlockEndOp outgoing = SSIUtils.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)) {
+
+                            } else if (isConstant(fromValue)) {
+                            } else {
+                                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
+    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 681c04ce9db2 -r 06a9e6737dcf graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceLinearScanResolveDataFlowPhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceLinearScanResolveDataFlowPhase.java	Fri Jul 24 10:55:33 2015 +0200
@@ -0,0 +1,107 @@
+/*
+ * 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.meta.*;
+
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.ssa.SSAUtils.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);
+            SSIUtils.forEachValuePair(allocator.ir, 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 681c04ce9db2 -r 06a9e6737dcf graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceRegisterAllocationPhase.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceRegisterAllocationPhase.java	Fri Jul 24 10:55:33 2015 +0200
@@ -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.lsra;
+
+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.SSAUtils.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) {
+                SSIUtils.removeIncoming(lir, toBlock);
+            } else {
+                assert lir.getControlFlowGraph().getStartBlock().equals(toBlock);
+            }
+            SSIUtils.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);
+                                SSIUtils.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 681c04ce9db2 -r 06a9e6737dcf 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	Fri Jul 24 10:55:33 2015 +0200
@@ -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 681c04ce9db2 -r 06a9e6737dcf graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/SSIBlockValueMapImpl.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/SSIBlockValueMapImpl.java	Fri Jul 24 10:55:33 2015 +0200
@@ -0,0 +1,246 @@
+/*
+ * 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 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.util.*;
+
+public class SSIBlockValueMapImpl implements BlockValueMap {
+
+    private 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() {
+            valueIndexMap = new GenericValueMap<>();
+            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) {
+            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;
+
+    public SSIBlockValueMapImpl(AbstractControlFlowGraph<?> cfg) {
+        valueToDefBlock = new GenericValueMap<>();
+        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();
+            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 681c04ce9db2 -r 06a9e6737dcf 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	Fri Jul 24 16:20:56 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/AllocationStage.java	Fri Jul 24 10:55:33 2015 +0200
@@ -22,6 +22,7 @@
  */
 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.dfa.*;
 import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext;
@@ -30,7 +31,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 681c04ce9db2 -r 06a9e6737dcf 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	Fri Jul 24 16:20:56 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/PreAllocationOptimizationStage.java	Fri Jul 24 10:55:33 2015 +0200
@@ -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 681c04ce9db2 -r 06a9e6737dcf 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	Fri Jul 24 10:55:33 2015 +0200
@@ -0,0 +1,119 @@
+/*
+ * 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.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 SSAUtils.verifySSAForm(lirGenRes.getLIR());
+        LIR lir = lirGenRes.getLIR();
+        new SSIBuilder(lir).build(lirGen);
+    }
+
+    private static class SSIBuilder {
+        private final SSIBlockValueMapImpl valueMap;
+        private final LIR lir;
+        private final BitSet processed;
+
+        private SSIBuilder(LIR lir) {
+            this.lir = lir;
+            valueMap = new SSIBlockValueMapImpl(lir.getControlFlowGraph());
+            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 681c04ce9db2 -r 06a9e6737dcf graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIUtils.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIUtils.java	Fri Jul 24 10:55:33 2015 +0200
@@ -0,0 +1,113 @@
+/*
+ * 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.SSAUtils.*;
+
+public final class SSIUtils {
+
+    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.getSuccessors(), 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 681c04ce9db2 -r 06a9e6737dcf 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	Fri Jul 24 10:55:33 2015 +0200
@@ -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 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 = SSIUtils.outgoing(lir, from);
+        LabelOp in = SSIUtils.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 681c04ce9db2 -r 06a9e6737dcf mx.graal/suite.py
--- a/mx.graal/suite.py	Fri Jul 24 16:20:56 2015 +0200
+++ b/mx.graal/suite.py	Fri Jul 24 10:55:33 2015 +0200
@@ -568,10 +568,8 @@
       "subDir" : "graal",
       "sourceDirs" : ["src"],
       "dependencies" : [
-        "com.oracle.graal.debug",
         "com.oracle.graal.nodeinfo",
         "com.oracle.graal.compiler.common",
-        "com.oracle.graal.debug",
         "com.oracle.graal.api.collections",
         "com.oracle.graal.api.runtime",
       ],
@@ -665,7 +663,6 @@
       "sourceDirs" : ["src"],
       "dependencies" : [
         "com.oracle.graal.compiler.common",
-        "com.oracle.graal.debug",
         "com.oracle.graal.asm",
       ],
       "checkstyle" : "com.oracle.graal.graph",
@@ -992,10 +989,8 @@
       "subDir" : "graal",
       "sourceDirs" : ["src"],
       "dependencies" : [
-        "jdk.internal.jvmci.debug",
-        "jdk.internal.jvmci.options",
         "jdk.internal.jvmci.common",
-        "jdk.internal.jvmci.code",
+        "com.oracle.graal.debug",
       ],
       "annotationProcessors" : ["jdk.internal.jvmci.options.processor"],
       "checkstyle" : "com.oracle.graal.graph",