GATE CS 2010 Q37 — Runtime Environments

To find the minimum number of registers needed without spilling, we perform liveness analysis for each variable at every program point. Since this is a basic block (straight-line code), the live ranges form an interval graph, and the minimum number of registers required is equal to the maximum number of variables live at any single point.

Let's trace the set of live variables after each instruction:

1. a = 1                                    $\rightarrow \text{Live: } \{a\}$
2. b = 10                                   $\rightarrow \text{Live: } \{a, b\}$
3. c = 20                                   $\rightarrow \text{Live: } \{a, b, c\}$   (Size = 3)
4. d = a + b                                $\rightarrow \text{Live: } \{c, d\}$   (a, b die)
5. e = c + d                                $\rightarrow \text{Live: } \{c, e\}$   (d dies)
6. f = c + e                                $\rightarrow \text{Live: } \{c, e, f\}$   (Size = 3)
7. b = c + e                                $\rightarrow \text{Live: } \{b, f\}$   (c, e die)
8. e = b + f                                $\rightarrow \text{Live: } \{e, f\}$   (b dies)
9. d = 5 + e                                $\rightarrow \text{Live: } \{d, f\}$   (e dies)
10. return d + f                            $\rightarrow \text{Live: } \{\}$   (d, f die)

The maximum number of variables live simultaneously at any point is $3$ (at steps 3 and 6). Thus, the minimum number of registers needed to execute this program without spilling is $3$.