为什么GCC在实现整数除法时使用乘以奇怪的数字? [英] Why does GCC use multiplication by a strange number in implementing integer division?

问题描述

我一直在阅读有关 div 和 mul 汇编操作的文章，我决定通过用 C 编写一个简单的程序来看看它们的实际效果:

I've been reading about div and mul assembly operations, and I decided to see them in action by writing a simple program in C:

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

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

然后生成汇编语言代码:

And then generating assembly language code with:

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

但是查看生成的division.s文件，它不包含任何div操作！相反，它通过位移位和幻数执行某种黑魔法.这是计算 i/5 的代码片段:

But looking at generated division.s file, it doesn't contain any div operations! Instead, it does some kind of black magic with bit shifting and magic numbers. Here's a code snippet that computes 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?它是如何生成这个神奇数字的?为什么一切正常?

What's going on here? Why doesn't GCC use div at all? How does it generate this magic number and why does everything work?

推荐答案

整数除法是您可以在现代处理器上执行的最慢的算术运算之一，延迟高达数十个周期，吞吐量也很差.(对于 x86，请参阅 Agner Fog 的指令表和微架构指南).

Integer division is one of the slowest arithmetic operations you can perform on a modern processor, with latency up to the dozens of cycles and bad throughput. (For x86, see Agner Fog's instruction tables and microarch guide).

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

If you know the divisor ahead of time, you can avoid the division by replacing it with a set of other operations (multiplications, additions, and shifts) which have the equivalent effect. Even if several operations are needed, it's often still a heck of a lot faster than the integer division itself.

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

Implementing the C / operator this way instead of with a multi-instruction sequence involving div is just GCC's default way of doing division by constants. It doesn't require optimizing across operations and doesn't change anything even for debugging. (Using -Os for small code size does get GCC to use div, though.) Using a multiplicative inverse instead of division is like using lea instead of mul and add

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

As a result, you only tend to see div or idiv in the output if the divisor isn't known at compile-time.

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

For information on how the compiler generates these sequences, as well as code to let you generate them for yourself (almost certainly unnecessary unless you're working with a braindead compiler), see libdivide.

这篇关于为什么GCC在实现整数除法时使用乘以奇怪的数字?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！