Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1130457
  • 博文数量: 86
  • 博客积分: 667
  • 博客等级: 上士
  • 技术积分: 1472
  • 用 户 组: 普通用户
  • 注册时间: 2009-04-27 15:59
个人简介

一沙一世界

文章分类

全部博文(86)

文章存档

2020年(10)

2019年(8)

2017年(3)

2016年(11)

2015年(17)

2014年(9)

2013年(4)

2012年(19)

2011年(1)

2009年(4)

分类: C/C++

2020-08-02 23:41:55

这几天对汇编有点意思,以前也接触不少,但是没太注意。前几天无意看到switchif-else区别,就想深入研究下switch如何生成跳转表提高效率的。有误的地方大家提出里,多交流。
34275076@qq.com或者shiyigudong@gmail.com

背景是在http://www.eventhelix.com/RealtimeMantra/Basics/CToAssemblyTranslation3.htm这里看到关于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分支的数量而增加。如下面的代码:
点击(此处)折叠或打开

  1. {
  2.         case 1:
  3. ...
  4.         case 1000:
  5. ...
  6.         case 100:
  7. ...
  8.         case 500:
  9.         case 5:
  10.         default:casedefault();break;
  11. }


我的电脑是i7-9750h,系统是ubuntu160464位。

对于switch首先有2点需要注意:

一  4case+default不会生成跳转表,生成的是cmplje,if-else比较类似。

二  5case+default,生成跳转结构

先看C源码,这是不会生成跳转表的代码:

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>

  4. void case1(void)
  5. {
  6.     printf("case1\n");
  7. }

  8. void case2(void)
  9. {
  10.     printf("case2\n");
  11. }

  12. void case3(void)
  13. {
  14.     printf("case3\n");
  15. }

  16. void case4(void)
  17. {
  18.     printf("case4\n");
  19. }

  20. void case5(void)
  21. {
  22.     printf("case5\n");
  23. }

  24. void casedefault(void)
  25. {
  26.     printf("casedefault\n");
  27. }


  28. int main(void)
  29. {
  30.     srand(time(NULL));
  31.     int branchvare = rand()%10;
  32.     switch(branchvare)
  33.     {
  34.         case 1:case1();break;
  35.         case 2:case2();break;
  36.         case 3:case3();break;
  37.         case 4:case4();break;
  38. //        case 5:case5();break;
  39.         default:casedefault();break;
  40.     }
  41.     return 0;
  42. }
我们看看这段代码的汇编是个什么样子,执行

gcc -S switchcase.c -o switchcase.s

我删除了大部分,下面这部分是关键:

点击(此处)折叠或打开

  1. movl    %eax, -4(%rbp) #eax中存放的是c代码中的 branchvare变量值
  2.     movl    -4(%rbp), %eax
  3.     cmpl    $2, %eax
  4.     je    .L9 #等于2跳转到L9
  5.     cmpl    $2, %eax
  6.     jg    .L10 #大于2跳转到L10,在L10代码处又进行了分支跳转
  7.     cmpl    $1, %eax
  8.     je    .L11 #等于1跳转到L11
  9.     jmp    .L8 #跳转default
  10. .L10:
  11.     cmpl    $3, %eax
  12.     je    .L12
  13.     cmpl    $4, %eax
  14.     je    .L13
  15.     jmp    .L8
  16. .L11:
  17.     call    case1
  18.     jmp    .L14
  19. .L9:
  20.     call    case2
  21.     jmp    .L14
  22. .L12:
  23.     call    case3
  24.     jmp    .L14
  25. .L13:
  26.     call    case4
  27.     jmp    .L14
  28. .L8:
  29.     call    casedefault
  30.     nop
  31. .L14:
  32.     movl    $0, %eax
  33.     leave
  34.     .cfi_def_cfa 7, 8
  35.     ret
  36.     .cfi_endproc
大家可以明确的看到,被汇编成cmp比较和je跳转。也就是和if-else的逻辑相同。这段不细说了,看下面。

把上面的C代码中的// case 5:case5();break;注释去掉,其它不变。Switch-case部分如下:

点击(此处)折叠或打开

  1. switch(branchvare)
  2. {
  3.         case 1:case1();break;
  4.         case 2:case2();break;
  5.         case 3:case3();break;
  6.         case 4:case4();break;
  7.         case 5:case5();break;
  8.         default:casedefault();break;
  9.  }

对应的汇编代码,我只截取了一部分:

