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