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

Question

我正在研究woothashwyhash哈希函数，这是根据 SMHasher 项目的最佳哈希函数之一的重申。

GCC 和 clang 都能够在-O1（或者更高级别，当然）执行非常深入的优化，我完全不明白它们是如何从 900 多行 asm with -Og（紧密遵循源代码）变成只有 25 行asm 指令（带有 GCC 主干的 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 中似乎也经过了很好的优化，所有辅助函数都内联了。但接下来按照 switch 的 31 个分支，总共 900+ 行 asm。这很容易理解并且紧密遵循源代码。

但这里是 O1..O3 的优化程序集main- 这是完整的代码，而不是摘录：

main:
        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

从这段代码调用上面的woothash代码switch：

[[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);
}

GCC 和 clang 是如何做到的？我想也许源代码有 UB 并且某些部分被意外删除，但是使用 GCC 或 MSVC 进行优化和不进行优化时得到的哈希值是相同的。这是什么魔法？尾部开关怎么可能简化得这么好？

更重要的是，由于 25 条汇编指令似乎确实正确地表示了这个函数，所以应该可以以同样的方式简化源代码，以便它始终得到优化？

Answer 1

当您在下面调用此函数时，编译器知道woothash64len 是一个等于 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 本身仅以颜色突出显示未优化的线条