这篇文档属于类型a：单篇原创研究的报告。以下是关于该研究的学术报告。

面向SIMD扩展的非同构语句向量化新方法研究

本研究由中国科学院软件研究所基础软件国家工程研究中心的冯靖格、何晔平、陶秋铭和马恒太共同完成，他们同时隶属于中国科学院大学。这项研究以”An SLP Vectorization Method Based on Equivalent Extended Transformation”为题，于2022年3月9日发表在学术期刊《Wireless Communications and Mobile Computing》上（卷2022，文章ID 1832522）。

一、 研究的学术背景

本研究的核心科学领域是编译器优化，特别是自动向量化（Auto-vectorization）技术。随着移动设备对高性能和低功耗的需求日益增长，单指令多数据流（SIMD）扩展指令集因其能效比优势，成为支撑移动系统的重要平台。如何高效利用SIMD指令提升程序性能是编译技术面临的挑战。超字级并行（Superword Level Parallelism, SLP）是一种面向基本块内语句间并行性发掘的高效向量化方法，已被主流编译器广泛采用。

SLP方法的核心在于寻找同构（Isomorphic）语句（即具有相同数量、类型和顺序操作的语句）并将其打包成向量指令。然而，传统SLP方法对非同构（Non-isomorphic）语句的向量化能力不足，限制了其应用范围。针对此问题，近年来的研究主要从两个方向展开：1）基于硬件特殊指令（如PSLP方法），但受限于特定处理器平台并可能引入额外开销；2）基于表达式等价变换（如LSLP和SN-SLP方法），主要通过交换律或逆运算重组操作顺序，将操作顺序不同的非同构语句转化为同构语句。

本研究团队发现，现有基于表达式变换的方法主要解决了操作顺序不同 的非同构问题，但普遍忽略了另一类常见且重要的情形：操作数量不同 的非同构语句。这类情况在科学计算和多媒体应用中普遍存在。更关键的是，编译器在进行标量优化（如常量折叠、强度削弱）时，经常会将原本操作数相同的同构语句（例如 a[0] = i - 0 被折叠为 a[0] = i）转变为操作数量不同的非同构语句，从而错失SLP向量化的机会。简单地关闭这些标量优化虽能部分解决问题，却会损失优化本身带来的性能收益。

因此，本研究旨在解决操作数量不同的非同构语句的SLP向量化问题。研究目标是提出一种新的自动向量化方法，能够自动识别并将此类非同构语句转化为同构语句，从而扩展SLP的应用范围并提升其收益。为此，研究团队提出了两个核心研究问题：1）如何识别可进行同构变换的对象，即如何在待处理的程序语句集合中，识别出那些能够通过变换成为同构的操作数量不同的非同构语句；2）如何实现同构变换，即如何基于等价变换弥合操作数量的差异，并确保变换后语义不变且程序整体性能得到提升。

二、 研究的详细工作流程

本研究提出了一种名为SLP-E 的新型自动向量化方法，其核心是引入并利用一种新的表达式等价变换——等价扩展变换（Equivalent Extended Transformation）。该方法主要工作流程可分为以下几个核心步骤：

1. 提出并定义等价扩展变换 这是一种全新的变换思路，利用诸如 x = x + 0、x = x * 1、x = x - 0 等恒等扩展关系，在表达式中“无成本”地增加操作节点，从而弥合语句间操作数量的差异。例如，语句 a = b 可通过扩展变换为 a = b * 1 + 0，从而与 c = d * e + f 在操作数量上达成一致，为后续同构化创造条件。大多数二元操作都有其对应的等价扩展表达式。

2. 设计基于最大公共子图的差异分析算法（NM-MCS） 为了解决“识别变换对象”的问题（问题1），SLP-E首先需要精确分析语句间的差异。研究团队将程序语句表示为数据依赖图（Data Dependency Graph）。为了高效地找到两个数据依赖图之间的差异部分，他们提出了一个基于最大公共子图（Maximum Common Subgraph, MCS） 的启发式方法，即NM-MCS算法。 该算法首先在两张图中收集所有可能的匹配节点对（满足类型相同、内存访问连续、相互独立等条件的节点），并计算每对节点的匹配分数（基于以它们为根的子图的节点类型相似度）。然后，算法以匹配分数为指导，迭代地构建相对最优的匹配节点对组。具体步骤包括：1）初始化候选组；2）迭代地向现有组中添加新的匹配节点对，形成新的候选组，并仅保留评分最高的前K个组；3）当无法添加新对时，获得最优匹配节点对组；4）根据匹配的节点和边，推导出最大公共子图。从原始依赖图中减去最大公共子图，即可得到差分图（Differential Graph），该图清晰地揭示了语句间的结构差异。

