Какие 2 дополнительных целочисленных операции можно использовать без обнуления высоких бит в входах, если требуется только низкая часть результата?

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

Это особенно характерно для x86-64 (он же AMD64) по разным причинам ¹, некоторые из которых присутствуют в других ISA.

Я буду использовать 64-битную x86 в качестве примера, но намереваюсь спросить/обсудить 2 дополнения и бинарную арифметику без знака в целом, так как все современные процессоры используют ее. (Обратите внимание, что C и C++ не гарантируют два дополнения ⁴, и что переполнение со знаком является неопределенным поведением.)

В качестве примера рассмотрим простую функцию, которая может компилироваться в инструкцию LEA ². (В x86-64 SysV (Linux) ABI³ первые два аргумента функции находятся в rdi и rsi, с возвратом в rax. int является 32-битным тип.)

gcc знает, что сложение, даже целых чисел со знаком минус, переносится только справа налево, поэтому старшие биты входных данных не могут влиять на то, что входит в eax. Таким образом, он сохраняет байт инструкции и использует lea eax, [rdi + rsi*4 + 3]

Какие другие операции имеют это свойство младших битов результата, не зависящее от старших битов входов?

Сноски

¹ Почему это часто встречается в x86-64: В x86-64 есть инструкции переменной длины, где дополнительный префиксный байт изменяет размер операнда (с 32 до 64 или 16), поэтому сохранение байта часто возможно в инструкциях, которые в противном случае выполняются с той же скоростью. Он также имеет ложные зависимости (AMD/P4/Silvermont) при записи младших 8b или 16b регистра (или остановку при последующем чтении полного регистра (Intel pre-IvB)): по историческим причинам пишет только до 32b подрегистров ноль, остальные из регистра 64b. Почти вся арифметика и логика могут использоваться на младших 8, 16 или 32 битах, а также на полных 64 битах регистров общего назначения. Целочисленные векторные инструкции также довольно неортогональны, некоторые операции недоступны для элементов некоторых размеров.

Кроме того, в отличие от x86-32, ABI передает аргументы функции в регистрах, и верхние биты не должны быть нулевыми для узких типов.

² LEA: Как и в других инструкциях, размер операнда по умолчанию LEA составляет 32 бита, но размер адреса по умолчанию - 64 бита. Байт префикса размера операнда (0x66 или REX.W) может сделать размер выходного операнда 16 или 64 бита. Байт префикса размера адреса (0x67) может уменьшить размер адреса до 32 бит (в 64-битном режиме) или 16 бит (в 32-битном режиме). Таким образом, в 64-битном режиме lea eax, [edx+esi] занимает на один байт больше, чем lea eax, [rdx+rsi].

Можно сделать lea rax, [edx+esi], но адрес все еще вычисляется только с 32 битами (перенос не устанавливает бит 32 в rax). Вы получаете идентичные результаты с lea eax, [rdx+rsi], который на два байта короче. Таким образом, префикс размера адреса никогда не будет полезен с LEA, так как комментарии в выводе разборки от Agner Fog предупреждают о превосходном дизассемблере objconv.

³ x86 ABI: Вызывающая сторона не должна обнулять (или расширять знак) верхнюю часть 64-битных регистров, используемых для передачи или возврата меньших типов по значению. Вызывающий объект, который хотел использовать возвращаемое значение в качестве индекса массива, должен был бы расширить его со знаком (с помощью movzx rax, eax или специальной инструкции case-to-eax cdqe. (Не путать с cdq, какой знак расширяет eax в edx:eax, например, чтобы установить для idiv.))

Это означает, что функция, возвращающая unsigned int, может вычислить свое возвращаемое значение в 64-битном временном значении в rax и не требовать mov eax, eax для обнуления старших битов в rax. Это конструктивное решение работает в большинстве случаев: часто вызывающему абоненту не нужны никакие дополнительные инструкции, чтобы игнорировать неопределенные биты в верхней половине rax.

⁴ C и C++

В частности, C и C++ не требуют двух дополнительных двоичных чисел со знаком (кроме типов C++ std::atomic). Допускается также одно дополнение и знак/величина, поэтому для полностью переносимого C эти приемы полезны только для типов unsigned. Очевидно, что для знаковых операций установленный бит знака в представлении знак/величина означает, что другие биты, например, вычитаются, а не добавляются. Я не проработал логику для одного дополнения

Однако бит-хаки, которые работают только с двумя дополнениями, широко распространены, потому что на практике больше никому нет дела. Многие вещи, которые работают с двумя дополнениями, должны также работать с одним дополнением, поскольку знаковый бит по-прежнему не меняет интерпретацию других битов: он просто имеет значение - (2 ^N -1) (вместо 2 ^N). Представление знака/величины не имеет этого свойства: значение места каждого бита является положительным или отрицательным в зависимости от знакового бита.

Ответы

Ответ 1

Широкие операции, которые можно использовать с мусором в старших битах:

побитовая логика
сдвиг влево (включая *scale в [reg1 + reg2*scale + disp])
сложение/вычитание (и, следовательно, инструкции LEA: префикс размера адреса никогда не нужен. Просто используйте нужный размер операнда для усечения при необходимости.)
Низкая половина умножения. например 16b x 16b → 16b можно сделать с 32b x 32b → 32b. Вы можете избежать остановок LCP (и проблем с частичной регистрацией) из imul r16, r/m16, imm16, используя 32-битный imul r32, r/m32, imm32 и затем читая только младшие 16 результата. (При использовании версии m32 будьте осторожны с более широкими ссылками на память.)

