IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

1

JAAT: A Practical Alias Analysis Tool
for Java Programs

Fumiaki OHATA, Yusuke YAMANAKA, Kazuhiro KONDO and Katsuro
INOUE

The authors are with the Software Engineering Research Group (C/O Katsuro Inoue), Division of Software
Science, Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama-cho, Toyonaka, Osaka
560-8531, JAPAN. E-mail: {oohata, y-yamank, kondou, inoue}@ics.es.osaka-u.ac.jp.
December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

2

Abstract
When an expression refers to a memory location that is referred to by another expression, we
say that there is an alias relation between those expressions. Alias analysis, i.e, the extractionof such relations is essential for efficient maintenance of object-oriented programs.
Although many researchers have already proposed analysis methods and implemented prototype tools for object-oriented programs, difficulties still remain in applying such methods topractical tools in the sense of precision, extensibility, and scalability. Focusing mainly on practical implementation, we propose an alias analysis method for object-oriented programs. Thismethod employs a two-phase, on-demand, instance-based, and extensible algorithm.
We have implemented the proposed method as JAAT. JAAT can analyze large programs
such as Java Developer’s Kit (JDK) class library. We have applied JAAT to various large Java
programs and confirmed JAAT’s performance.
Keywords
Alias, Object-Oriented programs, Scalability, Java

I. Introduction
An alias relation between two expressions e0 and e1 in a source program is a relationsuch that e0 and e1 may possibly refer to the same memory location during program
execution. Alias relations are generated by various situations such as parameter passing,reference variables and indirect reference with pointer variables. We say that e0 is an aliasof e1 (and vice versa) when there is an alias relation between e0 and e1 . An alias relation isan equivalence relation, and we call its equivalence class an alias set. Alias analysis is an
extraction method of alias sets by static analysis, and alias analysis is needed for various
purposes such as compiler optimization[1] and program slicing[23].
Alias analysis was first proposed for traditional procedural languages such as C andPascal as part of the static analysis of pointer variables[2], [16], [22], [28]. Concepts suchas class, inheritance, dynamic binding and polymorphism[7] have been introduced throughObject-oriented (OO) languages such as C++[3] and Java[14], and alias analysis methods
for OO programs have been devised[24], [27]. [24], [27] focus mainly on analysis algorithms,
and they have not explored practicability and scalability as analysis tools.
We are interested in developing a practical alias analysis tool for OO languages such
as Java; however, implementation of already proposed approaches remains difficult as
December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

3

discussed in [21].
The primary issue for such tools is scalability. Since programs being developed havebecome larger and class libraries associated with the developed programs tend to be hugeand complex, the analysis should satisfy scalability in handling large programs. However,many analysis methods produce poor results due to inherent implementations and morestudies need to be conducted[21].
Another issue is the usage and approach of the analysis. Most previous works focused
mainly on compiler optimization and back-end for data-flow analysis as applications of thealias analysis. For such purposes, all alias relations in the program need to be extracted
by the analysis. Nonetheless, we believe that alias analysis is useful for program debugging and understanding[21]. For program debugging and understanding, not all the alias
relations are needed at one time; only user-requested relations are to be extracted quickly.
Thus, we have to newly devise an on-demand, incremental analysis approach, which canbe used effectively in an interactive environment.
To resolve these issues, we propose in this paper a new alias analysis method for OO
programs. We have developed a two-phase approach, in which intra-module analysis isdone in Phase 1 for whole programs and libraries, and inter-module analysis is done in
Phase 2 only for an user-demanded target. This two-phase approach greatly contributes
to the overall performance of the analysis.
In this paper, we also consider analysis precision. Flow-sensitiveness of the analysis is an
important factor in determining the analysis precision and cost[18], [19], [20], [30]. A flow
insensitive approach is easily implemented in general; however, this approach produces
poor results. Also, for OO programs, an instance-based analysis for individual objects instantiated from a single class will improve the analysis precision programs when compared
to class-based analysis, although the instance-based approach generally requires high analysis cost. We take a flow-sensitive instance-based analysis in this research to aim for highanalysis precision with practically affordable analysis cost.
The two-phase approach is also suitable for extending analysis algorithms since software
components for each phase and sub-phase are easily replaceable. Therefore, a new analysis
policy for a precision-cost compromise will be introduced.

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

4

We have implemented the proposed algorithm as JAAT. JAAT considers scalability
in the sense that it can analyze large programs with reasonable computation time. For
example, the analysis time of 32,037 lines of Java programs with 119,564 lines of JDKlibrary was 168 seconds in Phase 1 and less than 1 milli second in Phase 2. This resultshows that the user can immediately get the resulting aliases on-demand for the userspecified analysis target after the preparation of Phase 1. Also, the result was fairly
precise in the sense that for our sample programs, 4.42 – 15.37 aliases were found dueto the instance-based approach, which is 32 – 63% less than the traditional class-based
analysis.
As an additional feature of JAAT, it can save internal syntactic and semantic information
as an external XML database, and restore the information, in order to improve reusabilityof analysis results. Also, JAAT provides useful Graphical User Interface (GUI), whichshows the resulting aliases using several visualization ways and helps the user’s program
debugging and understanding activities.
In Section II, we give a brief overview of an alias and its analysis for OO programs.
In Section III and Section IV, we propose an alias analysis method for OO programs.
In Section VI, we introduce an implementation of the proposed method and evaluate its
effectiveness using several sample programs. In Section VII, we discuss the evaluation
results with respect to related works and also describe an extension of our method to alias
analysis of pointer variables in C or C++. In Section VIII and Section IX, we conclude our
discussion with a few remarks and describe our future works. In the Appendix, a detailed
proposal of the alias analysis algorithm and its algorithm complexity are presented.
II. Preliminary
A. Example of Aliases
Alias analysis is useful for program debugging and program understanding. To give an
intuition of this, we present an example here. Fig. 1(a) shows a sample Java program andFig. 1(b) shows its execution outputs. This program computes the salaries of employee
Emp and manager Mng. The salary of the manager should be higher than the employee.
However, the program execution output is incorrect because a salary addition was madeDecember 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

5

to Emp. When the user recognizes such a fault, he/she computes the aliases for reference
variable Emp at line 32. In this paper, we call such a target expression of the alias analysis
the alias criterion (or simply criterion), and it is specified by a tuple <s, e>, where s isa statement in the source program and e is an expression at s. The shadow expressions
are the resulting aliases for <32, Emp> (which is also an alias itself, and therefore, boxedwith a bold line). We can see around those shadow expressions, and can identify a fault at
the salary addition statement at line 24. By modifying the statement e.add salary(200)to add salary(200) at line 24, the program will compute an expected result as shown in
Fig. 1(c).
B. Alias Analysis
Alias analysis methods are roughly divided into two categories, flow insensitive alias
analysis (FI analysis) and flow sensitive alias analysis (FS analysis).
B.1 Flow Insensitive Alias Analysis (FI Analysis)
In FI analysis, we do not take into account the execution order of each statement in thesource program[2], [22]. To compute FI aliases, we usually use an alias graph as shownin Fig. 2(b). An alias graph is an undirected graph, in which each node represents an
expression that refers to a particular memory location. Each edge represents a possible
alias relation between two nodes, which occurs on both sides of an assignment statement
and on the actual and formal parameters.
In Fig. 2(a), when we specify <7, c> as the alias criterion, we get aliases {a, b, newInteger(1), new Integer(2)}, which are all reachable nodes in the alias graph from thecriterion node.
B.2 Flow Sensitive Alias Analysis (FS Analysis)
In FS analysis, we consider the execution order of statements using a Reaching Aliasset (RAset)[16], [28]. A RAset for statement s, denoted by RA(s), is a collection of alias
sets, which possibly exists just before the execution of s. Each alias set is represented bya set of tuples (t, f ) (t is a statement in the source program and f is an expression at t).
Fig. 2(d) shows RAsets for each statement in Fig. 2(c). In order to compute the aliases

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

