2.2　整数集合与仿射函数

优化编译器的目的是通过模型的构建来实现对程序的变换，但在对程序进行变换之前，一个更重要的问题是如何对程序进行有效的表示。从上面的描述中可以看出，程序语句实例的执行顺序是语句实例之间的先后关系，而循环边界和循环步长限定的范围是语句实例构成的集合。在这些集合和关系的基础上，编译器的优化模型可以借助集合和映射关系的基本操作实现对程序执行顺序的调整，从而达到提升程序性能的目的。

2.2.1　静态仿射约束

整数集合（integer set）和仿射函数（affine function）或仿射关系（affine relation）是多面体模型对程序进行表示的数学基础。多面体模型要求表示的程序满足整数集合的约束显然是合理的，因为在实际应用中，循环索引变量的取值范围都是整数。在此基础上，多面体模型用仿射函数或仿射关系来表示程序中语句和语句之间或语句与内存地址单元之间的关系，这在一定程度上限定了多面体模型的适用范围。尽管如此，多面体模型还是能够满足绝大部分程序或循环嵌套的表示和优化，尤其是以深度神经网络为代表的应用。

多面体模型要求待分析和变换的循环嵌套满足 静态仿射约束 （Static Control Parts，即SCoP）。一个SCoP是指一段满足特定条件的程序语句的最大集合，该条件要求封装这些程序语句的循环的边界、步长和控制流语句的条件只能是外层循环索引变量和符号常量的仿射函数。这样的约束允许多面体模型利用仿射函数或仿射关系来实现程序的表示和优化。显然，一些复杂的程序表示形式，如形如 A [ i×j ]的数组下标表达式是无法利用多面体模型进行建模的，因为这样的表达式并不满足仿射函数的要求。此外，一些只有在程序运行时才能够确定的控制流信息也不利于用多面体模型进行抽象，例如break、continue等动态控制循环提前结束或循环运行状态的指令，都不在多面体模型的处理能力范围内。当然，随着多面体模型技术的不断发展，这些问题的处理也有了一定的改进，但是本章不会涉及这些扩展技术的细节。

对于满足静态仿射约束的程序片段或循环嵌套而言，优化编译器可以利用多面体模型构造相应的中间表示抽象，这种中间表示的基础就是整数集合和仿射函数。下面分别介绍整数集合和仿射函数，然后再介绍由此得到的更高层次的中间表示。

2.2.2　整数集合

对循环嵌套内的语句进行实例化的过程是根据循环嵌套的维度进行展开并进行排列的。对于一个 d 层循环而言，可以用一个整数 d 元组表示语句实例的维度，如果再用一个标识符对每个语句进行命名，那么该标识符以及 d 元组就可以表示循环嵌套内的一个语句。如2.1节中的例子，循环嵌套内的语句可以用 S ₁ （ i,j ）来表示，其中 S ₁ 为该语句的标识符，（ i,j ）为循环索引变量构成的二元组。我们用 一个标识符加上一个整数 d 元组 标识一个命名的整数空间。

在整数空间上添加上各个循环维度的约束，即循环边界和循环的步长带来的约束后，就可以得到对应的 整数集合 。我们用 一个带有约束的命名整数空间 标识一个命名的整数集合，每个约束用于标识循环边界和其他程序语义导致限定的边界，约束之间用“;”隔开。对于有限元素的整数集合，也可以通过枚举集合元素的方式进行描述。

在满足静态仿射约束的前提下，循环的边界等程序语义限定的约束通常是一个仿射表达式，而循环步长则有可能会引入一些复杂的约束，如前文提到的带有整除的约束信息，这些约束都可以用Presburger 公式 表示，而Presburger公式则是Presburger 语言 的一个一阶谓词公式。

