1 /*
2 * Copyright (c) 2015, 2016, 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.replacements;
24
25 import static org.graalvm.compiler.debug.GraalError.unimplemented;
26 import static org.graalvm.compiler.java.BytecodeParserOptions.DumpDuringGraphBuilding;
27 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;
28 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;
29
30 import java.util.ArrayList;
31 import java.util.Arrays;
32 import java.util.HashMap;
33 import java.util.Iterator;
34 import java.util.List;
35 import java.util.Map;
36
37 import org.graalvm.compiler.bytecode.Bytecode;
38 import org.graalvm.compiler.bytecode.BytecodeProvider;
39 import org.graalvm.compiler.common.PermanentBailoutException;
40 import org.graalvm.compiler.core.common.cfg.CFGVerifier;
41 import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
42 import org.graalvm.compiler.core.common.type.StampFactory;
43 import org.graalvm.compiler.core.common.type.StampPair;
44 import org.graalvm.compiler.debug.Debug;
45 import org.graalvm.compiler.debug.DebugCloseable;
46 import org.graalvm.compiler.debug.GraalError;
47 import org.graalvm.compiler.graph.Node;
48 import org.graalvm.compiler.graph.NodeClass;
49 import org.graalvm.compiler.graph.NodeSourcePosition;
50 import org.graalvm.compiler.graph.spi.Canonicalizable;
51 import org.graalvm.compiler.java.GraphBuilderPhase;
52 import org.graalvm.compiler.nodeinfo.NodeInfo;
53 import org.graalvm.compiler.nodes.AbstractBeginNode;
54 import org.graalvm.compiler.nodes.AbstractMergeNode;
55 import org.graalvm.compiler.nodes.CallTargetNode;
56 import org.graalvm.compiler.nodes.CallTargetNode.InvokeKind;
57 import org.graalvm.compiler.nodes.DeoptimizeNode;
58 import org.graalvm.compiler.nodes.EncodedGraph;
59 import org.graalvm.compiler.nodes.FixedNode;
60 import org.graalvm.compiler.nodes.FixedWithNextNode;
61 import org.graalvm.compiler.nodes.FrameState;
62 import org.graalvm.compiler.nodes.IfNode;
63 import org.graalvm.compiler.nodes.Invoke;
64 import org.graalvm.compiler.nodes.InvokeWithExceptionNode;
65 import org.graalvm.compiler.nodes.MergeNode;
66 import org.graalvm.compiler.nodes.ParameterNode;
67 import org.graalvm.compiler.nodes.ReturnNode;
68 import org.graalvm.compiler.nodes.SimplifyingGraphDecoder;
69 import org.graalvm.compiler.nodes.StateSplit;
70 import org.graalvm.compiler.nodes.StructuredGraph;
71 import org.graalvm.compiler.nodes.UnwindNode;
72 import org.graalvm.compiler.nodes.ValueNode;
73 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
74 import org.graalvm.compiler.nodes.extended.ForeignCallNode;
75 import org.graalvm.compiler.nodes.extended.IntegerSwitchNode;
76 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderContext;
77 import org.graalvm.compiler.nodes.graphbuilderconf.InlineInvokePlugin;
78 import org.graalvm.compiler.nodes.graphbuilderconf.InlineInvokePlugin.InlineInfo;
79 import org.graalvm.compiler.nodes.graphbuilderconf.IntrinsicContext;
80 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugin;
81 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins;
82 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins.InvocationPluginReceiver;
83 import org.graalvm.compiler.nodes.graphbuilderconf.LoopExplosionPlugin;
84 import org.graalvm.compiler.nodes.graphbuilderconf.LoopExplosionPlugin.LoopExplosionKind;
85 import org.graalvm.compiler.nodes.graphbuilderconf.ParameterPlugin;
86 import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
87 import org.graalvm.compiler.nodes.java.MonitorIdNode;
88 import org.graalvm.compiler.nodes.spi.StampProvider;
89 import org.graalvm.compiler.nodes.util.GraphUtil;
90 import org.graalvm.compiler.options.Option;
91 import org.graalvm.compiler.options.OptionType;
92 import org.graalvm.compiler.options.OptionValue;
93 import org.graalvm.compiler.phases.common.inlining.InliningUtil;
94
95 import jdk.vm.ci.code.Architecture;
96 import jdk.vm.ci.code.BailoutException;
97 import jdk.vm.ci.code.BytecodeFrame;
98 import jdk.vm.ci.meta.ConstantReflectionProvider;
99 import jdk.vm.ci.meta.DeoptimizationAction;
100 import jdk.vm.ci.meta.DeoptimizationReason;
101 import jdk.vm.ci.meta.JavaConstant;
102 import jdk.vm.ci.meta.JavaKind;
103 import jdk.vm.ci.meta.JavaType;
104 import jdk.vm.ci.meta.MetaAccessProvider;
105 import jdk.vm.ci.meta.ResolvedJavaMethod;
106
107 /**
108 * A graph decoder that performs partial evaluation, i.e., that performs method inlining and
109 * canonicalization/simplification of nodes during decoding.
110 *
111 * Inlining and loop explosion are configured via the plugin mechanism also used by the
112 * {@link GraphBuilderPhase}. However, not all callback methods defined in
113 * {@link GraphBuilderContext} are available since decoding is more limited than graph building.
114 *
115 * The standard {@link Canonicalizable#canonical node canonicalization} interface is used to
116 * canonicalize nodes during decoding. Additionally, {@link IfNode branches} and
117 * {@link IntegerSwitchNode switches} with constant conditions are simplified.
118 */
119 public abstract class PEGraphDecoder extends SimplifyingGraphDecoder {
120
121 public static class Options {
122 @Option(help = "Maximum inlining depth during partial evaluation before reporting an infinite recursion")//
123 public static final OptionValue<Integer> InliningDepthError = new OptionValue<>(1000);
124
125 @Option(help = "Max number of loop explosions per method.", type = OptionType.Debug)//
126 public static final OptionValue<Integer> MaximumLoopExplosionCount = new OptionValue<>(10000);
127
128 @Option(help = "Do not bail out but throw an exception on failed loop explosion.", type = OptionType.Debug) //
129 public static final OptionValue<Boolean> FailedLoopExplosionIsFatal = new OptionValue<>(false);
130 }
131
132 protected class PEMethodScope extends MethodScope {
133 /** The state of the caller method. Only non-null during method inlining. */
134 protected final PEMethodScope caller;
135 protected final ResolvedJavaMethod method;
136 protected final InvokeData invokeData;
137 protected final int inliningDepth;
138
139 protected final LoopExplosionPlugin loopExplosionPlugin;
140 protected final InvocationPlugins invocationPlugins;
141 protected final InlineInvokePlugin[] inlineInvokePlugins;
142 protected final ParameterPlugin parameterPlugin;
143 protected final ValueNode[] arguments;
144
145 protected FrameState outerState;
146 protected FrameState exceptionState;
147 protected ExceptionPlaceholderNode exceptionPlaceholderNode;
148 protected NodeSourcePosition callerBytecodePosition;
149
150 protected PEMethodScope(StructuredGraph targetGraph, PEMethodScope caller, LoopScope callerLoopScope, EncodedGraph encodedGraph, ResolvedJavaMethod method, InvokeData invokeData,
151 int inliningDepth, LoopExplosionPlugin loopExplosionPlugin, InvocationPlugins invocationPlugins, InlineInvokePlugin[] inlineInvokePlugins, ParameterPlugin parameterPlugin,
152 ValueNode[] arguments) {
153 super(callerLoopScope, targetGraph, encodedGraph, loopExplosionKind(method, loopExplosionPlugin));
154
155 this.caller = caller;
156 this.method = method;
157 this.invokeData = invokeData;
158 this.inliningDepth = inliningDepth;
159 this.loopExplosionPlugin = loopExplosionPlugin;
160 this.invocationPlugins = invocationPlugins;
161 this.inlineInvokePlugins = inlineInvokePlugins;
162 this.parameterPlugin = parameterPlugin;
163 this.arguments = arguments;
164 }
165
166 public boolean isInlinedMethod() {
167 return caller != null;
168 }
169
170 public NodeSourcePosition getCallerBytecodePosition() {
171 if (caller == null) {
172 return null;
173 }
174 if (callerBytecodePosition == null) {
175 JavaConstant constantReceiver = caller.invokeData == null ? null : caller.invokeData.constantReceiver;
176 NodeSourcePosition callerPosition = caller.getCallerBytecodePosition();
177 NodeSourcePosition invokePosition = invokeData.invoke.asNode().getNodeSourcePosition();
178 callerBytecodePosition = invokePosition != null ? invokePosition.addCaller(constantReceiver, callerPosition) : callerPosition;
179 }
180 return callerBytecodePosition;
181 }
182 }
183
184 protected class PENonAppendGraphBuilderContext implements GraphBuilderContext {
185 protected final PEMethodScope methodScope;
186 protected final Invoke invoke;
187
188 public PENonAppendGraphBuilderContext(PEMethodScope methodScope, Invoke invoke) {
189 this.methodScope = methodScope;
190 this.invoke = invoke;
191 }
192
193 @Override
194 public BailoutException bailout(String string) {
195 BailoutException bailout = new PermanentBailoutException(string);
196 throw GraphUtil.createBailoutException(string, bailout, GraphUtil.approxSourceStackTraceElement(methodScope.getCallerBytecodePosition()));
197 }
198
199 @Override
200 public StampProvider getStampProvider() {
201 return stampProvider;
202 }
203
204 @Override
205 public MetaAccessProvider getMetaAccess() {
206 return metaAccess;
207 }
208
209 @Override
210 public ConstantReflectionProvider getConstantReflection() {
211 return constantReflection;
212 }
213
214 @Override
215 public ConstantFieldProvider getConstantFieldProvider() {
216 return constantFieldProvider;
217 }
218
219 @Override
220 public StructuredGraph getGraph() {
221 return methodScope.graph;
222 }
223
224 @Override
225 public int getDepth() {
226 return methodScope.inliningDepth;
227 }
228
229 @Override
230 public IntrinsicContext getIntrinsic() {
231 return null;
232 }
233
234 @Override
235 public <T extends ValueNode> T append(T value) {
236 throw unimplemented();
237 }
238
239 @Override
240 public <T extends ValueNode> T recursiveAppend(T value) {
241 throw unimplemented();
242 }
243
244 @Override
245 public void push(JavaKind kind, ValueNode value) {
246 throw unimplemented();
247 }
248
249 @Override
250 public void handleReplacedInvoke(InvokeKind invokeKind, ResolvedJavaMethod targetMethod, ValueNode[] args, boolean inlineEverything) {
251 throw unimplemented();
252 }
253
254 @Override
255 public boolean intrinsify(BytecodeProvider bytecodeProvider, ResolvedJavaMethod targetMethod, ResolvedJavaMethod substitute, InvocationPlugin.Receiver receiver, ValueNode[] args) {
256 return false;
257 }
258
259 @Override
260 public void setStateAfter(StateSplit stateSplit) {
261 throw unimplemented();
262 }
263
264 @Override
265 public GraphBuilderContext getParent() {
266 throw unimplemented();
267 }
268
269 @Override
270 public Bytecode getCode() {
271 throw unimplemented();
272 }
273
274 @Override
275 public ResolvedJavaMethod getMethod() {
276 throw unimplemented();
277 }
278
279 @Override
280 public int bci() {
281 return invoke.bci();
282 }
283
284 @Override
285 public InvokeKind getInvokeKind() {
286 throw unimplemented();
287 }
288
289 @Override
290 public JavaType getInvokeReturnType() {
291 throw unimplemented();
292 }
293 }
294
295 protected class PEAppendGraphBuilderContext extends PENonAppendGraphBuilderContext {
296 protected FixedWithNextNode lastInstr;
297 protected ValueNode pushedNode;
298
299 public PEAppendGraphBuilderContext(PEMethodScope inlineScope, FixedWithNextNode lastInstr) {
300 super(inlineScope, inlineScope.invokeData.invoke);
301 this.lastInstr = lastInstr;
302 }
303
304 @Override
305 public void push(JavaKind kind, ValueNode value) {
306 if (pushedNode != null) {
307 throw unimplemented("Only one push is supported");
308 }
309 pushedNode = value;
310 }
311
312 @Override
313 public void setStateAfter(StateSplit stateSplit) {
314 Node stateAfter = decodeFloatingNode(methodScope.caller, methodScope.callerLoopScope, methodScope.invokeData.stateAfterOrderId);
315 getGraph().add(stateAfter);
316 FrameState fs = (FrameState) handleFloatingNodeAfterAdd(methodScope.caller, methodScope.callerLoopScope, stateAfter);
317 stateSplit.setStateAfter(fs);
318 }
319
320 @SuppressWarnings("try")
321 @Override
322 public <T extends ValueNode> T append(T v) {
323 if (v.graph() != null) {
324 return v;
325 }
326 try (DebugCloseable position = withNodeSoucePosition()) {
327 T added = getGraph().addOrUnique(v);
328 if (added == v) {
329 updateLastInstruction(v);
330 }
331 return added;
332 }
333 }
334
335 private DebugCloseable withNodeSoucePosition() {
336 if (getGraph().mayHaveNodeSourcePosition()) {
337 return getGraph().withNodeSourcePosition(methodScope.getCallerBytecodePosition());
338 }
339 return null;
340 }
341
342 @SuppressWarnings("try")
343 @Override
344 public <T extends ValueNode> T recursiveAppend(T v) {
345 if (v.graph() != null) {
346 return v;
347 }
348 try (DebugCloseable position = withNodeSoucePosition()) {
349 T added = getGraph().addOrUniqueWithInputs(v);
350 if (added == v) {
351 updateLastInstruction(v);
352 }
353 return added;
354 }
355 }
356
357 private <T extends ValueNode> void updateLastInstruction(T v) {
358 if (v instanceof FixedNode) {
359 FixedNode fixedNode = (FixedNode) v;
360 lastInstr.setNext(fixedNode);
361 if (fixedNode instanceof FixedWithNextNode) {
362 FixedWithNextNode fixedWithNextNode = (FixedWithNextNode) fixedNode;
363 assert fixedWithNextNode.next() == null : "cannot append instruction to instruction which isn't end";
364 lastInstr = fixedWithNextNode;
365 } else {
366 lastInstr = null;
367 }
368 }
369 }
370 }
371
372 @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED)
373 static class ExceptionPlaceholderNode extends ValueNode {
374 public static final NodeClass<ExceptionPlaceholderNode> TYPE = NodeClass.create(ExceptionPlaceholderNode.class);
375
376 protected ExceptionPlaceholderNode() {
377 super(TYPE, StampFactory.object());
378 }
379 }
380
381 public PEGraphDecoder(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider, StampProvider stampProvider,
382 Architecture architecture) {
383 super(metaAccess, constantReflection, constantFieldProvider, stampProvider, true, architecture);
384 }
385
386 protected static LoopExplosionKind loopExplosionKind(ResolvedJavaMethod method, LoopExplosionPlugin loopExplosionPlugin) {
387 if (loopExplosionPlugin == null) {
388 return LoopExplosionKind.NONE;
389 } else {
390 return loopExplosionPlugin.loopExplosionKind(method);
391 }
392 }
393
394 public void decode(StructuredGraph targetGraph, ResolvedJavaMethod method, LoopExplosionPlugin loopExplosionPlugin, InvocationPlugins invocationPlugins, InlineInvokePlugin[] inlineInvokePlugins,
395 ParameterPlugin parameterPlugin) {
396 PEMethodScope methodScope = new PEMethodScope(targetGraph, null, null, lookupEncodedGraph(method, null), method, null, 0, loopExplosionPlugin, invocationPlugins, inlineInvokePlugins,
397 parameterPlugin, null);
398 decode(createInitialLoopScope(methodScope, null));
399 cleanupGraph(methodScope);
400
401 Debug.dump(Debug.VERBOSE_LOG_LEVEL, methodScope.graph, "After graph cleanup");
402 assert methodScope.graph.verify();
403
404 try {
405 /* Check that the control flow graph can be computed, to catch problems early. */
406 assert CFGVerifier.verify(ControlFlowGraph.compute(methodScope.graph, true, true, true, true));
407 } catch (Throwable ex) {
408 throw GraalError.shouldNotReachHere("Control flow graph not valid after partial evaluation");
409 }
410 }
411
412 @Override
413 protected void cleanupGraph(MethodScope methodScope) {
414 super.cleanupGraph(methodScope);
415
416 for (FrameState frameState : methodScope.graph.getNodes(FrameState.TYPE)) {
417 if (frameState.bci == BytecodeFrame.UNWIND_BCI) {
418 /*
419 * handleMissingAfterExceptionFrameState is called during graph decoding from
420 * InliningUtil.processFrameState - but during graph decoding it does not do
421 * anything because the usages of the frameState are not available yet. So we need
422 * to call it again.
423 */
424 InliningUtil.handleMissingAfterExceptionFrameState(frameState);
425
426 /*
427 * The frameState must be gone now, because it is not a valid deoptimization point.
428 */
429 assert frameState.isDeleted();
430 }
431 }
432 }
433
434 @Override
435 protected void checkLoopExplosionIteration(MethodScope s, LoopScope loopScope) {
436 PEMethodScope methodScope = (PEMethodScope) s;
437
438 if (loopScope.loopIteration > Options.MaximumLoopExplosionCount.getValue()) {
439 throw tooManyLoopExplosionIterations(methodScope);
440 }
441 }
442
443 private static RuntimeException tooManyLoopExplosionIterations(PEMethodScope methodScope) {
444 String message = "too many loop explosion iterations - does the explosion not terminate for method " + methodScope.method + "?";
445 RuntimeException bailout = Options.FailedLoopExplosionIsFatal.getValue() ? new RuntimeException(message) : new PermanentBailoutException(message);
446 throw GraphUtil.createBailoutException(message, bailout, GraphUtil.approxSourceStackTraceElement(methodScope.getCallerBytecodePosition()));
447 }
448
449 @Override
450 protected LoopScope handleInvoke(MethodScope s, LoopScope loopScope, InvokeData invokeData) {
451 PEMethodScope methodScope = (PEMethodScope) s;
452
453 /*
454 * Decode the call target, but do not add it to the graph yet. This avoids adding usages for
455 * all the arguments, which are expensive to remove again when we can inline the method.
456 */
457 assert invokeData.invoke.callTarget() == null : "callTarget edge is ignored during decoding of Invoke";
458 CallTargetNode callTarget = (CallTargetNode) decodeFloatingNode(methodScope, loopScope, invokeData.callTargetOrderId);
459 if (callTarget instanceof MethodCallTargetNode) {
460 MethodCallTargetNode methodCall = (MethodCallTargetNode) callTarget;
461 if (methodCall.invokeKind().hasReceiver()) {
462 invokeData.constantReceiver = methodCall.arguments().get(0).asJavaConstant();
463 }
464 LoopScope inlineLoopScope = trySimplifyInvoke(methodScope, loopScope, invokeData, (MethodCallTargetNode) callTarget);
465 if (inlineLoopScope != null) {
466 return inlineLoopScope;
467 }
468 }
469
470 /* We know that we need an invoke, so now we can add the call target to the graph. */
471 methodScope.graph.add(callTarget);
472 registerNode(loopScope, invokeData.callTargetOrderId, callTarget, false, false);
473 return super.handleInvoke(methodScope, loopScope, invokeData);
474 }
475
476 protected LoopScope trySimplifyInvoke(PEMethodScope methodScope, LoopScope loopScope, InvokeData invokeData, MethodCallTargetNode callTarget) {
477 // attempt to devirtualize the call
478 ResolvedJavaMethod specialCallTarget = MethodCallTargetNode.findSpecialCallTarget(callTarget.invokeKind(), callTarget.receiver(), callTarget.targetMethod(), invokeData.contextType);
479 if (specialCallTarget != null) {
480 callTarget.setTargetMethod(specialCallTarget);
481 callTarget.setInvokeKind(InvokeKind.Special);
482 }
483
484 if (tryInvocationPlugin(methodScope, loopScope, invokeData, callTarget)) {
485 /*
486 * The invocation plugin handled the call, so decoding continues in the calling method.
487 */
488 return loopScope;
489 }
490 LoopScope inlineLoopScope = tryInline(methodScope, loopScope, invokeData, callTarget);
491 if (inlineLoopScope != null) {
492 /*
493 * We can inline the call, so decoding continues in the inlined method.
494 */
495 return inlineLoopScope;
496 }
497
498 for (InlineInvokePlugin plugin : methodScope.inlineInvokePlugins) {
499 plugin.notifyNotInlined(new PENonAppendGraphBuilderContext(methodScope, invokeData.invoke), callTarget.targetMethod(), invokeData.invoke);
500 }
501 return null;
502 }
503
504 protected boolean tryInvocationPlugin(PEMethodScope methodScope, LoopScope loopScope, InvokeData invokeData, MethodCallTargetNode callTarget) {
505 if (methodScope.invocationPlugins == null) {
506 return false;
507 }
508
509 Invoke invoke = invokeData.invoke;
510
511 ResolvedJavaMethod targetMethod = callTarget.targetMethod();
512 InvocationPlugin invocationPlugin = methodScope.invocationPlugins.lookupInvocation(targetMethod);
513 if (invocationPlugin == null) {
514 return false;
515 }
516
517 ValueNode[] arguments = callTarget.arguments().toArray(new ValueNode[0]);
518 FixedWithNextNode invokePredecessor = (FixedWithNextNode) invoke.asNode().predecessor();
519
520 /*
521 * Remove invoke from graph so that invocation plugin can append nodes to the predecessor.
522 */
523 invoke.asNode().replaceAtPredecessor(null);
524
525 PEMethodScope inlineScope = new PEMethodScope(methodScope.graph, methodScope, loopScope, null, targetMethod, invokeData, methodScope.inliningDepth + 1, methodScope.loopExplosionPlugin,
526 methodScope.invocationPlugins, methodScope.inlineInvokePlugins, null, arguments);
527 PEAppendGraphBuilderContext graphBuilderContext = new PEAppendGraphBuilderContext(inlineScope, invokePredecessor);
528 InvocationPluginReceiver invocationPluginReceiver = new InvocationPluginReceiver(graphBuilderContext);
529
530 if (invocationPlugin.execute(graphBuilderContext, targetMethod, invocationPluginReceiver.init(targetMethod, arguments), arguments)) {
531
532 if (graphBuilderContext.lastInstr != null) {
533 registerNode(loopScope, invokeData.invokeOrderId, graphBuilderContext.pushedNode, true, true);
534 invoke.asNode().replaceAtUsages(graphBuilderContext.pushedNode);
535 graphBuilderContext.lastInstr.setNext(nodeAfterInvoke(methodScope, loopScope, invokeData, AbstractBeginNode.prevBegin(graphBuilderContext.lastInstr)));
536 } else {
537 assert graphBuilderContext.pushedNode == null : "Why push a node when the invoke does not return anyway?";
538 invoke.asNode().replaceAtUsages(null);
539 }
540
541 deleteInvoke(invoke);
542 return true;
543
544 } else {
545 /* Intrinsification failed, restore original state: invoke is in Graph. */
546 invokePredecessor.setNext(invoke.asNode());
547 return false;
548 }
549 }
550
551 protected LoopScope tryInline(PEMethodScope methodScope, LoopScope loopScope, InvokeData invokeData, MethodCallTargetNode callTarget) {
552 if (!callTarget.invokeKind().isDirect()) {
553 return null;
554 }
555
556 ResolvedJavaMethod targetMethod = callTarget.targetMethod();
557 if (!targetMethod.canBeInlined()) {
558 return null;
559 }
560
561 ValueNode[] arguments = callTarget.arguments().toArray(new ValueNode[0]);
562 GraphBuilderContext graphBuilderContext = new PENonAppendGraphBuilderContext(methodScope, invokeData.invoke);
563
564 for (InlineInvokePlugin plugin : methodScope.inlineInvokePlugins) {
565 InlineInfo inlineInfo = plugin.shouldInlineInvoke(graphBuilderContext, targetMethod, arguments);
566 if (inlineInfo != null) {
567 if (inlineInfo.getMethodToInline() == null) {
568 return null;
569 } else {
570 return doInline(methodScope, loopScope, invokeData, inlineInfo, arguments);
571 }
572 }
573 }
574 return null;
575 }
576
577 protected LoopScope doInline(PEMethodScope methodScope, LoopScope loopScope, InvokeData invokeData, InlineInfo inlineInfo, ValueNode[] arguments) {
578 ResolvedJavaMethod inlineMethod = inlineInfo.getMethodToInline();
579 EncodedGraph graphToInline = lookupEncodedGraph(inlineMethod, inlineInfo.getIntrinsicBytecodeProvider());
580 if (graphToInline == null) {
581 return null;
582 }
583
584 if (methodScope.inliningDepth > Options.InliningDepthError.getValue()) {
585 throw tooDeepInlining(methodScope);
586 }
587
588 for (InlineInvokePlugin plugin : methodScope.inlineInvokePlugins) {
589 plugin.notifyBeforeInline(inlineMethod);
590 }
591
592 Invoke invoke = invokeData.invoke;
593 FixedNode invokeNode = invoke.asNode();
594 FixedWithNextNode predecessor = (FixedWithNextNode) invokeNode.predecessor();
595 invokeNode.replaceAtPredecessor(null);
596
597 PEMethodScope inlineScope = new PEMethodScope(methodScope.graph, methodScope, loopScope, graphToInline, inlineMethod, invokeData, methodScope.inliningDepth + 1,
598 methodScope.loopExplosionPlugin, methodScope.invocationPlugins, methodScope.inlineInvokePlugins, null, arguments);
599
600 /*
601 * After decoding all the nodes of the inlined method, we need to re-wire the return and
602 * unwind nodes. Since inlining is non-recursive, this cannot be done at the end of this
603 * method, but must be registered as a cleanup task that runs when all nodes of the inlined
604 * methods have been decoded.
605 */
606 inlineScope.cleanupTasks.add(() -> finishInlining(methodScope, loopScope, invokeData, inlineMethod, inlineScope));
607
608 /*
609 * Do the actual inlining by returning the initial loop scope for the inlined method scope.
610 */
611 return createInitialLoopScope(inlineScope, predecessor);
612 }
613
614 protected void finishInlining(PEMethodScope methodScope, LoopScope loopScope, InvokeData invokeData, ResolvedJavaMethod inlineMethod, PEMethodScope inlineScope) {
615 Invoke invoke = invokeData.invoke;
616 FixedNode invokeNode = invoke.asNode();
617
618 ValueNode exceptionValue = null;
619 List<UnwindNode> unwindNodes = inlineScope.unwindNodes;
620 Iterator<UnwindNode> iter = unwindNodes.iterator();
621 while (iter.hasNext()) {
622 if (iter.next().isDeleted()) {
623 iter.remove();
624 }
625 }
626
627 if (!unwindNodes.isEmpty()) {
628 FixedNode unwindReplacement;
629 if (invoke instanceof InvokeWithExceptionNode) {
630 /* Decoding continues for the exception handler. */
631 unwindReplacement = makeStubNode(methodScope, loopScope, invokeData.exceptionNextOrderId);
632 } else {
633 /* No exception handler available, so the only thing we can do is deoptimize. */
634 unwindReplacement = methodScope.graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateRecompile, DeoptimizationReason.NotCompiledExceptionHandler));
635 }
636
637 if (unwindNodes.size() == 1) {
638 /* Only one UnwindNode, we can use the exception directly. */
639 UnwindNode unwindNode = unwindNodes.get(0);
640 exceptionValue = unwindNode.exception();
641 unwindNode.replaceAndDelete(unwindReplacement);
642
643 } else {
644 /*
645 * More than one UnwindNode. This can happen with the loop explosion strategy
646 * FULL_EXPLODE_UNTIL_RETURN, where we keep exploding after the loop and therefore
647 * also explode exception paths. Merge the exception in a similar way as multiple
648 * return values.
649 */
650 MergeNode unwindMergeNode = methodScope.graph.add(new MergeNode());
651 exceptionValue = InliningUtil.mergeValueProducers(unwindMergeNode, unwindNodes, null, unwindNode -> unwindNode.exception());
652 unwindMergeNode.setNext(unwindReplacement);
653
654 ensureExceptionStateDecoded(inlineScope);
655 unwindMergeNode.setStateAfter(inlineScope.exceptionState.duplicateModified(JavaKind.Object, JavaKind.Object, exceptionValue));
656 }
657 }
658
659 assert invoke.next() == null;
660 assert !(invoke instanceof InvokeWithExceptionNode) || ((InvokeWithExceptionNode) invoke).exceptionEdge() == null;
661
662 ValueNode returnValue;
663 List<ReturnNode> returnNodes = inlineScope.returnNodes;
664 if (!returnNodes.isEmpty()) {
665 if (returnNodes.size() == 1) {
666 ReturnNode returnNode = returnNodes.get(0);
667 returnValue = returnNode.result();
668 FixedNode n = nodeAfterInvoke(methodScope, loopScope, invokeData, AbstractBeginNode.prevBegin(returnNode));
669 returnNode.replaceAndDelete(n);
670 } else {
671 AbstractMergeNode merge = methodScope.graph.add(new MergeNode());
672 merge.setStateAfter((FrameState) ensureNodeCreated(methodScope, loopScope, invokeData.stateAfterOrderId));
673 returnValue = InliningUtil.mergeReturns(merge, returnNodes, null);
674 FixedNode n = nodeAfterInvoke(methodScope, loopScope, invokeData, merge);
675 merge.setNext(n);
676 }
677 } else {
678 returnValue = null;
679 }
680 invokeNode.replaceAtUsages(returnValue);
681
682 /*
683 * Usage the handles that we have on the return value and the exception to update the
684 * orderId->Node table.
685 */
686 registerNode(loopScope, invokeData.invokeOrderId, returnValue, true, true);
687 if (invoke instanceof InvokeWithExceptionNode) {
688 registerNode(loopScope, invokeData.exceptionOrderId, exceptionValue, true, true);
689 }
690 if (inlineScope.exceptionPlaceholderNode != null) {
691 inlineScope.exceptionPlaceholderNode.replaceAtUsagesAndDelete(exceptionValue);
692 }
693 deleteInvoke(invoke);
694
695 for (InlineInvokePlugin plugin : methodScope.inlineInvokePlugins) {
696 plugin.notifyAfterInline(inlineMethod);
697 }
698
699 if (Debug.isDumpEnabled(Debug.INFO_LOG_LEVEL) && DumpDuringGraphBuilding.getValue()) {
700 Debug.dump(Debug.INFO_LOG_LEVEL, methodScope.graph, "Inline finished: %s.%s", inlineMethod.getDeclaringClass().getUnqualifiedName(), inlineMethod.getName());
701 }
702 }
703
704 private static RuntimeException tooDeepInlining(PEMethodScope methodScope) {
705 HashMap<ResolvedJavaMethod, Integer> methodCounts = new HashMap<>();
706 for (PEMethodScope cur = methodScope; cur != null; cur = cur.caller) {
707 Integer oldCount = methodCounts.get(cur.method);
708 methodCounts.put(cur.method, oldCount == null ? 1 : oldCount + 1);
709 }
710
711 List<Map.Entry<ResolvedJavaMethod, Integer>> methods = new ArrayList<>(methodCounts.entrySet());
712 methods.sort((e1, e2) -> -Integer.compare(e1.getValue(), e2.getValue()));
713
714 StringBuilder msg = new StringBuilder("Too deep inlining, probably caused by recursive inlining.").append(System.lineSeparator()).append("== Inlined methods ordered by inlining frequency:");
715 for (Map.Entry<ResolvedJavaMethod, Integer> entry : methods) {
716 msg.append(System.lineSeparator()).append(entry.getKey().format("%H.%n(%p) [")).append(entry.getValue()).append("]");
717 }
718 msg.append(System.lineSeparator()).append("== Complete stack trace of inlined methods:");
719 int lastBci = 0;
720 for (PEMethodScope cur = methodScope; cur != null; cur = cur.caller) {
721 msg.append(System.lineSeparator()).append(cur.method.asStackTraceElement(lastBci));
722 if (cur.invokeData != null) {
723 lastBci = cur.invokeData.invoke.bci();
724 } else {
725 lastBci = 0;
726 }
727 }
728
729 throw new PermanentBailoutException(msg.toString());
730 }
731
732 public FixedNode nodeAfterInvoke(PEMethodScope methodScope, LoopScope loopScope, InvokeData invokeData, AbstractBeginNode lastBlock) {
733 assert lastBlock.isAlive();
734 FixedNode n;
735 if (invokeData.invoke instanceof InvokeWithExceptionNode) {
736 registerNode(loopScope, invokeData.nextOrderId, lastBlock, false, false);
737 n = makeStubNode(methodScope, loopScope, invokeData.nextNextOrderId);
738 } else {
739 n = makeStubNode(methodScope, loopScope, invokeData.nextOrderId);
740 }
741 return n;
742 }
743
744 private static void deleteInvoke(Invoke invoke) {
745 /*
746 * Clean up unused nodes. We cannot just call killCFG on the invoke node because that can
747 * kill too much: nodes that are decoded later can use values that appear unused by now.
748 */
749 FrameState frameState = invoke.stateAfter();
750 invoke.asNode().safeDelete();
751 assert invoke.callTarget() == null : "must not have been added to the graph yet";
752 if (frameState != null && frameState.hasNoUsages()) {
753 frameState.safeDelete();
754 }
755 }
756
757 protected abstract EncodedGraph lookupEncodedGraph(ResolvedJavaMethod method, BytecodeProvider intrinsicBytecodeProvider);
758
759 @SuppressWarnings("try")
760 @Override
761 protected void handleFixedNode(MethodScope s, LoopScope loopScope, int nodeOrderId, FixedNode node) {
762 PEMethodScope methodScope = (PEMethodScope) s;
763 if (node instanceof ForeignCallNode) {
764 ForeignCallNode foreignCall = (ForeignCallNode) node;
765 if (foreignCall.getBci() == BytecodeFrame.UNKNOWN_BCI && methodScope.invokeData != null) {
766 foreignCall.setBci(methodScope.invokeData.invoke.bci());
767 }
768 }
769
770 NodeSourcePosition pos = node.getNodeSourcePosition();
771 if (pos != null && methodScope.isInlinedMethod()) {
772 NodeSourcePosition newPosition = pos.addCaller(methodScope.getCallerBytecodePosition());
773 try (DebugCloseable scope = node.graph().withoutNodeSourcePosition()) {
774 super.handleFixedNode(s, loopScope, nodeOrderId, node);
775 }
776 if (node.isAlive()) {
777 node.setNodeSourcePosition(newPosition);
778 }
779 } else {
780 super.handleFixedNode(s, loopScope, nodeOrderId, node);
781 }
782
783 }
784
785 @Override
786 protected Node handleFloatingNodeBeforeAdd(MethodScope s, LoopScope loopScope, Node node) {
787 PEMethodScope methodScope = (PEMethodScope) s;
788
789 if (node instanceof ParameterNode) {
790 ParameterNode param = (ParameterNode) node;
791 if (methodScope.arguments != null) {
792 Node result = methodScope.arguments[param.index()];
793 assert result != null;
794 return result;
795
796 } else if (methodScope.parameterPlugin != null) {
797 GraphBuilderContext graphBuilderContext = new PENonAppendGraphBuilderContext(methodScope, null);
798 Node result = methodScope.parameterPlugin.interceptParameter(graphBuilderContext, param.index(),
799 StampPair.create(param.stamp(), param.uncheckedStamp()));
800 if (result != null) {
801 return result;
802 }
803 }
804
805 }
806
807 return super.handleFloatingNodeBeforeAdd(methodScope, loopScope, node);
808 }
809
810 protected void ensureOuterStateDecoded(PEMethodScope methodScope) {
811 if (methodScope.outerState == null && methodScope.caller != null) {
812 FrameState stateAtReturn = methodScope.invokeData.invoke.stateAfter();
813 if (stateAtReturn == null) {
814 stateAtReturn = (FrameState) decodeFloatingNode(methodScope.caller, methodScope.callerLoopScope, methodScope.invokeData.stateAfterOrderId);
815 }
816
817 JavaKind invokeReturnKind = methodScope.invokeData.invoke.asNode().getStackKind();
818 FrameState outerState = stateAtReturn.duplicateModified(methodScope.graph, methodScope.invokeData.invoke.bci(), stateAtReturn.rethrowException(), true, invokeReturnKind, null, null);
819
820 /*
821 * When the encoded graph has methods inlining, we can already have a proper caller
822 * state. If not, we set the caller state here.
823 */
824 if (outerState.outerFrameState() == null && methodScope.caller != null) {
825 ensureOuterStateDecoded(methodScope.caller);
826 outerState.setOuterFrameState(methodScope.caller.outerState);
827 }
828 methodScope.outerState = outerState;
829 }
830 }
831
832 protected void ensureStateAfterDecoded(PEMethodScope methodScope) {
833 if (methodScope.invokeData.invoke.stateAfter() == null) {
834 methodScope.invokeData.invoke.setStateAfter((FrameState) ensureNodeCreated(methodScope.caller, methodScope.callerLoopScope, methodScope.invokeData.stateAfterOrderId));
835 }
836 }
837
838 protected void ensureExceptionStateDecoded(PEMethodScope methodScope) {
839 if (methodScope.exceptionState == null && methodScope.caller != null && methodScope.invokeData.invoke instanceof InvokeWithExceptionNode) {
840 ensureStateAfterDecoded(methodScope);
841
842 assert methodScope.exceptionPlaceholderNode == null;
843 methodScope.exceptionPlaceholderNode = methodScope.graph.add(new ExceptionPlaceholderNode());
844 registerNode(methodScope.callerLoopScope, methodScope.invokeData.exceptionOrderId, methodScope.exceptionPlaceholderNode, false, false);
845 FrameState exceptionState = (FrameState) ensureNodeCreated(methodScope.caller, methodScope.callerLoopScope, methodScope.invokeData.exceptionStateOrderId);
846
847 if (exceptionState.outerFrameState() == null && methodScope.caller != null) {
848 ensureOuterStateDecoded(methodScope.caller);
849 exceptionState.setOuterFrameState(methodScope.caller.outerState);
850 }
851 methodScope.exceptionState = exceptionState;
852 }
853 }
854
855 @Override
856 protected Node addFloatingNode(MethodScope s, Node node) {
857 Node addedNode = super.addFloatingNode(s, node);
858 PEMethodScope methodScope = (PEMethodScope) s;
859 NodeSourcePosition pos = node.getNodeSourcePosition();
860 if (methodScope.isInlinedMethod()) {
861 if (pos != null) {
862 NodeSourcePosition bytecodePosition = methodScope.getCallerBytecodePosition();
863 node.setNodeSourcePosition(pos.addCaller(bytecodePosition));
864 }
865 }
866 return addedNode;
867 }
868
869 @Override
870 protected Node handleFloatingNodeAfterAdd(MethodScope s, LoopScope loopScope, Node node) {
871 PEMethodScope methodScope = (PEMethodScope) s;
872
873 if (methodScope.isInlinedMethod()) {
874 if (node instanceof FrameState) {
875 FrameState frameState = (FrameState) node;
876
877 ensureOuterStateDecoded(methodScope);
878 if (frameState.bci < 0) {
879 ensureExceptionStateDecoded(methodScope);
880 }
881 List<ValueNode> invokeArgsList = null;
882 if (frameState.bci == BytecodeFrame.BEFORE_BCI) {
883 /*
884 * We know that the argument list is only used in this case, so avoid the List
885 * allocation for "normal" bcis.
886 */
887 invokeArgsList = Arrays.asList(methodScope.arguments);
888 }
889 return InliningUtil.processFrameState(frameState, methodScope.invokeData.invoke, methodScope.method, methodScope.exceptionState, methodScope.outerState, true, methodScope.method,
890 invokeArgsList);
891
892 } else if (node instanceof MonitorIdNode) {
893 ensureOuterStateDecoded(methodScope);
894 InliningUtil.processMonitorId(methodScope.outerState, (MonitorIdNode) node);
895 return node;
896 }
897 }
898
899 return node;
900 }
901 }