Region-Based Symbolic Analysis
Introduction: We can extend the region-based analysis described in Section 9.7 to find expressions of variables in the ith. Iteration of a loop. A region-based symbolic analysis has a bottom-up pass and a top-down pass, like other region-based algorithms. The bottom-up pass summarizes the effect of a region with a transfer function that sends a symbolic map at the entry to an output symbolic map at the exit. In the top-down pass, values of symbolic maps are propagated down to the inner regions.
The difference lies in how we handle loops. In Section 9.7, the effect of a loop is summarized with a closure operator. Given a loop with body /, its closure /* is defined as an infinite meet of all possible numbers of applications of /. However, to find induction variables, we need to determine if a value of a variable is an affine function of the number of iterations executed so far. The symbolic map must be parameterized by the number of the iteration being executed. Furthermore, whenever we know the total number of iterations executed in a loop, we can use that number to find the values of induction variables after the loop. For instance, in Example 9.58, we claimed that a has the value of i after executing the ith iteration. Since the loop has 100 iterations, the value of a must be 100 at the end of the loop.
In what follows, we first define the primitive operators: meet and composition of transfer functions for symbolic analysis. Then show how we use them to perform region-based analysis of induction variables.
Meet of Transfer Functions: When computing the meet of two functions, the value of a variable is NAA unlessthe two functions map the variable to the same value and the value is not NAA.Thus,
Parameterized Function Compositions: To express a variable as an affine function of a loop index, we need to compute the effect of composing a function some given number of times. If the effect of one iteration is summarized by transfer function /, then the effect of executing i iterations, for some i > 0, is denoted /\ Note that when i = 0, fl = f° = I, the identify function.
Variables in the program are divided into three categories:
1. If f(m)(x) = m(x) c, where c is a constant, then fl(m)(x) — m(x) ci for every value of i > 0. We say that a: is a basic induction variable of the loop whose body is represented by the transfer function /.
2. If f(m)(x) = m(x), then fl(m)(x) = m(x) for all i > 0. The variable x is not modified and it remains unchanged at the end of any number of iterations through the loop with transfer function /. We say that x is a symbolic constant in the loop.
3. l£f(m)(x) = co cim(xi)-\ \-cnm(xn), where each xk is either a basic induction variable or a symbolic constant, then for i > 0,
4. We say that x is also an induction variable, though not a basic one. Note that the formula above does not apply if i = 0.
5. In all other cases, fl(m)(x) = NAA. To find the effect of executing a fixed number of iterations, we simply replace i above by that number. In the case where the number of iterations is unknown, the value at the start of the last iteration is given by /*. In this case, the only variables whose values can still be expressed in the affine form are the loop invariant variables.
A Region-Based Algorithm
Algorithm: Region-based symbolic analysis.
INPUT: A reducible flow graph G.
OUTPUT: Symbolic maps IN[B] for each block B of G.
METHOD: We make the following modifications to Algorithm 9.53.
1. We change how we construct the transfer function for a loop region. In the original algorithm we use the /#,IN[.S] transfer function to map the symbolic map at the entry of loop region R to a symbolic map at the entry of loop body S after executing an unknown number of iterations. It is defined to be the closure of the transfer function representing all paths leading back to the entry of the loop, as shown in Fig. 9.50(b). Here we define /jy,iN[S] t° represent the effect of execution from the start of the loop region to the entry of the ith. iteration. Thus, fR,i,IN[S) = ( A /s.OUTpS]) predecessors B in R of the header of S
2. If the number of iterations of a region is known, the summary of the region is computed by replacing i with the actual count.
3. In the top-down pass, we compute /jjtk)iN[B] to find the symbolic map associated with the entry of the ith iteration of a loop.
4.In the case where the input value of a variable m(v) is used on the righthand- side of a symbolic map in region R, and m(v) = NAA upon entry to thexregion, we introduce a new reference variable t, add assignment t = v to the beginning of region R, and all references of m(v) are replaced by t. If we did not introduce a reference variable at this point, the NAA value held by v would penetrate into inner loops.