模数(%)的GCC实现如何工作,为什么不使用div指令？

Question

我试图弄清楚如何在汇编中计算模10,所以我在gcc中编译了以下c代码,看看它是什么产生的.

unsigned int i=999;
unsigned int j=i%10;

令我惊讶的是,我得到了

movl    -4(%ebp), %ecx
movl    $-858993459, %edx
movl    %ecx, %eax
mull    %edx
shrl    $3, %edx
movl    %edx, %eax
sall    $2, %eax
addl    %edx, %eax
addl    %eax, %eax
movl    %ecx, %edx
subl    %eax, %edx
movl    %edx, %eax
movl    %eax, -12(%ebp)

其中-4(%ebp)或"i"是输入,-12(%ebp)或"j"是答案.我已经测试了这个,无论你做出什么数字,它都能正常工作-4(%ebp).

我的问题是这个代码是如何工作的,它比使用div操作数更好.

Answer 1

第二个问题:div是一个非常慢的指令(超过20个时钟周期).上面的序列包含更多指令,但它们都相对较快,所以它在速度方面是一个净赢.

shrl计算i/10 的前五个指令(最多包括)(我将在一分钟内解释).

接下来的几条指令再次将结果乘以10,但避免使用mul/ imul指令(无论这是否胜利取决于您所针对的确切处理器 - 较新的x86具有非常快的乘数,但较旧的乘数不具备).

movl    %edx, %eax   ; eax=i/10
sall    $2, %eax     ; eax=(i/10)*4
addl    %edx, %eax   ; eax=(i/10)*4 + (i/10) = (i/10)*5
addl    %eax, %eax   ; eax=(i/10)*5*2 = (i/10)*10

这是然后从减去i再次获得i - (i/10)*10这i % 10(对于无符号数).

最后,关于i/10的计算:基本思想是将除以10乘以1/10.编译器通过乘以(2**35/10 + 1)来进行定点逼近 - 这是加载的魔法值edx,尽管它输出为有符号值,即使它实际上是无符号的 - 并且右移结果结果为所有32位整数提供了正确的结果.

有确定这种近似的算法可以保证误差小于1(对于整数意味着它是正确的值),而GCC显然使用了一个:)

最后的评论:如果你想实际看到GCC计算模数,可以使用除数变量(例如函数参数),这样它就不能进行这种优化.无论如何,在x86上,你使用计算模数div.div预计在64位被除数edx:eax(EDX中的高32位,EAX中低32位-明确EDX为零,如果你有一个32位数字的工作),并划分,通过什么操作可以指定(例如div ebx分裂edx:eax的ebx).它返回商eax和其余的商edx.idiv对签名值执行相同操作.

Answer 2

第一部分，直到shrl $3, %edx，实现了一个快速整数除以 10。当你被除以的数字是预先知道的时候，有几种不同的算法可以工作。请注意，858993459 是“0.2 * 2^32”。这样做的原因是因为，即使有整数除法指令dividiv指令集中/ ，它通常也很慢，比乘法慢几倍。

第二部分通过将除法结果乘以 10 来计算余数（以间接方式，通过移位和加法；大概编译器认为这样会更快），然后从原始数字中减去它。