下载掌阅APP，畅读海量书库
立即打开
在经过各层次的抽象后，优化编译器可以对一段满足静态仿射约束的代码片段进行变换并最终生成代码。各种抽象表示为程序优化和代码生成提供方便的同时，也增加了系统工程师和程序员理解这些抽象表示的难度。此外，这些抽象表示方法在理论上相对完善，但如何在系统软件中实现这些抽象及各种操作，也是一个非常具有挑战的任务。isl（integer set library） [71] 是一个集成了整数集合、仿射函数、调度树和抽象语法树等各种抽象表示的工具库。本节将介绍isl中关于各种抽象表示的实现，结合实际代码来帮助读者加深对这些抽象表示的理解。
在进行整数集合和仿射函数集合的操作时，需要先判定整数集合和仿射函数集合是否同构。以整数集合的并集为例，当两个整数集合同构时，其并集可以合并成一个整数集合；否则，并集运算的结果需要以两个整数集合并集的形式描述。为了在工程实现上对这些操作进行区分，isl定义了6种不同的数据类型，并根据这6种不同的数据类型来实现前文介绍的运算。
首先，isl中定义了基本整数集合和基本映射集合。
定义2.11 基本整数集合
一个基本整数集合 S 被定义为一组仿射不等式约束
其中
。
定义2.12 基本映射集合
一个基本映射集合 R 被定义为由仿射不等式约束限定的映射 x 1 → x 2 的集合，即
其中
。
上面两个定义在isl中分别用isl_basic_set和isl_basic_map这两个数据结构表示。在本章开始部分，我们介绍过如果循环嵌套边界和步长的约束可以用式（2-2）和式（2-4）表示。也就是说，循环的边界和步长约束都可以表示成不等式的形式，并且每个不等式都可以用≥0表示。所以，式（2-48）和式（2-49）中的仿射约束都可以用≥0表示。
式（2-48）的仿射约束代表一个形如式（2-9）的整数集合中的仿射约束，在该例中，
s
=（
N
）
T
表示由图2.1的编译符号常量构成的一个向量，
x
=（
i,j
）
T
是该程序循环索引变量构成的向量，
z
=（2）
T
是外层循环步长构成的整数向量，
c
=（
−
3,9,0
,−
1）
T
是式（2-2）中的常数列向量。将式（2-48）进行实例化之后，不难看出式（2-48）中其他变量的含义。
是一个
m×d
维的矩阵，
m
为仿射不等式约束的个数，
d
为循环嵌套的层数，
A
代表形如式（2-48）中（
i,j
）
T
的系数矩阵。
是一个
m×n
维的矩阵，
n
为符号常量构成的向量
s
的维度。
是一个
m×e
维的矩阵，
e
是
z
的维度。这里，
z
的每个分量会形成一个具有存在量词
∃
的仿射不等式约束。当
e
=0时，意味着不存在一个具有存在量词
∃
的约束。例如，当循环嵌套内每个循环的步长都为1时，
e
=0成立。
式（2-49）中各变量的含义与式（2-48）的含义基本一致，区别在于式（2-49）涉及一个映射 x 1 → x 2 两个集合之间的关系，因此在仿约束中需要同时体现 x 1 和 x 2 的约束。利用整数集合和基本映射集合，我们可以定义isl中的其他几个数据结构的定义。
定义2.13 整数集合
一个整数集合 S 被定义为一组同构基本整数集合 S i 的并集，即
定义2.14 仿射函数集合
一个仿射函数集合 R 被定义为一组同构基本映射集合 R i 的并集，即
isl中用isl_set和isl_map表示整数集合和仿射函数集合。在此基础上，isl又分别用isl_union_set和isl_union_map表示整数集合的并集和仿射函数集合的并集，其定义分别如下。
定义2.15 整数集合的并集
一个整数集合的并集 S 被定义为一组整数集合 S i 的并集，即
定义2.16 仿射函数集合的并集
一个仿射函数集合的并集 R 被定义为一组仿射函数集合 R i 的并集，即
整数集合的并集isl_union_set、整数集合isl_set和基本整数集合isl_basic_set之间是逐层“嵌套”的关系。通过isl_union_set_empty可以构造一个空的整数集合的并集，通过isl_union_set_intersect、isl_union_set_union和isl_union_set_subtract可以获得两个整数集合并集的交集、并集和差集。通过isl_union_set_is_empty可以判断一个整数集合的并集是否为空集，通过isl_union_set_is_equal、isl_union_set_is_subset、isl_union_map_is_strict_subset可以判断两个整数集合的并集之间的包含关系。
通过整数集合构造整数集合的并集，isl提供了对多个语句建模的支持。通过基本整数集合构造整数集合，isl能够将同一个语句的不同约束集成到一个整数集合内。在isl的实现中，一个基本整数集合isl_basic_set可以直接转换成一个整数集合isl_set，一个整数集合isl_set可以直接转换成一个isl_union_set，但反过来的转换并不一定总是正确的。
仿射函数集合的并集isl_union_map、仿射函数集合isl_map和基本仿射函数集合isl_basic_map之间也是逐层“嵌套”关系。通过isl_union_map_empty可以构造一个空的仿射函数集合的并集，通过isl_union_map_intersect、isl_union_map_union和isl_union_map_subtract可以获得两个仿射函数集合并集的交集、并集和差集。通过调用isl_union_map_is_empty可以判断一个仿射函数集合的并集是否为空集，并且可以通过调用isl_union_map_is_equal、isl_union_map_is_subset、isl_union_map_is_strict_subset判断两个仿射函数集合的并集之间的包含关系。
另外，通过调用isl_union_map_reverse可以获得仿射函数集合的并集的逆映射，所谓逆映射是将每个仿射函数替换为对应的反函数。
定义2.17 整数集合的参数范围
一个整数集合 S 的参数范围（parameter domain）dom p 可以表示为
定义2.18 仿射函数集合的参数范围
一个仿射函数集合 R 的参数范围（parameter domain）dom p 可以表示为
整数集合的参数范围可以用于计算整数集合的基数。以例2.1为例，一个整数集合的基数与其参数 M 和 N 的取值相关。也就是说，如果要计算一个整数集合的基数，编译器需要计算出一个整数集合的参数范围，根据不同的参数范围，整数集合的基数也会有所不同。此外，当利用带有符号常量的整数集合生成代码时，为了保证程序的正确性，编译器必须分析所有符号常量的可能取值。此时，生成的代码可能就会有以符号常量的取值范围为条件的if分支。
对于仿射函数集合的每个元素，isl可以计算该映射关系的定义域和值域，那么每个元素的定义域构成的集合就被称为这个仿射函数集合的定义域，每个元素的值域构成的集合被称为这个仿射函数集合的值域。
定义2.19 仿射函数集合的定义域
一个仿射函数集合 R 的定义域（domain）dom是一个整数集合，可以表示为
定义2.20 仿射函数集合的值域
一个仿射函数集合 R 的值域（range）ran是一个整数集合，可以表示为
在isl中，可以通过isl_union_map_domain和isl_union_map_range获得仿射函数集合并集的定义域和值域。
仿射函数集合的定义域和值域在代码生成阶段发挥着重要作用。以调度树表示为例，当利用filter结点下的一个band结点生成代码时，isl可以计算该band结点中的一个仿射函数集合的定义域，并与该filter结点内的整数集合进行求交运算，以消除band结点中与该filter结点无关的仿射函数集合。
类似地，两个仿射函数集合的复合被定义为这两个集合元素的复合的集合。仿射函数集合的复合可用于计算依赖关系。在isl中对应的操作是isl_union_map_apply_range。
定义2.21 两个仿射函数集合的复合
两个仿射函数集合
和
的复合
S◦R
被定义为一个仿射函数的集合，可以表示为
基于复合和逆映射的概念可以定义仿射函数集合的幂。
定义2.22 仿射函数集合的幂
在isl中调用isl_union_map_fixed_power_val可计算仿射函数集合的幂。
定义2.23 两个集合的全域关系
两个集合 R 和 S 的全域关系 R→S 被定义为定义域为 R 、值域为 S 的映射关系，可以表示为
R→S :={ i→j | i∈R∧j∈S } （2-60）
在isl中调用isl_union_map_from_domain_and_range可计算两个集合的全域关系。
定义2.24 集合的恒等关系
集合 S 的恒等关系定义如下：
I S :={ i→i | i∈S } （2-61）
在isl中调用isl_union_set_identity可获得一个集合的恒等关系。
定义2.25 两个集合的笛卡儿积
集合 S 和 R 的笛卡儿积定义如下：
S×R :={ i→j | i∈S∧j∈R } （2-62）
在isl中调用isl_union_set_product可获得两个集合的笛卡儿积。
定义2.26 两个二元关系的笛卡儿积
两个二元关系 S 和 R 的笛卡儿积定义如下：
S×R :={[ i→m ] → [ j→n ]|[ i∈j ] ∈S∧ [ m→m ] ∈R } （2-63）
在isl中调用isl_union_map_product可获得两个二元关系的笛卡儿积。
除了上面介绍的在整数集合和映射集合上的基本操作，isl中还定义了许多其他关于整数集合和仿射函数集合的运算，包括2.2.4节中介绍的单目运算和双目运算，这些都可以通过调用相应的函数接口即可使用。此外，isl中也实现了对三目运算符/条件运算符的支持。具体可参考isl的最新用户手册，这里我们就不再赘述了。这些基本操作的组合可以实现许多在程序优化过程中可能会用到的常用操作。
isl也支持调度树表示。调度树表示被封装在isl_schedule数据结构中，每个结点由不同的结点数据结构isl_schedule_node_x定义，x表示2.4.2节中一种结点的类型。例如，domain结点对应的数据结构为isl_schedule_node_domain。一个调度树一般以domain结点为根结点，但在一些特殊的情况下，extension结点也可以作为调度树的根结点。
调度树的构造过程在isl中也有许多对应的函数接口。例如，当优化编译器已经从程序中提取了表示迭代空间的整数集合后，isl可以构造一个domain结点，并通过isl_schedule_from_domain生成一个只有根结点的调度树。在此基础上，编译器可以添加其他结点，以构成原始程序未优化之前的调度。经过调度算法变换之后，优化编译器可以通过修改调度树band结点的仿射函数来修改调度树，并形成优化后的调度。
与调度树类似，抽象语法树的各种不同类型的结点也被封装在isl内，由isl_ast_node_x定义一种结点类型。isl_ast_buid表示生成抽象语法树的上下文信息，该数据结构封装了编译符号常量和外层循环索引变量的约束。根据不同的抽象语法树结点类型，用户也可以根据需求获取该结点的成员信息。例如，当结点类型为for结点时，可以通过isl_ast_node_for_get_cond来获取当前for结点循环索引的上界条件，该函数的返回类型为isl_ast_expr，是一个表达式。
一个isl_ast_expr可以是任意一种表达式，可以是一个操作isl_ast_expr_op，也可以是一个结点的标识符isl_ast_expr_id，或者是一个常数isl_ast_expr_int。抽象语法树由这些不同类型的表达式和结点递归构造生成。
此外，isl中的抽象语法树和调度树表示之间衔接得非常紧密。在根据调度结果生成优化后的抽象语法树时，isl既可以以一个调度树为输入，也可以以一个isl_union_map为输入，支持union map表示的代码生成。