7.1 Introduction

To this point in the book, we have focused on transformations of programs that have no control flow other than loops. In other words, we have ignored the problems created by conditional branches. These problems are extremely difficult to handle because control flow creates a new type of constraint on program transformations one that is not handled by data dependence.

To illustrate the execution constraints imposed by control flow, consider the following loop:

    DO 100 I = 1, NS<sub1       </sub>IF (A(I 1).GT.0.0) GOTO 100S<sub2          </sub>A(I) = A(I) + B(I) * C100    CONTINUE

If we consider only data dependences, we see that S ₁ has a loop-carried dependence upon S ₂, due to the reference to A and no other data dependences. As a result, data dependence alone would indicate that both statements could be vectorized. However, since we do not know how to vectorize an IF with a GOTO, we will implement that as a loop, yielding

S<sub2    </sub>A(1:N) = A(1:N) + B(1:N) * C    DO 100 I = 1, NS<sub1       </sub>IF (A(I 1).GT.0.0) GOTO 100100    CONTINUE

Here the loop with the IF statement must come after the vector statement because of the dependence from S ₂ to S ₁ in the original code.

It is easy to see that this code is incorrect. In the original version, statement S ₂ executes only on iterations where A(I 1) is greater than zero; in...