Mercurial > hg > truffle
changeset 19479:7837f7aab5ed
Split bci block mapping and local liveness analysis. Clean up bci block mapping. Always sort loop blocks to be consecutive.
| author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
|---|---|
| date | Wed, 18 Feb 2015 17:52:22 +0100 |
| parents | 076cb9f9bdbc |
| children | ff67cb313c9a |
| files | graal/com.oracle.graal.java/src/com/oracle/graal/java/AbstractFrameStateBuilder.java graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java graal/com.oracle.graal.java/src/com/oracle/graal/java/HIRFrameStateBuilder.java graal/com.oracle.graal.java/src/com/oracle/graal/java/LargeLocalLiveness.java graal/com.oracle.graal.java/src/com/oracle/graal/java/LocalLiveness.java graal/com.oracle.graal.java/src/com/oracle/graal/java/SmallLocalLiveness.java |
| diffstat | 7 files changed, 627 insertions(+), 534 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/AbstractFrameStateBuilder.java Wed Feb 18 15:10:57 2015 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/AbstractFrameStateBuilder.java Wed Feb 18 17:52:22 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 15:10:57 2015 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java Wed Feb 18 17:52:22 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,7 +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.*; /** @@ -424,20 +423,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 +439,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 +455,30 @@ /** * 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 + startBlock = blockMap[0]; blockMap = null; 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 +497,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 +515,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 +537,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 +560,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 +587,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 +604,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 +630,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 +642,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 +676,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 +684,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 +698,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 +745,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 +787,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 +807,7 @@ } while (loopChanges); } - private void computeBlockOrder() { + private void computeBlockOrder(BciBlock[] blockMap) { int maxBlocks = blocksNotYetAssignedId; this.blocks = new BciBlock[blocksNotYetAssignedId]; long loop = computeBlockOrder(blockMap[0]); @@ -855,7 +837,7 @@ if (b != null) { b.setId(next); newBlocks[next++] = b; - if (consecutiveLoopBlocks && b.isLoopHeader) { + if (b.isLoopHeader) { next = handleLoopHeader(newBlocks, next, i, b); } } @@ -882,7 +864,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 +1000,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 +1014,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 +1029,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 +1039,15 @@ 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 int getLoopCount() { + return nextLoop; + } }
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Wed Feb 18 15:10:57 2015 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Wed Feb 18 17:52:22 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; @@ -247,20 +247,30 @@ 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); + BciBlockMapping blockMap = BciBlockMapping.create(stream, method); loopHeaders = blockMap.getLoopHeaders(); - liveness = blockMap.liveness; + + 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); + } + } returnCount = blockMap.getReturnCount(); 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 +280,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 +289,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(); + startBlock.setEntryState(0, frameState); + if (startBlock.isLoopHeader && !explodeLoops) { + appendGoto(startBlock); } else { - blockMap.startBlock.setFirstInstruction(0, lastInstr); + startBlock.setFirstInstruction(0, lastInstr); } int index = 0;
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/HIRFrameStateBuilder.java Wed Feb 18 15:10:57 2015 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/HIRFrameStateBuilder.java Wed Feb 18 17:52:22 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 17:52:22 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 17:52:22 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 17:52:22 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; + } +}