Basic Blocks and Flow Graphs | Examples

Basic Blocks-

 

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-

 

 

Here,

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

 

 

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

 

Flow Graphs-

 

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-

 

Problem-01:

 

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)

 

Solution-

 

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-02:

 

Draw a flow graph for the three address statements given in problem-01.

 

Solution-

 

• Firstly, we compute the basic blocks (already done above).
• Secondly, we assign the flow control information.

 

The required flow graph is-

 

 

Also Read- More Problems On Basic Blocks & Flow Graphs

 

To gain better understanding about Basic Blocks and Flow Graphs,

Watch this Video Lecture

 

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.