Chapter 24 of 33

Quadruples, Triples & Indirect Triples

In the previous chapter, Intermediate Code & Three-Address Code, we wrote instructions like t1 = a + b on paper. Paper is fine for humans, but a compiler has to store those instructions in memory, in some data structure that later phases (the optimizer and the code generator) can read, rearrange and delete. How exactly should one instruction be stored?

Think of a teacher keeping marks. She can write every student's name next to each mark ("Ravi: 78"), or she can number the rows and refer to them later ("row 4 + row 7"). The first way uses more ink but is easy to rearrange; the second is compact but breaks the moment rows are moved. Compilers face exactly this trade-off, and the three classic answers are quadruples, triples and indirect triples.

Quadruples, triples and indirect triples are three record-based data structures for storing three-address code. A quadruple has four fields (op, arg1, arg2, result); a triple has three fields (op, arg1, arg2) and refers to earlier results by their position; indirect triples store the triples once and keep a separate list of pointers that gives the execution order.

In this chapter we build all three representations for the same expressions, see what happens when the optimizer moves or deletes an instruction, handle unary minus, arrays, copies and jumps, and finish with exam-style counting problems. Every table here was generated by a small Python program, which also executed the quadruples and triples on hundreds of random inputs and checked that they compute the same value as the original expression.


The Running Example

We will translate this assignment:

x = (a + b) * (a - c) + (a + b) / d

Translating it naively (a new temporary for every operator, no optimization) gives this three-address code:

t1 = a + b
t2 = a - c
t3 = t1 * t2
t4 = a + b
t5 = t4 / d
t6 = t3 + t5
x  = t6

Notice that a + b is computed twice. That is deliberate: the translator does not look for repeated work, that is the optimizer's job. We will use this redundancy later to see how each representation copes with changes.


Quadruples

A quadruple (often shortened to "quad") is a record with four fields:

Field

Meaning

op

An internal code for the operator: +, *, minus, =, goto, if<, param, call, ...

arg1

First operand: a variable name, a constant or a temporary (in practice, a pointer to its symbol-table entry).

arg2

Second operand, left empty for unary operators and copies.

result

Where the answer goes: a variable or temporary. For jumps it holds the target label.

The instruction x = y op z becomes the quad (op, y, z, x). Our running example:

#

op

arg1

arg2

result

(0)

+

a

b

t1

(1)

-

a

c

t2

(2)

*

t1

t2

t3

(3)

+

a

b

t4

(4)

/

t4

d

t5

(5)

+

t3

t5

t6

(6)

=

t6

x

Three conventions are worth memorising, because exam answers are judged on them:

  • Unary operators leave arg2 empty: t1 = minus a is (minus, a, , t1).

  • Copies such as x = t6 use op =, arg1 = source, result = destination, and an empty arg2.

  • Unconditional jumps put the target in result: goto L is (goto, , , L). Conditional jumps use both arguments: if a < b goto L is (if<, a, b, L). Parameter passing is (param, x, , ) and a call is (call, p, n, ), where n is the number of parameters (or (call, p, n, t) when the returned value goes into t).

Why do temporaries appear as names? Because each temporary is entered in the symbol table, just like a programmer's variable. A quad's fields are really pointers to symbol-table entries, so later phases can find the type and, eventually, the memory location or register of every temporary.

A small optimization you will see in books: the last two quads (+, t3, t5, t6) and (=, t6, , x) can be merged into (+, t3, t5, x), saving a temporary and an instruction. A simple translator emits the copy; an optimizer removes it.


Triples

Look at the result column of the quad table. Most entries are temporaries that exist only to name "the value computed by instruction k". If we simply refer to instruction k by its number, we can throw away the result field and the temporaries.

A triple has three fields: op, arg1, arg2. An argument is either a name or constant, or a parenthesised position like (2), meaning "the value computed by triple 2".

#

op

arg1

arg2

(0)

+

a

b

(1)

-

a

c

(2)

*

(0)

(1)

(3)

+

a

b

(4)

/

(3)

d

(5)

+

