arXiv:cs/0703155v1 [] 30 Mar 2007

Replace this file with prentcsmacro.sty for your meeting,
or with entcsmacro.sty for your meeting. Both can be
found at the ENTCS Macro Home Page.

Liveness of Heap Data for Functional Programs
Amey Karkare1 Uday Khedker Amitabha Sanyal
{karkare,uday,as}@cse.iitb.ac.in
Department of CSE, IIT Bombay
Mumbai, India

Abstract
Functional programming languages use garbage collection for heap memory management. Ideally, garbage collectors should
reclaim all objects that are dead at the time of garbage collection. An object is dead at an execution instant if it is not used in
future. Garbage collectors collect only those dead objects that are not reachable from any program variable. This is because
they are not able to distinguish between reachable objects that are dead and reachable objects that are live.
In this paper, we describe a static analysis to discover reachable dead objects in programs written in first-order, eager functional programming languages. The results of this technique can be used to make reachable dead objects unreachable, thereby
allowing garbage collectors to reclaim more dead objects.
Keywords: Compilers, Liveness, Garbage Collection, Memory Management, Data Flow Analysis, Context Free Grammars

1

Introduction

Garbage collection is an attractive alternative to manual memory management because it
frees the programmer from the responsibility of keeping track of object lifetimes. This
makes programs easier to implement, understand and maintain. Ideally, garbage collectors
should reclaim all objects that are dead at the time of garbage collection. An object is
dead at an execution instant if it is not used in future. Since garbage collectors are not able
to distinguish between reachable objects that are live and reachable objects that are dead,
they conservatively approximate the liveness of an object by its reachability from a set of
locations called root set (stack locations and registers containing program variables) [14].
As a consequence, many dead objects are left uncollected. This has been confirmed by
empirical studies for Haskell [19], Scheme [16] and Java [22,23,24].
Compile time analysis can help in distinguishing reachable objects that are live from
reachable objects that are dead. This is done by detecting unused references to objects.
If an object is dead at a program point, none of its references are used by the program
beyond that program point. If every unused reference is nullified, then the dead objects
may become unreachable and may be claimed by garbage collector.
1

Supported by Infosys Technologies Limited, Bangalore, under Infosys Fellowship Award.
c

2018 Published by Elsevier Science B. V.

Karkare, Khedker and Sanyal

(define (app list1 list2)
π1 :(if π2 :(null? π3 :list1)
π4 :list2
π5 :(cons π6 :(car π7 :list1)
π8 :(app π9 :(cdr π10 :list1)
π11 :list2))))
(let z ←(cons (cons 4 (cons 5 Nil))
(cons 6 Nil)) in
(let y ← (cons 3 Nil) in
π12 :(let w ← π13 :(app y z) in
π14 :(car (car (cdr w))))))

y

w

×

z

×
×

3

×

Nil

×
6

4
5

Nil

Nil

(b) Memory graph at π14 .
(b) Thick edges denote live links.
(b) Edges marked × can be nullified.

(a) Example program.

Fig. 1. Example Program and its Memory Graph.

Example 1.1 Figure 1(a) shows an example program. The label π of an expression e denotes the program point just before the evaluation of e. At a given program point, the heap
memory can be viewed as a (possibly unconnected) directed acyclic graph called memory
graph. The locations in the root set form the entry nodes for the memory graph. Figure 1(b) shows the memory graph at π14 . Each cons cell is an intermediate node in the
graph. Elements of basic data types and the 0-ary constructor Nil form leaf nodes of the
graph. They are assumed to be boxed, i.e. stored in separate heap cells and are accessed
through references. The edges in the graph are called links.
If we consider the execution of the program starting from π14 , the links in the memory
graph that are traversed are shown by thick arrows. These links are live at π14 . Links that
are not live can be nullified by the compiler by inserting suitable statements. If an object
becomes unreachable due to nullification, it can be collected by the garbage collector.
In the figure, the links that can be nullified are shown with a ×. Note that a link need
not be nullified if nullifying some other link makes it unreachable from the root set. If a
node becomes unreachable from the root set as a consequence of nullifying the links, it will
be collected during the next invocation of garbage collector.
✷
In this example, starting at π14 , there is only one execution path. In general, there could
be multiple execution paths starting from a program point π. The liveness information at π
is a combination of liveness information along every execution path starting at π.
In this paper, we describe a static analysis for programs written in first-order, eager
functional programming languages. The analysis discovers live references at every program
point, i.e. the references that may be used beyond the program point in any execution of
the program. We use context free grammars as a bounded representation for the set of live
references. The result of the analysis can be used by the compiler to decide whether a given
reference can be nullified at a given program point. Our analysis is context-sensitive yet
modular in that a function is analyzed only once.
The rest of the paper is organized as follows: Section 2 describes the language used to
explain our analysis along with the basic concepts and notations. The analysis in Section 3
captures the liveness information of a program as a set of equations. The method to solve
2

Karkare, Khedker and Sanyal

p ::= d1 . . . dn e1
— program
d ::= (define ( f v1 . . . vn ) e1 ) — function definition
e ::=
— expression
κ
— constant
|v
— variable
| Nil
— primitive constructor
— primitive constructor
| (cons e1 e2 )
| (car e1 )
— primitive selector
| (cdr e1 )
— primitive selector
| (pair? e1 )
— primitive tester
| (null? e1 )
— primitive tester
| (+ e1 e2 )
— generic primitive
| (if e1 e2 e3 )
— conditional
| (let v1 ← e2 in e3 ) — let binding
| ( f e1 . . . en )
— function application
Fig. 2. The syntax of our language

