C: Writing code which can be auto vectorized, nested loop, GCC

Question

I am trying to write some C code which can be vectorized. This is the loop I am trying:

for(jj=0;jj<params.nx;jj++)
    for(kk=0;kk<NSPEEDS;kk++)
        local_density_vec[jj] += tmp_cells_chunk[jj].speeds[kk];

GCC gives me the following message when run with the -ftree-vectorizer-verbose=5 flag http://pastebin.com/RfCc04aS.

How can I rewrite it in order that it can be auto vectorized. NSPEEDS is 5.

EDIT:

I've continued to work on it, and I don't seem to be able to vectorize anything with .speeds[kk]. Is there a way of restructuring it so that it can?

The compiler can't vectorize it because it can't determine if there is aliasing going on between your arrays. Furthermore, your `NSPEEDS` trip-count is too small to get any speedup from vectorizing. — Mysticial, Feb 13 '13 at 16:41
In my first attempt, I had the loops swapped around. I wanted it to unroll the look with `NSPEEDS` and to vectorize the other loop. Any loop with `.speeds[kk]` fails to vectorize. Can I change this? — superbriggs, Feb 13 '13 at 16:58
Aliasing means, that the compiler doesn't know if your arrays overlap. Vectorization usually changes the order in which the memory is accessed. The compiler can't legally vectorize unless it can prove that it won't violate any dependencies. — Mysticial, Feb 13 '13 at 17:19
In short, your code is not vectorizable no matter how you order it. Vectorization is usually only applicable to sequential and contiguous memory access. This is not the case here regardless of how you order the loop. The problem is that `tmp_cells_chunk` appears to be a struct. Which means you have [array-of-structs](http://stackoverflow.com/questions/8377667/layout-in-memory-of-a-struct-struct-of-arrays-and-array-of-structs-in-c-c) packing. If you want to vectorize, you may have to switch to struct-of-arrays memory layout. — Mysticial, Feb 13 '13 at 17:21
Thank you. I will try to change the datatype so that it is a struct of arrays instead. That should fix the problem, if I understand it correctly. — superbriggs, Feb 13 '13 at 17:29
Thank you very much for your help. I have had another issue with it stopping vectorising all together when I introduce OpenMP into the program. If you have had any experience with OpenMP, could you please have a quick look at this other post? http://stackoverflow.com/questions/14861447/using-openmp-stops-gcc-auto-vectorising — superbriggs, Feb 13 '13 at 19:30

score 4 · Accepted Answer · answered Feb 13 '13 at 20:15

for (jj = 0; jj < nx; jj++) {
        partial = 0.0f;
        fp = c[jj].speeds;
        for (kk = 0; kk < M; kk++)
                partial += fp[kk];
        out[jj] = partial;
}
(...)
Calculated minimum iters for profitability: 12

36:   Profitability threshold = 11

Vectorizing loop at autovect.c:36

36: Profitability threshold is 11 loop iterations.
36: LOOP VECTORIZED.

Important points:

1) In your dump, the loop was considered "complicated access pattern" (see the last line of your log). As already commented, this is related to the compiler being unable to verify aliasing. For "simple" access patterns, see: http://gcc.gnu.org/projects/tree-ssa/vectorization.html#vectorizab

2) My example loop required 12 iterations for vectorization to be useful. Since NSPEEDS == 5, the compiler would loose time if it vectorized yours.

3) I was only able to vectorize my loop after I added -funsafe-math-optimizations. I believe this is required due to either different rounding or associativity behavior with the resulting vector operations. See, for example: http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems

4) If you reverse the loop you could have problems with "complicated" access patterns again. As already commented, you may need to reverse the array organization. Check the gcc vectorization docs about strided accesses to check if you can match one of the patterns.

For completeness, here is the complete example: http://pastebin.com/CWhyqUny

C: Writing code which can be auto vectorized, nested loop, GCC

1 Answers1