(2)

(4)

(6)

=

x

(5)

Two things changed besides the missing column:

  1. Every t1 ... t6 is gone. Triple (2) says "multiply the value of triple (0) by the value of triple (1)".

  2. The copy x = t6 becomes (=, x, (5)): the destination is now arg1, because there is no result field to put it in. This is a classic trap; in a quad the destination is the last field, in a triple it is arg1.

A triple is, in fact, just a compact way of writing the syntax tree (or DAG) of the expression: each triple is a node, and (k) is an edge pointing to node k.

Operations That Need Two Triples

An instruction that uses three addresses, such as the indexed assignment x[i] = y, cannot fit in two argument fields. It is split into two triples:

x[i] = y                      x = y[i]

(0)  []=   x    i             (0)  =[]   y    i
(1)  =     (0)  y             (1)  =     x    (0)

In the left column, triple (0) computes the location x[i] and triple (1) stores y into it. In the right column, triple (0) fetches y[i] and triple (1) copies that value into x. In quads, each of these fits in a single instruction, because a quad has three address fields. x = y[i] is naturally (=[], y, i, x). For x[i] = y, books do not agree on which field holds which address (for example ([]=, y, i, x) versus ([]=, i, y, x)), so if an exam asks for it, state your convention in one line before writing the answer.


Indirect Triples

Triples have one serious weakness: the position of an instruction is its name. If the optimizer moves or deletes an instruction, every reference to the moved instructions must be found and renumbered. Indirect triples fix this with one extra level of indirection.

In indirect triples, the triples themselves are stored once, in any order, and a separate instruction list (an array of pointers to triples) gives the order in which they are executed. Reordering the program means reordering the pointer list; the triples, and the references between them, do not change.

For the running example (the instruction list is numbered from 35 just to make it obvious that the two numbering systems are independent):

Instruction list            Triples
+-----+------+              +-----+-----+------+------+
| 35  | (0)  |              | (0) |  +  |  a   |  b   |
| 36  | (1)  |              | (1) |  -  |  a   |  c   |
| 37  | (2)  |              | (2) |  *  | (0)  | (1)  |
| 38  | (3)  |              | (3) |  +  |  a   |  b   |
| 39  | (4)  |              | (4) |  /  | (3)  |  d   |
| 40  | (5)  |              | (5) |  +  | (2)  | (4)  |
| 41  | (6)  |              | (6) |  =  |  x   | (5)  |
+-----+------+              +-----+-----+------+------+

Right now this looks like the plain triples plus a useless list. Its value shows only when the code changes, so let us change it.


What Happens When the Optimizer Edits the Code?

The optimizer notices that a + b is computed twice (a common subexpression) and decides to delete the second computation and reuse the first. Let us apply that one change to each representation.

Quadruples: Easy

Delete quad (3) and replace t4 by t1 in quad (4). Every other quad refers to values by name (t3, t5), and names do not care where the instruction lives:

(0)  +   a    b    t1
(1)  -   a    c    t2
(2)  *   t1   t2   t3
(3)  /   t1   d    t5        <- was (4); only t4 changed to t1
(4)  +   t3   t5   t6
(5)  =   t6        x

Triples: Painful

Delete triple (3). Now triples (4), (5), (6) slide up to become (3), (4), (5), and every argument that pointed at them must be rewritten:

(0)  +   a    b
(1)  -   a    c
(2)  *   (0)  (1)
(3)  /   (0)  d           <- was (4); its (3) became (0)
(4)  +   (2)  (3)         <- was (5); its (4) became (3)
(5)  =   x    (4)         <- was (6); its (5) became (4)

Here three triples had to be edited for one deletion. In a real function with thousands of instructions, the compiler would have to scan everything after the deleted instruction. Moving an instruction (for example, hoisting a computation out of a loop) causes the same problem.

Indirect Triples: Easy Again

Remove entry 38 from the instruction list and change the one argument of triple (4) from (3) to (0). The triple numbers do not change, so nothing else is touched:

