Call-Graph Optimization of Java Applications
Antonio Magnaghi, Shuichi Sakai and Hidehiko Tanaka
The University of Tokyo

This represents a conservative assumption.
In order to re ne type-information, the function
Java popularity has remarkably increased over the last typeInference(:) is introduced.
For every apfew years and the utilization of Java programming lan- plication reference type t: typeInf erence(t) =guage has ourished both in academic and industrial subT reeClasses((t)) \ LCS
projects. The demand for high-performance Java applications is, however, stressing the necessity of appro- 3 Experimental Evaluation of LCA
priate compilation techniques and aggressive optimiza- Given a program call-graph representing the possibletion procedures. In this paper we present a framework callees at each call site, interprocedural analysis sumto enhance static analysis of Java applications by ex- marizes the e ects of callees at each method entry. Beploitation of type-inference [1, 4]. And we experimen- cause of Java dynamic dispatching mechanism, the set
tally evaluate how such a framework can be utilized to of possible callees at each call-site is dicult to evaluate
improve interprocedural analysis for source code level precisely, necessitating to compute the possible classes
optimizations. For brevity reasons, the proposed con- of message receivers or the possible values returned bycepts are not strictly formalized and exposition simply invoked methods. Generally, more consolidated callgraph construction techniques rely on interprocedural
outlines the implemented algorithms.
data- ow analysis. In this section we investigate an
2 Type-Inference via Living Classes Analysis
alternative approach: type-inference through LCA isThe program to analyze is represented by the Appli- applied to enhance call-graph construction.
cation Taxonomy (AT). AT collects, in a control- ow
insensitive manner, all reference types (classes or inApplication
Classes Code Linesterfaces) needed for compiling the application. AT el1. httpserver
162
ements are distinguished in class-nodes and interface2. proxy3309
nodes. AT nodes are organized in a tree data struc3. RngPack
81419
ture that collects all syntactic and semantic informa4. dent
224286tion necessary for successive analysis procedures. The
5. Jasmine177
15585
developed representation model (AT) formulates also
proper conditions in order to deal with programming
Figure 1: Benchmarks
constructs critical to static analysis, such as dynamic
class generation and native methods.
The choice of benchmarks is a delicate aspect beWe aim at inferring the classes an expression can be cause of the lack of standard programs that are widely
instance of at run-time based on the analysis of ob- accepted by the Java community. This is due, on one
jects instantiated by the application. Thus, we de ne hand, to the broad variety of programming contexts
the application Living Classes Set (LCS). LCS collects that Java APIs address, and, on the other hand, toall AT class-nodes that correspond to classes conserva- the relative newness of the language. We chose a set
tively generated by any application execution path. A of ve Java benchmarks based on diversi cation of apclass C is excluded from LCS if and only if there can plication area and complexity as well: 1.) httpserver:
be no execution path in the application that causes C is a simple HTTP-server application; 2.) proxy: is ato be instantiated.
generic cascading proxy server supporting single socket
Let type(:) be a function that returns the unique network applications; 3.) RngPack: implements a ranstatic type associated to a program expression. type(:) dom number generator; 4.) dent: is a formatter ofis properly de ned as Java is strictly statically typed. Java source code; 5.) Jasmine: is a Java byte-code deLet subT reeClasses(:) be a function that maps every compiler. Figure 1 summarizes some features of theseAT node n to the set of class-nodes of the AT sub-tree programs. The number of classes in gure 1 refers torooted in n. There exists a one-to-one correspondence classes (interfaces) contained in the application distri between reference types in the application and AT bution package. The number of code lines refers to thenodes. Hence subT reeClasses(:) can equivalently be application source code whether it is available, otherdescribed as a function that maps every reference type wise it is obtained through byte-code decompilation.
t in the application to the set s of all application class All benchmarks are pure Java applications.
types that subclass t. Therefore, if expression expr has
The conducted experimentation can be described asstatic reference type t = type(expr), then at run-time follows. Firstly AT is constructed and LCS is evaluexpr is instance of classes in subT reeClasses( (t)).
ated. Figure 2 shows for each benchmark the cardinal1

