GATE 2017 CS (CS1) – Question 62
Consider the expression $(a - 1) * (((b + c) / 3) + d)$. Let $X$ be the minimum number of registers required by an *optimal* code generation (without any register spill) 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 ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 2
Explanation
Expression: $(a-1)*(((b+c)/3)+d)$ on a load/store machine (arithmetic only on registers or immediates).
Evaluate the more register-hungry right operand first, so that only one register is occupied while the left side is computed.
1. `R1 = load b`
2. `R2 = load c`
3. `R1 = R1 + R2` (now $b+c$ in R1; R2 is free)
4. `R1 = R1 / 3` (immediate operand)
5. `R2 = load d`
6. `R1 = R1 + R2` (now $((b+c)/3)+d$ in R1; R2 free)
7. `R2 = load a`
8. `R2 = R2 - 1` (immediate)
9. `R1 = R2 * R1`
At no point are more than two registers live, and one register is not enough (an operation with two register operands needs two). So $X=\mathbf{2}$.