控制流图(Control Flow Graph, CFG)也叫控制流程图，是一个过程或程序的抽象表现，是用在编译器中的一个抽象数据结构，由编译器在内部维护，代表了一个程序执行过程中会遍历到的所有路径。它用图的形式表示一个过程内所有基本块执行的可能流向, 也能反映一个过程的实时执行过程。

Frances E. Allen与1970年提出控制流图的概念。此后，控制流图成为了编译器优化和静态分析的重要工具。

细述

控制流图中每个在图形中的节点代表一个基本块，例如，没有任何跳跃或跳跃目标的直线代码块；跳跃目标以一个块开始，和以一个块结束。定向边缘被用于代表在控制流中的跳跃。在那里，在大部分介绍中，两个特定的设计块：项目块，通过它控制到流图的输入，和编辑块，通过它全面控制流输出。

意义

CFG 能反映出一个过程的许多信息：

是哪一个过程;

一个过程的入口(第一个基本块) 和出口( 最后一个基本块)；

一个基本块的所有可能的下一个基本块( 所有的出口)；

一个基本块的所有可能的上一个基本块( 所有的入口)；

一个基本块所对应的语句表。

对于一个动态CFG 而言, 它还包含下列信息：

当前活动的基本块；

上次执行的基本块；

执行流向，即上次执行的基本块到当前活动基本块之间的连线。

功能

一个CFG 可显示一个过程内各基本块之间的相互关系、动态执行状态、各基本块对应的语句表。此外，还有其他辅助信息，如各基本块执行次数，执行时间等等。

静态结构图

静态结构图为一有向图，如图2所示。图中各节点的序号顺序从1排列。第1个块即为子程序头“Suborutine子程序名”。从一个节点到下一个节点的连线表明其执行的可能顺序，用有箭头的线表示，称为有向线。有向线的起点所对应的块为正要转移的块，而箭头所指的块为将要转向的块。

图1为一过程XYZA的源程序，图2 为与该过程对应的CFG。从图中可以看出，从一个节点画出的有向线有四种情形：(a)指向下一块；(b)指向下一块以后的节点；(c)指向上一个块或上一块以前的块；(d)指向其自身。如图中, 块2到块3为(a)情形，块6到块8为(b)情形，块13到块6为(c) 情形，块12为(d)情形。

每一个块的块号为其标识符。每一块对应一组源程序中的语句。

动态显示图

动态显示图是在静态图的基础上完成的, 它不但能反映源程序的静态结构关系，还能实时地反映动态执行时的轨迹。

在即将执行一个块的第一条语句时“点亮”该块，表明这一块为将要执行的活动基本块，而上一个基本块已经执行完毕，但还没有完全“熄灭”。这完全是为了记住执行轨迹而人为设置的。从上一次执行的基本块到当前活动基本块有一条连线，箭头表示转移方向。这条有向线有别于其他的有向线，用红色标出，称为“活动线”，因为它是当前的执行轨迹。当从当前块转向下一个块时，重新标出活动线，而原先的活动线则恢复为静态连线。

浏览语句表

任何时候都可以浏览图中任一基本块所对应的语句表。

统计信息

由于进入和离开一个基本块的时刻和进入的次数是知道的，所以一个块被执行的次数和执行它所花的时间的总和是可以统计出来的。

举例说明

控制流图CFG是一有向图G = (N, E, nentry, nexit). 其中，N是节点集，程序中的每个语句都对应图中的一个节点；边集E = {\u003c n1,n2 \u003e | n1, n2∈ N且n1执行后，可能立即执行n2}； nentry 和nexit分别为程序的入口和出口节点。它具有唯一的起始结点START和唯一的终止结点STOP。CFG中的每个结点至多只能有两个直接后继。对于有两个直接后继的结点v,其出边具有属性“T”或“F”,并且在CFG中的任意结点N,均存在一条从START经N到达STOP的路径。

绘制要求

程序语句格式化、规范化处理；

识别程序的逻辑行；

根据程序逻辑行之间的控制关系绘制CFG图；

在CFG图上作适当的标记，例如入/出口、真假分支等。

控制和操作

对CFG 控制有两种方式，一是在调用图中用参数选择决定是否要显示CFG，二是在CFG的弹出式菜单中选择参数，决定是否要显示每一步执行轨迹。如果选择否，则仅显示一次静态CFG。否则，详细显示执行轨迹。在CFG中，有控制显示速度的参数，它们是：无延迟；延迟半秒；延迟1秒和延迟3 秒。此外，还有暂停/ 继续开关，用于停下来浏览等。CFG中的控制菜单如图4所示。

参考资料