Instruction list          Triples (unchanged except (4))
 35  (0)                  (0)  +   a    b
 36  (1)                  (1)  -   a    c
 37  (2)                  (2)  *   (0)  (1)
 38  (4)                  (3)  +   a    b      <- no longer listed
 39  (5)                  (4)  /   (0)  d
 40  (6)                  (5)  +   (2)  (4)
                          (6)  =   x    (5)

This is the whole point of indirect triples: they keep the compact form of triples but give the optimizer the freedom that quads have.


Comparing the Three

Point

Quadruples

Triples

Indirect triples

Fields per instruction

4 (op, arg1, arg2, result)

3 (op, arg1, arg2)

3, plus one pointer in the instruction list

How a computed value is referred to

By a temporary's name

By the position of the triple that computed it

By the triple's number, which never changes

Temporaries in symbol table

Yes, many

No

No

Space

Most (extra field plus temporaries)

Least

Between the two

Moving / deleting instructions

Easy

Hard: all references must be renumbered

Easy: reorder the pointer list

Suitability for an optimizing compiler

Good

Poor

Good

Access to a value

Direct, by name

Direct, by position

One extra indirection

x[i] = y

1 instruction

2 triples

2 triples

A practical note: real compilers today mostly use the quad-like style (each instruction names its result), often in static single-assignment (SSA) form, where every name is assigned exactly once. LLVM IR is a well-known example: %3 = add i32 %1, %2 is essentially a quad. Triples are mainly of historical and exam interest, but the idea "a value is identified by the instruction that produced it" lives on: inside LLVM, an instruction object is the value it computes.


Solved Problems

Problem 1: Unary Minus

Give the three-address code, quadruples and triples for y = -a * (b + c) - -a.

Solution. Unary minus has the highest precedence here, so the expression is ((-a) * (b + c)) - (-a).

Three-address code        Quadruples                    Triples
t1 = minus a              (0) minus  a         t1       (0) minus  a
t2 = b + c                (1) +      b    c    t2       (1) +      b    c
t3 = t1 * t2              (2) *      t1   t2   t3       (2) *      (0)  (1)
t4 = minus a              (3) minus  a         t4       (3) minus  a
t5 = t3 - t4              (4) -      t3   t4   t5       (4) -      (2)  (3)
y  = t5                   (5) =      t5        y        (5) =      y    (4)

(Blank columns are empty fields.)

Writing minus (not -) for the unary operator matters, because - with an empty arg2 would be ambiguous. Note again that the copy into y puts y in the result field of the quad but in arg1 of the triple.

Problem 2: Counting Temporaries (SSA)

What is the minimum number of temporaries needed to translate q + r / 3 + s - t * 5 + u * v / w into three-address code in static single-assignment form, if the final value is also held in a temporary?

Solution. In SSA form no name may be assigned twice, so a temporary cannot be reused. Each binary operator produces a new value, so we simply count operators. Parsing with the usual precedence and left associativity:

t1 = r / 3
t2 = q + t1
t3 = t2 + s
t4 = t * 5
t5 = t3 - t4
t6 = u * v
t7 = t6 / w
t8 = t5 + t7

There are 8 operators (/ + + - * + * /), so the answer is 8. The order of the instructions can vary (for example t4 = t * 5 could come first), but the count cannot.

Problem 3: Counting Temporaries When Reuse Is Allowed

Without the SSA restriction, how few temporaries are needed for the running example x = (a + b) * (a - c) + (a + b) / d?

Solution. A temporary can be reused once its value is no longer needed. The right side of the outer + must be computed while the left side's value waits, and the left side itself needs two values at once for its *. So two are always enough and two are needed:

t1 = a + b
t2 = a - c
t1 = t1 * t2      // t1 now holds (a+b)*(a-c)
t2 = a + b
t2 = t2 / d
x  = t1 + t2

Answer: 2. (If you are allowed to assign intermediate values into x itself, you could do with fewer, but questions normally forbid touching program variables.)

Problem 4: A Fragment With a Jump

Write the quadruples for:

if (a < b) x = y + z; else x = y - z;

