控制流图

在计算机科学中，控制流图（CFG）是表示，使用图形可能通过一个被遍历所有路径的符号，程序其期间执行。该控制流图是由于法兰·艾伦，谁注意到，里斯T.Prosser的使用布尔连接矩阵用于流动分析之前。

控制流图对于许多编译器优化和静态分析工具都是必不可少的。

在控制流图中的每个节点在所述图形表示基本块，即一个直线片而没有任何跳跃或代码的跳转目标;跳转目标开始一个块，跳转结束一个块。引导边缘被用来表示在跳跃控制流程。在大多数演示中，有两个特别指定的块：入口块，控制通过它进入流图，以及出口块，所有控制流都通过它离开。

由于其构造过程，在控制流图中，每条边A→B都具有以下性质：

出度(A)>1或入度(B)>1（或两者）。

因此，至少在概念上，可以通过从程序的（完整）流程图开始获得CFG，即每个节点代表一条单独指令的图，并对每条边进行边收缩以证伪上述谓词，即收缩每条边的源有一个出口，其目的地有一个入口。这种基于收缩的算法没有实际意义，除了作为理解CFG构造的可视化辅助工具外，因为可以通过扫描基本块，直接从程序更有效地构造CFG。

环头（有时也被称为入口点的循环的）是支配其是环成形后边缘的目标。循环头控制循环体中的所有块。一个块可以是一个以上循环的循环头。一个循环可能有多个入口点，在这种情况下它没有“循环头”。

假设块M是一个支配者，有几个传入边，其中一些是后边（所以M是一个循环头）。将M分成两个块Mpre和Mloop对多次优化传递是有利的。M的内容和后边移动到Mloop，其余边移动以指向Mpre，并插入从Mpre到Mloop的新边（因此Mpre是Mloop的直接支配者）。一开始，Mpre将是空的，但是像循环不变代码运动这样的传递可以填充它。Mpre被称为looppre-header和Mloop将是循环头。

可约CFG的边可以分为两个不相交的集合：前边和后边，这样：

• 前向边形成一个有向无环图，所有节点都可以从入口节点到达。
• 对于所有后边(A,B)，节点B支配节点A。

结构化编程语言通常被设计为它们生成的所有CFG都是可约化的，并且常见的结构化编程语句（如IF、FOR、WHILE、BREAK和CONTINUE）生成可约化图。要生成不可约图，需要诸如GOTO之类的语句。一些编译器优化也可能产生不可约图。

控制流图的环路连通性是相对于CFG的给定深度优先搜索树(DFST)定义的。这个DFST应该以起始节点为根，覆盖CFG的每个节点。

控制流图中从节点到其DFST祖先之一（包括其自身）的边称为后边。

环连通性是在CFG的任何无环路径中找到的xxx数量的后边缘。在可约CFG中，回路连通性与选择的DFST无关。

循环连通性已被用于推理数据流分析的时间复杂度。

控制流图表示单个过程的控制流，过程间控制流图表示整个程序的控制流。