4.4　编译器使用的优化技巧

本节将讨论基于Pentium微处理器的优化技术。由于代码优化技术博大精深，已成为另外一门学科，其知识体系和本书讨论的软件逆向分析也不一样，所以本书只对此技术做一些有针对性的讲解。如果大家对这方面的技术有兴趣，可阅读笔者推荐的著作。

  • Modern Compiler Implementation in C，作者：Andrew W.Appel和Maia Ginsburg。此书从编译器实现的角度讲解了代码优化的理论知识和具体方法。
  • Code Optimization:Effective Memory Usage，作者：Kaspersky。此书从实际工作的角度介绍了如何检查定位目标的低效代码位置以及调整优化的方法。

所谓代码优化，是指为了达到某一种优化目的对程序代码进行变换。这样的变换有一个原则：变换前和变换后等价（不改变程序的运行结果）。

就优化目的而言，代码优化一般有如下4个方向。

  • 执行速度优化。
  • 内存存储空间优化。
  • 磁盘存储空间优化。

编译时间优化（别诧异，大型软件编译一次需要好几个小时是常事）。

如今，计算机的存储空间都不小，因此常见的都是以执行速度为主的优化，这里仅以速度优化为主展开讨论。编译器的工作过程可以分为几个阶段：预处理→词法分析→语法分析→语义分析→中间代码生成→目标代码生成。其中，优化的机会一般存在于中间代码生成和目标代码生成这两个阶段。尤其是在中间代码生成阶段所做的优化不具备设备相关性，在不同的硬件环境中都能通用，因此编译器设计者广泛采用这类办法。

常见的与设备无关的优化方案有以下几种。

1. 常量折叠

示例如下：

x = 1 + 2；

1和2都是常量，结果可以预见，必然是3，因此没必要产生加法指令，直接生成x=3即可。

2. 常量传播

接上例，下一行代码为y=x+3，由于上例最后生成了x=3，其结果还是可以预见的，所以直接生成y=6即可。

3. 减少变量

示例如下：

x = i*2; y = j*2;
if(x > y) // 其后再也没有引用 x、y
{
…
}

这时对x、y的比较等价于对i、j的比较，因此可以去掉x、y，直接生成if(i>j)。

4. 公共表达式

示例如下：

x = i * 2; y = i * 2;

这时i * 2被称为公共表达式，可以归并为一个，即

x = i * 2;
y = x;

5. 复写传播

类似于常量传播，但是目标变成了变量，示例如下：

x = a;
……
y = x+c;

如果省略号表示的代码中没有修改变量x，则可以直接用变量a代替x，即

y = a + c；

6. 剪去不可达分支（剪支优化）

示例如下：

if( 1>2) //条件永远为假
{
…
}

由于if作用域内的代码内容永远不会执行，因此整个if代码块没有存在的理由。

7. 顺序语句代替分支

请参考4.2.3节中条件表达式的优化。

8. 强度削弱

用加法或者移位代替乘法，用乘法或者移位代替除法，请参考4.1.1节中关于乘除法的优化。

9. 数学变换

以下表达式都是代数恒等式：

x = a + 0; x = a - 0; x = a * 1; x = a / 1;

因此，不会产生运算指令，直接输入x=a即可。下面这个表达式稍复杂一点：

x = a * y + b * y;//等价于x = (a+b) * y;

这样只须进行一次加法一次乘法。

10. 代码外提

这类优化一般存在于循环中，如下列代码所示：

while(x > y/2)
{
… //循环体内没有修改y值
}

以上代码不必在每次判定循环条件时都做除法，可以进行如下优化：

t = y / 2;
while(x > t)
…

在实际分析过程中，很可能会组合应用以上优化方案，读者应先建立优化方案的概念，以后遇到各类方案的组合时用心琢磨体会即可。

以上是中间代码生成阶段的各类优化方案，下面我们讨论目标代码生成阶段的优化方案。生成目标代码，也就是二进制代码，是和设备有关的。这里讨论的是基于32位Pentium微处理器的优化。

目标代码生成阶段有以下3种优化案。

  • 流水线优化。
  • 分支优化。
  • 高速缓存（cache）优化。

流水线技术的由来[1]

从前，在英格兰北部的一个小镇上，一个名叫艾薇的人经营着一家炸鱼和油煎土豆片商店。在店里面，每位顾客需要排队才能点餐（比如油炸鳕鱼、油煎土豆片、豌豆糊和一杯茶），然后等着盘子装满后坐下来用餐。

艾薇店里的油煎土豆片是小镇中最好吃的，在每个集市日的中午，长长的队伍都会排出商店。所以，当隔壁的木器店关门时，艾薇就把它租下了。

没办法再另外增加服务台了，艾薇想出了一个聪明的办法。把柜台加长，艾薇、伯特、狄俄尼索斯和玛丽站成一排。顾客进来时，艾薇先给他们一个盛着鳕鱼的盘子，然后伯特加上油煎土豆片，狄俄尼索斯再盛上豌豆糊，最后玛丽倒茶并收钱。顾客们不停地走动，一位顾客拿到豌豆糊的同时，他后面的人已经拿到了油煎土豆片，再后面的一个人已经拿到了鳕鱼。一些村民不吃豌豆糊，但这没关系，他们也能从狄俄尼索斯那里得到笑脸。

