[InstSimplify] Missed fold for (x & m) + C < m + C + 1 with nuw adds
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
For unsigned integers, `a = (x & m)` implies `a <=u m`: bitwise `and` can only clear bits relative to `m`.
For defined executions of the following `add nuw` operations, this should also imply:
(x & m) + C ` keep the comparison (https://godbolt.org/z/9cqq6e935).
The source pattern is motivated by SPEC CPU 2017 `557.xz_r`, around `liblzma/lz/lz_encoder_mf.c:lzma_mf_hc3_find`. It computes a masked hash value and uses it after a fixed offset:
```c
hash_value = (...) & mf->hash_mask;
idx = FIX_3_HASH_SIZE + hash_value;
```
The backing hash table size is computed as:
```c
hash_size_sum = (mf->hash_mask + 1) + FIX_3_HASH_SIZE;
```
The original SPEC source does not contain an explicit boundary check such as `idx < hash_size_sum`; this is only the motivating source shape. If such a boundary check is materialized in this context, LLVM should be able to eliminate it.
The issue seems local to existing InstSimplify logic. LLVM already folds the base fact: `icmp ule (x & m), m -> true`. The missing step is preserving that unsigned-order fact through no-wrap constant offsets. `simplifyICmpWithBinOp()` in `llvm/lib/Analysis/InstructionSimplify.cpp` already handles icmp over `add`/`sub` with no-wrap information to some extent.
Contributor guide
Assessment
This issue has not been assessed yet.