输入源程序的逻辑可能是非常复杂的，是编译器设计者无法预知的。语法分析阶段获得的是输入程序的语法结构，而语义处理阶段获得的是符号表以及IR。但是，仅依据这些信息仍不足以让编译器一窥输入源程序的全貌。无论是HIR还是LIR，它们为编译器提供的关于输入程序逻辑结构的信息是非常有限的。那么，编译器到底希望得到哪些信息呢？回答这个问题并不容易，在理想情况下，编译器希望得到关于输入源程序的一切信息，无论是有用或无用。不过，这仅仅是一种理想状态。根据一些经典编译器的设计经验，发现有两类信息对于优化是非常重要的，即数据流、控制流。这里，笔者简单解释一下相关概念。

数据流(data flow)。就是用于描述数据处理相关的全局信息，例如，一个变量在哪些IR指令中被赋值，而在哪些IR指令中被引用等。这些信息对于优化算法是非常重要的，编译器通常在实施优化前，必须分析获得这些信息，否则讨论优化可能是不安全的。很多算法都是基于数据流分析的结果进行代码优化的。

控制流(control flow)。主要用于描述程序结构的相关信息。一般来说，控制流分析将完成两项工作：循环结构分析、流图构造。在编译技术中，有些优化算法是基于循环结构分析实现的，例如，循环优化、循环倒置等。除此之外，构造流图供数据流分析及其他优化算法使用也是非常必要的。由于Neo Pascal不涉及循环优化算法，所以并不需要进行循环结构分析。本节的重点就是讲解流图的概念及其构造。

流图(flow graph)。是程序结构的有向图描述形式。它的形式与程序流程图类似，却又比程序流程图的结构更为清晰明了。与程序流程图相比，流图更关注程序的结构描述。例如，流图关注的是选择结构有几个分支及其流向，可能并不关心具体哪个是真（假）分支。在实际编译器中，流图只是优化、代码生成的一种辅助工具，通常，可能并不需要显式地输出，因此，很多时候，流图对程序员而言是完全透明的。图7-1是一段IR实例，它的流图描述形式如图7-2所示。下面，结合图7-2介绍流图的主要组成。

基本块(basic block)。在流图中，使用方框表示一系列动作，通常将其称为“基本块”。基本块内的动作是自上而下顺序执行的，不存在任何跳转。有时，为了更突出程序结构的特点，也可以将基本块退化为一个结点形式。

图7-1 IR实例

边(edge)。在流图中，使用有向线来表示程序结构中的分支。一般来说，可以将跳转语句分为两类：无条件跳转语句、条件跳转语句。因此，基本块的出度一般不会超过2，而入度却是不定的。当基本块末语句是条件跳转语句时，该基本块的出度必定为2。在其他情况下，基本块（除出口基本块外）的出度必定是1。

图7-2 与图7-1对应的流图形式

入口基本块(entry basic block)。流图必定存在一个唯一的入口，即程序首语句所在的基本块，入口基本块的入度必定是0。不过，值得注意的是，入度为0的基本块却不一定是入口基本块。实际上，通常将入度是0的基本块（除入口基本块外）称为不可到达代码。也就是说，在任何情况下，它们都无法被调用执行。

出口基本块(exit basic block)。出口基本块的数量与源语言的特点有着密切的关系。由于源语言的不同，流图的出口基本块的数量是不同的。例如，C语言的函数允许使用return语句直接返回，因此，C语言函数的出口与实际return语句的数量有关。而标准Pascal语言并不允许使用return语句返回，这种情况下，Pascal的出口就是唯一的。根据一些经典编译器设计的经验，人们发现当流图的出口不唯一时，许多优化问题就变得非常复杂了。为了降低优化的实现难度，通常会为流图添加一个冗余基本块，并且令原图中所有的出口基本块添加一条流向该冗余基本块的边。这样，该冗余基本块就成了流图的唯一出口。有些书将该冗余基本块称为“扩展基本块”(extended basic block)。由于Pascal函数的出口是唯一的，所以并不需要建立扩展基本块，这里就不再深入讨论。(www.daowen.com)

流图主要描述的对象是IR或目标代码。理论上讲，一张流图或许可以描述一个完整的程序。不过，却很少进行这样的尝试。通常，编译器是以过程为单位生成流图的，因为这样构造得到的流图规模适中，便于其他优化算法使用。

事实上，构建流图的关键就在于划分基本块。下面，就来看看如何将一个IR序列划分成若干基本块。

划分基本块可以遵循如下算法：

(1)首先，确定基本块的入口语句。其判定条件如下：

1)程序第一个语句。

2)任意能够由条件跳转语句或无条件转移语句转移到的语句。

3)紧跟在跳转语句后面的语句。

当一个语句满足上述三个判定条件之一时，则该语句即为基本块入口语句。

(2)从某个入口语句开始，直到下一个入口语句（但不含该入口语句）或程序结束语句之间的所有语句即组成了一个基本块。

完成基本块划分后，只需根据基本块末的语句的类型构建流图的边即可。如果块末语句为无条件跳转时，则构造一条指向目的标号所在基本块的边。如果块末语句不是跳转语句时，则构造一个指向后继语句所在的基本块的边即可。这个过程并不复杂，读者参考图7-2、图7-3分析构造过程，这里不再详细讲述。