The Gateway to Computer Science Excellence

+37 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

+6

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

+27 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

@Arjun Sir

r should be the answer.

Reason should be like this:

i) There exists a statement S*j* that uses x // here p,q,r,s,u,v all uses a statement.

ii) There is a path from S*i* to S*j* in the flow graph corresponding to the program // means it need to be in atleast length 1 path and that should be read only

iii) The path has no intervening assignment to x including at S*i* and S*j* // means there should not be any write after reading the value// only r is never written after reading

Where am I going wrong?

0

v is live in 3 but not in 2 //correct

u is live in 3 and 2 . but it is not live in 1. And in loop it is going back. It is a writing statement So, how u is live?

The path has no intervening assignment to x including at S*i* and S*j* // that means no write operation.

0

@srestha

Best answer is correct , it is r,u

in the official answer key also you can see it is r,u is given as an answer.

as for you question : u is live in 3 and 2 , yes 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

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:)

+21 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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,252 answers

198,061 comments

104,696 users