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

Ответ 1

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

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

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

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

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

Компиляторы иногда используют это, например. для bool → int преобразование даже gcc 4.4 просто равно нулю - продолжается до 32-битного (movzx eax, dil). Clang и MSVC тоже делают это. Правила C и С++ требуют, чтобы это преобразование производило 0 или 1, поэтому это поведение является безопасным, если всегда безопасно предположить, что аргумент bool arg или глобальная переменная имеет значение 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 проводник компилятора Godboltдля gcc4.6/4.7 и clang/MSVC. См. Также Matt Godbolt CppCon2017 talk Что мой компилятор для меня сделал в последнее время? Откручивание крышки компилятора)

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 or dil, sil/mov eax, edi является глупым: он гарантировал, что на Nehalem или более раннем Intel при чтении edi после записи dil он будет работать с неполным регистратором, и у него будет худший размер кода от необходимости REX префикс для использования 8-разрядной части edi. Лучшим выбором может быть or dil,sil/movzx eax, dil, если вы хотите избежать чтения любых 32-разрядных регистров в случае, если ваш вызывающий абонент оставил некоторые регистры, проходящие через arg, с "грязными" частичными регистрами.)

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

logical_or PROC                     ; x86-64 MSVC CL19
    test     cl, cl                 ; Windows ABI passes args in ecx, edx
    jne      SHORT [email protected]_or
    test     dl, dl
    jne      SHORT [email protected]_or
    xor      al, al                 ; missed peephole: xor eax,eax is strictly better
    ret      0
[email protected]_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; }. Он поддерживает int (с movzx) и использует or для установки флагов в соответствии с побитовым ИЛИ. Это глупо по сравнению с or dil,sil/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;
}

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

Выглядит достаточно просто; вы надеетесь, что интеллектуальный компилятор сделает это без разветвления с помощью одного test/cmov. x86 test команда устанавливает флаги в соответствии с поразрядным И. Это инструкция 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 и меньше, поэтому его используют компиляторы.

Версия Clang строго хуже моей рукописной версии. (Обратите внимание, что это требует, чтобы вызывающий нуль расширил аргументы 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 ночной код для этого разветвляется, как и предыдущие версии 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 [email protected]
        mov      eax, r8d       ; retval = x
        test     dl, dl         ; b
        jne      SHORT [email protected]
[email protected]:
        mov      eax, r9d       ; retval = y
[email protected]:
        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 [email protected]
    test     dl, dl
    je       SHORT [email protected]
    mov      al, 1              ; ab = 1

    test     al, al             ;; and then test/cmov on an immediate constant!!!
    cmovne   r9d, r8d
    mov      eax, r9d
    ret      0
[email protected]:
    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 до 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

Ответ 2

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

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

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

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

Булевы или:

bool fn(bool a, bool b) {
    return a||b;
}

0000000000000000 <fn(bool, bool)>:
   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 <fn(bool)>:
   0:   40 0f b6 c7             movzx  eax,dil
   4:   c3                      ret    

Снова не проверять, просто перемещать.

Преобразовать char в bool:

bool fn(char a) {
    return a;
}

0000000000000000 <fn(char)>:
   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 conversion. Эта операция может быть простой mov, если значение bool не будет ограничено 0/1. Для всех других операций текущий подход одинаково хорош или лучше.

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

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

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

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

Ответ 3

Я скомпилировал следующее с 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, которая делает меньше.