InstCombine 贡献者指南

本指南列出了一系列 InstCombine 贡献应遵循的规则。**遵循这些规则将使 PR 更快得到批准。**

测试

预提交测试

新的优化或错误编译修复的测试应该预先提交。这意味着您首先提交包含 CHECK 行的测试，这些 CHECK 行显示了*未*应用您的更改时的行为。然后，您的实际更改将仅包含相对于该基线的 CHECK 行差异。

这意味着拉取请求通常应包含两个提交：首先，一个提交添加新的测试以及基线检查行。其次，一个提交包含功能更改和测试差异。

如果您的 PR 中的第二个提交不包含测试差异，则说明您操作有误。要么您在生成 CHECK 行时犯了错误，要么您的测试实际上不受您的补丁影响。

例外情况：修复断言失败或无限循环时，不要预提交测试。

使用 update_test_checks.py

CHECK 行应使用 update_test_checks.py 脚本生成。使用后**不要**手动编辑检查行。

使用脚本时，请确保使用正确的 opt 二进制文件。例如，如果您的构建目录是 build，那么您需要运行

llvm/utils/update_test_checks.py --opt-binary build/bin/opt \
    llvm/test/Transforms/InstCombine/the_test.ll

例外情况：调试信息测试允许手动编写 CHECK 行。

一般测试注意事项

将所有与转换相关的测试放在一个文件中。如果您要为现有转换中的崩溃/错误编译添加回归测试，请找到现有测试所在的文件。一个好方法是注释掉转换并查看哪些测试失败。

使测试尽量简洁。仅测试正在转换的确切模式。如果您的原始激励案例是一个更大的模式，您的折叠以某种非平凡的方式启用了对其进行优化，您也可以添加它——但是，测试覆盖率的大部分应该尽可能简洁。

为测试提供简短但有意义的名称。不要将其命名为 @test1、@test2 等。例如，一个检查涉及两个选择加法的折叠的多用途行为的测试可能被称为 @add_of_selects_multi_use。

为每个测试类别（如下所述）添加代表性测试，但不要测试所有组合。如果您有多用途测试，并且您有交换测试，则不应再添加交换多用途测试。

最好将测试的位宽保持较低，以提高使用 alive2 进行证明检查的性能。在可能的情况下，使用 i8 比 i128 更好。

添加负测试

确保为您的转换**不**应用的测试添加测试。从一个成功的测试用例开始，然后创建一系列负测试，以便在每个测试中，您的转换的**恰好一个**不同的先决条件不满足。

添加多用途测试

添加多用途测试，以确保如果某些指令有其他用途，您的转换不会增加指令计数。标准模式是使用函数调用引入额外的用途

declare void @use(i8)

define i8 @add_mul_const_multi_use(i8 %x) {
  %add = add i8 %x, 1
  call void @use(i8 %add)
  %mul = mul i8 %add, 3
  ret i8 %mul
}

例外情况：对于仅生成一条指令的转换，可以省略多用途测试。

添加交换测试

如果转换涉及交换运算，请添加具有交换（交换）操作数的测试。

确保操作数顺序在预提交测试的 CHECK 行中保持不变。您不应该看到类似这样的情况

; CHECK-NEXT: [[OR:%.*]] = or i8 [[X]], [[Y]]
; ...
%or = or i8 %y, %x

如果发生这种情况，您可能需要更改其中一个操作数以具有更高的复杂度（在这种情况下包含“thwart”注释）

%y2 = mul i8 %y, %y ; thwart complexity-based canonicalization
%or = or i8 %y, %x

添加向量测试

在可能的情况下，建议至少添加一个使用向量而不是标量的测试。

对于包含常量的模式，我们区分三种类型的测试。第一种是“splat”向量，其中所有向量元素都相同。这些测试通常*应该*无需额外努力即可折叠。

define <2 x i8> @add_mul_const_vec_splat(<2 x i8> %x) {
  %add = add <2 x i8> %x, <i8 1, i8 1>
  %mul = mul <2 x i8> %add, <i8 3, i8 3>
  ret <2 x i8> %mul
}

