Transform multiplying a float by a power of two into adding to the exponent.
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
It is a well known trick that a "fast" way to multiply a float by 2.0 is to add 1 to the exponent. For `ieee_binary32`, this looks like `f32_value += (1 << 23)` or `f32_value += 0x00800000`.
More generally, if we want to multiply or divide by 2^N, we just have to add or subtract N from the exponent. This is valid provided that the input and output are both normal. Since we are multiplying/dividing by a power of two, the operation is exact, and does not depend on the rounding mode.
This optimization is most profitable on targets without an FPU.
Clang/LLVM is currently unable to perform this optimization.
```c
float src_f32(float x) {
if (__builtin_isnan(x) || x < 1.0f || x > 256.0f) {
__builtin_unreachable();
}
return 2.0f * x;
}
float tgt_f32(float x) {
if (__builtin_isnan(x) || x < 1.0f || x > 256.0f) {
__builtin_unreachable();
}
uint32_t bin;
__builtin_memcpy(&bin, &x, sizeof(x));
bin += 0x00800000;
float result;
__builtin_memcpy(&result, &bin, sizeof(bin));
return result;
}
```
Godbolt: https://godbolt.org/z/s7W446zno
Alive2: https://alive2.llvm.org/ce/z/C573ZE
`KnownFPClass` can provide information on if the input is normal, but the transformation is only valid if we can prove that `x * 2^N` won't become infinity, or that `x / 2^N` won't become zero or subnormal. This can be proven by computing the known range of the floating point value. We can also prove a value won't overflow to infinity if we are doing `ninf fmul`.
The only time where the result overflows to infinity but is still a valid transformation is `0x7F000000 * 2.0 == 0x7F000000 + 0x00800000 == 0x7F800000 == +inf` (unless a floating point exception or etc needs to be raised).
***
This optimization can also be applied to `ldexp`/`scalbn`
Contributor guide
Assessment
This issue has not been assessed yet.