其中，函数符号和谓词符号的 / 2表示该符号需要以两个参数作为输入，常数符号 / 0表示不需要参数。由于Presburger语言是一种一阶谓词语言，为了判断其中的公式是否能够被满足，必须对语言中的每个函数符号和谓词符号进行解释，并且必须限定每个公式中变量的范围。考虑到编译器是对循环嵌套的范围进行建模，所以多面体模型对Presburger语言的变量限定的范围是全体整数空间Z。对于Presburger语言中的符号，解释如下。

常数符号 c _i 并没有对应的特定解释，在编译阶段被当作符号常量处理。在给出Presburger公式的定义前，我们还需要定义Presburger语言中的项。

在上述定义中，当 r _i =0时， f _i （）也是Presburger语言的一个项。在编译优化的过程中， f _i （）可用于表示标量。

在多面体模型的表示中，一个整数集合是指如式（2-6）所示的元素构成的集合。当我们需要用一种更简洁的方式表示这个集合时，可以用Presburger公式表示这些元素的边界和取值范围。更具体地，图2.1中的语句实例集合可以用

{ S ₁ （ i,j ）:3≤ i< 10 ∧i ≤ j<N∧ （ i +1）%2=0}　　（2-9）

表示，“:”后是该命名整数空间的约束，每个约束由一个Presburger公式定义，循环索引变量 i 和 j 为该公式的 自由变元 （free variable）。当一个Presburger公式 F 是由另外一个公式 ∃v : F ₁ 或全称量词 ∀v F ₂ 递归定义，并且变量 v 在公式 F ₁ 或 F ₂ 中出现时，该变量 v 被称为公式 F 的自由变元，该变量在公式 F 中的出现被称为自由出现（free occurrence）。不难看出，式（2-9）中的约束实际上就是定义2.4中各种情况根据真实应用的实例化过程。

利用Presburger公式对整数集合的约束进行表示，能够帮助优化编译器利用Presburger算术（Presburger arithmetic）进行建模，并在此模型系统内进行演绎。Presburger算术是一个只有加法运算、没有乘法运算的算术体系，是一个相容并且完备的公理体系。Presburger算术只允许加法运算，但循环嵌套仿射表达式中可能会存在减法、乘法、除法和取模等复杂的运算。另一方面，Presburger语言中也允许减法、取模等运算的出现。因此，在Presburger公式的基础上，我们还定义了一些 语法糖 （syntactic sugar），说明其他几种运算和加法运算之间的等价性。

根据语法糖的定义，优化编译器可以将程序中可能存在的各种操作转换为加法操作或者其他Presburger公式归纳定义中的项来完成计算。例如，根据语法糖定义的规则（3），可以看出图2.2中外层循环的上界和图2.1中内层循环的下界是等价的。此外，在进行一些关键的循环优化，如循环分块时，规则（5）可以用于表示循环分块后带有取模操作的运算。

语法糖的其他规则给整数集合的表示提供了便利。例如，当我们想获取一个多维整数空间上的所有元素时，可以用布尔型值true表示对应的约束，相应的整数集合也被称为该整数集合的全集（universal set或universe）；当我们想表示一个标量值时，其对应的整数空间是一个零维空间，那么此时就可以用语法糖定义的规则（6）来表示。

当一个循环嵌套内有多个语句，并且不同语句外层的循环嵌套层数不相同时，这些语句所在的整数空间的维度不同。例如，当我们用一个三层循环嵌套实现一个矩阵乘法运算时，初始化语句的整数集合所在的空间是一个二维整数空间，而归约语句的整数集合所在的空间是一个三维整数空间。优化编译器可以将这个二维整数集合和三维整数集合合并在一起，用于表示整个矩阵运算的整数集合。当两个整数集合所在空间的维度不一致时，这两个整数集合之间无法进行基本的集合运算，例如，集合的交集运算。

2.2.3　仿射函数

虽然两个不同维度的整数集合进行基本运算是不允许的，但不同维度的整数集合之间可以构造一个相关的函数或映射进行关联。如果把一个整数集合作为定义域，另外一个整数空间作为值域，那么任意两个集合之间都可以构造一个 二元映射关系 （binary relation）。两个集合之间的二元映射关系可以是

