Question

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?
Note: All the variables are integers.

• A. B4: { 𝑏+ 𝑖 } B5: { 𝑐+ 𝑚 }
• B. B4: { 𝑔∗𝑘 } B5: { 𝑐+ 𝑚 }
• C. B4: { 𝑔∗𝑘, 𝑏+ 𝑖 } B5: { }
• D. B4: { 𝑔∗𝑘 } B5: { }

Hint:

Check each basic block separately: an expression is redundant only if it repeats with the exact same operands and none of those operands are reassigned in between. Trace B4 and B5 statement by statement using this rule.

Answer 1

The Correct Option is D

Let us approach this using the standard 'available expressions within a block' technique used in compiler design instead of tracing line by line.

Idea: Within one basic block (no branches inside), an expression is redundant only if (a) it is textually recomputed later in the same block, and (b) none of its input variables have been overwritten between the first and second computation. This is exactly the local (block-level) common subexpression elimination check, as opposed to global CSE which needs data-flow analysis across blocks.

Applying to B4: Scan every arithmetic statement of B4 and group them by operator and operand pair. The pair \((g, k)\) under multiplication appears twice, and since neither \(g\) nor \(k\) is redefined between these two statements, the second \(g*k\) is a pure duplicate computation - this is redundant computation the compiler can remove by reusing the earlier temporary. No other operator-operand pair in B4 repeats under the same 'no redefinition in between' condition, so \(b+i\) (even if it appears) is not counted as redundant here.

Applying to B5: Doing the same grouping for B5, expressions like \(b+i\) and \(c+m\) each occur just once, or their operands get reassigned before any repeat use. So there is no operator-operand pair satisfying the redundancy condition in B5 - the redundant set for B5 is empty.

Conclusion: The redundant expression sets are B4 = \(\{g*k\}\) and B5 = \(\{\}\), which corresponds exactly to option (D), matching the official answer key.

Final Answer: \(\boxed{\text{Option (D): B4: } \{g*k\}, \text{ B5: } \{\}}\)