3. 识别可扩展变换的优化对象 在获得差分图后，SLP-E需要从中定位可进行等价扩展变换的具体位置。为此，研究团队提出了可扩展差分子图对（Extensible Differential Subgraph Pair） 的概念。一个可扩展差分子图对 <A, B> 需要满足三个条件：A图仅有一条边；B图中的操作类型仅限于加、减、乘、除或移位（若是非交换操作，则要求其第一操作数节点没有外连边）；A和B是彼此对应的差分子图。满足这些条件的 <A, B> 意味着可以通过对A进行等价扩展，使其变得与B同构。SLP-E方法在差分图中搜索满足这些约束条件的图对，从而确定进行等价扩展变换的位置。

4. 实现等价扩展变换的算法 为了解决“实现同构变换”的问题（问题2），SLP-E设计了一套具体的变换算法。该算法针对可扩展差分子图对 <A, B>，将仅有一条边的A图扩展为与B图同构的A‘图，同时保持语义等价。算法的关键在于如何为新增的操作节点添加正确的叶节点（常量操作数）。 算法首先确保处理的数据依赖图是树形结构（若非树形则通过复制节点进行转化）。然后，它沿着连接公共子图和差分子图的路径（v_path）进行分析，并根据节点是否在此路径上，将节点分为直接节点（在v_path上） 和间接节点（不在v_path上）。为直接节点添加叶节点时，只需根据其操作类型插入特定常量（如加法节点插入0，乘法节点插入1）。为间接节点添加叶节点时，则需根据其操作类型和其输出值来决定：在第一操作数位置插入与其输出值相同的操作数，在第二操作数位置根据操作类型插入特定常量（0或1）。通过这一系列插入操作，最终完成从图A到图A‘的扩展变换，使其与图B同构。

5. 集成、评估与实现 SLP-E方法的完整编译流程包括预处理（如循环展开以增加向量化机会）、SLP-E处理（核心的同构变换、代码调度和向量代码生成）和后处理（寄存器分配等）。研究团队将SLP-E方法在LLVM编译器框架（版本v11.01） 中进行了实现。为了评估其有效性，他们从SPEC CPU 2017/2006/2000以及Mediabench2 基准测试集中选取了一组能从自动向量化中受益的应用程序进行测试。测试分为两部分：内核函数测试，用于测试对不同类型（操作数不同、操作类型不同、操作顺序不同）特定代码片段的优化能力；整体性能测试，用于评估在完整基准程序上的综合性能提升。实验平台为支持AVX2等SIMD指令集的Intel i7处理器。性能对比对象是LLVM自身实现的SLP方法（包含了LSLP和SN-SLP等现有技术）。

三、 研究的主要结果

1. 内核函数测试结果 实验结果表明，SLP-E方法在内核测试中平均取得了1.77倍的加速比，显著高于LLVM-SLP方法的1.23倍加速比，平均性能提升达到43.9%。 * 针对操作数量不同的程序：SLP-E表现出了决定性优势。例如，在 gl_render_vb 函数中，LLVM-SLP由于常量折叠优化破坏了语句的同构性而无法向量化；而SLP-E通过将 i 扩展为 i - 0，成功恢复了同构性并实现了向量化，显著提升了性能。calc_pair_energy 和 jdct-ifast 的情况类似。 * 针对操作类型不同的程序：SLP-E与LLVM-SLP的性能提升效果基本相当，部分程序因生成的向量指令实际性能与标量指令相差无几而未获得显著加速，部分程序两者都能有效向量化并提升性能。 * 针对操作顺序不同的程序：两者性能提升效果也非常接近，因为SLP-E在无法应用扩展变换时，会回退到与LLVM-SLP相同的处理方式（如利用交换律重排操作顺序）。

