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.common.CompilationIdentifier.INVALID_COMPILATION_ID; 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.Debug; 36 import org.graalvm.compiler.debug.GraalError; 37 import org.graalvm.compiler.debug.Debug.Scope; 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.StructuredGraph.AllowAssumptions; 49 import org.graalvm.compiler.nodes.ValueNode; 50 import org.graalvm.compiler.nodes.ValuePhiNode; 51 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration; 52 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.BytecodeExceptionMode; 53 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.Plugins; 54 import org.graalvm.compiler.nodes.graphbuilderconf.InvocationPlugins; 55 import org.graalvm.compiler.nodes.java.LoadFieldNode; 56 import org.graalvm.compiler.nodes.java.MethodCallTargetNode; 57 import org.graalvm.compiler.nodes.java.NewArrayNode; 58 import org.graalvm.compiler.nodes.java.NewInstanceNode; 59 import org.graalvm.compiler.nodes.java.StoreFieldNode; 60 import org.graalvm.compiler.nodes.spi.StampProvider; 61 import org.graalvm.compiler.nodes.util.GraphUtil; 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 StructuredGraph graph = new StructuredGraph(method, AllowAssumptions.NO, INVALID_COMPILATION_ID); 245 /* 246 * Support for graph dumping, IGV uses this information to show the method name of a 247 * graph. 248 */ 249 try (Scope scope = Debug.scope("graph building", graph)) { 250 /* 251 * We want all types to be resolved by the graph builder, i.e., we want classes 252 * referenced by the bytecodes to be loaded and initialized. Since we do not run 253 * the code before static analysis, the classes would otherwise be not loaded 254 * yet and the bytecode parser would only create a graph. 255 */ 256 Plugins plugins = new Plugins(new InvocationPlugins()); 257 GraphBuilderConfiguration graphBuilderConfig = GraphBuilderConfiguration.getDefault(plugins).withEagerResolving(true); 258 /* 259 * For simplicity, we ignore all exception handling during the static analysis. 260 * This is a constraint of this example code, a real static analysis needs to 261 * handle the Graal nodes for throwing and handling exceptions. 262 */ 263 graphBuilderConfig = graphBuilderConfig.withBytecodeExceptionMode(BytecodeExceptionMode.OmitAll); 264 /* 265 * We do not want Graal to perform any speculative optimistic optimizations, 266 * i.e., we do not want to use profiling information. Since we do not run the 267 * code before static analysis, the profiling information is empty and therefore 268 * wrong. 269 */ 270 OptimisticOptimizations optimisticOpts = OptimisticOptimizations.NONE; 271 272 GraphBuilderPhase.Instance graphBuilder = new GraphBuilderPhase.Instance(metaAccess, stampProvider, null, null, graphBuilderConfig, optimisticOpts, null); 273 graphBuilder.apply(graph); 274 } catch (Throwable ex) { 275 Debug.handle(ex); 276 } 277 278 /* 279 * Build the type flow graph from the Graal graph, i.e., process all nodes that are 280 * deal with objects. 281 */ 282 283 TypeFlowBuilder typeFlowBuilder = new TypeFlowBuilder(graph); 284 typeFlowBuilder.apply(); 285 } 286 } 287 } 288 289 /** 290 * The active element during static analysis: types are added until a fixed point is reached. 291 * When a new type is added, it is propagated to all usages by putting this element on the 292 * {@link StaticAnalysis#addToWorklist worklist}. 293 */ 294 public class TypeFlow extends WorklistEntry { 295 private final Set<ResolvedJavaType> types; 296 private final Set<TypeFlow> uses; 297 298 protected TypeFlow() { 299 types = new HashSet<>(); 300 uses = new HashSet<>(); 301 } 302 303 /** Returns the types of this element. */ 304 public Set<ResolvedJavaType> getTypes() { 305 return types; 306 } 307 308 /** 309 * Adds new types to this element. If that changes the state of this element, it is added to 310 * the {@link StaticAnalysis#addToWorklist worklist} in order to propagate the added types 311 * to all usages. 312 */ 313 protected void addTypes(Set<ResolvedJavaType> newTypes) { 314 if (types.addAll(newTypes)) { 315 addToWorklist(this); 316 } 317 } 318 319 /** 320 * Adds a new use to this element. All types of this element are propagated to the new 321 * usage. 322 */ 323 protected void addUse(TypeFlow use) { 324 if (uses.add(use)) { 325 use.addTypes(types); 326 } 327 } 328 329 /** 330 * Processing of the worklist element: propagate the types to all usages. That in turn can 331 * add the usages to the worklist (if the types of the usage are changed). 332 */ 333 @Override 334 protected void process() { 335 for (TypeFlow use : uses) { 336 use.addTypes(types); 337 } 338 } 339 } 340 341 /** 342 * The active element for method invocations. For {@link InvokeKind#Virtual virtual} and 343 * {@link InvokeKind#Interface interface} calls, the {@link TypeFlow#getTypes() types} of this 344 * node are the receiver types. When a new receiver type is added, a new callee might be added. 345 * Adding a new callee means linking the type flow of the actual parameters with the formal 346 * parameters of the callee, and linking the return value of the callee with the return value 347 * state of the invocation. 348 * 349 * Statically bindable methods calls ({@link InvokeKind#Static static} and 350 * {@link InvokeKind#Special special} calls) have only one callee, but use the same code for 351 * simplicity. 352 */ 353 class InvokeTypeFlow extends TypeFlow { 354 private final MethodCallTargetNode callTarget; 355 private final TypeFlow[] actualParameters; 356 private final TypeFlow actualReturn; 357 private final Set<ResolvedJavaMethod> callees; 358 359 protected InvokeTypeFlow(MethodCallTargetNode callTarget, TypeFlow[] actualParameterFlows, TypeFlow actualReturnFlow) { 360 this.callTarget = callTarget; 361 this.actualParameters = actualParameterFlows; 362 this.actualReturn = actualReturnFlow; 363 this.callees = new HashSet<>(); 364 } 365 366 private void linkCallee(ResolvedJavaMethod callee) { 367 if (callees.add(callee)) { 368 /* We have added a new callee. */ 369 370 /* 371 * Connect the actual parameters of the invocation with the formal parameters of the 372 * callee. 373 */ 374 MethodState calleeState = results.lookupMethod(callee); 375 for (int i = 0; i < actualParameters.length; i++) { 376 if (actualParameters[i] != null) { 377 actualParameters[i].addUse(calleeState.formalParameters[i]); 378 } 379 } 380 381 /* 382 * Connect the formal return value of the callee with the actual return value of the 383 * invocation. 384 */ 385 if (actualReturn != null) { 386 calleeState.formalReturn.addUse(actualReturn); 387 } 388 addToWorklist(calleeState); 389 } 390 } 391 392 @Override 393 protected void process() { 394 if (callTarget.invokeKind().isDirect()) { 395 /* Static and special calls: link the statically known callee method. */ 396 linkCallee(callTarget.targetMethod()); 397 } else { 398 /* Virtual and interface call: Iterate all receiver types. */ 399 for (ResolvedJavaType type : getTypes()) { 400 /* 401 * Resolve the method call for one exact receiver type. The method linking 402 * semantics of Java are complicated, but fortunatley we can use the linker of 403 * the hosting Java VM. The Graal API exposes this functionality. 404 */ 405 ResolvedJavaMethod method = type.resolveConcreteMethod(callTarget.targetMethod(), callTarget.invoke().getContextType()); 406 407 /* 408 * Since the static analysis is conservative, the list of receiver types can 409 * contain types that actually do not provide the method to be called. Ignore 410 * these. 411 */ 412 if (method != null && !method.isAbstract()) { 413 linkCallee(method); 414 } 415 } 416 } 417 super.process(); 418 } 419 } 420 421 /** 422 * Converts the Graal nodes of a method to a type flow graph. The main part of the algorithm is 423 * a reverse-postorder iteration of the Graal nodes, which is provided by the base class 424 * {@link StatelessPostOrderNodeIterator}. 425 */ 426 class TypeFlowBuilder extends StatelessPostOrderNodeIterator { 427 private final StructuredGraph graph; 428 private final MethodState methodState; 429 /** 430 * Mapping from Graal nodes to type flows. This uses an efficient Graal-provided 431 * {@link NodeMap collection class}. 432 */ 433 private final NodeMap<TypeFlow> typeFlows; 434 435 protected TypeFlowBuilder(StructuredGraph graph) { 436 super(graph.start()); 437 438 this.graph = graph; 439 this.methodState = results.lookupMethod(graph.method()); 440 this.typeFlows = new NodeMap<>(graph); 441 } 442 443 /** 444 * Register the type flow node for a Graal node. 445 */ 446 private void registerFlow(ValueNode node, TypeFlow flow) { 447 /* 448 * We ignore intermediate nodes used by Graal that, e.g., add more type information or 449 * encapsulate values flowing out of loops. 450 */ 451 ValueNode unproxiedNode = GraphUtil.unproxify(node); 452 453 assert typeFlows.get(unproxiedNode) == null : "overwriting existing value"; 454 typeFlows.set(unproxiedNode, flow); 455 } 456 457 /** 458 * Lookup the type flow node for a Graal node. 459 */ 460 private TypeFlow lookupFlow(ValueNode node) { 461 ValueNode unproxiedNode = GraphUtil.unproxify(node); 462 TypeFlow result = typeFlows.get(unproxiedNode); 463 if (result == null) { 464 /* 465 * This is only the prototype of a static analysis, the handling of many Graal nodes 466 * (such as array accesses) is not implemented. 467 */ 468 throw error("Node is not supported yet by static analysis: " + node.getClass().getName()); 469 } 470 return result; 471 } 472 473 private boolean isObject(ValueNode node) { 474 return node.getStackKind() == JavaKind.Object; 475 } 476 477 @Override 478 public void apply() { 479 /* 480 * Before the reverse-postorder iteration of fixed nodes, we handle some classes of 481 * floating nodes. 482 */ 483 for (Node n : graph.getNodes()) { 484 if (n instanceof ParameterNode) { 485 /* 486 * Incoming method parameter already have a type flow created by the 487 * MethodState. 488 */ 489 ParameterNode node = (ParameterNode) n; 490 if (isObject(node)) { 491 registerFlow(node, methodState.formalParameters[(node.index())]); 492 } 493 } else if (n instanceof ValuePhiNode) { 494 /* 495 * Phi functions for loops are cyclic. We create the type flow here (before 496 * processing any loop nodes), but link the phi values only later (after 497 * processing of all loop nodes. 498 */ 499 ValuePhiNode node = (ValuePhiNode) n; 500 if (isObject(node)) { 501 registerFlow(node, new TypeFlow()); 502 } 503 } else if (n instanceof ConstantNode) { 504 /* Constants have a known type. */ 505 ConstantNode node = (ConstantNode) n; 506 JavaConstant constant = node.asJavaConstant(); 507 if (constant.isNull()) { 508 registerFlow(node, new TypeFlow()); 509 } 510 } 511 } 512 513 super.apply(); 514 515 for (Node n : graph.getNodes()) { 516 if (n instanceof ValuePhiNode) { 517 /* 518 * Post-processing of phi functions. Now the type flow for all input values has 519 * been created, so we can link the type flows together. 520 */ 521 ValuePhiNode node = (ValuePhiNode) n; 522 if (isObject(node)) { 523 TypeFlow phiFlow = lookupFlow(node); 524 for (ValueNode value : node.values()) { 525 lookupFlow(value).addUse(phiFlow); 526 } 527 } 528 } 529 } 530 } 531 532 private void allocation(ValueNode node, ResolvedJavaType type) { 533 /* 534 * The type flow of allocation nodes is one exact type. This is the source of the 535 * fixpoint iteration, the types are propagated downwards from these sources. 536 */ 537 TypeFlow flow = new TypeFlow(); 538 flow.addTypes(Collections.singleton(type)); 539 registerFlow(node, flow); 540 flow.addUse(results.getAllInstantiatedTypes()); 541 } 542 543 @Override 544 protected void node(FixedNode n) { 545 if (n instanceof NewInstanceNode) { 546 NewInstanceNode node = (NewInstanceNode) n; 547 allocation(node, node.instanceClass()); 548 } else if (n instanceof NewArrayNode) { 549 NewArrayNode node = (NewArrayNode) n; 550 allocation(node, node.elementType().getArrayClass()); 551 552 } else if (n instanceof LoadFieldNode) { 553 /* 554 * The type flow of a field load is the type flow of the field itself. It 555 * accumulates all types ever stored to the field. 556 */ 557 LoadFieldNode node = (LoadFieldNode) n; 558 if (isObject(node)) { 559 registerFlow(node, results.lookupField(node.field())); 560 } 561 } else if (n instanceof StoreFieldNode) { 562 /* 563 * Connect the type flow of the stored value with the type flow of the field. 564 */ 565 StoreFieldNode node = (StoreFieldNode) n; 566 if (isObject(node.value())) { 567 TypeFlow fieldFlow = results.lookupField(node.field()); 568 lookupFlow(node.value()).addUse(fieldFlow); 569 } 570 571 } else if (n instanceof ReturnNode) { 572 /* 573 * Connect the type flow of the returned value with the formal return type flow of 574 * the MethodState. 575 */ 576 ReturnNode node = (ReturnNode) n; 577 if (node.result() != null && isObject(node.result())) { 578 lookupFlow(node.result()).addUse(methodState.formalReturn); 579 } 580 581 } else if (n instanceof Invoke) { 582 /* 583 * Create the InvokeTypeFlow, which performs all the linking of actual and formal 584 * parameter values with all identified callees. 585 */ 586 Invoke invoke = (Invoke) n; 587 MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget(); 588 589 TypeFlow[] actualParameters = new TypeFlow[callTarget.arguments().size()]; 590 for (int i = 0; i < actualParameters.length; i++) { 591 ValueNode actualParam = callTarget.arguments().get(i); 592 if (isObject(actualParam)) { 593 actualParameters[i] = lookupFlow(actualParam); 594 } 595 } 596 TypeFlow actualReturn = null; 597 if (isObject(invoke.asNode())) { 598 actualReturn = new TypeFlow(); 599 registerFlow(invoke.asNode(), actualReturn); 600 } 601 602 InvokeTypeFlow invokeFlow = new InvokeTypeFlow(callTarget, actualParameters, actualReturn); 603 604 if (callTarget.invokeKind().isIndirect()) { 605 /* 606 * For virtual and interface calls, new receiver types can lead to new callees. 607 * Connect the type flow of the receiver with the invocation flow. 608 */ 609 lookupFlow(callTarget.arguments().get(0)).addUse(invokeFlow); 610 } 611 /* 612 * Ensure the invocation is on the worklist at least once, even if it is a static 613 * call with not parameters that does not involve any type flows. 614 */ 615 addToWorklist(invokeFlow); 616 } 617 } 618 } 619 }