001/* 002 * Copyright (c) 2013, 2014, Oracle and/or its affiliates. All rights reserved. 003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 004 * 005 * This code is free software; you can redistribute it and/or modify it 006 * under the terms of the GNU General Public License version 2 only, as 007 * published by the Free Software Foundation. 008 * 009 * This code is distributed in the hope that it will be useful, but WITHOUT 010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 011 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 012 * version 2 for more details (a copy is included in the LICENSE file that 013 * accompanied this code). 014 * 015 * You should have received a copy of the GNU General Public License version 016 * 2 along with this work; if not, write to the Free Software Foundation, 017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 018 * 019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 020 * or visit www.oracle.com if you need additional information or have any 021 * questions. 022 */ 023package com.oracle.graal.phases.common.inlining.info; 024 025import com.oracle.graal.debug.*; 026import jdk.internal.jvmci.meta.ResolvedJavaType; 027import jdk.internal.jvmci.meta.Kind; 028import jdk.internal.jvmci.meta.DeoptimizationReason; 029import jdk.internal.jvmci.meta.DeoptimizationAction; 030import jdk.internal.jvmci.meta.ResolvedJavaMethod; 031import jdk.internal.jvmci.meta.JavaTypeProfile.ProfiledType; 032 033import java.util.*; 034 035import com.oracle.graal.compiler.common.type.*; 036import com.oracle.graal.graph.*; 037import com.oracle.graal.nodes.*; 038import com.oracle.graal.nodes.CallTargetNode.InvokeKind; 039import com.oracle.graal.nodes.extended.*; 040import com.oracle.graal.nodes.java.*; 041import com.oracle.graal.nodes.spi.*; 042import com.oracle.graal.nodes.util.*; 043import com.oracle.graal.phases.common.inlining.*; 044import com.oracle.graal.phases.common.inlining.info.elem.*; 045import com.oracle.graal.phases.util.*; 046 047/** 048 * Polymorphic inlining of m methods with n type checks (n ≥ m) in case that the profiling 049 * information suggests a reasonable amount of different receiver types and different methods. If an 050 * unknown type is encountered a deoptimization is triggered. 051 */ 052public class MultiTypeGuardInlineInfo extends AbstractInlineInfo { 053 054 private final List<ResolvedJavaMethod> concretes; 055 private final double[] methodProbabilities; 056 private final double maximumMethodProbability; 057 private final ArrayList<Integer> typesToConcretes; 058 private final ArrayList<ProfiledType> ptypes; 059 private final double notRecordedTypeProbability; 060 private final Inlineable[] inlineableElements; 061 062 public MultiTypeGuardInlineInfo(Invoke invoke, ArrayList<ResolvedJavaMethod> concretes, ArrayList<ProfiledType> ptypes, ArrayList<Integer> typesToConcretes, double notRecordedTypeProbability) { 063 super(invoke); 064 assert concretes.size() > 0 : "must have at least one method"; 065 assert ptypes.size() == typesToConcretes.size() : "array lengths must match"; 066 067 this.concretes = concretes; 068 this.ptypes = ptypes; 069 this.typesToConcretes = typesToConcretes; 070 this.notRecordedTypeProbability = notRecordedTypeProbability; 071 this.inlineableElements = new Inlineable[concretes.size()]; 072 this.methodProbabilities = computeMethodProbabilities(); 073 this.maximumMethodProbability = maximumMethodProbability(); 074 assert maximumMethodProbability > 0; 075 assert assertUniqueTypes(ptypes); 076 } 077 078 private static boolean assertUniqueTypes(ArrayList<ProfiledType> ptypes) { 079 Set<ResolvedJavaType> set = new HashSet<>(); 080 for (ProfiledType ptype : ptypes) { 081 set.add(ptype.getType()); 082 } 083 return set.size() == ptypes.size(); 084 } 085 086 private double[] computeMethodProbabilities() { 087 double[] result = new double[concretes.size()]; 088 for (int i = 0; i < typesToConcretes.size(); i++) { 089 int concrete = typesToConcretes.get(i); 090 double probability = ptypes.get(i).getProbability(); 091 result[concrete] += probability; 092 } 093 return result; 094 } 095 096 private double maximumMethodProbability() { 097 double max = 0; 098 for (int i = 0; i < methodProbabilities.length; i++) { 099 max = Math.max(max, methodProbabilities[i]); 100 } 101 return max; 102 } 103 104 @Override 105 public int numberOfMethods() { 106 return concretes.size(); 107 } 108 109 @Override 110 public ResolvedJavaMethod methodAt(int index) { 111 assert index >= 0 && index < concretes.size(); 112 return concretes.get(index); 113 } 114 115 @Override 116 public Inlineable inlineableElementAt(int index) { 117 assert index >= 0 && index < concretes.size(); 118 return inlineableElements[index]; 119 } 120 121 @Override 122 public double probabilityAt(int index) { 123 return methodProbabilities[index]; 124 } 125 126 @Override 127 public double relevanceAt(int index) { 128 return probabilityAt(index) / maximumMethodProbability; 129 } 130 131 @Override 132 public void setInlinableElement(int index, Inlineable inlineableElement) { 133 assert index >= 0 && index < concretes.size(); 134 inlineableElements[index] = inlineableElement; 135 } 136 137 @Override 138 public Collection<Node> inline(Providers providers) { 139 if (hasSingleMethod()) { 140 return inlineSingleMethod(graph(), providers.getStampProvider()); 141 } else { 142 return inlineMultipleMethods(graph(), providers); 143 } 144 } 145 146 public boolean shouldInline() { 147 for (ResolvedJavaMethod method : concretes) { 148 if (method.shouldBeInlined()) { 149 return true; 150 } 151 } 152 return false; 153 } 154 155 private boolean hasSingleMethod() { 156 return concretes.size() == 1 && !shouldFallbackToInvoke(); 157 } 158 159 private boolean shouldFallbackToInvoke() { 160 return notRecordedTypeProbability > 0; 161 } 162 163 private Collection<Node> inlineMultipleMethods(StructuredGraph graph, Providers providers) { 164 int numberOfMethods = concretes.size(); 165 FixedNode continuation = invoke.next(); 166 167 // setup merge and phi nodes for results and exceptions 168 AbstractMergeNode returnMerge = graph.add(new MergeNode()); 169 returnMerge.setStateAfter(invoke.stateAfter()); 170 171 PhiNode returnValuePhi = null; 172 if (invoke.asNode().getKind() != Kind.Void) { 173 returnValuePhi = graph.addWithoutUnique(new ValuePhiNode(invoke.asNode().stamp().unrestricted(), returnMerge)); 174 } 175 176 AbstractMergeNode exceptionMerge = null; 177 PhiNode exceptionObjectPhi = null; 178 if (invoke instanceof InvokeWithExceptionNode) { 179 InvokeWithExceptionNode invokeWithException = (InvokeWithExceptionNode) invoke; 180 ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithException.exceptionEdge(); 181 182 exceptionMerge = graph.add(new MergeNode()); 183 184 FixedNode exceptionSux = exceptionEdge.next(); 185 graph.addBeforeFixed(exceptionSux, exceptionMerge); 186 exceptionObjectPhi = graph.addWithoutUnique(new ValuePhiNode(StampFactory.forKind(Kind.Object), exceptionMerge)); 187 exceptionMerge.setStateAfter(exceptionEdge.stateAfter().duplicateModified(invoke.stateAfter().bci, true, Kind.Object, new Kind[]{Kind.Object}, new ValueNode[]{exceptionObjectPhi})); 188 } 189 190 // create one separate block for each invoked method 191 AbstractBeginNode[] successors = new AbstractBeginNode[numberOfMethods + 1]; 192 for (int i = 0; i < numberOfMethods; i++) { 193 successors[i] = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, true); 194 } 195 196 // create the successor for an unknown type 197 FixedNode unknownTypeSux; 198 if (shouldFallbackToInvoke()) { 199 unknownTypeSux = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, false); 200 } else { 201 unknownTypeSux = graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated)); 202 } 203 successors[successors.length - 1] = BeginNode.begin(unknownTypeSux); 204 205 // replace the invoke exception edge 206 if (invoke instanceof InvokeWithExceptionNode) { 207 InvokeWithExceptionNode invokeWithExceptionNode = (InvokeWithExceptionNode) invoke; 208 ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithExceptionNode.exceptionEdge(); 209 exceptionEdge.replaceAtUsages(exceptionObjectPhi); 210 exceptionEdge.setNext(null); 211 GraphUtil.killCFG(invokeWithExceptionNode.exceptionEdge()); 212 } 213 214 assert invoke.asNode().isAlive(); 215 216 // replace the invoke with a switch on the type of the actual receiver 217 boolean methodDispatch = createDispatchOnTypeBeforeInvoke(graph, successors, false, providers.getStampProvider()); 218 219 assert invoke.next() == continuation; 220 invoke.setNext(null); 221 returnMerge.setNext(continuation); 222 if (returnValuePhi != null) { 223 invoke.asNode().replaceAtUsages(returnValuePhi); 224 } 225 invoke.asNode().safeDelete(); 226 227 ArrayList<GuardedValueNode> replacementNodes = new ArrayList<>(); 228 229 // prepare the anchors for the invokes 230 for (int i = 0; i < numberOfMethods; i++) { 231 AbstractBeginNode node = successors[i]; 232 Invoke invokeForInlining = (Invoke) node.next(); 233 234 ResolvedJavaType commonType; 235 if (methodDispatch) { 236 commonType = concretes.get(i).getDeclaringClass(); 237 } else { 238 commonType = getLeastCommonType(i); 239 } 240 241 ValueNode receiver = ((MethodCallTargetNode) invokeForInlining.callTarget()).receiver(); 242 boolean exact = (getTypeCount(i) == 1 && !methodDispatch); 243 GuardedValueNode anchoredReceiver = InliningUtil.createAnchoredReceiver(graph, node, commonType, receiver, exact); 244 invokeForInlining.callTarget().replaceFirstInput(receiver, anchoredReceiver); 245 246 assert !anchoredReceiver.isDeleted() : anchoredReceiver; 247 replacementNodes.add(anchoredReceiver); 248 } 249 if (shouldFallbackToInvoke()) { 250 replacementNodes.add(null); 251 } 252 253 Collection<Node> canonicalizeNodes = new ArrayList<>(); 254 // do the actual inlining for every invoke 255 for (int i = 0; i < numberOfMethods; i++) { 256 Invoke invokeForInlining = (Invoke) successors[i].next(); 257 canonicalizeNodes.addAll(inline(invokeForInlining, methodAt(i), inlineableElementAt(i), false)); 258 } 259 if (returnValuePhi != null) { 260 canonicalizeNodes.add(returnValuePhi); 261 } 262 return canonicalizeNodes; 263 } 264 265 private int getTypeCount(int concreteMethodIndex) { 266 int count = 0; 267 for (int i = 0; i < typesToConcretes.size(); i++) { 268 if (typesToConcretes.get(i) == concreteMethodIndex) { 269 count++; 270 } 271 } 272 return count; 273 } 274 275 private ResolvedJavaType getLeastCommonType(int concreteMethodIndex) { 276 ResolvedJavaType commonType = null; 277 for (int i = 0; i < typesToConcretes.size(); i++) { 278 if (typesToConcretes.get(i) == concreteMethodIndex) { 279 if (commonType == null) { 280 commonType = ptypes.get(i).getType(); 281 } else { 282 commonType = commonType.findLeastCommonAncestor(ptypes.get(i).getType()); 283 } 284 } 285 } 286 assert commonType != null; 287 return commonType; 288 } 289 290 private ResolvedJavaType getLeastCommonType() { 291 ResolvedJavaType result = getLeastCommonType(0); 292 for (int i = 1; i < concretes.size(); i++) { 293 result = result.findLeastCommonAncestor(getLeastCommonType(i)); 294 } 295 return result; 296 } 297 298 private Collection<Node> inlineSingleMethod(StructuredGraph graph, StampProvider stampProvider) { 299 assert concretes.size() == 1 && inlineableElements.length == 1 && ptypes.size() > 1 && !shouldFallbackToInvoke() && notRecordedTypeProbability == 0; 300 301 AbstractBeginNode calleeEntryNode = graph.add(new BeginNode()); 302 303 AbstractBeginNode unknownTypeSux = createUnknownTypeSuccessor(graph); 304 AbstractBeginNode[] successors = new AbstractBeginNode[]{calleeEntryNode, unknownTypeSux}; 305 createDispatchOnTypeBeforeInvoke(graph, successors, false, stampProvider); 306 307 calleeEntryNode.setNext(invoke.asNode()); 308 309 return inline(invoke, methodAt(0), inlineableElementAt(0), false); 310 } 311 312 private boolean createDispatchOnTypeBeforeInvoke(StructuredGraph graph, AbstractBeginNode[] successors, boolean invokeIsOnlySuccessor, StampProvider stampProvider) { 313 assert ptypes.size() >= 1; 314 ValueNode nonNullReceiver = InliningUtil.nonNullReceiver(invoke); 315 LoadHubNode hub = graph.unique(new LoadHubNode(stampProvider, nonNullReceiver)); 316 317 Debug.log("Type switch with %d types", concretes.size()); 318 319 ResolvedJavaType[] keys = new ResolvedJavaType[ptypes.size()]; 320 double[] keyProbabilities = new double[ptypes.size() + 1]; 321 int[] keySuccessors = new int[ptypes.size() + 1]; 322 double totalProbability = notRecordedTypeProbability; 323 for (int i = 0; i < ptypes.size(); i++) { 324 keys[i] = ptypes.get(i).getType(); 325 keyProbabilities[i] = ptypes.get(i).getProbability(); 326 totalProbability += keyProbabilities[i]; 327 keySuccessors[i] = invokeIsOnlySuccessor ? 0 : typesToConcretes.get(i); 328 assert keySuccessors[i] < successors.length - 1 : "last successor is the unknownTypeSux"; 329 } 330 keyProbabilities[keyProbabilities.length - 1] = notRecordedTypeProbability; 331 keySuccessors[keySuccessors.length - 1] = successors.length - 1; 332 333 // Normalize the probabilities. 334 for (int i = 0; i < keyProbabilities.length; i++) { 335 keyProbabilities[i] /= totalProbability; 336 } 337 338 TypeSwitchNode typeSwitch = graph.add(new TypeSwitchNode(hub, successors, keys, keyProbabilities, keySuccessors)); 339 FixedWithNextNode pred = (FixedWithNextNode) invoke.asNode().predecessor(); 340 pred.setNext(typeSwitch); 341 return false; 342 } 343 344 private static AbstractBeginNode createInvocationBlock(StructuredGraph graph, Invoke invoke, AbstractMergeNode returnMerge, PhiNode returnValuePhi, AbstractMergeNode exceptionMerge, 345 PhiNode exceptionObjectPhi, boolean useForInlining) { 346 Invoke duplicatedInvoke = duplicateInvokeForInlining(graph, invoke, exceptionMerge, exceptionObjectPhi, useForInlining); 347 AbstractBeginNode calleeEntryNode = graph.add(new BeginNode()); 348 calleeEntryNode.setNext(duplicatedInvoke.asNode()); 349 350 EndNode endNode = graph.add(new EndNode()); 351 duplicatedInvoke.setNext(endNode); 352 returnMerge.addForwardEnd(endNode); 353 354 if (returnValuePhi != null) { 355 returnValuePhi.addInput(duplicatedInvoke.asNode()); 356 } 357 return calleeEntryNode; 358 } 359 360 private static Invoke duplicateInvokeForInlining(StructuredGraph graph, Invoke invoke, AbstractMergeNode exceptionMerge, PhiNode exceptionObjectPhi, boolean useForInlining) { 361 Invoke result = (Invoke) invoke.asNode().copyWithInputs(); 362 Node callTarget = result.callTarget().copyWithInputs(); 363 result.asNode().replaceFirstInput(result.callTarget(), callTarget); 364 result.setUseForInlining(useForInlining); 365 366 Kind kind = invoke.asNode().getKind(); 367 if (kind != Kind.Void) { 368 FrameState stateAfter = invoke.stateAfter(); 369 stateAfter = stateAfter.duplicate(stateAfter.bci); 370 stateAfter.replaceFirstInput(invoke.asNode(), result.asNode()); 371 result.setStateAfter(stateAfter); 372 } 373 374 if (invoke instanceof InvokeWithExceptionNode) { 375 assert exceptionMerge != null && exceptionObjectPhi != null; 376 377 InvokeWithExceptionNode invokeWithException = (InvokeWithExceptionNode) invoke; 378 ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithException.exceptionEdge(); 379 FrameState stateAfterException = exceptionEdge.stateAfter(); 380 381 ExceptionObjectNode newExceptionEdge = (ExceptionObjectNode) exceptionEdge.copyWithInputs(); 382 // set new state (pop old exception object, push new one) 383 newExceptionEdge.setStateAfter(stateAfterException.duplicateModified(Kind.Object, Kind.Object, newExceptionEdge)); 384 385 EndNode endNode = graph.add(new EndNode()); 386 newExceptionEdge.setNext(endNode); 387 exceptionMerge.addForwardEnd(endNode); 388 exceptionObjectPhi.addInput(newExceptionEdge); 389 390 ((InvokeWithExceptionNode) result).setExceptionEdge(newExceptionEdge); 391 } 392 return result; 393 } 394 395 @Override 396 public void tryToDevirtualizeInvoke(Providers providers) { 397 if (hasSingleMethod()) { 398 devirtualizeWithTypeSwitch(graph(), InvokeKind.Special, concretes.get(0), providers.getStampProvider()); 399 } else { 400 tryToDevirtualizeMultipleMethods(graph(), providers.getStampProvider()); 401 } 402 } 403 404 private void tryToDevirtualizeMultipleMethods(StructuredGraph graph, StampProvider stampProvider) { 405 MethodCallTargetNode methodCallTarget = (MethodCallTargetNode) invoke.callTarget(); 406 if (methodCallTarget.invokeKind() == InvokeKind.Interface) { 407 ResolvedJavaMethod targetMethod = methodCallTarget.targetMethod(); 408 ResolvedJavaType leastCommonType = getLeastCommonType(); 409 ResolvedJavaType contextType = invoke.getContextType(); 410 // check if we have a common base type that implements the interface -> in that case 411 // we have a vtable entry for the interface method and can use a less expensive 412 // virtual call 413 if (!leastCommonType.isInterface() && targetMethod.getDeclaringClass().isAssignableFrom(leastCommonType)) { 414 ResolvedJavaMethod baseClassTargetMethod = leastCommonType.resolveConcreteMethod(targetMethod, contextType); 415 if (baseClassTargetMethod != null) { 416 devirtualizeWithTypeSwitch(graph, InvokeKind.Virtual, leastCommonType.resolveConcreteMethod(targetMethod, contextType), stampProvider); 417 } 418 } 419 } 420 } 421 422 private void devirtualizeWithTypeSwitch(StructuredGraph graph, InvokeKind kind, ResolvedJavaMethod target, StampProvider stampProvider) { 423 AbstractBeginNode invocationEntry = graph.add(new BeginNode()); 424 AbstractBeginNode unknownTypeSux = createUnknownTypeSuccessor(graph); 425 AbstractBeginNode[] successors = new AbstractBeginNode[]{invocationEntry, unknownTypeSux}; 426 createDispatchOnTypeBeforeInvoke(graph, successors, true, stampProvider); 427 428 invocationEntry.setNext(invoke.asNode()); 429 ValueNode receiver = ((MethodCallTargetNode) invoke.callTarget()).receiver(); 430 GuardedValueNode anchoredReceiver = InliningUtil.createAnchoredReceiver(graph, invocationEntry, target.getDeclaringClass(), receiver, false); 431 invoke.callTarget().replaceFirstInput(receiver, anchoredReceiver); 432 InliningUtil.replaceInvokeCallTarget(invoke, graph, kind, target); 433 } 434 435 private static AbstractBeginNode createUnknownTypeSuccessor(StructuredGraph graph) { 436 return BeginNode.begin(graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated))); 437 } 438 439 @Override 440 public String toString() { 441 StringBuilder builder = new StringBuilder(shouldFallbackToInvoke() ? "megamorphic" : "polymorphic"); 442 builder.append(", "); 443 builder.append(concretes.size()); 444 builder.append(" methods [ "); 445 for (int i = 0; i < concretes.size(); i++) { 446 builder.append(concretes.get(i).format(" %H.%n(%p):%r")); 447 } 448 builder.append(" ], "); 449 builder.append(ptypes.size()); 450 builder.append(" type checks [ "); 451 for (int i = 0; i < ptypes.size(); i++) { 452 builder.append(" "); 453 builder.append(ptypes.get(i).getType().getName()); 454 builder.append(ptypes.get(i).getProbability()); 455 } 456 builder.append(" ]"); 457 return builder.toString(); 458 } 459}