在本小节中，将讨论Neo Pascal的流图构造算法。经过前面的讲解，读者已经知道构造流图的关键就在于分析基本块的入口。根据先前的分析，算法的逻辑是比较明确的，而实现的难度也应该相对较低。

不过，在编译过程中，构造流图的次数将是非常可观的，并不是通常认为的一次或者几次。实际上，任何优化算法都是针对某种或者几种特定的情景进行分析与优化的。然而，各种优化算法的执行必定存在先后次序。后续的优化算法执行完毕后，可能导致代码情景发生一定变化。这种情况下，有可能为先前己执行完毕的某些优化算法创造了新的条件。一般而言，优化算法需要经过多次迭代，直至达到一个相对稳定的状况。在此过程中，由于代码情景的不断变化，经常需要重新构造流图。因此，编译器设计者不得不考虑流图构造算法的性能。

Neo Pascal的流图构造算法如程序7-1所示。

程序7-1 DFA.cpp

在Neo Pascal中，笔者并没有设置独立的控制流分析模块，而是将流图构造算法置于数据流分析模块中。下面，来详细分析流图构造算法的源代码实现。

判定基本块入口是本算法的关键所在，不过，这并不是算法的难点。难点在于如何在一遍扫描中完成基本块的识别及块间关系的分析。实际上，使用两遍扫描分别完成这两项工作是非常简单的。不过，这却不是一种高效的方案。那么，一遍扫描完成流图分析的难点何在呢？当跳转语句的目的标号出现在跳转语句之后，算法就很难获取两者之间的关系。Neo Pascal采用了一种回填的机制，即实现了一遍扫描构造流图的算法。整个程序主要由三部分组成：遍历IR列表、回填基本块后继关系、回填基本块的前趋关系。

第8～61行：这个循环主要用于遍历IR列表，根据IR的操作符，判断基本块的入口。这里，Neo Pascal设置了一张二维表opti_Tbl，这张表中记录了各种IR操作符在各类优化算法中所需执行的动作，也就是“处理方案”。无论是构造流图或者是其他优化算法，它们的工作对象都是IR。通常，算法需要对IR操作符进行判断，并执行相应的处理方案。下列程序就是Opti_Tbl的声明形式，而该表的初始化值请参见Opti_Tbl.h文件，这里就不再逐一列出。

【声明7-3】

第11、12行：以IR操作符为关键字检索处理方案表，检索成功时，则返回相应的Opti_Tbl结构，否则返回null。这里需要注意一点，从设计的初衷来说，Opti_Tbl表的记录与IR操作符是一一对应的，也就是说，检索永远不会失败。但事实上，有些优化算法根据需要只为每一大类操作符设置一个表项，以便将一些雷同的操作符归类处理。因此，需要考虑检索失败的情况。(www.daowen.com)

第13行：根据检索得到的处理方案的eJmpType属性，完成相应的处理动作。eJmpType属性用于描述IR的跳转情况，其可能的取值包括：None、Lbl、CondJmp、NonCondJmp。在流图构造算法中，需要关心的IR操作符主要是3类，即标号、条件跳转、无条件跳转。至于其他的任何IR操作符都不是算法所关注的，因为它们不可能是基本块的入口，所以其他的IR操作符相应的eJmpType取值为None，表示无需处理这类指令，直接跃过即可。

第15行：根据eJmpType的取值，分别进行相应的处理。

第17～33行：处理标号类型IR。标号是基本块的可能入口。除第一行是标号IR的情况之外，出现标号就意味着其上一行IR应该就是某个基本块的结束，标号本身又是新基本块的开始。而这两个基本块的关系也非常明确，即前者是后者的前趋。不过，值得注意的是，需要记录标号及其所标识的基本块的序号关系（登记在Lbl Block表中），以便处理以该标号为目的的跳转语句。

第34～58行：处理跳转类型IR。在Neo Pascal中，包括JMP、JNT、JT、JE 1。实际上，区别无条件跳转、条件跳转的目的就是确定基本块之间的关系。由于Neo Pascal的过程（函数）是不可能以跳转类型IR结束的，因此出现跳转语句就意味着一个基本块的结束，而其后的一句IR就是一个新基本块的入口。这两个基本块的关系就依赖于IR的跳转类型，如果是无条件跳转，那么这两个基本块之间就可能不存在关系（除非后者的首行IR正好是跳转的目标标号）。如果是条件跳转，则前者将是后者的前趋基本块。当然，对于跳转类型IR的另一个处理动作就是建立跳转IR所在基本块与跳转目的基本块的关系。这一过程需要考虑两种情况，即向前跳转、向后跳转。向前跳转的情况比较容易，由于算法是顺序遍历IR，所以目的标号必定已经识别，并登记在Lbl Block表中，只需检索获取标号对应的基本块序号建立关系即可。而向后跳转的情况复杂一些，由于无法预知目标标号所在的基本块，因此，仅能将其记录在ReWrite表中，以便遍历后续程序回填相应的关系。当然，在不考虑效率的情况下，也可以将此过程分为两遍处理。

第62～68行：主要用于处理最末一个基本块。因为最末一个基本块的结束可能无法通过标号或者跳转标识，一般需要在遍历完毕后进行特殊处理。

第70～71行：遍历ReWrite表回填所有DownFlow信息。此时，已经不需要考虑目的标号不存在等情况。即使是输入源程序存在一定的错误，应该已经在语义分析阶段完成出错处理了。任何优化算法都是建立在IR列表绝对正确的前提下讨论的。

第73～75行：根据基本块的DownFlow集合的信息，填写相应的UpFlow集合。笔者觉得这是一个非常简单的处理过程。当然，可以将其集成在整个IR遍历过程中完成，但那样做可能会使问题变得稍复杂。

第77行：将该过程（函数）的流图放到流图集合中。前面已经说过，分析算法是以过程（函数）为单位构造流图，因此，一个完整的程序通常可以存在若干张流图。