# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1431421106 -7200
# Node ID fd18bffefcc1389611dcc921527bb17c192086c2
# Parent  5f4847feeb6919f2444e4c1bd48cdf71e79aa1b4
LinearScan: outsource LifetimeAnalysis.

diff -r 5f4847feeb69 -r fd18bffefcc1 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LifetimeAnalysis.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LifetimeAnalysis.java	Tue May 12 10:58:26 2015 +0200
@@ -0,0 +1,696 @@
+/*
+ * 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.api.code.ValueUtil.*;
+import static com.oracle.graal.compiler.common.GraalOptions.*;
+import static com.oracle.graal.lir.LIRValueUtil.*;
+import static com.oracle.graal.lir.debug.LIRGenerationDebugContext.*;
+
+import java.util.*;
+
+import com.oracle.graal.api.code.*;
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.compiler.common.*;
+import com.oracle.graal.compiler.common.alloc.*;
+import com.oracle.graal.compiler.common.cfg.*;
+import com.oracle.graal.compiler.common.util.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.debug.Debug.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.LIRInstruction.*;
+import com.oracle.graal.lir.StandardOp.*;
+import com.oracle.graal.lir.alloc.lsra.Interval.*;
+import com.oracle.graal.lir.alloc.lsra.LinearScan.*;
+import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.gen.LIRGeneratorTool.*;
+import com.oracle.graal.lir.phases.*;
+
+class LifetimeAnalysis extends AllocationPhase {
+
+    protected final LinearScan allocator;
+
+    /**
+     * @param linearScan
+     */
+    LifetimeAnalysis(LinearScan linearScan) {
+        allocator = linearScan;
+    }
+
+    @Override
+    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory) {
+        numberInstructions();
+        allocator.printLir("Before register allocation", true);
+        computeLocalLiveSets();
+        computeGlobalLiveSets();
+        buildIntervals();
+    }
+
+    /**
+     * Numbers all instructions in all blocks. The numbering follows the
+     * {@linkplain ComputeBlockOrder linear scan order}.
+     */
+    void numberInstructions() {
+
+        allocator.intervalsSize = allocator.operandSize();
+        allocator.intervals = new Interval[allocator.intervalsSize + (allocator.intervalsSize >> LinearScan.SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)];
+
+        ValueConsumer setVariableConsumer = (value, mode, flags) -> {
+            if (isVariable(value)) {
+                allocator.getOrCreateInterval(asVariable(value));
+            }
+        };
+
+        // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node.
+        int numInstructions = 0;
+        for (AbstractBlockBase<?> block : allocator.sortedBlocks) {
+            numInstructions += allocator.ir.getLIRforBlock(block).size();
+        }
+
+        // initialize with correct length
+        allocator.opIdToInstructionMap = new LIRInstruction[numInstructions];
+        allocator.opIdToBlockMap = new AbstractBlockBase<?>[numInstructions];
+
+        int opId = 0;
+        int index = 0;
+        for (AbstractBlockBase<?> block : allocator.sortedBlocks) {
+            allocator.blockData.put(block, new LinearScan.BlockData());
+
+            List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block);
+
+            int numInst = instructions.size();
+            for (int j = 0; j < numInst; j++) {
+                LIRInstruction op = instructions.get(j);
+                op.setId(opId);
+
+                allocator.opIdToInstructionMap[index] = op;
+                allocator.opIdToBlockMap[index] = block;
+                assert allocator.instructionForId(opId) == op : "must match";
+
+                op.visitEachTemp(setVariableConsumer);
+                op.visitEachOutput(setVariableConsumer);
+
+                index++;
+                opId += 2; // numbering of lirOps by two
+            }
+        }
+        assert index == numInstructions : "must match";
+        assert (index << 1) == opId : "must match: " + (index << 1);
+    }
+
+    /**
+     * Computes local live sets (i.e. {@link BlockData#liveGen} and {@link BlockData#liveKill})
+     * separately for each block.
+     */
+    void computeLocalLiveSets() {
+        int liveSize = allocator.liveSetSize();
+
+        allocator.intervalInLoop = new BitMap2D(allocator.operandSize(), allocator.numLoops());
+
+        // iterate all blocks
+        for (final AbstractBlockBase<?> block : allocator.sortedBlocks) {
+            try (Indent indent = Debug.logAndIndent("compute local live sets for block %s", block)) {
+
+                final BitSet liveGen = new BitSet(liveSize);
+                final BitSet liveKill = new BitSet(liveSize);
+
+                List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block);
+                int numInst = instructions.size();
+
+                ValueConsumer useConsumer = (operand, mode, flags) -> {
+                    if (isVariable(operand)) {
+                        int operandNum = allocator.operandNumber(operand);
+                        if (!liveKill.get(operandNum)) {
+                            liveGen.set(operandNum);
+                            if (Debug.isLogEnabled()) {
+                                Debug.log("liveGen for operand %d(%s)", operandNum, operand);
+                            }
+                        }
+                        if (block.getLoop() != null) {
+                            allocator.intervalInLoop.setBit(operandNum, block.getLoop().getIndex());
+                        }
+                    }
+
+                    if (DetailedAsserts.getValue()) {
+                        verifyInput(block, liveKill, operand);
+                    }
+                };
+                ValueConsumer stateConsumer = (operand, mode, flags) -> {
+                    if (LinearScan.isVariableOrRegister(operand)) {
+                        int operandNum = allocator.operandNumber(operand);
+                        if (!liveKill.get(operandNum)) {
+                            liveGen.set(operandNum);
+                            if (Debug.isLogEnabled()) {
+                                Debug.log("liveGen in state for operand %d(%s)", operandNum, operand);
+                            }
+                        }
+                    }
+                };
+                ValueConsumer defConsumer = (operand, mode, flags) -> {
+                    if (isVariable(operand)) {
+                        int varNum = allocator.operandNumber(operand);
+                        liveKill.set(varNum);
+                        if (Debug.isLogEnabled()) {
+                            Debug.log("liveKill for operand %d(%s)", varNum, operand);
+                        }
+                        if (block.getLoop() != null) {
+                            allocator.intervalInLoop.setBit(varNum, block.getLoop().getIndex());
+                        }
+                    }
+
+                    if (DetailedAsserts.getValue()) {
+                        // fixed intervals are never live at block boundaries, so
+                        // they need not be processed in live sets
+                        // process them only in debug mode so that this can be checked
+                        verifyTemp(liveKill, operand);
+                    }
+                };
+
+                // iterate all instructions of the block
+                for (int j = 0; j < numInst; j++) {
+                    final LIRInstruction op = instructions.get(j);
+
+                    try (Indent indent2 = Debug.logAndIndent("handle op %d", op.id())) {
+                        op.visitEachInput(useConsumer);
+                        op.visitEachAlive(useConsumer);
+                        // Add uses of live locals from interpreter's point of view for proper
+// debug
+                        // information generation
+                        op.visitEachState(stateConsumer);
+                        op.visitEachTemp(defConsumer);
+                        op.visitEachOutput(defConsumer);
+                    }
+                } // end of instruction iteration
+
+                BlockData blockSets = allocator.blockData.get(block);
+                blockSets.liveGen = liveGen;
+                blockSets.liveKill = liveKill;
+                blockSets.liveIn = new BitSet(liveSize);
+                blockSets.liveOut = new BitSet(liveSize);
+
+                if (Debug.isLogEnabled()) {
+                    Debug.log("liveGen  B%d %s", block.getId(), blockSets.liveGen);
+                    Debug.log("liveKill B%d %s", block.getId(), blockSets.liveKill);
+                }
+
+            }
+        } // end of block iteration
+    }
+
+    private void verifyTemp(BitSet liveKill, Value operand) {
+        // fixed intervals are never live at block boundaries, so
+        // they need not be processed in live sets
+        // process them only in debug mode so that this can be checked
+        if (isRegister(operand)) {
+            if (allocator.isProcessed(operand)) {
+                liveKill.set(allocator.operandNumber(operand));
+            }
+        }
+    }
+
+    private void verifyInput(AbstractBlockBase<?> block, BitSet liveKill, Value operand) {
+        // fixed intervals are never live at block boundaries, so
+        // they need not be processed in live sets.
+        // this is checked by these assertions to be sure about it.
+        // the entry block may have incoming
+        // values in registers, which is ok.
+        if (isRegister(operand) && block != allocator.ir.getControlFlowGraph().getStartBlock()) {
+            if (allocator.isProcessed(operand)) {
+                assert liveKill.get(allocator.operandNumber(operand)) : "using fixed register that is not defined in this block";
+            }
+        }
+    }
+
+    /**
+     * Performs a backward dataflow analysis to compute global live sets (i.e.
+     * {@link BlockData#liveIn} and {@link BlockData#liveOut}) for each block.
+     */
+    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.blockData.get(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()) {
+                                    liveOut.or(allocator.blockData.get(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.ir.getControlFlowGraph().getStartBlock();
+            if (allocator.blockData.get(startBlock).liveIn.cardinality() != 0) {
+                if (DetailedAsserts.getValue()) {
+                    reportFailure(numBlocks);
+                }
+                // bailout if this occurs in product mode.
+                throw new GraalInternalError("liveIn set of first block must be empty: " + allocator.blockData.get(startBlock).liveIn);
+            }
+        }
+    }
+
+    private void reportFailure(int numBlocks) {
+        try (Scope s = Debug.forceLog()) {
+            try (Indent indent = Debug.logAndIndent("report failure")) {
+
+                BitSet startBlockLiveIn = allocator.blockData.get(allocator.ir.getControlFlowGraph().getStartBlock()).liveIn;
+                try (Indent indent2 = Debug.logAndIndent("Error: liveIn set of first block must be empty (when this fails, variables are used before they are defined):")) {
+                    for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) {
+                        Interval interval = allocator.intervalFor(operandNum);
+                        if (interval != null) {
+                            Value operand = interval.operand;
+                            Debug.log("var %d; operand=%s; node=%s", operandNum, operand, getSourceForOperandFromDebugContext(operand));
+                        } else {
+                            Debug.log("var %d; missing operand", operandNum);
+                        }
+                    }
+                }
+
+                // print some additional information to simplify debugging
+                for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) {
+                    Interval interval = allocator.intervalFor(operandNum);
+                    Value operand = null;
+                    Object valueForOperandFromDebugContext = null;
+                    if (interval != null) {
+                        operand = interval.operand;
+                        valueForOperandFromDebugContext = getSourceForOperandFromDebugContext(operand);
+                    }
+                    try (Indent indent2 = Debug.logAndIndent("---- Detailed information for var %d; operand=%s; node=%s ----", operandNum, operand, valueForOperandFromDebugContext)) {
+
+                        Deque<AbstractBlockBase<?>> definedIn = new ArrayDeque<>();
+                        HashSet<AbstractBlockBase<?>> usedIn = new HashSet<>();
+                        for (AbstractBlockBase<?> block : allocator.sortedBlocks) {
+                            if (allocator.blockData.get(block).liveGen.get(operandNum)) {
+                                usedIn.add(block);
+                                try (Indent indent3 = Debug.logAndIndent("used in block B%d", block.getId())) {
+                                    for (LIRInstruction ins : allocator.ir.getLIRforBlock(block)) {
+                                        try (Indent indent4 = Debug.logAndIndent("%d: %s", ins.id(), ins)) {
+                                            ins.forEachState((liveStateOperand, mode, flags) -> {
+                                                Debug.log("operand=%s", liveStateOperand);
+                                                return liveStateOperand;
+                                            });
+                                        }
+                                    }
+                                }
+                            }
+                            if (allocator.blockData.get(block).liveKill.get(operandNum)) {
+                                definedIn.add(block);
+                                try (Indent indent3 = Debug.logAndIndent("defined in block B%d", block.getId())) {
+                                    for (LIRInstruction ins : allocator.ir.getLIRforBlock(block)) {
+                                        Debug.log("%d: %s", ins.id(), ins);
+                                    }
+                                }
+                            }
+                        }
+
+                        int[] hitCount = new int[numBlocks];
+
+                        while (!definedIn.isEmpty()) {
+                            AbstractBlockBase<?> block = definedIn.removeFirst();
+                            usedIn.remove(block);
+                            for (AbstractBlockBase<?> successor : block.getSuccessors()) {
+                                if (successor.isLoopHeader()) {
+                                    if (!block.isLoopEnd()) {
+                                        definedIn.add(successor);
+                                    }
+                                } else {
+                                    if (++hitCount[successor.getId()] == successor.getPredecessorCount()) {
+                                        definedIn.add(successor);
+                                    }
+                                }
+                            }
+                        }
+                        try (Indent indent3 = Debug.logAndIndent("**** offending usages are in: ")) {
+                            for (AbstractBlockBase<?> block : usedIn) {
+                                Debug.log("B%d", block.getId());
+                            }
+                        }
+                    }
+                }
+            }
+        } catch (Throwable e) {
+            throw Debug.handle(e);
+        }
+    }
+
+    private void verifyLiveness() {
+        // check that fixed intervals are not live at block boundaries
+        // (live set must be empty at fixed intervals)
+        for (AbstractBlockBase<?> block : allocator.sortedBlocks) {
+            for (int j = 0; j <= allocator.maxRegisterNumber(); j++) {
+                assert !allocator.blockData.get(block).liveIn.get(j) : "liveIn  set of fixed register must be empty";
+                assert !allocator.blockData.get(block).liveOut.get(j) : "liveOut set of fixed register must be empty";
+                assert !allocator.blockData.get(block).liveGen.get(j) : "liveGen set of fixed register must be empty";
+            }
+        }
+    }
+
+    void addUse(AllocatableValue operand, int from, int to, RegisterPriority registerPriority, LIRKind kind) {
+        if (!allocator.isProcessed(operand)) {
+            return;
+        }
+
+        Interval interval = allocator.getOrCreateInterval(operand);
+        if (!kind.equals(LIRKind.Illegal)) {
+            interval.setKind(kind);
+        }
+
+        interval.addRange(from, to);
+
+        // Register use position at even instruction id.
+        interval.addUsePos(to & ~1, registerPriority);
+
+        if (Debug.isLogEnabled()) {
+            Debug.log("add use: %s, from %d to %d (%s)", interval, from, to, registerPriority.name());
+        }
+    }
+
+    void addTemp(AllocatableValue operand, int tempPos, RegisterPriority registerPriority, LIRKind kind) {
+        if (!allocator.isProcessed(operand)) {
+            return;
+        }
+
+        Interval interval = allocator.getOrCreateInterval(operand);
+        if (!kind.equals(LIRKind.Illegal)) {
+            interval.setKind(kind);
+        }
+
+        interval.addRange(tempPos, tempPos + 1);
+        interval.addUsePos(tempPos, registerPriority);
+        interval.addMaterializationValue(null);
+
+        if (Debug.isLogEnabled()) {
+            Debug.log("add temp: %s tempPos %d (%s)", interval, tempPos, RegisterPriority.MustHaveRegister.name());
+        }
+    }
+
+    void addDef(AllocatableValue operand, LIRInstruction op, RegisterPriority registerPriority, LIRKind kind) {
+        if (!allocator.isProcessed(operand)) {
+            return;
+        }
+        int defPos = op.id();
+
+        Interval interval = allocator.getOrCreateInterval(operand);
+        if (!kind.equals(LIRKind.Illegal)) {
+            interval.setKind(kind);
+        }
+
+        Range r = interval.first();
+        if (r.from <= defPos) {
+            // Update the starting point (when a range is first created for a use, its
+            // start is the beginning of the current block until a def is encountered.)
+            r.from = defPos;
+            interval.addUsePos(defPos, registerPriority);
+
+        } else {
+            // Dead value - make vacuous interval
+            // also add register priority for dead intervals
+            interval.addRange(defPos, defPos + 1);
+            interval.addUsePos(defPos, registerPriority);
+            if (Debug.isLogEnabled()) {
+                Debug.log("Warning: def of operand %s at %d occurs without use", operand, defPos);
+            }
+        }
+
+        allocator.changeSpillDefinitionPos(interval, defPos);
+        if (registerPriority == RegisterPriority.None && interval.spillState().ordinal() <= SpillState.StartInMemory.ordinal() && isStackSlot(operand)) {
+            // detection of method-parameters and roundfp-results
+            interval.setSpillState(SpillState.StartInMemory);
+        }
+        interval.addMaterializationValue(LinearScan.getMaterializedValue(op, operand, interval));
+
+        if (Debug.isLogEnabled()) {
+            Debug.log("add def: %s defPos %d (%s)", interval, defPos, registerPriority.name());
+        }
+    }
+
+    /**
+     * Optimizes moves related to incoming stack based arguments. The interval for the destination
+     * of such moves is assigned the stack slot (which is in the caller's frame) as its spill slot.
+     */
+    void handleMethodArguments(LIRInstruction op) {
+        if (op instanceof MoveOp) {
+            MoveOp move = (MoveOp) op;
+            if (LinearScan.optimizeMethodArgument(move.getInput())) {
+                StackSlot slot = asStackSlot(move.getInput());
+                if (DetailedAsserts.getValue()) {
+                    assert op.id() > 0 : "invalid id";
+                    assert allocator.blockForId(op.id()).getPredecessorCount() == 0 : "move from stack must be in first block";
+                    assert isVariable(move.getResult()) : "result of move must be a variable";
+
+                    if (Debug.isLogEnabled()) {
+                        Debug.log("found move from stack slot %s to %s", slot, move.getResult());
+                    }
+                }
+
+                Interval interval = allocator.intervalFor(move.getResult());
+                interval.setSpillSlot(slot);
+                interval.assignLocation(slot);
+            }
+        }
+    }
+
+    void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) {
+        if (flags.contains(OperandFlag.HINT) && LinearScan.isVariableOrRegister(targetValue)) {
+
+            op.forEachRegisterHint(targetValue, mode, (registerHint, valueMode, valueFlags) -> {
+                if (LinearScan.isVariableOrRegister(registerHint)) {
+                    Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint);
+                    Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue);
+
+                    /* hints always point from def to use */
+                    if (hintAtDef) {
+                        to.setLocationHint(from);
+                    } else {
+                        from.setLocationHint(to);
+                    }
+                    if (Debug.isLogEnabled()) {
+                        Debug.log("operation at opId %d: added hint from interval %d to %d", op.id(), from.operandNumber, to.operandNumber);
+                    }
+
+                    return registerHint;
+                }
+                return null;
+            });
+        }
+    }
+
+    void buildIntervals() {
+
+        try (Indent indent = Debug.logAndIndent("build intervals")) {
+            InstructionValueConsumer outputConsumer = (op, operand, mode, flags) -> {
+                if (LinearScan.isVariableOrRegister(operand)) {
+                    addDef((AllocatableValue) operand, op, LinearScan.registerPriorityOfOutputOperand(op), operand.getLIRKind());
+                    addRegisterHint(op, operand, mode, flags, true);
+                }
+            };
+
+            InstructionValueConsumer tempConsumer = (op, operand, mode, flags) -> {
+                if (LinearScan.isVariableOrRegister(operand)) {
+                    addTemp((AllocatableValue) operand, op.id(), RegisterPriority.MustHaveRegister, operand.getLIRKind());
+                    addRegisterHint(op, operand, mode, flags, false);
+                }
+            };
+
+            InstructionValueConsumer aliveConsumer = (op, operand, mode, flags) -> {
+                if (LinearScan.isVariableOrRegister(operand)) {
+                    RegisterPriority p = LinearScan.registerPriorityOfInputOperand(flags);
+                    int opId = op.id();
+                    int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId)));
+                    addUse((AllocatableValue) operand, blockFrom, opId + 1, p, operand.getLIRKind());
+                    addRegisterHint(op, operand, mode, flags, false);
+                }
+            };
+
+            InstructionValueConsumer inputConsumer = (op, operand, mode, flags) -> {
+                if (LinearScan.isVariableOrRegister(operand)) {
+                    int opId = op.id();
+                    int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId)));
+                    RegisterPriority p = LinearScan.registerPriorityOfInputOperand(flags);
+                    addUse((AllocatableValue) operand, blockFrom, opId, p, operand.getLIRKind());
+                    addRegisterHint(op, operand, mode, flags, false);
+                }
+            };
+
+            InstructionValueConsumer stateProc = (op, operand, mode, flags) -> {
+                if (LinearScan.isVariableOrRegister(operand)) {
+                    int opId = op.id();
+                    int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId)));
+                    addUse((AllocatableValue) operand, blockFrom, opId + 1, RegisterPriority.None, operand.getLIRKind());
+                }
+            };
+
+            // create a list with all caller-save registers (cpu, fpu, xmm)
+            Register[] callerSaveRegs = allocator.regAllocConfig.getRegisterConfig().getCallerSaveRegisters();
+
+            // iterate all blocks in reverse order
+            for (int i = allocator.blockCount() - 1; i >= 0; i--) {
+
+                AbstractBlockBase<?> block = allocator.blockAt(i);
+                try (Indent indent2 = Debug.logAndIndent("handle block %d", block.getId())) {
+
+                    List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block);
+                    final int blockFrom = allocator.getFirstLirInstructionId(block);
+                    int blockTo = allocator.getLastLirInstructionId(block);
+
+                    assert blockFrom == instructions.get(0).id();
+                    assert blockTo == instructions.get(instructions.size() - 1).id();
+
+                    // Update intervals for operands live at the end of this block;
+                    BitSet live = allocator.blockData.get(block).liveOut;
+                    for (int operandNum = live.nextSetBit(0); operandNum >= 0; operandNum = live.nextSetBit(operandNum + 1)) {
+                        assert live.get(operandNum) : "should not stop here otherwise";
+                        AllocatableValue operand = allocator.intervalFor(operandNum).operand;
+                        if (Debug.isLogEnabled()) {
+                            Debug.log("live in %d: %s", operandNum, operand);
+                        }
+
+                        addUse(operand, blockFrom, blockTo + 2, RegisterPriority.None, LIRKind.Illegal);
+
+                        // add special use positions for loop-end blocks when the
+                        // interval is used anywhere inside this loop. It's possible
+                        // that the block was part of a non-natural loop, so it might
+                        // have an invalid loop index.
+                        if (block.isLoopEnd() && block.getLoop() != null && allocator.isIntervalInLoop(operandNum, block.getLoop().getIndex())) {
+                            allocator.intervalFor(operandNum).addUsePos(blockTo + 1, RegisterPriority.LiveAtLoopEnd);
+                        }
+                    }
+
+                    // iterate all instructions of the block in reverse order.
+                    // definitions of intervals are processed before uses
+                    for (int j = instructions.size() - 1; j >= 0; j--) {
+                        final LIRInstruction op = instructions.get(j);
+                        final int opId = op.id();
+
+                        try (Indent indent3 = Debug.logAndIndent("handle inst %d: %s", opId, op)) {
+
+                            // add a temp range for each register if operation destroys
+                            // caller-save registers
+                            if (op.destroysCallerSavedRegisters()) {
+                                for (Register r : callerSaveRegs) {
+                                    if (allocator.attributes(r).isAllocatable()) {
+                                        addTemp(r.asValue(), opId, RegisterPriority.None, LIRKind.Illegal);
+                                    }
+                                }
+                                if (Debug.isLogEnabled()) {
+                                    Debug.log("operation destroys all caller-save registers");
+                                }
+                            }
+
+                            op.visitEachOutput(outputConsumer);
+                            op.visitEachTemp(tempConsumer);
+                            op.visitEachAlive(aliveConsumer);
+                            op.visitEachInput(inputConsumer);
+
+                            // Add uses of live locals from interpreter's point of view for
+// proper
+                            // debug information generation
+                            // Treat these operands as temp values (if the live range is
+// extended
+                            // to a call site, the value would be in a register at
+                            // the call otherwise)
+                            op.visitEachState(stateProc);
+
+                            // special steps for some instructions (especially moves)
+                            handleMethodArguments(op);
+
+                        }
+
+                    } // end of instruction iteration
+                }
+            } // end of block iteration
+
+            // add the range [0, 1] to all fixed intervals.
+            // the register allocator need not handle unhandled fixed intervals
+            for (Interval interval : allocator.intervals) {
+                if (interval != null && isRegister(interval.operand)) {
+                    interval.addRange(0, 1);
+                }
+            }
+        }
+    }
+}
diff -r 5f4847feeb69 -r fd18bffefcc1 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java	Thu May 07 14:17:53 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java	Tue May 12 10:58:26 2015 +0200
@@ -27,7 +27,6 @@
 import static com.oracle.graal.compiler.common.GraalOptions.*;
 import static com.oracle.graal.compiler.common.cfg.AbstractControlFlowGraph.*;
 import static com.oracle.graal.lir.LIRValueUtil.*;
