IAE Academy

GATE 2024 CS1 Q.39: solution and answer

GATE 2024 · CS1Q.39 · 2 marks · MCQ

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 ?

  1. (A)

    6 and 6

  2. (B)

    6 and 7

  3. (C)

    7 and 7

  4. (D)

    7 and 6

See the question in the paper
GATE 2024 CS1 question 39Tap to open full size

Answer and solution

ANSWER

There are 7 basic blocks, and the largest one (L4 to L9) has 6 instructions: option (D).

Official answer: DSource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

  1. A basic block starts at a leader: the first instruction, any instruction that is the target of a jump, and any instruction that immediately follows a jump (conditional or unconditional).

  2. The first instruction is L1. The jump targets are L11 (from L9), L4 (from L12) and L3 (from L14).

  3. The instructions immediately after a jump are L10 (after L9), L13 (after L12) and L15 (after L14).

  4. The leaders are therefore L1, L3, L4, L10, L11, L13, L15. That is 7 leaders, so there are 7 basic blocks.

  5. Each block runs from its leader up to the instruction before the next leader:

  6. The counts add up to , which matches the 15 instructions, so no instruction is missed or counted twice.

  7. The largest block is (L4 to L9) with 6 instructions. So there are 7 basic blocks and the largest has 6 instructions, which is option (D).

KEY IDEA

Find the leaders (the first instruction, every jump target, every instruction right after a jump). Each basic block runs from one leader up to the instruction before the next leader.

WATCH OUT FOR

Forgetting that L3 is a jump target (from L14) and so starts its own block, separate from L1-L2. That gives 6 blocks and the wrong option. Another slip is to leave out the instruction after a conditional jump, which merges L10 into the block before it and makes the largest block 7.

From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 6 Optimisation questions, with notes

More Optimisation questions