c - 为什么 GCC 在实现整数除法时使用乘以一个奇怪的数字？

Question

我一直在阅读有关 div 和 mul 汇编操作的内容，因此我决定通过用 C 语言编写一个简单的程序来了解它们的实际应用:

文件分割.c

#include <stdlib.h>
#include <stdio.h>

int main()
{
    size_t i = 9;
    size_t j = i / 5;
    printf("%zu\n",j);
    return 0;
}

然后生成汇编语言代码:

gcc -S division.c -O0 -masm=intel

但是查看生成的 division.s 文件，它不包含任何 div 操作!相反，它使用位移位和魔数(Magic Number)来执行某种黑魔法。下面是计算 i/5 的代码片段:

mov     rax, QWORD PTR [rbp-16]   ; Move i (=9) to RAX
movabs  rdx, -3689348814741910323 ; Move some magic number to RDX (?)
mul     rdx                       ; Multiply 9 by magic number
mov     rax, rdx                  ; Take only the upper 64 bits of the result
shr     rax, 2                    ; Shift these bits 2 places to the right (?)
mov     QWORD PTR [rbp-8], rax    ; Magically, RAX contains 9/5=1 now, 
                                  ; so we can assign it to j

这是怎么回事？为什么 GCC 根本不使用 div？它是如何生成这个魔数(Magic Number)的，为什么一切正常？

Answer 1

整数除法是您可以在现代处理器上执行的最慢的算术运算之一，延迟高达几十个周期并且吞吐量很差。 (对于 x86，请参阅 Agner Fog's instruction tables and microarch guide )。

如果您提前知道除数，则可以通过将其替换为一组具有等效效果的其他运算(乘法、加法和移位)来避免除法。即使需要多个运算，它通常仍然比整数除法本身快很多。

以这种方式实现 C / 运算符而不是使用涉及 div 的多指令序列只是 GCC 按常量进行除法的默认方式。它不需要跨操作优化，甚至在调试时也不会改变任何东西。 (不过，对小代码量使用 -Os 确实会让 GCC 使用 div。)使用乘法逆而不是除法就像使用 lea代替 mul 和 add

因此，如果除数在编译时未知，您只会在输出中看到 div 或 idiv。

有关编译器如何生成这些序列的信息，以及让您自己生成它们的代码(几乎肯定是不必要的，除非您使用的是脑死亡编译器)，请参阅 libdivide .