面向国产平台的LLVM 自动向量化移植与优化

李嘉楠，韩 林，柴赟达

（1.郑州大学信息工程学院，郑州 450000；2.国家超级计算郑州中心，郑州 450000）

0 概述

高性能计算可用于开发解决全球性问题的科学应用程序，如疫苗研制、气候建模等。如今，提高处理器的性能变得越来越重要，而电子器件的更新已不能满足日益增长的计算需求，在此情况下，微型的向量并行部件SIMD（Single Instruction Multiple Data）扩展得到迅速发展，并被广泛应用于各种科学计算类程序的加速优化任务。

基于SIMD 扩展部件的向量化已成为程序并行的重要手段，其向量寄存器和SIMD 指令是程序员以及处理器厂商的研究重点［1］。目前，ICC、GCC、LLVM（Low Level Virtual Machine）等编译器已相继支持了SIMD 的自动向量化编译，面向SIMD 扩展部件的自动向量化编译已逐渐成为程序向量化变换的主要方式。

LLVM 是对任意编程语言提供一种基于SSA（Static Single Assignment）［2］的静态与动态编译的现代编译技术，与其他主流编译器相比，LLVM 具有如下优势：统一的IR（Intermediate Representation）与模块化［3］，能够以库的形式抽取其组件并用于其他领域；编译器中的优化和分析被组织成遍（Pass）结构，通过不同遍完成不同的优化算法［4］；开源License 的优势使其被各大公司广泛采用。在LLVM 编译器中，已实现了循环级与基本块级的自动向量化方法［5］。

申威系列处理器是我国自主研发、面向高性能计算的通用微处理器，该处理器主要针对计算密集型程序，如科学计算、数字信号分析、多媒体处理等。申威系列处理器包含丰富的向量运算指令和完善的向量重组指令，为程序的向量化提供了良好的硬件基础。

LLVM 编译器中自动向量化部分主要由Intel 团队开发推进，算法以及向量指令的应用更适用于X86 平台［6］。目前，LLVM 编译器还未支持面向国产平台的自动向量化。由于指令集的差别，申威处理器与X86 处理器的自动向量化实现方法有所不同，如AVX 指令集兼容256 位与128 位的向量长度，而国产处理器一般只支持单一的向量长度，导致向量化后生成不支持的向量类型，从而产生段错误、结果错误等问题。

本文针对申威1621 处理器平台进行自动向量化移植研究，从循环级与基本块级2 个方面提高自动向量化适配能力，以完善向量化所需的指令代价信息，并在精准代价模型的指导下生成后端支持的向量指令。同时，针对循环级向量化中控制流向量化进行算法改进，以解决后端不支持掩码访存指令的问题。

1 LLVM 自动向量化框架

1.1 循环级向量化

循环级向量化主要是在迭代间寻找并行机会以进行向量化，其主要流程如图1 所示。

图1 循环级向量化流程Fig.1 Procedure of cyclic vectorization

合法性分析步骤为：首先检查是否为嵌套循环，排除不能向量化的循环形式，如多出口多回边结构；然后对包含控制流的循环进行分析，收集分支掩码以用于后续向量代码生成［7］；接着对phi 指令以及调用指令进行分析，判断其是否符合向量化格式要求；最后调用循环访存信息，分析访存指令是否具有阻止向量化的依赖关系。依赖分析就是根据循环内的数据依赖关系构造语句依赖图，在语句依赖图上求解强连通分量，不具有强连通分量的语句就是可以进行向量执行的语句［8-9］。

通过调用代价模型，首先对基本块中访存指令进行分析，连续访存可直接获取指令代价，非连续访存需要对比不同策略下的收益，选出访存指令向量化的最佳执行方案［10-11］；然后将该指令与基本块内其他指令一起，以2 的整数幂在［2，IMaxVF］范围内进行收益比较；最终将其与标量代价进行对比，选出最优的向量化因子。

向量代码生成是在原始标量循环结构之前创建一个新的循环，使其成为向量指令的载体。标量循环中不同类型的指令分别调用不同的转换函数以进行向量指令生成，最后将生成的向量指令逐一添加到新的循环中，更新支配关系，原始的标量循环将作为新向量循环的“标量尾循环”处理［12］。

1.2 基本块级向量化

