Control Flow Graph
Subject: Computer and Technology noun /kənˈtroʊl floʊ ɡræf/ 1 definition
- compiler-design
- static-analysis
- compiler-optimization
- graph-theory
-
Definition (noun)
Entry #123 · UpdatedA Control Flow Graph (CFG) is a directed graph representation of all execution paths that a program or subroutine may traverse during runtime. In a CFG, each node represents a basic block—a maximal straight-line sequence of instructions with a single entry point at the beginning and a single exit point at the end—while directed edges denote possible jumps, conditional branches, loops, or fall-through transitions between blocks. Compilers, decompilers, and static analysis tools construct CFGs as an intermediate representation to reason about reachability, dominance, and data flow across every statically possible path, though a standard intraprocedural CFG models potential control transfers within a single routine rather than tracking concrete runtime values or cross-function call targets directly.
Common Forms
Intraprocedural CFG: Models control flow strictly within a single function or procedure from a unique entry node to exit nodes, treating calls to other routines as atomic instructions inside a basic block rather than expanding their internal branches.
Interprocedural CFG (ICFG): Connects individual function CFGs together using call and return edges across a codebase, allowing static analyzers and link-time optimizers to trace execution paths and propagate data-flow facts across function boundaries.
Reducible CFG: A structured graph form in which every loop has a single dominating entry header—characteristic of
if,while, andforconstructs—enabling straightforward loop-nest detection and faster data-flow convergence than irreducible multi-entry graphs produced by arbitrarygotojumps.Exceptional CFG: Augments standard branch and fall-through edges with exceptional control-flow edges from potentially throwing or faulting instructions to matching
catchandfinallyhandler blocks so optimizers preserve error-handling semantics when reordering code.
Example
When Clang/LLVM compiles a function containing an
if (count > 0)branch followed by areturnstatement, it partitions the instructions into basic blocks—an entry block ending in a conditional branch, separate branch-target blocks, and a merge block—linked by directed edges. Running reachability analysis over this CFG lets the optimizer detect and eliminate dead code, such as a logging call placed immediately after an unconditionalreturn, because its block has no path from the entry node.