Liveness-Based Pointer Analysis
Uday Khedker
(IIT Bombay)
Info
|
Date
|
3rd July 2014
|
|
Time
|
15:00
|
|
Place
|
278
|
Abstract
Precise flow- and context-sensitive pointer analysis (FCPA) is generally
considered prohibitively expensive for arge programs; most tools relax
one or both of the requirements for scalability. We argue that precise
FCPA has been over-harshly judged---the vast majority of points-to pairs
calculated by existing algorithms are never used by any client analysis
or transformation because they involve dead variables. We therefore
formulate a FCPA in terms of a joint points-to and liveness analysis
which we call L-FCPA. Our analysis computes points-to information only
for live pointers and its propagation is sparse (restricted to live
ranges of respective pointers). Further, our analysis
- uses strong liveness, effectively including dead code elimination,
- calculates must-points-to information from may-points-to information
afterwards instead of using a mutual fixed-point, and
- uses value-based termination of call strings during interprocedural
analysis (which reduces the number of call strings significantly).
We implemented a naive L-FCPA in GCC-4.6.0 using linked lists.
Evaluation on SPEC2006 showed significant increase in the precision of
points-to pairs compared to GCC's analysis. Interestingly, our naive
implementation turned out to be faster than GCC's analysis for all
programs under 30kLoC. Further, L-FCPA showed that fewer than 4% of
basic blocks had more than 8 points-to pairs. We conclude that the
usable points-to information and the required context information is
small and sparse and argue that approximations (e.g. weakening flow or
context sensitivity) are not only undesirable but also unnecessary for
performance.
Reference:
Uday P. Khedker, Alan Mycroft, and Prashant Singh Rawat.
Liveness Based Pointer Analysis.
International Static Analysis Symposium (SAS 2012). France 2012.
(This supercedes the earlier paper Lazy Pointer Analysis that was
posted in the CM Computing Research Repository, abs/cs/1112.5000.)
Further info
