# HG changeset patch # User Josef Eisl # Date 1394618787 -3600 # Node ID 42013bd831d614862352b15723e683185f0c8453 # Parent 1a9dca3c3fd75d9143ff8be32eea935a82ac22c5 Make LinearScan use AbstractBlock. diff -r 1a9dca3c3fd7 -r 42013bd831d6 graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java --- 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 > PriorityQueue initializeWorklist(T startBlock, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { - PriorityQueue result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator(nodeProbabilities)); + PriorityQueue result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator(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 order, int expectedBlockCount) { + private static boolean checkOrder(List> 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; } diff -r 1a9dca3c3fd7 -r 42013bd831d6 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java --- 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 sortedBlocks; + final List> 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 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 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 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 definedIn = new ArrayDeque<>(); - HashSet usedIn = new HashSet<>(); - for (Block block : sortedBlocks) { + Deque> definedIn = new ArrayDeque<>(); + HashSet> 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 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 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 diff -r 1a9dca3c3fd7 -r 42013bd831d6 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java --- 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"; diff -r 1a9dca3c3fd7 -r 42013bd831d6 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/RegisterVerifier.java --- 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 workList; // all blocks that must be processed + List> workList; // all blocks that must be processed ArrayMap 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) { diff -r 1a9dca3c3fd7 -r 42013bd831d6 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java --- 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 lir(Block block) { + public List lir(AbstractBlock block) { return lirInstructions.get(block); } diff -r 1a9dca3c3fd7 -r 42013bd831d6 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/AbstractBlock.java --- 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 { +public interface AbstractBlock> { int getId(); diff -r 1a9dca3c3fd7 -r 42013bd831d6 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/BlockMap.java --- 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; } }