Practical Pointer Aliasing Analysis

Two names are aliased if they refer to the same location at a program point during execution. Pointer aliasing analysis for C programs is essential for compile-time analyses and optimizations. Many techniques have been proposed in the literature. Some are fast, but not so precise; some are quite precise, but not fast in some cases. We have developed a technique which decomposes program statements into independent sets in terms of their effects on pointer aliasing. Each set implies a program segment which includes the statements in the set and some control statements. Each segment can be analyzed for pointer aliasing independently. Therefore the program decomposition allows the use of more than one analysis algorithm on a same program and the use of appropriate aliasing analyses based on characteristics of pointers being analyzed. We handle features in C such as function pointers, indirect calls through functions pointers, unions, and type casting with some restrictions. We have also developed a points-to analysis algorithm and an aliasing analysis algorithm. Both are ow-insensitive and context-insensitive; thus they are efficient and can be used on large programs. For each assignment lhs=rhs in a program, the aliasing analysis effectively assumes there is also an assignment rhs=lhs while the points-to analysis does not make such assumptions. Therefore the points-to analysis is more precise than the aliasing analysis. ii We have implemented prototypes of the program decomposition, the points-to and the aliasing analysis algorithms; empirical results on a set of C programs are given. We have also experimented with combining two or more aliasing/points-to analyses for a same program by using the program decomposition; we present empirical results of our preliminary experiment.