42 votes

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

- There exists a statement $S_{j}$ that uses $x$
- There is a path from $S_{i}$ to $S_{j}$ in the flow graph corresponding to the program
- 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

- $\text{p, s, u}$
- $\text{r, s, u}$
- $\text{r, u}$
- $\text{q, v}$

0

@Arjun sir how u is not live in block 2 and 3 according to rule : a variable is live after statement s if its successor block is using its value thus variable u will not be dead in block 2 and 3.sir kindly explain this plz

7

'u' is live in 2 and 3 but not in 1...but question is asking only for 2 and 3 , in 2 and 3 statements S_{i} and S_{j }are same .

See the question " 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 "

that's why we need to consider r and u both .

0

r is surely liveby definition,and I think u is live if we interchange statement 2 and 3 in basic block 1 .

32 votes

Best answer

**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.

0

See I have seen it from here https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/courseware/8168ef6c0e2e4003a88d8766c9182a35/89590470e23d458fac620018c63b8f47/

Here clearly mentioned, if there is any write operation then there shouldnot be any liveness. So, it eliminates u.

rt?

0

where is u assigned in the intervening path?? In the path of length zero from block 2 to block 2 where is u assigned, so it should be u and r right???

0

@Bikram sir

liveness for u : at statement2 : 2->4->1 (violation of condition 3 because in statement1 u has been assigned a value)

liveness for u : at statement3 : 3->4->1 (violation of condition 3 because in statement1 u has been assigned a value)

so u is not live at statement2 and 3 so how is the answer containing u ??

liveness for u : at statement2 : 2->4->1 (violation of condition 3 because in statement1 u has been assigned a value)

liveness for u : at statement3 : 3->4->1 (violation of condition 3 because in statement1 u has been assigned a value)

so u is not live at statement2 and 3 so how is the answer containing u ??

0

@Arjun sir Thanks

In these type of questions do we have to consider a 0 length path also for a statement every time ?

In these type of questions do we have to consider a 0 length path also for a statement every time ?

2

Yes @ gari

see the above explanation..

v is live at statement 3 .

r is live at statement 2 and 3 both .

u is live at statement 2 and 3 .

so answer must contain r and u .

0

@Bikram sir Live Variable is under code optimization, So this is not in syllabus if it is in syllabus.

**Please share reference link this topic if you have any.**

0

Why r is a live variable?

1st condition says:-

- There exists a statement Sj that uses x

But r is not used in 3rd block ,?

0

rahul sharma 5 r is live variable

See the question . X is live at Si and used in Sj.

r is used in B1: path is from 4 to 1. here **si = 4 **and **sj=1 **so its live at** 4.**

r is used in B2: path from 1 to 2 . here **si = 1 **and **sj=2 **so its live at** 1.**

r is used in B4: path from 3 to 4 . here **si = 3 **and **sj=4 **so its live at** 3.**

path from 2 to 4 . here **si = 2 **and **sj=4 **so its live at** 2.**

hope it helps:)

1

@Arjun sir, here we are considering $0$ path length for liveness..But in register allocation scheme while using inference graph then we dont consider $0$ path length otherwise we may compute more than required number of registers.

1

If anyone is using the Stanford compiler notes here: https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/15/Slides15.pdf, is the way that the question is asking us to analyse liveness (with the 3 conditions given) different from how Stanford does it? (see example of liveness calculation with loops in CFG in the PDF above, page 82 onwards).

Edit: ok I see where I went wrong, I was not calculating liveness per statement. It has to be done per statement. The backward analysis in the Stanford notes works just fine.

0

After going through this link as suggested by @Prashant and reading Live Variable Analysis from Ullman, I have concluded that liveness analysis flows backwards and started from the last basic block and for every basic block i, In[i], Out[i], Gen[i] and Kill[i] need to be calculated. I understand that for last basic block of a program, Out = ϕ as no variable is live after that. But in this question, what should be the content of Out[4]. It can't be ϕ because 1 follows 4. So, what should be the content of Out[4] and where should the analysis be started.

0

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

28 votes

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).**

0

No S cant be live in 2 since after getting the value of s ,we are not using or reading it elsewhere in block 2.s is live in block 3 as we are reading the value of s.

0

@Ayush Upadhyaya why v is not live before start of block 1 .According to me , variables {q,r,v} are read and they are live before start of block 1