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

Question

Я пытался выяснить, как рассчитать модуль 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.

Answer 1

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

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

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

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 вычислялся по модулю, задайте переменную делителя (например, параметр функции), чтобы он не мог выполнять такую ​​оптимизацию. В любом случае на x86 вы вычисляете по модулю, используя div. div ожидает 64-битное деление в edx:eax (старшие 32 бита в edx, младшие 32 бита в eax - обнулять edx в ноль, если вы работаете с 32-битным числом) и делит его на любой операнд, который вы укажете (например, div ebx делит edx:eax на ebx). Возвращает частное в eax, а остаток в edx. idiv делает то же самое для значений со знаком.

Answer 2

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

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