Codegentypical

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.

The question

What does a compiler backend actually do after the optimizer has finished?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

Low-level IR: three-address instructions over an unbounded supply of virtual registers, already lowered so that every operation is close to something a machine can do, but not yet committed to any particular machine. It exists to answer "what work must happen, and in what dependence order" while deliberately refusing to answer "with which instruction" or "in which register" — because those two answers are only valid for one target, and the middle-end wants to be reusable across many.

What this phase may assume or do

The backend is entitled to assume the IR is well-typed, verified and semantically final: every transformation whose legality depended on language semantics has already run and already established its precondition. What the backend may still not do is change observable behavior — it may reorder two instructions only if neither depends on the other and neither may trap, it may keep a value in a register only if nothing else can observe that value's memory, and it must emit code that respects the calling convention exactly, because the code on the other side of a call was compiled separately and cannot be consulted.

Key points

The backend answers four questions the IR deliberately left open: which instruction, which register, in which order, which bytes.
The conventional order — select, allocate, schedule, emit — is a compromise; each phase would prefer to know the outcome of a later one.
Everything target-specific is concentrated here so that the middle-end can stay reusable, which is the whole economics of a shared compiler infrastructure.
Register allocation destroys the one-name-one-value property, and scheduling destroys source order. Both losses are what make optimized builds hard to debug.
Backend bugs do not produce diagnostics. They produce wrong answers and corrupted memory, far from the cause.

Four decisions, in order

The middle-end hands over a program that is correct and machine-agnostic. The backend has to make it executable, and it does so by answering four questions that the IR left open. Which target instruction implements this IR operation? Which physical register or stack slot does each virtual register live in? In what order should the chosen instructions be issued? And what bytes encode the result?

They are listed in that order because that is the order most backends run them, but the ordering is a compromise rather than a truth. Selection would like to know how much register pressure it is about to create. Allocation would like to know the final schedule, because the schedule determines which values are simultaneously live. Scheduling would like to know which registers were assigned, because a reused register creates a false dependence that did not exist in the IR. Every backend picks an order, and every order is wrong about something — which is [[phase-ordering]] wearing a backend hat.

The backend, as a sequence of representationstypical

Low-level IRbuild time
Three-address instructions over virtual registers, target-independent.
A dependence order and named intermediate values.
Selected machine IRbuild time
Target instructions, still over virtual registers.
A commitment to one instruction set — which operations exist and what shapes their operands take.
Portability. From here the program is about one machine.
Allocated machine IRbuild time
Target instructions over physical registers and stack slots.
A decision about where every live value physically is.
The one-name-one-value property. Two unrelated values now share rax at different times, so the instruction stream has dependences the IR did not.
Scheduled machine IRbuild time
The same instructions in a different order.
An issue order chosen for the target pipeline.
Correspondence with source order, which is what makes a stepping debugger jump around in optimized builds.
Assembly textbuild time
Mnemonics, operands, labels and directives — a textual program for the assembler.
Symbolic names for addresses that are not yet known.
Object codebuild time
Encoded bytes plus a relocation and symbol table.
The actual instruction encodings the fetcher will read.
The mnemonics. From here it is bytes, and only debug metadata says otherwise.

Read it asTwo of the three loses rows are the ones that hurt later. Losing the one-name-one-value property is why a debugger cannot always tell you what a variable holds. Losing source order is why a breakpoint on line 12 stops somewhere that looks like line 30. Both are the price of a backend doing its job, and both are what [[debugging-optimized-code]] is about.

Why the IR could not have done this

typicalThis four-phase split describes mainstream ahead-of-time backends such as LLVM's and GCC's. A baseline JIT tier often collapses selection and allocation into a single template-driven pass with no scheduling at all, because compile time is the user-visible cost there — V8's Sparkplug and JavaScriptCore's baseline JIT both do this. A tree-walking interpreter has no backend whatsoever.

It is tempting to ask why the middle-end does not simply emit instructions directly. The answer is the argument for [[why-ir-exists]], run in reverse: every optimization worth having is written against a representation that has no register limit and no instruction-shape constraints, because both of those turn a simple transformation into a case analysis over the target.

Consider constant folding. On the IR it is one rule: an operation whose operands are all constants becomes a constant. On x86-64 machine code it would need to know that add is two-operand and destructive, that the destination may be a memory operand, that folding might free a register and change the allocation, and that the immediate has to fit in 32 bits. None of that is about constant folding. All of it is about x86.

So the backend exists to absorb exactly the facts that would have contaminated everything upstream. That is also why a backend is the least reusable part of a compiler and the part that has to be rewritten for every target — which is the entire commercial argument for [[llvm]].

Selection absorbs "which operations this machine has, and in what operand shapes".
Allocation absorbs "how many registers there are, and which ones a call destroys".
Scheduling absorbs "how long each instruction takes and how many can issue at once".
Encoding absorbs "how the bytes are laid out", which nothing else ever needs to know.

