Работа с 64-битными произведениями и частными 32-битных целых чисел в сборке x86-64

x86-64 — это 64-битная архитектура, поэтому эффективный код bigint обычно должен работать 64-битными фрагментами. например imul %rdi, чтобы установить 128-битный RDX:RAX для произведения RDI * RAX. Используйте для этого форму с одним операндом imul (https://www.felixcloutier.com/x86/imul). Формы с большим количеством операндов, которые вы используете, не записывают неявно EDX или RDX.

Если 64 бита достаточно широки, вы можете использовать 64-битную математику без расширения после знакового расширения входных данных с помощью таких нагрузок, как movslq (%r8), %rax. Затем 2-операнд imul для умножения, не нарушая RDX. Вам понадобится cqo / idiv, если вы хотите выполнить 64-битное деление. Синтаксис AT&T называет это cqto, но GAS принимает любую мнемонику.

(Если значения в памяти могут быть просто 64-битными, вы можете использовать такие вещи, как imulq 8(%r8), %rax вместо использования mov для загрузки.)

Если вы знаете, что частное умещается в 32 бита, mov 8(%r8), %eax/imull (%r8) получит ваш 64-битный продукт в EDX:EAX (обратите внимание на явный суффикс размера операнда l в imul), который устанавливает 32-битный размер операнда. idivl 4(%r8). В этом случае вы не используете cdq, это заменит ваш 64-битный продукт расширением знака младшей половины. (Когда и почему мы подписываем расширение и используем cdq с mul/div? / Почему EDX должен быть равен 0 перед использованием инструкции DIV?).

Но использование полной 64-битной ширины делимого для 32-битного деления размера операнда приводит к тому, что частное не помещается в размер операнда (для случаев, отличных от INT_MIN / -1 или деления на 0) , и в этом случае вы получите исключение #DE. (И операционные системы POSIX, включая Linux, доставят SIGFPE в ваш процесс.)

Кроме того, это ограничивает ваш делитель до 32-битного. Вы говорите, что возведение в квадрат r10d может переполниться, и это еще одна причина, по которой это не вариант.

64-битный размер операнда для деления работает намного медленнее на процессорах Intel до Ice Lake, но если ваш делитель не помещается в 32 бита, это ваш единственный вариант. (За исключением ветвления по размеру делителя, что может быть преимуществом для старых процессоров Intel; некоторые версии clang/опции оптимизации делают это.)

С 32-битными входными данными со знаком и использованием 64-битных целых чисел для временных значений. Хранение 64-битных целых чисел в отдельных регистрах для простоты и эффективности. (два операнда imul — это один моп, а один операнд — это 2 или 3 мопа на Intel, поскольку он должен записать 2 выходных регистра и разделить выход блока умножителя. https://uops.info/)

    movslq (%r8), %rdi   # sign-extend long (32-bit) to quad (64-bit)
    movslq 4(%r8), %r10
    movslq 8(%r8), %rax 

    imul   %rdi, %rax    # 64-bit non-widening multiplies can't overflow since the values are 32-bit
    imul   %r10, %r10

    cqto                # signed division of RAX by R10
    idiv   %r10

Даже квадрат INT_MIN (-2^31) по-прежнему помещается в int64_t, поэтому эти умножения не могут привести к переполнению. Не было необходимости в imul %rdi, который записывал бы полный 128-битный продукт в RDX:RAX. Но это позволит избежать необходимости в cqto в данном случае, поскольку для целочисленного деления x86 действительно требуется делимое двойной ширины.

На самом деле это дало бы нам меньший машинный код и обеспечило бы безубыточность по количеству операций на последних процессорах Intel и AMD (https://uops.info/), где imul r64 — это «всего» 2 мопса, а задержка записи RDX равна всего через один цикл после того, как результат RAX готов (так же, как cqo).

Если вы сделаете исходные входные данные 64-битными, использование расширяющего умножения имеет то преимущество, что делимое может быть больше 64-битного без ошибок, если делитель достаточно велик, чтобы частное уместилось в 64 бита.