Basic Blocks and Flow Graphs in Compiler Design

What are basic blocks?

 

  • Basic block is a set of statements which always executes in a sequence one after the other without getting halt in the middle or any possibility of branching.
  • Basic blocks do not contain any kind of jump statements in them.
  • All the statements in a basic block gets execute in the same order as they appear in the block without losing the flow control of the program.

 

Also read- Three Address Code

 

Example of a basic block-

 

Consider the three address code for the expression a = b + c + d

(1) T1 = b + c

(2) T2 = T1 + d

(3) a = T2

These statements will be executed in a sequence one after the other and therefore they form a basic block.

 

Consider the following three address code for the expression- “If A<B then 1 else 0”

(1) If A<B goto (4)

(2) T1 = 0

(3) goto (5)

(4) T1 = 1

(5)

These statements will not be executed in a sequence one after the other and therefore they do not form a basic block.

 

Rules for partitioning the intermediate code into basic blocks-

 

After an intermediate code has been generated, we use the following rules to partition the intermediate code into basic blocks-

 

Rule-01: Determine the leaders-

 

Following statements of the code will always be called as leaders-

  1. First statement of the code
  2. Statement that is a target of the conditional goto statement or unconditional goto statement
  3. Statement that appears immediately after a goto statement

 

Rule-02-

 

All the statements that follows the leader (including the leader itself) till just before the next leader appears forms one basic block.

The block containing the first leader which is the first statement of the code is called as initial block.

 

PRACTICE PROBLEM BASED ON BASIC BLOCKS-

 

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 know, first statement of the code is a leader, so PROD = 0 is a leader.
  • Also, we know the target statement of conditional goto or unconditional goto statement is a leader, so T1 = 4 x I is also a leader.

Thus, the given code can be partitioned into two blocks as –

(1) PROD = 0

(2) I = 1

(3) T2 = addr(A) – 4

(4) T4 = addr(B) – 4

B1

(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)

B2

What are Flow Graphs?

 

  • A flow graph is a directed graph (graph with directed edges) in which the flow control information is added to the basic blocks.

 

Rules for Flow Graphs:

 

  • The basic blocks are considered as the nodes for drawing the flow graph.
  • We will have a directed edge from block B1 to block B2 in the flow graph if block B2 appears immediately after block B1 in the given code sequence i.e. block B2 is a successor of block B1

 

PRACTICE PROBLEM BASED ON FLOW GRAPHS-

 

Problem-01:

Consider the following three address statements and draw the flow graph-

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

First of all, we will decide the basic blocks (as we have already done in the last question) and then we will assign the flow control information which will give us the following flow graph-

 

 

To gain better understanding of the concepts of Basic Blocks and Flow Graphs in compiler design,

Watch this video lecture

Download the handwritten notes of “Basic Blocks and Flow Graphs” here-

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Basic blocks and Flow Graphs in Compiler Design
Article Name
Basic blocks and Flow Graphs in Compiler Design
Description
Basic block is a set of statements which always executes in a sequence one after the other without getting halt in the middle or any possibility of branching. A flow graph is a directed graph (graph with directed edges) in which the flow control information is added to the basic blocks.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-