llvm/llvm-project

Implement `clz` using floating point math if `clz` instruction is not available

Open

#161,746 创建于 2025年10月2日

在 GitHub 查看
 (22 评论) (0 反应) (1 负责人)C++ (10,782 fork)batch import
good first issuellvm:SelectionDAGmissed-optimization

仓库指标

Star
 (26,378 star)
PR 合并指标
 (平均合并 1天 2小时) (30 天内合并 1,000 个 PR)

描述

In https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogIEEE64Float we can find a neat trick to calculate the ilog2 of a u32 with floating point math:

u32 ilog2_u32(u32 x) {
    // zexto extend to 64 bits
    u64 x_u64 = x;

    // set exponent to 52
    x_u64 |= (52 + 1023ULL) << 52;

    // move into f64 register
    double f = __builtin_bit_cast(double, x_u64);

    // subtract 2^52
    f -= 0x1.0p52;

    // move back into u64 register
    x_u64 = __builtin_bit_cast(u64, f);

    // extract exponent
    return (x_u64 >> 52) - 1023;
}

Rearrange the equation:

ilog2(x) == 31 - clz(x)
clz(x) + ilog2(x) == 31
clz(x) == 31 - ilog2(x)

and we get:

u32 src32(u32 x) { return __builtin_clzg(x); }
u32 tgt32(u32 x) { return 31 - ilog2_u32(x); }

This generalizes to u8 and u16 using float instead of double

https://godbolt.org/z/cW8js3MK9 https://alive2.llvm.org/ce/z/-bK_nC

贡献者指南