# HG changeset patch # User Christian Haeubl # Date 1370949025 -7200 # Node ID 053b837d0d7dec21f0ccc40701dfbc0c65b9e0f0 # Parent b2aea23ee2b109bb2c7953981dc15ee03b152629 Readded the pass that fixes DeoptimizeNode probabilities. diff -r b2aea23ee2b1 -r 053b837d0d7d graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotProfilingInfo.java --- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotProfilingInfo.java Mon Jun 10 15:17:10 2013 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotProfilingInfo.java Tue Jun 11 13:10:25 2013 +0200 @@ -22,12 +22,9 @@ */ package com.oracle.graal.hotspot.meta; -import static com.oracle.graal.hotspot.HotSpotGraalRuntime.*; - import com.oracle.graal.api.meta.*; import com.oracle.graal.debug.*; import com.oracle.graal.hotspot.*; -import com.oracle.graal.phases.*; public final class HotSpotProfilingInfo extends CompilerObject implements ProfilingInfo { diff -r b2aea23ee2b1 -r 053b837d0d7d graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java Mon Jun 10 15:17:10 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java Tue Jun 11 13:10:25 2013 +0200 @@ -35,4 +35,6 @@ } public abstract double probability(AbstractBeginNode successor); + + public abstract void setProbability(AbstractBeginNode successor, double value); } diff -r b2aea23ee2b1 -r 053b837d0d7d graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Mon Jun 10 15:17:10 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Tue Jun 11 13:10:25 2013 +0200 @@ -132,6 +132,12 @@ } @Override + public void setProbability(AbstractBeginNode successor, double value) { + assert successor == trueSuccessor || successor == falseSuccessor; + setTrueSuccessorProbability(successor == trueSuccessor ? value : 1 - value); + } + + @Override public void generate(LIRGeneratorTool gen) { gen.emitIf(this); } diff -r b2aea23ee2b1 -r 053b837d0d7d graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Mon Jun 10 15:17:10 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Tue Jun 11 13:10:25 2013 +0200 @@ -36,6 +36,8 @@ @NodeInfo(nameTemplate = "Invoke!#{p#targetMethod/s}") public class InvokeWithExceptionNode extends ControlSplitNode implements Node.IterableNodeType, Invoke, MemoryCheckpoint, LIRLowerable { + private static final double EXCEPTION_PROBA = 1e-5; + @Successor private AbstractBeginNode next; @Successor private DispatchBeginNode exceptionEdge; @Input private CallTargetNode callTarget; @@ -45,6 +47,7 @@ private final int bci; private boolean polymorphic; private boolean useForInlining; + private double exceptionProbability; public InvokeWithExceptionNode(CallTargetNode callTarget, DispatchBeginNode exceptionEdge, int bci) { super(callTarget.returnStamp()); @@ -53,6 +56,7 @@ this.callTarget = callTarget; this.polymorphic = false; this.useForInlining = true; + this.exceptionProbability = EXCEPTION_PROBA; } public DispatchBeginNode exceptionEdge() { @@ -205,11 +209,15 @@ } } - private static final double EXCEPTION_PROBA = 1e-5; + @Override + public double probability(AbstractBeginNode successor) { + return successor == next ? 1 - exceptionProbability : exceptionProbability; + } @Override - public double probability(AbstractBeginNode successor) { - return successor == next ? 1 - EXCEPTION_PROBA : EXCEPTION_PROBA; + public void setProbability(AbstractBeginNode successor, double value) { + assert successor == next || successor == exceptionEdge; + this.exceptionProbability = successor == next ? 1 - value : value; } @Override diff -r b2aea23ee2b1 -r 053b837d0d7d graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java Mon Jun 10 15:17:10 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java Tue Jun 11 13:10:25 2013 +0200 @@ -76,7 +76,8 @@ return sum; } - public void setProbability(Node successor, double value) { + @Override + public void setProbability(AbstractBeginNode successor, double value) { double changeInProbability = 0; int nonZeroProbabilityCases = 0; for (int i = 0; i < keySuccessors.length; i++) { diff -r b2aea23ee2b1 -r 053b837d0d7d graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java --- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java Mon Jun 10 15:17:10 2013 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java Tue Jun 11 13:10:25 2013 +0200 @@ -24,6 +24,7 @@ import java.util.*; +import com.oracle.graal.debug.internal.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.util.*; @@ -63,12 +64,98 @@ } public NodesToDoubles apply() { + adjustControlSplitProbabilities(); new PropagateProbability(graph.start()).apply(); computeLoopFactors(); new PropagateLoopFrequency(graph.start()).apply(); + assert verifyProbabilities(); return nodeProbabilities; } + /** + * Assume that paths with a DeoptimizeNode at their end are taken infrequently. + */ + private void adjustControlSplitProbabilities() { + HashSet result = new HashSet<>(); + NodeBitMap visitedNodes = new NodeBitMap(graph); + for (DeoptimizeNode n : graph.getNodes(DeoptimizeNode.class)) { + if (n.action().doesInvalidateCompilation()) { + findParentControlSplitNodes(result, n, visitedNodes); + } + } + + for (ControlSplitNode n : result) { + if (!allSuxVisited(n, visitedNodes)) { + modifyProbabilities(n, visitedNodes); + } + } + } + + private static void findParentControlSplitNodes(HashSet result, DeoptimizeNode n, NodeBitMap visitedNodes) { + ArrayDeque nodes = new ArrayDeque<>(); + nodes.push(n); + + Node currentNode; + do { + currentNode = nodes.pop(); + visitedNodes.mark(currentNode); + + for (Node pred : currentNode.cfgPredecessors()) { + FixedNode fixedPred = (FixedNode) pred; + if (visitedNodes.isMarked(fixedPred) && allPredsVisited(fixedPred, visitedNodes)) { + DebugScope.dump(n.graph(), "ComputeProbabilityClosure"); + GraalInternalError.shouldNotReachHere(String.format("Endless loop because %s was already visited", fixedPred)); + } else if (allSuxVisited(fixedPred, visitedNodes)) { + nodes.push(fixedPred); + } else { + assert fixedPred instanceof ControlSplitNode : "only control splits can have more than one sux"; + result.add((ControlSplitNode) fixedPred); + } + } + } while (!nodes.isEmpty()); + } + + private static void modifyProbabilities(ControlSplitNode controlSplit, NodeBitMap visitedNodes) { + assert !allSuxVisited(controlSplit, visitedNodes); + for (Node sux : controlSplit.successors()) { + if (visitedNodes.isMarked(sux)) { + controlSplit.setProbability((AbstractBeginNode) sux, 0); + } + } + } + + private static boolean allSuxVisited(FixedNode node, NodeBitMap visitedNodes) { + return allVisited(node.successors(), visitedNodes); + } + + private static boolean allPredsVisited(FixedNode node, NodeBitMap visitedNodes) { + return allVisited(node.cfgPredecessors(), visitedNodes); + } + + private static boolean allVisited(Iterable nodes, NodeBitMap visitedNodes) { + for (Node sux : nodes) { + if (!visitedNodes.contains(sux)) { + return false; + } + } + return true; + } + + private boolean verifyProbabilities() { + if (doesNotAlwaysDeopt(graph)) { + for (DeoptimizeNode n : graph.getNodes(DeoptimizeNode.class)) { + if (n.action().doesInvalidateCompilation() && nodeProbabilities.get(n) > 0.01) { + throw new AssertionError(String.format("%s with reason %s and probability %f in graph %s", n, n.reason(), nodeProbabilities.get(n), graph)); + } + } + } + return true; + } + + private static boolean doesNotAlwaysDeopt(StructuredGraph graph) { + return graph.getNodes(ReturnNode.class).iterator().hasNext(); + } + private void computeLoopFactors() { for (LoopInfo info : loopInfos) { double frequency = info.loopFrequency(nodeProbabilities);