用多面体模型静态预测缓存缺失次数

这是我论文的主体部分翻译为中文后的结果。所以，可能会比较正式一点，行文也没有那么自然。

1. 背景知识

本章介绍本论文涉及的理论与实际工具基础。我们首先介绍多面体分析的核心概念，然后展示它们如何在缓存建模语境下应用。随后我们讨论软件工程的相关方面，包括所用工具、需求分析和项目的起点。

1.1. 多面体分析

多面体分析聚焦于嵌套的仿射循环。这些循环的循环变量称作归纳变量，它们从某个下界迭代至上界，每一步按固定常数递增。典型的仿射循环形式如下：

for i in lower..upper, step c
  ...

在多面体分析中，循环界必须为其外围循环归纳变量的仿射表达式。变量 ${𝑥}_1,{𝑥}_2,\dots$ 的仿射表达式即它们的线性组合加一个常数项，即 ${𝑎}_1{𝑥}_1+{𝑎}_2{𝑥}_2+\dots +𝑐$，其中 ${𝑎}_{𝑖}$ 为编译期常数。

循环迭代由其外围循环归纳变量的取值唯一标识。这些值组成一个向量，称为归纳向量，按从最外层到最内层排序。它的取值范围称为迭代域，记为 $\mathrm{𝒟︀}$。

作为例子，考虑如下循环嵌套：

for i in 0..10:
  for j in 0..i:
    a[i][j] *= 2   # S

语句 $𝑆$ 的归纳向量可表达为 $𝐱=\left(𝑖,𝑗\right)$，其迭代域为 $𝐷=\left\{\left(𝑖,𝑗\right)|0\le 𝑖\le 10,0\le 𝑗\le 𝑖\right\}$。

在不同迭代中，语句 $𝑆$ 访问不同的内存地址。为加以区分，我们用 $𝑆\left(𝐱\right)$ 表示在第 $𝐱=\left(𝑖,𝑗\right)$ 次迭代中执行的 $𝑆$ 实例，用 $𝑆\left[𝐱\right]$ 表示 $𝑆$ 在迭代 $𝐱$ 中访问的地址。在上面的例子中，$𝑆\left[𝐱\right]=\&𝑎\left[𝑖\right]\left[𝑗\right]$。

1.1.1. 计算依赖关系

考虑缓存行为时，我们将语句 $𝑆\left(𝐱\right)$ 视为依赖于先前语句 $𝑇\left(𝐲\right)$，当且仅当二者访问同一地址¹。现代缓存通常为 write-back 模式，因此我们不关心 $𝑆$ 和 $𝑇$ 是读还是写，因为任一操作都会把被访问数据引入缓存。

形式上，当以下条件成立时，$𝑆\left(𝐱\right)$ 依赖 $𝑇\left(𝐲\right)$：

1. $𝐱$ 和 $𝐲$ 分别位于迭代域 ${\mathrm{𝒟︀}}_{𝑆}$ 和 ${\mathrm{𝒟︀}}_{𝑇}$ 内；

2. $𝑆\left[𝐱\right]=𝑇\left[𝐲\right]$；

3. $𝑇\left(𝐲\right)$ 在 $𝑆\left(𝐱\right)$ 之前执行。

当 $𝑆$ 和 $𝑇$ 位于同一循环嵌套中，第三个条件等价于 $𝐱{>}_{\text{lex}}𝐲$，其中 ${>}_{\text{lex}}$ 是字典序比较。然而当 $𝑆$ 和 $𝑇$ 共享全部外围循环，但不包含彼此时，其含义便不再等价于 $𝐱{>}_{\text{lex}}𝐲$。复杂情形在 Section 2.4.1 中详细说明。

该定义将 $𝑆\left(𝐱\right)$ 与所有访问同一地址的 $𝑇\left(𝐲\right)$ 相关联，但对我们使用场景而言，只需取最近的一个。该实例为字典序最大的 $𝑇\left(𝐲\right)$，记为 $\text{𝖽𝖾𝗉𝗌}\left(𝑆\left(𝐱\right)\right)$。

$𝑆\left(𝐱\right)$ 也可能不依赖任何 $𝑇\left(𝐲\right)$。此时我们认为 $\text{𝖽𝖾𝗉𝗌}\left(𝑆\left(𝐱\right)\right)$ 未定义。

例如，在 Figure 1 中，当且仅当 $𝑗=𝑖$ 时，语句 $𝑆\left(𝑗\right)$ 依赖于语句 $𝑇\left(𝑖\right)$，故 $\text{𝖽𝖾𝗉𝗌}\left(𝑆\left(𝑗\right)\right)=𝑇\left(𝑗\right)$。另一方面，$𝑇\left(𝑖\right)$ 不依赖任何其他语句，故 $\text{𝖽𝖾𝗉𝗌}\left(𝑇\left(𝑖\right)\right)$ 处处未定义。

1.1.2. 复用距离

$𝑆\left(𝐱\right)$ 的复用距离是 $\text{𝖽𝖾𝗉𝗌}\left(𝑆\left(𝐱\right)\right)$ 与 $𝑆\left(𝐱\right)$ 之间的各语句所访问的不同地址个数，记为 $\text{𝖽𝗂𝗌𝗍}\left(𝑆\left(𝐱\right)\right)$。换言之，若假设每条缓存行只存放一个元素，这就是 $𝑆\left[𝐱\right]$ 与其上次使用之间被逐出的缓存行数量。