这样一来队伍变短了，不久以后，艾薇买下了对面的商店，又增加了更多的餐位。这就是流水线的由来。将那些具有重复性的工作分割成几个串行部分，使工作在工人们中间移动，每个熟练工人只需要依次将自己负责的工作做好就可以了。虽然每位顾客等待服务的总时间没变，但是同时有4位顾客接受服务，这样在集市日的午餐时段里能够照顾的顾客数增加了3倍。

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 ptrds:[ebx+40DA44]

对应的机器代码是：038344DA4000

注意，Intel处理器是以小尾方式排列的，数据的高位对应内存的高地址，低位对应内存的低地址。

第1步，取指令，得到第1个十六进制字节0x03，并且eip加1。

第2步，译码得知这个指令是个加法，但是信息不够，先把上次取到的机器码放入处理器的指令队列缓存中。

第3步，取指令，得到第2个十六进制字节0x83。机器码放入处理器的指令队列缓存中，eip加1。

第4步，译码得知这个指令是寄存器相对寻址方式的加法，而且参与寻址的寄存器是ebx，存放目标是eax，其后还跟着4字节的偏移量，这样指令长度也确定了。机器码放入处理器的指令队列缓存中。

第5步[2]，取地址，得到第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公司从i486处理器开始引入了流水线的机制。

引入流水线机制以后，在第一条流水线执行mov eax, 92492493h的过程中，第二条流水线可以开始对004010AF进行读取和译码。这样并行处理提高了处理器的工作效率。

对于流水线的设计，不同的厂商有不同的设计理念。比如Intel的长流水线设计，把每条指令划分为很多阶段（执行步骤），使得每个步骤的工作内容都很简单，更容易设计电路，加快工作效率，因此Intel的处理器的主频较高。但是这样也有缺点，举例说明，如果执行的指令变成如下所示。

00401063 jmp [00401000h]
00401069 add  esp,8

那么，按长流水线设计的处理器使A流水线先取得00401063的指令，然后开始译码等步骤，这时候B流水线开始工作，按部就班去00401069处取指令，也开始译码等步骤。当A流水线译码完成，知道这是个jmp指令，意识到B流水线取指令错误了，就需要立刻停止B流水线的工作，定位新地址，从取指令开始重新工作。有些时候甚至需要回滚操作，清除B流水线执行错误带来的影响（流水线冲洗）。由于长流水线设计步骤较多，会导致发生错误后损失较大。

相对Intel的长流水线设计，ARM的设计理念是多流水线设计，即为每条指令划分较少的工作阶段，但是流水线数量较多。这样一来，并行程度更高了，而且由于流水线的工作步骤少，弥补错误会更及时，错误的影响也较少。当然这样的设计也有缺点，同样的指令，由于划分的工作阶段少，每个阶段做的事情多了，电路设计就会较为复杂，主频会受到限制，同时由于流水线数量较多，处理器对流水线的管理成本也增大了。

3. 注意事项

明白流水线的设计初衷后，我们接下来探讨影响流水线工作的一些禁忌，了解编译器在这方面的工作。

（1）指令相关性

对于顺序安排的两条指令，后一条指令的执行依赖前一条指令的硬件资源，这样的情况就是指令相关，如下面的代码所示。

add edx,
esi
sar edx, 2

由于以上两条代码都需要访问并设置edx，因此只能在执行完add edx, esi后才能执行sar edx, 2。这样会导致寄存器的争用，影响并行效率，应尽量避免。

（2）地址相关性

对于顺序安排的两条指令，前一条指令需要访问并回写到某一地址上，而后一条指令也需要访问这一地址，这样的情况就是地址相关，如下面的代码所示。

add [00401234],esi
mov eax,[00401234]

由于第一条指令计算并回写到[00401234]，而第二条指令也需要访问[00401234]，形成了对内存地址的争用，因此只能在第一条指令操作完成后再去执行第二条，这同样影响了并行效率，应尽量避免。

由C++的02选项生成的代码会考虑流水线执行的工作方式，如以下代码所示。

0040101F pusheax
00401020 push offset aN; "n/ 2 =%d"
00401025 call_printf
0040102A mov eax,92492493h
0040102F add esp,8
00401032 imulesi
00401034 add edx,esi
00401036 sar edx,2
00401039 mov eax,edx
0040103B shr eax,1Fh
0040103E add edx,eax