these equations is given in Section 4. Section 5 describes how the result of the analysis can
be used to nullify unused references. Finally, we compare our approach with related work
in Section 6 and conclude in Section 7.

2

Language, Concepts and Notations

The syntax of our language is described in Figure 2. The language has call-by-value semantics. The argument expressions are evaluated from left to right. We assume that variables
in the program are renamed so that the same name is not defined in two different scopes.
For notational convenience, the left link (corresponding to the car) of a cons cell is
denoted by 0 and the right link (corresponding to the cdr) is denoted by 1. We use e.0 to
denote the link corresponding to (car e) for an expression e (assuming e evaluates to a list)
and e.1 to denote the link corresponding to (cdr e). A composition of several cars and cdrs
is represented by a string α ∈ {0, 1}∗ . If an expression e evaluates to a cons cell then e.ε
corresponds to the reference to the cons cell.
For an expression e, let [e] denote the location in the root set holding the value of e.
Given a memory graph, the string e.α describes a path in the memory graph that starts
at [e]. We call the string e.α an access expression, the string α an access pattern, and
the path traced in the memory graph an access path. In Figure 1, the access expression
w.100 represents the access path from w to the node containing the value 4. Most often,
the memory graph being referred to is clear from the context, and therefore we shall use
access expressions to refer to access paths. When we use an access path to refer to a link in
the memory graph, it denotes the last link in the access path. Thus, w.100 denotes the link
incident on the node containing the value 4. If σ denotes a set of access patterns, then e.σ
is the set of access paths rooted at [e] and corresponding to σ. i.e.
e.σ = {e.α | α ∈ σ}
A link in a memory graph is live at a program point π if it is used in some path from π
3

Karkare, Khedker and Sanyal

to the program exit. An access path is defined to be live if its last link is live. In Example 1,
the set of live access paths at π14 is {w.ε, w.1, w.10, w.100, z.0, z.00}. Note that the access
paths z.0 and z.00 are live at π14 due to sharing. We do not discover the liveness of such
access paths directly. Instead, we assume that an optimizer using our analysis will use alias
analysis to discover liveness due to sharing.
The end result of our analysis is the annotation of every expression in the program
with a set of access paths rooted at program variables. We call this liveness environment,
denoted L . This information can be used to insert nullifying statements before expressions.
The symbols 0 and 1 extend the access patterns of a structure to describe the access
patterns of a larger structure. In some situations, we need to create access patterns of a
substructure from the access patterns of a larger structure. For this purpose, we extend our
alphabet of access patterns to include symbols 0̄ and 1̄. The following example motivates
the need for these symbols.
Example 2.1 Consider the expression at program point π1 in
π1 :(let w ← π2 :(cons x y) in π3 :· · ·)
Assuming Lπ3 = {w.α}, we would like to find out which reference of the list x and y are
live at π1 . Let x.α′ be live at π1 . Then, the two possible cases are:
•

If α = 1β or α = ε, no link in the structure rooted at x is used. We use ⊥ to denote the
access pattern describing such a situation. Thus, α′ = ⊥.

•

If α = 0β then the link represented by w.α that is x rooted and live at π1 can be represented by x.β. Thus, α′ = β.

This relation between α and α′ is expressed by α′ = 0̄α. 1̄ can be interpreted similarly. ✷
With the inclusion of 0̄, 1̄ and ⊥ in the alphabet for access patterns, an access pattern
does not directly describe a path in the memory graph. Hence we define a Canonical Access
Pattern as a string restricted to the alphabet {0, 1}. As a special case, ⊥ is also considered
as a canonical access pattern.
We define rules to reduce access patterns to their canonical forms. For access patterns
α1 and α2 :

α1 α′2 if α2 ≡ 0α′2
(1) α1 0̄α2 →
⊥
if α2 ≡ 1α′2 or α2 ≡ ε

α1 α′2 if α2 ≡ 1α′2
(2) α1 1̄α2 →
⊥
if α2 ≡ 0α′2 or α2 ≡ ε
(3) α1 ⊥α2 → ⊥
k

α → α′ denotes the reduction of α to α′ in k steps, and → denotes the reflexive and transitive
closure of →. The concatenation (·) of a set of access patterns σ1 with σ2 is defined as a
set containing concatenation of each element in σ1 with each element in σ2 , i.e.
⋆

σ1 · σ2 = {α1 α2 | α1 ∈ σ1 , α2 ∈ σ2 }

3

Computing Liveness Environments

Let σ be the set of access patterns specifying the liveness of the result of evaluating e. Let

L be the liveness environment after the evaluation of e. Then the liveness environment
4

Karkare, Khedker and Sanyal

before the computation of e is discovered by propagating σ backwards through the body of
e. This is achieved by defining an environment transformer for e, denoted X E .
Since e may contain applications of primitive operations and user defined functions,
we also need transfer functions that propagate σ from the result of the application to the
arguments. These functions are denoted by X P and X F . While X P is given directly based
on the semantics of the primitive, X F is inferred from the body of a function.
3.1

Computing X E

For an expression e at program point π, X E (e, σ, L ) computes liveness environment at π
where σ is the set of access patterns specifying the liveness of the result of evaluating e
and L is the liveness environment after the evaluation of e. Additionally, as a side effect,
the program point π is annotated with the value computed. However, we do not show this
explicitly to avoid clutter. The computation of X E (e, σ, L ) is as follows.
(4)
(5)
(6)

