Why does GCC use multiplication by a strange number in implementing integer division?

Question

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=intelBut 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 jWhat's going on here? Why doesn't GCC use div at all? How does it generate this magic number and why does everything work?

Answer 1

Hello!

You've stumbled on a great example of how compilers work hard to make the translated code both correct and fast! This is called 'optimization', and the compiler is [generally] free to change your code from what you wrote to something equivalent (logically), but faster.

In this particular case, the compiler knows that, for the target machine (X86), the integer divide instruction (div) is a fair bit slower than the instruction sequence it chose.

First, remember that 9/6 == 9 * 1/5. You saw that the 9 has been placed in RAX. *Something* (-3689348814741910323) has been put into RDX, and the two registers are multiplied.

The *something* is a 'fixed point' representation of the value 1/5, aka 0.2. The value -3689348814741910323 is a 64-bit representation of 1/5, multiplied by 2^64; the 'fraction' is now 64 bits long, with an implied decimal point between the 64th-bit (the left end of RDX). When you multiply this value (in RDX) by 9 (in RAX), you get a 128-bit result (in RDX:RAX), still with an implied decimal point between bit 64 and 65; the integer part of the answer is in RDX, and the fractional part is in RAX. The compiler has replaced the (slower) division with a (faster) multiply.

(It's not clear to me what the SHR RAX,2 is doing; I could imagine simply storing RDX.)