编译点滴

自动向量化能最大程度的解放程序员， 为程序员屏蔽底层CPU的细节，又能通过底层CPU SIMD并行获得有效的性能提升，所以自动向量化一直是研究热点。

目前实现自动向量化的方式有主要有两种：

• 基于循环的自动向量化： 通过分析循环，对于无数据依赖的并行迭代，直接生成对应的向量指令的方式实现向量化。
• 基于基本块的自动向量化： 通过循环展开，得到较大的基本块，然后收集循环中的相同操作，合成后端CPU支持的SIMD操作，实现向量化。

基于循环的自动向量化

基于循环的自动向量化早在上世纪80年代就在向量机系统上得到了广泛应用，其中又以Randy Allen的工作最为著名。 Randy Allen为了在向量机上让历史遗留代码充分利用处理器，开发了一个Fortran到Fortran 8x的代码编译器，其中Fortran 8x中支持向量操作。 该过程就是一个基于循环的自动向量化过程。 为了将循环向量化，作者首先对循环体进行依赖分析，找出无数据依赖的循环迭代， 通过设定循环控制变量每次迭代的跨度，决定有多少个循环迭代被转换成相应的向量指令。 这一机制，使得Fortran能更好的利用向量运算。从Benchmark来看，向量化的加速度大约10倍。

Konrad T. 等人研究了如何把循环自动向量化和其他循环优化映射到多面体模型中。 并在这一模型中，针对这些循环优化，构建统一的代价模型，通过衡量代价模型找出最佳的优化方式。 一般的自动向量化需要事先设定针对最内层循环还是最外层循环作自动向量化。 而本文则可以通过多面体模型自动判断对哪一层循环做向量化。 在作者使用的Benchmark上，基于CELL处理器的测试显示，相比于普通标量有3.5倍的加速比， 相比基于GCC的直接最内层循环向量化有2.3倍的加速；相比直接外层循环向量化，有36%的加速。 在IBM PPC970处理器上，相比串行程序有2.9倍的加速，相比内层循环向量化有2.3倍的加速， 相比外层循环向量化有50%的加速。

Alexandre E. E等人在循环中，考虑有非对齐访存情况下的自动向量化， 提出了一种系统的解决该问题的编译架构。 作者的机制通过在SIMD寄存器中自动拼接数据来满足硬件的对齐需求， 这种拼接多数基于位移的操作，即整个寄存器位移元素长度的整数倍的方式， 位移的操作最终会转换成目标机中的vperm置换指令。 通过vperm置换操作，数据就被有序的组织在向量寄存器中， 接着作者通过向量化数据操作语句的方式，生成向量指令。 作者选定了一些75%以上的数据访存是非对齐的例子，在支持128位向量数据的IBM Altiec上，对于单精度浮点例子，加速比3.71; 对于半字整点例子，加速比6.06。

Doriy Nuzman等人针对通用CPU中的短SIMD结构，研究如何对外层循环做自动向量化， 并在GCC中实现之，相比最内层循环向量化，有一倍以上的加速。 作者注意到，一般的最内层循环向量化很难应对交叉循环迭代依赖，而且迭代次数较少时，也很难有性能提升。 相比于在最内层循环做自动向量化，外层循环能够发现更多的数据并行和局部性，出现非连续访存的可能性更小。 作者首先分析循环，包括对循环内控制流的分析和循环迭代控制的分析，找出循环中会被一直执行的语句和循环的迭代次数。 之后，先通过循环体变换，得到内层循环中的一段线性语句，再递归的对内层循环作处理，将内层循环直线代码分配到基本块。 作者在GCC 4.3中实现了这套机制，对于选定的benchmark，在Cell BE SPU和PowerPC 970上分别获得3.13和2.77的加速比。 相比之下，最内层循环向量化的加速比只有1.53和1.39。

Aart J. C. Bik等人实现了Intel编译器中自动向量化。 ICC通过对最内层循环展开，构建数据依赖图的方式，寻找可以向量化的操作。 为了降低非对齐访存带来的开销，ICC生成了多种版本的循环主体代码，通过运行时检测的方式，寻找最适合执行的代码，并执行之。 对于Linpack，ICC的自动向量化在有MMX和SSE2扩展的2GHz的Pentium 4芯片上，双精度例子加速比平均为2。 对于SPEC2000例子，galgel性能提升20%， swim 6%， gzpi 6%。

