Heap Reference Analysis Using Access Graphs

arXiv:cs/0608104v3 [] 1 Sep 2007

UDAY P. KHEDKER, AMITABHA SANYAL and AMEY KARKARE
Department of Computer Science & Engg., IIT Bombay.

Despite significant progress in the theory and practice of program analysis, analyzing properties
of heap data has not reached the same level of maturity as the analysis of static and stack data.
The spatial and temporal structure of stack and static data is well understood while that of heap
data seems arbitrary and is unbounded. We devise bounded representations which summarize
properties of the heap data. This summarization is based on the structure of the program which
manipulates the heap. The resulting summary representations are certain kinds of graphs called
access graphs. The boundedness of these representations and the monotonicity of the operations
to manipulate them make it possible to compute them through data flow analysis.
An important application which benefits from heap reference analysis is garbage collection,
where currently liveness is conservatively approximated by reachability from program variables.
As a consequence, current garbage collectors leave a lot of garbage uncollected, a fact which
has been confirmed by several empirical studies. We propose the first ever end-to-end static
analysis to distinguish live objects from reachable objects. We use this information to make dead
objects unreachable by modifying the program. This application is interesting because it requires
discovering data flow information representing complex semantics. In particular, we formulate
the following new analyses for heap data: liveness, availability, and anticipability and propose
solution methods for them. Together, they cover various combinations of directions of analysis
(i.e. forward and backward) and confluence of information (i.e. union and intersection). Our
analysis can also be used for plugging memory leaks in C/C++ languages.
Categories and Subject Descriptors: D.3.4 [Programming Languages]: Processors—Memory management
(garbage collection); Optimization; F.3.2 [Logics and Meanings Of Programs]: Semantics of Programming
Languages—Program analysis
General Terms: Algorithms, Languages, Theory
Additional Key Words and Phrases: Aliasing, Data Flow Analysis, Heap References, Liveness

1. INTRODUCTION
Conceptually, data in a program is allocated in either the static data area, stack, or heap.
Despite significant progress in the theory and practice of program analysis, analyzing the
properties of heap data has not reached the same level of maturity as the analysis of static
and stack data. Section 1.2 investigates possible reasons.
In order to facilitate a systematic analysis, we devise bounded representations which
summarize properties of the heap data. This summarization is based on the structure of the
program which manipulates the heap. The resulting summary representations are certain
kinds of graphs, called access graphs which are obtained through data flow analysis. We
believe that our technique of summarization is general enough to be also used in contexts
other than heap reference analysis.
1.1 Improving Garbage Collection through Heap Reference Analysis
An important application which benefits from heap reference analysis is garbage collection,
where liveness of heap data is conservatively approximated by reachability. This amounts

ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year, Pages 1–??.

·

2

Uday Khedker et al.

// x points to ma
1. w = x
2. while (x.getdata() < max)
{
1.
3.
x = x.rptr
}
2.
4. y = x.lptr
5. z = New class of z
// Possible GC Point
3.
6. y = y.lptr
7. z.sum = x.lptr.getdata() + y.getdata()
(a) A Program Fragment
z
x
w
y
Stack

r md lptr
rpt
l
m
me lptr
p
c
r
tr
rpt
l
m
l
m
ml
p
p
g
r b tr
tr
rpt
m f lptr
ma lptr
mm
mh
mi lptr
mk

mj

4.
5.
6.
7.

Heap

(b) Superimposition of memory graphs before line 5.
Dashed arrows capture the effect of different iterations of the while loop. All thick arrows (both
dashed and solid) are live links.

y = z = null
w=x
w = null
while (x.getdata() < max)
{ x.lptr = null
x = x.rptr
}
x.rptr = x.lptr.rptr = null
x.lptr.lptr.lptr = null
x.lptr.lptr.rptr = null
y = x.lptr
y.rptr = y.lptr.lptr = y.lptr.rptr = null
z = New class of z
z.lptr = z.rptr = null
y = y.lptr
x.lptr.lptr = y.lptr = y.rptr = null
z.sum = x.lptr.getdata() + y.getdata()
x = y = z = null

(c) The modified program. Highlighted statements indicate the null assignments inserted in the program
using our method. (More details in Section 4)

Fig. 1. A motivating example.

to approximating the future of an execution with its past. Since current garbage collectors
cannot distinguish live data from data that is reachable but not live, they leave a lot of
garbage uncollected. This has been confirmed by empirical studies [Hirzel et al. 2002;
Hirzel et al. 2002; Shaham et al. 2000; 2001; 2002] which show that a large number (24%
to 76%) of heap objects which are reachable at a program point are actually not accessed
beyond that point. In order to collect such objects, we perform static analyses to make dead
objects unreachable by setting appropriate references to null. The idea that doing so would
facilitate better garbage collection is well known as “Cedar Mesa Folk Wisdom” [Gadbois
et al. ]. The empirical attempts at achieving this have been [Shaham et al. 2001; 2002].
Garbage collection is an interesting application for us because it requires discovering
data flow information representing complex semantics. In particular, we need to discover
four properties of heap references: liveness, aliasing, availability, and anticipability. Liveness captures references that may be used beyond the program point under consideration.
Only the references that are not live can be considered for null assignments. Safety of null
assignments further requires (a) discovering all possible ways of accessing a given heap
memory cell (aliasing), and (b) ensuring that the reference being nullified is accessible
(availability and anticipability).
For simplicity of exposition, we present our method using a memory model similar to
that of Java. Extensions required for handling C/C++ model of heap usage are easy and are
explained in Section 8. We assume that root variable references are on the stack and the
actual objects corresponding to the root variables are in the heap. In the rest of the paper we
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

·

3

ignore non-reference variables. We view the heap at a program point as a directed graph
called memory graph. Root variables form the entry nodes of a memory graph. Other
nodes in the graph correspond to objects on the heap and edges correspond to references.
The out-edges of entry nodes are labeled by root variable names while out-edges of other
nodes are labeled by field names. The edges in the memory graph are called links.
E XAMPLE 1.1. Figure 1 shows a program fragment and its memory graphs before line
5. Depending upon the number of times the while loop is executed x points to ma , mb , mc
etc. Correspondingly, y points to mi , m f , mg etc. The call to New on line 5 may require
garbage collection. A conventional copying collector will preserve all nodes except mk .
However, only a few of them are used beyond line 5.
The modified program is an evidence of the strength of our approach. It makes the
unused nodes unreachable by nullifying relevant links. The modifications in the program
are general enough to nullify appropriate links for any number of iterations of the loop.
Observe that a null assignment has also been inserted within the loop body thereby making
some memory unreachable in each iteration of the loop.
✷
After such modifications, a garbage collector will collect a lot more garbage. Further,
since copying collectors process only live data, garbage collection by such collectors will
be faster. Both these facts are corroborated by our empirical measurements (Section 7).
In the context of C/C++, instead of setting the references to null, allocated memory will
have to be explicitly deallocated after checking that no alias is live.
1.2 Difficulties in Analyzing Heap Data
A program accesses data through expressions which have l-values and hence are called
access expressions. They can be scalar variables such as x, or may involve an array access
such as a[2 ∗ i], or can be a reference expression such as x.l.r.
An important question that any program analysis has to answer is: Can an access expression α1 at program point p1 have the same l-value as α2 at program point p2 ? Note that
the access expressions or program points could be identical. The precision of the analysis
depends on the precision of the answer to the above question.
When the access expressions are simple and correspond to scalar data, answering the
above question is often easy because, the mapping of access expressions to l-values remains fixed in a given scope throughout the execution of a program. However in the case
of array or reference expressions, the mapping between an access expression and its l-value
is likely to change during execution. From now on, we shall limit our attention to reference
expressions, since these are the expressions that are primarily used to access the heap. Observe that manipulation of the heap is nothing but changing the mapping between reference
expressions and their l-values. For example, in Figure 1, access expression x.lptr refers to
mi when the execution reaches line number 2 and may refer to mi , m f , mg , or me at line 4.
This implies that, subject to type compatibility, any access expression can correspond to
any heap data, making it difficult to answer the question mentioned above. The problem
is compounded because the program may contain loops implying that the same access
expression appearing at the same program point may refer to different l-values at different
points of time. Besides, the heap data may contain cycles, causing an infinite number
of access expressions to refer to the same l-value. All these make analysis of programs
involving heaps difficult.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

4

·

Uday Khedker et al.

1.3 Contributions of This Paper
The contributions of this paper fall in the following two categories
—Contributions in Data Flow Analysis. We present a data flow framework in which the
data flow values represent abstractions of heap. An interesting aspect of our method is
the way we obtain bounded representations of the properties by using the structure of
the program which manipulates the heap. As a consequence of this summarization, the
values of data flow information constitute a complete lattice with finite height. Further,
we have carefully identified a set of monotonic operations to manipulate this data flow
information. Hence, the standard results of data flow analysis can be extended to heap
reference analysis. Due to the generality of this approach, it can be applied to other
analyses as well.
—Contributions in Heap Data Analysis. We propose the first ever end-to-end solution
(in the intraprocedural context) for statically discovering heap references which can be
made null to improve garbage collection. The only approach which comes close to our
approach is the heap safety automaton based approach [Shaham et al. 2003]. However,
our approach is superior to their approach in terms of completeness, effectiveness, and
efficiency (details in Section 9.2).
The concept which unifies the contributions is the summarization of heap properties
which uses the fact that the heap manipulations consist of repeating patterns which bear
a close resemblance to the program structure. Our approach to summarization is more
natural and more precise than other approaches because it does not depend on an a-priori
bound [Jones and Muchnick 1979; 1982; Larus and Hilfinger 1988; Chase et al. 1990].
1.4 Organization of the paper
The rest of the paper is organized as follows. Section 2 defines the concept of explicit
liveness of heap objects and formulates a data flow analysis by using access graphs as data
flow values. Section 3 defines other properties required for ensuring safety of null assignment insertion. Section 4 explains how null assignments are inserted. Section 5 discusses
convergence and complexity issues. Section 6 shows the soundness of our approach. Section 7 presents empirical results. Section 8 extends the approach to C++. Section 9 reviews
related work while Section 10 concludes the paper.
2. EXPLICIT LIVENESS ANALYSIS OF HEAP REFERENCES
Our method discovers live links at each program point, i.e., links which may be used in
the program beyond the point under consideration. Links which are not live can be set to
null. This section describes the liveness analysis. In particular, we define liveness of heap
references, devise a bounded representation called an access graph for liveness, and then
propose a data flow analysis for discovering liveness. Other analyses required for safety of
null insertion are described in Section 3.
Our method is flow sensitive but context insensitive. This means that we compute pointspecific information in each procedure by taking into account the flow of control at the
intraprocedural level and by approximating the interprocedural information such that it is
not context-specific but is safe in all calling contexts. For the purpose of analysis, arrays
are handled by approximating any occurrence of an array element by the entire array. The
current version models exception handling by explicating possible control flows. However,
programs containing threads are not covered.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

·

5

2.1 Access Paths
In order to discover liveness and other properties of heap, we need a way of naming links
in the memory graph. We do this using access paths.
An access path is a root variable name followed by a sequence of zero or more field
names and is denoted by ρx ≡ x f1 f2 · · · fk . Since an access path represents a path
in a memory graph, it can be used for naming links and nodes. An access path consisting
of just a root variable name is called a simple access path; it represents a path consisting of
a single link corresponding to the root variable. E denotes an empty access path.
The last field name in an access path ρ is called its frontier and is denoted by Frontier (ρ).
The frontier of a simple access path is the root variable name. The access path corresponding to the longest sequence of names in ρ excluding its frontier is called its base and is
denoted by Base(ρ). Base of a simple access path is the empty access path E . The object
reached by traversing an access path ρ is called the target of the access path and is denoted
by Target(ρ). When we use an access path ρ to refer to a link in a memory graph, it
denotes the last link in ρ, i.e. the link corresponding to Frontier (ρ).
E XAMPLE 2.1. As explained earlier, Figure 1(b) is the superimposition of memory
graphs that can result before line 5 for different executions of the program. For the access
path ρx ≡ x lptr lptr, depending on whether the while loop is executed 0, 1, 2, or 3
times, Target(ρx ) denotes nodes m j , mh , mm , or ml . Frontier (ρx ) denotes one of the links
mi → m j , m f → mh , mg → mm or me → ml . Base(ρx ) represents the following paths in the
heap memory: x → ma → mi , x → mb → m f , x → mc → mg or x → md → me .
✷
In the rest of the paper, α denotes an access expression, ρ denotes an access path and
σ denotes a (possibly empty) sequence of field names separated by . Let the access
expression αx be x. f1 . f2 . . . fn . Then, the corresponding access path ρx is x f1 f2 . . . fn .
When the root variable name is not required, we drop the subscripts from αx and ρx .
2.2 Program Flow Graph
Since the current version of our method involves context insensitive analysis, each procedure is analyzed separately and only once. Thus there is no need of maintaining a call
graph and we use the term program and procedure interchangeably.
To simplify the description of analysis we make the following assumptions:
—The program flow graph has a unique Entry and a unique Exit node. We assume that
there is a distinguished main procedure.
—Each statement forms a basic block.
—The conditions that alter flow of control are made up only of simple variables. If not, the
offending reference expression is assigned to a fresh simple variable before the condition
and is replaced by the fresh variable in the condition.
With these simplification, each statement falls in one of the following categories:
—Function Calls. These are statements x = f (αy , αz , . . .) where the functions involve access expressions in arguments. The type of x does not matter.
—Assignment Statements. These are assignments to references and are denoted by αx = αy .
Only these statements can modify the structure of the heap.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

