-
StaticAnalysis
-
metaAccess: MetaAccessProvider
-
stampProvider: StampProvider
-
results: Results
-
worklist: Deque<WorklistEntry>
-
StaticAnalysis(MetaAccessProvider, StampProvider): void
-
addMethod(ResolvedJavaMethod): void
-
finish(): void
-
getResults(): Results
-
addToWorklist(WorklistEntry): void
-
error(String): RuntimeException
-
WorklistEntry
-
Results
-
MethodState
-
TypeFlow
-
InvokeTypeFlow
-
TypeFlowBuilder
-
/*
* Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
package org.graalvm.compiler.core.test.tutorial;
import static org.graalvm.compiler.core.test.GraalCompilerTest.getInitialOptions;
import java.util.ArrayDeque;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import org.graalvm.compiler.debug.DebugHandlersFactory;
import org.graalvm.compiler.debug.DebugContext;
import org.graalvm.compiler.debug.GraalError;
import org.graalvm.compiler.graph.Node;
import org.graalvm.compiler.graph.NodeMap;
import org.graalvm.compiler.java.GraphBuilderPhase;
import org.graalvm.compiler.nodes.CallTargetNode.InvokeKind;
import org.graalvm.compiler.nodes.ConstantNode;
import org.graalvm.compiler.nodes.FixedNode;
import org.graalvm.compiler.nodes.Invoke;
import org.graalvm.compiler.nodes.ParameterNode;
import org.graalvm.compiler.nodes.ReturnNode;
import org.graalvm.compiler.nodes.StructuredGraph;
import org.graalvm.compiler.nodes.ValueNode;
import org.graalvm.compiler.nodes.ValuePhiNode;
import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration;
import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.BytecodeExceptionMode;
import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.Plugins;
import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins;
import org.graalvm.compiler.nodes.java.LoadFieldNode;
import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
import org.graalvm.compiler.nodes.java.NewArrayNode;
import org.graalvm.compiler.nodes.java.NewInstanceNode;
import org.graalvm.compiler.nodes.java.StoreFieldNode;
import org.graalvm.compiler.nodes.spi.StampProvider;
import org.graalvm.compiler.nodes.util.GraphUtil;
import org.graalvm.compiler.options.OptionValues;
import org.graalvm.compiler.phases.OptimisticOptimizations;
import org.graalvm.compiler.phases.graph.StatelessPostOrderNodeIterator;
import jdk.vm.ci.meta.JavaConstant;
import jdk.vm.ci.meta.JavaKind;
import jdk.vm.ci.meta.MetaAccessProvider;
import jdk.vm.ci.meta.ResolvedJavaField;
import jdk.vm.ci.meta.ResolvedJavaMethod;
import jdk.vm.ci.meta.ResolvedJavaType;
A simple context-insensitive static analysis based on the Graal API. It is intended for
educational purposes, not for use in production. Only a limited set of Java functionality is
supported to keep the code minimal.
The analysis builds a directed graph of type flows. If a type is added to type flow, it is propagated to all uses of the type flow. Types are propagated using a worklist of changed type flows until a fixpoint is reached, i.e., until no more types need to be added to any type state.
The type flows are constructed from a high-level Graal graph by the TypeFlowBuilder. All nodes that operate on object values are converted to the appropriate type flows. The analysis is context insensitive: every Java field has one
list of types assigned to the field; every Java method has one
state for each parameter as well as the return value.
/**
* A simple context-insensitive static analysis based on the Graal API. It is intended for
* educational purposes, not for use in production. Only a limited set of Java functionality is
* supported to keep the code minimal.
* <p>
* The analysis builds a directed graph of {@link TypeFlow type flows}. If a type is added to type
* flow, it is propagated to all {@link TypeFlow#uses uses} of the type flow. Types are propagated
* using a {@link #worklist} of changed type flows until a fixpoint is reached, i.e., until no more
* types need to be added to any type state.
* <p>
* The type flows are constructed from a high-level Graal graph by the {@link TypeFlowBuilder}. All
* nodes that operate on {@link JavaKind#Object object} values are converted to the appropriate type
* flows. The analysis is context insensitive: every Java field has {@link Results#lookupField one
* list} of types assigned to the field; every Java method has {@link Results#lookupMethod one
* state} for each {@link MethodState#formalParameters parameter} as well as the
* {@link MethodState#formalReturn return value}.
*/
public class StaticAnalysis {
Access to type, method, and fields using the Graal API. /** Access to type, method, and fields using the Graal API. */
private final MetaAccessProvider metaAccess;
Access to platform dependent stamps. /** Access to platform dependent stamps. */
private final StampProvider stampProvider;
The results of the static analysis. /** The results of the static analysis. */
private final Results results;
Worklist for fixpoint iteration. /** Worklist for fixpoint iteration. */
private final Deque<WorklistEntry> worklist;
public StaticAnalysis(MetaAccessProvider metaAccess, StampProvider stampProvider) {
this.metaAccess = metaAccess;
this.stampProvider = stampProvider;
this.results = new Results();
this.worklist = new ArrayDeque<>();
}
Adds a root method to the static analysis. The method must be static and must not have any
parameters, because the possible types of the parameters would not be known.
/**
* Adds a root method to the static analysis. The method must be static and must not have any
* parameters, because the possible types of the parameters would not be known.
*/
public void addMethod(ResolvedJavaMethod method) {
if (!method.isStatic() || method.getSignature().getParameterCount(false) > 0) {
error("Entry point method is not static or has parameters: " + method.format("%H.%n(%p)"));
}
addToWorklist(results.lookupMethod(method));
}
Performs the fixed-point analysis that finds all methods transitively reachable from the root methods. /**
* Performs the fixed-point analysis that finds all methods transitively reachable from the
* {@link #addMethod root methods}.
*/
public void finish() {
while (!worklist.isEmpty()) {
worklist.removeFirst().process();
}
}
Returns the static analysis results computed by finish. /**
* Returns the static analysis results computed by {@link StaticAnalysis#finish}.
*/
public Results getResults() {
return results;
}
protected void addToWorklist(WorklistEntry task) {
worklist.addLast(task);
}
protected static RuntimeException error(String msg) {
throw GraalError.shouldNotReachHere(msg);
}
Base class for all work items that can be added to the worklist. /**
* Base class for all work items that can be {@link #addToWorklist added to the worklist}.
*/
abstract class WorklistEntry {
protected abstract void process();
}
The results computed by the static analysis.
/**
* The results computed by the static analysis.
*/
public class Results {
private final TypeFlow allInstantiatedTypes;
private final Map<ResolvedJavaField, TypeFlow> fields;
private final Map<ResolvedJavaMethod, MethodState> methods;
protected Results() {
allInstantiatedTypes = new TypeFlow();
fields = new HashMap<>();
methods = new HashMap<>();
}
All types that are found to be instantiated, i.e., all types allocated by the reachable instance and array allocation bytecodes. /**
* All {@link TypeFlow#getTypes() types} that are found to be instantiated, i.e., all types
* allocated by the reachable instance and array allocation bytecodes.
*/
public TypeFlow getAllInstantiatedTypes() {
return allInstantiatedTypes;
}
All types that the given field can have, i.e., all types assigned by the reachable field store bytecodes. /**
* All {@link TypeFlow#getTypes() types} that the given field can have, i.e., all types
* assigned by the reachable field store bytecodes.
*/
public TypeFlow lookupField(ResolvedJavaField field) {
TypeFlow result = fields.get(field);
if (result == null) {
result = new TypeFlow();
fields.put(field, result);
}
return result;
}
/**
* All {@link TypeFlow#getTypes() types} that {@link MethodState#formalParameters
* parameters} and {@link MethodState#formalReturn return value} of the given method can
* have.
*/
public MethodState lookupMethod(ResolvedJavaMethod method) {
MethodState result = methods.get(method);
if (result == null) {
result = new MethodState(method);
methods.put(method, result);
}
return result;
}
}
The types of the parameters and return value of a method. Also serves as the worklist element to parse the bytecodes of the method. /**
* The {@link TypeFlow#getTypes() types} of the parameters and return value of a method. Also
* serves as the worklist element to parse the bytecodes of the method.
*/
public class MethodState extends WorklistEntry {
private final ResolvedJavaMethod method;
private final TypeFlow[] formalParameters;
private final TypeFlow formalReturn;
private boolean processed;
protected MethodState(ResolvedJavaMethod method) {
this.method = method;
formalParameters = new TypeFlow[method.getSignature().getParameterCount(!method.isStatic())];
for (int i = 0; i < formalParameters.length; i++) {
formalParameters[i] = new TypeFlow();
}
formalReturn = new TypeFlow();
}
All types that the parameters of this method can have. /**
* All {@link TypeFlow#getTypes() types} that the parameters of this method can have.
*/
public TypeFlow[] getFormalParameters() {
return formalParameters;
}
All types that the return value of this method can have. /**
* All {@link TypeFlow#getTypes() types} that the return value of this method can have.
*/
public TypeFlow getFormalReturn() {
return formalReturn;
}
@Override
@SuppressWarnings("try")
protected void process() {
if (!processed) {
/* We want to process a method only once. */
processed = true;
/*
* Build the Graal graph for the method using the bytecode parser provided by Graal.
*/
OptionValues options = getInitialOptions();
DebugContext debug = DebugContext.create(options, DebugHandlersFactory.LOADER);
StructuredGraph graph = new StructuredGraph.Builder(options, debug).method(method).build();
/*
* Support for graph dumping, IGV uses this information to show the method name of a
* graph.
*/
try (DebugContext.Scope scope = debug.scope("graph building", graph)) {
/*
* We want all types to be resolved by the graph builder, i.e., we want classes
* referenced by the bytecodes to be loaded and initialized. Since we do not run
* the code before static analysis, the classes would otherwise be not loaded
* yet and the bytecode parser would only create a graph.
*/
Plugins plugins = new Plugins(new InvocationPlugins());
GraphBuilderConfiguration graphBuilderConfig = GraphBuilderConfiguration.getDefault(plugins).withEagerResolving(true).withUnresolvedIsError(true);
/*
* For simplicity, we ignore all exception handling during the static analysis.
* This is a constraint of this example code, a real static analysis needs to
* handle the Graal nodes for throwing and handling exceptions.
*/
graphBuilderConfig = graphBuilderConfig.withBytecodeExceptionMode(BytecodeExceptionMode.OmitAll);
/*
* We do not want Graal to perform any speculative optimistic optimizations,
* i.e., we do not want to use profiling information. Since we do not run the
* code before static analysis, the profiling information is empty and therefore
* wrong.
*/
OptimisticOptimizations optimisticOpts = OptimisticOptimizations.NONE;
GraphBuilderPhase.Instance graphBuilder = new GraphBuilderPhase.Instance(metaAccess, stampProvider, null, null, graphBuilderConfig, optimisticOpts, null);
graphBuilder.apply(graph);
} catch (Throwable ex) {
debug.handle(ex);
}
/*
* Build the type flow graph from the Graal graph, i.e., process all nodes that are
* deal with objects.
*/
TypeFlowBuilder typeFlowBuilder = new TypeFlowBuilder(graph);
typeFlowBuilder.apply();
}
}
}
The active element during static analysis: types are added until a fixed point is reached. When a new type is added, it is propagated to all usages by putting this element on the worklist. /**
* The active element during static analysis: types are added until a fixed point is reached.
* When a new type is added, it is propagated to all usages by putting this element on the
* {@link StaticAnalysis#addToWorklist worklist}.
*/
public class TypeFlow extends WorklistEntry {
private final Set<ResolvedJavaType> types;
private final Set<TypeFlow> uses;
protected TypeFlow() {
types = new HashSet<>();
uses = new HashSet<>();
}
Returns the types of this element. /** Returns the types of this element. */
public Set<ResolvedJavaType> getTypes() {
return types;
}
Adds new types to this element. If that changes the state of this element, it is added to the worklist in order to propagate the added types to all usages. /**
* Adds new types to this element. If that changes the state of this element, it is added to
* the {@link StaticAnalysis#addToWorklist worklist} in order to propagate the added types
* to all usages.
*/
protected void addTypes(Set<ResolvedJavaType> newTypes) {
if (types.addAll(newTypes)) {
addToWorklist(this);
}
}
Adds a new use to this element. All types of this element are propagated to the new
usage.
/**
* Adds a new use to this element. All types of this element are propagated to the new
* usage.
*/
protected void addUse(TypeFlow use) {
if (uses.add(use)) {
use.addTypes(types);
}
}
Processing of the worklist element: propagate the types to all usages. That in turn can
add the usages to the worklist (if the types of the usage are changed).
/**
* Processing of the worklist element: propagate the types to all usages. That in turn can
* add the usages to the worklist (if the types of the usage are changed).
*/
@Override
protected void process() {
for (TypeFlow use : uses) {
use.addTypes(types);
}
}
}
The active element for method invocations. For virtual and interface calls, the types of this node are the receiver types. When a new receiver type is added, a new callee might be added. Adding a new callee means linking the type flow of the actual parameters with the formal parameters of the callee, and linking the return value of the callee with the return value state of the invocation. Statically bindable methods calls (static and special calls) have only one callee, but use the same code for simplicity. /**
* The active element for method invocations. For {@link InvokeKind#Virtual virtual} and
* {@link InvokeKind#Interface interface} calls, the {@link TypeFlow#getTypes() types} of this
* node are the receiver types. When a new receiver type is added, a new callee might be added.
* Adding a new callee means linking the type flow of the actual parameters with the formal
* parameters of the callee, and linking the return value of the callee with the return value
* state of the invocation.
*
* Statically bindable methods calls ({@link InvokeKind#Static static} and
* {@link InvokeKind#Special special} calls) have only one callee, but use the same code for
* simplicity.
*/
class InvokeTypeFlow extends TypeFlow {
private final MethodCallTargetNode callTarget;
private final TypeFlow[] actualParameters;
private final TypeFlow actualReturn;
private final Set<ResolvedJavaMethod> callees;
protected InvokeTypeFlow(MethodCallTargetNode callTarget, TypeFlow[] actualParameterFlows, TypeFlow actualReturnFlow) {
this.callTarget = callTarget;
this.actualParameters = actualParameterFlows;
this.actualReturn = actualReturnFlow;
this.callees = new HashSet<>();
}
private void linkCallee(ResolvedJavaMethod callee) {
if (callees.add(callee)) {
/* We have added a new callee. */
/*
* Connect the actual parameters of the invocation with the formal parameters of the
* callee.
*/
MethodState calleeState = results.lookupMethod(callee);
for (int i = 0; i < actualParameters.length; i++) {
if (actualParameters[i] != null) {
actualParameters[i].addUse(calleeState.formalParameters[i]);
}
}
/*
* Connect the formal return value of the callee with the actual return value of the
* invocation.
*/
if (actualReturn != null) {
calleeState.formalReturn.addUse(actualReturn);
}
addToWorklist(calleeState);
}
}
@Override
protected void process() {
if (callTarget.invokeKind().isDirect()) {
/* Static and special calls: link the statically known callee method. */
linkCallee(callTarget.targetMethod());
} else {
/* Virtual and interface call: Iterate all receiver types. */
for (ResolvedJavaType type : getTypes()) {
/*
* Resolve the method call for one exact receiver type. The method linking
* semantics of Java are complicated, but fortunatley we can use the linker of
* the hosting Java VM. The Graal API exposes this functionality.
*/
ResolvedJavaMethod method = type.resolveConcreteMethod(callTarget.targetMethod(), callTarget.invoke().getContextType());
/*
* Since the static analysis is conservative, the list of receiver types can
* contain types that actually do not provide the method to be called. Ignore
* these.
*/
if (method != null && !method.isAbstract()) {
linkCallee(method);
}
}
}
super.process();
}
}
Converts the Graal nodes of a method to a type flow graph. The main part of the algorithm is a reverse-postorder iteration of the Graal nodes, which is provided by the base class StatelessPostOrderNodeIterator. /**
* Converts the Graal nodes of a method to a type flow graph. The main part of the algorithm is
* a reverse-postorder iteration of the Graal nodes, which is provided by the base class
* {@link StatelessPostOrderNodeIterator}.
*/
class TypeFlowBuilder extends StatelessPostOrderNodeIterator {
private final StructuredGraph graph;
private final MethodState methodState;
Mapping from Graal nodes to type flows. This uses an efficient Graal-provided collection class. /**
* Mapping from Graal nodes to type flows. This uses an efficient Graal-provided
* {@link NodeMap collection class}.
*/
private final NodeMap<TypeFlow> typeFlows;
protected TypeFlowBuilder(StructuredGraph graph) {
super(graph.start());
this.graph = graph;
this.methodState = results.lookupMethod(graph.method());
this.typeFlows = new NodeMap<>(graph);
}
Register the type flow node for a Graal node.
/**
* Register the type flow node for a Graal node.
*/
private void registerFlow(ValueNode node, TypeFlow flow) {
/*
* We ignore intermediate nodes used by Graal that, e.g., add more type information or
* encapsulate values flowing out of loops.
*/
ValueNode unproxiedNode = GraphUtil.unproxify(node);
assert typeFlows.get(unproxiedNode) == null : "overwriting existing value";
typeFlows.set(unproxiedNode, flow);
}
Lookup the type flow node for a Graal node.
/**
* Lookup the type flow node for a Graal node.
*/
private TypeFlow lookupFlow(ValueNode node) {
ValueNode unproxiedNode = GraphUtil.unproxify(node);
TypeFlow result = typeFlows.get(unproxiedNode);
if (result == null) {
/*
* This is only the prototype of a static analysis, the handling of many Graal nodes
* (such as array accesses) is not implemented.
*/
throw error("Node is not supported yet by static analysis: " + node.getClass().getName());
}
return result;
}
private boolean isObject(ValueNode node) {
return node.getStackKind() == JavaKind.Object;
}
@Override
public void apply() {
/*
* Before the reverse-postorder iteration of fixed nodes, we handle some classes of
* floating nodes.
*/
for (Node n : graph.getNodes()) {
if (n instanceof ParameterNode) {
/*
* Incoming method parameter already have a type flow created by the
* MethodState.
*/
ParameterNode node = (ParameterNode) n;
if (isObject(node)) {
registerFlow(node, methodState.formalParameters[(node.index())]);
}
} else if (n instanceof ValuePhiNode) {
/*
* Phi functions for loops are cyclic. We create the type flow here (before
* processing any loop nodes), but link the phi values only later (after
* processing of all loop nodes.
*/
ValuePhiNode node = (ValuePhiNode) n;
if (isObject(node)) {
registerFlow(node, new TypeFlow());
}
} else if (n instanceof ConstantNode) {
/* Constants have a known type. */
ConstantNode node = (ConstantNode) n;
JavaConstant constant = node.asJavaConstant();
if (constant.isNull()) {
registerFlow(node, new TypeFlow());
}
}
}
super.apply();
for (Node n : graph.getNodes()) {
if (n instanceof ValuePhiNode) {
/*
* Post-processing of phi functions. Now the type flow for all input values has
* been created, so we can link the type flows together.
*/
ValuePhiNode node = (ValuePhiNode) n;
if (isObject(node)) {
TypeFlow phiFlow = lookupFlow(node);
for (ValueNode value : node.values()) {
lookupFlow(value).addUse(phiFlow);
}
}
}
}
}
private void allocation(ValueNode node, ResolvedJavaType type) {
/*
* The type flow of allocation nodes is one exact type. This is the source of the
* fixpoint iteration, the types are propagated downwards from these sources.
*/
TypeFlow flow = new TypeFlow();
flow.addTypes(Collections.singleton(type));
registerFlow(node, flow);
flow.addUse(results.getAllInstantiatedTypes());
}
@Override
protected void node(FixedNode n) {
if (n instanceof NewInstanceNode) {
NewInstanceNode node = (NewInstanceNode) n;
allocation(node, node.instanceClass());
} else if (n instanceof NewArrayNode) {
NewArrayNode node = (NewArrayNode) n;
allocation(node, node.elementType().getArrayClass());
} else if (n instanceof LoadFieldNode) {
/*
* The type flow of a field load is the type flow of the field itself. It
* accumulates all types ever stored to the field.
*/
LoadFieldNode node = (LoadFieldNode) n;
if (isObject(node)) {
registerFlow(node, results.lookupField(node.field()));
}
} else if (n instanceof StoreFieldNode) {
/*
* Connect the type flow of the stored value with the type flow of the field.
*/
StoreFieldNode node = (StoreFieldNode) n;
if (isObject(node.value())) {
TypeFlow fieldFlow = results.lookupField(node.field());
lookupFlow(node.value()).addUse(fieldFlow);
}
} else if (n instanceof ReturnNode) {
/*
* Connect the type flow of the returned value with the formal return type flow of
* the MethodState.
*/
ReturnNode node = (ReturnNode) n;
if (node.result() != null && isObject(node.result())) {
lookupFlow(node.result()).addUse(methodState.formalReturn);
}
} else if (n instanceof Invoke) {
/*
* Create the InvokeTypeFlow, which performs all the linking of actual and formal
* parameter values with all identified callees.
*/
Invoke invoke = (Invoke) n;
MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget();
TypeFlow[] actualParameters = new TypeFlow[callTarget.arguments().size()];
for (int i = 0; i < actualParameters.length; i++) {
ValueNode actualParam = callTarget.arguments().get(i);
if (isObject(actualParam)) {
actualParameters[i] = lookupFlow(actualParam);
}
}
TypeFlow actualReturn = null;
if (isObject(invoke.asNode())) {
actualReturn = new TypeFlow();
registerFlow(invoke.asNode(), actualReturn);
}
InvokeTypeFlow invokeFlow = new InvokeTypeFlow(callTarget, actualParameters, actualReturn);
if (callTarget.invokeKind().isIndirect()) {
/*
* For virtual and interface calls, new receiver types can lead to new callees.
* Connect the type flow of the receiver with the invocation flow.
*/
lookupFlow(callTarget.arguments().get(0)).addUse(invokeFlow);
}
/*
* Ensure the invocation is on the worklist at least once, even if it is a static
* call with not parameters that does not involve any type flows.
*/
addToWorklist(invokeFlow);
}
}
}
}