GATE CSE 2024 | Set 1 | Question: 29

Question

Consider the following pseudo-code.

$L 1 : t 1 = -1$ 

$L 2: t 2 = 0$ 

$L 3: t 3 = 0$ 

$L 4: t 4 = 4 * t 3$

$L 5: t 5 = 4 * t 2$

$L 6: t 6 = t 5 * M$

$L 7: t 7 = t 4+t 6$

$L 8: t 8 = a[t 7]$

$L 9: \text{if t 8<= max goto L} 11$

$L 10: t 1 = t 8$

$L 11: t 3 = t 3+1$

$L 12: \text{if t 3 < M}   \text{ goto L 4}$

$L 13: t 2 = t 2+1$

$L 14: \text{if t 2<N}  \text{ goto L} 3$

$L 15: max =t 1$

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

• A. $6$ and $6$
• B. $6$ and $7$
• C. $7$ and $7$
• D. $7$ and $6$ 

Answer 1

Basic block: The collection of 3AC statements from the leader to the next leader without including the next leader is known as the basic block. 

Steps to find the basic blocks:

• Identify the leader first. (The first statement of 3AC is the leader.)
• The address of conditional, unconditional goto is the leader. (target location of goto)
• immediate next line of goto is the leader.

Now construct the basic block from leader to line before the next leader.

In the given 3AC $7$ leaders are there: $1,3,4,10,11,13,15$

There are $7$ basic block are there:

1. Block $B_1$: statement $1-2$
2. Block $B_2$: statement $3$
3. Block $B_3$: statement $4-9$
4. Block $B_4$: statement $10$
5. Block $B_5$: statement $11-12$
6. Block $B_6$: statement $13-14$
7. Block $B_7$: statement $15$

So the total number of basic blocks is $7$ and the largest basic block is $B_3$ which contains a total of $6$ instruction.

Correct option is $(D)$

Ref: Basic Block

Comments

Correct option is  d

---