Как работает реализация GCC по модулю (%) и почему она не использует команду div?

Я пытался выяснить, как рассчитать по модулю 10 в сборке, поэтому я скомпилировал следующий код c в gcc, чтобы узнать, что он придумал.

unsigned int i=999;
unsigned int j=i%10;

К моему удивлению, я получил

movl    -4(%ebp), %ecx
movl    $-858993459, %edx
movl    %ecx, %eax
mull    %edx
shrl    $3, %edx
movl    %edx, %eax
sall    $2, %eax
addl    %edx, %eax
addl    %eax, %eax
movl    %ecx, %edx
subl    %eax, %edx
movl    %edx, %eax
movl    %eax, -12(%ebp)

Где -4 (% ebp) или "i" - это вход, а -12 (% ebp) или "j" - ответ. Я тестировал это, и он работает независимо от того, сколько вы делаете -4 (% ebp).

Мой вопрос в том, как работает этот код и как он лучше, чем использование операнда div.

Ответ 1

Второй вопрос: div - очень медленная инструкция (более 20 тактов). Последовательность выше содержит больше инструкций, но все они относительно быстрые, поэтому это чистая победа с точки зрения скорости.

Первые пять команд (вплоть до shrl) вычисляют i/10 (я объясню, как через минуту).

Следующие несколько команд снова умножают результат на 10, но избегая инструкций mul/imul (независимо от того, является ли это победой или нет, зависит от точного процессора, на который вы нацеливаетесь - новые x86s имеют очень быстрые множители, но более старые не делают).

movl    %edx, %eax   ; eax=i/10
sall    $2, %eax     ; eax=(i/10)*4
addl    %edx, %eax   ; eax=(i/10)*4 + (i/10) = (i/10)*5
addl    %eax, %eax   ; eax=(i/10)*5*2 = (i/10)*10

Затем вычитается из i снова, чтобы получить i - (i/10)*10, который равен i % 10 (для неподписанных номеров).

Наконец, при вычислении i/10: Основная идея - заменить деление на 10 умножением на 1/10. Компилятор делает приближение с фиксированной точкой, умножая на (2 ** 35/10 + 1) - магическое значение, загруженное в edx, хотя оно выводится как знаковое значение, даже если оно действительно без знака - сдвигая результат на 35. Это, оказывается, дает правильный результат для всех 32-битных целых чисел.

Существуют алгоритмы для определения такого приближения, которые гарантируют, что ошибка меньше 1 (что для целых чисел означает ее правильное значение), и GCC, очевидно, использует один:)

Заключительное замечание. Если вы хотите, чтобы GCC вычислил модуль, сделайте переменную divisor (например, параметр функции), чтобы она не могла выполнять такую оптимизацию. Во всяком случае, на x86 вы вычисляете modulo с помощью div. div ожидает 64-битного дивиденда в edx:eax (высокие 32 бита в edx, минимум 32 бит в eax - четкий edx до нуля, если вы работаете с 32-разрядным номером) и делит это на любой операнд, который вы указываете (например, div ebx делит edx:eax на ebx). Он возвращает коэффициент в eax, а остаток - в edx. idiv делает то же самое для подписанных значений.

Ответ 2

Первая часть, до shrl $3, %edx, реализует быстрое целочисленное деление на 10. Существует несколько разных алгоритмов, которые работают, когда число, по которому вы делите, известно заранее. Обратите внимание, что 858993459 "0.2 * 2 ^ 32". Причина этого заключается в том, что, хотя в наборе команд есть команда с целым делением div/idiv, она обычно очень медленная, в несколько раз медленнее, чем умножение.

Вторая часть вычисляет остаток, умножая результат деления на 10 (косвенно, с помощью сдвигов и добавлений, по-видимому, компилятор думает, что он будет быстрее таким образом), а затем вычитает это из исходного числа.