为什么GCC在执行整数除法时使用奇数乘法？ [英] Why does GCC use multiplication by a strange number in implementing integer division?
问题描述
我一直在阅读关于 div 和 mul 汇编操作，并且我决定通过操作在C中编写一个简单的程序：
File division.c
#include< stdlib.h>
#include< stdio.h>
int main（）
{
size_t i = 9;
size_t j = i / 5;
printf（％zu\\\
，j）;
返回0;
}
然后用以下代码生成汇编语言代码：
gcc -S division.c -O0 -masm = intel
但是看看生成的 division.s 文件，它不包含任何div操作！相反，它做了一些带有位移和魔法数字的黑魔法。这是一个计算 i / 5 的代码片段：
mov rax， QWORD PTR [rbp-16];将我（= 9）移至RAX
movabs rdx，-3689348814741910323;将一些幻数移动到RDX（？）
mul rdx;由幻数乘以9
mov rax，rdx;只取结果的高64位
shr rax，2;将这两位移到右边（？）
mov QWORD PTR [rbp-8]，rax;神奇的是，RAX现在包含9/5 = 1，
;所以我们可以将它分配给j
这是怎么回事？为什么GCC不使用div？它是如何产生这个幻数的，以及为什么一切正常？
整数除法是您可以执行的最慢整数运算之一在现代处理器上，延迟时间长达数十个周期，吞吐量不佳。 （对于x86，请参阅 Agner Fog的指令表和微型指南）。
如果您提前知道除数，则可以通过将其替换为具有相同效果的一组其他运算（乘法，加法和移位）来避免该除法。即使需要多个操作，它仍然比整数部分本身快得多。
实现C / >运算符，而不是使用涉及 div 的多指令序列，这只是GCC按常量进行除法的默认方式。它不需要跨操作进行优化，即使进行调试也不会改变任何内容。 （对于小代码，使用 -Os 确实会让GCC使用 div ）。使用乘法反而不是除了使用 lea 而不是 mul 和 add
因此，您只能看到 div 或 idiv 。
有关编译器如何生成这些序列的信息，以及用于生成这些序列的代码他们为自己（几乎肯定是不必要的，除非你正在使用braindead编译器），请参阅 libdivide 。
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:
File division.c
#include <stdlib.h>
#include <stdio.h>
int main()
{
size_t i = 9;
size_t j = i / 5;
printf("%zu\n",j);
return 0;
}
And then generating assembly language code with:
gcc -S division.c -O0 -masm=intel
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
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?
Integer division is one of the slowest integer 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.
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
As a result, you only tend to see div or idiv in the output if the divisor isn't known at compile-time.
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屋！
