For a statement \(S\) in a program, in the context of liveness analysis, the…
2021
For a statement \(S\) in a program, in the context of liveness analysis, the following sets are defined:
\(USE(S)\) : the set of variables used in \(S\)
\(IN(S)\): the set of variables that are live at the entry of \(S\)
\(OUT(S)\) : the set of variables that are live at the exit of \(S\)
Consider a basic block that consists of two statements, \(S_1\) followed by \(S_2\). Which one of the following statements is correct?
- A.
\(\text{OUT($S_1$)} = \text{IN ($S_2$)}\) - B.
\(\text{OUT ($S_1$)} = \text{IN ($S_1$)} \cup \text{ USE ($S_1$)}\) - C.
\(\text{OUT ($S_1$)} = \text{IN ($S_2$) }\cup \text{ OUT ($S_2$)}\) - D.
\(\text{OUT ($S_1$)} = \text{USE ($S_1$)} \cup \text{IN ($S_2$)}\)
Attempted by 103 students.
Show answer & explanation
Correct answer: A
Answer: OUT(S1) = IN(S2).
Why: In a basic block S1 is immediately followed by S2, so control flows directly from the exit of S1 to the entry of S2. The set of variables live at the exit of S1 is therefore exactly the set of variables live at the entry of S2.
Reminder (general liveness equation): IN(S) = USE(S) ∪ (OUT(S) - DEF(S)).
Apply this to the sequence: since there is no intermediate control flow between S1 and S2, the OUT set of S1 is the same as the IN set of S2, i.e. OUT(S1) = IN(S2).
A video solution is available for this question — log in and enroll to watch it.