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.



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.


These terms are commonly used when discussing control flow graphs.


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


Full article ▸

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