Project ForgeA variable x is said to be live at a statement Sᵢ in a program if the following three conditions hold simultaneously: (i) there exists a statement Sⱼ that uses x; (ii) there is a path from Sᵢ to Sⱼ in the flow graph; (iii) the path has no intervening assignment to x, including at Sᵢ and Sⱼ.
Control flow graph: Block 1 {p=q+r; s=p+q; u=s*v} → Block 2 {v=r+u} and Block 3 {q=s*u}, both → Block 4 {q=v+r} → (back edge) → Block 1.
The variables which are live both at the statement in basic block 2 and at the statement in basic block 3 are
- Ap, s, u
- Br, s, u
- r, u
- Dq, v
Explanation
Block 2's statement v=r+u USES r and u, both live entering block 2 with no prior assignment on the path from Block 1's assignments. Block 3's statement q=s*u uses s and u. The variables live at BOTH block 2's statement and block 3's statement (i.e. live at the shared point right after Block 1, before the branch) are exactly the ones used by EITHER successor without being killed first: r (used in block2) and u (used in both) qualify at both program points since backward liveness propagates uses upward through Block 1 for r,u (s is defined in Block1 itself so it's not live INTO block 2, only into block 3's use point after being defined) — the intersection that holds at both split points is {r, u}.
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.