Precise Interprocedural Dataflow Analysis
with Applications to Constant Propagation
Mooly Sagiv, Thomas Reps, and Susan Horwitz
This paper concerns interprocedural dataflow-analysis problems in
which the dataflow information at a program point is represented by an
environment (i.e., a mapping from symbols to values), and the effect
of a program operation is represented by a distributive environment
transformer. We present two efficient algorithms that produce precise
solutions: an exhaustive algorithm that finds values for all symbols
at all program points, and a demand algorithm that finds the value for
an individual symbol at a particular program point.
Two interesting problems that can be handled by our algorithms are
(decidable) variants of the interprocedural constant-propagation
problem: copy-constant propagation and linear-constant
propagation. The former interprets program statements of the form
x := 7 and x := y.
The latter also interprets statements of the form x := 5 * y + 17.
Experimental results on C programs have shown that
(Click here to access the paper:
PostScript,
PDF.)
University of Wisconsin