考虑 Figure 1 中的程序。$\text{𝖽𝗂𝗌𝗍}\left(𝑆\left(6\right)\right)$ 的值为 $9$，$\text{𝖽𝗂𝗌𝗍}\left(𝑆\left(5\right)\right)$ 为 $10$。Figure 2 以图形方式展示了该情形，其中橙色方块表示 load $𝑆\left(𝑗\right)$ 及其依赖 $𝑇\left(𝑗\right)$，蓝色方块代表它们之间访问的缓存行。注意当 $𝑗=5$ 时，地址 a[6] 被访问两次，但由于我们只关心不同的地址，它只被计算一次。

1.1.3. 缓存缺失计数

我们参考的是缓存模型 Falcon 的设置，假设缓存是全关联的、采用 LRU 替换策略，且每个数组元素占用整条缓存行。我们用 $𝐶$ 表示缓存容量，并逐个考虑每个语句 $𝑆$。

$𝑆$ 产生的 compulsory miss 数量，等于 $\text{𝖽𝖾𝗉𝗌}\left(𝑆\left(𝐱\right)\right)$ 未定义的归纳向量 $𝐱$ 的个数。

$𝑆$ 引起的 capacity miss 数量，为满足 $\text{𝖽𝗂𝗌𝗍}\left(𝑆\left(𝐱\right)\right)\ge 𝐶$ 的 $𝐱$ 个数。这个条件即 $𝑆\left[𝐱\right]$ 上次访问后，每条缓存行均已被逐出。

为高效统计满足上述约束的 $𝐱$，我们使用 Barvinok 算法，下面将介绍该算法。

1.2. Barvinok 算法

Barvinok 算法 [1] 用于计算多面体内的整点个数。

1.2.1. 多面体

$𝑛$ 维多面体 $𝑃$ 可视为 $𝑛$ 个变量上的不等式集合，每个不等式定义了整个空间 ${ℝ}^{𝑛}$ 的一半。多面体就是所有这些半空间的交集。该表示称为H 表示，其中 ‘H’ 代表 halfspace（半空间）。

形式上，多面体 $𝑃$ 的 H 表示由矩阵 $𝐴$ 与向量 $𝐛$ 定义，满足 $𝑃=\left\{𝐱\in {ℝ}^{𝑛}|𝐴𝐱+𝐛\ge 0\right\}$。除非另有说明，我们只考虑 $𝐴$、$𝐛$、$𝐱$ 每个元素均为整数的多面体。

例如，考虑 Figure 3 所示的三角形，它是一个二维多面体。它可由 3 个不等式表示：

各颜色的部分表示由每个不等式标出的半空间。

在每个 $𝑛$ 维多面体的顶点 $𝑣$ 处，至少有 $𝑛$ 个不等式变为等式。称这些不等式在 $𝑣$ 处活跃。在上面的例子中，前两个不等式在顶点 $\left(0,0\right)$ 处活跃。

对多面体 $𝑃$ 及其顶点 $𝑣$，$𝑣$ 处活跃的不等式构成另一个多面体，事实上这是一个锥。我们称其为 $𝑣$ 处的切锥。

1.2.2. 锥

锥是多面体的特殊情形。它们由从原点射出的射线构成。

形式上，锥 $𝐶$ 可用一组向量 $\left\{{𝐯}_{𝑖}\right\}$ 描述，其中 $𝐶=\left\{{\sum }_{𝑖}{𝜆}_{𝑖}{𝐯}_{𝑖}|{𝜆}_{𝑖}\ge 0\right\}$。这些向量 ${𝐯}_{𝑖}$ 称为生成元。该描述方法称为锥的V 表示。

锥 $𝐶$ 的生成元可组成一个矩阵，每个生成元占一列：

当 $𝑉$ 为方阵且 $𝑉$ 的行列式为 $\pm 1$ 时，称锥 $𝐶$ 是素模的。

H 表示下的 ${𝐶}^{°}=\left\{𝐱|𝑉𝐱\ge 0\right\}$ 称为 $𝐶$ 的对偶。

1.2.3. 算法概述

Figure 5 展示了 Barvinok 算法的总体结构。为获得图中多面体的整数计数 $10$，上述步骤需对其他所有切锥重复执行。

图中绿色箭头指代我们在 FPL 中实现的步骤。红色箭头指代当前实现中已修复的 bug，黑色箭头指代早已完备、我们未加修改即使用其功能。

该算法仅适用于满维多面体。对于低维多面体 $𝑃$，需要一个预处理步骤将其投影（project）到具有相同整数点数量的满维多面体 $𝑄$。

Barvinok 算法首先识别 $𝑄$ 每个顶点 $𝐮=\left({𝑢}_1,\dots ,{𝑢}_{𝑛}\right)$ 处的切锥 $𝐶$。然后它将 ${𝐶}^{°}$ 分解为素模锥 ${𝑈}_{𝑖}$ 的带符号求和。Figure 5 则直接对原始锥 $𝐶$ 进行分解，这同样是合法的，但此时分解中产生的低维锥同样需要加以考虑 [2]。

对于每个具有 $𝑚$ 个生成元 ${𝐯}_1,\dots ,{𝐯}_{𝑚}$ 的 $𝑛$ 维素模锥 ${𝑈}_{𝑖}$，算法随后推导一个含 $𝑛$ 个变量 ${𝑥}_1,\dots ,{𝑥}_{𝑛}$ 的有理函数，称为生成函数。该函数形式为

最后，算法求该函数在 $𝐱=1$ 处的极限，并将各结果求和以得到整数计数。

1.3. Fast Presburger Library

我们介绍项目中使用的数学库，即 Fast Presburger Library [3]，简称 FPL。

FPL 处理整数关系，即 Presburger 算术中仿射表达式的合取。等价地，整数关系也可视为整数多面体 $\left\{𝐱|𝐴𝐱+𝐛=0,𝐶𝐱+𝐝\ge 0\right\}$ 的 H 表示。

