Quadruples, Triples and Representations

Three-address code tells you what each instruction means — one operator, at most three addresses — but it says nothing about how those instructions actually sit in memory. That is a separate design choice, and it matters more than it first appears: the data structure you pick decides how easy it is to move, delete, or reorder an instruction later, which is the daily business of an optimiser. There are three classic layouts — quadruples, triples, and indirect triples — and the differences between them are a small, sharp lesson in the cost of naming.

The running example throughout is one deliberately repetitive assignment,

a = b \times {-c} + b \times {-c}.

It has a unary minus, two multiplications, an addition and a final assignment, plus a repeated sub-expression b \times (-c) — perfect for showing how each representation names its intermediate results.

Quadruples: name every result

A quadruple ("quad") is a record with four fields: (\textit{op}, \textit{arg}_1, \textit{arg}_2, \textit{result}). Each intermediate value gets an explicit temporary name in the result field, and later instructions refer to that value by its name. Our expression becomes:

#oparg1arg2result
0minusc—t1
1*bt1t2
2minusc—t3
3*bt3t4
4+t2t4t5
5=t5—a

The great virtue is independence. Every temporary has a name of its own, so an instruction can be picked up and dropped anywhere its operands are still available — the references travel by name, not by position. Deleting the redundant second copy of b \times (-c) (common-subexpression elimination) is trivial: rewrite instruction 4 to read + t2 t2 and delete instructions 2 and 3, and nothing else needs to change. This is why quadruples are the layout of choice for optimising compilers.

Triples: let position be the name

A triple drops the result field entirely: (\textit{op}, \textit{arg}_1, \textit{arg}_2). So where does an instruction's result live? It has no name — instead, other instructions refer to it by the position of the triple that computes it. We write (i) to mean "the value produced by triple i". The same expression, three fields wide:

#oparg1arg2
0minusc—
1*b(0)
2minusc—
3*b(2)
4+(1)(3)
5=a(4)

Triples are compact — no temporaries to store in the symbol table, one fewer field per record — which is why they were beloved in the memory-scarce era and still show up in tree-shaped IRs (a triple is essentially a node with two child pointers). But look what "position is the name" costs us. Instruction 4 refers to (1) and (3) by their row numbers. Move a triple, insert one, or delete one, and every subsequent row number shifts — so every reference that pointed past the change is now wrong. Reordering, the optimiser's bread and butter, becomes a nightmare of renumbering.

Indirect triples: one level of indirection fixes it

The classic engineering escape is a level of indirection. Keep the triples in a pool in any order, but drive execution through a separate listing array that holds pointers to triples in the order they should run. Reordering the program now means shuffling the small listing array; the triples themselves never move, so no reference into them ever breaks.

listing→ triple #triple #oparg1arg2
[0](0)(0)minusc—
[1](1)(1)*b(0)
[2](2)(2)minusc—
[3](3)(3)*b(2)
[4](4)(4)+(1)(3)
[5](5)(5)=a(4)

To swap two statements, swap two entries in the listing column — the triples' own numbers stay put, so (1) still means the same triple no matter where it appears in the schedule. This is the same trick a linker's relocation table or a virtual-memory page table plays: any problem in computer science can be solved by adding a level of indirection (except the problem of too many levels of indirection).

Building both, in code

The two layouts fall out of the same post-order walk. Below we translate a = b \times (-c) + b \times (-c) once as a quad list (results carry explicit temporary names) and once as a triple list (results are the row indices), and print them side by side.

type Quad = { op: string; a1: string; a2: string; res: string }; type Triple = { op: string; a1: string; a2: string }; // --- Quadruples: a fresh temporary names each result. --- function buildQuads(): Quad[] { const q: Quad[] = []; let n = 0; const t = () => `t${++n}`; const t1 = t(); q.push({ op: "minus", a1: "c", a2: "-", res: t1 }); const t2 = t(); q.push({ op: "*", a1: "b", a2: t1, res: t2 }); const t3 = t(); q.push({ op: "minus", a1: "c", a2: "-", res: t3 }); const t4 = t(); q.push({ op: "*", a1: "b", a2: t3, res: t4 }); const t5 = t(); q.push({ op: "+", a1: t2, a2: t4, res: t5 }); q.push({ op: "=", a1: t5, a2: "-", res: "a" }); return q; } // --- Triples: results are referenced by position, written "(i)". --- function buildTriples(): Triple[] { const tr: Triple[] = []; const emit = (op: string, a1: string, a2: string) => (tr.push({ op, a1, a2 }), tr.length - 1); const i0 = emit("minus", "c", "-"); const i1 = emit("*", "b", `(${i0})`); const i2 = emit("minus", "c", "-"); const i3 = emit("*", "b", `(${i2})`); const i4 = emit("+", `(${i1})`, `(${i3})`); emit("=", "a", `(${i4})`); return tr; } console.log("QUADRUPLES (op, arg1, arg2, result)"); buildQuads().forEach((q, i) => console.log(`${i}: ${q.op}\t${q.a1}\t${q.a2}\t-> ${q.res}`)); console.log("\nTRIPLES (op, arg1, arg2) — result is the row number"); buildTriples().forEach((t, i) => console.log(`(${i}): ${t.op}\t${t.a1}\t${t.a2}`));

The quad rows carry -> t1 … t5; the triple rows carry no result at all, and their cross-references are the parenthesised row numbers (0)…(4). Same computation, two philosophies of naming.

Modern optimising compilers almost universally use something quad-like, because their central data structure is SSA form, in which every value already has a unique name — the ultimate expression of "name every result". LLVM's IR, for instance, is essentially quadruples in SSA: each instruction defines a fresh, uniquely-named value. Triples survive in tree-oriented or memory-frugal settings and in teaching, where their compactness makes the position-coupling lesson vivid. Indirect triples are more of a historical curiosity now — once you are willing to spend names, quadruples give you everything indirect triples do, with less ceremony.

The trap with triples is that renumbering is invisible. If you insert a new triple at position 2, the triple formerly at 2 is now at 3, at 3 is now at 4, and so on — but a reference written as (3) elsewhere still literally says (3), and now points at the wrong instruction. Nothing errors; the code just computes garbage. This is exactly why an optimiser that wants to reorder cannot use raw triples. The two honest fixes are: (a) switch to quadruples, where references are stable names, or (b) add the listing array of indirect triples, so the triples never move and only the schedule does. Never hand an instruction-scheduler a bare triple list.