Interprocedural aliasing in the presence of pointers

An Alias occurs at some program point during execution when two or more names exist for the same location. We've investigated the theoretical difficulty of determining the aliases of a program, developed an approximation algorithm for solving for aliases in C like languages, and explored the precision (i.e., closeness of our approximate solution to the actual solution) and time behavior of this algorithm. Myers explored the theoretical difficulty of solving flow sensitive interprocedural data flow problems in the presence of aliasing. However, he did not make any claims about the difficulty of determining aliases. We isolate various programming language mechanisms that create aliases. The complexity of the alias problem (i.e., determining the aliases for a program) induced by each mechanism and their combinations is considered separately and categorized as NP-hard, complement NP-hard, or polynomial time (P). We proved that if there are two (or more) levels of indirection, regardless of the alias mechanisms used, aliasing is NP-hard. However, if only one level of indirection is possible, then the alias problem is in P. In addition, we show the alias problem in the presence of some mechanisms to be P-space complete. Therefore, in a language which allows general purpose pointers, the problem of determining which aliases can occur during program execution is NP-hard. We present an algorithm which safely approximates Interprocedural May Alias (i.e., we fail to report an alias only if it never occurs) in the presence of pointers. We are able to show, relative to our definition of precision, that our algorithm is as precise as possible in the worst case. We also pinpoint the sources of imprecision in our algorithm and can empirically bound its precision. Our algorithm has been implemented in a prototype analysis tool for C programs, and we present a preliminary empirical investigation of algorithm speed and precision.