[InstCombine] Bail on memrchr calls with an excessive size.

[msebor]

Summary

This change implements folding of memrchr calls with constant bounds in excess of the size of the source array to null. This is done in preparation for a subsequent change that assumes the bound is valid.

Depends on D123626.

[msebor]

Add context.

[nikic]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

903

While this is correct, I do wonder whether we should be going out of our way to fold this to null, rather than simply bailing out of the transform. In particular, I wonder whether this will end up suppressing an asan/msan warning. It's okay to do that, as these are "best effort", but it's probably better to avoid if it doesn't cost us any additional effort?

[msebor]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

903

I don't yet know what the LLVM policy is for dealing with provably undefined code. I chose this because it seems like the lesser of the two evils (e.g., when passing in a negative/very large size). But I'm aware that some other handlers punt invalid calls to the library and I'm fine with that if it helps sanitizers detect the problem.

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

903

Or insert UnreachableInst?

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

903

But generally not worth to catch all UBs and fold them, so I agree with @nikic

[msebor]

Avoid folding memrchr calls with an excessive size to null.

I'm open to treating such calls with unreachable if there is broader support for it. In my experience, some users/projects are in favor of it, others prefer the current approach of making the library call, and others still would like to see it replaced with a trap. Providing a compiler option would let each group choose what works best for them.

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

906

But currently this patch does not make sense a bit as we would reach this nullptr (with your patch we reach it sooner).

So in the current form, I dont think we need this patch. This “bail out” you can add in the patch which uses this patch as a base.

[nikic]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

906

Yeah, this makes more sense as part of the next patch in the stack now.

[msebor]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

906

The follow-on patch depends on this hunk so now that they've both been reviewed and agreed on, whether they're applied separately or together doesn't seem important. But they're easy enough to merge before committing.

[nikic]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

906

Right. The code change itself is fine, so I'm marking this as approved.

[msebor]

This patch was committed as part of the next one in the series so I'm abandoning it to keep it from popping up as ready to land.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

if (LenC->isOne()) {
       Value *Val = B.CreateLoad(B.getInt8Ty(), SrcStr, "memrchr.char0");
       // Slice off the character's high end bits.
       CharVal = B.CreateTrunc(CharVal, B.getInt8Ty());
       Value *Cmp = B.CreateICmpEQ(Val, CharVal, "memrchr.char0cmp");
       return B.CreateSelect(Cmp, SrcStr, NullPtr, "memrchr.sel");
     }
   }
 
+  StringRef Str;
+  if (!getConstantStringInfo(SrcStr, Str, 0, /*TrimAtNul=*/false))
+    return nullptr;
+
+  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;
+  }
+
   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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 ;
-; Verify that memrchr calls with an out of bounds size are folded to null.
+; Verify that memrchr calls with an out of bounds size are not folded to
+; null (they might be intercepted by sanitizers).
 
 declare i8* @memrchr(i8*, i32, i64)
 
 @ax = external global [0 x i8]
 @ax1 = external global [1 x i8]
 @a12345 = constant [5 x i8] c"\01\02\03\04\05"
 
 
-; Fold memrchr(a12345, C, UINT32_MAX + 1LU) to null (and not to a12345
-; as might happen if the size were to be truncated to int32_t).
+; 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* @fold_memrchr_a12345_c_ui32max_p1(i32 %C) {
-; CHECK-LABEL: @fold_memrchr_a12345_1_ui32max_p1(
+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 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
 }
 
 
-; Fold memrchr(ax1, C, UINT32_MAX + 2LU) to null (and not to *ax1 == 1).
+; Do not fold memrchr(ax1, C, UINT32_MAX + 2LU) to null or to *ax1 == 1.
 
-define i8* @fold_memrchr_ax1_1_ui32max_p2(i32 %C) {
-; CHECK-LABEL: @fold_memrchr_ax1_1_ui32max_p2(
+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 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
 }
 
 
-; But don't fold memrchr(ax, C, UINT32_MAX + 2LU) to *ax == 1.
+; Do not fold memrchr(ax, C, UINT32_MAX + 2LU) to *ax == 1.
 
-define i8* @fold_memrchr_ax_1_ui32max_p2(i32 %C) {
-; CHECK-LABEL: @fold_memrchr_ax_1_ui32max_p2(
-; CHECK-NEXT:    [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4294967297) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 [[TMP0:%.*]], i64 4294967297)
+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 i8* [[RET]]
 ;
 
-  %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i64 0, i64 0
+  %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
 }
 
 
-; Fold memrchr(a12345, C, 6) to null.
+; Do not fold memrchr(a12345, C, 6) to null.
 
-define i8* @fold_memrchr_a12345_c_6(i32 %C) {
-; CHECK-LABEL: @fold_memrchr_a12345_c_6(
+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 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
 }
 
 
-; Fold memrchr(a12345, C, SIZE_MAX) to null.
+; Do not fold memrchr(a12345, C, SIZE_MAX) to null.
 
-define i8* @fold_memrchr_a12345_c_szmax(i32 %C) {
-; CHECK-LABEL: @fold_memrchr_a12345_c_szmax(
+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 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
 }