编译器优化：何为SLP矢量化 _SLP

引言Superword Level Parallelism （SLP）矢量化是llvm auto-vectorization中的一种，另一种是loop vectorizer，详见于Auto-Vectorization in LLVM[1] 。它在2000年由Larsen 和 Amarasinghe 首次作为basic block矢量化提出。SLP矢量化的目标是将相似的独立指令组合成向量指令，内存访问、算术运算、比较运算、PHI节点都可以使用这种技术进行矢量化。它和循环矢量化最大的差异在于，循环矢量化关注迭代间的矢量化机会，而SLP更关注于迭代内basic block中的矢量化的机会。
一个简单的小例子案例.cpp[1]：
void foo(float a1, float a2, float b1, float b2, float *A) { A[0] = a1*(a1 + b1); A[1] = a2*(a2 + b2); A[2] = a1*(a1 + b1); A[3] = a2*(a2 + b2);}命令：clang++ case.cpp -O3 -S ;SLP在clang中是默认使能的，可以看到汇编中已出现使用矢量寄存器的fadd和fmul 。

文章插图

如果编译命令中加上选项-fno-slp-vectorize 或者 -mllvm -vectorize-slp=false 关闭该优化，则只能得到标量的版本。

文章插图

让我们来跟随《利用多媒体指令集利用超字级 Parallelism》[2]这篇经典论文来探究一下SLP矢量化的奥秘。
1.原始SLP算法介绍1.1概述论文中用一张图来解释了SLP要做的事情：

文章插图

原始SLP例子[2]
这四条语句中的位置相对应的操作数，比如（b，e，s，x）可以pack到一个向量寄存器Vb中，同样的，（c，f，t，y）可以pack到Vc，（z[i+0]~z[i+3]）可以到Vd 。然后可以利用simd指令进行相应的矢量化计算。最后根据Va中（a，d，r，w）的被使用方式，可能还需要将他们从向量寄存器中load出来，称为unpack 。
所以，如果pack操作数的开销 + 矢量化执行的开销 + unpack操作数的开销小于原本执行的开销，那就证明SLP矢量化具有性能收益[3] 。
1.2 优化场景为了进一步说明SLP和循环矢量化在优化场景上的差异，论文[2]中给了两个例子（可以通过
https://godbolt.org/z/EWr4zTc3P 直接查看汇编情况）。
1）对于原始循环 a，既可以通过标量扩展（一种转换标量数据以匹配矢量或矩阵数据的维度的方法）和循环裂变（与循环融合相反：但其实由于论文比较老了，目前llvm编译器对于a这样形式的循环可以直接做矢量化。

for (i=0; i<16; i++) { localdiff = ref - curr;diff += abs(localdiff);}（a）原始循环。
for (i=0; i<16; i++) { T = ref - curr;}for (i=0; i<16; i++) {diff += abs(T);}（b）标量膨胀和环裂变后。

for (i=0; i<16; i+=4) { localdiff = ref[i+0] - curr[i+0];diff += abs(localdiff); localdiff = ref[i+1] - curr[i+1];diff += abs(localdiff);localdiff = ref[i+2] - curr[i+2];diff += abs(localdiff);localdiff = ref[i+3] - curr[i+3];diff += abs(localdiff);}

（c）展开后暴露的超字级并行性。

for (i=0; i<16; i+=4) {localdiff0 = ref[i+0] - curr[i+0];localdiff1 = ref[i+1] - curr[i+1];localdiff2 = ref[i+2] - curr[i+2];localdiff3 = ref[i+3] - curr[i+3];diff += abs(localdiff0);diff += abs(localdiff1);diff += abs(localdiff2);diff += abs(localdiff3); }

（d）重新命名后分组在一起的可压缩报表。
2）但是对于如下例子，循环向量化需要将do while循环转换为for循环，恢复归纳变量，将展开后的循环恢复为未展开的形式（loop rerolling）。而SLP只需要将计算 dst[{0， 1， 2， 3}] 的这四条语句组合成一条使用向量化指令的语句即可。

do { dst[0] = (src1[0] + src2[0]) >> 1; dst[1] = (src1[1] + src2[1]) >> 1; dst[2] = (src1[2] + src2[2]) >> 1;dst[3] = (src1[3] + src2[3]) >> 1; dst += 4;src1 += 4;src2 += 4;}while (dst != end);

看到这里，可以了解到哪些是SLP的优化机会。论文中提出了一种简单的算法来实现，简而言之是通过寻找independent（无数据依赖）、isomorphic（相同操作）的指令组合成一条向量化指令。
那么如何找呢？