8.4 Unroll-and-Jam

We now return to a version of the example of Figure 8.1:

    DO I = 1, N * 2       DO J = 1, M          A(I) = A(I) + B(J)       ENDDO    ENDDO

Scalar replacement will do an excellent job of minimizing the references to A based on the dependences carried by the inner loop. However, there is also an input dependence on B carried by the outer loop. It is possible to extract some reuse from that dependence as well.

As the loop is currently structured, it is unlikely that we can achieve any reuse, because a particular value of B(J) must stay in a register throughout the iteration of the J-loop until the next iteration of the I-loop. Since N the number of iterations of the J-loop is unknown, we must assume that any given machine will not have enough registers to get much reuse for B. However, if we make a simple transformation, called unroll-and-jam, we can bring pairs of iterations closer together:

    DO I = 1, N * 2, 2       DO J = 1, M          A(I) = A(I) + B(J)          A(I+1) =...