LLVM 对 C++ switch 语句的实现¶

标题：C++ switch statements under the hood in LLVM

日期：2024/11/28

作者：Hans Wennborg

链接：https://www.youtube.com/watch?v=nfy51jenN3M

注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。

备注：常规优化大家都有差不多的想法，不过聚类还是有点意思。

好的，您可以看到幻灯片。这是最令人兴奋的部分，将计算机连接到系统。那么，大家好。感谢邀请我。我叫 Hans，我在 Google 从事编译器相关工作，特别是维护我们用于构建 Chromium 的工具链。我也曾担任过一段时间的 LLVM 发布经理，并且在 LLVM 的 Windows 支持、ClangCL 等方面做了大量工作。自从我搬到斯德哥尔摩以来，我想我来这里参加活动已经快两年了。我想我是通过 Bjorn 的 Twitter 发现这里的，所以这很有效。与在座的许多人不同，我对最新的 C++26 特性并不是特别熟悉，所以我来这里是为了学习和享受乐趣。但我确实了解的一个特性是 switch 语句，因为它们很古老，就像我一样，而且我在 LLVM 中对它们做了一些工作。所以，这是一场关于 C++ 底层实现的演讲。不是关于 C++ 的最新特性，而是关于底层实现。所以，请告诉我您是否希望看到更多这类演讲。

那么，我们在这里尝试解析演讲的标题：C++ switch 语句在 LLVM 中的底层实现。内容很多。首先，这个 LLVM 到底是什么？这里有多少人听说过 LLVM？很多手举起来了。非常非常酷。我想是对的人了。所以，这个名字曾经代表“低级虚拟机”（low-level virtual machine），因为在核心层面，它过去是（或者说现在仍然是）一个类似汇编的语言，即中间表示（intermediate representation），您可以用它来编写程序。然后您可以优化这些程序、进行分析并对其进行处理。接着您可以运行它们。LLVM 有一个 JIT（即时编译器）和一个解释器，或者您可以输出机器码。但如今，这个名字就叫 LLVM。这些字母不再代表任何含义。它实际上是一个包含大量编译器相关内容的伞形项目。因此，它包含用于优化、代码生成、读写各种目标文件和可执行文件的库。它还包含使用这些库的工具，比如编译器和链接器。有一个调试器、各种运行时库等等。Clang 是 LLVM 的 C++ 编译器，或者更确切地说是 C、C++、Objective-C 和 Objective-C++ 的编译器。但还有许多其他编译器也使用 LLVM 作为目标。我想如今 Intel C++ 编译器也使用 LLVM，其他语言也使用它。比如 Rust、Fortran、Swift、Julia 等等。我想也有使用 LLVM 的 Java 编译器。

有时我们会谈论编译的沙漏模型（hourglass model）。LLVM 位于中间，处于沙漏的狭窄部分。在左侧，它可以接收来自多种不同编程语言的输入，这些语言的编译器会生成 LLVM 的中间表示（IR）。在右侧是 LLVM 可以定位的所有目标，即为其生成代码的目标，比如典型的 CPU 架构，如 Intel 的 x86、ARM、PowerPC、RISC-V 等等。还有一些更奇特的东西，比如 GPU、WebAssembly 等等。还包括不同的操作系统及其文件格式、应用二进制接口（ABI）等等。这种模型的妙处在于中间只有一个 LLVM。因此，每个编译器，如 Clang 或 Rust，只需以 LLVM 为目标，而不需要自己实现编写 x86 机器码等所有细节。它们也不需要实现 LLVM 能提供的所有花哨的优化。所以，我不知道我是否适合做这些工作。这就是我在那里画沙漏图的原因。

