Parallelizing and Vectorizing Compilers

A modern CPU core is secretly a small parallel machine. Its SIMD units (SSE, AVX, NEON, SVE) apply one instruction to a whole vector of 4, 8, or 16 elements at once; multiple cores can run independent iterations simultaneously. But most source code is written as plain scalar loops — one element at a time. The job of a parallelizing and vectorizing compiler is to discover the parallelism latent in those loops and map it onto the hardware's lanes and cores, without the programmer rewriting anything. It is one of the highest-leverage optimisations there is: a single loop, correctly vectorized, can run several times faster on the exact same chip.

This work stands squarely on the theory of loop transformations and data dependence. The gating question is always the same: can these iterations run at the same time, or does one need a value another produces? Parallelism is legal exactly when the answer is "they're independent" — and proving independence is where all the difficulty lives.

Two shapes of automatic parallelism

Compilers exploit two distinct granularities, and it helps to keep them separate:

Auto-vectorization — pack several iterations (or several nearby scalar operations) into one SIMD instruction that processes a whole vector of lanes per cycle. Fine-grained, within a single core. Two flavours: loop vectorization (consecutive iterations become lanes) and SLP — superword-level parallelism (independent straight-line scalar operations, like the four components of a colour, are bundled into one vector op).
Auto-parallelization — spread whole iterations across multiple cores/threads. Coarse-grained. The prize target is a DOALL loop: one with no loop-carried dependence, so every iteration is independent and they can all run at once.

DOALL, dependences, and the SIMD picture

A loop-carried dependence is one that flows from one iteration to a later one. The loop a[i] = b[i] + c[i] has none — iteration 5 neither needs nor disturbs iteration 4, so it is DOALL and vectorizes trivially: load four bs, four cs, add all four in one instruction, store four as. By contrast a[i] = a[i-1] + b[i] carries a dependence of distance 1 — each iteration needs the previous iteration's result — so its lanes cannot run at once. The picture below contrasts the two:

On the left, four independent iterations drop cleanly into four SIMD lanes and execute in one vector step. On the right, the arrows chain iteration to iteration — a serial recurrence that no amount of wishful thinking will let you run in parallel as written.

Reductions: the important exception

Some loops look serial but aren't quite. A reduction — sum = sum + a[i] — has a genuine loop-carried dependence on sum, yet it can still be parallelized, because the combining operation (+) is associative. The compiler recognises the reduction pattern and splits it: give each lane (or thread) its own partial accumulator, run the independent partial sums in parallel, then combine the partials at the end.

\Big(\sum_{i} a_i\Big) \;=\; \underbrace{(a_0{+}a_4{+}\cdots)}_{\text{lane 0}} + \underbrace{(a_1{+}a_5{+}\cdots)}_{\text{lane 1}} + \underbrace{(a_2{+}a_6{+}\cdots)}_{\text{lane 2}} + \underbrace{(a_3{+}a_7{+}\cdots)}_{\text{lane 3}}

There is a subtlety with floating point: real addition is associative, but floating-point addition is not (rounding makes (a+b)+c \ne a+(b+c) in general). So reassociating a floating-point reduction can change the last bits of the result — which is why compilers only do it under a "fast-math"/relaxed-FP flag, and never by default.

Dependence tests: proving independence cheaply

To vectorize A[2*i + 1] = A[3*i] + 1 the compiler must decide whether a write in one iteration can ever hit the same array element as a read in another. Solving that exactly is integer linear programming; in practice compilers run a ladder of cheap, conservative dependence tests, from fastest-and-weakest to slowest-and-strongest:

The GCD test. A dependence between subscripts a\,i + c_1 and b\,i' + c_2 requires an integer solution to a\,i - b\,i' = c_2 - c_1. Such a solution exists only if \gcd(a,b) divides c_2 - c_1. If it does not, there is provably no dependence — vectorize freely. It is a one-line necessary condition and the classic first filter.
The Banerjee test. Sharper: it checks whether a real solution lies within the loop bounds (using the intermediate-value theorem on the subscript expression). If no solution fits the iteration range, no dependence exists — catching cases the GCD test cannot.
Stronger still: the Omega test and I-test decide the integer problem exactly for affine subscripts, at higher cost.

Note the logic: these tests prove the absence of a dependence. Failing the GCD condition is a certificate of independence. Passing it (gcd divides the difference) does not prove a dependence exists — only that one might, so the compiler must stay conservative and not parallelize (or run a stronger test).

The GCD test in code

Here is the GCD test deciding whether a dependence can exist between two affine array subscripts in a loop. If the gcd of the coefficients does not divide the constant gap, independence is proven and the loop is safe to vectorize.

The first and third loops are certified independent by a single divisibility check; the classic A[i] = A[i-1] recurrence passes the test (gcd 1 divides everything), so the compiler cannot rule out the dependence — exactly the loop that must stay serial.

Why it is hard — and why programmers add hints

If dependence testing were the whole story, compilers would vectorize everything. Reality fights back on several fronts:

Aliasing. If two array pointers might alias, the compiler must assume the worst and refuse to vectorize. This is the single most common blocker.
Alignment. SIMD loads are fastest (sometimes only correct) on suitably aligned addresses; the compiler must handle unaligned starts and generate a scalar remainder loop for the leftover iterations when the trip count isn't a multiple of the vector width.
Control flow. Branches inside the loop body must be turned into predicated (masked) vector operations, which not every target supports well.
Unknown trip counts and non-affine subscripts (A[index[i]] gathers) defeat static dependence tests entirely.

Because of all this, languages give programmers ways to promise what the compiler cannot prove. C's restrict asserts non-aliasing; #pragma omp simd and #pragma omp parallel for assert that a loop is safe to vectorize or parallelize; alignment attributes assert address alignment. These hints don't make the compiler smarter — they shift the proof obligation onto the programmer, letting the compiler proceed where its own analysis had to give up.

Superword-Level Parallelism (SLP) vectorizes straight-line code, no loop required. Imagine transforming an RGBA pixel: r2 = r*s; g2 = g*s; b2 = b*s; a2 = a*s — four independent scalar multiplies by the same factor. An SLP pass spots that these isomorphic operations can be bundled into a single 4-wide vector multiply, packing the four scalars into one vector register. It is the perfect complement to loop vectorization: loop vectorization finds parallelism across iterations, SLP finds it within a basic block among sibling operations. Modern compilers run both, and much hand-written "SIMD intrinsics" code is really just doing by hand what an SLP vectorizer does automatically.

Vectorization is all-or-nothing per loop: pack four iterations into one vector step and they execute simultaneously, so if any of those four needs a value another of the four is still computing, the result is wrong. A single true loop-carried dependence — one A[i] = A[i-1] + … anywhere in the body — is enough to block the entire loop, even if every other statement is embarrassingly parallel (the cure is often loop fission to split the serial statement out). Two more traps follow close behind. Reductions look like blocking dependences but are legal to parallelize only when the operator is associative — and for floating point that means accepting a different rounding, so it needs an explicit fast-math opt-in. And alignment/remainder: the vector body handles iterations in chunks of the vector width, so a scalar remainder loop must mop up the leftover n \bmod W iterations — forget it and you either crash on a bad access or silently skip elements.