Back to the 2023 paper

Module 4: Intermediate Code Generation, Code Improvement (optimization)

20239m

Translate the expression a=(a+b)∗(c+d)+(a+b+c)a = (a + b) * (c + d) + (a + b + c) into
(i) Quadruple
(ii) Triple
(iii) Indirect triple

Worked SolutionAI Assisted

Three-address code for a=(a+b)∗(c+d)+(a+b+c)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.

Similar questions

Free AppAndroid App

Coursify Android App

Generate AI courses, take quick quizzes between classes, and master complex engineering concepts on the go.