| /* |
| * Copyright (c) 2011, 2016, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| |
| package org.graalvm.compiler.phases.common.inlining.walker; |
| |
| import static org.graalvm.compiler.core.common.GraalOptions.Intrinsify; |
| import static org.graalvm.compiler.core.common.GraalOptions.MaximumRecursiveInlining; |
| import static org.graalvm.compiler.core.common.GraalOptions.MegamorphicInliningMinMethodProbability; |
| |
| import java.util.ArrayDeque; |
| import java.util.ArrayList; |
| import java.util.BitSet; |
| import java.util.Collection; |
| import java.util.Iterator; |
| import java.util.LinkedList; |
| import java.util.List; |
| |
| import jdk.internal.vm.compiler.collections.EconomicSet; |
| import jdk.internal.vm.compiler.collections.Equivalence; |
| import org.graalvm.compiler.core.common.type.ObjectStamp; |
| import org.graalvm.compiler.debug.CounterKey; |
| import org.graalvm.compiler.debug.DebugContext; |
| import org.graalvm.compiler.debug.GraalError; |
| import org.graalvm.compiler.graph.Graph; |
| import org.graalvm.compiler.graph.Node; |
| import org.graalvm.compiler.nodes.CallTargetNode; |
| import org.graalvm.compiler.nodes.CallTargetNode.InvokeKind; |
| import org.graalvm.compiler.nodes.Invoke; |
| import org.graalvm.compiler.nodes.NodeView; |
| import org.graalvm.compiler.nodes.ParameterNode; |
| import org.graalvm.compiler.nodes.StructuredGraph; |
| import org.graalvm.compiler.nodes.ValueNode; |
| import org.graalvm.compiler.nodes.java.AbstractNewObjectNode; |
| import org.graalvm.compiler.nodes.java.MethodCallTargetNode; |
| import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode; |
| import org.graalvm.compiler.nodes.virtual.VirtualObjectNode; |
| import org.graalvm.compiler.options.OptionValues; |
| import org.graalvm.compiler.phases.OptimisticOptimizations; |
| import org.graalvm.compiler.phases.common.CanonicalizerPhase; |
| import org.graalvm.compiler.phases.common.inlining.InliningUtil; |
| import org.graalvm.compiler.phases.common.inlining.info.AssumptionInlineInfo; |
| import org.graalvm.compiler.phases.common.inlining.info.ExactInlineInfo; |
| import org.graalvm.compiler.phases.common.inlining.info.InlineInfo; |
| import org.graalvm.compiler.phases.common.inlining.info.MultiTypeGuardInlineInfo; |
| import org.graalvm.compiler.phases.common.inlining.info.TypeGuardInlineInfo; |
| import org.graalvm.compiler.phases.common.inlining.info.elem.Inlineable; |
| import org.graalvm.compiler.phases.common.inlining.info.elem.InlineableGraph; |
| import org.graalvm.compiler.phases.common.inlining.policy.InliningPolicy; |
| import org.graalvm.compiler.phases.tiers.HighTierContext; |
| import org.graalvm.compiler.phases.util.Providers; |
| |
| import jdk.vm.ci.code.BailoutException; |
| import jdk.vm.ci.meta.Assumptions.AssumptionResult; |
| import jdk.vm.ci.meta.JavaTypeProfile; |
| import jdk.vm.ci.meta.ResolvedJavaMethod; |
| import jdk.vm.ci.meta.ResolvedJavaType; |
| |
| /** |
| * <p> |
| * The space of inlining decisions is explored depth-first with the help of a stack realized by |
| * {@link InliningData}. At any point in time, the topmost element of that stack consists of: |
| * <ul> |
| * <li>the callsite under consideration is tracked as a {@link MethodInvocation}.</li> |
| * <li>one or more {@link CallsiteHolder}s, all of them associated to the callsite above. Why more |
| * than one? Depending on the type-profile for the receiver more than one concrete method may be |
| * feasible target.</li> |
| * </ul> |
| * </p> |
| * |
| * <p> |
| * The bottom element in the stack consists of: |
| * <ul> |
| * <li>a single {@link MethodInvocation} (the |
| * {@link org.graalvm.compiler.phases.common.inlining.walker.MethodInvocation#isRoot root} one, ie |
| * the unknown caller of the root graph)</li> |
| * <li>a single {@link CallsiteHolder} (the root one, for the method on which inlining was called) |
| * </li> |
| * </ul> |
| * </p> |
| * |
| * @see #moveForward() |
| */ |
| public class InliningData { |
| |
| // Counters |
| private static final CounterKey counterInliningPerformed = DebugContext.counter("InliningPerformed"); |
| private static final CounterKey counterInliningRuns = DebugContext.counter("InliningRuns"); |
| private static final CounterKey counterInliningConsidered = DebugContext.counter("InliningConsidered"); |
| |
| /** |
| * Call hierarchy from outer most call (i.e., compilation unit) to inner most callee. |
| */ |
| private final ArrayDeque<CallsiteHolder> graphQueue = new ArrayDeque<>(); |
| private final ArrayDeque<MethodInvocation> invocationQueue = new ArrayDeque<>(); |
| |
| private final HighTierContext context; |
| private final int maxMethodPerInlining; |
| private final CanonicalizerPhase canonicalizer; |
| private final InliningPolicy inliningPolicy; |
| private final StructuredGraph rootGraph; |
| private final DebugContext debug; |
| |
| private int maxGraphs; |
| |
| public InliningData(StructuredGraph rootGraph, HighTierContext context, int maxMethodPerInlining, CanonicalizerPhase canonicalizer, InliningPolicy inliningPolicy, LinkedList<Invoke> rootInvokes) { |
| assert rootGraph != null; |
| this.context = context; |
| this.maxMethodPerInlining = maxMethodPerInlining; |
| this.canonicalizer = canonicalizer; |
| this.inliningPolicy = inliningPolicy; |
| this.maxGraphs = 1; |
| this.rootGraph = rootGraph; |
| this.debug = rootGraph.getDebug(); |
| |
| invocationQueue.push(new MethodInvocation(null, 1.0, 1.0, null)); |
| graphQueue.push(new CallsiteHolderExplorable(rootGraph, 1.0, 1.0, null, rootInvokes)); |
| } |
| |
| public static boolean isFreshInstantiation(ValueNode arg) { |
| return (arg instanceof AbstractNewObjectNode) || (arg instanceof AllocatedObjectNode) || (arg instanceof VirtualObjectNode); |
| } |
| |
| private String checkTargetConditionsHelper(ResolvedJavaMethod method, int invokeBci) { |
| OptionValues options = rootGraph.getOptions(); |
| if (method == null) { |
| return "the method is not resolved"; |
| } else if (method.isNative() && (!Intrinsify.getValue(options) || !InliningUtil.canIntrinsify(context.getReplacements(), method, invokeBci))) { |
| return "it is a non-intrinsic native method"; |
| } else if (method.isAbstract()) { |
| return "it is an abstract method"; |
| } else if (!method.getDeclaringClass().isInitialized()) { |
| return "the method's class is not initialized"; |
| } else if (!method.canBeInlined()) { |
| return "it is marked non-inlinable"; |
| } else if (countRecursiveInlining(method) > MaximumRecursiveInlining.getValue(options)) { |
| return "it exceeds the maximum recursive inlining depth"; |
| } else { |
| if (new OptimisticOptimizations(rootGraph.getProfilingInfo(method), options).lessOptimisticThan(context.getOptimisticOptimizations())) { |
| return "the callee uses less optimistic optimizations than caller"; |
| } else { |
| return null; |
| } |
| } |
| } |
| |
| private boolean checkTargetConditions(Invoke invoke, ResolvedJavaMethod method) { |
| final String failureMessage = checkTargetConditionsHelper(method, invoke.bci()); |
| if (failureMessage == null) { |
| return true; |
| } else { |
| InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), method, failureMessage); |
| invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, failureMessage); |
| return false; |
| } |
| } |
| |
| /** |
| * Determines if inlining is possible at the given invoke node. |
| * |
| * @param invoke the invoke that should be inlined |
| * @return an instance of InlineInfo, or null if no inlining is possible at the given invoke |
| */ |
| private InlineInfo getInlineInfo(Invoke invoke) { |
| final String failureMessage = InliningUtil.checkInvokeConditions(invoke); |
| if (failureMessage != null) { |
| InliningUtil.logNotInlinedMethod(invoke, failureMessage); |
| return null; |
| } |
| MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget(); |
| ResolvedJavaMethod targetMethod = callTarget.targetMethod(); |
| |
| InvokeKind invokeKind = callTarget.invokeKind(); |
| if (invokeKind == CallTargetNode.InvokeKind.Special || invokeKind == CallTargetNode.InvokeKind.Static || targetMethod.canBeStaticallyBound()) { |
| return getExactInlineInfo(invoke, targetMethod); |
| } |
| |
| assert invokeKind.isIndirect(); |
| |
| ResolvedJavaType holder = targetMethod.getDeclaringClass(); |
| if (!(callTarget.receiver().stamp(NodeView.DEFAULT) instanceof ObjectStamp)) { |
| return null; |
| } |
| ObjectStamp receiverStamp = (ObjectStamp) callTarget.receiver().stamp(NodeView.DEFAULT); |
| if (receiverStamp.alwaysNull()) { |
| // Don't inline if receiver is known to be null |
| return null; |
| } |
| ResolvedJavaType contextType = invoke.getContextType(); |
| if (receiverStamp.type() != null) { |
| // the invoke target might be more specific than the holder (happens after inlining: |
| // parameters lose their declared type...) |
| ResolvedJavaType receiverType = receiverStamp.type(); |
| if (receiverType != null && holder.isAssignableFrom(receiverType)) { |
| holder = receiverType; |
| if (receiverStamp.isExactType()) { |
| assert targetMethod.getDeclaringClass().isAssignableFrom(holder) : holder + " subtype of " + targetMethod.getDeclaringClass() + " for " + targetMethod; |
| ResolvedJavaMethod resolvedMethod = holder.resolveConcreteMethod(targetMethod, contextType); |
| if (resolvedMethod != null) { |
| return getExactInlineInfo(invoke, resolvedMethod); |
| } |
| } |
| } |
| } |
| |
| if (holder.isArray()) { |
| // arrays can be treated as Objects |
| ResolvedJavaMethod resolvedMethod = holder.resolveConcreteMethod(targetMethod, contextType); |
| if (resolvedMethod != null) { |
| return getExactInlineInfo(invoke, resolvedMethod); |
| } |
| } |
| |
| if (invokeKind != InvokeKind.Interface) { |
| AssumptionResult<ResolvedJavaType> leafConcreteSubtype = holder.findLeafConcreteSubtype(); |
| if (leafConcreteSubtype != null) { |
| ResolvedJavaMethod resolvedMethod = leafConcreteSubtype.getResult().resolveConcreteMethod(targetMethod, contextType); |
| if (resolvedMethod != null) { |
| if (leafConcreteSubtype.canRecordTo(callTarget.graph().getAssumptions())) { |
| return getAssumptionInlineInfo(invoke, resolvedMethod, leafConcreteSubtype); |
| } else { |
| return getTypeCheckedAssumptionInfo(invoke, resolvedMethod, leafConcreteSubtype.getResult()); |
| } |
| } |
| } |
| |
| AssumptionResult<ResolvedJavaMethod> concrete = holder.findUniqueConcreteMethod(targetMethod); |
| if (concrete != null && concrete.canRecordTo(callTarget.graph().getAssumptions())) { |
| return getAssumptionInlineInfo(invoke, concrete.getResult(), concrete); |
| } |
| } |
| |
| // type check based inlining |
| return getTypeCheckedInlineInfo(invoke, targetMethod); |
| } |
| |
| private InlineInfo getTypeCheckedAssumptionInfo(Invoke invoke, ResolvedJavaMethod method, ResolvedJavaType type) { |
| if (!checkTargetConditions(invoke, method)) { |
| return null; |
| } |
| return new TypeGuardInlineInfo(invoke, method, type); |
| } |
| |
| private InlineInfo getTypeCheckedInlineInfo(Invoke invoke, ResolvedJavaMethod targetMethod) { |
| JavaTypeProfile typeProfile = ((MethodCallTargetNode) invoke.callTarget()).getProfile(); |
| if (typeProfile == null) { |
| InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "no type profile exists"); |
| invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "no type profile exists"); |
| return null; |
| } |
| |
| JavaTypeProfile.ProfiledType[] ptypes = typeProfile.getTypes(); |
| if (ptypes == null || ptypes.length <= 0) { |
| InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "no types in profile"); |
| invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "no types in profile"); |
| return null; |
| } |
| ResolvedJavaType contextType = invoke.getContextType(); |
| double notRecordedTypeProbability = typeProfile.getNotRecordedProbability(); |
| final OptimisticOptimizations optimisticOpts = context.getOptimisticOptimizations(); |
| OptionValues options = invoke.asNode().getOptions(); |
| if (ptypes.length == 1 && notRecordedTypeProbability == 0) { |
| if (!optimisticOpts.inlineMonomorphicCalls(options)) { |
| InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "inlining monomorphic calls is disabled"); |
| invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "inlining monomorphic calls is disabled"); |
| return null; |
| } |
| |
| ResolvedJavaType type = ptypes[0].getType(); |
| assert type.isArray() || type.isConcrete(); |
| ResolvedJavaMethod concrete = type.resolveConcreteMethod(targetMethod, contextType); |
| if (!checkTargetConditions(invoke, concrete)) { |
| return null; |
| } |
| return new TypeGuardInlineInfo(invoke, concrete, type); |
| } else { |
| invoke.setPolymorphic(true); |
| |
| if (!optimisticOpts.inlinePolymorphicCalls(options) && notRecordedTypeProbability == 0) { |
| InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "inlining polymorphic calls is disabled (%d types)", ptypes.length); |
| invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "inlining polymorphic calls is disabled (%d types)", ptypes.length); |
| return null; |
| } |
| if (!optimisticOpts.inlineMegamorphicCalls(options) && notRecordedTypeProbability > 0) { |
| // due to filtering impossible types, notRecordedTypeProbability can be > 0 although |
| // the number of types is lower than what can be recorded in a type profile |
| InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "inlining megamorphic calls is disabled (%d types, %f %% not recorded types)", ptypes.length, |
| notRecordedTypeProbability * 100); |
| invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, |
| "inlining megamorphic calls is disabled (%d types, %f %% not recorded types)", ptypes.length, notRecordedTypeProbability); |
| return null; |
| } |
| |
| // Find unique methods and their probabilities. |
| ArrayList<ResolvedJavaMethod> concreteMethods = new ArrayList<>(); |
| ArrayList<Double> concreteMethodsProbabilities = new ArrayList<>(); |
| for (int i = 0; i < ptypes.length; i++) { |
| ResolvedJavaMethod concrete = ptypes[i].getType().resolveConcreteMethod(targetMethod, contextType); |
| if (concrete == null) { |
| InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "could not resolve method"); |
| invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "could not resolve method"); |
| return null; |
| } |
| int index = concreteMethods.indexOf(concrete); |
| double curProbability = ptypes[i].getProbability(); |
| if (index < 0) { |
| index = concreteMethods.size(); |
| concreteMethods.add(concrete); |
| concreteMethodsProbabilities.add(curProbability); |
| } else { |
| concreteMethodsProbabilities.set(index, concreteMethodsProbabilities.get(index) + curProbability); |
| } |
| } |
| |
| // Clear methods that fall below the threshold. |
| if (notRecordedTypeProbability > 0) { |
| ArrayList<ResolvedJavaMethod> newConcreteMethods = new ArrayList<>(); |
| ArrayList<Double> newConcreteMethodsProbabilities = new ArrayList<>(); |
| for (int i = 0; i < concreteMethods.size(); ++i) { |
| if (concreteMethodsProbabilities.get(i) >= MegamorphicInliningMinMethodProbability.getValue(options)) { |
| newConcreteMethods.add(concreteMethods.get(i)); |
| newConcreteMethodsProbabilities.add(concreteMethodsProbabilities.get(i)); |
| } |
| } |
| |
| if (newConcreteMethods.isEmpty()) { |
| // No method left that is worth inlining. |
| InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "no methods remaining after filtering less frequent methods (%d methods previously)", |
| concreteMethods.size()); |
| invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, |
| "no methods remaining after filtering less frequent methods (%d methods previously)", concreteMethods.size()); |
| return null; |
| } |
| |
| concreteMethods = newConcreteMethods; |
| concreteMethodsProbabilities = newConcreteMethodsProbabilities; |
| } |
| |
| if (concreteMethods.size() > maxMethodPerInlining) { |
| InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "polymorphic call with more than %d target methods", maxMethodPerInlining); |
| invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "polymorphic call with more than %d target methods", maxMethodPerInlining); |
| return null; |
| } |
| |
| // Clean out types whose methods are no longer available. |
| ArrayList<JavaTypeProfile.ProfiledType> usedTypes = new ArrayList<>(); |
| ArrayList<Integer> typesToConcretes = new ArrayList<>(); |
| for (JavaTypeProfile.ProfiledType type : ptypes) { |
| ResolvedJavaMethod concrete = type.getType().resolveConcreteMethod(targetMethod, contextType); |
| int index = concreteMethods.indexOf(concrete); |
| if (index == -1) { |
| notRecordedTypeProbability += type.getProbability(); |
| } else { |
| assert type.getType().isArray() || !type.getType().isAbstract() : type + " " + concrete; |
| usedTypes.add(type); |
| typesToConcretes.add(index); |
| } |
| } |
| |
| if (usedTypes.isEmpty()) { |
| // No type left that is worth checking for. |
| InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "no types remaining after filtering less frequent types (%d types previously)", ptypes.length); |
| invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "no types remaining after filtering less frequent types (%d types previously)", |
| ptypes.length); |
| return null; |
| } |
| |
| for (ResolvedJavaMethod concrete : concreteMethods) { |
| if (!checkTargetConditions(invoke, concrete)) { |
| InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "it is a polymorphic method call and at least one invoked method cannot be inlined"); |
| invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, |
| "it is a polymorphic method call and at least one invoked method cannot be inlined"); |
| return null; |
| } |
| } |
| return new MultiTypeGuardInlineInfo(invoke, concreteMethods, usedTypes, typesToConcretes, notRecordedTypeProbability); |
| } |
| } |
| |
| private InlineInfo getAssumptionInlineInfo(Invoke invoke, ResolvedJavaMethod concrete, AssumptionResult<?> takenAssumption) { |
| assert concrete.isConcrete(); |
| if (checkTargetConditions(invoke, concrete)) { |
| return new AssumptionInlineInfo(invoke, concrete, takenAssumption); |
| } |
| return null; |
| } |
| |
| private InlineInfo getExactInlineInfo(Invoke invoke, ResolvedJavaMethod targetMethod) { |
| assert targetMethod.isConcrete(); |
| if (checkTargetConditions(invoke, targetMethod)) { |
| return new ExactInlineInfo(invoke, targetMethod); |
| } |
| return null; |
| } |
| |
| @SuppressWarnings("try") |
| private void doInline(CallsiteHolderExplorable callerCallsiteHolder, MethodInvocation calleeInvocation, String reason) { |
| StructuredGraph callerGraph = callerCallsiteHolder.graph(); |
| InlineInfo calleeInfo = calleeInvocation.callee(); |
| try { |
| try (DebugContext.Scope scope = debug.scope("doInline", callerGraph)) { |
| EconomicSet<Node> canonicalizedNodes = EconomicSet.create(Equivalence.IDENTITY); |
| canonicalizedNodes.addAll(calleeInfo.invoke().asNode().usages()); |
| EconomicSet<Node> parameterUsages = calleeInfo.inline(new Providers(context), reason); |
| canonicalizedNodes.addAll(parameterUsages); |
| counterInliningRuns.increment(debug); |
| debug.dump(DebugContext.DETAILED_LEVEL, callerGraph, "after %s", calleeInfo); |
| |
| Graph.Mark markBeforeCanonicalization = callerGraph.getMark(); |
| |
| canonicalizer.applyIncremental(callerGraph, context, canonicalizedNodes); |
| |
| // process invokes that are possibly created during canonicalization |
| for (Node newNode : callerGraph.getNewNodes(markBeforeCanonicalization)) { |
| if (newNode instanceof Invoke) { |
| callerCallsiteHolder.pushInvoke((Invoke) newNode); |
| } |
| } |
| |
| callerCallsiteHolder.computeProbabilities(); |
| |
| counterInliningPerformed.increment(debug); |
| } |
| } catch (BailoutException bailout) { |
| throw bailout; |
| } catch (AssertionError | RuntimeException e) { |
| throw new GraalError(e).addContext(calleeInfo.toString()); |
| } catch (GraalError e) { |
| throw e.addContext(calleeInfo.toString()); |
| } catch (Throwable e) { |
| throw debug.handle(e); |
| } |
| } |
| |
| /** |
| * |
| * This method attempts: |
| * <ol> |
| * <li>to inline at the callsite given by <code>calleeInvocation</code>, where that callsite |
| * belongs to the {@link CallsiteHolderExplorable} at the top of the {@link #graphQueue} |
| * maintained in this class.</li> |
| * <li>otherwise, to devirtualize the callsite in question.</li> |
| * </ol> |
| * |
| * @return true iff inlining was actually performed |
| */ |
| private boolean tryToInline(MethodInvocation calleeInvocation, int inliningDepth) { |
| CallsiteHolderExplorable callerCallsiteHolder = (CallsiteHolderExplorable) currentGraph(); |
| InlineInfo calleeInfo = calleeInvocation.callee(); |
| assert callerCallsiteHolder.containsInvoke(calleeInfo.invoke()); |
| counterInliningConsidered.increment(debug); |
| |
| InliningPolicy.Decision decision = inliningPolicy.isWorthInlining(context.getReplacements(), calleeInvocation, inliningDepth, true); |
| if (decision.shouldInline()) { |
| doInline(callerCallsiteHolder, calleeInvocation, decision.getReason()); |
| return true; |
| } |
| |
| if (context.getOptimisticOptimizations().devirtualizeInvokes(calleeInfo.graph().getOptions())) { |
| calleeInfo.tryToDevirtualizeInvoke(new Providers(context)); |
| } |
| |
| return false; |
| } |
| |
| /** |
| * This method picks one of the callsites belonging to the current |
| * {@link CallsiteHolderExplorable}. Provided the callsite qualifies to be analyzed for |
| * inlining, this method prepares a new stack top in {@link InliningData} for such callsite, |
| * which comprises: |
| * <ul> |
| * <li>preparing a summary of feasible targets, ie preparing an {@link InlineInfo}</li> |
| * <li>based on it, preparing the stack top proper which consists of:</li> |
| * <ul> |
| * <li>one {@link MethodInvocation}</li> |
| * <li>a {@link CallsiteHolder} for each feasible target</li> |
| * </ul> |
| * </ul> |
| * |
| * <p> |
| * The thus prepared "stack top" is needed by {@link #moveForward()} to explore the space of |
| * inlining decisions (each decision one of: backtracking, delving, inlining). |
| * </p> |
| * |
| * <p> |
| * The {@link InlineInfo} used to get things rolling is kept around in the |
| * {@link MethodInvocation}, it will be needed in case of inlining, see |
| * {@link InlineInfo#inline(Providers, String)} |
| * </p> |
| */ |
| private void processNextInvoke() { |
| CallsiteHolderExplorable callsiteHolder = (CallsiteHolderExplorable) currentGraph(); |
| Invoke invoke = callsiteHolder.popInvoke(); |
| InlineInfo info = getInlineInfo(invoke); |
| |
| if (info != null) { |
| info.populateInlinableElements(context, currentGraph().graph(), canonicalizer, rootGraph.getOptions()); |
| double invokeProbability = callsiteHolder.invokeProbability(invoke); |
| double invokeRelevance = callsiteHolder.invokeRelevance(invoke); |
| MethodInvocation methodInvocation = new MethodInvocation(info, invokeProbability, invokeRelevance, freshlyInstantiatedArguments(invoke, callsiteHolder.getFixedParams())); |
| pushInvocationAndGraphs(methodInvocation); |
| } |
| } |
| |
| /** |
| * Gets the freshly instantiated arguments. |
| * <p> |
| * A freshly instantiated argument is either: |
| * <uL> |
| * <li>an {@link InliningData#isFreshInstantiation(org.graalvm.compiler.nodes.ValueNode)}</li> |
| * <li>a fixed-param, ie a {@link ParameterNode} receiving a freshly instantiated argument</li> |
| * </uL> |
| * </p> |
| * |
| * @return the positions of freshly instantiated arguments in the argument list of the |
| * <code>invoke</code>, or null if no such positions exist. |
| */ |
| public static BitSet freshlyInstantiatedArguments(Invoke invoke, EconomicSet<ParameterNode> fixedParams) { |
| assert fixedParams != null; |
| assert paramsAndInvokeAreInSameGraph(invoke, fixedParams); |
| BitSet result = null; |
| int argIdx = 0; |
| for (ValueNode arg : invoke.callTarget().arguments()) { |
| assert arg != null; |
| if (isFreshInstantiation(arg) || (arg instanceof ParameterNode && fixedParams.contains((ParameterNode) arg))) { |
| if (result == null) { |
| result = new BitSet(); |
| } |
| result.set(argIdx); |
| } |
| argIdx++; |
| } |
| return result; |
| } |
| |
| private static boolean paramsAndInvokeAreInSameGraph(Invoke invoke, EconomicSet<ParameterNode> fixedParams) { |
| if (fixedParams.isEmpty()) { |
| return true; |
| } |
| for (ParameterNode p : fixedParams) { |
| if (p.graph() != invoke.asNode().graph()) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| public int graphCount() { |
| return graphQueue.size(); |
| } |
| |
| public boolean hasUnprocessedGraphs() { |
| return !graphQueue.isEmpty(); |
| } |
| |
| private CallsiteHolder currentGraph() { |
| return graphQueue.peek(); |
| } |
| |
| private void popGraph() { |
| graphQueue.pop(); |
| assert graphQueue.size() <= maxGraphs; |
| } |
| |
| private void popGraphs(int count) { |
| assert count >= 0; |
| for (int i = 0; i < count; i++) { |
| graphQueue.pop(); |
| } |
| } |
| |
| private static final Object[] NO_CONTEXT = {}; |
| |
| /** |
| * Gets the call hierarchy of this inlining from outer most call to inner most callee. |
| */ |
| private Object[] inliningContext() { |
| if (!debug.isDumpEnabled(DebugContext.INFO_LEVEL)) { |
| return NO_CONTEXT; |
| } |
| Object[] result = new Object[graphQueue.size()]; |
| int i = 0; |
| for (CallsiteHolder g : graphQueue) { |
| result[i++] = g.method(); |
| } |
| return result; |
| } |
| |
| private MethodInvocation currentInvocation() { |
| return invocationQueue.peekFirst(); |
| } |
| |
| private void pushInvocationAndGraphs(MethodInvocation methodInvocation) { |
| invocationQueue.addFirst(methodInvocation); |
| InlineInfo info = methodInvocation.callee(); |
| maxGraphs += info.numberOfMethods(); |
| assert graphQueue.size() <= maxGraphs; |
| for (int i = 0; i < info.numberOfMethods(); i++) { |
| CallsiteHolder ch = methodInvocation.buildCallsiteHolderForElement(i); |
| assert !contains(ch.graph()); |
| graphQueue.push(ch); |
| assert graphQueue.size() <= maxGraphs; |
| } |
| } |
| |
| private void popInvocation() { |
| maxGraphs -= invocationQueue.peekFirst().callee().numberOfMethods(); |
| assert graphQueue.size() <= maxGraphs; |
| invocationQueue.removeFirst(); |
| } |
| |
| public int countRecursiveInlining(ResolvedJavaMethod method) { |
| int count = 0; |
| for (CallsiteHolder callsiteHolder : graphQueue) { |
| if (method.equals(callsiteHolder.method())) { |
| count++; |
| } |
| } |
| return count; |
| } |
| |
| public int inliningDepth() { |
| assert invocationQueue.size() > 0; |
| return invocationQueue.size() - 1; |
| } |
| |
| @Override |
| public String toString() { |
| StringBuilder result = new StringBuilder("Invocations: "); |
| |
| for (MethodInvocation invocation : invocationQueue) { |
| if (invocation.callee() != null) { |
| result.append(invocation.callee().numberOfMethods()); |
| result.append("x "); |
| result.append(invocation.callee().invoke()); |
| result.append("; "); |
| } |
| } |
| |
| result.append("\nGraphs: "); |
| for (CallsiteHolder graph : graphQueue) { |
| result.append(graph.graph()); |
| result.append("; "); |
| } |
| |
| return result.toString(); |
| } |
| |
| /** |
| * Gets a stack trace representing the current inlining stack represented by this object. |
| */ |
| public Collection<StackTraceElement> getInvocationStackTrace() { |
| List<StackTraceElement> result = new ArrayList<>(); |
| for (CallsiteHolder graph : graphQueue) { |
| result.add(graph.method().asStackTraceElement(0)); |
| } |
| |
| return result; |
| } |
| |
| private boolean contains(StructuredGraph graph) { |
| assert graph != null; |
| for (CallsiteHolder info : graphQueue) { |
| if (info.graph() == graph) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * <p> |
| * The stack realized by {@link InliningData} grows and shrinks as choices are made among the |
| * alternatives below: |
| * <ol> |
| * <li>not worth inlining: pop stack top, which comprises: |
| * <ul> |
| * <li>pop any remaining graphs not yet delved into</li> |
| * <li>pop the current invocation</li> |
| * </ul> |
| * </li> |
| * <li>{@link #processNextInvoke() delve} into one of the callsites hosted in the current graph, |
| * such callsite is explored next by {@link #moveForward()}</li> |
| * <li>{@link #tryToInline(MethodInvocation, int) try to inline}: move past the current graph |
| * (remove it from the topmost element). |
| * <ul> |
| * <li>If that was the last one then {@link #tryToInline(MethodInvocation, int) try to inline} |
| * the callsite under consideration (ie, the "current invocation").</li> |
| * <li>Whether inlining occurs or not, that callsite is removed from the top of |
| * {@link InliningData} .</li> |
| * </ul> |
| * </li> |
| * </ol> |
| * </p> |
| * |
| * <p> |
| * Some facts about the alternatives above: |
| * <ul> |
| * <li>the first step amounts to backtracking, the 2nd one to depth-search, and the 3rd one also |
| * involves backtracking (however possibly after inlining).</li> |
| * <li>the choice of abandon-and-backtrack or delve-into depends on |
| * {@link InliningPolicy#isWorthInlining} and {@link InliningPolicy#continueInlining}.</li> |
| * <li>the 3rd choice is picked whenever none of the previous choices are made</li> |
| * </ul> |
| * </p> |
| * |
| * @return true iff inlining was actually performed |
| */ |
| @SuppressWarnings("try") |
| public boolean moveForward() { |
| |
| final MethodInvocation currentInvocation = currentInvocation(); |
| |
| final boolean backtrack = (!currentInvocation.isRoot() && !inliningPolicy.isWorthInlining(context.getReplacements(), currentInvocation, inliningDepth(), false).shouldInline()); |
| if (backtrack) { |
| int remainingGraphs = currentInvocation.totalGraphs() - currentInvocation.processedGraphs(); |
| assert remainingGraphs > 0; |
| popGraphs(remainingGraphs); |
| popInvocation(); |
| return false; |
| } |
| |
| final boolean delve = currentGraph().hasRemainingInvokes() && inliningPolicy.continueInlining(currentGraph().graph()); |
| if (delve) { |
| processNextInvoke(); |
| return false; |
| } |
| |
| popGraph(); |
| if (currentInvocation.isRoot()) { |
| return false; |
| } |
| |
| // try to inline |
| assert currentInvocation.callee().invoke().asNode().isAlive(); |
| currentInvocation.incrementProcessedGraphs(); |
| if (currentInvocation.processedGraphs() == currentInvocation.totalGraphs()) { |
| /* |
| * "all of currentInvocation's graphs processed" amounts to |
| * "all concrete methods that come into question already had the callees they contain analyzed for inlining" |
| */ |
| popInvocation(); |
| try (DebugContext.Scope s = debug.scope("Inlining", inliningContext())) { |
| if (tryToInline(currentInvocation, inliningDepth() + 1)) { |
| // Report real progress only if we inline into the root graph |
| return currentGraph().graph() == rootGraph; |
| } |
| return false; |
| } catch (Throwable e) { |
| throw debug.handle(e); |
| } |
| } |
| |
| return false; |
| } |
| |
| /** |
| * Checks an invariant that {@link #moveForward()} must maintain: "the top invocation records |
| * how many concrete target methods (for it) remain on the {@link #graphQueue}; those targets |
| * 'belong' to the current invocation in question. |
| */ |
| private boolean topGraphsForTopInvocation() { |
| if (invocationQueue.isEmpty()) { |
| assert graphQueue.isEmpty(); |
| return true; |
| } |
| if (currentInvocation().isRoot()) { |
| if (!graphQueue.isEmpty()) { |
| assert graphQueue.size() == 1; |
| } |
| return true; |
| } |
| final int remainingGraphs = currentInvocation().totalGraphs() - currentInvocation().processedGraphs(); |
| final Iterator<CallsiteHolder> iter = graphQueue.iterator(); |
| for (int i = (remainingGraphs - 1); i >= 0; i--) { |
| if (!iter.hasNext()) { |
| assert false; |
| return false; |
| } |
| CallsiteHolder queuedTargetCH = iter.next(); |
| Inlineable targetIE = currentInvocation().callee().inlineableElementAt(i); |
| InlineableGraph targetIG = (InlineableGraph) targetIE; |
| assert queuedTargetCH.method().equals(targetIG.getGraph().method()); |
| } |
| return true; |
| } |
| |
| /** |
| * This method checks invariants for this class. Named after shorthand for "internal |
| * representation is ok". |
| */ |
| public boolean repOK() { |
| assert topGraphsForTopInvocation(); |
| return true; |
| } |
| } |
