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

Question

我一直在读div和mul汇编操作,我决定用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操作！取而代之的是，它使用比特移动和魔法数字来执行某种黑魔法。下面是计算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？它是如何产生这个神奇的数字的，为什么一切都起作用？

Answer 1

整数除法是在现代处理器上可以执行的最慢的算术运算之一，延迟可达几十个周期，吞吐量也很差。（对于x86，请参阅Agner Fog的说明表和微拱形指南）。

如果您提前知道除数，那么您可以通过用一组具有同等作用的其他操作（乘法、加法和移位）替换它来避免除法。即使需要几次运算，它仍然比整数除法本身要快得多。

以这种方式实现C/运算符，而不是使用包含div的多指令序列，这正是GCC按常量除法的默认方式。它不需要跨操作进行优化，即使是调试也不会更改任何内容。（但是，对于较小的代码大小使用-os会使GCC使用div)使用乘法逆代替除法就像使用lea代替mul和add

因此，只有在编译时不知道除数的情况下，您才倾向于在输出中看到div或idiv。

有关编译器如何生成这些序列的信息，以及允许您为自己生成这些序列的代码（除非使用Brainead编译器，否则几乎肯定是不必要的），请参见libdivide。