what this lab teaches

The loop vectorizer explains itself if you ask. Seven loops, each a classic reason for vectorizing or not: may-alias pointers, restrict, a floating-point reduction (illegal to reorder), the same reduction with a per-function permission, a loop-carried dependence, an early exit, and a gather. The remarks name the reason; the timings show what it costs; and one surprise shows that "more ISA" can make a loop SLOWER.

first, get the code

run this

$ git clone https://github.com/adit4443ya/debug_labs.git && cd debug_labs

then build it

run this

$ cd codegen && ./build.sh

produces bin/02_vectorize (baseline x86-64), bin/02_vectorize.native

walk it, one step at a time

run this

$ clang -O2 -c 02_vectorize.c -o /dev/null -Rpass=loop-vectorize -Rpass-missed=loop-vectorize -Rpass-analysis=loop-vectorize

what it printed on the machine that wrote this lab

axpy          : remark: vectorized loop (vectorization width: 4, interleaved count: 2)
axpy_restrict : remark: vectorized loop (vectorization width: 4, interleaved count: 2)
dot           : remark: loop not vectorized: cannot prove it is safe to reorder floating-point
                operations; allow reordering by specifying '#pragma clang loop vectorize(enable)'
                before the loop or by providing the compiler option '-ffast-math'
dot_pragma    : remark: vectorized loop (vectorization width: 4, interleaved count: 2)
prefix        : remark: loop not vectorized: unsafe dependent memory operations in loop.
                Use #pragma clang loop distribute(enable) to allow loop distribution ...
find_neg      : remark: loop not vectorized: Cannot vectorize potentially faulting early exit loop
gather        : remark: loop not vectorized: cannot identify array bounds
main's loops  : vectorized (the fill loop)

Read it: width 4 = four floats per 128-bit register; interleave 2 = two independent vector accumulators/streams per iteration. `axpy` vectorized even though y and x may alias: clang emitted a RUNTIME overlap check and two versions of the loop (versioning). `restrict` removes the check.

run this

$ clang -O2 -march=native -c 02_vectorize.c -o /dev/null -Rpass=loop-vectorize

what it printed on the machine that wrote this lab

axpy, axpy_restrict, dot_pragma : vectorized loop (vectorization width: 8, interleaved count: 4)
gather                          : vectorized loop (vectorization width: 8, interleaved count: 1)

With AVX2 the width doubles, and `gather` now vectorizes (vpgatherdd exists), while the cost model still refuses to interleave it.

run this

$ ../tools/pin.sh -q ./bin/02_vectorize

what it printed on the machine that wrote this lab

  axpy               0.603 ns/elem
  axpy_restrict      0.364 ns/elem
  dot (scalar)       0.985 ns/elem
  dot_pragma         0.244 ns/elem

run this

$ ../tools/pin.sh -q ./bin/02_vectorize.native

what it printed on the machine that wrote this lab

  axpy               0.431 ns/elem
  axpy_restrict      0.377 ns/elem
  dot (scalar)       1.940 ns/elem      <-- SLOWER than baseline
  dot_pragma         0.230 ns/elem
  Read it:
  - dot vs dot_pragma: 4x. The scalar reduction is a chain of dependent
    adds (2 cycles each on this core); the vector version keeps 8 partial
    sums (4 lanes x 2 interleave) and adds them at the end.
  - axpy vs axpy_restrict at baseline: 0.60 vs 0.36. The versioned loop
    pays its overlap check and a less favourable code layout; `restrict`
    (or `__restrict`, or passing spans you know are disjoint) is free
    speed when it is TRUE. When it is false, it is undefined behaviour.
  - THE SURPRISE: `dot (scalar)` got 2x SLOWER with -march=native. The asm:
      baseline: mulss (%rsi,%rcx,4),%xmm1 ; addss %xmm0,%xmm1 ; ...
      native:   vfmadd132ss (%rsi,%rcx,4),%xmm0,%xmm1 ; vfmadd231ss ... ; ...
    clang's default -ffp-contract=on fused the multiply-add into an FMA.
    FMA has 4-cycle latency here; the separate add had 2, and the multiply
    was off the critical path. Fewer instructions, longer dependency chain,
    half the speed. Lesson: the chain, not the instruction count, bounds a
    reduction; and "enable FMA" is not automatically a win.

THE VECTORIZER'S CHECKLIST (what the remarks are checking):
  1. Countable trip count (no early exit; find_neg fails here).
  2. No loop-carried dependence (prefix fails: a[i] needs a[i-1]).
  3. Memory does not overlap, or a runtime check can prove it (axpy).
  4. Operations are vectorizable on this target (gather needs AVX2).
  5. Reordering is allowed (FP reductions need reassociation permission).
  6. The cost model says it is profitable (interleave count 1 for gather).