6

·

Uday Khedker et al.

—Use Statements. These statements use heap references to access heap data but do not
modify heap references. For the purpose of analysis, these statements are abstracted as
lists of expressions αy .d where αy is an access expression and d is a non-reference.
—Return Statement of the type return αx involving reference variable x.
—Other Statements. These statements include all statements which do not refer to the
heap. We ignore these statements since they do not influence heap reference analysis.
When we talk about the execution path, we shall refer to the execution of the program
derived by retaining all function calls, assignments and use statements and ignoring the
condition checks in the path.
For simplicity of exposition, we present the analyses assuming that there are no cycles
in the heap. This assumption does not limit the theory in any way because our analyses
inherently compute conservative information in the presence of cycles without requiring
any special treatment.
2.3 Liveness of Access Paths
A link l is live at a program point p if it is used in some control flow path starting from p.
Note that l may be used in two different ways. It may be dereferenced to access an object
or tested for comparison. An erroneous nullification of l would affect the two uses in
different ways: Dereferencing l would result in an exception being raised whereas testing
l for comparison may alter the result of condition and thereby the execution path.
Figure 1(b) shows links that are live before line 5 by thick arrows. For a link l to be live,
there must be at least one access path from some root variable to l such that every link in
this path is live. This is the path that is actually traversed while using l.
Since our technique involves nullification of access paths, we need to extend the notion
of liveness from links to access paths. An access path is defined to be live at p if the
link corresponding to its frontier is live along some path starting at p. Safety of null
assignments requires that the access paths which are live are excluded from nullification.
We initially limit ourselves to a subset of live access paths, whose liveness can be determined without taking into account the aliases created before p. These access paths are live
solely because of the execution of the program beyond p. We call access paths which are
live in this sense as explicitly live access paths. An interesting property of explicitly live
access paths is that they form the minimal set covering every live link.
E XAMPLE 2.2. If the body of the while loop in Figure 1(a) is not executed even once,
Target(y) = mi at line 5 and the link mi → m j is live at line 5 because it is used in line 6.
The access paths y and y lptr are explicitly live because their liveness at 5 can be determined solely from the statements from 5 onwards. In contrast, the access path w lptr lptr
is live without being explicitly live. It becomes live because of the alias between y and
w lptr and this alias was created before 5. Also note that if an access path is explicitly
live, so are all its prefixes.
✷
E XAMPLE 2.3. We illustrate the issues in determining explicit liveness of access paths
by considering the assignment x.r.n = y.n.n.
—Killed Access Paths. Since the assignment modifies Frontier (x r n), any access path
which is live after the assignment and has x r n as prefix will cease to be live before
the assignment. Access paths that are live after the assignment and not killed by it are
live before the assignment also.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

·

7

