## Live-Variable Analysis

**Introduction:** Some code-improving transformations depend on information computed in the direction opposite to the flow of control in a program; we shall examine one such example now. In live-variable analysis we wish to know for variable x and point p whether the value of x at p could be used along some path in the flow graph starting at p. If so, we say x is live at p; otherwise, x is dead at p.

An important use for live-variable information is register allocation for basic blocks. Aspects of this issue were introduced in Sections 8.6 and 8.8. After a value is computed in a register, and presumably used within a block, it is not necessary to store that value if it is dead at the end of the block. Also, if all registers are full and we need another register, we should favor using a register with a dead value, since that value does not have to be stored.

Here, we define the data-flow equations directly in terms of IN[5] and OUTpB], which represent the set of variables live at the points immediately before and after block B, respectively. These equations can also be derived by first defining the transfer functions of individual statements and composing them to create the transfer function of a basic block. Define

1. defB as the set of variables defined (i.e., definitely assigned values) in B prior to any use of that variable in B, and

2. useB as the set of variables whose values may be used in B prior to any definition of the variable.

**Example**: For instance, block B2 in Fig. 9.13 definitely uses i. It also uses j before any redefinition of j, unless it is possible that i and j are aliases of one another. Assuming there are no aliases among the variables in Fig. 9.13, then uses2 = {i,j}- Also, B2 clearly defines i and j. Assuming there are no aliases, defB2 = as well.

As a consequence of the definitions, any variable in useB must be considered live on entrance to block B, while definitions of variables in defB definitely are dead at the beginning of B. In effect, membership in defB "kills" any opportunity for a variable to be live because of paths that begin at B. Thus, the equations relating def and use to the unknowns IN and OUT are defined as follows:

IN [EXIT] = 0

and for all basic blocks B other than EXIT

The first equation specifies the boundary condition, which is that no variables are live on exit from the program. The second equation says that a variable is live coming into a block if either it is used before redefinition in the block or it is live coming out of the block and is not redefined in the block. The third equation says that a variable is live coming out of a block if and only if it is live coming into one of its successors.

The relationship between the equations for liveness and the reaching-definitions equations should be noticed:

Ø Both sets of equations have union as the meet operator. The reason is that in each data-flow schema we propagate information along paths, and we care only about whether any path with desired properties exist, rather than whether something is true along all paths.

Ø However, information flow for liveness travels "backward," opposite to the direction of control flow, because in this problem we want to make sure that the use of a variable x at a point p is transmitted to all points prior to p in an execution path, so that we may know at the prior point that x will have its value used.

To solve a backward problem, instead of initializing OUT[ENTRY] , we initialize IN [EXIT]. Sets IN and O U T have their roles interchanged, and use and def substitute for gen and kill, respectively. As for reaching definitions, the solution to the liveness equations is not necessarily unique, and we want the solution with the smallest sets of live variables. The algorithm used is essentially a backwards version of Algorithm 9.11.

**Algorithm:** Live-variable analysis.

**INPUT**: A flow graph with def and use computed for each block.

**OUTPUT**: m[B] and O U T [ £ ] , the set of variables live on entry and exit of each block B of the flow graph.

**METHOD**: Execute the program in Fig. 9.16.

IN [EXIT] = 0;

for (each basic block B other than EXIT) IN [B] = 0;

while (changes to any IN occur)

for (each basic block B other than EXIT) {

O U T [ £ ] = Us a successor of B

m[B] = useBU (bUTpB] - defB);

}

**Figure 9.16: Iterative algorithm to compute live variables**