Control Flow Graph

How a control flow graph is built

The source you write is a tree — nested if, while, and for statements that a parser turns into an abstract syntax tree. But the tree describes nesting, not flow. A break, a goto, an early return, or an exception unwinds across the tree shape and leaves no trace in it. To reason about what actually executes after what, a compiler lowers the program to a flat list of instructions and rebuilds the flow explicitly. That rebuilt structure is the control flow graph (CFG): a directed graph whose nodes are basic blocks and whose edges are the possible transfers of control between them.

A basic block is a maximal straight-line sequence with one way in and one way out. Once execution enters at the top, it runs every instruction to the bottom — no jump lands in the middle, and no branch happens except as the very last instruction. That single-entry, single-exit property is the whole point: a block can be treated as one indivisible unit, so an analysis that holds at the top of a block holds for all of it.

Finding the blocks is a two-pass leader algorithm. A leader is the first instruction of a block, and there are exactly three rules for what counts as one:

• The first instruction of the program is a leader.
• Any instruction that is the target of a jump or branch is a leader.
• Any instruction that immediately follows a jump or branch is a leader (the fall-through after a conditional).

Each block then runs from one leader up to — but not including — the next leader. The second pass adds edges: a block ending in an unconditional jump gets one edge to its target; a block ending in a conditional branch gets two (taken and fall-through); a block ending in return gets an edge to the synthetic exit node. The result is a graph with a single distinguished entry and (conventionally) a single exit, both of which simplify the data-flow analyses that run on top.

Why optimizers need the graph

Almost every interesting compiler optimization is a data-flow analysis: it computes a fact at every program point by propagating facts along edges until nothing changes (a fixed point). Liveness analysis (which variables are still needed), reaching definitions (which assignment last wrote a variable), available expressions (what has already been computed), constant propagation — all of them are iterative passes over the CFG's edges. The graph is the substrate the equations run on.

• Dead-code elimination. A block with no predecessors can never run; delete it. A computed value never read downstream is dead; delete it.
• Loop optimizations. Once you can name a loop (a back-edge plus its body), you can hoist loop-invariant code, unroll, or vectorize.
• Register allocation. Liveness over the CFG produces the interference graph that graph-coloring allocators color.
• SSA construction. Static single assignment places φ-functions exactly at the dominance frontier — a property defined purely on the CFG.

Dominators, post-dominators, and loops

Two definitions unlock most of the analysis. Block A dominates B if every path from the entry to B passes through A. The entry dominates everything; a loop header dominates the entire loop body, because there is no way into the body without first reaching the header. Symmetrically, A post-dominates B if every path from B to the exit passes through A — useful for sinking code and for control-dependence.

The dominance relation forms a tree (each block has exactly one immediate dominator), and from it you detect loops. A back-edge is an edge n → h where h dominates n. The natural loop of that back-edge is h together with every block that can reach n without passing through h. That single rule is how a compiler turns a tangle of jumps into named, nestable loops it can transform with confidence.

When you reach for a CFG

• Any global (within-function) optimization. If a pass needs to know what reaches a point from multiple branches, it needs the CFG.
• Static analysis and linters. Unreachable-code warnings, definite-assignment checks ("variable used before set"), and "function may not return a value" all run on the CFG.
• Coverage and profiling. Edge-coverage and block-coverage instrumentation place counters on CFG edges and blocks.
• Decompilation and reverse engineering. Tools like IDA, Ghidra, and Binary Ninja recover a CFG from raw machine code to display the familiar block-and-arrow view.

You do not need a full CFG for purely local, peephole-style rewrites inside one block, and you reach past it to a call graph when the question is interprocedural ("does inlining B into A pay off?"). The CFG is the intraprocedural workhorse in between.

CFG vs other program representations

	AST	Control Flow Graph	Call graph	Data-flow / SSA	PDG
Node	Syntax construct	Basic block	Function	Definition / use	Statement
Edge	"is child of"	Possible control transfer	"calls"	"def reaches use"	Control + data dep
Scope	One function	One function	Whole program	One function	One function
Captures goto / break	No	Yes	n/a	Yes (built on CFG)	Yes
Captures loops directly	By nesting only	By back-edges	By recursion cycles	Via CFG	By control edges
Primary use	Parsing, type-check	Global optimization	Inlining, WPO	SSA, optimization	Slicing, parallelism

