Control-flow graph

The control-flow graph was conceived by Frances E. Allen,[1] who noted that Reese T. Prosser used boolean connectivity matrices for flow analysis before.

In a control-flow graph each node in the graph represents a basic block, i.e. a straight-line sequence of code with a single entry point and a single exit point, where no branches or jumps occur within the block.

This contraction-based algorithm is of no practical importance, except as a visualization aid for understanding the CFG construction, because the CFG can be more efficiently constructed directly from the program by scanning it for basic blocks.

Unreachable code and infinite loops are possible even if the programmer does not explicitly code them: optimizations like constant propagation and constant folding followed by jump threading can collapse multiple basic blocks into one, cause edges to be removed from a CFG, etc., thus possibly disconnecting parts of the graph.

It is advantageous to several optimization passes to break M up into two blocks Mpre and Mloop.

In the beginning, Mpre would be empty, but passes like loop-invariant code motion could populate it.

A reducible CFG is one with edges that can be partitioned into two disjoint sets: forward edges, and back edges, such that:[5] Structured programming languages are often designed such that all CFGs they produce are reducible, and common structured programming statements such as IF, FOR, WHILE, BREAK, and CONTINUE produce reducible graphs.

The loop connectedness is the largest number of back edges found in any cycle-free path of the CFG.

In a reducible CFG, the loop connectedness is independent of the DFST chosen.

[6][7] Loop connectedness has been used to reason about the time complexity of data-flow analysis.

[6] While control-flow graphs represent the control flow of a single procedure, inter-procedural control-flow graphs represent the control flow of whole programs.