c++ - 编译器在这里做什么，允许通过很少的实际比较来完成许多值的比较？

Question

我的问题是编译器在这种情况下做了什么，以比我认为可能的方式更优化代码。

给定这个枚举:

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

这里发生了什么？我看到即使我向函数添加更多枚举比较，生成的程序集实际上并没有变得“更多”，只是这个魔数(Magic Number) (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

由于我不明白在第一种情况下会发生什么，所以我无法真正判断在我的情况下哪个更有效。

Answer 1

很聪明!与 24 的第一个比较是进行粗略的范围检查——如果它大于 24 或小于 0，它将退出；这很重要，因为后面对魔数(Magic Number)进行操作的指令对操作数范围的硬上限为 [0, 31]。

对于其余部分，魔数(Magic Number)只是一个位掩码，其位对应于“好”值集。

>>> 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基于 -based 的代码，它非常糟糕 - 它使用了大量的 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 都生成基于跳转表的代码，在这种情况下不太好；然而:
    • gcc 更喜欢发出一个 QWORD 表，交易大小以简化设置代码；
    • MSVC 而是发出一个 BYTE 表，以设置代码大小支付；即使将 -O3 更改为 -Os(针对大小进行优化)，我也无法让 gcc 发出类似的代码。