# HG changeset patch # User Christian.Wimmer@Oracle.com # Date 1305320372 25200 # Node ID bcd20d26d52df59a5bf147b4b8cfaf7061b4e0d6 # Parent 35453d725a2aa4d0ca82e0f207a2d5d165ee5de8 Refactoring of BlockMap so that it doesn't create BlockBegin objects, but maintains its own Block data structure diff -r 35453d725a2a -r bcd20d26d52d graal/GraalCompiler/src/com/sun/c1x/C1XCompilation.java --- a/graal/GraalCompiler/src/com/sun/c1x/C1XCompilation.java Thu May 12 17:57:58 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/C1XCompilation.java Fri May 13 13:59:32 2011 -0700 @@ -169,18 +169,13 @@ */ public BlockMap getBlockMap(RiMethod method) { // PERF: cache the block map for methods that are compiled or inlined often - BlockMap map = new BlockMap(method, hir.numberOfBlocks(), graph); - if (!map.build(C1XOptions.PhiLoopStores)) { - throw new CiBailout("build of BlockMap failed for " + method); - } else { - if (compiler.isObserved()) { - String label = CiUtil.format("BlockListBuilder %f %r %H.%n(%p)", method, true); - compiler.fireCompilationEvent(new CompilationEvent(this, label, map, method.code().length)); - } + BlockMap map = new BlockMap(method); + map.build(); + if (compiler.isObserved()) { + String label = CiUtil.format("BlockListBuilder %f %r %H.%n(%p)", method, true); + compiler.fireCompilationEvent(new CompilationEvent(this, label, map, method.code().length)); } - map.cleanup(); - stats.bytecodeCount += map.numberOfBytes(); - stats.blockCount += map.numberOfBlocks(); + stats.bytecodeCount += method.code().length; return map; } diff -r 35453d725a2a -r bcd20d26d52d graal/GraalCompiler/src/com/sun/c1x/C1XOptions.java --- a/graal/GraalCompiler/src/com/sun/c1x/C1XOptions.java Thu May 12 17:57:58 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/C1XOptions.java Fri May 13 13:59:32 2011 -0700 @@ -137,6 +137,8 @@ public static boolean UseXmmLoadAndClearUpper = ____; public static boolean UseXmmRegToRegMoveAll = ____; + public static boolean StressImplicitExceptions = ____; + static { setOptimizationLevel(1); } diff -r 35453d725a2a -r bcd20d26d52d graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java --- a/graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java Thu May 12 17:57:58 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/debug/CFGPrinter.java Fri May 13 13:59:32 2011 -0700 @@ -565,11 +565,10 @@ public void printCFG(RiMethod method, BlockMap blockMap, int codeSize, String label, boolean printHIR, boolean printLIR) { begin("cfg"); out.print("name \"").print(label).println('"'); - for (int bci = 0; bci < codeSize; ++bci) { - BlockBegin block = blockMap.get(bci); - if (block != null) { - printBlock(block, Arrays.asList(blockMap.getSuccessors(block)), blockMap.getHandlers(block), printHIR, printLIR); - } + for (BlockMap.Block block : blockMap.blocks) { + begin("block"); + blockMap.printBlock(block, out); + end("block"); } end("cfg"); } diff -r 35453d725a2a -r bcd20d26d52d graal/GraalCompiler/src/com/sun/c1x/graph/BlockMap.java --- a/graal/GraalCompiler/src/com/sun/c1x/graph/BlockMap.java Thu May 12 17:57:58 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/BlockMap.java Fri May 13 13:59:32 2011 -0700 @@ -26,9 +26,7 @@ import java.util.*; -import com.oracle.graal.graph.*; -import com.sun.c1x.ir.*; -import com.sun.c1x.util.*; +import com.sun.c1x.debug.*; import com.sun.cri.bytecode.*; import com.sun.cri.ci.*; import com.sun.cri.ri.*; @@ -114,279 +112,117 @@ * mark all local variables that are stored in the blocks in the list. */ public final class BlockMap { + public class Block { + public int startBci; + public int endBci; + public boolean isExceptionEntry; + public boolean isLoopHeader; - private static final BlockBegin[] NONE = {}; - private static final List NONE_LIST = Collections.emptyList(); + private Block[] successors; + private boolean visited; + private boolean active; + private int loops; + } + + private static final Block[] NO_SUCCESSORS = new Block[0]; /** - * The {@code ExceptionMap} class is used internally to track exception handlers - * while iterating over the bytecode and the control flow graph. Since methods with - * exception handlers are much less frequent than those without, the common case - * does not need to construct an exception map. + * The blocks found in this method, in reverse postorder. */ - private class ExceptionMap { - private final CiBitMap canTrap; - private final boolean isObjectInit; - private final RiExceptionHandler[] allHandlers; - private final ArrayMap> handlerMap; - - ExceptionMap(RiMethod method, byte[] code) { - canTrap = new CiBitMap(code.length); - isObjectInit = (method.isConstructor() && method.holder().superType() == null); - allHandlers = method.exceptionHandlers(); - handlerMap = new ArrayMap>(firstBlock, firstBlock + code.length / 5); - } - - void setCanTrap(int bci) { - canTrap.set(bci); - } - - void addHandlers(BlockBegin block, int bci) { - if (canTrap.get(bci)) { - // XXX: replace with faster algorithm (sort exception handlers by start and end) - for (RiExceptionHandler h : allHandlers) { - if (h.startBCI() <= bci && bci < h.endBCI()) { - addHandler(block, get(h.handlerBCI())); - if (h.isCatchAll()) { - break; - } - } - } - } - } - - Collection getHandlers(BlockBegin block) { - // lookup handlers for the basic block - HashSet set = handlerMap.get(block.blockID); - return set == null ? NONE_LIST : set; - } - - void setHandlerEntrypoints() { - // start basic blocks at all exception handler blocks and mark them as exception entries - for (RiExceptionHandler h : allHandlers) { - addEntrypoint(h.handlerBCI(), BlockBegin.BlockFlag.ExceptionEntry); - } - } - - void addHandler(BlockBegin block, BlockBegin handler) { - // add a handler to a basic block, creating the set if necessary - HashSet set = handlerMap.get(block.blockID); - if (set == null) { - set = new HashSet(); - handlerMap.put(block.blockID, set); - } - set.add(handler); - } - } - - /** The bytecodes for the associated method. */ - private final byte[] code; + public final List blocks; /** - * Every {@link BlockBegin} node created by {@link BlockMap#build} has an entry in this - * array at the corresponding bytecode index. Length is same as {@link BlockMap#code}. - */ - private final BlockBegin[] blockMap; - - /** - * A bit map covering the locals with a bit set for each local that is - * stored to within a loop. This may be conservative depending on the value - * of the {@code computeStoresInLoops} parameters of {@link #build(boolean)}. - */ - private final CiBitMap storesInLoops; - - /** - * Every bytecode instruction that has zero, one or more successor nodes (e.g. {@link Bytecodes#GOTO} has one) has - * an entry in this array at the corresponding bytecode index. The value is another array of {@code BlockBegin} nodes, - * with length equal to the number of successors, whose entries are the {@code BlockBegin} nodes for the successor - * blocks. Length is same as {@link BlockMap#code}. + * A bit map covering the locals with a bit set for each local that might be stored to within a + * loop. If the bit is cleared, it is guaranteed that the local is never stored in a loop. */ - private BlockBegin[][] successorMap; + public final BitSet storesInLoops; - /** List of {@code BlockBegin} nodes that are inside loops. */ - private ArrayList loopBlocks; - private ExceptionMap exceptionMap; + private final RiMethod method; - /** - * The first block number allocated for the blocks within this block map. - */ - private final int firstBlock; + private Block[] blockMap; - /** - * Used for initial block ID (count up) and post-order number (count down). - */ - private int blockNum; - - private final Graph graph; + private BitSet canTrap; /** * Creates a new BlockMap instance from bytecode of the given method . * @param method the compiler interface method containing the code - * @param firstBlockNum the first block number to use when creating {@link BlockBegin} nodes - * @param graph */ - public BlockMap(RiMethod method, int firstBlockNum, Graph graph) { - this.graph = graph; - byte[] code = method.code(); - this.code = code; - firstBlock = firstBlockNum; - blockNum = firstBlockNum; - blockMap = new BlockBegin[code.length]; - successorMap = new BlockBegin[code.length][]; - storesInLoops = new CiBitMap(method.maxLocals()); + public BlockMap(RiMethod method) { + this.method = method; + this.blockMap = new Block[method.code().length]; if (method.exceptionHandlers().length != 0) { - exceptionMap = new ExceptionMap(method, code); - } - } - - /** - * Add an entrypoint to this BlockMap. The resulting block will be marked - * with the specified block flags. - * @param bci the bytecode index of the start of the block - * @param entryFlag the entry flag to mark the block with - */ - public void addEntrypoint(int bci, BlockBegin.BlockFlag entryFlag) { - make(bci).setBlockFlag(entryFlag); - } - - /** - * Gets the block that begins at the specified bytecode index. - * @param bci the bytecode index of the start of the block - * @return the block starting at the specified index, if it exists; {@code null} otherwise - */ - public BlockBegin get(int bci) { - if (bci < blockMap.length) { - return blockMap[bci]; + this.canTrap = new BitSet(blockMap.length); } - return null; - } - - private BlockBegin make(int bci) { - BlockBegin block = blockMap[bci]; - if (block == null) { - block = new BlockBegin(bci, blockNum++, graph); - blockMap[bci] = block; - } - return block; - } - - /** - * Gets a conservative approximation of the successors of a given block. - * @param block the block for which to get the successors - * @return an array of the successors of the specified block - */ - public BlockBegin[] getSuccessors(BlockBegin block) { - BlockBegin[] succ = successorMap[block.bci()]; - return succ == null ? NONE : succ; - } - - /** - * Gets the exception handlers for a specified block. Note that this - * set of exception handlers takes into account whether the block contains - * bytecodes that can cause traps or not. - * @param block the block for which to get the exception handlers - * @return an array of the blocks which represent exception handlers; a zero-length - * array of blocks if there are no handlers that cover any potentially trapping - * instruction in the specified block - */ - public Collection getHandlers(BlockBegin block) { - if (exceptionMap == null) { - return NONE_LIST; - } - return exceptionMap.getHandlers(block); + this.blocks = new ArrayList(); + this.storesInLoops = new BitSet(method.maxLocals()); } /** * Builds the block map and conservative CFG and numbers blocks. - * @param computeStoresInLoops {@code true} if the block map builder should - * make a second pass over the bytecodes for blocks in loops - * @return {@code true} if the block map was built successfully; {@code false} otherwise */ - public boolean build(boolean computeStoresInLoops) { - if (exceptionMap != null) { - exceptionMap.setHandlerEntrypoints(); - } + public void build() { + makeExceptionEntries(); iterateOverBytecodes(); - moveSuccessorLists(); - computeBlockNumbers(); - if (computeStoresInLoops) { - // process any blocks in loops to compute their stores - // (requires another pass, but produces fewer phi's and ultimately better code) - processLoopBlocks(); - } else { - // be conservative and assume all locals are potentially stored in loops - // (does not require another pass, but produces more phi's and worse code) - storesInLoops.setAll(); - } - return true; // XXX: what bailout conditions should the BlockMap check? + addExceptionEdges(); + computeBlockOrder(); + + // Discard big arrays so that they can be GCed + blockMap = null; + canTrap = null; } - /** - * Cleans up any internal state not necessary after the initial pass. Note that - * this method discards the conservative CFG edges and only retains the block mapping - * and stores in loops. - */ - public void cleanup() { - // discard internal state no longer needed - successorMap = null; - loopBlocks = null; - exceptionMap = null; + private void makeExceptionEntries() { + // start basic blocks at all exception handler blocks and mark them as exception entries + for (RiExceptionHandler h : method.exceptionHandlers()) { + Block xhandler = makeBlock(h.handlerBCI()); + xhandler.isExceptionEntry = true; + } } - /** - * Gets the number of blocks in this block map. - * @return the number of blocks - */ - public int numberOfBlocks() { - return blockNum - firstBlock; - } - - public int numberOfBytes() { - return code.length; - } - - /** - * Gets the bitmap that indicates which local variables are assigned in loops. - * @return a bitmap which indicates the locals stored in loops - */ - public CiBitMap getStoresInLoops() { - return storesInLoops; - } - - void iterateOverBytecodes() { + private void iterateOverBytecodes() { // iterate over the bytecodes top to bottom. // mark the entrypoints of basic blocks and build lists of successors for // all bytecodes that end basic blocks (i.e. goto, ifs, switches, throw, jsr, returns, ret) + byte[] code = method.code(); + Block current = null; int bci = 0; - ExceptionMap exceptionMap = this.exceptionMap; - byte[] code = this.code; - make(0); while (bci < code.length) { + if (current == null || blockMap[bci] != null) { + Block b = makeBlock(bci); + if (current != null) { + setSuccessors(current.endBci, b); + } + current = b; + } + blockMap[bci] = current; + current.endBci = bci; + int opcode = Bytes.beU1(code, bci); switch (opcode) { - case ATHROW: - if (exceptionMap != null) { - exceptionMap.setCanTrap(bci); - } - // fall through case IRETURN: // fall through case LRETURN: // fall through case FRETURN: // fall through case DRETURN: // fall through case ARETURN: // fall through case WRETURN: // fall through - case RETURN: - if (exceptionMap != null && exceptionMap.isObjectInit) { - exceptionMap.setCanTrap(bci); + case RETURN: { + current = null; + + assert lengthOf(code, bci) == 1; + bci += 1; + break; + } + + case ATHROW: { + current = null; + if (canTrap != null) { + canTrap.set(bci); } - successorMap[bci] = NONE; // end of control flow - bci += 1; // these are all 1 byte opcodes + + assert lengthOf(code, bci) == 1; + bci += 1; break; - - case RET: - successorMap[bci] = NONE; // end of control flow - bci += 2; // ret is 2 bytes - break; + } case IFEQ: // fall through case IFNE: // fall through @@ -404,288 +240,417 @@ case IF_ACMPNE: // fall through case IFNULL: // fall through case IFNONNULL: { - succ2(bci, bci + 3, bci + Bytes.beS2(code, bci + 1)); - bci += 3; // these are all 3 byte opcodes + current = null; + Block b1 = makeBlock(bci + 3); + Block b2 = makeBlock(bci + Bytes.beS2(code, bci + 1)); + setSuccessors(bci, b1, b2); + + assert lengthOf(code, bci) == 3; + bci += 3; break; } case GOTO: { - succ1(bci, bci + Bytes.beS2(code, bci + 1)); - bci += 3; // goto is 3 bytes + current = null; + Block b1 = makeBlock(bci + Bytes.beS2(code, bci + 1)); + setSuccessors(bci, b1); + + assert lengthOf(code, bci) == 3; + bci += 3; break; } case GOTO_W: { - succ1(bci, bci + Bytes.beS4(code, bci + 1)); - bci += 5; // goto_w is 5 bytes - break; - } + current = null; + Block b1 = makeBlock(bci + Bytes.beS4(code, bci + 1)); + setSuccessors(bci, b1); - case JSR: { - int target = bci + Bytes.beS2(code, bci + 1); - succ2(bci, bci + 3, target); // make JSR's a successor or not? - addEntrypoint(target, BlockBegin.BlockFlag.SubroutineEntry); - bci += 3; // jsr is 3 bytes - break; - } - - case JSR_W: { - int target = bci + Bytes.beS4(code, bci + 1); - succ2(bci, bci + 5, target); - addEntrypoint(target, BlockBegin.BlockFlag.SubroutineEntry); - bci += 5; // jsr_w is 5 bytes + assert lengthOf(code, bci) == 5; + bci += 5; break; } case TABLESWITCH: { - BytecodeSwitch sw = new BytecodeTableSwitch(code, bci); - makeSwitchSuccessors(bci, sw); + BytecodeTableSwitch sw = new BytecodeTableSwitch(code, bci); + setSuccessors(bci, makeSwitchSuccessors(sw)); + current = null; + + assert lengthOf(code, bci) == sw.size(); bci += sw.size(); break; } case LOOKUPSWITCH: { - BytecodeSwitch sw = new BytecodeLookupSwitch(code, bci); - makeSwitchSuccessors(bci, sw); + current = null; + BytecodeLookupSwitch sw = new BytecodeLookupSwitch(code, bci); + setSuccessors(bci, makeSwitchSuccessors(sw)); + + assert lengthOf(code, bci) == sw.size(); bci += sw.size(); break; } + + case JSR: { + throw new JSRNotSupportedBailout(); + } + case JSR_W: { + throw new JSRNotSupportedBailout(); + } + case RET: { + throw new JSRNotSupportedBailout(); + } + case WIDE: { + if (canTrap != null && ProfileInformationStub.trappedFrequently(method, bci)) { + canTrap.set(bci); + } + bci += lengthOf(code, bci); break; } default: { - if (exceptionMap != null && canTrap(opcode)) { - exceptionMap.setCanTrap(bci); + if (canTrap != null && ProfileInformationStub.trappedFrequently(method, bci)) { + canTrap.set(bci); } - bci += lengthOf(opcode); // all variable length instructions are handled above + + assert lengthOf(code, bci) == lengthOf(opcode); + bci += lengthOf(opcode); } } } } - private void makeSwitchSuccessors(int bci, BytecodeSwitch tswitch) { - // make a list of all the successors of a switch - int max = tswitch.numberOfCases(); - ArrayList list = new ArrayList(max + 1); - for (int i = 0; i < max; i++) { - list.add(make(tswitch.targetAt(i))); - } - list.add(make(tswitch.defaultTarget())); - successorMap[bci] = list.toArray(new BlockBegin[list.size()]); - } + private Block makeBlock(int startBci) { + Block oldBlock = blockMap[startBci]; + if (oldBlock == null) { + Block newBlock = new Block(); + newBlock.startBci = startBci; + newBlock.successors = NO_SUCCESSORS; + blockMap[startBci] = newBlock; + return newBlock; - private void moveSuccessorLists() { - // move successor lists from the block-ending bytecodes that created them - // to the basic blocks which they end. - // also handle fall-through cases from backwards branches into the middle of a block - // add exception handlers to basic blocks - BlockBegin current = get(0); - ExceptionMap exceptionMap = this.exceptionMap; - for (int bci = 0; bci < blockMap.length; bci++) { - BlockBegin next = blockMap[bci]; - if (next != null && next != current) { - if (current != null) { - // add fall through successor to current block - successorMap[current.bci()] = new BlockBegin[] {next}; - } - current = next; + } else if (oldBlock.startBci != startBci) { + // Backward branch into the middle of an already processed block. + // Add the correct fall-through successor. + Block newBlock = new Block(); + newBlock.startBci = startBci; + newBlock.endBci = oldBlock.endBci; + newBlock.successors = oldBlock.successors; + + oldBlock.endBci = startBci - 1; + oldBlock.successors = new Block[] {newBlock }; + + for (int i = startBci; i <= newBlock.endBci; i++) { + blockMap[i] = newBlock; } - if (exceptionMap != null) { - exceptionMap.addHandlers(current, bci); - } - BlockBegin[] succ = successorMap[bci]; - if (succ != null && current != null) { - // move this successor list to current block - successorMap[bci] = null; - successorMap[current.bci()] = succ; - current = null; - } + return newBlock; + + } else { + return oldBlock; } - assert current == null : "fell off end of code, should end with successor list"; - } - - private void computeBlockNumbers() { - // compute the block number for all blocks - int blockNum = this.blockNum; - int numBlocks = blockNum - firstBlock; - numberBlock(get(0), new CiBitMap(numBlocks), new CiBitMap(numBlocks)); - this.blockNum = blockNum; // _blockNum is used to compute the number of blocks later } - private boolean numberBlock(BlockBegin block, CiBitMap visited, CiBitMap active) { - // number a block with its reverse post-order traversal number - int blockIndex = block.blockID - firstBlock; - - if (visited.get(blockIndex)) { - if (active.get(blockIndex)) { - // reached block via backward branch - block.setParserLoopHeader(true); - addLoopBlock(block); - return true; - } - // return whether the block is already a loop header - return block.isParserLoopHeader(); + private Block[] makeSwitchSuccessors(BytecodeSwitch tswitch) { + int max = tswitch.numberOfCases(); + Block[] successors = new Block[max + 1]; + for (int i = 0; i < max; i++) { + successors[i] = makeBlock(tswitch.targetAt(i)); } - - visited.set(blockIndex); - active.set(blockIndex); + successors[max] = makeBlock(tswitch.defaultTarget()); + return successors; + } - boolean inLoop = false; - for (BlockBegin succ : getSuccessors(block)) { - // recursively process successors - inLoop |= numberBlock(succ, visited, active); - } - if (exceptionMap != null) { - for (BlockBegin succ : exceptionMap.getHandlers(block)) { - // process exception handler blocks - inLoop |= numberBlock(succ, visited, active); + private void setSuccessors(int predBci, Block... successors) { + for (Block sux : successors) { + if (sux.isExceptionEntry) { + throw new CiBailout("Exception handler can be reached by both normal and exceptional control flow"); } } - // clear active bit after successors are processed - active.clear(blockIndex); - block.setDepthFirstNumber(blockNum--); - if (inLoop) { - addLoopBlock(block); - } - - return inLoop; - } - - private void addLoopBlock(BlockBegin block) { - if (loopBlocks == null) { - loopBlocks = new ArrayList(); - } - loopBlocks.add(block); + Block predecessor = blockMap[predBci]; + assert predecessor.successors.length == 0; + predecessor.successors = successors; } - private void processLoopBlocks() { - if (loopBlocks == null) { + private void addExceptionEdges() { + if (canTrap == null) { return; } - for (BlockBegin block : loopBlocks) { - // process all the stores in this block - int bci = block.bci(); - byte[] code = this.code; - while (true) { - // iterate over the bytecodes in this block - int opcode = code[bci] & 0xff; - if (opcode == WIDE) { - bci += processWideStore(code[bci + 1] & 0xff, code, bci); - } else if (isStore(opcode)) { - bci += processStore(opcode, code, bci); - } else { - bci += lengthOf(code, bci); + + Block block = null; + HashSet newSuccessorsOfBlock = new HashSet(); + + for (int bci = canTrap.nextSetBit(0); bci >= 0; bci = canTrap.nextSetBit(bci + 1)) { + Block newBlock = blockMap[bci]; + if (newBlock != block) { + if (block != null) { + block.successors = newSuccessorsOfBlock.toArray(new Block[newSuccessorsOfBlock.size()]); + newSuccessorsOfBlock.clear(); } - if (bci >= code.length || blockMap[bci] != null) { - // stop when we reach the next block - break; + Collections.addAll(newSuccessorsOfBlock, newBlock.successors); + } + block = newBlock; + + for (RiExceptionHandler h : method.exceptionHandlers()) { + if (h.startBCI() <= bci && bci < h.endBCI()) { + newSuccessorsOfBlock.add(blockMap[h.handlerBCI()]); + if (h.isCatchAll()) { + break; + } } } } + if (block != null) { + block.successors = newSuccessorsOfBlock.toArray(new Block[newSuccessorsOfBlock.size()]); + } + } + + private void computeBlockOrder() { + int loop = computeBlockOrder(blockMap[0]); + + if (loop != 0) { + // There is a path from a loop end to the method entry that does not pass the loop header. + // Therefore, the loop is non reducible (has more than one entry). + // We don't want to compile such methods because the IR only supports structured loops. + throw new CiBailout("Non-reducible loop"); + } + + // Convert postorder to the desired reverse postorder. + Collections.reverse(blocks); } - private int processWideStore(int opcode, byte[] code, int bci) { - switch (opcode) { - case IINC: storeOne(Bytes.beU2(code, bci + 2)); return 6; - case ISTORE: storeOne(Bytes.beU2(code, bci + 2)); return 3; - case LSTORE: storeTwo(Bytes.beU2(code, bci + 2)); return 3; - case FSTORE: storeOne(Bytes.beU2(code, bci + 2)); return 3; - case DSTORE: storeTwo(Bytes.beU2(code, bci + 2)); return 3; - case ASTORE: storeOne(Bytes.beU2(code, bci + 2)); return 3; + /** + * The next available loop number. + */ + private int nextLoop = 0; + + /** + * Mark the block as a loop header, using the next available loop number. + * Also checks for corner cases that we don't want to compile. + */ + private void makeLoopHeader(Block block) { + if (!block.isLoopHeader) { + block.isLoopHeader = true; + + if (block.isExceptionEntry) { + // Loops that are implicitly formed by an exception handler lead to all sorts of corner cases. + // Don't compile such methods for now, until we see a concrete case that allows checking for correctness. + throw new CiBailout("Loop formed by an exception handler"); + } + if (nextLoop >= Integer.SIZE) { + // This restriction can be removed by using a fall-back to a BitSet in case we have more than 32 loops + // Don't compile such methods for now, until we see a concrete case that allows checking for correctness. + throw new CiBailout("Too many loops in method"); + } + + assert block.loops == 0; + block.loops = 1 << nextLoop; + nextLoop++; } - return lengthOf(code, bci); + assert Integer.bitCount(block.loops) == 1; } - private int processStore(int opcode, byte[] code, int bci) { - switch (opcode) { - case IINC: storeOne(code[bci + 1] & 0xff); return 3; - case ISTORE: storeOne(code[bci + 1] & 0xff); return 2; - case LSTORE: storeTwo(code[bci + 1] & 0xff); return 2; - case FSTORE: storeOne(code[bci + 1] & 0xff); return 2; - case DSTORE: storeTwo(code[bci + 1] & 0xff); return 2; - case WSTORE: - case ASTORE: storeOne(code[bci + 1] & 0xff); return 2; - case ISTORE_0: // fall through - case ISTORE_1: // fall through - case ISTORE_2: // fall through - case ISTORE_3: storeOne(opcode - ISTORE_0); return 1; - case LSTORE_0: // fall through - case LSTORE_1: // fall through - case LSTORE_2: // fall through - case LSTORE_3: storeTwo(opcode - LSTORE_0); return 1; - case FSTORE_0: // fall through - case FSTORE_1: // fall through - case FSTORE_2: // fall through - case FSTORE_3: storeOne(opcode - FSTORE_0); return 1; - case DSTORE_0: // fall through - case DSTORE_1: // fall through - case DSTORE_2: // fall through - case DSTORE_3: storeTwo(opcode - DSTORE_0); return 1; - case ASTORE_0: // fall through - case ASTORE_1: // fall through - case ASTORE_2: // fall through - case ASTORE_3: storeOne(opcode - ASTORE_0); return 1; - case WSTORE_0: // fall through - case WSTORE_1: // fall through - case WSTORE_2: // fall through - case WSTORE_3: storeOne(opcode - WSTORE_0); return 1; + /** + * Depth-first traversal of the control flow graph. The flag {@linkplain Block#visited} is used to + * visit every block only once. The flag {@linkplain Block#active} is used to detect cycles (backward + * edges). + */ + private int computeBlockOrder(Block block) { + if (block.visited) { + if (block.active) { + // Reached block via backward branch. + makeLoopHeader(block); + } + // Return cached loop information for this block. + return block.loops; + } + + block.visited = true; + block.active = true; + + int loops = 0; + for (Block successor : block.successors) { + // Recursively process successors. + loops |= computeBlockOrder(successor); + } + + if (loops != 0) { + processLoopBlock(block); } - throw Util.shouldNotReachHere(); + if (block.isLoopHeader) { + assert Integer.bitCount(block.loops) == 1; + loops &= ~block.loops; + } + + block.loops = loops; + block.active = false; + blocks.add(block); + + return loops; + } + + private void processLoopBlock(Block block) { + // process all the stores in this block + byte[] code = method.code(); + int bci = block.startBci; + while (bci <= block.endBci) { + int opcode = Bytes.beU1(code, bci); + if (isStore(opcode)) { + processStore(opcode, Bytes.beU1(code, bci + 1)); + + } else if (opcode == WIDE) { + opcode = Bytes.beU1(code, bci + 1); + if (isStore(opcode)) { + processStore(opcode, Bytes.beU2(code, bci + 2)); + } + } + bci += lengthOf(code, bci); + } } - private void storeOne(int local) { - storesInLoops.set(local); - } + private void processStore(int opcode, int local) { + switch (opcode) { + case IINC: + case ISTORE: + case FSTORE: + case WSTORE: + case ASTORE: + storesInLoops.set(local); + break; - private void storeTwo(int local) { - storesInLoops.set(local); - storesInLoops.set(local + 1); - } + case LSTORE: + case DSTORE: + storesInLoops.set(local); + storesInLoops.set(local + 1); + break; - private void succ2(int bci, int s1, int s2) { - successorMap[bci] = new BlockBegin[] {make(s1), make(s2)}; - } + case ISTORE_0: + case FSTORE_0: + case ASTORE_0: + case WSTORE_0: + storesInLoops.set(0); + break; + case ISTORE_1: + case FSTORE_1: + case ASTORE_1: + case WSTORE_1: + storesInLoops.set(1); + break; + case ISTORE_2: + case FSTORE_2: + case ASTORE_2: + case WSTORE_2: + storesInLoops.set(2); + break; + case ISTORE_3: + case FSTORE_3: + case ASTORE_3: + case WSTORE_3: + storesInLoops.set(3); + break; - private void succ1(int bci, int s1) { - successorMap[bci] = new BlockBegin[] {make(s1)}; - } + case LSTORE_0: + case DSTORE_0: + storesInLoops.set(0); + storesInLoops.set(1); + break; + case LSTORE_1: + case DSTORE_1: + storesInLoops.set(1); + storesInLoops.set(2); + break; + case LSTORE_2: + case DSTORE_2: + storesInLoops.set(2); + storesInLoops.set(3); + break; + case LSTORE_3: + case DSTORE_3: + storesInLoops.set(3); + storesInLoops.set(4); + break; - private static StringBuilder append(StringBuilder sb, BlockBegin block) { - return sb.append('B').append(block.blockID).append('@').append(block.bci()); + default: + throw new InternalError("undefined store bytecode"); + } } - @Override - public String toString() { - StringBuilder sb = new StringBuilder(); - for (int bci = 0; bci < blockMap.length; ++bci) { - BlockBegin block = blockMap[bci]; - if (block != null) { - append(sb, block); - if (loopBlocks != null && loopBlocks.contains(block)) { - sb.append("{loop-header}"); - } - if (successorMap != null) { - BlockBegin[] succs = successorMap[bci]; - if (succs != null && succs.length > 0) { - sb.append(" ->"); - for (BlockBegin succ : succs) { - append(sb.append(' '), succ); - } - } - } - Collection handlers = getHandlers(block); - if (!handlers.isEmpty()) { - sb.append(" xhandlers{"); - for (BlockBegin h : handlers) { - append(sb, h).append(' '); - } - sb.append('}'); - } - sb.append(String.format("%n")); + + + /** + * Print block information in the format required by {@linkplain CFGPrinter}. The method must + * be here because it accesses private state of a block. + */ + public void printBlock(Block block, LogStream out) { + out.print("name \"B").print(block.startBci).println('"'); + out.print("from_bci ").println(block.startBci); + out.print("to_bci ").println(block.endBci); + + out.println("predecessors "); + + out.print("successors "); + for (Block succ : block.successors) { + if (!succ.isExceptionEntry) { + out.print("\"B").print(succ.startBci).print("\" "); + } + } + out.println(); + + out.print("xhandlers"); + for (Block succ : block.successors) { + if (succ.isExceptionEntry) { + out.print("\"B").print(succ.startBci).print("\" "); } } - return sb.toString(); + out.println(); + + out.print("flags "); + if (block.isExceptionEntry) { + out.print("\"ex\" "); + } + if (block.isLoopHeader) { + out.print("\"plh\" "); + } + out.println(); + + out.print("loop_depth ").println(Integer.bitCount(block.loops)); } + +// +// private static StringBuilder append(StringBuilder sb, BlockBegin block) { +// return sb.append('B').append(block.blockID).append('@').append(block.bci()); +// } +// +// @Override +// public String toString() { +// StringBuilder sb = new StringBuilder(); +// for (int bci = 0; bci < blockMap.length; ++bci) { +// BlockBegin block = blockMap[bci]; +// if (block != null) { +// append(sb, block); +// if (loopBlocks != null && loopBlocks.contains(block)) { +// sb.append("{loop-header}"); +// } +// if (successorMap != null) { +// BlockBegin[] succs = successorMap[bci]; +// if (succs != null && succs.length > 0) { +// sb.append(" ->"); +// for (BlockBegin succ : succs) { +// append(sb.append(' '), succ); +// } +// } +// } +// Collection handlers = getHandlers(block); +// if (!handlers.isEmpty()) { +// sb.append(" xhandlers{"); +// for (BlockBegin h : handlers) { +// append(sb, h).append(' '); +// } +// sb.append('}'); +// } +// sb.append(String.format("%n")); +// } +// } +// return sb.toString(); +// } } diff -r 35453d725a2a -r bcd20d26d52d graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java --- a/graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java Thu May 12 17:57:58 2011 +0200 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java Fri May 13 13:59:32 2011 -0700 @@ -83,7 +83,7 @@ private final BytecodeStream stream; // the bytecode stream // bci-to-block mapping - private BlockMap blockMap; + private BlockBegin[] blockList; // the constant pool private final RiConstantPool constantPool; @@ -151,17 +151,36 @@ graph.root().setStart(startBlock); // 2. compute the block map, setup exception handlers and get the entrypoint(s) - blockMap = compilation.getBlockMap(rootMethod); - BlockBegin stdEntry = blockMap.get(0); + BlockMap blockMap = compilation.getBlockMap(rootMethod); + + blockList = new BlockBegin[rootMethod.code().length]; + for (int i = 0; i < blockMap.blocks.size(); i++) { + BlockMap.Block block = blockMap.blocks.get(i); + BlockBegin blockBegin = new BlockBegin(block.startBci, ir.nextBlockNumber(), graph); + if (block.isExceptionEntry) { + blockBegin.setBlockFlag(BlockBegin.BlockFlag.ExceptionEntry); + } + if (block.isLoopHeader) { + blockBegin.setBlockFlag(BlockBegin.BlockFlag.ParserLoopHeader); + } + blockBegin.setDepthFirstNumber(blockBegin.blockID); + blockList[block.startBci] = blockBegin; + } + + BlockBegin stdEntry = blockList[0]; curBlock = startBlock; RiExceptionHandler[] handlers = rootMethod.exceptionHandlers(); if (handlers != null && handlers.length > 0) { exceptionHandlers = new ArrayList(handlers.length); for (RiExceptionHandler ch : handlers) { - ExceptionHandler h = new ExceptionHandler(ch); - h.setEntryBlock(blockAt(h.handler.handlerBCI())); - exceptionHandlers.add(h); + BlockBegin entry = blockAtOrNull(ch.handlerBCI()); + // entry == null means that the exception handler is unreachable according to the BlockMap conservative analysis + if (entry != null) { + ExceptionHandler h = new ExceptionHandler(ch); + h.setEntryBlock(entry); + exceptionHandlers.add(h); + } } flags |= Flag.HasHandler.mask; } @@ -950,7 +969,7 @@ } private BlockBegin blockAtOrNull(int bci) { - return blockMap.get(bci); + return blockList[bci]; } private BlockBegin blockAt(int bci) { diff -r 35453d725a2a -r bcd20d26d52d graal/GraalCompiler/src/com/sun/c1x/graph/JSRNotSupportedBailout.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/JSRNotSupportedBailout.java Fri May 13 13:59:32 2011 -0700 @@ -0,0 +1,34 @@ +/* + * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.sun.c1x.graph; + +import com.sun.cri.ci.*; + + +public class JSRNotSupportedBailout extends CiBailout{ + private static final long serialVersionUID = -7476925652727154272L; + + public JSRNotSupportedBailout() { + super("jsr/ret not supported"); + } +} diff -r 35453d725a2a -r bcd20d26d52d graal/GraalCompiler/src/com/sun/c1x/graph/ProfileInformationStub.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/GraalCompiler/src/com/sun/c1x/graph/ProfileInformationStub.java Fri May 13 13:59:32 2011 -0700 @@ -0,0 +1,59 @@ +/* + * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.sun.c1x.graph; + +import static com.sun.cri.bytecode.Bytecodes.*; + +import com.sun.c1x.*; +import com.sun.cri.bytecode.*; +import com.sun.cri.ri.*; + +/** + * A temporary placeholder to bring in profile information to Graal, until we have a definitive interface. + * That allows us to mark dependencies in code that will need fixup in the future. + * + * TODO this class and the signature of its methods i temporary + */ +public class ProfileInformationStub { + + public static boolean trappedFrequently(RiMethod method, int bci) { + + // TODO: Currently, the runtime system does not support deoptimization when a call trhows an exception, + // so mark is a trapping so that explicit exception handler edges are generated. + switch (Bytes.beU1(method.code(), bci)) { + case INVOKESTATIC: + case INVOKESPECIAL: + case INVOKEVIRTUAL: + case INVOKEINTERFACE: { + return true; + } + } + + if (C1XOptions.StressImplicitExceptions && canTrap(method.code()[bci])) { + return true; + } + + return false; + } + +}