Three-Address Code
Imagine translating the expression `x = a b + a b * c` directly into machine instructions. A processor cannot evaluate a nested expression tree in one step. It needs somewhere to put intermediate results. It also needs each instruction to name at most a couple of operands. Three-address code (TAC) is the classic linear Intermediate Representation that bridges this gap. Every instruction computes one operation on at most two operands. It then assigns the result to a temporary. The whole computation becomes a straight-line sequence of tiny steps. TAC matters because virtually every optimizing compiler funnels source syntax through it. Examples include GCC's GIMPLE, LLVM's earlier scalar forms, javac's bytecode lowering, and countless course-project compilers. All pass through some flavor of three-address form before doing anything else. It is simple enough that generating it from an Abstract Syntax Tree is almost mechanical. Yet it is structured enough that classic optimizations operate cleanly on it. These include constant folding, common-subexpression elimination, dead-code elimination, and register allocation. Machine code, by contrast, is too low-level and irregular for analysis. ASTs are too high-level and tree-shaped for a linear pass. TAC sits at exactly the right altitude. The big picture: a compiler's middle end exists to transform a program while preserving its meaning. TAC is the common vocabulary that lets syntax-directed translation, control-flow analysis, and optimization all talk to the same representation. Once code is in three-address form, some questions become simple problems. For example: "which variables are live at this point?" or "can these two expressions be merged?" These become graph and dataflow problems over a list of instructions. They are no longer ad-hoc tree surgery. This article gives the precise instruction set of three-address code. It presents an algorithm for generating it from expressions and control structures via syntax-directed translation. It includes a worked trace on a real expression with short-circuit control flow. It also gives an honest accounting of costs. This sets up later material on Code Generation and Register Allocation. Both of these consume TAC as their primary input.
- Three-address code (TAC) is a linear IR where each instruction has at most one operator and three addresses (two operands, one result).
- Compound expressions are broken into instructions using compiler-generated temporaries, so no instruction nests another computation.
- TAC is generated from an AST or grammar via synthesized/inherited attributes in a single syntax-directed pass, in linear time.
- Control constructs (if, while, short-circuit `&&`/`||`) compile to explicit labels and conditional/unconditional jumps.
- TAC is the natural substrate for optimizations like constant folding, common-subexpression elimination, and dataflow analysis before Register Allocation.
- Common representations include quadruples, triples, and static single assignment (an SSA-flavored TAC variant), each with different tradeoffs for editing and space.
Three-address code flattens nested expressions and control structures into a straight-line sequence of atomic operations connected by temporaries and jump labels.
The idea
A three-address instruction performs at most one arithmetic or logical operation and has at most three addresses: two source operands and one destination. Formally, each instruction has one of a small number of shapes: ``` x = y op z // binary operation x = op y // unary operation (negation, not, cast) x = y // copy goto L // unconditional jump if x goto L // conditional jump if x relop y goto L param x ; call p, n ; return y // procedure linkage x = y[i] ; x[i] = y // indexed load/store x = &y ; x = y ; x = y // address-of / pointer deref ``` Here `x`, `y`, `z` are addresses: names (source variables), compiler-generated temporaries (`t1`, `t2`, …), constants, or labels. The key restriction is that no instruction contains a nested sub-expression — `t1 = a b + c` is illegal in TAC; it must be split into `t1 = a b` followed by `t2 = t1 + c`. This atomicity is what makes TAC "three-address": you can always read off the (at most) three names involved in one instruction without re-parsing a tree. TAC generalizes the AST (a tree, good for syntax-directed reasoning) into a sequence (good for control-flow and dataflow reasoning), while remaining more structured than raw assembly (no fixed register set, unlimited symbolic temporaries, and machine-independent operators). Three common concrete representations exist. Quadruples store `(op, arg1, arg2, result)` as four explicit fields — easy to reorder and rewrite, at the cost of extra space for temporary names. Triples store `(op, arg1, arg2)` and refer to a result implicitly by the instruction's own position/index — more compact, but reordering instructions requires fixing up references. Indirect triples add a level of indirection (a list of pointers into a triple table) to get compactness with easier reordering. Later, Static Single Assignment refines TAC further by requiring every variable to be assigned exactly once, adding φ-functions at control-flow merges — the natural next step once TAC control flow via labels is understood.
How it works
TAC is generated by a syntax-directed translation: walk the AST (or drive the translation directly from the grammar during parsing) and, at each node, synthesize (a) the TAC instructions needed to compute the node's value and (b) the address holding that value. Two auxiliary devices make this precise for expressions and for control flow. For expressions, each node's translation returns an address (`place`) where its value lives, plus a code list. Function `newtemp()` allocates a fresh temporary name; `gen(...)` emits one instruction. For boolean expressions used for control (in `if`, `while`, `&&`, `||`), the classical technique is backpatching: rather than deciding jump targets before their destinations are known, generate jump instructions with a placeholder target, remember their instruction numbers in lists `truelist` and `falselist`, and patch in the real label once it is known. This avoids a forward-reference problem — you often need to jump to code you haven't generated yet. ``` // Expression translation: returns (code, place) function translateExpr(node): switch node.kind: case NUM or ID: return ([], node.value) // no code needed, already an address case BinOp(op, L, R): (codeL, addrL) = translateExpr(L) (codeR, addrR) = translateExpr(R) t = newtemp() code = codeL ++ codeR ++ [ gen(t "=" addrL op addrR) ] return (code, t) case UnOp(op, E): (codeE, addrE) = translateExpr(E) t = newtemp() return (codeE ++ [ gen(t "=" op addrE) ], t) case Assign(ID, E): (codeE, addrE) = translateExpr(E) return (codeE ++ [ gen(ID "=" addrE) ], ID) // Boolean expression translation with backpatching: returns (code, truelist, falselist) function translateBool(node): switch node.kind: case RelOp(op, L, R): (codeL, addrL) = translateExpr(L) (codeR, addrR) = translateExpr(R) i1 = nextInstr() emit("if" addrL op addrR "goto _") // target patched later i2 = nextInstr() emit("goto _") code = codeL ++ codeR ++ [instr(i1), instr(i2)] return (code, [i1], [i2]) case And(B1, B2): (code1, true1, false1) = translateBool(B1) M = nextInstr() // label for start of B2 (code2, true2, false2) = translateBool(B2) backpatch(true1, M) // B1 true -> evaluate B2 return (code1 ++ code2, true2, false1 ++ false2) case Or(B1, B2): (code1, true1, false1) = translateBool(B1) M = nextInstr() (code2, true2, false2) = translateBool(B2) backpatch(false1, M) // B1 false -> evaluate B2 return (code1 ++ code2, true1 ++ true2, false2) case Not(B1): (code1, true1, false1) = translateBool(B1) return (code1, false1, true1) // swap lists function backpatch(list, label): for i in list: patch instruction i's "_" target to label // Statement translation for if/while uses translateBool + backpatch similarly: function translateIf(B, S1): (codeB, truelist, falselist) = translateBool(B) M = nextInstr() codeS1 = translateStmt(S1) backpatch(truelist, M) Lafter = nextInstr() backpatch(falselist, Lafter) return codeB ++ codeS1 ``` The algorithm is a single recursive descent: each grammar production has a translation rule combining its children's code and addresses. There is no backtracking — every subexpression is translated exactly once, and every jump target is either known immediately (loop headers) or filled in later via backpatch lists, never guessed and revised.
Complexity & correctness
Time. Syntax-directed translation of expressions visits each AST node exactly once and does O(1) work per node (allocate at most one temporary, emit at most one instruction, concatenate code lists). If code lists are represented so that concatenation is O(1) (e.g., linked lists with tail pointers, or emitting directly into a growing array rather than functional list-append), the whole pass is O(n) in the number of AST nodes. A naive implementation using array/list concatenation with copying can degrade to O(n²) in pathological left-deep expressions, so real compilers always use an appendable emission buffer or difference lists, not immutable list concatenation.
Space. The output has O(n) instructions (each original operator produces one instruction, each leaf produces zero), and O(n) temporaries in the worst case (a fully unshared expression tree with n internal nodes needs at most n live temporaries at generation time, though far fewer are simultaneously alive). Backpatch lists add O(n) extra bookkeeping, released once patched.
Correctness argument. The translation is correct if, inductively, `translateExpr(node)` returns code that, when executed, leaves in `place` exactly the value that `node` denotes under the source language's semantics, without altering any address used elsewhere. The base cases (`NUM`, `ID`) hold trivially — no code needed, the address already denotes the value. The inductive step for `BinOp(op, L, R)` assumes (inductive hypothesis) that `codeL` correctly computes `L`'s value into `addrL` and `codeR` correctly computes `R`'s value into a distinct fresh address `addrR` (freshness guaranteed because `newtemp()` never reuses a name), then the emitted instruction `t = addrL op addrR` computes the correct value because `op` is applied to the two already-correct operands, executed strictly after both operand computations by the sequencing of the emitted code. Since each temporary is generated fresh and never aliased to a surviving variable, no instruction can accidentally clobber a value still needed later in the same expression — this is the crucial invariant that justifies temporary allocation. For control flow, backpatching's correctness rests on an invariant over jump lists: `truelist` (`falselist`) always contains exactly the instruction numbers of incomplete jumps that must target the instruction executed when the boolean expression evaluates to true (false), and nothing else. `backpatch` establishes this invariant by patching every element of the list to the same label at the moment that label becomes known (i.e., the label of the very next instruction to be emitted), and the recursive cases (`And`, `Or`, `Not`) combine sublists exactly according to Boolean short-circuit semantics — e.g., in `And`, `B1`'s true-list must jump into the start of `B2`'s code, which is precisely what `backpatch(true1, M)` enforces. Because every jump instruction appears in exactly one list until patched, and every list is eventually and only patched once, no jump is left dangling and no jump is double-patched — giving a straightforward structural induction on Boolean expression size for full correctness.
Tradeoffs. TAC's uniformity costs something: unlimited symbolic temporaries mean a later pass (register allocation) must map an unbounded namespace onto a small fixed register file, and naive TAC generation (one temp per subexpression) can produce far more temporaries than a hand-tuned expression evaluator would need — mitigated later by liveness analysis and register allocation, not by TAC generation itself. Quadruples are simple to optimize in place but use 4× the fields of triples; triples save space but complicate reordering during optimization (moving an instruction requires updating every triple that references it by position), which is why many production compilers prefer quadruple-like or SSA-based forms despite the space cost.
Worked example
Translate the statement: ``` if (a < b && c > d) then x = a b + a b * c else x = 0 ``` Assume instructions are numbered starting at 100, and `translateBool` is applied to `a < b && c > d`, followed by `translateIf`-style dispatch to the then/else branches.
| Step | Action | Emitted instruction (index) | truelist / falselist after step |
|---|---|---|---|
| 1 | `translateBool(a < b)` | 100: `if a < b goto _` | true=[100] |
| 101: `goto _` | false=[101] | ||
| 2 | `M` = label of next instr for `And` (= 102) | — | — |
| 3 | `translateBool(c > d)` | 102: `if c > d goto _` | true2=[102] |
| 103: `goto _` | false2=[103] | ||
| 4 | `backpatch(true1=[100], M=102)` | 100 becomes `if a < b goto 102` | combined true=true2=[102] |
| 5 | `And` returns | — | true=[102], false=[101,103] |
| 6 | `M2` = next instr (104), start of then-branch | — | — |
| 7 | translate then-branch `x = ab + ab*c` | 104: `t1 = a b` 105: `t2 = a b` 106: `t3 = t2 * c` 107: `t4 = t1 + t3` 108: `x = t4` | — |
| 8 | `goto Lend` (skip else) | 109: `goto _` | pending=[109] |
| 9 | `Lelse` = next instr (110); `backpatch(false=[101,103], 110)` | 101 → `goto 110`; 103 → `goto 110` | — |
| 10 | translate else-branch `x = 0` | 110: `x = 0` | — |
| 11 | `Lend` = next instr (111); `backpatch([109], 111)` | 109 → `goto 111` | — |
| 12 | `backpatch(true=[102], M2=104)` | 102 → `if c > d goto 104` | — |
Final linear code: ``` 100: if a < b goto 102 101: goto 110 102: if c > d goto 104 103: goto 110 104: t1 = a b 105: t2 = a b 106: t3 = t2 c 107: t4 = t1 + t3 108: x = t4 109: goto 111 110: x = 0 111: (end) ``` Trace with `a=2, b=3, c=5, d=1`: instruction 100 tests `2<3` (true) → jump to 102; 102 tests `5>1` (true) → jump to 104; instructions 104–108 compute `x = 23 + 235 = 6+30 = 36`; instruction 109 jumps past the else to 111. The trace confirms short-circuit structure: had `ad`, matching `&&`'s short-circuit semantics exactly — and this behavior falls directly out of the invariant that `false1` (the false-list of the left operand) is patched to the else label, bypassing the right operand entirely. Notice also that `t1` and `t2` both compute `a*b` — TAC's straightforward generation does not notice the redundancy; that is deliberately left for a later common-subexpression-elimination pass operating on this exact instruction sequence.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Reusing a temporary across independent subexpressions | Naive temp allocator resets a counter per statement instead of using a true fresh-name generator | Always call a monotonically increasing `newtemp()`; never recycle within one expression's live range |
| Forgetting to patch every element of a jump list | Manual jump generation without a systematic list convention | Maintain explicit `truelist`/`falselist` per node and patch exactly once at the point the target is known |
| O(n²) blowup from list concatenation in code generation | Using immutable/functional list append (`code1 ++ code2`) repeatedly on large lists | Emit into a single growing buffer, or use difference lists / rear-pointer linked lists for O(1) append |
| Mis-ordering side effects in `a = f() + g()` | Emitting `t2 = g()` before recording that `f()`'s call already may have side effects visible to `g()` | Fix an explicit left-to-right (or language-mandated) evaluation order in the translation rules, don't leave it implicit |
| Off-by-one label targeting (jumping to the instruction before the intended target) | Confusing "next instruction to be emitted" with "last instruction emitted" when recording `M` | Always record the label as the index of the next instruction about to be generated, before generating it |
| Losing the true/false list distinction under `Not` | Forgetting to swap `truelist` and `falselist` | `Not(B)` translation must literally exchange the two lists, not just negate a flag |
Pioneers & history
Origins · 1 minRobert W. Floyd and how this was discovered
Floyd's work on syntax-directed parsing and program correctness underlies the systematic, rule-by-rule translation style that later became standard for generating three-address code from grammars.
Where this matters
Every major optimizing compiler infrastructure lowers source syntax to a TAC-like linear form before optimizing: GCC's GIMPLE, LLVM's early scalar representations and its SSA-based LLVM IR (a direct descendant of TAC ideas), the Java virtual machine's stack bytecode is compiled from a TAC-shaped intermediate inside `javac`, and V8's TurboFan and other JIT compilers use TAC-like sea-of-nodes or linear IRs internally. Course compilers (the classic "toy C compiler" projects) universally use TAC as the handoff point between the front end (parsing, type checking) and the back end (instruction selection, Register Allocation). Static analysis and security tools (taint analysis, dataflow-based bug finders) operate on TAC or SSA because reasoning about "which definition reaches this use" is tractable on a linear instruction sequence but awkward on a raw AST. Anywhere a system needs to reason about, transform, or optimize a program mechanically — compilers, JITs, static analyzers, decompilers — some cousin of three-address code sits at its core.
Ask the tutor: Can you walk me through how backpatching would change if the boolean expression also contained a `!(...)` negation nested inside an `&&`?
Why not just optimize directly on the AST instead of lowering to TAC?
An AST encodes nesting and precedence well but hides control flow inside tree shape (e.g., an `if` node's branches are subtrees, not sequential code), making dataflow questions like "what reaches this point" awkward to state. TAC linearizes the program into an explicit sequence of tiny instructions connected by named temporaries and jump labels, so classic analyses — liveness, reaching definitions, available expressions — become graph and dataflow problems over a control-flow graph of instructions rather than ad hoc tree traversals. Many optimizations (common-subexpression elimination, constant folding across statements, code motion) are naturally stated over sequences of instructions with shared temporaries, which an AST does not expose directly. Lowering to TAC first also decouples the front end's grammar-specific structure from the back end's optimization and code-generation logic, a valuable separation of concerns in real compiler engineering.
How many temporaries does TAC generation actually need, and does that number matter?
A naive syntax-directed translator introduces one temporary per internal operator node, so an expression tree with k operators can produce up to k live temporary names during generation. This raw count matters less than it seems, because most temporaries have very short live ranges — they are defined and consumed almost immediately — so a later liveness analysis typically finds far fewer temporaries simultaneously alive at any instruction. The temporary count becomes directly consequential only once Register Allocation must map these symbolic names onto a small fixed set of hardware registers; TAC generation itself is deliberately profligate with names to keep the translation simple, trusting later passes to compress the namespace.
What's the relationship between three-address code and static single assignment (SSA) form?
SSA is best understood as three-address code with one additional global constraint: every variable (including every temporary) is assigned exactly once in the program text. Where ordinary TAC allows a variable to be reassigned repeatedly (e.g., in a loop counter update), SSA renames each reassignment to a fresh version and inserts special φ-functions at control-flow merge points to reconcile which version reaches from which predecessor. The instruction shapes — binary/unary ops, copies, at most three addresses — are otherwise identical to plain TAC, which is why SSA is usually described as a refinement of TAC rather than an unrelated representation. Most modern optimizing compilers generate ordinary TAC first (or directly generate SSA using techniques that avoid ever materializing non-SSA TAC).
How does TAC handle function calls and array accesses, which don't fit the "one operator" pattern?
TAC extends its atomic-instruction philosophy with a small set of special forms rather than forcing everything into a strict binary-operator mold. Function calls are usually split into a sequence of `param x` instructions (pushing arguments) followed by `call p, n` (invoking procedure `p` with `n` arguments) and, if there's a return value, a following `y = call-result` style instruction. Array indexing and pointer operations get their own instruction shapes — `x = y[i]`, `x[i] = y`, `x = &y`, `x = y`, `x = y` — because address computation genuinely needs its own primitive rather than being expressible as a single arithmetic operator. These extensions preserve the core TAC discipline (each instruction does one conceptually atomic thing) while accommodating language features an idealized binary-operator grammar doesn't cover.
Is TAC generation ever combined directly with parsing, or is it always a separate AST pass?
Both approaches are used in practice, and the pseudocode-level translation rules are identical either way. In a strict two-phase design, the parser first builds a complete AST, and a separate tree-walking pass then emits TAC — simpler to implement and easier to test in isolation. In a one-pass syntax-directed design (common in LR-parser-based compilers), TAC is emitted as productions are reduced during parsing itself, using synthesized attributes carried on the parser stack, avoiding the need to build and store a full AST. The one-pass approach saves memory and a traversal but requires the language's grammar to admit clean synthesized-attribute translation, which is not always true for languages needing significant lookahead for control constructs.
Why does the worked example produce two separate temporaries (t1 and t2) for the same subexpression a*b?
Plain syntax-directed TAC generation translates each AST occurrence of a subexpression independently, with no memory of previously computed values — it is a purely local, one-node-at-a-time rule with no global bookkeeping. Since `a*b` appears twice as separate nodes in the AST (even though textually identical), the translator faithfully emits two separate multiply instructions into two separate temporaries. Recognizing that `t1` and `t2` compute the same value and merging them is precisely the job of a subsequent common-subexpression-elimination optimization pass, deliberately kept separate from TAC generation so each pass stays simple and independently verifiable.
Does using three-address code lose information the compiler might need later, like source-level types or structure?
TAC itself only records operations and addresses, so type and structural information must be preserved alongside it — typically in a symbol table cross-referenced by variable and temporary names, not encoded in the instructions themselves. Well-engineered compilers keep type annotations, source-line mappings for debugging, and structural metadata (e.g., which temporaries alias which array) in auxiliary tables that travel with the TAC rather than being reconstructed from it. This separation is intentional: keeping TAC instructions minimal is exactly what makes generic optimization passes reusable across source languages, while richer information lives in side tables consulted only when a specific pass needs it.