Control Flow Graph

A control flow graph (CFG) is a directed graph that represents all paths that might be traversed through a program during its execution. Each node in the graph is a basic block — a maximal sequence of consecutive instructions with a single entry point and a single exit point, containing no internal branches. Each directed edge represents a possible transfer of control from the end of one basic block to the beginning of another. The CFG is the canonical representation of a program's control structure, abstracting away from the surface syntax of the source language to expose the branching, looping, and sequential logic that determines execution paths.

The CFG is constructed from an abstract syntax tree or from an intermediate representation by partitioning instructions into basic blocks and drawing edges between blocks whose execution can follow one another. A conditional branch creates two outgoing edges; a loop creates a cycle; a return statement creates an edge to a special exit node. The resulting graph makes explicit what the linear text of the program obscures: the topology of possible executions.

Basic Blocks and Graph Structure

A basic block is defined by two properties: it has exactly one entry point (the first instruction is either the program entry or the target of some branch) and exactly one exit point (the last instruction is either a branch, a return, or a fall-through to the next block). Within a basic block, instructions execute sequentially and unconditionally. This abstraction is powerful because it collapses the fine-grained sequential structure of the program into a coarse-grained graph of control decisions.

The CFG has a distinguished entry node representing the start of the function and a distinguished exit node representing all return points. Every path from the entry node to the exit node represents a possible execution trace. This graph-theoretic framing makes the CFG amenable to standard algorithms: reachability analysis determines which code is dead; cycle detection identifies loops; dominator analysis finds regions where one block must execute before another.

The construction of a CFG from an AST is not trivial. High-level control structures — "if" statements, "while" loops, "for" loops, "switch" statements — must be lowered into a graph of basic blocks and conditional branches. Each lowering is a design choice that determines the shape of the graph and therefore the efficiency of subsequent analyses. A compiler that lowers a "switch" into a binary search of basic blocks produces a very different CFG from one that lowers it into a jump table.

The CFG in Compiler Optimization

The CFG is the substrate upon which most compiler optimizations are performed. Because the CFG exposes the branching structure of the program, it enables analyses that the AST cannot support efficiently:

Data-flow analysis computes properties at each point in the program — which variables are live, which expressions are available, which definitions reach each use. These analyses are formulated as systems of equations over the CFG, solved by iterative propagation until a fixed point is reached.
Loop optimization identifies natural loops in the CFG (cycles with a single header block dominated by the back edge) and applies transformations: loop invariant code motion, strength reduction, induction variable elimination.
Global code motion moves computations out of frequently executed blocks and into less frequently executed predecessors, guided by profile data that annotates CFG edges with execution frequencies.
Register allocation uses the CFG to determine where variables are live and therefore where they must reside in registers or spill to memory.

The CFG is also the bridge between the AST and lower-level representations. After optimization on the CFG, the compiler may transform it into Static Single Assignment (SSA) form — a variant in which each variable is assigned exactly once, and phi-functions at join nodes merge values from different predecessors. SSA form simplifies many optimizations but requires the CFG as its scaffolding.

CFGs and Emergent Program Behavior

The CFG is not merely a compiler data structure. It is a model of the program's possible behavior. Every path through the CFG is a possible execution; the set of all paths is the program's behavioral envelope. But this envelope is not the same as the program's actual behavior. The CFG overapproximates: it includes paths that are syntactically possible but semantically unreachable — paths guarded by contradictory conditions, paths through loops that never iterate in practice, paths that require inputs no user would provide.

This overapproximation is the source of both the CFG's power and its limitation. It enables conservative analyses that are guaranteed correct for all possible executions, but it also forces conservative optimizations that may miss opportunities present only in the actually-executed subset of paths. Profile-guided optimization attempts to close this gap by annotating the CFG with observed execution frequencies, turning a conservative graph into a weighted one. But the gap between possible and actual behavior is irreducible, and it is the fundamental reason why static analysis cannot fully replace dynamic analysis.

The control flow graph is often treated as a straightforward compilation artifact — a mechanical lowering of the AST into a form suitable for optimization. This view misses the epistemological weight of the CFG. The CFG is a theory of what a program can do, and like all theories, it is both revealing and distorting. It reveals the branching structure that determines execution; it distorts by treating all branches as equally possible, all paths as equally traversable. A compiler that optimizes using the CFG alone is a compiler that optimizes for a program that exists in logical space, not for the program that runs in physical time. The gap between the CFG and the execution profile is not a bug to be closed. It is the boundary between static and dynamic knowledge, and it is where the deepest challenges in program optimization live.