1 /*
   2  * Copyright (c) 2012, 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 java.lang.reflect.*;
  26 import java.util.*;
  27 import java.util.concurrent.*;
  28 
  29 import com.oracle.graal.api.code.*;
  30 import com.oracle.graal.api.code.Assumptions.Assumption;
  31 import com.oracle.graal.api.meta.*;
  32 import com.oracle.graal.api.meta.JavaTypeProfile.ProfiledType;
  33 import com.oracle.graal.api.meta.ResolvedJavaType.Representation;
  34 import com.oracle.graal.debug.*;
  35 import com.oracle.graal.graph.*;
  36 import com.oracle.graal.hotspot.HotSpotGraalRuntime;
  37 import com.oracle.graal.nodes.*;
  38 import com.oracle.graal.nodes.calc.*;
  39 import com.oracle.graal.nodes.extended.*;
  40 import com.oracle.graal.nodes.java.*;
  41 import com.oracle.graal.nodes.java.MethodCallTargetNode.InvokeKind;
  42 import com.oracle.graal.nodes.spi.*;
  43 import com.oracle.graal.nodes.type.*;
  44 import com.oracle.graal.nodes.util.*;
  45 import com.oracle.graal.phases.*;
  46 
  47 public class InliningUtil {
  48 
  49     private static final DebugMetric metricInliningTailDuplication = Debug.metric("InliningTailDuplication");
  50     private static final String inliningDecisionsScopeString = "InliningDecisions";
  51 
  52     /**
  53      * Meters the size (in bytecodes) of all methods processed during compilation (i.e., top level
  54      * and all inlined methods), irrespective of how many bytecodes in each method are actually
  55      * parsed (which may be none for methods whose IR is retrieved from a cache).
  56      */
  57     public static final DebugMetric InlinedBytecodes = Debug.metric("InlinedBytecodes");
  58 
  59     public interface InliningCallback {
  60 
  61         StructuredGraph buildGraph(final ResolvedJavaMethod method);
  62     }
  63 
  64     public interface InliningPolicy {
  65 
  66         void initialize(StructuredGraph graph);
  67 
  68         boolean continueInlining(StructuredGraph graph);
  69 
  70         InlineInfo next();
  71 
  72         void scanInvokes(Iterable<? extends Node> newNodes);
  73 
  74         boolean isWorthInlining(InlineInfo info);
  75     }
  76 
  77     /**
  78      * Print a HotSpot-style inlining message to the console.
  79      */
  80     private static void printInlining(final InlineInfo info, final boolean success, final String msg, final Object... args) {
  81         printInlining(info.methodAt(0), info.invoke(), success, msg, args);
  82     }
  83 
  84     /**
  85      * Print a HotSpot-style inlining message to the console.
  86      */
  87     private static void printInlining(final ResolvedJavaMethod method, final Invoke invoke, final boolean success, final String msg, final Object... args) {
  88         if (GraalOptions.HotSpotPrintInlining) {
  89             final int mod = method.getModifiers();
  90             //         1234567
  91             TTY.print("        ");     // print timestamp
  92             //         1234
  93             TTY.print("     ");        // print compilation number
  94             //          % s ! b n
  95             TTY.print("%c%c%c%c%c ",
  96                     ' ',
  97                     Modifier.isSynchronized(mod) ? 's' : ' ',
  98                     ' ',
  99                     ' ',
 100                     Modifier.isNative(mod) ? 'n' : ' ');
 101             TTY.print("     ");        // more indent
 102             TTY.print("    ");         // initial inlining indent
 103             final int level = computeInliningLevel(invoke);
 104             for (int i = 0; i < level; i++) {
 105                 TTY.print("  ");
 106             }
 107             TTY.println(String.format("@ %d  %s   %s%s",
 108                     invoke.bci(), methodName(method, null),
 109                     success ? "" : "not inlining ",
 110                     String.format(msg, args)));
 111         }
 112     }
 113 
 114     public static boolean logInlinedMethod(InlineInfo info, String msg, Object... args) {
 115         logInliningDecision(info, true, msg, args);
 116         return true;
 117     }
 118 
 119     public static boolean logNotInlinedMethod(InlineInfo info, String msg, Object... args) {
 120         logInliningDecision(info, false, msg, args);
 121         return false;
 122     }
 123 
 124     public static void logInliningDecision(InlineInfo info, boolean success, String msg, final Object... args) {
 125         printInlining(info, success, msg, args);
 126         if (shouldLogInliningDecision()) {
 127             logInliningDecision(methodName(info), success, msg, args);
 128         }
 129     }
 130 
 131     public static void logInliningDecision(final String msg, final Object... args) {
 132         Debug.scope(inliningDecisionsScopeString, new Runnable() {
 133 
 134             public void run() {
 135                 Debug.log(msg, args);
 136             }
 137         });
 138     }
 139 
 140     private static boolean logNotInlinedMethodAndReturnFalse(Invoke invoke, String msg) {
 141         if (shouldLogInliningDecision()) {
 142             String methodString = invoke.toString() + (invoke.callTarget() == null ? " callTarget=null" : invoke.callTarget().targetName());
 143             logInliningDecision(methodString, false, msg, new Object[0]);
 144         }
 145         return false;
 146     }
 147 
 148     private static InlineInfo logNotInlinedMethodAndReturnNull(Invoke invoke, ResolvedJavaMethod method, String msg) {
 149         return logNotInlinedMethodAndReturnNull(invoke, method, msg, new Object[0]);
 150     }
 151 
 152     private static InlineInfo logNotInlinedMethodAndReturnNull(Invoke invoke, ResolvedJavaMethod method, String msg, Object... args) {
 153         printInlining(method, invoke, false, msg, args);
 154         if (shouldLogInliningDecision()) {
 155             String methodString = methodName(method, invoke);
 156             logInliningDecision(methodString, false, msg, args);
 157         }
 158         return null;
 159     }
 160 
 161     private static boolean logNotInlinedMethodAndReturnFalse(Invoke invoke, ResolvedJavaMethod method, String msg) {
 162         printInlining(method, invoke, false, msg, new Object[0]);
 163         if (shouldLogInliningDecision()) {
 164             String methodString = methodName(method, invoke);
 165             logInliningDecision(methodString, false, msg, new Object[0]);
 166         }
 167         return false;
 168     }
 169 
 170     private static void logInliningDecision(final String methodString, final boolean success, final String msg, final Object... args) {
 171         String inliningMsg = "inlining " + methodString + ": " + msg;
 172         if (!success) {
 173             inliningMsg = "not " + inliningMsg;
 174         }
 175         logInliningDecision(inliningMsg, args);
 176     }
 177 
 178     public static boolean shouldLogInliningDecision() {
 179         return Debug.scope(inliningDecisionsScopeString, new Callable<Boolean>() {
 180 
 181             public Boolean call() {
 182                 return Debug.isLogEnabled();
 183             }
 184         });
 185     }
 186 
 187     private static String methodName(ResolvedJavaMethod method, Invoke invoke) {
 188         if (invoke != null && invoke.stateAfter() != null) {
 189             return methodName(invoke.stateAfter(), invoke.bci()) + ": " + MetaUtil.format("%H.%n(%p):%r", method) + " (" + method.getCodeSize() + " bytes)";
 190         } else {
 191             return MetaUtil.format("%H.%n(%p):%r", method) + " (" + method.getCodeSize() + " bytes)";
 192         }
 193     }
 194 
 195     private static String methodName(InlineInfo info) {
 196         if (info == null) {
 197             return "null";
 198         } else if (info.invoke() != null && info.invoke().stateAfter() != null) {
 199             return methodName(info.invoke().stateAfter(), info.invoke().bci()) + ": " + info.toString();
 200         } else {
 201             return info.toString();
 202         }
 203     }
 204 
 205     private static String methodName(FrameState frameState, int bci) {
 206         StringBuilder sb = new StringBuilder();
 207         if (frameState.outerFrameState() != null) {
 208             sb.append(methodName(frameState.outerFrameState(), frameState.outerFrameState().bci));
 209             sb.append("->");
 210         }
 211         sb.append(MetaUtil.format("%h.%n", frameState.method()));
 212         sb.append("@").append(bci);
 213         return sb.toString();
 214     }
 215 
 216     /**
 217      * Represents an opportunity for inlining at the given invoke, with the given weight and level.
 218      * The weight is the amortized weight of the additional code - so smaller is better. The level
 219      * is the number of nested inlinings that lead to this invoke.
 220      */
 221     public interface InlineInfo {
 222 
 223         Invoke invoke();
 224 
 225         int level();
 226 
 227         int numberOfMethods();
 228 
 229         ResolvedJavaMethod methodAt(int index);
 230 
 231         /**
 232          * Performs the inlining described by this object and returns the node that represents the
 233          * return value of the inlined method (or null for void methods and methods that have no
 234          * non-exceptional exit).
 235          **/
 236         void inline(StructuredGraph graph, MetaAccessProvider runtime, Replacements replacements, InliningCallback callback, Assumptions assumptions);
 237 
 238         /**
 239          * Try to make the call static bindable to avoid interface and virtual method calls.
 240          */
 241         void tryToDevirtualizeInvoke(StructuredGraph graph, MetaAccessProvider runtime, Assumptions assumptions);
 242     }
 243 
 244     public abstract static class AbstractInlineInfo implements InlineInfo {
 245 
 246         protected final Invoke invoke;
 247 
 248         public AbstractInlineInfo(Invoke invoke) {
 249             this.invoke = invoke;
 250         }
 251 
 252         @Override
 253         public Invoke invoke() {
 254             return invoke;
 255         }
 256 
 257         @Override
 258         public int level() {
 259             return computeInliningLevel(invoke);
 260         }
 261 
 262         protected static void inline(Invoke invoke, ResolvedJavaMethod concrete, InliningCallback callback, Replacements replacements, Assumptions assumptions, boolean receiverNullCheck) {
 263             Class<? extends FixedWithNextNode> macroNodeClass = getMacroNodeClass(replacements, concrete);
 264             StructuredGraph graph = (StructuredGraph) invoke.graph();
 265             if (macroNodeClass != null) {
 266                 FixedWithNextNode macroNode;
 267                 try {
 268                     macroNode = macroNodeClass.getConstructor(Invoke.class).newInstance(invoke);
 269                 } catch (ReflectiveOperationException | IllegalArgumentException | SecurityException e) {
 270                     throw new GraalInternalError(e).addContext(invoke.node()).addContext("macroSubstitution", macroNodeClass);
 271                 }
 272                 macroNode.setProbability(invoke.node().probability());
 273                 CallTargetNode callTarget = invoke.callTarget();
 274                 if (invoke instanceof InvokeNode) {
 275                     graph.replaceFixedWithFixed((InvokeNode) invoke, graph.add(macroNode));
 276                 } else {
 277                     InvokeWithExceptionNode invokeWithException = (InvokeWithExceptionNode) invoke;
 278                     invokeWithException.killExceptionEdge();
 279                     graph.replaceSplitWithFixed(invokeWithException, graph.add(macroNode), invokeWithException.next());
 280                 }
 281                 GraphUtil.killWithUnusedFloatingInputs(callTarget);
 282             } else {
 283                 StructuredGraph calleeGraph = getIntrinsicGraph(replacements, concrete);
 284                 if (calleeGraph == null) {
 285                     calleeGraph = getGraph(concrete, callback);
 286                 }
 287                 InlinedBytecodes.add(concrete.getCodeSize());
 288                 assumptions.recordMethodContents(concrete);
 289                 InliningUtil.inline(invoke, calleeGraph, receiverNullCheck);
 290 
 291                 graph.getLeafGraphIds().add(calleeGraph.graphId());
 292                 // we might at some point cache already-inlined graphs, so add recursively:
 293                 graph.getLeafGraphIds().addAll(calleeGraph.getLeafGraphIds());
 294             }
 295         }
 296 
 297         protected static StructuredGraph getGraph(final ResolvedJavaMethod concrete, final InliningCallback callback) {
 298             return Debug.scope("GetInliningGraph", concrete, new Callable<StructuredGraph>() {
 299 
 300                 @Override
 301                 public StructuredGraph call() throws Exception {
 302                     assert !Modifier.isNative(concrete.getModifiers());
 303                     return callback.buildGraph(concrete);
 304                 }
 305             });
 306         }
 307 
 308         protected void replaceInvokeCallTarget(StructuredGraph graph, InvokeKind invokeKind, ResolvedJavaMethod targetMethod) {
 309             MethodCallTargetNode oldCallTarget = invoke.methodCallTarget();
 310             MethodCallTargetNode newCallTarget = graph.add(new MethodCallTargetNode(invokeKind, targetMethod, oldCallTarget.arguments().toArray(new ValueNode[0]), oldCallTarget.returnType()));
 311             invoke.node().replaceFirstInput(oldCallTarget, newCallTarget);
 312         }
 313     }
 314 
 315     /**
 316      * Represents an inlining opportunity where the compiler can statically determine a monomorphic
 317      * target method and therefore is able to determine the called method exactly.
 318      */
 319     private static class ExactInlineInfo extends AbstractInlineInfo {
 320 
 321         public final ResolvedJavaMethod concrete;
 322 
 323         public ExactInlineInfo(Invoke invoke, ResolvedJavaMethod concrete) {
 324             super(invoke);
 325             this.concrete = concrete;
 326         }
 327 
 328         @Override
 329         public void inline(StructuredGraph compilerGraph, MetaAccessProvider runtime, Replacements replacements, InliningCallback callback, Assumptions assumptions) {
 330             inline(invoke, concrete, callback, replacements, assumptions, true);
 331         }
 332 
 333         @Override
 334         public void tryToDevirtualizeInvoke(StructuredGraph graph, MetaAccessProvider runtime, Assumptions assumptions) {
 335             // nothing todo, can already be bound statically
 336         }
 337 
 338         @Override
 339         public int numberOfMethods() {
 340             return 1;
 341         }
 342 
 343         @Override
 344         public ResolvedJavaMethod methodAt(int index) {
 345             assert index == 0;
 346             return concrete;
 347         }
 348 
 349         @Override
 350         public String toString() {
 351             return "exact " + MetaUtil.format("%H.%n(%p):%r", concrete);
 352         }
 353     }
 354 
 355     /**
 356      * Represents an inlining opportunity for which profiling information suggests a monomorphic
 357      * receiver, but for which the receiver type cannot be proven. A type check guard will be
 358      * generated if this inlining is performed.
 359      */
 360     private static class TypeGuardInlineInfo extends AbstractInlineInfo {
 361 
 362         public final ResolvedJavaMethod concrete;
 363         public final ResolvedJavaType type;
 364 
 365         public TypeGuardInlineInfo(Invoke invoke, ResolvedJavaMethod concrete, ResolvedJavaType type) {
 366             super(invoke);
 367             this.concrete = concrete;
 368             this.type = type;
 369         }
 370 
 371         @Override
 372         public int numberOfMethods() {
 373             return 1;
 374         }
 375 
 376         @Override
 377         public ResolvedJavaMethod methodAt(int index) {
 378             assert index == 0;
 379             return concrete;
 380         }
 381 
 382         @Override
 383         public void inline(StructuredGraph graph, MetaAccessProvider runtime, Replacements replacements, InliningCallback callback, Assumptions assumptions) {
 384             createGuard(graph, runtime);
 385             inline(invoke, concrete, callback, replacements, assumptions, false);
 386         }
 387 
 388         @Override
 389         public void tryToDevirtualizeInvoke(StructuredGraph graph, MetaAccessProvider runtime, Assumptions assumptions) {
 390             createGuard(graph, runtime);
 391             replaceInvokeCallTarget(graph, InvokeKind.Special, concrete);
 392         }
 393 
 394         private void createGuard(StructuredGraph graph, MetaAccessProvider runtime) {
 395             InliningUtil.receiverNullCheck(invoke);
 396             ValueNode receiver = invoke.methodCallTarget().receiver();
 397             ConstantNode typeHub = ConstantNode.forConstant(type.getEncoding(Representation.ObjectHub), runtime, graph);
 398             LoadHubNode receiverHub = graph.add(new LoadHubNode(receiver, typeHub.kind()));
 399             CompareNode typeCheck = CompareNode.createCompareNode(Condition.EQ, receiverHub, typeHub);
 400             FixedGuardNode guard = graph.add(new FixedGuardNode(typeCheck, DeoptimizationReason.TypeCheckedInliningViolated, DeoptimizationAction.InvalidateReprofile));
 401             ValueAnchorNode anchor = graph.add(new ValueAnchorNode());
 402             assert invoke.predecessor() != null;
 403 
 404             ValueNode anchoredReceiver = createAnchoredReceiver(graph, anchor, type, receiver, true);
 405             invoke.callTarget().replaceFirstInput(receiver, anchoredReceiver);
 406 
 407             graph.addBeforeFixed(invoke.node(), receiverHub);
 408             graph.addBeforeFixed(invoke.node(), guard);
 409             graph.addBeforeFixed(invoke.node(), anchor);
 410         }
 411 
 412         @Override
 413         public String toString() {
 414             return "type-checked with type " + type.getName() + " and method " + MetaUtil.format("%H.%n(%p):%r", concrete);
 415         }
 416     }
 417 
 418     /**
 419      * Polymorphic inlining of m methods with n type checks (n >= m) in case that the profiling
 420      * information suggests a reasonable amounts of different receiver types and different methods.
 421      * If an unknown type is encountered a deoptimization is triggered.
 422      */
 423     private static class MultiTypeGuardInlineInfo extends AbstractInlineInfo {
 424 
 425         public final List<ResolvedJavaMethod> concretes;
 426         public final ArrayList<ProfiledType> ptypes;
 427         public final int[] typesToConcretes;
 428         public final double notRecordedTypeProbability;
 429 
 430         public MultiTypeGuardInlineInfo(Invoke invoke, ArrayList<ResolvedJavaMethod> concretes, ArrayList<ProfiledType> ptypes, int[] typesToConcretes, double notRecordedTypeProbability) {
 431             super(invoke);
 432             assert concretes.size() > 0 && concretes.size() <= ptypes.size() : "must have at least one method but no more than types methods";
 433             assert ptypes.size() == typesToConcretes.length : "array lengths must match";
 434 
 435             this.concretes = concretes;
 436             this.ptypes = ptypes;
 437             this.typesToConcretes = typesToConcretes;
 438             this.notRecordedTypeProbability = notRecordedTypeProbability;
 439         }
 440 
 441         @Override
 442         public int numberOfMethods() {
 443             return concretes.size();
 444         }
 445 
 446         @Override
 447         public ResolvedJavaMethod methodAt(int index) {
 448             assert index >= 0 && index < concretes.size();
 449             return concretes.get(index);
 450         }
 451 
 452         @Override
 453         public void inline(StructuredGraph graph, MetaAccessProvider runtime, Replacements replacements, InliningCallback callback, Assumptions assumptions) {
 454             // receiver null check must be the first node
 455             InliningUtil.receiverNullCheck(invoke);
 456             if (hasSingleMethod()) {
 457                 inlineSingleMethod(graph, callback, replacements, assumptions);
 458             } else {
 459                 inlineMultipleMethods(graph, callback, replacements, assumptions);
 460             }
 461         }
 462 
 463         private boolean hasSingleMethod() {
 464             return concretes.size() == 1 && !shouldFallbackToInvoke();
 465         }
 466 
 467         private boolean shouldFallbackToInvoke() {
 468             return notRecordedTypeProbability > 0;
 469         }
 470 
 471         private void inlineMultipleMethods(StructuredGraph graph, InliningCallback callback, Replacements replacements, Assumptions assumptions) {
 472             int numberOfMethods = concretes.size();
 473             FixedNode continuation = invoke.next();
 474 
 475             ValueNode originalReceiver = invoke.methodCallTarget().receiver();
 476             // setup merge and phi nodes for results and exceptions
 477             MergeNode returnMerge = graph.add(new MergeNode());
 478             returnMerge.setProbability(invoke.probability());
 479             returnMerge.setStateAfter(invoke.stateAfter().duplicate(invoke.stateAfter().bci));
 480 
 481             PhiNode returnValuePhi = null;
 482             if (invoke.node().kind() != Kind.Void) {
 483                 returnValuePhi = graph.unique(new PhiNode(invoke.node().kind(), returnMerge));
 484             }
 485 
 486             MergeNode exceptionMerge = null;
 487             PhiNode exceptionObjectPhi = null;
 488             if (invoke instanceof InvokeWithExceptionNode) {
 489                 InvokeWithExceptionNode invokeWithException = (InvokeWithExceptionNode) invoke;
 490                 ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithException.exceptionEdge();
 491 
 492                 exceptionMerge = graph.add(new MergeNode());
 493                 exceptionMerge.setProbability(exceptionEdge.probability());
 494 
 495                 FixedNode exceptionSux = exceptionEdge.next();
 496                 graph.addBeforeFixed(exceptionSux, exceptionMerge);
 497                 exceptionObjectPhi = graph.unique(new PhiNode(Kind.Object, exceptionMerge));
 498                 exceptionMerge.setStateAfter(exceptionEdge.stateAfter().duplicateModified(invoke.stateAfter().bci, true, Kind.Object, exceptionObjectPhi));
 499             }
 500 
 501             // create one separate block for each invoked method
 502             BeginNode[] successors = new BeginNode[numberOfMethods + 1];
 503             for (int i = 0; i < numberOfMethods; i++) {
 504                 double probability = 0;
 505                 for (int j = 0; j < typesToConcretes.length; j++) {
 506                     if (typesToConcretes[j] == i) {
 507                         probability += ptypes.get(j).getProbability();
 508                     }
 509                 }
 510 
 511                 successors[i] = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, invoke.probability() * probability, true);
 512             }
 513 
 514             // create the successor for an unknown type
 515             FixedNode unknownTypeSux;
 516             if (shouldFallbackToInvoke()) {
 517                 unknownTypeSux = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, notRecordedTypeProbability, false);
 518             } else {
 519                 unknownTypeSux = graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated));
 520             }
 521             successors[successors.length - 1] = BeginNode.begin(unknownTypeSux);
 522 
 523             // replace the invoke exception edge
 524             if (invoke instanceof InvokeWithExceptionNode) {
 525                 InvokeWithExceptionNode invokeWithExceptionNode = (InvokeWithExceptionNode) invoke;
 526                 ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithExceptionNode.exceptionEdge();
 527                 exceptionEdge.replaceAtUsages(exceptionObjectPhi);
 528                 exceptionEdge.setNext(null);
 529                 GraphUtil.killCFG(invokeWithExceptionNode.exceptionEdge());
 530             }
 531 
 532             assert invoke.node().isAlive();
 533 
 534             // replace the invoke with a switch on the type of the actual receiver
 535             createDispatchOnTypeBeforeInvoke(graph, successors, false);
 536 
 537             assert invoke.next() == continuation;
 538             invoke.setNext(null);
 539             returnMerge.setNext(continuation);
 540             invoke.node().replaceAtUsages(returnValuePhi);
 541             invoke.node().replaceAndDelete(null);
 542 
 543             ArrayList<PiNode> replacementNodes = new ArrayList<>();
 544 
 545             // do the actual inlining for every invoke
 546             for (int i = 0; i < numberOfMethods; i++) {
 547                 BeginNode node = successors[i];
 548                 Invoke invokeForInlining = (Invoke) node.next();
 549 
 550                 ResolvedJavaType commonType = getLeastCommonType(i);
 551                 ValueNode receiver = invokeForInlining.methodCallTarget().receiver();
 552                 boolean exact = getTypeCount(i) == 1;
 553                 PiNode anchoredReceiver = createAnchoredReceiver(graph, node, commonType, receiver, exact);
 554                 invokeForInlining.callTarget().replaceFirstInput(receiver, anchoredReceiver);
 555 
 556                 inline(invokeForInlining, concretes.get(i), callback, replacements, assumptions, false);
 557 
 558                 replacementNodes.add(anchoredReceiver);
 559             }
 560             if (shouldFallbackToInvoke()) {
 561                 replacementNodes.add(null);
 562             }
 563             if (GraalOptions.OptTailDuplication) {
 564                 /*
 565                  * We might want to perform tail duplication at the merge after a type switch, if
 566                  * there are invokes that would benefit from the improvement in type information.
 567                  */
 568                 FixedNode current = returnMerge;
 569                 int opportunities = 0;
 570                 do {
 571                     if (current instanceof InvokeNode && ((InvokeNode) current).methodCallTarget().receiver() == originalReceiver) {
 572                         opportunities++;
 573                     } else if (current.inputs().contains(originalReceiver)) {
 574                         opportunities++;
 575                     }
 576                     current = ((FixedWithNextNode) current).next();
 577                 } while (current instanceof FixedWithNextNode);
 578                 if (opportunities > 0) {
 579                     metricInliningTailDuplication.increment();
 580                     Debug.log("MultiTypeGuardInlineInfo starting tail duplication (%d opportunities)", opportunities);
 581                     TailDuplicationPhase.tailDuplicate(returnMerge, TailDuplicationPhase.TRUE_DECISION, replacementNodes);
 582                 }
 583             }
 584         }
 585 
 586         private int getTypeCount(int concreteMethodIndex) {
 587             int count = 0;
 588             for (int i = 0; i < typesToConcretes.length; i++) {
 589                 if (typesToConcretes[i] == concreteMethodIndex) {
 590                     count++;
 591                 }
 592             }
 593             return count;
 594         }
 595 
 596         private ResolvedJavaType getLeastCommonType(int concreteMethodIndex) {
 597             ResolvedJavaType commonType = null;
 598             for (int i = 0; i < typesToConcretes.length; i++) {
 599                 if (typesToConcretes[i] == concreteMethodIndex) {
 600                     if (commonType == null) {
 601                         commonType = ptypes.get(i).getType();
 602                     } else {
 603                         commonType = commonType.findLeastCommonAncestor(ptypes.get(i).getType());
 604                     }
 605                 }
 606             }
 607             assert commonType != null;
 608             return commonType;
 609         }
 610 
 611         private ResolvedJavaType getLeastCommonType() {
 612             ResolvedJavaType result = getLeastCommonType(0);
 613             for (int i = 1; i < concretes.size(); i++) {
 614                 result = result.findLeastCommonAncestor(getLeastCommonType(i));
 615             }
 616             return result;
 617         }
 618 
 619         private void inlineSingleMethod(StructuredGraph graph, InliningCallback callback, Replacements replacements, Assumptions assumptions) {
 620             assert concretes.size() == 1 && ptypes.size() > 1 && !shouldFallbackToInvoke() && notRecordedTypeProbability == 0;
 621 
 622             BeginNode calleeEntryNode = graph.add(new BeginNode());
 623             calleeEntryNode.setProbability(invoke.probability());
 624 
 625             BeginNode unknownTypeSux = createUnknownTypeSuccessor(graph);
 626             BeginNode[] successors = new BeginNode[]{calleeEntryNode, unknownTypeSux};
 627             createDispatchOnTypeBeforeInvoke(graph, successors, false);
 628 
 629             calleeEntryNode.setNext(invoke.node());
 630 
 631             ResolvedJavaMethod concrete = concretes.get(0);
 632             inline(invoke, concrete, callback, replacements, assumptions, false);
 633         }
 634 
 635         private void createDispatchOnTypeBeforeInvoke(StructuredGraph graph, BeginNode[] successors, boolean invokeIsOnlySuccessor) {
 636             assert ptypes.size() > 1;
 637 
 638             Kind hubKind = invoke.methodCallTarget().targetMethod().getDeclaringClass().getEncoding(Representation.ObjectHub).getKind();
 639             LoadHubNode hub = graph.add(new LoadHubNode(invoke.methodCallTarget().receiver(), hubKind));
 640             graph.addBeforeFixed(invoke.node(), hub);
 641 
 642             ResolvedJavaType[] keys = new ResolvedJavaType[ptypes.size()];
 643             double[] keyProbabilities = new double[ptypes.size() + 1];
 644             int[] keySuccessors = new int[ptypes.size() + 1];
 645             for (int i = 0; i < ptypes.size(); i++) {
 646                 keys[i] = ptypes.get(i).getType();
 647                 keyProbabilities[i] = ptypes.get(i).getProbability();
 648                 keySuccessors[i] = invokeIsOnlySuccessor ? 0 : typesToConcretes[i];
 649                 assert keySuccessors[i] < successors.length - 1 : "last successor is the unknownTypeSux";
 650             }
 651             keyProbabilities[keyProbabilities.length - 1] = notRecordedTypeProbability;
 652             keySuccessors[keySuccessors.length - 1] = successors.length - 1;
 653 
 654             TypeSwitchNode typeSwitch = graph.add(new TypeSwitchNode(hub, successors, keys, keyProbabilities, keySuccessors));
 655             FixedWithNextNode pred = (FixedWithNextNode) invoke.node().predecessor();
 656             pred.setNext(typeSwitch);
 657         }
 658 
 659         private static BeginNode createInvocationBlock(StructuredGraph graph, Invoke invoke, MergeNode returnMerge, PhiNode returnValuePhi, MergeNode exceptionMerge, PhiNode exceptionObjectPhi,
 660                         double probability, boolean useForInlining) {
 661             Invoke duplicatedInvoke = duplicateInvokeForInlining(graph, invoke, exceptionMerge, exceptionObjectPhi, useForInlining, probability);
 662             BeginNode calleeEntryNode = graph.add(new BeginNode());
 663             calleeEntryNode.setNext(duplicatedInvoke.node());
 664             calleeEntryNode.setProbability(probability);
 665 
 666             EndNode endNode = graph.add(new EndNode());
 667             endNode.setProbability(probability);
 668 
 669             duplicatedInvoke.setNext(endNode);
 670             returnMerge.addForwardEnd(endNode);
 671 
 672             if (returnValuePhi != null) {
 673                 returnValuePhi.addInput(duplicatedInvoke.node());
 674             }
 675             return calleeEntryNode;
 676         }
 677 
 678         private static Invoke duplicateInvokeForInlining(StructuredGraph graph, Invoke invoke, MergeNode exceptionMerge, PhiNode exceptionObjectPhi, boolean useForInlining, double probability) {
 679             Invoke result = (Invoke) invoke.node().copyWithInputs();
 680             Node callTarget = result.callTarget().copyWithInputs();
 681             result.node().replaceFirstInput(result.callTarget(), callTarget);
 682             result.setUseForInlining(useForInlining);
 683             result.setProbability(probability);
 684             result.setInliningRelevance(invoke.inliningRelevance() * probability);
 685 
 686             Kind kind = invoke.node().kind();
 687             if (kind != Kind.Void) {
 688                 FrameState stateAfter = invoke.stateAfter();
 689                 stateAfter = stateAfter.duplicate(stateAfter.bci);
 690                 stateAfter.replaceFirstInput(invoke.node(), result.node());
 691                 result.setStateAfter(stateAfter);
 692             }
 693 
 694             if (invoke instanceof InvokeWithExceptionNode) {
 695                 assert exceptionMerge != null && exceptionObjectPhi != null;
 696 
 697                 InvokeWithExceptionNode invokeWithException = (InvokeWithExceptionNode) invoke;
 698                 ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithException.exceptionEdge();
 699                 FrameState stateAfterException = exceptionEdge.stateAfter();
 700 
 701                 ExceptionObjectNode newExceptionEdge = (ExceptionObjectNode) exceptionEdge.copyWithInputs();
 702                 // set new state (pop old exception object, push new one)
 703                 newExceptionEdge.setStateAfter(stateAfterException.duplicateModified(stateAfterException.bci, stateAfterException.rethrowException(), Kind.Object, newExceptionEdge));
 704 
 705                 EndNode endNode = graph.add(new EndNode());
 706                 newExceptionEdge.setNext(endNode);
 707                 exceptionMerge.addForwardEnd(endNode);
 708                 exceptionObjectPhi.addInput(newExceptionEdge);
 709 
 710                 ((InvokeWithExceptionNode) result).setExceptionEdge(newExceptionEdge);
 711             }
 712             return result;
 713         }
 714 
 715         @Override
 716         public void tryToDevirtualizeInvoke(StructuredGraph graph, MetaAccessProvider runtime, Assumptions assumptions) {
 717             if (hasSingleMethod()) {
 718                 tryToDevirtualizeSingleMethod(graph);
 719             } else {
 720                 tryToDevirtualizeMultipleMethods(graph);
 721             }
 722         }
 723 
 724         private void tryToDevirtualizeSingleMethod(StructuredGraph graph) {
 725             devirtualizeWithTypeSwitch(graph, InvokeKind.Special, concretes.get(0));
 726         }
 727 
 728         private void tryToDevirtualizeMultipleMethods(StructuredGraph graph) {
 729             MethodCallTargetNode methodCallTarget = invoke.methodCallTarget();
 730             if (methodCallTarget.invokeKind() == InvokeKind.Interface) {
 731                 ResolvedJavaMethod targetMethod = methodCallTarget.targetMethod();
 732                 ResolvedJavaType leastCommonType = getLeastCommonType();
 733                 // check if we have a common base type that implements the interface -> in that case
 734                 // we have a vtable entry for the interface method and can use a less expensive
 735                 // virtual call
 736                 if (!leastCommonType.isInterface() && targetMethod.getDeclaringClass().isAssignableFrom(leastCommonType)) {
 737                     ResolvedJavaMethod baseClassTargetMethod = leastCommonType.resolveMethod(targetMethod);
 738                     if (baseClassTargetMethod != null) {
 739                         devirtualizeWithTypeSwitch(graph, InvokeKind.Virtual, leastCommonType.resolveMethod(targetMethod));
 740                     }
 741                 }
 742             }
 743         }
 744 
 745         private void devirtualizeWithTypeSwitch(StructuredGraph graph, InvokeKind kind, ResolvedJavaMethod target) {
 746             InliningUtil.receiverNullCheck(invoke);
 747 
 748             BeginNode invocationEntry = graph.add(new BeginNode());
 749             invocationEntry.setProbability(invoke.probability());
 750 
 751             BeginNode unknownTypeSux = createUnknownTypeSuccessor(graph);
 752             BeginNode[] successors = new BeginNode[]{invocationEntry, unknownTypeSux};
 753             createDispatchOnTypeBeforeInvoke(graph, successors, true);
 754 
 755             invocationEntry.setNext(invoke.node());
 756             ValueNode receiver = invoke.methodCallTarget().receiver();
 757             PiNode anchoredReceiver = createAnchoredReceiver(graph, invocationEntry, target.getDeclaringClass(), receiver, false);
 758             invoke.callTarget().replaceFirstInput(receiver, anchoredReceiver);
 759             replaceInvokeCallTarget(graph, kind, target);
 760         }
 761 
 762         private static BeginNode createUnknownTypeSuccessor(StructuredGraph graph) {
 763             return BeginNode.begin(graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated)));
 764         }
 765 
 766         @Override
 767         public String toString() {
 768             StringBuilder builder = new StringBuilder(shouldFallbackToInvoke() ? "megamorphic" : "polymorphic");
 769             builder.append(", ");
 770             builder.append(concretes.size());
 771             builder.append(" methods [ ");
 772             for (int i = 0; i < concretes.size(); i++) {
 773                 builder.append(MetaUtil.format("  %H.%n(%p):%r", concretes.get(i)));
 774             }
 775             builder.append(" ], ");
 776             builder.append(ptypes.size());
 777             builder.append(" type checks [ ");
 778             for (int i = 0; i < ptypes.size(); i++) {
 779                 builder.append("  ");
 780                 builder.append(ptypes.get(i).getType().getName());
 781                 builder.append(ptypes.get(i).getProbability());
 782             }
 783             builder.append(" ]");
 784             return builder.toString();
 785         }
 786     }
 787 
 788     /**
 789      * Represents an inlining opportunity where the current class hierarchy leads to a monomorphic
 790      * target method, but for which an assumption has to be registered because of non-final classes.
 791      */
 792     private static class AssumptionInlineInfo extends ExactInlineInfo {
 793 
 794         private final Assumption takenAssumption;
 795 
 796         public AssumptionInlineInfo(Invoke invoke, ResolvedJavaMethod concrete, Assumption takenAssumption) {
 797             super(invoke, concrete);
 798             this.takenAssumption = takenAssumption;
 799         }
 800 
 801         @Override
 802         public void inline(StructuredGraph graph, MetaAccessProvider runtime, Replacements replacements, InliningCallback callback, Assumptions assumptions) {
 803             assumptions.record(takenAssumption);
 804             Debug.log("recording assumption: %s", takenAssumption);
 805 
 806             super.inline(graph, runtime, replacements, callback, assumptions);
 807         }
 808 
 809         @Override
 810         public void tryToDevirtualizeInvoke(StructuredGraph graph, MetaAccessProvider runtime, Assumptions assumptions) {
 811             assumptions.record(takenAssumption);
 812             replaceInvokeCallTarget(graph, InvokeKind.Special, concrete);
 813         }
 814 
 815         @Override
 816         public String toString() {
 817             return "assumption " + MetaUtil.format("%H.%n(%p):%r", concrete);
 818         }
 819     }
 820 
 821     /**
 822      * Determines if inlining is possible at the given invoke node.
 823      * 
 824      * @param invoke the invoke that should be inlined
 825      * @return an instance of InlineInfo, or null if no inlining is possible at the given invoke
 826      */
 827     public static InlineInfo getInlineInfo(Invoke invoke, Replacements replacements, Assumptions assumptions, OptimisticOptimizations optimisticOpts) {
 828         if (!checkInvokeConditions(invoke)) {
 829             return null;
 830         }
 831         ResolvedJavaMethod caller = getCaller(invoke);
 832         MethodCallTargetNode callTarget = invoke.methodCallTarget();
 833         ResolvedJavaMethod targetMethod = callTarget.targetMethod();
 834 
 835         if (callTarget.invokeKind() == InvokeKind.Special || targetMethod.canBeStaticallyBound()) {
 836             return getExactInlineInfo(replacements, invoke, optimisticOpts, targetMethod);
 837         }
 838 
 839         assert callTarget.invokeKind() == InvokeKind.Virtual || callTarget.invokeKind() == InvokeKind.Interface;
 840 
 841         ResolvedJavaType holder = targetMethod.getDeclaringClass();
 842         ObjectStamp receiverStamp = callTarget.receiver().objectStamp();
 843         if (receiverStamp.type() != null) {
 844             // the invoke target might be more specific than the holder (happens after inlining:
 845             // locals lose their declared type...)
 846             ResolvedJavaType receiverType = receiverStamp.type();
 847             if (receiverType != null && holder.isAssignableFrom(receiverType)) {
 848                 holder = receiverType;
 849                 if (receiverStamp.isExactType()) {
 850                     assert targetMethod.getDeclaringClass().isAssignableFrom(holder) : holder + " subtype of " + targetMethod.getDeclaringClass() + " for " + targetMethod;
 851                     return getExactInlineInfo(replacements, invoke, optimisticOpts, holder.resolveMethod(targetMethod));
 852                 }
 853             }
 854         }
 855 
 856         if (holder.isArray()) {
 857             // arrays can be treated as Objects
 858             return getExactInlineInfo(replacements, invoke, optimisticOpts, holder.resolveMethod(targetMethod));
 859         }
 860 
 861         if (assumptions.useOptimisticAssumptions()) {
 862             ResolvedJavaType uniqueSubtype = holder.findUniqueConcreteSubtype();
 863             if (uniqueSubtype != null) {
 864                 return getAssumptionInlineInfo(replacements, invoke, optimisticOpts, uniqueSubtype.resolveMethod(targetMethod), new Assumptions.ConcreteSubtype(holder, uniqueSubtype));
 865             }
 866 
 867             ResolvedJavaMethod concrete = holder.findUniqueConcreteMethod(targetMethod);
 868             if (concrete != null) {
 869                 return getAssumptionInlineInfo(replacements, invoke, optimisticOpts, concrete, new Assumptions.ConcreteMethod(targetMethod, holder, concrete));
 870             }
 871         }
 872 
 873         // type check based inlining
 874         return getTypeCheckedInlineInfo(replacements, invoke, caller, holder, targetMethod, optimisticOpts);
 875     }
 876 
 877     private static InlineInfo getAssumptionInlineInfo(Replacements replacements, Invoke invoke, OptimisticOptimizations optimisticOpts, ResolvedJavaMethod concrete, Assumption takenAssumption) {
 878         assert !Modifier.isAbstract(concrete.getModifiers());
 879         if (!checkTargetConditions(replacements, invoke, concrete, optimisticOpts)) {
 880             return null;
 881         }
 882         return new AssumptionInlineInfo(invoke, concrete, takenAssumption);
 883     }
 884 
 885     private static InlineInfo getExactInlineInfo(Replacements replacements, Invoke invoke, OptimisticOptimizations optimisticOpts, ResolvedJavaMethod targetMethod) {
 886         assert !Modifier.isAbstract(targetMethod.getModifiers());
 887         if (!checkTargetConditions(replacements, invoke, targetMethod, optimisticOpts)) {
 888             return null;
 889         }
 890         return new ExactInlineInfo(invoke, targetMethod);
 891     }
 892 
 893     private static InlineInfo getTypeCheckedInlineInfo(Replacements replacements, Invoke invoke, ResolvedJavaMethod caller, ResolvedJavaType holder, ResolvedJavaMethod targetMethod,
 894                     OptimisticOptimizations optimisticOpts) {
 895         ProfilingInfo profilingInfo = caller.getProfilingInfo();
 896         JavaTypeProfile typeProfile = profilingInfo.getTypeProfile(invoke.bci());
 897         if (typeProfile == null) {
 898             return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "no type profile exists");
 899         }
 900 
 901         ProfiledType[] rawProfiledTypes = typeProfile.getTypes();
 902         ArrayList<ProfiledType> ptypes = getCompatibleTypes(rawProfiledTypes, holder);
 903         if (ptypes == null || ptypes.size() <= 0) {
 904             return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "no types remained after filtering (%d types were recorded)", rawProfiledTypes.length);
 905         }
 906 
 907         double notRecordedTypeProbability = typeProfile.getNotRecordedProbability();
 908         if (ptypes.size() == 1 && notRecordedTypeProbability == 0) {
 909             if (!optimisticOpts.inlineMonomorphicCalls()) {
 910                 return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "inlining monomorphic calls is disabled");
 911             }
 912 
 913             ResolvedJavaType type = ptypes.get(0).getType();
 914             ResolvedJavaMethod concrete = type.resolveMethod(targetMethod);
 915             if (!checkTargetConditions(replacements, invoke, concrete, optimisticOpts)) {
 916                 return null;
 917             }
 918             return new TypeGuardInlineInfo(invoke, concrete, type);
 919         } else {
 920             invoke.setPolymorphic(true);
 921 
 922             if (!optimisticOpts.inlinePolymorphicCalls() && notRecordedTypeProbability == 0) {
 923                 return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "inlining polymorphic calls is disabled (%d types)", ptypes.size());
 924             }
 925             if (!optimisticOpts.inlineMegamorphicCalls() && notRecordedTypeProbability > 0) {
 926                 // due to filtering impossible types, notRecordedTypeProbability can be > 0 although
 927                 // the number of types is lower than what can be recorded in a type profile
 928                 return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "inlining megamorphic calls is disabled (%d types, %f %% not recorded types)", ptypes.size(),
 929                                 notRecordedTypeProbability * 100);
 930             }
 931 
 932             // determine concrete methods and map type to specific method
 933             ArrayList<ResolvedJavaMethod> concreteMethods = new ArrayList<>();
 934             int[] typesToConcretes = new int[ptypes.size()];
 935             for (int i = 0; i < ptypes.size(); i++) {
 936                 ResolvedJavaMethod concrete = ptypes.get(i).getType().resolveMethod(targetMethod);
 937 
 938                 int index = concreteMethods.indexOf(concrete);
 939                 if (index < 0) {
 940                     index = concreteMethods.size();
 941                     concreteMethods.add(concrete);
 942                 }
 943                 typesToConcretes[i] = index;
 944             }
 945 
 946             for (ResolvedJavaMethod concrete : concreteMethods) {
 947                 if (!checkTargetConditions(replacements, invoke, concrete, optimisticOpts)) {
 948                     return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "it is a polymorphic method call and at least one invoked method cannot be inlined");
 949                 }
 950             }
 951             return new MultiTypeGuardInlineInfo(invoke, concreteMethods, ptypes, typesToConcretes, notRecordedTypeProbability);
 952         }
 953     }
 954 
 955     private static ArrayList<ProfiledType> getCompatibleTypes(ProfiledType[] types, ResolvedJavaType holder) {
 956         ArrayList<ProfiledType> result = new ArrayList<>();
 957         for (int i = 0; i < types.length; i++) {
 958             ProfiledType ptype = types[i];
 959             ResolvedJavaType type = ptype.getType();
 960             assert !type.isInterface() && (type.isArray() || !Modifier.isAbstract(type.getModifiers())) : type;
 961             if (!GraalOptions.OptFilterProfiledTypes || holder.isAssignableFrom(type)) {
 962                 result.add(ptype);
 963             }
 964         }
 965         return result;
 966     }
 967 
 968     private static ResolvedJavaMethod getCaller(Invoke invoke) {
 969         return invoke.stateAfter().method();
 970     }
 971 
 972     private static PiNode createAnchoredReceiver(StructuredGraph graph, FixedNode anchor, ResolvedJavaType commonType, ValueNode receiver, boolean exact) {
 973         // to avoid that floating reads on receiver fields float above the type check
 974         return graph.unique(new PiNode(receiver, exact ? StampFactory.exactNonNull(commonType) : StampFactory.declaredNonNull(commonType), anchor));
 975     }
 976 
 977     private static boolean checkInvokeConditions(Invoke invoke) {
 978         if (invoke.predecessor() == null || !invoke.node().isAlive()) {
 979             return logNotInlinedMethodAndReturnFalse(invoke, "the invoke is dead code");
 980         } else if (!(invoke.callTarget() instanceof MethodCallTargetNode)) {
 981             return logNotInlinedMethodAndReturnFalse(invoke, "the invoke has already been lowered, or has been created as a low-level node");
 982         } else if (invoke.methodCallTarget().targetMethod() == null) {
 983             return logNotInlinedMethodAndReturnFalse(invoke, "target method is null");
 984         } else if (invoke.stateAfter() == null) {
 985             return logNotInlinedMethodAndReturnFalse(invoke, "the invoke has no after state");
 986         } else if (!invoke.useForInlining()) {
 987             return logNotInlinedMethodAndReturnFalse(invoke, "the invoke is marked to be not used for inlining");
 988         } else if (invoke.methodCallTarget().receiver() != null && invoke.methodCallTarget().receiver().isConstant() && invoke.methodCallTarget().receiver().asConstant().isNull()) {
 989             return logNotInlinedMethodAndReturnFalse(invoke, "receiver is null");
 990         } else {
 991             return true;
 992         }
 993     }
 994 
 995     private static boolean checkTargetConditions(Replacements replacements, Invoke invoke, ResolvedJavaMethod method, OptimisticOptimizations optimisticOpts) {
 996         if (method == null) {
 997             return logNotInlinedMethodAndReturnFalse(invoke, method, "the method is not resolved");
 998         } else if (Modifier.isNative(method.getModifiers()) && (!GraalOptions.Intrinsify || !InliningUtil.canIntrinsify(replacements, method))) {
 999             return logNotInlinedMethodAndReturnFalse(invoke, method, "it is a non-intrinsic native method");
1000         } else if (Modifier.isAbstract(method.getModifiers())) {
1001             return logNotInlinedMethodAndReturnFalse(invoke, method, "it is an abstract method");
1002         } else if (!method.getDeclaringClass().isInitialized()) {
1003             return logNotInlinedMethodAndReturnFalse(invoke, method, "the method's class is not initialized");
1004         } else if (!method.canBeInlined()) {
1005             return logNotInlinedMethodAndReturnFalse(invoke, method, "it is marked non-inlinable");
1006         } else if (computeRecursiveInliningLevel(invoke.stateAfter(), method) > GraalOptions.MaximumRecursiveInlining) {
1007             return logNotInlinedMethodAndReturnFalse(invoke, method, "it exceeds the maximum recursive inlining depth");
1008         } else if (new OptimisticOptimizations(method).lessOptimisticThan(optimisticOpts)) {
1009             return logNotInlinedMethodAndReturnFalse(invoke, method, "the callee uses less optimistic optimizations than caller");
1010         } else {
1011             return true;
1012         }
1013     }
1014 
1015     private static int computeInliningLevel(Invoke invoke) {
1016         int count = -1;
1017         FrameState curState = invoke.stateAfter();
1018         while (curState != null) {
1019             count++;
1020             curState = curState.outerFrameState();
1021         }
1022         return count;
1023     }
1024 
1025     private static int computeRecursiveInliningLevel(FrameState state, ResolvedJavaMethod method) {
1026         assert state != null;
1027 
1028         int count = 0;
1029         FrameState curState = state;
1030         while (curState != null) {
1031             if (curState.method() == method) {
1032                 count++;
1033             }
1034             curState = curState.outerFrameState();
1035         }
1036         return count;
1037     }
1038 
1039     static MonitorExitNode findPrecedingMonitorExit(UnwindNode unwind) {
1040         Node pred = unwind.predecessor();
1041         while (pred != null) {
1042             if (pred instanceof MonitorExitNode) {
1043                 return (MonitorExitNode) pred;
1044             }
1045             pred = pred.predecessor();
1046         }
1047         return null;
1048     }
1049 
1050     /**
1051      * Performs an actual inlining, thereby replacing the given invoke with the given inlineGraph.
1052      * 
1053      * @param invoke the invoke that will be replaced
1054      * @param inlineGraph the graph that the invoke will be replaced with
1055      * @param receiverNullCheck true if a null check needs to be generated for non-static inlinings,
1056      *            false if no such check is required
1057      */
1058     public static Map<Node, Node> inline(Invoke invoke, StructuredGraph inlineGraph, boolean receiverNullCheck) {
1059         NodeInputList<ValueNode> parameters = invoke.callTarget().arguments();
1060         StructuredGraph graph = (StructuredGraph) invoke.node().graph();
1061 
1062         FrameState stateAfter = invoke.stateAfter();
1063         assert stateAfter.isAlive();
1064 
1065         IdentityHashMap<Node, Node> replacements = new IdentityHashMap<>();
1066         ArrayList<Node> nodes = new ArrayList<>();
1067         ReturnNode returnNode = null;
1068         UnwindNode unwindNode = null;
1069         StartNode entryPointNode = inlineGraph.start();
1070         FixedNode firstCFGNode = entryPointNode.next();
1071         for (Node node : inlineGraph.getNodes()) {
1072             if (node == entryPointNode || node == entryPointNode.stateAfter()) {
1073                 // Do nothing.
1074             } else if (node instanceof LocalNode) {
1075                 replacements.put(node, parameters.get(((LocalNode) node).index()));
1076             } else {
1077                 nodes.add(node);
1078                 if (node instanceof ReturnNode) {
1079                     assert returnNode == null;
1080                     returnNode = (ReturnNode) node;
1081                 } else if (node instanceof UnwindNode) {
1082                     assert unwindNode == null;
1083                     unwindNode = (UnwindNode) node;
1084                 }
1085             }
1086         }
1087         // ensure proper anchoring of things that were anchored to the StartNode
1088         replacements.put(entryPointNode, BeginNode.prevBegin(invoke.node()));
1089 
1090         assert invoke.node().successors().first() != null : invoke;
1091         assert invoke.node().predecessor() != null;
1092 
1093         Map<Node, Node> duplicates = graph.addDuplicates(nodes, replacements);
1094         FixedNode firstCFGNodeDuplicate = (FixedNode) duplicates.get(firstCFGNode);
1095         if (receiverNullCheck) {
1096             receiverNullCheck(invoke);
1097         }
1098         invoke.node().replaceAtPredecessor(firstCFGNodeDuplicate);
1099 
1100         FrameState stateAtExceptionEdge = null;
1101         if (invoke instanceof InvokeWithExceptionNode) {
1102             InvokeWithExceptionNode invokeWithException = ((InvokeWithExceptionNode) invoke);
1103             if (unwindNode != null) {
1104                 assert unwindNode.predecessor() != null;
1105                 assert invokeWithException.exceptionEdge().successors().count() == 1;
1106                 ExceptionObjectNode obj = (ExceptionObjectNode) invokeWithException.exceptionEdge();
1107                 stateAtExceptionEdge = obj.stateAfter();
1108                 UnwindNode unwindDuplicate = (UnwindNode) duplicates.get(unwindNode);
1109                 obj.replaceAtUsages(unwindDuplicate.exception());
1110                 unwindDuplicate.clearInputs();
1111                 Node n = obj.next();
1112                 obj.setNext(null);
1113                 unwindDuplicate.replaceAndDelete(n);
1114             } else {
1115                 invokeWithException.killExceptionEdge();
1116             }
1117         } else {
1118             if (unwindNode != null) {
1119                 UnwindNode unwindDuplicate = (UnwindNode) duplicates.get(unwindNode);
1120                 MonitorExitNode monitorExit = findPrecedingMonitorExit(unwindDuplicate);
1121                 DeoptimizeNode deoptimizeNode = new DeoptimizeNode(DeoptimizationAction.InvalidateRecompile, DeoptimizationReason.NotCompiledExceptionHandler);
1122                 unwindDuplicate.replaceAndDelete(graph.add(deoptimizeNode));
1123                 // move the deopt upwards if there is a monitor exit that tries to use the
1124                 // "after exception" frame state
1125                 // (because there is no "after exception" frame state!)
1126                 if (monitorExit != null) {
1127                     if (monitorExit.stateAfter() != null && monitorExit.stateAfter().bci == FrameState.AFTER_EXCEPTION_BCI) {
1128                         FrameState monitorFrameState = monitorExit.stateAfter();
1129                         graph.removeFixed(monitorExit);
1130                         monitorFrameState.safeDelete();
1131                     }
1132                 }
1133             }
1134         }
1135 
1136         FrameState outerFrameState = null;
1137         double invokeProbability = invoke.node().probability();
1138         int callerLockDepth = stateAfter.nestedLockDepth();
1139         for (Node node : duplicates.values()) {
1140             if (GraalOptions.ProbabilityAnalysis) {
1141                 if (node instanceof FixedNode) {
1142                     FixedNode fixed = (FixedNode) node;
1143                     double newProbability = fixed.probability() * invokeProbability;
1144                     if (GraalOptions.LimitInlinedProbability) {
1145                         newProbability = Math.min(newProbability, invokeProbability);
1146                     }
1147                     fixed.setProbability(newProbability);
1148                 }
1149                 if (node instanceof Invoke) {
1150                     Invoke newInvoke = (Invoke) node;
1151                     double newRelevance = newInvoke.inliningRelevance() * invoke.inliningRelevance();
1152                     if (GraalOptions.LimitInlinedRelevance) {
1153                         newRelevance = Math.min(newRelevance, invoke.inliningRelevance());
1154                     }
1155                     newInvoke.setInliningRelevance(newRelevance);
1156                 }
1157             }
1158             if (node instanceof FrameState) {
1159                 FrameState frameState = (FrameState) node;
1160                 assert frameState.bci != FrameState.BEFORE_BCI;
1161                 if (frameState.bci == FrameState.AFTER_BCI) {
1162                     frameState.replaceAndDelete(stateAfter);
1163                 } else if (frameState.bci == FrameState.AFTER_EXCEPTION_BCI) {
1164                     if (frameState.isAlive()) {
1165                         assert stateAtExceptionEdge != null;
1166                         frameState.replaceAndDelete(stateAtExceptionEdge);
1167                     } else {
1168                         assert stateAtExceptionEdge == null;
1169                     }
1170                 } else {
1171                     // only handle the outermost frame states
1172                     if (frameState.outerFrameState() == null) {
1173                         assert frameState.bci == FrameState.INVALID_FRAMESTATE_BCI || frameState.method() == inlineGraph.method();
1174                         if (outerFrameState == null) {
1175                             outerFrameState = stateAfter.duplicateModified(invoke.bci(), stateAfter.rethrowException(), invoke.node().kind());
1176                             outerFrameState.setDuringCall(true);
1177                         }
1178                         frameState.setOuterFrameState(outerFrameState);
1179                     }
1180                 }
1181             }
1182             if (callerLockDepth != 0 && node instanceof MonitorReference) {
1183                 MonitorReference monitor = (MonitorReference) node;
1184                 monitor.setLockDepth(monitor.getLockDepth() + callerLockDepth);
1185             }
1186         }
1187 
1188         Node returnValue = null;
1189         if (returnNode != null) {
1190             if (returnNode.result() instanceof LocalNode) {
1191                 returnValue = replacements.get(returnNode.result());
1192             } else {
1193                 returnValue = duplicates.get(returnNode.result());
1194             }
1195             invoke.node().replaceAtUsages(returnValue);
1196             Node returnDuplicate = duplicates.get(returnNode);
1197             returnDuplicate.clearInputs();
1198             Node n = invoke.next();
1199             invoke.setNext(null);
1200             returnDuplicate.replaceAndDelete(n);
1201         }
1202 
1203         invoke.node().replaceAtUsages(null);
1204         GraphUtil.killCFG(invoke.node());
1205 
1206         return duplicates;
1207     }
1208 
1209     public static void receiverNullCheck(Invoke invoke) {
1210         MethodCallTargetNode callTarget = invoke.methodCallTarget();
1211         StructuredGraph graph = (StructuredGraph) invoke.graph();
1212         NodeInputList<ValueNode> parameters = callTarget.arguments();
1213         ValueNode firstParam = parameters.size() <= 0 ? null : parameters.get(0);
1214         if (!callTarget.isStatic() && firstParam.kind() == Kind.Object && !firstParam.objectStamp().nonNull()) {
1215             graph.addBeforeFixed(invoke.node(),
1216                             graph.add(new FixedGuardNode(graph.unique(new IsNullNode(firstParam)), DeoptimizationReason.NullCheckException, DeoptimizationAction.InvalidateReprofile, true)));
1217         }
1218     }
1219 
1220     public static boolean canIntrinsify(Replacements replacements, ResolvedJavaMethod target) {
1221         return getIntrinsicGraph(replacements, target) != null || getMacroNodeClass(replacements, target) != null;
1222     }
1223 
1224     public static StructuredGraph getIntrinsicGraph(Replacements replacements, ResolvedJavaMethod target) {
1225         return replacements.getMethodSubstitution(target);
1226     }
1227 
1228     public static Class<? extends FixedWithNextNode> getMacroNodeClass(Replacements replacements, ResolvedJavaMethod target) {
1229         return replacements.getMacroSubstitution(target);
1230     }
1231 }