GATE 2015 CS – Question 46
A variable $x$ is said to be live at a statement $S_i$ in a program if the following three conditions hold simultaneously:
i. There exists a statement $S_j$ that uses $x$
ii. There is a path from $S_i$ to $S_j$ in the flow graph corresponding to the program
iii. The path has no intervening assignment to $x$ including at $S_i$ and $S_j$
[Control flow graph: block 1 has `p = q + r`, `s = p + q`, `u = s * v`. Block 1 goes to block 2 (`v = r + u`) and to block 3 (`q = s * u`). Blocks 2 and 3 both go to block 4 (`q = v + r`), and block 4 goes back to block 1.]
The variables which are live both at the statement in basic block 2 and at the statement in basic block 3 of the above control flow graph are
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) $r, u$
Explanation
The statement in block 2 uses $r$ and $u$, and it assigns $v$. The statement in block 3 uses $s$ and $u$. Variable $u$ is used in both blocks, so it is live at both. Variable $r$ is used in block 2, and from block 3 the path to block 4 reaches a use of $r$ with no assignment to $r$ anywhere, so $r$ is live at both. Variable $s$ is not live at block 2, because the only path from block 2 goes through blocks 4 and 1, where $s$ is reassigned before any use. Variable $v$ is assigned in block 2 itself, and $q$ and $p$ are reassigned before being used, so none of them are live at both.