6

for <s, e>, we search RA(s) for an alias set that contains e.
At RA(7) in Fig. 2(d), since an alias set [(6, c), (2, a), (6, a), (2, new Integer(1))]
contains variable c, we get the result as shown in Fig. 2(c).
Since FS analysis considers the execution order, it generally requires a larger amountof CPU time and memory space than FI analysis; however, FS analysis can extract moreaccurate alias relations than FI analysis. In Fig. 2, we can see the difference in theaccuracy between the two methods. Previous works [18], [19], [20], [30] show empiricalcomparisons of these analyses. In this paper, we focus on FS analysis for more accurate
analysis results.
C. Alias Analysis for Object-Oriented Programs
Alias analysis methods for OO programs have been proposed as the extension of analysis
methods for procedural programs[16], [17], [22], [28], [30]; however, some issues still remain
to be solved for the implementation of practical alias analysis tools for OO programs. Here,we consider three issues, as follows:[a] Overall computation time for analysis
In order to implement a practical analysis tool, overall computation time is one of ourmain concerns. We have chosen relatively expensive FS approach, where all possible
method-call-paths should be analyzed to compute the RAset. When the target program
contains loops or recursive method calls, it should be analyzed until the increase of
the RAset ‘settles down’. In other words, when a RA(s) for statement s changes
during alias computation, we must re-compute the RAsets for all statements thatare possibly affected by RA(s). Thus, convergence and total computation time areimportant factors of the tool.
[b] Effective reuse of analysis results
The alias analysis tool should be used repeatedly with various alias criteria or withslightly distinct target programs. In such cases, we do not want to re-analyze theover all programs. In traditional FS alias analysis, RA(s) for statement s is computedby analyzing all statements in the source program that contain s along the execution
order. Therefore, when another statement t is modified, we might simply re-compute
December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

7

RA(s) for each statement s in the source program even if RA(s) is not affected by themodification of t. We are interested in finding an effective approach that re-computes
RAsets only affected by the modification.
[c] Improvement of analysis precision by separating each instanceIn OO programs, each object has its own state and behavior even if they are instantiatedfrom the same class. Fig. 3 shows part of a Java program that refers to attribute s ofobjects x and y. In this program, we prefer to have two independent alias sets [(3, x.s),(8, s)] and [(4, y.s), (8, s)]. However, if we apply a simple analysis approach such that
all objects instantiated from the same class share the inner alias information, we get
only one alias set [(3, x.s), (4, y.s), (8, s)] where (3, x.s) and (4, y.s) unwillingly fallin the same alias set. In order to increase the analysis precision, each object should
retain its inner alias relations separately; however, applying this notion to traditional
FS analysis methods would cause consumption of large memory space. We devise an
efficient approach.
III. Analysis Overview
A. Approach
To solve above the mentioned issues, we will adopt the following analysis policies.
Policy 1 Compute intra-module alias relations for each module such as class, method,and so on.
Policy 2 Compute inter-module alias relations on-demand.
Utilizing these two policies, modularity and independence of the analysis will be established. This is particularly important because in OO programming, we usually have toanalyze class libraries in addition to the developed codes. Those class libraries tend to belarge and their analysis cost also becomes large. Thus, the modularized analysis approachis essential.
In this paper, we divide alias relations into two categories, inner alias relation and outeralias relation. The followings are their definitions.
inner alias relation: alias relations that are common among all objects instantiated fromthe same class
December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

8

outer alias relation: alias relations that are not common among objects instantiatedfrom the same class
Outer alias relations are generated by external objects.
Policy 3 Distinguish outer alias relations on the objects instantiated from the sameclass, and analyze inner alias relations in advance, and compute outer alias relations
on-demand.
This policy holds for issue [c].
We also distinguish method invocation information for each instance. Such information
is named object context, which is used where computing outer alias relations for each
instance.
The object context for alias set A, denoted by OC(A), is a set of instance methods thatmight be invoked on the objects in A. This context is defined by the following process:
OC(A) := φ.
repeatWhen method m appears in expressions such asa.m(. . .) and a is in A,
OC(A) := OC(A) ∪ {m}.
When method m is an instance method of the objects
in A and its invocation appears in OC(A),OC(A) := OC(A) ∪ {m}.
until OC(A) is unchanged.

Using OC(A) when we compute the aliases for a.i on condition that a is in A, we canlimit the candidate methods to be considered further. In other words, we can exclude theinstance methods that can not be invoked in the objects referred to by expressions in A.1
We also consider two variants of object context, flow insensitive object context (FIOC)
and flow sensitive object context (FSOC). The former takes into account the method invo1

If we can not specify the unique A’s type, we might have more than one method; method overriding causessuch a situation.
December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

9cation order, whereas the latter does not. FSOC extracts more accurate alias information
than FIOC.
For example, suppose we compute the aliases for <13, return(i)> in Fig. 42 assuming that the underlined methods Calc::Calc(), Calc::add() and Calc::result() areinvoked in this order. Since Fig. 4(b) uses FSOC, it can generate more precise results
than Fig. 4(a) which uses FIOC. FSOC can exclude two expressions, i and new Integer
in Calc::Calc(), since we know that the definition of i at line 4 is always discarded atline 10.
FSOC requires more analysis cost than FIOC; on the other hand, FIOC might be lessprecise than FSOC. Therefore, we need to compromise between analysis cost and analysis
precision. In this paper, we use the FIOC approach.
Based on Policy 1 – 3 and object context, we propose the following two-phase approach.
Phase 1: Intra-module analysis in advance:(a) Construction of AFG (defined later) by intra-method analysis(b) Construction of MFG (defined later) by intra-class and inter-method analysis
Phase 2: Inter-module analysis on demand: Alias computation using AFG and MFG
along with object context
The details of this approach are discussed in Section IV.
B. Other Issues with OO Program Analysis
OO languages like Java, contain more features than traditional procedural languages.
We use the following approaches for each feature.
• Inheritance:

The inheritance concept causes other features such as method overriding and dynamic
binding. In addition, we must take virtual method invocation mechanisms into account, so that MFG construction algorithms consider the inheritance. The details of
our consideration will be shown later.
• Method overriding and Dynamic binding:2

Since return(x) and x always satisfy alias relations, we only show x as aliases in the figures.

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

10

Method overriding might generate two or more methods that have the same signature
in a class hierarchy. Since the determination of the invoking method depends on thereference-type of the object that receives a message, static identification of the actually
invoked method is difficult. This difficulty stems from the undecidable type of receiverobject without program execution; however, with alias analysis we can infer such atype more accurately.
For example, when we identify the invoking method of expression a.b(), we can use
the alias information of a in order to infer the reference-types of the instances thatmight be referred to by a.
• Thread and Exception:

Here, we do not deal with threads and exceptions. We concentrate on more generalcontrol flows such as loop statement, conditional statement and method call discussed
in Section VII.
IV. Details of Analysis
A. Phase 1: Construction of AFG and MFG
A.1 Phase 1(a): Construction of AFG
An alias flow graph (AFG) is an undirected graph, which shows FS alias relations insidea single method. A node represents either• an expression that refers to an object (e.g., a reference variable, an instance creation

expression, or a method invocation) or• parameters to/from a method or an instance.

