Basic Blocks and Flow Graphs

A stream of three-address code is a flat list — instruction after instruction, with jumps threading through it like wormholes. Before a compiler can reason about that code — allocate registers, propagate constants, eliminate redundant work — it has to recover the shape hidden in the flat list: which instructions always run together, and how control can pass between those clumps. That shape is the control-flow graph, and its nodes are basic blocks.

A basic block is a maximal run of straight-line instructions with one entry and one exit: control enters only at the top and leaves only at the bottom, with no jumps into the middle and no jumps out of the middle. That single property is enormously freeing. Inside a block there are no surprises — every instruction runs, exactly once, in order, every time the block is entered. So the block is the natural unit of local analysis: whatever we prove about the top of a block still holds all the way down, because nothing can sneak in or out along the way.

Finding the blocks: the leader rule

To carve a TAC listing into blocks we first find the leaders — the instructions that begin a block. There are exactly three ways an instruction earns leader status:

the first instruction of the program is a leader;
any instruction that is the target of a conditional or unconditional jump is a leader;
any instruction that immediately follows a jump is a leader.

Once the leaders are marked, each basic block is a leader together with all instructions up to — but not including — the next leader (or the end of the program). Every instruction lands in exactly one block, and the blocks tile the listing with no gaps and no overlaps. The rule is purely syntactic: you can run it with a highlighter and never think about what the code means.

From blocks to a graph

The control-flow graph (CFG) has one node per basic block and a directed edge B_i \to B_j whenever control may pass from the end of B_i to the start of B_j. Concretely, add an edge B_i \to B_j when either:

B_j begins with the target of a jump that ends B_i; or
B_j immediately follows B_i in the listing and B_i does not end in an unconditional jump (the fall-through edge).

A block ending in a conditional branch has two successors — the branch target and the fall-through — so it fans out. Two distinguished nodes are usually added: an entry feeding the first block, and an exit that every block with no other successor flows into. The result below is built one block at a time from a little program that computes x two different ways depending on the sign of t = a + b:

Notice the shape: block B1 ends in if t < 0 goto B3, so it has two out-edges — a branch edge to B3 and a fall-through edge to B2. B2 ends in an unconditional goto B4, so it has no fall-through — only the branch edge. B2 and B3 both funnel into B4, which is therefore said to have two predecessors. This diamond — a split at B1, a merge at B4 — is the CFG fingerprint of an if/else.

Successors, predecessors, and the vocabulary of flow

The CFG is just a directed graph, so it borrows all the usual graph vocabulary — but a few terms do the heavy lifting in code generation:

Term	Meaning
successors of B	the blocks reachable from B by one out-edge — where control might go next
predecessors of B	the blocks with an edge into B — where control could have come from
merge point	a block with two or more predecessors (a join in control flow)
branch / split	a block with two or more successors (ends in a conditional jump)
back edge	an edge B_i \to B_j where B_j is at or above B_i in the listing — the signature of a loop

A dataflow value that must be true "on entry to B" has to hold no matter which predecessor we arrived from — that is why merge points force analyses to combine information (meet or join) across incoming edges. Everything downstream in this course, from liveness to constant propagation, is phrased in terms of successors and predecessors on this graph.

Loops live in the graph, not the text

The reason we bother building a graph at all is that loops are a property of the edges, not of the source syntax. A while, a for, a goto that jumps backward, even a recursive tangle of hand-written jumps — all of them show up in the CFG as the same thing: a cycle. Formally, the strongly connected components of the CFG capture exactly the sets of blocks that can repeatedly reach one another, and a back edge (an edge whose head dominates its tail) is what closes such a cycle. The blocks a back edge can reach form the loop's body — its \text{natural loop}.

This matters because loops are where programs spend their time: a body executed n times is n times as worth optimising. Once the CFG exposes a loop as a cycle, a compiler can hoist invariant computations out of it, allocate registers more aggressively inside it, or unroll it — none of which is visible from the flat TAC listing.

The trick is dominance. Block D dominates block B if every path from entry to B passes through D. An edge B \to D is a genuine back edge — and hence a loop — precisely when its target D dominates its source B: control cannot reach the jump without first having gone through the place it jumps to, so it must be circling. An ordinary forward if that happens to branch to an earlier label fails this test, because you can reach the branch without passing through its target. Dominance is what lets the compiler distinguish "spaghetti that loops" from "spaghetti that merely re-joins".

