除法函数背后的优化细节

代码片段

​ 以下是一段很简单的函数，对传入的参数进行 除以8 的操作：

long arith(long a) {
	return a / 8;
}

gcc -S test.c编译后对应的汇编代码如下：

	.file	"t.c"
	.text
	.globl	arith
	.type	arith, @function
arith:
.LFB0:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, -8(%rbp)
	movq	-8(%rbp), %rax
	leaq	7(%rax), %rdx
	testq	%rax, %rax
	cmovs	%rdx, %rax
	sarq	$3, %rax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	arith, .-arith
	.ident	"GCC: (Debian 8.3.0-6) 8.3.0"
	.section	.note.GNU-stack,"",@progbits

​ 真正与函数 arith 对应的汇编代码很好找，只是一行 C 代码，编译后有 10 行汇编指令，下面逐行分析指令后面的意义。

栈指针保存

pushq	%rbp
movq	%rsp, %rbp

​ 首先两条指令是对栈底指针 rbp 的保存，并且将当前的栈顶指针 rsp 设置为当前的栈底。rbp 是一个被调用者保存的寄存器，所以需要被调用者去处理，最后在函数完成退栈的时候恢复 (popq %rbp) 。rsp 与 rbp 配合使用，标记函数调用栈帧之间的边界。

保存函数参数与加载参数

movq	%rdi, -8(%rbp)
movq	-8(%rbp), %rax

​ rdi 寄存器在函数调用的时候代表的是第一个参数，指令的意思是将第一个参数保存至 栈底指针位置 - 8 的内存处，也就是将参数入栈。为什么是 -8 呢，因为 x86/64 内存是从高到低增长的。随后是一条加载指令，将刚刚保存在栈上的参数重新加载到 rax 寄存器。

移位优化除法运算

leaq	7(%rax), %rdx
testq	%rax, %rax
cmovs	%rdx, %rax
sarq	$3, %rax

​ leaq 7(%rax), %rdx 将 rax + 7 并将值传递到 rdx 寄存器；随后 testq %rax, %rax 指令会设置条件寄存器，配合条件传输指令 comvs %rdx, %rax 实现的效果是：如果 rax < 0，那么 rax = rdx，即 rax + 7。随后是一个算术右移计算 sarq $3, %rax。处以8 用移位 >>3 运算代替，这个很容易理解，但是为什么在移位之前需要做一个 +7 的操作呢？

​ 首先回顾一下整数除法的定义，如果一个数不能被整除，向靠近 0 的数值舍入。比如 15/8 = 1，这个例子转换成二进制右移就是 1111 >> 3 = 0001 ，低位的 111舍去了。但是对于负数（byte，方便展示）来说，-15/8 = -1，对应的二进制逻辑右移是 1111 0001 >> 3 = 1111 1110(-2) ，结果是向偏离 0 的方向舍入了，需要在这个结果上 +1，才能得到除法定义的结果。如何才能 +1 呢，答案就是在执行逻辑右移前 +7 = +0111，也就是原被除数的低 3 位，只要任意一个位为 1，那么在 +7 后都可以让低 4 位进1，即在最后的结果中 +1。等等，这样处理不会让结果变大吗？答案是不会，因为 低3位 在逻辑右移的过程中已经被抹去了。另外一个问题又出现了，正数的情况呢？这就是 cmovs %rdx, %rax 条件传输指令起到的作用，只有负数的情况才会对被除数做偏置处理（biasing）。扩展开来，也就是负数需要用移位代替除法，需要加上 (2^x)-1) 的偏置值。

​ 这里还有一个点就是，为什么负数逻辑右移后会向远离 0 的方向舍入？这个问题可以从补码的定义上理解。假设一个 byte a = -127，二进制补码表示是：1000 0001 ，大学刚学数电的时候一直搞不清补码如何转换成 10 进制的真实值，后来在 CSAPP 中看到这个定义，豁然开朗。即：最高位看成是符号为 负 的权重位。所以负数逻辑右移过程中丢弃的都是正数位的有效值，那么它的结果往远离 0 的方向偏移（即变小）。而加上 (2^x)-1) 的偏置值，可以将丢弃的正低位进位，来达到向 0 靠近的效果。

​ 正数的右移一位效果等于除以2很好理解：高位补0，每个有效位都变成 1/2，最终的结果就是除以2。负数的表示是补码，右移的逻辑没有那么清晰。上面说到，负数的补码可以这么理解，最高位的 1 看成是对应 -2^x 的负数值，其余的位当成正常的值看，将以上值全部加起来，就是对应的 -n。反过来说，这个 n 直接就是补码所有 0 所在位的值累加，再加上1。而算数右移高位是补1的，可以看成是所有的 0 向右移动了位置，即所有累加的值 / 2，再加上上面说的偏置值，就可以用算数右移取代除法操作了。

条件传输指令

​ 上一段讲到只有负数的情况，才会将被除数做 +7 操作，但是汇编代码并没有类似 if-else 的逻辑，而是用条件传输指令 cmovs %rdx, %rax 代替。

​ 这是因为现代处理器高度依赖于 pipeline ，取指，译码，读内存，逻辑运算，写内存，更新程序计数器都是在在流水线中重叠连续的，一旦发生条件跳转并且分支预测失败，那么需要丢弃该跳转之后所有指令已经做的工作，也就是分支预测错误惩罚，浪费 15~30 个时钟周期。所以在上述情况下，因为两个分支的计算都很简单，编译器选择将两个分支的计算结果都保存起来（实际上是计算 1 个），通过条件传输指令替代条件跳转指令进行优化。

其他

​ 其实这段编译出来的代码，栈指针保存，保存函数参数都不是必须的，只是在默认编译参数下编译才会有，如果我们用 gcc -S -Og test.c 参数，编译出来的代码会更加紧凑，如下：

	.file	"t.c"
	.text
	.globl	arith
	.type	arith, @function
arith:
.LFB0:
	.cfi_startproc
	leaq	7(%rdi), %rax
	testq	%rdi, %rdi
	cmovns	%rdi, %rax
	sarq	$3, %rax
	ret
	.cfi_endproc
.LFE0:
	.size	arith, .-arith
	.ident	"GCC: (Debian 8.3.0-6) 8.3.0"
	.section	.note.GNU-stack,"",@progbits

参考文献

Computer Systems: A Programmer’s Perspective, 3/E (CS:APP3e)