Estimating the Impact of Scalable Pointer Analysis on OptimizationEstimating the Impact of Scalable Pointer Analysis on OptimizationThis research was conducted by Manuvir Das, Ben Liblit, Manuel Fähndrich, and Jakob Rehof. The paper has been published in the Eighth Annual International Static Analysis Symposium (SAS ’01), and is also filed as Microsoft Research technical report MSR-TR-2001-20.
This paper addresses the following question: Do scalable control-flow-insensitive pointer analyses provide the level of precision required to make them useful in compiler optimizations?
We first describe alias frequency, a metric that measures the ability of a pointer analysis to determine that pairs of memory accesses in C programs cannot be aliases. We believe that this kind of information is useful for a variety of optimizations, while remaining independent of a particular optimization. We show that control-flow and context insensitive analyses provide the same answer as the best possible pointer analysis on at least 95% of all statically generated alias queries. In order to understand the potential run-time impact of the remaining 5% queries, we weight the alias queries by dynamic execution counts obtained from profile data. Flow-insensitive pointer analyses are accurate on at least 95% of the weighted alias queries as well.
We then examine whether scalable pointer analyses are inaccurate on the remaining 5% alias queries because they are context-insensitive. To this end, we have developed a new context-sensitive pointer analysis that also serves as a general engine for tracing the flow of values in C programs. To our knowledge, it is the first technique for performing context-sensitive analysis with subtyping that scales to millions of lines of code. We find that the new algorithm does not identify fewer aliases than the context-insensitive analysis.
The full paper is available as a single PDF document. A suggested BibTeX citation record is also available.