Three-Address Code as the Contract Between Front End and Back End

A parsed and type-checked program is a tree. A register allocator, a scheduler, and a peephole pass all want a list. The conversion between the two is the first real decision in a compiler, because the shape chosen there determines which facts are cheap to compute for every pass that follows. Three-address code is the oldest and still the most common answer: every instruction performs one operation, writes one destination, and names its operands.

The name comes from the classic form x = y op z, with at most two sources and one destination, each an address in the broad sense of a constant, a variable, or a compiler-generated temporary. Modern variants relax the arity but keep the essential property: no nesting. An operand is never itself an operation.

One Operator, One Destination

The restriction sounds pedantic until the consequences are traced. Consider t = (a*b) + (c*d). As a tree, the addition node owns two multiplication children, and the order in which the multiplications happen is implicit in the parent-child relation. As three-address code it becomes three instructions:

t1 = mul a, b
t2 = mul c, d
t3 = add t1, t2

Each intermediate now has a name. That name is what makes the value addressable: it can be counted, compared, renamed, copied, and deleted. Dead code elimination reduces to a use count over names rather than a tree walk with parent pointers. Common subexpression elimination reduces to hashing the right-hand side of each instruction. Neither transformation needs to know the syntactic context of the expression, only the multiset of definitions and uses.

The destinations are virtual registers: an unbounded supply of names, not physical machine registers. A function with ten thousand live temporaries is legal at this level and the register allocator’s problem later. Keeping the supply unbounded is what allows passes to invent new values freely — splitting a live range, duplicating a computation to shorten a dependency chain, or hoisting a loop-invariant expression all create definitions, and none of them should have to worry about exhausting a fixed register file.

A minimal in-memory form needs very little: an opcode, a destination, and a small operand array. In C, a fixed-capacity variant is often enough for a teaching compiler, and the fixed capacity is itself an instructive constraint because it forces the front end to break large expressions into chains of temporaries.

enum Op { OP_ADD, OP_MUL, OP_LOAD, OP_STORE, OP_CONST, OP_BRANCH };

struct Insn {
    enum Op op;
    int dst;              /* virtual register, -1 if none */
    int src[2];           /* virtual registers or -1 */
    long imm;             /* constant payload for OP_CONST */
    int target;           /* block index for OP_BRANCH */
};

The struct is deliberately flat: no pointers between instructions, no parent links. Control flow is expressed by branches to labelled positions, and those positions are grouped into basic blocks by a later pass, which is the step described in Building Basic Blocks and Control-Flow Graphs from Linear Code.

What Flatness Buys

Reordering is the central gain. In a tree, a node cannot move before its children, and sibling order is an artifact of source syntax rather than of data dependence. In a flat list, the only ordering constraints that exist are the ones encoded in operand names: an instruction must follow the definitions of the values it reads. A scheduler can move independent instructions freely without reasoning about tree structure, and it can do so at instruction granularity rather than subtree granularity.

The second gain is that dataflow analysis has a natural unit. Liveness, reaching definitions, and available expressions are all defined over a sequence of statements, and the sequence is right there. A tree has to be linearized before any of these frameworks apply, so the linearization might as well be the IR rather than a temporary view of it.

The third gain is uniformity. A front end for a language with pattern matching, closures, and exceptions emits the same instruction set as one for a language with none of those features. All the irregularity is paid for at translation time, in the form of runtime calls and explicit control flow, rather than by making every subsequent pass handle a larger set of node kinds. The cost is that high-level structure is gone: a pass that wants to recognize a loop must reconstruct it from branches, and a pass that wants to recognize a vectorizable reduction must pattern-match over scalar loads and adds.

The Tree Has to Come Back for Selection

Instruction selection works by tiling: machine instructions correspond to small tree patterns, and the selector covers the expression tree with the cheapest set of tiles. Addressing modes make this concrete. A load of a[i] on a typical 64-bit architecture is one instruction when the index is scaled by the element size and added to a base pointer, because the hardware provides a scaled-index addressing mode. If the IR has already separated the multiply and the add into distinct instructions with distinct destinations, the selector must undo that separation by matching a chain of definitions against a pattern.