The former node is called an AFG normal node and the latter is called an AFG special
node. We prepare special nodes as listed in TABLE I. An edge in AFG denotes an alias
relation immediately determined by the intra-method alias analysis. We call such an alias
relation a direct alias relation. Examples are aliases created by assignment statement,variable’s definition and its use (def-use relation), and assignment of parameters to/from
special nodes. Such aliases are easily obtained by RAset-based FS may-alias analysis
inside methods and classes[16], [28]. Also, a path formed with more than one edge shows
an indirect alias relation.

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

11

TABLE IAFG special node
Node

Description

Location

Actual-Alias-in (AA-in)

Alias passed by actual parameter to callee.

callerFormal-Alias-in (FA-in)

Alias passed by formal parameter to callee.

calleeActual-Alias-out (AA-out)

Alias passed by actual parameter to caller.

callerFormal-Alias-out (FA-out)

Alias passed by formal parameter to caller.

calleeMethod-Alias-out (MA-out)

Alias passed by return statement to caller.

calleeMethod-Invocation (MI)

Alias passed by return statement to caller.

caller(Parent node for AA-in(out) node)
Instance-Alias-in (IA-in)

Alias passed by instance attribute to method.

-

Instance-Alias-out (IA-out)

Alias passed by instance attribute from method.

-

Note that an expression specifying an attribute b (or a method b()) associated with an
instance a is denoted by a.b (or a.b()) in Java. In such a case, we say that the node fora in AFG is a parent of the node for b, and the node for b is called a child of the node
for a. Such a parent-child relationship is used for the alias computation in Phase 2. Also,
parent-child relationships between an MI node and its corresponding AA-in nodes exist.
A.2 Phase 1(b): Construction of MFG
A method flow graph (MFG) is a directed graph, which represents the caller-callee
relations of methods in a single class. An MFG node denotes the definition of each method,
and when a method A possibly calls a method B, an MFG edge is drawn from the nodefor A to the node for B.
The consideration of inheritance and method overriding concepts of methods are also
important. We have to make MFG while considering such concepts (this will be discussed
in Section V-A.2). Each MFG is constructed by the intra-class analysis of caller-callee
relations using class inheritance analysis.
B. Phase 2: Alias Computation Using AFG and MFG
We compute aliases A(X) for a reference-type expression X by AFG traversal. A(X)means a set of expressions that might refer to the same memory location as X. X is also
an element of A(X). Note that Fig. 5 includes some of the definitions of the symbols usedin this paper.
December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

12

We have adopted the following principles for alias computation using AFG:
1. When we compute the aliases for node C with a parent node P , first we compute P ’s
aliases A(P ), and then we collect information about A(P ), such as• types for A(P ) and• OC(A(P )),after which we compute C’s aliases.
There are many cases where we can not compute the aliases for C without A(P ) andtheir types. If we omitted P ’s alias computation, we would have had to consider that
P could refer to all the objects instantiated from the classes derived from P , so that
C’s alias result would be enlarged.
We have named this approach ‘parent-first-child-last approach’.
2. When we reach an MI, MA-out, an FA-in, FA-out, an AA-in or AA-out node during
AFG traversal, using MFG we determine the callee or caller method corresponding to
the node, and then we traverse from the corresponding MA-out, MI, AA-in, AA-out,
FA-in or FA-out node, respectively.
AFG is traversed on the whole program or several classes beyond the class boundary with
MFG information. When programs hold recursive method calls, AFG traversal continues
until the increase of the resulting aliases settles down. The details of the AFG traversal
algorithm and its termination are shown in Appendix I. The complexities of Phase 1 and
2 are shown in Appendix II.
V. Example
A. Phase 1: Construction of AFG and MFG
A.1 Phase 1(a): Construction of AFG
Fig. 6 shows a small Java program and its AFG. Nodes in AFG are shown as circles
with expressions inside, and edges are denoted with solid lines. Other strings out of those
nodes (e.g., Integer, =, Integer b, c;) are comments used to identify the occurrencesof expressions and to help the reader imagine the original source text. In Fig. 6(b), since
new Integer(0) is assigned to a in the source program, you can see that a node for new
Integer(0) is connected to node a with an edge. This edge represents a direct alias

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

13

relation.
Fig. 7 is a Java program with two class definitions, and its AFG. Variable i appearing
at each righthand-side expression (line 7 and 10) is a reference-type instance variable.
Thus, AFG special nodes IA-in[i] and IA-out[i] are employed for each method in class
Calc. Also, the expression for the return value, return(i), at line 13 is a reference to an
object. Therefore, an AFG special node MA-out is created for method Calc::result().
Also, b.result() at line 24 in Fig. 7(a) is represented in AFG with a parent node ϕ(b)and a child node ϕ(result()).
A.2 Phase 1(b): Construction of MFG
Fig. 8 shows a sample program and its MFG. Method p() is not defined in class B,
and method A::p() is executed when p() is activated on the B’s object. In this case,method call to q() appearing in A::p() causes activation of B::q(), not A::q(). Thus,
the resulting MFG for class B is as shown in Fig. 8(b).
Fig. 9 shows MFGs for class Calc and class Test shown in Fig. 7(a). Since neitherclasses do not have intra-class method calls, there is no MFG edge.
B. Phase 2: Alias Computation Using AFG and MFG
We show an alias computation process for <24, c> (boxed with a bold line) in Fig. 10,
which is the same as Fig. 7(a). Also, lower-case letters b and c represent expressions in
the program, and capital letters B and C represent nodes in AFG.
1. Start AFG traversal from AFG normal node ϕ(c), and immediately reach MI nodeϕ(result()) (Fig. 11).
2. Since ϕ(result()) has parent node ϕ(b), first compute b’s aliases to specify the object
related to result()’s aliases.
(a) Compute b’s aliases A(B).
(b) Compute the types of A(B) using class instance creation expressions included in
A(B). In this case, the type is determined to be Calc.
(c) Compute OC(A(B)). The result is {Calc::Calc(), Calc::add(int c), Calc::result()}.
3. Since alias computation for b indicates that it refers to the objects that are instantiatedfrom class Calc, traverse AFG from MA-out node in ψ(Calc::result()) (Fig. 12).
December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

14(a) Reach IA-in[i] in ψ(Calc::result()).
(b) Traverse AFG from IA-out[i] in {M | ψ −1 (M ) ∈ OC(this)( ≡ OC(A(B)))}.
Fig. 10 shows c’s aliases (masked) and OC(A(B)) (underlined). Since OC(A(B)) does
not contain Calc::inc(), expressions in Calc::inc() are excluded from the candidates
for c’s aliases.
VI. A Java Alias Analysis Tool (JAAT)
We have implemented the proposed method as a Java Alias Analysis Tool (JAAT).
Using JAAT, we have executed several programs and obtained data.
A. Overview of JAAT
JAAT consists of three subsystems, the analysis subsystem, the XML database subsystemand the User Interface (UI) subsystem. Fig. 13 shows the structure of JAAT. We will
overview each subsystem.
A.1 Analysis Subsystem
The analysis subsystem consists of three components: The syntax analyzer analyzes
Java source files and generate syntax trees3 . The semantic analyzer proceeds with asemantic analysis that creates symbol tables and extracts declare-refer relations among
identifiers and generates semantic trees. The alias analyzer that generates MFGs and
AFGs as Phase 1, and computes the aliases for the alias criterion specified by the user’s
request as Phase 2. The alias analyzer returns the resulting aliases to the UI subsystem.
A.2 XML Database Subsystem
Generated trees and graphs are proprietary data structures, and are placed into thememory space of JAAT, as are many other analysis tools[4], [25]. Since the translationfrom a source program to the corresponding semantic tree is a fairly time-consuming
process, we would not want to discard analysis results for the analysis sessions. Thus, webuild a database for semantic trees. This feature improves the reusability of the analysis
results along with the AFG/MFG approach.
3

The syntax analyzer is generated by ANTLR[9].

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

