Introduction: The motivation for this study is to exploit the techniques that, in simple settings like matrix multiplication as in Section 11.2, were quite straightforward. In the more general setting, the same techniques apply, but they are far less intuitive. But by applying some linear algebra, we can make everything work in the general setting.
As discussed in Section 11.1.5, there are three kinds of spaces in our transformation model: iteration space, data space, and processor space. Here we start with the iteration space. The iteration space of a loop nest is defined to be all the combinations of loop-index values in the nest.
Often, the iteration space is rectangular, as in the matrix-multiplication example of Fig. 11.5. There, each of the nested loops had a lower bound of 0 and an upper bound of n — 1. However, in more complicated, but still quite realistic, loop nests, the upper and/or lower bounds on one loop index can depend on the values of the indexes of the outer loops. We shall see an example shortly.
Constructing Iteration Spaces from Loop Nests:To begin, let us describe the sort of loop nests that can be handled by thetechniques to be developed. Each loop has a single loop index, which we assumeis incremented by 1 at each iteration. That assumption is without loss ofgenerality, since if the incrementation is by integer c > 1, we can always replace uses of the index i by uses of ci a for some positive or negative constant a, and then increment i by 1 in the loop. The bounds of the loop should be written as affine expressions of outer loop indices.
Example: Consider the loop
f o r (i = 2; i <= 100; i = i 3)
Z [ i ] = 0;
which increments i by 3 each time around the loop. The effect is to set to 0 each of the elements Z, Z, Z [ 8 ] , . . . , Z. We can get the same effect with:
f o r (j = 0; j <= 32; j )
Z[3*j 2] = 0;
That is, we substitute 3j 2 for i. The lower limit i = 2 becomes j = 0 (just solve 3j 2 = 2 for j ) , and the upper limit i < 100 becomes j < 32 (simplify 3j 2 < 100 to get j < 32.67 and round down because j has to be an integer). Typically, we shall use for-loops in loop nests. A while-loop or repeat-loop can be replaced by a for-loop if there is an index and upper and lower bounds for the index, as would be the case in something like the loop of Fig. 11.9(a). A for-loop like f o r (i=0; i<100; i ) serves exactly the same purpose.
However, some while- or repeat-loops have no obvious limit. For example, Fig. 11.9(b) may or may not terminate, but there is no way to tell what condition on i in the unseen body of the loop causes the loop to break. Figure 11.9(c) is another problem case. Variable n might be a parameter of a function, for example. We know the loop iterates n times, but we don't know what n is at compile time, and in fact we may expect that different executions of the loop will execute different numbers of times. In cases like (b) and (c), we must treat the upper limit on i as infinity.
A <i-deep loop nest can be modeled by a dl-dimensional space. The dimensions are ordered, with the kth dimension representing the kth nested loop, counting from the outermost loop, inward. A point (xi,x2,... ,Xd) in this space represents values for all the loop indexes; the outermost loop index has value xi, the second loop index has value x2, and so on. The innermost loop index has value x&.
But not all points in this space represent combinations of indexes that actually occur during execution of the loop nest. As an affine function of outer loop indices, each lower and upper loop bound defines an inequality dividing the iteration space into two half spaces: those that are iterations in the loop (the positive half space), and those that are not (the negative half space). The conjunction (logical AND) of all the linear equalities represents the intersection of the positive half spaces, which defines a convex polyhedron, which we call the iteration space for the loop nest. A convex polyhedron has the property that if two points are in the polyhedron, all points on the line between them are also in the polyhedron. All the iterations in the loop are represented by the points with integer coordinates found within the polyhedron described by the loop-bound inequalities. And conversely, all integer points within the polyhedron represent iterations of the loop nest at some time.
f o r (i = 0; i <= 5; i )
f o r (j = i ; j <= 7; j )
Z [ j , i ] = 0;
Figure 11.10: A 2-dimensional loop nest