How to get Visual C++ to vectorize this loop (error code 1200)?

Question

I'm trying to have VC++ 2012 auto-vectorize a loop that looks a bit like this (there are actually interesting computations going on, but they're elided for the purpose of making the question as to the point as possible).

parameters:
int period;
unsigned char* out_array;
unsigned char* in_array1;
unsigned char* in_array2;
unsigned char* in_array3;

for (int x = 0; x < width; ++x)
{
   int index = period * (x / 2);

   out_array[0] = in_array1[x];
   out_array[1] = in_array2[index];
   out_array[2] = in_array3[index];
   out_array += 4;
}

I thought the only thing standing in the way of vectorizing was out_array += 4, so I made an inner "unrolled" loop, hoping at least that one could be vectorized:

for (int x = 0; x < width; ++x)
{
   for (int xx = 0; xx < 4; ++xx)
   {
       int index = period * ((xx + x) / 2);

       unsigned char* pout_array = out_array + (4 * xx);
       pout_array[0] = in_array1[xx + x];
       pout_array[1] = in_array2[index];
       pout_array[2] = in_array3[index];
   }
   out_array += 16;
}

But as I run the compiler with /Qvect-report:2, it is telling me the inner loop cannot be vectorized because of error code 1200. Error code 1200 states:

Loop contains loop-carried data dependences that prevent vectorization. Different iterations of the loop interfere with each other such that vectorizing the loop would produce wrong answers, and the auto-vectorizer cannot prove to itself that there are no such data dependences.

I don't understand this. Obviously each iteration of this loop is independent. How can I get Visual Studio to vectorize it?

The compiler can't prove that your 4 arrays don't overlap or alias. That aside, I'm not sure this loop is that easily vectorizable in the first place. I'm not too confidant I can do better than this naive approach manually via intrinsics. — Mysticial
Split it into 2 loops, 1 with out_array[0] = in_array1[x]; one with the other 2. Then which loop does the compiler complain about? — indeterminately sequenced
@indeterminatelysequenced The overhead of making 3 passes over the out_array array is likely non-negligible. That said, I can't say whether it will be better or worse anyway. — Mysticial
@Dr_Asik Correct. in_array2 and in_array3 are being read non-sequentially. You are making hops of size period * (x / 2) Vectorization really only works with sequential accesses where you don't skip any elements. — Mysticial

kfsone kfsone · Accepted Answer · 2013-05-21T04:02:58

The primary reason it can't vectorize this is that, as written, the compiler cannot eliminate the possibility that out_array[n] is not in_arrayX[m], so it has to stick with your sequential ordering.

You can resolve this for the compiler with the "__restrict" or "restrict" keyword which is a promise to the compiler that you will only call it in a way that ensures out_array is not the same as any of the other three pointers. You may also want to get generous with the "const" modifier to assist the compiler:

void func(const int period,
    unsigned char* __restrict out_array,
    const unsigned char* in_array1,
    const unsigned char* in_array2,
    const unsigned char* in_array3)
{
   ...
   //mark 'width' as 'const' if possible:
   const int width = ...;
   for (int x = 0; x < width; ++x)
   {
       const int index = period * (x / 2);

       out_array[(x* 4) + 0] = in_array1[x];
       out_array[(x* 4) + 1] = in_array2[index];
       out_array[(x* 4) + 2] = in_array3[index];
   }
}

How to get Visual C++ to vectorize this loop (error code 1200)?

1 Answers