Batch Alias Analysis
Jyothi Vedurada

V. Krishna Nandivada

Dept. of CSE, IIT Madras
vjyothi@cse.iitm.ac.in

Dept. of CSE, IIT Madras
nvk@iitm.ac.in

Abstract—Many program-analysis based tools require precise
points-to/alias information only for some program variables. To
meet this requirement efficiently, there have been many works on
demand-driven analyses that perform only the work necessary
to compute the points-to or alias information on the requested
variables (queries). However, these demand-driven analyses canbe very expensive when applied on large systems where thenumber of queries can be significant. Such a blow-up in analysis
time is unacceptable in cases where scalability with real-time
constraints is crucial; for example, when program analysis tools
are plugged into an IDE (Integrated Development Environment).
In this paper, we propose schemes to improve the scalability ofdemand-driven analyses without compromising on precision.
Our work is based on novel ideas for eliminating irrelevant andredundant data-flow paths for the given queries. We introduce theidea of batch analysis, which can answer multiple given queries
in batch mode. Batch analysis suits the environments with stricttime constraints, where the queries come in batch. We present
a batch alias analysis framework that can be used to speed up
given demand-driven alias analysis. To show the effectiveness of
this framework, we use two demand-driven alias analyses (1) the
existing best performing demand-driven alias analysis tool for
race-detection clients and (2) an optimized version thereof thatavoids irrelevant computation. Our evaluations on a simulated
data-race client, and on a recent program-understanding tool,
show that batch analysis leads to significant performance gains,
along with minor gains in precision.

I. I NTRODUCTION
Points-to analysis is the underlying base analysis for manyother static analyses, for example, the analyses designed for
callgraph construction [1], bug detection [2]–[4], compiler
optimizations, program understanding [5] and so on. On
one hand, there have been several whole-program points-to
analyses over the last two decades [6]–[9] that compute theexhaustive solution and meet the requirements of clients thatneed points-to information for many parts of the code. On
the other hand, many demand-driven analyses [2], [10]–[16]have been proposed that compute only necessary results for a
fixed set of queries and meet the requirements of clients thatneed points-to information only for a few parts of the code.
Whole-program analyses are expensive because they are fully
exhaustive and compute the points-to information for the entire
input application. Many of the demand-driven analyses are
fully on-demand (work on each query independently) and may
not scale well to clients with a large number of queries [17],[18], because they recompute a lot of information acrossdifferent queries. However, an open question (similar to theone asked by Hind and Pioli [19]) which is of interest to thecommunity is: what is a suitable analysis for clients that fallin-between? That is, for the clients that: (1) do not require

the complete whole-program information but can trigger asignificant number of queries on large applications, (2) trigger
queries which are not fully on-demand (i.e., all the queries
can come in a batch), and (3) are performance critical, that is,should suit IDE kind of environments. There are many suchclients, for example, data-race detection analyses [4], [20],analyses for identifying refactoring opportunities [5], and soon, where the points-to or alias queries are available in a batch.
“Pointer Analyses should be designed to be appropriate in costand precision for specific groups of client problems.”–Barbara Ryder [8]The existing demand-driven analyses [2], [10]–[16], [21]answer one query at a time (fully on-demand) and none ofthem provide special treatment when the queries from a client
come in batch. Some of these works perform ad-hoc caching(or summarization) to avoid redundant computations acrossdifferent queries without exploiting the availability of queriesin advance and hence they suffer from storing unnecessary
information or from missing to store useful information acrossdifferent queries leading to performance losses. Su et al. [15]provide a parallel algorithm to process queries from suchclients independently, but still do not take full advantage of
queries arriving in batches. We are not aware of any work that
efficiently answers such batch alias queries.
To address this issue of efficient alias analysis where queries
come in batches, in this paper, we introduce the idea ofbatch analysis. It can efficiently serve clients with strict time
constraints by modeling a batch query (a group of demanddriven queries) as a single-source multiple-destination CFLreachability problem. To present our ideas on batch analysis,
we use two demand-driven alias analyses (1) the existing best
performing demand-driven alias analysis tool [2], and (2) an
optimized version thereof that avoids irrelevant computations
with respect to the input queries. The key step in batch analysis is identifying redundant computations across queries andcarefully forming batch queries such that these computations
are performed only once in a batch query. We believe that theinsights behind the batch analysis can be extended to otheranalyses such as points-to analysis, null-pointer analysis, etc.
Our Contributions.
• We design a batch alias analysis framework that can efficiently address clients where alias queries come in batch, byavoiding redundant computations within batch queries.
• We present techniques to optimize demand-driven analyses
by eliminating irrelevant analysis paths that can improve theperformance of the batch analysis further. We propose anovel type-information based approach to eliminate irrelevantanalysis paths when solving alias queries and thus improve theperformance and precision of demand-driven alias analyses.
• We present a detailed evaluation using a simulated datarace client and on a recent program-understanding tool [5].
We show that batch analysis leads to significant performancegains, along with minor precision gains, and the elimination ofirrelevant search paths improves performance and precision.
II. P RELIMINARIESIn this section, we first introduce some notations andterminology, and then we outline the CFL-reachability-based
demand-driven context-sensitive alias analysis proposed by
Yan et al. [2] (implementation available [23]) as it serves as
our baseline; hereafter, we refer to it as BASIC A NALYZER.
Alias Analysis. We use the notation Φ = alias?(a, b) torepresent an alias query between two variables a and b. To illustrate, Fig. 1 shows a modified code snippet from jfreechart1.0.14 [22] (a chart library). Classes BarRenderer and
LineRenderer extend the abstract class Renderer. Methods client1, client3 use LineRenderer and methods client2, client4 use BarRenderer. The method
apply in ChartTheme applies theme/style to a chart by various chart parameters like renderer. Note that ShadowPaint
controls the shadows drawn for the bars and hence is specific to BarRenderer. Suppose we are interested in finding whether the read of field ShadowPaint:enabled atLine 25 and the write of it at Line 22 maybe involved in adata race, the alias query is Φ = alias?(lsp25 , fsp22 ).
CFL-reachability. Context-free language (CFL) reachability
is an extension of graph reachability problem in which a
directed graph G with edges having labels from an alphabet Σand a context-free language L over Σ are considered. A path
p from a node n to n0 in G is called an L-path if the word
formed by concatenating the labels of edges in p, say w, isa member of L. Here, n0 is said to be L-reachable from n.
This is a popular mechanism [2], [11]–[13], [15], [16], [20],[24] to model field- and context-sensitivity.
Program Representation. Interprocedural symbolic pointsto graph (ISPG) [2], [20] forms the basis for the CFLreachability-based alias analysis. Fig. 2 shows the ISPG for
the code in Fig. 1. The ISPG is constructed in two steps: (1)an intraprocedural SPG is built locally for each method using
placeholders for the objects created outside the method. (2)The constructed intraprocedural SPGs are connected to form
the ISPG. An ISPG contains three kinds of nodes: (1) nodes for
local variables (shown using ellipses), (2) abstract allocation
nodes representing allocated objects o ∈ O (shown using
rectangular white boxes), and (3) placeholder nodes called as
symbolic nodes s ∈ S (shown using shaded boxes).
Edges in ISPG: (1) The new, copy and store statements
lead to edges similar to the ones realized in standard points-to
analysis. For example, for each store statement of the formfx.f = y, a points-to edge o1 −→ o2 is added if x points to
o1 and y points to o2, where o1 and o2 can be symbolic or
allocation nodes; (2) for each formal parameter f , an edgef → s is added, where symbolic node s represents the object

