Skip to main content
Definition Website Computer and Technology

Control Flow Graph

Subject: Computer and Technology noun /kənˈtroʊl floʊ ɡræf/ 1 definition

  1. Definition (noun)

    Entry #123 · Updated

    A 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, and for constructs—enabling straightforward loop-nest detection and faster data-flow convergence than irreducible multi-entry graphs produced by arbitrary goto jumps.

    • Exceptional CFG: Augments standard branch and fall-through edges with exceptional control-flow edges from potentially throwing or faulting instructions to matching catch and finally handler 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 a return statement, 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 unconditional return, because its block has no path from the entry node.