FPL 还支持Presburger 关系，即整数关系的有限并。该并的每个分量称为一个析取分量。

FPL 提供如下原语：

• 并与交；
• 集合之差；
• 空判定。

该库还提供各种辅助数学工具，如整数矩阵的规范形计算。后续各节将突出说明我们在实现中使用的这些 FPL 过程。

整数关系上的运算基于 Simplex 算法 [4] 的一种变体实现。通过开放对 Simplex 对象的运算，FPL 还提供了整数线性规划的功能。具体而言，FPL 可计算 $𝐤\cdot 𝐱+𝑏$ 的极小值和极大值，其中 $𝐱$ 属于整数关系 $𝑃$。

1.3.1. 变量类型

FPL 区分四种变量类型：

• Domain（定义域）变量，表示关系的输入；
• Range（值域）变量，表示关系的输出；
• Symbol（符号）变量，表示未知但固定的符号常数；
• Local（局部）变量，被存在量词修饰。

这种区分促使我们在库中将整数关系视为关系而非多面体。该设计使语义解释更为清晰，并便于关系的复合，后者在我们缓存分析 pass 中频繁使用。

例如，给定符号常数 $𝑁$，函数 $𝑦=\lfloor \frac{𝑥}{2}\rfloor +𝑁$ 可表示为如下关系：

在该关系中，$𝑥$ 是 domain 变量，$𝑦$ 是 range 变量，$𝑁$ 是 symbol 变量，$𝑒$ 是局部变量。该例子也展示了通过引入额外局部变量表示整数常系数除法的方法。

对 Presburger 关系，局部变量被限制在对其各析取分量中。一个析取分量无法访问在另一个析取分量中定义的局部变量。

1.3.2. 与原设计之偏离

FPL 的原始设计 [3] 采用精度渐进策略。计算从 16 位整数开始，发现溢出时提升到 64 位，再提升到任意精度整数。这种方式对缓存更友好，并能在常见情形下使用 SIMD 指令。

然而，MLIR 内 FPL 的上游实现并不包含此功能。该库中以任意精度整数类型 DynamicAPInt 表示所有整数。这一设计选择由两个原因驱动：

• 精度切换依赖 C++ 异常，而 LLVM 项目禁用了异常。

• SIMD intrinsics 不适合跨平台的可移植代码库。

因此，MLIR 版本的 FPL 优化较少，性能可能劣于 isl。但由于该库与 MLIR 深度集成，它仍然是我们项目的理想选择。

1.4. Clang IR

项目基于 MLIR（Multi-Level Intermediate Representation）实现，它是一种编译基础设施框架，支持自定义定义不同形式的中间表示（IR）。这些 IR 称为 dialect（方言）。

我们聚焦 Clang IR——一种为 clang C++ 编译器设计的 MLIR 方言，常简记为 cir。Clang IR 项目还提供前端，将 clang 生成的抽象语法树（AST）转换为 cir 形式的 MLIR 模块。

1.4.1. 结构特征

Clang IR 是静态单赋值（SSA）形式，且具有结构化控制流。

与 LLVM IR 以基本块间分支表示控制流、依赖分析恢复高级构造不同，Clang IR 通过携带区域的运算显式编码构造。例如，while 循环的典型形式为

cir.while %cond {
  loop body
}

一个 region 是基本块的容器，一个基本块包含一个运算列表。运算也可以拥有嵌套的 region。这种相互递归的设计在 Clang IR 中构成树形结构，其根是 cir.module 运算。

显式控制流运算简化了我们高度依赖循环结构的分析，因为不再需要支配分析来恢复循环结构。

1.4.2. $𝜑$ 节点

在 SSA 中，$𝜑$ 节点用于在控制流汇合点选择被执行的前驱块所提供的值。它们通常作为伪指令放置在汇合块开头。

在 MLIR 大多数方言中，$𝜑$ 节点的结果以基本块参数的形式编码，$𝜑$ 节点的操作则被看作结束各前驱块的 branch 指令的操作。

然而 Clang IR 目前未采用上述任一种 $𝜑$ 节点形式。对局部变量的读写被翻译为对栈地址的 load 和 store。因此，值合并通过内存状态隐式表示，而非在 SSA 中显式表示。

这使得识别循环的归纳变量更加困难，也使 Clang IR 需要预处理 pass，其中之一是分析常见的 for 循环模式。我们将在 Section 2.3.1 中更详细地讨论 IR 模式。

1.5. 需求分析

按项目提案，本项目只有一个交付物：一个静态分析 pass，使用多面体模型估计仿射程序的缓存缺失。

1.5.1. 问题范围

我们的分析仅限于仿射程序，遵循多面体分析中的标准定义：

• 循环界在编译期已知；

• 数组下标是归纳变量的仿射表达式；

• 控制流仅依赖归纳变量，不依赖运行期数据。

这些限制确保程序可用多面体模型表示。

1.5.2. 实现策略

基于 Section 1.1.3 中描述的缓存建模算法，项目可分为两部分：实现多面体缓存模型，以及完成 Barvinok 算法。

虽然 Barvinok 算法在概念上独立于缓存模型，但它依赖我们的缓存模型生成测试用例，以验证其正确性并检查边界情形的覆盖度。基于上述理由，两个组件以交替方式开发，缓存模型优先。

为指引开发，我们构建了如图 Figure 6 所示的依赖图，蓝色节点对应模型各阶段，绿色节点对应 Barvinok 算法的组件。Section 2.5 详细解释了每个组件。

我们的开发推进方式为反复选择需求已满足的节点，类似图的拓扑排序。由于缓存模型阶段为计数算法提供测试用例，故被优先。

