Логические значения как 8 бит в компиляторах. Операции на них неэффективны?

Я читаю « Оптимизирующее программное обеспечение на C ++ » Agner Fog (специально для процессоров x86 для Intel, AMD и VIA), и он указывает на стр. 34

Булева переменная хранится как 8-битные целые числа со значением 0 для false и 1 для true. Булевы переменные переопределены в том смысле, что все операторы, которые имеют логические переменные в качестве входных, проверяют, имеют ли входы какое-либо другое значение, чем 0 или 1, но операторы, которые имеют логический вывод в качестве вывода, могут не вызывать другого значения, кроме 0 или 1. Это делает операции с Булевы переменные в качестве входных данных менее эффективны, чем необходимо.

Это все еще актуально и для компиляторов? Можете ли вы привести пример? Автор утверждает,

Булевы операции могут быть сделаны намного эффективнее, если известно, что операнды не имеют других значений, чем 0 и 1. Причина, по которой компилятор не делает такого предположения, состоит в том, что переменные могут иметь другие значения, если они неинициализированы или происходят из неизвестных источников.

Означает ли это, что, например, если я беру указатель функции bool(*)() и вызываю его, то операции с ним производят неэффективный код? Или это случай, когда я обращаюсь к логическому виду путем разыменования указателя или чтения из ссылки, а затем работает на нем?

TL: DR : у современных компиляторов все еще есть пропущенные оптимизации bool когда делаете такие вещи, как
(a&&b) ? x : y (a&&b) ? x : y . Но причина в том, что они не предполагают 0/1, они просто сосут это.

Многие способы использования bool предназначены для локальных пользователей или встроенных функций, поэтому при первоначальном условии booleanizing to 0/1 может оптимизироваться и разветвляться (или cmov или что-то еще). Только беспокоиться об оптимизации входов / выходов bool когда он должен быть передан / возвращен через то, что не встроено или действительно хранится в памяти.

Возможная директива оптимизации : объединить bool s из внешних источников (функция args / memory) с побитовыми операторами, например a&b . MSVC и ICC лучше справляются с этим. IDK, если это еще хуже для местных bool s. Остерегайтесь того, что a&b эквивалентно только a&&b для bool , а не целочисленных типов. 2 && 1 истинно, но 2 & 1 равно 0, что является ложным. Побитовое ИЛИ не имеет этой проблемы.

IDK, если это правило будет когда-либо вредно для местных жителей, которые были установлены из сравнения в рамках функции (или в чем-то, что встраивается). Например, это может привести к тому, что компилятор действительно сделает целочисленные булевы вместо того, чтобы просто использовать результаты сравнения, когда это возможно. Также обратите внимание, что это не похоже на текущие gcc и clang.


Да, реализация C ++ в x86 хранит bool в байте, который всегда равен 0 или 1 (по крайней мере, через границы функциональных вызовов, где компилятор должен соблюдать соглашение ABI / вызова, которое требует этого).

Компиляторы иногда используют это, например, для bool -> int conversion даже gcc 4.4 просто нуль – продолжается до 32 бит ( movzx eax, dil ). Clang и MSVC тоже делают это. Правила C и C ++ требуют, чтобы это преобразование производило 0 или 1, поэтому это поведение является безопасным, если всегда можно предположить, что аргумент arg или глобальная переменная bool имеет значение 0 или 1.

Даже старые компиляторы обычно использовали его для bool -> int , но не в других случаях. Таким образом, Агнер ошибается в причине, когда он говорит:

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


MSVC CL19 делает код, который предполагает, что аргументы bool функции args равны 0 или 1, поэтому ABI Windows x86-64 должен гарантировать это.

В x86-64 System V ABI (используется все, кроме Windows) в журнале изменений для версии 0.98 говорится: «Укажите, что _Bool (aka bool ) булеван в вызывающем». Я думаю, что даже до этого изменения компиляторы принимали это, но это просто документирует то, на что уже ссылались компиляторы. Текущий язык в x86-64 SysV ABI:

3.1.2 Представление данных

Булевы, хранящиеся в объекте памяти, хранятся в виде однобайтовых объектов, значение которых всегда равно 0 (false) или 1 (true). Когда они хранятся в целочисленных регистрах (за исключением передачи в качестве аргументов), все 8 байтов регистра являются значительными; любое ненулевое значение считается истинным.