（1）单射，即定义域中的每个元素被映射到值域的不同元素上；

（2）满射，即值域中的每个元素至少对应定义域中的一个元素；

（3）双射或一一映射，既是单射又是满射的映射，即定义域中的元素和值域中的元素一一对应。

整数集合的映射关系可以用于表述语句实例和内存地址单元之间的访存关系。例如式（2-5）中每个元素表示语句实例和被访问数组之间的写访存关系。构成映射关系的整数集合之间不必一定满足维度相同的约束。程序语句实例和内存地址单元之间的映射关系可以是单射、满射或双射。整数集合的映射关系也可以表示语句实例的执行顺序，如当一个命名的整数空间映射到未命名的整数空间时，可以表示该语句实例的执行顺序，即程序语句的 调度 （schedule）。例如，图2.1中语句的执行顺序可以用

[ S ₁ （ i,j ） → （ i,j ）]　　（2-10）

表示，该映射表示将一个命名的整数集合 S ₁ （ i,j ）中的所有元素映射到一个未命名的整数集合（ i,j ）上，可以理解为将语句 S ₁ （ i,j ）按照（ i,j ）的调度顺序执行。表示程序语句实例执行顺序的映射一般都是双射。但是在一些特殊的情况下，优化编译器也需要用满

射来表示程序语句实例的执行顺序，这种情况往往是在实现复杂的循环变换，例如第5章将会介绍的交叉分块就需要利用满射来实现将同一个语句实例执行多次。

基于多面体模型的优化编译器将程序的表示限定在静态仿射约束的范围内，所以多面体模型关注的是仿射函数，根据仿射函数实现的程序变换也被称为 仿射变换 （affine transformation）。在继续介绍仿射变换之前，我们给出 仿射函数 的定义。

上述定义中 i 可以看作定义域，函数的结果 f （ i ）是值域。在实际应用中，多面体模型常将上述定义中的实数空间R局限在整数空间Z上，这样能够使计算结果更符合程序的实际语义。如果上述定义中 c 向量是一个零向量，那么式（2-11）退化成一个线性函数。所以，仿射函数可以看作线性函数加上一个偏移。我们用 → 表示两个整数集合之间的二元映射关系。

与整数集合类似，多面体模型也可以以一个仿射函数作为一个元素构造由仿射函数构成的集合，如式（2-5）所示就是一个仿射函数的集合。类似地，我们也用“:”将仿射函数与仿射函数的约束分开。仿射函数集合的约束也由一个Presburger公式指定。与整数集合不同的是，仿射函数集合的约束需要同时考虑定义域和值域中所有自由变元。与此同时，在比较多维整数集合之间的大小时，需要用到字典序比较，字典序的定义将在第3章中进行介绍，这里我们先给出关于字典序比较的语法糖。

根据上述语法糖的规则，多面体模型可以构造由仿射函数为元素构成的集合，即可得到如式（2-5）所示的访存关系集合，并在此基础上计算语句实例之间的依赖关系。多面体模型也可以根据这些语法糖来计算语句实例的执行顺序，并结合依赖关系计算新的执行顺序，在此过程中实现的变换都是仿射变换。

Presburger公式只允许加法操作，根据语法糖的定义，可以通过加法操作实现减法和乘法操作，但是除法操作却无法直接用加法操作来实现。除法操作是优化编译器实现循环分块的一个重要基础。利用Presburger公式实现通用的除法运算比较困难，但结合循环嵌套和实际应用只取整数值的特点，能够表达整数除法就足以实现满足程序变换的目的。以定义2.5规则（5）中取模操作为例，取模操作可以看作减法和整数除法的组合操作，而整数除法可以用乘法来表示。更具体地，如果优化编译器需要对图2.2中的循环嵌套实现循环分块，那么可以用

