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 first contribution is a set of experiments that explore the
trade-offs between techniques previously defined by Lars Andersen
and Bjarne Steensgaard.
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, Andersen'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, Andersen's algorithm can be much slower than Steensgaard'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
Steensgaard 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 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.)