1.5.3. 验证策略

正确性以增量方式检查。每个缓存模型阶段实现后，部分完成的分析被应用于 6 个小测试程序。中间结果随后与手工计算或缓存模拟器得到的期望结果比较。

实现完成后，系统在另外 28 个程序上评估，以检验正确性、精度与效率。评估细节见 Section 3。

1.5.4. 库与工具

调试与测试高度依赖 LLVM 基础设施。特别是 LLVM 的言机制被广泛使用，用于验证数学过程的前置条件与后置条件。Barvinok 算法及 FPL 中现有方法的单元测试与回归测试使用 llvm-lit——LLVM 内的测试工具——来开展。

由于带调试信息的 LLVM 编译内存与时间开销大，GNU 调试工具 gdb 仅偶尔使用。

静态分析工具如 clang-tidy 和 clangd 用于代码 lint 与维护代码质量。版本管理使用 git，仓库定期备份到我们 GitHub 上的 Clang IR fork。

1.6. 起点

项目开始之前，我已熟悉 C++、编译器内部机制、MLIR 框架及 Clang IR 仓库。我在 Part IB 团队项目中积累的 Clang IR 经验大有裨益。暑假期间，我研读了多面体分析涉及的数学知识，并学习了 Barvinok 算法。

项目基于 Clang IR git commit e4003cd3a263。该 commit 于 2024 年 11 月 10 日合并，但我此前未为本项目编写任何代码，直到 2025 年 10 月。项目期间未再从主分支 pull。

2. 具体实现

2.1. 工作流程概述

我们的分析基于 Clang IR 项目——它既是 C 前端，也是一个 MLIR 方言。其工作流程总结在 Figure 7 中。

我们从 Clang IR 出发，将其部分提升为 Affine IR。该步骤识别归纳变量及其迭代域，为后续分析做准备。

在提升后的 IR 中，我们将导致缓存缺失的数组下标建模为多面体中的整数点。这通过分析循环内部的数组访问运算实现：计算下标的符号表示，并构造 Presburger 关系。

最终，我们对多面体应用 Barvinok 算法计数其中的整数点，从而得到估计的缓存缺失次数。

2.2. 仓库概述

Figure 8 概述了我们对 Clang IR 仓库的修改。为简洁起见，图中省略了开发用 shell 脚本和小于十行的微小改动。新引入的仓库文件在图中以蓝色高亮。

我们的修改与上一节描述的三阶段工作流相绑定。代码结构按阶段清晰分离，各阶段位于独立的源文件中。

在文件 RaiseToAffine.cpp 中，我们将 Clang IR 提升为 Affine IR，如 Section 2.3.1 所述。它识别 C 语言中常见的 for 循环模式，并翻译为仿射循环。同时生成胶水 IR，以将两种不同方言集成到同一 MLIR 模块中。

RevertLICM.cpp、FindOffset.cpp 和 ComputeDeps.cpp 中的 pass 按此顺序执行，以将数组下标间的关系建模为整数多面体。RevertLICM.cpp 重构 IR 以简化 FindOffset.cpp 的执行，后者用分析所得的下标注释相关运算。最后一个 pass ComputeDeps.cpp 将数组下标上的关系翻译为多面体。

计数步骤实现于 Barvinok.cpp，它消费建模步骤中的多面体，并给出缓存缺失次数估计。我们基于 MLIR 中现有的未完成工作，在该文件中完成了 Barvinok 算法。

除这些核心组件外，还修改了 Clang IR 仓库中已有的文件，以便将我们的 pass 整合进 MLIR 框架并收集性能数据。

总体而言，我们的仓库体现了需求分析 (Section 1.5) 中识别的模块化分解，并在此基础上扩展以应对项目复杂度。

2.3. 预处理 pass

2.3.1. IR 提升

在这一阶段，我们将 Clang IR 中的仿射循环提升为 MLIR 的 affine 方言，使后续 pass 能够分析循环结构及其归纳变量。

我们关注如下经典 C 循环结构。

for (i = a; i < n; i++)

在 Clang IR 中，每个全局变量都被赋予一个栈地址（一个 cir.alloca 运算）。循环被生成为 cir.for 运算。该循环有三个 region，分别为：cond 对应循环条件 i < n，body 对应循环体，step 对应增量 i++。初始化语句 i = a 被放置在 cir.for 运算之前，因为它仅在进入循环前执行一次。

为了提升仿射循环，我们匹配 Figure 9 所示的模式，提取下界 %a、上界 %n 和归纳变量%i。随后创建具有相同界与相同 body region 的 affine.for 运算。

一个挑战是 Clang IR 循环变量 %i 与 affine 方言循环变量 %arg 之间的类型不匹配。Clang IR 拥有自己的类型 !cir.int<s, 32>（带符号 32 位整数），而 affine 方言要求使用 MLIR 内置类型 index 作为循环变量。因此我们不能直接将 %i 的用途替换为 %arg。

为此，我们向 Clang IR 扩展了一个类型转换运算 cir.from_index，用于将 index 类型转换为所需的 Clang IR 整数类型，使两种 IR 能够互操作。类似地，我们引入了 cir.index_cast 运算，将 Clang IR 类型转换为 index。

我们还处理如下形式的反向循环

for (i = a; i >= n; i--)

将其规范化为等价的递增形式

for (j = n; j < a + 1; j++)

并将循环内 i 的全部用途替换为 n + a - j - 1。

规范化对于 Section 2.4.1 中引入的建模阶段的字典序比较的正确性至关重要。

2.3.2. 发现偏移与基地址

