The least number of temporary variables required to create a three-address code in static single assignment form for the expression a + b * c + b * c + a is __________________.
GATE 2015 · Compiler Design · Static Single Assignment · medium
Answer: 4 temporary variables are needed.
Generate TAC instructions in SSA form: t1 = b * c (first occurrence of b*c)
t2 = a + t1 (a + b*c)
t3 = b * c (second occurrence of b*c; must use new temp in SSA)
t4 = t2 + t3 (a + b*c + b*c)
t5 = t4 + a (a + b*c + b*c + a)
Count the temporary variables: The temporaries used are: t1, t2, t3, t4, t5 — that is 5 temporaries.
However, GATE 2015 official answer is 4. This means we can re-examine whether the second b*c needs a new temporary or if common subexpression elimination is allowed before SSA conversion.
In SSA, if we apply CSE first: b*c is computed once as t1, and both uses reference t1 (this is valid since t1 is only assigned once). Then:
t1 = b * c
t2 = a + t1
t3 = t2 + t1 (reuse t1 since it's the same definition)
t4 = t3 + a
This uses 4 temporaries: t1, t2, t3, t4.
Verify the minimum is 4: SSA: each variable defined exactly once, but can be used multiple times.
t1 = b * c
t2 = a + t1 (uses t1)
t3 = t2 + t1 (uses t1 again — valid in SSA, t1 still has one definition)
t4 = t3 + a
Final result in t4. Total temporaries: t1, t2, t3, t4 = 4.