Interprocedural compatibility analysis for static object preallocation.
We present an interprocedural and compositional algorithm for finding pairs of compatible allocation sites, which have the property that no object allocated at one site is live at the same time as any object allocated at the other site. If an allocation site is compatible with itself, it is said to be unitary: at most one object allocated at that site is live at any given point in the, execution of the program. We use the results of the analysis to statically preallocate memory space for the objects allocated at unitary sites, thus simplifying the computation of an upper bound on the amount of memory required to execute the program. We also use the analysis to enable objects allocated at several compatible allocation sites to share the same preallocated memory. Our experimental results show that, for our set of Java benchmark programs, 60% of the allocation sites are unitary and can be statically preallocated. Moreover, allowing compatible unitary allocation sites to share the same preallocated memory leads to a 95% reduction in the amount of memory preallocated for these sites.
INTRODUCTION
Modern object-oriented languages such as Java present
a clean and simple memory model: conceptually, all objects
are allocated in a garbage-collected heap. While this
abstraction simplies many aspects of the program devel-
opment, it can complicate the calculation of an accurate
upper bound on the amount of memory required to execute
the program. Scenarios in which this upper bound is especially
important include the development of programs for
embedded systems with hard limits on the amount of available
memory and the estimation of scoped memory sizes
for real-time threads that allocate objects in sized scoped
memories [9].
This paper presents a static program analysis designed to
nd pairs of compatible allocation sites; two sites are compatible
if no object allocated at one site may be live at the
same time as any object allocated at the other site. If an allocation
site is compatible with itself (we call such allocation
sites unitary allocation sites), then at any time during the
execution of the program, there is at most one live object
that was allocated at that site. It is therefore possible to
statically preallocate a xed amount of space for that allocation
site, then use that space to hold all objects allocated
at that site. Any further space usage analyses can then focus
only on the non-unitary allocation sites.
Our analysis uses techniques inspired from register allocation
[2, 6] to reduce the amount of memory required to
hold objects allocated at unitary allocation sites. The basic
approach is to build and color an incompatibility graph. The
nodes in this graph are the unitary allocation sites. There is
an undirected edge between two nodes if the nodes are not
compatible. The analysis applies a coloring algorithm that
assigns a minimal number of colors to the graph nodes subject
to the constraint that incompatible nodes have dierent
colors. This information enables the compiler to statically
preallocate a xed amount of memory for each color. At
each unitary allocation site, the generated code bypasses the
standard dynamic allocation mechanism and instead simply
returns a pointer to the start of the statically preallocated
memory for that allocation site's color. The object is stored
in this memory for the duration of its lifetime in the com-
putation. Our algorithm therefore enables objects allocated
at compatible allocation sites to share the same memory.
Results from our implemented analysis show that, for our
set of Java benchmark programs, our analysis is able to identify
60% of all allocation sites in the program as unitary allocation
sites. Furthermore, our incompatibility graph coloring
algorithm delivers a 95% reduction in the amount of
memory required to store objects allocated at these unitary
allocation sites. We attribute the high percentage of unitary
allocation sites to specic object usage patterns characteristic
of Java programs: many unitary allocation sites allocate
exception, string buer, or iterator objects.
We identify two potential benets of our analysis. First,
it can be used to simplify a computation of the amount of
memory required to execute a given program. We have implemented
a memory requirements analysis that, when pos-
sible, computes a symbolic mathematical expression for this
amount of memory [16]. Our results from [16] show that preceding
the memory requirements analysis with the analysis
presented in this paper, then using the results to compute
the memory requirements of unitary sites separately, can
signicantly improve both the precision and the e-ciency of
the subsequent memory requirements analysis. The second
potential benet is a reduction in the memory management
overhead. By enabling the compiler to convert heap allocation
to static allocation, our analysis can reduce the amount
of time required to allocate and reclaim memory.
This paper makes the following contributions:
Object Liveness Analysis: It presents a compositional
and interprocedural object liveness analysis that
conservatively estimates the set of objects that are live
at each program point.
Compatibility Analysis: It presents a compositional
and interprocedural analysis that nds sets of compatible
allocation sites. All objects allocated at sites in
each such set can share the same statically preallocated
memory. This analysis uses the results of the object
liveness analysis.
Implementation: We implemented our analyses in
the MIT Flex [3] compiler and used them to analyze
a set of Java benchmark programs. Our results show
that our analyses are able to classify the majority of
the allocation sites as unitary allocation sites, and that
many such sites can share the same memory. We also
implemented and evaluated a compiler optimization
that transforms each unitary allocation site to use pre-allocated
memory space instead of invoking the standard
memory allocator.
The rest of this paper is organized as follows. Section 2
presents the analysis algorithm. Section 3 describes the implementation
and presents our experimental results. We discuss
related work in Section 4 and conclude in Section 5.
2. ANALYSIS PRESENTATION
Given a program P , the goal of the analysis is to detect
pairs of compatible allocation sites from P , i.e., sites that
have the property that no object allocated at one site is live
at the same time as any object allocated at the other site.
Equivalently, the analysis identies all pairs of incompatible
allocation sites, i.e., pairs of sites such that an object allocated
at the rst site and an object allocated at the second
site may both be live at the same time in some possible execution
of P . An object is live if any of its elds or methods
is used in the future. It is easy to prove the following fact:
Fact 1. Two allocation sites are incompatible if an object
allocated at one site is live at the program point that
corresponds to the other site.
To identify the objects that are live at a program point,
the analysis needs to track the use of objects throughout the
program. There are two complications. First, we have an
abstraction problem: the analysis must use a nite abstraction
to reason about the potentially unbounded number of
objects that the program may create. Second, some parts
of the program may read heap references created by other
parts of the program. Using a full-edged

