llvm / llvm/llvm-project

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

Open
#161,746 22 comments 0 reactions 1 assignee Claimed by @def3r View on GitHub
good first issue llvm:SelectionDAG missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

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:

```c++
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:
```c++
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

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.