4.4 编译器使用的优化技巧
本节将讨论基于Pentium微处理器的优化技术。由于代码优化技术博大精深,已成为另外一门学科,其知识体系和本书所讨论的软件逆向分析也不一样,所以本书只对此技术做一些有针对性的讲解。如果大家对这方面的技术有兴趣,可阅读笔者推荐的著作:
《Modern Compiler Implementation in C》(作者:Andrew W.Appel, Maia Ginsburg)此书从编译器实现的角度讲解了代码优化的理论知识和具体方法;
《Code Optimization:Effective Memory Usage》(作者:Kaspersky)
此书从实际工作的角度介绍了如何检查定位目标的低效代码位置,以及调整优化的方法。
所谓代码优化,是指为了达到某一种优化目的对程序代码进行变换。这样的变换有一个原则:变换前和变换后等价(不改变程序的运行结果)。
就优化目的而论,代码优化一般有四个方向:
执行速度优化;
内存存储空间优化;
磁盘存储空间优化;
编译时间优化(别诧异,大型软件编译一次需要好几个小时是常事)。
如今,计算机的存储空间都不小,因此常见的优化都是以执行速度的优化为主,这里也仅以速度优化为主展开讨论。编译器的工作过程中可以分为几个阶段:预处理→词法分析→语法分析→语义分析→中间代码生成→目标代码生成。其中,优化的机会一般存在于中间代码生成和目标代码生成这两个阶段。尤其是在中间代码生成阶段所做的优化,这类优化不具备设备相关性,在不同的硬件环境中都能通用,因此编译器设计者广泛采用这类办法。
常见的与设备无关的优化方案有以下几种。
常量折叠
示例如下:
x=1+2;
1和2都是常量,结果可以预见,必然是3,因此没必要产生加法指令,直接生成x=3;即可。
常量传播
接上例,其后代码为y=x+3;由于上例最后生成了x=3;,其结果还是可以预见的,所以直接生成y=6;即可。
减少变量
示例如下:
x=i*2;
y=j*2;
if(x>y)//其后再也没有引用x、y
{
…….
}
这时对x、y的比较等价于对i、j的比较,可以去掉x、y,直接生成if(i>j)。
公共表达式
示例如下:
x=i*2;
y=i*2;
这时i*2被称为公共表达式,可以归并为一个,如下:
x=i*2;
y=x;
复写传播
类似于常量传播,但是目标变成了变量,示例如下:
x=a;
……
y=x+c;
如果省略号表示的代码中没有修改变量x,则可以直接用变量a代替x:
y=a+c;
剪去不可达分支(剪支优化)
示例如下:
if(1>2)//条件永远为假
{
……
}
由于if作用域内的代码内容永远不可能被执行,因此整个if代码块没有存在的理由。
顺序语句代替分支
请参考4.2.3小节中条件表达式的优化。
强度削弱
用加法或者移位代替乘法,用乘法或者移位代替除法,请参考4.1.1小节中关于乘除法的优化。
数学变换
以下表达式都是代数恒等式:
x=a+0;
x=a-0;
x=a*1;
x=a/1;
因此,不会产生运算指令,直接输入x=a;即可。
下面这个表达式稍复杂一点:
x=a*y+b*y;//等价于x=(a+b)*y;
这样只需一次加法一次乘法即可。
代码外提
这类优化一般存在于循环中,如下面的代码所示:
while(x>y/2)
{
……//循环体内没有修改y值
}
以上代码不必在每次判定循环条件时都做一次除法,可以进行如下优化:
t=y/2;
while(x>t)
……
在实际分析过程中,很可能会组合应用以上优化方案,读者应先建立优化方案的概念,以后遇到各类方案的组合时用心琢磨体会即可。
以上是中间代码生成阶段的各类优化方案,下面我们讨论目标代码生成阶段的各类优化方案。生成目标代码,也就是二进制代码,是和设备有关的。这里讨论的是基于32位Pentium微处理器的优化。
目标代码生成阶段有以下几种优化方案:
流水线优化
分支优化
高速缓存(cache)优化
下面逐一介绍以上三种优化方案。
流水线技术的由来(摘自百度百科)
从前,在英格兰北部的一个小镇上,有一个名叫艾薇的人开的炸鱼和油煎土豆片商店。在店里面,每位顾客需要排队才能点他(她)要的食物(比如油炸鳕鱼,油煎土豆片,豌豆糊和一杯茶),然后等着盘子装满后坐下来进餐。
艾薇店里的油煎土豆片是小镇中最好的,在每个集市日的中午,长长的队伍都会排出商店。所以,当隔壁的木器店关门时,艾薇就把它租了.
没办法再另外增加服务台了,后来艾薇想出了一个聪明的办法。把柜台加长,艾薇,伯特,狄俄尼索斯和玛丽站成一排。顾客进来时,艾薇先给他们一个盛着鳕鱼的盘子,然后伯特加上油煎土豆片,狄俄尼索斯再盛上豌豆糊,最后玛丽倒茶并收钱。顾客们不停地走动,一位顾客拿到豌豆糊的同时,他后面的已经拿到了油煎土豆片,再后面的一个已经拿到了鳕鱼。一些村民不吃豌豆糊,但这没关系,他们也能从狄俄尼索斯那里得个笑脸。
这样一来队伍变短了,不久以后,艾薇买下了对面的商店又增加了更多的餐位。这就是流水线。将那些具有重复性的工作分割成几个串行部分,使工作能在工人们中间移动,每个熟练工人只需要依次将自己那部分工作做好就可以了。虽然每位顾客等待服务的总时间没变,但是同时接受服务的顾客有四个,这样在集市日的午餐时段里能够照顾的顾客数增加了三倍。
4.4.1 流水线优化规则
1.指令的工作流程
1)取指令
CPU从高速缓存或内存中取机器码。
2)指令译码
分析指令的长度、功能和寻址方式。
3)按寻址方式确定操作数
指令的操作数可以是寄存器、内存单元或者立即数(包含在完整指令中),如果操作数在内存单元里,这一步就要计算出有效地址(Effective Address, EA)。
4)取操作数
按操作数存放的位置获得数值,并存放在临时寄存器中。
5)执行指令
由控制单元(Control Unit, CU)或者计算单元(Arithmetic Logic Unit, ALU)执行指令规定的操作。
6)存放计算结果
其中步骤1)、2)、5)是必须的,其他步骤视指令功能而定,比如,控制类指令NOP没有操作数,步骤3)、4)、6)也就没有了。
下面举例说明一个完整的指令流程。
比如执行指令:add eax, dword ptr ds:[ebx+40DA44]
对应的机器代码是:0383 44DA4000
注意,Intel处理器是以小尾方式排列的,数据的高位对应内存的高地址,低位对应内存的低地址。
第1步,取指令,得到第1个十六进制字节:0x03,并且eip加1。
第2步,译码得知这个指令是个加法,但是信息不够,先把上次取到的机器码放入处理器的指令队列缓存中。
第3步,取指令,得到第2个十六进制字节:0x83。机器码放入处理器的指令队列缓存中,eip加1。
第4步,译码得知这个指令是寄存器相对寻址方式的加法,而且参与寻址的寄存器是ebx,存放目标是eax,其后还跟着4字节的偏移量,这样指令长度也确定了。机器码放入处理器的指令队列缓存中。
第5步[1],取地址,得到第3个十六进制字节:0x44,这是指令中包含的4字节地址偏移量信息的第1个字节,先放入内部暂存器;同时ebx的值保存到ALU,准备计算有效地址,eip加1。
第6步,取指令,得到第4个十六进制字节:0xDA,先放入内部暂存器,eip加1。
第7步,取指令,得到第5个十六进制字节:0x40,先放入内部暂存器,eip加1。
第8步,取指令,得到第6个十六进制字节:0x00,先放入内部暂存器,eip加1。
第9步,此时4字节偏移量全部到位,ALU中也保留了ebx的值,于是开始计算有效地址。
第10步,将eax的值传送到ALU;调度内存管理单元(MMU),得到内存单元中的值,将其传送到ALU,并计算结果。
第11步,按指令要求,将计算结果存回eax中。
2.什么是流水线
由于每条指令的工作流程都是由取指令、译码、执行、回写等步骤构成的,所以处理器厂商设计了多流水线结构,也就是说,在A流水线处理的过程中,B流水线可以提前对下一条指令做处理。我们先来看下面的例子:
004010AA mov eax,92492493h
004010AF add esp,8
执行这段代码,不具备流水线的处理器先读取004010AA处的二进制指令,然后开始译码等操作,这一系列工作的每一步都是需要时间的,比如取指令,内存管理单元开始工作,其他部件闲置等待,等拿到了指令才进行下一步工作。于是,为了提高效率,Intel公司从486开始就引入了流水线的机制。
引入流水线机制以后,在第一条流水线执行mov eax,92492493h的过程中,第二条流水线就可以开始对004010AF进行读取和译码了。这样就可以并行处理了,从而提高了处理器的工作效率。
对于流水线的设计,不同的厂商有不同的设计理念。比如Intel的长流水线设计,把每条指令划分出很多阶段(执行步骤),使得每个步骤的工作内容都很简单,从而容易设计电路,加快工作频率,因此Intel的处理器的主频较高。但是这样也有缺点,举例说明,如果执行的指令变成如下所示:
00401063 jmp[00401000h]
00401069 add esp,8
那么,按长流水线设计的处理器使A流水线先取得00401063的指令,然后开始译码等步骤,这时候B流水线开始工作,按部就班去00401069处取指令,也开始译码等步骤。当A流水线译码完成,知道这是个jmp指令,意识到B流水线取指令错误了,需要立刻停止B流水线的工作,定位新地址,从取指令开始重新工作,有些时候甚至需要回滚操作,清除掉B流水线执行错误带来的影响(流水线冲洗)。由于长流水线设计步骤较多,会导致发生错误后损失较大。
相对Intel的长流水线设计,AMD的设计理念是多流水线设计,也就是说为每条指令划分的工作阶段少,但是流水线数量较多。这样一来,并行程度更高了,而且由于流水线的工作步骤少,弥补错误会更及时,错误的影响也较少。当然也有缺点,同样的指令,由于划分的工作阶段少,每个阶段做的事情多,电路设计也就较为复杂,主频也会受到限制,同时由于流水线数量较多,处理器对流水线的管理成本也增大了。
3.注意事项
明白流水线的设计初衷以后,我们来探讨一下影响流水线工作的一些禁忌,以及编译器在这方面的工作。
指令相关性
对于顺序安排的两条指令,后一条指令的执行依赖前一条指令的硬件资源,这样的情况就是指令相关,如下面的代码所示:
add edx, esi
sar edx,2
由于以上两条代码都需要访问并设置edx,因此只能在执行完add edx, esi后才能执行sar edx,2。这样的情况会存在寄存器的争用,影响并行效率,应尽量避免。
地址相关性
对于顺序安排的两条指令,前一条指令需要访问并回写到某一地址上,而后一条指令也需要访问这一地址,这样的情况就是地址相关,如下面的代码所示:
add[00401234],esi
mov eax,[00401234]
由于第一条指令计算并回写到[00401234],而第二条指令也需要访问[00401234],形成了对内存地址的争用,因此只能在第一条指令操作完成后再去执行第二条语句,这同样影响了并行效率,应尽量避免。
由VC++的O2选项生成的代码会考虑流水线执行的工作方式,如以下代码所示:
.text:0040101F push eax
.text:00401020 push offset aNvarone2D;"nVarOne/2=%d"
.text:00401025 call_printf
.text:0040102A mov eax,92492493h
.text:0040102F add esp,8
.text:00401032 imul esi
.text:00401034 add edx, esi
.text:00401036 sar edx,2
.text:00401039 mov eax, edx
.text:0040103B shr eax,1Fh
.text:0040103E add edx, eax
.text:00401025处的call_printf是C语言的调用方式,由调用方恢复栈顶,其恢复栈顶的指令是.text:0040102F处的add esp,8,中间有mov eax,92492493h指令,这里就是典型的流水线优化。因为mov eax,92492493h和.text:00401032处的imul esi存在指令相关性,mov eax,92492493h需要设置eax,而imul指令也是把计算结果的低位设置到eax。由于存在寄存器争用的问题,这两条指令是无法并行的,因此,编译器在不影响程序结果的前提下,将mov eax,92492493h安排到add esp,8之上了,这两者没有任何相关性,能同时执行。但是,流水线优化的前提条件是不影响计算结果,请看.text:00401034处的add edx, esi和.text:00401036处的sar edx,2这两条指令,都需要设置edx,所以无法并行,为了保证计算结果的正确,不能改变执行顺序,编译器只能放弃流水线优化了。
[1]对于CISC指令集,指令长度是可变的,所以CPU工作时需要按字节取得指令,然后译码。如果译码后得知后面是地址,可以实现直接以4字节的方式取地址。但是,如果这样,又会导致流水线工作处于等待状态,因为只有在译码后才能取得后面的内容。因此,不同的CPU设计结构解决这个问题的方式都可能不一样。