基于基本块的自动向量化

Samuel L.首先提出了从单个基本块中综合生成SIMD指令操作的SLP(Superword Level Parallelism)向量化机制。 该架构先在基本块中寻找无依赖的同构操作，将这些同构操作合并，并转换为相应的SIMD操作来实现向量化。 首先使用循环展开，将循环迭代间的并行语句集中到一个基本块中，再在该基本块中利用启发式算法，作对齐分析和数据流优化，减少数据依赖。 之后确定合并成SIMD指令的语句组，并最终生成SIMD操作。 作者将以上机制应用在SPEC95浮点测试集中的科学计算程序和几个多媒体计算程序的kernel中。 因为有了SIMD并行，最终执行的指令数下降了46%。这些benchmark的加速比从1.24到6.70不等。

接着，Samuel L.等人又将软流水和向量化结合，在软流水中寻找向量并行机会，同时进行ILP(Instruction Level Parallelism)和DLP(Data Level Parallelism)。 作者注意到虽然SLP能够发掘并行性，让向量部件更有效的运转，但同时标量运算部件和向量运算部件之间也可以并行。 为了更好的利用这种并行，作者尝试在软流水中寻找向量化机会。 在DSP和SPEC FP benchmark上，分别拿到了1.30和1.18的加速比。

Jaewook Shin等人将SLP扩充到有控制流存在的情况下。 作者注意到控制流因为有分支，使得有些SLP向量化无法进行。 通过将控制流依赖转换为数据流依赖，之后在控制流依赖涉及到的指令中，添加一个谓词属性的转换方式，消除分支，使循环体都在一个基本块中。 之后，重新将SLP算法作用到这个基本块中。 在合并SIMD指令语句组时，相对Samuel L.的SLP，唯一的不同是只有具有相同谓词属性的指令才能合并成带有向量谓词属性的SIMD指令。 然后，对于可以向量化的语句，将其合并。否则通过将向量谓词转换为SELECT动作，保持原程序中分支的语义。 最后将这些向量化的语句生成对应的SIMD代码，而SELECT动作的语句，则重新转换为if-then分支。 作者选取了8个多媒体程序的Kernel来评估自己的工作，获得了1.97到15.07的加速比。

关注可移植性的编译器向量支持

因为各个处理器厂商支持的SIMD扩展支持的数据元素类型、向量数据总长度都有很大的不同。 SIMD指令的数量和功能也有很大的差别，而且处理器厂商也会持续改进自己的SIMD扩展。 在没有好的通用自动向量化算法的前提下，只能由编译器开发者针对每个SIMD扩展，作精确的调优。 如果支持多个处理器，就需要很多繁琐的调优工作。 所以，提升编译器的自动向量化算法的可移植性，也是研究的热点问题。

Dorit N一直为实现一个高性能高可移植的GCC自动向量化而努力。 她在04年的文章中介绍了在 GCC 上实现的基于循环的自动向量化，该机制可以用在向量长度不同的一些后端上。 作者首先介绍了在GCC的嵌套循环优化阶段如何在GCC的SSA表示上使用数据依赖图中的强联通分量作数据依赖分析。 它利用GCC基于SSA的GIMPLE中间表示，首先分析循环格式，接着做数据依赖分析和操作分析。 通过这一系列分析，进行向量化。通过向量化因子VF，控制循环展开的次数，从而实现对不同SIMD数据长度后端的支持。 作者通过循环标记和循环peeling来作对齐分析，寻找最大限度的访存对齐。 两年以后，Dorit N.介绍了他们在GCC中实现自动向量化支持的工作的进展。 作者在GCC 4中实现了新的自动向量化机制，在这套机制中充分考虑了向量化的可移植性问题。 作者的工作基于GCC的GIMPLE中间表示，因为SIMD扩展比较底层，所以作者着重介绍了如何在可移植和暴露底层细节之间的权衡。 在访存对齐方面，作者首先采用静态对齐分析找出对齐访存；再将这些非对齐访存尽可能转换为对齐访存， 可以同时包含多个循环变换版本，并在动态对齐检测的方式确定执行哪个版本； 若经过这一变换，还有些不能确定是否对齐的，若目标平台提供了非对齐访存指令，则向量化之，否则放弃向量化。 作者选了一些浮点、short和char型整点的例子，并在四个平台：IBM PPC97、Pentium4 、Itanium2、Alpha。 结果显示，在四个平台上都有不少加速，尤其在IBM PPC97和Intel Pentium4上有不错的加速比。

