Intermediate Representation: IR Types, SSA Form, and Optimization

Compilers Compilers 8 min read 1598 words Beginner ExcellentWiki Editorial Team

An intermediate representation (IR) is the data structure that sits between the compiler frontend and backend. It is the crucial abstraction that makes retargetable compilers possible: the frontend translates source code into IR, and the backend translates IR into machine code. A well-designed IR enables machine-independent optimizations, supports multiple source languages from a single backend, and simplifies the addition of new target architectures. This article covers the major IR types — three-address code, SSA form, control flow graphs, and the IR designs of LLVM, GCC, and JIT compilers.

Why IR Matters

Without IR, each compiler frontend would need its own backend. Supporting N languages and M targets would require N × M compiler implementations. With IR, you need N frontends, M backends, and one shared IR — N + M implementations. This is the retargetability benefit that made the IR-based architecture standard after the 1980s.

IR design involves several tradeoffs:

Level of abstraction — high-level IR preserves source structure (easier optimization, harder code gen); low-level IR is close to machine code (easier code gen, harder high-level optimization)
Graph vs. linear — graph IRs (CFGs, data-flow graphs) expose structure; linear IRs (bytecode, three-address code) are compact and easy to serialize
Typed vs. untyped — typed IRs carry type information for safety and optimization; untyped IRs are simpler but require more analysis

Three-Address Code (TAC)

Three-address code is a linear IR where each instruction has at most three operands. The name comes from the typical form: result = operand1 operator operand2. TAC decomposes complex expressions into simple operations that correspond closely to machine instructions.

TAC instruction types include:

Assignment — x = y (copy)
Binary operation — x = y + z, x = y * z
Unary operation — x = -y, x = !y
Control flow — if x goto L, goto L
Function call — param x, call f, x = call f
Memory access — x = *p, *p = x
Pointer assignment — x = &y, x = y.field

The Dragon Book uses TAC extensively for illustrating code generation and optimization. Each TAC instruction can be represented as a quadruple (op, arg1, arg2, result). The simplicity of this representation makes it an excellent teaching tool, and many production compilers use TAC as a starting point before converting to SSA.

Static Single Assignment (SSA) Form

SSA is a refinement of TAC where each variable is assigned exactly once, and φ (phi) functions merge values at control-flow join points. SSA simplifies data-flow analysis because the use-def chain is explicit — each use of a variable has exactly one definition, which is trivially found by following the SSA edge.

Converting to SSA

The standard algorithm for placing φ functions uses dominance frontiers. A variable that is defined in multiple basic blocks needs a φ function at every block in the dominance frontier of the definition blocks. Cytron et al.’s 1991 paper “Efficiently Computing Static Single Assignment Form and the Control Dependence Graph” presents the O(N log N) algorithm used in production compilers.

Consider a simple example:

// Original:
if (cond)
    x = 1;
else
    x = 2;
y = x;

// SSA form:
if (cond)
    x1 = 1;
else
    x2 = 2;
x3 = φ(x1, x2);
y = x3;

The φ function selects x1 if control came from the true branch, x2 if from the false branch.

Benefits of SSA

Simpler constant propagation — if x = 5 is the only definition, all uses can be replaced with 5
Dead code elimination — if a variable is never used, its defining instruction is dead
Global Value Numbering (GVN) — detects redundant computations across blocks
Register allocation — SSA-based allocation (through live range splitting) produces high-quality results

Control Flow Graphs (CFGs)

A CFG represents all possible execution paths of a program. Nodes are basic blocks — maximal sequences of straight-line code — and edges represent control transfers between blocks.

CFG properties used in optimization:

Dominance — block A dominates block B if every path from entry to B goes through A. Dominance trees structure optimization passes
Post-dominance — block A post-dominates B if every path from B to exit goes through A
Loops — natural loops are identified by back edges in the CFG. Loop nest trees organize loop transformations
Reachability — unreachable blocks are candidates for dead code elimination

IR in Production Compilers

LLVM IR

LLVM IR is a typed, SSA-based IR that serves as both an in-memory representation and a serialization format. It exists in three forms: .ll (human-readable), .bc (bitcode), and in-memory LLVMContext. LLVM IR instructions include:

Memory operations — alloca, load, store, getelementptr
Arithmetic — add, sub, mul, sdiv, udiv (with nuw/nsw flags)
Control flow — br, switch, indirectbr, invoke, resume
Aggregate operations — extractvalue, insertvalue, shufflevector