15

We use an eXtensible Markup Language (XML)[11] database that holds semantic tree
information. The XML converter 4 converts semantic trees to XML documents and viseversa. The XML database is a collection of XML documents, each of which represents one
Java class or interface. In order to keep the XML database compact, we do not preserve
source text information, such as line breaks, spaces and comments. The formatted source
text in Java can be re-generated by the application that we have also implemented. In
Section VII, we will discuss the effectiveness of the XML database with experimental
results and some XML applications.
A.3 UI Subsystem
The UI subsystem5 has two main functions, editing programs and visualizing the resulting aliases. When the user specifies an expression as an alias criterion, the UI subsystemsends a query to the analysis subsystem. It displays the analysis results on the text window (Fig. 14(a)). The text window shows the resulting aliases with colored backgrounds.
Statements without any aliases can be compressed on the screen with smaller fonts by theuser’s commands. The user can focus attention to the statements with aliases, and otherstatements, masked by the compressed display mode, can be easily enlarged and displayed
normally if required.
Fig. 14(b) is the alias tree window that shows the resulting aliases like a tree, on which
each node denotes class, method or expression. Since aliases tend to be found widely
in many methods or classes, the alias tree window enables the user to grasp the overall
distribution. In Fig. 14(b), two alias trees (left tile) for two alias criteria are shown, on
which the resulting alias trees are spread from Alias[0] and Alias[1] nodes, respectively.
When clicking a node, the user can see the information (right tile) about that node.
B. Evaluation
In order to explore the applicability of JAAT, we have applied it to various sample
programs. TABLE II shows features of the sample programs. Note that we must analyze
not only these sample programs but also all related classes in JDK for inter-method alias
4
5

The XML converter uses libxml[13] as an XML parser.
The UI subsystem uses Gtk−− tool kit[8].

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

16

TABLE II
characteristics of analyzed programs
Programs

Sample Program

Related Classes in JDK

Number of Files

Number of Lines

Number of Files

Number of Lines

TextEditor

1(0.1%)

915(0.8%)802(99.9%)

114,887(99.2%)

WeirdX (X server)

47(5.5%)

16,703(12.6%)815(94.5%)

115,977(87.4%)

ANTLR (Parser Generator[9])129(32.6%)

18,775(35.7%)267(67.4%)

33,847(64.3%)

DynamicJava (Java Interpreter)242(22.7%)

32,037(21.1%)825(77.3%)

119,564(78.9%)

analysis. For example, TextEditor is composed of one file 915 lines long. TextEditor
directly and indirectly uses the classes in JDK, which is in 802 files with a total of 114,887
lines (99.2% of the overall total lines). This data shows that a heavy effort on analysis
must be done for the related classes.
B.1 Computation Time of Phase 1(a)Our modularized analysis is effective in that we only have to re-analyze modified partsof the programs when small parts of the program are modified. On the other hand, theRAset-based analysis[16], [28] can not retain analysis results for each module separately;
therefore, the overall program might have to be re-analyzed. Although user-development
programs are often modified when developing a Java program, their related classes are
seldom modified.
TABLE III(a) shows AFG construction time for sample programs and their relatedclasses. The analysis time for its related classes is much longer than for those of thesample programs. For example, TextEditor itself requires only 100 milli seconds, and its
related classes require 99,980 milli seconds. When we modify TextEditor, we do not needto re-analyze its related classes, but only the TextEditor.
B.2 Computation Time of Phase 1(b)TABLE III(b) shows MFG construction time for sample programs and their relatedclasses. Since MFG construction time does not depend on the programs size, but on thenumber of intra-class method calls, the MFG construction time of the sample program
is not always longer than that of its related classes. For example, DynamicJava itself

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

17

TABLE IIIexperimental results
Programs

Sample Program

TextEditor

Related Classes in JDK

100

99,980WeirdX

14,220100,540

ANTLR

12,83023,480

DynamicJava

56,260110,150(a) computation time of Phase 1(a) [ms]Programs

Sample Program

Related Classes in JDKPrograms

Average

TextEditor
WeirdX

10390

TextEditor

0.65

20

390

WeirdX

0.29

ANTLR

100

80

ANTLR

0.17

DynamicJava

960

450

DynamicJava

0.07(b) computation time of Phase 1(b) [ms](c) computation time of
Phase 2 [ms]Programs

Instance-based

Class-based

TextEditor

4.42

8.31

WeirdX

15.37

24.54

ANTLR

5.94

18.77

DynamicJava

9.16

17.19

(d) average number of detected aliases [nodes]— PentiumIII-667MHz-512MB(Debian GNU/Linux)

requires 960 milli seconds, but its related classes require only 450 milli seconds. However,
the overall MFG construction time is much smaller than the AFG construction time.
B.3 Computation Time of Phase 2
TABLE III(b) shows average AFG traversal time for all AFG normal nodes in eachsample program. According to TABLE III(b), it is clear that Phase 2 takes much lesscomputation time than Phase 1. In the case of TextEditor, 0.65 milli seconds is muchsmaller than the AFG construction time (100,080 milli seconds = 100 milli seconds +99,980 milli seconds) for TextEditor and its related classes.
Our on-demand approach might be unsuitable as back-end for data-flow analysis andcompiler optimization which needs whole alias analysis results. However, when we do

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

18

TABLE IV
comparison between Java source files and the XML database in construction of thesemantic tree
From

Construction time[s]Data Size[MB]Java source files

37

25

XML database24

62

not need to compute the aliases for all expressions, or when we implement an interactive
programming support tool with alias analysis features, our method is a practical choice.
B.4 Average Number of Detected Aliases
The proposed method uses the instance-based approach that can distinguish outer alias
relations on objects instantiated from the same class. On the other hand, if we use theclass-based approach that shares outer alias relations with other objects instantiated fromthe same class, analysis precision will decrease. Traditional alias analysis methods are notconcerned with the instance-based approach, but only with the class-based approach.
TABLE III(c) shows the comparison results between those two approaches with regard to
the average number of detected aliases for all AFG normal nodes in each sample program.
For example, the instance-based approach generates more accurate results than the classbased approach (4.42 nodes v.s. 8.31 nodes) in TextEditor. The average size of aliases isabout 32 – 63% of the class-based approach; therefore, our approach is of practical value.
B.5 Effects of The XML Database
Since the XML database is a text-based database, it requires higher analysis costs thanin a proprietary database. However, we think that the reusability of the data by the XML
database is important. As mentioned in Section VI, since there are many programs andlibraries that can deal with XML documents, we can easily implement XML applications
for program debugging and understanding activities that access the XML database. The
advantages of the XML database are as follows:• Decreased analysis costs

The implemented XML database holds semantic tree information. In order to evaluate
its effectiveness, we have compared the XML database and the Java source files from
December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

19

the viewpoints of time and space.
We have used all source codes for the JDK 1.3 class library. The XML database forsemantic trees took 45.6 seconds to be generated.
We compared the construction time for all semantic trees from the XML database and
the Java source files, and compared disk space to store them as shown in TABLE IV.
It took 37 seconds to construct semantic trees from the Java source files and only 24
seconds to construct the trees from the XML database. While the data size became
large, the improvement of the construction was satisfactory.
• Rapid development of applications

