控制流图（Control Flow Graph）

2024-06-18 07:53| 来源: 网络整理| 查看: 265

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 then S2: y = 3

上面我们可以看出：只有在S1语句x > 2时，才会执行S2语句，也就是说S2的执行受S1语句的控制(影响)，那么我们就称S1与S2具有控制依赖性。

5.数据依赖性(Data dependencies)：

数据依赖产生于两个访问或修改相同资源的语句。

同样从例子来说明数据依赖性：

1 x = 10 2 y = x + c

从上面我们可以知道：x 值的变化会引起 y 值得变化，那么我们就称 y 依赖于 x，y 与具有数据依赖性。

参考：

控制流图、圈复杂度_spring_willow的博客-CSDN博客_控制流图圈复杂度计算控制流图_百度百科https://en.wikipedia.org/wiki/Control-flow_graphSoftware Engineering | Control Flow Graph (CFG) - GeeksforGeekshttps://en.wikipedia.org/wiki/Dependence_analysis#Control_dependenciesPerl until 循环 | 菜鸟教程

梦不会逃走，逃走的一直都是自己。

——《蜡笔小新》

【本文地址】

公司简介

联系我们