紧跟在循环级向量化后的是基本块级向量化，其主要在基本块内寻找同构语句以发掘并行机会。基本块级向量化流程如图2 所示。

图2 基本块级向量化流程Fig.2 Procedure of basic-block level vectorization

在基本块级向量化中，首先找到函数中所有的内存引用，收集指令并进行打包［13］，包是一个同构语句的集合，将多个同构语句组成包的过程称作打包，相反则称为拆包［14］；然后SLP 利用相邻地址的存储指令作为种子进行打包，通过“定义-使用链”和“使用-定义链”启发式地扩展包［15］，若循环中的每一个操作都可以被目标平台以向量形式支持，则进行语法树的代价分析，在有收益的情况下构建向量化树，从上到下扫描基本块的所有语句，在需要向量化的标量语句前插入向量语句，以完成向量代码生成［16］；最后移至下一组指令重复以上分析，直至完成基本块内所有指令的向量发掘。

2 自动向量化移植

近年来，作为编译优化领域的研究热点，SIMD扩展部件不断发展。申威系列处理器的SIMD 向量长度在持续增长，指令集功能也越来越丰富，因此，需要针对每一种处理器实现其自动向量化功能移植。移植主要包含自动向量化优化遍、后端相关转换信息2 个方面。自动向量化可分为识别、优化、指令生成3 个部分。识别方法在循环级向量化与基本块级向量化中通用，最重要的是考虑SIMD 部件差异与指令集特征，其中，寄存器信息、跨幅因子、基本指令代价的精确描述是自动向量化的基础条件。另外，本文提出一种掩码指令转换方法，使得申威平台支持包含控制流结构的向量化。

2.1 寄存器信息

完善SIMD 向量化的寄存器基础信息包含RegisterInfo 文件中向量寄存器数量、特征信息以及TargetTransformInfo 文件中寄存器宽度描述，必要时数据类型长度也需要根据指令集信息进行修改［17］，否则会生成后端不支持的向量长度或向量类型，增加后端指令降级工作从而导致向量代码生成效率降低。

2.2 跨幅因子

跨幅因子即循环级向量化中的“Interleave Count”，为基本块中单条语句的展开数，默认值为1。结合向量指令特征，将TargetTransformInfo 中最大跨幅因子设置为4，向量化阶段调用代价模型从［1，4］范围内分析出最佳跨幅因子，与原始默认值1 相比，提升了向量化性能。以TSVC（Test Suit for Vectorizing Compilers）测试集中的vpvts 函数为例，移植后进行收益分析，选择出最佳跨幅因子为4，以此进行向量代码的局部展开，相比原始向量化其性能提升了70%。

2.3 基本指令延迟信息

基本指令包含逻辑运算指令、类型转换指令、比较指令、内建函数指令、访存指令等。根据硬件提供的指令延迟表，在后端TargetTransformInfo 文件中对指令代价进行精确描述，包含数据类型、操作码识别、指令延迟数补充。将后端不支持的向量指令代价调高，防止向量化后产生倒加速问题。对于复杂指令如混洗指令，结合后端指令降级中自定义的指令拆分组合情况进行精确描述。

X86 平台支持128 位的向量寄存器［18］，在自动向量化中最小向量化因子限制为2，但这在申威平台不适用，原因是会造成数据处理过程中读取错误信息，在程序运行时引发段错误。基于上述原因，本文分别在循环级向量化与基本块级向量化中修改最小向量化因子。

2.4 掩码内建指令

掩码内建函数是对LLVM 基本指令集的补充，由特定目标平台的特殊指令组合而成，但并不是所有目标架构指令集都具备全面的掩码指令［18-19］。在申威平台下进行SIMD 编译时，自动向量化并不支持掩码访存指令，导致大量包含控制流的循环错失向量化机会。在循环级向量化时将掩码访存指令替换为select 向量指令，可解决目标平台不支持掩码访存指令的问题，核心转换算法描述如算法1 所示。

算法1掩码指令转换算法

3 收益评估模型

循环或函数被向量化后的基本收益就是基本块中减少的指令周期数，收益评估用于衡量向量化是否有利于提高程序效率［7］。自动向量化移植使得收益评估更加精准与完善，可以在收益评估的指导下判断是否需要进行向量化以及如何进行向量化，从而生成最符合申威后端需求的向量或标量代码。