对数组 b[i][j] 的访问可分解为一个 base（基）b 和一个 offset（偏移）$\left(𝑖,𝑗\right)$。缓存模型需要我们找到二者：基用于区分不同数组，相当于一次基本的别名分析；偏移用于计算依赖关系。数组访问语句的偏移与基在 FindOffset.cpp 中的预处理 pass 中被识别。

访问 b[i][j] 在 Clang IR 中如下表示，其中多维访问被降为一系列 cir.get_element 运算³, 每个作用于单一维度。

%1 = cir.get_element %b[%i]
%2 = cir.get_element %1[%j]
%result = cir.load %2

我们检查 load 运算操作数（类似地，store 的地址操作数）的定义运算，期望得到一个 get_element %addr[%x]。我们检查包围该运算的循环嵌套深度 $𝑑$，并构造仿射表达式

其中 $𝑐$ 和 ${𝑎}_{𝑖}$ 初始设为零。

系数通过递归沿 %x 的 use-def 链向上遍历，沿途处理算术运算获得：

• 对于携带常数 $𝑣$ 的 cir.int，我们将 $𝑐$ 增加 $𝑣$；

• 对于对应 ${𝑥}_{𝑖}$ 的值 %i，我们将 ${𝑎}_{𝑖}$ 增加 1；

• 对于加减运算 cir.binop add（或 sub），我们将两个操作数的仿射表达式相加；

• 对于乘常数 $𝑚$ 的乘法 cir.binop mul，我们将所有系数与常数乘以 $𝑚$。

其他所有表达式都会失败，并被我们的分析 pass 拒绝，因为它们已不再仿射。

为找到基，%addr 也递归处理。如果 %addr 本身由一个 get_element 运算定义，我们就递归检查其地址，即沿地址链向上遍历，直到它是 alloca 或全局数组为止。

我们在 Figure 10 中给出一个示例以演示该过程。它是从 Polybench 的 ludcmp.c 获取的 Clang IR 适配片段。

我们的分析确定 %70 以偏移 $\left(119-𝑖,𝑗\right)$ 访问数组 A。基 A 通过查看地址操作数 %69 以及 %A（紫色部分）获得。由于 get_element 位于两个嵌套循环内，我们知道偏移是两个归纳变量的仿射函数。第二维的偏移由检查 %68 计算得到——它是一个直接引用 $𝑗$ 的 from_index 运算（蓝色部分）。第一维的偏移类似获得，在到达 $𝑖$ 之前额外经过一个 sub 表达式（绿色部分）。

该 pass 不处理经由任意指针的访问，因为那将需要别名分析，显著增加实现复杂度。

在 pass 之前，我们进行常量折叠与内联，以简化 IR 并减少对复杂跨过程程分析的需求。

每个访问的基与偏移以附加在每次 get_element 运算上的属性形式表示。

对于基，我们为每个 alloca 或全局数组分配一个整数作为标识，并将 array_base 属性附加到 get_element 运算上。该属性是首次引入 Clang IR 的。我们不能直接在属性中存储运算或 SSA 值，因为它们在 MLIR 中不可序列化，会被拒绝。

类似地，我们为数组偏移添加了 array_offset 属性。该属性存储仿射映射（affine map），MLIR 原生支持。

作为例子，pass 之后的 get_element 运算可能形如：

%17 = cir.get_element %5[%8] {
  #array_base = 1,
  #array_offset = (d0, d1) -> (d0)
}

二维 induction vector (d0, d1) 表示该运算嵌套于两个循环中，并以外层循环的归纳变量索引编号为 $1$ 的数组。

2.3.3. 恢复 get_element 运算的局部性

如上一节所示，数组访问信息关联在 get_element 运算上，偏移仿射映射的维度由该运算所在的循环嵌套决定。

我们的分析期望 get_element 运算位于访问语句所在的同一循环嵌套中，以便引用外围循环的全部归纳变量。但并非总是如此。考虑 Figure 11, (a) 所示的 IR 结构：

load 嵌套于两个循环中，其 induction vector 为 $\left(𝑖,𝑗\right)$，但其 get_element 仅嵌套于一个循环中，在我们的分析中认为其 induction vector 为 $𝑗$。维数不匹配违背了我们的假设。

在代码生成中，这种结构通常不会出现。get_element 运算紧邻于 load 或 store 之前，如 Figure 11, (b) 所示。该结构产生于内层 get_element 运算因循环不变量提取 (LICM) 被提升到循环之外。随后，公共子表达式消除 (CSE) 可能合并这样两个运算，使其与其使用场景进一步分离。

因此，解决该问题的最直接方案是在 Clang IR 中禁用 LICM 与 CSE。考虑到未来与 MLIR 的集成，我们还实现了 RevertLICM pass，通过克隆 get_element 运算使过程还原，确保每个 load 都直接由一个 get_element 前置。

2.4. 缓存缺失计数分析

2.4.1. 计算必要缺失

为计算必要缺失，我们识别其访问地址此前从未被访问过的语句实例集合。

我们首先识别所有数组访问语句的集合，记为 $\mathrm{ℒ︀}$。当 $𝑆$ 是一个 cir.load 或 cir.store 运算，且其地址操作数为带有基与偏移属性的 cir.get_element 时，称其访问数组。

随后，我们按照语句在程序中出现顺序，给 $\mathrm{ℒ︀}$ 中每个语句分配一个正整数，称为 lexical index（字典序索引），以便利后续步骤的字典序比较。越早出现的语句获得较小的索引。$𝑆\in \mathrm{ℒ︀}$ 的字典序索引记为 ${𝑖}_{𝑆}$。