The leader algorithm, in code

Here is the whole pipeline — leaders, then blocks, then edges — run on the Dragon Book's array-init loop. Each TAC line is an object; a goto field marks a jump target and cond marks it conditional (so the block also falls through). Watch which lines become leaders and how the two conditional branches each spawn a back edge and a fall-through.

interface Tac { text: string; goto?: number; cond?: boolean; } // A TAC program, 1-based line numbers. `goto` = jump target; `cond` = conditional branch. const prog: Tac[] = [ { text: "i = 1" }, // 1 { text: "j = 1" }, // 2 { text: "t1 = 10 * i" }, // 3 { text: "t2 = t1 + j" }, // 4 { text: "t3 = 8 * t2" }, // 5 { text: "t4 = t3 - 88" }, // 6 { text: "a[t4] = 0.0" }, // 7 { text: "j = j + 1" }, // 8 { text: "if j <= 10 goto 3", goto: 3, cond: true }, // 9 { text: "i = i + 1" }, // 10 { text: "if i <= 10 goto 2", goto: 2, cond: true }, // 11 ]; // 1) LEADERS: first line; every jump target; every line after a jump. function findLeaders(p: Tac[]): number[] { const L = new Set<number>([1]); p.forEach((ins, i) => { const line = i + 1; if (ins.goto !== undefined) { L.add(ins.goto); // target of the jump if (line + 1 <= p.length) L.add(line + 1); // instruction after the jump } }); return [...L].sort((a, b) => a - b); } // 2) BLOCKS: a leader up to (not including) the next leader. function partition(p: Tac[], L: number[]): number[][] { return L.map((from, k) => { const to = k + 1 < L.length ? L[k + 1] - 1 : p.length; const lines: number[] = []; for (let ln = from; ln <= to; ln++) lines.push(ln); return lines; }); } // 3) EDGES: branch target(s) + fall-through of the block's last instruction. function cfgEdges(p: Tac[], blocks: number[][]): string[] { const blockOf = (line: number) => blocks.findIndex((b) => b.includes(line)); const out: string[] = []; blocks.forEach((b, bi) => { const last = b[b.length - 1]; const ins = p[last - 1]; if (ins.goto !== undefined) { out.push(`B${bi} -> B${blockOf(ins.goto)} (branch)`); if (ins.cond && last + 1 <= p.length) out.push(`B${bi} -> B${blockOf(last + 1)} (fall-through)`); } else if (last + 1 <= p.length) { out.push(`B${bi} -> B${blockOf(last + 1)} (fall-through)`); } else { out.push(`B${bi} -> EXIT`); } }); return out; } const leaders = findLeaders(prog); const blocks = partition(prog, leaders); console.log("Leaders (lines):", leaders.join(", ")); blocks.forEach((b, i) => console.log(`B${i} = lines [${b.join(", ")}]`)); console.log("--- CFG edges ---"); cfgEdges(prog, blocks).forEach((e) => console.log(e));

The output shows leaders 1, 2, 3, 10, four blocks, and — crucially — that the conditional branches at lines 9 and 11 each produce two edges: a back edge that closes the loop and a fall-through that escapes it. That pair of edges per conditional branch is the single most important thing to get right.

The classic partitioning bug is to mark only one instruction around a jump. But a conditional jump if c goto L creates two leaders at once: the target L begins a block, and the instruction immediately after the jump begins another block (because control can fall through when c is false). Miss either one and your "basic block" secretly has two entry points or two exit points — it is no longer basic, and every analysis built on it silently breaks.

The mirror-image slip is on the edges: people draw the branch edge to the target and forget the fall-through edge. A block ending in a conditional branch always has two successors; only an unconditional goto (or the exit) has a single successor and no fall-through. When in doubt, ask: "if the condition is false, where does control go?" — that answer is the fall-through edge.

With the program reshaped into a flow graph, the compiler finally has something to compute over. The next lesson uses exactly this structure — one block at a time, with its successors and predecessors — to generate target code, and later chapters run liveness and colouring across the whole graph.