Mercurial > hg > truffle
changeset 2782:915456e4959e
Merge
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 25 May 2011 11:15:24 +0200 |
parents | 79dda81dd337 (diff) bda5972a40a5 (current diff) |
children | 9bc0c2eb00d6 |
files | 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/BlockBegin.java graal/GraalCompiler/src/com/sun/c1x/ir/BlockEnd.java graal/GraalGraph/src/com/oracle/graal/graph/NodeArray.java |
diffstat | 22 files changed, 681 insertions(+), 273 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java Wed May 25 11:15:24 2011 +0200 @@ -24,17 +24,25 @@ import java.util.*; +import com.sun.c1x.ir.*; + public class Block { private int blockID; 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); } + public List<Instruction> getInstructions() { + return instructions; + } + public List<Block> getPredecessors() { return Collections.unmodifiableList(predecessors); } @@ -52,6 +60,14 @@ return blockID; } + public void setExceptionEntry(boolean b) { + exceptionEntry = b; + } + + public boolean isExceptionEntry() { + return exceptionEntry; + } + @Override public String toString() { return "B" + blockID;
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java Wed May 25 11:15:24 2011 +0200 @@ -26,6 +26,7 @@ import com.oracle.graal.graph.*; import com.sun.c1x.debug.*; +import com.sun.c1x.ir.*; public class Schedule { @@ -54,35 +55,47 @@ } private Block assignBlock(Node n) { + assert n instanceof BlockBegin : n; Block curBlock = nodeToBlock.get(n); if (curBlock == null) { curBlock = createBlock(); - nodeToBlock.set(n, curBlock); + return assignBlock(n, curBlock); } return curBlock; } - private void identifyBlocks() { - // Identify nodes that form the control flow. - final NodeBitMap topDownBitMap = NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), null, null); - final NodeBitMap combinedBitMap = NodeIterator.iterate(EdgeType.PREDECESSORS, graph.end(), topDownBitMap, null); + private Block assignBlock(Node n, Block b) { + assert nodeToBlock.get(n) == null; + nodeToBlock.set(n, b); + b.getInstructions().add((Instruction) n); + return b; + } + private boolean isCFG(Node n) { + return n != null && (n instanceof Instruction); + } + + private void identifyBlocks() { // Identify blocks. final ArrayList<Node> blockBeginNodes = new ArrayList<Node>(); - NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), combinedBitMap, new NodeVisitor() { + NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start().successors().get(0), null, new NodeVisitor() { @Override - public void visit(Node n) { + public boolean visit(Node n) { + if (!isCFG(n)) { + return false; + } + Node singlePred = null; for (Node pred : n.predecessors()) { - if (pred != null && combinedBitMap.isMarked(pred)) { + if (isCFG(pred)) { if (singlePred == null) { singlePred = pred; } else { // We have more than one predecessor => we are a merge block. assignBlock(n); blockBeginNodes.add(n); - return; + return true; } } } @@ -95,18 +108,33 @@ // We have a single predecessor => check its successor count. int successorCount = 0; for (Node succ : singlePred.successors()) { - if (succ != null && combinedBitMap.isMarked(succ)) { + if (isCFG(succ)) { 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; + return true; } } } - nodeToBlock.set(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; }} ); @@ -114,17 +142,39 @@ for (Node n : blockBeginNodes) { Block block = nodeToBlock.get(n); for (Node pred : n.predecessors()) { - Block predBlock = nodeToBlock.get(pred); - predBlock.addSuccessor(block); + if (isCFG(pred)) { + Block predBlock = nodeToBlock.get(pred); + predBlock.addSuccessor(block); + } } } + + 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()) { @@ -136,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()) { @@ -150,6 +202,6 @@ } TTY.println(); } - } + }*/ } }
--- a/graal/GraalCompiler/src/com/sun/c1x/alloc/ControlFlowOptimizer.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/alloc/ControlFlowOptimizer.java Wed May 25 11:15:24 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 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/alloc/EdgeMoveOptimizer.java Wed May 25 11:15:24 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 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/alloc/LinearScan.java Wed May 25 11:15:24 2011 +0200 @@ -1159,6 +1159,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 +1271,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 +1613,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 +2089,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 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java Wed May 25 11:15:24 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 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/gen/LIRGenerator.java Wed May 25 11:15:24 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())); } @@ -578,7 +578,6 @@ } protected LIRBlock getLIRBlock(Instruction b) { - assert b instanceof BlockBegin : "only BlockBegin, for now..."; return ir.valueToBlock.get(b); } @@ -1266,11 +1265,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 +1281,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/CriticalEdgeFinder.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/CriticalEdgeFinder.java Wed May 25 11:15:24 2011 +0200 @@ -24,9 +24,11 @@ import java.util.*; +import com.oracle.graal.graph.*; import com.sun.c1x.*; import com.sun.c1x.debug.*; import com.sun.c1x.ir.*; +import com.sun.c1x.lir.*; /** * This class finds and splits "critical" edges in the control flow graph. @@ -34,26 +36,31 @@ * has more than one successor and {@code B} has more than one predecessor. Such * edges are split by adding a block between the two blocks. */ -public class CriticalEdgeFinder implements BlockClosure { +public class CriticalEdgeFinder { - private final IR ir; + private final List<LIRBlock> lirBlocks; + private final Graph graph; /** * The graph edges represented as a map from source to target nodes. * Using a linked hash map makes compilation tracing more deterministic and thus eases debugging. */ - private Map<BlockBegin, Set<BlockBegin>> edges = C1XOptions.DetailedAsserts ? - new LinkedHashMap<BlockBegin, Set<BlockBegin>>() : - new HashMap<BlockBegin, Set<BlockBegin>>(); + private Map<LIRBlock, Set<LIRBlock>> edges = C1XOptions.DetailedAsserts ? + new LinkedHashMap<LIRBlock, Set<LIRBlock>>() : + new HashMap<LIRBlock, Set<LIRBlock>>(); - public CriticalEdgeFinder(IR ir) { - this.ir = ir; + public CriticalEdgeFinder(List<LIRBlock> lirBlocks, Graph graph) { + this.lirBlocks = lirBlocks; + this.graph = graph; + for (LIRBlock block : lirBlocks) { + apply(block); + } + } - public void apply(BlockBegin block) { - BlockEnd end = block.end(); - if (end.blockSuccessorCount() >= 2) { - for (BlockBegin succ : end.blockSuccessors()) { + private void apply(LIRBlock block) { + if (block.numberOfSux() >= 2) { + for (LIRBlock succ : block.blockSuccessors()) { if (succ.numberOfPreds() >= 2) { // TODO: (tw) probably we don't have to make it a critical edge if succ only contains the _same_ predecessor multiple times. recordCriticalEdge(block, succ); @@ -62,23 +69,52 @@ } } - private void recordCriticalEdge(BlockBegin block, BlockBegin succ) { + private void recordCriticalEdge(LIRBlock block, LIRBlock succ) { if (!edges.containsKey(block)) { - edges.put(block, new HashSet<BlockBegin>()); + edges.put(block, new HashSet<LIRBlock>()); } edges.get(block).add(succ); } public void splitCriticalEdges() { - for (Map.Entry<BlockBegin, Set<BlockBegin>> entry : edges.entrySet()) { - BlockBegin from = entry.getKey(); - for (BlockBegin to : entry.getValue()) { - BlockBegin split = ir.splitEdge(from, to); + for (Map.Entry<LIRBlock, Set<LIRBlock>> entry : edges.entrySet()) { + LIRBlock from = entry.getKey(); + for (LIRBlock to : entry.getValue()) { + LIRBlock split = splitEdge(from, to); if (C1XOptions.PrintHIR) { - TTY.println("Split edge between block %d and block %d, creating new block %d", from.blockID, to.blockID, split.blockID); + TTY.println("Split edge between block %d and block %d, creating new block %d", from.blockID(), to.blockID(), split.blockID()); } } } } + + + /** + * Creates and inserts a new block between this block and the specified successor, + * altering the successor and predecessor lists of involved blocks appropriately. + * @param source the source of the edge + * @param target the successor before which to insert a block + * @return the new block inserted + */ + public LIRBlock splitEdge(LIRBlock source, LIRBlock target) { + + // create new successor and mark it for special block order treatment + LIRBlock newSucc = new LIRBlock(lirBlocks.size()); + lirBlocks.add(newSucc); + + // This goto is not a safepoint. + Goto e = new Goto(target.getInstructions().get(0), graph); + newSucc.getInstructions().add(e); + + // link predecessor to new block + ((BlockEnd) source.getInstructions().get(source.getInstructions().size() - 1)).successors().replace(target.getInstructions().get(0), newSucc.getInstructions().get(0)); + + source.substituteSuccessor(target, newSucc); + target.substitutePredecessor(source, newSucc); + newSucc.blockPredecessors().add(source); + newSucc.blockSuccessors().add(target); + + return newSucc; + } }
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java Wed May 25 11:15:24 2011 +0200 @@ -24,7 +24,6 @@ import java.util.*; -import com.oracle.graal.graph.*; import com.oracle.max.graal.schedule.*; import com.sun.c1x.*; import com.sun.c1x.debug.*; @@ -82,15 +81,24 @@ Schedule schedule = new Schedule(this.compilation.graph); List<Block> blocks = schedule.getBlocks(); - NodeMap<Block> nodeToBlock = schedule.getNodeToBlock(); + List<LIRBlock> lirBlocks = new ArrayList<LIRBlock>(); Map<Block, LIRBlock> map = new HashMap<Block, LIRBlock>(); for (Block b : blocks) { - map.put(b, new LIRBlock(b.blockID())); + LIRBlock block = new LIRBlock(b.blockID()); + block.setExceptionEntry(b.isExceptionEntry()); + map.put(b, block); + block.setInstructions(b.getInstructions()); + 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()) { @@ -98,12 +106,37 @@ } } - // TODO(tw): Schedule nodes within a block. + + // TODO(tw): Schedule nodes within a block. + + + CriticalEdgeFinder finder = new CriticalEdgeFinder(lirBlocks, compilation.graph); + finder.splitCriticalEdges(); - valueToBlock = computeLinearScanOrder(); + orderedBlocks = lirBlocks; + + valueToBlock = new HashMap<Value, LIRBlock>(); + for (LIRBlock b : orderedBlocks) { + for (Instruction i : b.getInstructions()) { + valueToBlock.put(i, b); + } + } + startBlock = valueToBlock.get(getHIRStartBlock()); + 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++); + } + + + if (C1XOptions.PrintTimers) { C1XTimers.HIR_OPTIMIZE.stop(); } @@ -119,61 +152,6 @@ } } - private Map<Value, LIRBlock> computeLinearScanOrder() { - return makeLinearScanOrder(); - } - - private Map<Value, LIRBlock> makeLinearScanOrder() { - - Map<Value, LIRBlock> valueToBlock = new HashMap<Value, LIRBlock>(); - - if (orderedBlocks == null) { - CriticalEdgeFinder finder = new CriticalEdgeFinder(this); - ((BlockBegin) getHIRStartBlock()).iteratePreOrder(finder); - finder.splitCriticalEdges(); - ComputeLinearScanOrder computeLinearScanOrder = new ComputeLinearScanOrder(compilation.stats.blockCount, (BlockBegin) getHIRStartBlock()); - List<BlockBegin> blocks = computeLinearScanOrder.linearScanOrder(); - orderedBlocks = new ArrayList<LIRBlock>(); - - int z = 0; - for (BlockBegin bb : blocks) { - LIRBlock lirBlock = new LIRBlock(z); - lirBlock.getInstructions().add(bb); - valueToBlock.put(bb, lirBlock); - lirBlock.setLinearScanNumber(bb.linearScanNumber()); - // TODO(tw): Initialize LIRBlock.linearScanLoopHeader and LIRBlock.linearScanLoopEnd - lirBlock.setStateBefore(bb.stateBefore()); - orderedBlocks.add(lirBlock); - ++z; - } - - z = 0; - for (BlockBegin bb : blocks) { - LIRBlock lirBlock = orderedBlocks.get(z); - for (int i = 0; i < bb.numberOfPreds(); ++i) { - lirBlock.blockPredecessors().add(valueToBlock.get(bb.predAt(i).block())); - } - - BlockEnd end = bb.end(); - for (int i = 0; i < end.blockSuccessorCount(); ++i) { - lirBlock.blockSuccessors().add(valueToBlock.get(end.blockSuccessor(i))); - } - - Instruction first = bb; - while (first != null) { - lirBlock.getInstructions().add(first); - first = first.next(); - } - ++z; - } - - startBlock = valueToBlock.get(getHIRStartBlock()); - assert startBlock != null; - compilation.stats.loopCount = computeLinearScanOrder.numLoops(); - } - return valueToBlock; - } - /** * Gets the linear scan ordering of blocks as a list. * @return the blocks in linear scan order @@ -187,7 +165,7 @@ TTY.println("IR for " + compilation.method); final InstructionPrinter ip = new InstructionPrinter(TTY.out()); final BlockPrinter bp = new BlockPrinter(this, ip, cfgOnly); - ((BlockBegin) getHIRStartBlock()).iteratePreOrder(bp); + getHIRStartBlock().iteratePreOrder(bp); } } @@ -206,55 +184,6 @@ } } - /** - * Creates and inserts a new block between this block and the specified successor, - * altering the successor and predecessor lists of involved blocks appropriately. - * @param source the source of the edge - * @param target the successor before which to insert a block - * @return the new block inserted - */ - public BlockBegin splitEdge(BlockBegin source, BlockBegin target) { - int bci = -2; - - int backEdgeIndex = target.predecessors().indexOf(source.end()); - - // create new successor and mark it for special block order treatment - BlockBegin newSucc = new BlockBegin(bci, nextBlockNumber(), false, compilation.graph); - - List<Integer> removePhiInputs = null; - for (int i = backEdgeIndex + 1; i < target.predecessors().size(); ++i) { - if (target.predecessors().get(i) == source.end()) { - if (removePhiInputs == null) { - removePhiInputs = new ArrayList<Integer>(); - } - removePhiInputs.add(i); - } - } - - // This goto is not a safepoint. - Goto e = new Goto(target, compilation.graph); - newSucc.appendNext(e); - e.reorderSuccessor(0, backEdgeIndex); - - // link predecessor to new block - source.end().substituteSuccessor(target, newSucc); - if (removePhiInputs != null && removePhiInputs.size() > 0) { - - for (Node n : target.usages()) { - if (n instanceof Phi) { - Phi phi = (Phi) n; - int correction = 0; - for (int index : removePhiInputs) { - phi.removeInput(index - correction); - correction++; - } - } - } - - } - - return newSucc; - } public int nextBlockNumber() { return compilation.stats.blockCount++;
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/BlockBegin.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/BlockBegin.java Wed May 25 11:15:24 2011 +0200 @@ -342,25 +342,4 @@ public String shortName() { return "BlockBegin #" + blockID; } - - /** - * Iterates over all successors of this block: successors of the end node and exception handler. - */ - public void allSuccessorsDo(boolean backwards, BlockClosure closure) { - BlockEnd end = end(); - if (backwards) { - for (int i = end.blockSuccessorCount() - 1; i >= 0; i--) { - closure.apply(end.blockSuccessor(i)); - } - } else { - for (int i = 0; i < end.blockSuccessorCount(); i++) { - closure.apply(end.blockSuccessor(i)); - } - } - for (Instruction x = next(); x != null; x = x.next()) { - if (x instanceof ExceptionEdgeInstruction && ((ExceptionEdgeInstruction) x).exceptionEdge() != null) { - closure.apply((BlockBegin) ((ExceptionEdgeInstruction) x).exceptionEdge()); - } - } - } }
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/BlockEnd.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/BlockEnd.java Wed May 25 11:15:24 2011 +0200 @@ -52,9 +52,9 @@ /** * The list of instructions that produce input for this instruction. */ - public BlockBegin blockSuccessor(int index) { + public Instruction blockSuccessor(int index) { assert index >= 0 && index < blockSuccessorCount; - return (BlockBegin) successors().get(super.successorCount() + SUCCESSOR_COUNT + index); + return (Instruction) successors().get(super.successorCount() + SUCCESSOR_COUNT + index); } public Instruction setBlockSuccessor(int index, Instruction n) { @@ -123,7 +123,7 @@ * Gets the successor corresponding to the default (fall through) case. * @return the default successor */ - public BlockBegin defaultSuccessor() { + public Instruction defaultSuccessor() { return blockSuccessor(blockSuccessorCount - 1); }
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/ComputeLinearScanOrder.java Wed May 25 11:15:24 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/ir/ExceptionDispatch.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/ExceptionDispatch.java Wed May 25 11:15:24 2011 +0200 @@ -80,7 +80,7 @@ * Gets the block corresponding to the catch block. * @return the true successor */ - public BlockBegin catchSuccessor() { + public Instruction catchSuccessor() { return blockSuccessor(1); } @@ -88,7 +88,7 @@ * Gets the block corresponding to the rest of the dispatch chain. * @return the false successor */ - public BlockBegin otherSuccessor() { + public Instruction otherSuccessor() { return blockSuccessor(0); } @@ -97,7 +97,7 @@ * @param istrue {@code true} if the true successor is requested, {@code false} otherwise * @return the corresponding successor */ - public BlockBegin successor(boolean istrue) { + public Instruction successor(boolean istrue) { return blockSuccessor(istrue ? 1 : 0); }
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Goto.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Goto.java Wed May 25 11:15:24 2011 +0200 @@ -52,6 +52,6 @@ @Override public void print(LogStream out) { - out.print("goto B").print(defaultSuccessor().blockID); + out.print("goto ").print(defaultSuccessor()); } }
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/LookupSwitch.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/LookupSwitch.java Wed May 25 11:15:24 2011 +0200 @@ -81,6 +81,6 @@ out.printf("case %5d: B%d%n", keyAt(i), blockSuccessors().get(i).blockID); } INSTRUCTION.advance(out); - out.print("default : B").print(defaultSuccessor().blockID); + out.print("default : ").print(defaultSuccessor()); } }
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/TableSwitch.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/ir/TableSwitch.java Wed May 25 11:15:24 2011 +0200 @@ -83,6 +83,6 @@ out.printf("case %5d: B%d%n", lowKey() + i, blockSuccessors().get(i).blockID); } INSTRUCTION.advance(out); - out.print("default : B").print(defaultSuccessor().blockID); + out.print("default : ").print(defaultSuccessor()); } }
--- a/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java Wed May 25 11:15:24 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); @@ -219,4 +245,24 @@ successors.clear(); predecessors.clear(); } + + public void setInstructions(List<Instruction> list) { + instructions = list; + } + + public void substituteSuccessor(LIRBlock target, LIRBlock newSucc) { + for (int i = 0; i < successors.size(); ++i) { + if (successors.get(i) == target) { + successors.set(i, newSucc); + } + } + } + + public void substitutePredecessor(LIRBlock source, LIRBlock newSucc) { + for (int i = 0; i < predecessors.size(); ++i) { + if (predecessors.get(i) == source) { + predecessors.set(i, newSucc); + } + } + } }
--- a/graal/GraalCompiler/src/com/sun/c1x/util/BitMap2D.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/util/BitMap2D.java Wed May 25 11:15:24 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/graal/GraalGraph/src/com/oracle/graal/graph/NodeArray.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeArray.java Wed May 25 11:15:24 2011 +0200 @@ -127,6 +127,17 @@ return false; } + public int replace(Node toReplace, Node replacement) { + int result = 0; + for (int i = 0; i < nodes.length; i++) { + if (nodes[i] == toReplace) { + set(i, replacement); + result++; + } + } + return result; + } + public int size() { return nodes.length; }
--- a/graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java Wed May 25 11:15:24 2011 +0200 @@ -35,7 +35,10 @@ while (nodes.size() > 0) { Node n = nodes.remove(); if (visitor != null) { - visitor.visit(n); + boolean followEdges = visitor.visit(n); + if (!followEdges) { + continue; + } } switch(e) { case INPUTS:
--- a/graal/GraalGraph/src/com/oracle/graal/graph/NodeVisitor.java Tue May 24 15:31:52 2011 +0200 +++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeVisitor.java Wed May 25 11:15:24 2011 +0200 @@ -24,5 +24,5 @@ public interface NodeVisitor { - void visit(Node n); + boolean visit(Node n); }
--- a/runtests.sh Tue May 24 15:31:52 2011 +0200 +++ b/runtests.sh Wed May 25 11:15:24 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