Building Basic Blocks and Control-Flow Graphs from Linear Code

A linear instruction list is enough to execute a program, and it is useless for reasoning about one. Liveness, constant propagation, and loop detection all need to know which instructions can reach which other instructions. The structure that answers that question is a directed graph whose nodes are straight-line runs of instructions and whose edges are the possible transfers of control between them.

Leaders and the Three Rules

The construction rests on a single observation: within a run of instructions that has exactly one entry and one exit, execution is strictly sequential, so the only facts worth tracking are those at the entry and exit of the run. A maximal such run is a basic block, and it is identified by its first instruction, the leader.

A leader is any instruction that satisfies one of three conditions. It is the first instruction of the function. It is the target of a branch, conditional or unconditional. It is the instruction immediately following a branch or a return. The first rule guarantees the entry block exists; the second guarantees that every jump lands on a boundary; the third guarantees that a block never has two possible successors inside itself. The third rule requires the list to be in execution order for fall-through, so the construction applies to a list where every conditional branch’s fall-through successor is the next instruction — the shape the front end emits, and the one a stack-machine bytecode already has, since conditional jumps in that form are explicit and fall-through is implicit.

Once leaders are marked, a block extends from its leader up to, but not including, the next leader. The block’s terminator is therefore the instruction just before the next leader, which by the third rule must be a branch or a return, or the last instruction of the function.

def build_blocks(insns):
    leaders = {0}
    for i, ins in enumerate(insns):
        if ins.is_branch:
            leaders.add(i + 1)          # rule 3: fall-through start
            leaders.add(ins.target)     # rule 2: branch target
    leaders.discard(len(insns))         # past-the-end is not an instruction
    ordered = sorted(leaders)
    blocks = []
    for k, start in enumerate(ordered):
        end = ordered[k + 1] if k + 1 < len(ordered) else len(insns)
        blocks.append(Block(start, end))
    return blocks

Two details in that snippet are worth naming. The fall-through successor of a conditional branch is an instruction index that may not otherwise be a leader, so rule 3 is what creates it. And the index just past the final instruction must be discarded, because a branch at the end of the function produces it and it is not a real position.

The count of blocks is bounded by the number of branches: with b branches there are at most 2b + 1 leaders, since the entry is always one and each branch contributes at most a target and a fall-through, so the block count is at most 2b + 1. A function with n instructions and no branches is a single block, which is why the entry and exit liveness sets of such a function are trivial.

Deriving Edges

Each block’s terminator determines its successors. An unconditional branch has one successor, the block containing its target. A conditional branch has two: the target block and the block that follows in the linear order, which is the fall-through. A return has none. A call is not a terminator in the simple model, even though it transfers control away and back; treating every call as an edge would connect the call site to every function in the program.

Edges are classified by the pair of endpoints. A forward edge goes from a block to one with a higher linear index, a backward edge to a lower one. Backward edges are the raw material of loop detection, but they are not identical to loops: an irreducible control structure can produce backward edges that do not form a single-entry region, and a backward edge in a graph with multiple entries cannot be reduced to a natural loop without node splitting.

A second classification matters for optimization: an edge whose target has more than one predecessor is a merge point. Values that flow into a merge must be reconciled, which is exactly where phi functions appear in SSA form, as described in Minimal SSA Construction from Dominance Frontiers. A block with a single predecessor and a single successor can be merged with either neighbour, which is what block merging passes do to clean up after other transformations.

Dominance, Defined Without a Dataflow Solver

The property that makes CFGs useful for placement decisions is dominance. Block d dominates block b if every path from the entry to b passes through d. Dominance is reflexive and transitive, and the dominators of a block form a chain under the subset relation, so each block except the entry has a unique immediate dominator: the strict dominator that is not dominated by any other strict dominator of b.

The iterative formulation is a forward dataflow problem with intersection as the meet operator. Initialise every block’s dominator set to all blocks except the entry, whose set is itself, then repeatedly set each block’s set to the intersection of its predecessors’ sets plus the block itself, until nothing changes. It converges because the sets only shrink, and it is simple enough to write in a dozen lines, but it can take a number of passes proportional to the loop nesting depth on graphs with long chains.