00401025处的call_printf是C语言的调用方式，由调用方恢复栈顶，指令是0040102F处的add esp，8，中间有mov eax，92492493h指令，这就是典型的流水线优化。因为mov eax，92492493h和00401032处的imul esi存在指令相关性，mov eax，92492493h需要设置eax，而imul指令也是把计算结果的低位设置到eax。由于存在寄存器争用的问题，这两条指令是无法并行的，因此，编译器在不影响程序结果的前提下，将mov eax，92492493h安排到add esp，8之上了，二者没有任何相关性，能同时执行。但是，流水线优化的前提条件是不影响计算结果，请看00401034处的add edx, esi和00401036处的sar edx，2这两条指令，都需要设置edx，所以无法并行，为了保证计算结果正确，不能改变执行顺序，编译器只能放弃流水线优化了。

4.4.2　分支优化规则

引入流水线工作机制后，为了配合流水线工作，处理器增加了一个分支目标缓冲器（Branch TargetBuffer）。在流水线工作模式下，如果遇到分支结构，就可以利用分支目标缓冲器预测并读取指令的目标地址。分支目标缓冲器在程序运行时将动态记录和调整转移指令的目标地址，可以记录多个地址，对其进行表格化管理。当发生转移时，如果分支目标缓冲器中有记录，下一条指令在取指令阶段就会将其作为目标地址。如果记录地址等于实际目标地址，则并行成功；如果记录地址不等于实际目标地址，则流水线被冲洗。同一个分支，多次预测失败，则更新记录的目标地址。因此，分支预测属于“经验主义”或“机会主义”，存在一定的误测。

基于上述原因，大家以后在编写多重循环时应该把大循环放到内层，这样可以增加分支预测的准确度，如下面的示例所示。

for (int i = 0; i < 10; i++){
  // 下面每次循环会预测成功9999次
  // 第1次没有预测，最后退出循环时预测失败1次
  // 这样的过程重复10次
  for (int j = 0; j < 10000;
    j++){ a[i][j]++;
  }
}

for (int j = 0; j < 10000; j++){
  // 下面每次循环会预测成功9次
  // 第1次没有预测，最后退出循环时预测失败1次
  // 这样的过程重复10000次
  for (int i = 0; i < 10;
    i++){ a[i][j]++;
  }
}

想想看，上述两种方式哪个划算？

编译器对分支的优化主要体现在减少分支结构上，使用顺序结构代替分支结构，相关知识请参考4.2.3节。关于使用查表法代替多分支结构的相关知识，请参考5.4节。

4.4.3　高速缓存优化规则

我们都知道，计算机内存的访问效率大大低于处理器，而且在程序的运行中，被访问的数据和指令相对集中，为此处理器准备了片上高速缓存（cache）存放需要经常访问的数据和代码。这些数据的内容和所在的虚拟地址（Virtual Address，VA）以表格的形式一一对应，在处理器访问内存数据时，先去高速缓存中看看这个虚拟地址有没有记录，如果有，则命中（cachehit），无须访问内存单元；如果没有找到（cachemiss），则转换虚拟地址的访问数据，并保存到高速缓存中。通常，高速缓存不仅会读取指令需要的数据，还会读取这个地址附近的数据。为了节省高速缓存的宝贵空间，VA值的二进制低位不会被保存，也就是说保存的数据是以2n字节为单位的，VA值具体会被保存多少位是由高速缓存设计的数据组织方式确定的。

由于现代操作系统的内存管理是分段加分页的管理模式，而页级管理是虚拟内存的基础，为了避免频繁访问三级页表转换地址，处理器准备了页表缓冲（Translation Lookaside Buffer，TLB）存放长期命中的页表数据。需要访问虚拟内存时，处理器会先去TLB查询是否命中，如果命中则直接查询TLB表中对应的物理地址。对于虚拟内存的管理，长期没有命中的分页会被交换到磁盘上，下次访问时会触发缺页中断，中断处理程序会把磁盘数据读回RAM。

基于以上设计，高速缓存优化有以下几个特点。

1. 数据对齐

高速缓存不会保存虚拟地址的二进制低位，对于Intel的32位处理器来说，如果访问的地址是4的倍数，则可以直接查询并提取；如果不是4的倍数，则需要访问多次。因此，VC++编译器在设置变量地址时会按照4字节边界对齐。

2. 数据集中

将访问次数多的数据或代码尽量安排在一起，一方面是高速缓存在抓取命中数据时会抓取周围的其他数据；另一方面是虚拟内存分页的问题，如果数据分散，保留到多个分页中，就会导致过多的虚拟地址转换，甚至会导致缺页中断频繁发生，这些都会影响效率。

3. 减少体积

命中率高的代码段应减少体积，尽量放入高速缓存中，以提高效率。

如果读者对与32位处理器相关的知识意犹未尽，可以阅读《80x86汇编语言程序设计教程》（作者：杨季文）一书，该书对保护模式下的开发讲解得很细致。

[1]节选自百度百科。

[2]对于CISC指令集，指令长度是可变的，所以CPU工作时需要按字节取得指令，然后译码。如果译码后得知后面是地址，可以直接以4字节的方式取地址。但是，这样又会导致流水线工作处于等待状态，因为只有在译码后才能取得后面的内容。因此，不同的CPU设计结构解决这个问题的方式都可能不一样。

上一章目录下一章