passed from outside; (3) for each field access v.f , an edgefv −→ s is added, where symbolic node s is used to represent
the object that v.f points to. (4) for each call site of the formv = a0 .m(a1 , ..., ai , ...): (i) an entry edge is added from any
allocation or symbolic node that ai points to in the caller, tothe symbolic node si that formal parameter fi points to in m;(ii) an exit edge is added from any allocation or symbolic nodethat a return variable points to in m to the symbolic node sthat was introduced as a placeholder of the return value in thecaller m. (iii) an edge v → s is added, where s (same as in(ii)) is the symbolic node representing the object returned fromm. For an edge with label t, t̄ represents the reverse edge.
BASIC A NALYZER. Alias query Φ to BASIC A NALYZER is
performed as an on-demand single-source single-target CFLreachability problem on ISPG. Edge labels in ISPG are fieldnames coming from field read/write operations, and entry andexit labels. A path between any two nodes n ∈ (O ∪ S) andn0 ∈ (O ∪ S) in ISPG has a string w formed by concatenatingthese edge labels. The memory alias relation between n and
n0 can be described using CFL memAlias as:
memAlias → f¯ memAlias f | memAlias memAlias| entry | entry | exit | exit | Thus, memAlias is capturing field-sensitivity by looking formatching field names (f ) in w. For example, In Fig. 1, there
is a memAlias-path between lsp25 and rsp13 with w: “spentry16 entry12 entry13 sp exit13 ”, and hence lsp25 andrsp13 may alias. Context-sensitivity is captured using thefollowing grammar that matches entry and exit labels.
C → (i C )i | CC | (i → entry(i) | exit(i))i → exit(i) | entry(i)Fig. 3 shows the demand-driven context-sensitive alias
analysis of BASIC A NALYZER. If Φ = alias?(a, b) is an alias
query on the local variables a and b, the algorithm takes (n1 ,n2 ) as the corresponding input query, where n1 and n2 are
the nodes that a and b point to respectively in the ISPG. We
call φ = (n1 , n2 ) as an effective query of Φ; since a andb can point to multiple allocation/symbolic nodes, an alias
query can have multiple effective queries. checkAliasing
checks for context-sensitive memAlias-path reachability fromn1 to n2 in the ISPG by performing a breadth-first traversal.
The procedure maintains two stacks (f ldStk and cxtStk) tosupport field sensitivity and context sensitivity. The function
processEdge processes each edge by updating f ldStk andcxtStk with the edge label when required and returns true
when it finds a context mismatch (⇒ the corresponding pathshould be ignored); detailed definition of this function is elided
for space. If n2 is reached from n1 and the f ldStk is empty,
it implies that variables a and b are aliases. The termination
check (Line 10) does not check for cxtStk to be empty as arealizable path may have unbalanced prefix and suffix edges.
Caching. Xu et al. [20] use a whole program pre-analysis tocache the reachability strings associated with all the reachable
nodes of each ISPG node to compute all-pairs memAlias-pathvoid client1(){ ...
client3(new LineRenderer());}
3 void client2(){ ...
4BarRenderer b = new BarRenderer();5b.setShadow(new ShadowPaint());
6
client4(b);}
7 void client3(LineRenderer lr){
8
ChartTheme theme = ...;
9theme.apply(lr); ...}
10 void client4(BarRenderer br){11
ChartTheme theme = ...;
12
theme.apply(br);13
rsp = br.getShadow();...}
1
2

14
15
16

17
18

abstract class ChartRenderer {void paint(){...} ...}//end

class BarRenderer extends ChartRenderer{
ShadowPaint sp;
21
void setShadow(ShadowPaint fsp){22
fsp.enabled=true; this.sp = fsp;}
23
void getShadow(){ return this.sp; }24
void paint(){ lsp = this.sp;
25
if(lsp.enabled){...}else{...}; }26 ...}//end
19
20

class ChartTheme {void apply(ChartRenderer cr){
cr.paint();} ...}//end

27
28

class LineRenderer extends ChartRenderer{
void paint(){ this...} ...}//end

29

class ShadowPaint{boolean enabled; ...}//end

Fig. 1: Running example. Code snippet from jfreechart [22], with minor modifications.
client1

client2

O2

O4

lr7

5

this22rsp13

S3

exit13sp

entry13

setShadow

S1

en
t

br10

S2

9

entry12

cr15

S4

ry

LineRenderer:paintthis28

S5

y 16
ntr

apply

e

Field points-to edge
entryi

Entry edge at call site i

S8

getShadow

S9

this23
BarRenderer:paint

entry

16

function checkAliasing(n1 ,n2 )WL ← {(n1, ∅, ∅)};
3
while WL 6= ∅ do4
remove (n, f ldStkn , cxtStkn ) from WL;
5(f ldStk, cxtStk) ← clone(f ldStkn , cxtStkn );6foreach edge e ∈ n.Edges do
7
ignoreP ath ← processEdge(edge,fldStk,cxtStk);8
if ignoreP ath 6= true then9m ← neighbour(e, n1 );10
if m = n2 ∧ f ldStk = ∅ then11
if cachingOn then Results.add((n1 , n2 ), true);
12
return true; // n2 and n1 are may-aliases
13
WL ← ∪{(m, f ldStk, cxtStk)};
1

fsp22

2

S10

client4

client3

S11

sp

entry

entry6entry2entry5O5

S6

sp

this24S7

lsp25

fField points-to edge
exiti Exit edge at call site i

14
15

Fig. 2: Symbolic Points-to Graph for the example in Fig. 1.
reachability information. Yan et al. [2] in their implementation [23] of BASIC A NALYZER, use a caching scheme (evolved
from that of Xu et al.) that caches during the demand driven
analysis (in contrast to whole program pre-analysis), andcaches only the results of effective queries (thus, has lower
memory overhead than the work of Xu et al.) We now briefly
discuss this caching scheme (termed CACHE) of Yan et al.
The code for caching gets executed upon setting an option
cachingOn. Here, for each input query (n1 , n2 ), (i) during
the analysis, upon visiting a node m with empty fldStk andcallStk (to respect field- and context-sensitivity), this scheme
uses the prior result of the query (m, n2 ) if available (shownin Fig. 4, Lines 3 and 4). (ii) in Fig. 3, before returning, theanswer for (n1 , n2 ) is stored (Lines 11 and 14).
III. O PPORTUNITIES FOR I MPROVEMENTOur goal is to improve the performance of alias analysis without compromising on precision. In this section, we
demonstrate two main opportunities for improving the performance of a demand-driven alias analysis, for example,
BASIC A NALYZER. We illustrate the same by using the example program in Fig. 1. Our identified opportunities can beclassified into two categories: redundant work (discussed in
Section III-A) and irrelevant work (discussed in Section III-B).

if cachingOn then Results.add((n1 , n2 ), false);
return false;

Fig. 3: Solving Alias Queries
if cachingOn ∧f ldStk = ∅ ∧ cxtStk = ∅ thenif effective query (m, n2 ) is in Results then // in “cache”
3
if Results.get((m, n2 )) is true then return true;4else continue;

1

2

Fig. 4: Enable caching: code to be added to Fig. 3 (before Line 13).
A. Redundant WorkTo see how BASIC A NALYZER performs redundant work,
let us consider the example code from Fig. 1. Suppose
we are interested in finding whether the read of field
ShadowPaint:enabled at Line 25 and the write of it
at Line 13 may involve in a data race and hence the alias
query becomes Φ1 = alias?(lsp25 , rsp13 ). Similarly, say,we are also interested to answer the alias query Φ2 =alias?(lsp25 , fsp22 ). The effective query of Φ1 is φ = (S7 , S3 )as lsp25 points to S7 and rsp13 points to S3 in the ISPG
as shown in Fig. 2. Similarly, the effective query of Φ2 is
φ2 = (S7 , S11 ). Paths π2 and π1 in Fig. 6 are the contextsensitive memAlias-paths for φ1 and φ2 respectively. Fig. 5
shows the two sub graphs of the ISPG in Fig. 2 containingedges of all the paths that are traversed by BASIC A NALYZER
for answering φ1 and φ2 respectively. The start node during

Φ1client1
O2

client2
O4

entry510

entry6
8 client4
S3
7
S1
S
2
entry
en
13
t
client35
4 ry9 entry
12
entry2
6

LineRenderer
3
S4:paintS5 entry 16

apply

2
entry
16

Φ2
setShadow
S10

exit13 11
S9
sp
9
S8

getShadow

BarRenderer:paint
S6

sp
1 S7

client1

client2

O2

O4

10
entry6
8 client4
S3
7
S1
S
2
entry
en
13
t
client35
4 ry9 entry
12
entry2
6

LineRenderer
3
S4:paintS5 entry 16

setShadowentry52entry

S10 sp12

S11

exit13 11
S9
sp
9
S8

getShadow

BarRenderer:paint
S6

16

apply

sp
1 S7

Fig. 5: Sub graphs traversed for answering Φ1 = alias?(lsp25 , rsp13 ) and Φ2 = alias?(lsp25 , fsp22 ).
both the traversals is S7 and the edges are numbered according
to their visiting order during the backward traversals. We cansee that the only difference between the traversal of φ1 and φ2is the edge 12; all other edges are redundantly traversed. Since
BASIC A NALYZER handles each query independently, there aremany redundant paths possible across different queries.
As discussed in Section I, for clients in which the input
alias queries come in a batch, handling the queries independently adds a lot of overhead due to redundant traversals
across queries. To address such redundant traversals, standard demand-driven analyses perform optimizations such as:
caching the results of the previous queries and caching thealready analyzed method summaries etc. However, as supported by our evaluation, these optimizations are not sufficient
to eliminate the possible redundant traversals across different
queries. If the queries are known to be available in batch,the information about the query (S7 , S3 ) will be known whenanswering the query (S7 , S11 ) (or vice versa). This priorknowledge can be used to avoid redundant path traversals. In
this paper, we propose the idea of batch analysis frameworkto efficiently handle multiple queries coming in batch mode.
We call our batch analysis technique as BATCH A NALYZER.
B. Irrelevant WorkTo see how BASIC A NALYZER performs irrelevant work,
consider the code shown in Fig. 1. Suppose we are interested
in answering only the alias query Φ = alias?(lsp25 , fsp22 ).
Based on the points-to edges of the variables involved, using
the ISPG in Fig. 2, we can see that the effective query ofΦ is φ = (S7 , S11 ). To answer this query, BASIC A NALYZER
performs backward analysis from the start node S7 to check fora context-sensitive memAlias-path to S11 . BASIC A NALYZER
starts with the ISPG node S7 corresponding to lsp25 andreaches S4 , the ISPG node pointed by cr15 in method
apply(), and from there reaches the nodes pointed bylr7 and br10 in methods client3() and client4()
respectively; the search continues until S11 is found. Fig. 6
lists the different paths used by BASIC A NALYZER startingfrom S7 until it reaches S11 to answer the query φ; theanalyzer may trace these paths in any order. Clearly, we cansee that π1 is a context-sensitive memAlias-path from S7 to
S11 and is a relevant path. However, π3 and π4 are different.
Path π3 : This is not even a valid path and is not necessary to the query because of the following two reasons:π1 : S 7

