c ++-在编译器中为8位的布尔值。 对它们的操作效率低下吗?

我正在阅读Agner Fog的“ C ++优化软件”(特定于Intel,AMD和VIA的x86处理器),它在第34页上说

布尔变量存储为8位整数,false值为0,true值为1。 从所有具有布尔值的运算符的意义上来说,布尔变量是超定的 变量作为输入检查输入是否具有0或1以外的其他值,但运算符 具有布尔值作为输出,除了0或1之外,不能产生其他任何值。这使操作成为可能 布尔变量作为输入的效率比必要的低。

在今天和什么编译器上仍然如此吗? 你能举个例子吗? 作者指出

如果布尔运算可以使效率更高 可以肯定地知道操作数除0和1外没有其他值。原因 为什么编译器没有做出这样的假设是变量可能具有其他 未初始化或来自未知来源的值。

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

Johannes Schaub - litb asked 2020-06-27T03:28:29Z
3个解决方案
68 votes

TL:DR:当前的编译器在执行类似以下操作时仍具有bool bitwise_or(bool a, bool b) { return a|b; }遗漏的优化
int。但是原因不是他们不假设0/1,他们只是对此感到suck恼。

bool bitwise_or(bool a, bool b) { return a|b; }的许多用途是用于本地函数或内联函数,因此将int/movzx布尔化可以在原始条件下优化分支和分支(或cmov或其他功能)。 当不必在非内联或真正存储在内存中的某些东西上传递/返回它时,只需担心优化or输入/输出。

可能的优化指南:将外部源(函数args /内存)中的bool bitwise_or(bool a, bool b) { return a|b; }int之类的按位运算符结合在一起。MSVC和ICC对此做得更好。 如果本地movzx的情况更糟,则使用IDK。 注意or仅等效于movzx eax, dilor dil,sil,而不是整数类型。 2 && 1为true,但2 & 1为0,为false。 按位或不存在此问题。

IDK(如果此指南对通过函数内的比较(或内联的东西)设置的本地人有害)。 例如。 它可能会导致编译器实际生成整数布尔值,而不仅仅是在可能的情况下直接使用比较结果。 还要注意,它对当前的gcc和clang似乎没有帮助。


是的,x86上的C ++实现将bool bitwise_or(bool a, bool b) { return a|b; }的字节存储为始终为0或1(至少在函数调用边界上,编译器必须遵守需要此操作的ABI /调用约定)。

编译器有时确实会利用这一点,例如 对于bool bitwise_or(bool a, bool b) { return a|b; }-> int的转换,即使gcc 4.4只是零扩展到32位(movzx)。 Clang和MSVC也这样做。 C和C ++规则要求此转换产生0或1,因此,只有在始终可以安全地假定or函数arg或全局变量具有0或1值的情况下,此行为才是安全的。

即使是旧的编译器也确实在bool bitwise_or(bool a, bool b) { return a|b; }-> int中利用了它,但在其他情况下则没有。 因此,阿格纳(Agner)在说出原因时是错误的:

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


MSVC CL19确实制作了假定bool bitwise_or(bool a, bool b) { return a|b; }函数args为0或1的代码,因此Windows x86-64 ABI必须对此进行保证。

在x86-64 System V ABI(除Windows以外的所有版本中使用)中,修订版0.98的变更日志显示“指定在调用方处对bool bitwise_or(bool a, bool b) { return a|b; }(也称为int)进行布尔化”。 我认为,即使在进行此更改之前,编译器仍在进行假设,但这只是记录了编译器已经依赖的内容。 x86-64 SysV ABI中的当前语言是:

3.1.2数据表示

布尔值存储在内存对象中时,将以单字节对象的形式存储,其值始终为0(false)或1(true)。 当存储在整数寄存器中(除了作为参数传递时)时,寄存器的所有8个字节都是有效的。 任何非零值都被视为true。

第二句话是胡说八道:ABI并没有告诉编译器如何在函数内部的寄存器中存储内容,而只是在不同编译单元之间的边界(内存/函数args和返回值)进行存储。 我不久前在维护它的github页面上报告了此ABI缺陷。

3.2.3参数传递:

当类型bool bitwise_or(bool a, bool b) { return a|b; }的值返回或传递到寄存器或堆栈中时,位0包含真值,位1至7应为零16。

(脚注16):其他位未指定,因此这些值的使用方在被截断为8位时可以依靠它为0或1。

i386 System V ABI中的语言是相同的,即IIRC。


