llvm / llvm/llvm-project

[InstSimplify] Missed fold for (x & m) + C < m + C + 1 with nuw adds

Open
#201,290 1 comment 0 reactions 1 assignee Claimed by @iamaayushrivastava View on GitHub
llvm:instcombine missed-optimization
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

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.