控制流圖（Control Flow Graph）

1.定義

百度百科：

控制流圖(Control Flow Graph, CFG)也叫控制流程圖，是一個過程或程式的抽象表現，是用在編譯器中的一個抽象資料結構，由編譯器在内部維護，代表了一個程式執行過程中會周遊到的所有路徑。它用圖的形式表示一個過程内所有基本塊執行的可能流向, 也能反映一個過程的實時執行過程。
Frances E. Allen于1970年提出控制流圖的概念。此後，控制流圖成為了編譯器優化和靜态分析的重要工具。           

維基百科：

原文：
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.
譯文：
在控制流圖中，圖中的每個節點代表一個基本塊，即一段沒有任何跳轉或跳轉目标的直線代碼；跳轉目标開始一個塊，而跳轉結束一個塊。有向邊用來表示控制流中的跳轉。在大多數示範中，有兩個特别指定的塊：入口塊，控制通過它進入流程圖；出口塊，所有控制流通過它離開。           

控制流圖的幾種結構：

​

2.特點

• 控制流程圖是過程導向的
• 控制流程圖顯示了程式執行過程中可以周遊的所有路徑
• 控制流程圖是一個有向圖
• CFG 中的邊描述控制流路徑，節點描述基本塊
• 每個控制流圖都存在2個指定的塊：Entry Block(輸入塊)，Exit Block(輸出塊)

3.執行個體

• 例1：

if  A = 10 then
  if B > C
     A = B
  else A = C
  endif
  endif
print A, B, C            

其控制流圖為：

• 例2：計算整數X和整數Y的最大公約數

int gsd(int x,int y)
{
	int q=x;
	int r=y;
	while(q!=r)
	{
		if (q>r)
			q=q-r;
		else 
			r=r-q;
	}
	return q;
}           

4.控制依賴性(Control dependencies)

Control dependency is a situation in which a program instruction executes if the previous instruction evaluates in a way that allows its execution.           

控制依賴講的是：在某種情況下，一個程式指令的執行依賴于前面指令的執行(在前面某個指令執行後才會執行)。

下面從一個例子來說明控制依賴性：

S1       if x > 2 goto L1
S2       y = 3   
S3   L1: z = y + 1           

上面我們可以看出：隻有在S1語句x <= 2時，才會執行S2語句，也就是說S2的執行僅受S1語句的控制(影響)，那麼我們就稱S1與S2具有控制依賴性。

5.資料依賴性：

資料依賴産生于兩個通路或修改相同資源的語句。

同樣從例子來說明資料依賴性：

1       x = 10
2       y = x + c           

從上面我們可以知道：x 值的變化會引起 y 值得變化，那麼我們就稱 y 依賴于 x，y 與具有資料依賴性。

我的公衆号！

參考：

1. https://blog.csdn.net/spring_willow/article/details/70814214?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161893381516780262592064%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=161893381516780262592064&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-3-70814214.first_rank_v2_pc_rank_v29&utm_term=%E6%8E%A7%E5%88%B6%E6%B5%81%E5%9B%BE
2. https://baike.baidu.com/item/%E6%8E%A7%E5%88%B6%E6%B5%81%E5%9B%BE/5984243?fr=aladdin
3. https://en.wikipedia.org/wiki/Control-flow_graph
4. https://www.geeksforgeeks.org/software-engineering-control-flow-graph-cfg/
5. https://en.wikipedia.org/wiki/Dependence_analysis#Control_dependencies
6. https://www.runoob.com/perl/perl-until-loop.html

夢不會逃走，逃走的一直都是自己。

——《蠟筆小新》