We have implemented three XML applications (see Fig. 13):
– XML-HTML converter (2000 lines in eXtensible Stylesheet Language Transformations (XSLT)[12]),– XML-Java converter (2000 lines in XSLT, 1500 lines in C++) and– XML-XML converter (identifier replacement program, 600 lines in XSLT).
Fig. 15 shows the result of applying the XML-HTML converter. We can see theJava source text with HTML tags that are generated from the XML representationof class java.lang.ClassLoader. Using WWW browsers, we can also traverse thedeclaration-reference chains for identifiers (these chains are represented by links) suchas types and methods and variables.
VII. Discussion
Our proposed method for alias computation, which consists of two analysis phases,
has produced effective results, and problems with the alias analysis of OO programs are
sufficiently resolved.
In this section, we compare our results and related works, and also show an extensionof our method to programs with pointer variables in ordinary languages.
A. Comparison with Related Works
In this section, we discuss our work and related works from several viewpoints.

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

20

A.1 Two-phase Approach
Several prior research studies also analyze each module in advance[17], [27]. However, inthese studies, each element A (alias relation) in an RAset holds conditions if a specific alias
relation A0 really exists (if true, A exists). These conditions are used for indirect alias
relations; however, all combinations of accessible variables should be taken into account ascandidates for A0 . In our method, since each AFG edge represents a direct alias relation,
we can easily extract each indirect alias relation as an AFG path.
Such conditional-based algorithms used in [17], [27] would be suitable as back-end fordata-flow analysis (e.g., program slicing), which needs whole alias relations in target programs. Since we focus mainly on program debugging and understanding activities using
alias information itself, more simple representation is useful. On the other hand, since
our AFG traversal algorithm is designed in order to compute the aliases for single alias
criterion specified by the user, it is unsuitable for data-flow analysis (however, we will beable to define new AFG traversal algorithm for computing whole alias relations in target
programs if need).
Also, [17] focuses on ordinary procedural languages only, and [27] is not applied to aliases
with pointers, where both methods have been implemented as prototype tools only.
A.2 Instance-based Analysis
The instance-based approach was proposed in Object slicing, which is a slice extraction
method for OO programs[5]. [5] extends the System Dependence Graph (SDG) and defines
the traversal algorithm to compute slices with regard to a specific object; however, [5]assumes that the pointer or alias analysis have been already performed by another method.
To get a practical alias analysis tool, combining an alias analysis method and the instanceseparation method into a single method is very important, as we have proposed here.
A.3 On-demand Alias Extraction
We applied an on-demand approach to alias analysis. Although alias information has
been used for other analyses such as compiler optimization, data-flow analysis and soon[1], [2], [16], [22], [24], [28], alias information is itself useful for program debugging andunderstanding of Java programs, because, in general, Java programs have many aliases,
December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

21

which are caused by reference-type expressions.
Since all alias information in the target program is not necessary on program debugging
and understanding activities, we believe on-demand (or query-based) analysis will be acost-effective approach.
A.4 Extensibility of The Algorithm
In Section II, we introduced FS analysis and FI analysis. In general, their algorithms
are different, and are implemented independently; the former uses RAsets, the latter uses
point-to or alias graphs. Since each analysis has merits and demerits on analysis costs andanalysis precision, we think that practical alias analysis tools should be implemented withboth methods. In order to compare various alias analysis methods, many prototype tools
have been implemented[18], [19], [20], [30]. Since those tools are for prototypes, changing
and extending analysis algorithms are not considered.
Using our AFG-based alias analysis approach, we can share intra-method analysis results with several alias analysis algorithms. Each AFG holds intra-method FS alias analysis results for its corresponding method. Although FS analysis requires much larger
computation time than FI analysis, intra-method analysis is generally more effective thaninter-method analysis; applying FS policy to the intra-method alias analysis would be apractical choice.
Since various alias analysis methods can be described in the form of the AFG traversal
algorithm, we can compromise between analysis cost and precision by changing traversal
algorithms. FSOC and FIOC are examples of this approach. So are instance-based andclass-based algorithms (their comparison results were shown in TABLE III(c)).
Currently, the AFG traversal algorithm in Appendix I does not completely satisfy FS
due to the FIOC approach. In order to apply FSOC, flow directions should be represented
using direct edges.
Since distinguishing may-alias relations and must-alias relations is effective for more precise analysis results, applying this approach to AFG construction and traversal algorithms
would be more powerful by its flexible mechanism on algorithm selection.

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

22

A.5 XML Database
JavaML also describes semantic tree information using XML[10]. [10]’s approach resembles our XML database. However, since JavaML considers only intra-class declarationreference relations about identifiers, we are afraid that JavaML can not restore semantic
trees from generated XML documents. Since our generated XML documents can take into
account both inter-class and intra-class declaration-reference relations, semantic trees canbe easily restored from XML documents.
A.6 Thread and Exception
Since FS analysis considers the execution order of statements, its analysis precision
depends on the precision of control-flow information. Thus, if we can collect more precise
control-flow information, FS analysis results should become more precise.
Currently, since JAAT’s control-flow representation does not consider the control-flows
caused by threads and exceptions, its resulting aliases will become imprecise with theprograms that contain threads and exceptions. However, since many researchers havealready proposed control-flow analysis methods for thread and exception[15], [29], we
will be able to adopt the algorithms in [15], [29] to construct the improved control-flow
representation that takes thread and exception into account.
B. Alias Analysis for Pointer Variables
In Section IV, we have described an alias analysis method for reference-type expressions
in Java. This method has been also extended to the alias analysis of ordinary procedural
programs with pointer variables such as C or C++. In such a case, we need special
consideration of indirect reference by pointers (especially, higher-order pointers) because
a callee can modify its caller’s alias relations using n-order (n ≥ 2) pointer variables evenif parameter passing uses a passed-by-value mechanism. The following are the core partsof the extension.
B.1 Phase 1(a): Construction of AFG
We prepare n AFG nodes for each n-order pointer variable. Fig. 16 shows a C program
and the direct alias relations (i.e, the AFG edge and each element denotes an AFG node)
December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

23

extracted from the program. Since procedure assign(char **y, char *x) uses a secondorder pointer variable y as the first parameter, we prepare the following nodes:• AA-in[&b] and AA-in[b] for actual parameter b in procedure main()• FA-in[y] and FA-in[*y] for formal parameter y in procedure assign(char**y, char*x)
In addition to AA-in and FA-in nodes, we add the corresponding AA-out and FA-out
nodes, respectively.
B.2 Phase 2: Alias Computation using AFG and MFG
There are two operators for pointer variables – indirect operator ‘∗’ and address operator‘&’. Expression ∗x represents the value in the memory location to which x refers, andexpression &x represents x’s memory location. To adapt the alias computation algorithm
to these operators, we have also applied the parent-first-child-last approach to them. For
example, when we compute the aliases for ∗a, first we compute the aliases for a. The
details of the AFG traverse algorithm for ‘∗’ and ‘&’ will be represented in Fig. 17 as[Cond.8] and [Cond.9] at Step 2.
VIII. Conclusions
We have proposed an alias analysis method for OO programs, which is a scalable andon-demand method with high precision and extensibility. Also, we have implemented thismethod as JAAT, and evaluated its effectiveness. JAAT consists of three subsystems, theanalysis subsystem, the XML database subsystem, and the UI subsystem. The analysis
subsystem can analyze large programs such as a JDK class library. We can save semantic
tree information to the XML database to decrease the analysis cost and improve reusabilityof the analysis results.
IX. Future Research
We plan to implement the FSOC approach, and compare this approach with the existing
FIOC approach. In addition, we also plan to extend our AFG construction and AFG
traversal algorithms for exceptions and threads.

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

24

