Mercurial > hg > graal-compiler
changeset 22598:5396006b321a
TraceRA: always insert spill-moves and use TraceLinearScanResolveDataFlowPhase only for SSI resolution.
author | Josef Eisl <josef.eisl@jku.at> |
---|---|
date | Tue, 08 Sep 2015 10:50:21 +0200 |
parents | 9fd19e2fc0be |
children | b83f27f75684 |
files | graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanWalker.java |
diffstat | 3 files changed, 77 insertions(+), 102 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java Mon Sep 07 17:38:39 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java Tue Sep 08 10:50:21 2015 +0200 @@ -726,7 +726,7 @@ } protected TraceLinearScanResolveDataFlowPhase createResolveDataFlowPhase() { - return new TraceLinearScanResolveDataFlowPhase(this); + return new TraceLinearScanResolveDataFlowPhase(this, traceBuilderResult); } protected TraceLinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java Mon Sep 07 17:38:39 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java Tue Sep 08 10:50:21 2015 +0200 @@ -32,6 +32,7 @@ import jdk.internal.jvmci.meta.*; 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.lir.*; @@ -48,45 +49,21 @@ */ final class TraceLinearScanResolveDataFlowPhase extends AllocationPhase { - protected final TraceLinearScan allocator; + private final TraceLinearScan allocator; + private final TraceBuilderResult<?> traceBuilderResult; - protected TraceLinearScanResolveDataFlowPhase(TraceLinearScan allocator) { + protected TraceLinearScanResolveDataFlowPhase(TraceLinearScan allocator, TraceBuilderResult<?> traceBuilderResult) { this.allocator = allocator; + this.traceBuilderResult = traceBuilderResult; } @Override protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) { - resolveDataFlow(); + resolveDataFlow(allocator.sortedBlocks()); } - protected void resolveCollectMappings0(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, TraceLocalMoveResolver moveResolver) { - assert moveResolver.checkEmpty(); - assert midBlock == null || - (midBlock.getPredecessorCount() == 1 && midBlock.getSuccessorCount() == 1 && midBlock.getPredecessors().get(0).equals(fromBlock) && midBlock.getSuccessors().get(0).equals( - toBlock)); - - int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock); - int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1; - int numOperands = allocator.operandSize(); - BitSet liveAtEdge = allocator.getBlockData(toBlock).liveIn; - - // visit all variables for which the liveAtEdge bit is set - for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) { - assert operandNum < numOperands : "live information set for not exisiting interval"; - assert allocator.getBlockData(fromBlock).liveOut.get(operandNum) && allocator.getBlockData(toBlock).liveIn.get(operandNum) : "interval not live at this edge"; - - TraceInterval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF); - TraceInterval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); - - if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) { - // need to insert move instruction - moveResolver.addMapping(fromInterval, toInterval); - } - } - } - - void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) { + private void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) { if (fromBlock.getSuccessorCount() <= 1) { if (Debug.isLogEnabled()) { Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId()); @@ -128,79 +105,52 @@ * have been split. */ @SuppressWarnings("try") - protected void resolveDataFlow() { + private void resolveDataFlow(List<? extends AbstractBlockBase<?>> blocks) { + if (blocks.size() < 2) { + // no resolution necessary + return; + } try (Indent indent = Debug.logAndIndent("resolve data flow")) { TraceLocalMoveResolver moveResolver = allocator.createMoveResolver(); - BitSet blockCompleted = new BitSet(allocator.blockCount()); - - BitSet alreadyResolved = new BitSet(allocator.blockCount()); - for (AbstractBlockBase<?> fromBlock : allocator.sortedBlocks()) { - if (!blockCompleted.get(fromBlock.getLinearScanNumber())) { - alreadyResolved.clear(); - alreadyResolved.or(blockCompleted); - - for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) { - - /* - * Check for duplicate edges between the same blocks (can happen with switch - * blocks). - */ - if (!alreadyResolved.get(toBlock.getLinearScanNumber())) { - if (Debug.isLogEnabled()) { - Debug.log("processing edge between B%d and B%d", fromBlock.getId(), toBlock.getId()); - } - - alreadyResolved.set(toBlock.getLinearScanNumber()); - - // collect all intervals that have been split between - // fromBlock and toBlock - resolveCollectMappings(fromBlock, toBlock, null, moveResolver); - if (moveResolver.hasMappings()) { - resolveFindInsertPos(fromBlock, toBlock, moveResolver); - moveResolver.resolveAndAppendMoves(); - } - } - } + ListIterator<? extends AbstractBlockBase<?>> it = blocks.listIterator(); + AbstractBlockBase<?> toBlock = null; + for (AbstractBlockBase<?> fromBlock = it.next(); it.hasNext(); fromBlock = toBlock) { + toBlock = it.next(); + assert containedInTrace(fromBlock) : "Not in Trace: " + fromBlock; + assert containedInTrace(toBlock) : "Not in Trace: " + toBlock; + resolveCollectMappings(fromBlock, toBlock, moveResolver); + } + assert blocks.get(blocks.size() - 1).equals(toBlock); + if (toBlock.isLoopEnd()) { + assert toBlock.getSuccessorCount() == 1; + AbstractBlockBase<?> loopHeader = toBlock.getSuccessors().get(0); + if (containedInTrace(loopHeader)) { + resolveCollectMappings(toBlock, loopHeader, moveResolver); } } } } - protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, TraceLocalMoveResolver moveResolver) { - assert midBlock == null; - if (containedInTrace(fromBlock) && containedInTrace(toBlock)) { - assert moveResolver.checkEmpty(); - assert midBlock == null || - (midBlock.getPredecessorCount() == 1 && midBlock.getSuccessorCount() == 1 && midBlock.getPredecessors().get(0).equals(fromBlock) && midBlock.getSuccessors().get(0).equals( - toBlock)); - - int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock); - int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1; - int numOperands = allocator.operandSize(); - BitSet liveAtEdge = allocator.getBlockData(toBlock).liveIn; - - // visit all variables for which the liveAtEdge bit is set - for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) { - assert operandNum < numOperands : "live information set for not exisiting interval"; - assert allocator.getBlockData(fromBlock).liveOut.get(operandNum) && allocator.getBlockData(toBlock).liveIn.get(operandNum) : "interval not live at this edge"; - - TraceInterval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF); - TraceInterval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); - - if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) { - // need to insert move instruction - moveResolver.addMapping(fromInterval, toInterval); - } + private void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) { + try (Indent indent0 = Debug.logAndIndent("Edge %s -> %s", fromBlock, toBlock)) { + // collect all intervals that have been split between + // fromBlock and toBlock + SSIUtil.forEachValuePair(allocator.getLIR(), toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock)); + if (moveResolver.hasMappings()) { + resolveFindInsertPos(fromBlock, toBlock, moveResolver); + moveResolver.resolveAndAppendMoves(); } - SSIUtil.forEachValuePair(allocator.getLIR(), toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock)); } - } private boolean containedInTrace(AbstractBlockBase<?> block) { - return allocator.sortedBlocks().contains(block); + return currentTrace() == traceBuilderResult.getTraceForBlock(block); + } + + private int currentTrace() { + return traceBuilderResult.getTraceForBlock(allocator.sortedBlocks().get(0)); } private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]");
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanWalker.java Mon Sep 07 17:38:39 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanWalker.java Tue Sep 08 10:50:21 2015 +0200 @@ -37,6 +37,8 @@ import com.oracle.graal.compiler.common.util.*; 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.ValueMoveOp; import com.oracle.graal.lir.alloc.lsra.*; import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterPriority; @@ -233,6 +235,26 @@ } } + private int insertIdAtBasicBlockBoundary(int opId) { + assert allocator.isBlockBegin(opId) : "Not a block begin: " + opId; + assert allocator.instructionForId(opId) instanceof LabelOp; + assert allocator.instructionForId(opId - 2) instanceof BlockEndOp; + + AbstractBlockBase<?> toBlock = allocator.blockForId(opId); + AbstractBlockBase<?> fromBlock = allocator.blockForId(opId - 2); + + final int operandId; + if (fromBlock.getSuccessorCount() == 1) { + // insert move in predecessor + operandId = opId - 2; + } else { + assert toBlock.getPredecessorCount() == 1 : String.format("Critical Edge? %s->%s", fromBlock, toBlock); + // insert move in predecessor + operandId = opId + 2; + } + return operandId; + } + private void insertMove(int operandId, TraceInterval srcIt, TraceInterval dstIt) { // output all moves here. When source and target are equal, the move is // optimized away later in assignRegNums @@ -335,12 +357,13 @@ // must calculate this before the actual split is performed and before split position is // moved to odd opId boolean isBlockBegin = allocator.isBlockBegin(optimalSplitPos); - boolean moveNecessary = !isBlockBegin; + boolean moveNecessary = true; - if (!isBlockBegin) { - // move position before actual instruction (odd opId) - optimalSplitPos = (optimalSplitPos - 1) | 1; + if (isBlockBegin) { + optimalSplitPos = insertIdAtBasicBlockBoundary(optimalSplitPos); } + // move position before actual instruction (odd opId) + optimalSplitPos = (optimalSplitPos - 1) | 1; if (Debug.isLogEnabled()) { Debug.log("splitting at position %d", optimalSplitPos); @@ -434,10 +457,11 @@ assert optimalSplitPos < interval.to() : "cannot split at end of interval"; assert optimalSplitPos >= interval.from() : "cannot split before start of interval"; - if (!allocator.isBlockBegin(optimalSplitPos)) { - // move position before actual instruction (odd opId) - optimalSplitPos = (optimalSplitPos - 1) | 1; + if (allocator.isBlockBegin(optimalSplitPos)) { + optimalSplitPos = insertIdAtBasicBlockBoundary(optimalSplitPos); } + // move position before actual instruction (odd opId) + optimalSplitPos = (optimalSplitPos - 1) | 1; try (Indent indent2 = Debug.logAndIndent("splitting at position %d", optimalSplitPos)) { assert allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary"; @@ -448,12 +472,13 @@ handleSpillSlot(spilledPart); changeSpillState(spilledPart, optimalSplitPos); - if (!allocator.isBlockBegin(optimalSplitPos)) { - if (Debug.isLogEnabled()) { - Debug.log("inserting move from interval %d to %d", interval.operandNumber, spilledPart.operandNumber); - } - insertMove(optimalSplitPos, interval, spilledPart); + if (allocator.isBlockBegin(optimalSplitPos)) { + optimalSplitPos = insertIdAtBasicBlockBoundary(optimalSplitPos); } + if (Debug.isLogEnabled()) { + Debug.log("inserting move from interval %s to %d", interval, spilledPart); + } + insertMove(optimalSplitPos, interval, spilledPart); // the currentSplitChild is needed later when moves are inserted for reloading assert spilledPart.currentSplitChild() == interval : "overwriting wrong currentSplitChild";