Why does GCC use multiplication by a strange number in implementing integer division?
assembly, c, gcc, integer-division, x86-64
Solution
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.
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.
Problem
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?