一个小的变体是将一些 splat 元素替换为 poison。这些通常也无需额外努力即可折叠。

define <2 x i8> @add_mul_const_vec_splat_poison(<2 x i8> %x) {
  %add = add <2 x i8> %x, <i8 1, i8 poison>
  %mul = mul <2 x i8> %add, <i8 3, i8 poison>
  ret <2 x i8> %mul
}

最后，您可以拥有非 splat 向量，其中向量元素不相同

define <2 x i8> @add_mul_const_vec_non_splat(<2 x i8> %x) {
  %add = add <2 x i8> %x, <i8 1, i8 5>
  %mul = mul <2 x i8> %add, <i8 3, i8 6>
  ret <2 x i8> %mul
}

非 splat 向量通常不会默认折叠。您**不应**尝试使其折叠，除非这样做不会增加**任何**额外的复杂性。即使它没有折叠，您仍然应该添加测试。

标志测试

如果您的转换涉及可能生成 poison 标志的指令，例如 add 上的 nuw 和 nsw，您应该测试这些指令如何与转换交互。

如果您的转换*需要*某个标志才能正确执行，请确保添加缺少所需标志的负测试。

如果您的转换不需要标志才能正确执行，则应进行保留行为测试。如果输入指令具有某些标志，它们是否保留在输出指令中，如果保留它们是否有效？（这取决于转换。请咨询 alive2。）

快速数学标志 (FMF) 也适用。在这种情况下，请始终测试特定的标志，例如 nnan、nsz 或 reassoc，而不是总括的 fast 标志。

其他测试

上面提到的测试类别并不详尽。可能需要添加更多测试，具体取决于转换中涉及的指令。一些例子

• 对于涉及内存访问（如加载/存储）的折叠，请检查可扩展向量和非字节大小类型（如 i3）是否被正确处理。还要检查 volatile/atomic 是否被处理。

• 对于以某种非平凡方式与位宽交互的折叠，请检查非法类型，如 i13。还要确认转换对于 i1 是否正确。

• 对于涉及 phi 的折叠，您可能需要检查来自一个块的多个传入值的情况是否被正确处理。

证明

您的拉取请求描述应包含一个或多个 alive2 证明，以证明所提议转换的正确性。

基础知识

证明使用 LLVM IR 编写，通过指定 @src 和 @tgt 函数。可以通过为 src 和 tgt 函数提供匹配的后缀，在一个文件中包含多个证明。

例如，以下是一对证明，证明 (x-y)+y 和 (x+y)-y 都可以简化为 x（在线）

define i8 @src_add_sub(i8 %x, i8 %y) {
  %add = add i8 %x, %y
  %sub = sub i8 %add, %y
  ret i8 %sub
}

define i8 @tgt_add_sub(i8 %x, i8 %y) {
  ret i8 %x
}


define i8 @src_sub_add(i8 %x, i8 %y) {
  %sub = sub i8 %x, %y
  %add = add i8 %sub, %y
  ret i8 %add
}

define i8 @tgt_sub_add(i8 %x, i8 %y) {
  ret i8 %x
}

在证明中使用通用值

证明应该在通用值上运行，而不是在特定常量上运行，在可能的情况下做到这一点。

例如，如果我们想要将 X s/ C s< X 折叠为 X s> 0，以下将是一个错误的证明

; Don't do this!
define i1 @src(i8 %x) {
  %div = sdiv i8 %x, 123
  %cmp = icmp slt i8 %div, %x
  ret i1 %cmp
}

define i1 @tgt(i8 %x) {
  %cmp = icmp sgt i8 %x, 0
  ret i1 %cmp
}

这是因为它只证明了转换对于特定常量 123 是正确的。也许有一些常量会导致转换不正确？

编写此证明的正确方法如下所示（在线）

define i1 @src(i8 %x, i8 %C) {
  %precond = icmp ne i8 %C, 1
  call void @llvm.assume(i1 %precond)
  %div = sdiv i8 %x, %C
  %cmp = icmp slt i8 %div, %x
  ret i1 %cmp
}

