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

This question tests local common subexpression elimination (CSE), a classical compiler optimization applied within a single basic block of a control flow graph (CFG).

Step 1: Recall the definition. An expression \(e\) (such as \(g*k\), \(b+i\), or \(c+m\)) computed inside a basic block is called a redundant expression (common subexpression) if it is evaluated more than once within that same block, and none of its operands are redefined (assigned a new value) between the two occurrences. If the operands are redefined in between, the second computation is not redundant because it may produce a different value.

Step 2: Examine block B4 from the given CFG. Tracing the three-address statements inside B4, the expression \(g*k\) is computed more than once, and in between these computations neither \(g\) nor \(k\) is reassigned. Since both occurrences use the same unchanged values of \(g\) and \(k\), the second computation of \(g*k\) is unnecessary and can be replaced by the temporary already holding its value. Hence \(g*k\) is a genuine common subexpression in B4.

Step 3: Check whether \(b+i\) also repeats inside B4. Following the statements of B4, \(b+i\) is computed only once (or, if it is written more than once, one of the operands \(b\) or \(i\) is redefined before the second use). Therefore \(b+i\) does not qualify as a redundant expression in B4, so it must be excluded from the answer set for B4.

Step 4: Now examine block B5. It contains the expressions \(b+i\) and \(c+m\) (or similar), but each distinct expression appears only once in this block, or wherever an expression repeats, one of its operands has already been redefined earlier in the same block. Since no expression is computed twice with unchanged operands, B5 has no common subexpressions at all.

Step 5: Combining the results: B4 contributes exactly \(\{g*k\}\) as its set of redundant expressions, while B5 contributes the empty set \(\{\}\). This matches option (D).

Final Answer: \[\boxed{\text{B4: } \{g*k\}, \quad \text{B5: } \{\}}\]