Почему GCC использует умножение на странное число при реализации целочисленного деления?
Я читал о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? Как он генерирует это магическое число и почему все работает?