GCC 中的开关降低

GCC 中的 Switch 降低 2024-01-14 简介 我们在之前的文章中已经看到 switch 语句比看起来更复杂。编译器能够将它们实现为决策树（尽管也许不应该）。这就是它能做的一切吗？在这篇文章中，我将重点关注 gcc 。除了位集降低之外的所有优化都会转化为 clang。除非另有说明，我将使用 -O3 优化标志。为了简洁起见，我还稍微编辑了 gcc 代码并删除了某些断言。示例 让我们从一个简单的示例开始。采用两个整数 x 和 val 的函数。根据 x 的值，它以 val 作为参数调用相应的函数（ f0 、 f1 等）并返回结果。如果我们手动实现这一点，我们将使用函数指针数组，其中输入用作数组的索引。 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 ) ;情况1：返回f1(val)；情况2：返回f2(val)；情况3：返回f3(val)；情况 4：返回 f4(val)；默认：返回0；返回0； } 紧凑: 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 语句转换为跳转表。此外，它能够识别值何时被常量偏移： 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 ) { 案例 97 : return f0 ( val ) ;情况98：返回f1(val)；情况99：返回f2(val)；情况100：返回f3(val)；情况101：返回f4(val)；默认：返回0；返回0； } 紧凑: 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 标签 8 个跳转表条目。换句话说，以下函数编译为跳转表： 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 ) ;情况7：返回f1(val)；情况14：返回f2(val)；情况21：返回f3(val)；情况34：返回f4(val)；默认：返回0；返回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 但是另一个函数被扩展为比较树： int f0 ( int val ) ; int f1 ( int val ) ; int f2 ( int val ) ; int f3 ( int val ) ; int f4 ( int val ) ; int稀疏_8（int x，int val）{switch（x）{情况0：返回f0（val）；情况8：返回f1(val)；情况16：返回f2(val)；情况24：返回f3(val)；情况40：返回f4(val)；默认：返回0；返回0； }稀疏_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：测试 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 为了清晰起见，下面是可视化的比较树： G 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->调用 f2 je test eax, eax 测试 eax, eax cmp eax, 16->测试 eax, eax jle cmp eax, 16->cmp eax, 24 测试 eax, eax->调用 f0 je cmp eax, 8 cmp eax, 8 测试 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 jne cmp eax, 40->call f4 cmp eax, 8->ret 0 jne cmp eax, 8->call f1 一些观察结果：到目前为止，我们只尝试了等间隔的值。编译器能否识别在所有情况的子集上有利可图的转换？到目前为止，每个案例都导致了不同的