10.3 Basic Blocks and Control Flow Graphs

A basic block is a straight-line run of instructions with one entry and one exit: control enters at the top, falls through to the bottom, and never jumps into or out of the middle.

Grouping code this way lets the compiler reason about a block as a single unit, then reason about how blocks connect.

Finding Leaders

Blocks are cut at leaders. A leader is the first instruction, any jump target, and any instruction immediately following a jump. Everything from one leader up to the next forms a block.

This rule is mechanical and complete: apply it and the program partitions cleanly into basic blocks with no overlap.

The Control Flow Graph

Connect blocks with edges and you have a control flow graph (CFG). Sequential code yields one successor; a conditional branch yields two; a loop adds a back edge.

The CFG is the substrate for almost everything downstream: dominance, loops, liveness, and SSA all read it.

Out-Degree Tells the Story

A block ending in a conditional has out-degree two. A block ending in a jump has one. A return has none. Reading edge counts already reveals branch and merge structure.

Predecessors, Successors, and Merges

Every edge has two ends, so each block has a set of successors and a set of predecessors. A block with two or more predecessors is a merge point, and merges are where data flow gets interesting: values arriving from different paths must be reconciled. This is the exact spot where SSA later inserts phi nodes.

Entry, Exit, and Reachability

A well-formed CFG has a single entry block and, conceptually, one exit. Blocks not reachable from entry are dead and can be deleted on sight. A first, cheap optimization is simply: build the CFG, mark reachable blocks, drop the rest.

Worked Example

From the conditional TAC of the previous section, leaders fall at the first line, L1, and L2. That yields four blocks: the test, the else arm, the then arm, and the merge. Edges run test to both arms, and both arms to the merge. Drawn out, it is the canonical diamond, the smallest interesting CFG you can analyze.

Get comfortable reading this diamond. Dominators, loops, liveness, and SSA all reuse exactly this shape.