https://openjdk.java.net/ 
/*
 * 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;


 The space of inlining decisions is explored depth-first with the help of a stack realized by InliningData. At any point in time, the topmost element of that stack consists of: 
    

  • the callsite under consideration is tracked as a MethodInvocation.
    • 

  • one or more CallsiteHolders, 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.
    • 






The bottom element in the stack consists of:





See Also:
/**
 * <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.

/**
     * 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.

Params:
  • invoke – the invoke that should be inlined
Returns:an instance of InlineInfo, or null if no inlining is possible at the given invoke
/**
     * 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:

    

  1. to inline at the callsite given by calleeInvocation, where that callsite belongs to the CallsiteHolderExplorable at the top of the graphQueue maintained in this class.
    2. 

  2. otherwise, to devirtualize the callsite in question.
    3. 



Returns:true iff inlining was actually performed
/**
     *
     * 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 CallsiteHolderExplorable. Provided the callsite qualifies to be analyzed for inlining, this method prepares a new stack top in InliningData for such callsite, which comprises: 

 The thus prepared "stack top" is needed by moveForward() to explore the space of inlining decisions (each decision one of: backtracking, delving, inlining). 


 The InlineInfo used to get things rolling is kept around in the MethodInvocation, it will be needed in case of inlining, see InlineInfo.inline(Providers, String) 


/**
     * 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.


A freshly instantiated argument is either:





Returns:the positions of freshly instantiated arguments in the argument list of the
        invoke, or null if no such positions exist.
/**
     * 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.

/**
     * 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.

/**
     * 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;
    }

    
 The stack realized by InliningData grows and shrinks as choices are made among the alternatives below: 
    

  1. not worth inlining: pop stack top, which comprises:

      

    • pop any remaining graphs not yet delved into
      • 

    • pop the current invocation
      • 

    

    2. 

  2. delve into one of the callsites hosted in the current graph, such callsite is explored next by moveForward()
    3. 

  3. try to inline: move past the current graph (remove it from the topmost element). 
      

    • If that was the last one then try to inline the callsite under consideration (ie, the "current invocation").
      • 

    • Whether inlining occurs or not, that callsite is removed from the top of InliningData .
      • 

    

    4. 






Some facts about the alternatives above:

    

  • the first step amounts to backtracking, the 2nd one to depth-search, and the 3rd one also
involves backtracking (however possibly after inlining).
    • 

  • the choice of abandon-and-backtrack or delve-into depends on InliningPolicy.isWorthInlining and InliningPolicy.continueInlining.
    • 

  • the 3rd choice is picked whenever none of the previous choices are made
    • 





Returns:true iff inlining was actually performed
/**
     * <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 moveForward() must maintain: "the top invocation records how many concrete target methods (for it) remain on the graphQueue; those targets 'belong' to the current invocation in question. 
/**
     * 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".

/**
     * This method checks invariants for this class. Named after shorthand for "internal
     * representation is ok".
     */
    public boolean repOK() {
        assert topGraphsForTopInvocation();
        return true;
    }
}