the rules

V1. Always ask: -Rpass=loop-vectorize -Rpass-missed=loop-vectorize -Rpass-analysis=loop-vectorize. Never guess from the source. V2. Grant permissions narrowly: `restrict` on the pointers you know, `#pragma clang fp reassociate(on)` on the function you accept, not -ffast-math on the whole program (it also changes NaN/inf handling). V3. Verify the effect with a measurement AND by reading the loop body; a vectorized loop that runs slower (FMA chain, gather scatter cost) is not a success.

take it further

1. Compile with -ffp-contract=off -march=native: dot (scalar) returns to ~1 ns. Now you have proof the FMA was the cause. 2. Change `find_neg` to count negatives without returning early: it vectorizes. Compare the two remarks. 3. `#pragma clang loop vectorize_width(8)` on axpy at baseline: the vectorizer can't (no AVX); read the remark it gives you. ============================================================

read the source · codegen/02_vectorize.c

#include "../tools/bench.h"

/* 1. May alias: y and x could overlap -> clang emits a runtime overlap check (loop versioning), then vectorizes. */
void axpy(float *y, const float *x, float a, size_t n) { for (size_t i = 0; i < n; i++) y[i] = a * x[i] + y[i]; }
/* 2. restrict: no check needed. */
void axpy_restrict(float *restrict y, const float *restrict x, float a, size_t n) { for (size_t i = 0; i < n; i++) y[i] = a * x[i] + y[i]; }
/* 3. FP reduction: reordering additions changes rounding -> NOT vectorized unless allowed. */
float dot(const float *a, const float *b, size_t n) { float s = 0; for (size_t i = 0; i < n; i++) s += a[i] * b[i]; return s; }
/* 4. Same reduction, reassociation allowed for THIS function only. */
float dot_pragma(const float *a, const float *b, size_t n) {
#pragma clang fp reassociate(on)                 /* must be first in the block; applies to the whole function body */
    float s = 0;
    for (size_t i = 0; i < n; i++) s += a[i] * b[i];
    return s;
}
/* 5. Loop-carried dependence: a[i] needs a[i-1] from THIS iteration -> cannot vectorize. */
void prefix(int *a, size_t n) { for (size_t i = 1; i < n; i++) a[i] += a[i - 1]; }
/* 6. Early exit: trip count unknown up front -> vectorizer gives up (no early-exit vectorization for this shape). */
int find_neg(const int *a, size_t n) { for (size_t i = 0; i < n; i++) if (a[i] < 0) return (int)i; return -1; }
/* 7. Indirect (gather) access: legal, but is it profitable on this target? The cost model decides. */
void gather(int *out, const int *in, const int *idx, size_t n) { for (size_t i = 0; i < n; i++) out[i] = in[idx[i]]; }

int main(int argc, char **argv) {
    size_t n = argc > 1 ? strtoull(argv[1], 0, 10) : (1u << 20);   /* 1M floats = 4 MB, fits in L3 */
    float *x = malloc(n * 4), *y = malloc(n * 4);
    for (size_t i = 0; i < n; i++) { x[i] = (float)(i & 255) * 0.5f; y[i] = 1.0f; }
    int reps = 200; uint64_t t0; float r = 0;
    t0 = bench_ns(); for (int k = 0; k < reps; k++) axpy(y, x, 0.999f, n); BENCH_KEEP(y);
    printf("axpy            %8.3f ns/elem\n", (double)(bench_ns() - t0) / ((double)n * reps));
    t0 = bench_ns(); for (int k = 0; k < reps; k++) axpy_restrict(y, x, 0.999f, n); BENCH_KEEP(y);
    printf("axpy_restrict   %8.3f ns/elem\n", (double)(bench_ns() - t0) / ((double)n * reps));
    t0 = bench_ns(); for (int k = 0; k < reps; k++) r += dot(x, y, n); BENCH_KEEP(r);
    printf("dot (scalar)    %8.3f ns/elem\n", (double)(bench_ns() - t0) / ((double)n * reps));
    t0 = bench_ns(); for (int k = 0; k < reps; k++) r += dot_pragma(x, y, n); BENCH_KEEP(r);
    printf("dot_pragma      %8.3f ns/elem\n", (double)(bench_ns() - t0) / ((double)n * reps));
    return 0;
}

◇

Finish the lab: write the evidence note

A lab is done when you can say what it showed on your machine — not when you have read it.

Vectorization remarks — why a loop did or did not vectorize

Which role are you preparing for?