gcc 编译器优化是如何工作的？

我正在研究woothash散列函数，它是wyhash的一个重复--根据SMHasher项目，它是最好的散列函数之一。
GCC和clang都能够在-O1（当然还有更高的级别）上执行非常深入的优化，我完全不明白它们是如何从-Og的900多行asm指令（严格遵循源代码）变成只有25条asm指令（GCC Backbone.js 的23条指令，大概是GCC 13！）。
代码有点太长，无法完整粘贴到这里，因此下面是编译器资源管理器的链接：https://godbolt.org/z/qK16EW4zT
下面是问题的要点：散列函数具有主循环，该主循环成批地处理32字节宽的数据，其后是具有31个标签的开关，以处理数据的剩余尾部。_wootp1 ... _wootp5是编译时常数。

inline constexpr uint64_t ROTL64(uint64_t x,int r) { return (x << r) | (x >> (64 - r)); }

inline uint64_t _wootmum(const uint64_t A, const uint64_t B) {
    uint64_t r = (A ^ ROTL64(B, 39)) * (B ^ ROTL64(A, 39));
    return r - (r >> 32);
}

inline uint64_t _wootr16(const uint8_t *p){ uint16_t v; memcpy(&v, p, 2); return v; }
inline uint64_t _wootr08(const uint8_t *p){ uint8_t v; memcpy(&v, p, 1); return v; }
inline uint64_t _wootr32(const uint8_t *p){ uint32_t v; memcpy(&v, p, 4); return v; }
inline uint64_t _wootr64(const uint8_t *p){ uint64_t v; memcpy(&v, p, 8); return v; }

uint64_t woothash(const uint8_t* p, uint64_t len, uint64_t seed) {

   for (i = 0; i + 32 <= len; i += 32, p += 32)
   {
       a = (_wootr64(p     ) ^ a) * _wootp1; a = ROTL64(a, 22); a *= _wootp3;
       b = (_wootr64(p +  8) ^ b) * _wootp2; b = ROTL64(b, 25); b *= _wootp4;
       c = (_wootr64(p + 16) ^ c) * _wootp3; c = ROTL64(c, 28); c *= _wootp5;
       d = (_wootr64(p + 24) ^ d) * _wootp4; d = ROTL64(d, 31); d *= _wootp1;
       seed += a + b + c + d;
   }

   switch (len & 31) {
       case 1 : seed = _wootmum(seed, _wootr08(p) ^ _wootp1); break;
       case 2 : seed = _wootmum(seed, _wootr16(p) ^ _wootp1); break;
       case 3 : seed = _wootmum(seed, ((_wootr16(p) << 8) | _wootr08(p + 2)) ^ _wootp1); break;
       case 4 : seed = _wootmum(seed, _wootr32(p) ^ _wootp1); break;
   ...
   }

}

主循环相当小，即使在Og中也看起来优化得很好，所有的helper函数都是内联的。但是接下来要跟随switch的31个分支，总共有900多行asm。这很容易理解，并且紧跟源代码。
但这里是O1..O3中的优化汇编-这是完整的代码，而不是摘录：

movabs  rdx, -1800455987208640293
        movsx   rax, edi
        sal     rdi, 32
        movabs  rcx, -6884282663029611481
        shr     rax, 32
        or      rdi, rax
        movabs  rax, 6239426704749895748
        xor     rdx, rdi
        ror     rdx, 25
        xor     rdx, rax
        movabs  rax, -4822408543216407806
        xor     rdi, rax
        imul    rdx, rdi
        mov     rax, rdx
        shr     rax, 32
        sub     rdx, rax
        mov     rax, rdx
        sal     rax, 16
        xor     rax, rdx
        shr     rdx, 32
        xor     rdx, rcx
        imul    rax, rdx
        mov     rdx, rax
        shr     rdx, 31
        sub     eax, edx
        ret

GCC和clang是怎么做到的呢？我想可能是源代码有UB，有些部分意外地被删除了，但是不管有没有优化，不管是GCC还是MSVC，得到的哈希值都是一样的。这是什么魔法？怎么可能把尾部切换简化得这么好呢？
更重要的是，既然25条汇编指令看起来确实正确地表示了这个函数，那么应该可以用同样的方式简化源代码，这样它就总是被优化的。

当你在下面调用它时，编译器知道在woothash64中len是一个等于8的常量（sizeof（uint64_t））。

[[nodiscard]] inline uint64_t woothash64(const void* data, uint64_t len) noexcept
{
    return detail::woothash(data, len, 7733305894521163487ULL /* Completely fair and random seed*/);
}

[[nodiscard]] inline uint64_t woothash64i(uint64_t value) noexcept
{
    return woothash64(&value, sizeof(uint64_t));
}

int main(int argc, char**)
{
    return woothash64i(argc);
}
int main(int argc, char**)
{
    return woothash64i(argc);
}

因此，当它调用detail::woothash时，它会丢弃所有内容，变成：

inline uint64_t woothash(const void* key, uint64_t len, uint64_t seed) {
    const uint8_t *p = (const uint8_t*)key;
    
    // switch (len & 31) {
    //case 8 : 
    seed = _wootmum(seed, __wootr64(p) ^ _wootp1); break;
    
    seed = (seed ^ seed << 16) * (len ^ _wootp0 ^ seed >> 32);
    return seed - (seed >> 31) + (seed << 33);
}

您可以看到Godbolt本身仅以颜色突出显示了未优化的行

gcc 编译器优化是如何工作的？

1条答案

相关问题

热门标签

最新问答