Compiler Design

Answer: (ii) At most 3 addresses

Explanation

A three-address code is an intermediate-code statement of the general form:

$$\mathrm{result} = \mathrm{arg}_1\ \text{op}\ \mathrm{arg}_2$$

Each statement contains at most three operands/addresses: the destination plus at most two source operands. The name comes from the fact that a single 3-address statement involves at most three addresses.

• It is not exactly 3 addresses — a statement like t = a or t = -a has fewer than three addresses.
• It can contain a unary operation (e.g. t = -x), so saying "no unary operator" is wrong.
• Therefore "Exactly 3 address" (i), "No unary operator" (iii), and "None" (iv) are incorrect.

The correct statement is:

$$\boxed{\text{(ii) At most 3 addresses}}$$

Answer: (iii) Common subexpression elimination

Explanation

Common subexpression elimination (CSE) detects an expression that was already computed and whose operands have not changed since, and reuses the earlier result instead of recomputing it.

Before:

x = a * b + c
y = a * b + d

After CSE:

t = a * b
x = t + c
y = t + d

The other options: loop interchange changes loop order (cache behaviour); dead-code elimination removes useless code; register allocation maps variables to registers.

$$\boxed{\text{(iii) Common subexpression elimination}}$$

Answer: (ii) Loop Jamming (loop jamming)

Explanation

• Loop jamming / loop fusion (jamming) is the compiler optimization that merges the bodies of two adjacent loops that have the same range of traversal, into a single loop, so the loop control overhead runs only once.
• Loop rolling is not a standard optimization.
• Constant folding folds expressions with only constants at compile time, evaluating them at compile time (e.g. x = 3+4 → x = 7), unrelated to merging loops.
• "None of the above" is therefore wrong.

Hence the method which merges the bodies of two loops is:

$$\boxed{\text{(ii)Loop jamming (loop fusion)}}$$

Three-address code for $a=(a+b)*(c+d)+(a+b+c)$

Start from the natural statement sequence:

t1 = a + b
t2 = c + d
t3 = t1 * t2
t4 = a + b         (or reuse t1)
t5 = t4 + c        → computes (a+b) + c
t6 = t3 + t5
a  = t6

(i) Quadruples

Form (op, arg1, arg2, result):

No	op	arg1	arg2	result
1	+	a	b	t1
2	+	c	d	t2
3	*	t1	t2	t3
4	+	a	b	t4
5	+	t4	c	t5
6	+	t3	t5	t6
7	=	t6	(empty)	a

(ii) Triples

Three fields (op, arg1, arg2); a result value is referenced by its triple index (k).

#	op	arg1	arg2
1	+	a	b
2	+	c	d
3	*	(1)	(2)
4	+	a	b
5	+	(4)	c
6	+	(3)	(5)
7	=	(6)	a

(iii) Indirect triples

List of triples plus a separate indirect table that holds the execution-order pointers to the triples; changing an instruction (e.g. removing a common subexpression) is done by redirecting a pointer, no renumbering needed.

Triples:

#	op	arg1	arg2
1	+	a	b
2	+	c	d
3	*	(1)	(2)
4	+	(1)	c
5	+	(3)	(4)
6	=	(5)	a

Indirect table (execution order):

(1) → triple 1
(2) → triple 2
(3) → triple 3
(4) → triple 4
(5) → triple 5
(6) → triple 6   → assigns into a

Since triple 4 reuses triple 1 (a+b), the (a+b) subexpression appears once; that is exactly how the indirection layer makes common-subexpression elimination and code motion easy.

Summary

• Quadruple: explicit result names — easiest to manipulate, most commonly used in optimizers.
• Triple: compact (no temporaries), but moving/deleting statements requires renumbering.
• Indirect triple: triples + index vector — easy CSE/code motion at the price of one extra level of indirection.