—Directly Generated Access Paths. All prefixes of x r and y n are explicitly live before
the assignment due to the local effect of the assignment.
—Transferred Access Paths. If x r n σ is live after the assignment, then y n n σ will
be live before the assignment. For example, if x r n n is live after the assignment,
then y n n n will be live before the assignment. The sequence of field names σ is
viewed as being transferred from x r n to y n n.
✷
We now define liveness by generalizing the above observations. We use the notation
ρx ∗ to enumerate all access paths which have ρx as a prefix. The summary liveness
information for a set S of reference variables is defined as follows:
[

Summary(S) =

{x ∗}

x∈S

Further, the set of all global variables is denoted by Globals and the set of formal parameters of the function being analyzed is denoted by Params.
Definition 2.1. Explicit Liveness. The set of explicitly live access paths at a program
point p, denoted by Liveness p is defined as follows.
Liveness p =

[

(PathLivenessψp )

ψ∈Paths(p)
ψ

where, ψ ∈ Paths(p) is a control flow path p to Exit and PathLiveness p denotes the liveness
at p along ψ and is defined as follows. If p is not program exit then let the statement which
follows it be denoted by s and the program point immediately following s be denoted by
p′ . Then,

0/
p is Exit of main

Summary(Globals)
p is Exit of some procedure
PathLivenessψp =
 StatementLiveness (PathLivenessψ ) otherwise
s
′
p
where the flow function for s is defined as follows:

StatementLivenesss (X) = (X − LKills ) ∪ LDirects ∪ LTransfers (X)
LKills denotes the sets of access paths which cease to be live before statement s, LDirects
denotes the set of access paths which become live due to local effect of s and LTransfers (X)
denotes the the set of access paths which become live before s due to transfer of liveness
from live access paths after s. They are defined in Figure 2.
✷
Observe that the definitions of LKills , LDirects , and LTransfers (X) ensure that the Liveness p
is prefix-closed.
E XAMPLE 2.4. In Figure 1, it cannot be statically determined which link is represented
by access expression x.lptr at line 4. Depending upon the number of iterations of the while
loop, it may be any of the links represented by thick arrows. Thus at line 1, we have to assume that all access paths {x lptr lptr, x rptr lptr lptr, x rptr rptr lptr lptr, . . . }
are explicitly live.
✷
In general, an infinite number of access paths with unbounded lengths may be live before
a loop. Clearly, performing data flow analysis for access paths requires a suitable finite
representation. Section 2.4 defines access graphs for the purpose.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

8

·

Uday Khedker et al.

Statement s

LKills

LDirects

αx = αy
{ρx
αx = f (αy ) {ρx
αx = new
αx = null
use αy .d
return αy
other

∗} Prefixes(Base(ρx )) ∪ Prefixes(Base(ρy )) {ρy
∗}
Prefixes(Base(ρx ))
∪ Summary({ρy } ∪ Globals)
{ρx ∗}
Prefixes(Base(ρx ))
{ρx ∗}
Prefixes(Base(ρx ))
0/
Prefixes(ρy )
0/
Summary({ρy })
0/
0/

LTransfers (X)
σ | ρx
0/

σ ∈ X}

0/
0/
0/
0/
0/

Fig. 2. Defining Flow Functions for Liveness. Globals denotes the set of global references and Params denotes
the set of formal parameters. For simplicity, we have shown a single access expression on the RHS.

2.4 Representing Sets of Access Paths by Access Graphs
In the presence of loops, the set of access paths may be infinite and the lengths of access
paths may be unbounded. If the algorithm for analysis tries to compute sets of access paths
explicitly, termination cannot be guaranteed. We solve this problem by representing a set
of access paths by a graph of bounded size.
2.4.1 Defining Access Graphs. An access graph, denoted by Gv , is a directed graph
hn0 , N, Ei representing a set of access paths starting from a root variable v.1 N is the set of
nodes, n0 ∈ NF is the entry node with no in-edges and E is the set of edges. Every path in
the graph represents an access path. The empty graph EG has no nodes or edges and does
not accept any access path.
The entry node of an access graphs is labeled with the name of the root variable while
the non-entry nodes are labeled with a unique label created as follows: If a field name f
is referenced in basic block b, we create an access graph node with a label h f , b, ii where i
is the instance number used for distinguishing multiple occurrences of the field name f in
block b. Note that this implies that the nodes with the same label are treated as identical.
Often, i is 0 and in such a case we denote the label h f , b, 0i by fb for brevity. Access paths
ρx ∗ are represented by including a summary node denoted n∗ with a self loop over it. It
is distinct from all other nodes but matches the field name of any other node.
A node in the access graph represents one or more links in the memory graph. Additionally, during analysis, it represents a state of access graph construction (explained in
Section 2.4.2). An edge fn → gm in an access graph at program point p indicates that a
link corresponding to field f dereferenced in block n may be used to dereference a link
corresponding to field g in block m on some path starting at p. This has been used in
Section 5.2 to argue that the size of access graphs in practical programs is small.
Pictorially, the entry node of an access graph is indicated by an incoming double arrow.
2.4.2 Summarization. Recall that a link is live at a program point p if it is used along
some control flow path from p to Exit. Since different access paths may be live along
different control flow paths and there may be infinitely many control flow paths in the case
1 Where

the root variable name is not required, we drop the subscript v from Gv .

ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

1 x = x.r 1

2 x = x.r 2

9

Live access paths at entry of block 1: {x, x r, x r r, x r r r, . . .}
Corresponding access graph: G1x

1 x = x.r 1

·

x

r1

Live access paths at entry of block 1: {x, x r, x r r}
Corresponding access graph: G2x

x

r1

r2

Fig. 3. Approximations in Access Graphs

of a loop following p, there may be infinitely many access paths which are live at p. Hence,
the lengths of access paths will be unbounded. In such a case summarization is required.
Summarization is achieved by merging appropriate nodes in access graphs, retaining all
in and out edges of merged nodes. We explain merging with the help of Figure 3:
—Node n1 in access graph G1x indicates references of n at different execution instances
of the same program point. Every time this program point is visited during analysis,
the same state is reached in that the pattern of references after n1 is repeated. Thus all
occurrences of n1 are merged into a single state. This creates a cycle which captures the
repeating pattern of references.
—In G2x , nodes n1 and n2 indicate referencing n at different program points. Since the
references made after these program points may be different, n1 and n2 are not merged.
Summarization captures the pattern of heap traversal in the most straightforward way.
Traversing a path in the heap requires the presence of reference assignments αx = αy such
that ρx is a proper prefix of ρy . Assignments in Figure 3 are examples of such assignments.
The structure of the flow of control between such assignments in a program determines the
pattern of heap traversal. Summarization captures this pattern without the need of control
flow analysis and the resulting structure is reflected in the access graphs as can be seen
in Figure 3. More examples of the resemblance of program structure and access graph
structure can be seen in the access graphs in Figure 6.
2.4.3 Operations on Access Graphs. Section 2.3 defined liveness by applying certain
operations on access paths. In this subsection we define the corresponding operations on
access graphs. Unless specified otherwise, the binary operations are applied only to access
graphs having same root variable. The auxiliary operations and associated notations are:
—Root(ρ) denotes the root variable of access path ρ, while Root(G) denotes the root
variable of access graph G.
—Field(n) for a node n denotes the field name component of the label of n.
—G (ρ) constructs access graphs corresponding to ρ. It uses the current basic block number
and the field names to create appropriate labels for nodes. The instance number depends
on the number of occurrences of a field name in the block. G (ρ ∗) creates an access
graph with root variable x and the summary node n∗ with an edge from x to n∗ and a self
loop over n∗ .
—lastNode(G) returns the last node of a linear graph G constructed from a given ρ.
—CleanUp(G) deletes the nodes which are not reachable from the entry node.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

10

·

Uday Khedker et al.

Program

Access Graphs
g1

1 x = x.l 1
2 y = x.r.d 2
Union
g3 ⊎ g4 = g4
g2 ⊎ g4 = g5
g5 ⊎ g4 = g5
g5 ⊎ g6 = g6

g2
x

g3
r2

x

g4

g5
x

l1

Path Removal
g6 ⊖ x l = g2
g5 ⊖ x = EG
g4 ⊖ x r = g4
g4 ⊖ x l = g1

r2

x

Remainder
Graphs
rg1

l1

x

r2

r2

l1

rg2

g6
x

l1

r2

l1

r2

Factorisation
Extension
g2 / (g1 , {x}) = {rg1 }
(g3 , {l1 }) # {rg1 } = g4
g5 / (g1 , {x}) = {rg1 , rg2 } (g3 , {x, l1 }) # {rg1, rg2 } = g6
(g2 , {r2 }) # {εRG } = g2
g5 / (g2 , {r2 }) = {εRG }
(g2 , {r2 }) # 0/ = EG
g4 / (g2 , {r2 }) = 0/

Fig. 4. Examples of operations on access graphs.

—CN(G, G′ , S) computes the set of nodes of G which correspond to the nodes of G′ specified in the set S. To compute CN(G, G′ , S), we define ACN(G, G′ ), the set of pairs of
all corresponding nodes. Let G ≡ hn0 , N, Ei and G′ ≡ hn′0 , N ′ , E ′ i. A node n in G corresponds to a node n′ in G′ if there there exists an access path ρ which is represented by a
path from n0 to n in G and a path from n′0 to n′ in G′ .
Formally, ACN(G, G′ ) is the least solution of the following equation:

0/
Root(G) 6= Root(G′ )


 {hn , n′ i} ∪ {hn , n′ i | Field(n ) = Field(n′ ),
otherwise
0 0
j j
j
j
ACN(G, G′ ) =
′ → n′ ∈ E ′ ,
n
→
n
∈
E,
n

i
j
i
j


hni , n′i i ∈ ACN(G, G′ )}
CN(G, G′ , S) = {n | hn, n′ i ∈ ACN(G, G′ ), n′ ∈ S}

Note that Field(n j ) = Field(n′j ) would hold even when n j or n′j is the summary node n∗ .
Let G ≡ hn0 , N, Ei and G′ ≡ hn0 , N ′ , E ′ i be access graphs (having the same entry node).
G and G′ are equal if N = N ′ and E = E ′ .
The main operations of interest are defined below and are illustrated in Figure 4.
(1) Union ( ⊎ ). G ⊎ G′ combines access graphs G and G′ such that any access path contained in G or G′ is contained in the resulting graph.
G ⊎ G′ = n 0 , N ∪ N ′ , E ∪ E ′
The operation N ∪ N ′ treats the nodes with the same label as identical. Because of
associativity, ⊎ can be generalized to arbitrary number of arguments in an obvious
manner.
(2) Path Removal (⊖). The operation G ⊖ ρ removes those access paths in G which have
ρ as a prefix.

ρ = E or Root(ρ) 6= Root(G)
G
G⊖ρ =
EG
ρ is a simple access path

CleanUp(hn0 , N, E − Edel i) otherwise

ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

·

11

where
Edel = {ni → n j | ni → n j ∈ E, ni ∈ CN(G, GB , {lastNode(GB)}),
{ni → f n j |Field(n j ) = Frontier (ρ), GB = G (Base(ρ)),
{ni → f n j |UniqueAccessPath?(G, ni )}
UniqueAccessPath?(G, n) returns true if in G, all paths from the entry node to node
n represent the same access path. Note that path removal is conservative in that some
paths having ρ as prefix may not be removed. Since an access graph edge may be
contained in more than one access paths, we have to ensure that access paths which do
not have ρ as prefix are not erroneously deleted.
(3) Factorization (/). Recall that the Transfer term in Definition 2.1 requires extracting
suffixes of access paths and attaching them to some other access paths. The corresponding operations on access graphs are performed using factorization and extension.
Given a node m ∈ (N − {n0}) of an access graph G, the Remainder Graph of G at m
is the subgraph of G rooted at m and is denoted by RG(G, m). If m does not have any
outgoing edges, then the result is the empty remainder graph εRG . Let M be a subset
of the nodes of G′ and M ′ be the set of corresponding nodes in G. Then, G/(G′ , M)
computes the set of remainder graphs of the successors of nodes in M ′ .
G/(G′ , M) = {RG(G, n j ) | ni → n j ∈ E, ni ∈ CN(G, G′ , M)}

(1)

A remainder graph is similar to an access graph except that (a) its entry node does
not correspond to a root variable but to a field name and (b) the entry node can have
incoming edges.
(4) Extension. Extending an empty access graph EG results in the empty access graph EG .
For non-empty graphs, this operation is defined as follows.
(a) Extension with a remainder graph (·). Let M be a subset of the nodes of G and
R ≡ hn′ , N R , E R i be a remainder graph. Then, (G, M) · R appends the suffixes in
R to the access paths ending on nodes in M.
(G, M) · εRG = G
(G, M) · R = n0 , N ∪ N R , E ∪ E R ∪ {ni → n′ | ni ∈ M}

(2)

(b) Extension with a set of remainder graphs (#). Let S be a set of remainder graphs.
Then, G# S extends access graph G with every remainder graph in S.
(G, M)# 0/ = EG
(G, M)# S =

]

(G, M) · R

(3)

R∈S

2.4.4 Safety of Access Graph Operations. Since access graphs are not exact representations of sets of access paths, the safety of approximations needs to be defined explicitly.
The constraints defined in Figure 5 capture safety in the context of liveness in the following
sense: Every access path which can possibly be live should be retained by each operation.
Since the complement of liveness is used for nullification, this ensures that no live access
path is considered for nullification. These properties have been proved [Iyer 2005] using
the PVS theorem prover2.
2 Available

from http://pvs.csl.sri.com.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

·

12

Uday Khedker et al.

Operation

Access Graphs

Access Paths

Union

G3 = G1 ⊎ G2

P(G3 ,M3 ) ⊇ P(G1 ,M1 ) ∪ P(G2 ,M2 )

Path Removal G2 = G1 ⊖ ρ

P(G2 ,M2 ) ⊇ P(G1 ,M1 ) − {ρ σ | ρ σ ∈ P(G1 ,M1 )}

Factorization

S = G1 /(G2 ,M) P(S,Ms ) = {σ | ρ′

σ ∈ P(G1 ,M1 ),ρ′ ∈ P(G2 ,M)}

Extension

G2 = (G1 ,M)# S P(G2 ,M2 ) ⊇ P(G1 ,M1 ) ∪ {ρ σ | ρ ∈ P(G1 ,M),σ ∈ P(S,Ms )}

Fig. 5. Safety of Access Graph Operations. P(G,M) is the set of paths in graph G terminating on nodes in M.
For graph Gi , Mi is the set of all nodes in Gi . S is the set of remainder graphs and P(S,Ms ) is the set of all paths
in all remainder graphs in S.

2.5 Data Flow Analysis for Discovering Explicit Liveness
For a given root variable v, ELInv (i) and ELOutv (i) denote the access graphs representing
explicitly live access paths at the entry and exit of basic block i. We use EG as the initial
value for ELInv (i)/ELOutv (i).
ELInv (i) = (ELOutv (i) ⊖ ELKillPathv(i)) ⊎ ELGenv (i)

i = Exit, v ∈ Globals
G (v ∗)



EG]
i = Exit, v 6∈ Globals
ELOutv (i) =

ELInv (s) otherwise



(4)
(5)

s∈succ(i)

where

ELGenv (i) = LDirectv (i) ⊎ LTransferv (i)
We define ELKillPathv (i), LDirectv (i), and LTransferv (i) depending upon the statement.
(1) Assignment statement αx = αy . Apart from defining the desired terms for x and y, we
also need to define them for any other variable z. In the following equations, Gx and
Gy denote G (ρx ) and G (ρy ) respectively, whereas Mx and My denote lastNode(G (ρx ))
and lastNode(G (ρy )) respectively.
LDirectx (i) = G (Base(ρx ))

EG
αy is New . . . or null
LDirecty (i) =
G (Base(ρy )) otherwise
LDirectz (i) = EG , for any variable z other than x and y

αy is New or null
EG
LTransfery (i) = (Gy , My )#
otherwise

(ELOutx (i)/(Gx , Mx ))

(6)

LTransferz (i) = EG , for any variable z other than y
ELKillPathx (i) = ρx
ELKillPathz (i) = E , for any variable z other than x

As stated earlier, the path removal operation deletes an edge only if it is contained in
a unique path. Thus fewer paths may be killed than desired. This is a safe approximation. Another approximation which is also safe is that only the paths rooted at x are
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

ELOut(i)

i

x
x

5

y

l7

x

y

l7
x

z

y

y

l7

x
z

l6

l7

y

l7
x

x

r3

l6

l4

x
l4

r3

l6

l4

l7
x

l6

l7

r3

x
l4

l6

l7

r3

2

1

l6
l7

x

l7
x

l6

l7

l6

l7
r3
l4

z

y

l4

3

z
l6

l7

4
x

13

ELIn(i)

7
6

·

r3

l6

l4

l6

Fig. 6. Explicit liveness for the program in Figure 1 under the assumption that all variables are local variables.

killed. Since assignment to αx changes the link represented by Frontier(ρx ), for precision, any path which is guaranteed to contain the link represented by Frontier (ρx )
should also be killed. Such paths can be discovered through must-alias analysis which
we do not perform.
(2) Function call αx = f (αy ). We conservatively assume that a function call may make
any access path rooted at y or any global reference variable live. Thus this version of
our analysis is context insensitive.
LDirectx (i) = G (Base(ρx ))
LDirecty (i) = G (ρy ∗)

G (z ∗) if z is a global variable
LDirectz (i) =
EG
otherwise
LTransferz (i) = EG , for all variables z
ELKillPathx (i) = ρx
ELKillPathz (i) = E , for any variable z other than x
(3) Return Statement return αx .
LDirectx (i) = G (ρx ∗)

G (z ∗) if z is a global variable
LDirectz (i) =
EG
otherwise
LTransferz (i) = EG , for any variable z
ELKillPathz (i) = E , for any variable z
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

14

·

Uday Khedker et al.
1 x=y 1
2 x = New 2 3 x.n = New 3
4 x.n = null? 4

T

F

5 y = x.r 5

6 y = x.r 6
7 x.n.n = New 7

Fig. 7. Explicit liveness information is not sufficient for nullification.

(4) Use Statements
LDirectx (i) =

]

G (ρx ) for every αx .d used in i

LDirectz (i) = EG for any variable z other than x andy
LTransferz (i) = EG , for every variable z
ELKillPathz(i) = E , for every variable z
E XAMPLE 2.5. Figure 6 lists explicit liveness information at different points of the
program in Figure 1 under the assumption that all variables are local variables.
✷
Observe that computing liveness using equations (4) and (5) results in an MFP (Maximum Fixed Point) solution of data flow analysis whereas definition (2.1) specifies an
MoP (Meet over Paths) solution of data flow analysis. Since the flow functions are nondistributive (see appendix A), the two solutions may be different.
3. OTHER ANALYSES FOR INSERTING NULL ASSIGNMENTS
Explicit liveness alone is not enough to decide whether an assignment αx = null can be
safely inserted at p. We have to additionally ensure that:
—Frontier (ρx ) is not live through an alias created before the program point p. The extensions required to find all live access paths, including those created due to aliases, is
discussed in section 3.1.
—Dereferencing links during the execution of the inserted statement αx = null does not
cause an exception. This is done through availability and anticipability analysis and is
described in section 3.2.
Both these requirements are illustrated through the example shown below:
E XAMPLE 3.1. In Figure 7, access path y n is not explicitly live in block 6. However,
Frontier (y n) and Frontier (x n) represent the same link due to the assignment x = y.
Thus y n is implicitly live and setting it to null in block 6 will raise an exception in block
7. Also, x n n is not live in block 2. However, it cannot be set to null since the object
pointed to by x n does not exist in memory when the execution reaches block 2. Therefore,
insertion of x.n.n = null in block 2 will raise an exception at run-time.
✷
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

·

15

3.1 Computing Live Access Paths
Recall that an access path is live if it is either explicitly live or shares its Frontier with
some explicitly live path. The property of sharing is captured by aliasing. Two access
paths ρx and ρy are aliased at a program point p if Target(ρx ) is same as Target(ρy ) at p
during some execution of the program. They are link-aliased if their frontiers represent the
same link; they are node-aliased if they are aliased but their frontiers do not represent the
same link. Link-aliases can be derived from node-aliases (or other link-aliases) by adding
the same field names to aliased access paths.
Alias information is flow-sensitive if the aliases at a program point depend on the statements along control flow paths reaching the point. Otherwise it is flow insensitive. Among
flow sensitive aliases, two access paths are must-aliased at p if they are aliased along every
control flow path reaching p; they are may-aliased if they are aliased along some control
flow path reaching p. As an example, in Figure 1, x lptr and y are must-node-aliases,
x lptr lptr and y lptr are must-link-aliases, and w and x are node-aliases at line 5.
We compute flow sensitive may-aliases (without kills) using the algorithm described
by Hind et al. [1999] and use pairs of access graphs for compact representation of aliases.
Liveness is computed through a backward propagation much in the same manner as explicit
liveness except that it is ensured that the live paths at each program point is closed under
may-aliasing. This requires the following two changes in the earlier scheme.
(1) Inclusion of Intermediate Nodes in Access Graphs. Unlike explicit liveness, live access
paths may not be prefix closed. This is because the frontier of a live access path ρx may
be accessed using some other access path and not through the links which constitute
ρx . Hence prefixes of ρx may not be live. In an access graph representing liveness,
all paths may not represent live links. We therefore modify the access graph so that
such paths are not described by the access graph. In order to make this distinction, we
divide the nodes in an access graphs in two categories: final and intermediate. The
only access paths described by the access graph are those which end at final nodes. 3
This change affects the access graph operations in the following manner:
—The equality of graphs now must consider equality of the sets of intermediate nodes
and the sets of final nodes separately.
—Graph constructor G (ρx ) marks all nodes in the resulting graph as final implying
that all non-empty prefixes of ρx are contained in the graph. We define a new constructor GOnly (ρx ) which marks only the last node as final and all other nodes as
intermediate implying that only ρx is contained in the graph.
—Whenever multiple nodes with identical labels are combined, if any instance of the
node is final then the resulting node is treated as final. This influences union (⊎)
and extension (# ).
—The set M used in defining factorization and extension (equations 1, 2, 3) and the
safety properties of access graph operations (Figure 5) contain final nodes only.
—Extension G · RG marks all nodes in G as intermediate. If G and RG have a common
node then the status of the node is governed by its status in RG.
—The CleanUp(G) operation is modified to delete those intermediate nodes which do
not have a path leading to a final node.
3 These

two categories are completely orthogonal to the labeling criterion of the nodes.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

·

16

Uday Khedker et al.
AIn(i)

i

0/

1
2
3
4

5

D
D
D
D

D

6

D

D

7

AOut(i)
D

D

D

x ,
x ,
x ,

x ,

ED
w ,
ED
w ,
ED
w ,
ED
w ,

y ,

x

x ,

w

ED
,

y ,

x

x ,

w

y ,

l4

l4

ED
,

x

x ,

x

r3

x ,

x

r3

x ,

x

r3

x ,

x

r3

E
x ,

x

r3

E
x ,

ED
l4 ,

x

r3

y ,

y

E

D

E

D

E
E
E
E

D
D
D

,

D

D

,

D

D

,
l6

E D

x ,

w

x ,

w

x ,
x ,
y ,
x ,

E

ED
,
ED
w ,
ED
w ,
x

l4
ED
w ,

x

r3

x ,

x

r3

x ,

x

r3

E

x ,

x

r3

E
E

E
E

y ,

x

x ,

w

x ,

x

r3

y ,

ED
x
l4 ,
ED
x ,
w ,
ED
x
l4 ,

y ,

y

x

r3

y ,

y

x ,
y ,

l4

ED
,

E

x ,

E

E

,

,
l6

E

l6

E

,

Fig. 8. Alias pairs for the running example from Figure (1).

(2) Link Alias Closure. To discover all link aliases of a live access we compute link alias
closure as defined below. Given an alias set AS , the set of link aliases of an access
path ρx f is the least solution of:
LnA(ρx f , AS ) = {ρy f | hρx , ρy i ∈ AS or hρx , ρy i ∈ LnA(ρx , AS)}
Given an alias pair hgx , gy i link aliases of Gx rooted at y are included in the access
graph Gy as follows:
LnG(Gy , Gx , hgx , gy i) = Gy ⊎ (gy , my )# ((Gx /(gx , mx ))−εRG )

(7)

where my and mx are the singleton sets containing the final nodes of gy and gx respectively. εRG has to be removed from set of remainder graphs because we want to
transfer non-empty links only. Complete liveness is computed as the least solution of
the following equations
LInv (i) = TLInv (i)

]

LnG (LInv (i), LInu (i), hgv , gu i)

hgv ,gu i∈AIn(i)


 G (v ∗)





EG ⊎ LnG (LOutv (i), LOutu (i), hgv , gu i)
LOutv (i) =

 ]



LInv (s)



i = Exit, v ∈ Globals
or v ∈ Params
i = Exit, v 6∈ Globals,
hgv , gu i ∈ AOut(i)
otherwise

s∈succ(i)

where TLInv (i) is same as ELInv (i) except that ELOutv (i) is replaced by LOutv (i) in
the main equation (equation 4) and in the computation of Transfer (equation 6).
E XAMPLE 3.2. Figure 7 shows the may-alias information for our running example
from Figure 1. Observe that the access graphs used for storing alias information have
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

·

Heap Reference Analysis Using Access Graphs

LOut(i)

i

LIn(i)
w

r3

l7

r3

x

l7

7
y

w

r3

l7

r3

x

l7

6
y

5

4

3

2

1

w
y

l6

w

r3

l4

y

l6

w

r3

w

r3

r3

x

r3

l6

l4

l6

z

x

l4

l6

w

r3

y

l6

l6

w

r3

l7
x
l6

r3

w
l4

r3

l7

l7
l4

x

r3

l6

l4

x
l6

r3

w
l4

l6

r3

l7

l7
l4

x

r3

l6

l4

l4

x

r3

l6

l4

x
l6

x
l6

r3
l4

l6

l7

l7

x
l6

r3
l4

l6

l7

r3

x
l4

l6

l7

l7

l4

l6

l7

l7

l7

l7

l6

z

l4

l6

l7

l7

l4

y

r3

l6

l7

l4

r3

l7

l7

l4

z

l7

l7

l4

w

w

z

r3

17

l6

r3
l4

l6

Fig. 9. Liveness access graphs including implicit liveness information for the program in Figure 1. Gray nodes
are nodes included by link-alias computation. Intermediate nodes are shown with dotted lines.

only the last node as final and all other nodes as intermediate. Figure 9 shows the liveness
access graphs augmented with implicit liveness.
✷
Observe that in the presence of cyclic data structures, we will get alias pairs of the
form hρ, ρ σi. If a link in the cycle is live then the link alias closure will ensure that all
possible links are marked live by creating cycles in the access graphs. This may cause
approximation but would be safe.
3.2 Availability and Anticipability of Access Paths
Example 3.1 shows that safety of inserting an assignment αx = null at a program point p
requires that whenever control reaches p, every prefix of Base(ρx ) has a non-null l-value.
Such an access path is said to be accessible at p. Our use of accessibility ensures the
preservation of semantics in the following sense: Consider an execution path which does
not have a dereferencing exception in the unoptimized program. Then the proposed optiACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

18

·

Uday Khedker et al.

Statement s
αx = αy

AvKills
{ρz

αx = f (αy ) {ρz
αx = new {ρz
αx = null {ρz
use αy .d
return αy
other

AvDirects

AvTransfer s (X)

∗ | ρz ∈ LnA(ρx ,AIn(s))} Prefixes(Base(ρx )) {ρx
∪Prefixes(Base(ρy ))
∗ | ρz ∈ LnA(ρx ,AIn(s))} Prefixes(Base(ρx ))
∗ | ρz ∈ LnA(ρx ,AIn(s))}
Prefixes(ρx )
∗ | ρz ∈ LnA(ρx ,AIn(s))} Prefixes(Base(ρx ))
0/
Prefixes(ρy )
0/
Prefixes(Base(ρy ))
0/
0/

σ | ρy

σ ∈ X}

0/
0/
0/
0/
0/
0/

Fig. 10. Flow functions for availability. AIn(s) denotes the set of may-aliases at the entry of s.

mization will also not have any dereferencing exception in the same execution path.
3.2.1 Defining Availability and Anticipability. We define an access path ρx to be accessible at p if all of its prefixes are available or anticipable at p:
—An access path ρx is available at a program point p, if along every path reaching p,
there exists a program point p′ such that Frontier (ρx ) is either dereferenced or assigned
a non-null l-value at p′ and is not made null between p′ to p.
—An access path ρx is anticipable at a program point p, if along every path starting from
p, Frontier (ρx ) is dereferenced before being assigned.
Since both these properties are all paths properties, all may-link aliases of the left hand
side of an assignment need to be killed. Conversely, these properties can be made more
precise by including must-aliases in the set of anticipable or available paths.
Recall that comparisons in conditionals consists of simple variables only. The use of
these variables does not involve any dereferencing. Hence a comparison x == y does not
contribute to accessibility of x or y.
Definition 3.1. Availability. The set of paths which are available at a program point p,
denoted by Avail p , is defined as follows.
Avail p =

\

(PathAvailψp )

ψ∈Paths(p)
ψ

where, ψ ∈ Paths(p) is a control flow path Entry to p and PathAvail p denotes the availability at p along ψ and is defined as follows. If p is not Entry of the procedure being
analyzed, then let the statement which precedes it be denoted by s and the program point
immediately preceding s be denoted by p′ . Then,

0/
p is Entry
PathAvailψp =
ψ
StatementAvails (PathAvail p′ ) otherwise
where the flow function for s is defined as follows:
StatementAvails (X) = (X − AvKills ) ∪ AvDirects ∪ AvTransfers (X)
AvKills denotes the sets of access paths which cease to be available after statement s,
AvDirects denotes the set of access paths which become available due to local effect of
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

·

Heap Reference Analysis Using Access Graphs

Statement s
αx = αy

AnKills
{ρz

αx = f (αy ) {ρz
αx = new
αx = null
use αy .d
return αy
other

{ρz
{ρz

Fig. 11.

19

AnTransfers (X)

AnDirects

∗ | ρz ∈ LnA(ρx ,AOut(s))} Prefixes(Base(ρx )) {ρy
∪Prefixes(Base(ρy ))
∗ | ρz ∈ LnA(ρx ,AOut(s))} Prefixes(Base(ρx ))
∪Prefixes(Base(ρy ))
∗ | ρz ∈ LnA(ρx ,AOut(s))} Prefixes(Base(ρx ))
∗ | ρz ∈ LnA(ρx ,AOut(s))} Prefixes(Base(ρx ))
Prefixes(ρy )
0/
Prefixes(Base(ρy ))
0/
0/
0/

σ | ρx

σ ∈ X}

0/
0/
0/
0/
0/
0/

Flow functions for anticipability. AOut(s) denotes the set of may-aliases at the exit of s.

s and AvTransfers (X) denotes the the set of access paths which become available after s
due to transfer. They are defined in Figure 10.
✷
In a similar manner, we define anticipability of access paths.
Definition 3.2. Anticipability. The set of paths which are anticipable at a program
point p, denoted by Ant p is defined as follows.
Ant p =

\

(PathAntψp )

ψ∈Paths(p)
ψ

where, ψ ∈ Paths(p) is a control flow path p to Exit and PathAvail p denotes the anticipability at p along ψ and is defined as follows. If p is Exit then let the statement which
follows it be denoted by s and the program point immediately following s be denoted by
p′ . Then,

0/
p is Exit
ψ
PathAnt p =
ψ
StatementAnts (PathAnt p′ ) otherwise
where the flow function for s is defined as follows:
StatementAnts (X) = (X − AnKills ) ∪ AnDirects ∪ AnTransfers (X)
AnKills denotes the sets of access paths which cease to be anticipable before statement s,
AnDirects denotes the set of access paths which become anticipable due to local effect of s
and AnTransfers (X) denotes the the set of access paths which become anticipable before s
due to transfer. They are defined in Figure 11.
✷
Observe that both Avail p and Ant p are prefix-closed.
3.2.2 Data Flow Analyses for Availability and Anticipability. Availability and Anticipability are all (control-flow) paths properties in that the desired property must hold along
every path reaching/leaving the program point under consideration. Thus these analyses
identify access paths which are common to all control flow paths including acyclic control
flow paths. Since acyclic control flow paths can generate only acyclic4 and hence finite
4 In the

presence of cycles in heap, considering only acyclic access paths results in an approximation which is safe
for availability and anticipability.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

20

·

Uday Khedker et al.

i

AvIn(i)

1
2
3
4
5
6
7

0/
0/
{x}
{x}
{x}
{x, z}
{x, z}
Fig. 12.

AvOut(i)
0/
{x}
0/
{x}
{x, z}
{x, z}
{x, x l, y, z}

AnIn(i)
{x}
{x}
{x, x
{x, x
{x, x
{x, x
{x, x

r}
l, x l l}
l, y, y l}
l, y, y l, z}
l, y, z}

AnOut(i)
{x}
{x}
{x}
{x, x l, y, y l}
{x, x l, y, y l, z}
{x, x l, y, z}
0/

Availability and anticipability for the program in Figure 1.

access paths, anticipability and availability analyses deal with a finite number of access
paths and summarization is not required.
Thus there is no need to use access graphs for availability and anticipability analyses.
The data flow analysis can be performed using a set of access paths because the access
paths are bounded and the sets would be finite. Moreover, since the access paths resulting
from anticipability and availability are prefix-closed, they can be represented efficiently.
The data flow equations are same as the definitions of these analyses except that definitions are path-based (i.e. they define MoP solution) while the data flow equations are
edge-based (i.e. they define MFP solution) as is customary in data flow analysis. In other
words, the data flow information is merged at the intermediate points and availability and
anticipability information is derived from the corresponding information at the preceding
and following program point respectively. As observed in appendix A, the flow functions in
availability and anticipability analyses are non-distributive hence MoP and MFP solutions
may be different.
For brevity, we omit the data flow equations. We use the universal set of access paths
as the initial value for all blocks other than Entry for availability analysis and Exit for
anticipability analysis.
E XAMPLE 3.3. Figure 12 gives the availability and anticipability information for program in Figure 1. AvIn(i) and AvOut(i) denote the set of available access paths before
and after the statement i, while AnIn(i) and AnOut(i) denote the set of anticipable access
paths before and after the statement i.
✷
4. NULL ASSIGNMENT INSERTION
We now explain how the analyses described in preceding sections can be used to insert
appropriate null assignments to nullify dead links. The inserted assignments should be
safe and profitable as defined below.
Definition 4.1. Safety. It is safe to insert an assignment α = null at a program point p if
and only if ρ is not live at p and Base(ρ) can be dereferenced without raising an exception.
An access path ρ is nullable at a program point p if and only if it is safe to insert
assignment α = null at p.
Definition 4.2. Profitability. It is profitable to insert an assignment α = null at a program point p if and only if no proper prefix of ρ is nullable at p and the link corresponding
to Frontier (ρ) is not made null before execution reaches p.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

·

21

Note that profitability definition is strict in that every control flow path may nullify a
particular link only once. Redundant null assignments on any path are prohibited. Since
control flow paths have common segments, a null assignment may be partially redundant
in the sense that it may be redundant along one path but not along some other path. Such
null assignments will be deemed unprofitable by Definition 4.2. Our algorithm may not be
able to avoid all redundant assignments.
E XAMPLE 4.1. We illustrate some situations of safety and profitability for the program
in Figure 1.
—Access path x lptr lptr is not nullable at the entry of 6. This is because x lptr lptr is
implicitly live, due to the use of y lptr in 6. Hence it is not safe to insert x.lptr.lptr = null
at the entry of 6.
—Access path x rptr is nullable at the entry of 4, and continues to be so on the path from
the entry of 4 to the entry of 7. The assignment x.rptr = null is profitable only at the
entry of 4.
✷
Section 4.1 describes the criteria for deciding whether a given path ρ should be considered for a null assignment at a program point p. Section 4.2 describes how we create the
set of candidate access paths. Let Live(p), Available(p), and Anticipable(p) denote set of
live paths, set of available paths and set of anticipable paths respectively at program point
p.5 They refer to LIn(i), AvIn(i), and AnIn(i) respectively when p is Ini . When p is Outi ,
they refer to LOut(i), AvOut(i), and AnOut(i) respectively.
4.1 Computing Safety and Profitability
To find out if ρ can be nullified at p, we compute two predicates: Nullable and Nullify.
Nullable(ρ, p) captures the safety property—it is true if insertion of assignment α = null
at program point p is safe.
Nullable(ρ, p) = ρ 6∈ Live(p) ∧ Base(ρ) ∈ Available(p) ∪ Anticipable(p)

(8)

Nullify(ρ, p) captures the profitability property—it is true if insertion of assignment
α = null at program point p is profitable. To compute Nullify, we note that it is most
profitable to set a link to null at the earliest point where it ceases to be live. Therefore,
the Nullify predicate at a point has to take into account the possibility of null assignment
insertion at previous point(s). For a statement i in the program, let Ini and Outi denote the
program points immediately before and after i. Then,
ρ′ 6∈ Live(Outi ))

