The Limits of Alias Analysis for Scalar Optimizations

Rezaul Alam Chowdhury, Peter Djeu, Brendon Cahoon, Jim Burrill, and Kathryn S. McKinley

Proceedings of the 13th International Conference on Compiler Construction (CC 2004), Barcelona, Spain, pp. 24-38, 2004

In theory, increasing the precision of alias analysis should improve the results of compiler optimizations on C programs. This paper compares the effectiveness of several popular alias analyses on nine scalar optimizations. We include an analysis that assumes no aliases to establish a very loose upper bound on optimization opportunities. We statically measure the number of optimization opportunities in the Scale compiler for each analysis performed on thirty-six C programs. We find that, in practice, the precision of the alias analysis rarely inhibits these optimization opportunities. Previous work finds similarly that the increased precision of specific alias algorithms provide little benefit for scalar optimizations, and that simple static alias algorithms uncover almost all dynamically determined aliases. This paper, however, is the first to provide a static methodology that indicates that additional precision is unlikely to yield improvements for a wide set of optimizations. For clients with higher alias accuracy demands, this methodology can help pinpoint the cases where additional accuracy is needed.

Download (copyright restrictions may apply): PSPDF