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