[InstCombine] Use memchr return-range semantics to remove redundant npos check
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
InstCombine currently misses a simplification for code patterns derived from `memchr`-based string search.
This is not a purely algebraic fold. The intended optimization relies on a limited libcall postcondition of `memchr`: if `memchr(base, ch, len)` returns non-null, the returned pointer must point inside the searched range starting at `base`.
Therefore, the offset from `base` cannot be `-1` on the non-null path.
### Reproducer
```llvm
; opt -passes=instcombine -S
declare ptr @memchr(ptr noundef, i32 noundef, i64 noundef)
define i64 @src(ptr %base, i64 %len) {
entry:
%p = tail call ptr @memchr(ptr noundef %base, i32 noundef 38, i64 noundef %len)
%isnull = icmp eq ptr %p, null
%pi = ptrtoint ptr %p to i64
%bi = ptrtoint ptr %base to i64
%idx = sub i64 %pi, %bi
%isnpos = icmp eq i64 %idx, -1
%cond = select i1 %isnull, i1 true, i1 %isnpos
%r = select i1 %cond, i64 %len, i64 %idx
ret i64 %r
}
```
### Current behavior
InstCombine keeps the idx == -1 check:
```llvm
%isnpos = icmp eq i64 %idx, -1
%cond = select i1 %isnull, i1 true, i1 %isnpos
%r = select i1 %cond, i64 %len, i64 %idx
```
### Proposed result
The condition can be simplified to the null check:
```llvm
define i64 @src(ptr %base, i64 %len) {
entry:
%p = tail call ptr @memchr(ptr noundef %base, i32 noundef 38, i64 noundef %len)
%isnull = icmp eq ptr %p, null
%pi = ptrtoint ptr %p to i64
%bi = ptrtoint ptr %base to i64
%idx = sub i64 %pi, %bi
%r = select i1 %isnull, i64 %len, i64 %idx
ret i64 %r
}
```
### Reasoning
The relevant libcall postcondition is:
```
p = memchr(base, ch, len)
```
p == null || p points inside [base, base + len)
For the offset:
```
%idx = ptrtoint %p - ptrtoint %base
```
this implies:
```
p != null => idx != -1
```
Therefore:
```llvm
%cond = select i1 %isnull, i1 true, i1 (%idx == -1)
```
is equivalent to:
```llvm
%cond = %isnull
```
because:
```llvm
if %isnull:
%cond = true
if !%isnull:
memchr returned a pointer inside the searched range
so %idx != -1
therefore (%idx == -1) is false
so %cond = false
```
Thus both cases match %isnull.
### Important safety restriction
This fold must not be applied to arbitrary pointer values.
For example, the following generic IR is not equivalent after removing the idx == -1 check:
```llvm
define i1 @not_valid_for_generic_pointer(ptr %base, ptr %p) {
entry:
%isnull = icmp eq ptr %p, null
%pi = ptrtoint ptr %p to i64
%bi = ptrtoint ptr %base to i64
%idx = sub i64 %pi, %bi
%isnpos = icmp eq i64 %idx, -1
%cond = select i1 %isnull, i1 true, i1 %isnpos
ret i1 %cond
}
```
If %p is an arbitrary non-null pointer one byte before %base, then %idx == -1 may be true.
So the fold should be limited to cases where:
```
%p is the result of a recognized memchr libcall
and
%idx is computed as ptrtoint(%p) - ptrtoint(the same memchr base pointer)
```
### Suggested pattern
```llvm
%p = call ptr @memchr(ptr %base, i32 %ch, i64 %len)
%isnull = icmp eq ptr %p, null
%pi = ptrtoint ptr %p to iN
%bi = ptrtoint ptr %base to iN
%idx = sub iN %pi, %bi
%isnpos = icmp eq iN %idx, -1
%cond = select i1 %isnull, i1 true, i1 %isnpos
```
can become:
```llvm
%cond = %isnull
Similarly, the logically equivalent form:
%cond = or i1 %isnull, %isnpos
```
can also become:
```llvm
%cond = %isnull
```
under the same memchr postcondition.
### Notes
This optimization is intentionally libcall-aware. It is not a general simplification of pointer subtraction or ptrtoint arithmetic.
The main motivation is to remove redundant npos checks generated after memchr-based string search lowering, such as patterns from string_view::find_first_of-style code.
AliveProof : https://alive2.llvm.org/ce/z/Hm4qPZ
Compiler-Explorer sample & perf : https://compiler-explorer.com/z/3T6zxc1xe
RealWorld Usage : https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/pull/382/changes
Contributor guide
Assessment
This issue has not been assessed yet.