Consider the following pseudo-code.
L 1: t1 = -1 L 2: t2 = 0 L 3: t3 = 0 L 4: t4 = 4 * t3 L 5: t5 = 4 * t2 L 6: t6 = t5 * M L 7: t7 = t4 + t6 L 8: t8 = a[t7] L 9: if t8 <= max goto L11 L 10: t1 = t8 L 11: t3 = t3 + 1 L 12: if t3 < M goto L4 L 13: t2 = t2 + 1 L 14: if t2 < N goto L3 L 15: 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?
View worked solution
Answer: D
To find the basic blocks, we first identify the leaders using the standard compiler design rules:
- The first instruction (L1) is a leader.
- Any instruction that is the target of a conditional or unconditional jump is a leader. Here, these are:
- L3 (target of
goto L3in L14) - L4 (target of
goto L4in L12) - L11 (target of
goto L11in L9)
- L3 (target of
- Any instruction that immediately follows a conditional or unconditional jump is a leader. Here, these are:
- L10 (follows
goto L11in L9) - L13 (follows
goto L4in L12) - L15 (follows
goto L3in L14)
- L10 (follows
Thus, the leaders are: L1, L3, L4, L10, L11, L13, and L15. Since there are 7 leaders, there are exactly 7 basic blocks.
Now, we partition the instructions into basic blocks starting at each leader up to (but not including) the next leader:
- Block 1 (starts at L1): L1, L2 (2 instructions)
- Block 2 (starts at L3): L3 (1 instruction)
- Block 3 (starts at L4): L4, L5, L6, L7, L8, L9 (6 instructions)
- Block 4 (starts at L10): L10 (1 instruction)
- Block 5 (starts at L11): L11, L12 (2 instructions)
- Block 6 (starts at L13): L13, L14 (2 instructions)
- Block 7 (starts at L15): L15 (1 instruction)
The largest basic block is Block 3, which contains 6 instructions.
Therefore, the number of basic blocks is 7 and the number of instructions in the largest basic block is 6.
Free practice · Your answers on this page are not saved.