Basic block

From Wikipedia, the free encyclopedia

In computing, a basic block is code that has one entry point (i.e., no code within it is the destination of a jump instruction), one exit point and no jump instructions contained within it. The start of a basic block may be jumped to from more than one location. The end of a basic block may be a jump instruction or the destination of a jump instruction. Basic blocks are usually the basic unit to which compiler optimizations are applied. Basic blocks form the vertices or nodes in a control flow graph.

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 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 algorithm for generating basic blocks from a listing of code is simple: you scan 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.

Instructions that end a basic block include

Unconditional and conditional branches, both direct and indirect.
Returns to a calling procedure
Instructions which may throw an exception
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 C's longjmp and exit.

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.