Auto-vectorization: reading and steering it

Level 10 introduced the auto-vectorizer. This skill is about working with it at the machine level: reading the vector code GCC produces, recognising from the asm why a loop wasn't vectorized, and rewriting the C++ so it is — without intrinsics, and without -ffast-math.

1. What GCC does at each level (GCC 12+)

The target matters as much as the level: the same -O2 loop may stay scalar for SSE2 and vectorize for AVX2, because wider lanes make it profitable.

Ask GCC directly:

$ g++ -O2 -march=x86-64-v3 -fopt-info-vec-optimized -c k.cpp
k.cpp:4:26: optimized: loop vectorized using 32 byte vectors
$ g++ -O2 -march=x86-64-v3 -fopt-info-vec-missed -c k.cpp
k.cpp:9:26: missed: couldn't vectorize loop
k.cpp:10:14: missed: not vectorized: complicated access pattern.

2. Reading vectorized code

A vectorized loop has a recognisable shape. For y[i] = x[i] + k with __restrict pointers at -O2 -march=x86-64-v3:

    vpbroadcastd ymm1, edx             ; k → all 8 lanes, once
.L4:                                   ; main loop: 8 ints per iteration
    vpaddd  ymm0, ymm1, YMMWORD PTR [rsi+rax]
    vmovdqu YMMWORD PTR [rdi+rax], ymm0
    add     rax, 32
    cmp     rax, rcx
    jne     .L4
    …                                  ; epilogue: the last 0–7 elements
                                       ; (an xmm step and/or a scalar loop)
    vzeroupper
    ret

Things to look for in the Compiler tab:

• ymm / xmm operands with p (packed) mnemonics — vpaddd, vmulps, vaddps — inside the loop: vectorized. ss/sd suffixes (vaddss) are scalar float ops that merely use xmm registers.
• The induction step: add rax, 32 (8 × 4 bytes) instead of add rax, 4.
• Prologue checks like cmp rdx, 7 / jbe (too short for a vector iteration) and, at -O3, address comparisons (alias versioning).
• A fold after the loop for reductions: vextracti128, shuffles, adds.

3. What blocks it — and the fix

Aliasing

#include <cstddef>
void add_k(int* y, const int* x, int k, std::size_t n) {
    for (std::size_t i = 0; i < n; ++i) y[i] = x[i] + k;
}

If y == x + 1, each iteration reads what the previous one wrote; loading 8 x values before storing 8 y values would change the result. -O3 handles it with a runtime overlap check (two versions of the loop); -O2 won't. The fix is a promise:

#include <cstddef>
void add_k(int* __restrict y, const int* __restrict x, int k, std::size_t n) {
    for (std::size_t i = 0; i < n; ++i) y[i] = x[i] + k;
}

__restrict (GCC/Clang/MSVC extension; restrict in C) means "nothing else accesses this memory through another pointer here". Breaking it is UB. With std::span parameters, copy .data() into local __restrict pointers. Aliasing also bites through members: in a loop over this->v.size() writing out[i], the compiler may have to reload size() every iteration, because out might point into the vector's own control block — hoist it into a local.

Loop-carried dependencies

a[i] += a[i - 1] needs the previous iteration's result. No lane-parallel version exists without changing the algorithm (a SIMD prefix sum is log₂(lanes) shift-and-add steps — a different program).

Float reductions

#include <cstddef>
float sum(const float* a, std::size_t n) {
    float s = 0;
    for (std::size_t i = 0; i < n; ++i) s += a[i];
    return s;
}

Vectorizing this means adding in a different order — (a0+a8+…) + (a1+a9+…) + … — and float addition isn't associative:

#include <cstdio>
int main() {
    volatile float big = 1e8f, one = 1.0f;
    std::printf("%g %g\n", (big + one) - big, (big - big) + one);
}

So GCC keeps the order. For a dot product it still vectorizes the products and then adds them one at a time (eight vaddss per chunk: an in-order reduction). Your options:

1. Write a vectorizable order yourself: independent partial sums. The compiler maps acc[0..7] onto one ymm register (SLP vectorization):

   #include <cstddef>
   float sum(const float* a, std::size_t n) {
       float acc[8] = {};
       std::size_t i = 0;
       for (; i + 8 <= n; i += 8)
           for (std::size_t k = 0; k < 8; ++k) acc[k] += a[i + k];
       float s = 0;
       for (; i < n; ++i) s += a[i];
       for (float x : acc) s += x;
       return s;
   }
   

2. -fassociative-math (part of -ffast-math): file-wide permission — along with other assumptions (no NaN/inf with -ffinite-math-only).
3. #pragma omp simd reduction(+:s) with -fopenmp-simd: permission for one loop.
4. std::reduce / std::transform_reduce with std::execution::unseq.

Integer sums have no such problem: integer addition is associative, so the compiler regroups freely.

Early exits, calls, strides, conditions

• Early exit (if (a[i] == v) return i;): scalar at -O2; GCC 15+ can vectorize some at -O3. Hand-written movemask code (x86-simd-intrinsics) is the dependable route.
• Calls to functions the compiler can't inline: it can't make 8 calls at once (unless the function has #pragma omp declare simd clones). Math functions like sqrtf are fine (vsqrtps); expf needs a vector math library (-fveclib, glibc's libmvec with -ffast-math).
• Strided / gathered access (x[2*i], x[idx[i]]): needs shuffles or vpgatherdd; often judged unprofitable at -O2. Prefer a structure-of-arrays layout (Level 10, data-oriented design).
• Conditions: y[i] = c ? a : b becomes a blend — fine. A conditional store (if (c) y[i] = …) needs a masked store; often blocked.
• Mixed widths: int loads into int64_t sums need widening (vpmovsxdq) — fine, but each widening halves the lanes per instruction.

4. The checklist

When a hot loop isn't vectorized, in this order:

1. Is it the right target? (-march=x86-64-v3 or target("avx2"))
2. -fopt-info-vec-missed: what does GCC say?
3. Pointers that may alias → __restrict locals.
4. A float reduction → partial sums.
5. Function calls → inline them, or restructure.
6. Data layout → contiguous, unit stride.
7. Still not? Intrinsics or std::experimental::simd.

The build task applies step 4: make a float dot product's sum vectorize, with the codegen stage checking the real -O2 -march=x86-64-v3 output.