C++ 反汇编之关于Switch语句的优化措施

流程控制语句是C语言中最基本的判断语句，通常我们可以使用IF来构建多分支结构，但同样可以使用Switch语句构建，Switch语句针对多分支的优化措施有4种形式，分别是，IF-ELSE优化，有序线性优化，非线性索引优化，平衡判定树优化。

与IF语句结构不同，IF语句会在条件跳转后紧跟语句块，而SWITCH结构则将所有条件跳转都放置在一起，判断时需要重点观察每个条件跳转指令后面是否跟有语句块，以辨别SWITCH分支结构。

在switch分支数小于4的情况下，编译器将采用模拟IF-ELSE分支的方式构建SWITCH结构，这样则无法发挥出SWITCH语句的优势，当分支数大于3并且case的判断值存在明显线性关系时，Switch语句的优化特性才可以凸显出来。

有序线性优化: 该优化方式将每个case语句块的地址预先保存在数组中，并依据此数组查询case语句块对应的首地址。

首先代码生成时会为case语句制作一个case地址表数组，数组中保存每个ease语句块的首地址，并且下标以0开头，在进入switch后先进行一次比较，检查输入的数值是否大于case值的最大值，

为了达到线性有序，对于没有case对应的数值，编译器以switch的结束地址或者default语句块的首地址填充对应的表格项。

case线性地址表是一个有序表。

当switch为一个有序线性组合时，会对其case语句块制作地址表，以减少比较跳转次数。

在编写代码时，我们无需自己排列case序列，编译器编译时会自动进行排序优化，先来编写一个简单的代码：

int main(int argc, char *argv[])
{
int index = 0;

scanf("％d", &index);
switch (index)
{
case 1:
printf("index 1"); break;
case 2:
printf("index 2"); break;
case 3:
printf("index 3"); break;
case 6:
printf("index 6"); break;
case 7:
printf("index 7"); break;
default:
printf("default"); break;
}
return 0;
}

代码经过反汇编后，我们可以注意到，首先用户通过scanf输入所需要执行的分支，因为分支语句下标从0开始，所以需要dec eax减去1，在进入switch语句之前，判断输入的下标是否高于6，如果高于则直接跳出switch，否则执行ds:[eax*4+0x401348]寻址。

004012B4 | FF15 B8304000            | call dword ptr ds:[<&scanf>]              |
004012BA | 8B45 FC                  | mov eax,dword ptr ss:[ebp-4]              |
004012BD | 83C4 08                  | add esp,8                                 |
004012C0 | 48                       | dec eax                                   | Switch语句获取比例因子,需要减1
004012C1 | 83F8 06                  | cmp eax,6                                 | 首先对比输入数据是否大于6
004012C4 | 77 6B                    | ja consoleapplication.401331              | 大于则说明Switch分支无对应结构 (则直接跳转到结束)
004012C6 | FF2485 48134000          | jmp dword ptr ds:[eax*4+0x401348]         | 跳转到指定代码段

地址0x401348对应的就是每一个分支的首地址，跳转后即可看到分支。

非线性索引优化: 如果两个case值间隔较大，仍然使用switch的结尾地址或default地址代替地址表中缺少的case地址，这样则会造成极大的空间浪费。

非线性的switch结构，可采用制作索引表的方式进行优化，索引表有两张，1.case语句块地址表，2.case语句块索引表。

地址表中每一项保存一个case语句块首地址，有几个case语句块或default语句块，就保存几项，结束地址在地址表中指挥保存一份。

索引表中保存了地址表中的下标值，索引表最多可容纳256项，每项1字节，所以case值不可超过1字节，索引表也只能存储256项索引编号。

在执行时需要通过索引表来查询地址表，会多出一次查表的过程，因此效率上会有所下降。

004012B4 | FF15 B8304000            | call dword ptr ds:[<&scanf>]              |
004012BA | 8B45 FC                  | mov eax,dword ptr ss:[ebp-4]              |
004012BD | 83C4 08                  | add esp,8                                 |
004012C0 | 48                       | dec eax                                   | Switch语句获取比例因子,需要减1
004012C1 | 3D FE000000              | cmp eax,FE                                | 首先对比输入数据是否大于254
004012C6 | 0F87 80000000            | ja consoleapplication.40134C              | 跳转到指定代码段
004012CC | 0FB680 70134000          | movzx eax,byte ptr ds:[eax+0x401370]      | 从索引表找地址表下标
004012D3 | FF2485 54134000          | jmp dword ptr ds:[eax*4+0x401354]         | 比例因子寻找函数地址

首先movzx eax, byte ptr ds:[eax+0x401370]从索引表中找到地址表下标。

然后通过索引表找到索引值，并带入jmp dword ptr ds:[eax*4+0x401354]找到地址表中的指定地址，地址表中每一个地址就代表一个分支结构里的函数。

这样的优势就是可以节约空间，每一个所以表字段只占1字节，如果两个case差距较大同样会指向同一个地址表中的地址，地址表相对来说会变得简单，但这种查询方式会产生两次间接内存访问，在效率上远远低于线性表方式。

平衡判定树优化: 当最大case值与最小case值之差大于255时，则会采用判定树优化，将每个case值作为一个节点，从节点中找出中间值作为根节点，以此形成一颗平衡二叉树，以每个节点为判定值，大于和小于关系分别对应左子树和右子树，从而提高查询效率。

如果打开编译器体积优先，编译器尽量会以二叉判定树的方式来降低程序占用体积，如果无法使用以上优化方式，则需要将switch做成树。

int main(int argc, char *argv[])
{
int index = 0;

scanf("％d", &index);
switch (index)
{
case 2:
printf("index 2"); break;
case 3:
printf("index 3"); break;
case 8:
printf("index 8"); break;
case 10:
printf("index 10"); break;
case 35:
printf("index 35"); break;
case 37:
printf("index 37"); break;
case 666:
printf("index 666"); break;
}
return 0;
}

判定树反汇编形式。

004012C0 | 83F8 0A                  | cmp eax,A                                 | A:'\n'
004012C3 | 7F 63                    | jg consoleapplication.401328              |
004012C5 | 74 4D                    | je consoleapplication.401314              |
004012C7 | 83E8 02                  | sub eax,2                                 |
004012CA | 74 34                    | je consoleapplication.401300              |
004012CC | 48                       | dec eax                                   |
004012CD | 74 1D                    | je consoleapplication.4012EC              |
004012CF | 83E8 05                  | sub eax,5                                 |
004012D2 | 0F85 97000000            | jne consoleapplication.40136F             |
004012D8 | 68 A0314000              | push consoleapplication.4031A0            | main.cpp:16, 4031A0:"index 8"
004012DD | FF15 B4304000            | call dword ptr ds:[<&printf>]             | main.cpp:20
004012E3 | 83C4 04                  | add esp,4                                 |

判定树，通过增加多条分支结构，从中位数开始判断，大于或小于分别走不同的分支，直到遇到函数地址位置。

为了降低数的高度，在优化过程中，会检查代码是否满足if-else优化，有序线性优化，非线性索引优化，利用三种优化来降低树高度，谁的效率高就优先使用谁，三种优化都无法匹配才会使用判定树。

来源：https://www.cnblogs.com/LyShark/archive/2022/01/28/15852569.html