Consider the control flow graph shown in the figure. Which one of the…
2026
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: { }
Attempted by 34 students.
Show answer & explanation
Correct answer: D
Analysis of Redundant Expressions
A redundant expression (or common subexpression) in a basic block is one that has been computed previously along all paths leading to the current point, and the operands have not been modified since that computation.
1. Analysis of Basic Block B4
Predecessors of B4 are B2 and B3.
Expression g*k: Computed in B2 (a = g*k) and B3 (t = g*k). Neither block modifies g or k. Thus, g*k is available at the entry of B4.
Expression b+i: Computed in B1. However, in path B1 -> B3 -> B4, the variable b is modified in B3 (b = c+m). Thus, b+i is not available along all paths.
Conclusion for B4: The only redundant expression is { g*k }.
2. Analysis of Basic Block B5
Predecessor of B5 is B4.
Expression c+m: Computed in B3 (b = c+m). However, it is not computed in B2. Since it is not available along the path through B2, it is not redundant in B5.
Conclusion for B5: No redundant expressions { }.
Final Answer
B4: { g*k }, B5: { }