Index: llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
===================================================================
--- llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
+++ llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
@@ -903,6 +903,31 @@
       return nullptr;
   }
 
+  if (ConstantInt *CharC = dyn_cast<ConstantInt>(CharVal)) {
+    // Fold memrchr(S, C, N) for a constant C.
+    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");
+    }
+  }
+
   return nullptr;
 }
 
Index: llvm/test/Transforms/InstCombine/memrchr-3.ll
===================================================================
--- llvm/test/Transforms/InstCombine/memrchr-3.ll
+++ llvm/test/Transforms/InstCombine/memrchr-3.ll
@@ -105,8 +105,7 @@
 
 define i8* @fold_memrchr_a12345_5_5() {
 ; CHECK-LABEL: @fold_memrchr_a12345_5_5(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(5) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 5, i64 5)
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    ret i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 4)
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0
@@ -119,8 +118,7 @@
 
 define i8* @fold_memrchr_a12345_5_4() {
 ; CHECK-LABEL: @fold_memrchr_a12345_5_4(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 5, i64 4)
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    ret i8* null
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0
@@ -133,8 +131,7 @@
 
 define i8* @fold_memrchr_a12345_4_5() {
 ; CHECK-LABEL: @fold_memrchr_a12345_4_5(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(5) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 4, i64 5)
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    ret i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 3)
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0
@@ -147,8 +144,7 @@
 
 define i8* @fold_memrchr_a12345p1_1_4() {
 ; CHECK-LABEL: @fold_memrchr_a12345p1_1_4(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 1), i32 5, i64 4)
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    ret i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 4)
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 1
@@ -161,8 +157,7 @@
 
 define i8* @fold_memrchr_a12345_2_5() {
 ; CHECK-LABEL: @fold_memrchr_a12345_2_5(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(5) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 2, i64 5)
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    ret i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 1)
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0
@@ -175,8 +170,7 @@
 
 define i8* @fold_memrchr_a12345_0_n(i64 %N) {
 ; CHECK-LABEL: @fold_memrchr_a12345_0_n(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 0, i64 [[TMP0:%.*]])
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    ret i8* null
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0
@@ -185,12 +179,35 @@
 }
 
 
+; 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(
+;
+
+  %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(
+;
+
+  %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
+}
+
+
 ; Fold memrchr(a123123, 3, 5) to a123123 + 2.
 
 define i8* @fold_memrchr_a123123_3_5() {
 ; CHECK-LABEL: @fold_memrchr_a123123_3_5(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(5) getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 3, i64 5)
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    ret i8* getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 2)
 ;
 
   %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0
@@ -203,8 +220,7 @@
 
 define i8* @fold_memrchr_a123123_3_6() {
 ; CHECK-LABEL: @fold_memrchr_a123123_3_6(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(6) getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 3, i64 6)
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    ret i8* getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 5)
 ;
 
   %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0
@@ -216,8 +232,7 @@
 
 define i8* @fold_memrchr_a123123_2_6() {
 ; CHECK-LABEL: @fold_memrchr_a123123_2_6(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(6) getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 2, i64 6)
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    ret i8* getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 4)
 ;
 
   %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0
@@ -229,8 +244,7 @@
 
 define i8* @fold_memrchr_a123123_1_6() {
 ; CHECK-LABEL: @fold_memrchr_a123123_1_6(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(6) getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 1, i64 6)
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    ret i8* getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 3)
 ;
 
   %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0
@@ -243,11 +257,53 @@
 
 define i8* @fold_memrchr_a123123_0_6() {
 ; CHECK-LABEL: @fold_memrchr_a123123_0_6(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(6) getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 0, i64 6)
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    ret i8* null
 ;
 
   %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0
   %ret = call i8* @memrchr(i8* %ptr, i32 0, i64 6)
   ret i8* %ret
 }
+
+
+; Fold memrchr(a123123, 0, n) to null
+
+define i8* @fold_memrchr_a123123_0_n(i64 %n) {
+; CHECK-LABEL: @fold_memrchr_a123123_0_n(
+; CHECK-NEXT:    ret i8* null
+;
+
+  %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0
+  %ret = call i8* @memrchr(i8* %ptr, i32 0, i64 %n)
+  ret i8* %ret
+}
+
+
+; Don't fold memrchr(a123123, 3, n) (although it's possible to fold the call
+; for a small number of occurrences of the character greater than one, it's
+; less and less profitable as the number grows).
+
+define i8* @call_memrchr_a123123_3_n(i64 %n) {
+; CHECK-LABEL: @call_memrchr_a123123_3_n(
+; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 3, 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 3, i64 %n)
+  ret i8* %ret
+}
+
+
+; Same as above but for 2.
+
+define i8* @call_memrchr_a123123_2_n(i64 %n) {
+; CHECK-LABEL: @call_memrchr_a123123_2_n(
+; 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
+}