define i1 @tgt(i8 %x, i8 %C) {
  %cmp = icmp sgt i8 %x, 0
  ret i1 %cmp
}

请注意，@llvm.assume 内联函数用于指定转换的先决条件。在这种情况下，除非我们指定 C != 1 作为先决条件，否则证明将失败。

需要强调的是，通常不期望证明中的 IR 会被实现的折叠转换。在上面的例子中，只有当 %C 实际上是常量时，转换才会应用，但我们需要在证明中使用非常量。

常见先决条件

以下是一些常见先决条件的示例。

; %x is non-negative:
%nonneg = icmp sgt i8 %x, -1
call void @llvm.assume(i1 %nonneg)

; %x is a power of two:
%ctpop = call i8 @llvm.ctpop.i8(i8 %x)
%pow2 = icmp eq i8 %x, 1
call void @llvm.assume(i1 %pow2)

; %x is a power of two or zero:
%ctpop = call i8 @llvm.ctpop.i8(i8 %x)
%pow2orzero = icmp ult i8 %x, 2
call void @llvm.assume(i1 %pow2orzero)

; Adding %x and %y does not overflow in a signed sense:
%wo = call { i8, i1 } @llvm.sadd.with.overflow(i8 %x, i8 %y)
%ov = extractvalue { i8, i1 } %wo, 1
%ov.not = xor i1 %ov, true
call void @llvm.assume(i1 %ov.not)

超时

Alive2 证明有时会产生超时，并显示以下消息

Alive2 timed out while processing your query.
There are a few things you can try:

- remove extraneous instructions, if any

- reduce variable widths, for example to i16, i8, or i4

- add the --disable-undef-input command line flag, which
  allows Alive2 to assume that arguments to your IR are not
  undef. This is, in general, unsound: it can cause Alive2
  to miss bugs.

这是一个很好的建议，请遵循它！

减少位宽通常会有所帮助。对于浮点数，您可以使用 half 类型来减少位宽。对于指针，您可以通过指定自定义数据布局来减少位宽

; For 16-bit pointers
target datalayout = "p:16:16"

如果减少位宽没有帮助，请尝试 -disable-undef-input。这通常会显着提高性能，但也意味着不再验证具有 undef 值的转换的正确性。如果转换不会增加任何值的用途数量，这通常是可以的。

最后，您可以本地构建 alive2 并使用 -smt-to=<m> 来验证具有更大超时的证明。如果您不想这样做（或者它仍然不起作用），请尽管提交您现有的证明，即使它超时了。

实现

现实世界的实用性

有非常大量的转换*可以*实现，但只有一小部分对现实世界的代码有用。

没有现实世界实用性的转换会对 LLVM 项目产生负面影响，因为它们会占用宝贵的审查时间，增加代码复杂性并增加编译时间开销。

我们不要求对每个转换都进行明确的现实世界实用性证明——在大多数情况下，实用性是相当“显而易见”的。但是，对于复杂或不寻常的折叠，这个问题可能会出现。在选择工作内容时请记住这一点。

特别是，如果缺少来自模糊测试生成的优化报告改进的现实世界用例证据，则可能会被拒绝。

选择正确的优化过程

InstCombine 系列中有很多过程和实用程序，在实现折叠时选择正确的位置非常重要。

• ConstantFolding：用于将具有常量参数的指令折叠为常量。（主要与内联函数相关。）

• ValueTracking：用于分析指令，例如已知位、非零等。测试通常应该使用 -passes=instsimplify。

• InstructionSimplify：用于不创建新指令的折叠（折叠到现有值或常量）。

• InstCombine：用于创建或修改指令的折叠。

• AggressiveInstCombine：用于代价高昂或违反 InstCombine 要求的折叠。

• VectorCombine：用于需要目标相关成本建模的向量操作折叠。

有时，逻辑上属于 InstSimplify 的折叠会放在 InstCombine 中，例如因为它们代价过高，或者因为在 InstCombine 中实现结构更简单。