Appendix
I. AFG Traversal Algorithm
In this section, we will describe the AFG traversal algorithm in Phase 2. Phase 2 is themost important phase for our AFG-based alias analysis because we use query-based alias
computation, and we can control the analysis cost and precision by changing the AFG
traversal algorithm.
Fig. 17 shows the AFG traversal algorithm used in JAAT. The algorithm uses the FIOC
and FS may-alias approaches.
In Step 1, we identify AFG node E for e that is specified by the user as an alias criterion.
In Step 2, we start AFG traversal from E where we find reachable nodes in AFG from
E. This step requires not only simply traversing AFG edges but also additional processes.
Traversing AFG edges is only for intra-method alias relations identified in Phase 1(a);thus, more complicated alias relations such as inter-method or outer alias relations haveto be identified here. We perform the following processes according to the classification ofnodes during the AFG traversal.
If we arrive at AFG node C on the traversal, we do the following based on the nodetype of C.
1. C is an AFG normal node that has parent node P :Compute P ’s aliases A(P ) by applying Step 2 recursively to P , and infer A(P )’stypes from the instance creation expressions in A(P ). Next, compute OC(A(P )).
If C’s corresponding expression c is an instance variable, traverse AFG from IAin[c] and IA-out[c] nodes held by OC(A(P ))’s corresponding methods, and traverse
AFG from the nodes (here, we define each node as N ) that satisfy all the following
conditions:• N ’s corresponding expression is an instance variable named c, and• N ’s parent node is in A(P ).

2. C is a MI node that has parent node P :Compute P ’s aliases A(P ), infer A(P )’s type, and compute OC(A(P )). Next,
traverse AFG from MA-out nodes whose corresponding methods are in OC(A(P ))and their signatures are the same as that of C’s corresponding method invocation
December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

25

expression.
3. C is an IA-in[c] or IA-out[c]:Traverse AFG from IA-out[c] or IA-in[c] held by OC(this)’s corresponding AFGs.
OC(this) means the object context for the currently focused instance (i.e, thisobject). If an alias criterion is in this object, OC(this) is initialized as a set of
constructors and methods that are directly or indirectly called from the constructors. Otherwise, OC(this) is initialized with OC(A(P )) (A(P ) is an alias set thatrefer to the instances that have c as an instance variable).
This process is for the instance-based approach.
For example, suppose that we have reached IA-in[b] or IA-out[b] computing thealiases for a.b. After finishing the alias computation for a, we begin alias computation for b using information about a’s type and OC(a). When a’s type is A, thealias computation for IA-out[b] or IA-in[b] is proceeded under OC(this)(≡ OC(a))
in class A. If we can not determine the unique A(a)’s type, we should traverse
AFG in two or more classes inferred from A(a).
4. C is an AA-in[c] or AA-out[c] that has parent node P :Traverse AFG from FA-in[c] or FA-out[c] whose corresponding methods are calledby MI node P .
When P has parent node Q, we will apply a dynamic binding policy to the alias
computation for P . Thus, P ’s invoked methods are determined by Q’s type, i.e,
Q’s alias analysis results.
5. C is an FA-in[c] or FA-out[c]:Suppose that method mB is a method that has formal parameter c. First, collectmethods mA that are in OC(this) and calls mB , using MFG. Next, traverse AFG
from AA-in[c] or AA-out[c] in mA ’s corresponding AFGs.
6. C is an MA-out node:Suppose that method mB is a method that has C’s corresponding return expression. First, collect methods mA that are in OC(this) and calls mB , using MFG.
Next, traverse AFG from MI nodes in mA ’s corresponding AFGs.
7. C is an MI node:

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

26

TABLE Velements of AFG-based alias analysis
SymbolDescription

A

Maximum number of attributes in each class(inherited attributes are also counted)

M

Maximum number of methods in each class(inherited methods are also counted)

L

Maximum number of sum of local variables and parameters in a method

C

Total number of classes in the target program

E

Total number of expressions in the target programk

Maximum length of parent-child chains(when a chain forms a recursive loop, we do not count the previously visited expressions)First, extract methods mA that are in OC(this) and are called by C. Next, traverse
AFG from the MA-out nodes in mA ’s corresponding AFGs.
In our AFG traversal algorithm, we applied the following rules to detect its termination.
• When AFG traversal reaches node N0 to compute the aliases for c, we record N0 to

RNlist(c); RNlist(c) represents reached nodes list (RNlist) for c.
• When the AFG traversal reaches the nodes in the RNlist again, we no longer traverse

AFG.
• A RNlist is created for each alias set that may refer to the same memory location. For

example, when a.b is an alias criterion, RNlist(a) and RNlist(b) is created.
• Suppose that a.b.c is an alias criterion and we have reached node N1

on the alias

computation for a. When we check if N1 is in RNlist(a), we should also check if N1 ∈RNlist(b) and check if N1 ∈ RNlist(c), respectively.
Since the size of each RNlist is less than E and the number of the RNlist is less than k(the maximum length of the parent-child chain), we can prevent creating RNlists infinitely
so that AFG traversal must terminate.
II. Algorithm Complexity
We discuss algorithm complexity for each phase.
TABLE V shows the elements of AFG-based alias analysis.
• Phase 1(a): Construction of AFG

When the target program has loop statements, we must analyze expressions at
most E 2 times. In order to analyze each expression, two or three set operations
December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

27

are needed. Since set operation cost is proportional to the number of elementsin the target set, the time complexity of set operation is covered with O(A + L).
Thus, in the worst case, the time complexity is O((A + L) · E 2 ). The number of
AFG nodes is O(E) and the number of AFG edges is O(E 2 ). The space complexity
is O(E 2 ) in the worst case.
In our experimentation, both the time complexity and the space complexity werenear liner order.
• Phase 1(b): Construction of MFG

One MFG is constructed for each class. Since we must check each expression oncein order to find method calls, the time complexity is O(E). Since the number ofmethods in a class is less than M , the number of MFG nodes is O(C · M ), and thenumber of MFG edges is O(C · M 2 ). Thus, the space complexity is O(C · M 2 ) in
the worst case.
Also, the complexity was near liner order in our experimentation.
• Phase 2: Alias Computation using AFG and MFG

Since we use the instance-based approach, we must also compute the aliases forparent nodes, recursively.
In the worst case, the time complexity and the space complexity are both O(E k );however, such a case is quite rare. In our experimentation, k’s values were 2 or 3
on average.
References[1] A. V. Aho, S. Sethi and J. D. Ullman, Compilers : Principles, Techniques, and Tools, Addison-Weseley, 1986.
[2] B. Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT
symposium on Principles of programming languages, Pages 32–41, 1996, St. Petersburg Beach, Florida, USA.
[3] B. Stroustrup, The C++ Programming Language(Third edition), Addison-Wesley, 1997.
[4] D. C. Atkison and W. G. Griswold, The Design of Whole-Program Analysis Tools, Proceedings of the 18th
International Conference on Software Engineering, Pages 16–27, 1996, Berlin, Germany.
[5] D. Liang, and M. J. Harrold, Slicing Objects Using System Dependence Graphs, Proceedings of the International
Conference on Software Maintenance, pp.358–367, 1998, Washington, D.C., USA.
[6] F. Ohata, and K. Inoue, Alias analysis for object-oriented programs, Technical Report on IPSJ-SIGSE-126,
Vol.2000, No.25, 2000-SE-126, pp.57-64 (in Japanese).
[7] G. Booch, Object-Oriented Design with Application, The Benjamin/Cummings Publishing Company, Inc,
1991.

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

