Control flow graph

related topics
{math, number, function}
{line, north, south}
{@card@, make, design}
{system, computer, user}
{car, race, vehicle}

A control flow graph (CFG) in computer science is a representation, using graph notation, of all paths that might be traversed through a program during its execution.

Contents

Overview

In a control flow graph each node in the graph represents a basic block, i.e. a straight-line piece of code without any jumps or jump targets; jump targets start a block, and jumps end a block. Directed edges are used to represent jumps in the control flow. There are, in most presentations, two specially designated blocks: the entry block, through which control enters into the flow graph, and the exit block, through which all control flow leaves.

The CFG is essential to many compiler optimizations and static analysis tools.

Reachability is another graph property useful in optimization. If a block/subgraph is not connected from the subgraph containing the entry block, that block is unreachable during any execution, and so is unreachable code; it can be safely removed. If the exit block is unreachable from the entry block, it indicates an infinite loop (not all infinite loops are detectable, of course. See Halting problem). Again, dead code and some infinite loops are possible even if the programmer didn't explicitly code that way: optimizations like constant propagation and constant folding followed by jump threading could collapse multiple basic blocks into one, cause edges to be removed from a CFG, etc., thus possibly disconnecting parts of the graph.

Terminology

These terms are commonly used when discussing control flow graphs.

Examples

Consider the following fragment of code:

0: (A) t0 = read_num
1: (A) if t0 mod 2 == 0 goto 4
2: (B)   print t0 + " is odd."
3: (B)   goto 5
4: (C) print t0 + " is even."
5: (D) end program

In the above, we have 4 basic blocks: A from 0 to 1, B from 2 to 3, C at 4 and D at 5. In particular, in this case, A is the "entry block", D the "exit block" and lines 4 and 5 are jump targets. A graph for this fragment has edges from A to B, A to C, B to D and C to D.

See also

Notes

Full article ▸

related documents
Dedekind cut
Semi-continuity
Homomorphism
Division ring
Infimum
Cofinality
Ternary numeral system
Iterative method
Principal ideal domain
Elliptic function
Upper and lower bounds
Conjugacy class
Lambert W function
Shannon–Fano coding
Counting sort
ZPP
Pointless topology
Binary space partitioning
Cyclone (programming language)
Multiplication table
Five lemma
Möbius function
Distributivity
Commutator
Intermediate value theorem
Arithmetic function
Banach algebra
Pseudocode
HMAC
Elementary function