Второе предложение – нонсенс: ABI не комментирует бизнес-компиляторы, как хранить вещи в регистре внутри функции только на границах между различными единицами компиляции (аргументы памяти / функции и возвращаемые значения). Я сообщил об этом дефекте ABI некоторое время назад на странице github, где он поддерживается .

3.2.3 Передача параметров :

Когда значение типа _Bool возвращается или передается в регистре или в стеке, бит 0 содержит значение истины, а биты с 1 по 7 равны нулю 16 .

(сноска 16): Остальные биты остаются неопределенными, поэтому потребительская сторона этих значений может полагаться на то, что она равна 0 или 1 при усечении до 8 бит.

Язык в i386 System V ABI тот же, IIRC.


Любой компилятор, который принимает 0/1 для одного (например, преобразование в int ), но не может воспользоваться этим в других случаях, имеет пропущенную оптимизацию . К сожалению, такие пропущенные оптимизации все еще существуют, хотя они реже, чем когда Агнер писал этот параграф о компиляторах, которые всегда повторяются повторно.

(Источник + asm в проводнике для компилятора Godbolt для gcc4.6 / 4.7 и clang / MSVC. См. Также рассказ CppCon2017 от Matt Godbolt. Что мой компилятор сделал для меня в последнее время? Откручивание крышки компилятора )

 bool logical_or(bool a, bool b) { return a||b; } # gcc4.6.4 -O3 for the x86-64 System V ABI test dil, dil # test a against itself (for non-zero) mov eax, 1 cmove eax, esi # return a ? 1 : b; ret 

Таким образом, даже gcc4.6 не повторил booleanize b , но он пропустил оптимизацию, которую gcc4.7 делает: (и clang и более поздние компиляторы, как показано в других ответах):

  # gcc4.7 -O3 to present: looks ideal to me. mov eax, esi or eax, edi ret 

(Clang’s or dil, sil / mov eax, edi глупый: гарантировано, что он будет закрывать неполный регистр на Nehalem или ранее Intel при чтении edi после написания dil , и у него есть худший размер кода от необходимости префикса REX для использования низкого -8 часть edi. Лучшим выбором может быть or dil,sil movzx eax, dil / movzx eax, dil если вы хотите избежать чтения любых 32-битных регистров в случае, если ваш вызывающий абонент оставил некоторые регистры, проходящие через arg, с «грязными» частичными регистрами.)

MSVC испускает этот код, который проверяет a затем b отдельно, полностью не в состоянии воспользоваться чем-либо , и даже используя xor al,al вместо xor eax,eax . Таким образом, он имеет ложную зависимость от старого значения eax на большинстве процессоров ( включая Haswell / Skylake, которые не переименовывают низкоуровневые частичные регистры отдельно от всего регистра, только AH / BH / … ). Это просто глупо. Единственная причина когда-либо использовать xor al,al – это когда вы явно хотите сохранить верхние байты.

 logical_or PROC ; x86-64 MSVC CL19 test cl, cl ; Windows ABI passes args in ecx, edx jne SHORT $LN3@logical_or test dl, dl jne SHORT $LN3@logical_or xor al, al ; missed peephole: xor eax,eax is strictly better ret 0 $LN3@logical_or: mov al, 1 ret 0 logical_or ENDP 

ICC18 также не использует преимущества 0/1 характер входов, он просто использует команду or для установки флагов в соответствии с побитовым ИЛИ обоих входов, а setcc для создания 0/1.

 logical_or(bool, bool): # ICC18 xor eax, eax #4.42 movzx edi, dil #4.33 movzx esi, sil #4.33 or edi, esi #4.42 setne al #4.42 ret #4.42 

ICC испускает один и тот же код даже для bool bitwise_or(bool a, bool b) { return a|b; } bool bitwise_or(bool a, bool b) { return a|b; } . Он продвигает до intmovzx ) и использует or устанавливает флаги в соответствии с побитовым ИЛИ. Это глупо по сравнению с or dil,sil setne al / setne al .

Для bitwise_or MSVC просто использует команду or (после movzx на каждом входе), но в любом случае не повторяет booleanize.


