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