优化汇编指令 (三)
zenglong 2014-06-02 16:56:48
除了上一节提到的循环结构外，if...else...之类的条件选择语句也需要进行优化，因为if...else...语句生成的汇编指令中的jle之类的条件跳转指令，会让处理器的指令预取缓存措施大打折扣...
本文由zengl.com站长对汇编教程英文版相应章节进行翻译得来。
汇编教程英文版的下载地址：点此进入原百度盘 ， 点此进入Dropbox网盘 ， 点此进入Google Drive (Dropbox与Google Drive里是Assembly_Language.pdf文档)
另外再附加一个英特尔英文手册的共享链接地址：
点此进入原百度盘， 点此进入Dropbox网盘 ，点此进入Google Drive (在某些例子中会用到，Dropbox与Google Drive里是intel_manual.pdf文档)
本篇翻译对应汇编教程英文原著的第473页到第483页，目前翻译完前15章 (注意这里的页数不是页脚的页数，而是pdf电子档顶部，分页输入框中的页数，也就是包含了目录，前言部分的总页数，pdf电子档总页数是577，当前已翻译完的页数为483 / 577)。
Optimizing conditional branches 优化条件分支指令：
除了上一节提到的循环结构外，if...else...之类的条件选择语句也需要进行优化，因为if...else...语句生成的汇编指令中的jle之类的条件跳转指令，会让处理器的指令预取缓存措施大打折扣。
在之前的"汇编流程控制 (三) 流程控制结束篇"里，我们介绍过，if...else...语句的通用汇编模板如下：
上面模板中当if条件判断为false时，就通过jxx指令(jxx中的xx是通配符，可以是jge , jle等等)跳转到else标签处执行else代码块，如果条件判断为true，则不跳转，直接执行then部分的语句也就是if代码块。
如果if条件判断部分有多条语句的话，就需要用到多个cmp和jxx指令，如下面这个pascal语言中的if例子：
对应的汇编代码如下：
上面的汇编代码中通过两个cmp指令和jg , jne指令对if....then之间的逻辑或运算分别作了判断，当EBX大于EAX时，就直接跳到then标签处，否则继续比较EAX和ECX，若 EAX和ECX不相等，则jne就跳转到else部分，如果相等则执行then部分。
下面我们还是通过具体的例子来说明非优化与优化两种情况下，if...else...之类的条件选择语句所生成的汇编代码的区别。
Viewing if-then code 查看if条件选择语句在非优化时所生成的汇编代码：
我们用下面的condtest.c程式来进行演示说明：
上面的代码中，定义了一个conditiontest函数，在该函数里，就使用了if...else if...else多条件选择语句，来对test1与test2两个参数进行大小比较，并将较大的参数作为结果返回，如果test1与test2相等，则结果返回0 。
同样的，我们先使用gcc -S来生成非优化版的汇编代码：
从上面的输出可以看到，conditiontest函数里和if...else if...else...多条件选择语句相关的汇编代码如下：
上面的汇编代码中，8(%ebp)对应conditiontest函数里的test1参数，12(%ebp)对应test2参数，-4(%ebp)对应result局部变量，如果test1大于test2则jle .L2指令就不会发生跳转，继续通过mov指令将test1的值设置到result局部变量，再通过jmp .L3指令跳转到函数的结束位置，并由movl -4(%ebp), %eax指令将result的值赋值给EAX，作为结果返回。当test1小于或等于test2时，则jle .L2指令就会跳转到.L2处，该处又会对test1和test2进行比较，如果test2大于test1，则jge .L4就不会跳转，而是继续执行，将test2的值设置到result变量，并通过jmp .L3跳转到函数结束位置。如果test2小于或等于test1，则jpe .L4就会跳转到.L4的位置，并将result变量设置为0 。
从上面的分析可以看到，为了完成if...else if...else的条件选择语句，汇编代码里使用了多个cmp和jle之类的条件跳转指令，这些条件跳转指令，会对处理器的指令预取缓存机制产生一定的消极影响，尤其是当处理器的分支预测不准时，处理器就需要重新去加载新的跳转位置处的指令，从而会在一定程度上降低程序的执行性能。
对这类汇编代码进行优化时，主要是对条件跳转指令进行优化，通过调整汇编代码顺序，来去掉不必要的跳转指令，并尽量用cmov之类的条件传值指令来代替。
Optimized If-Then Code 生成优化版的汇编代码：
下面我们用gcc的-O3选项来生成优化版的汇编代码：
从上面输出中，可以看到，和conditiontest函数里if...else if...else相关的汇编代码如下：
同样的，上面代码中的8(%ebp)对应test1参数，12(%ebp)对应test2参数，代码里先通过movl 12(%ebp), %edx将test2的值设置到EDX，并通过movl 8(%ebp), %eax将test1的值设置到EAX，然后使用cmpl %edx, %eax指令，当EAX大于EDX时，后面的jg .L2指令就会跳转到.L2处，这样EAX里的test1值就可以直接作为结果返回。当EAX小于或等于EDX时，jg .L2指令就不会发生跳转，而是继续执行movl $0, %eax的指令，从而将EAX先设置为0，接着用cmovl条件传值指令来判断EDX与EAX的大小，当EAX小于EDX时，cmovl指令就会将EDX里的test2的值传值给EAX，当EAX等于EDX时，cmovl指令就不会发生传值操作，这样EAX就会以0值返回。
上面汇编代码通过使用cmovl条件传值指令，去掉了不必要的条件跳转指令，让整个函数的汇编代码都得到了简化，有效的提高了程序的执行性能。cmov条件传值指令的用法可以参考之前的"Moving Data 汇编数据移动 (二)"文章里的内容。
Common subexpression elimination 公共子表达式消除技术：
Common subexpression elimination(公共子表达式消除技术，简写为cse)是编译器使用的一项比较先进的优化技术，该技术会对整个汇编代码进行扫描，当编译器发现比较常用的表达式时，例如：a * b的表达式在汇编代码里出现了多次时，就只会对a * b计算一次，并将计算的结果保存起来，其他的地方出现a * b时，就直接使用之前保存的结果，而不需要再计算一遍，从而可以提高程序的运行速度。
下面就通过例子来进行说明。
A program example 代码示例：
上面的funct1函数里用到了三次a * b的表达式，我们先用gcc -S得到非优化版的汇编代码：
从上面的输出可以看到，每个a * b的表达式，都执行了一次类似imull 12(%ebp), %eax的乘法操作。
上面代码中，比较有意思的地方是变量d的计算，d = (a * b) / 5里存在除法运算，但是汇编代码里并没有使用div除法指令来完成除法运算，而是使用imul乘法指令和sar之类的移位指令来完成除以5的运算，这是因为div之类的除法指令是很耗时的指令，比乘法指令占用更多的时钟周期。
但是上面的imul和sar的算法有点不太好理解，movl $1717986919, %edx指令中的1717986919近似的等于2^33 / 5即2的33次方除以5 ，其大致的算法原理图如下：
图1
上图为了将(a * b) / 5转为乘法和移位运算，就先假设上图中的第一个等式成立，在等式成立的情况下，我们可以得出edx的初始值来，有了edx的初始值，那么汇编代码里，只需用imul指令将(a * b)与edx的初始值相乘，由于imul乘法运算的结果是存储在EDX : EAX的寄存器对里的，EDX存储高32位部分，因此，EDX就等于上图的(a * b) * edx / 2^32部分，然后再用sarl %edx移位指令就可以得到EDX / 2的值，也就计算出图中第一个等式右侧的值，右侧的值出来后，(a * b) / 5的值也就出来了(左右两侧的值相等)。
至于后面的sarl $31, %eax指令是为了能得到(a * b)的符号位，然后用subl %eax, %ecx指令减去符号位来得出最终的除法运算的结果。
更详细的数学原理(包括精度，溢出等方面的控制)以及为何要计算符号位的原因，请参考 http://reverseengineering.stackexchange.com/questions/1397/how-can-i-reverse-optimized-integer-division-modulo-by-constant-operations 该链接里的文章。
可以看出来，非优化的汇编代码中，所有(a * b)的表达式都会被计算一次，即便这些表达式计算的结果在本例中都是一样的。接下来看下优化后的汇编代码又会如何。
Optimizing with cse 使用cse技术优化汇编代码：
我们给gcc添加-O3选项来查看优化后的汇编代码：
从上面的输出可以看到，汇编代码里只使用了一次imull 8(%ebp), %ecx指令来计算(a * b)的值，并将该值存储在ECX里，后面在计算变量d和e时，就不会再去计算(a * b)了，而是直接从ECX里获取之前计算过的值，从而有效的简化了imul指令，提高了程序的执行速度。
以后就是和优化有关的内容。剩下的是一些原著第15章的总结部分，限于篇幅就不多说了。
下一篇介绍如何在汇编里使用文件。
OK，就到这里，休息，休息一下 o(∩_∩)o~~
汇编教程英文版的下载地址：点此进入原百度盘 ， 点此进入Dropbox网盘 ， 点此进入Google Drive (Dropbox与Google Drive里是Assembly_Language.pdf文档)
另外再附加一个英特尔英文手册的共享链接地址：
点此进入原百度盘， 点此进入Dropbox网盘 ，点此进入Google Drive (在某些例子中会用到，Dropbox与Google Drive里是intel_manual.pdf文档)
本篇翻译对应汇编教程英文原著的第473页到第483页，目前翻译完前15章 (注意这里的页数不是页脚的页数，而是pdf电子档顶部，分页输入框中的页数，也就是包含了目录，前言部分的总页数，pdf电子档总页数是577，当前已翻译完的页数为483 / 577)。
Optimizing conditional branches 优化条件分支指令：
除了上一节提到的循环结构外，if...else...之类的条件选择语句也需要进行优化，因为if...else...语句生成的汇编指令中的jle之类的条件跳转指令，会让处理器的指令预取缓存措施大打折扣。
在之前的"汇编流程控制 (三) 流程控制结束篇"里，我们介绍过，if...else...语句的通用汇编模板如下：
if:
<condition to evaluate>
jxx else ; jump to the else part if the condition is false
<code to implement the "then" statements>
jmp end ;jump to the end
else:
< code to implement the "else" statements>
end:
|
上面模板中当if条件判断为false时，就通过jxx指令(jxx中的xx是通配符，可以是jge , jle等等)跳转到else标签处执行else代码块，如果条件判断为true，则不跳转，直接执行then部分的语句也就是if代码块。
如果if条件判断部分有多条语句的话，就需要用到多个cmp和jxx指令，如下面这个pascal语言中的if例子：
|
if (eax < ebx) || (eax == ecx) then < then logic code> else < else logic code > |
对应的汇编代码如下：
|
if: cmpl %eax, %ebx jg then cmpl %eax, %ecx jne else then: < then logic code> jmp end else: < else logic code > end: |
上面的汇编代码中通过两个cmp指令和jg , jne指令对if....then之间的逻辑或运算分别作了判断，当EBX大于EAX时，就直接跳到then标签处，否则继续比较EAX和ECX，若 EAX和ECX不相等，则jne就跳转到else部分，如果相等则执行then部分。
下面我们还是通过具体的例子来说明非优化与优化两种情况下，if...else...之类的条件选择语句所生成的汇编代码的区别。
Viewing if-then code 查看if条件选择语句在非优化时所生成的汇编代码：
我们用下面的condtest.c程式来进行演示说明：
/* condtest.c - An example of optimizing if-then code */
#include <stdio.h>
int conditiontest(int test1, int test2)
{
int result;
if (test1 > test2)
{
result = test1;
}
else if (test1 < test2)
{
result = test2;
}
else
{
result = 0;
}
return result;
}
int main()
{
int data1 = 10;
int data2 = 30;
printf("The result is %d\n", conditiontest(data1, data2));
return 0;
}
|
上面的代码中，定义了一个conditiontest函数，在该函数里，就使用了if...else if...else多条件选择语句，来对test1与test2两个参数进行大小比较，并将较大的参数作为结果返回，如果test1与test2相等，则结果返回0 。
同样的，我们先使用gcc -S来生成非优化版的汇编代码：
$ gcc -S condtest.c $ cat condtest.s .file "condtest.c" .text .globl conditiontest .type conditiontest, @function conditiontest: pushl %ebp movl %esp, %ebp subl $16, %esp movl 8(%ebp), %eax cmpl 12(%ebp), %eax jle .L2 movl 8(%ebp), %eax movl %eax, -4(%ebp) jmp .L3 .L2: movl 8(%ebp), %eax cmpl 12(%ebp), %eax jge .L4 movl 12(%ebp), %eax movl %eax, -4(%ebp) jmp .L3 .L4: movl $0, -4(%ebp) .L3: movl -4(%ebp), %eax leave ret .size conditiontest, .-conditiontest .section .rodata .LC0: .string "The result is %d\n" .text .globl main .type main, @function main: pushl %ebp movl %esp, %ebp andl $-16, %esp subl $32, %esp movl $10, 28(%esp) movl $30, 24(%esp) movl 24(%esp), %eax movl %eax, 4(%esp) movl 28(%esp), %eax movl %eax, (%esp) call conditiontest movl $.LC0, %edx movl %eax, 4(%esp) movl %edx, (%esp) call printf movl $0, %eax leave ret .size main, .-main .ident "GCC: (Ubuntu/Linaro 4.5.3-12ubuntu2) 4.5.3" .section .note.GNU-stack,"",@progbits $ |
从上面的输出可以看到，conditiontest函数里和if...else if...else...多条件选择语句相关的汇编代码如下：
movl 8(%ebp), %eax cmpl 12(%ebp), %eax jle .L2 movl 8(%ebp), %eax movl %eax, -4(%ebp) jmp .L3 .L2: movl 8(%ebp), %eax cmpl 12(%ebp), %eax jge .L4 movl 12(%ebp), %eax movl %eax, -4(%ebp) jmp .L3 .L4: movl $0, -4(%ebp) .L3: movl -4(%ebp), %eax |
上面的汇编代码中，8(%ebp)对应conditiontest函数里的test1参数，12(%ebp)对应test2参数，-4(%ebp)对应result局部变量，如果test1大于test2则jle .L2指令就不会发生跳转，继续通过mov指令将test1的值设置到result局部变量，再通过jmp .L3指令跳转到函数的结束位置，并由movl -4(%ebp), %eax指令将result的值赋值给EAX，作为结果返回。当test1小于或等于test2时，则jle .L2指令就会跳转到.L2处，该处又会对test1和test2进行比较，如果test2大于test1，则jge .L4就不会跳转，而是继续执行，将test2的值设置到result变量，并通过jmp .L3跳转到函数结束位置。如果test2小于或等于test1，则jpe .L4就会跳转到.L4的位置，并将result变量设置为0 。
从上面的分析可以看到，为了完成if...else if...else的条件选择语句，汇编代码里使用了多个cmp和jle之类的条件跳转指令，这些条件跳转指令，会对处理器的指令预取缓存机制产生一定的消极影响，尤其是当处理器的分支预测不准时，处理器就需要重新去加载新的跳转位置处的指令，从而会在一定程度上降低程序的执行性能。
对这类汇编代码进行优化时，主要是对条件跳转指令进行优化，通过调整汇编代码顺序，来去掉不必要的跳转指令，并尽量用cmov之类的条件传值指令来代替。
Optimized If-Then Code 生成优化版的汇编代码：
下面我们用gcc的-O3选项来生成优化版的汇编代码：
$ gcc -O3 -S -o condtest2.s condtest.c $ cat condtest2.s .file "condtest.c" .text .p2align 4,,15 .globl conditiontest .type conditiontest, @function conditiontest: pushl %ebp movl %esp, %ebp movl 12(%ebp), %edx movl 8(%ebp), %eax cmpl %edx, %eax jg .L2 movl $0, %eax cmovl %edx, %eax .L2: popl %ebp ret .size conditiontest, .-conditiontest .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .string "The result is %d\n" .text .p2align 4,,15 .globl main .type main, @function main: pushl %ebp movl %esp, %ebp andl $-16, %esp subl $16, %esp movl $30, 8(%esp) movl $.LC0, 4(%esp) movl $1, (%esp) call __printf_chk xorl %eax, %eax leave ret .size main, .-main .ident "GCC: (Ubuntu/Linaro 4.5.3-12ubuntu2) 4.5.3" .section .note.GNU-stack,"",@progbits $ |
从上面输出中，可以看到，和conditiontest函数里if...else if...else相关的汇编代码如下：
movl 12(%ebp), %edx movl 8(%ebp), %eax cmpl %edx, %eax jg .L2 movl $0, %eax cmovl %edx, %eax .L2: popl %ebp ret |
同样的，上面代码中的8(%ebp)对应test1参数，12(%ebp)对应test2参数，代码里先通过movl 12(%ebp), %edx将test2的值设置到EDX，并通过movl 8(%ebp), %eax将test1的值设置到EAX，然后使用cmpl %edx, %eax指令，当EAX大于EDX时，后面的jg .L2指令就会跳转到.L2处，这样EAX里的test1值就可以直接作为结果返回。当EAX小于或等于EDX时，jg .L2指令就不会发生跳转，而是继续执行movl $0, %eax的指令，从而将EAX先设置为0，接着用cmovl条件传值指令来判断EDX与EAX的大小，当EAX小于EDX时，cmovl指令就会将EDX里的test2的值传值给EAX，当EAX等于EDX时，cmovl指令就不会发生传值操作，这样EAX就会以0值返回。
上面汇编代码通过使用cmovl条件传值指令，去掉了不必要的条件跳转指令，让整个函数的汇编代码都得到了简化，有效的提高了程序的执行性能。cmov条件传值指令的用法可以参考之前的"Moving Data 汇编数据移动 (二)"文章里的内容。
Common subexpression elimination 公共子表达式消除技术：
Common subexpression elimination(公共子表达式消除技术，简写为cse)是编译器使用的一项比较先进的优化技术，该技术会对整个汇编代码进行扫描，当编译器发现比较常用的表达式时，例如：a * b的表达式在汇编代码里出现了多次时，就只会对a * b计算一次，并将计算的结果保存起来，其他的地方出现a * b时，就直接使用之前保存的结果，而不需要再计算一遍，从而可以提高程序的运行速度。
下面就通过例子来进行说明。
A program example 代码示例：
/* csetest.c - An example of implementing cse optimization */ #include <stdio.h> void funct1(int a, int b) { int c = a * b; int d = (a * b) / 5; int e = 500 / (a * b); printf("The results are c=%d d=%d e=%d\n", c, d, e); } int main() { int a = 10; int b = 25; funct1(a, b); funct1(20, 10); return 0; } |
上面的funct1函数里用到了三次a * b的表达式，我们先用gcc -S得到非优化版的汇编代码：
$ gcc -S csetest.c $ cat csetest.s ................................. ................................. funct1: pushl %ebp movl %esp, %ebp subl $56, %esp movl 8(%ebp), %eax imull 12(%ebp), %eax movl %eax, -12(%ebp) movl 8(%ebp), %eax movl %eax, %ecx imull 12(%ebp), %ecx movl $1717986919, %edx movl %ecx, %eax imull %edx sarl %edx movl %ecx, %eax sarl $31, %eax movl %edx, %ecx subl %eax, %ecx movl %ecx, %eax movl %eax, -16(%ebp) movl 8(%ebp), %eax movl %eax, %edx imull 12(%ebp), %edx movl %edx, -28(%ebp) movl $500, %eax movl %eax, %edx sarl $31, %edx idivl -28(%ebp) movl %eax, -20(%ebp) movl $.LC0, %eax movl -20(%ebp), %edx movl %edx, 12(%esp) movl -16(%ebp), %edx movl %edx, 8(%esp) movl -12(%ebp), %edx movl %edx, 4(%esp) movl %eax, (%esp) call printf leave ret ................................. ................................. $ |
从上面的输出可以看到，每个a * b的表达式，都执行了一次类似imull 12(%ebp), %eax的乘法操作。
上面代码中，比较有意思的地方是变量d的计算，d = (a * b) / 5里存在除法运算，但是汇编代码里并没有使用div除法指令来完成除法运算，而是使用imul乘法指令和sar之类的移位指令来完成除以5的运算，这是因为div之类的除法指令是很耗时的指令，比乘法指令占用更多的时钟周期。
但是上面的imul和sar的算法有点不太好理解，movl $1717986919, %edx指令中的1717986919近似的等于2^33 / 5即2的33次方除以5 ，其大致的算法原理图如下：
图1
上图为了将(a * b) / 5转为乘法和移位运算，就先假设上图中的第一个等式成立，在等式成立的情况下，我们可以得出edx的初始值来，有了edx的初始值，那么汇编代码里，只需用imul指令将(a * b)与edx的初始值相乘，由于imul乘法运算的结果是存储在EDX : EAX的寄存器对里的，EDX存储高32位部分，因此，EDX就等于上图的(a * b) * edx / 2^32部分，然后再用sarl %edx移位指令就可以得到EDX / 2的值，也就计算出图中第一个等式右侧的值，右侧的值出来后，(a * b) / 5的值也就出来了(左右两侧的值相等)。
至于后面的sarl $31, %eax指令是为了能得到(a * b)的符号位，然后用subl %eax, %ecx指令减去符号位来得出最终的除法运算的结果。
更详细的数学原理(包括精度，溢出等方面的控制)以及为何要计算符号位的原因，请参考 http://reverseengineering.stackexchange.com/questions/1397/how-can-i-reverse-optimized-integer-division-modulo-by-constant-operations 该链接里的文章。
可以看出来，非优化的汇编代码中，所有(a * b)的表达式都会被计算一次，即便这些表达式计算的结果在本例中都是一样的。接下来看下优化后的汇编代码又会如何。
Optimizing with cse 使用cse技术优化汇编代码：
我们给gcc添加-O3选项来查看优化后的汇编代码：
$ gcc -O3 -S -o csetest2.s csetest.c $ cat csetest2.s ................................ ................................ funct1: pushl %ebp movl $500, %eax movl %esp, %ebp subl $40, %esp movl 12(%ebp), %ecx movl %eax, %edx imull 8(%ebp), %ecx sarl $31, %edx movl $.LC0, 4(%esp) movl $1, (%esp) idivl %ecx movl $1717986919, %edx movl %ecx, 8(%esp) movl %eax, 16(%esp) movl %ecx, %eax imull %edx movl %ecx, %eax sarl $31, %eax sarl %edx subl %eax, %edx movl %edx, 12(%esp) call __printf_chk leave ret ................................ ................................ $ |
从上面的输出可以看到，汇编代码里只使用了一次imull 8(%ebp), %ecx指令来计算(a * b)的值，并将该值存储在ECX里，后面在计算变量d和e时，就不会再去计算(a * b)了，而是直接从ECX里获取之前计算过的值，从而有效的简化了imul指令，提高了程序的执行速度。
以后就是和优化有关的内容。剩下的是一些原著第15章的总结部分，限于篇幅就不多说了。
下一篇介绍如何在汇编里使用文件。
OK，就到这里，休息，休息一下 o(∩_∩)o~~