Пропущенные оптимизации в текущем gcc / clang:

Только ICC / MSVC делали немой код с простой функцией выше, но эта функция все еще дает проблемы с gcc и clang:

 int select(bool a, bool b, int x, int y) { return (a&&b) ? x : y; } 

Source + asm в проводнике компилятора Godbolt (тот же источник, разные компиляторы, выбранные против последнего времени).

Выглядит достаточно просто; вы бы надеялись, что умный компилятор сделает это без разрыва с одним test / cmov . Контрольная инструкция x86 устанавливает флаги в соответствии с поразрядным И. Это инструкция AND, которая фактически не записывает адресат. (Точно так же, как cmp – это sub , который не записывает адресата).

 # hand-written implementation that no compilers come close to making select: mov eax, edx # retval = x test edi, esi # ZF = ((a & b) == 0) cmovz eax, ecx # conditional move: return y if ZF is set ret 

Но даже ежедневные сборки gcc и clang в проводнике-компиляторе Godbolt делают гораздо более сложный код, проверяя каждый булев отдельно. Они знают, как оптимизировать bool ab = a&&b; если вы вернете ab , но даже записывая его таким образом (с отдельной логической переменной, чтобы удерживать результат), не удается вручную удерживать их в создании кода, который не сосать.

Обратите внимание, что test same,same как и в точности эквивалентен cmp reg, 0 , и меньше, поэтому это то, что используют компиляторы.

Версия Клана строго хуже моей рукописной версии. (Обратите внимание, что это требует, чтобы вызывающий нуль расширил аргументы bool до 32-разрядных, как и для узких целых типов, в качестве неофициальной части ABI, которую он и gcc реализует, но зависит только от clang ).

 select: # clang 6.0 trunk 317877 nightly build on Godbolt test esi, esi cmove edx, ecx # x = b ? y : x test edi, edi cmove edx, ecx # x = a ? y : x mov eax, edx # return x ret 

gcc 8.0.0 20171110 nightly делает разветвленный код для этого, как и предыдущие версии gcc.

 select(bool, bool, int, int): # gcc 8.0.0-pre 20171110 test dil, dil mov eax, edx ; compiling with -mtune=intel or -mtune=haswell would keep test/jcc together for macro-fusion. je .L8 test sil, sil je .L8 rep ret .L8: mov eax, ecx ret 

MSVC x86-64 CL19 очень похож на разветвленный код. Он нацелен на соглашение о вызове Windows, где целые args находятся в rcx, rdx, r8, r9.

 select PROC test cl, cl ; a je SHORT $LN3@select mov eax, r8d ; retval = x test dl, dl ; b jne SHORT $LN4@select $LN3@select: mov eax, r9d ; retval = y $LN4@select: ret 0 ; 0 means rsp += 0 after popping the return address, not C return 0. ; MSVC doesn't emit the `ret imm16` opcode here, so IDK why they put an explicit 0 as an operand. select ENDP 

ICC18 также делает разветвленный код, но с обеих команд mov после ветвей.

 select(bool, bool, int, int): test dil, dil #8.13 je ..B4.4 # Prob 50% #8.13 test sil, sil #8.16 jne ..B4.5 # Prob 50% #8.16 ..B4.4: # Preds ..B4.2 ..B4.1 mov edx, ecx #8.13 ..B4.5: # Preds ..B4.2 ..B4.4 mov eax, edx #8.13 ret #8.13 

Попытка помочь компилятору, используя

 int select2(bool a, bool b, int x, int y) { bool ab = a&&b; return (ab) ? x : y; } 

приводит MSVC к созданию веселого кода :

 ;; MSVC CL19 -Ox = full optimization select2 PROC test cl, cl je SHORT $LN3@select2 test dl, dl je SHORT $LN3@select2 mov al, 1 ; ab = 1 test al, al ;; and then test/cmov on an immediate constant!!! cmovne r9d, r8d mov eax, r9d ret 0 $LN3@select2: xor al, al ;; ab = 0 test al, al ;; and then test/cmov on another path with known-constant condition. cmovne r9d, r8d mov eax, r9d ret 0 select2 ENDP 

