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

C++ 反汇编:关于Switch语句的优化措施,第1张

流程控制语句是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对应的就是每一个分支的首地址,跳转后即可看到分支。

C++ 反汇编:关于Switch语句的优化措施,第2张

非线性索引优化: 如果两个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]从索引表中找到地址表下标。

C++ 反汇编:关于Switch语句的优化措施,第3张

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

C++ 反汇编:关于Switch语句的优化措施,第4张

这样的优势就是可以节约空间,每一个所以表字段只占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                                 |

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

C++ 反汇编:关于Switch语句的优化措施,第5张

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

文章出处:https://www.cnblogs.com/LyShark/p/15852569.html
版权声明:本博客文章与代码均为学习时整理的笔记,博客中除去明确标注有参考文献的文章,其他文章 [均为原创] 作品,转载请 [添加出处] ,您添加出处是我创作的动力!

如果您恶意转载本人文章并被本人发现,则您的整站文章,将会变为我的原创作品,请相互尊重 !

文章来源:https://www.cnblogs.com/LyShark/p/15852569.html

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复