编译器中的布尔值为8位。对它们的操作效率低吗？

Question

我正在读Agner Fog的“C++优化软件”（专门针对Intel、AMD和VIA的x86处理器），它在第34页上说

布尔变量存储为8位整数，值0表示false，1表示true。布尔变量是超定的，因为所有以布尔变量为输入的运算符都会检查输入是否有除0或1以外的任何其他值，但以布尔变量为输出的运算符只能产生除0或1以外的任何其他值。这使得以布尔变量作为输入的操作效率低于所需的效率。

如果可以肯定地知道操作数除了0和1之外没有其他值，则可以使布尔运算更有效。编译器不做这样一个假设的原因是，如果变量未初始化或者来自未知的源，那么它们可能有其他值。

这是否意味着如果我以函数指针bool(*)()为例并调用它，那么对它的操作会生成低效的代码？或者当我通过取消引用指针或从引用中读取然后对其进行操作来访问布尔值时，情况是这样的吗？

Answer 1

TL：DR：当前编译器在执行
(A&&B)之类的操作时，仍然存在bool漏选优化？x:Y。但原因并不是他们不假设0/1，他们只是在这个方面很烂。

bool的许多用法都是用于局部函数或内联函数，因此将booleanizing为0/1可以在原始条件上优化离开和分支（或cmov或其他）。当bool输入/输出必须通过不内联或不真正存储在内存中的东西传递/返回时，只需担心优化它。

可能的优化准则：将来自外部源（函数参数/内存）的bools与按位运算符结合起来，如a&b。MSVC和ICC在这方面做得更好。如果它对本地bools更糟的话。当心a&b只相当于bool的a&b，而不是整数类型。2&1为true，但2&1为0，为false。按位或不存在此问题。

如果这个指导原则会对在函数（或内联的东西）内进行比较而设置的局部变量造成伤害。例如。这可能导致编译器在可能的情况下实际生成整数布尔值，而不是直接使用比较结果。还要注意，它似乎对当前的gcc和clang没有帮助。

是的，x86上的C++实现将bool存储在一个始终为0或1的字节中（至少在函数调用边界中，编译器必须遵守要求这样做的ABI/调用约定）

编译器有时会利用这一点，例如，对于bool->int转换，甚至gcc 4.4也只是零扩展到32位(movzx eax,dil)。Clang和MSVC也会这样做。C和C++规则要求这种转换产生0或1，因此只有在假定bool函数参数或全局变量具有0或1值总是安全的情况下，这种行为才是安全的。

编译器不做这样一个假设的原因是，如果变量未初始化或者来自未知的源，那么它们可能有其他值。

MSVC CL19确实会生成假定bool函数参数为0或1的代码，因此Windows x86-64 ABI必须保证这一点。

在x86-64 System V ABI（除Windows以外的所有工具都使用）中，0.98修订版的更改日志中说：“指定_bool（又名bool)在调用者处是booleanized的。”我想即使在那次更改之前，编译器就已经假设了，但这只是记录了编译器已经依赖的东西。x86-64 SysV ABI中的当前语言为：

布尔值存储在内存对象中时，存储为单字节对象，其值始终为0（false）或1（true）。当存储在整数寄存器中时（作为参数传递除外），寄存器的所有8个字节都是有效的；任何非零值都视为true。

第二句话是无稽之谈：ABI没有责任告诉编译器如何在函数内部的寄存器中存储东西，只能在不同编译单元（内存/函数参数和返回值）之间的边界处存储。我不久前在维护它的github页面上报告了这个ABI缺陷。

3.2.3参数传递：

任何一个编译器假设0/1（例如转换为int)，但在其他情况下却没有利用它，那么它就错过了优化。不幸的是，这种错过的优化仍然存在，尽管它们比Agner写的关于编译器总是重新布尔化的段落要少见。

（源码+asm关于GCC4.6/4.7的Godbolt编译器资源管理器和clang/msvc。另请参见Matt Godbolt的CppCon2017谈话“我的编译器最近为我做了什么？打开编译器的盖子”）

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也没有重新布尔化b，但它确实错过了GCC4.7所做的优化：（以及clang和以后的编译器，如其他答案所示）：

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

（Clang的或dil,SIL/MOV eax,EDI是愚蠢的：在写入dil后读取EDI时，它保证会导致Nehalem或更早的Intel上的部分寄存器停止，并且由于需要REX前缀来使用EDI的低8部分，它的代码大小更差。如果您希望避免读取任何32位寄存器，以防调用方留下一些带有“脏”部分寄存器的arg传递寄存器，则最好选择或dil,SIL/MOVZX eax,dilMOVZX eax,dil。）

MSVC发出这个分别检查A然后检查B的代码，完全没有利用任何东西，甚至使用异或al,al代替异或eax,eax。因此，它对大多数CPU（包括Haswell/Skylake）上的eax的旧值有错误依赖，它们不会从整个寄存器中单独重命名低8的部分reg，只重命名ah/bh/...)。这太蠢了。使用异或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特性，它只是使用或指令根据两个输入的位或设置标志，并使用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

即使对于bool bitwise_or(bool a,bool b）{return ab；}，ICC也会发出相同的代码。它升级为int（使用movzx)，并使用或根据按位或设置标志。与或dil,SIL/Setneal相比，这是哑巴。

对于bitwise_or，MSVC只是使用一个或指令（在每个输入的movzx之后），但无论如何不会重新布尔化。

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

Godbolt编译器资源管理器上的源代码+ASM（相同的源代码，选择的编译器与上次不同）。

看起来很简单；您希望一个智能编译器能够用一个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

但即使是Godbolt编译器资源管理器上的gcc和clang的日常构建也会产生复杂得多的代码，分别检查每个布尔值。如果您返回ab，他们知道如何优化bool ab=a&b；，但即使是这样编写它（使用单独的布尔变量保存结果）也无法控制他们生成不糟糕的代码。

Clang的版本严格来说比我手写的版本还要差。（注意，它要求调用方将bool参数零扩展为32位，就像它对窄整数类型所做的那样，这是它和gcc实现的ABI的非官方部分，但只依赖于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 201 71110每晚都会为此编写分支代码，与较旧的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调用约定，其中整数参数位于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

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在一个刚刚设置为常数的寄存器上有相同的Test/CMOV漏选优化）。

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

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指令--将bool0扩展为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