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