InstCombine 贡献者指南

本指南列出了一系列 InstCombine 贡献应遵循的规则。遵循这些规则将大大加快 PR 审核速度。

测试

预提交测试

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

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

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

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

使用 update_test_checks.py

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

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

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

例外情况：debuginfo 测试允许手写 CHECK 行。

通用测试注意事项

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

使测试尽可能精简。仅测试正在转换的模式。如果您的原始动机案例是一个更大的模式，您的折叠使其能够以某种非平凡的方式进行优化，您也可以添加它 - 但是，测试覆盖率的大部分应该是最小的。

为测试提供简短但有意义的名称。不要将它们称为 @test1、@test2 等。例如，检查涉及两个 select 相加的折叠的多用途行为的测试可以称为 @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
}

一个小的变体是用 poison 替换一些 splat 元素。这些通常也会在没有额外努力的情况下折叠。

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 标志。

其他测试

上面提到的测试类别并非详尽无遗。根据转换中涉及的指令，可能需要添加更多测试。一些例子

• 对于涉及内存访问（如 load/store）的折叠，请检查是否正确处理了可伸缩向量和非字节大小类型（如 i3）。还要检查是否处理了 volatile/atomic。

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

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

证明

您的拉取请求描述应包含一个或多个 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 项目带来负面价值，它们会占用宝贵的审阅者时间，增加代码复杂度并增加编译时开销。

我们不要求对每个转换都提供实际应用价值的明确证明——在大多数情况下，实用性是相当“明显”的。但是，对于复杂或不寻常的折叠，可能会出现这个问题。在选择您要从事的工作时，请记住这一点。

特别是，如果没有任何实际应用价值的证据，则针对 fuzzer 生成的遗漏优化报告的修复可能会被拒绝。

选择正确的优化 pass

InstCombine 家族中有许多 pass 和实用程序，在实现折叠时选择正确的位置非常重要。

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

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

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

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

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

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

有时，逻辑上属于 InstSimplify 的折叠会放在 InstCombine 中，例如因为它们太昂贵，或者因为它们在 InstCombine 中实现起来结构更简单。

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

规范化和目标无关性

InstCombine 是一个目标无关的规范化 pass。这意味着它试图将 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 pass 代替。在极少数情况下，如果没有其他替代方案，则目标相关的转换可能会被接受到 AggressiveInstCombine 中。

PatternMatch

许多转换都使用了在 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)：将标量整数常量或 splat 向量常量匹配到 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() 中的某个位置。

visit 方法的返回值是一个指令。您可以返回一个新指令，在这种情况下，它将在旧指令之前插入，并且旧指令的用途将被替换为新指令。或者您可以返回原始指令，以指示已进行某种更改。最后，nullptr 返回值表示未发生任何更改。

例如，如果您的转换生成单个新的 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，结果相反。类似地，如果您为 icmp 的 and 实现模式，您还应该使用 or 处理德摩根共轭。

• 如果处理非 splat 向量常量是免费的，请处理它们，但如果它给代码增加了任何额外的复杂性，则不要添加对它们的处理。

• 除非有特定的动机这样做，否则不要处理非规范模式。例如，有时可能值得处理通常会转换为不同规范形式的模式，但仍然可能在多用途场景中发生。如果有特定的实际应用价值动机，这样做是可以的，但否则您不应该特意这样做。

• 有时，动机模式使用具有某些属性的常量值，但可以通过使用 ValueTracking 查询将折叠泛化为非常量值。这是否有意义取决于具体情况，但通常最好先处理常量模式，然后在看起来有用时稍后进行泛化。

审阅者指南

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