GATE CS 2015 Set 2 Q.39 (CS Q.29): Intermediate Code Generation, Data Flow Analysis and Code Optimization

Consider the intermediate code given below.

(1)  i = 1
(2)  j = 1
(3)  t1 = 5 * i
(4)  t2 = t1 + j
(5)  t3 = 4 * t2
(6)  t4 = t3
(7)  a[t4] = -1
(8)  j = j + 1
(9)  if j<=5 goto (3)
(10) i = i + 1
(11) if i<5 goto (2)

The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are

5 and 7

6 and 7

5 and 5

7 and 8

Official answer and solution

Official answer: B
From: Official GATE 2015 answer key

Solution

Identify the basic block leaders to construct the control-flow graph (CFG), and include standard entry/exit nodes.

The three standard rules for identifying leaders:

Instruction (1) is the first instruction $\implies$ Leader.
Any target of a conditional or unconditional goto is a leader:
- Target of goto (3) at line 9 is instruction (3) $\implies$ Leader.
- Target of goto (2) at line 11 is instruction (2) $\implies$ Leader.
Any instruction immediately following a conditional or unconditional goto is a leader:
- Instruction (10) follows line 9 $\implies$ Leader.

The leaders are instructions (1), (2), (3), and (10), partitioning the code into 4 basic blocks:

$B_1$ : { (1) }
$B_2$ : { (2) }
$B_3$ : { (3), (4), (5), (6), (7), (8), (9) }
$B_4$ : { (10), (11) }

In standard compiler textbooks (Aho, Lam, Sethi, Ullman), the CFG contains explicit Entry and Exit nodes:

\text{Total nodes} = 4\text{ (basic blocks)} + 2\text{ (Entry, Exit)} = 6\text{ nodes}.

Constructing the directed edges:

$\text{Entry} \rightarrow B_1$
$B_1 \rightarrow B_2$ (fall-through)
$B_2 \rightarrow B_3$ (fall-through)
$B_3 \rightarrow B_3$ (loop back on $j \le 5$ )
$B_3 \rightarrow B_4$ (fall-through when $j > 5$ )
$B_4 \rightarrow B_2$ (loop back on $i < 5$ )
$B_4 \rightarrow \text{Exit}$ (fall-through when $i \ge 5$ )

Total edges = 7 edges. Thus, there are 6 nodes and 7 edges (option B).

Final answer

Common trap

Omitting the Entry and Exit nodes, which would give 4 nodes instead of 6.

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 2
Question: 39 of 65, printed as CS Q.29
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