This paper was on new methods of statically determining which methods can be called by virtual method calls in Java. This is used for method inlining and producing more accurate call graphs, which can improve other analysis. This paper suggest two algorithms that builds type propagation graphs, where vertexes are variables and edges represent the flow of types due to assignments,. anc compares them against CHA and RTA. These new algorithms were designed so that they would scale linearly with the size of the Java program being analyzed. The analysis was implemented with the Soot framework, which provides Jimple, which is a representation of Java bytecode. Thus, this analysis can be used for all JVM languages and not just Java.
The Soot framework is an APO for manipulating Java bytecode. The implementation of the algorithms worked by reading all class files required by an application, converting them into Soot representations of the class, with Jimple classes representing the bytecode. Once the analysis and transformation is complete, the optimized code is output again as bytecode.
Class Hierarchy Analysis is a method for determining the set of types for objects used in Java applications. Basically, for any method call c.m() where the declared type of c is a class, the possible types of c are the declared type of c and it’s subclasses. If the declared type of c is an interface I, the possible types of c are all classes that implement I or a subinterface of I, plus all classes that are subclasses of those classes.
A call graph consists of one node for each method that is reachable from the main method. Each node in the call graph contains a collection of call sites, which are method calls. Edges go from call sites to all nodes that could be called from that call site. This call graph may contain edges and nodes that are not necessary; we want to remove these as much as possible.
Rapid type analysis is a way to improve the call graph. It uses the fact that an object can only be called if it is created by a ‘new’. There are two types of RTA: optimistic and conservative. In conservative RTA, CHA is performed and then the reachable methods are inspected to determine which types can be instantiated. Optimistic RTA constructs the call graph iteratively,
The two new algorithms refine RTA using the property that for any call c.m(), c can only be a type T if there is an expression of the form v = new T() followed by a set of assignments x_1 = v, x_2 = x_1, …, x_n = x_{n - 1}, c = x_{n - 1}. The two analysis work by building a type propagation graph, where nodes represent variables and a directed edge from a to b represents an assignment of the form b = a. This graph is used to determine which variables that methods are called can correspond to which classes in a more precise way than RTA.
One of the new algorithms, Variable-Type Analysis, uses the name of a variable as its representative. There are three types of variables, with the following representative names: local variables/parameters have a name C.m.a, fields are named C.f, and array references are named a[x].
The nodes of the type propagation graph is constructed as follows:
For every class C in the program:
For every field F in C
create a node C.F
For every method C.m in the call graph of P:
For every parameter p_i of C.m, create C.m.p_i
For every local variable l of C.m, create C.m.l
Create C.m.this
Create C.m.return
Afterwards, assignments between variables in the form of assignment statements and method calls are used to construct the edges of the type propagation graph. Native methods have their information input by hand. Aliases do not affect this alias’, because locals and fields cannot be aliased - if there is are two locals a and b, they refer to different locations. This is not true for arrays, and references to arrays can be stored in Objects. To solve this issue, when adding edges to the type propagation graph, if the two types are of array types or java.lang.Object, a bidirectional edge is added to the graph. Declared-type analysis works the same way, except that a node is used for each declared type and not each variable. The size of the graph is smaller, since there are fewer nodes, but the final answer is less precise.
To keep the algorithm simple, some design tradeoffs were made:
- Aliases - To avoid solving the aliasing problem except in the case of arrays, one node was used for all instances of a field instead of one per arrays.
- No killing based on casts - For assignments of the form lhs = (C)rhs, we do not take into account the extra type information given by the task of C, as this would require either a iterative solver or a more complex constraint solver.
- Pessimistic algorithm - The algorithm adds edges for all method calls in the conservative call graph, instead of using which types could currently reach the call at each step of the analysis. However, this would require iteration. We improve the pessimistic algorithm by generating a better conservative call graph.
- A whole-program approach - Instead of only propagating type information within a procedure and using the call graph to determine the effect of method calls.
- A 3-address representation of bytecode - This greatly simplified the analysis
Seven benchmarks were used to compare algorithms, including javac. One use of these algorithms is to reduce the size of the call graph. For this, both VTA and DTA perform better than even optimistic RTA, with VTA performing better. VTA removes 10% to 65% of the methods and 17 to 65% of the edges, whereas optimistic RTA varies from 7% to 56%. VTA has more notable improvements on more object-oriented benchmarks. VTA in general seems to be an improvement over RTA in all cases.
The other measurement is how many polymorphic calls. Given a call graph constructed by CHA, the percentage of polymorphic calls that were determined to be monomorphic by RTA, DTA, and VTA were measured. VTA showed a significant improvement, whereas RTA and DTA did not prune the call graph very much - VTA can resolve between 12% and 96% of the calls. The benchmarks were then instrumented to output profiling information to construct a complete call graph. On the large OO benchmarks, while VTA did significantly better than RTA, it still did not match the profiling information. In javac, VTA only determined 82% of the calls that the profile indicated were monomorphic. There are two ways to attempt to improve this percentage; perform more expensive static analysis or do dynamic optimization, such as branch target prediction.
Using this information to implement inlining showed small increases in speed on both the soot and javac benchmarks. For soot, using CHA to determine monomorhpic calls gives a 1% speedup in execution time, whereas VTA give 3% speedup. In javac, these percentages are 0% and 2%.
Both DTA and VTA behave linearly in practise, and thus scale well. VTA is approximately a constant factor of 10 slower than DTA, and so while is more precise is also more expensive. In conclusion, VTA gives significant improvements to DTA, which performs better than both CHA and RTA.