Это только с MSVC (и ICC18 имеет ту же пропущенную оптимизацию теста / cmov в регистре, который был просто установлен на константу).

gcc и clang, как обычно, не делают код столь же плохим, как MSVC; они делают то же самое, что и для select() , что по-прежнему не очень хорошо, но по крайней мере пытаться помочь им не ухудшает работу с MSVC.


Комбинация bool с побитовыми операторами помогает MSVC и ICC

В моем очень ограниченном тестировании, | и & похоже, работают лучше, чем || и && для MSVC и ICC. Посмотрите на вывод компилятора для своего собственного кода с параметрами компилятора + компиляции, чтобы узнать, что происходит.

 int select_bitand(bool a, bool b, int x, int y) { return (a&b) ? x : y; } 

Gcc по-прежнему разветвляется отдельно на отдельных test двух входов, то же самое, что и другие версии select . clang все еще выполняет два отдельных test/cmov , то же самое, что и для других исходных версий.

MSVC приходит и оптимизируется правильно, избивая все другие компиляторы (по крайней мере, в автономном определении):

 select_bitand PROC ;; MSVC test cl, dl ;; ZF = !(a & b) cmovne r9d, r8d mov eax, r9d ;; could have done the mov to eax in parallel with the test, off the critical path, but close enough. ret 0 

ICC18 тратит две команды movzx нулевая, расширяя bool s до int , но затем делает тот же код, что и MSVC

 select_bitand: ## ICC18 movzx edi, dil #16.49 movzx esi, sil #16.49 test edi, esi #17.15 cmovne ecx, edx #17.15 mov eax, ecx #17.15 ret #17.15 

Я думаю, что это не так.

Прежде всего, это рассуждение совершенно неприемлемо:

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

Давайте проверим некоторый код (скомпилированный с clang 6, но GCC 7 и MSVC 2017 создают аналогичный код).

Boolean или:

 bool fn(bool a, bool b) { return a||b; } 0000000000000000 : 0: 40 08 f7 or dil,sil 3: 40 88 f8 mov al,dil 6: c3 ret 

Как видно, нет 0/1 здесь, просто or .

Преобразование bool в int:

 int fn(bool a) { return a; } 0000000000000000 : 0: 40 0f b6 c7 movzx eax,dil 4: c3 ret 

Опять же, нет проверки, простого перемещения.

Преобразовать символ в bool:

 bool fn(char a) { return a; } 0000000000000000 : 0: 40 84 ff test dil,dil 3: 0f 95 c0 setne al 6: c3 ret 

Здесь char проверяется, является ли оно 0 или нет, а значение bool установлено равным 0 или 1 соответственно.

Поэтому я думаю, что можно с уверенностью сказать, что компилятор использует bool таким образом, чтобы он всегда содержал 0/1. Он никогда не проверяет его достоверность.

Об эффективности: я думаю, что bool оптимален. Единственный случай, который я могу себе представить, когда этот подход не является оптимальным, – это преобразование char-> bool. Эта операция может быть простой mov, если значение bool не будет ограничено 0/1. Для всех других операций текущий подход одинаково хорош или лучше.


EDIT: Питер Кордес упомянул ABI. Вот соответствующий текст из System V ABI для AMD64 (текст для i386 похож):

Булевы, хранящиеся в объекте памяти, хранятся в виде однобайтовых объектов, значение которых всегда равно 0 (false) или 1 (true) . Когда они хранятся в целочисленных регистрах (за исключением передачи в качестве аргументов), все 8 байтов регистра являются значительными; любое ненулевое значение считается истинным

Поэтому для платформ, которые следуют за SysV ABI, мы можем быть уверены, что значение bool имеет значение 0/1.

Я искал документ ABI для MSVC, но, к сожалению, я ничего не нашел о bool .

Я скомпилировал следующее с clang ++ -O3 -S

 bool andbool(bool a, bool b) { return a && b; } bool andint(int a, int b) { return a && b; } 

Файл .s содержит:

 andbool(bool, bool): # @andbool(bool, bool) andb %sil, %dil movl %edi, %eax retq andint(int, int): # @andint(int, int) testl %edi, %edi setne %cl testl %esi, %esi setne %al andb %cl, %al retq 

Очевидно, что это версия bool, которая делает меньше.