Code Generation

The backend takes an IR that assumed unlimited registers and no particular machine, and produces instructions for one machine with sixteen of them. Four decisions do it: select, allocate, schedule, emit — and each one makes the next one harder.

Mapping IR operations onto instructions the machine actually has. Our backend selects `lea rax, [rbx+rbx]` for `x * 2` rather than `imul` — not because it is fewer bytes, but because it is three-operand and does not touch the flags.

Instruction selection implemented properly: tile the IR tree with instruction-shaped patterns. Maximal munch is greedy and fast; dynamic programming is optimal for the cost model; BURG-style generators write the matcher for you from a declarative table.

Reordering instructions so a pipeline has something to do while a long-latency operation completes — subject to every data dependence. On a big out-of-order core the hardware reorders anyway; static scheduling earns its keep on in-order cores and in what it does to register pressure.

A small window slid over the finished instruction stream, rewriting local patterns. Our backend's real peephole deletes `mov X, X` — an instruction that exists only because the register allocator happened to give a copy the same source and destination.

How to actually read `clang -S -o -`. The same two-line `add(a, b)` is `lea eax, [rdi+rsi]` on x86-64 System V and `add w0, w0, w1` on AArch64 AAPCS — and neither listing means anything without knowing which ABI produced it.

The last translation: `add rax, rbx` becomes the three bytes 48 01 D8. A REX prefix says the operands are 64-bit, one opcode byte says "add", and a ModR/M byte names both registers.

Four things, and none of them optional: the instruction set, the register file, the calling convention and the memory model. x86-64, ARM64, RISC-V and WebAssembly answer all four differently — and one of them has no registers at all.