Part 3 · Reading compiler output
The optimisations you will actually see
Six transformations account for most of the distance between your source and the output. Name them and the listing stops looking arbitrary.
What this lesson is trying to break (2)
- Optimisation is mostly about removing redundant instructions.
- A multiply by a strange constant is a hash or a magic number from the source.
The gap between your source and -O2 output is mostly six transformations. Learn
their signatures and most listings stop being mysterious.
1. Inlining — and why it matters most
Replacing a call with the callee’s body. The call overhead saved is trivial; the real gain is that an optimisation barrier disappeared.
Before inlining the compiler must assume the callee could do anything. After, it
can see everything, and every other optimisation below becomes applicable across
what used to be a boundary. This is why -O2 output can be dramatically shorter
than the sum of its functions, and why the binary call graph differs from the
source one (2.5).
2. Constant folding and propagation
Evaluating what is knowable at compile time, then carrying known values forward.
int f(void) { int x = 10; int y = x * 4; return y + 2; }compiles to mov eax, 42; ret. Folding computed 10*4+2; propagation carried
x = 10 into the multiply in the first place.
Combined with inlining this is startlingly powerful: a call chain four deep with
constant arguments can collapse to a single mov.
3. Strength reduction
Replacing an expensive operation with a cheaper equivalent. The one you must be able to recognise:
imul rax, rax, 1431655766 followed by shr / sar / sub
A division by a constant. Not a hash, not a magic number from the source.
Integer division is among the slowest instructions on the machine — tens of
cycles and poorly pipelined. So the compiler multiplies by a fixed-point
approximation of the reciprocal and shifts. 1431655766 is 0x55555556,
approximately 2³²/3, so this is x / 3.
The accompanying sar reg, 31 extracts the sign bit and the final sub
implements C’s round-towards-zero rule for negative values. Unsigned division
needs neither, so an unsigned divide is shorter — a rare case where choosing
unsigned genuinely produces less code.
Division by a power of two is simpler still: sar for signed, shr for
unsigned.
unsigned du(unsigned x) { return x / 3; }
int ds(int x) { return x / 3; }Compile both. Which produces fewer instructions?
The unsigned one, by two instructions.
The signed version must handle C’s requirement that -7 / 3 == -2 (round toward
zero) rather than -3 (round toward negative infinity). Getting that right needs
the sign bit extracted and a correction applied — hence the extra sar and sub.
The unsigned version just multiplies and shifts.
This is a small, real, and rarely-mentioned argument for using unsigned types for quantities that cannot be negative: not safety, but two fewer instructions per division. It is also a good example of how a language rule (rounding behaviour) shows up as instructions.
4. Common subexpression elimination
Computing a repeated expression once.
int g(int *p, int i) { return p[i]*2 + p[i]*3; }One load, not two — the compiler proves p[i] cannot change between them and
reuses it. When it cannot prove that, you get two loads, and the usual reason is
aliasing: if anything might write through another pointer in between, the
value must be re-read. That is 3.4’s main
obstacle too.
5. Dead-code elimination
Removing anything whose result is unobservable — including whole loops.
This is the classic microbenchmark failure. A loop that computes a sum and never
uses it is deleted entirely, and you measure an empty loop. Every serious
benchmarking harness exists partly to defeat this, with black_box in Rust
criterion or DoNotOptimize in Google Benchmark.
The rule to carry: if you did not observe the result, you did not measure the computation.
6. Tail-call optimisation
A call in final position becomes a jmp, reusing the frame
(2.5). No stack growth, and the frame vanishes from
traces.
Putting them together
static int scale(int x) { return x * 4; }
static int offset(int x) { return x + 10; }
int pipeline(void) {
return offset(scale(3));
}Three functions, two calls, arithmetic in each.
Two instructions:
"pipeline":
mov eax, 22
retInlining removed both calls. Constant propagation carried 3 inward. Folding
computed 3*4 = 12, then 12+10 = 22. Dead-code elimination removed the now-unused
function bodies.
Four optimisations, and the entire program became a constant.
This is worth sitting with, because it is the honest answer to “how much does this abstraction cost?” for a large class of code: nothing, because it is not there. It is also the mechanism behind Rust’s zero-cost claim, which 3.6 checks on a harder case.
A colleague benchmarks two implementations of a pure function and reports that both take 0.3 nanoseconds per call, which is faster than a single cache access.
Explain what almost certainly happened, name the optimisation responsible, and say what they should change.
What you should now be able to say
- Inlining matters because it removes an optimisation barrier, not because of call overhead.
- Folding and propagation together can collapse whole call chains to constants.
- Strength reduction: a multiply by a large odd constant plus shifts is a division; signed costs two more instructions than unsigned.
- CSE is blocked by possible aliasing.
- Dead-code elimination deletes unobserved work — the classic microbenchmark trap.
- Tail calls become jumps and disappear from stack traces.
Next: 3.4 — How a loop disappears.