这是一个非常理想化的图像，因为在实践中，编译器确实需要了解一些关于目标的信息，例如 Clang 需要知道某些 C++ 特性在 ARM 与 Intel 上，或者 Mac 与 Windows 上的工作方式有何不同。编译器通常也会自己进行一些优化，这些优化与源语言关系更密切，我想 Rust 和 Swift 经常这样做，Clang 可能做得少一些。这种模型也有一些缺点，比如因为 LLVM 能做所有这些事情，它是一个相当庞大的项目，是一个很大的依赖项。所以，如果您只是想尽快生成 x86 代码，您可能可以自己完成，或者找到一个更小的库。但如果您还需要支持所有其他目标并执行所有花哨的优化，那么使用 LLVM 可能是一个不错的选择。这就是 LLVM 的部分。现在来看 switch 的部分，这是主要部分。希望你们都了解这个，C 或 C++ 中的 switch 语句已经存在很长时间了。我想它从一开始就在 C 中，我肯定它从一开始就在 C++ 中。您可以将其视为一个花哨的 if 语句，其中代码（计算机）会根据输入跳转到不同的 case 标签。所以这是 switch 表达式上的 LLVM。这是这个例子中的 x。在右侧，我们可以看到 LLVM 如何在内部表示它，它实际上有一个专门的指令，叫做 switch。我们可以看到它以 x 作为输入。然后它根据 x 的值跳转到不同的标签。这里的标签 7 是特殊的，那是默认标签（default label）。所以如果不匹配其他任何标签，它将跳转到默认标签。在这个 C++ 例子中，我们没有显式的 default 标签。但在 C++ 中，在 switch 之后存在一个隐式的默认标签。如果 case 不匹配，它将跳转到下一条语句。

我试图找一些关于 C++ switch 的新东西，但没有什么太令人兴奋的，不过有一个常见的扩展，即支持 case 范围（case ranges），因为这是人们经常使用 switch 的原因之一。例如，GCC 和 Clang 都允许这样做，但这是一种扩展。这不是标准。但它似乎正在 C26 的标准轨道上，如果它进入标准，也许最终也会进入 C++。我们会看到的。在右侧，我们可以看到它的 LLVM 中间表示。您可以看到它不是很优雅。它只是将范围展开了。这并没有太大关系。我想它在内存上效率低下，看起来也不美观，但最好能对此做一些改进。所以这可能是一个机会。但 LLVM 的 switch 指令不仅用于实际的 C 或 C++ switch。它也可以用于其他语言结构。所以，请 C++ 纯粹主义者原谅，这里有一些 Rust 代码，它是一个 match 表达式。这些有时也会变成 LLVM 的 switch 指令。这意味着当我们在 LLVM 内部查看 switch 是如何处理时，它实际上适用于远不止常规 switch 的范围。因此，妥善处理这些的影响范围更广。这里是另一个语言结构，它根本不是 switch。它只是一个普通的 if 语句。它是一个 if-else 链。但 LLVM 会发现，在内部将其视为 switch 会更高效。因此，如果您开启优化，它会为您这样做。这回到了本次演讲预告中的那个问题或引子：switch 是否比 if-else 链更高效？嗯，理想情况下，LLVM 会找出最佳做法。因此，您可以选择以最能自然描述所需功能的方式编写代码。所以可以说它们实际上是等价的。当然，LLVM 并不完美。所以这并不总是有效。因此，如果您真的关心性能，您可能应该检查输出。但无论如何，这就是思路。同样，关键在于这不仅仅是关于字面意义上的 switch，而是关于更大范围的语言输入。现在我们知道了什么是 switch。现在让我们讨论不同类型的 switch。我觉得这是一个非常狭窄的主题，但我们会继续深入探讨。LLVM 确实考虑了两种不同类型的 switch。

左边的那种是我们为不同的 case 实际执行不同操作的情况。右边的那种是我们并不真正执行不同的操作，而只是选择不同的值。所以在这个例子中，我们为变量 y 选择一个值，但这同样适用于我们为多个变量或返回值等选择值的情况。LLVM 会尝试做的是，它会尝试将这些值放入一个查找表（lookup table），并使用 switch 表达式作为索引来访问该表。这很好，因为这意味着除了可能在开始时进行边界检查（bounce check）之外，没有控制流。因此，这比我们必须根据输入跳转到某个地方要高效得多。而且，根据具体情况，边界检查也可以被移除。这里的主要问题是表的大小。它需要覆盖从最小值到最大值的所有情况。如果有空缺（holes），比如在这个例子中，我们没有空缺，但如果我们还有一个 case 5，那么 3 和 4 就会有空缺。如果有默认值，它会用默认值填充这些空缺。如果这些间隙变得非常大，比如如果我们有一个 case 1000000，我们就会有很多空缺，一个非常大的表。这对二进制文件大小来说不太好。

