The GATE Grind

GATE 2026 CS (CS1) – Question 42

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

Consider the control flow graph shown in the figure. Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B4 and B5?

Diagram for GATE 2026 CS (CS1) question 42
  1. B4: { b + i }, B5: { c + m }
  2. B4: { g * k }, B5: { c + m }
  3. B4: { g * k, b + i }, B5: { }
  4. B4: { g * k }, B5: { }

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) B4: { g * k }, B5: { }

Explanation

Using standard Available Expressions analysis on the control flow graph:
- An expression $e$ is available at the entry of block $B$ if it is evaluated along all incoming paths from the start node and none of its constituent variables are redefined along any path after the last evaluation.
- In basic block B4: The incoming paths from B2 and B3 compute $g * k$ without modifying $g$ or $k$, making $g * k$ available at the entry of B4 and hence redundant. However, $b + i$ is killed along one of the branches due to an assignment to $b$.
- In basic block B5: The expression $c + m$ is not available along all execution paths reaching B5.

Therefore, the set of redundant expressions is B4: { g * k } and B5: { }. Option (D) is correct.