Compilers From Scratch — How Source Becomes Machine Code

One line of source code, followed all the way down through lexing, parsing, semantic analysis, intermediate representation, optimization, and code generation, until it comes out as a single machine instruction. Along the way: why bugs surface at -O2, and why your benchmark loop disappears.

The Interpreter and the Translator

A simultaneous interpreter renders speech as it arrives — fast, but with only the sentence just heard to work from. A translator takes the whole manuscript first. Slower, but able to revise, having read to the end.

An interpreter is the first; a compiler is the second. Compilers emit fast code not because they are clever but because they stand in a position to see everything before writing anything. Everything we call "optimization" is that revision pass.

The one line we'll follow all the way down

int f(int x) { return (x + 1) * 4 - 4; }

A human reads it as "add one to x, multiply by four, subtract four" — three operations. Turn optimization on, though, and this function becomes one instruction's worth of machine code. We'll find out exactly where three collapses into one by walking down six stages.

Those stages are lexing → parsing → semantic analysis → intermediate representation → optimization → code generation. The first three are the "frontend," the rest the "backend," and the seam between them earns its keep. With M languages and N target CPUs, the naive approach needs M×N translators; route everything through a shared intermediate representation and you need M+N. That is a large part of why LLVM is everywhere.

Stage 1 — Lexing: cutting a stream of characters into words

What a compiler first receives is nothing but a stream of characters. Lexing slices that stream into tokens, the smallest units that carry meaning, and throws away whitespace and comments.

( ident:x ) ( op:+ ) ( num:1 ) ( op:* ) ( num:4 ) ( op:- ) ( num:4 )

It looks mechanical, and it nearly is — except for one rule: maximal munch, meaning cut as long a token as you possibly can. Write a+++b in C and the lexer, having seen one +, does not stop; it swallows ++ and produces a ++ + b. It does not matter that you meant a + (++b). The rule decides the cut, not your intent, and that rule works without any knowledge of syntax whatsoever.

The implementation is a state machine compiled from regular-expression token definitions. Each character read advances the state once, so lexing finishes in time proportional to the input length.

import re
TOKEN = re.compile(r"\s*(?:(\d+)|([A-Za-z_]\w*)|([-+*/()]))")

def lex(src):
    pos = 0
    while pos < len(src):
        m = TOKEN.match(src, pos)
        if not m: raise SyntaxError(src[pos])
        pos = m.end()
        num, ident, op = m.groups()
        yield ("num", int(num)) if num else ("id", ident) if ident else ("op", op)

Stage 2 — Parsing: giving the sequence a shape

A token stream is flat. Evaluate x + 1 * 4 strictly left to right and you get (x+1)*4, when the right answer is x + (1*4). Parsing recovers that precedence and associativity from the flat sequence and rebuilds it as a tree. The structure of a language is written down as a grammar.

Read the arrow as "the thing on the left takes one of the forms on the right." An expression ($E$) is either "expression + term" or just a term ($T$); a term is either "term × factor" or just a factor ($F$); a factor is a parenthesized expression, a number, or a name. Those three levels of nesting are enough to force multiplication to sit deeper in the tree than addition. Precedence is the grammar's hierarchy. Put in words, those three lines say nothing more than what your hand already does when it reaches for parentheses: keep multiplication and division tucked inside addition and subtraction.

Transcribe equation (1) directly into code and the function nesting mirrors the grammar's levels. This is recursive descent parsing.

def parse_expr(ts):                 # E → T (('+'|'-') T)*
    node = parse_term(ts)
    while ts.peek() in ("+", "-"):
        op = ts.next()
        node = ("binop", op, node, parse_term(ts))   # stack on the left = left-associative
    return node

That while loop stacking to the left is exactly what makes a - b - c mean (a-b)-c. Turn it into recursion and you get right associativity, which changes what subtraction means. What comes out is an abstract syntax tree (AST).

        (-)
       /   \
     (*)    4
    /   \
  (+)    4
 /   \
x     1

Stage 3 — Semantic analysis: checking names and types