我们逐个考虑 $𝑆\in \mathrm{ℒ︀}$ 中的每个语句。在 Section 1.1.1 中，我们定义了 $𝑆\left(𝐱\right)$ 与另一访问运算 $𝑇\left(𝐲\right)$ 之间的依赖概念。我们枚举所有 $𝑇\in \mathrm{ℒ︀}$，并构造依赖关系：

如 Section 1.1.1 所述，在我们的缓存模型中，$𝑆$ 依赖 $𝑇$，当二者访问同一地址且 $𝑇$ 在 $𝑆$ 之前执行时。

在 Section 1.3 中，我们指出 FPL 仅支持仿射约束。现在我们说明依赖条件确实可以用仿射约束表达。

边界条件以及 $𝑆\left[𝐱\right]=𝑇\left[𝐲\right]$ 的条件是仿射的，因为所有循环界与数组访问都被假设为仿射。

为确保 $𝑆\left(𝐱\right)$ 在 $𝑇\left(𝐲\right)$ 之后执行，只需要求 $𝑆\left(𝐱\right){>}_{\text{lex}}𝑇\left(𝐲\right)$，因为所有循环均已如 Section 2.3.1 所述规范化为递增循环。设 $𝑆$ 与 $𝑇$ 的共同循环深度为 $𝑑$。当 $𝑆$ 和 $𝑇$ 位于同一循环嵌套中，我们按定义构造字典序比较：

当并非如此时，我们在穷尽所有公共循环后退回字典序。仅当 $𝑇$ 字典序在 $𝑆$ 之前时，我们将上述关系与以下析取式取并：

我们需要找到 $\text{𝖽𝖾𝗉𝗌}\left(𝑆\left(𝐱\right)\right)$——在所有考察过的 $𝑇$ 中，$𝑆\left(𝐱\right)$ 最新、即字典序最大的依赖。由于它们可能位于不同深度、不同嵌套的循环中，它们的归纳变量无法直接比较。我们已说明如何比较两个实例 $𝑆\left(𝐱\right)$ 与 $𝑇\left(𝐲\right)$ 的执行顺序，但要更一般地比较候选，我们必须将向量嵌入一个公共空间，以同时编码字典序与循环结构。

设 $𝑛$ 为所有候选语句 $𝑇$ 中最大嵌套循环深度，并定义一个循环的字典序索引为其内部语句最小字典序索引。假设 $𝑇\left(𝐲\right)$ 的字典序索引为 ${𝑖}_{𝑇}$，且嵌套于索引为 ${𝑖}_0,\dots ,{𝑖}_{𝑚}$ 的循环中。我们将 $𝐲=\left({𝑦}_0,\dots ,{𝑦}_{𝑚}\right)$ 提升为

在嵌入中，每一对 ${𝑖}_{𝑚},{𝑦}_{𝑚}$ 同时编码了循环身份与对应归纳变量的取值。填充项 ${𝑖}_{𝑇},0$ 表示没有循环，用于维持不同深度语句之间的正确字典序。最后的 ${𝑖}_{𝑇}$ 作为同一循环嵌套内语句的排序标准。

乍看之下，似乎将 $𝐲$ 提升为以下形式即可：

然而这一变体对非完全嵌套的循环不成立，因为它缺少循环层级之外语句的字典序信息。考虑如下示例：

for i:
  for j:
    load a[i]     # T1: index = 1
  load a[j]       # T2: index = 2

在此情形下，若在 ${𝑦}_{𝑚}$ 之后填充零，我们将得到

当 $𝑖$ 取相同值时，${𝑇}_1$ 应字典序位于 ${𝑇}_2$ 之前，但提升后的向量却暗示相反。

将全部依赖候选 $𝑇\left(𝐲\right)$ 提升进公共空间后，我们使用 FPL 计算字典序最大值以获得 $\text{𝖽𝖾𝗉𝗌}\left(𝑆\left(𝐱\right)\right)$。最大化过程在 $𝐱$ 的定义域上是分段的，因此 FPL 返回一组 pieces，即二元组 $\left(𝐷,𝐳\left(𝐱\right)\right)$，其中 $𝐳\left(𝐱\right)$ 是作为 $𝐱$ 函数表达的提升后最大值，$𝐷$ 是 $𝐳\left(𝐱\right)$ 有效的 $𝐱$ 取值范围。由于 ${𝑖}_{𝑇}$ 唯一，提升过程可逆，我们可将任意 $𝐳\left(𝐱\right)$ 降回 $𝑇\left(𝐲\left(𝐱\right)\right)$。

程序返回的每个 $𝐷$ 都对应一个存在依赖的区域。将 $𝑆$ 的迭代域减去所有这样的 $𝐷$，得到地址此前未被访问过的区域 $𝑈$。因此 $𝑈$ 的整数点个数即等于必要缺失数量，可用 Barvinok 算法计算。

2.4.2. 计算复用距离

复用距离 $\text{𝖽𝗂𝗌𝗍}\left(𝑆\left(𝐱\right)\right)$ 是严格位于 $\text{𝖽𝖾𝗉𝗌}\left(𝑆\left(𝐱\right)\right)$ 与 $𝑆\left(𝐱\right)$ 之间被访问的不同缓存行数量。由于 $\text{𝖽𝖾𝗉𝗌}\left(𝑆\left(𝐱\right)\right)$ 在 $𝐱$ 的迭代域上分段定义，我们必须枚举上一节中计算出的全部 piece $\left(𝐷,𝐳\left(𝐱\right)\right)$ 以及降回的语句 $𝑇\left(𝐲\right)$。