28[8] http://gtkmm.sourceforge.net/, Gtk−−.
[9] http://www.ANTLR.org/, ANTLR Website.
[10] G. J. Badros, JavaML: A Markup Language for Java Source Code Computer Networks, Vol.33, No.1-6,
pp.159–177, 2000.
[11] http://www.w3c.org/XML/, Extensible Markup Language(XML).
[12] http://www.w3.org/TR/1999/WD-xslt-19990421, XSL Transformations (XSLT) Specification.
[13] http://xmlsoft.org/, The XML C library for Gnome.
[14] J. Gosling, B. Joy, and G. Steele, The JavaTM Language Specification, Addison-Weseley, 1996.
[15] J. Zhao, Slicing Concurrent Java Programs, Proceedings of the 7th IEEE International Workshop on Program
Comprehension, Pages 126–133, 1999, Pittsburgh, Pennsylvania, USA.
[16] M. Enami, R. Ghiya, and L. J. Hendren, Context-sensitive interprocedural points-to analysis in the presenceof function pointers, Proceedings of the ACM SIGPLAN’94 Conference on Programming Language Design
and Implementation, Pages 242–256, 1994, Orlando, Florida, USA.
[17] M. J. Harrold and G. Rothermel, Separate Computation of Alias Information for Reuse, IEEE Transactions
on Software Engineering, Special section of best papers of the 1996 International Symposium on Software
Testing and Analysis, Vol. 22, No. 7, Pages 442–460, 1996.
[18] M. Hind, and A. Pioli, An empirical comparison of interprocedural pointer alias analysis, IBM Research
Report, #21058, 1997.
[19] M. Hind, and A. Pioli, Assessing the Effects of Flow-Sensitivity on Pointer Alias Analysis, IBM Research
Report, #21251, 1998.
[20] M. Hind, and A. Pioli, Which Pointer Analysis Should I Use?, Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis, Pages –, 2000, Portland, Oregon.
[21] M. Hind, Pointer Analysis: Haven’t We Solved This Problem Yet?, Proceedings of the ACM SIGPLANSIGSOFT Workshop on Program Analysis for Software Tools and Engineering, Pages 54 – 61, 2001, Snowbird,
Utah.
[22] M. Shapiro, and S. Horwitz, Fast and accurate flow-insensitive point-to analysis, Proceedings of the 24th ACM
SIGPLAN-SIGACT symposium on Principles of programming languages, Pages 1–14, 1997, Paris, France.
[23] M. Weiser, Program slicing, Proceedings of the 5th International Conference on Software Engineering, Pages
439–449, 1981, San Diego, California, USA.
[24] P. Tonella, G. Antoniol, R. Fiutem, and E. Merlo, Flow insensitive C++ pointers and polymorphism analysis
and its application to slicing, Proceedings of the 19th International Conference on Software Engineering, Pages
433–443, 1997, Boston, Massachusetts, USA.
[25] The Wisconsin Program-Slicing Tool 1.0, Reference Manual, Computer Sciences Department, University of
Wisconsin-Madison, 1997.
[26] T. Kamiya, F. Ohata, K. Kondo, S. Kusumoto, and K. Inoue, Maintenance support tools for Java programs:
CCFinder and JAAT, Proceedings of the 5th International Conference on Software Engineering, Pages 837–838,
Formal Research Demonstrations, 2001, Toronto, Canada.
[27] R. K. Chatterjee and B. G. Ryder, Modular Concrete Type-Inference for Statically Typed Object-Oriented
Programming Languages, Department of Computer Science, Rutgers University, no. DCS-TR-349, 1997.
[28] R. P. Wilson, and M. S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the
ACM SIGPLAN’95 Conference on Programming Language Design and Implementation, Pages 1–12, 1995, La
Jolla, California, USA.

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

29[29] S. Sinha, and M. J. Harrold, Analysis of Programs With Exception-Handling Constructs, Proceedings of theInternational Conference on Software Maintenance, Pages 358–367, 1998, Washington, D.C., USA.
[30] S. Zhang, B. G. Ryder, and W. A. Landi, Experiments with Combined Analysis for Pointer Aliasing, Proceedings of the SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, Pages
11–18, 1998, Montreal, Canada.

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

1:

30class Employee {2:String name; int salary; Employee supervisor;

3:

Employee(String n, int s) {4:

name = n;5:salary = s;6:supervisor = null;

7:

}

8:

void add salary(int n) {9:salary += n;

10:

}

11:

void set supervisor(Employee e) {12:supervisor = e;

13:

}

14:

void print() {15:

System.out.println(name + ” Salary:” + salary);

16:

}

17: }
18: class Manager extends Employee {19:Manager(String n, int s) {20:

super(n, s);

21:

}

22:

void manage(Employee e) {23:

e.set supervisor(this);

24:

e.add salary(200);

25:

}

26: }
27: class Office {28:

public static void main(String args[]) {29:

Employee Emp = new Employee(”Emp”, 750);

30:Manager Mng = new Manager(”Mng”, 750);

31:

B.manage(Emp);

32:

Emp.print();

33:

Mng.print();

34:

}

35: }

(a) source program(b)
December 27, 2001

% java Office% java Office

Emp Salary: 950

Emp Salary: 750

Mng Salary: 750

Mng Salary: 950

program(with error)

execution(c)program(without error)

Fig. 1. example of alias

execution
DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

1: Integer a, b, c;

31

1: Integer a, b, c;

2: a = new Integer(1);2: a = new Integer(1);3: b = new Integer(2);3: b = new Integer(2);4: c = b;

4: c = b;

5: System.out.println(c);5: System.out.println(c);6: c = a;

6: c = a;

7: System.out.println(c);new Integer(1)(a) FI alias analysis

a

c

b

new Integer(2)7: System.out.println(c);(b) alias graph(c) FS alias analysis

St.(s)

Reaching alias set(RA(s))

1

φ

2

φ

3

{[(2, a), (2, new Integer(1))]}

4{[(2, a), (2, new Integer(1))], [(3, b), (3, new Integer(2))]}5{[(2, a), (2, new Integer(1))], [(4, c), (3, b), (4, b), (3, new Integer(2))]}

