GATE 2025 CS1 Q.52: solution and answer

GATE 2025 · CS1Q.52 · 2 marks · NAT

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

GATE 2025 CS1 question 52: A 17-line three-address code listing, numbered 1001 to 1017, given in the stem as a fenced block exactly as printed. — Figure from the GATE 2025 CS1 paper. It is part of the question.

Answer and solution

ANSWER

The code splits into 6 basic blocks.

Official answer: 6Source: Official answer key, GATE 2025 CS1 (IIT Roorkee)

A basic block is a maximal straight-line sequence of statements, entered only at its first statement and left only at its last. To split the code, find the leaders (the first statement of each block).
Rule 1: the first statement of the code is a leader, so 1001 is a leader.
Rule 2: the target of any jump is a leader. The jumps are 1009 to 1003, 1011 to 1002 and 1017 to 1013, so 1003, 1002 and 1013 are leaders.
Rule 3: the statement right after a jump is a leader. The statement after 1009 is 1010, and the statement after 1011 is 1012. The jump at 1017 is the last statement, so nothing follows it and it starts no block.
Leaders: ${1001, 1002, 1003, 1010, 1012, 1013}$ . These are six distinct statements.
Each block runs from one leader up to the statement before the next leader: $B_{1}$ = 1001; $B_{2}$ = 1002; $B_{3}$ = 1003 to 1009; $B_{4}$ = 1010 to 1011; $B_{5}$ = 1012; $B_{6}$ = 1013 to 1017.
The number of basic blocks equals the number of leaders, so there are $6$ basic blocks.

KEY IDEA

Find the leaders: the first statement, every jump target, and every statement right after a jump. Each leader starts one basic block, so the number of blocks equals the number of leaders.

WATCH OUT FOR

Forgetting that a jump target in the middle of a loop nest, such as 1002, starts its own block, which merges 1001 and 1002. Another slip is counting only the jump targets and missing the statements after the jumps (1010, 1012).

From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 6 Optimisation questions, with notes

GATE 2025 CS1 Q.52: solution and answer

Answer and solution

More Optimisation questions