Basic Blocks & Flow Graphs | Compiler Design - Computer Science Engineering (CSE) PDF Download

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.

Clear all your Computer Science Engineering (CSE) doubts with EduRev Join for Free

Join for Free

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.

Download the notes Basic Blocks & Flow Graphs

Download as PDF

Download as PDF

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