Skip to content
GATEiit

GATE CSE 2026 Session 1 Q42: Redundant (common) subexpressions in blocks B4 and B5 of a CFG

Question

Consider the control flow graph shown in the figure.

Control flow graph: ENTRY to B1 (a = b + i); B1 branches to B2 (a = g * k; f = d - f; a = c * 4) and B3 (t = g * k; b = c + m); both lead to B4 (x = g * k; y = b + i), then B5 (z = c + m), then EXIT
Tap the figure to enlarge

Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B4 and B5?

Note: All the variables are integers.

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: D (official GATE 2026 final answer key)

Concept used: Available expressions: an expression is redundant at a point only if it is computed, and not killed, on every path reaching it.

First step: Check each path into B4: g * k is computed in both B2 and B3, but B3 redefines b (killing b + i) and only B3 computes c + m.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 1 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More Compiler Design PYQs

PracticePractise Compiler Design questions →Full paperAll GATE CSE 2026 Session 1 questions →