Mercurial > hg > truffle
changeset 14540:f659d019d3ab
Merged
| author | Christian Wirth <christian.wirth@oracle.com> |
|---|---|
| date | Fri, 14 Mar 2014 15:29:17 +0100 |
| parents | 47b775458982 (current diff) 360beb9b3c50 (diff) |
| children | 145b31ba9a57 c4219e527b83 |
| files | |
| diffstat | 11 files changed, 589 insertions(+), 212 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java Fri Mar 14 09:58:31 2014 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java Fri Mar 14 15:29:17 2014 +0100 @@ -45,8 +45,8 @@ this.nodeOperands = nodeOperands; } - protected HashMap<VirtualObjectNode, VirtualObject> virtualObjects = new HashMap<>(); - protected IdentityHashMap<VirtualObjectNode, EscapeObjectState> objectStates = new IdentityHashMap<>(); + protected final HashMap<VirtualObjectNode, VirtualObject> virtualObjects = new HashMap<>(); + protected final IdentityHashMap<VirtualObjectNode, EscapeObjectState> objectStates = new IdentityHashMap<>(); public LIRFrameState build(FrameState topState, LabelRef exceptionEdge) { assert virtualObjects.size() == 0;
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeList.java Fri Mar 14 09:58:31 2014 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeList.java Fri Mar 14 15:29:17 2014 +0100 @@ -257,7 +257,7 @@ } @Override - public void snapshotTo(List<T> to) { + public void snapshotTo(Collection<T> to) { for (int i = 0; i < size; i++) { to.add(get(i)); }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/AbstractNodeIterable.java Fri Mar 14 09:58:31 2014 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/AbstractNodeIterable.java Fri Mar 14 15:29:17 2014 +0100 @@ -74,7 +74,7 @@ } @Override - public void snapshotTo(List<T> to) { + public void snapshotTo(Collection<T> to) { for (T n : this) { to.add(n); }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java Fri Mar 14 09:58:31 2014 +0100 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java Fri Mar 14 15:29:17 2014 +0100 @@ -44,7 +44,7 @@ List<T> snapshot(); - void snapshotTo(List<T> to); + void snapshotTo(Collection<T> to); T first();
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java Fri Mar 14 09:58:31 2014 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java Fri Mar 14 15:29:17 2014 +0100 @@ -99,11 +99,6 @@ public Block retSuccessor; public boolean endsWithRet = false; - public BitSet localsLiveIn; - public BitSet localsLiveOut; - private BitSet localsLiveGen; - private BitSet localsLiveKill; - public Block exceptionDispatchBlock() { if (successors.size() > 0 && successors.get(successors.size() - 1) instanceof ExceptionDispatchBlock) { return successors.get(successors.size() - 1); @@ -167,6 +162,8 @@ private Block[] blockMap; public Block[] loopHeaders; + public LocalLiveness liveness; + /** * Creates a new BlockMap instance from bytecode of the given method . * @@ -212,7 +209,8 @@ } if (OptLivenessAnalysis.getValue()) { try (Scope s = Debug.scope("LivenessAnalysis")) { - computeLiveness(); + liveness = method.getMaxLocals() <= 64 ? new SmallLocalLiveness() : new LargeLocalLiveness(); + liveness.computeLiveness(); } catch (Throwable e) { throw Debug.handle(e); } @@ -729,153 +727,225 @@ return loops; } - private void computeLiveness() { - for (Block block : blocks) { - computeLocalLiveness(block); - } + /** + * Encapsulates the liveness calculation, so that subclasses for locals <= 64 and locals > 64 + * can be implemented. + */ + public abstract class LocalLiveness { + + private void computeLiveness() { + for (Block block : blocks) { + computeLocalLiveness(block); + } - boolean changed; - int iteration = 0; - do { - Debug.log("Iteration %d", iteration); - changed = false; - for (int i = blocks.size() - 1; i >= 0; i--) { - Block block = blocks.get(i); - Debug.log(" start B%d [%d, %d] in: %s out: %s gen: %s kill: %s", block.blockID, block.startBci, block.endBci, block.localsLiveIn, block.localsLiveOut, block.localsLiveGen, - block.localsLiveKill); + boolean changed; + int iteration = 0; + do { + Debug.log("Iteration %d", iteration); + changed = false; + for (int i = blocks.size() - 1; i >= 0; i--) { + Block block = blocks.get(i); + int blockID = block.blockID; + // log statements in IFs because debugLiveX creates a new String + if (Debug.isLogEnabled()) { + Debug.log(" start B%d [%d, %d] in: %s out: %s gen: %s kill: %s", block.blockID, block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID), + debugLiveGen(blockID), debugLiveKill(blockID)); + } - boolean blockChanged = (iteration == 0); - if (block.successors.size() > 0) { - int oldCardinality = block.localsLiveOut.cardinality(); - for (Block sux : block.successors) { - Debug.log(" Successor B%d: %s", sux.blockID, sux.localsLiveIn); - block.localsLiveOut.or(sux.localsLiveIn); + boolean blockChanged = (iteration == 0); + if (block.successors.size() > 0) { + int oldCardinality = liveOutCardinality(blockID); + for (Block sux : block.successors) { + if (Debug.isLogEnabled()) { + Debug.log(" Successor B%d: %s", sux.blockID, debugLiveIn(sux.blockID)); + } + propagateLiveness(blockID, sux.blockID); + } + blockChanged |= (oldCardinality != liveOutCardinality(blockID)); } - blockChanged |= (oldCardinality != block.localsLiveOut.cardinality()); + + if (blockChanged) { + updateLiveness(blockID); + if (Debug.isLogEnabled()) { + Debug.log(" end B%d [%d, %d] in: %s out: %s gen: %s kill: %s", block.blockID, block.startBci, block.endBci, debugLiveIn(blockID), debugLiveOut(blockID), + debugLiveGen(blockID), debugLiveKill(blockID)); + } + } + changed |= blockChanged; } - - if (blockChanged) { - block.localsLiveIn.clear(); - block.localsLiveIn.or(block.localsLiveOut); - block.localsLiveIn.andNot(block.localsLiveKill); - block.localsLiveIn.or(block.localsLiveGen); - Debug.log(" end B%d [%d, %d] in: %s out: %s gen: %s kill: %s", block.blockID, block.startBci, block.endBci, block.localsLiveIn, block.localsLiveOut, block.localsLiveGen, - block.localsLiveKill); - } - changed |= blockChanged; - } - iteration++; - } while (changed); - } - - private void computeLocalLiveness(Block block) { - block.localsLiveIn = new BitSet(method.getMaxLocals()); - block.localsLiveOut = new BitSet(method.getMaxLocals()); - block.localsLiveGen = new BitSet(method.getMaxLocals()); - block.localsLiveKill = new BitSet(method.getMaxLocals()); - - if (block.startBci < 0 || block.endBci < 0) { - return; + iteration++; + } while (changed); } - stream.setBCI(block.startBci); - while (stream.currentBCI() <= block.endBci) { - switch (stream.currentBC()) { - case LLOAD: - case DLOAD: - loadTwo(block, stream.readLocalIndex()); - break; - case LLOAD_0: - case DLOAD_0: - loadTwo(block, 0); - break; - case LLOAD_1: - case DLOAD_1: - loadTwo(block, 1); - break; - case LLOAD_2: - case DLOAD_2: - loadTwo(block, 2); - break; - case LLOAD_3: - case DLOAD_3: - loadTwo(block, 3); - break; - case ILOAD: - case IINC: - case FLOAD: - case ALOAD: - case RET: - loadOne(block, stream.readLocalIndex()); - break; - case ILOAD_0: - case FLOAD_0: - case ALOAD_0: - loadOne(block, 0); - break; - case ILOAD_1: - case FLOAD_1: - case ALOAD_1: - loadOne(block, 1); - break; - case ILOAD_2: - case FLOAD_2: - case ALOAD_2: - loadOne(block, 2); - break; - case ILOAD_3: - case FLOAD_3: - case ALOAD_3: - loadOne(block, 3); - break; + /** + * Returns whether the local is live at the beginning of the given block. + */ + public abstract boolean localIsLiveIn(Block block, int local); + + /** + * Returns whether the local is live at the end of the given block. + */ + public abstract boolean localIsLiveOut(Block 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); - case LSTORE: - case DSTORE: - storeTwo(block, stream.readLocalIndex()); - break; - case LSTORE_0: - case DSTORE_0: - storeTwo(block, 0); - break; - case LSTORE_1: - case DSTORE_1: - storeTwo(block, 1); - break; - case LSTORE_2: - case DSTORE_2: - storeTwo(block, 2); - break; - case LSTORE_3: - case DSTORE_3: - storeTwo(block, 3); - break; - case ISTORE: - case FSTORE: - case ASTORE: - storeOne(block, stream.readLocalIndex()); - break; - case ISTORE_0: - case FSTORE_0: - case ASTORE_0: - storeOne(block, 0); - break; - case ISTORE_1: - case FSTORE_1: - case ASTORE_1: - storeOne(block, 1); - break; - case ISTORE_2: - case FSTORE_2: - case ASTORE_2: - storeOne(block, 2); - break; - case ISTORE_3: - case FSTORE_3: - case ASTORE_3: - storeOne(block, 3); - break; + private void computeLocalLiveness(Block block) { + if (block.startBci < 0 || block.endBci < 0) { + return; } - stream.next(); + int blockID = block.blockID; + 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 ILOAD: + case IINC: + 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); } } @@ -889,25 +959,182 @@ return map; } - private static void loadTwo(Block block, int local) { - loadOne(block, local); - loadOne(block, local + 1); - } + 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; + + public SmallLocalLiveness() { + localsLiveIn = new long[blocks.size()]; + localsLiveOut = new long[blocks.size()]; + localsLiveGen = new long[blocks.size()]; + localsLiveKill = new long[blocks.size()]; + } + + 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]); + } - private static void loadOne(Block block, int local) { - if (!block.localsLiveKill.get(local)) { - block.localsLiveGen.set(local); + @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; + } + } + + @Override + public boolean localIsLiveIn(Block block, int local) { + int blockID = block.blockID; + return blockID >= Integer.MAX_VALUE ? false : (localsLiveIn[blockID] & (1L << local)) != 0L; + } + + @Override + public boolean localIsLiveOut(Block block, int local) { + int blockID = block.blockID; + return blockID >= Integer.MAX_VALUE ? false : (localsLiveOut[blockID] & (1L << local)) != 0L; } } - private static void storeTwo(Block block, int local) { - storeOne(block, local); - storeOne(block, local + 1); - } + public final class LargeLocalLiveness extends LocalLiveness { + private BitSet[] localsLiveIn; + private BitSet[] localsLiveOut; + private BitSet[] localsLiveGen; + private BitSet[] localsLiveKill; + + public LargeLocalLiveness() { + localsLiveIn = new BitSet[blocks.size()]; + localsLiveOut = new BitSet[blocks.size()]; + localsLiveGen = new BitSet[blocks.size()]; + localsLiveKill = new BitSet[blocks.size()]; + for (int i = 0; i < blocks.size(); i++) { + localsLiveIn[i] = new BitSet(method.getMaxLocals()); + localsLiveOut[i] = new BitSet(method.getMaxLocals()); + localsLiveGen[i] = new BitSet(method.getMaxLocals()); + localsLiveKill[i] = new BitSet(method.getMaxLocals()); + } + } + + @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(); + } - private static void storeOne(Block block, int local) { - if (!block.localsLiveGen.get(local)) { - block.localsLiveKill.set(local); + @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); + } + } + + @Override + public boolean localIsLiveIn(Block block, int local) { + return block.blockID >= Integer.MAX_VALUE ? true : localsLiveIn[block.blockID].get(local); + } + + @Override + public boolean localIsLiveOut(Block block, int local) { + return block.blockID >= Integer.MAX_VALUE ? true : localsLiveOut[block.blockID].get(local); } } }
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java Fri Mar 14 09:58:31 2014 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java Fri Mar 14 15:29:17 2014 +0100 @@ -32,6 +32,8 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.Node.Verbosity; +import com.oracle.graal.java.BciBlockMapping.Block; +import com.oracle.graal.java.BciBlockMapping.LocalLiveness; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.java.*; @@ -315,13 +317,21 @@ } } - public void clearNonLiveLocals(BitSet liveness) { + public void clearNonLiveLocals(Block block, LocalLiveness liveness, boolean liveIn) { if (liveness == null) { return; } - for (int i = 0; i < locals.length; i++) { - if (!liveness.get(i)) { - locals[i] = null; + if (liveIn) { + for (int i = 0; i < locals.length; i++) { + if (!liveness.localIsLiveIn(block, i)) { + locals[i] = null; + } + } + } else { + for (int i = 0; i < locals.length; i++) { + if (!liveness.localIsLiveOut(block, i)) { + locals[i] = null; + } } } }
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Fri Mar 14 09:58:31 2014 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Fri Mar 14 15:29:17 2014 +0100 @@ -42,6 +42,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.java.BciBlockMapping.Block; import com.oracle.graal.java.BciBlockMapping.ExceptionDispatchBlock; +import com.oracle.graal.java.BciBlockMapping.LocalLiveness; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.calc.FloatConvertNode.FloatConvert; @@ -159,6 +160,7 @@ } private Block[] loopHeaders; + private LocalLiveness liveness; /** * Gets the current frame state being processed by this builder. @@ -225,6 +227,7 @@ // compute the block map, setup exception handlers and get the entrypoint(s) BciBlockMapping blockMap = BciBlockMapping.create(method); loopHeaders = blockMap.loopHeaders; + liveness = blockMap.liveness; lastInstr = currentGraph.start(); if (isSynchronized(method.getModifiers())) { @@ -233,7 +236,7 @@ methodSynchronizedObject = synchronizedObject(frameState, method); lastInstr = genMonitorEnter(methodSynchronizedObject); } - frameState.clearNonLiveLocals(blockMap.startBlock.localsLiveIn); + frameState.clearNonLiveLocals(blockMap.startBlock, liveness, true); ((StateSplit) lastInstr).setStateAfter(frameState.create(0)); if (graphBuilderConfig.eagerInfopointMode()) { @@ -1228,7 +1231,7 @@ createInvoke(callTarget, resultType); } else { assert bci() == currentBlock.endBci; - frameState.clearNonLiveLocals(currentBlock.localsLiveOut); + frameState.clearNonLiveLocals(currentBlock, liveness, false); InvokeWithExceptionNode invoke = createInvokeWithException(callTarget, resultType); @@ -1544,7 +1547,7 @@ Target target = checkLoopExit(block.firstInstruction, block, state); FixedNode result = target.fixed; block.entryState = target.state == state ? state.copy() : target.state; - block.entryState.clearNonLiveLocals(block.localsLiveIn); + block.entryState.clearNonLiveLocals(block, liveness, true); Debug.log("createTarget %s: first visit, result: %s", block, block.firstInstruction); return result; @@ -1823,7 +1826,7 @@ bci = stream.currentBCI(); if (bci > block.endBci) { - frameState.clearNonLiveLocals(currentBlock.localsLiveOut); + frameState.clearNonLiveLocals(currentBlock, liveness, false); } if (lastInstr instanceof StateSplit) { if (lastInstr.getClass() == AbstractBeginNode.class) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Fri Mar 14 09:58:31 2014 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Fri Mar 14 15:29:17 2014 +0100 @@ -222,7 +222,8 @@ } } else if (b instanceof InstanceOfNode) { InstanceOfNode instanceOfB = (InstanceOfNode) b; - if (instanceOfA.object() == instanceOfB.object() && !instanceOfA.type().isAssignableFrom(instanceOfB.type()) && !instanceOfB.type().isAssignableFrom(instanceOfA.type())) { + if (instanceOfA.object() == instanceOfB.object() && !instanceOfA.type().isInterface() && !instanceOfB.type().isInterface() && + !instanceOfA.type().isAssignableFrom(instanceOfB.type()) && !instanceOfB.type().isAssignableFrom(instanceOfA.type())) { // Two instanceof on the same value with mutually exclusive types. JavaTypeProfile profileA = instanceOfA.profile(); JavaTypeProfile profileB = instanceOfB.profile();
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/FrameStateAssignmentPhase.java Fri Mar 14 09:58:31 2014 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/FrameStateAssignmentPhase.java Fri Mar 14 15:29:17 2014 +0100 @@ -59,8 +59,9 @@ if (node instanceof StateSplit) { StateSplit stateSplit = (StateSplit) node; - if (stateSplit.stateAfter() != null) { - FrameState newState = stateSplit.stateAfter(); + FrameState stateAfter = stateSplit.stateAfter(); + if (stateAfter != null) { + FrameState newState = stateAfter; stateSplit.setStateAfter(null); return newState; }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Fri Mar 14 09:58:31 2014 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Fri Mar 14 15:29:17 2014 +0100 @@ -292,7 +292,7 @@ } private void printSchedule(String desc) { - if (Debug.isEnabled()) { + if (Debug.isLogEnabled()) { Debug.printf("=== %s / %s / %s (%s) ===\n", getCFG().getStartBlock().getBeginNode().graph(), selectedStrategy, memsched, desc); for (Block b : getCFG().getBlocks()) { Debug.printf("==== b: %s (loopDepth: %s). ", b, b.getLoopDepth()); @@ -388,8 +388,7 @@ private void assignBlockToNode(ScheduledNode node, SchedulingStrategy strategy) { assert !node.isDeleted(); - Block prevBlock = cfg.getNodeToBlock().get(node); - if (prevBlock != null) { + if (cfg.getNodeToBlock().containsKey(node)) { return; } // PhiNodes, ProxyNodes and FixedNodes should already have been placed in blocks by @@ -418,6 +417,7 @@ block = latestBlock(node, strategy); } if (block == null) { + // handle nodes without usages block = earliestBlock; } else if (strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS && !(node instanceof VirtualObjectNode)) { // schedule at the latest position possible in the outermost loop possible @@ -752,10 +752,14 @@ if (!(usage instanceof FrameState)) { throw new SchedulingError(usage.toString()); } - // If a FrameState belongs to a BeginNode then it's inputs will be placed at the - // common dominator of all EndNodes. - for (Node pred : unscheduledUsage.cfgPredecessors()) { - closure.apply(cfg.getNodeToBlock().get(pred)); + if (unscheduledUsage instanceof StartNode) { + closure.apply(cfg.getNodeToBlock().get(unscheduledUsage)); + } else { + // If a FrameState belongs to a BeginNode then it's inputs will be placed at + // the common dominator of all EndNodes. + for (Node pred : unscheduledUsage.cfgPredecessors()) { + closure.apply(cfg.getNodeToBlock().get(pred)); + } } } else { // For the time being, FrameStates can only be connected to NodeWithState.
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java Fri Mar 14 09:58:31 2014 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java Fri Mar 14 15:29:17 2014 +0100 @@ -26,7 +26,12 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.VirtualState.NodeClosure; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.graph.*; +import com.oracle.graal.phases.graph.ReentrantBlockIterator.*; +import com.oracle.graal.phases.schedule.*; +import com.oracle.graal.phases.schedule.SchedulePhase.*; public final class GraphOrder { @@ -34,9 +39,9 @@ } /** - * Asserts that there are no (invalid) cycles in the given graph. First, an ordered list of all - * nodes in the graph (a total ordering) is created. A second run over this list checks whether - * inputs are scheduled before their usages. + * Quick (and imprecise) assertion that there are no (invalid) cycles in the given graph. First, + * an ordered list of all nodes in the graph (a total ordering) is created. A second run over + * this list checks whether inputs are scheduled before their usages. * * @param graph the graph to be checked. * @throws AssertionError if a cycle was detected. @@ -62,7 +67,6 @@ } visited.mark(node); } - return true; } @@ -80,34 +84,161 @@ } private static void visitForward(ArrayList<Node> nodes, NodeBitMap visited, Node node, boolean floatingOnly) { - if (node != null && !visited.isMarked(node)) { - assert !floatingOnly || !(node instanceof FixedNode) : "unexpected reference to fixed node: " + node + " (this indicates an unexpected cycle)"; - visited.mark(node); - FrameState stateAfter = null; - if (node instanceof StateSplit) { - stateAfter = ((StateSplit) node).stateAfter(); - } - for (Node input : node.inputs()) { - if (input != stateAfter) { - visitForward(nodes, visited, input, true); + try { + assert node.isAlive() : node + " not alive"; + if (node != null && !visited.isMarked(node)) { + if (floatingOnly && node instanceof FixedNode) { + throw new GraalInternalError("unexpected reference to fixed node: %s (this indicates an unexpected cycle)", node); + } + visited.mark(node); + FrameState stateAfter = null; + if (node instanceof StateSplit) { + stateAfter = ((StateSplit) node).stateAfter(); + } + for (Node input : node.inputs()) { + if (input != stateAfter) { + visitForward(nodes, visited, input, true); + } + } + if (node instanceof EndNode) { + EndNode end = (EndNode) node; + for (PhiNode phi : end.merge().phis()) { + visitForward(nodes, visited, phi.valueAt(end), true); + } + } + nodes.add(node); + if (node instanceof MergeNode) { + for (PhiNode phi : ((MergeNode) node).phis()) { + visited.mark(phi); + nodes.add(phi); + } + } + if (stateAfter != null) { + visitForward(nodes, visited, stateAfter, true); } } - if (node instanceof EndNode) { - EndNode end = (EndNode) node; - for (PhiNode phi : end.merge().phis()) { - visitForward(nodes, visited, phi.valueAt(end), true); - } - } - nodes.add(node); - if (node instanceof MergeNode) { - for (PhiNode phi : ((MergeNode) node).phis()) { - visited.mark(phi); - nodes.add(phi); - } - } - if (stateAfter != null) { - visitForward(nodes, visited, stateAfter, true); - } + } catch (GraalInternalError e) { + e.addContext(node); + throw e; } } + + /** + * This method schedules the graph and makes sure that, for every node, all inputs are available + * at the position where it is scheduled. This is a very expensive assertion. + * + * Also, this phase assumes ProxyNodes to exist at LoopExitNodes, so that it cannot be run after + * phases that remove loop proxies or move proxies to BeginNodes. + */ + public static boolean assertSchedulableGraph(final StructuredGraph graph) { + try { + final SchedulePhase schedule = new SchedulePhase(SchedulingStrategy.LATEST_OUT_OF_LOOPS, MemoryScheduling.NONE); + final IdentityHashMap<LoopBeginNode, NodeBitMap> loopEntryStates = new IdentityHashMap<>(); + schedule.apply(graph, false); + + BlockIteratorClosure<NodeBitMap> closure = new BlockIteratorClosure<NodeBitMap>() { + + @Override + protected List<NodeBitMap> processLoop(Loop loop, NodeBitMap initialState) { + return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates; + } + + @Override + protected NodeBitMap processBlock(final Block block, final NodeBitMap currentState) { + final List<ScheduledNode> list = schedule.getBlockToNodesMap().get(block); + + /* + * A stateAfter is not valid directly after its associated state split, but + * right before the next fixed node. Therefore a pending stateAfter is kept that + * will be checked at the correct position. + */ + FrameState pendingStateAfter = null; + for (final ScheduledNode node : list) { + FrameState stateAfter = node instanceof StateSplit ? ((StateSplit) node).stateAfter() : null; + + if (pendingStateAfter != null && node instanceof FixedNode) { + pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() { + public void apply(Node usage, Node nonVirtualNode) { + assert currentState.isMarked(nonVirtualNode) : nonVirtualNode + " not available at virtualstate " + usage + " before " + node + " in block " + block + " \n" + list; + } + }); + pendingStateAfter = null; + } + + if (node instanceof MergeNode) { + // phis aren't scheduled, so they need to be added explicitly + currentState.markAll(((MergeNode) node).phis()); + if (node instanceof LoopBeginNode) { + // remember the state at the loop entry, it's restored at exits + loopEntryStates.put((LoopBeginNode) node, currentState.copy()); + } + } else if (node instanceof ProxyNode) { + for (Node input : node.inputs()) { + if (input != ((ProxyNode) node).proxyPoint()) { + assert currentState.isMarked(input) : input + " not available at " + node + " in block " + block + "\n" + list; + } + } + } else if (node instanceof LoopExitNode) { + // the contents of the loop are only accessible via proxies at the exit + currentState.clearAll(); + currentState.markAll(loopEntryStates.get(((LoopExitNode) node).loopBegin())); + // Loop proxies aren't scheduled, so they need to be added explicitly + currentState.markAll(((LoopExitNode) node).proxies()); + } else { + for (Node input : node.inputs()) { + if (input != stateAfter) { + assert currentState.isMarked(input) : input + " not available at " + node + " in block " + block + "\n" + list; + } + } + } + if (node instanceof AbstractEndNode) { + MergeNode merge = ((AbstractEndNode) node).merge(); + for (PhiNode phi : merge.phis()) { + assert currentState.isMarked(phi.valueAt((AbstractEndNode) node)) : phi.valueAt((AbstractEndNode) node) + " not available at phi " + phi + " / end " + node + + " in block " + block; + } + } + if (stateAfter != null) { + assert pendingStateAfter == null; + pendingStateAfter = stateAfter; + } + currentState.mark(node); + } + if (pendingStateAfter != null) { + pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() { + public void apply(Node usage, Node nonVirtualNode) { + assert currentState.isMarked(nonVirtualNode) : nonVirtualNode + " not available at virtualstate " + usage + " at end of block " + block + " \n" + list; + } + }); + } + return currentState; + } + + @Override + protected NodeBitMap merge(Block merge, List<NodeBitMap> states) { + NodeBitMap result = states.get(0); + for (int i = 1; i < states.size(); i++) { + result.intersect(states.get(i)); + } + return result; + } + + @Override + protected NodeBitMap getInitialState() { + return graph.createNodeBitMap(); + } + + @Override + protected NodeBitMap cloneState(NodeBitMap oldState) { + return oldState.copy(); + } + }; + + ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock()); + + } catch (Throwable t) { + throw new AssertionError("unschedulable graph", t); + } + return true; + } }