GATE CS 2021 Set 2 Q.48 (CS Q.38): Intermediate Code Generation, Data Flow Analysis and Code Optimization

For a statement $S$ in a program, in the context of liveness analysis, the following sets are defined:

\text{USE}(S) : \text{the set of variables used in } S

\text{IN}(S) : \text{the set of variables that are live at the entry of } S

\text{OUT}(S) : \text{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?

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

$\text{OUT}(S_1) = \text{IN}(S_1) \cup \text{USE}(S_1)$

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

$\text{OUT}(S_1) = \text{USE}(S_1) \cup \text{IN}(S_2)$

Official answer and solution

Official answer: A
From: Official GATE 2021 answer key

Solution

Recall the fundamental dataflow equations for backward liveness analysis within a sequential basic block.

In compiler liveness analysis, analysis is performed in the backward direction:

A variable is live at a point $p$ if there is an execution path from $p$ along which its value is used before being redefined.

Within a basic block consisting of statement $S_1$ followed immediately by statement $S_2$ , execution proceeds unconditionally and sequentially from $S_1$ to $S_2$ . There are no intervening statements or branch points between the exit of $S_1$ and the entry of $S_2$ .

Consequently, a variable is live immediately after executing $S_1$ (at the exit of $S_1$ ) if and only if it is live immediately before executing $S_2$ (at the entry of $S_2$ ):

\text{OUT}(S_1) = \text{IN}(S_2)

This matches option A.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 48 of 65, printed as CS Q.38
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source