[InstCombine] Fold memchr of sequences of same characters

[msebor]

Summary

This change enhances the memchr library function handler to fold calls with one or two consecutive sequences of the same character, analogously to the corresponding feature recently added to the memrchr handler (D123631). Rather than just one sequence as for memrchr, this one handles also two sequences in order to also benefit strchr.

Tested on x86_64-linux by building Clang and running make check-all.

[nikic]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

302

Unrelated change (in strchr rather than memchr)?

1055

As far as I can tell EndOff doesn't actually get used later, it's only used for the substr(), so I'm not sure why this code is changing rather than only being moved.

I think in https://reviews.llvm.org/D123472 the wrong version of the patch ended up being committed, I remember there being a static substr() function for this purpose, but it doesn't seem to be present on main.

1066

I don't think this is correct for the case where N is variable. Let's say we have S = "12", C = 2 and N = 1 (known only at runtime). The correct result for this is null. I believe your code would return S + 1.

There doesn't seem to be test coverage for this case (variable N with two runs -- there's only one with three runs).

llvm/test/Transforms/InstCombine/memchr-6.ll

19

Why does this one not fold?

53

Unrelated: There's a canonicalization opportunity here to convert C1 ? X : (C2 ? X : Y) to (C1 ? true : C2) ? X : Y` (or vice versa, but I'd consider logical or more canonical here).

[msebor]

• Add a substr helper function and call it.
• Remove a spurious change to LibCallSimplifier::optimizeStrChr.
• Add a missing conditional and a test case for it.

[msebor]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

1055

Yes, I must have committed a prior version of the patch.

1066

Good catch! I've added the missing conditional and a test case for it.