The AST and CFG are complementary, not competing: front ends parse into an AST, then lower to a linear IR and build the CFG for the middle end. The program dependence graph (PDG) layers data dependences on top of the CFG and is the basis for program slicing and automatic parallelization.

What the numbers actually say

• Construction is linear. The leader scan and edge-adding pass are each O(n) in the instruction count, so building the CFG itself is never the bottleneck.
• Edges stay sparse. Most blocks have one or two successors (fall-through, conditional). In practice E ≈ 1.5–2 · V, so the graph is sparse and the O(V + E) graph algorithms behave like O(V).
• Dominators are near-linear. The classic iterative dominator algorithm is O(V²) worst case; Lengauer–Tarjan runs in O(E · α(E)) — effectively linear — and is what production compilers ship (GCC's dominance pass and LLVM's Semi-NCA both belong to this lineage), while Cooper–Harvey–Kennedy's simpler iterative version is fast enough in practice to beat Lengauer–Tarjan on the graph sizes real programs produce.
• Blocks are short. Empirically, average basic block length is only a handful of instructions before a branch breaks the straight line — the long-standing rule of thumb is that roughly one in every four to six instructions is a branch in typical code, which is exactly why branch prediction matters so much to hardware.
• Critical-edge splitting adds nodes. An edge from a block with multiple successors to a block with multiple predecessors is a "critical edge"; SSA and some optimizations split it by inserting an empty block, which can grow the CFG by a noticeable fraction on branchy code.

JavaScript implementation

Building a CFG from a flat list of instructions, where a branch instruction names its target indices:

// Each instr: { op, target, fallthrough }
//   op: 'jump' | 'branch' | 'return' | 'op'
//   branch has both target and fallthrough; jump has target only.
function buildCFG(instrs) {
  const n = instrs.length;
  const isLeader = new Array(n).fill(false);
  isLeader[0] = true;                          // rule 1: program start

  for (let i = 0; i < n; i++) {
    const ins = instrs[i];
    if (ins.op === 'jump' || ins.op === 'branch') {
      if (ins.target != null) isLeader[ins.target] = true;  // rule 2: jump target
      if (i + 1 < n) isLeader[i + 1] = true;                // rule 3: fall-through
    } else if (ins.op === 'return') {
      if (i + 1 < n) isLeader[i + 1] = true;
    }
  }

  // Map each instruction index to the block id (= its leader index).
  const blockOf = new Array(n);
  let cur = -1;
  for (let i = 0; i < n; i++) {
    if (isLeader[i]) cur = i;
    blockOf[i] = cur;
  }

  // Collect blocks and wire successor edges from each block's last instr.
  const blocks = new Map();                    // leader index -> { id, instrs, succ }
  for (let i = 0; i < n; i++) {
    const id = blockOf[i];
    if (!blocks.has(id)) blocks.set(id, { id, instrs: [], succ: new Set() });
    blocks.get(id).instrs.push(i);
  }

  for (const b of blocks.values()) {
    const last = instrs[b.instrs[b.instrs.length - 1]];
    const lastIdx = b.instrs[b.instrs.length - 1];
    if (last.op === 'jump') {
      b.succ.add(blockOf[last.target]);
    } else if (last.op === 'branch') {
      b.succ.add(blockOf[last.target]);                     // taken
      if (lastIdx + 1 < n) b.succ.add(blockOf[lastIdx + 1]); // fall-through
    } else if (last.op !== 'return') {
      if (lastIdx + 1 < n) b.succ.add(blockOf[lastIdx + 1]); // straight-line
    }
    // 'return' has no successor (edge to a synthetic EXIT if you add one)
  }
  return blocks;
}

// Reachable-block set from the entry — the basis of dead-block elimination.
function reachable(blocks, entry = 0) {
  const seen = new Set([entry]);
  const stack = [entry];
  while (stack.length) {
    const b = blocks.get(stack.pop());
    for (const s of b.succ) if (!seen.has(s)) { seen.add(s); stack.push(s); }
  }
  return seen;                                 // any block not in seen is dead
}

The trick that makes this clean is using each block's leader index as its stable id, and the blockOf map to translate an instruction-level jump target into the block it lands in. Dead-block elimination then falls out as a graph reachability query: anything the DFS in reachable never visits has no path from the entry and can be removed.

Python implementation

The same algorithm, plus a depth-first walk that detects back-edges — the first step of loop recognition:

from collections import defaultdict

