Register

GATE CSE 2015 Set 1 | Question: 50

• retagged by
26,680 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
User Avatar

2 Answers

Best answer
46 votes
46 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
User Avatar
35 votes
35 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).

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

29.8k
views
7 answers
80 votes
makhdoom ghaya asked Feb 13, 2015
29,800 views
GATE CSE 2015 Set 1 | Question: 55
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__________________.
User Avatar
19.5k
views
2 answers
53 votes
makhdoom ghaya asked Feb 12, 2015
19,453 views
GATE CSE 2015 Set 1 | Question: 1‏3
Which one of the following is TRUE at any valid state in shift-reduce parsing?Viable prefixes appear only at the bottom of the stack and not ... insideThe stack contains only a set of viable prefixesThe stack never contains viable prefixes
User Avatar
19.2k
views
4 answers
54 votes
makhdoom ghaya asked Feb 12, 2015
19,193 views
GATE CSE 2015 Set 1 | Question: 8
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 ... or $S3$Only $S2$ and $S3$All of $S1$, $S2$ and $S3$
User Avatar
7.0k
views
4 answers
13 votes
Arjun asked Feb 18, 2021
7,013 views
GATE CSE 2021 Set 2 | Question: 38
For a statement $S$ in a program, in the context of liveness analysis, the following sets are defined:$\text{USE}(S)$ : the set of variables used in $S$ ... $)} = \text{USE ($S_1$)} \cup \text{IN ($S_2$)}$
User Avatar
Link Copied!