^

Nullify(ρ, Outi ) = Nullable(ρ, Outi ) ∧ (

ρ′ ∈ProperPrefix(ρ)

∧ (¬Nullable(ρ, Ini ) ∨ ¬Transp(ρ, i))
^

Nullify(ρ, Ini ) = Nullable(ρ, Ini ) ∧ (

(9)

ρ 6∈ Live(Ini ))
′

ρ′ ∈ProperPrefix(ρ)

∧ ρ 6= lhs(i) ∧ (¬

^

Nullable(ρ, Out j ))

(10)

j∈pred(i)

5 Because availability and anticipability properties are prefix closed, Base(ρ) ∈ Available(p) ∪ Anticipable(p)
guarantees that all proper prefixes of ρ are either available or anticipable.

ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

22

·

Uday Khedker et al.

where, Transp(ρ, i) denotes that ρ is transparent with respect to statement i, i.e. no prefix of
ρ is may-link-aliased to the access path corresponding to the lhs of statement i at Ini . lhs(i)
denotes the access path corresponding to the lhs access expression of assignment in statement i. pred(i) is the set of predecessors of statement i in the program. ProperPrefix(ρ) is
the set of all proper prefixes of ρ.
We insert assignment α = null at program point p if Nullify(ρ, p) is true.
4.2 Computing Candidate Access Paths for null Insertion
The method described above only checks whether a given access path ρ can be nullified
at a given program point p. We can generate the candidate set of access paths for null
insertion at p as follows: For any candidate access path ρ, Base(ρ) must either be available or anticipable at p. Additionally, all simple access paths are also candidates for null
insertions. Therefore,
Candidates(p) = {ρ f | ρ ∈ Available(p) ∪ Anticipable(p), f ∈ OutField(ρ)}
∪ {ρ | ρ is a simple access path }
(11)
Where OutField(ρ) is the set of fields which can be used to extend access path ρ at p. It
can be obtained easily from the type information of the object Target(ρ) at p.
Note that all the information required for equations (8), (9), (10), and (11) is obtained
from the result of data flow analyses described in preceding sections. Type information of
objects required by equation (11) can be obtained from the front end of compiler. Transp
uses may alias information as computed in terms of pairs of access graph.
E XAMPLE 4.2. Figure 13 lists a trace of the null insertion algorithm for the program
in Figure 1.
✷
4.3 Reducing Redundant null Insertions
Consider a program with an assignment statement i : αx = αy . Assume a situation where,
for some non-empty suffix σ, both Nullify(ρy σ, Ini ) and Nullify(ρx σ, Outi ) are true. In
that case, we will be inserting αy .σ = null at Ini and αx .σ = null at Outi . Clearly, the
latter null assignment is redundant in this case and can be avoided by checking if ρy σ is
nullable at Ini .
If must-alias analysis is performed then redundant assignments can be reduced further.
Since must-link-alias relation is symmetric, reflexive, and transitive and hence an equivalence relation, the set of candidate paths at a program point can be divided into equivalence
classes based on must-link-alias relation. Redundant null assignments can be reduced by
nullifying at most one access path in any equivalence class.
5. CONVERGENCE OF HEAP REFERENCE ANALYSIS
The null assignment insertion algorithm makes a single traversal over the control flow
graph. We show the termination of liveness analysis using the properties of access graph
operations. Termination of availability and anticipability can be shown by similar arguments over finite sets of bounded access paths. Termination of alias analysis follows from
Hind et al. [1999].
5.1 Monotonicity
For a program there are a finite number of basic blocks, a finite number of fields for any
root variable, and a finite number of field names in any access expression. Hence the
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

·

Heap Reference Analysis Using Access Graphs

p, i
In,1

lhs(i)

Candidates(p)
{w, x, y, z, x l, x r}

w

Out,1 {w, x, y, z, x l, x r}
In,2

{w, x, y, z, x l, x r}

{w}
0/

Out,2 {w, x, y, z, x l, x r}
In,3

{w, x, y, z, x l, x r,
x r l, x r r}

x
{x, x l,
x r}

Out,3 {w, x, y, z, x l, x r}

In,4

Out,4

In,5

Out,5

In,6

Out,6

In,7

Out,7

{w, x, y, z, x l, x
x l l, x l r,
x l l l,
x l l r}
{w, x, y, z, x l, x
y l, y r,
x l l, x l r,
y l l, y l r}
{w, x, y, z, x l, x
y l, y r,
x l l, x l r,
y l l, y l r}
{w, x, y, z, x l, x
y l, y r, z l, z
x l l, x l r,
y l l, y l r}
{w, x, y, z, x l, x
y l, y r, z l, z
x l l, x l r,
y l l, y l r}
{w, x, y, z, x l, x
y l, y r, z l, z
x l l, x l r}
{w, x, y, z, x l, x
y l, y r, z l, z
x l l, x l r}
{w, x, y, z, x l, x
y l, y r, z l, z
x l l, x l r}

¬Transp(ρ, i)

r,
y
{y, y l,
y r,
y l l,
y l r}

r,

r,
z
r,
r,

r,
r,

{z}

y

r,
r,
r,
r,
r,
r,

{y, y l,
y r}
0/

23

Nullable(ρ, p)

Nullify(ρ, p)

{w, y, z}

{y, z}

{w, y, z}

{w}

{w, y, z}

0/

{w, y, z}

0/

{w, y, z, x l}

{x l}

{w, y, z}

0/

{w, y, z, x r,
x l r,
x l l l,
x l l r}

{x
x
x
x

{w, z, x r, y r,
x l r,
y l l, y l r}

{y r,
y l l,
y l r}

{w, z, x r, y r,
x l r,
y l l, y l r}

0/

{w, x r, y r,
z l, z r, x l r,
y l l, y l r}

{z l, z r}

{w, x r, y r,
z l, z r, x l r,
y l l, y l r}

0/

{w, x r, y l,
y r, z l, z r,
x l l, x l r}

{y l, y r,
x l l}

{w, x r, y l,
y r, z l, z r,
x l l, x l r}

0/

{w, x, y, z, x l, x r,
y l, y r, z l, z r,
x l l, x l r}

{x, y, z}

r,
l r,
l l l,
l l r}

Fig. 13. Null insertion for the program in Figure 1.

ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

24

·

Uday Khedker et al.

Operation
Union

Monotonicity
G1 ⊑G G′1 ∧ G2 ⊑G G′2 ⇒ G1 ⊎ G2 ⊑G G′1 ⊎ G′2
G1 ⊑ G G2 ⇒ G1 ⊖ ρ ⊑ G G2 ⊖ ρ

Path Removal

G1 ⊑G G2 ⇒ G1 /(G,M) ⊑RS G2 /(G,M)

Factorization
Extension
Link-Alias
Closure

RS1 ⊑RS RS2 ∧ G1 ⊑G G2 ∧ M1 ⊆ M2 ⇒ (G1 ,M1 )# RS1 ⊑G (G2 ,M2 )# RS2
G1 ⊑G G′1 ∧ G2 ⊑G G′2 ⇒ LnG(G1 ,G2 ,hgx ,gy i) ⊑S LnG(G′1 ,G′2 ,hgx ,gy i)
Fig. 14.

Monotonicity of Access Graph Operations

.

number of access graphs for a program is finite. Further, the number of nodes and hence
the size of each access graph, is bounded by the number of labels which can be created for
a program.
Access graphs for a variable x form a complete lattice with a partial order ⊑G induced by
⊎ . Note that ⊎ is commutative, idempotent, and associative. Let G = hx, NF , NI , Ei and
G′ = hx, NF′ , NI′ , E ′ i where subscripts F and I distinguish between the final and intermediate
nodes. The partial order ⊑G is defined as



G ⊑G G′ ⇔ NF′ ⊆ NF ∧ NI′ ⊆ (NF ∪ NI ) ∧ E ′ ⊆ E

Clearly, G ⊑G G′ implies that G contains all access paths of G′ . We extend ⊑G to a set of
access graphs as follows:
S1 ⊑S S2 ⇔ ∀G2 ∈ S2 , ∃G1 ∈ S1 s.t. G1 ⊑G G2

It is easy to verify that ⊑G is reflexive, transitive, and antisymmetric. For a given variable
x, the access graph EG forms the ⊤ element of the lattice while the ⊥ element is a greatest
lower bound of all access graphs.
The partial order over access graphs and their sets can be carried over unaltered to remainder graphs (⊑RG ) and their sets (⊑RS ), with the added condition that εRG is incomparable to any other non empty remainder graph.
Access graph operations are monotonic as described in Figure 14. Path removal is monotonic in the first argument but not in the second argument. Similarly factorization is monotonic in the first argument but not in the second and the third argument. However, we show
that in each context where they are used, the resulting functions are monotonic:
(1) Path removal is used only for an assignment αx = αy . It is used in liveness analysis
and its second argument is ρx which is constant for any assignment statement αx = αy .
Thus the resulting flow functions are monotonic.
(2) Factorization is used in the following situations:
(a) Link-alias closure of access graphs. From equation (7) it is clear LnG is monotonic in the first argument (because it is used in ⊎ ) and the second argument
(because it is supplied as the first argument of factorization). The third and the
fourth arguments of LnG are linear access graphs containing a single path and
hence are incomparable with any other linear access graph. Thus link-alias computation is monotonic in all its arguments.
(b) Liveness analysis. Factorization is used for the flow function corresponding to
an assignment αx = αy and its second argument is G (ρx ) while its third arguACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

·

25

ment is lastNode(G (ρx )) both of which are constant for any assignment statement
αx = αy . Thus, the resulting flow functions are monotonic.
Thus we conclude that all flow functions are monotonic. Since lattices are finite, termination of heap reference analysis follows.
Appendix A discusses the distributivity of flow functions.
5.2 Complexity
This section discusses the issues which influence the complexity and efficiency of performing heap reference analysis. Empirical measurements which corroborate the observations
made in this section are presented in Section 7.
The data flow frameworks defined in this paper are not separable [Khedker 2002] because the data flow information of a variable depends on the data flow information of other
variables. Thus the number of iterations over control flow graph is not bounded by the
depth of the graph [Aho et al. 1986; Hecht 1977; Khedker 2002] but would also depend on
the number of root variables which depend on each other.
Although we consider each statement to be a basic block, our control flow graphs retain
only statements involving references. A further reduction in the size of control flow graphs
follows from the fact that successive use statements need not be kept separate and can be
grouped together into a block which ends on a reference assignment.
The amount of work done in each iteration is not fixed but depends on the size of access
graphs. Of all operations performed in an iteration, only CFN(G, G′ ) is costly. Conversion
to deterministic access graphs is also a costly operations but is performed for a single pass
during null assignment insertion. In practice, the access graphs are quite small because of
the following reason: Recall that edges in access graphs capture dependence of a reference
made at one program point on some other reference made at another point (Section 2.4.1).
In real programs, traversals involving long dependences are performed using iterative constructs in the program. In such situations, the length of the chain of dependences is limited
by the process of summarization because summarization treats nodes with the same label
as being identical. Thus, in real programs chains of such dependences, and hence the access graphs, are quite small in size. This is corroborated by Figure 16 which provides the
empirical data for the access graphs in our examples. The average number of nodes in
these access graphs is less than 7 while the average number of edges is less than 12. These
numbers are still smaller in the interprocedural analysis. Hence the complexities of access
graph operations is not a matter of concern.
6. SAFETY OF NULL ASSIGNMENT INSERTION
We have to prove that the null assignments inserted by our algorithm (Section 4) in a
program are safe in that they do not alter the result of executing the program. We do this
by showing that (a) an inserted statement itself does not raise a dereferencing exception,
and (b) an inserted statement does not affect any other statement, both original and inserted.
We use the subscripts b and a for a program point p to denote “before” and “after” in
an execution order. Further, the corresponding program points in the original and modified
program are distinguished by the superscript o and m. The correspondence is defined as
follows: If pm is immediately before or after an inserted assignment α = null, po is the
point where the decision to insert the null assignment is taken. For any other pm , there is
an obvious po .
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

26

·

Uday Khedker et al.

We first assert the soundness of availability, anticipability and alias analyses without
proving them.
L EMMA 6.1. (Soundness of Availability Analysis). Let AVpa be the set of access paths
available at program point pa . Let ρ ∈ AVpa . Then along every path reaching pa , there exists a program point pb , such that the link represented by Frontier(ρ) is either dereferenced
or assigned a non-null l-value at pb and is not made null between pb and pa .
L EMMA 6.2. (Soundness of Anticipability Analysis). Let AN p be the set of access
paths anticipable at program point p. Let ρ ∈ AN p . Then along every path starting from p,
the link represented by Frontier (ρ) is dereferenced before being assigned.
For semantically valid input programs (i.e. programs which do not generate dereferencing exceptions), Lemma 6.1 and Lemma 6.2 guarantee that if ρ is available or anticipable
at p, Target(ρ) can be dereferenced at p.
L EMMA 6.3. (Soundness of Alias Analysis). Let Frontier (ρx ) represents the same link
as Frontier (ρy ) at a program point p during some execution of the program. Then linkalias computation of ρx at p would discover ρy to be link-aliased to ρx .
For the main claim, we relate the access paths at pa to the access paths at pb by incorporating the effect of intervening statements only, regardless of the statements executed
before pb . In some execution of a program, let ρ be the access path of interest at pa and the
sequence of statements between pb and pa be s.6 Then T (s, ρ) represents the access path
at pb which, if non-E , can be used to access the link represented by Frontier (ρ). T (s, ρ)
captures the transitive effect of backward transfers of ρ through s. T is defined as follows:

ρ
s is a use statement




ρ
s is αx = . . . and ρx is not a prefix of ρ




E
s is αx = New and ρ = ρx σ




E
s is αx = null and ρ = ρx σ




ρ
σ
s
is αx = αy and ρ = ρx σ

y



ρ
s
is the function call αx = f (αy ) and



Root(ρ) is a global variable
T (s, ρ) =
s is the function call αx = f (αy ), ρ = z σ and
ρy σ




z is the formal parameter of f




ρ
s is the return statement return(αz ) and




Root(ρ)
is a global variable




σ
s
is
the
return
statement return(αz ), ρ = ρx σ and
ρ

z



the
corresponding
call is αx = f (αy )



T (s1 , T (s2 , ρ)) s is a sequence s1 ; s2
L EMMA 6.4. (Liveness Propagation). Let ρa be in some explicit liveness graph at pa .
Let the sequence of statements between pb to pa be s. Then, if T (s, ρa ) = ρb and ρb is not
E , then ρb is in some explicit liveness graph at pb .
P ROOF. The proof is by structural induction on s. Since ρb is non-E , the base cases are:
(1) s is a use statement. In this case ρb = ρa .
6 When s is a function call α = f (α ), p is the entry point of f and p is the program point just before the
x
y
a
b
statement s in the caller’s body. Analogous remark holds for the return statement.

ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

·

27

(2) s is an assignment αx = . . . such that ρx is not a prefix of ρa . Here also ρb = ρa .
(3) s is an assignment αx = αy such that ρa = ρx σ. In this case ρb = ρy σ.
(4) s is the function call αx = f (αy ). The only interesting case is when ρa = z σ, where
z is the formal parameter of f . In this case, ρb = ρy σ.
(5) s is the return statement return(αz ). The only interesting case is when ρa = ρx σ, and
the corresponding call is αx = f (αy ). In this case, ρb = ρz σ.
For (1) and (2), since ρa is not in ELKillPath, ρb is in some explicit liveness graph at pb .
For (3), from Equation (6), ρb is in some explicit liveness graph at pb . For (4) and (5), the
result follows from the fact that Summary(ρy ) and Summary(ρz ) are in the explicit liveness
graph of the program points before the call and return statements respectively.
For the inductive step, assume that the lemma holds for s1 and s2 . From the definition
of T , there exists a non-E ρi at the intermediate point pi between s1 and s2 , such that
ρi = T (s2 , ρa ) and ρb = T (s1 , ρi ). Since ρa is in some explicit liveness graph at pa , by
the induction hypothesis, ρi must be in some explicit liveness graph at pi . Further, by the
induction hypothesis, ρb must be in some explicit liveness graph at pb .
L EMMA 6.5. Every access path which is in some liveness graph at pm
b is also in some
liveness graph at pob .
P ROOF. If an extra explicitly live access path is introduced in the modified program,
it could be only because of an inserted assignment α = null at some pm
a . The only access
paths which this statement can add to an explicit liveness graph are the paths corresponding
the proper prefixes of α. However, the algorithm selects α for nullification only if the
access paths corresponding to all its proper prefixes are in some explicit liveness graph.
Therefore every access path which is in some explicit liveness graph at pm
a is also in some
o.
explicit liveness graph at poa . The same relation would hold at pm
and
p
b
b
If an extra live access path is introduced in the modified program, it could be only because of an inserted assignment α = null at some pm
a . The only access paths which this
statement can add to an liveness graphs are LnA(ρ′ , AS m ), where ρ′ is a proper prefix of
ρ and AS m represents the alias set at pm
a . However, the algorithm selects α for nullification at pm
only
if
the
access
paths
corresponding
to all its proper prefixes are in some
a
liveness graph at poa . As liveness graphs are closed under link aliasing, this implies that
the liveness graph at poa includes paths LnA(ρ′ , AS o ), where AS o represents the alias set at
poa . Since inserted statements can only kill aliases, AS m ⊆ AS o . Thus, LnA(ρ′ , AS m ), the
paths resulting out of insertion, are also in the liveness graph at poa . Therefore every access
o
path which is in some liveness graph at pm
a is also in some liveness graph at pa . The same
m
o
relation would hold at pb and pb .
T HEOREM 6.1. (Safety of null insertion). Let the assignment αb = null be inserted by
the algorithm immediately before pm
b . Then:
(1) Execution of αb = null does not raise any exception due to dereferencing.
(2) Let αa be used immediately after pm
a (in an original statement or an inserted null
assignment). Then, execution of αb = null cannot nullify any link used in αa .
P ROOF. We prove the two parts separately.
(1) If αb is a root variable, then the execution of αb = null cannot raise an exception.
When αb is not a root variable, from the null assignment algorithm, every proper
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

28

·

Uday Khedker et al.

2600

2600

2400

2400

2200

2200

2000

2000

1800

1800
0

400

800
Loop

1200

1600

2600

0

400

800
DLoop

1200

1600

2400

2400

2200

2200
2000

2000
1800

1800
0

400

800
1200
CReverse

1600

2400

0

800

1600 2400 3200 4000
BiSort

20000
16000
12000
8000
4000
0

2200
2000
1800
1600
0

400

800 1200 1600 2000
TreeAdd

0

50000
100000
GCBench

150000

X axis indicates measurement instants in milliseconds. Y axis indicates heap usage in KB. Solid line represents
memory required for original program while dashed line represents memory for the modified program. Observe
that the modified program executed faster than the original program in each case.
Fig. 15. Temporal plots of memory usages.

prefix ρ′ of ρb is either anticipable or available. From the soundness of both these
analyses, Target(ρ′ ) exists and the execution of αb = null cannot raise an exception.
(2) We prove this by contradiction. Let s denote the sequence of statements between pm
b
b
a
and pm
a . Assume that α = null nullifies a link used in α . This is possible only if
there exists a prefix ρ′ of ρa such that T (s, ρ′ ) shares its frontier with ρb at pm
b . By
Lemma 6.4, T (s, ρ′ ) must be in some explicit liveness graph at pm
b . From Lemma 6.3
b
and the definition of liveness, ρb is in some liveness graph at pm
b . By Lemma 6.5, ρ is
also in some liveness graph at pob . Thus a decision to insert αb = null cannot be taken
at pob .

7. EMPIRICAL MEASUREMENTS
In order to show the effectiveness of heap reference analysis, we have developed proof-ofconcept implementations of heap reference analysis at two levels: One at the interprocedural level and the other at the intraprocedural level.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

·

29

7.1 Experimentation Methodology
Our intraprocedural analyzer, which predates the interprocedural version is an evidence
of the effectiveness of intraprocedural analysis. It was implemented using XSB-Prolog7.
The measurements were made on a 800 MHz Pentium III machine with 128 MB memory
running Fedora Core release 2. The benchmarks used were Loop, DLoop, CReverse,
BiSort, TreeAdd and GCBench. Three of these (Loop, DLoop and CReverse) are similar
to those in [Shaham et al. 2003]. Loop creates a singly linked list and traverses it, DLoop
is doubly linked list variation of the same program, CReverse reverses a singly linked
list. BiSort and TreeAdd are taken from Java version of Olden benchmark suite [Carlisle
1996]. GCBench is taken from [Boehm ].
For measurements on this implementation, the function of interest in a given Java program was manually translated to Prolog representation. This allowed us to avoid redundant
information like temporaries, empty statements etc. resulting in a compact representations
of programs. The interprocedural information for this function was approximated in the
Prolog representations in the following manner: Calls to non-recursive functions were
inlined and calls to recursive functions were replaced by iterative constructs which approximated the liveness property of heap manipulations in the function bodies. The result of
the analysis was used to manually insert null assignments in the original Java programs to
create modified Java programs.
Manual interventions allowed us to handle procedure calls without performing interprocedural analysis. In order to automate the analysis and extend it to interprocedural level,
we used SOOT [Vallée-Rai et al. 1999] which has built in support for many of our requirements. However, compared to the Prolog representation of programs, the default Jimple
representation used by SOOT is not efficient for our purposes because it introduces a large
number of temporaries and contains all statements even if they do not affect heap reference
analysis.
As was described earlier, our interprocedural analysis is very simplistic. Our experience shows that imprecision of interprocedural alias analysis increases the size of alias
information thereby making the analysis inefficient apart from reducing the precision of
the resulting information. This effect has been worsened by the fact that SOOT introduces
a large number of temporary variables. Besides, the complete alias information is not
required for our purposes.
We believe that our approach can be made much more scalable by
—Devising a method of avoiding full alias analysis and computing only the required alias
information, and
—Improving the Jimple representation by eliminating redundant information, combining
multiple successive uses into a single statement etc.
The implementations, along with the test programs (with their original, modified, and
Prolog versions) are available at [Karkare 2005].
7.2 Measurements and Observations
Our experiments were directed at measuring:
7 Available

from http://xsb.sourceforge.net.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

30

·

Uday Khedker et al.
Intraprocedural analysis of selected method (Prolog Implementation)

Program
Name.Function

Analysis
Time
#Iter
(sec)

Loop.main
DLoop.main
CReverse.main
BiSort.main
TreeAdd.addtree
GCBench.Populate

5
5
5
6
6
6

0.082
1.290
0.199
0.083
0.255
0.247

#G

Access Graphs
Nodes
Edges
Avg
Max
Avg
Max

172
332
242
63
132
136

1.13
2.74
1.41
2.16
2.84
2.73

2
4
4
3
7
7

0.78
5.80
1.10
3.81
4.87
4.63

2
10
6
6
14
14

#null
9
11
8
5
7
7

Execution
Time (sec)
Orig.
Mod.
1.503
1.594
1.512
3.664
1.976
132.99

1.388
1.470
1.414
3.646
1.772
88.86

Interprocedural analysis of all methods (SOOT Implementation)
Program
Name
Loop
DLoop
CReverse
BiSort
TreeAdd
GCBench

LOC
in
Jimple

#
methods

Analysis
Time
(sec.)

83
78
85
466
228
226

2
2
2
12
4
9

0.558
20.660
1.833
1.498
0.797
1.447

Access Graph Stats
Nodes
Edges
Max
Avg
Max
Avg
2
5
3
7
6
4

1.24
1.45
1.39
1.29
1.29
1.13

2
12
4
10
7
5

0.39
0.76
0.51
0.40
0.46
0.16

#null
12
12
12
77
34
56

Execution
Time (sec)
Orig.
Mod.
1.868
1.898
1.930
1.519
2.704
122.731

1.711
1.772
1.929
1.524
2.716
60.372

- #Iter is the maximum number of iterations taken by any analysis.
- Analysis Time is the total time taken by all analyses.
- #G is total number of access graphs created by alias analysis and liveness analysis. Prolog implementation
performs alias analysis also using access graphs.
- Max nodes (edges) is the maximum over number of nodes (edges) in all access graphs. In some cases, maximum number nodes/edges is more in case of intraprocedural analysis due to presence of longer paths in
explicitly supplied boundary information, which gets replaced by a single * node in interprocedural analysis.
- Avg nodes (edges) is the average number of nodes (edges) over all access graphs.
- #null is the number of inserted null assignments.
Fig. 16.

Empirical measurements of proof-of-concept implementations of heap reference analyzer.

(1) The efficiency of analysis. We measured the total time required, number of iterations
of round robin analyses, and the number and sizes of access graphs.
(2) The effectiveness of null assignment insertions. The programs were made to create
huge data structures. Memory usage was measured by explicit calls to garbage collector in both modified and original Java programs at specific probing points such as
call sites, call returns, loop begins and loop ends. The overall execution time for the
original and the modified programs was also measured.
The results of our experiments are shown in Figure 15 and Figure 16. As can be seen
from Figure 15, nullification of links helped the garbage collector to collect a lot more
garbage, thereby reducing the allocated heap memory. In case of BiSort, however, the links
were last used within a recursive procedure which was called multiple times. Hence, safety
criteria prevented null assignment insertion within the called procedure. Our analysis could
only nullify the root of the data structure at the end of the program. Thus the memory was
released only at the end of the program.
For interprocedural analysis, class files for both original as well as modified programs
were generated using SOOT. As can be seen from Figure 16, modified programs executed
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

·

31

faster. In general, a reduction in execution time can be attributed to the following two
factors: (a) a decrease in the number of calls to garbage collector and (b) reduction in the
time taken for garbage collection in each call. The former is possible because of availability
of a larger amount of free memory, the latter is possible because lesser reachable memory
needs to be copied.8 In our experiments, factor (a) above was absent because the number of
(explicit) calls to garbage collector were kept same. GCBench showed a large improvement
in execution time after null assignment insertion. This is because GCBench creates large
trees in heap, which are not used in the program after creation and our implementation was
able to nullify left and right subtrees of these trees immediately after their creation. This
also reduced the high water mark of the heap memory requirement.
As explained in Section 5.2, sizes of the access graphs (average number of nodes and
edges) is small. This can be verified from Figure 16. The analysis of DLoop creates a large
number of access graphs because of the presence of cycles in heap. In such a case, a large
number of alias pairs are generated, many of which are redundant. Though it is possible
to reduce analysis time by eliminating redundant alias pairs, our implementation, being a
proof-of-concept implementation, does not do so for sake of simplicity.
Our technique and implementation compares well with the technique and results described in [Shaham et al. 2003]. A conceptual comparison with this method is included in
Section 9.2. The implementation described in [Shaham et al. 2003] runs on a 900 MHz
P-III with 512 MB RAM running Windows 2000. It takes 1.76 seconds, 2.68 seconds and
4.79 seconds respectively for Loop, DLoop and CReverse for null assignment insertion.
Time required by our implementation for the above mentioned programs is given in Figure 16. Our implementation automatically computes the program points for null insertion
whereas their method cannot do so. Our implementation performs much better in all cases.
8. EXTENSIONS FOR C++
This approach becomes applicable to C++ by extending the concept of access graphs to
faithfully represent the C++ memory model. It is assumed that the memory which becomes unreachable due to nullification of pointers is reclaimed by an independent garbage
collector. Otherwise, explicit reclamation of memory can be performed by checking that
no node-alias of a nullified pointer is live.
In order to extend the concept of access graphs to C++, we need to account for two
major differences between the C++ and the Java memory model:
(1) Unlike Java, C++ has explicit pointers. Field of a structure (struct or class) can be
accessed in two different ways in C++:
—using pointer dereferencing (∗.), e.g. (∗x).lptr9 or
—using simple dereferencing (.) , e.g. y.rptr.
We need to distinguish between the two.
(2) Although root variables are allocated on stack in both C++ and Java, C++ allows a
pointer/reference to point to root variables on stack through the use of addressof (&)
operator, whereas Java does not allow a reference to point to stack. Since the root
nodes in access graphs do not have an incoming edge by definition, it is not possible
to use access graphs directly to represent memory links in C++.
8 This
9 This

happens because Java Virtual Machine uses a copying garbage collector.
is equivalently written as x−>lptr.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

32

·

Uday Khedker et al.

We create access graphs for C++ memory model as follows:
(1) We treat dereference of a pointer as a field reference, i.e., ∗ is considered as a field
named deref. For example, an access expression (∗x).lptr is viewed as x.deref.lptr,
and corresponding access path is x deref lptr. The access path for x.lptr is x lptr.
(2) Though a pointer can point to a variable x, it is not possible extract the address of &x,
i.e. no pointer can point to &x. For Java, we partition memory as stack and heap, and
had root variables of access graphs correspond to stack variables. In C++, we partition
the memory as address of variables and rest of the memory (stack and heap together).
We make the roots of access graphs correspond to addresses of variables. A root
&y
d1
l2 represents access
variable y is represented as deref (&y). Thus,
paths &y and &y deref and &y deref l, which correspond to access expressions
&y, y and y.l respectively.
Handling pointer arithmetic and type casting in C++ is orthogonal to above discussion,
and requires techniques similar to [Yong et al. 1999; Cheng and Hwu 2000] to be used.
9. RELATED WORK
Several properties of heap (viz. reachability, sharing, liveness etc.) have been explored in
past; a good review has been provided by Sagiv et al. [2002]. In this section, we review
the related work in the main property of interest: liveness. We are not aware of past work
in availability and anticipability analysis of heap references.
9.1 Liveness Analysis of Heap Data
Most of the reported literature in liveness analysis of heap data either does not address
liveness of individual objects or addresses liveness of objects identified by their allocation
sites. Our method, by contrast, does not need the knowledge of allocation site. Since the
precision of a garbage collector depends on its ability to distinguish between reachable
heap objects and live heap objects, even state of art garbage collectors leave a significant
amount of garbage uncollected [Agesen et al. 1998; Shaham et al. 2000; 2001; 2002]. All
reported attempts to incorporate liveness in garbage collection have been quite approximate. The known approaches have been:
(1) Liveness of root variables. A popular approach (which has also been used in some state
of art garbage collectors) involves identifying liveness of root variable on the stack.
All heap objects reachable from the live root variables are considered live [Agesen
et al. 1998].
(2) Imposing stack discipline on heap objects. These approaches try to change the statically unpredictable lifetimes of heap objects into predictable lifetimes similar to stack
data. They can be further classified as
—Allocating objects on call stack. These approach try to detect which objects can be
allocated on stack frame so that they are automatically deallocated without the need
of traditional garbage collection. A profile based approach which tracks the last use
of an object is reported in [McDowell 1998], while a static analysis based approach
is reported in [Reid et al. 1999].
Some approaches ask a converse question: which objects are unstackable (i.e. their
lifetimes outlive the procedure which created it)? They use abstract interpretation
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

·

33

and perform escape analysis to discover objects which escape a procedure[Blanchet
1999; 2003; Choi et al. 1999]. All other objects are allocated on stack.
—Associating objects with call stack [Cannarozzi et al. 2000]. This approach identifies
the stackability. The objects are allocated in the heap but are associated with a stack
frame and the runtime support is modified to deallocate these (heap) objects when
the associated stack frame is popped.
—Allocating objects on separate stack. This approach uses a static analysis called region inference [Tofte and Birkedal 1998; Hallenberg et al. 2002] to identify regions
which are storages for objects. These regions are allocated on a separate region
stack.
All these approaches require modifying the runtime support for the programs.
(3) Liveness analysis of locally allocated objects. The Free-Me approach [Guyer et al.
2006] combines a lightweight pointer analysis with liveness information that detects
when allocated objects die and insert statements to free such objects. The analysis is
simpler and cheaper as the scope is limited, but it frees locally allocated objects only
by separating objects which escape the procedure call from those which do not. The
objects which do not escape the procedure which creates them become unreachable at
the end of the procedure anyway and would be garbage collected. Thus their method
merely advances the work of garbage collection instead of creating new garbage. Further, this does not happened in the called method. Further, their method uses traditional
liveness analysis for root variables only and hence can not free objects that are stored
in field references.
(4) The Shape Analysis Based based approaches. The two approaches in this category are
—Heap Safety Automaton approach [Shaham et al. 2003] is a recently reported work
which comes closest to our approach since it tries to determine if a reference can be
made null. We discuss this approach in the next section.
—Cherem and Rugina [2006] use a shape analysis framework [Hackett and Rugina
2005] to analyze a single heap cell to discover the point in the program where it object becomes unreachable. Their method claims the objects at such points thereby
reducing the work of the garbage collector. They use equivalence classes of expressions to store definite points-to and definitely-not points-to information in order to
increase the precision of abstract reference counts. However, multiple iterations of
the analysis and the optimization steps are required, since freeing a cell might result
in opportunities for more deallocations. Their method does not take into account the
last use of an object, and therefore does not make additional objects unreachable.
9.2 Heap Safety Automaton Based Approach
This approach models safety of inserting a null statement at a given point by an automaton.
A shape graph based abstraction of the program is then model-checked against the heap
safety automaton. Additionally, they also consider freeing the object; our approach can be
easily extended to include freeing.
The fundamental differences between the two approaches are
—Their method answers the following question: Given an access expression and a program
point, can the access expression be set to null immediately after that program point?
However, they leave a very important question unanswered: Which access expressions
should we consider and at which point in the program? It is impractical to use their
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

34

·

Uday Khedker et al.

method to ask this question for every pair of access expression and program point. Our
method answers both the questions by finding out appropriate access expressions and
program points.
—We insert null assignments at the earliest possible point. The effectiveness of any method
to improve garbage collection depends crucially on this aspect. Their method does not
address this issue directly.
—As noted in Section 7.2, their method is inefficient in practice. For a simple Java program
containing 11 lines of executable statements, it takes over 1.37 MB of storage and takes
1.76 seconds for answering the question: Can the variable y be set to null after line 10?
Hence our approach is superior to their approach in terms of completeness, effectiveness,
and efficiency.
10. CONCLUSIONS AND FURTHER WORK
Two fundamental challenges in analyzing heap data are that the temporal and spatial structures of heap data seem arbitrary and are unbounded. The apparent arbitrariness arises due
to the fact that the mapping between access expressions and l-values varies dynamically.
The two key insights which allow us to overcome the above problems in the context of
liveness analysis of heap data are:
—Creating finite representations for properties of heap data using program structure. We
create an abstract representation of heap in terms of sets of access paths. Further, a
bounded representation, called access graphs, is used for summarizing sets of access
paths. Summarization is based on the fact that the heap can be viewed as consisting
of repeating patterns which bear a close resemblance to the program structure. Access
graphs capture this fact directly by tagging program points to access graph nodes. Unlike [Horwitz et al. 1989; Chase et al. 1990; Choi et al. 1993; Wilson and Lam 1995;
Hind et al. 1999] where only memory allocation points are remembered, we remember
all program points where references are used. This allows us to combine data flow information arising out of the same program point, resulting in bounded representations
of heap data. These representations are simple, precise, and natural.
The dynamically varying mapping between access expressions and l-values is handled
by abstracting out regions in the heap which can possibly be accessed by a program.
These regions are represented by sets of access paths and access graphs which are manipulated using a carefully chosen set of operations. The computation of access graphs
and access paths using data flow analysis is possible because of their finiteness and
the monotonicity of the chosen operations. We define data flow analyses for liveness,
availability and anticipability of heap references. Liveness analysis is an any path problem, hence it involve unbounded information requiring access graphs as data flow values. Availability and anticipability analyses are all paths problems, hence they involve
bounded information which is represented by finite sets of access paths.
—Identifying the minimal information which covers every live link in the heap. An interesting aspect of our liveness analysis is that the property of explicit liveness captures
the minimal information which covers every link which can possibly be live. Complete
liveness is computed by incorporating alias information in explicit liveness.
An immediate application of these analyses is a technique to improve garbage collection.
This technique works by identifying objects which are dead and rendering them unreachACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

·

35

able by setting them to null as early as possible. Though this idea was previously known to
yield benefits [Gadbois et al. ], nullification of dead objects was based on profiling [Shaham et al. 2001; 2002]. Our method, instead, is based on static analysis.
For the future work, we find some scope of improvements on both conceptual level and
at the level of implementation.
(1) Conceptual Aspects.
(a) Since the scalability of our method critically depends on the scalability of alias
analysis, we would like to explore the possibility of avoiding computation of complete alias information at each program point. Since explicit liveness does not
require alias information, an interesting question for further investigation is: Just
how much alias information is enough to compute complete liveness from explicit
liveness? This question is important because:
—Not all aliases contribute to complete liveness.
—Even when an alias contributes to liveness, it needs to be propagated over a
limited region of the program.
(b) We have proposed an efficient version of call strings based interprocedural data
flow analysis in an independent work [Karkare 2007]. It is a generic approach
which retains full context sensitivity. We would like to use it for heap reference
analysis.
(c) We would like to improve the null insertion algorithm so that the same link is not
nullified more than once.
(d) We would like to analyze array fragments instead of treating an entire array as a
scalar (and hence, all elements as equivalent).
(e) We would also like to extend the scope of heap reference analysis for functional
languages. The basic method and the details of the liveness analysis are already
finalized [Karkare et al. 2007]. The details of other analyses are being finalized [Karkare et al. 2007].
(2) Implementation Related Aspects.
(a) We would also like to implement this approach for C/C++ and use it for plugging
memory leaks statically.
(b) Our experience with our proof-of-concept implementations indicates that the engineering choices made in the implementation have a significant bearing on the
performance of our method. For example, we would like to use a better representation than the one provided by SOOT.
We would also like to apply the summarization heuristic to other analyses. Our initial
explorations indicate that a similar approach would be useful for extending static inferencing of flow-sensitive monomorphic types [Khedker et al. 2003] to include polymorphic
types. This is possible because polymorphic types represent an infinite set of types and
hence discovering them requires summarizing unbounded information.
ACKNOWLEDGMENTS

Several people have contributed to this work in past few years. We would particularly like
to thank Smita Ranjan, Asit Varma, Deepti Gupta, Neha Adkar, C. Arunkumar, Mugdha
Jain, and Reena Kharat. Neha’s work was supported by Tata Infotech Ltd. A initial version
of the prototype implementation of this work was partially supported by Synopsys India
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

36

·

Uday Khedker et al.

Ltd. Amey Karkare has been supported by Infosys Fellowship. We are thankful to the
anonymous referee for detailed remarks.
REFERENCES
A GESEN , O., D ETLEFS , D., AND M OSS , J. E. 1998. Garbage collection and local variable type-precision and
liveness in Java virtual machines. In PLDI ’98: Proceedings of the ACM SIGPLAN 1998 conference on
Programming language design and implementation. ACM Press, New York, NY, USA, 269–279.
A HO , A. V., S ETHI , R., AND U LLMAN , J. D. 1986. Compilers – Principles, Techniques, and Tools. AddisonWesley.
B LANCHET, B. 1999. Escape analysis for object-oriented languages: application to Java. In OOPSLA ’99:
Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages,
and applications. ACM Press, New York, NY, USA, 20–34.
B LANCHET, B. 2003. Escape analysis for JavaT M : Theory and practice. ACM Transactions on Programming
Languages and Systems 25, 6, 713–775.
B OEHM , H. An artificial garbage collection benchmark. http://www.hpl.hp.com/personal/Hans_Boehm/
gc/gc_bench.html.
C ANNAROZZI , D. J., P LEZBERT, M. P., AND C YTRON , R. K. 2000. Contaminated garbage collection. In PLDI
’00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation. ACM Press, New York, NY, USA, 264–273.
C ARLISLE , M. C. 1996. Olden: Parallelizing programs with dynamic data structures on distributed-memory
machines. Ph.D. thesis, Princeton University.
C HASE , D. R., W EGMAN , M., AND Z ADECK , F. K. 1990. Analysis of pointers and structures. In PLDI ’90:
Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation.
ACM Press, New York, NY, USA, 296–310.
C HENG , B.-C. AND H WU , W.-M. W. 2000. Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation. In PLDI ’00: Proceedings of the ACM SIGPLAN 2000 conference on
Programming language design and implementation. ACM Press, New York, NY, USA, 57–69.
C HEREM , S. AND RUGINA , R. 2006. Compile-time deallocation of individual objects. In ISMM ’06: Proceedings
of the 2006 international symposium on Memory management. ACM Press, New York, NY, USA, 138–149.
C HOI , J.-D., B URKE , M., AND C ARINI , P. 1993. Efficient flow-sensitive interprocedural computation of pointerinduced aliases and side effects. In POPL ’93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium
on Principles of programming languages. ACM Press, New York, NY, USA, 232–245.
C HOI , J.-D., G UPTA , M., S ERRANO , M., S REEDHAR , V. C., AND M IDKIFF , S. 1999. Escape analysis for
Java. In OOPSLA ’99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming,
systems, languages, and applications. ACM Press, New York, NY, USA, 1–19.
G ADBOIS , D., F ITERMAN , C., C HASE , D., S HAPIRO , M., N ILSEN , K., H AAHR , P., BARNES , N., AND P IRI NEN , P. P. The GC FAQ. http://www.iecc.com/gclist/GC-faq.html.
G UYER , S. Z., M C K INLEY, K. S., AND F RAMPTON , D. 2006. Free-me: a static analysis for automatic individual object reclamation. In PLDI ’06: Proceedings of the 2006 ACM SIGPLAN conference on Programming
language design and implementation. ACM Press, New York, NY, USA, 364–375.
H ACKETT, B. AND RUGINA , R. 2005. Region-based shape analysis with tracked locations. In POPL ’05:
Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM
Press, New York, NY, USA, 310–323.
H ALLENBERG , N., E LSMAN , M., AND T OFTE , M. 2002. Combining region inference and garbage collection.
In PLDI ’02: Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and
implementation. ACM Press, New York, NY, USA, 141–152.
H ECHT, M. S. 1977. Flow Analysis of Computer Programs. Elsevier North-Holland Inc.
H IND , M., B URKE , M., C ARINI , P., AND C HOI , J.-D. 1999. Interprocedural pointer alias analysis. ACM
Transactions on Programming Languages and Systems 21, 4, 848–894.
H IRZEL , M., D IWAN , A., AND H ENKEL , J. 2002. On the usefulness of type and liveness accuracy for garbage
collection and leak detection. ACM Transactions on Programming Languages and Systems 24, 6, 593–624.
H IRZEL , M., H ENKEL , J., D IWAN , A., AND H IND , M. 2002. Understanding the connectivity of heap objects. In
ISMM ’02: Proceedings of the 3rd international symposium on Memory management. ACM Press, New York,
NY, USA, 36–49.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

Heap Reference Analysis Using Access Graphs

·

37

H ORWITZ , S., P FEIFFER , P., AND R EPS , T. 1989. Dependence analysis for pointer variables. In PLDI ’89:
Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation.
ACM Press, New York, NY, USA, 28–40.
I YER , P. C. 2005. PVS based proofs of safety properties of access graph operations. http://www.cse.iitb.
ac.in/~uday/hraResources/AGSafety.html.
J ONES , N. D. AND M UCHNICK , S. S. 1979. Flow analysis and optimization of lisp-like structures. In POPL
’79: Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages.
ACM Press, New York, NY, USA, 244–256.
J ONES , N. D. AND M UCHNICK , S. S. 1982. A flexible approach to interprocedural data flow analysis and
programs with recursive data structures. In POPL ’82: Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM Press, New York, NY, USA, 66–74.
K ARKARE , A. 2005. XSB-Prolog based prototype implementation of heap reference analysis. http://www.
cse.iitb.ac.in/~ uday/hraResources/hraPrototpye.html.
K ARKARE , A., K HEDKER , U., AND S ANYAL , A. 2007. Liveness of heap data for functional programs. In
HAV 2007: Heap Analysis and Verification Workshop. 64–80. http://research.microsoft.com/~ jjb/
papers/HAV_proceedings.pdf.
K ARKARE , A., S ANYAL , A., AND K HEDKER , U. 2007. Heap reference analysis for functional programs. (In
preparation).
K ARKARE , B. 2007. Complexity and efficiency issues in data flow analysis. Ph.D. thesis, Department of Computer Science and Engineering, Indian Institute of Technology, Bombay. (Submitted).
K HEDKER , U. P. 2002. Data flow analysis. In Compiler Design Handbook: Optimizations and Machine Code
Generation, Y. N. Srikant and P. Shankar, Eds. CRC Press, Inc., Boca Raton, FL, USA.
K HEDKER , U. P., D HAMDHERE , D. M., AND M YCROFT, A. 2003. Bidirectional data flow analysis for type
inferencing. Computer Languages, Systems and Structures 29, 1-2, 15–44.
L ARUS , J. R. AND H ILFINGER , P. N. 1988. Detecting conflicts between structure accesses. In PLDI ’88:
Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation.
ACM Press, New York, NY, USA, 24–31.
M C D OWELL , C. E. 1998. Reducing garbage in java. SIGPLAN Notices 33, 9, 84–86.
R EID , A., M C C ORQUODALE , J., BAKER , J., H SIEH , W., AND Z ACHARY, J. 1999. The need for predictable
garbage collection. In Proceedings of the ACM SIGPLAN Workshop on Compiler Support for System Software
(WCSSS’99).
S AGIV, M., R EPS , T., AND W ILHELM , R. 2002. Shape analysis and applications. In Compiler Design Handbook:
Optimizations and Machine Code Generation, Y. N. Srikant and P. Shankar, Eds. CRC Press, Inc, Boca Raton,
FL, USA.
S HAHAM , R., K OLODNER , E. K., AND S AGIV, M. 2000. On effectiveness of gc in java. In ISMM ’00: Proceedings of the 2nd international symposium on Memory management. ACM Press, New York, NY, USA,
12–17.
S HAHAM , R., K OLODNER , E. K., AND S AGIV, M. 2001. Heap profiling for space-efficient java. In PLDI ’01:
Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation.
ACM Press, New York, NY, USA, 104–113.
S HAHAM , R., K OLODNER , E. K., AND S AGIV, M. 2002. Estimating the impact of heap liveness information
on space consumption in Java. In ISMM ’02: Proceedings of the 3rd international symposium on Memory
management. ACM Press, New York, NY, USA, 64–75.
S HAHAM , R., YAHAV, E., K OLODNER , E. K., AND S AGIV, S. 2003. Establishing local temporal heap safety
properties with applications to compile-time memory management. In SAS ’03: Proceedings of the 10th
International Symposium on Static Analysis. Springer-Verlag, London, UK, 483–503.
T OFTE , M. AND B IRKEDAL , L. 1998. A region inference algorithm. ACM Transactions on Programming
Languages and Systems 20, 4, 724–767.
VALL ÉE -R AI , R., H ENDREN , L., S UNDARESAN , V., L AM , P., G AGNON , E., AND C O , P. 1999. Soot - a java
optimization framework. In Proceedings of CASCON 1999. 125–135.
W ILSON , R. P. AND L AM , M. S. 1995. Efficient, context-sensitive pointer analysis for C programs. In PLDI ’95:
Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation.
ACM Press, New York, NY, USA, 1–12.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

38

·

Uday Khedker et al.

1 x.n = null
x

n2

1

n3
n6

x

r4

r8

n6

ELOutx (1)

n7

n3

n5

n2

n7
n6

x
r4

2 x = x.n 2

4 x = x.r 4
n3

x
3 x.n.n = null

n6

x

r8

n5
n6

n7

f1 (ELInx (2) ⊎ ELInx (4))

5 x.n.r = null

3
x

n6

n7

n7

5

n6
x

r8

r8

n7
f1 (ELInx (2)) ⊎ f1 (ELInx (4))

x

n6

r8
x

7 z = x.n 7

r4
n5

6 x = x.n 6
x

r8
n5

8 z = x.r 8

n7

r4
n5

Fig. 17. Non-distributivity of liveness analysis. Access path x r n r is a spurious access path which does not
get killed by the assignment in block 1.

Y ONG , S. H., H ORWITZ , S., AND R EPS , T. 1999. Pointer analysis for programs with structures and casting.
In PLDI ’99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and
implementation. ACM Press, New York, NY, USA, 91–103.

A. NON-DISTRIBUTIVITY IN HEAP REFERENCE ANALYSIS
Explicit liveness analysis defined in this paper is not distributive whereas availability and
anticipability analyses are distributive. Explicit liveness analysis is non-distributive because of the approximation introduced by the ⊎ operation. G1 ⊎ G2 may contain access
paths which are neither in G1 nor in G2 .
E XAMPLE A.1. Figure 17 illustrates the non-distributivity of explicit liveness analysis.
Liveness graphs associated with the entry each block is shown in shaded boxes. Let f1
denote the flow function which computes x-rooted liveness graphs at the entry of block 1.
Neither ELInx (2) nor ELInx (4) contains the access path x r n r but their union contains
it. It is easy to see that
f1 (ELInx (2) ⊎ ELInx (4)) ⊑G f1 (ELInx (2)) ⊎ f1 (ELInx (4))
✷
Availability and anticipability analyses are non-distributive because they depend on
may-alias analysis which is non-distributive.
ACM Transactions on Programming Languages and Systems, Vol. TBD, No. TDB, Month Year.

