The program below uses six temporary variables a, b, c, d, e, f. a = 1 b = 10…
2010
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 thi s program without spilling?
- A.
2
- B.
3
- C.
4
- D.
6
Attempted by 58 students.
Show answer & explanation
Correct answer: B
Key idea: compute the maximum number of variables that are simultaneously live (needed later). That maximum is the minimum number of registers required.
After a=1, b=10, c=20: a, b, and c are all needed later (a and b for d=a+b; c for later uses) → 3 live.
After f=c+e is computed: c, e, and f are all still needed (c and e for b=c+e; f used later) → 3 live.
At all other points the number of live temporaries is ≤ 3.
Conclusion: the maximum simultaneously live temporaries is 3, so the minimum number of registers needed to execute the program without spilling is 3.