点击(此处)折叠或打开

  1. movl    %eax, -4(%rbp)
  2.     cmpl    $5, -4(%rbp)
  3.     ja    .L8 #大于5不经过跳转表,直接跳转到L8处,也就是default处理代码
  4.     movl    -4(%rbp), %eax
  5.     movq    .L10(,%rax,8), %rax 
  6. #%rax寄存器里存放的是c代码里的branchvare,也就是索引值。绿色的%rax存放的是case对应项的地址值,L10可以认为该处是一个数组,这个数组里存放的就是各个case项的地址,每一项占8字节。jmp指令的操作数有 前缀 ' * ' ,表明这是一个间接跳转,操作数指定一个内存位置,大家可以认为%rax前加`*`就当时c语言里的指针。这个jmp就跳转到case对应的代码了。
  7.     jmp    *%rax

  8.     .section    .rodata
  9.     .align 8
  10.     .align 4
  11. .L10:
  12.     .quad    .L8
  13.     .quad    .L9
  14.     .quad    .L11
  15.     .quad    .L12
  16.     .quad    .L13
  17.     .quad    .L14
  18.     .text
  19. .L9:
  20.     call    case1
  21.     jmp    .L15
  22. .L11:
  23.     call    case2
  24.     jmp    .L15
  25. .L12:
  26.     call    case3
  27.     jmp    .L15
  28. .L13:
  29.     call    case4
  30.     jmp    .L15
  31. .L14:
  32.     call    case5
  33.     jmp    .L15
  34. .L8:
  35.     call    casedefault
  36.     nop
  37. .L15:
  38.     movl    $0, %eax
  39.     leave
  40.     .cfi_def_cfa 7, 8
  41.     ret
  42.     .cfi_endproc


这部分汇编子关键的就是中间注释那段中文。其它不多说。

下面我们看看反汇编的情况,执行下面命令:

gcc switchcase.c -o switchcase

objdump -d -s switchcase > switchcase.txt

Txt文件里包括你想了解的所有信息,我截取了一部分,下面是main函数代码段的关于跳转这部分代码:
点击(此处)折叠或打开

  1.   40123d:    8b 45 fc                 mov -0x4(%rbp),%eax
  2.   401240:    48 8b 04 c5 38 20 40     mov 0x402038(,%rax,8),%rax
  3.   401247:    00
  4.   401248:    ff e0                     jmpq *%rax
  5.   40124a:    e8 37 ff ff ff     callq 401186 <case1>
  6.   40124f:    eb 22                     jmp 401273 <main+0x87>
  7.   401251:    e8 41 ff ff ff     callq 401197 <case2>
  8.   401256:    eb 1b                     jmp 401273 <main+0x87>
  9.   401258:    e8 4b ff ff ff     callq 4011a8 <case3>
  10.   40125d:    eb 14                     jmp 401273 <main+0x87>
  11.   40125f:    e8 55 ff ff ff     callq 4011b9 <case4>
  12.   401264:    eb 0d                     jmp 401273 <main+0x87>
  13.   401266:    e8 5f ff ff ff     callq 4011ca <case5>
  14.   40126b:    eb 06                     jmp 401273 <main+0x87>
  15.   40126d:    e8 69 ff ff ff     callq 4011db <casedefault>
  16.   401272:    90                     nop
  17.   401273:    b8 00 00 00 00         mov $0x0,%eax
  18.   401278:    c9                     leaveq
  19.   401279:    c3                     retq
  20.   40127a:    66 0f 1f 44 00 00      nopw 0x0(%rax,%rax,1)

  21. 下面是代码段关于几个函数的部分:
  22. 0000000000401186 <case1>:
  23.   401186:    55     push %rbp
  24.   401187:    48 89 e5     mov %rsp,%rbp
  25.   40118a:    bf 08 20 40 00     mov $0x402008,%edi
  26.   40118f:    e8 9c fe ff ff     callq 401030 <puts@plt>
  27.   401194:    90     nop
  28.   401195:    5d     pop %rbp
  29.   401196:    c3     retq

  30. 0000000000401197 <case2>:
  31.   401197:    55     push %rbp
  32.   401198:    48 89 e5     mov %rsp,%rbp
  33.   40119b:    bf 0e 20 40 00     mov $0x40200e,%edi
  34.   4011a0:    e8 8b fe ff ff     callq 401030 <puts@plt>
  35.   4011a5:    90     nop
  36.   4011a6:    5d     pop %rbp
  37.   4011a7:    c3     retq

  38. 00000000004011a8 <case3>:
  39.   4011a8:    55     push %rbp
  40.   4011a9:    48 89 e5     mov %rsp,%rbp
  41.   4011ac:    bf 14 20 40 00     mov $0x402014,%edi
  42.   4011b1:    e8 7a fe ff ff     callq 401030 <puts@plt>
  43.   4011b6:    90     nop
  44.   4011b7:    5d     pop %rbp
  45.   4011b8:    c3     retq

  46. 00000000004011b9 <case4>:
  47.   4011b9:    55     push %rbp
  48.   4011ba:    48 89 e5     mov %rsp,%rbp
  49.   4011bd:    bf 1a 20 40 00     mov $0x40201a,%edi
  50.   4011c2:    e8 69 fe ff ff     callq 401030 <puts@plt>
  51.   4011c7:    90     nop
  52.   4011c8:    5d     pop %rbp
  53.   4011c9:    c3     retq

  54. 00000000004011ca <case5>:
  55.   4011ca:    55     push %rbp
  56.   4011cb:    48 89 e5     mov %rsp,%rbp
  57.   4011ce:    bf 20 20 40 00     mov $0x402020,%edi
  58.   4011d3:    e8 58 fe ff ff     callq 401030 <puts@plt>
  59.   4011d8:    90     nop
  60.   4011d9:    5d     pop %rbp
  61.   4011da:    c3     retq

  62. 00000000004011db <casedefault>:
  63.   4011db:    55     push %rbp
  64.   4011dc:    48 89 e5     mov %rsp,%rbp
  65.   4011df:    bf 26 20 40 00     mov $0x402026,%edi
  66.   4011e4:    e8 47 fe ff ff     callq 401030 <puts@plt>
  67.   4011e9:    90     nop
  68.   4011ea:    5d     pop %rbp
  69.   4011eb:

