GATE CS 2015 Set 1 Q50 — Data Flow Analyses: Constant Propagation, Liveness, CSE

A variable is live at a point in a program if there is a path from that point to a use of the variable along which it is not redefined.

Let us analyze the control flow graph (CFG) and the liveness of variables at the exit of basic blocks 2 and 3:

1. Basic Block 4 ($B_4$):
   • Contains the statement: y = r * u
   • Since both $r$ and $u$ are used here, they must be live at the entry of $B_4$. Thus, $\text{Live-in}(B_4) = \{r, u\}$.
2. Basic Block 2 ($B_2$):
   • Contains:
     s = p + q
r = r + s
   • The control flows from $B_2$ directly to $B_4$. Therefore, the live variables at the exit of $B_2$ are the same as the live-in variables of $B_4$, which are $\{r, u\}$.
3. Basic Block 3 ($B_3$):
   • Contains:
     t = q - r
u = t * v
   • The control flows from $B_3$ directly to $B_4$. Therefore, the live variables at the exit of $B_3$ are also the same as the live-in variables of $B_4$, which are $\{r, u\}$.

Thus, the variables live both at the exit of the statements in basic block 2 and basic block 3 are r and u.