3.4.2. Data dependencies

A loop that has results from one iteration feeding back into a future iteration of the same loop is said to have a data dependency conflict. The conflicting values might be array elements or a scalar such as an accumulated sum.

Loops containing data dependency conflicts might not be completely optimized. To detect data dependencies involving arrays and/or pointers requires extensive analysis of the arrays used in each loop nest, and examination of the offset and stride of accesses to elements along each dimension of arrays that are both used and stored in a loop. If there is a possibility of the usage and storage of arrays overlapping on different iterations of a loop, then there is a data dependency problem. A loop cannot be safely vectorized if the vector order of operations can change the results. In these cases, the compiler detects the problem and leaves the loop in its original form or carries out a partial vectorization of the loop. This type of data dependency must be avoided in your code to achieve the best performance.

In the loop shown in the Example 3.3, the reference to a[i-2] at the top of the loop conflicts with the store into a[i] at the bottom. Performing vectorization on this loop gives a different result, and so it is left in its original form.

Example 3.3.  Non vectorizable data dependency

float a[99], b[99], t;
int i;
for (i = 3; i < 99; i++)
    t = a[i-1] + a[i-2];
    b[i] = t + 3.0 + a[i];
    a[i] = sqrt(b[i]) - 5.0;

Information from other array subscripts is used as part of the analysis of dependencies. The loop in Example 3.4 vectorizes because the non vector subscripts of the references to array a can never be equal, because n is not equal to n+1, and so gives no feedback between iterations. The references to array a use two different pieces of the array and so, do not share data.

Example 3.4.  Vectorizable data dependency

float a[99][99], b[99][99], c[99];
int i, n, m;
for (i = 1; i < m; i++) a[n][i] = a[n+1][i-1] * b[i] + c[i];

Copyright © 2007 ARM Limited. All rights reserved.ARM DUI 0350A