Precise Interprocedural Dataflow Analysis with Applications to Constant Propagation

Mooly Sagiv, Thomas Reps, and Susan Horwitz
University of Wisconsin

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.)