第 1 章：Polyhedral Model 的最小回顾
直觉
Polyhedral Model 把循环程序的一部分执行结构改写成几何对象。一个循环迭代对应整数格上的一个点；循环边界给出点必须满足的不等式；数组下标给出从迭代点到内存位置的映射。这样，交换循环、融合循环或改变执行次序，就可以转化为对整数点及其关系的变换。
这里首先要分清两层对象。设 $d$ 为循环嵌套的维数，$P \subseteq \mathbb{R}^d$ 表示实数空间中的有理多面体；真正会执行的实例却属于整数点集 $P \cap \mathbb{Z}^d$。图上画出的连续三角形或矩形只是“实数形状”，编译器必须处理的是其中离散的整数格点。二者有联系，但不是同一个集合。
Polyhedral Model 通常从 静态控制部分（static control part，SCoP）出发：循环边界、分支条件和数组下标都能由外围参数与循环变量的仿射式描述，并且控制结构不依赖运行时数组值。SCoP 是工程上的可分析程序区域，不是“任何使用数组的循环”的同义词。这种以仿射域、访问和变换组织循环程序的工程路线可参照 Pluto 项目/作者资料页；从 polyhedra 扫描整数点并恢复循环的经典表述参见 Bastoul 2004。两处引用用于定位经典模型与工程语境，不替代本章对具体公式的推导。
形式定义
令 $m$ 表示参数个数，$p=(p_1,\ldots,p_m)$ 表示参数向量。参数是在所分析区域内保持不变、但编译时未必知道具体数值的整数，例如矩阵尺寸 $N$ 和 $M$。只约束参数的公式记为 $C(p)$，称为参数上下文。例如
$$ p=(N,M),\qquad C(p): N\ge 0\land M\ge 0. $$
令 $S$ 表示一条语句，$x=(i_1,\ldots,i_d)$ 表示它的一次语句实例或迭代向量。语句 $S$ 的参数化迭代域记为
$$ D_S(p)\subseteq \mathbb{Z}^d. $$
因此 $x \in D_S(p)$ 表示实例 $x$ 会执行；完整条件写作 $C(p) \land x\in D_S(p)$，避免把参数误当成迭代坐标。
本章所说的仿射式是
$$ a_0+a_1i_1+\cdots+a_di_d+b_1p_1+\cdots+b_mp_m, $$
其中所有系数 $a_r$、$b_s$ 都是固定整数。仿射边界和数组下标允许常数乘变量，例如 2i+N-1；不允许两个一般变量相乘，例如 ij。
共同符号契约把抽象内存位置集合记为 $M$。由于本章的矩形例已用 $M$ 表示尺寸，在两者同现时临时写作 M_{mem}；它只是该内存集合的消歧别名。读访问关系 $R_S \subseteq D_S\times M_{mem}$、写访问关系 $W_S \subseteq D_S\times M_{mem}$ 都按“语句实例 $\to$ 内存位置”读取。例如
$$ ((i,j),A[i,j])\in R_S $$
表示实例 (i,j) 读取数组元素 A[i,j]。
手算示例
矩形域
令 $N,M\in\mathbb{Z}$ 且参数上下文为 $N\ge0\land M\ge0$。矩形域定义为
$$ D_{\mathrm{rect}}(N,M)= \{(i,j)\in\mathbb{Z}^2\mid 0\le i<N\land 0\le j<M\}. $$
取 N=3、M=2，逐行固定 $i$ 可得
$$ D_{\mathrm{rect}}(3,2) =\{(0,0),(0,1),(1,0),(1,1),(2,0),(2,1)\}. $$
它的实数松弛是
$$ P_{\mathrm{rect}}(3,2)= \{(u,v)\in\mathbb{R}^2\mid 0\le u<3\land0\le v<2\}. $$
例如 (1/2,1) 属于这个实数形状，却不是循环实例；循环只执行 $P_{\mathrm{rect}}(3,2)\cap\mathbb{Z}^2$ 中的点。严格上界使该实数集合不是闭多面体；在整数语义下可等价改写为 $i\le N-1$、$j\le M-1$，得到通常使用的闭不等式描述。
三角域
令 $N\in\mathbb{Z}$，并把循环尺寸的参数上下文规定为 $C(N):N\ge0$。在此上下文下，三角域定义为
$$ D_{\mathrm{tri}}(N)= \{(i,j)\in\mathbb{Z}^2\mid0\le i<N\land0\le j\le i\}. $$
取 $N=4$：当 $i=0,1,2,3$ 时，$j$ 分别取 $0$、$\{0,1\}$、$\{0,1,2\}$、$\{0,1,2,3\}$，所以
$$ D_{\mathrm{tri}}(4) = \left\{ \begin{aligned} &(0,0),\\ &(1,0),(1,1),\\ &(2,0),(2,1),(2,2),\\ &(3,0),(3,1),(3,2),(3,3) \end{aligned} \right\}. $$
点数为 $1+2+3+4=10$。边界 $j\le i$ 把两个循环变量线性联系起来，因此它仍是仿射约束。
数据运算不等于下标运算
考虑矩阵乘法内部语句
C[i][j] += A[i][k] * B[k][j];
若 $i$、$j$、$k$ 的循环边界仿射，访问 C[i][j]、A[i][k]、B[k][j] 的下标也都是仿射的。右侧 A[i][k] * B[k][j] 确实做了乘法，但相乘的是从内存读出的数据值，不是用来决定控制流或地址的循环变量。因此该乘法不违反经典 SCoP 对控制和下标的仿射限制。
编译器用途
把每次执行显式表示成整数点后，编译器可以分别记录：
- 域 $D_S(p)$：哪些实例存在；
- 访问关系 $R_S$、$W_S$：每个实例读写哪里；
- 调度：每个实例在什么逻辑时间执行。
这些对象共同支持后续的依赖分析和循环变换。特别要注意，本章只建立表示条件：某段程序可被建模，并不自动说明任意变换都合法；合法性还要由 source 实例到 sink 实例的依赖顺序证明。
矩形域常对应彼此独立的规则循环，三角域常对应带迭代变量相关仿射边界（如 $j\le i$）的嵌套循环。二者都能用仿射不等式描述，所以可以交给整数集合/关系工具做求交、投影和扫描。
常见误区
- 把实数图形等同于执行集合。 $P\subseteq\mathbb{R}^d$ 包含连续点，程序实例是 $P\cap\mathbb{Z}^d$。在实数上消去严格不等式、取凸包或做松弛时，必须检查是否保持所需的整数语义。
- 认为程序中不能出现任何乘法。 限制针对控制条件和地址函数。
A[i][k] * B[k][j]的数据值乘法不改变迭代域或访问下标，因此可以留在语句体内。 - 把参数和循环坐标混在一起。 $N$、$M$ 属于参数向量 $p$，$i$、$j$ 属于实例 $x$；应写 $C(p)\land x\in D_S(p)$。
- 把所有数组表达式都当成仿射访问。
A[i*i]的下标含变量乘变量；A[B[i]]的地址依赖运行时数组值；while (A[i] > 0)的迭代次数依赖运行时数据。三者都越过经典 SCoP/Presburger 建模边界。运行时检查、保守近似或扩展模型可以处理部分情况，但那是另外的技术路线，不能把原表达式悄然当成精确仿射模型。 - 从“能表示”直接跳到“优化有效”。 表示、变换合法性和性能收益是三个不同问题。
练习
练习 EX01-B01｜矩形域枚举与计数（基础）
枚举 $D_{\mathrm{rect}}(2,3)$ 的全部整数点，并写出点数关于 $N,M$ 的公式。
答案索引： ANS-EX01-B01
练习 EX01-D01｜三角域计数与语言边界（推导）
枚举 $D_{\mathrm{tri}}(5)$，验证点数为 $N(N+1)/2$。这里的乘法出现在分析者给出的计数公式中；说明它为何不等于在 Presburger 域公式里加入变量乘法。
答案索引： ANS-EX01-D01
练习 EX01-B02｜仿射下标判定（基础）
判断下列下标是否仿射，并说明理由：A[2*i+N]、A[i+j]、A[i*j]、A[index[i]]。
答案索引： ANS-EX01-B02
练习 EX01-C01｜参数化斜三角域（综合）
为 for (i=0;i<N;i++) for (j=i;j<M;j++) S(i,j); 写出参数上下文和迭代域。若 $N>M$，域会发生什么？
答案索引： ANS-EX01-C01
本章小结
Polyhedral Model 的基本对象不是连续图形本身，而是参数化仿射约束所选出的整数语句实例。参数上下文、迭代域和访问关系分别回答“尺寸是否合法”“哪些实例执行”“实例访问哪里”。经典 SCoP 允许语句体中的一般数据计算，但要求控制和地址保持仿射且不依赖运行时数组值。下一章将用 Presburger 算术精确说明这些整数集合能够使用哪些公式表达。