llvm / llvm/llvm-project

Transform multiplying a float by a power of two into adding to the exponent.

Open
#216,414 8 comments 0 reactions 1 assignee Claimed by @L3GiaBao View on GitHub
floating-point llvm:SelectionDAG missed-optimization
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

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.