Mercurial > hg > graal-compiler
diff graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScan.java @ 2509:16b9a8b5ad39
Renamings Runtime=>GraalRuntime and Compiler=>GraalCompiler
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 27 Apr 2011 11:50:44 +0200 |
parents | graal/Compiler/src/com/sun/c1x/alloc/LinearScan.java@9ec15d6914ca |
children | 4fdef1464592 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScan.java Wed Apr 27 11:50:44 2011 +0200 @@ -0,0 +1,2559 @@ +/* + * Copyright (c) 2009, 2011, 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.sun.c1x.alloc; + +import static com.sun.cri.ci.CiUtil.*; +import static java.lang.reflect.Modifier.*; + +import java.util.*; + +import com.sun.c1x.*; +import com.sun.c1x.alloc.Interval.*; +import com.sun.c1x.debug.*; +import com.sun.c1x.gen.*; +import com.sun.c1x.graph.*; +import com.sun.c1x.ir.*; +import com.sun.c1x.ir.BlockBegin.BlockFlag; +import com.sun.c1x.lir.*; +import com.sun.c1x.lir.LIRInstruction.OperandMode; +import com.sun.c1x.observer.*; +import com.sun.c1x.util.*; +import com.sun.c1x.value.*; +import com.sun.c1x.value.FrameState.PhiProcedure; +import com.sun.c1x.value.FrameState.ValueProcedure; +import com.sun.cri.ci.*; +import com.sun.cri.ri.*; + +/** + * 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. + * + * @author Christian Wimmer (original HotSpot implementation) + * @author Thomas Wuerthinger + * @author Doug Simon + */ +public final class LinearScan { + + final C1XCompilation compilation; + final IR ir; + final LIRGenerator gen; + final FrameMap frameMap; + final RiRegisterAttributes[] registerAttributes; + final CiRegister[] registers; + + private static final int INITIAL_SPLIT_INTERVALS_CAPACITY = 32; + + /** + * List of blocks in linear-scan order. This is only correct as long as the CFG does not change. + */ + final BlockBegin[] sortedBlocks; + + final OperandPool operands; + + /** + * Number of stack slots used for intervals allocated to memory. + */ + int maxSpills; + + /** + * Unused spill slot for a single-word value because of alignment of a double-word value. + */ + CiStackSlot unusedSpillSlot; + + /** + * Map from {@linkplain #operandNumber(CiValue) operand numbers} to intervals. + */ + Interval[] intervals; + + /** + * The number of valid entries in {@link #intervals}. + */ + int intervalsSize; + + /** + * The index of the first entry in {@link #intervals} for a {@linkplain #createDerivedInterval(Interval) derived interval}. + */ + int firstDerivedIntervalIndex = -1; + + /** + * Intervals sorted by {@link Interval#from()}. + */ + 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. + */ + LIRInstruction[] opIdToInstructionMap; + + /** + * Map from an instruction {@linkplain LIRInstruction#id id} to the {@linkplain + * BlockBegin block} containing the instruction. Entries should be retrieved with + * {@link #blockForId(int)} as the id is not simply an index into this array. + */ + BlockBegin[] opIdToBlockMap; + + /** + * Bit set for each variable that is contained in each loop. + */ + BitMap2D intervalInLoop; + + public LinearScan(C1XCompilation compilation, IR ir, LIRGenerator gen, FrameMap frameMap) { + this.compilation = compilation; + this.ir = ir; + this.gen = gen; + this.frameMap = frameMap; + this.maxSpills = frameMap.initialSpillSlot(); + this.unusedSpillSlot = null; + this.sortedBlocks = ir.linearScanOrder().toArray(new BlockBegin[ir.linearScanOrder().size()]); + CiRegister[] allocatableRegisters = compilation.registerConfig.getAllocatableRegisters(); + this.registers = new CiRegister[CiRegister.maxRegisterNumber(allocatableRegisters) + 1]; + for (CiRegister reg : allocatableRegisters) { + registers[reg.number] = reg; + } + this.registerAttributes = compilation.registerConfig.getAttributesMap(); + this.operands = gen.operands; + } + + /** + * Converts an operand (variable or register) to an index in a flat address space covering all the + * {@linkplain CiVariable variables} and {@linkplain CiRegisterValue registers} being processed by this + * allocator. + */ + int operandNumber(CiValue operand) { + return operands.operandNumber(operand); + } + + static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() { + @Override + public boolean apply(Interval i) { + return i.operand.isRegister(); + } + }; + + static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() { + @Override + public boolean apply(Interval i) { + return i.operand.isVariable(); + } + }; + + static final IntervalPredicate IS_OOP_INTERVAL = new IntervalPredicate() { + @Override + public boolean apply(Interval i) { + return !i.operand.isRegister() && i.kind() == CiKind.Object; + } + }; + + /** + * Gets an object describing the attributes of a given register according to this register configuration. + */ + RiRegisterAttributes attributes(CiRegister reg) { + return registerAttributes[reg.number]; + } + + /** + * Allocates the next available spill slot for a value of a given kind. + */ + CiStackSlot allocateSpillSlot(CiKind kind) { + CiStackSlot spillSlot; + if (numberOfSpillSlots(kind) == 2) { + if (isOdd(maxSpills)) { + // alignment of double-slot values + // the hole because of the alignment is filled with the next single-slot value + assert unusedSpillSlot == null : "wasting a spill slot"; + unusedSpillSlot = CiStackSlot.get(kind, maxSpills); + maxSpills++; + } + spillSlot = CiStackSlot.get(kind, maxSpills); + maxSpills += 2; + } else if (unusedSpillSlot != null) { + // re-use hole that was the result of a previous double-word alignment + spillSlot = unusedSpillSlot; + unusedSpillSlot = null; + } else { + spillSlot = CiStackSlot.get(kind, maxSpills); + maxSpills++; + } + + return spillSlot; + } + + 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.spillSlot() != null) { + interval.assignLocation(interval.spillSlot()); + } else { + CiStackSlot slot = allocateSpillSlot(interval.kind()); + interval.setSpillSlot(slot); + interval.assignLocation(slot); + } + } + + /** + * Creates a new interval. + * + * @param operand the operand for the interval + * @return the created interval + */ + Interval createInterval(CiValue operand) { + assert isProcessed(operand); + assert operand.isLegal(); + 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 * 2); + } + intervalsSize++; + Interval interval = createInterval(operands.newVariable(source.kind())); + assert intervals[intervalsSize - 1] == interval; + return interval; + } + + // copy the variable flags if an interval is split + void copyRegisterFlags(Interval from, Interval to) { + if (operands.mustBeByteRegister(from.operand)) { + operands.setMustBeByteRegister((CiVariable) to.operand); + } + + // Note: do not copy the mustStartInMemory flag because it is not necessary for child + // intervals (only the very beginning of the interval must be in memory) + } + + // access to block list (sorted in linear scan order) + int blockCount() { + assert sortedBlocks.length == ir.linearScanOrder().size() : "invalid cached block list"; + return sortedBlocks.length; + } + + BlockBegin blockAt(int index) { + assert sortedBlocks[index] == ir.linearScanOrder().get(index) : "invalid cached block list"; + return sortedBlocks[index]; + } + + /** + * Gets the size of the {@link LIRBlock#liveIn} and {@link LIRBlock#liveOut} sets for a basic block. These sets do + * not include any operands allocated as a result of creating {@linkplain #createDerivedInterval(Interval) derived + * intervals}. + */ + int liveSetSize() { + return firstDerivedIntervalIndex == -1 ? operands.size() : firstDerivedIntervalIndex; + } + + int numLoops() { + return ir.numLoops(); + } + + boolean isIntervalInLoop(int interval, int loop) { + return intervalInLoop.at(interval, loop); + } + + Interval intervalFor(CiValue operand) { + int operandNumber = operandNumber(operand); + assert operandNumber < intervalsSize; + return intervals[operandNumber]; + } + + /** + * 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 predecesor + * with the first instruction having an index of 0. + */ + 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} + */ + 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} + */ + BlockBegin 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).hasCall; + } + + /** + * Eliminates moves from register to stack if the stack slot is known to be correct. + */ + void changeSpillDefinitionPos(Interval interval, int defPos) { + assert interval.isSplitParent() : "can only be called for split parents"; + + switch (interval.spillState()) { + case NoDefinitionFound: + assert interval.spillDefinitionPos() == -1 : "must no be set before"; + interval.setSpillDefinitionPos(defPos); + interval.setSpillState(SpillState.NoSpillStore); + break; + + case NoSpillStore: + assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created"; + if (defPos < interval.spillDefinitionPos() - 2 || instructionForId(interval.spillDefinitionPos()).code == LIROpcode.Xir) { + // second definition found, so no spill optimization possible for this interval + interval.setSpillState(SpillState.NoOptimization); + } else { + // two consecutive definitions (because of two-operand LIR form) + assert blockForId(defPos) == blockForId(interval.spillDefinitionPos()) : "block must be equal"; + } + break; + + case NoOptimization: + // nothing to do + break; + + default: + throw new CiBailout("other states not allowed at this time"); + } + } + + // called during register allocation + void changeSpillState(Interval interval, int spillPos) { + switch (interval.spillState()) { + case NoSpillStore: { + int defLoopDepth = blockForId(interval.spillDefinitionPos()).loopDepth(); + int spillLoopDepth = blockForId(spillPos).loopDepth(); + + if (defLoopDepth < spillLoopDepth) { + // the loop depth of the spilling position is higher then the loop depth + // at the definition of the interval . move write to memory out of loop + // by storing at definitin of the interval + interval.setSpillState(SpillState.StoreAtDefinition); + } else { + // the interval is currently spilled only once, so for now there is no + // reason to store the interval at the definition + interval.setSpillState(SpillState.OneSpillStore); + } + break; + } + + case OneSpillStore: { + // the interval is spilled more then once, so it is better to store it to + // memory at the definition + interval.setSpillState(SpillState.StoreAtDefinition); + break; + } + + case StoreAtDefinition: + case StartInMemory: + case NoOptimization: + case NoDefinitionFound: + // nothing to do + break; + + default: + throw new CiBailout("other states not allowed at this time"); + } + } + + abstract static class IntervalPredicate { + abstract boolean apply(Interval i); + } + + private static final IntervalPredicate mustStoreAtDefinition = new IntervalPredicate() { + @Override + public boolean apply(Interval i) { + return i.isSplitParent() && i.spillState() == SpillState.StoreAtDefinition; + } + }; + + // called once before assignment of register numbers + void eliminateSpillMoves() { + if (C1XOptions.TraceLinearScanLevel >= 3) { + TTY.println(" Eliminating unnecessary spill moves"); + } + + // collect all intervals that must be stored after their definition. + // the list is sorted by Interval.spillDefinitionPos + Interval interval; + interval = createUnhandledLists(mustStoreAtDefinition, null).first; + if (C1XOptions.DetailedAsserts) { + checkIntervals(interval); + } + + LIRInsertionBuffer insertionBuffer = new LIRInsertionBuffer(); + int numBlocks = blockCount(); + for (int i = 0; i < numBlocks; i++) { + BlockBegin block = blockAt(i); + List<LIRInstruction> instructions = block.lir().instructionsList(); + int numInst = instructions.size(); + boolean hasNew = false; + + // iterate all instructions of the block. skip the first because it is always a label + for (int j = 1; j < numInst; j++) { + LIRInstruction op = instructions.get(j); + int opId = op.id; + + if (opId == -1) { + CiValue resultOperand = op.result(); + // remove move from register to stack if the stack slot is guaranteed to be correct. + // only moves that have been inserted by LinearScan can be removed. + assert op.code == LIROpcode.Move : "only moves can have a opId of -1"; + assert resultOperand.isVariable() : "LinearScan inserts only moves to variables"; + + LIROp1 op1 = (LIROp1) op; + Interval curInterval = intervalFor(resultOperand); + + if (!curInterval.location().isRegister() && curInterval.alwaysInMemory()) { + // move target is a stack slot that is always correct, so eliminate instruction + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("eliminating move from interval %d to %d", operandNumber(op1.operand()), operandNumber(op1.result())); + } + instructions.set(j, null); // null-instructions are deleted by assignRegNum + } + + } else { + // insert move from register to stack just after the beginning of the interval + assert interval == Interval.EndMarker || interval.spillDefinitionPos() >= opId : "invalid order"; + assert interval == Interval.EndMarker || (interval.isSplitParent() && interval.spillState() == SpillState.StoreAtDefinition) : "invalid interval"; + + while (interval != Interval.EndMarker && interval.spillDefinitionPos() == opId) { + if (!hasNew) { + // prepare insertion buffer (appended when all instructions of the block are processed) + insertionBuffer.init(block.lir()); + hasNew = true; + } + + CiValue fromLocation = interval.location(); + CiValue toLocation = canonicalSpillOpr(interval); + + assert fromLocation.isRegister() : "from operand must be a register but is: " + fromLocation + " toLocation=" + toLocation + " spillState=" + interval.spillState(); + assert toLocation.isStackSlot() : "to operand must be a stack slot"; + + insertionBuffer.move(j, fromLocation, toLocation, null); + + if (C1XOptions.TraceLinearScanLevel >= 4) { + CiStackSlot slot = interval.spillSlot(); + TTY.println("inserting move after definition of interval %d to stack slot %d%s at opId %d", + interval.operandNumber, slot.index(), slot.inCallerFrame() ? " in caller frame" : "", opId); + } + + interval = interval.next; + } + } + } // end of instruction iteration + + if (hasNew) { + block.lir().append(insertionBuffer); + } + } // end of block iteration + + assert interval == Interval.EndMarker : "missed an interval"; + } + + private void checkIntervals(Interval interval) { + Interval prev = null; + Interval temp = interval; + while (temp != Interval.EndMarker) { + assert temp.spillDefinitionPos() > 0 : "invalid spill definition pos"; + if (prev != null) { + assert temp.from() >= prev.from() : "intervals not sorted"; + assert temp.spillDefinitionPos() >= prev.spillDefinitionPos() : "when intervals are sorted by from : then they must also be sorted by spillDefinitionPos"; + } + + assert temp.spillSlot() != null : "interval has no spill slot assigned"; + assert temp.spillDefinitionPos() >= temp.from() : "invalid order"; + assert temp.spillDefinitionPos() <= temp.from() + 2 : "only intervals defined once at their start-pos can be optimized"; + + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("interval %d (from %d to %d) must be stored at %d", temp.operandNumber, temp.from(), temp.to(), temp.spillDefinitionPos()); + } + + prev = temp; + temp = temp.next; + } + } + + /** + * Numbers all instructions in all blocks. The numbering follows the {@linkplain ComputeLinearScanOrder linear scan order}. + */ + void numberInstructions() { + // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node. + int numBlocks = blockCount(); + int numInstructions = 0; + for (int i = 0; i < numBlocks; i++) { + numInstructions += blockAt(i).lir().instructionsList().size(); + } + + // initialize with correct length + opIdToInstructionMap = new LIRInstruction[numInstructions]; + opIdToBlockMap = new BlockBegin[numInstructions]; + + int opId = 0; + int index = 0; + + for (int i = 0; i < numBlocks; i++) { + BlockBegin block = blockAt(i); + block.setFirstLirInstructionId(opId); + List<LIRInstruction> instructions = block.lir().instructionsList(); + + int numInst = instructions.size(); + for (int j = 0; j < numInst; j++) { + LIRInstruction op = instructions.get(j); + op.id = opId; + + opIdToInstructionMap[index] = op; + opIdToBlockMap[index] = block; + assert instructionForId(opId) == op : "must match"; + + index++; + opId += 2; // numbering of lirOps by two + } + block.setLastLirInstructionId(opId - 2); + } + assert index == numInstructions : "must match"; + assert (index << 1) == opId : "must match: " + (index << 1); + } + + /** + * Computes local live sets (i.e. {@link LIRBlock#liveGen} and {@link LIRBlock#liveKill}) separately for each block. + */ + void computeLocalLiveSets() { + int numBlocks = blockCount(); + int liveSize = liveSetSize(); + + BitMap2D localIntervalInLoop = new BitMap2D(operands.size(), numLoops()); + + // iterate all blocks + for (int i = 0; i < numBlocks; i++) { + BlockBegin block = blockAt(i); + final CiBitMap liveGen = new CiBitMap(liveSize); + final CiBitMap liveKill = new CiBitMap(liveSize); + + if (block.isExceptionEntry()) { + // Phi functions at the begin of an exception handler are + // implicitly defined (= killed) at the beginning of the block. + block.stateBefore().forEachLivePhi(block, new PhiProcedure() { + public boolean doPhi(Phi phi) { + liveKill.set(operandNumber(phi.operand())); + return true; + } + }); + } + + List<LIRInstruction> instructions = block.lir().instructionsList(); + int numInst = instructions.size(); + + // iterate all instructions of the block. skip the first because it is always a label + assert !instructions.get(0).hasOperands() : "first operation must always be a label"; + for (int j = 1; j < numInst; j++) { + final LIRInstruction op = instructions.get(j); + + // iterate input operands of instruction + int n = op.operandCount(LIRInstruction.OperandMode.Input); + for (int k = 0; k < n; k++) { + CiValue operand = op.operandAt(LIRInstruction.OperandMode.Input, k); + + if (operand.isVariable()) { + int operandNum = operandNumber(operand); + if (!liveKill.get(operandNum)) { + liveGen.set(operandNum); + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println(" Setting liveGen for operand %d at instruction %d", operandNum, op.id); + } + } + if (block.loopIndex() >= 0) { + localIntervalInLoop.setBit(operandNum, block.loopIndex()); + } + } + + if (C1XOptions.DetailedAsserts) { + assert operand.isVariableOrRegister() : "visitor should only return register operands"; + verifyInput(block, liveKill, operand); + } + } + + // Add uses of live locals from interpreter's point of view for proper debug information generation + LIRDebugInfo info = op.info; + if (info != null) { + info.state.forEachLiveStateValue(new ValueProcedure() { + public void doValue(Value value) { + CiValue operand = value.operand(); + if (operand.isVariable()) { + int operandNum = operandNumber(operand); + if (!liveKill.get(operandNum)) { + liveGen.set(operandNum); + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println(" Setting liveGen for value %s, LIR opId %d, operand %d", Util.valueString(value), op.id, operandNum); + } + } + } else if (operand.isRegister()) { + assert !isProcessed(operand) && !operand.kind.isObject(); + } else { + assert operand.isConstant() || operand.isIllegal() : "invalid operand for deoptimization value: " + value; + } + } + }); + } + + // iterate temp operands of instruction + n = op.operandCount(LIRInstruction.OperandMode.Temp); + for (int k = 0; k < n; k++) { + CiValue operand = op.operandAt(LIRInstruction.OperandMode.Temp, k); + + if (operand.isVariable()) { + int varNum = operandNumber(operand); + liveKill.set(varNum); + if (block.loopIndex() >= 0) { + localIntervalInLoop.setBit(varNum, block.loopIndex()); + } + } + + if (C1XOptions.DetailedAsserts) { + assert operand.isVariableOrRegister() : "visitor should only return register operands"; + verifyTemp(liveKill, operand); + } + } + + // iterate output operands of instruction + n = op.operandCount(LIRInstruction.OperandMode.Output); + for (int k = 0; k < n; k++) { + CiValue operand = op.operandAt(LIRInstruction.OperandMode.Output, k); + + if (operand.isVariable()) { + int varNum = operandNumber(operand); + liveKill.set(varNum); + if (block.loopIndex() >= 0) { + localIntervalInLoop.setBit(varNum, block.loopIndex()); + } + } + + if (C1XOptions.DetailedAsserts) { + assert operand.isVariableOrRegister() : "visitor should only return register operands"; + // fixed intervals are never live at block boundaries, so + // they need not be processed in live sets + // process them only in debug mode so that this can be checked + verifyTemp(liveKill, operand); + } + } + } // end of instruction iteration + + LIRBlock lirBlock = block.lirBlock(); + lirBlock.liveGen = liveGen; + lirBlock.liveKill = liveKill; + lirBlock.liveIn = new CiBitMap(liveSize); + lirBlock.liveOut = new CiBitMap(liveSize); + + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("liveGen B%d %s", block.blockID, block.lirBlock.liveGen); + TTY.println("liveKill B%d %s", block.blockID, block.lirBlock.liveKill); + } + } // end of block iteration + + intervalInLoop = localIntervalInLoop; + } + + private void verifyTemp(CiBitMap liveKill, CiValue operand) { + // fixed intervals are never live at block boundaries, so + // they need not be processed in live sets + // process them only in debug mode so that this can be checked + if (!operand.isVariable()) { + if (isProcessed(operand)) { + liveKill.set(operandNumber(operand)); + } + } + } + + private void verifyInput(BlockBegin block, CiBitMap liveKill, CiValue operand) { + // fixed intervals are never live at block boundaries, so + // they need not be processed in live sets. + // this is checked by these assertions to be sure about it. + // the entry block may have incoming + // values in registers, which is ok. + if (!operand.isVariable() && block != ir.startBlock) { + if (isProcessed(operand)) { + assert liveKill.get(operandNumber(operand)) : "using fixed register that is not defined in this block"; + } + } + } + + /** + * Performs a backward dataflow analysis to compute global live sets (i.e. {@link LIRBlock#liveIn} and + * {@link LIRBlock#liveOut}) for each block. + */ + void computeGlobalLiveSets() { + int numBlocks = blockCount(); + boolean changeOccurred; + boolean changeOccurredInBlock; + int iterationCount = 0; + CiBitMap liveOut = new CiBitMap(liveSetSize()); // scratch set for calculations + + // Perform a backward dataflow analysis to compute liveOut and liveIn for each block. + // The loop is executed until a fixpoint is reached (no changes in an iteration) + // Exception handlers must be processed because not all live values are + // present in the state array, e.g. because of global value numbering + do { + changeOccurred = false; + + // iterate all blocks in reverse order + for (int i = numBlocks - 1; i >= 0; i--) { + BlockBegin block = blockAt(i); + LIRBlock lirBlock = block.lirBlock(); + + changeOccurredInBlock = false; + + // liveOut(block) is the union of liveIn(sux), for successors sux of block + int n = block.numberOfSux(); + int e = block.numberOfExceptionHandlers(); + if (n + e > 0) { + // block has successors + if (n > 0) { + liveOut.setFrom(block.suxAt(0).lirBlock.liveIn); + for (int j = 1; j < n; j++) { + liveOut.setUnion(block.suxAt(j).lirBlock.liveIn); + } + } else { + liveOut.clearAll(); + } + for (int j = 0; j < e; j++) { + liveOut.setUnion(block.exceptionHandlerAt(j).lirBlock.liveIn); + } + + if (!lirBlock.liveOut.isSame(liveOut)) { + // A change occurred. Swap the old and new live out sets to avoid copying. + CiBitMap temp = lirBlock.liveOut; + lirBlock.liveOut = liveOut; + liveOut = temp; + + changeOccurred = true; + changeOccurredInBlock = true; + } + } + + if (iterationCount == 0 || changeOccurredInBlock) { + // liveIn(block) is the union of liveGen(block) with (liveOut(block) & !liveKill(block)) + // note: liveIn has to be computed only in first iteration or if liveOut has changed! + CiBitMap liveIn = lirBlock.liveIn; + liveIn.setFrom(lirBlock.liveOut); + liveIn.setDifference(lirBlock.liveKill); + liveIn.setUnion(lirBlock.liveGen); + } + + if (C1XOptions.TraceLinearScanLevel >= 4) { + traceLiveness(changeOccurredInBlock, iterationCount, block); + } + } + iterationCount++; + + if (changeOccurred && iterationCount > 50) { + throw new CiBailout("too many iterations in computeGlobalLiveSets"); + } + } while (changeOccurred); + + if (C1XOptions.DetailedAsserts) { + verifyLiveness(numBlocks); + } + + // check that the liveIn set of the first block is empty + CiBitMap liveInArgs = new CiBitMap(ir.startBlock.lirBlock.liveIn.size()); + if (!ir.startBlock.lirBlock.liveIn.isSame(liveInArgs)) { + if (C1XOptions.DetailedAsserts) { + reportFailure(numBlocks); + } + + // bailout of if this occurs in product mode. + throw new CiBailout("liveIn set of first block must be empty"); + } + } + + private void reportFailure(int numBlocks) { + TTY.println("Error: liveIn set of first block must be empty (when this fails, variables are used before they are defined)"); + TTY.print("affected registers:"); + TTY.println(ir.startBlock.lirBlock.liveIn.toString()); + + // print some additional information to simplify debugging + for (int operandNum = 0; operandNum < ir.startBlock.lirBlock.liveIn.size(); operandNum++) { + if (ir.startBlock.lirBlock.liveIn.get(operandNum)) { + CiValue operand = operands.operandFor(operandNum); + Value instr = operand.isVariable() ? gen.operands.instructionForResult(((CiVariable) operand)) : null; + TTY.println(" var %d (HIR instruction %s)", operandNum, instr == null ? " " : instr.toString()); + + for (int j = 0; j < numBlocks; j++) { + BlockBegin block = blockAt(j); + if (block.lirBlock.liveGen.get(operandNum)) { + TTY.println(" used in block B%d", block.blockID); + } + if (block.lirBlock.liveKill.get(operandNum)) { + TTY.println(" defined in block B%d", block.blockID); + } + } + } + } + } + + private void verifyLiveness(int numBlocks) { + // check that fixed intervals are not live at block boundaries + // (live set must be empty at fixed intervals) + for (int i = 0; i < numBlocks; i++) { + BlockBegin block = blockAt(i); + for (int j = 0; j <= operands.maxRegisterNumber(); j++) { + assert !block.lirBlock.liveIn.get(j) : "liveIn set of fixed register must be empty"; + assert !block.lirBlock.liveOut.get(j) : "liveOut set of fixed register must be empty"; + assert !block.lirBlock.liveGen.get(j) : "liveGen set of fixed register must be empty"; + } + } + } + + private void traceLiveness(boolean changeOccurredInBlock, int iterationCount, BlockBegin block) { + char c = iterationCount == 0 || changeOccurredInBlock ? '*' : ' '; + TTY.print("(%d) liveIn%c B%d ", iterationCount, c, block.blockID); + TTY.println(block.lirBlock.liveIn.toString()); + TTY.print("(%d) liveOut%c B%d ", iterationCount, c, block.blockID); + TTY.println(block.lirBlock.liveOut.toString()); + } + + Interval addUse(CiValue operand, int from, int to, RegisterPriority registerPriority, CiKind kind) { + if (!isProcessed(operand)) { + return null; + } + if (C1XOptions.TraceLinearScanLevel >= 2 && kind == null) { + TTY.println(" use %s from %d to %d (%s)", operand, from, to, registerPriority.name()); + } + + if (kind == null) { + kind = operand.kind.stackKind(); + } + Interval interval = intervalFor(operand); + if (interval == null) { + interval = createInterval(operand); + } + + if (kind != CiKind.Illegal) { + interval.setKind(kind); + } + + if (operand.isVariable() && gen.operands.mustStayInMemory((CiVariable) operand)) { + interval.addRange(from, maxOpId()); + } else { + interval.addRange(from, to); + } + + interval.addUsePos(to, registerPriority); + return interval; + } + + void addTemp(CiValue operand, int tempPos, RegisterPriority registerPriority, CiKind kind) { + if (!isProcessed(operand)) { + return; + } + Interval interval = intervalFor(operand); + if (interval == null) { + interval = createInterval(operand); + } + + if (kind != CiKind.Illegal) { + interval.setKind(kind); + } + + interval.addRange(tempPos, tempPos + 1); + interval.addUsePos(tempPos, registerPriority); + } + + boolean isProcessed(CiValue operand) { + return !operand.isRegister() || attributes(operand.asRegister()).isAllocatable; + } + + void addDef(CiValue operand, int defPos, RegisterPriority registerPriority, CiKind kind) { + if (!isProcessed(operand)) { + return; + } + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println(" def %s defPos %d (%s)", operand, defPos, registerPriority.name()); + } + Interval interval = intervalFor(operand); + if (interval != null) { + + if (kind != CiKind.Illegal) { + interval.setKind(kind); + } + + Range r = interval.first(); + if (r.from <= defPos) { + // Update the starting point (when a range is first created for a use, its + // start is the beginning of the current block until a def is encountered.) + r.from = defPos; + interval.addUsePos(defPos, registerPriority); + + } else { + // Dead value - make vacuous interval + // also add register priority for dead intervals + interval.addRange(defPos, defPos + 1); + interval.addUsePos(defPos, registerPriority); + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println("Warning: def of operand %s at %d occurs without use", operand, defPos); + } + } + + } else { + // Dead value - make vacuous interval + // also add register priority for dead intervals + interval = createInterval(operand); + if (kind != CiKind.Illegal) { + interval.setKind(kind); + } + + interval.addRange(defPos, defPos + 1); + interval.addUsePos(defPos, registerPriority); + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println("Warning: dead value %s at %d in live intervals", operand, defPos); + } + } + + changeSpillDefinitionPos(interval, defPos); + if (registerPriority == RegisterPriority.None && interval.spillState().ordinal() <= SpillState.StartInMemory.ordinal()) { + // detection of method-parameters and roundfp-results + // TODO: move this directly to position where use-kind is computed + interval.setSpillState(SpillState.StartInMemory); + } + } + + /** + * Determines the register priority for an instruction's output/result operand. + */ + RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op, CiValue operand) { + if (op.code == LIROpcode.Move) { + LIROp1 move = (LIROp1) op; + CiValue res = move.result(); + boolean resultInMemory = res.isVariable() && operands.mustStartInMemory((CiVariable) res); + + if (resultInMemory) { + // Begin of an interval with mustStartInMemory set. + // This interval will always get a stack slot first, so return noUse. + return RegisterPriority.None; + + } else if (move.operand().isStackSlot()) { + // method argument (condition must be equal to handleMethodArguments) + return RegisterPriority.None; + + } else if (move.operand().isVariableOrRegister() && move.result().isVariableOrRegister()) { + // Move from register to register + if (blockForId(op.id).checkBlockFlag(BlockBegin.BlockFlag.OsrEntry)) { + // special handling of phi-function moves inside osr-entry blocks + // input operand must have a register instead of output operand (leads to better register + // allocation) + return RegisterPriority.ShouldHaveRegister; + } + } + } + + if (operand.isVariable() && operands.mustStartInMemory((CiVariable) operand)) { + // result is a stack-slot, so prevent immediate reloading + return RegisterPriority.None; + } + + // all other operands require a register + return RegisterPriority.MustHaveRegister; + } + + /** + * Determines the priority which with an instruction's input operand will be allocated a register. + */ + RegisterPriority registerPriorityOfInputOperand(LIRInstruction op, CiValue operand) { + if (op.code == LIROpcode.Move) { + LIROp1 move = (LIROp1) op; + CiValue res = move.result(); + boolean resultInMemory = res.isVariable() && operands.mustStartInMemory((CiVariable) res); + + if (resultInMemory) { + // Move to an interval with mustStartInMemory set. + // To avoid moves from stack to stack (not allowed) force the input operand to a register + return RegisterPriority.MustHaveRegister; + + } else if (move.operand().isVariableOrRegister() && move.result().isVariableOrRegister()) { + // Move from register to register + if (blockForId(op.id).checkBlockFlag(BlockBegin.BlockFlag.OsrEntry)) { + // special handling of phi-function moves inside osr-entry blocks + // input operand must have a register instead of output operand (leads to better register + // allocation) + return RegisterPriority.MustHaveRegister; + } + + // The input operand is not forced to a register (moves from stack to register are allowed), + // but it is faster if the input operand is in a register + return RegisterPriority.ShouldHaveRegister; + } + } + + if (compilation.target.arch.isX86()) { + if (op.code == LIROpcode.Cmove) { + // conditional moves can handle stack operands + assert op.result().isVariableOrRegister(); + return RegisterPriority.ShouldHaveRegister; + } + + // optimizations for second input operand of arithmetic operations on Intel + // this operand is allowed to be on the stack in some cases + CiKind kind = operand.kind.stackKind(); + if (kind == CiKind.Float || kind == CiKind.Double) { + // SSE float instruction (CiKind.Double only supported with SSE2) + switch (op.code) { + case Cmp: + case Add: + case Sub: + case Mul: + case Div: { + LIROp2 op2 = (LIROp2) op; + if (op2.operand1() != op2.operand2() && op2.operand2() == operand) { + assert (op2.result().isVariableOrRegister() || op.code == LIROpcode.Cmp) && op2.operand1().isVariableOrRegister() : "cannot mark second operand as stack if others are not in register"; + return RegisterPriority.ShouldHaveRegister; + } + } + } + } else if (kind != CiKind.Long) { + // integer instruction (note: long operands must always be in register) + switch (op.code) { + case Cmp: + case Add: + case Sub: + case LogicAnd: + case LogicOr: + case LogicXor: { + LIROp2 op2 = (LIROp2) op; + if (op2.operand1() != op2.operand2() && op2.operand2() == operand) { + assert (op2.result().isVariableOrRegister() || op.code == LIROpcode.Cmp) && op2.operand1().isVariableOrRegister() : "cannot mark second operand as stack if others are not in register"; + return RegisterPriority.ShouldHaveRegister; + } + } + } + } + } // X86 + + // all other operands require a register + return RegisterPriority.MustHaveRegister; + } + + /** + * Optimizes moves related to incoming stack based arguments. + * The interval for the destination of such moves is assigned + * the stack slot (which is in the caller's frame) as its + * spill slot. + */ + void handleMethodArguments(LIRInstruction op) { + if (op.code == LIROpcode.Move) { + LIROp1 move = (LIROp1) op; + + if (move.operand().isStackSlot()) { + CiStackSlot slot = (CiStackSlot) move.operand(); + if (C1XOptions.DetailedAsserts) { + int argSlots = compilation.method.signature().argumentSlots(!isStatic(compilation.method.accessFlags())); + assert slot.index() >= 0 && slot.index() < argSlots; + assert move.id > 0 : "invalid id"; + assert blockForId(move.id).numberOfPreds() == 0 : "move from stack must be in first block"; + assert move.result().isVariable() : "result of move must be a variable"; + + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("found move from stack slot %s to %s", slot, move.result()); + } + } + + Interval interval = intervalFor(move.result()); + CiStackSlot copySlot = slot; + if (C1XOptions.CopyPointerStackArguments && slot.kind == CiKind.Object) { + copySlot = allocateSpillSlot(slot.kind); + } + interval.setSpillSlot(copySlot); + interval.assignLocation(copySlot); + } + } + } + + void addRegisterHints(LIRInstruction op) { + switch (op.code) { + case Move: // fall through + case Convert: { + LIROp1 move = (LIROp1) op; + + CiValue moveFrom = move.operand(); + CiValue moveTo = move.result(); + + if (moveTo.isVariableOrRegister() && moveFrom.isVariableOrRegister()) { + Interval from = intervalFor(moveFrom); + Interval to = intervalFor(moveTo); + if (from != null && to != null) { + to.setLocationHint(from); + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("operation at opId %d: added hint from interval %d to %d", move.id, from.operandNumber, to.operandNumber); + } + } + } + break; + } + case Cmove: { + LIROp2 cmove = (LIROp2) op; + + CiValue moveFrom = cmove.operand1(); + CiValue moveTo = cmove.result(); + + if (moveTo.isVariableOrRegister() && moveFrom.isVariableOrRegister()) { + Interval from = intervalFor(moveFrom); + Interval to = intervalFor(moveTo); + if (from != null && to != null) { + to.setLocationHint(from); + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("operation at opId %d: added hint from interval %d to %d", cmove.id, from.operandNumber, to.operandNumber); + } + } + } + break; + } + } + } + + void buildIntervals() { + intervalsSize = operands.size(); + intervals = new Interval[intervalsSize + INITIAL_SPLIT_INTERVALS_CAPACITY]; + + // create a list with all caller-save registers (cpu, fpu, xmm) + RiRegisterConfig registerConfig = compilation.registerConfig; + CiRegister[] callerSaveRegs = registerConfig.getCallerSaveRegisters(); + + // iterate all blocks in reverse order + for (int i = blockCount() - 1; i >= 0; i--) { + BlockBegin block = blockAt(i); + List<LIRInstruction> instructions = block.lir().instructionsList(); + final int blockFrom = block.firstLirInstructionId(); + int blockTo = block.lastLirInstructionId(); + + assert blockFrom == instructions.get(0).id; + assert blockTo == instructions.get(instructions.size() - 1).id; + + // Update intervals for operands live at the end of this block; + CiBitMap live = block.lirBlock.liveOut; + for (int operandNum = live.nextSetBit(0); operandNum >= 0; operandNum = live.nextSetBit(operandNum + 1)) { + assert live.get(operandNum) : "should not stop here otherwise"; + CiValue operand = operands.operandFor(operandNum); + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println("live in %s to %d", operand, blockTo + 2); + } + + addUse(operand, blockFrom, blockTo + 2, RegisterPriority.None, CiKind.Illegal); + + // add special use positions for loop-end blocks when the + // interval is used anywhere inside this loop. It's possible + // that the block was part of a non-natural loop, so it might + // have an invalid loop index. + if (block.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd) && block.loopIndex() != -1 && isIntervalInLoop(operandNum, block.loopIndex())) { + intervalFor(operand).addUsePos(blockTo + 1, RegisterPriority.LiveAtLoopEnd); + } + } + + // iterate all instructions of the block in reverse order. + // skip the first instruction because it is always a label + // definitions of intervals are processed before uses + assert !instructions.get(0).hasOperands() : "first operation must always be a label"; + for (int j = instructions.size() - 1; j >= 1; j--) { + LIRInstruction op = instructions.get(j); + final int opId = op.id; + + // add a temp range for each register if operation destroys caller-save registers + if (op.hasCall) { + for (CiRegister r : callerSaveRegs) { + if (attributes(r).isAllocatable) { + addTemp(r.asValue(), opId, RegisterPriority.None, CiKind.Illegal); + } + } + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("operation destroys all caller-save registers"); + } + } + + // Add any platform dependent temps + pdAddTemps(op); + + // visit definitions (output and temp operands) + int k; + int n; + n = op.operandCount(LIRInstruction.OperandMode.Output); + for (k = 0; k < n; k++) { + CiValue operand = op.operandAt(LIRInstruction.OperandMode.Output, k); + assert operand.isVariableOrRegister(); + addDef(operand, opId, registerPriorityOfOutputOperand(op, operand), operand.kind.stackKind()); + } + + n = op.operandCount(LIRInstruction.OperandMode.Temp); + for (k = 0; k < n; k++) { + CiValue operand = op.operandAt(LIRInstruction.OperandMode.Temp, k); + assert operand.isVariableOrRegister(); + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println(" temp %s tempPos %d (%s)", operand, opId, RegisterPriority.MustHaveRegister.name()); + } + addTemp(operand, opId, RegisterPriority.MustHaveRegister, operand.kind.stackKind()); + } + + // visit uses (input operands) + n = op.operandCount(LIRInstruction.OperandMode.Input); + for (k = 0; k < n; k++) { + CiValue operand = op.operandAt(LIRInstruction.OperandMode.Input, k); + assert operand.isVariableOrRegister(); + RegisterPriority p = registerPriorityOfInputOperand(op, operand); + Interval interval = addUse(operand, blockFrom, opId, p, null); + if (interval != null && op instanceof LIRXirInstruction) { + Range range = interval.first(); + // (tw) Increase range by 1 in order to overlap the input with the temp and the output operand. + if (range.to == opId) { + range.to++; + } + } + } + + // Add uses of live locals from interpreter's point of view for proper + // debug information generation + // Treat these operands as temp values (if the live range is extended + // to a call site, the value would be in a register at the call otherwise) + LIRDebugInfo info = op.info; + if (info != null) { + info.state.forEachLiveStateValue(new ValueProcedure() { + public void doValue(Value value) { + CiValue operand = value.operand(); + if (operand.isVariableOrRegister()) { + addUse(operand, blockFrom, (opId + 1), RegisterPriority.None, null); + } + } + }); + } + + // special steps for some instructions (especially moves) + handleMethodArguments(op); + addRegisterHints(op); + + } // end of instruction iteration + + // (tw) Make sure that no spill store optimization is applied for phi instructions that flow into exception handlers. + if (block.isExceptionEntry()) { + FrameState stateBefore = block.stateBefore(); + stateBefore.forEachLivePhi(block, new PhiProcedure() { + @Override + public boolean doPhi(Phi phi) { + Interval interval = intervalFor(phi.operand()); + if (interval != null) { + interval.setSpillState(SpillState.NoOptimization); + } + return true; + } + }); + } + + } // end of block iteration + + // add the range [0, 1] to all fixed intervals. + // the register allocator need not handle unhandled fixed intervals + for (Interval interval : intervals) { + if (interval != null && interval.operand.isRegister()) { + interval.addRange(0, 1); + } + } + } + + // * Phase 5: actual register allocation + + private void pdAddTemps(LIRInstruction op) { + // TODO Platform dependent! + assert compilation.target.arch.isX86(); + + switch (op.code) { + case Tan: + case Sin: + case Cos: { + // The slow path for these functions may need to save and + // restore all live registers but we don't want to save and + // restore everything all the time, so mark the xmms as being + // killed. If the slow path were explicit or we could propagate + // live register masks down to the assembly we could do better + // but we don't have any easy way to do that right now. We + // could also consider not killing all xmm registers if we + // assume that slow paths are uncommon but it's not clear that + // would be a good idea. + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println("killing XMMs for trig"); + } + int opId = op.id; + + for (CiRegister r : compilation.registerConfig.getCallerSaveRegisters()) { + if (r.isFpu()) { + addTemp(r.asValue(), opId, RegisterPriority.None, CiKind.Illegal); + } + } + break; + } + } + + } + + boolean isSorted(Interval[] intervals) { + int from = -1; + for (Interval interval : intervals) { + assert interval != null; + assert from <= interval.from(); + from = interval.from(); + + // XXX: very slow! + assert Arrays.asList(this.intervals).contains(interval); + } + return true; + } + + 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); + } + + 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_COMPARATOR); + + // 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; + } + + private static final Comparator<Interval> INTERVAL_COMPARATOR = new Comparator<Interval>() { + + public int compare(Interval a, Interval b) { + if (a != null) { + if (b != null) { + return a.from() - b.from(); + } else { + return -1; + } + } else { + if (b != null) { + return 1; + } else { + return 0; + } + } + } + }; + + public void allocateRegisters() { + Interval precoloredIntervals; + Interval notPrecoloredIntervals; + + Interval.Pair result = createUnhandledLists(IS_PRECOLORED_INTERVAL, IS_VARIABLE_INTERVAL); + precoloredIntervals = result.first; + notPrecoloredIntervals = result.second; + + // allocate cpu registers + LinearScanWalker lsw = new LinearScanWalker(this, precoloredIntervals, notPrecoloredIntervals); + lsw.walk(); + lsw.finishAllocation(); + } + + // * Phase 6: resolve data flow + // (insert moves at edges between blocks if intervals have been split) + + // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode + // instead of returning null + Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) { + Interval result = interval.getSplitChildAtOpId(opId, mode, this); + + if (result != null) { + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("Split child at pos " + opId + " of interval " + interval.toString() + " is " + result.toString()); + } + return result; + } + + throw new CiBailout("LinearScan: interval is null"); + } + + Interval intervalAtBlockBegin(BlockBegin block, CiValue operand) { + assert operand.isVariable() : "register number out of bounds"; + assert intervalFor(operand) != null : "no interval found"; + + return splitChildAtOpId(intervalFor(operand), block.firstLirInstructionId(), LIRInstruction.OperandMode.Output); + } + + Interval intervalAtBlockEnd(BlockBegin block, CiValue operand) { + assert operand.isVariable() : "register number out of bounds"; + assert intervalFor(operand) != null : "no interval found"; + + return splitChildAtOpId(intervalFor(operand), block.lastLirInstructionId() + 1, LIRInstruction.OperandMode.Output); + } + + Interval intervalAtOpId(CiValue operand, int opId) { + assert operand.isVariable() : "register number out of bounds"; + assert intervalFor(operand) != null : "no interval found"; + + return splitChildAtOpId(intervalFor(operand), opId, LIRInstruction.OperandMode.Input); + } + + void resolveCollectMappings(BlockBegin fromBlock, BlockBegin toBlock, MoveResolver moveResolver) { + assert moveResolver.checkEmpty(); + + int numOperands = operands.size(); + CiBitMap liveAtEdge = toBlock.lirBlock.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 fromBlock.lirBlock.liveOut.get(operandNum) && toBlock.lirBlock.liveIn.get(operandNum) : "interval not live at this edge"; + + CiValue liveOperand = operands.operandFor(operandNum); + Interval fromInterval = intervalAtBlockEnd(fromBlock, liveOperand); + Interval toInterval = intervalAtBlockBegin(toBlock, liveOperand); + + if (fromInterval != toInterval && (fromInterval.location() != toInterval.location())) { + // need to insert move instruction + moveResolver.addMapping(fromInterval, toInterval); + } + } + } + + void resolveFindInsertPos(BlockBegin fromBlock, BlockBegin toBlock, MoveResolver moveResolver) { + if (fromBlock.numberOfSux() <= 1) { + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("inserting moves at end of fromBlock B%d", fromBlock.blockID); + } + + List<LIRInstruction> instructions = fromBlock.lir().instructionsList(); + LIRInstruction instr = instructions.get(instructions.size() - 1); + if (instr instanceof LIRBranch) { + LIRBranch branch = (LIRBranch) instr; + // insert moves before branch + assert branch.cond() == Condition.TRUE : "block does not end with an unconditional jump"; + moveResolver.setInsertPosition(fromBlock.lir(), instructions.size() - 2); + } else { + moveResolver.setInsertPosition(fromBlock.lir(), instructions.size() - 1); + } + + } else { + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("inserting moves at beginning of toBlock B%d", toBlock.blockID); + } + + if (C1XOptions.DetailedAsserts) { + assert fromBlock.lir().instructionsList().get(0) instanceof LIRLabel : "block does not start with a label"; + + // because the number of predecessor edges matches the number of + // successor edges, blocks which are reached by switch statements + // may have be more than one predecessor but it will be guaranteed + // that all predecessors will be the same. + for (int i = 0; i < toBlock.numberOfPreds(); i++) { + assert fromBlock == toBlock.predAt(i) : "all critical edges must be broken"; + } + } + + moveResolver.setInsertPosition(toBlock.lir(), 0); + } + } + + /** + * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals that + * have been split. + */ + void resolveDataFlow() { + int numBlocks = blockCount(); + MoveResolver moveResolver = new MoveResolver(this); + CiBitMap blockCompleted = new CiBitMap(numBlocks); + CiBitMap alreadyResolved = new CiBitMap(numBlocks); + + int i; + for (i = 0; i < numBlocks; i++) { + BlockBegin block = blockAt(i); + + // check if block has only one predecessor and only one successor + if (block.numberOfPreds() == 1 && block.numberOfSux() == 1 && block.numberOfExceptionHandlers() == 0 && !block.isExceptionEntry()) { + List<LIRInstruction> instructions = block.lir().instructionsList(); + assert instructions.get(0).code == LIROpcode.Label : "block must start with label"; + assert instructions.get(instructions.size() - 1).code == LIROpcode.Branch : "block with successors must end with branch"; + assert ((LIRBranch) instructions.get(instructions.size() - 1)).cond() == Condition.TRUE : "block with successor must end with unconditional branch"; + + // check if block is empty (only label and branch) + if (instructions.size() == 2) { + BlockBegin pred = block.predAt(0); + BlockBegin sux = block.suxAt(0); + + // prevent optimization of two consecutive blocks + if (!blockCompleted.get(pred.linearScanNumber()) && !blockCompleted.get(sux.linearScanNumber())) { + if (C1XOptions.TraceLinearScanLevel >= 3) { + TTY.println(" optimizing empty block B%d (pred: B%d, sux: B%d)", block.blockID, pred.blockID, sux.blockID); + } + blockCompleted.set(block.linearScanNumber()); + + // directly resolve between pred and sux (without looking at the empty block between) + resolveCollectMappings(pred, sux, moveResolver); + if (moveResolver.hasMappings()) { + moveResolver.setInsertPosition(block.lir(), 0); + moveResolver.resolveAndAppendMoves(); + } + } + } + } + } + + for (i = 0; i < numBlocks; i++) { + if (!blockCompleted.get(i)) { + BlockBegin fromBlock = blockAt(i); + alreadyResolved.setFrom(blockCompleted); + + int numSux = fromBlock.numberOfSux(); + for (int s = 0; s < numSux; s++) { + BlockBegin toBlock = fromBlock.suxAt(s); + + // check for duplicate edges between the same blocks (can happen with switch blocks) + if (!alreadyResolved.get(toBlock.linearScanNumber())) { + if (C1XOptions.TraceLinearScanLevel >= 3) { + TTY.println(" processing edge between B%d and B%d", fromBlock.blockID, toBlock.blockID); + } + alreadyResolved.set(toBlock.linearScanNumber()); + + // collect all intervals that have been split between fromBlock and toBlock + resolveCollectMappings(fromBlock, toBlock, moveResolver); + if (moveResolver.hasMappings()) { + resolveFindInsertPos(fromBlock, toBlock, moveResolver); + moveResolver.resolveAndAppendMoves(); + } + } + } + } + } + } + + void resolveExceptionEntry(BlockBegin block, CiValue operand, MoveResolver moveResolver) { + if (intervalFor(operand) == null) { + // if a phi function is never used, no interval is created . ignore this + return; + } + + Interval interval = intervalAtBlockBegin(block, operand); + CiValue location = interval.location(); + + if (location.isRegister() && interval.alwaysInMemory()) { + // the interval is split to get a short range that is located on the stack + // in the following two cases: + // * the interval started in memory (e.g. method parameter), but is currently in a register + // this is an optimization for exception handling that reduces the number of moves that + // are necessary for resolving the states when an exception uses this exception handler + // * the interval would be on the fpu stack at the begin of the exception handler + // this is not allowed because of the complicated fpu stack handling on Intel + + // range that will be spilled to memory + int fromOpId = block.firstLirInstructionId(); + int toOpId = fromOpId + 1; // short live range of length 1 + assert interval.from() <= fromOpId && interval.to() >= toOpId : "no split allowed between exception entry and first instruction"; + + if (interval.from() != fromOpId) { + // the part before fromOpId is unchanged + interval = interval.split(fromOpId, this); + interval.assignLocation(location); + } + assert interval.from() == fromOpId : "must be true now"; + + Interval spilledPart = interval; + if (interval.to() != toOpId) { + // the part after toOpId is unchanged + spilledPart = interval.splitFromStart(toOpId, this); + moveResolver.addMapping(spilledPart, interval); + } + assignSpillSlot(spilledPart); + + assert spilledPart.from() == fromOpId && spilledPart.to() == toOpId : "just checking"; + } + } + + void resolveExceptionEntry(final BlockBegin block, final MoveResolver moveResolver) { + assert block.checkBlockFlag(BlockBegin.BlockFlag.ExceptionEntry) : "should not call otherwise"; + assert moveResolver.checkEmpty(); + + // visit all registers where the liveIn bit is set + for (int operandNum = block.lirBlock.liveIn.nextSetBit(0); operandNum >= 0; operandNum = block.lirBlock.liveIn.nextSetBit(operandNum + 1)) { + resolveExceptionEntry(block, operands.operandFor(operandNum), moveResolver); + } + + // the liveIn bits are not set for phi functions of the xhandler entry, so iterate them separately + block.stateBefore().forEachLivePhi(block, new PhiProcedure() { + public boolean doPhi(Phi phi) { + resolveExceptionEntry(block, phi.operand(), moveResolver); + return true; + } + }); + + if (moveResolver.hasMappings()) { + // insert moves after first instruction + moveResolver.setInsertPosition(block.lir(), 0); + moveResolver.resolveAndAppendMoves(); + } + } + + void resolveExceptionEdge(ExceptionHandler handler, int throwingOpId, CiValue operand, Phi phi, MoveResolver moveResolver) { + if (intervalFor(operand) == null) { + // if a phi function is never used, no interval is created . ignore this + return; + } + + // the computation of toInterval is equal to resolveCollectMappings, + // but fromInterval is more complicated because of phi functions + BlockBegin toBlock = handler.entryBlock(); + Interval toInterval = intervalAtBlockBegin(toBlock, operand); + + if (phi != null) { + // phi function of the exception entry block + // no moves are created for this phi function in the LIRGenerator, so the + // interval at the throwing instruction must be searched using the operands + // of the phi function + Value fromValue = phi.inputAt(handler.phiOperand()); + Constant con = null; + if (fromValue instanceof Constant) { + con = (Constant) fromValue; + } + if (con != null && (con.operand().isIllegal() || con.operand().isConstant())) { + // unpinned constants may have no register, so add mapping from constant to interval + moveResolver.addMapping(con.asConstant(), toInterval); + } else { + // search split child at the throwing opId + Interval fromInterval = intervalAtOpId(fromValue.operand(), throwingOpId); + if (fromInterval != toInterval) { + moveResolver.addMapping(fromInterval, toInterval); + // with phi functions it can happen that the same fromValue is used in + // multiple mappings, so notify move-resolver that this is allowed + moveResolver.setMultipleReadsAllowed(); + } + } + } else { + // no phi function, so use regNum also for fromInterval + // search split child at the throwing opId + Interval fromInterval = intervalAtOpId(operand, throwingOpId); + if (fromInterval != toInterval) { + // optimization to reduce number of moves: when toInterval is on stack and + // the stack slot is known to be always correct, then no move is necessary + if (!fromInterval.alwaysInMemory() || fromInterval.spillSlot() != toInterval.location()) { + moveResolver.addMapping(fromInterval, toInterval); + } + } + } + } + + void resolveExceptionEdge(final ExceptionHandler handler, final int throwingOpId, final MoveResolver moveResolver) { + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("resolving exception handler B%d: throwingOpId=%d", handler.entryBlock().blockID, throwingOpId); + } + + assert moveResolver.checkEmpty(); + assert handler.lirOpId() == -1 : "already processed this xhandler"; + handler.setLirOpId(throwingOpId); + assert handler.entryCode() == null : "code already present"; + + // visit all registers where the liveIn bit is set + BlockBegin block = handler.entryBlock(); + for (int operandNum = block.lirBlock.liveIn.nextSetBit(0); operandNum >= 0; operandNum = block.lirBlock.liveIn.nextSetBit(operandNum + 1)) { + resolveExceptionEdge(handler, throwingOpId, operands.operandFor(operandNum), null, moveResolver); + } + + // the liveIn bits are not set for phi functions of the xhandler entry, so iterate them separately + block.stateBefore().forEachLivePhi(block, new PhiProcedure() { + public boolean doPhi(Phi phi) { + resolveExceptionEdge(handler, throwingOpId, phi.operand(), phi, moveResolver); + return true; + } + }); + + if (moveResolver.hasMappings()) { + LIRList entryCode = new LIRList(gen); + moveResolver.setInsertPosition(entryCode, 0); + moveResolver.resolveAndAppendMoves(); + + entryCode.jump(handler.entryBlock()); + handler.setEntryCode(entryCode); + } + } + + void resolveExceptionHandlers() { + MoveResolver moveResolver = new MoveResolver(this); + //LIRVisitState visitor = new LIRVisitState(); + int numBlocks = blockCount(); + + int i; + for (i = 0; i < numBlocks; i++) { + BlockBegin block = blockAt(i); + if (block.checkBlockFlag(BlockFlag.ExceptionEntry)) { + resolveExceptionEntry(block, moveResolver); + } + } + + for (i = 0; i < numBlocks; i++) { + BlockBegin block = blockAt(i); + LIRList ops = block.lir(); + int numOps = ops.length(); + + // iterate all instructions of the block. skip the first because it is always a label + assert !ops.at(0).hasOperands() : "first operation must always be a label"; + for (int j = 1; j < numOps; j++) { + LIRInstruction op = ops.at(j); + int opId = op.id; + + if (opId != -1 && op.info != null) { + // visit operation to collect all operands + for (ExceptionHandler handler : op.exceptionEdges()) { + resolveExceptionEdge(handler, opId, moveResolver); + } + + } else if (C1XOptions.DetailedAsserts) { + assert op.exceptionEdges().size() == 0 : "missed exception handler"; + } + } + } + } + + // * Phase 7: assign register numbers back to LIR + // (includes computation of debug information and oop maps) + + boolean verifyAssignedLocation(Interval interval, CiValue location) { + CiKind kind = interval.kind(); + + assert location.isRegister() || location.isStackSlot(); + + if (location.isRegister()) { + CiRegister reg = location.asRegister(); + + // register + switch (kind) { + case Byte: + case Char: + case Short: + case Jsr: + case Word: + case Object: + case Int: { + assert reg.isCpu() : "not cpu register"; + break; + } + + case Long: { + assert reg.isCpu() : "not cpu register"; + break; + } + + case Float: { + assert !compilation.target.arch.isX86() || reg.isFpu() : "not xmm register: " + reg; + break; + } + + case Double: { + assert !compilation.target.arch.isX86() || reg.isFpu() : "not xmm register: " + reg; + break; + } + + default: { + throw Util.shouldNotReachHere(); + } + } + } + return true; + } + + CiStackSlot canonicalSpillOpr(Interval interval) { + assert interval.spillSlot() != null : "canonical spill slot not set"; + return interval.spillSlot(); + } + + /** + * Assigns the allocated location for an LIR instruction operand back into the instruction. + * + * @param operand an LIR instruction operand + * @param opId the id of the LIR instruction using {@code operand} + * @param mode the usage mode for {@code operand} by the instruction + * @return the location assigned for the operand + */ + private CiValue colorLirOperand(CiVariable operand, int opId, OperandMode mode) { + Interval interval = intervalFor(operand); + assert interval != null : "interval must exist"; + + if (opId != -1) { + if (C1XOptions.DetailedAsserts) { + BlockBegin block = blockForId(opId); + if (block.numberOfSux() <= 1 && opId == block.lastLirInstructionId()) { + // check if spill moves could have been appended at the end of this block, but + // before the branch instruction. So the split child information for this branch would + // be incorrect. + LIRInstruction instr = block.lir().instructionsList().get(block.lir().instructionsList().size() - 1); + if (instr instanceof LIRBranch) { + LIRBranch branch = (LIRBranch) instr; + if (block.lirBlock.liveOut.get(operandNumber(operand))) { + assert branch.cond() == Condition.TRUE : "block does not end with an unconditional jump"; + throw new CiBailout("can't get split child for the last branch of a block because the information would be incorrect (moves are inserted before the branch in resolveDataFlow)"); + } + } + } + } + + // operands are not changed when an interval is split during allocation, + // so search the right interval here + interval = splitChildAtOpId(interval, opId, mode); + } + + return interval.location(); + } + + IntervalWalker initComputeOopMaps() { + // setup lists of potential oops for walking + Interval oopIntervals; + Interval nonOopIntervals; + + oopIntervals = createUnhandledLists(IS_OOP_INTERVAL, null).first; + + // intervals that have no oops inside need not to be processed. + // to ensure a walking until the last instruction id, add a dummy interval + // with a high operation id + nonOopIntervals = new Interval(CiValue.IllegalValue, -1); + nonOopIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1); + + return new IntervalWalker(this, oopIntervals, nonOopIntervals); + } + + void computeOopMap(IntervalWalker iw, LIRInstruction op, LIRDebugInfo info, boolean isCallSite, CiBitMap frameRefMap, CiBitMap regRefMap) { + if (C1XOptions.TraceLinearScanLevel >= 3) { + TTY.println("creating oop map at opId %d", op.id); + } + + // walk before the current operation . intervals that start at + // the operation (i.e. output operands of the operation) are not + // included in the oop map + iw.walkBefore(op.id); + + // Iterate through active intervals + for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) { + CiValue operand = interval.operand; + + assert interval.currentFrom() <= op.id && op.id <= interval.currentTo() : "interval should not be active otherwise"; + assert interval.operand.isVariable() : "fixed interval found"; + + // Check if this range covers the instruction. Intervals that + // start or end at the current operation are not included in the + // oop map, except in the case of patching moves. For patching + // moves, any intervals which end at this instruction are included + // in the oop map since we may safepoint while doing the patch + // before we've consumed the inputs. + if (op.id < interval.currentTo()) { + // caller-save registers must not be included into oop-maps at calls + assert !isCallSite || !operand.isRegister() || !isCallerSave(operand) : "interval is in a caller-save register at a call . register will be overwritten"; + + CiValue location = interval.location(); + if (location.isStackSlot()) { + location = frameMap.toStackAddress((CiStackSlot) location); + } + info.setOop(location, compilation, frameRefMap, regRefMap); + + // Spill optimization: when the stack value is guaranteed to be always correct, + // then it must be added to the oop map even if the interval is currently in a register + if (interval.alwaysInMemory() && op.id > interval.spillDefinitionPos() && !interval.location().equals(interval.spillSlot())) { + assert interval.spillDefinitionPos() > 0 : "position not set correctly"; + assert interval.spillSlot() != null : "no spill slot assigned"; + assert !interval.operand.isRegister() : "interval is on stack : so stack slot is registered twice"; + info.setOop(frameMap.toStackAddress(interval.spillSlot()), compilation, frameRefMap, regRefMap); + } + } + } + } + + private boolean isCallerSave(CiValue operand) { + return attributes(operand.asRegister()).isCallerSave; + } + + void computeOopMap(IntervalWalker iw, LIRInstruction op, LIRDebugInfo info, CiBitMap frameRefMap, CiBitMap regRefMap) { + computeOopMap(iw, op, info, op.hasCall, frameRefMap, regRefMap); + if (op instanceof LIRCall) { + List<CiValue> pointerSlots = ((LIRCall) op).pointerSlots; + if (pointerSlots != null) { + for (CiValue v : pointerSlots) { + info.setOop(v, compilation, frameRefMap, regRefMap); + } + } + } else if (op instanceof LIRXirInstruction) { + List<CiValue> pointerSlots = ((LIRXirInstruction) op).pointerSlots; + if (pointerSlots != null) { + for (CiValue v : pointerSlots) { + info.setOop(v, compilation, frameRefMap, regRefMap); + } + } + } + } + + CiValue toCiValue(int opId, Value value) { + if (value != null && value.operand() != CiValue.IllegalValue) { + CiValue operand = value.operand(); + Constant con = null; + if (value instanceof Constant) { + con = (Constant) value; + } + + assert con == null || operand.isVariable() || operand.isConstant() || operand.isIllegal() : "Constant instructions have only constant operands (or illegal if constant is optimized away)"; + + if (con != null && !con.isLive() && !operand.isConstant()) { + // Unpinned constants may have a variable operand for a part of the lifetime + // or may be illegal when it was optimized away, + // so always use a constant operand + operand = con.asConstant(); + } + + if (operand.isVariable()) { + OperandMode mode = OperandMode.Input; + BlockBegin block = blockForId(opId); + if (block.numberOfSux() == 1 && opId == block.lastLirInstructionId()) { + // generating debug information for the last instruction of a block. + // if this instruction is a branch, spill moves are inserted before this branch + // and so the wrong operand would be returned (spill moves at block boundaries are not + // considered in the live ranges of intervals) + // Solution: use the first opId of the branch target block instead. + final LIRInstruction instr = block.lir().instructionsList().get(block.lir().instructionsList().size() - 1); + if (instr instanceof LIRBranch) { + if (block.lirBlock.liveOut.get(operandNumber(operand))) { + opId = block.suxAt(0).firstLirInstructionId(); + mode = OperandMode.Output; + } + } + } + + // Get current location of operand + // The operand must be live because debug information is considered when building the intervals + // if the interval is not live, colorLirOperand will cause an assert on failure + operand = colorLirOperand((CiVariable) operand, opId, mode); + assert !hasCall(opId) || operand.isStackSlot() || !isCallerSave(operand) : "cannot have caller-save register operands at calls"; + return operand; + } else if (operand.isRegister()) { + assert value instanceof LoadRegister; + return operand; + } else { + assert value instanceof Constant; + assert operand.isConstant() : "operand must be constant"; + return operand; + } + } else { + // return a dummy value because real value not needed + return CiValue.IllegalValue; + } + } + + CiFrame computeFrameForState(int opId, FrameState state, CiBitMap frameRefMap) { + CiFrame callerFrame = null; + + FrameState callerState = state.callerState(); + if (callerState != null) { + // process recursively to compute outermost scope first + callerFrame = computeFrameForState(opId, callerState, frameRefMap); + } + + CiValue[] values = new CiValue[state.valuesSize() + state.locksSize()]; + int valueIndex = 0; + + for (int i = 0; i < state.valuesSize(); i++) { + values[valueIndex++] = toCiValue(opId, state.valueAt(i)); + } + + for (int i = 0; i < state.locksSize(); i++) { + if (compilation.runtime.sizeOfBasicObjectLock() != 0) { + CiStackSlot monitorAddress = frameMap.toMonitorBaseStackAddress(i); + values[valueIndex++] = monitorAddress; + assert frameRefMap != null; + CiStackSlot objectAddress = frameMap.toMonitorObjectStackAddress(i); + LIRDebugInfo.setBit(frameRefMap, objectAddress.index()); + } else { + Value lock = state.lockAt(i); + if (lock.isConstant() && compilation.runtime.asJavaClass(lock.asConstant()) != null) { + // lock on class for synchronized static method + values[valueIndex++] = lock.asConstant(); + } else { + values[valueIndex++] = toCiValue(opId, lock); + } + } + } + + return new CiFrame(callerFrame, state.scope().method, state.bci, values, state.localsSize(), state.stackSize(), state.locksSize()); + } + + private void computeDebugInfo(IntervalWalker iw, LIRInstruction op) { + assert iw != null : "interval walker needed for debug information"; + computeDebugInfo(iw, op, op.info); + + if (op instanceof LIRXirInstruction) { + LIRXirInstruction xir = (LIRXirInstruction) op; + if (xir.infoAfter != null) { + computeDebugInfo(iw, op, xir.infoAfter); + } + } + } + + + private void computeDebugInfo(IntervalWalker iw, LIRInstruction op, LIRDebugInfo info) { + if (info != null) { + if (info.debugInfo == null) { + int frameSize = compilation.frameMap().frameSize(); + int frameWords = frameSize / compilation.target.spillSlotSize; + CiBitMap frameRefMap = new CiBitMap(frameWords); + CiBitMap regRefMap = !op.hasCall ? new CiBitMap(compilation.target.arch.registerReferenceMapBitCount) : null; + CiFrame frame = compilation.placeholderState != null ? null : computeFrame(info.state, op.id, frameRefMap); + computeOopMap(iw, op, info, frameRefMap, regRefMap); + info.debugInfo = new CiDebugInfo(frame, regRefMap, frameRefMap); + } else if (C1XOptions.DetailedAsserts) { + assert info.debugInfo.frame().equals(computeFrame(info.state, op.id, new CiBitMap(info.debugInfo.frameRefMap.size()))); + } + } + } + + CiFrame computeFrame(FrameState state, int opId, CiBitMap frameRefMap) { + if (C1XOptions.TraceLinearScanLevel >= 3) { + TTY.println("creating debug information at opId %d", opId); + } + return computeFrameForState(opId, state, frameRefMap); + } + + private void assignLocations(List<LIRInstruction> instructions, IntervalWalker iw) { + int numInst = instructions.size(); + boolean hasDead = false; + + for (int j = 0; j < numInst; j++) { + LIRInstruction op = instructions.get(j); + if (op == null) { // this can happen when spill-moves are removed in eliminateSpillMoves + hasDead = true; + continue; + } + + // iterate all modes of the visitor and process all virtual operands + for (LIRInstruction.OperandMode mode : LIRInstruction.OPERAND_MODES) { + int n = op.operandCount(mode); + for (int k = 0; k < n; k++) { + CiValue operand = op.operandAt(mode, k); + if (operand.isVariable()) { + op.setOperandAt(mode, k, colorLirOperand((CiVariable) operand, op.id, mode)); + } + } + } + + if (op.info != null) { + // exception handling + if (compilation.hasExceptionHandlers()) { + for (ExceptionHandler handler : op.exceptionEdges()) { + if (handler.entryCode() != null) { + assignLocations(handler.entryCode().instructionsList(), null); + } + } + } + + // compute reference map and debug information + computeDebugInfo(iw, op); + } + + // make sure we haven't made the op invalid. + assert op.verify(); + + // remove useless moves + if (op.code == LIROpcode.Move) { + CiValue src = op.operand(0); + CiValue dst = op.result(); + if (dst == src || src.equals(dst)) { + // TODO: what about o.f = o.f and exceptions? + instructions.set(j, null); + hasDead = true; + } + } + } + + if (hasDead) { + // iterate all instructions of the block and remove all null-values. + int insertPoint = 0; + for (int j = 0; j < numInst; j++) { + LIRInstruction op = instructions.get(j); + if (op != null) { + if (insertPoint != j) { + instructions.set(insertPoint, op); + } + insertPoint++; + } + } + Util.truncate(instructions, insertPoint); + } + } + + private void assignLocations() { + IntervalWalker iw = initComputeOopMaps(); + for (BlockBegin block : sortedBlocks) { + assignLocations(block.lir().instructionsList(), iw); + } + } + + public void allocate() { + if (C1XOptions.PrintTimers) { + C1XTimers.LIFETIME_ANALYSIS.start(); + } + + numberInstructions(); + + printLir("Before register allocation", true); + + computeLocalLiveSets(); + computeGlobalLiveSets(); + + buildIntervals(); + sortIntervalsBeforeAllocation(); + + if (C1XOptions.PrintTimers) { + C1XTimers.LIFETIME_ANALYSIS.stop(); + C1XTimers.LINEAR_SCAN.start(); + } + + printIntervals("Before register allocation"); + + allocateRegisters(); + + if (C1XOptions.PrintTimers) { + C1XTimers.LINEAR_SCAN.stop(); + C1XTimers.RESOLUTION.start(); + } + + resolveDataFlow(); + if (compilation.hasExceptionHandlers()) { + resolveExceptionHandlers(); + } + + if (C1XOptions.PrintTimers) { + C1XTimers.RESOLUTION.stop(); + C1XTimers.DEBUG_INFO.start(); + } + + C1XMetrics.LSRASpills += (maxSpills - frameMap.initialSpillSlot()); + + // fill in number of spill slots into frameMap + frameMap.finalizeFrame(maxSpills); + + printIntervals("After register allocation"); + printLir("After register allocation", true); + + sortIntervalsAfterAllocation(); + + if (C1XOptions.DetailedAsserts) { + verify(); + } + + eliminateSpillMoves(); + assignLocations(); + + if (C1XOptions.DetailedAsserts) { + verifyIntervals(); + } + + if (C1XOptions.PrintTimers) { + C1XTimers.DEBUG_INFO.stop(); + C1XTimers.CODE_CREATE.start(); + } + + printLir("After register number assignment", true); + + EdgeMoveOptimizer.optimize(ir.linearScanOrder()); + if (C1XOptions.OptControlFlow) { + ControlFlowOptimizer.optimize(ir); + } + + printLir("After control flow optimization", false); + } + + void printIntervals(String label) { + if (C1XOptions.TraceLinearScanLevel >= 1) { + int i; + TTY.println(); + TTY.println(label); + + for (Interval interval : intervals) { + if (interval != null) { + TTY.out().println(interval.logString(this)); + } + } + + TTY.println(); + TTY.println("--- Basic Blocks ---"); + for (i = 0; i < blockCount(); i++) { + BlockBegin block = blockAt(i); + TTY.print("B%d [%d, %d, %d, %d] ", block.blockID, block.firstLirInstructionId(), block.lastLirInstructionId(), block.loopIndex(), block.loopDepth()); + } + TTY.println(); + TTY.println(); + } + + if (compilation.compiler.isObserved()) { + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, label, this, intervals, intervalsSize)); + } + } + + void printLir(String label, boolean hirValid) { + if (C1XOptions.TraceLinearScanLevel >= 1 && !TTY.isSuppressed()) { + TTY.println(); + TTY.println(label); + LIRList.printLIR(ir.linearScanOrder()); + TTY.println(); + } + + if (compilation.compiler.isObserved()) { + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, label, compilation.hir().startBlock, hirValid, true)); + } + } + + boolean verify() { + // (check that all intervals have a correct register and that no registers are overwritten) + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println(" verifying intervals *"); + } + verifyIntervals(); + + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println(" verifying that no oops are in fixed intervals *"); + } + //verifyNoOopsInFixedIntervals(); + + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println(" verifying that unpinned constants are not alive across block boundaries"); + } + verifyConstants(); + + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println(" verifying register allocation *"); + } + verifyRegisters(); + + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println(" no errors found *"); + } + + return true; + } + + private void verifyRegisters() { + RegisterVerifier verifier = new RegisterVerifier(this); + verifier.verify(blockAt(0)); + } + + void verifyIntervals() { + int len = intervalsSize; + + for (int i = 0; i < len; i++) { + Interval i1 = intervals[i]; + if (i1 == null) { + continue; + } + + i1.checkSplitChildren(); + + if (i1.operandNumber != i) { + TTY.println("Interval %d is on position %d in list", i1.operandNumber, i); + TTY.println(i1.logString(this)); + throw new CiBailout(""); + } + + if (i1.operand.isVariable() && i1.kind() == CiKind.Illegal) { + TTY.println("Interval %d has no type assigned", i1.operandNumber); + TTY.println(i1.logString(this)); + throw new CiBailout(""); + } + + if (i1.location() == null) { + TTY.println("Interval %d has no register assigned", i1.operandNumber); + TTY.println(i1.logString(this)); + throw new CiBailout(""); + } + + if (!isProcessed(i1.location())) { + TTY.println("Can not have an Interval for an ignored register " + i1.location()); + TTY.println(i1.logString(this)); + throw new CiBailout(""); + } + + if (i1.first() == Range.EndMarker) { + TTY.println("Interval %d has no Range", i1.operandNumber); + TTY.println(i1.logString(this)); + throw new CiBailout(""); + } + + for (Range r = i1.first(); r != Range.EndMarker; r = r.next) { + if (r.from >= r.to) { + TTY.println("Interval %d has zero length range", i1.operandNumber); + TTY.println(i1.logString(this)); + throw new CiBailout(""); + } + } + + 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; + } + CiValue l1 = i1.location(); + CiValue l2 = i2.location(); + if (i1.intersects(i2) && (l1.equals(l2))) { + if (C1XOptions.DetailedAsserts) { + TTY.println("Intervals %d and %d overlap and have the same register assigned", i1.operandNumber, i2.operandNumber); + TTY.println(i1.logString(this)); + TTY.println(i2.logString(this)); + } + throw new CiBailout(""); + } + } + } + } + + void verifyNoOopsInFixedIntervals() { + 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(CiValue.IllegalValue, -1); + otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1); + IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals); + + for (int i = 0; i < blockCount(); i++) { + BlockBegin block = blockAt(i); + + List<LIRInstruction> instructions = block.lir().instructionsList(); + + for (int j = 0; j < instructions.size(); j++) { + LIRInstruction op = instructions.get(j); + + if (op.info != null) { + 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. + boolean ok = false; + for (LIRInstruction.OperandMode mode : LIRInstruction.OPERAND_MODES) { + int n = op.operandCount(mode); + for (int k = 0; k < n; k++) { + CiValue operand = op.operandAt(mode, k); + if (operand.isRegister()) { + if (intervalFor(operand) == interval) { + ok = true; + break; + } + } + } + } + assert ok : "fixed intervals should never be live across an oopmap point"; + } + } + } + } + } + } + } + + void verifyConstants() { + int numBlocks = blockCount(); + + for (int i = 0; i < numBlocks; i++) { + BlockBegin block = blockAt(i); + CiBitMap liveAtEdge = block.lirBlock.liveIn; + + // visit all operands where the liveAtEdge bit is set + for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) { + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("checking interval %d of block B%d", operandNum, block.blockID); + } + CiValue operand = operands.operandFor(operandNum); + assert operand.isVariable() : "value must have variable operand"; + Value value = gen.operands.instructionForResult(((CiVariable) operand)); + assert value != null : "all intervals live across block boundaries must have Value"; + // TKR assert value.asConstant() == null || value.isPinned() : + // "only pinned constants can be alive accross block boundaries"; + } + } + } + + public int numberOfSpillSlots(CiKind kind) { + return compilation.target.spillSlots(kind); + } +}