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

1.3 算法描述作者注意到如果被 pack 的指令的操作数引用的是相邻的内存，那么特别适合 SLP 执行。所以核心算法就是从识别相邻的记忆引用开始的。
当然寻找这样的相邻内存引用前也需要做一些准备工作，主要是三部分：（1） Loop Unrolling;（2） Alignment analysis;（3） Pre-Optimization（主要是一些死代码和冗余代码消除）。具体不展开讲。
接下来我们来看看核心算法，主要分为以下4步：

标识相邻的内存引用
扩展包集
组合
调度

伪代码[4]是：

文章插图

（1）第一步 find_adj_refs先来看第一步：

文章插图

函数 find_adj_refs 的输入是 BasicBlock，输出为集合 PackSet 。
遍历BasicBlock里面的任意语句对（s， s'），如果他们访问了相邻的内存（比如s访问了arr[1]，s'访问了arr[2]），并且他俩能够pack到一起（即stmts_can_pack（）返回true），那么将语句对（s， s'）加入集合PacketSet 。
这里用到了一个辅助函数stmts_can_pack，伪代码如下：

文章插图

声明了可以pack到一起的条件：

s 和 s'是相同操作（isomorphic）
s 和 s'无数据依赖
s 之前没有作为左操作数出现在 PackSet 中，s'之前没有作为右操作数出现在 PackSet 中
s 和 s'满足对齐要求（consistent），即要求新加入的语句对的数据类型也是可以和已存在的语句对在内存上是对齐的

（2）第二步：扩展包集从第一步我们可以获得PacketSet，第二步沿着其中包含的语句的defs 和 uses 来扩充PacketSet 。所以这一步的输入是PacketSet，输出是扩充后的PacketSet 。
伪代码如下：

文章插图

?对于PacketSet中的每一个元素pack，即语句对（s， s'），不断执行follow_use_defs 和 follow_def_uses函数来分别在同一个BasicBlock中寻找s和s'的源操作数和目标操作数相关的语句，判断两个条件，一个是stmts_can_pack是否可以pack，另一个是根据cost model判断是否有收益，从而扩充PacketSet，直至其不能加入更多的Pack 。
（3）第三步：组合这一步的输入为已经尽可能多的（s，s'）语句对组成的PacketSet，输出则为尽可能可以合并语句对之后的PacketSet 。
那么怎么合并呢？伪代码如下：

文章插图

?对于两个Pack，p = （s1,...,sn）和 p' = （s1',...,sm'），如果sn与s1'相同，那么恭喜，p和 p' 可以合并成新的 p'' = （s1,...,sn，s2',...,sm'）。
（4）最后一步：调度将PackSet中的语句对根据数据依赖关系整理成simd指令，如果是有循环依赖的pack，那么revert掉，不再对这pack里的指令矢量化。
最后输出的是包含SIMD指令的BasicBlock 。
1.4 一个例子为了更好理解，论文中也给出了一个例子，我们简单过一下：

文章插图

（1）初始状态，BasicBlock中指令，如（a）。
（2）执行find_adj_refs，将（1， 4）和（4， 7）加入PackSet，如（b）。
（3）执行extern_packlist：
a. 函数follow_use_defs 去寻找对a[i+0]， a[i+1]， a[i+2]进行def的语句，无语句对加入P