Interprocedural Pointer Analysis for C

Abstract

Many powerful code optimization techniques rely on accurate information connecting the definitions and uses of values in a program. This information is difficult to produce for programs written with pointer-based languages such as C. For values in memory locations, accurate information is difficult to obtain at call sites and pointer-based memory operations. Most compilers conservatively assume that call sites and pointer-based operations may access any memory location. This greatly weakens the effectiveness of many optimizations and leaves opportunities for improvement. This dissertation examines how to implement an interprocedural pointer analyzer for C in order to provide more accurate information about which memory locations call sites and pointer-based memory operations may access. The key issues of pointer analysis versus alias analysis, modeling of call sites, modeling of the heap, and usage of interprocedural path information are discussed. Solutions given for the first two questions and various solutions for the last two questions were used to build pointer analyzers of varying power and complexity. All versions of the analyzer were tested over a suite of programs, and we demonstrate that pointer analysis for programs of about 30K lines can easily be done with the computational power of current machines. The resulting pointer-analyzed programs were tested, and we show that their performance is better than non-analyzed programs. The data for each analyzers' performance and each analyzed programs' performance was used to look at the trade-offs among analysis time, analysis accuracy, and performance of the analyzed code. These results were also compared with interprocedural MOD/REF analysis. We also show that the analyzer can speed up the execution times of the rest our optimizer. Anew optimization, register promotion, that was specifically designed to use the information generated by pointer analysis was also developed. Register promotion moves a variable that normally resides in memory to a register for portions of the code in which it is safe to do so. Our experimental results for register promotion show that it is effective in reducing memory traffic.