gcc 愚者如何优化这个开关

qeeaahzv  于 2022-11-30  发布在  其他
关注(0)|答案(1)|浏览(192)

今天我发现愚者在优化开关方面有着惊人的魔力:

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相比,愚者设法将其编译为1/4的代码。
1.从概念上讲,这个asm是做什么的?
1.愚者如何做到这一点?

rdlzhqv9

rdlzhqv91#

两种编译器都以显而易见的方式编译此部分:

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,但使用不同的确切指令。愚者偷偷地使用进位标志来计算((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上,它首先检查瓦片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分成了一些逻辑组。Eidogg.超过130只有到城镇的捷径。
我不知道编译器作者是如何想出这些东西的。

相关问题