-import static com.oracle.graal.lir.debug.LIRGenerationDebugContext.*;
 
 import java.util.*;
 
@@ -38,7 +37,6 @@
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.compiler.common.util.*;
 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;
@@ -73,7 +71,7 @@
     final boolean callKillsRegisters;
 
     public static final int DOMINATOR_SPILL_MOVE_ID = -2;
-    private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1;
+    static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1;
 
     public static class Options {
         // @formatter:off
@@ -216,7 +214,7 @@
      * the {@linkplain Variable variables} and {@linkplain RegisterValue registers} being processed
      * by this allocator.
      */
-    private int operandNumber(Value operand) {
+    int operandNumber(Value operand) {
         if (isRegister(operand)) {
             int number = asRegister(operand).number;
             assert number < firstVariableNumber;
@@ -229,7 +227,7 @@
     /**
      * Gets the number of operands. This value will increase by 1 for new variable.
      */
-    private int operandSize() {
+    int operandSize() {
         return firstVariableNumber + ir.numVariables();
     }
 
@@ -667,448 +665,6 @@
     }
 
     /**
-     * Numbers all instructions in all blocks. The numbering follows the
-     * {@linkplain ComputeBlockOrder linear scan order}.
-     */
-    void numberInstructions() {
-
-        intervalsSize = operandSize();
-        intervals = new Interval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)];
-
-        ValueConsumer setVariableConsumer = (value, mode, flags) -> {
-            if (isVariable(value)) {
-                getOrCreateInterval(asVariable(value));
-            }
-        };
-
-        // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node.
-        int numInstructions = 0;
-        for (AbstractBlockBase<?> block : sortedBlocks) {
-            numInstructions += ir.getLIRforBlock(block).size();
-        }
-
-        // initialize with correct length
-        opIdToInstructionMap = new LIRInstruction[numInstructions];
-        opIdToBlockMap = new AbstractBlockBase<?>[numInstructions];
-
-        int opId = 0;
-        int index = 0;
-        for (AbstractBlockBase<?> block : sortedBlocks) {
-            blockData.put(block, new BlockData());
-
-            List<LIRInstruction> instructions = ir.getLIRforBlock(block);
-
-            int numInst = instructions.size();
-            for (int j = 0; j < numInst; j++) {
-                LIRInstruction op = instructions.get(j);
-                op.setId(opId);
-
-                opIdToInstructionMap[index] = op;
-                opIdToBlockMap[index] = block;
-                assert instructionForId(opId) == op : "must match";
-
-                op.visitEachTemp(setVariableConsumer);
-                op.visitEachOutput(setVariableConsumer);
-
-                index++;
-                opId += 2; // numbering of lirOps by two
-            }
-        }
-        assert index == numInstructions : "must match";
-        assert (index << 1) == opId : "must match: " + (index << 1);
-    }
-
-    /**
-     * Computes local live sets (i.e. {@link BlockData#liveGen} and {@link BlockData#liveKill})
-     * separately for each block.
-     */
-    void computeLocalLiveSets() {
-        int liveSize = liveSetSize();
-
-        intervalInLoop = new BitMap2D(operandSize(), numLoops());
-
-        // iterate all blocks
-        for (final AbstractBlockBase<?> block : sortedBlocks) {
-            try (Indent indent = Debug.logAndIndent("compute local live sets for block %s", block)) {
-
-                final BitSet liveGen = new BitSet(liveSize);
-                final BitSet liveKill = new BitSet(liveSize);
-
-                List<LIRInstruction> instructions = ir.getLIRforBlock(block);
-                int numInst = instructions.size();
-
-                ValueConsumer useConsumer = (operand, mode, flags) -> {
-                    if (isVariable(operand)) {
-                        int operandNum = operandNumber(operand);
-                        if (!liveKill.get(operandNum)) {
-                            liveGen.set(operandNum);
-                            if (Debug.isLogEnabled()) {
-                                Debug.log("liveGen for operand %d(%s)", operandNum, operand);
-                            }
-                        }
-                        if (block.getLoop() != null) {
-                            intervalInLoop.setBit(operandNum, block.getLoop().getIndex());
-                        }
-                    }
-
-                    if (DetailedAsserts.getValue()) {
-                        verifyInput(block, liveKill, operand);
-                    }
-                };
-                ValueConsumer stateConsumer = (operand, mode, flags) -> {
-                    if (isVariableOrRegister(operand)) {
-                        int operandNum = operandNumber(operand);
-                        if (!liveKill.get(operandNum)) {
-                            liveGen.set(operandNum);
-                            if (Debug.isLogEnabled()) {
-                                Debug.log("liveGen in state for operand %d(%s)", operandNum, operand);
-                            }
-                        }
-                    }
-                };
-                ValueConsumer defConsumer = (operand, mode, flags) -> {
-                    if (isVariable(operand)) {
-                        int varNum = operandNumber(operand);
-                        liveKill.set(varNum);
-                        if (Debug.isLogEnabled()) {
-                            Debug.log("liveKill for operand %d(%s)", varNum, operand);
-                        }
-                        if (block.getLoop() != null) {
-                            intervalInLoop.setBit(varNum, block.getLoop().getIndex());
-                        }
-                    }
-
-                    if (DetailedAsserts.getValue()) {
-                        // fixed intervals are never live at block boundaries, so
-                        // they need not be processed in live sets
-                        // process them only in debug mode so that this can be checked
-                        verifyTemp(liveKill, operand);
-                    }
-                };
-
-                // iterate all instructions of the block
-                for (int j = 0; j < numInst; j++) {
-                    final LIRInstruction op = instructions.get(j);
-
-                    try (Indent indent2 = Debug.logAndIndent("handle op %d", op.id())) {
-                        op.visitEachInput(useConsumer);
-                        op.visitEachAlive(useConsumer);
-                        // Add uses of live locals from interpreter's point of view for proper debug
-                        // information generation
-                        op.visitEachState(stateConsumer);
-                        op.visitEachTemp(defConsumer);
-                        op.visitEachOutput(defConsumer);
-                    }
-                } // end of instruction iteration
-
-                BlockData blockSets = blockData.get(block);
-                blockSets.liveGen = liveGen;
-                blockSets.liveKill = liveKill;
-                blockSets.liveIn = new BitSet(liveSize);
-                blockSets.liveOut = new BitSet(liveSize);
-
-                if (Debug.isLogEnabled()) {
-                    Debug.log("liveGen  B%d %s", block.getId(), blockSets.liveGen);
-                    Debug.log("liveKill B%d %s", block.getId(), blockSets.liveKill);
-                }
-
-            }
-        } // end of block iteration
-    }
-
-    private void verifyTemp(BitSet liveKill, Value operand) {
-        // fixed intervals are never live at block boundaries, so
-        // they need not be processed in live sets
-        // process them only in debug mode so that this can be checked
-        if (isRegister(operand)) {
-            if (isProcessed(operand)) {
-                liveKill.set(operandNumber(operand));
-            }
-        }
-    }
-
-    private void verifyInput(AbstractBlockBase<?> block, BitSet liveKill, Value operand) {
-        // fixed intervals are never live at block boundaries, so
-        // they need not be processed in live sets.
-        // this is checked by these assertions to be sure about it.
-        // the entry block may have incoming
-        // values in registers, which is ok.
-        if (isRegister(operand) && block != ir.getControlFlowGraph().getStartBlock()) {
-            if (isProcessed(operand)) {
-                assert liveKill.get(operandNumber(operand)) : "using fixed register that is not defined in this block";
-            }
-        }
-    }
-
-    /**
-     * Performs a backward dataflow analysis to compute global live sets (i.e.
-     * {@link BlockData#liveIn} and {@link BlockData#liveOut}) for each block.
-     */
-    void computeGlobalLiveSets() {
-        try (Indent indent = Debug.logAndIndent("compute global live sets")) {
-            int numBlocks = blockCount();
-            boolean changeOccurred;
-            boolean changeOccurredInBlock;
-            int iterationCount = 0;
-            BitSet liveOut = new BitSet(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 = blockAt(i);
-                        BlockData blockSets = blockData.get(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()) {
-                                    liveOut.or(blockData.get(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 = ir.getControlFlowGraph().getStartBlock();
-            if (blockData.get(startBlock).liveIn.cardinality() != 0) {
-                if (DetailedAsserts.getValue()) {
-                    reportFailure(numBlocks);
-                }
-                // bailout if this occurs in product mode.
-                throw new GraalInternalError("liveIn set of first block must be empty: " + blockData.get(startBlock).liveIn);
-            }
-        }
-    }
-
-    private void reportFailure(int numBlocks) {
-        try (Scope s = Debug.forceLog()) {
-            try (Indent indent = Debug.logAndIndent("report failure")) {
-
-                BitSet startBlockLiveIn = blockData.get(ir.getControlFlowGraph().getStartBlock()).liveIn;
-                try (Indent indent2 = Debug.logAndIndent("Error: liveIn set of first block must be empty (when this fails, variables are used before they are defined):")) {
-                    for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) {
-                        Interval interval = intervalFor(operandNum);
-                        if (interval != null) {
-                            Value operand = interval.operand;
-                            Debug.log("var %d; operand=%s; node=%s", operandNum, operand, getSourceForOperandFromDebugContext(operand));
-                        } else {
-                            Debug.log("var %d; missing operand", operandNum);
-                        }
-                    }
-                }
-
-                // print some additional information to simplify debugging
-                for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) {
-                    Interval interval = intervalFor(operandNum);
-                    Value operand = null;
-                    Object valueForOperandFromDebugContext = null;
-                    if (interval != null) {
-                        operand = interval.operand;
-                        valueForOperandFromDebugContext = getSourceForOperandFromDebugContext(operand);
-                    }
-                    try (Indent indent2 = Debug.logAndIndent("---- Detailed information for var %d; operand=%s; node=%s ----", operandNum, operand, valueForOperandFromDebugContext)) {
-
-                        Deque<AbstractBlockBase<?>> definedIn = new ArrayDeque<>();
-                        HashSet<AbstractBlockBase<?>> usedIn = new HashSet<>();
-                        for (AbstractBlockBase<?> block : sortedBlocks) {
-                            if (blockData.get(block).liveGen.get(operandNum)) {
-                                usedIn.add(block);
-                                try (Indent indent3 = Debug.logAndIndent("used in block B%d", block.getId())) {
-                                    for (LIRInstruction ins : ir.getLIRforBlock(block)) {
-                                        try (Indent indent4 = Debug.logAndIndent("%d: %s", ins.id(), ins)) {
-                                            ins.forEachState((liveStateOperand, mode, flags) -> {
-                                                Debug.log("operand=%s", liveStateOperand);
-                                                return liveStateOperand;
-                                            });
-                                        }
-                                    }
-                                }
-                            }
-                            if (blockData.get(block).liveKill.get(operandNum)) {
-                                definedIn.add(block);
-                                try (Indent indent3 = Debug.logAndIndent("defined in block B%d", block.getId())) {
-                                    for (LIRInstruction ins : ir.getLIRforBlock(block)) {
-                                        Debug.log("%d: %s", ins.id(), ins);
-                                    }
-                                }
-                            }
-                        }
-
-                        int[] hitCount = new int[numBlocks];
-
-                        while (!definedIn.isEmpty()) {
-                            AbstractBlockBase<?> block = definedIn.removeFirst();
-                            usedIn.remove(block);
-                            for (AbstractBlockBase<?> successor : block.getSuccessors()) {
-                                if (successor.isLoopHeader()) {
-                                    if (!block.isLoopEnd()) {
-                                        definedIn.add(successor);
-                                    }
-                                } else {
-                                    if (++hitCount[successor.getId()] == successor.getPredecessorCount()) {
-                                        definedIn.add(successor);
-                                    }
-                                }
-                            }
-                        }
-                        try (Indent indent3 = Debug.logAndIndent("**** offending usages are in: ")) {
-                            for (AbstractBlockBase<?> block : usedIn) {
-                                Debug.log("B%d", block.getId());
-                            }
-                        }
-                    }
-                }
-            }
-        } catch (Throwable e) {
-            throw Debug.handle(e);
-        }
-    }
-
-    private void verifyLiveness() {
-        // check that fixed intervals are not live at block boundaries
-        // (live set must be empty at fixed intervals)
-        for (AbstractBlockBase<?> block : sortedBlocks) {
-            for (int j = 0; j <= maxRegisterNumber(); j++) {
-                assert !blockData.get(block).liveIn.get(j) : "liveIn  set of fixed register must be empty";
-                assert !blockData.get(block).liveOut.get(j) : "liveOut set of fixed register must be empty";
-                assert !blockData.get(block).liveGen.get(j) : "liveGen set of fixed register must be empty";
-            }
-        }
-    }
-
-    void addUse(AllocatableValue operand, int from, int to, RegisterPriority registerPriority, LIRKind kind) {
-        if (!isProcessed(operand)) {
-            return;
-        }
-
-        Interval interval = getOrCreateInterval(operand);
-        if (!kind.equals(LIRKind.Illegal)) {
-            interval.setKind(kind);
-        }
-
-        interval.addRange(from, to);
-
-        // Register use position at even instruction id.
-        interval.addUsePos(to & ~1, registerPriority);
-
-        if (Debug.isLogEnabled()) {
-            Debug.log("add use: %s, from %d to %d (%s)", interval, from, to, registerPriority.name());
-        }
-    }
-
-    void addTemp(AllocatableValue operand, int tempPos, RegisterPriority registerPriority, LIRKind kind) {
-        if (!isProcessed(operand)) {
-            return;
-        }
-
-        Interval interval = getOrCreateInterval(operand);
-        if (!kind.equals(LIRKind.Illegal)) {
-            interval.setKind(kind);
-        }
-
-        interval.addRange(tempPos, tempPos + 1);
-        interval.addUsePos(tempPos, registerPriority);
-        interval.addMaterializationValue(null);
-
-        if (Debug.isLogEnabled()) {
-            Debug.log("add temp: %s tempPos %d (%s)", interval, tempPos, RegisterPriority.MustHaveRegister.name());
-        }
-    }
-
-    boolean isProcessed(Value operand) {
-        return !isRegister(operand) || attributes(asRegister(operand)).isAllocatable();
-    }
-
-    void addDef(AllocatableValue operand, LIRInstruction op, RegisterPriority registerPriority, LIRKind kind) {
-        if (!isProcessed(operand)) {
-            return;
-        }
-        int defPos = op.id();
-
-        Interval interval = getOrCreateInterval(operand);
-        if (!kind.equals(LIRKind.Illegal)) {
-            interval.setKind(kind);
-        }
-
-        Range r = interval.first();
-        if (r.from <= defPos) {
-            // Update the starting point (when a range is first created for a use, its
-            // start is the beginning of the current block until a def is encountered.)
-            r.from = defPos;
-            interval.addUsePos(defPos, registerPriority);
-
-        } else {
-            // Dead value - make vacuous interval
-            // also add register priority for dead intervals
-            interval.addRange(defPos, defPos + 1);
-            interval.addUsePos(defPos, registerPriority);
-            if (Debug.isLogEnabled()) {
-                Debug.log("Warning: def of operand %s at %d occurs without use", operand, defPos);
-            }
-        }
-
-        changeSpillDefinitionPos(interval, defPos);
-        if (registerPriority == RegisterPriority.None && interval.spillState().ordinal() <= SpillState.StartInMemory.ordinal() && isStackSlot(operand)) {
-            // detection of method-parameters and roundfp-results
-            interval.setSpillState(SpillState.StartInMemory);
-        }
-        interval.addMaterializationValue(LinearScan.getMaterializedValue(op, operand, interval));
-
-        if (Debug.isLogEnabled()) {
-            Debug.log("add def: %s defPos %d (%s)", interval, defPos, registerPriority.name());
-        }
-    }
-
-    /**
      * Determines the register priority for an instruction's output/result operand.
      */
     static RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) {
@@ -1140,7 +696,7 @@
         return RegisterPriority.MustHaveRegister;
     }
 
-    private static boolean optimizeMethodArgument(Value value) {
+    static boolean optimizeMethodArgument(Value value) {
         /*
          * Object method arguments that are passed on the stack are currently not optimized because
          * this requires that the runtime visits method arguments during stack walking.
@@ -1148,188 +704,8 @@
         return isStackSlot(value) && asStackSlot(value).isInCallerFrame() && value.getKind() != Kind.Object;
     }
 
-    /**
-     * Optimizes moves related to incoming stack based arguments. The interval for the destination
-     * of such moves is assigned the stack slot (which is in the caller's frame) as its spill slot.
-     */
-    void handleMethodArguments(LIRInstruction op) {
-        if (op instanceof MoveOp) {
-            MoveOp move = (MoveOp) op;
-            if (optimizeMethodArgument(move.getInput())) {
-                StackSlot slot = asStackSlot(move.getInput());
-                if (DetailedAsserts.getValue()) {
-                    assert op.id() > 0 : "invalid id";
-                    assert blockForId(op.id()).getPredecessorCount() == 0 : "move from stack must be in first block";
-                    assert isVariable(move.getResult()) : "result of move must be a variable";
-
-                    if (Debug.isLogEnabled()) {
-                        Debug.log("found move from stack slot %s to %s", slot, move.getResult());
-                    }
-                }
-
-                Interval interval = intervalFor(move.getResult());
-                interval.setSpillSlot(slot);
-                interval.assignLocation(slot);
-            }
-        }
-    }
-
-    void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) {
-        if (flags.contains(OperandFlag.HINT) && isVariableOrRegister(targetValue)) {
-
-            op.forEachRegisterHint(targetValue, mode, (registerHint, valueMode, valueFlags) -> {
-                if (isVariableOrRegister(registerHint)) {
-                    Interval from = getOrCreateInterval((AllocatableValue) registerHint);
-                    Interval to = getOrCreateInterval((AllocatableValue) targetValue);
-
-                    /* hints always point from def to use */
-                    if (hintAtDef) {
-                        to.setLocationHint(from);
-                    } else {
-                        from.setLocationHint(to);
-                    }
-                    if (Debug.isLogEnabled()) {
-                        Debug.log("operation at opId %d: added hint from interval %d to %d", op.id(), from.operandNumber, to.operandNumber);
-                    }
-
-                    return registerHint;
-                }
-                return null;
-            });
-        }
-    }
-
-    void buildIntervals() {
-
-        try (Indent indent = Debug.logAndIndent("build intervals")) {
-            InstructionValueConsumer outputConsumer = (op, operand, mode, flags) -> {
-                if (isVariableOrRegister(operand)) {
-                    addDef((AllocatableValue) operand, op, registerPriorityOfOutputOperand(op), operand.getLIRKind());
-                    addRegisterHint(op, operand, mode, flags, true);
-                }
-            };
-
-            InstructionValueConsumer tempConsumer = (op, operand, mode, flags) -> {
-                if (isVariableOrRegister(operand)) {
-                    addTemp((AllocatableValue) operand, op.id(), RegisterPriority.MustHaveRegister, operand.getLIRKind());
-                    addRegisterHint(op, operand, mode, flags, false);
-                }
-            };
-
-            InstructionValueConsumer aliveConsumer = (op, operand, mode, flags) -> {
-                if (isVariableOrRegister(operand)) {
-                    RegisterPriority p = registerPriorityOfInputOperand(flags);
-                    int opId = op.id();
-                    int blockFrom = getFirstLirInstructionId((blockForId(opId)));
-                    addUse((AllocatableValue) operand, blockFrom, opId + 1, p, operand.getLIRKind());
-                    addRegisterHint(op, operand, mode, flags, false);
-                }
-            };
-
-            InstructionValueConsumer inputConsumer = (op, operand, mode, flags) -> {
-                if (isVariableOrRegister(operand)) {
-                    int opId = op.id();
-                    int blockFrom = getFirstLirInstructionId((blockForId(opId)));
-                    RegisterPriority p = registerPriorityOfInputOperand(flags);
-                    addUse((AllocatableValue) operand, blockFrom, opId, p, operand.getLIRKind());
-                    addRegisterHint(op, operand, mode, flags, false);
-                }
-            };
-
-            InstructionValueConsumer stateProc = (op, operand, mode, flags) -> {
-                if (isVariableOrRegister(operand)) {
-                    int opId = op.id();
-                    int blockFrom = getFirstLirInstructionId((blockForId(opId)));
-                    addUse((AllocatableValue) operand, blockFrom, opId + 1, RegisterPriority.None, operand.getLIRKind());
-                }
-            };
-
-            // create a list with all caller-save registers (cpu, fpu, xmm)
-            Register[] callerSaveRegs = regAllocConfig.getRegisterConfig().getCallerSaveRegisters();
-
-            // iterate all blocks in reverse order
-            for (int i = blockCount() - 1; i >= 0; i--) {
-
-                AbstractBlockBase<?> block = blockAt(i);
-                try (Indent indent2 = Debug.logAndIndent("handle block %d", block.getId())) {
-
-                    List<LIRInstruction> instructions = ir.getLIRforBlock(block);
-                    final int blockFrom = getFirstLirInstructionId(block);
-                    int blockTo = getLastLirInstructionId(block);
-
-                    assert blockFrom == instructions.get(0).id();
-                    assert blockTo == instructions.get(instructions.size() - 1).id();
-
-                    // Update intervals for operands live at the end of this block;
-                    BitSet live = blockData.get(block).liveOut;
-                    for (int operandNum = live.nextSetBit(0); operandNum >= 0; operandNum = live.nextSetBit(operandNum + 1)) {
-                        assert live.get(operandNum) : "should not stop here otherwise";
-                        AllocatableValue operand = intervalFor(operandNum).operand;
-                        if (Debug.isLogEnabled()) {
-                            Debug.log("live in %d: %s", operandNum, operand);
-                        }
-
-                        addUse(operand, blockFrom, blockTo + 2, RegisterPriority.None, LIRKind.Illegal);
-
-                        // add special use positions for loop-end blocks when the
-                        // interval is used anywhere inside this loop. It's possible
-                        // that the block was part of a non-natural loop, so it might
-                        // have an invalid loop index.
-                        if (block.isLoopEnd() && block.getLoop() != null && isIntervalInLoop(operandNum, block.getLoop().getIndex())) {
-                            intervalFor(operandNum).addUsePos(blockTo + 1, RegisterPriority.LiveAtLoopEnd);
-                        }
-                    }
-
-                    // iterate all instructions of the block in reverse order.
-                    // definitions of intervals are processed before uses
-                    for (int j = instructions.size() - 1; j >= 0; j--) {
-                        final LIRInstruction op = instructions.get(j);
-                        final int opId = op.id();
-
-                        try (Indent indent3 = Debug.logAndIndent("handle inst %d: %s", opId, op)) {
-
-                            // add a temp range for each register if operation destroys
-                            // caller-save registers
-                            if (op.destroysCallerSavedRegisters()) {
-                                for (Register r : callerSaveRegs) {
-                                    if (attributes(r).isAllocatable()) {
-                                        addTemp(r.asValue(), opId, RegisterPriority.None, LIRKind.Illegal);
-                                    }
-                                }
-                                if (Debug.isLogEnabled()) {
-                                    Debug.log("operation destroys all caller-save registers");
-                                }
-                            }
-
-                            op.visitEachOutput(outputConsumer);
-                            op.visitEachTemp(tempConsumer);
-                            op.visitEachAlive(aliveConsumer);
-                            op.visitEachInput(inputConsumer);
-
-                            // Add uses of live locals from interpreter's point of view for proper
-                            // debug information generation
-                            // Treat these operands as temp values (if the live range is extended
-                            // to a call site, the value would be in a register at
-                            // the call otherwise)
-                            op.visitEachState(stateProc);
-
-                            // special steps for some instructions (especially moves)
-                            handleMethodArguments(op);
-
-                        }
-
-                    } // end of instruction iteration
-                }
-            } // end of block iteration
-
-            // add the range [0, 1] to all fixed intervals.
-            // the register allocator need not handle unhandled fixed intervals
-            for (Interval interval : intervals) {
-                if (interval != null && isRegister(interval.operand)) {
-                    interval.addRange(0, 1);
-                }
-            }
-        }
+    boolean isProcessed(Value operand) {
+        return !isRegister(operand) || attributes(asRegister(operand)).isAllocatable();
     }
 
     // * Phase 5: actual register allocation
@@ -1864,20 +1240,6 @@
         }
     }
 
-    private final class LifetimeAnalysis extends AllocationPhase {
-
-        @Override
-        protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder,
-                        SpillMoveFactory spillMoveFactory) {
-            numberInstructions();
-            printLir("Before register allocation", true);
-            computeLocalLiveSets();
-            computeGlobalLiveSets();
-            buildIntervals();
-        }
-
-    }
-
     private final class RegisterAllocation extends AllocationPhase {
 
         @Override
diff -r 5f4847feeb69 -r fd18bffefcc1 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALifetimeAnalysis.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALifetimeAnalysis.java	Tue May 12 10:58:26 2015 +0200
@@ -0,0 +1,73 @@
+/*
+ * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.lir.alloc.lsra;
+
+import java.util.*;
+
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.LIRInstruction.*;
+import com.oracle.graal.lir.StandardOp.*;
+import com.oracle.graal.lir.ssa.*;
+
+public class SSALifetimeAnalysis extends LifetimeAnalysis {
+
+    SSALifetimeAnalysis(LinearScan linearScan) {
+        super(linearScan);
+    }
+
+    @Override
+    void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) {
+        super.addRegisterHint(op, targetValue, mode, flags, hintAtDef);
+
+        if (hintAtDef && op instanceof LabelOp) {
+            LabelOp label = (LabelOp) op;
+
+            Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue);
+
+            SSAUtils.forEachPhiRegisterHint(allocator.ir, allocator.blockForId(label.id()), label, targetValue, mode, (ValueConsumer) (registerHint, valueMode, valueFlags) -> {
+                if (LinearScan.isVariableOrRegister(registerHint)) {
+                    Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint);
+
+                    setHint(op, to, from);
+                    setHint(op, from, to);
+                }
+            });
+        }
+    }
+
+    private static void setHint(final LIRInstruction op, Interval target, Interval source) {
+        Interval currentHint = target.locationHint(false);
+        if (currentHint == null || currentHint.from() > target.from()) {
+            /*
+             * Update hint if there was none or if the hint interval starts after the hinted
+             * interval.
+             */
+            target.setLocationHint(source);
+            if (Debug.isLogEnabled()) {
+                Debug.log("operation at opId %d: added hint from interval %d to %d", op.id(), source.operandNumber, target.operandNumber);
+            }
+        }
+    }
+}
diff -r 5f4847feeb69 -r fd18bffefcc1 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScan.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScan.java	Thu May 07 14:17:53 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScan.java	Tue May 12 10:58:26 2015 +0200
@@ -34,8 +34,6 @@
 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.LabelOp;
 import com.oracle.graal.lir.StandardOp.MoveOp;
 import com.oracle.graal.lir.gen.*;
