Question 52

We are given the expression $(a - 1) * (((b + c) / 3) + d)$ on a load/store architecture where memory operands must be loaded first, and arithmetic operations can use registers or immediate constants.

Let us determine if 2 registers (R1, R2) are sufficient without spilling:

1. Evaluate $(b + c) / 3$:
   • LOAD R1, b (R1 holds $b$)
   • LOAD R2, c (R2 holds $c$)
   • ADD R1, R1, R2 (R1 holds $b + c$; R2 is now free)
   • DIV R1, R1, #3 (R1 holds $(b + c) / 3$ using immediate 3)

2. Add $d$:
   • LOAD R2, d (R2 holds $d$)
   • ADD R1, R1, R2 (R1 holds $((b + c) / 3) + d$; R2 is free again)

3. Evaluate $(a - 1)$ while holding the previous subexpression in R1:
   • LOAD R2, a (R2 holds $a$)
   • SUB R2, R2, #1 (R2 holds $a - 1$ using immediate 1)

4. Final multiplication:
   • MUL R1, R1, R2 (R1 holds the final result)
     At every instruction, at most 2 registers (R1 and R2) are required simultaneously, and no register spill to memory is needed. Hence, the minimum number of registers is 2.