## Transfer Functions for the Constant-Propagation Framework

**Introduction:** We assume in the following that a basic block contains only one statement. Transfer functions for basic blocks containing several statements can be constructed by composing the functions corresponding to individual statements. The set F consists of certain transfer functions that accept a map of variables to values in the constant lattice and return another such map. F contains the identity function, which takes a map as input and returns the same map as output.

F also contains the constant transfer function for the ENTRY node. This transfer function, given any input map, returns a map mo, where mo(v) = UNDEF, for all variables v. This boundary condition makes sense, because before executing any program statements there are no definitions for any variables.

In general, let fs be the transfer function of statement s, and let m and m' represent data-flow values such that m' = f(m). We shall describe /s in terms of the relationship between m and m'.

1. If s is not an assignment statement, then fs is simply the identity function.

2. If s is an assignment to variable x, then m'(v) = m(v), for all variables v ^ x, provided one of the following conditions holds:

a. If the right-hand-side (RHS) of the statement s is a constant c, then m'(x) = c.

b. If the RHS is of the form y z, then

c. If the RHS is any other expression (e.g. a function call or assignment through a pointer), then m'(x) = NAC.

**Nondistributivity of the Constant-Propagation Framework: **The constant-propagation framework as defined is monotone but not distributive. That is, the iterative solution MFP is safe but may be smaller than the MOP solution. An example will prove that the framework is not distributive.

**Example**: In the program in Fig. 9.27, *x *and *y *are set to 2 and 3 in block *Bi, *and to 3 and 2, respectively, in block *B2. *We know that regardless of which path is taken, the value of *z *at the end of block *B3 *is 5. The iterative algorithm does not discover this fact, however. Rather, it applies the meet operator at the entry of *B3, *getting **NAC'S **as the values of *x *and *y. *Since adding two **NAC**'s yields a NAC, the output produced by Iterative Algorithm is that z — NAC at the exit of the program. This result is safe, but imprecise. Iterative Algorithm is imprecise because it does not keep track of the correlation that whenever x is 2, y is 3, and vice versa. It is possible, but significantly more expensive, to use a more complex framework that tracks all the possible equalities that hold among pairs of expressions involving the variables in the program. Theoretically, we can attribute this loss of precision to the nondistributivity of the constant propagation framework. Let / i , f2, and fa be the transfer functions representing blocks B\, B2 and B3, respectively. As shown in Fig 9.28, rendering the framework nondistributive.