sp

S6

sp

π2 : S 7
π3 : S 7
π4 : S 7

S6

sp
sp

S6

S6

entry16
entry16

entry16
entry16

S4

S4

S4

S4

entry12
entry12

entry9entry16

S2

S2

S1

S5

entry6entry13

entry2O4

S8

O2

entry5

sp

S9

S10

sp

exit13

S11

3

S3

3

7

7

Fig. 6: Paths traversed on Fig. 2 for Φ = alias?(lsp25 , fsp22 ).
(1) Consider the subpath S7 → S6 → S4 → S1 of π3 .
The string on this subpath is sp entry16 entry9 , where
the type of S1 is LineRenderer and the type of S7
is ShadowPaint, which indicates that LineRenderer
has a field sp of type ShadowPaint. However, from thecode in Fig. 1, we can see that only BarRenderer has afield sp of type ShadowPaint and the subpath traversal
happened because of the upcast at the virtual call at Line 16.
(2) Consider the subpath S6 → S4 → S1 of π3 . The
string of this subpath is entry16 entry9 and hence is acontext-sensitive memAlias-path from S6 to S1 . Therefore,
it is expected that the types of S6 and S1 are compatible (same type or one is a subtype of another). However,
the type of S6 is BarRenderer and the type of S1 is
LineRenderer; both are not compatible types but are
subtypes of ChartRenderer. Again, in this case, the invalid
path is resulting due to the underlying implicit type cast.
Path π4 : Like π3 even this path is invalid, but because ofa different reason: Consider the subpath S6 → S4 → S5 of
π4 . It is traversing back from S6 which belongs to method
BarRenderer:paint to S5 which belongs to method
LineRenderer:paint. As the entry edges to callees
LineRenderer:paint and BarRenderer:paint in
the ISPG are added for the same call site at Line 16 in
Fig. 1, the information from LineRenderer:paint cannot
propagate to BarRenderer:paint at runtime and hence
the subpath S6 to S5 and thereby path π4 are invalid paths.
When processing the entry and exit edges, BASIC A NALYZER
does not recognize the paths across different target callees ofthe same virtual call site and hence allows such invalid paths.
To summarize, we see that even though BASIC A NALYZER
traverses paths like π3 and π4 , such paths are “irrelevant” foranswering the query Φ. These irrelevant traversals affect theperformance as well as the precision of the demand-driven

Alias Queries{φ1 , φ2 ...φN }Query Unifier
Batch Queries {G1 , G2 ...GM }AutoAnswerer

Alias Information
BATCH A NALYZER

Fig. 7: Block diagram of the batch alias analysis framework.

Input : Q = {(ni , mi )}N
i=1 , N = number of effective queries
Output: {rj }N
j=1 where rj stores the boolean value of φ(nj , mj )1 procedure batchAnalysis(Q)2
S = unifyToBatchQrys(Q);3foreach G ∈ S processed in the order of decreasing size do
4
autoAnswer(G);5batchQryCheckAliasing(G);function unifyToBatchQrys(Q)// Q = {(ni , mi )}K
i=1
G ← {};
8foreach (nx , mx ) ∈ Q do {cnt(nx )++; cnt(mx )++;} ;9max ← nodeWithMaxCnt(cnt, n1 , ..., nK , m1 , ..., mK );10
foreach (nx , mx ) ∈ Q do
11
if nx = max or mx = max then G ← G ∪ {(nx , mx )};6
7analysis. Further, it is challenging to detect such irrelevant
paths for an on-the-fly query during the analysis. Note that
context-sensitivity cannot capture these invalid paths as it
checks only for matching call/return pairs and all the invalid
paths discussed above respects (do not violate) this check. This
paper proposes a general type-information based technique to
avoid processing of such irrelevant paths which can be applied
to any pointer-analysis-based analysis to improve its precisionand performance. We call our technique as S MARTA NALYZER.
We discuss BATCH A NALYZER, our batch alias analysis
technique, in Section IV and S MARTA NALYZER, our optimized demand-driven alias analysis technique, in Section V.
IV. BATCH A NALYZER
We now discuss the details of our proposed batch analysis
framework, which can use a plugged-in demand-driven analyser (for example, BASIC A NALYZER, or S MARTA NALYZER
discussed in Section V) to efficiently answer batch queries,
by avoiding redundant computation. As discussed in Sections I
and III, in batch analysis all the possible alias queries froma client are known in advance. Note that a naı̈ve way to
reduce the redundant computations across different queries is
to cache all the intermediate traversed paths [20] and reuse
them upon re-analysis. However, such techniques store a lotof information (not-scalable) which may or may not be reusedin future; BATCH A NALYZER overcomes these challenges.
Fig. 7 depicts our batch alias analysis framework. Our
approach consists of two steps: (1) Query unification: to groupthe queries into a set of batch queries to make them moreamenable to batch processing. (2) Answering batch queries
by using the insights of batch analysis and the underlying
demand-driven analysis engine.
Batch Query Generation. Figure 8 shows the core of ourbatch alias analysis framework. We group a subset G ofstandard alias queries to a batch query such that the redundant
computations are eliminated completely across the queries in
G. The function unifyToBatchQrys depicts how the batch
queries are created. The input to the function is the set of all
effective queries {φ1 , φ2 , ..., φN } of the input alias queries{Φ1 , Φ2 , ..., ΦN 0 }. Note that N ≥ N 0 because an alias queryΦi can have more than one effective query if a variable in Φipoints-to more than one symbolic/allocation node in the ISPG.
Answer to Φi is true if at least one of its effective queries’
answer is true and is false when all of its effective queries’
answers are false. The function unifyToBatchQrys treats
the effective queries (n1 , n2 ) and (n2 , n1 ) as the same query.
The function unifyToBatchQrys unifies the effective queries into groups such that all the effective queries

12

return {G} ∪ unifyToBatchQrys(Q − G);

Fig. 8: Batch Alias Analysis
Input :G = {(nk , m1 ), (nk , m2 ), · · · (nk , mM )}Output: {rj }N
j=1 where rj stores the boolean value of φ(nk , mj )1 procedure batchQryCheckAliasing(G)2D ← {m1 , m2 , ..., mM }; WL ← {(nk , ∅, ∅)};
3
while WL 6= ∅ do4
remove (n, f ldStkn , cxtStkn ) from WL
5(f ldStk, cxtStk) ← clone(f ldStkn , cxtStkn )6
foreach edge ∈ n.Edges do
7
ignoreP ath ← processEdge(edge,fldStk,cxtStk)
8
if ignoreP ath 6= true then9n2 ← neighbour(e, n1 );10
if ∃mj ∈ D s.t. mj = n2 ∧ f ldStk = ∅ then11
D ← D − {mj }; rj ← true;
12
if D = ∅ then return;13
WL ← WL ∪ {n2 , f ldStk, cxtStk)};
14

foreach mj ∈ D do rj = f alse ;Fig. 9: Alias analysis for batch queries
with a common node in them are unified into the samegroup. Each such group becomes a batch query. However, two effective queries with a common node may
still be present in two different groups. For example,
if the set Q of input queries to the function are:{(a, b), (c, a), (d, c), (m, n), (p, q), (c, r), (a, m)}. Here, (c, a)
can be included in the group where (a, b) is present or in
the group where (d, c) is present. The function breaks suchties by greedily grouping the query with the group that canhave higher number of queries in it (See lines 9-11); note:
cnt is a local array. Thus, the set of batch queries for Q is:{{(a, b), (a, c), (a, m)}, {(c, d), (c, r)}, {(m, n)}, {(p, q)}}.
Answering Batch Queries. Given a batch query G with
queries sharing a common node, and an underlying demanddriven alias analyzer (for example, S MARTA NALYZER), we
now discuss how BATCH A NALYZER answers these queries.
As shown in Fig. 8, we first check if G can be answered
based on the queries answered so far; we do so by invoking
the function autoAnswer. If not, we invoke the function
batchQryCheckAliasing. We process the groups in thedecreasing order of their size. If the group has only element, the function batchQryCheckAliasing invokes thecheckAliasing function of the underlying demand-driven
analysis (for example, Fig. 3) – not shown explicitly.

