[InstCombine] Generalise `bitreverse(bitreverse(x) << 1) => x >> 1` to more complex operations on `x`
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
Doing a left/right shift on `bitreverse(x)` and then bitreversing the result is the same as doing the opposite shift:
```rs
#[unsafe(no_mangle)]
pub fn src1(x: u64) -> u64 {
fn f(x: u64) -> u64 {
(x << 1)
}
f(x.reverse_bits()).reverse_bits()
}
#[unsafe(no_mangle)]
pub fn tgt1(x: u64) -> u64 {
(x >> 1)
}
#[unsafe(no_mangle)]
pub fn src2(x: u64) -> u64 {
fn f(x: u64) -> u64 {
(x >> 1)
}
f(x.reverse_bits()).reverse_bits()
}
#[unsafe(no_mangle)]
pub fn tgt2(x: u64) -> u64 {
(x << 1)
}
```
LLVM is smart enough to recognise these cases.
But if `f` includes more complex operations on `x`, the bitreverses are not eliminated, eg
```rs
#[unsafe(no_mangle)]
pub fn src3(x: u64) -> u64 {
fn f(x: u64) -> u64 {
!(x >> 1)
}
f(x.reverse_bits()).reverse_bits()
}
#[unsafe(no_mangle)]
pub fn tgt3(x: u64) -> u64 {
!(x << 1)
}
#[unsafe(no_mangle)]
pub fn src4(x: u64) -> u64 {
fn f(x: u64) -> u64 {
x | (x >> 1)
}
f(x.reverse_bits()).reverse_bits()
}
#[unsafe(no_mangle)]
pub fn tgt4(x: u64) -> u64 {
x | (x << 1)
}
#[unsafe(no_mangle)]
pub fn src5(x: u64) -> u64 {
fn f(x: u64) -> u64 {
x & (x >> 1)
}
f(x.reverse_bits()).reverse_bits()
}
#[unsafe(no_mangle)]
pub fn tgt5(x: u64) -> u64 {
x & (x << 1)
}
#[unsafe(no_mangle)]
pub fn src6(x: u64) -> u64 {
fn f(x: u64) -> u64 {
x & !(x >> 1)
}
f(x.reverse_bits()).reverse_bits()
}
#[unsafe(no_mangle)]
pub fn tgt6(x: u64) -> u64 {
x & !(x << 1)
}
```
[Compiler explorer](https://godbolt.org/z/6xzs71PnE)
[Alive proofs](https://alive2.llvm.org/ce/z/G_wWw5)
Contributor guide
Assessment
This issue has not been assessed yet.