6{[(2, a), (2, new Integer(1)), [(4, c), (5, c), (3, b), (4, b), (3, new Integer(2))]}

7{[(6, c), (2, a), (6, a), (2, new Integer(1))], [(3, b), (4, b), (3, new Integer(2))]}(d) reaching alias set (RAset)

Fig. 2. FI alias analysis and FS alias analysis

1:

x = new A;

5:class A {2:

y = new A;

6:Integer s;3:x.s = . . . ;7:. . . (. . . ) {4:

y.s = . . . ;8:. . . = s;Fig. 3. aliases without instance separation

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

1:

public class Calc {1:

public class Calc {2:Integer i;2:Integer i;3:public Calc() {3:public Calc() {4:4:i = new Integer(0);

5:

}

6:

public void inc() {7:i = new Integer(i.intValue() + 1);

i = new Integer(0);

5:

}

6:

public void inc() {7:i = new Integer(i.intValue() + 1);

8:

}

8:

}

9:

public void add(int c) {9:public void add(int c) {10:

i = new Integer(i.intValue() + c);

10:

i = new Integer(i.intValue() + c);

11:

}

11:

}

12:

public Integer result() {12:public Integer result() {

13:
14:

return(i);

13:

}

32

14:

return(i);
}

15: }

15: }

(a) flow insensitive object context (FIOC)(b) flow sensitive object context (FSOC)

Fig. 4. example of object context

ϕ(x): mapping from expression x to its corresponding AFG node
ϕ−1 (X): mapping from AFG node X to its corresponding expression
A(X): aliases for AFG node X
NP (X): a parent AFG node for AFG node X
ψ(m): mapping from method m to its corresponding AFG
ψ −1 (M ): mapping from AFG M to its corresponding method
e =id e0 : true when e and e0 are the same identifiers, otherwise false
Fig. 5. definition of symbols

1:

Integer a = new Integer(0);2:Integer b, c;Integer b, c;3:

b = a;

b = a ;

4:c = b;

c = b ;(a) source program

Integer a = new Integer (0);(b) AFG

Fig. 6. sample program and its AFG (1)December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

1:

33

public class Calc {2:Integer i;3:public Calc() {4:i = new Integer(0);

5:

}

6:

public void inc() {7:i = new Integer

16: class Test {(i.intValue() + 1);

17:

Calc a, b;

8:

}

18:

Integer c;

9:public void add(int c) {19:

Test() {10:

i = new Integer(i.intValue() + c);

20:

a = new Calc();

21:b = new Calc();

11:

}

22:

a.inc();

12:

public Integer result() {23:b.add(1);24:c = b.result();

13:
14:

return(i);
}

25:

15: }

}

26: }

(a) source program
public class Calc
Integer i;public Calc() IA-in[i]public void inc() IA-in[i]i = new Integer(0);i = new Integer(i.intValue() + 1);

IA-out[i]IA-out[i]public void add(int c) IA-in[i]i = new Integer (i.intValue() + c);
IA-out[i]public Integer result() IA-in[i]return (i);MA-outIA-out[i]class Test
Calc a ; Calc b ; Integer c ;Test() IA-in[a]IA-in[b]IA-in[c]a = new Calc();b = new Calc();a.inc();

b.add(1);IA-out[a]IA-out[b]c = b.result ();IA-out[c](b) AFG

Fig. 7. sample program and its AFG (2)December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

1:

34class A {2:

void p() { q(); }6:class B extends A {3:void q() { r(); }7:void q() { s(); }4:void r() { }8:void s() { }

5:

}

9:

A::p()

A::q()

A::r()}

A::p()(a) class A

B::q()

B::s()

A::r()(b) class B

Fig. 8. sample program and its MFG

Calc::Calc()

Calc::inc()Calc::add()

Calc::result()(a) class Calc

Test::Test()(b) class Test

Fig. 9. MFGs for Fig. 7(a)1:public class Calc {16: class Test {2:Integer i;

17:

Calc a, b;

3:

public Calc() {18:

Integer c;19:

Test() {4:

i = new Integer(0);

5:

}

20:

a = new Calc();

6:
7:

public void inc() {21:b = new Calc();

i = new Integer

22:a.inc();

23:b.add(1);24:c = b.result();(i.intValue() + 1);
8:

}

9:

public void add(int c) {10:

i = new Integer

25:

}

26: }

(i.intValue() + c);
11:

}

12:

public Integer result() {

13:
14:

return(i);
}

15: }

Fig. 10. alias set for <24, c> (masked expressions are aliases)

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

35

class Test
Calc a ; Calc b ; Integer c ;Test() IA-in[a]IA-in[b]IA-in[c]a = new Calc();b = new Calc();a.inc();

b.add(1);IA-out[a]IA-out[b]c = b.result ();IA-out[c]Fig. 11. alias set for <24, b> in Fig.10 (masked expressions are aliases)
public class Calc
Integer i;public Calc() IA-in[i]public void inc() IA-in[i]i = new Integer(0);i = new Integer(i.intValue() + 1);

IA-out[i]IA-out[i]public void add(int c) IA-in[i]i = new Integer (i.intValue() + c);
IA-out[i]public Integer result() IA-in[i]return (i);MA-outIA-out[i]Fig. 12. alias set for <24, result()> in Fig.10 (masked expressions are aliases)[UI subsystem]

User

GUI

[Analysis subsystem]

Syntaxanalyzer
Source file

Semantic
analyzer
Parse tree

Alias
analyzer
Semantic tree

MFG

AFG

[XML database subsystem]

Semantic tree-XML
converter
XML-HTML
converter
Source text with HTML tags

XML-Java
converter
User
Source file

XML-XML
converter
XML database

Fig. 13. JAAT (structure)

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

36(a) text window(b) alias tree window

Fig. 14. JAAT (UI)

Fig. 15. HTML representation of Java source file

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

37[(3, &c), (3, a)][(3, a), (4, a)]void main() {[(1, b), (4, b)]1:char *a, *b;[(4, &b), (4, AA-in[y])]2:char c = ’ ’;[(4, b), (4, AA-in[*y])]3:

a = &c;[(4, a), (4, AA-in[x])]4:assign(&b, a);[(4, AA-out[*y]), (4, b)]5:putc(*b);[(4, b), (5, b)]}[(6, FA-in[y]), (7, y)]
6: void assign(char **y,[(6, FA-in[*y]), (7, *y)]char *x) {[(6, FA-in[x]), (7, x)]7:*y = x;[(7, x), (7, *y)]}[(7, *y), (6, FA-out[*y])](a) sample C program(b) extracted direct alias
relationsFig. 16. alias analysis for programs with pointer variables

December 27, 2001

DRAFT

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. XX, NO. Y, MONTH 200X

38

Step 1: Specify an alias criterion e (E := ϕ(e)).
Step 2: Start AFG traversal from E.
When we traverse AFG, we perform following processes at each reachable node C:[Cond.1] C is an AFG normal node that has a parent node:
1. c := ϕ−1 (C), P := NP (C)
2. Compute P ’s aliases A(P ).
3. Compute A(P )’s type using class instance creation expressions included in A(P )4. Compute OC(A(P )).
5. Traverse AFG from IA-in[c] and IA-out[c] nodes in {GM | ψ −1 (GM ) ∈ OC(A(P ))}, andTraverse AFG from {N | NP (N ) ∈ A(P ) and ϕ−1 (N ) =id c}.
[Cond.2] C is an MI node that has a parent node:
1. c := ϕ−1 (C), P := NP (C)
2. Compute P ’s aliases A(P ).
3. Compute A(P )’s type using class instance creation expressions included in A(P ).
4. Compute OC(A(P )).
5. Traverse AFG from MA-out nodes in {M | ψ −1 (M ) ∈ OC(A(P ))}.
[Cond.3] C is an IA-in or IA-out node:
1. c := ϕ−1 (C)
2. Traverse AFG from IA-out[c] or IA-in[c] in {M | ψ −1 (M ) ∈ OC(this)}.
[Cond.4] C is an AA-in or AA-out node:
1. Compute method m that MI node NP (C) calls.
2. Traverse AFG from the corresponding FA-in or FA-out node in ψ(m).
[Cond.5] C is an FA-in or FA-out node:
1. MB := {M | C ∈ M }, mB := ψ −1 (MB )2. mA := {m | m ∈ OC(this) and m calls mB } (using MFG)
3. MA := ψ(mA )4. Traverse AFG from the corresponding AA-in or AA-out node in MA .
[Cond.6] C is an MA-out node:
1. MB := {M | C ∈ M }, mB := ψ −1 (MB )2. mA := {m | m ∈ OC(this) and m calls mB } (using MFG)
3. MA := ψ(mA )4. In MA , traverse AFG from MI nodes that call mB[Cond.7] C is a MI node:
1. mA := {m | m ∈ OC(this) and C calls m}
2. MA := ψ(mA )3. Traverse AFG from MA-out nodes in MA .
. . . . . . . . . . . . . . . . . . . . . . [Cond.8] and [Cond.9] are for programs that have pointer variables.
[Cond.8] C is an AFG normal node with ’∗’ operator, such as ∗x:
1. X := ϕ(x)2. Compute X’s aliases A(X).
3. Traverse AFG from {ϕ(y) | ϕ(&y) ∈ A(X)} and {ϕ(∗y) | ϕ(y) ∈ A(X)}.
[Cond.9] C is an AFG normal node with ’&’ operator, such as &x :1. X := ϕ(x)2. Compute X’s aliases A(X).
3. Traverse AFG from {ϕ(y) | ϕ(∗y) ∈ A(X)} and {ϕ(&y) | ϕ(y) ∈ A(X)}.
................................................................................................
Step 3: Expressions corresponding to reachable nodes are e’s aliases.
December 27, 2001

DRAFT

Fig. 17. alias computation algorithm