(7)
(8)

(9)

(10)

X E (κ, σ, L ) = L
X E (v, σ, L ) = L ∪ v.σ
X E ((P e1 e2 ), σ, L ) = let L ′ ← X E (e2 , X PP2 (σ), L ) in
X E (e1 , X PP1 (σ), L ′ )
where P is one of cons, +
X E ((P e1 ), σ, L ) = X E (e1 , X PP1 (σ), L )
where P is one of car, cdr, null?, pair?
X E ((if e1 e2 e3 ), σ, L ) = let L ′ ← X E (e3 , σ, L ) in
let L ′′ ← X E (e2 , σ, L ) in
X E (e1 , {ε}, L ′ ∪ L ′′)
X E ((let v1 ← e1 in e2 ), σ, L ) = let L ′ ← X E (e2 , σ, L ) in
X E (e1 , σ′ , L ′ − v1 .σ′ )
where σ′ = {α | v1 .α ∈ L ′ }
X E (( f e1 . . . en ), σ, L ) = let L1 ← X E (en , X F fn (σ), L ) in
..
.
let Ln−1 ← X E (e2 , X F f2 (σ), Ln−2 ) in

X E (e1 , X F f1 (σ), Ln−1 )
We explain the definition of X E for the if expression. Since the value of the conditional
expression e1 is boolean and this value is used, the liveness access pattern with respect to
which e1 is computed is {ε}. Further, since it is not possible to statically determine whether
e2 or e3 will be executed, the liveness environment with respect to which e1 is computed is
the union of the liveness environments arising out of e2 and e3 .
3.2

Computing X P and X F

If σ is the set of access patterns specifying the liveness of the result of evaluating (P e1 . . . en ),
where P is a primitive, then X PPi (σ) gives the set of access patterns specifying the liveness
of ei . We describe the transfer functions for the primitives in our language: car, cdr, cons,
null?, pair? and +. The 0-ary constructor Nil does not accept any argument and is ignored.
5

Karkare, Khedker and Sanyal

Assume that the live access pattern for the result of the expression (car e) is α. Then,
the link that is denoted by the path labeled α starting from location [(car e)] can also be
denoted by a path 0α starting from location [e]. We can extend the same reasoning for set
of access patterns (σ) of result, i.e. every pattern in the set is prefixed by 0 to give live
access pattern of e. Also, since the cell corresponding to e is used to find the value of car,
we need to add ε to the live access patterns of e. Reasoning about (cdr e) similarly, we have
1
(σ) = {ε} ∪ {0} · σ,
(11) X Pcar

1
X Pcdr
(σ) = {ε} ∪ {1} · σ

As seen in Example 2.1, an access pattern of α for result of cons translates to an access
pattern of 0̄α for its first argument, and 1̄α for its second argument. Since cons does not
read its arguments, the access patterns of the arguments do not contain ε.
1
(12) X Pcons
(σ) = {0̄} · σ,

2
X Pcons
(σ) = {1̄} · σ

Since the remaining primitives read only the value of the arguments, the set of live access
patterns of the arguments is {ε}.
1
(13) X Pnull? (σ) = {ε},

1
X Ppair?
(σ) = {ε},

X P+1 (σ) = {ε},

X P+2 (σ) = {ε}

We now consider the transfer function for a user defined function f . If σ is the set of
access patterns specifying the liveness of the result of evaluating ( f e1 . . . en ), then X F fi (σ)
gives the set of access patterns specifying the liveness of ei . Let f be defined as:
(define ( f v1 . . . vn ) π : e)
Assume that σ is the live access pattern for the result of f . Then, σ is also the live access
/ computes live access patterns for vi (1 ≤ i ≤ n) at π. Thus, the
pattern for e. X E (e, σ, 0)
transfer function for the ith argument of f is given by:
/
(14) X F fi (σ) = {α | vi .α ∈ X E (e, σ, 0)}

1≤i≤n

The following example illustrates our analysis.
Example 3.1 Consider the program in Figure 1. To compute the transfer functions for app,
/ in terms of a variable σ. Here e is
we compute the environment transformer X E (e, σ, 0)
the body of app. The value of the liveness environment at each point in the body of app is
shown in Appendix A. From the liveness information at π1 we get:
1
1
X F app
(σ) = {ε} ∪ {00̄} · σ ∪ {1} · X F app
({1̄} · σ)
2
2
X F app
(σ) = σ ∪ X F app
({1̄} · σ)

Let epgm represent the entire program being analyzed and σpgm be the set of access
patterns describing the liveness of the result. Then, the liveness environment at various
/ The liveness environments at
points in the epgm can be computed as X E (epgm , σpgm , 0).
π14 and π12 are as follows:

Lπ14 = { w.({ε, 1, 10} ∪ {100} · σpgm ) }
Lπ12 =

(

1
({ε, 1, 10} ∪ {100} · σpgm ),
y.X F app
2
z.X F app ({ε, 1, 10} ∪ {100} · σpgm )

)
✷

We assume that the entire result of the program is needed, i.e., σpgm is {0, 1}∗.
6

Karkare, Khedker and Sanyal

4

Solving the Equations for X F

