In computer science, a control-flow graph (CFG) is a representation, using graph notation, of all paths that might be traversed through a program during its execution. The control-flow graph was discovered by Frances E. Allen, who noted that Reese T. Prosser used boolean connectivity matrices for flow analysis before.

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

Definition 
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.

Because of its construction procedure, in a CFG, every edge A→B has the property that:
 outdegree(A) > 1 or indegree(B) > 1 (or both).

The CFG can thus be obtained, at least conceptually, by starting from the program's (full) flow graph—i.e. the graph in which every node represents an individual instruction—and performing an edge contraction for every edge that falsifies the predicate above, i.e. contracting every edge whose source has a single exit and whose destination has a single entry. 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.

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 a graph property useful in optimization.

If a subgraph is not connected from the subgraph containing the entry block, that subgraph is unreachable during any execution, and so is unreachable code; under normal conditions it can be safely removed.

If the exit block is unreachable from the entry block, an infinite loop may exist. Not all infinite loops are detectable, see Halting problem. A halting order may also exist there.

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.

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. The dominator tree 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

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.  A block may be a loop header for more than one loop.  A loop may have multiple entry points, in which case it has no "loop header".

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.

Reducibility 

A reducible CFG is one with edges that can be partitioned into two disjoint sets: forward edges, and back edges, such that:

 Forward edges form a directed acyclic graph with all nodes reachable from the entry node.
 For all back edges (A, B), node B dominates node A.

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. To produce irreducible graphs, statements such as GOTO are needed.  Irreducible graphs may also be produced by some compiler optimizations.

Loop connectedness 
The loop connectedness of a CFG is defined with respect to a given depth-first search tree (DFST) of the CFG. This DFST should be rooted at the start node and cover every node of the CFG.

Edges in the CFG which run from a node to one of its DFST ancestors (including itself) are called back edges.

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.

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

Inter-procedural Control Flow Graph 

While Control Flow Graphs represent the control flow of a single procedure, Inter-procedural Control Flow Graphs represent the control flow of whole programs.

See also
 Abstract syntax tree
 Flowchart
 Control-flow diagram
 Control-flow analysis
 Data-flow analysis
 Interval (graph theory)
 Program dependence graph
 Cyclomatic complexity
 Static single assignment
 Compiler construction
 Intermediate representation

References

External links

The Machine-SUIF Control Flow Graph Library
GNU Compiler Collection Internals
Paper "Infrastructure for Profile Driven Optimizations in GCC Compiler" by Zdeněk Dvořák et al.

Examples
Avrora – Control-Flow Graph Tool

Compiler construction

Application-specific graphs
Modeling languages
제어 흐름 그래프(, CFG)는 프로그램이 실행 중에 횡단할 수 있는 모든 경로를 그래프 표기법을 사용하여 표현한 것이다.

CFG는 많은 컴파일러 최적화와 정적 프로그램 분석 툴에서 핵심 요소이다.

정의 
CFG에서 그래프의 각 노드(node)는 기본 블록 (basic block)을 표현한다. 즉, 점프가 없는 코드의 직선 조각이다. (점프는 블록의 시작과 끝을 나눈다.) 방향성의 엣지(edge)들은 제어 흐름에서 점프를 나타낸다. 대부분의 경우에 흐름 그래프가 진입하는 엔트리 블록과 모든 제어 흐름이 떠나는 "종료 블록"이라는 두 특별히 고안된 블록을 지닌다.

이것의 구조 절차 때문에 (사소하지 않은 CFG에서) 모든 A→B 엣지는 다음의 속성을 갖는다.
 출력 차수 (outdegree) (A) > 1 또는 진입차수(indegree) (B) > 1 (또는 둘 다).
그러므로 CFG는 적어도 개념적으로는 프로그램의 흐름 그래프(모든 노드가 각각의 명령어를 표현하는 그래프)에서 시작하고, 위의 술어를 조작하는 모든 엣지 수축(edge contraction)을 수행함으로써 (즉, 소스가 단일 종료를 갖거나 목적지가 단일 엔트리인 모든 엣지를 줄이며) 얻어질 수 있다. 이 수축 기반 알고리즘은 CFG 구조를 시각화하는데 도움을 준다는 점 외에는 실용적인 중요성은 없다.

예시 
다음의 코드 부분을 보자.
 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
위에서, 우리는 4개의 기본 블록을 갖는다. A는 0부터 1, B는 2부터 3, C는 4 그리고 D는 5다. 특히, A의 경우 엔트리 블록이며, D의 경우 종료 블록이다. 그리고 라인 4와 5는 점프 대상이다. 이 코드의 그래프는 A부터 B, A부터 C, B부터 D 그리고 C부터 D까지의 엣지를 갖는다.

