Joh*_*nAl 3 c++ optimization assembly x86-64 micro-optimization
我的问题是，在这种情况下，编译器在做什么，这比我认为的可能更多地优化了代码方式。
鉴于此枚举：
enum MyEnum {
Entry1,
Entry2,
... // Entry3..27 are the same, omitted for size.
Entry28,
Entry29
};
而这个功能：
bool MyFunction(MyEnum e)
{
if (
e == MyEnum::Entry1 ||
e == MyEnum::Entry3 ||
e == MyEnum::Entry8 ||
e == MyEnum::Entry14 ||
e == MyEnum::Entry15 ||
e == MyEnum::Entry18 ||
e == MyEnum::Entry21 ||
e == MyEnum::Entry22 ||
e == MyEnum::Entry25)
{
return true;
}
return false;
}
对于该函数，当使用-Ox优化标志（Godbolt）编译时，MSVC会生成此程序集：
bool MyFunction(MyEnum) PROC ; MyFunction
cmp ecx, 24
ja SHORT $LN5@MyFunction
mov eax, 20078725 ; 01326085H
bt eax, ecx
jae SHORT $LN5@MyFunction
mov al, 1
ret 0
$LN5@MyFunction:
xor al, al
ret 0
用-O3标志编译时，Clang生成类似的程序集（稍微好一点，跳转少一点）：
MyFunction(MyEnum): # @MyFunction(MyEnum)
cmp edi, 24
ja .LBB0_2
mov eax, 20078725
mov ecx, edi
shr eax, cl
and al, 1
ret
.LBB0_2:
xor eax, eax
ret
这是怎么回事 我看到，即使我向该函数添加了更多的枚举比较，生成的程序集实际上也不会变成“更多”，只有这个幻数（20078725）会改变。该数字取决于函数中发生了多少枚举比较。我不明白这里发生了什么。
我之所以这样看，是因为我想知道按上述方式编写上述函数还是按如下方式比较好：
bool MyFunction(MyEnum) PROC ; MyFunction
cmp ecx, 24
ja SHORT $LN5@MyFunction
mov eax, 20078725 ; 01326085H
bt eax, ecx
jae SHORT $LN5@MyFunction
mov al, 1
ret 0
$LN5@MyFunction:
xor al, al
ret 0
这将导致使用MSVC生成此程序集：
bool MyFunction2(MyEnum) PROC ; MyFunction2
xor edx, edx
mov r9d, 1
cmp ecx, 24
mov eax, edx
mov r8d, edx
sete r8b
cmp ecx, 21
sete al
or r8d, eax
mov eax, edx
cmp ecx, 20
cmove r8d, r9d
cmp ecx, 17
sete al
or r8d, eax
mov eax, edx
cmp ecx, 14
cmove r8d, r9d
cmp ecx, 13
sete al
or r8d, eax
cmp ecx, 7
cmove r8d, r9d
cmp ecx, 2
sete dl
or r8d, edx
test ecx, ecx
cmove r8d, r9d
test r8d, r8d
setne al
ret 0
由于我不了解在第一种情况下会发生什么，因此我无法真正判断哪种情况在我的情况下更有效。
很聪明！与24的第一个比较是进行粗略的范围检查-如果大于24或小于0，它将退出紧急状态；这很重要，因为后面跟在魔术数字上的指令对操作数范围的上限为[0，31]。
对于其余部分，幻数只是一个位掩码，其位对应于设置的“良好”值。
>>> bin(20078725)
'0b1001100100110000010000101'
很容易发现第一个和第三个位（从1开始，从右开始），第8、14、15，...
MSVC使用BT（位测试）指令和分支“直接”检查它，而用clang对其进行适当的移位（以使相关位处于最低顺序位置），并使其与零进行与（避免分支）。 。
与clang版本相对应的C代码如下所示：
bool MyFunction(MyEnum e) {
if(unsigned(e) > 24) return false;
return (20078725 >> e) & 1;
}
至于MSVC版本，它更像
inline bool bit_test(unsigned val, int bit) {
return val & (1<<bit);
}
bool MyFunction(MyEnum e) {
if(unsigned(e) > 24) return false;
return bit_test(20078725, e);
}
（我将bit_test函数分开，以强调它实际上是汇编中的一条指令，该val & (1<<bit)东西与原始汇编没有对应关系。
对于if基于代码的代码，这是非常糟糕的-它使用大量CMOV并将结果进行或运算，这既是较长的代码，也可能会序列化执行。我怀疑相应的clang代码会更好。OTOH，您是使用按位OR（|）而不是语义上更正确的逻辑OR（||）编写此代码的，并且编译器严格遵循您的命令（通常为MSVC）。
相反，另一种可能的尝试是switch-但与第一个代码段已经生成的代码相比，我认为并没有太多收获，对我来说这看起来不错。
好的，针对所有编译器对所有版本进行快速测试，我们可以看到：
switch情况外，gcc的作用与CLang基本相同。switch 结果是多种多样的：
啊，古老的立即位图技巧。
\n\nGCC 也这样做，至少对于交换机来说是这样。\n x86 asm casetable 实现。不幸的是，GCC9 在某些情况下会出现回归：https://gcc.gnu.org/bugzilla/show_bug.cgi ?id=91026#c3 #c3 ；GCC8 及更早版本做得更好。
\n\n使用它的另一个例子，这次是代码高尔夫（最少字节的代码，在本例中为 x86 机器代码）来检测某些字母：用户欣赏挑战#1：Dennis \xe2\x99\xa6
\n\n基本思想是使用输入作为真/假结果位图的索引。
\n\n首先，您必须进行范围检查，因为位图是固定宽度的，并且 x86 移位会包含移位计数。我们不希望高输入别名到某些应返回 true 的范围中。 cmp edi, 24/ja是在做。
（例如，如果最低值和最高值之间的范围true是从 120 到 140，则可能会以sub edi,120范围移动 之前的所有内容开始cmp。）
然后，您使用bitmap & (1<<e)（指令bt）或(bitmap >> e) & 1（shr/ and）来检查位图中的位，该位告诉您该值是否应e返回 true 或 false。
实现该检查的方法有很多种，逻辑上等效，但性能有所不同。
\n\n如果范围大于 32，则必须使用 64 位操作数大小。如果它比 64 宽，编译器可能根本不会尝试此优化。或者对于某些范围较窄的条件仍可能这样做。
\n\n使用更大的位图（在 .rodata 内存中）是可能的，但大多数编译器可能不会为您发明。使用bt [mem],reg（低效）或手动索引双字并以与此代码检查立即位图相同的方式进行检查。如果您有很多高熵范围，可能值得检查 2x 64 位立即位图，有分支或无分支......
Clang/LLVM 还有其他技巧可以有效地比较多个值（当命中哪个值并不重要时），例如将一个值广播到 SIMD 寄存器中并使用打包比较。这并不依赖于密集范围内的值。（Clang 对于 7 次比较生成的代码比 8 次比较生成的代码更差）
\n\n\n\n\n这对代码的优化程度超出了我的想象。
\n
这些类型的优化来自聪明的人类编译器开发人员，他们注意到源代码中的常见模式并想出巧妙的方法来实现它们。然后让编译器识别这些模式并转换其程序逻辑的内部表示以使用该技巧。
\n\n事实证明switch，类似 switch 的if()语句很常见，并且积极的优化也很常见。
编译器远非完美，但有时它们确实接近人们经常声称的那样。编译器将为您优化您的代码，以便您可以以人类可读的方式编写代码，并且仍然使其以接近最佳的状态运行。在小范围内有时也是如此。
\n\n\n\n\n由于我不明白第一种情况会发生什么，因此我无法真正判断哪个在我的情况下更有效。
\n
立即位图的效率要高得多。两者都没有数据内存访问，因此没有缓存未命中加载。唯一“昂贵”的指令是变量计数移位（主流 Intel 上为 3 uop，因为 x86 令人讨厌的 FLAGS 设置语义；BMI2shrx只有 1 uop，避免必须将mov数字添加到ecx。） https://agner .org/优化. 并查看https://stackoverflow.com/tags/x86/info中的其他性能分析链接。
cmp/cmov 链中的每条指令至少有 1 个 uop，并且每条指令都有相当长的依赖链，cmov因为 MSVC 没有费心将其分成 2 个或更多并行链。但无论如何，它只是大量的微指令，远远超过位图版本，因此吞吐量（无序执行与周围代码重叠工作的能力）和延迟都更差。
bt也很便宜：现代 AMD 和 Intel 上 1 uop。（bts、btr、btc在 AMD 上为 2，在 Intel 上仍为 1）。
立即位图版本中的分支可能是 /setna以and使其无分支，但特别是对于此枚举定义，编译器期望它将在范围内。e <= 31它可以通过仅要求而不是增加分支的可预测性e <= 24。
由于enum最多只能达到 29，并且 IIRC 它的 UB 具有超出范围的枚举值，因此实际上可以将其完全优化掉。
即使该e>24分支的预测效果不是很好，但总体而言仍然可能更好。考虑到当前的编译器，我们只能在令人讨厌的 cmp/cmov 链或分支 + 位图之间进行选择。除非将 asm 逻辑重新转换为 C 语言，以便手持编译器生成我们想要的 asm，否则我们可能可以使用 AND 或 CMOV 来实现无分支，以使其对于超出范围的情况始终为零e。
但如果我们幸运的话，配置文件引导的优化可能会让一些编译器使位图范围检查无分支。（在 asm 中， cl > 31 或 63 的行为shl reg, cl是明确定义的：在 x86 上，它只是屏蔽计数。在 C 等价物中，您可以使用bitmap >> (e&31)which 仍然可以优化为shr；编译器知道 x86 shr 屏蔽了计数，因此它们可以优化它。但不适用于其他使移位计数饱和的 ISA...）
有很多方法可以实现位图检查，它们几乎是等效的。例如，您甚至可以使用 的 CF 输出shr，根据最后移出的位进行设置。至少如果你确保 CF 提前有一个已知的状态cl=0案例的状态。
当您想要整数bool结果时，右移似乎比bt/更有意义setcc，但shr在 Intel 上花费 3 uops，实际上最好使用bt reg,reg/ setc al。 特别是如果您只需要一个bool, 并且可以使用 EAX 作为位图目标，那么 EAX 的先前值肯定已经准备好了setcc。（避免对一些不相关的早期 dep 链的错误依赖。）
顺便说一句，MSVC 还有其他愚蠢之处：如What is the best way to set a register to zero in x86 assembly: xor, mov or and? 解释说，与你想要将 AL 归零xor al,al相比，这完全是愚蠢的。xor eax,eax如果您不需要保留 RAX 的高字节不变，请使用归零惯用法将整个寄存器归零。
当然，仅仅为了返回 0 或返回 1 进行分支是没有意义的，除非您期望它非常可预测并且想要打破数据依赖性。我希望setc al阅读 CF 结果会更有意义bt
| 归档时间： |
|
| 查看次数： |
143 次 |
| 最近记录： |