| Issue |
92074
|
| Summary |
[ValueTracking] Missed optimization of modulo power-of-two
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
YanWQ-monad
|
Recently I found a missed optimization related to modulo power-of-two. It's
https://github.com/dtcxzyw/llvm-opt-benchmark/blob/b79d63cb8adea5949cc449d4186e342d3dbdd871/bench/wasmtime-rs/optimized/1ham0fg2czw77e66.ll#L235
and it's compiled from [something](https://github.com/bytecodealliance/wasmtime/blob/a6f27eeb7e9ada3f1e10d75630f733b204e2c1ba/cranelift/codegen/meta/src/constant_hash.rs#L12-L42) like
``` rust
let modulo = if size.is_power_of_two() { // i.e. ctpop(size) == 1
size * 2
} else {
size.next_power_of_two()
};
let result = xxx % modulo;
```
where `urem xxx, modulo` could be optimized to `and xxx, (modulo - 1)`.
To solve it, I have created a PR #91171 that enables the recognization of `.next_power_of_two()`, and I also have a draft patch that could recognize power-of-two from dom conditions.
However, the key problem in this case is that LLVM currently only search 2 levels beyond `phi` nodes, so the resursion of `isKnownToBeAPowerOfTwo` stops at `size * 2`, and fails to know `size` is a power-of-two from the condition.
https://github.com/llvm/llvm-project/blob/37ffbbb19576a884c5bb93b9ac0ae97f89523b6b/llvm/lib/Analysis/ValueTracking.cpp#L2197-L2199
Though changing `- 1` to `- 3` could make it work in this case, it's obviously not a proper way to solve the problem.
I am not sure if there is a way to handle this complex context across multiple basic blocks, or should we instead patch `wasmtime` to use `let modulo = (size + 1).next_power_of_two()`?
cc @nikic @dtcxzyw
![]()
_______________________________________________
llvm-bugs mailing list
llvm-bugs@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