Where a backend gets it wrong

Backend bugs have a distinctive signature: the program compiles, the program links, and the program returns wrong answers, or corrupts memory in a way that surfaces in an unrelated function. There is no type error to catch a register that was reused while still live, because by this point in the pipeline the type system has been discarded along with the names.

This is why backends are the part of a compiler most aggressively differential-tested. Two backends for the same IR should produce programs with the same observable behavior, and when they do not, one of them is wrong — see [[differential-testing]]. It is also why our own backend is a *teaching* backend and says so everywhere: it demonstrates the decisions honestly and it would not assemble.

What each backend phase can get wrong, and how it presentstypical

Phase	The internal mistake	What the engineer observes
Selectiontarget	A pattern matches an IR shape it does not actually implement	Arithmetic is subtly wrong — usually at a boundary value, because the wrong instruction has different overflow or sign behavior
Allocation	A register is reused while its previous value is still live	A value is silently corrupted; the wrong answer appears in a function several frames away
Schedulingtarget	Two instructions are swapped across a dependence the scheduler did not model	Works at `-O0`, fails at higher levels, and fails differently on a different CPU
Encodingtarget	A ModR/M byte names the wrong register field	An illegal-instruction fault, or — far worse — a legal instruction that does something else entirely
ABI compliancetarget	A callee-saved register is clobbered without saving it	The caller's local variable changes value across a call it does not control

How it works

The steps, in the order the compiler takes them.

The optimizer finishes and the IR is lowered to a form where every operation has some plausible target implementation — no more high-level constructs.
Instruction selection matches IR subtrees against a table of target instruction patterns, producing machine instructions that still use virtual registers.
Liveness analysis runs over the selected code, and register allocation assigns each virtual register a physical register or a stack slot, inserting spill code where it must.
Instruction scheduling reorders instructions within a basic block to suit the target pipeline, subject to the data dependences and to whatever register pressure the allocation created.
A peephole pass sweeps the final stream for local redundancies — most of them artefacts of the earlier phases rather than of the source.
The emitter prints assembly text, or the integrated assembler encodes instructions directly to bytes together with the relocations the linker will need.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A value is silently corrupted because a register was reused while still live, and the wrong answer surfaces three functions later with no crash and no diagnostic.
The generated code works on the development machine and faults on an older CPU, because the selector emitted an instruction from an extension the target does not have.
A function returns garbage only when called from code compiled by a different compiler, because the two disagree about the calling convention — see [[abi]].
Compilation time explodes on one enormous machine-generated function, because an allocation or scheduling heuristic that is near-linear on human-sized code is quadratic on a ten-thousand-instruction basic block.
The debugger reports a variable as "optimized out" in exactly the region the engineer wants to inspect, because it lives in a register the allocator reused.

When it helps

Reading disassembly with intent: knowing which phase produced which artefact tells you whether an odd-looking instruction is a selection decision, an allocation consequence or a scheduling one.
Diagnosing performance that does not match the source: extra mov instructions are almost always allocation, and stack traffic in a hot loop is almost always spilling.
Porting: knowing that all target knowledge lives in the backend tells you the size of the job when a new architecture appears.

When it hurts

Reasoning about performance from the instruction count. An out-of-order core executes several of these per cycle and stalls for hundreds of cycles on a cache miss; the count is a weak proxy for time — see [[out-of-order-execution]].
Assuming the backend is where speed comes from. Most of the win in a modern compiler was decided in the middle-end, and the backend mostly avoids giving it back.

What it costs

Every one of these is paid by something.

Concentrating target knowledge in the backend buys a reusable middle-end and a tractable port, and costs an abstraction boundary that is systematically wrong: the middle-end optimizes against a machine model that does not have register limits, so it can create pressure the backend then has to pay for in spill code.
Running the four phases in sequence buys implementation tractability and costs code quality, because each phase commits to decisions the next one would have made differently. Integrated approaches exist and are much harder to write and much slower to run.
A more aggressive backend buys runtime speed and pays in compile time and in debuggability — more reordering, more register reuse, less correspondence between what runs and what was written.

What else you could do

What a different compiler or language does instead, and when that is better.

A template JIT skips selection and scheduling entirely: each bytecode has a fixed machine-code template, stitched together in order. Compilation becomes near-instant and the code is perhaps two to five times slower than an optimizing backend would produce — which is the right trade when the alternative is the user waiting.
Emitting C instead of machine code hands the entire backend to someone else's compiler. Nim, early C++ implementations and many DSLs do this. You inherit a world-class backend and give up control over debug information, compile time and anything C cannot express.
Targeting a virtual instruction set — [[bytecode]] or [[webassembly]] — defers the machine-specific half to the consumer, buying portability and paying with an extra compilation step at load or run time.
Superoptimization searches exhaustively for the shortest instruction sequence with the required behavior. It produces better code than any heuristic backend and is far too slow for anything but small kernels or peephole table generation.

