GATE CSE 2021 | Set 2 | Question: 38

Question

For a statement $S$ in a program, in the context of liveness analysis, the following sets are defined:

$\text{USE}(S)$ : the set of variables used in $S$

$\text{IN}(S)$ : the set of variables that are live at the entry of $S$

$\text{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$)}$

Comments

Detailed Video Explanation with Complete Analysis: https://www.youtube.com/watch?v=PPYznWzl44I&t=5891s 

---

Liveness Analysis - All in One - Complete Lecture: https://youtu.be/TNvLmincMyM?si=G02FQTGY4yiDBu3c

---

All questions related to Live variable analysis:

Compiler Design: GATE CSE 2015 Set 1 | Question: 50

Compiler Design: GATE CSE 2021 Set 2 | Question: 38

Compiler Design: GATE CSE 2023 | Question: 27

Compiler Design: GATE CSE 2026 | Set 2 | Question: 35

---

Two properties :

1. OUT(B) = ⋃ IN(successors)
    
2. IN(B) = USE(B) ∪ (OUT(B) − DEF(B))

 

So question is formed using 1st property, 

OUT(S1) = ⋃ IN(successor) = IN(S2) 

Answer 1

Given:

Let’s assume the following two statements:

• S1: a = b + c + d

• S2: z = b + c + m

Note: Since S1 is followed directly by S2 with nothing in between, OUT(S1) = IN(S2) by definition of basic blocks in liveness analysis.

Also, OUT(S1) and OUT(S2) can be any subset of variables used in S1 or S2, respectively, depending on what variables are live after those statements. That’s why we are free to assume reasonable values for them during elimination.

Now, we evaluate each option:

---

Option B: OUT(S1) = IN(S1) ∪ USE(S1)

LHS = OUT(S1)
Assume OUT(S1) = {b} (as explained above)

RHS = IN(S1) ∪ USE(S1)
IN(S1) = {b} (assumed)
USE(S1) = {b, c, d}
RHS = {b} ∪ {b, c, d} = {b, c, d}

LHS = {b}
RHS = {b, c, d}
LHS ≠ RHS → Incorrect

---

Option C: OUT(S1) = IN(S2) ∪ OUT(S2)

LHS = OUT(S1)
Assume OUT(S1) = {b, d}

RHS = IN(S2) ∪ OUT(S2)
IN(S2) = {b, d} (from previous logic)
OUT(S2) = {b, c, m} (assumed live variables)
RHS = {b, d} ∪ {b, c, m} = {b, c, d, m}

LHS = {b, d}
RHS = {b, c, d, m}
LHS ≠ RHS → Incorrect

---

Option D: OUT(S1) = USE(S1) ∪ IN(S2)

LHS = OUT(S1)
Assume OUT(S1) = {d}

RHS = USE(S1) ∪ IN(S2)
USE(S1) = {b, c, d}
IN(S2) = {d}
RHS = {b, c, d} ∪ {d} = {b, c, d}

LHS = {d}
RHS = {b, c, d}
LHS ≠ RHS → Incorrect

---

Option A: OUT(S1) = IN(S2)

LHS = OUT(S1)
RHS = IN(S2)
Since S1 is immediately followed by S2, we know OUT(S1) = IN(S2) directly

LHS = RHS → Correct Answer

Answer 2

When a statement $S_2$ immediately follows another statement $S_1,$ in a basic block, all variables that are live at exit of $S_1$ must be live at entry of $S_2$ (no intermediate place where they can get killed) and no other variable can be live at entry of $S_2$ as a basic block is always single entry and single exit.

So, $\text{OUT($S_1$)} = \text{IN ($S_2$)}$

Correct option: A

Liveness Analysis Slides

Comments

Yes @raja11sep it's backward analysis. But between out of S1 and out of S2 there might be chance that some variable die as they would have been required only till S2 block, so how union of both will be present at entry of S3. :( .Please check @adad20.

---

@ankit3009

S1→ S2→ S3 ,we will start calculating live variable from S3 (not S1) and then will go to S2 then S1. When we will go from S3 to S2 some variable may die and also some new variable may appear. So such conclusion(like union) not possible (because it may or may not true).

But we can say OUT(S1)=IN(S2) , OUT(S2)=IN(S3). these are always true.

If you want to compare IN(S2) and OUT(S2) it depends on KILL and GEN set. If both KILL and GEN set phi then IN(S2) = OUT(S2).

Please..Correct me if Im wrong.

---

@Arjun in go pdf this question has been mentioned inside the vector space of linear algebra section also...plz remove that sir

Answer 3

IN(S1) -->USE(S1) -->OUT(S1) /IN(S2) -->USE(S2) -->OUT(S1)

Here you can clearly see OUT(S1) = IN(S2)

Ans: A

Comments

Last one is OUT(S2)..I think

---

what are all formulas for IN AND OUT

Answer 4

Only A is correct.

Reference: See rule 1 on page 7.