编译器工程师眼中的好代码：Loop Interchange

2022 年 8 月 05 日
本文字数：4518 字
阅读完需：约 15 分钟

本文分享自华为云社区《编译器工程师眼中的好代码（1）：Loop Interchange》，作者：毕昇小助手。

编者按：C/C++代码在编译时，编译器将源码翻译成 CPU 可识别的指令序列并生成可执行代码，而最终代码的运行效率取决于由编译器生成的可执行代码。在大部分情况下，编写源代码时就已经决定了程序可以在何种程度下被编译器优化。即使对源代码做微小改动也可能会对编译器生成的代码运行效率产生重大影响。因此，源代码的优化可以在一定程度上帮助编译器生成更高效的可执行代码。

本文将以 Loop Interchange 的场景为例，讲述在编写代码时可以拿到更优性能的书写方式。

1. Loop Interchange 相关基本概念

1.1 访问局部性

访问局部性指的是在计算机科学领域中应用程序在访问内存的时候，倾向于访问内存中较为靠近的值。这种局部性是出现在计算机系统中的一种可预测行为，我们可以利用系统的这种强访问局部性来进行性能优化。访问局部性分为三种基本形式，分别为时间局部性、空间局部性、循序局部性。

而本文主要讲述的 Loop Interchange 主要是利用了空间局部性。空间局部性指的是，最近引用过的内存位置以及其周边的内存位置容易再次被使用。比较常见于循环中，比如在一个数组中，如果第 3 个元素在上一个循环中被使用，那么本次循环中极有可能会使用第 4 个元素;如果本次循环确实使用第 4 个元素，就是命中上一次迭代所 prefetch 到的 cache 数据。

所以对于数组循环运算，可以利用空间局部性这一特征，保证两次相邻循环中对数组元素的访问在内存上是更加靠近的，即循环访问数组中的元素时 stride 越小，相应的性能可能会有所优化。

那么，数组在内存上是如何存储的呢？

1.2 行主和列主

Row-major 和 Column-major 是两种将多维数组存储在线性存储中的方式。数组的元素在内存中是连续的;Row-major ordering 代表行的连续元素在内存中彼此相邻，而 Column-major ordering 则是代表列的连续元素彼此相邻，如下图所示。

虽然 Row 和 Column 的名称看起来像是特指二维数组，但是 Row-major 和 Column-major 也可以推广适用于任何维度的数组。

那么在 C/C++中，数组是以以上哪种方式存储的呢？

举一个小例子，用 cachegrind 工具来展示 C 使用两种不同的访问形式的 CPU 的 cache 丢失率对比。

按行访问：

#include <stdio.h>
int main(){
size_t i,j;
const size_t dim = 1024 ;
int matrix [dim][dim];
for (i=0;i< dim; i++)
for (j=0;j <dim;j++)
matrix[i][j]= i*j;
return 0;
}

复制代码

按列访问：

#include <stdio.h>
int main(){
size_t i,j;
const size_t dim = 1024 ;
int matrix [dim][dim];
for (i=0;i< dim; i++){
for (j=0;j <dim;j++){
matrix[j][i]= i*j;
}
}
return 0;
}

复制代码

根据上述 C 代码中对相同数组的两种不同访问方式时 cache 丢失率的对比，可以说明在 C/C++代码中，数组是以 Row-major 形式储存的。也就是说，如果前一步访问了 a[i][j]，那么对 a[i][j+1]的访问会命中 cache。这样就不会执行对主存储器的访问，而 cache 比主内存快，因此遵循相应编程语言的储存形式使其可以命中 cache 可能会带来优化。

至于其他常用的编程语言，Fortran、MATLAB 等则是默认 Column-major 形式。

1.3 Loop Interchange

Loop Interchange 利用系统倾向于访问内存中较为靠近的值的特征以及 C/C++ Row-major 的特点，通过改变循环嵌套中两个循环之间的执行顺序，增加整体代码空间局部性。此外，它还可以启用其他重要的代码转换，例如，Loop Reordering 就是 Loop Interchange 扩展到两个以上循环被重新排序时的优化。在 LLVM 中，Loop Interchange 需要通过使能-mllvm -enable-loopinterchange 选项启用。

