Skip to content
GATETECH
Official PYQ · 2015Set 2 · Q29Intermediate Code GenerationMCQ1 mark

GATE CS 2015 Set 2 Q29 — Intermediate Code Generation

Explain with AI

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 control-flow-graph constructed for the above code, respectively, are

Choose one option
View worked solution

Answer: B

To construct the Control Flow Graph (CFG), we first identify the leaders (the first instructions of the basic blocks):

  1. Rule 1: The first instruction is a leader.
      ⟹  \implies Line (1) is a leader.
  2. Rule 2: Any instruction that is the target of a conditional or unconditional jump is a leader.
      ⟹  \implies Line (2) (target of goto (2) at line 11) and Line (3) (target of goto (3) at line 9) are leaders.
  3. Rule 3: Any instruction immediately following a conditional or unconditional jump is a leader.
      ⟹  \implies Line (10) (following the jump at line 9) is a leader.

Using these leaders, we partition the code into 4 basic blocks:

  • B1B_1: Line (1)
  • B2B_2: Line (2)
  • B3B_3: Lines (3) to (9)
  • B4B_4: Lines (10) to (11)

Standard CFG construction includes an Entry and an Exit node. Thus, the total number of nodes is:

Nodes={Entry,B1,B2,B3,B4,Exit}  ⟹  6 nodes\text{Nodes} = \{\text{Entry}, B_1, B_2, B_3, B_4, \text{Exit}\} \implies 6 \text{ nodes}

The control flow edges are:

  1. Entry→B1\text{Entry} \to B_1
  2. B1→B2B_1 \to B_2
  3. B2→B3B_2 \to B_3
  4. B3→B3B_3 \to B_3 (loop back when j <= 5)
  5. B3→B4B_3 \to B_4 (fall through when j > 5)
  6. B4→B2B_4 \to B_2 (loop back when i < 5)
  7. B4→ExitB_4 \to \text{Exit} (fall through when i >= 5)

This gives a total of 7 edges.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Intermediate Code Generation questions