所以，LLVM 的启发式算法（heuristic）大概是，表需要至少有三个条目，并且表需要至少 10% 的密度（dense），意味着表中至少 10% 的槽位被填充。LLVM 在处理表相关的方面有很多小技巧。但一个大技巧是，它会识别输出是否实际上是输入值的线性变换（linear transformation）。如果是这样，它只会发出计算该值的指令。这样就节省了大量空间，不必发出一个大表。比如在这个例子中，输出是 42 + 2 * x。代码将直接计算它，或者如果超出 switch 范围则返回零。

有问题吗？是的。那么，如果你有一个像位标志枚举（bit flag enum）之类的东西，这也会发生吗？因为它总是可预测的。如果是位标志枚举，我不太确定我理解了。0, 1, 2, 8，像 2 的幂次方。是的，我想是的。是的，没错。是的，那应该可行。是的。然后乘法可能也会变成移位（shift）。好的。但那些值选择 switch（value selection switches）确实是一个特例。

那么，对于一般的 switch，我们实际上必须根据不同的 case 跳转并执行不同的操作，该怎么办呢？首先，有些目标非常特殊，对 switch 的处理方式不同，因为它们的能力有限或不同。比如 GPU 很特殊。WebAssembly 很特殊。WebAssembly 有点有趣，因为我们编译成 WebAssembly，然后 WebAssembly 引擎会读取它并像编译成其他东西一样。但对于其他目标，它们将使用以下令人兴奋的技术。因此，在执行任何其他操作之前，我们会将相邻的 case 聚类（cluster）在一起。所以，如果我们有像早期例子中使用扩展那样的 case 范围，其中几个连续的 case 跳转到同一个目标，它们将被放入一个聚类中。在这个例子中，case 0 跳转到 A。case 1, 2, 3 都跳转到 B 标签。所以我们将它们放入一个聚类。case 4, 5 跳转到 C 标签。所以它们成为一个聚类。LLVM 将继续使用这些聚类而不是单个 case 进行处理。所以，对于范围来说，这也意味着效率很高。它并不像最初看起来那么糟糕。

好的。一旦我们将它们组织成聚类，我们有四种策略来为它们生成代码。我们将逐一讨论这些策略。

首先，如果只有很少的聚类，三个或更少，LLVM 将进行直接比较（straight comparisons）。所以对于单个 case，这意味着我们只需检查 switch 表达式是否匹配 case 编号，然后跳转到标签。在这个例子中，我们使用 x86 的 test 指令检查 x 是否等于 0，然后执行条件跳转。如果相等则跳转到 A（je A）。对于有多个 case 的聚类，我们进行范围检查（range check）。这最终变成了减去下界、与调整后的上界比较，然后条件跳转。这比单个 case 只多一条指令。特别是，它仍然只有一个条件跳转，这才是关键所在。我们正试图最小化条件跳转的数量。在这个例子中，它使用 lea 指令进行减法，然后是 cmp，接着是 jb（如果低于则跳转）。

第二种策略是它用位掩码（bit masks）做的一件非常聪明的事情。这张幻灯片看起来非常复杂，我想。所以如果有一堆 case，在这个例子中，我们有九个 case，但只有三个目标。如果目标少于三个，它会尝试使用位掩码来描述这些 case。在这个例子中，对于第一个目标（跳转到 A），我们通过创建一个常量来为 case 0, 3, 6 创建一个位掩码，该常量设置了第 0、3 和 6 位。所以十进制是 73。然后我们生成一条位测试指令（bt）来检查该掩码中的第 x 位是否被设置。如果是，我们就跳转到 A 标签。我们对其他 case 做同样的事情。通过这种技术，我们只需一次位测试就可以检查很多 case，我认为这非常优雅。同样，我们必须首先进行范围检查，以确保它在我们要查看的 case 范围内。当然，范围必须适合机器字（machine word），这种位掩码技术才能工作。

