GATE CS 2017 Set 1 Q52 — Runtime Environments

To find the minimum number of registers $X$ required for the expression $(a-1) * (((b+c)/3)+d)$ on a load/store architecture, we can write an optimal sequence of instructions. In a load/store architecture, memory variables must be loaded into registers before performing operations, while constants can be used as immediate operands.

Let us evaluate the expression using registers $R_1$ and $R_2$:

1. Evaluate $((b+c)/3) + d$:
   • LD R1, b             (R1 = b)
   • LD R2, c             (R2 = c)
   • ADD R1, R1, R2     (R1 = b + c; R2 is now free)
   • DIV R1, R1, #3     (R1 = (b + c) / 3, using immediate operand 3)
   • LD R2, d             (R2 = d)
   • ADD R1, R1, R2     (R1 = ((b + c) / 3) + d; R2 is now free)
2. Evaluate $(a-1)$:
   • LD R2, a             (R2 = a; R1 still holds the right subexpression)
   • SUB R2, R2, #1     (R2 = a - 1, using immediate operand 1)
3. Perform the final multiplication:
   • MUL R1, R2, R1     (R1 = (a - 1) * (((b + c) / 3) + d))

Throughout the execution, we use at most 2 registers ($R_1$ and $R_2$). Since adding two memory variables $b$ and $c$ requires both to be loaded into registers, we need at least 2 registers. Thus, the minimum number of registers required is $2$.