Statement

n4
n3
n1

n5

n2
n6

n7

Fig. 10: Alias analysis paths in the ISPG.
In BATCH A NALYZER a batch query is formulated as asingle-source multiple destination CFL-reachability problem.
Hence, batchQryCheckAliasing in Fig. 9 works similar
to function checkAliasing in Fig. 3. The function starts
from a common start node nk and searches for the destination
nodes of all individual effective queries in the batch query
G. An individual query in G terminates at Line 11 when acontext-sensitive memAlias-path is found to its destinationnode, otherwise it terminates at Line 14. When the function
terminates, all the individual queries in G are answered. UnlikeBASIC A NALYZER, BATCH A NALYZER performs no redundant
traversals across the queries in G, because BATCH A NALYZER
never re-traverses the common paths across the queries in G
unless the retraversal is required even for BASIC A NALYZER
to solve an individual query. Here, we can see the advantage
of a batch analysis in which the redundant traversals acrossdifferent queries can be avoided without caching.
AutoAnswerer(Fig. 7) attempts individual effective
queries using prior solved queries. For example, if
alias?(n1 , n2 )=alias?(n2 , n3 )=true, ⇒ alias?(n1 , n3 )=true.
Thus, we can see that BATCH A NALYZER avoids redundant
path traversals, without caching any intermediate results, bytreating a set of individual queries in a batch query as a singlesource multiple destination CFL-reachability problem insteadof treating it as many single-source single destination CFLreachability problems and AutoAnswerer further avoids
redundant path traversals.
Discussion: We briefly describe the differences/similarities
between CACHE (see Section II) and the batch analysis
technique, using the graph in Fig. 10 that shows ISPG nodes
with memAlias-paths joining them. Note that we use CACHE
to compare (and not its precursor [20]) as CACHE takes the
input demand-driven queries into consideration for caching.
Consider the batch query G1 = (n1 , {n4 , n5 , n7 }). Here,the batch analysis will traverse each of the paths in the graphonly once. In contrast, CACHE re-traverses the paths n1n2
and n2n3 across the queries in G1 : (n1 , n4 ), (n1 , n5 ) and(n1 , n7 ); here, path n2
n3 may also be traversed whenanswering (n1 , n7 ) because the traversal is performed in BFS(breadth-first search) manner. However, say, if a batch query
G0 = (n3 , {n4 , n5 }) is solved before G1 , batch analysis retraverses the paths n3 to n4 and n3 to n5 , whereas CACHE
reuses those paths if the individual queries in G0 are solved
before solving the individual queries in G1 . Hence, in theory,neither of the techniques is more precise than the other (seeSection VI for an empirical comparison). Note that caching
can complement batching. For example, the answers to theindividual queries (n3 , n4 ) and (n3 , n5 ) of G0 can be cached,
and reused when solving a latter batch query, like G1 .

Type Information

τ1 = typ(x) ∧ τ2 = (typ(new()) ∨ typ(y))⇒ τ2 ∈ cmpt({τ1 }) ∧ τ1 ∈ cmpt({τ2 })τ1 = typ(x) ∧ τ2 = typ(y)⇒ τ2 ◦ τ1 [τ2 encloses τ1 ]Equivalent to assignments: fi = ai , r =Call: r=mret ; where fi is the ith formal parametera0 .m(a1 , .., ai , ..)of m and mret is the variable returned in m
Alloc: x=new()
Copy: x=y
Load: x=y.f
Store: y.f=x

Fig. 11: Type relations in the statements that affect points-to
information. typ(e) returns the static type of expression e.
V. S MARTA NALYZER
In this section, we use a novel type-based approach to
reduce the irrelevant work performed during demand-driven
analysis. Our approach is based on identifying relevant types
for the queries and by detecting edges that need not be
traversed (termed imaginary adjacent ISPG edges).
A. Relevant Types
Our goal now is to provide a general scheme to avoid
demand-driven alias (or points-to) analysis via invalid paths
that occur due to upcasting and downcasting in codes written
in languages that support subtype polymorphism.
Our strategy is based on identifying the set of relevant types
for a given input query Φ. To avoid traversing irrelevant paths
during backward analysis, we process a node only if the node
has a relevant type with respect to Φ. Our approach is basedon the following two definitions.
Definition 1 (Compatible Types). Given a type τ , all the
sub-types and supertypes of τ are the compatible types of τ .
Thus, for a set of types T , we compute its set of compatible
types cmpt(T ) = T ∪{t | t is a sub type or a super type of τ ,where τ ∈ T }.
Definition 2 (Type Enclosing). We say a type τ 0 encloses a
type τ 00 if there exists a sequence τ1 ◦ τ2 ◦ τ3 ◦ . . . τk such that
τ1 = τ 0 , τk = τ 00 and for all 1 ≤ i < k, there is a field oftype τi+1 in τi (represented by τi ◦ τi+1 ).
Fig. 11 shows the compatible types and type enclosing
relations in the program statements that affect the points-to
information. For example, for an assignment (copy) statement,
the LHS variable’s type belongs to the compatible types of
the RHS variable and vice versa. For a store statement, thebase variable’s type of the LHS field access encloses the typeof the RHS variable. The types of actual arguments and of
LHS variable at a call statement relate to the types of formal
parameters and of a return expression in the callee, in amanner similar to that of a copy statement. As the edges in
ISPG are constructed by processing these program statements(see Section II), entry/exit edges represent compatible typerelations and field edges represent type enclosing relations.
Definition 3 (Declared Types). If Φ = alias?(a, b) is an
input query and τ1 is the declared-type of variable a and τ2is the declared-type of variable b, then we define the set of
declared-types {τ1 , τ2 } as Dtype(Φ).

Definition 4 (Relevant Types). We define the set of relevant
types for a given query Φ as: cmpt(D)∪cmpt(E), where D is
the Dtype(Φ) and E = {τ | τ encloses τ 0 and τ 0 ∈ cmpt(D)}.
Let Φ = alias?(a, b) is the input query and φ = (S1 , S2 )is one of the effective queries of Φ. A context-sensitive
memAlias-path of Φ starts from S1 whose declared-type issay τ1 and passes through intermediate nodes connected via
field edges that represent type enclosing relations w.r.t. τ1 , orentry/exit edges that represent compatible type relations andfinally reaches S2 whose declared type is say τ2 . Thus, theset of relevant types for Φ (where, Dtype(Φ) = {τ1 , τ2 })captures the set of types of the nodes that can appear in acontext-sensitive memAlias-path of Φ. A context-sensitive
memAlias-path has the following key property:
Property 1. If a path π is a context-sensitive memAlias-path
for a query Φ, then a node n appears in π iff static -type(n) ∈Rtype, where Rtype=set of relevant types for Φ.
Our S MARTA NALYZER computes relevant types and uses
Property 1 to answer a query Φ. It processes the edges(by calling processEdge(), Section II) connected to anode in the worklist only if its type is in the set of relevant
types of Φ and thus avoids the irrelevant paths that canbe taken by BASIC A NALYZER. We now demonstrate thesame on the example query Φ = alias?(lsp25 , fsp22 ) from
Section III. Here, Dtype(Φ) = {ShadowPaint}, and theset of relevant types of Φ is Rtype = {ShadowPaint,
BarRenderer, ChartRenderer, Object}.
Rtype
includes BarRenderer as it encloses ShadowPaint
and includes {ChartRenderer, Object} because they
are the comaptible types of BarRenderer. Consider thepaths π1 and π3 in Fig. 6 traversed by BASIC A NALYZER
for answering the query Φ. Path π1 is a context-sensitive
memAlias-path and hence the types of nodes in path π1{ShadowPaint, BarRenderer, ChartRenderer} areincluded in the set Rtype. As LineRenderer, the typeof node S1 in π3 , is not included in the set Rtype, path
π3 cannot be a context-sensitive memAlias-path for Φ andhence it is not relevant to Φ. Similarly, path π4 in Fig. 6
is not relevant to Φ. S MARTA NALYZER avoids traversing
through paths π3 and π4 , thereby reducing the search space.
Note that the idea of relevant types is not specific to CFLreachability-based demand-driven alias analysis and is directly
applicable to any demand-driven points-to/alias analysis as thedata-flow in all these analyses is similar.
B. Imaginary Adjacent Edges
Our goal now is to detect and thereby avoid invalid pathtraversals discussed in Case 2 in Section III-B, which happens
whenever there are multiple target callees at a virtual call site.
Let φ = (S1 , S2 ) be an effective alias query. Let us
consider a method mcaller which calls a method mcallee ata call site x. Let p be a path from S1 which has an edge
e1 = (n1 , n2 ) in it such that n1 is in mcallee and n2 isin mcaller . Path p is an invalid path if the edge e1 has an