In general, the equations defining the transfer functions X F will be recursive. To solve
such equations, we start by guessing that the solution will be of the form:
(15) X F fi (σ) = I fi ∪ D if · σ,
where I fi and D if are sets of strings over the alphabet {0, 1, 0̄, 1̄}. The intuition behind this
form of solution is as follows: The function f can use its argument locally and/or copy a
part of it to the return value being computed. I fi is the live access pattern of ith argument
due to local use in f . D if is a sort of selector that selects the liveness pattern corresponding
to the ith argument of f from σ, the liveness pattern of the return value.
If we substitute the guessed form of X F fi in the equations describing it and equate the
terms containing σ and the terms without σ, we get the equations for I fi and D if . This is
illustrated in the following example.
1
(σ) from Example 3.1:
Example 4.1 Consider the equation for X F app
1
1
X F app
(σ) = {ε} ∪ {00̄} · σ ∪ {1} · X F app
({1̄} · σ)

Decomposing both sides of the equation, and rearranging the RHS gives:
1
1
1
1
Iapp
∪ Dapp
· σ = {ε} ∪ {00̄} · σ ∪ {1} · (Iapp
∪ Dapp
· {1̄} · σ)
1
1
= {ε} ∪ {1} · Iapp
∪ {00̄} · σ ∪ {1} · Dapp
· {1̄} · σ

Separating the parts that are σ dependent and the parts that are σ independent, and equating
them separately, we get:
1
1
Iapp
= {ε} ∪ {1} · Iapp
1
1
· {1̄}σ
Dapp
· σ = {00̄} · σ ∪ {1} · Dapp
1
= ({00̄} ∪ {1} · Dapp
· {1̄}) · σ

As the equations hold for any general σ, we can simplify them to:
1
1
1
1
Iapp
= {ε} ∪ {1} · Iapp
and Dapp
= {00̄} ∪ {1} · Dapp
· {1̄}
2
(σ), we get:
Similarly, from the equation describing X F app
2
2
2
2
Iapp
= Iapp
and Dapp
= {ε} ∪ Dapp
· {1̄}
The liveness environment at π12 and π14 in terms Iapp and Dapp are:

Lπ14 = { w.{100} · σpgm }


