Linux汇编之分支优化

心不留意外尘 2016-07-08

展开全文

http:///linux-asm-optimized-branch/

2015 枫竹梦

分支指令对程序的性能有较大的影响，大多数现代的处理器利用指令预取缓存提高性能。而在程序运行时，指令预取缓存被填充上顺序指令。乱序引擎试图尽可能快地执行指令，即使程序前面的指令还没有执行。但是，分支指令对乱序引擎有严重的影响。本文中枫竹梦介绍在Linux汇编语言(ASM)中如何改进汇编语言的性能。

分支预测

在遇到分支指令时，处理器的乱序引擎必须确定要处理的下一条指令。乱序引擎单元利用称为分支预测前端(branch prediction front end)的独立单元确定是否应该跳转该分支。

无条件分支

对于无条件分支，确定下一条指令是简单的。但是跳转的距离有多远，下一条指令是否在缓存中，是不一定的。

在确定下一条指令的位置时，乱序引擎必须确定指令在预取缓存中是否存在。如果不存在就要清空缓存，然后从新的位置重新加载指令。这对应用程序的性能而言代价很高。

条件分支

条件分支给处理器提出了更大的挑战。对于每一个条件分支，分支预测单元必须确定是否采用分支。通常在乱序引擎执行指令时，没有充分的充分的条件确定采用哪个分支。乱序引擎采用分支预测的方式确定执行的分支。使用规则和学习的历史来实现。主要有以下3个规则：

假设会采用后向分支
假设不会采用向前分支
以前曾经采用过的分支会再次采用

使用一般的程序设计逻辑，最常用的向后分支(跳转到前面的指令码的分支)是在循环中使用的。如：

movl $100, %ecx
loop1:
addl %cx, %eax
decl %ecx
jns loop1

执行下一条指令中有一次，即退出循环。跳转回loop1执行100次。也就是说在总计101次的预测中只有1次是错误的。

对前向分支处理会困难一些。分支预测算法假设多数情况下分支不会采用向前的方向。在程序设计逻辑中，假设紧跟在跳转指令后面的代码最可能被执行，而不是跳转到代码的其他位置。从下面的代码中可以观察到这一点：

movl -12(%ebp), %eax
cmpl -8(%ebp), %eax
jle .L2
movl -12(%ebp), %eax
movl %eax, 4(%esp)
movl $.LC0, (%esp)
call printf
jmp .L4
.L2:
movl -8(%ebp), %eax
movl %eax, 4(%esp)
movl $.LC0, (%esp)
call printf

这是在模仿高级语言分支一文中对C程序if语句汇编的部分代码。JLE指令后面的代码处理if语句的then部分。从分支预测的角度来看，汇编预测if语句的then部分比else部分更可能被执行，从而试图优化代码。

第3条规则暗示，执行了多次的分支在多数情况下可能采用相同的路径。分支目标缓冲区(Branch Target Buffer, BTB)跟踪处理器执行的每个分支指令，分支的结果存储在缓冲区区域中。BTB信息高于分支的前两个规则。如果第一次遇到分支时，没有采用向后的方向，分支预测单元就会假设任何后续分支都不会采用向后方向，而不是假设会应用向后分支的规则。BTB的问题在于它可能会充满，这会使分支结果花费更长时间。

优化技巧

处理器尽其最大的努力优化分支，也可以在汇编语言程序中使用几个技巧来帮助处理器。

消除分支

解决分支性能问题的最显而易见的方式是尽可能消除分支的使用。如条件传送指令的使用。

有时候重复几个额外指令能够消除跳转。这种小的指令开销将容易地适合指令预取缓存，并且补偿跳转本身造成的性能影响。如：

loop:
cmpl data(, %edi, 4), %eax
je part2
call function1
jmp looptest
part2:
call function2
looptest:
inc %edi
cmpl $10, $edi
jnz loop

根据从data数组读出的值，循环调用两个函数之一。调用函数后，跳转到循环的末尾，递增数组的下标值并且返回循环的开始。每次执行第个函数时，都要使用JMP指令进行向前跳转。因为前向分支预测不会采用它，这对性能有一定的影响。修改代码如下：

loop:
cmpl data(, %edi, 4), %eax
je part2
call function1
inc %edi
cmpl $10, $edi
jnz loop
jmp end
part2:
call function2
inc %edi
cmpl $10, $edi
jnz loop
end:

在循环内不使用向前分支，相比之前消除了向前分支。