Mercurial > hg > truffle
changeset 7505:1b00e067eafe
Merge
| author | Christian Humer <christian.humer@gmail.com> |
|---|---|
| date | Fri, 18 Jan 2013 13:41:46 +0100 |
| parents | d295ab2902fb (current diff) 994f7ed25a46 (diff) |
| children | 40133ce026c6 |
| files | |
| diffstat | 10 files changed, 46 insertions(+), 42 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Fri Jan 18 13:39:04 2013 +0100 +++ b/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Fri Jan 18 13:41:46 2013 +0100 @@ -29,7 +29,19 @@ /** * Computes an ordering of the block that can be used by the linear scan register allocator and the machine code - * generator. + * generator. The machine code generation order will start with the first block and produce a straight sequence + * always following the most likely successor. Then it will continue with the most likely path that was left out during + * this process. The process iteratively continues until all blocks are scheduled. Additionally, it is guaranteed that + * all blocks of a loop are scheduled before any block following the loop is scheduled. + * + * The machine code generator order includes reordering of loop headers such that the backward jump is a conditional jump if there + * is only one loop end block. Additionally, the target of loop backward jumps are always marked as aligned. Aligning the target of conditional + * jumps does not bring a measurable benefit and is therefore avoided to keep the code size small. + * + * The linear scan register allocator order has an additional mechanism that prevents merge nodes from being scheduled if there is + * at least one highly likely predecessor still unscheduled. This increases the probability that the merge node and the corresponding + * predecessor are more closely together in the schedule thus decreasing the probability for inserted phi moves. Also, the algorithm sets + * the linear scan order number of the block that corresponds to its index in the linear scan order. */ public final class ComputeBlockOrder { @@ -112,7 +124,7 @@ Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks); enqueueSuccessors(block, worklist, visitedBlocks); if (mostLikelySuccessor != null) { - if (!mostLikelySuccessor.isLoopHeader() && mostLikelySuccessor.getPredecessors().size() > 1) { + if (!mostLikelySuccessor.isLoopHeader() && mostLikelySuccessor.getPredecessorCount() > 1) { // We are at a merge. Check probabilities of predecessors that are not yet scheduled. double unscheduledSum = 0.0; for (Block pred : mostLikelySuccessor.getPredecessors()) {
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java Fri Jan 18 13:39:04 2013 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java Fri Jan 18 13:41:46 2013 +0100 @@ -807,9 +807,8 @@ // block has successors if (n > 0) { liveOut.clear(); - liveOut.or(blockData.get(block.getFirstSuccessor()).liveIn); - for (int j = 1; j < n; j++) { - liveOut.or(blockData.get(block.suxAt(j)).liveIn); + for (Block successor : block.getSuccessors()) { + liveOut.or(blockData.get(successor).liveIn); } } else { liveOut.clear(); @@ -859,7 +858,7 @@ reportFailure(numBlocks); } - TTY.println("preds=" + startBlock.getPredecessors().size() + ", succs=" + startBlock.getSuccessors().size()); + TTY.println("preds=" + startBlock.getPredecessorCount() + ", succs=" + startBlock.getSuccessorCount()); TTY.println("startBlock-ID: " + startBlock.getId()); // bailout of if this occurs in product mode. @@ -918,7 +917,7 @@ definedIn.add(successor); } } else { - if (++hitCount[successor.getId()] == successor.getPredecessors().size()) { + if (++hitCount[successor.getId()] == successor.getPredecessorCount()) { definedIn.add(successor); } } @@ -1541,8 +1540,8 @@ // check if block is empty (only label and branch) if (instructions.size() == 2) { - Block pred = block.getPredecessors().get(0); - Block sux = block.getSuccessors().get(0); + Block pred = block.getFirstPredecessor(); + Block sux = block.getFirstSuccessor(); // prevent optimization of two consecutive blocks if (!blockCompleted.get(pred.getLinearScanNumber()) && !blockCompleted.get(sux.getLinearScanNumber())) {
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Fri Jan 18 13:39:04 2013 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Fri Jan 18 13:41:46 2013 +0100 @@ -289,12 +289,12 @@ } if (block == lir.cfg.getStartBlock()) { - assert block.getPredecessors().size() == 0; + assert block.getPredecessorCount() == 0; currentLockCount = 0; emitPrologue(); } else { - assert block.getPredecessors().size() > 0; + assert block.getPredecessorCount() > 0; currentLockCount = -1; for (Block pred : block.getPredecessors()) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ControlFlowOptimizer.java Fri Jan 18 13:39:04 2013 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ControlFlowOptimizer.java Fri Jan 18 13:41:46 2013 +0100 @@ -62,7 +62,7 @@ assert instructions.size() >= 2 : "block must have label and branch"; assert instructions.get(0) instanceof StandardOp.LabelOp : "first instruction must always be a label"; assert instructions.get(instructions.size() - 1) instanceof StandardOp.JumpOp : "last instruction must always be a branch"; - assert ((StandardOp.JumpOp) instructions.get(instructions.size() - 1)).destination().label() == ((StandardOp.LabelOp) ir.lir(block.suxAt(0)).get(0)).getLabel() : "branch target must be the successor"; + assert ((StandardOp.JumpOp) instructions.get(instructions.size() - 1)).destination().label() == ((StandardOp.LabelOp) ir.lir(block.getFirstSuccessor()).get(0)).getLabel() : "branch target must be the successor"; // Block must have exactly one successor. return instructions.size() == 2 && !instructions.get(instructions.size() - 1).hasState(); @@ -79,7 +79,7 @@ for (Block pred : block.getPredecessors()) { Collections.replaceAll(pred.getSuccessors(), block, other); } - for (int i = 0; i < other.getPredecessors().size(); i++) { + for (int i = 0; i < other.getPredecessorCount(); i++) { if (other.getPredecessors().get(i) == block) { other.getPredecessors().remove(i); other.getPredecessors().addAll(i, block.getPredecessors());
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/EdgeMoveOptimizer.java Fri Jan 18 13:39:04 2013 +0100 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/EdgeMoveOptimizer.java Fri Jan 18 13:41:46 2013 +0100 @@ -213,7 +213,7 @@ // the same blocks. return; } - assert sux.getPredecessors().get(0) == block : "invalid control flow"; + assert sux.getFirstPredecessor() == 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.nodes/src/com/oracle/graal/nodes/cfg/Block.java Fri Jan 18 13:39:04 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Fri Jan 18 13:41:46 2013 +0100 @@ -34,7 +34,6 @@ protected BeginNode beginNode; protected FixedNode endNode; protected Loop loop; - protected double probability; protected List<Block> predecessors; protected List<Block> successors; @@ -82,6 +81,10 @@ return getBeginNode().next() instanceof ExceptionObjectNode; } + public Block getFirstPredecessor() { + return predecessors.get(0); + } + public List<Block> getPredecessors() { return predecessors; } @@ -186,11 +189,6 @@ return getSuccessors().size(); } - public Block suxAt(int i) { - return getSuccessors().get(i); - } -// end to be inlined later on - public boolean dominates(Block block) { return block.isDominatedBy(this); }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Fri Jan 18 13:39:04 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Fri Jan 18 13:41:46 2013 +0100 @@ -131,13 +131,6 @@ } } - if (cur instanceof FixedNode) { - double probability = ((FixedNode) cur).probability(); - if (probability > block.probability) { - block.probability = probability; - } - } - last = cur; cur = cur.successors().first(); } while (cur != null && !(cur instanceof BeginNode)); @@ -233,9 +226,8 @@ for (LoopExitNode exit : loopBegin.loopExits()) { Block exitBlock = nodeToBlock.get(exit); - List<Block> predecessors = exitBlock.getPredecessors(); - assert predecessors.size() == 1; - computeLoopBlocks(predecessors.get(0), loop); + assert exitBlock.getPredecessorCount() == 1; + computeLoopBlocks(exitBlock.getFirstPredecessor(), loop); loop.exits.add(exitBlock); } List<Block> unexpected = new LinkedList<>(); @@ -287,15 +279,12 @@ } private void computeDominators() { - assert reversePostOrder[0].getPredecessors().size() == 0 : "start block has no predecessor and therefore no dominator"; + assert reversePostOrder[0].getPredecessorCount() == 0 : "start block has no predecessor and therefore no dominator"; for (int i = 1; i < reversePostOrder.length; i++) { Block block = reversePostOrder[i]; - List<Block> predecessors = block.getPredecessors(); - assert predecessors.size() > 0; - - Block dominator = predecessors.get(0); - for (int j = 1; j < predecessors.size(); j++) { - Block pred = predecessors.get(j); + assert block.getPredecessorCount() > 0; + Block dominator = null; + for (Block pred : block.getPredecessors()) { if (!pred.isLoopEnd()) { dominator = commonDominator(dominator, pred); } @@ -313,6 +302,12 @@ } public static Block commonDominator(Block a, Block b) { + if (a == null) { + return b; + } + if (b == null) { + return a; + } Block iterA = a; Block iterB = b; while (iterA != iterB) {
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java Fri Jan 18 13:39:04 2013 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java Fri Jan 18 13:41:46 2013 +0100 @@ -64,8 +64,8 @@ info.endStates.add(blockEndStates.get(predecessors.get(i).getEndNode())); } for (Block loopExit : loop.exits) { - assert loopExit.getPredecessors().size() == 1; - T exitState = blockEndStates.get(loopExit.getPredecessors().get(0).getEndNode()); + assert loopExit.getPredecessorCount() == 1; + T exitState = blockEndStates.get(loopExit.getFirstPredecessor().getEndNode()); assert exitState != null; info.exitStates.add(exitState); } @@ -102,7 +102,7 @@ int i = 0; assert loop.exits.size() == exitStates.size(); for (Block exit : loop.exits) { - blockEndStates.put(exit.getPredecessors().get(0).getEndNode(), exitStates.get(i++)); + blockEndStates.put(exit.getFirstPredecessor().getEndNode(), exitStates.get(i++)); blockQueue.addFirst(exit); } }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Fri Jan 18 13:39:04 2013 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Fri Jan 18 13:41:46 2013 +0100 @@ -246,7 +246,7 @@ assert mergeBlock != null : "no block for merge " + merge.toString(Verbosity.Id); for (int i = 0; i < phi.valueCount(); ++i) { if (phi.valueAt(i) == node) { - if (mergeBlock.getPredecessors().size() <= i) { + if (mergeBlock.getPredecessorCount() <= i) { TTY.println(merge.toString()); TTY.println(phi.toString()); TTY.println(merge.cfgPredecessors().toString());
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Fri Jan 18 13:39:04 2013 +0100 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Fri Jan 18 13:41:46 2013 +0100 @@ -241,7 +241,7 @@ out.println("HIR"); out.disableIndentation(); - if (block.getPredecessors().size() == 0) { + if (block.getPredecessorCount() == 0) { // Currently method parameters are not in the schedule, so print them separately here. for (ValueNode param : block.getBeginNode().graph().getNodes(LocalNode.class)) { printNode(param, false);