[PRL] [1112.5000] Lazy Pointer Analysis

[Mitchell Wand]

Lazy Pointer Analysis
Uday P. Khedker <http://arxiv.org/find/cs/1/au:+Khedker_U/0/1/0/all/0/1>, Alan
Mycroft <http://arxiv.org/find/cs/1/au:+Mycroft_A/0/1/0/all/0/1>, Prashant
Singh Rawat <http://arxiv.org/find/cs/1/au:+Rawat_P/0/1/0/all/0/1>
(Submitted on 21 Dec 2011)

Flow- and context-sensitive pointer analysis is generally considered too
expensive for large programs; most tools relax one or both of the
requirements for scalability. We formulate a flow- and context-sensitive
points-to analysis that is lazy in the following sense: points-to
information is computed only for live pointers and its propagation is
sparse (restricted to live ranges of respective pointers). Further, our
analysis (a) uses strong liveness, effectively including dead code
elimination; (b) afterwards calculates must-points-to information from
may-points-to information instead of using a mutual fixed-point; and (c)
uses value-based termination of call strings during interprocedural
analysis (which reduces the number of call strings significantly).
A naive implementation of our analysis within GCC-4.6.0 gave analysis time
and size of points-to measurements for SPEC2006. Using liveness reduced the
amount of points-to information by an order of magnitude with no loss of
precision. For all programs under 30kLoC we found that the results were
much more precise than gcc's analysis. What comes as a pleasant surprise
however, is the fact that below this cross-over point, our naive
linked-list implementation is faster than a flow- and context-insensitive
analysis which is primarily used for efficiency. We speculate that lazy
flow- and context-sensitive analyses may be not only more precise, but also
more efficient, than current approaches.


http://arxiv.org/abs/1112.5000
-------------- next part --------------
HTML attachment scrubbed and removed