LLVM IR’s type system includes integers, floats, vectors, arrays, structs, pointers, and functions. The alloca instruction allocates stack memory; getelementptr (GEP) computes pointer offsets for struct fields and array elements.

LLVM IR is the input to LLVM’s optimization passes. The opt tool reads .ll or .bc files, applies a sequence of passes, and outputs transformed IR. This makes LLVM IR a useful format for compiler research — you can write a pass that operates on LLVM IR without building a full compiler.

One distinguishing feature of LLVM IR is its ability to carry metadata — annotations that do not affect semantics but guide optimizations. Debug information, profile data, and loop hints (e.g., #pragma clang loop vectorize(enable)) are all encoded as metadata nodes attached to instructions or functions. Metadata survives optimization passes because passes are semantically transparent to it — they transform instructions but carry the metadata forward.

The GEP Instruction

LLVM’s getelementptr (GEP) instruction is famously subtle. It computes the address of a subelement of an aggregate type without accessing memory. Given a pointer to a struct and an index into a field, GEP returns a new pointer:

%ptr = getelementptr %MyStruct, ptr %s, i32 0, i32 1

This computes the address of field 1 of struct %s. GEP does not read or write memory — it is purely an address computation. Understanding GEP is essential for anyone working with LLVM IR because it appears in almost every memory access pattern.

GCC’s Two-Level IR

GCC uses two IRs: GENERIC (high-level, close to the AST) and GIMPLE (lower-level, three-address SSA). GENERIC is the bridge between frontends and the middle-end; GIMPLE is the IR that optimization passes work on. After GIMPLE optimization, GCC expands to RTL (Register Transfer Language), a low-level IR with explicit registers and machine instructions.

The two-level design lets GCC apply source-level optimizations on GIMPLE (inlining, constant propagation) and machine-level optimizations on RTL (instruction selection, register allocation).

JIT Compiler IRs

JIT compilers use IRs optimized for fast compilation rather than peak optimization:

Java HotSpot’s HIR (High IR) and LIR (Low IR) — HIR is SSA-based for profiling and optimization; LIR is a linear representation close to machine code for fast emission
V8’s TurboFan — a sea-of-nodes IR where data dependencies and control dependencies are explicit edges in a graph
Cranelift — a lightweight, SSA-based IR designed for fast WebAssembly and JIT compilation, with a simpler type system than LLVM IR

FAQ

What is the difference between high-level and low-level IR? High-level IR (like GENERIC or HIR) preserves source-language abstractions such as loops, arrays, and structures. Low-level IR (like RTL or LIR) exposes registers, memory operations, and machine instructions. Optimizations are easier on high-level IR; code generation is easier on low-level IR.

Why does SSA form use φ functions? φ functions encode control-flow-dependent value selection. Without φ, the same variable name would have different values depending on the execution path. φ functions make data-flow explicit by modeling the merge point.

Can IR be serialized to disk? Yes. LLVM IR has both text (.ll) and bitcode (.bc) formats. GCC supports LTO (Link-Time Optimization) by serializing GIMPLE to bytecode in object files. Serialized IR enables whole-program optimization across translation units.

What IR does a JIT compiler use? JITs typically use a lighter IR than ahead-of-time compilers. V8’s TurboFan uses a sea-of-nodes graph IR. Java HotSpot uses HIR (for profiling) then LIR (for code generation). LLVM’s JIT (MCJIT/OrcJIT) uses standard LLVM IR.

IR Design Tradeoffs

Choosing or designing an IR for a new compiler involves several tradeoffs:

Graph vs. linear — Graph IRs (sea-of-nodes, data-flow graphs) expose parallelism and make it easy to move operations across blocks. However, they consume more memory and are harder to serialize. Linear IRs (TAC, bytecode) are compact and map directly to machine code but obscure the data-flow relationships.

Typed vs. untyped — Typed IRs (LLVM IR, Java bytecode) carry type information that enables safety checks and optimization. Untyped IRs (RTL, early TAC) are simpler but require the backend to reconstruct type information through analysis. The trend in modern compilers is toward typed IRs.

SSA vs. non-SSA — SSA form simplifies many optimizations but requires phi nodes and complicates memory operations (since memory is not in SSA form). LLVM uses memory SSA through memdep and MemorySSA passes. JIT compilers sometimes use non-SSA IR to keep compilation fast.

Single vs. multi-level — GCC uses two IRs (GIMPLE for high-level optimization, RTL for backend). LLVM uses one IR throughout. Two levels give more optimization opportunities at the cost of maintaining two representations. One level simplifies the compiler but may miss optimizations that require high-level information.