Auto-vectorization with gcc 4.7

One way of speeding up code which contains many loops is to use vectorization. On modern machines, this means the use of SSE or AVX instructions. However, if one had to manually re-write code into assembly language in order to do this, then very few programs would. The reason is obvious: assembly language is error-prone, and a difficult skill to master. It is also intrinsically nonportable. Fortunately, compiler writers have a few tricks up their sleeves to help us.

At the lowest level, gcc exposes compiler intrinsics that match one-to-one with the vector instructions on the the cpu. Therefore, it is possible to write code using them in a higher level language like C or C++, and still have nearly complete control over the output. Unfortunately, since these intrinsics are still very low-level, code written using them can be a little hard to read. The code is also not portable to machines that lack the instructions corresponding to the intrinsics used.

gcc has another extension that helps with vectorization, vector types. It is possible to construct types that represent arrays (i.e. vectors) of smaller more basic types. Then, code can use normal C (or C++) operations on those types. The result will be vectorized over the whole vector of basic types. In other words, you can add two vectors together to make a third, and gcc will understand exactly what you mean and use the instruction you want. More recent versions of gcc allow array accesses into the vector types, making them even more flexible and easy to use.

Vector types have a disadvantage though, code needs to be rewritten in order to use them. Instead of passing around standard types, the non-portable compiler-specific ones need to be used instead. Also, since there are many vector operations that don't correspond to C operators, you may need to fall back to intrinsics in order to get the instructions you want.

At an even higher level is auto-vectorization. There, code isn't re-written at all. It remains portable C, and the compiler automagically determines how to vectorize it. Since ideally, no work needs to be done, one can simply recompile with a new compiler and get all the speed advantages of vectorization with very little effort required. The big question though, is how much code can gcc vectorize? If very few loops can be, then this feature isn't too useful. Conversely, if gcc is very smart, then the lower level techniques aren't necessary any more.

Auto-vectorization

