Event Entry
New for: D1, D2, D3, D4, D5
What and Who
Liveness-Based Pointer Analysis
Date, Time and Location
Abstract
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. It 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.
Contact
Video Broadcast
Susanne Rock, 04/18/2013 10:02 -- Created document.