控制流图

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

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

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

假设块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无关。

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

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