37 Iterative Data Flow Analysis
Rajeswari Sridhar
In this module, we would learn to compute the in ( ) and out( ) of the data flow equation component for reaching definitions. We will discuss the algorithm for computing the data flow equations. In addition, we will also discuss to compute the list of available expressions and live-variables.
37.1Iterative solution to data-flow equations
As we have already discussed in the previous module, our aim is to find out the out[] of all the statements so as to help in code optimization. The approach to the computation is to calculate the in() and out() simultaneously for each node of the flow graph. Gen() and kill() are computed in essentially the same manner. The previous module talked about forward equations which calculates out ( ) based on in( ). In this module, an algorithm is discussed which is based on a backward equation wherein in() is computed assuming out() and again out() is computed based on the new in(). We also make use of a confluence operator, “Union” function which computes the union of all definitions reaching a point.
We discuss the algorithm for computing reaching definition and is discussed in Algorithm 37.1
Algorithm 37.1 Iterative algorithm – Reaching Definitions
The idea behind the algorithm is discussed below:
• in[B] = U out[P] for all P being a predecessor of B
• out [B] = gen [B] U {in[B] – kill [B]}
• We try to solve a flow graph with ‘n’ blocks having ‘2n’ equations assuming they are recurrences
Compute_ReachingDefinitions( ) Input: A flow graph for which kill[B] and gen[B] have been computed
Output: in[B] and out[B] for each block B
Approach: in[B1] is Φ for all B and converging to the desired values of in[] and out[]. Initialize in[B] = Φ for all blocks B
{
a. for each block B
i. out[B] = gen[B]
b. change := true
c. while change
change := false
for each block B
1. in[B] = U out[P] where P is a predecessor
2. oldout = out[B]
- out[B] = gen[B] U {in[B] – kill[B]};
- if out[B] ≠ oldout then change := true
end
end
}
Algorithm 37.1 discusses the computation of reaching definitions. The input to this algorithm is gen[] and kill[] functions. The algorithm initializes in[] of all block to {} and the first line of the algorithm initializes out[] of all blocks to gen[] and will be revised in subsequent iterations. A flag variable ‘change’ is used to keep track of the number of passes by comparing the result of the out[] of each block that is computed in adjacent iterations. The algorithm loops through where the in[] of every block is computed as the union of all the out[] of its predecessor blocks. As the out[] value changes in subsequent iterations, the in[] of the blocks will also vary thus resulting in a possibility for a new out[] value for each block.
The sequence of definitions as given in the previous module is converted to a flow graph and we identify four blocks here and the representation is shown in figure 37.1. Figures 37.2 and 37.3 shows the computation of gen[] and kill[] of these statements using the procedure already discussed in the previous module. The result is reproduced here for convenience. The input to the reaching definitions computation algorithm is this graph or the bit vector values of each statement.
end
end
}
Algorithm 37.2 discusses the algorithm for available expressions. This again uses the flag variable for making it go through multiple passes. Again using the data flow equations we compute the available expressions.
37.3 Live-Variable analysis
For live- variable analysis, determine whether for any 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 ‘x’ is used then, ‘x’ is live at ‘p’ else ‘x’ is dead at ‘p’. For computing the live-variable analysis the following definitions are used”
• in[B] – set of variables live at the point immediately before block B
• Out[B] – same at the point immediately after the block
• Def[B] – definitely assigned values in B prior to any use of that variable in B
• Use[B] – set of variables whose values may be used in B prior to definition of the variable
Here we compute in[] based on use[], out[] and def[] which is defined as follows:
in[B] = use[B] U {out[B] – def[B]}
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 defined in the block. However, out[] of any block is computed using the following equation:
• out[B] = U in[S] for all S being successor of B
We say that a variable is live coming out of a block if and only if, it is live coming into one of its successors. Algorithm 37.3 gives the computation of live variable analysis.
Algorithm 37.3
Compute_Livevariable()
Input: A flow graph with def and use computed for each block
Output: out[B] – the set of variable live on exit from each block B
{
for each block B do in[B] = Φ
while changes to any of the in’s occur do
for each block B do begin
out[B] = U in [S]
in[B] := use[B] U (out[B] – def[B])
The algorithm 37.4 is used for the computation of use[ ] and def [ ].
Algorithm 37.4
Compute_use_and_def()
{
for each basic block BB do
def[B] = Φ ;
use[B] = Φ ;
for each statement (x := y op z) in sequential order, do for each operand y, do
if (y not in def[B])
use[B] = use[B] U {y};
end for
def[B] = def[B] U {x};
endfor
}