See it for yourself

The flag, dump or tool that shows you this directly.

Assembly from a real backend: clang -S -o - file.c or gcc -S -o - file.c. Add -O2 and diff against -O0 — most of the difference is the middle-end, not the backend.
LLVM between the phases: llc -print-after-all file.ll 2>&1 | less prints the machine IR after every backend pass, including before and after register allocation.
GCC's equivalent: gcc -fdump-rtl-all -O2 file.c writes one file per RTL pass into the working directory.
The bytes: objdump -d file.o disassembles what was actually encoded, which is the only view that cannot be lying to you.
Our assembly explorer at /compilers/codegen runs the real AtlasLang selector and allocator and shows the IR, the selection decisions and the emitted assembly side by side.

Plausible wrong readings

Stated the way a confident engineer states them.

"The backend is the part that makes code fast." The backend mostly avoids making it slow. Inlining, loop transformation and redundancy elimination all happened upstream on the IR.
"Instruction selection picks the fastest instruction." It picks an instruction that implements the operation under the constraints it can see. Whether it is fastest depends on the microarchitecture, which the selector models only approximately.
"Assembly is what the CPU executes." Assembly is text. The encoded bytes are what the CPU fetches, and the CPU then reorders and renames them anyway.
"If the assembly looks right, the codegen is right." Assembly that looks right can still violate the calling convention, and that failure only appears when someone else's code calls it.

Misconceptions

The claim, and what is actually true.

Code generation is the translation step, and everything before it is preparation.

Everything before it is where the program's shape was decided. Code generation is where the program is committed to one machine, which is a different kind of decision and a much less optimizable one.

The backend works on the AST.

It works on a low-level IR that has been through lowering, control-flow construction and the whole middle-end. The AST was discarded many phases earlier.

A good backend makes any IR fast.

A backend cannot recover information the middle-end destroyed or never had. Register pressure created by aggressive inlining upstream is paid for in spill code downstream, and no allocator can undo it.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

The optimizer produces a program that is correct but machine-agnostic: it assumes it can have as many named values as it wants and does not know what instructions exist. The backend turns that into something a specific CPU can run, by choosing instructions, choosing where each value lives, choosing an order, and finally writing bytes. Everything that is true only of one machine lives here.

practical

When optimized code looks wrong in a disassembly, attribute it to a phase before theorising. A stray mov between two registers is allocation. Loads and stores of stack slots in a tight loop are spilling. Instructions in an order that does not match the source is scheduling. An unfamiliar instruction doing something arithmetic — lea for a multiply, a shift for a divide — is selection. Each of those has a different fix, and only one of them is ever the compiler's bug.

advanced

The deep problem in backend design is that the four phases are mutually dependent and are run in sequence anyway. Selection determines register pressure; allocation determines false dependences; scheduling determines liveness, which determines pressure again. Approaches that attack the circularity — integrated selection and allocation via PBQP, SSA-based allocation that exploits the chordality of SSA interference graphs, register-pressure-aware scheduling — all exist, all improve code, and all cost compile time that most users would rather spend elsewhere. Which is why the naive sequence is still what ships.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalThe four-phase decomposition describes mainstream optimizing backends (LLVM, GCC, MSVC). Baseline JIT tiers collapse it to one template pass with no scheduling; the Go compiler folds selection and scheduling together and deliberately keeps its backend simple to protect compile speed. The phases are a way of thinking, not a law.

targetRegister counts, instruction shapes and calling conventions in this module are x86-64 System V unless stated. AArch64 AAPCS has 31 general-purpose registers, three-operand arithmetic and different argument registers; Windows x64 uses the same instruction set as System V and a different calling convention. Only the structure of the argument transfers between them.

simplifiedOur backend in src/compilers/sim/codegen.ts emits x86-64-flavoured assembly with no proper prologue beyond a frame pointer, no alignment handling, no relocations and 64-bit integers only. It would not assemble. It is faithful about the decisions — selection patterns, allocation results, parallel-copy sequencing — and about nothing else.

If you were asked this in an interview

The optimizer has finished. Name the decisions still to be made, and say why they cannot be made in any order you like.
You see extra mov instructions between registers in a hot loop. Which backend phase produced them and why?
Why is the backend the part of a compiler that has to be rewritten for a new architecture, and what stays?

Connections

Computer Architectureinstruction-set-architecture isa-vs-microarchitecture registers instruction-decode

Performancecpu-profiling

Domains that do not exist yet

Programming Languages & Runtime Internals — What the emitted code assumes about the runtime that will host it
A backend does not emit code in a vacuum: it emits calls to allocation, barriers for a collector and metadata for stack walking. The runtime's half of that contract is owned there; the compiler side is the metadata [[lowering]] and [[escape-analysis]] leave behind for it.