Как указано в руководстве Intel insn ref, формы с 2 и 3 операндами imul безопасны для целых чисел без знака. Знаковые биты входов не влияют на N битов результата при умножении на бит N x N -> N.)
2 ^x (т.е. смещение на x): работает, по крайней мере, на x86, где число смещений маскируется, а не насыщается, вплоть до ширины операции, что приводит к большому мусору в ecx или даже к высокой биты cl, не влияют на счет смены. Также применяется к изменениям без флага BMI2 (shlx и т.д.), Но не к векторным сдвигам (pslld xmm, xmm/m128 и т.д., Которые насыщают счет). Умные компиляторы оптимизируют маскировку числа сдвигов, обеспечивая безопасную идиому для поворотов в C (без неопределенного поведения).

Очевидно, что флаги типа carry/overflow/sign/zero будут зависеть от мусора в старших битах более широкой операции. сдвиги x86 помещают последний сдвинутый бит в флаг переноса, так что это даже влияет на сдвиги.

Операции, которые нельзя использовать с мусором в старших битах:

сдвиг вправо
полное умножение: например, для 16b x 16b → 32b, убедитесь, что верхние 16 входов zero- или расширены до знака перед выполнением 32b x 32b → 32b imul. Или используйте 16-битный однооперанд mul или imul, чтобы неудобно поместить результат в dx:ax. (Выбор инструкции со знаком и без знака будет влиять на верхние 16b таким же образом, как zero- или на расширение знака до 32b imul.)
адресация памяти ([rsi + rax]): знак или zero- расширяются по мере необходимости. Режим адресации [rsi + eax] отсутствует.
деление и остаток
log2 (то есть позиция старшего установленного бита)
конечный отсчет нуля (если вы не знаете, что где-то в нужной части есть установленный бит, или просто проверьте результат, превышающий N, поскольку вы не нашли проверку.)

Два дополнения, подобно неподписанному основанию 2, представляют собой систему стоимости-места. MSB для неподписанного base2 имеет значение места 2 ^N-1 в числе N битов (например, 2 ³¹). В дополнении 2 MSB имеет значение -2 ^N-1 (и, таким образом, работает как знаковый бит). Статья в Википедии объясняет множество других способов понимания дополнения 2 и отрицания числа без знака base2.

Ключевым моментом является то, что с установленным битом знака не меняет интерпретацию других битов. Сложение и вычитание работают точно так же, как и для unsigned base2, и это только интерпретация результата, которая отличается между подписанным и unsigned. (Например, переполнение со знаком происходит, когда имеется перенос в, но не из знакового бита.)

Кроме того, перенос распространяется только от LSB к MSB (справа налево). Вычитание одно и то же: независимо от того, есть ли что-либо в старших битах для заимствования, младшие биты заимствуют это. Если это вызывает переполнение или перенос, будут затронуты только старшие биты. Например.:

 0x801F
-0x9123
-------
 0xeefc

Младшие 8 битов 0xFC не зависят от того, что они позаимствовали. Они "оборачиваются" и передают заем в верхние 8 бит.

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

Поскольку LEA использует только сложение (и сдвиг влево), использование размера адреса по умолчанию всегда хорошо. Задержка усечения, пока размер операнда не вступает в игру для результата, всегда в порядке.

(Исключение: 16-битный код может использовать префикс размера адреса для выполнения 32-битной математики. В 32-битном или 64-битном коде префикс размера адреса уменьшает ширину, а не увеличивается.)

Умножение можно рассматривать как повторное сложение или как смещение и сложение. Нижняя половина не подвержена влиянию верхних битов. В этом 4-битном примере я выписал все битовые продукты, которые суммируются в младшие 2 результирующих бита. Только младшие 2 бита любого источника вовлечены. Понятно, что это работает в целом: частичные произведения перед добавлением сдвигаются, поэтому старшие биты в источнике никогда не влияют на младшие биты в результате в целом.

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

    *Warning*: This diagram is probably slightly bogus.


       ABCD   A has a place value of -2^3 = -8
     * abcd   a has a place value of -2^3 = -8
     ------
   RRRRrrrr

   AAAAABCD * d  sign-extended partial products
 + AAAABCD  * c
 + AAABCD   * b
 - AABCD    * a  (a * A = +2^6, since the negatives cancel)
  ----------
          D*d
         ^
         C*d+D*c

Выполнение умножения со знаком вместо умножения без знака все равно дает тот же результат в младшей половине (младшие 4 бита в этом примере). Расширение знака частичных продуктов происходит только в верхней половине результата.

Это объяснение не очень полное (и, возможно, даже содержит ошибки), но есть убедительные доказательства того, что оно является правдивым и безопасным для использования в рабочем коде:

gcc использует imul для вычисления произведения unsigned long двух входов unsigned long. Посмотрите на пример того, как gcc использует LEA для других функций в проводнике компилятора Godbolt.
Справочное руководство Intel Insn гласит:

two- и трехоперандные формы также могут использоваться с беззнаковыми операнды, потому что нижняя половина произведения одинакова независимо если операнды подписаны или не подписаны. Флаги CF и OF, однако, не может использоваться, чтобы определить, является ли верхняя половина результата не равен нулю.

Решение Intel о разработке только 2 и 3 операндных форм imul, а не mul.

Очевидно, что побитовые двоичные логические операции (и/или /xor/not) обрабатывают каждый бит независимо: результат для позиции бита зависит только от входного значения в этой позиции бита. Сдвиги битов также довольно очевидны.