Mercurial > hg > truffle
changeset 19644:3ed1c541f420
Merge with 68dd6598be5f74970e7fc1a4a2fa4ccd166dbb11
| author | Michael Van De Vanter <michael.van.de.vanter@oracle.com> |
|---|---|
| date | Sat, 28 Feb 2015 12:50:25 -0800 |
| parents | ac35617db239 (current diff) 68dd6598be5f (diff) |
| children | 10a1fc5e3209 |
| files | |
| diffstat | 8 files changed, 286 insertions(+), 39 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java Sat Feb 28 09:32:36 2015 -0800 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java Sat Feb 28 12:50:25 2015 -0800 @@ -24,8 +24,6 @@ import java.util.*; -import com.oracle.graal.compiler.common.*; - public interface AbstractControlFlowGraph<T extends AbstractBlockBase<T>> { int BLOCK_ID_INITIAL = -1; @@ -73,26 +71,22 @@ * True if block {@code a} is dominated by block {@code b}. */ static boolean isDominatedBy(AbstractBlockBase<?> a, AbstractBlockBase<?> b) { - assert a != null; - AbstractBlockBase<?> dominator = a; - int i = 0; - while (dominator != null) { - if (i++ == Integer.MAX_VALUE) { // For safety - throw GraalInternalError.shouldNotReachHere(); - } - if (dominator == b) { - return true; - } - dominator = dominator.getDominator(); + assert a != null && b != null; + if (a == b) { + return true; } - return false; + if (a.getDominatorDepth() < b.getDominatorDepth()) { + return false; + } + + return b == (AbstractBlockBase<?>) a.getDominator(a.getDominatorDepth() - b.getDominatorDepth()); } /** * True if block {@code a} dominates block {@code b}. */ static boolean dominates(AbstractBlockBase<?> a, AbstractBlockBase<?> b) { - assert a != null; + assert a != null && b != null; return isDominatedBy(b, a); }
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Sat Feb 28 09:32:36 2015 -0800 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Sat Feb 28 12:50:25 2015 -0800 @@ -330,12 +330,179 @@ index = iterateBlock(blocks, block); } + if (this.mergeExplosions) { + Debug.dump(currentGraph, "Before loop detection"); + 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); + } else if (visited.contains(n)) { + // Normal merge into a branch we are already exploring. + } else { + visited.mark(n); + stack.push(n); + } + } + } + } + + Debug.dump(currentGraph, "After loops detected"); + 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); + 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); + } + } + } + + 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(); + if (current == loopBegin) { + continue; + } + for (Node pred : current.cfgPredecessors()) { + 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); + } + } + } + } + + 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); + if (GraalOptions.DumpDuringGraphBuilding.getValue()) { + Debug.dump(currentGraph, "After adding loop exits for %s.", inner); + } + } + + 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); @@ -1501,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()) { @@ -1712,11 +1879,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. @@ -1736,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); @@ -1804,6 +1969,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.loop/src/com/oracle/graal/loop/LoopEx.java Sat Feb 28 09:32:36 2015 -0800 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java Sat Feb 28 12:50:25 2015 -0800 @@ -175,13 +175,13 @@ negated = true; } LogicNode ifTest = ifNode.condition(); - if (!(ifTest instanceof IntegerLessThanNode)) { + if (!(ifTest instanceof IntegerLessThanNode) && !(ifTest instanceof IntegerEqualsNode)) { if (ifTest instanceof IntegerBelowNode) { Debug.log("Ignored potential Counted loop at %s with |<|", loopBegin); } return false; } - IntegerLessThanNode lessThan = (IntegerLessThanNode) ifTest; + CompareNode lessThan = (CompareNode) ifTest; Condition condition = null; InductionVariable iv = null; ValueNode limit = null; @@ -198,6 +198,9 @@ limit = lessThan.getY(); } } + if (iv != null && iv.isConstantStride() && iv.constantStride() != 1 && !(ifTest instanceof IntegerLessThanNode)) { + return false; + } if (condition == null) { return false; } @@ -206,6 +209,24 @@ } boolean oneOff = false; switch (condition) { + case EQ: + return false; + case NE: { + IntegerStamp initStamp = (IntegerStamp) iv.initNode().stamp(); + IntegerStamp limitStamp = (IntegerStamp) limit.stamp(); + if (iv.direction() == Direction.Up) { + if (initStamp.upperBound() > limitStamp.lowerBound()) { + return false; + } + } else { + assert iv.direction() == Direction.Down; + if (initStamp.lowerBound() < limitStamp.upperBound()) { + return false; + } + } + oneOff = true; + break; + } case LE: oneOff = true; // fall through case LT:
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/MergeNode.java Sat Feb 28 09:32:36 2015 -0800 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/MergeNode.java Sat Feb 28 12:50:25 2015 -0800 @@ -36,4 +36,21 @@ public MergeNode() { super(TYPE); } + + public static void removeMergeIfDegenerated(MergeNode node) { + if (node.forwardEndCount() == 1 && node.hasNoUsages()) { + FixedNode currentNext = node.next(); + node.setNext(null); + EndNode forwardEnd = node.forwardEndAt(0); + forwardEnd.replaceAtPredecessor(currentNext); + node.markDeleted(); + forwardEnd.markDeleted(); + } + } + + @Override + public boolean verify() { + assertTrue(this.forwardEndCount() > 1, "Must merge more than one end."); + return true; + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Sat Feb 28 09:32:36 2015 -0800 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Sat Feb 28 12:50:25 2015 -0800 @@ -173,6 +173,7 @@ // First time we see this block: push all successors. for (Node suxNode : block.getEndNode().cfgSuccessors()) { Block suxBlock = blockFor(suxNode); + assert suxBlock != null : suxNode; if (suxBlock.getId() == BLOCK_ID_INITIAL) { stack.add(suxBlock); }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Sat Feb 28 09:32:36 2015 -0800 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java Sat Feb 28 12:50:25 2015 -0800 @@ -322,11 +322,11 @@ @Override protected void run(StructuredGraph graph) { assert GraphOrder.assertNonCyclicGraph(graph); - cfg = ControlFlowGraph.compute(graph, true, true, true, true); + cfg = ControlFlowGraph.compute(graph, true, true, true, false); earliestCache = graph.createNodeMap(); blockToNodesMap = new BlockMap<>(cfg); - if (selectedStrategy != SchedulingStrategy.EARLIEST) { + if (selectedStrategy != SchedulingStrategy.EARLIEST && graph.isAfterFloatingReadPhase()) { blockToKillSet = new BlockMap<>(cfg); } @@ -359,7 +359,6 @@ for (Block b : getCFG().getBlocks()) { buf.format("==== b: %s (loopDepth: %s). ", b, b.getLoopDepth()); buf.format("dom: %s. ", b.getDominator()); - buf.format("post-dom: %s. ", b.getPostdominator()); buf.format("preds: %s. ", b.getPredecessors()); buf.format("succs: %s ====%n", b.getSuccessors()); BlockMap<LocationSet> killSets = blockToKillSet; @@ -1083,9 +1082,8 @@ addUnscheduledToLatestSorting(stateAfter, state); // Now predecessors and inputs are scheduled => we can add this node. - if (!state.containsInstruction(i)) { - state.addInstruction(i); - } + assert !state.containsInstruction(i); + state.addInstruction(i); if (state.readsSize() != 0 && i instanceof FloatingReadNode) { state.removeRead(i);
--- a/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java Sat Feb 28 09:32:36 2015 -0800 +++ b/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/BytecodeInterpreterPartialEvaluationTest.java Sat Feb 28 12:50:25 2015 -0800 @@ -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++; @@ -217,7 +217,6 @@ } @Test - @Ignore public void simpleLoopProgram() { byte[] bytecodes = new byte[]{ /* 0: */Bytecode.CONST, @@ -234,7 +233,38 @@ /* 11: */4, /* 12: */Bytecode.POP, /* 13: */Bytecode.RETURN}; - assertPartialEvalEqualsAndRunsCorrect(new Program("ifAndPopProgram", bytecodes, 0, 3)); + assertPartialEvalEqualsAndRunsCorrect(new Program("simpleLoopProgram", bytecodes, 0, 3)); + } + + @Test + public void nestedLoopsProgram() { + byte[] bytecodes = new byte[]{ + /* 0: */Bytecode.CONST, + /* 1: */42, + /* 2: */Bytecode.CONST, + /* 3: */-2, + /* 4: */Bytecode.CONST, + /* 5: */1, + /* 6: */Bytecode.ADD, + /* 7: */Bytecode.DUP, + /* 8: */Bytecode.CONST, + /* 9: */-2, + /* 10: */Bytecode.CONST, + /* 11: */1, + /* 12: */Bytecode.ADD, + /* 13: */Bytecode.DUP, + /* 14: */Bytecode.IFZERO, + /* 15: */18, + /* 16: */Bytecode.JMP, + /* 17: */10, + /* 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)); } @Test(timeout = 1000)
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/substitutions/TruffleGraphBuilderPlugins.java Sat Feb 28 09:32:36 2015 -0800 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/substitutions/TruffleGraphBuilderPlugins.java Sat Feb 28 12:50:25 2015 -0800 @@ -30,6 +30,7 @@ import com.oracle.graal.compiler.common.*; import com.oracle.graal.compiler.common.calc.*; import com.oracle.graal.compiler.common.type.*; +import com.oracle.graal.graph.*; import com.oracle.graal.java.*; import com.oracle.graal.java.GraphBuilderPlugin.InvocationPlugin; import com.oracle.graal.java.InvocationPlugins.Registration; @@ -198,7 +199,18 @@ if (curValue.isConstant()) { return true; } else { - throw builder.bailout("Partial evaluation did not reduce value to a constant, is a regular compiler node: " + curValue); + StringBuilder sb = new StringBuilder(); + sb.append(curValue); + if (curValue instanceof ValuePhiNode) { + ValuePhiNode valuePhi = (ValuePhiNode) curValue; + sb.append(" ("); + for (Node n : valuePhi.inputs()) { + sb.append(n); + sb.append("; "); + } + sb.append(")"); + } + throw builder.bailout("Partial evaluation did not reduce value to a constant, is a regular compiler node: " + sb.toString()); } } });