adjacent edge e2 = (n2 , n3 ) in p such that n3 is in m0callee ,where m0callee 6= mcallee is another target callee of mcallerat the same call site x. Hence, we focus on detecting such
imaginary adjacent edges to avoid invalid paths. In particular,
we look for adjacent edge pair (e1 , e2 ) in path p: S1 n1 e1 n2nk
e 2 n3(edge directions are omitted for simplicity), wheren1 is in mcallee , n2 is in mcaller , n3 is in m0callee , and mcallee
and m0callee are the target callees of mcaller at the same callsite x. We take this into consideration by noting that as weare interested in a traversal from a callee to a caller andagain to a callee, e1 and e2 should have opposite directions.
Thus, we ignore paths with (e1 , e2 ) pair having edge labels as(entryx , entryx ) or (exitx , exitx ). To identify such adjacentedge pair combinations, S MARTA NALYZER memoizes the lastprocessed edge. It marks the edges with unique IDs to store thecall site information. Thus, S MARTA NALYZER further reduces
the search space over that obtained using relevant-types, byeliminating invalid paths due to imaginary adjacent edges.

. .

. . .

VI. I MPLEMENTATION AND E VALUATION
Implementation. Our algorithms are implemented [25] byextending the Soot [26] framework We consider the following
seven variants for our evaluation. BASIC: Fig. 3, existing
BASIC A NALYZER [2]; RT: Fig. 3 with use of relevant types(Section V-A); VC: Fig. 3 with only valid paths at virtual
call sites (Section V-B); SMART: S MARTA NALYZER, Fig. 3
with extensions in RT and VC; BATCH: BATCH A NALYZER
using BASIC in Fig. 8 and S-BATCH: BATCH A NALYZER
using SMART in Fig. 8. CACHE: Fig. 3 with Fig. 4 and withcaching option enabled. We used the implementations of Yan
et al. [2], [23] for BASIC and CACHE. Note that we do notchoose the recent demand-driven works [14], [21] as baselines
for our work, as they are not suitable (we found them to takesignificantly more time, compared to BASIC) for data-racekind of clients that require simpler alias information.
We investigate the following three research questions:
RQ1: Is batch analysis efficient compared to a conventional
demand-driven analysis? RQ2: Is batch analysis beneficial
compared to caching? RQ3: What is the impact of eliminating
irrelevant paths on the precision and the performance of ademand-driven analysis?
Experimental Setup. We have run all our experiments on
an AMD 2.3GHz machine by allocating 64GB heap space to
the JVM. For RQ1, we evaluate our techniques on two clients:(1) a data-race detection tool (simulated), and (2) a refactoring
tool (existing). For RQ2 and RQ3, we only use the data-race
detection client. For all the RQs, the set of all the queries fora benchmark is collected and passed as an argument to thefunction batchAnalysis (see Fig. 8).
We simulate a data race detector client as done by Yan etal. [2] by considering all the queries of the form alias?(x, y)
where for some field f, x.f and y.f are accessed in
two program statements (Soot’s jimple IR statements) of theapplication code with at least one statement in the two being afield write operation. For this client, we evaluate our techniqueusing twelve Java programs from the DaCapo benchmark

DaCapo 2006
Bench
#RM
antlr
24190
bloat
13365
chart
29017
eclipse 12107
fop
25252
hsqldb 28231
jython
18926
xalan
24121

DaCapo 2009
Bench
#RM
avrora10693
luindex9730
lusearch
9612
pmd
13448

Used by Client
Bench
#RM
avrora
33780
fop
48780
javaGeom
27166
JFreeChart 29137
jOcular
33059
Rackj
15789
sunflow
28530
UR
24434

Fig. 12: Benchmarks used for the experiments. #RM (#Reachable methods) is as computed by Spark [1].
suite [27]. We have used (i) four benchmarks from the latest
DaCapo version (dacapo-9.12-MR1-bach.jar) – all the ones
that could be processed by the TamiFlex [28] (to eliminate
reflective calls) and Soot combination, and (ii) eight nonoverlapping ones from DaCapo 2006, as listed in the first andthe third columns of Fig. 12. The figure also lists the numberof callgraph reachable methods as computed by Spark [1].
Next, we consider an existing client Auto-SCST [5], aprogram understanding tool which automatically identifies
refactoring opportunities for two important refactorings ‘replace type code with subclass’ (SC-refactoring) and ‘replace
type code with state’ (ST-refactoring) that are required for performing ‘replace conditional with polymorphism’ refactoring.
For many client analyses such as Auto-SCST [5], CHORD [4],and so on, the alias queries can come in batches. Auto-SCST
has strict time budgets to identify the refactoring opportunities
because it is an Eclipse-plugin (IDE plugin). The tool classifies
an identified refactoring opportunity, represented using theclass and field pair hC , f i, for ST-refactoring if there is acontrol path from a read dereference x.f to a write dereference
y.f , both the dereferences refer to the field f of C, and x and y
are aliases. Since the refactoring opportunities are independentof each other, and all the opportunities are identified before
displaying to the developer, the set of all the queries is available (as input to batchAnalysis, Fig. 8). For Auto-SCST,
we use the eight open-source applications used by Vedurada
and Nandivada [5], [29]. The last two columns in Fig. 12 show
the details of the applications. Note that for the overlapping
benchmarks, the entries in fourth column are different fromthat of the ones in the last column, owing to the differencesin benchmark versions and the callgraph configurations.
For all the experiments, we use the cutoff used by by Yan
et al. [2] and set the budget as 75000 traversed ISPG nodes
for: (i) each demand-driven query in case of BASIC and (ii)each batch-query in case of BATCH and S-BATCH. We alsoenable summarization (to memoize intermediate method-levelsummaries/results) for all the library methods.
A. RQ1: Benefits of Batch Analysis
We first discuss about the analysis times of BASIC, BATCH,
and S-BATCH, and then about their precision on the datarace detection client followed by on the client Auto-SCST.
Fig 13 and Fig. 14 show the comparison of the time takenby the implementations and of their precisions, respectively.
The second column in Fig. 14(a) lists the number of alias
queries coming from the data-race client for each benchmark
and the third column lists the number of their corresponding
batch queries. We can see that the number of batch queries arequite less than that of the actual queries; this is because of thequery-unifier step in the batch analysis framework. Similarly,
in Fig. 14(b), columns 2 and 3 list the number of alias queries
generated by Auto-SCST and resulting batch-queries.
Results on Data-race Detection Client. Fig. 13(a) shows theanalysis times of all the three implementations to answer thealias queries. BATCH runs geomean 77.51% (up to 95.8%)
faster than BASIC and S-BATCH runs geomean 83.14% (upto 96.1%) faster than BASIC. S-BATCH performs geomean
12.13% (up to 45.64%) faster than BATCH showing the impactof eliminating irrelevant path traversals.
We have studied the number of budget exceptions of all
the three implementations (detailed plots skipped for space).
We found BATCH and S-BATCH lead to 85.52%, and 87.8%(geomean) less budget exceptions than BASIC, respectively –points to the performance improvements and scalability due
to the batch alias analysis. Note that the percentage reductionin the number of budget exceptions is due to the batching of
queries. For example, say, out of a given set of ten demanddriven queries six got timed-out with BASIC. If these ten aregrouped as a single batch query then BATCH would timeout
only once, as they are all solved together. Thus, the number ofbudget exceptions reduce from six to one (hence would lead tooverall faster execution). Note that BASIC and BATCH would
give the same answer for the remaining four.
Columns 4, 8 and 9 in Fig. 14(a) show the precision of all
the three implementations. Each entry shows the number of‘true’ answers of the data race queries and thus indicate thenumber of possible data races; lower the number, higher the
precision. BATCH reports up to 1.12% less data races thanBASIC (see avrora). The precision of BATCH and BASIC
varies slightly because BATCH transforms some effective
queries from (a, b) to (b, a) form during the unification step(see Section IV). Because of this swapping, BATCH may avoid
hitting budget exceptions in some cases – leads to improved
precision. However, such swapping may also lead to newer
budget exceptions or encounter static globals in the backward
analysis and conservatively answers ‘true’ – leads to reduced
precision. For example, for the program hsqldb, BATCH
reports two more data races than BASIC; but we found that
number of such cases have been very minimal. Similar to
BATCH, S-BATCH reports up to 10.22% less data races thanBASIC (for xalan) and reports 0.28% more data races for
luindex. We found that, overall, BATCH and SBATCH
report minor improvements in precision: 0.07% and 0.61%(geomean) less data races than BASIC, respectively.
Summary. Overall, compared to BASIC, over DaCapo
benchmarks, BATCH and S-BATCH run 77.5% (up to 95.8%)
and 83.1% (up to 96.1%) faster, respectively, with minor
precision gains; attests to the importance of batch analysis.

1000

BASIC
BATCH
S-BATCHTime [sec] (log scale)Time [sec] (log scale)

10000

1000

100

