第一次给LLVM的Contribution

2023.9.21修改：LLVM的patch以及完全迁移到Github PR上，本篇文章有关Phabricator的操作已经out-of-dated。

为什么要参与LLVM的开源？

由于一直以来对编译器后端特别感兴趣，又曾用LLVM作为后端为自己的语言进行AOT的编译， 我对LLVM的内部十分好奇，于是想通过为LLVM贡献代码的方式了解LLVM，并了解编译器优化的流程。

于是我参考了一位LLVM Member的文章: How to contribute to llvm?

以下则是我从编译到提交patch的全流程。

编译

要为LLVM贡献代码，那首先能在本地编译LLVM库。

那么我们首先要clone LLVM的git仓库，或者自己fork了llvm-project后再clone到本地。二者区别不大，我按照github的开源习惯选了后者。

clone完之后我们开始编译，这边要注意的是：由于计算机编译速度的限制，我们一边建议进行Release编译。否则一次编译链接要长达几小时的时间。 以下是cmake的模板：

cmake -GNinja -Bbuild -Hllvm \
    -DLLVM_ENABLE_PROJECTS="clang" \
    -DLLVM_TARGETS_TO_BUILD="all" \
    -DCMAKE_BUILD_TYPE=Release \
    -DLLVM_ENABLE_ASSERTIONS=true \
    -DLLVM_CCACHE_BUILD=true \
    -DLLVM_USE_LINKER=lld

其中Debug可通过-debug flag来进行，你可以在对应的代码位置用errs() << something进行输出。

而ninja的编译速度相对较快，所以以下有构建和测试的shell：

# Build LLVM
ninja -Cbuild

# Run all LLVM tests
ninja -Cbuild check-llvm

# Run tests in a specific directory.
# -v will print additional information for failures.
build/bin/llvm-lit -v llvm/test/Transforms/InstCombine

选Issue

由于我是LLVM领域的新手，不太可能一上来就砍大龙，所以我挑了个简单的任务。 而llvm-project包括许多子项目，包括LLVM本身、Clang编译器、LLD链接器、libc++标准库以及许多其他项目。即使在LLVM本身中也有不同的领域。主要分为与中端优化器与LLVM中间表示(IR)有关的项目，和与后端将IR转换为机器代码有关的项目。

而我对中端的了解比较多，而且中端优化的代码有许多corner cases，可以通过简单的几行代码解决这些cases， 所以本博客主要针对中端IR优化的InstCombine进行讨论，挑选的也是InstCombine Issue。 当然，LLVM还有许多其他容易解决的Issue，如：good first issues，Clang，Flang还有clang-tidy和clang-format等项目的Issue。

在这里我将展示我的一次LLVM贡献经历：D154126

相关Issue。

问题分析

这篇Issue里提到的问题为: (a > b) | (a < b) 的优化会在 b == 0 时失效。

而一般的 (a > b) | (a < b) 会折叠为 ZExt(a != 0)，对应的LLVM-IR如下：

define i32 @src(i32 %A, i32 %B) {
%1:
  %2 = icmp sgt i32 %A, %B
  %3 = zext i1 %2 to i32
  %4 = icmp slt i32 %A, %B
  %5 = zext i1 %4 to i32
  %6 = or i32 %3, %5
  ret i32 %6
}
=>
define i32 @tgt(i32 %A, i32 %B) {
%1:
  %2 = icmp ne i32 %A, %B
  %3 = zext i1 %2 to i32
  ret i32 %3
}

但对于 b == 0 的case，其对应的InstCombine优化为：

define i32 @src(i32 %A) {
%1:
  %2 = icmp sgt i32 %A, 0
  %3 = zext i1 %2 to i32
  %4 = lshr i32 %A, 31
  %5 = or i32 %4, %3
  ret i32 %5
}
=>
define i32 @tgt(i32 %A) {
%1:
  %2 = icmp sgt i32 %A, 0
  %3 = zext i1 %2 to i32 
  %4 = lshr i32 %A, 31
  %5 = or i32 %3, %4
  ret i32 %5
}

也就是说在这种情况下 A < 0 被优化成了 A << 31，而之前对应的 A < B | A > B 的Pattern Matching被破坏掉了。

在分析如何解决这个优化问题前，我们先了解LLVM的中端优化代码提交patch的特殊规则。

