Control-flow graph

A control-flow graph models possible transfers of control between program regions. A conventional construction divides code into basic blocks: maximal straight-line sequences whose instructions execute consecutively, with control entering at the first instruction and leaving at the last. Directed edges connect a block to each block that can execute next; conditional branches therefore have multiple outgoing edges, while joins have multiple incoming edges. A distinguished entry node and, in many representations, an exit node make procedures easier to analyze. The graph describes syntactic possibility rather than a guarantee that every path is feasible for some input: mutually exclusive conditions, array bounds, exceptions, or runtime values may eliminate paths. Compiler intermediate representations commonly retain this graph alongside instructions and control-flow metadata.¹²

Building the graph begins by identifying leaders, forming basic blocks, and connecting each block to its possible successors. Leaders typically include the first instruction, branch targets, and instructions following a branch; call and return conventions require additional treatment. Once built, the graph supports reachability, dead-code detection, dominator computation, loop recognition, and data-flow analysis. A node dominates another when every path from entry to the latter passes through the former; the corresponding postdominance relation reasons backward from exit. These relations help compilers place computations, eliminate redundant work, and construct static single-assignment form, whose placement of φ-functions relies on dominance frontiers.³⁴ Graph structure also supplies a basis for branch prediction, instruction scheduling, and complexity measures such as cyclomatic complexity.

Real programs require control-flow graphs to represent more than ordinary conditional branches. A loop creates a back edge, a switch creates several successors, and short-circuit Boolean operators can introduce hidden branches. Exceptional control flow may connect an instruction to a handler whose transfer is not visible as a normal fall-through edge; asynchronous signals, setjmp/longjmp, coroutines, and indirect jumps create further uncertainty. Interprocedural analyses extend the model across procedure boundaries, often with call and return edges, while context-sensitive methods distinguish different calling situations. At machine-code level, indirect branches and computed jump tables can make graph recovery incomplete, especially when code and data are difficult to distinguish. Consequently, tools may mark edges as unknown, conservative, exceptional, or infeasible rather than pretending that the graph is exact.¹²

Control-flow graphs are also central to security analysis and program understanding, not only to optimization. Static analyzers traverse them to detect unreachable code, missing checks, tainted-data routes, and paths that can reach dangerous operations; test generators use path conditions to seek inputs that exercise selected edges. A graph can be reducible when its cycles have a structured single-entry form, as in ordinary source-level loops, but irreducible graphs can arise from unstructured jumps or low-level transformations and may require node splitting or specialized algorithms. The graph is not the same as a call graph: a control-flow graph describes transfers within a procedure or a chosen interprocedural model, whereas a call graph describes which procedures may invoke which others. Its granularity also matters: instruction-level graphs preserve detail, while block-level graphs are smaller and faster to analyze.¹³

Basic block

A maximal straight-line sequence of instructions with one entry point and one exit point.

Dominator

A node that lies on every path from the graph entry to a specified node.

Back edge

An edge that returns to an earlier region in a traversal, commonly representing a loop.

Cyclomatic complexity

A graph-based measure of independent control-flow paths, commonly calculated as E − N + 2P.

Static single-assignment form

An intermediate representation in which each variable version is assigned once, with φ-functions merging control-flow alternatives.