任何一件事假设0/1的编译器(例如,转换为bool bitwise_or(bool a, bool b) { return a|b; }),但在其他情况下却无法利用它,则会错过优化。 不幸的是,这种遗漏的优化仍然存在,尽管它们比Agner写关于编译器的段落总是重新布尔化的情况要少。

(Godbolt编译器资源管理器中的gcc4.6 / 4.7和clang / MSVC的Source + asm。另请参见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都没有重新布尔bool bitwise_or(bool a, bool b) { return a|b; },但确实错过了gcc4.7所做的优化:(还有其他答案中所示的clang和更高版本的编译器):

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

(Clang的bool bitwise_or(bool a, bool b) { return a|b; }/int很愚蠢:在编写or后读取movzx后,确保在Nehalem或更早的Intel上导致部分寄存器停顿,并且由于需要REX前缀来使用edi的低8部分而导致代码大小更糟。 如果您想避免读取任何32位寄存器,以防您的调用者留下一些带有“脏”部分寄存器的arg传递寄存器,则更好的选择可能是or dil,sil /movzx eax, dil。)

MSVC发出此代码,分别检查bool bitwise_or(bool a, bool b) { return a|b; }int,完全无法利用任何东西,甚至使用bool bitwise_or(bool a, bool b) { return a|b; }而不是int。因此,它对大多数CPU(包括Haswell / Skylake)上movzx的旧值有错误的依赖性。 请勿重命名低8位部分寄存器(与整个寄存器分开,仅重命名AH / BH / ...)。 这真是愚蠢。 使用or的唯一原因是当您明确想要保留高字节时。

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性质,它仅使用bool bitwise_or(bool a, bool b) { return a|b; }指令根据两个输入的按位或来设置标志,而使用int产生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设置标志。 与movzx/bool相比,这是愚蠢的。

对于movzx,MSVC只会使用bool指令(在每个输入int之后),但是无论如何都不会重新布尔化。


当前gcc / clang中缺少优化:

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

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

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

看起来很简单; 您希望智能编译器可以使用movzx/bool无分支地完成此任务。 x86的int指令根据按位AND设置标志。 这是一条AND指令,实际上并未写入目的地。 (就像&&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的日常构建也会产生更复杂的代码,并分别检查每个布尔值。 他们知道如何优化movzx(如果您返回bool),但是即使以这种方式编写(使用单独的布尔变量来保存结果)也无法使他们手忙脚乱,使代码变得不那么糟糕。

请注意,movzxbool完全等效,并且更小,因此它是编译器使用的。

Clang的版本比我的手写版本严格。 (请注意,它要求调用者将movzx args零扩展到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也产生分支代码,但分支之后都带有movzx指令。

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一样糟糕; 他们使用与movzx相同的asm,效果仍然不佳,但至少尝试帮助他们并不会像使用MSVC一样使情况更糟。


movzx与按位运算符结合使用可帮助MSVC和ICC

在我非常有限的测试中,对于MSVC和ICC,movzxbool似乎比int&&更好地工作。 使用您的编译器+编译选项查看您自己的代码的编译器输出,以了解发生了什么。

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

Gcc仍在两个输入的单独movzxs上分别分支,其代码与bool的其他版本相同。clang仍执行两个单独的movzx,与其他源版本相同的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
Peter Cordes answered 2020-06-27T03:32:04Z
7 votes

我认为并非如此。

首先,这种推理是完全不能接受的:

编译器未作此假设的原因是 如果变量未初始化,则它们可能具有其他值或 来自未知来源。

让我们检查一些代码(与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检查,简单的bool

将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,则该操作可能很简单。 对于所有其他操作,当前的方法同样不错,甚至更好。


编辑:彼得·科德斯(Peter Cordes)提到了ABI。 这是AMD64的System V ABI中的相关文本(i386的文本与此类似):

布尔值存储在存储对象中时,将其存储为单个字节 对象,其值始终为0(false)或1(true)。 什么时候 存储在整数寄存器中(除了作为参数传递外),所有8 寄存器的字节是有效的; 考虑任何非零值 真正

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

我搜索了MSBI的ABI文档,但不幸的是,我没有找到有关bool的任何信息。

geza answered 2020-06-27T03:33:31Z
0 votes

我用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版本的作用要小一些。

Tony Delroy answered 2020-06-27T03:33:59Z
translate from https://stackoverflow.com:/questions/47243955/boolean-values-as-8-bit-in-compilers-are-operations-on-them-inefficient