从底层汇编实现来探索switch

  我们都知道switch是一个选择分支结构，其功能和if...else是一样的，那么他们两个有什么区别呢？我们什么时候用switch，什么时候该用if...else呢？带着这些疑问，我们从汇编的角度剖析一下，ARM64架构编译器是如何做的？？if...else的汇编我们就不过多讲了，可以参考汇编if...else语句，我们主要讲一下switch：

开始之前我们先来了解一下基础知识：也可以点击这里查看常用指令

• ASLR机制，(地址随机化)是一种针对缓冲区溢出的安全保护技术,通过对堆、栈、共享库映射等线性区布局的随机化,通过增加攻击者预测目的地址的难度,防止攻击者直接定位攻击代码位置；
• subs指令，运算结果影响目标寄存器，也影响状态寄存器
• adrp x0, 1 ;将1向左移12位，补0️⃣，即将PC寄存器的低12位清零
• ldrsw x10, [x8, x11, lsl #2] ;将x11寄存器向左移2位，加上x8寄存器地址，作为寻址地址，读出数值放到x10寄存器中。

首先如果一个switch有两个分支：（一般很少用不讲）

如果一个switch有两个case分支：

void testFun(int a)
{
  switch (b) {
        case 5:
            printf("O(∩_∩)O\n");
            break;
        case 9:
            printf("haha\n");
            break;
        default:
            printf("diaomao\n");
            break;
    }
}
调用
testFun(6);

我们看一下汇编代码

Demo`testFun:
    0x1007de1e4 <+0>:   sub    sp, sp, #0x30             ; =0x30 
    0x1007de1e8 <+4>:   stp    x29, x30, [sp, #0x20]
    0x1007de1ec <+8>:   add    x29, sp, #0x20            ; =0x20 
    0x1007de1f0 <+12>:  stur   w0, [x29, #-0x4]
    0x1007de1f4 <+16>:  ldur   w0, [x29, #-0x4]
    0x1007de1f8 <+20>:  mov    x8, x0
    0x1007de1fc <+24>:  subs   w0, w0, #0x5              ; =0x5 
    0x1007de200 <+28>:  stur   w8, [x29, #-0x8]
    0x1007de204 <+32>:  stur   w0, [x29, #-0xc]
    0x1007de208 <+36>:  b.eq   0x1007de224               ; <+64> at main.m:34:13
    0x1007de20c <+40>:  b      0x1007de210               ; <+44> at main.m
    0x1007de210 <+44>:  ldur   w8, [x29, #-0x8]
    0x1007de214 <+48>:  subs   w9, w8, #0x9              ; =0x9 
    0x1007de218 <+52>:  str    w9, [sp, #0x10]
    0x1007de21c <+56>:  b.eq   0x1007de238               ; <+84> at main.m:37:13
    0x1007de220 <+60>:  b      0x1007de24c               ; <+104> at main.m:47:13
    0x1007de224 <+64>:  adrp   x0, 1
    0x1007de228 <+68>:  add    x0, x0, #0xf76            ; =0xf76 
    0x1007de22c <+72>:  bl     0x1007de5f4               ; symbol stub for: printf
    0x1007de230 <+76>:  str    w0, [sp, #0xc]
    0x1007de234 <+80>:  b      0x1007de25c               ; <+120> at main.m:63:1
    0x1007de238 <+84>:  adrp   x0, 1
    0x1007de23c <+88>:  add    x0, x0, #0xf83            ; =0xf83 
    0x1007de240 <+92>:  bl     0x1007de5f4               ; symbol stub for: printf
    0x1007de244 <+96>:  str    w0, [sp, #0x8]
    0x1007de248 <+100>: b      0x1007de25c               ; <+120> at main.m:63:1
->  0x1007de24c <+104>: adrp   x0, 1
    0x1007de250 <+108>: add    x0, x0, #0xf89            ; =0xf89 
    0x1007de254 <+112>: bl     0x1007de5f4               ; symbol stub for: printf
    0x1007de258 <+116>: str    w0, [sp, #0x4]
    0x1007de25c <+120>: ldp    x29, x30, [sp, #0x20]
    0x1007de260 <+124>: add    sp, sp, #0x30             ; =0x30 
    0x1007de264 <+128>: ret  

  我们来分析一下，直到0x1007de1f8 <+20>: mov x8, x0这行指令w0寄存器是我们的形参值8，8比5如果eq，就跳转到0x1007de224（也就是printf("O(∩_∩)O\n");）处执行，那它是如何找到常量的呢？我们通过0x1007de224 <+64>: adrp x0, 1 0x1007de228 <+68>: add x0, x0, #0xf76能够定位到一个内存地址0x1007dff76,然后我们打开view Memory，输入这个地址可以看到：

0x1007dff76
如果不相等，继续往下走，跟9比较，如果相等就跳到0x1007de238处执行，同理，也就是view memory的0x1007dff83地址，也就是上图的haha,否则直接跳到default中，也就是对应的view Memory的0x1007dff89地址----上图的diaomao。

如果一个switch有三个case分支：

void testFun(int a)
{
  switch (b) {
        case 5:
            printf("O(∩_∩)O\n");
            break;
        case 9:
            printf("haha\n");
            break;
        case 2:
            printf("kaiche\n");
            break;
        default:
            printf("diaomao\n");
            break;
    }
}
调用
testFun(6);

注：可以自己测试一下，和上面两个case分支是一样的，也是一个一个比，然后执行相应的输出

如果一个switch有四个case分支：

void testFun(int a)
{
  switch (b) {
        case 5:
            printf("O(∩_∩)O\n");
            break;
        case 9:
            printf("haha\n");
            break;
        case 2:
            printf("kaiche\n");
            break;
        case 6:
            printf("meng(*︶*)bi\n");
            break;
        default:
            printf("diaomao\n");
            break;
    }
}
调用
testFun(6);

汇编代码如下：
Demo`func:
    0x10061a17c <+0>:   sub    sp, sp, #0x50             ; =0x50 
    0x10061a180 <+4>:   stp    x29, x30, [sp, #0x40]
    0x10061a184 <+8>:   add    x29, sp, #0x40            ; =0x40 
    0x10061a188 <+12>:  stur   w0, [x29, #-0x4]
    0x10061a18c <+16>:  ldur   w0, [x29, #-0x4]
    0x10061a190 <+20>:  subs   w0, w0, #0x2              ; =0x2 
    0x10061a194 <+24>:  mov    x8, x0
    0x10061a198 <+28>:  subs   w0, w0, #0x7              ; =0x7 
    0x10061a19c <+32>:  stur   x8, [x29, #-0x10]
    0x10061a1a0 <+36>:  stur   w0, [x29, #-0x14]
    0x10061a1a4 <+40>:  b.hi   0x10061a214               ; <+152> at main.m:47:13
    0x10061a1a8 <+44>:  adrp   x8, 0
    0x10061a1ac <+48>:  add    x8, x8, #0x230            ; =0x230 
->  0x10061a1b0 <+52>:  ldur   x11, [x29, #-0x10]
    0x10061a1b4 <+56>:  ldrsw  x10, [x8, x11, lsl #2]
    0x10061a1b8 <+60>:  add    x9, x8, x10
    0x10061a1bc <+64>:  str    x10, [sp, #0x20]
    0x10061a1c0 <+68>:  br     x9
    0x10061a1c4 <+72>:  adrp   x0, 1
    0x10061a1c8 <+76>:  add    x0, x0, #0xf5e            ; =0xf5e 
    0x10061a1cc <+80>:  bl     0x10061a5dc               ; symbol stub for: printf
    0x10061a1d0 <+84>:  str    w0, [sp, #0x1c]
    0x10061a1d4 <+88>:  b      0x10061a224               ; <+168> at main.m:63:1
    0x10061a1d8 <+92>:  adrp   x0, 1
    0x10061a1dc <+96>:  add    x0, x0, #0xf6b            ; =0xf6b 
    0x10061a1e0 <+100>: bl     0x10061a5dc               ; symbol stub for: printf
    0x10061a1e4 <+104>: str    w0, [sp, #0x18]
    0x10061a1e8 <+108>: b      0x10061a224               ; <+168> at main.m:63:1
    0x10061a1ec <+112>: adrp   x0, 1
    0x10061a1f0 <+116>: add    x0, x0, #0xf71            ; =0xf71 
    0x10061a1f4 <+120>: bl     0x10061a5dc               ; symbol stub for: printf
    0x10061a1f8 <+124>: str    w0, [sp, #0x14]
    0x10061a1fc <+128>: b      0x10061a224               ; <+168> at main.m:63:1
    0x10061a200 <+132>: adrp   x0, 1
    0x10061a204 <+136>: add    x0, x0, #0xf79            ; =0xf79 
    0x10061a208 <+140>: bl     0x10061a5dc               ; symbol stub for: printf
    0x10061a20c <+144>: str    w0, [sp, #0x10]
    0x10061a210 <+148>: b      0x10061a224               ; <+168> at main.m:63:1
    0x10061a214 <+152>: adrp   x0, 1
    0x10061a218 <+156>: add    x0, x0, #0xf88            ; =0xf88 
    0x10061a21c <+160>: bl     0x10061a5dc               ; symbol stub for: printf
    0x10061a220 <+164>: str    w0, [sp, #0xc]
    0x10061a224 <+168>: ldp    x29, x30, [sp, #0x40]
    0x10061a228 <+172>: add    sp, sp, #0x50             ; =0x50 
    0x10061a22c <+176>: ret     

  我们可以看到汇编中有5个adrp，很明显是寻址常量O(∩_∩)O\n,haha\n,kaiche\n,meng(*︶*)bi\n,diaomao\n值，但是我们看到原来的b.eq，变成了b.hi，而且只有一个条件跳转，可是我们有4个case啊？纳尼？
  这就是苹果骚操作，编译器会进行优化选择。我们看看它是怎么优化的，都做了什么。
首先是用形参值6减去2，subs w0, w0, #0x2,然后再减去7subs w0, w0, #0x7，纳尼？减2可以理解，case有一个2，那这个7从哪里来？这里就不卖关子了（2是最小的case，7是最大case与最小case的差值），如果无符号大于，就直接default，也就是，判断形参6是否在最小case与最大case区间[2, 9]，不在[2, 9]区间就直接default(好聪明)。

---

实际上是用参数减去最小的case与case差值进行无符号比较。我们取例子说明一下吧，其实是根据状态寄存机的标志位判断：

• 例子1：如果参数是1，1-2 = -1，无符号情况下，这个-1是一个很大的数比7大，所以走default
• 例子2：如果参数是10，10-2 = 8，本身就比7大，所以走default
• 例子3：如果参数是6，6-2 = 4 < 7,所以在[2,9]区间内

---

  我们的6是在区间[2, 9]内，继续往下执行

    0x10061a1a8 <+44>:  adrp   x8, 0
    0x10061a1ac <+48>:  add    x8, x8, #0x230            ; =0x230 
得到地址：0x10061a230

到这两句指令我们可以得到x8的地址：0x10061a230，我们看看这个地址里面是一个连续的表，每4个字节存一个负数，总共存了8个数据（最大case-最小case+1个default == 9-2+1 == 8）。

0x10061a230数据表
我们还发现0x10061a230地址是紧跟在代码最后一行地址0x10061a22c的。

0x10061a1b0 <+52>:  ldur   x11, [x29, #-0x10]
->  0x10061a1b4 <+56>:  ldrsw  x10, [x8, x11, lsl #2]

从上图（0x10061a230数据表）我们也可以看到x11是4，然后将4左移2位得到16，x8的地址0x10061a230偏移16字节作为寻址地址，取出值放到x10寄存器。根据上图打印结果可以看到是：-48，我们也可以根据x11的值进行打印：p (int)0xffffffffffffffd0得到 (int) $14 = -48

    0x10061a1b8 <+60>:  add    x9, x8, x10
    0x10061a1bc <+64>:  str    x10, [sp, #0x20]
    0x10061a1c0 <+68>:  br     x9

然后根据x8（表的首地址），加上偏移地址-48，得到一个新的地址，作为寻址地址，再根据寄存器寻址br x9，找到要执行的代码，我们根据指令打印一下：
(lldb) p/x 0x10061a230-48
得到结果：(long) $17 = 0x000000010061a200

我们验证一下，地址0x10061a200是不是case6所对应的代码：

    0x10061a200 <+132>: adrp   x0, 1
    0x10061a204 <+136>: add    x0, x0, #0xf79            ; =0xf79 
得到常量地址0x10061bf79

验证memory：

验证Memory
我们看到常量确实是"meng(*︶*)bi"，至此我们就知道了：
当case数量超过3个的时候，编译器会在编译时期将根据case的差值在代码内存后面建立一个表，存表地址与对应的case的偏移值，通过一定的运算找到唯一的映射直接执行，这样就比if...else优雅很多，效率快很多，case数量越多，效率越明显

拓展

如果差值过大，case数量过少，编译器还是会选择if...else

void testFun(int a)
{
  switch (b) {
        case 500:
            printf("O(∩_∩)O\n");
            break;
        case 9:
            printf("haha\n");
            break;
        case 2:
            printf("kaiche\n");
            break;
        case 600:
            printf("meng(*︶*)bi\n");
            break;
        default:
            printf("diaomao\n");
            break;
    }
}
调用
testFun(6);

汇编代码：
Demo`func:
    0x1004d217c <+0>:   sub    sp, sp, #0x40             ; =0x40 
    0x1004d2180 <+4>:   stp    x29, x30, [sp, #0x30]
    0x1004d2184 <+8>:   add    x29, sp, #0x30            ; =0x30 
    0x1004d2188 <+12>:  stur   w0, [x29, #-0x4]
->  0x1004d218c <+16>:  ldur   w0, [x29, #-0x4]
    0x1004d2190 <+20>:  mov    x8, x0
    0x1004d2194 <+24>:  subs   w0, w0, #0x2              ; =0x2 
    0x1004d2198 <+28>:  stur   w8, [x29, #-0x8]
    0x1004d219c <+32>:  stur   w0, [x29, #-0xc]
    0x1004d21a0 <+36>:  b.eq   0x1004d220c               ; <+144> at main.m:40:13
    0x1004d21a4 <+40>:  b      0x1004d21a8               ; <+44> at main.m
    0x1004d21a8 <+44>:  ldur   w8, [x29, #-0x8]
    0x1004d21ac <+48>:  subs   w9, w8, #0x9              ; =0x9 
    0x1004d21b0 <+52>:  stur   w9, [x29, #-0x10]
    0x1004d21b4 <+56>:  b.eq   0x1004d21f8               ; <+124> at main.m:37:13
    0x1004d21b8 <+60>:  b      0x1004d21bc               ; <+64> at main.m
    0x1004d21bc <+64>:  ldur   w8, [x29, #-0x8]
    0x1004d21c0 <+68>:  subs   w9, w8, #0x1f4            ; =0x1f4 
    0x1004d21c4 <+72>:  stur   w9, [x29, #-0x14]
    0x1004d21c8 <+76>:  b.eq   0x1004d21e4               ; <+104> at main.m:34:13
    0x1004d21cc <+80>:  b      0x1004d21d0               ; <+84> at main.m
    0x1004d21d0 <+84>:  ldur   w8, [x29, #-0x8]
    0x1004d21d4 <+88>:  subs   w9, w8, #0x258            ; =0x258 
    0x1004d21d8 <+92>:  str    w9, [sp, #0x18]
    0x1004d21dc <+96>:  b.eq   0x1004d2220               ; <+164> at main.m:43:13
    0x1004d21e0 <+100>: b      0x1004d2234               ; <+184> at main.m:47:13
    0x1004d21e4 <+104>: adrp   x0, 1
    0x1004d21e8 <+108>: add    x0, x0, #0xf5e            ; =0xf5e 
    0x1004d21ec <+112>: bl     0x1004d25dc               ; symbol stub for: printf
    0x1004d21f0 <+116>: str    w0, [sp, #0x14]
    0x1004d21f4 <+120>: b      0x1004d2244               ; <+200> at main.m:63:1
    0x1004d21f8 <+124>: adrp   x0, 1
    0x1004d21fc <+128>: add    x0, x0, #0xf6b            ; =0xf6b 
    0x1004d2200 <+132>: bl     0x1004d25dc               ; symbol stub for: printf
    0x1004d2204 <+136>: str    w0, [sp, #0x10]
    0x1004d2208 <+140>: b      0x1004d2244               ; <+200> at main.m:63:1
    0x1004d220c <+144>: adrp   x0, 1
    0x1004d2210 <+148>: add    x0, x0, #0xf71            ; =0xf71 
    0x1004d2214 <+152>: bl     0x1004d25dc               ; symbol stub for: printf
    0x1004d2218 <+156>: str    w0, [sp, #0xc]
    0x1004d221c <+160>: b      0x1004d2244               ; <+200> at main.m:63:1
    0x1004d2220 <+164>: adrp   x0, 1
    0x1004d2224 <+168>: add    x0, x0, #0xf79            ; =0xf79 
    0x1004d2228 <+172>: bl     0x1004d25dc               ; symbol stub for: printf
    0x1004d222c <+176>: str    w0, [sp, #0x8]
    0x1004d2230 <+180>: b      0x1004d2244               ; <+200> at main.m:63:1
    0x1004d2234 <+184>: adrp   x0, 1
    0x1004d2238 <+188>: add    x0, x0, #0xf88            ; =0xf88 
    0x1004d223c <+192>: bl     0x1004d25dc               ; symbol stub for: printf
    0x1004d2240 <+196>: str    w0, [sp, #0x4]
    0x1004d2244 <+200>: ldp    x29, x30, [sp, #0x30]
    0x1004d2248 <+204>: add    sp, sp, #0x40             ; =0x40 
    0x1004d224c <+208>: ret    

那么这个临界值是什么呢？猜想：case的数量与差值比较，差值大于case数量，编译器会选择if...else，否则会选择建表方式。
然后我建了case分别是从2到49，加52，53，总共50个。差值是53-2=51，发现结果是建表询问的方式。
此时我再修改一下case分别是从2到51，总共50个。差值是51-2=49，发现结果还是建表询问的方式。

猜想不成立，感觉是根据时间复杂度进行取舍选择的。

总结

1、假设switch语句的分支比较少的时候（例如3，少于4的时候没有意义）没有必要使用此结构，相当于if。
2、各个分支常量的差值较大的时候，编译器会在效率还是内存进行取舍，这个时候编译器还是会编译成类似于if，else的结构。
3、在分支比较多的时候：在编译的时候会生成一个表（跳转表每个地址四个字节）。