The GATE Grind

GATE 2024 CS (CS1) – Question 39

Compiler Design · Intermediate Code Generation · 2 marks · Multiple choice

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?

  1. 6 and 6
  2. 6 and 7
  3. 7 and 7
  4. 7 and 6

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.

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).

More Intermediate Code Generation questions

All Intermediate Code Generation questions →