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. [Figure: ENTRY → B1 (i = m − 1; j = n; a = 10) → B2 (i = i + 1; j = j − 1); B3 (i = a + 1); B4 (a = 20); EXIT.] 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: (C) B1: {a, i, j}, B2: {a, i, j}, B3: {a, i}, B4: {a}

Explanation

Solve the backward dataflow equations LiveOut(B) = ∪ LiveIn(succ). Using the uses and definitions in each block gives B1 {a,i,j}, B2 {a,i,j}, B3 {a,i}, B4 {a}.