Mercurial > hg > graal-jvmci-8
diff graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/OptimizeSpillPosition.java @ 21322:73942ac6e650
LinearScan: outsource OptimizeSpillPosition.
author | Josef Eisl <josef.eisl@jku.at> |
---|---|
date | Tue, 12 May 2015 10:57:59 +0200 |
parents | |
children | b8dcf353b822 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/OptimizeSpillPosition.java Tue May 12 10:57:59 2015 +0200 @@ -0,0 +1,215 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra; + +import static com.oracle.graal.api.code.ValueUtil.*; +import static com.oracle.graal.compiler.common.cfg.AbstractControlFlowGraph.*; + +import java.util.*; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.api.meta.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandMode; +import com.oracle.graal.lir.alloc.lsra.Interval.SpillState; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; +import com.oracle.graal.lir.phases.*; + +final class OptimizeSpillPosition extends AllocationPhase { + + private static final DebugMetric betterSpillPos = Debug.metric("BetterSpillPosition"); + private static final DebugMetric betterSpillPosWithLowerProbability = Debug.metric("BetterSpillPositionWithLowerProbability"); + + private final LinearScan allocator; + + OptimizeSpillPosition(LinearScan allocator) { + this.allocator = allocator; + } + + @Override + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory) { + optimizeSpillPosition(); + allocator.printIntervals("After optimize spill position"); + } + + private void optimizeSpillPosition() { + LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.ir.linearScanOrder().size()]; + for (Interval interval : allocator.intervals) { + if (interval != null && interval.isSplitParent() && interval.spillState() == SpillState.SpillInDominator) { + AbstractBlockBase<?> defBlock = allocator.blockForId(interval.spillDefinitionPos()); + AbstractBlockBase<?> spillBlock = null; + Interval firstSpillChild = null; + try (Indent indent = Debug.logAndIndent("interval %s (%s)", interval, defBlock)) { + for (Interval splitChild : interval.getSplitChildren()) { + if (isStackSlotValue(splitChild.location())) { + if (firstSpillChild == null || splitChild.from() < firstSpillChild.from()) { + firstSpillChild = splitChild; + } else { + assert firstSpillChild.from() < splitChild.from(); + } + // iterate all blocks where the interval has use positions + for (AbstractBlockBase<?> splitBlock : blocksForInterval(splitChild)) { + if (dominates(defBlock, splitBlock)) { + if (Debug.isLogEnabled()) { + Debug.log("Split interval %s, block %s", splitChild, splitBlock); + } + if (spillBlock == null) { + spillBlock = splitBlock; + } else { + spillBlock = commonDominator(spillBlock, splitBlock); + assert spillBlock != null; + } + } + } + } + } + if (spillBlock == null) { + // no spill interval + interval.setSpillState(SpillState.StoreAtDefinition); + } else { + // move out of loops + if (defBlock.getLoopDepth() < spillBlock.getLoopDepth()) { + spillBlock = moveSpillOutOfLoop(defBlock, spillBlock); + } + + /* + * If the spill block is the begin of the first split child (aka the value + * is on the stack) spill in the dominator. + */ + assert firstSpillChild != null; + if (!defBlock.equals(spillBlock) && spillBlock.equals(allocator.blockForId(firstSpillChild.from()))) { + AbstractBlockBase<?> dom = spillBlock.getDominator(); + if (Debug.isLogEnabled()) { + Debug.log("Spill block (%s) is the beginning of a spill child -> use dominator (%s)", spillBlock, dom); + } + spillBlock = dom; + } + + if (!defBlock.equals(spillBlock)) { + assert dominates(defBlock, spillBlock); + betterSpillPos.increment(); + if (Debug.isLogEnabled()) { + Debug.log("Better spill position found (Block %s)", spillBlock); + } + + if (defBlock.probability() <= spillBlock.probability()) { + // better spill block has the same probability -> do nothing + interval.setSpillState(SpillState.StoreAtDefinition); + } else { + LIRInsertionBuffer insertionBuffer = insertionBuffers[spillBlock.getId()]; + if (insertionBuffer == null) { + insertionBuffer = new LIRInsertionBuffer(); + insertionBuffers[spillBlock.getId()] = insertionBuffer; + insertionBuffer.init(allocator.ir.getLIRforBlock(spillBlock)); + } + int spillOpId = allocator.getFirstLirInstructionId(spillBlock); + // insert spill move + AllocatableValue fromLocation = interval.getSplitChildAtOpId(spillOpId, OperandMode.DEF, allocator).location(); + AllocatableValue toLocation = LinearScan.canonicalSpillOpr(interval); + LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation); + move.setId(LinearScan.DOMINATOR_SPILL_MOVE_ID); + /* + * We can use the insertion buffer directly because we always insert + * at position 1. + */ + insertionBuffer.append(1, move); + + betterSpillPosWithLowerProbability.increment(); + interval.setSpillDefinitionPos(spillOpId); + } + } else { + // definition is the best choice + interval.setSpillState(SpillState.StoreAtDefinition); + } + } + } + } + } + for (LIRInsertionBuffer insertionBuffer : insertionBuffers) { + if (insertionBuffer != null) { + assert insertionBuffer.initialized() : "Insertion buffer is nonnull but not initialized!"; + insertionBuffer.finish(); + } + } + } + + /** + * Iterate over all {@link AbstractBlockBase blocks} of an interval. + */ + private class IntervalBlockIterator implements Iterator<AbstractBlockBase<?>> { + + Range range; + AbstractBlockBase<?> block; + + public IntervalBlockIterator(Interval interval) { + range = interval.first(); + block = allocator.blockForId(range.from); + } + + public AbstractBlockBase<?> next() { + AbstractBlockBase<?> currentBlock = block; + int nextBlockIndex = block.getLinearScanNumber() + 1; + if (nextBlockIndex < allocator.sortedBlocks.size()) { + block = allocator.sortedBlocks.get(nextBlockIndex); + if (range.to <= allocator.getFirstLirInstructionId(block)) { + range = range.next; + if (range == Range.EndMarker) { + block = null; + } else { + block = allocator.blockForId(range.from); + } + } + } else { + block = null; + } + return currentBlock; + } + + public boolean hasNext() { + return block != null; + } + } + + private Iterable<AbstractBlockBase<?>> blocksForInterval(Interval interval) { + return new Iterable<AbstractBlockBase<?>>() { + public Iterator<AbstractBlockBase<?>> iterator() { + return new IntervalBlockIterator(interval); + } + }; + } + + private static AbstractBlockBase<?> moveSpillOutOfLoop(AbstractBlockBase<?> defBlock, AbstractBlockBase<?> spillBlock) { + int defLoopDepth = defBlock.getLoopDepth(); + for (AbstractBlockBase<?> block = spillBlock.getDominator(); !defBlock.equals(block); block = block.getDominator()) { + assert block != null : "spill block not dominated by definition block?"; + if (block.getLoopDepth() <= defLoopDepth) { + assert block.getLoopDepth() == defLoopDepth : "Cannot spill an interval outside of the loop where it is defined!"; + return block; + } + } + return defBlock; + } +}