ow-sensitive
pointer analysis would substantially increase the time and
space requirements of our analysis; a
ow-insensitive pointer
analysis [18, 5] would not provide su-cient precision since
liveness is essentially a
ow-sensitive property. We address
these complications as follows:
We use the object allocation site model [13]: all objects
allocated by a given statement are modelled by an inside
node 1 associated with that statement's program
label.
The analysis tracks only the objects pointed to by local
variables. Nodes whose address may be stored into the
heap are said to escape into the heap. The analysis
conservatively assumes that such a node is not unitary
(to ensure this, it sets the node to be incompatible with
itself). Notice that, in a usual Java program, there
are many objects that are typically manipulated only
through local variables: exceptions, iterators, string
buers, etc. 2
Under these assumptions, a node that does not escape
into the heap is live at a given program point if and only if
a variable that is live at that program point refers to that
node. Variable liveness is a well-studied data
ow analysis [2,
6] and we do not present it here. As a quick reminder, a
variable v is live at a program point if and only if there
is a path through the control
ow graph that starts at that
program point, does not contain any denition of v and ends
at an instruction that uses v.
The analysis has to process the call instructions accu-
rately. For example, it needs to know the nodes returned
from a call and the nodes that escape into the heap during
the execution of an invoked method. Reanalyzing each
method for each call instruction (which corresponds conceptually
to inlining that method) would be ine-cient. In-
stead, we use parameter nodes to obtain a single context-sensitive
analysis result for each method. The parameter
nodes are placeholders for the nodes passed as actual argu-
ments. When the analysis processes a call instruction, it
replaces the parameter nodes with the nodes sent as argu-
ments. Hence, the analysis is compositional : in the absence
of recursion, it analyzes each method exactly once to extract
a single analysis result. 3 At each call site, it instantiates the
result for the calling context of that particular call site.
We use the adjective \inside" to make the distinction from the \pa-
rameter" nodes that we introduce later in the paper.
2 It is possible to increase the precision of this analyis by tracking one
or more levels of heap references (similar to [8]).
3 The analysis may analyze recursive methods multiple times before
it reaches a xed point.
I

Figure

1: Node Abstraction

Figure

