## Constant Propagation

**Introduction:** All the data-flow schemas discussed in Section 9.2 are actually simple examples of distributive frameworks with finite height. Thus, the iterative Algorithm 9.25 applies to them in either its forward or backward version and produces the MOP solution in each case. In this section, we shall examine in detail a useful dataflow framework with more interesting properties. Recall that constant propagation, or "constant folding," replaces expressions that evaluate to the same constant every time they are executed, by that constant.

The constant-propagation framework described below is different from all the data-flow problems discussed so far, in that

a) it has an unbounded set of possible data-flow values, even for a fixed flow graph, and

b) it is not distributive.

Constant propagation is a forward data-flow problem. The semilattice representing the data-flow values and the family of transfer functions are presented next.

**Data-Flow Values for the Constant-Propagation Framework**

The set of data-flow values is a product lattice, with one component for each variable in a program. The lattice for a single variable consists of the following:

1. All constants appropriate for the type of the variable.

2. The value NAC, which stands for not-a-constant. A variable is mapped to this value if it is determined not to have a constant value. The variable may have been assigned an input value, or derived from a variable that is not a constant, or assigned different constants along different paths that lead to the same program point.

3. The value UNDEF, which stands for undefined. A variable is assigned this value if nothing may yet be asserted; presumably, no definition of the variable has been discovered to reach the point in question.

Note that NAC and UNDEF are not the same; they are essentially opposites. NAC says we have seen so many ways a variable could be defined that we know it is not constant; UNDEF says we have seen so little about the variable that we cannot say anything at all.

The semilattice for a typical integer-valued variable is shown in Fig. 9.25. Here the top element is UNDEF, and the bottom element is NAC. That is, the greatest value in the partial order is UNDEF and the least is NAC. The constant values are unordered, but they are all less than UNDEF and greater than NAC. As discussed in Section 9.3.1, the meet of two values is their greatest lower bound. Thus, for all values v,

UNDEF A v = v and NAC A v = NAC.

For any constant c,

c A c = c

and given two distinct constants c\ and c2,

d A c 2 = NAC.

A data-flow value for this framework is a map from each variable in the program to one of the values in the constant semilattice. The value of a variable v in a map m is denoted by m(v).

**The Meet for the Constant-Propagation Framework**: The semilattice of data-flow values is simply the product of the semilattices like Fig. 9.25, one for each variable. Thus, m < m' if and only if for all variables v we have m(v) < m'(v). Put another way, mAm' = m" if m"(v) = m(v)Am'(v) for all variables v.