|Basic block is a set of statements that always executes in a sequence one after the other.|
The characteristics of basic blocks are-
- They do not contain any kind of jump statements in them.
- There is no possibility of branching or getting halt in the middle.
- All the statements execute in the same order they appear.
- They do not lose lose the flow control of the program.
Example Of Basic Block-
Three Address Code for the expression a = b + c + d is-
- All the statements execute in a sequence one after the other.
- Thus, they form a basic block.
Also Read-Three Address Code
Example Of Not A Basic Block-
Three Address Code for the expression If A<B then 1 else 0 is-
- The statements do not execute in a sequence one after the other.
- Thus, they do not form a basic block.
Partitioning Intermediate Code Into Basic Blocks-
Any given code can be partitioned into basic blocks using the following rules-
Rule-01: Determining Leaders-
Following statements of the code are called as Leaders–
- First statement of the code.
- Statement that is a target of the conditional or unconditional goto statement.
- Statement that appears immediately after a goto statement.
Rule-02: Determining Basic Blocks-
- All the statements that follow the leader (including the leader) till the next leader appears form one basic block.
- The first statement of the code is called as the first leader.
- The block containing the first leader is called as Initial block.
|A flow graph is a directed graph with flow control information added to the basic blocks.|
- The basic blocks serve as nodes of the flow graph.
- There is a directed edge from block B1 to block B2 if B2 appears immediately after B1 in the code.
PRACTICE PROBLEMS BASED ON BASIC BLOCKS & FLOW GRAPHS-
Compute the basic blocks for the given three address statements-
(1) PROD = 0
(2) I = 1
(3) T2 = addr(A) – 4
(4) T4 = addr(B) – 4
(5) T1 = 4 x I
(6) T3 = T2[T1]
(7) T5 = T4[T1]
(8) T6 = T3 x T5
(9) PROD = PROD + T6
(10) I = I + 1
(11) IF I <=20 GOTO (5)
- PROD = 0 is a leader since first statement of the code is a leader.
- T1 = 4 x I is a leader since target of the conditional goto statement is a leader.
Now, the given code can be partitioned into two basic blocks as-
Draw a flow graph for the three address statements given in problem-01.
- Firstly, we compute the basic blocks (already done above).
- Secondly, we assign the flow control information.
The required flow graph is-
To gain better understanding about Basic Blocks and Flow Graphs,
Download Handwritten Notes Here-
Next Article-Directed Acyclic Graphs
Get more notes and other study material of Compiler Design.
Watch video lectures by visiting our YouTube channel LearnVidFun.