Basic Block - Algorithm To Generate Basic Blocks.

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).

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 :

1. The first instruction is a leader.
2. The target of a conditional or an unconditional goto/jump instruction is a leader.
3. 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 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 cannot return, such as functions which throw exceptions or special calls like C's longjmp and exit
• 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.