第一步，我们收集可能在 $𝑆\left(𝐱\right)$ 与 $𝑇\left(𝐲\right)$ 之间执行的语句，即所有被包含在同时容纳 $𝑆$ 与 $𝑇$ 的最小公共 region 内的数组访问语句。这些语句不仅限于字典序索引介于 ${𝑖}_{𝑆}$ 与 ${𝑖}_{𝑇}$ 之间的语句，因为位于 $𝑆$ 之后但仍在 $𝑆$ 同区域内执行的语句也可能在 $𝑆\left(𝐱\right)$ 与 $𝑇\left(𝐲\right)$ 之间执行。对 $𝑇$ 也有类似观察。

每个收集的语句 $𝑈$ 关联一个 induction vector $𝐰$。我们寻找使 $𝑈$ 在 $𝑇\left(𝐲\right)$ 之后、$𝑆\left(𝐱\right)$ 之前执行的 $𝐰$ 取值范围。这些点称为 reuse instances（复用实例）。每个这样的 $𝐰$ 对应 $𝑈$ 的一个在 $𝑆\left(𝐱\right)$ 与 $𝑇\left(𝐲\right)$ 之间访问内存的实例，当其映射到不同缓存行时，即对复用距离做出贡献。

形式上，

这里 ${\mathrm{𝒟︀}}_{𝐰}$ 是 $𝐰$ 的迭代域，${<}_{\text{lex}}$ 表示字典序优先，定义见上一节。

为计算 $𝑈$ 访问的内存位置集合，我们将关系 $\text{reuseInstance}\left(𝑈,𝑆\left(𝐱\right),𝑇\left(𝐲\right)\right)$ 与 $𝑈$ 的访问函数（一个仿射映射）相复合。然后跨所有 $𝑈$ 取并，得到 $𝑆\left(𝐱\right)$ 与 $𝑇\left(𝐲\right)$ 之间访问的全部内存位置集合，记为 $\text{total}\left(𝑆\left(𝐱\right),𝑇\left(𝐲\right)\right)$。

若假设缓存行大小 $𝐿$ 为 1，则有

由于 $\text{total}$ 关系由仿射等式与不等式构成，可视为多面体的 H 表示。因此我们可用 Barvinok 算法计数其中的整数点。

该多面体对 $𝐱$ 是参数化的。此时 Barvinok 算法给出的计数不是单一整数，而是关于 $𝐱$ 的 quasi-polynomial（准多项式），其形式为

其中 ${𝑐}_{𝑖}$、${𝐤}_{𝑖𝑗}$ 与 ${𝑏}_{𝑖𝑗}$ 为算法计算的有理数。该形式对下一节引入的容量缺失计数至关重要。

2.4.3. 计算容量缺失

为获得容量 $𝐶$ 的缓存的容量缺失计数，我们逐个考虑 $𝑆\in \mathrm{ℒ︀}$，并统计满足 $\text{𝖽𝗂𝗌𝗍}\left(𝑆\left(𝐱\right)\right)\ge 𝐶$ 的 induction vector $𝐱$ 数量。

当准多项式 $\text{𝖽𝗂𝗌𝗍}\left(𝑆\left(𝐱\right)\right)$ 的每个乘积至多含一项时，条件 $\text{𝖽𝗂𝗌𝗍}\left(𝑆\left(𝐱\right)\right)\ge 𝐶$ 可转化为一个多面体，从而可用 Barvinok 算法高效求解。但更一般的情形下，甚至判定是否存在这样的 $𝐱$ 就是 NP-hard [5]。因此我们必须枚举 $𝐱=\left({𝑥}_1,\dots ,{𝑥}_{𝑛}\right)$ 以获得精确计数。

我们按维度逐一枚举。给定 ${𝑥}_1,\dots ,{𝑥}_{𝑖}$ 的固定值，可借助 Simplex 算法确定 ${𝑥}_{𝑖+1}$ 的取值范围 $\left[𝑙,𝑟\right]$。然后遍历其中每个值 $𝑘\in \left[𝑙,𝑟\right]$，令 ${𝑥}_{𝑖+1}$ 为 $𝑘$，并递归枚举 ${𝑥}_{𝑖+2}$。

我们随时在 PWMA 函数被简化为每个乘积至多一项时停止递归过程，此时调用 Barvinok 算法。出于性能考虑，若剩余变量的可能取值不超过 10 个，则继续枚举而非调用更为复杂的 Barvinok 过程。

2.4.4. 支持可配置的缓存行大小

前述讨论中我们假设每个数组元素占用一整条缓存行。现在我们说明如何支持缓存行大小 $𝐿>1$。

我们以二维数组 a[N][M] 为例。数组访问 a[i][j] 等价于访问地址 &a + i * M + j，其映射到缓存行 $\lfloor \frac{𝑖𝑀+𝑗}{𝐿}\rfloor$。特别地，当假设 $𝑀$ 是 $𝐿$ 的倍数时，我们只需将最后一维 $𝑗$ 替换为 $\lfloor \frac{𝑗}{𝐿}\rfloor$。

然而我们对 $𝐿>1$ 的支持是有限的。引入取整除法会引入 local 变量，导致生成函数变长，且枚举变得不可避免。即使对小型程序、$𝐿=3$，我们的实现也无法在 600 秒内终止。

2.5. Barvinok 算法

我们已在 Figure 5 中给出了 Barvinok 算法的概述。本节说明我们实现的细节。

2.5.1. 非参数化投影

我们从一个非参数化的 $𝑑$ 维多面体（既有不等式又有等式）开始：

由于 Barvinok 算法作用于满维多面体，因此需要进行 projection（投影），以找到一个新的 ${𝑑}^{\prime }$ 维多面体 $𝑄$，使其整数点数量与 $𝑃$ 相同，且 $𝑄$ 填满整个 ${\mathbb{Z}}^{{𝑑}^{\prime }}$。这意味着 $𝑄$ 不能含任何等式。

