truffle: graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java comparison

comparison graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java @ 19560:4d70d150944f

Remove AbstractBlock interface.

author	Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date	Mon, 23 Feb 2015 18:37:20 +0100
parents	95a7954ea155
children	a33fe10c4d93

comparison

equal deleted inserted replaced

-:08d94d9f0b0f
+:4d70d150944f
 final BlockMap<BlockData> blockData;
 /**
 * List of blocks in linear-scan order. This is only correct as long as the CFG does not change.
 */
-final List<? extends AbstractBlock<?>> sortedBlocks;
+final List<? extends AbstractBlockBase<?>> sortedBlocks;
 /**
 * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals.
 */
 Interval[] intervals;
 * array.
 */
 LIRInstruction[] opIdToInstructionMap;
 /**
-* Map from an instruction {@linkplain LIRInstruction#id id} to the {@linkplain AbstractBlock
+* 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.
 */
-AbstractBlock<?>[] opIdToBlockMap;
+AbstractBlockBase<?>[] opIdToBlockMap;
 /**
 * Bit set for each variable that is contained in each loop.
 */
 BitMap2D intervalInLoop;
 // If all allocatable registers are caller saved, then no registers are live across a call
 // site. The register allocator can save time not trying to find a register at a call site.
 this.callKillsRegisters = this.frameMapBuilder.getRegisterConfig().areAllAllocatableRegistersCallerSaved();
 }
