# HG changeset patch # User Christian Haeubl # Date 1370609297 -7200 # Node ID 5a4fbe932ab33281c1ed98d9014aeefba61f038d # Parent dacc978797514bd9e657f31c578bda75c02bc8f2 Assume that those path which end in a DeoptimizeNode are taken less frequently. diff -r dacc97879751 -r 5a4fbe932ab3 graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/DeoptimizationAction.java --- a/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/DeoptimizationAction.java Fri Jun 07 14:38:50 2013 +0200 +++ b/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/DeoptimizationAction.java Fri Jun 07 14:48:17 2013 +0200 @@ -32,28 +32,39 @@ * it's highly likely nothing will change the likelihood of the deoptimization happening again. * For example, a compiled array allocation where the size is negative. */ - None, + None(false), /** * Do not invalidate the machine code, but schedule a recompilation if this deoptimization is * triggered too often. */ - RecompileIfTooManyDeopts, + RecompileIfTooManyDeopts(true), /** * Invalidate the machine code and reset the profiling information. */ - InvalidateReprofile, + InvalidateReprofile(true), /** * Invalidate the machine code and immediately schedule a recompilation. This is typically used * when deoptimizing to resolve an unresolved symbol in which case extra profiling is not * required to determine that the deoptimization will not re-occur. */ - InvalidateRecompile, + InvalidateRecompile(true), /** * Invalidate the machine code and stop compiling the outermost method of this compilation. */ - InvalidateStopCompiling; + InvalidateStopCompiling(true); + + private final boolean invalidatesCompilation; + + private DeoptimizationAction(boolean invalidatesCompilation) { + this.invalidatesCompilation = invalidatesCompilation; + } + + public boolean doesInvalidateCompilation() { + return invalidatesCompilation; + } + } diff -r dacc97879751 -r 5a4fbe932ab3 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 Fri Jun 07 14:38:50 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java Fri Jun 07 14:48:17 2013 +0200 @@ -73,6 +73,32 @@ return sum; } + public void setProbability(Node successor, double value) { + double changeInProbability = 0; + int nonZeroProbabilityCases = 0; + for (int i = 0; i < keySuccessors.length; i++) { + if (successors.get(keySuccessors[i]) == successor) { + changeInProbability += keyProbabilities[i] - value; + keyProbabilities[i] = value; + } else if (keyProbabilities[i] > 0) { + nonZeroProbabilityCases++; + } + } + + if (nonZeroProbabilityCases > 0) { + double changePerEntry = changeInProbability / nonZeroProbabilityCases; + if (changePerEntry != 0) { + for (int i = 0; i < keyProbabilities.length; i++) { + if (keyProbabilities[i] > 0) { + keyProbabilities[i] = keyProbabilities[i] + changePerEntry; + } + } + } + } + + assertProbabilities(); + } + public ValueNode value() { return value; } diff -r dacc97879751 -r 5a4fbe932ab3 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Fri Jun 07 14:38:50 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Fri Jun 07 14:48:17 2013 +0200 @@ -437,15 +437,16 @@ } double inliningBonus = getInliningBonus(info); - + int nodes = determineNodeCount(info); int lowLevelGraphSize = previousLowLevelGraphSize(info); + if (SmallCompiledLowLevelGraphSize.getValue() > 0 && lowLevelGraphSize > SmallCompiledLowLevelGraphSize.getValue() * inliningBonus) { - return InliningUtil.logNotInlinedMethod(info, inliningDepth, "too large previous low-level graph: %d", lowLevelGraphSize); + return InliningUtil.logNotInlinedMethod(info, inliningDepth, "too large previous low-level graph (low-level-nodes: %d, relevance=%f, probability=%f, bonus=%f, nodes=%d)", + lowLevelGraphSize, relevance, probability, inliningBonus, nodes); } - int nodes = determineNodeCount(info); if (nodes < TrivialInliningSize.getValue() * inliningBonus) { - return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "trivial (nodes=%d)", nodes); + return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "trivial (relevance=%f, probability=%f, bonus=%f, nodes=%d)", relevance, probability, inliningBonus, nodes); } /* @@ -456,16 +457,17 @@ */ double invokes = determineInvokeProbability(info); if (LimitInlinedInvokes.getValue() > 0 && fullyProcessed && invokes > LimitInlinedInvokes.getValue() * inliningBonus) { - return InliningUtil.logNotInlinedMethod(info, inliningDepth, "callee invoke probability is too high (%f)", invokes); + return InliningUtil.logNotInlinedMethod(info, inliningDepth, "callee invoke probability is too high (invokeP=%f, relevance=%f, probability=%f, bonus=%f, nodes=%d)", invokes, + relevance, probability, inliningBonus, nodes); } double maximumNodes = computeMaximumSize(relevance, (int) (MaximumInliningSize.getValue() * inliningBonus)); if (nodes <= maximumNodes) { - return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "relevance-based (relevance=%f, probability=%f, bonus=%f, nodes=%d <= max=%f)", relevance, probability, + return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "relevance-based (relevance=%f, probability=%f, bonus=%f, nodes=%d <= %f)", relevance, probability, inliningBonus, nodes, maximumNodes); } - return InliningUtil.logNotInlinedMethod(info, inliningDepth, "relevance-based (relevance=%f, probability=%f, bonus=%f, nodes=%d > max=%f)", relevance, probability, inliningBonus, nodes, + return InliningUtil.logNotInlinedMethod(info, inliningDepth, "relevance-based (relevance=%f, probability=%f, bonus=%f, nodes=%d > %f)", relevance, probability, inliningBonus, nodes, maximumNodes); } } diff -r dacc97879751 -r 5a4fbe932ab3 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 Fri Jun 07 14:38:50 2013 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java Fri Jun 07 14:48:17 2013 +0200 @@ -26,6 +26,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.util.*; /** @@ -63,12 +64,103 @@ } 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 (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(Node node, NodeBitMap visitedNodes) { + if (node instanceof IfNode) { + IfNode ifNode = (IfNode) node; + assert visitedNodes.isMarked(ifNode.falseSuccessor()) ^ visitedNodes.isMarked(ifNode.trueSuccessor()); + + if (visitedNodes.isMarked(ifNode.trueSuccessor())) { + if (ifNode.probability(ifNode.trueSuccessor()) > 0) { + ifNode.setTrueSuccessorProbability(0); + } + } else { + if (ifNode.probability(ifNode.trueSuccessor()) < 1) { + ifNode.setTrueSuccessorProbability(1); + } + } + } else if (node instanceof SwitchNode) { + SwitchNode switchNode = (SwitchNode) node; + for (Node sux : switchNode.successors()) { + if (visitedNodes.isMarked(sux)) { + switchNode.setProbability(sux, 0); + } + } + } else { + assert !(node instanceof ControlSplitNode); + } + } + + private static boolean allSuxVisited(FixedNode fixedPred, NodeBitMap visitedNodes) { + for (Node sux : fixedPred.successors()) { + 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);