In computing, a basic block is a straight-line piece of code without any jumps or jump targets in the middle; jump targets, if any, start a block, and jumps end a block. Basic blocks are the usually the basic unit to which compiler optimizations are applied in compiler theory. Basic blocks form the vertices or nodes in a control flow graph.
More formally, we say a sequence of instructions forms a basic block if the statement in each position dominatess, or always executes before, all those in later positions, and no other statement executes between two statements in the sequence. This definition is more general than the intuitive one in some ways. For example, it allows unconditional jumps to labels not targetted 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
- Jumps, either unconditional or parameterized
- Conditional branches
- Returns to a calling procedure
- Function calls which may throw an exception
- Procedure entry points
- Targets of jumps or branches
- "Fall-through" statements following some conditional branches
- Statements following calls that throw exceptions
- Exception handlers
See also: control flow graph