Mercurial > hg > graal-compiler
changeset 22352:e6ea77e2a770
Move different register allocators into sub-packages.
line wrap: on
line diff
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/Interval.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/Interval.java Fri Jul 24 09:21:04 2015 +0200 @@ -292,7 +292,7 @@ /** * Constants used in optimization of spilling of an interval. */ - enum SpillState { + public enum SpillState { /** * Starting state of calculation: no definition found yet. */ @@ -578,7 +578,7 @@ return first; } - int from() { + public int from() { return first.from; } @@ -594,11 +594,11 @@ return usePosList.size(); } - void setLocationHint(Interval interval) { + public void setLocationHint(Interval interval) { locationHint = interval; } - boolean isSplitParent() { + public boolean isSplitParent() { return splitParent == this; } @@ -647,22 +647,22 @@ return splitParent().spillState; } - int spillDefinitionPos() { + public int spillDefinitionPos() { return splitParent().spillDefinitionPos; } - void setSpillState(SpillState state) { + public void setSpillState(SpillState state) { assert state.ordinal() >= spillState().ordinal() : "state cannot decrease"; splitParent().spillState = state; } - void setSpillDefinitionPos(int pos) { + public void setSpillDefinitionPos(int pos) { assert spillState() == SpillState.SpillInDominator || spillState() == SpillState.NoDefinitionFound || spillDefinitionPos() == -1 : "cannot set the position twice"; splitParent().spillDefinitionPos = pos; } // returns true if this interval has a shadow copy on the stack that is always correct - boolean alwaysInMemory() { + public boolean alwaysInMemory() { return (splitParent().spillState == SpillState.SpillInDominator || splitParent().spillState == SpillState.StoreAtDefinition || splitParent().spillState == SpillState.StartInMemory) && !canMaterialize(); } @@ -1052,7 +1052,7 @@ } } - void addRange(int from, int to) { + public void addRange(int from, int to) { assert from < to : "invalid range"; assert first() == Range.EndMarker || to < first().next.from : "not inserting at begin of interval"; assert from <= first().to : "not inserting at begin of interval";
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java Fri Jul 24 09:21:04 2015 +0200 @@ -53,11 +53,11 @@ * >"Optimized Interval Splitting in a Linear Scan Register Allocator"</a> by Christian Wimmer and * Hanspeter Moessenboeck. */ -class LinearScan { +public class LinearScan { final LIRGenerationResult res; - final LIR ir; - final FrameMapBuilder frameMapBuilder; + private final LIR ir; + private final FrameMapBuilder frameMapBuilder; final RegisterAttributes[] registerAttributes; final Register[] registers; final RegisterAllocationConfig regAllocConfig; @@ -112,7 +112,7 @@ /** * List of blocks in linear-scan order. This is only correct as long as the CFG does not change. */ - final List<? extends AbstractBlockBase<?>> sortedBlocks; + private final List<? extends AbstractBlockBase<?>> sortedBlocks; /** @see #intervals() */ protected Interval[] intervals; @@ -152,7 +152,8 @@ */ private final int firstVariableNumber; - LinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, List<? extends AbstractBlockBase<?>> sortedBlocks) { + protected LinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, + List<? extends AbstractBlockBase<?>> sortedBlocks) { this.res = res; this.ir = res.getLIR(); this.moveFactory = spillMoveFactory; @@ -172,20 +173,20 @@ this.callKillsRegisters = regAllocConfig.getRegisterConfig().areAllAllocatableRegistersCallerSaved(); } - int getFirstLirInstructionId(AbstractBlockBase<?> block) { + public int getFirstLirInstructionId(AbstractBlockBase<?> block) { int result = ir.getLIRforBlock(block).get(0).id(); assert result >= 0; return result; } - int getLastLirInstructionId(AbstractBlockBase<?> block) { + public int getLastLirInstructionId(AbstractBlockBase<?> block) { List<LIRInstruction> instructions = ir.getLIRforBlock(block); int result = instructions.get(instructions.size() - 1).id(); assert result >= 0; return result; } - SpillMoveFactory getSpillMoveFactory() { + public SpillMoveFactory getSpillMoveFactory() { return moveFactory; } @@ -228,7 +229,7 @@ return firstVariableNumber - 1; } - BlockData getBlockData(AbstractBlockBase<?> block) { + public BlockData getBlockData(AbstractBlockBase<?> block) { return blockData.get(block); } @@ -287,7 +288,7 @@ /** * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals. */ - Interval[] intervals() { + public Interval[] intervals() { return intervals; } @@ -334,11 +335,11 @@ } // access to block list (sorted in linear scan order) - int blockCount() { + public int blockCount() { return sortedBlocks.size(); } - AbstractBlockBase<?> blockAt(int index) { + public AbstractBlockBase<?> blockAt(int index) { return sortedBlocks.get(index); } @@ -347,7 +348,7 @@ * block. These sets do not include any operands allocated as a result of creating * {@linkplain #createDerivedInterval(Interval) derived intervals}. */ - int liveSetSize() { + public int liveSetSize() { return firstDerivedIntervalIndex == -1 ? operandSize() : firstDerivedIntervalIndex; } @@ -359,13 +360,13 @@ return intervals[operandNumber]; } - Interval intervalFor(Value operand) { + public Interval intervalFor(Value operand) { int operandNumber = operandNumber(operand); assert operandNumber < intervalsSize; return intervals[operandNumber]; } - Interval getOrCreateInterval(AllocatableValue operand) { + public Interval getOrCreateInterval(AllocatableValue operand) { Interval ret = intervalFor(operand); if (ret == null) { return createInterval(operand); @@ -407,7 +408,7 @@ * @param opId an instruction {@linkplain LIRInstruction#id id} * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id} */ - LIRInstruction instructionForId(int opId) { + public LIRInstruction instructionForId(int opId) { assert isEven(opId) : "opId not even"; LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)]; assert instr.id() == opId; @@ -420,7 +421,7 @@ * @param opId an instruction {@linkplain LIRInstruction#id id} * @return the block containing the instruction denoted by {@code opId} */ - AbstractBlockBase<?> blockForId(int opId) { + public AbstractBlockBase<?> blockForId(int opId) { assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range"; return opIdToBlockMap[opIdToIndex(opId)]; } @@ -515,7 +516,7 @@ return new Interval.Pair(list1, list2); } - void sortIntervalsBeforeAllocation() { + protected void sortIntervalsBeforeAllocation() { int sortedLen = 0; for (Interval interval : intervals) { if (interval != null) { @@ -585,7 +586,7 @@ // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode // instead of returning null - Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) { + public Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) { Interval result = interval.getSplitChildAtOpId(opId, mode, this); if (result != null) { @@ -622,8 +623,8 @@ return attributes(asRegister(operand)).isCallerSave(); } - <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory, - RegisterAllocationConfig registerAllocationConfig) { + protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, + SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) { /* * This is the point to enable debug logging for the whole register allocation. @@ -688,7 +689,7 @@ return new LinearScanAssignLocationsPhase(this); } - void printIntervals(String label) { + protected void printIntervals(String label) { if (Debug.isLogEnabled()) { try (Indent indent = Debug.logAndIndent("intervals %s", label)) { for (Interval interval : intervals) { @@ -708,7 +709,7 @@ Debug.dump(Arrays.copyOf(intervals, intervalsSize), label); } - void printLir(String label, @SuppressWarnings("unused") boolean hirValid) { + protected void printLir(String label, @SuppressWarnings("unused") boolean hirValid) { Debug.dump(ir, label); } @@ -731,7 +732,7 @@ } } - void verifyIntervals() { + protected void verifyIntervals() { try (Indent indent = Debug.logAndIndent("verifying intervals")) { int len = intervalsSize; @@ -872,4 +873,16 @@ } } + public LIR getLIR() { + return ir; + } + + public FrameMapBuilder getFrameMapBuilder() { + return frameMapBuilder; + } + + public List<? extends AbstractBlockBase<?>> sortedBlocks() { + return sortedBlocks; + } + }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanAssignLocationsPhase.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanAssignLocationsPhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -45,7 +45,7 @@ /** * Phase 7: Assign register numbers back to LIR. */ -final class LinearScanAssignLocationsPhase extends AllocationPhase { +public final class LinearScanAssignLocationsPhase extends AllocationPhase { private final LinearScan allocator; @@ -80,7 +80,7 @@ * before the branch instruction. So the split child information for this branch * would be incorrect. */ - LIRInstruction instr = allocator.ir.getLIRforBlock(block).get(allocator.ir.getLIRforBlock(block).size() - 1); + LIRInstruction instr = allocator.getLIR().getLIRforBlock(block).get(allocator.getLIR().getLIRforBlock(block).size() - 1); if (instr instanceof StandardOp.JumpOp) { if (allocator.getBlockData(block).liveOut.get(allocator.operandNumber(operand))) { assert false : String.format( @@ -125,10 +125,10 @@ * is a branch, spill moves are inserted before this branch and so the wrong operand * would be returned (spill moves at block boundaries are not considered in the live * ranges of intervals). - * + * * Solution: use the first opId of the branch target block instead. */ - final LIRInstruction instr = allocator.ir.getLIRforBlock(block).get(allocator.ir.getLIRforBlock(block).size() - 1); + final LIRInstruction instr = allocator.getLIR().getLIRforBlock(block).get(allocator.getLIR().getLIRforBlock(block).size() - 1); if (instr instanceof StandardOp.JumpOp) { if (allocator.getBlockData(block).liveOut.get(allocator.operandNumber(operand))) { tempOpId = allocator.getFirstLirInstructionId(block.getSuccessors().iterator().next()); @@ -208,9 +208,9 @@ private void assignLocations() { try (Indent indent = Debug.logAndIndent("assign locations")) { - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { try (Indent indent2 = Debug.logAndIndent("assign locations in block B%d", block.getId())) { - assignLocations(allocator.ir.getLIRforBlock(block)); + assignLocations(allocator.getLIR().getLIRforBlock(block)); } } }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanEliminateSpillMovePhase.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanEliminateSpillMovePhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -42,7 +42,7 @@ import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*; -class LinearScanEliminateSpillMovePhase extends AllocationPhase { +public class LinearScanEliminateSpillMovePhase extends AllocationPhase { private static final IntervalPredicate mustStoreAtDefinition = new LinearScan.IntervalPredicate() { @@ -54,7 +54,7 @@ protected final LinearScan allocator; - LinearScanEliminateSpillMovePhase(LinearScan allocator) { + protected LinearScanEliminateSpillMovePhase(LinearScan allocator) { this.allocator = allocator; } @@ -88,9 +88,9 @@ } LIRInsertionBuffer insertionBuffer = new LIRInsertionBuffer(); - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { try (Indent indent1 = Debug.logAndIndent("Handle %s", block)) { - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); int numInst = instructions.size(); // iterate all instructions of the block.
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanLifetimeAnalysisPhase.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanLifetimeAnalysisPhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -50,14 +50,14 @@ import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*; -class LinearScanLifetimeAnalysisPhase extends AllocationPhase { +public class LinearScanLifetimeAnalysisPhase extends AllocationPhase { protected final LinearScan allocator; /** * @param linearScan */ - LinearScanLifetimeAnalysisPhase(LinearScan linearScan) { + protected LinearScanLifetimeAnalysisPhase(LinearScan linearScan) { allocator = linearScan; } @@ -96,8 +96,8 @@ // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node. int numInstructions = 0; - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { - numInstructions += allocator.ir.getLIRforBlock(block).size(); + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { + numInstructions += allocator.getLIR().getLIRforBlock(block).size(); } // initialize with correct length @@ -105,10 +105,10 @@ int opId = 0; int index = 0; - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { allocator.initBlockData(block); - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); int numInst = instructions.size(); for (int j = 0; j < numInst; j++) { @@ -139,13 +139,13 @@ intervalInLoop = new BitMap2D(allocator.operandSize(), allocator.numLoops()); // iterate all blocks - for (final AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (final AbstractBlockBase<?> block : allocator.sortedBlocks()) { try (Indent indent = Debug.logAndIndent("compute local live sets for block %s", block)) { final BitSet liveGen = new BitSet(liveSize); final BitSet liveKill = new BitSet(liveSize); - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); int numInst = instructions.size(); ValueConsumer useConsumer = (operand, mode, flags) -> { @@ -249,7 +249,7 @@ * sets. This is checked by these assertions to be sure about it. The entry block may have * incoming values in registers, which is ok. */ - if (isRegister(operand) && block != allocator.ir.getControlFlowGraph().getStartBlock()) { + if (isRegister(operand) && block != allocator.getLIR().getControlFlowGraph().getStartBlock()) { if (allocator.isProcessed(operand)) { assert liveKill.get(allocator.operandNumber(operand)) : "using fixed register that is not defined in this block"; } @@ -260,7 +260,7 @@ * Performs a backward dataflow analysis to compute global live sets (i.e. * {@link BlockData#liveIn} and {@link BlockData#liveOut}) for each block. */ - void computeGlobalLiveSets() { + protected void computeGlobalLiveSets() { try (Indent indent = Debug.logAndIndent("compute global live sets")) { int numBlocks = allocator.blockCount(); boolean changeOccurred; @@ -341,7 +341,7 @@ } // check that the liveIn set of the first block is empty - AbstractBlockBase<?> startBlock = allocator.ir.getControlFlowGraph().getStartBlock(); + AbstractBlockBase<?> startBlock = allocator.getLIR().getControlFlowGraph().getStartBlock(); if (allocator.getBlockData(startBlock).liveIn.cardinality() != 0) { if (DetailedAsserts.getValue()) { reportFailure(numBlocks); @@ -356,7 +356,7 @@ try (Scope s = Debug.forceLog()) { try (Indent indent = Debug.logAndIndent("report failure")) { - BitSet startBlockLiveIn = allocator.getBlockData(allocator.ir.getControlFlowGraph().getStartBlock()).liveIn; + BitSet startBlockLiveIn = allocator.getBlockData(allocator.getLIR().getControlFlowGraph().getStartBlock()).liveIn; try (Indent indent2 = Debug.logAndIndent("Error: liveIn set of first block must be empty (when this fails, variables are used before they are defined):")) { for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) { Interval interval = allocator.intervalFor(operandNum); @@ -382,11 +382,11 @@ Deque<AbstractBlockBase<?>> definedIn = new ArrayDeque<>(); HashSet<AbstractBlockBase<?>> usedIn = new HashSet<>(); - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { if (allocator.getBlockData(block).liveGen.get(operandNum)) { usedIn.add(block); try (Indent indent3 = Debug.logAndIndent("used in block B%d", block.getId())) { - for (LIRInstruction ins : allocator.ir.getLIRforBlock(block)) { + for (LIRInstruction ins : allocator.getLIR().getLIRforBlock(block)) { try (Indent indent4 = Debug.logAndIndent("%d: %s", ins.id(), ins)) { ins.forEachState((liveStateOperand, mode, flags) -> { Debug.log("operand=%s", liveStateOperand); @@ -399,7 +399,7 @@ if (allocator.getBlockData(block).liveKill.get(operandNum)) { definedIn.add(block); try (Indent indent3 = Debug.logAndIndent("defined in block B%d", block.getId())) { - for (LIRInstruction ins : allocator.ir.getLIRforBlock(block)) { + for (LIRInstruction ins : allocator.getLIR().getLIRforBlock(block)) { Debug.log("%d: %s", ins.id(), ins); } } @@ -441,7 +441,7 @@ * Check that fixed intervals are not live at block boundaries (live set must be empty at * fixed intervals). */ - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { for (int j = 0; j <= allocator.maxRegisterNumber(); j++) { assert !allocator.getBlockData(block).liveIn.get(j) : "liveIn set of fixed register must be empty"; assert !allocator.getBlockData(block).liveOut.get(j) : "liveOut set of fixed register must be empty"; @@ -536,7 +536,7 @@ * Optimizes moves related to incoming stack based arguments. The interval for the destination * of such moves is assigned the stack slot (which is in the caller's frame) as its spill slot. */ - void handleMethodArguments(LIRInstruction op) { + protected void handleMethodArguments(LIRInstruction op) { if (op instanceof MoveOp) { MoveOp move = (MoveOp) op; if (optimizeMethodArgument(move.getInput())) { @@ -564,7 +564,7 @@ } } - void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) { + protected void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) { if (flags.contains(OperandFlag.HINT) && LinearScan.isVariableOrRegister(targetValue)) { op.forEachRegisterHint(targetValue, mode, (registerHint, valueMode, valueFlags) -> { @@ -662,7 +662,7 @@ return RegisterPriority.MustHaveRegister; } - void buildIntervals() { + protected void buildIntervals() { try (Indent indent = Debug.logAndIndent("build intervals")) { InstructionValueConsumer outputConsumer = (op, operand, mode, flags) -> { @@ -716,7 +716,7 @@ AbstractBlockBase<?> block = allocator.blockAt(i); try (Indent indent2 = Debug.logAndIndent("handle block %d", block.getId())) { - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); final int blockFrom = allocator.getFirstLirInstructionId(block); int blockTo = allocator.getLastLirInstructionId(block);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanOptimizeSpillPositionPhase.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanOptimizeSpillPositionPhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -40,7 +40,7 @@ import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*; -final class LinearScanOptimizeSpillPositionPhase extends AllocationPhase { +public final class LinearScanOptimizeSpillPositionPhase extends AllocationPhase { private static final DebugMetric betterSpillPos = Debug.metric("BetterSpillPosition"); private static final DebugMetric betterSpillPosWithLowerProbability = Debug.metric("BetterSpillPositionWithLowerProbability"); @@ -60,7 +60,7 @@ private void optimizeSpillPosition() { try (Indent indent0 = Debug.logAndIndent("OptimizeSpillPositions")) { - LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.ir.linearScanOrder().size()]; + LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.getLIR().linearScanOrder().size()]; for (Interval interval : allocator.intervals()) { optimizeInterval(insertionBuffers, interval); } @@ -118,7 +118,7 @@ /* * The spill block is the begin of the first split child (aka the value is on the * stack). - * + * * The problem is that if spill block has more than one predecessor, the values at the * end of the predecessors might differ. Therefore, we would need a spill move in all * predecessors. To avoid this we spill in the dominator. @@ -154,7 +154,7 @@ if (insertionBuffer == null) { insertionBuffer = new LIRInsertionBuffer(); insertionBuffers[spillBlock.getId()] = insertionBuffer; - insertionBuffer.init(allocator.ir.getLIRforBlock(spillBlock)); + insertionBuffer.init(allocator.getLIR().getLIRforBlock(spillBlock)); } int spillOpId = allocator.getFirstLirInstructionId(spillBlock); // insert spill move @@ -189,8 +189,8 @@ public AbstractBlockBase<?> next() { AbstractBlockBase<?> currentBlock = block; int nextBlockIndex = block.getLinearScanNumber() + 1; - if (nextBlockIndex < allocator.sortedBlocks.size()) { - block = allocator.sortedBlocks.get(nextBlockIndex); + if (nextBlockIndex < allocator.sortedBlocks().size()) { + block = allocator.sortedBlocks().get(nextBlockIndex); if (range.to <= allocator.getFirstLirInstructionId(block)) { range = range.next; if (range == Range.EndMarker) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -31,6 +31,8 @@ import com.oracle.graal.compiler.common.alloc.*; import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.alloc.lsra.ssa.*; +import com.oracle.graal.lir.alloc.lsra.ssi.*; import com.oracle.graal.lir.gen.*; import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanRegisterAllocationPhase.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanRegisterAllocationPhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -33,7 +33,7 @@ import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*; -final class LinearScanRegisterAllocationPhase extends AllocationPhase { +public final class LinearScanRegisterAllocationPhase extends AllocationPhase { private final LinearScan allocator;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanResolveDataFlowPhase.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanResolveDataFlowPhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -41,11 +41,11 @@ * * Insert moves at edges between blocks if intervals have been split. */ -class LinearScanResolveDataFlowPhase extends AllocationPhase { +public class LinearScanResolveDataFlowPhase extends AllocationPhase { protected final LinearScan allocator; - LinearScanResolveDataFlowPhase(LinearScan allocator) { + protected LinearScanResolveDataFlowPhase(LinearScan allocator) { this.allocator = allocator; } @@ -55,7 +55,7 @@ resolveDataFlow(); } - void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { + protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { assert moveResolver.checkEmpty(); assert midBlock == null || (midBlock.getPredecessorCount() == 1 && midBlock.getSuccessorCount() == 1 && midBlock.getPredecessors().get(0).equals(fromBlock) && midBlock.getSuccessors().get(0).equals( @@ -87,7 +87,7 @@ Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId()); } - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(fromBlock); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(fromBlock); LIRInstruction instr = instructions.get(instructions.size() - 1); if (instr instanceof StandardOp.JumpOp) { // insert moves before branch @@ -102,7 +102,7 @@ } if (DetailedAsserts.getValue()) { - assert allocator.ir.getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label"; + assert allocator.getLIR().getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label"; /* * Because the number of predecessor edges matches the number of successor edges, @@ -114,7 +114,7 @@ } } - moveResolver.setInsertPosition(allocator.ir.getLIRforBlock(toBlock), 1); + moveResolver.setInsertPosition(allocator.getLIR().getLIRforBlock(toBlock), 1); } } @@ -122,7 +122,7 @@ * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals that * have been split. */ - void resolveDataFlow() { + protected void resolveDataFlow() { try (Indent indent = Debug.logAndIndent("resolve data flow")) { MoveResolver moveResolver = allocator.createMoveResolver(); @@ -136,11 +136,11 @@ } protected void optimizeEmptyBlocks(MoveResolver moveResolver, BitSet blockCompleted) { - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { // check if block has only one predecessor and only one successor if (block.getPredecessorCount() == 1 && block.getSuccessorCount() == 1) { - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); assert instructions.get(0) instanceof StandardOp.LabelOp : "block must start with label"; assert instructions.get(instructions.size() - 1) instanceof StandardOp.JumpOp : "block with successor must end with unconditional jump"; @@ -174,7 +174,7 @@ protected void resolveDataFlow0(MoveResolver moveResolver, BitSet blockCompleted) { BitSet alreadyResolved = new BitSet(allocator.blockCount()); - for (AbstractBlockBase<?> fromBlock : allocator.sortedBlocks) { + for (AbstractBlockBase<?> fromBlock : allocator.sortedBlocks()) { if (!blockCompleted.get(fromBlock.getLinearScanNumber())) { alreadyResolved.clear(); alreadyResolved.or(blockCompleted);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanWalker.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanWalker.java Fri Jul 24 09:21:04 2015 +0200 @@ -268,7 +268,7 @@ // numbering of instructions is known. // When the block already contains spill moves, the index must be increased until the // correct index is reached. - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(opBlock); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(opBlock); int index = (opId - instructions.get(0).id()) >> 1; assert instructions.get(index).id() <= opId : "error in calculation"; @@ -845,7 +845,7 @@ * errors */ allocator.assignSpillSlot(interval); - Debug.dump(allocator.ir, description); + Debug.dump(allocator.getLIR(), description); allocator.printIntervals(description); throw new OutOfRegistersException("LinearScan: no register found", description); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/MoveResolver.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/MoveResolver.java Fri Jul 24 09:21:04 2015 +0200 @@ -36,7 +36,7 @@ /** */ -class MoveResolver { +public class MoveResolver { private final LinearScan allocator; @@ -81,7 +81,7 @@ return allocator; } - MoveResolver(LinearScan allocator) { + protected MoveResolver(LinearScan allocator) { this.allocator = allocator; this.multipleReadsAllowed = false; @@ -93,7 +93,7 @@ this.registerBlocked = new int[allocator.registers.length]; } - boolean checkEmpty() { + protected boolean checkEmpty() { assert mappingFrom.size() == 0 && mappingFromOpr.size() == 0 && mappingTo.size() == 0 : "list must be empty before and after processing"; for (int i = 0; i < getAllocator().registers.length; i++) { assert registerBlocked[i] == 0 : "register map must be empty before and after processing"; @@ -351,7 +351,7 @@ // one stack slot to another can happen (not allowed by LIRAssembler StackSlotValue spillSlot = fromInterval.spillSlot(); if (spillSlot == null) { - spillSlot = getAllocator().frameMapBuilder.allocateSpillSlot(fromInterval.kind()); + spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval.kind()); fromInterval.setSpillSlot(spillSlot); } spillInterval(spillCandidate, fromInterval, spillSlot); @@ -420,7 +420,7 @@ this.insertIdx = newInsertIdx; } - void addMapping(Interval fromInterval, Interval toInterval) { + public void addMapping(Interval fromInterval, Interval toInterval) { if (isIllegal(toInterval.location()) && toInterval.canMaterialize()) { if (Debug.isLogEnabled()) { @@ -446,7 +446,7 @@ mappingTo.add(toInterval); } - void addMapping(Value fromOpr, Interval toInterval) { + public void addMapping(Value fromOpr, Interval toInterval) { if (Debug.isLogEnabled()) { Debug.log("add move mapping from %s to %s", fromOpr, toInterval); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/OptimizingLinearScanWalker.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/OptimizingLinearScanWalker.java Fri Jul 24 09:21:04 2015 +0200 @@ -74,7 +74,7 @@ @Override void walk() { try (Scope s = Debug.scope("OptimizingLinearScanWalker")) { - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { optimizeBlock(block); } }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/RegisterVerifier.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/RegisterVerifier.java Fri Jul 24 09:21:04 2015 +0200 @@ -202,7 +202,7 @@ } void processOperations(AbstractBlockBase<?> block, final Interval[] inputState) { - List<LIRInstruction> ops = allocator.ir.getLIRforBlock(block); + List<LIRInstruction> ops = allocator.getLIR().getLIRforBlock(block); InstructionValueConsumer useConsumer = new InstructionValueConsumer() { @Override
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinarScanResolveDataFlowPhase.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,89 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import static jdk.internal.jvmci.code.ValueUtil.*; - -import java.util.*; - -import com.oracle.graal.debug.*; -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.ssa.*; -import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor; - -class SSALinarScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase { - - private static final DebugMetric numPhiResolutionMoves = Debug.metric("SSA LSRA[numPhiResolutionMoves]"); - private static final DebugMetric numStackToStackMoves = Debug.metric("SSA LSRA[numStackToStackMoves]"); - - SSALinarScanResolveDataFlowPhase(LinearScan allocator) { - super(allocator); - } - - @Override - void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { - super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver); - - if (toBlock.getPredecessorCount() > 1) { - int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock); - int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1; - - AbstractBlockBase<?> phiOutBlock = midBlock != null ? midBlock : fromBlock; - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(phiOutBlock); - int phiOutIdx = SSAUtils.phiOutIndex(allocator.ir, phiOutBlock); - int phiOutId = midBlock != null ? fromBlockLastInstructionId : instructions.get(phiOutIdx).id(); - assert phiOutId >= 0; - - PhiValueVisitor visitor = new PhiValueVisitor() { - - public void visit(Value phiIn, Value phiOut) { - assert !isRegister(phiOut) : "phiOut is a register: " + phiOut; - assert !isRegister(phiIn) : "phiIn is a register: " + phiIn; - Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); - if (isConstant(phiOut)) { - numPhiResolutionMoves.increment(); - moveResolver.addMapping(phiOut, toInterval); - } else { - Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), phiOutId, LIRInstruction.OperandMode.DEF); - if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) { - numPhiResolutionMoves.increment(); - if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { - moveResolver.addMapping(fromInterval, toInterval); - } else { - numStackToStackMoves.increment(); - moveResolver.addMapping(fromInterval, toInterval); - } - } - } - } - }; - - SSAUtils.forEachPhiValuePair(allocator.ir, toBlock, phiOutBlock, visitor); - SSAUtils.removePhiOut(allocator.ir, phiOutBlock); - } - } - -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScan.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,80 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import java.util.*; - -import jdk.internal.jvmci.code.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.debug.Debug.*; - -import com.oracle.graal.compiler.common.alloc.*; -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.lir.gen.*; -import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; -import com.oracle.graal.lir.ssa.*; - -final class SSALinearScan extends LinearScan { - - SSALinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, List<? extends AbstractBlockBase<?>> sortedBlocks) { - super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks); - } - - @Override - protected MoveResolver createMoveResolver() { - SSAMoveResolver moveResolver = new SSAMoveResolver(this); - assert moveResolver.checkEmpty(); - return moveResolver; - } - - @Override - protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { - return new SSALinearScanLifetimeAnalysisPhase(this); - } - - @Override - protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { - return new SSALinarScanResolveDataFlowPhase(this); - } - - @Override - protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { - return new SSALinearScanEliminateSpillMovePhase(this); - } - - @Override - protected void beforeSpillMoveElimination() { - /* - * PHI Ins are needed for the RegisterVerifier, otherwise PHIs where the Out and In value - * matches (ie. there is no resolution move) are falsely detected as errors. - */ - try (Scope s1 = Debug.scope("Remove Phi In")) { - for (AbstractBlockBase<?> toBlock : sortedBlocks) { - if (toBlock.getPredecessorCount() > 1) { - SSAUtils.removePhiIn(ir, toBlock); - } - } - } - } - -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScanEliminateSpillMovePhase.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,89 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import static com.oracle.graal.compiler.common.BackendOptions.*; -import static com.oracle.graal.lir.LIRValueUtil.*; -import static jdk.internal.jvmci.code.ValueUtil.*; -import com.oracle.graal.debug.*; - -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.StandardOp.LabelOp; -import com.oracle.graal.lir.StandardOp.MoveOp; - -public class SSALinearScanEliminateSpillMovePhase extends LinearScanEliminateSpillMovePhase { - - SSALinearScanEliminateSpillMovePhase(LinearScan allocator) { - super(allocator); - } - - @Override - protected int firstInstructionOfInterest() { - // also look at Labels as they define PHI values - return 0; - } - - @Override - protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) { - assert isVariable(move.getResult()) || LinearScanVariant.getValue() == LSRAVariant.SSA_LSRA : "Move should not be produced in a non-SSA compilation: " + move; - - if (super.canEliminateSpillMove(block, move)) { - // SSA Linear Scan might introduce moves to stack slots - Interval curInterval = allocator.intervalFor(move.getResult()); - assert !isRegister(curInterval.location()) && curInterval.alwaysInMemory(); - if (!isPhiResolutionMove(block, move, curInterval)) { - assert isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location(); - return true; - } - } - return false; - } - - private boolean isPhiResolutionMove(AbstractBlockBase<?> block, MoveOp move, Interval toInterval) { - assert LinearScanVariant.getValue() == LSRAVariant.SSA_LSRA; - if (!toInterval.isSplitParent()) { - return false; - } - if ((toInterval.from() & 1) == 1) { - // phi intervals start at even positions. - return false; - } - if (block.getSuccessorCount() != 1) { - return false; - } - LIRInstruction op = allocator.instructionForId(toInterval.from()); - if (!(op instanceof LabelOp)) { - return false; - } - AbstractBlockBase<?> intStartBlock = allocator.blockForId(toInterval.from()); - assert allocator.ir.getLIRforBlock(intStartBlock).get(0).equals(op); - if (!block.getSuccessors().get(0).equals(intStartBlock)) { - return false; - } - try (Indent indet = Debug.indent()) { - Debug.log("Is a move (%s) to phi interval %s", move, toInterval); - } - return true; - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScanLifetimeAnalysisPhase.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,87 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import java.util.*; - -import com.oracle.graal.debug.*; -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.LIRInstruction.OperandFlag; -import com.oracle.graal.lir.LIRInstruction.OperandMode; -import com.oracle.graal.lir.StandardOp.LabelOp; -import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority; -import com.oracle.graal.lir.ssa.*; - -public class SSALinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase { - - SSALinearScanLifetimeAnalysisPhase(LinearScan linearScan) { - super(linearScan); - } - - @Override - void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) { - super.addRegisterHint(op, targetValue, mode, flags, hintAtDef); - - if (hintAtDef && op instanceof LabelOp) { - LabelOp label = (LabelOp) op; - - Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue); - - SSAUtils.forEachPhiRegisterHint(allocator.ir, allocator.blockForId(label.id()), label, targetValue, mode, (ValueConsumer) (registerHint, valueMode, valueFlags) -> { - if (LinearScan.isVariableOrRegister(registerHint)) { - Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint); - - setHint(op, to, from); - setHint(op, from, to); - } - }); - } - } - - static void setHint(final LIRInstruction op, Interval target, Interval source) { - Interval currentHint = target.locationHint(false); - if (currentHint == null || currentHint.from() > target.from()) { - /* - * Update hint if there was none or if the hint interval starts after the hinted - * interval. - */ - target.setLocationHint(source); - if (Debug.isLogEnabled()) { - Debug.log("operation at opId %d: added hint from interval %d to %d", op.id(), source.operandNumber, target.operandNumber); - } - } - } - - @Override - protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { - if (op instanceof LabelOp) { - LabelOp label = (LabelOp) op; - if (label.isPhiIn()) { - return RegisterPriority.None; - } - } - return super.registerPriorityOfOutputOperand(op); - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSAMoveResolver.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,169 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import static jdk.internal.jvmci.code.ValueUtil.*; - -import java.util.*; - -import jdk.internal.jvmci.code.*; -import jdk.internal.jvmci.common.*; -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.framemap.*; - -final class SSAMoveResolver extends MoveResolver { - - private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1; - private int[] stackBlocked; - private final int firstVirtualStackIndex; - - SSAMoveResolver(LinearScan allocator) { - super(allocator); - FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) allocator.frameMapBuilder; - FrameMap frameMap = frameMapBuilderTool.getFrameMap(); - this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()]; - this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1; - } - - @Override - boolean checkEmpty() { - for (int i = 0; i < stackBlocked.length; i++) { - assert stackBlocked[i] == 0 : "stack map must be empty before and after processing"; - } - return super.checkEmpty(); - } - - @Override - protected void checkMultipleReads() { - // multiple reads are allowed in SSA LSRA - } - - @Override - protected void verifyStackSlotMapping() { - // relax disjoint stack maps invariant - } - - @Override - protected boolean areMultipleReadsAllowed() { - return true; - } - - @Override - protected boolean mightBeBlocked(Value location) { - if (super.mightBeBlocked(location)) { - return true; - } - if (isStackSlotValue(location)) { - return true; - } - return false; - } - - private int getStackArrayIndex(StackSlotValue stackSlotValue) { - if (isStackSlot(stackSlotValue)) { - return getStackArrayIndex(asStackSlot(stackSlotValue)); - } - if (isVirtualStackSlot(stackSlotValue)) { - return getStackArrayIndex(asVirtualStackSlot(stackSlotValue)); - } - throw JVMCIError.shouldNotReachHere("Unhandled StackSlotValue: " + stackSlotValue); - } - - private int getStackArrayIndex(StackSlot stackSlot) { - int stackIdx; - if (stackSlot.isInCallerFrame()) { - // incoming stack arguments can be ignored - stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX; - } else { - assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot; - int offset = -stackSlot.getRawOffset(); - assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex); - stackIdx = offset; - } - return stackIdx; - } - - private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) { - return firstVirtualStackIndex + virtualStackSlot.getId(); - } - - @Override - protected void setValueBlocked(Value location, int direction) { - assert direction == 1 || direction == -1 : "out of bounds"; - if (isStackSlotValue(location)) { - int stackIdx = getStackArrayIndex(asStackSlotValue(location)); - if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { - // incoming stack arguments can be ignored - return; - } - if (stackIdx >= stackBlocked.length) { - stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1); - } - stackBlocked[stackIdx] += direction; - } else { - super.setValueBlocked(location, direction); - } - } - - @Override - protected int valueBlocked(Value location) { - if (isStackSlotValue(location)) { - int stackIdx = getStackArrayIndex(asStackSlotValue(location)); - if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { - // incoming stack arguments are always blocked (aka they can not be written) - return 1; - } - if (stackIdx >= stackBlocked.length) { - return 0; - } - return stackBlocked[stackIdx]; - } - return super.valueBlocked(location); - } - - @Override - protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) { - if (isStackSlotValue(toLocation) && isStackSlotValue(fromLocation)) { - return getAllocator().getSpillMoveFactory().createStackMove(toOpr, fromOpr); - } - return super.createMove(fromOpr, toOpr, fromLocation, toLocation); - } - - @Override - protected void breakCycle(int spillCandidate) { - if (spillCandidate != -1) { - super.breakCycle(spillCandidate); - return; - } - assert mappingFrom.size() > 1; - // Arbitrarily select the first entry for spilling. - int stackSpillCandidate = 0; - Interval fromInterval = mappingFrom.get(stackSpillCandidate); - assert isStackSlotValue(fromInterval.location()); - // allocate new stack slot - StackSlotValue spillSlot = getAllocator().frameMapBuilder.allocateSpillSlot(fromInterval.kind()); - spillInterval(stackSpillCandidate, fromInterval, spillSlot); - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSILinearScan.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,70 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import java.util.*; - -import jdk.internal.jvmci.code.*; - -import com.oracle.graal.compiler.common.alloc.*; -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.lir.gen.*; -import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; -import com.oracle.graal.lir.ssi.*; - -public final class SSILinearScan extends LinearScan { - - public SSILinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, - List<? extends AbstractBlockBase<?>> sortedBlocks) { - super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks); - } - - @Override - protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, - SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) { - assert SSIVerifier.verify(lirGenRes.getLIR()) : "LIR not in SSI form."; - super.allocate(target, lirGenRes, codeEmittingOrder, linearScanOrder, spillMoveFactory, registerAllocationConfig); - } - - @Override - protected MoveResolver createMoveResolver() { - SSAMoveResolver moveResolver = new SSAMoveResolver(this); - assert moveResolver.checkEmpty(); - return moveResolver; - } - - @Override - protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { - return new SSILinearScanLifetimeAnalysisPhase(this); - } - - @Override - protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { - return new SSILinearScanResolveDataFlowPhase(this); - } - - @Override - protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { - return new SSILinearScanEliminateSpillMovePhase(this); - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSILinearScanEliminateSpillMovePhase.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,45 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.lir.StandardOp.MoveOp; - -public class SSILinearScanEliminateSpillMovePhase extends LinearScanEliminateSpillMovePhase { - - public SSILinearScanEliminateSpillMovePhase(LinearScan allocator) { - super(allocator); - } - - @Override - protected int firstInstructionOfInterest() { - // also look at Labels as they define PHI values - return 0; - } - - @Override - protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) { - // TODO (je) do not eliminate spill moves yet! - return false; - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSILinearScanLifetimeAnalysisPhase.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,122 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import static com.oracle.graal.lir.alloc.lsra.SSALinearScanLifetimeAnalysisPhase.*; - -import java.util.*; - -import jdk.internal.jvmci.code.*; -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.LIRInstruction.OperandFlag; -import com.oracle.graal.lir.LIRInstruction.OperandMode; -import com.oracle.graal.lir.StandardOp.LabelOp; -import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority; -import com.oracle.graal.lir.alloc.lsra.Interval.SpillState; -import com.oracle.graal.lir.ssi.*; - -public class SSILinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase { - - public SSILinearScanLifetimeAnalysisPhase(LinearScan linearScan) { - super(linearScan); - } - - @Override - protected void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) { - super.addRegisterHint(op, targetValue, mode, flags, hintAtDef); - - if (hintAtDef && op instanceof LabelOp) { - LabelOp label = (LabelOp) op; - - Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue); - - SSIUtils.forEachRegisterHint(allocator.ir, allocator.blockForId(label.id()), label, targetValue, mode, (ValueConsumer) (registerHint, valueMode, valueFlags) -> { - if (LinearScan.isVariableOrRegister(registerHint)) { - Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint); - - setHint(op, to, from); - setHint(op, from, to); - } - }); - } - } - - @Override - protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, Interval interval, int defPos) { - assert interval.isSplitParent() : "can only be called for split parents"; - - switch (interval.spillState()) { - case NoDefinitionFound: - // assert interval.spillDefinitionPos() == -1 : "must no be set before"; - interval.setSpillDefinitionPos(defPos); - if (!(op instanceof LabelOp)) { - // Do not update state for labels. This will be done afterwards. - interval.setSpillState(SpillState.NoSpillStore); - } - break; - - case NoSpillStore: - assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created"; - if (defPos < interval.spillDefinitionPos() - 2) { - // second definition found, so no spill optimization possible for this interval - interval.setSpillState(SpillState.NoOptimization); - } else { - // two consecutive definitions (because of two-operand LIR form) - assert allocator.blockForId(defPos) == allocator.blockForId(interval.spillDefinitionPos()) : "block must be equal"; - } - break; - - case NoOptimization: - // nothing to do - break; - - default: - throw new BailoutException("other states not allowed at this time"); - } - } - - @Override - protected void buildIntervals() { - super.buildIntervals(); - for (Interval interval : allocator.intervals()) { - if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) { - // there was a definition in a phi/sigma - interval.setSpillState(SpillState.NoSpillStore); - } - } - } - - @Override - protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { - if (op instanceof LabelOp) { - LabelOp label = (LabelOp) op; - if (label.id() != 0) { - // skip method header - return RegisterPriority.None; - } - } - return super.registerPriorityOfOutputOperand(op); - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSILinearScanResolveDataFlowPhase.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,127 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import static jdk.internal.jvmci.code.ValueUtil.*; - -import java.util.*; - -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.compiler.common.*; -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor; -import com.oracle.graal.lir.ssi.*; - -public class SSILinearScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase { - - private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]"); - private static final DebugMetric numStackToStackMoves = Debug.metric("SSI LSRA[numStackToStackMoves]"); - - public SSILinearScanResolveDataFlowPhase(LinearScan allocator) { - super(allocator); - } - - @Override - protected void resolveDataFlow() { - super.resolveDataFlow(); - /* - * Incoming Values are needed for the RegisterVerifier, otherwise SIGMAs/PHIs where the Out - * and In value matches (ie. there is no resolution move) are falsely detected as errors. - */ - for (AbstractBlockBase<?> toBlock : allocator.sortedBlocks) { - if (toBlock.getPredecessorCount() != 0) { - SSIUtils.removeIncoming(allocator.ir, toBlock); - } else { - assert allocator.ir.getControlFlowGraph().getStartBlock().equals(toBlock); - } - SSIUtils.removeOutgoing(allocator.ir, toBlock); - } - } - - @Override - protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { - super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver); - - if (midBlock != null) { - HashMap<Value, Value> map = CollectionsFactory.newMap(); - SSIUtils.forEachValuePair(allocator.ir, midBlock, fromBlock, (to, from) -> map.put(to, from)); - - MyPhiValueVisitor visitor = new MyPhiValueVisitor(moveResolver, toBlock, fromBlock); - SSIUtils.forEachValuePair(allocator.ir, toBlock, midBlock, (to, from) -> { - Value phiOut = isConstant(from) ? from : map.get(from); - assert phiOut != null : "No entry for " + from; - visitor.visit(to, phiOut); - }); - } else { - // default case - SSIUtils.forEachValuePair(allocator.ir, toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock)); - } - - } - - private class MyPhiValueVisitor implements PhiValueVisitor { - final MoveResolver moveResolver; - final int toId; - final int fromId; - - public MyPhiValueVisitor(MoveResolver moveResolver, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock) { - this.moveResolver = moveResolver; - toId = allocator.getFirstLirInstructionId(toBlock); - fromId = allocator.getLastLirInstructionId(fromBlock); - assert fromId >= 0; - } - - public void visit(Value phiIn, Value phiOut) { - assert !isRegister(phiOut) : "Out is a register: " + phiOut; - assert !isRegister(phiIn) : "In is a register: " + phiIn; - if (Value.ILLEGAL.equals(phiIn)) { - // The value not needed in this branch. - return; - } - if (isVirtualStackSlot(phiIn) && isVirtualStackSlot(phiOut) && phiIn.equals(phiOut)) { - // no need to handle virtual stack slots - return; - } - Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toId, LIRInstruction.OperandMode.DEF); - if (isConstant(phiOut)) { - numSSIResolutionMoves.increment(); - moveResolver.addMapping(phiOut, toInterval); - } else { - Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), fromId, LIRInstruction.OperandMode.DEF); - if (fromInterval != toInterval) { - numSSIResolutionMoves.increment(); - if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { - moveResolver.addMapping(fromInterval, toInterval); - } else { - numStackToStackMoves.increment(); - moveResolver.addMapping(fromInterval, toInterval); - } - } - } - } - } - -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceGlobalMoveResolver.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,407 +0,0 @@ -/* - * Copyright (c) 2009, 2014, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import static jdk.internal.jvmci.code.ValueUtil.*; - -import java.util.*; - -import jdk.internal.jvmci.code.*; -import jdk.internal.jvmci.common.*; -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.debug.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.framemap.*; -import com.oracle.graal.lir.gen.*; -import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; - -/** - */ -class TraceGlobalMoveResolver { - - private int insertIdx; - private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted - - private final List<Value> mappingFrom; - private final List<AllocatableValue> mappingTo; - private final int[] registerBlocked; - private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1; - private int[] stackBlocked; - private final int firstVirtualStackIndex; - private final SpillMoveFactory spillMoveFactory; - private final FrameMapBuilder frameMapBuilder; - - private void setValueBlocked(Value location, int direction) { - assert direction == 1 || direction == -1 : "out of bounds"; - if (isStackSlotValue(location)) { - int stackIdx = getStackArrayIndex(asStackSlotValue(location)); - if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { - // incoming stack arguments can be ignored - return; - } - if (stackIdx >= stackBlocked.length) { - stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1); - } - stackBlocked[stackIdx] += direction; - } else { - assert direction == 1 || direction == -1 : "out of bounds"; - if (isRegister(location)) { - registerBlocked[asRegister(location).number] += direction; - } else { - throw JVMCIError.shouldNotReachHere("unhandled value " + location); - } - } - } - - private int valueBlocked(Value location) { - if (isStackSlotValue(location)) { - int stackIdx = getStackArrayIndex(asStackSlotValue(location)); - if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { - // incoming stack arguments are always blocked (aka they can not be written) - return 1; - } - if (stackIdx >= stackBlocked.length) { - return 0; - } - return stackBlocked[stackIdx]; - } - if (isRegister(location)) { - return registerBlocked[asRegister(location).number]; - } - throw JVMCIError.shouldNotReachHere("unhandled value " + location); - } - - private static boolean areMultipleReadsAllowed() { - return true; - } - - private boolean hasMappings() { - return mappingFrom.size() > 0; - } - - private SpillMoveFactory getSpillMoveFactory() { - return spillMoveFactory; - } - - private Register[] getRegisters() { - return frameMapBuilder.getRegisterConfig().getAllocatableRegisters(); - } - - public TraceGlobalMoveResolver(LIRGenerationResult res, SpillMoveFactory spillMoveFactory, Architecture arch) { - - this.mappingFrom = new ArrayList<>(8); - this.mappingTo = new ArrayList<>(8); - this.insertIdx = -1; - this.insertionBuffer = new LIRInsertionBuffer(); - - this.frameMapBuilder = res.getFrameMapBuilder(); - this.spillMoveFactory = spillMoveFactory; - this.registerBlocked = new int[arch.getRegisters().length]; - - FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) frameMapBuilder; - this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()]; - - FrameMap frameMap = frameMapBuilderTool.getFrameMap(); - this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1; - } - - private boolean checkEmpty() { - for (int i = 0; i < stackBlocked.length; i++) { - assert stackBlocked[i] == 0 : "stack map must be empty before and after processing"; - } - assert mappingFrom.size() == 0 && mappingTo.size() == 0 : "list must be empty before and after processing"; - for (int i = 0; i < getRegisters().length; i++) { - assert registerBlocked[i] == 0 : "register map must be empty before and after processing"; - } - return true; - } - - private boolean verifyBeforeResolve() { - assert mappingFrom.size() == mappingTo.size() : "length must be equal"; - assert insertIdx != -1 : "insert position not set"; - - int i; - int j; - if (!areMultipleReadsAllowed()) { - for (i = 0; i < mappingFrom.size(); i++) { - for (j = i + 1; j < mappingFrom.size(); j++) { - assert mappingFrom.get(i) == null || mappingFrom.get(i) != mappingFrom.get(j) : "cannot read from same interval twice"; - } - } - } - - for (i = 0; i < mappingTo.size(); i++) { - for (j = i + 1; j < mappingTo.size(); j++) { - assert mappingTo.get(i) != mappingTo.get(j) : "cannot write to same interval twice"; - } - } - - for (i = 0; i < mappingTo.size(); i++) { - Value to = mappingTo.get(i); - assert !isStackSlotValue(to) || getStackArrayIndex(asStackSlotValue(to)) != STACK_SLOT_IN_CALLER_FRAME_IDX : "Cannot move to in argument: " + to; - } - - HashSet<Value> usedRegs = new HashSet<>(); - if (!areMultipleReadsAllowed()) { - for (i = 0; i < mappingFrom.size(); i++) { - Value from = mappingFrom.get(i); - if (from != null && !isIllegal(from)) { - boolean unique = usedRegs.add(from); - assert unique : "cannot read from same register twice"; - } - } - } - - usedRegs.clear(); - for (i = 0; i < mappingTo.size(); i++) { - Value to = mappingTo.get(i); - if (isIllegal(to)) { - // After insertion the location may become illegal, so don't check it since multiple - // intervals might be illegal. - continue; - } - boolean unique = usedRegs.add(to); - assert unique : "cannot write to same register twice"; - } - - return true; - } - - // mark assignedReg and assignedRegHi of the interval as blocked - private void block(Value location) { - if (mightBeBlocked(location)) { - assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location; - setValueBlocked(location, 1); - Debug.log("block %s", location); - } - } - - // mark assignedReg and assignedRegHi of the interval as unblocked - private void unblock(Value location) { - if (mightBeBlocked(location)) { - assert valueBlocked(location) > 0 : "location already marked as unused: " + location; - setValueBlocked(location, -1); - Debug.log("unblock %s", location); - } - } - - /** - * Checks if the {@linkplain Interval#location() location} of {@code to} is not blocked or is - * only blocked by {@code from}. - */ - private boolean safeToProcessMove(Value fromLocation, Value toLocation) { - if (mightBeBlocked(toLocation)) { - if ((valueBlocked(toLocation) > 1 || (valueBlocked(toLocation) == 1 && !isMoveToSelf(fromLocation, toLocation)))) { - return false; - } - } - - return true; - } - - public static boolean isMoveToSelf(Value from, Value to) { - assert to != null; - if (to.equals(from)) { - return true; - } - if (from != null && isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) { - assert LIRKind.verifyMoveKinds(to.getLIRKind(), from.getLIRKind()) : String.format("Same register but Kind mismatch %s <- %s", to, from); - return true; - } - return false; - } - - private static boolean mightBeBlocked(Value location) { - return isRegister(location) || isStackSlotValue(location); - } - - private void createInsertionBuffer(List<LIRInstruction> list) { - assert !insertionBuffer.initialized() : "overwriting existing buffer"; - insertionBuffer.init(list); - } - - private void appendInsertionBuffer() { - if (insertionBuffer.initialized()) { - insertionBuffer.finish(); - } - assert !insertionBuffer.initialized() : "must be uninitialized now"; - - insertIdx = -1; - } - - private void insertMove(Value fromOperand, AllocatableValue toOperand) { - assert !fromOperand.equals(toOperand) : "from and to are equal: " + fromOperand + " vs. " + toOperand; - assert LIRKind.verifyMoveKinds(fromOperand.getLIRKind(), fromOperand.getLIRKind()) : "move between different types"; - assert insertIdx != -1 : "must setup insert position first"; - - insertionBuffer.append(insertIdx, createMove(fromOperand, toOperand)); - - if (Debug.isLogEnabled()) { - Debug.log("insert move from %s to %s at %d", fromOperand, toOperand, insertIdx); - } - } - - /** - * @param fromOpr {@link Interval#operand operand} of the {@code from} interval - * @param toOpr {@link Interval#operand operand} of the {@code to} interval - */ - private LIRInstruction createMove(Value fromOpr, AllocatableValue toOpr) { - if (isStackSlotValue(toOpr) && isStackSlotValue(fromOpr)) { - return getSpillMoveFactory().createStackMove(toOpr, fromOpr); - } - return getSpillMoveFactory().createMove(toOpr, fromOpr); - } - - private void resolveMappings() { - try (Indent indent = Debug.logAndIndent("resolveMapping")) { - assert verifyBeforeResolve(); - if (Debug.isLogEnabled()) { - printMapping(); - } - - // Block all registers that are used as input operands of a move. - // When a register is blocked, no move to this register is emitted. - // This is necessary for detecting cycles in moves. - for (int i = mappingFrom.size() - 1; i >= 0; i--) { - Value from = mappingFrom.get(i); - block(from); - } - - int spillCandidate = -1; - while (mappingFrom.size() > 0) { - boolean processedInterval = false; - - for (int i = mappingFrom.size() - 1; i >= 0; i--) { - Value fromInterval = mappingFrom.get(i); - AllocatableValue toInterval = mappingTo.get(i); - - Value fromLocation = fromInterval; - AllocatableValue toLocation = toInterval; - if (safeToProcessMove(fromLocation, toLocation)) { - // this interval can be processed because target is free - insertMove(fromLocation, toLocation); - unblock(fromLocation); - mappingFrom.remove(i); - mappingTo.remove(i); - - processedInterval = true; - } else if (fromInterval != null && isRegister(fromLocation)) { - // this interval cannot be processed now because target is not free - // it starts in a register, so it is a possible candidate for spilling - spillCandidate = i; - } - } - - if (!processedInterval) { - breakCycle(spillCandidate); - } - } - } - - // check that all intervals have been processed - assert checkEmpty(); - } - - private void breakCycle(int spillCandidate) { - // no move could be processed because there is a cycle in the move list - // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory - assert spillCandidate != -1 : "no interval in register for spilling found"; - - // create a new spill interval and assign a stack slot to it - Value from = mappingFrom.get(spillCandidate); - try (Indent indent = Debug.logAndIndent("BreakCycle: %s", from)) { - StackSlotValue spillSlot = frameMapBuilder.allocateSpillSlot(from.getLIRKind()); - if (Debug.isLogEnabled()) { - Debug.log("created new slot for spilling: %s", spillSlot); - } - // insert a move from register to stack and update the mapping - insertMove(from, spillSlot); - block(spillSlot); - mappingFrom.set(spillCandidate, spillSlot); - unblock(from); - } - } - - private void printMapping() { - try (Indent indent = Debug.logAndIndent("Mapping")) { - for (int i = mappingFrom.size() - 1; i >= 0; i--) { - Debug.log("move %s <- %s", mappingTo.get(i), mappingFrom.get(i)); - } - } - } - - public void setInsertPosition(List<LIRInstruction> insertList, int insertIdx) { - assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set"; - - createInsertionBuffer(insertList); - this.insertIdx = insertIdx; - } - - public void addMapping(Value from, AllocatableValue to) { - if (Debug.isLogEnabled()) { - Debug.log("add move mapping from %s to %s", from, to); - } - - assert !from.equals(to) : "from and to interval equal: " + from; - assert LIRKind.verifyMoveKinds(to.getLIRKind(), from.getLIRKind()) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", from.getLIRKind(), to.getLIRKind(), from, to); - mappingFrom.add(from); - mappingTo.add(to); - } - - public void resolveAndAppendMoves() { - if (hasMappings()) { - resolveMappings(); - } - appendInsertionBuffer(); - } - - private int getStackArrayIndex(StackSlotValue stackSlotValue) { - if (isStackSlot(stackSlotValue)) { - return getStackArrayIndex(asStackSlot(stackSlotValue)); - } - if (isVirtualStackSlot(stackSlotValue)) { - return getStackArrayIndex(asVirtualStackSlot(stackSlotValue)); - } - throw JVMCIError.shouldNotReachHere("Unhandled StackSlotValue: " + stackSlotValue); - } - - private int getStackArrayIndex(StackSlot stackSlot) { - int stackIdx; - if (stackSlot.isInCallerFrame()) { - // incoming stack arguments can be ignored - stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX; - } else { - assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot; - int offset = -stackSlot.getRawOffset(); - assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex); - stackIdx = offset; - } - return stackIdx; - } - - private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) { - return firstVirtualStackIndex + virtualStackSlot.getId(); - } - -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceLinearScan.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,123 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import static com.oracle.graal.compiler.common.GraalOptions.*; - -import java.util.*; - -import jdk.internal.jvmci.code.*; - -import com.oracle.graal.compiler.common.alloc.*; -import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.debug.Debug.Scope; -import com.oracle.graal.lir.gen.*; -import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; -import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext; - -public final class TraceLinearScan extends LinearScan { - - private final TraceBuilderResult<?> traceBuilderResult; - - public TraceLinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, - List<? extends AbstractBlockBase<?>> sortedBlocks, TraceBuilderResult<?> traceBuilderResult) { - super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks); - this.traceBuilderResult = traceBuilderResult; - } - - @Override - protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, - SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) { - - /* - * This is the point to enable debug logging for the whole register allocation. - */ - try (Indent indent = Debug.logAndIndent("LinearScan allocate")) { - AllocationContext context = new AllocationContext(spillMoveFactory, registerAllocationConfig); - - createLifetimeAnalysisPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); - - try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals)) { - sortIntervalsBeforeAllocation(); - - createRegisterAllocationPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); - - if (LinearScan.Options.LSRAOptimizeSpillPosition.getValue()) { - createOptimizeSpillPositionPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); - } - // resolve intra-trace data-flow - LinearScanResolveDataFlowPhase dataFlowPhase = createResolveDataFlowPhase(); - dataFlowPhase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); - Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks, "%s", dataFlowPhase.getName()); - - LinearScanAssignLocationsPhase assignPhase = createAssignLocationsPhase(); - assignPhase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); - - if (DetailedAsserts.getValue()) { - verifyIntervals(); - } - } catch (Throwable e) { - throw Debug.handle(e); - } - } - } - - @Override - protected MoveResolver createMoveResolver() { - SSAMoveResolver moveResolver = new SSAMoveResolver(this); - assert moveResolver.checkEmpty(); - return moveResolver; - } - - @Override - protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { - return new TraceLinearScanLifetimeAnalysisPhase(this, traceBuilderResult); - } - - @Override - protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { - return new TraceLinearScanResolveDataFlowPhase(this); - } - - @Override - protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { - return new SSILinearScanEliminateSpillMovePhase(this); - } - - @Override - void printIntervals(String label) { - if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) { - super.printIntervals(label); - } - } - - @Override - void printLir(String label, boolean hirValid) { - if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) { - Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks, label); - } - } - -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceLinearScanLifetimeAnalysisPhase.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,288 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import static com.oracle.graal.compiler.common.GraalOptions.*; -import static com.oracle.graal.lir.LIRValueUtil.*; -import static com.oracle.graal.lir.alloc.lsra.TraceRegisterAllocationPhase.Options.*; -import static jdk.internal.jvmci.code.ValueUtil.*; - -import java.util.*; - -import jdk.internal.jvmci.code.*; -import jdk.internal.jvmci.common.*; -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.StandardOp.BlockEndOp; -import com.oracle.graal.lir.StandardOp.LabelOp; -import com.oracle.graal.lir.StandardOp.MoveOp; -import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority; -import com.oracle.graal.lir.alloc.lsra.Interval.SpillState; -import com.oracle.graal.lir.alloc.lsra.LinearScan.BlockData; -import com.oracle.graal.lir.ssi.*; - -public class TraceLinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase { - - private final TraceBuilderResult<?> traceBuilderResult; - - public TraceLinearScanLifetimeAnalysisPhase(LinearScan linearScan, TraceBuilderResult<?> traceBuilderResult) { - super(linearScan); - this.traceBuilderResult = traceBuilderResult; - } - - private boolean sameTrace(AbstractBlockBase<?> a, AbstractBlockBase<?> b) { - return traceBuilderResult.getTraceForBlock(b) == traceBuilderResult.getTraceForBlock(a); - } - - private boolean isAllocatedOrCurrent(AbstractBlockBase<?> currentBlock, AbstractBlockBase<?> other) { - return traceBuilderResult.getTraceForBlock(other) <= traceBuilderResult.getTraceForBlock(currentBlock); - } - - static void setHint(final LIRInstruction op, Interval target, Interval source) { - Interval currentHint = target.locationHint(false); - if (currentHint == null || currentHint.from() > target.from()) { - /* - * Update hint if there was none or if the hint interval starts after the hinted - * interval. - */ - target.setLocationHint(source); - if (Debug.isLogEnabled()) { - Debug.log("operation at opId %d: added hint from interval %d (%s) to %d (%s)", op.id(), source.operandNumber, source, target.operandNumber, target); - } - } - } - - @Override - protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, Interval interval, int defPos) { - assert interval.isSplitParent() : "can only be called for split parents"; - - switch (interval.spillState()) { - case NoDefinitionFound: - // assert interval.spillDefinitionPos() == -1 : "must no be set before"; - interval.setSpillDefinitionPos(defPos); - if (!(op instanceof LabelOp)) { - // Do not update state for labels. This will be done afterwards. - interval.setSpillState(SpillState.NoSpillStore); - } - break; - - case NoSpillStore: - assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created"; - if (defPos < interval.spillDefinitionPos() - 2) { - // second definition found, so no spill optimization possible for this interval - interval.setSpillState(SpillState.NoOptimization); - } else { - // two consecutive definitions (because of two-operand LIR form) - assert allocator.blockForId(defPos) == allocator.blockForId(interval.spillDefinitionPos()) : "block must be equal"; - } - break; - - case NoOptimization: - // nothing to do - break; - - default: - throw new BailoutException("other states not allowed at this time"); - } - } - - @Override - protected void buildIntervals() { - super.buildIntervals(); - // fix spill state for phi/sigma intervals - for (Interval interval : allocator.intervals()) { - if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) { - // there was a definition in a phi/sigma - interval.setSpillState(SpillState.NoSpillStore); - } - } - if (TraceRAuseInterTraceHints.getValue()) { - addInterTraceHints(); - } - } - - private void addInterTraceHints() { - // set hints for phi/sigma intervals - LIR lir = allocator.ir; - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { - LabelOp label = SSIUtils.incoming(lir, block); - for (AbstractBlockBase<?> pred : block.getPredecessors()) { - if (isAllocatedOrCurrent(block, pred)) { - BlockEndOp outgoing = SSIUtils.outgoing(lir, pred); - for (int i = 0; i < outgoing.getOutgoingSize(); i++) { - Value toValue = label.getIncomingValue(i); - if (!isIllegal(toValue)) { - Value fromValue = outgoing.getOutgoingValue(i); - assert sameTrace(block, pred) || !isVariable(fromValue) : "Unallocated variable: " + fromValue; - - if (isStackSlotValue(fromValue)) { - - } else if (isConstant(fromValue)) { - } else { - Interval from = allocator.getOrCreateInterval((AllocatableValue) fromValue); - Interval to = allocator.getOrCreateInterval((AllocatableValue) toValue); - setHint(label, to, from); - } - } - } - } - } - } - /* - * Set the first range for fixed intervals to [-1, 0] to avoid intersection with incoming - * values. - */ - for (Interval interval : allocator.intervals()) { - if (interval != null && isRegister(interval.operand)) { - Range range = interval.first(); - if (range == Range.EndMarker) { - interval.addRange(-1, 0); - } else if (range.from == 0 && range.to == 1) { - range.from = -1; - range.to = 0; - } - } - } - } - - @Override - protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { - if (op instanceof LabelOp) { - // skip method header - return RegisterPriority.None; - } - return super.registerPriorityOfOutputOperand(op); - } - - @Override - void handleMethodArguments(LIRInstruction op) { - if (op instanceof MoveOp) { - // do not optimize method arguments - return; - } - super.handleMethodArguments(op); - } - - /** - * Performs a backward dataflow analysis to compute global live sets (i.e. - * {@link BlockData#liveIn} and {@link BlockData#liveOut}) for each block. - */ - @Override - protected void computeGlobalLiveSets() { - try (Indent indent = Debug.logAndIndent("compute global live sets")) { - int numBlocks = allocator.blockCount(); - boolean changeOccurred; - boolean changeOccurredInBlock; - int iterationCount = 0; - BitSet liveOut = new BitSet(allocator.liveSetSize()); // scratch set for calculations - - /* - * Perform a backward dataflow analysis to compute liveOut and liveIn for each block. - * The loop is executed until a fixpoint is reached (no changes in an iteration). - */ - do { - changeOccurred = false; - - try (Indent indent2 = Debug.logAndIndent("new iteration %d", iterationCount)) { - - // iterate all blocks in reverse order - for (int i = numBlocks - 1; i >= 0; i--) { - AbstractBlockBase<?> block = allocator.blockAt(i); - BlockData blockSets = allocator.getBlockData(block); - - changeOccurredInBlock = false; - - /* liveOut(block) is the union of liveIn(sux), for successors sux of block. */ - int n = block.getSuccessorCount(); - if (n > 0) { - liveOut.clear(); - // block has successors - if (n > 0) { - for (AbstractBlockBase<?> successor : block.getSuccessors()) { - if (allocator.sortedBlocks.contains(successor)) { - liveOut.or(allocator.getBlockData(successor).liveIn); - } - } - } - - if (!blockSets.liveOut.equals(liveOut)) { - /* - * A change occurred. Swap the old and new live out sets to avoid - * copying. - */ - BitSet temp = blockSets.liveOut; - blockSets.liveOut = liveOut; - liveOut = temp; - - changeOccurred = true; - changeOccurredInBlock = true; - } - } - - if (iterationCount == 0 || changeOccurredInBlock) { - /* - * liveIn(block) is the union of liveGen(block) with (liveOut(block) & - * !liveKill(block)). - * - * Note: liveIn has to be computed only in first iteration or if liveOut - * has changed! - */ - BitSet liveIn = blockSets.liveIn; - liveIn.clear(); - liveIn.or(blockSets.liveOut); - liveIn.andNot(blockSets.liveKill); - liveIn.or(blockSets.liveGen); - - if (Debug.isLogEnabled()) { - Debug.log("block %d: livein = %s, liveout = %s", block.getId(), liveIn, blockSets.liveOut); - } - } - } - iterationCount++; - - if (changeOccurred && iterationCount > 50) { - throw new BailoutException("too many iterations in computeGlobalLiveSets"); - } - } - } while (changeOccurred); - - if (DetailedAsserts.getValue()) { - verifyLiveness(); - } - - // check that the liveIn set of the first block is empty - AbstractBlockBase<?> startBlock = allocator.blockAt(0); - if (allocator.getBlockData(startBlock).liveIn.cardinality() != 0) { - if (DetailedAsserts.getValue()) { - reportFailure(numBlocks); - } - // bailout if this occurs in product mode. - throw new JVMCIError("liveIn set of first block must be empty: " + allocator.getBlockData(startBlock).liveIn); - } - } - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceLinearScanResolveDataFlowPhase.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,107 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import static jdk.internal.jvmci.code.ValueUtil.*; - -import java.util.*; - -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor; -import com.oracle.graal.lir.ssi.*; - -public class TraceLinearScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase { - - private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]"); - private static final DebugMetric numStackToStackMoves = Debug.metric("SSI LSRA[numStackToStackMoves]"); - - public TraceLinearScanResolveDataFlowPhase(LinearScan allocator) { - super(allocator); - } - - @Override - protected void optimizeEmptyBlocks(MoveResolver moveResolver, BitSet blockCompleted) { - // do not optimize - } - - @Override - protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { - assert midBlock == null; - if (containedInTrace(fromBlock) && containedInTrace(toBlock)) { - super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver); - SSIUtils.forEachValuePair(allocator.ir, toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock)); - } - - } - - private boolean containedInTrace(AbstractBlockBase<?> block) { - return allocator.sortedBlocks.contains(block); - } - - private class MyPhiValueVisitor implements PhiValueVisitor { - final MoveResolver moveResolver; - final int toId; - final int fromId; - - public MyPhiValueVisitor(MoveResolver moveResolver, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock) { - this.moveResolver = moveResolver; - toId = allocator.getFirstLirInstructionId(toBlock); - fromId = allocator.getLastLirInstructionId(fromBlock); - assert fromId >= 0; - } - - public void visit(Value phiIn, Value phiOut) { - assert !isRegister(phiOut) : "Out is a register: " + phiOut; - assert !isRegister(phiIn) : "In is a register: " + phiIn; - if (Value.ILLEGAL.equals(phiIn)) { - // The value not needed in this branch. - return; - } - if (isVirtualStackSlot(phiIn) && isVirtualStackSlot(phiOut) && phiIn.equals(phiOut)) { - // no need to handle virtual stack slots - return; - } - Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toId, LIRInstruction.OperandMode.DEF); - if (isConstant(phiOut)) { - numSSIResolutionMoves.increment(); - moveResolver.addMapping(phiOut, toInterval); - } else { - Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), fromId, LIRInstruction.OperandMode.DEF); - if (fromInterval != toInterval) { - numSSIResolutionMoves.increment(); - if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { - moveResolver.addMapping(fromInterval, toInterval); - } else { - numStackToStackMoves.increment(); - moveResolver.addMapping(fromInterval, toInterval); - } - } - } - } - } - -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceRegisterAllocationPhase.java Fri Jul 24 09:04:14 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,168 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import static jdk.internal.jvmci.code.ValueUtil.*; - -import java.util.*; - -import jdk.internal.jvmci.code.*; -import jdk.internal.jvmci.meta.*; -import jdk.internal.jvmci.options.*; - -import com.oracle.graal.compiler.common.alloc.*; -import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.debug.Debug.Scope; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.StandardOp.MoveOp; -import com.oracle.graal.lir.gen.*; -import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; -import com.oracle.graal.lir.phases.*; -import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor; -import com.oracle.graal.lir.ssi.*; - -public class TraceRegisterAllocationPhase extends AllocationPhase { - public static class Options { - // @formatter:off - @Option(help = "Use inter-trace register hints.", type = OptionType.Debug) - public static final OptionValue<Boolean> TraceRAuseInterTraceHints = new OptionValue<>(true); - // @formatter:on - } - - static final int TRACE_DUMP_LEVEL = 3; - - @Override - protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory, - RegisterAllocationConfig registerAllocationConfig) { - LIR lir = lirGenRes.getLIR(); - assert SSIVerifier.verify(lir) : "LIR not in SSI form."; - B startBlock = linearScanOrder.get(0); - assert startBlock.equals(lir.getControlFlowGraph().getStartBlock()); - TraceBuilderResult<B> resultTraces = TraceBuilder.computeTraces(startBlock, linearScanOrder); - - Debug.dump(lir, "Before TraceRegisterAllocation"); - int traceNumber = 0; - for (List<B> trace : resultTraces.getTraces()) { - try (Indent i = Debug.logAndIndent("Allocating Trace%d: %s", traceNumber, trace); Scope s = Debug.scope("AllocateTrace", trace)) { - Debug.dump(TRACE_DUMP_LEVEL, trace, "Trace" + traceNumber + ": " + trace); - TraceLinearScan allocator = new TraceLinearScan(target, lirGenRes, spillMoveFactory, registerAllocationConfig, trace, resultTraces); - allocator.allocate(target, lirGenRes, codeEmittingOrder, linearScanOrder, spillMoveFactory, registerAllocationConfig); - Debug.dump(TRACE_DUMP_LEVEL, trace, "After Trace" + traceNumber + ": " + trace); - traceNumber++; - } catch (Throwable e) { - throw Debug.handle(e); - } - unnumberInstructions(trace, lir); - } - Debug.dump(lir, "After trace allocation"); - - resolveGlobalDataFlow(resultTraces, lirGenRes, spillMoveFactory, target.arch); - Debug.dump(lir, "After global dataflow resolution"); - - if (replaceStackToStackMoves(lir, spillMoveFactory)) { - Debug.dump(lir, "After fixing stack to stack moves"); - } - /* - * Incoming Values are needed for the RegisterVerifier, otherwise SIGMAs/PHIs where the Out - * and In value matches (ie. there is no resolution move) are falsely detected as errors. - */ - for (AbstractBlockBase<?> toBlock : lir.getControlFlowGraph().getBlocks()) { - if (toBlock.getPredecessorCount() != 0) { - SSIUtils.removeIncoming(lir, toBlock); - } else { - assert lir.getControlFlowGraph().getStartBlock().equals(toBlock); - } - SSIUtils.removeOutgoing(lir, toBlock); - } - } - - /** - * Fixup stack to stack moves introduced by stack arguments. - * - * TODO (je) find a better solution. - */ - private static boolean replaceStackToStackMoves(LIR lir, SpillMoveFactory spillMoveFactory) { - boolean changed = false; - for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) { - List<LIRInstruction> instructions = lir.getLIRforBlock(block); - for (int i = 0; i < instructions.size(); i++) { - LIRInstruction inst = instructions.get(i); - - if (inst instanceof MoveOp) { - MoveOp move = (MoveOp) inst; - if (isStackSlotValue(move.getInput()) && isStackSlotValue(move.getResult())) { - instructions.set(i, spillMoveFactory.createStackMove(move.getResult(), move.getInput())); - changed = true; - } - } - } - } - return changed; - } - - private static <B extends AbstractBlockBase<B>> void resolveGlobalDataFlow(TraceBuilderResult<B> resultTraces, LIRGenerationResult lirGenRes, SpillMoveFactory spillMoveFactory, Architecture arch) { - LIR lir = lirGenRes.getLIR(); - /* Resolve trace global data-flow mismatch. */ - TraceGlobalMoveResolver moveResolver = new TraceGlobalMoveResolver(lirGenRes, spillMoveFactory, arch); - PhiValueVisitor visitor = (Value phiIn, Value phiOut) -> { - if (!isIllegal(phiIn) && !TraceGlobalMoveResolver.isMoveToSelf(phiOut, phiIn)) { - moveResolver.addMapping(phiOut, (AllocatableValue) phiIn); - } - }; - - try (Indent indent = Debug.logAndIndent("Trace global move resolution")) { - for (List<B> trace : resultTraces.getTraces()) { - for (AbstractBlockBase<?> fromBlock : trace) { - for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) { - if (resultTraces.getTraceForBlock(fromBlock) != resultTraces.getTraceForBlock(toBlock)) { - try (Indent indent0 = Debug.logAndIndent("Handle trace edge from %s (Trace%d) to %s (Trace%d)", fromBlock, resultTraces.getTraceForBlock(fromBlock), toBlock, - resultTraces.getTraceForBlock(toBlock))) { - - final List<LIRInstruction> instructions; - final int insertIdx; - if (fromBlock.getSuccessorCount() == 1) { - instructions = lir.getLIRforBlock(fromBlock); - insertIdx = instructions.size() - 1; - } else { - assert toBlock.getPredecessorCount() == 1; - instructions = lir.getLIRforBlock(toBlock); - insertIdx = 1; - } - - moveResolver.setInsertPosition(instructions, insertIdx); - SSIUtils.forEachValuePair(lir, toBlock, fromBlock, visitor); - moveResolver.resolveAndAppendMoves(); - } - } - } - } - } - } - } - - private static void unnumberInstructions(List<? extends AbstractBlockBase<?>> trace, LIR lir) { - trace.stream().flatMap(b -> lir.getLIRforBlock(b).stream()).forEach(op -> op.setId(-1)); - } -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinarScanResolveDataFlowPhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,91 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssa; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import com.oracle.graal.debug.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.ssa.*; +import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor; + +class SSALinarScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase { + + private static final DebugMetric numPhiResolutionMoves = Debug.metric("SSA LSRA[numPhiResolutionMoves]"); + private static final DebugMetric numStackToStackMoves = Debug.metric("SSA LSRA[numStackToStackMoves]"); + + SSALinarScanResolveDataFlowPhase(LinearScan allocator) { + super(allocator); + } + + @Override + protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { + super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver); + + if (toBlock.getPredecessorCount() > 1) { + int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock); + int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1; + + AbstractBlockBase<?> phiOutBlock = midBlock != null ? midBlock : fromBlock; + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(phiOutBlock); + int phiOutIdx = SSAUtils.phiOutIndex(allocator.getLIR(), phiOutBlock); + int phiOutId = midBlock != null ? fromBlockLastInstructionId : instructions.get(phiOutIdx).id(); + assert phiOutId >= 0; + + PhiValueVisitor visitor = new PhiValueVisitor() { + + public void visit(Value phiIn, Value phiOut) { + assert !isRegister(phiOut) : "phiOut is a register: " + phiOut; + assert !isRegister(phiIn) : "phiIn is a register: " + phiIn; + Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); + if (isConstant(phiOut)) { + numPhiResolutionMoves.increment(); + moveResolver.addMapping(phiOut, toInterval); + } else { + Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), phiOutId, LIRInstruction.OperandMode.DEF); + if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) { + numPhiResolutionMoves.increment(); + if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { + moveResolver.addMapping(fromInterval, toInterval); + } else { + numStackToStackMoves.increment(); + moveResolver.addMapping(fromInterval, toInterval); + } + } + } + } + }; + + SSAUtils.forEachPhiValuePair(allocator.getLIR(), toBlock, phiOutBlock, visitor); + SSAUtils.removePhiOut(allocator.getLIR(), phiOutBlock); + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinearScan.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,82 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssa; + +import java.util.*; + +import jdk.internal.jvmci.code.*; + +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.*; +import com.oracle.graal.compiler.common.alloc.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; +import com.oracle.graal.lir.ssa.*; + +public final class SSALinearScan extends LinearScan { + + public SSALinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, + List<? extends AbstractBlockBase<?>> sortedBlocks) { + super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks); + } + + @Override + protected MoveResolver createMoveResolver() { + SSAMoveResolver moveResolver = new SSAMoveResolver(this); + assert moveResolver.checkEmpty(); + return moveResolver; + } + + @Override + protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { + return new SSALinearScanLifetimeAnalysisPhase(this); + } + + @Override + protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { + return new SSALinarScanResolveDataFlowPhase(this); + } + + @Override + protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { + return new SSALinearScanEliminateSpillMovePhase(this); + } + + @Override + protected void beforeSpillMoveElimination() { + /* + * PHI Ins are needed for the RegisterVerifier, otherwise PHIs where the Out and In value + * matches (ie. there is no resolution move) are falsely detected as errors. + */ + try (Scope s1 = Debug.scope("Remove Phi In")) { + for (AbstractBlockBase<?> toBlock : sortedBlocks()) { + if (toBlock.getPredecessorCount() > 1) { + SSAUtils.removePhiIn(getLIR(), toBlock); + } + } + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinearScanEliminateSpillMovePhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,90 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssa; + +import static com.oracle.graal.compiler.common.BackendOptions.*; +import static com.oracle.graal.lir.LIRValueUtil.*; +import static jdk.internal.jvmci.code.ValueUtil.*; + +import com.oracle.graal.debug.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.LabelOp; +import com.oracle.graal.lir.StandardOp.MoveOp; +import com.oracle.graal.lir.alloc.lsra.*; + +public class SSALinearScanEliminateSpillMovePhase extends LinearScanEliminateSpillMovePhase { + + SSALinearScanEliminateSpillMovePhase(LinearScan allocator) { + super(allocator); + } + + @Override + protected int firstInstructionOfInterest() { + // also look at Labels as they define PHI values + return 0; + } + + @Override + protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) { + assert isVariable(move.getResult()) || LinearScanVariant.getValue() == LSRAVariant.SSA_LSRA : "Move should not be produced in a non-SSA compilation: " + move; + + if (super.canEliminateSpillMove(block, move)) { + // SSA Linear Scan might introduce moves to stack slots + Interval curInterval = allocator.intervalFor(move.getResult()); + assert !isRegister(curInterval.location()) && curInterval.alwaysInMemory(); + if (!isPhiResolutionMove(block, move, curInterval)) { + assert isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location(); + return true; + } + } + return false; + } + + private boolean isPhiResolutionMove(AbstractBlockBase<?> block, MoveOp move, Interval toInterval) { + assert LinearScanVariant.getValue() == LSRAVariant.SSA_LSRA; + if (!toInterval.isSplitParent()) { + return false; + } + if ((toInterval.from() & 1) == 1) { + // phi intervals start at even positions. + return false; + } + if (block.getSuccessorCount() != 1) { + return false; + } + LIRInstruction op = allocator.instructionForId(toInterval.from()); + if (!(op instanceof LabelOp)) { + return false; + } + AbstractBlockBase<?> intStartBlock = allocator.blockForId(toInterval.from()); + assert allocator.getLIR().getLIRforBlock(intStartBlock).get(0).equals(op); + if (!block.getSuccessors().get(0).equals(intStartBlock)) { + return false; + } + try (Indent indet = Debug.indent()) { + Debug.log("Is a move (%s) to phi interval %s", move, toInterval); + } + return true; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinearScanLifetimeAnalysisPhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,89 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssa; + +import java.util.*; + +import com.oracle.graal.debug.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandFlag; +import com.oracle.graal.lir.LIRInstruction.OperandMode; +import com.oracle.graal.lir.StandardOp.LabelOp; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority; +import com.oracle.graal.lir.ssa.*; + +public class SSALinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase { + + SSALinearScanLifetimeAnalysisPhase(LinearScan linearScan) { + super(linearScan); + } + + @Override + protected void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) { + super.addRegisterHint(op, targetValue, mode, flags, hintAtDef); + + if (hintAtDef && op instanceof LabelOp) { + LabelOp label = (LabelOp) op; + + Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue); + + SSAUtils.forEachPhiRegisterHint(allocator.getLIR(), allocator.blockForId(label.id()), label, targetValue, mode, (ValueConsumer) (registerHint, valueMode, valueFlags) -> { + if (LinearScan.isVariableOrRegister(registerHint)) { + Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint); + + setHint(op, to, from); + setHint(op, from, to); + } + }); + } + } + + public static void setHint(final LIRInstruction op, Interval target, Interval source) { + Interval currentHint = target.locationHint(false); + if (currentHint == null || currentHint.from() > target.from()) { + /* + * Update hint if there was none or if the hint interval starts after the hinted + * interval. + */ + target.setLocationHint(source); + if (Debug.isLogEnabled()) { + Debug.log("operation at opId %d: added hint from interval %d to %d", op.id(), source.operandNumber, target.operandNumber); + } + } + } + + @Override + protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { + if (op instanceof LabelOp) { + LabelOp label = (LabelOp) op; + if (label.isPhiIn()) { + return RegisterPriority.None; + } + } + return super.registerPriorityOfOutputOperand(op); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSAMoveResolver.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,170 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssa; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.common.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.framemap.*; + +public final class SSAMoveResolver extends MoveResolver { + + private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1; + private int[] stackBlocked; + private final int firstVirtualStackIndex; + + public SSAMoveResolver(LinearScan allocator) { + super(allocator); + FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) allocator.getFrameMapBuilder(); + FrameMap frameMap = frameMapBuilderTool.getFrameMap(); + this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()]; + this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1; + } + + @Override + public boolean checkEmpty() { + for (int i = 0; i < stackBlocked.length; i++) { + assert stackBlocked[i] == 0 : "stack map must be empty before and after processing"; + } + return super.checkEmpty(); + } + + @Override + protected void checkMultipleReads() { + // multiple reads are allowed in SSA LSRA + } + + @Override + protected void verifyStackSlotMapping() { + // relax disjoint stack maps invariant + } + + @Override + protected boolean areMultipleReadsAllowed() { + return true; + } + + @Override + protected boolean mightBeBlocked(Value location) { + if (super.mightBeBlocked(location)) { + return true; + } + if (isStackSlotValue(location)) { + return true; + } + return false; + } + + private int getStackArrayIndex(StackSlotValue stackSlotValue) { + if (isStackSlot(stackSlotValue)) { + return getStackArrayIndex(asStackSlot(stackSlotValue)); + } + if (isVirtualStackSlot(stackSlotValue)) { + return getStackArrayIndex(asVirtualStackSlot(stackSlotValue)); + } + throw JVMCIError.shouldNotReachHere("Unhandled StackSlotValue: " + stackSlotValue); + } + + private int getStackArrayIndex(StackSlot stackSlot) { + int stackIdx; + if (stackSlot.isInCallerFrame()) { + // incoming stack arguments can be ignored + stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX; + } else { + assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot; + int offset = -stackSlot.getRawOffset(); + assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex); + stackIdx = offset; + } + return stackIdx; + } + + private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) { + return firstVirtualStackIndex + virtualStackSlot.getId(); + } + + @Override + protected void setValueBlocked(Value location, int direction) { + assert direction == 1 || direction == -1 : "out of bounds"; + if (isStackSlotValue(location)) { + int stackIdx = getStackArrayIndex(asStackSlotValue(location)); + if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { + // incoming stack arguments can be ignored + return; + } + if (stackIdx >= stackBlocked.length) { + stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1); + } + stackBlocked[stackIdx] += direction; + } else { + super.setValueBlocked(location, direction); + } + } + + @Override + protected int valueBlocked(Value location) { + if (isStackSlotValue(location)) { + int stackIdx = getStackArrayIndex(asStackSlotValue(location)); + if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { + // incoming stack arguments are always blocked (aka they can not be written) + return 1; + } + if (stackIdx >= stackBlocked.length) { + return 0; + } + return stackBlocked[stackIdx]; + } + return super.valueBlocked(location); + } + + @Override + protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) { + if (isStackSlotValue(toLocation) && isStackSlotValue(fromLocation)) { + return getAllocator().getSpillMoveFactory().createStackMove(toOpr, fromOpr); + } + return super.createMove(fromOpr, toOpr, fromLocation, toLocation); + } + + @Override + protected void breakCycle(int spillCandidate) { + if (spillCandidate != -1) { + super.breakCycle(spillCandidate); + return; + } + assert mappingFrom.size() > 1; + // Arbitrarily select the first entry for spilling. + int stackSpillCandidate = 0; + Interval fromInterval = mappingFrom.get(stackSpillCandidate); + assert isStackSlotValue(fromInterval.location()); + // allocate new stack slot + StackSlotValue spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval.kind()); + spillInterval(stackSpillCandidate, fromInterval, spillSlot); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScan.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,72 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssi; + +import java.util.*; + +import jdk.internal.jvmci.code.*; + +import com.oracle.graal.compiler.common.alloc.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.alloc.lsra.ssa.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; +import com.oracle.graal.lir.ssi.*; + +public final class SSILinearScan extends LinearScan { + + public SSILinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, + List<? extends AbstractBlockBase<?>> sortedBlocks) { + super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks); + } + + @Override + protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, + SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) { + assert SSIVerifier.verify(lirGenRes.getLIR()) : "LIR not in SSI form."; + super.allocate(target, lirGenRes, codeEmittingOrder, linearScanOrder, spillMoveFactory, registerAllocationConfig); + } + + @Override + protected MoveResolver createMoveResolver() { + SSAMoveResolver moveResolver = new SSAMoveResolver(this); + assert moveResolver.checkEmpty(); + return moveResolver; + } + + @Override + protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { + return new SSILinearScanLifetimeAnalysisPhase(this); + } + + @Override + protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { + return new SSILinearScanResolveDataFlowPhase(this); + } + + @Override + protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { + return new SSILinearScanEliminateSpillMovePhase(this); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScanEliminateSpillMovePhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,46 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssi; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.StandardOp.MoveOp; +import com.oracle.graal.lir.alloc.lsra.*; + +public class SSILinearScanEliminateSpillMovePhase extends LinearScanEliminateSpillMovePhase { + + public SSILinearScanEliminateSpillMovePhase(LinearScan allocator) { + super(allocator); + } + + @Override + protected int firstInstructionOfInterest() { + // also look at Labels as they define PHI values + return 0; + } + + @Override + protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) { + // TODO (je) do not eliminate spill moves yet! + return false; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScanLifetimeAnalysisPhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,123 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssi; + +import static com.oracle.graal.lir.alloc.lsra.ssa.SSALinearScanLifetimeAnalysisPhase.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandFlag; +import com.oracle.graal.lir.LIRInstruction.OperandMode; +import com.oracle.graal.lir.StandardOp.LabelOp; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority; +import com.oracle.graal.lir.alloc.lsra.Interval.SpillState; +import com.oracle.graal.lir.ssi.*; + +public class SSILinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase { + + public SSILinearScanLifetimeAnalysisPhase(LinearScan linearScan) { + super(linearScan); + } + + @Override + protected void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) { + super.addRegisterHint(op, targetValue, mode, flags, hintAtDef); + + if (hintAtDef && op instanceof LabelOp) { + LabelOp label = (LabelOp) op; + + Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue); + + SSIUtils.forEachRegisterHint(allocator.getLIR(), allocator.blockForId(label.id()), label, targetValue, mode, (ValueConsumer) (registerHint, valueMode, valueFlags) -> { + if (LinearScan.isVariableOrRegister(registerHint)) { + Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint); + + setHint(op, to, from); + setHint(op, from, to); + } + }); + } + } + + @Override + protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, Interval interval, int defPos) { + assert interval.isSplitParent() : "can only be called for split parents"; + + switch (interval.spillState()) { + case NoDefinitionFound: + // assert interval.spillDefinitionPos() == -1 : "must no be set before"; + interval.setSpillDefinitionPos(defPos); + if (!(op instanceof LabelOp)) { + // Do not update state for labels. This will be done afterwards. + interval.setSpillState(SpillState.NoSpillStore); + } + break; + + case NoSpillStore: + assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created"; + if (defPos < interval.spillDefinitionPos() - 2) { + // second definition found, so no spill optimization possible for this interval + interval.setSpillState(SpillState.NoOptimization); + } else { + // two consecutive definitions (because of two-operand LIR form) + assert allocator.blockForId(defPos) == allocator.blockForId(interval.spillDefinitionPos()) : "block must be equal"; + } + break; + + case NoOptimization: + // nothing to do + break; + + default: + throw new BailoutException("other states not allowed at this time"); + } + } + + @Override + protected void buildIntervals() { + super.buildIntervals(); + for (Interval interval : allocator.intervals()) { + if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) { + // there was a definition in a phi/sigma + interval.setSpillState(SpillState.NoSpillStore); + } + } + } + + @Override + protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { + if (op instanceof LabelOp) { + LabelOp label = (LabelOp) op; + if (label.id() != 0) { + // skip method header + return RegisterPriority.None; + } + } + return super.registerPriorityOfOutputOperand(op); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScanResolveDataFlowPhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,128 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssi; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor; +import com.oracle.graal.lir.ssi.*; + +public class SSILinearScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase { + + private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]"); + private static final DebugMetric numStackToStackMoves = Debug.metric("SSI LSRA[numStackToStackMoves]"); + + public SSILinearScanResolveDataFlowPhase(LinearScan allocator) { + super(allocator); + } + + @Override + protected void resolveDataFlow() { + super.resolveDataFlow(); + /* + * Incoming Values are needed for the RegisterVerifier, otherwise SIGMAs/PHIs where the Out + * and In value matches (ie. there is no resolution move) are falsely detected as errors. + */ + for (AbstractBlockBase<?> toBlock : allocator.sortedBlocks()) { + if (toBlock.getPredecessorCount() != 0) { + SSIUtils.removeIncoming(allocator.getLIR(), toBlock); + } else { + assert allocator.getLIR().getControlFlowGraph().getStartBlock().equals(toBlock); + } + SSIUtils.removeOutgoing(allocator.getLIR(), toBlock); + } + } + + @Override + protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { + super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver); + + if (midBlock != null) { + HashMap<Value, Value> map = CollectionsFactory.newMap(); + SSIUtils.forEachValuePair(allocator.getLIR(), midBlock, fromBlock, (to, from) -> map.put(to, from)); + + MyPhiValueVisitor visitor = new MyPhiValueVisitor(moveResolver, toBlock, fromBlock); + SSIUtils.forEachValuePair(allocator.getLIR(), toBlock, midBlock, (to, from) -> { + Value phiOut = isConstant(from) ? from : map.get(from); + assert phiOut != null : "No entry for " + from; + visitor.visit(to, phiOut); + }); + } else { + // default case + SSIUtils.forEachValuePair(allocator.getLIR(), toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock)); + } + + } + + private class MyPhiValueVisitor implements PhiValueVisitor { + final MoveResolver moveResolver; + final int toId; + final int fromId; + + public MyPhiValueVisitor(MoveResolver moveResolver, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock) { + this.moveResolver = moveResolver; + toId = allocator.getFirstLirInstructionId(toBlock); + fromId = allocator.getLastLirInstructionId(fromBlock); + assert fromId >= 0; + } + + public void visit(Value phiIn, Value phiOut) { + assert !isRegister(phiOut) : "Out is a register: " + phiOut; + assert !isRegister(phiIn) : "In is a register: " + phiIn; + if (Value.ILLEGAL.equals(phiIn)) { + // The value not needed in this branch. + return; + } + if (isVirtualStackSlot(phiIn) && isVirtualStackSlot(phiOut) && phiIn.equals(phiOut)) { + // no need to handle virtual stack slots + return; + } + Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toId, LIRInstruction.OperandMode.DEF); + if (isConstant(phiOut)) { + numSSIResolutionMoves.increment(); + moveResolver.addMapping(phiOut, toInterval); + } else { + Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), fromId, LIRInstruction.OperandMode.DEF); + if (fromInterval != toInterval) { + numSSIResolutionMoves.increment(); + if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { + moveResolver.addMapping(fromInterval, toInterval); + } else { + numStackToStackMoves.increment(); + moveResolver.addMapping(fromInterval, toInterval); + } + } + } + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceGlobalMoveResolver.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,408 @@ +/* + * Copyright (c) 2009, 2014, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.trace; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.common.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.framemap.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; + +/** + */ +class TraceGlobalMoveResolver { + + private int insertIdx; + private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted + + private final List<Value> mappingFrom; + private final List<AllocatableValue> mappingTo; + private final int[] registerBlocked; + private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1; + private int[] stackBlocked; + private final int firstVirtualStackIndex; + private final SpillMoveFactory spillMoveFactory; + private final FrameMapBuilder frameMapBuilder; + + private void setValueBlocked(Value location, int direction) { + assert direction == 1 || direction == -1 : "out of bounds"; + if (isStackSlotValue(location)) { + int stackIdx = getStackArrayIndex(asStackSlotValue(location)); + if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { + // incoming stack arguments can be ignored + return; + } + if (stackIdx >= stackBlocked.length) { + stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1); + } + stackBlocked[stackIdx] += direction; + } else { + assert direction == 1 || direction == -1 : "out of bounds"; + if (isRegister(location)) { + registerBlocked[asRegister(location).number] += direction; + } else { + throw JVMCIError.shouldNotReachHere("unhandled value " + location); + } + } + } + + private int valueBlocked(Value location) { + if (isStackSlotValue(location)) { + int stackIdx = getStackArrayIndex(asStackSlotValue(location)); + if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { + // incoming stack arguments are always blocked (aka they can not be written) + return 1; + } + if (stackIdx >= stackBlocked.length) { + return 0; + } + return stackBlocked[stackIdx]; + } + if (isRegister(location)) { + return registerBlocked[asRegister(location).number]; + } + throw JVMCIError.shouldNotReachHere("unhandled value " + location); + } + + private static boolean areMultipleReadsAllowed() { + return true; + } + + private boolean hasMappings() { + return mappingFrom.size() > 0; + } + + private SpillMoveFactory getSpillMoveFactory() { + return spillMoveFactory; + } + + private Register[] getRegisters() { + return frameMapBuilder.getRegisterConfig().getAllocatableRegisters(); + } + + public TraceGlobalMoveResolver(LIRGenerationResult res, SpillMoveFactory spillMoveFactory, Architecture arch) { + + this.mappingFrom = new ArrayList<>(8); + this.mappingTo = new ArrayList<>(8); + this.insertIdx = -1; + this.insertionBuffer = new LIRInsertionBuffer(); + + this.frameMapBuilder = res.getFrameMapBuilder(); + this.spillMoveFactory = spillMoveFactory; + this.registerBlocked = new int[arch.getRegisters().length]; + + FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) frameMapBuilder; + this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()]; + + FrameMap frameMap = frameMapBuilderTool.getFrameMap(); + this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1; + } + + private boolean checkEmpty() { + for (int i = 0; i < stackBlocked.length; i++) { + assert stackBlocked[i] == 0 : "stack map must be empty before and after processing"; + } + assert mappingFrom.size() == 0 && mappingTo.size() == 0 : "list must be empty before and after processing"; + for (int i = 0; i < getRegisters().length; i++) { + assert registerBlocked[i] == 0 : "register map must be empty before and after processing"; + } + return true; + } + + private boolean verifyBeforeResolve() { + assert mappingFrom.size() == mappingTo.size() : "length must be equal"; + assert insertIdx != -1 : "insert position not set"; + + int i; + int j; + if (!areMultipleReadsAllowed()) { + for (i = 0; i < mappingFrom.size(); i++) { + for (j = i + 1; j < mappingFrom.size(); j++) { + assert mappingFrom.get(i) == null || mappingFrom.get(i) != mappingFrom.get(j) : "cannot read from same interval twice"; + } + } + } + + for (i = 0; i < mappingTo.size(); i++) { + for (j = i + 1; j < mappingTo.size(); j++) { + assert mappingTo.get(i) != mappingTo.get(j) : "cannot write to same interval twice"; + } + } + + for (i = 0; i < mappingTo.size(); i++) { + Value to = mappingTo.get(i); + assert !isStackSlotValue(to) || getStackArrayIndex(asStackSlotValue(to)) != STACK_SLOT_IN_CALLER_FRAME_IDX : "Cannot move to in argument: " + to; + } + + HashSet<Value> usedRegs = new HashSet<>(); + if (!areMultipleReadsAllowed()) { + for (i = 0; i < mappingFrom.size(); i++) { + Value from = mappingFrom.get(i); + if (from != null && !isIllegal(from)) { + boolean unique = usedRegs.add(from); + assert unique : "cannot read from same register twice"; + } + } + } + + usedRegs.clear(); + for (i = 0; i < mappingTo.size(); i++) { + Value to = mappingTo.get(i); + if (isIllegal(to)) { + // After insertion the location may become illegal, so don't check it since multiple + // intervals might be illegal. + continue; + } + boolean unique = usedRegs.add(to); + assert unique : "cannot write to same register twice"; + } + + return true; + } + + // mark assignedReg and assignedRegHi of the interval as blocked + private void block(Value location) { + if (mightBeBlocked(location)) { + assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location; + setValueBlocked(location, 1); + Debug.log("block %s", location); + } + } + + // mark assignedReg and assignedRegHi of the interval as unblocked + private void unblock(Value location) { + if (mightBeBlocked(location)) { + assert valueBlocked(location) > 0 : "location already marked as unused: " + location; + setValueBlocked(location, -1); + Debug.log("unblock %s", location); + } + } + + /** + * Checks if the {@linkplain Interval#location() location} of {@code to} is not blocked or is + * only blocked by {@code from}. + */ + private boolean safeToProcessMove(Value fromLocation, Value toLocation) { + if (mightBeBlocked(toLocation)) { + if ((valueBlocked(toLocation) > 1 || (valueBlocked(toLocation) == 1 && !isMoveToSelf(fromLocation, toLocation)))) { + return false; + } + } + + return true; + } + + public static boolean isMoveToSelf(Value from, Value to) { + assert to != null; + if (to.equals(from)) { + return true; + } + if (from != null && isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) { + assert LIRKind.verifyMoveKinds(to.getLIRKind(), from.getLIRKind()) : String.format("Same register but Kind mismatch %s <- %s", to, from); + return true; + } + return false; + } + + private static boolean mightBeBlocked(Value location) { + return isRegister(location) || isStackSlotValue(location); + } + + private void createInsertionBuffer(List<LIRInstruction> list) { + assert !insertionBuffer.initialized() : "overwriting existing buffer"; + insertionBuffer.init(list); + } + + private void appendInsertionBuffer() { + if (insertionBuffer.initialized()) { + insertionBuffer.finish(); + } + assert !insertionBuffer.initialized() : "must be uninitialized now"; + + insertIdx = -1; + } + + private void insertMove(Value fromOperand, AllocatableValue toOperand) { + assert !fromOperand.equals(toOperand) : "from and to are equal: " + fromOperand + " vs. " + toOperand; + assert LIRKind.verifyMoveKinds(fromOperand.getLIRKind(), fromOperand.getLIRKind()) : "move between different types"; + assert insertIdx != -1 : "must setup insert position first"; + + insertionBuffer.append(insertIdx, createMove(fromOperand, toOperand)); + + if (Debug.isLogEnabled()) { + Debug.log("insert move from %s to %s at %d", fromOperand, toOperand, insertIdx); + } + } + + /** + * @param fromOpr {@link Interval#operand operand} of the {@code from} interval + * @param toOpr {@link Interval#operand operand} of the {@code to} interval + */ + private LIRInstruction createMove(Value fromOpr, AllocatableValue toOpr) { + if (isStackSlotValue(toOpr) && isStackSlotValue(fromOpr)) { + return getSpillMoveFactory().createStackMove(toOpr, fromOpr); + } + return getSpillMoveFactory().createMove(toOpr, fromOpr); + } + + private void resolveMappings() { + try (Indent indent = Debug.logAndIndent("resolveMapping")) { + assert verifyBeforeResolve(); + if (Debug.isLogEnabled()) { + printMapping(); + } + + // Block all registers that are used as input operands of a move. + // When a register is blocked, no move to this register is emitted. + // This is necessary for detecting cycles in moves. + for (int i = mappingFrom.size() - 1; i >= 0; i--) { + Value from = mappingFrom.get(i); + block(from); + } + + int spillCandidate = -1; + while (mappingFrom.size() > 0) { + boolean processedInterval = false; + + for (int i = mappingFrom.size() - 1; i >= 0; i--) { + Value fromInterval = mappingFrom.get(i); + AllocatableValue toInterval = mappingTo.get(i); + + Value fromLocation = fromInterval; + AllocatableValue toLocation = toInterval; + if (safeToProcessMove(fromLocation, toLocation)) { + // this interval can be processed because target is free + insertMove(fromLocation, toLocation); + unblock(fromLocation); + mappingFrom.remove(i); + mappingTo.remove(i); + + processedInterval = true; + } else if (fromInterval != null && isRegister(fromLocation)) { + // this interval cannot be processed now because target is not free + // it starts in a register, so it is a possible candidate for spilling + spillCandidate = i; + } + } + + if (!processedInterval) { + breakCycle(spillCandidate); + } + } + } + + // check that all intervals have been processed + assert checkEmpty(); + } + + private void breakCycle(int spillCandidate) { + // no move could be processed because there is a cycle in the move list + // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory + assert spillCandidate != -1 : "no interval in register for spilling found"; + + // create a new spill interval and assign a stack slot to it + Value from = mappingFrom.get(spillCandidate); + try (Indent indent = Debug.logAndIndent("BreakCycle: %s", from)) { + StackSlotValue spillSlot = frameMapBuilder.allocateSpillSlot(from.getLIRKind()); + if (Debug.isLogEnabled()) { + Debug.log("created new slot for spilling: %s", spillSlot); + } + // insert a move from register to stack and update the mapping + insertMove(from, spillSlot); + block(spillSlot); + mappingFrom.set(spillCandidate, spillSlot); + unblock(from); + } + } + + private void printMapping() { + try (Indent indent = Debug.logAndIndent("Mapping")) { + for (int i = mappingFrom.size() - 1; i >= 0; i--) { + Debug.log("move %s <- %s", mappingTo.get(i), mappingFrom.get(i)); + } + } + } + + public void setInsertPosition(List<LIRInstruction> insertList, int insertIdx) { + assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set"; + + createInsertionBuffer(insertList); + this.insertIdx = insertIdx; + } + + public void addMapping(Value from, AllocatableValue to) { + if (Debug.isLogEnabled()) { + Debug.log("add move mapping from %s to %s", from, to); + } + + assert !from.equals(to) : "from and to interval equal: " + from; + assert LIRKind.verifyMoveKinds(to.getLIRKind(), from.getLIRKind()) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", from.getLIRKind(), to.getLIRKind(), from, to); + mappingFrom.add(from); + mappingTo.add(to); + } + + public void resolveAndAppendMoves() { + if (hasMappings()) { + resolveMappings(); + } + appendInsertionBuffer(); + } + + private int getStackArrayIndex(StackSlotValue stackSlotValue) { + if (isStackSlot(stackSlotValue)) { + return getStackArrayIndex(asStackSlot(stackSlotValue)); + } + if (isVirtualStackSlot(stackSlotValue)) { + return getStackArrayIndex(asVirtualStackSlot(stackSlotValue)); + } + throw JVMCIError.shouldNotReachHere("Unhandled StackSlotValue: " + stackSlotValue); + } + + private int getStackArrayIndex(StackSlot stackSlot) { + int stackIdx; + if (stackSlot.isInCallerFrame()) { + // incoming stack arguments can be ignored + stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX; + } else { + assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot; + int offset = -stackSlot.getRawOffset(); + assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex); + stackIdx = offset; + } + return stackIdx; + } + + private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) { + return firstVirtualStackIndex + virtualStackSlot.getId(); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,126 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.trace; + +import static com.oracle.graal.compiler.common.GraalOptions.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; + +import com.oracle.graal.compiler.common.alloc.*; +import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.alloc.lsra.ssa.*; +import com.oracle.graal.lir.alloc.lsra.ssi.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; +import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext; + +public final class TraceLinearScan extends LinearScan { + + private final TraceBuilderResult<?> traceBuilderResult; + + public TraceLinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, + List<? extends AbstractBlockBase<?>> sortedBlocks, TraceBuilderResult<?> traceBuilderResult) { + super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks); + this.traceBuilderResult = traceBuilderResult; + } + + @Override + protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, + SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) { + + /* + * This is the point to enable debug logging for the whole register allocation. + */ + try (Indent indent = Debug.logAndIndent("LinearScan allocate")) { + AllocationContext context = new AllocationContext(spillMoveFactory, registerAllocationConfig); + + createLifetimeAnalysisPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + + try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals)) { + sortIntervalsBeforeAllocation(); + + createRegisterAllocationPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + + if (LinearScan.Options.LSRAOptimizeSpillPosition.getValue()) { + createOptimizeSpillPositionPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + } + // resolve intra-trace data-flow + LinearScanResolveDataFlowPhase dataFlowPhase = createResolveDataFlowPhase(); + dataFlowPhase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks(), "%s", dataFlowPhase.getName()); + + LinearScanAssignLocationsPhase assignPhase = createAssignLocationsPhase(); + assignPhase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + + if (DetailedAsserts.getValue()) { + verifyIntervals(); + } + } catch (Throwable e) { + throw Debug.handle(e); + } + } + } + + @Override + protected MoveResolver createMoveResolver() { + SSAMoveResolver moveResolver = new SSAMoveResolver(this); + assert moveResolver.checkEmpty(); + return moveResolver; + } + + @Override + protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { + return new TraceLinearScanLifetimeAnalysisPhase(this, traceBuilderResult); + } + + @Override + protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { + return new TraceLinearScanResolveDataFlowPhase(this); + } + + @Override + protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { + return new SSILinearScanEliminateSpillMovePhase(this); + } + + @Override + protected void printIntervals(String label) { + if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) { + super.printIntervals(label); + } + } + + @Override + protected void printLir(String label, boolean hirValid) { + if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) { + Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks(), label); + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,289 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.trace; + +import static com.oracle.graal.compiler.common.GraalOptions.*; +import static com.oracle.graal.lir.LIRValueUtil.*; +import static com.oracle.graal.lir.alloc.trace.TraceRegisterAllocationPhase.Options.*; +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.common.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.StandardOp.LabelOp; +import com.oracle.graal.lir.StandardOp.MoveOp; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority; +import com.oracle.graal.lir.alloc.lsra.Interval.SpillState; +import com.oracle.graal.lir.alloc.lsra.LinearScan.BlockData; +import com.oracle.graal.lir.ssi.*; + +public class TraceLinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase { + + private final TraceBuilderResult<?> traceBuilderResult; + + public TraceLinearScanLifetimeAnalysisPhase(LinearScan linearScan, TraceBuilderResult<?> traceBuilderResult) { + super(linearScan); + this.traceBuilderResult = traceBuilderResult; + } + + private boolean sameTrace(AbstractBlockBase<?> a, AbstractBlockBase<?> b) { + return traceBuilderResult.getTraceForBlock(b) == traceBuilderResult.getTraceForBlock(a); + } + + private boolean isAllocatedOrCurrent(AbstractBlockBase<?> currentBlock, AbstractBlockBase<?> other) { + return traceBuilderResult.getTraceForBlock(other) <= traceBuilderResult.getTraceForBlock(currentBlock); + } + + static void setHint(final LIRInstruction op, Interval target, Interval source) { + Interval currentHint = target.locationHint(false); + if (currentHint == null || currentHint.from() > target.from()) { + /* + * Update hint if there was none or if the hint interval starts after the hinted + * interval. + */ + target.setLocationHint(source); + if (Debug.isLogEnabled()) { + Debug.log("operation at opId %d: added hint from interval %d (%s) to %d (%s)", op.id(), source.operandNumber, source, target.operandNumber, target); + } + } + } + + @Override + protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, Interval interval, int defPos) { + assert interval.isSplitParent() : "can only be called for split parents"; + + switch (interval.spillState()) { + case NoDefinitionFound: + // assert interval.spillDefinitionPos() == -1 : "must no be set before"; + interval.setSpillDefinitionPos(defPos); + if (!(op instanceof LabelOp)) { + // Do not update state for labels. This will be done afterwards. + interval.setSpillState(SpillState.NoSpillStore); + } + break; + + case NoSpillStore: + assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created"; + if (defPos < interval.spillDefinitionPos() - 2) { + // second definition found, so no spill optimization possible for this interval + interval.setSpillState(SpillState.NoOptimization); + } else { + // two consecutive definitions (because of two-operand LIR form) + assert allocator.blockForId(defPos) == allocator.blockForId(interval.spillDefinitionPos()) : "block must be equal"; + } + break; + + case NoOptimization: + // nothing to do + break; + + default: + throw new BailoutException("other states not allowed at this time"); + } + } + + @Override + protected void buildIntervals() { + super.buildIntervals(); + // fix spill state for phi/sigma intervals + for (Interval interval : allocator.intervals()) { + if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) { + // there was a definition in a phi/sigma + interval.setSpillState(SpillState.NoSpillStore); + } + } + if (TraceRAuseInterTraceHints.getValue()) { + addInterTraceHints(); + } + } + + private void addInterTraceHints() { + // set hints for phi/sigma intervals + LIR lir = allocator.getLIR(); + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { + LabelOp label = SSIUtils.incoming(lir, block); + for (AbstractBlockBase<?> pred : block.getPredecessors()) { + if (isAllocatedOrCurrent(block, pred)) { + BlockEndOp outgoing = SSIUtils.outgoing(lir, pred); + for (int i = 0; i < outgoing.getOutgoingSize(); i++) { + Value toValue = label.getIncomingValue(i); + if (!isIllegal(toValue)) { + Value fromValue = outgoing.getOutgoingValue(i); + assert sameTrace(block, pred) || !isVariable(fromValue) : "Unallocated variable: " + fromValue; + + if (isStackSlotValue(fromValue)) { + + } else if (isConstant(fromValue)) { + } else { + Interval from = allocator.getOrCreateInterval((AllocatableValue) fromValue); + Interval to = allocator.getOrCreateInterval((AllocatableValue) toValue); + setHint(label, to, from); + } + } + } + } + } + } + /* + * Set the first range for fixed intervals to [-1, 0] to avoid intersection with incoming + * values. + */ + for (Interval interval : allocator.intervals()) { + if (interval != null && isRegister(interval.operand)) { + Range range = interval.first(); + if (range == Range.EndMarker) { + interval.addRange(-1, 0); + } else if (range.from == 0 && range.to == 1) { + range.from = -1; + range.to = 0; + } + } + } + } + + @Override + protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { + if (op instanceof LabelOp) { + // skip method header + return RegisterPriority.None; + } + return super.registerPriorityOfOutputOperand(op); + } + + @Override + protected void handleMethodArguments(LIRInstruction op) { + if (op instanceof MoveOp) { + // do not optimize method arguments + return; + } + super.handleMethodArguments(op); + } + + /** + * Performs a backward dataflow analysis to compute global live sets (i.e. + * {@link BlockData#liveIn} and {@link BlockData#liveOut}) for each block. + */ + @Override + protected void computeGlobalLiveSets() { + try (Indent indent = Debug.logAndIndent("compute global live sets")) { + int numBlocks = allocator.blockCount(); + boolean changeOccurred; + boolean changeOccurredInBlock; + int iterationCount = 0; + BitSet liveOut = new BitSet(allocator.liveSetSize()); // scratch set for calculations + + /* + * Perform a backward dataflow analysis to compute liveOut and liveIn for each block. + * The loop is executed until a fixpoint is reached (no changes in an iteration). + */ + do { + changeOccurred = false; + + try (Indent indent2 = Debug.logAndIndent("new iteration %d", iterationCount)) { + + // iterate all blocks in reverse order + for (int i = numBlocks - 1; i >= 0; i--) { + AbstractBlockBase<?> block = allocator.blockAt(i); + BlockData blockSets = allocator.getBlockData(block); + + changeOccurredInBlock = false; + + /* liveOut(block) is the union of liveIn(sux), for successors sux of block. */ + int n = block.getSuccessorCount(); + if (n > 0) { + liveOut.clear(); + // block has successors + if (n > 0) { + for (AbstractBlockBase<?> successor : block.getSuccessors()) { + if (allocator.sortedBlocks().contains(successor)) { + liveOut.or(allocator.getBlockData(successor).liveIn); + } + } + } + + if (!blockSets.liveOut.equals(liveOut)) { + /* + * A change occurred. Swap the old and new live out sets to avoid + * copying. + */ + BitSet temp = blockSets.liveOut; + blockSets.liveOut = liveOut; + liveOut = temp; + + changeOccurred = true; + changeOccurredInBlock = true; + } + } + + if (iterationCount == 0 || changeOccurredInBlock) { + /* + * liveIn(block) is the union of liveGen(block) with (liveOut(block) & + * !liveKill(block)). + * + * Note: liveIn has to be computed only in first iteration or if liveOut + * has changed! + */ + BitSet liveIn = blockSets.liveIn; + liveIn.clear(); + liveIn.or(blockSets.liveOut); + liveIn.andNot(blockSets.liveKill); + liveIn.or(blockSets.liveGen); + + if (Debug.isLogEnabled()) { + Debug.log("block %d: livein = %s, liveout = %s", block.getId(), liveIn, blockSets.liveOut); + } + } + } + iterationCount++; + + if (changeOccurred && iterationCount > 50) { + throw new BailoutException("too many iterations in computeGlobalLiveSets"); + } + } + } while (changeOccurred); + + if (DetailedAsserts.getValue()) { + verifyLiveness(); + } + + // check that the liveIn set of the first block is empty + AbstractBlockBase<?> startBlock = allocator.blockAt(0); + if (allocator.getBlockData(startBlock).liveIn.cardinality() != 0) { + if (DetailedAsserts.getValue()) { + reportFailure(numBlocks); + } + // bailout if this occurs in product mode. + throw new JVMCIError("liveIn set of first block must be empty: " + allocator.getBlockData(startBlock).liveIn); + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,108 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.trace; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor; +import com.oracle.graal.lir.ssi.*; + +public class TraceLinearScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase { + + private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]"); + private static final DebugMetric numStackToStackMoves = Debug.metric("SSI LSRA[numStackToStackMoves]"); + + public TraceLinearScanResolveDataFlowPhase(LinearScan allocator) { + super(allocator); + } + + @Override + protected void optimizeEmptyBlocks(MoveResolver moveResolver, BitSet blockCompleted) { + // do not optimize + } + + @Override + protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { + assert midBlock == null; + if (containedInTrace(fromBlock) && containedInTrace(toBlock)) { + super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver); + SSIUtils.forEachValuePair(allocator.getLIR(), toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock)); + } + + } + + private boolean containedInTrace(AbstractBlockBase<?> block) { + return allocator.sortedBlocks().contains(block); + } + + private class MyPhiValueVisitor implements PhiValueVisitor { + final MoveResolver moveResolver; + final int toId; + final int fromId; + + public MyPhiValueVisitor(MoveResolver moveResolver, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock) { + this.moveResolver = moveResolver; + toId = allocator.getFirstLirInstructionId(toBlock); + fromId = allocator.getLastLirInstructionId(fromBlock); + assert fromId >= 0; + } + + public void visit(Value phiIn, Value phiOut) { + assert !isRegister(phiOut) : "Out is a register: " + phiOut; + assert !isRegister(phiIn) : "In is a register: " + phiIn; + if (Value.ILLEGAL.equals(phiIn)) { + // The value not needed in this branch. + return; + } + if (isVirtualStackSlot(phiIn) && isVirtualStackSlot(phiOut) && phiIn.equals(phiOut)) { + // no need to handle virtual stack slots + return; + } + Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toId, LIRInstruction.OperandMode.DEF); + if (isConstant(phiOut)) { + numSSIResolutionMoves.increment(); + moveResolver.addMapping(phiOut, toInterval); + } else { + Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), fromId, LIRInstruction.OperandMode.DEF); + if (fromInterval != toInterval) { + numSSIResolutionMoves.increment(); + if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { + moveResolver.addMapping(fromInterval, toInterval); + } else { + numStackToStackMoves.increment(); + moveResolver.addMapping(fromInterval, toInterval); + } + } + } + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceRegisterAllocationPhase.java Fri Jul 24 09:21:04 2015 +0200 @@ -0,0 +1,168 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.trace; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.meta.*; +import jdk.internal.jvmci.options.*; + +import com.oracle.graal.compiler.common.alloc.*; +import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.MoveOp; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; +import com.oracle.graal.lir.phases.*; +import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor; +import com.oracle.graal.lir.ssi.*; + +public class TraceRegisterAllocationPhase extends AllocationPhase { + public static class Options { + // @formatter:off + @Option(help = "Use inter-trace register hints.", type = OptionType.Debug) + public static final OptionValue<Boolean> TraceRAuseInterTraceHints = new OptionValue<>(true); + // @formatter:on + } + + static final int TRACE_DUMP_LEVEL = 3; + + @Override + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory, + RegisterAllocationConfig registerAllocationConfig) { + LIR lir = lirGenRes.getLIR(); + assert SSIVerifier.verify(lir) : "LIR not in SSI form."; + B startBlock = linearScanOrder.get(0); + assert startBlock.equals(lir.getControlFlowGraph().getStartBlock()); + TraceBuilderResult<B> resultTraces = TraceBuilder.computeTraces(startBlock, linearScanOrder); + + Debug.dump(lir, "Before TraceRegisterAllocation"); + int traceNumber = 0; + for (List<B> trace : resultTraces.getTraces()) { + try (Indent i = Debug.logAndIndent("Allocating Trace%d: %s", traceNumber, trace); Scope s = Debug.scope("AllocateTrace", trace)) { + Debug.dump(TRACE_DUMP_LEVEL, trace, "Trace" + traceNumber + ": " + trace); + TraceLinearScan allocator = new TraceLinearScan(target, lirGenRes, spillMoveFactory, registerAllocationConfig, trace, resultTraces); + allocator.allocate(target, lirGenRes, codeEmittingOrder, linearScanOrder, spillMoveFactory, registerAllocationConfig); + Debug.dump(TRACE_DUMP_LEVEL, trace, "After Trace" + traceNumber + ": " + trace); + traceNumber++; + } catch (Throwable e) { + throw Debug.handle(e); + } + unnumberInstructions(trace, lir); + } + Debug.dump(lir, "After trace allocation"); + + resolveGlobalDataFlow(resultTraces, lirGenRes, spillMoveFactory, target.arch); + Debug.dump(lir, "After global dataflow resolution"); + + if (replaceStackToStackMoves(lir, spillMoveFactory)) { + Debug.dump(lir, "After fixing stack to stack moves"); + } + /* + * Incoming Values are needed for the RegisterVerifier, otherwise SIGMAs/PHIs where the Out + * and In value matches (ie. there is no resolution move) are falsely detected as errors. + */ + for (AbstractBlockBase<?> toBlock : lir.getControlFlowGraph().getBlocks()) { + if (toBlock.getPredecessorCount() != 0) { + SSIUtils.removeIncoming(lir, toBlock); + } else { + assert lir.getControlFlowGraph().getStartBlock().equals(toBlock); + } + SSIUtils.removeOutgoing(lir, toBlock); + } + } + + /** + * Fixup stack to stack moves introduced by stack arguments. + * + * TODO (je) find a better solution. + */ + private static boolean replaceStackToStackMoves(LIR lir, SpillMoveFactory spillMoveFactory) { + boolean changed = false; + for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) { + List<LIRInstruction> instructions = lir.getLIRforBlock(block); + for (int i = 0; i < instructions.size(); i++) { + LIRInstruction inst = instructions.get(i); + + if (inst instanceof MoveOp) { + MoveOp move = (MoveOp) inst; + if (isStackSlotValue(move.getInput()) && isStackSlotValue(move.getResult())) { + instructions.set(i, spillMoveFactory.createStackMove(move.getResult(), move.getInput())); + changed = true; + } + } + } + } + return changed; + } + + private static <B extends AbstractBlockBase<B>> void resolveGlobalDataFlow(TraceBuilderResult<B> resultTraces, LIRGenerationResult lirGenRes, SpillMoveFactory spillMoveFactory, Architecture arch) { + LIR lir = lirGenRes.getLIR(); + /* Resolve trace global data-flow mismatch. */ + TraceGlobalMoveResolver moveResolver = new TraceGlobalMoveResolver(lirGenRes, spillMoveFactory, arch); + PhiValueVisitor visitor = (Value phiIn, Value phiOut) -> { + if (!isIllegal(phiIn) && !TraceGlobalMoveResolver.isMoveToSelf(phiOut, phiIn)) { + moveResolver.addMapping(phiOut, (AllocatableValue) phiIn); + } + }; + + try (Indent indent = Debug.logAndIndent("Trace global move resolution")) { + for (List<B> trace : resultTraces.getTraces()) { + for (AbstractBlockBase<?> fromBlock : trace) { + for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) { + if (resultTraces.getTraceForBlock(fromBlock) != resultTraces.getTraceForBlock(toBlock)) { + try (Indent indent0 = Debug.logAndIndent("Handle trace edge from %s (Trace%d) to %s (Trace%d)", fromBlock, resultTraces.getTraceForBlock(fromBlock), toBlock, + resultTraces.getTraceForBlock(toBlock))) { + + final List<LIRInstruction> instructions; + final int insertIdx; + if (fromBlock.getSuccessorCount() == 1) { + instructions = lir.getLIRforBlock(fromBlock); + insertIdx = instructions.size() - 1; + } else { + assert toBlock.getPredecessorCount() == 1; + instructions = lir.getLIRforBlock(toBlock); + insertIdx = 1; + } + + moveResolver.setInsertPosition(instructions, insertIdx); + SSIUtils.forEachValuePair(lir, toBlock, fromBlock, visitor); + moveResolver.resolveAndAppendMoves(); + } + } + } + } + } + } + } + + private static void unnumberInstructions(List<? extends AbstractBlockBase<?>> trace, LIR lir) { + trace.stream().flatMap(b -> lir.getLIRforBlock(b).stream()).forEach(op -> op.setId(-1)); + } +}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/AllocationStage.java Fri Jul 24 09:04:14 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/AllocationStage.java Fri Jul 24 09:21:04 2015 +0200 @@ -23,7 +23,9 @@ package com.oracle.graal.lir.phases; import static com.oracle.graal.compiler.common.BackendOptions.UserOptions.*; + import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.alloc.trace.*; import com.oracle.graal.lir.dfa.*; import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext; import com.oracle.graal.lir.stackslotalloc.*;