1 /*
   2  * Copyright (c) 2011, 2016, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 
  25 package org.graalvm.compiler.phases.common.inlining.walker;
  26 
  27 import static org.graalvm.compiler.core.common.GraalOptions.Intrinsify;
  28 import static org.graalvm.compiler.core.common.GraalOptions.MaximumRecursiveInlining;
  29 import static org.graalvm.compiler.core.common.GraalOptions.MegamorphicInliningMinMethodProbability;
  30 
  31 import java.util.ArrayDeque;
  32 import java.util.ArrayList;
  33 import java.util.BitSet;
  34 import java.util.Collection;
  35 import java.util.Iterator;
  36 import java.util.LinkedList;
  37 import java.util.List;
  38 
  39 import jdk.internal.vm.compiler.collections.EconomicSet;
  40 import jdk.internal.vm.compiler.collections.Equivalence;
  41 import org.graalvm.compiler.core.common.type.ObjectStamp;
  42 import org.graalvm.compiler.debug.CounterKey;
  43 import org.graalvm.compiler.debug.DebugContext;
  44 import org.graalvm.compiler.debug.GraalError;
  45 import org.graalvm.compiler.graph.Graph;
  46 import org.graalvm.compiler.graph.Node;
  47 import org.graalvm.compiler.nodes.CallTargetNode;
  48 import org.graalvm.compiler.nodes.Invoke;
  49 import org.graalvm.compiler.nodes.NodeView;
  50 import org.graalvm.compiler.nodes.ParameterNode;
  51 import org.graalvm.compiler.nodes.StructuredGraph;
  52 import org.graalvm.compiler.nodes.ValueNode;
  53 import org.graalvm.compiler.nodes.java.AbstractNewObjectNode;
  54 import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
  55 import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode;
  56 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
  57 import org.graalvm.compiler.options.OptionValues;
  58 import org.graalvm.compiler.phases.OptimisticOptimizations;
  59 import org.graalvm.compiler.phases.common.CanonicalizerPhase;
  60 import org.graalvm.compiler.phases.common.inlining.InliningUtil;
  61 import org.graalvm.compiler.phases.common.inlining.info.AssumptionInlineInfo;
  62 import org.graalvm.compiler.phases.common.inlining.info.ExactInlineInfo;
  63 import org.graalvm.compiler.phases.common.inlining.info.InlineInfo;
  64 import org.graalvm.compiler.phases.common.inlining.info.MultiTypeGuardInlineInfo;
  65 import org.graalvm.compiler.phases.common.inlining.info.TypeGuardInlineInfo;
  66 import org.graalvm.compiler.phases.common.inlining.info.elem.Inlineable;
  67 import org.graalvm.compiler.phases.common.inlining.info.elem.InlineableGraph;
  68 import org.graalvm.compiler.phases.common.inlining.policy.InliningPolicy;
  69 import org.graalvm.compiler.phases.tiers.HighTierContext;
  70 import org.graalvm.compiler.phases.util.Providers;
  71 
  72 import jdk.vm.ci.code.BailoutException;
  73 import jdk.vm.ci.meta.Assumptions.AssumptionResult;
  74 import jdk.vm.ci.meta.JavaTypeProfile;
  75 import jdk.vm.ci.meta.ResolvedJavaMethod;
  76 import jdk.vm.ci.meta.ResolvedJavaType;
  77 
  78 /**
  79  * <p>
  80  * The space of inlining decisions is explored depth-first with the help of a stack realized by
  81  * {@link InliningData}. At any point in time, the topmost element of that stack consists of:
  82  * <ul>
  83  * <li>the callsite under consideration is tracked as a {@link MethodInvocation}.</li>
  84  * <li>one or more {@link CallsiteHolder}s, all of them associated to the callsite above. Why more
  85  * than one? Depending on the type-profile for the receiver more than one concrete method may be
  86  * feasible target.</li>
  87  * </ul>
  88  * </p>
  89  *
  90  * <p>
  91  * The bottom element in the stack consists of:
  92  * <ul>
  93  * <li>a single {@link MethodInvocation} (the
  94  * {@link org.graalvm.compiler.phases.common.inlining.walker.MethodInvocation#isRoot root} one, ie
  95  * the unknown caller of the root graph)</li>
  96  * <li>a single {@link CallsiteHolder} (the root one, for the method on which inlining was called)
  97  * </li>
  98  * </ul>
  99  * </p>
 100  *
 101  * @see #moveForward()
 102  */
 103 public class InliningData {
 104 
 105     // Counters
 106     private static final CounterKey counterInliningPerformed = DebugContext.counter("InliningPerformed");
 107     private static final CounterKey counterInliningRuns = DebugContext.counter("InliningRuns");
 108     private static final CounterKey counterInliningConsidered = DebugContext.counter("InliningConsidered");
 109 
 110     /**
 111      * Call hierarchy from outer most call (i.e., compilation unit) to inner most callee.
 112      */
 113     private final ArrayDeque<CallsiteHolder> graphQueue = new ArrayDeque<>();
 114     private final ArrayDeque<MethodInvocation> invocationQueue = new ArrayDeque<>();
 115 
 116     private final HighTierContext context;
 117     private final int maxMethodPerInlining;
 118     private final CanonicalizerPhase canonicalizer;
 119     private final InliningPolicy inliningPolicy;
 120     private final StructuredGraph rootGraph;
 121     private final DebugContext debug;
 122 
 123     private int maxGraphs;
 124 
 125     public InliningData(StructuredGraph rootGraph, HighTierContext context, int maxMethodPerInlining, CanonicalizerPhase canonicalizer, InliningPolicy inliningPolicy, LinkedList<Invoke> rootInvokes) {
 126         assert rootGraph != null;
 127         this.context = context;
 128         this.maxMethodPerInlining = maxMethodPerInlining;
 129         this.canonicalizer = canonicalizer;
 130         this.inliningPolicy = inliningPolicy;
 131         this.maxGraphs = 1;
 132         this.rootGraph = rootGraph;
 133         this.debug = rootGraph.getDebug();
 134 
 135         invocationQueue.push(new MethodInvocation(null, 1.0, 1.0, null));
 136         graphQueue.push(new CallsiteHolderExplorable(rootGraph, 1.0, 1.0, null, rootInvokes));
 137     }
 138 
 139     public static boolean isFreshInstantiation(ValueNode arg) {
 140         return (arg instanceof AbstractNewObjectNode) || (arg instanceof AllocatedObjectNode) || (arg instanceof VirtualObjectNode);
 141     }
 142 
 143     private String checkTargetConditionsHelper(ResolvedJavaMethod method, int invokeBci) {
 144         OptionValues options = rootGraph.getOptions();
 145         if (method == null) {
 146             return "the method is not resolved";
 147         } else if (method.isNative() && (!Intrinsify.getValue(options) || !InliningUtil.canIntrinsify(context.getReplacements(), method, invokeBci))) {
 148             return "it is a non-intrinsic native method";
 149         } else if (method.isAbstract()) {
 150             return "it is an abstract method";
 151         } else if (!method.getDeclaringClass().isInitialized()) {
 152             return "the method's class is not initialized";
 153         } else if (!method.canBeInlined()) {
 154             return "it is marked non-inlinable";
 155         } else if (countRecursiveInlining(method) > MaximumRecursiveInlining.getValue(options)) {
 156             return "it exceeds the maximum recursive inlining depth";
 157         } else {
 158             if (new OptimisticOptimizations(rootGraph.getProfilingInfo(method), options).lessOptimisticThan(context.getOptimisticOptimizations())) {
 159                 return "the callee uses less optimistic optimizations than caller";
 160             } else {
 161                 return null;
 162             }
 163         }
 164     }
 165 
 166     private boolean checkTargetConditions(Invoke invoke, ResolvedJavaMethod method) {
 167         final String failureMessage = checkTargetConditionsHelper(method, invoke.bci());
 168         if (failureMessage == null) {
 169             return true;
 170         } else {
 171             InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), method, failureMessage);
 172             invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, failureMessage);
 173             return false;
 174         }
 175     }
 176 
 177     /**
 178      * Determines if inlining is possible at the given invoke node.
 179      *
 180      * @param invoke the invoke that should be inlined
 181      * @return an instance of InlineInfo, or null if no inlining is possible at the given invoke
 182      */
 183     private InlineInfo getInlineInfo(Invoke invoke) {
 184         final String failureMessage = InliningUtil.checkInvokeConditions(invoke);
 185         if (failureMessage != null) {
 186             InliningUtil.logNotInlinedMethod(invoke, failureMessage);
 187             return null;
 188         }
 189         MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget();
 190         ResolvedJavaMethod targetMethod = callTarget.targetMethod();
 191 
 192         if (callTarget.invokeKind() == CallTargetNode.InvokeKind.Special || targetMethod.canBeStaticallyBound()) {
 193             return getExactInlineInfo(invoke, targetMethod);
 194         }
 195 
 196         assert callTarget.invokeKind().isIndirect();
 197 
 198         ResolvedJavaType holder = targetMethod.getDeclaringClass();
 199         if (!(callTarget.receiver().stamp(NodeView.DEFAULT) instanceof ObjectStamp)) {
 200             return null;
 201         }
 202         ObjectStamp receiverStamp = (ObjectStamp) callTarget.receiver().stamp(NodeView.DEFAULT);
 203         if (receiverStamp.alwaysNull()) {
 204             // Don't inline if receiver is known to be null
 205             return null;
 206         }
 207         ResolvedJavaType contextType = invoke.getContextType();
 208         if (receiverStamp.type() != null) {
 209             // the invoke target might be more specific than the holder (happens after inlining:
 210             // parameters lose their declared type...)
 211             ResolvedJavaType receiverType = receiverStamp.type();
 212             if (receiverType != null && holder.isAssignableFrom(receiverType)) {
 213                 holder = receiverType;
 214                 if (receiverStamp.isExactType()) {
 215                     assert targetMethod.getDeclaringClass().isAssignableFrom(holder) : holder + " subtype of " + targetMethod.getDeclaringClass() + " for " + targetMethod;
 216                     ResolvedJavaMethod resolvedMethod = holder.resolveConcreteMethod(targetMethod, contextType);
 217                     if (resolvedMethod != null) {
 218                         return getExactInlineInfo(invoke, resolvedMethod);
 219                     }
 220                 }
 221             }
 222         }
 223 
 224         if (holder.isArray()) {
 225             // arrays can be treated as Objects
 226             ResolvedJavaMethod resolvedMethod = holder.resolveConcreteMethod(targetMethod, contextType);
 227             if (resolvedMethod != null) {
 228                 return getExactInlineInfo(invoke, resolvedMethod);
 229             }
 230         }
 231 
 232         AssumptionResult<ResolvedJavaType> leafConcreteSubtype = holder.findLeafConcreteSubtype();
 233         if (leafConcreteSubtype != null) {
 234             ResolvedJavaMethod resolvedMethod = leafConcreteSubtype.getResult().resolveConcreteMethod(targetMethod, contextType);
 235             if (resolvedMethod != null) {
 236                 if (leafConcreteSubtype.canRecordTo(callTarget.graph().getAssumptions())) {
 237                     return getAssumptionInlineInfo(invoke, resolvedMethod, leafConcreteSubtype);
 238                 } else {
 239                     return getTypeCheckedAssumptionInfo(invoke, resolvedMethod, leafConcreteSubtype.getResult());
 240                 }
 241             }
 242         }
 243 
 244         AssumptionResult<ResolvedJavaMethod> concrete = holder.findUniqueConcreteMethod(targetMethod);
 245         if (concrete != null && concrete.canRecordTo(callTarget.graph().getAssumptions())) {
 246             return getAssumptionInlineInfo(invoke, concrete.getResult(), concrete);
 247         }
 248 
 249         // type check based inlining
 250         return getTypeCheckedInlineInfo(invoke, targetMethod);
 251     }
 252 
 253     private InlineInfo getTypeCheckedAssumptionInfo(Invoke invoke, ResolvedJavaMethod method, ResolvedJavaType type) {
 254         if (!checkTargetConditions(invoke, method)) {
 255             return null;
 256         }
 257         return new TypeGuardInlineInfo(invoke, method, type);
 258     }
 259 
 260     private InlineInfo getTypeCheckedInlineInfo(Invoke invoke, ResolvedJavaMethod targetMethod) {
 261         JavaTypeProfile typeProfile = ((MethodCallTargetNode) invoke.callTarget()).getProfile();
 262         if (typeProfile == null) {
 263             InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "no type profile exists");
 264             invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "no type profile exists");
 265             return null;
 266         }
 267 
 268         JavaTypeProfile.ProfiledType[] ptypes = typeProfile.getTypes();
 269         if (ptypes == null || ptypes.length <= 0) {
 270             InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "no types in profile");
 271             invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "no types in profile");
 272             return null;
 273         }
 274         ResolvedJavaType contextType = invoke.getContextType();
 275         double notRecordedTypeProbability = typeProfile.getNotRecordedProbability();
 276         final OptimisticOptimizations optimisticOpts = context.getOptimisticOptimizations();
 277         OptionValues options = invoke.asNode().getOptions();
 278         if (ptypes.length == 1 && notRecordedTypeProbability == 0) {
 279             if (!optimisticOpts.inlineMonomorphicCalls(options)) {
 280                 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "inlining monomorphic calls is disabled");
 281                 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "inlining monomorphic calls is disabled");
 282                 return null;
 283             }
 284 
 285             ResolvedJavaType type = ptypes[0].getType();
 286             assert type.isArray() || type.isConcrete();
 287             ResolvedJavaMethod concrete = type.resolveConcreteMethod(targetMethod, contextType);
 288             if (!checkTargetConditions(invoke, concrete)) {
 289                 return null;
 290             }
 291             return new TypeGuardInlineInfo(invoke, concrete, type);
 292         } else {
 293             invoke.setPolymorphic(true);
 294 
 295             if (!optimisticOpts.inlinePolymorphicCalls(options) && notRecordedTypeProbability == 0) {
 296                 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "inlining polymorphic calls is disabled (%d types)", ptypes.length);
 297                 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "inlining polymorphic calls is disabled (%d types)", ptypes.length);
 298                 return null;
 299             }
 300             if (!optimisticOpts.inlineMegamorphicCalls(options) && notRecordedTypeProbability > 0) {
 301                 // due to filtering impossible types, notRecordedTypeProbability can be > 0 although
 302                 // the number of types is lower than what can be recorded in a type profile
 303                 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "inlining megamorphic calls is disabled (%d types, %f %% not recorded types)", ptypes.length,
 304                                 notRecordedTypeProbability * 100);
 305                 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null,
 306                                 "inlining megamorphic calls is disabled (%d types, %f %% not recorded types)", ptypes.length, notRecordedTypeProbability);
 307                 return null;
 308             }
 309 
 310             // Find unique methods and their probabilities.
 311             ArrayList<ResolvedJavaMethod> concreteMethods = new ArrayList<>();
 312             ArrayList<Double> concreteMethodsProbabilities = new ArrayList<>();
 313             for (int i = 0; i < ptypes.length; i++) {
 314                 ResolvedJavaMethod concrete = ptypes[i].getType().resolveConcreteMethod(targetMethod, contextType);
 315                 if (concrete == null) {
 316                     InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "could not resolve method");
 317                     invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "could not resolve method");
 318                     return null;
 319                 }
 320                 int index = concreteMethods.indexOf(concrete);
 321                 double curProbability = ptypes[i].getProbability();
 322                 if (index < 0) {
 323                     index = concreteMethods.size();
 324                     concreteMethods.add(concrete);
 325                     concreteMethodsProbabilities.add(curProbability);
 326                 } else {
 327                     concreteMethodsProbabilities.set(index, concreteMethodsProbabilities.get(index) + curProbability);
 328                 }
 329             }
 330 
 331             // Clear methods that fall below the threshold.
 332             if (notRecordedTypeProbability > 0) {
 333                 ArrayList<ResolvedJavaMethod> newConcreteMethods = new ArrayList<>();
 334                 ArrayList<Double> newConcreteMethodsProbabilities = new ArrayList<>();
 335                 for (int i = 0; i < concreteMethods.size(); ++i) {
 336                     if (concreteMethodsProbabilities.get(i) >= MegamorphicInliningMinMethodProbability.getValue(options)) {
 337                         newConcreteMethods.add(concreteMethods.get(i));
 338                         newConcreteMethodsProbabilities.add(concreteMethodsProbabilities.get(i));
 339                     }
 340                 }
 341 
 342                 if (newConcreteMethods.isEmpty()) {
 343                     // No method left that is worth inlining.
 344                     InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "no methods remaining after filtering less frequent methods (%d methods previously)",
 345                                     concreteMethods.size());
 346                     invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null,
 347                                     "no methods remaining after filtering less frequent methods (%d methods previously)", concreteMethods.size());
 348                     return null;
 349                 }
 350 
 351                 concreteMethods = newConcreteMethods;
 352                 concreteMethodsProbabilities = newConcreteMethodsProbabilities;
 353             }
 354 
 355             if (concreteMethods.size() > maxMethodPerInlining) {
 356                 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "polymorphic call with more than %d target methods", maxMethodPerInlining);
 357                 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "polymorphic call with more than %d target methods", maxMethodPerInlining);
 358                 return null;
 359             }
 360 
 361             // Clean out types whose methods are no longer available.
 362             ArrayList<JavaTypeProfile.ProfiledType> usedTypes = new ArrayList<>();
 363             ArrayList<Integer> typesToConcretes = new ArrayList<>();
 364             for (JavaTypeProfile.ProfiledType type : ptypes) {
 365                 ResolvedJavaMethod concrete = type.getType().resolveConcreteMethod(targetMethod, contextType);
 366                 int index = concreteMethods.indexOf(concrete);
 367                 if (index == -1) {
 368                     notRecordedTypeProbability += type.getProbability();
 369                 } else {
 370                     assert type.getType().isArray() || !type.getType().isAbstract() : type + " " + concrete;
 371                     usedTypes.add(type);
 372                     typesToConcretes.add(index);
 373                 }
 374             }
 375 
 376             if (usedTypes.isEmpty()) {
 377                 // No type left that is worth checking for.
 378                 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "no types remaining after filtering less frequent types (%d types previously)", ptypes.length);
 379                 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "no types remaining after filtering less frequent types (%d types previously)",
 380                                 ptypes.length);
 381                 return null;
 382             }
 383 
 384             for (ResolvedJavaMethod concrete : concreteMethods) {
 385                 if (!checkTargetConditions(invoke, concrete)) {
 386                     InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "it is a polymorphic method call and at least one invoked method cannot be inlined");
 387                     invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null,
 388                                     "it is a polymorphic method call and at least one invoked method cannot be inlined");
 389                     return null;
 390                 }
 391             }
 392             return new MultiTypeGuardInlineInfo(invoke, concreteMethods, usedTypes, typesToConcretes, notRecordedTypeProbability);
 393         }
 394     }
 395 
 396     private InlineInfo getAssumptionInlineInfo(Invoke invoke, ResolvedJavaMethod concrete, AssumptionResult<?> takenAssumption) {
 397         assert concrete.isConcrete();
 398         if (checkTargetConditions(invoke, concrete)) {
 399             return new AssumptionInlineInfo(invoke, concrete, takenAssumption);
 400         }
 401         return null;
 402     }
 403 
 404     private InlineInfo getExactInlineInfo(Invoke invoke, ResolvedJavaMethod targetMethod) {
 405         assert targetMethod.isConcrete();
 406         if (checkTargetConditions(invoke, targetMethod)) {
 407             return new ExactInlineInfo(invoke, targetMethod);
 408         }
 409         return null;
 410     }
 411 
 412     @SuppressWarnings("try")
 413     private void doInline(CallsiteHolderExplorable callerCallsiteHolder, MethodInvocation calleeInvocation, String reason) {
 414         StructuredGraph callerGraph = callerCallsiteHolder.graph();
 415         InlineInfo calleeInfo = calleeInvocation.callee();
 416         try {
 417             try (DebugContext.Scope scope = debug.scope("doInline", callerGraph)) {
 418                 EconomicSet<Node> canonicalizedNodes = EconomicSet.create(Equivalence.IDENTITY);
 419                 canonicalizedNodes.addAll(calleeInfo.invoke().asNode().usages());
 420                 EconomicSet<Node> parameterUsages = calleeInfo.inline(new Providers(context), reason);
 421                 canonicalizedNodes.addAll(parameterUsages);
 422                 counterInliningRuns.increment(debug);
 423                 debug.dump(DebugContext.DETAILED_LEVEL, callerGraph, "after %s", calleeInfo);
 424 
 425                 Graph.Mark markBeforeCanonicalization = callerGraph.getMark();
 426 
 427                 canonicalizer.applyIncremental(callerGraph, context, canonicalizedNodes);
 428 
 429                 // process invokes that are possibly created during canonicalization
 430                 for (Node newNode : callerGraph.getNewNodes(markBeforeCanonicalization)) {
 431                     if (newNode instanceof Invoke) {
 432                         callerCallsiteHolder.pushInvoke((Invoke) newNode);
 433                     }
 434                 }
 435 
 436                 callerCallsiteHolder.computeProbabilities();
 437 
 438                 counterInliningPerformed.increment(debug);
 439             }
 440         } catch (BailoutException bailout) {
 441             throw bailout;
 442         } catch (AssertionError | RuntimeException e) {
 443             throw new GraalError(e).addContext(calleeInfo.toString());
 444         } catch (GraalError e) {
 445             throw e.addContext(calleeInfo.toString());
 446         } catch (Throwable e) {
 447             throw debug.handle(e);
 448         }
 449     }
 450 
 451     /**
 452      *
 453      * This method attempts:
 454      * <ol>
 455      * <li>to inline at the callsite given by <code>calleeInvocation</code>, where that callsite
 456      * belongs to the {@link CallsiteHolderExplorable} at the top of the {@link #graphQueue}
 457      * maintained in this class.</li>
 458      * <li>otherwise, to devirtualize the callsite in question.</li>
 459      * </ol>
 460      *
 461      * @return true iff inlining was actually performed
 462      */
 463     private boolean tryToInline(MethodInvocation calleeInvocation, int inliningDepth) {
 464         CallsiteHolderExplorable callerCallsiteHolder = (CallsiteHolderExplorable) currentGraph();
 465         InlineInfo calleeInfo = calleeInvocation.callee();
 466         assert callerCallsiteHolder.containsInvoke(calleeInfo.invoke());
 467         counterInliningConsidered.increment(debug);
 468 
 469         InliningPolicy.Decision decision = inliningPolicy.isWorthInlining(context.getReplacements(), calleeInvocation, inliningDepth, true);
 470         if (decision.shouldInline()) {
 471             doInline(callerCallsiteHolder, calleeInvocation, decision.getReason());
 472             return true;
 473         }
 474 
 475         if (context.getOptimisticOptimizations().devirtualizeInvokes(calleeInfo.graph().getOptions())) {
 476             calleeInfo.tryToDevirtualizeInvoke(new Providers(context));
 477         }
 478 
 479         return false;
 480     }
 481 
 482     /**
 483      * This method picks one of the callsites belonging to the current
 484      * {@link CallsiteHolderExplorable}. Provided the callsite qualifies to be analyzed for
 485      * inlining, this method prepares a new stack top in {@link InliningData} for such callsite,
 486      * which comprises:
 487      * <ul>
 488      * <li>preparing a summary of feasible targets, ie preparing an {@link InlineInfo}</li>
 489      * <li>based on it, preparing the stack top proper which consists of:</li>
 490      * <ul>
 491      * <li>one {@link MethodInvocation}</li>
 492      * <li>a {@link CallsiteHolder} for each feasible target</li>
 493      * </ul>
 494      * </ul>
 495      *
 496      * <p>
 497      * The thus prepared "stack top" is needed by {@link #moveForward()} to explore the space of
 498      * inlining decisions (each decision one of: backtracking, delving, inlining).
 499      * </p>
 500      *
 501      * <p>
 502      * The {@link InlineInfo} used to get things rolling is kept around in the
 503      * {@link MethodInvocation}, it will be needed in case of inlining, see
 504      * {@link InlineInfo#inline(Providers, String)}
 505      * </p>
 506      */
 507     private void processNextInvoke() {
 508         CallsiteHolderExplorable callsiteHolder = (CallsiteHolderExplorable) currentGraph();
 509         Invoke invoke = callsiteHolder.popInvoke();
 510         InlineInfo info = getInlineInfo(invoke);
 511 
 512         if (info != null) {
 513             info.populateInlinableElements(context, currentGraph().graph(), canonicalizer, rootGraph.getOptions());
 514             double invokeProbability = callsiteHolder.invokeProbability(invoke);
 515             double invokeRelevance = callsiteHolder.invokeRelevance(invoke);
 516             MethodInvocation methodInvocation = new MethodInvocation(info, invokeProbability, invokeRelevance, freshlyInstantiatedArguments(invoke, callsiteHolder.getFixedParams()));
 517             pushInvocationAndGraphs(methodInvocation);
 518         }
 519     }
 520 
 521     /**
 522      * Gets the freshly instantiated arguments.
 523      * <p>
 524      * A freshly instantiated argument is either:
 525      * <uL>
 526      * <li>an {@link InliningData#isFreshInstantiation(org.graalvm.compiler.nodes.ValueNode)}</li>
 527      * <li>a fixed-param, ie a {@link ParameterNode} receiving a freshly instantiated argument</li>
 528      * </uL>
 529      * </p>
 530      *
 531      * @return the positions of freshly instantiated arguments in the argument list of the
 532      *         <code>invoke</code>, or null if no such positions exist.
 533      */
 534     public static BitSet freshlyInstantiatedArguments(Invoke invoke, EconomicSet<ParameterNode> fixedParams) {
 535         assert fixedParams != null;
 536         assert paramsAndInvokeAreInSameGraph(invoke, fixedParams);
 537         BitSet result = null;
 538         int argIdx = 0;
 539         for (ValueNode arg : invoke.callTarget().arguments()) {
 540             assert arg != null;
 541             if (isFreshInstantiation(arg) || (arg instanceof ParameterNode && fixedParams.contains((ParameterNode) arg))) {
 542                 if (result == null) {
 543                     result = new BitSet();
 544                 }
 545                 result.set(argIdx);
 546             }
 547             argIdx++;
 548         }
 549         return result;
 550     }
 551 
 552     private static boolean paramsAndInvokeAreInSameGraph(Invoke invoke, EconomicSet<ParameterNode> fixedParams) {
 553         if (fixedParams.isEmpty()) {
 554             return true;
 555         }
 556         for (ParameterNode p : fixedParams) {
 557             if (p.graph() != invoke.asNode().graph()) {
 558                 return false;
 559             }
 560         }
 561         return true;
 562     }
 563 
 564     public int graphCount() {
 565         return graphQueue.size();
 566     }
 567 
 568     public boolean hasUnprocessedGraphs() {
 569         return !graphQueue.isEmpty();
 570     }
 571 
 572     private CallsiteHolder currentGraph() {
 573         return graphQueue.peek();
 574     }
 575 
 576     private void popGraph() {
 577         graphQueue.pop();
 578         assert graphQueue.size() <= maxGraphs;
 579     }
 580 
 581     private void popGraphs(int count) {
 582         assert count >= 0;
 583         for (int i = 0; i < count; i++) {
 584             graphQueue.pop();
 585         }
 586     }
 587 
 588     private static final Object[] NO_CONTEXT = {};
 589 
 590     /**
 591      * Gets the call hierarchy of this inlining from outer most call to inner most callee.
 592      */
 593     private Object[] inliningContext() {
 594         if (!debug.isDumpEnabled(DebugContext.INFO_LEVEL)) {
 595             return NO_CONTEXT;
 596         }
 597         Object[] result = new Object[graphQueue.size()];
 598         int i = 0;
 599         for (CallsiteHolder g : graphQueue) {
 600             result[i++] = g.method();
 601         }
 602         return result;
 603     }
 604 
 605     private MethodInvocation currentInvocation() {
 606         return invocationQueue.peekFirst();
 607     }
 608 
 609     private void pushInvocationAndGraphs(MethodInvocation methodInvocation) {
 610         invocationQueue.addFirst(methodInvocation);
 611         InlineInfo info = methodInvocation.callee();
 612         maxGraphs += info.numberOfMethods();
 613         assert graphQueue.size() <= maxGraphs;
 614         for (int i = 0; i < info.numberOfMethods(); i++) {
 615             CallsiteHolder ch = methodInvocation.buildCallsiteHolderForElement(i);
 616             assert !contains(ch.graph());
 617             graphQueue.push(ch);
 618             assert graphQueue.size() <= maxGraphs;
 619         }
 620     }
 621 
 622     private void popInvocation() {
 623         maxGraphs -= invocationQueue.peekFirst().callee().numberOfMethods();
 624         assert graphQueue.size() <= maxGraphs;
 625         invocationQueue.removeFirst();
 626     }
 627 
 628     public int countRecursiveInlining(ResolvedJavaMethod method) {
 629         int count = 0;
 630         for (CallsiteHolder callsiteHolder : graphQueue) {
 631             if (method.equals(callsiteHolder.method())) {
 632                 count++;
 633             }
 634         }
 635         return count;
 636     }
 637 
 638     public int inliningDepth() {
 639         assert invocationQueue.size() > 0;
 640         return invocationQueue.size() - 1;
 641     }
 642 
 643     @Override
 644     public String toString() {
 645         StringBuilder result = new StringBuilder("Invocations: ");
 646 
 647         for (MethodInvocation invocation : invocationQueue) {
 648             if (invocation.callee() != null) {
 649                 result.append(invocation.callee().numberOfMethods());
 650                 result.append("x ");
 651                 result.append(invocation.callee().invoke());
 652                 result.append("; ");
 653             }
 654         }
 655 
 656         result.append("\nGraphs: ");
 657         for (CallsiteHolder graph : graphQueue) {
 658             result.append(graph.graph());
 659             result.append("; ");
 660         }
 661 
 662         return result.toString();
 663     }
 664 
 665     /**
 666      * Gets a stack trace representing the current inlining stack represented by this object.
 667      */
 668     public Collection<StackTraceElement> getInvocationStackTrace() {
 669         List<StackTraceElement> result = new ArrayList<>();
 670         for (CallsiteHolder graph : graphQueue) {
 671             result.add(graph.method().asStackTraceElement(0));
 672         }
 673 
 674         return result;
 675     }
 676 
 677     private boolean contains(StructuredGraph graph) {
 678         assert graph != null;
 679         for (CallsiteHolder info : graphQueue) {
 680             if (info.graph() == graph) {
 681                 return true;
 682             }
 683         }
 684         return false;
 685     }
 686 
 687     /**
 688      * <p>
 689      * The stack realized by {@link InliningData} grows and shrinks as choices are made among the
 690      * alternatives below:
 691      * <ol>
 692      * <li>not worth inlining: pop stack top, which comprises:
 693      * <ul>
 694      * <li>pop any remaining graphs not yet delved into</li>
 695      * <li>pop the current invocation</li>
 696      * </ul>
 697      * </li>
 698      * <li>{@link #processNextInvoke() delve} into one of the callsites hosted in the current graph,
 699      * such callsite is explored next by {@link #moveForward()}</li>
 700      * <li>{@link #tryToInline(MethodInvocation, int) try to inline}: move past the current graph
 701      * (remove it from the topmost element).
 702      * <ul>
 703      * <li>If that was the last one then {@link #tryToInline(MethodInvocation, int) try to inline}
 704      * the callsite under consideration (ie, the "current invocation").</li>
 705      * <li>Whether inlining occurs or not, that callsite is removed from the top of
 706      * {@link InliningData} .</li>
 707      * </ul>
 708      * </li>
 709      * </ol>
 710      * </p>
 711      *
 712      * <p>
 713      * Some facts about the alternatives above:
 714      * <ul>
 715      * <li>the first step amounts to backtracking, the 2nd one to depth-search, and the 3rd one also
 716      * involves backtracking (however possibly after inlining).</li>
 717      * <li>the choice of abandon-and-backtrack or delve-into depends on
 718      * {@link InliningPolicy#isWorthInlining} and {@link InliningPolicy#continueInlining}.</li>
 719      * <li>the 3rd choice is picked whenever none of the previous choices are made</li>
 720      * </ul>
 721      * </p>
 722      *
 723      * @return true iff inlining was actually performed
 724      */
 725     @SuppressWarnings("try")
 726     public boolean moveForward() {
 727 
 728         final MethodInvocation currentInvocation = currentInvocation();
 729 
 730         final boolean backtrack = (!currentInvocation.isRoot() && !inliningPolicy.isWorthInlining(context.getReplacements(), currentInvocation, inliningDepth(), false).shouldInline());
 731         if (backtrack) {
 732             int remainingGraphs = currentInvocation.totalGraphs() - currentInvocation.processedGraphs();
 733             assert remainingGraphs > 0;
 734             popGraphs(remainingGraphs);
 735             popInvocation();
 736             return false;
 737         }
 738 
 739         final boolean delve = currentGraph().hasRemainingInvokes() && inliningPolicy.continueInlining(currentGraph().graph());
 740         if (delve) {
 741             processNextInvoke();
 742             return false;
 743         }
 744 
 745         popGraph();
 746         if (currentInvocation.isRoot()) {
 747             return false;
 748         }
 749 
 750         // try to inline
 751         assert currentInvocation.callee().invoke().asNode().isAlive();
 752         currentInvocation.incrementProcessedGraphs();
 753         if (currentInvocation.processedGraphs() == currentInvocation.totalGraphs()) {
 754             /*
 755              * "all of currentInvocation's graphs processed" amounts to
 756              * "all concrete methods that come into question already had the callees they contain analyzed for inlining"
 757              */
 758             popInvocation();
 759             try (DebugContext.Scope s = debug.scope("Inlining", inliningContext())) {
 760                 if (tryToInline(currentInvocation, inliningDepth() + 1)) {
 761                     // Report real progress only if we inline into the root graph
 762                     return currentGraph().graph() == rootGraph;
 763                 }
 764                 return false;
 765             } catch (Throwable e) {
 766                 throw debug.handle(e);
 767             }
 768         }
 769 
 770         return false;
 771     }
 772 
 773     /**
 774      * Checks an invariant that {@link #moveForward()} must maintain: "the top invocation records
 775      * how many concrete target methods (for it) remain on the {@link #graphQueue}; those targets
 776      * 'belong' to the current invocation in question.
 777      */
 778     private boolean topGraphsForTopInvocation() {
 779         if (invocationQueue.isEmpty()) {
 780             assert graphQueue.isEmpty();
 781             return true;
 782         }
 783         if (currentInvocation().isRoot()) {
 784             if (!graphQueue.isEmpty()) {
 785                 assert graphQueue.size() == 1;
 786             }
 787             return true;
 788         }
 789         final int remainingGraphs = currentInvocation().totalGraphs() - currentInvocation().processedGraphs();
 790         final Iterator<CallsiteHolder> iter = graphQueue.iterator();
 791         for (int i = (remainingGraphs - 1); i >= 0; i--) {
 792             if (!iter.hasNext()) {
 793                 assert false;
 794                 return false;
 795             }
 796             CallsiteHolder queuedTargetCH = iter.next();
 797             Inlineable targetIE = currentInvocation().callee().inlineableElementAt(i);
 798             InlineableGraph targetIG = (InlineableGraph) targetIE;
 799             assert queuedTargetCH.method().equals(targetIG.getGraph().method());
 800         }
 801         return true;
 802     }
 803 
 804     /**
 805      * This method checks invariants for this class. Named after shorthand for "internal
 806      * representation is ok".
 807      */
 808     public boolean repOK() {
 809         assert topGraphsForTopInvocation();
 810         return true;
 811     }
 812 }