Basic Blocks

GATE CS previous year questions · 2 questions

GATE CS 2025 Set 1 | Question 52

NAT · 2 marks

Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is ________. (Answer in integer)

1001: i = 1
1002: j = 1
1003: t1 = 10*i
1004: t2 = t1+j
1005: t3 = 8*t2
1006: t4 = t3-88
1007: a[t4] = 0.0
1008: j = j+1
1009: if j <= 10 goto 1003
1010: i = i+1
1011: if i <= 10 goto 1002
1012: i = 1
1013: t5 = i-1
1014: t6 = 88*t5
1015: a[t6] = 1.0
1016: i = i+1
1017: if i <= 10 goto 1013

Explanation

Answer: 6

A new basic block starts at every leader: the first instruction, every jump target, and every instruction right after a jump.

  • First instruction: 1001.
  • Jump targets: 1003, 1002 and 1013.
  • Instructions after a jump: 1010 (after 1009) and 1012 (after 1011); 1017 is the last line.

The six leaders 1001, 1002, 1003, 1010, 1012 and 1013 give the blocks 1001 | 1002 | 1003–1009 | 1010–1011 | 1012 | 1013–1017.

Answer: 6

GATE CS 2024 Set 1 | Question 39

MCQ · 2 marks · −0.66

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 ?

Options for GATE CS 2024 Set 1 | Question 39

Explanation

Answer: (D)

A leader starts each basic block: the first instruction, every jump target, and every instruction right after a jump.

  • L1 is the first instruction.
  • L11, L4 and L3 are the targets of the jumps in L9, L12 and L14.
  • L10, L13 and L15 each follow a conditional jump.

These 7 leaders give 7 blocks: L1–L2, L3, L4–L9, L10, L11–L12, L13–L14 and L15. The largest is L4–L9, with 6 instructions; it ends at the jump in L9. Missing L3 or L4 as a leader merges two blocks, which leads to the 6-block options A and B.

Answer: D