GATE2025_CS1_Q52

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

✅ Final Answer:

The correct answer is 6.

🔹 Short Answer:

To find the number of basic blocks, we first identify the "leaders". A leader is the first instruction of a basic block. The rules for finding leaders are: 1) The first instruction is a leader. 2) Any instruction that is the target of a `goto` is a leader. 3) Any instruction immediately following a `goto` is a leader. Applying these rules, the leaders are at lines 1001, 1002, 1003, 1010, 1012, and 1013. Since there are 6 leaders, there are 6 basic blocks.

🔸 Long Answer:

A basic block is a sequence of consecutive instructions in which control flow enters at the beginning and exits at the end without any branches, except possibly at the end. To partition a code sequence into basic blocks, we first identify all the leaders.

Rules for Identifying Leaders

1. The very first instruction in the code is a leader.
2. Any instruction that is the target of a conditional or unconditional `goto` statement is a leader.
3. Any instruction that immediately follows a `goto` or conditional `goto` statement is a leader.

Once the leaders are identified, the basic block corresponding to a leader consists of the leader itself and all instructions up to, but not including, the next leader.

Applying the Rules to the Code

• Rule 1: `1001: i = 1` is the first instruction, so it is a leader.
• Rule 2 (Targets of gotos):
  • The `goto` at line 1009 targets `1003`. So, `1003` is a leader.
  • The `goto` at line 1011 targets `1002`. So, `1002` is a leader.
  • The `goto` at line 1017 targets `1013`. So, `1013` is a leader.
• Rule 3 (Instructions after gotos):
  • The instruction after line 1009 is `1010`. So, `1010` is a leader.
  • The instruction after line 1011 is `1012`. So, `1012` is a leader.
  • There is no instruction after 1017.

Combining and sorting the list of leaders, we get: {1001, 1002, 1003, 1010, 1012, 1013}. There are 6 unique leaders, which means there are 6 basic blocks.

The Basic Blocks and Control Flow Graph

The code is partitioned into the following 6 blocks:

• B1: {1001}
• B2: {1002}
• B3: {1003 to 1009}
• B4: {1010 to 1011}
• B5: {1012}
• B6: {1013 to 1017}

Bibliography:
- Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2007). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson/Addison Wesley. (Chapter 8: Intermediate-Code Generation).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.