编译器中的布尔值为8位。 对他们的操作是低效的吗?
我正在阅读Agner Fog的“ 用C ++优化软件 ”(针对Intel,AMD和VIA的x86处理器),它在第34页
布尔variables存储为8位整数,值为0表示为false,1表示为true。 布尔variables是超定的,因为所有具有布尔variables作为input的运算符都检查input是否具有除0或1之外的其他值,但具有布尔值作为输出的运算符不能产生除0或1之外的其他值。作为input的布尔variables效率低于必要的。
这是今天仍然如此,编译器是什么? 你能举个例子吗? 作者说
如果能够确定地知道操作数不具有除0和1之外的其他值,则可以使布尔操作更加高效。编译器没有做出这样的假设的原因是如果variables可能具有其他值未初始化或来自不明的来源。
这是否意味着,如果我拿一个函数指针bool(*)()
为例,并调用它,那么对它的操作产生低效的代码? 或者,当我通过解引用指针或从引用读取来访问布尔值,然后对其进行操作时,情况就是这样吗?
TL:DR :目前的编译器在执行诸如此类的操作时仍然存在bool
错误优化
(a&&b) ? x : y
(a&&b) ? x : y
。 但是,为什么不是他们不假设0/1,他们只是在这个吸吮。
bool
许多用途是为本地人或内联函数,所以布尔化为0/1可以在原始条件下优化和分支(或cmov或其他)。 只需要考虑优化bool
input/输出,当它必须通过/返回一些不内联或真正存储在内存中的东西。
可能的优化准则 :将来自外部资源(函数参数/内存)的bool
与按位运算符(如a&b
。 MSVC和ICC做得更好。 IDK,如果当地bool
的情况更糟。 请注意, a&b
仅相当于bool
a&&b
,而不是整数types。 2 && 1
是真的,但2 & 1
是0,这是错误的。 按位或没有这个问题。
IDK,如果这个指导方针会损害那些从函数内部(或内联的)比较中设置的本地人。 例如,它可能会导致编译器实际制作整数布尔值,而不是直接使用比较结果。 另外请注意,它似乎没有帮助当前的gcc和铛。
是的,x86上的C ++实现以一个始终为0或1的字节存储bool
(至less在编译器必须尊重ABI /调用约定的函数调用边界上)。
编译器有时会利用这个优势,例如,对于bool
– > int
转换,即使gcc 4.4只是零延伸到32位( movzx eax, dil
)。 铿锵和MSVC也是这样做的。 C和C ++规则要求这种转换产生0或1,所以这种行为是唯一的,如果总是假定一个bool
函数arg或全局variables具有0或1的值是安全的。
即使是旧的编译器,通常也会将其用于bool
– > int
,但在其他情况下不会。 因此,Agner错误地认为他的理由是:
编译器之所以没有做这样的假设,是因为如果这些variables是未初始化的或者来自未知的来源,这些variables可能具有其他的值。
MSVC CL19的确使代码,假设bool
函数参数为0或1,所以Windows x86-64 ABI必须保证这一点。
在x86-64 System V ABI (由Windows以外的其他应用程序使用)中,修订版本0.98的更改日志显示“指定_Bool
(aka bool
)在调用程序中被bool
”。 我想即使在这个变化之前,编译器也是假设它,但这只是logging了编译器已经依赖的东西。 x86-64 SysV ABI中的当前语言是:
3.1.2数据表示
当存储在内存对象中时,布尔值被存储为单字节对象,其值始终为0(假)或1(真)。 当存储在整数寄存器中(除了作为parameter passing外),寄存器的所有8个字节都是有效的; 任何非零值都被认为是正确的。
第二句话是荒谬的:ABI没有告诉编译器如何将函数中的寄存器中的内容存储在不同的编译单元(内存/函数参数和返回值)之间的边界上。 我刚才在github页面上报告过这个ABI缺陷。
3.2.3parameter passing :
当
_Bool
types的值返回或传递到寄存器或栈中时,位0包含真值,位1至7应为零16 。(脚注16):其他位是未指定的,因此这些值的消费者侧可以依靠0或1被截断为8位。
i386 System V ABI中的语言与IIRC相同。
任何编译器假设0/1(例如转换为int
)但在其他情况下无法利用它的优化器都会错过 。 不幸的是,这样的错失优化依然存在,尽pipe比Agner写的关于编译器总是重新布尔化的段落要less得多。
(在gb4.6 / 4.7的Godbolt编译器资源pipe理器上的Source + asm和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
是愚蠢的:在写入dil
,在读取edi
时,保证会在Nehalem或更早的Intel上导致部分寄存器失速,并且由于需要REX前缀而使用较低的代码大小如果你想避免读取任何32位寄存器,如果你的调用者留下了一些带有“脏”部分寄存器的arg-passing寄存器movzx eax, dil
那么更好的select可能是or dil,sil
movzx eax, dil
or dil,sil
/ movzx eax, dil
。
MSVC发出这个代码,单独检查a
然后b
,完全没有利用任何东西 ,甚至使用xor al,al
而不是xor eax,eax
。 所以它在大多数CPU上( 包括Haswell / Skylake,它们不会将整个寄存器中的低8位部分寄存器,只有AH / BH / … )错误地依赖于旧的eax
值。 这是愚蠢的。 曾经使用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也没有利用input已知的0/1特性,它只是使用一个or
一个指令根据两个input的按位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
即使对于bool bitwise_or(bool a, bool b) { return a|b; }
ICC也会发出相同的代码bool bitwise_or(bool a, bool b) { return a|b; }
bool bitwise_or(bool a, bool b) { return a|b; }
。 它促进int
(与movzx
),并使用or
设置标志根据按位或。 这是愚蠢的相比, or dil,sil
setne al
or dil,sil
/ setne al
。
对于bitwise_or
,MSVC只是使用一个or
指令(在每个input上的movzx
之后),但无论如何不会重新布尔化。
错过当前gcc / clang的优化:
只有ICC / MSVC用上面这个简单的函数做了哑代码,但是这个函数还是给gcc和clang带来了麻烦:
int select(bool a, bool b, int x, int y) { return (a&&b) ? x : y; }
在Godbolt编译器资源pipe理器上的源代码+ asm (相同的源代码,select不同的编译器与上一次)。
看起来很简单, 你希望一个聪明的编译器可以用一个test
/ cmov
无cmov
执行它。 x86的test
指令根据按位AND设置标志。 这是一个AND指令,实际上并没有写入目的地。 (就像cmp
是不写目的地的子)。
# 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编译器资源pipe理器上每天编译gcc和clang也会使代码更加复杂,分别检查每个布尔值。 他们知道如何优化bool ab = a&&b;
如果你返回ab
,但是即使这样写(用一个单独的布尔variables来保存结果)也不能设法使它们成为不吸引的代码。
请注意, test same,same
完全等同于cmp reg, 0
,并且更小,所以这是编译器使用的。
铿锵的版本严格比我手写的版本更差。 (请注意,它要求调用者将bool
参数零扩展到32位, 就像它对于窄整数types作为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
海湾合作委员会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调用约定,其中整型参数在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有相同的错误优化testing/厘米的寄存器,只是设置为一个常数)。
像往常一样,gcc和clang不会使代码和MSVC一样糟糕; 他们为select()
做了同样的东西,但仍然不好,但至less试图帮助他们不会像MSVC那样变得更糟糕。
结合bool
和按位运算符有助于MSVC和ICC
在我非常有限的testing中, |
和似乎比||
更好地工作 和MSVC和ICC &&
。 使用编译器+编译选项查看编译器输出以查找自己的代码,以查看发生的情况。
int select_bitand(bool a, bool b, int x, int y) { return (a&b) ? x : y; }
海湾合作委员会仍然分开分别在两个input单独的test
,与其他版本的select
相同的代码。 铛仍然做两个单独的test/cmov
,同样的asm其他来源版本。
MSVC通过和优化正确,击败所有其他编译器(至less在独立的定义):
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
我认为情况并非如此。
首先,这个推理是完全不可接受的:
编译器之所以没有做这样的假设,是因为如果这些variables是未初始化的或来自未知的来源,这些variables可能具有其他的值。
让我们来看看一些代码(使用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。 它从不检查其有效性。
关于效率:我认为布尔是最佳的。 我可以想象的唯一情况是,这种方法不是最佳的是char-> bool转换。 如果bool值不会被限制为0/1,那么这个操作可能是一个简单的mov。 对于所有其他行动,目前的做法同样好,或更好。
编辑:彼得·科德斯提到ABI。 这里是来自AMD64的System V ABI的相关文本(i386的文本是相似的):
当存储在内存对象中时,布尔值被存储为单字节对象,其值始终为0(假)或1(真) 。 当存储在整数寄存器中(除了作为parameter passing外),寄存器的所有8个字节都是有效的; 任何非零值都被认为是正确的
因此,对于遵循SysV ABI的平台,我们可以确定bool
具有0/1的值。
我search了MSVC的ABI文档,但不幸的是我没有find关于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
显然,这是布尔版本正在减less。