Estimating the Impact of Scalable Pointer Analysis on Optimization

Manuvir Das, Ben Liblit, Manuel Fahndrich, Jakob Rehof

To appear at Static Analysis Symposium (SAS01), Paris, France, 16-18 July 2001


Abstract

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 the 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 analyses are accurate on at least 95\% of the weighted alias queries as well. We also examine whether scalable pointer analyses produce less precise alias information because they are context-insensitive. We present a new context-sensitive pointer analysis that is also a general engine for tracing the flow of values in programs. To our knowledge, it is the first technique for performing context-sensitive analysis with subtyping on millions of lines of code. We show that the new algorithm does not identify fewer aliases than the context-insensitive analysis.


Server START Conference Manager
Update Time 31 Mar 2001 at 16:55:39
Maintainer sas01@ens.fr.
Start Conference Manager
Conference Systems