The GATE Grind

GATE 2023 CS – Question 37

Compiler Design · Code Optimization and Data Flow Analysis · 2 marks · Multiple choice

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?

Diagram for GATE 2023 CS question 37
  1. B1: {}, B2: {a}, B3: {a}, B4: {a}
  2. B1: {i, j}, B2: {a}, B3: {a}, B4: {i}
  3. B1: {a, i, j}, B2: {a, i, j}, B3: {a, i}, B4: {a}
  4. B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}

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**.

More Code Optimization and Data Flow Analysis questions

All Code Optimization and Data Flow Analysis questions →