Consider the expression (a - b) + e * (c + d). Let X be the minimum number of…
2025
Consider the expression (a - b) + e * (c + d). Let X be the minimum number of registers required by an optimal code generation algorithm for a load/store architecture, in which:
i. Only load and store instructions can have memory operands, and
ii. Arithmetic instructions can have only register or immediate operands.
The value of X is ________.
- A.
4
- B.
3
- C.
2
- D.
12
Attempted by 23 students.
Show answer & explanation
Correct answer: B
Apply the Sethi-Ullman algorithm. Sub-expressions (c + d) and (a - b) each require 2 registers as their operands are leaves. The multiplication e * (c + d) requires max(1, 2) = 2 registers. Finally, adding the two sub-results both needing 2 registers requires max(2, 2) + 1 = 3 registers.