1 /* 2 * Copyright (c) 2011, 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 com.oracle.graal.phases.common; 24 25 import static com.oracle.graal.phases.GraalOptions.*; 26 import static com.oracle.graal.phases.common.InliningPhase.Options.*; 27 28 import java.util.*; 29 import java.util.concurrent.*; 30 31 import com.oracle.graal.api.code.*; 32 import com.oracle.graal.api.meta.*; 33 import com.oracle.graal.debug.*; 34 import com.oracle.graal.graph.*; 35 import com.oracle.graal.nodes.*; 36 import com.oracle.graal.nodes.java.*; 37 import com.oracle.graal.nodes.spi.*; 38 import com.oracle.graal.nodes.type.*; 39 import com.oracle.graal.nodes.util.*; 40 import com.oracle.graal.options.*; 41 import com.oracle.graal.phases.*; 42 import com.oracle.graal.phases.PhasePlan.PhasePosition; 43 import com.oracle.graal.phases.common.CanonicalizerPhase.CustomCanonicalizer; 44 import com.oracle.graal.phases.common.InliningUtil.InlineInfo; 45 import com.oracle.graal.phases.common.InliningUtil.Inlineable; 46 import com.oracle.graal.phases.common.InliningUtil.InlineableMacroNode; 47 import com.oracle.graal.phases.common.InliningUtil.InlineableGraph; 48 import com.oracle.graal.phases.common.InliningUtil.InliningPolicy; 49 import com.oracle.graal.phases.graph.*; 50 51 public class InliningPhase extends Phase { 52 53 static class Options { 54 55 // @formatter:off 56 @Option(help = "Unconditionally inline intrinsics") 57 public static final OptionValue<Boolean> AlwaysInlineIntrinsics = new OptionValue<>(false); 58 // @formatter:on 59 } 60 61 private final PhasePlan plan; 62 private final MetaAccessProvider runtime; 63 private final Assumptions compilationAssumptions; 64 private final Replacements replacements; 65 private final GraphCache cache; 66 private final InliningPolicy inliningPolicy; 67 private final OptimisticOptimizations optimisticOpts; 68 69 private CustomCanonicalizer customCanonicalizer; 70 private int inliningCount; 71 private int maxMethodPerInlining = Integer.MAX_VALUE; 72 73 // Metrics 74 private static final DebugMetric metricInliningPerformed = Debug.metric("InliningPerformed"); 75 private static final DebugMetric metricInliningConsidered = Debug.metric("InliningConsidered"); 76 private static final DebugMetric metricInliningStoppedByMaxDesiredSize = Debug.metric("InliningStoppedByMaxDesiredSize"); 77 private static final DebugMetric metricInliningRuns = Debug.metric("Runs"); 78 79 public InliningPhase(MetaAccessProvider runtime, Map<Invoke, Double> hints, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, 80 OptimisticOptimizations optimisticOpts) { 81 this(runtime, replacements, assumptions, cache, plan, optimisticOpts, hints); 82 } 83 84 private InliningPhase(MetaAccessProvider runtime, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts, 85 Map<Invoke, Double> hints) { 86 this.runtime = runtime; 87 this.replacements = replacements; 88 this.compilationAssumptions = assumptions; 89 this.cache = cache; 90 this.plan = plan; 91 this.inliningPolicy = new GreedyInliningPolicy(replacements, hints); 92 this.optimisticOpts = optimisticOpts; 93 } 94 95 public InliningPhase(MetaAccessProvider runtime, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts, InliningPolicy policy) { 96 this.runtime = runtime; 97 this.replacements = replacements; 98 this.compilationAssumptions = assumptions; 99 this.cache = cache; 100 this.plan = plan; 101 this.inliningPolicy = policy; 102 this.optimisticOpts = optimisticOpts; 103 } 104 105 public void setCustomCanonicalizer(CustomCanonicalizer customCanonicalizer) { 106 this.customCanonicalizer = customCanonicalizer; 107 } 108 109 public void setMaxMethodsPerInlining(int max) { 110 maxMethodPerInlining = max; 111 } 112 113 public int getInliningCount() { 114 return inliningCount; 115 } 116 117 public static void storeStatisticsAfterLowTier(StructuredGraph graph) { 118 ResolvedJavaMethod method = graph.method(); 119 if (method != null) { 120 CompiledMethodInfo info = compiledMethodInfo(graph.method()); 121 info.setLowLevelNodeCount(graph.getNodeCount()); 122 } 123 } 124 125 @Override 126 protected void run(final StructuredGraph graph) { 127 final InliningData data = new InliningData(graph, compilationAssumptions); 128 129 while (data.hasUnprocessedGraphs()) { 130 final MethodInvocation currentInvocation = data.currentInvocation(); 131 GraphInfo graphInfo = data.currentGraph(); 132 if (!currentInvocation.isRoot() && !inliningPolicy.isWorthInlining(currentInvocation.callee(), data.inliningDepth(), currentInvocation.probability(), currentInvocation.relevance(), false)) { 133 int remainingGraphs = currentInvocation.totalGraphs() - currentInvocation.processedGraphs(); 134 assert remainingGraphs > 0; 135 data.popGraphs(remainingGraphs); 136 data.popInvocation(); 137 } else if (graphInfo.hasRemainingInvokes() && inliningPolicy.continueInlining(graphInfo.graph())) { 138 processNextInvoke(data, graphInfo); 139 } else { 140 data.popGraph(); 141 if (!currentInvocation.isRoot()) { 142 assert currentInvocation.callee().invoke().asNode().isAlive(); 143 currentInvocation.incrementProcessedGraphs(); 144 if (currentInvocation.processedGraphs() == currentInvocation.totalGraphs()) { 145 data.popInvocation(); 146 final MethodInvocation parentInvoke = data.currentInvocation(); 147 Debug.scope("Inlining", data.inliningContext(), new Runnable() { 148 149 @Override 150 public void run() { 151 tryToInline(data.currentGraph(), currentInvocation, parentInvoke, data.inliningDepth() + 1); 152 } 153 }); 154 155 } 156 } 157 } 158 } 159 160 assert data.inliningDepth() == 0; 161 assert data.graphCount() == 0; 162 } 163 164 /** 165 * Process the next invoke and enqueue all its graphs for processing. 166 */ 167 private void processNextInvoke(InliningData data, GraphInfo graphInfo) { 168 Invoke invoke = graphInfo.popInvoke(); 169 MethodInvocation callerInvocation = data.currentInvocation(); 170 Assumptions parentAssumptions = callerInvocation.assumptions(); 171 InlineInfo info = InliningUtil.getInlineInfo(data, invoke, maxMethodPerInlining, replacements, parentAssumptions, optimisticOpts); 172 173 if (info != null) { 174 double invokeProbability = graphInfo.invokeProbability(invoke); 175 double invokeRelevance = graphInfo.invokeRelevance(invoke); 176 MethodInvocation calleeInvocation = data.pushInvocation(info, parentAssumptions, invokeProbability, invokeRelevance); 177 178 for (int i = 0; i < info.numberOfMethods(); i++) { 179 Inlineable elem = getInlineableElement(info.methodAt(i), info.invoke(), calleeInvocation.assumptions()); 180 info.setInlinableElement(i, elem); 181 if (elem instanceof InlineableGraph) { 182 data.pushGraph(((InlineableGraph) elem).getGraph(), invokeProbability * info.probabilityAt(i), invokeRelevance * info.relevanceAt(i)); 183 } else { 184 assert elem instanceof InlineableMacroNode; 185 data.pushDummyGraph(); 186 } 187 } 188 } 189 } 190 191 private void tryToInline(GraphInfo callerGraphInfo, MethodInvocation calleeInfo, MethodInvocation parentInvocation, int inliningDepth) { 192 InlineInfo callee = calleeInfo.callee(); 193 Assumptions callerAssumptions = parentInvocation.assumptions(); 194 195 if (inliningPolicy.isWorthInlining(callee, inliningDepth, calleeInfo.probability(), calleeInfo.relevance(), true)) { 196 doInline(callerGraphInfo, calleeInfo, callerAssumptions); 197 } else if (optimisticOpts.devirtualizeInvokes()) { 198 callee.tryToDevirtualizeInvoke(runtime, callerAssumptions); 199 } 200 metricInliningConsidered.increment(); 201 } 202 203 private void doInline(GraphInfo callerGraphInfo, MethodInvocation calleeInfo, Assumptions callerAssumptions) { 204 StructuredGraph callerGraph = callerGraphInfo.graph(); 205 int markBeforeInlining = callerGraph.getMark(); 206 InlineInfo callee = calleeInfo.callee(); 207 try { 208 List<Node> invokeUsages = callee.invoke().asNode().usages().snapshot(); 209 callee.inline(runtime, callerAssumptions, replacements); 210 callerAssumptions.record(calleeInfo.assumptions()); 211 metricInliningRuns.increment(); 212 Debug.dump(callerGraph, "after %s", callee); 213 214 if (OptCanonicalizer.getValue()) { 215 int markBeforeCanonicalization = callerGraph.getMark(); 216 new CanonicalizerPhase.Instance(runtime, callerAssumptions, !AOTCompilation.getValue(), invokeUsages, markBeforeInlining, customCanonicalizer).apply(callerGraph); 217 218 // process invokes that are possibly created during canonicalization 219 for (Node newNode : callerGraph.getNewNodes(markBeforeCanonicalization)) { 220 if (newNode instanceof Invoke) { 221 callerGraphInfo.pushInvoke((Invoke) newNode); 222 } 223 } 224 } 225 226 callerGraphInfo.computeProbabilities(); 227 228 inliningCount++; 229 metricInliningPerformed.increment(); 230 } catch (BailoutException bailout) { 231 throw bailout; 232 } catch (AssertionError | RuntimeException e) { 233 throw new GraalInternalError(e).addContext(callee.toString()); 234 } catch (GraalInternalError e) { 235 throw e.addContext(callee.toString()); 236 } 237 } 238 239 private Inlineable getInlineableElement(final ResolvedJavaMethod method, Invoke invoke, Assumptions assumptions) { 240 Class<? extends FixedWithNextNode> macroNodeClass = InliningUtil.getMacroNodeClass(replacements, method); 241 if (macroNodeClass != null) { 242 return new InlineableMacroNode(macroNodeClass); 243 } else { 244 return new InlineableGraph(buildGraph(method, invoke, assumptions)); 245 } 246 } 247 248 private StructuredGraph buildGraph(final ResolvedJavaMethod method, final Invoke invoke, final Assumptions assumptions) { 249 final StructuredGraph newGraph; 250 final boolean parseBytecodes; 251 252 // TODO (chaeubl): copying the graph is only necessary if it is modified or if it contains 253 // any invokes 254 StructuredGraph intrinsicGraph = InliningUtil.getIntrinsicGraph(replacements, method); 255 if (intrinsicGraph != null) { 256 newGraph = intrinsicGraph.copy(); 257 parseBytecodes = false; 258 } else { 259 StructuredGraph cachedGraph = getCachedGraph(method); 260 if (cachedGraph != null) { 261 newGraph = cachedGraph.copy(); 262 parseBytecodes = false; 263 } else { 264 newGraph = new StructuredGraph(method); 265 parseBytecodes = true; 266 } 267 } 268 269 return Debug.scope("InlineGraph", newGraph, new Callable<StructuredGraph>() { 270 271 @Override 272 public StructuredGraph call() throws Exception { 273 if (parseBytecodes) { 274 parseBytecodes(newGraph, assumptions); 275 } 276 277 boolean callerHasMoreInformationAboutArguments = false; 278 NodeInputList<ValueNode> args = invoke.callTarget().arguments(); 279 for (LocalNode localNode : newGraph.getNodes(LocalNode.class).snapshot()) { 280 ValueNode arg = args.get(localNode.index()); 281 if (arg.isConstant()) { 282 Constant constant = arg.asConstant(); 283 newGraph.replaceFloating(localNode, ConstantNode.forConstant(constant, runtime, newGraph)); 284 callerHasMoreInformationAboutArguments = true; 285 } else { 286 Stamp joinedStamp = localNode.stamp().join(arg.stamp()); 287 if (joinedStamp != null && !joinedStamp.equals(localNode.stamp())) { 288 localNode.setStamp(joinedStamp); 289 callerHasMoreInformationAboutArguments = true; 290 } 291 } 292 } 293 294 if (!callerHasMoreInformationAboutArguments) { 295 // TODO (chaeubl): if args are not more concrete, inlining should be avoided 296 // in most cases or we could at least use the previous graph size + invoke 297 // probability to check the inlining 298 } 299 300 if (OptCanonicalizer.getValue()) { 301 new CanonicalizerPhase.Instance(runtime, assumptions, !AOTCompilation.getValue()).apply(newGraph); 302 } 303 304 return newGraph; 305 } 306 }); 307 } 308 309 private StructuredGraph getCachedGraph(ResolvedJavaMethod method) { 310 if (CacheGraphs.getValue() && cache != null) { 311 StructuredGraph cachedGraph = cache.get(method); 312 if (cachedGraph != null) { 313 return cachedGraph; 314 } 315 } 316 return null; 317 } 318 319 private StructuredGraph parseBytecodes(StructuredGraph newGraph, Assumptions assumptions) { 320 boolean hasMatureProfilingInfo = newGraph.method().getProfilingInfo().isMature(); 321 322 if (plan != null) { 323 plan.runPhases(PhasePosition.AFTER_PARSING, newGraph); 324 } 325 assert newGraph.start().next() != null : "graph needs to be populated during PhasePosition.AFTER_PARSING"; 326 327 new DeadCodeEliminationPhase().apply(newGraph); 328 329 if (OptCanonicalizer.getValue()) { 330 new CanonicalizerPhase.Instance(runtime, assumptions, !AOTCompilation.getValue()).apply(newGraph); 331 } 332 333 if (CacheGraphs.getValue() && cache != null) { 334 cache.put(newGraph.copy(), hasMatureProfilingInfo); 335 } 336 return newGraph; 337 } 338 339 private static synchronized CompiledMethodInfo compiledMethodInfo(ResolvedJavaMethod m) { 340 CompiledMethodInfo info = (CompiledMethodInfo) m.getCompilerStorage().get(CompiledMethodInfo.class); 341 if (info == null) { 342 info = new CompiledMethodInfo(); 343 m.getCompilerStorage().put(CompiledMethodInfo.class, info); 344 } 345 return info; 346 } 347 348 private abstract static class AbstractInliningPolicy implements InliningPolicy { 349 350 protected final Replacements replacements; 351 protected final Map<Invoke, Double> hints; 352 353 public AbstractInliningPolicy(Replacements replacements, Map<Invoke, Double> hints) { 354 this.replacements = replacements; 355 this.hints = hints; 356 } 357 358 protected double computeMaximumSize(double relevance, int configuredMaximum) { 359 double inlineRatio = Math.min(RelevanceCapForInlining.getValue(), relevance); 360 return configuredMaximum * inlineRatio; 361 } 362 363 protected double getInliningBonus(InlineInfo info) { 364 if (hints != null && hints.containsKey(info.invoke())) { 365 return hints.get(info.invoke()); 366 } 367 return 1; 368 } 369 370 protected boolean isIntrinsic(InlineInfo info) { 371 if (AlwaysInlineIntrinsics.getValue()) { 372 return onlyIntrinsics(info); 373 } else { 374 return onlyForcedIntrinsics(info); 375 } 376 } 377 378 private boolean onlyIntrinsics(InlineInfo info) { 379 for (int i = 0; i < info.numberOfMethods(); i++) { 380 if (!InliningUtil.canIntrinsify(replacements, info.methodAt(i))) { 381 return false; 382 } 383 } 384 return true; 385 } 386 387 private boolean onlyForcedIntrinsics(InlineInfo info) { 388 for (int i = 0; i < info.numberOfMethods(); i++) { 389 if (!InliningUtil.canIntrinsify(replacements, info.methodAt(i))) { 390 return false; 391 } 392 if (!replacements.isForcedSubstitution(info.methodAt(i))) { 393 return false; 394 } 395 } 396 return true; 397 } 398 399 protected static int previousLowLevelGraphSize(InlineInfo info) { 400 int size = 0; 401 for (int i = 0; i < info.numberOfMethods(); i++) { 402 size += compiledMethodInfo(info.methodAt(i)).lowLevelNodeCount(); 403 } 404 return size; 405 } 406 407 protected static int determineNodeCount(InlineInfo info) { 408 int nodes = 0; 409 for (int i = 0; i < info.numberOfMethods(); i++) { 410 Inlineable elem = info.inlineableElementAt(i); 411 if (elem != null) { 412 nodes += elem.getNodeCount(); 413 } 414 } 415 return nodes; 416 } 417 418 protected static double determineInvokeProbability(InlineInfo info) { 419 double invokeProbability = 0; 420 for (int i = 0; i < info.numberOfMethods(); i++) { 421 Inlineable callee = info.inlineableElementAt(i); 422 Iterable<Invoke> invokes = callee.getInvokes(); 423 if (invokes.iterator().hasNext()) { 424 NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(((InlineableGraph) callee).getGraph()).apply(); 425 for (Invoke invoke : invokes) { 426 invokeProbability += nodeProbabilities.get(invoke.asNode()); 427 } 428 } 429 } 430 return invokeProbability; 431 } 432 } 433 434 private static final class GreedyInliningPolicy extends AbstractInliningPolicy { 435 436 public GreedyInliningPolicy(Replacements replacements, Map<Invoke, Double> hints) { 437 super(replacements, hints); 438 } 439 440 public boolean continueInlining(StructuredGraph currentGraph) { 441 if (currentGraph.getNodeCount() >= MaximumDesiredSize.getValue()) { 442 InliningUtil.logInliningDecision("inlining is cut off by MaximumDesiredSize"); 443 metricInliningStoppedByMaxDesiredSize.increment(); 444 return false; 445 } 446 return true; 447 } 448 449 @Override 450 public boolean isWorthInlining(InlineInfo info, int inliningDepth, double probability, double relevance, boolean fullyProcessed) { 451 if (InlineEverything.getValue()) { 452 return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "inline everything"); 453 } 454 455 if (isIntrinsic(info)) { 456 return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "intrinsic"); 457 } 458 459 double inliningBonus = getInliningBonus(info); 460 int nodes = determineNodeCount(info); 461 int lowLevelGraphSize = previousLowLevelGraphSize(info); 462 463 if (SmallCompiledLowLevelGraphSize.getValue() > 0 && lowLevelGraphSize > SmallCompiledLowLevelGraphSize.getValue() * inliningBonus) { 464 return InliningUtil.logNotInlinedMethod(info, inliningDepth, "too large previous low-level graph (low-level-nodes: %d, relevance=%f, probability=%f, bonus=%f, nodes=%d)", 465 lowLevelGraphSize, relevance, probability, inliningBonus, nodes); 466 } 467 468 if (nodes < TrivialInliningSize.getValue() * inliningBonus) { 469 return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "trivial (relevance=%f, probability=%f, bonus=%f, nodes=%d)", relevance, probability, inliningBonus, nodes); 470 } 471 472 /* 473 * TODO (chaeubl): invoked methods that are on important paths but not yet compiled -> 474 * will be compiled anyways and it is likely that we are the only caller... might be 475 * useful to inline those methods but increases bootstrap time (maybe those methods are 476 * also getting queued in the compilation queue concurrently) 477 */ 478 double invokes = determineInvokeProbability(info); 479 if (LimitInlinedInvokes.getValue() > 0 && fullyProcessed && invokes > LimitInlinedInvokes.getValue() * inliningBonus) { 480 return InliningUtil.logNotInlinedMethod(info, inliningDepth, "callee invoke probability is too high (invokeP=%f, relevance=%f, probability=%f, bonus=%f, nodes=%d)", invokes, 481 relevance, probability, inliningBonus, nodes); 482 } 483 484 double maximumNodes = computeMaximumSize(relevance, (int) (MaximumInliningSize.getValue() * inliningBonus)); 485 if (nodes <= maximumNodes) { 486 return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "relevance-based (relevance=%f, probability=%f, bonus=%f, nodes=%d <= %f)", relevance, probability, 487 inliningBonus, nodes, maximumNodes); 488 } 489 490 return InliningUtil.logNotInlinedMethod(info, inliningDepth, "relevance-based (relevance=%f, probability=%f, bonus=%f, nodes=%d > %f)", relevance, probability, inliningBonus, nodes, 491 maximumNodes); 492 } 493 } 494 495 public static final class InlineEverythingPolicy implements InliningPolicy { 496 497 public boolean continueInlining(StructuredGraph graph) { 498 if (graph.getNodeCount() >= MaximumDesiredSize.getValue()) { 499 throw new BailoutException("Inline all calls failed. The resulting graph is too large."); 500 } 501 return true; 502 } 503 504 public boolean isWorthInlining(InlineInfo info, int inliningDepth, double probability, double relevance, boolean fullyProcessed) { 505 return true; 506 } 507 } 508 509 private static class InliningIterator { 510 511 private final FixedNode start; 512 private final Deque<FixedNode> nodeQueue; 513 private final NodeBitMap queuedNodes; 514 515 public InliningIterator(FixedNode start, NodeBitMap visitedFixedNodes) { 516 this.start = start; 517 this.nodeQueue = new ArrayDeque<>(); 518 this.queuedNodes = visitedFixedNodes; 519 assert start.isAlive(); 520 } 521 522 public LinkedList<Invoke> apply() { 523 LinkedList<Invoke> invokes = new LinkedList<>(); 524 FixedNode current; 525 forcedQueue(start); 526 527 while ((current = nextQueuedNode()) != null) { 528 assert current.isAlive(); 529 530 if (current instanceof Invoke) { 531 if (current != start) { 532 invokes.addLast((Invoke) current); 533 } 534 queueSuccessors(current); 535 } else if (current instanceof LoopBeginNode) { 536 queueSuccessors(current); 537 } else if (current instanceof LoopEndNode) { 538 // nothing todo 539 } else if (current instanceof MergeNode) { 540 queueSuccessors(current); 541 } else if (current instanceof FixedWithNextNode) { 542 queueSuccessors(current); 543 } else if (current instanceof EndNode) { 544 queueMerge((EndNode) current); 545 } else if (current instanceof ControlSinkNode) { 546 // nothing todo 547 } else if (current instanceof ControlSplitNode) { 548 queueSuccessors(current); 549 } else { 550 assert false : current; 551 } 552 } 553 554 return invokes; 555 } 556 557 private void queueSuccessors(FixedNode x) { 558 for (Node node : x.successors()) { 559 queue(node); 560 } 561 } 562 563 private void queue(Node node) { 564 if (node != null && !queuedNodes.isMarked(node)) { 565 forcedQueue(node); 566 } 567 } 568 569 private void forcedQueue(Node node) { 570 queuedNodes.mark(node); 571 nodeQueue.addFirst((FixedNode) node); 572 } 573 574 private FixedNode nextQueuedNode() { 575 if (nodeQueue.isEmpty()) { 576 return null; 577 } 578 579 FixedNode result = nodeQueue.removeFirst(); 580 assert queuedNodes.isMarked(result); 581 return result; 582 } 583 584 private void queueMerge(AbstractEndNode end) { 585 MergeNode merge = end.merge(); 586 if (!queuedNodes.isMarked(merge) && visitedAllEnds(merge)) { 587 queuedNodes.mark(merge); 588 nodeQueue.add(merge); 589 } 590 } 591 592 private boolean visitedAllEnds(MergeNode merge) { 593 for (int i = 0; i < merge.forwardEndCount(); i++) { 594 if (!queuedNodes.isMarked(merge.forwardEndAt(i))) { 595 return false; 596 } 597 } 598 return true; 599 } 600 } 601 602 /** 603 * Holds the data for building the callee graphs recursively: graphs and invocations (each 604 * invocation can have multiple graphs). 605 */ 606 static class InliningData { 607 608 private static final GraphInfo DummyGraphInfo = new GraphInfo(null, new LinkedList<Invoke>(), 1.0, 1.0); 609 610 /** 611 * Call hierarchy from outer most call (i.e., compilation unit) to inner most callee. 612 */ 613 private final ArrayDeque<GraphInfo> graphQueue; 614 private final ArrayDeque<MethodInvocation> invocationQueue; 615 616 private int maxGraphs; 617 618 public InliningData(StructuredGraph rootGraph, Assumptions rootAssumptions) { 619 this.graphQueue = new ArrayDeque<>(); 620 this.invocationQueue = new ArrayDeque<>(); 621 this.maxGraphs = 1; 622 623 invocationQueue.push(new MethodInvocation(null, rootAssumptions, 1.0, 1.0)); 624 pushGraph(rootGraph, 1.0, 1.0); 625 } 626 627 public int graphCount() { 628 return graphQueue.size(); 629 } 630 631 public void pushGraph(StructuredGraph graph, double probability, double relevance) { 632 assert !contains(graph); 633 NodeBitMap visitedFixedNodes = graph.createNodeBitMap(); 634 LinkedList<Invoke> invokes = new InliningIterator(graph.start(), visitedFixedNodes).apply(); 635 assert invokes.size() == count(graph.getInvokes()); 636 graphQueue.push(new GraphInfo(graph, invokes, probability, relevance)); 637 assert graphQueue.size() <= maxGraphs; 638 } 639 640 public void pushDummyGraph() { 641 graphQueue.push(DummyGraphInfo); 642 } 643 644 public boolean hasUnprocessedGraphs() { 645 return !graphQueue.isEmpty(); 646 } 647 648 public GraphInfo currentGraph() { 649 return graphQueue.peek(); 650 } 651 652 public void popGraph() { 653 graphQueue.pop(); 654 assert graphQueue.size() <= maxGraphs; 655 } 656 657 public void popGraphs(int count) { 658 assert count >= 0; 659 for (int i = 0; i < count; i++) { 660 graphQueue.pop(); 661 } 662 } 663 664 /** 665 * Gets the call hierarchy of this inling from outer most call to inner most callee. 666 */ 667 public Object[] inliningContext() { 668 Object[] result = new Object[graphQueue.size()]; 669 int i = 0; 670 for (GraphInfo g : graphQueue) { 671 result[i++] = g.graph.method(); 672 } 673 return result; 674 } 675 676 public MethodInvocation currentInvocation() { 677 return invocationQueue.peek(); 678 } 679 680 public MethodInvocation pushInvocation(InlineInfo info, Assumptions assumptions, double probability, double relevance) { 681 MethodInvocation methodInvocation = new MethodInvocation(info, new Assumptions(assumptions.useOptimisticAssumptions()), probability, relevance); 682 invocationQueue.push(methodInvocation); 683 maxGraphs += info.numberOfMethods(); 684 assert graphQueue.size() <= maxGraphs; 685 return methodInvocation; 686 } 687 688 public void popInvocation() { 689 maxGraphs -= invocationQueue.peek().callee.numberOfMethods(); 690 assert graphQueue.size() <= maxGraphs; 691 invocationQueue.pop(); 692 } 693 694 public int countRecursiveInlining(ResolvedJavaMethod method) { 695 int count = 0; 696 for (GraphInfo graphInfo : graphQueue) { 697 if (method.equals(graphInfo.method())) { 698 count++; 699 } 700 } 701 return count; 702 } 703 704 public int inliningDepth() { 705 assert invocationQueue.size() > 0; 706 return invocationQueue.size() - 1; 707 } 708 709 @Override 710 public String toString() { 711 StringBuilder result = new StringBuilder("Invocations: "); 712 713 for (MethodInvocation invocation : invocationQueue) { 714 if (invocation.callee() != null) { 715 result.append(invocation.callee().numberOfMethods()); 716 result.append("x "); 717 result.append(invocation.callee().invoke()); 718 result.append("; "); 719 } 720 } 721 722 result.append("\nGraphs: "); 723 for (GraphInfo graph : graphQueue) { 724 result.append(graph.graph()); 725 result.append("; "); 726 } 727 728 return result.toString(); 729 } 730 731 private boolean contains(StructuredGraph graph) { 732 for (GraphInfo info : graphQueue) { 733 if (info.graph() == graph) { 734 return true; 735 } 736 } 737 return false; 738 } 739 740 private static int count(Iterable<Invoke> invokes) { 741 int count = 0; 742 Iterator<Invoke> iterator = invokes.iterator(); 743 while (iterator.hasNext()) { 744 iterator.next(); 745 count++; 746 } 747 return count; 748 } 749 } 750 751 private static class MethodInvocation { 752 753 private final InlineInfo callee; 754 private final Assumptions assumptions; 755 private final double probability; 756 private final double relevance; 757 758 private int processedGraphs; 759 760 public MethodInvocation(InlineInfo info, Assumptions assumptions, double probability, double relevance) { 761 this.callee = info; 762 this.assumptions = assumptions; 763 this.probability = probability; 764 this.relevance = relevance; 765 } 766 767 public void incrementProcessedGraphs() { 768 processedGraphs++; 769 assert processedGraphs <= callee.numberOfMethods(); 770 } 771 772 public int processedGraphs() { 773 assert processedGraphs <= callee.numberOfMethods(); 774 return processedGraphs; 775 } 776 777 public int totalGraphs() { 778 return callee.numberOfMethods(); 779 } 780 781 public InlineInfo callee() { 782 return callee; 783 } 784 785 public Assumptions assumptions() { 786 return assumptions; 787 } 788 789 public double probability() { 790 return probability; 791 } 792 793 public double relevance() { 794 return relevance; 795 } 796 797 public boolean isRoot() { 798 return callee == null; 799 } 800 801 @Override 802 public String toString() { 803 if (isRoot()) { 804 return "<root>"; 805 } 806 CallTargetNode callTarget = callee.invoke().callTarget(); 807 if (callTarget instanceof MethodCallTargetNode) { 808 ResolvedJavaMethod calleeMethod = ((MethodCallTargetNode) callTarget).targetMethod(); 809 return MetaUtil.format("Invoke#%H.%n(%p)", calleeMethod); 810 } else { 811 return "Invoke#" + callTarget.targetName(); 812 } 813 } 814 } 815 816 /** 817 * Information about a graph that will potentially be inlined. This includes tracking the 818 * invocations in graph that will subject to inlining themselves. 819 */ 820 private static class GraphInfo { 821 822 private final StructuredGraph graph; 823 private final LinkedList<Invoke> remainingInvokes; 824 private final double probability; 825 private final double relevance; 826 827 private NodesToDoubles nodeProbabilities; 828 private NodesToDoubles nodeRelevance; 829 830 public GraphInfo(StructuredGraph graph, LinkedList<Invoke> invokes, double probability, double relevance) { 831 this.graph = graph; 832 this.remainingInvokes = invokes; 833 this.probability = probability; 834 this.relevance = relevance; 835 836 if (graph != null) { 837 computeProbabilities(); 838 } 839 } 840 841 /** 842 * Gets the method associated with the {@linkplain #graph() graph} represented by this 843 * object. 844 */ 845 public ResolvedJavaMethod method() { 846 return graph.method(); 847 } 848 849 public boolean hasRemainingInvokes() { 850 return !remainingInvokes.isEmpty(); 851 } 852 853 /** 854 * The graph about which this object contains inlining information. 855 */ 856 public StructuredGraph graph() { 857 return graph; 858 } 859 860 public Invoke popInvoke() { 861 return remainingInvokes.removeFirst(); 862 } 863 864 public void pushInvoke(Invoke invoke) { 865 remainingInvokes.push(invoke); 866 } 867 868 public void computeProbabilities() { 869 nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); 870 nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).apply(); 871 } 872 873 public double invokeProbability(Invoke invoke) { 874 return probability * nodeProbabilities.get(invoke.asNode()); 875 } 876 877 public double invokeRelevance(Invoke invoke) { 878 return Math.min(CapInheritedRelevance.getValue(), relevance) * nodeRelevance.get(invoke.asNode()); 879 } 880 881 @Override 882 public String toString() { 883 return MetaUtil.format("%H.%n(%p)", method()) + remainingInvokes; 884 } 885 } 886 887 private static class CompiledMethodInfo { 888 889 private int lowLevelNodes; 890 891 public CompiledMethodInfo() { 892 } 893 894 public int lowLevelNodeCount() { 895 return lowLevelNodes; 896 } 897 898 public void setLowLevelNodeCount(int lowLevelNodes) { 899 this.lowLevelNodes = lowLevelNodes; 900 } 901 902 } 903 } --- EOF ---