LLVM的patch由两部分组成，第一部分是impl前的misoptimization tests，第二部分则是impl以及应用impl后的tests。 这样分解patch的好处有以下2点：

1. 便于通过对tests的前后对比查看你实现的优化效果。
2. 可以把tests作为单独的patch提交，这样能简单提高LLVM的测试量。

除此之外，在你提交patch前，你还要证明你优化的正确性。

证明Transform的正确性

一般来讲，我们会使用 alive2 验证不同LLVM-IR的正确性，online版。 本篇的Issue的alive2结果如下：

define i32 @src(i32 %0) {
%1:
  %2 = icmp sgt i32 %0, 0
  %3 = zext i1 %2 to i32
  %4 = lshr i32 %0, 31
  %5 = or i32 %4, %3
  ret i32 %5
}
=>
define i32 @tgt(i32 %0) {
%1:
  %2 = icmp ne i32 %0, 0
  %3 = zext i1 %2 to i32
  ret i32 %3
}
Transformation seems to be correct!

虽然alive2是确保LLVM转换正确性的非常重要的工具，但值得注意的是它可能会产生false negative结果（即有时它会声称一个不正确的转换是正确的）。这通常发生在循环优化的背景下，并且通常不会影响InstCombine优化。

测试

在我们写impl之前，我们需要先完成所有testcases的构建。

首先是基本成功转换的测试样例:

