[InstCombine] Fold memrchr calls with a constant character.

[msebor]

Summary

This change implements folding of memrchr calls with a constant array and character, analogous to memchr.

Depends on D123628.

[msebor]

Add context.

[nikic]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

944

Use NullPtr?

952

I don't think this is correct. Consider an unknown size and a string with two occurrences of C in it. Now assume that at runtime, the size is chosen to lie between the two occurrences of C. I believe your implementation will return null for that case, while it should return the first occurrence.

[nikic]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

952

Gah, I just realized that this code is only used for a known length, unlike the corresponding memchr() implementation. In this case EndOff will be the exact end offset, and not just an upper bound on it, and this code will always constant fold, so it's fine.

I think it would be clearer that this is a fully static if this directly emitted the appropriate result based on LenC->getValue().ule(Pos) rather than going through constant folding.

[nikic]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

952

Actually, if the length is constant, shouldn't this just directly return the GEP without any further comparisons?

[msebor]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

944

Sure.

952

You're right, thanks! Your comment makes me realize it's possible to also fold the call when n isn't known as long as there's just one occurrence of the character in the string. Let me do both.

[msebor]

Simplify folding when Len is constant and handle subset of cases when it isn't.

[nikic]

LG apart from test nits.

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

151–164

Should pass 1 here to match test description.

198

Missing check lines?

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

Value *LibCallSimplifier::optimizeMemRChr(CallInst *CI, IRBuilderBase &B) {
   uint64_t EndOff = UINT64_MAX;
   if (LenC) {
     EndOff = LenC->getZExtValue();
     if (Str.size() < EndOff)
       // Punt out-of-bounds accesses to sanitizers and/or libc.
       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;
 }
 
 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-2.ll

 @a12345 = constant [5 x i8] c"\01\02\03\04\05"
 
 
 ; Do not fold memrchr(a12345, C, UINT32_MAX + 1LU) to null or to a12345
 ; as might happen if the size were to be truncated to int32_t.
 
 define i8* @call_memrchr_a12345_c_ui32max_p1(i32 %C) {
 ; CHECK-LABEL: @call_memrchr_a12345_c_ui32max_p1(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4294967296) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 [[TMP0:%.*]], i64 4294967296)
+; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4294967296) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 [[C:%.*]], i64 4294967296)
 ; CHECK-NEXT:    ret i8* [[RET]]
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i64 0, i64 0
   %ret = call i8* @memrchr(i8* %ptr, i32 %C, i64 4294967296)
   ret i8* %ret
 }
 
 
 ; Do not fold memrchr(ax1, C, UINT32_MAX + 2LU) to null or to *ax1 == 1.
 
 define i8* @call_memrchr_ax1_c_ui32max_p2(i32 %C) {
 ; CHECK-LABEL: @call_memrchr_ax1_c_ui32max_p2(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4294967297) getelementptr inbounds ([1 x i8], [1 x i8]* @ax1, i64 0, i64 0), i32 [[TMP0:%.*]], i64 4294967297)
+; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4294967297) getelementptr inbounds ([1 x i8], [1 x i8]* @ax1, i64 0, i64 0), i32 [[C:%.*]], i64 4294967297)
 ; CHECK-NEXT:    ret i8* [[RET]]
 ;
 
   %ptr = getelementptr [1 x i8], [1 x i8]* @ax1, i64 0, i64 0
   %ret = call i8* @memrchr(i8* %ptr, i32 %C, i64 4294967297)
   ret i8* %ret
 }
 
 
 ; Do not fold memrchr(ax, C, UINT32_MAX + 2LU) to *ax == 1.
 
 define i8* @call_memrchr_ax_c_ui32max_p2(i32 %C) {
 ; CHECK-LABEL: @call_memrchr_ax_c_ui32max_p2(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4294967297) getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i32 [[TMP0:%.*]], i64 4294967297)
+; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4294967297) getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i32 [[C:%.*]], i64 4294967297)
 ; CHECK-NEXT:    ret i8* [[RET]]
 ;
 
   %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0
   %ret = call i8* @memrchr(i8* %ptr, i32 %C, i64 4294967297)
   ret i8* %ret
 }
 
 
 ; Do not fold memrchr(a12345, C, 6) to null.
 
 define i8* @call_memrchr_a12345_c_6(i32 %C) {
 ; CHECK-LABEL: @call_memrchr_a12345_c_6(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(6) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 [[TMP0:%.*]], i64 6)
+; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(6) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 [[C:%.*]], i64 6)
 ; CHECK-NEXT:    ret i8* [[RET]]
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i64 0, i64 0
   %ret = call i8* @memrchr(i8* %ptr, i32 %C, i64 6)
   ret i8* %ret
 }
 
 
 ; Do not fold memrchr(a12345, C, SIZE_MAX) to null.
 
 define i8* @call_memrchr_a12345_c_szmax(i32 %C) {
 ; CHECK-LABEL: @call_memrchr_a12345_c_szmax(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(18446744073709551615) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 [[TMP0:%.*]], i64 -1)
+; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(18446744073709551615) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 [[C:%.*]], i64 -1)
 ; CHECK-NEXT:    ret i8* [[RET]]
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i64 0, i64 0
   %ret = call i8* @memrchr(i8* %ptr, i32 %C, i64 18446744073709551615)
   ret i8* %ret
 }

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

;
   ret i8* %ret
 }
 
 
 ; Fold memrchr(a12345, 5, 5) to a12345 + 4.
 
 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
   %ret = call i8* @memrchr(i8* %ptr, i32 5, i64 5)
   ret i8* %ret
 }
 
 
 ; Fold memrchr(a12345, 5, 4) to null.
 
 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
   %ret = call i8* @memrchr(i8* %ptr, i32 5, i64 4)
   ret i8* %ret
 }
 
 
 ; Fold memrchr(a12345, 4, 5) to a12345 + 3.
 
 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
   %ret = call i8* @memrchr(i8* %ptr, i32 4, i64 5)
   ret i8* %ret
 }
 
 
 ; Fold memrchr(a12345 + 1, 1, 4) to null.
 
 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* null
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 1
-  %ret = call i8* @memrchr(i8* %ptr, i32 5, i64 4)
+  %ret = call i8* @memrchr(i8* %ptr, i32 1, i64 4)
+  ret i8* %ret
+}
+
+
+; Fold memrchr(a12345 + 1, 2, 4) to a12345 + 1.
+
+define i8* @fold_memrchr_a12345p1_2_4() {
+; CHECK-LABEL: @fold_memrchr_a12345p1_2_4(
+; 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 1
+  %ret = call i8* @memrchr(i8* %ptr, i32 2, i64 4)
   ret i8* %ret
 }
 
 
 ; Fold memrchr(a12345, 2, 5) to a12345 + 1.
 
 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
   %ret = call i8* @memrchr(i8* %ptr, i32 2, i64 5)
   ret i8* %ret
 }
 
 
 ; Fold memrchr(a12345, 0, %N) to null.
 
 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 [[N:%.*]])
-; CHECK-NEXT:    ret i8* [[RET]]
+; CHECK-NEXT:    ret i8* null
 ;
 
   %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0
   %ret = call i8* @memrchr(i8* %ptr, i32 0, i64 %N)
   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]]
+;
+
+  %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]]
+;
+
+  %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
   %ret = call i8* @memrchr(i8* %ptr, i32 3, i64 5)
   ret i8* %ret
 }
 
 
 ; Fold memrchr(a123123, 3, 6) to a123123 + 5.
 
 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
   %ret = call i8* @memrchr(i8* %ptr, i32 3, i64 6)
   ret i8* %ret
 }
 
 ; Fold memrchr(a123123, 2, 6) to a123123 + 4.
 
 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
   %ret = call i8* @memrchr(i8* %ptr, i32 2, i64 6)
   ret i8* %ret
 }
 
 ; Fold memrchr(a123123, 1, 6) to a123123 + 3.
 
 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
   %ret = call i8* @memrchr(i8* %ptr, i32 1, i64 6)
   ret i8* %ret
 }
 
 
 ; Fold memrchr(a123123, 0, 6) to null.
 
 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
+}