GATE CS 2015 Set 1 Q.60 (CS Q.50): Intermediate Code Generation, Data Flow Analysis and Code Optimization

A variable $x$ is said to be live at a statement $S_i$ in a program if the following three conditions hold simultaneously:
i. There exists a statement $S_j$ that uses $x$
ii. There is a path from $S_i$ to $S_j$ in the flow graph corresponding to the program
iii. The path has no intervening assignment to $x$ including at $S_i$ and $S_j$

Control flow graph with four basic blocks: block 1 branches to blocks 2 and 3, both converge to block 4, which loops back to block 1 — Control flow graph of basic blocks

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

$p, s, u$

$r, s, u$

$r, u$

$q, v$

Official answer and solution

Official answer: C
From: Official GATE 2015 answer key

Solution

Trace variable uses and definitions downstream from basic blocks 2 and 3 using the given definition of live variables.

Definition of live variable at statement $S_i$ :
- A variable $x$ must be used downstream at some $S_j$ .
- There must exist a path from $S_i$ to $S_j$ without any intervening assignment to $x$ (including at $S_i$ and $S_j$ ).
Check definitions at blocks 2 and 3:
- Basic block 2 assigns $v$ : v = r + u. By condition (iii), $v$ is assigned at this statement, so $v$ is NOT live at block 2.
- Basic block 3 assigns $q$ : q = s * u. By condition (iii), $q$ is assigned at this statement, so $q$ is NOT live at block 3.
  Hence, neither $v$ nor $q$ can be live at both blocks.
Check variable $u$ :
- In block 2, v = r + u uses $u$ . Is $u$ live before this use? The question asks about variables live at the statement in block 2 and block 3. At block 2, $u$ is read on the right-hand side, defined in block 1 with no intervening assignment. Similarly, at block 3, q = s * u reads $u$ . Hence, $u$ is live at both statements.
Check variable $r$ :
- Variable $r$ is read in block 2 (v = r + u).
- From block 3, control flows to block 4 (q = v + r), which reads $r$ . Since $r$ is never assigned anywhere in blocks 1, 2, 3, or 4, $r$ reaches its use in block 4 without any intervening definition.
  Hence, $r$ is live at both statements.
Check variable $s$ :
- In block 3, q = s * u uses $s$ .
- However, from block 2, control flows through block 4 to block 1, where $s$ is redefined (s = p + q) before any subsequent use of $s$ . Therefore, $s$ is NOT live at block 2.

Thus, the variables that are live both at the statement in block 2 and block 3 are $r$ and $u$ (option C).

Final answer

Common trap

Including variable s, which is overwritten in block 1 before any subsequent use along the path from block 2.

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

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 1
Question: 60 of 65, printed as CS Q.50
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