GATE CS 2026 Set 1 Q.42: Intermediate Code Generation, Data Flow Analysis and Code Optimization

Consider the control flow graph shown in the figure.

Control flow graph with ENTRY leading to basic block B1 (a = b + i), which branches to B2 (a = g * k; f = d - f; a = c * 4) and B3 (t = g * k; b = c + m); both B2 and B3 merge into B4 (x = g * k; y = b + i), which flows to B5 (z = c + m) and then EXIT.

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.

B4: $\{ b + i \}$
B5: $\{ c + m \}$

B4: $\{ g * k \}$
B5: $\{ c + m \}$

B4: $\{ g * k, b + i \}$
B5: $\{ \}$

B4: $\{ g * k \}$
B5: $\{ \}$

Official answer and solution

Official answer: D
From: Official GATE 2026 answer key

Solution

Perform available-expressions analysis along all paths from ENTRY to B4 and B5.

An expression is redundant (a common subexpression) at a point if and only if it is available on every path from ENTRY to that point without any of its operands being redefined afterwards:

In block B4 (x = g * k, y = b + i):
- g * k: Computed in B2 (a = g * k) and in B3 (t = g * k), and neither g nor k is modified later in B2 or B3. Since every path from ENTRY to B4 passes through either B2 or B3, g * k is available at B4 and is therefore redundant.
- b + i: Computed in B1, but along the path B1 -> B3 -> B4, block B3 redefines b (b = c + m), killing b + i. Hence b + i is not available at B4.
In block B5 (z = c + m):
- c + m: Computed in B3, but never computed along the path B1 -> B2 -> B4 -> B5. Hence c + m is not available at B5.

Therefore, the redundant expressions are B4: { g * k } and B5: { }.

Final answer

Option (D)

Common trap

Treating c + m or b + i as available when they are only available along one of the two branches.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 42 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source