Lesson 18.8 — Vectorization: the loop vectorizer, VPlan, SLP, predication and scalable vectors¶

Techniques: loop vectorization (legality, cost model, interleaving, runtime checks, epilogue vectorization), VPlan, SLP vectorization, predication, masking and scalable vectors · Pebble implements: — · Lab: — (the real-world boxes are the experiments) · Prerequisites: Lesson 18.6 (LoopAccessAnalysis, distances), Lesson 18.5 (versioning, remainders), Lesson 18.3 (trip counts, add recurrences) · Time: 6–7 hours

A modern core executes one instruction on 4, 8, 16 or more data elements at once (SSE, AVX, AVX-512, NEON, SVE, RVV). Vectorization is the compiler's job of finding those data elements: in consecutive loop iterations (the loop vectorizer) or in isomorphic scalar instructions of straight-line code (SLP). It is the loop optimization with the largest direct payoff, and it uses almost everything in this chapter: trip counts (Lesson 18.3), dependence distances and runtime checks (Lesson 18.6), versioning and remainder loops (Lesson 18.5), and induction variables (Lesson 18.2).

1. Problem and motivation¶

The problem. Given a loop for i in 0..n: body(i), produce code that runs \(VF\) iterations per instruction — body(i..i+VF-1) as vector operations — whenever that gives the same results, and decide whether it is worth it on the target. Given a basic block, find groups of independent, isomorphic instructions that can become one vector instruction.

Loop vectorization¶

