[InstCombine] Fix memrchr logic error that prevents folding

[msebor]

Summary

The memrchr enhancement added in D123629 has a logic bug that renders it ineffective in a subset of instances. The bug is (most likely) assuming that the second argument to StringRef::find() is the number of characters to search rather than the offset to search from. The tests that were added for these instances were precommitted so they didn't fail and during review none of us noticed the expected folding wasn't done.(*)

This change corrects the mistake and enables the folding.

(*) This seems like another gotcha to keep in mind with precommitting tests, one that could be helped by having XFAIL directives for individual assertions.)

[msebor]

Fix a copy and paste mistake in memrchr-3.ll.

[nikic]

LGTM

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

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
+    if (Str.find(Str[Pos]) == Pos) {
+      // When there is just a single occurrence of C in S, i.e., the one
+      // in Str[Pos], 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");
+                                                          Pos),
+                                   "memrchr.cmp");
       Value *SrcPlus = B.CreateGEP(B.getInt8Ty(), SrcStr, B.getInt64(Pos),
-           "memrchr.ptr_plus");
+                                   "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;

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

;
   ret i8* %ret
 }
 
 
 ; Fold memrchr(a12345, 3, n) to n < 3 ? null : s + 2.
 
 define i8* @fold_memrchr_a12345_3_n(i64 %n) {
 ; CHECK-LABEL: @fold_memrchr_a12345_3_n(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 3, i64 [[N:%.*]])
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    [[MEMRCHR_CMP:%.*]] = icmp ult i64 [[N:%.*]], 3
+; CHECK-NEXT:    [[MEMRCHR_SEL:%.*]] = select i1 [[MEMRCHR_CMP]], i8* null, i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 2)
+; CHECK-NEXT:    ret i8* [[MEMRCHR_SEL]]
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0
   %ret = call i8* @memrchr(i8* %ptr, i32 3, i64 %n)
   ret i8* %ret
 }
 
 
 ; Fold memrchr(a12345, 5, n) to n < 5 ? null : s + 4.
 
 define i8* @fold_memrchr_a12345_5_n(i64 %n) {
 ; CHECK-LABEL: @fold_memrchr_a12345_5_n(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 5, i64 [[N:%.*]])
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    [[MEMRCHR_CMP:%.*]] = icmp ult i64 [[N:%.*]], 5
+; CHECK-NEXT:    [[MEMRCHR_SEL:%.*]] = select i1 [[MEMRCHR_CMP]], i8* null, i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 4)
+; CHECK-NEXT:    ret i8* [[MEMRCHR_SEL]]
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0
   %ret = call i8* @memrchr(i8* %ptr, i32 5, i64 %n)
   ret i8* %ret
 }
 
 

 ; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 2, i64 [[N:%.*]])
 ; CHECK-NEXT:    ret i8* [[RET]]
 ;
 
   %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0
   %ret = call i8* @memrchr(i8* %ptr, i32 2, i64 %n)
   ret i8* %ret
 }
+
+
+; And again for 1 to exercise the other edge case.
+
+define i8* @call_memrchr_a123123_1_n(i64 %n) {
+; CHECK-LABEL: @call_memrchr_a123123_1_n(
+; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 1, i64 [[N:%.*]])
+; CHECK-NEXT:    ret i8* [[RET]]
+;
+
+  %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0
+  %ret = call i8* @memrchr(i8* %ptr, i32 1, i64 %n)
+  ret i8* %ret
+}