The Lengauer-Tarjan algorithm computes the same relation in near-linear time using a depth-first spanning tree and a union-find structure with path compression. The insight that makes it fast is that dominance can be characterised in terms of the semidominator, a value computed during the depth-first walk. The practical relevance is that dominator trees get recomputed after nearly every transformation that changes the graph, so the difference between quadratic-in-practice and near-linear matters for compile time on large functions.

The postdominator relation is the mirror image, computed on the reverse graph: p postdominates b if every path from b to the exit passes through p. Control dependence is derived from it. A block y is control dependent on a branch x if some successor of x leads to y along a path on which every node other than x is postdominated by y, while y does not postdominate x itself. The informal reading is that executing y is decided by the branch at x. Exception handlers and speculative motion both need this relation, and neither can be expressed with dominance alone.

Loops as Strongly Connected Components

A loop in the graph sense is a set of blocks that can reach each other. The maximal such sets are the strongly connected components, computable in linear time by Tarjan’s algorithm, which numbers blocks in a single depth-first pass and identifies a component whenever a block’s lowlink equals its discovery index.

The strongly connected components are the starting point, but a component is not the same object as a loop. Once a loop that contains nested loops has been identified, its component already contains the inner loops, and the outer loop as a whole is not a set of blocks that can all reach each other. The natural-loop construction on backward edges is what recovers the nesting. The natural loop of a backward edge from b to h is the set of blocks that can reach b without passing through h, plus h itself, so a nested loop produces its own set nested inside the outer one. When h dominates b, the natural loop is the only loop containing that edge, and it has a unique header. Reducible control flow, which is what structured source languages produce, has the property that every loop has a unique header and every backward edge is dominated by its target. Irreducible flow arises from unrestricted goto, from hand-written assembly, and from some generated code; it requires node splitting to fit the natural-loop model.

Loop nesting is recovered from the header set: loop A is nested inside loop B if the blocks of A are a subset of the blocks of B. The nesting depth of a block is the number of loops containing it, and it is the number that most loop optimizations care about, since a transformation applied at depth d changes the work performed by the enclosing d loops.

Irregularities That Break the Model

The three-rule construction assumes branches have statically known targets. Indirect jumps break that. A computed goto or a tail call through a function pointer has a target that is only known at run time, and the graph must either over-approximate with edges to every possible target or leave the node with an unknown successor set. The first inflates the graph and makes analysis conservative; the second leaves a hole that every pass consuming the graph must account for, either by treating the function as unanalysable or by falling back to a coarser summary. A jump table for a switch is the tractable case: the table enumerates its targets, so the successors are known once the table’s contents are read, and the node has an ordinary, if large, successor set.

Calls are the second irregularity. A call may not return, may return twice in a language with generators, and may transfer control to a handler rather than to the instruction after it. Modelling the call as a terminator with a normal and an exceptional successor is more accurate than ignoring it, but it splits blocks at every call site and inflates the graph.

The third irregularity is that block boundaries are not stable across transformations. Tail duplication splits a block to give a hot path its own copy, block merging fuses a chain, and edge splitting inserts a new block on an edge to give it a unique source or target. Each of these changes the numbering that other passes may have cached, which is why most compilers treat the graph as a mutable structure with explicit invalidation rather than as a derived view of the instruction list.

A fourth, subtler issue is that the linear order of blocks affects the cost of the code even though it does not affect the graph. When both outcomes are equally likely, fall-through is cheaper than a taken branch on every mainstream architecture: the fetch unit continues without a redirect, and the front end does not pay a taken-branch penalty. When a branch is heavily biased the prediction hardware often absorbs the difference, so the layout pass that assigns final addresses is maximising the number of frequently traversed edges that become fall-throughs rather than the total. That problem is a variant of the travelling-salesman path problem on the graph’s edges, which is why block layout is usually solved with a greedy chain builder rather than optimally. The instruction scheduler described in Instruction Scheduling and Its Dependence on the Graph consumes the same edges, but for a different purpose: it needs to know which instructions may be reordered relative to each other, not which ones should sit next to each other in memory.

What the Graph Is For

Every pass that follows operates on this structure. Dataflow analyses iterate over blocks in reverse postorder, which is the order that makes forward problems converge fastest because it visits a block after most of its predecessors. Register allocation builds an interference graph per block and merges across blocks using liveness at boundaries. Inlining decides where to splice a callee by looking at the call block’s predecessors and successors. The graph is not a convenience: it is the object that most of the middle end actually manipulates, and the instruction list is retained mostly so that the graph’s nodes have contents.