表示循环分块的调度，其中32表示该维度上循环分块的大小。那么这个仿射函数中的除法就可以用

的乘法形式来表示。在程序变换的过程中，基于多面体模型的优化编译器仍然允许形如式（2-12）的仿射函数，这种带有整数除法的表达式被称为 近似仿射表达式 （quasi-affine expression），相应的变换也被称为 近似仿射变换 （quasi-affine transformation）。

整数除法操作能够支持循环分块之间的调度，但是式（2-12）表示的循环分块并不完整。对于图2.2中的两层循环嵌套（ j,i ），循环分块后应该是一个四层的循环嵌套，所以，循环分块的一个更精确的仿射函数应该用

来表示，其中（ j/ 32 ,i/ 32）表示分块之间的循环维度，（ j,i ）表示分块内的循环维度。

在利用仿射或近似仿射函数表示程序变换的同时，优化编译器也不得不考虑函数与硬件之间的对应关系。例如，在经过循环分块之后，优化编译器需要将式（2-14）中的不同维度映射到不同的并行硬件维度上，这就需要将式（2-14）表示成一种分段（piecewise）的形式。仿射函数或近似仿射函数的分段表示是一种变换形式，例如，式（2-14）也可以表示成

的形式，即将式（2-14）的值域进行分段，每一段用一对“{}”表示，如式（2-15）所示，这种表示形式被称为 分段近似仿射函数 （piecewise quasi-affine function）。此时，优化编译器可以根据分段表示形式将仿射函数进行分裂，不同的分段可以映射到不同的并行硬件维度。关于仿射函数的分裂将在下面的内容中进行介绍。

2.2.4　集合与映射的运算

整数集合和仿射函数为程序的表示提供了数学基础，但如果需要对程序进行变换，多面体模型还需要支持基于这些表示的运算。即使是程序的表示，仅利用整数集合和仿射函数也是不够的。

一个整数集合可以表示一个语句的所有实例，正如图2.1中的例子所示。考虑一个稍微复杂点的例子，如矩阵乘法，循环嵌套内包含两个语句，分别是二维整数空间上的初始化语句和三维整数空间上的归约语句，根据整数集合，假设这两个语句分别可以用整数集合

{ S ₁ （ i,j ）:0≤ i ≤ M∧ 0≤ j ≤ N }　　（2-16）

和

{ S ₂ （ i,j,k ）:0≤ i ≤ M∧ 0≤ j ≤ N∧ 0≤ k ≤ K }　　（2-17）

表示。当我们需要表示整个矩阵乘法的语句实例时，需要计算这两个整数集合的并集，其结果为

{ S ₁ （ i,j ）:0≤ i ≤ M∧ 0≤ j ≤ N ; S ₂ （ i,j,k ）:0≤ i ≤ M∧ 0≤ j ≤ N∧ 0≤ k ≤ K }　　（2-18）

计算集合的并集这个运算看起来是一个非常直观的事情，但是在具体实现的过程中，需要考虑到各种复杂的应用场景。在上面集合并集的计算过程中，虽然我们知道式（2-16）和式（2-17）表示两个不同的语句，但在工程实现中却需要一系列复杂的准备工作来确定这两个整数集合表示的是不同的语句。如果程序中存在另外一个语句，其对应的整数集合可以用

{ S ₁ （ i,j ）: M ≤ i ≤2 M∧N ≤ j ≤2 N }　　（2-19）

表示，那么当对式（2-16）和式（2-19）进行并集计算时，可以得到：

{ S ₁ （ i,j ）:0≤ i ≤ M∧ 0≤ j ≤ N ; S ₁ （ i,j ）: M ≤ i ≤2 M∧N ≤ j ≤2 N }　　（2-20）

更进一步地，我们可以将其化简成

{ S ₁ （ i,j ）:0≤ i ≤2 M∧ 0≤ j ≤2 N }　　（2-21）

