# GATE2015-1-50

11.7k 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}$

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

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

2
again added in gate 2021 syllabus
1
This falls under Liveness Analysis Part right?

0
YES
4

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
0

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

rt?

1
@srestha

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 ?
9

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.

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

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

Is it still in Syllabus(control flow graphs)???
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 @ 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. It can't be ϕ because 1 follows 4. So, what should be the content of Out 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 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).

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

v is not live in block1 see the third condition. The path has no intervening assignment to x including at Si and Sj.  v used in block 2 after block 1. But in block 2 v has an assignment. so, v is dead.

correct me, if i am wrong .

0
@ayush Sir, which variables are live at entry point of block 1?

The following video will help but I don’t know what’s the problem with admin, why he removed this answer of mine. If this video is helpful then what’s the problem. I can’t even type his name here because his name is prohibited here (Don’t know why ?)

## Related questions

1
16.6k views
The least number of temporary variables required to create a three-address code in static single assignment form for the expression $q + r / 3 + s - t * 5 + u * v/w$ is__________________.
For computer based on three-address instruction formats, each address field can be used to specify which of the following: (S1) A memory operand (S2) A processor register (S3) An implied accumulator register Either $S1$ or $S2$ Either $S2$ or $S3$ Only $S2$ and $S3$ All of $S1$, $S2$ and $S3$