下载掌阅APP，畅读海量书库
立即打开
在经过一系列的调度变换之后，优化编译器的最终任务是要生成代码。为了能够支持面向不同体系结构的代码生成，优化编译器应该生成一个与上下文无关的代码，并基于此面向不同的编程模型生成代码。显然，抽象语法树（abstract syntax tree）满足这一特定需求。抽象语法树是编译器中使用的一种经典的语法抽象，它将程序的语义表示成树状结构，并基于此带来一些上下文无关的优化机遇。如图2.7所示是图2.5所示代码的抽象语法树。
图2.7 图2.5所示代码的抽象语法树
抽象语法树的相关内容在经典的编译原理教材中都能够找到，本节说明抽象语法树在基于多面体模型的代码生成过程中发挥的作用。根据前面的介绍，多面体模型采用整数集合和仿射函数集合或者这些集合的并集来实现程序的优化。优化编译器中的代码生成就是在这些优化策略的基础上生成更高效的代码。多面体模型的代码生成过程是在给定表示迭代空间的整数集合并集和实现了程序变换的仿射函数集合并集的前提下，生成抽象语法树的过程。如前文所述，在多面体模型中，抽象语法树的代码生成通常也被称为多面体扫描。
根据整数集合和仿射函数等数学抽象生成抽象语法树需要在抽象层次之间构建非常细致的对应关系。在实现这样的对应关系时，优化编译器需要借助一些数据结构来辅助代码生成，这些数据结构形成了一种代码生成过程中的抽象。
无论是以何种调度表示方式来表示调度，多面体模型表示循环嵌套的方式都依赖于仿射函数。在表示语句实例的执行顺序时，仿射函数将一个语句实例映射到一个表述语句执行顺序的多维逻辑时间节点上。关于一维和多维逻辑时间节点的概念，我们将在第4章中进行介绍。抽象语法树的生成过程根据调度表示的仿射函数依次生成循环的边界信息，从抽象语法树的结构上看，应该是一个循环内包含一个或多个语句。因此，在调度变换完成后，一个从多维逻辑时间节点映射到语句的仿射函数或近似仿射函数应该更适合于生成代码，这种变换可以基于仿射函数的求逆操作。
例如，对于式（2-46）所示的union map表示的仿射函数进行求逆操作可得
[（0 ,i, 0,0） →S 1 （ i ）;（1 ,i, 0 ,i ） →S 2 （ i,j ）;（1 ,i, 1,0） →S 3 （ i ）] （2-47）
这种从多维逻辑时间节点映射到语句的映射称为 被执行关系 （executed relation）。被执行关系也是一个仿射函数集合的并集，在式（2-47）中我们并没有标注出该被执行关系的约束。给定一个被执行关系，代码生成过程可以从中提取出每个仿射函数，并根据每个仿射函数的定义域从左到右依次生成循环的边界信息。
更具体地，以式（2-47）中的第一个仿射函数（0 ,i, 0,0） →S 1 （ i ）表示一个从一层 i 循环映射到语句 S 1 （ i ）的函数，代码生成时获取该仿射函数的定义域（0 ,i, 0,0），然后从左到右依次尝试生成循环。当获取第一个维度时得到了一个标量0，代码生成器并不会生成循环，而是会给当前的语句记录一个相对位置；当获取到第二个维度时得到了一个变量 i ，代码生成器就会尝试生成 i 循环。
在根据给定的仿射函数定义域从左至右遍历生成代码的过程中，抽象语法树的树状结构也以从上至下的过程按深度遍历的方式被逐渐构建出来。对于代表仿射函数定义域的一个整数集合，一个维度对应一层循环。在一些情况下，外层循环的循环索引变量会被当作内层循环的编译符号常量来使用和生成。例如，图2.1和图2.3所示的两个例子，在生成内层循环时，外层循环索引变量 i 会被当作编译符号常量，并在生成内层循环的边界时使用。
这些上下文信息对于抽象语法树的生成是必不可少的，优化编译器可以将这些信息存储起来，以便在抽象语法树以深度遍历的方式生成代码时使用。优化编译器需要存储的上下文信息包括两方面：一是当前代码生成结点所必须的编译符号常量的约束，既包括整个程序的符号常量，如图2.1和图2.3原始程序循环边界中的符号常量 M 和 N ，也包括外层循环的循环索引变量上的约束；二是2.5.1节中介绍的被执行关系。在以深度优先的方式生成抽象语法树的过程中，优化编译器在每个维度上都需要维护一个上下文信息，该上下文信息可以用上一个维度的上下文信息进行初始化，并结合当前维度进行扩展。
另外，代码生成过程中还要维护循环索引变量和调度维度之间的关系，这是因为一些复杂的循环变换可能会导致循环索引变量在生成代码时与原始程序中的关系不一致。例如，式（2-14）定义了图2.2两层循环的循环分块变换。在原始程序中，调度的维度（ j,i ）和循环索引变量（ j,i ）之间是一一对应的，但是经过循环变换之后，循环索引变量（ j,i ）和调度维度（ j/ 32 ,i/ 32 ,j,i ）之间却不再是一一对应的关系了，用于调度分块之间的循环维度和循环索引变量之间需要由整数除法运算关联起来。
在具备生成当前循环对应抽象语法树的信息之后，代码生成工具可以创建抽象语法树。与调度树类似，抽象语法树也是由各种不同类型的结点构成的树状结构，这些结点可以是另外一个或多个结点的组合，也可以包含抽象语法树上的表达式。更具体地，抽象语法树上的结点包括：
（1）for 结点 ：抽象语法树上的一个for结点是一个for循环的抽象，它由四个表达式和另外一个结点构成，分别如下。
– 循环索引 （iterator）：循环索引是一个仿射表达式，用于表示循环索引变量。一个循环索引通常用一个字符串表示，如前文描述的 i 、 j 等变量，编译器也可以自定义新的字符串，以区分生成代码前后的循环索引。
– 循环迭代的起始表达式 （init）：循环迭代的起始表达式通常是一个常量或外层循环索引变量的仿射表达式。另外，在循环索引变量存在多个下界时，起始表达式也可以是一个max函数定义的表达式。
– 循环迭代的上界表达式 （cond）：循环迭代的上界表达式是一个关于循环索引变量与外层循环索引变量和/或编译符号常量的仿射表达式。循环索引变量有多个上界时，可以用min函数表示。
– 循环步长 （inc）：循环步长是一个整型常数，一个常数也可以用一个仿射表达式表示。循环步长在大多数情况下是1，也可以是其他整型常数。当循环步长是负数时，循环是一个递减型循环。
– 循环体 （body）：循环体可以是抽象语法树上的任意一种类型的结点。当循环体仍然是一个for结点时，该循环体与当前循环构成循环嵌套。当循环体是一个block结点时，代表该循环内有多个语句。
如图2.7中第2层和第4层上都有for结点。以 S 1 （ i ）结点上面的for结点为例，该for结点可以表示成{iterator: i ;init:0;cond: i<M ;inc:1;body:for}的形式，其中循环迭代上界表达式cond还可以嵌套地用另外一个抽象语法树表示，如图2.8所示是图2.5所示代码 i 循环上界表达式的抽象语法树。
图2.8 一个循环上界表达式的抽象语法树
（2）if 结点 ：if结点是条件控制流语句的抽象，它由一个谓词条件表达式和两个结点组成，分别如下。
– 谓词条件表达式 （guard）：if结点的谓词条件表达式可以是一个循环索引变量的仿射表达式，也可以是多个仿射表达式的合取范式或析取范式；if结点的谓词条件表达式也可以是非仿射表达式，或者是可以修改外层循环迭代次数的表达式。谓词条件表达式的抽象语法树与图2.8类似。
–then 语句结点 （then）：then语句结点可以是任意一种类型的结点。当then语句结点是一个block结点时，表示该if语句内有多个语句。
–else 语句结点 （else）：else语句结点也可以是任意一种类型的结点。与then语句不同，else语句不是必须存在的，这取决于程序的语义和代码生成阶段根据整数集合和仿射函数计算出来的边界和其他约束条件。
在实际应用中，一个if结点可以用{guard:ast_expr;then:ast_node;else:ast_node}的形式表示，其中ast_expr表示一个表达式，ast_node表示一个抽象语法树的结点。
（3）block 结点 ：block结点是一组抽象语法树结点的列表，该列表中的每个结点可以是任意类型的结点。如图2.7最上面的结点为一个block结点，该结点可以用{ast_node,ast_node, … }的形式表示。
（4）mark 结点 ：mark结点是根据调度树表示创建的一种特殊类型的结点，该结点由标识符和被标记的结点构成。其中，标识符用于存储调度树表示中用于指定特殊信息的字符串相关信息，被标记的结点可以是任意其他类型的结点，该结点根据mark结点的字符串信息按照定制化的方式生成抽象语法树。例如，在面向GPU生成代码时，需要将循环索引变量和硬件循环索引变量进行映射和替换。当一个for结点被mark结点标记后，相应的循环索引变量可以被替换成硬件循环索引变量。mark结点可以用{id:id;node:ast_node}的形式表示，其中id为该结点的标识符，node为被该结点标记的结点。
（5）user 结点 ：user结点是从调度树中继承过来的结点，用于表示多面体模型抽象成的语句。如图2.7中的叶结点都是user结点。当user结点代表一个语句时，对应的语句可以被递归地表示成传统表达式抽象语法树的形式。在实际应用中，多面体模型可能会将多个语句抽象成一个宏语句，此时抽象语法树可以递归地构建每个语句的表达式。user结点内可以有while循环，也可以有break、continue等语句。
通过构造抽象语法树，多面体模型能够面向不同体系结构自动生成代码。在面向一种特定体系结构上的编程模型生成代码时，优化编译器的后端可以按照目标编程模型的规范打印程序语句。与传统的抽象语法树相比，多面体模型中的抽象语法树还提供了调度树与抽象语法树之间的信息交互，使调度变换能够更好地传递到抽象语法树中。