An Inter-procedural Approach for Optimizations of Java Programs
Antonio Magnaghi, Shuichi Sakai, Hidehiko Tanaka
The University of Tokyo

class XX extends X {S13:public void m() {S14:
System.out.println("XX"+c); }}1 Introduction
Java is capturing an increasing interest both in academic and industrial contexts. Code portability("Write once-Run everywhere") is one of the most
relevant aspects of the language, and it relyes on
the interpretation of Java byte-code by the JVM. Asa drawback, program execution can be considerablyslower compared to native code. Our research activity
aims at improving execution performance of Java programs through the extraction of implicit parallelism[1, 2, 3]. This paper reports on the source-to-sourceJava optimizer that we are developing in order to reconstruct source code into a semantically equivalentmulti-threaded program. As original contribution, theadopted approach directly addresses the rich and articulated Object Oriented features of Java. Source code
static analysis is performed on an inter-procedural level
through the characterization of method invocation effects in order to achieve a better description of program
dependencies.
2 Target Optimizations
We are focusing on task-level parallelism extraction[1, 2], hence we are developing a framework for statically analyzing program behavior beyond method invocation boundaries. As follows a Java code fragment
is proposed as a working example that will be considered also in subsequent sections to illustrate the tasks
performed by the optimizer in di erent passes. Before
proceeding, let us discuss how we intend to identify
implicit parallelism in source programs.

Let us focus on the code of method p in class Y (using a notation borrowed from C + +: X :: p()) and on
its body. In order to characterize the potential dependencies between instructions S 4 and S 5 (true, outputor anti dependency) it is necessary to describe the effect produced in the program execution environment
as a consequence of invocation of methods m and n
respectively. The member eld myX of class Y is anested object whose type is X , hence it comprises two
primitive member elds: c and i. In S 4 and S 5, theactions performed by methods m and n on the receiverobject myX can alter the state of its constituent elds.
Therefore we need to analyze X :: m() and X :: n(int).
Method X :: m() performs an output operation thatuses as input the value of member eld c. Hence wecan conclude that: No alteration is produced on the state of the re-ceiver by X :: m().

 The execution of X :: m() requires the bit of in-formation associated to member eld c.

This situation can be conveniently modeled by associating two sets to method X :: m(), a set I N (X ::m()) = fthis:cg containing the memberelds used
as input to the task performed by the method (methods instructions are considered as a whole), and a set
OU T (X :: m()) = fg containing the memberelds
modi ed by the method invocation. Proceeding in thesame way for the other method (X :: n(int)) invoked in
S 5, the following sets are produced: I N (X :: n(int)) =feg, OU T (X :: n(int)) = fthis:ig. After collecting
this necessary information, let us return to our original matter: the dependency analysis of instructions
S 4 and S 5.
It is possible to produce more detailed
considerations. The call site represented by instruction S 4 operates on receiver myX , and we know that
myX:c is used by m(), because I N (X :: m()) contains "this:c". In S 5 the receiver is still myX , andthe method invocation produces an alteration of myX:ibecause OU T (X :: n(int)) contains "this:i". As it isnot possible for the two member elds of myX object
to be alias of one another, these considerations lead
us to conclude that S 4 and S 5 do not interfere witheach other even if they are invoked on the same object.
Therefore S 4 and S 5 can be issued simultaneously ina multi-threaded manner.

class Y {S1:
private X myX;
S2:
public void p() {S3:
int myValue;...
S4:
myX.m();
S5:
myX.n(myValue); }}class X {S6:
private char c;
S7:private int i;
S8:public void m() {S9:System.out.println("X"+c); }S10:
public void n(int e) {S11:this.i = e; }S12:public void n(long j) {... }}1

