Three-address code, quadruples and triples

Why it exists

An intermediate code must be written down in some concrete form the compiler can store, search and rewrite. The best-known form is three-address code: a very small, uniform instruction set that is close enough to assembly to be translated easily, and abstract enough to be optimised before a particular machine is chosen. The way each instruction is stored (as four fields, three fields, or as a pointer into a table) affects how easily the optimiser can move code.

Prerequisites

You need the translation of expressions into three-address code with temporaries (intermediate code generation).

Precise definitions

Addresses. An operand of an instruction is a name (a variable of the source program, referred to through the symbol table), a constant, or a compiler-generated temporary.

Instruction forms (the standard repertoire):

Instructions may carry labels. A call p(x1, ..., xn) becomes param x1, ..., param xn, call p, n.

Storage formats. The same code can be stored in three ways. For $a = b * -c + b * -c$, the code is

t1 = minus c
t2 = b * t1
t3 = minus c
t4 = b * t3
t5 = t2 + t4
a = t5

and the three forms of it are shown in the animation below.

• Quadruples: four fields (op, arg1, arg2, result). The result is a name (usually a temporary that must be entered in the symbol table). A copy x = y is (=, y, , x); unary operators leave arg2 empty; a jump has the target label in the result field. Instructions can be moved about without changing the others, because instructions refer to each other through names; this suits optimisers.
• Triples: three fields (op, arg1, arg2). There is no result field: the result of a triple is referred to by the position (index) of the triple, written (k). A temporary never needs a name or a symbol-table entry, so triples save space. But if instructions are reordered or deleted, the indices used by other triples change, which makes optimisation awkward. A copy x = y is stored as (=, x, y), with the target as the first argument. An array assignment x[i] = y needs two triples (one for the element address with []=, one for the copy).
• Indirect triples: the triples are kept in one table, and a separate list of pointers to triples gives the execution order. Moving an instruction means moving a pointer, so the triples do not change and may even be shared; this combines the compact triple format with the freedom of quadruples (at the cost of one extra level of indirection).

Comparison.

Static single assignment form (SSA). A variant in which every variable is assigned once: the variables are renamed (x1, x2, ...) and at a join of control flow a $\phi$-function chooses the right version. It simplifies many optimisations; the syllabus items on data flow analysis do not require it.

How it works

The animation builds the three storage forms of the six-instruction code of $a = b * -c + b * -c$ column by column. Compare the second and the third column: in the quadruples each result has a name (t1 to t5, and a); in the triples the second operand of (1) is written (0), the position of the triple that computes minus c. The last triple is the copy (=, a, (4)). The last column is the instruction list of the indirect triples, which numbers the pointers from 35 as in the textbook figure.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The code format is the output of intermediate code generation; the translation of conditions and loops, which introduces the jump instructions and the labels, is control-flow translation. Optimisation reorders and rewrites it (local optimisation).

PYQs

Consider the following expression: x[i] = (p + r)
*-s[i] + u/w
(0)
+
p
r
(1)

(2)
uminus
(1)

(3)

(4)
/
u
w
(5)
+
(3)
(4)
(6)

(7)
=
(6)
(5)

Which one of the following options fills in the
missing entries CORRECTLY?

Consider the following code segment.

x = u - t;

y = x * v;

x = y + w;

y = t - z;

y = x * y;

The minimum number of  variables required to
convert the above code segment to static single
assignment form is ________.

The least number of temporary variables required
to create a three-address code in static single
assignment form for the expression

q + r/3 + s – t * 5 + u * v/w  is _________.

For a C program accessing X[i][j][k], the following
intermediate code is generated by a compiler. Assume
that the size of an integer is 32 bits and the size of a
character is 8 bits.

t0 = i * 1024

t1 = j * 32

t2 = k * 4

t3 = t1 + t0

COMPILER DESIGN

t4 = t3 + t2

t5 = x[t4]

Which one of the following statements about the
source code for the C program is CORRECT?

Self-check

Revision card

References