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.core.test.tutorial;
24
25 import static org.graalvm.compiler.core.test.GraalCompilerTest.getInitialOptions;
26
27 import java.util.ArrayDeque;
28 import java.util.Collections;
29 import java.util.Deque;
30 import java.util.HashMap;
31 import java.util.HashSet;
32 import java.util.Map;
33 import java.util.Set;
34
35 import org.graalvm.compiler.debug.DebugHandlersFactory;
36 import org.graalvm.compiler.debug.DebugContext;
37 import org.graalvm.compiler.debug.GraalError;
38 import org.graalvm.compiler.graph.Node;
39 import org.graalvm.compiler.graph.NodeMap;
40 import org.graalvm.compiler.java.GraphBuilderPhase;
41 import org.graalvm.compiler.nodes.CallTargetNode.InvokeKind;
42 import org.graalvm.compiler.nodes.ConstantNode;
43 import org.graalvm.compiler.nodes.FixedNode;
44 import org.graalvm.compiler.nodes.Invoke;
45 import org.graalvm.compiler.nodes.ParameterNode;
46 import org.graalvm.compiler.nodes.ReturnNode;
47 import org.graalvm.compiler.nodes.StructuredGraph;
48 import org.graalvm.compiler.nodes.ValueNode;
49 import org.graalvm.compiler.nodes.ValuePhiNode;
50 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration;
51 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.BytecodeExceptionMode;
52 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.Plugins;
53 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins;
54 import org.graalvm.compiler.nodes.java.LoadFieldNode;
55 import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
56 import org.graalvm.compiler.nodes.java.NewArrayNode;
57 import org.graalvm.compiler.nodes.java.NewInstanceNode;
58 import org.graalvm.compiler.nodes.java.StoreFieldNode;
59 import org.graalvm.compiler.nodes.spi.StampProvider;
60 import org.graalvm.compiler.nodes.util.GraphUtil;
61 import org.graalvm.compiler.options.OptionValues;
62 import org.graalvm.compiler.phases.OptimisticOptimizations;
63 import org.graalvm.compiler.phases.graph.StatelessPostOrderNodeIterator;
64
65 import jdk.vm.ci.meta.JavaConstant;
66 import jdk.vm.ci.meta.JavaKind;
67 import jdk.vm.ci.meta.MetaAccessProvider;
68 import jdk.vm.ci.meta.ResolvedJavaField;
69 import jdk.vm.ci.meta.ResolvedJavaMethod;
70 import jdk.vm.ci.meta.ResolvedJavaType;
71
72 /**
73 * A simple context-insensitive static analysis based on the Graal API. It is intended for
74 * educational purposes, not for use in production. Only a limited set of Java functionality is
75 * supported to keep the code minimal.
76 * <p>
77 * The analysis builds a directed graph of {@link TypeFlow type flows}. If a type is added to type
78 * flow, it is propagated to all {@link TypeFlow#uses uses} of the type flow. Types are propagated
79 * using a {@link #worklist} of changed type flows until a fixpoint is reached, i.e., until no more
80 * types need to be added to any type state.
81 * <p>
82 * The type flows are constructed from a high-level Graal graph by the {@link TypeFlowBuilder}. All
83 * nodes that operate on {@link JavaKind#Object object} values are converted to the appropriate type
84 * flows. The analysis is context insensitive: every Java field has {@link Results#lookupField one
85 * list} of types assigned to the field; every Java method has {@link Results#lookupMethod one
86 * state} for each {@link MethodState#formalParameters parameter} as well as the
87 * {@link MethodState#formalReturn return value}.
88 */
89 public class StaticAnalysis {
90 /** Access to type, method, and fields using the Graal API. */
91 private final MetaAccessProvider metaAccess;
92 /** Access to platform dependent stamps. */
93 private final StampProvider stampProvider;
94 /** The results of the static analysis. */
95 private final Results results;
96 /** Worklist for fixpoint iteration. */
97 private final Deque<WorklistEntry> worklist;
98
99 public StaticAnalysis(MetaAccessProvider metaAccess, StampProvider stampProvider) {
100 this.metaAccess = metaAccess;
101 this.stampProvider = stampProvider;
102 this.results = new Results();
103 this.worklist = new ArrayDeque<>();
104 }
105
106 /**
107 * Adds a root method to the static analysis. The method must be static and must not have any
108 * parameters, because the possible types of the parameters would not be known.
109 */
110 public void addMethod(ResolvedJavaMethod method) {
111 if (!method.isStatic() || method.getSignature().getParameterCount(false) > 0) {
112 error("Entry point method is not static or has parameters: " + method.format("%H.%n(%p)"));
113 }
114 addToWorklist(results.lookupMethod(method));
115 }
116
117 /**
118 * Performs the fixed-point analysis that finds all methods transitively reachable from the
119 * {@link #addMethod root methods}.
120 */
121 public void finish() {
122 while (!worklist.isEmpty()) {
123 worklist.removeFirst().process();
124 }
125 }
126
127 /**
128 * Returns the static analysis results computed by {@link StaticAnalysis#finish}.
129 */
130 public Results getResults() {
131 return results;
132 }
133
134 protected void addToWorklist(WorklistEntry task) {
135 worklist.addLast(task);
136 }
137
138 protected static RuntimeException error(String msg) {
139 throw GraalError.shouldNotReachHere(msg);
140 }
141
142 /**
143 * Base class for all work items that can be {@link #addToWorklist added to the worklist}.
144 */
145 abstract class WorklistEntry {
146 protected abstract void process();
147 }
148
149 /**
150 * The results computed by the static analysis.
151 */
152 public class Results {
153 private final TypeFlow allInstantiatedTypes;
154 private final Map<ResolvedJavaField, TypeFlow> fields;
155 private final Map<ResolvedJavaMethod, MethodState> methods;
156
157 protected Results() {
158 allInstantiatedTypes = new TypeFlow();
159 fields = new HashMap<>();
160 methods = new HashMap<>();
161 }
162
163 /**
164 * All {@link TypeFlow#getTypes() types} that are found to be instantiated, i.e., all types
165 * allocated by the reachable instance and array allocation bytecodes.
166 */
167 public TypeFlow getAllInstantiatedTypes() {
168 return allInstantiatedTypes;
169 }
170
171 /**
172 * All {@link TypeFlow#getTypes() types} that the given field can have, i.e., all types
173 * assigned by the reachable field store bytecodes.
174 */
175 public TypeFlow lookupField(ResolvedJavaField field) {
176 TypeFlow result = fields.get(field);
177 if (result == null) {
178 result = new TypeFlow();
179 fields.put(field, result);
180 }
181 return result;
182 }
183
184 /**
185 * All {@link TypeFlow#getTypes() types} that {@link MethodState#formalParameters
186 * parameters} and {@link MethodState#formalReturn return value} of the given method can
187 * have.
188 */
189 public MethodState lookupMethod(ResolvedJavaMethod method) {
190 MethodState result = methods.get(method);
191 if (result == null) {
192 result = new MethodState(method);
193 methods.put(method, result);
194 }
195 return result;
196 }
197 }
198
199 /**
200 * The {@link TypeFlow#getTypes() types} of the parameters and return value of a method. Also
201 * serves as the worklist element to parse the bytecodes of the method.
202 */
203 public class MethodState extends WorklistEntry {
204 private final ResolvedJavaMethod method;
205 private final TypeFlow[] formalParameters;
206 private final TypeFlow formalReturn;
207 private boolean processed;
208
209 protected MethodState(ResolvedJavaMethod method) {
210 this.method = method;
211
212 formalParameters = new TypeFlow[method.getSignature().getParameterCount(!method.isStatic())];
213 for (int i = 0; i < formalParameters.length; i++) {
214 formalParameters[i] = new TypeFlow();
215 }
216 formalReturn = new TypeFlow();
217 }
218
219 /**
220 * All {@link TypeFlow#getTypes() types} that the parameters of this method can have.
221 */
222 public TypeFlow[] getFormalParameters() {
223 return formalParameters;
224 }
225
226 /**
227 * All {@link TypeFlow#getTypes() types} that the return value of this method can have.
228 */
229 public TypeFlow getFormalReturn() {
230 return formalReturn;
231 }
232
233 @Override
234 @SuppressWarnings("try")
235 protected void process() {
236 if (!processed) {
237 /* We want to process a method only once. */
238 processed = true;
239
240 /*
241 * Build the Graal graph for the method using the bytecode parser provided by Graal.
242 */
243
244 OptionValues options = getInitialOptions();
245 DebugContext debug = DebugContext.create(options, DebugHandlersFactory.LOADER);
246 StructuredGraph graph = new StructuredGraph.Builder(options, debug).method(method).build();
247 /*
248 * Support for graph dumping, IGV uses this information to show the method name of a
249 * graph.
250 */
251 try (DebugContext.Scope scope = debug.scope("graph building", graph)) {
252 /*
253 * We want all types to be resolved by the graph builder, i.e., we want classes
254 * referenced by the bytecodes to be loaded and initialized. Since we do not run
255 * the code before static analysis, the classes would otherwise be not loaded
256 * yet and the bytecode parser would only create a graph.
257 */
258 Plugins plugins = new Plugins(new InvocationPlugins());
259 GraphBuilderConfiguration graphBuilderConfig = GraphBuilderConfiguration.getDefault(plugins).withEagerResolving(true);
260 /*
261 * For simplicity, we ignore all exception handling during the static analysis.
262 * This is a constraint of this example code, a real static analysis needs to
263 * handle the Graal nodes for throwing and handling exceptions.
264 */
265 graphBuilderConfig = graphBuilderConfig.withBytecodeExceptionMode(BytecodeExceptionMode.OmitAll);
266 /*
267 * We do not want Graal to perform any speculative optimistic optimizations,
268 * i.e., we do not want to use profiling information. Since we do not run the
269 * code before static analysis, the profiling information is empty and therefore
270 * wrong.
271 */
272 OptimisticOptimizations optimisticOpts = OptimisticOptimizations.NONE;
273
274 GraphBuilderPhase.Instance graphBuilder = new GraphBuilderPhase.Instance(metaAccess, stampProvider, null, null, graphBuilderConfig, optimisticOpts, null);
275 graphBuilder.apply(graph);
276 } catch (Throwable ex) {
277 debug.handle(ex);
278 }
279
280 /*
281 * Build the type flow graph from the Graal graph, i.e., process all nodes that are
282 * deal with objects.
283 */
284
285 TypeFlowBuilder typeFlowBuilder = new TypeFlowBuilder(graph);
286 typeFlowBuilder.apply();
287 }
288 }
289 }
290
291 /**
292 * The active element during static analysis: types are added until a fixed point is reached.
293 * When a new type is added, it is propagated to all usages by putting this element on the
294 * {@link StaticAnalysis#addToWorklist worklist}.
295 */
296 public class TypeFlow extends WorklistEntry {
297 private final Set<ResolvedJavaType> types;
298 private final Set<TypeFlow> uses;
299
300 protected TypeFlow() {
301 types = new HashSet<>();
302 uses = new HashSet<>();
303 }
304
305 /** Returns the types of this element. */
306 public Set<ResolvedJavaType> getTypes() {
307 return types;
308 }
309
310 /**
311 * Adds new types to this element. If that changes the state of this element, it is added to
312 * the {@link StaticAnalysis#addToWorklist worklist} in order to propagate the added types
313 * to all usages.
314 */
315 protected void addTypes(Set<ResolvedJavaType> newTypes) {
316 if (types.addAll(newTypes)) {
317 addToWorklist(this);
318 }
319 }
320
321 /**
322 * Adds a new use to this element. All types of this element are propagated to the new
323 * usage.
324 */
325 protected void addUse(TypeFlow use) {
326 if (uses.add(use)) {
327 use.addTypes(types);
328 }
329 }
330
331 /**
332 * Processing of the worklist element: propagate the types to all usages. That in turn can
333 * add the usages to the worklist (if the types of the usage are changed).
334 */
335 @Override
336 protected void process() {
337 for (TypeFlow use : uses) {
338 use.addTypes(types);
339 }
340 }
341 }
342
343 /**
344 * The active element for method invocations. For {@link InvokeKind#Virtual virtual} and
345 * {@link InvokeKind#Interface interface} calls, the {@link TypeFlow#getTypes() types} of this
346 * node are the receiver types. When a new receiver type is added, a new callee might be added.
347 * Adding a new callee means linking the type flow of the actual parameters with the formal
348 * parameters of the callee, and linking the return value of the callee with the return value
349 * state of the invocation.
350 *
351 * Statically bindable methods calls ({@link InvokeKind#Static static} and
352 * {@link InvokeKind#Special special} calls) have only one callee, but use the same code for
353 * simplicity.
354 */
355 class InvokeTypeFlow extends TypeFlow {
356 private final MethodCallTargetNode callTarget;
357 private final TypeFlow[] actualParameters;
358 private final TypeFlow actualReturn;
359 private final Set<ResolvedJavaMethod> callees;
360
361 protected InvokeTypeFlow(MethodCallTargetNode callTarget, TypeFlow[] actualParameterFlows, TypeFlow actualReturnFlow) {
362 this.callTarget = callTarget;
363 this.actualParameters = actualParameterFlows;
364 this.actualReturn = actualReturnFlow;
365 this.callees = new HashSet<>();
366 }
367
368 private void linkCallee(ResolvedJavaMethod callee) {
369 if (callees.add(callee)) {
370 /* We have added a new callee. */
371
372 /*
373 * Connect the actual parameters of the invocation with the formal parameters of the
374 * callee.
375 */
376 MethodState calleeState = results.lookupMethod(callee);
377 for (int i = 0; i < actualParameters.length; i++) {
378 if (actualParameters[i] != null) {
379 actualParameters[i].addUse(calleeState.formalParameters[i]);
380 }
381 }
382
383 /*
384 * Connect the formal return value of the callee with the actual return value of the
385 * invocation.
386 */
387 if (actualReturn != null) {
388 calleeState.formalReturn.addUse(actualReturn);
389 }
390 addToWorklist(calleeState);
391 }
392 }
393
394 @Override
395 protected void process() {
396 if (callTarget.invokeKind().isDirect()) {
397 /* Static and special calls: link the statically known callee method. */
398 linkCallee(callTarget.targetMethod());
399 } else {
400 /* Virtual and interface call: Iterate all receiver types. */
401 for (ResolvedJavaType type : getTypes()) {
402 /*
403 * Resolve the method call for one exact receiver type. The method linking
404 * semantics of Java are complicated, but fortunatley we can use the linker of
405 * the hosting Java VM. The Graal API exposes this functionality.
406 */
407 ResolvedJavaMethod method = type.resolveConcreteMethod(callTarget.targetMethod(), callTarget.invoke().getContextType());
408
409 /*
410 * Since the static analysis is conservative, the list of receiver types can
411 * contain types that actually do not provide the method to be called. Ignore
412 * these.
413 */
414 if (method != null && !method.isAbstract()) {
415 linkCallee(method);
416 }
417 }
418 }
419 super.process();
420 }
421 }
422
423 /**
424 * Converts the Graal nodes of a method to a type flow graph. The main part of the algorithm is
425 * a reverse-postorder iteration of the Graal nodes, which is provided by the base class
426 * {@link StatelessPostOrderNodeIterator}.
427 */
428 class TypeFlowBuilder extends StatelessPostOrderNodeIterator {
429 private final StructuredGraph graph;
430 private final MethodState methodState;
431 /**
432 * Mapping from Graal nodes to type flows. This uses an efficient Graal-provided
433 * {@link NodeMap collection class}.
434 */
435 private final NodeMap<TypeFlow> typeFlows;
436
437 protected TypeFlowBuilder(StructuredGraph graph) {
438 super(graph.start());
439
440 this.graph = graph;
441 this.methodState = results.lookupMethod(graph.method());
442 this.typeFlows = new NodeMap<>(graph);
443 }
444
445 /**
446 * Register the type flow node for a Graal node.
447 */
448 private void registerFlow(ValueNode node, TypeFlow flow) {
449 /*
450 * We ignore intermediate nodes used by Graal that, e.g., add more type information or
451 * encapsulate values flowing out of loops.
452 */
453 ValueNode unproxiedNode = GraphUtil.unproxify(node);
454
455 assert typeFlows.get(unproxiedNode) == null : "overwriting existing value";
456 typeFlows.set(unproxiedNode, flow);
457 }
458
459 /**
460 * Lookup the type flow node for a Graal node.
461 */
462 private TypeFlow lookupFlow(ValueNode node) {
463 ValueNode unproxiedNode = GraphUtil.unproxify(node);
464 TypeFlow result = typeFlows.get(unproxiedNode);
465 if (result == null) {
466 /*
467 * This is only the prototype of a static analysis, the handling of many Graal nodes
468 * (such as array accesses) is not implemented.
469 */
470 throw error("Node is not supported yet by static analysis: " + node.getClass().getName());
471 }
472 return result;
473 }
474
475 private boolean isObject(ValueNode node) {
476 return node.getStackKind() == JavaKind.Object;
477 }
478
479 @Override
480 public void apply() {
481 /*
482 * Before the reverse-postorder iteration of fixed nodes, we handle some classes of
483 * floating nodes.
484 */
485 for (Node n : graph.getNodes()) {
486 if (n instanceof ParameterNode) {
487 /*
488 * Incoming method parameter already have a type flow created by the
489 * MethodState.
490 */
491 ParameterNode node = (ParameterNode) n;
492 if (isObject(node)) {
493 registerFlow(node, methodState.formalParameters[(node.index())]);
494 }
495 } else if (n instanceof ValuePhiNode) {
496 /*
497 * Phi functions for loops are cyclic. We create the type flow here (before
498 * processing any loop nodes), but link the phi values only later (after
499 * processing of all loop nodes.
500 */
501 ValuePhiNode node = (ValuePhiNode) n;
502 if (isObject(node)) {
503 registerFlow(node, new TypeFlow());
504 }
505 } else if (n instanceof ConstantNode) {
506 /* Constants have a known type. */
507 ConstantNode node = (ConstantNode) n;
508 JavaConstant constant = node.asJavaConstant();
509 if (constant.isNull()) {
510 registerFlow(node, new TypeFlow());
511 }
512 }
513 }
514
515 super.apply();
516
517 for (Node n : graph.getNodes()) {
518 if (n instanceof ValuePhiNode) {
519 /*
520 * Post-processing of phi functions. Now the type flow for all input values has
521 * been created, so we can link the type flows together.
522 */
523 ValuePhiNode node = (ValuePhiNode) n;
524 if (isObject(node)) {
525 TypeFlow phiFlow = lookupFlow(node);
526 for (ValueNode value : node.values()) {
527 lookupFlow(value).addUse(phiFlow);
528 }
529 }
530 }
531 }
532 }
533
534 private void allocation(ValueNode node, ResolvedJavaType type) {
535 /*
536 * The type flow of allocation nodes is one exact type. This is the source of the
537 * fixpoint iteration, the types are propagated downwards from these sources.
538 */
539 TypeFlow flow = new TypeFlow();
540 flow.addTypes(Collections.singleton(type));
541 registerFlow(node, flow);
542 flow.addUse(results.getAllInstantiatedTypes());
543 }
544
545 @Override
546 protected void node(FixedNode n) {
547 if (n instanceof NewInstanceNode) {
548 NewInstanceNode node = (NewInstanceNode) n;
549 allocation(node, node.instanceClass());
550 } else if (n instanceof NewArrayNode) {
551 NewArrayNode node = (NewArrayNode) n;
552 allocation(node, node.elementType().getArrayClass());
553
554 } else if (n instanceof LoadFieldNode) {
555 /*
556 * The type flow of a field load is the type flow of the field itself. It
557 * accumulates all types ever stored to the field.
558 */
559 LoadFieldNode node = (LoadFieldNode) n;
560 if (isObject(node)) {
561 registerFlow(node, results.lookupField(node.field()));
562 }
563 } else if (n instanceof StoreFieldNode) {
564 /*
565 * Connect the type flow of the stored value with the type flow of the field.
566 */
567 StoreFieldNode node = (StoreFieldNode) n;
568 if (isObject(node.value())) {
569 TypeFlow fieldFlow = results.lookupField(node.field());
570 lookupFlow(node.value()).addUse(fieldFlow);
571 }
572
573 } else if (n instanceof ReturnNode) {
574 /*
575 * Connect the type flow of the returned value with the formal return type flow of
576 * the MethodState.
577 */
578 ReturnNode node = (ReturnNode) n;
579 if (node.result() != null && isObject(node.result())) {
580 lookupFlow(node.result()).addUse(methodState.formalReturn);
581 }
582
583 } else if (n instanceof Invoke) {
584 /*
585 * Create the InvokeTypeFlow, which performs all the linking of actual and formal
586 * parameter values with all identified callees.
587 */
588 Invoke invoke = (Invoke) n;
589 MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget();
590
591 TypeFlow[] actualParameters = new TypeFlow[callTarget.arguments().size()];
592 for (int i = 0; i < actualParameters.length; i++) {
593 ValueNode actualParam = callTarget.arguments().get(i);
594 if (isObject(actualParam)) {
595 actualParameters[i] = lookupFlow(actualParam);
596 }
597 }
598 TypeFlow actualReturn = null;
599 if (isObject(invoke.asNode())) {
600 actualReturn = new TypeFlow();
601 registerFlow(invoke.asNode(), actualReturn);
602 }
603
604 InvokeTypeFlow invokeFlow = new InvokeTypeFlow(callTarget, actualParameters, actualReturn);
605
606 if (callTarget.invokeKind().isIndirect()) {
607 /*
608 * For virtual and interface calls, new receiver types can lead to new callees.
609 * Connect the type flow of the receiver with the invocation flow.
610 */
611 lookupFlow(callTarget.arguments().get(0)).addUse(invokeFlow);
612 }
613 /*
614 * Ensure the invocation is on the worklist at least once, even if it is a static
615 * call with not parameters that does not involve any type flows.
616 */
617 addToWorklist(invokeFlow);
618 }
619 }
620 }
621 }