Compilation §

Compilation studies how source code is transformed into executable programs. It is relevant whenever a program must be translated from one representation to another for execution on a target architecture.

Authoritative sources

• Compilers: Principles, Techniques, and Practice (Aho, Lam, Sethi, Ullman)
• Modern Compiler Implementation in ML (Appel)

Compiler pipeline §

A compiler transforms source code into machine code through a sequence of passes:

Front-end: parsing and type checking §

The front-end translates source text into a structured, type-checked representation. It is target-independent: the same front-end can feed any back-end.

• Tokenizer (lexer): splits the character stream into tokens (identifiers, literals, operators, keywords). See Language Theory for grammar and tokenization details.
• Parser: builds an Abstract Syntax Tree (AST) from the token stream using a grammar (LL, LR, recursive descent). See Language Theory for parser construction.
• Type checker: walks the AST, infers or verifies types, and rejects ill-typed expressions. See Language Theory for type systems and Hindley-Milner inference.

Intermediate Representations §

An intermediate representation (IR) is a machine-independent, structured form of the program that sits between the front-end and the back-end. IRs exist because:

1. The AST is too high-level for optimization (it mirrors source syntax, not computation).
2. The target ISA is too low-level to be portable (each architecture has different registers, opcodes, and calling conventions).
3. A middle form lets the compiler apply optimizations once, independent of the target.

Three-address code (TAC) §

Every operation is expressed with at most three operands: $x \leftarrow y \ op \ z$. This eliminates nested expressions and makes data dependencies explicit.

// Source:  c = (a + b) * (a - b)
// TAC:
  t1 = a + b
  t2 = a - b
  c  = t1 * t2

Static Single Assignment (SSA) form §

In SSA, every variable is assigned exactly once. Multiple logical assignments to the same variable become distinct SSA names ($x_1, x_2, x_3$), joined by phi (φ) nodes at control-flow merge points.

// Source:
//   if (cond) { x = 1; } else { x = 2; }
//   y = x + 3;
// SSA:
  x1 = 1
  x2 = 2
  x3 = φ(x1, x2)   // at the merge point
  y  = x3 + 3

SSA makes data-flow analysis (liveness, reaching definitions, constant propagation) linear-time and local, because each variable has a single definition site.

Optimization passes §

Optimization transforms the IR to reduce execution time, code size, or power consumption while preserving semantics. Passes are organized by the scope of analysis they perform.

Local (basic-block) optimizations §

• Constant folding: evaluate constant expressions at compile time ($x = 3 + 4$ → $x = 7$).
• Dead code elimination: remove instructions whose results are never used.
• Common subexpression elimination (CSE): compute a repeated expression once and reuse the result.

Loop optimizations §

• Loop-invariant code motion (LICM): hoist computations that do not change across iterations out of the loop.
• Loop unrolling: replicate the loop body $k$ times to reduce branch overhead and expose instruction-level parallelism.
• Vectorization: transform scalar loop iterations into SIMD instructions that process multiple data elements per instruction. See CPU Architecture for SIMD register details.

Global (whole-function) optimizations §

• Inlining: replace a function call with the callee’s body, eliminating call overhead and exposing further optimization opportunities.
• Partial evaluation: specialize the program for known inputs, eliminating dead branches.
• Register allocation: assign virtual registers (variables) to the limited set of physical CPU registers. See Memory Management for the register-vs-memory hierarchy.

Code generation §

Code generation is the final, target-specific phase: it translates the optimized IR into a sequence of instructions for a specific ISA.

Instruction selection §

Match IR patterns to target instructions. This is a tree-covering or dynamic-programming problem: find the cheapest sequence of instructions that computes the same result as the IR expression tree.

// IR:  t1 = a + b
//      t2 = t1 * 4
// x86-64 selection:
  mov  rax, [a]
  add  rax, [b]      ; t1 = a + b
  shl  rax, 2        ; t2 = t1 * 4  (shift is cheaper than imul by power of 2)

Instruction scheduling §

Reorder instructions within a basic block to hide pipeline stalls (data hazards, branch mispredictions). The scheduler respects data dependencies but may reorder independent instructions to fill pipeline slots. See CPU Architecture for pipelining and out-of-order execution details.

Peephole optimization §

Examine a small window of consecutive instructions and replace them with a shorter or faster equivalent:

• $x = x + 0$ → delete (no-op).
• $x = x * 1$ → delete.
• $push x; pop x$ → delete.
• $x = x << 1$ → $x = x + x$ (on some ISAs, addition is faster than shift).

Linking §

The linker combines multiple object files (and libraries) into a single executable or shared library. It is distinct from the loader, which maps the final binary into memory at process start.

Static linking §

The linker resolves all symbol references at build time, copying the needed code from libraries (e.g., libc.a) directly into the executable. The result is a self-contained binary with no runtime library dependencies.

Dynamic linking §

The linker records references to shared libraries (e.g., libc.so) and the dynamic linker (runtime loader, e.g., ld-linux.so) resolves them at process start or on first use. This reduces binary size and allows multiple processes to share one copy of the library in memory.

Symbol resolution and relocation §

Each object file exports symbols (functions, globals) and imports symbols it references. The linker:

1. Merges symbol tables from all input objects.
2. Resolves each undefined symbol to exactly one definition (or reports an error).
3. Performs relocations: patches placeholder addresses in the code and data sections with the final addresses assigned by the linker.

Linking vs. loading §

• Linking (static or dynamic): resolves symbols and produces a final binary with fixed section layout. Happens at build time (static) or process start (dynamic).
• Loading: the OS kernel maps the binary’s sections into the process’s virtual address space, sets up the stack, and transfers control to the entry point (_start). See Memory Management for virtual memory and the process address space layout.

Execution models §

Three models govern when and how compilation happens relative to execution:

• AOT (Ahead-Of-Time): the entire program is compiled to native machine code before execution. Fast startup, no runtime overhead. Used by C, C++, Rust, Go.
• JIT (Just-In-Time): the program is compiled to bytecode, then the runtime compiles hot code paths to native machine code during execution. Slower startup, but can optimize based on runtime profiles (e.g., which branches are taken, which types are actually used). Used by Java (HotSpot), JavaScript (V8, SpiderMonkey), .NET (CoreCLR).
• Bytecode interpretation: the bytecode is executed instruction-by-instruction by an interpreter, with no native compilation. Simplest to implement, slowest at runtime. Used by Python (CPython), Ruby (MRI).

Example problem §

Problem: A C function int sum(int *a, int n) sums an array of $n$ integers. A caller invokes it three times with arrays of lengths $n_1, n_2, n_3$. After inlining, how many times does the loop body execute?