Control Flow Graph

Also Known As

TL;DR

Explanation

A control flow graph (CFG) is a fundamental data structure in compiler design and static analysis that models all possible execution paths through a program or function. Each node in the graph represents a basic block - a straight-line sequence of instructions with no branches except at the end and no branch targets except at the beginning. Edges connect basic blocks to show how control can flow: a conditional branch creates two outgoing edges, a loop creates a back edge to an earlier block, and a function call may create edges to exception handlers. The CFG has a single entry node (the function's first block) and one or more exit nodes (returns, throws). Compilers construct CFGs after parsing to enable dataflow analysis: reaching definitions, live variable analysis, available expressions, and constant propagation all operate by propagating facts along CFG edges until a fixed point is reached. Optimisations like dead code elimination, loop-invariant code motion, and common subexpression elimination rely on the CFG structure. Static analysers like PHPStan, Psalm, and ESLint plugins build CFGs to detect unreachable code, guarantee return statements exist on all paths, and verify type narrowing persists through conditionals. The CFG also determines basic block ordering for register allocation and instruction scheduling. Cyclomatic complexity - a common code quality metric - is computed directly from the CFG as E - N + 2P, where E is edges, N is nodes, and P is connected components. Understanding CFGs helps developers reason about why analysers report certain warnings and how restructuring conditionals affects tool output.

Diagram

flowchart TD
    ENTRY[Entry Block] --> A[Block A: x = input]
    A --> B{Block B: x > 0?}
    B -->|true| C[Block C: y = x * 2]
    B -->|false| D[Block D: y = 0]
    C --> E[Block E: return y]
    D --> E
    E --> EXIT[Exit Block]
style ENTRY fill:#1f6feb,color:#fff
style EXIT fill:#238636,color:#fff
style B fill:#d29922,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Confusing CFG with AST - the AST represents syntactic structure while the CFG represents execution flow; they serve different purposes.
• Assuming CFG edges only represent explicit goto/jump statements - conditionals, loops, exceptions, and fall-through all create edges.
• Forgetting that unreachable code after return/throw creates disconnected nodes the analyser flags as dead code.
• Not recognising that complex nested conditionals create exponentially more CFG paths, increasing analysis time and cyclomatic complexity.
• Believing CFGs only matter for compiled languages - interpreted languages like PHP and JavaScript use CFGs in their static analysers and JIT compilers.

Avoid When

• Explaining code structure to beginners who need to understand syntax before execution flow.
• Analysing trivial functions with linear flow where CFG complexity adds no insight.
• Working in contexts where the runtime provides no CFG-based tooling and manual analysis is impractical.

When To Use

• Building or extending static analysers that need to track dataflow through branches and loops.
• Debugging why an analyser reports unreachable code or missing return paths.
• Measuring and reducing cyclomatic complexity in complex functions.
• Understanding compiler optimisations that rely on basic block structure.

Code Examples

// PHP: complex control flow creates tangled CFG
function process($value) {
    if ($value > 0) {
        if ($value > 100) {
            return 'large';
        } else {
            $result = 'medium';
        }
    } else {
        if ($value < -100) {
            return 'very negative';
        }
        // Missing return path! PHPStan detects via CFG analysis
        $result = 'small negative';
    }
    echo 'processing'; // Unreachable after some paths
    return $result;    // $result may be undefined on some paths
}

// PHP: clear control flow with explicit paths
function process($value): string {
    if ($value > 100) {
        return 'large';           // Exit edge from this block
    }
    if ($value > 0) {
        return 'medium';          // Exit edge from this block
    }
    if ($value < -100) {
        return 'very negative';   // Exit edge from this block
    }
    return 'small negative';      // Final exit - all paths covered
}
// CFG has clear structure: 4 condition blocks, 4 exit edges, no dead code

Tags

Related Terms

References

• https://en.wikipedia.org/wiki/Control-flow_graph
• https://en.wikipedia.org/wiki/Basic_block
• https://llvm.org/docs/Passes.html
• https://craftinginterpreters.com/representing-code.html