Mercurial > hg > graal-compiler
changeset 22547:544f172cb2db
TraceRA: merge trace.LinearScan and TraceLinearScan.
line wrap: on
line diff
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/Interval.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/Interval.java Mon Aug 31 13:21:01 2015 +0200 @@ -37,7 +37,7 @@ import com.oracle.graal.lir.*; /** - * Represents an interval in the {@linkplain LinearScan linear scan register allocator}. + * Represents an interval in the {@linkplain TraceLinearScan linear scan register allocator}. */ public final class Interval { @@ -829,7 +829,7 @@ return null; } - Interval getSplitChildAtOpId(int opId, LIRInstruction.OperandMode mode, LinearScan allocator) { + Interval getSplitChildAtOpId(int opId, LIRInstruction.OperandMode mode, TraceLinearScan allocator) { assert isSplitParent() : "can only be called for split parents"; assert opId >= 0 : "invalid opId (method cannot be called for spill moves)"; @@ -865,7 +865,7 @@ } } - private boolean checkSplitChild(Interval result, int opId, LinearScan allocator, int toOffset, LIRInstruction.OperandMode mode) { + private boolean checkSplitChild(Interval result, int opId, TraceLinearScan allocator, int toOffset, LIRInstruction.OperandMode mode) { if (result == null) { // this is an error StringBuilder msg = new StringBuilder(this.toString()).append(" has no child at ").append(opId); @@ -1067,7 +1067,7 @@ } } - Interval newSplitChild(LinearScan allocator) { + Interval newSplitChild(TraceLinearScan allocator) { // allocate new interval Interval parent = splitParent(); Interval result = allocator.createDerivedInterval(parent); @@ -1103,7 +1103,7 @@ * @param allocator the register allocator context * @return the child interval split off from this interval */ - Interval split(int splitPos, LinearScan allocator) { + Interval split(int splitPos, TraceLinearScan allocator) { assert isVariable(operand) : "cannot split fixed intervals"; // allocate new interval @@ -1152,7 +1152,7 @@ * Currently, only the first range can be split, and the new interval must not have split * positions */ - Interval splitFromStart(int splitPos, LinearScan allocator) { + Interval splitFromStart(int splitPos, TraceLinearScan allocator) { assert isVariable(operand) : "cannot split fixed intervals"; assert splitPos > from() && splitPos < to() : "can only split inside interval"; assert splitPos > first.from && splitPos <= first.to : "can only split inside first range"; @@ -1253,7 +1253,7 @@ * * @param allocator the register allocator context */ - public String logString(LinearScan allocator) { + public String logString(TraceLinearScan allocator) { StringBuilder buf = new StringBuilder(100); buf.append(operandNumber).append(':').append(operand).append(' '); if (!isRegister(operand)) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/IntervalWalker.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/IntervalWalker.java Mon Aug 31 13:21:01 2015 +0200 @@ -32,7 +32,7 @@ */ public class IntervalWalker { - protected final LinearScan allocator; + protected final TraceLinearScan allocator; /** * Sorted list of intervals, not live before the current position. @@ -86,7 +86,7 @@ * @param unhandledAny the list of unhandled {@linkplain RegisterBinding#Any non-fixed} * intervals */ - IntervalWalker(LinearScan allocator, Interval unhandledFixed, Interval unhandledAny) { + IntervalWalker(TraceLinearScan allocator, Interval unhandledFixed, Interval unhandledAny) { this.allocator = allocator; unhandledLists = new RegisterBindingLists(unhandledFixed, unhandledAny, Interval.EndMarker);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScan.java Mon Aug 31 13:11:26 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,882 +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.trace; - -import static com.oracle.graal.compiler.common.GraalOptions.*; -import static com.oracle.graal.lir.LIRValueUtil.*; -import static jdk.internal.jvmci.code.CodeUtil.*; -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.*; -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.LIRInstruction.OperandFlag; -import com.oracle.graal.lir.LIRInstruction.OperandMode; -import com.oracle.graal.lir.alloc.trace.Interval.RegisterBinding; -import com.oracle.graal.lir.framemap.*; -import com.oracle.graal.lir.gen.*; -import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; -import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext; - -/** - * An implementation of the linear scan register allocator algorithm described in <a - * href="http://doi.acm.org/10.1145/1064979.1064998" - * >"Optimized Interval Splitting in a Linear Scan Register Allocator"</a> by Christian Wimmer and - * Hanspeter Moessenboeck. - */ -public class LinearScan { - - public static class BlockData { - - /** - * Bit map specifying which operands are live upon entry to this block. These are values - * used in this block or any of its successors where such value are not defined in this - * block. The bit index of an operand is its {@linkplain LinearScan#operandNumber(Value) - * operand number}. - */ - public BitSet liveIn; - - /** - * Bit map specifying which operands are live upon exit from this block. These are values - * used in a successor block that are either defined in this block or were live upon entry - * to this block. The bit index of an operand is its - * {@linkplain LinearScan#operandNumber(Value) operand number}. - */ - public BitSet liveOut; - - /** - * Bit map specifying which operands are used (before being defined) in this block. That is, - * these are the values that are live upon entry to the block. The bit index of an operand - * is its {@linkplain LinearScan#operandNumber(Value) operand number}. - */ - public BitSet liveGen; - - /** - * Bit map specifying which operands are defined/overwritten in this block. The bit index of - * an operand is its {@linkplain LinearScan#operandNumber(Value) operand number}. - */ - public BitSet liveKill; - } - - public static final int DOMINATOR_SPILL_MOVE_ID = -2; - private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1; - - private final LIR ir; - private final FrameMapBuilder frameMapBuilder; - private final RegisterAttributes[] registerAttributes; - private final Register[] registers; - private final RegisterAllocationConfig regAllocConfig; - private final SpillMoveFactory moveFactory; - - private final BlockMap<BlockData> blockData; - - /** - * List of blocks in linear-scan order. This is only correct as long as the CFG does not change. - */ - private final List<? extends AbstractBlockBase<?>> sortedBlocks; - - /** @see #intervals() */ - private Interval[] intervals; - - /** - * The number of valid entries in {@link #intervals}. - */ - private int intervalsSize; - - /** - * The index of the first entry in {@link #intervals} for a - * {@linkplain #createDerivedInterval(Interval) derived interval}. - */ - private int firstDerivedIntervalIndex = -1; - - /** - * Intervals sorted by {@link Interval#from()}. - */ - private Interval[] sortedIntervals; - - /** - * Map from an instruction {@linkplain LIRInstruction#id id} to the instruction. Entries should - * be retrieved with {@link #instructionForId(int)} as the id is not simply an index into this - * array. - */ - private LIRInstruction[] opIdToInstructionMap; - - /** - * Map from an instruction {@linkplain LIRInstruction#id id} to the - * {@linkplain AbstractBlockBase block} containing the instruction. Entries should be retrieved - * with {@link #blockForId(int)} as the id is not simply an index into this array. - */ - private AbstractBlockBase<?>[] opIdToBlockMap; - - /** - * The {@linkplain #operandNumber(Value) number} of the first variable operand allocated. - */ - private final int firstVariableNumber; - - protected LinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, - List<? extends AbstractBlockBase<?>> sortedBlocks) { - this.ir = res.getLIR(); - this.moveFactory = spillMoveFactory; - this.frameMapBuilder = res.getFrameMapBuilder(); - this.sortedBlocks = sortedBlocks; - this.registerAttributes = regAllocConfig.getRegisterConfig().getAttributesMap(); - this.regAllocConfig = regAllocConfig; - - this.registers = target.arch.getRegisters(); - this.firstVariableNumber = getRegisters().length; - this.blockData = new BlockMap<>(ir.getControlFlowGraph()); - } - - public int getFirstLirInstructionId(AbstractBlockBase<?> block) { - int result = ir.getLIRforBlock(block).get(0).id(); - assert result >= 0; - return result; - } - - public int getLastLirInstructionId(AbstractBlockBase<?> block) { - List<LIRInstruction> instructions = ir.getLIRforBlock(block); - int result = instructions.get(instructions.size() - 1).id(); - assert result >= 0; - return result; - } - - public SpillMoveFactory getSpillMoveFactory() { - return moveFactory; - } - - protected MoveResolver createMoveResolver() { - MoveResolver moveResolver = new MoveResolver(this); - assert moveResolver.checkEmpty(); - return moveResolver; - } - - public static boolean isVariableOrRegister(Value value) { - return isVariable(value) || isRegister(value); - } - - /** - * Converts an operand (variable or register) to an index in a flat address space covering all - * the {@linkplain Variable variables} and {@linkplain RegisterValue registers} being processed - * by this allocator. - */ - int operandNumber(Value operand) { - if (isRegister(operand)) { - int number = asRegister(operand).number; - assert number < firstVariableNumber; - return number; - } - assert isVariable(operand) : operand; - return firstVariableNumber + ((Variable) operand).index; - } - - /** - * Gets the number of operands. This value will increase by 1 for new variable. - */ - int operandSize() { - return firstVariableNumber + ir.numVariables(); - } - - /** - * Gets the highest operand number for a register operand. This value will never change. - */ - int maxRegisterNumber() { - return firstVariableNumber - 1; - } - - public BlockData getBlockData(AbstractBlockBase<?> block) { - return blockData.get(block); - } - - void initBlockData(AbstractBlockBase<?> block) { - blockData.put(block, new BlockData()); - } - - static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() { - - @Override - public boolean apply(Interval i) { - return isRegister(i.operand); - } - }; - - static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() { - - @Override - public boolean apply(Interval i) { - return isVariable(i.operand); - } - }; - - static final IntervalPredicate IS_STACK_INTERVAL = new IntervalPredicate() { - - @Override - public boolean apply(Interval i) { - return !isRegister(i.operand); - } - }; - - /** - * Gets an object describing the attributes of a given register according to this register - * configuration. - */ - public RegisterAttributes attributes(Register reg) { - return registerAttributes[reg.number]; - } - - void assignSpillSlot(Interval interval) { - /* - * Assign the canonical spill slot of the parent (if a part of the interval is already - * spilled) or allocate a new spill slot. - */ - if (interval.canMaterialize()) { - interval.assignLocation(Value.ILLEGAL); - } else if (interval.spillSlot() != null) { - interval.assignLocation(interval.spillSlot()); - } else { - VirtualStackSlot slot = frameMapBuilder.allocateSpillSlot(interval.kind()); - interval.setSpillSlot(slot); - interval.assignLocation(slot); - } - } - - /** - * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals. - */ - public Interval[] intervals() { - return intervals; - } - - void initIntervals() { - intervalsSize = operandSize(); - intervals = new Interval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)]; - } - - /** - * Creates a new interval. - * - * @param operand the operand for the interval - * @return the created interval - */ - Interval createInterval(AllocatableValue operand) { - assert isLegal(operand); - int operandNumber = operandNumber(operand); - Interval interval = new Interval(operand, operandNumber); - assert operandNumber < intervalsSize; - assert intervals[operandNumber] == null; - intervals[operandNumber] = interval; - return interval; - } - - /** - * Creates an interval as a result of splitting or spilling another interval. - * - * @param source an interval being split of spilled - * @return a new interval derived from {@code source} - */ - Interval createDerivedInterval(Interval source) { - if (firstDerivedIntervalIndex == -1) { - firstDerivedIntervalIndex = intervalsSize; - } - if (intervalsSize == intervals.length) { - intervals = Arrays.copyOf(intervals, intervals.length + (intervals.length >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)); - } - intervalsSize++; - Variable variable = new Variable(source.kind(), ir.nextVariable()); - - Interval interval = createInterval(variable); - assert intervals[intervalsSize - 1] == interval; - return interval; - } - - // access to block list (sorted in linear scan order) - public int blockCount() { - return sortedBlocks.size(); - } - - public AbstractBlockBase<?> blockAt(int index) { - return sortedBlocks.get(index); - } - - /** - * Gets the size of the {@link BlockData#liveIn} and {@link BlockData#liveOut} sets for a basic - * block. These sets do not include any operands allocated as a result of creating - * {@linkplain #createDerivedInterval(Interval) derived intervals}. - */ - public int liveSetSize() { - return firstDerivedIntervalIndex == -1 ? operandSize() : firstDerivedIntervalIndex; - } - - int numLoops() { - return ir.getControlFlowGraph().getLoops().size(); - } - - Interval intervalFor(int operandNumber) { - return intervals[operandNumber]; - } - - public Interval intervalFor(Value operand) { - int operandNumber = operandNumber(operand); - assert operandNumber < intervalsSize; - return intervals[operandNumber]; - } - - public Interval getOrCreateInterval(AllocatableValue operand) { - Interval ret = intervalFor(operand); - if (ret == null) { - return createInterval(operand); - } else { - return ret; - } - } - - void initOpIdMaps(int numInstructions) { - opIdToInstructionMap = new LIRInstruction[numInstructions]; - opIdToBlockMap = new AbstractBlockBase<?>[numInstructions]; - } - - void putOpIdMaps(int index, LIRInstruction op, AbstractBlockBase<?> block) { - opIdToInstructionMap[index] = op; - opIdToBlockMap[index] = block; - } - - /** - * Gets the highest instruction id allocated by this object. - */ - int maxOpId() { - assert opIdToInstructionMap.length > 0 : "no operations"; - return (opIdToInstructionMap.length - 1) << 1; - } - - /** - * Converts an {@linkplain LIRInstruction#id instruction id} to an instruction index. All LIR - * instructions in a method have an index one greater than their linear-scan order predecessor - * with the first instruction having an index of 0. - */ - private static int opIdToIndex(int opId) { - return opId >> 1; - } - - /** - * Retrieves the {@link LIRInstruction} based on its {@linkplain LIRInstruction#id id}. - * - * @param opId an instruction {@linkplain LIRInstruction#id id} - * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id} - */ - public LIRInstruction instructionForId(int opId) { - assert isEven(opId) : "opId not even"; - LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)]; - assert instr.id() == opId; - return instr; - } - - /** - * Gets the block containing a given instruction. - * - * @param opId an instruction {@linkplain LIRInstruction#id id} - * @return the block containing the instruction denoted by {@code opId} - */ - public AbstractBlockBase<?> blockForId(int opId) { - assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range"; - return opIdToBlockMap[opIdToIndex(opId)]; - } - - boolean isBlockBegin(int opId) { - return opId == 0 || blockForId(opId) != blockForId(opId - 1); - } - - boolean coversBlockBegin(int opId1, int opId2) { - return blockForId(opId1) != blockForId(opId2); - } - - /** - * Determines if an {@link LIRInstruction} destroys all caller saved registers. - * - * @param opId an instruction {@linkplain LIRInstruction#id id} - * @return {@code true} if the instruction denoted by {@code id} destroys all caller saved - * registers. - */ - boolean hasCall(int opId) { - assert isEven(opId) : "opId not even"; - return instructionForId(opId).destroysCallerSavedRegisters(); - } - - abstract static class IntervalPredicate { - - abstract boolean apply(Interval i); - } - - public boolean isProcessed(Value operand) { - return !isRegister(operand) || attributes(asRegister(operand)).isAllocatable(); - } - - // * Phase 5: actual register allocation - - private static boolean isSorted(Interval[] intervals) { - int from = -1; - for (Interval interval : intervals) { - assert interval != null; - assert from <= interval.from(); - from = interval.from(); - } - return true; - } - - static Interval addToList(Interval first, Interval prev, Interval interval) { - Interval newFirst = first; - if (prev != null) { - prev.next = interval; - } else { - newFirst = interval; - } - return newFirst; - } - - Interval.Pair createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) { - assert isSorted(sortedIntervals) : "interval list is not sorted"; - - Interval list1 = Interval.EndMarker; - Interval list2 = Interval.EndMarker; - - Interval list1Prev = null; - Interval list2Prev = null; - Interval v; - - int n = sortedIntervals.length; - for (int i = 0; i < n; i++) { - v = sortedIntervals[i]; - if (v == null) { - continue; - } - - if (isList1.apply(v)) { - list1 = addToList(list1, list1Prev, v); - list1Prev = v; - } else if (isList2 == null || isList2.apply(v)) { - list2 = addToList(list2, list2Prev, v); - list2Prev = v; - } - } - - if (list1Prev != null) { - list1Prev.next = Interval.EndMarker; - } - if (list2Prev != null) { - list2Prev.next = Interval.EndMarker; - } - - assert list1Prev == null || list1Prev.next == Interval.EndMarker : "linear list ends not with sentinel"; - assert list2Prev == null || list2Prev.next == Interval.EndMarker : "linear list ends not with sentinel"; - - return new Interval.Pair(list1, list2); - } - - protected void sortIntervalsBeforeAllocation() { - int sortedLen = 0; - for (Interval interval : intervals) { - if (interval != null) { - sortedLen++; - } - } - - Interval[] sortedList = new Interval[sortedLen]; - int sortedIdx = 0; - int sortedFromMax = -1; - - // special sorting algorithm: the original interval-list is almost sorted, - // only some intervals are swapped. So this is much faster than a complete QuickSort - for (Interval interval : intervals) { - if (interval != null) { - int from = interval.from(); - - if (sortedFromMax <= from) { - sortedList[sortedIdx++] = interval; - sortedFromMax = interval.from(); - } else { - // the assumption that the intervals are already sorted failed, - // so this interval must be sorted in manually - int j; - for (j = sortedIdx - 1; j >= 0 && from < sortedList[j].from(); j--) { - sortedList[j + 1] = sortedList[j]; - } - sortedList[j + 1] = interval; - sortedIdx++; - } - } - } - sortedIntervals = sortedList; - } - - void sortIntervalsAfterAllocation() { - if (firstDerivedIntervalIndex == -1) { - // no intervals have been added during allocation, so sorted list is already up to date - return; - } - - Interval[] oldList = sortedIntervals; - Interval[] newList = Arrays.copyOfRange(intervals, firstDerivedIntervalIndex, intervalsSize); - int oldLen = oldList.length; - int newLen = newList.length; - - // conventional sort-algorithm for new intervals - Arrays.sort(newList, (Interval a, Interval b) -> a.from() - b.from()); - - // merge old and new list (both already sorted) into one combined list - Interval[] combinedList = new Interval[oldLen + newLen]; - int oldIdx = 0; - int newIdx = 0; - - while (oldIdx + newIdx < combinedList.length) { - if (newIdx >= newLen || (oldIdx < oldLen && oldList[oldIdx].from() <= newList[newIdx].from())) { - combinedList[oldIdx + newIdx] = oldList[oldIdx]; - oldIdx++; - } else { - combinedList[oldIdx + newIdx] = newList[newIdx]; - newIdx++; - } - } - - sortedIntervals = combinedList; - } - - // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode - // instead of returning null - public Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) { - Interval result = interval.getSplitChildAtOpId(opId, mode, this); - - if (result != null) { - if (Debug.isLogEnabled()) { - Debug.log("Split child at pos %d of interval %s is %s", opId, interval, result); - } - return result; - } - - throw new BailoutException("LinearScan: interval is null"); - } - - static StackSlotValue canonicalSpillOpr(Interval interval) { - assert interval.spillSlot() != null : "canonical spill slot not set"; - return interval.spillSlot(); - } - - boolean isMaterialized(AllocatableValue operand, int opId, OperandMode mode) { - Interval interval = intervalFor(operand); - assert interval != null : "interval must exist"; - - if (opId != -1) { - /* - * Operands are not changed when an interval is split during allocation, so search the - * right interval here. - */ - interval = splitChildAtOpId(interval, opId, mode); - } - - return isIllegal(interval.location()) && interval.canMaterialize(); - } - - boolean isCallerSave(Value operand) { - return attributes(asRegister(operand)).isCallerSave(); - } - - 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 (com.oracle.graal.lir.alloc.lsra.LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue()) { - createOptimizeSpillPositionPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); - } - createResolveDataFlowPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context); - - sortIntervalsAfterAllocation(); - - if (DetailedAsserts.getValue()) { - verify(); - } - beforeSpillMoveElimination(); - createSpillMoveEliminationPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context); - createAssignLocationsPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context); - - if (DetailedAsserts.getValue()) { - verifyIntervals(); - } - } catch (Throwable e) { - throw Debug.handle(e); - } - } - } - - protected void beforeSpillMoveElimination() { - } - - protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { - return new LinearScanLifetimeAnalysisPhase(this); - } - - protected LinearScanRegisterAllocationPhase createRegisterAllocationPhase() { - return new LinearScanRegisterAllocationPhase(this); - } - - protected LinearScanOptimizeSpillPositionPhase createOptimizeSpillPositionPhase() { - return new LinearScanOptimizeSpillPositionPhase(this); - } - - protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { - return new LinearScanResolveDataFlowPhase(this); - } - - protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { - return new LinearScanEliminateSpillMovePhase(this); - } - - protected LinearScanAssignLocationsPhase createAssignLocationsPhase() { - return new LinearScanAssignLocationsPhase(this); - } - - public void printIntervals(String label) { - if (Debug.isLogEnabled()) { - try (Indent indent = Debug.logAndIndent("intervals %s", label)) { - for (Interval interval : intervals) { - if (interval != null) { - Debug.log("%s", interval.logString(this)); - } - } - - try (Indent indent2 = Debug.logAndIndent("Basic Blocks")) { - for (int i = 0; i < blockCount(); i++) { - AbstractBlockBase<?> block = blockAt(i); - Debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop()); - } - } - } - } - Debug.dump(Arrays.copyOf(intervals, intervalsSize), label); - } - - public void printLir(String label, @SuppressWarnings("unused") boolean hirValid) { - Debug.dump(ir, label); - } - - boolean verify() { - // (check that all intervals have a correct register and that no registers are overwritten) - verifyIntervals(); - - verifyRegisters(); - - Debug.log("no errors found"); - - return true; - } - - private void verifyRegisters() { - // Enable this logging to get output for the verification process. - try (Indent indent = Debug.logAndIndent("verifying register allocation")) { - RegisterVerifier verifier = new RegisterVerifier(this); - verifier.verify(blockAt(0)); - } - } - - protected void verifyIntervals() { - try (Indent indent = Debug.logAndIndent("verifying intervals")) { - int len = intervalsSize; - - for (int i = 0; i < len; i++) { - Interval i1 = intervals[i]; - if (i1 == null) { - continue; - } - - i1.checkSplitChildren(); - - if (i1.operandNumber != i) { - Debug.log("Interval %d is on position %d in list", i1.operandNumber, i); - Debug.log(i1.logString(this)); - throw new JVMCIError(""); - } - - if (isVariable(i1.operand) && i1.kind().equals(LIRKind.Illegal)) { - Debug.log("Interval %d has no type assigned", i1.operandNumber); - Debug.log(i1.logString(this)); - throw new JVMCIError(""); - } - - if (i1.location() == null) { - Debug.log("Interval %d has no register assigned", i1.operandNumber); - Debug.log(i1.logString(this)); - throw new JVMCIError(""); - } - - if (i1.first() == Range.EndMarker) { - Debug.log("Interval %d has no Range", i1.operandNumber); - Debug.log(i1.logString(this)); - throw new JVMCIError(""); - } - - for (Range r = i1.first(); r != Range.EndMarker; r = r.next) { - if (r.from >= r.to) { - Debug.log("Interval %d has zero length range", i1.operandNumber); - Debug.log(i1.logString(this)); - throw new JVMCIError(""); - } - } - - for (int j = i + 1; j < len; j++) { - Interval i2 = intervals[j]; - if (i2 == null) { - continue; - } - - // special intervals that are created in MoveResolver - // . ignore them because the range information has no meaning there - if (i1.from() == 1 && i1.to() == 2) { - continue; - } - if (i2.from() == 1 && i2.to() == 2) { - continue; - } - Value l1 = i1.location(); - Value l2 = i2.location(); - if (i1.intersects(i2) && !isIllegal(l1) && (l1.equals(l2))) { - if (DetailedAsserts.getValue()) { - Debug.log("Intervals %d and %d overlap and have the same register assigned", i1.operandNumber, i2.operandNumber); - Debug.log(i1.logString(this)); - Debug.log(i2.logString(this)); - } - throw new BailoutException(""); - } - } - } - } - } - - class CheckConsumer implements ValueConsumer { - - boolean ok; - Interval curInterval; - - @Override - public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { - if (isRegister(operand)) { - if (intervalFor(operand) == curInterval) { - ok = true; - } - } - } - } - - void verifyNoOopsInFixedIntervals() { - try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) { - CheckConsumer checkConsumer = new CheckConsumer(); - - Interval fixedIntervals; - Interval otherIntervals; - fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).first; - // to ensure a walking until the last instruction id, add a dummy interval - // with a high operation id - otherIntervals = new Interval(Value.ILLEGAL, -1); - otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1); - IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals); - - for (AbstractBlockBase<?> block : sortedBlocks) { - List<LIRInstruction> instructions = ir.getLIRforBlock(block); - - for (int j = 0; j < instructions.size(); j++) { - LIRInstruction op = instructions.get(j); - - if (op.hasState()) { - iw.walkBefore(op.id()); - boolean checkLive = true; - - /* - * Make sure none of the fixed registers is live across an oopmap since we - * can't handle that correctly. - */ - if (checkLive) { - for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) { - if (interval.currentTo() > op.id() + 1) { - /* - * This interval is live out of this op so make sure that this - * interval represents some value that's referenced by this op - * either as an input or output. - */ - checkConsumer.curInterval = interval; - checkConsumer.ok = false; - - op.visitEachInput(checkConsumer); - op.visitEachAlive(checkConsumer); - op.visitEachTemp(checkConsumer); - op.visitEachOutput(checkConsumer); - - assert checkConsumer.ok : "fixed intervals should never be live across an oopmap point"; - } - } - } - } - } - } - } - } - - public LIR getLIR() { - return ir; - } - - public FrameMapBuilder getFrameMapBuilder() { - return frameMapBuilder; - } - - public List<? extends AbstractBlockBase<?>> sortedBlocks() { - return sortedBlocks; - } - - public Register[] getRegisters() { - return registers; - } - - public RegisterAllocationConfig getRegisterAllocationConfig() { - return regAllocConfig; - } - - public boolean callKillsRegisters() { - return regAllocConfig.getRegisterConfig().areAllAllocatableRegistersCallerSaved(); - } - -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanAssignLocationsPhase.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanAssignLocationsPhase.java Mon Aug 31 13:21:01 2015 +0200 @@ -48,9 +48,9 @@ */ public class LinearScanAssignLocationsPhase extends AllocationPhase { - protected final LinearScan allocator; + protected final TraceLinearScan allocator; - public LinearScanAssignLocationsPhase(LinearScan allocator) { + public LinearScanAssignLocationsPhase(TraceLinearScan allocator) { this.allocator = allocator; }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanEliminateSpillMovePhase.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanEliminateSpillMovePhase.java Mon Aug 31 13:21:01 2015 +0200 @@ -39,14 +39,14 @@ import com.oracle.graal.lir.StandardOp.MoveOp; import com.oracle.graal.lir.StandardOp.ValueMoveOp; import com.oracle.graal.lir.alloc.trace.Interval.SpillState; -import com.oracle.graal.lir.alloc.trace.LinearScan.IntervalPredicate; +import com.oracle.graal.lir.alloc.trace.TraceLinearScan.IntervalPredicate; import com.oracle.graal.lir.gen.*; import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*; public class LinearScanEliminateSpillMovePhase extends AllocationPhase { - private static final IntervalPredicate mustStoreAtDefinition = new LinearScan.IntervalPredicate() { + private static final IntervalPredicate mustStoreAtDefinition = new TraceLinearScan.IntervalPredicate() { @Override public boolean apply(Interval i) { @@ -54,9 +54,9 @@ } }; - protected final LinearScan allocator; + protected final TraceLinearScan allocator; - protected LinearScanEliminateSpillMovePhase(LinearScan allocator) { + protected LinearScanEliminateSpillMovePhase(TraceLinearScan allocator) { this.allocator = allocator; } @@ -146,7 +146,7 @@ } AllocatableValue fromLocation = interval.location(); - AllocatableValue toLocation = LinearScan.canonicalSpillOpr(interval); + AllocatableValue toLocation = TraceLinearScan.canonicalSpillOpr(interval); if (!fromLocation.equals(toLocation)) { assert isRegister(fromLocation) : "from operand must be a register but is: " + fromLocation + " toLocation=" + toLocation + " spillState=" +
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanLifetimeAnalysisPhase.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanLifetimeAnalysisPhase.java Mon Aug 31 13:21:01 2015 +0200 @@ -46,19 +46,19 @@ import com.oracle.graal.lir.StandardOp.ValueMoveOp; import com.oracle.graal.lir.alloc.trace.Interval.RegisterPriority; import com.oracle.graal.lir.alloc.trace.Interval.SpillState; -import com.oracle.graal.lir.alloc.trace.LinearScan.BlockData; +import com.oracle.graal.lir.alloc.trace.TraceLinearScan.BlockData; import com.oracle.graal.lir.gen.*; import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*; public class LinearScanLifetimeAnalysisPhase extends AllocationPhase { - protected final LinearScan allocator; + protected final TraceLinearScan allocator; /** * @param linearScan */ - protected LinearScanLifetimeAnalysisPhase(LinearScan linearScan) { + protected LinearScanLifetimeAnalysisPhase(TraceLinearScan linearScan) { allocator = linearScan; } @@ -168,7 +168,7 @@ } }; ValueConsumer stateConsumer = (operand, mode, flags) -> { - if (LinearScan.isVariableOrRegister(operand)) { + if (TraceLinearScan.isVariableOrRegister(operand)) { int operandNum = allocator.operandNumber(operand); if (!liveKill.get(operandNum)) { liveGen.set(operandNum); @@ -566,10 +566,10 @@ } 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)) { + if (flags.contains(OperandFlag.HINT) && TraceLinearScan.isVariableOrRegister(targetValue)) { op.forEachRegisterHint(targetValue, mode, (registerHint, valueMode, valueFlags) -> { - if (LinearScan.isVariableOrRegister(registerHint)) { + if (TraceLinearScan.isVariableOrRegister(registerHint)) { Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint); Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue); @@ -667,21 +667,21 @@ try (Indent indent = Debug.logAndIndent("build intervals")) { InstructionValueConsumer outputConsumer = (op, operand, mode, flags) -> { - if (LinearScan.isVariableOrRegister(operand)) { + if (TraceLinearScan.isVariableOrRegister(operand)) { addDef((AllocatableValue) operand, op, registerPriorityOfOutputOperand(op), operand.getLIRKind()); addRegisterHint(op, operand, mode, flags, true); } }; InstructionValueConsumer tempConsumer = (op, operand, mode, flags) -> { - if (LinearScan.isVariableOrRegister(operand)) { + if (TraceLinearScan.isVariableOrRegister(operand)) { addTemp((AllocatableValue) operand, op.id(), RegisterPriority.MustHaveRegister, operand.getLIRKind()); addRegisterHint(op, operand, mode, flags, false); } }; InstructionValueConsumer aliveConsumer = (op, operand, mode, flags) -> { - if (LinearScan.isVariableOrRegister(operand)) { + if (TraceLinearScan.isVariableOrRegister(operand)) { RegisterPriority p = registerPriorityOfInputOperand(flags); int opId = op.id(); int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId))); @@ -691,7 +691,7 @@ }; InstructionValueConsumer inputConsumer = (op, operand, mode, flags) -> { - if (LinearScan.isVariableOrRegister(operand)) { + if (TraceLinearScan.isVariableOrRegister(operand)) { int opId = op.id(); int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId))); RegisterPriority p = registerPriorityOfInputOperand(flags); @@ -701,7 +701,7 @@ }; InstructionValueConsumer stateProc = (op, operand, mode, flags) -> { - if (LinearScan.isVariableOrRegister(operand)) { + if (TraceLinearScan.isVariableOrRegister(operand)) { int opId = op.id(); int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId))); addUse((AllocatableValue) operand, blockFrom, opId + 1, RegisterPriority.None, operand.getLIRKind());
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanOptimizeSpillPositionPhase.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanOptimizeSpillPositionPhase.java Mon Aug 31 13:21:01 2015 +0200 @@ -45,9 +45,9 @@ private static final DebugMetric betterSpillPos = Debug.metric("BetterSpillPosition"); private static final DebugMetric betterSpillPosWithLowerProbability = Debug.metric("BetterSpillPositionWithLowerProbability"); - private final LinearScan allocator; + private final TraceLinearScan allocator; - LinearScanOptimizeSpillPositionPhase(LinearScan allocator) { + LinearScanOptimizeSpillPositionPhase(TraceLinearScan allocator) { this.allocator = allocator; } @@ -159,10 +159,10 @@ int spillOpId = allocator.getFirstLirInstructionId(spillBlock); // insert spill move AllocatableValue fromLocation = interval.getSplitChildAtOpId(spillOpId, OperandMode.DEF, allocator).location(); - AllocatableValue toLocation = LinearScan.canonicalSpillOpr(interval); + AllocatableValue toLocation = TraceLinearScan.canonicalSpillOpr(interval); LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation); Debug.log(3, "Insert spill move %s", move); - move.setId(LinearScan.DOMINATOR_SPILL_MOVE_ID); + move.setId(TraceLinearScan.DOMINATOR_SPILL_MOVE_ID); /* * We can use the insertion buffer directly because we always insert at position 1. */
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanRegisterAllocationPhase.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanRegisterAllocationPhase.java Mon Aug 31 13:21:01 2015 +0200 @@ -35,9 +35,9 @@ public final class LinearScanRegisterAllocationPhase extends AllocationPhase { - private final LinearScan allocator; + private final TraceLinearScan allocator; - LinearScanRegisterAllocationPhase(LinearScan allocator) { + LinearScanRegisterAllocationPhase(TraceLinearScan allocator) { this.allocator = allocator; } @@ -54,7 +54,7 @@ Interval precoloredIntervals; Interval notPrecoloredIntervals; - Interval.Pair result = allocator.createUnhandledLists(LinearScan.IS_PRECOLORED_INTERVAL, LinearScan.IS_VARIABLE_INTERVAL); + Interval.Pair result = allocator.createUnhandledLists(TraceLinearScan.IS_PRECOLORED_INTERVAL, TraceLinearScan.IS_VARIABLE_INTERVAL); precoloredIntervals = result.first; notPrecoloredIntervals = result.second;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanResolveDataFlowPhase.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanResolveDataFlowPhase.java Mon Aug 31 13:21:01 2015 +0200 @@ -43,9 +43,9 @@ */ public class LinearScanResolveDataFlowPhase extends AllocationPhase { - protected final LinearScan allocator; + protected final TraceLinearScan allocator; - protected LinearScanResolveDataFlowPhase(LinearScan allocator) { + protected LinearScanResolveDataFlowPhase(TraceLinearScan allocator) { this.allocator = allocator; }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanWalker.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanWalker.java Mon Aug 31 13:21:01 2015 +0200 @@ -80,7 +80,7 @@ return allocator.blockForId(opId); } - LinearScanWalker(LinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) { + LinearScanWalker(TraceLinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) { super(allocator, unhandledFixedFirst, unhandledAnyFirst); moveResolver = allocator.createMoveResolver();
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/MoveResolver.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/MoveResolver.java Mon Aug 31 13:21:01 2015 +0200 @@ -37,7 +37,7 @@ */ public class MoveResolver { - private final LinearScan allocator; + private final TraceLinearScan allocator; private int insertIdx; private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted @@ -84,11 +84,11 @@ return mappingFrom.size() > 0; } - protected LinearScan getAllocator() { + protected TraceLinearScan getAllocator() { return allocator; } - protected MoveResolver(LinearScan allocator) { + protected MoveResolver(TraceLinearScan allocator) { this.allocator = allocator; this.multipleReadsAllowed = false;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/OptimizingLinearScanWalker.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/OptimizingLinearScanWalker.java Mon Aug 31 13:21:01 2015 +0200 @@ -36,7 +36,7 @@ public class OptimizingLinearScanWalker extends LinearScanWalker { - OptimizingLinearScanWalker(LinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) { + OptimizingLinearScanWalker(TraceLinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) { super(allocator, unhandledFixedFirst, unhandledAnyFirst); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/RegisterVerifier.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/RegisterVerifier.java Mon Aug 31 13:21:01 2015 +0200 @@ -42,7 +42,7 @@ */ final class RegisterVerifier { - LinearScan allocator; + TraceLinearScan allocator; List<AbstractBlockBase<?>> workList; // all blocks that must be processed ArrayMap<Interval[]> savedStates; // saved information of previous check @@ -71,7 +71,7 @@ } } - RegisterVerifier(LinearScan allocator) { + RegisterVerifier(TraceLinearScan allocator) { this.allocator = allocator; workList = new ArrayList<>(16); this.savedStates = new ArrayMap<>(); @@ -208,7 +208,7 @@ @Override public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { // we skip spill moves inserted by the spill position optimization - if (LinearScan.isVariableOrRegister(operand) && allocator.isProcessed(operand) && op.id() != LinearScan.DOMINATOR_SPILL_MOVE_ID) { + if (TraceLinearScan.isVariableOrRegister(operand) && allocator.isProcessed(operand) && op.id() != TraceLinearScan.DOMINATOR_SPILL_MOVE_ID) { Interval interval = intervalAt(operand); if (op.id() != -1) { interval = interval.getSplitChildAtOpId(op.id(), mode, allocator); @@ -220,7 +220,7 @@ }; InstructionValueConsumer defConsumer = (op, operand, mode, flags) -> { - if (LinearScan.isVariableOrRegister(operand) && allocator.isProcessed(operand)) { + if (TraceLinearScan.isVariableOrRegister(operand) && allocator.isProcessed(operand)) { Interval interval = intervalAt(operand); if (op.id() != -1) { interval = interval.getSplitChildAtOpId(op.id(), mode, allocator);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/SSAMoveResolver.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/SSAMoveResolver.java Mon Aug 31 13:21:01 2015 +0200 @@ -39,7 +39,7 @@ private int[] stackBlocked; private final int firstVirtualStackIndex; - public SSAMoveResolver(LinearScan allocator) { + public SSAMoveResolver(TraceLinearScan allocator) { super(allocator); FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) allocator.getFrameMapBuilder(); FrameMap frameMap = frameMapBuilderTool.getFrameMap();
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/SSILinearScanEliminateSpillMovePhase.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/SSILinearScanEliminateSpillMovePhase.java Mon Aug 31 13:21:01 2015 +0200 @@ -27,7 +27,7 @@ public class SSILinearScanEliminateSpillMovePhase extends LinearScanEliminateSpillMovePhase { - public SSILinearScanEliminateSpillMovePhase(LinearScan allocator) { + public SSILinearScanEliminateSpillMovePhase(TraceLinearScan allocator) { super(allocator); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java Mon Aug 31 13:21:01 2015 +0200 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * 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 @@ -23,12 +23,16 @@ package com.oracle.graal.lir.alloc.trace; import static com.oracle.graal.compiler.common.GraalOptions.*; -import static com.oracle.graal.lir.alloc.trace.TraceLinearScan.Options.*; +import static com.oracle.graal.lir.LIRValueUtil.*; import static com.oracle.graal.lir.alloc.trace.TraceRegisterAllocationPhase.Options.*; +import static jdk.internal.jvmci.code.CodeUtil.*; +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 jdk.internal.jvmci.options.*; import jdk.internal.jvmci.options.OptionValue.OverrideScope; @@ -37,11 +41,22 @@ 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.LIRInstruction.OperandFlag; +import com.oracle.graal.lir.LIRInstruction.OperandMode; +import com.oracle.graal.lir.alloc.trace.Interval.RegisterBinding; +import com.oracle.graal.lir.framemap.*; 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 { +/** + * An implementation of the linear scan register allocator algorithm described in <a + * href="http://doi.acm.org/10.1145/1064979.1064998" + * >"Optimized Interval Splitting in a Linear Scan Register Allocator"</a> by Christian Wimmer and + * Hanspeter Moessenboeck. + */ +public class TraceLinearScan { public static class Options { // @formatter:off @@ -50,15 +65,559 @@ // @formatter:on } - private final TraceBuilderResult<?> traceBuilderResult; + public static class BlockData { + + /** + * Bit map specifying which operands are live upon entry to this block. These are values + * used in this block or any of its successors where such value are not defined in this + * block. The bit index of an operand is its {@linkplain TraceLinearScan#operandNumber(Value) + * operand number}. + */ + public BitSet liveIn; + + /** + * Bit map specifying which operands are live upon exit from this block. These are values + * used in a successor block that are either defined in this block or were live upon entry + * to this block. The bit index of an operand is its + * {@linkplain TraceLinearScan#operandNumber(Value) operand number}. + */ + public BitSet liveOut; + + /** + * Bit map specifying which operands are used (before being defined) in this block. That is, + * these are the values that are live upon entry to the block. The bit index of an operand + * is its {@linkplain TraceLinearScan#operandNumber(Value) operand number}. + */ + public BitSet liveGen; + + /** + * Bit map specifying which operands are defined/overwritten in this block. The bit index of + * an operand is its {@linkplain TraceLinearScan#operandNumber(Value) operand number}. + */ + public BitSet liveKill; + } + + public static final int DOMINATOR_SPILL_MOVE_ID = -2; + private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1; + + private final LIR ir; + private final FrameMapBuilder frameMapBuilder; + private final RegisterAttributes[] registerAttributes; + private final Register[] registers; + private final RegisterAllocationConfig regAllocConfig; + private final SpillMoveFactory moveFactory; + + private final BlockMap<BlockData> blockData; + + /** + * List of blocks in linear-scan order. This is only correct as long as the CFG does not change. + */ + private final List<? extends AbstractBlockBase<?>> sortedBlocks; - public TraceLinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, + /** @see #intervals() */ + private Interval[] intervals; + + /** + * The number of valid entries in {@link #intervals}. + */ + private int intervalsSize; + + /** + * The index of the first entry in {@link #intervals} for a + * {@linkplain #createDerivedInterval(Interval) derived interval}. + */ + private int firstDerivedIntervalIndex = -1; + + /** + * Intervals sorted by {@link Interval#from()}. + */ + private Interval[] sortedIntervals; + + /** + * Map from an instruction {@linkplain LIRInstruction#id id} to the instruction. Entries should + * be retrieved with {@link #instructionForId(int)} as the id is not simply an index into this + * array. + */ + private LIRInstruction[] opIdToInstructionMap; + + /** + * Map from an instruction {@linkplain LIRInstruction#id id} to the + * {@linkplain AbstractBlockBase block} containing the instruction. Entries should be retrieved + * with {@link #blockForId(int)} as the id is not simply an index into this array. + */ + private AbstractBlockBase<?>[] opIdToBlockMap; + + /** + * The {@linkplain #operandNumber(Value) number} of the first variable operand allocated. + */ + private final int firstVariableNumber; + protected final TraceBuilderResult<?> traceBuilderResult; + + protected TraceLinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, List<? extends AbstractBlockBase<?>> sortedBlocks, TraceBuilderResult<?> traceBuilderResult) { - super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks); + this.ir = res.getLIR(); + this.moveFactory = spillMoveFactory; + this.frameMapBuilder = res.getFrameMapBuilder(); + this.sortedBlocks = sortedBlocks; + this.registerAttributes = regAllocConfig.getRegisterConfig().getAttributesMap(); + this.regAllocConfig = regAllocConfig; + + this.registers = target.arch.getRegisters(); + this.firstVariableNumber = getRegisters().length; + this.blockData = new BlockMap<>(ir.getControlFlowGraph()); this.traceBuilderResult = traceBuilderResult; } - @Override + public int getFirstLirInstructionId(AbstractBlockBase<?> block) { + int result = ir.getLIRforBlock(block).get(0).id(); + assert result >= 0; + return result; + } + + public int getLastLirInstructionId(AbstractBlockBase<?> block) { + List<LIRInstruction> instructions = ir.getLIRforBlock(block); + int result = instructions.get(instructions.size() - 1).id(); + assert result >= 0; + return result; + } + + public SpillMoveFactory getSpillMoveFactory() { + return moveFactory; + } + + protected MoveResolver createMoveResolver() { + SSAMoveResolver moveResolver = new SSAMoveResolver(this); + assert moveResolver.checkEmpty(); + return moveResolver; + } + + public static boolean isVariableOrRegister(Value value) { + return isVariable(value) || isRegister(value); + } + + /** + * Converts an operand (variable or register) to an index in a flat address space covering all + * the {@linkplain Variable variables} and {@linkplain RegisterValue registers} being processed + * by this allocator. + */ + int operandNumber(Value operand) { + if (isRegister(operand)) { + int number = asRegister(operand).number; + assert number < firstVariableNumber; + return number; + } + assert isVariable(operand) : operand; + return firstVariableNumber + ((Variable) operand).index; + } + + /** + * Gets the number of operands. This value will increase by 1 for new variable. + */ + int operandSize() { + return firstVariableNumber + ir.numVariables(); + } + + /** + * Gets the highest operand number for a register operand. This value will never change. + */ + int maxRegisterNumber() { + return firstVariableNumber - 1; + } + + public BlockData getBlockData(AbstractBlockBase<?> block) { + return blockData.get(block); + } + + void initBlockData(AbstractBlockBase<?> block) { + blockData.put(block, new BlockData()); + } + + static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() { + + @Override + public boolean apply(Interval i) { + return isRegister(i.operand); + } + }; + + static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() { + + @Override + public boolean apply(Interval i) { + return isVariable(i.operand); + } + }; + + static final IntervalPredicate IS_STACK_INTERVAL = new IntervalPredicate() { + + @Override + public boolean apply(Interval i) { + return !isRegister(i.operand); + } + }; + + /** + * Gets an object describing the attributes of a given register according to this register + * configuration. + */ + public RegisterAttributes attributes(Register reg) { + return registerAttributes[reg.number]; + } + + void assignSpillSlot(Interval interval) { + /* + * Assign the canonical spill slot of the parent (if a part of the interval is already + * spilled) or allocate a new spill slot. + */ + if (interval.canMaterialize()) { + interval.assignLocation(Value.ILLEGAL); + } else if (interval.spillSlot() != null) { + interval.assignLocation(interval.spillSlot()); + } else { + VirtualStackSlot slot = frameMapBuilder.allocateSpillSlot(interval.kind()); + interval.setSpillSlot(slot); + interval.assignLocation(slot); + } + } + + /** + * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals. + */ + public Interval[] intervals() { + return intervals; + } + + void initIntervals() { + intervalsSize = operandSize(); + intervals = new Interval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)]; + } + + /** + * Creates a new interval. + * + * @param operand the operand for the interval + * @return the created interval + */ + Interval createInterval(AllocatableValue operand) { + assert isLegal(operand); + int operandNumber = operandNumber(operand); + Interval interval = new Interval(operand, operandNumber); + assert operandNumber < intervalsSize; + assert intervals[operandNumber] == null; + intervals[operandNumber] = interval; + return interval; + } + + /** + * Creates an interval as a result of splitting or spilling another interval. + * + * @param source an interval being split of spilled + * @return a new interval derived from {@code source} + */ + Interval createDerivedInterval(Interval source) { + if (firstDerivedIntervalIndex == -1) { + firstDerivedIntervalIndex = intervalsSize; + } + if (intervalsSize == intervals.length) { + intervals = Arrays.copyOf(intervals, intervals.length + (intervals.length >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)); + } + intervalsSize++; + Variable variable = new Variable(source.kind(), ir.nextVariable()); + + Interval interval = createInterval(variable); + assert intervals[intervalsSize - 1] == interval; + return interval; + } + + // access to block list (sorted in linear scan order) + public int blockCount() { + return sortedBlocks.size(); + } + + public AbstractBlockBase<?> blockAt(int index) { + return sortedBlocks.get(index); + } + + /** + * Gets the size of the {@link BlockData#liveIn} and {@link BlockData#liveOut} sets for a basic + * block. These sets do not include any operands allocated as a result of creating + * {@linkplain #createDerivedInterval(Interval) derived intervals}. + */ + public int liveSetSize() { + return firstDerivedIntervalIndex == -1 ? operandSize() : firstDerivedIntervalIndex; + } + + int numLoops() { + return ir.getControlFlowGraph().getLoops().size(); + } + + Interval intervalFor(int operandNumber) { + return intervals[operandNumber]; + } + + public Interval intervalFor(Value operand) { + int operandNumber = operandNumber(operand); + assert operandNumber < intervalsSize; + return intervals[operandNumber]; + } + + public Interval getOrCreateInterval(AllocatableValue operand) { + Interval ret = intervalFor(operand); + if (ret == null) { + return createInterval(operand); + } else { + return ret; + } + } + + void initOpIdMaps(int numInstructions) { + opIdToInstructionMap = new LIRInstruction[numInstructions]; + opIdToBlockMap = new AbstractBlockBase<?>[numInstructions]; + } + + void putOpIdMaps(int index, LIRInstruction op, AbstractBlockBase<?> block) { + opIdToInstructionMap[index] = op; + opIdToBlockMap[index] = block; + } + + /** + * Gets the highest instruction id allocated by this object. + */ + int maxOpId() { + assert opIdToInstructionMap.length > 0 : "no operations"; + return (opIdToInstructionMap.length - 1) << 1; + } + + /** + * Converts an {@linkplain LIRInstruction#id instruction id} to an instruction index. All LIR + * instructions in a method have an index one greater than their linear-scan order predecessor + * with the first instruction having an index of 0. + */ + private static int opIdToIndex(int opId) { + return opId >> 1; + } + + /** + * Retrieves the {@link LIRInstruction} based on its {@linkplain LIRInstruction#id id}. + * + * @param opId an instruction {@linkplain LIRInstruction#id id} + * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id} + */ + public LIRInstruction instructionForId(int opId) { + assert isEven(opId) : "opId not even"; + LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)]; + assert instr.id() == opId; + return instr; + } + + /** + * Gets the block containing a given instruction. + * + * @param opId an instruction {@linkplain LIRInstruction#id id} + * @return the block containing the instruction denoted by {@code opId} + */ + public AbstractBlockBase<?> blockForId(int opId) { + assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range"; + return opIdToBlockMap[opIdToIndex(opId)]; + } + + boolean isBlockBegin(int opId) { + return opId == 0 || blockForId(opId) != blockForId(opId - 1); + } + + boolean coversBlockBegin(int opId1, int opId2) { + return blockForId(opId1) != blockForId(opId2); + } + + /** + * Determines if an {@link LIRInstruction} destroys all caller saved registers. + * + * @param opId an instruction {@linkplain LIRInstruction#id id} + * @return {@code true} if the instruction denoted by {@code id} destroys all caller saved + * registers. + */ + boolean hasCall(int opId) { + assert isEven(opId) : "opId not even"; + return instructionForId(opId).destroysCallerSavedRegisters(); + } + + abstract static class IntervalPredicate { + + abstract boolean apply(Interval i); + } + + public boolean isProcessed(Value operand) { + return !isRegister(operand) || attributes(asRegister(operand)).isAllocatable(); + } + + // * Phase 5: actual register allocation + + private static boolean isSorted(Interval[] intervals) { + int from = -1; + for (Interval interval : intervals) { + assert interval != null; + assert from <= interval.from(); + from = interval.from(); + } + return true; + } + + static Interval addToList(Interval first, Interval prev, Interval interval) { + Interval newFirst = first; + if (prev != null) { + prev.next = interval; + } else { + newFirst = interval; + } + return newFirst; + } + + Interval.Pair createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) { + assert isSorted(sortedIntervals) : "interval list is not sorted"; + + Interval list1 = Interval.EndMarker; + Interval list2 = Interval.EndMarker; + + Interval list1Prev = null; + Interval list2Prev = null; + Interval v; + + int n = sortedIntervals.length; + for (int i = 0; i < n; i++) { + v = sortedIntervals[i]; + if (v == null) { + continue; + } + + if (isList1.apply(v)) { + list1 = addToList(list1, list1Prev, v); + list1Prev = v; + } else if (isList2 == null || isList2.apply(v)) { + list2 = addToList(list2, list2Prev, v); + list2Prev = v; + } + } + + if (list1Prev != null) { + list1Prev.next = Interval.EndMarker; + } + if (list2Prev != null) { + list2Prev.next = Interval.EndMarker; + } + + assert list1Prev == null || list1Prev.next == Interval.EndMarker : "linear list ends not with sentinel"; + assert list2Prev == null || list2Prev.next == Interval.EndMarker : "linear list ends not with sentinel"; + + return new Interval.Pair(list1, list2); + } + + protected void sortIntervalsBeforeAllocation() { + int sortedLen = 0; + for (Interval interval : intervals) { + if (interval != null) { + sortedLen++; + } + } + + Interval[] sortedList = new Interval[sortedLen]; + int sortedIdx = 0; + int sortedFromMax = -1; + + // special sorting algorithm: the original interval-list is almost sorted, + // only some intervals are swapped. So this is much faster than a complete QuickSort + for (Interval interval : intervals) { + if (interval != null) { + int from = interval.from(); + + if (sortedFromMax <= from) { + sortedList[sortedIdx++] = interval; + sortedFromMax = interval.from(); + } else { + // the assumption that the intervals are already sorted failed, + // so this interval must be sorted in manually + int j; + for (j = sortedIdx - 1; j >= 0 && from < sortedList[j].from(); j--) { + sortedList[j + 1] = sortedList[j]; + } + sortedList[j + 1] = interval; + sortedIdx++; + } + } + } + sortedIntervals = sortedList; + } + + void sortIntervalsAfterAllocation() { + if (firstDerivedIntervalIndex == -1) { + // no intervals have been added during allocation, so sorted list is already up to date + return; + } + + Interval[] oldList = sortedIntervals; + Interval[] newList = Arrays.copyOfRange(intervals, firstDerivedIntervalIndex, intervalsSize); + int oldLen = oldList.length; + int newLen = newList.length; + + // conventional sort-algorithm for new intervals + Arrays.sort(newList, (Interval a, Interval b) -> a.from() - b.from()); + + // merge old and new list (both already sorted) into one combined list + Interval[] combinedList = new Interval[oldLen + newLen]; + int oldIdx = 0; + int newIdx = 0; + + while (oldIdx + newIdx < combinedList.length) { + if (newIdx >= newLen || (oldIdx < oldLen && oldList[oldIdx].from() <= newList[newIdx].from())) { + combinedList[oldIdx + newIdx] = oldList[oldIdx]; + oldIdx++; + } else { + combinedList[oldIdx + newIdx] = newList[newIdx]; + newIdx++; + } + } + + sortedIntervals = combinedList; + } + + // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode + // instead of returning null + public Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) { + Interval result = interval.getSplitChildAtOpId(opId, mode, this); + + if (result != null) { + if (Debug.isLogEnabled()) { + Debug.log("Split child at pos %d of interval %s is %s", opId, interval, result); + } + return result; + } + + throw new BailoutException("LinearScan: interval is null"); + } + + static StackSlotValue canonicalSpillOpr(Interval interval) { + assert interval.spillSlot() != null : "canonical spill slot not set"; + return interval.spillSlot(); + } + + boolean isMaterialized(AllocatableValue operand, int opId, OperandMode mode) { + Interval interval = intervalFor(operand); + assert interval != null : "interval must exist"; + + if (opId != -1) { + /* + * Operands are not changed when an interval is split during allocation, so search the + * right interval here. + */ + interval = splitChildAtOpId(interval, opId, mode); + } + + return isIllegal(interval.location()) && interval.canMaterialize(); + } + + boolean isCallerSave(Value operand) { + return attributes(asRegister(operand)).isCallerSave(); + } + protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) { @@ -101,32 +660,21 @@ } } - @Override - protected MoveResolver createMoveResolver() { - SSAMoveResolver moveResolver = new SSAMoveResolver(this); - assert moveResolver.checkEmpty(); - return moveResolver; - } - - @Override protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { - if (TraceRAsimpleLifetimeAnalysis.getValue()) { + if (Options.TraceRAsimpleLifetimeAnalysis.getValue()) { return new TraceSimpleLifetimeAnalysisPhase(this, traceBuilderResult); } return new TraceLinearScanLifetimeAnalysisPhase(this, traceBuilderResult); } - @Override protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { return new TraceLinearScanResolveDataFlowPhase(this); } - @Override protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { return new SSILinearScanEliminateSpillMovePhase(this); } - @Override protected LinearScanAssignLocationsPhase createAssignLocationsPhase() { if (TraceRAshareSpillInformation.getValue()) { return new TraceLinearScanAssignLocationsPhase(this, traceBuilderResult); @@ -134,18 +682,227 @@ return new LinearScanAssignLocationsPhase(this); } - @Override + protected void beforeSpillMoveElimination() { + } + + protected LinearScanRegisterAllocationPhase createRegisterAllocationPhase() { + return new LinearScanRegisterAllocationPhase(this); + } + + protected LinearScanOptimizeSpillPositionPhase createOptimizeSpillPositionPhase() { + return new LinearScanOptimizeSpillPositionPhase(this); + } + public void printIntervals(String label) { if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) { - super.printIntervals(label); + if (Debug.isLogEnabled()) { + try (Indent indent = Debug.logAndIndent("intervals %s", label)) { + for (Interval interval : intervals) { + if (interval != null) { + Debug.log("%s", interval.logString(this)); + } + } + + try (Indent indent2 = Debug.logAndIndent("Basic Blocks")) { + for (int i = 0; i < blockCount(); i++) { + AbstractBlockBase<?> block = blockAt(i); + Debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop()); + } + } + } + } + Debug.dump(Arrays.copyOf(intervals, intervalsSize), label); } } - @Override - public void printLir(String label, boolean hirValid) { + public void printLir(String label, @SuppressWarnings("unused") boolean hirValid) { if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) { Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks(), label); } } + boolean verify() { + // (check that all intervals have a correct register and that no registers are overwritten) + verifyIntervals(); + + verifyRegisters(); + + Debug.log("no errors found"); + + return true; + } + + private void verifyRegisters() { + // Enable this logging to get output for the verification process. + try (Indent indent = Debug.logAndIndent("verifying register allocation")) { + RegisterVerifier verifier = new RegisterVerifier(this); + verifier.verify(blockAt(0)); + } + } + + protected void verifyIntervals() { + try (Indent indent = Debug.logAndIndent("verifying intervals")) { + int len = intervalsSize; + + for (int i = 0; i < len; i++) { + Interval i1 = intervals[i]; + if (i1 == null) { + continue; + } + + i1.checkSplitChildren(); + + if (i1.operandNumber != i) { + Debug.log("Interval %d is on position %d in list", i1.operandNumber, i); + Debug.log(i1.logString(this)); + throw new JVMCIError(""); + } + + if (isVariable(i1.operand) && i1.kind().equals(LIRKind.Illegal)) { + Debug.log("Interval %d has no type assigned", i1.operandNumber); + Debug.log(i1.logString(this)); + throw new JVMCIError(""); + } + + if (i1.location() == null) { + Debug.log("Interval %d has no register assigned", i1.operandNumber); + Debug.log(i1.logString(this)); + throw new JVMCIError(""); + } + + if (i1.first() == Range.EndMarker) { + Debug.log("Interval %d has no Range", i1.operandNumber); + Debug.log(i1.logString(this)); + throw new JVMCIError(""); + } + + for (Range r = i1.first(); r != Range.EndMarker; r = r.next) { + if (r.from >= r.to) { + Debug.log("Interval %d has zero length range", i1.operandNumber); + Debug.log(i1.logString(this)); + throw new JVMCIError(""); + } + } + + for (int j = i + 1; j < len; j++) { + Interval i2 = intervals[j]; + if (i2 == null) { + continue; + } + + // special intervals that are created in MoveResolver + // . ignore them because the range information has no meaning there + if (i1.from() == 1 && i1.to() == 2) { + continue; + } + if (i2.from() == 1 && i2.to() == 2) { + continue; + } + Value l1 = i1.location(); + Value l2 = i2.location(); + if (i1.intersects(i2) && !isIllegal(l1) && (l1.equals(l2))) { + if (DetailedAsserts.getValue()) { + Debug.log("Intervals %d and %d overlap and have the same register assigned", i1.operandNumber, i2.operandNumber); + Debug.log(i1.logString(this)); + Debug.log(i2.logString(this)); + } + throw new BailoutException(""); + } + } + } + } + } + + class CheckConsumer implements ValueConsumer { + + boolean ok; + Interval curInterval; + + @Override + public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { + if (isRegister(operand)) { + if (intervalFor(operand) == curInterval) { + ok = true; + } + } + } + } + + void verifyNoOopsInFixedIntervals() { + try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) { + CheckConsumer checkConsumer = new CheckConsumer(); + + Interval fixedIntervals; + Interval otherIntervals; + fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).first; + // to ensure a walking until the last instruction id, add a dummy interval + // with a high operation id + otherIntervals = new Interval(Value.ILLEGAL, -1); + otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1); + IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals); + + for (AbstractBlockBase<?> block : sortedBlocks) { + List<LIRInstruction> instructions = ir.getLIRforBlock(block); + + for (int j = 0; j < instructions.size(); j++) { + LIRInstruction op = instructions.get(j); + + if (op.hasState()) { + iw.walkBefore(op.id()); + boolean checkLive = true; + + /* + * Make sure none of the fixed registers is live across an oopmap since we + * can't handle that correctly. + */ + if (checkLive) { + for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) { + if (interval.currentTo() > op.id() + 1) { + /* + * This interval is live out of this op so make sure that this + * interval represents some value that's referenced by this op + * either as an input or output. + */ + checkConsumer.curInterval = interval; + checkConsumer.ok = false; + + op.visitEachInput(checkConsumer); + op.visitEachAlive(checkConsumer); + op.visitEachTemp(checkConsumer); + op.visitEachOutput(checkConsumer); + + assert checkConsumer.ok : "fixed intervals should never be live across an oopmap point"; + } + } + } + } + } + } + } + } + + public LIR getLIR() { + return ir; + } + + public FrameMapBuilder getFrameMapBuilder() { + return frameMapBuilder; + } + + public List<? extends AbstractBlockBase<?>> sortedBlocks() { + return sortedBlocks; + } + + public Register[] getRegisters() { + return registers; + } + + public RegisterAllocationConfig getRegisterAllocationConfig() { + return regAllocConfig; + } + + public boolean callKillsRegisters() { + return regAllocConfig.getRegisterConfig().areAllAllocatableRegistersCallerSaved(); + } + }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanAssignLocationsPhase.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanAssignLocationsPhase.java Mon Aug 31 13:21:01 2015 +0200 @@ -46,7 +46,7 @@ private final TraceBuilderResult<?> traceBuilderResult; - TraceLinearScanAssignLocationsPhase(LinearScan allocator, TraceBuilderResult<?> traceBuilderResult) { + TraceLinearScanAssignLocationsPhase(TraceLinearScan allocator, TraceBuilderResult<?> traceBuilderResult) { super(allocator); this.traceBuilderResult = traceBuilderResult; }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java Mon Aug 31 13:21:01 2015 +0200 @@ -42,14 +42,14 @@ import com.oracle.graal.lir.StandardOp.MoveOp; import com.oracle.graal.lir.alloc.trace.Interval.RegisterPriority; import com.oracle.graal.lir.alloc.trace.Interval.SpillState; -import com.oracle.graal.lir.alloc.trace.LinearScan.BlockData; +import com.oracle.graal.lir.alloc.trace.TraceLinearScan.BlockData; import com.oracle.graal.lir.ssi.*; public class TraceLinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase { private final TraceBuilderResult<?> traceBuilderResult; - public TraceLinearScanLifetimeAnalysisPhase(LinearScan linearScan, TraceBuilderResult<?> traceBuilderResult) { + public TraceLinearScanLifetimeAnalysisPhase(TraceLinearScan linearScan, TraceBuilderResult<?> traceBuilderResult) { super(linearScan); this.traceBuilderResult = traceBuilderResult; }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java Mon Aug 31 13:21:01 2015 +0200 @@ -40,7 +40,7 @@ private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]"); private static final DebugMetric numStackToStackMoves = Debug.metric("SSI LSRA[numStackToStackMoves]"); - public TraceLinearScanResolveDataFlowPhase(LinearScan allocator) { + public TraceLinearScanResolveDataFlowPhase(TraceLinearScan allocator) { super(allocator); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceSimpleLifetimeAnalysisPhase.java Mon Aug 31 13:11:26 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceSimpleLifetimeAnalysisPhase.java Mon Aug 31 13:21:01 2015 +0200 @@ -41,7 +41,7 @@ public class TraceSimpleLifetimeAnalysisPhase extends TraceLinearScanLifetimeAnalysisPhase { - public TraceSimpleLifetimeAnalysisPhase(LinearScan allocator, TraceBuilderResult<?> traceBuilderResult) { + public TraceSimpleLifetimeAnalysisPhase(TraceLinearScan allocator, TraceBuilderResult<?> traceBuilderResult) { super(allocator, traceBuilderResult); } @@ -165,21 +165,21 @@ try (Indent indent = Debug.logAndIndent("build intervals")) { InstructionValueConsumer outputConsumer = (op, operand, mode, flags) -> { - if (LinearScan.isVariableOrRegister(operand)) { + if (TraceLinearScan.isVariableOrRegister(operand)) { addDef((AllocatableValue) operand, op, registerPriorityOfOutputOperand(op), operand.getLIRKind()); addRegisterHint(op, operand, mode, flags, true); } }; InstructionValueConsumer tempConsumer = (op, operand, mode, flags) -> { - if (LinearScan.isVariableOrRegister(operand)) { + if (TraceLinearScan.isVariableOrRegister(operand)) { addTemp((AllocatableValue) operand, op.id(), RegisterPriority.MustHaveRegister, operand.getLIRKind()); addRegisterHint(op, operand, mode, flags, false); } }; InstructionValueConsumer aliveConsumer = (op, operand, mode, flags) -> { - if (LinearScan.isVariableOrRegister(operand)) { + if (TraceLinearScan.isVariableOrRegister(operand)) { RegisterPriority p = registerPriorityOfInputOperand(flags); int opId = op.id(); int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId))); @@ -189,7 +189,7 @@ }; InstructionValueConsumer inputConsumer = (op, operand, mode, flags) -> { - if (LinearScan.isVariableOrRegister(operand)) { + if (TraceLinearScan.isVariableOrRegister(operand)) { int opId = op.id(); RegisterPriority p = registerPriorityOfInputOperand(flags); int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId))); @@ -199,7 +199,7 @@ }; InstructionValueConsumer stateProc = (op, operand, mode, flags) -> { - if (LinearScan.isVariableOrRegister(operand)) { + if (TraceLinearScan.isVariableOrRegister(operand)) { int opId = op.id(); int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId))); addUse((AllocatableValue) operand, blockFrom, opId + 1, RegisterPriority.None, operand.getLIRKind());