Question

Consider the control flow graph shown in the figure.

The basic blocks are:
B1: \(a = b + i\)
B2: \(a = g*k\); \(f = d-f\); \(a = c*4\)
B3: \(t = g*k\); \(b = c+m\)
B4: \(x = g*k\); \(y = b+i\)
B5: \(z = c+m\)

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.

• A. B4: { \(b+i\) }
  B5: { \(c+m\) }
• B. B4: { \(g*k\) }
  B5: { \(c+m\) }
• C. B4: { \(g*k\), \(b+i\) }
  B5: { }
• D. B4: { \(g*k\) }
  B5: { }

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.

Answer 1

The Correct Option is D

A different, more mechanical way to solve this is to build an explicit available expressions bit vector for each path through the graph, tracking $g*k$, $b+i$ and $c+m$ block by block, rather than reasoning about each expression's history in prose.

Step 1: List the two paths from entry to B5.
Path 1: B1, B2, B4, B5.
Path 2: B1, B3, B4, B5.

Step 2: Track $g*k$ along Path 1.
After B1: not computed. After B2: B2 computes $a=g*k$, and does not modify $g$ or $k$ afterwards, so $g*k$ becomes available. After B4: $x=g*k$ is redundant here, and $g$, $k$ remain unchanged after B4.

Step 3: Track $g*k$ along Path 2.
After B1: not computed. After B3: B3 computes $t=g*k$, does not touch $g$ or $k$ again, so $g*k$ becomes available. After B4: available, so $x=g*k$ is redundant here too.

Step 4: Combine the two paths for $g*k$ at B4.
Both paths mark $g*k$ available on arrival at B4, so the intersection is also available. $g*k$ is confirmed redundant at B4.

Step 5: Track $b+i$ along both paths.
Path 1: computed in B1, not touched by B2, so available entering B4. Path 2: computed in B1, but B3 executes $b=c+m$, redefining $b$, which kills the availability of $b+i$; so on Path 2, $b+i$ is not available entering B4. Intersection over both paths: not available. $b+i$ is not redundant at B4, confirming Step 4 of the direct reasoning and again eliminating options (A) and (C).

Step 6: Track $c+m$ along both paths, extended to B5.
Path 1: $c+m$ is never computed in B1, B2 or B4, so it stays unavailable all the way to B5.
Path 2: $c+m$ is computed in B3, and $c$, $m$ are not redefined again before the $z=c+m$ statement, so it is available entering B5 on this path.
Intersection over both paths at B5: not available. $c+m$ is not redundant at B5, eliminating option (B) and confirming option (D).

Step 7: Conclusion.
The bit vector intersection over both paths gives exactly $\{g*k\}$ available at B4 and $\{\}$ available at B5, the same result as the direct reasoning.$$ \boxed{\text{B4: } \{g*k\}, \ \text{B5: } \{\} \ \text{(Option D)}} $$