A variable \(x\) is said to be live at a statement \(S_i\) in a program if the…
2015
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\)
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
- A.
\(p, s, u\) - B.
\( r, s, u\) - C.
\(r, u\) - D.
\(q, v\)
Attempted by 71 students.
Show answer & explanation
Correct answer: C
Key insight: a variable is live at a program point if there exists a reachable use along some path that does not pass through any assignment to that variable.
Live just before the statement in basic block 2 (v = r + u):
r and u are live because they are used immediately in that statement; no intervening assignment to r or u occurs before that use.
Live just before the statement in basic block 3 (q = s * u):
u is used immediately in block 3, so u is live. s is also used immediately in block 3, so s is live there. r is live at block 3 because block 4 uses r (q = v + r) and that use is reachable from block 3 without any assignment to r (r is never assigned).
Intersection: r and u are live at both the statement in block 2 and the statement in block 3, so the correct set is {r, u}.
Why other variables fail to be live at both points:
p is not live at block 2 because its only use occurs after its definition in block 1, so there is no path from block 2 to a use of p without an intervening definition.
s is not live at block 2 because any path from block 2 back to a use of s goes through the assignment s = p + q in block 1, which breaks the liveness condition.
v is not live at block 2 because block 2 defines v (a variable is not live at the point where it is redefined), though v is live at block 3.
q is not live at both points because it gets redefined on paths that would otherwise reach its uses.
A video solution is available for this question — log in and enroll to watch it.