Basic block

A basic block is a maximal sequence of consecutive three-address instructions with one entry point (only the first instruction can be reached from outside) and one exit point (control leaves only at the last instruction, with no jumps into or out of the middle).

Algorithm to find basic blocks

1. Find the leaders (first instructions of blocks):
   • the first instruction of the program;
   • the target of any conditional or unconditional jump;
   • the instruction immediately after a jump (conditional or unconditional).
2. For each leader, the basic block consists of the leader and all instructions up to (but not including) the next leader or the end of the program.

Example three-address code

1  sum = 0
2  i = 1
3  if i > 10 goto 8
4  t1 = i * 2
5  sum = sum + t1
6  i = i + 1
7  goto 3
8  print sum

Leaders: instruction 1 (first), 3 (target of the jump at 7), 4 (follows the conditional jump at 3), 8 (target of the jump at 3 and follows the jump at 7). So the leaders are $\{1, 3, 4, 8\}$.

Block	Instructions
$B_1$	1-2
$B_2$	3
$B_3$	4-7
$B_4$	8

Control-flow graph (CFG)

A CFG has the basic blocks as nodes. There is an edge $B_i \to B_j$ if control can pass from the end of $B_i$ to the start of $B_j$: either by a jump from the last instruction of $B_i$ to the leader of $B_j$, or because $B_j$ follows $B_i$ in program order and $B_i$ does not end in an unconditional jump.

Uses: the CFG exposes loops (here $B_2 \to B_3 \to B_2$), and is the basis for data-flow analysis, local optimizations inside a block, and global optimizations such as code motion and dead-code elimination.