GSoC 2024: 3-way 比较内联函数

大家好！我是 Volodymyr，在这篇文章中，我想谈谈我在过去几个月里作为 Google Summer of Code 2024 项目的一部分所做的工作。这个项目的目的是向 LLVM IR 引入 3-way 比较内联函数，并为它们添加相当程度的优化。

背景

三路比较是许多高级语言中存在的运算，例如 C++ 及其 spaceship 运算符，或 Rust 和 Ord 特性。它对两个定义了比较运算的值进行操作，如果第一个操作数小于第二个，则返回 -1；如果它们相等，则返回 0；否则返回 1。目前，使用 LLVM 的编译器使用不同的指令序列来表达此操作，这些指令序列被单独优化和降低，而不是作为单个操作。因此，为此操作添加一个内联函数将有助于我们在某些目标上生成更好的机器代码，以及可能优化以前未优化的中间端模式。

做了什么

在项目过程中，我在 LLVM IR 中添加了两个新的内联函数：用于无符号 3 路比较的 llvm.ucmp 和用于有符号比较的 llvm.scmp。它们都接收两个参数，这些参数必须是整数或整数向量，并返回一个具有相同元素数量的整数或整数向量。参数和结果不需要具有相同的类型。

在中间端，以下传递获得了对这些内联函数的一些支持

InstSimplify (#1, #2)
InstCombine (#1, #2, #3, #4, #5)
CorrelatedValuePropagation
ConstraintElimination

我还添加了 3 路比较可以表达的惯用方式的折叠，以调用相应的内联函数。

在后端，有两种不同的方法可以扩展内联函数：作为嵌套选择（即 (x < y) ? -1 : (x > y ? 1 : 0)）或作为零扩展比较的减法（zext(x > y) - zext(x < y)）。第二个选项是默认选项，但目标可以通过 TLI hook 选择使用第一个选项。

结果

我认为总体而言，该项目取得了成功，对 LLVM 进行了积极的小幅改变。为了证明它在一个小型测试用例中的影响，以下使用 spaceship 运算符的 C++ 函数被编译了两次，第一次使用 Clang 18.1，第二次使用从 LLVM 存储库的主分支构建的 Clang。

#include <compare>

std::strong_ordering cmp(unsigned int a, unsigned int b)
{
    return a <=> b;
}

使用 Clang 18.1

; ====== LLVM IR ======
define i8 @cmp(i32 %a, i32 %b) {
entry:
  %cmp.lt = icmp ult i32 %a, %b
  %sel.lt = select i1 %cmp.lt, i8 -1, i8 1
  %cmp.eq = icmp eq i32 %a, %b
  %sel.eq = select i1 %cmp.eq, i8 0, i8 %sel.lt
  ret i8 %sel.eq
}

; ====== x86_64 assembly ======
cmp:
  xor     ecx, ecx
  cmp     edi, esi
  mov     eax, 0
  sbb     eax, eax
  or      al, 1
  cmp     edi, esi
  movzx   eax, al
  cmove   eax, ecx
  ret

使用新构建的 Clang

; ====== LLVM IR ======
define i8 @cmp(i32 %a, i32 %b) {
entry:
  %sel.eq = tail call i8 @llvm.ucmp.i8.i32(i32 %a, i32 %b)
  ret i8 %sel.eq
}

; ====== x86_64 assembly ======
cmp:
  cmp     edi, esi
  seta    al
  sbb     al, 0
  ret

如您所见，生成的代码中的指令数量已大大减少（从 8 个减少到 3 个，不包括 ret）。尽管这并不多，只是一个小的合成测试，但如果像这样的代码出现在某个热路径中，它仍然会产生明显的影响。

这些更改对真实代码的影响更难量化。查看 llvm-opt-benchmark，有很多地方使用了内联函数，这表明肯定有一些改进，尽管它不太可能在除极少数情况外的所有情况下都显着。

未来工作

在中间端仍然有许多优化机会，其中一些在撰写本文时已经为人所知并正在进行中，而另一些尚未被发现。我还想允许指针和指针向量成为内联函数的有效操作数，尽管这将是一个很小的改动。在后端，我还想研究在 GlobalISel 中更好地处理内联函数，这是我当时没有时间做的事情，LLVM 社区的其他成员帮助我完成了这项工作。

致谢

如果没有两位出色的导师 Nikita Popov 和 Dhruv Chawla 以及整个 LLVM 社区的帮助，这一切都将不可能实现。感谢您在这次旅程中帮助我，我期待着将来与您合作。