例如，如果折叠在某些情况下生成新指令，而在其他情况下返回现有值，那么最好将所有情况都保留在 InstCombine 中，而不是尝试将它们拆分到 InstCombine 和 InstSimplify 中。

规范化和目标独立性

InstCombine 是一个目标独立的规范化过程。这意味着它试图将 IR 转换为其他优化（InstCombine 内部和外部）可以依赖的“规范形式”。出于这个原因，选择的规范形式需要对所有目标相同，并且不依赖于目标特定的成本建模。

在许多情况下，“规范化”和“优化”是重合的。例如，如果我们将 x * 2 转换为 x << 1，这既使 IR 更规范（因为现在只有一种方法可以表达相同的操作，而不是两种），也更快（因为移位通常比乘法具有更低的延迟）。

但是，也有一些规范化没有直接的优化目的。例如，InstCombine 将把非严格谓词（如 ule）规范化为严格谓词（如 ult）。icmp ule i8 %x, 7 变为 icmp ult i8 %x, 8。这在任何有意义的意义上都不是优化，但它确实减少了其他转换需要处理的情况数量。

如果某些规范化对特定目标没有好处，则需要在后端添加反向转换。禁用某些目标上特定 InstCombine 转换或使用目标特定成本建模来驱动它们的补丁将**不会被接受**。唯一允许的目标依赖性是 DataLayout 和 TargetLibraryInfo。

TargetTransformInfo 的使用仅允许用于目标特定内联函数的钩子，例如 TargetTransformInfo::instCombineIntrinsic()。无论如何，这些本身就是目标相关的。

对于需要成本建模的特定于向量的转换，可以使用 VectorCombine 过程。在非常罕见的情况下，如果没有其他替代方案，目标相关的转换可能会被接受到 AggressiveInstCombine 中。

模式匹配

许多转换利用了在 PatternMatch.h 中定义的匹配基础结构。

这是一个典型的用法示例

// Fold (A - B) + B and B + (A - B) to A.
Value *A, *B;
if (match(V, m_c_Add(m_Sub(m_Value(A), m_Value(B)), m_Deferred(B))))
  return A;

还有一个

// Fold A + C1 == C2 to A == C1+C2
Value *A;
if (match(V, m_ICmp(Pred, m_Add(m_Value(A), m_APInt(C1)), m_APInt(C2))) &&
    ICmpInst::isEquality(Pred))
  return Builder.CreateICmp(Pred, A,
                            ConstantInt::get(A->getType(), *C1 + *C2));

一些常见的匹配器是

• m_Value(A)：匹配任何值并将其写入 Value *A。

• m_Specific(A)：检查操作数是否等于 A。如果 A 在模式**外部**分配，则使用此方法。

• m_Deferred(A)：检查操作数是否等于 A。如果 A 在模式**内部**分配，例如通过 m_Value(A)，则使用此方法。

• m_APInt(C)：将标量整数常量或散列向量常量匹配到 const APInt *C。不允许 undef/poison 值。

• m_ImmConstant(C)：将任何非常量表达式常量匹配到 Constant *C。

• m_Constant(C)：将任何常量匹配到 Constant *C。除非你了解自己在做什么，否则不要使用它。

• m_Add(M1, M2)、m_Sub(M1, M2) 等：匹配加法/减法/等，其中第一个操作数匹配 M1，第二个操作数匹配 M2。

• m_c_Add(M1, M2) 等：交换匹配加法。操作数必须匹配 M1 和 M2 或 M2 和 M1。大多数指令匹配器都有交换变体。

• m_ICmp(Pred, M1, M2) 和 m_c_ICmp(Pred, M1, M2)：匹配 icmp，将谓词写入 IcmpInst::Predicate Pred。如果使用交换版本，并且操作数按顺序匹配 M2、M1，则 Pred 将是交换后的谓词。

• m_OneUse(M)：检查值是否只有一个使用，并且也匹配 M。例如 m_OneUse(m_Add(...))。有关更多信息，请参阅下一节。

