Basic Blocks & Flow Graphs

Basic Blocks

• 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-

Here,

• All the statements execute in a sequence one after the other.
• Thus, they form a basic block.

Example of Not a Basic Block
Three Address Code for the expression If A<B then 1 else 0 is-

Here,

• 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 1: 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 2: 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.

Flow Graphs

• 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.

Problems Based on Basic Blocks & Flow Graphs

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)

We have-

• 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-

Problem 2: 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