GATE 2023 CS Q.37: solution and answer

Official answer: DSource: Official answer key, GATE 2023 CS (IIT Kanpur)

1. A variable is live at a point if its current value may be used before it is redefined. Use the backward equations $\text{IN}(B)=\text{USE}(B)\cup (\text{OUT}(B)-\text{DEF}(B))$ and $\text{OUT}(B)={\bigcup }_{S\in \text{succ}(B)}\text{IN}(S)$.

2. Successors: B1 $\to$ B2; B2 $\to$ B3, B4; B3 $\to$ B4; B4 $\to$ B2 (back edge) and EXIT. Nothing is live at EXIT.

3. USE/DEF: B1 uses $\{m,n\}$ and defines $\{i,j,a\}$. B2 uses $\{i,j\}$ and defines $\{i,j\}$. B3 uses nothing and defines $\{a\}$. B4 uses $\{a\}$ and defines $\{i\}$. ($m$ and $n$ are never defined in the graph and do not appear in the options.)

4. Because B2 uses $i,j$ before redefining them, $\text{IN}(B2)=\{i,j\}\cup (\text{OUT}(B2)-\{i,j\})$. Also $\text{OUT}(B4)=\text{IN}(B2)\cup \varnothing =\text{IN}(B2)$, since the back edge feeds B2 and EXIT contributes nothing.

5. $\text{IN}(B4)=\{a\}\cup (\text{OUT}(B4)-\{i\})$. $\text{OUT}(B3)=\text{IN}(B4)$ and $\text{IN}(B3)=\text{OUT}(B3)-\{a\}\subseteq \text{IN}(B4)$. Hence $\text{OUT}(B2)=\text{IN}(B3)\cup \text{IN}(B4)=\text{IN}(B4)$.

6. Iterate from $\text{IN}(B2)=\{i,j\}$. Then $\text{OUT}(B4)=\{i,j\}$ and $\text{IN}(B4)=\{a\}\cup \{j\}=\{a,j\}$. So $\text{OUT}(B2)=\{a,j\}$ and $\text{IN}(B2)=\{i,j\}\cup (\{a,j\}-\{i,j\})=\{a,i,j\}$. Recompute: $\text{OUT}(B4)=\{a,i,j\}$, so $\text{IN}(B4)=\{a\}\cup (\{a,i,j\}-\{i\})=\{a,j\}$ again. Nothing changes, so this is the fixed point.

7. Exit sets: $\text{OUT}(B4)=\{a,i,j\}$; $\text{OUT}(B2)=\{a,j\}$; $\text{OUT}(B3)=\text{IN}(B4)=\{a,j\}$; $\text{OUT}(B1)=\text{IN}(B2)=\{a,i,j\}$.

8. This is B1: $\{a,i,j\}$, B2: $\{a,j\}$, B3: $\{a,j\}$, B4: $\{a,i,j\}$, which is option (D).