Chinaunix首页 | 论坛 | 博客

石头的奔跑

首页　| 　博文目录　| 　关于我

shiyigudong

  • 博客访问： 1725897
  • 博文数量： 98
  • 博客积分： 667
  • 博客等级： 上士
  • 技术积分： 1631
  • 用 户 组： 普通用户
  • 注册时间： 2009-04-27 15:59
个人简介

一沙一世界 一树一菩提

文章分类

全部博文（98）

文章存档

2021年（8）

2020年（16）

2019年（8）

2017年（1）

2016年（11）

2015年（17）

2014年（9）

2013年（4）

2012年（19）

2011年（1）

2009年（4）

我的朋友
最近访客
推荐博文
相关博文
switch的汇编分析

分类： C/C++

2020-08-02 23:41:55

这几天对汇编有点意思，以前也接触不少，但是没太注意。前几天无意看到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分支的数量而增加。如下面的代码：
点击(此处)折叠或打开

  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，系统是ubuntu1604，64位。

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

一  4个case+default不会生成跳转表，生成的是cmpl和je,和if-else比较类似。

二  5个case+default，生成跳转结构

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

点击(此处)折叠或打开

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

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

  10. void case2(void)
  11. {
  12.     printf("case2\n");
  13. }

  15. void case3(void)
  16. {
  17.     printf("case3\n");
  18. }

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

  25. void case5(void)
  26. {
  27.     printf("case5\n");
  28. }

  30. void casedefault(void)
  31. {
  32.     printf("casedefault\n");
  33. }


  36. int main(void)
  37. {
  38.     srand(time(NULL));
  39.     int branchvare = rand()%10;
  40.     switch(branchvare)
  41.     {
  42.         case 1:case1();break;
  43.         case 2:case2();break;
  44.         case 3:case3();break;
  45.         case 4:case4();break;
  46. //        case 5:case5();break;
  47.         default:casedefault();break;
  48.     }
  49.     return 0;
  50. }
我们看看这段代码的汇编是个什么样子，执行

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

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

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

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

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

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

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

  68. 00000000004011db <casedefault>:
  69.   4011db:    55     push %rbp
  70.   4011dc:    48 89 e5     mov %rsp,%rbp
  71.   4011df:    bf 26 20 40 00     mov $0x402026,%edi
  72.   4011e4:    e8 47 fe ff ff     callq 401030 <puts@plt>
  73.   4011e9:    90     nop
  74.   4011ea:    5d     pop %rbp
  75.   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是个地址值，这一行有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可以认为以元素值为地址，把这个地址里的内容作为跳转目标。这个跳转目标是什么呢？接着看代码段中的这一部分：

点击(此处)折叠或打开

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










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

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

下一篇：skylake and other lakes pipeline (三）

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6