# HG changeset patch # User Thomas Wuerthinger # Date 1425049272 -3600 # Node ID 490f2c54c28af6fc9df1d169970a52b125ff7cb6 # Parent 0e90dbf0b9fd2a679174385fcf124cb914ac6738 Support for creating merges during partial evaluation of bytecode interpreters. diff -r 0e90dbf0b9fd -r 490f2c54c28a graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java --- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Fri Feb 27 14:06:36 2015 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Fri Feb 27 16:01:12 2015 +0100 @@ -204,6 +204,7 @@ private FixedWithNextNode lastInstr; // the last instruction added private final boolean explodeLoops; private final boolean mergeExplosions; + private final Map mergeExplosionsMap; private Stack explodeLoopsContext; private int nextPeelIteration = 1; private boolean controlFlowSplit; @@ -233,12 +234,15 @@ explodeLoops = loopExplosionPlugin.shouldExplodeLoops(method); if (explodeLoops) { mergeExplosions = loopExplosionPlugin.shouldMergeExplosions(method); + mergeExplosionsMap = new HashMap<>(); } else { mergeExplosions = false; + mergeExplosionsMap = null; } } else { explodeLoops = false; mergeExplosions = false; + mergeExplosionsMap = null; } } @@ -349,6 +353,9 @@ ExplodedLoopContext context = new ExplodedLoopContext(); context.header = header; context.peelIteration = this.getCurrentDimension(); + if (this.mergeExplosions) { + this.addToMergeCache(getEntryState(context.header, context.peelIteration), context.peelIteration); + } explodeLoopsContext.push(context); if (Debug.isDumpEnabled() && DumpDuringGraphBuilding.getValue()) { Debug.dump(currentGraph, "before loop explosion dimension " + context.peelIteration); @@ -359,9 +366,12 @@ return header.loopEnd + 1; } + private void addToMergeCache(HIRFrameStateBuilder key, int dimension) { + mergeExplosionsMap.put(key, dimension); + } + private void peelIteration(BciBlock[] blocks, BciBlock header, ExplodedLoopContext context) { while (true) { - processBlock(this, header); for (int j = header.getId() + 1; j <= header.loopEnd; ++j) { BciBlock block = blocks[j]; @@ -1372,7 +1382,7 @@ assert block != null && state != null; assert !block.isExceptionEntry || state.stackSize() == 1; - int operatingDimension = findOperatingDimension(block); + int operatingDimension = findOperatingDimension(block, state); if (getFirstInstruction(block, operatingDimension) == null) { /* @@ -1417,8 +1427,8 @@ 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 getFirstInstruction(block, operatingDimension).next() == null : "bytecodes already parsed for block"; + assert currentBlock == null || currentBlock.getId() < block.getId() || this.mergeExplosions : "must not be backward branch"; + assert getFirstInstruction(block, operatingDimension).next() == null || this.mergeExplosions : "bytecodes already parsed for block"; if (getFirstInstruction(block, operatingDimension) instanceof AbstractBeginNode && !(getFirstInstruction(block, operatingDimension) instanceof AbstractMergeNode)) { /* @@ -1459,19 +1469,27 @@ return result; } - private int findOperatingDimension(BciBlock block) { + private int findOperatingDimension(BciBlock block, HIRFrameStateBuilder state) { if (this.explodeLoops && this.explodeLoopsContext != null && !this.explodeLoopsContext.isEmpty()) { - return findOperatingDimensionWithLoopExplosion(block); + return findOperatingDimensionWithLoopExplosion(block, state); } return this.getCurrentDimension(); } - private int findOperatingDimensionWithLoopExplosion(BciBlock block) { + private int findOperatingDimensionWithLoopExplosion(BciBlock block, HIRFrameStateBuilder state) { int i; for (i = explodeLoopsContext.size() - 1; i >= 0; --i) { ExplodedLoopContext context = explodeLoopsContext.elementAt(i); if (context.header == block) { + if (this.mergeExplosions) { + state.clearNonLiveLocals(block, liveness, true); + Integer cachedDimension = mergeExplosionsMap.get(state); + if (cachedDimension != null) { + return cachedDimension; + } + } + // We have a hit on our current explosion context loop begin. if (context.targetPeelIteration == null) { context.targetPeelIteration = new int[1]; @@ -1482,6 +1500,9 @@ // 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. + if (this.mergeExplosions) { + this.addToMergeCache(state.copy(), nextPeelIteration); + } context.targetPeelIteration[context.targetPeelIteration.length - 1] = nextPeelIteration++; if (nextPeelIteration > MaximumLoopExplosionCount.getValue()) { String message = "too many loop explosion interations - does the explosion not terminate for method " + method + "?"; diff -r 0e90dbf0b9fd -r 490f2c54c28a graal/com.oracle.graal.java/src/com/oracle/graal/java/HIRFrameStateBuilder.java --- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/HIRFrameStateBuilder.java Fri Feb 27 14:06:36 2015 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/HIRFrameStateBuilder.java Fri Feb 27 16:01:12 2015 +0100 @@ -873,4 +873,61 @@ assert xpeek() == null; return true; } + + @Override + public int hashCode() { + int result = hashCode(locals, locals.length); + result *= 13; + result += hashCode(stack, this.stackSize); + return result; + } + + private static int hashCode(Object[] a, int length) { + int result = 1; + for (int i = 0; i < length; ++i) { + Object element = a[i]; + result = 31 * result + (element == null ? 0 : System.identityHashCode(element)); + } + return result; + } + + private static boolean equals(ValueNode[] a, ValueNode[] b, int length) { + for (int i = 0; i < length; ++i) { + if (a[i] != b[i]) { + return false; + } + } + return true; + } + + @Override + public boolean equals(Object otherObject) { + if (otherObject instanceof HIRFrameStateBuilder) { + HIRFrameStateBuilder other = (HIRFrameStateBuilder) otherObject; + if (other.method != method) { + return false; + } + if (other.stackSize != stackSize) { + return false; + } + if (other.checkTypes != checkTypes) { + return false; + } + if (other.rethrowException != rethrowException) { + return false; + } + if (other.graph != graph) { + return false; + } + if (other.outerFrameStateSupplier != outerFrameStateSupplier) { + return false; + } + if (other.locals.length != locals.length) { + return false; + } + return equals(other.locals, locals, locals.length) && equals(other.stack, stack, stackSize) && equals(other.lockedObjects, lockedObjects, lockedObjects.length) && + equals(other.monitorIds, monitorIds, monitorIds.length); + } + return false; + } } diff -r 0e90dbf0b9fd -r 490f2c54c28a graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java --- a/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java Fri Feb 27 14:06:36 2015 +0100 +++ b/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java Fri Feb 27 16:01:12 2015 +0100 @@ -26,7 +26,6 @@ import com.oracle.truffle.api.*; import com.oracle.truffle.api.CompilerDirectives.CompilationFinal; -import com.oracle.truffle.api.CompilerDirectives.TruffleBoundary; import com.oracle.truffle.api.frame.*; import com.oracle.truffle.api.nodes.*; @@ -37,14 +36,17 @@ public static final byte RETURN = 1; public static final byte ADD = 2; public static final byte IFZERO = 3; + public static final byte POP = 4; } public static class Program extends RootNode { - @CompilationFinal final byte[] bytecodes; + private final String name; + @CompilationFinal private final byte[] bytecodes; @CompilationFinal private final FrameSlot[] locals; @CompilationFinal private final FrameSlot[] stack; - public Program(byte[] bytecodes, int maxLocals, int maxStack) { + public Program(String name, byte[] bytecodes, int maxLocals, int maxStack) { + this.name = name; this.bytecodes = bytecodes; locals = new FrameSlot[maxLocals]; stack = new FrameSlot[maxStack]; @@ -70,9 +72,9 @@ } } - @TruffleBoundary - public void print(String name, int value) { - System.out.println(name + "=" + value); + @Override + public String toString() { + return name; } @Override @@ -89,14 +91,14 @@ value = bytecodes[bci + 1]; setInt(frame, ++topOfStack, value); bci = bci + 2; - break; + continue; case Bytecode.RETURN: return getInt(frame, topOfStack); case Bytecode.ADD: setInt(frame, topOfStack - 1, getInt(frame, topOfStack) + getInt(frame, topOfStack - 1)); topOfStack--; bci = bci + 1; - break; + continue; case Bytecode.IFZERO: if (getInt(frame, topOfStack--) == 0) { bci = bytecodes[bci + 1]; @@ -105,6 +107,10 @@ bci = bci + 2; continue; } + case Bytecode.POP: + topOfStack--; + bci++; + continue; } } } @@ -115,16 +121,16 @@ } @Test - public void simpleProgram() { + public void constReturnProgram() { byte[] bytecodes = new byte[]{ /* 0: */Bytecode.CONST, /* 1: */42, /* 2: */Bytecode.RETURN}; - assertPartialEvalEquals("constant42", new Program(bytecodes, 0, 2)); + assertPartialEvalEquals("constant42", new Program("constReturnProgram", bytecodes, 0, 2)); } @Test - public void simpleProgramWithAdd() { + public void constAddProgram() { byte[] bytecodes = new byte[]{ /* 0: */Bytecode.CONST, /* 1: */40, @@ -132,11 +138,11 @@ /* 3: */2, /* 4: */Bytecode.ADD, /* 5: */Bytecode.RETURN}; - assertPartialEvalEquals("constant42", new Program(bytecodes, 0, 2)); + assertPartialEvalEquals("constant42", new Program("constAddProgram", bytecodes, 0, 2)); } @Test - public void simpleProgramWithIf() { + public void simpleIfProgram() { byte[] bytecodes = new byte[]{ /* 0: */Bytecode.CONST, /* 1: */40, @@ -147,11 +153,27 @@ /* 6: */Bytecode.CONST, /* 7: */42, /* 8: */Bytecode.RETURN}; - assertPartialEvalEquals("constant42", new Program(bytecodes, 0, 3)); + assertPartialEvalEquals("constant42", new Program("simpleIfProgram", bytecodes, 0, 3)); + } + + @Test + public void ifAndPopProgram() { + byte[] bytecodes = new byte[]{ + /* 0: */Bytecode.CONST, + /* 1: */40, + /* 2: */Bytecode.CONST, + /* 3: */1, + /* 4: */Bytecode.IFZERO, + /* 5: */9, + /* 6: */Bytecode.POP, + /* 7: */Bytecode.CONST, + /* 8: */42, + /* 9: */Bytecode.RETURN}; + assertPartialEvalEquals("constant42", new Program("ifAndPopProgram", bytecodes, 0, 3)); } @Test(timeout = 1000) - public void simpleProgramWithManyIfs() { + public void manyIfsProgram() { byte[] bytecodes = new byte[]{ /* 0: */Bytecode.CONST, /* 1: */40, @@ -198,6 +220,6 @@ /* 42: */Bytecode.CONST, /* 43: */42, /* 44: */Bytecode.RETURN}; - assertPartialEvalEquals("constant42", new Program(bytecodes, 0, 3)); + assertPartialEvalEquals("constant42", new Program("manyIfsProgram", bytecodes, 0, 3)); } }