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

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

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.

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