Compilers therefore rebuild expression trees on demand from single-use definitions, a view sometimes called the tied tree or the expression DAG. A definition used exactly once can be folded into its consumer; a definition used twice cannot, because the consumer would then have to duplicate the computation. This creates a genuine phase-ordering conflict. Redundancy elimination merges duplicate computations, which is good for code size and execution count, but every merge turns two single-use chains into one multi-use value and blocks a fold that would have produced a single machine instruction. The selector’s cost model and the redundancy pass’s benefit estimate are measuring different things, and neither has full information about the other.

Constructs the Form Cannot Express

A single-destination instruction with explicit operands covers arithmetic and scalar memory traffic well. Several constructs strain it.

Instructions that write more than one register have no natural encoding. A division that produces both quotient and remainder, or a wide multiply that produces a high and low half, needs a tuple destination. Compilers handle this with an instruction whose destination is a small vector, or by modelling the second result as an extra output register fixed by the ABI, which then becomes an implicit constraint the register allocator must respect.

Memory operands are the second strain. A machine instruction such as an add that reads one operand from memory and writes it back performs a load, an arithmetic operation, and a store in one encoding. A load/store IR expands this into three instructions, and the selector must fuse them back. Peephole passes exist partly to recover these fusions, which is why the boundary between selection and peephole optimization is blurry in most real compilers.

Anything that can fail has an implicit control-flow edge. A division by zero, a null check, or an out-of-bounds access transfers control to a handler, and that transfer is not visible in the operand list. An IR that ignores this will reorder a potentially trapping operation across a store and change which state the handler observes. The standard fix is to mark such instructions as may-throw and to treat the marking as a side effect that constrains motion, or to model the throwing operation as an explicit call with a normal and an exceptional successor.

Predication is the fourth case. A conditional move writes a destination only when a predicate holds, and there is no branch to attach that condition to. Adding a select instruction that takes a predicate as an explicit operand is the usual resolution, and it interacts with the SSA construction described in Minimal SSA Construction from Dominance Frontiers, because a select is a value-producing merge rather than a control-flow merge.

Stack Machines and the Alternative

Not every IR names its intermediates. Java bytecode and the bytecode of many virtual machines are stack-based: operands are pushed and popped, and the depth of the stack at each point is a verifiable property. The form is compact, because no operand names need encoding, and it is locally checkable, because each opcode declares exactly what it pops and what it pushes. What it lacks is any notion of a value that outlives a single expression: the stack slot that holds a value is identified by its depth rather than by a name, so two occurrences of the same expression at different depths cannot be recognised as equal without simulating the stack, and there are no def-use chains to walk.

Converting a stack IR to a register IR is a standard first pass: simulate the stack symbolically, giving each push a fresh virtual register, and replace each pop with a reference to the register that the corresponding push defined. The result is ordinary three-address code, with one fresh name per push. What it is not is SSA: the mapping from stack slot to register changes when control flow merges, because the slot at depth 0 after a merge may hold a value pushed on either path, and the conversion must insert a merge of its own or accept that a name then has more than one definition. Running the SSA construction described in Minimal SSA Construction from Dominance Frontiers on the converted code supplies the phis the stack slots needed.

What the Choice Fixes

Choosing a flat, single-operator IR settles several questions at once. It makes value identity explicit, so redundancy and liveness are cheap. It makes evaluation order explicit, which is necessary for correctness around side effects but is a constraint on parallelism. It discards syntactic structure, so every high-level pattern must be rediscovered. And it pushes the mismatch with machine encodings into the selector, where a cost model can arbitrate.

The parts of the language that do not fit — aggregates, calls with several results, exceptions, predication — are usually handled by extending the instruction set with a small number of special forms rather than by abandoning the flat shape. Each such extension buys expressiveness at the price of a special case in every pass that walks instructions, and the size of that set is a decent measure of how much of the source language the IR was designed to see.