# HG changeset patch # User Thomas Wuerthinger # Date 1425131699 -3600 # Node ID 96cf6f7678d27f451434e5307af91b0a982cd46e # Parent 86909168a529af26bd90c5681d78d179610e855b Add test case and support for nested loops for Truffle bytecode interpreters. diff -r 86909168a529 -r 96cf6f7678d2 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 Sat Feb 28 14:54:29 2015 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Sat Feb 28 14:54:59 2015 +0100 @@ -331,6 +331,7 @@ } if (this.mergeExplosions) { + Debug.dump(currentGraph, "Before loop detection"); detectLoops(startInstruction); } @@ -373,7 +374,6 @@ LoopBeginNode loopBegin = (LoopBeginNode) ((EndNode) merge.next()).merge(); LoopEndNode loopEnd = currentGraph.add(new LoopEndNode(loopBegin)); endNode.replaceAndDelete(loopEnd); - System.out.println("Cycle detected! root node: " + n); } else if (visited.contains(n)) { // Normal merge into a branch we are already exploring. } else { @@ -384,6 +384,7 @@ } } + Debug.dump(currentGraph, "After loops detected"); insertLoopEnds(startInstruction); } @@ -413,6 +414,17 @@ for (int i = loopBegins.size() - 1; i >= 0; --i) { LoopBeginNode loopBegin = loopBegins.get(i); insertLoopExits(loopBegin, innerLoopsMap); + if (GraalOptions.DumpDuringGraphBuilding.getValue()) { + Debug.dump(currentGraph, "After building loop exits for %s.", loopBegin); + } + } + + // Remove degenerated merges with only one predecessor. + for (LoopBeginNode loopBegin : loopBegins) { + Node pred = loopBegin.forwardEnd().predecessor(); + if (pred instanceof MergeNode) { + MergeNode.removeMergeIfDegenerated((MergeNode) pred); + } } } @@ -429,23 +441,28 @@ while (!stack.isEmpty()) { Node current = stack.pop(); + if (current == loopBegin) { + continue; + } for (Node pred : current.cfgPredecessors()) { - if (pred instanceof LoopExitNode) { - // Inner loop - LoopExitNode loopExitNode = (LoopExitNode) pred; - LoopBeginNode innerLoopBegin = loopExitNode.loopBegin(); - if (!visited.isMarked(innerLoopBegin)) { - stack.push(innerLoopBegin); - visited.mark(innerLoopBegin); - innerLoopBegins.add(innerLoopBegin); + if (!visited.isMarked(pred)) { + visited.mark(pred); + if (pred instanceof LoopExitNode) { + // Inner loop + LoopExitNode loopExitNode = (LoopExitNode) pred; + LoopBeginNode innerLoopBegin = loopExitNode.loopBegin(); + if (!visited.isMarked(innerLoopBegin)) { + stack.push(innerLoopBegin); + visited.mark(innerLoopBegin); + innerLoopBegins.add(innerLoopBegin); + } + } else { + if (pred instanceof ControlSplitNode) { + ControlSplitNode controlSplitNode = (ControlSplitNode) pred; + controlSplits.add(controlSplitNode); + } + stack.push(pred); } - } else if (!visited.isMarked(pred)) { - if (pred instanceof ControlSplitNode) { - ControlSplitNode controlSplitNode = (ControlSplitNode) pred; - controlSplits.add(controlSplitNode); - } - stack.push(pred); - visited.mark(pred); } } } @@ -463,6 +480,9 @@ for (LoopBeginNode inner : innerLoopBegins) { addLoopExits(loopBegin, inner, innerLoopsMap, visited); + if (GraalOptions.DumpDuringGraphBuilding.getValue()) { + Debug.dump(currentGraph, "After adding loop exits for %s.", inner); + } } innerLoopsMap.put(loopBegin, innerLoopBegins); @@ -1648,7 +1668,7 @@ // time mark the context loop begin as hit during the current // iteration. if (this.mergeExplosions) { - this.addToMergeCache(state.copy(), nextPeelIteration); + this.addToMergeCache(state, nextPeelIteration); } context.targetPeelIteration[context.targetPeelIteration.length - 1] = nextPeelIteration++; if (nextPeelIteration > MaximumLoopExplosionCount.getValue()) { @@ -1879,6 +1899,8 @@ setEntryState(block, this.getCurrentDimension(), frameState.copy()); Debug.log(" created loop header %s", loopBegin); + } else if (block.isLoopHeader && explodeLoops && this.mergeExplosions) { + frameState = frameState.copy(); } assert lastInstr.next() == null : "instructions already appended at block " + block; Debug.log(" frameState: %s", frameState); diff -r 86909168a529 -r 96cf6f7678d2 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 Sat Feb 28 14:54:29 2015 +0100 +++ b/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java Sat Feb 28 14:54:59 2015 +0100 @@ -100,19 +100,19 @@ switch (bc) { case Bytecode.CONST: value = bytecodes[bci + 1]; - trace("%d: CONST %s", bci, value); + trace("%d (%d): CONST %s", bci, topOfStack, value); setInt(frame, ++topOfStack, value); bci = bci + 2; continue; case Bytecode.RETURN: - trace("%d: RETURN", bci); + trace("%d (%d): RETURN", bci, topOfStack); return getInt(frame, topOfStack); case Bytecode.ADD: { int left = getInt(frame, topOfStack); int right = getInt(frame, topOfStack - 1); - trace("%d: ADD %d %d", bci, left, right); + trace("%d (%d): ADD %d %d", bci, topOfStack, left, right); setInt(frame, topOfStack - 1, left + right); topOfStack--; bci = bci + 1; @@ -120,7 +120,7 @@ } case Bytecode.IFZERO: - trace("%d: IFZERO", bci); + trace("%d (%d): IFZERO", bci, topOfStack); if (getInt(frame, topOfStack--) == 0) { bci = bytecodes[bci + 1]; continue; @@ -130,18 +130,18 @@ } case Bytecode.POP: - trace("%d: POP", bci); + trace("%d (%d): POP", bci, topOfStack); topOfStack--; bci++; continue; case Bytecode.JMP: - trace("%d: JMP", bci); + trace("%d (%d): JMP", bci, topOfStack); bci = bytecodes[bci + 1]; continue; case Bytecode.DUP: - trace("%d: DUP", bci); + trace("%d (%d): DUP", bci, topOfStack); setInt(frame, topOfStack + 1, getInt(frame, topOfStack)); topOfStack++; bci++; @@ -236,20 +236,19 @@ assertPartialEvalEqualsAndRunsCorrect(new Program("simpleLoopProgram", bytecodes, 0, 3)); } - @Ignore @Test public void nestedLoopsProgram() { byte[] bytecodes = new byte[]{ /* 0: */Bytecode.CONST, /* 1: */42, /* 2: */Bytecode.CONST, - /* 3: */-12, + /* 3: */-2, /* 4: */Bytecode.CONST, /* 5: */1, /* 6: */Bytecode.ADD, /* 7: */Bytecode.DUP, /* 8: */Bytecode.CONST, - /* 9: */-12, + /* 9: */-2, /* 10: */Bytecode.CONST, /* 11: */1, /* 12: */Bytecode.ADD, @@ -258,13 +257,13 @@ /* 15: */18, /* 16: */Bytecode.JMP, /* 17: */10, - /* 18: */Bytecode.IFZERO, - /* 19: */22, - /* 20: */Bytecode.JMP, - /* 21: */4, - /* 22: */Bytecode.POP, - /* 22: */Bytecode.POP, - /* 23: */Bytecode.RETURN}; + /* 18: */Bytecode.POP, + /* 19: */Bytecode.IFZERO, + /* 20: */23, + /* 21: */Bytecode.JMP, + /* 22: */4, + /* 23: */Bytecode.POP, + /* 24: */Bytecode.RETURN}; assertPartialEvalEqualsAndRunsCorrect(new Program("nestedLoopsProgram", bytecodes, 0, 6)); }