We use the most recent version of gcc at the time of writing (4.7) to test to see how well auto-vectorization works in practice. We will try a series of test routines with simple loops to see what gcc does with them. To start with, we will use a constant loop count. (It is possible to have a variable loop count, but in most code that doesn't change too much in the important inner loop.)

The first test simply adds an array of doubles onto a second array. We compile with -O3 which in modern gcc turns on auto-vectorization for us. We use no other optimization compile-time flags to get the default from the compiler. The resulting routine in asm is:

The above code is interesting... but not particularly optimal. gcc first tests to see if the arrays partially overlap, if so it jumps to a slow loop that does one addition at a time. If the arrays are not directly on top of each other, gcc then does a rather strange thing of loading each double manually, and stuffing them into %xmm1 and %xmm2 It then wastes time by copying into %xmm0 before finally doing the packed addition. Once the addition is done, it then moves the data out one double at a time.

The above can at best be called partially vectorized. The problem is that the compiler is constrained by what we tell it about the arrays. If we tell it more, then perhaps it can do more optimization. The most obvious thing is to inform the compiler that no overlap is possible. This is done in standard C by using the restrict qualifier for the pointers. The resulting code looks like:

The above is an enormous monstrosity. The problem here is alignment. gcc is not yet allowed to assume that the arrays are 16-byte aligned. This means that it has to go through all sorts of gymnastics to handle the cases which are not. (SSE instructions in general do not work with unaligned accesses.) It also means that the inner loop above can't assume that both arrays are aligned. If gcc were smart, it could test for the cases where the arrays are either both aligned, or both unaligned, and have a fast inner loop. However, it doesn't do that currently.

So in order to get the performance we are looking for, we need to tell gcc that the arrays are aligned. There are a couple of ways to do that. The first is to construct a (non-portable) aligned type, and use that in the function interface. The second is to add an intrinsic or two within the function itself. The second option is easier to implement on older code bases, as other functions calling the one to be vectorized do not have to be modified. The intrinsic has for this is called __builtin_assume_aligned:

Which is unfortunately identical to the non-aligned version. It looks like gcc didn't understand what we were telling it. Lets be more explicit:

Now finally, we get the nice tight vectorized code we were looking for. gcc has used packed SSE instructions to add two doubles at a time. It also manages to load and store two at a time, which it did do last time. The question is now that we understand what we need to tell the compiler, how much more complex can the loop be before auto-vectorization fails.

The above uses a common code idiom where a matrix is represented by a block of contiguous memory. The explicit indexing is usually hidden within a macro in normal usage, but the above is what it would expand out into. Lets see how well gcc does:

Ouch! What a difference a single extra loop makes. gcc hasn't understood what we are trying to say. Perhaps the problem here is that the amount of memory accessed is larger than the size an int can touch. Lets use size_t as a hint that the two loop indexes can be collapsed into one.

The above is a bit better (200 instead of 300 bytes of instructions), but still is nowhere near where we want it to be. It looks like gcc doesn't understand that we are just iterating over the array in segments. Lets be more explicit that we touch the whole array:

This accomplishes the exact same thing as the previous two functions, but uses one loop. This routine is very similar to test4(), and we would expect gcc to do a fairly good job:

Indeed, it does produce what we are looking for. So, a rule of thumb might be; two loops bad, one loop good.

We have used addition in the above because it is both a C operator, and a vectorizable instruction. Lets see what happens when we try to use something that should vectorize, but doesn't directly correspond to a C operator. A simple example is the max() operation:

And there is no vectorization at all. What has gone wrong? The problem here is the C memory model. gcc isn't allowed to introduce extra writes to a memory location. If some other thread modifies x[] while the above routine is called, then those extra writes could stomp on modifications. We need a way to tell gcc that using the vectorized max() instruction is okay. Fortunately, this isn't too hard, we just use a non-conditional write:

This code looks like the vectorized code for addition, and we didn't have to use any SSE-explicit intrinsic to do so. gcc has pattern-matched the operation and found the instruction we are looking for, which is very encouraging.

So what happens when we try something a little more complex, like a conditional add?

Which is unfortunately not vectorized. Perhaps our expression is too complex, so lets try the simpler version:

So the form of the expression matters. In this case, a different rearrangement of an expression was vectorizable. In general, the simpler the expression, the greater the chance of auto-vectorization.

All of the above have had fixed-length loops. What happens if the loop exit condition is more complex:

Where here we can exit early if the (hopefully vectorizable) condition occurs. Unfortunately, gcc produces:

Where the above obviously isn't vectorized. For some reason gcc isn't using a compare followed by a move-mask to determine if the loop can exit early, whilst maintaining the ability to do two adds at a time.

In all the above, we have used simple indexing, lets see what happens if we make it more complex:

This is half-vectorized. Instead of using an unaligned load instruction, gcc has used two half-load instructions for the upper and lower halves of %xmm1. The unaligned-load is probably better. Another possibility is to use pipelined aligned loads followed by shuffles.

If we switch to an even offset, gcc no longer needs to do unaligned accesses, and switches back to full vectorization:

So the quality of the code gcc produces can subtly depend on which index offsets are used. Confirming this is the simpler routine:

So, now that we have a third array, lets use it within the expression on the right:

Ooops, no vectorization here. It looks like a conditional store is a bit too complex. How about if we make it a bit simpler, using an if statement instead:

This is a bit tighter code, but it still isn't vectorized. We may need to go to intrinsics to get something like the output from test11().

Finally, lets look at operations that scan over an array, and collate a single output. gcc should be able to vectorize these as well.

Unfortunately, this global maximum operation isn't vectorized. Lets see a simpler function that calculates a global sum instead:

Which also isn't vectorized. What is going on? The problem here is that gcc isn't allowed to re-order the operations we give it. Even though the maximum operation, and the addition operation are associative with real numbers, they aren't with floating point numbers. (Consider what happens with signed zeros, for example.)

We need to tell gcc that re-ordering operations is okay with us. To do this, we need to add another compile-time flag, "--fast-math". If we do this, we find that the output from functions 20 and 21 are improved:

gcc is very intelligent, and does a vectorized maximum calculation, followed by a horizontal maximum at the end.

And again gcc manages to vectorize the summation, even with having to do a horizontal add at the end.

Summary

gcc is very good, and can auto-vectorize many inner loops. However, if the expressions get too complex, vectorization will fail. gcc also may not be able to get the most optimal form of the loop kernel. In general, the simpler the code, the more likely gcc is to give good results.

However, you cannot expect gcc to give what you expect without a few tweaks. You may need to add the "--fast-math" to turn on associativity. You will definitely need to tell the compiler about alignment and array-overlap considerations to get good code.

On the other hand, gcc will still attempt to vectorize code which hasn't had changes done to it at all. It just won't be able to get nearly as much of a performance improvement as you might hope.

However, as time passes, more inner loop patterns will be added to the vectorizable list. Thus if you are using later versions of gcc, don't take the above results for granted. Check the output of the compiler yourself to see if it is behaving as you might expect. You might be pleasantly surprised by what it can do.

Comments

bobbyprani said...

I wonder how good ICC will be able to vectorize these codes. Last heard, ICC was much better at auto-vectorization than GCC. I think I will do a comparison with ICC for the above cases.

pikachu said...

Just read software.intel.com/file/31848

Bdog said...

Rather than use -ffast-math, which sets a number of potentially dangerous options, it would be safer to use -fassociative-math to enable the specific optimization desired here.

ssam said...

Could it be considered a GCC bug that:
__builtin_assume_aligned(a, 16);
was not recognised, and you had to switch to:
double *x = __builtin_assume_aligned(a, 16);

Also what are the practical implications of making that assumption? do I have to do something special when I create the array?

(PS you captcha is hard)

sfuerst said...

You may consider it a bug. The gcc maintainers may disagree. I haven't tried submitting a PR request for it though.

For 16-byte alignment: Anything allocated by malloc() and friends will already be 16-byte aligned due to the ABI. Arrays allocated statically or on the stack probably will not be 16-byte aligned. You will need to add a non-standard gcc alignment attribute for them.

The Captcha is unusual... but we get hundreds of spam attempts per day, and it filters out all of them.

said...

Enter your comments here

Albert said...

Hi and thanks for this great article! What flags did you give gcc when compiling these examples? I couldn't get it to recognize the restrict keyword.

Then I tried your examples with icc and used:

#pragma vector always
#pragma vector aligned

before the loop and flags:

-restrict -O3 -march=corei7-avx -vec-report2

to icc. That worked and it vectorized nicely. But I had to manually edit the generated .s file a bit before I could feed it back to gcc. Basically what I did was removing some intel stuff and adding .cfi_startproc and .cfi_endproc. And changed to .p2align syntax, like the ones gcc -O3 usually generates.

It would be nice to see a vectorization comparison between gcc and icc, as the first comment suggested. Keep up the good work!

hsroh said...

This is what Sun's suncc generates for test2:

<pre>

test2:
.CG4:
.CG5:
        movl %edi,%edx
        andl $15,%edx
        movl %esi,%eax
        andl $15,%eax
        movl %edi,%ecx
        andl $7,%ecx
        xorl %edx,%eax
        xorl %r8d,%r8d
        orl %ecx,%eax
        je .L77000045.44
.L77000069.43:
        xorq %rax,%rax
        .align 16
.L77000057.52:
        prefetcht0 256(%rdi,%rax)
        movupd (%rdi,%rax),%xmm0
        movupd (%rsi,%rax),%xmm1
        addpd %xmm1,%xmm0
        movupd %xmm0,(%rdi,%rax)
        prefetcht0 272(%rsi,%rax)
        movupd 16(%rdi,%rax),%xmm0
        movupd 16(%rsi,%rax),%xmm1
        addpd %xmm1,%xmm0
        movupd %xmm0,16(%rdi,%rax)
        movupd 32(%rdi,%rax),%xmm0
        movupd 32(%rsi,%rax),%xmm1
        addpd %xmm1,%xmm0
        movupd %xmm0,32(%rdi,%rax)
        movupd 48(%rdi,%rax),%xmm0
        movupd 48(%rsi,%rax),%xmm1
        addpd %xmm1,%xmm0
        movupd %xmm0,48(%rdi,%rax)
        addq $64,%rax
        addl $8,%r8d
        cmpl $65534,%r8d
        jle .L77000057.52
.LX2.123:
        jmp .LE5.143
.L77000045.44:
        movl $16,%ecx
        subl %edx,%ecx
        sarl $3,%ecx
        andl $1,%ecx
        jle .LE0.120
.L77000071.46:
        addl $-1,%ecx
        movq $65535,%rax
        movslq %ecx,%rcx
        cmpq %rcx,%rax
        movq $0,%rdx
        cmovlq %rax,%rcx
        .zalign 16,8
.L77000049.48:
        movsd (%rdi,%rdx),%xmm0
        addsd (%rsi,%rdx),%xmm0
        movsd %xmm0,(%rdi,%rdx)
        addq $8,%rdx
        addl $1,%r8d
        cmpl %ecx,%r8d
        jle .L77000049.48
.LX0.119:
.LE0.120:
.L77000044.45:
        movl $65536,%ecx
        subl %r8d,%ecx
        leal 1(%rcx),%edx
        testl %ecx,%ecx
        cmovnsl %ecx,%edx
        sarl $1,%edx
        testl %edx,%edx
        jle .LE5.143
.L77000072.50:
        movl $-2147483647,%eax
        andl %ecx,%eax
        jns .CG3.144
        andl $1,%eax
        negl %eax
.CG3.144:
        subl %eax,%ecx
        addl %r8d,%ecx
        movslq %r8d,%rax
        movl %ecx,%edx
        subl %r8d,%edx
        addl $-2,%edx
        leal -2(%rcx),%r10d
        leal 1(%rdx),%r9d
        shlq $3,%rax
        testl %edx,%edx
        cmovnsl %edx,%r9d
        sarl $1,%r9d
        addl $1,%r9d
        cmpl %r10d,%r8d
        jle .CG2.134
        xorl %r9d,%r9d
.CG2.134:
        cmpl $4,%r9d
        jl .LU0.135
.LP0.139:
        addl $-8,%ecx
        .zalign 16,8
.L77000052.51:
        prefetcht0 256(%rdi,%rax)
        movapd (%rdi,%rax),%xmm0
        addpd (%rsi,%rax),%xmm0
        movapd %xmm0,(%rdi,%rax)
        prefetcht0 272(%rsi,%rax)
        movapd 16(%rdi,%rax),%xmm0
        addpd 16(%rsi,%rax),%xmm0
        movapd %xmm0,16(%rdi,%rax)
        movapd 32(%rdi,%rax),%xmm0
        addpd 32(%rsi,%rax),%xmm0
        movapd %xmm0,32(%rdi,%rax)
        movapd 48(%rdi,%rax),%xmm0
        addpd 48(%rsi,%rax),%xmm0
        movapd %xmm0,48(%rdi,%rax)
        addq $64,%rax
        addl $8,%r8d
        cmpl %ecx,%r8d
        jle .L77000052.51
.LX4.140:
.LE4.141:
        cmpl %r10d,%r8d
        jg .LE5.143
.LU0.135:
        .zalign 16,8
.LU1.136:
        movapd (%rdi,%rax),%xmm0
        addpd (%rsi,%rax),%xmm0
        movapd %xmm0,(%rdi,%rax)
        addq $16,%rax
        addl $2,%r8d
        cmpl %r10d,%r8d
        jle .LU1.136
.LX5.142:
.LE5.143:
.LX1.121:
.LE1.122:
.LE2.124:
.L77000046.49:
        cmpl $65535,%r8d
        jg .LE3.126
.L77000070.54:
        movslq %r8d,%rax
        leaq (,%rax,8),%rcx
        .zalign 16,8
.L77000054.55:
        movsd (%rdi,%rcx),%xmm0
        addsd (%rsi,%rcx),%xmm0
        movsd %xmm0,(%rdi,%rcx)
        addq $8,%rcx
        addq $1,%rax
        cmpq $65535,%rax
        jle .L77000054.55
.LX3.125:
.LE3.126:
.L77000034.53:
        repz
        ret

</pre>

Yann said...

Thanks for your excellent article. It helps a lot when trying to build "standard" C code in a way which benefit auto-vectorize when it's present.

Quick question : I don't understand the requirement for "16-bytes aligned" property.

Both SSE and AVX offer instructions to load unaligned memory segments.
Look at movdqu (SSE) or vmovdqu (AVX).

They are very good. Not only do they work properly on unaligned memory, they also transparently benefit from loading aligned memory (i.e. they run faster in such case).

Considering the gigantic flexibility these instructions offer, I would use them always instead of their "aligned" counterpart (movdqa, vmovdqa).

Not sure, from your example, if GCC is able to use them automatically (without intrinsics).

Nat said...

The issues compiling are due to the restrict keyword being c99 specific. Add the flag -std=c99 and it should compile just fine with restrict.

Great article! Thanks from somebody just getting started with vectorization!

James said...

Thank you for the clear details on what Vectorization is. its so nice that people take the time to write articles like this up for the community!

said...

Enter your comments here