今天我发现 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 的代码。
- 从概念上讲,这个 asm 是做什么的?
- GCC 如何做到这一点?
最佳答案
两个编译器都以明显的方式编译这部分:
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 时,只有通往城镇的捷径。
我不知道编译器编写者是如何想出这些东西的。
关于c++ - GCC如何优化这个 `switch`,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/74605269/