-int getFirstLirInstructionId(AbstractBlock<?> block) {
+int getFirstLirInstructionId(AbstractBlockBase<?> block) {
 int result = ir.getLIRforBlock(block).get(0).id();
 assert result >= 0;
 return result;
 }
-int getLastLirInstructionId(AbstractBlock<?> block) {
+int getLastLirInstructionId(AbstractBlockBase<?> block) {
 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
 int result = instructions.get(instructions.size() - 1).id();
 assert result >= 0;
 return result;
 }
 // access to block list (sorted in linear scan order)
 int blockCount() {
 return sortedBlocks.size();
 }
-AbstractBlock<?> blockAt(int index) {
+AbstractBlockBase<?> blockAt(int index) {
 return sortedBlocks.get(index);
 }
 /**
 * Gets the size of the {@link BlockData#liveIn} and {@link BlockData#liveOut} sets for a basic
 * 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}
 */
-AbstractBlock<?> blockForId(int opId) {
+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) {
 if (DetailedAsserts.getValue()) {
 checkIntervals(interval);
 }
 LIRInsertionBuffer insertionBuffer = new LIRInsertionBuffer();
-for (AbstractBlock<?> block : sortedBlocks) {
+for (AbstractBlockBase<?> block : sortedBlocks) {
 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
 int numInst = instructions.size();
 // iterate all instructions of the block. skip the first
 // because it is always a label
 }
 };
 // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node.
 int numInstructions = 0;
-for (AbstractBlock<?> block : sortedBlocks) {
+for (AbstractBlockBase<?> block : sortedBlocks) {
 numInstructions += ir.getLIRforBlock(block).size();
 }
 // initialize with correct length
 opIdToInstructionMap = new LIRInstruction[numInstructions];
-opIdToBlockMap = new AbstractBlock<?>[numInstructions];
+opIdToBlockMap = new AbstractBlockBase<?>[numInstructions];
 int opId = 0;
 int index = 0;
-for (AbstractBlock<?> block : sortedBlocks) {
+for (AbstractBlockBase<?> block : sortedBlocks) {
 blockData.put(block, new BlockData());
 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
 int numInst = instructions.size();
 int liveSize = liveSetSize();
 intervalInLoop = new BitMap2D(operandSize(), numLoops());
 // iterate all blocks
-for (final AbstractBlock<?> block : sortedBlocks) {
+for (final AbstractBlockBase<?> block : sortedBlocks) {
 try (Indent indent = Debug.logAndIndent("compute local live sets for block %d", block.getId())) {
 final BitSet liveGen = new BitSet(liveSize);
 final BitSet liveKill = new BitSet(liveSize);
 liveKill.set(operandNumber(operand));
 }
 }
 }
-private void verifyInput(AbstractBlock<?> block, BitSet liveKill, Value operand) {
+private void verifyInput(AbstractBlockBase<?> block, BitSet liveKill, Value 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.
 try (Indent indent2 = Debug.logAndIndent("new iteration %d", iterationCount)) {
 // iterate all blocks in reverse order
 for (int i = numBlocks - 1; i >= 0; i--) {
-AbstractBlock<?> block = blockAt(i);
+AbstractBlockBase<?> block = blockAt(i);
 BlockData blockSets = blockData.get(block);
 changeOccurredInBlock = false;
 // liveOut(block) is the union of liveIn(sux), for successors sux of block
 int n = block.getSuccessorCount();
 if (n > 0) {
 liveOut.clear();
 // block has successors
 if (n > 0) {
-for (AbstractBlock<?> successor : block.getSuccessors()) {
+for (AbstractBlockBase<?> successor : block.getSuccessors()) {
 liveOut.or(blockData.get(successor).liveIn);
 }
 }
 if (!blockSets.liveOut.equals(liveOut)) {
 if (DetailedAsserts.getValue()) {
 verifyLiveness();
 }
 // check that the liveIn set of the first block is empty
-AbstractBlock<?> startBlock = ir.getControlFlowGraph().getStartBlock();
+AbstractBlockBase<?> startBlock = ir.getControlFlowGraph().getStartBlock();
 if (blockData.get(startBlock).liveIn.cardinality() != 0) {
 if (DetailedAsserts.getValue()) {
 reportFailure(numBlocks);
 }
 // bailout if this occurs in product mode.
 operand = interval.operand;
 valueForOperandFromDebugContext = getSourceForOperandFromDebugContext(operand);
 }
 try (Indent indent2 = Debug.logAndIndent("---- Detailed information for var %d; operand=%s; node=%s ----", operandNum, operand, valueForOperandFromDebugContext)) {
-Deque<AbstractBlock<?>> definedIn = new ArrayDeque<>();
+Deque<AbstractBlockBase<?>> definedIn = new ArrayDeque<>();
-HashSet<AbstractBlock<?>> usedIn = new HashSet<>();
+HashSet<AbstractBlockBase<?>> usedIn = new HashSet<>();
-for (AbstractBlock<?> block : sortedBlocks) {
+for (AbstractBlockBase<?> block : sortedBlocks) {
 if (blockData.get(block).liveGen.get(operandNum)) {
 usedIn.add(block);
 try (Indent indent3 = Debug.logAndIndent("used in block B%d", block.getId())) {
 for (LIRInstruction ins : ir.getLIRforBlock(block)) {
 try (Indent indent4 = Debug.logAndIndent("%d: %s", ins.id(), ins)) {
 }
 int[] hitCount = new int[numBlocks];
 while (!definedIn.isEmpty()) {
-AbstractBlock<?> block = definedIn.removeFirst();
+AbstractBlockBase<?> block = definedIn.removeFirst();
 usedIn.remove(block);
-for (AbstractBlock<?> successor : block.getSuccessors()) {
+for (AbstractBlockBase<?> successor : block.getSuccessors()) {
 if (successor.isLoopHeader()) {
 if (!block.isLoopEnd()) {
 definedIn.add(successor);
 }
 } else {
 }
 }
 }
 }
 try (Indent indent3 = Debug.logAndIndent("**** offending usages are in: ")) {
-for (AbstractBlock<?> block : usedIn) {
+for (AbstractBlockBase<?> block : usedIn) {
 Debug.log("B%d", block.getId());
 }
 }
 }
 }
 }
 private void verifyLiveness() {
 // check that fixed intervals are not live at block boundaries
 // (live set must be empty at fixed intervals)
-for (AbstractBlock<?> block : sortedBlocks) {
+for (AbstractBlockBase<?> block : sortedBlocks) {
 for (int j = 0; j <= maxRegisterNumber(); j++) {
 assert !blockData.get(block).liveIn.get(j) : "liveIn  set of fixed register must be empty";
 assert !blockData.get(block).liveOut.get(j) : "liveOut set of fixed register must be empty";
 assert !blockData.get(block).liveGen.get(j) : "liveGen set of fixed register must be empty";
 }
 Register[] callerSaveRegs = frameMapBuilder.getRegisterConfig().getCallerSaveRegisters();
 // iterate all blocks in reverse order
 for (int i = blockCount() - 1; i >= 0; i--) {
-AbstractBlock<?> block = blockAt(i);
+AbstractBlockBase<?> block = blockAt(i);
 try (Indent indent2 = Debug.logAndIndent("handle block %d", block.getId())) {
 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
 final int blockFrom = getFirstLirInstructionId(block);
 int blockTo = getLastLirInstructionId(block);
 }
 throw new BailoutException("LinearScan: interval is null");
 }
-Interval intervalAtBlockBegin(AbstractBlock<?> block, int operandNumber) {
+Interval intervalAtBlockBegin(AbstractBlockBase<?> block, int operandNumber) {
 return splitChildAtOpId(intervalFor(operandNumber), getFirstLirInstructionId(block), LIRInstruction.OperandMode.DEF);
 }
-Interval intervalAtBlockEnd(AbstractBlock<?> block, int operandNumber) {
+Interval intervalAtBlockEnd(AbstractBlockBase<?> block, int operandNumber) {
 return splitChildAtOpId(intervalFor(operandNumber), getLastLirInstructionId(block) + 1, LIRInstruction.OperandMode.DEF);
 }
-void resolveCollectMappings(AbstractBlock<?> fromBlock, AbstractBlock<?> toBlock, MoveResolver moveResolver) {
+void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, MoveResolver moveResolver) {
 assert moveResolver.checkEmpty();
 int numOperands = operandSize();
 BitSet liveAtEdge = blockData.get(toBlock).liveIn;
 moveResolver.addMapping(fromInterval, toInterval);
 }
 }
 }
-void resolveFindInsertPos(AbstractBlock<?> fromBlock, AbstractBlock<?> toBlock, MoveResolver moveResolver) {
+void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, MoveResolver moveResolver) {
 if (fromBlock.getSuccessorCount() <= 1) {
 Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId());
 List<LIRInstruction> instructions = ir.getLIRforBlock(fromBlock);
 LIRInstruction instr = instructions.get(instructions.size() - 1);
 // 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 (AbstractBlock<?> predecessor : toBlock.getPredecessors()) {
+for (AbstractBlockBase<?> predecessor : toBlock.getPredecessors()) {
 assert fromBlock == predecessor : "all critical edges must be broken";
 }
 }
 moveResolver.setInsertPosition(ir.getLIRforBlock(toBlock), 1);
 int numBlocks = blockCount();
 MoveResolver moveResolver = new MoveResolver(this);
 BitSet blockCompleted = new BitSet(numBlocks);
 BitSet alreadyResolved = new BitSet(numBlocks);
-for (AbstractBlock<?> block : sortedBlocks) {
+for (AbstractBlockBase<?> block : sortedBlocks) {
 // check if block has only one predecessor and only one successor
 if (block.getPredecessorCount() == 1 && block.getSuccessorCount() == 1) {
 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
 assert instructions.get(0) instanceof StandardOp.LabelOp : "block must start with label";
 assert instructions.get(instructions.size() - 1) instanceof StandardOp.JumpOp : "block with successor must end with unconditional jump";
 // check if block is empty (only label and branch)
 if (instructions.size() == 2) {
-AbstractBlock<?> pred = block.getPredecessors().iterator().next();
+AbstractBlockBase<?> pred = block.getPredecessors().iterator().next();
-AbstractBlock<?> sux = block.getSuccessors().iterator().next();
+AbstractBlockBase<?> sux = block.getSuccessors().iterator().next();
 // prevent optimization of two consecutive blocks
 if (!blockCompleted.get(pred.getLinearScanNumber()) && !blockCompleted.get(sux.getLinearScanNumber())) {
 Debug.log(" optimizing empty block B%d (pred: B%d, sux: B%d)", block.getId(), pred.getId(), sux.getId());
 }
 }
 }
 }
-for (AbstractBlock<?> fromBlock : sortedBlocks) {
+for (AbstractBlockBase<?> fromBlock : sortedBlocks) {
 if (!blockCompleted.get(fromBlock.getLinearScanNumber())) {
 alreadyResolved.clear();
 alreadyResolved.or(blockCompleted);
-for (AbstractBlock<?> toBlock : fromBlock.getSuccessors()) {
+for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) {
 // check for duplicate edges between the same blocks (can happen with switch
 // blocks)
 if (!alreadyResolved.get(toBlock.getLinearScanNumber())) {
 Debug.log("processing edge between B%d and B%d", fromBlock.getId(), toBlock.getId());
 Interval interval = intervalFor(operand);
 assert interval != null : "interval must exist";
 if (opId != -1) {
 if (DetailedAsserts.getValue()) {
-AbstractBlock<?> block = blockForId(opId);
+AbstractBlockBase<?> block = blockForId(opId);
 if (block.getSuccessorCount() <= 1 && opId == getLastLirInstructionId(block)) {
 // 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.
 if (isVirtualStackSlot(operand)) {
 return operand;
 }
 int tempOpId = op.id();
 OperandMode mode = OperandMode.USE;
-AbstractBlock<?> block = blockForId(tempOpId);
+AbstractBlockBase<?> block = blockForId(tempOpId);
 if (block.getSuccessorCount() == 1 && tempOpId == getLastLirInstructionId(block)) {
 // 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
 }
 }
 private void assignLocations() {
 try (Indent indent = Debug.logAndIndent("assign locations")) {
-for (AbstractBlock<?> block : sortedBlocks) {
+for (AbstractBlockBase<?> block : sortedBlocks) {
 try (Indent indent2 = Debug.logAndIndent("assign locations in block B%d", block.getId())) {
 assignLocations(ir.getLIRforBlock(block));
 }
 }
 }
 private void optimizeSpillPosition() {
 LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[ir.linearScanOrder().size()];
 for (Interval interval : intervals) {
 if (interval != null && interval.isSplitParent() && interval.spillState() == SpillState.SpillInDominator) {
-AbstractBlock<?> defBlock = blockForId(interval.spillDefinitionPos());
+AbstractBlockBase<?> defBlock = blockForId(interval.spillDefinitionPos());
-AbstractBlock<?> spillBlock = null;
+AbstractBlockBase<?> spillBlock = null;
 Interval firstSpillChild = null;
 try (Indent indent = Debug.logAndIndent("interval %s (%s)", interval, defBlock)) {
 for (Interval splitChild : interval.getSplitChildren()) {
 if (isStackSlotValue(splitChild.location())) {
 if (firstSpillChild == null || splitChild.from() < firstSpillChild.from()) {
 firstSpillChild = splitChild;
 } else {
 assert firstSpillChild.from() < splitChild.from();
 }
 // iterate all blocks where the interval has use positions
-for (AbstractBlock<?> splitBlock : blocksForInterval(splitChild)) {
+for (AbstractBlockBase<?> splitBlock : blocksForInterval(splitChild)) {
 if (dominates(defBlock, splitBlock)) {
 Debug.log("Split interval %s, block %s", splitChild, splitBlock);
 if (spillBlock == null) {
 spillBlock = splitBlock;
 } else {
 * If the spill block is the begin of the first split child (aka the value
 * is on the stack) spill in the dominator.
 */
 assert firstSpillChild != null;
 if (!defBlock.equals(spillBlock) && spillBlock.equals(blockForId(firstSpillChild.from()))) {
-AbstractBlock<?> dom = spillBlock.getDominator();
+AbstractBlockBase<?> dom = spillBlock.getDominator();
 Debug.log("Spill block (%s) is the beginning of a spill child -> use dominator (%s)", spillBlock, dom);
 spillBlock = dom;
 }
 if (!defBlock.equals(spillBlock)) {
 }
 }
 }
 /**
-* Iterate over all {@link AbstractBlock blocks} of an interval.
+* Iterate over all {@link AbstractBlockBase blocks} of an interval.
 */
-private class IntervalBlockIterator implements Iterator<AbstractBlock<?>> {
+private class IntervalBlockIterator implements Iterator<AbstractBlockBase<?>> {
 Range range;
-AbstractBlock<?> block;
+AbstractBlockBase<?> block;
 public IntervalBlockIterator(Interval interval) {
 range = interval.first();
 block = blockForId(range.from);
 }
-public AbstractBlock<?> next() {
+public AbstractBlockBase<?> next() {
-AbstractBlock<?> currentBlock = block;
+AbstractBlockBase<?> currentBlock = block;
 int nextBlockIndex = block.getLinearScanNumber() + 1;
 if (nextBlockIndex < sortedBlocks.size()) {
 block = sortedBlocks.get(nextBlockIndex);
 if (range.to <= getFirstLirInstructionId(block)) {
 range = range.next;
 public boolean hasNext() {
 return block != null;
 }
 }
-private Iterable<AbstractBlock<?>> blocksForInterval(Interval interval) {
+private Iterable<AbstractBlockBase<?>> blocksForInterval(Interval interval) {
-return new Iterable<AbstractBlock<?>>() {
+return new Iterable<AbstractBlockBase<?>>() {
-public Iterator<AbstractBlock<?>> iterator() {
+public Iterator<AbstractBlockBase<?>> iterator() {
 return new IntervalBlockIterator(interval);
 }
 };
 }
-private static AbstractBlock<?> moveSpillOutOfLoop(AbstractBlock<?> defBlock, AbstractBlock<?> spillBlock) {
+private static AbstractBlockBase<?> moveSpillOutOfLoop(AbstractBlockBase<?> defBlock, AbstractBlockBase<?> spillBlock) {
 int defLoopDepth = defBlock.getLoopDepth();
-for (AbstractBlock<?> block = spillBlock.getDominator(); !defBlock.equals(block); block = block.getDominator()) {
+for (AbstractBlockBase<?> block = spillBlock.getDominator(); !defBlock.equals(block); block = block.getDominator()) {
 assert block != null : "spill block not dominated by definition block?";
 if (block.getLoopDepth() <= defLoopDepth) {
 assert block.getLoopDepth() == defLoopDepth : "Cannot spill an interval outside of the loop where it is defined!";
 return block;
 }
 }
 }
 try (Indent indent2 = Debug.logAndIndent("Basic Blocks")) {
 for (int i = 0; i < blockCount(); i++) {
-AbstractBlock<?> block = blockAt(i);
+AbstractBlockBase<?> block = blockAt(i);
 Debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop());
 }
 }
 }
 }
 // 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 (AbstractBlock<?> block : sortedBlocks) {
+for (AbstractBlockBase<?> block : sortedBlocks) {
 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
 for (int j = 0; j < instructions.size(); j++) {
 LIRInstruction op = instructions.get(j);

Mercurial > hg > truffle

comparison graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java @ 19560:4d70d150944f