def build_cfg(instrs):
    """instrs: list of dicts with op in {jump, branch, return, op},
       branch/jump carry an integer 'target' index."""
    n = len(instrs)
    leader = [False] * n
    leader[0] = True
    for i, ins in enumerate(instrs):
        if ins['op'] in ('jump', 'branch'):
            t = ins.get('target')
            if t is not None:
                leader[t] = True
            if i + 1 < n:
                leader[i + 1] = True
        elif ins['op'] == 'return' and i + 1 < n:
            leader[i + 1] = True

    block_of, cur = [0] * n, -1
    for i in range(n):
        if leader[i]:
            cur = i
        block_of[i] = cur

    succ = defaultdict(set)
    blocks = defaultdict(list)
    for i in range(n):
        blocks[block_of[i]].append(i)
    for bid, idxs in blocks.items():
        last_idx = idxs[-1]
        last = instrs[last_idx]
        if last['op'] == 'jump':
            succ[bid].add(block_of[last['target']])
        elif last['op'] == 'branch':
            succ[bid].add(block_of[last['target']])
            if last_idx + 1 < n:
                succ[bid].add(block_of[last_idx + 1])
        elif last['op'] != 'return' and last_idx + 1 < n:
            succ[bid].add(block_of[last_idx + 1])
    return dict(blocks), succ

def back_edges(succ, entry=0):
    """Find back-edges via DFS: an edge to a node still on the recursion
       stack (gray) is a back-edge — the seed of a natural loop."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = defaultdict(int)
    edges = []

    def dfs(u):
        color[u] = GRAY
        for v in succ.get(u, ()):
            if color[v] == GRAY:
                edges.append((u, v))      # back-edge u -> v
            elif color[v] == WHITE:
                dfs(v)
        color[u] = BLACK

    dfs(entry)
    return edges

Note that back_edges here uses the DFS-tree definition (an edge to a gray ancestor). That is a fast over-approximation; the precise definition requires dominators, since a back-edge is properly an edge to a block that dominates its source. On reducible CFGs — which structured languages without arbitrary goto always produce — the two definitions coincide.

Variants worth knowing

Interval / reducible analysis. A CFG is reducible if its edges split cleanly into forward edges (a DAG) plus back-edges. Code from structured control flow is always reducible; arbitrary goto spaghetti may be irreducible, which forces node-splitting or controlled-node-duplication to analyze. Most real code is reducible, so many compilers fast-path it.

Extended basic blocks. A tree of blocks with a single entry but possibly several exits. Some local optimizations operate on these larger regions to get more context than a single block without paying for full global analysis.

Single-exit (post-dominator) form. Adding a unique synthetic exit node and routing every return to it makes post-dominance well-defined and simplifies control-dependence computation.

Program dependence graph (PDG). Overlays data-dependence edges on the CFG's control structure. It is the representation behind program slicing ("which statements can affect this value?") and several auto-parallelization techniques.

Sea of nodes. The IR in HotSpot's C2 JIT and the V8 / Graal lineage dissolves the rigid block structure into a graph where only true dependences pin instructions in place, scheduling blocks late. It trades the tidy CFG for more freedom to reorder.

Common bugs and edge cases

• Forgetting the fall-through leader. The instruction after a conditional branch is a leader even though nothing jumps to it. Miss rule 3 and two logical blocks get glued into one, corrupting every downstream analysis.
• Dangling edges after deleting a block. When dead-code elimination removes a block, every predecessor's branch target into it must be rewired or removed — otherwise an edge points into nothing. Always update predecessors when you delete a node.
• Unsplit critical edges. Inserting a copy "on an edge" (common in SSA out-of-SSA lowering) is only safe on an edge whose source has one successor or whose target has one predecessor. On a critical edge you must split first or you place the copy on a path that shouldn't run it.
• Irreducible loops. The DFS-stack back-edge test misclassifies edges in irreducible graphs. If your input can contain arbitrary jumps (assembly, obfuscated binaries), use real dominators, not the DFS shortcut.
• Exceptions and implicit edges. A call that can throw has an edge to its handler; an out-of-bounds access can branch to a trap. Omitting these "exceptional" edges makes a block look like it always falls through when it might not — a classic source of unsound optimization.
• Infinite loops break post-dominance. A loop with no exit never reaches the exit node, so post-dominators are undefined unless you add a virtual edge from the loop to exit. Compilers add this edge specifically to keep the analysis total.