分支的向量化

If转换是向量化控制依赖最常用的方法，可以将控制依赖转换为数据依赖，其需要借助于向量条件选择指令完成向量指令生成。向量选择指令select的格式如图所示：

dst = select (src1，src2， mask)，指令有三个参数，其中mask为掩码，src1和src2是两个源操作数。当掩码位置的值为1时，取src2的值赋给dst，否则将src1的值赋给dst。

当程序的指令执行顺序和分支结果相关时会形成控制依赖，其存在会影响向量化的开展，是向量化时需要重点考虑的依赖形式之一，本节将介绍向量化时存在分支所导致的控制依赖的处理方法。

原始代码：

经过if转换后的代码：

向量化是根据条件表达式进行改写的，对于满足条件的进行与操作，对于不满足条件的取反。如果程序中有多层条件嵌套，则按此规则逐级向外层递推。

原始代码：

向量化后代码：

当基本块内同构语句条数足够多时，基于if转换的控制流向量化生成的代码并不高效，因为这些语句对应的控制条件相同，不需要再生成条件语句指令，可以直接进行向量化，此种向量化方法称为直接SIMD向量化控制流方法。

原始代码：

向量化后代码：

进一步精简：

归约的向量化

归约操作是指将多个元素归并为单个元素的过程，该操作把向量中的多个元素归约为一个元素，常见的归约操作包括归约加、归约乘等。

原始代码：

向量化后：

以上面的代码段为例，将向量寄存器槽位中的4个数据相加，利用提取指令实现的上述归约需要进行三次提取，然后进行三次加法。

此外还可以利用向量移位指令实现归约加法，实现原理如图所示。此种方法通过两次移位、两次相加获得最终结果。由于几乎所有平台的移位指令节拍数和提取指令节拍数相同，而向量加和标量加的节拍数也相同，因此利用向量寄存器移位指令实现的归约加减少了一次加法和提取操作，代价小于利用提取指令实现的归约加。

当前大多数向量寄存器在使用时为一个不可拆分的整体，即向量寄存器中的每个数据都是有效的。但语句中的数据并行性不足时，需要向量寄存器的部分使用，即向量寄存器中的某些槽位为有效数据，其它槽位为无效数据。向量寄存器有四种使用方式，分别为满载使用、一端无效的部分使用、两端无效的部分使用、不连续的部分使用。其中寄存器满载使用的情况也可称为程序充分向量化，而部分使用的情况可称为程序不充分向量化。

合适的向量长度

但不是所有程序都适合使用不充分向量化方法改写，适合使用不充分向量化方法程序可以分为两种情况。

（1）一是当平台没有向量重组指令或者向量重组指令的功能较弱时，如果强制将不连续的访存数据组成向量可能导致向量化没有收益，而不充分向量化不需考虑平台是否支持向量重组指令，同样可以生成向量程序。

（2）二是向量重组指令的代价过大而导致向量化没有效果，即使用充分向量化效果不如使用不充分向量化效果。

常用的不充分向量化方法分为三类，分别为掩码内存读写方法、插入/提取方法以及加宽向量访存方法。首先介绍掩码内存读写方法，以下图所示的语句S1:c[2i]=a[2i] + b[2i]为例，load指令从内存中连续地加载数据到向量寄存器Va和Vb中，其中的偶数位是有效槽位，奇数位是无效的槽位 。

不充分向量化方法的代码生成需要从三个方面进行考虑，首先在读内存时需要标记出有效槽位和无效槽位，然后在运算时需要将参与运算的向量寄存器槽位相对应，最后再将结果写入内存时需要避免将无效槽位的值写入内存。在申威平台以下面的基本块代码为例说明如何生成不充分向量化代码。 申威平台支持256位的向量寄存器，其向量寄存器也是标量寄存器，根据操作指令决定寄存器类型。然而这个结果是不正确的。

源代码为：

汇编代码为：

因为读写内存操作会访问到原程序没有涉及到的值w[col+1][0]和A[Anext][1][0]，如下图所示，这可能导致程序结果不正确和内存溢出，并且在对无效槽位进行乘法运算时可能引发异常，此时可以采用插入/提取的方法对程序进行向量化。

利用插入指令实现时首先通过多条标量内存读操作将数据存放到标量寄存器中，然后将数据分别插入到向量寄存器中，如下图所示。一些平台支持向量插入指令，如Intel的SSE指令集可利用一条插入读指令“__mm_set_ps(f[k][0],f[k][1], f[k][2],0)”，就可以将f[k][0]、f[k][1] 和f[k][2]的值加载到向量寄存器中。

同样可以利用加宽向量访存方法实现向量化，如图所示，如果需要的值在内存中是连续的，那么一条加宽的向量读指令就可以将其加载到向量寄存器中实现部分向量读操作。

代码中的向量写操作可以使用提取指令实现，如图所示。利用提取指令将数据从向量寄存器中提取出来，然后利用标量内存写指令实现。AVX2指令集中提供有掩码内存写指令，一条掩码内存写指令“vmaskmovpd ymm3，mask，x[k][0]”就可以将x[k][0]， x[k][1]和x[k][2]的值写入内存。

与加宽向量读指令相似，加宽向量写指令可以用于部分向量写内存操作，然而该操作不仅需要避免访存溢出，同时还要避免对内存造成误写，可以在尾部添加一些内存空间避免内存访问溢出。

示例中需要避免w[col+1][0]的值在部分内存写时被改变，使用备份和恢复机制可以更正被改变的值，首先将w[col+1][0]的值读到标量寄存器$f4中，然后利用一个加宽的向量存操作将结果写入内存，最后再利用一个标量存操作恢复w[col+1][0]的值。

在原程序中，无效槽位的数据不需要任何计算。因此需要将无效槽位填充一些数据以避免无效槽位引入算术异常。利用插入指令或者混洗指令，将任意一个有效槽位中的数据填充到无效槽位，来避免无效槽位引入的算术异常。

利用加宽向量访存生成的不充分向量化汇编代码如下所示：

与前面直接向量化的错误代码相比，添加了一条插入指令以保证部分向量运算时不会引起算术异常，然后添加了一条标量读和标量写指令实现部分向量操作。