GATE CS 2024 Set 1 Q.39: Intermediate Code Generation, Data Flow Analysis and Code Optimization

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 <= max goto L11
L10: t1 = t8
L11: t3 = t3 + 1
L12: if t3 < M goto L4
L13: t2 = t2 + 1
L14: if t2 < 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

Official answer and solution

Official answer: D
From: Official GATE 2024 answer key

Solution

Identify all leader instructions (the first instruction, targets of jumps, and instructions immediately following jumps) to partition the code into basic blocks.

By the standard basic-block partitioning algorithm, an instruction is a leader if it is:

The first instruction (L1),
The target of a conditional or unconditional jump (L3 from L14, L4 from L12, L11 from L9), or
Immediately following a conditional or unconditional jump (L10 after L9, L13 after L12, L15 after L14).

This gives 7 leaders (L1, L3, L4, L10, L11, L13, L15) and therefore 7 basic blocks:

$B_1$ : L1..L2 ( $2$ instructions)
$B_2$ : L3 ( $1$ instruction)
$B_3$ : L4..L9 ( $6$ instructions)
$B_4$ : L10 ( $1$ instruction)
$B_5$ : L11..L12 ( $2$ instructions)
$B_6$ : L13..L14 ( $2$ instructions)
$B_7$ : L15 ( $1$ instruction)

Thus, there are 7 basic blocks and the largest basic block ( $B_3$ ) contains 6 instructions.

Final answer

Option (D)

Common trap

Forgetting that L3 is the target of goto L3 at L14, which would merge L1..L3 into one block and give 6 basic blocks.

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

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 1 (CS1)
Question: 39 of 65
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