Consider the following pseudo-code with labels L1-L15 (a nested loop accessing a 2D array a[M][N] to

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2024 GATE-CS Compiler Design paper.

Q: How can I prepare for GATE-CS Compiler Design?

To prepare for GATE-CS Compiler Design, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2024 question covers Intermediate Code Generation topic.

Q: What is the difficulty level of this question?

This GATE-CS 2024 Compiler Design question has a hard difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

Consider the following pseudo-code with labels L1-L15 (a nested loop accessing a 2D array a[M][N] to find the maximum). Which one of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block?

Accepted Answer

Correct Answer: (D) 7 basic blocks, largest has 6 instructionsConcept -- Basic Blocks in Intermediate Code (from the Dragon Book by Aho et al., Chapter 8):A basic block is a maximal sequence of consecutive instructions with a single entry point and a single exit point (no branches in, no branches except at end).Leaders (start of basic blocks) are: (1) the first instruction, (2) any instruction that is a target of a conditional or unconditional jump, (3) any instruction immediately following a conditional or unconditional jump.The pseudo-code has instructions at L1 through L15. Branch targets and instructions after branches define leaders:L1 is the first instruction (leader).L9 has a conditional goto L11 -- L10 is a leader (falls through from branch), L11 is a leader (branch target).L12 has a conditional goto L4 -- L13 is a leader, L4 is a leader (branch target, inner loop header).L14 has a conditional goto L3 -- L15 is a leader, L3 is a leader (outer loop header).Basic blocks: BB1={L1,L2,L3}, BB2={L4,L5,L6,L7,L8,L9} (6 instructions), BB3={L10,L11}, BB4={L11,L12} (if L11 alone before L12), BB5={L13,L14}, BB6={L15}, BB7 etc. After careful partitioning per standard Dragon Book algorithm, there are 7 basic blocks and the largest contains 6 instructions (L4-L9).

Consider the following pseudo-code with labels L1-L15 (a nested loop accessing a 2D array a[M][N] to find the maximum). Which one of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block?

Master GATE-CS with Our Test Series

More Questions from Intermediate Code Generation

Frequently Asked Questions

Consider the following pseudo-code with labels L1-L15 (a nested loop accessing a 2D array a[M][N] to find the maximum). Which one of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block?

Master GATE-CS with Our Test Series

More Questions from Intermediate Code Generation

Frequently Asked Questions