Mercurial > hg > graal-jvmci-8
changeset 19639:f727ca2940ba
Support for loops for Truffle bytecode interpreters.
author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
---|---|
date | Fri, 27 Feb 2015 22:49:50 +0100 |
parents | 312bf1b3f410 |
children | c96ebc780911 |
files | graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java |
diffstat | 2 files changed, 158 insertions(+), 7 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Fri Feb 27 22:49:26 2015 +0100 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Fri Feb 27 22:49:50 2015 +0100 @@ -330,12 +330,159 @@ index = iterateBlock(blocks, block); } + if (this.mergeExplosions) { + detectLoops(startInstruction); + } + if (Debug.isDumpEnabled() && DumpDuringGraphBuilding.getValue() && this.beforeReturnNode != startInstruction) { Debug.dump(currentGraph, "Bytecodes parsed: " + method.getDeclaringClass().getUnqualifiedName() + "." + method.getName()); } } } + private void detectLoops(FixedNode startInstruction) { + NodeBitMap visited = currentGraph.createNodeBitMap(); + NodeBitMap active = currentGraph.createNodeBitMap(); + Stack<Node> stack = new Stack<>(); + stack.add(startInstruction); + visited.mark(startInstruction); + while (!stack.isEmpty()) { + Node next = stack.peek(); + assert next.isDeleted() || visited.isMarked(next); + if (next.isDeleted() || active.isMarked(next)) { + stack.pop(); + if (!next.isDeleted()) { + active.clear(next); + } + } else { + active.mark(next); + for (Node n : next.cfgSuccessors()) { + if (active.contains(n)) { + // Detected cycle. + assert n instanceof MergeNode; + assert next instanceof EndNode; + MergeNode merge = (MergeNode) n; + EndNode endNode = (EndNode) next; + merge.removeEnd(endNode); + FixedNode afterMerge = merge.next(); + if (!(afterMerge instanceof EndNode) || !(((EndNode) afterMerge).merge() instanceof LoopBeginNode)) { + merge.setNext(null); + LoopBeginNode newLoopBegin = this.appendLoopBegin(merge); + newLoopBegin.setNext(afterMerge); + } + 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 { + visited.mark(n); + stack.push(n); + } + } + } + } + + insertLoopEnds(startInstruction); + } + + private void insertLoopEnds(FixedNode startInstruction) { + NodeBitMap visited = currentGraph.createNodeBitMap(); + Stack<Node> stack = new Stack<>(); + stack.add(startInstruction); + visited.mark(startInstruction); + List<LoopBeginNode> loopBegins = new ArrayList<>(); + while (!stack.isEmpty()) { + Node next = stack.pop(); + assert visited.isMarked(next); + if (next instanceof LoopBeginNode) { + loopBegins.add((LoopBeginNode) next); + } + for (Node n : next.cfgSuccessors()) { + if (visited.contains(n)) { + // Nothing to do. + } else { + visited.mark(n); + stack.push(n); + } + } + } + + IdentityHashMap<LoopBeginNode, List<LoopBeginNode>> innerLoopsMap = new IdentityHashMap<>(); + for (int i = loopBegins.size() - 1; i >= 0; --i) { + LoopBeginNode loopBegin = loopBegins.get(i); + insertLoopExits(loopBegin, innerLoopsMap); + } + } + + private void insertLoopExits(LoopBeginNode loopBegin, IdentityHashMap<LoopBeginNode, List<LoopBeginNode>> innerLoopsMap) { + NodeBitMap visited = currentGraph.createNodeBitMap(); + Stack<Node> stack = new Stack<>(); + for (LoopEndNode loopEnd : loopBegin.loopEnds()) { + stack.push(loopEnd); + visited.mark(loopEnd); + } + + List<ControlSplitNode> controlSplits = new ArrayList<>(); + List<LoopBeginNode> innerLoopBegins = new ArrayList<>(); + + while (!stack.isEmpty()) { + Node current = stack.pop(); + 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); + } + } else if (!visited.isMarked(pred)) { + if (pred instanceof ControlSplitNode) { + ControlSplitNode controlSplitNode = (ControlSplitNode) pred; + controlSplits.add(controlSplitNode); + } + stack.push(pred); + visited.mark(pred); + } + } + } + + for (ControlSplitNode controlSplit : controlSplits) { + for (Node succ : controlSplit.cfgSuccessors()) { + if (!visited.isMarked(succ)) { + LoopExitNode loopExit = currentGraph.add(new LoopExitNode(loopBegin)); + FixedNode next = ((FixedWithNextNode) succ).next(); + next.replaceAtPredecessor(loopExit); + loopExit.setNext(next); + } + } + } + + for (LoopBeginNode inner : innerLoopBegins) { + addLoopExits(loopBegin, inner, innerLoopsMap, visited); + } + + innerLoopsMap.put(loopBegin, innerLoopBegins); + } + + private void addLoopExits(LoopBeginNode loopBegin, LoopBeginNode inner, IdentityHashMap<LoopBeginNode, List<LoopBeginNode>> innerLoopsMap, NodeBitMap visited) { + for (LoopExitNode exit : inner.loopExits()) { + if (!visited.isMarked(exit)) { + LoopExitNode newLoopExit = currentGraph.add(new LoopExitNode(loopBegin)); + FixedNode next = exit.next(); + next.replaceAtPredecessor(newLoopExit); + newLoopExit.setNext(next); + } + } + + for (LoopBeginNode innerInner : innerLoopsMap.get(inner)) { + addLoopExits(loopBegin, innerInner, innerLoopsMap, visited); + } + } + private int iterateBlock(BciBlock[] blocks, BciBlock block) { if (block.isLoopHeader && this.explodeLoops) { return iterateExplodedLoopHeader(blocks, block); @@ -1712,11 +1859,7 @@ // Create the loop header block, which later will merge the backward branches of // the loop. controlFlowSplit = true; - EndNode preLoopEnd = currentGraph.add(new EndNode()); - LoopBeginNode loopBegin = currentGraph.add(new LoopBeginNode()); - lastInstr.setNext(preLoopEnd); - // Add the single non-loop predecessor of the loop header. - loopBegin.addForwardEnd(preLoopEnd); + LoopBeginNode loopBegin = appendLoopBegin(this.lastInstr); lastInstr = loopBegin; // Create phi functions for all local variables and operand stack slots. @@ -1804,6 +1947,15 @@ } } + private LoopBeginNode appendLoopBegin(FixedWithNextNode fixedWithNext) { + EndNode preLoopEnd = currentGraph.add(new EndNode()); + LoopBeginNode loopBegin = currentGraph.add(new LoopBeginNode()); + fixedWithNext.setNext(preLoopEnd); + // Add the single non-loop predecessor of the loop header. + loopBegin.addForwardEnd(preLoopEnd); + return loopBegin; + } + /** * A hook for derived classes to modify the last instruction or add other instructions. *
--- a/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java Fri Feb 27 22:49:26 2015 +0100 +++ b/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java Fri Feb 27 22:49:50 2015 +0100 @@ -217,7 +217,6 @@ } @Test - @Ignore public void simpleLoopProgram() { byte[] bytecodes = new byte[]{ /* 0: */Bytecode.CONST, @@ -234,7 +233,7 @@ /* 11: */4, /* 12: */Bytecode.POP, /* 13: */Bytecode.RETURN}; - assertPartialEvalEqualsAndRunsCorrect(new Program("ifAndPopProgram", bytecodes, 0, 3)); + assertPartialEvalEqualsAndRunsCorrect(new Program("simpleLoopProgram", bytecodes, 0, 3)); } @Test(timeout = 1000)