1 /*
2 * Copyright (c) 2014, 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.nodes.graphbuilderconf.IntrinsicContext.CompilationContext.INLINE_AFTER_PARSING;
26
27 import java.lang.reflect.Method;
28 import java.lang.reflect.Modifier;
29 import java.util.ArrayList;
30 import java.util.List;
31
32 import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
33 import org.graalvm.compiler.core.common.type.StampFactory;
34 import org.graalvm.compiler.core.common.type.StampPair;
35 import org.graalvm.compiler.graph.Graph;
36 import org.graalvm.compiler.graph.Node.ValueNumberable;
37 import org.graalvm.compiler.java.FrameStateBuilder;
38 import org.graalvm.compiler.java.GraphBuilderPhase;
39 import org.graalvm.compiler.nodes.AbstractBeginNode;
40 import org.graalvm.compiler.nodes.AbstractMergeNode;
41 import org.graalvm.compiler.nodes.BeginNode;
42 import org.graalvm.compiler.nodes.CallTargetNode.InvokeKind;
43 import org.graalvm.compiler.nodes.EndNode;
44 import org.graalvm.compiler.nodes.FixedNode;
45 import org.graalvm.compiler.nodes.FixedWithNextNode;
46 import org.graalvm.compiler.nodes.IfNode;
47 import org.graalvm.compiler.nodes.InvokeNode;
48 import org.graalvm.compiler.nodes.InvokeWithExceptionNode;
49 import org.graalvm.compiler.nodes.KillingBeginNode;
50 import org.graalvm.compiler.nodes.LogicNode;
51 import org.graalvm.compiler.nodes.MergeNode;
52 import org.graalvm.compiler.nodes.StructuredGraph;
53 import org.graalvm.compiler.nodes.ValueNode;
54 import org.graalvm.compiler.nodes.calc.FloatingNode;
55 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration;
56 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.Plugins;
57 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderTool;
58 import org.graalvm.compiler.nodes.graphbuilderconf.IntrinsicContext;
59 import org.graalvm.compiler.nodes.java.ExceptionObjectNode;
60 import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
61 import org.graalvm.compiler.nodes.spi.StampProvider;
62 import org.graalvm.compiler.nodes.type.StampTool;
63 import org.graalvm.compiler.phases.OptimisticOptimizations;
64 import org.graalvm.compiler.phases.common.DeadCodeEliminationPhase;
65 import org.graalvm.compiler.phases.common.DeadCodeEliminationPhase.Optionality;
66 import org.graalvm.compiler.phases.common.inlining.InliningUtil;
67 import org.graalvm.compiler.phases.util.Providers;
68 import org.graalvm.compiler.word.WordTypes;
69 import org.graalvm.word.LocationIdentity;
70
71 import jdk.vm.ci.code.BytecodeFrame;
72 import jdk.vm.ci.meta.ConstantReflectionProvider;
73 import jdk.vm.ci.meta.JavaKind;
74 import jdk.vm.ci.meta.JavaType;
75 import jdk.vm.ci.meta.MetaAccessProvider;
76 import jdk.vm.ci.meta.ResolvedJavaMethod;
77 import jdk.vm.ci.meta.ResolvedJavaType;
78 import jdk.vm.ci.meta.Signature;
79
80 /**
81 * A utility for manually creating a graph. This will be expanded as necessary to support all
82 * subsystems that employ manual graph creation (as opposed to {@linkplain GraphBuilderPhase
83 * bytecode parsing} based graph creation).
84 */
85 public class GraphKit implements GraphBuilderTool {
86
87 protected final Providers providers;
88 protected final StructuredGraph graph;
89 protected final WordTypes wordTypes;
90 protected final GraphBuilderConfiguration.Plugins graphBuilderPlugins;
91 protected FixedWithNextNode lastFixedNode;
92
93 private final List<Structure> structures;
94
95 protected abstract static class Structure {
96 }
97
98 public GraphKit(StructuredGraph graph, Providers providers, WordTypes wordTypes, GraphBuilderConfiguration.Plugins graphBuilderPlugins) {
99 this.providers = providers;
100 this.graph = graph;
101 this.wordTypes = wordTypes;
102 this.graphBuilderPlugins = graphBuilderPlugins;
103 this.lastFixedNode = graph.start();
104
105 structures = new ArrayList<>();
106 /*
107 * Add a dummy element, so that the access of the last element never leads to an exception.
108 */
109 structures.add(new Structure() {
110 });
111 }
112
113 @Override
114 public StructuredGraph getGraph() {
115 return graph;
116 }
117
118 @Override
119 public ConstantReflectionProvider getConstantReflection() {
120 return providers.getConstantReflection();
121 }
122
123 @Override
124 public ConstantFieldProvider getConstantFieldProvider() {
125 return providers.getConstantFieldProvider();
126 }
127
128 @Override
129 public MetaAccessProvider getMetaAccess() {
130 return providers.getMetaAccess();
131 }
132
133 @Override
134 public StampProvider getStampProvider() {
135 return providers.getStampProvider();
136 }
137
138 @Override
139 public boolean parsingIntrinsic() {
140 return true;
141 }
142
143 /**
144 * Ensures a floating node is added to or already present in the graph via {@link Graph#unique}.
145 *
146 * @return a node similar to {@code node} if one exists, otherwise {@code node}
147 */
148 public <T extends FloatingNode & ValueNumberable> T unique(T node) {
149 return graph.unique(changeToWord(node));
150 }
151
152 public <T extends ValueNode> T add(T node) {
153 return graph.add(changeToWord(node));
154 }
155
156 public <T extends ValueNode> T changeToWord(T node) {
157 if (wordTypes != null && wordTypes.isWord(node)) {
158 node.setStamp(wordTypes.getWordStamp(StampTool.typeOrNull(node)));
159 }
160 return node;
161 }
162
163 @Override
164 public <T extends ValueNode> T append(T node) {
165 T result = graph.addOrUniqueWithInputs(changeToWord(node));
166 if (result instanceof FixedNode) {
167 updateLastFixed((FixedNode) result);
168 }
169 return result;
170 }
171
172 private void updateLastFixed(FixedNode result) {
173 assert lastFixedNode != null;
174 assert result.predecessor() == null;
175 graph.addAfterFixed(lastFixedNode, result);
176 if (result instanceof FixedWithNextNode) {
177 lastFixedNode = (FixedWithNextNode) result;
178 } else {
179 lastFixedNode = null;
180 }
181 }
182
183 public InvokeNode createInvoke(Class<?> declaringClass, String name, ValueNode... args) {
184 return createInvoke(declaringClass, name, InvokeKind.Static, null, BytecodeFrame.UNKNOWN_BCI, args);
185 }
186
187 /**
188 * Creates and appends an {@link InvokeNode} for a call to a given method with a given set of
189 * arguments. The method is looked up via reflection based on the declaring class and name.
190 *
191 * @param declaringClass the class declaring the invoked method
192 * @param name the name of the invoked method
193 * @param args the arguments to the invocation
194 */
195 public InvokeNode createInvoke(Class<?> declaringClass, String name, InvokeKind invokeKind, FrameStateBuilder frameStateBuilder, int bci, ValueNode... args) {
196 boolean isStatic = invokeKind == InvokeKind.Static;
197 ResolvedJavaMethod method = findMethod(declaringClass, name, isStatic);
198 return createInvoke(method, invokeKind, frameStateBuilder, bci, args);
199 }
200
201 public ResolvedJavaMethod findMethod(Class<?> declaringClass, String name, boolean isStatic) {
202 ResolvedJavaMethod method = null;
203 for (Method m : declaringClass.getDeclaredMethods()) {
204 if (Modifier.isStatic(m.getModifiers()) == isStatic && m.getName().equals(name)) {
205 assert method == null : "found more than one method in " + declaringClass + " named " + name;
206 method = providers.getMetaAccess().lookupJavaMethod(m);
207 }
208 }
209 assert method != null : "did not find method in " + declaringClass + " named " + name;
210 return method;
211 }
212
213 public ResolvedJavaMethod findMethod(Class<?> declaringClass, String name, Class<?>... parameterTypes) {
214 try {
215 Method m = declaringClass.getDeclaredMethod(name, parameterTypes);
216 return providers.getMetaAccess().lookupJavaMethod(m);
217 } catch (NoSuchMethodException | SecurityException e) {
218 throw new AssertionError(e);
219 }
220 }
221
222 /**
223 * Creates and appends an {@link InvokeNode} for a call to a given method with a given set of
224 * arguments.
225 */
226 public InvokeNode createInvoke(ResolvedJavaMethod method, InvokeKind invokeKind, FrameStateBuilder frameStateBuilder, int bci, ValueNode... args) {
227 assert method.isStatic() == (invokeKind == InvokeKind.Static);
228 Signature signature = method.getSignature();
229 JavaType returnType = signature.getReturnType(null);
230 assert checkArgs(method, args);
231 StampPair returnStamp = graphBuilderPlugins.getOverridingStamp(this, returnType, false);
232 if (returnStamp == null) {
233 returnStamp = StampFactory.forDeclaredType(graph.getAssumptions(), returnType, false);
234 }
235 MethodCallTargetNode callTarget = graph.add(createMethodCallTarget(invokeKind, method, args, returnStamp, bci));
236 InvokeNode invoke = append(new InvokeNode(callTarget, bci));
237
238 if (frameStateBuilder != null) {
239 if (invoke.getStackKind() != JavaKind.Void) {
240 frameStateBuilder.push(returnType.getJavaKind(), invoke);
241 }
242 invoke.setStateAfter(frameStateBuilder.create(bci, invoke));
243 if (invoke.getStackKind() != JavaKind.Void) {
244 frameStateBuilder.pop(returnType.getJavaKind());
245 }
246 }
247 return invoke;
248 }
249
250 protected MethodCallTargetNode createMethodCallTarget(InvokeKind invokeKind, ResolvedJavaMethod targetMethod, ValueNode[] args, StampPair returnStamp, @SuppressWarnings("unused") int bci) {
251 return new MethodCallTargetNode(invokeKind, targetMethod, args, returnStamp, null);
252 }
253
254 /**
255 * Determines if a given set of arguments is compatible with the signature of a given method.
256 *
257 * @return true if {@code args} are compatible with the signature if {@code method}
258 * @throws AssertionError if {@code args} are not compatible with the signature if
259 * {@code method}
260 */
261 public boolean checkArgs(ResolvedJavaMethod method, ValueNode... args) {
262 Signature signature = method.getSignature();
263 boolean isStatic = method.isStatic();
264 if (signature.getParameterCount(!isStatic) != args.length) {
265 throw new AssertionError(graph + ": wrong number of arguments to " + method);
266 }
267 int argIndex = 0;
268 if (!isStatic) {
269 ResolvedJavaType expectedType = method.getDeclaringClass();
270 JavaKind expected = wordTypes == null ? expectedType.getJavaKind() : wordTypes.asKind(expectedType);
271 JavaKind actual = args[argIndex++].stamp().getStackKind();
272 assert expected == actual : graph + ": wrong kind of value for receiver argument of call to " + method + " [" + actual + " != " + expected + "]";
273 }
274 for (int i = 0; i != signature.getParameterCount(false); i++) {
275 JavaType expectedType = signature.getParameterType(i, method.getDeclaringClass());
276 JavaKind expected = wordTypes == null ? expectedType.getJavaKind().getStackKind() : wordTypes.asKind(expectedType).getStackKind();
277 JavaKind actual = args[argIndex++].stamp().getStackKind();
278 if (expected != actual) {
279 throw new AssertionError(graph + ": wrong kind of value for argument " + i + " of call to " + method + " [" + actual + " != " + expected + "]");
280 }
281 }
282 return true;
283 }
284
285 /**
286 * Recursively {@linkplain #inline inlines} all invocations currently in the graph.
287 */
288 public void inlineInvokes() {
289 while (!graph.getNodes().filter(InvokeNode.class).isEmpty()) {
290 for (InvokeNode invoke : graph.getNodes().filter(InvokeNode.class).snapshot()) {
291 inline(invoke);
292 }
293 }
294
295 // Clean up all code that is now dead after inlining.
296 new DeadCodeEliminationPhase().apply(graph);
297 }
298
299 /**
300 * Inlines a given invocation to a method. The graph of the inlined method is processed in the
301 * same manner as for snippets and method substitutions.
302 */
303 public void inline(InvokeNode invoke) {
304 ResolvedJavaMethod method = ((MethodCallTargetNode) invoke.callTarget()).targetMethod();
305
306 MetaAccessProvider metaAccess = providers.getMetaAccess();
307 Plugins plugins = new Plugins(graphBuilderPlugins);
308 GraphBuilderConfiguration config = GraphBuilderConfiguration.getSnippetDefault(plugins);
309
310 StructuredGraph calleeGraph = new StructuredGraph.Builder(invoke.getOptions()).method(method).build();
311 IntrinsicContext initialReplacementContext = new IntrinsicContext(method, method, providers.getReplacements().getDefaultReplacementBytecodeProvider(), INLINE_AFTER_PARSING);
312 GraphBuilderPhase.Instance instance = new GraphBuilderPhase.Instance(metaAccess, providers.getStampProvider(), providers.getConstantReflection(), providers.getConstantFieldProvider(), config,
313 OptimisticOptimizations.NONE,
314 initialReplacementContext);
315 instance.apply(calleeGraph);
316
317 // Remove all frame states from inlinee
318 calleeGraph.clearAllStateAfter();
319 new DeadCodeEliminationPhase(Optionality.Required).apply(calleeGraph);
320
321 InliningUtil.inline(invoke, calleeGraph, false, method);
322 }
323
324 protected void pushStructure(Structure structure) {
325 structures.add(structure);
326 }
327
328 protected <T extends Structure> T getTopStructure(Class<T> expectedClass) {
329 return expectedClass.cast(structures.get(structures.size() - 1));
330 }
331
332 protected void popStructure() {
333 structures.remove(structures.size() - 1);
334 }
335
336 protected enum IfState {
337 CONDITION,
338 THEN_PART,
339 ELSE_PART,
340 FINISHED
341 }
342
343 static class IfStructure extends Structure {
344 protected IfState state;
345 protected FixedNode thenPart;
346 protected FixedNode elsePart;
347 }
348
349 /**
350 * Starts an if-block. This call can be followed by a call to {@link #thenPart} to start
351 * emitting the code executed when the condition hold; and a call to {@link #elsePart} to start
352 * emititng the code when the condition does not hold. It must be followed by a call to
353 * {@link #endIf} to close the if-block.
354 *
355 * @param condition The condition for the if-block
356 * @param trueProbability The estimated probability the condition is true
357 */
358 public void startIf(LogicNode condition, double trueProbability) {
359 AbstractBeginNode thenSuccessor = graph.add(new BeginNode());
360 AbstractBeginNode elseSuccessor = graph.add(new BeginNode());
361 append(new IfNode(condition, thenSuccessor, elseSuccessor, trueProbability));
362 lastFixedNode = null;
363
364 IfStructure s = new IfStructure();
365 s.state = IfState.CONDITION;
366 s.thenPart = thenSuccessor;
367 s.elsePart = elseSuccessor;
368 pushStructure(s);
369 }
370
371 private IfStructure saveLastIfNode() {
372 IfStructure s = getTopStructure(IfStructure.class);
373 switch (s.state) {
374 case CONDITION:
375 assert lastFixedNode == null;
376 break;
377 case THEN_PART:
378 s.thenPart = lastFixedNode;
379 break;
380 case ELSE_PART:
381 s.elsePart = lastFixedNode;
382 break;
383 case FINISHED:
384 assert false;
385 break;
386 }
387 lastFixedNode = null;
388 return s;
389 }
390
391 public void thenPart() {
392 IfStructure s = saveLastIfNode();
393 lastFixedNode = (FixedWithNextNode) s.thenPart;
394 s.state = IfState.THEN_PART;
395 }
396
397 public void elsePart() {
398 IfStructure s = saveLastIfNode();
399 lastFixedNode = (FixedWithNextNode) s.elsePart;
400 s.state = IfState.ELSE_PART;
401 }
402
403 public void endIf() {
404 IfStructure s = saveLastIfNode();
405
406 FixedWithNextNode thenPart = s.thenPart instanceof FixedWithNextNode ? (FixedWithNextNode) s.thenPart : null;
407 FixedWithNextNode elsePart = s.elsePart instanceof FixedWithNextNode ? (FixedWithNextNode) s.elsePart : null;
408
409 if (thenPart != null && elsePart != null) {
410 /* Both parts are alive, we need a real merge. */
411 EndNode thenEnd = graph.add(new EndNode());
412 graph.addAfterFixed(thenPart, thenEnd);
413 EndNode elseEnd = graph.add(new EndNode());
414 graph.addAfterFixed(elsePart, elseEnd);
415
416 AbstractMergeNode merge = graph.add(new MergeNode());
417 merge.addForwardEnd(thenEnd);
418 merge.addForwardEnd(elseEnd);
419
420 lastFixedNode = merge;
421
422 } else if (thenPart != null) {
423 /* elsePart ended with a control sink, so we can continue with thenPart. */
424 lastFixedNode = thenPart;
425
426 } else if (elsePart != null) {
427 /* thenPart ended with a control sink, so we can continue with elsePart. */
428 lastFixedNode = elsePart;
429
430 } else {
431 /* Both parts ended with a control sink, so no nodes can be added after the if. */
432 assert lastFixedNode == null;
433 }
434 s.state = IfState.FINISHED;
435 popStructure();
436 }
437
438 static class InvokeWithExceptionStructure extends Structure {
439 protected enum State {
440 INVOKE,
441 NO_EXCEPTION_EDGE,
442 EXCEPTION_EDGE,
443 FINISHED
444 }
445
446 protected State state;
447 protected ExceptionObjectNode exceptionObject;
448 protected FixedNode noExceptionEdge;
449 protected FixedNode exceptionEdge;
450 }
451
452 public InvokeWithExceptionNode startInvokeWithException(ResolvedJavaMethod method, InvokeKind invokeKind,
453 FrameStateBuilder frameStateBuilder, int invokeBci, int exceptionEdgeBci, ValueNode... args) {
454
455 assert method.isStatic() == (invokeKind == InvokeKind.Static);
456 Signature signature = method.getSignature();
457 JavaType returnType = signature.getReturnType(null);
458 assert checkArgs(method, args);
459 StampPair returnStamp = graphBuilderPlugins.getOverridingStamp(this, returnType, false);
460 if (returnStamp == null) {
461 returnStamp = StampFactory.forDeclaredType(graph.getAssumptions(), returnType, false);
462 }
463 ExceptionObjectNode exceptionObject = add(new ExceptionObjectNode(getMetaAccess()));
464 if (frameStateBuilder != null) {
465 FrameStateBuilder exceptionState = frameStateBuilder.copy();
466 exceptionState.clearStack();
467 exceptionState.push(JavaKind.Object, exceptionObject);
468 exceptionState.setRethrowException(false);
469 exceptionObject.setStateAfter(exceptionState.create(exceptionEdgeBci, exceptionObject));
470 }
471 MethodCallTargetNode callTarget = graph.add(createMethodCallTarget(invokeKind, method, args, returnStamp, invokeBci));
472 InvokeWithExceptionNode invoke = append(new InvokeWithExceptionNode(callTarget, exceptionObject, invokeBci));
473 AbstractBeginNode noExceptionEdge = graph.add(KillingBeginNode.create(LocationIdentity.any()));
474 invoke.setNext(noExceptionEdge);
475 if (frameStateBuilder != null) {
476 if (invoke.getStackKind() != JavaKind.Void) {
477 frameStateBuilder.push(returnType.getJavaKind(), invoke);
478 }
479 invoke.setStateAfter(frameStateBuilder.create(invokeBci, invoke));
480 if (invoke.getStackKind() != JavaKind.Void) {
481 frameStateBuilder.pop(returnType.getJavaKind());
482 }
483 }
484 lastFixedNode = null;
485
486 InvokeWithExceptionStructure s = new InvokeWithExceptionStructure();
487 s.state = InvokeWithExceptionStructure.State.INVOKE;
488 s.noExceptionEdge = noExceptionEdge;
489 s.exceptionEdge = exceptionObject;
490 s.exceptionObject = exceptionObject;
491 pushStructure(s);
492
493 return invoke;
494 }
495
496 private InvokeWithExceptionStructure saveLastInvokeWithExceptionNode() {
497 InvokeWithExceptionStructure s = getTopStructure(InvokeWithExceptionStructure.class);
498 switch (s.state) {
499 case INVOKE:
500 assert lastFixedNode == null;
501 break;
502 case NO_EXCEPTION_EDGE:
503 s.noExceptionEdge = lastFixedNode;
504 break;
505 case EXCEPTION_EDGE:
506 s.exceptionEdge = lastFixedNode;
507 break;
508 case FINISHED:
509 assert false;
510 break;
511 }
512 lastFixedNode = null;
513 return s;
514 }
515
516 public void noExceptionPart() {
517 InvokeWithExceptionStructure s = saveLastInvokeWithExceptionNode();
518 lastFixedNode = (FixedWithNextNode) s.noExceptionEdge;
519 s.state = InvokeWithExceptionStructure.State.NO_EXCEPTION_EDGE;
520 }
521
522 public void exceptionPart() {
523 InvokeWithExceptionStructure s = saveLastInvokeWithExceptionNode();
524 lastFixedNode = (FixedWithNextNode) s.exceptionEdge;
525 s.state = InvokeWithExceptionStructure.State.EXCEPTION_EDGE;
526 }
527
528 public ExceptionObjectNode exceptionObject() {
529 InvokeWithExceptionStructure s = getTopStructure(InvokeWithExceptionStructure.class);
530 return s.exceptionObject;
531 }
532
533 /**
534 * Finishes a control flow started with {@link #startInvokeWithException}. If necessary, creates
535 * a merge of the non-exception and exception edges. The merge node is returned and the
536 * non-exception edge is the first forward end of the merge, the exception edge is the second
537 * forward end (relevant for phi nodes).
538 */
539 public AbstractMergeNode endInvokeWithException() {
540 InvokeWithExceptionStructure s = saveLastInvokeWithExceptionNode();
541 FixedWithNextNode noExceptionEdge = s.noExceptionEdge instanceof FixedWithNextNode ? (FixedWithNextNode) s.noExceptionEdge : null;
542 FixedWithNextNode exceptionEdge = s.exceptionEdge instanceof FixedWithNextNode ? (FixedWithNextNode) s.exceptionEdge : null;
543 AbstractMergeNode merge = null;
544 if (noExceptionEdge != null && exceptionEdge != null) {
545 EndNode noExceptionEnd = graph.add(new EndNode());
546 graph.addAfterFixed(noExceptionEdge, noExceptionEnd);
547 EndNode exceptionEnd = graph.add(new EndNode());
548 graph.addAfterFixed(exceptionEdge, exceptionEnd);
549 merge = graph.add(new MergeNode());
550 merge.addForwardEnd(noExceptionEnd);
551 merge.addForwardEnd(exceptionEnd);
552 lastFixedNode = merge;
553 } else if (noExceptionEdge != null) {
554 lastFixedNode = noExceptionEdge;
555 } else if (exceptionEdge != null) {
556 lastFixedNode = exceptionEdge;
557 } else {
558 assert lastFixedNode == null;
559 }
560 s.state = InvokeWithExceptionStructure.State.FINISHED;
561 popStructure();
562 return merge;
563 }
564 }