Mercurial > hg > graal-compiler
changeset 14152:42013bd831d6
Make LinearScan use AbstractBlock.
author | Josef Eisl <josef.eisl@jku.at> |
---|---|
date | Wed, 12 Mar 2014 11:06:27 +0100 |
parents | 1a9dca3c3fd7 |
children | e328f28f7401 |
files | graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/RegisterVerifier.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/AbstractBlock.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/BlockMap.java |
diffstat | 7 files changed, 64 insertions(+), 63 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Wed Mar 12 10:19:15 2014 +0100 +++ b/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Wed Mar 12 11:06:27 2014 +0100 @@ -113,9 +113,8 @@ /** * Initializes the priority queue used for the work list of blocks and adds the start block. */ - @SuppressWarnings("unchecked") private static <T extends AbstractBlock<T>> PriorityQueue<T> initializeWorklist(T startBlock, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { - PriorityQueue<T> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator(nodeProbabilities)); + PriorityQueue<T> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator<T>(nodeProbabilities)); result.add(startBlock); visitedBlocks.set(startBlock.getId()); return result; @@ -233,14 +232,14 @@ * Skip the loop header block if the loop consists of more than one block and it has only a * single loop end block. */ - private static boolean skipLoopHeader(AbstractBlock block) { + private static boolean skipLoopHeader(AbstractBlock<?> block) { return (block.isLoopHeader() && !block.isLoopEnd() && block.getLoop().loopBegin().loopEnds().count() == 1); } /** * Checks that the ordering contains the expected number of blocks. */ - private static boolean checkOrder(List<? extends AbstractBlock> order, int expectedBlockCount) { + private static boolean checkOrder(List<? extends AbstractBlock<?>> order, int expectedBlockCount) { assert order.size() == expectedBlockCount : String.format("Number of blocks in ordering (%d) does not match expected block count (%d)", order.size(), expectedBlockCount); return true; }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java Wed Mar 12 10:19:15 2014 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java Wed Mar 12 11:06:27 2014 +0100 @@ -104,7 +104,7 @@ /** * List of blocks in linear-scan order. This is only correct as long as the CFG does not change. */ - final List<Block> sortedBlocks; + final List<? extends AbstractBlock<?>> sortedBlocks; /** * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals. @@ -139,7 +139,7 @@ * containing the instruction. Entries should be retrieved with {@link #blockForId(int)} as the * id is not simply an index into this array. */ - Block[] opIdToBlockMap; + AbstractBlock<?>[] opIdToBlockMap; /** * Bit set for each variable that is contained in each loop. @@ -171,13 +171,13 @@ this.blockData = new BlockMap<>(ir.getControlFlowGraph()); } - public int getFirstLirInstructionId(Block block) { + public int getFirstLirInstructionId(AbstractBlock<?> block) { int result = ir.lir(block).get(0).id(); assert result >= 0; return result; } - public int getLastLirInstructionId(Block block) { + public int getLastLirInstructionId(AbstractBlock<?> block) { List<LIRInstruction> instructions = ir.lir(block); int result = instructions.get(instructions.size() - 1).id(); assert result >= 0; @@ -321,7 +321,7 @@ return sortedBlocks.size(); } - Block blockAt(int index) { + AbstractBlock<?> blockAt(int index) { return sortedBlocks.get(index); } @@ -393,7 +393,7 @@ * @param opId an instruction {@linkplain LIRInstruction#id id} * @return the block containing the instruction denoted by {@code opId} */ - Block blockForId(int opId) { + AbstractBlock<?> blockForId(int opId) { assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range"; return opIdToBlockMap[opIdToIndex(opId)]; } @@ -516,7 +516,7 @@ } LIRInsertionBuffer insertionBuffer = new LIRInsertionBuffer(); - for (Block block : sortedBlocks) { + for (AbstractBlock<?> block : sortedBlocks) { List<LIRInstruction> instructions = ir.lir(block); int numInst = instructions.size(); @@ -623,7 +623,7 @@ // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node. int numInstructions = 0; - for (Block block : sortedBlocks) { + for (AbstractBlock<?> block : sortedBlocks) { numInstructions += ir.lir(block).size(); } @@ -633,7 +633,7 @@ int opId = 0; int index = 0; - for (Block block : sortedBlocks) { + for (AbstractBlock<?> block : sortedBlocks) { blockData.put(block, new BlockData()); List<LIRInstruction> instructions = ir.lir(block); @@ -675,7 +675,7 @@ intervalInLoop = new BitMap2D(operandSize(), numLoops()); // iterate all blocks - for (final Block block : sortedBlocks) { + for (final AbstractBlock<?> block : sortedBlocks) { Indent indent = Debug.logAndIndent("compute local live sets for block %d", block.getId()); final BitSet liveGen = new BitSet(liveSize); @@ -779,7 +779,7 @@ } } - private void verifyInput(Block block, BitSet liveKill, Value operand) { + private void verifyInput(AbstractBlock<?> 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. @@ -813,7 +813,7 @@ // iterate all blocks in reverse order for (int i = numBlocks - 1; i >= 0; i--) { - Block block = blockAt(i); + AbstractBlock<?> block = blockAt(i); BlockData blockSets = blockData.get(block); changeOccurredInBlock = false; @@ -824,7 +824,7 @@ // block has successors if (n > 0) { liveOut.clear(); - for (Block successor : block.getSuccessors()) { + for (AbstractBlock<?> successor : block.getSuccessors()) { liveOut.or(blockData.get(successor).liveIn); } } else { @@ -914,9 +914,9 @@ Value operand = operandFor(operandNum); final Indent indent2 = Debug.logAndIndent("---- Detailed information for var %d; operand=%s; node=%s ----", operandNum, operand, getValueForOperandFromDebugContext(operand)); - Deque<Block> definedIn = new ArrayDeque<>(); - HashSet<Block> usedIn = new HashSet<>(); - for (Block block : sortedBlocks) { + Deque<AbstractBlock<?>> definedIn = new ArrayDeque<>(); + HashSet<AbstractBlock<?>> usedIn = new HashSet<>(); + for (AbstractBlock<?> block : sortedBlocks) { if (blockData.get(block).liveGen.get(operandNum)) { usedIn.add(block); try (Indent indent3 = Debug.logAndIndent("used in block B%d", block.getId())) { @@ -947,9 +947,9 @@ int[] hitCount = new int[numBlocks]; while (!definedIn.isEmpty()) { - Block block = definedIn.removeFirst(); + AbstractBlock<?> block = definedIn.removeFirst(); usedIn.remove(block); - for (Block successor : block.getSuccessors()) { + for (AbstractBlock<?> successor : block.getSuccessors()) { if (successor.isLoopHeader()) { if (!block.isLoopEnd()) { definedIn.add(successor); @@ -962,7 +962,7 @@ } } try (Indent indent3 = Debug.logAndIndent("**** offending usages are in: ")) { - for (Block block : usedIn) { + for (AbstractBlock<?> block : usedIn) { Debug.log("B%d", block.getId()); } } @@ -975,7 +975,7 @@ private void verifyLiveness() { // check that fixed intervals are not live at block boundaries // (live set must be empty at fixed intervals) - for (Block block : sortedBlocks) { + for (AbstractBlock<?> 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"; @@ -1158,7 +1158,7 @@ // iterate all blocks in reverse order for (int i = blockCount() - 1; i >= 0; i--) { - Block block = blockAt(i); + AbstractBlock<?> block = blockAt(i); Indent indent2 = Debug.logAndIndent("handle block %d", block.getId()); List<LIRInstruction> instructions = ir.lir(block); @@ -1463,14 +1463,14 @@ throw new BailoutException("LinearScan: interval is null"); } - Interval intervalAtBlockBegin(Block block, Value operand) { + Interval intervalAtBlockBegin(AbstractBlock<?> block, Value operand) { assert isVariable(operand) : "register number out of bounds"; assert intervalFor(operand) != null : "no interval found"; return splitChildAtOpId(intervalFor(operand), getFirstLirInstructionId(block), LIRInstruction.OperandMode.DEF); } - Interval intervalAtBlockEnd(Block block, Value operand) { + Interval intervalAtBlockEnd(AbstractBlock<?> block, Value operand) { assert isVariable(operand) : "register number out of bounds"; assert intervalFor(operand) != null : "no interval found"; @@ -1484,7 +1484,7 @@ return splitChildAtOpId(intervalFor(operand), opId, LIRInstruction.OperandMode.USE); } - void resolveCollectMappings(Block fromBlock, Block toBlock, MoveResolver moveResolver) { + void resolveCollectMappings(AbstractBlock<?> fromBlock, AbstractBlock<?> toBlock, MoveResolver moveResolver) { assert moveResolver.checkEmpty(); int numOperands = operandSize(); @@ -1506,7 +1506,7 @@ } } - void resolveFindInsertPos(Block fromBlock, Block toBlock, MoveResolver moveResolver) { + void resolveFindInsertPos(AbstractBlock<?> fromBlock, AbstractBlock<?> toBlock, MoveResolver moveResolver) { if (fromBlock.getSuccessorCount() <= 1) { Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId()); @@ -1529,7 +1529,7 @@ // 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 (Block predecessor : toBlock.getPredecessors()) { + for (AbstractBlock<?> predecessor : toBlock.getPredecessors()) { assert fromBlock == predecessor : "all critical edges must be broken"; } } @@ -1550,7 +1550,7 @@ BitSet blockCompleted = new BitSet(numBlocks); BitSet alreadyResolved = new BitSet(numBlocks); - for (Block block : sortedBlocks) { + for (AbstractBlock<?> block : sortedBlocks) { // check if block has only one predecessor and only one successor if (block.getPredecessorCount() == 1 && block.getSuccessorCount() == 1) { @@ -1560,8 +1560,8 @@ // check if block is empty (only label and branch) if (instructions.size() == 2) { - Block pred = block.getFirstPredecessor(); - Block sux = block.getFirstSuccessor(); + AbstractBlock<?> pred = block.getPredecessors().iterator().next(); + AbstractBlock<?> sux = block.getSuccessors().iterator().next(); // prevent optimization of two consecutive blocks if (!blockCompleted.get(pred.getLinearScanNumber()) && !blockCompleted.get(sux.getLinearScanNumber())) { @@ -1581,12 +1581,12 @@ } } - for (Block fromBlock : sortedBlocks) { + for (AbstractBlock<?> fromBlock : sortedBlocks) { if (!blockCompleted.get(fromBlock.getLinearScanNumber())) { alreadyResolved.clear(); alreadyResolved.or(blockCompleted); - for (Block toBlock : fromBlock.getSuccessors()) { + for (AbstractBlock<?> toBlock : fromBlock.getSuccessors()) { // check for duplicate edges between the same blocks (can happen with switch // blocks) @@ -1630,7 +1630,7 @@ if (opId != -1) { if (DetailedAsserts.getValue()) { - Block block = blockForId(opId); + AbstractBlock<?> 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 @@ -1744,7 +1744,7 @@ public Value doValue(Value operand) { int tempOpId = op.id(); OperandMode mode = OperandMode.USE; - Block block = blockForId(tempOpId); + AbstractBlock<?> 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 @@ -1755,7 +1755,7 @@ final LIRInstruction instr = ir.lir(block).get(ir.lir(block).size() - 1); if (instr instanceof StandardOp.JumpOp) { if (blockData.get(block).liveOut.get(operandNumber(operand))) { - tempOpId = getFirstLirInstructionId(block.getFirstSuccessor()); + tempOpId = getFirstLirInstructionId(block.getSuccessors().iterator().next()); mode = OperandMode.DEF; } } @@ -1844,7 +1844,7 @@ private void assignLocations() { IntervalWalker iw = initIntervalWalker(IS_STACK_INTERVAL); try (Indent indent = Debug.logAndIndent("assign locations")) { - for (Block block : sortedBlocks) { + for (AbstractBlock<?> block : sortedBlocks) { try (Indent indent2 = Debug.logAndIndent("assign locations in block B%d", block.getId())) { assignLocations(ir.lir(block), iw); } @@ -1921,7 +1921,7 @@ try (Indent indent2 = Debug.logAndIndent("Basic Blocks")) { for (int i = 0; i < blockCount(); i++) { - Block block = blockAt(i); + AbstractBlock<?> block = blockAt(i); Debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop()); } } @@ -2059,7 +2059,7 @@ otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1); IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals); - for (Block block : sortedBlocks) { + for (AbstractBlock<?> block : sortedBlocks) { List<LIRInstruction> instructions = ir.lir(block); for (int j = 0; j < instructions.size(); j++) { @@ -2097,7 +2097,7 @@ void verifyConstants() { try (Indent indent = Debug.logAndIndent("verifying that unpinned constants are not alive across block boundaries")) { - for (Block block : sortedBlocks) { + for (AbstractBlock<?> block : sortedBlocks) { BitSet liveAtEdge = blockData.get(block).liveIn; // visit all operands where the liveAtEdge bit is set
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java Wed Mar 12 10:19:15 2014 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java Wed Mar 12 11:06:27 2014 +0100 @@ -25,6 +25,7 @@ import static com.oracle.graal.api.code.CodeUtil.*; import static com.oracle.graal.api.code.ValueUtil.*; import static com.oracle.graal.lir.LIRValueUtil.*; + import java.util.*; import com.oracle.graal.api.code.*; @@ -57,11 +58,11 @@ return allocator.blockCount(); } - Block blockAt(int idx) { + AbstractBlock<?> blockAt(int idx) { return allocator.blockAt(idx); } - Block blockOfOpWithId(int opId) { + AbstractBlock<?> blockOfOpWithId(int opId) { return allocator.blockForId(opId); } @@ -235,7 +236,7 @@ // optimized away later in assignRegNums int opId = (operandId + 1) & ~1; - Block opBlock = allocator.blockForId(opId); + AbstractBlock<?> opBlock = allocator.blockForId(opId); assert opId > 0 && allocator.blockForId(opId - 2) == opBlock : "cannot insert move at block boundary"; // calculate index of instruction inside instruction list of current block @@ -259,7 +260,7 @@ moveResolver.addMapping(srcIt, dstIt); } - int findOptimalSplitPos(Block minBlock, Block maxBlock, int maxSplitPos) { + int findOptimalSplitPos(AbstractBlock<?> minBlock, AbstractBlock<?> maxBlock, int maxSplitPos) { int fromBlockNr = minBlock.getLinearScanNumber(); int toBlockNr = maxBlock.getLinearScanNumber(); @@ -276,7 +277,7 @@ int minLoopDepth = maxBlock.getLoopDepth(); for (int i = toBlockNr - 1; i >= fromBlockNr; i--) { - Block cur = blockAt(i); + AbstractBlock<?> cur = blockAt(i); if (cur.getLoopDepth() < minLoopDepth) { // block with lower loop-depth found . split at the end of this block @@ -304,13 +305,13 @@ // beginning of a block, then minSplitPos is also a possible split position. // Use the block before as minBlock, because then minBlock.lastLirInstructionId() + 2 == // minSplitPos - Block minBlock = allocator.blockForId(minSplitPos - 1); + AbstractBlock<?> minBlock = allocator.blockForId(minSplitPos - 1); // reason for using maxSplitPos - 1: otherwise there would be an assert on failure // when an interval ends at the end of the last block of the method // (in this case, maxSplitPos == allocator().maxLirOpId() + 2, and there is no // block at this opId) - Block maxBlock = allocator.blockForId(maxSplitPos - 1); + AbstractBlock<?> maxBlock = allocator.blockForId(maxSplitPos - 1); assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order"; if (minBlock == maxBlock) { @@ -348,7 +349,7 @@ // Desired result: uses tagged as shouldHaveRegister inside a loop cause // a reloading // of the interval (normally, only mustHaveRegister causes a reloading) - Block loopBlock = allocator.blockForId(loopEndPos); + AbstractBlock<?> loopBlock = allocator.blockForId(loopEndPos); Debug.log("interval is used in loop that ends in block B%d, so trying to move maxBlock back from B%d to B%d", loopBlock.getId(), maxBlock.getId(), loopBlock.getId()); assert loopBlock != minBlock : "loopBlock and minBlock must be different because block boundary is needed between";
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/RegisterVerifier.java Wed Mar 12 10:19:15 2014 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/RegisterVerifier.java Wed Mar 12 11:06:27 2014 +0100 @@ -23,6 +23,7 @@ package com.oracle.graal.compiler.alloc; import static com.oracle.graal.api.code.ValueUtil.*; + import java.util.*; import com.oracle.graal.api.code.*; @@ -39,7 +40,7 @@ final class RegisterVerifier { LinearScan allocator; - List<Block> workList; // all blocks that must be processed + List<AbstractBlock<?>> workList; // all blocks that must be processed ArrayMap<Interval[]> savedStates; // saved information of previous check // simplified access to methods of LinearScan @@ -53,15 +54,15 @@ } // accessors - Interval[] stateForBlock(Block block) { + Interval[] stateForBlock(AbstractBlock<?> block) { return savedStates.get(block.getId()); } - void setStateForBlock(Block block, Interval[] savedState) { + void setStateForBlock(AbstractBlock<?> block, Interval[] savedState) { savedStates.put(block.getId(), savedState); } - void addToWorkList(Block block) { + void addToWorkList(AbstractBlock<?> block) { if (!workList.contains(block)) { workList.add(block); } @@ -74,7 +75,7 @@ } - void verify(Block start) { + void verify(AbstractBlock<?> start) { // setup input registers (method arguments) for first block Interval[] inputState = new Interval[stateSize()]; setStateForBlock(start, inputState); @@ -82,14 +83,14 @@ // main loop for verification do { - Block block = workList.get(0); + AbstractBlock<?> block = workList.get(0); workList.remove(0); processBlock(block); } while (!workList.isEmpty()); } - private void processBlock(Block block) { + private void processBlock(AbstractBlock<?> block) { try (Indent indent = Debug.logAndIndent("processBlock B%d", block.getId())) { // must copy state because it is modified Interval[] inputState = copy(stateForBlock(block)); @@ -108,13 +109,13 @@ processOperations(allocator.ir.lir(block), inputState); // iterate all successors - for (Block succ : block.getSuccessors()) { + for (AbstractBlock<?> succ : block.getSuccessors()) { processSuccessor(succ, inputState); } } } - private void processSuccessor(Block block, Interval[] inputState) { + private void processSuccessor(AbstractBlock<?> block, Interval[] inputState) { Interval[] savedState = stateForBlock(block); if (savedState != null) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java Wed Mar 12 10:19:15 2014 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java Wed Mar 12 11:06:27 2014 +0100 @@ -94,7 +94,7 @@ return spillMoveFactory; } - public List<LIRInstruction> lir(Block block) { + public List<LIRInstruction> lir(AbstractBlock<?> block) { return lirInstructions.get(block); }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/AbstractBlock.java Wed Mar 12 10:19:15 2014 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/AbstractBlock.java Wed Mar 12 11:06:27 2014 +0100 @@ -24,7 +24,7 @@ import com.oracle.graal.nodes.*; -public interface AbstractBlock<T extends AbstractBlock> { +public interface AbstractBlock<T extends AbstractBlock<?>> { int getId();
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/BlockMap.java Wed Mar 12 10:19:15 2014 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/BlockMap.java Wed Mar 12 11:06:27 2014 +0100 @@ -31,11 +31,11 @@ data = (T[]) new Object[cfg.getBlocks().length]; } - public T get(Block block) { + public T get(AbstractBlock<?> block) { return data[block.getId()]; } - public void put(Block block, T value) { + public void put(AbstractBlock<?> block, T value) { data[block.getId()] = value; } }