llvm / llvm/llvm-project

[InstCombine] Use memchr return-range semantics to remove redundant npos check

Open
#199,903 3 comments 0 reactions 1 assignee Claimed by @JihyeonJeong129 View on GitHub
llvm:instcombine missed-optimization
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

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.