retagged by
6,680 views
12 votes
12 votes

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{IN}(S)$ : the set of variables that are live at the entry of $S$

$\text{OUT}(S)$ : the set of variables that are live at the exit of $S$

Consider a basic block that consists of two statements, $S_1$ followed by $S_2$. Which one of the following statements is correct?

  1. $\text{OUT($S_1$)} = \text{IN ($S_2$)}$
  2. $\text{OUT ($S_1$)} = \text{IN ($S_1$)} \cup \text{ USE ($S_1$)}$
  3. $\text{OUT ($S_1$)} = \text{IN ($S_2$) }\cup \text{ OUT ($S_2$)}$
  4. $\text{OUT ($S_1$)} = \text{USE ($S_1$)} \cup \text{IN ($S_2$)}$
retagged by

4 Answers

Best answer
13 votes
13 votes

When a basic block $S_2$ immediately follows another basic block $S_1,$ all variables that are live at exit of $S_1$ must be live at entry of $S_2$ (no intermediate place where they can get killed) and no other variable can be live at entry of $S_2$ as a basic block is always single entry and single exit.

So, $\text{OUT($S_1$)} = \text{IN ($S_2$)}$

Correct option: A

Liveness Analysis Slides

0 votes
0 votes
IN(S1) -->USE(S1) -->OUT(S1) /IN(S2) -->USE(S2) -->OUT(S1)

Here you can clearly see OUT(S1) = IN(S2)

Ans: A
Answer:

Related questions

8 votes
8 votes
1 answer
3
Arjun asked Feb 18, 2021
6,468 views
Consider the following augmented grammar with $\{ \#, @, <, >, a, b, c \}$ as the set of terminals. $$\begin{array}{l} S’ \rightarrow S \\ S \rightarrow S \# cS \\ S \r...