##  [Control-Flow Graph](/control-flow-graph-0) 

 Definition

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

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

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

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

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

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

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

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

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.