Demand-Driven Pointer Analysis with Strong Updates via Value-Flow Refinement
- Publication Type:
- Journal Article
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
We present a new demand-driven flow- and context-sensitive pointer analysis
with strong updates for C programs, called SUPA, that enables computing
points-to information via value-flow refinement, in environments with small
time and memory budgets such as IDEs. We formulate SUPA by solving a graph
reachability problem on an inter-procedural value-flow graph representing a
program's def-use chains, which are pre-computed efficiently but
over-approximately. To answer a client query (a request for a variable's
points-to set), SUPA reasons about the flow of values along the pre-computed
def-use chains sparsely (rather than across all program points), by performing
only the work necessary for the query (rather than analyzing the whole
program). In particular, strong updates are performed to filter out spurious
def-use chains through value-flow refinement as long as the total budget is not
exhausted. SUPA facilitates efficiency and precision tradeoffs by applying
different pointer analyses in a hybrid multi-stage analysis framework.
We have implemented SUPA in LLVM (3.5.0) and evaluate it by choosing
uninitialized pointer detection as a major client on 18 open-source C programs.
As the analysis budget increases, SUPA achieves improved precision, with its
single-stage flow-sensitive analysis reaching 97.4% of that achieved by
whole-program flow-sensitive analysis by consuming about 0.18 seconds and 65KB
of memory per query, on average (with a budget of at most 10000 value-flow
edges per query). With context-sensitivity also considered, SUPA's two- stage
analysis becomes more precise for some programs but also incurs more analysis
times. SUPA is also amenable to parallelization. A parallel implementation of
its single-stage flow-sensitive analysis achieves a speedup of up to 6.9x with
an average of 3.05x a 8-core machine with respect its sequential version.
Please use this identifier to cite or link to this item: