Abstract The Ant ��Ò�×ÙØ�Ü�×��Ù and the Grasshopper: Fast and Ð�Ò×ÙØ�Ü�×��Ù Accurate Pointer Analysis for Millions of Lines of Code

Pointer information is a prerequisite for most program analyses, and the quality of this information can greatly affect their precision and performance. Inclusion-based (i.e. Andersen-style) pointer analysis is an important point in the space of pointer analyses, offering a potential sweet-spot in the trade-off between precision and performance. However, current techniques for inclusion-based pointer analysis can have difficulties delivering on this potential. We introduce and evaluate two novel techniques for inclusionbased pointer analysis—one lazy, one eager 1 —that significantly improve upon the current state-of-the-art without impacting precision. These techniques focus on the problem of online cycle detection, a critical optimization for scaling such analyses. Using a suite of six open-source C programs, which range in size from 169K to 2.17M LOC, we compare our techniques against the three best inclusion-based analyses—described by Heintze and Tardieu [11], by Pearce et al. [21], and by Berndl et al. [4]. The combination of our two techniques results in an algorithm which is on average �¢faster than Heintze and Tardieu’s algorithm,���¢faster than Pearce et al.’s algorithm, and��¢faster than Berndl et al.’s algorithm. We also investigate the use of different data structures to represent points-to sets, examining the impact on both performance and memory consumption. We compare a sparse-bitmap implementation used in the GCC compiler with a BDD-based implementation, and we find that the BDD implementation is on average 2¢slower than using sparse bitmaps but uses 5.5¢less memory