llvm / llvm/llvm-project

[InstCombine] Generalise `bitreverse(bitreverse(x) << 1) => x >> 1` to more complex operations on `x`

Open
#219,334 4 comments 0 reactions 1 assignee Claimed by @rohan11235813 View on GitHub
llvm:instcombine missed-optimization
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

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.