Compilation Pipeline

The pipeline, stage by stage

Stage	Input	Output	Job
1. Lexer (scanner, tokenizer)	Source text	Token stream	Group characters into tokens (identifiers, keywords, operators, literals)
2. Parser	Token stream	Concrete syntax tree	Apply grammar rules; check syntactic structure
3. AST builder	Concrete tree	Abstract Syntax Tree	Drop irrelevant syntax (parens, semicolons); keep meaning
4. Semantic analysis	AST	Annotated AST	Type checking, name resolution, scope analysis
5. IR generation	Annotated AST	IR (e.g., LLVM IR)	Lower high-level constructs to low-level operations
6. Optimization	IR	Optimized IR	Constant folding, dead code, inlining, loop transforms, etc.
7. Code generation	Optimized IR	Assembly	Translate IR to target machine instructions
8. Assembler	Assembly	Object file (machine code + relocations)	Encode instructions to bytes
9. Linker	Object files + libraries	Executable	Resolve symbols, finalize addresses

Modern compilers blur stages — frontends produce IR directly without an explicit assembly intermediate; some optimizations work on AST instead of IR; LTO (link-time optimization) merges files for cross-module optimization. The 9-stage breakdown is conceptual.

Lexing and parsing

Take the source x = a + 42;. The lexer produces:

IDENT("x")  EQUALS  IDENT("a")  PLUS  INT(42)  SEMI

The parser consumes the token stream and builds a tree per the language grammar:

Assign
├── Target: Identifier("x")
└── Value:
    └── BinaryOp("+")
        ├── Left:  Identifier("a")
        └── Right: IntLiteral(42)

Lexers are typically finite state machines (regex-based). Parsers are often LL(k) or LR(1) for simple grammars; recursive descent for more complex languages. Modern parser generators (ANTLR, tree-sitter) handle ambiguous grammars and produce useful error messages.

From AST to IR

The AST is high-level — it has functions, classes, control structures. IR is low-level — basic blocks of instructions, branches, register-like SSA values. The "lowering" step does this translation.

For the C statement if (x > 0) y = 1; else y = -1;:

; LLVM IR (simplified)
entry:
  %cmp = icmp sgt i32 %x, 0
  br i1 %cmp, label %if.then, label %if.else

if.then:
  store i32 1, i32* %y
  br label %if.end

if.else:
  store i32 -1, i32* %y
  br label %if.end

if.end:
  ret void

Each function becomes a control-flow graph of basic blocks. Each basic block is a sequence of instructions that executes top-to-bottom with no branches in the middle. Optimizations operate on this CFG.

Common compiler optimizations

Optimization	Effect	Example
Constant folding	Compute constant expressions at compile time	3 * 4 → 12
Constant propagation	Replace uses of known constants	x = 5; y = x + 1; → y = 6;
Dead code elimination	Remove instructions whose results aren't used	x = expensive(); /* never used */ deleted
Common subexpression elimination	Compute repeated expressions once	(a+b)*c + (a+b)*d → t=a+b; t*c + t*d
Inlining	Replace function call with body	Eliminates call overhead; enables further optimization
Loop unrolling	Repeat loop body to reduce iteration overhead	for(i=0;i<4;i++) a[i]=0; → 4 stores
Loop invariant code motion	Move invariant computations out of loops	while(...){ x=a*b; ... } → x=a*b; while(...){ ... }
Strength reduction	Replace expensive ops with cheaper	x*2 → x<<1
Tail call optimization	Reuse stack frame for tail calls	Recursion uses O(1) stack instead of O(depth)

Production compilers (LLVM, GCC) ship hundreds of optimization passes. -O2 and -O3 are bundles of these passes; the tradeoff is compile time vs runtime speed.

Static compilation vs JIT

	Static compilation (AOT)	Just-in-time (JIT)
When code is compiled	Once, before execution	During execution, on hot paths
Optimizations	Profile-guided possible (rarely used in practice)	Profile-guided automatic (real runtime data)
Startup speed	Fast (binary loads, runs)	Slow (warm-up while JIT compiles)
Steady-state speed	Limited by static analysis	Often faster (specializes on actual types)
Memory	Smaller — no compiler in process	Larger — JIT compiler resident
Examples	C/C++/Rust/Go executables	JVM, V8, Python (PyPy), .NET

Modern languages mix approaches — V8 first interprets JS, then JIT-compiles hot functions, then re-optimizes them as more profiling data arrives. Java's HotSpot has tiered compilation (interpreter → C1 → C2 → optimized C2). Hybrid is the norm for dynamic languages.

When understanding the pipeline matters

• Debugging compiler errors. Each stage has distinct error messages; recognizing "lexer error" vs "parse error" vs "type error" tells you what part of your code to inspect.
• Reading assembly to optimize hot code. gcc -S or godbolt.org shows the assembly your code compiles to. Spotting unnecessary memory loads, inefficient branches, missed vectorization — all require reading the codegen output.
• Writing language tooling. Linters, formatters, refactoring tools all operate on AST. Understanding the AST shape of your language is a prerequisite.
• Knowing which optimizations are automatic. Don't manually inline a function the compiler already inlines. Don't manually constant-fold; the compiler does it. Focus optimization effort on what compilers can't do (algorithmic improvements, data layout).
• Cross-compilation and target tuning. Same source, different backends — x86 vs ARM, server vs embedded. The IR layer is what makes this practical.

Common compilation pitfalls

• Thinking -O3 is always faster. Aggressive optimization can be slower in cache-pressured workloads (more inlining → larger code → more I-cache misses). Profile both.
• Undefined behavior optimizations. C/C++ compilers exploit UB to skip checks ("this can't happen, so I'll assume it doesn't"). Signed integer overflow, null dereference, strict aliasing violations all get aggressively optimized. Use UB sanitizers (UBSan) to catch.
• Forgetting that JIT warmup matters. JVM benchmarks must run for 30+ seconds before measurements; first iterations are interpreter-paced. Microbenchmark frameworks (JMH) handle this; ad-hoc measurements often don't.
• Ignoring linker errors as "weird messages." "Undefined symbol" means a function/variable was declared but never defined — fix the linkage, not the calling code.
• Compile times exploding from template instantiation. C++ templates and Rust generics produce one specialization per type combination. Heavy template use can blow compile times to minutes; LTO/PGO compounds this.