这几天对汇编有点意思,以前也接触不少,但是没太注意。前几天无意看到switch和if-else区别,就想深入研究下switch如何生成跳转表提高效率的。有误的地方大家提出里,多交流。
34275076@qq.com或者shiyigudong@gmail.com。
背景是在这里看到关于switch-case的一些注意事项,才有了研究的想法。这个站点有不少嵌入式或者实时系统的高质量文章,大家有时间可以多读一读。下面进入正文,有一些内容是上面链接的翻译。
1 小范围紧凑的使用switch-case
紧凑的范围内使用switch-case,编译器可以避免对switch语句中的每个case 值进行比较。在这种情况下,编译器会生成一个跳转表,其中包含要在不同分支上执行的操作的地址。操作执行case的值,将其转换为跳转表的索引。在此实现中,switch语句中花费的时间比等效的if-else-if语句中花费的时间少得多。并且,switch语句中花费的时间与switch语句中case分支的数量无关。
2 case范围比较大且差异较大的情形
如果switch语句的case分支的值存在较大差异,则编译器无法创建跳转表来处理switch语句。在这种情况下,跳转表的大小将非常庞大且有效项非常少。因此,编译器倾向使用逐级比较来实现切换。在这种情况下,为switch语句生成的代码看起来更像一系列if-else-if语句。在这里,执行switch语句所花费的时间随着开关中case分支的数量而增加。如下面的代码:
点击(此处)折叠或打开
-
{
-
case 1:
-
...
-
case 1000:
-
...
-
case 100:
-
...
-
case 500:
-
case 5:
-
default:casedefault();break;
-
}
我的电脑是i7-9750h,系统是ubuntu1604,64位。
对于switch首先有2点需要注意:
一 4个case+default不会生成跳转表,生成的是cmpl和je,和if-else比较类似。
二 5个case+default,生成跳转结构
先看C源码,这是不会生成跳转表的代码:
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include <time.h>
-
-
void case1(void)
-
{
-
printf("case1\n");
-
}
-
-
void case2(void)
-
{
-
printf("case2\n");
-
}
-
-
void case3(void)
-
{
-
printf("case3\n");
-
}
-
-
void case4(void)
-
{
-
printf("case4\n");
-
}
-
-
void case5(void)
-
{
-
printf("case5\n");
-
}
-
-
void casedefault(void)
-
{
-
printf("casedefault\n");
-
}
-
-
-
int main(void)
-
{
-
srand(time(NULL));
-
int branchvare = rand()%10;
-
switch(branchvare)
-
{
-
case 1:case1();break;
-
case 2:case2();break;
-
case 3:case3();break;
-
case 4:case4();break;
-
// case 5:case5();break;
-
default:casedefault();break;
-
}
-
return 0;
-
}
我们看看这段代码的汇编是个什么样子,执行
gcc -S switchcase.c -o switchcase.s
我删除了大部分,下面这部分是关键:
-
movl %eax, -4(%rbp) #eax中存放的是c代码中的 branchvare变量值
-
movl -4(%rbp), %eax
-
cmpl $2, %eax
-
je .L9 #等于2跳转到L9
-
cmpl $2, %eax
-
jg .L10 #大于2跳转到L10,在L10代码处又进行了分支跳转
-
cmpl $1, %eax
-
je .L11 #等于1跳转到L11
-
jmp .L8 #跳转default
-
.L10:
-
cmpl $3, %eax
-
je .L12
-
cmpl $4, %eax
-
je .L13
-
jmp .L8
-
.L11:
-
call case1
-
jmp .L14
-
.L9:
-
call case2
-
jmp .L14
-
.L12:
-
call case3
-
jmp .L14
-
.L13:
-
call case4
-
jmp .L14
-
.L8:
-
call casedefault
-
nop
-
.L14:
-
movl $0, %eax
-
leave
-
.cfi_def_cfa 7, 8
-
ret
-
.cfi_endproc
大家可以明确的看到,被汇编成cmp比较和je跳转。也就是和if-else的逻辑相同。这段不细说了,看下面。
把上面的C代码中的// case 5:case5();break;注释去掉,其它不变。Switch-case部分如下:
-
switch(branchvare)
-
{
-
case 1:case1();break;
-
case 2:case2();break;
-
case 3:case3();break;
-
case 4:case4();break;
-
case 5:case5();break;
-
default:casedefault();break;
-
}
对应的汇编代码,我只截取了一部分:
-
movl %eax, -4(%rbp)
-
cmpl $5, -4(%rbp)
-
ja .L8 #大于5不经过跳转表,直接跳转到L8处,也就是default处理代码
-
movl -4(%rbp), %eax
-
movq .L10(,%rax,8), %rax
-
#%rax寄存器里存放的是c代码里的branchvare,也就是索引值。绿色的%rax存放的是case对应项的地址值,L10可以认为该处是一个数组,这个数组里存放的就是各个case项的地址,每一项占8字节。jmp指令的操作数有 前缀 ' * ' ,表明这是一个间接跳转,操作数指定一个内存位置,大家可以认为%rax前加`*`就当时c语言里的指针。这个jmp就跳转到case对应的代码了。
-
jmp *%rax
-
-
.section .rodata
-
.align 8
-
.align 4
-
.L10:
-
.quad .L8
-
.quad .L9
-
.quad .L11
-
.quad .L12
-
.quad .L13
-
.quad .L14
-
.text
-
.L9:
-
call case1
-
jmp .L15
-
.L11:
-
call case2
-
jmp .L15
-
.L12:
-
call case3
-
jmp .L15
-
.L13:
-
call case4
-
jmp .L15
-
.L14:
-
call case5
-
jmp .L15
-
.L8:
-
call casedefault
-
nop
-
.L15:
-
movl $0, %eax
-
leave
-
.cfi_def_cfa 7, 8
-
ret
-
.cfi_endproc
这部分汇编子关键的就是中间注释那段中文。其它不多说。
下面我们看看反汇编的情况,执行下面命令:
gcc switchcase.c -o switchcase
objdump -d -s switchcase > switchcase.txt
Txt文件里包括你想了解的所有信息,我截取了一部分,下面是main函数代码段的关于跳转这部分代码:
点击(此处)折叠或打开
-
40123d: 8b 45 fc mov -0x4(%rbp),%eax
-
401240: 48 8b 04 c5 38 20 40 mov 0x402038(,%rax,8),%rax
-
401247: 00
-
401248: ff e0 jmpq *%rax
-
40124a: e8 37 ff ff ff callq 401186 <case1>
-
40124f: eb 22 jmp 401273 <main+0x87>
-
401251: e8 41 ff ff ff callq 401197 <case2>
-
401256: eb 1b jmp 401273 <main+0x87>
-
401258: e8 4b ff ff ff callq 4011a8 <case3>
-
40125d: eb 14 jmp 401273 <main+0x87>
-
40125f: e8 55 ff ff ff callq 4011b9 <case4>
-
401264: eb 0d jmp 401273 <main+0x87>
-
401266: e8 5f ff ff ff callq 4011ca <case5>
-
40126b: eb 06 jmp 401273 <main+0x87>
-
40126d: e8 69 ff ff ff callq 4011db <casedefault>
-
401272: 90 nop
-
401273: b8 00 00 00 00 mov $0x0,%eax
-
401278: c9 leaveq
-
401279: c3 retq
-
40127a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
-
-
下面是代码段关于几个函数的部分:
-
0000000000401186 <case1>:
-
401186: 55 push %rbp
-
401187: 48 89 e5 mov %rsp,%rbp
-
40118a: bf 08 20 40 00 mov $0x402008,%edi
-
40118f: e8 9c fe ff ff callq 401030 <puts@plt>
-
401194: 90 nop
-
401195: 5d pop %rbp
-
401196: c3 retq
-
-
0000000000401197 <case2>:
-
401197: 55 push %rbp
-
401198: 48 89 e5 mov %rsp,%rbp
-
40119b: bf 0e 20 40 00 mov $0x40200e,%edi
-
4011a0: e8 8b fe ff ff callq 401030 <puts@plt>
-
4011a5: 90 nop
-
4011a6: 5d pop %rbp
-
4011a7: c3 retq
-
-
00000000004011a8 <case3>:
-
4011a8: 55 push %rbp
-
4011a9: 48 89 e5 mov %rsp,%rbp
-
4011ac: bf 14 20 40 00 mov $0x402014,%edi
-
4011b1: e8 7a fe ff ff callq 401030 <puts@plt>
-
4011b6: 90 nop
-
4011b7: 5d pop %rbp
-
4011b8: c3 retq
-
-
00000000004011b9 <case4>:
-
4011b9: 55 push %rbp
-
4011ba: 48 89 e5 mov %rsp,%rbp
-
4011bd: bf 1a 20 40 00 mov $0x40201a,%edi
-
4011c2: e8 69 fe ff ff callq 401030 <puts@plt>
-
4011c7: 90 nop
-
4011c8: 5d pop %rbp
-
4011c9: c3 retq
-
-
00000000004011ca <case5>:
-
4011ca: 55 push %rbp
-
4011cb: 48 89 e5 mov %rsp,%rbp
-
4011ce: bf 20 20 40 00 mov $0x402020,%edi
-
4011d3: e8 58 fe ff ff callq 401030 <puts@plt>
-
4011d8: 90 nop
-
4011d9: 5d pop %rbp
-
4011da: c3 retq
-
-
00000000004011db <casedefault>:
-
4011db: 55 push %rbp
-
4011dc: 48 89 e5 mov %rsp,%rbp
-
4011df: bf 26 20 40 00 mov $0x402026,%edi
-
4011e4: e8 47 fe ff ff callq 401030 <puts@plt>
-
4011e9: 90 nop
-
4011ea: 5d pop %rbp
-
4011eb:
把上面内容说一下,重点关注红色,绿色和蓝色三部分的几个数字,这些都是地址。入口就是最上面的这一行:
mov 0x402038(,%rax,8),%rax
这一行和前面分析的汇编 movq .L10(,%rax,8), %rax这一行对应,意思其实也一样,只是链接后,把标号换成地址值了。括号里面的rax和括号外面的rax也和汇编分析的意思半点不差。那0x402038这个地址是什么意思呢?我们接着看反汇编的只读数据段部分:
-
Contents of section .rodata:
-
402000 01000200 00000000 63617365 31006361 ........case1.ca
-
402010 73653200 63617365 33006361 73653400 se2.case3.case4.
-
402020 63617365 35006361 73656465 6661756c case5.casedefaul
-
402030 74000000 00000000 6d124000 00000000 t.......m.@.....
-
402040 4a124000 00000000 51124000 00000000 J.@.....Q.@.....
-
402050 58124000 00000000 5f124000 00000000 X.@....._.@.....
-
402060 66124000 00000000 f.@.....
红色402030是个地址值,这一行有4个4字节数值,地址分别是402030、402034、402038、40203b,而402038地址处是6d124000,而这里其实真实的数据是8字节:00000000 0040126d,为何呢?0x402038(,%rax,8),%rax,括号外面的%rax的值假设为y,括号里面%rax的值假设是x,则有y = 0x402038+8x。
x = 0, y = 0x402038+0x00 = 0x402038;
x = 1, y = 0x402038+0x08 = 0x402040;
x = 2, y = 0x402038+0x10 = 0x402048;
x = 3, y = 0x402038+0x18 = 0x402050;
x = 4, y = 0x402038+0x20 = 0x402058;
x = 5, y = 0x402038+0x28 = 0x402060;
后面都是8字节对齐。其中x的值就是源代码中的switch后面的值,也就是说根据这个值,%rax得到不同的值。你可以认为这是根据数组的索引得到数组元素的值。每个元素的大小为8字节。这是一个指针数组,指向从0x402038开始的6个地址,每个数组元素指向的元素是8字节,每个元素的具体内容就是右面的数据。
mov 0x402038(,%rax,8),%rax这一行可以认为就是获得数组元素值,jmpq *%rax可以认为以元素值为地址,把这个地址里的内容作为跳转目标。这个跳转目标是什么呢?接着看代码段中的这一部分:
-
401248: ff e0 jmpq *%rax
-
40124a: e8 37 ff ff ff callq 401186 <case1>
-
40124f: eb 22 jmp 401273 <main+0x87>
-
401251: e8 41 ff ff ff callq 401197 <case2>
-
401256: eb 1b jmp 401273 <main+0x87>
-
401258: e8 4b ff ff ff callq 4011a8 <case3>
-
40125d: eb 14 jmp 401273 <main+0x87>
-
40125f: e8 55 ff ff ff callq 4011b9 <case4>
-
401264: eb 0d jmp 401273 <main+0x87>
-
401266: e8 5f ff ff ff callq 4011ca <case5>
-
40126b: eb 06 jmp 401273 <main+0x87>
-
40126d: e8 69 ff ff ff callq 4011db <casedefault>
绿色部分是不是和只读数据段里的内容相同啊。跳转目标就是这几个绿色地址数值的地方。跳转到这里,而这里放的是什么呢?看后面蓝色的部分。这几个蓝色的数字你可以从上面的内容中找到,这就是每个case函数的地址。OK,终于从switch的输入值找到要执行的流程了。
Switch代码在源代码中很常见,但是一般还真没太注意。高效编程的话,switch比else要强不少,分支预测影响指令流,成本很高。另外,还有一点要记住,在我的电脑上,4个case+1个default生成汇编和if-else相同,5个case+1个default才生成跳转表。
阅读(49848) | 评论(0) | 转发(0) |