gcc - 模(%)的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的计算:基本思想是用乘以1/10代替除以10。编译器通过乘以 (2**35/10 + 1) 来对此进行定点近似 - 这是加载到 edx 中的魔法值，尽管它是作为有符号值输出的，即使它实际上是无符号的 - 并将结果右移 35。结果证明为所有 32 位整数都提供了正确的结果。

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

最后备注:如果您想实际看到 GCC 计算模数，请设置除数变量(例如函数参数)，这样它就不能进行这种优化。无论如何，在 x86 上，您使用 div 计算模数. div预计 edx:eax 中的 64 位红利(edx 中的高 32 位，eax 中的低 32 位 - 如果您使用的是 32 位数字，则将 edx 清除为零)并将其除以您指定的任何操作数(例如 div ebx 除 edx:eax 除以 ebx )。它返回 eax 中的商余数在 edx . idiv对有符号值也一样。