1
1
y.(Iapp
∪ Dapp
· ({ε, 1, 10} ∪ {100} · σpgm )),
Lπ12 =
2
2
· ({ε, 1, 10} ∪ {100} · σpgm ))
∪ Dapp
z.(Iapp
Solving for Iapp and Dapp gives us the desired liveness environments at these program
points.
4.1

✷

Representing Liveness by Context Free Grammars

The values of I and D variables of a transfer function are sets of strings over the alphabet
{0, 1, 0̄, 1̄}. We use context free grammars (CFG) to describe these sets. The set of terminal
symbols of the CFG is {0, 1, 0̄, 1̄}. Non-terminals and associated rules are constructed as
illustrated in Examples 4.2 and 4.3.
7

Karkare, Khedker and Sanyal

Example 4.2 Consider the following constraint from Example 4.1:
1
1
Iapp
= {ε} ∪ {1} · Iapp
1 i and the productions with right hand sides directly derived
We add non-terminal hIapp

from the constraints:
1 i → ε | 1hI 1 i
hIapp
app

The productions generated from other constraints of Example 4.1 are:
1
1
hDapp
i → 00̄ | 1hDapp
i1̄
2 i → hI 2 i
hIapp
app
2
2
hDapp
i → ε | hDapp
i1̄

These productions describe the transfer functions of app.

✷

The liveness environment at each program point can be represented as a CFG with a
start symbol for every variable. To do so, the analysis starts with hSpgm i, the non-terminal
describing the liveness pattern of the result of the program, σpgm . The productions for
hSpgm i are:
hSpgm i → ε | 0hSpgm i | 1hSpgm i
Example 4.3 Let Sπv denote the non-terminal generating liveness access patterns associated
with a variable v at program point π. For the program of Figure 1:
hSπw14 i → ε | 1 | 10 | 100hSpgm i
2 i | hD 2
2
2
2
hSπz 12 i → hIapp
app i | hDapp i1 | hDapp i10 | hDapp i100hSpgm i
1
1
1
1 i | hD 1
hSπy12 i → hIapp
app i | hDapp i1 | hDapp i10 | hDapp i100hSpgm i

✷

The access patterns in the access paths used for nullification are in canonical form
but the access patterns described by the CFGs resulting out of our analysis are not. It is
not obvious how to check the membership of a canonical access pattern in such CFGs.
To solve this problem, we need equivalent CFGs such that if α belongs to an original
⋆
CFG and α → β, where β is in canonical form, then β belongs to the corresponding new
CFG. Directly converting the reduction rules (Equations (1, 2, 3)) into productions and
adding it to the grammar results in unrestricted grammar [11]. To simplify the problem,
we approximate original CFGs by non-deterministic finite automata (NFAs) and eliminate
0̄ and 1̄ from the NFAs.
4.2

Approximating CFGs using NFAs

The conversion of a CFG G to an approximate NFA N should be safe in that the language
accepted by N should be a superset of the language accepted by G. We use the algorithm
described by Mohri and Nederhof [18]. The algorithm transforms a CFG to a restricted
form called strongly regular CFG which can be converted easily to a finite automaton.
Example 4.4 We show the approximate NFAs for each of the non-terminals in Example 4.2 and Example 4.3.
1

0
hSpgm i:

start

1 i:
hIapp

1

8

start

Karkare, Khedker and Sanyal
1̄

1
1
hDapp
i:

start

0

1̄

0̄

2
hDapp
i:

1̄

0
hSπw14 i:

start

1

start

0

0̄

hSπz 12 i :

start

0
1

0

0

1

1̄

1
hSπy12 i:

0

0

start

1
0

1

0

0
1

2 i. This is because the least solution of the equaNote that there is no automaton for hIapp
2 i → hI 2 i is 0.
1
/ Also, the language accepted by the automaton for Dapp
tion hIapp
is
app
approximate as it does not ensure that there is an equal number of 1 and 1̄ in the strings
1
generated by rules for hDapp
i.
✷

4.3

Eliminating 0̄ and 1̄ from NFA

We now describe how to convert an NFA with transitions on symbols 0̄ and 1̄ to an equivalent NFA without any transitions on these symbols.
Input: An NFA N with underlying alphabet {0, 1, 0̄, 1̄} accepting a set of access patterns
Output: An NFA N with underlying alphabet {0, 1} accepting the equivalent set of canonical access patterns
Steps:
i←0
N0 ← Equivalent NFA of N without ε-moves [11]
do {
N′i+1 ← Ni
foreach state q in Ni such that q has an incoming edge from q′
with label 0̄ and outgoing edge to q′′ with label 0 {
/⋆ bypass 0̄0 using ε ⋆/
add an edge in N′i+1 from q′ to q′′ with label ε.
}
foreach state q in Ni such that q has an incoming edge from q′
with label 1̄ and outgoing edge to q′′ with label 1 {
/⋆ bypass 1̄1 using ε ⋆/
add an edge in N′i+1 from q′ to q′′ with label ε.
}
Ni+1 ← Equivalent NFA of N′i+1 without ε-moves
i ← i+1
} while (Ni 6= Ni−1 )
N ← Ni
delete all edges with label 0̄ or 1̄ in N.

The algorithm repeatedly introduces ε edges to bypass a pair of consecutive edges labeled
0̄0 or 1̄1. The process is continued till a fixed point is reached. When the fixed point is
reached, the resulting NFA contains the canonical access patterns corresponding to all the
9

Karkare, Khedker and Sanyal

access patterns in the original NFA. The access patterns not in canonical form are deleted
by removing edges labeled 0̄ and 1̄. Note that by our reduction rules if α is accepted by
⋆
N and α → ⊥, then ⊥ should be accepted by N, However, N returned by our algorithm
does not accept ⊥. This is not a problem because the access patterns which are tested for
membership against N do not include ⊥ as well.
Example 4.5 We show the elimination of 0̄ and 1̄ for the automata for hSπy12 i and hSπz 12 i.
The automaton for hSπw14 i remains unchanged as it does not contain transitions on 0̄ and 1̄.
The automata at the termination of the loop in the algorithm are:
1̄

1
hSπy12 i:

start

0

0̄

0
0

0

1
0
0

1

1̄
hSπz 12 i

:

start

0
0

0

1
0

1

Eliminating the edges labeled 0̄ and 1̄, and removing the dead states gives:
1
hSπy12 i:

start

0

0
0

0

hSπz 12 i :

start

0

1

0

0

1

1

The language accepted by these automata represent the live access paths corresponding to
y and z at π12 .
✷
We now prove the termination and correctness of our algorithm.
Termination
Termination of the algorithm follows from the fact that every iteration of do-while loop
adds new edges to the NFA, while old edges are not deleted. Since no new states are added
to NFA, only a fixed number of edges can be added before we reach a fix point.
Correctness
The sequence of obtaining N from N can be viewed as follows, with Nm denoting the NFA
at the termination of while loop:
N

deletion
of ε-edges

N0

addition
of ε-edges

N′1

deletion
of ε-edges

N1

addition

···

addition

of ε-edges
of ε-edges
deletion of
Nm
N
0̄, 1̄ edges

N′i

deletion
of ε-edges

Ni · · ·

deletion
of ε-edges

Nm

Then, the languages accepted by these NFAs have the following relation:
L(N) = L(N0 ) ⊆ L(N′1 ) = L(N1 ) ⊆ · · · ⊆ L(N′i ) = L(Ni ) ⊆ · · · = L(Nm )
L(N) ⊆ L(Nm )
We first prove that the addition of ε-edges in the while loop does not add any new
information, i.e. any access pattern accepted by the NFA after the addition of ε-edges is a
reduced version of some access pattern existing in the NFA before the addition of ε-edges.
10

Karkare, Khedker and Sanyal

Lemma 4.6 for i > 0, if α ∈ L(Ni ) then there exists α′ ∈ L(Ni−1 ) such that α′ → α.
⋆

Proof. As L(Ni ) = L(N′i ), we have α ∈ L(N′i ). Only difference between N′i and Ni−1 is that
N′i contains some extra ε-edges. Thus, any ε-edge free path in N′i is also in Ni−1 . Consider
a path p in N′i that accepts α. Assume the number of ε edges in p is k. The proof is by
induction on k.
(BASE) k = 0, i.e. p does not contains any ε-edge: As the path p is ε-edge free, it must be
⋆
present in Ni−1 . Thus, Ni−1 also accepts α. α → α.
(HYPOTHESIS) For any α ∈ L(Ni ) with accepting path p having less than k ε-edges there
⋆
exists α′ ∈ L(Ni−1 ) such that α′ → α.
(INDUCTION) p contains k ε-edges e1 , . . . , ek : Assume e1 connects states q′ and q′′ in N′i .
By construction, there exists a state q in N′i such that there is an edge e′1 from q′ to q with
label 0̄(1̄) and an edge e′′1 from q to q′′ with label 0(1) in N′i . Replace e1 by e′1 e′′1 in p to get a
1

new path p′′ in N′i . Let α′′ be the access pattern accepted by p′′ . Clearly, α′′ → α. Since p′′
has k − 1 ε-edges, α′′ is accepted by N′i along a path (p′′ ) that has less than k ε-edges. By
1

induction hypothesis, we have α′ ∈ L(Ni−1 ) such that α′ → α′′ . This along with α′′ → α
⋆
✷
gives α′ → α.
⋆

Corollary 4.7 for each α ∈ L(Nm ), there exists α′ ∈ L(N) such that α′ → α.
⋆

Proof. The proof is by induction on m, and using Lemma 4.6.

✷

The following lemma shows that the the language accepted by Nm is closed with respect
to reduction of access patterns.
Lemma 4.8 For α ∈ L(Nm ), if α → α′ and α′ 6= ⊥, then α′ ∈ L(Nm ).
⋆

k

Proof. Assume α → α′ . The Proof is by induction on k, number of steps in reduction.
0
(BASE) case k = 0 is trivial as α → α.
k−1
(HYPOTHESIS) Assume that for α ∈ L(Nm ), if α → α′ , then α′ ∈ L(Nm ).
k

k−1

1

(INDUCTION) α ∈ L(Nm ), α → α′ . There exists α′′ such that: α → α′′ → α′ . By
induction hypothesis, we have α′′ ∈ L(Nm ).
1

For α′′ → α′ to hold we must have α′′ = α1 0̄0α2 and α′ = α1 α2 , or α′′ = α1 1̄1α2 and
α′ = α1 α2 . Consider the case when α′′ = α1 0̄0α2 . Any path in Nm accepting α′′ must have
the following structure (The states shown separately may not necessarily be different):
start

q0

α1

q′

0̄

q

0

q′′

α2

qF

As Nm is the fixed point NFA for the iteration process described in the algorithm, adding
an ε-edge between states q′ and q′′ will not change the language accepted by Nm . But, the
access pattern accepted after adding an ε-edge is α1 α2 = α′ . Thus, α′ ∈ L(Nm ). The case
when α′′ = α1 1̄1α2 is identical.
✷
Corollary 4.9 For α ∈ L(N), if α → α′ and α′ 6= ⊥, then α′ ∈ L(Nm ).
⋆

Proof. L(N) ⊆ L(Nm ) ⇒ α ∈ L(Nm ). The proof follows from Lemma 4.8.

✷

The following theorem asserts the equivalence of N and N with respect to the equivalence of access patterns, i.e. every access pattern in N has an equivalent canonical access
11

Karkare, Khedker and Sanyal

pattern in N, and for every canonical access pattern in N, there exists an equivalent access
pattern in N.
Theorem 4.10 Let N be an NFA with underlying alphabet {0, 1, 0̄, 1̄}. Let NFA N be the
NFA with underlying alphabet {0, 1} returned by the algorithm. Then,
(i) if α ∈ L(N), β is a canonical access pattern such that α → β and β 6= ⊥, then β ∈ L(N).
⋆

(ii) if β ∈ L(N) then there exists an access pattern α ∈ L(N) such that α → β.
⋆

Proof.
(i) From Corollary 4.9: α ∈ L(N), α → β and β 6= ⊥ ⇒ β ∈ L(Nm ). As β is in canonical
form, the path accepting β in Nm consists of edges labeled 0 and 1 only. The same
path exists in N. Thus N also accepts β ⇒ β ∈ L(N).
⋆

(ii) L(N) ⊆ L(Nm ) ⇒ β ∈ L(Nm ). Using Corollary 4.7, there exists α ∈ L(N) such that
⋆
α → β.
✷

5

An Application of Liveness Analysis

The result of liveness analysis can be used to decide whether a given access path v.α can be
nullified at a given program point π. Let the link corresponding to v.α in the memory graph
be l. A naive approach is to nullify v.α if it does not belongs to the liveness environment
at π. However, the approach is not safe because of two reasons: (a) The link l may be
used beyond π through an alias, and may therefore be live. (b) a link l ′ in the access path
from the root variable v to l may have been created along one execution path but not along
another. Since the nullification of v.α requires the link l ′ to be dereferenced, a run time
exception may occur.
To solve the first problem, we need an alias analysis phase to detect sharing of links
among access paths. A link in the memory graph can be nullified at π if none of the access
paths sharing it are live at π . To solve the second problem, we need an availability analysis
phase. It detects whether all links in the access path have been created along all execution
paths reaching π. The results of these analysis are used to filter out those access paths
whose nullification may be unsafe. We do not address the descriptions of these analyses in
this paper.

6

Related Work

In this paper, we have described a static analysis for inferring dead references in first order
functional programs. We employ a context free grammar based abstraction for the heap.
This is in the spirit of the work by Jones and Muchnick [13] for functional programs. The
existing literature related to improving memory efficiency of programs can be categorized
as follows:
Compile time reuse. The method by Barth [2] detects memory cells with zero reference count and reallocates them for further use in the program. Jones and Le Metayer [15]
describe a sharing analysis based garbage collection for reusing of cells. Their analysis
incorporates liveness information: A cell is collected even when it is shared provided expressions sharing it do not need it for their evaluation.
12

Karkare, Khedker and Sanyal

Explicit reclamation. Shaham et. al. [25] use an automaton called heap safety automaton to model safety of inserting a free statement at a given program point. The analysis is
based on shape analysis [20,21] and is very precise. The disadvantage of the analysis is
that it is very inefficient and takes large time even for toy programs. Free-Me [7] combines
a lightweight pointer analysis with liveness information that detects when short-lived objects die and insert statements to free such objects. The analysis is simpler and cheaper as
the scope is limited. The analysis described by Inoue et. al. [12] detects the scope (function) out of which a cell becomes unreachable, and claims the cell using an explicit reclaim
procedure whenever the execution goes out of that scope. Like our method, the result of
their analysis is also represented using CFGs. The main difference between their work and
ours is that we detect and nullify dead links at any point of the program, while they detect
and collect objects that are unreachable at function boundaries. Cherem and Rugina [5]
use a shape analysis framework [8] to analyze a single heap cell at a time for deallocation.
However, multiple iterations of the analysis and the optimization steps are required, since
freeing a cell might result in opportunities for more deallocations.
Making dead objects unreachable. The most popular approach to make dead objects
unreachable is to identify live variables in the program to reduce the root set to only the
live reference variables [1]. The major drawback of this approach is that all heap objects
reachable from the live root variables are considered live, even if some of them may not be
used by the program. Escape analysis [3,4,6] based approaches discover objects escaping
a procedure (an escaping object being an object whose lifetimes outlives the procedure that
created it). All non-escaping objects are allocated on stack, thus becoming unreachable
whenever the creating procedure exits. In Region based garbage collection [9], a static
analysis called region inference [26] is used to identify regions that are storage for objects.
Normal memory blocks can be allocated at any point in time; they are always allocated
in a particular region and are deallocated at the end of that region’s lifetime. Approaches
based on escape analysis and region inference detect garbage only at the boundaries of
certain predefined areas of the program. In our previous work [17], we have used bounded
abstractions of access paths called access graphs to describe the liveness of memory links
in imperative programs and have used this information to nullify dead links.
A related work due to Heine and Lam [10] attempts to find potential memory leaks
in C/C++ programs by detecting the earliest point in a program when an object becomes
unreachable.

7

Conclusions

In this paper we presented a technique to compute liveness of heap data in functional programs. This information could be used to nullify links in heap memory to improve garbage
collection. We have abstracted the liveness information in the form of a CFG, which is then
converted to NFAs. This conversion implies some imprecision. We present a novel way to
simplify the NFAs so they directly describe paths in the heap. Unlike the method described
by Inoue et. al. [12], our simplification does not cause any imprecision.
In future, we intend to take this method to its logical conclusion by addressing the issue
of nullification. This would require us to perform alias analysis which we feel can be done
in a similar fashion. We also feel that with minor modification our method can be used for
dead code elimination and intend to extend our analysis to higher order languages.
13

Karkare, Khedker and Sanyal

References
[1] Agesen, O., D. Detlefs and J. E. Moss, 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 (1998), pp. 269–279.
[2] Barth, J. M., Shifting garbage collection overhead to compile time, Commun. ACM 20 (1977), pp. 513–518.
[3] Blanchet, B., 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 (1999), pp.
20–34.
[4] Blanchet, B., Escape analysis for JavaT M : Theory and practice, ACM Transactions on Programming Languages and
Systems 25 (2003), pp. 713–775.
[5] Cherem, S. and R. Rugina, Compile-time deallocation of individual objects, in: ISMM ’06: Proceedings of the 2006
international symposium on Memory management (2006), pp. 138–149.
[6] Choi, J.-D., M. Gupta, M. Serrano, V. C. Sreedhar and S. Midkiff, Escape analysis for Java, in: OOPSLA ’99:
Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and
applications (1999), pp. 1–19.
[7] Guyer, S. Z., K. S. McKinley and D. Frampton, 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 (2006), pp. 364–375.
[8] Hackett, B. and R. Rugina, Region-based shape analysis with tracked locations, in: POPL ’05: Proceedings of the 32nd
ACM SIGPLAN-SIGACT symposium on Principles of programming languages (2005), pp. 310–323.
[9] Hallenberg, N., M. Elsman and M. Tofte, Combining region inference and garbage collection, in: PLDI ’02:
Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation (2002),
pp. 141–152.
[10] Heine, D. L. and M. S. Lam, A practical flow-sensitive and context-sensitive c and c++ memory leak detector, in: PLDI
’03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation (2003),
pp. 168–181.
[11] Hopcroft, J. E. and J. D. Ullman, “Introduction To Automata Theory, Languages, And Computation,” Addison-Wesley
Longman Publishing Co., Inc., Boston, MA, USA, 1990.
[12] Inoue, K., H. Seki and H. Yagi, Analysis of functional programs to detect run-time garbage cells, ACM Trans. Program.
Lang. Syst. 10 (1988), pp. 555–578.
[13] Jones, N. D. and S. S. Muchnick, Flow analysis and optimization of lisp-like structures, in: POPL ’79: Proceedings of
the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (1979), pp. 244–256.
[14] Jones, R. and R. Lins, “Garbage collection: algorithms for automatic dynamic memory management,” John Wiley &
Sons, Inc., New York, NY, USA, 1996.
[15] Jones, S. B. and D. L. Metayer, Compile-time garbage collection by sharing analysis, in: FPCA ’89: Proceedings of the
fourth international conference on Functional programming languages and computer architecture (1989), pp. 54–74.
[16] Karkare, A., A. Sanyal and U. Khedker, Effectiveness of garbage collection in MIT/GNU scheme,
http://arxiv.org/abs/cs/0611093 (2006).
[17] Khedker, U., A. Sanyal and A. Karkare, Heap reference analysis using access graphs, Submitted to ACM Transactions
on Programming Languages and Systems, copy available at http://arxiv.org/abs//0608104 (2006).
[18] Mohri, M. and M.-J. Nederhof, Regular approximation of context-free grammars through transformation, in: J.-C.
Junqua and G. van Noord, editors, Robustness in Language and Speech Technology, Kluwer Academic Publishers,
Dordrecht, 2000 pp. 251–261.
[19] Röjemo, N. and C. Runciman, Lag, drag, void and use—heap profiling and space-efficient compilation revisited, in:
ICFP ’96: Proceedings of the first ACM SIGPLAN international conference on Functional programming (1996), pp.
34–41.
[20] Sagiv, M., T. Reps and R. Wilhelm, Parametric shape analysis via 3-valued logic, in: POPL ’99: Proceedings of the
26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (1999), pp. 105–118.
[21] Sagiv, M., T. Reps and R. Wilhelm, Parametric shape analysis via 3-valued logic, ACM Transactions on Programming
Languages and Systems 24 (2002), pp. 217–298.
[22] Shaham, R., E. K. Kolodner and M. Sagiv, On the effectiveness of gc in java, in: ISMM ’00: Proceedings of the 2nd
international symposium on Memory management (2000), pp. 12–17.
[23] Shaham, R., E. K. Kolodner and M. Sagiv, Heap profiling for space-efficient java, in: PLDI ’01: Proceedings of the
ACM SIGPLAN 2001 conference on Programming language design and implementation (2001), pp. 104–113.
[24] Shaham, R., E. K. Kolodner and M. Sagiv, Estimating the impact of heap liveness information on space consumption
in Java, in: ISMM ’02: Proceedings of the 3rd international symposium on Memory management (2002), pp. 64–75.
[25] Shaham, R., E. Yahav, E. K. Kolodner and M. Sagiv, Establishing local temporal heap safety properties with
applications to compile-time memory management, Sci. Comput. Program. 58 (2005), pp. 264–289.
[26] Tofte, M. and L. Birkedal, A region inference algorithm, ACM Transactions on Programming Languages and Systems
20 (1998), pp. 724–767.

14

A

Live Access Patterns

Liveness Environment

Liveness Environment

Point

for e at π

after e

at π

(π)

(σ)

(L )

π1

π4

15

π5

π7
π8
π9

)

