retagged by
25,943 views
57 votes
57 votes

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 by

2 Answers

Best answer
45 votes
45 votes

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

Answer:

Related questions

80 votes
80 votes
7 answers
1
makhdoom ghaya asked Feb 13, 2015
28,737 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_...