Intermediate Representations

An intermediate representation is a data structure or textual form that encodes a program's computation independently of both source syntax and target-machine details. It is produced by the front end after lexing, parsing, and Type Checking in Compilers, and consumed — possibly through several successive IRs — by the back end, which performs optimization and code generation. Crucially, an IR is not one fixed thing: it is a design point on a spectrum from high-level (close to source, tree-shaped, e.g. an annotated abstract syntax tree) to low-level (close to hardware, linear, e.g. an assembly-like three-address form). Three properties determine whether an IR design is good. Expressiveness: every construct in every supported source language must be representable, without loss of the semantic information optimizations need (types, aliasing, exception behavior). Ease of translation: it should be mechanical — ideally a syntax-directed structural recursion — to lower a typed AST into the IR, and equally mechanical to lower the IR into target instructions. Amenability to analysis and transformation: the IR should make common patterns (a variable's definitions and uses, the flow of control, which computations are redundant) explicit and cheap to compute, rather than buried in nested expression trees or entangled with a specific instruction set. The major IR families reflect different tradeoffs among these properties. Graph-structured IRs — abstract syntax trees (ASTs) and directed acyclic graphs (DAGs) — mirror the recursive structure of source programs and are natural right after parsing; a DAG additionally shares identical subexpressions, exposing redundancy directly in the structure. Linear IRs — three-address code (TAC), stack-based bytecode (as in the JVM), and register-transfer lists — flatten computation into a sequence of simple, machine-instruction-like steps, each doing at most one operation, which is exactly the granularity most classical optimizations are defined over. Control-flow graphs (CFGs) organize a linear IR into basic blocks (maximal straight-line instruction sequences) connected by edges representing possible control transfers, exposing loop and branch structure for global analyses like liveness and dominance. Static single assignment (SSA) form, an augmentation of CFG-based IR in which every variable is assigned exactly once and control-flow merges are made explicit via $\phi$-functions, is the representation of choice in modern optimizing compilers (LLVM, GCC's later passes, most JIT compilers) because it makes def-use chains — and hence most dataflow-based optimizations — nearly $O(1)$ to query.

The canonical pipeline lowers a typed AST, the output of parsing and Type Checking in Compilers, into three-address code organized as a control-flow graph. This is a syntax-directed translation: a recursive procedure with one case per AST construct, each case emitting a small, fixed pattern of low-level instructions and returning a handle (a temporary name or a label) that the caller stitches into surrounding code. The essential machinery is:

• Temporaries: fresh variable-like names (`t1`, `t2`, …) introduced by the translator to hold intermediate results, so that no TAC instruction needs more than one operator and two operands.
• Labels: fresh symbolic addresses (`L1`, `L2`, …) marking jump targets, used to compile structured control flow (`if`, `while`) into conditional and unconditional jumps.
• Basic blocks: after emitting a flat instruction stream, the compiler partitions it at "leaders" (block-starting instructions: jump targets, and instructions immediately after a jump/branch) to build the control-flow graph consumed by later optimization passes.

The pseudocode below shows the two central mechanisms: (1) expression translation, which returns the temporary holding a value, and (2) statement/control-flow translation, which threads labels for `true`, `false`, and `next` continuations. ``` // gen(op, a, b, dst) emits one TAC instruction: dst = a op b // newTemp() returns a fresh temporary name // newLabel() returns a fresh label // emit(instr) appends instr to the current instruction stream // emitLabel(L) marks L at the current point in the stream function translateExpr(node): match node: case Const(v): t = newTemp() emit(t := v) return t case Var(x): return x // no new instruction needed case BinOp(op, left, right): tL = translateExpr(left) tR = translateExpr(right) t = newTemp() emit(t := tL op tR) return t case Call(f, args): argTemps = [translateExpr(a) for a in args] for at in argTemps: emit(param at) t = newTemp() emit(t := call f, length(argTemps)) return t function translateStmt(node, nextLabel): match node: case Assign(x, expr): t = translateExpr(expr) emit(x := t) case If(cond, thenS, elseS): Ltrue = newLabel() Lfalse = newLabel() translateCond(cond, Ltrue, Lfalse) emitLabel(Ltrue) translateStmt(thenS, nextLabel) emit(goto nextLabel) emitLabel(Lfalse) translateStmt(elseS, nextLabel) // falls through to nextLabel case While(cond, body): Lstart = newLabel() Lbody = newLabel() emitLabel(Lstart) translateCond(cond, Lbody, nextLabel) emitLabel(Lbody) translateStmt(body, Lstart) // body's "next" loops back emit(goto Lstart) case Seq(s1, s2): Lmid = newLabel() translateStmt(s1, Lmid) emitLabel(Lmid) translateStmt(s2, nextLabel) function translateCond(node, Ltrue, Lfalse): match node: case RelOp(op, left, right): tL = translateExpr(left) tR = translateExpr(right) emit(if tL op tR goto Ltrue) emit(goto Lfalse) case And(c1, c2): Lmid = newLabel() translateCond(c1, Lmid, Lfalse) emitLabel(Lmid) translateCond(c2, Ltrue, Lfalse) case Or(c1, c2): Lmid = newLabel() translateCond(c1, Ltrue, Lmid) emitLabel(Lmid) translateCond(c2, Ltrue, Lfalse) case Not(c1): translateCond(c1, Lfalse, Ltrue) ``` After this flat instruction stream is emitted, a second, purely mechanical pass builds the control-flow graph: ``` function buildCFG(instructions): // Step 1: identify leaders leaders = { instructions[0] } for i, instr in instructions: if instr is (goto L) or (if ... goto L): leaders.add(target L) leaders.add(instructions[i+1]) // fall-through after a branch for i, instr in instructions: if i > 0 and instructions[i-1] is a jump/branch: leaders.add(instr) // Step 2: partition into basic blocks blocks = [] currentBlock = [] for instr in instructions: if instr in leaders and currentBlock is not empty: blocks.append(currentBlock) currentBlock = [] currentBlock.append(instr) blocks.append(currentBlock) // Step 3: connect blocks by control flow for B in blocks: last = B.lastInstruction if last is (goto L): addEdge(B, blockStartingAt(L)) elif last is (if ... goto L): addEdge(B, blockStartingAt(L)) addEdge(B, nextBlockInOrder(B)) // fall-through elif last is not a jump: addEdge(B, nextBlockInOrder(B)) // fall-through return blocks with edges ``` The figure below shows the whole pipeline for a tiny program, `while (x < 10) { x = x + 1; }`, tracing from source through the typed AST, through the flat TAC stream, into the final control-flow graph — the three IR "altitudes" a real compiler moves through.

Note what does not appear anywhere in this pipeline: registers, calling conventions, instruction encodings, or a specific CPU's addressing modes. Those decisions are deliberately deferred to Code Generation, which consumes exactly this kind of CFG-over-TAC representation (often after further conversion to Three-Address Code in SSA form for optimization).

Time and space complexity of IR construction. Translating a typed AST with $n$ nodes into TAC is a single traversal: each `translateExpr`/`translateStmt`/`translateCond` case does $O(1)$ work (allocate a bounded number of temporaries/labels, emit a bounded number of instructions) plus recursive calls on strictly smaller subtrees. By the standard recurrence $T(n) = O(1) + \sum T(n_i)$ over disjoint children summing to $n-1$ nodes, translation runs in $O(n)$ time and produces $O(n)$ TAC instructions, since each AST node contributes a constant number of instructions. Building the control-flow graph from an instruction stream of length $m = O(n)$ is two linear scans (finding leaders, then partitioning and linking blocks), so it too is $O(m) = O(n)$. Overall: $O(n)$ time and $O(n)$ space, linear in program size — the same asymptotic class as parsing itself, which is essential, since IR construction happens on every compile.

Why this is correct. Correctness means: the TAC/CFG program, when executed under its own (simpler) operational semantics, computes the same result as the source AST under the source language's semantics, for every input. The argument is a structural induction on the AST, mirroring the translation's own recursive structure:

• Base cases (`Const`, `Var`): `translateExpr` emits code that computes exactly the constant or reads exactly the variable's current value into a temporary, matching the source semantics of a literal or identifier lookup directly.
• Inductive step (`BinOp(op, left, right)`): by the induction hypothesis, the emitted code for `left` correctly computes `left`'s value into `tL` (using only names and temporaries disjoint from `right`'s, since temporaries are freshly allocated), and likewise `right` into `tR`; the final instruction `t := tL op tR` then computes `op` applied to the correct operands, matching the AST node's semantics.
• Control flow (`If`, `While`): the key invariant is that `translateCond(cond, Ltrue, Lfalse)` transfers control to `Ltrue` in exactly the executions where `cond` is true and to `Lfalse` otherwise — provable by induction on the structure of boolean expressions (relational operators are base cases; `And`/`Or`/`Not` compose correctly because short-circuit semantics is exactly what the label-threading pattern implements). Given that invariant, `If` and `While` correctly reproduce structured control flow using only conditional/unconditional jumps.
• Freshness invariant: because `newTemp()` and `newLabel()) never reuse a name already emitted, no two independent subcomputations can accidentally alias, which is what makes the "disjoint names" assumption in the inductive step legitimate.

This inductive argument is exactly why syntax-directed translation is trustworthy: correctness of the whole program follows from correctness of each local translation rule plus non-interference between subtranslations, not from reasoning about the program globally.

Tradeoffs. Lower-level IRs (TAC, CFG, SSA) make optimization and code generation easier but are farther from the source, so error messages and source-level debugging metadata must be carried along explicitly (line-number maps, debug annotations) rather than read off the structure for free. Higher-level IRs (AST, DAG) preserve source structure for good diagnostics but hide the redundancy and control-flow patterns that classical optimizations exploit, so production compilers use several IRs in sequence rather than picking one altitude and staying there — trading extra translation passes (still each $O(n)$, so still $O(n)$ overall by a constant factor) for representations well-suited to each compilation phase.

Consider compiling the function below, deliberately including a nested `if` inside a loop so the trace is not symmetric or trivial: ``` function clamp(x): while (x > 100 or x < 0): if (x > 100): x = x - 50 else: x = x + 10 return x ``` Trace of `translateStmt` on the `While` node (labels/temps numbered in allocation order):

Assembling the full instruction stream: ``` L1: if x > 100 goto L2 goto L3 L3: if x < 0 goto L2 goto next L2: if x > 100 goto L4 goto L5 L4: t1 := x - 50 x := t1 goto L1 L5: t2 := x + 10 x := t2 goto L1 next: return x ``` Running `buildCFG` on this stream: leaders are `L1` (entry), `L3` (branch target and fall-through after a branch), `L2` (branch target), `L4`, `L5`, and `next` — six leaders, producing six basic blocks, each ending in either a conditional branch, an unconditional jump, or a `return`. Executing this TAC on input `x = 205`: block `L1` tests `205 > 100` → true → jump to `L2`; `L2` tests `205 > 100` → true → jump to `L4`; `t1 := 155`, `x := 155`, loop to `L1`; `155 > 100` → true → `L2` → `L4` again → `x := 105`; loop; `105 > 100` → true → `L4` → `x := 55`; loop; `55 > 100` false, `55 < 0` false → falls to `next`; `return 55`. This matches direct evaluation of the source under the loop's informal semantics, confirming the translation preserves behavior on a non-trivial, asymmetric input.

The idea of a machine-independent middle layer was pushed forward by researchers building the first retargetable and portable compiler infrastructures, connecting directly to work on optimizing transformations, dataflow analysis, and static single assignment form.

LLVM IR is the textbook example at industrial scale: Clang, Rust, Swift, and Julia all compile to the same typed, SSA-based LLVM IR, which a shared set of optimization passes transforms before any target-specific code generation happens — precisely the $O(m+n)$ architecture this article opened with. JVM bytecode plays the analogous role for the Java ecosystem: javac, Kotlin, Scala, and Clojure all target the same stack-based bytecode, letting a single JIT (HotSpot) optimize and compile all of them at runtime. GCC uses a chain of IRs — GENERIC (tree-based, close to source), GIMPLE (three-address, simplified), and RTL (register-transfer lists, close to machine) — illustrating that production compilers routinely use multiple IRs at different altitudes rather than one. Beyond traditional compilers, query optimizers in database systems (relational algebra as an IR between SQL and physical execution plans) and ML compiler stacks (ONNX, MLIR, XLA's HLO as IRs between deep-learning frameworks and accelerator hardware) apply the exact same decoupling principle to entirely different domains. Anywhere a system must support many front ends and many back ends without quadratic translator sprawl, an intermediate representation is the standard engineering answer.

Ask the tutor: How does converting three-address code into static single assignment (SSA) form actually make optimizations like dead-code elimination faster to compute?