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 }