3.12 Data dependency conflicts when vectorizing code

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. Detecting data dependencies involving arrays or pointers requires extensive analysis of the arrays used in each loop nest. It also involves 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 below, 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 result that differs from the result that is obtained without vectorization, so it is left in its original form.

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 the following example vectorizes because the nonvector subscripts of the references to array a can never be equal. They 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, so they do not share data.

float a[99][99], b[99], c[99];
int i, n;
...
for (i = 1; i < 99; i++) 
{
    a[n][i] = a[n+1][i-1] * b[i] + c[i];
}
Non-ConfidentialPDF file icon PDF versionARM DUI0472M
Copyright © 2010-2016 ARM Limited or its affiliates. All rights reserved.