B1 has two successors, B2 and B3, both B2 and B3 flow into B4, and B4 flows into B5.
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.
Show Hint
An expression is redundant (available) at a block only if it has already been computed with the same operand values along every path reaching that block, so check both incoming paths to B4 and B5 separately before deciding.
Step 1: State the rule for a redundant (available) expression. An expression computed in a block is redundant if an equivalent computation of it, using the same operand values, has already occurred on every path from the entry of the program to that block, with none of its operands redefined in between. If even one incoming path fails this, the expression must be treated as not available, because eliminating it would be unsafe on that path. Step 2: Identify B4's predecessors and the expressions computed on each incoming path. B4 is reached from either B2 or B3. B4 itself computes \(x=g*k\) and \(y=b+i\); check whether \(g*k\) and \(b+i\) are already available on both incoming paths. Step 3: Check availability of \(g*k\) at B4. Path through B2: B2 computes \(a=g*k\), then \(f=d-f\), then \(a=c*4\); neither \(g\) nor \(k\) is redefined anywhere in B2, so \(g*k\) computed in B2 is still valid on arrival at B4. Path through B3: B3 computes \(t=g*k\), then \(b=c+m\); again neither \(g\) nor \(k\) is touched afterwards, so \(g*k\) is valid on arrival at B4 through this path too. Since \(g*k\) is available on both incoming paths to B4, it is a genuine redundant expression at B4. Step 4: Check availability of \(b+i\) at B4. The only earlier computation of \(b+i\) is in B1 (\(a=b+i\)). Path through B2: B2 does not redefine \(b\) or \(i\), so the value of \(b+i\) from B1 is still valid when reaching B4 via B2. Path through B3: B3 contains \(b=c+m\), which redefines \(b\). This means the \(b\) used in the earlier B1 computation of \(b+i\) is no longer the current \(b\) by the time control reaches B4 via B3, so the previously computed \(b+i\) is stale and unusable on this path. Since \(b+i\) is available on the B2 path but not on the B3 path, it fails the every path requirement, so \(b+i\) is not a redundant expression at B4, even though it looks textually identical to the B1 computation. This rules out options (A) and (C). Step 5: Determine B4's full redundant set. Only \(g*k\) survives, so B4's redundant expression set is \(\{g*k\}\), consistent with both remaining options (B) and (D). Step 6: Check availability of \(c+m\) at B5. B5 computes \(z=c+m\). B5's only predecessor is B4, but B4 itself is reached from either B2 or B3, so the relevant paths into B5 are B1 to B2 to B4 to B5, and B1 to B3 to B4 to B5. Path through B3: B3 computes \(b=c+m\), which includes the subexpression \(c+m\); neither \(c\) nor \(m\) is redefined afterwards in B3, B4 or B5 before the \(z=c+m\) statement, so \(c+m\) is available on arrival at B5 via this path. Path through B2: none of B1, B2 or B4 contains any computation of \(c+m\) anywhere; the only occurrence of \(c+m\) in the whole flow graph before B5 is inside B3. So on the path that goes through B2, \(c+m\) has never been computed at all by the time control reaches B5. Step 7: Determine B5's full redundant set. Since \(c+m\) is available on the B3 path but not on the B2 path, it fails the every path requirement at B5 as well, so \(c+m\) is not a redundant expression at B5. B5's redundant expression set is therefore empty, \(\{\}\), which rules out option (B) and matches option (D). Step 8: Conclusion. B4's redundant set is \(\{g*k\}\) and B5's redundant set is \(\{\}\), matching option (D) exactly.\[ \boxed{\text{B4: } \{g*k\}, \ \text{B5: } \{\} \ \text{(Option D)}} \]
