Control-flow graph

Deep dive

How it works

In: a flat instruction list in which jumps name their targets · Out: basic blocks with successor and predecessor lists, and a reverse postorder · State: none (a function of the list) · Cost: O(n) to build, order of 25 ns per instruction measured below; RPO O(blocks + edges)

1. Leaders: mark instruction 0, the target of every jump/branch, and the instruction after every jump, branch or return.
2. Blocks: each block runs from one leader up to (excluding) the next. Store start offsets only; a block is ins[start[b]..start[b+1]].
3. Edges, from the block's last instruction: jmp t gives [block(t)]; br t gives [block(t), fallthrough]; ret gives none; anything else falls through to the next block.
4. Predecessors: invert the successor lists in the same pass.
5. Order: iterative depth-first search from the entry; the reversed postorder lists every block before its non-back-edge successors. Blocks not in it are unreachable.

B0: op ; br L          B0 --> B3, B1
B1: op ; jmp E         B1 --> B5
B2: op   (dead)        B2 --> B3        (no edge into B2)
B3: L: op ; br L       B3 --> B3, B4    (self loop)
B4: op                 B4 --> B5
B5: E: ret

Code

#[derive(Clone, Copy, Debug)]
pub enum Ins {
    Op,          // straight-line instruction
    Jmp(usize),  // unconditional jump to instruction index
    Br(usize),   // conditional: jump to index if true, else fall through
    Ret,
}

pub struct Cfg {
    pub start: Vec<usize>,     // block b covers ins[start[b]..start[b+1]]
    pub succ: Vec<Vec<u32>>,
    pub pred: Vec<Vec<u32>>,
}

impl Cfg {
    pub fn build(code: &[Ins]) -> Cfg {
        let n = code.len();
        // 1. Leaders: first instruction, every jump target, every instruction after a jump/ret.
        let mut leader = vec![false; n + 1];
        leader[0] = true;
        for (i, ins) in code.iter().enumerate() {
            match *ins {
                Ins::Jmp(t) | Ins::Br(t) => { leader[t] = true; leader[i + 1] = true; }
                Ins::Ret => leader[i + 1] = true,
                Ins::Op => {}
            }
        }
        // 2. Blocks are the runs between leaders; map instruction index -> block id.
        let mut start = Vec::new();
        let mut block_of = vec![0u32; n];
        for i in 0..n {
            if leader[i] { start.push(i); }
            block_of[i] = (start.len() - 1) as u32;
        }
        start.push(n);
        // 3. Edges come from each block's last instruction only.
        let nb = start.len() - 1;
        let mut succ = vec![Vec::new(); nb];
        let mut pred = vec![Vec::new(); nb];
        for b in 0..nb {
            let last = start[b + 1] - 1;
            let fall = (start[b + 1] < n).then(|| block_of[start[b + 1]]);
            let out: Vec<u32> = match code[last] {
                Ins::Jmp(t) => vec![block_of[t]],
                Ins::Br(t) => { let mut v = vec![block_of[t]]; v.extend(fall.filter(|&f| f != v[0])); v }
                Ins::Ret => vec![],
                Ins::Op => fall.into_iter().collect(),
            };
            for &s in &out { pred[s as usize].push(b as u32); }
            succ[b] = out;
        }
        Cfg { start, succ, pred }
    }

    /// Reverse postorder from the entry (block 0), iterative; unreachable blocks are absent.
    pub fn rpo(&self) -> Vec<u32> {
        let mut seen = vec![false; self.succ.len()];
        let mut post = Vec::with_capacity(self.succ.len());
        let mut stack = vec![(0u32, 0usize)]; // (block, next successor index)
        seen[0] = true;
        while let Some(&mut (b, ref mut k)) = stack.last_mut() {
            if let Some(&s) = self.succ[b as usize].get(*k) {
                *k += 1;
                if !seen[s as usize] { seen[s as usize] = true; stack.push((s, 0)); }
            } else {
                post.push(b);
                stack.pop();
            }
        }
        post.reverse();
        post
    }

    /// Edges from a multi-successor block to a multi-predecessor block.
    pub fn critical_edges(&self) -> Vec<(u32, u32)> {
        let mut v = Vec::new();
        for (a, ss) in self.succ.iter().enumerate() {
            if ss.len() > 1 {
                v.extend(ss.iter().filter(|&&s| self.pred[s as usize].len() > 1).map(|&s| (a as u32, s)));
            }
        }
        v
    }
}

Tested with asserts on the 9-instruction example above (leaders, successors, predecessors, RPO, critical edges, duplicate-edge branch) and run on a 20 M-instruction synthetic program.

Complexity and constants

• Build: O(n) in instructions (three passes over the code, one over the blocks); RPO: O(blocks + edges).
• Ins is 16 bytes here; the CFG itself is two Vec<u32> per block plus 8 bytes of start. Real compilers store the terminator in the block and keep instructions elsewhere.
• Measured on one Apple-silicon Mac, release build, 20 M synthetic instructions (about 1 in 5 branches, so about 9.6 M blocks, far denser than real code): about 0.5 s (order of 25 ns/instruction) when jump targets are within 64 instructions, and 85-130 ns/instruction when targets are uniformly random over the whole program. The gap is cache misses on leader and block_of. Not profiled further, but with two Vecs per block the allocator is the likely remaining cost.
• RPO on the random-target graph (6.7 M reachable blocks) took 1-2 s: pointer chasing through succ, one cache miss per edge.

