The program below uses six temporary variables a, b, c, d, e, f.

a = 1
b = 10
c = 20
d = a + b
e = c + d
f = c + e
b = c + e
e = b + f
d = 5 + e
return d + f

Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?

This is a register allocation problem using graph coloring principles. Tracking live variables: a=1 (a live), b=10 (a,b), c=20 (a,b,c), d=a+b (b,c,d) - a dead, e=c+d (c,d,e) - b dead, f=c+e (c,e,f) - d dead, b=c+e (b,c,e,f), e=b+f (b,e,f) - c dead, d=5+e (d,e,f) - b dead, return d+f (d,f). At the end, we need d and f alive simultaneously. Minimum registers needed = 3. We can allocate: R1=e (then f), R2=c (through multiple uses), R3=d (final). This satisfies all constraints with 3 registers. With only 2 registers, we'd need to spill a variable.