第三种策略是跳转表（jump tables）。也许这是大多数人联想到 switch 的东西。思路是我们只是将每个标签的地址放入一个表中，然后使用 switch 表达式作为索引来访问该表，看看需要跳转到哪里。这个地址可以是绝对地址，也可以是偏移量（offset），即要跳多远。当然，我们同样必须首先进行范围检查。就像我们用于值选择 switch 的查找表一样，这里的主要问题是表的大小。我们需要覆盖从最小 case 到最大 case 以及它们之间的所有内容。如果存在很大的间隙，我们最终会得到一个非常大的表。所以，它再次使用启发式算法来决定何时执行此操作。启发式算法大概是，至少需要四个 case 聚类，并且表密度需要至少达到 10%。表中至少 10% 的位置需要被填充。如果您使用 -Os（优化大小）进行编译，则需要达到 40% 的填充率。

最后，当整个 switch 不满足前三种方法的标准时（这些方法确实有限制，对吧？它们有限制条件），我们将回退到通用解决方案，即构建一个二叉搜索树（binary search tree）。这是一种经典的 switch 降级（switch lowering）策略。您查看中间的 case，看看您的值是更低还是更高，然后像这样在树中向左或向右移动。LLVM 的特殊之处在于它可以将前几种策略与二叉搜索树结合起来。在这个例子中，有些 case 适合位测试，有些适合跳转表，还有些是剩下的，并且数量足够少，适合直接比较。LLVM 在这里使用一种自底向上（bottom up）的策略，它会考虑整个 case 或 case 聚类集合。它尝试找到适合不同策略（特别是查找表）的最佳范围。因此，它尝试找到足够密集以适合跳转表的范围。然后它将在它们周围构建二叉搜索树。对于我们的例子，它看起来会是这样。在树的叶子节点，我们使用之前的降级策略。内部节点（这里是橙色的）是用于遍历树的比较。虽然之前的策略（我们在叶子节点使用的那些）都是常数时间复杂度，O(1)。我们现在对整个 switch 执行 O(log n) 的操作。为了实现 O(log n) 的复杂度，树需要是平衡的（balanced），对吧？这才是关键。所以，通常这意味着我们尝试在每个节点的左右两侧放置数量大致相等的内容。但是，如果我们有配置信息（profile information），我们可以做得更好。我不知道您是否能看到 case 上的绿色数字。那是配置信息，告诉我们它们被使用的频率。然后我们可以根据这些权重进行平衡。在这个例子中，case 70 的权重远高于其他 case。它将被放置在更靠近顶部的位置。这样我们需要更少的比较和分支才能到达它。所以，虽然这棵树看起来有点不平衡，但至少对于这个配置来说，它实际上是最优的。同样，对于直接比较，我们当然会按照 case 的常见程度顺序执行它们。最常见的 case 最先执行。基本上就是这样。

现在，您对 switch 的了解比大多数人都要多了。所以总结一下：LLVM 有一个专门的 switch 构造。它用于 C 和 C++ 的 switch，但也可能用于 if-else 链和其他语言结构。非常强大。用于选择值的 switch 可能会被降级为没有任何控制流（除了范围检查）的表查找或线性变换。否则，switch 被降级为一个由配置权重（profile weight）平衡的二叉搜索树，可能结合直接比较、位测试和跳转表。就是这样。非常感谢。

我看到后排有两个问题。

是的。分支预测器（branch predictors）的变化是否改变了您看待这些实现的方式？什么效率不高？这是个好问题。所以问题是，分支预测器的变化是否影响了我们这样做的方式？实际上并没有。我认为这项技术足够通用，没有，它没有。我的意思是，它可能会改变一些人编写代码的方式，但我想这已经很长时间没有变化了，也没有改变。我真的想不出任何我们想要做的改变，但这是个好问题。

对于表查找（table caps），您获取跳转地址，是否有惩罚？那是一种好方法吗？是的。所以，有些目标可能会稍微调整这些启发式算法，对吧？比如什么时候最有利？比如正确的密度是多少等等。所以这绝对是一个因素。而且，当人们编译时，就像我提到的，如果您优化大小与否，标准是不同的。那些也是人们喜欢调整的旋钮。

是的。下一排。所以您说权重与配置相关联。所以我想这既包括配置引导优化（profile guided optimization, PGO），但我想您也考虑了一些提示，比如内置的 likely 或 unlikely。或者有没有办法表达类似的东西？如果您不能，例如，如果产品没有为 PGO 进行插桩（instrumented），而您仍然想表明这个分支更重要。是的。是的。我不确定。我必须仔细检查当您在 case 上放置 likely 时会发生什么，我怀疑可能会。所以，在内部，这可能看起来一样，具有高计数或频率，但我必须仔细检查。在前面，我想。完全相同的问题。好的。

