Consider the expression \((a-1) * (((b+c)/3)+d)\). Let \(X\) be the minimum…
2017
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
only load and store instructions can have memory operands and
arithmetic instructions can have only register or immediate operands.
The value of \(X\) is _____________ .
Attempted by 24 students.
Show answer & explanation
Correct answer: 2
Answer: 2.
Why: Use the register-need (Sethi–Ullman) idea and the fact that immediates can be used directly by arithmetic instructions while variables must be loaded from memory.
The subexpression (a - 1) needs 1 register (load a, subtract immediate 1).
The subexpression (b + c) needs 2 registers (load b and c into two registers and add).
Dividing (b + c) by 3 uses the result register and the immediate 3, so still needs 2 registers.
Adding d to that result combines a 2-register value with a 1-register value and therefore requires 2 registers.
Finally multiplying (a - 1) (1 register) with the right side (2 registers) requires 2 registers overall (evaluate the 2-register side first).
Concrete 2-register evaluation schedule (one possible ordering):
Load b into R1; load c into R2; add R1,R1,R2 -> R1 = b+c.
Divide R1 by immediate 3 -> R1 = (b+c)/3.
Load d into R2; add R1,R1,R2 -> R1 = ((b+c)/3)+d.
Load a into R2; subtract immediate 1 from R2 -> R2 = a-1.
Multiply R1,R1,R2 -> final result in R1.
Since this schedule never needs more than two registers, the minimum number of registers required is 2.