Solution. Number the quads from 100:

(100)  if<    a    b    102
(101)  goto             105
(102)  +      y    z    t1
(103)  =      t1        x
(104)  goto             107
(105)  -      y    z    t2
(106)  =      t2        x
(107)  ...

Jump targets are quad numbers stored in the result field. Generating such code, and in particular filling in a target like 105 before we have reached quad 105, is the subject of the next chapter, Translating Control Flow & Backpatching.

Problem 5: How Many Triples?

How many triples are needed for a[i] = b * c + b * c without optimization? With common-subexpression elimination?

Solution. Without optimization: b * c, b * c, +, then the indexed assignment, which needs two triples ([]= and =). Total 5. With CSE the second b * c disappears and the + becomes (+, (0), (0)), giving 4:

(0)  *    b    c
(1)  +    (0)  (0)
(2)  []=  a    i
(3)  =    (2)  (1)

Common Mistakes

  • Putting the destination of a copy in the wrong field. Quad: (=, t6, , x). Triple: (=, x, (5)).

  • Using - for unary minus. Write minus (or uminus) and leave arg2 empty.

  • Saying indirect triples save space over triples. They use slightly more space than triples (the extra pointer list). Their advantage is that instructions can be reordered cheaply.

  • Forgetting that triples refer by position. After moving or deleting a triple, every reference to later triples must be renumbered.

  • Counting x[i] = y as one triple. It needs two.

  • Mixing up "minimum temporaries" with and without SSA. In SSA every operator needs its own temporary; with reuse, the count depends on how many values must be alive at the same time.


Interview and Exam Questions

Q1. What are the fields of a quadruple and of a triple?

Quadruple: op, arg1, arg2, result. Triple: op, arg1, arg2; the result of a triple is referred to by the triple's position, such as (3).

Q2. Why are quadruples preferred over triples in an optimizing compiler?

Because quads refer to values by name (temporaries), an instruction can be moved or deleted without changing any other instruction. With triples, values are referred to by position, so moving one triple forces renumbering every reference to it and to the triples after it.

Q3. What problem do indirect triples solve, and at what cost?

They allow instructions to be reordered or deleted by editing only a list of pointers, while the triples and their mutual references stay fixed. The cost is the extra pointer list and one more indirection when walking the code.

Q4. Which representation does not need temporaries in the symbol table?

Triples and indirect triples. Their intermediate values are named by triple numbers. Quadruples need a symbol-table entry for every temporary.

Q5. How many triples does x = y[i] need? Write them.

Two: (0) =[] y i, which fetches y[i], and (1) = x (0), which copies it into x.

Q6. Give the quadruples for t = a * b + c and say how many temporaries a triple form would need.

Quads: (*, a, b, t1), (+, t1, c, t2), (=, t2, , t), or merged: (*, a, b, t1), (+, t1, c, t). Triples need zero temporaries: (0) * a b, (1) + (0) c, (2) = t (1).

Q7. Is a triple representation related to the syntax tree or DAG?

Yes. Each triple is a node and each reference (k) is an edge to node k. If common subexpressions share one triple, the triples form a DAG; this idea is developed in DAG Representation of Basic Blocks.


Summary

  • Quadruples store (op, arg1, arg2, result). Values are named by temporaries, so code is easy to rearrange, at the cost of space and many symbol-table entries.

  • Triples store (op, arg1, arg2) and refer to a computed value by its position (k). Compact, but moving or deleting an instruction forces renumbering.

  • Indirect triples keep triples fixed and order them through a separate pointer list, combining compactness with easy reordering.

  • Conventions: unary minus is minus with empty arg2; a copy's destination is the result field of a quad but arg1 of a triple; jumps put the target in the result field; x[i] = y and x = y[i] need two triples.

  • Counting questions: in SSA, temporaries = number of operators; with reuse, it is the number of values that must be alive at once.

So far our code has been straight-line arithmetic. Next, in Translating Control Flow & Backpatching, we generate code for if, while and boolean expressions, and learn how to fill in jump targets that are not known yet.