Reading optimised code

At -O0 the compiler translates each statement on its own: every variable lives in a stack slot, every expression is evaluated exactly as written. At -O2 it treats your program as a specification and emits whatever is fastest that behaves the same — for every input that doesn't invoke undefined behaviour. Reading -O2 output is a skill of pattern recognition: once you know the dozen classic transformations, most listings stop looking like noise.

Open the Compiler pane next to any snippet below and follow along. All listings here are GCC 16 at -O2, Intel syntax.

1. The as-if rule

The standard only constrains observable behaviour: volatile accesses, I/O, and the final values written by the program. Everything else — which variables exist, in which order arithmetic happens, whether a function is called at all — is the compiler's choice. That is why

extern "C" int square_plus_one(int x) {
    int y = x * x;   // no stack slot, no separate "y"
    return y + 1;
}

compiles to two instructions plus ret:

square_plus_one:
    imul  edi, edi
    lea   eax, 1[rdi]
    ret

y never exists. lea eax, 1[rdi] (AT&T: leal 1(%rdi), %eax) computes an address-shaped expression rdi + 1 without touching memory — it is the compiler's favourite three-operand add.

2. Inlining, constant propagation, folding

Inlining copies a callee's body into the caller. That alone saves a call, but its real value is that it exposes the callee to the caller's facts:

static int scale(int x, int k) { return x * k + k; }
extern "C" int f(int x) { return scale(x, 8); }

After inlining, k is the constant 8, so x * 8 + 8 folds into a shift or a single lea:

f:
    lea   eax, 8[0+rdi*8]
    ret

Constant folding evaluates expressions whose operands are known; constant propagation pushes known values into later uses; together they cascade. A whole constexpr-free computation on literals often becomes one mov eax, <answer>.

3. Strength reduction: multiply with lea, shift and subtract

Multiplication by a constant rarely becomes imul. x86 addressing modes compute base + index*{1,2,4,8} + disp in one instruction, so:

imul with a constant is 3 cycles of latency on modern cores; lea and shifts are 1. Compilers only use these sequences when they're no longer than the multiply.

4. Division by a constant: magic numbers

div is one of the slowest integer instructions — 13 to 40+ cycles depending on the CPU and the operand size. Division by a compile-time constant never needs it. The trick: for a 32-bit unsigned n,

n / d  ==  (n * M) >> s        for a suitable "magic" M ≈ 2^s / d

computed with a 64-bit (or 128-bit) multiply so nothing overflows. For d = 10, GCC picks M = 3435973837 = ceil(2^35 / 10) and s = 35:

extern "C" unsigned div10(unsigned x) { return x / 10; }

div10:
    mov   eax, edi
    mov   edx, 3435973837
    imul  rax, rdx        ; 64-bit product
    shr   rax, 35         ; keep the top bits
    ret

Why is this exact? M = 2^35/10 + e with a small error e < 1. Then n*M / 2^35 = n/10 + n*e/2^35, and because n < 2^32 the error term stays below 1/10 — not enough to push the result across the next integer. The compiler picks the smallest s for which that bound holds (and falls back to a multiply-add-shift sequence for divisors like 7 where no 33-bit M works).

Signed division rounds toward zero, but an arithmetic shift rounds toward minus infinity, so signed code adds a fix-up for negative inputs:

sdiv10:                  ; int x / 10
    movsxd rax, edi
    sar    edi, 31       ; edi = (x < 0) ? -1 : 0
    imul   rax, rax, 1717986919
    sar    rax, 34
    sub    eax, edi      ; +1 for negative x
    ret

The same rounding issue makes signed division by a power of two more than a shift: x / 4 for int x adds 3 first when x is negative (lea eax, 3[rdi] / test / cmovns / sar eax, 2), and x % 8 needs a sar/shr pair to build the bias. For unsigned it's just shr or and. If you know a value is non-negative, say so — use an unsigned type, or [[assume(x >= 0)]] — and the fix-up disappears.

