GATE CS 2024 Set 1 — Question 39

MCQ+2 / -0.67MediumBasic Blocks & Flow GraphsCode OptimizationCompiler Design

Compiler Design → Code Optimization → Basic Blocks & Flow Graphs

Last updated 20 August 2026

Question

Consider the following pseudo-code.

L1:   t1 = -1
L2:   t2 = 0
L3:   t3 = 0
L4:   t4 = 4 * t3
L5:   t5 = 4 * t2
L6:   t6 = t5 * M
L7:   t7 = t4 + t6
L8:   t8 = a[t7]
L9:   if t8 &lt;= max goto L11
L10:  t1 = t8
L11:  t3 = t3 + 1
L12:  if t3 &lt; M goto L4
L13:  t2 = t2 + 1
L14:  if t2 &lt; N goto L3
L15:  max = t1

Which one of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively ?

6 and 6

6 and 7

7 and 7

7 and 6

Correct answer

(D) 7 and 6

Solution

To find the number of basic blocks, we first identify the leaders in the code:

1.The first instruction is a leader: L1.

2.Any instruction that is the target of a conditional or unconditional jump is a leader: L3 (target of L14), L4 (target of L12), and L11 (target of L9).

3.Any instruction that immediately follows a conditional or unconditional jump is a leader: L10 (follows L9), L13 (follows L12), and L15 (follows L14).

The set of leaders is

\{L1, L3, L4, L10, L11, L13, L15\}

Now, we form the basic blocks starting from each leader until the next leader or the end of the program:

Block 1: $\{L1, L2\}$ (2 instructions)
Block 2: $\{L3\}$ (1 instruction)
Block 3: $\{L4, L5, L6, L7, L8, L9\}$ (6 instructions)
Block 4: $\{L10\}$ (1 instruction)
Block 5: $\{L11, L12\}$ (2 instructions)
Block 6: $\{L13, L14\}$ (2 instructions)
Block 7: $\{L15\}$ (1 instruction)

Total number of basic blocks = 7.
The largest basic block is Block 3, which contains 6 instructions.
Therefore, the correct option is (D).

GATE CS 2024 Set 1 — Question 39

Question

Correct answer

Solution

More questions on Code Optimization