您知道 switch 的实现与 GCC 的 switch 相比如何？对不起，我应该重复一下问题。这与 GCC 的做法相比如何？所以，我最近没有检查，但我想 GCC 使用相同的技术。我想它为值选择 switch 做查找表。它在 LLVM 之前就这么做了。所以我们不得不实现它。我想它也使用相同的技术：跳转表、位测试，当然还有直接比较。我想主要区别在于，我想它不能像 LLVM 那样组合它们。我想它会查看整个情况，然后决定用跳转表还是二叉搜索树。我想您可以构建基准测试（benchmarks）来证明这很重要，但我想一般来说，可能不是什么大问题。所以，我不会说我们中哪一方的 switch 性能更优越。

是的。那边有问题。所以，如果您有一个架构，其中有不同类型的跳转指令，比如短跳转和长跳转等等，是否有办法将信息反馈到过程中？或者这会改变什么吗？我不认为这会改变任何东西。这更像是一个代码布局（code layout）的问题，对吧？它通常会尝试将代码布局得靠近。然后您可以——如果您在构建一个跳转表，那更像是 256。它不可达（not reachable），但这是一个实际的错误，我们在生成短跳转的编译器中有这个 bug。是的。嗯，我不认为 switch 降级代码会查看这个，对吧？其他代码会关心它。是的。

还有一个，是的。所以，如果您有一个 switch case，在这里您为 case 标签赋值。是的。如果您在每个 case 中使用 return 指令并返回值，会有区别吗？这里没有人。是的。所以问题是，如果您为变量选择值或者只是从 case 中返回值（本质上是选择返回值），是否有区别？不，处理方式相同。是的。优化级别呢？代码是否以无优化（-O0）、一级优化（-O1）或更激进的优化级别编译，是否会影响使用的方法？它是否会影响可调试性（debuggability）？所以，是的，问题是，优化级别是否有影响？我们是否做不同的事情？它是否影响可调试性？所以是的，优化级别很重要。如果您关闭优化，我们将做最简单的事情，我想就是二叉搜索树。对于值选择 switch，我们也会这样做。我们不会识别出它们是值选择 switch。然后，我不认为我们在 -O1, -O2, -O3 上对 switch 做不同的事情。只是优化开启或关闭。如果您优化大小与否会影响启发式算法，比如跳转表需要多密集，例如。所以这是另一个区别。这会影响可调试性吗？嗯，是的，当然。这是一个难题。为优化后的代码表示符号调试信息（symbolic debug information）是很棘手的，对吧？所以，如果您有一个包含所有这些 case 的大 switch，然后 LLVM 识别出它只是一个线性变换。那么，如果您尝试单步执行（single step）这个程序，很多源代码位置（source locations）可能会丢失。但对于其他情况，我认为可调试性应该仍然很好。比如，我们会为二叉搜索树和跳转表维护调试信息。您会跳转到您的 case，并且它会有良好的调试信息。所以我认为对于 switch 来说，情况还不算太糟。

是的。完美哈希（perfect hashing）是否曾经被考虑过作为实现方案？所以问题是，完美哈希是否曾被考虑过作为实现方案？所以这是个好问题。答案是是的，它被考虑过。人们尝试过这样做。我的意思是，基本思路是，如果您不能使用跳转表，因为您的 switch 太稀疏，例如，您可以计算一个完美哈希，将整个内容压缩到一个表中。曾经有一个很大的补丁（patch）。很多年前有人尝试过这样做。这有点棘手，因为，是的，您必须计算完美哈希。您也没有很多周期去计算它，您必须找到完美哈希。这需要一些时间，而时间是昂贵的。然后您必须在运行时计算要使用的哈希值，而您在那里的预算不多。一两条指令还可以。如果超过这个限度就不好了。我想那个补丁也有很多复杂性。代码量很大。它没有通过。但是，是的，这绝对是一种可能性。但目前没有实现。是的。好的。谢谢。谢谢。谢谢。