Efficiency

• Cost: about 25 ns per instruction to build (20 M synthetic instructions in about 0.5 s, release build, Apple-silicon Mac, jump targets within 64 instructions); 85-130 ns per instruction when targets are random (measured above). RPO on 6.7 M reachable blocks took 1-2 s. Memory is a u32 start per block plus its edge list. Bound: memory latency (cache misses on leader/block_of, one per edge in RPO) and allocation.
• Levers:
  • flat edge storage (CSR) instead of a Vec per block — removes an allocation and about 24 bytes of header per list (see Implementation notes) — any CFG; a fixed [u32; 2] works until switches appear
  • cache RPO and derived data — computed once per CFG edit instead of once per pass — pipelines with many passes
  • bitsets for visited and dataflow sets — one bit per block instead of a bool or hash entry — large functions
  • lazy predecessors; drop unreachable blocks early — skips work no pass needs — analyses that only walk forward
  • blocks hold index ranges into separate instruction storage — passes reorder instructions without touching the graph — optimizers
• Naive → standard → state of the art:
  • Vec<Vec<usize>> successors, recomputed for each pass · allocation per block, cache misses per edge
  • leader pass, CSR edges, cached RPO · about 25 ns per instruction measured above
  • terminator-as-data, instructions in separate storage, incremental invalidation as in LLVM and rustc MIR · cost proportional to what changed (design claim, not measured)

Implementation notes

• Terminator as data: keep the last instruction's kind as an enum (Jmp, Br, Ret, Switch, Trap) so edges can be read off without scanning instructions.
• Layout: start: Vec<u32>, successors in CSR form, and block ids as u32; a Vec<Vec<_>> costs about 24 bytes of header and an allocation per list.
• Instructions in separate storage: blocks hold index ranges; passes can then reorder or delete instructions without touching the graph.
• Entry block has no predecessors: if the source can jump to instruction 0 (a loop at the top), add an empty entry block first. Dominator and SSA algorithms assume it.
• Invalidate on edit: cache the CFG, RPO and everything derived from them, and drop them when a pass changes a terminator. Stale predecessor lists are a classic source of miscompiles.
• Splitting critical edges: insert an empty block M on A -> B (A has several successors, B several predecessors), retarget A's terminator to M, and make M jump to B. Needed to place phi-elimination copies and spill code on one edge only.

Pitfalls

• Empty code and jumps past the end: build above indexes block_of[t]; a target equal to n or an empty program panics. Validate targets first.
• Unreachable blocks keep edges into reachable ones (B2 -> B3 above), so they show up in pred and wreck phi arity and dominator computation. Filter by RPO or delete them.
• Fallthrough after a branch whose target is the next instruction gives two identical edges; deduplicate, or phi inputs get counted twice.
• Implicit edges: exceptions, setjmp, indirect jumps (jmp *reg, switch) and computed gotos need explicit edges or a conservative "any address-taken block" set; recovering them from binaries is its own problem, see CFG recovery.
• Calls normally do not end a block; if they can unwind, an exception edge makes them a terminator.
• Recursive DFS overflows the stack on long chains of blocks; use an explicit stack as above.
• Irreducible loops (a cycle with several entries) have no single header; algorithms that assume natural loops from back edges (loop optimizations) must detect and skip or split them.

Variants and alternatives

In production

• Compilers: LLVM IR functions are lists of basic blocks, each ending in exactly one terminator, with predecessors()/successors() derived from them (LangRef). rustc's MIR is a graph of basic blocks with terminators, with cached predecessors and reverse postorder (guide). Cranelift keeps a ControlFlowGraph of block predecessors and successors.
• Binary analysis and security: angr recovers a CFG from machine code (CFGFast, docs); Ghidra exposes basic-block models over a program (API).
• GPU shader compilers: SPIR-V modules are CFGs of blocks whose merge instructions (OpSelectionMerge, OpLoopMerge) mark structured constructs (spec).
• Compilers that start from bytecode or machine code (see bytecode compilation, disassembly) commonly find block starts with the leader pass above.

Implementations

Sources

• Frances E. Allen, Control Flow Analysis, ACM SIGPLAN Notices 5(7), 1970. paper
• Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools (2nd ed.), Addison-Wesley 2006, section 8.4 "Basic Blocks and Flow Graphs" (leader algorithm).
• Cooper, Harvey, Kennedy, A Simple, Fast Dominance Algorithm, Rice University technical report, 2001 (iteration in reverse postorder).
• Cytron, Ferrante, Rosen, Wegman, Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM TOPLAS 13(4), 1991. paper
• LLVM Language Reference, "Well-Formedness" and "Terminator Instructions". docs
• rustc dev guide, "MIR". docs