Vectorization: Turning a Loop Into Vector Work

Given two pointers into arrays, a compiler generally cannot assume they point to different memory. If a and c overlap, then writing c[i] may change a value that a later iteration reads through a, creating a genuine loop-carried dependency. Vectorising would compute several iterations at once and produce a different, wrong answer.

So the compiler faces a choice: prove non-overlap, or emit scalar code. Sometimes it can prove it — arrays declared locally, or types that cannot alias under the language rules. Often it cannot, particularly across function boundaries where the pointers arrive as parameters. The result is a loop that looks perfectly parallel and compiles to scalar code.

The fixes are all about supplying the missing proof: a restrict-style annotation promising non-overlap, passing by value or by a type the language guarantees cannot alias, or a runtime overlap check that dispatches to a vector path when the ranges are disjoint. Many compilers generate that last one automatically — versioning the loop and choosing at run time — which costs a branch and some code size in exchange for keeping the vector path available.

Loop-carried dependencies are the fundamental blocker. If iteration i reads a value that iteration i-1 wrote, the iterations are genuinely ordered and no legal transformation can run them together. A running sum is the common case — and the standard fix is per-lane partial sums combined at the end, which is legal only if reassociating the operation is acceptable. For integers it always is; for floating point it changes the result, so the compiler needs explicit permission (Why 0.1 + 0.2 Is Not 0.2 + 0.1's Problem).

Control flow inside the loop body breaks uniformity. Where the instruction set supports masking, the usual implementation computes all paths and blends the results, so a loop with a rarely-taken expensive branch pays for it on every element. Where masking is unavailable, the loop simply does not vectorise. Restructuring into separate uniform passes over filtered data is often faster than either.

Memory access shape decides whether the loads are cheap. Contiguous unit-stride access maps onto a single wide load. Strided access wastes most of each cache line. Truly scattered access requires gather instructions where they exist, and those cost substantially more than a contiguous load — often enough to erase the benefit entirely. This is the deepest reason layout choices like Array of Structs, or Struct of Arrays? have such a large effect on numeric code.

A reduction is the most common loop shape that appears blocked but is not. sum = sum + a[i] has a loop-carried dependency on sum by construction, so a literal transformation is illegal. The standard rewrite keeps one partial sum per lane, accumulates independently, and performs a single horizontal combine after the loop.

That rewrite is legal for integer addition, which is associative. It is *not* legal for floating-point addition, which is not: grouping the additions differently changes rounding and therefore the result. The difference is usually tiny and occasionally is not, and it is not the compiler's decision to make — so by default it will refuse, and vectorising the reduction requires an explicit flag or pragma granting permission to reassociate.

This is the single most common surprise when a numeric loop refuses to vectorise. The loop looks trivially parallel, the arrays do not alias, and it still emits scalar code — because the answer would differ in the last bits and the compiler is not allowed to decide that is acceptable on your behalf. The correct response is to decide deliberately, not to reach for a global fast-math flag that also relaxes assumptions you may be relying on elsewhere.