时间戳

首页 > 解决方案 > 编译器在这里做了什么，允许通过很少的实际比较来比较许多值？

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

问题描述

我的问题是关于编译器在这种情况下所做的优化代码的方式比我认为可能的方式更多。

鉴于此枚举：

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

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

}

这将导致使用 M​​SVC 生成此程序集：

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

由于我不了解第一种情况会发生什么，因此我无法真正判断哪种情况对我来说更有效。

标签： c++assemblyoptimizationx86-64micro-optimization

解决方案

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

其余的，幻数只是一个位掩码，位对应于设置的“好”值。

>>> bin(20078725)
'0b1001100100110000010000101'

很容易发现第 1 位和第 3 位（从 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 和 ORs 结果一起，这都是更长的代码，并且可能会序列化执行。我怀疑相应的clang代码会更好。OTOH，您使用按位 OR ( |) 而不是语义上更正确的逻辑 OR ( ||) 编写了此代码，并且编译器严格遵循您的命令（典型的 MSVC）。

另一种尝试的可能性可能是switch- 但与已经为第一个片段生成的代码相比，我认为没有太多收获，这对我来说看起来相当不错。

好的，对所有编译器的所有版本进行快速测试，我们可以看到：

  • 上面 CLang 输出的 C 翻译在所有编译器中产生几乎相同的代码（= 到 clang 输出）；对于 MSVC 翻译也是如此；
  • 按位或版本与 CLang 和 gcc 中的逻辑或版本（=好）相同；
  • 一般来说，gcc 的作用与 CLang 基本相同，但switch情况除外；
  • switch结果五花八门：
    • 通过生成完全相同的代码，CLang 做得最好；
    • gcc 和 MSVC 都生成基于跳转表的代码，在这种情况下不太好；然而：
      • gcc 更喜欢发出一个 QWORD 表，交易大小以简化设置代码；
      • 相反，MSVC 会发出一个 BYTE 表，并以设置代码大小进行支付；即使将 -O3 更改为 -Os（针对大小进行优化），我也无法让 gcc 发出类似的代码。

推荐阅读