Which pointer analysis should I use?.
During the past two decades many different pointer analysis algorithms have been published.  Although some descriptions include measurements of the effectiveness of the algorithm, qualitative comparisons among algorithms are difficult because of varying infrastructure, benchmarks, and performance metrics.  Without such comparisons it is not only difficult for an implementor to determine which pointer analysis is appropriate for their application, but also for a researcher to know which algorithms should be used as a basis for future advances.This paper describes an  empirical comparison of the effectiveness of five pointer analysis algorithms on C programs.  The algorithms vary in their use of control flow information (flow-sensitivity) and alias data structure, resulting in worst-case complexity from linear to polynomial.  The effectiveness of the analyses is quantified in terms of compile-time precision and efficiency.  In addition to measuring the direct effects of pointer analysis, precision is also reported by determining how the information computed by the five pointer analyses affects typical client analyses of pointer information: Mod/Ref analysis, live variable analysis and dead assignment identification, reaching definitions analysis, dependence analysis, and conditional constant propagation and unreachable code identification.  Efficiency is reported by measuring analysis time and memory consumption of the pointer analyses and their clients.
INTRODUCTION
Programs written in languages with pointers can be troublesome
to analyze because the memory location accessed
through a pointer is not known by inspecting the statement.
To effectively analyze such languages, knowledge of pointer
behavior is required. Without such knowledge, conserva-
This copy is posted by permission of ACM and may not be redis-
tributed. The official citation of this work is Hind, M., and Pioli, A.
2000. Which Pointer Analysis Should I Use? ACM SIGSOFT International
Symposium on Software Testing and Analysis
August 22-25, 2000.
Copyright 2000 ACM 1-58113-266-2/00/008.$5.00
tive assumptions about memory locations accessed through
a pointer must be made. These assumptions can adversely
affect the precision and efficiency of any analysis that requires
this information, such as a program understanding
system, an optimizing compiler, or a testing tool.
A pointer analysis is a compile-time analysis that attempts
to determine the possible values of a pointer. As such an
analysis is, in general, undecidable [16, 28], many approximation
algorithms have been developed that provide a trade-off
between the efficiency of the analysis and the precision
of the computed solution. The worst-case time complexities
of these analyses range from linear to exponential. Because
such worst-case complexities are often not a true indication
of analysis time, many researchers provide empirical results
of their algorithms. However, comparisons among results
from different researchers can be difficult because of differing
program representations, benchmark suites, and preci-
sion/efficiency metrics. In this work, we describe a comprehensive
study of five widely used pointer analysis algorithms
that holds these factors constant, thereby focusing more on
the efficacy of the algorithms and less on the manner in
which the results were obtained.
The main contributions of this paper are the following:
ffl empirical results that measure the precision and efficiency
of five pointer alias analysis algorithms with
varying degrees of flow-sensitivity and alias data struc-
tures: Address-taken, Steensgaard [34], Andersen [1],
Burke et al. [4, 12], Choi et al. [5, 12];
ffl empirical data on how the pointer analyses solutions
affect the precision and efficiency of the following client
analyses: Mod/Ref, live variable analysis and dead
assignment identification, reaching definition analysis,
dependence analysis, and interprocedural conditional
constant propagation and unreachable code identification