(For what it's worth, plain C runtime tests would help spot these mistakes sooner.)

llvm/test/Transforms/InstCombine/memchr-6.ll

19

Because a00000 has no initializer getConstantDataArrayInfo returns a null Slice.Array that getConstantStringInfo then fails for. I've added a comment to the test.

I thought I'd handled it D125114 but apparently it needs another enhancement. I can take care of it in a followup.

53

I've reworked the conditional a bit and I'm not sure I see this opportunity there anymore but let me know if I missed it.

[nikic]

LGTM

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

1055

I'd suggest landing the substr() function as a separate NFC patch, as it's not directly related to this one (and we'd want to replace the other usages at the same time as well).

llvm/test/Transforms/InstCombine/memchr-6.ll

19

Hrm, that would probably also require an API change, because we don't have any already allocated string we could create a StringRef to.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

 Value *LibCallSimplifier::optimizeStrChr(CallInst *CI, IRBuilderBase &B) {
   Function *Callee = CI->getCalledFunction();
   FunctionType *FT = Callee->getFunctionType();
   Value *SrcStr = CI->getArgOperand(0);
   annotateNonNullNoUndefBasedOnAccess(CI, 0);
 
   // If the second operand is non-constant, see if we can compute the length
   // of the input string and turn this into memchr.
-  ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
+  Value *CharVal = CI->getArgOperand(1);
+  ConstantInt *CharC = dyn_cast<ConstantInt>(CharVal);
   if (!CharC) {
     uint64_t Len = GetStringLength(SrcStr);
     if (Len)
       annotateDereferenceableBytes(CI, 0, Len);
     else
       return nullptr;
     if (!FT->getParamType(1)->isIntegerTy(32)) // memchr needs i32.
       return nullptr;
Value *LibCallSimplifier::optimizeMemChr(CallInst *CI, IRBuilderBase &B) {
   Value *SrcStr = CI->getArgOperand(0);
   Value *Size = CI->getArgOperand(2);
   if (isKnownNonZero(Size, DL))
     annotateNonNullNoUndefBasedOnAccess(CI, 0);
 
   Value *CharVal = CI->getArgOperand(1);
   ConstantInt *CharC = dyn_cast<ConstantInt>(CharVal);
   ConstantInt *LenC = dyn_cast<ConstantInt>(Size);
+  Value *NullPtr = Constant::getNullValue(CI->getType());
 
   // memchr(x, y, 0) -> null
   if (LenC) {
     if (LenC->isZero())
-      return Constant::getNullValue(CI->getType());
+      return NullPtr;
 
     if (LenC->isOne()) {
       // Fold memchr(x, y, 1) --> *x == y ? x : null for any x and y,
       // constant or otherwise.
       Value *Val = B.CreateLoad(B.getInt8Ty(), SrcStr, "memchr.char0");
       // Slice off the character's high end bits.
       CharVal = B.CreateTrunc(CharVal, B.getInt8Ty());
       Value *Cmp = B.CreateICmpEQ(Val, CharVal, "memchr.char0cmp");
-      Value *NullPtr = Constant::getNullValue(CI->getType());
       return B.CreateSelect(Cmp, SrcStr, NullPtr, "memchr.sel");
     }
   }
 
   StringRef Str;
   if (!getConstantStringInfo(SrcStr, Str, 0, /*TrimAtNul=*/false))
     return nullptr;
 
   if (CharC) {
     size_t Pos = Str.find(CharC->getZExtValue());
     if (Pos == StringRef::npos)
       // When the character is not in the source array fold the result
       // to null regardless of Size.
-      return Constant::getNullValue(CI->getType());
+      return NullPtr;
 
     // Fold memchr(s, c, n) -> n <= Pos ? null : s + Pos
     // When the constant Size is less than or equal to the character
     // position also fold the result to null.
     Value *Cmp = B.CreateICmpULE(Size, ConstantInt::get(Size->getType(), Pos),
                                  "memchr.cmp");
-    Value *NullPtr = Constant::getNullValue(CI->getType());
     Value *SrcPlus =
         B.CreateGEP(B.getInt8Ty(), SrcStr, B.getInt64(Pos), "memchr.ptr");
     return B.CreateSelect(Cmp, NullPtr, SrcPlus);
   }
 
+  uint64_t EndOff = UINT64_MAX;
+  if (LenC) {
+    EndOff = LenC->getZExtValue();
+    // Either truncate the string to LenC or set EndOff to its size,
+    // including the terminating null, whichever is smaller.
+    if (EndOff < Str.size())
+      Str = Str.substr(0, EndOff);
+    else
+      EndOff = Str.size();
+  }
+
+  size_t Pos = Str.find_first_not_of(Str[0]);
+  if (Pos == StringRef::npos
+      || Str.find_first_not_of(Str[Pos], Pos) == StringRef::npos) {
+    // If the source array consists of at most two consecutive sequences
+    // of the same characters, then for any C and N (whether in bounds or
+    // not), fold memchr(S, C, N) to
+    //   N != 0 && *S == C ? S : null
+    // or for the two sequences to:
+    //   N != 0 ? (S[0] == C ? S : S[Pos] == C ? S + Pos : null) : null
+    // where       ^Sel2    and    ^Sel1 are denoted above.
+    // The latter makes it also possible to fold strchr() calls with
+    // strings of the same characters.
+    Type *SizeTy = Size->getType();
+    Type *Int8Ty = B.getInt8Ty();
+
+    // Slice off the sought character's high end bits.
+    CharVal = B.CreateTrunc(CharVal, Int8Ty);
+
+    Value *Sel1 = NullPtr;
+    if (Pos != StringRef::npos) {
+      // Handle two consecutive sequences of the same characters.
+      Value *PosVal = ConstantInt::get(SizeTy, Pos);
+      Value *StrPos = ConstantInt::get(Int8Ty, Str[Pos]);
+      Value *CEqSPos = B.CreateICmpEQ(CharVal, StrPos);
+      Value *SrcPlus = B.CreateInBoundsGEP(B.getInt8Ty(), SrcStr, PosVal);
+      Sel1 = B.CreateSelect(CEqSPos, SrcPlus, NullPtr, "memchr.sel1");
+    }
+
+    Value *Str0 = ConstantInt::get(Int8Ty, Str[0]);
+    Value *CEqS0 = B.CreateICmpEQ(Str0, CharVal);
+    Value *Sel2 = B.CreateSelect(CEqS0, SrcStr, Sel1, "memchr.sel2");
+
+    Value *NNeZ = B.CreateICmpNE(Size, ConstantInt::get(SizeTy, 0));
+    return B.CreateSelect(NNeZ, Sel2, NullPtr, "memchr.sel3");
+  }
+
   if (!LenC)
     // From now on we need a constant length and constant array.
     return nullptr;
 
-  // Truncate the string to LenC without slicing when targeting LP64
-  // on an ILP32 host.
-  uint64_t EndOff = std::min(LenC->getZExtValue(), (uint64_t)StringRef::npos);
-  Str = Str.substr(0, EndOff);
-
   // If the char is variable but the input str and length are not we can turn
   // this memchr call into a simple bit field test. Of course this only works
   // when the return value is only checked against null.
   //
   // It would be really nice to reuse switch lowering here but we can't change
   // the CFG at this point.
   //
   // memchr("\r\n", C, 2) != nullptr -> (1 << C & ((1 << '\r') | (1 << '\n')))

llvm/test/Transforms/InstCombine/memchr-6.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=instcombine -S | FileCheck %s
+;
+; Verify that memchr calls with a string consisting of all the same
+; characters are folded and those with mixed strings are not.
+
+declare i8* @memchr(i8*, i32, i64)
+
+@a00000 = constant [5 x i8] zeroinitializer
+@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 memchr(a00000, C, 5) to *a00000 == C ? a00000 : null.
+
+define i8* @fold_memchr_a00000_c_5(i32 %C) {
+; CHECK-LABEL: @fold_memchr_a00000_c_5(
+; CHECK-NEXT:    [[RET:%.*]] = call i8* @memchr(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([5 x i8], [5 x i8]* @a00000, i64 0, i64 0), i32 [[C:%.*]], i64 5)
+; CHECK-NEXT:    ret i8* [[RET]]
+;
+
+  %ptr = getelementptr [5 x i8], [5 x i8]* @a00000, i64 0, i64 0
+  %ret = call i8* @memchr(i8* %ptr, i32 %C, i64 5)
+  ret i8* %ret
+}
+
+
+; Fold memchr(a11111, C, 5) to *a11111 == C ? a11111 : null.
+
+define i8* @fold_memchr_a11111_c_5(i32 %C) {
+; CHECK-LABEL: @fold_memchr_a11111_c_5(
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 1
+; CHECK-NEXT:    [[MEMCHR_SEL2:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a11111, i64 0, i64 0), i8* null
+; CHECK-NEXT:    ret i8* [[MEMCHR_SEL2]]
+;
+
+  %ptr = getelementptr [5 x i8], [5 x i8]* @a11111, i64 0, i64 0
+  %ret = call i8* @memchr(i8* %ptr, i32 %C, i64 5)
+  ret i8* %ret
+}
+
+
+; Fold memchr(a11111, C, N) to N && *a11111 == C ? a11111 : null,
+; on the assumption that N is in bounds.
+
+define i8* @fold_memchr_a11111_c_n(i32 %C, i64 %N) {
+; CHECK-LABEL: @fold_memchr_a11111_c_n(
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 1
+; CHECK-NEXT:    [[MEMCHR_SEL2:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a11111, i64 0, i64 0), i8* null
+; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i64 [[N:%.*]], 0
+; CHECK-NEXT:    [[MEMCHR_SEL3:%.*]] = select i1 [[DOTNOT]], i8* null, i8* [[MEMCHR_SEL2]]
+; CHECK-NEXT:    ret i8* [[MEMCHR_SEL3]]
+;
+
+  %ptr = getelementptr [5 x i8], [5 x i8]* @a11111, i64 0, i64 0
+  %ret = call i8* @memchr(i8* %ptr, i32 %C, i64 %N)
+  ret i8* %ret
+}
+
+
+; Fold memchr(a1110111, C, 3) to a1110111[2] == C ? a1110111 : null.
+
+define i8* @fold_memchr_a1110111_c_3(i32 %C) {
+; CHECK-LABEL: @fold_memchr_a1110111_c_3(
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 1
+; CHECK-NEXT:    [[MEMCHR_SEL2:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([7 x i8], [7 x i8]* @a1110111, i64 0, i64 0), i8* null
+; CHECK-NEXT:    ret i8* [[MEMCHR_SEL2]]
+;
+
+  %ptr = getelementptr [7 x i8], [7 x i8]* @a1110111, i64 0, i64 0
+  %ret = call i8* @memchr(i8* %ptr, i32 %C, i64 3)
+  ret i8* %ret
+}
+
+
+; Don't fold memchr(a1110111, C, 4).
+
+define i8* @call_memchr_a1110111_c_4(i32 %C) {
+; CHECK-LABEL: @call_memchr_a1110111_c_4(
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    [[MEMCHR_SEL1:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([7 x i8], [7 x i8]* @a1110111, i64 0, i64 3), i8* null
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i8 [[TMP1]], 1
+; CHECK-NEXT:    [[MEMCHR_SEL2:%.*]] = select i1 [[TMP3]], i8* getelementptr inbounds ([7 x i8], [7 x i8]* @a1110111, i64 0, i64 0), i8* [[MEMCHR_SEL1]]
+; CHECK-NEXT:    ret i8* [[MEMCHR_SEL2]]
+;
+
+  %ptr = getelementptr [7 x i8], [7 x i8]* @a1110111, i64 0, i64 0
+  %ret = call i8* @memchr(i8* %ptr, i32 %C, i64 4)
+  ret i8* %ret
+}
+
+
+; Don't fold memchr(a1110111, C, 7).
+
+define i8* @call_memchr_a1110111_c_7(i32 %C) {
+; CHECK-LABEL: @call_memchr_a1110111_c_7(
+; CHECK-NEXT:    [[RET:%.*]] = call i8* @memchr(i8* noundef nonnull dereferenceable(1) 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* @memchr(i8* %ptr, i32 %C, i64 7)
+  ret i8* %ret
+}
+
+
+; Don't fold memchr(a1110111, C, N).
+
+define i8* @call_memchr_a1110111_c_n(i32 %C, i64 %N) {
+; CHECK-LABEL: @call_memchr_a1110111_c_n(
+; CHECK-NEXT:    [[RET:%.*]] = call i8* @memchr(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* @memchr(i8* %ptr, i32 %C, i64 %N)
+  ret i8* %ret
+}

llvm/test/Transforms/InstCombine/memchr.ll

 ; CHECK-NEXT:    ret void
 ;
   %str = getelementptr [14 x i8], [14 x i8]* @hello, i32 0, i32 0
   %dst = call i8* @memchr(i8* %str, i32 119, i32 6)
   store i8* %dst, i8** @chp
   ret void
 }
 
-; Check transformation memchr("\r\n", C, 2) != nullptr -> (C & 9216) != 0
+; Check transformation memchr("\r\n", C, 3) != nullptr -> (C & 9217) != 0
 define i1 @test11(i32 %C) {
 ; CHECK-LABEL: @test11(
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i16
 ; CHECK-NEXT:    [[TMP2:%.*]] = and i16 [[TMP1]], 255
 ; CHECK-NEXT:    [[MEMCHR_BOUNDS:%.*]] = icmp ult i16 [[TMP2]], 16
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i16 1, [[TMP2]]
-; CHECK-NEXT:    [[TMP4:%.*]] = and i16 [[TMP3]], 9216
+; CHECK-NEXT:    [[TMP4:%.*]] = and i16 [[TMP3]], 9217
 ; CHECK-NEXT:    [[MEMCHR_BITS:%.*]] = icmp ne i16 [[TMP4]], 0
 ; CHECK-NEXT:    [[MEMCHR:%.*]] = select i1 [[MEMCHR_BOUNDS]], i1 [[MEMCHR_BITS]], i1 false
 ; CHECK-NEXT:    ret i1 [[MEMCHR]]
 ;
-  %dst = call i8* @memchr(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @newlines, i64 0, i64 0), i32 %C, i32 2)
+  %dst = call i8* @memchr(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @newlines, i64 0, i64 0), i32 %C, i32 3)
   %cmp = icmp ne i8* %dst, null
   ret i1 %cmp
 }
 
 ; No 64 bits here
 define i1 @test12(i32 %C) {
 ; CHECK-LABEL: @test12(
 ; CHECK-NEXT:    [[DST:%.*]] = call i8* @memchr(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([4 x i8], [4 x i8]* @spaces, i32 0, i32 0), i32 [[C:%.*]], i32 3)
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8* [[DST]], null
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %dst = call i8* @memchr(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @spaces, i64 0, i64 0), i32 %C, i32 3)
   %cmp = icmp ne i8* %dst, null
   ret i1 %cmp
 }
 
 define i1 @test13(i32 %C) {
 ; CHECK-LABEL: @test13(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C:%.*]], 255
-; CHECK-NEXT:    [[MEMCHR_BOUNDS:%.*]] = icmp ult i32 [[TMP1]], 32
-; CHECK-NEXT:    [[TMP2:%.*]] = shl i32 1, [[TMP1]]
-; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], -2147483647
-; CHECK-NEXT:    [[MEMCHR_BITS:%.*]] = icmp ne i32 [[TMP3]], 0
-; CHECK-NEXT:    [[MEMCHR:%.*]] = select i1 [[MEMCHR_BOUNDS]], i1 [[MEMCHR_BITS]], i1 false
-; CHECK-NEXT:    ret i1 [[MEMCHR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i8 [[TMP1]], 31
+; CHECK-NEXT:    [[CMP:%.*]] = or i1 [[TMP3]], [[TMP2]]
+; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %dst = call i8* @memchr(i8* getelementptr inbounds ([2 x i8], [2 x i8]* @single, i64 0, i64 0), i32 %C, i32 2)
   %cmp = icmp ne i8* %dst, null
   ret i1 %cmp
 }
 
 define i1 @test14(i32 %C) {
 ; CHECK-LABEL: @test14(

llvm/test/Transforms/InstCombine/strchr-3.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=instcombine -S | FileCheck %s
+;
+; Verify that strchr calls with a string consisting of one or two sequences
+; of all the same characters are folded and those with mixed strings are not.
+
+@s1 = constant [2 x i8] c"\01\00"
+@s11 = constant [3 x i8] c"\01\01\00"
+@s111 = constant [4 x i8] c"\01\01\01\00"
+@s000 = constant [4 x i8] c"\00\00\00\00"
+@s11102 = constant [6 x i8] c"\01\01\01\00\02\00"
+@s21111 = constant [6 x i8] c"\02\01\01\01\01\00"
+
+declare i8* @strchr(i8*, i32)
+
+
+; Fold strchr(S = "\01", C) to C == '\01' ? S : C == '\0' ? S + 1 : null.
+
+define i8* @fold_strchr_s1_C(i32 %C) {
+; CHECK-LABEL: @fold_strchr_s1_C(
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    [[MEMCHR_SEL1:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([2 x i8], [2 x i8]* @s1, i64 0, i64 1), i8* null
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i8 [[TMP1]], 1
+; CHECK-NEXT:    [[MEMCHR_SEL2:%.*]] = select i1 [[TMP3]], i8* getelementptr inbounds ([2 x i8], [2 x i8]* @s1, i64 0, i64 0), i8* [[MEMCHR_SEL1]]
+; CHECK-NEXT:    ret i8* [[MEMCHR_SEL2]]
+;
+  %ptr = getelementptr inbounds [2 x i8], [2 x i8]* @s1, i64 0, i64 0
+  %ret = call i8* @strchr(i8* %ptr, i32 %C)
+  ret i8* %ret
+}
+
+
+; Fold strchr(S = "\01\01", C) to C == '\01' ? S : C == '\0' ? S + 2 : null.
+
+define i8* @fold_strchr_s11_C(i32 %C) {
+; CHECK-LABEL: @fold_strchr_s11_C(
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    [[MEMCHR_SEL1:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([3 x i8], [3 x i8]* @s11, i64 0, i64 2), i8* null
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i8 [[TMP1]], 1
+; CHECK-NEXT:    [[MEMCHR_SEL2:%.*]] = select i1 [[TMP3]], i8* getelementptr inbounds ([3 x i8], [3 x i8]* @s11, i64 0, i64 0), i8* [[MEMCHR_SEL1]]
+; CHECK-NEXT:    ret i8* [[MEMCHR_SEL2]]
+;
+  %ptr = getelementptr inbounds [3 x i8], [3 x i8]* @s11, i64 0, i64 0
+  %ret = call i8* @strchr(i8* %ptr, i32 %C)
+  ret i8* %ret
+}
+
+
+; Fold strchr(S = "\01\01\01", C) to C == '\01' ? S : C == '\0' ? S + 3 : null.
+
+define i8* @fold_strchr_s111_C(i32 %C) {
+; CHECK-LABEL: @fold_strchr_s111_C(
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    [[MEMCHR_SEL1:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s111, i64 0, i64 3), i8* null
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i8 [[TMP1]], 1
+; CHECK-NEXT:    [[MEMCHR_SEL2:%.*]] = select i1 [[TMP3]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s111, i64 0, i64 0), i8* [[MEMCHR_SEL1]]
+; CHECK-NEXT:    ret i8* [[MEMCHR_SEL2]]
+;
+  %ptr = getelementptr inbounds [4 x i8], [4 x i8]* @s111, i64 0, i64 0
+  %ret = call i8* @strchr(i8* %ptr, i32 %C)
+  ret i8* %ret
+}
+
+
+; Fold strchr(S = "\00\00\00", C) to C == '\0' ? S : null.
+
+define i8* @fold_strchr_s000_C(i32 %C) {
+; CHECK-LABEL: @fold_strchr_s000_C(
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[MEMCHR_CHAR0CMP:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    [[MEMCHR_SEL:%.*]] = select i1 [[MEMCHR_CHAR0CMP]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s000, i64 0, i64 0), i8* null
+; CHECK-NEXT:    ret i8* [[MEMCHR_SEL]]
+;
+  %ptr = getelementptr inbounds [4 x i8], [4 x i8]* @s000, i64 0, i64 0
+  %ret = call i8* @strchr(i8* %ptr, i32 %C)
+  ret i8* %ret
+}
+
+
+; Do not fold strchr(S = "\02\01\01\01\01", C).  It's transformed to
+; memchr(S, C, 6).
+
+define i8* @xform_strchr_s21111_C(i32 %C) {
+; CHECK-LABEL: @xform_strchr_s21111_C(
+; CHECK-NEXT:    [[MEMCHR:%.*]] = call i8* @memchr(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([6 x i8], [6 x i8]* @s21111, i64 0, i64 0), i32 [[C:%.*]], i64 6)
+; CHECK-NEXT:    ret i8* [[MEMCHR]]
+;
+  %ptr = getelementptr inbounds [6 x i8], [6 x i8]* @s21111, i64 0, i64 0
+  %ret = call i8* @strchr(i8* %ptr, i32 %C)
+  ret i8* %ret
+}
+
+
+; Fold strchr(S = "\02\01\01\01\01" + 1, C) to
+;   C == '\01' ? S + 1 : C == '\0' ? S + 5 : null.
+
+define i8* @fold_strchr_s21111p1_C(i32 %C) {
+; CHECK-LABEL: @fold_strchr_s21111p1_C(
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    [[MEMCHR_SEL1:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s21111, i64 0, i64 5), i8* null
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i8 [[TMP1]], 1
+; CHECK-NEXT:    [[MEMCHR_SEL2:%.*]] = select i1 [[TMP3]], i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s21111, i64 0, i64 1), i8* [[MEMCHR_SEL1]]
+; CHECK-NEXT:    ret i8* [[MEMCHR_SEL2]]
+;
+  %ptr = getelementptr inbounds [6 x i8], [6 x i8]* @s21111, i64 0, i64 1
+  %ret = call i8* @strchr(i8* %ptr, i32 %C)
+  ret i8* %ret
+}
+
+; Fold strchr(S = "\01\01\01\00\02", C) to
+;   C == '\01' ? S : C == '\0' ? S + 3 : null.
+
+define i8* @fold_strchr_s11102_C(i32 %C) {
+; CHECK-LABEL: @fold_strchr_s11102_C(
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    [[MEMCHR_SEL1:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s11102, i64 0, i64 3), i8* null
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i8 [[TMP1]], 1
+; CHECK-NEXT:    [[MEMCHR_SEL2:%.*]] = select i1 [[TMP3]], i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s11102, i64 0, i64 0), i8* [[MEMCHR_SEL1]]
+; CHECK-NEXT:    ret i8* [[MEMCHR_SEL2]]
+;
+  %ptr = getelementptr inbounds [6 x i8], [6 x i8]* @s11102, i64 0, i64 0
+  %ret = call i8* @strchr(i8* %ptr, i32 %C)
+  ret i8* %ret
+}