GATE CSE
First time here? Checkout the FAQ!
x
+7 votes
2.1k 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 (38.7k points)   | 2.1k 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 .

1 Answer

+7 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 (294k points)  
edited by
@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 .



Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2076 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,649 answers
79,695 comments
31,069 users