GATE CSE 2015 Set 1 | Question: 50

Question

A variable $x$ is said to be live at a statement $s_{i}$ in a program if the following three conditions hold simultaneously:

1. There exists a statement $S_{j}$ that uses $x$
2. There is a path from $S_{i}$ to $S_{j}$ in the flow graph corresponding to the program
3. 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. $\text{p, s, u}$
• B. $\text{r, s, u}$
• C. $\text{r, u}$
• D. $\text{q, v}$

Comments

This falls under Liveness Analysis Part right?

Which was newly added.

---

YES

---

good read ...

https://youtu.be/IHYZnrsVovE

 

 

Answer 1

r, u.

p, and s are assigned to in $1$ and there is no intermediate use of them before that. Hence p, and s are not live in both $2$ and $3$.
q is assigned to in 4 and hence is not live in both $2$ and $3$.

v is live at $3$ but not at $2$.

u is live at $3$ and also at $2$ if we consider a path of length $0$ from $2 - 2$.

So, r, u is the answer.

Comments

If we consider “u” to be live in block 2, then we would need to store it in register(this is useless thing to do) during register allocation. Actually, there is no need to store “u” in register bcz we aren’t going to use this value of “u”. Considering path of length 0 is just for justifying the answer provided

---

 Arjun sir, Deepakk Poonia (Dee) please make some blog/video on these topics, provide some questions with a detailed explanation.

---

Liveness Analysis By Deepak Poonia: https://youtu.be/rEFJvITxAM0

Answer 2

Variables {q and r} are live at the entry point of block 1. P is dead because p is overwritten at the first statement and the statement 2 of block 1 uses this new value.And from line 2 of block 1, P is never used. So, p is dead.

Similar is the case for variable S, which is overwritten at line 2 and read at line 3 in block 1. So, S is dead the entry point of Block1.

U is never read in block 1, so U is dead before Block 1.

Before Block 2, variables R and U are being read so they are live at the entry point as well in the assignment line of block 2.

Similarly, In block 3, variables S and U are live at the entry point of block 3.

Now, if we talk about block 4, at the entry point of block 4, variables V and R are live.

Talking about block 3, at the exit point variables V and R are live.

The rule of liveliness states that if a block B does not use a variable V which is live after it's exit point, then this variable V is live also before the entry point of Block B.

Reference: https://www.youtube.com/watch?v=mPNZAUa54hs&list=PLFB9EC7B8FE963EB8&index=81

Since Variables  V and R are live after Block B3, so they must be live before block B3.(V is not shown in the figure).

So, at entry point of below Blocks 

B2-R and U are live

B3 - R , S ,U and V are live.

which is common between B2 and B3- R and U. (Ans).

Comments

"v" is live in entry of Block 1 and also in entry of Block 3. Correct me if I'm wrong. :)

---

v is not live in block1 see the third condition. The path has no intervening assignment to x including at Si and Sj.  v used in block 2 after block 1. But in block 2 v has an assignment. so, v is dead.

correct me, if i am wrong .

---

@ayush Sir, which variables are live at entry point of block 1?