Loop-carried dependences...cont'd

Next: Definition: Up: Dependence Previous: ...

What is a loop-carried dependence?

Consider two iterations I₁ and I₂
A dependence occurs between two statements S_p and S_q (not necessarily distinct), when an assignment in S_p^I₁ refers to the same location as a use in S_q^I₂
In the example,
$\fbox{\begin{minipage}{6em}{\tt\begin{tabbing} $S_1:$\space \= A[0] := 0\\ \> ... ... 1 to 5\\ $S_2:$\space \> ~ A[I] := A[I-1] + B[I] \end{tabbing}}\end{minipage}}$
- The assignment is ``A[I₁] := ...''
- The use is ``... := A[I₂-1] ...''
- These refer to the same location when I₁ = I₂-1
- Thus I₁ < I₂, ie the assignment is in an earlier iteration
Notation: $S_2 ~\delta_{<}~ S_2$