Control flow graph

Control flow graph
Simplified control flowgraphs[1]

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.

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.

Example

Consider the following fragment of code:

```0: (A) t0 = read_num
1: (A) if t0 mod 2 == 0
2: (B)   print t0 + " is even."
3: (B)   goto 5
4: (C) print t0 + " is odd."
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.

Reachability

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.

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.

Domination relationship

A block M dominates a block N if every path from the entry that reaches block N has to pass through block M. The entry block dominates all blocks.

In the reverse direction, block M postdominates block N if every path from N to the exit has to pass through block M. The exit block postdominates all blocks.

It is said that a block M immediately dominates block N if M dominates N, and there is no intervening block P such that M dominates P and P dominates N. In other words, M is the last dominator on all paths from entry to N. Each block has a unique immediate dominator.

Similarly, there is a notion of immediate postdominator : Analogous to immediate dominator.

The dominator tree is an ancillary data structure depicting the dominator relationships. There is an arc from Block M to Block N if M is an immediate dominator of N. This graph is a tree, since each block has a unique immediate dominator. This tree is rooted at the entry block. Can be calculated efficiently using Lengauer-Tarjan's algorithm.

A postdominator tree is analogous to the dominator tree. This tree is rooted at the exit block.

Special edges

For practical reasons, it is necessary to introduce some artificial kinds of edges or to process differently some kinds of edges.

A back edge is an edge that points to a block that has already been met during a depth-first (DFS) traversal of the graph. Back edges are typical of loops.

A critical edge is an edge which is neither the only edge leaving its source block, nor the only edge entering its destination block. These edges must be split: a new block must be created in the middle of the edge, in order to insert computations on the edge without affecting any other edges.

An abnormal edge is an edge whose destination is unknown. Exception handling constructs can produce them. These edges tend to inhibit optimization.

An impossible edge (also known as a fake edge) is an edge which has been added to the graph solely to preserve the property that the exit block postdominates all blocks. It cannot ever be traversed.

Loop management

A loop header (sometimes called the entry point of the loop) is a dominator that is the target of a loop-forming back edge. The loop header dominates all blocks in the loop body.

Suppose block M is a dominator with several incoming edges, some of them being back edges (so M is a loop header). It is advantageous to several optimization passes to break M up into two blocks Mpre and Mloop. The contents of M and back edges are moved to Mloop, the rest of the edges are moved to point into Mpre, and a new edge from Mpre to Mloop is inserted (so that Mpre is the immediate dominator of Mloop). In the beginning, Mpre would be empty, but passes like loop-invariant code motion could populate it. Mpre is called the loop pre-header, and Mloop would be the loop header.

Notes

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Control flow analysis — is a static code analysis technique for determining the control flow of a program. The control flow is expressed as a control flow graph (CFG). For many languages, the control flow of a program is explicit in a program s source code. As a result …   Wikipedia

• Control flow — Not to be confused with Flow control. In computer science, control flow (or alternatively, flow of control) refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are… …   Wikipedia

• Control flow diagram — Example of a so called performance seeking control flow diagram .[1] A control flow diagram (CFD) is a diagram to describe the control flow of a business process, process or program. Contr …   Wikipedia

• Signal-flow graph — A signal flow graph (SFG) is a special type of block diagram[1] and directed graph consisting of nodes and branches. Its nodes are the variables of a set of linear algebraic relations. An SFG can only represent multiplications and additions.… …   Wikipedia

• Graph drawing — This article is about the general subject of graph drawing. For the annual research symposium, see International Symposium on Graph Drawing. Graphic representation of a minute fraction of the WWW, demonstrating hyperlinks. Graph drawing is an… …   Wikipedia

• Control theory — For control theory in psychology and sociology, see control theory (sociology) and Perceptual Control Theory. The concept of the feedback loop to control the dynamic behavior of the system: this is negative feedback, because the sensed value is… …   Wikipedia

• Flow (computer networking) — In a Packet Switching network, a packet flow or traffic flow is a sequence of packets from one particular source (e.g. a computer host, process or class of service) to a single destination (another computer host, multicast group, broadcast domain …   Wikipedia

• Data-flow analysis — is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program s control flow graph (CFG) is used to determine those parts of a program to which a particular value assigned… …   Wikipedia

• Dominator (graph theory) — For Dominating set problem, see Dominating set. In computer science, in control flow graphs, a node d dominates a node n if every path from the start node to n must go through d. Notationally, this is written as d dom n (or sometimes d n). By… …   Wikipedia

• GRaPH-Int — The Genome based Research and Population Health International Network (GRaPH Int) is an international collaboration of experts and researchers focused in the area of population health. The principal goal of the network is to promote the… …   Wikipedia