的形式。这种化简过程的前提条件是这两个整数集合代表的是相同的语句，并且这种情况在实际应用中也会发生，例如第4章中将会介绍的迭代空间分裂或其逆过程就需要使用这样的运算。所以，在进行整数集合和仿射函数的运算时，一个重要的步骤就是要判定当前运算中的整数集合是否表示相同的语句，或者称两个整数空间是否 同构 。

当两个整数集合的空间是同构空间时，对两个整数集合实现并集运算就可以转换为两个整数集合的约束Presburger公式之间的析取操作。类似地，由于仿射函数的定义域和值域都是整数集合，所以判定整数集合的空间是否相等的方法也可以用于判定仿射函数所在的空间是否同构，即两个仿射函数集合定义域所在的整数空间和值域所在的整数空间分别同构时，这两个仿射函数集合就被认为是同构的。

在实际应用中，一个循环嵌套内往往包含多个语句，所以优化编译器通常需要对整数集合的并集进行各种操作。如果我们把整数集合或仿射函数集合的并集看作集合的集合，那么这些集合的并集运算可以被定义为以元素为单位执行的运算。对于一个整数集合或仿射函数而言，其运算可以分为单目运算（unary operation）和双目运算（binary operation）。

多目运算可以是单目运算和双目运算的组合。单目运算和双目运算也涵盖了多面体模型中整数集合或仿射函数集合并集的几乎全部运算。对于整数集合的并集，一个典型的单目运算是对每个整数集合取样（sampling），一个典型的双目运算可以是两个集合之间求交运算。对于仿射函数集合的并集，一个典型的单目运算可以是对每个仿射函数进行求逆操作，双目运算的例子包括计算两个仿射函数的复合函数（composition function）等。

所以我们可以将问题聚焦在一个语句的整数集合或一个仿射函数的集合上。整数集合和仿射函数的单目运算可以通过Presburger公式的定义和语法糖的规则来实现。对于双目运算，假设有整数集合 S ₁ ={ A （ i ）: p ₁ （ i ）}和 S ₂ ={ B （ j ）: p ₂ （ j ）}，仿射函数集合 R ₁ ={ C （ i ₁ ） →D （ j ₁ ）: q ₁ （ i ₁ , j ₁ ）}和 R ₂ ={ E （ i ₂ ） →F （ j ₂ ）: q ₂ （ i ₂ , j ₂ ）}，那么整数集合和仿射函数的一些双目运算可按照如下方式计算。

（1） 整数集合的并集 为

（2） 仿射函数集合的并集 为

（3） 整数集合的交集 为

（4） 仿射函数集合的交集 为

（5） 整数集合的差集 为

（6） 仿射函数集合的差集 为

这些基本的双目运算可以用于计算更复杂的运算。例如，集合的包含关系可以用

（1） A⊆B⇔A\B =∅；

（2） A⊇B⇔B⊆A ；

（3） A = B⇔A⊆B∧B⊆A ；

（4） A⊂B⇔A⊆B∧¬ （ A = B ）；

（5） A⊃B⇔A⊂B 。

计算。其中， A 和 B 既可以是一个整数集合，也可以是一个仿射函数的集合。

整数集合和仿射函数集合的绝大部分运算的定义或计算规则是相同的，但也存在某一种运算对这两种不同的集合定义不同的情况，这个运算就是计算集合的 基数 （cardinality），它被定义如下。

整数集合基数的定义比较直观，即计算当前集合内所有满足条件的元素个数。仿射函数集合的基数则是代表了每个仿射函数不同的定义域在该函数关系下对应的值域上的元素个数，它可以用于判定当前仿射函数是否对每个元素定义了单射、满射还是双射。在实际应用中，仿射函数集合的基数还可以用于判定语句依赖关系的源点、汇点个数，或某个语句实例是否会被执行多次等现实问题。当计算整数集合并集或仿射函数集合并集时，由于计算基数的运算是单目运算，可以按照式（2-22）的方式得到最终的结果。