Basic Blocks and Leaders
You'll learn how to identify the boundaries of basic blocks by recognizing three types of leader instructions.
The Core Idea
A basic block is a straight-line sequence of instructions with no branches in (except at the entry) and no branches out (except at the exit). Think of it like a hallway with one entrance and one exit—once you enter, you must walk straight through to the end without turning.
To divide a program into basic blocks, we first identify leaders—the first instruction of each block. Once we know where leaders are, we can draw boundaries: a basic block runs from one leader up to (but not including) the next leader.
The Three Types of Leaders
An instruction is a leader if it satisfies any of these conditions:
- Entry point: The very first instruction of the program or procedure
- Jump target: Any instruction that is the target of a jump, branch, or goto statement
- Follower: Any instruction that immediately follows a jump, branch, conditional, or return statement
Why This Works
- The entry point starts the first block (you always begin somewhere)
- Jump targets start new blocks because control can arrive from elsewhere (a new entrance)
- Followers start new blocks because the previous instruction could have transferred control away (forcing a new hallway)
Example in Three-Address Code
1: x = input // Leader (entry point)
2: if x > 0 goto 5
3: y = -x // Leader (follows conditional)
4: goto 6
5: y = x // Leader (jump target)
6: output y // Leader (jump target)
This creates four basic blocks: {1-2}, {3-4}, {5}, {6}.
Key Takeaway: Leaders mark basic block boundaries at entry points, jump targets, and instructions following control transfers—these three rules partition code into maximal straight-line sequences.