O-line variable substitution for scaling points-to analysis

Most compiler optimizations and software productivity tools rely on information about the eects of pointer dereferences in a program. The purpose of points-to analysis is to com-pute this information safely, and as accurately as is practical. Unfortunately, accurate points-to information is dicult to obtain for large programs, because the time and space re-quirements of the analysis become prohibitive. We consider the problem of scaling flow- and context-insensi-tive points-to analysis to large programs, perhaps contain-ing hundreds of thousands of lines of code. Our approach is based on a variable substitution transformation, which is performed o-line, i.e., before a standard points-to analy-sis is performed. The general idea of variable substitution is that a set of variables in a program can be replaced by a single representative variable, thereby reducing the input size of the problem. Our main contribution is a linear-time algorithm which nds a particular variable substitution that maintains the precision of the standard analysis, and is also very eective in reducing the size of the problem. We report our experience in performing points-to analysis on large C programs, including some industrial-sized ones. Experiments show that our algorithm can reduce the cost of Andersen’s points-to analysis [2] substantially: on average, it reduced the running time by 53 % and the memory cost by 59%, relative to an ecient baseline implementation of the analysis.