BASIC
SMART
BATCH
S-BATCH

100

10

10

un
o
ic
de

ow

nf

ar

j

ck

su

ra

e

ul

c
jo

e
jfr

om

(a) Impact on data race queries (on DaCapo benchmark suite).

ge

h

ra

rc

ro

p

fo

av

d

ex

ea

pm

s
lu

ra

d
in
lu

n

n

ro

av

la

ho

db
ql

xa

t
jy

hs

se

t

lip

p

fo

ec

t

ar

tlr

oa

ch

bl

an

1

(b) Impact of batch analysis on queries from Auto-SCST.

Fig. 13: Timing comparison (in seconds).
1

2

Bench

3

4

5

#Alias #Batch
Queries Queries

antlr
bloat
chart
eclipsefop
hsqldbjythonxalan
avroraluindexlusearch
pmd

8594
51158
2475
2516
899
15422
9413
988
16720
2627
1913
35547

283
974
338
306
105
729
615
105
527
295
253
365

6

7

8

9

Precision
BASIC

4941
51110
2407
2418
899
14730
9103
930
15920
2531
1884
35531

RT

4941
51110
2248
2418
899
14730
9103
930
15920
2531
1884
35531

VC

4941
51103
2407
2418
899
14724
9103
835
15911
2531
1884
35531

SMART BATCH S-BATCH

4941
51103
2242
2418
899
14724
9103
835
15911
2531
1884
35531

4941
51109
2407
2414
899
14732
9090
930
15742
2538
1883
35531

4941
51102
2243
2414
899
14726
9090
835
15741
2538
1883
35531

1

2

Bench

3

4

#Alias #Batch

5

6

7

Precision

Queries Queries BASIC SMART BATCH S-BATCH

avrorafop
javaGeom
JFreeChart
jOcular
RackJ
sunflow
UR

6136
781
158
748
243
75
75
62

248
155
13
146
25
9
22
14

4984
519
137
654
180
29
75
36

4984
518
137
654
180
29
75
36

4761
540
134
654
185
29
75
42

4761
539
134
654
185
29
75
42

(b) Precision on queries from the client Auto-SCST.

(a) Precision on data race queries.

Fig. 14: Precision comparison in terms of the number of aliases detected (lower the better).
Results on Auto-SCST. SMART, BATCH and S-BATCH show
similar performance and precision improvements over BASIC
on Auto-SCST. Fig. 13(b) shows the analysis times of all thefour implementations on Auto-SCST. SMART, BATCH and
S-BATCH run 1.75%, 31.94%, and 33.3% (geomean) fasterthan BASIC, respectively (and up to 29.35%, 88.15%, and90.81% faster than BASIC, respectively). In terms of numberof budget exceptions, SMART, BATCH and S-BATCH have
3.7%, 73%, and 78.03% (geomean) less budget exceptions
than BASIC, respectively.
In Fig. 14(b), columns 4-7 list the number of ‘true’ answers
for the alias queries. SMART, BATCH and S-BATCH report
up to 0.19% (fop), up to 4.47% (avrora) and up to 4.47%(avrora), respectively, less aliases than BASIC. In UR, fop,and jocular the reason for precision losses of BATCH and
S-BATCH is again because of the swapping of queries in theunification step. We found that, overall, SMART reports 0.02%(geomean) less data races than BASIC, and BATCH and SBATCH report 5.46%, and 5.44% (geomean) more data races
than BASIC. The geomean percentages for BATCH and SBATCH are mainly biased by the precision differences in UR.

Summary. The performance improvements show the benefitsof batch analysis over demand-driven analysis and the needfor a batch analysis framework, for real-world clients like
Auto-SCST, to answer alias queries in batch mode.
Discussion. For the tested benchmarks, auto-answerer (seeSection IV) had no impact. But in practice, we can easily
visualise cases where auto-answerer can be impactful. Hence,
we keep the auto-answerer step intact, especially considering
minimal overheads due to auto-answerer.
B. RQ2: Batch Analysis vs Caching
We now compare BATCH and S-BATCH against CACHE(see Section II) to show the performance of our batch analysis
technique against caching. As it is known, the performanceof CACHE may depend on the order of queries. For eachbenchmark, we use the data-race queries obtained by iteratingover the methods in the order as given by the SPARK callgraph (as used by Yan et al. [2]).
Fig. 15 shows the performance of CACHE against BASIC,
BATCH and S-BATCH on the queries from the data-race detection client. CACHE performs 20.37% (geomean) better thanBASIC whereas BATCH and S-BATCH perform 77.51% and83.14% (geomean) better than BASIC, respectively. Clearly,10000

BASIC
CACHE
BATCH
S-BATCHTime [sec] (log scale)Time [sec] (log scale)

10000

1000

100

10

BASIC
RT
VC
SMART

1000

100

10
d

h

rc

ex

ea

pm

s
lu

ra

d
in
lu

n

n

ro

av

la

ho

se

h

rc

db
ql

xa

t
jy

hs

p

fo

t

lip

ec

t

ar

tlr

oa

ch

bl

an

d

ex

ea

pm

s
lu

ra

d
in
lu

n

n

ro

av

la

ho

se

db
ql

xa

t
jy

hs

p

fo

t

lip

ec

t

ar

tlr

oa

ch

bl

an

Fig. 15: Caching against batch analysis on data race queries.

Fig. 16: Impact of irrelevant path elimination (DaCapo suite).

our batch analysis techniques outperform CACHE; In termsof the number of budget exceptions, CACHE, BATCH and
S-BATCH have 48.48%, 85.52% and 87.8% (geomean) lessbudget exceptions than BASIC, respectively, asserting theimprovements in analysis timings. In case of hsqldb, we seethat caching shows negative effects which can happen when
the benefits from reusing the cached entries get subsumed
by the cost of searching the cached entries. We have also
tried enabling caching for BATCH and for S-BATCH, andwe observed that caching has minimal impact on batching
techniques (BATCH improved by 0.38%, S-BATCH’s performance decreased by 7.6% (geomean)). This shows thatour batch analysis technique subsumes most of the benefitsof caching. In terms of precision, CACHE reports 0.02%(geomean) more data races than BASIC, whereas BATCH and
SBATCH reported 0.07% and 0.61% (geomean) less data races
than BASIC, respectively. Note that the reason for precision
loss for CACHE (compared to BASIC) is because of notdifferentiating the cached queries of form (a, b) with theirswapped form (b, a) during reuse (similar to batch analysis).
Summary. Overall, compared to CACHE, BATCH and
S-BATCH run 54.54% and 70.3% faster, respectively. We
argue that batch analysis technique mostly subsumes thebenefits of caching and outperforms it.

BenchTotal types

antlr
bloat
chart
eclipsefop
hsqldbjythonxalan
avroraluindexlusearch
pmd

5865
3204
6642
3261
8109
6349
4299
6404
3418
3136
3121
3792

C. RQ3: Performance of S MARTA NALYZER
We first discuss about the analysis times of the implementations BASIC, SMART, RT and VC, and then about theirprecision. Fig. 16 shows the analysis times of all the four
implementations to answer the alias queries. SMART performs
10.97% (geomean) better than BASIC (up to 54.36% better).
We explain the reasons behind the performance difference bystudying the performance of RT and VC.
In Fig. 16, it can be seen that for most of the benchmarks RT
and VC perform better than BASIC. The reason for RT and
VC not showing performance benefits over BASIC in somecases is the following: BASIC may conservatively answer analias query as ‘true’ via an irrelevant path, whereas RT or
VC may try for the precise answer ‘false’ by searching amuch longer ‘relevant’ search space – can be expensive. For
example, in the case of the program chart, RT takes 16.3%

Avg
% Avg
Time (msec)
Relevant types Relevant types
4109
2191
4722
2255
5850
4478
3127
4543
2326
2066
2045
2453

70.0
68.4
71.0
69.1
72.1
70.5
72.7
70.9
68.0
65.8
65.5
64.6

722
948
1240
513
646
1401
975
530
855
383
363
413

Fig. 17: Details on the computed relevant types.
more time than BASIC (also realizes improved precision, seeFig. 14(a)). In Fig. 17, we show that the overheads of the RT
implementation cannot be the reason for such performancedegradation. Fig. 17 lists the total time taken by RT to findthe relevant types for all the queries (in last column) and theaverage number of relevant types for a query (in third column).
We can see that the average time taken by RT to find relevant
types is almost negligible. RT performs up to 11.3% (lusearch)better than BASIC; geomean = −0.43%; the negative value ismainly because of the difference in performance on chart.
VC performs geomean 9.01% (up to 54%) better than BASIC.
In Fig. 14(a), columns 4-7 show the precision of all thefour implementations. SMART reports up to 10.2% less data
races than BASIC (for xalan). SMART can be more precise
than BASIC when SMART finishes the search within the timebudget and: (1) BASIC fails to finish because of irrelevant
traversals, or (2) BASIC conservatively hits a static global
or a destination node via an irrelevant path. For the chart
program, the 16.3% performance loss of RT can be attributed
to the 6.61% precision improvements for that program. VC
also shows up to 10.2% precision improvements. We foundthat, overall, RT, VC and SMART report 0.18%, 0.23% and0.47% (geomean) less data races than BASIC, respectively.
Summary. Overall, compared to BASIC, SMART runs
10.97% (up to 54.36%) faster with minor precision gains, on

