Fast and Accurate Flow-Insensitive Points-To Analysis
Marc Shapiro and Susan Horwitz
University of Wisconsin
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 interprocedural analysis of stack-based storage.
The paper makes two contributions to work in this area:
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 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.
(Click here to access the paper.)