CGO 2011中，Dorit Nuzman等人介绍了通过引入运行时支持， 使得静态编译得到的向量化中间表示能在多个不同的SIMD平台上运行，实现了一次编译，跨平台运行。 Dorit Nuzman针对不同处理器的SIMD扩展对向量长度、内存对齐和访问方式三方面的差异展开可移植研究。 作者首先扩充CIL中间表示，针对如上三个差异设计相应的中间表示， 然后利用GCC已有的自动向量化机制，修改GCC使之能生成包含向量扩展的CIL中间表示， 并分别在Intel的SSE、AVX，IBM的AltiVec和ARM的NEON四种SIMD扩展上，通过扩充CIL的运行时环境MONO分别验证了其解决上面三个差异的方法。 作者通过引入向量长度因子和向量化因子来动态表示向量长度，以及由向量长度不同引起的循环展开次数的不同； 通过同时生成对齐和非对齐访存语句，并引入一个判断语句在运行时确定采取哪种方式访存，解决访存对齐问题。 实验结果显示，虽然该策略平均比GCC静态向量化结果略差，但能同时针对多种SIMD扩展， 可以应对不同扩展间对齐访存不同、向量宽度不同、向量指令集不同的问题。

Manuel H.等人针对嵌入式平台，研究编译器 SIMD 支持的可移植性，给出了一个能快速高效移植的编译器向量化架构。 这种嵌入式平台多为面向特定应用的指令集(ASIP)，这类平台一般指令集差别很大，因此对编译器的可移植性要求高。 作者提出了一种能充分利用SIMD指令和编译器可移植性的机制。 该机制由一个循环向量化器和一个展开——打包工具组成，这两者都使用相同的SIMD指令集描述。 因此，移植编译器时只需要修改这些指令集表示即可。 向量相关的优化都采用机器无关的形式描述。 作者在ACE公司的编译器生成工具中实现了这一机制，并在ARM11和NXP TriMedia两款嵌入式处理器上做了验证。 结果显示，这种机制对于DSP类的Benchmark，有7%-66%的加速比。 即使做了4次循环展开， 代码大小与串行代码相比，ARM为原来的0.9，TriMedia为原来的1.1。

Randall J. Fisher等人研究了98年以前SIMD扩展的情况，总结概括了这些SIMD扩展中指令动作的特点， 并据此开发了一种类C语言SWARC，以方便编译器同时支持多个SIMD扩展。 并为该语言开发了一个实验性的编译器Scc，该编译器支持X86平台的MMX和3DNow！ SIMD扩展。 之后，他们又针对SCC编译器做了向量处理优化，但并未给出具体的数据。 该编译器针通过扩展数据类型，使之具有溢出和向量的属性。 针对SIMD指令的新功能，增加新的操作符，如增加最大操作符：?<、最小值操作符：?>。

自动向量化面临的问题

时至今日，虽然学术界针对自动向量化展开了很多研究，但仍存在很多的问题：

• 发现可向量化操作难： 因为指针引起的别名，使得编译器很难对有指针存在的程序做精确的数据依赖关系分析，因而很难并行化。 且SIMD指令无法描述有分支的串行程序的语义，因此编译器无法对循环体中有分支结构的程序向量化。
• 确定向量化方案难： 对于越来越强大的SIMD支持，编译器有很多种向量化方式，由于代价模型不成熟，编译器有时不能正确找到有性能提升的自动向量化方式。 数据置换指令执行时间长，非对齐访存延迟大，自动向量化对循环结构的改变影响其他编译优化的正常进行， 这些都可能影响自动向量化的最终效果。 目前尚无理想的代价模型，可以让编译器从众多向量化方式中，找到代价最小，性能最优的一个。
• 对齐访存要求严格： 非对齐的访存，要么出错，要么效率很低。 在编译时并不能得到所有对齐信息。 为了保证正确性，编译器就需要放弃许多潜在优化机会。
• 可移植性差： 由于知识产权保护和技术演进，各个 CPU SIMD 扩展指令支持的操作、SIMD数据长度和类型都不尽相同。 自动向量化算法要么针对各个不同的指令集做针对性配置和调试，但这样可移植性差； 要么努力提高可移植性，兼容尽可能多的后端CPU扩展，但这样某些后端特有的指令就很难有效利用。

