Automatic Vectorization
Turn a loop over scalars into a loop over vectors, doing several elements per instruction. It is legal only when no dependence is violated by processing elements together, and profitable only when the memory access pattern suits it — and the list of things that make a vectorizer give up is longer than the list of things that make it succeed.
Why did my loop not vectorize, when the one next to it did?
A loop nest plus a dependence graph, mapped onto a target vector width. Vectorization is a *scheduling* decision expressed as a rewrite: the iteration space is chunked into groups of VF consecutive iterations, and each scalar operation becomes one operation on a vector of VF lanes. The representation the pass needs is the dependence graph plus a target description that says which vector widths and which operations exist.
Processing VF consecutive iterations simultaneously must preserve every dependence. A loop-carried dependence with a distance smaller than VF makes it illegal outright: if iteration i reads what iteration i-1 wrote, lanes within a vector would read stale values. Reductions are a special case — legal via a vector accumulator and a final horizontal combine, but only when the reduction operator is associative, which excludes IEEE-754 floating-point addition without explicit permission. Memory accesses must also be provably non-overlapping between the read and write streams, which for pointers means alias analysis or a run-time check.
Key points
- Vectorization processes several consecutive iterations in one instruction, plus a scalar remainder for the leftovers.
- A loop-carried dependence with distance less than the vector factor makes it illegal; the distance is what decides, not the presence of a dependence.
- Reductions vectorize with a vector accumulator and a final horizontal combine, but only when the operator is associative — which excludes IEEE floating-point addition without permission.
- Aliasing the compiler cannot rule out is handled with a run-time overlap check and a fallback;
restrictor a language with non-aliasing references removes the check. - Calls, early exits, non-contiguous access and unknown small trip counts are the other common blockers, and the diagnostics name which one applied.
- Legality and profitability are separate decisions, and a memory-bound loop gains little from vectorization however legal it is.
The rewrite, and the two questions behind it
A vector unit performs the same operation on several values at once — four, eight, sixteen lanes depending on the instruction set and the element width. Vectorizing a loop means restructuring it so each iteration of the new loop fills those lanes, plus a scalar remainder loop for the iterations that do not fill a full vector.
The compiler is asking two separate questions, and conflating them is the usual source of confusion when reading vectorizer diagnostics. Is it legal? — does processing several iterations together violate any dependence. Is it profitable? — will the vector version actually be faster, given the cost of gathering non-contiguous data, of the remainder loop, and of any run-time checks that had to be inserted. A loop can be perfectly legal to vectorize and be rejected on cost, and the diagnostics distinguish the two.
for (int i = 0; i < n; i++)
c[i] = a[i] + b[i];// conceptual output at VF = 4:
int i = 0;
for (; i + 3 < n; i += 4)
store4(&c[i], add4(load4(&a[i]), load4(&b[i])));
for (; i < n; i++) // scalar remainder
c[i] = a[i] + b[i];Each iteration reads a[i] and b[i] and writes c[i], so no iteration depends on another — the dependence graph has no loop-carried edges. The accesses are unit-stride, so four consecutive elements are one contiguous vector load. And c must be proved not to overlap a or b; where the compiler cannot prove it, it emits a run-time overlap check and a scalar fallback, which is legal but costs the check.
A loop-carried dependence spans fewer than VF iterations. c[i] = c[i-1] + a[i] cannot be vectorized as written: lane 1 needs the result lane 0 is still computing. A distance of 1 blocks every vector width; a dependence with distance 8 permits VF up to 8. This is why a[i] = a[i-1] + 1 refuses and a[i] = a[i-16] + 1 may not — the distance is the whole answer, and it is why compilers compute it rather than pattern-matching.
What actually defeats a vectorizer
-Rpass=loop-vectorize, -Rpass-missed=loop-vectorize and -Rpass-analysis=loop-vectorize, the last of which gives the specific reason. GCC reports through -fopt-info-vec and -fopt-info-vec-missed. The categories above are common to both; the exact wording and the set of cases each handles differ and change between versions.The useful content of this lesson is the list, because reading a -Rpass-missed=loop-vectorize message is much easier when you already know what the categories are.
- Loop-carried dependences. Iteration
ireads whati-1wrote. Reductions are the exception — a vector accumulator handles them — and only when the operator is associative. - Aliasing it cannot rule out. If the output pointer might overlap an input, elements written by one lane could be read by another. Compilers often insert a run-time overlap check and vectorize under it;
restrictremoves the check, and Rust's references remove the question —[[alias-analysis]]. - Unknown or non-constant trip count. Not fatal by itself — a remainder loop handles it — but a trip count that is *usually small* makes vectorization unprofitable, and without a profile the compiler must guess.
- Non-contiguous access.
a[i*3]ora[idx[i]]requires gather instructions or several loads plus shuffles. Sometimes done, often judged not worth it, and the cost model rather than legality is what decides. - Function calls in the body. A call is opaque: unknown effects, unknown dependences, and no vector version of the callee. Inlining first, or a vectorized math library with
#pragma omp declare simd, is what removes this — which makes[[inlining]]a prerequisite. - Early exits. A
breakor areturninside the body means the loop may stop mid-vector, and lanes past the exit must not have their side effects performed. Some compilers handle simple search loops; most refuse. - Floating-point reductions without reassociation permission. Summing into one accumulator is a dependence chain, and breaking it into vector lanes changes the association. Legal only with
-ffast-mathor a local pragma — see[[strength-reduction]]. - Unaligned or unknown-alignment access. Rarely fatal on modern instruction sets, where unaligned vector loads are cheap, but it still shows up in cost models and on targets where it is not.
- Complex control flow in the body. Handled by if-conversion into masked operations where the target has masking; otherwise a blocker.
Legality is not profitability, and the cost model is a guess
Once a loop is legal to vectorize, the compiler estimates whether it should be. That estimate involves the width, the cost of each vector operation on the target, the overhead of the remainder loop, the cost of any run-time alias check, and — crucially — an assumed trip count, because a loop that runs three times will never reach the vector body.
That guess is the weakest part of the process, and it is exactly what profile data fixes. It is also why #pragma omp simd exists: it asserts that the loop is safe to vectorize and instructs the compiler to do it, moving both the legality proof and the profitability judgement to the programmer. Used correctly it unlocks loops the compiler could not prove; used carelessly it produces wrong answers with no diagnostic, because the pragma is a promise the compiler does not check.
The final honest note is that vectorizing a memory-bound loop buys very little. If the loop is limited by how fast data arrives from memory, doing the arithmetic four at a time does not make the data arrive faster. Vectorization pays when there is arithmetic to parallelise and the data is already streaming efficiently, which is why it so often comes after the locality work in [[loop-transformations]] rather than before it.
| Loop | Legal? | Vectorized in practice? |
|---|---|---|
c[i] = a[i] + b[i], restrict pointers | Yes | Yes — the canonical case |
c[i] = a[i] + b[i], plain pointers | Yes, under a run-time check | Usually, with an overlap test and a scalar fallback emitted |
sum += a[i], int | Yes, as a reduction | Yes — integer addition is associative |
sum += a[i], doublespec | Not without permission | Only with -ffast-math or #pragma omp simd reduction(+:sum) |
a[i] = a[i-1] + 1 | No — distance-1 loop-carried dependence | No, at any width |
if (a[i] > 0) c[i] = a[i]target | Yes, via masking | Usually, on targets with masked stores |
Body contains f(a[i]) with f external | Unknown | No, unless f is inlined or has a declared SIMD variant |
How it works
The steps, in the order the compiler takes them.
- Identify a candidate loop with a single entry, a countable trip count and a body that can be analysed.
- Compute the dependence graph over the loop's memory accesses, including the distances of any loop-carried dependences.
- Determine the maximum safe vector factor: bounded above by the smallest loop-carried dependence distance, and by the target's available widths.
- For memory accesses that cannot be disambiguated statically, decide whether to emit a run-time overlap check plus a scalar fallback, and include its cost in the decision.
- Recognise reductions and pattern-match them onto a vector accumulator plus a horizontal reduction after the loop, checking the operator's associativity or the reassociation permission.
- If-convert conditional statements into masked vector operations where the target supports masking; otherwise reject.
- Estimate the cost of the vector body against the scalar body over the estimated trip count, including the remainder loop, and vectorize only if it wins.
- Emit the vector loop, the remainder loop, and any guards, then re-run simplification on the result.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- A loop that looks obviously parallel does not vectorize, and nothing in the build output says why until
-Rpass-analysis=loop-vectorizeis enabled — at which point it names an aliasing pair or a call. - A loop vectorizes and gets slower, because it was memory-bound and the added remainder loop and alias check cost more than the arithmetic saved.
- A floating-point sum changes in the last few bits after
-ffast-mathis enabled to unlock vectorization, and a bit-exact test fails. The result is not wrong, but the test was checking something the flag gave away. #pragma omp simdis applied to a loop with a genuine loop-carried dependence, and the program produces wrong results with no warning — the pragma is an assertion the compiler trusts rather than verifies.- A hand-written intrinsics version stops matching the auto-vectorized one after a compiler upgrade, and the hand-written version is now slower and target-specific and cannot be changed easily.
When it helps
- Element-wise operations over arrays: arithmetic kernels, image and audio processing, numerical inner loops — where the arithmetic is the cost and the access is contiguous.
- Reductions over large arrays where the operator is associative, which vector accumulators handle well.
- After
[[inlining]]and after locality work, when the body has no calls and the data streams efficiently — vectorization is usually the last of the loop optimizations to pay off, not the first.
When it hurts
- Memory-bandwidth-bound loops, where the arithmetic was never the bottleneck and the vector version adds overhead for nothing.
- Loops with small or highly variable trip counts, where the remainder loop and the run-time checks dominate.
- Where the alias check itself is expensive relative to the body — a short loop with several pointer pairs to check can spend most of its time in the guard.
What it costs
Every one of these is paid by something.
- Vectorization buys several elements per instruction and pays in code size — a vector body, a remainder loop and sometimes a guarded scalar fallback, three versions of one loop — plus the compile time to analyse and cost them.
- Emitting a run-time alias check buys vectorization for loops that could not be proved safe and costs a branch and the duplicated scalar path on every entry, which is a bad trade for short loops.
- Granting reassociation to unlock floating-point reductions buys a large speedup and costs IEEE-754 conformance and result reproducibility across builds and optimization levels.
- Writing intrinsics by hand buys certainty about what is generated and costs portability, readability and the ability to benefit from later improvements in the compiler.
What else you could do
What a different compiler or language does instead, and when that is better.
- Write intrinsics or inline assembly. Full control, no guessing, and code that is tied to one instruction set and must be rewritten for the next.
- Use
#pragma omp simdto assert legality and force the transformation, keeping portable source and taking responsibility for the assertion. - Use a library: BLAS, oneDNN, Highway, std::simd. Someone has already done the per-target work, usually better.
- Restructure the data instead. Struct-of-arrays rather than array-of-structs turns a strided access into a contiguous one and is frequently what unlocks vectorization —
[[loop-transformations]]. - Do nothing: if the loop is bound by memory bandwidth, the correct answer is to reduce memory traffic, not to vectorize the arithmetic.
See it for yourself
The flag, dump or tool that shows you this directly.
- Clang:
-Rpass=loop-vectorizefor successes,-Rpass-missed=loop-vectorizefor refusals, and-Rpass-analysis=loop-vectorizefor the specific reason. The third is the one that answers the lesson's question. - GCC:
-fopt-info-vecand-fopt-info-vec-missed, with-fopt-info-vec-allfor the full analysis. - Confirm from the disassembly: look for the vector registers and instructions of the target —
xmm/ymm/zmmwithpadd/vaddpson x86-64,v0-v31withadd v0.4son AArch64. - Add
restrictto the pointers and re-run the diagnostics; if the refusal changes, aliasing was the blocker and you have your answer. perf stat -e cycles,instructionsbefore and after: vectorization should cut the instruction count substantially, and if the cycle count does not follow, the loop was memory-bound.
Plausible wrong readings
Stated the way a confident engineer states them.
- "The compiler vectorizes anything parallel." It vectorizes what it can prove is parallel, which is a much smaller set, and only when its cost model agrees.
- "My loop is simple, so it will vectorize." Simplicity in source says nothing about aliasing, trip count or whether a call is hiding in an operator overload. Ask the diagnostics.
- "Vectorization made it slower, so the compiler is wrong." More likely the loop was memory-bound, or its trip count was small, and the cost model guessed the trip count.
- "
-ffast-mathjust enables vectorization." It changes floating-point semantics program-wide. Enabling vectorization is a consequence, and a#pragma omp simd reductionis the local way to get the same effect.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
Processors can do the same arithmetic on several numbers at once. The compiler tries to rewrite loops to use that, which requires the iterations to be independent of each other and the data to sit next to each other in memory. When it declines, it is almost always because it cannot prove one of those two things.
practical
Never guess whether a loop vectorized — ask, with -Rpass-analysis=loop-vectorize or -fopt-info-vec-missed. The three highest-value fixes are: add restrict or use a language that carries the guarantee; inline or remove calls from the body; and lay the data out contiguously in the direction the loop walks. If you need to break a floating-point reduction chain, say so locally with a pragma rather than globally with a flag.
advanced
Modern vectorizers do more than the loop-level transformation described here. SLP (superword-level parallelism) vectorization finds independent scalar operations in straight-line code and packs them into vectors without any loop at all — which is why some functions contain vector instructions with no loop in sight. Vector-length-agnostic instruction sets such as SVE and RISC-V V change the model again: the width is not known at compile time, so the generated code uses predication and a loop over an unknown vector length, removing the remainder loop entirely and making the same binary run on different vector widths. Both are cases where the compiler's model of the machine and the machine itself are further apart than the classic fixed-width picture suggests.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
-march=native changes the available widths), and the cost model, so it must be checked per compiler rather than assumed.-ffast-math, -fassociative-math, or an OpenMP reduction clause. The integer equivalent needs no permission because integer addition is associative.If you were asked this in an interview
- Give me five distinct reasons a compiler would refuse to vectorize a loop.
- Why can
sum += a[i]be vectorized forintand not fordouble? - A loop vectorized and got slower. What are the likely explanations and how would you check?