Какие целые операции с дополнением 2 можно использовать без обнуления высоких бит в входах, если требуется только низкая часть результата?
В программировании сборки довольно часто требуется вычислить что-то из младших бит регистра, который не гарантирует, что остальные биты будут обнулены. На языках более высокого уровня, таких как C, вы просто вводите свои входы в малый размер и позволяете компилятору решить, нужно ли ему обнулять верхние биты каждого входа отдельно или же он может отрубить верхние биты результата после факт.
Это особенно характерно для x86-64 (aka AMD64) по разным причинам 1 , некоторые из которых присутствуют в других ISA.
Я буду использовать 64-битные x86 для примеров, но цель состоит в том, чтобы спросить о / обсуждать дополнение 2 и двоичную арифметику без знака в целом, поскольку все современные процессоры используют ее . (Обратите внимание, что C и C ++ не гарантируют два дополнения 4 , а подписанное переполнение – неопределенное поведение.)
- Сборка - JG / JNLE / JL / JNGE после CMP
- Является x86 CMPXCHG атомом?
- Инструкция INC против ADD 1: Это имеет значение?
- В чем разница между MOV и LEA?
- Двоичная бомба - Фаза 4
В качестве примера рассмотрим простую функцию, которая может компилироваться в инструкцию LEA 2 . (В x86-64 SysV (Linux) ABI 3 первые два аргумента функции находятся в rdi и rsi с возвратом в rax . int – 32-битный тип.)
; int intfunc(int a, int b) { return a + b*4 + 3; } intfunc: lea eax, [edi + esi*4 + 3] ; the obvious choice, but gcc can do better ret
gcc знает, что добавление, даже отрицательных целых чисел, переносится только справа налево, поэтому верхние биты входов не могут влиять на то, что входит в eax . Таким образом, он сохраняет байты команд и использует lea eax, [rdi + rsi*4 + 3]
Какие другие операции имеют это свойство для младших бит результата, не зависящего от старших бит входов?
И почему это работает?
Сноски
1 Почему это часто возникает для x86-64 : x86-64 имеет инструкции переменной длины, где дополнительный префиксный байт изменяет размер операнда (от 32 до 64 или 16), поэтому сохранение байта часто возможно в инструкциях, которые в противном случае выполненных с той же скоростью. Он также имеет ложные зависимости (AMD / P4 / Silvermont) при записи низких 8b или 16b регистра (или стоп, когда позже читает полный регистр (Intel pre-IvB)): по историческим причинам только запись на 32b sub -регирует ноль остальную часть регистра 64b . Почти все арифметики и логики могут использоваться на низких 8, 16 или 32 битах, а также на всех 64 битах регистров общего назначения. Целочисленные векторные инструкции также довольно не ортогональны, некоторые операции недоступны для некоторых размеров элементов.
Кроме того, в отличие от x86-32, ABI передает функции args в регистры, а верхние биты не обязательно равны нулю для узких типов.
2 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 , так как комментарии в parsingке выводятся из превосходного демонстратора objconv от Agner Fog.
3 x86 ABI : вызывающему абоненту не нужно иметь нуль (или подписывать-расширять) верхнюю часть 64-битных регистров, используемых для передачи или возврата меньших типов по значению. Вызывающий, который хотел использовать возвращаемое значение в качестве индекса массива, должен был бы movzx rax, eax его (с помощью movzx rax, eax или команды cdqe для специального случая для eax (не путать с cdq , расширяет eax в edx:eax например, для установки idiv .))
Это означает, что функция, возвращающая unsigned int может вычислить возвращаемое значение в 64-битном временном режиме в rax и не требует, чтобы mov eax, eax чтобы обнулить верхние биты rax . Это конструктивное решение работает в большинстве случаев: часто вызывающему абоненту не нужны какие-либо дополнительные инструкции, чтобы игнорировать неопределенные биты в верхней половине rax .
4 C и C ++
C и C ++, в частности, не требуют двоичных двоичных целых двоичных дополнений (кроме C ++ std::atomic types ). Также допускаются дополнения и знак / величина , поэтому для полностью переносимого C эти трюки полезны только для unsigned типов. Очевидно, что для подписанных операций набор знака-бита в представлении знака / величины означает, что другие биты вычитаются, а не добавляются, например. Я не проработал логику для своего дополнения
Однако бит-хаки, которые работают только с дополнением двух, широко распространены , потому что на практике никто не заботится ни о чем другом. Многие вещи, которые работают с дополнением двух, также должны работать со своим дополнением, поскольку бит знака по-прежнему не меняет интерпретации других битов: он просто имеет значение – (2 N -1) (вместо 2 N ). Знак / величина представления не имеет этого свойства: значение места каждого бита положительное или отрицательное в зависимости от знакового бита.
Также обратите внимание, что компиляторам C разрешено считать, что подписанное переполнение никогда не происходит , потому что это неопределенное поведение. Поэтому, например, компиляторы могут и предполагают (x+1) < x всегда false . Это делает обнаружение подписанного переполнения довольно неудобным в C. Обратите внимание, что разница между unsigned wraparound (carry) и подписанным переполнением .
- Почему медленная инструкция цикла? Не удалось ли Intel эффективно внедрить его?
- Медленная инструкция jmp
- Почему нарушение «выходной зависимости» LZCNT имеет значение?
- Атомные операции, std :: atomic и упорядочение записи
- Цикл с вызовом функции быстрее, чем пустой цикл
- Почему этот код SSE в 6 раз медленнее без VZEROUPPER на Skylake?
- Какова цель инструкции «ПАУЗА» в x86?
- x86 Расчет AX с учетом AH и AL?
Широкие операции, которые могут использоваться с мусором в верхних битах:
- побитовые логики
- левый сдвиг (включая
*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, t влияет на количество сдвигов. Также применяется к беспошлинным сдвигам BMI2 (shlxт. Д.), Но не к векторным сдвигам (pslld xmm, xmm/m128т. Д.,pslld xmm, xmm/m128насыщают счет). Интеллектуальные компиляторы оптимизируют маскировку счета сдвига, позволяя безопасную идиому для вращения в C (нет неопределенного поведения) .
Очевидно, что флаги, такие как carry / overflow / sign / zero, будут зависеть от мусора в высоких бит более широкой операции. Сдвиги x86 помещают последний бит, смещенный в флаг переноса, так что это даже влияет на сдвиги.
Операции, которые нельзя использовать с мусором в верхних битах:
- правая смена
-
полное умножение: например, для 16b x 16b -> 32b, убедитесь, что верхние 16 входов имеют нуль или расширенный знак перед выполнением 32b x 32b -> 32b
imul. Или используйте 16-битный один-операндmulилиimulчтобы неудобно поместить результат вdx:ax. (Выбор подписанной или неподписанной команды будет влиять на верхний 16b так же, как ноль или знак, до 32bimul.) -
адресация памяти (
[rsi + rax]): знак или нуль расширяются по мере необходимости. Нет режима адресации[rsi + eax]. -
разделение и остаток
- log2 (т. е. положение самого старшего бита)
- завершение нулевого отсчета (если вы не знаете, что бит бит находится где-то в той части, которую вы хотите, или просто проверьте результат больше, чем N, поскольку вы не обнаружили проверку.)
Дополнением 2, как беззнаковое основание 2, является система ценностей места. MSB для unsigned base2 имеет значение места 2 N-1 в N битовом числе (например, 2 31 ). В дополнении 2 MSB имеет значение -2 N-1 (и, следовательно, работает как знаковый бит). В статье wikipedia объясняется много других способов понимания дополнения 2 и отрицания номера без знака base2.
Ключевым моментом является то , что наличие установленного битового знака не меняет интерпретации других битов . Сложение и вычитание работают точно так же, как для unsigned base2, и только интерпретация результата отличается между подписанным и unsigned. (например, подписанное переполнение происходит, когда есть перенос, но не из знакового бита ).
Кроме того, перенос распространяется только от LSB до MSB (справа налево). Вычитание одинаково: независимо от того, есть ли что-либо в высоких бит для заимствования, низкие бит заимствуют его. Если это вызывает переполнение или перенос, будут затронуты только высокие биты. например:
0x801F -0x9123 ------- 0xeefc
Низкие 8 бит, 0xFC , не зависят от того, что они заимствовали. Они «обертываются» и передают заимствование в верхние 8.
Таким образом, сложение и вычитание имеют свойство, что низкие биты результата не зависят от каких-либо верхних бит операндов.
Поскольку LEA использует только добавление (и сдвиг влево), использование размера адреса по умолчанию всегда прекрасное. Отсрочка усечения до тех пор, пока размер операнда не вступит в игру, результат всегда прекрасен.
(Исключение: 16-битный код может использовать префикс размера адреса для выполнения 32-битной математики. В коде 32 или 64b префикс размера адреса уменьшает ширину вместо увеличения.)
Умножение можно рассматривать как повторное добавление, или как смещение и добавление. На нижнюю половину не влияют никакие верхние биты. В этом 4-битном примере я выписал все бит-продукты, которые суммируются в биты с низким результатом. Используются только два младших бита обоих источников. Понятно, что это работает в целом: частичные продукты сдвигаются перед добавлением, поэтому высокие бит в источнике никогда не влияют на младшие биты в результате в целом.
См. Википедию для более широкой версии этого с гораздо более подробным объяснением . Есть много хороших хитов 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 ref говорит:
Двух- и трехоперационные формы также могут использоваться с неподписанными операндами, потому что нижняя половина продукта одинакова независимо от того, подписаны ли операнды или нет. Однако флаги CF и OF не могут использоваться, чтобы определить, отлична ли верхняя половина результата.
- Проектное решение Intel вводит только 2 и 3 операндных формы
imul, а неmul.
Очевидно, что побитовые двоичные логические операции (и / или / xor / not) обрабатывают каждый бит независимо: результат для позиции бита зависит только от значения входных данных в этой позиции бита. Бит-сдвиги также довольно очевидны.