Control-Flow Graphs and the Dominance Relation

A statement after an unconditional return is unreachable in a way anyone can see. A statement after a call to a function that always throws is unreachable in a way that requires knowing the callee. A statement in a catch block whose try body cannot throw anything the handler catches is unreachable in a way that requires knowing the type system. The control-flow graph is the structure that turns “unreachable” from a visual judgement into a reachability question.

From syntax to basic blocks

A basic block is a maximal sequence of statements with one entry and one exit: control enters at the top, leaves at the bottom, and cannot branch into the middle. The standard construction scans the linearised statement list and marks leaders. The first statement is a leader. Any statement that is the target of a branch is a leader. Any statement immediately following a branch is a leader. Each leader starts a block, and the block extends to the statement before the next leader.

The edges are where the language shows through. A conditional branch contributes two edges, one to the taken target and one to the fallthrough. A switch contributes one edge per case plus a default, and languages with fallthrough, such as C and Go’s explicit fallthrough, may add edges between adjacent cases. A loop contributes a back edge. A break, continue, goto, or labelled jump contributes an edge to its target, which may cross block and function boundaries in languages that allow it.

Short-circuit operators are easy to get wrong. a && b is not a single expression node for flow purposes; it is a branch. b is evaluated only when a is true, so the graph needs a block for a, a conditional edge to the block for b, and a join. The same applies to ||, the ternary operator, optional chaining, and null-coalescing assignment. A CFG built by treating the whole expression as one node may be correct for some dataflow questions and wrong for any question about which subexpression executes.

Generators and coroutines add edges that are not textual. A yield suspends and later resumes, so the statement after it is reachable from the resume point, not from the yield itself. A CFG that ignores this models the function as straight-line code and may report the code after a yield as reachable when it is never resumed, or the reverse. Explicitly modelling suspend and resume as edges is the accurate option; ignoring them and disabling reachability checks inside generators is the cheap one.

Exceptions are edges too

In a language with exceptions, almost every statement can transfer control to a handler. A call can throw, an allocation can fail, an array index can be out of bounds, and a division can trap. If these edges are omitted, the handler looks unreachable. If every statement gets an edge to every enclosing handler, the graph becomes dense and precision collapses.

Real analyzers use a middle ground. Calls get edges to handlers that can catch the declared or inferred exception types. Operations that cannot throw under the language semantics get none. A finally block is modelled as a copy on every exit path, or as a subroutine with its own entry and exit, depending on whether the analysis needs to reason about the finally body once or many times. The choice changes the graph size substantially: duplicating a finally body across ten exits produces ten copies.

Java is instructive because its specification defines unreachable statements syntactically, not semantically. The compiler must reject a statement that cannot be reached by the rules in the language specification, and those rules deliberately ignore runtime values in most positions. The body of while (false) { ... } is a compile-time error in Java, because the specification treats a constant-false condition as making the body unreachable, while if (false) { ... } is permitted because the rule for if only asks whether the statement itself is reachable. That asymmetry is a language design decision, and a linter that applies a uniform semantic definition will disagree with the compiler about which code is legal.

Dominators describe which block must execute

Reachability says a block can execute. Dominance says a block must execute on every path to another block. Block A dominates block B if every path from entry to B passes through A. Every block dominates itself, entry dominates everything reachable, and the relation forms a tree once immediate dominators are chosen: the immediate dominator of B is the unique dominator closest to B.

The classic computation is a forward dataflow analysis with sets of blocks. The entry block’s dominator set is itself; every other block starts with the set of all blocks; the transfer function intersects the dominator sets of all predecessors and adds the block itself. Iterating to a fixpoint yields the full relation. The set-based version is simple and quadratic in the worst case, which is acceptable for functions of ordinary size.

The Cooper-Harvey-Kennedy algorithm is the usual replacement. It processes blocks in reverse postorder, which is close to a topological order for reducible flow, and represents dominator sets implicitly through immediate dominators. Each pass intersects the immediate dominators of already-processed predecessors, and convergence is fast in practice. The same reverse-postorder ordering is what makes many dataflow analyses converge quickly, as discussed in Monotone Dataflow and Fixpoint Convergence.

def dominators(blocks, succ, pred, entry):
    dom = {b: set(blocks) for b in blocks}
    dom[entry] = {entry}
    changed = True
    while changed:
        changed = False
        for b in blocks:
            if b == entry:
                continue
            in_sets = [dom[p] for p in pred[b]]
            new = set.intersection(*in_sets) | {b} if in_sets else {b}
            if new != dom[b]:
                dom[b] = new
                changed = True
    return dom

Dominance is the foundation for two things a linter needs. The first is identifying unreachable code precisely: a block with no path from entry is unreachable, and a block that is reachable but whose only predecessor is dominated by a return is also dead, which the graph expresses as a missing edge rather than a special case. The second is placing a check where it is guaranteed to run. A rule that wants to insert a guard at a merge point can use the immediate dominator to find the latest block that executes on all paths, which is also how SSA construction places phi nodes using the dominance frontier.

The graph is an approximation, and that is the point

A CFG is built from syntax plus a model of the language’s control transfers. Every omission in that model becomes a wrong answer. Omitting exception edges makes handlers look dead. Omitting the edge from a noreturn call makes the code after it look live. Omitting the implicit edge from a constructor to a superclass constructor makes initialisation order analyses wrong. Including edges that cannot occur makes live code look reachable and hides real dead code.

The noreturn case is a good example of the dependency on interprocedural information. Whether a call returns is a property of the callee, so a per-function CFG cannot know it unless the front end propagates an annotation or a summary. Languages and libraries provide such annotations, and analyzers that respect them get sharper reachability; analyzers that do not are conservative in the safe direction for dead-code reports but may miss genuine unreachable code after a call that always panics.

Irreducible flow is the other structural limit. Languages with unrestricted goto permit loops with multiple entry points, which have no single header block. Dominance still computes correctly, but algorithms that assume natural loops, such as the classic loop optimisations, need an extra node-splitting step. For a linter, the practical consequence is that any rule phrased in terms of “the loop header” must handle the irreducible case or restrict itself to languages and constructs where reducibility is guaranteed.

Finally, the graph is per function, while the bugs are often not. A function that is never called has a perfectly reachable CFG, and dead-code analysis at the function level will not flag it. That requires the call graph, which is a different structure with a different set of approximation problems, covered in Interprocedural Summaries and Context Sensitivity. The graph also says nothing about which combinations of branches can occur together; that is the correlation question taken up in Path Sensitivity and Branch Correlation.