有关可用匹配器的完整列表，请参阅标头。

InstCombine API

InstCombine 转换由 visitXYZ() 方法处理，其中 XYZ 对应于转换的根指令。如果匹配的模式的最外层指令是 icmp，则折叠将位于 visitICmpInst() 内部。

访问方法的返回值是一个指令。你可以返回一个新的指令，在这种情况下，它将插入到旧指令之前，旧指令的使用将被替换为它。或者，你可以返回原始指令以指示已进行了某种更改。最后，空指针返回值表示没有发生更改。

例如，如果你的转换生成单个新的 icmp 指令，你可以编写以下内容

if (...)
  return new ICmpInst(Pred, X, Y);

在这种情况下，主要的 InstCombine 循环负责插入指令并替换旧指令的使用。

或者，你也可以这样编写它

if (...)
  return replaceInstUsesWith(OrigI, Builder.CreateICmp(Pred, X, Y));

在这种情况下，IRBuilder 将插入指令，replaceInstUsesWith() 将替换旧指令的使用，并返回它以指示发生了更改。

这两种形式是等效的，你可以根据上下文使用任何一种更方便的形式。例如，折叠通常位于返回 Value * 的辅助函数中，然后对该辅助函数的结果调用 replaceInstUsesWith()。

InstCombine 使用工作列表，在转换期间需要正确更新该工作列表。这通常会自动发生，但有一些需要注意的事项

• 不要使用 Value::replaceAllUsesWith() API。请改用 InstCombine 的 replaceInstUsesWith() 辅助函数。

• 不要使用 Instruction::eraseFromParent() API。请改用 InstCombine 的 eraseInstFromFunction() 辅助函数。（显式删除指令通常是不必要的，因为没有用户的无副作用指令会自动删除。）

• 除了上面“直接返回指令”模式之外，请使用 IRBUilder 创建所有指令。不要手动创建和插入它们。

• 替换指令的操作数或使用时，请使用 replaceOperand() 和 replaceUse() 而不是 setOperand()。

多用途处理

转换通常不应增加指令的总数。这不是一个硬性要求：例如，用多个其他指令替换单个除法指令通常是值得的。

例如，如果你有一个转换用两个其他指令替换两个指令，那么（通常）只有在可以删除两个原始指令时才有利。为了确保删除这两个指令，你需要为内部指令添加一个单一使用检查。

可以使用 m_OneUse() 匹配器或 V->hasOneUse() 方法执行单一使用检查。

泛化

转换既可能过于具体（只处理某些奇怪的模式子集，导致意外的优化悬崖），也可能过于通用（引入复杂性以处理与现实世界无关的情况）。正确的泛化程度是相当主观的，因此本节仅提供一些广泛的指导。

• 避免硬编码到特定常量的转换。尝试找出任意常量的一般规则是什么。

• 为共轭模式添加处理。例如，如果你为 icmp eq 实现折叠，那么你几乎肯定也希望支持 icmp ne，结果相反。类似地，如果你为 and 的 icmp 实现一个模式，你也应该使用 or 处理德摩根共轭。

• 如果这样做是免费的，则处理非散列向量常量，但如果它增加了代码的任何额外复杂性，则不要为它们添加处理。

• 除非有特定动机，否则不要处理非规范模式。例如，有时可能值得处理一个通常会被转换为不同规范形式的模式，但它仍然可能出现在多用途场景中。如果存在具体的现实世界动机，这样做是可以的，但否则你不应该特意这样做。

• 有时，激励模式使用具有某些属性的常量值，但可以通过利用 ValueTracking 查询将折叠推广到非常量值。这是否合理取决于具体情况，但通常最好先只处理常量模式，然后在以后看起来有用时再进行推广。

审阅者指南

• 不要要求新的贡献者在代码审查中实现非 splat 向量支持。如果您认为某个折叠的非 splat 向量支持既有价值又符合策略（也就是说，处理不会导致代码复杂度明显增加），请在后续补丁中自己实现它。