Почему GCC использует умножение на странное число при реализации целочисленного деления?

Я читал о div а также mul сборочные операции, и я решил увидеть их в действии, написав простую программу на C:

Файл деление.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? Как он генерирует это магическое число и почему все работает?

Источник

4 ответа

Целочисленное деление является одной из самых медленных арифметических операций, которые вы можете выполнять на современном процессоре, с задержкой до десятков циклов и плохой пропускной способностью. (Для x86 см . Таблицы инструкций Agner Fog и руководство microarch).

Если вы знаете делитель заранее, вы можете избежать деления, заменив его набором других операций (умножения, сложения и сдвиги), которые имеют эквивалентный эффект. Даже если требуется несколько операций, часто это все равно намного быстрее, чем само целочисленное деление.

Реализация C / оператор таким образом, а не с последовательностью из нескольких команд, включающей div это просто способ GCC по умолчанию для деления на константы. Он не требует оптимизации операций и ничего не меняет даже для отладки. (С помощью -Os для небольшого размера кода заставляет GCC использовать divХотя использование мультипликативного обратного вместо деления похоже на использование lea вместо mul а также add

В результате вы только склонны видеть div или же idiv в выводе, если делитель не известен во время компиляции.

Для получения информации о том, как компилятор генерирует эти последовательности, а также код, позволяющий вам создавать их для себя (почти наверняка ненужный, если вы не работаете с компилятором braindead), смотрите http://libdivide.com/.

Источник

Деление на 5 - это то же самое, что умножение на 1/5, что опять же, как умножение на 4/5 и сдвиг вправо на 2 бита. Соответствующее значение CCCCCCCCCCCCD в шестнадцатеричном формате, который является двоичным представлением 4/5, если ставится после шестнадцатеричной точки (то есть двоичный код для четырех пятых равен 0.110011001100 повторяющиеся - см. ниже, почему). Я думаю, что вы можете взять это отсюда! Возможно, вы захотите проверить арифметику с фиксированной точкой (хотя обратите внимание, что в конце она округляется до целого числа).

Что касается того, почему, умножение быстрее, чем деление, и когда делитель фиксирован, это более быстрый маршрут.

См. Взаимное Умножение, учебное пособие для подробного описания того, как это работает, объясняя с точки зрения фиксированной точки. Он показывает, как работает алгоритм поиска обратной величины и как обрабатывать деление со знаком и по модулю.

Давайте на минуту рассмотрим, почему 0.CCCCCCCC... (шестнадцатеричный) или 0.110011001100... двоичный файл 4/5. Разделите двоичное представление на 4 (сдвиньте вправо на 2 места), и мы получим 0.001100110011... который путем тривиального осмотра может быть добавлен оригинал, чтобы получить 0.111111111111..., который, очевидно, равен 1, так же, как 0.9999999... в десятичном формате равен единице. Поэтому мы знаем, что x + x/4 = 1, так 5x/4 = 1, x=4/5, Это тогда представляется как CCCCCCCCCCCCD в шестнадцатеричном виде для округления (поскольку двоичная цифра за пределами последней присутствующей будет 1).

Источник

В общем, умножение намного быстрее, чем деление. Так что, если нам удастся избежать умножения на обратное, мы сможем значительно ускорить деление на константу

Проблема заключается в том, что мы не можем точно представить обратную величину (если деление не было степенью двойки, но в этом случае мы обычно можем просто преобразовать деление в битовый сдвиг). Таким образом, чтобы гарантировать правильные ответы, мы должны быть осторожны, чтобы ошибка в нашем ответе не приводила к ошибкам в нашем конечном результате.

-3689348814741910323 - это 0xCCCCCCCCCCCCCCCD, значение чуть более 4/5, выраженное в 0,64 с фиксированной точкой.

Когда мы умножаем 64-битное целое число на число с фиксированной точкой 0,64, мы получаем результат 64,64. Мы усекаем значение до 64-битного целого числа (эффективно округляя его до нуля), а затем выполняем дальнейшее смещение, которое делится на четыре и снова усекает. Посмотрев на битовый уровень, становится ясно, что мы можем рассматривать оба усечения как одно усечение.

Это дает нам хотя бы приблизительное значение деления на 5, но дает ли он точный ответ, правильно округленный до нуля?

Чтобы получить точный ответ, ошибка должна быть достаточно маленькой, чтобы не переместить ответ за границу округления.

Точный ответ на деление на 5 всегда будет иметь дробную часть 0, 1/5, 2/5, 3/5 или 4/5 . Следовательно, положительная ошибка менее 1/5 в умноженном и сдвинутом результате никогда не переместит результат за границу округления.

Ошибка в нашей константе (1/5) * 2-64. Значение i составляет менее 264, поэтому ошибка после умножения составляет менее 1/5. После деления на 4 ошибка меньше (1/5) * 2−2.

(1/5) * 2−2 <1/5, поэтому ответ всегда будет равен точному делению и округлению до нуля.

К сожалению, это не работает для всех делителей.

Если мы попытаемся представить 4/7 как число с фиксированной точкой 0,64 с округлением от нуля, мы получим ошибку (6/7) * 2-64. После умножения на значение i чуть менее 264 мы получим ошибку чуть меньше 6/7, а после деления на четыре мы получим ошибку чуть менее 1,5/7, которая больше 1/7.

Таким образом, чтобы правильно реализовать деление на 7, нам нужно умножить на число с фиксированной точкой 0,65. Мы можем реализовать это путем умножения на младшие 64 бита нашего числа с фиксированной запятой, затем добавления исходного числа (это может переполниться в бит переноса) и последующего поворота через перенос.

Источник

Вот ссылка на документ алгоритма, который создает значения и код, который я вижу в Visual Studio (в большинстве случаев), и который, как я полагаю, все еще используется в GCC для деления целого числа переменной на целое число константы.

http://gmplib.org/~tege/divcnst-pldi94.pdf

В этой статье uword имеет N битов, udword имеет 2N битов, n = числитель, d = знаменатель = делитель, initially изначально установлено в ceil(log2(d)), shpre является предварительным сдвигом (используется перед умножением) = e = количество завершающих нулевых битов в d, shpost- пост-сдвиг (используется после умножения), prec - точность = N - e = N - shpre. Цель состоит в том, чтобы оптимизировать расчет н / д с использованием до сдвига, умножения и постсдвига.

Прокрутите вниз до рисунка 6.2, который определяет, как генерируется множитель udword (максимальный размер N+1 бит), но не дает четкого объяснения процесса. Я объясню это ниже.

Рисунок 4.2 и рисунок 6.2 показывают, как множитель может быть уменьшен до множителя N бит или меньше для большинства делителей. Уравнение 4.5 объясняет, как была получена формула, используемая для работы с N+1 битовыми умножителями на рисунках 4.1 и 4.2.

Возвращаясь к рисунку 6.2. Числитель может быть больше, чем вымышленное слово, только когда делитель> 2^(N-1) (когда ℓ == N), в этом случае оптимизированной заменой для n/d является сравнение (если n>=d, q = 1, иначе q = 0), поэтому множитель не генерируется. Начальные значения mlow и mhigh будут N+1 бит, и для получения каждого значения N+1 бит (mlow или mhigh) можно использовать два деления udword / uword. Используя X86 в 64-битном режиме в качестве примера:

; upper 8 bytes of numerator = 2^(ℓ) = (upper part of 2^(N+ℓ))
; lower 8 bytes of numerator for mlow  = 0
; lower 8 bytes of numerator for mhigh = 2^(N+ℓ-prec) = 2^(ℓ+shpre) = 2^(ℓ+e)
numerator dq    2 dup(?)        ;16 byte numerator
divisor   dq    1 dup(?)        ; 8 byte divisor
; ...
        mov     rcx,divisor
        mov     rdx,0
        mov     rax,numerator+8    ;upper 8 bytes of numerator
        div     rcx                ;after div, rax == 1
        mov     rax,numerator      ;lower 8 bytes of numerator
        div     rcx
        mov     rdx,1              ;rdx:rax = N+1 bit value = 65 bit value

Вы можете проверить это с помощью GCC. Вы уже видели, как обрабатывается j = i/5. Посмотрите, как обрабатывается j = i/7 (это должен быть случай умножения N+1 бит).

Источник

Я отвечу немного под другим углом: потому что это разрешено.

C и C++ определены для абстрактной машины. Компилятор преобразует эту программу в терминах абстрактной машины в конкретную машину, следуя правилу " как если бы".

  • Компилятору разрешено вносить ЛЮБЫЕ изменения, если он не изменяет наблюдаемое поведение, указанное абстрактной машиной. Нет разумных ожиданий, что компилятор преобразует ваш код наиболее простым способом (даже если многие программисты на C предполагают это). Обычно это происходит потому, что компилятор хочет оптимизировать производительность по сравнению с простым подходом (как подробно обсуждается в других ответах).
  • Если при каких-либо обстоятельствах компилятор "оптимизирует" правильную программу для чего-то, что имеет другое наблюдаемое поведение, это ошибка компилятора.
  • Любое неопределенное поведение в нашем коде (знаковое целочисленное переполнение - классический пример) и этот контракт недействителен.
Источник
Другие вопросы по тегам