The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
2.4k views

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

  1. p, s, u
  2. r, s, u
  3. r, u
  4. q, v
asked in Compiler Design by Veteran (42.8k points) | 2.4k views
@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

'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 Si and Sare 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 .

2 Answers

+11 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.
answered by Veteran (327k points)
edited by
Thanx a lot. Gonna see it.
@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 ??
That path length is 0 from 2-2 and 3-3 and statements 2 and 3 are the uses.
@Arjun  sir Thanks

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

If we consider zero length paths, then variable 's' is live at the statement in block 3. Right?

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 .

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

Why r is a live variable?

1st condition says:- 

  1. There exists a statement Sj that uses x

But r is  not used in 3rd block ,?

 अनुराग पाण्डेय But u is being assigned a value at 1.3. So how it is live?

 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 vote

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

 

answered by Loyal (3.5k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,115 questions
36,926 answers
91,928 comments
34,782 users