The results show (1) Steensgaard's analysis is significantly
more precise than the Address-taken analysis in terms of direct
precision and client precision, (2) Andersen's and Burke
et al.'s analyses provide the same level of precision and a
modest increase in precision over Steensgaard's analysis, (3)
the flow-sensitive analysis of Choi et al. offers only a minimal
increase in precision over the analyses of Andersen and
Burke et al. using a direct metric and little or no precision
improvement in client analyses, and (4) increasing the precision
of pointer information reduces the client analyses' in-
put, resulting in significant improvement in their efficiency.
The remainder of this paper is organized as follows. Section
describes background for this work and describes how
it differs from similar studies. Section 3 provides an overview
of the five pointer algorithms. Section 4 summarizes the
client analyses. Section 5 describes the empirical study and
discusses the results. Section 6 describes related work and
Section 7 summarizes the conclusions.
2. BACKGROUND
A pointer alias analysis attempts to determine when two
pointer expressions refer to the same storage location. For
example, if p and q both point to the same storage location,
we say \Lambdap and \Lambdaq are aliases, written as h\Lambdap; \Lambdaq i. A points-to
analysis attempts to determine what storage location a
pointer can point to. This information can then be used to
determine the aliases in the program. This works uses the
compact representation [5, 12] of alias information, which
shares the property of the points-to representation [8], in
that it captures the "edge" characteristic of alias relations. 1
For example, if variable a points to b, and b points to c, the
compact representation records only the following alias set:
cig, from which it can be inferred that h    a; ci
and h    a; \Lambdabi are also aliases. The cost and time when such
information is inferred can affect the precision and efficiency
of the analysis [22, 12, 20].
Interprocedural data-flow analysis can be classified as flow-sensitive
or flow-insensitive, depending on whether control-flow
information of a procedure is used during the analysis
[23]. By not considering control flow information, and
therefore computing a conservative summary, a flow-insensitive
analysis can be more efficient, but less precise than a
flow-sensitive analysis. In addition to flow-sensitivity, there
are several other factors that affect cost/precision trade-offs
including
Context-sensitivity: Is calling context considered when
analyzing a function?
Heap modeling: Are objects named by allocation site or
is a more sophisticated shape analysis performed?
Struct modeling: Are components distinguished or collapsed
into one object?
Alias representation: Is an explicit alias representation
or a points-to/compact representation used?
This work holds these factors constant, choosing the most
popular and efficient alternatives in each case, so that the
results only vary the usage of flow-sensitivity. In particular,
all analyses are context-insensitive, name heap objects based
on their allocation site, collapse aggregate components, and
use the compact/points-to representation.
This work differs from previous studies [33, 35, 7, 21] in the
following ways:
1 The minor difference between the compact and points-to
representations [12] is not relevant to this work.
ffl The breadth of pointer algorithms studied; in the only
two studies [35, 21] that also include a flow-sensitive
analysis, the analysis they study [18] also benefits from
being context sensitive and uses a different alias representation
(an explicit one) than the (points-to) flow-insensitive
analyses it is compared with.
ffl The number of client analyses reported; this work is
the first to report how reaching definitions, flow de-
pendences, and interprocedural constant propagation
are affected by the quality of pointer analysis.
ffl The reporting of memory usage, which is an important
aspect in evaluating the scalability of interprocedural
data-flow analyses.
3. POINTER ANALYSES
The algorithms we consider, listed in order of increasing
precision, are
Address-taken: a flow-insensitive algorithm often used in
production compilers that records all variables whose
addresses have been assigned to another variable. This
set includes all heap objects and actual parameters
whose addresses are stored in the corresponding for-
mal. This analysis is efficient because it is linear in
the size of the program and uses a single solution set,
but can be very imprecise.
Steensgaard [34]: a flow-insensitive algorithm that computes
one solution set for the entire program and employs
a fast union-find [36] data structure to represent
all alias relations. This results in an almost linear time
algorithm that makes one pass over the program. Similar
algorithms are discussed in [42, 24, 2].
Andersen [1]: an iterative implementation of Andersen's
context-insensitive flow-insensitive algorithm, which was
originally described using constraint-solving [1]. Although
it also uses one solution set for the entire pro-
gram, it can be more precise than Steensgaard's algorithm
because it does not perform the merging required
by the union-find data structure. However, it
does require a fixed-point computation over all pointer-
related statements that do not produce constant alias
relations.
Burke et al. [4, 12]: a flow-insensitive algorithm that also
iterates over all pointer-related statements in the pro-
gram. It differs from Andersen's analysis in that it
computes an alias solution for each procedure, requiring
iteration within each function in addition to iteration
over the functions. A worklist is used in the latter
case to improve efficiency. Distinguishing alias sets
for each function allows precision-improving enhancements
such as using precomputed kill information [4,
et al.'s analysis can be more precise than
Andersen's analysis because it can filter alias information
based on scoping, i.e., formals and locals from
provably nonactive functions are not considered. It
This particular enhancement never improved precision over
the Burke et al.'s analysis studied in this paper [13]. Thus,
the enhanced version of Burke et al.'s analysis that uses
precomputed kill information is not included in this study.
void main() f
S5:
void f() f
void g(T   fp) f
S9: if (.)

Figure

1: Example program
may be less efficient because it computes a solution
set for each function, rather than one for the whole
program.
Choi et al. [5, 12]: a flow-sensitive algorithm that computes
a solution set for every program point. It associates
alias sets with each CFG node in the program
and uses worklists for efficiency [13].
All analyses incorporate (optimistic) function pointer analysis
during the alias analysis by resolving indirect call sites
as the analysis proceeds [8, 4].
In theory, each subsequent analysis is more precise (and
costly) than its predecessors. This paper will help quantify
not only these characteristics, but also how client analyses
are affected by the precision of the pointer analyses.
Consider the program in Figure 1, where main calls f and
g, and f also calls g. The Address-taken analysis computes
only one set of objects that it assumes all pointers may point
to: fheapS1 , heapS4 , heapS6 , heapS8 , local, p, qg, all of
which will appear to be referenced at S5.
Steensgaard's analysis unions two objects that are pointed-to
by the same pointer into one object. This leads to the
unioning of the points-to sets of these formerly distinct ob-
jects. This unioning removes the necessity of iteration from
the algorithm. In the example, the formal parameter of g,
may point to either p or q, resulting in p and q being
unioned into one object. Thus, it appears that they both can
point to the heap objects that either can point to: heapS1 ,
local. At the dereference of S5, these
four objects are reported aliased to \Lambdap.
Andersen's analysis also keeps one set of aliases that can
hold anywhere in the program, but it does not merge objects
that have a common pointer point to them. This leads to
local being reported as aliased to \Lambdap.
Burke et al.'s analysis associates one set with every function,
which conservatively represents what may hold at any CFG
node in the function, without considering control flow within
the function. This distinction allows the removal of objects
that are no longer active, such as local in functions main
and f. This leads to heapS1 and heapS4 being aliased to \Lambdap
at S5.
Choi et al.'s analysis associates an alias set before (Inn)
and after (Outn ) every CFG node, n. For example, OutS1
because \Lambdap and heapS1 refer to the same
storage after S1. Choi et al.'s analysis will compute
fh\Lambdap; heapS4ig, which is the precise solution for this simple
example.
This example illustrates the theoretical precision/efficiency
levels of the five analyses we study, from Address-taken
(least precise) to Choi et al.'s (most precise). The Address-
taken analysis is our most efficient analysis because it is
linear and uses only one set. Steensgaard's analysis also
uses one set and is almost linear. The other three analyses
require iteration, but differ in the amount of information
stored from one alias set per program (Andersen), one set
per function (Burke et al.), and two per CFG Node (Choi
et al. 3
The analyses have been implemented in the NPIC system,
an experimental program analysis system written in C++.
The system uses multiple and virtual inheritance to provide
an extensible framework for data-flow analyses [14, 26]. A
prototype version of the IBM VisualAge C++ compiler [15]
is used as the front end. The analyzed program is represented
as a program call (multi-) graph (PCG), in which a
node corresponds to a function, and a directed edge represents
a call to the target function. 4 Each function body is
represented by a control flow graph (CFG), where each node
roughly corresponds to a statement. This graph is used to
build a simplified sparse evaluation graph (SEG) [6], which
is used by Choi et al.'s analysis in a manner similar to Wilson
[39]. As no CFG is available for library functions, a call
to a library function is modeled based on the function's semantics
with respect to pointer analysis. This hand-coded
modeling provides the benefits of context-sensitive analysis
of such calls. Library calls that cannot affect the value
of a pointer are treated as the identity transfer function
for pointer analysis. The implementation also assumes that
pointer values will only exist in pointer variables, and that
pointer arithmetic does not result in the pointer outside of
an array. All string literals are modeled as one object. The
implementation handles setjmp/longjmp in a manner similar
to Wilson [39]; all calls to setjmp are recorded and used
to determine the possible effects of a call to longjmp.
To model the values passed as argc and argv to the main
function, a dummy main function was added, which called
the benchmark's main function, simulating the effects of
3 We have found that performing Choi et al.'s analysis using
a SEG (sparse evaluation graph [6]) instead of a CFG
reduces the number of alias sets by an average of over 73%
and reduces analysis time by an average of 280% [13].
Indirect calls can result in several potential target functions

argc and argv. This function also initialized the iob array,
used for standard I/O. The added function is similar to the
one added by Ruf [29, 30] and Landi et al. [19, 17]. Explicit
and implicit initializations of global variables are automatically
modeled as assignment statements in the dummy main
function. Array initializations are expanded into an assignment
for each array component.
4. CLIENT ANALYSES
This section summarizes the client analyses used in this
study.
4.1 Mod/Ref Analysis
Mod/Ref analysis [20] determines what objects may be mod-
ified/referenced at each CFG node. This information is subsequently
used by other analyses, such as reaching definitions
and live variable analysis. This information is computed
by first visiting each CFG node and computing what
objects are modified or referenced by the node. Pointer
dereferences generate a query of the alias information to
determine the objects modified. These results (Mod and
Ref sets) are summarized for each function and used at call
sites to the function. A call site's Mod/Ref set does not
include a local of a function that cannot be on the activation
stack because its lifetime is not active. The actual
parameters at each call site are assumed to be referenced
because their value is assigned to the corresponding formal
parameter (pass-by-value semantics). The Mod/Ref analysis
makes the simplifying assumption that libraries do not
modify or reference locations indirectly through a pointer
parameter. Fixed-point iteration is employed when the program
has PCG cycles.
4.2 Live Variable Analysis
Live variable analysis [25] determines what objects may be
referenced after a program point without an intervening killing
definition. This information is useful for register allo-
cation, detecting uninitialized variables, and finding dead
assignments. The implementation, a backward analysis, directly
uses the Mod/Ref information. It associates two sets
of live variables with each CFG node representing what is
live before and after execution of the node. Sharing of such
sets is performed when a CFG node has only one successor,
or when the node acts as an identify function, i.e., it has an
empty Mod and Ref set.
All named objects in the Ref set of a CFG node become live
before that node. A named object is killed at a CFG node if
it is definitely assigned (i.e., it is the only element in the Mod
set of a noncall node) and represents one runtime object,
i.e., it is not an aggregate, a heap object, or a local/formal
of a recursive function. The implementation processes each
function once, employing a priority-based worklist of CFG
nodes for each function. It is optimistic; no named objects
are considered live initially, except at the exit node where all
nonlocals that are modified in the function are considered
to be live.
4.3 Reaching Definitions Analysis
Reaching definitions analysis [25] determines what definitions
of named objects may reach (in an execution sense) a
program point. This information is useful in computing data
dependences among statements, an important step for program
slicing [37] and code motion. The implementation, a
forward analysis, uses Mod/Ref information and associates
two sets of reaching definitions with each CFG node. Set
sharing is performed as in live variable analysis.
All named objects in the Mod set of a CFG node result in
new definitions being generated at that node. Definitions
are killed as in live variable analysis. Each function is processed
once, using a priority-based worklist of CFG nodes for
each function. The analysis is optimistic; no definitions are
initially considered reaching any point, except for dummy
definitions created at the entry node of a function for each
parameter or nonlocal that is referenced in the function.
4.4 Interprocedural Constant Propagation
The constant propagation client [26] is an optimistic interprocedural
algorithm inspired by Wegman and Zadeck's
Conditional Constant algorithm [38]. The algorithm tracks
values of variables interprocedurally throughout the program
and uses this information to simultaneously evaluate
conditional branches where possible, thereby determining
if a conditional branch will always evaluate to one value.
In addition to potentially removing unexecutable code, this
analysis can simplify computations and provide useful information
for cloning algorithms.
Because this analysis was designed to be combined with Choi
et al.'s pointer analysis [26, 27], it uses pointer information
directly, rather than using the Mod/Ref sets as was done in
reaching definitions and live variable analysis. In this work,
the constant propagation analysis is simply run after the
pointer analysis is completed. Like Choi et al.'s analysis, the
constant propagation algorithm uses nested iteration and a
SEG. 5 The algorithm extends the traditional lattice of ?,
?, and constant to include Positive, Negative, and NonZero.
This can help when analyzing C programs that treat nonzero
values as true.
5. RESULTS
This study was performed on a 333MHz IBM RS/6000 PowerPC
604e with 512MB RAM and 817MB paging space, running
AIX 4.3. The analyses were compiled with IBM's xlC
compiler using the "-O3" option. For each benchmark the
following are reported for all pointer analyses and clients:
precision, analysis time, and the maximum memory usage.

Table

describes characteristics of the benchmark suite,
which contains 23 C programs provided by other researchers
[19, 8, 29, 31] and the SPEC benchmark suites. 6 LOC is
computed using wc on the source and header files. The
column marked "Fcts", the number of user-defined func-
tions, includes the dummy main function, created to simu-
5 However, the SEG benefits are not as dramatic; most CFG
nodes are "interesting" to constant propagation, and thus,
the efficiency is typically worse than Choi et al.'s analysis.
6 The large number of CFG nodes for 129.compress results
from the explicit creation of assignment statements for implicit
array initialization. Some programs had to be syntactically
modified to satisfy C++'s stricter type-checking
semantics. A few program names are different than those
reported in [29]. Namely, ks was referred to as part, and ft
as span [30]. Also, the SPEC CINT92 program 052.alvinn
was named backprop in Todd Austin's benchmark suite [3].

Table

1: Static Characteristics of Benchmark Suite.
Ptr-Asg
CFG Nodes
Name Source LOC Nodes Fcts Pct
allroots Landi 227 159 7 1.3%
01.qbsort McCat 325 170 8 24.1%
06.matx McCat 350 245 7 13.5%
15.trie McCat 358 167 13 23.4%
04.bisect McCat 463 175 9 9.7%
fixoutput PROLANGS 477 299 6 4.4%
17.bintr McCat 496 193 17 8.8%
anagram Austin 650 346
ks Austin 782 526 14 27.4%
05.eks McCat 1,202 677
08.main McCat 1,206 793 41 20.9%
09.vor McCat 1,406 857 52 28.6%
loader Landi 1,539 691
129.compress SPEC95 1,934 17,012 25 0.2%
football Landi 2,354 2,854 58 1.8%
compiler Landi 2,360 1,767 40 5.1%
assembler Landi 3,446 1,845 52 16.6%
simulator Landi 4,639 2,929 111 6.3%
flex PROLANGS 7,659 7,107 88 5.2%
late command-line argument passing. The column marked
"Ptr-Asg Nodes Pct" reports the percentage of CFG nodes
that are considered pointer-assignment nodes, i.e., the number
of assignment nodes where the left side variable involved
in the pointer expression is declared to be a pointer.
5.1 Pointer Analysis Precision
The most direct way to measure the precision of a pointer
analysis is to record the number of objects aliased to a
pointer expression appearing in the program. Using this
metric, Andersen's and Burke et al.'s analyses provide the
same level of precision for all benchmarks, suggesting that
alias relations involving formals or locals from provably non-active
functions do not occur in this benchmark suite. Because
all client analyses use the alias solution computed by
these analysis as their input, there is, likewise, no precision
difference in these clients. For this reason, we group these
two analysis together in the precision data. The efficiency
results of Section 5.6 distinguish these analyses.
A pointer expression with multiple dereferences, such as
\Lambdap, is counted as multiple dereference expressions, one
for each dereference. The intermediate dereferences (\Lambdap and
are counted as reads. The last dereference (    \Lambdap)
is counted as a read or write depending on the context
of the expression. Statements such as (\Lambdap)++ and \Lambdap +=
increment are treated as both a read and a write of \Lambdap. A
pointer is considered to be dereferenced if the variable is declared
as a pointer or an array formal parameter, and one
or more of the " ", "-?", or "[ ]" operators are used with
that variable. Formal parameter arrays are included because
their corresponding actual parameter(s) could be a pointer.
We do not count the use of the "[ ]" operator on arrays that
are not formal parameters because the resulting "pointer"
(the array name) is constant, and therefore, counting it may
skew results.
The left half of Table 2 reports the average size of the Mod
and Ref sets for expressions containing a pointer dereference
for each benchmark and the average of all benchmarks. 7
This table, and the rest in this paper, use "-" to signify
a value that is the same as in the previous column. For
example, the Ptr-Mod for allroots is the same for Choi et
al.'s analysis and Andersen/Burke et al.'s analyses.
The results show
1. a substantial difference between the Address-taken analysis
and Steensgaard's analysis: (i) an average of 30.26
vs. 4.03 and an improvement in all benchmarks that
assigned through a pointer for Ptr-Mod, and (ii) an
average of 30.70 vs. 4.87 and an improvement in all
benchmarks for Ptr-Ref;
2. a measurable difference between Steensgaard's analysis
and Andersen/Burke et al.'s analyses: (i) an average of
4.03 vs. 2.06 and an improvement in 15 of the 22 benchmarks
that assign through a pointer for Ptr-Mod, (ii)
and an average 4.87 vs. 2.35 and an improvement in
13 of the 23 benchmarks for Ptr-Ref;
3. little difference between Andersen/Burke et al.'s analyses
and Choi et al.'s analysis: (i) an average of 2.06
vs. 2.02 and an improvement in 5 of the 22 benchmarks
that assign through a pointer for Ptr-Mod, and
(ii) 2.35 vs. 2.29 and an improvement in 5 of the 23
benchmarks for Ptr-Ref.
In summary, varying degrees of increased precision can be
gained by using a more precise analysis. However, as more
precise algorithms are used, the improvement diminishes.
5.2 Mod/Ref Precision
The right half of Table 2 reports the average Mod/Ref set
size for all CFG nodes. This captures how the pointer analysis
affects Mod/Ref analysis, which serves as input to many
other analyses. The results show
1. a substantial difference between the Address-taken analysis
and Steensgaard's analysis: (i) an average of 2.50
vs. 1.04 and an improvement in 22 of 23 benchmarks
for Mod, and (ii) 4.48 vs. 1.75 and an improvement in
all 23 benchmarks for Ref;
2. a measurable difference between Steensgaard's analysis
and Andersen/Burke et al.'s analyses: (i) an average
of 1.04 vs.87 and an improvement in 13 of 23
benchmarks for Mod, and (ii) 1.75 vs. 1.54 and an improvement
in 11 of 23 benchmarks for Ref;
3. little difference between Andersen/Burke et al.'s analyses
and Choi et al.'s analysis: (i) an average of .871
vs.867 and an improvement in 3 of 23 benchmarks for
both Mod; and (ii) an average of 1.540 vs. 1.536 and
an improvement in 4 of 23 benchmarks for Ref.
7 The modeling of potentially many runtime objects with one
representative object may seem more precise when compared
to a model that uses more names [29, 20]. For example, if the
heap was modeled as one object, all heap-directed pointers
would be "resolved" to one object in Table 2.

Table

2: Mod and Ref at pointer dereferences and all CFG nodes. No assignments through a pointer occur
in compiler.
et al.
Ptr Mod Ptr Ref Mod Ref
Name AT St A/B Ch AT St A/B Ch AT St A/B Ch AT St A/B Ch
allroots 3 2.00 1.00 - 3 2.00 1.38 - .88 .85 .83 - 1.77 1.58 1.52 -
04.bisect 14 1.15 - 14 1.00 - 2.57 .58 - 3.92 1.57 -
anagram
ks 17 1.90 1.86 1.62 17 1.79 - 1.74 1.70 .56 .55 .53 3.76 1.35 - 1.34
05.eks
09.vor 19 1.85 1.35 1.32 19 1.92 1.68 1.60 2.04 .63 .62 - 7.91 1.40 1.34 -
loader
129.compress 13 1.40 1.07 - 13 2.26 1.11 - 1.68 .80 .78 - 1.66 1.29 1.28 -
football
compiler
assembler 87 1.24 2.21 - 87 15.14 2.11 - 1.21 1.88 .87 - 15.07 4.09 1.47 -
simulator 87 3.16 2.05 - 87 3.95 1.86 - 6.82 .62 .57 - 8.21 1.21 1.06 -
flex 56 5.37 1.78 - 56 5.09 2.03 2.01 5.97 1.60 1.18 - 1.55 3.89 3.44 3.43
Average 30.26 4.03 2.06 2.02 30.70 4.87 2.35 2.29 2.50 1.04 0.871 0.867 4.48 1.75 1.540 1.536
Once again varying degrees of increased precision can be
gained by using a more precise analysis. However, the improvements
are not as dramatic as in the previous metric,
resulting in minimal precision gain from the flow-sensitive
analysis.
5.3 Live Variable Analysis and Dead Assignment
The first set of four columns in Table 3 reports precision
results for live variable analysis. For each benchmark we
list the average number of live variables at each CFG node
and the average of these averages. Live variable information
is used to find assignments to variables that are never used,
i.e., a dead assignments. The second set of four columns
gives the number of CFG nodes that are dead assignments.
The results show
1. a substantial difference between the Address-taken analysis
and Steensgaard's analysis for live variables -
on average 34.24 vs. 20.13 and an improvement in all
benchmarks - but no difference for finding dead assignments

2. a significant difference between Steensgaard's analysis
and Andersen/Burke et al.'s analyses for live variables
- an average of 20.13 vs. 18.36 and an improvement
in 13 of 23 benchmarks - but less of a difference for
finding dead assignments: an average of 1.91 vs. 1.96
and an improvement in only 1 of 23 benchmarks.
3. a small difference between Andersen/Burke et al.'s analyses
and Choi et al.'s analysis for live variables - an
average of 18.36 vs. 18.30 and an improvement in 3 of
benchmarks - but no difference for finding dead
assignments.
In summary, more precise pointer analyses improved the
precision of live variable analysis, but Choi et al.'s analysis
provided only minimal improvement. In contrast, dead
assignments identification was hardly affected by using different
pointer analyses.
5.4 Reaching Definitions andFlowDependences
The third set of four columns in Table 3 reports precision
results for reaching definitions analysis. For each benchmark
we list the average number of definitions that reach a
CFG node. The last set of four columns reports the average
number of unique flow dependences between two CFG nodes
per function. This metric captures reaching definitions that
are used at a CFG node, but counts dependences between
the same two nodes only once. Thus, if a set of variables
are potentially defined at one node and potentially used at
another node, only one dependence is counted because only
one such dependence is needed to prohibit code motion of
the two nodes or to be part of a slice.
The results show
1. a significant difference between the Address-taken analysis
and Steensgaard's analysis: (i) an average of 36.39
vs. 22.04 and an improvement in all 23 benchmarks for
reaching definitions, and (ii) an average of 52.51 vs.
44.24 and an improvement in 21 of 23 benchmarks for
flow dependences;
2. a measurable difference between Steensgaard's analysis
and Andersen/Burke et al.'s analyses: (i) an aver-
Table

3: Live variables, dead assignments, reaching definitions, and flow dependences.
Avg live variables at a Node Total dead assignments Avg reaching defs at a node Avg flow deps per function
Name AT St A/B Ch AT St A/B Ch AT St A/B Ch AT St A/B Ch
allroots
04.bisect
fixoutput
anagram
ks
05.eks
08.main
09.vor 20.33 6.96 6.85 - 2 - 23.68 7.35 7.26 - 34.92 26.52 26.20 -
loader 50.16 21.76
129.compress
compiler 43.73 43.70 -
assembler 82.24 37.36 20.75
simulator
Average 34.24 20.13 18.36
age of 22.04 vs. 20.21 and an improvement in 12 of 23
benchmarks for reaching definitions, and (ii) an average
of 44.24 vs. 43.84 and an improvement in 9 of 23
benchmarks for flow dependences;
3. a negligible difference between Andersen/Burke et al.'s
analyses and Choi et al.'s analysis for reaching definitions
- an average of 20.21 vs. 20.16 and an improvement
in 5 of 23 benchmarks - but no difference in
flow dependences for any benchmark.
In summary, each successively more precise analysis results
in an improvement of precision of reaching definitions, but
this improvement is diminished when flow dependences are
computed. In particular, there is no gain in flow dependences
precision using Choi et al.'s analysis over Ander-
sen/Burke et al.'s analyses and only minor improvements in
using Andersen/Burke et al.'s analyses over Steensgaard's
analysis.
Constant Propagation and Unexecutable
Code Detection
The constant propagation precision results are shown in Table
4. After the benchmark name the first four columns give
the number of complete expressions found to be constant.
This metric does not count subexpressions such as "b" in
=b+c;". The next four columns report the number of
unexecutable nodes found by the analysis. The results show
1. a significant difference between the Address-taken analysis
and Steensgaard's analysis: (i) an average of 7.8
vs. 10.6 constants found, but an improvement in only
3 of 22 benchmarks, and (ii) an average of 3.2 vs. 25.3
unexecutable nodes detected, but an improvement in
only 2 of 22 benchmarks;

Table

4: Constants and unexecutable CFG nodes
found.
gaard's, ``A/B''= Andersen/Burke et al.,
Choi et al. 099.go is not included because it exhausts
the 200MB heap size.
Constants Unexecutable Nodes
Name AT St A/B Ch AT St A/B Ch
allroots
04.bisect
ks
05.eks
08.main 36 -
loader
129.compress 34 - 5 -
compiler
assembler
simulator
flex
Average 7.8 10.6 10.7 - 3.2 25.3 25.4 -
2. a negligible difference between Steensgaard's analysis
and Andersen/Burke et al.'s analyses: (i) an average
of 10.6 vs. 10.7 constants found, an improvement in
only 1 of 22 benchmarks, and (ii) an average of 25.3
vs. 25.4 unexecutable nodes detected, an improvement
in only 1 of 22 benchmarks;
3. no difference between Andersen/Burke et al.'s analyses
and Choi et al.'s analysis in terms of constants found
and unexecutable nodes detected.
In summary, constant propagation and unexecutable code
detection does not seem to benefit much from increasing
precision beyond Steensgaard's analysis.
5.6 Efficiency
The efficiency of an algorithm can vary greatly depending on
the implementation [13] and therefore, care must be taken
when drawing conclusions regarding efficiency. For example,
F-ahndrich et al. [9] have demonstrated that the efficiency of
a constraint solving implementation of Andersen's algorithm
can be improved by orders of magnitude, without a loss of
precision, using partial online cycle detection and inductive
form.

Table

5 presents the analysis time in seconds of five individual
runs for each benchmark. The runs differ only in the
pointer analysis used. The times are given for the pointer
analysis, the total time for all client analyses, and the sum
of these two values. The time reported does not include
the time to build the PCG and CFGs, but does include any
analysis-specific preprocessing, such as the building of the
SEG from the CFG in Choi et al.'s analysis. The last line
gives the average for each column expressed as a ratio of the
Address-taken analysis for each category: pointer analysis,
clients, and total. For example, the average pointer analysis
time of Andersen's analysis is 29.60 times that of the
average pointer analysis time of the Address-taken analysis,
but the average of the client analyses using this information
is .84 times the average of the same client analyses using
the alias information from the Address-taken analysis. The
results show
1. the Address-taken and Steensgaard's analyses are very
fast; in all benchmarks these analyses completed in less
than a second;
2. the flow-insensitive analyses of Andersen and Burke
et al. are significantly slower (approximately
than the Address-taken and Steensgaard's analyses;
3. the flow-sensitive analysis of Choi et al.'s is on average
times slower than the Address-taken analysis and
about 2.5 times slower than the Andersen/Burke et
al.'s analyses;
4. the client analyses improved in efficiency as the pointer
information was made more precise because the input
size to these client analysis is smaller. On average this
reduction outweighed the initial costs of the pointer
analysis for Steensgaard, Andersen, and Burke et al.'s
analyses compared to the Address-taken analysis, and
brought the total time of the flow-sensitive analysis
of Choi et al.'s to within 9% of the total time of the
Address-taken analysis.

Table

6 reports the high-water mark of memory usage during
the various analyses as reported by the "ps v" command
under AIX 4.3. As before, the amounts are given for the
pointer analysis, the total memory for all client analyses,
and the sum of these two values. The last line gives the
average for each column expressed as a ratio of the Address-
taken analysis for each category: pointer analysis, clients,
and total. The results show
1. the memory consumption of the Address-taken and
Steensgaard's analyses are similar;
2. the memory consumption of the flow-sensitive analysis
of Choi et al. can be over 6 times larger than any of the
other pointer analysis (flex), and on average uses 12
times more memory than the Address-taken analysis;
3. once again, the memory usage of the client analyses
improves as the precision of pointer information
increases; on average the clients using the information
produced by Choi et al.'s analysis used the least
amount of memory, which was enough to overcome the
twelve-fold increase in pointer analysis memory consumption
over the Address-taken analysis.
6. RELATED WORK
Because of space constraints we limit this section to other
comparative studies of pointer analyses. A more thorough
treatment of related work can be found in [12, 20, 39].
Ruf [29] presents an empirical study of two algorithms: a
flow-sensitive algorithm similar to Choi et al. and a context-sensitive
version of the same algorithm. The context-sensitive
algorithm did not improve precision at pointer dereferences,
but Ruf cautioned that this may be a characteristic of the
benchmark suite.
Shapiro and Horwitz [32] present an empirical comparison
of four flow-insensitive algorithms: Address-taken, Steens-
gaard, Andersen, and a fourth algorithm [33] that can be parameterized
between Steensgaard's and Andersen's analysis.
The authors measure the precision of these analyses using
procedure-level Mod, live and truly live variables analyses,
and an interprocedural slicing algorithm. Their results suggest
that a more precise analysis will improve the precision
and efficiency of its clients, but leave as an open question
whether a flow-sensitive analysis will follow this pattern.
Landi et al. [20, 35] report precision results for the computation
of the interprocedural Mod problem using the flow-sensitive
context-sensitive analysis of Landi and Ryder [18].
They compare this analysis with an analysis [42] that is
similar to Steensgaard's analysis. They found that the more
precise analysis provided improved precision, but exhausted
memory on some programs that the less precise analysis was
able to process.
Emami et al. [8] report precision results for a flow-sensitive
context-sensitive algorithm. Ghiya and Hendren [11] empir-
Table

5: Analysis Time in Seconds
Pointer Analysis Clients Total
Name AT ST An Bu Ch AT ST An Bu Ch AT ST An Bu Ch
allroots
04.bisect
ks
05.eks
loader
129.compress
compiler
assembler
simulator
flex
Ratio to AT 1.00 0.90 29.60 32.92 79.49 1.00 0.81 0.84 0.71 0.69 1.00 0.82 0.98 0.87 1.09

Table

Memory Usage in MBs
Pointer Analysis Clients Total
Name AT ST An Bu Ch AT ST An Bu Ch AT ST An Bu Ch
allroots
04.bisect 1.01 0.61 2.25 0.00 0.50 0.89 0.91 0.55 0.66 0.60 1.90 1.52 2.80 0.66 1.10
fixoutput
anagram 0.50 0.28 1.62 0.04 0.25 1.15 1.10 0.91 0.96 1.37 1.65 1.38 2.53 1.00 1.62
ks 0.26 0.31 2.39 0.42 1.63 2.79 2.38 2.36 2.31 2.86 3.05 2.69 4.75 2.73 4.49
05.eks 0.00 0.10 2.04 0.18 0.75 2.13 1.86 1.69 1.72 1.66 2.13 1.96 3.73 1.90 2.41
08.main 0.19 0.00 3.39 0.76 2.72 2.66 1.89 1.47 1.43 1.42 2.85 1.89 4.86 2.19 4.14
loader
129.compress
compiler 0.61 1.22 4.20 1.05 2.19 14.60 15.03 14.11 13.80 13.72 15.21 16.25 18.31 14.85 15.91
assembler
simulator
Ratio to AT 1.00 1.15 8.52 3.15 12.19 1.00 0.81 0.77 0.71 0.70 1.00 0.82 0.89 0.74 0.87
ically demonstrate how a version of points-to [8] and connection
analyses [10] can improve traditional transformations,
array dependence testing, and program understanding.
Wilson and Lam [40, 39] present a context-sensitive algorithm
that avoids redundant analyses of functions for similar
calling contexts. The algorithm distinguishes structure
components and handles pointer arithmetic. Wilson [39]
compares various levels of context-sensitivity and describes
how dependence analysis uses the computed information to
parallelize loops in two SPEC benchmarks.
Diwan et al. [7] examine the effectiveness of three type-based
flow-insensitive analyses for a type-safe language (Modula-
3). The first two algorithms rely on type declarations. The
third considers assignments in a manner similar to Steens-
gaard's analysis, but retains declared type information. They
evaluate the effect of these algorithms on redundant load
elimination using statical, dynamic, and upper bound met-
rics. They conclude that for type-safe languages such as
Modula-3 or Java, a fast and simple type-based analysis
may be sufficient.
In an earlier paper [13], we describe an empirical comparison
of four context-insensitive pointer algorithms: three described
in this paper (Choi et al., Burke et al., Address-
taken) and a flow-insensitive algorithm that uses precomputed
kill information [4, 12]. No alias analysis clients are
studied. The paper also quantifies analysis-time speed-up of
various implementation techniques for Choi et al.'s analysis.
Yong et al. [41] present a tunable pointer-analysis framework
for handling structures in the presence of casting. They provide
experimental results from four instances of the frame-work
using a flow- and context-insensitive algorithm, which
appears to be similar to Andersen's algorithm. Their results
show that for this pointer algorithm distinguishing struct
components can improve precision where pointers are dereferenced
(the metric used in Section 5.1). They do not address
how this affects the precision of client analyses or if
similar results hold for other pointer analyses.
Liang and Harrold [21] describe a context-sensitive flow-insensitive
algorithm and empirically compare it to three
other algorithms: Steensgaard, Andersen, and Landi and
Ryder [18], using Ptr-Mod (Section 5.1), summary edges in
a system dependence graph, and average slice size as precision
metrics. They demonstrate performance and precision
mostly between Andersen's and Steensgaard's algorithms.
None of the implementations handles function pointers or
setjmp/longjmp.
7. CONCLUSIONS
This paper describes an empirical study of the precision and
efficiency of five pointer analyses and typical clients of the
alias information they compute. The major conclusions are
ffl Steensgaard's analysis is significantly more precise than
the Address-taken analysis without an appreciable increase
in compilation time or memory usage, and therefore
should always be preferred over the Address-taken
analysis.
ffl The flow-insensitive analysis of Andersen and Burke et
al. provide the same level of precision. Both analyses
offer a modest increase in precision over Steensgaard's
analysis. Although this improvement requires additional
pointer analysis time, it is typically offset by
decreasing the input size (the alias information) and
analysis time of subsequent analyses. There is not a
clear distinction in analysis time or memory usage between
the implementations of these analyses.
ffl The use of flow-sensitive pointer analysis (as described
in this paper) does not seem justified because it offers
only a minimum increase in precision over the analyses
of Andersen and Burke et al. using a direct metric
(such as ptr-mod/ref) and little or no precision improvement
in client analyses.
ffl The time and space efficiency of the client analyses
improved as the pointer analysis precision increased
because the increase in precision reduced the input to
these client analysis.
8.

ACKNOWLEDGMENTS

We thank Vivek Sarkar for his support of this work and
NPIC group members who have assisted with the implemen-
tation. We also thank Todd Austin, Bill Landi, and Laurie
Hendren for making their benchmarks available. We thank
Frank Tip, Laureen Treacy, and the anonymous referees for
comments on an earlier draft of this work. This work was
supported in part by the National Science Foundation under
grant CCR-9633010, by IBM Research, and by SUNY
at New Paltz Research and Creative Project Awards.
9.



--R

Program Analysis and Specialization for the C Programming Language.
Effective whole-program analysis in the pressence of pointers


Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects
Automatic construction of sparse data flow evaluation graphs.


Partial online cycle elimination in inclusion constraint graphs.
Connection analysis: A practical interprocedural heap analysis for C.
Putting pointer analysis to work.
Interprocedural pointer alias analysis.
Assessing the effects of flow-sensitivity on pointer alias analyses
Traveling through Dakota: Experiences with an object-oriented program analysis system
The architecture of Montana: An open and extensible programming environment with an incremental C
Undecidability of static analysis.
Personal communication
A safe approximate algorithm for interprocedural pointer aliasing.
Interprocedural modification side effect analysis with pointer aliasing.
A schema for interprocedural modification side-effect analysis with pointer aliasing
Efficient points-to analysis for whole-program analysis

Defining flow sensitivity in data flow problems.
Static Analysis for a Software Transformation Tool.
Advanced Compiler Design and Imlementation.
Conditional pointer aliasing and constant propagation.
Combining interprocedural pointer analysis and conditional constant propagation.
The undecidability of aliasing.

Personal communication

The effects of the precision of pointer analysis.
Fast and accurate flow-insensitive point-to analysis

Comparing flow and context sensitivity on the modifications-side-effects problem
Data structures and network flow algorithms.
A survey of program slicing techniques.
Constant propagation with conditional branches.
Efficient Context-Sensitive Pointer Analysis for C Programs
Efficient context-sensitive pointer analysis for C programs
Pointer analysis for programs with structures and casting.
Program decomposition for pointer aliasing: A step toward practical analyses.
--TR
Data structures and network algorithms
Automatic construction of sparse data flow evaluation graphs
Constant propagation with conditional branches
A safe approximate algorithm for interprocedural aliasing
Interprocedural modification side effect analysis with pointer aliasing
Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects
Undecidability of static analysis
Pointer-induced aliasing
Context-sensitive interprocedural points-to analysis in the presence of function pointers
The undecidability of aliasing
Efficient context-sensitive pointer analysis for C programs
Context-insensitive alias analysis reconsidered
Points-to analysis in almost linear time
Program decomposition for pointer aliasing
Connection analysis
Fast and accurate flow-insensitive points-to analysis
Putting pointer analysis to work
Comparing flow and context sensitivity on the modification-side-effects problem
Partial online cycle elimination in inclusion constraint graphs
Type-based alias analysis
Advanced compiler design and implementation
Static analysis for a software transformation tool
Effective whole-program analysis in the presence of pointers
The architecture of Montana
Pointer analysis for programs with structures and casting
Efficient points-to analysis for whole-program analysis
Interprocedural pointer alias analysis
Flow-Insensitive Interprocedural Alias Analysis in the Presence of Pointers
The Effects of the Presision of Pointer Analysis
Assessing the Effects of Flow-Sensitivity on Pointer Alias Analyses
Traveling Through Dakota
Efficient, context-sensitive pointer analysis for c programs

--CTR
Mana Taghdiri , Robert Seater , Daniel Jackson, Lightweight extraction of syntactic specifications, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA
Andreas Zeller, Isolating cause-effect chains from computer programs, ACM SIGSOFT Software Engineering Notes, v.27 n.6, November 2002
Ran Shaham , Elliot K. Kolodner , Mooly Sagiv, Heap profiling for space-efficient Java, ACM SIGPLAN Notices, v.36 n.5, p.104-113, May 2001
Andreas Zeller, Isolating cause-effect chains from computer programs, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA
Jens Krinke, Effects of context on program slicing, Journal of Systems and Software, v.79 n.9, p.1249-1260, September 2006
Ondrej Lhotk, Comparing call graphs, Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.37-42, June 13-14, 2007, San Diego, California, USA
Markus Mock , Manuvir Das , Craig Chambers , Susan J. Eggers, Dynamic points-to sets: a comparison with static analyses and potential applications in program understanding and optimization, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.66-72, June 2001, Snowbird, Utah, United States
Jamieson M. Cobleigh , Lori A. Clarke , Leon J. Osterweil, The right algorithm at the right time: comparing data flow analysis algorithms for finite state verification, Proceedings of the 23rd International Conference on Software Engineering, p.37-46, May 12-19, 2001, Toronto, Ontario, Canada
Haifeng He , John Trimble , Somu Perianayagam , Saumya Debray , Gregory Andrews, Code Compaction of an Operating System Kernel, Proceedings of the International Symposium on Code Generation and Optimization, p.283-298, March 11-14, 2007
Esther Salam , Mateo Valero, Dynamic memory interval test vs. interprocedural pointer analysis in multimedia applications, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.2, p.199-219, June 2005
Donglin Liang , Maikel Pennings , Mary Jean Harrold, Extending and evaluating flow-insenstitive and context-insensitive points-to analyses for Java, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.73-79, June 2001, Snowbird, Utah, United States
David J. Pearce , Paul H. J. Kelly , Chris Hankin, Efficient field-sensitive pointer analysis for C, Proceedings of the ACM-SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08, 2004, Washington DC, USA
Donglin Liang , Mary Jean Harrold, Equivalence analysis and its application in improving the efficiency of program slicing, ACM Transactions on Software Engineering and Methodology (TOSEM), v.11 n.3, p.347-383, July 2002
Thomas Eisenbarth , Rainer Koschke , Gunther Vogel, Static object trace extraction for programs with pointers, Journal of Systems and Software, v.77 n.3, p.263-284, September 2005
Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to and side-effect analyses for Java, ACM SIGSOFT Software Engineering Notes, v.27 n.4, July 2002
Brian Hackett , Alex Aiken, How is aliasing used in systems software?, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA
Bolei Guo , Matthew J. Bridges , Spyridon Triantafyllis , Guilherme Ottoni , Easwaran Raman , David I. August, Practical and Accurate Low-Level Pointer Analysis, Proceedings of the international symposium on Code generation and optimization, p.291-302, March 20-23, 2005
Jeff Da Silva , J. Gregory Steffan, A probabilistic pointer analysis for speculative optimizations, ACM SIGPLAN Notices, v.41 n.11, November 2006
Gregor Snelting , Frank Tip, Understanding class hierarchies using concept analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.540-582, May 2000
Charles N. Fischer, Interactive, scalable, declarative program analysis: from prototype to implementation, Proceedings of the 9th ACM SIGPLAN international symposium on Principles and practice of declarative programming, July 14-16, 2007, Wroclaw, Poland
Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to analysis for Java, ACM Transactions on Software Engineering and Methodology (TOSEM), v.14 n.1, p.1-41, January 2005
Jianwen Zhu , Silvian Calman, Symbolic pointer analysis revisited, ACM SIGPLAN Notices, v.39 n.6, May 2004
Markus Mock , Darren C. Atkinson , Craig Chambers , Susan J. Eggers, Program Slicing with Dynamic Points-To Sets, IEEE Transactions on Software Engineering, v.31 n.8, p.657-678, August 2005
Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
Martin Hirzel , Daniel Von Dincklage , Amer Diwan , Michael Hind, Fast online pointer analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.2, p.11-es, April 2007
Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States
David J. Pearce , Paul H. J. Kelly , Chris Hankin, Online Cycle Detection and Difference Propagation: Applications to Pointer Analysis, Software Quality Control, v.12 n.4, p.311-337, December 2004
Baowen Xu , Ju Qian , Xiaofang Zhang , Zhongqiang Wu , Lin Chen, A brief survey of program slicing, ACM SIGSOFT Software Engineering Notes, v.30 n.2, March 2005
interprocedural pointer analysis;data flow analysis