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