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