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. 海湾合作委员会是如何做到这一点的？

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。无论出于何种原因，它选择StairsType::Down在跳转之前将数字 1 ( ) 预加载到返回值寄存器中。

同时，在 gcc 上，它首先检查图块 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;
}

编译器似乎注意到您将图块 ID 分组为某种逻辑组。例如，高于 130 则只有捷径可通往城镇。

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