3.1 面向循环级向量化的收益评估

循环级向量化收益分析流程如图3 所示。

图3 循环级向量化收益分析流程Fig.3 Procedure of cost analysis in cyclic vectorization

收益分析主要集中在2 个部分：针对访存指令的最佳加宽决策；针对循环基本块的最佳向量化因子选择。具体步骤如下：

1）计算可行的最大向量化因子IMaxVF，获取后端向量寄存器长度DWidthRegister以及数据宽度DWidthType信息，对于只支持单一向量长度的后端：

2）访存指令对程序的向量化或性能提升起决定性作用，对于访存指令，循环级向量化具有专属的决策分析以求得最大收益。对于连续访存代价，直接从后端指令延迟表获取；对于不连续访存，比较跨幅访存、聚合访存、标量化访存3 种方案下的收益以选取最佳方案进行执行。

额外代价来源于从<8 x i32>向量中的0、2、4、6 位抽取数据并插入到<4 x i32>向量过程中的插入抽取指令，设GGroupNums为跨幅访存组指令数量，其额外代价为：

跨幅store 指令是从子向量中提取所有元素，并将它们插入到目的向量中，例如：

额外代价来源于从2 个<4 x i32>向量中抽取8 个元素插入到<8 x i32>向量过程中的插入抽取指令代价，设跨步为SSteps，其额外代价为：

（3）标量化访存代价首先获取标量存储指令和地址计算：

包含控制流的循环属于不连续访存，掩码指令转换算法将包含控制流的循环进行select 指令转换，改变包含控制流访存收益分析的计算方式，如下：

在更新包含控制流的代价计算后，根据基本块执行的概率来扩展代价［20］，循环级向量化认为每个基本块执行的概率均为50%，因此，分支基本块的代价为CCost=CCost/2。

3）将循环中所有指令进行累加，对比以上3 种不连续访存的收益，选择最优收益方案进行下一步向量因子的收益分析。

最后对比标量与向量形式下的收益，选择进行向量代码生成或保持原有的标量执行。

3.2 面向基本块级向量化的收益评估

SLP 向量化收益开销计算算法以抽象语法树为基础，满足E≥VVF条件后以存储指令为根节点遍历树形结构，通过“使用-定义链”自下而上进行打包，其中，每个节点都包含可并行处理且数目相同的同构语句［21-22］。

代价模型获取寄存器信息计算向量化所需的同构语句数，根据指令代价选择收益最大的进行向量化。首先确定同构语句长度（即同构语句数量）与向量化因子：设同构语句长度为E，向量化因子为VVF（设向量寄存器长度为256 位，标量元素double 为64 bit，则向量化因子VVF等于4）。假设标量指令代价为Si，向量指令代价为VCost，则每条向量指令的收益为：

该基本块向量的收益总和为：

考虑寄存器溢出与指令重组对向量化性能存在影响，因此，自底向上遍历语法树以计算额外开销，其值在理想状态下为0，则总体收益为：

另外一些计算如标量的规约计算、向量化指针指令的索引计算，没有被基于同构store 组的自底向上的遍历过程所捕获，因为它们不包含这样的存储指令，此类收益分析需考虑插入/抽取指令以及索引信息的代价（从后端相关指令延迟表中获取，默认值为0），则总体收益为：

4 测试分析

本文采用申威1621 处理器为测试平台，进行LLVM 编译器自动向量化移植功能测试，编译器版本为7.0。分别采用SPEC2006 与TSVC 测试集以及向量化应用测试，从正确性与向量化性能2 个方面进行对比分析。

4.1 功能测试与分析

SPEC2006 标准测试集是SPEC 组织推出的CPU 子系统评估软件。为验证本文方法改进下编译器的健壮性，对SPEC2006 标准测试集中的29 道题进行测试，结果如表1 所示。

表1 SPEC 测试结果Table 1 SPEC test results

移植前中间表示代码在自动向量化阶段生成了后端不支持的向量类型，在后端指令降级过程中找不到匹配的降级方法与指令模板，导致测试题出现段错误以及结果错误的问题。从表1 可以看出，移植优化后410、416、454 等测试题依靠后端信息的精准描述以及收益分析的正确引导，向量化程序在test、train、ref 规模下正确运行。

4.2 精准代价指导下的测试分析