把上面内容说一下,重点关注红色,绿色和蓝色三部分的几个数字,这些都是地址。入口就是最上面的这一行:

mov    0x402038(,%rax,8),%rax

这一行和前面分析的汇编  movq .L10(,%rax,8), %rax这一行对应,意思其实也一样,只是链接后,把标号换成地址值了。括号里面的rax和括号外面的rax也和汇编分析的意思半点不差。那0x402038这个地址是什么意思呢?我们接着看反汇编的只读数据段部分:

点击(此处)折叠或打开

  1. Contents of section .rodata:
  2.  402000 01000200 00000000 63617365 31006361 ........case1.ca
  3.  402010 73653200 63617365 33006361 73653400 se2.case3.case4.
  4.  402020 63617365 35006361 73656465 6661756c case5.casedefaul
  5.  402030 74000000 00000000 6d124000 00000000 t.......m.@.....
  6.  402040 4a124000 00000000 51124000 00000000 J.@.....Q.@.....
  7.  402050 58124000 00000000 5f124000 00000000 X.@....._.@.....
  8.  402060 66124000 00000000 f.@.....

红色402030是个地址值,这一行有44字节数值,地址分别是40203040203440203840203b,而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可以认为以元素值为地址,把这个地址里的内容作为跳转目标。这个跳转目标是什么呢?接着看代码段中的这一部分:

点击(此处)折叠或打开

  1.   401248:    ff e0     jmpq *%rax
  2.   40124a:    e8 37 ff ff ff     callq 401186 <case1>
  3.   40124f:    eb 22                  jmp 401273 <main+0x87>
  4.   401251:    e8 41 ff ff ff     callq 401197 <case2>
  5.   401256:    eb 1b                  jmp 401273 <main+0x87>
  6.   401258:    e8 4b ff ff ff     callq 4011a8 <case3>
  7.   40125d:    eb 14                  jmp 401273 <main+0x87>
  8.   40125f:    e8 55 ff ff ff     callq 4011b9 <case4>
  9.   401264:    eb 0d                  jmp 401273 <main+0x87>
  10.   401266:    e8 5f ff ff ff     callq 4011ca <case5>
  11.   40126b:    eb 06                  jmp 401273 <main+0x87>
  12.   40126d:    e8 69 ff ff ff     callq 4011db <casedefault>

绿色部分是不是和只读数据段里的内容相同啊。跳转目标就是这几个绿色地址数值的地方。跳转到这里,而这里放的是什么呢?看后面蓝色的部分。这几个蓝色的数字你可以从上面的内容中找到,这就是每个case函数的地址。OK,终于从switch的输入值找到要执行的流程了。

Switch代码在源代码中很常见,但是一般还真没太注意。高效编程的话,switchelse要强不少,分支预测影响指令流,成本很高。另外,还有一点要记住,在我的电脑上,4case+1default生成汇编和if-else相同,5case+1default才生成跳转表。










阅读(1151) | 评论(0) | 转发(0) |
0

上一篇: Optimizing C and C++ Code(二)

下一篇:没有了

给主人留下些什么吧!~~