A tree exists, but nobody has yet asked whether it means anything. Is x declared? May an int be multiplied by 4? Does the result match the declared return type? Semantic analysis answers these, building a symbol table (name → type, declaration site, scope) as it goes. Most compile errors you meet day to day are this stage talking.

Which means code that clears this stage is guaranteed only to be "syntactically valid with no name or type contradictions." That is not a guarantee that it is correct, and the gap matters later. The tree that emerges carries a type on every node, and the backend reads those types to pick instructions.

Stage 4 — Intermediate representation: flattening the tree into one move at a time

A CPU executes one move at a time, so the tree gets flattened into a list of one-operation lines. This is the intermediate representation known as three-address code.

t1 = x  + 1
t2 = t1 * 4
t3 = t2 - 4
ret t3

t1 through t3 are virtual registers. Real machines have on the order of a dozen or two; at this stage we pretend there are infinitely many and let a later stage worry about it.

Nearly every modern compiler adds one more constraint here: SSA form (static single assignment), meaning every variable is assigned exactly once. The payoff is that when you look at t2, the question "where did this value come from?" has exactly one answer, in exactly one place. In naive code x gets overwritten repeatedly and that search happens over and over. Where branches merge and a value could have come from two places, a $\phi$ node marks the junction.

Stage 5 — Optimization: getting shorter without changing meaning

Now the revision pass — but the licence to revise has a precise boundary.

"The original program $P$ and its rewrite $P'$ must, for every possible input, agree on everything observable from the outside." $\mathrm{obs}$ (observable) covers output to the screen, writes to memory and files, system calls. Which means the converse: anything unobservable is fair game. Delete an intermediate computation, reorder the work — if it looks the same from outside, it is legal. C++ calls this the as-if rule. The line is a licence handed to the compiler, one which says same on the outside, free on the inside — and which is revoked the instant a difference leaks past $\mathrm{obs}$.

Holding that licence, a series of rewrites runs in turn.

• Constant folding: turn 3 * 4 into 12 at compile time
• Constant propagation: push a value known to be constant into its use sites
• Common subexpression elimination: compute something once and reuse it
• Dead code elimination: delete computations whose results nobody reads
• Inlining: paste a small function's body into the caller
• Strength reduction: swap an expensive operation for a cheap one

For the line we're following, what fires is algebraic simplification followed by strength reduction.

Expand the parentheses, watch +4 and −4 cancel, then replace the surviving 4x with a two-bit left shift. $\ll$ shifts bits leftward; shifting a binary number one place doubles it, so two places quadruples it. No multiplier needed, and the IR shrinks from three lines to one. Put in words: "add one, multiply by four, subtract four" and "multiply by four" give the same answer whatever you put in for $x$, and that multiply-by-four is just sliding the bits two places to the left.

t1 = x << 2
ret t1

Integer addition and multiplication are associative and distributive, which is what makes that rewrite valid — but the same is not true of floating point. Rounding error means $(a+b)+c$ and $a+(b+c)$ generally differ, so compilers forbid this reordering by default (-ffast-math is the switch that lifts the ban). "Algebraically equal" means different things for integers and for floats, and that is the most commonly misunderstood point in this stage.

Why the compiler doesn't go looking for the best possible code

"Why not just try every possible instruction sequence and keep the shortest?" Because of complexity: the candidates grow exponentially with the number of instructions.

Just how different a creature the exponential curve is gets covered in Complexity From Scratch. The point here is single: compile time is part of the product, so the compiler settles for a good answer found within a bounded search.

There are places where it need not give up entirely, though. Restricted to tree-shaped expressions, dynamic programming works: compute the best code for each subexpression once, store it in a table, and the exponential collapses to the number of cells in that table.

The idea itself is taken apart in Dynamic Programming From Scratch.

Stage 6 — Code generation: fitting infinite virtual registers into finite real ones

The last stage has three jobs.

