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