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.core.test.tutorial;
26
27 import static org.graalvm.compiler.core.test.GraalCompilerTest.getInitialOptions;
28
29 import java.util.ArrayDeque;
30 import java.util.Collections;
31 import java.util.Deque;
32 import java.util.HashMap;
33 import java.util.HashSet;
34 import java.util.Map;
35 import java.util.Set;
36
37 import org.graalvm.compiler.debug.DebugHandlersFactory;
38 import org.graalvm.compiler.debug.DebugContext;
39 import org.graalvm.compiler.debug.GraalError;
40 import org.graalvm.compiler.graph.Node;
41 import org.graalvm.compiler.graph.NodeMap;
42 import org.graalvm.compiler.java.GraphBuilderPhase;
43 import org.graalvm.compiler.nodes.CallTargetNode.InvokeKind;
44 import org.graalvm.compiler.nodes.ConstantNode;
45 import org.graalvm.compiler.nodes.FixedNode;
46 import org.graalvm.compiler.nodes.Invoke;
47 import org.graalvm.compiler.nodes.ParameterNode;
48 import org.graalvm.compiler.nodes.ReturnNode;
49 import org.graalvm.compiler.nodes.StructuredGraph;
50 import org.graalvm.compiler.nodes.ValueNode;
51 import org.graalvm.compiler.nodes.ValuePhiNode;
52 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration;
53 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.BytecodeExceptionMode;
54 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.Plugins;
55 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins;
56 import org.graalvm.compiler.nodes.java.LoadFieldNode;
57 import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
58 import org.graalvm.compiler.nodes.java.NewArrayNode;
59 import org.graalvm.compiler.nodes.java.NewInstanceNode;
60 import org.graalvm.compiler.nodes.java.StoreFieldNode;
61 import org.graalvm.compiler.nodes.spi.StampProvider;
62 import org.graalvm.compiler.nodes.util.GraphUtil;
63 import org.graalvm.compiler.options.OptionValues;
64 import org.graalvm.compiler.phases.OptimisticOptimizations;
65 import org.graalvm.compiler.phases.graph.StatelessPostOrderNodeIterator;
66
67 import jdk.vm.ci.meta.JavaConstant;
68 import jdk.vm.ci.meta.JavaKind;
69 import jdk.vm.ci.meta.MetaAccessProvider;
70 import jdk.vm.ci.meta.ResolvedJavaField;
71 import jdk.vm.ci.meta.ResolvedJavaMethod;
72 import jdk.vm.ci.meta.ResolvedJavaType;
73
74 /**
75 * A simple context-insensitive static analysis based on the Graal API. It is intended for
76 * educational purposes, not for use in production. Only a limited set of Java functionality is
77 * supported to keep the code minimal.
78 * <p>
79 * The analysis builds a directed graph of {@link TypeFlow type flows}. If a type is added to type
80 * flow, it is propagated to all {@link TypeFlow#uses uses} of the type flow. Types are propagated
81 * using a {@link #worklist} of changed type flows until a fixpoint is reached, i.e., until no more
82 * types need to be added to any type state.
83 * <p>
84 * The type flows are constructed from a high-level Graal graph by the {@link TypeFlowBuilder}. All
85 * nodes that operate on {@link JavaKind#Object object} values are converted to the appropriate type
86 * flows. The analysis is context insensitive: every Java field has {@link Results#lookupField one
87 * list} of types assigned to the field; every Java method has {@link Results#lookupMethod one
88 * state} for each {@link MethodState#formalParameters parameter} as well as the
89 * {@link MethodState#formalReturn return value}.
90 */
91 public class StaticAnalysis {
92 /** Access to type, method, and fields using the Graal API. */
93 private final MetaAccessProvider metaAccess;
94 /** Access to platform dependent stamps. */
95 private final StampProvider stampProvider;
96 /** The results of the static analysis. */
97 private final Results results;
98 /** Worklist for fixpoint iteration. */
99 private final Deque<WorklistEntry> worklist;
100
101 public StaticAnalysis(MetaAccessProvider metaAccess, StampProvider stampProvider) {
102 this.metaAccess = metaAccess;
103 this.stampProvider = stampProvider;
104 this.results = new Results();
105 this.worklist = new ArrayDeque<>();
106 }
107
108 /**
109 * Adds a root method to the static analysis. The method must be static and must not have any
110 * parameters, because the possible types of the parameters would not be known.
111 */
112 public void addMethod(ResolvedJavaMethod method) {
113 if (!method.isStatic() || method.getSignature().getParameterCount(false) > 0) {
114 error("Entry point method is not static or has parameters: " + method.format("%H.%n(%p)"));
115 }
116 addToWorklist(results.lookupMethod(method));
117 }
118
119 /**
120 * Performs the fixed-point analysis that finds all methods transitively reachable from the
121 * {@link #addMethod root methods}.
122 */
123 public void finish() {
256 * referenced by the bytecodes to be loaded and initialized. Since we do not run
257 * the code before static analysis, the classes would otherwise be not loaded
258 * yet and the bytecode parser would only create a graph.
259 */
260 Plugins plugins = new Plugins(new InvocationPlugins());
261 GraphBuilderConfiguration graphBuilderConfig = GraphBuilderConfiguration.getDefault(plugins).withEagerResolving(true).withUnresolvedIsError(true);
262 /*
263 * For simplicity, we ignore all exception handling during the static analysis.
264 * This is a constraint of this example code, a real static analysis needs to
265 * handle the Graal nodes for throwing and handling exceptions.
266 */
267 graphBuilderConfig = graphBuilderConfig.withBytecodeExceptionMode(BytecodeExceptionMode.OmitAll);
268 /*
269 * We do not want Graal to perform any speculative optimistic optimizations,
270 * i.e., we do not want to use profiling information. Since we do not run the
271 * code before static analysis, the profiling information is empty and therefore
272 * wrong.
273 */
274 OptimisticOptimizations optimisticOpts = OptimisticOptimizations.NONE;
275
276 GraphBuilderPhase.Instance graphBuilder = new GraphBuilderPhase.Instance(metaAccess, stampProvider, null, null, graphBuilderConfig, optimisticOpts, null);
277 graphBuilder.apply(graph);
278 } catch (Throwable ex) {
279 debug.handle(ex);
280 }
281
282 /*
283 * Build the type flow graph from the Graal graph, i.e., process all nodes that are
284 * deal with objects.
285 */
286
287 TypeFlowBuilder typeFlowBuilder = new TypeFlowBuilder(graph);
288 typeFlowBuilder.apply();
289 }
290 }
291 }
292
293 /**
294 * The active element during static analysis: types are added until a fixed point is reached.
295 * When a new type is added, it is propagated to all usages by putting this element on the
296 * {@link StaticAnalysis#addToWorklist worklist}.
297 */
298 public class TypeFlow extends WorklistEntry {
299 private final Set<ResolvedJavaType> types;
300 private final Set<TypeFlow> uses;
301
302 protected TypeFlow() {
303 types = new HashSet<>();
304 uses = new HashSet<>();
305 }
306
307 /** Returns the types of this element. */
308 public Set<ResolvedJavaType> getTypes() {
309 return types;
310 }
311
312 /**
313 * Adds new types to this element. If that changes the state of this element, it is added to
314 * the {@link StaticAnalysis#addToWorklist worklist} in order to propagate the added types
315 * to all usages.
316 */
317 protected void addTypes(Set<ResolvedJavaType> newTypes) {
318 if (types.addAll(newTypes)) {
319 addToWorklist(this);
320 }
321 }
322
323 /**
324 * Adds a new use to this element. All types of this element are propagated to the new
325 * usage.
326 */
327 protected void addUse(TypeFlow use) {
332
333 /**
334 * Processing of the worklist element: propagate the types to all usages. That in turn can
335 * add the usages to the worklist (if the types of the usage are changed).
336 */
337 @Override
338 protected void process() {
339 for (TypeFlow use : uses) {
340 use.addTypes(types);
341 }
342 }
343 }
344
345 /**
346 * The active element for method invocations. For {@link InvokeKind#Virtual virtual} and
347 * {@link InvokeKind#Interface interface} calls, the {@link TypeFlow#getTypes() types} of this
348 * node are the receiver types. When a new receiver type is added, a new callee might be added.
349 * Adding a new callee means linking the type flow of the actual parameters with the formal
350 * parameters of the callee, and linking the return value of the callee with the return value
351 * state of the invocation.
352 *
353 * Statically bindable methods calls ({@link InvokeKind#Static static} and
354 * {@link InvokeKind#Special special} calls) have only one callee, but use the same code for
355 * simplicity.
356 */
357 class InvokeTypeFlow extends TypeFlow {
358 private final MethodCallTargetNode callTarget;
359 private final TypeFlow[] actualParameters;
360 private final TypeFlow actualReturn;
361 private final Set<ResolvedJavaMethod> callees;
362
363 protected InvokeTypeFlow(MethodCallTargetNode callTarget, TypeFlow[] actualParameterFlows, TypeFlow actualReturnFlow) {
364 this.callTarget = callTarget;
365 this.actualParameters = actualParameterFlows;
366 this.actualReturn = actualReturnFlow;
367 this.callees = new HashSet<>();
368 }
369
370 private void linkCallee(ResolvedJavaMethod callee) {
371 if (callees.add(callee)) {
372 /* We have added a new callee. */
|
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.core.test.tutorial;
26
27 import static org.graalvm.compiler.core.test.GraalCompilerTest.getInitialOptions;
28
29 import java.util.ArrayDeque;
30 import java.util.Collections;
31 import java.util.Deque;
32 import java.util.HashMap;
33 import java.util.HashSet;
34 import java.util.Map;
35 import java.util.Set;
36
37 import org.graalvm.compiler.debug.DebugContext;
38 import org.graalvm.compiler.debug.DebugHandlersFactory;
39 import org.graalvm.compiler.debug.GraalError;
40 import org.graalvm.compiler.graph.Node;
41 import org.graalvm.compiler.graph.NodeMap;
42 import org.graalvm.compiler.java.GraphBuilderPhase;
43 import org.graalvm.compiler.nodes.CallTargetNode.InvokeKind;
44 import org.graalvm.compiler.nodes.ConstantNode;
45 import org.graalvm.compiler.nodes.FixedNode;
46 import org.graalvm.compiler.nodes.Invoke;
47 import org.graalvm.compiler.nodes.ParameterNode;
48 import org.graalvm.compiler.nodes.ReturnNode;
49 import org.graalvm.compiler.nodes.StructuredGraph;
50 import org.graalvm.compiler.nodes.ValueNode;
51 import org.graalvm.compiler.nodes.ValuePhiNode;
52 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration;
53 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.BytecodeExceptionMode;
54 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.Plugins;
55 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins;
56 import org.graalvm.compiler.nodes.java.LoadFieldNode;
57 import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
58 import org.graalvm.compiler.nodes.java.NewArrayNode;
59 import org.graalvm.compiler.nodes.java.NewInstanceNode;
60 import org.graalvm.compiler.nodes.java.StoreFieldNode;
61 import org.graalvm.compiler.nodes.spi.CoreProviders;
62 import org.graalvm.compiler.nodes.util.GraphUtil;
63 import org.graalvm.compiler.options.OptionValues;
64 import org.graalvm.compiler.phases.OptimisticOptimizations;
65 import org.graalvm.compiler.phases.graph.StatelessPostOrderNodeIterator;
66
67 import jdk.vm.ci.meta.JavaConstant;
68 import jdk.vm.ci.meta.JavaKind;
69 import jdk.vm.ci.meta.ResolvedJavaField;
70 import jdk.vm.ci.meta.ResolvedJavaMethod;
71 import jdk.vm.ci.meta.ResolvedJavaType;
72
73 /**
74 * A simple context-insensitive static analysis based on the Graal API. It is intended for
75 * educational purposes, not for use in production. Only a limited set of Java functionality is
76 * supported to keep the code minimal.
77 * <p>
78 * The analysis builds a directed graph of {@link TypeFlow type flows}. If a type is added to type
79 * flow, it is propagated to all {@link TypeFlow#uses uses} of the type flow. Types are propagated
80 * using a {@link #worklist} of changed type flows until a fixpoint is reached, i.e., until no more
81 * types need to be added to any type state.
82 * <p>
83 * The type flows are constructed from a high-level Graal graph by the {@link TypeFlowBuilder}. All
84 * nodes that operate on {@link JavaKind#Object object} values are converted to the appropriate type
85 * flows. The analysis is context insensitive: every Java field has {@link Results#lookupField one
86 * list} of types assigned to the field; every Java method has {@link Results#lookupMethod one
87 * state} for each {@link MethodState#formalParameters parameter} as well as the
88 * {@link MethodState#formalReturn return value}.
89 */
90 public class StaticAnalysis {
91 /**
92 * Access to various builtin providers.
93 */
94 private final CoreProviders providers;
95 /**
96 * The results of the static analysis.
97 */
98 private final Results results;
99 /**
100 * Worklist for fixpoint iteration.
101 */
102 private final Deque<WorklistEntry> worklist;
103
104 public StaticAnalysis(CoreProviders providers) {
105 this.providers = providers;
106 this.results = new Results();
107 this.worklist = new ArrayDeque<>();
108 }
109
110 /**
111 * Adds a root method to the static analysis. The method must be static and must not have any
112 * parameters, because the possible types of the parameters would not be known.
113 */
114 public void addMethod(ResolvedJavaMethod method) {
115 if (!method.isStatic() || method.getSignature().getParameterCount(false) > 0) {
116 error("Entry point method is not static or has parameters: " + method.format("%H.%n(%p)"));
117 }
118 addToWorklist(results.lookupMethod(method));
119 }
120
121 /**
122 * Performs the fixed-point analysis that finds all methods transitively reachable from the
123 * {@link #addMethod root methods}.
124 */
125 public void finish() {
258 * referenced by the bytecodes to be loaded and initialized. Since we do not run
259 * the code before static analysis, the classes would otherwise be not loaded
260 * yet and the bytecode parser would only create a graph.
261 */
262 Plugins plugins = new Plugins(new InvocationPlugins());
263 GraphBuilderConfiguration graphBuilderConfig = GraphBuilderConfiguration.getDefault(plugins).withEagerResolving(true).withUnresolvedIsError(true);
264 /*
265 * For simplicity, we ignore all exception handling during the static analysis.
266 * This is a constraint of this example code, a real static analysis needs to
267 * handle the Graal nodes for throwing and handling exceptions.
268 */
269 graphBuilderConfig = graphBuilderConfig.withBytecodeExceptionMode(BytecodeExceptionMode.OmitAll);
270 /*
271 * We do not want Graal to perform any speculative optimistic optimizations,
272 * i.e., we do not want to use profiling information. Since we do not run the
273 * code before static analysis, the profiling information is empty and therefore
274 * wrong.
275 */
276 OptimisticOptimizations optimisticOpts = OptimisticOptimizations.NONE;
277
278 GraphBuilderPhase.Instance graphBuilder = new GraphBuilderPhase.Instance(providers, graphBuilderConfig, optimisticOpts, null);
279 graphBuilder.apply(graph);
280 } catch (Throwable ex) {
281 debug.handle(ex);
282 }
283
284 /*
285 * Build the type flow graph from the Graal graph, i.e., process all nodes that are
286 * deal with objects.
287 */
288
289 TypeFlowBuilder typeFlowBuilder = new TypeFlowBuilder(graph);
290 typeFlowBuilder.apply();
291 }
292 }
293 }
294
295 /**
296 * The active element during static analysis: types are added until a fixed point is reached.
297 * When a new type is added, it is propagated to all usages by putting this element on the
298 * {@link StaticAnalysis#addToWorklist worklist}.
299 */
300 public class TypeFlow extends WorklistEntry {
301 private final Set<ResolvedJavaType> types;
302 private final Set<TypeFlow> uses;
303
304 protected TypeFlow() {
305 types = new HashSet<>();
306 uses = new HashSet<>();
307 }
308
309 /**
310 * Returns the types of this element.
311 */
312 public Set<ResolvedJavaType> getTypes() {
313 return types;
314 }
315
316 /**
317 * Adds new types to this element. If that changes the state of this element, it is added to
318 * the {@link StaticAnalysis#addToWorklist worklist} in order to propagate the added types
319 * to all usages.
320 */
321 protected void addTypes(Set<ResolvedJavaType> newTypes) {
322 if (types.addAll(newTypes)) {
323 addToWorklist(this);
324 }
325 }
326
327 /**
328 * Adds a new use to this element. All types of this element are propagated to the new
329 * usage.
330 */
331 protected void addUse(TypeFlow use) {
336
337 /**
338 * Processing of the worklist element: propagate the types to all usages. That in turn can
339 * add the usages to the worklist (if the types of the usage are changed).
340 */
341 @Override
342 protected void process() {
343 for (TypeFlow use : uses) {
344 use.addTypes(types);
345 }
346 }
347 }
348
349 /**
350 * The active element for method invocations. For {@link InvokeKind#Virtual virtual} and
351 * {@link InvokeKind#Interface interface} calls, the {@link TypeFlow#getTypes() types} of this
352 * node are the receiver types. When a new receiver type is added, a new callee might be added.
353 * Adding a new callee means linking the type flow of the actual parameters with the formal
354 * parameters of the callee, and linking the return value of the callee with the return value
355 * state of the invocation.
356 * <p>
357 * Statically bindable methods calls ({@link InvokeKind#Static static} and
358 * {@link InvokeKind#Special special} calls) have only one callee, but use the same code for
359 * simplicity.
360 */
361 class InvokeTypeFlow extends TypeFlow {
362 private final MethodCallTargetNode callTarget;
363 private final TypeFlow[] actualParameters;
364 private final TypeFlow actualReturn;
365 private final Set<ResolvedJavaMethod> callees;
366
367 protected InvokeTypeFlow(MethodCallTargetNode callTarget, TypeFlow[] actualParameterFlows, TypeFlow actualReturnFlow) {
368 this.callTarget = callTarget;
369 this.actualParameters = actualParameterFlows;
370 this.actualReturn = actualReturnFlow;
371 this.callees = new HashSet<>();
372 }
373
374 private void linkCallee(ResolvedJavaMethod callee) {
375 if (callees.add(callee)) {
376 /* We have added a new callee. */
|