Three-address code instruction forms; quadruples, triples, indirect triples

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• How many nodes does a DAG have for an expression in which b − c appears twice? from Lesson 4.1
• Translate 9 − 5 + 2 to postfix with the scheme R → + T {print('+')} R | − T {print('−')} R | ε. from Lesson 3.3
• Which phase produces simple machine-independent code with temporaries t1, t2? from Lesson 0.1.3

1 · The Story

📖

Index cards

Dev turns each outline into a stack of index cards. Every card does one small thing and names at most three things: two inputs and a result, like “t2 = b times t1”. Intermediate results get scratch names t1, t2, ….

His filing has three styles. In the first, every card has four boxes: operation, first input, second input, result. In the second, cards have no result box: later cards say “use the result of card 3”. That saves space, but if Ishaan later moves card 3, every reference breaks. In the third, the cards stay fixed and a separate list says in which order to read them; moving a card means editing the list only.

2 · Predict First

🤔

For a = b * −c + b * −c, translated without sharing, how many instructions and how many temporaries are needed? Write your guess down. The answer is in the vault.

3 · Core Concept

Three-address code

Three-address code (TAC) is a linear IR: each instruction has at most one operator on the right side and at most three addresses (names, constants or compiler-generated temporaries). A syntax tree or DAG is linearised bottom-up, a temporary for each interior node.

Instruction forms

Quadruples

A quadruple has four fields: op, arg1, arg2, result. Temporaries are explicit names. Easy to rearrange (results are named), but temporaries must be entered in the symbol table.

Triples

A triple has three fields: op, arg1, arg2; the result is referred to by the triple’s position, written (k). An assignment x = (k) becomes a triple (=, x, (k)). Saves space, but moving an instruction changes every reference to it. Convention: like the Dragon book, triples here are numbered from (0); some books start at (1). Questions usually show their numbering, so follow it.

Indirect triples

Indirect triples keep the triples in place and add a separate list of pointers to them giving the execution order. An optimizer can reorder instructions by reordering the pointer list only.

Story → compiler term

4 · Visual

( 1) t1 = minus c
( 2) t2 = b * t1
( 3) t3 = minus c
( 4) t4 = b * t3
( 5) t5 = t2 + t4
( 6) a = t5

Quadruples for a = b * −c + b * −c.

Triples: results are referred to by position (numbered from 0).

Indirect triples: the list (35 … 40) gives the order; reordering edits only this list.

5 · Worked Examples

Example 1 Easy

Write TAC for x = (a + b) * (c − d) + e.

Solution

( 1) t1 = a + b
( 2) t2 = c - d
( 3) t3 = t1 * t2
( 4) x = t3 + e

4 instructions, 3 temporaries; the last operation writes directly into x. One card per operation, as in Dev’s filing.

Example 2 Medium

Give the quadruples, triples and indirect triples for a = b * −c + b * −c.

Solution

See the three tables above. Quadruples name every temporary; triples replace t1 … t5 by (0) … (4); indirect triples add the order list. Ishaan can reorder the indirect version by editing only the list.

Example 3 GATE

For x = a * b + c * d − e, what is the minimum number of temporaries if each instruction may write its result into the target only at the end?

Solution

t1 = a * b; t2 = c * d; t3 = t1 + t2; x = t3 − e: 3 temporaries and 4 instructions (as generated). With temporary reuse (t1 = a * b; t2 = c * d; t1 = t1 + t2) two would suffice; questions say which rule applies.

6 · Shortcuts

⚡

Instructions = operators (plus one copy if the result goes through a temporary into a variable); temporaries = operator nodes not written directly into a variable. Valid when: counting TAC for an expression without sharing.

⚡

Triples from quads: delete the result column; replace each temporary by the number of the instruction that computed it. Valid when: converting between representations.

7 · GATE Traps

⚠️

• A triple has no result field; its result is its position.
• Reordering triples breaks references; indirect triples avoid that.
• Quadruples need temporaries in the symbol table; triples do not.
• Check the numbering convention: (0) or (1).
• x = y op z has at most one operator: a + b * c needs two instructions.

8 · Memory Hook

🧠

Quad = four boxes; triple = three boxes, results by number; indirect = a reading list of triple numbers.

9 · Connect the Dots

Expressions with plain variables are easy. Arrays need an address computed from indices, row sizes and element widths. The next lesson computes those addresses and writes them as three-address code.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markTriples

Compared with quadruples, triples:

• (A) have an explicit result field
• (B) refer to results by instruction position
• (C) are easier to reorder
• (D) need more fields

Q2NAT1 markCount

How many three-address instructions does x = (a + b) * (c − d) + e need (no sharing, last operation directly into x)?

Numerical answer: ________

Q3MCQ1 markIndirect

The advantage of indirect triples over triples is:

• (A) fewer instructions
• (B) instructions can be reordered by changing only the pointer list
• (C) no need for temporaries in expressions
• (D) they are always faster to execute

Q4MSQ1 markForms

Which are valid three-address instructions?

• (A) x = y + z
• (B) x = y + z * w
• (C) if x y goto L
• (D) param x

Q5NAT2 marksTemporaries

Translating a = b * −c + b * −c without sharing (every operator result in a new temporary, then a = t), how many temporaries are used?

Numerical answer: ________

11 · Rule Card

• TAC: ≤ 1 operator, ≤ 3 addresses per instruction; temporaries for intermediate values.
• Forms: x = y op z, x = op y, x = y, goto L, if x relop y goto L, param/call/return, x = y[i], x[i] = y, &, *.
• Quadruple: (op, arg1, arg2, result).
• Triple: (op, arg1, arg2), result = position (k).
• Indirect triples: pointer list gives order; easy reordering.

12 · Concept Ledger

three-address code (TAC)temporarygoto / conditional jumpparam / call p, n / returnquadrupletripleindirect triples

13 · Answer Vault