基本运算指令代价的精准描述，可以使得自动向量化做出符合后端要求的向量化决策，生成简洁高效的向量汇编指令。本文采用TSVC 测试集中的典型例题，对比移植优化前后的加速性能，结果如图4 所示，从图4 可以看出，相对移植前，移植优化后平均加速比提升42%。

图4 精准代价指导下的加速性能Fig.4 Accelerated performance under precise cost guidance

当后端对不支持的向量指令进行降级处理时，会生成冗余标量指令导致倒加速。精准代价模型指导下的自动向量化可排除后端不支持的向量类型，防止向量化倒加速产生。从图5 可以看出，使用精准代价指导后，选择与后端匹配的向量化因子以及向量化方法，可以使倒加速情况得到明显改善，在原有移植的基础上平均加速比提升28%。

图5 精准代价指导下的倒加速改善结果Fig.5 Reverse acceleration improvement results under precise cost guidance

4.3 性能测试与分析

本文分别采用SPEC CPU2006 测试题、TSVC 测试集以及被广泛应用的矩阵运算测试题进行性能测试。

4.3.1 SPEC 测试分析

本次实验对SPEC 测试集的29 道题进行性能测试分析，编译优化选择-O3-static，ref 规模，单进程运行。选取代表性测试题进行分析，对比X86 平台与国产平台的向量化能力，从而验证移植的有效性。测试结果如图6 所示，其中，X86 选用与申威SIMD长度相同的AVX 指令集。

图6 SPEC 测试分析结果Fig.6 SPEC test analysis results

前端将测试题解析为中间表示代码，自动向量化在此基础上进行向量代码优化生成，然后由后端进行降级处理，生成特定指令集的汇编码。从图6 可以看出，移植优化后的向量代码简洁高效且符合后端指令集特征需求，移植后SPEC 整体性能提升10.8%，国产平台的向量化能力优于X86，其中，436 加速效果最为明显，提升了97%，437 加速比提升52%，434、470、482 加速比平均提升21%。由于指令集存在差异，国产处理器不支持一些特殊的向量指令，导致其对456 与482 的加速性能低于X86。

4.3.2 TSVC 测试分析

TSVC 测试集主要用来对编译器的自动向量化能力进行性能测试，本文采用TSVC 测试集对比移植优化前后的加速性能，测试结果表明，移植优化后整体加速比提升16%。对掩码内建指令进行相关修改，可以使得后端兼容原本不支持的向量化实现方法，从而充分利用申威后端的向量指令。从图7 可以看出，在控制流优化下，循环识别率提升48%，平均加速比提升51%。

图7 控制流优化下的加速比结果Fig.7 Acceleration ratio results under control flow optimization

4.3.3 应用测试分析

快速傅立叶变换被广泛应用于信号分析任务，其性能提升离不开矩阵运算优化，另外，图形处理、游戏开发、科学计算中包含了大量的矩阵运算，因此，本次实验以矩阵乘为代表，进行应用程序测试分析。实验采用3 层循环，以3 种N×N规模的矩阵进行测试，每个规模运行3 次并取平均值，以对比移植优化前后的运算性能，结果如图8 所示。从图8 可以看出，矩阵乘运算总体性能提升了72%，矩阵规模为1 024×1 024、2 048×2 048、4 096×4 096 时，加速比分别提升了77%、79%、59%。矩阵乘性能收益主要来源于合适的跨幅因子与向量化因子，其能够最大程度地发挥SIMD 向量指令的优势。

图8 矩阵乘运算性能分析Fig.8 Performance analysis of matrix multiplication operation

5 结束语

本文针对申威1621 处理器进行LLVM 自动向量化功能移植，以解决自动向量化过程中后端信息不匹配和向量化实现方法不兼容的问题。实验结果表明，移植优化后不再生成后端不支持的向量类型以及不合法的向量指令，控制流向量化程度显著提升，在TSVC 测试集中，相对自动向量化移植前，移植优化后平均加速比提升16%。通过对自动向量化移植进行研究可以看出，在申威后端存在不支持某些相对重要的向量指令的情况，这将严重影响向量化的效果。因此，下一步将综合考虑申威指令集与自动向量化后代码生成的关系，将申威指令集中的基本向量指令进行拼接与重组，从而提高向量指令的适用性。