1 /*
2 * Copyright (c) 2015, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.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() {
124 while (!worklist.isEmpty()) {
125 worklist.removeFirst().process();
126 }
127 }
128
129 /**
130 * Returns the static analysis results computed by {@link StaticAnalysis#finish}.
131 */
132 public Results getResults() {
133 return results;
134 }
135
136 protected void addToWorklist(WorklistEntry task) {
137 worklist.addLast(task);
138 }
139
140 protected static RuntimeException error(String msg) {
141 throw GraalError.shouldNotReachHere(msg);
142 }
143
144 /**
145 * Base class for all work items that can be {@link #addToWorklist added to the worklist}.
146 */
147 abstract class WorklistEntry {
148 protected abstract void process();
149 }
150
151 /**
152 * The results computed by the static analysis.
153 */
154 public class Results {
155 private final TypeFlow allInstantiatedTypes;
156 private final Map<ResolvedJavaField, TypeFlow> fields;
157 private final Map<ResolvedJavaMethod, MethodState> methods;
158
159 protected Results() {
160 allInstantiatedTypes = new TypeFlow();
161 fields = new HashMap<>();
162 methods = new HashMap<>();
163 }
164
165 /**
166 * All {@link TypeFlow#getTypes() types} that are found to be instantiated, i.e., all types
167 * allocated by the reachable instance and array allocation bytecodes.
168 */
169 public TypeFlow getAllInstantiatedTypes() {
170 return allInstantiatedTypes;
171 }
172
173 /**
174 * All {@link TypeFlow#getTypes() types} that the given field can have, i.e., all types
175 * assigned by the reachable field store bytecodes.
176 */
177 public TypeFlow lookupField(ResolvedJavaField field) {
178 TypeFlow result = fields.get(field);
179 if (result == null) {
180 result = new TypeFlow();
181 fields.put(field, result);
182 }
183 return result;
184 }
185
186 /**
187 * All {@link TypeFlow#getTypes() types} that {@link MethodState#formalParameters
188 * parameters} and {@link MethodState#formalReturn return value} of the given method can
189 * have.
190 */
191 public MethodState lookupMethod(ResolvedJavaMethod method) {
192 MethodState result = methods.get(method);
193 if (result == null) {
194 result = new MethodState(method);
195 methods.put(method, result);
196 }
197 return result;
198 }
199 }
200
201 /**
202 * The {@link TypeFlow#getTypes() types} of the parameters and return value of a method. Also
203 * serves as the worklist element to parse the bytecodes of the method.
204 */
205 public class MethodState extends WorklistEntry {
206 private final ResolvedJavaMethod method;
207 private final TypeFlow[] formalParameters;
208 private final TypeFlow formalReturn;
209 private boolean processed;
210
211 protected MethodState(ResolvedJavaMethod method) {
212 this.method = method;
213
214 formalParameters = new TypeFlow[method.getSignature().getParameterCount(!method.isStatic())];
215 for (int i = 0; i < formalParameters.length; i++) {
216 formalParameters[i] = new TypeFlow();
217 }
218 formalReturn = new TypeFlow();
219 }
220
221 /**
222 * All {@link TypeFlow#getTypes() types} that the parameters of this method can have.
223 */
224 public TypeFlow[] getFormalParameters() {
225 return formalParameters;
226 }
227
228 /**
229 * All {@link TypeFlow#getTypes() types} that the return value of this method can have.
230 */
231 public TypeFlow getFormalReturn() {
232 return formalReturn;
233 }
234
235 @Override
236 @SuppressWarnings("try")
237 protected void process() {
238 if (!processed) {
239 /* We want to process a method only once. */
240 processed = true;
241
242 /*
243 * Build the Graal graph for the method using the bytecode parser provided by Graal.
244 */
245
246 OptionValues options = getInitialOptions();
247 DebugContext debug = DebugContext.create(options, DebugHandlersFactory.LOADER);
248 StructuredGraph graph = new StructuredGraph.Builder(options, debug).method(method).build();
249 /*
250 * Support for graph dumping, IGV uses this information to show the method name of a
251 * graph.
252 */
253 try (DebugContext.Scope scope = debug.scope("graph building", graph)) {
254 /*
255 * We want all types to be resolved by the graph builder, i.e., we want classes
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) {
328 if (uses.add(use)) {
329 use.addTypes(types);
330 }
331 }
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. */
373
374 /*
375 * Connect the actual parameters of the invocation with the formal parameters of the
376 * callee.
377 */
378 MethodState calleeState = results.lookupMethod(callee);
379 for (int i = 0; i < actualParameters.length; i++) {
380 if (actualParameters[i] != null) {
381 actualParameters[i].addUse(calleeState.formalParameters[i]);
382 }
383 }
384
385 /*
386 * Connect the formal return value of the callee with the actual return value of the
387 * invocation.
388 */
389 if (actualReturn != null) {
390 calleeState.formalReturn.addUse(actualReturn);
391 }
392 addToWorklist(calleeState);
393 }
394 }
395
396 @Override
397 protected void process() {
398 if (callTarget.invokeKind().isDirect()) {
399 /* Static and special calls: link the statically known callee method. */
400 linkCallee(callTarget.targetMethod());
401 } else {
402 /* Virtual and interface call: Iterate all receiver types. */
403 for (ResolvedJavaType type : getTypes()) {
404 /*
405 * Resolve the method call for one exact receiver type. The method linking
406 * semantics of Java are complicated, but fortunatley we can use the linker of
407 * the hosting Java VM. The Graal API exposes this functionality.
408 */
409 ResolvedJavaMethod method = type.resolveConcreteMethod(callTarget.targetMethod(), callTarget.invoke().getContextType());
410
411 /*
412 * Since the static analysis is conservative, the list of receiver types can
413 * contain types that actually do not provide the method to be called. Ignore
414 * these.
415 */
416 if (method != null && !method.isAbstract()) {
417 linkCallee(method);
418 }
419 }
420 }
421 super.process();
422 }
423 }
424
425 /**
426 * Converts the Graal nodes of a method to a type flow graph. The main part of the algorithm is
427 * a reverse-postorder iteration of the Graal nodes, which is provided by the base class
428 * {@link StatelessPostOrderNodeIterator}.
429 */
430 class TypeFlowBuilder extends StatelessPostOrderNodeIterator {
431 private final StructuredGraph graph;
432 private final MethodState methodState;
433 /**
434 * Mapping from Graal nodes to type flows. This uses an efficient Graal-provided
435 * {@link NodeMap collection class}.
436 */
437 private final NodeMap<TypeFlow> typeFlows;
438
439 protected TypeFlowBuilder(StructuredGraph graph) {
440 super(graph.start());
441
442 this.graph = graph;
443 this.methodState = results.lookupMethod(graph.method());
444 this.typeFlows = new NodeMap<>(graph);
445 }
446
447 /**
448 * Register the type flow node for a Graal node.
449 */
450 private void registerFlow(ValueNode node, TypeFlow flow) {
451 /*
452 * We ignore intermediate nodes used by Graal that, e.g., add more type information or
453 * encapsulate values flowing out of loops.
454 */
455 ValueNode unproxiedNode = GraphUtil.unproxify(node);
456
457 assert typeFlows.get(unproxiedNode) == null : "overwriting existing value";
458 typeFlows.set(unproxiedNode, flow);
459 }
460
461 /**
462 * Lookup the type flow node for a Graal node.
463 */
464 private TypeFlow lookupFlow(ValueNode node) {
465 ValueNode unproxiedNode = GraphUtil.unproxify(node);
466 TypeFlow result = typeFlows.get(unproxiedNode);
467 if (result == null) {
468 /*
469 * This is only the prototype of a static analysis, the handling of many Graal nodes
470 * (such as array accesses) is not implemented.
471 */
472 throw error("Node is not supported yet by static analysis: " + node.getClass().getName());
473 }
474 return result;
475 }
476
477 private boolean isObject(ValueNode node) {
478 return node.getStackKind() == JavaKind.Object;
479 }
480
481 @Override
482 public void apply() {
483 /*
484 * Before the reverse-postorder iteration of fixed nodes, we handle some classes of
485 * floating nodes.
486 */
487 for (Node n : graph.getNodes()) {
488 if (n instanceof ParameterNode) {
489 /*
490 * Incoming method parameter already have a type flow created by the
491 * MethodState.
492 */
493 ParameterNode node = (ParameterNode) n;
494 if (isObject(node)) {
495 registerFlow(node, methodState.formalParameters[(node.index())]);
496 }
497 } else if (n instanceof ValuePhiNode) {
498 /*
499 * Phi functions for loops are cyclic. We create the type flow here (before
500 * processing any loop nodes), but link the phi values only later (after
501 * processing of all loop nodes.
502 */
503 ValuePhiNode node = (ValuePhiNode) n;
504 if (isObject(node)) {
505 registerFlow(node, new TypeFlow());
506 }
507 } else if (n instanceof ConstantNode) {
508 /* Constants have a known type. */
509 ConstantNode node = (ConstantNode) n;
510 JavaConstant constant = node.asJavaConstant();
511 if (constant.isNull()) {
512 registerFlow(node, new TypeFlow());
513 }
514 }
515 }
516
517 super.apply();
518
519 for (Node n : graph.getNodes()) {
520 if (n instanceof ValuePhiNode) {
521 /*
522 * Post-processing of phi functions. Now the type flow for all input values has
523 * been created, so we can link the type flows together.
524 */
525 ValuePhiNode node = (ValuePhiNode) n;
526 if (isObject(node)) {
527 TypeFlow phiFlow = lookupFlow(node);
528 for (ValueNode value : node.values()) {
529 lookupFlow(value).addUse(phiFlow);
530 }
531 }
532 }
533 }
534 }
535
536 private void allocation(ValueNode node, ResolvedJavaType type) {
537 /*
538 * The type flow of allocation nodes is one exact type. This is the source of the
539 * fixpoint iteration, the types are propagated downwards from these sources.
540 */
541 TypeFlow flow = new TypeFlow();
542 flow.addTypes(Collections.singleton(type));
543 registerFlow(node, flow);
544 flow.addUse(results.getAllInstantiatedTypes());
545 }
546
547 @Override
548 protected void node(FixedNode n) {
549 if (n instanceof NewInstanceNode) {
550 NewInstanceNode node = (NewInstanceNode) n;
551 allocation(node, node.instanceClass());
552 } else if (n instanceof NewArrayNode) {
553 NewArrayNode node = (NewArrayNode) n;
554 allocation(node, node.elementType().getArrayClass());
555
556 } else if (n instanceof LoadFieldNode) {
557 /*
558 * The type flow of a field load is the type flow of the field itself. It
559 * accumulates all types ever stored to the field.
560 */
561 LoadFieldNode node = (LoadFieldNode) n;
562 if (isObject(node)) {
563 registerFlow(node, results.lookupField(node.field()));
564 }
565 } else if (n instanceof StoreFieldNode) {
566 /*
567 * Connect the type flow of the stored value with the type flow of the field.
568 */
569 StoreFieldNode node = (StoreFieldNode) n;
570 if (isObject(node.value())) {
571 TypeFlow fieldFlow = results.lookupField(node.field());
572 lookupFlow(node.value()).addUse(fieldFlow);
573 }
574
575 } else if (n instanceof ReturnNode) {
576 /*
577 * Connect the type flow of the returned value with the formal return type flow of
578 * the MethodState.
579 */
580 ReturnNode node = (ReturnNode) n;
581 if (node.result() != null && isObject(node.result())) {
582 lookupFlow(node.result()).addUse(methodState.formalReturn);
583 }
584
585 } else if (n instanceof Invoke) {
586 /*
587 * Create the InvokeTypeFlow, which performs all the linking of actual and formal
588 * parameter values with all identified callees.
589 */
590 Invoke invoke = (Invoke) n;
591 MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget();
592
593 TypeFlow[] actualParameters = new TypeFlow[callTarget.arguments().size()];
594 for (int i = 0; i < actualParameters.length; i++) {
595 ValueNode actualParam = callTarget.arguments().get(i);
596 if (isObject(actualParam)) {
597 actualParameters[i] = lookupFlow(actualParam);
598 }
599 }
600 TypeFlow actualReturn = null;
601 if (isObject(invoke.asNode())) {
602 actualReturn = new TypeFlow();
603 registerFlow(invoke.asNode(), actualReturn);
604 }
605
606 InvokeTypeFlow invokeFlow = new InvokeTypeFlow(callTarget, actualParameters, actualReturn);
607
608 if (callTarget.invokeKind().isIndirect()) {
609 /*
610 * For virtual and interface calls, new receiver types can lead to new callees.
611 * Connect the type flow of the receiver with the invocation flow.
612 */
613 lookupFlow(callTarget.arguments().get(0)).addUse(invokeFlow);
614 }
615 /*
616 * Ensure the invocation is on the worklist at least once, even if it is a static
617 * call with not parameters that does not involve any type flows.
618 */
619 addToWorklist(invokeFlow);
620 }
621 }
622 }
623 }