DaCapo benchmarks. It shows that demand-driven analyses
can be made performant by avoiding irrelevant path traversals.
VII. R ELATED W ORK
There exist many prior works on alias/points-to analysis.
Sridharan et al. [7] present a survey of the alias analysis techniques for object-oriented programs. Ryder [30] andHind [8] present insightful discussions on different dimensions
on pointer analysis. In this section, we mainly focus our discussion to the works that are closely related to our approach.
Demand-driven
Points-to/Alias
Analyses.
Many
researchers [11]–[13], [15], [20] have focused on improving
the scalability of demand-driven points-to analysis based on
CFL-reachability to suit the environments like just-in-time(JIT) compilers and interactive development environments(IDEs). Past works [2], [16] further improved the performanceof CFL-reachability based solution by answering the alias
queries directly without computing the points-to informationand show that for answering may-alias queries, a demanddriven alias analysis is more efficient than a demand-driven
points-to analysis. Boomerang [14] is a demand-driven, flow-,
field- and context-sensitive pointer analysis built on top of the
IFDS (Interprocedural Finite Distributive Subset problems)
framework. It supports all-alias (to find all aliases of agiven variable along with its points-to information) queries
that are required for the clients like taint analysis. Since it
requires all-alias queries, in cases of simple demand-driven
points-to/alias queries, it can perform more work than that
required to answer the input demand-driven queries. Recently
Späth et al. [21] have presented a demand-driven, flow-, fieldand context-sensitive pointer analysis which encodes contextsensitivity and field-sensitivity as a separate “synchronized”
CFL reachability problems using the concept of synchronized
pushdown systems (SPDS). All these techniques answer one
query at a time (fully on-demand) and none of them exploit
the resulting advantages when the queries come in batch.
These works perform ad-hoc caching (or summarization)
to avoid redundant computations across different queries
without exploiting the availability of queries in advance inbatch mode. Hence they suffer from storing unnecessary
information and/or from missing to store useful information
across different queries leading to performance losses.
We overcome these challenges by proposing a batch analysis
framework that can handle multiple queries in a batch mode.
We instantiate a “batch version” of the popular demand-driven
analysis of Yan et al. [2]. We have observed the recent demanddriven works [14], [21] although more precise than that of
Yan et al. [2], do not suit for clients where the number ofalias queries is large. Further, most of the techniques discussed
above suffer from the issue of irrelevant path traversals, whichis addressed in this paper.
Analyses that Handle Queries in Batch. Su et al. [15] proposed a parallel algorithm to CFL-reachability-based demanddriven, context-sensitive points-to analysis to meet the requirements of clients where the queries come in batch. The
technique processes the queries independently on different

cores allowing some data-sharing across different queries
based on few heuristics. In this paper, we propose a sequential
algorithm which processes multiple queries together in one
pass as a batch query. Hence, our technique does not require
data sharing across individual queries in a batch query.
There have been prior works (not demand-driven) that
present target client-specific solutions [31], improving the
precision based on a complete set of queries [32]–[35]. In
contrast, we present a scheme to improve the performanceand precision by exploiting the underlying features of batch
queries. Their techniques are complimentary to our approach.
Type-based Optimizations in Points-to/Alias Analyses. Diwan et al. [36] use type information and propose different alias
analyses for Modula-3, a statically-typed type-safe language.
For Java, many past works [1], [7], [11] perform type-based
checks to avoid invalid data-flow paths and thus improve
the precision and efficiency of the points-to analysis. The
work of Sridharan et al. [11] (hereafter referred to as SRI)
uses type-based optimizations that subsumes the ones usedby Lhoták and Hendren [1], and Sridharan et al. [7]. The
type-based checks of SRI use compatible types to avoid
marking possible aliasing nodes in two phases: (1) during awhole-program pre-analysis by avoiding the addition of some“match” edges, ahead of time (not dependent on demanddriven queries), (2) on-the-fly when answering a points-toquery by not considering nodes whose types are incompatible
with the type of the query variable. In contrast, we consider
enclosing types along with compatible types (used in SRI)
for constructing the set of relevant types with respect to thegiven demand-driven queries and use them to avoid traversing
irrelevant paths in the ISPG.
VIII. C ONCLUSION
Demand-driven analyses can be costly when applied onlarge systems where the number of queries is high. This is
not acceptable in cases when the clients of the analyses areplugged into an IDE-kind of resource-bound environments.
We propose the idea of batch alias analysis that can efficiently address such clients by avoiding redundant computations within batch queries. Batch analysis suits the environments with strict time constraints, where the queries comein batch. Our proposed techniques (publicly available [25])improve the performance by avoiding redundant and irrelevant
computation. Our evaluation shows that the proposed batch
analysis leads to significant performance gains, along withminor gains in precision. We also show that the elimination ofirrelevant search paths can improve the performance and theprecision of the demand-driven alias analysis of Yan at al. [2](the best one suitable for race-detection type of clients).
ACKNOWLEDGMENT
We thank the shepherd, the PC chairs and all the reviewers
for their valuable comments. We thank Dacang Yan, Harry
Xu and Atanas Rountev for making their code publicly available [23]. Jyothi Vedurada is supported by the TCS Research
Scholarship Program for her doctoral studies.

