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