language: en

Fast and Accurate Flow-Insensitive Points-To Analysis

Marc Shapiro and Susan Horwitz
Computer Sciences Department, University of Wisconsin-Madison
1210 West Dayton Street, Madison, WI 53706 USA
Electronic mail: {mds, horwitz}@cs.wisc.edu

Abstract In order to analyze a program that involves pointers, it is necessary to have (safe) information about what each pointer points to. There are many different approaches to computing points-to information. This paper addresses techniques for flow- and context-insensitive in-terprocedural analysis of stack-based storage. The paper makes two contributions to work in this area: * The first contribution is a set of experiments that explore the trade-offs between techniques previously defined by Lars Andersen and Bjarne Steens-gaard. The former has a cubic worst-case running time, while the latter is essentially linear. However, the former may be much more precise than the latter. We have found that in practice, Ander-sen's algorithm is consistently more precise than Steensgaard's. For small programs, there is very little difference in the times required by the two approaches; however, for larger programs, Ander-sen's algorithm can be much slower than Steens gaard's. * The second contribution is the definition of two new algorithms. The first algorithm can be "tuned" so that its worst-case time and space requirements, as well as its accuracy range from those of Steens-gaard to those of Andersen. We have experimented with several versions of this algorithm; one version provided a significant increase in accuracy over Steensgaard's algorithm, while keeping the running time within a factor of two. The second algorithm uses the first as a subroutine. Its worst-case time and space requirements are a factor of log N (where N is the number of variables in the program) worse than those of Steensgaard's algorithm. In practice, it appears to

[This work was supported in part by the National Science Foundation under grant CCR-8958530, and by the Defense Advanced Research Projects Agency under ARPA Order No. 8856 (monitored by the Office of Naval Research under contract N00014-92-J-1937).]

run about ten times slower than Steensgaard's algorithm; however it is significantly more accurate than Steensgaard's algorithm, and significantly faster than Andersen's algorithm on large programs.

1 Introduction