2. 整体性能测试结果 在完整的基准测试集上，SLP-E方法平均取得了1.11倍的加速比，优于LLVM-SLP方法的1.07倍，整体性能提升达3.8%。这一提升在已被深入研究多年的科学计算和多媒体基准测试中具有重要价值。 研究发现，在整体测试中，SLP-E的扩展变换优化被大量触发（共358次），涵盖了 x = x + 0、x = x - 0、x = x << 0 等多种形式。这既包括原本就操作数不同的语句，也包括被编译器常量折叠优化“意外”破坏了的同构语句。SLP-E通过扩展变换，有效拓宽了同构变换的适用范围，从而在如 433.milc、453.povray 等程序中取得了性能增益。 研究也指出，在少数程序（如 410.bwaves）上，向量化后性能下降并非SLP-E优化所致，而是由于LLVM静态评估模型未能充分考虑内存访问和超标量处理器标量指令级并行等因素，做出了错误的向量化决策。在这些案例中，SLP-E的性能并未低于LLVM-SLP。

3. 算法有效性验证 通过对比图1中展示的各种向量化方法对示例程序的处理流程，直观地证明了SLP-E方法的有效性。对于包含操作数量差异的示例 c[i] = a[i] * b[i]; c[i+1] = a[i+1] * b[i+1] + 5;，传统SLP、LSLP、SN-SLP均因非同构而停止向量化；基于硬件的PSLP方法虽然能向量化，但需要引入额外的选择（select）指令，带来额外开销（效益评估为-1）；而SLP-E通过将第一个语句的加法部分扩展为 + 0，成功将非同构语句转化为同构语句，并实现了无额外指令开销的向量化，获得了最高的效益评估（+4）。这一示例清晰展示了等价扩展变换在解决操作数量差异问题上的独特优势。

四、 研究的结论与价值

本研究得出核心结论：提出的基于等价扩展变换的SLP-E自动向量化方法，能够有效解决操作数量不同的非同构语句的向量化问题，扩展了SLP的应用范围，提升了其向量化处理能力。

该研究的科学价值和应用价值主要体现在： 1. 问题创新：明确提出了“操作数量不同的非同构语句向量化”这一新的研究问题，并对其进行了深入分析，丰富了自动向量化领域的研究范畴。 2. 方法创新：首创性地引入了等价扩展变换这一新型程序变换技术，为编译器优化提供了一种新的语义保持的程序重构手段。 3. 算法创新：提出了基于最大公共子图（NM-MCS算法） 的全局差异分析方法和可扩展差分子图对的识别机制，为在复杂程序结构中定位优化机会提供了系统性的解决方案。 4. 实践价值：在广泛使用的LLVM编译器框架中实现了SLP-E，并通过主流基准测试验证了其有效性。实验证明，该方法能有效恢复因编译器标量优化而丢失的向量化机会，且不依赖于特定硬件指令，具有较好的通用性和实用性。 5. 性能提升：在核心测试和整体测试中分别实现了43.9%和3.8%的平均性能提升，证明了该方法对于提升移动计算等高能效平台上的程序性能具有实际意义。

五、 研究的亮点

1. 研究问题的针对性：精准地捕捉到了现有SLP扩展方法（LSLP, SN-SLP）的盲区——操作数量差异，并针对此“空白地带”展开研究。
2. 核心变换思想的独创性：提出的“等价扩展变换”（如 x = x + 0）看似简单，实则巧妙地利用了算术恒等式，以一种近乎零开销的方式（在向量化上下文中）改变数据依赖图的结构，为解决操作数量差异提供了简洁而强大的理论工具。
3. 全局分析视角：不同于现有方法（如LSLP）主要依赖局部贪婪搜索，SLP-E采用了基于最大公共子图的全局差异分析，能够更全面地把握语句间的结构关系，从而更准确地识别优化潜力点。
4. 系统化的工程实现与验证：不仅提出了理论方法，还完成了在复杂工业级编译器（LLVM）中的完整实现，并利用权威的SPEC CPU等基准测试集进行了详尽的定量评估，使研究成果具有很强的说服力和可重复性。

六、 其他有价值的讨论

论文在“未来工作”部分指出，后续研究方向包括：进一步优化和完善SLP-E方法本身；探索更多类型的程序等价变换及其对应的向量化方法，以进一步提升SLP对各类非同构语句的处理能力；研究如何在SLP中协同运用多种等价变换。这些方向为进一步深化自动向量化研究提供了清晰的路线图。

本研究是一项在编译器自动向量化领域具有显著创新性和实用价值的工作。它通过引入新颖的等价扩展变换和配套的全局分析算法，有效解决了一类长期被忽视的非同构语句向量化难题，为提升SIMD指令利用率和程序性能提供了新的有效工具。