Mercurial > hg > truffle
changeset 21316:fd18bffefcc1
LinearScan: outsource LifetimeAnalysis.
| author | Josef Eisl <josef.eisl@jku.at> |
|---|---|
| date | Tue, 12 May 2015 10:58:26 +0200 |
| parents | 5f4847feeb69 |
| children | 15ec3912cffb |
| files | graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LifetimeAnalysis.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALifetimeAnalysis.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScan.java |
| diffstat | 4 files changed, 777 insertions(+), 677 deletions(-) [+] |
line wrap: on
line diff
--- /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); + } + } + } + } +}
--- 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
--- /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); + } + } + } +}
--- 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) {