GATE 2023 CS – Question 37
Consider the control flow graph shown. Which one of the following choices correctly lists the set of live variables at the exit point of each basic block?

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}
Explanation
Use $OUT(B)=\bigcup IN(S)$ over successors S, and $IN(B)=USE(B)\cup(OUT(B)-DEF(B))$. The back edge from B4 to B2 means i and j must remain available for the next iteration.
B4 uses a and defines i; its successor B2 needs a,i,j, so $OUT(B4)=\{a,i,j\}$ and $IN(B4)=\{a,j\}$. B3 defines a, so $OUT(B3)=\{a,j\}$ and $IN(B3)=\{j\}$.
B2 has successors B3 and B4, giving $OUT(B2)=\{a,j\}$. Its read-modify-write assignments use both old i and old j, so $IN(B2)=\{a,i,j\}$. Therefore $OUT(B1)=\{a,i,j\}$.
The exit sets for B1,B2,B3,B4 are **{a,i,j}, {a,j}, {a,j}, {a,i,j}**, respectively: **D**.