Basic Blocks and Control-Flow Graphs

A basic block is a maximal sequence of consecutive three-address code instructions such that control enters only at the first instruction and leaves only after the last instruction, with no branching in or out in between. Concretely: if execution reaches any instruction in the block, it is guaranteed to execute every instruction in the block, in order, exactly once, before leaving. This "all-or-nothing, straight-line" property is what makes a basic block the right unit of granularity for local optimizations (constant folding, common-subexpression elimination within the block) and the right node type for global analyses that operate between blocks. The key to finding basic blocks is the notion of a leader — an instruction that must be the first instruction of some basic block. An instruction is a leader if it is (1) the first instruction of the whole program (or procedure), (2) the target of some conditional or unconditional jump, or (3) the instruction immediately following a conditional or unconditional jump (including immediately after a `return`). Once leaders are identified, each basic block consists of a leader together with all instructions up to, but not including, the next leader (or end of program). The control-flow graph is then built by treating each basic block as a node and drawing a directed edge `B_i → B_j` whenever control can pass from the last instruction of `B_i` directly to the first instruction of `B_j` — either because `B_i` ends in a jump to `B_j`'s leader, or because `B_i` simply falls through (its last instruction is not an unconditional jump, and `B_j` follows it textually). Two designated blocks, `ENTRY` and `EXIT`, are conventionally added: `ENTRY` has an edge to the block containing the procedure's first instruction, and every block that can end execution (falls off the end, or returns) has an edge to `EXIT`. This gives every analysis a single well-defined start and end point to anchor fixpoint computations, which becomes essential once you reach Data-Flow Analysis Framework.

Construction happens in two clean passes over the instruction list, both linear in the number of instructions.

Pass 1 — find leaders. Scan the instruction sequence once. Mark the first instruction as a leader. Whenever an instruction is a jump (conditional or unconditional) to some target `L`, mark `L` as a leader, and also mark the instruction textually following the jump as a leader (because that is where control resumes if the jump is conditional and not taken, or simply because a fresh block must start after any jump regardless of whether it is taken).

Pass 2 — build blocks. Walk the instructions again; each leader starts a new block, and every following non-leader instruction is appended to the current block until the next leader is reached.

Pass 3 — wire edges. For each block `B` ending in instruction `s`:

• if `s` is `goto L`, add edge `B → block(L)`;
• if `s` is `if cond goto L`, add edge `B → block(L)` and `B → succ(B)` (fall-through, the block that follows `B` textually);
• if `s` is `return` (or the block is the program's last block with no jump), add edge `B → EXIT`;
• otherwise (`s` is an ordinary instruction, not a control transfer), add a fall-through edge `B → succ(B)`.

Finally, add `ENTRY → B_first`, where `B_first` is the block containing the first instruction. ``` function BUILD_CFG(instrs[1..n]): // --- Pass 1: find leaders --- isLeader[1..n] ← all false isLeader[1] ← true // first instruction always starts a block for i ← 1 to n: if instrs[i] is Jump(target) or CondJump(cond, target): isLeader[ index_of(target) ] ← true if i + 1 <= n: isLeader[i + 1] ← true // instruction after any jump starts a block // --- Pass 2: slice into blocks --- blocks ← [] current ← [] for i ← 1 to n: if isLeader[i] and current is not empty: blocks.append(current) current ← [] current.append(instrs[i]) if current is not empty: blocks.append(current) leaderIndexToBlock ← map from each leader's instruction index to its block // --- Pass 3: wire edges --- ENTRY, EXIT ← fresh sentinel nodes edges ← { (ENTRY, blocks[0]) } for k ← 0 to len(blocks) - 1: B ← blocks[k] last ← B.lastInstruction match last: case Jump(target): edges.add( (B, leaderIndexToBlock[index_of(target)]) ) case CondJump(cond, target): edges.add( (B, leaderIndexToBlock[index_of(target)]) ) if k + 1 < len(blocks): edges.add( (B, blocks[k+1]) ) // fall-through case Return: edges.add( (B, EXIT) ) case _: // ordinary instruction, falls through if k + 1 < len(blocks): edges.add( (B, blocks[k+1]) ) else: edges.add( (B, EXIT) ) // falls off the end of the program return (blocks, edges, ENTRY, EXIT) ``` The diagram below shows the shape produced: straight-line blocks as boxes, jump/branch/fall-through edges as arrows, with `ENTRY` and `EXIT` as sentinels.

Time. Pass 1 scans every instruction once, doing O(1) work per instruction (checking whether it is a jump, marking at most two leader flags) — O(n). Pass 2 walks the instructions once more, appending each to the current block — O(n). Pass 3 iterates over the blocks, and does O(1) work per block for wiring at most two outgoing edges, so it is O(number of blocks) ≤ O(n). Total: O(n) time, where n is the number of three-address instructions, and this is asymptotically optimal since every instruction must be inspected at least once. Building a lookup from label/target to instruction index (for `index_of` and `leaderIndexToBlock`) is done with a hash map or array indexed by label, adding no more than O(n) preprocessing.

Space. The algorithm stores the leader bit array (O(n)), the list of blocks (O(n), since blocks partition the instructions), and the edge set (O(number of blocks), since each block has at most two outgoing edges: a jump target and a fall-through). So total space is O(n).

Correctness argument. The central invariant to verify is: > Partition invariant: every instruction belongs to exactly one basic block, and within a block, control flow is strictly sequential — the block's first instruction is the only possible entry point, and only the last instruction can transfer control elsewhere. This holds by construction. Every instruction index gets assigned to exactly one block in Pass 2, because leaders are visited in increasing order and each non-leader instruction is appended to the block started by the most recent leader — this is a partition, not a cover, since the `if isLeader[i] and current is not empty` guard ensures a new block starts exactly at leader positions and nowhere else. No instruction interior to a block can be a jump target, because if it were, Pass 1 would have marked it as a leader, forcing it to start its own block — contradiction. No instruction interior to a block can itself be a jump, because if it were, Pass 1 would mark the next instruction as a leader, again forcing a block boundary immediately after it — so a jump can only be the last instruction of its block. The second invariant is about edges: > Edge completeness: for every pair of instructions `(s, s')` such that control can transfer directly from `s` to `s'` at run time, if `s` is the last instruction of block `B` and `s'` is the first instruction of block `B'`, then the CFG contains the edge `B → B'`, and conversely every CFG edge corresponds to a real possible transfer. Pass 3's case analysis is exhaustive over the three ways a block can end: an unconditional jump (single successor, the target), a conditional jump (exactly two successors: target and fall-through, matching the two run-time outcomes of the branch), or an ordinary instruction (one successor, the textual next block, since control simply proceeds). Each case is handled, and each adds exactly the edges that correspond to real transfers — no more, no fewer. The `ENTRY`/`EXIT` sentinels are added exactly once and connect to exactly the blocks that can legitimately be first or last at run time. Hence the CFG is a faithful, exact model of every intraprocedural control transfer in the program.

Tradeoffs. The construction as given is intentionally conservative: a conditional jump always gets two outgoing edges even if static analysis could prove one branch dead — that refinement is left to later passes (constant propagation, unreachable-code elimination), not to CFG construction itself, which must remain a sound over-approximation of all run-time behavior. Precision is deliberately sacrificed for soundness and cheapness: O(n) construction is worth it because the CFG is rebuilt or incrementally patched many times during a compilation, and any unsoundness here (a missing edge) would silently break every analysis downstream.

Consider this three-address code for summing an array (line numbers added for reference): ``` 1: i = 0 2: s = 0 3: L1: if i < n goto 5 4: goto 8 5: t = a[i] 6: s = s + t 7: i = i + 1 8: ... // wait — fix below ``` To make the trace honest and non-trivial (loop and branch, not just a straight loop), use this slightly richer version with an `if` inside the loop body that skips negative elements: ``` 1: i = 0 2: s = 0 3: L1: if i < n goto 4 else goto 10 4: t = a[i] 5: if t < 0 goto 7 6: s = s + t 7: i = i + 1 8: goto 3 9: (unreachable filler, see pitfalls) 10: r = s 11: return r ```