도달 가능성 
도달 가능성은 최적화 시에 유용한 그래프 속성이다.

만약 서브그래프가 엔트리 블록에 포함된 서브 그래프와 연결되지 않았다면, 이 서브그래프는 실행 중에 도달할 수 없으며, 일반 조건에서 안전하게 제거될 수 있다.

만약 종료 블록이 엔트리 블록에서 도달 불가능하다면, 무한 루프가 존재할 수 있다. 정지 문제처럼 모든 무한 루프가 탐지되는 것은 아니다. 또한 거기에 정지 순서도 존재할 수 있다.

도달 불가능한 코드와 무한 루프는 프로그래머가 명시적으로 그것을 코딩하지 않았어도 생길 수 있다. 상수 전파와 상수 폴딩 같은 점프 스레딩에 의한 최적화는 엣지를 CFG에서 제거함으로써 여러 기본 블록을 하나로 붕괴시킬 수 있다.

지배 관계 
만약 모든 경로에서 블록 N에 도달하는 엔트리가 블록 M을 거쳐야 한다면 블록 M은 블록 N을 지배한다.

역방향으로, 만약 블록 N에서 종료 까지의 모든 경로가 블록 M을 거쳐야 한다면, 블록 M은 블록 N을 후지배(postdominate)한다.

다른말로 해서, M은 엔트리부터 N까지의 모든 경로에서 마지막으로 지배한다. 각 블록들은 고유한 즉각적 (immediate) 지배관계를 갖는다.

비슷하게, 즉각적 지배와 즉각적 후지배도 존재한다.

지배자 트리 (dominator tree)는 지배 관계를 묘사하는 보조적인 데이터 구조이다. 만약 블록 M이 블록 N을 즉각적으로 지배한다면, 블록 M부터 블록 N까지 원(arc)이 생긴다. 이 그래프는 각 블록이 고유한 즉각적 지배자를 갖은 이후로 트리가 된다. 이 트리는 엔트리 블록부터 갈라져 나온다. Lengauer-Tarjan's algorithm을 사용해 효율적으로 계산될 수 있다.

후지배자 트리 (postdominator tree)는 지배자 트리의 유사체이다. 이 트리는 종료 블록부터 갈라져 나온다.

특별한 엣지 
백 엣지 (back edge)는 이미 DFS 동안 만났던 블록에 대한 포인터이다. 백 엣지는 대표적인 루프이다.

크리티컬 엣지 (critical edge)는 소스 블록을 떠나는 유익한 엣지도 아니고, 목적 블록에 도달하는 유일한 엣지도 아니다. 이러한 엣지들은 반드시 쪼개져야 한다. 즉, 다른 엣지들에 대한 영향 없이 계산을 삽입하기 위하여 새로운 블록이 엣지 중간에 생성되어야 한다.

불가능한 엣지 (impossible edge 또는 fake edge)는 종료 블록이 모든 블록들을 후지배하는 속성을 보존하기 위해 단독으로 추가된 엣지이다. 이것은 영원히 지나갈 수 없다.

루프 관리 
루프 헤더(종종 루프의 엔트리 포인트라고 불리는)는 루프를 형성하는 백 엣지의 대상인 지배자이다. 루프 헤더는 루프 몸체의 모든 블록들을 지배한다. 블록은 하나 이상의 루프를 위한 루프 헤더이다. 루프 헤더가 없는 경우 루프는 여러 엔트리 포인트를 가질 수 있다.

블록 M이 여러 들어오는 엣지들의 지배자이며, 몇몇은 백 엣지라고 가정해 보자. (즉, M은 루프 헤더이다.) M을 Mpre 와 Mloop라는 두 블록으로 쪼개는 것은 여러 최적화된 경로에 이득이 된다. M의 내용과 백 엣지들은 Mloop가 되며, 나머지 엣지들은 Mpre가 되고, Mpre 에서 Mloop 까지의 새로운 엣지가 삽입된다. (즉, Mpre는 Mloop의 즉각적인 지배자이다.) 시작할 때, Mpre는 비어 있겠지만, loop-invariant code motion 같은 경로들은 이것을 덧붙일 수 있다. Mpre는 loop pre-header라고도 불리며, Mloop 는 루프 헤더가 될 것이다.

같이 보기 
 순서도
 제어 흐름 다이어그램
 제어 흐름 분석
 데이터 흐름 분석

노트

외부 링크 
 The Machine-SUIF Control Flow Graph Library
 GNU Compiler Collection Internals
 Paper "Infrastructure for Profile Driven Optimizations in GCC Compiler" by Zdeněk Dvořák et al.
 예시
 http://compilers.cs.ucla.edu/avrora/cfg.html

컴파일러
컴파일러 구성
제어 흐름 분석
모델링 언어
그래프의 응용