Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
What is the Basic Block in Compiler Design?
2.1.
Algorithm of Basic Block in Compiler Design
2.2.
Example of Basic Block in Compiler Design
2.3.
Explanation
3.
Transformations on Basic Blocks
3.1.
Structure-preserving transformations
3.2.
Algebraic transformations
4.
Frequently Asked Questions
4.1.
What is a Basic Block of code?
4.2.
How can we represent a basic block?
4.3.
What are basic blocks and flow graphs compiler design?
4.4.
What is meant by flow graph in compiler design?
4.5.
What is a leader of basic block?
4.6.
What are the five basic blocks?
5.
Conclusion
Last Updated: May 5, 2024
Easy

Basic Blocks and Flow Graphs in Compiler Design

Author GAZAL ARORA
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction 

The Basic Block is a straight-line code sequence with no in and out branches except at the beginning and end. It is a set of statements that always run one after the other sequentially without any halt.

Basic Blocks and Flow Graphs in Compiler Design

A compiler first converts the source code of any programming language into an intermediate code. It is then converted into basic blocks. After partitioning an intermediate code into basic blocks, the flow of control among basic blocks is represented by a flow graph. 

Intermediate code can be language-independent (three-address code) or language-specific (e.g., Byte Code for Java).

Also see, Phases of Compiler

What is the Basic Block in Compiler Design?

In compiler design, a basic block is a straight-line piece of code that has only one entry point and one exit point. Basic block construction is the process of dividing a program's control flow graph into basic blocks. 

The task is to partition a sequence of three-address codes into the basic block. The new basic block always begins with the first instruction and continues to add instructions until a jump or a label is reached. If no jumps or labels are identified, control will flow sequentially from one instruction to another.

Task: Partition a sequence of three-address codes into basic blocks.

Input: Sequence of three address statements.

Output: A sequence of basic blocks.

Also See, Top Down Parsing

Algorithm of Basic Block in Compiler Design

  1. First, find the set of leaders from intermediate code, the first statements of basic blocks. The following are the steps for finding leaders:
    1. The first instruction of the three-address code is a leader.
    2. Instructions that are the target of conditional/unconditional goto are leaders. 
    3. Instructions that immediately follow any conditional/unconditional goto/jump statements are leaders. 
  2. For each leader found, its basic block contains itself and all instructions up to the next leader.

 

Hence following the above algorithm, you can partition a sequence of three-address code into basic blocks.

Example of Basic Block in Compiler Design

Consider the source code for converting a 10 x 10 matrix to an identity matrix.

for r from 1 to 10 do
      for c from 1 to 10 do
             a [ r, c ] = 0.0;
 
for r from 1 to 10 do
         a [ r, c ] = 1.0;

 

The following are the three address codes for the above source code:

1) r = 1
 2) c = 1
 3) t1 = 10 * r
 4) t2 = t1 + c
 5) t3 = 8 * t2
 6) t4 = t3 - 88
 7) a[t4] = 0.0
 8) c = c + 1
 9) if c <= 10 goto (3)
 10) r = r + 1
 11) if r <= 10 goto (2)
 12) r = 1
 13) t5 = c - 1
 14) t6 = 88 * t5
 15) a[t6] = 1.0
 16) r = r + 1
 17) if r <= 10 goto (13)

 

There are six basic blocks for the above-given code, which are:

  • B1 for statement 1
  • B2 for statement 2
  • B3 for statements 3-9
  • B4 for statements 10-11
  • B5 for statement 12
  • B6 for statements 13-17.

 

Explanation

According to the definition of leaders given in the above algorithm, 

  • Instruction 1 is a leader as the first instruction of a three-address code is always a leader.
  • Instruction 2 is a leader because it is followed by a goto statement at Instruction 11.
  • Instruction 3 and Instruction 13 are also leaders because they are followed by a goto statement at Instruction 9 and 17, respectively.
  • Instruction 10 and Instruction 12 are also leaders because they are followed by a conditional goto statement at Instruction 9 and 17, respectively.

Also read About, Specifications of Tokens in Compiler Design

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Transformations on Basic Blocks

We can also apply transformations to a basic block. Two main classes of transformation are :

  1. Structure-preserving transformations
  2. Algebraic transformations

Structure-preserving transformations

The main Structure-Preserving Transformation on basic blocks are:

  • Common subexpression elimination.
  • Dead code elimination.
  • Renaming of temporary variables.
  • Interchange of two adjacent independent statements.

 

For example, 

a : = b + c    - -  >   a : = b + c
b : = a - d    - -  >   b : = a - d
c : = b + c   - -  >    c : = b + c
d : = a - d    - -  >   d : = b

The basic block can be transformed as shown above because the second and fourth expressions produce the same expression.

Algebraic transformations

Algebraic transformations are used to convert the set of expressions computed by a basic block into an algebraically equivalent set. For example, 

the exponential expression x: = y * * 2 can be replaced with x: = y * y.

Frequently Asked Questions

What is a Basic Block of code?

The Basic Block is a straight-line code sequence with no in and out branches except at the start and end. It is a set of statements that always run one after the other sequentially.

How can we represent a basic block?

Control flow graphs can be used to represent basic blocks in a software program. A control flow graph displays how program control is passed between blocks. It can be used in software optimization to find unwanted loops.

What are basic blocks and flow graphs compiler design?

In compiler design, basic blocks are a sequence of instructions that have a single entry point and a single exit point. Flow graphs are graphical representations of a program's control flow, where nodes represent basic blocks and edges represent the possible flow of control between them.

What is meant by flow graph in compiler design?

In compiler design, a flow graph is a graphical representation of a program's control flow. It is a directed graph that shows the flow of control between basic blocks, with each basic block represented as a node in the graph. 

What is a leader of basic block?

The leader of a basic block is the first instruction in the block, serving as the entry point for control flow within the block.

What are the five basic blocks?

Basic blocks typically comprise entry, exit, conditional, unconditional, and empty blocks, forming fundamental units in control flow graphs within programs.

Conclusion

In this article, we learned about basic blocks in Compiler Design. We learned that basic blocks are the set of statements that always run one after the other sequentially without any halt.

We then designed an algorithm to convert a sequence of three-address codes into basic blocks.

Next, we saw two major transformations that can be applied to a basic block. These were:

  • Structure-preserving transformations.
  • Algebraic transformations.

A basic block can be represented by Control flow graphs. Click here to learn more about flow diagrams.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Run Time Environments
Next article
Block Optimization
Live masterclass