The classic vectorizers of the 1970s–80s (Allen and Kennedy's PFC) transformed Fortran loops into vector statements for Cray-style machines, statement by statement after loop distribution [AK87; AK02]. LLVM's loop vectorizer vectorizes innermost loops as a whole, executing \(VF\) iterations in lockstep: it checks legality (LoopAccessAnalysis, Lesson 18.6; reductions and inductions, Lesson 18.2; if-convertible control flow), chooses \(VF\) and an interleave count \(IC\) with a target cost model, emits runtime checks when pointers may overlap, and handles the leftover iterations with a vectorized epilogue and a scalar remainder [LLVM-Vectorizers; LLVM-LV]. GCC's vectorizer follows the same plan [GCC-Vect]; its handling of strided and interleaved accesses is described in [NRZ06].

VPlan¶

The vectorizer's decisions — which VF, which instructions widen, which are replicated per lane or predicated — used to be made on the scalar IR and applied in one monolithic code generator. VPlan makes the planned vector loop an explicit data structure: a hierarchical CFG of recipes, one plan per range of candidate VFs, which transformations can rewrite and the cost model can price before any IR is generated [LLVM-VPlan].

SLP vectorization¶

Larsen and Amarasinghe observed that straight-line code often contains superword-level parallelism (SLP): isomorphic operations on adjacent memory, like r[0] = a[0] + b[0]; r[1] = a[1] + b[1] — found by packing statements, independently of any loop [LA00]. LLVM's SLP vectorizer builds trees bottom-up from seeds (consecutive stores, reductions) and keeps a tree only if the target cost model says it is cheaper [LLVM-SLP].

Predication, masking and scalable vectors¶

Loops with if statements vectorize only after if-conversion turns control dependence into data dependence: both sides execute, and per-lane masks select results — the idea goes back to Allen, Kennedy, Porterfield and Warren [AKPW83]. Hardware masks (AVX-512, SVE, RVV) also allow masked loads and stores, and tail folding: the last partial vector iteration runs with a mask instead of a scalar remainder. Scalable vectors (Arm SVE [SVE17], RISC-V V) do not fix the vector length in the binary: LLVM represents them as <vscale x 4 x float>, where vscale is a run-time constant.

2. Definitions and algorithms¶

Loop vectorization¶

Definition 18.8.1 (Vectorization factor, lockstep execution, interleave count)

For a loop for \(i = 0\) to \(n - 1\) with body statements \(S_1, \dots, S_m\) (in order), vectorization by \(VF\) executes vector iterations \(j = 0, 1, \dots\), each covering scalar iterations \(jVF, \dots, jVF + VF - 1\) (the lanes), in lockstep: for \(p = 1..m\), statement \(S_p\) executes for all lanes before \(S_{p+1}\) executes for any; within one vector instruction all lanes read their operands before any lane writes. The interleave count \(IC\) unrolls the vector loop \(IC\) times, so one iteration of the final loop covers \(VF \cdot IC\) scalar iterations. The iterations \(\lfloor n / (VF \cdot IC) \rfloor \cdot VF \cdot IC, \dots, n - 1\) form the remainder, run by an epilogue (a vector loop with a smaller VF, a scalar loop, or both).

Theorem 18.8.2 (Legality of lockstep execution)

Vectorizing a loop by \(VF\) preserves its behavior if every dependence from an instance \(S_p(x)\) to an instance \(S_q(y)\) with \(0 < y - x < VF\) is forward: \(p < q\) (\(S_p\) strictly precedes \(S_q\) in the body). Dependences with \(y - x \ge VF\) and loop-independent ones (\(x = y\), \(p \le q\)) never constrain \(VF\).

Proof

The vector loop runs vector iterations in order and, inside one, statements in order. Consider a dependence \(S_p(x) \to S_q(y)\) (source first in the scalar loop, so \(x < y\), or \(x = y\) and \(p \le q\)). If \(x\) and \(y\) fall in different vector iterations, \(x\)'s runs first: preserved. That is always the case when \(y - x \ge VF\). If they fall in the same vector iteration: for \(p < q\), all lanes of \(S_p\) run before any lane of \(S_q\): preserved. For \(p = q\) and \(x = y\) it is one lane of one statement, in the scalar order (reads before writes). For \(p = q\), \(x < y\) in the same vector iteration, or \(p > q\), the lockstep order runs the sink before (or, for one vector instruction, simultaneously with, reading before writing) the source: violated — which is why the condition requires \(p < q\). When every dependence is preserved, every read sees the same last write as in the scalar loop, so all values and the final memory state agree (the argument of Theorem 18.7.4).

In LoopAccessAnalysis's terms: a dependence whose sink is later in the body than its source is Forward (safe for any VF); a Backward dependence with distance \(\delta\) elements is safe iff \(\delta \ge VF\) — which is Definition 18.6.16's "safe for VF".

Algorithm 18.8.3 (The loop vectorizer, as in LLVM)

Input: an innermost loop in loop-simplify and LCSSA form (Ch 15), with SCEV, LAA, TTI (target cost model).
Output: the loop with a vector version guarded by trip-count and memory checks, a vector epilogue and a scalar remainder; or the loop unchanged.
Precondition: a single exit (or a supported early exit), a computable trip count (Lesson 18.3), no unsupported instructions (calls without vector variants, volatile accesses).
Postcondition: the transformed loop computes the same results as the original (Theorem 18.8.11).
Invariant: every candidate VF is at most LAA's maximum safe VF (Theorem 18.8.2).

function LoopVectorize(L):
    Legal: classify every header phi: induction (Lesson 18.2), reduction (+, *, min, max, and/or/xor;
           FP only with reassociation allowed), first-order recurrence; otherwise give up
           blocks with conditions must be if-convertible (Algorithm 18.8.9)
           LAA(L) (Algorithm 18.6.17): safe / safe with runtime checks / unsafe; MaxSafeVF
    Cost:  for each VF in {1, 2, 4, …, min(MaxSafeVF, widest register / smallest element)}
               (and scalable VFs vscale × k if the target has them):
               cost(VF) ← Σ over instructions of TTI cost of the widened, scalarized or predicated form
           VF ← argmin cost(VF) / VF   (per scalar iteration); if VF = 1: give up
           IC ← choose by register pressure and trip count (small loops: interleave to hide latency)
    Emit:  if the trip count < VF·IC: skip to the epilogue
           runtime pointer checks from LAA (overlap tests, Theorem 18.6.18) → fail: scalar loop
           vector loop over ⌊n / (VF·IC)⌋·VF·IC iterations; reductions keep IC partial vectors,
           combined in the middle block
           epilogue: if profitable, a vector loop with a smaller VF; then the scalar remainder

LLVM's loop vectorizer: VF and IC, runtime checks, epilogue vectorization

Reproduce (clang 23.1.2):

cat > lv.c <<'X'
void saxpy(float *y, const float *x, float a, long n) {
  for (long i = 0; i < n; i++)
    y[i] = a * x[i] + y[i];
}
int sum(const int *a, long n) {
  int s = 0;
  for (long i = 0; i < n; i++)
    s += a[i];
  return s;
}
X
clang-23 -O2 -march=x86-64-v3 -gline-tables-only -Rpass=loop-vectorize -c lv.c -o /dev/null 2>&1 | grep remark
clang-23 -O2 -march=x86-64-v3 -fno-discard-value-names -S -emit-llvm lv.c -o lv.ll
sed -n '/^define.*@saxpy/,/^}/p' lv.ll | grep -E '^[a-z.]+:|min.*iters.check[0-9]* =|n.mod.vf =|n.vec[0-9]* =|bound[01] =|found.conflict =|load <' |
  sed -E 's/ +;.*//; s/, !tbaa ![0-9]+//'

Output (complete):

lv.c:2:3: remark: vectorized loop (vectorization width: 8, interleaved count: 4) [-Rpass=loop-vectorize]
lv.c:7:3: remark: vectorized loop (vectorization width: 8, interleaved count: 4) [-Rpass=loop-vectorize]
entry:
iter.check:
  %min.iters.check = icmp ult i64 %n, 4
vector.memcheck:
  %bound0 = icmp ult ptr %y, %scevgep10
  %bound1 = icmp ult ptr %x, %scevgep
  %found.conflict = and i1 %bound0, %bound1
vector.main.loop.iter.check:
  %min.iters.check11 = icmp ult i64 %n, 32
vector.ph:
  %n.mod.vf = and i64 %n, 28
  %n.vec = and i64 %n, 9223372036854775776
vector.body:
  %wide.load = load <8 x float>, ptr %1, align 4, !alias.scope !11
  %wide.load12 = load <8 x float>, ptr %2, align 4, !alias.scope !11
  %wide.load13 = load <8 x float>, ptr %3, align 4, !alias.scope !11
  %wide.load14 = load <8 x float>, ptr %4, align 4, !alias.scope !11
  %wide.load15 = load <8 x float>, ptr %5, align 4, !alias.scope !14, !noalias !11
  %wide.load16 = load <8 x float>, ptr %6, align 4, !alias.scope !14, !noalias !11
  %wide.load17 = load <8 x float>, ptr %7, align 4, !alias.scope !14, !noalias !11
  %wide.load18 = load <8 x float>, ptr %8, align 4, !alias.scope !14, !noalias !11
middle.block:
vec.epilog.iter.check:
  %min.epilog.iters.check = icmp eq i64 %n.mod.vf, 0
vec.epilog.ph:
  %n.vec20 = and i64 %n, 9223372036854775804
vec.epilog.vector.body:
  %wide.load24 = load <4 x float>, ptr %14, align 4, !alias.scope !11
  %wide.load25 = load <4 x float>, ptr %15, align 4, !alias.scope !14, !noalias !11
vec.epilog.middle.block:
for.body.preheader:
for.body.prol:
for.body.prol.loopexit:
for.cond.cleanup:
for.body:

What to notice: on AVX2 (x86-64-v3, 256-bit registers) both loops get \(VF = 8\) (8 floats or 8 i32 per register) and \(IC = 4\): one iteration of vector.body handles 32 elements with four independent loads per array — for sum, four independent vector accumulators, combined after the loop. y and x may overlap, so vector.memcheck tests \([y, y + 4n) \cap [x, x + 4n) = \emptyset\) exactly as Theorem 18.6.18 says (%scevgep \(= y + 4n\) in bytes), falling back to the scalar loop on conflict. The leftover iterations first go to a vectorized epilogue with \(VF = 4\) (vec.epilog.vector.body, <4 x float>), then to the scalar loop, which the runtime unroller (Lesson 18.5) has unrolled with a prol remainder of its own.

GCC's vectorizer on the same loops

Reproduce (gcc 14.2.0):

cat > lv.c <<'X'
void saxpy(float *y, const float *x, float a, long n) {
  for (long i = 0; i < n; i++)
    y[i] = a * x[i] + y[i];
}
int sum(const int *a, long n) {
  int s = 0;
  for (long i = 0; i < n; i++)
    s += a[i];
  return s;
}
X
gcc-14 -O3 -march=x86-64-v3 -fopt-info-vec-optimized -c lv.c -o /dev/null

Output (complete):

lv.c:2:22: optimized: loop vectorized using 32 byte vectors
lv.c:2:22: optimized:  loop versioned for vectorization because of possible aliasing
lv.c:2:22: optimized: loop vectorized using 16 byte vectors
lv.c:7:22: optimized: loop vectorized using 32 byte vectors
lv.c:7:22: optimized: loop vectorized using 16 byte vectors

What to notice: the same decisions in GCC's words: 32-byte vectors, versioning for possible aliasing (GCC's name for LLVM's vector.memcheck), and a second, 16-byte vectorized epilogue for both loops [GCC-Vect].

VPlan¶

Definition 18.8.4 (VPlan)

A VPlan for a loop and a range of candidate vectorization factors is a hierarchical CFG: VPBasicBlocks hold recipes, each describing how to generate code for one or more scalar instructions — widen (one vector instruction for all lanes), replicate (one scalar copy per lane, possibly predicated), widen-induction, reduction, blend (a select replacing a phi after if-conversion), interleave group, and so on — and VPRegionBlocks group blocks into single-entry single-exit regions (the vector loop region, replicate regions for predicated scalar code). Recipes define and use VPValues; live-ins such as VF, VF * UF and the vector trip count are symbolic until code generation. All VFs in a plan's range share the same recipes.

Algorithm 18.8.5 (VPlan-based planning and code generation)

Input: a loop that passed legality; candidate VFs (Algorithm 18.8.3).
Output: the chosen plan executed into IR.
Precondition: the legality analysis of Algorithm 18.8.3.
Postcondition: the IR produced for the chosen \(VF\) and \(UF\) implements the plan's recipes lane by lane (Theorem 18.8.12).
Invariant: each plan transformation maps a valid plan to a valid plan with the same meaning for every VF in its range.

function Plan(L, candidateVFs):
    partition candidateVFs into ranges on which every widening/scalarization decision agrees
    for each range R:
        P ← initial VPlan from L's scalar CFG (one recipe per instruction)
        apply VPlan-to-VPlan transformations: create loop regions, introduce masks and linearize
            (if-conversion), decide per memory op: widen / interleave group / gather / scalarize,
            create reduction and induction recipes, simplify, remove dead recipes, …
        plans ← plans ∪ {(R, P)}
    (VF, P) ← the VF and plan with the least cost per scalar iteration (VPlan-based cost model)
    choose UF (the interleave count); execute P: each recipe emits IR for VF lanes × UF parts

LLVM prints its VPlans

Reproduce (clang 23.1.2, opt 23.1.2):

cat > vp.c <<'X'
void saxpy(float *restrict y, const float *restrict x, float a, long n) {
  for (long i = 0; i < n; i++)
    y[i] = a * x[i] + y[i];
}
X
clang-23 -O2 -fno-vectorize -fno-unroll-loops -fno-discard-value-names -S -emit-llvm vp.c -o vp.ll
opt -passes=loop-vectorize -vplan-print-after=printOptimizedVPlan -disable-output vp.ll 2>&1 |
  sed -E 's/ \(!tbaa[^)]*\)//' |
  awk '/^VPlan .Initial/ { print; show = ($0 ~ /VF=\{2/) } show && /vector loop: \{/, show && /^}/'
opt -passes=loop-vectorize -pass-remarks=loop-vectorize -disable-output vp.ll 2>&1

Output (complete):

VPlan 'Initial VPlan for VF={1},UF>=1' {
VPlan 'Initial VPlan for VF={2,4},UF>=1' {
<x1> vector loop: {
vp<%3> = CANONICAL-IV

  vector.body:
    vp<%4> = SCALAR-STEPS vp<%3>, ir<1>, vp<%0>
    CLONE ir<%arrayidx> = getelementptr inbounds nuw ir<%x>, vp<%4>
    vp<%5> = vector-pointer inbounds nuw ir<%arrayidx>, ir<1>
    WIDEN ir<%0> = load vp<%5>
    CLONE ir<%arrayidx1> = getelementptr inbounds nuw ir<%y>, vp<%4>
    vp<%6> = vector-pointer inbounds nuw ir<%arrayidx1>, ir<1>
    WIDEN ir<%1> = load vp<%6>
    WIDEN-INTRINSIC ir<%2> = call llvm.fmuladd(ir<%a>, ir<%0>, ir<%1>)
    vp<%7> = vector-pointer inbounds nuw ir<%arrayidx1>, ir<1>
    WIDEN store vp<%7>, ir<%2>
    EMIT vp<%index.next> = add nuw vp<%3>, vp<%1>
    EMIT branch-on-count vp<%index.next>, vp<%2>
  No successors
}
remark: <unknown>:0:0: vectorized loop (vectorization width: 4, interleaved count: 1)

What to notice: two plans: \(VF = 1\) (the scalar plan, used for cost comparison and interleaving) and one plan for the range \(VF \in \{2, 4\}\) (SSE2's 128-bit registers hold at most 4 floats), whose vector loop region shows the recipes of Definition 18.8.4: the loads, the fmuladd and the store are WIDENed, the address computations stay scalar (CLONE of lane 0 plus a vector-pointer), the canonical IV steps by the symbolic VF * UF (vp<%1>) and exits at the symbolic vector trip count (vp<%2>). The cost model then picked \(VF = 4\); the interleave count is 1 because -fno-unroll-loops also disables interleaving. -vplan-print-after (a regular expression over transformation names) is available in release builds of LLVM 23; the names are those of the functions in VPlanTransforms.cpp.

SLP vectorization¶

Definition 18.8.6 (Packs, isomorphism, SLP tree)

Two instructions are isomorphic if they have the same opcode and type (and, for memory, the same kind of access). A pack is a tuple of \(k\) pairwise independent isomorphic instructions of one basic block (no member depends on another, directly or through memory); a pack of loads or stores is consecutive if its addresses are \(p, p + s, \dots, p + (k-1)s\) for the element size \(s\). An SLP tree is rooted at a pack of seeds and has, for every pack of non-load instructions, the packs of their \(r\)-th operands as children (a child that is not a valid pack becomes a gather leaf: its scalars are inserted into a vector).

Algorithm 18.8.7 (Bottom-up SLP vectorization, as in LLVM)

Input: a basic block, TTI.
Output: the block with profitable SLP trees replaced by vector instructions.
Precondition: SSA form; alias analysis for memory dependences.
Postcondition: the block computes the same values (Theorem 18.8.13).
Invariant: every non-gather node of a tree is a pack (Definition 18.8.6).

function SLP(B):
    seeds ← chains of consecutive stores (by base and offset, via SCEV), reduction trees,
            insertelement chains, …
    for each seed pack S (widest first, then halves):
        T ← BuildTree(S)                     # recursive on operands; stop at non-isomorphic
                                             # or dependent operands (gather) or loads
                                             # (consecutive: vector load; else gather)
        cost ← Σ over nodes (vector cost − Σ scalar costs) + gather/extract costs
        if cost < -slp-threshold (default 0): schedule the pack members together
                                             # (dependence-aware list scheduling)
                                             # and replace T by vector instructions

LLVM's SLP vectorizer on straight-line code, with an alternate-opcode pack

Reproduce (clang 23.1.2):

cat > slp.c <<'X'
void add4(double *restrict r, const double *restrict a, const double *restrict b) {
  r[0] = a[0] + b[0];
  r[1] = a[1] + b[1];
  r[2] = a[2] + b[2];
  r[3] = a[3] + b[3];
}
void mixed(double *restrict r, const double *restrict a) {
  r[0] = a[0] + 1.0;
  r[1] = a[1] * 2.0;     /* different opcode: an "alternate" pattern */
}
X
clang-23 -O2 -march=x86-64-v3 -gline-tables-only -Rpass=slp-vectorizer -c slp.c -o /dev/null 2>&1 | grep remark
clang-23 -O2 -march=x86-64-v3 -fno-discard-value-names -S -emit-llvm slp.c -o - |
  sed -n '/^define/,/^}/p' | grep -Ev '^(entry:|})' | sed -E 's/, !tbaa ![0-9]+//; s/ local_unnamed_addr.*//'
gcc-14 -O2 -march=x86-64-v3 -fopt-info-vec -c slp.c -o /dev/null

Output (complete):

slp.c:2:8: remark: Stores SLP vectorized with cost -12 and with tree size 4 [-Rpass=slp-vectorizer]
slp.c:8:8: remark: Stores SLP vectorized with cost -1 and with tree size 4 [-Rpass=slp-vectorizer]
define dso_local void @add4(ptr noalias nofree noundef writeonly captures(none) initializes((0, 32)) %r, ptr noalias nofree noundef readonly captures(none) %a, ptr noalias nofree noundef readonly captures(none) %b)
  %0 = load <4 x double>, ptr %a, align 8
  %1 = load <4 x double>, ptr %b, align 8
  %2 = fadd <4 x double> %0, %1
  store <4 x double> %2, ptr %r, align 8
  ret void
define dso_local void @mixed(ptr noalias nofree noundef writeonly captures(none) initializes((0, 16)) %r, ptr noalias nofree noundef readonly captures(none) %a)
  %0 = load <2 x double>, ptr %a, align 8
  %1 = fadd <2 x double> %0, <double 1.000000e+00, double poison>
  %2 = fmul <2 x double> %0, <double poison, double 2.000000e+00>
  %3 = shufflevector <2 x double> %1, <2 x double> %2, <2 x i32> <i32 0, i32 3>
  store <2 x double> %3, ptr %r, align 8
  ret void
slp.c:2:8: optimized: basic block part vectorized using 32 byte vectors
slp.c:8:8: optimized: basic block part vectorized using 16 byte vectors

What to notice: in add4 the seed is the four consecutive stores; their operands are four fadds (a pack), whose operands are consecutive loads of a and b (packs): the tree has 4 nodes and is replaced by two vector loads, one fadd <4 x double> and one store (cost \(-12\) = 12 units cheaper). mixed is not isomorphic — fadd and fmul — but LLVM packs it as an alternate node: both operations on the vector, then a shufflevector picking lane 0 from the sum and lane 1 from the product; still profitable (cost \(-1\)). GCC's basic-block SLP vectorizer does the same ("basic block part vectorized").

Predication, masking and scalable vectors¶

Definition 18.8.8 (If-conversion, masks, tail folding, scalable vectors)

If-conversion replaces control flow inside the loop body by data flow: each block \(b\) gets a predicate \(\mathit{pred}(b)\) (the conjunction of branch conditions on the path from the header, disjoined over paths), every instruction of \(b\) executes on all lanes, and a phi at a join becomes a blend (select on the predicates). A mask is a vector of booleans, one per lane; a masked load or store touches only the active lanes. Tail folding executes the remainder iterations within the vector loop, with the mask \(\{ \text{lane } k \text{ active} \iff jVF + k < n \}\) (LLVM: llvm.get.active.lane.mask(j·VF, n)). A scalable vector type <vscale x k x T> has \(\mathit{vscale} \cdot k\) elements, where \(\mathit{vscale} \ge 1\) is a constant of the running machine unknown at compile time (llvm.vscale() reads it); a scalable \(VF\) is written "vscale × k".

Algorithm 18.8.9 (If-conversion for vectorization)

Input: a loop body with forward branches only (the loop's own latch excepted).
Output: a single straight-line body with predicates, blends and masked memory operations.
Precondition: every instruction that may trap or have side effects either is safe to execute on inactive lanes (Lesson 18.1's speculation safety) or can be masked (load, store, and some calls).
Postcondition: for each lane, the active instructions compute what the scalar iteration would (Theorem 18.8.14).
Invariant: \(\mathit{pred}(b)\) is true on lane \(k\) iff scalar iteration \(jVF + k\) executes \(b\).

function IfConvert(body):
    for b in reverse post-order:                    # Ch 15: predecessors first
        pred(b) ← ∨ over predecessors p of (pred(p) ∧ condition of the edge p → b)
        for each instruction I of b:
            if I is a store: make it masked with pred(b)
            elif I is a load that is not safe to speculate: make it masked with pred(b)
            elif I may trap (division, …): make it safe (e.g. divide by 1 on inactive lanes) or give up
            else: execute I unconditionally
        for each phi at b with incoming (v_p from p): replace by select chains on pred(p)
    concatenate the blocks in reverse post-order

Algorithm 18.8.10 (Tail folding by masking)

Input: a vectorizable loop with trip count \(n\), a vector length \(VF\) (fixed or scalable).
Output: a vector loop with no scalar remainder.
Precondition: every memory access can be masked; reductions can ignore inactive lanes.
Postcondition: exactly the scalar iterations \(0..n - 1\) take effect (Theorem 18.8.14).
Invariant: at the top of vector iteration \(j\), lanes \(k\) with \(jVF + k < n\) are active.

function TailFold(L):
    mask ← active_lane_mask(0, n)                  # lane k active iff 0 + k < n
    index ← 0
    while mask has an active lane:
        vector body, with every load/store masked by mask and reductions blending by mask
        index ← index + VF                          # VF = vscale·k for scalable vectors
        mask ← active_lane_mask(index, n)

Masked stores for an if in the loop (AVX-512)

Reproduce (clang 23.1.2):

cat > pred.c <<'X'
void clampneg(float *a, long n) {
  for (long i = 0; i < n; i++)
    if (a[i] < 0.0f)
      a[i] = 0.0f;
}
X
clang-23 -O2 -march=x86-64-v4 -gline-tables-only -Rpass=loop-vectorize -S -emit-llvm pred.c -o pred.ll 2>&1 | grep remark
grep -oE 'call [^(]*@llvm\.masked\.[a-z]+[^(]*|fcmp olt <[^>]*>' pred.ll | sort | uniq -c

Output (complete):

pred.c:2:3: remark: vectorized loop (vectorization width: 8, interleaved count: 4) [-Rpass=loop-vectorize]
      1 call void @llvm.masked.store.v4f32.p0
      4 call void @llvm.masked.store.v8f32.p0
      1 fcmp olt <4 x float>
      4 fcmp olt <8 x float>

What to notice: the store executes only on some iterations, and storing unconditionally would write memory the scalar loop does not write (a data race in a multithreaded program, a fault if the page were read-only), so the store is not speculatable. If-conversion (Algorithm 18.8.9) computes the predicate as a vector compare (fcmp olt <8 x float>, four times for \(IC = 4\)) and turns the store into llvm.masked.store with that mask; the vectorized epilogue uses <4 x float>. The VF is 8, not 16, although x86-64-v4 has 512-bit registers: by default LLVM limits itself to 256-bit vectors on this target, and -mprefer-vector-width=512 makes the same loop vectorize with width 16. The load of a[i] needs no mask: it runs on every iteration in the scalar loop too.

Scalable vectors and tail folding on SVE

Reproduce (clang 23.1.2, cross-compiling to AArch64):

cat > sve.c <<'X'
void saxpy(float *restrict y, const float *restrict x, float a, long n) {
  for (long i = 0; i < n; i++)
    y[i] = a * x[i] + y[i];
}
X
for f in "" "-mllvm -tail-folding-policy=must-fold-tail"; do
  echo "== clang $f"
  clang-23 --target=aarch64-linux-gnu -march=armv9-a+sve -O2 $f -Rpass=loop-vectorize \
    -fno-discard-value-names -S -emit-llvm sve.c -o sve.ll 2>&1 | grep -o 'remark: .*'
  grep -E '^[a-z.0-9]+:' sve.ll | cut -d: -f1 | tr '\n' ' '; echo
done
sed -n '/^vector.body:/,/^$/p' sve.ll | sed -E 's/, !(tbaa|dbg|llvm.loop) ![0-9]+//g'

Output (complete):

== clang 
remark: vectorized loop (vectorization width: vscale x 4, interleaved count: 2) [-Rpass=loop-vectorize]
entry for.body.preheader vector.ph vector.body middle.block for.body.preheader13 for.cond.cleanup for.body 
== clang -mllvm -tail-folding-policy=must-fold-tail
remark: vectorized loop (vectorization width: vscale x 4, interleaved count: 1) [-Rpass=loop-vectorize]
entry vector.ph vector.body for.cond.cleanup 
vector.body:                                      ; preds = %vector.body, %vector.ph
  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
  %active.lane.mask = phi <vscale x 4 x i1> [ %active.lane.mask.entry, %vector.ph ], [ %active.lane.mask.next, %vector.body ]
  %2 = getelementptr inbounds nuw [4 x i8], ptr %x, i64 %index
  %wide.masked.load = tail call <vscale x 4 x float> @llvm.masked.load.nxv4f32.p0(ptr align 4 %2, <vscale x 4 x i1> %active.lane.mask, <vscale x 4 x float> poison)
  %3 = getelementptr inbounds nuw [4 x i8], ptr %y, i64 %index
  %wide.masked.load10 = tail call <vscale x 4 x float> @llvm.masked.load.nxv4f32.p0(ptr align 4 %3, <vscale x 4 x i1> %active.lane.mask, <vscale x 4 x float> poison)
  %4 = tail call <vscale x 4 x float> @llvm.fmuladd.nxv4f32(<vscale x 4 x float> %broadcast.splat, <vscale x 4 x float> %wide.masked.load, <vscale x 4 x float> %wide.masked.load10)
  tail call void @llvm.masked.store.nxv4f32.p0(<vscale x 4 x float> %4, ptr align 4 %3, <vscale x 4 x i1> %active.lane.mask)
  %index.next = add i64 %index, %1
  %active.lane.mask.next = tail call <vscale x 4 x i1> @llvm.get.active.lane.mask.nxv4i1.i64(i64 %index.next, i64 %n)
  %5 = extractelement <vscale x 4 x i1> %active.lane.mask.next, i64 0
  br i1 %5, label %vector.body, label %for.cond.cleanup

What to notice: with SVE the chosen VF is "vscale x 4": <vscale x 4 x float>, four floats per 128 bits of whatever vector length the machine has (128 to 2048 bits) — one binary for all of them. By default a scalar remainder loop remains (for.body); forcing tail folding (-tail-folding-policy=must-fold-tail, LLVM 23's option) removes it: the loop is just vector.ph, vector.body, and the exit. Every load and store is masked by %active.lane.mask, recomputed by llvm.get.active.lane.mask(%index.next, %n) — Algorithm 18.8.10 — and the loop continues while lane 0 is active (SVE's whilelo instruction sets exactly this mask).

3. Worked example¶

Loop vectorization on the running example¶

Take saxpy from the first box with \(VF = 8\), \(IC = 4\) (\(VF \cdot IC = 32\)), epilogue \(VF = 4\), and the guards it printed: iter.check (\(n < 4\) → scalar), vector.memcheck, vector.main.loop.iter.check (\(n < 32\) → epilogue directly), %n.vec \(= n \mathbin{\&} \sim 31\) (a multiple of 32), %n.mod.vf \(= n \mathbin{\&} 28\) (zero iff fewer than 4 iterations remain after the main loop), epilogue bound %n.vec20 \(= n \mathbin{\&} \sim 3\). Assuming no overlap:

\(n\)	main vector loop (×32)	vector epilogue (×4)	scalar remainder	total
3	skipped (\(n < 4\))	skipped	0, 1, 2	3
10	skipped (\(n < 32\))	iterations 0–7 (2 vector iterations)	8, 9	10
37	0–31 (1 iteration)	32–35 (\(37 \mathbin{\&} 28 = 4 \ne 0\))	36	37
64	0–63 (2 iterations)	skipped (\(n = n.vec\))	—	64
100	0–95 (3 iterations)	96–99 (\(100 \mathbin{\&} \sim 3 = 100\))	—	100

Legality (Theorem 18.8.2): with restrict, the only dependences are the loop-independent anti dependence between the load and the store of y[i] (\(x = y\)): no constraint. Without restrict, y could equal x + 1: then iteration \(i\) stores y[i] \(=\) x[i+1], which iteration \(i + 1\) loads — a dependence of distance 1 from the store (statement 2) to the load (statement 1), backward and \(< VF\): the lockstep execution would load the old value. That is what vector.memcheck rules out at run time.

VPlan on the running example¶

The printed plan for \(VF \in \{2, 4\}\) has 11 recipes in its loop region. Executing it for \(VF = 4\), \(UF = 1\): SCALAR-STEPS produces lane 0's index \(i\), CLONE computes the address &x[i], vector-pointer keeps it, WIDEN load becomes load <4 x float>, WIDEN-INTRINSIC becomes call <4 x float> @llvm.fmuladd.v4f32, WIDEN store becomes store <4 x float>, and the canonical IV adds VF * UF \(= 4\). For \(VF = 2\) the same recipes produce <2 x float>: that is why the two VFs share one plan, and why the cost model can compare them before generating any IR.

SLP vectorization on the running example¶

add4: seeds \(\{\)store r[0], …, store r[3]\(\}\) (consecutive, element size 8). Operands: \(\{\)fadd ×4\(\}\) (isomorphic, independent) → operands \(\{\)load a[0..3]\(\}\) and \(\{\)load b[0..3]\(\}\) (consecutive). Tree size 4, no gathers. Scalar cost: 4 stores + 4 adds + 8 loads; vector cost: 1 store + 1 add + 2 loads; the difference is the reported \(-12\) in TTI's units (assuming each operation costs 1 in both forms, \(16 - 4 = 12\)). If r[1] were a[1] + b[2], the b operand pack would not be consecutive: a gather node (4 scalar loads + inserts) would raise the cost.

Predication, masking and scalable vectors on the running example¶

clampneg with \(VF = 4\) on the lanes \(a[0..3] = (1.5, -2, 0, -0.5)\): mask \(=\) fcmp olt \(= (0, 1, 0, 1)\); the masked store writes 0.0 to lanes 1 and 3 only; a[0] and a[2] are not written — the same memory effect as the scalar loop. Tail folding for \(n = 10\), \(VF = 4\) (i.e. vscale \(= 1\) with "vscale × 4"): masks \((1,1,1,1)\) for index 0, \((1,1,1,1)\) for index 4, \((1,1,0,0)\) for index 8, then \((0,0,0,0)\) for index 12 — the loop exits after 3 vector iterations, 10 active lanes in total. With vscale \(= 2\) (256-bit SVE): \(VF = 8\), masks all-ones at 0 and \((1,1,0,\dots,0)\) at 8: 2 iterations — the same binary.

Try it

Rerun the first box with -march=x86-64 (SSE2) and -march=x86-64-v4 (AVX-512) and predict the VF each time from the register width before looking; add -ffast-math to a float sum and watch it vectorize (reassociation, Theorem 18.8.11's hypothesis).

4. Invariants and correctness¶

Loop vectorization¶

Theorem 18.8.11 (The vectorized loop preserves behavior)

Suppose LAA's checks and trip-count guards are emitted as in Algorithm 18.8.3, \(VF \le\) MaxSafeVF, every reduction is over an operation that is associative and commutative on the values involved (integer \(+\), \(\times\), min, max, bitwise ops modulo \(2^w\); floating-point only when reassociation is permitted), and inductions are recognized with their closed forms (Lesson 18.2). Then the transformed loop computes the same results as the original on every input.

Proof

On inputs where a check fails, the original scalar loop runs (versioning, Theorem 18.5.17). Otherwise the accesses through different groups do not overlap (Theorem 18.6.18), and within each group every dependence is forward or has distance \(\ge\) MaxSafeVF \(\ge VF\) (Definition 18.6.16), so the lockstep execution of the vector loop preserves every memory dependence (Theorem 18.8.2); interleaving by \(IC\) is unrolling the vector loop (Theorem 18.5.15) with its \(IC\) vector iterations run in order, so the same holds for \(VF \cdot IC\) consecutive iterations. Inductions are computed by their closed forms (lane \(k\) of vector iteration \(j\) gets \(\mathit{start} + (jVF + k)\cdot\mathit{step}\), the value the scalar loop has in that iteration — Lesson 18.3's CR evaluation). A reduction \(s = s \oplus v_i\) is computed as \(IC \cdot VF\) partial results \(s_{r} = \bigoplus_{i \equiv r} v_i\), combined at the end; by associativity and commutativity this equals \(v_0 \oplus \dots \oplus v_{n'-1}\) over the vectorized iterations, and the epilogue continues from it. The remainder iterations run afterwards, in order, from the resume values. So every value, and the final memory state, equals the scalar loop's.

VPlan¶

Theorem 18.8.12 (Executing a widened recipe)

Let a recipe widen a scalar instruction \(I\) whose operands are either loop-invariant (broadcast), widened values, or a consecutive address, and suppose no dependence connects different lanes of \(I\) (Theorem 18.8.2's condition). Then lane \(k\) of the vector instruction generated for vector iteration \(j\) and part \(u\) equals the value \(I\) has in scalar iteration \((j \cdot UF + u)\cdot VF + k\).

Proof

By induction over the recipes in plan order. Broadcast operands are the same in every lane and iteration. A widened operand has the right per-lane value by the induction hypothesis. The canonical IV of vector iteration \(j\) is \(j \cdot VF \cdot UF\), so SCALAR-STEPS gives part \(u\)'s lane-0 index \((j\,UF + u)VF\) and the vector-pointer of a consecutive address \(\{p,+,s\}\) addresses \(s\)-sized elements \(p + ((jUF+u)VF + k)s\) in lane \(k\) — the scalar addresses of those iterations. An element-wise vector operation applies the scalar operation lane by lane; a vector load or store reads or writes lane \(k\)'s address. With no inter-lane dependence, the order of the lanes inside the instruction is irrelevant. Hence each lane computes \(I\)'s scalar value.

SLP vectorization¶

Theorem 18.8.13 (Replacing an SLP tree)

If every node of an SLP tree is a pack (pairwise independent isomorphic instructions with the operand structure of Definition 18.8.6), and the pack members can be scheduled together — no instruction outside the pack depends on one member and is depended on by another — then replacing the tree by vector instructions (and extracting lanes still used by scalar code) preserves the block's behavior.

Proof

Scheduling the members of each pack adjacently is a reordering of independent instructions (the scheduling condition ensures that no dependence path passes between members through other instructions), so it preserves behavior. Once adjacent, \(k\) independent isomorphic instructions compute exactly the lanes of one vector instruction applied to the packed operands: a consecutive load pack reads the same bytes as one vector load, a consecutive store pack writes the same bytes (the members are independent, so their relative order does not matter), and an arithmetic pack computes lane \(r\) from the \(r\)-th operands — the \(r\)-th lanes of the child packs, by induction from the leaves (gathers insert the scalar values into lanes explicitly). An alternate pack computes both operations on all lanes and selects per lane, which is the same value. Extracts give remaining scalar users the lane they used before.

Predication, masking and scalable vectors¶

Theorem 18.8.14 (If-conversion and tail folding preserve behavior)

(a) If-conversion by Algorithm 18.8.9 preserves the behavior of every lane: the active lanes compute the scalar values and memory effects, and inactive lanes have no memory effect and do not trap. (b) Tail folding by Algorithm 18.8.10 executes exactly the scalar iterations \(0, \dots, n - 1\).

Proof

(a) By the invariant, \(\mathit{pred}(b)\) holds on lane \(k\) iff the scalar iteration executes \(b\): this holds for the header (always executed) and follows for \(b\) from its predecessors, because in a forward-branching body \(b\) executes iff one of its predecessors executes and branches to it — the disjunction that defines \(\mathit{pred}(b)\). An instruction executed unconditionally on an inactive lane computes a value that is either never used by an active lane (the blend at the join selects the value of the predecessor that the lane actually came from, which is the phi's incoming value in the scalar iteration) or is speculatable and cannot trap. Stores and non-speculatable loads are masked, so an inactive lane has no memory effect. So the active lanes see exactly the scalar computations. (b) Lane \(k\) of vector iteration \(j\) is active iff \(jVF + k < n\). The iterations \(0..n-1\) are covered, each by exactly one lane of one vector iteration; lanes with index \(\ge n\) are inactive and have no effect by (a)'s masking; the loop exits when the first lane of the mask is inactive, i.e. when \(jVF \ge n\) — after all active lanes ran. Combined with Theorem 18.8.11 for the lanes' order, the loop's result is the scalar one. The argument does not use the value of \(VF\), so it holds for every vscale.

5. Complexity¶

\(S\) = instructions in the loop body or block, \(V\) = number of candidate VFs, \(k\) = pack width, \(t\) = SLP tree size.

Technique	Analysis	Transformation	Worst case	Variables
Loop vectorization	LAA \(O(a^2)\) for \(a\) accesses (Lesson 18.6); cost model \(O(S \cdot V)\)	\(O(S \cdot VF \cdot IC)\) code	Runtime checks \(O(g^2)\) for \(g\) pointer groups (bounded by `runtime-memory-check-threshold`)	\(S\), \(V\), \(a\), \(g\)
VPlan	One plan per VF range: \(O(S)\) recipes each	Transformations \(O(S)\) each; execution \(O(S \cdot UF)\)	Number of plans \(\le V\)	\(S\), \(V\)
SLP vectorization	Seeds \(O(S)\); tree building \(O(t)\) per seed	\(O(t)\)	Trying all seed widths and orders: \(O(S^2)\) in bad blocks (LLVM limits with `slp-max-look-ahead-depth`, `slp-recursion-max-depth`, …)	\(S\), \(t\)
Predication, masking and scalable vectors	Predicates: one pass in RPO, \(O(S + E)\)	Masks and blends \(O(S)\)	Blends of \(p\) incoming values need \(p - 1\) selects	\(S\), \(E\)

Proposition 18.8.15 (Iterations in the main vector loop and the remainder)

With the guards of the worked example (\(VF \cdot IC = W\), epilogue \(VF_e \mid W\)), for \(n \ge W\) the main vector loop runs \(\lfloor n/W \rfloor\) iterations, the vector epilogue \(\lfloor (n \bmod W)/VF_e \rfloor\) iterations, and the scalar remainder \(n \bmod VF_e\) iterations.

Proof

%n.vec \(= n \mathbin{\&} \sim(W - 1)\) \(= W \lfloor n/W \rfloor\) for \(W\) a power of 2, so the main loop, stepping by \(W\) from 0, runs \(\lfloor n/W \rfloor\) times. The epilogue starts at \(W\lfloor n/W \rfloor\) and ends at \(n \mathbin{\&} \sim(VF_e - 1) = VF_e \lfloor n / VF_e \rfloor\), stepping by \(VF_e\): \((VF_e\lfloor n/VF_e \rfloor - W \lfloor n/W \rfloor)/VF_e = \lfloor (n \bmod W)/VF_e \rfloor\) iterations (since \(VF_e \mid W\)). The scalar loop runs from there to \(n\): \(n \bmod VF_e\) iterations. (Check: \(n = 37\), \(W = 32\), \(VF_e = 4\): \(1\), \(1\), \(1\).)

Pathological input. A loop with 30 pointer arguments that may alias: LAA would need up to \(\binom{30}{2} = 435\) overlap checks; LLVM gives up when more than runtime-memory-check-threshold comparisons (default 8) would be needed, and the loop stays scalar. restrict (or #pragma clang loop vectorize(assume_safety)) is the fix.

At scale. Vectorization is where most of -O2's speedup on numeric loops comes from, and also most of its code growth: every vectorized loop carries a vector body, an epilogue, a scalar remainder and checks — which is why the vectorizer's cost model, not legality, rejects most loops in practice.

Loop vectorization¶

Early-exit vectorization (LLVM handleEarlyExits): loops with a break depending on loaded data, when the loads are known dereferenceable — trade-off: more complex exit handling.
Outer-loop vectorization (-enable-vplan-native-path): vectorize an outer loop, keeping the inner loop scalar per lane — trade-off: experimental, VPlan-only.
Interleaved access groups [NRZ06]: a[2i], a[2i+1] loaded as one wide load plus shuffles — trade-off: shuffle cost.

VPlan¶

VPlan-based cost model: price recipes directly instead of scalar instructions — trade-off: must model every recipe kind.
Explicit vector length (EVL) recipes for RISC-V V: set vl each iteration instead of masking — trade-off: target-specific.

SLP vectorization¶

Horizontal reductions (slp-vectorize-hor): vectorize a[0] + a[1] + a[2] + a[3] into a vector add and a reduce — trade-off: FP needs reassociation.
Look-ahead operand reordering for commutative operations — trade-off: compile time.
ReVec (slp-revec): SLP on code that is already vector — trade-off: off by default.

Predication, masking and scalable vectors¶

Masked gathers/scatters for non-consecutive predicated accesses (AVX-512, SVE) — trade-off: slow on many cores.
Tail folding vs epilogue (-tail-folding-policy): fold on predicated ISAs, epilogue elsewhere — trade-off: mask overhead in every iteration vs code size.
VLA vs VLS: vector-length agnostic code (vscale) or code specialized for a known SVE length (-msve-vector-bits=256) — trade-off: portability vs constant-folding of VF.

7. In real compilers¶

Loop vectorization¶

LLVM

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp — LoopVectorizePass::processLoop (the driver), LoopVectorizationCostModel::computeMaxVF, LoopVectorizationPlanner::computeBestVF and selectInterleaveCount, LoopVectorizationCostModel::isEpilogueVectorizationProfitable and LoopVectorizationPlanner::selectBestEpiloguePlan, EpilogueVectorizerMainLoop [LLVM-LV]; llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp — LoopVectorizationLegality::canVectorize, canVectorizeMemory (LAA), canVectorizeWithIfConvert, canFoldTailByMasking [LLVM-LVLegality]; design notes in llvm/docs/Vectorizers.md [LLVM-Vectorizers] (LLVM 23.1.2).

GCC gcc/tree-vect-loop.cc (vect_analyze_loop, vect_transform_loop), tree-vect-data-refs.cc, versioning for alias in tree-vect-loop-manip.cc (GCC 15) [GCC-Vect].

Find where LLVM does it. Open LoopVectorize.cpp and find the option that turns epilogue vectorization off. Question: what is it called and what is its default? (Quiz lv-find-epilogue.)

The real-world boxes for this technique are in §2.

VPlan¶

LLVM

llvm/lib/Transforms/Vectorize/VPlan.h — VPlan, VPBasicBlock, VPRegionBlock, VPRecipeBase and the recipe classes (VPWidenRecipe, VPReplicateRecipe, VPBlendRecipe, …); llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp — the plan-to-plan transformations named in the box; the design in llvm/docs/VectorizationPlan.rst [LLVM-VPlan] (LLVM 23.1.2).

GCC has no VPlan equivalent; its vectorizer decides on SLP trees and loop statements directly (tree-vect-slp.cc builds SLP trees even for loops) (GCC 15) [GCC-Vect].

The real-world box for this technique is in §2.

SLP vectorization¶

LLVM

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp — SLPVectorizerPass::runImpl, vectorizeStores, vectorizeChainsInBlock, tryToVectorizeList; BoUpSLP::buildTree, getTreeCost, vectorizeTree; threshold slp-threshold (default 0) [LLVM-SLP] (LLVM 23.1.2).

GCC gcc/tree-vect-slp.cc — vect_slp_function, vect_slp_region, vect_build_slp_tree (GCC 15) [GCC-SLP].

The real-world box for this technique is in §2.

Predication, masking and scalable vectors¶

LLVM

LoopVectorizationLegality::blockNeedsPredication and canVectorizeWithIfConvert [LLVM-LVLegality]; VPlanTransforms::introduceMasksAndLinearize (if-conversion inside VPlan, named in the VPlan box's transformation list); tail folding policy options tail-folding-policy and AArch64's sve-tail-folding [LLVM-LV]; the IR intrinsics llvm.masked.load, llvm.masked.store, llvm.get.active.lane.mask, llvm.vscale are specified in llvm/docs/LangRef.rst (LLVM 23.1.2).

GCC uses "fully masked" loops on SVE and AVX-512 (LOOP_VINFO_FULLY_MASKED_P in tree-vect-loop.cc) (GCC 15) [GCC-Vect].

The real-world boxes for this technique are in §2.

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Loop vectorization	Innermost loops with analyzable accesses, reductions, inductions	Cost model per VF; LAA quadratic in accesses	Vector body + checks + epilogue + remainder; good remarks	Very high	Numeric loops at `-O2`
VPlan	Makes decisions explicit and composable	Linear per plan	Printable plans in release builds	High (framework)	LLVM's vectorizer internals
SLP vectorization	Straight-line isomorphic code, unrolled loops, struct fields	Near linear in practice	Tree-by-tree decisions, cost in remarks	High	Unrolled code, complex arithmetic, small structs
Predication, masking and scalable vectors	Loops with `if`s; no remainder; vector-length agnostic code	Mask computation in every iteration	Masked intrinsics, `vscale`	Medium on top of the vectorizer	AVX-512, SVE, RVV targets

Choose the loop vectorizer for loops (it is on at -O2); SLP complements it for straight-line code and the unrolled remainders. Predication is what makes loops with conditionals vectorizable; tail folding pays off on ISAs with cheap masks and for short trip counts. Scalable vectors are the only option for one binary across SVE/RVV implementations.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch18.yaml`)	Drill	Flashcard tag	Exercises
Loop vectorization	`lv-iterations`, `lv-find-epilogue`	`./course drill dependence-test` (distances decide the maximum safe VF)	`loop-vectorizer`	—
VPlan	`vplan-recipes`, `vplan-range`	none: VPlan is an internal representation; its behavior is observed in the real-world box	`vplan`	—
SLP vectorization	`slp-pack`, `slp-cost`	none: packing decisions are exercised by the quiz's computational questions	`slp`	—
Predication, masking and scalable vectors	`pred-mask`, `tail-fold-iterations`	none: masks are computed by hand in the quiz	`predication`	—

Pitfall

"The loop wasn't vectorized, so it must have a dependence" — usually wrong. Most rejections come from the cost model (the vector version is not cheaper), from possible aliasing that needs too many runtime checks, or from floating-point reductions without permission to reassociate. Read the remark (-Rpass-missed=loop-vectorize -Rpass-analysis=loop-vectorize) before changing the code.

References¶

See the chapter references.

Lesson 18.8 — Vectorization: the loop vectorizer, VPlan, SLP, predication and scalable vectors¶

1. Problem and motivation¶

Loop vectorization¶

VPlan¶

SLP vectorization¶

Predication, masking and scalable vectors¶

2. Definitions and algorithms¶

Loop vectorization¶

VPlan¶

SLP vectorization¶

Predication, masking and scalable vectors¶

3. Worked example¶

Loop vectorization on the running example¶

VPlan on the running example¶

SLP vectorization on the running example¶

Predication, masking and scalable vectors on the running example¶

4. Invariants and correctness¶

Loop vectorization¶

VPlan¶

SLP vectorization¶

Predication, masking and scalable vectors¶

5. Complexity¶

6. Variants and refinements¶

Loop vectorization¶

VPlan¶

SLP vectorization¶

Predication, masking and scalable vectors¶

7. In real compilers¶

Loop vectorization¶

VPlan¶

SLP vectorization¶

Predication, masking and scalable vectors¶

8. Comparison¶

9. Assessment¶

References¶