PRECISE INTERPROCEDURAL DATA-FLOW ANALYSIS WITH APPLICATIONS TO CONSTANT PROPAGATION

This paper concerns interprocedural dataflow-analysis problems in whic h the dataflow information at a program point is represented by an env ironment (i.e., a mapping from symbols to values), and the effect of a program operation is represented by a distributive environment transf ormer. We present two efficient algorithms that produce precise soluti ons: an exhaustive algorithm that finds values for all symbols at all program points, and a demand algorithm that finds the value for an ind ividual 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 propagati on and linear-constant propagation. The former interprets program stat ements of the form x := 7 and x := y. The latter also interprets state ments of the form x := 5 y + 17. Experimental results on C programs have shown that Although solving constant-propagation problems precise ly (i.e., finding the meet-over-all-valid-paths solution, rather than the meet-over-all-paths solution) resulted in a slowdown by a factor r anging from 2.2 to 4.5, the precise algorithm found additional constan ts in 7 of 38 test programs. In contrast to previous results for numer ic Fortran programs, linear-constant propagation found more constants than copy-constant propagation in 6 of 38 test programs. The demand al gorithm, when used to demand values for all uses of scalar integer var iables, was faster than the exhaustive algorithm by a factor ranging f rom 1.14 to about 6.