# HG changeset patch # User Thomas Wuerthinger # Date 1367107414 -7200 # Node ID ee8cd087a731982be16ffce174457269c6c3110f # Parent 217e82c93bde5efd764eb00c4ed588cc4508292e Dispatch based on method instead of type if it seems more beneficial. diff -r 217e82c93bde -r ee8cd087a731 graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/ResolvedJavaMethod.java --- a/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/ResolvedJavaMethod.java Sun Apr 28 01:04:44 2013 +0200 +++ b/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/ResolvedJavaMethod.java Sun Apr 28 02:03:34 2013 +0200 @@ -24,7 +24,6 @@ import java.lang.annotation.*; import java.lang.reflect.*; -import java.lang.reflect.Method; import java.util.*; /** @@ -202,4 +201,11 @@ * @return The newly created and initialized object. */ Constant newInstance(Constant[] arguments); + + /** + * Gets the encoding of (that is, a constant representing the value of) this method. + * + * @return a constant representing a reference to this method + */ + Constant getEncoding(); } diff -r 217e82c93bde -r ee8cd087a731 graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotResolvedJavaMethod.java --- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotResolvedJavaMethod.java Sun Apr 28 01:04:44 2013 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotResolvedJavaMethod.java Sun Apr 28 02:03:34 2013 +0200 @@ -86,6 +86,11 @@ } @Override + public Constant getEncoding() { + return getMetaspaceMethodConstant(); + } + + @Override public int getModifiers() { HotSpotVMConfig config = graalRuntime().getConfig(); return unsafe.getInt(metaspaceMethod + config.methodAccessFlagsOffset) & Modifier.methodModifiers(); diff -r 217e82c93bde -r ee8cd087a731 graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotRuntime.java --- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotRuntime.java Sun Apr 28 01:04:44 2013 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotRuntime.java Sun Apr 28 02:03:34 2013 +0200 @@ -539,13 +539,12 @@ if (!hsMethod.getDeclaringClass().isInterface()) { int vtableEntryOffset = hsMethod.vtableEntryOffset(); if (vtableEntryOffset > 0) { - // We use LocationNode.ANY_LOCATION for the reads that access the vtable - // entry and the compiled code entry - // as HotSpot does not guarantee they are final values. assert vtableEntryOffset > 0; - LoadHubNode hub = graph.add(new LoadHubNode(receiver, wordKind)); - ReadNode metaspaceMethod = graph.add(new ReadNode(hub, ConstantLocationNode.create(LocationNode.ANY_LOCATION, wordKind, vtableEntryOffset, graph), - StampFactory.forKind(wordKind()))); + ReadNode hub = this.createReadHub(tool, graph, wordKind, receiver); + ReadNode metaspaceMethod = createReadVirtualMethod(graph, wordKind, hub, hsMethod); + // We use LocationNode.ANY_LOCATION for the reads that access the + // compiled code entry as HotSpot does not guarantee they are final + // values. ReadNode compiledEntry = graph.add(new ReadNode(metaspaceMethod, ConstantLocationNode.create(LocationNode.ANY_LOCATION, wordKind, config.methodCompiledEntryOffset, graph), StampFactory.forKind(wordKind()))); @@ -664,27 +663,16 @@ WriteNode write = graph.add(new WriteNode(object, store.value(), location, barrierType)); write.setStateAfter(store.stateAfter()); graph.replaceFixedWithFixed(store, write); - } else if (n instanceof LoadHubNode) { LoadHubNode loadHub = (LoadHubNode) n; assert loadHub.kind() == wordKind; - LocationNode location = ConstantLocationNode.create(LocationNode.FINAL_LOCATION, wordKind, config.hubOffset, graph); ValueNode object = loadHub.object(); - assert !object.isConstant() || object.asConstant().isNull(); - ReadNode hub = graph.add(new ReadNode(object, location, StampFactory.forKind(wordKind()))); - tool.createNullCheckGuard(hub.dependencies(), object); + ReadNode hub = createReadHub(tool, graph, wordKind, object); graph.replaceFixed(loadHub, hub); } else if (n instanceof LoadMethodNode) { LoadMethodNode loadMethodNode = (LoadMethodNode) n; - HotSpotResolvedJavaMethod hsMethod = (HotSpotResolvedJavaMethod) loadMethodNode.getMethod(); - assert !hsMethod.getDeclaringClass().isInterface(); - - int vtableEntryOffset = hsMethod.vtableEntryOffset(); - assert vtableEntryOffset > 0; - // We use LocationNode.ANY_LOCATION for the reads that access the vtable - // entry as HotSpot does not guarantee that this is a final value. - ReadNode metaspaceMethod = graph.add(new ReadNode(loadMethodNode.getHub(), ConstantLocationNode.create(LocationNode.ANY_LOCATION, wordKind, vtableEntryOffset, graph), - StampFactory.forKind(wordKind()))); + ResolvedJavaMethod method = loadMethodNode.getMethod(); + ReadNode metaspaceMethod = createReadVirtualMethod(graph, wordKind, loadMethodNode.getHub(), method); graph.replaceFixed(loadMethodNode, metaspaceMethod); } else if (n instanceof FixedGuardNode) { FixedGuardNode node = (FixedGuardNode) n; @@ -735,6 +723,26 @@ } } + private static ReadNode createReadVirtualMethod(StructuredGraph graph, Kind wordKind, ValueNode hub, ResolvedJavaMethod method) { + HotSpotResolvedJavaMethod hsMethod = (HotSpotResolvedJavaMethod) method; + assert !hsMethod.getDeclaringClass().isInterface(); + + int vtableEntryOffset = hsMethod.vtableEntryOffset(); + assert vtableEntryOffset > 0; + // We use LocationNode.ANY_LOCATION for the reads that access the vtable + // entry as HotSpot does not guarantee that this is a final value. + ReadNode metaspaceMethod = graph.add(new ReadNode(hub, ConstantLocationNode.create(LocationNode.ANY_LOCATION, wordKind, vtableEntryOffset, graph), StampFactory.forKind(wordKind()))); + return metaspaceMethod; + } + + private ReadNode createReadHub(LoweringTool tool, StructuredGraph graph, Kind wordKind, ValueNode object) { + LocationNode location = ConstantLocationNode.create(LocationNode.FINAL_LOCATION, wordKind, config.hubOffset, graph); + assert !object.isConstant() || object.asConstant().isNull(); + ReadNode hub = graph.add(new ReadNode(object, location, StampFactory.forKind(wordKind()))); + tool.createNullCheckGuard(hub.dependencies(), object); + return hub; + } + private static WriteBarrierType getFieldStoreBarrierType(StoreFieldNode storeField) { WriteBarrierType barrierType = WriteBarrierType.NONE; if (storeField.field().getKind() == Kind.Object && !storeField.value().objectStamp().alwaysNull()) { diff -r 217e82c93bde -r ee8cd087a731 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Sun Apr 28 01:04:44 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Sun Apr 28 02:03:34 2013 +0200 @@ -421,12 +421,15 @@ public final ArrayList ptypes; public final int[] typesToConcretes; public final double notRecordedTypeProbability; + private final ArrayList concretesProbabilities; - public MultiTypeGuardInlineInfo(Invoke invoke, ArrayList concretes, ArrayList ptypes, int[] typesToConcretes, double notRecordedTypeProbability) { + public MultiTypeGuardInlineInfo(Invoke invoke, ArrayList concretes, ArrayList concretesProbabilities, ArrayList ptypes, int[] typesToConcretes, + double notRecordedTypeProbability) { super(invoke); assert concretes.size() > 0 && concretes.size() <= ptypes.size() : "must have at least one method but no more than types methods"; assert ptypes.size() == typesToConcretes.length : "array lengths must match"; + this.concretesProbabilities = concretesProbabilities; this.concretes = concretes; this.ptypes = ptypes; this.typesToConcretes = typesToConcretes; @@ -449,7 +452,7 @@ // receiver null check must be the first node InliningUtil.receiverNullCheck(invoke); if (hasSingleMethod()) { - inlineSingleMethod(graph, callback, replacements, assumptions); + inlineSingleMethod(graph, callback, replacements, assumptions, runtime); } else { inlineMultipleMethods(graph, callback, replacements, assumptions, runtime); } @@ -518,7 +521,7 @@ assert invoke.asNode().isAlive(); // replace the invoke with a switch on the type of the actual receiver - createDispatchOnTypeBeforeInvoke(graph, successors, false); + boolean methodDispatch = createDispatchOnTypeBeforeInvoke(graph, successors, false, runtime); assert invoke.next() == continuation; invoke.setNext(null); @@ -533,9 +536,15 @@ BeginNode node = successors[i]; Invoke invokeForInlining = (Invoke) node.next(); - ResolvedJavaType commonType = getLeastCommonType(i); + ResolvedJavaType commonType; + if (methodDispatch) { + commonType = concretes.get(i).getDeclaringClass(); + } else { + commonType = getLeastCommonType(i); + } + ValueNode receiver = ((MethodCallTargetNode) invokeForInlining.callTarget()).receiver(); - boolean exact = getTypeCount(i) == 1; + boolean exact = (getTypeCount(i) == 1 && !methodDispatch); PiNode anchoredReceiver = createAnchoredReceiver(graph, node, commonType, receiver, exact); invokeForInlining.callTarget().replaceFirstInput(receiver, anchoredReceiver); @@ -604,14 +613,14 @@ return result; } - private void inlineSingleMethod(StructuredGraph graph, InliningCallback callback, Replacements replacements, Assumptions assumptions) { + private void inlineSingleMethod(StructuredGraph graph, InliningCallback callback, Replacements replacements, Assumptions assumptions, MetaAccessProvider runtime) { assert concretes.size() == 1 && ptypes.size() > 1 && !shouldFallbackToInvoke() && notRecordedTypeProbability == 0; BeginNode calleeEntryNode = graph.add(new BeginNode()); BeginNode unknownTypeSux = createUnknownTypeSuccessor(graph); BeginNode[] successors = new BeginNode[]{calleeEntryNode, unknownTypeSux}; - createDispatchOnTypeBeforeInvoke(graph, successors, false); + createDispatchOnTypeBeforeInvoke(graph, successors, false, runtime); calleeEntryNode.setNext(invoke.asNode()); @@ -619,13 +628,50 @@ inline(invoke, concrete, callback, replacements, assumptions, false); } - private void createDispatchOnTypeBeforeInvoke(StructuredGraph graph, BeginNode[] successors, boolean invokeIsOnlySuccessor) { + private boolean createDispatchOnTypeBeforeInvoke(StructuredGraph graph, BeginNode[] successors, boolean invokeIsOnlySuccessor, MetaAccessProvider runtime) { assert ptypes.size() >= 1; Kind hubKind = ((MethodCallTargetNode) invoke.callTarget()).targetMethod().getDeclaringClass().getEncoding(Representation.ObjectHub).getKind(); LoadHubNode hub = graph.add(new LoadHubNode(((MethodCallTargetNode) invoke.callTarget()).receiver(), hubKind)); graph.addBeforeFixed(invoke.asNode(), hub); + if (!invokeIsOnlySuccessor && chooseMethodDispatch()) { + assert successors.length == concretes.size() + 1; + assert concretes.size() > 0; + Debug.log("Method check cascade with %d methods", concretes.size()); + + LoadMethodNode[] methods = new LoadMethodNode[concretes.size()]; + ValueNode[] constantMethods = new ValueNode[concretes.size()]; + double[] probability = new double[concretes.size()]; + for (int i = 0; i < concretes.size(); ++i) { + ResolvedJavaMethod firstMethod = concretes.get(i); + Constant firstMethodConstant = firstMethod.getEncoding(); + + ValueNode firstMethodConstantNode = ConstantNode.forConstant(firstMethodConstant, runtime, graph); + constantMethods[i] = firstMethodConstantNode; + probability[i] = concretesProbabilities.get(i); + if (i > 0) { + probability[i] /= (1.0 - probability[i - 1]); + } + } + + FixedNode lastSucc = successors[concretes.size()]; + for (int i = concretes.size() - 1; i >= 0; --i) { + LoadMethodNode method = graph.add(new LoadMethodNode(concretes.get(i), hub, constantMethods[i].kind())); + methods[i] = method; + CompareNode methodCheck = CompareNode.createCompareNode(Condition.EQ, methods[i], constantMethods[i]); + IfNode ifNode = graph.add(new IfNode(methodCheck, successors[i], lastSucc, probability[i])); + method.setNext(ifNode); + lastSucc = method; + } + + FixedWithNextNode pred = (FixedWithNextNode) invoke.asNode().predecessor(); + pred.setNext(lastSucc); + return true; + } else { + Debug.log("Type switch with %d types", concretes.size()); + } + ResolvedJavaType[] keys = new ResolvedJavaType[ptypes.size()]; double[] keyProbabilities = new double[ptypes.size() + 1]; int[] keySuccessors = new int[ptypes.size() + 1]; @@ -641,6 +687,45 @@ TypeSwitchNode typeSwitch = graph.add(new TypeSwitchNode(hub, successors, keys, keyProbabilities, keySuccessors)); FixedWithNextNode pred = (FixedWithNextNode) invoke.asNode().predecessor(); pred.setNext(typeSwitch); + return false; + } + + private boolean chooseMethodDispatch() { + if (concretes.size() == 1 && this.notRecordedTypeProbability > 0) { + // Always chose method dispatch if there is a single concrete method and the call + // site is megamorphic. + return true; + } + + if (concretes.size() == ptypes.size()) { + // Always prefer types over methods if the number of types is smaller than the + // number of methods. + return false; + } + + return chooseMethodDispatchCostBased(); + } + + private boolean chooseMethodDispatchCostBased() { + double remainder = 1.0 - this.notRecordedTypeProbability; + double costEstimateMethodDispatch = remainder; + for (int i = 0; i < concretes.size(); ++i) { + if (i != 0) { + costEstimateMethodDispatch += remainder; + } + remainder -= concretesProbabilities.get(i); + } + + double costEstimateTypeDispatch = 0.0; + remainder = 1.0; + for (int i = 0; i < ptypes.size(); ++i) { + if (i != 0) { + costEstimateTypeDispatch += remainder; + } + remainder -= ptypes.get(i).getProbability(); + } + costEstimateTypeDispatch += notRecordedTypeProbability; + return costEstimateMethodDispatch < costEstimateTypeDispatch; } private static BeginNode createInvocationBlock(StructuredGraph graph, Invoke invoke, MergeNode returnMerge, PhiNode returnValuePhi, MergeNode exceptionMerge, PhiNode exceptionObjectPhi, @@ -697,17 +782,17 @@ @Override public void tryToDevirtualizeInvoke(StructuredGraph graph, MetaAccessProvider runtime, Assumptions assumptions) { if (hasSingleMethod()) { - tryToDevirtualizeSingleMethod(graph); + tryToDevirtualizeSingleMethod(graph, runtime); } else { - tryToDevirtualizeMultipleMethods(graph); + tryToDevirtualizeMultipleMethods(graph, runtime); } } - private void tryToDevirtualizeSingleMethod(StructuredGraph graph) { - devirtualizeWithTypeSwitch(graph, InvokeKind.Special, concretes.get(0)); + private void tryToDevirtualizeSingleMethod(StructuredGraph graph, MetaAccessProvider runtime) { + devirtualizeWithTypeSwitch(graph, InvokeKind.Special, concretes.get(0), runtime); } - private void tryToDevirtualizeMultipleMethods(StructuredGraph graph) { + private void tryToDevirtualizeMultipleMethods(StructuredGraph graph, MetaAccessProvider runtime) { MethodCallTargetNode methodCallTarget = (MethodCallTargetNode) invoke.callTarget(); if (methodCallTarget.invokeKind() == InvokeKind.Interface) { ResolvedJavaMethod targetMethod = methodCallTarget.targetMethod(); @@ -718,19 +803,19 @@ if (!leastCommonType.isInterface() && targetMethod.getDeclaringClass().isAssignableFrom(leastCommonType)) { ResolvedJavaMethod baseClassTargetMethod = leastCommonType.resolveMethod(targetMethod); if (baseClassTargetMethod != null) { - devirtualizeWithTypeSwitch(graph, InvokeKind.Virtual, leastCommonType.resolveMethod(targetMethod)); + devirtualizeWithTypeSwitch(graph, InvokeKind.Virtual, leastCommonType.resolveMethod(targetMethod), runtime); } } } } - private void devirtualizeWithTypeSwitch(StructuredGraph graph, InvokeKind kind, ResolvedJavaMethod target) { + private void devirtualizeWithTypeSwitch(StructuredGraph graph, InvokeKind kind, ResolvedJavaMethod target, MetaAccessProvider runtime) { InliningUtil.receiverNullCheck(invoke); BeginNode invocationEntry = graph.add(new BeginNode()); BeginNode unknownTypeSux = createUnknownTypeSuccessor(graph); BeginNode[] successors = new BeginNode[]{invocationEntry, unknownTypeSux}; - createDispatchOnTypeBeforeInvoke(graph, successors, true); + createDispatchOnTypeBeforeInvoke(graph, successors, true, runtime); invocationEntry.setNext(invoke.asNode()); ValueNode receiver = ((MethodCallTargetNode) invoke.callTarget()).receiver(); @@ -949,9 +1034,11 @@ if (notRecordedTypeProbability > 0) { // Clean out uncommon methods. ArrayList newConcreteMethods = new ArrayList<>(); + ArrayList newConcreteMethodsProbabilities = new ArrayList<>(); for (int i = 0; i < concreteMethods.size(); ++i) { if (concreteMethodsProbabilities.get(i) >= GraalOptions.MegamorphicInliningMinMethodProbability) { newConcreteMethods.add(concreteMethods.get(i)); + newConcreteMethodsProbabilities.add(concreteMethodsProbabilities.get(i)); } else { concreteMethods.set(i, null); } @@ -986,6 +1073,7 @@ usedTypes = newTypes; typesToConcretes = newTypesToConcretesArray; concreteMethods = newConcreteMethods; + concreteMethodsProbabilities = newConcreteMethodsProbabilities; } } @@ -994,7 +1082,7 @@ return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "it is a polymorphic method call and at least one invoked method cannot be inlined"); } } - return new MultiTypeGuardInlineInfo(invoke, concreteMethods, usedTypes, typesToConcretes, notRecordedTypeProbability); + return new MultiTypeGuardInlineInfo(invoke, concreteMethods, concreteMethodsProbabilities, usedTypes, typesToConcretes, notRecordedTypeProbability); } } diff -r 217e82c93bde -r ee8cd087a731 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java --- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Sun Apr 28 01:04:44 2013 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Sun Apr 28 02:03:34 2013 +0200 @@ -45,8 +45,8 @@ static boolean InlineMonomorphicCalls = true; static boolean InlinePolymorphicCalls = true; static boolean InlineMegamorphicCalls = true; - public static double MegamorphicInliningMinTypeProbability = 0.1; - public static double MegamorphicInliningMinMethodProbability = 0.25; + public static double MegamorphicInliningMinTypeProbability = 0.05; + public static double MegamorphicInliningMinMethodProbability = 0.20; public static int MaximumDesiredSize = 5000; public static int MaximumRecursiveInlining = 1; public static float BoostInliningForEscapeAnalysis = 2f;