R EFERENCES[1] O. Lhoták and L. Hendren, “Scaling Java Points-to Analysis Using
Spark,” in Compiler Construction, G. Hedin, Ed. Berlin, Heidelberg:
Springer Berlin Heidelberg, 2003, pp. 153–169.
[2] D. Yan, G. Xu, and A. Rountev, “Demand-driven Context-sensitive
Alias Analysis for Java,” in Proceedings of the 2011 International
Symposium on Software Testing and Analysis, ser. ISSTA ’11. New
York, NY, USA: ACM, 2011, pp. 155–165. [Online]. Available:
http://doi.acm.org/10.1145/2001420.2001440[3] M. G. Nanda and S. Sinha, “Accurate interprocedural null-dereference
analysis for java,” in 2009 IEEE 31st International Conference on
Software Engineering, May 2009, pp. 133–143.
[4] M. Naik, A. Aiken, and J. Whaley, “Effective Static Race Detection
for Java,” in Proceedings of the 27th ACM SIGPLAN Conference on
Programming Language Design and Implementation, ser. PLDI ’06.
New York, NY, USA: ACM, 2006, pp. 308–319. [Online]. Available:
http://doi.acm.org/10.1145/1133981.1134018[5] J. Vedurada and V. K. Nandivada, “Identifying Refactoring Opportunities
for Replacing Type Code with Subclass and State,” Proc. ACM Program.
Lang., vol. 2, no. OOPSLA, pp. 138:1–138:28, Oct. 2018. [Online].
Available: http://doi.acm.org/10.1145/3276508[6] L. O. Andersen., “Program Analysis and Specialization for the C Programming Language,” Ph.D. dissertation, DIKU, University of Copenhagen, May 1994.
[7] M. Sridharan, S. Chandra, J. Dolby, S. J. Fink, and E. Yahav,“Aliasing in object-oriented programming,” D. Clarke, J. Noble, andT. Wrigstad, Eds. Berlin, Heidelberg: Springer-Verlag, 2013, ch.
Alias Analysis for Object-oriented Programs, pp. 196–232. [Online].
Available: http://dl.acm.org/citation.cfm?id=2554511.2554523[8] M. Hind, “Pointer Analysis: Haven’t We Solved This Problem Yet?”in Proceedings of the 2001 ACM SIGPLAN-SIGSOFT Workshop on
Program Analysis for Software Tools and Engineering, ser. PASTE ’01.
New York, NY, USA: ACM, 2001, pp. 54–61. [Online]. Available:
http://doi.acm.org/10.1145/379605.379665[9] A. Milanova, A. Rountev, and B. G. Ryder, “Parameterized Object
Sensitivity for Points-to and Side-effect Analyses for Java,” inProceedings of the 2002 ACM SIGSOFT International Symposium
on Software Testing and Analysis, ser. ISSTA ’02. New York,NY, USA: ACM, 2002, pp. 1–11. [Online]. Available: http://doi.acm.org/10.1145/566172.566174[10] S. Z. Guyer and C. Lin, “Client-driven Pointer Analysis,” inProceedings of the 10th International Conference on Static Analysis,ser. SAS’03. Berlin, Heidelberg: Springer-Verlag, 2003, pp. 214–236.
[Online]. Available: http://dl.acm.org/citation.cfm?id=1760267.1760284[11] M. Sridharan, D. Gopan, L. Shan, and R. Bodı́k, “Demanddriven Points-to Analysis for Java,” in Proceedings of the 20th
Annual ACM SIGPLAN Conference on Object-oriented Programming,
Systems, Languages, and Applications, ser. OOPSLA ’05. New
York, NY, USA: ACM, 2005, pp. 59–76. [Online]. Available:
http://doi.acm.org/10.1145/1094811.1094817[12] M. Sridharan and R. Bodı́k, “Refinement-based Context-sensitive
Points-to Analysis for Java,” in Proceedings of the 27th ACM SIGPLAN
Conference on Programming Language Design and Implementation,
ser. PLDI ’06. New York, NY, USA: ACM, 2006, pp. 387–400.
[Online]. Available: http://doi.acm.org/10.1145/1133981.1134027[13] L. Shang, X. Xie, and J. Xue, “On-demand dynamic summarybased points-to analysis,” in Proceedings of the Tenth International
Symposium on Code Generation and Optimization, ser. CGO ’12.
New York, NY, USA: ACM, 2012, pp. 264–274. [Online]. Available:
http://doi.acm.org/10.1145/2259016.2259050[14] J. Späth, L. N. Q. Do, K. Ali, and E. Bodden, “Boomerang:
Demand-Driven Flow- and Context-Sensitive Pointer Analysis for
Java,” in 30th European Conference on Object-Oriented Programming,
ECOOP 2016, July 18-22, 2016, Rome, Italy, 2016, pp. 22:1–22:26.
[Online]. Available: https://doi.org/10.4230/LIPIcs.ECOOP.2016.22[15] Y. Su, D. Ye, and J. Xue, “Parallel Pointer Analysis with CFLReachability,” 43rd International Conference on Parallel Processing,no. ICPP, pp. 451–460, 2014.
[16] X. Zheng and R. Rugina, “Demand-driven Alias Analysis for C,” inProceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposiumon Principles of Programming Languages, ser. POPL ’08. New
York, NY, USA: ACM, 2008, pp. 197–208. [Online]. Available:
http://doi.acm.org/10.1145/1328438.1328464[17] M. Sridharan, “Discussion in Soot mailing list on demand-driven
points-to analyses,” 2006, www.sable.mcgill.ca/pipermail/soot-list/
2006-January/000477.html.
[18] B. K. Rosen, “Linear Cost is Sometimes Quadratic,” in Proceedingsof the 8th ACM SIGPLAN-SIGACT Symposium on Principles ofProgramming Languages, ser. POPL ’81. New York, NY, USA:ACM, 1981, pp. 117–124. [Online]. Available: http://doi.acm.org/10.
1145/567532.567545[19] M. Hind and A. Pioli, “Which Pointer Analysis Should I Use?”in Proceedings of the 2000 ACM SIGSOFT International Symposium
on Software Testing and Analysis, ser. ISSTA ’00. New York,NY, USA: ACM, 2000, pp. 113–123. [Online]. Available: http://doi.acm.org/10.1145/347324.348916[20] G. Xu, A. Rountev, and M. Sridharan, “Scaling CFL-ReachabilityBased Points-To Analysis Using Context-Sensitive Must-Not-Alias
Analysis,” in Proceedings of the 23rd European Conference on
Object-Oriented Programming, ECOOP 2009. Berlin, Heidelberg:
Springer-Verlag, 2009, pp. 98–122. [Online]. Available: http://dx.doi.
org/10.1007/978-3-642-03013-0 6[21] J. Späth, K. Ali, and E. Bodden, “Context-, Flow-, and Field-sensitive
Data-flow Analysis Using Synchronized Pushdown Systems,” Proc.
ACM Program. Lang., vol. 3, no. POPL, pp. 48:1–48:29, Jan. 2019.
[Online]. Available: http://doi.acm.org/10.1145/3290361[22] JFreeChart, “A Java Chart Library,” 2017, https://sourceforge.net/
projects/jfreechart/.
[23] “Source Code: Demand-Driven Context-Sensitive Alias Analysis for
Java,” 2013, http://web.cs.ucla.edu/∼harryxu/tools/files/MayAlias.zip.
[24] Y. Lu, L. Shang, X. Xie, and J. Xue, “An Incremental Pointsto Analysis with CFL-Reachability,” in Proceedings of the 22Nd
International Conference on Compiler Construction, ser. CC’13.
Berlin, Heidelberg: Springer-Verlag, 2013, pp. 61–81. [Online].
Available: http://dx.doi.org/10.1007/978-3-642-37051-9 4[25] J. Vedurada and V. K. Nandivada, “Source Code: Batch Alias Analysis (BatchAnalyzer),” 2019, https://archive.softwareheritage.org/browse/
origin/https://github.com/jyothivedurada/BatchAnalyzer.git.
[26] R. Vallée-Rai, P. Co, E. Gagnon, L. Hendren, P. Lam, andV. Sundaresan, “Soot - a Java Bytecode Optimization Framework,
booktitle = Proceedings of the 1999 Conference of the Centre forAdvanced Studies on Collaborative Research,” ser. CASCON ’99.
IBM Press, 1999, pp. 13–. [Online]. Available: http://dl.acm.org/
citation.cfm?id=781995.782008[27] S. M. Blackburn, R. Garner, C. Hoffman, A. M. Khan, K. S. McKinley,
R. Bentzur, A. Diwan, D. Feinberg, D. Frampton, S. Z. Guyer, M. Hirzel,
A. Hosking, M. Jump, H. Lee, J. E. B. Moss, A. Phansalkar, D. Stefanović, T. VanDrunen, D. von Dincklage, and B. Wiedermann, “The
DaCapo Benchmarks: Java Benchmarking Development and Analysis,”in OOPSLA ’06. New York, NY, USA: ACM Press, Oct. 2006, pp.
169–190.
[28] E. Bodden, A. Sewe, J. Sinschek, M. Mezini, and H. Oueslati, “Taming
Reflection: Aiding Static Analysis in the Presence of Reflection andCustom Class Loaders,” in Proceeding of the 33rd International Conference on Software Engineering, ser. ICSE ’11. New York, NY, USA:ACM, 2011, pp. 241–250.
[29] J. Vedurada and V. K. Nandivada, “Refactoring Opportunities for
Replacing Type Code with State and Subclass,” in Proceedings of the39th International Conference on Software Engineering Companion,
ser. ICSE-C ’17. Piscataway, NJ, USA: IEEE Press, 2017, pp.
305–307. [Online]. Available: https://doi.org/10.1109/ICSE-C.2017.97[30] B. G. Ryder, “Dimensions of Precision in Reference Analysis of
Object-Oriented Programming Languages,” in Compiler Construction,
G. Hedin, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003,
pp. 126–137.
[31] M. Thakur and V. K. Nandivada, “Compare less, defer more: scaling
value-contexts based whole-program heap analyses,” in Proceedings ofthe 28th International Conference on Compiler Construction, CC 2019,
Washington, DC, USA, February 16-17, 2019, 2019, pp. 135–146.
[Online]. Available: https://doi.org/10.1145/3302516.3307359[32] H. Oh, W. Lee, K. Heo, H. Yang, and K. Yi, “Selective Contextsensitivity Guided by Impact Pre-analysis,” in Proceedings of the 35th
ACM SIGPLAN Conference on Programming Language Design and
Implementation, ser. PLDI ’14. New York, NY, USA: ACM, 2014,
pp. 475–484. [Online]. Available: http://doi.acm.org/10.1145/2594291.
2594318

[33] S. Jeong, M. Jeon, S. Cha, and H. Oh, “Data-driven Contextsensitivity for Points-to Analysis,” Proc. ACM Program. Lang., vol. 1,
no. OOPSLA, pp. 100:1–100:28, Oct. 2017. [Online]. Available:
http://doi.acm.org/10.1145/3133924[34] G. M. Rama, R. Komondoor, and H. Sharma, “Refinement in
Object-sensitivity Points-to Analysis via Slicing,” Proc. ACM Program.
Lang., vol. 2, no. OOPSLA, pp. 142:1–142:27, Oct. 2018. [Online].
Available: http://doi.acm.org/10.1145/3276512[35] X. Zhang, R. Mangal, R. Grigore, M. Naik, and H. Yang,“On Abstraction Refinement for Program Analyses in Datalog,” inProceedings of the 35th ACM SIGPLAN Conference on Programming
Language Design and Implementation, ser. PLDI ’14. New York,NY, USA: ACM, 2014, pp. 239–248. [Online]. Available: http://doi.acm.org/10.1145/2594291.2594327[36] A. Diwan, K. S. McKinley, and J. E. B. Moss, “Type-based Alias
Analysis,” in Proceedings of the ACM SIGPLAN 1998 Conference on
Programming Language Design and Implementation, ser. PLDI ’98.
New York, NY, USA: ACM, 1998, pp. 106–117. [Online]. Available:
http://doi.acm.org/10.1145/277650.277670