GATE 2024 CS (CS1) – Question 39
Consider the pseudo-code with lines 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 option CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) 7 and 6
Explanation
A basic block starts at a **leader**: (i) the first instruction, (ii) any instruction that is the target of a jump, (iii) any instruction immediately after a jump.
- L1: first instruction.
- L3: target of the jump in L14.
- L4: target of the jump in L12.
- L11: target of the jump in L9.
- L10: follows the conditional jump in L9.
- L13: follows the conditional jump in L12.
- L15: follows the conditional jump in L14.
Leaders: L1, L3, L4, L10, L11, L13, L15 give **7** blocks:
$\{L1,L2\},\{L3\},\{L4\text{–}L9\},\{L10\},\{L11,L12\},\{L13,L14\},\{L15\}$.
The largest block is L4–L9 with **6** instructions. Answer: 7 and 6, option (D).