Mercurial > hg > truffle
changeset 7497:0f8c6dbf68be
Code clean up and documentation for ComputeBlockOrder class.
line wrap: on
line diff
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Thu Jan 17 00:41:44 2013 +0100 +++ b/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Thu Jan 17 17:21:16 2013 +0100 @@ -28,173 +28,216 @@ import com.oracle.graal.nodes.cfg.*; /** - * Computes an ordering of the block that can be used by the linear scan register allocator - * and the machine code generator. + * Computes an ordering of the block that can be used by the linear scan register allocator and the machine code + * generator. */ public final class ComputeBlockOrder { - private List<Block> linearScanOrder; - private List<Block> codeEmittingOrder; + + /** + * The initial capacities of the worklists used for iteratively finding the block order. + */ + private static final int INITIAL_WORKLIST_CAPACITY = 10; + + /** + * Divisor used for degrading the probability of the current path versus unscheduled paths at a merge node when + * calculating the linear scan order. A high value means that predecessors of merge nodes are more likely to be + * scheduled before the merge node. + */ + private static final int PENALTY_VERSUS_UNSCHEDULED = 10; + + /** + * Computes the block order used for the linear scan register allocator. + * + * @return sorted list of blocks + */ + public static List<Block> computeLinearScanOrder(int blockCount, Block startBlock) { + List<Block> order = new ArrayList<>(); + BitSet visitedBlocks = new BitSet(blockCount); + PriorityQueue<Block> worklist = initializeWorklist(startBlock, visitedBlocks); + computeLinearScanOrder(order, worklist, visitedBlocks); + assert checkOrder(order, blockCount); + return order; + } + + /** + * Computes the block order used for code emission. + * + * @return sorted list of blocks + */ + public static List<Block> computeCodeEmittingOrder(int blockCount, Block startBlock) { + List<Block> order = new ArrayList<>(); + BitSet visitedBlocks = new BitSet(blockCount); + PriorityQueue<Block> worklist = initializeWorklist(startBlock, visitedBlocks); + computeCodeEmittingOrder(order, worklist, visitedBlocks); + assert checkOrder(order, blockCount); + return order; + } + + /** + * Iteratively adds paths to the code emission block order. + */ + private static void computeCodeEmittingOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks) { + while (!worklist.isEmpty()) { + Block nextImportantPath = worklist.poll(); + addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks); + } + } + + /** + * Iteratively adds paths to the linear scan block order. + */ + private static void computeLinearScanOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks) { + while (!worklist.isEmpty()) { + Block nextImportantPath = worklist.poll(); + addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks); + } + } + + /** + * Initializes the priority queue used for the work list of blocks and adds the start block. + */ + private static PriorityQueue<Block> initializeWorklist(Block startBlock, BitSet visitedBlocks) { + PriorityQueue<Block> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, blockComparator); + result.add(startBlock); + visitedBlocks.set(startBlock.getId()); + return result; + } + + /** + * Add a linear path to the linear scan order greedily following the most likely successor. + */ + private static void addPathToLinearScanOrder(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks) { + block.setLinearScanNumber(order.size()); + order.add(block); + Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks); + enqueueSuccessors(block, worklist, visitedBlocks); + if (mostLikelySuccessor != null) { + if (!mostLikelySuccessor.isLoopHeader() && mostLikelySuccessor.getPredecessors().size() > 1) { + // We are at a merge. Check probabilities of predecessors that are not yet scheduled. + double unscheduledSum = 0.0; + for (Block pred : mostLikelySuccessor.getPredecessors()) { + if (!visitedBlocks.get(pred.getId())) { + unscheduledSum += pred.getBeginNode().probability(); + } + } - private Comparator<Block> blockComparator = new Comparator<Block>() { + if (unscheduledSum > block.getProbability() / PENALTY_VERSUS_UNSCHEDULED) { + // Add this merge only after at least one additional predecessor gets scheduled. + visitedBlocks.clear(mostLikelySuccessor.getId()); + return; + } + } + addPathToLinearScanOrder(mostLikelySuccessor, order, worklist, visitedBlocks); + } + } + + /** + * Add a linear path to the code emission order greedily following the most likely successor. + */ + private static void addPathToCodeEmittingOrder(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks) { + + // Skip loop headers if there is only a single loop end block to make the backward jump be a conditional jump. + if (!skipLoopHeader(block)) { + + // Align unskipped loop headers as they are the target of the backward jump. + if (block.isLoopHeader()) { + block.setAlign(true); + } + addBlock(block, order); + } + + Loop loop = block.getLoop(); + if (block.isLoopEnd() && skipLoopHeader(loop.header)) { + + // This is the only loop end of a skipped loop header. Add the header immediately afterwards. + addBlock(loop.header, order); + + // Make sure the loop successors of the loop header are aligned as they are the target of the backward jump. + for (Block successor : loop.header.getSuccessors()) { + if (successor.getLoopDepth() == block.getLoopDepth()) { + successor.setAlign(true); + } + } + } + + Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks); + enqueueSuccessors(block, worklist, visitedBlocks); + if (mostLikelySuccessor != null) { + addPathToCodeEmittingOrder(mostLikelySuccessor, order, worklist, visitedBlocks); + } + } + + /** + * Adds a block to the ordering. + */ + private static void addBlock(Block header, List<Block> order) { + assert !order.contains(header) : "Cannot insert block twice"; + order.add(header); + } + + /** + * Find the highest likely unvisited successor block of a given block. + */ + private static Block findAndMarkMostLikelySuccessor(Block block, BitSet visitedBlocks) { + Block result = null; + for (Block successor : block.getSuccessors()) { + assert successor.getProbability() >= 0.0 : "Probabilities must be positive"; + if (!visitedBlocks.get(successor.getId()) && successor.getLoopDepth() >= block.getLoopDepth() && (result == null || successor.getProbability() >= result.getProbability())) { + result = successor; + } + } + if (result != null) { + visitedBlocks.set(result.getId()); + } + return result; + } + + /** + * Add successor blocks into the given work list if they are not already marked as visited. + */ + private static void enqueueSuccessors(Block block, PriorityQueue<Block> worklist, BitSet visitedBlocks) { + for (Block successor : block.getSuccessors()) { + if (!visitedBlocks.get(successor.getId())) { + visitedBlocks.set(successor.getId()); + worklist.add(successor); + } + } + } + + /** + * 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(Block 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<Block> 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; + } + + /** + * Comparator for sorting blocks based on loop depth and probability. + */ + private static Comparator<Block> blockComparator = new Comparator<Block>() { + @Override - public int compare(Block o1, Block o2) { + public int compare(Block a, Block b) { // Loop blocks before any loop exit block. - int diff = o2.getLoopDepth() - o1.getLoopDepth(); + int diff = b.getLoopDepth() - a.getLoopDepth(); if (diff != 0) { return diff; } // Blocks with high probability before blocks with low probability. - if (o1.getBeginNode().probability() > o2.getBeginNode().probability()) { + if (a.getProbability() > b.getProbability()) { return -1; } else { return 1; } - }}; - - public ComputeBlockOrder(int maxBlockId, @SuppressWarnings("unused") int loopCount, Block startBlock, @SuppressWarnings("unused") boolean reorderLoops) { - - List<Block> newLinearScanOrder = new ArrayList<>(); - List<Block> order = new ArrayList<>(); - PriorityQueue<Block> worklist = new PriorityQueue<>(10, blockComparator); - BitSet orderedBlocks = new BitSet(maxBlockId); - orderedBlocks.set(startBlock.getId()); - worklist.add(startBlock); - computeCodeEmittingOrder(order, worklist, orderedBlocks); - codeEmittingOrder = order; - - orderedBlocks.clear(); - orderedBlocks.set(startBlock.getId()); - worklist.add(startBlock); - computeNewLinearScanOrder(newLinearScanOrder, worklist, orderedBlocks); - - assert order.size() == newLinearScanOrder.size() : codeEmittingOrder.size() + " vs " + newLinearScanOrder.size(); - linearScanOrder = newLinearScanOrder; - } - - private void computeCodeEmittingOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet orderedBlocks) { - while (!worklist.isEmpty()) { - Block nextImportantPath = worklist.poll(); - addImportantPath(nextImportantPath, order, worklist, orderedBlocks); } - } - - private void computeNewLinearScanOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet orderedBlocks) { - while (!worklist.isEmpty()) { - Block nextImportantPath = worklist.poll(); - addImportantLinearScanOrderPath(nextImportantPath, order, worklist, orderedBlocks); - } - } - - private void addImportantLinearScanOrderPath(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet orderedBlocks) { - order.add(block); - - Block bestSucc = null; - double bestSuccProb = 0; - - for (Block succ : block.getSuccessors()) { - if (!orderedBlocks.get(succ.getId()) && succ.getLoopDepth() >= block.getLoopDepth()) { - double curProb = succ.getBeginNode().probability(); - if (curProb >= bestSuccProb) { - bestSuccProb = curProb; - bestSucc = succ; - } - assert curProb >= 0 : curProb; - } - } - - for (Block succ : block.getSuccessors()) { - if (!orderedBlocks.get(succ.getId())) { - if (succ != bestSucc) { - orderedBlocks.set(succ.getId()); - worklist.add(succ); - } - } - } - - if (bestSucc != null) { - if (!bestSucc.isLoopHeader() && bestSucc.getPredecessors().size() > 1) { - // We are at a merge. Check probabilities of predecessors that are not yet scheduled. - double unscheduledSum = 0.0; - double scheduledSum = 0.0; - for (Block pred : bestSucc.getPredecessors()) { - if (!orderedBlocks.get(pred.getId())) { - unscheduledSum += pred.getBeginNode().probability(); - } else { - scheduledSum += pred.getBeginNode().probability(); - } - } - - if (unscheduledSum > 0.0 && unscheduledSum > scheduledSum / 10) { - return; - } - } - orderedBlocks.set(bestSucc.getId()); - addImportantLinearScanOrderPath(bestSucc, order, worklist, orderedBlocks); - } - } - - private void addImportantPath(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet orderedBlocks) { - if (!skipLoopHeader(block)) { - if (block.isLoopHeader()) { - block.align = true; - } - order.add(block); - } - if (block.isLoopEnd() && skipLoopHeader(block.getLoop().header)) { - order.add(block.getLoop().header); - for (Block succ : block.getLoop().header.getSuccessors()) { - if (succ.getLoopDepth() == block.getLoopDepth()) { - succ.align = true; - } - } - } - Block bestSucc = null; - double bestSuccProb = 0; - - for (Block succ : block.getSuccessors()) { - if (!orderedBlocks.get(succ.getId()) && succ.getLoopDepth() >= block.getLoopDepth()) { - double curProb = succ.getBeginNode().probability(); - if (curProb >= bestSuccProb) { - bestSuccProb = curProb; - bestSucc = succ; - } - assert curProb >= 0 : curProb; - } - } - - for (Block succ : block.getSuccessors()) { - if (!orderedBlocks.get(succ.getId())) { - if (succ != bestSucc) { - orderedBlocks.set(succ.getId()); - worklist.add(succ); - } - } - } - - if (bestSucc != null) { - orderedBlocks.set(bestSucc.getId()); - addImportantPath(bestSucc, order, worklist, orderedBlocks); - } - } - - private static boolean skipLoopHeader(Block bestSucc) { - return (bestSucc.isLoopHeader() && !bestSucc.isLoopEnd() && bestSucc.getLoop().loopBegin().loopEnds().count() == 1); - } - - /** - * Returns the block order used for the linear scan register allocator. - * @return list of sorted blocks - */ - public List<Block> linearScanOrder() { - return linearScanOrder; - } - - /** - * Returns the block order used for machine code generation. - * @return list of sorted blocks2222 - */ - public List<Block> codeEmittingOrder() { - return codeEmittingOrder; - } + }; }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Thu Jan 17 00:41:44 2013 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Thu Jan 17 17:21:16 2013 +0100 @@ -210,7 +210,7 @@ final Block[] blocks = schedule.getCFG().getBlocks(); final Block startBlock = schedule.getCFG().getStartBlock(); assert startBlock != null; - assert startBlock.numberOfPreds() == 0; + assert startBlock.getPredecessorCount() == 0; new ComputeProbabilityPhase().apply(graph); @@ -218,14 +218,8 @@ @Override public LIR call() { - ComputeBlockOrder clso = new ComputeBlockOrder(blocks.length, schedule.getCFG().getLoops().length, startBlock, GraalOptions.OptReorderLoops); - List<Block> linearScanOrder = clso.linearScanOrder(); - List<Block> codeEmittingOrder = clso.codeEmittingOrder(); - - int z = 0; - for (Block b : linearScanOrder) { - b.linearScanNumber = z++; - } + List<Block> codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blocks.length, startBlock); + List<Block> linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blocks.length, startBlock); LIR lir = new LIR(schedule.getCFG(), schedule.getBlockToNodesMap(), linearScanOrder, codeEmittingOrder); Debug.dump(lir, "After linear scan order");
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java Thu Jan 17 00:41:44 2013 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java Thu Jan 17 17:21:16 2013 +0100 @@ -802,12 +802,12 @@ changeOccurredInBlock = false; // liveOut(block) is the union of liveIn(sux), for successors sux of block - int n = block.numberOfSux(); + int n = block.getSuccessorCount(); if (n > 0) { // block has successors if (n > 0) { liveOut.clear(); - liveOut.or(blockData.get(block.suxAt(0)).liveIn); + liveOut.or(blockData.get(block.getFirstSuccessor()).liveIn); for (int j = 1; j < n; j++) { liveOut.or(blockData.get(block.suxAt(j)).liveIn); } @@ -1095,7 +1095,7 @@ StackSlot slot = (StackSlot) move.getInput(); if (GraalOptions.DetailedAsserts) { assert op.id() > 0 : "invalid id"; - assert blockForId(op.id()).numberOfPreds() == 0 : "move from stack must be in first block"; + assert blockForId(op.id()).getPredecessorCount() == 0 : "move from stack must be in first block"; assert isVariable(move.getResult()) : "result of move must be a variable"; if (GraalOptions.TraceLinearScanLevel >= 4) { @@ -1484,7 +1484,7 @@ } void resolveFindInsertPos(Block fromBlock, Block toBlock, MoveResolver moveResolver) { - if (fromBlock.numberOfSux() <= 1) { + if (fromBlock.getSuccessorCount() <= 1) { if (GraalOptions.TraceLinearScanLevel >= 4) { TTY.println("inserting moves at end of fromBlock B%d", fromBlock.getId()); } @@ -1510,8 +1510,8 @@ // 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"; + for (Block predecessor : toBlock.getPredecessors()) { + assert fromBlock == predecessor : "all critical edges must be broken"; } } @@ -1534,22 +1534,22 @@ Block block = blockAt(i); // check if block has only one predecessor and only one successor - if (block.numberOfPreds() == 1 && block.numberOfSux() == 1) { + if (block.getPredecessorCount() == 1 && block.getSuccessorCount() == 1) { List<LIRInstruction> instructions = ir.lir(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) { - Block pred = block.predAt(0); - Block sux = block.suxAt(0); + Block pred = block.getPredecessors().get(0); + Block sux = block.getSuccessors().get(0); // prevent optimization of two consecutive blocks - if (!blockCompleted.get(pred.linearScanNumber) && !blockCompleted.get(sux.linearScanNumber)) { + if (!blockCompleted.get(pred.getLinearScanNumber()) && !blockCompleted.get(sux.getLinearScanNumber())) { if (GraalOptions.TraceLinearScanLevel >= 3) { TTY.println(" optimizing empty block B%d (pred: B%d, sux: B%d)", block.getId(), pred.getId(), sux.getId()); } - blockCompleted.set(block.linearScanNumber); + blockCompleted.set(block.getLinearScanNumber()); // directly resolve between pred and sux (without looking at the empty block between) resolveCollectMappings(pred, sux, moveResolver); @@ -1568,16 +1568,15 @@ alreadyResolved.clear(); alreadyResolved.or(blockCompleted); - int numSux = fromBlock.numberOfSux(); - for (int s = 0; s < numSux; s++) { - Block toBlock = fromBlock.suxAt(s); + int numSux = fromBlock.getSuccessorCount(); + for (Block toBlock : fromBlock.getSuccessors()) { // check for duplicate edges between the same blocks (can happen with switch blocks) - if (!alreadyResolved.get(toBlock.linearScanNumber)) { + if (!alreadyResolved.get(toBlock.getLinearScanNumber())) { if (GraalOptions.TraceLinearScanLevel >= 3) { TTY.println(" processing edge between B%d and B%d", fromBlock.getId(), toBlock.getId()); } - alreadyResolved.set(toBlock.linearScanNumber); + alreadyResolved.set(toBlock.getLinearScanNumber()); // collect all intervals that have been split between fromBlock and toBlock resolveCollectMappings(fromBlock, toBlock, moveResolver); @@ -1614,7 +1613,7 @@ if (opId != -1) { if (GraalOptions.DetailedAsserts) { Block block = blockForId(opId); - if (block.numberOfSux() <= 1 && opId == getLastLirInstructionId(block)) { + 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. @@ -1708,7 +1707,7 @@ int tempOpId = op.id(); OperandMode mode = OperandMode.USE; Block block = blockForId(tempOpId); - if (block.numberOfSux() == 1 && tempOpId == getLastLirInstructionId(block)) { + 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 @@ -1717,7 +1716,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.suxAt(0)); + tempOpId = getFirstLirInstructionId(block.getFirstSuccessor()); mode = OperandMode.DEF; } }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java Thu Jan 17 00:41:44 2013 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java Thu Jan 17 17:21:16 2013 +0100 @@ -265,8 +265,8 @@ } int findOptimalSplitPos(Block minBlock, Block maxBlock, int maxSplitPos) { - int fromBlockNr = minBlock.linearScanNumber; - int toBlockNr = maxBlock.linearScanNumber; + int fromBlockNr = minBlock.getLinearScanNumber(); + int toBlockNr = maxBlock.getLinearScanNumber(); assert 0 <= fromBlockNr && fromBlockNr < blockCount() : "out of range"; assert 0 <= toBlockNr && toBlockNr < blockCount() : "out of range"; @@ -318,7 +318,7 @@ // block at this opId) Block maxBlock = allocator.blockForId(maxSplitPos - 1); - assert minBlock.linearScanNumber <= maxBlock.linearScanNumber : "invalid order"; + assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order"; if (minBlock == maxBlock) { // split position cannot be moved to block boundary : so split as late as possible if (GraalOptions.TraceLinearScanLevel >= 4) {
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/RegisterVerifier.java Thu Jan 17 00:41:44 2013 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/RegisterVerifier.java Thu Jan 17 17:21:16 2013 +0100 @@ -118,8 +118,7 @@ processOperations(allocator.ir.lir(block), inputState); // iterate all successors - for (int i = 0; i < block.numberOfSux(); i++) { - Block succ = block.suxAt(i); + for (Block succ : block.getSuccessors()) { processSuccessor(succ, inputState); } }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Thu Jan 17 00:41:44 2013 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Thu Jan 17 17:21:16 2013 +0100 @@ -282,7 +282,7 @@ assert lir.lir(block) == null : "LIR list already computed for this block"; lir.setLir(block, new ArrayList<LIRInstruction>()); - append(new LabelOp(new Label(), block.align)); + append(new LabelOp(new Label(), block.isAligned())); if (GraalOptions.TraceLIRGeneratorLevel >= 1) { TTY.println("BEGIN Generating LIR for block B" + block.getId()); @@ -400,7 +400,7 @@ } } } - if (block.numberOfSux() >= 1 && !endsWithJump(block)) { + if (block.getSuccessorCount() >= 1 && !endsWithJump(block)) { NodeClassIterable successors = block.getEndNode().successors(); assert successors.isNotEmpty() : "should have at least one successor : " + block.getEndNode();
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ControlFlowOptimizer.java Thu Jan 17 00:41:44 2013 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ControlFlowOptimizer.java Thu Jan 17 17:21:16 2013 +0100 @@ -51,9 +51,9 @@ * @return whether the block can be deleted */ private static boolean canDeleteBlock(LIR ir, Block block) { - if (block.numberOfSux() != 1 || - block.numberOfPreds() == 0 || - block.suxAt(0) == block) { + if (block.getSuccessorCount() != 1 || + block.getPredecessorCount() == 0 || + block.getFirstSuccessor() == block) { return false; } @@ -75,7 +75,7 @@ Block block = iterator.next(); if (canDeleteBlock(ir, block)) { // adjust successor and predecessor lists - Block other = block.suxAt(0); + Block other = block.getFirstSuccessor(); for (Block pred : block.getPredecessors()) { Collections.replaceAll(pred.getSuccessors(), block, other); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/EdgeMoveOptimizer.java Thu Jan 17 00:41:44 2013 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/EdgeMoveOptimizer.java Thu Jan 17 17:21:16 2013 +0100 @@ -60,10 +60,10 @@ for (int i = blockList.size() - 1; i >= 1; i--) { Block block = blockList.get(i); - if (block.numberOfPreds() > 1) { + if (block.getPredecessorCount() > 1) { optimizer.optimizeMovesAtBlockEnd(block); } - if (block.numberOfSux() == 2) { + if (block.getSuccessorCount() == 2) { optimizer.optimizeMovesAtBlockBegin(block); } } @@ -115,7 +115,7 @@ // clear all internal data structures edgeInstructionSeqences.clear(); - int numPreds = block.numberOfPreds(); + int numPreds = block.getPredecessorCount(); assert numPreds > 1 : "do not call otherwise"; // setup a list with the LIR instructions of all predecessors @@ -124,13 +124,13 @@ assert ir.lir(pred) != null; List<LIRInstruction> predInstructions = ir.lir(pred); - if (pred.numberOfSux() != 1) { + if (pred.getSuccessorCount() != 1) { // this can happen with switch-statements where multiple edges are between // the same blocks. return; } - assert pred.suxAt(0) == block : "invalid control flow"; + assert pred.getFirstSuccessor() == block : "invalid control flow"; assert predInstructions.get(predInstructions.size() - 1) instanceof StandardOp.JumpOp : "block must end with unconditional jump"; if (predInstructions.get(predInstructions.size() - 1).hasState()) { @@ -177,7 +177,7 @@ private void optimizeMovesAtBlockBegin(Block block) { edgeInstructionSeqences.clear(); - int numSux = block.numberOfSux(); + int numSux = block.getSuccessorCount(); List<LIRInstruction> instructions = ir.lir(block); @@ -203,18 +203,17 @@ int insertIdx = instructions.size() - 2; // setup a list with the lir-instructions of all successors - for (int i = 0; i < numSux; i++) { - Block sux = block.suxAt(i); + for (Block sux : block.getSuccessors()) { List<LIRInstruction> suxInstructions = ir.lir(sux); assert suxInstructions.get(0) instanceof StandardOp.LabelOp : "block must start with label"; - if (sux.numberOfPreds() != 1) { + if (sux.getPredecessorCount() != 1) { // this can happen with switch-statements where multiple edges are between // the same blocks. return; } - assert sux.predAt(0) == block : "invalid control flow"; + assert sux.getPredecessors().get(0) == block : "invalid control flow"; // ignore the label at the beginning of the block List<LIRInstruction> seq = suxInstructions.subList(1, suxInstructions.size());
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRVerifier.java Thu Jan 17 00:41:44 2013 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRVerifier.java Thu Jan 17 17:21:16 2013 +0100 @@ -114,7 +114,7 @@ assert lir.lir(block).get(0) instanceof StandardOp.LabelOp : "block must start with label"; - if (block.numberOfSux() > 0) { + if (block.getSuccessorCount() > 0) { LIRInstruction last = lir.lir(block).get(lir.lir(block).size() - 1); assert last instanceof StandardOp.JumpOp : "block with successor must end with unconditional jump"; }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LabelRef.java Thu Jan 17 00:41:44 2013 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LabelRef.java Thu Jan 17 17:21:16 2013 +0100 @@ -72,12 +72,12 @@ return new LabelRef() { @Override public Label label() { - return ((StandardOp.LabelOp) lir.lir(block.suxAt(suxIndex)).get(0)).getLabel(); + return ((StandardOp.LabelOp) lir.lir(block.getSuccessors().get(suxIndex)).get(0)).getLabel(); } @Override public String toString() { - return suxIndex < block.numberOfSux() ? block.suxAt(suxIndex).toString() : "?" + block + ":" + suxIndex + "?"; + return suxIndex < block.getSuccessorCount() ? block.getSuccessors().get(suxIndex).toString() : "?" + block + ":" + suxIndex + "?"; } }; }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Thu Jan 17 00:41:44 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Thu Jan 17 17:21:16 2013 +0100 @@ -27,7 +27,7 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.java.*; -public class Block { +public final class Block { protected int id; @@ -43,9 +43,8 @@ protected List<Block> dominated; protected Block postdominator; - // Fields that still need to be worked on, try to remove them later. - public boolean align; - public int linearScanNumber; + private boolean align; + private int linearScanNumber; protected Block() { id = ControlFlowGraph.BLOCK_ID_INITIAL; @@ -87,6 +86,10 @@ return predecessors; } + public Block getFirstSuccessor() { + return successors.get(0); + } + public List<Block> getSuccessors() { return successors; } @@ -175,20 +178,14 @@ return "B" + id; } - -// to be inlined later on - public int numberOfPreds() { + public int getPredecessorCount() { return getPredecessors().size(); } - public int numberOfSux() { + public int getSuccessorCount() { return getSuccessors().size(); } - public Block predAt(int i) { - return getPredecessors().get(i); - } - public Block suxAt(int i) { return getSuccessors().get(i); } @@ -207,4 +204,24 @@ } return dominator.isDominatedBy(block); } + + public double getProbability() { + return getBeginNode().probability(); + } + + public int getLinearScanNumber() { + return linearScanNumber; + } + + public void setLinearScanNumber(int linearScanNumber) { + this.linearScanNumber = linearScanNumber; + } + + public boolean isAligned() { + return align; + } + + public void setAlign(boolean align) { + this.align = align; + } }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Thu Jan 17 00:41:44 2013 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Thu Jan 17 17:21:16 2013 +0100 @@ -193,7 +193,6 @@ public static boolean OptReadElimination = true; public static boolean OptCanonicalizer = true; public static boolean OptScheduleOutOfLoops = true; - public static boolean OptReorderLoops = true; public static boolean OptEliminateGuards = true; public static boolean OptImplicitNullChecks = true; public static boolean OptLivenessAnalysis = true;