Part 3 · Reading compiler output
How a loop disappears
Your counter is gone, the body is duplicated four times, and the exit test compares addresses. Here is what happened and why.
What this lesson is trying to break (3)
- A for loop compiles to a loop with a counter.
- Unrolling is always a win.
- The compiler will vectorise anything simple.
The for loop is where source and output diverge most, and where the divergence
is most systematic.
Four things that happen to loops
Induction-variable strength reduction. The counter goes away. Instead of
i plus base + i*4, the compiler walks a pointer and compares against a
precomputed end address. You saw this in 1.5.
Loop-invariant code motion (LICM). Anything constant across iterations moves out.
Unrolling. The body is duplicated so each iteration does 2, 4 or 8 elements, reducing loop overhead and exposing parallelism. Requires a “tail” to handle a count that is not a multiple of the unroll factor — which is why unrolled loops have an untidy epilogue.
Vectorisation. The body is rewritten to process several elements per instruction using vector registers. This is the big one, and it is also the one that usually fails.
void scale(float *out, const float *in, int n) {
for (int i = 0; i < n; i++) out[i] = in[i] * 2.0f;
}About as simple as a loop gets. Compile it for x86-64.
It vectorises, and the output is much bigger than you expect — often 40+ instructions for a three-line loop.
The structure you will see:
- a guard for
n <= 0 - an alias check — comparing
outandinto see whether the ranges overlap - a scalar fallback loop, used if they do overlap
- an alignment prologue, handling elements until a nice boundary
- the vector body —
movups/mulpsonxmmregisters, four floats at a time - a scalar epilogue for the leftover elements
Points 2 and 3 are the interesting part. out and in are separate parameters,
and nothing stops a caller passing overlapping ranges. If they overlap, processing
four at a time gives different results from processing one at a time. So the
compiler emits both versions and chooses at run time.
Add restrict to both pointers — float *restrict out, const float *restrict in
— and recompile. The alias check and the scalar fallback disappear, and the
function gets substantially smaller.
That is the concrete, mechanical cash value of aliasing information. And it is
where Rust has a real structural advantage: &mut is a no-alias guarantee, so
rustc emits noalias and gets this for free, with no annotation and no way to
get it wrong. Everything the borrow checker put you through buys exactly this.
a scalar loop, then a vector loop, then another scalar loop
A vectorised loop with its prologue and epilogue.
The first scalar section handles elements up to an alignment boundary or is an alias fallback; the middle does the real work several lanes at a time; the last handles the remainder.
When reading, find the vector body and ignore the rest — the two scalar sections handle at most a handful of elements between them, however long they look.
Why vectorisation fails
Worth knowing by name, because “why didn’t it vectorise?” is a question you can actually answer.
Varies: the single obstacle preventing vectorisation
| Loop | Vectorises? | Why not |
|---|---|---|
out[i] = in[i] * 2 | Yes, with a runtime alias check | — |
out[i] = in[i] * 2 with restrict | Yes, cleanly | — |
sum += a[i] (int) | Yes | Integer addition is associative, so reordering is legal |
sum += a[i] (float) | No | FP addition is not associative — reordering changes the result |
a[i] = a[i-1] + 1 | No | Loop-carried dependency — iteration i needs i−1 |
if (a[i] > 0) sum += a[i] | Often yes | Becomes a masked add, if the ISA supports it |
The float-reduction row is the one that surprises people most: the integer version vectorises and the float version does not, from identical-looking source. -ffast-math permits the reordering, at the cost of exact reproducibility.
The float row deserves emphasis because it is a genuine correctness constraint,
not compiler timidity. (a + b) + c and a + (b + c) can differ in floating
point. Vectorising a sum means computing four partial sums and combining them,
which is a different grouping and therefore possibly a different answer. The
compiler will not silently change your results, so it refuses — unless you tell it
you do not mind, with -ffast-math or -fassociative-math.
And you can just ask why. Add -fopt-info-vec-missed and gcc reports its
reasoning in English. This is the most useful and least known diagnostic in this
area.
Unrolling is not free
Unrolling costs code size, which costs instruction-cache pressure, and it increases register pressure, which can cause spills (1.1). An over-unrolled loop that spills every iteration is slower than the tight version.
Which is why the shape to look for in a hot loop is not “is it unrolled” but “is it storing and reloading the same stack addresses every iteration”. That is spilling, and it means the unroll factor was too aggressive.
You have a float reduction that will not vectorise:
float sum(const float *a, int n) {
float s = 0;
for (int i = 0; i < n; i++) s += a[i];
return s;
}Give two different ways to make it vectorise, and state precisely what each one costs you. One of them changes the answers you get; say by roughly how much and whether you would accept it.
What you should now be able to say
- Loop counters are replaced by pointer walks; exit tests compare addresses.
- LICM hoists invariants; aliasing is what usually blocks it.
- A vectorised loop has a scalar prologue, vector body, scalar epilogue — read the middle.
- Vectorisation fails for nameable reasons: aliasing, FP non-associativity, loop-carried dependencies, unknown trip count.
restrict(and Rust’s&mut) removes the alias check entirely.-fopt-info-vec-missedtells you why in English.- Unrolling costs code size and registers, and can cause spills.