编译器在这里做什么，允许通过很少的实际比较来完成许多值的比较？
What is the compiler doing here that allows comparison of many values to be done with few actual comparisons?
我的问题是编译器在这种情况下做了什么，它优化代码的方式比我想象的要多。
鉴于此枚举：
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;
}
对于该函数，MSVC 在使用 -Ox 优化标志 (Godbolt) 编译时生成此程序集：
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
这里发生了什么？我看到即使我向函数添加更多枚举比较，生成的程序集实际上并没有变成 "more"，只是这个幻数 (20078725) 发生了变化。该数字取决于函数中发生了多少枚举比较。我不明白这里发生了什么。
我之所以看这个是因为我想知道这样写函数是否好，或者像这样，按位比较：
bool MyFunction2(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;
}
这将导致生成带有 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]。
对于其余部分，幻数只是一个位掩码，其位对应于 "good" 值集。
>>> bin(20078725)
'0b1001100100110000010000101'
很容易找出第一个和第三个位（从 1 开始从右数）组，第 8、14、15 位，...
MSVC 使用 BT（位测试）指令和分支检查它 "directly"，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 和 OR 将结果放在一起，这都是更长的代码，并且可能会序列化执行。我怀疑相应的 clang 代码会更好。 OTOH，您使用按位或（|）而不是语义上更正确的逻辑或（||）编写此代码，并且编译器严格遵循您的命令（典型的 MSVC）。
另一种尝试的可能性是 switch - 但我认为与已经为第一个代码段生成的代码相比没有太多收获，这对我来说看起来很不错。
好的，做a quick test with all the versions against all compilers，我们可以看到：
- 上述 CLang 输出的 C 翻译在所有编译器中产生几乎相同的代码（= 到 clang 输出）；类似的 MSVC 翻译；
- 按位或版本与 CLang 和 gcc 中的逻辑或版本相同（=好）；
- 一般来说，除了
switch 情况外，gcc 与 CLang 做的事情基本相同；
switch 结果各不相同：
- CLang 做得最好，生成完全相同的代码；
- gcc 和 MSVC 都生成基于 jump-table 的代码，在这种情况下不太好；然而：
- gcc 更喜欢发出 table 个 QWORD，交易大小以简化设置代码；
- MSVC 改为发出 table 个 BYTE，以设置代码大小支付；即使将 -O3 更改为 -Os（针对大小进行优化），我也无法让 gcc 发出类似的代码。
啊，老的直接位图技巧。
GCC 也是这样做的，至少对于 switch。
x86 asm casetable implementation. Unfortunately GCC9 has a regression for some cases: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91026#c3; GCC8 和更早的版本做得更好。
另一个使用它的例子，这次是代码高尔夫（最少字节的代码，在本例中为 x86 机器代码）检测某些字母：User Appreciation Challenge #1: Dennis ♦
基本思想是使用输入作为 true/false 结果位图中的索引。
首先您必须进行范围检查，因为位图是固定宽度的，并且 x86 移位包含移位计数。我们不希望高输入别名进入某些应该 return 为真的范围。 cmp edi, 24/ja正在做。
（如果最低和最高 true 值之间的范围是从 120 到 140，例如，它可能以 sub edi,120 开始以在 [=14= 之前对所有内容进行范围移动].)
然后你使用bitmap & (1<<e)（the bt instruction），或(bitmap >> e) & 1（shr / and）来检查位图中告诉你的位e 值应该 return 真还是假。
有很多方法可以实现该检查，逻辑上等同但性能不同。
如果范围大于 32，则必须使用 64 位操作数大小。如果它大于 64，编译器可能根本不会尝试这种优化。或者可能仍然会针对某些范围较窄的条件执行此操作。
使用更大的位图（在 .rodata 内存中）是可能的，但可能不是大多数编译器会为您发明的东西。使用 bt [mem],reg （效率低下）或手动索引双字并检查是否与此代码检查直接位图的方式相同。如果你有很多高熵范围，可能值得检查 2x 64 位立即位图，分支或无分支......
Clang/LLVM 还有其他技巧可以有效地与多个值进行比较（当命中哪个并不重要时），例如将值广播到 SIMD 寄存器并使用打包比较。这不依赖于处于密集范围内的值。 ()
that optimizes the code way more than what I would think is possible.
这些类型的优化来自聪明的人类编译器开发人员，他们注意到源代码中的常见模式并想出巧妙的方法来实现它们。然后让编译器识别这些模式并转换它们对程序逻辑的内部表示以使用该技巧。
事实证明 switch 和 switch-like if() 语句很常见，并且积极的优化很常见。
编译器 远 不完美，但有时它们确实接近人们经常声称的那样；编译器会为您优化您的代码，这样您就可以以人类可读的方式编写代码，并且仍然 运行 接近最佳。有时在小范围内也是如此。
Since I do not understand what happens in the first case, I can not really judge which one is more efficient in my case.
直接位图大大更有效率。两者都没有数据内存访问，因此没有缓存丢失加载。唯一的 "expensive" 指令是可变计数移位（在主流 Intel 上为 3 微指令，因为 x86 令人讨厌的 FLAGS 设置语义；BMI2 shrx 仅为 1 微指令，避免必须 mov编号为 ecx.) https://agner.org/optimize. And see other performance analysis links in https://whosebug.com/tags/x86/info.
cmp/cmov 链中的每条指令至少为 1 uop，并且每个 cmov 中都有一个相当长的依赖链，因为 MSVC 没有费心将它分成 2 个或更多并行链.但无论如何它只是很多微指令，远远超过位图版本，因此吞吐量（无序执行与周围代码重叠工作的能力）以及延迟更差。
bt 也很便宜：在现代 AMD 和英特尔上为 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)，它仍然可以优化为 shr; 编译器知道 x86 shr 屏蔽了计数，因此他们可以优化它。但对于其他使移位计数饱和的 ISA 则不然...)
有很多方法可以实现几乎相同的位图检查。例如您甚至可以使用 shr 的 CF 输出，根据移出的最后一位进行设置。至少如果您确保 CF 提前为 cl=0 案例具有已知状态。
当你想要一个整数 bool 结果时，右移似乎比 bt / setcc、 更有意义，但 shr在 Intel 上花费 3 微指令实际上最好使用 bt reg,reg / setc al. 特别是如果你只需要一个 bool，并且可以使用 EAX 作为你的位图目标所以EAX 的前一个值肯定在 setcc 之前准备好了。 （避免对一些不相关的早期 dep 链的错误依赖。）
顺便说一句，MSVC 还有其他愚蠢之处：正如 所解释的那样，当您想将 AL 归零时，xor al,al 与 xor eax,eax 相比完全是愚蠢的。如果您不需要保留 RAX 的高位字节不变，请使用归零惯用语将完整寄存器归零。
当然，仅分支到 return 0 或 return 1 是没有意义的，除非您希望它非常可预测并且想要打破数据依赖性。我希望 setc al 阅读 bt
的 CF 结果更有意义
我的问题是编译器在这种情况下做了什么，它优化代码的方式比我想象的要多。
鉴于此枚举：
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;
}
对于该函数，MSVC 在使用 -Ox 优化标志 (Godbolt) 编译时生成此程序集：
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
这里发生了什么？我看到即使我向函数添加更多枚举比较，生成的程序集实际上并没有变成 "more"，只是这个幻数 (20078725) 发生了变化。该数字取决于函数中发生了多少枚举比较。我不明白这里发生了什么。
我之所以看这个是因为我想知道这样写函数是否好，或者像这样，按位比较：
bool MyFunction2(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;
}
这将导致生成带有 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]。
对于其余部分，幻数只是一个位掩码，其位对应于 "good" 值集。
>>> bin(20078725)
'0b1001100100110000010000101'
很容易找出第一个和第三个位（从 1 开始从右数）组，第 8、14、15 位，...
MSVC 使用 BT（位测试）指令和分支检查它 "directly"，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 和 OR 将结果放在一起，这都是更长的代码，并且可能会序列化执行。我怀疑相应的 clang 代码会更好。 OTOH，您使用按位或（|）而不是语义上更正确的逻辑或（||）编写此代码，并且编译器严格遵循您的命令（典型的 MSVC）。
另一种尝试的可能性是 switch - 但我认为与已经为第一个代码段生成的代码相比没有太多收获，这对我来说看起来很不错。
好的，做a quick test with all the versions against all compilers，我们可以看到：
- 上述 CLang 输出的 C 翻译在所有编译器中产生几乎相同的代码（= 到 clang 输出）；类似的 MSVC 翻译；
- 按位或版本与 CLang 和 gcc 中的逻辑或版本相同（=好）；
- 一般来说，除了
switch情况外，gcc 与 CLang 做的事情基本相同； switch结果各不相同：- CLang 做得最好，生成完全相同的代码；
- gcc 和 MSVC 都生成基于 jump-table 的代码，在这种情况下不太好；然而：
- gcc 更喜欢发出 table 个 QWORD，交易大小以简化设置代码；
- MSVC 改为发出 table 个 BYTE，以设置代码大小支付；即使将 -O3 更改为 -Os（针对大小进行优化），我也无法让 gcc 发出类似的代码。
啊，老的直接位图技巧。
GCC 也是这样做的，至少对于 switch。 x86 asm casetable implementation. Unfortunately GCC9 has a regression for some cases: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91026#c3; GCC8 和更早的版本做得更好。
另一个使用它的例子，这次是代码高尔夫（最少字节的代码，在本例中为 x86 机器代码）检测某些字母：User Appreciation Challenge #1: Dennis ♦
基本思想是使用输入作为 true/false 结果位图中的索引。
首先您必须进行范围检查，因为位图是固定宽度的，并且 x86 移位包含移位计数。我们不希望高输入别名进入某些应该 return 为真的范围。 cmp edi, 24/ja正在做。
（如果最低和最高 true 值之间的范围是从 120 到 140，例如，它可能以 sub edi,120 开始以在 [=14= 之前对所有内容进行范围移动].)
然后你使用bitmap & (1<<e)（the bt instruction），或(bitmap >> e) & 1（shr / and）来检查位图中告诉你的位e 值应该 return 真还是假。
有很多方法可以实现该检查，逻辑上等同但性能不同。
如果范围大于 32，则必须使用 64 位操作数大小。如果它大于 64，编译器可能根本不会尝试这种优化。或者可能仍然会针对某些范围较窄的条件执行此操作。
使用更大的位图（在 .rodata 内存中）是可能的，但可能不是大多数编译器会为您发明的东西。使用 bt [mem],reg （效率低下）或手动索引双字并检查是否与此代码检查直接位图的方式相同。如果你有很多高熵范围，可能值得检查 2x 64 位立即位图，分支或无分支......
Clang/LLVM 还有其他技巧可以有效地与多个值进行比较（当命中哪个并不重要时），例如将值广播到 SIMD 寄存器并使用打包比较。这不依赖于处于密集范围内的值。 (
that optimizes the code way more than what I would think is possible.
这些类型的优化来自聪明的人类编译器开发人员，他们注意到源代码中的常见模式并想出巧妙的方法来实现它们。然后让编译器识别这些模式并转换它们对程序逻辑的内部表示以使用该技巧。
事实证明 switch 和 switch-like if() 语句很常见，并且积极的优化很常见。
编译器 远 不完美，但有时它们确实接近人们经常声称的那样；编译器会为您优化您的代码，这样您就可以以人类可读的方式编写代码，并且仍然 运行 接近最佳。有时在小范围内也是如此。
Since I do not understand what happens in the first case, I can not really judge which one is more efficient in my case.
直接位图大大更有效率。两者都没有数据内存访问，因此没有缓存丢失加载。唯一的 "expensive" 指令是可变计数移位（在主流 Intel 上为 3 微指令，因为 x86 令人讨厌的 FLAGS 设置语义；BMI2 shrx 仅为 1 微指令，避免必须 mov编号为 ecx.) https://agner.org/optimize. And see other performance analysis links in https://whosebug.com/tags/x86/info.
cmp/cmov 链中的每条指令至少为 1 uop，并且每个 cmov 中都有一个相当长的依赖链，因为 MSVC 没有费心将它分成 2 个或更多并行链.但无论如何它只是很多微指令，远远超过位图版本，因此吞吐量（无序执行与周围代码重叠工作的能力）以及延迟更差。
bt 也很便宜：在现代 AMD 和英特尔上为 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)，它仍然可以优化为 shr; 编译器知道 x86 shr 屏蔽了计数，因此他们可以优化它。但对于其他使移位计数饱和的 ISA 则不然...)
有很多方法可以实现几乎相同的位图检查。例如您甚至可以使用 shr 的 CF 输出，根据移出的最后一位进行设置。至少如果您确保 CF 提前为 cl=0 案例具有已知状态。
当你想要一个整数 bool 结果时，右移似乎比 bt / setcc、 更有意义，但 shr在 Intel 上花费 3 微指令实际上最好使用 bt reg,reg / setc al. 特别是如果你只需要一个 bool，并且可以使用 EAX 作为你的位图目标所以EAX 的前一个值肯定在 setcc 之前准备好了。 （避免对一些不相关的早期 dep 链的错误依赖。）
顺便说一句，MSVC 还有其他愚蠢之处：正如 xor al,al 与 xor eax,eax 相比完全是愚蠢的。如果您不需要保留 RAX 的高位字节不变，请使用归零惯用语将完整寄存器归零。
当然，仅分支到 return 0 或 return 1 是没有意义的，除非您希望它非常可预测并且想要打破数据依赖性。我希望 setc al 阅读 bt