Intermediate Representations

The phases of compilation all speak to each other through a program's intermediate representation — the data structure that is the program between the source text and the final machine code. Choosing an IR is the most consequential design decision a compiler makes, because every optimisation and every analysis is expressed as a transformation over it. Too high-level and the back end drowns in source-language detail; too low-level and the optimiser cannot see the structure it needs to exploit. Real compilers resolve the tension by using not one IR but several, in sequence, each a little closer to the machine than the last.

This page is a map of that landscape: the levels of abstraction an IR can sit at, the difference between graphical and linear IRs, and why the journey from source to machine is best travelled as a staircase of representations rather than a single leap. We call each downward step lowering.

A taxonomy by level of abstraction

Sort IRs by how much they still resemble the source versus the target. Cooper & Torczon call this the IR's level; it is the single most useful axis for placing any IR you meet.

Level	Typical form	Keeps	Hides	Real example
High-level	abstract syntax tree (AST)	source structure: loops, expressions, scopes	address computation, control flow as jumps	a parser's AST; Java's early tree
Mid-level (linear)	three-address code, bytecode, SSA	a simple explicit operation sequence with temporaries	the exact target instructions and registers	LLVM IR, JVM bytecode, GCC GIMPLE
Low-level	near-machine ops / RTL	registers, addressing modes, machine idioms	almost nothing — one step above assembly	GCC RTL, LLVM MIR

A high-level IR is where source-shaped optimisations live (e.g. array-bounds reasoning, which needs to know an array access is an array access). A low-level IR is where machine-shaped optimisations live (instruction scheduling, register allocation). The mid-level is the sweet spot for the great general-purpose optimisations — constant folding, dead-code elimination, common-subexpression elimination — which is exactly why the industry's shared IRs (LLVM IR, GIMPLE) live there.

Graphical versus linear

Cutting the space a different way: an IR is either a graphical structure (nodes and edges you traverse) or a linear sequence (a list of instructions, like a tiny assembly program). Most compilers use both, at different moments.

Graphical IRs express a program as a graph. An AST is a tree of the source's phrase structure. A DAG (directed acyclic graph) is an expression tree with identical subexpressions shared, so a repeated computation appears once. A control-flow graph (CFG) has basic blocks as nodes and possible jumps as edges — the substrate of nearly all dataflow analysis.
Linear IRs express a program as an ordered list of instructions. Three-address code (TAC) allows one operator per instruction over named temporaries; stack (bytecode) machines push and pop operands instead of naming them. Linear IRs read like assembly for an idealised machine and are easy to emit, store and stream.

These are complementary, not rival. A compiler typically builds a graphical IR (an AST, then a CFG whose blocks hold linear TAC), analyses the graph, and finally walks it to emit a linear form for the back end. The graph is good for reasoning about relationships; the list is good for reasoning about order.

Why several IRs: lowering as a staircase

Consider the humble expression a \times b + a \times b. At the source level it is a tree. But a \times b appears twice, and a DAG — which shares the common subexpression — makes that redundancy visible: compute a \times b once, then add the result to itself. Lowering that DAG to linear three-address code bakes the sharing into a reused temporary. Watch the abstraction drop, one step at a time, in the diagram, then in code.

Each representation is better than its neighbour for some specific job, and no single IR is best at all of them — which is precisely why compilers descend the staircase instead of committing to one level. The tree is closest to the programmer's intent; the DAG exposes shared work; the linear code is ready for the back end. Optimising is largely a matter of choosing the right rung to stand on.

// Lower a*b + a*b from an expression tree to linear three-address code, // sharing the common subexpression a*b via a DAG-style memo. type Expr = | { op: "var"; name: string } | { op: "mul" | "add"; l: Expr; r: Expr }; // Tree for (a*b) + (a*b) — note both children of + are the SAME multiply. const ab: Expr = { op: "mul", l: { op: "var", name: "a" }, r: { op: "var", name: "b" } }; const tree: Expr = { op: "add", l: ab, r: ab }; const code: string[] = []; let next = 1; const memo = new Map<Expr, string>(); // identity memo = the DAG sharing function lower(e: Expr): string { if (e.op === "var") return e.name; const hit = memo.get(e); if (hit) return hit; // already computed this exact node const l = lower(e.l), r = lower(e.r); const t = `t${next++}`; const sym = e.op === "mul" ? "*" : "+"; code.push(`${t} = ${l} ${sym} ${r}`); memo.set(e, t); return t; } const result = lower(tree); console.log("three-address code:"); for (const line of code) console.log(" " + line); console.log(`result in ${result}`); console.log(`(a*b computed ONCE thanks to sharing: ${code.length} instructions, not 3)`);

All three are real mid-level linear IRs you can print and read. LLVM IR is a typed, SSA-form three-address code: %t = fmul float %rate, 6.0e1 — infinitely many virtual registers, explicit types, one operation per line. Java bytecode is a stack machine: to compute rate * 60 it emits fload rate; ldc 60.0; fmul — no register names at all, operands flow through an operand stack, which keeps class files compact and portable. GCC's GIMPLE is a three-address form GCC lowers its parse trees into before optimising, later dropping further to the low-level RTL for the back end. Three different languages, three different IRs — but all sitting at the same mid-level rung, for the same reason: it is the best place to optimise.

A tempting misconception is that the IR is simply the target assembly produced ahead of time — so a compiler could skip the IR and emit machine code directly. Two things are wrong with this. First, a good mid-level IR is deliberately machine-independent: it has an unbounded supply of virtual registers, no fixed calling convention, no target opcodes. That independence is the whole point — it is what lets one optimiser and many back ends share it (the narrow waist). Bake in x86 registers and you have thrown that away.

Second, an IR usually carries more semantic structure than assembly, not less: types, that a value is a pointer, that a block is a loop header, that two names cannot alias. Assembly has forgotten all of that. So an IR is not "assembly early" — it is a distinct, richer, more abstract language chosen to make analysis and retargeting possible. Emitting assembly directly from an AST is possible for a toy compiler, but it forfeits every optimisation the mid-level exists to enable.