控制流图（Control Flow Graph）

深碍√TFBOYSˉ_ 2023-01-14 14:59 251阅读 0赞

### 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.
    译文：
    在控制流图中，图中的每个节点代表一个基本块，即一段没有任何跳转或跳转目标的直线代码；跳转目标开始一个块，而跳转结束一个块。有向边用来表示控制流中的跳转。在大多数演示中，有两个特别指定的块：入口块，控制通过它进入流程图；出口块，所有控制流通过它离开。

控制流图的几种结构：

![e6894c529e158296c77ae8b0c371a736.png][]

### 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

其控制流图为：

![a9d4c742993b28b9a11c82037a78271e.png][]

*  例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;
    }

其控制流图为：

![721d4cea8cbeff0552076a91d1b6d605.png][]

### 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][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][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][https_en.wikipedia.org_wiki_Control-flow_graph]
4.  [https://www.geeksforgeeks.org/software-engineering-control-flow-graph-cfg/][https_www.geeksforgeeks.org_software-engineering-control-flow-graph-cfg]
5.  [https://en.wikipedia.org/wiki/Dependence\_analysis\#Control\_dependencies][https_en.wikipedia.org_wiki_Dependence_analysis_Control_dependencies]
6.  [https://www.runoob.com/perl/perl-until-loop.html][https_www.runoob.com_perl_perl-until-loop.html]

> 梦不会逃走，逃走的一直都是自己。
> 
> ——《蜡笔小新》

[e6894c529e158296c77ae8b0c371a736.png]: /images/20221022/d0a8aeff9fe843a89c94029c0eb53269.png
[a9d4c742993b28b9a11c82037a78271e.png]: /images/20221022/c4b509a5838649049d9f4052d38908db.png
[721d4cea8cbeff0552076a91d1b6d605.png]: /images/20221022/a19b88dbee4a4c5cb06b532eb2c7dd2c.png
[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]: 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
[https_baike.baidu.com_item_E6_8E_A7_E5_88_B6_E6_B5_81_E5_9B_BE_5984243_fr_aladdin]: https://baike.baidu.com/item/%E6%8E%A7%E5%88%B6%E6%B5%81%E5%9B%BE/5984243?fr=aladdin
[https_en.wikipedia.org_wiki_Control-flow_graph]: https://en.wikipedia.org/wiki/Control-flow_graph
[https_www.geeksforgeeks.org_software-engineering-control-flow-graph-cfg]: https://www.geeksforgeeks.org/software-engineering-control-flow-graph-cfg/
[https_en.wikipedia.org_wiki_Dependence_analysis_Control_dependencies]: https://en.wikipedia.org/wiki/Dependence_analysis#Control_dependencies
[https_www.runoob.com_perl_perl-until-loop.html]: https://www.runoob.com/perl/perl-until-loop.html