Introduction: The following algorithm solves a forward data-flow-analysis problem on a reducible flow graph, according to some framework that satisfies the assumptions of Section 9.7.4. Recall that / R J N ^ ' ] and /j^ouTps] refer to transfer functions that transform data-flow values at the entry to region R into the correct value at the entry of subregion R' and the exit of the exit block B, respectively.

Algorithm: Region-based analysis.

INPUT: A data-flow framework with the properties outlined in Section 9.7.4 and a reducible flow graph G.

OUTPUT: Data-flow values m[B] for each block B of G.

METHOD:

1.  Use Algorithm 9.52 to construct the bottom-up sequence of regions of G, say Ri, R2,... ,Rn, where Rn is the topmost region.

2.  Perform the bottom-up analysis to compute the transfer functions summarizing the effect of executing a region. For each region Ri, R2,... ,Rn, in the bottom-up order, do the following:

(a)    If R is a leaf region corresponding to block B, let /RJN[.B] — a nd / H ,OUT[B] = / B , the transfer function associated with block B.

(b)   If R is a body region, perform the computation of Fig. 9.50(a).

(c)    If R is a loop region, perform the computation of Fig. 9.50(b).

3. Perform the top-down pass to find the data-flow values at the beginning of each region.

(a)    w[Rn] = IN[ENTRY].

(b)   For each region R in {Ri,... Rn-i}, in the top-down order, compute

I N [ J R ] - / ^ J I N [ J R ] ( I N [ J R ' ] ) ,

where R' is the immediate enclosing region of R.

Let us first look at the details of how the bottom-up analysis works. In line (1) of Fig. 9.50(a) we visit the subregions of a body region, in some topological order. Line (2) computes the transfer function representing all the possible paths from the header of R to the header of S; then in lines (3) and (4) we compute the transfer functions representing all the possible paths from the header of R to the exits of R — that is, to the exits of all blocks that have successors outside S. Notice that all the predecessors B' in R must be in regions that precede S in the topological order constructed at line (1). Thus, /#(OUT[jB'] will have been computed already, in line (4) of a previous iteration through the outer loop.

For loop regions, we perform the steps of lines (1) through (4) in Fig. 9.50(b) Line (2) computes the effect of going around the loop body region S zero or more times. Lines (3) and (4) compute the effect at the exits of the loop after one or more iterations. In the top-down pass of the algorithm, step 3(a) first assigns the boundary condition to the input of the top-most region. Then if R is immediately contained in R', we can simply apply the transfer function /#'5IN[JR] to the data-flow value w[R'] to compute m[R]. •

1. for (each subregion S immediately contained in R, in topological order) {

2.  IR,W[S] = Apredecessors B in R of the header of S /fl.OUTps] 5

/* if S is the header of region R, then / R J N [S] is the

meet over nothing, which is the identity function */

3.  for (each exit block B in S)

4.    /R,OVT[B] - / s , O U T [ B ] 0 / R , I N [ S ];

}

(a)    Constructing transfer functions for a body region R

1.       let S be the body region immediately nested within R] that is,

S is R without back edges from R to the header of R;

2.       fR,W[S) = (Apredecessors B in R of the header of S /s,0UTp3]) 5

3.       for (each exit block B in R)

4.       /fl,OUT[B] = /s,OUTp3] ° /fl,IN[S];

b. Constructing transfer functions for a loop region R'

Figure 9.50: Details of region-based data-flow computations

Previous Next