Tech Report CS-89-36

Constant Propagation with Conditional Branches

Mark N. Wegman and Kenneth Zadeck

May 1989


Constant propagation is a well-known global flow analysis problem. The goal of constant propagation is to discover values that are constant on all possible executions of a program and to propagate these constant values as far forward through the program as possible. Expressions whose operands are all constants can be evaluated at compile time and the results propagated further. The use of the algorithms presented in this paper can result in compiled programs that are smaller and faster. The same algorithms can be used for other kinds of analyses (e.g. type determination).

We present four algorithms in this paper, all {\it conservative} in the sense that all constants may not be found, but each constant found is constant over all possible executions of the program. These algorithms are among the simplest, fastest, and most powerful global constant propagation algorithms known.

A new algorithm is also presented that performs a form of interprocedural data flow analysis in which aliasing information is gathered in conjunction with constant propagation. Several variants of this algorithm are considered.

(complete text in pdf)