Mercurial > hg > graal-compiler
changeset 19486:b53645225e48
Merge.
| author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
|---|---|
| date | Wed, 18 Feb 2015 20:20:46 +0100 |
| parents | 82475095334f (diff) bd2dd97f2bdb (current diff) |
| children | fb38e004503c |
| files | |
| diffstat | 9 files changed, 837 insertions(+), 715 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/AbstractFrameStateBuilder.java Wed Feb 18 16:55:20 2015 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/AbstractFrameStateBuilder.java Wed Feb 18 20:20:46 2015 +0100 @@ -26,7 +26,6 @@ import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; import com.oracle.graal.java.BciBlockMapping.BciBlock; -import com.oracle.graal.java.BciBlockMapping.LocalLiveness; public abstract class AbstractFrameStateBuilder<T extends KindProvider, S extends AbstractFrameStateBuilder<T, S>> {
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java Wed Feb 18 16:55:20 2015 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java Wed Feb 18 20:20:46 2015 +0100 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2009, 2015, 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 @@ -32,8 +32,6 @@ import com.oracle.graal.bytecode.*; import com.oracle.graal.compiler.common.*; import com.oracle.graal.debug.*; -import com.oracle.graal.debug.Debug.Scope; -import com.oracle.graal.nodes.*; /** * Builds a mapping between bytecodes and basic blocks and builds a conservative control flow graph @@ -86,11 +84,6 @@ protected List<BciBlock> successors; private int predecessorCount; - private FixedWithNextNode firstInstruction; - private AbstractFrameStateBuilder<?, ?> entryState; - private FixedWithNextNode[] firstInstructionArray; - private AbstractFrameStateBuilder<?, ?>[] entryStateArray; - private boolean visited; private boolean active; public long loops; @@ -250,7 +243,7 @@ return jsrData; } - public void setEndsWithRet() { + void setEndsWithRet() { getOrCreateJSRData().endsWithRet = true; } @@ -270,7 +263,7 @@ } } - public void setRetSuccessor(BciBlock bciBlock) { + void setRetSuccessor(BciBlock bciBlock) { this.getOrCreateJSRData().retSuccessor = bciBlock; } @@ -313,78 +306,18 @@ } } - public void setJsrScope(JsrScope nextScope) { + void setJsrScope(JsrScope nextScope) { this.getOrCreateJSRData().jsrScope = nextScope; } - public void setJsrSuccessor(BciBlock clone) { + void setJsrSuccessor(BciBlock clone) { this.getOrCreateJSRData().jsrSuccessor = clone; } - public void setJsrReturnBci(int bci) { + void setJsrReturnBci(int bci) { this.getOrCreateJSRData().jsrReturnBci = bci; } - public FixedWithNextNode getFirstInstruction(int dimension) { - if (dimension == 0) { - return firstInstruction; - } else { - if (firstInstructionArray != null && dimension - 1 < firstInstructionArray.length) { - return firstInstructionArray[dimension - 1]; - } else { - return null; - } - } - } - - public void setFirstInstruction(int dimension, FixedWithNextNode firstInstruction) { - if (dimension == 0) { - this.firstInstruction = firstInstruction; - } else { - if (firstInstructionArray == null) { - firstInstructionArray = new FixedWithNextNode[4]; - } - if (dimension - 1 < firstInstructionArray.length) { - // We are within bounds. - } else { - // We are out of bounds. - firstInstructionArray = Arrays.copyOf(firstInstructionArray, Math.max(firstInstructionArray.length * 2, dimension)); - } - - firstInstructionArray[dimension - 1] = firstInstruction; - } - } - - public AbstractFrameStateBuilder<?, ?> getEntryState(int dimension) { - if (dimension == 0) { - return entryState; - } else { - if (entryStateArray != null && dimension - 1 < entryStateArray.length) { - return entryStateArray[dimension - 1]; - } else { - return null; - } - } - } - - public void setEntryState(int dimension, AbstractFrameStateBuilder<?, ?> entryState) { - if (dimension == 0) { - this.entryState = entryState; - } else { - if (entryStateArray == null) { - entryStateArray = new AbstractFrameStateBuilder<?, ?>[4]; - } - if (dimension - 1 < entryStateArray.length) { - // We are within bounds. - } else { - // We are out of bounds. - entryStateArray = Arrays.copyOf(entryStateArray, Math.max(entryStateArray.length * 2, dimension)); - } - - entryStateArray[dimension - 1] = entryState; - } - } - public int getSuccessorCount() { return successors.size(); } @@ -393,7 +326,7 @@ return successors; } - public void setId(int i) { + void setId(int i) { this.id = i; } @@ -424,20 +357,15 @@ private BciBlock[] blocks; public final ResolvedJavaMethod method; public boolean hasJsrBytecodes; - public BciBlock startBlock; - private final BytecodeStream stream; private final ExceptionHandler[] exceptionHandlers; - private BciBlock[] blockMap; + private BciBlock startBlock; private BciBlock[] loopHeaders; private static final int LOOP_HEADER_MAX_CAPACITY = Long.SIZE; private static final int LOOP_HEADER_INITIAL_CAPACITY = 4; - private final boolean doLivenessAnalysis; - public LocalLiveness liveness; private int blocksNotYetAssignedId; - private final boolean consecutiveLoopBlocks; public int returnCount; /** @@ -445,14 +373,9 @@ * * @param method the compiler interface method containing the code */ - private BciBlockMapping(ResolvedJavaMethod method, boolean doLivenessAnalysis, boolean consecutiveLoopBlocks) { - this.doLivenessAnalysis = doLivenessAnalysis; - this.consecutiveLoopBlocks = consecutiveLoopBlocks; + private BciBlockMapping(ResolvedJavaMethod method) { this.method = method; this.exceptionHandlers = method.getExceptionHandlers(); - this.stream = new BytecodeStream(method.getCode()); - int codeSize = method.getCodeSize(); - this.blockMap = new BciBlock[codeSize]; } public BciBlock[] getBlocks() { @@ -466,37 +389,28 @@ /** * Builds the block map and conservative CFG and numbers blocks. */ - public void build() { - makeExceptionEntries(); - iterateOverBytecodes(); + public void build(BytecodeStream stream) { + int codeSize = method.getCodeSize(); + BciBlock[] blockMap = new BciBlock[codeSize]; + makeExceptionEntries(blockMap); + iterateOverBytecodes(blockMap, stream); if (hasJsrBytecodes) { if (!SupportJsrBytecodes.getValue()) { throw new JsrNotSupportedBailout("jsr/ret parsing disabled"); } - createJsrAlternatives(blockMap[0]); + createJsrAlternatives(blockMap, blockMap[0]); } if (Debug.isLogEnabled()) { - this.log("Before BlockOrder"); + this.log(blockMap, "Before BlockOrder"); } - computeBlockOrder(); - fixLoopBits(); - - startBlock = blockMap[0]; + computeBlockOrder(blockMap); + fixLoopBits(blockMap); assert verify(); - // Discard big arrays so that they can be GCed - blockMap = null; + startBlock = blockMap[0]; if (Debug.isLogEnabled()) { - this.log("Before LivenessAnalysis"); - } - if (doLivenessAnalysis) { - try (Scope s = Debug.scope("LivenessAnalysis")) { - liveness = method.getMaxLocals() <= 64 ? new SmallLocalLiveness() : new LargeLocalLiveness(); - liveness.computeLiveness(); - } catch (Throwable e) { - throw Debug.handle(e); - } + this.log(blockMap, "Before LivenessAnalysis"); } } @@ -515,15 +429,15 @@ return true; } - private void makeExceptionEntries() { + private void makeExceptionEntries(BciBlock[] blockMap) { // start basic blocks at all exception handler blocks and mark them as exception entries for (ExceptionHandler h : this.exceptionHandlers) { - BciBlock xhandler = makeBlock(h.getHandlerBCI()); + BciBlock xhandler = makeBlock(blockMap, h.getHandlerBCI()); xhandler.isExceptionEntry = true; } } - private void iterateOverBytecodes() { + private void iterateOverBytecodes(BciBlock[] blockMap, BytecodeStream stream) { // 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) @@ -533,9 +447,9 @@ int bci = stream.currentBCI(); if (current == null || blockMap[bci] != null) { - BciBlock b = makeBlock(bci); + BciBlock b = makeBlock(blockMap, bci); if (current != null) { - addSuccessor(current.endBci, b); + addSuccessor(blockMap, current.endBci, b); } current = b; } @@ -555,9 +469,9 @@ } case ATHROW: { current = null; - ExceptionDispatchBlock handler = handleExceptions(bci); + ExceptionDispatchBlock handler = handleExceptions(blockMap, bci); if (handler != null) { - addSuccessor(bci, handler); + addSuccessor(blockMap, bci, handler); } break; } @@ -578,24 +492,24 @@ case IFNULL: // fall through case IFNONNULL: { current = null; - addSuccessor(bci, makeBlock(stream.readBranchDest())); - addSuccessor(bci, makeBlock(stream.nextBCI())); + addSuccessor(blockMap, bci, makeBlock(blockMap, stream.readBranchDest())); + addSuccessor(blockMap, bci, makeBlock(blockMap, stream.nextBCI())); break; } case GOTO: case GOTO_W: { current = null; - addSuccessor(bci, makeBlock(stream.readBranchDest())); + addSuccessor(blockMap, bci, makeBlock(blockMap, stream.readBranchDest())); break; } case TABLESWITCH: { current = null; - addSwitchSuccessors(bci, new BytecodeTableSwitch(stream, bci)); + addSwitchSuccessors(blockMap, bci, new BytecodeTableSwitch(stream, bci)); break; } case LOOKUPSWITCH: { current = null; - addSwitchSuccessors(bci, new BytecodeLookupSwitch(stream, bci)); + addSwitchSuccessors(blockMap, bci, new BytecodeLookupSwitch(stream, bci)); break; } case JSR: @@ -605,11 +519,11 @@ if (target == 0) { throw new JsrNotSupportedBailout("jsr target bci 0 not allowed"); } - BciBlock b1 = makeBlock(target); + BciBlock b1 = makeBlock(blockMap, target); current.setJsrSuccessor(b1); current.setJsrReturnBci(stream.nextBCI()); current = null; - addSuccessor(bci, b1); + addSuccessor(blockMap, bci, b1); break; } case RET: { @@ -622,11 +536,11 @@ case INVOKESTATIC: case INVOKEVIRTUAL: case INVOKEDYNAMIC: { - ExceptionDispatchBlock handler = handleExceptions(bci); + ExceptionDispatchBlock handler = handleExceptions(blockMap, bci); if (handler != null) { current = null; - addSuccessor(bci, makeBlock(stream.nextBCI())); - addSuccessor(bci, handler); + addSuccessor(blockMap, bci, makeBlock(blockMap, stream.nextBCI())); + addSuccessor(blockMap, bci, handler); } break; } @@ -648,11 +562,11 @@ case SALOAD: case PUTFIELD: case GETFIELD: { - ExceptionDispatchBlock handler = handleExceptions(bci); + ExceptionDispatchBlock handler = handleExceptions(blockMap, bci); if (handler != null) { current = null; - addSuccessor(bci, makeBlock(stream.nextBCI())); - addSuccessor(bci, handler); + addSuccessor(blockMap, bci, makeBlock(blockMap, stream.nextBCI())); + addSuccessor(blockMap, bci, handler); } } } @@ -660,7 +574,7 @@ } } - private BciBlock makeBlock(int startBci) { + private BciBlock makeBlock(BciBlock[] blockMap, int startBci) { BciBlock oldBlock = blockMap[startBci]; if (oldBlock == null) { BciBlock newBlock = new BciBlock(); @@ -694,7 +608,7 @@ } } - private void addSwitchSuccessors(int predBci, BytecodeSwitch bswitch) { + private void addSwitchSuccessors(BciBlock[] blockMap, int predBci, BytecodeSwitch bswitch) { // adds distinct targets to the successor list Collection<Integer> targets = new TreeSet<>(); for (int i = 0; i < bswitch.numberOfCases(); i++) { @@ -702,11 +616,11 @@ } targets.add(bswitch.defaultTarget()); for (int targetBci : targets) { - addSuccessor(predBci, makeBlock(targetBci)); + addSuccessor(blockMap, predBci, makeBlock(blockMap, targetBci)); } } - private void addSuccessor(int predBci, BciBlock sux) { + private static void addSuccessor(BciBlock[] blockMap, int predBci, BciBlock sux) { BciBlock predecessor = blockMap[predBci]; if (sux.isExceptionEntry) { throw new BailoutException("Exception handler can be reached by both normal and exceptional control flow"); @@ -716,7 +630,7 @@ private final ArrayList<BciBlock> jsrVisited = new ArrayList<>(); - private void createJsrAlternatives(BciBlock block) { + private void createJsrAlternatives(BciBlock[] blockMap, BciBlock block) { jsrVisited.add(block); JsrScope scope = block.getJsrScope(); @@ -763,14 +677,14 @@ } for (BciBlock successor : block.getSuccessors()) { if (!jsrVisited.contains(successor)) { - createJsrAlternatives(successor); + createJsrAlternatives(blockMap, successor); } } } private HashMap<ExceptionHandler, ExceptionDispatchBlock> initialExceptionDispatch = CollectionsFactory.newMap(); - private ExceptionDispatchBlock handleExceptions(int bci) { + private ExceptionDispatchBlock handleExceptions(BciBlock[] blockMap, int bci) { ExceptionDispatchBlock lastHandler = null; for (int i = exceptionHandlers.length - 1; i >= 0; i--) { @@ -805,14 +719,14 @@ private boolean loopChanges; - private void fixLoopBits() { + private void fixLoopBits(BciBlock[] blockMap) { do { loopChanges = false; for (BciBlock b : blocks) { b.visited = false; } - long loop = fixLoopBits(blockMap[0]); + long loop = fixLoopBits(blockMap, blockMap[0]); if (loop != 0) { // There is a path from a loop end to the method entry that does not pass the loop @@ -825,7 +739,7 @@ } while (loopChanges); } - private void computeBlockOrder() { + private void computeBlockOrder(BciBlock[] blockMap) { int maxBlocks = blocksNotYetAssignedId; this.blocks = new BciBlock[blocksNotYetAssignedId]; long loop = computeBlockOrder(blockMap[0]); @@ -837,17 +751,9 @@ throw new BailoutException("Non-reducible loop"); } - if (blocks[0] != null && this.nextLoop == 0) { - // No unreached blocks and no loops - for (int i = 0; i < blocks.length; ++i) { - blocks[i].setId(i); - } - return; - } - // Purge null entries for unreached blocks and sort blocks such that loop bodies are always // consecutively in the array. - int blockCount = maxBlocks - blocksNotYetAssignedId; + int blockCount = maxBlocks - blocksNotYetAssignedId + 2; BciBlock[] newBlocks = new BciBlock[blockCount]; int next = 0; for (int i = 0; i < blocks.length; ++i) { @@ -855,11 +761,23 @@ if (b != null) { b.setId(next); newBlocks[next++] = b; - if (consecutiveLoopBlocks && b.isLoopHeader) { + if (b.isLoopHeader) { next = handleLoopHeader(newBlocks, next, i, b); } } } + + // Add return block. + BciBlock returnBlock = new BciBlock(); + returnBlock.setId(newBlocks.length - 2); + newBlocks[newBlocks.length - 2] = returnBlock; + + // Add unwind block. + ExceptionDispatchBlock unwindBlock = new ExceptionDispatchBlock(); + unwindBlock.deoptBci = method.isSynchronized() ? BytecodeFrame.UNWIND_BCI : BytecodeFrame.AFTER_EXCEPTION_BCI; + unwindBlock.setId(newBlocks.length - 1); + newBlocks[newBlocks.length - 1] = unwindBlock; + blocks = newBlocks; } @@ -882,7 +800,7 @@ return next; } - public void log(String name) { + public void log(BciBlock[] blockMap, String name) { if (Debug.isLogEnabled()) { String n = System.lineSeparator(); StringBuilder sb = new StringBuilder(Debug.currentScope()).append("BlockMap ").append(name).append(" :"); @@ -1018,7 +936,7 @@ return loops; } - private long fixLoopBits(BciBlock block) { + private long fixLoopBits(BciBlock[] blockMap, BciBlock block) { if (block.visited) { // Return cached loop information for this block. if (block.isLoopHeader) { @@ -1032,7 +950,7 @@ long loops = block.loops; for (BciBlock successor : block.getSuccessors()) { // Recursively process successors. - loops |= fixLoopBits(successor); + loops |= fixLoopBits(blockMap, successor); } if (block.loops != loops) { loopChanges = true; @@ -1047,241 +965,9 @@ return loops; } - /** - * Encapsulates the liveness calculation, so that subclasses for locals ≤ 64 and locals > - * 64 can be implemented. - */ - public abstract class LocalLiveness { - - private void computeLiveness() { - for (BciBlock block : blocks) { - computeLocalLiveness(block); - } - - boolean changed; - int iteration = 0; - do { - Debug.log("Iteration %d", iteration); - changed = false; - for (int i = blocks.length - 1; i >= 0; i--) { - BciBlock block = blocks[i]; - int blockID = block.getId(); - // log statements in IFs because debugLiveX creates a new String - if (Debug.isLogEnabled()) { - Debug.logv(" start B%d [%d, %d] in: %s out: %s gen: %s kill: %s", block.getId(), block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID), - debugLiveGen(blockID), debugLiveKill(blockID)); - } - - boolean blockChanged = (iteration == 0); - if (block.getSuccessorCount() > 0) { - int oldCardinality = liveOutCardinality(blockID); - for (BciBlock sux : block.getSuccessors()) { - if (Debug.isLogEnabled()) { - Debug.log(" Successor B%d: %s", sux.getId(), debugLiveIn(sux.getId())); - } - propagateLiveness(blockID, sux.getId()); - } - blockChanged |= (oldCardinality != liveOutCardinality(blockID)); - } - - if (blockChanged) { - updateLiveness(blockID); - if (Debug.isLogEnabled()) { - Debug.logv(" end B%d [%d, %d] in: %s out: %s gen: %s kill: %s", block.getId(), block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID), - debugLiveGen(blockID), debugLiveKill(blockID)); - } - } - changed |= blockChanged; - } - iteration++; - } while (changed); - } - - /** - * Returns whether the local is live at the beginning of the given block. - */ - public abstract boolean localIsLiveIn(BciBlock block, int local); - - /** - * Returns whether the local is set in the given loop. - */ - public abstract boolean localIsChangedInLoop(int loopId, int local); - - /** - * Returns whether the local is live at the end of the given block. - */ - public abstract boolean localIsLiveOut(BciBlock block, int local); - - /** - * Returns a string representation of the liveIn values of the given block. - */ - protected abstract String debugLiveIn(int blockID); - - /** - * Returns a string representation of the liveOut values of the given block. - */ - protected abstract String debugLiveOut(int blockID); - - /** - * Returns a string representation of the liveGen values of the given block. - */ - protected abstract String debugLiveGen(int blockID); - - /** - * Returns a string representation of the liveKill values of the given block. - */ - protected abstract String debugLiveKill(int blockID); - - /** - * Returns the number of live locals at the end of the given block. - */ - protected abstract int liveOutCardinality(int blockID); - - /** - * Adds all locals the are in the liveIn of the successor to the liveOut of the block. - */ - protected abstract void propagateLiveness(int blockID, int successorID); - - /** - * Calculates a new liveIn for the given block from liveOut, liveKill and liveGen. - */ - protected abstract void updateLiveness(int blockID); - - /** - * Adds the local to liveGen if it wasn't already killed in this block. - */ - protected abstract void loadOne(int blockID, int local); - - /** - * Add this local to liveKill if it wasn't already generated in this block. - */ - protected abstract void storeOne(int blockID, int local); - - private void computeLocalLiveness(BciBlock block) { - if (block.startBci < 0 || block.endBci < 0) { - return; - } - int blockID = block.getId(); - int localIndex; - stream.setBCI(block.startBci); - while (stream.currentBCI() <= block.endBci) { - switch (stream.currentBC()) { - case LLOAD: - case DLOAD: - loadTwo(blockID, stream.readLocalIndex()); - break; - case LLOAD_0: - case DLOAD_0: - loadTwo(blockID, 0); - break; - case LLOAD_1: - case DLOAD_1: - loadTwo(blockID, 1); - break; - case LLOAD_2: - case DLOAD_2: - loadTwo(blockID, 2); - break; - case LLOAD_3: - case DLOAD_3: - loadTwo(blockID, 3); - break; - case IINC: - localIndex = stream.readLocalIndex(); - loadOne(blockID, localIndex); - storeOne(blockID, localIndex); - break; - case ILOAD: - case FLOAD: - case ALOAD: - case RET: - loadOne(blockID, stream.readLocalIndex()); - break; - case ILOAD_0: - case FLOAD_0: - case ALOAD_0: - loadOne(blockID, 0); - break; - case ILOAD_1: - case FLOAD_1: - case ALOAD_1: - loadOne(blockID, 1); - break; - case ILOAD_2: - case FLOAD_2: - case ALOAD_2: - loadOne(blockID, 2); - break; - case ILOAD_3: - case FLOAD_3: - case ALOAD_3: - loadOne(blockID, 3); - break; - - case LSTORE: - case DSTORE: - storeTwo(blockID, stream.readLocalIndex()); - break; - case LSTORE_0: - case DSTORE_0: - storeTwo(blockID, 0); - break; - case LSTORE_1: - case DSTORE_1: - storeTwo(blockID, 1); - break; - case LSTORE_2: - case DSTORE_2: - storeTwo(blockID, 2); - break; - case LSTORE_3: - case DSTORE_3: - storeTwo(blockID, 3); - break; - case ISTORE: - case FSTORE: - case ASTORE: - storeOne(blockID, stream.readLocalIndex()); - break; - case ISTORE_0: - case FSTORE_0: - case ASTORE_0: - storeOne(blockID, 0); - break; - case ISTORE_1: - case FSTORE_1: - case ASTORE_1: - storeOne(blockID, 1); - break; - case ISTORE_2: - case FSTORE_2: - case ASTORE_2: - storeOne(blockID, 2); - break; - case ISTORE_3: - case FSTORE_3: - case ASTORE_3: - storeOne(blockID, 3); - break; - } - stream.next(); - } - } - - private void loadTwo(int blockID, int local) { - loadOne(blockID, local); - loadOne(blockID, local + 1); - } - - private void storeTwo(int blockID, int local) { - storeOne(blockID, local); - storeOne(blockID, local + 1); - } - } - - public static BciBlockMapping create(ResolvedJavaMethod method, boolean doLivenessAnalysis, boolean consecutiveLoopBlocks) { - BciBlockMapping map = new BciBlockMapping(method, doLivenessAnalysis, consecutiveLoopBlocks); - map.build(); + public static BciBlockMapping create(BytecodeStream stream, ResolvedJavaMethod method) { + BciBlockMapping map = new BciBlockMapping(method); + map.build(stream); if (Debug.isDumpEnabled()) { Debug.dump(map, method.format("After block building %f %R %H.%n(%P)")); } @@ -1289,228 +975,27 @@ return map; } - public final class SmallLocalLiveness extends LocalLiveness { - /* - * local n is represented by the bit accessible as (1 << n) - */ - - private final long[] localsLiveIn; - private final long[] localsLiveOut; - private final long[] localsLiveGen; - private final long[] localsLiveKill; - private final long[] localsChangedInLoop; - - public SmallLocalLiveness() { - int blockSize = blocks.length; - localsLiveIn = new long[blockSize]; - localsLiveOut = new long[blockSize]; - localsLiveGen = new long[blockSize]; - localsLiveKill = new long[blockSize]; - localsChangedInLoop = new long[BciBlockMapping.this.nextLoop]; - } - - private String debugString(long value) { - StringBuilder str = new StringBuilder("{"); - long current = value; - for (int i = 0; i < method.getMaxLocals(); i++) { - if ((current & 1L) == 1L) { - if (str.length() > 1) { - str.append(", "); - } - str.append(i); - } - current >>= 1; - } - return str.append('}').toString(); - } - - @Override - protected String debugLiveIn(int blockID) { - return debugString(localsLiveIn[blockID]); - } - - @Override - protected String debugLiveOut(int blockID) { - return debugString(localsLiveOut[blockID]); - } - - @Override - protected String debugLiveGen(int blockID) { - return debugString(localsLiveGen[blockID]); - } - - @Override - protected String debugLiveKill(int blockID) { - return debugString(localsLiveKill[blockID]); - } - - @Override - protected int liveOutCardinality(int blockID) { - return Long.bitCount(localsLiveOut[blockID]); - } - - @Override - protected void propagateLiveness(int blockID, int successorID) { - localsLiveOut[blockID] |= localsLiveIn[successorID]; - } - - @Override - protected void updateLiveness(int blockID) { - localsLiveIn[blockID] = (localsLiveOut[blockID] & ~localsLiveKill[blockID]) | localsLiveGen[blockID]; - } - - @Override - protected void loadOne(int blockID, int local) { - long bit = 1L << local; - if ((localsLiveKill[blockID] & bit) == 0L) { - localsLiveGen[blockID] |= bit; - } - } - - @Override - protected void storeOne(int blockID, int local) { - long bit = 1L << local; - if ((localsLiveGen[blockID] & bit) == 0L) { - localsLiveKill[blockID] |= bit; - } - - BciBlock block = blocks[blockID]; - long tmp = block.loops; - int pos = 0; - while (tmp != 0) { - if ((tmp & 1L) == 1L) { - this.localsChangedInLoop[pos] |= bit; - } - tmp >>= 1; - ++pos; - } - } - - @Override - public boolean localIsLiveIn(BciBlock block, int local) { - int blockID = block.getId(); - return blockID >= Integer.MAX_VALUE ? false : (localsLiveIn[blockID] & (1L << local)) != 0L; - } - - @Override - public boolean localIsLiveOut(BciBlock block, int local) { - int blockID = block.getId(); - return blockID >= Integer.MAX_VALUE ? false : (localsLiveOut[blockID] & (1L << local)) != 0L; - } - - @Override - public boolean localIsChangedInLoop(int loopId, int local) { - return (localsChangedInLoop[loopId] & (1L << local)) != 0L; - } - } - - public final class LargeLocalLiveness extends LocalLiveness { - private BitSet[] localsLiveIn; - private BitSet[] localsLiveOut; - private BitSet[] localsLiveGen; - private BitSet[] localsLiveKill; - private BitSet[] localsChangedInLoop; - - public LargeLocalLiveness() { - int blocksSize = blocks.length; - localsLiveIn = new BitSet[blocksSize]; - localsLiveOut = new BitSet[blocksSize]; - localsLiveGen = new BitSet[blocksSize]; - localsLiveKill = new BitSet[blocksSize]; - int maxLocals = method.getMaxLocals(); - for (int i = 0; i < blocksSize; i++) { - localsLiveIn[i] = new BitSet(maxLocals); - localsLiveOut[i] = new BitSet(maxLocals); - localsLiveGen[i] = new BitSet(maxLocals); - localsLiveKill[i] = new BitSet(maxLocals); - } - localsChangedInLoop = new BitSet[nextLoop]; - for (int i = 0; i < nextLoop; ++i) { - localsChangedInLoop[i] = new BitSet(maxLocals); - } - } - - @Override - protected String debugLiveIn(int blockID) { - return localsLiveIn[blockID].toString(); - } - - @Override - protected String debugLiveOut(int blockID) { - return localsLiveOut[blockID].toString(); - } - - @Override - protected String debugLiveGen(int blockID) { - return localsLiveGen[blockID].toString(); - } - - @Override - protected String debugLiveKill(int blockID) { - return localsLiveKill[blockID].toString(); - } - - @Override - protected int liveOutCardinality(int blockID) { - return localsLiveOut[blockID].cardinality(); - } - - @Override - protected void propagateLiveness(int blockID, int successorID) { - localsLiveOut[blockID].or(localsLiveIn[successorID]); - } - - @Override - protected void updateLiveness(int blockID) { - BitSet liveIn = localsLiveIn[blockID]; - liveIn.clear(); - liveIn.or(localsLiveOut[blockID]); - liveIn.andNot(localsLiveKill[blockID]); - liveIn.or(localsLiveGen[blockID]); - } - - @Override - protected void loadOne(int blockID, int local) { - if (!localsLiveKill[blockID].get(local)) { - localsLiveGen[blockID].set(local); - } - } - - @Override - protected void storeOne(int blockID, int local) { - if (!localsLiveGen[blockID].get(local)) { - localsLiveKill[blockID].set(local); - } - - BciBlock block = blocks[blockID]; - long tmp = block.loops; - int pos = 0; - while (tmp != 0) { - if ((tmp & 1L) == 1L) { - this.localsChangedInLoop[pos].set(local); - } - tmp >>= 1; - ++pos; - } - } - - @Override - public boolean localIsLiveIn(BciBlock block, int local) { - return block.getId() >= Integer.MAX_VALUE ? true : localsLiveIn[block.getId()].get(local); - } - - @Override - public boolean localIsLiveOut(BciBlock block, int local) { - return block.getId() >= Integer.MAX_VALUE ? true : localsLiveOut[block.getId()].get(local); - } - - @Override - public boolean localIsChangedInLoop(int loopId, int local) { - return localsChangedInLoop[loopId].get(local); - } - } - public BciBlock[] getLoopHeaders() { return loopHeaders; } + + public BciBlock getStartBlock() { + return startBlock; + } + + public BciBlock getReturnBlock() { + return blocks[blocks.length - 2]; + } + + public ExceptionDispatchBlock getUnwindBlock() { + return (ExceptionDispatchBlock) blocks[blocks.length - 1]; + } + + public int getLoopCount() { + return nextLoop; + } + + public int getBlockCount() { + return blocks.length; + } }
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Wed Feb 18 16:55:20 2015 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Wed Feb 18 20:20:46 2015 +0100 @@ -40,13 +40,13 @@ import com.oracle.graal.compiler.common.calc.*; import com.oracle.graal.compiler.common.type.*; import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.*; import com.oracle.graal.graph.Graph.Mark; import com.oracle.graal.graph.*; import com.oracle.graal.graph.Node.ValueNumberable; import com.oracle.graal.graph.iterators.*; import com.oracle.graal.java.BciBlockMapping.BciBlock; import com.oracle.graal.java.BciBlockMapping.ExceptionDispatchBlock; -import com.oracle.graal.java.BciBlockMapping.LocalLiveness; import com.oracle.graal.java.GraphBuilderPlugin.AnnotatedInvocationPlugin; import com.oracle.graal.java.GraphBuilderPlugin.InlineInvokePlugin; import com.oracle.graal.java.GraphBuilderPlugin.InvocationPlugin; @@ -173,7 +173,7 @@ public class BytecodeParser extends AbstractBytecodeParser<ValueNode, HIRFrameStateBuilder> implements GraphBuilderContext { - private BciBlock[] loopHeaders; + private BciBlockMapping blockMap; private LocalLiveness liveness; protected final int entryBCI; private int currentDepth; @@ -183,8 +183,6 @@ private int currentLineNumber; private ValueNode methodSynchronizedObject; - private ExceptionDispatchBlock unwindBlock; - private BciBlock returnBlock; private ValueNode returnValue; private FixedWithNextNode beforeReturnNode; @@ -195,9 +193,13 @@ private final boolean explodeLoops; private Stack<ExplodedLoopContext> explodeLoopsContext; private int nextPeelIteration = 1; - private int returnCount; private boolean controlFlowSplit; + private FixedWithNextNode[] firstInstructionArray; + private AbstractFrameStateBuilder<?, ?>[] entryStateArray; + private FixedWithNextNode[][] firstInstructionMatrix; + private AbstractFrameStateBuilder<?, ?>[][] entryStateMatrix; + /** * @param isReplacement specifies if this object is being used to parse a method that * implements the semantics of another method (i.e., an intrinsic) or @@ -247,20 +249,31 @@ try (Indent indent = Debug.logAndIndent("build graph for %s", method)) { // compute the block map, setup exception handlers and get the entrypoint(s) - BciBlockMapping blockMap = BciBlockMapping.create(method, graphBuilderConfig.doLivenessAnalysis(), explodeLoops); - loopHeaders = blockMap.getLoopHeaders(); - liveness = blockMap.liveness; - returnCount = blockMap.getReturnCount(); + BciBlockMapping newMapping = BciBlockMapping.create(stream, method); + this.blockMap = newMapping; + this.firstInstructionArray = new FixedWithNextNode[blockMap.getBlockCount()]; + this.entryStateArray = new AbstractFrameStateBuilder<?, ?>[blockMap.getBlockCount()]; + + if (graphBuilderConfig.doLivenessAnalysis()) { + try (Scope s = Debug.scope("LivenessAnalysis")) { + int maxLocals = method.getMaxLocals(); + liveness = LocalLiveness.compute(stream, blockMap.getBlocks(), maxLocals, blockMap.getLoopCount()); + } catch (Throwable e) { + throw Debug.handle(e); + } + } lastInstr = startInstruction; this.setCurrentFrameState(startFrameState); + stream.setBCI(0); + BciBlock startBlock = blockMap.getStartBlock(); if (startInstruction == currentGraph.start()) { StartNode startNode = currentGraph.start(); if (method.isSynchronized()) { startNode.setStateAfter(frameState.create(BytecodeFrame.BEFORE_BCI)); } else { - frameState.clearNonLiveLocals(blockMap.startBlock, liveness, true); + frameState.clearNonLiveLocals(startBlock, liveness, true); assert bci() == 0; startNode.setStateAfter(frameState.create(bci())); } @@ -270,7 +283,7 @@ // add a monitor enter to the start block methodSynchronizedObject = synchronizedObject(frameState, method); MonitorEnterNode monitorEnter = genMonitorEnter(methodSynchronizedObject); - frameState.clearNonLiveLocals(blockMap.startBlock, liveness, true); + frameState.clearNonLiveLocals(startBlock, liveness, true); assert bci() == 0; monitorEnter.setStateAfter(frameState.create(bci())); } @@ -279,12 +292,12 @@ append(createInfoPointNode(InfopointReason.METHOD_START)); } - currentBlock = blockMap.startBlock; - blockMap.startBlock.setEntryState(0, frameState); - if (blockMap.startBlock.isLoopHeader && !explodeLoops) { - appendGoto(blockMap.startBlock); + currentBlock = blockMap.getStartBlock(); + setEntryState(startBlock, 0, frameState); + if (startBlock.isLoopHeader && !explodeLoops) { + appendGoto(startBlock); } else { - blockMap.startBlock.setFirstInstruction(0, lastInstr); + setFirstInstruction(startBlock, 0, lastInstr); } int index = 0; @@ -293,8 +306,6 @@ BciBlock block = blocks[index]; index = iterateBlock(blocks, block); } - processBlock(this, returnBlock); - processBlock(this, unwindBlock); if (Debug.isDumpEnabled() && this.beforeReturnNode != startInstruction) { Debug.dump(currentGraph, "Bytecodes parsed: " + method.getDeclaringClass().getUnqualifiedName() + "." + method.getName()); @@ -344,27 +355,6 @@ return header.loopEnd + 1; } - private BciBlock returnBlock(int bci) { - if (returnBlock == null) { - returnBlock = new BciBlock(); - returnBlock.startBci = bci; - returnBlock.endBci = bci; - returnBlock.setId(Integer.MAX_VALUE); - } - return returnBlock; - } - - private BciBlock unwindBlock() { - if (unwindBlock == null) { - unwindBlock = new ExceptionDispatchBlock(); - unwindBlock.startBci = -1; - unwindBlock.endBci = -1; - unwindBlock.deoptBci = method.isSynchronized() ? BytecodeFrame.UNWIND_BCI : BytecodeFrame.AFTER_EXCEPTION_BCI; - unwindBlock.setId(Integer.MAX_VALUE); - } - return unwindBlock; - } - /** * @param type the unresolved type of the constant */ @@ -480,7 +470,7 @@ * unwind immediately. */ if (bci != currentBlock.endBci || dispatchBlock == null) { - dispatchBlock = unwindBlock(); + dispatchBlock = blockMap.getUnwindBlock(); } HIRFrameStateBuilder dispatchState = frameState.copy(); @@ -1015,8 +1005,9 @@ beforeReturn(x); append(new ReturnNode(x)); } else { - if (returnCount == 1 || !controlFlowSplit) { + if (blockMap.getReturnCount() == 1 || !controlFlowSplit) { // There is only a single return. + beforeReturn(x); this.returnValue = x; this.beforeReturnNode = this.lastInstr; this.lastInstr = null; @@ -1026,8 +1017,8 @@ if (x != null) { frameState.push(x.getKind(), x); } - assert returnCount > 1; - appendGoto(returnBlock(bci())); + assert blockMap.getReturnCount() > 1; + appendGoto(blockMap.getReturnBlock()); } } } @@ -1187,7 +1178,7 @@ do { long lMask = 1L << pos; if ((exits & lMask) != 0) { - exitLoops.add(loopHeaders[pos]); + exitLoops.add(blockMap.getLoopHeader(pos)); exits &= ~lMask; } pos++; @@ -1207,7 +1198,7 @@ } HIRFrameStateBuilder newState = state.copy(); for (BciBlock loop : exitLoops) { - LoopBeginNode loopBegin = (LoopBeginNode) loop.getFirstInstruction(this.getCurrentDimension()); + LoopBeginNode loopBegin = (LoopBeginNode) getFirstInstruction(loop, this.getCurrentDimension()); LoopExitNode loopExit = currentGraph.add(new LoopExitNode(loopBegin)); if (lastLoopExit != null) { lastLoopExit.setNext(loopExit); @@ -1217,7 +1208,7 @@ } lastLoopExit = loopExit; Debug.log("Target %s Exits %s, scanning framestates...", targetBlock, loop); - newState.insertLoopProxies(loopExit, (HIRFrameStateBuilder) loop.getEntryState(this.getCurrentDimension())); + newState.insertLoopProxies(loopExit, (HIRFrameStateBuilder) getEntryState(loop, this.getCurrentDimension())); loopExit.setStateAfter(newState.create(bci)); } @@ -1228,6 +1219,98 @@ return new Target(target, state); } + private AbstractFrameStateBuilder<?, ?> getEntryState(BciBlock block, int dimension) { + int id = block.id; + if (dimension == 0) { + return entryStateArray[id]; + } else { + return getEntryStateMultiDimension(dimension, id); + } + } + + private AbstractFrameStateBuilder<?, ?> getEntryStateMultiDimension(int dimension, int id) { + if (entryStateMatrix != null && dimension - 1 < entryStateMatrix.length) { + AbstractFrameStateBuilder<?, ?>[] entryStateArrayEntry = entryStateMatrix[dimension - 1]; + if (entryStateArrayEntry == null) { + return null; + } + return entryStateArrayEntry[id]; + } else { + return null; + } + } + + private void setEntryState(BciBlock block, int dimension, AbstractFrameStateBuilder<?, ?> entryState) { + int id = block.id; + if (dimension == 0) { + this.entryStateArray[id] = entryState; + } else { + setEntryStateMultiDimension(dimension, entryState, id); + } + } + + private void setEntryStateMultiDimension(int dimension, AbstractFrameStateBuilder<?, ?> entryState, int id) { + if (entryStateMatrix == null) { + entryStateMatrix = new AbstractFrameStateBuilder<?, ?>[4][]; + } + if (dimension - 1 < entryStateMatrix.length) { + // We are within bounds. + } else { + // We are out of bounds. + entryStateMatrix = Arrays.copyOf(entryStateMatrix, Math.max(entryStateMatrix.length * 2, dimension)); + } + if (entryStateMatrix[dimension - 1] == null) { + entryStateMatrix[dimension - 1] = new AbstractFrameStateBuilder<?, ?>[blockMap.getBlockCount()]; + } + entryStateMatrix[dimension - 1][id] = entryState; + } + + private void setFirstInstruction(BciBlock block, int dimension, FixedWithNextNode firstInstruction) { + int id = block.id; + if (dimension == 0) { + this.firstInstructionArray[id] = firstInstruction; + } else { + setFirstInstructionMultiDimension(dimension, firstInstruction, id); + } + } + + private void setFirstInstructionMultiDimension(int dimension, FixedWithNextNode firstInstruction, int id) { + if (firstInstructionMatrix == null) { + firstInstructionMatrix = new FixedWithNextNode[4][]; + } + if (dimension - 1 < firstInstructionMatrix.length) { + // We are within bounds. + } else { + // We are out of bounds. + firstInstructionMatrix = Arrays.copyOf(firstInstructionMatrix, Math.max(firstInstructionMatrix.length * 2, dimension)); + } + if (firstInstructionMatrix[dimension - 1] == null) { + firstInstructionMatrix[dimension - 1] = new FixedWithNextNode[blockMap.getBlockCount()]; + } + firstInstructionMatrix[dimension - 1][id] = firstInstruction; + } + + private FixedWithNextNode getFirstInstruction(BciBlock block, int dimension) { + int id = block.id; + if (dimension == 0) { + return firstInstructionArray[id]; + } else { + return getFirstInstructionMultiDimension(dimension, id); + } + } + + private FixedWithNextNode getFirstInstructionMultiDimension(int dimension, int id) { + if (firstInstructionMatrix != null && dimension - 1 < firstInstructionMatrix.length) { + FixedWithNextNode[] firstInstructionArrayEntry = firstInstructionMatrix[dimension - 1]; + if (firstInstructionArrayEntry == null) { + return null; + } + return firstInstructionArrayEntry[id]; + } else { + return null; + } + } + private FixedNode createTarget(double probability, BciBlock block, HIRFrameStateBuilder stateAfter) { assert probability >= 0 && probability <= 1.01 : probability; if (isNeverExecutedCode(probability)) { @@ -1246,41 +1329,9 @@ assert block != null && state != null; assert !block.isExceptionEntry || state.stackSize() == 1; - int operatingDimension = this.getCurrentDimension(); - if (this.explodeLoops && this.explodeLoopsContext != null && !this.explodeLoopsContext.isEmpty()) { - int i; - for (i = explodeLoopsContext.size() - 1; i >= 0; --i) { - ExplodedLoopContext context = explodeLoopsContext.elementAt(i); - if (context.header == block) { - - // We have a hit on our current explosion context loop begin. - if (context.targetPeelIteration == -1) { - // This is the first hit => allocate a new dimension and at the same - // time mark the context loop begin as hit during the current - // iteration. - context.targetPeelIteration = nextPeelIteration++; - if (nextPeelIteration > MaximumLoopExplosionCount.getValue()) { - throw new BailoutException("too many loop explosion interations - does the explosion not terminate?"); - } - } + int operatingDimension = findOperatingDimension(block); - // Operate on the target dimension. - operatingDimension = context.targetPeelIteration; - break; - } else if (block.getId() > context.header.getId() && block.getId() <= context.header.loopEnd) { - // We hit the range of this context. - operatingDimension = context.peelIteration; - break; - } - } - - if (i == -1) { - // I did not find a dimension. - operatingDimension = 0; - } - } - - if (block.getFirstInstruction(operatingDimension) == null) { + if (getFirstInstruction(block, operatingDimension) == null) { /* * This is the first time we see this block as a branch target. Create and * return a placeholder that later can be replaced with a MergeNode when we see @@ -1288,51 +1339,51 @@ */ FixedNode targetNode; if (isGoto && (block.getPredecessorCount() == 1 || !controlFlowSplit) && !block.isLoopHeader && (currentBlock.loops & ~block.loops) == 0) { - block.setFirstInstruction(operatingDimension, lastInstr); + setFirstInstruction(block, operatingDimension, lastInstr); lastInstr = null; } else { - block.setFirstInstruction(operatingDimension, currentGraph.add(new BeginNode())); + setFirstInstruction(block, operatingDimension, currentGraph.add(new BeginNode())); } - targetNode = block.getFirstInstruction(operatingDimension); + targetNode = getFirstInstruction(block, operatingDimension); Target target = checkLoopExit(targetNode, block, state); FixedNode result = target.fixed; - AbstractFrameStateBuilder<?, ?> entryState = target.state == state ? state.copy() : target.state; - block.setEntryState(operatingDimension, entryState); - entryState.clearNonLiveLocals(block, liveness, true); + AbstractFrameStateBuilder<?, ?> currentEntryState = target.state == state ? state.copy() : target.state; + setEntryState(block, operatingDimension, currentEntryState); + currentEntryState.clearNonLiveLocals(block, liveness, true); Debug.log("createTarget %s: first visit, result: %s", block, targetNode); return result; } // We already saw this block before, so we have to merge states. - if (!((HIRFrameStateBuilder) block.getEntryState(operatingDimension)).isCompatibleWith(state)) { + if (!((HIRFrameStateBuilder) getEntryState(block, operatingDimension)).isCompatibleWith(state)) { throw new BailoutException("stacks do not match; bytecodes would not verify"); } - if (block.getFirstInstruction(operatingDimension) instanceof LoopBeginNode) { + if (getFirstInstruction(block, operatingDimension) instanceof LoopBeginNode) { assert this.explodeLoops || (block.isLoopHeader && currentBlock.getId() >= block.getId()) : "must be backward branch"; /* * Backward loop edge. We need to create a special LoopEndNode and merge with * the loop begin node created before. */ - LoopBeginNode loopBegin = (LoopBeginNode) block.getFirstInstruction(operatingDimension); + LoopBeginNode loopBegin = (LoopBeginNode) getFirstInstruction(block, operatingDimension); Target target = checkLoopExit(currentGraph.add(new LoopEndNode(loopBegin)), block, state); FixedNode result = target.fixed; - ((HIRFrameStateBuilder) block.getEntryState(operatingDimension)).merge(loopBegin, target.state); + ((HIRFrameStateBuilder) getEntryState(block, operatingDimension)).merge(loopBegin, target.state); Debug.log("createTarget %s: merging backward branch to loop header %s, result: %s", block, loopBegin, result); return result; } assert currentBlock == null || currentBlock.getId() < block.getId() : "must not be backward branch"; - assert block.getFirstInstruction(operatingDimension).next() == null : "bytecodes already parsed for block"; + assert getFirstInstruction(block, operatingDimension).next() == null : "bytecodes already parsed for block"; - if (block.getFirstInstruction(operatingDimension) instanceof AbstractBeginNode && !(block.getFirstInstruction(operatingDimension) instanceof AbstractMergeNode)) { + if (getFirstInstruction(block, operatingDimension) instanceof AbstractBeginNode && !(getFirstInstruction(block, operatingDimension) instanceof AbstractMergeNode)) { /* * This is the second time we see this block. Create the actual MergeNode and * the End Node for the already existing edge. For simplicity, we leave the * placeholder in the graph and just append the new nodes after the placeholder. */ - AbstractBeginNode placeholder = (AbstractBeginNode) block.getFirstInstruction(operatingDimension); + AbstractBeginNode placeholder = (AbstractBeginNode) getFirstInstruction(block, operatingDimension); // The EndNode for the already existing edge. AbstractEndNode end = currentGraph.add(new EndNode()); @@ -1350,22 +1401,58 @@ mergeNode.addForwardEnd(end); mergeNode.setNext(next); - block.setFirstInstruction(operatingDimension, mergeNode); + setFirstInstruction(block, operatingDimension, mergeNode); } - AbstractMergeNode mergeNode = (AbstractMergeNode) block.getFirstInstruction(operatingDimension); + AbstractMergeNode mergeNode = (AbstractMergeNode) getFirstInstruction(block, operatingDimension); // The EndNode for the newly merged edge. AbstractEndNode newEnd = currentGraph.add(new EndNode()); Target target = checkLoopExit(newEnd, block, state); FixedNode result = target.fixed; - ((HIRFrameStateBuilder) block.getEntryState(operatingDimension)).merge(mergeNode, target.state); + ((HIRFrameStateBuilder) getEntryState(block, operatingDimension)).merge(mergeNode, target.state); mergeNode.addForwardEnd(newEnd); Debug.log("createTarget %s: merging state, result: %s", block, result); return result; } + private int findOperatingDimension(BciBlock block) { + if (this.explodeLoops && this.explodeLoopsContext != null && !this.explodeLoopsContext.isEmpty()) { + return findOperatingDimensionWithLoopExplosion(block); + } + return this.getCurrentDimension(); + } + + private int findOperatingDimensionWithLoopExplosion(BciBlock block) { + int i; + for (i = explodeLoopsContext.size() - 1; i >= 0; --i) { + ExplodedLoopContext context = explodeLoopsContext.elementAt(i); + if (context.header == block) { + + // We have a hit on our current explosion context loop begin. + if (context.targetPeelIteration == -1) { + // This is the first hit => allocate a new dimension and at the same + // time mark the context loop begin as hit during the current + // iteration. + context.targetPeelIteration = nextPeelIteration++; + if (nextPeelIteration > MaximumLoopExplosionCount.getValue()) { + throw new BailoutException("too many loop explosion interations - does the explosion not terminate?"); + } + } + + // Operate on the target dimension. + return context.targetPeelIteration; + } else if (block.getId() > context.header.getId() && block.getId() <= context.header.loopEnd) { + // We hit the range of this context. + return context.peelIteration; + } + } + + // No dimension found. + return 0; + } + /** * Returns a block begin node with the specified state. If the specified probability is * 0, the block deoptimizes immediately. @@ -1389,14 +1476,14 @@ protected void processBlock(BytecodeParser parser, BciBlock block) { // Ignore blocks that have no predecessors by the time their bytecodes are parsed - if (block == null || block.getFirstInstruction(this.getCurrentDimension()) == null) { + if (block == null || getFirstInstruction(block, this.getCurrentDimension()) == null) { Debug.log("Ignoring block %s", block); return; } - try (Indent indent = Debug.logAndIndent("Parsing block %s firstInstruction: %s loopHeader: %b", block, block.getFirstInstruction(this.getCurrentDimension()), block.isLoopHeader)) { + try (Indent indent = Debug.logAndIndent("Parsing block %s firstInstruction: %s loopHeader: %b", block, getFirstInstruction(block, this.getCurrentDimension()), block.isLoopHeader)) { - lastInstr = block.getFirstInstruction(this.getCurrentDimension()); - frameState = (HIRFrameStateBuilder) block.getEntryState(this.getCurrentDimension()); + lastInstr = getFirstInstruction(block, this.getCurrentDimension()); + frameState = (HIRFrameStateBuilder) getEntryState(block, this.getCurrentDimension()); parser.setCurrentFrameState(frameState); currentBlock = block; @@ -1412,14 +1499,14 @@ } } - if (block == returnBlock) { + if (block == blockMap.getReturnBlock()) { Kind returnKind = method.getSignature().getReturnKind().getStackKind(); ValueNode x = returnKind == Kind.Void ? null : frameState.pop(returnKind); assert frameState.stackSize() == 0; beforeReturn(x); this.returnValue = x; this.beforeReturnNode = this.lastInstr; - } else if (block == unwindBlock) { + } else if (block == blockMap.getUnwindBlock()) { if (currentDepth == 0) { frameState.setRethrowException(false); createUnwind(); @@ -1496,7 +1583,7 @@ ResolvedJavaType resolvedCatchType = (ResolvedJavaType) catchType; for (ResolvedJavaType skippedType : graphBuilderConfig.getSkippedExceptionTypes()) { if (skippedType.isAssignableFrom(resolvedCatchType)) { - BciBlock nextBlock = block.getSuccessorCount() == 1 ? unwindBlock() : block.getSuccessor(1); + BciBlock nextBlock = block.getSuccessorCount() == 1 ? blockMap.getUnwindBlock() : block.getSuccessor(1); ValueNode exception = frameState.stackAt(0); FixedNode trueSuccessor = currentGraph.add(new DeoptimizeNode(InvalidateReprofile, UnreachedCode)); FixedNode nextDispatch = createTarget(nextBlock, frameState); @@ -1507,7 +1594,7 @@ } if (initialized) { - BciBlock nextBlock = block.getSuccessorCount() == 1 ? unwindBlock() : block.getSuccessor(1); + BciBlock nextBlock = block.getSuccessorCount() == 1 ? blockMap.getUnwindBlock() : block.getSuccessor(1); ValueNode exception = frameState.stackAt(0); CheckCastNode checkCast = currentGraph.add(new CheckCastNode((ResolvedJavaType) catchType, exception, null, false)); frameState.apop(); @@ -1556,12 +1643,12 @@ * merge to the loop header. This ensures that the loop header has exactly one * non-loop predecessor. */ - block.setFirstInstruction(this.getCurrentDimension(), loopBegin); + setFirstInstruction(block, this.getCurrentDimension(), loopBegin); /* * We need to preserve the frame state builder of the loop header so that we can * merge values for phi functions, so make a copy of it. */ - block.setEntryState(this.getCurrentDimension(), frameState.copy()); + setEntryState(block, this.getCurrentDimension(), frameState.copy()); Debug.log(" created loop header %s", loopBegin); }
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/HIRFrameStateBuilder.java Wed Feb 18 16:55:20 2015 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/HIRFrameStateBuilder.java Wed Feb 18 20:20:46 2015 +0100 @@ -31,7 +31,6 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.common.type.*; import com.oracle.graal.debug.*; -import com.oracle.graal.java.BciBlockMapping.LocalLiveness; import com.oracle.graal.java.GraphBuilderPlugin.ParameterPlugin; import com.oracle.graal.nodeinfo.*; import com.oracle.graal.nodes.*;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/LargeLocalLiveness.java Wed Feb 18 20:20:46 2015 +0100 @@ -0,0 +1,133 @@ +/* + * Copyright (c) 2009, 2015, 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.oracle.graal.java; + +import java.util.*; + +import com.oracle.graal.java.BciBlockMapping.*; + +public final class LargeLocalLiveness extends LocalLiveness { + private BitSet[] localsLiveIn; + private BitSet[] localsLiveOut; + private BitSet[] localsLiveGen; + private BitSet[] localsLiveKill; + private BitSet[] localsChangedInLoop; + + public LargeLocalLiveness(BciBlock[] blocks, int maxLocals, int loopCount) { + super(blocks); + int blocksSize = blocks.length; + localsLiveIn = new BitSet[blocksSize]; + localsLiveOut = new BitSet[blocksSize]; + localsLiveGen = new BitSet[blocksSize]; + localsLiveKill = new BitSet[blocksSize]; + for (int i = 0; i < blocksSize; i++) { + localsLiveIn[i] = new BitSet(maxLocals); + localsLiveOut[i] = new BitSet(maxLocals); + localsLiveGen[i] = new BitSet(maxLocals); + localsLiveKill[i] = new BitSet(maxLocals); + } + localsChangedInLoop = new BitSet[loopCount]; + for (int i = 0; i < loopCount; ++i) { + localsChangedInLoop[i] = new BitSet(maxLocals); + } + } + + @Override + protected String debugLiveIn(int blockID) { + return localsLiveIn[blockID].toString(); + } + + @Override + protected String debugLiveOut(int blockID) { + return localsLiveOut[blockID].toString(); + } + + @Override + protected String debugLiveGen(int blockID) { + return localsLiveGen[blockID].toString(); + } + + @Override + protected String debugLiveKill(int blockID) { + return localsLiveKill[blockID].toString(); + } + + @Override + protected int liveOutCardinality(int blockID) { + return localsLiveOut[blockID].cardinality(); + } + + @Override + protected void propagateLiveness(int blockID, int successorID) { + localsLiveOut[blockID].or(localsLiveIn[successorID]); + } + + @Override + protected void updateLiveness(int blockID) { + BitSet liveIn = localsLiveIn[blockID]; + liveIn.clear(); + liveIn.or(localsLiveOut[blockID]); + liveIn.andNot(localsLiveKill[blockID]); + liveIn.or(localsLiveGen[blockID]); + } + + @Override + protected void loadOne(int blockID, int local) { + if (!localsLiveKill[blockID].get(local)) { + localsLiveGen[blockID].set(local); + } + } + + @Override + protected void storeOne(int blockID, int local) { + if (!localsLiveGen[blockID].get(local)) { + localsLiveKill[blockID].set(local); + } + + BciBlock block = blocks[blockID]; + long tmp = block.loops; + int pos = 0; + while (tmp != 0) { + if ((tmp & 1L) == 1L) { + this.localsChangedInLoop[pos].set(local); + } + tmp >>= 1; + ++pos; + } + } + + @Override + public boolean localIsLiveIn(BciBlock block, int local) { + return block.getId() >= Integer.MAX_VALUE ? true : localsLiveIn[block.getId()].get(local); + } + + @Override + public boolean localIsLiveOut(BciBlock block, int local) { + return block.getId() >= Integer.MAX_VALUE ? true : localsLiveOut[block.getId()].get(local); + } + + @Override + public boolean localIsChangedInLoop(int loopId, int local) { + return localsChangedInLoop[loopId].get(local); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/LocalLiveness.java Wed Feb 18 20:20:46 2015 +0100 @@ -0,0 +1,272 @@ +/* + * Copyright (c) 2009, 2015, 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.oracle.graal.java; + +import static com.oracle.graal.bytecode.Bytecodes.*; + +import com.oracle.graal.bytecode.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.java.BciBlockMapping.*; + +/** + * Encapsulates the liveness calculation, so that subclasses for locals ≤ 64 and locals > 64 + * can be implemented. + */ +public abstract class LocalLiveness { + protected final BciBlock[] blocks; + + public static LocalLiveness compute(BytecodeStream stream, BciBlock[] blocks, int maxLocals, int loopCount) { + LocalLiveness liveness = maxLocals <= 64 ? new SmallLocalLiveness(blocks, maxLocals, loopCount) : new LargeLocalLiveness(blocks, maxLocals, loopCount); + liveness.computeLiveness(stream); + return liveness; + } + + protected LocalLiveness(BciBlock[] blocks) { + this.blocks = blocks; + } + + void computeLiveness(BytecodeStream stream) { + for (BciBlock block : blocks) { + computeLocalLiveness(stream, block); + } + + boolean changed; + int iteration = 0; + do { + Debug.log("Iteration %d", iteration); + changed = false; + for (int i = blocks.length - 1; i >= 0; i--) { + BciBlock block = blocks[i]; + int blockID = block.getId(); + // log statements in IFs because debugLiveX creates a new String + if (Debug.isLogEnabled()) { + Debug.logv(" start B%d [%d, %d] in: %s out: %s gen: %s kill: %s", block.getId(), block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID), + debugLiveGen(blockID), debugLiveKill(blockID)); + } + + boolean blockChanged = (iteration == 0); + if (block.getSuccessorCount() > 0) { + int oldCardinality = liveOutCardinality(blockID); + for (BciBlock sux : block.getSuccessors()) { + if (Debug.isLogEnabled()) { + Debug.log(" Successor B%d: %s", sux.getId(), debugLiveIn(sux.getId())); + } + propagateLiveness(blockID, sux.getId()); + } + blockChanged |= (oldCardinality != liveOutCardinality(blockID)); + } + + if (blockChanged) { + updateLiveness(blockID); + if (Debug.isLogEnabled()) { + Debug.logv(" end B%d [%d, %d] in: %s out: %s gen: %s kill: %s", block.getId(), block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID), + debugLiveGen(blockID), debugLiveKill(blockID)); + } + } + changed |= blockChanged; + } + iteration++; + } while (changed); + } + + /** + * Returns whether the local is live at the beginning of the given block. + */ + public abstract boolean localIsLiveIn(BciBlock block, int local); + + /** + * Returns whether the local is set in the given loop. + */ + public abstract boolean localIsChangedInLoop(int loopId, int local); + + /** + * Returns whether the local is live at the end of the given block. + */ + public abstract boolean localIsLiveOut(BciBlock block, int local); + + /** + * Returns a string representation of the liveIn values of the given block. + */ + protected abstract String debugLiveIn(int blockID); + + /** + * Returns a string representation of the liveOut values of the given block. + */ + protected abstract String debugLiveOut(int blockID); + + /** + * Returns a string representation of the liveGen values of the given block. + */ + protected abstract String debugLiveGen(int blockID); + + /** + * Returns a string representation of the liveKill values of the given block. + */ + protected abstract String debugLiveKill(int blockID); + + /** + * Returns the number of live locals at the end of the given block. + */ + protected abstract int liveOutCardinality(int blockID); + + /** + * Adds all locals the are in the liveIn of the successor to the liveOut of the block. + */ + protected abstract void propagateLiveness(int blockID, int successorID); + + /** + * Calculates a new liveIn for the given block from liveOut, liveKill and liveGen. + */ + protected abstract void updateLiveness(int blockID); + + /** + * Adds the local to liveGen if it wasn't already killed in this block. + */ + protected abstract void loadOne(int blockID, int local); + + /** + * Add this local to liveKill if it wasn't already generated in this block. + */ + protected abstract void storeOne(int blockID, int local); + + private void computeLocalLiveness(BytecodeStream stream, BciBlock block) { + if (block.startBci < 0 || block.endBci < 0) { + return; + } + int blockID = block.getId(); + int localIndex; + stream.setBCI(block.startBci); + while (stream.currentBCI() <= block.endBci) { + switch (stream.currentBC()) { + case LLOAD: + case DLOAD: + loadTwo(blockID, stream.readLocalIndex()); + break; + case LLOAD_0: + case DLOAD_0: + loadTwo(blockID, 0); + break; + case LLOAD_1: + case DLOAD_1: + loadTwo(blockID, 1); + break; + case LLOAD_2: + case DLOAD_2: + loadTwo(blockID, 2); + break; + case LLOAD_3: + case DLOAD_3: + loadTwo(blockID, 3); + break; + case IINC: + localIndex = stream.readLocalIndex(); + loadOne(blockID, localIndex); + storeOne(blockID, localIndex); + break; + case ILOAD: + case FLOAD: + case ALOAD: + case RET: + loadOne(blockID, stream.readLocalIndex()); + break; + case ILOAD_0: + case FLOAD_0: + case ALOAD_0: + loadOne(blockID, 0); + break; + case ILOAD_1: + case FLOAD_1: + case ALOAD_1: + loadOne(blockID, 1); + break; + case ILOAD_2: + case FLOAD_2: + case ALOAD_2: + loadOne(blockID, 2); + break; + case ILOAD_3: + case FLOAD_3: + case ALOAD_3: + loadOne(blockID, 3); + break; + + case LSTORE: + case DSTORE: + storeTwo(blockID, stream.readLocalIndex()); + break; + case LSTORE_0: + case DSTORE_0: + storeTwo(blockID, 0); + break; + case LSTORE_1: + case DSTORE_1: + storeTwo(blockID, 1); + break; + case LSTORE_2: + case DSTORE_2: + storeTwo(blockID, 2); + break; + case LSTORE_3: + case DSTORE_3: + storeTwo(blockID, 3); + break; + case ISTORE: + case FSTORE: + case ASTORE: + storeOne(blockID, stream.readLocalIndex()); + break; + case ISTORE_0: + case FSTORE_0: + case ASTORE_0: + storeOne(blockID, 0); + break; + case ISTORE_1: + case FSTORE_1: + case ASTORE_1: + storeOne(blockID, 1); + break; + case ISTORE_2: + case FSTORE_2: + case ASTORE_2: + storeOne(blockID, 2); + break; + case ISTORE_3: + case FSTORE_3: + case ASTORE_3: + storeOne(blockID, 3); + break; + } + stream.next(); + } + } + + private void loadTwo(int blockID, int local) { + loadOne(blockID, local); + loadOne(blockID, local + 1); + } + + private void storeTwo(int blockID, int local) { + storeOne(blockID, local); + storeOne(blockID, local + 1); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/SmallLocalLiveness.java Wed Feb 18 20:20:46 2015 +0100 @@ -0,0 +1,143 @@ +/* + * Copyright (c) 2009, 2015, 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.oracle.graal.java; + +import com.oracle.graal.java.BciBlockMapping.*; + +public final class SmallLocalLiveness extends LocalLiveness { + /* + * local n is represented by the bit accessible as (1 << n) + */ + + private final long[] localsLiveIn; + private final long[] localsLiveOut; + private final long[] localsLiveGen; + private final long[] localsLiveKill; + private final long[] localsChangedInLoop; + private final int maxLocals; + + public SmallLocalLiveness(BciBlock[] blocks, int maxLocals, int loopCount) { + super(blocks); + this.maxLocals = maxLocals; + int blockSize = blocks.length; + localsLiveIn = new long[blockSize]; + localsLiveOut = new long[blockSize]; + localsLiveGen = new long[blockSize]; + localsLiveKill = new long[blockSize]; + localsChangedInLoop = new long[loopCount]; + } + + private String debugString(long value) { + StringBuilder str = new StringBuilder("{"); + long current = value; + for (int i = 0; i < maxLocals; i++) { + if ((current & 1L) == 1L) { + if (str.length() > 1) { + str.append(", "); + } + str.append(i); + } + current >>= 1; + } + return str.append('}').toString(); + } + + @Override + protected String debugLiveIn(int blockID) { + return debugString(localsLiveIn[blockID]); + } + + @Override + protected String debugLiveOut(int blockID) { + return debugString(localsLiveOut[blockID]); + } + + @Override + protected String debugLiveGen(int blockID) { + return debugString(localsLiveGen[blockID]); + } + + @Override + protected String debugLiveKill(int blockID) { + return debugString(localsLiveKill[blockID]); + } + + @Override + protected int liveOutCardinality(int blockID) { + return Long.bitCount(localsLiveOut[blockID]); + } + + @Override + protected void propagateLiveness(int blockID, int successorID) { + localsLiveOut[blockID] |= localsLiveIn[successorID]; + } + + @Override + protected void updateLiveness(int blockID) { + localsLiveIn[blockID] = (localsLiveOut[blockID] & ~localsLiveKill[blockID]) | localsLiveGen[blockID]; + } + + @Override + protected void loadOne(int blockID, int local) { + long bit = 1L << local; + if ((localsLiveKill[blockID] & bit) == 0L) { + localsLiveGen[blockID] |= bit; + } + } + + @Override + protected void storeOne(int blockID, int local) { + long bit = 1L << local; + if ((localsLiveGen[blockID] & bit) == 0L) { + localsLiveKill[blockID] |= bit; + } + + BciBlock block = blocks[blockID]; + long tmp = block.loops; + int pos = 0; + while (tmp != 0) { + if ((tmp & 1L) == 1L) { + this.localsChangedInLoop[pos] |= bit; + } + tmp >>= 1; + ++pos; + } + } + + @Override + public boolean localIsLiveIn(BciBlock block, int local) { + int blockID = block.getId(); + return blockID >= Integer.MAX_VALUE ? false : (localsLiveIn[blockID] & (1L << local)) != 0L; + } + + @Override + public boolean localIsLiveOut(BciBlock block, int local) { + int blockID = block.getId(); + return blockID >= Integer.MAX_VALUE ? false : (localsLiveOut[blockID] & (1L << local)) != 0L; + } + + @Override + public boolean localIsChangedInLoop(int loopId, int local) { + return (localsChangedInLoop[loopId] & (1L << local)) != 0L; + } +}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Wed Feb 18 16:55:20 2015 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Wed Feb 18 20:20:46 2015 +0100 @@ -601,7 +601,6 @@ * Multiple phis but merging same values for true and false, so simply delete * the path */ - tool.addToWorkList(condition()); removeThroughFalseBranch(tool); return true; } else if (distinct == 1) { @@ -644,6 +643,9 @@ AbstractBeginNode trueBegin = trueSuccessor(); graph().removeSplitPropagate(this, trueBegin, tool); tool.addToWorkList(trueBegin); + if (condition().isAlive() && condition().hasNoUsages()) { + GraphUtil.killWithUnusedFloatingInputs(condition()); + } } private ConditionalNode canonicalizeConditionalCascade(ValueNode trueValue, ValueNode falseValue) {
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/PartialEvaluator.java Wed Feb 18 16:55:20 2015 +0100 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/PartialEvaluator.java Wed Feb 18 20:20:46 2015 +0100 @@ -265,10 +265,12 @@ } } + // Perform dead code elimination. Dead nodes mainly come from parse time canonicalizations. + new DeadCodeEliminationPhase().apply(graph); + // Do single partial escape and canonicalization pass. try (Scope pe = Debug.scope("TrufflePartialEscape", graph)) { new PartialEscapePhase(true, canonicalizer).apply(graph, tierContext); - new PartialEscapePhase(true, canonicalizer).apply(graph, tierContext); new IncrementalCanonicalizerPhase<>(canonicalizer, new ConditionalEliminationPhase()).apply(graph, tierContext); } catch (Throwable t) { Debug.handle(t);