GCC 中的 Switch 语句降级（lowering）

# Xoranth 的随想 来源：https://xoranth.net/gcc-switch/ ## GCC 中的 switch 语句降低 --- **2024-01-14** ### 引言 我们在上一篇文章（https://xoranth.net/verb-parse/）中已经看到，switch 语句比表面上看起来复杂得多。编译器可以将其编译为决策树（即使它可能不应该这么做）。这已经是它能做的全部了吗？ *本文将重点讨论 `gcc`。除了位集（bitset）降低外，所有优化同样适用于 clang。除非另有说明，否则我将使用 `-O3` 优化级别。* *我对 `gcc` 生成的代码做了轻微编辑，并为简洁起见删除了某些断言。* ### 示例 让我们从一个简单的例子开始。一个函数接受两个整数 `x` 和 `val`。根据 `x` 的值，调用相应的函数（`f0`、`f1` 等），并将 `val` 作为参数，然后返回结果。如果我们手动实现这个功能，会使用一个函数指针数组，以输入作为数组索引。 ```c int f0(int val); int f1(int val); int f2(int val); int f3(int val); int f4(int val); int compact(int x, int val) { switch (x) { case 0: return f0(val); case 1: return f1(val); case 2: return f2(val); case 3: return f3(val); case 4: return f4(val); default: return 0; } return 0; } ``` ``` compact: mov eax, edi mov edi, esi cmp eax, 4 ja .L2 jmp [QWORD PTR .L4[0+rax*8]] .L4: .quad .L8 .quad .L7 .quad .L6 .quad .L5 .quad .L3 .L5: jmp f3 .L3: jmp f4 .L8: jmp f0 .L7: jmp f1 .L6: jmp f2 .L2: xor eax, eax ret ``` 编译器同意这种做法，将 switch 语句转换为跳转表（jump table）。此外，它还能够识别值偏移一个常数的情况： ```c int f0(int val); int f1(int val); int f2(int val); int f3(int val); int f4(int val); int compact(int x, int val) { switch (x) { case 97: return f0(val); case 98: return f1(val); case 99: return f2(val); case 100: return f3(val); case 101: return f4(val); default: return 0; } return 0; } ``` ``` compact: lea eax, [rdi-97] cmp eax, 4 ja .L2 mov edi, esi jmp [QWORD PTR .L4[0+rax*8]] .L4: .quad .L8 .quad .L7 .quad .L6 .quad .L5 .quad .L3 .L5: jmp f3 .L3: jmp f4 .L8: jmp f0 .L7: jmp f1 .L6: jmp f2 .L2: xor eax, eax ret ``` 我们的直觉表明，值越稀疏，跳转表转换的优势就越小。通过实验，我们发现 `gcc` 的阈值大约是每个跳转表条目对应八个 case 标签。换句话说，以下函数会编译为跳转表： ```c int f0(int val); int f1(int val); int f2(int val); int f3(int val); int f4(int val); int compact_7(int x, int val) { switch (x) { case 0: return f0(val); case 7: return f1(val); case 14: return f2(val); case 21: return f3(val); case 34: return f4(val); default: return 0; } return 0; } ``` ``` compact_7: mov eax, edi mov edi, esi cmp eax, 34 ja .L2 jmp [QWORD PTR .L4[0+rax*8]] .L4: .quad .L8 .quad .L2 ; ... .quad .L2 .quad .L7 .quad .L2 ; ... .quad .L2 .quad .L6 .quad .L2 ; ... .quad .L2 .quad .L5 .quad .L2 ; ... .quad .L2 .quad .L3 .L2: xor eax, eax ret .L8: jmp f0 .L7: jmp f1 .L6: jmp f2 .L5: jmp f3 .L3: jmp f4 ``` 但以下这个函数则被展开为比较树： ```c int f0(int val); int f1(int val); int f2(int val); int f3(int val); int f4(int val); int sparse_8(int x, int val) { switch (x) { case 0: return f0(val); case 8: return f1(val); case 16: return f2(val); case 24: return f3(val); case 40: return f4(val); default: return 0; } return 0; } ``` ``` sparse_8: mov eax, edi mov edi, esi cmp eax, 16 je .L2 jle .L10 cmp eax, 24 je .L7 cmp eax, 40 jne .L1 jmp f4 .L10: test eax, eax je .L4 cmp eax, 8 jne .L1 jmp f1 .L1: xor eax, eax ret .L4: jmp f0 .L7: jmp f3 .L2: jmp f2 ``` 以下是为便于理解而绘制的比较树： ``` ret 0 ret 0 call f0 call f0 call f1 call f1 call f2 call f2 cmp eax, 24 cmp eax, 24 call f3 call f3 call f4 call f4 cmp eax, 16 cmp eax, 16 cmp eax, 16 -> call f2 je test eax, eax test eax, eax test eax, eax -> cmp eax, 16 jle test eax, eax -> cmp eax, 24 cmp eax, 16 -> test eax, eax -> call f0 je cmp eax, 8 cmp eax, 8 cmp eax, 8 test eax, eax -> cmp eax, 8 test eax, eax -> cmp eax, 8 cmp eax, 24 -> call f3 je cmp eax, 40 cmp eax, 40 cmp eax, 24 -> cmp eax, 40 cmp eax, 40 -> ret 0 cmp eax, 40 -> call f4 jne cmp eax, 8 -> ret 0 cmp eax, 8 -> call f1 jne ``` 几点观察： 1. 到目前为止，我们只尝试了等间距的值。编译器能否识别出仅对所有 case 的子集而言有利的转换？ 2. 到目前为止，每个 `case` 都导向不同的结果。如果有不同的 case 产生相同的结果呢？ 3. `sparse_8` 中的 switch 本可以通过在跳转前将 `x` 除以八来简化。有趣的是，`gcc` *没有*发现这种简化。让我们深入探讨第 1 点和第 2 点。 #### 离群值 修改第一个示例，加入一个离群值，可以看到编译器能够识别出 case 的密集子集。 ```c int f0(int val); int f1(int val); int f2(int val); int f3(int val); int f4(int val); int f5(int val); int outlier(int x, int val) { switch (x) { case 1: return f0(val); case 2: return f1(val); case 3: return f2(val); case 4: return f3(val); case 5: return f4(val); case 100: return f5(val); default: return 0; } return 0; } ``` ``` outlier: mov eax, edi mov edi, esi cmp eax, 5 jg .L2 test eax, eax jle .L1 cmp eax, 5 ja .L4 jmp [QWORD PTR .L6[0+rax*8]] .L6: .quad .L4 .quad .L4 .quad .L9 .quad .L8 .quad .L7 .quad .L5 .L2: cmp eax, 100 jne .L1 jmp f5 .L7: jmp f3 .L5: jmp f4 .L9: jmp f1 .L8: jmp f2 .L4: jmp f0 .L1: xor eax, eax ret ``` 编译器为 case 100 生成了一个分支，而为 case 1 到 5 生成了跳转表。 #### 连续值 在到目前为止的示例中，每个 case 语句都导向不同的代码块。让我们测试当多个 `case` 标签调用同一个函数时会发生什么。 ```c int f1(int val); int f2(int val); int f3(int val); int f4(int val); int f5(int val); int blocks_2(int x, int val) { switch (x) { case 0: case 1: case 2: case 3: return f1(val); case 21: ... case 24: return f2(val); case 42: ... case 45: return f3(val); case 63: ... case 66: return f4(val); case 84: ... case 87: return f5(val); default: return 0; } return 0; } ``` ``` blocks_2: mov eax, edi mov edi, esi cmp eax, 45 jg .L2 cmp eax, 41 jg .L3 cmp eax, 3 jg .L4 test eax, eax js .L1 jmp f1 .L2: cmp eax, 66 jg .L8 cmp eax, 62 jle .L1 jmp f4 .L4: sub eax, 21 cmp eax, 3 ja .L1 jmp f2 .L8: sub eax, 84 cmp eax, 3 ja .L1 jmp f5 .L3: jmp f3 .L1: xor eax, eax ret ``` 我们有 20 个 case 标签，值在 0 到 87 之间。编译器本可以将此 `switch` 降低为一个包含 88 个条目的跳转表。我们对启发式规则的假设是：当跳转表的大小小于 `8 * num_case_labels` 时，转换是有利的。由于 `88 < 20 * 8`，这种情况下转换应该是有利的，然而 `gcc` 选择将 switch 降低为一系列比较。为了更好地理解原因，让我们查看一个特定的 case 标签块。 ```c int blocks_2(int x, int val) { switch (x) { case 42: case 43: case 44: case 45: return f3(val); } return 0; } ``` ``` blocks_2: mov eax, edi ; 将 `val` 移动到 $eax mov edi, esi cmp eax, 45 ; 如果 val <= 45，不要跳转 jg .L2 cmp eax, 41 ; 如果 val >= 42，跳转到 L3 jg .L3 ; ... .L2: ; ... .L3: ; 只有在 42 <= val <= 45 时才会到达 L3 jmp f3 ; 调用 f3(val) ; ... ``` 编译器意识到这些 case 是连续的，可以用两次比较代替四次来实现。如果跳转表启发式规则的输入是*比较次数*而不是*case 标签数量*，那么结果就说得通了：我们总共有 10 次比较。由于 `10 * 8 < 88`，我们修正后的启发式规则表明跳转表转换是不利的。 #### 非连续值 让我们尝试一个非连续的 case。 ```c int f1(int val); int bittest(int x, int val) { switch (x) { case '0': case '2': case '4': case '5': case '7': case '9': case 'A': case 'C': case 'E': return f1(x); default: return 0; } return 0; } ``` ``` bittest: lea eax, [rdi-48] cmp eax, 21 ja .L1 mov edx, 2753205 ; ??? bt rdx, rax jc .L7 .L1: xor eax, eax ret .L7: jmp f1 ``` 编译器生成了非常不直观的机器代码。为什么没有 `cmp` 也没有跳转表？常数 `2753205` 是从哪里来的？指令 `bt` 给了我们一个线索。根据 Intel 文档（https://www.felixcloutier.com/x86/bt），`bt`： > 选择位字符串中（由第一个操作数指定，称为位基址）在位偏移（由第二个操作数指定）所指定位置的位，并将该位的值存储在 CF 标志中。 如果我们检查 `2753205` 的二进制表示，会发现它实际上是一个位集（bitset）。设置为 1 的位对应于 case 标签的 ASCII 值，每个值都减去了 48。 ``` chars: 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E Cases ... edx: 1 0 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 mov edx, 2753205 edx: p0 -- chars: p0 edx: p2 -- chars: p2 edx: p4 -- chars: p4 edx: p5 -- chars: p5 edx: p7 -- chars: p7 edx: p9 -- chars: p9 edx: p17 -- chars: p17 edx: p19 -- chars: p19 edx: p21 -- chars: p21 ``` ### 实现 我们已经遇到了 `gcc` 采用的几种不同的降低策略。为了更深入地了解，我们可以深入研究编译器的源代码。负责降低 `switch` 语句的编译器遍（pass）是（恰如其名的）`pass_lower_switch`，它进而调用 `analyze_switch_statement`。由于 `gcc` 的源码可能难以跟踪，我将在下面提供一个带注释的逐步版本。之后，我将逐节解释其功能。 ```c bool switch_decision_tree::analyze_switch_statement () { unsigned l = gimple_switch_num_labels (m_switch); auto_vec clusters; ... compute_cases_per_edge (); ``` 一些前导代码。`m_switch` 指向一个 gimple 对象。Gimple 是 `gcc` 使用的中间表示。通过它，我们提取 case 的总数和每条出边的各个 case 计数。我们还分配了一个向量，用来记录为每个 case 标签选择的降低策略。 ```c for (unsigned i = 1; i < l; i++) { tree elt = gimple_switch_label (m_switch, i); // ... tree low = CASE_LOW (elt); tree high = CASE_HIGH (elt); profile_probability p = case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)); clusters.quick_push (new simple_cluster (low, high, elt, case_edge->dest, p)); // ... } ``` 更多的初始化代码。我们注意到 gimple 中每个标签都有高值和低值的概念。也就是说，连续的 `case` 标签在这个阶段已经合并在一起了。对于每个 case 标签，我们分配一个 `simple_cluster`。这个簇充当记录，捕获与该标签关联的值范围、相关的输出边，以及该簇被选中的概率。该概率来自配置文件引导优化（profile-guided optimization）。默认情况下，在 case 标签之间是均匀分布的。 ```c // ... vec output = bit_test_cluster::find_bit_tests (clusters); ``` 我们对已创建的簇向量进行转换。名称 `bit_test_cluster` 暗示了我们之前看到的位集降低策略。 ```c /* Find jump table clusters. */ vec output2; auto_vec tmp; // ... for (unsigned i = 0; i < output.length (); i++) { cluster *c = output[i]; if (c->get_type () != SIMPLE_CASE) { if (!tmp.is_empty ()) { tmp.truncate (0); } output2.safe_push (c); } else tmp.safe_push (c); } ``` 这一部分为转换后的 case 分配了一个向量和一个临时向量。在位集转换过程中未被修改的任何 case 都被收集在这个临时向量中。当我们遇到一个优化后的簇时，这些 case 会被处理并清空。本质上，在这一部分我们寻找无法转换为位集簇的 case 标签序列。 ```c vec n = jump_table_cluster::find_jump_tables (tmp); output2.safe_splice (n); n.release (); ``` 我们尝试将这些连续的标签转换为跳转表，并将结果添加到输出中。 ```c /* We still can have a temporary vector to test. */ if (!tmp.is_empty ()) { vec n = jump_table_cluster::find_jump_tables (tmp); output2.safe_splice (n); n.release (); } ``` 这是上述循环的收尾代码。 ```c // ... bool expanded = try_switch_expansion (output2); release_clusters(output2); return expanded; } ``` 剩余的内容经过另一遍处理，将 switch 语句转换为决策树。位集和跳转表是决策树的叶子节点。 #### 位集 让我们进一步深入研究 `bit_test_cluster::find_bit_tests`。代码的高层结构如下。最初，我们旨在找到将所有簇打包为位集的最优方法。在此上下文中，最优性指的是使用最少数量的位集。我们通过动态规划来实现。随后，我们遍历这些位集并应用一个收益性启发式规则。如果位集满足此规则，我们就生成一个 `bit_test_cluster`；否则，保留原始的 `simple_cluster`。 ```c vec bit_test_cluster::find_bit_tests (vec &clusters) { ... unsigned l = clusters.length (); auto_vec min; ... min.quick_push (min_cluster_item (0, 0, 0)); for (unsigned i = 1; i <= l; i++) { min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX)); for (unsigned j = 0; j < i; j++) { if (min[j].m_count + 1 < min[i].m_count && can_be_handled (clusters, j, i - 1)) min[i] = min_cluster_item (min[j].m_count + 1, j, INT_MAX); } gcc_checking_assert (min[i].m_count != INT_MAX); } ``` 对于动态规划，我们使用一个 `min_cluster_item` 结构体的向量。每个 `min_cluster_item` 有三个组成部分： - 第一个记录表示前 *i* 个 case 标签需要多少个位集，其中 *i* 是向量中的索引。 - 第二个记录最后一个位集的**起始**位置。 - 第三个未使用。 动态规划的思路如下。我们希望找到表示前 *i* 个 case 标签所需的最少位集数。基本情况很简单：单个 case 标签可以用单个位集表示。假设我们已经为所有 j 找到了前 *j* 个 case 标签的最优位集数。我们定义 min[i] 为前 `i` 个元素的最优划分数量。这意味着我们已经计算了 min[j]，现在需要寻找 min[i]。如果 case 标签的范围可以表示为位集簇，则必须满足 min[i] = min[j] + 1（其中 j 是最后一个位集的起始位置）。反过来，假设我们有了前 *i* 个标签的最优分配。如果最后一个位集从标签 j 开始，那么将该分配限制在前 j 个标签上也应是最优的。如果不是这样，我们也可以改进前 j 个标签上的分配。因此，必须满足：min[j] + 1 = min[i]。这些条件正是上面代码中 `if` 语句所检查的内容。 `can_be_handled` 函数控制一段 `case` 标签范围是否可以转换为位集测试。它测试两个标准： - 所有 case 标签的*合并*范围必须小于寄存器的宽度。在现代系统上，合并范围应小于 64。 - case 标签最多只能有 3 个*唯一*的出边。如果有多于一个出边，我们会发出一系列级联的位测试。 ```c vec output; // ... /* Find and build the clusters. */ for (unsigned end = l;;) { int start = min[end].m_start; if (is_beneficial (clusters, start, end - 1)) { bool entire = start == 0 && end == clusters.length (); output.safe_push (new bit_test_cluster (clusters, start, end - 1, entire)); } else for (int i = end - 1; i >= start; i--) output.safe_push (clusters[i]); end = start; if (start <= 0) break; } output.reverse (); return output; } ``` 现在我们只转换满足 `is_beneficial` 测试的位集。在代码中，`count` 表示簇处理的 case 标签数量，而 `uniq` 表示不同出边的数量。 ```c bool bit_test_cluster::is_beneficial (unsigned count, unsigned uniq) { return (((uniq == 1 && count >= 3) || (uniq == 2 && count >= 5) || (uniq == 3 && count >= 6))); } ``` #### 跳转表 跳转表转换的逻辑与位测试转换类似。它利用动态规划来识别可以有利地转换为跳转表的"簇"。让我们深入研究代码。 ```c vec jump_table_clu