[InstCombine] Fold memrchr calls with sequences of identical bytes.

[msebor]

Summary

This change implements folding of memrchr calls with sequences of identical characters.

Depends on D123629.

[msebor]

Add context.

[nikic]

Just wondering if there's any specific motivation for this pattern, as it seems oddly specific. Is this something that GCC implements?

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

984

Why do we need the N <= sizeof S comparison here? As that would be UB, I think we can omit it here.

[msebor]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

984

I did it for the same reason as the folding of the excessive bounds to null. In my view, if it can be done cheaply it's preferable to avoid out of bounds accesses. GCC takes this approach in some cases (e.g., for strlen("123" + i)) but not in others. But unless these cases are handled consistently in LLVM I don't think it matters much one way or the other either. I can remove the check if you prefer. (It would be helpful to have some documented guidance on how these issues are expected to be handled in general, or to try to come to a consensus if it's not yet clear.)

My motivation for recognizing this particular pattern is to optimize searches in zero-initialized arrays (including the trailing sequences of nulls following initial strings in bigger arrays, ending at the offset of one of the nulls). The former are rare on their own but common as members of bigger aggregates. They're yet to be handled by LLVM (the latter is only handled in strlen) but my hope is to add support for both to all the function folders. I'd also like to extend this pattern to memchr, for the same reason. (The non-null cases aren't as important but they naturally fall out of this.)

GCC doesn't have a built-in for memrchr so it doesn't do anything interesting with calls to it. Its `memchr folder is very simplistic and doesn't support this pattern (unlike LLVM, it does handle searches in all kinds of constant aggregates).

[nikic]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

984

I did it for the same reason as the folding of the excessive bounds to null. In my view, if it can be done cheaply it's preferable to avoid out of bounds accesses. GCC takes this approach in some cases (e.g., for strlen("123" + i)) but not in others. But unless these cases are handled consistently in LLVM I don't think it matters much one way or the other either. I can remove the check if you prefer. (It would be helpful to have some documented guidance on how these issues are expected to be handled in general, or to try to come to a consensus if it's not yet clear.)

I don't think there is any official guidance for this, but my 2c is that we're free to exploit UB aggressively, but also don't need to go out of the way to do so, if there's no benefit. In D123628 the choice was between retaining the libcall (and thus sanitizer checks) or returning null. In this case, the libcall is going to be removed either way, and we're going to return an "incorrect" result either way, whether that is s + n or null. I don't think one of those values is preferable over the other. As such, we should make the choice which results in fewer instructions here, which is to omit the additional bounds check.

My motivation for recognizing this particular pattern is to optimize searches in zero-initialized arrays (including the trailing sequences of nulls following initial strings in bigger arrays, ending at the offset of one of the nulls). The former are rare on their own but common as members of bigger aggregates. They're yet to be handled by LLVM (the latter is only handled in strlen) but my hope is to add support for both to all the function folders. I'd also like to extend this pattern to memchr, for the same reason. (The non-null cases aren't as important but they naturally fall out of this.)

Ah, I see, thanks for the context.

[msebor]

Remove bounds check on the assumption it's valid.

[msebor]

There is a build error with the patch that I don't understand:

Build 240741: pre-merge checks patch application failed

ERROR error: patch failed: llvm/test/Transforms/InstCombine/memrchr-2.ll:1
error: llvm/test/Transforms/InstCombine/memrchr-2.ll: patch does not apply

There is no memrchr-2.ll in this patch. Not sure what to make of it.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

984

I forgot this is still open. I'll go ahead and remove the check. Just one remark: the essential difference between returning null and an invalid past-the-end pointer is that most callers are prepared to handle the former while none can meaningfully deal with the latter. Whether the null result is correct or not depends. The invalid result is never correct and will almost certainly cause trouble.

[msebor]

I wonder if the error has something to do with merging the patch from D123628 into the next one in the series (D123629) in the final commit. Should I abandon the former?

[nikic]

In D123631#3475651, @msebor wrote:

I wonder if the error has something to do with merging the patch from D123628 into the next one in the series (D123629) in the final commit. Should I abandon the former?

Yes, that's likely. Pre-merge checks apply dependencies of the patch first, though I'm not sure how exactly that works if some of them are closed. In either case, you can abandon the patch as it is no longer relevant.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

962

Use the helper function that avoids the 32-bit truncation issue?

970

I don't get the AKA part of this comment.

977

I think this should be using CreateLogicalAnd, in case CharVal is poison (unless we want to argue that this memrchr argument cannot be poison, even for a zero bound).

[msebor]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

962

The issue can't happen here because EndOff is either restricted to at most Str.size() earlier on, or, for variable offsets, left initialized to UINT64_MAX and then implicitly converted to SIZE_MAX AKA std::npos when passed to substr.

970

When N is constant it's not zero at this point (constants zero and one are handled above). It's might be a vestige of the constant zero handling being done later in one of the early patches. Let me remove it.

977

I don't have enough experience with poison to understand how it makes a difference but sure, CreateLogicalAnd sounds fine.

(Since CharVal is treated as an unsigned char by these functions, any value should be allowed here, including indeterminate/uninitialized. What exactly that means in practical C terms has been debated but the official albeit sometimes contested position is that each evaluation of an indeterminate unsigned char might yield a different result).

[msebor]

Use CreateLogicalAnd instead of CreateAnd and update comment.

[nikic]

LGTM

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

if (ConstantInt *CharC = dyn_cast<ConstantInt>(CharVal)) {
     size_t Pos = Str.rfind(CharC->getZExtValue(), EndOff);
     if (Pos == StringRef::npos)
       // When the character is not in the source array fold the result
       // to null regardless of Size.
       return NullPtr;
 
     if (LenC)
       // Fold memrchr(s, c, N) --> s + Pos for constant N > Pos.
       return B.CreateGEP(B.getInt8Ty(), SrcStr, B.getInt64(Pos));
 
     if (Str.find(CharC->getZExtValue(), Pos) == StringRef::npos) {
       // When there is just a single occurrence of C in S, fold
       //   memrchr(s, c, N) --> N <= Pos ? null : s + Pos
       // for nonconstant N.
       Value *Cmp = B.CreateICmpULE(Size, ConstantInt::get(Size->getType(),
                 Pos),
            "memrchr.cmp");
       Value *SrcPlus = B.CreateGEP(B.getInt8Ty(), SrcStr, B.getInt64(Pos),
            "memrchr.ptr_plus");
       return B.CreateSelect(Cmp, NullPtr, SrcPlus, "memrchr.sel");
     }
   }
 
+  // Truncate the string to search at most EndOff characters.
+  Str = Str.substr(0, EndOff);
+  if (Str.find_first_not_of(Str[0]) != StringRef::npos)
     return nullptr;
+
+  // If the source array consists of all equal characters, then for any
+  // C and N (whether in bounds or not), fold memrchr(S, C, N) to
+  //   N != 0 && *S == C ? S + N - 1 : null
+  Type *SizeTy = Size->getType();
+  Type *Int8Ty = B.getInt8Ty();
+  Value *NNeZ = B.CreateICmpNE(Size, ConstantInt::get(SizeTy, 0));
+  // Slice off the sought character's high end bits.
+  CharVal = B.CreateTrunc(CharVal, Int8Ty);
+  Value *CEqS0 = B.CreateICmpEQ(ConstantInt::get(Int8Ty, Str[0]), CharVal);
+  Value *And = B.CreateLogicalAnd(NNeZ, CEqS0);
+  Value *SizeM1 = B.CreateSub(Size, ConstantInt::get(SizeTy, 1));
+  Value *SrcPlus = B.CreateGEP(Int8Ty, SrcStr, SizeM1, "memrchr.ptr_plus");
+  return B.CreateSelect(And, SrcPlus, NullPtr, "memrchr.sel");
 }
 
 Value *LibCallSimplifier::optimizeMemChr(CallInst *CI, IRBuilderBase &B) {
   Value *SrcStr = CI->getArgOperand(0);
   Value *Size = CI->getArgOperand(2);
   if (isKnownNonZero(Size, DL))
     annotateNonNullNoUndefBasedOnAccess(CI, 0);
 

llvm/test/Transforms/InstCombine/memrchr-4.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 ;
 ; Verify that memrchr calls with a string consisting of all the same
-; characters are folded.
+; characters are folded and those with mixed strings are not.
 
 declare i8* @memrchr(i8*, i32, i64)
 
 @a11111 = constant [5 x i8] c"\01\01\01\01\01"
 @a1110111 = constant [7 x i8] c"\01\01\01\00\01\01\01"
 
 
 ; Fold memrchr(a11111, C, 5) to *a11111 == C ? a11111 + 5 - 1 : null.
 
 define i8* @fold_memrchr_a11111_c_5(i32 %C) {
 ; CHECK-LABEL: @fold_memrchr_a11111_c_5(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(5) getelementptr inbounds ([5 x i8], [5 x i8]* @a11111, i64 0, i64 0), i32 [[C:%.*]], i64 5)
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 1
+; CHECK-NEXT:    [[MEMRCHR_SEL:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a11111, i64 0, i64 4), i8* null
+; CHECK-NEXT:    ret i8* [[MEMRCHR_SEL]]
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a11111, i64 0, i64 0
   %ret = call i8* @memrchr(i8* %ptr, i32 %C, i64 5)
   ret i8* %ret
 }
 
 
+; Fold memrchr(a11111, C, N) to N && *a11111 == C ? a11111 + N - 1 : null,
+; on the assumption that N is in bounds.
+
+define i8* @fold_memrchr_a11111_c_n(i32 %C, i64 %N) {
+; CHECK-LABEL: @fold_memrchr_a11111_c_n(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[N:%.*]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i8 [[TMP2]], 1
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP1]], i1 [[TMP3]], i1 false
+; CHECK-NEXT:    [[TMP5:%.*]] = add i64 [[N]], -1
+; CHECK-NEXT:    [[MEMRCHR_PTR_PLUS:%.*]] = getelementptr [5 x i8], [5 x i8]* @a11111, i64 0, i64 [[TMP5]]
+; CHECK-NEXT:    [[MEMRCHR_SEL:%.*]] = select i1 [[TMP4]], i8* [[MEMRCHR_PTR_PLUS]], i8* null
+; CHECK-NEXT:    ret i8* [[MEMRCHR_SEL]]
+;
+
+  %ptr = getelementptr [5 x i8], [5 x i8]* @a11111, i64 0, i64 0
+  %ret = call i8* @memrchr(i8* %ptr, i32 %C, i64 %N)
+  ret i8* %ret
+}
+
+
 ; Fold memrchr(a1110111, C, 3) to a1110111[2] == C ? a1110111 + 2 : null.
 
 define i8* @fold_memrchr_a1110111_c_3(i32 %C) {
 ; CHECK-LABEL: @fold_memrchr_a1110111_c_3(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(3) getelementptr inbounds ([7 x i8], [7 x i8]* @a1110111, i64 0, i64 0), i32 [[C:%.*]], i64 3)
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 1
+; CHECK-NEXT:    [[MEMRCHR_SEL:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([7 x i8], [7 x i8]* @a1110111, i64 0, i64 2), i8* null
+; CHECK-NEXT:    ret i8* [[MEMRCHR_SEL]]
 ;
 
   %ptr = getelementptr [7 x i8], [7 x i8]* @a1110111, i64 0, i64 0
   %ret = call i8* @memrchr(i8* %ptr, i32 %C, i64 3)
   ret i8* %ret
 }
 
 
 ; Don't fold memrchr(a1110111, C, 4).
 
 define i8* @call_memrchr_a1110111_c_4(i32 %C) {
 ; CHECK-LABEL: @call_memrchr_a1110111_c_4(
 ; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4) getelementptr inbounds ([7 x i8], [7 x i8]* @a1110111, i64 0, i64 0), i32 [[C:%.*]], i64 4)
 ; CHECK-NEXT:    ret i8* [[RET]]
 ;
 
   %ptr = getelementptr [7 x i8], [7 x i8]* @a1110111, i64 0, i64 0
   %ret = call i8* @memrchr(i8* %ptr, i32 %C, i64 4)
   ret i8* %ret
 }
 
 
 ; Don't fold memrchr(a1110111, C, 7).
 
-define i8* @call_memrchr_a11111_c_7(i32 %C) {
-; CHECK-LABEL: @call_memrchr_a11111_c_7(
+define i8* @call_memrchr_a1110111_c_7(i32 %C) {
+; CHECK-LABEL: @call_memrchr_a1110111_c_7(
 ; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(7) getelementptr inbounds ([7 x i8], [7 x i8]* @a1110111, i64 0, i64 0), i32 [[C:%.*]], i64 7)
 ; CHECK-NEXT:    ret i8* [[RET]]
 ;
 
   %ptr = getelementptr [7 x i8], [7 x i8]* @a1110111, i64 0, i64 0
   %ret = call i8* @memrchr(i8* %ptr, i32 %C, i64 7)
   ret i8* %ret
 }
+
+
+; Don't fold memrchr(a1110111, C, N).
+
+define i8* @call_memrchr_a1110111_c_n(i32 %C, i64 %N) {
+; CHECK-LABEL: @call_memrchr_a1110111_c_n(
+; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @a1110111, i64 0, i64 0), i32 [[C:%.*]], i64 [[N:%.*]])
+; CHECK-NEXT:    ret i8* [[RET]]
+;
+
+  %ptr = getelementptr [7 x i8], [7 x i8]* @a1110111, i64 0, i64 0
+  %ret = call i8* @memrchr(i8* %ptr, i32 %C, i64 %N)
+  ret i8* %ret
+}