下载掌阅APP，畅读海量书库
立即打开
对于循环优化，一个经典的优化模型是 幺模变换 （unimodular transformation） [7] 。“幺模”一词取自线性代数中的幺模矩阵，该矩阵是指一个所有元素均为整数且行列式的绝对值为1的方阵。幺模矩阵能够表示的变换包括循环交换、循环倾斜和循环反转。根据幺模矩阵的定义，多个幺模矩阵的乘积也是幺模矩阵，所以幺模变换允许上述这几种变换的组合，但也仅局限于上述三种循环变换。
幺模变换虽然没有被广泛地使用在优化编译器中，但是该模型为多面体模型（polyhedral model）的发展奠定了良好的基础。多面体模型是对满足一定约束的循环嵌套进行分析和优化的数学抽象模型。多面体模型能够处理的循环变换比幺模变换的范围要广，并且不受限于矩阵行列式的绝对值必须为1的约束，在典型的优化编译器和面向深度学习的编译器中占据着一席之地。
多面体模型的抽象是基于程序语句实例的。换句话说，程序中的每个语句实例和内存单元都需要分别进行表示，一条语句的每次执行都对应不同的实例，一个数组元素的每次访问都对应一次内存单元的访问。多面体模型通过一些不同的表示组合来对程序进行抽象，一个典型的组合是用一个集合和多种映射的组合，即将程序表示成一个迭代空间（集合）、语句实例和内存单元之间的访存关系（映射）、语句实例之间的依赖关系（映射）和程序语句实例执行顺序的先后关系（映射）。当然，在多面体模型的发展过程中，还存在过一些其他的组合方式，这些组合方式可能在采用集合和映射的个数上与上述组合方式不完全一致，但其基本原理与这种组合方式并无差别。
为了对多面体模型有一个直观的理解，我们以一个具体的实例说明多面体优化问题的数学建模过程。以图2.1所示代码为例，其中 N 为编译阶段未知的符号常量。
图2.1 带符号常量的循环嵌套
为了构造形如式（1-1）所示的迭代空间的约束集合，我们首先列出上述循环嵌套的所有上界和下界约束，并将其转换为
即多面体模型将所有的不等式都统一转换成≥0的形式。在该转换过程中，多面体模型总是假设所有的变量是满足整数约束的，即所有的循环索引变量在整个可行解空间上只取整数值，这样的约束是满足程序实际应用需求的。所以，在上述转换过程中， i< 10和 −i +9≥0总是等价的。
将上述不等式组写成矩阵形式，可以得到
将约束不等式组写成矩阵的形式，是为了方便后续利用整数线性规划或其他的数学模型来提取一些特定的信息并实现相关的优化，相关细节将会在后面的内容中具体介绍。显然，只表示循环的边界是不够精确的，因为循环的步长限定外层循环变量 i 只取奇数，这意味着外层循环还要满足（ i +1）%2=0的条件，%表示整除操作。我们也可以将这个约束表示成
的形式。更进一步地，式（2-3）也可以表示成
的形式。因此，所有的循环约束都可以表示成不等式的形式。
此外，多面体模型用一个映射关系表示语句实例和数组表示的内存地址单元之间的访存关系。对于图2.1所示的访存关系，语句实例只对内存地址单元进行写访存操作，那么这个访存关系可以表示成
的形式，其中 → 可以解读成从语句 S 1 （ i,j ）到 A （ j,i ）的（读/写访存）关系，上述表示也是这种关系构成的一个集合，即该集合中的每个元素都是一个读/写访存关系。
在上述约束的限定条件下，编译器或相关的抽象模型需要对图2.1中循环的并行性、可切分性及数据访存的局部性进行分析与优化。根据循环约束式（2-4），可以将图2.1所示的原始代码的语句实例按照访问顺序展开如
的形式。
根据访存关系式（2-5）与语句实例的执行顺序式（2-6），可以推断出数组 A （ j,i ）的访问顺序为
如果数组在内存中是按照行优先的方式存储的，那么上述数组访问顺序显然无法利用数组 A 在内存空间存储的局部性。但是，如果编译器能将上述代码进行变换，得到如
所示的访问顺序，那么数组被访问的顺序就与该数组在内存中的存储顺序一致，程序的执行性能就有可能因此提高。编译器通过对这种性质的建模，利用语句实例和数组存储的内存地址单元之间的关系，可以推断出程序应该实现一个循环交换的变换，那么这种变换之后对应的程序应该是如图2.2所示的代码。
图2.2 变换后的循环嵌套
此时，语句 S 1 的执行顺序与数组在内存中的排列顺序一致。此外，从图2.2中的代码不难看出，在计算循环交换的同时，编译器还需要精确计算交换后循环的边界。由于 N 是编译阶段未知的符号常量，编译器并不知道 N 与另外的已知循环上界10之间的关系，那么为了获得正确的代码，在循环交换后循环边界上必须引入一个min操作来获取这两个边界之间较小的那个值。如果是两个下界之间的比较，那么就需要引入一个max操作来获取较大的那个下界，这样经过变换之后的程序总是正确的。
虽然上述循环交换的变换是比较直观的，但是让编译器自动实现这样的程序变换仍然是一个非常复杂的过程，需要用到包括集合与映射的运算、矩阵变换以及对整除等操作的建模和相应表示的代码生成等一系列中间抽象过程。本章将针对当前优化编译器中的多面体模型中所使用的抽象进行介绍。