Inter-Procedural Analysis for Parallelizationof Java Programs
Antonio Magnaghi, Shuichi Sakai, Hidehiko Tanaka
The University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo, Japan

1 Introduction

Parallelization of Java programs is a complex task due to inheritance, dynamic
method dispatching and aliases. Our research [2] aims to perform static analysis of Java programs in order to identify implicit parallelism. In this paper, wediscuss rst the inter-procedural analysis technique we are studying and implementing to characterize data-dependency. And then we enhance this frameworkwith type-based alias analysis.

2 Inter-Procedural Analysis

Some of the fundamental characteristics of Object Oriented Programming(OOP),
such as information hiding, lead us to stress the role of inter-procedural analysis
for Java programs because access to objects relies heavily on method dispatching. Through the example below we demonstrate how implicit parallelism can beidenti ed in source programs. Let us focus on instructions S1 and S2 of method
p in class Y (using a notation borrowed from C++:class Y {Y::p()). The member eld myX of class Y is a referprivate X myX;ence object comprising two primitive member elds: cvoid p() {and i. In S1 and S2, the actions performed by methods
S1:myX.m();m and n on the receiver myX can alter the state of its conS2:myX.n(3);}}stituent elds. Method X::m() performs an assignment
class X {that uses as input the value of member eld c. Hence
private char c;
we can conclude that: 1.) no alteration is produced on
private int i;
the state of the receiver by X::m(); 2.) the execution
void m() {of X::m() requires member eld c as input informaS3:String s="X"+c;} tion. We model this situation by associating two sets tovoid n(int e) {method X::m(), a set IN(X::m())=fthis.cg containS4:i=e; }}ing objects externally visible to the method and used
as input to the task performed by the method.
And similarly, OUT(X::m())=; is the set of objects which are modi ed. The following sets are produced for X::n(int): IN(X::n(int))=feg, OUT(X::n(int))=
fthis.ig. Because it is not possible for the two member elds of myX (c and i)
to be alias of one another, we conclude that S1 and S2 in Y::p do not interferewith each other even if they are invoked on the same object. Therefore S1 andS2 can be issued simultaneously in a multi-threaded manner.

3 Type-based Pointer Analysis

In more general contexts than the example above, alias problems arise [1]. We canformalize our type-based approach for aliases as follows. Let Class and Object
respectively be the sets containing all program classes, and all program objects.
Let T ype be a function that returns the class type of an object. Let Comp be afunction from Class to 2Class . It maps every class to the set of reference types
encountered by recursively traversing the data structure of the input class. If
cls 2 Class, and S is the set of nodes of the sub-tree
S rooted in cls in the programtaxonomy, then we designate Comp (cls) = i2S Comp(i). If we consider twoobjects in Object, obj1 and obj2 , we assume that an alias may take place i thefollowing condition holds: Comp (Type(obj1 ))\Romp (Type(obj2 ))6= ;4 Analyzer Structure

Current implementation produces dependency information based on the algorithms expressed above, conveniently addressing inheritance and method (constructor) overloading. The structure of the analyzer can be outlined as follows:
1.) First Pass: the input program is parsed and information about call sides iscollected. 2.) Second Pass: it gathers additional information that becomes available only after parsing the whole input program. The following activities arecarried out: call graph construction; topological sorting of methods (constructors) based on call graph analysis (the concept of Transfer set is introduced asa generalization to OOP of the Extension in [3]); evaluation of IN and OUT
sets for every call site and method (constructor) by type-based alias analysis.

5 Conclusions

Preliminary evaluation has been carried out. On simple benchmarks like Linpack
and Primes, we identi ed parallelism associated to immutable objects or statelessmethods. Current research activity is improving the alias analysis algorithms byre ning the type information associated with every program object.

References
1. A. Diwan, K. McKinley, E. Moss. Type-based Alias Analysis. In ACM SIGPLAN98
Conference on Programming Language Design and Implementation, pp. 106-117,
1998.
2. A. Magnaghi, S. Sakai, H. Tanaka. An Inter-procedural Approach for Optimizationsof Java Programs. In Proceedings of the Information Processing Society of Japan,
vol. 57, pp. 299-300, 1998.
3. M. Rinard, P. Diniz. Commutativity Analysis: a New Analysis Technique for Parallelizing Compilers. ACM Transactions on Programming Languages and Systems,
vol. 19, no. 6, pp. 942-991, 1997.
4. H. Zima, B. Chapman. Supercompilers for Parallel and Vector Computers. ACM
Press, 1992.