Introduction1ity of AT and LCS. A preliminary observation is thatfor benchmarks 1 to 4 the number of taxonomy classes
does not vary much (about 200 elements). The numberof classes (interfaces) that constitute the applications isrelatively small (see gure 1), and therefore the majority of AT nodes are represented by classes (interfaces)
belonging to jdk APIs. Benchmark 5 represents an exception: 49.2% of AT nodes are classes (interfaces) thatbelong to the application (177 AT nodes out of 360).
1. httpserver
2. proxy
3. RngPack
4. dent
5. JasminejAT j jLCS j
198
197
191
206
360

111
113
106
116
260

Figure 2: AT and LCS Cardinality
It is interesting to additionally observe that for applications 1, 2, 3, and 4 the percentage of living classes
in the AT is considerably stable (respectively: 56%,57.3%, 55.5% and 56.3%) even if the size of the applications in terms of lines of code varies in a remarkable way from benchmark 1 to benchmark 4. The fth
benchmark shows a di erent behavior instead: 72.2%
of taxonomy classes are living classes. Such a highpercentage of living classes a ects LCA precision as
following experimental steps clearly prove. Successively, experimentation consists in evaluating the effectiveness of LCA for call-graph optimization. Hence,
two approaches are used when producing the application call-graphs. In the rst place, for each benchmark,the call-graph is produced without the exploitation oftype-inference by LCA. Therefore, only AT is taken
into consideration when analyzing call-sites. Then, thecall-graph is computed again, but LCA is performed
in order to gather more precise information. Figures 3
visualizes the achieved results.
1. httpserver
2. proxy
3. RngPack
4. dent
5. Jasmine

Method Reduction (%)
19.9
18.7
18.5
19.4
9.2

Figure 3: Method Reduction
Figure 3 compares the number of methods (constructors) included in the constructed call-graphs when LCA
is not employed against the case when LCA is carriedout. It shows for each benchmark the reduction percentage of the number of call-graph methods (constructors). LCA performs eciently on benchmarks 1,2,3,4:
it is possible to obtain by LCA a 20% reduction ofmethods (constructors) in the call-graph compared tothe case where LCA is not employed. In the case of thefth benchmark, instead, LCA produces a 9.2% reduction. As previously observed such a benchmark showsa higher percentage of living classes (72.2%) comparedto the other selected applications.
4Conclusions

We proposed both a conceptual framework and an implementation to carry out type-inference on Java programs. Using this framework, we empirically accesseda set of benchmarks, which vary in complexity and areaof application. We applied LCA type-inference to thesebenchmarks in order to optimize their call-graphs. Obtained results showed that LCA enabled substantial
improvements in call-graph construction. For thosebenchmarks where the percentage of application living
classes was approximately 50%, LCA type-inference led
us to a signi cant reduction in the number of callgraph constructors/methods (20%). However, in one
case (benchmark 5) the percentage of living classes wasremarkably higher (more than 72%) than in the otherbenchmarks, and call-graph optimization achieved by
LCA was limited. We are improving LCA performance
also in such situations by adopting a control- ow sensitive algorithm for evaluation of application livingclasses. We expect that LCA type-inference can result bene cial not only to call-graph construction, butalso to other essential tasks performed by optimizingcompilers. Speci cally, in our research project about
automatic parallelization of Java programs [2, 3], LCA
is adopted not only to enhance program call-graphs,
but also to develop an interprocedural analysis framework where aliasing con icts are investigated via TypeBased Aliasing Analysis (TBAA) [3].
References[1] S. Collin, D. Colnet, O. Zendra. Type Inference for
Late Binding: the SmallEi el Compiler. In Proceedings of the Joint Modular Languages Conference (JMLC'97), Lecture Notes in Computer Science, Springer-Verlag, pp. 67-81, 1997
[2] A. Magnaghi, S. Sakai, H. Tanaka. An Interprocedural Approach for Optimizations of Java
Programs. In Proceedings of Information Processing Society of Japan, 1998
[3] A. Magnaghi, S. Sakai, H. Tanaka. Interprocedural Analysis for Parallelization of Java
Programs. In Proceedings of the 4th International
Conference on Parallel Computation (ACPC99),
Lecture Notes in Computer Science, SpringerVerlag, pp. 594-595, 1999
[4] A. Magnaghi, S. Sakai, H. Tanaka. Evaluationof a Type-Inference Framework for Java Applications, Proceedings of the Workshop on Javafor High-Performance Computing, ACM International Conference on Supercomputing (ICS99),
pp. 67-74, June, 1999, Rhodes, Greece.