@@ -136,37 +134,8 @@
     }
 
     @Override
-    void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) {
-        super.addRegisterHint(op, targetValue, mode, flags, hintAtDef);
-
-        if (hintAtDef && op instanceof LabelOp) {
-            LabelOp label = (LabelOp) op;
-
-            Interval to = getOrCreateInterval((AllocatableValue) targetValue);
-
-            SSAUtils.forEachPhiRegisterHint(ir, blockForId(label.id()), label, targetValue, mode, (ValueConsumer) (registerHint, valueMode, valueFlags) -> {
-                if (isVariableOrRegister(registerHint)) {
-                    Interval from = getOrCreateInterval((AllocatableValue) registerHint);
-
-                    setHint(op, to, from);
-                    setHint(op, from, to);
-                }
-            });
-        }
-    }
-
-    private static void setHint(final LIRInstruction op, Interval target, Interval source) {
-        Interval currentHint = target.locationHint(false);
-        if (currentHint == null || currentHint.from() > target.from()) {
-            /*
-             * Update hint if there was none or if the hint interval starts after the hinted
-             * interval.
-             */
-            target.setLocationHint(source);
-            if (Debug.isLogEnabled()) {
-                Debug.log("operation at opId %d: added hint from interval %d to %d", op.id(), source.operandNumber, target.operandNumber);
-            }
-        }
+    protected LifetimeAnalysis createLifetimeAnalysis() {
+        return new SSALifetimeAnalysis(this);
     }
 
     private boolean isPhiResolutionMove(AbstractBlockBase<?> block, MoveOp move, Interval toInterval) {