3 Compiler First Pass
In the previous paragraph we exposed ideas underlying
the implementation of an analysis framework. In thefollowing sections an overview is presented of current
implementation status and of the design choices necessary to face the great deal of situations arising when
optimizing a real program. While parsing the inputJava code, the following attributes are evaluated:
1) Construction of the Symbol Table (ST). The ST
stores objects declared in the program according to thelanguage scope rules. Compared to C language, in Javathe task is simpli ed by the absence of "typedef" declarations. On the other hand, visibility extends also toclass member elds. Moreover in Java an object can bedeclared in any point where an instruction can appear,and not only at the beginning of a new scope marker.
2) Construction of method abstract syntax trees.
Syntax trees provide a structured representation ofsource code, allowing successive analysis phases. The
adopted syntax tree representation is designed to facilitate inter-procedural analysis. In this initial phase weare not directly addressing more standard transformations as, for example, expression optimizations, hence
expressions are represented in a compact way in syntaxtrees.
3) Identi cation of call sites. Call sites represent
discontinuity points in program control ow and thepoints of interest in task-level optimizations. Everymethod keeps a list whose elements point to tree nodes
where a method is invoked. Every time a new call site
is met, it is added to the call site list, and a call site
descriptor is compiled with information that includes
the receiver and actual parameters. If these are locallydeclared variables or method parameter, their descriptors are already allocated on the ST. However, not all
information required to completely characterize a callsite can be available in this phase. For example, callsite descriptors need to contain also information about
the invoked method, but it can belong to a di erent
class that maybe textually follows the invocation pointin the source le. Let us consider method Y :: p(). Itscall site list contains the syntax tree nodes that represent instructions S 4 and S 5. The call site descriptor ofS 5 links the identi er myV alue to the corresponding
variable descriptor stored in ST; on the other hand thelink to the code of method n is still dangling and it will
be resolved successively.
4 Compiler Second Pass
The second pass of the compiling process aims at gathering additional information that is available only afterparsing the whole input program. In particular, thefollowing activities are carried out:
1) Resolution of name references. All name references that were dangling from previous pass are xed.
This concerns, for example, member eld accesses: thereference to a class member eld is linked to the appropriate descriptor in this phase.

2) Construction of the call-graph. A method invocation in a call site descriptor is associated to the corresponding syntax tree. Inheritance and method overloading play a relevant role in this context. When identifying the appropriate method, at rst the type of thereceiver object provides a candidate class from whichto start the matching procedure. It can be necessary toinspect one or more ancestor classes of the candidateclass, moving upward in the program taxonomy. Inside
a class is then required to resolve method overloading:the more speci c method is identi ed that matches thedescriptor of the call site under analysis. Also in thiscase it is required to consider the program taxonomy
when matching actual invocation parameters against
formal parameters in method signatures. Hence, considering our example, in the call site descriptor of S5
the method reference is set to X :: n(int).
3) Evaluation of E xtent set for every method. The
Extent of a method m is de ned as the set of all othermethods that, at run time, m might invoke directly orindirectly. Such information corresponds to the identi cation of the portion of call graph reachable fromm. Current implementation does not support recursion yet. Given a call site descriptor D , E xtent evaluation requires to inspect also all descendant classes of
the class containing the method linked to D. If, forexample, after declaration S3, eld myX is assigned
an object of type X X and if this de nition reaches S 4,
then the execution of S 4 would activate method m()
in class X X (X X :: m()) because of dynamic binding mechanism. Therefore, Extent(X :: p()) = fX ::m(); X X :: m(); X :: n(int)g.
4) Topological sorting of program methods. Based on
the Extent set, all methods are topologically sorted ina list L. If Xq :: mh (:::) is the k-th element in L, thenevery method in E xtent(Xq :: mh (:::)) is included inthe (k-1)-length pre x of L. In our example a possible
method sorting is L =< X X :: m(); X :: n(int); Y ::p(); X :: n(long ) >. Processing methods in this order
guarantees that all information necessary in a method
is available when it is processed.
5 Current Implementation Activity
Current activity is concluding the program static analysis in order to characterize method behavior. Following steps will include the identi cation of parallelizable
code portions and multi-threaded code generation.
References[1]

C. Brownhill, A. Nicolau, S. Novack, C. Polychronopoulos.

Achieving Multi-level Parallelization. Proc. Of Inter-national Symposium ISHPC'97, Springer, pp. 183-194[2]M.

Rinard,P. Diniz.

Commutativity Analysis:Analysis Technique for Parallelizing Compilers.

A NewACM,

Trans. on Programming Languages and Systems, vol. 19,No.6, Nov. 1997, pp. 942-991[3]

H. Zima, B. Chapman.

Supercompilers for Parallel andVector Computers. ACM Press, 1992.