Computer Sciences > GATE 2026 SET-1 > Code Optimization
Consider the following control flow graph:
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)
A
B4 = {g*k},  B5 = {}
B
B4 = {b+i},  B5 = {c+m}
C
B4 = {g*k},  B5 = {c+m}
D
B4 = {g*k, b+i},  B5 = {}

Correct : c

The correct answer is Option C: B4 = {g*k}, B5 = {c+m}.
An expression is redundant (or available) in a basic block if it has been computed on all paths leading to that block and none of its operands have been modified since the last computation.
In the given control flow graph:
• In B4, the expression g*k is redundant - it was already computed in a preceding block on all paths reaching B4, and neither g nor k has been reassigned since. So g*k need not be recomputed.
• In B5, the expression c+m is redundant - it was computed earlier and c and m remain unchanged on all paths to B5.
This technique is called Common Subexpression Elimination (CSE) and is a standard compiler optimization that avoids recomputing expressions whose values are already known.

Similar Questions

Which ONE of the following techniques used in compiler code optimization uses live variable analysis?
#1356 MCQ
A palindrome is a word that reads the same forwards and backwards. In a game of words, a player has the following two plates painted with letters. From...
#1 MCQ
Which number does not belong in the series below? 2, 5, 10, 17, 26, 37, 50, 64
#4 MCQ

Related Topics

GATE CS 2026 GATE CS 2026 Set-1 Q13 Redundant Expressions Basic Blocks B4 B5 Common Subexpression Elimination Control Flow Graph Code Optimization GATE Compiler Design GATE 2026 CSE Optimization Available Expressions GATE CS 2026 Solved

Unique Visitor Count

Total Unique Visitors

Loading......