Lazy Pointer Analysis

Details Lazy Pointer Analysis Lazy Pointer Analysis

2011-12-21

arxiv.org/abs/1112.5000v1

Computer Science

Programming Languages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Lazy Pointer Analysis does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lazy Pointer Analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lazy Pointer Analysis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-191739