# HG changeset patch # User Christian Haeubl # Date 1330643912 28800 # Node ID c2ebd3d559f7e1e1cce6e93917cc4a14d57b5c55 # Parent 2792bcd9a0ce906a26b978271f6e06e3b7da5e76 fixed probabilities when polymorphic inlining is used diff -r 2792bcd9a0ce -r c2ebd3d559f7 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Thu Mar 01 15:58:46 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Thu Mar 01 15:18:32 2012 -0800 @@ -77,7 +77,7 @@ // absolute probability analysis public static boolean ProbabilityAnalysis = true; - public static int LoopFrequencyPropagationPolicy = -1; + public static int LoopFrequencyPropagationPolicy = -2; // profiling information public static int MatureExecutionsBranch = 1; diff -r 2792bcd9a0ce -r c2ebd3d559f7 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java Thu Mar 01 15:58:46 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java Thu Mar 01 15:18:32 2012 -0800 @@ -90,7 +90,6 @@ if (info.invoke.node().isAlive()) { try { info.inline(graph, runtime, this); - Debug.log("inlining %f: %s", info.weight, info); Debug.dump(graph, "after %s", info); // get the new nodes here, the canonicalizer phase will reset the mark newNodes = graph.getNewNodes(); @@ -119,6 +118,7 @@ } if (GraalOptions.Debug && graph.getNodeCount() >= GraalOptions.MaximumDesiredSize) { + Debug.log("inlining cut off by MaximumDesiredSize"); metricInliningStoppedByMaxDesiredSize.increment(); } } @@ -247,14 +247,17 @@ @Override public boolean isWorthInlining(StructuredGraph callerGraph, InlineInfo info) { if (GraalOptions.SmallCompiledCodeSize >= 0 && info.compiledCodeSize() > GraalOptions.SmallCompiledCodeSize) { + Debug.log("not inlining (CompiledCodeSize too large %d): %s", info.compiledCodeSize(), info); return false; } double penalty = Math.pow(GraalOptions.InliningSizePenaltyExp, callerGraph.getNodeCount() / (double) GraalOptions.MaximumDesiredSize) / GraalOptions.InliningSizePenaltyExp; if (info.weight > GraalOptions.MaximumInlineWeight / (1 + penalty * GraalOptions.InliningSizePenalty)) { - Debug.log("not inlining (cut off by weight): %e", info.weight); + Debug.log("not inlining (cut off by weight %e): ", info.weight); return false; } + + Debug.log("inlining (weight %f): %s", info.weight, info); return true; } } @@ -263,7 +266,13 @@ @Override public boolean isWorthInlining(StructuredGraph callerGraph, InlineInfo info) { double maxSize = Math.max(GraalOptions.MaximumTrivialSize, Math.pow(GraalOptions.NestedInliningSizeRatio, info.level) * GraalOptions.MaximumInlineSize); - return info.weight <= maxSize; + if (info.weight <= maxSize) { + Debug.log("inlining (size %f): %s", info.weight, info); + return true; + } else { + Debug.log("not inlining (too large %f): %s", info.weight, info); + return false; + } } } @@ -272,13 +281,21 @@ public boolean isWorthInlining(StructuredGraph callerGraph, InlineInfo info) { assert GraalOptions.ProbabilityAnalysis; if (GraalOptions.SmallCompiledCodeSize >= 0 && info.compiledCodeSize() > GraalOptions.SmallCompiledCodeSize) { + Debug.log("not inlining (CompiledCodeSize too large %d): %s", info.compiledCodeSize(), info); return false; } double inlineWeight = Math.min(GraalOptions.ProbabilityCapForInlining, info.invoke.probability()); double maxSize = Math.pow(GraalOptions.NestedInliningSizeRatio, info.level) * GraalOptions.MaximumInlineSize * inlineWeight; maxSize = Math.max(GraalOptions.MaximumTrivialSize, maxSize); - return info.weight <= maxSize; + + if (info.weight <= maxSize) { + Debug.log("inlining (size %f): %s", info.weight, info); + return true; + } else { + Debug.log("not inlining (too large %f): %s", info.weight, info); + return false; + } } } @@ -287,6 +304,7 @@ public boolean isWorthInlining(StructuredGraph callerGraph, InlineInfo info) { assert GraalOptions.ProbabilityAnalysis; if (GraalOptions.SmallCompiledCodeSize >= 0 && info.compiledCodeSize() > GraalOptions.SmallCompiledCodeSize) { + Debug.log("not inlining (CompiledCodeSize too large %d): %s", info.compiledCodeSize(), info); return false; } @@ -294,7 +312,14 @@ double maxSize = Math.pow(GraalOptions.NestedInliningSizeRatio, info.level) * GraalOptions.MaximumInlineSize; maxSize = maxSize + maxSize * inlineBoost; maxSize = Math.min(GraalOptions.MaximumGreedyInlineSize, Math.max(GraalOptions.MaximumTrivialSize, maxSize)); - return info.weight <= maxSize; + + if (info.weight <= maxSize) { + Debug.log("inlining (size %f): %s", info.weight, info); + return true; + } else { + Debug.log("not inlining (too large %f): %s", info.weight, info); + return false; + } } } @@ -303,13 +328,21 @@ public boolean isWorthInlining(StructuredGraph callerGraph, InlineInfo info) { assert GraalOptions.ProbabilityAnalysis; if (GraalOptions.SmallCompiledCodeSize >= 0 && info.compiledCodeSize() > GraalOptions.SmallCompiledCodeSize) { + Debug.log("not inlining (CompiledCodeSize too large %d): %s", info.compiledCodeSize(), info); return false; } double inlineRatio = Math.min(GraalOptions.ProbabilityCapForInlining, info.invoke.probability()); double maxSize = Math.pow(GraalOptions.NestedInliningSizeRatio, info.level) * GraalOptions.MaximumGreedyInlineSize * inlineRatio; maxSize = Math.max(maxSize, GraalOptions.MaximumTrivialSize); - return info.weight <= maxSize; + + if (info.weight <= maxSize) { + Debug.log("inlining (size %f): %s", info.weight, info); + return true; + } else { + Debug.log("not inlining (too large %f): %s", info.weight, info); + return false; + } } } diff -r 2792bcd9a0ce -r c2ebd3d559f7 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/InliningUtil.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/InliningUtil.java Thu Mar 01 15:58:46 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/InliningUtil.java Thu Mar 01 15:18:32 2012 -0800 @@ -214,19 +214,19 @@ public final List concretes; public final RiResolvedType[] types; public final int[] typesToConcretes; - public final double[] branchProbabilities; + public final double[] typeProbabilities; public final double notRecordedTypeProbability; public MultiTypeGuardInlineInfo(Invoke invoke, double weight, int level, List concretes, RiResolvedType[] types, - int[] typesToConcretes, double[] branchProbabilities, double notRecordedTypeProbability) { + int[] typesToConcretes, double[] typeProbabilities, double notRecordedTypeProbability) { super(invoke, weight, level); assert concretes.size() > 0 && concretes.size() <= types.length : "must have at least one method but no more than types methods"; - assert types.length == typesToConcretes.length && types.length == branchProbabilities.length : "array length must match"; + assert types.length == typesToConcretes.length && types.length == typeProbabilities.length : "array length must match"; this.concretes = concretes; this.types = types; this.typesToConcretes = typesToConcretes; - this.branchProbabilities = branchProbabilities; + this.typeProbabilities = typeProbabilities; this.notRecordedTypeProbability = notRecordedTypeProbability; } @@ -291,14 +291,22 @@ // create one separate block for each invoked method BeginNode[] calleeEntryNodes = new BeginNode[numberOfMethods]; for (int i = 0; i < numberOfMethods; i++) { - int predecessors = getPredecessorCount(i); - calleeEntryNodes[i] = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, predecessors, true); + int predecessors = 0; + double probability = 0; + for (int j = 0; j < typesToConcretes.length; j++) { + if (typesToConcretes[j] == i) { + predecessors++; + probability += typeProbabilities[j]; + } + } + + calleeEntryNodes[i] = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, predecessors, invoke.probability() * probability, true); } // create the successor for an unknown type FixedNode unknownTypeNode; if (shouldFallbackToInvoke()) { - unknownTypeNode = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, 1, false); + unknownTypeNode = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, 1, notRecordedTypeProbability, false); } else { unknownTypeNode = graph.add(new DeoptimizeNode(DeoptAction.InvalidateReprofile)); } @@ -382,17 +390,19 @@ private FixedNode createDispatchOnType(StructuredGraph graph, ReadHubNode objectClassNode, BeginNode[] calleeEntryNodes, FixedNode unknownTypeSux) { assert types.length > 1; - // TODO (ch) set probabilities for all created fixed nodes... int lastIndex = types.length - 1; - FixedNode nextNode = createTypeCheck(graph, objectClassNode, types[lastIndex], calleeEntryNodes[typesToConcretes[lastIndex]], unknownTypeSux, branchProbabilities[lastIndex]); + double[] branchProbabilities = convertTypeToBranchProbabilities(typeProbabilities, notRecordedTypeProbability); + double nodeProbability = typeProbabilities[lastIndex]; + IfNode nextNode = createTypeCheck(graph, objectClassNode, types[lastIndex], calleeEntryNodes[typesToConcretes[lastIndex]], unknownTypeSux, branchProbabilities[lastIndex], invoke.probability() * nodeProbability); for (int i = lastIndex - 1; i >= 0; i--) { - nextNode = createTypeCheck(graph, objectClassNode, types[i], calleeEntryNodes[typesToConcretes[i]], nextNode, branchProbabilities[i]); + nodeProbability += typeProbabilities[i]; + nextNode = createTypeCheck(graph, objectClassNode, types[i], calleeEntryNodes[typesToConcretes[i]], nextNode, branchProbabilities[i], invoke.probability() * nodeProbability); } return nextNode; } - private static FixedNode createTypeCheck(StructuredGraph graph, ReadHubNode objectClassNode, RiResolvedType type, BeginNode tsux, FixedNode nextNode, double tsuxProbability) { + private static IfNode createTypeCheck(StructuredGraph graph, ReadHubNode objectClassNode, RiResolvedType type, BeginNode tsux, FixedNode nextNode, double tsuxProbability, double probability) { IfNode result; IsTypeNode isTypeNode = graph.unique(new IsTypeNode(objectClassNode, type)); if (tsux instanceof MergeNode) { @@ -402,45 +412,46 @@ } else { result = graph.add(new IfNode(isTypeNode, tsux, nextNode, tsuxProbability)); } + result.setProbability(probability); return result; } - private int getPredecessorCount(int concreteMethodIndex) { - if (concretes.size() == types.length) { - return 1; - } else { - int count = 0; - for (int i = 0; i < typesToConcretes.length; i++) { - if (typesToConcretes[i] == concreteMethodIndex) { - count++; - } - } - return count; + private static double[] convertTypeToBranchProbabilities(double[] typeProbabilities, double notRecordedTypeProbability) { + double[] result = new double[typeProbabilities.length]; + double total = notRecordedTypeProbability; + for (int i = typeProbabilities.length - 1; i >= 0; i--) { + total += typeProbabilities[i]; + result[i] = typeProbabilities[i] / total; } + assert total > 0.99 && total < 1.01; + return result; } private static BeginNode createInvocationBlock(StructuredGraph graph, Invoke invoke, MergeNode returnMerge, PhiNode returnValuePhi, - MergeNode exceptionMerge, PhiNode exceptionObjectPhi, int predecessors, boolean useForInlining) { - Invoke duplicatedInvoke = duplicateInvokeForInlining(graph, invoke, exceptionMerge, exceptionObjectPhi, useForInlining); - // TODO (ch) set probabilities + MergeNode exceptionMerge, PhiNode exceptionObjectPhi, int predecessors, double probability, boolean useForInlining) { + Invoke duplicatedInvoke = duplicateInvokeForInlining(graph, invoke, exceptionMerge, exceptionObjectPhi, useForInlining, probability); BeginNode calleeEntryNode = graph.add(predecessors > 1 ? new MergeNode() : new BeginNode()); calleeEntryNode.setNext(duplicatedInvoke.node()); + calleeEntryNode.setProbability(probability); EndNode endNode = graph.add(new EndNode()); - // TODO (ch) set probability + endNode.setProbability(probability); + duplicatedInvoke.setNext(endNode); returnMerge.addForwardEnd(endNode); + if (returnValuePhi != null) { returnValuePhi.addInput(duplicatedInvoke.node()); } return calleeEntryNode; } - private static Invoke duplicateInvokeForInlining(StructuredGraph graph, Invoke invoke, MergeNode exceptionMerge, PhiNode exceptionObjectPhi, boolean useForInlining) { + private static Invoke duplicateInvokeForInlining(StructuredGraph graph, Invoke invoke, MergeNode exceptionMerge, PhiNode exceptionObjectPhi, boolean useForInlining, double probability) { Invoke result = (Invoke) invoke.node().copyWithInputs(); Node callTarget = result.callTarget().copyWithInputs(); result.node().replaceFirstInput(result.callTarget(), callTarget); result.setUseForInlining(useForInlining); + result.setProbability(probability); CiKind kind = invoke.node().kind(); if (!kind.isVoid()) { @@ -644,7 +655,6 @@ } if (canInline) { - convertTypeToBranchProbabilities(probabilities, notRecordedTypeProbability); return new MultiTypeGuardInlineInfo(invoke, totalWeight, level, concreteMethods, types, typesToConcretes, probabilities, notRecordedTypeProbability); } else { Debug.log("not inlining %s because it is a polymorphic method call and at least one invoked method cannot be inlined", methodName(targetMethod, invoke)); @@ -672,17 +682,6 @@ return checkCast; } - private static void convertTypeToBranchProbabilities(double[] typeProbabilities, double notRecordedTypeProbability) { - // avoid branches with 0.0/1.0 probability - double total = Math.max(1E-10, notRecordedTypeProbability); - - for (int i = typeProbabilities.length - 1; i >= 0; i--) { - total += typeProbabilities[i]; - typeProbabilities[i] = typeProbabilities[i] / total; - } - assert total > 0.99 && total < 1.01; - } - private static boolean checkInvokeConditions(Invoke invoke) { if (invoke.stateAfter() == null) { Debug.log("not inlining %s because the invoke has no after state", methodName(invoke.callTarget().targetMethod(), invoke)); diff -r 2792bcd9a0ce -r c2ebd3d559f7 graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/Invoke.java --- a/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/Invoke.java Thu Mar 01 15:58:46 2012 +0100 +++ b/graal/com.oracle.max.graal.nodes/src/com/oracle/max/graal/nodes/Invoke.java Thu Mar 01 15:18:32 2012 -0800 @@ -49,6 +49,8 @@ double probability(); + void setProbability(double value); + boolean useForInlining(); void setUseForInlining(boolean value); diff -r 2792bcd9a0ce -r c2ebd3d559f7 graal/com.oracle.max.graal.tests/src/com/oracle/max/graal/compiler/tests/CompiledMethodTest.java --- a/graal/com.oracle.max.graal.tests/src/com/oracle/max/graal/compiler/tests/CompiledMethodTest.java Thu Mar 01 15:58:46 2012 +0100 +++ b/graal/com.oracle.max.graal.tests/src/com/oracle/max/graal/compiler/tests/CompiledMethodTest.java Thu Mar 01 15:18:32 2012 -0800 @@ -30,7 +30,6 @@ import com.oracle.max.cri.ri.*; import com.oracle.max.cri.ri.RiCompiledMethod.MethodInvalidatedException; import com.oracle.max.graal.compiler.phases.*; -import com.oracle.max.graal.cri.*; import com.oracle.max.graal.graph.*; import com.oracle.max.graal.java.*; import com.oracle.max.graal.nodes.*;