2. 优化示例

2.1 基础场景

简单看下面一个矩阵运算的示例：

原始代码：

for(int i = 0; i < 2048; i++) {
for(int j = 0; j < 1024; j++) {
for(int k = 0; k < 1024; k++) {
C[i * 1024 + j] += A[i * 1024 + k] * B[k * 1024 + j];
}
}
}

复制代码

试着把 jk 两层循环进行 Loop Interchange 之后的代码：

for(int i = 0; i < 2048; i++) {
for(int k = 0; k < 1024; k++) {
for(int j = 0; j < 1024; j++) {
C[i * 1024 + j] += A[i * 1024 + k] * B[k * 1024 + j];
}
}
}

复制代码

可以发现，在原始代码中，最内层的 k 每次迭代，C 要访问的数据不变，A 每次访问的 stride 为 1，大概率命中 cache，但 B 由于每次访问的 stride 为 1024，几乎每次都会 cache miss。

Loop Interchange 之后，j 位于最内层循环，每次迭代时 A 每次要访问的数据不变，C 和 B 每次访问的 stride 为 1，都会有很大概率命中 cache，cache 命中率大大增加。

那么 cache 命中率是否真的增加，以及两者的性能又如何呢？

原始代码：

$ time -p ./a.out

复制代码

$ sudo perf stat -r 3 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-loads ./a.out

复制代码

Loop Interchange 后的结果如下：

$ time -p ./a.out

复制代码

$ sudo perf stat -r 3 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-loads ./a.out

复制代码

两者相比：

L1-dcache-loads 的数目差不多，因为要访问的数据总量差不多；

L1-dcache-load-misses 所占 L1-dcache-loads 的比例在进行 loop interchange 代码修改后降低了将近 10 倍。

同时，性能数据上也能带来接近 9.5%的性能提升。

2.2 特殊场景

当然，在实际使用时，并不是所有的场景都是如 2.1 中所示的那种工整的可 Loop Interchange 场景。

for ( int i = 0; i < N; ++ i )
{
if( I[i] != 1 ) continue;
for ( int m = 0; m < M; ++ m )
{
Res2 = res[m][i] * res[m][i];
norm[m] += Res2;
}
}

复制代码

如上述场景，如果 N 是超大数组，那么 Loop Interchange 理论上可以带来较大收益;但由于两层循环中间增加一个分支判断，导致原本可以 Loop Interchange 的场景无法实现。

针对这种场景，可以考虑将中间的分支判断逻辑剥离，可以先保证 Loop Interchange 使得数组 res 在连续内存上进行访问;至于中间的判断分支逻辑，可以在 Loop Interchange 两层循环后再进行回退。

for ( int m = 0; m < M; ++ m )
{
for ( int i = 0; i < N; ++ i)
{
Res2 = res[m][i] * res[m][i];
norm[m] += Res2;
if( I[i] != 1 ) //补充逻辑，保证源代码语义
{
norm[m] -= Res2;
continue;
}
}
}

复制代码

当然，这样的源码修改也需要考虑 cost 是否值得，如果该 if 分支进入频率非常高，那么之后回退带来的 cost 也会较大，可能就需要重新考虑 Loop Interchange 是否值得;反之，如果分支进入频率非常低，那么 Loop Interchange 的实现还是可以带来可观的收益的。

3. 毕昇编译器对 Loop Interchange pass 社区的贡献

毕昇编译器团队在 llvm 社区中对 Loop Interchange pass 也做出了不小的贡献。团队从 legality、profitability 等方面对 Loop Interchange pass 做了全方位的增强，同时也对该 pass 所支持的场景做了大量的扩展。在 Loop Interchange 方面，近两年来团队小伙伴为社区提供了二十余个主要的 patch，包含 Loop Interchange，以及相关的 dependence analysis、loop cache analysis、delinearization 等分析和优化的增强。简单举几个例子：

