1 /*
2 * Copyright (c) 2012, 2015, 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 org.graalvm.compiler.phases.common.inlining;
24
25 import static jdk.vm.ci.meta.DeoptimizationAction.InvalidateReprofile;
26 import static jdk.vm.ci.meta.DeoptimizationReason.NullCheckException;
27 import static org.graalvm.compiler.core.common.GraalOptions.HotSpotPrintInlining;
28
29 import java.lang.reflect.Constructor;
30 import java.util.ArrayDeque;
31 import java.util.ArrayList;
32 import java.util.List;
33 import java.util.function.Consumer;
34
35 import org.graalvm.compiler.api.replacements.MethodSubstitution;
36 import org.graalvm.compiler.core.common.GraalOptions;
37 import org.graalvm.compiler.core.common.type.Stamp;
38 import org.graalvm.compiler.core.common.type.StampFactory;
39 import org.graalvm.compiler.core.common.type.TypeReference;
40 import org.graalvm.compiler.core.common.util.Util;
41 import org.graalvm.compiler.debug.DebugContext;
42 import org.graalvm.compiler.debug.GraalError;
43 import org.graalvm.compiler.graph.GraalGraphError;
44 import org.graalvm.compiler.graph.Graph;
45 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
46 import org.graalvm.compiler.graph.Graph.NodeEventScope;
47 import org.graalvm.compiler.graph.Node;
48 import org.graalvm.compiler.graph.NodeInputList;
49 import org.graalvm.compiler.graph.NodeMap;
50 import org.graalvm.compiler.graph.NodeSourcePosition;
51 import org.graalvm.compiler.graph.NodeWorkList;
52 import org.graalvm.compiler.nodeinfo.Verbosity;
53 import org.graalvm.compiler.nodes.AbstractBeginNode;
54 import org.graalvm.compiler.nodes.AbstractEndNode;
55 import org.graalvm.compiler.nodes.AbstractMergeNode;
56 import org.graalvm.compiler.nodes.BeginNode;
57 import org.graalvm.compiler.nodes.CallTargetNode;
58 import org.graalvm.compiler.nodes.CallTargetNode.InvokeKind;
59 import org.graalvm.compiler.nodes.DeoptimizeNode;
60 import org.graalvm.compiler.nodes.EndNode;
61 import org.graalvm.compiler.nodes.FixedGuardNode;
62 import org.graalvm.compiler.nodes.FixedNode;
63 import org.graalvm.compiler.nodes.FixedWithNextNode;
64 import org.graalvm.compiler.nodes.FrameState;
65 import org.graalvm.compiler.nodes.Invoke;
66 import org.graalvm.compiler.nodes.InvokeNode;
67 import org.graalvm.compiler.nodes.InvokeWithExceptionNode;
68 import org.graalvm.compiler.nodes.KillingBeginNode;
69 import org.graalvm.compiler.nodes.LogicNode;
70 import org.graalvm.compiler.nodes.MergeNode;
71 import org.graalvm.compiler.nodes.ParameterNode;
72 import org.graalvm.compiler.nodes.PhiNode;
73 import org.graalvm.compiler.nodes.PiNode;
74 import org.graalvm.compiler.nodes.ReturnNode;
75 import org.graalvm.compiler.nodes.StartNode;
76 import org.graalvm.compiler.nodes.StateSplit;
77 import org.graalvm.compiler.nodes.StructuredGraph;
78 import org.graalvm.compiler.nodes.UnwindNode;
79 import org.graalvm.compiler.nodes.ValueNode;
80 import org.graalvm.compiler.nodes.calc.IsNullNode;
81 import org.graalvm.compiler.nodes.extended.ForeignCallNode;
82 import org.graalvm.compiler.nodes.extended.GuardingNode;
83 import org.graalvm.compiler.nodes.java.ExceptionObjectNode;
84 import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
85 import org.graalvm.compiler.nodes.java.MonitorExitNode;
86 import org.graalvm.compiler.nodes.java.MonitorIdNode;
87 import org.graalvm.compiler.nodes.spi.Replacements;
88 import org.graalvm.compiler.nodes.type.StampTool;
89 import org.graalvm.compiler.nodes.util.GraphUtil;
90 import org.graalvm.compiler.phases.common.inlining.info.InlineInfo;
91 import org.graalvm.compiler.phases.common.util.HashSetNodeEventListener;
92 import org.graalvm.compiler.phases.util.ValueMergeUtil;
93 import org.graalvm.util.EconomicMap;
94 import org.graalvm.util.EconomicSet;
95 import org.graalvm.util.Equivalence;
96 import org.graalvm.util.UnmodifiableEconomicMap;
97 import org.graalvm.util.UnmodifiableMapCursor;
98
99 import jdk.vm.ci.code.BytecodeFrame;
100 import jdk.vm.ci.meta.Assumptions;
101 import jdk.vm.ci.meta.DeoptimizationAction;
102 import jdk.vm.ci.meta.DeoptimizationReason;
103 import jdk.vm.ci.meta.JavaConstant;
104 import jdk.vm.ci.meta.JavaKind;
105 import jdk.vm.ci.meta.ResolvedJavaMethod;
106 import jdk.vm.ci.meta.ResolvedJavaType;
107
108 public class InliningUtil extends ValueMergeUtil {
109
110 private static final String inliningDecisionsScopeString = "InliningDecisions";
111
112 /**
113 * Print a HotSpot-style inlining message to the console.
114 */
115 private static void printInlining(final InlineInfo info, final int inliningDepth, final boolean success, final String msg, final Object... args) {
116 printInlining(info.methodAt(0), info.invoke(), inliningDepth, success, msg, args);
117 }
118
119 private static void printInlining(final ResolvedJavaMethod method, final Invoke invoke, final int inliningDepth, final boolean success, final String msg, final Object... args) {
120 if (HotSpotPrintInlining.getValue(invoke.asNode().getOptions())) {
121 Util.printInlining(method, invoke.bci(), inliningDepth, success, msg, args);
122 }
123 }
124
125 public static void logInlinedMethod(InlineInfo info, int inliningDepth, boolean allowLogging, String msg, Object... args) {
126 logInliningDecision(info, inliningDepth, allowLogging, true, msg, args);
127 }
128
129 public static void logNotInlinedMethod(InlineInfo info, int inliningDepth, String msg, Object... args) {
130 logInliningDecision(info, inliningDepth, true, false, msg, args);
131 }
132
133 public static void logInliningDecision(InlineInfo info, int inliningDepth, boolean allowLogging, boolean success, String msg, final Object... args) {
134 if (allowLogging) {
135 printInlining(info, inliningDepth, success, msg, args);
136 DebugContext debug = info.graph().getDebug();
137 if (shouldLogInliningDecision(debug)) {
138 logInliningDecision(debug, methodName(info), success, msg, args);
139 }
140 }
141 }
142
143 @SuppressWarnings("try")
144 public static void logInliningDecision(DebugContext debug, final String msg, final Object... args) {
145 try (DebugContext.Scope s = debug.scope(inliningDecisionsScopeString)) {
146 // Can't use log here since we are varargs
147 if (debug.isLogEnabled()) {
148 debug.logv(msg, args);
149 }
150 }
151 }
152
153 public static void logNotInlinedMethod(Invoke invoke, String msg) {
154 DebugContext debug = invoke.asNode().getDebug();
155 if (shouldLogInliningDecision(debug)) {
156 String methodString = invoke.toString();
157 if (invoke.callTarget() == null) {
158 methodString += " callTarget=null";
159 } else {
160 String targetName = invoke.callTarget().targetName();
161 if (!methodString.endsWith(targetName)) {
162 methodString += " " + targetName;
163 }
164 }
165 logInliningDecision(debug, methodString, false, msg, new Object[0]);
166 }
167 }
168
169 public static void logNotInlined(Invoke invoke, int inliningDepth, ResolvedJavaMethod method, String msg) {
170 logNotInlinedInvoke(invoke, inliningDepth, method, msg, new Object[0]);
171 }
172
173 public static void logNotInlinedInvoke(Invoke invoke, int inliningDepth, ResolvedJavaMethod method, String msg, Object... args) {
174 DebugContext debug = invoke.asNode().getDebug();
175 printInlining(method, invoke, inliningDepth, false, msg, args);
176 if (shouldLogInliningDecision(debug)) {
177 String methodString = methodName(method, invoke);
178 logInliningDecision(debug, methodString, false, msg, args);
179 }
180 }
181
182 private static void logInliningDecision(DebugContext debug, final String methodString, final boolean success, final String msg, final Object... args) {
183 String inliningMsg = "inlining " + methodString + ": " + msg;
184 if (!success) {
185 inliningMsg = "not " + inliningMsg;
186 }
187 logInliningDecision(debug, inliningMsg, args);
188 }
189
190 @SuppressWarnings("try")
191 public static boolean shouldLogInliningDecision(DebugContext debug) {
192 try (DebugContext.Scope s = debug.scope(inliningDecisionsScopeString)) {
193 return debug.isLogEnabled();
194 }
195 }
196
197 private static String methodName(ResolvedJavaMethod method, Invoke invoke) {
198 if (invoke != null && invoke.stateAfter() != null) {
199 return methodName(invoke.stateAfter(), invoke.bci()) + ": " + method.format("%H.%n(%p):%r") + " (" + method.getCodeSize() + " bytes)";
200 } else {
201 return method.format("%H.%n(%p):%r") + " (" + method.getCodeSize() + " bytes)";
202 }
203 }
204
205 private static String methodName(InlineInfo info) {
206 if (info == null) {
207 return "null";
208 } else if (info.invoke() != null && info.invoke().stateAfter() != null) {
209 return methodName(info.invoke().stateAfter(), info.invoke().bci()) + ": " + info.toString();
210 } else {
211 return info.toString();
212 }
213 }
214
215 private static String methodName(FrameState frameState, int bci) {
216 StringBuilder sb = new StringBuilder();
217 if (frameState.outerFrameState() != null) {
218 sb.append(methodName(frameState.outerFrameState(), frameState.outerFrameState().bci));
219 sb.append("->");
220 }
221 ResolvedJavaMethod method = frameState.getMethod();
222 sb.append(method != null ? method.format("%h.%n") : "?");
223 sb.append("@").append(bci);
224 return sb.toString();
225 }
226
227 public static void replaceInvokeCallTarget(Invoke invoke, StructuredGraph graph, InvokeKind invokeKind, ResolvedJavaMethod targetMethod) {
228 MethodCallTargetNode oldCallTarget = (MethodCallTargetNode) invoke.callTarget();
229 MethodCallTargetNode newCallTarget = graph.add(new MethodCallTargetNode(invokeKind, targetMethod, oldCallTarget.arguments().toArray(new ValueNode[0]), oldCallTarget.returnStamp(),
230 oldCallTarget.getProfile()));
231 invoke.asNode().replaceFirstInput(oldCallTarget, newCallTarget);
232 }
233
234 public static PiNode createAnchoredReceiver(StructuredGraph graph, GuardingNode anchor, ResolvedJavaType commonType, ValueNode receiver, boolean exact) {
235 return createAnchoredReceiver(graph, anchor, receiver,
236 exact ? StampFactory.objectNonNull(TypeReference.createExactTrusted(commonType)) : StampFactory.objectNonNull(TypeReference.createTrusted(graph.getAssumptions(), commonType)));
237 }
238
239 private static PiNode createAnchoredReceiver(StructuredGraph graph, GuardingNode anchor, ValueNode receiver, Stamp stamp) {
240 // to avoid that floating reads on receiver fields float above the type check
241 return graph.unique(new PiNode(receiver, stamp, (ValueNode) anchor));
242 }
243
244 /**
245 * @return null iff the check succeeds, otherwise a (non-null) descriptive message.
246 */
247 public static String checkInvokeConditions(Invoke invoke) {
248 if (invoke.predecessor() == null || !invoke.asNode().isAlive()) {
249 return "the invoke is dead code";
250 }
251 if (!(invoke.callTarget() instanceof MethodCallTargetNode)) {
252 return "the invoke has already been lowered, or has been created as a low-level node";
253 }
254 MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget();
255 if (callTarget.targetMethod() == null) {
256 return "target method is null";
257 }
258 assert invoke.stateAfter() != null : invoke;
259 if (!invoke.useForInlining()) {
260 return "the invoke is marked to be not used for inlining";
261 }
262 ValueNode receiver = callTarget.receiver();
263 if (receiver != null && receiver.isConstant() && receiver.isNullConstant()) {
264 return "receiver is null";
265 }
266 return null;
267 }
268
269 /**
270 * Performs an actual inlining, thereby replacing the given invoke with the given inlineGraph.
271 *
272 * @param invoke the invoke that will be replaced
273 * @param inlineGraph the graph that the invoke will be replaced with
274 * @param receiverNullCheck true if a null check needs to be generated for non-static inlinings,
275 * false if no such check is required
276 * @param inlineeMethod the actual method being inlined. Maybe be null for snippets.
277 */
278 @SuppressWarnings("try")
279 public static UnmodifiableEconomicMap<Node, Node> inline(Invoke invoke, StructuredGraph inlineGraph, boolean receiverNullCheck, ResolvedJavaMethod inlineeMethod) {
280 FixedNode invokeNode = invoke.asNode();
281 StructuredGraph graph = invokeNode.graph();
282 final NodeInputList<ValueNode> parameters = invoke.callTarget().arguments();
283
284 assert inlineGraph.getGuardsStage().ordinal() >= graph.getGuardsStage().ordinal();
285 assert !invokeNode.graph().isAfterFloatingReadPhase() : "inline isn't handled correctly after floating reads phase";
286
287 if (receiverNullCheck && !((MethodCallTargetNode) invoke.callTarget()).isStatic()) {
288 nonNullReceiver(invoke);
289 }
290
291 ArrayList<Node> nodes = new ArrayList<>(inlineGraph.getNodes().count());
292 ArrayList<ReturnNode> returnNodes = new ArrayList<>(4);
293 ArrayList<Invoke> partialIntrinsicExits = new ArrayList<>();
294 UnwindNode unwindNode = null;
295 final StartNode entryPointNode = inlineGraph.start();
296 FixedNode firstCFGNode = entryPointNode.next();
297 if (firstCFGNode == null) {
298 throw new IllegalStateException("Inlined graph is in invalid state: " + inlineGraph);
299 }
300 for (Node node : inlineGraph.getNodes()) {
301 if (node == entryPointNode || (node == entryPointNode.stateAfter() && node.usages().count() == 1) || node instanceof ParameterNode) {
302 // Do nothing.
303 } else {
304 nodes.add(node);
305 if (node instanceof ReturnNode) {
306 returnNodes.add((ReturnNode) node);
307 } else if (node instanceof Invoke) {
308 Invoke invokeInInlineGraph = (Invoke) node;
309 if (invokeInInlineGraph.bci() == BytecodeFrame.UNKNOWN_BCI) {
310 ResolvedJavaMethod target1 = inlineeMethod;
311 ResolvedJavaMethod target2 = invokeInInlineGraph.callTarget().targetMethod();
312 assert target1.equals(target2) : String.format("invoke in inlined method expected to be partial intrinsic exit (i.e., call to %s), not a call to %s",
313 target1.format("%H.%n(%p)"), target2.format("%H.%n(%p)"));
314 partialIntrinsicExits.add(invokeInInlineGraph);
315 }
316 } else if (node instanceof UnwindNode) {
317 assert unwindNode == null;
318 unwindNode = (UnwindNode) node;
319 }
320 }
321 }
322
323 final AbstractBeginNode prevBegin = AbstractBeginNode.prevBegin(invokeNode);
324 DuplicationReplacement localReplacement = new DuplicationReplacement() {
325
326 @Override
327 public Node replacement(Node node) {
328 if (node instanceof ParameterNode) {
329 return parameters.get(((ParameterNode) node).index());
330 } else if (node == entryPointNode) {
331 return prevBegin;
332 }
333 return node;
334 }
335 };
336
337 assert invokeNode.successors().first() != null : invoke;
338 assert invokeNode.predecessor() != null;
339
340 EconomicMap<Node, Node> duplicates = graph.addDuplicates(nodes, inlineGraph, inlineGraph.getNodeCount(), localReplacement);
341
342 FrameState stateAfter = invoke.stateAfter();
343 assert stateAfter == null || stateAfter.isAlive();
344
345 FrameState stateAtExceptionEdge = null;
346 if (invoke instanceof InvokeWithExceptionNode) {
347 InvokeWithExceptionNode invokeWithException = ((InvokeWithExceptionNode) invoke);
348 if (unwindNode != null) {
349 ExceptionObjectNode obj = (ExceptionObjectNode) invokeWithException.exceptionEdge();
350 stateAtExceptionEdge = obj.stateAfter();
351 }
352 }
353
354 updateSourcePositions(invoke, inlineGraph, duplicates);
355 if (stateAfter != null) {
356 processFrameStates(invoke, inlineGraph, duplicates, stateAtExceptionEdge, returnNodes.size() > 1);
357 int callerLockDepth = stateAfter.nestedLockDepth();
358 if (callerLockDepth != 0) {
359 for (MonitorIdNode original : inlineGraph.getNodes(MonitorIdNode.TYPE)) {
360 MonitorIdNode monitor = (MonitorIdNode) duplicates.get(original);
361 processMonitorId(invoke.stateAfter(), monitor);
362 }
363 }
364 } else {
365 assert checkContainsOnlyInvalidOrAfterFrameState(duplicates);
366 }
367
368 firstCFGNode = (FixedNode) duplicates.get(firstCFGNode);
369 for (int i = 0; i < returnNodes.size(); i++) {
370 returnNodes.set(i, (ReturnNode) duplicates.get(returnNodes.get(i)));
371 }
372 for (Invoke exit : partialIntrinsicExits) {
373 // A partial intrinsic exit must be replaced with a call to
374 // the intrinsified method.
375 Invoke dup = (Invoke) duplicates.get(exit.asNode());
376 if (dup instanceof InvokeNode) {
377 InvokeNode repl = graph.add(new InvokeNode(invoke.callTarget(), invoke.bci()));
378 dup.intrinsify(repl.asNode());
379 } else {
380 ((InvokeWithExceptionNode) dup).replaceWithNewBci(invoke.bci());
381 }
382 }
383 if (unwindNode != null) {
384 unwindNode = (UnwindNode) duplicates.get(unwindNode);
385 }
386
387 finishInlining(invoke, graph, firstCFGNode, returnNodes, unwindNode, inlineGraph.getAssumptions(), inlineGraph);
388 GraphUtil.killCFG(invokeNode);
389
390 return duplicates;
391 }
392
393 /**
394 * Inline {@code inlineGraph} into the current replacing the node {@code Invoke} and return the
395 * set of nodes which should be canonicalized. The set should only contain nodes which modified
396 * by the inlining since the current graph and {@code inlineGraph} are expected to already be
397 * canonical.
398 *
399 * @param invoke
400 * @param inlineGraph
401 * @param receiverNullCheck
402 * @param inlineeMethod
403 * @return the set of nodes to canonicalize
404 */
405 @SuppressWarnings("try")
406 public static EconomicSet<Node> inlineForCanonicalization(Invoke invoke, StructuredGraph inlineGraph, boolean receiverNullCheck, ResolvedJavaMethod inlineeMethod) {
407 return inlineForCanonicalization(invoke, inlineGraph, receiverNullCheck, inlineeMethod, null);
408 }
409
410 @SuppressWarnings("try")
411 public static EconomicSet<Node> inlineForCanonicalization(Invoke invoke, StructuredGraph inlineGraph, boolean receiverNullCheck, ResolvedJavaMethod inlineeMethod,
412 Consumer<UnmodifiableEconomicMap<Node, Node>> duplicatesConsumer) {
413 HashSetNodeEventListener listener = new HashSetNodeEventListener();
414 /*
415 * This code relies on the fact that Graph.addDuplicates doesn't trigger the
416 * NodeEventListener to track only nodes which were modified into the process of inlining
417 * the graph into the current graph.
418 */
419 try (NodeEventScope nes = invoke.asNode().graph().trackNodeEvents(listener)) {
420 UnmodifiableEconomicMap<Node, Node> duplicates = InliningUtil.inline(invoke, inlineGraph, receiverNullCheck, inlineeMethod);
421 if (duplicatesConsumer != null) {
422 duplicatesConsumer.accept(duplicates);
423 }
424 }
425 return listener.getNodes();
426 }
427
428 private static ValueNode finishInlining(Invoke invoke, StructuredGraph graph, FixedNode firstNode, List<ReturnNode> returnNodes, UnwindNode unwindNode, Assumptions inlinedAssumptions,
429 StructuredGraph inlineGraph) {
430 FixedNode invokeNode = invoke.asNode();
431 FrameState stateAfter = invoke.stateAfter();
432 assert stateAfter == null || stateAfter.isAlive();
433
434 invokeNode.replaceAtPredecessor(firstNode);
435
436 if (invoke instanceof InvokeWithExceptionNode) {
437 InvokeWithExceptionNode invokeWithException = ((InvokeWithExceptionNode) invoke);
438 if (unwindNode != null && unwindNode.isAlive()) {
439 assert unwindNode.predecessor() != null;
440 assert invokeWithException.exceptionEdge().successors().count() == 1;
441 ExceptionObjectNode obj = (ExceptionObjectNode) invokeWithException.exceptionEdge();
442 obj.replaceAtUsages(unwindNode.exception());
443 Node n = obj.next();
444 obj.setNext(null);
445 unwindNode.replaceAndDelete(n);
446
447 obj.replaceAtPredecessor(null);
448 obj.safeDelete();
449 } else {
450 invokeWithException.killExceptionEdge();
451 }
452
453 // get rid of memory kill
454 AbstractBeginNode begin = invokeWithException.next();
455 if (begin instanceof KillingBeginNode) {
456 AbstractBeginNode newBegin = new BeginNode();
457 graph.addAfterFixed(begin, graph.add(newBegin));
458 begin.replaceAtUsages(newBegin);
459 graph.removeFixed(begin);
460 }
461 } else {
462 if (unwindNode != null && unwindNode.isAlive()) {
463 DeoptimizeNode deoptimizeNode = graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateRecompile, DeoptimizationReason.NotCompiledExceptionHandler));
464 unwindNode.replaceAndDelete(deoptimizeNode);
465 }
466 }
467
468 ValueNode returnValue;
469 if (!returnNodes.isEmpty()) {
470 FixedNode n = invoke.next();
471 invoke.setNext(null);
472 if (returnNodes.size() == 1) {
473 ReturnNode returnNode = returnNodes.get(0);
474 returnValue = returnNode.result();
475 invokeNode.replaceAtUsages(returnValue);
476 returnNode.replaceAndDelete(n);
477 } else {
478 MergeNode merge = graph.add(new MergeNode());
479 merge.setStateAfter(stateAfter);
480 returnValue = mergeReturns(merge, returnNodes);
481 invokeNode.replaceAtUsages(returnValue);
482 if (merge.isPhiAtMerge(returnValue)) {
483 fixFrameStates(graph, merge, (PhiNode) returnValue);
484 }
485 merge.setNext(n);
486 }
487 } else {
488 returnValue = null;
489 invokeNode.replaceAtUsages(null);
490 GraphUtil.killCFG(invoke.next());
491 }
492
493 // Copy assumptions from inlinee to caller
494 Assumptions assumptions = graph.getAssumptions();
495 if (assumptions != null) {
496 if (inlinedAssumptions != null) {
497 assumptions.record(inlinedAssumptions);
498 }
499 } else {
500 assert inlinedAssumptions == null : String.format("cannot inline graph (%s) which makes assumptions into a graph (%s) that doesn't", inlineGraph, graph);
501 }
502
503 // Copy inlined methods from inlinee to caller
504 graph.updateMethods(inlineGraph);
505
506 // Update the set of accessed fields
507 if (GraalOptions.GeneratePIC.getValue(graph.getOptions())) {
508 graph.updateFields(inlineGraph);
509 }
510
511 if (inlineGraph.hasUnsafeAccess()) {
512 graph.markUnsafeAccess();
513 }
514 assert inlineGraph.getSpeculationLog() == null || inlineGraph.getSpeculationLog() == graph.getSpeculationLog() : "Only the root graph should have a speculation log";
515
516 return returnValue;
517 }
518
519 private static void fixFrameStates(StructuredGraph graph, MergeNode originalMerge, PhiNode returnPhi) {
520 // It is possible that some of the frame states that came from AFTER_BCI reference a Phi
521 // node that was created to merge multiple returns. This can create cycles
522 // (see GR-3949 and GR-3957).
523 // To detect this, we follow the control paths starting from the merge node,
524 // split the Phi node inputs at merges and assign the proper input to each frame state.
525 NodeMap<Node> seen = new NodeMap<>(graph);
526 ArrayDeque<Node> workList = new ArrayDeque<>();
527 ArrayDeque<ValueNode> valueList = new ArrayDeque<>();
528 workList.push(originalMerge);
529 valueList.push(returnPhi);
530 while (!workList.isEmpty()) {
531 Node current = workList.pop();
532 ValueNode currentValue = valueList.pop();
533 if (seen.containsKey(current)) {
534 continue;
535 }
536 seen.put(current, current);
537 if (current instanceof StateSplit && current != originalMerge) {
538 StateSplit stateSplit = (StateSplit) current;
539 FrameState state = stateSplit.stateAfter();
540 if (state != null && state.values().contains(returnPhi)) {
541 int index = 0;
542 FrameState duplicate = state.duplicate();
543 for (ValueNode value : state.values()) {
544 if (value == returnPhi) {
545 duplicate.values().set(index, currentValue);
546 }
547 index++;
548 }
549 stateSplit.setStateAfter(duplicate);
550 GraphUtil.tryKillUnused(state);
551 }
552 }
553 if (current instanceof AbstractMergeNode) {
554 AbstractMergeNode currentMerge = (AbstractMergeNode) current;
555 for (EndNode pred : currentMerge.cfgPredecessors()) {
556 ValueNode newValue = currentValue;
557 if (currentMerge.isPhiAtMerge(currentValue)) {
558 PhiNode currentPhi = (PhiNode) currentValue;
559 newValue = currentPhi.valueAt(pred);
560 }
561 workList.push(pred);
562 valueList.push(newValue);
563 }
564 } else if (current.predecessor() != null) {
565 workList.push(current.predecessor());
566 valueList.push(currentValue);
567 }
568 }
569 }
570
571 @SuppressWarnings("try")
572 private static void updateSourcePositions(Invoke invoke, StructuredGraph inlineGraph, UnmodifiableEconomicMap<Node, Node> duplicates) {
573 if (inlineGraph.mayHaveNodeSourcePosition() && invoke.stateAfter() != null) {
574 if (invoke.asNode().getNodeSourcePosition() == null) {
575 // Temporarily ignore the assert below.
576 return;
577 }
578
579 JavaConstant constantReceiver = invoke.getInvokeKind().hasReceiver() ? invoke.getReceiver().asJavaConstant() : null;
580 NodeSourcePosition invokePos = invoke.asNode().getNodeSourcePosition();
581 assert invokePos != null : "missing source information";
582
583 EconomicMap<NodeSourcePosition, NodeSourcePosition> posMap = EconomicMap.create(Equivalence.DEFAULT);
584 UnmodifiableMapCursor<Node, Node> cursor = duplicates.getEntries();
585 while (cursor.advance()) {
586 NodeSourcePosition pos = cursor.getKey().getNodeSourcePosition();
587 if (pos != null) {
588 NodeSourcePosition callerPos = pos.addCaller(constantReceiver, invokePos);
589 if (!posMap.containsKey(callerPos)) {
590 posMap.put(callerPos, callerPos);
591 }
592 cursor.getValue().setNodeSourcePosition(posMap.get(callerPos));
593 }
594 }
595 }
596 }
597
598 public static void processMonitorId(FrameState stateAfter, MonitorIdNode monitorIdNode) {
599 if (stateAfter != null) {
600 int callerLockDepth = stateAfter.nestedLockDepth();
601 monitorIdNode.setLockDepth(monitorIdNode.getLockDepth() + callerLockDepth);
602 }
603 }
604
605 protected static void processFrameStates(Invoke invoke, StructuredGraph inlineGraph, EconomicMap<Node, Node> duplicates, FrameState stateAtExceptionEdge,
606 boolean alwaysDuplicateStateAfter) {
607 FrameState stateAtReturn = invoke.stateAfter();
608 FrameState outerFrameState = null;
609 JavaKind invokeReturnKind = invoke.asNode().getStackKind();
610 EconomicMap<Node, Node> replacements = EconomicMap.create();
611 for (FrameState original : inlineGraph.getNodes(FrameState.TYPE)) {
612 FrameState frameState = (FrameState) duplicates.get(original);
613 if (frameState != null && frameState.isAlive()) {
614 if (outerFrameState == null) {
615 outerFrameState = stateAtReturn.duplicateModifiedDuringCall(invoke.bci(), invokeReturnKind);
616 }
617 processFrameState(frameState, invoke, replacements, inlineGraph.method(), stateAtExceptionEdge, outerFrameState, alwaysDuplicateStateAfter, invoke.callTarget().targetMethod(),
618 invoke.callTarget().arguments());
619 }
620 }
621 // If processing the frame states replaced any nodes, update the duplicates map.
622 duplicates.replaceAll((key, value) -> replacements.containsKey(value) ? replacements.get(value) : value);
623 }
624
625 public static FrameState processFrameState(FrameState frameState, Invoke invoke, EconomicMap<Node, Node> replacements, ResolvedJavaMethod inlinedMethod, FrameState stateAtExceptionEdge,
626 FrameState outerFrameState,
627 boolean alwaysDuplicateStateAfter, ResolvedJavaMethod invokeTargetMethod, List<ValueNode> invokeArgsList) {
628 assert outerFrameState == null || !outerFrameState.isDeleted() : outerFrameState;
629 final FrameState stateAtReturn = invoke.stateAfter();
630 JavaKind invokeReturnKind = invoke.asNode().getStackKind();
631
632 if (frameState.bci == BytecodeFrame.AFTER_BCI) {
633 return handleAfterBciFrameState(frameState, invoke, alwaysDuplicateStateAfter);
634 } else if (stateAtExceptionEdge != null && isStateAfterException(frameState)) {
635 // pop exception object from invoke's stateAfter and replace with this frameState's
636 // exception object (top of stack)
637 FrameState stateAfterException = stateAtExceptionEdge;
638 if (frameState.stackSize() > 0 && stateAtExceptionEdge.stackAt(0) != frameState.stackAt(0)) {
639 stateAfterException = stateAtExceptionEdge.duplicateModified(JavaKind.Object, JavaKind.Object, frameState.stackAt(0));
640 }
641 frameState.replaceAndDelete(stateAfterException);
642 return stateAfterException;
643 } else if (frameState.bci == BytecodeFrame.UNWIND_BCI || frameState.bci == BytecodeFrame.AFTER_EXCEPTION_BCI) {
644 handleMissingAfterExceptionFrameState(frameState, invoke, replacements, alwaysDuplicateStateAfter);
645 return frameState;
646 } else if (frameState.bci == BytecodeFrame.BEFORE_BCI) {
647 // This is an intrinsic. Deoptimizing within an intrinsic
648 // must re-execute the intrinsified invocation
649 assert frameState.outerFrameState() == null;
650 ValueNode[] invokeArgs = invokeArgsList.isEmpty() ? NO_ARGS : invokeArgsList.toArray(new ValueNode[invokeArgsList.size()]);
651 FrameState stateBeforeCall = stateAtReturn.duplicateModifiedBeforeCall(invoke.bci(), invokeReturnKind, invokeTargetMethod.getSignature().toParameterKinds(!invokeTargetMethod.isStatic()),
652 invokeArgs);
653 frameState.replaceAndDelete(stateBeforeCall);
654 return stateBeforeCall;
655 } else {
656 // only handle the outermost frame states
657 if (frameState.outerFrameState() == null) {
658 assert checkInlineeFrameState(invoke, inlinedMethod, frameState);
659 frameState.setOuterFrameState(outerFrameState);
660 }
661 return frameState;
662 }
663 }
664
665 private static FrameState handleAfterBciFrameState(FrameState frameState, Invoke invoke, boolean alwaysDuplicateStateAfter) {
666 FrameState stateAtReturn = invoke.stateAfter();
667 JavaKind invokeReturnKind = invoke.asNode().getStackKind();
668 FrameState stateAfterReturn = stateAtReturn;
669 if (frameState.getCode() == null) {
670 // This is a frame state for a side effect within an intrinsic
671 // that was parsed for post-parse intrinsification
672 for (Node usage : frameState.usages()) {
673 if (usage instanceof ForeignCallNode) {
674 // A foreign call inside an intrinsic needs to have
675 // the BCI of the invoke being intrinsified
676 ForeignCallNode foreign = (ForeignCallNode) usage;
677 foreign.setBci(invoke.bci());
678 }
679 }
680 }
681
682 // pop return kind from invoke's stateAfter and replace with this frameState's return
683 // value (top of stack)
684 assert !frameState.rethrowException() : frameState;
685 if (frameState.stackSize() > 0 && (alwaysDuplicateStateAfter || stateAfterReturn.stackAt(0) != frameState.stackAt(0))) {
686 // A non-void return value.
687 stateAfterReturn = stateAtReturn.duplicateModified(invokeReturnKind, invokeReturnKind, frameState.stackAt(0));
688 } else {
689 // A void return value.
690 stateAfterReturn = stateAtReturn.duplicate();
691 }
692 assert stateAfterReturn.bci != BytecodeFrame.UNKNOWN_BCI;
693
694 // Return value does no longer need to be limited by the monitor exit.
695 for (MonitorExitNode n : frameState.usages().filter(MonitorExitNode.class)) {
696 n.clearEscapedReturnValue();
697 }
698
699 frameState.replaceAndDelete(stateAfterReturn);
700 return stateAfterReturn;
701 }
702
703 static boolean checkInlineeFrameState(Invoke invoke, ResolvedJavaMethod inlinedMethod, FrameState frameState) {
704 assert frameState.bci != BytecodeFrame.AFTER_EXCEPTION_BCI : frameState;
705 assert frameState.bci != BytecodeFrame.BEFORE_BCI : frameState;
706 assert frameState.bci != BytecodeFrame.UNKNOWN_BCI : frameState;
707 assert frameState.bci != BytecodeFrame.UNWIND_BCI : frameState;
708 if (frameState.bci != BytecodeFrame.INVALID_FRAMESTATE_BCI) {
709 ResolvedJavaMethod method = frameState.getMethod();
710 if (method.equals(inlinedMethod)) {
711 // Normal inlining expects all outermost inlinee frame states to
712 // denote the inlinee method
713 } else if (method.equals(invoke.callTarget().targetMethod())) {
714 // This occurs when an intrinsic calls back to the original
715 // method to handle a slow path. During parsing of such a
716 // partial intrinsic, these calls are given frame states
717 // that exclude the outer frame state denoting a position
718 // in the intrinsic code.
719 assert inlinedMethod.getAnnotation(
720 MethodSubstitution.class) != null : "expected an intrinsic when inlinee frame state matches method of call target but does not match the method of the inlinee graph: " +
721 frameState;
722 } else if (method.getName().equals(inlinedMethod.getName())) {
723 // This can happen for method substitutions.
724 } else {
725 throw new AssertionError(String.format("inlinedMethod=%s frameState.method=%s frameState=%s invoke.method=%s", inlinedMethod, method, frameState,
726 invoke.callTarget().targetMethod()));
727 }
728 }
729 return true;
730 }
731
732 private static final ValueNode[] NO_ARGS = {};
733
734 private static boolean isStateAfterException(FrameState frameState) {
735 return frameState.bci == BytecodeFrame.AFTER_EXCEPTION_BCI || (frameState.bci == BytecodeFrame.UNWIND_BCI && !frameState.getMethod().isSynchronized());
736 }
737
738 public static FrameState handleMissingAfterExceptionFrameState(FrameState nonReplaceableFrameState, Invoke invoke, EconomicMap<Node, Node> replacements, boolean alwaysDuplicateStateAfter) {
739 Graph graph = nonReplaceableFrameState.graph();
740 NodeWorkList workList = graph.createNodeWorkList();
741 workList.add(nonReplaceableFrameState);
742 for (Node node : workList) {
743 FrameState fs = (FrameState) node;
744 for (Node usage : fs.usages().snapshot()) {
745 if (!usage.isAlive()) {
746 continue;
747 }
748 if (usage instanceof FrameState) {
749 workList.add(usage);
750 } else {
751 StateSplit stateSplit = (StateSplit) usage;
752 FixedNode fixedStateSplit = stateSplit.asNode();
753 if (fixedStateSplit instanceof AbstractMergeNode) {
754 AbstractMergeNode merge = (AbstractMergeNode) fixedStateSplit;
755 while (merge.isAlive()) {
756 AbstractEndNode end = merge.forwardEnds().first();
757 DeoptimizeNode deoptimizeNode = graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateRecompile, DeoptimizationReason.NotCompiledExceptionHandler));
758 end.replaceAtPredecessor(deoptimizeNode);
759 GraphUtil.killCFG(end);
760 }
761 } else if (fixedStateSplit instanceof ExceptionObjectNode) {
762 // The target invoke does not have an exception edge. This means that the
763 // bytecode parser made the wrong assumption of making an
764 // InvokeWithExceptionNode for the partial intrinsic exit. We therefore
765 // replace the InvokeWithExceptionNode with a normal
766 // InvokeNode -- the deoptimization occurs when the invoke throws.
767 InvokeWithExceptionNode oldInvoke = (InvokeWithExceptionNode) fixedStateSplit.predecessor();
768 FrameState oldFrameState = oldInvoke.stateAfter();
769 InvokeNode newInvoke = oldInvoke.replaceWithInvoke();
770 newInvoke.setStateAfter(oldFrameState.duplicate());
771 if (replacements != null) {
772 replacements.put(oldInvoke, newInvoke);
773 }
774 handleAfterBciFrameState(newInvoke.stateAfter(), invoke, alwaysDuplicateStateAfter);
775 } else {
776 FixedNode deoptimizeNode = graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateRecompile, DeoptimizationReason.NotCompiledExceptionHandler));
777 if (fixedStateSplit instanceof AbstractBeginNode) {
778 deoptimizeNode = BeginNode.begin(deoptimizeNode);
779 }
780 fixedStateSplit.replaceAtPredecessor(deoptimizeNode);
781 GraphUtil.killCFG(fixedStateSplit);
782 }
783 }
784 }
785 }
786 return nonReplaceableFrameState;
787 }
788
789 /**
790 * Ensure that all states are either {@link BytecodeFrame#INVALID_FRAMESTATE_BCI} or one of
791 * {@link BytecodeFrame#AFTER_BCI} or {@link BytecodeFrame#BEFORE_BCI}. Mixing of before and
792 * after isn't allowed.
793 */
794 private static boolean checkContainsOnlyInvalidOrAfterFrameState(UnmodifiableEconomicMap<Node, Node> duplicates) {
795 int okBci = BytecodeFrame.INVALID_FRAMESTATE_BCI;
796 for (Node node : duplicates.getValues()) {
797 if (node instanceof FrameState) {
798 FrameState frameState = (FrameState) node;
799 if (frameState.bci == BytecodeFrame.INVALID_FRAMESTATE_BCI) {
800 continue;
801 }
802 if (frameState.bci == BytecodeFrame.AFTER_BCI || frameState.bci == BytecodeFrame.BEFORE_BCI) {
803 if (okBci == BytecodeFrame.INVALID_FRAMESTATE_BCI) {
804 okBci = frameState.bci;
805 } else {
806 assert okBci == frameState.bci : node.toString(Verbosity.Debugger);
807 }
808 } else {
809 assert false : node.toString(Verbosity.Debugger);
810 }
811 }
812 }
813 return true;
814 }
815
816 /**
817 * Gets the receiver for an invoke, adding a guard if necessary to ensure it is non-null, and
818 * ensuring that the resulting type is compatible with the method being invoked.
819 */
820 public static ValueNode nonNullReceiver(Invoke invoke) {
821 MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget();
822 assert !callTarget.isStatic() : callTarget.targetMethod();
823 StructuredGraph graph = callTarget.graph();
824 ValueNode oldReceiver = callTarget.arguments().get(0);
825 ValueNode newReceiver = oldReceiver;
826 if (newReceiver.getStackKind() == JavaKind.Object) {
827
828 if (invoke.getInvokeKind() == InvokeKind.Special) {
829 Stamp paramStamp = newReceiver.stamp();
830 Stamp stamp = paramStamp.join(StampFactory.object(TypeReference.create(graph.getAssumptions(), callTarget.targetMethod().getDeclaringClass())));
831 if (!stamp.equals(paramStamp)) {
832 // The verifier and previous optimizations guarantee unconditionally that the
833 // receiver is at least of the type of the method holder for a special invoke.
834 newReceiver = graph.unique(new PiNode(newReceiver, stamp));
835 }
836 }
837
838 if (!StampTool.isPointerNonNull(newReceiver)) {
839 LogicNode condition = graph.unique(IsNullNode.create(newReceiver));
840 FixedGuardNode fixedGuard = graph.add(new FixedGuardNode(condition, NullCheckException, InvalidateReprofile, true));
841 PiNode nonNullReceiver = graph.unique(new PiNode(newReceiver, StampFactory.objectNonNull(), fixedGuard));
842 graph.addBeforeFixed(invoke.asNode(), fixedGuard);
843 newReceiver = nonNullReceiver;
844 }
845 }
846
847 if (newReceiver != oldReceiver) {
848 callTarget.replaceFirstInput(oldReceiver, newReceiver);
849 }
850 return newReceiver;
851 }
852
853 public static boolean canIntrinsify(Replacements replacements, ResolvedJavaMethod target, int invokeBci) {
854 return replacements.hasSubstitution(target, invokeBci);
855 }
856
857 public static StructuredGraph getIntrinsicGraph(Replacements replacements, ResolvedJavaMethod target, int invokeBci) {
858 return replacements.getSubstitution(target, invokeBci);
859 }
860
861 public static FixedWithNextNode inlineMacroNode(Invoke invoke, ResolvedJavaMethod concrete, Class<? extends FixedWithNextNode> macroNodeClass) throws GraalError {
862 StructuredGraph graph = invoke.asNode().graph();
863 if (!concrete.equals(((MethodCallTargetNode) invoke.callTarget()).targetMethod())) {
864 assert ((MethodCallTargetNode) invoke.callTarget()).invokeKind().hasReceiver();
865 InliningUtil.replaceInvokeCallTarget(invoke, graph, InvokeKind.Special, concrete);
866 }
867
868 FixedWithNextNode macroNode = createMacroNodeInstance(macroNodeClass, invoke);
869
870 CallTargetNode callTarget = invoke.callTarget();
871 if (invoke instanceof InvokeNode) {
872 graph.replaceFixedWithFixed((InvokeNode) invoke, graph.add(macroNode));
873 } else {
874 InvokeWithExceptionNode invokeWithException = (InvokeWithExceptionNode) invoke;
875 invokeWithException.killExceptionEdge();
876 graph.replaceSplitWithFixed(invokeWithException, graph.add(macroNode), invokeWithException.next());
877 }
878 GraphUtil.killWithUnusedFloatingInputs(callTarget);
879 return macroNode;
880 }
881
882 private static FixedWithNextNode createMacroNodeInstance(Class<? extends FixedWithNextNode> macroNodeClass, Invoke invoke) throws GraalError {
883 try {
884 Constructor<?> cons = macroNodeClass.getDeclaredConstructor(Invoke.class);
885 return (FixedWithNextNode) cons.newInstance(invoke);
886 } catch (ReflectiveOperationException | IllegalArgumentException | SecurityException e) {
887 throw new GraalGraphError(e).addContext(invoke.asNode()).addContext("macroSubstitution", macroNodeClass);
888 }
889 }
890
891 /**
892 * This method exclude InstrumentationNode from inlining heuristics.
893 */
894 public static int getNodeCount(StructuredGraph graph) {
895 return graph.getNodeCount();
896 }
897
898 }