c++ - GCC如何优化这个 `switch`

Question

今天我发现 GCC 在优化这段代码中的开关方面做了一些惊人的魔法:

StairsType GetStairsType(uint8_t tileId, uint8_t dlvl)
{
    if (dlvl == 0)
        return StairsType::Part;
    if (tileId == 48) {
        return dlvl >= 21 ? /* Crypt */ StairsType::Down : /* Caves */ StairsType::Part;
    }
    switch (tileId) {
    case 57: return StairsType::Down;
    // many more tile IDs go here
    }
}

看看这个🪄:

https://godbolt.org/z/snY3jv8Wz

(左边是gcc，右边是clang)

与 Clang 相比，GCC 设法将其编译为 1/4 的代码。

1. 从概念上讲，这个 asm 是做什么的？
2. GCC 如何做到这一点？

Answer 1

两个编译器都以明显的方式编译这部分:

    if (dlvl == 0)
        return StairsType::Part;

说到这部分:

    if (tileId == 48) {
        // This ID is used by both Caves and Crypt.
        return dlvl >= 21 ? /* Crypt */ StairsType::Down : /* Caves */ StairsType::Part;
    }

gcc 检查 tileId==48直接，而 clang 决定将其合并到 switch 语句中。

两个编译器决定计算dlvl >= 21 ? 1 : 4以或多或少相同的方式无分支，但具有不同的确切指令。 GCC偷偷地使用进位标志来计算((dlvl >= 21 ? 0 : -1) & 3) + 1而 clang 直接计算 ((dlvl < 21) * 3) + 1 .

// GCC
cmp     sil, 21
sbb     eax, eax
and     eax, 3
add     eax, 1

// clang
xor     eax, eax
cmp     sil, 21
setb    al
lea     eax, [rax + 2*rax]
inc     eax

说到 switch语句，clang 用一个跳转表来实现它。最低的条目是 16，最高的是 160，所以它减去 16，然后检查数字是否大于 144。有一个众所周知的技巧来保存一次检查，其中小于 16 的数字环绕到非常大的数字，所以它们大于 144。无论出于何种原因，它选择在执行跳转之前将数字 1 (StairsType::Down) 预加载到返回值寄存器中。

同时在 gcc 上，它首先检查 tile ID 是否在 16 到 78 之间。如果是，它减去 16 并检查一些位掩码:

if(tileID < 16) {
    return 0;
} else if(tileID <= 78) {
    mask = (1 << (tileID - 16));
    if(2307251517974380578 & mask) return 2;
    if(4611688220747366401 & mask) return 1;
    return ((421920768 & mask) != 0) << 2;
} else {
    tileID += 125; // The same as tileID -= 131
    // because it's being treated as a byte
    if(tileID > 29) { // values lower than 131 wrapped around
        return 0;
    }

    // notice that if we get here it means the tileID is >= 131 and <= 160
    // << only looks at the bottom 5 bits of tileID (i.e. tileID & 31)
    return -((541065279 & (1 << tileID)) != 0) & 3;
}

让我们再试一次，但是使用二进制位掩码，让我们弄清楚这些 return 语句返回什么:

if(tileID < 16) {
    return StairsType::Invalid;
} else if(tileID <= 78) {
    mask = (1 << (tileID - 16));
    // tile 17, 21, 35, 36, 38, 51, 56, 64, 66, 77
    if(0010000000000101000000010000100000000000010110000000000000100010 & mask) return StairsType::Up;
    // tile 16, 39, 40, 46, 47, 57, 78
    if(0100000000000000000000100000000011000100100000000000000000000001 & mask) return StairsType::Down;
    // tile 33, 34, 37, 40, 43, 44
    return ((00011001001001100000000000000000 & mask) != 0) ? StairsType::Part : StairsType::Invalid;
} else {
    if(tileID < 131 || tileID > 160) {
        return 0;
    }

    // tile 131, 132, 133, 134, 135, 136, 153, 160
    return (00100000010000000000000000111111 & (1 << (tileID - 131))) ? StairsType::ShortcutToTown : StairsType::Invalid;
}

似乎编译器注意到您将您的图 block ID 分组到一些逻辑组中。例如。高于 130 时，只有通往城镇的捷径。

我不知道编译器编写者是如何想出这些东西的。