D114916 [环路交换] 启用具有多个外部环路输入的环路交换（https://reviews.llvm.org/D114916)
D114917 [环路交换] 启用具有多个内部环路的环路交换(https://reviews.llvm.org/D1149167)

这两个 patch 将 Loop Interchange 的应用场景扩展到内层或者外层循环中包含不止一个 induction variable 的情况：

for (c = 0, e = 1; c + e < 150; c++, e++) {
d = 5;
for (; d; d--)
a |= b[d + e][c + 9];
}
}

复制代码

D118073 [IVDescriptor] Get the exact FP instruction that does not allow reordering
(https://reviews.llvm.org/D118073)
D117450 [LoopInterchange] Support loop interchange with floating point reductions
(https://reviews.llvm.org/D117450)

这两个 patch 将 Loop Interchange 的应用场景扩展到支持浮点类型的 reduction 计算的场景：

double matrix[dim][dim];
for (i=0;i< dim; i++)
for (j=0;j <dim;j++)
matrix[i][j] += 1.0;

复制代码

D120386 [LoopInterchange] Try to achieve the most optimal access pattern after interchange

(https://reviews.llvm.org/D120386)

这个 patch 增强了 Interchange 的能力使编译器能够将循环体 permute 成为全局最优的循环顺序：

void f(int e[100][100][100], int f[100][100][100]) {
for (int a = 0; a < 100; a++) {
for (int b = 0; b < 100; b++) {
for (int c = 0; c < 100; c++) {
f[c][b][a] = e[c][b][a];
}
}
}
}

复制代码

void f(int e[100][100][100], int f[100][100][100]) {
for (int c = 0; c < 100; c++) {
for (int b = 0; b < 100; b++) {
for (int a = 0; a < 100; a++) {
f[c][b][a] = e[c][b][a];
}
}
}
}

复制代码

D124926 [LoopInterchange] New cost model for loop interchange

(https://reviews.llvm.org/D124926)

这个 patch 为 loop interchange 提供了一个全新的，功能更强的 cost model，可以更准确地对 loop interchange 的盈利能力做出判断。

此外，我们还为社区提供了大量的 bugfix 的 patch：

D102300 [环路交换] 在多级嵌套环路场景中检查内部闩锁中的 lcssa phis
D101305 [环路交换] 修复三角环路的合法性
D100792 [环路交换] 处理具有多个前身的 lcssa PHI
D98263 [LoopInterchange] 紧固 LoopInterchange 合法性中的 Nested（）
D98475 [环路交换] 修复环路交换中的转换错误
D102743 [LoopInterchange] 在变换过程中适当地处理还原 phis 的移动（pr43326 && pr48212）
D128877 [循环缓存分析] 修复成本计算中的类型不匹配错误

以及其他功能的增强：

D115238 [环路交换] 取消合法性限制
D118102 [环路交换] 检测存储指令的输出依赖关系
D123559 [DA] 使用更好的 API 进行重构
D122776 [NFC][LoopCacheAnalysis] 添加激励测试用例以改进环路缓存分析成本计算
D124984 [NFC][LoopCacheAnalysis] 更新测试用例以确保输出遵循正确的顺序
D124725 [NFC][LoopCacheAnalysis] 使用 stable_sort（）以避免非确定性的打印输出
D127342 [目标转换信息] 添加了高速缓存行大小的选项
D124745 [去线性] 固定尺寸阵列去线性化的重构
D122857 [LoopCacheAnalysis] 实现固定大小阵列的去线性化

结语

如果想要尽可能的利用 Loop Interchange 优化，那在书写 C/C++代码时，请尽可能保证每个迭代之间对数组或数列的访问 stride 越小越好;stride 越接近 1，空间局部性就越高，自然 cache 命中率也会更高，在性能数据上也可以拿到更理想的收益。另外，由于 C/C++的存储方式为 Row-major ordering，所以在访问多维数组时，请注意内层循环要为 Column 才能拿到更小的 stride。