Given the following 3-address code
1: a = 1
2: b = 2
3: c = a + b
4: d = c - a
5: if( d < 20 ) goto 11
6: d = b * d
7: if( d > 20 ) goto 11
8: d = a + b
9: e = e + 1
10: goto 6
11: b = a + b
12: e = c - a
13: if( e < d ) goto 3
14: a = b * d
15: b = a – d
(a) What are the basic blocks for the code segment?
(b) Draw the control flow graph (CFG) for the code once you have determined the basic block.
(a) To determine the basic blocks for the code segment, we need to identify sequences of instructions that do not have any incoming or outgoing branches, except at the beginning and end. We can identify the basic blocks by finding the instructions where a branch takes place (e.g., goto statements or conditional statements). The basic blocks are as follows:
Basic Block 1:
1: a = 1
2: b = 2
Basic Block 2:
3: c = a + b
Basic Block 3:
4: d = c - a
Basic Block 4:
5: if( d < 20 ) goto 11
Basic Block 5:
6: d = b * d
Basic Block 6:
7: if( d > 20 ) goto 11
Basic Block 7:
8: d = a + b
Basic Block 8:
9: e = e + 1
Basic Block 9:
10: goto 6
Basic Block 10:
11: b = a + b
Basic Block 11:
12: e = c - a
Basic Block 12:
13: if( e < d ) goto 3
Basic Block 13:
14: a = b * d
Basic Block 14:
15: b = a – d
(b) To draw the control flow graph (CFG) for the code, we represent each basic block as a node and draw directed edges between them based on the control flow. The CFG for the given code is as follows:
┌───────┐
│ B1 │
└──┬────┘
│
▼
╔═════════╗
║ B2 ║
╚═══┬═════╝
│
▼
╔═════════╗
║ B3 ║
╚═══┬═════╝
│
▼
╔═════════╗ ┌────────────┐
║ B4 ◀────┤ │
╚═══┬═════╝ │ ▼
│ │ ╔═════════╗
▼ │ ║ B5 ║
╔═════════╗ └───►╚═════┬═══╝
║ B6 ◀───────────────┤
╚═══┬═════╝ │
│ ▼
▼ ┌────────────┐
╔═════════╗ │ B7 │
║ B8 ◀─────►╚═════┬════╝
╚═══┬═════╝ │
│ ▼
▼ ┌────────────┐
╔═════════╗ │ B9 │
║ B10 ◀─────►╚═════┬════╝
╚═══┬═════╝ │
│ ▼
▼ ┌────────────┐
╔═════════╗ │ B11 │
║ B12 ◀─────►╚═════┬════╝
╚═══┬═════╝ │
│ ▼
▼ ┌────────────┐
╔═════════╗ │ B13 │
║ B14 ◀─────►╚═════┬════╝
╚═══┬═════╝ │
│ ▼
└──────────────────►
Note: The arrows represent the control flow direction between the basic blocks.