Division by a value known only at run time does use div. If the same divisor is used many times (hashing into a table of fixed size, converting units in a loop), you can compute the magic number once at run time and divide with a multiply — that's the build task.

5. Dead stores, hoisting and induction variables

extern int g(int);
extern "C" int dse(int* p) { *p = 1; *p = 2; return g(0); }

The store of 1 is dead: nothing can read *p between the two stores, so only mov DWORD PTR [rdi], 2 survives. (Make p a volatile int* and both stores stay — volatile accesses are observable.) The call to g is in tail position, so it becomes jmp g rather than call/ret.

Loop-invariant code motion hoists work that doesn't change between iterations:

extern "C" long licm(const long* a, long n, long k) {
    long s = 0;
    for (long i = 0; i < n; ++i) s += a[i] * (k * k + 3);
    return s;
}

k*k + 3 is computed once, before the loop (imul rdx, rdx / add rdx, 3). The loop also shows induction-variable rewriting: instead of computing a + i*8 each time, GCC walks a pointer (add rdi, 8) and compares it with a precomputed end pointer, so i disappears entirely.

6. What undefined behaviour buys the optimiser

The compiler may assume UB never happens. That's not malice; it's how it proves facts:

• Signed overflow can't happen, so for (int i = 0; i <= n; ++i) terminates and runs exactly n + 1 times — the compiler can widen i to 64 bits and use it directly as an index.

• Dereferencing null can't happen, so after int x = *p; the check if (!p) is always false and is deleted:

  extern "C" int nullchk(int* p) { int x = *p; if (!p) return -1; return x; }
  

  nullchk:
      mov  eax, DWORD PTR [rdi]
      ret
  

• Forward progress: a loop without side effects (no I/O, volatile or atomic accesses) may be assumed to terminate.

You can also hand the compiler a fact: [[assume(expr)]] (C++23) or if (!expr) __builtin_unreachable();. Both make it UB for the expression to be false — so they're only safe for facts you've actually guaranteed.

extern "C" int quarter(int x) {
    [[assume(x >= 0)]];
    return x / 4;          // now just: mov eax, edi / sar eax, 2
}

7. Devirtualisation

A virtual call is an indirect call [rax] through the vtable, and it blocks inlining. When the compiler can prove the dynamic type, it calls (and inlines) the final overrider directly. final is the cheapest proof:

struct Shape { virtual int sides(); };
struct Square final : Shape { int sides() override { return 4; } };
int count(Square& s) { return s.sides() + 1; }

_Z5countR6Square:
    mov  eax, 5
    ret

Without final, GCC still tries speculative devirtualisation: it compares the vtable slot with the overriders it knows about and inlines those, keeping a real call as the fallback.

8. GCC and Clang disagree — often

Two good compilers make different choices. Summing 0 + 1 + … + (n−1):

extern "C" long sumto(long n) {
    long s = 0;
    for (long i = 0; i < n; ++i) s += i;
    return s;
}

Clang recognises the closed form n(n−1)/2 and emits a multiply with no loop (mul / shld …). GCC 16 keeps a loop, unrolled by two. Neither is "the" answer: when a claim about codegen matters, say which compiler and which flags, and check it. Every codegen claim in this skill's exercises was checked against the compiler you're using.

9. A reading checklist

When a listing looks surprising, ask in order:

1. Was something inlined? A call that vanished, or code from another function appearing here.
2. What constants are known? Folded arithmetic, strength-reduced multiplies, magic-number divides.
3. What was proven unnecessary? Dead stores, removed checks (often via UB), hoisted computations.
4. How is the loop shaped? Pointer walking instead of i, unrolling, vector instructions (movdqu, paddd, addpd …), a scalar tail loop.
5. Which compiler and flags? -O2 vs -O3, -march, GCC vs Clang.

#include <cstdio>
// Constant folding is visible even from inside a program: at -O2 this whole
// loop folds to one constant (open the Compiler pane to see `mov esi, 5050`).
int main() {
    int s = 0;
    for (int i = 1; i <= 100; ++i) s += i;
    std::printf("%d\n", s);
}