Instruction selection maps fragments of the IR onto real CPU instructions. Should "times four" be a multiply, a shift, or — on x86-64 — the address-calculation instruction lea pressed into service? Strengths differ per CPU, so this part is held per target.

Register allocation packs the once-infinite t1, t2, … into real registers. The classic approach is graph coloring: connect variables that are live at the same time with an edge, then color the graph with $k$ colors so no two neighbors share one. Colors are registers, $k$ is how many you have. Coloring can't be solved efficiently in general, so real allocators approximate, and whatever doesn't fit gets pushed out to memory. That is a spill — and the reason a function with too many simultaneously live variables gets visibly slower.

Instruction scheduling reorders instructions, within the limits of their dependencies, so the CPU's assembly line never stalls. Why order changes speed at all is the subject of CPU Pipelines and Branch Prediction.

By the time it arrives here, the line we've been following is one computation and a return. On arm64 (Apple Silicon and friends) it comes out roughly like this.

f:
        lsl     w0, w0, #2      // shift the argument left by 2 = multiply by 4
        ret                      // return that value

On x86-64 you get a single instruction along the lines of lea eax, [rdi*4] rather than a multiply. Either way, three operations have been folded into one. Don't take my word for it — save the C above as f.c and run these to see what your own machine actually produces.

clang -O0 -S -o - f.c              # unoptimized: three operations, spelled out
clang -O2 -S -o - f.c              # optimized: the folded form
clang -O2 -S -emit-llvm -o - f.c   # peek at the IR (LLVM IR)

Reading -O0 and -O2 side by side is the shortest path to making any of this yours. If you'd rather stay in a browser, Compiler Explorer (https://godbolt.org/) does the same thing.

How this shows up on the job

Who touches it, and when. Engineers in domains where a single instruction matters — embedded, games, numerical computing — read -S output for hot functions. Build infrastructure owners decide the mix of -O2 / -Os (favor size) / -g (debug info) / LTO (link-time optimization) / PGO (optimization fed by a real execution profile). And the fastest-growing population lately works on ML compilers. What XLA, TVM, and torch.compile do to a computation graph is stages 4 through 6 exactly: lower to an IR, fuse operations and delete unneeded ones, emit GPU kernels. The shared vocabulary is not a coincidence.

Pitfalls that turn into incidents.

• Undefined behavior is fuel for the optimizer. A C/C++ compiler may assume UB never happens, so once you dereference a pointer it can conclude "this is not NULL" and delete a later NULL check outright. This is the classic "worked at -O0, broke at -O2," and it has caused real incidents in the Linux kernel.
• Your benchmark loop disappears. Computations whose results go nowhere are dead-code elimination's favorite target, and a spinning microbenchmark can be gone before you measure it. Write the result to a volatile variable or hand it to an external function to make it observable first.
• Don't drop volatile. Reads and writes to memory-mapped I/O look to a compiler like pointlessly re-reading the same address.
• Don't reach for -ffast-math casually. Computations whose ordering was arranged to cancel error get ruined by reordering.
• "Optimized out" while debugging. Inlining and eliminated variables make stack traces jump and locals vanish. Reproduce at -O1 or with -fno-inline.

What gets asked in design review. "It started crashing when we went to -O2 — what do you suspect?" First undefined behavior (signed integer overflow, strict-aliasing violations, uninitialized reads), then a run under UBSan / ASan. Suspecting a compiler bug comes last. "Why is inlining so effective?" Not only because the call overhead disappears, but because information from the caller flows into the body and unlocks the next round of constant propagation and dead-code elimination.

Takeaways

• A compiler is a six-stage assembly line: cut characters into words, build a tree, check meaning, flatten to one move at a time, revise, emit machine code
• Revision is permitted only where externally observable behavior doesn't change. That line is the as-if rule, and it's also why undefined behavior becomes fuel for the optimizer
• The best answer is deliberately abandoned. What actually happens is an exponential search space narrowed to "good enough" by dynamic programming and heuristics
• You can watch (x+1)*4-4 collapse into one instruction yourself by putting clang -O0 -S and clang -O2 -S side by side