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.
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 are basic blocks and flow graphs 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
First, find the set of leaders from intermediate code, the first statements of basic blocks. The following are the steps for finding leaders:
- The first instruction of the three-address code is a leader.
- Instructions that are the target of conditional/unconditional goto are leaders.
- Instructions that immediately follow any conditional/unconditional goto/jump statements are leaders.
- 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.
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.
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.
Transformations on Basic Blocks
We can also apply transformations to a basic block. Two main classes of transformation are :
- Structure-preserving transformations
- Algebraic 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.
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 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?
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 are basic blocks in control flow diagram?
In a control flow diagram, a basic block is a sequence of program instructions that has a single entry point and a single exit point. Basic blocks are used to simplify the representation of a program's control flow.
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.
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.
- First and Follow in Compiler Design
- Top Down Parsing and Bottom Up Parsing
- Backpatching In Compiler Design
- Flow Graphs
- Intermediate Code Procedures
- Three Address Code
Input Buffering in Compiler Design
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.