GATE CS 2004 Q10 — Local Optimization

To find the evaluation order that produces the shortest code, let's analyze the instructions generated under a single-register ($R$) constraint. The subtraction operation $E1 - E2$ requires the first operand ($E1$) to be in the register $R$ at the time of subtraction (i.e., $R \leftarrow R - \text{operand}$).

Case 1: $E1$ is evaluated first

1. Evaluate $E1$ into $R$.
2. Since we need $R$ to evaluate $E2$, we must spill $E1$ to a temporary memory location:
   Store R → T1
3. Evaluate $E2$ into $R$.
4. Since the subtraction requires $E1$ (the first operand) to be in $R$, we cannot subtract directly. We must:
   • Spill $E2$: Store R → T2
   • Load $E1$ back: Load T1 → R
   • Perform subtraction: Sub T2 from R ($R \leftarrow R - T2$)

This sequence requires 2 Store and 1 Load extra instructions.

Case 2: $E2$ is evaluated first

1. Evaluate $E2$ into $R$.
2. Spill $E2$ to a temporary memory location to free $R$:
   Store R → T1
3. Evaluate $E1$ into $R$. Now, the first operand $E1$ is already in $R$.
4. Perform subtraction directly using the spilled value of $E2$:
   Sub T1 from R ($R \leftarrow R - T1$)

This sequence requires only 1 Store extra instruction.

Thus, evaluating $E2$ first yields the shortest possible code.