Basic block
Encyclopedia
In computing
, a basic block is a portion of the code within a program with certain desirable properties that make it highly amenable to analysis. Compiler
s usually decompose programs into their basic blocks as a first step in the analysis process. Basic blocks form the vertices or nodes in a control flow graph
.
Under these circumstances, whenever the first instruction in a basic block is executed, the rest of the instructions are necessarily executed exactly once, in order.
The code may be source code
, assembly code or some other sequence of instructions.
More formally, a sequence of instructions forms a basic block if:
This definition is more general than the intuitive one in some ways. For example, it allows unconditional jumps to labels not targeted by other jumps. This definition embodies the properties that make basic blocks easy to work with when constructing an algorithm.
The blocks to which control may transfer after reaching the end of a block are called that block's successors, while the blocks from which control may have come when entering a block are called that block's predecessors. The start of a basic block may be jumped to from more than one location.
Note that this method does not always generate maximal basic blocks, by the formal definition, but they are usually sufficient (maximal basic blocks are basic blocks which cannot be extended by including adjacent blocks without violating the definition of a basic block).
Input : A sequence of instructions (mostly Three address code
).
Output: A list of basic blocks with each three-address statement in exactly one block.
Step 1. Identify the leaders in the code. Leaders are instructions which come under any of the following 3 categories :
Step 2. Starting from a leader, the set of all following instructions until and not including the next leader is the basic block corresponding to the starting leader.
Thus every basic block has a leader.
Instructions that end a basic block include
Instructions which begin a new basic block include
Note that, because control can never pass through the end of a basic block, some block boundaries may have to be modified after finding the basic blocks. In particular, fall-through conditional branches must be changed to two-way branches, and function calls throwing exceptions must have unconditional jumps added after them. Doing these may require adding labels to the beginning of other blocks.
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
, a basic block is a portion of the code within a program with certain desirable properties that make it highly amenable to analysis. Compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
s usually decompose programs into their basic blocks as a first step in the analysis process. Basic blocks form the vertices or nodes in a control flow graph
Control flow graph
A control flow graph in computer science is a representation, using graph notation, of all paths that might be traversed through a program during its execution.- Overview :...
.
Definition
The code in a basic block has:- one entry point, meaning no code within it is the destination of a jump instruction anywhere in the program;
- one exit point, meaning only the last instruction can cause the program to begin executing code in a different basic block.
Under these circumstances, whenever the first instruction in a basic block is executed, the rest of the instructions are necessarily executed exactly once, in order.
The code may be source code
Source code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
, assembly code or some other sequence of instructions.
More formally, a sequence of instructions forms a basic block if:
- the instruction in each position dominates, or always executes before, all those in later positions, and
- no other instruction executes between two instructions in the sequence.
This definition is more general than the intuitive one in some ways. For example, it allows unconditional jumps to labels not targeted by other jumps. This definition embodies the properties that make basic blocks easy to work with when constructing an algorithm.
The blocks to which control may transfer after reaching the end of a block are called that block's successors, while the blocks from which control may have come when entering a block are called that block's predecessors. The start of a basic block may be jumped to from more than one location.
Algorithm to generate basic blocks.
The algorithm for generating basic blocks from a listing of code is simple: the analyser scans over the code, marking block boundaries, which are instructions which may either begin or end a block because they either transfer control or accept control from another point. Then, the listing is simply "cut" at each of these points, and basic blocks remain.Note that this method does not always generate maximal basic blocks, by the formal definition, but they are usually sufficient (maximal basic blocks are basic blocks which cannot be extended by including adjacent blocks without violating the definition of a basic block).
Input : A sequence of instructions (mostly Three address code
Three address code
In computer science, three-address code is a form of representing intermediate code used by compilers to aid in the implementation of code-improving transformations...
).
Output: A list of basic blocks with each three-address statement in exactly one block.
Step 1. Identify the leaders in the code. Leaders are instructions which come under any of the following 3 categories :
- The first instruction is a leader.
- The target of a conditional or an unconditional goto/jump instruction is a leader.
- The instruction that immediately follows a conditional or an unconditional goto/jump instruction is a leader.
Step 2. Starting from a leader, the set of all following instructions until and not including the next leader is the basic block corresponding to the starting leader.
Thus every basic block has a leader.
Instructions that end a basic block include
- Unconditional and conditional branchBranch (computer science)A branch is sequence of code in a computer program which is conditionally executed depending on whether the flow of control is altered or not . The term can be used when referring to programs in high level languages as well as program written in machine code or assembly language...
es, both direct and indirect - Returns to a calling procedure
- Instructions which may throw an exceptionException handlingException handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of exceptions, special conditions that change the normal flow of program execution....
- Function calls can be at the end of a basic block if they may not return, such as functions which throw exceptions or special calls like CC (programming language)C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
'slongjmpandexit - The return instruction itself.
Instructions which begin a new basic block include
- Procedure and function entry points
- Targets of jumps or branches
- "Fall-through" instructions following some conditional branches
- Instructions following ones that throw exceptions
- Exception handlers.
Note that, because control can never pass through the end of a basic block, some block boundaries may have to be modified after finding the basic blocks. In particular, fall-through conditional branches must be changed to two-way branches, and function calls throwing exceptions must have unconditional jumps added after them. Doing these may require adding labels to the beginning of other blocks.