Data-Flow Problem Formulation
Introduction: This analysis finds affine expressions of reference variables introduced (1) to count the number of iterations executed in each loop, and (2) to hold values at the entry of regions where necessary. This analysis also finds induction variables, loop invariants, as well as constants, as degenerate affine expressions. Note that this analysis cannot find all constants because it only tracks affine expressions of reference variables.
Data - Flow Values: Symbolic Maps: The domain of data-flow values for this analysis is symbolic maps, which arefunctions that map each variable in the program to a value. The value is eitheran affine function of reference values, or the special symbol NAA to representa non-afflne expression. If there is only one variable, the bottom value of thesemilattice is a map that sends the variable to NAA. The semi lattice for nvariables is simply the product of the individual semilattices. We use m N A A todenote the bottom of the semi lattice which maps all variables to NAA. We candefine the symbolic map that sends all variables to an unknown value to be thetop data-flow value, as we did for constant propagation. However, we do notneed top values in region-based analysis.
Example: The symbolic maps associated with each block for the code in Example 9.58 are shown in Figure 9.58. We shall see later how these maps are discovered; they are the result of doing region-based data-flow analysis on the flow graph of Fig. 9.56.
The symbolic map associated with the entry of the program is mN A A . At the exit of Bi, the value of a is set to 0. Upon entry to block _B2, a has value 0 in the first iteration and increments by one in each subsequent iteration of the outer loop. Thus a has value i — 1 at the entry of the ith iteration and value i at the end. The symbolic map at the entry of B2 maps variables 6, c, d to NAA, because the variables have unknown values on entry to the inner loop.
Their values depend on the number of iterations of the outer loop, so far. The symbolic map on exit from B2 reflects the assignment statements to a, b, and c in that block. The rest of the symbolic maps can be deduced in a similar manner. Once we have established the validity of the maps in Fig.
Transfer Function of a Statement: The transfer functions in this data-flow problem send symbolic maps to symbolicmaps. To compute the transfer function of an assignment statement, weinterpret the semantics of the statement and determine if the assigned variablecan be expressed as an affine expression of the values on the right of the assignment. The values of all other variables remain unchanged.