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 = t1Which one of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively ?
Answer
(D)
Explanation
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