presents a summary of our node abstraction. We
use the following notation: INode denotes the set of all inside
nodes, PNode denotes the set of parameter nodes, and Node
denotes the set of all nodes. When analyzing a method M ,
the analysis scope is the method M and all the methods that
it transitively invokes. The inside nodes model the objects
allocated in this scope. n I
lb denotes the inside node associated
with the allocation site from label lb (the superscript I
stands for \inside"; it is not a free variable). n I
lb represents
all objects allocated at label lb in the currently analyzed
scope. The parameter nodes model the objects that M receives
as arguments. The parameter node n P
models the
object that the currently analyzed method receives as its
ith argument of object type. 4
The analysis has two steps, each one an analysis in itself.
The rst analysis computes the objects live at each allocation
site or call instruction. 5 The second analysis uses the
liveness information to compute the incompatibility pairs.
We formulate our analyses as systems of set inclusion constraints
and use a bottom-up, iterative xed-point algorithm
to compute the least (under set inclusion) solution of the
constraints. For a given program, the number of nodes is
bounded by the number of object allocation sites and the
number of parameters. Hence, as our constraints are mono-
tonic, all xed point computations are guaranteed to terminate

The rest of this section is organized as follows. Section 2.1
describes the execution of the analysis on a small example.
Section 2.2 presents the program representation that the
analysis operates on. Section 2.3 describes the object liveness
analysis. In Section 2.4, we describe how to use the
object liveness information to compute the incompatibility
pairs. Section 2.5 discusses how to apply our techniques to
multithreaded programs.
2.1 Example
Consider the Java code from Figure 2. The program creates
a linked list that contains the integers from 0 to 9,
removes from the list all elements that satisfy a specic condition
(the even numbers in our case), then prints a string
representation of the remaining list. The program contains
six lines that allocate objects. The two Iterators from lines
3a and 3b are allocated in library code, at the same allocation
site. The other four lines allocate objects directly by
executing new instructions. For the sake of simplicity, we ignore
the other objects allocated in the library. In our exam-
ple, we have ve inside nodes. Node n I
1 represents the linked
list allocated at line 1, node n I
2 represents the Integers allocated
at line 2, etc. The iterators from lines 3a and 3b are
both represented by the same node n I
3 (they are allocated at
the same site). Figure 3 presents the incompatibility graph
for this example.
4 I.e., not primitive types such as int, char etc.
5 The object liveness analysis is able to nd the live nodes at any
program point; however, for e-ciency reasons, we produce an analysis
result only for the relevant statements.
static void main(String args[]) {
static List createList(int size) {
1: List list = new LinkedList();
{
2: Integer
list.add(v);
return list;
static void filterList(List l) {
{
static String listToString(List l) {
4: StringBuffer buffer = new StringBuffer();
{
buffer.append(v).append(" ");
5: return new String(buffer);

Figure

2: Example Code
The analysis processes the methods in a bottom-up fash-
ion, starting from the leaves of the call graph. The library
method LinkedList.add (not shown in Figure 2) causes its
parameter node n P
1 is the this parameter) to escape
into the heap (its address is stored in a list cell). createList
calls add with n I
2 as argument; therefore, the analysis instantiates
2 with n I
2 and detects that n I
escapes. In filterList,
the parameter node n P
(the list) escapes into the heap because
list.iterator() stores a reference to the underlying
list in the iterator that it creates.
In the listToString method, n I
4 is live \over the call" to
list.iterator() that allocates n I
is pointed to by the
local variable buffer, which is live both before and after the
call. Therefore, n I
4 is incompatible with n I
3 . Because n I
4 is
live at line 5, n I
4 is also incompatible with n I
5 . n I
3 is not live
n In In In In I
Figure

3: Incompatibility graph for the code from

Figure

2. Circles represent inside nodes; a double
circle indicates that the node escapes into the heap.
I
3 and n I
5 are compatible unitary nodes.
Name Format Informal semantics
local variable into another
new C create one object of class C
create a heap reference
RETURN return v normal return from a method
THROW throw v exceptional return from a method
nodes in join points

Figure

4: Instructions relevant for the analysis.
at line 5, so n I
3 and n I
5 are still compatible. The parameter
node n P
(the list) is live at lines 4 and 3b (but not at 5).
Therefore, n P
1 is incompatible with n I
4 and n I
3 .
The analysis of main detects that l points to n I
(because
createList returns n I
As the parameter of filterList
escapes into the heap, the analysis detects that n I
escapes.
When processing the call to listToString, the analysis instantiates
1 with n I
1 and discovers the incompatibility pairs
hn I
4 i. The analysis has already determined
that n I
escapes into the heap and is not an unitary node;
we generate the last two incompatibility pairs for purely expository
purposes.
The graph coloring algorithm colors n I
3 and n I
5 with the
same color. This means that the two iterators and the String
allocated by the program have the property that no two of
them are live at the same time. Hence, the compiler can
statically allocate all of these objects into the same memory
space.
2.2 Program Representation
We work in the context of a static compiler that compiles
the entire code of the application before the application is
deployed and executes. Our compiler provides full re
ec-
tive access to classes and emulates the dynamic loading of
classes precompiled into the executable. It does not support
the dynamic loading of classes unknown to the compiler at
compile time. This approach is acceptable for our class of
target applications, real time software for embedded devices,
for which memory consumption analysis is particularly important

The analyzed program consists of a set of methods
with a distinguished main method.
Each method m is represented by its control
ow graph
CFGm . The vertices of CFGm are the labels of the instructions
composing m's body, while the edges represent the
ow of control inside m. Each method has local variables
Var is the set of local variables and method parameters.

Figure

4 contains the instructions that are relevant for
the analysis. We assume that the analyzed program has
already been converted into the Single Static Information
(SSI) form [4], an extension of the Static Single Assignment
explain the dierences later in this sec-
tion).
Our intermediate representation models the creation and
the propagation of exceptions explicitly. Each instruction
that might generate an exception is preceded by a test. If an
exceptional situation is detected (e.g., a null pointer deref-
erencing), our intermediate representation follows the Java
convention of allocating and initializing an exception ob-
ject, (e.g., a NullPointerException), then propagating the
exception to the appropriate catch block or throwing the
exception out of the method if no such block exists. Notice
that due to the semantics of the Java programming lan-
guage, each instruction that can throw an exception is also
a potential object allocation site. Moreover, the exception
objects are rst class objects: once an exception is caught,
references to it can be stored into the heap or passed as
arguments of invoked methods. In practice, we apply an optimization
so that each method contains a single allocation
site for each automatically inserted exception (for example,
NullPointerException and ArrayIndexOutOfBoundsException)
that the method may generate but not catch. When the
method detects such an exception, it jumps to that allocation
site, which allocates the exception object and then
executes an exceptional return out of the method.
To allow the inter-procedural propagation of exceptions,
a CALL instruction from label lb has two successors:
for the normal termination of the method and
for the case when an exception is thrown out of
the invoked method.
In both cases | locally generated exceptions or exceptions
thrown from an invoked method | the control is
passed to the appropriate catch block, if any. This block
is determined by a succession of \instanceof" tests. If no
applicable block exists, the exception is propagated into
the caller of the current method by a THROW instruction
\throw v". Unlike a throw instruction from the Java
language, a THROW instruction from our intermediate
representation always terminates the execution of the
current method.
Note: we do not check for exceptions that are subclasses
of java.lang.Error.
6 This is not a signicant restriction: as
we work in the context of a static compiler, where we know
the entire code and class hierarchy, most of these errors cannot
be raised by a program that compiled successfully in our
system, e.g. VirtualMachineError, NoSuchFieldError etc.
If the program raises any one of the rest of the errors, e.g.,
OutOfMemoryError, it aborts. In most of the cases, this is
the intended behavior. In particular, none of our benchmarks
catches this kind of exception.
We next present the informal semantics of the instructions
from

Figure

4. A COPY instruction copies the
6 In the Java language, these exceptions correspond to severe errors
in the virtual machine that the program is not expected to handle.
value of local variable v1 into local variable v2 . A PHI instruction
is an SSA  node that appears
in the join points of the control
ow graph; it ensures that
each use of a local variable has exactly one reaching de-
nition. If the control arrived in the PHI instruction on the
ith incoming edge, v i is copied into v. A NEW instruction
new C" allocates a new object of class C and stores a
reference to it in the local variable v.
A CALL instruction \hvN ; vE
calls the method named mn of the object pointed to by
v1 , with the arguments If the execution of
the invoked method terminates with a RETURN instruction
\return v", the address of the returned object is stored into
vN and the control
ow goes to succN (lb ), where lb is the
label of the call instruction. Otherwise, i.e., if an exception
was thrown out of the invoked method, the address of the
exception object is stored into vE and the control
ow goes
to succE (lb ).
A TYPESWITCH instruction \hv1 ;
C" corresponds to a Java \instanceof" test. It checks
whether the class of the object pointed to by v is a subclass
of C. v is split into two variables: v1 is v's restriction on the
true branch, while v2 is v's restriction on the false branch.
Therefore, the object pointed to by v1 is an instance of C,
while the object pointed to by v2 is not. A TYPESWITCH
instruction is a simple example of an SSI \sigma" node,
(v)", that the SSI form introduces to preserve
the
ow sensitive information acquired in the test instruc-
tions. SSI thus allows the elegant construction of predicated
data
ow analyses. Apart from this \variable splitting", SSI
is similar to the SSA form. In particular, the SSI conversion
seems to require linear time in practice [4].
Finally, a STORE instruction \v1 sets the eld
f of the object referenced by v1 to point to the object referenced
by v2 . The other instructions are irrelevant for our
analysis. In particular, as we do not track heap references,
the analysis cannot gain any additional information by analyzing
the instructions that read references from memory.
However, we do analyze the STORE instructions because
we need to identify the objects that escape into the heap.
We assume that we have a precomputed call
each label lb that corresponds to a CALL instruction,
callees(lb ) is the set of methods that that call instruction
may invoke. The analysis works with any conservative approximation
of the runtime call graph. Our implementation
uses a simplied version of the Cartesian Product Algorithm
[1].
2.3 Object Liveness Analysis
Consider a method M , a label/program point lb inside
M , and let live(lb ) denote the set of inside and parameter
nodes that are live at lb . We conservatively consider that a
node is live at lb i it is pointed to by one of the variables
that are live at that point:
v live in lb P (v)
where P (v) is the set of nodes to which v may point. To
interpret the results, we need to compute the set EG of
inside nodes that escape into the heap during the execution
7 For the sake of simplicity, in the presentation of the analysis we
consider only instance methods (in Java terms, non-static methods),
i.e., with v1 as the this argument. The implementation handles both
instance methods and static methods.
of the program. To be able to process the calls to M , we also
compute the set of nodes that can be normally returned from
M , RN (M ), the set of exceptions thrown from M , RE (M ),
and the set of parameter nodes that may escape into the
heap during the execution of M , E(M ). More formally, the
analysis computes the following mathematical objects:
EG  INode
We formulate the analysis as a set inclusion constraint
problem. Figure 5 presents the constraints generated for a
method
the beginning of the method, p i points to the parameter
node n P
. A COPY instruction sets v1 to point
to all nodes that v2 points to; accordingly, the analysis generates
the constraint P The case of a PHI
instruction is similar. A NEW instruction from label lb , \v
new C", makes v point to the inside node n I
lb attached to
that allocation site. The constraints generated for RETURN
and THROW add more nodes to RN (M) and RE (M ), re-
spectively. A STORE instruction \v1 causes all the
nodes pointed to by v2 to escape into the heap. Accordingly,
the nodes from P (v2) are distributed between EG (the inside
nodes) and E(M) (the parameter nodes).
A TYPESWITCH instruction \hv1 ; v2
C" works as a type lter: v1 points to those nodes from P (v)
that may represent objects of a type that is a subtype of C,
while v2 points to those nodes from P (v) that may represent
objects of a type that is not a subtype of C. In Figure 5,
denotes the set of all subtypes (i.e., Java sub-
classes) of C (including C). We can precisely determine the
type type(n I
of an inside node n I
lb 0 by examining the NEW
instruction from label lb 0 . Therefore, we can precisely distribute
the inside nodes between P (v1 ) and P (v2 ). As we
do not know the exact types of the objects represented by
the parameter nodes, we conservatively put these nodes in
both sets. 9
A CALL instruction \hvN ; vE
vN to point to the nodes that may be returned from the
invoked method(s). For each possible callee m 2 callees(lb ),
we include the nodes from RN (m) into P (vN ). Note that
RN (m) is a parameterized result. We therefore instantiate
RN (m) before use by replacing each parameter node n P
i with
the nodes that the corresponding argument v i points to, i.e.,
the nodes from P (v i ). The case of vE is analogous. The execution
of the invoked method m may also cause some of the
nodes passed as arguments to escape into the heap. Accord-
ingly, the analysis generates a constraint that instantiates
the set E(m) and the uses the nodes from the resulting set
E(m)hP (v1 to update EG and E(M ).
Here is a more formal and general denition of the previously
mentioned instantiation operation: if S  Node is a
set that contains some of the parameter nodes n P
(not necessarily all), and
8 As we use the SSI form, this is the only denition of v1 ; therefore,
we do not lose any precision by using \=" instead of \".
9 A better solution would be to consider the declared type Cp of the
corresponding parameter and check that Cp and C have at least one
common subtype.
s
method entry P (p
where are M 's parameters.
RETURN: return v RN (M)  P (v)
THROW: throw v RE (M)  P (v)
RN (m)hP (v1
let
E(M)  A \ PNode ; EG  A \ INode
TYPESWITCH:
denotes the set of subclasses of class C.

Figure

5: Constraints for the object liveness analysis. For each method M , we compute RN (M), RE (M), E(M)
and P (v) for each variable v live in at a relevant label. We also compute the set EG of inside nodes that
escape into the heap.
2.4 Computing the Incompatibility Pairs
Once the computation of the object liveness information
completes, the analysis computes the (global) set of pairs
of incompatible allocation sites IncG  INode  INode. 10
The analysis uses this set of incompatible allocation sites
to detect the unitary allocation sites and to construct the
compatibility classes.

Figure

6 presents the constraints used to compute IncG .
An allocation site from label lb is incompatible with all the
allocation sites whose corresponding nodes are live at lb .
However, as some of the nodes from live(lb ) may be parameter
nodes, we cannot generate all incompatibility pairs
directly. Instead, for each method M , the analysis collects
the incompatibility pairs involving one parameter node into
a set of parametric incompatibilities ParInc(M ). It instantiates
this set at each call to M , similar to the way it instantiates
Recall that there is a bijection between the inside nodes and the
allocation sites.
(S i is the set of nodes that the ith argument sent to M
might point to). Notice that some S i may contain a parameter
node from M 's caller. However, at some point in the
call graph, each incompatibility pair will involve only inside
nodes and will be passed to IncG .
To simplify the equations from Figure 6, for each method
M , we compute the entire set of incompatibility pairs
AllInc(M ). After AllInc(M) is computed, the pairs that
contain only inside nodes are put in the global set of incompatibilities
IncG ; the pair that contains a parameter
node are put in ParInc(M ). Our implementation of this
algorithm performs this separation \on the
y", as soon as
an incompatibility pair is generated, without the need for
AllInc(M ).
In the case of a CALL instruction, we have two kinds of
incompatibility pairs. We have already mentioned the rst
kind: the pairs obtained by instantiating ParInc(m); 8m 2
callees(lb ). In addition, each node that is live \over the call"
(i.e., before and after the call) is incompatible with all the
nodes corresponding to the allocation sites from the invoked
methods. To increase the precision, we treat the normal and
new C live(lb )  fn I
lb g  AllInc(M)
. &
(live(lb) \ live(succN (lb ))) AN (m)  AllInc(M)
(live(lb) \ live(succE (lb))) AE (m)  AllInc(M)
AllInc(M) \ (INode  INode)  IncG
AllInc(M) n (INode  INode)  ParInc(M)

Figure

Constraints for computing the set of incompatibility pairs.
Instruction at label lb
in method M Condition Generated constraints
new C lb ; return n I

Figure

7: Constraints for computing AN , AE . For each relevant instruction, if the condition from the second
column is satised, the corresponding constraint from the third column is generated.
the exceptional exit from an invoked method separately. Let
AN (m)  INode be the set of inside nodes that represent
the objects that may be allocated during a method execution
that returns normally. Similarly, let AE (m)  INode
be the set of inside nodes that represent the objects that
may be allocated during an invocation of m that returns
with an exception. We describe later how to compute these
sets; for the moment we suppose the analysis computes them
just before it starts to generate the incompatibility pairs.
Let succN (lb ) be the successor corresponding to the normal
return from the CALL instruction from label lb . The
nodes from live(lb ) \ live(succN (lb are incompatible with
all nodes from AN (m). A similar relation holds for AE (m).
Computation of AN (M), AE (M)
Given a label lb from the code of some method M , we dene
the predicate \lb ; return" to be true i there is
a path in CFGM from lb to a RETURN instruction (i.e.,
the instruction from label lb may be executed in an invocation
of M that returns normally). Analogously, we dene
throw" to be true i there is a path from lb to
a THROW instruction. Computing these predicates is an
easy graph reachability problem. For a method M , AN (M)
contains each inside node n I
lb that corresponds to a NEW
instruction at label lb such that lb ; return. In addi-
tion, for a CALL instruction from label lb in M 's code, if
then we add all nodes from AN (m)
into AN (M ), for each possible callee m. Analogously, if
The computation
of AE (m) is similar. Figure 7 formally presents the constraints
for computing the sets AN (M) and AE (M ).
2.5 Multithreaded Applications
So far, we have presented the analysis in the context of
a single-threaded application. For a multithreaded appli-
cation, the analysis needs to examine all methods that are
transitively called from the main method and from the run()
methods of the threads that may be started. In addition, all
nodes that correspond to started threads need to be marked
as escaped nodes. The rest of the analysis is unchanged.
In Java, each thread is represented by a thread object
allocated in the heap. For an object to escape one thread
to be accessed by another, it must be reachable from either
the thread object or a static class variable (global variables
are called static class variables in Java). In both cases, the
analysis determines that the corresponding allocation site
is not unitary. Therefore, all objects allocated at unitary
allocation sites are local to the thread that created them and
do not escape to other threads. Although we know that no
two objects allocated by the same thread at the same unitary
site are live at any given moment, we can have multiple live
objects allocated at this site by dierent threads. Hence, for
each group of compatible unitary sites, we need to allocate
one memory slot per thread, instead of one per program.
The compiler generates code such that each time the program
starts a new thread, it preallocates memory space for
all unitary allocation sites that may be executed by that
thread. For each unitary allocation site, the compiler generates
code that retrieves the current thread and uses the
preallocated memory space for the unitary site in the current
thread. When a thread terminates its execution, it deallocates
its preallocated memory space. As only thread-local
objects used that space, this deallocation does not create
dangling references. To bound the memory space occupied
by the unitary allocation sites, we need to bound the number
of threads that simultaneously execute in the program
at any given time.
2.6 Optimization for Single-Thread Programs
In the previous sections, we consider a node that escapes
into the heap to be incompatible with all other nodes, including
itself. This is equivalent to considering the node to
be live during the entire program. We can gain additional
precision by considering that once a node escapes, it is live
only for the rest of the program. This enhancement allows
us to preallocate even objects that escape into the heap,
if their allocation site executes at most once. This section
presents the changes to our analysis that apply this idea.
We no longer use the global set EG . Instead, for each label
lb , E(lb)  Node denotes the set of nodes that the instruction
at label lb may store a reference to into the heap. This
set is relevant only for labels that correspond to STOREs
and CALLs; for a CALL, it represents the nodes that escape
during the execution of the invoked method.
We extend the set of objects live at label lb (from method
M) to include all objects that are escaped by instructions
at labels lb ' from M that can reach lb in CFGM :
live(lb
v live in lb P (v) [
We change the constraints from Figure 5 as follows: for
a STORE instruction \v1 only the
constraint E(lb
we generate the same constraints as
before for P (vN ) and P (vE ), and the additional constraint
The rules for STORE and CALL no longer generate any
constraints for EG (unused now) and E(M ). Instead, we
dene E(M) as
lb in M
E(lb)
E(M)  P(Node) denotes the set of all nodes | not
only parameter nodes as before, but also inside nodes | that
escape into the heap during M 's execution.
The rest of the analysis is unchanged. The new denition
of live(lb ) ensures that if a node escapes into the heap at
some program point, it is incompatible with all nodes that
are live at any future program point. Notice that objects
allocated at unitary sites are no longer guaranteed to be
thread local, and we cannot apply the preallocation optimization
described at the end of Section 2.5. Therefore, we
use this version of the analysis only for single thread programs

3. EXPERIMENTAL RESULTS
We have implemented our analysis, including the optimization
from Section 2.6, in the MIT Flex compiler system
[3]. We have also implemented the compiler transformation
for memory preallocation: our compiler generates
executables with the property that unitary sites use preallocated
memory space instead of calling the memory allocation
primitive. The memory for these sites is preallocated
at the beginning of the program. Our implementation does
not currently support multithreaded programs as described
in Section 2.5.
We measure the eectiveness of our analysis by using it to
nd unitary allocation sites in a set of Java programs. We
obtained our results on a Pentium 4 2.8Ghz system with
2GB of memory running RedHat Linux 7.3. We ran our
compiler and analysis using Sun JDK 1.4.1 (hotspot, mixed
mode); the compiler generates native executables that we
ran on the same machine. Table 1 presents a description of
the programs in our benchmark suite. We analyze programs
from the SPECjvm98 benchmark suite 11 and from the Java
version of the Olden benchmark suite [12, 11]. In addition,
we analyze JLex, JavaCUP, and 205 raytrace.

Table

presents several statistics that indicate the size of
each benchmark and the analysis time. The statistics refer
to the user code plus all library methods called from the
user code. As the data in Table 2 indicate, in general, the
time required to perform our analysis is of the same order
of magnitude as the time required to build the intermediate
representation of the program. The only exceptions are
202 jess and 213 javac.

Table

3 presents the number of total allocation sites and
unitary allocation sites in each program. These results show
that our analysis is usually able to identify the majority of
these sites as unitary sites: of the 14065 allocation sites in
our benchmarks, our analysis is able to classify 8396 (60%)
as unitary sites. For twelve of our twenty benchmarks, the
analysis is able to recognize over 80% of the allocation sites
as unitary.

Table

3 also presents results for the allocation
sites that allocate exceptions (i.e., any subclass of
java.lang.Throwable), non-exceptions (the rest of the ob-
jects), and java.lang.StringBuers (a special case of non-
exceptions). For each category, we present the total number
of allocation sites of that kind and the proportion of these
sites that are unitary. The majority of the unitary allocation
sites in our benchmarks allocate exception or string buer
objects. Of the 9660 total exception allocation sites in our
benchmarks, our analysis is able to recognize 6602 (68%)
as unitary sites. For thirteen of our twenty benchmarks,
the analysis is able to recognize over 90% of the exception
allocation sites as unitary sites. Of the 1293 string buer
allocation sites, our analysis is able to recognize 1190 (92%)
as unitary sites. For eight benchmarks, the analysis is able
to recognize over 95% of the string buer allocation sites as
unitary sites.

Table

4 presents the size of the statically preallocated
memory area that is used to store the objects created at
unitary allocation sites. The second column of the table
presents results for the case where each unitary allocation
site has its own preallocated memory chunk. As described
in the introduction of the paper, we can decrease the pre-allocated
memory size signicantly if we use a graph coloring
algorithm to allow compatible unitary allocation sites to
share the same preallocated memory area. The third column
of

Table

presents results for this case. Our compiler
optimization always uses the graph coloring algorithm; we
provide the second column for comparison purposes only.
11 With the exception of 227 mtrt, which is multithreaded.
Application Description
SPECjvm98 benchmark set
200 check Simple program; tests JVM features
compress File compression tool
jess Expert system shell
209 db Database application
213 javac JDK 1.0.2 Java compiler
222 mpegaudio Audio le decompression tool
228 jack Java parser generator
Java Olden benchmark set
BH Barnes-Hut N-body solver
BiSort Bitonic Sort
Em3d Models the propagation of electromagnetic waves through three dimensional objects
Health Simulates a health-care system
MST Computes the minimum spanning tree in a graph using Bentley's algorithm
Perimeter Computes the perimeter of a region in a binary image represented by a quadtree
Power Maximizes the economic e-ciency of a community of power consumers
TSP Solves the traveling salesman problem using a randomized algorithm
TreeAdd Recursive depth-rst traversal of a tree to sum the node values
Voronoi Computes a Voronoi diagram for a random set of points
Miscellaneous
raytrace Single thread raytracer (not an o-cial part of SPECjvm98)
JLex Java lexer generator
JavaCUP Java parser generator

Table

1: Analyzed Applications
Application Analyzed
methods
Bytecode
instrs
size
(instr.)
SSI
conversion
time
Analysis
time
200 check 208 7962 10353 1.1 4.1
compress 314 8343 11869 1.2 7.4
jess 1048 31061 44746 5.3 101.2
222 mpegaudio 511 18041 30884 5.2 15.9
228 jack 618 23864 37253 11.6 55.6
BiSort 123 5157 6615 1.2 2.9
Em3d 142 5519 7497 0.9 3.1
Health 141 5803 7561 0.9 3.2
MST 139 5228 6874 1.2 3.0
Perimeter 144 5401 6904 1.2 2.7
Power 135 6039 7928 1.0 3.2
TreeAdd 112 4814 6240 0.8 2.8
Voronoi 274 8072 10969 1.8 4.3
raytrace 498 14116 20875 4.2 23.0
JLex 482 22306 31354 4.0 12.3
JavaCUP 769 27977 41308 5.8 32.0

Table

2: Analyzed Code Size and Analysis Time
Application Allocation Unitary sites Exceptions Non-exceptions StringBuers
sites count % total unitary
total unitary
total unitary
200 check 407 326 80% 273 92% 134 57% 44 97%
compress 489 155 32% 390 28% 99 44% 38 97%
jess 1823 919 50% 1130 58% 693 38% 233 84%
222 mpegaudio 825 390 47% 625 55% 200 24% 43 97%
228 jack 910 479 53% 612 54% 298 50% 135 99%
BiSort 234 198 85% 177 97% 57 47% 17 94%
Em3d 276 235 85% 206 98% 70 50% 20 95%
Health 276 227 82% 202 97% 74 42% 17 94%
MST 257 216 85% 194 97% 63 44%
Perimeter
Power 262 213 81% 192 97% 70 39% 15 93%
TreeAdd 227 190 84% 170 96% 57 46% 15 93%
Voronoi 448 387 86% 349 98% 99 44% 28 96%
raytrace 753 318 42% 525 44% 228 39% 43 95%
JLex 971 812 84% 645 99% 326 54% 72 86%
Total 14065 8396 60% 9660 68% 4405 41% 1293 92%

Table

3: Unitary Site Analysis Results
Preallocated memory Size
Application size (bytes) reduction
normal sharing %
200 check 5516 196 96%
compress 2676 144 95%
jess 17000 840 96%
222 mpegaudio 6452 104 98%
228 jack 8344 224 97%
BH 4604 224 95%
BiSort 3252 96 98%
Em3d 3860 200 95%
Health 3716 96 97%
MST 3532 96 97%
Perimeter
Power 3540 196 94%
TreeAdd 3120 92 98%
raytrace 5656 644 89%
JLex 13996 1676 88%
JavaCUP 20540 1180 94%
Total 143088 6984 95%

Table

4: Preallocated Memory Size
The graph coloring algorithm nds an approximation of the
smallest number of colors such that no two incompatible
allocation sites have the same color. For each color, we pre-allocate
a memory area whose size is the maximum size of
the classes allocated at allocation sites with that color. Our
implementation uses the DSATUR graph coloring heuristic
[10]. It is important to notice that the DSATUR heuristic
minimizes the numbers of colors, not the nal total size
of the preallocated memory. However, this does not appear
to have a signicant negative eect on our results: as the
numbers from Table 4 show, we are able to reduce the preallocated
memory size by at least 88% in all cases; the average
reduction is 95%.
Theoretically, the preallocation optimization may allocate
more memory than the original program: preallocating a
memory area for a set of compatible allocation sites reserves
that area for the entire lifetime of the program, even when
no object allocated at the attached set of compatible sites
is reachable. An extreme case is represented by the memory
areas that we preallocate for allocation sites that the
program never executes. However, as the data from Table 4
indicate, in practice, the amount of preallocated memory for
each analyzed application is quite small.
We compiled each benchmark with the memory preallocation
optimization enabled. Each optimized executable n-
ished normally and produced the same result as the unoptimized
version. We executed the SPECjvm98 and the Olden
applications with their default workload. We ran JLex and
JavaCUP on the lexer and parser les from our compiler in-
frastructure. We instrumented the allocation sites to measure
how many objects were allocated by the program and
how many of these objects used the preallocated memory.
Application Total Preallocated objects
objects count %
200 check 725 238 33%
compress 941 108 11%
jess 7917932 3275 0%
222 mpegaudio 1189 7 1%
228 jack 6857090 409939 6%
BH 15115028 7257600 48%
BiSort 131128 15 0%
Em3d 16061 23 0%
Health 1196846 681872 57%
MST 2099256 1038 0%
Perimeter
Power 783439 12 0%
TreeAdd 1048620 13 0%
raytrace 6350085 4080258 64%
JLex 1419852 12926 1%
JavaCUP 100026 16517 17%

Table

5: Preallocated Objects

Table

5 presents the results of our measurements. For ve of
our benchmarks, at least one third of the objects resided in
the preallocated memory. There is no correlation between
the static number of unitary sites and the dynamic number
of objects allocated at those sites. This is explained by the
large dierence in the number of times dierent allocation
sites are executed. In general, application-specic details
tend to be the only factor in determining these dynamic
numbers. For example, in JLex, 95% of the objects are iterators
allocated at the same (non-unitary) allocation site;
213 javac and JavaCUP use many StringBuers that we can
preallocate; both 205 raytrace and BH use many temporary
objects to represent mathematical vectors, etc.
4. RELATED WORK
This paper presents, to our knowledge, the rst use of a
pointer analysis to enable static object preallocation. Other
researchers have used pointer and/or escape analyses to improve
the memory management of Java programs [14, 20, 7],
but these algorithms focus on allocating objects on the call
stack. Researchers have also developed algorithms that correlate
the lifetimes of objects with the lifetimes of invoked
methods, then use this information to allocate objects in
dierent regions [19]. The goal is to eliminate garbage collection
overhead by atomically deallocating all of the objects
allocated in a given region when the corresponding function
returns. Other researchers [17] require the programmer to
provide annotations (via a rich type systems) that specify
the region that each object is allocated into.
Bogda and Hoelzle [8] use pointer analysis to eliminate
unnecessary synchronizations in Java programs. In spite of
the dierent goals, their pointer analysis has many technical
similarities with our analysis. Both analyses avoid maintaining
precise information about objects that are placed \too
deep" into the heap. Bogda and Hoelzle's analysis is more
precise in that it can stack allocate objects reachable from a
single level of heap references, while our analysis does not attempt
to maintain precise points-to information for objects
reachable from the heap. On the other hand, our analysis
is more precise in that it computes live ranges of objects
and treats exceptions with more precision. In particular, we
found that our predicated analysis of type switches (which
takes the type of the referenced object into account) was
necessary to give our analysis enough precision to statically
preallocate exception objects.
Our analysis has more aggressive aims than escape anal-
ysis. Escape analysis is typically used to infer that the life-times
of all objects allocated at a specic allocation site are
contained within the lifetime of either the method that allocates
them or one of the methods that (transitively) invokes
the allocating method. The compiler can transform such an
allocation site to allocate the object from the method stack
frame instead of the heap. Notice that the analysis does not
provide any bound on the number of objects allocated at
that allocation site: in the presence of recursion or loops,
there may be an arbitrary number of live objects from a single
allocation site (and an arbitrary number of these objects
allocated on the call stack). In contrast, our analysis identify
allocation sites that have the property that at most one
object is live at any given time.
In addition, the stack allocation transformation may require
the compiler to lift the corresponding object allocation
site out of the method that originally contained it to one of
the (transitive) callers of this original allocating method [20].
The object would then be passed by reference down the call
stack, incurring runtime overhead. 12 The static preallocation
optimization enabled by our analysis does not suer
from this drawback. The compiler transforms the original
allocation site to simply acquire a pointer to the statically
allocated memory; there is no need to move the allocation
site into the callers of the original allocating method.
Our combined liveness and incompatibility analysis and
use of graph coloring to minimize the amount of memory required
to store objects allocated at unitary allocation sites is
similar in spirit to register allocation algorithms [6, Chapter
11]. However, register allocation algorithms are concerned
only with the liveness of the local variables, which can be
computed by a simple intraprocedural analysis. We found
that obtaining useful liveness results for dynamically allocated
objects is signicantly more di-cult. In particular,
we found that we had to use a predicated analysis and track
the
ow of objects across procedure boundaries to identify
signicant amounts of unitary sites.
5. CONCLUSIONS
We have presented an analysis designed to simplify the
computation of an accurate upper bound on the amount
of memory required to execute a program. This analysis
statically preallocates memory to store objects allocated
at unitary allocation sites and enables objects allocated at
compatible unitary allocation sites to share the same pre-allocated
memory. Our experimental results show that, for
our set of Java benchmark programs, 60% of the allocation
sites are unitary and can be statically preallocated. More-
over, allowing compatible unitary allocation sites to share
semantically equivalent alternative is to perform method inlining.
However, inlining introduces its own set of overheads.
the same preallocated memory leads to a 95% reduction in
the amount of memory required for these sites. Based on
this set of results, we believe our analysis can automatically
and eectively eliminate the need to consider many object
allocation sites when computing an accurate upper bound
on the amount of memory required to execute the program.
We have also used the analysis to optimize the memory managment

6.

ACKNOWLEDGEMENTS

We would like to thank Wes Beebee and Scott C. Ananian
for their useful advice on implementing the preallocation
optimization in the MIT Flex compiler system [3], and Viktor
Kuncak for proofreading early drafts of the paper. We
also want to thank the anonymous referees for their valuable
comments.
7.



--R

The cartesian product algorithm.

MIT FLEX compiler infrastructure for Java.
Static single information form.
Program Analysis and Specialization for the C Programming Language.
Modern Compiler Implementation in Java.
Escape analysis for object oriented languages.
Removing unnecessary synchronization in Java.
The Real-Time Speci cation for Java
Daniel Br
Data ow analysis for software prefetching linked data structures in Java.
Software caching and computation migration in Olden.
Analysis of pointers and structures.


Statically determining memory consumption of real-time Java threads


A region inference algorithm.
Compositional pointer and escape analysis for Java programs.
--TR
Compilers: principles, techniques, and tools
Analysis of pointers and structures
Efficiently computing static single assignment form and the control dependence graph
Software caching and computation migration in Olden
Points-to analysis in almost linear time
Modern compiler implementation in Java
A region inference algorithm
Escape analysis for Java
Escape analysis for object-oriented languages
Removing unnecessary synchronization in Java
Compositional pointer and escape analysis for Java programs
New methods to color the vertices of a graph
Region-based memory management in cyclone
Data Flow Analysis for Software Prefetching Linked Data Structures in Java
The Cartesian Product Algorithm

--CTR
Oukseh Lee , Kwangkeun Yi, Experiments on the effectiveness of an automatic insertion of memory reuses into ML-like programs, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
Oukseh Lee , Hongseok Yang , Kwangkeun Yi, Static insertion of safe and effective memory reuse commands into ML-like programs, Science of Computer Programming, v.58 n.1-2, p.141-178, October 2005
Samuel Z. Guyer , Kathryn S. McKinley , Daniel Frampton, Free-Me: a static analysis for automatic individual object reclamation, ACM SIGPLAN Notices, v.41 n.6, June 2006
Darko Marinov , Robert O'Callahan, Object equality profiling, ACM SIGPLAN Notices, v.38 n.11, November
Chandrasekhar Boyapati , Alexandru Salcianu , William Beebee, Jr. , Martin Rinard, Ownership types for safe region-based memory management in real-time Java, ACM SIGPLAN Notices, v.38 n.5, May
interprocedural analysis;memory preallocation;static analysis