向量化计划¶
摘要¶
向量化转换可能相当复杂，涉及多个潜在的替代方案，尤其是在外层循环[1]中，但可能也包括最内层循环。这些替代方案可能会对性能产生重大影响，既有积极的，也有消极的。因此，采用成本模型来识别最佳替代方案，包括完全避免任何转换的替代方案。
向量化计划是用于描述向量化候选对象的显式模型。它既用于优化候选对象（包括可靠地估计其成本），也用于将其最终转换为 IR。这有利于处理多个向量化候选对象。
当前状态¶
VPlan 目前用于驱动 LoopVectorize 中的代码生成。在做出所有基于成本的决策和大多数合法性相关的决策后，构建 VPlan。由于 VPlan 中现在完全模拟了配方之间的 def-use 链，因此使用基于 VPlan 的分析和转换来简化和模块化向量化过程[10]。其中包括以下转换：
使初始 VPlan 合法化，例如，为归约和交错组引入专门的配方。
优化合法化的 VPlan，例如，删除冗余配方或引入活动车道掩码。
应用展开和向量化因子特定的优化，例如，根据 VF 和 UF 删除后边来重复向量循环。
有关当前转换管道的概述，请参阅图 3。
请注意，某些合法性检查已在 VPlan 中完成，包括检查固定顺序递归的所有用户是否都可以重新排序。这是作为 VPlan 到 VPlan 的转换实现的，该转换要么应用有效的重新排序，要么退出并标记 VPlan 为无效。
图 3 2024 年的 VPlan 转换管道¶
VPlan 目前模拟完整的向量循环，以及向量化框架的其他部分。有关 VPlan 涵盖范围的概述，请参阅图 4。
图 4 2024 年 VPlan 中建模的范围¶
高级设计¶
向量化工作流程¶
基于 VPlan 的向量化涉及三个主要步骤，采用“基于场景的方法”来进行向量化计划
合法性步骤：检查循环是否可以合法地进行向量化；如果是，则编码约束和工件。
计划步骤
根据合法性步骤 1 中做出的约束和决策构建初始 VPlan，并计算其成本。
对 VPlan 应用优化，可能派生额外的 VPlan。修剪成本相对较高的次优 VPlan。
执行步骤：具体化最佳 VPlan。请注意，这是唯一修改 IR 的步骤。
设计指南¶
在下文中，“输入 IR”是指馈送到向量化器的代码，而“输出 IR”是指向量化器生成的代码。输出 IR 包含根据循环向量化因子 (VF) 进行向量化或“加宽”的代码，以及根据展开因子 (UF) 进行循环展开和合并的代码。VPlan 的设计遵循几个高级指南
类似分析：构建和操作 VPlan 绝不能修改输入 IR。特别是，如果最佳选择是根本不进行向量化，则向量化过程在到达步骤 3 之前终止，并且编译应像未构建 VPlan 一样继续进行。
成本与执行对齐：每个 VPlan 必须同时支持估计成本和生成输出 IR 代码，以便成本估计可靠地评估要生成的代码。
支持向量化其他结构
有效地支持多个候选对象。特别是，与一系列可能的 VF 和 UF 相关的类似候选对象必须有效地表示。需要有效地支持潜在的版本控制。
支持向量化习语，例如交错的步长加载或存储组。这是通过使用“配方”对输出指令序列进行建模来实现的，该配方负责计算其成本并生成其代码。
封装单入口单出口区域 (SESE)。在向量化期间，可能需要例如对这些区域进行谓词化和线性化，或者复制 VF*UF 次以处理标量化和谓词化指令。内层循环也建模为 SESE 区域。
支持指令级分析和转换，作为计划步骤 2.b 的一部分：在向量化期间，可能需要遍历、移动、替换为其他指令或创建指令。例如，向量习语检测和形成涉及搜索和优化指令模式。
定义¶
VPlan 的低级设计包含以下类。
- LoopVectorizationPlanner:
LoopVectorizationPlanner 旨在处理循环或循环嵌套的向量化。它可以构建、优化和丢弃一个或多个 VPlan，每个 VPlan 模拟向量化循环或循环嵌套的不同方式。一旦确定了最佳 VPlan（包括最佳 VF 和 UF），此 VPlan 就会驱动输出 IR 的生成。
- VPlan:
给定输入 IR 循环或循环嵌套的向量化候选对象的模型。此候选对象使用分层 CFG 表示。VPlan 支持估计成本并驱动其表示的输出 IR 代码的生成。
- 分层 CFG:
其节点是基本块或分层 CFG 的控制流图。分层 CFG 数据结构类似于 Tile Tree[5]，其中跨 Tile 边缘被提升以连接 Tile 而不是像 Sharir[6]中那样连接原始基本块，从而促进 Tile 封装。术语 Region 和 Block 用于代替 Tile[5]，以避免与循环平铺混淆。
- VPBlockBase:
分层 CFG 的构建块。VPBasicBlock 和 VPRegionBlock 的纯虚基类，见下文。VPBlockBase 使用其他 VPBlock 对分层控制流关系进行建模。请注意，与 IR BasicBlock 相比，VPBlockBase 直接对它的控制流后继和前驱进行建模，而不是通过 Terminator 分支或通过“使用”VPBlockBase 的前驱分支进行建模。
- VPBasicBlock:
VPBasicBlock 是 VPBlockBase 的子类，并用作分层 CFG 的叶子。它表示将在输出 IR 基本块中连续出现的输出 IR 指令序列。此基本块的指令源自一个或多个 VPBasicBlock。VPBasicBlock 持有一系列零个或多个 VPRecipe，这些配方模拟输出 IR 指令的成本和生成。
- VPRegionBlock:
VPRegionBlock 是 VPBlockBase 的子类。它模拟构成输出 IR CFG 的 SESE 子图的 VPBasicBlock 和 VPRegionBlock 集合。VPRegionBlock 可能会指示在生成输出 IR 时将其内容复制固定次数，有效地表示具有恒定循环次数的循环，该循环将被完全展开。这用于支持具有单个模型的标量化和谓词化指令，以用于多个候选 VF 和 UF。
- VPRecipeBase:
一个纯虚基类，对一个或多个输出 IR 指令的序列进行建模，可能基于一个或多个输入 IR 指令。这些输入 IR 指令称为配方的“成分”。配方可以指定如何转换其成分以生成输出 IR 指令；例如，克隆一次、复制多次或根据选定的 VF 加宽。
- VPValue:
VPlan 的 def-use 关系类层次结构的基类。当实例化时，它模拟 VPlan 中的常量或活动输入值。它有用户，其类型为 VPUser，但没有操作数。
- VPUser:
VPUser 表示一个使用多个 VPValue 作为操作数的实体。VPUser 在某些方面类似于 LLVM 的 User 类。
- VPDef:
VPDef 表示定义零个、一个或多个 VPValue 的实体。它用于模拟 VPlan 中的配方可以定义多个 VPValue 的事实。
- VPInstruction:
VPInstruction 是一个以单个操作码和可选标志为特征的配方，没有成分或其他元数据。VPInstruction 还使用丰富向量化器语义的习语操作扩展了 LLVM IR 的操作码。
- VPTransformState:
存储用于生成输出 IR 的信息，从 LoopVectorizationPlanner 传递到其选定的 VPlan 以供执行，并用于将其他信息传递给 VPBlock 和 VPRecipe。
计划过程和 VPlan 路线图¶
将循环向量化器转换为使用 VPlan 遵循分阶段方法。首先，VPlan 仅用于记录最终的向量化决策，并执行这些决策：分层 CFG 对计划的控制流进行建模，配方捕获在基本块内做出的决策。目前，VPlan 也用作做出这些决策的基础，有效地将它们转换为一系列 VPlan 到 VPlan 的算法。最后，VPlan 将支持计划过程本身，包括用于做出这些决策的基于成本的分析，以完全支持组合和迭代决策制定。
一些决策对于循环中的指令是局部的，例如是否将其扩展为向量指令或进行复制，同时保持生成的指令不变。然而，其他决策则涉及移动指令、用其他指令替换它们和/或引入新的指令。例如，一个类型转换可能会下沉到后面的指令之后，并被扩展以处理一阶递归；一系列跨步加载或存储的交错组可能会有效地移动到一个地方，在那里它们被替换为混洗和一个通用的宽向量加载或存储；可以引入新的指令来计算掩码、混洗向量的元素，以及将标量值打包成向量或反之亦然。
为了让 VPlan 支持做出指令级决策和分析，它需要对相关的指令及其 def/use 关系进行建模。这也遵循一个分阶段的方法：首先，计算掩码的新指令被建模为 VPInstructions，以及它们所诱导的 def/use 子图。这有效地将掩码建模到 VPlan 中，促进了基于 VPlan 的谓词化。接下来，嵌入在每个 Recipe 中用于在 VPlan 执行时生成其指令的逻辑，将改为参与计划过程，将其建模为 VPInstructions。最后，只有适用于指令组的逻辑将保留在 Recipe 中，例如交错组和可能的其他具有协同成本的习语组。