Mercurial > hg > graal-compiler
changeset 2778:2ac7b30b7290
Enabled new block finding algorithm.
| author | Thomas Wuerthinger <thomas@wuerthinger.net> |
|---|---|
| date | Tue, 24 May 2011 21:39:45 +0200 |
| parents | 3e4d992fd312 |
| children | 93ec3f067420 |
| files | graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java graal/GraalCompiler/src/com/sun/c1x/alloc/ControlFlowOptimizer.java graal/GraalCompiler/src/com/sun/c1x/alloc/EdgeMoveOptimizer.java graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScan.java graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java graal/GraalCompiler/src/com/sun/c1x/graph/IR.java graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java graal/GraalCompiler/src/com/sun/c1x/util/BitMap2D.java runtests.sh |
| diffstat | 12 files changed, 568 insertions(+), 112 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java Tue May 24 14:40:47 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java Tue May 24 21:39:45 2011 +0200 @@ -24,6 +24,7 @@ import java.util.*; +import com.sun.c1x.debug.*; import com.sun.c1x.ir.*; @@ -33,6 +34,7 @@ private final List<Block> successors = new ArrayList<Block>(); private final List<Block> predecessors = new ArrayList<Block>(); private final List<Instruction> instructions = new ArrayList<Instruction>(); + private boolean exceptionEntry; public List<Block> getSuccessors() { return Collections.unmodifiableList(successors); @@ -59,8 +61,28 @@ return blockID; } + public void setExceptionEntry(boolean b) { + exceptionEntry = b; + } + + public boolean isExceptionEntry() { + return exceptionEntry; + } + @Override public String toString() { return "B" + blockID; } + + public void removeExceptionSuccessors() { + for (int i = 0; i < successors.size(); ++i) { + TTY.println("checking succ"); + if (successors.get(i).isExceptionEntry()) { + TTY.println("removing successor " + i); + successors.remove(i); + i--; + } + } + + } }
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Tue May 24 14:40:47 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Tue May 24 21:39:45 2011 +0200 @@ -55,6 +55,7 @@ } private Block assignBlock(Node n) { + assert n instanceof BlockBegin : n; Block curBlock = nodeToBlock.get(n); if (curBlock == null) { curBlock = createBlock(); @@ -111,13 +112,27 @@ successorCount++; if (successorCount > 1) { // Our predecessor is a split => we need a new block. - assignBlock(n); + if (singlePred instanceof ExceptionEdgeInstruction) { + ExceptionEdgeInstruction e = (ExceptionEdgeInstruction) singlePred; + if (e.exceptionEdge() != n) { + break; + } + } + Block b = assignBlock(n); + b.setExceptionEntry(singlePred instanceof ExceptionEdgeInstruction); blockBeginNodes.add(n); return true; } } } - assignBlock(n, nodeToBlock.get(singlePred)); + + if (singlePred instanceof BlockEnd) { + Block b = assignBlock(n); + b.setExceptionEntry(singlePred instanceof Throw); + blockBeginNodes.add(n); + } else { + assignBlock(n, nodeToBlock.get(singlePred)); + } } return true; }} @@ -134,14 +149,32 @@ } } + orderBlocks(); //print(); } + private void orderBlocks() { + /* List<Block> orderedBlocks = new ArrayList<Block>(); + Block startBlock = nodeToBlock.get(graph.start().start()); + List<Block> toSchedule = new ArrayList<Block>(); + toSchedule.add(startBlock); + + while (toSchedule.size() != 0) { + + + }*/ + } + private void print() { TTY.println("============================================"); TTY.println("%d blocks", blocks.size()); + for (Block b : blocks) { + TTY.println(); TTY.print(b.toString()); + if (b.isExceptionEntry()) { + TTY.print(" (ex)"); + } TTY.print(" succs="); for (Block succ : b.getSuccessors()) { @@ -153,9 +186,11 @@ TTY.print(pred + ";"); } TTY.println(); + TTY.print("first instr: " + b.getInstructions().get(0)); + TTY.print("last instr: " + b.getInstructions().get(b.getInstructions().size() - 1)); } - +/* TTY.println("============================================"); TTY.println("%d nodes", nodeToBlock.size()); for (Node n : graph.getNodes()) { @@ -167,6 +202,6 @@ } TTY.println(); } - } + }*/ } }
--- a/graal/GraalCompiler/src/com/sun/c1x/alloc/ControlFlowOptimizer.java Tue May 24 14:40:47 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/alloc/ControlFlowOptimizer.java Tue May 24 21:39:45 2011 +0200 @@ -103,7 +103,7 @@ assert instructions.size() >= 2 : "block must have label and branch"; assert instructions.get(0).code == LIROpcode.Label : "first instruction must always be a label"; - assert instructions.get(instructions.size() - 1) instanceof LIRBranch : "last instruction must always be a branch"; + assert instructions.get(instructions.size() - 1) instanceof LIRBranch : "last instruction must always be a branch but is " + instructions.get(instructions.size() - 1); assert ((LIRBranch) instructions.get(instructions.size() - 1)).cond() == Condition.TRUE : "branch must be unconditional"; assert ((LIRBranch) instructions.get(instructions.size() - 1)).block() == block.suxAt(0) : "branch target must be the successor";
--- a/graal/GraalCompiler/src/com/sun/c1x/alloc/EdgeMoveOptimizer.java Tue May 24 14:40:47 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/alloc/EdgeMoveOptimizer.java Tue May 24 21:39:45 2011 +0200 @@ -126,6 +126,8 @@ // setup a list with the LIR instructions of all predecessors for (int i = 0; i < numPreds; i++) { LIRBlock pred = block.predAt(i); + assert pred != null; + assert pred.lir() != null; List<LIRInstruction> predInstructions = pred.lir().instructionsList(); if (pred.numberOfSux() != 1) {
--- a/graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScan.java Tue May 24 14:40:47 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScan.java Tue May 24 21:39:45 2011 +0200 @@ -27,6 +27,7 @@ import java.util.*; +import com.oracle.graal.graph.*; import com.sun.c1x.*; import com.sun.c1x.alloc.Interval.*; import com.sun.c1x.debug.*; @@ -1159,6 +1160,14 @@ final int blockFrom = block.firstLirInstructionId(); int blockTo = block.lastLirInstructionId(); + // (tw) Destroy all registers on exception handler entry. + if (block.isExceptionEntry()) { + for (CiRegister r : callerSaveRegs) { + if (attributes(r).isAllocatable) { + addTemp(r.asValue(), block.firstLirInstructionId(), RegisterPriority.None, CiKind.Illegal); + } + } + } assert blockFrom == instructions.get(0).id; assert blockTo == instructions.get(instructions.size() - 1).id; @@ -1263,6 +1272,22 @@ } // end of instruction iteration + + // (tw) TODO: Check if this matters.. + // (tw) Make sure that no spill store optimization is applied for phi instructions that flow into exception handlers. +// if (block.isExceptionEntry()) { +// Instruction firstInstruction = block.getInstructions().get(0); +// for (Node n : firstInstruction.usages()) { +// if (n instanceof Phi) { +// Phi phi = (Phi) n; +// Interval interval = intervalFor(phi.operand()); +// if (interval != null) { +// interval.setSpillState(SpillState.NoOptimization); +// } +// } +// } +// } + } // end of block iteration // add the range [0, 1] to all fixed intervals. @@ -1589,7 +1614,7 @@ if (block.numberOfPreds() == 1 && block.numberOfSux() == 1) { List<LIRInstruction> instructions = block.lir().instructionsList(); assert instructions.get(0).code == LIROpcode.Label : "block must start with label"; - assert instructions.get(instructions.size() - 1).code == LIROpcode.Branch : "block with successors must end with branch"; + assert instructions.get(instructions.size() - 1).code == LIROpcode.Branch : "block with successors must end with branch (" + block + "), " + instructions.get(instructions.size() - 1); assert ((LIRBranch) instructions.get(instructions.size() - 1)).cond() == Condition.TRUE : "block with successor must end with unconditional branch"; // check if block is empty (only label and branch) @@ -2065,8 +2090,8 @@ } printLir("After register number assignment", true); - EdgeMoveOptimizer.optimize(ir.linearScanOrder()); - ControlFlowOptimizer.optimize(ir); + //EdgeMoveOptimizer.optimize(ir.linearScanOrder()); + //ControlFlowOptimizer.optimize(ir); printLir("After control flow optimization", false); }
--- a/graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java Tue May 24 14:40:47 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java Tue May 24 21:39:45 2011 +0200 @@ -175,6 +175,9 @@ begin("states"); FrameState state = block.stateBefore(); + if (state == null) { + return; + } int stackSize = state.stackSize(); if (stackSize > 0) { begin("stack");
--- a/graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java Tue May 24 14:40:47 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java Tue May 24 21:39:45 2011 +0200 @@ -392,8 +392,8 @@ // emit phi-instruction moves after safepoint since this simplifies // describing the state at the safepoint. - moveToPhi(x.stateAfter()); + moveToPhi(); lir.jump(getLIRBlock(x.defaultSuccessor())); } @@ -1266,11 +1266,6 @@ } } - protected void moveToPhi() { - assert lastState != null; - this.moveToPhi(lastState); - } - private List<Phi> getPhis(LIRBlock block) { if (block.getInstructions().size() > 0) { Instruction i = block.getInstructions().get(0); @@ -1287,7 +1282,7 @@ return null; } - protected void moveToPhi(FrameState curState) { + protected void moveToPhi() { // Moves all stack values into their phi position LIRBlock bb = currentBlock; if (bb.numberOfSux() == 1) {
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java Tue May 24 14:40:47 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java Tue May 24 21:39:45 2011 +0200 @@ -86,33 +86,37 @@ Schedule schedule = new Schedule(this.compilation.graph); List<Block> blocks = schedule.getBlocks(); - NodeMap<Block> nodeToBlock = schedule.getNodeToBlock(); - /* orderedBlocks = new ArrayList<LIRBlock>(); + List<LIRBlock> lirBlocks = new ArrayList<LIRBlock>(); Map<Block, LIRBlock> map = new HashMap<Block, LIRBlock>(); for (Block b : blocks) { LIRBlock block = new LIRBlock(b.blockID()); + block.setExceptionEntry(b.isExceptionEntry()); map.put(b, block); block.setInstructions(b.getInstructions()); - orderedBlocks.add(block); + block.setLinearScanNumber(b.blockID()); + lirBlocks.add(block); } for (Block b : blocks) { for (Block succ : b.getSuccessors()) { - map.get(b).blockSuccessors().add(map.get(succ)); + if (succ.isExceptionEntry()) { + map.get(b).getExceptionHandlerSuccessors().add(map.get(succ)); + } else { + map.get(b).blockSuccessors().add(map.get(succ)); + } } for (Block pred : b.getPredecessors()) { map.get(b).blockPredecessors().add(map.get(pred)); } - }*/ + } - // TODO(tw): Schedule nodes within a block. - + // TODO(tw): Schedule nodes within a block. + //computeLinearScanOrder(); - - - computeLinearScanOrder(); +// assert orderedBlocks.size() == lirBlocks.size(); + orderedBlocks = lirBlocks; valueToBlock = new HashMap<Value, LIRBlock>(); @@ -125,6 +129,37 @@ assert startBlock != null; verifyAndPrint("After linear scan order"); + ComputeLinearScanOrder clso = new ComputeLinearScanOrder(lirBlocks.size(), startBlock); + orderedBlocks = clso.linearScanOrder(); + this.compilation.stats.loopCount = clso.numLoops(); + + int z = 0; + for (LIRBlock b : orderedBlocks) { + b.setLinearScanNumber(z++); + + /* TTY.println(); + + for (Instruction i : b.getInstructions()) { + if (i instanceof BlockBegin) { + TTY.println("BlockBegin #" + ((BlockBegin) i).blockID); + + TTY.print(" => succs: "); + for (LIRBlock succBlock : b.blockSuccessors()) { + TTY.print("B#" + ((BlockBegin) succBlock.getInstructions().get(0)).blockID); + } + TTY.print(" => ex: "); + for (LIRBlock succBlock : b.getExceptionHandlerSuccessors()) { + TTY.print("B#" + ((BlockBegin) succBlock.getInstructions().get(0)).blockID); + } + TTY.println(); + } else { + TTY.println(i.getClass().getSimpleName() + " #" + i.id()); + } + }*/ + } + + + if (C1XOptions.PrintTimers) { C1XTimers.HIR_OPTIMIZE.stop(); } @@ -145,7 +180,7 @@ } private Map<Value, LIRBlock> makeLinearScanOrder() { - +/* if (orderedBlocks == null) { Map<Value, LIRBlock> valueToBlock = new HashMap<Value, LIRBlock>(); @@ -160,7 +195,6 @@ valueToBlock.put(bb, lirBlock); lirBlock.setLinearScanNumber(bb.linearScanNumber()); // TODO(tw): Initialize LIRBlock.linearScanLoopHeader and LIRBlock.linearScanLoopEnd - lirBlock.setStateBefore(bb.stateBefore()); orderedBlocks.add(lirBlock); ++z; } @@ -185,8 +219,9 @@ ++z; } - } - return valueToBlock; + }*/ + return null; + //return valueToBlock; } /**
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java Tue May 24 14:40:47 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java Tue May 24 21:39:45 2011 +0200 @@ -27,6 +27,7 @@ import com.sun.c1x.*; import com.sun.c1x.debug.*; +import com.sun.c1x.lir.*; import com.sun.c1x.util.*; import com.sun.cri.ci.*; @@ -35,69 +36,71 @@ private final int maxBlockId; // the highest blockId of a block private int numBlocks; // total number of blocks (smaller than maxBlockId) private int numLoops; // total number of loops + private boolean iterativeDominators; // method requires iterative computation of dominators - List<BlockBegin> linearScanOrder; // the resulting list of blocks in correct order + List<LIRBlock> linearScanOrder; // the resulting list of blocks in correct order final CiBitMap visitedBlocks; // used for recursive processing of blocks final CiBitMap activeBlocks; // used for recursive processing of blocks + final CiBitMap dominatorBlocks; // temporary BitMap used for computation of dominator final int[] forwardBranches; // number of incoming forward branches for each block - final List<BlockBegin> loopEndBlocks; // list of all loop end blocks collected during countEdges + final List<LIRBlock> loopEndBlocks; // list of all loop end blocks collected during countEdges BitMap2D loopMap; // two-dimensional bit set: a bit is set if a block is contained in a loop - final List<BlockBegin> workList; // temporary list (used in markLoops and computeOrder) + final List<LIRBlock> workList; // temporary list (used in markLoops and computeOrder) // accessors for visitedBlocks and activeBlocks - private void initVisited() { + void initVisited() { activeBlocks.clearAll(); visitedBlocks.clearAll(); } - private boolean isVisited(BlockBegin b) { - return visitedBlocks.get(b.blockID); + boolean isVisited(LIRBlock b) { + return visitedBlocks.get(b.blockID()); } - private boolean isActive(BlockBegin b) { - return activeBlocks.get(b.blockID); + boolean isActive(LIRBlock b) { + return activeBlocks.get(b.blockID()); } - private void setVisited(BlockBegin b) { + void setVisited(LIRBlock b) { assert !isVisited(b) : "already set"; - visitedBlocks.set(b.blockID); + visitedBlocks.set(b.blockID()); } - private void setActive(BlockBegin b) { + void setActive(LIRBlock b) { assert !isActive(b) : "already set"; - activeBlocks.set(b.blockID); + activeBlocks.set(b.blockID()); } - private void clearActive(BlockBegin b) { + void clearActive(LIRBlock b) { assert isActive(b) : "not already"; - activeBlocks.clear(b.blockID); + activeBlocks.clear(b.blockID()); } // accessors for forwardBranches - private void incForwardBranches(BlockBegin b) { - forwardBranches[b.blockID]++; + void incForwardBranches(LIRBlock b) { + forwardBranches[b.blockID()]++; } - private int decForwardBranches(BlockBegin b) { - return --forwardBranches[b.blockID]; + int decForwardBranches(LIRBlock b) { + return --forwardBranches[b.blockID()]; } // accessors for loopMap - private boolean isBlockInLoop(int loopIdx, BlockBegin b) { - return loopMap.at(loopIdx, b.blockID); + boolean isBlockInLoop(int loopIdx, LIRBlock b) { + return loopMap.at(loopIdx, b.blockID()); } - private void setBlockInLoop(int loopIdx, BlockBegin b) { - loopMap.setBit(loopIdx, b.blockID); + void setBlockInLoop(int loopIdx, LIRBlock b) { + loopMap.setBit(loopIdx, b.blockID()); } - private void clearBlockInLoop(int loopIdx, int blockId) { + void clearBlockInLoop(int loopIdx, int blockId) { loopMap.clearBit(loopIdx, blockId); } // accessors for final result - public List<BlockBegin> linearScanOrder() { + public List<LIRBlock> linearScanOrder() { return linearScanOrder; } @@ -105,18 +108,34 @@ return numLoops; } - public ComputeLinearScanOrder(int maxBlockId, BlockBegin startBlock) { + public ComputeLinearScanOrder(int maxBlockId, LIRBlock startBlock) { this.maxBlockId = maxBlockId; visitedBlocks = new CiBitMap(maxBlockId); activeBlocks = new CiBitMap(maxBlockId); + dominatorBlocks = new CiBitMap(maxBlockId); forwardBranches = new int[maxBlockId]; - loopEndBlocks = new ArrayList<BlockBegin>(8); - workList = new ArrayList<BlockBegin>(8); + loopEndBlocks = new ArrayList<LIRBlock>(8); + workList = new ArrayList<LIRBlock>(8); + + splitCriticalEdges(); countEdges(startBlock, null); + if (numLoops > 0) { + markLoops(); + clearNonNaturalLoops(startBlock); + assignLoopDepth(startBlock); + } + computeOrder(startBlock); + + printBlocks(); + assert verify(); + } + + void splitCriticalEdges() { + // TODO: move critical edge splitting from IR to here } /** @@ -127,9 +146,9 @@ * 3. Number loop header blocks. * 4. Create a list with all loop end blocks. */ - private void countEdges(final BlockBegin cur, BlockBegin parent) { + void countEdges(LIRBlock cur, LIRBlock parent) { if (C1XOptions.TraceLinearScanLevel >= 3) { - TTY.println("Counting edges for block B%d%s", cur.blockID, parent == null ? "" : " coming from B" + parent.blockID); + TTY.println("Counting edges for block B%d%s", cur.blockID(), parent == null ? "" : " coming from B" + parent.blockID()); } if (isActive(cur)) { @@ -139,9 +158,19 @@ assert isVisited(cur) : "block must be visited when block is active"; assert parent != null : "must have parent"; - //cur.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader); + cur.setLinearScanLoopHeader(); + cur.setBackwardBranchTarget(true); + parent.setLinearScanLoopEnd(); - //parent.setBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd); + // When a loop header is also the start of an exception handler, then the backward branch is + // an exception edge. Because such edges are usually critical edges which cannot be split, the + // loop must be excluded here from processing. + if (cur.isExceptionEntry()) { + // Make sure that dominators are correct in this weird situation + iterativeDominators = true; + return; + } +// assert parent.numberOfSux() == 1 && parent.suxAt(0) == cur : "loop end blocks must have one successor (critical edges are split)"; loopEndBlocks.add(parent); return; @@ -162,40 +191,197 @@ setActive(cur); // recursive call for all successors - cur.allSuccessorsDo(true, new BlockClosure() { - public void apply(BlockBegin block) { - countEdges(block, cur); - } - }); + int i; + for (i = cur.numberOfSux() - 1; i >= 0; i--) { + countEdges(cur.suxAt(i), cur); + } + for (LIRBlock ex : cur.getExceptionHandlerSuccessors()) { + countEdges(ex, cur); + } clearActive(cur); + // Each loop has a unique number. + // When multiple loops are nested, assignLoopDepth assumes that the + // innermost loop has the lowest number. This is guaranteed by setting + // the loop number after the recursive calls for the successors above + // have returned. + if (cur.isLinearScanLoopHeader()) { + assert cur.loopIndex() == -1 : "cannot set loop-index twice"; + if (C1XOptions.TraceLinearScanLevel >= 3) { + TTY.println("Block B%d is loop header of loop %d", cur.blockID(), numLoops); + } + + cur.setLoopIndex(numLoops); + numLoops++; + } + if (C1XOptions.TraceLinearScanLevel >= 3) { - TTY.println("Finished counting edges for block B%d", cur.blockID); + TTY.println("Finished counting edges for block B%d", cur.blockID()); + } + } + + void markLoops() { + if (C1XOptions.TraceLinearScanLevel >= 3) { + TTY.println("----- marking loops"); + } + + loopMap = new BitMap2D(numLoops, maxBlockId); + + for (int i = loopEndBlocks.size() - 1; i >= 0; i--) { + LIRBlock loopEnd = loopEndBlocks.get(i); + LIRBlock loopStart = loopEnd.suxAt(0); + int loopIdx = loopStart.loopIndex(); + + if (C1XOptions.TraceLinearScanLevel >= 3) { + TTY.println("Processing loop from B%d to B%d (loop %d):", loopStart.blockID(), loopEnd.blockID(), loopIdx); + } + assert loopEnd.isLinearScanLoopEnd() : "loop end flag must be set"; +// assert loopEnd.numberOfSux() == 1 : "incorrect number of successors"; + assert loopStart.isLinearScanLoopHeader() : "loop header flag must be set"; + assert loopIdx >= 0 && loopIdx < numLoops : "loop index not set"; + assert workList.isEmpty() : "work list must be empty before processing"; + + // add the end-block of the loop to the working list + workList.add(loopEnd); + setBlockInLoop(loopIdx, loopEnd); + do { + LIRBlock cur = workList.remove(workList.size() - 1); + + if (C1XOptions.TraceLinearScanLevel >= 3) { + TTY.println(" processing B%d", cur.blockID()); + } + assert isBlockInLoop(loopIdx, cur) : "bit in loop map must be set when block is in work list"; + + // recursive processing of all predecessors ends when start block of loop is reached + if (cur != loopStart) { + for (int j = cur.numberOfPreds() - 1; j >= 0; j--) { + LIRBlock pred = cur.predAt(j); + + if (!isBlockInLoop(loopIdx, pred)) { + // this predecessor has not been processed yet, so add it to work list + if (C1XOptions.TraceLinearScanLevel >= 3) { + TTY.println(" pushing B%d", pred.blockID()); + } + workList.add(pred); + setBlockInLoop(loopIdx, pred); + } + } + } + } while (!workList.isEmpty()); } } - private int computeWeight(BlockBegin cur) { - BlockBegin singleSux = null; - BlockEnd end = cur.end(); - if (end.blockSuccessorCount() == 1) { - singleSux = end.blockSuccessor(0); + // check for non-natural loops (loops where the loop header does not dominate + // all other loop blocks = loops with multiple entries). + // such loops are ignored + void clearNonNaturalLoops(LIRBlock startBlock) { + for (int i = numLoops - 1; i >= 0; i--) { + if (isBlockInLoop(i, startBlock)) { + // loop i contains the entry block of the method. + // this is not a natural loop, so ignore it + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println("Loop %d is non-natural, so it is ignored", i); + } + + for (int blockId = maxBlockId - 1; blockId >= 0; blockId--) { + clearBlockInLoop(i, blockId); + } + iterativeDominators = true; + } + } + } + + void assignLoopDepth(LIRBlock startBlock) { + if (C1XOptions.TraceLinearScanLevel >= 3) { + TTY.println("----- computing loop-depth and weight"); + } + initVisited(); + + assert workList.isEmpty() : "work list must be empty before processing"; + workList.add(startBlock); + + do { + LIRBlock cur = workList.remove(workList.size() - 1); + + if (!isVisited(cur)) { + setVisited(cur); + if (C1XOptions.TraceLinearScanLevel >= 4) { + TTY.println("Computing loop depth for block B%d", cur.blockID()); + } + + // compute loop-depth and loop-index for the block + assert cur.loopDepth() == 0 : "cannot set loop-depth twice"; + int i; + int loopDepth = 0; + int minLoopIdx = -1; + for (i = numLoops - 1; i >= 0; i--) { + if (isBlockInLoop(i, cur)) { + loopDepth++; + minLoopIdx = i; + } + } + cur.setLoopDepth(loopDepth); + cur.setLoopIndex(minLoopIdx); + + // append all unvisited successors to work list + for (i = cur.numberOfSux() - 1; i >= 0; i--) { + workList.add(cur.suxAt(i)); + } + for (LIRBlock ex : cur.getExceptionHandlerSuccessors()) { + workList.add(ex); + } + } + } while (!workList.isEmpty()); + } + + int computeWeight(LIRBlock cur) { + LIRBlock singleSux = null; + if (cur.numberOfSux() == 1) { + singleSux = cur.suxAt(0); } // limit loop-depth to 15 bit (only for security reason, it will never be so big) - int loopDepth = 0; // TODO(tw): Assign loop depth - int weight = (loopDepth & 0x7FFF) << 16; + int weight = (cur.loopDepth() & 0x7FFF) << 16; int curBit = 15; + // this is necessary for the (very rare) case that two successive blocks have + // the same loop depth, but a different loop index (can happen for endless loops + // with exception handlers) + if (!cur.isLinearScanLoopHeader()) { + weight |= 1 << curBit; + } + curBit--; + + // loop end blocks (blocks that end with a backward branch) are added + // after all other blocks of the loop. + if (!cur.isLinearScanLoopEnd()) { + weight |= 1 << curBit; + } + curBit--; + + // critical edge split blocks are preferred because then they have a greater + // probability to be completely empty + //if (cur.isCriticalEdgeSplit()) { + // weight |= 1 << curBit; + //} + //curBit--; + // exceptions should not be thrown in normal control flow, so these blocks // are added as late as possible - if (!(cur.end() instanceof Throw) && (singleSux == null || !(singleSux.end() instanceof Throw))) { - weight |= (1 << curBit); - } - curBit--; - if (!(cur.end() instanceof Return) && (singleSux == null || !(singleSux.end() instanceof Return))) { - weight |= (1 << curBit); +// if (!(cur.end() instanceof Throw) && (singleSux == null || !(singleSux.end() instanceof Throw))) { +// weight |= 1 << curBit; +// } +// curBit--; +// if (!(cur.end() instanceof Return) && (singleSux == null || !(singleSux.end() instanceof Return))) { +// weight |= 1 << curBit; +// } +// curBit--; + + // exceptions handlers are added as late as possible + if (!cur.isExceptionEntry()) { + weight |= 1 << curBit; } curBit--; @@ -208,7 +394,7 @@ return weight; } - private boolean readyForProcessing(BlockBegin cur) { + boolean readyForProcessing(LIRBlock cur) { // Discount the edge just traveled. // When the number drops to zero, all forward branches were processed if (decForwardBranches(cur) != 0) { @@ -220,7 +406,7 @@ return true; } - private void sortIntoWorkList(BlockBegin cur) { + void sortIntoWorkList(LIRBlock cur) { assert !workList.contains(cur) : "block already in work list"; int curWeight = computeWeight(cur); @@ -243,9 +429,9 @@ workList.set(insertIdx, cur); if (C1XOptions.TraceLinearScanLevel >= 3) { - TTY.println("Sorted B%d into worklist. new worklist:", cur.blockID); + TTY.println("Sorted B%d into worklist. new worklist:", cur.blockID()); for (int i = 0; i < workList.size(); i++) { - TTY.println(String.format("%8d B%02d weight:%6x", i, workList.get(i).blockID, workList.get(i).linearScanNumber())); + TTY.println(String.format("%8d B%02d weight:%6x", i, workList.get(i).blockID(), workList.get(i).linearScanNumber())); } } @@ -255,9 +441,9 @@ } } - private void appendBlock(BlockBegin cur) { + void appendBlock(LIRBlock cur) { if (C1XOptions.TraceLinearScanLevel >= 3) { - TTY.println("appending block B%d (weight 0x%06x) to linear-scan order", cur.blockID, cur.linearScanNumber()); + TTY.println("appending block B%d (weight 0x%06x) to linear-scan order", cur.blockID(), cur.linearScanNumber()); } assert !linearScanOrder.contains(cur) : "cannot add the same block twice"; @@ -268,34 +454,160 @@ linearScanOrder.add(cur); } - private void computeOrder(BlockBegin startBlock) { + void computeOrder(LIRBlock startBlock) { if (C1XOptions.TraceLinearScanLevel >= 3) { TTY.println("----- computing final block order"); } // the start block is always the first block in the linear scan order - linearScanOrder = new ArrayList<BlockBegin>(numBlocks); + linearScanOrder = new ArrayList<LIRBlock>(numBlocks); + appendBlock(startBlock); + + LIRBlock stdEntry = startBlock.suxAt(0); // start processing with standard entry block assert workList.isEmpty() : "list must be empty before processing"; - if (readyForProcessing(startBlock)) { - sortIntoWorkList(startBlock); + if (readyForProcessing(stdEntry)) { + sortIntoWorkList(stdEntry); } else { throw new CiBailout("the stdEntry must be ready for processing (otherwise, the method has no start block)"); } do { - final BlockBegin cur = workList.remove(workList.size() - 1); + LIRBlock cur = workList.remove(workList.size() - 1); + appendBlock(cur); - cur.allSuccessorsDo(false, new BlockClosure() { - public void apply(BlockBegin block) { - if (readyForProcessing(block)) { - sortIntoWorkList(block); + int i; + int numSux = cur.numberOfSux(); + // changed loop order to get "intuitive" order of if- and else-blocks + for (i = 0; i < numSux; i++) { + LIRBlock sux = cur.suxAt(i); + if (readyForProcessing(sux)) { + sortIntoWorkList(sux); + } + } + for (LIRBlock ex : cur.getExceptionHandlerSuccessors()) { + if (readyForProcessing(ex)) { + sortIntoWorkList(ex); + } + } + } while (workList.size() > 0); + } + + public void printBlocks() { + if (C1XOptions.TraceLinearScanLevel >= 2) { + TTY.println("----- loop information:"); + for (LIRBlock cur : linearScanOrder) { + TTY.print(String.format("%4d: B%02d: ", cur.linearScanNumber(), cur.blockID())); + for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) { + TTY.print(String.format("%d = %b ", loopIdx, isBlockInLoop(loopIdx, cur))); + } + TTY.println(String.format(" . loopIndex: %2d, loopDepth: %2d", cur.loopIndex(), cur.loopDepth())); + } + } + + if (C1XOptions.TraceLinearScanLevel >= 1) { + TTY.println("----- linear-scan block order:"); + for (LIRBlock cur : linearScanOrder) { + TTY.print(String.format("%4d: B%02d loop: %2d depth: %2d", cur.linearScanNumber(), cur.blockID(), cur.loopIndex(), cur.loopDepth())); + + TTY.print(cur.isExceptionEntry() ? " ex" : " "); + TTY.print(cur.isLinearScanLoopHeader() ? " lh" : " "); + TTY.print(cur.isLinearScanLoopEnd() ? " le" : " "); + + TTY.print(" dom: null "); + + + if (cur.numberOfPreds() > 0) { + TTY.print(" preds: "); + for (int j = 0; j < cur.numberOfPreds(); j++) { + LIRBlock pred = cur.predAt(j); + TTY.print("B%d ", pred.blockID()); + } + } + if (cur.numberOfSux() > 0) { + TTY.print(" sux: "); + for (int j = 0; j < cur.numberOfSux(); j++) { + LIRBlock sux = cur.suxAt(j); + TTY.print("B%d ", sux.blockID()); } } - }); - } while (workList.size() > 0); + TTY.println(); + } + } + } + + boolean verify() { + /* assert linearScanOrder.size() == numBlocks : "wrong number of blocks in list"; + + if (C1XOptions.StressLinearScan) { + // blocks are scrambled when StressLinearScan is used + return true; + } + + // check that all successors of a block have a higher linear-scan-number + // and that all predecessors of a block have a lower linear-scan-number + // (only backward branches of loops are ignored) + int i; + for (i = 0; i < linearScanOrder.size(); i++) { + BlockBegin cur = linearScanOrder.get(i); + + assert cur.linearScanNumber() == i : "incorrect linearScanNumber"; + assert cur.linearScanNumber() >= 0 && cur.linearScanNumber() == linearScanOrder.indexOf(cur) : "incorrect linearScanNumber"; + + for (BlockBegin sux : cur.end().successors()) { + assert sux.linearScanNumber() >= 0 && sux.linearScanNumber() == linearScanOrder.indexOf(sux) : "incorrect linearScanNumber"; + if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopEnd)) { + assert cur.linearScanNumber() < sux.linearScanNumber() : "invalid order"; + } + if (cur.loopDepth() == sux.loopDepth()) { + assert cur.loopIndex() == sux.loopIndex() || sux.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index"; + } + } + + for (BlockBegin pred : cur.predecessors()) { + assert pred.linearScanNumber() >= 0 && pred.linearScanNumber() == linearScanOrder.indexOf(pred) : "incorrect linearScanNumber"; + if (!cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader)) { + assert cur.linearScanNumber() > pred.linearScanNumber() : "invalid order"; + } + if (cur.loopDepth() == pred.loopDepth()) { + assert cur.loopIndex() == pred.loopIndex() || cur.checkBlockFlag(BlockBegin.BlockFlag.LinearScanLoopHeader) : "successing blocks with same loop depth must have same loop index"; + } + + assert cur.dominator().linearScanNumber() <= pred.linearScanNumber() : "dominator must be before predecessors"; + } + + // check dominator + if (i == 0) { + assert cur.dominator() == null : "first block has no dominator"; + } else { + assert cur.dominator() != null : "all but first block must have dominator"; + } + assert cur.numberOfPreds() != 1 || cur.dominator() == cur.predAt(0) || cur.isExceptionEntry() : "Single predecessor must also be dominator"; + } + + // check that all loops are continuous + for (int loopIdx = 0; loopIdx < numLoops; loopIdx++) { + int blockIdx = 0; + assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "the first block must not be present in any loop"; + + // skip blocks before the loop + while (blockIdx < numBlocks && !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) { + blockIdx++; + } + // skip blocks of loop + while (blockIdx < numBlocks && isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx))) { + blockIdx++; + } + // after the first non-loop block : there must not be another loop-block + while (blockIdx < numBlocks) { + assert !isBlockInLoop(loopIdx, linearScanOrder.get(blockIdx)) : "loop not continuous in linear-scan order"; + blockIdx++; + } + } +*/ + return true; } }
--- a/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java Tue May 24 14:40:47 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java Tue May 24 21:39:45 2011 +0200 @@ -29,7 +29,6 @@ import com.sun.c1x.debug.*; import com.sun.c1x.ir.*; import com.sun.c1x.util.*; -import com.sun.c1x.value.*; import com.sun.cri.ci.*; /** @@ -43,7 +42,7 @@ private List<Instruction> instructions = new ArrayList<Instruction>(4); private List<LIRBlock> predecessors = new ArrayList<LIRBlock>(4); private List<LIRBlock> successors = new ArrayList<LIRBlock>(4); - private List<Phi> phis = new ArrayList<Phi>(4); + private List<LIRBlock> exceptionHandlerSuccessors = new ArrayList<LIRBlock>(4); /** * Bit map specifying which {@linkplain OperandPool operands} are live upon entry to this block. @@ -78,6 +77,10 @@ private int lastLirInstructionID; public int blockEntryPco; + public List<LIRBlock> getExceptionHandlerSuccessors() { + return exceptionHandlerSuccessors; + } + public LIRBlock(int blockID) { this.blockID = blockID; loopIndex = -1; @@ -105,7 +108,6 @@ } public int loopDepth; - public int loopIndex; public LIRList lir() { return lir; @@ -151,6 +153,11 @@ return successors; } + @Override + public String toString() { + return "B" + blockID(); + } + public List<LIRBlock> blockPredecessors() { return predecessors; } @@ -161,10 +168,19 @@ } public int loopIndex() { - // TODO(tw): Set correct loop index. - return -1; + return loopIndex; + } + + public void setLoopIndex(int v) { + loopIndex = v; } + public void setLoopDepth(int v) { + this.loopDepth = v; + } + + private int loopIndex; + public Label label() { return label; } @@ -172,7 +188,25 @@ private int linearScanNumber = -1; private boolean linearScanLoopEnd; private boolean linearScanLoopHeader; - private FrameState stateBefore; + private boolean exceptionEntry; + private boolean backwardBranchTarget; + + + public void setExceptionEntry(boolean b) { + this.exceptionEntry = b; + } + + public boolean isExceptionEntry() { + return exceptionEntry; + } + + public void setBackwardBranchTarget(boolean b) { + this.backwardBranchTarget = b; + } + + public boolean backwardBranchTarget() { + return backwardBranchTarget; + } public void setLinearScanNumber(int v) { linearScanNumber = v; @@ -198,14 +232,6 @@ return linearScanLoopHeader; } - public void setStateBefore(FrameState stateBefore) { - this.stateBefore = stateBefore; - } - - public FrameState stateBefore() { - return stateBefore; - } - public void replaceWith(LIRBlock other) { for (LIRBlock pred : predecessors) { Util.replaceAllInList(this, other, pred.successors);
--- a/graal/GraalCompiler/src/com/sun/c1x/util/BitMap2D.java Tue May 24 14:40:47 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/util/BitMap2D.java Tue May 24 21:39:45 2011 +0200 @@ -40,7 +40,8 @@ } private boolean verifyBitWithinSlotIndex(int index) { - return index < bitsPerSlot; + assert index < bitsPerSlot : "index " + index + " is out of bounds " + bitsPerSlot; + return true; } public BitMap2D(int sizeInSlots, int bitsPerSlot) {
--- a/runtests.sh Tue May 24 14:40:47 2011 +0200 +++ b/runtests.sh Tue May 24 21:39:45 2011 +0200 @@ -12,4 +12,4 @@ exit 1; fi TESTDIR=${MAXINE}/com.oracle.max.vm/test -${JDK7}/bin/java -client -d64 -graal -ea -esa -Xcomp -C1X:-PrintCFGToFile -XX:-TraceDeoptimization -XX:-TraceExceptions -XX:+PrintCompilation -XX:CompileOnly=jtt -Xbootclasspath/p:"${MAXINE}/com.oracle.max.vm/bin" -C1X:-PrintAssembly -Xbootclasspath/p:"${MAXINE}/com.oracle.max.base/bin" $1 test.com.sun.max.vm.compiler.JavaTester -verbose=1 -gen-run-scheme=false -run-scheme-package=all ${TESTDIR}/jtt/bytecode ${TESTDIR}/jtt/except ${TESTDIR}/jtt/hotpath ${TESTDIR}/jtt/jdk ${TESTDIR}/jtt/lang ${TESTDIR}/jtt/loop ${TESTDIR}/jtt/micro ${TESTDIR}/jtt/optimize ${TESTDIR}/jtt/reflect ${TESTDIR}/jtt/threads +${JDK7}/bin/java -client -d64 -graal -ea -esa -Xcomp -C1X:PrintIdealGraphLevel=0 -C1X:-PrintCFGToFile -C1X:-PrintAssembly -XX:-TraceSignals -XX:-TraceDeoptimization -XX:-TraceExceptions -XX:+PrintCompilation -XX:CompileOnly=jtt -Xbootclasspath/p:"${MAXINE}/com.oracle.max.vm/bin" -Xbootclasspath/p:"${MAXINE}/com.oracle.max.base/bin" $1 test.com.sun.max.vm.compiler.JavaTester -verbose=1 -gen-run-scheme=false -run-scheme-package=all ${TESTDIR}/jtt/bytecode ${TESTDIR}/jtt/except ${TESTDIR}/jtt/hotpath ${TESTDIR}/jtt/jdk ${TESTDIR}/jtt/lang ${TESTDIR}/jtt/loop ${TESTDIR}/jtt/micro ${TESTDIR}/jtt/optimize ${TESTDIR}/jtt/reflect ${TESTDIR}/jtt/threads