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 && leafConcreteSubtype.canRecordTo(callTarget.graph().getAssumptions())) {
236 return getAssumptionInlineInfo(invoke, resolvedMethod, leafConcreteSubtype);
237 }
238 }
239
240 AssumptionResult<ResolvedJavaMethod> concrete = holder.findUniqueConcreteMethod(targetMethod);
241 if (concrete != null && concrete.canRecordTo(callTarget.graph().getAssumptions())) {
242 return getAssumptionInlineInfo(invoke, concrete.getResult(), concrete);
243 }
244
245 // type check based inlining
246 return getTypeCheckedInlineInfo(invoke, targetMethod);
247 }
248
249 private InlineInfo getTypeCheckedInlineInfo(Invoke invoke, ResolvedJavaMethod targetMethod) {
250 JavaTypeProfile typeProfile = ((MethodCallTargetNode) invoke.callTarget()).getProfile();
251 if (typeProfile == null) {
252 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "no type profile exists");
253 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "no type profile exists");
254 return null;
255 }
256
257 JavaTypeProfile.ProfiledType[] ptypes = typeProfile.getTypes();
258 if (ptypes == null || ptypes.length <= 0) {
259 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "no types in profile");
260 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "no types in profile");
261 return null;
262 }
263 ResolvedJavaType contextType = invoke.getContextType();
264 double notRecordedTypeProbability = typeProfile.getNotRecordedProbability();
265 final OptimisticOptimizations optimisticOpts = context.getOptimisticOptimizations();
266 OptionValues options = invoke.asNode().getOptions();
267 if (ptypes.length == 1 && notRecordedTypeProbability == 0) {
268 if (!optimisticOpts.inlineMonomorphicCalls(options)) {
269 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "inlining monomorphic calls is disabled");
270 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "inlining monomorphic calls is disabled");
271 return null;
272 }
273
274 ResolvedJavaType type = ptypes[0].getType();
275 assert type.isArray() || type.isConcrete();
276 ResolvedJavaMethod concrete = type.resolveConcreteMethod(targetMethod, contextType);
277 if (!checkTargetConditions(invoke, concrete)) {
278 return null;
279 }
280 return new TypeGuardInlineInfo(invoke, concrete, type);
281 } else {
282 invoke.setPolymorphic(true);
283
284 if (!optimisticOpts.inlinePolymorphicCalls(options) && notRecordedTypeProbability == 0) {
285 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "inlining polymorphic calls is disabled (%d types)", ptypes.length);
286 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "inlining polymorphic calls is disabled (%d types)", ptypes.length);
287 return null;
288 }
289 if (!optimisticOpts.inlineMegamorphicCalls(options) && notRecordedTypeProbability > 0) {
290 // due to filtering impossible types, notRecordedTypeProbability can be > 0 although
291 // the number of types is lower than what can be recorded in a type profile
292 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "inlining megamorphic calls is disabled (%d types, %f %% not recorded types)", ptypes.length,
293 notRecordedTypeProbability * 100);
294 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null,
295 "inlining megamorphic calls is disabled (%d types, %f %% not recorded types)", ptypes.length, notRecordedTypeProbability);
296 return null;
297 }
298
299 // Find unique methods and their probabilities.
300 ArrayList<ResolvedJavaMethod> concreteMethods = new ArrayList<>();
301 ArrayList<Double> concreteMethodsProbabilities = new ArrayList<>();
302 for (int i = 0; i < ptypes.length; i++) {
303 ResolvedJavaMethod concrete = ptypes[i].getType().resolveConcreteMethod(targetMethod, contextType);
304 if (concrete == null) {
305 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "could not resolve method");
306 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "could not resolve method");
307 return null;
308 }
309 int index = concreteMethods.indexOf(concrete);
310 double curProbability = ptypes[i].getProbability();
311 if (index < 0) {
312 index = concreteMethods.size();
313 concreteMethods.add(concrete);
314 concreteMethodsProbabilities.add(curProbability);
315 } else {
316 concreteMethodsProbabilities.set(index, concreteMethodsProbabilities.get(index) + curProbability);
317 }
318 }
319
320 // Clear methods that fall below the threshold.
321 if (notRecordedTypeProbability > 0) {
322 ArrayList<ResolvedJavaMethod> newConcreteMethods = new ArrayList<>();
323 ArrayList<Double> newConcreteMethodsProbabilities = new ArrayList<>();
324 for (int i = 0; i < concreteMethods.size(); ++i) {
325 if (concreteMethodsProbabilities.get(i) >= MegamorphicInliningMinMethodProbability.getValue(options)) {
326 newConcreteMethods.add(concreteMethods.get(i));
327 newConcreteMethodsProbabilities.add(concreteMethodsProbabilities.get(i));
328 }
329 }
330
331 if (newConcreteMethods.isEmpty()) {
332 // No method left that is worth inlining.
333 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "no methods remaining after filtering less frequent methods (%d methods previously)",
334 concreteMethods.size());
335 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null,
336 "no methods remaining after filtering less frequent methods (%d methods previously)", concreteMethods.size());
337 return null;
338 }
339
340 concreteMethods = newConcreteMethods;
341 concreteMethodsProbabilities = newConcreteMethodsProbabilities;
342 }
343
344 if (concreteMethods.size() > maxMethodPerInlining) {
345 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "polymorphic call with more than %d target methods", maxMethodPerInlining);
346 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "polymorphic call with more than %d target methods", maxMethodPerInlining);
347 return null;
348 }
349
350 // Clean out types whose methods are no longer available.
351 ArrayList<JavaTypeProfile.ProfiledType> usedTypes = new ArrayList<>();
352 ArrayList<Integer> typesToConcretes = new ArrayList<>();
353 for (JavaTypeProfile.ProfiledType type : ptypes) {
354 ResolvedJavaMethod concrete = type.getType().resolveConcreteMethod(targetMethod, contextType);
355 int index = concreteMethods.indexOf(concrete);
356 if (index == -1) {
357 notRecordedTypeProbability += type.getProbability();
358 } else {
359 assert type.getType().isArray() || !type.getType().isAbstract() : type + " " + concrete;
360 usedTypes.add(type);
361 typesToConcretes.add(index);
362 }
363 }
364
365 if (usedTypes.isEmpty()) {
366 // No type left that is worth checking for.
367 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "no types remaining after filtering less frequent types (%d types previously)", ptypes.length);
368 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null, "no types remaining after filtering less frequent types (%d types previously)",
369 ptypes.length);
370 return null;
371 }
372
373 for (ResolvedJavaMethod concrete : concreteMethods) {
374 if (!checkTargetConditions(invoke, concrete)) {
375 InliningUtil.traceNotInlinedMethod(invoke, inliningDepth(), targetMethod, "it is a polymorphic method call and at least one invoked method cannot be inlined");
376 invoke.asNode().graph().getInliningLog().addDecision(invoke, false, "InliningPhase", null, null,
377 "it is a polymorphic method call and at least one invoked method cannot be inlined");
378 return null;
379 }
380 }
381 return new MultiTypeGuardInlineInfo(invoke, concreteMethods, usedTypes, typesToConcretes, notRecordedTypeProbability);
382 }
383 }
384
385 private InlineInfo getAssumptionInlineInfo(Invoke invoke, ResolvedJavaMethod concrete, AssumptionResult<?> takenAssumption) {
386 assert concrete.isConcrete();
387 if (checkTargetConditions(invoke, concrete)) {
388 return new AssumptionInlineInfo(invoke, concrete, takenAssumption);
389 }
390 return null;
391 }
392
393 private InlineInfo getExactInlineInfo(Invoke invoke, ResolvedJavaMethod targetMethod) {
394 assert targetMethod.isConcrete();
395 if (checkTargetConditions(invoke, targetMethod)) {
396 return new ExactInlineInfo(invoke, targetMethod);
397 }
398 return null;
399 }
400
401 @SuppressWarnings("try")
402 private void doInline(CallsiteHolderExplorable callerCallsiteHolder, MethodInvocation calleeInvocation, String reason) {
403 StructuredGraph callerGraph = callerCallsiteHolder.graph();
404 InlineInfo calleeInfo = calleeInvocation.callee();
405 try {
406 try (DebugContext.Scope scope = debug.scope("doInline", callerGraph)) {
407 EconomicSet<Node> canonicalizedNodes = EconomicSet.create(Equivalence.IDENTITY);
408 canonicalizedNodes.addAll(calleeInfo.invoke().asNode().usages());
409 EconomicSet<Node> parameterUsages = calleeInfo.inline(new Providers(context), reason);
410 canonicalizedNodes.addAll(parameterUsages);
411 counterInliningRuns.increment(debug);
412 debug.dump(DebugContext.DETAILED_LEVEL, callerGraph, "after %s", calleeInfo);
413
414 Graph.Mark markBeforeCanonicalization = callerGraph.getMark();
415
416 canonicalizer.applyIncremental(callerGraph, context, canonicalizedNodes);
417
418 // process invokes that are possibly created during canonicalization
419 for (Node newNode : callerGraph.getNewNodes(markBeforeCanonicalization)) {
420 if (newNode instanceof Invoke) {
421 callerCallsiteHolder.pushInvoke((Invoke) newNode);
422 }
423 }
424
425 callerCallsiteHolder.computeProbabilities();
426
427 counterInliningPerformed.increment(debug);
428 }
429 } catch (BailoutException bailout) {
430 throw bailout;
431 } catch (AssertionError | RuntimeException e) {
432 throw new GraalError(e).addContext(calleeInfo.toString());
433 } catch (GraalError e) {
434 throw e.addContext(calleeInfo.toString());
435 } catch (Throwable e) {
436 throw debug.handle(e);
437 }
438 }
439
440 /**
441 *
442 * This method attempts:
443 * <ol>
444 * <li>to inline at the callsite given by <code>calleeInvocation</code>, where that callsite
445 * belongs to the {@link CallsiteHolderExplorable} at the top of the {@link #graphQueue}
446 * maintained in this class.</li>
447 * <li>otherwise, to devirtualize the callsite in question.</li>
448 * </ol>
449 *
450 * @return true iff inlining was actually performed
451 */
452 private boolean tryToInline(MethodInvocation calleeInvocation, int inliningDepth) {
453 CallsiteHolderExplorable callerCallsiteHolder = (CallsiteHolderExplorable) currentGraph();
454 InlineInfo calleeInfo = calleeInvocation.callee();
455 assert callerCallsiteHolder.containsInvoke(calleeInfo.invoke());
456 counterInliningConsidered.increment(debug);
457
458 InliningPolicy.Decision decision = inliningPolicy.isWorthInlining(context.getReplacements(), calleeInvocation, inliningDepth, true);
459 if (decision.shouldInline()) {
460 doInline(callerCallsiteHolder, calleeInvocation, decision.getReason());
461 return true;
462 }
463
464 if (context.getOptimisticOptimizations().devirtualizeInvokes(calleeInfo.graph().getOptions())) {
465 calleeInfo.tryToDevirtualizeInvoke(new Providers(context));
466 }
467
468 return false;
469 }
470
471 /**
472 * This method picks one of the callsites belonging to the current
473 * {@link CallsiteHolderExplorable}. Provided the callsite qualifies to be analyzed for
474 * inlining, this method prepares a new stack top in {@link InliningData} for such callsite,
475 * which comprises:
476 * <ul>
477 * <li>preparing a summary of feasible targets, ie preparing an {@link InlineInfo}</li>
478 * <li>based on it, preparing the stack top proper which consists of:</li>
479 * <ul>
480 * <li>one {@link MethodInvocation}</li>
481 * <li>a {@link CallsiteHolder} for each feasible target</li>
482 * </ul>
483 * </ul>
484 *
485 * <p>
486 * The thus prepared "stack top" is needed by {@link #moveForward()} to explore the space of
487 * inlining decisions (each decision one of: backtracking, delving, inlining).
488 * </p>
489 *
490 * <p>
491 * The {@link InlineInfo} used to get things rolling is kept around in the
492 * {@link MethodInvocation}, it will be needed in case of inlining, see
493 * {@link InlineInfo#inline(Providers, String)}
494 * </p>
495 */
496 private void processNextInvoke() {
497 CallsiteHolderExplorable callsiteHolder = (CallsiteHolderExplorable) currentGraph();
498 Invoke invoke = callsiteHolder.popInvoke();
499 InlineInfo info = getInlineInfo(invoke);
500
501 if (info != null) {
502 info.populateInlinableElements(context, currentGraph().graph(), canonicalizer, rootGraph.getOptions());
503 double invokeProbability = callsiteHolder.invokeProbability(invoke);
504 double invokeRelevance = callsiteHolder.invokeRelevance(invoke);
505 MethodInvocation methodInvocation = new MethodInvocation(info, invokeProbability, invokeRelevance, freshlyInstantiatedArguments(invoke, callsiteHolder.getFixedParams()));
506 pushInvocationAndGraphs(methodInvocation);
507 }
508 }
509
510 /**
511 * Gets the freshly instantiated arguments.
512 * <p>
513 * A freshly instantiated argument is either:
514 * <uL>
515 * <li>an {@link InliningData#isFreshInstantiation(org.graalvm.compiler.nodes.ValueNode)}</li>
516 * <li>a fixed-param, ie a {@link ParameterNode} receiving a freshly instantiated argument</li>
517 * </uL>
518 * </p>
519 *
520 * @return the positions of freshly instantiated arguments in the argument list of the
521 * <code>invoke</code>, or null if no such positions exist.
522 */
523 public static BitSet freshlyInstantiatedArguments(Invoke invoke, EconomicSet<ParameterNode> fixedParams) {
524 assert fixedParams != null;
525 assert paramsAndInvokeAreInSameGraph(invoke, fixedParams);
526 BitSet result = null;
527 int argIdx = 0;
528 for (ValueNode arg : invoke.callTarget().arguments()) {
529 assert arg != null;
530 if (isFreshInstantiation(arg) || (arg instanceof ParameterNode && fixedParams.contains((ParameterNode) arg))) {
531 if (result == null) {
532 result = new BitSet();
533 }
534 result.set(argIdx);
535 }
536 argIdx++;
537 }
538 return result;
539 }
540
541 private static boolean paramsAndInvokeAreInSameGraph(Invoke invoke, EconomicSet<ParameterNode> fixedParams) {
542 if (fixedParams.isEmpty()) {
543 return true;
544 }
545 for (ParameterNode p : fixedParams) {
546 if (p.graph() != invoke.asNode().graph()) {
547 return false;
548 }
549 }
550 return true;
551 }
552
553 public int graphCount() {
554 return graphQueue.size();
555 }
556
557 public boolean hasUnprocessedGraphs() {
558 return !graphQueue.isEmpty();
559 }
560
561 private CallsiteHolder currentGraph() {
562 return graphQueue.peek();
563 }
564
565 private void popGraph() {
566 graphQueue.pop();
567 assert graphQueue.size() <= maxGraphs;
568 }
569
570 private void popGraphs(int count) {
571 assert count >= 0;
572 for (int i = 0; i < count; i++) {
573 graphQueue.pop();
574 }
575 }
576
577 private static final Object[] NO_CONTEXT = {};
578
579 /**
580 * Gets the call hierarchy of this inlining from outer most call to inner most callee.
581 */
582 private Object[] inliningContext() {
583 if (!debug.isDumpEnabled(DebugContext.INFO_LEVEL)) {
584 return NO_CONTEXT;
585 }
586 Object[] result = new Object[graphQueue.size()];
587 int i = 0;
588 for (CallsiteHolder g : graphQueue) {
589 result[i++] = g.method();
590 }
591 return result;
592 }
593
594 private MethodInvocation currentInvocation() {
595 return invocationQueue.peekFirst();
596 }
597
598 private void pushInvocationAndGraphs(MethodInvocation methodInvocation) {
599 invocationQueue.addFirst(methodInvocation);
600 InlineInfo info = methodInvocation.callee();
601 maxGraphs += info.numberOfMethods();
602 assert graphQueue.size() <= maxGraphs;
603 for (int i = 0; i < info.numberOfMethods(); i++) {
604 CallsiteHolder ch = methodInvocation.buildCallsiteHolderForElement(i);
605 assert !contains(ch.graph());
606 graphQueue.push(ch);
607 assert graphQueue.size() <= maxGraphs;
608 }
609 }
610
611 private void popInvocation() {
612 maxGraphs -= invocationQueue.peekFirst().callee().numberOfMethods();
613 assert graphQueue.size() <= maxGraphs;
614 invocationQueue.removeFirst();
615 }
616
617 public int countRecursiveInlining(ResolvedJavaMethod method) {
618 int count = 0;
619 for (CallsiteHolder callsiteHolder : graphQueue) {
620 if (method.equals(callsiteHolder.method())) {
621 count++;
622 }
623 }
624 return count;
625 }
626
627 public int inliningDepth() {
628 assert invocationQueue.size() > 0;
629 return invocationQueue.size() - 1;
630 }
631
632 @Override
633 public String toString() {
634 StringBuilder result = new StringBuilder("Invocations: ");
635
636 for (MethodInvocation invocation : invocationQueue) {
637 if (invocation.callee() != null) {
638 result.append(invocation.callee().numberOfMethods());
639 result.append("x ");
640 result.append(invocation.callee().invoke());
641 result.append("; ");
642 }
643 }
644
645 result.append("\nGraphs: ");
646 for (CallsiteHolder graph : graphQueue) {
647 result.append(graph.graph());
648 result.append("; ");
649 }
650
651 return result.toString();
652 }
653
654 /**
655 * Gets a stack trace representing the current inlining stack represented by this object.
656 */
657 public Collection<StackTraceElement> getInvocationStackTrace() {
658 List<StackTraceElement> result = new ArrayList<>();
659 for (CallsiteHolder graph : graphQueue) {
660 result.add(graph.method().asStackTraceElement(0));
661 }
662
663 return result;
664 }
665
666 private boolean contains(StructuredGraph graph) {
667 assert graph != null;
668 for (CallsiteHolder info : graphQueue) {
669 if (info.graph() == graph) {
670 return true;
671 }
672 }
673 return false;
674 }
675
676 /**
677 * <p>
678 * The stack realized by {@link InliningData} grows and shrinks as choices are made among the
679 * alternatives below:
680 * <ol>
681 * <li>not worth inlining: pop stack top, which comprises:
682 * <ul>
683 * <li>pop any remaining graphs not yet delved into</li>
684 * <li>pop the current invocation</li>
685 * </ul>
686 * </li>
687 * <li>{@link #processNextInvoke() delve} into one of the callsites hosted in the current graph,
688 * such callsite is explored next by {@link #moveForward()}</li>
689 * <li>{@link #tryToInline(MethodInvocation, int) try to inline}: move past the current graph
690 * (remove it from the topmost element).
691 * <ul>
692 * <li>If that was the last one then {@link #tryToInline(MethodInvocation, int) try to inline}
693 * the callsite under consideration (ie, the "current invocation").</li>
694 * <li>Whether inlining occurs or not, that callsite is removed from the top of
695 * {@link InliningData} .</li>
696 * </ul>
697 * </li>
698 * </ol>
699 * </p>
700 *
701 * <p>
702 * Some facts about the alternatives above:
703 * <ul>
704 * <li>the first step amounts to backtracking, the 2nd one to depth-search, and the 3rd one also
705 * involves backtracking (however possibly after inlining).</li>
706 * <li>the choice of abandon-and-backtrack or delve-into depends on
707 * {@link InliningPolicy#isWorthInlining} and {@link InliningPolicy#continueInlining}.</li>
708 * <li>the 3rd choice is picked whenever none of the previous choices are made</li>
709 * </ul>
710 * </p>
711 *
712 * @return true iff inlining was actually performed
713 */
714 @SuppressWarnings("try")
715 public boolean moveForward() {
716
717 final MethodInvocation currentInvocation = currentInvocation();
718
719 final boolean backtrack = (!currentInvocation.isRoot() && !inliningPolicy.isWorthInlining(context.getReplacements(), currentInvocation, inliningDepth(), false).shouldInline());
720 if (backtrack) {
721 int remainingGraphs = currentInvocation.totalGraphs() - currentInvocation.processedGraphs();
722 assert remainingGraphs > 0;
723 popGraphs(remainingGraphs);
724 popInvocation();
725 return false;
726 }
727
728 final boolean delve = currentGraph().hasRemainingInvokes() && inliningPolicy.continueInlining(currentGraph().graph());
729 if (delve) {
730 processNextInvoke();
731 return false;
732 }
733
734 popGraph();
735 if (currentInvocation.isRoot()) {
736 return false;
737 }
738
739 // try to inline
740 assert currentInvocation.callee().invoke().asNode().isAlive();
741 currentInvocation.incrementProcessedGraphs();
742 if (currentInvocation.processedGraphs() == currentInvocation.totalGraphs()) {
743 /*
744 * "all of currentInvocation's graphs processed" amounts to
745 * "all concrete methods that come into question already had the callees they contain analyzed for inlining"
746 */
747 popInvocation();
748 try (DebugContext.Scope s = debug.scope("Inlining", inliningContext())) {
749 if (tryToInline(currentInvocation, inliningDepth() + 1)) {
750 // Report real progress only if we inline into the root graph
751 return currentGraph().graph() == rootGraph;
752 }
753 return false;
754 } catch (Throwable e) {
755 throw debug.handle(e);
756 }
757 }
758
759 return false;
760 }
761
762 /**
763 * Checks an invariant that {@link #moveForward()} must maintain: "the top invocation records
764 * how many concrete target methods (for it) remain on the {@link #graphQueue}; those targets
765 * 'belong' to the current invocation in question.
766 */
767 private boolean topGraphsForTopInvocation() {
768 if (invocationQueue.isEmpty()) {
769 assert graphQueue.isEmpty();
770 return true;
771 }
772 if (currentInvocation().isRoot()) {
773 if (!graphQueue.isEmpty()) {
774 assert graphQueue.size() == 1;
775 }
776 return true;
777 }
778 final int remainingGraphs = currentInvocation().totalGraphs() - currentInvocation().processedGraphs();
779 final Iterator<CallsiteHolder> iter = graphQueue.iterator();
780 for (int i = (remainingGraphs - 1); i >= 0; i--) {
781 if (!iter.hasNext()) {
782 assert false;
783 return false;
784 }
785 CallsiteHolder queuedTargetCH = iter.next();
786 Inlineable targetIE = currentInvocation().callee().inlineableElementAt(i);
787 InlineableGraph targetIG = (InlineableGraph) targetIE;
788 assert queuedTargetCH.method().equals(targetIG.getGraph().method());
789 }
790 return true;
791 }
792
793 /**
794 * This method checks invariants for this class. Named after shorthand for "internal
795 * representation is ok".
796 */
797 public boolean repOK() {
798 assert topGraphsForTopInvocation();
799 return true;
800 }
801 }