但其逆命题不成立：即便 $𝑄$ 不含等式，也不意味着 $𝑄$ 是满维的。例如，考虑 ${\mathbb{Z}}^2$ 中的如下多面体：

这显然表明了一个等式 $𝑥=𝑦$，故其位于 ${\mathbb{Z}}^2$ 的一个 1 维子空间内。

我们通过预处理 $𝑃$ 来防止这种情况。对每个不等式 ${𝐷}_{𝑖,:}\cdot 𝐱\le {𝐟}_{𝑖}$，我们在约束 $𝐴𝐱=𝐜$ 与 $𝐷𝐱\le 𝐟$ 下计算 ${𝐷}_{𝑖,:}\cdot 𝐱$ 的最小值。这由 FPL 提供的 Simplex 算法完成。当最小值等于 ${𝐟}_{𝑖}$ 时，我们知道该不等式实为等式。

随后我们设法消除所有等式 $𝐴𝐱=𝐜$。考虑 $𝐴$ 的 null space（零子空间），其定义为

它是一个向量空间。我们寻找一个整数基，使其张成向量空间 $\text{null}\left(𝐴\right)\cap {\mathbb{Z}}^{𝑚}$：${𝐯}_1,{𝐯}_2,\dots ,{𝐯}_{𝑛}$。它们构成一个矩阵：

于是，方程组 $𝐴𝐱=𝐜$ 的任意解 $𝐱$ 都可表示为

其中 ${𝐱}_0$ 为一个 particular solution（特解），即满足方程组的任意整数解。

$𝐱$ 与 $𝐲$ 之间存在双射。此外，当 $𝐲$ 是整数向量时，$𝐱$ 亦然。其逆也成立：我们有 $𝐲={𝑉}^{-1}\left(𝐱-{𝐱}_0\right)$。由于 $𝑉$ 素模而 ${𝑉}^{-1}$ 因此为整数矩阵，只要 $𝐱$ 是整数向量，$𝐲$ 就是整数向量。由于该双射保持整数性，我们可计数向量 $𝐲$ 而非向量 $𝐱$，计数结果不变。

若我们将多面体 $𝑃$ 内整数点个数记为 $\#𝑃$，则有

由此，我们获得投影得到的合适 $𝑄$，其中 ${𝐷}^{\prime }=𝐷𝑉$，${𝐟}^{\prime }=𝐟-𝐷{𝑥}_0$。下面说明如何寻找 $\text{null}\left(𝐴\right)$ 的基与特解 ${𝐱}_0$。

2.5.2. 零子空间的整数基

寻找实值矩阵 $𝑀\in {ℝ}^{𝑛\times 𝑚}$ 零子空间基时，我们通常将 $𝑀$ 化为 row-echelon form（行阶梯形）。对整数矩阵 $𝐴\in {\mathbb{Z}}^{𝑛\times 𝑚}$，我们需要一个保持整数性的类似概念。这导出了 Hermite normal form（赫米特规范形）与 unimodular matrices（素模矩阵）。

当整数矩阵的行列式为 $\pm 1$ 时称其为 unimodular。素模矩阵的逆也是整数矩阵。这是因为

其中 $\text{adj}\left(𝑀\right)$ 是 $𝑀$ 的伴随矩阵（adjugate）。按定义它各元素均为整数：每个元素是 $𝑀$ 的子矩阵行列式。因此 ${𝑀}^{-1}$ 各元素亦为整数。Figure 12 给出了一个素模矩阵及其逆的实例。

整数矩阵 $𝐴$ 的 Hermite normal form 是满足如下性质的矩阵 $𝐻$：

• 存在一个素模矩阵 $𝑈$，使得 $𝐻=𝑈𝐴$；

• 每行中第一个非零元素，称为 pivot（主元），若存在则为正；

• $𝐻$ 为上三角形，即主元下方的元素为零；

• 主元上方的元素为非负且严格小于主元。

Figure 13 给出了 Hermite normal form 的实例。

FPL 提供计算整数矩阵 $𝑀$ Hermite normal form 的过程。它同时返回 $𝐻$ 与 $𝑈$。

对 $𝑛\times 𝑚$ 矩阵 $𝐴$，当 $𝑚\le 𝑛$ 且 $𝐴$ 列满秩时，零子空间仅含一点，即零向量。故我们考虑 $𝑚>𝑛$ 的情形。

为寻找 $\text{null}\left(𝐴\right)\cap {\mathbb{Z}}^{𝑚}$ 的基，我们计算 ${𝐴}^{𝑇}$ 的 Hermite normal form $𝐻$ 及其对应的素模矩阵 $𝑈$。于是 $𝑈{𝐴}^{𝑇}=𝐻$，故 $𝐴{𝑈}^{𝑇}={𝐻}^{𝑇}$。

由于 $𝑈$ 可逆，我们可知 $\text{rank}\left(𝐴\right)=\text{rank}\left(𝐻\right)$，记为 $𝑟$。由于 $𝐻$ 为上三角形，其末 $𝑚-𝑟$ 行必全为零。于是 ${𝑈}^{𝑇}$ 末 $𝑚-𝑟$ 列 ${𝐮}_{𝑟+1},\dots ,{𝐮}_{𝑚}$ 为整数，且满足 $𝐴{𝐮}_{𝑗}={𝐻}_{:,𝑗}^{𝑇}=0$，故位于零子空间。向量 ${𝐮}_{𝑟+1},\dots ,{𝐮}_{𝑚}$ 彼此线性无关，共 $𝑚-𝑟$ 个，等于零子空间的维数。故它们构成 $\text{null}\left(𝐴\right)\cap {\mathbb{Z}}^{𝑚}$ 的基。