编译器中的布尔值为8位.对他们的操作是否效率低下？

Question

我正在阅读Agner Fog的" 用C++优化软件 "(特定于英特尔,AMD和威盛的x86处理器),它在第34页说明

布尔变量存储为8位整数,值0表示false,1表示true.布尔变量是超定的,因为所有具有布尔变量作为输入的运算符检查输入是否具有除0或1之外的任何其他值,但是具有布尔值作为输出的运算符不能产生除0或1之外的其他值.布尔变量作为输入效率低于必要的效率.

这今天仍然适用于编译器吗？你能举个例子吗？作者说

如果确定操作数没有除0和1之外的其他值,则可以使布尔运算更有效.编译器没有做出这样的假设的原因是变量可能具有其他值,如果它们是未初始化或来自不明来源.

这是否意味着如果我拿一个函数指针bool(*)()作为示例并调用它,那么对它的操作会产生效率低下的代码？或者是通过取消引用指针或从引用读取然后对其进行操作来访问布尔值的情况？

Answer 1

TL:DR:bool当做类似的事情时,当前编译器仍然有错过优化
(a&&b) ? x : y.但其原因并不是他们不假设0/1,他们只是对此嗤之以鼻.

许多bool用于本地或内联函数的用法,因此boolean化为0/ 1可以在原始条件下优化离开和分支(或cmov或其他).只有bool当它必须通过不内联或真正存储在内存中的内容传递/返回时,才会担心优化输入/输出.

可能的优化准则:将bool来自外部源(函数args /内存)的s与按位运算符组合在一起a&b.MSVC和ICC做得更好.IDK如果对本地人来说更糟糕bool的话.注意a&b这只相当于a&&bfor bool,而不是整数类型. 2 && 1是的,但是2 & 10是假的.按位OR没有这个问题.

IDK,如果这个指南对于通过函数内部比较设置的本地人(或内联的东西)会受到伤害.例如,它可能会导致编译器实际生成整数布尔值,而不是仅在可能时直接使用比较结果.另请注意,它似乎对当前的gcc和clang没有帮助.

是的,x86上的C++实现存储bool在一个始终为0或1的字节中(至少跨越函数调用边界,其中编译器必须遵守需要此的ABI /调用约定.)

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

即使是旧编译器通常也会将其用于bool- > int,但在其他情况下则不然.因此,当他说:Agner说错的原因是:

编译器没有做出这样的假设的原因是,如果变量未初始化或来自未知来源,则变量可能具有其他值.

MSVC CL19确实生成假设bool函数args为0或1的代码,因此Windows x86-64 ABI必须保证这一点.

在x86-64 System V ABI(由除Windows之外的所有内容使用)中,修订版0.98的更改日志表示"指定_Bool(aka bool)在调用者处被boolean化." 我认为即使在这种变化之前,编译器也会假设它,但这仅仅记录了编译器已经依赖的内容.x86-64 SysV ABI中的当前语言是:

3.1.2数据表示

布尔值存储在存储器对象中时,存储为单字节对象,其值始终为0(假)或1(真).当存储在整数寄存器中时(除了作为参数传递),寄存器的所有8个字节都是重要的; 任何非零值都被认为是真的.

第二句话是胡说八道:ABI没有业务告诉编译器如何在函数内的寄存器中存储东西,只在不同编译单元之间的边界(内存/函数args和返回值).我不久前在github页面上报告了这个ABI缺陷.

3.2.3参数传递:

当_Bool在寄存器或堆栈中返回或传递type的值时,位0包含真值,位1到7应为零¹⁶.

(脚注16):未指定其他位,因此当截断为8位时,这些值的消费者侧可以依赖于0或1.

i386 System V ABI中的语言与IIRC相同.

任何假设为0/1(例如转换为int)但在其他情况下未能利用它的编译器都会错过优化.不幸的是,这种遗漏优化仍然存在,尽管它们比Agner写的关于编译器的段落总是重新布线时更罕见.

(源代码+ asm在Godbolt编译器浏览器上用于gcc4.6/4.7和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's or dil, sil/ mov eax, edi很傻:edi在写完后读取时dil,它确保在Nehalem或早期英特尔上造成部分寄存器停顿,并且由于需要REX前缀来使用edi的低8部分,因此代码大小更差.更好的选择可能是or dil,sil/ movzx eax, dil如果你想避免读取任何32位寄存器,以防你的调用者留下一些带有"脏"部分寄存器的arg传递寄存器.)

MSVC发出这个代码,a然后b单独检查,完全没有利用任何东西,甚至使用xor al,al而不是xor eax,eax.因此它依赖于eax大多数CPU 的旧值(包括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 $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指令根据两个输入的按位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,ICC也会发出相同的代码bool bitwise_or(bool a, bool b) { return a|b; }.它促进int(with movzx),并用于or根据按位OR设置标志.与or dil,sil/ 相比,这是愚蠢的setne al.

因为bitwise_or,MSVC只使用一条or指令(movzx在每次输入之后),但无论如何都不会重新布尔化.

当前gcc/clang中错过的优化:

只有ICC ​​/ MSVC使用上面的简单函数制作哑代码,但是这个函数仍然给gcc和clang带来麻烦:

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

Godbolt编译器资源管理器上的Source + asm (相同的源代码,与上次选择的不同编译器).

看起来很简单; 你希望一个聪明的编译器能用一个test/ 无分支地完成它cmov.x86的test指令根据按位AND设置标志.这是一条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和铛上Godbolt编译探险家让很多更复杂的代码,分别检查每一个布尔值.bool ab = a&&b;如果你返回它们,他们知道如何进行优化ab,但即使以这种方式编写它(用一个单独的布尔变量来保存结果)也无法将它们手工制作成不会产生的代码.

请注意,test same,same它完全等同于cmp reg, 0,并且更小,因此它是编译器使用的.

Clang的版本严格比我的手写版本差.(注意,它要求调用者将boolargs 零扩展为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 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 $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在仅设置为常量的寄存器上具有相同的test/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两个输入的单独s 上分支,与其他版本的代码相同select. clang仍然执行两个独立的test/cmov,与其他源版本相同的asm.

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指令,将bools 扩展为零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

Answer 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转换.如果bool值不限制为0/1,那么该操作可以是一个简单的mov.对于所有其他操作,当前的方法同样好或更好.

编辑:彼得科德斯提到ABI.这是AMD64 System V ABI的相关文本(i386的文字类似):

布尔值存储在存储器对象中时,存储为单字节对象,其值始终为0(假)或1(真).当存储在整数寄存器中时(除了作为参数传递),寄存器的所有8个字节都是重要的; 任何非零值都被认为是真的

因此,对于遵循SysV ABI的平台,我们可以确定a bool的值为0/1.

我搜索了MSVC的ABI文档,但不幸的是我没有找到任何关于bool.