define i32 @icmp_slt_0_or_icmp_sgt_0_i32(i32 %x) {
; CHECK-LABEL: @icmp_slt_0_or_icmp_sgt_0_i32(
; CHECK-NEXT:    [[B:%.*]] = icmp sgt i32 [[X:%.*]], 0
; CHECK-NEXT:    [[X_LOBIT:%.*]] = lshr i32 [[X]], 31
; CHECK-NEXT:    [[D:%.*]] = zext i1 [[B]] to i32
; CHECK-NEXT:    [[E:%.*]] = or i32 [[X_LOBIT]], [[D]]
; CHECK-NEXT:    ret i32 [[E]]
;
  %A = icmp slt i32 %x, 0
  %B = icmp sgt i32 %x, 0
  %C = zext i1 %A to i32
  %D = zext i1 %B to i32
  %E = or i32 %C, %D
  ret i32 %E
}

注意，其中的CHECK-LABEL后的是testcase的函数名，CHECK-NEXT后则是经过转换后期望的IR，在测试时若不满足期望，则会返回失败的测试报告。 这里的测试是未进行优化时的结果，故CHECK的结果也自然是未优化的。 当然这里CHECK的内容不用自己直接输入，可以用llvm的脚本自动生成，脚本如下：

llvm/utils/update_test_checks.py --opt-bin build/bin/opt \
    llvm/test/Transforms/InstCombine/and-or-icmps.ll

这段脚本会用InstCombine对and-or-icmps的每个testcase进行一次优化，并把优化结果作为CHECK的IR插入到and-or-icmps中。

而上面的测试用例只考虑了i32的基本类型，这里我们再添加i64的测试类型:

define i64 @icmp_slt_0_or_icmp_sgt_0_i64(i64 %x) {
  %A = icmp slt i64 %x, 0
  %B = icmp sgt i64 %x, 0
  %C = zext i1 %A to i64
  %D = zext i1 %B to i64
  %E = or i64 %C, %D
  ret i64 %E
}

除此之外，我们还需要一些反例(如改变左移的位数，把大于变为小于等)，防止我们的转换误优化，一例如下：

define i64 @icmp_slt_0_or_icmp_sgt_0_i64_fail2(i64 %x) {
; CHECK-LABEL: @icmp_slt_0_or_icmp_sgt_0_i64_fail2(
; CHECK-NEXT:    [[B:%.*]] = icmp sgt i64 [[X:%.*]], 0
; CHECK-NEXT:    [[C:%.*]] = lshr i64 [[X]], 62
; CHECK-NEXT:    [[D:%.*]] = zext i1 [[B]] to i64
; CHECK-NEXT:    [[E:%.*]] = or i64 [[C]], [[D]]
; CHECK-NEXT:    ret i64 [[E]]
;
  %B = icmp sgt i64 %x, 0
  %C = lshr i64 %x, 62
  %D = zext i1 %B to i64
  %E = or i64 %C, %D
  ret i64 %E
}

最后，我们可能还要考虑向量化的测试如下：

define <2 x i64> @icmp_slt_0_or_icmp_sgt_0_i64x2(<2 x i64> %x) {
  %A = icmp slt <2 x i64> %x, <i64 0,i64 0>
  %B = icmp sgt <2 x i64> %x, <i64 0,i64 0>
  %C = zext <2 x i1> %A to <2 x i64>
  %D = zext <2 x i1> %B to <2 x i64>
  %E = or <2 x i64> %C, %D
  ret <2 x i64> %E
}

完成这些testcases后我们进行一次commit。

实现

最终到了我们的实现部分，在实现之前，我们要进行有关的分析/debug的工作。

我们在这里通过build/bin/opt -passes=instcombine -S -debug src.ll进行Debug，在不同函数中插入打印的函数，从而根据输出判断优化的代码位置。

经过一系列排查，我们可以发现当b == 0时无法优化的原因是在 InstCombineAndOr.cpp中的transformZExtICmp函数会把ZExt(a < 0)转化为a << 31。

而优化 a < b | a > b 的函数foldAndOrOfICmpsUsingRanges无法识别a << 31这样的语句，自然就无法优化了。 由于笔者并不是特别清楚InstCombine优化的顺序，故笔者选择在foldCastedBitwiseLogic中增加对Zext(a > 0) | a << 31的匹配，并进行对应的优化。 代码如下：

// ( A << (X - 1) ) | ((A > 0) zext to iX)
// <=> A < 0 | A > 0
// <=> (A != 0) zext to iX
Value *A;
ICmpInst::Predicate Pred;

auto MatchOrZExtICmp = [&](Value *Op0, Value *Op1) -> bool {
return match(Op0, m_LShr(m_Value(A), m_SpecificInt(Op0->getType()->getScalarSizeInBits() - 1))) &&
       match(Op1, m_ZExt(m_ICmp(Pred, m_Specific(A), m_Zero())));
};

if (LogicOpc == Instruction::Or &&
  (MatchOrZExtICmp(Op0, Op1) || MatchOrZExtICmp(Op1, Op0)) &&
  Pred == ICmpInst::ICMP_SGT) {
  Value *Cmp =
      Builder.CreateICmpNE(A, Constant::getNullValue(A->getType()));
  return new ZExtInst(Cmp, A->getType());
}

在这里我们定义了一个lambda：MatchOrZExtICmp，用于匹配左移与Zext运算，而Op0,Op1则是在or运算符的两个操作数。

match、m_ZExt等有关的函数、类则是LLVM的PatternMatching库。 PatternMatching库提供一系列函数和模板类，用于匹配特定LLVM-IR的Pattern，类似m_SpecificInt则是匹配一个特定整数或者有相同整数元素的向量 (Splat Vector)。

其中要注意的是getScalarSizeInBits函数在整数类型中返回整数的大小，而在vector中返回元素的大小。

最后经过了实现，我们需要再次更新我们的testcases以确认优化的效果，故要再次运行：

llvm/utils/update_test_checks.py --opt-bin build/bin/opt \
    llvm/test/Transforms/InstCombine/and-or-icmps.ll

这时我们可以发现我们的正例的CHECK发生了变化：

define i32 @icmp_slt_0_or_icmp_sgt_0_i32(i32 %x) {
; CHECK-LABEL: @icmp_slt_0_or_icmp_sgt_0_i32(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i32 [[X:%.*]], 0
; CHECK-NEXT:    [[E:%.*]] = zext i1 [[TMP1]] to i32
; CHECK-NEXT:    ret i32 [[E]]
;
  %A = icmp slt i32 %x, 0
  %B = icmp sgt i32 %x, 0
  %C = zext i1 %A to i32
  %D = zext i1 %B to i32
  %E = or i32 %C, %D
  ret i32 %E
}

且其他的testcases的变化也符合我们的期望，这里我们再commit一次。

这时我们就可以进入patch的提交阶段了。

提交Patch

现在我们已经有了两个commit，可以通过以下指令生成test和impl的patch文件。

git show -U99999 HEAD^ > patch_test
git show -U99999 > patch_transform

而LLVM暂时不接受Github的PR，只允许在Phabricator上提交patch。 故在这里我注册了Phabricator的帐号，并通过Create Diff分别上传我的两个patch。

Patch的标题内容等格式可以博客开头的参考文章，机翻并改造如下： > 选择一个有意义的patch标题和摘要。对于我们的运行示例，第一个patch可能是这样的： > > title：[InstCombine] Add tests for (A > 0) | (A < 0) -> zext (A != 0) fold (NFC) > > summary：Tests for an upcoming (A > 0) | (A < 0) -> zext (A != 0) fold.。 > > reviewer：（见下文） > > 第二个patch可能是这样的： > > title：[InstCombine] Transform (A > 0) | (A < 0) -> zext (A != 0) fold > > summary：[InstCombine] Transform (A > 0) | (A < 0) -> zext (A != 0) fold > > This extends foldCastedBitwiseLogic to handle the similar cases. > > ......你的分析...... > > It's proved by alive-tv:link > > Depends on DNNNNNN（在此处放置第一个patch的ID）。 > reviewer：（见下文） > > 这里有几个值得强调的地方： > > 标题开头应该有一个 [Category] 标签。通常，您可以只使用您要修改的文件的名称。例如，对 InstCombine 的更改通常带有[InstCombine]标记。 > 非功能性更改（如测试添加）的patch通常在标题中的某个地方带有 NFC 标记。 > 如果您有任何 alive2 证明，请在patch摘要中包含它们。 > 您可以使用“Depends on DNNNNNN”来创建堆叠的patch。也可以事后添加“子修订版”来实现此目的。

---

现在我们还差Reviewers，在LLVM中，patch提交者负责选择适当的审阅者。虽然有人可能会根据patch标题（这就是分类标记如此重要的原因）来找到合适的审阅者，但您最好一开始就指定适当的审阅者。

虽然LLVM有一个CODE_OWNERS.txt文件，用于指定不同领域的代码所有者，但不幸的是， 这个文件往往过时且不完整。找到审阅者的更好方法是查看您要修改的文件的Git历史记录，并添加一些最近commit或最近review diff revision的人员。

对于InstCombine，主要的reviewer是spatel，但您也可以根据历史记录找到其他几个候选人（例如nikic，goldstein.w.n）。

提交了patch后，就该等待review了。对于这样简单的更改，通常会有人很快处理。如果您在一周内没有得到回复，请发送“ping”评论，并每周发送一次。对于InstCombine来说等待数周才进行审阅是相当不寻常的，但如果您提交的更改是很长时间没有人真正工作的领域，则可能会发生。只需要不断“ping”。

最后，一旦patch获得批准，审阅者通常会认为您已经拥有提交访问权限，并允许您自己提交更改。如果不是这种情况，则应该跟进一条评论， 例如“I don't have commit access, can you please land this for me? Please use 'Your Name your@email' for the commit”。 最后一点很重要，因为Phabricator会丢失patch的作者信息，提交者必须将其添加回来。

如果您计划对LLVM进行任何形式的常规贡献，建议请求提交访问权限。这方面的门槛非常低，因此可以尽早请求。如果不必创建堆叠的审查，则测试的预提交工作流程要方便得多。

最后，有关CI的一些话：Phabricator上的patch会通过“pre-merge”测试运行。特别是如果您没有在本地运行完整的测试套件，则这些结果可能会有所帮助。不幸的是，这些测试运行有些不稳定，因此如果您看到与您的patch没有明显关系的失败，则通常可以忽略它们。

一旦patch被提交，它将在更广泛的“buildbots”范围内运行，这些机器人在许多不同的架构和许多不同的配置上运行测试。 这些也相当不稳定，因此同样适用：如果您收到buildbots故障电子邮件，看起来与您的patch无关，则不必担心。如果最终发现是您的责任，buildbots所有者会让您知道。

总结

翻译参考文章的总结

LLVM的贡献过程具有某些不同于其他开源项目的不寻常方面。其中一部分是使用Phabricator而不是GitHub进行审查，但大多数差异都集中在强调正确性方面，从正确性证明开始，到测试的预提交工作流程，以及最终往往是测试和代码更改之间非常大的比率。

我希望本文对于想要进入LLVM开发的人有所帮助，但我想重申，第一次做不需要完全做得“正确”，如果遇到问题，人们会很乐意提供帮助。Discourse的初学者类别以及Discord聊天是提问的好地方。

自己的总结

第一次为大型开源项目Contribute是一次特别的经历，在不断与reviewer的沟通中，我也对LLVM的体系有了更深刻的了解，希望读者在看了本篇博客后也可以更活跃地参与开源活动。