Q: 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.
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 identify the basic blocks for the given 3-address code segment, we need to find the sets of instructions that have a single entry point and a single exit point. This means that we need to identify the points in the code where control can enter and exit a block without any jumps or branches.
From the given code segment, we can identify the following basic blocks:
Basic Block 1:
1: a = 1
2: b = 2
Basic Block 2:
3: c = a + b
4: d = c - a
Basic Block 3:
5: if( d < 20 ) goto 11
Basic Block 4:
6: d = b * d
Basic Block 5:
7: if( d > 20 ) goto 11
Basic Block 6:
8: d = a + b
9: e = e + 1
10: goto 6
Basic Block 7:
11: b = a + b
Basic Block 8:
12: e = c - a
Basic Block 9:
13: if( e < d ) goto 3
Basic Block 10:
14: a = b * d
15: b = a - d
(b) Now, let's draw the control flow graph (CFG) for the code segment using the basic blocks we identified:
_______
| |
V |
/--------> Basic Block 1 <-----------\
/ | | \
| V | |
| /-> Basic Block 2 <------------\ |
| / | | | |
| | V | | |
Entry | | Basic Block 3 Basic Block 10
| | | | | |
| V | | | |
| /-> Basic Block 4 Basic Block 7
| / | | | |
V/ V | | |
Basic Block 5 -------> Basic Block 6 <-----| |
| | | | |
| V | | |
| /--------> Basic Block 8 <---| |
| / | | | |
| | V | | |
-----> Basic Block 9 <----------------- |
| | |
V | |
Exit Basic Block 3 _____/ |
| |
V |
Exit Basic Block 8 ________________/
In the above CFG, the entry point is at Basic Block 1, and there are two exit points: Exit Basic Block 3 and Exit Basic Block 8. The arrows represent the control flow between the basic blocks, indicating the possible paths that the program can take while executing.