Loop dependencies are data dependencies that may constrain optimization of loops, typically pipelining. They can be within a single iteration of a loop and or between different iterations of a loop.
The easiest way to understand loop dependencies is to examine an extreme example. In the following example, the result of the loop is used as the loop continuation or exit condition. Each iteration of the loop must finish before the next can start.
Minim_Loop: while (a != b) {
if (a > b)
a -= b;
else
b -= a;
}
This loop cannot be pipelined. The next iteration of the loop cannot begin until the previous iteration ends. Not all loop dependencies are as extreme as this, but this example highlights that some operations cannot begin until some other operation has completed. The solution is to try to ensure that the initial operation is performed as early as possible.
Loop dependencies can occur with any and all types of data. They are particularly common when using arrays.