- A+
所属分类:笔记
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</pre>
上面我们可以看出:只有在S1语句x <= 2时,才会执行S2语句,也就是说S2的执行仅受S1语句的控制(影响),那么我们就称S1与S2具有控制依赖性。
5.数据依赖性:
数据依赖产生于两个访问或修改相同资源的语句。
同样从例子来说明数据依赖性:
1 x = 10
2 y = x + c
从上面我们可以知道:x 值的变化会引起 y 值得变化,那么我们就称 y 依赖于 x,y 与具有数据依赖性。
参考:
- 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://en.wikipedia.org/wiki/Control-flow_graph
- https://www.geeksforgeeks.org/software-engineering-control-flow-graph-cfg/
- https://en.wikipedia.org/wiki/Dependence_analysis#Control_dependencies
- https://www.runoob.com/perl/perl-until-loop.html