(

1
list1.({ε} ∪ {00̄} · σ ∪ {1} · X F app
({1̄} · σ)),

1
list1.({ε} ∪ {00̄} · σ ∪ {1} · X F app
({1̄} · σ)),

)

(

1
list1.({ε} ∪ {00̄} · σ ∪ {1} · X F app
({1̄} · σ)),

)

1
list1.({ε} ∪ {00̄} · σ ∪ {1} · X F app
({1̄} · σ)),

)

(

1
list1.({ε} ∪ {00̄} · σ ∪ {1} · X F app
({1̄} · σ)),

)

(

1
list1.({ε} ∪ {00̄} · σ ∪ {1} · X F app
({1̄} · σ)),

)

(

1
list1.({ε} ∪ {00̄} · σ ∪ {1} · X F app
({1̄} · σ)),

)

(

1
list1.({ε} ∪ {00̄} · σ ∪ {1} · X F app
({1̄} · σ)),

0/

{ε}

(

{ε}

(

σ

(

1
list1.({ε} ∪ {00̄} · σ ∪ {1} · X F app
({1̄} · σ)),
2
list2.(σ ∪ X F app
({1̄} · σ))
2
list2.(σ ∪ X F app
({1̄} · σ))
2
list2.X F app
({1̄} · σ)

0/

σ
{0̄} · σ

(

{ε} ∪ {00̄} · σ

(

{1̄} · σ

X F app ({1̄} · σ)
1

1
list1.{1} · X F app
({1̄} · σ),
2
list2.X F app
({1̄} · σ)
1
list1.{1} · X F app
({1̄} · σ),
2
list2.X F app
({1̄} · σ)

2
list2.(σ ∪ X F app
({1̄} · σ))
2
list2.(σ ∪ X F app
({1̄} · σ))
2
list2.(σ ∪ X F app
({1̄} · σ))
2
list2.X F app
({1̄} · σ)
2
list2.X F app
({1̄} · σ)
2
list2.X F app
({1̄} · σ)

0/

(

1
list1.{1} · X F app
({1̄} · σ),

)

{list2.X F app ({1̄} · σ)}

(

1
list1.{1} · X F app
({1̄} · σ),

)

(

1
list1.{1} · X F app
({1̄} · σ),

2

π10

{1} · X F app ({1̄} · σ)

{list2.X F app ({1̄} · σ)}

π11

2
X F app
({1̄} · σ)

0/

2

2
list2.(σ ∪ X F app
({1̄} · σ))

2

2
list2.X F app
({1̄} · σ)
2
list2.X F app
({1̄} · σ)
2
list2.X F app
({1̄} · σ)

2
{list2.X F app
({1̄} · σ)}

)

)
)

)
)
)

Karkare, Khedker and Sanyal

π3

π6

1
list1.({ε} ∪ {00̄} · σ ∪ {1} · X F app
({1̄} · σ)),

σ

π2

(X E (e, σ, L ))
(

Computation of Liveness for app

Program

