Course contentsShow
← Computer Science
Lesson 2043 of 2,87246. Compilation and InterpretationFree lesson

Basic Blocks and Leaders

Master identifying basic block boundaries using leader instructions: entry points, jump targets, and followers.

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:

  1. Entry point: The very first instruction of the program or procedure
  2. Jump target: Any instruction that is the target of a jump, branch, or goto statement
  3. 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.