A directed graph that represents the possible execution order and transfer of control between basic blocks or statements in a program; nodes typically represent basic blocks and edges represent jumps, branches, and fall-through transitions.

Principle

Model program execution as transitions between control regions so that reachability, dominance, liveness, and other control-centric analyses can be formulated as graph problems over nodes and edges representing flow of the program counter.

Demonstration

A function with an if/else and a loop maps to a CFG where a conditional node has two outgoing edges to the 'then' and 'else' blocks; the loop introduces a back edge from loop tail to loop header, making the CFG cyclic.

Misapplication

Using a CFG to reason about data dependencies (e.g., assuming value definitions flow along CFG edges) or assuming that the presence of an edge implies a runtime transition will always occur with the same frequency—both lead to incorrect optimization or analysis.

Consequence

Correct use supports optimizations like dead-code elimination, loop transformation, inlining decisions (when combined with interprocedural info), and verification tasks such as proving reachability or absence of certain control paths.

Reversal

Treat the program purely as a dataflow of values (computational graph) where control constructs are encoded as data transformations; this inversion replaces explicit control edges with data-based guards and can obscure control-centric properties.

Boundary

Applies to intra-procedural representations by default; interprocedural control flow requires extension (call/return edges, interprocedural CFG). It does not encode semantic side effects, concurrency interleavings, or precise timing unless augmented.

Semantic Tension

Tension exists between CFG and computational/dataflow graphs: CFG emphasizes possible program counter transfers (control), whereas dataflow graphs emphasize propagation of values; conflating them conflates distinct analyses.

Synthesis

A control-flow graph is the program abstraction that makes possible-transitions between program regions explicit as directed edges; it is the fundamental structure for analyses and transforms that depend on the shape of control rather than on pure data movement.