参考

Eichenberger et al.(2004)aEICHENBERGER A E, WU P, O’BRIEN K. Vectorization for SIMD architectures with alignment constraints. Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, 2004:82-93
Naishlos(2004)NAISHLOS D. Autovectorization in GCC. GCC Developers’ Summit, 2004:105-118Allen and Johnson(1988)ALLEN R, JOHNSON S. Compiling C for vectorization, parallelization, and inline expansion. Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, 1988:241-24942VOJIN Z. Compilers for digital signal processors: The hard way from marketing to production tool. DSP and Multimedia Technology, 1995(4):27-45
Cooperation()Intel COOPERATION . Intel C/C++ Compiler User and Reference Guides. http://www.intel.com/software/products/compilers.III(1999)III J H W. Programming Methods for the Pentium  III Processor’s Streaming SIMD Extensions Using the VTune^TMPerformance Enhancement Environment. Intel Technol. J., 1999Shahbahrami et al.(2006)SHAHBAHRAMI A, JUURLINK B, VASSILIADIS S. Performance Impact of Misaligned Accesses in SIMD Extension.Proceedings of the 17th Annual Workshop on Circuits, Systems and Signal Processing (ProRISC 2006), 2006:334-342Slingerland and Smith(2001)SLINGERLAND N, SMITH A J. Performance Analysis of Instruction Set Architecture Extensions for Multimedia.In the 3rd Workshop on Media and Stream Processors, 2001:204 – 217.Ren et al.(2006)REN G, WU P, PADUA D. Optimizing data permutations for SIMD devices. Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, 2006, 41:118-131.Allen and Kennedy(1987)ALLEN R, KENNEDY K. Automatic translation of FORTRAN programs to vector form. ACM Trans. Program. Lang. Syst., 1987, 9:491-542.Trifunovic et al.(2009)TRIFUNOVIC K, NUZMAN D, COHEN A, et al. Polyhedral-Model Guided Loop-Nest Auto-Vectorization. Proceedings of the 2009 18th International Conference on Parallel Architectures and Compilation Techniques, 2009:327-337.Eichenberger et al.(2004)bEICHENBERGER A E, WU P, O’BRIEN K. Vectorization for SIMD architectures with alignment constraints.Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, 2004:82-93.Nuzman and Zaks(2008)NUZMAN D, ZAKS A. Outer-loop vectorization: revisited for short SIMD architectures. Proceedings of the 17th international conference on Parallel architectures and compilation techniques, 2008:2-11Bik et al.(2002)BIK A J C, GIRKAR M, GREY P M, et al. Automatic intra-register vectorization for the Intel architecture. Int. J. Parallel Program., 2002, 30:65-98.Larsen and Amarasinghe(2000)LARSEN S, AMARASINGHE S. Exploiting superword level parallelism with multimedia instruction sets. Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, 2000:145-156.Larsen et al.(2005)LARSEN S, RABBAH R, AMARASINGHE S. Exploiting Vector Parallelism in Software Pipelined Loops. Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, 2005:119-129Shin et al.(2005)SHIN J, HALL M, JACQUELINE C. Superword-Level Parallelism in the Presence of Control Flow. Proceedings of the international symposium on Code generation and optimization, 2005:165-175Nuzman and Henderson(2006)NUZMAN D, HENDERSON R. Multi-platform Auto-vectorization. Proceedings of the International Symposium on Code Generation and Optimization, 2006:281-294Dyshel et al.(2011)DYSHEL S, NUZMAN D, ROHOU E, et al. Vapor SIMD – Auto-Vectorize Once, Run Everywhere. International Symposium on Code Generation and Optimization (CGO’11). Chamonix, France, 2011Hohenauer et al.(2009)HOHENAUER M, ENGEL F, LEUPERS R, et al. A SIMD optimization framework for retargetable compilers. ACM Trans. Archit. Code Optim., 2009, 6:2:1-2:27.Fisher and Dietz(1999)FISHER R J, DIETZ H G. Compiling for SIMD Within a Register. Proceedings of the 11th International Workshop on Languages and Compilers for Parallel Computing. 1999:290-304Fisher and Dietz(2000)FISHER R J, DIETZ H G. The Scc Compiler: SWARing at MMX 3DNow!. Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, 2000:399-414