控制流圖

控制流圖（control-flow graph）簡稱CFG，是计算机科学中的一種形式化表示，利用數學中图的表示方式，標示计算机程序執行過程中可能經過的所有路徑。控制流圖是由法兰·艾伦所建立，他提出曾將邻接矩阵用在流分析上。

CFG是許多編譯器最佳化及靜態程序分析工具中的核心技術。
定義
控制流圖中的每個顶点都對應一個程式基本塊，也就是一段沒有分支指令，也沒有分支目的（如goto標籤）的程式碼。基本塊的開始是分支目的，而基本塊會以分支為結束。控制流程中會用有向邊來表示分支。在大部份的表示中，會有兩個特殊指定的基本塊：進入程式塊（entry block），指進入此控制流圖時，第一個遇到的程式碼；結束程式塊（exit block），指所有流程在結束時都會執行的程式碼。

因為控制流圖的生成方式，在控制流圖中，每一個有向邊A→B會有以下的性質：
: outdegree(A) > 1 或 indegree(B) > 1（也可能同時成立）。

以概念上來看，控制流圖可以由程式的完整流程圖產生。先畫出一個控制流圖，其中每一個頂點對應程式中的一個指令。接著對每一個邊進行边收缩，即將不符合上述條件的邊（即outdegree(A) = 1 且 indegree(B) = 1的邊）和相鄰的邊整合。這個收縮演算法在實務上沒有什麼重要性，但可以以視覺的方式說明控制流圖的產生方式。而實務上產生控制流圖的方式會更有效率的掃描程式中的基本塊來達成：

• 前進邊會形成有向无环图，其中所有的節點都是可到達的節點。
• 針對所有倒退邊（A, B），節點B支配節點A。

结构化编程程式語言常會設計讓產生的所有控制流圖都是可规约控制流圖，常見的流程控制指令 (例如IF、FOR、WHILE、BREAK、CONTINUE）都會產生可规约控制流圖。若要讓控制流圖不可规约，需要加上Goto之類的指令。在一些編譯器的最佳化過程中，可能會出現不可规约控制流圖。

迴圈連結度
控制流圖的迴圈連結度（loop connectedness）是以控制流圖的給定深度优先搜索樹（DFST）為準。DFST需以啟始節點為根，包括控制流圖中的所有節點。

若控制流圖中的邊，是從一個節點到DFST中的祖先節點，此邊為倒退邊。

迴圈連結度是指控制流圖中沒有迴圈的路徑中，可以找到倒退邊的最大數量。若是可规约控制流圖，迴圈連結度和選擇的DFST無關。

迴圈連結度可以用來說明数据流分析的時間複雜度。

相關條目

• 抽象語法樹
• 流程图
• 控制流程圖
• 控制流分析
• 数据流分析

*
*

• 循環複雜度
• 静态单赋值形式
• 編譯器
• 中間語言

參考資料
外部連結
*[https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15745-s02/public/doc/cfg.html The Machine-SUIF Control Flow Graph Library]
*[https://gcc.gnu.org/onlinedocs/gccint/Control-Flow.html GNU Compiler Collection Internals]
Paper "[http://www.ucw.cz/~hubicka/papers/proj/node6.html#SECTION02420000000000000000 Infrastructure for Profile Driven Optimizations in GCC Compiler] " by Zdeněk Dvořák et al.*

;例子
*[http://compilers.cs.ucla.edu/avrora/cfg.html Avrora – Control-Flow Graph Tool]