The Gateway to Computer Science Excellence
+31 votes
5.9k 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. $\text{p, s, u}$
  2. $\text{r, s, u}$
  3. $\text{r, u}$
  4. $\text{q, v}$
in Compiler Design by Boss (29.9k points)
edited by | 5.9k views
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
+5

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

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

ADMIN Please add the tag out-of-syllabus as live variables are in code optimization which is removed from 2016

2 Answers

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

by Veteran (422k points)
edited by
0

@Arjun Sir

 r should be the answer.

Reason should be like this:

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

ii) There is a path from Si to Sj 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 Si and Sj // 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 Si and Sj // 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 Si and Sj 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?

+1
@srestha

read above comments , specially the comment made by @suraj
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
from where to study ths topic, i am not able to understand :(
0

Try here

Try here also Hope U got liveness concept 

0
Thanx a lot. Gonna see it.
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 ??
+3
That path length is 0 from 2-2 and 3-3 and statements 2 and 3 are the uses.
0
@Arjun  sir Thanks

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

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

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

  1. There exists a statement Sj that uses x

But r is  not used in 3rd block ,?

+1

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

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

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

Is it still in Syllabus(control flow graphs)???
+15 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).

by Boss (27.2k points)
0
then according to this explanation
s is live in 2 too
rt?
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

+2
@Ayush this is a nice explanation thanks a lot
+1

@

Is control flow graph in syllabus Gate 2019?

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

this link works fine

 

Answer:

Related questions

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
50,654 questions
56,169 answers
193,878 comments
94,301 users