Pass 1 (leaders). Start: instruction 1 is a leader (first instruction). Scan for jumps:

• Instr 3 is `if...goto 4 else goto 10` → mark 4 and 10 as leaders; mark instruction after the jump (4) as leader too (already done).
• Instr 5 is `if t<0 goto 7` → mark 7 as leader; mark instruction after (6) as leader.
• Instr 8 is `goto 3` → mark 3 as leader; mark instruction after (9) as leader.

Leader set: `{1, 3, 4, 6, 7, 9, 10}`.

Pass 2 (slice into blocks).

Pass 3 (edges).

The resulting graph has a back edge `B5 → B2`, which is precisely the structural signature of a loop — the thing Loop Optimizations and Loop-Invariant Code Motion looks for when identifying natural loops. It also has a genuinely unreachable block `B6`, flagged honestly rather than swept under the rug, which is exactly the kind of edge case a naive implementation gets wrong (see pitfalls below).

Basic blocks and their graph structure emerged from the earliest systematic work on program optimization, when researchers realized that program analysis required a coarser unit than the single instruction.

Every production optimizing compiler — GCC, LLVM, the JVM's HotSpot JIT, .NET's RyuJIT, Go's compiler — builds a CFG (often per function, sometimes per translation unit) as one of its earliest intermediate-representation-building steps, immediately after generating three-address code or an equivalent linear IR. LLVM's IR is explicitly organized as basic blocks grouped into functions, with `br` and `ret` instructions as the only legal block terminators, directly encoding the "single entry, single exit, terminator-only control transfer" discipline described here. JIT compilers in web browsers (V8, SpiderMonkey) build lightweight CFGs on hot functions at run time to drive speculative optimizations, then must be able to cheaply patch or discard the CFG when a speculation fails ("deoptimization"). Static analysis and security tools (control-flow integrity checking, taint analysis, symbolic execution engines like KLEE) rely on the same CFG structure to enumerate feasible execution paths. Profile-guided optimization annotates CFG edges with observed branch frequencies to decide code layout, inlining, and which paths deserve aggressive optimization. In every one of these systems, the CFG built by exactly the leader/block/edge algorithm above is the substrate that later stages — Data-Flow Analysis Framework for liveness and reaching definitions, Static Single Assignment (SSA) Form for renaming variables uniquely per definition, and loop-optimizations for recognizing and transforming natural loops — all consume without modification to its basic shape.

Ask the tutor: How do dominators and natural loops get computed from a control-flow graph, and why do back edges matter for that?