[InstCombine] Fold strnlen of strings at offsets and unknown bounds.

[msebor]

Summary

This patch in the strnlen series enables the handling of calls with constant arrays and variable offsets and variable bounds.

Depends on D123819.

[msebor]

I've dropped the prerequisite D123819 so I'm abandoning this as well.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

if (getConstantDataArrayInfo(GEP->getOperand(0), Slice, CharSize)) {
       } else {
         NullTermIdx = ~((uint64_t)0);
         for (uint64_t I = 0, E = Slice.Length; I < E; ++I) {
           if (Slice.Array->getElementAsInteger(I + Slice.Offset) == 0) {
             NullTermIdx = I;
             break;
           }
         }
-        if (NullTermIdx == ~((uint64_t)0))
+        if (NullTermIdx == ~((uint64_t)0) && MaxLen > Slice.Length)
           // If the array does not have '\0', leave it to either strlen
-          // or strnlen to compute its length.
+          // or strnlen with an excessive Bound to compute its length.
           return nullptr;
       }
 
       Value *Offset = GEP->getOperand(2);
       KnownBits Known = computeKnownBits(Offset, DL, 0, nullptr, CI, nullptr);
       uint64_t ArrSize =
              cast<ArrayType>(GEP->getSourceElementType())->getNumElements();
 
       // If Offset is not provably in the range [0, NullTermIdx], we can still
       // optimize if we can prove that the program has undefined behavior when
       // Offset is outside that range. That is the case when GEP->getOperand(0)
       // is a pointer to an object whose memory extent is NullTermIdx+1.
       // Similar logic applies to strnlen with a bound less than or equal
       // to the unterminated array size.
       if ((Known.isNonNegative() && Known.getMaxValue().ule(NullTermIdx)) ||
           (GEP->isInBounds() && isa<GlobalVariable>(GEP->getOperand(0)) &&
-           (NullTermIdx == ArrSize - 1) && (!Bound || MaxLen < UINT64_MAX))) {
+           (NullTermIdx == ArrSize - 1 ||
+            (NullTermIdx == UINT64_MAX && MaxLen <= ArrSize)))) {
         uint64_t Max = std::min(NullTermIdx, ArrSize);
         // Fold strnlen(s + x, Bound) -> min(strlen(s) - x, Bound)
         // for both constant and variable Bound.
         return [=]() {
           Value *MaxVal = ConstantInt::get(CI->getType(), Max);
           Value *Sub = B->CreateSub(MaxVal, Offset);
           return Bound ?
             B->CreateBinaryIntrinsic(Intrinsic::umin, Sub, Bound) : Sub;

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

;
   ret i64 %len
 }
 
 
 ; Fold strnlen(a3 + i, 2) to min(3 - i, 2).
 
 define i64 @fold_strnlen_a3_pi_2(i64 %i) {
 ; CHECK-LABEL: @fold_strnlen_a3_pi_2(
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [3 x i8], [3 x i8]* @a3, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull [[PTR]], i64 2)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 3, [[I:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP1]], i64 2)
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 
   %ptr = getelementptr inbounds [3 x i8], [3 x i8]* @a3, i64 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 2)
   ret i64 %len
 }
 
 
 ; Fold strnlen(a3 + i, 3) to min(3 - i, 3).
 
 define i64 @fold_strnlen_a3_pi_3(i64 %i) {
 ; CHECK-LABEL: @fold_strnlen_a3_pi_3(
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [3 x i8], [3 x i8]* @a3, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull [[PTR]], i64 3)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 3, [[I:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP1]], i64 3)
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 
   %ptr = getelementptr inbounds [3 x i8], [3 x i8]* @a3, i64 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 3)
   ret i64 %len
 }
 
 
;
   ret i64 %len
 }
 
 
 ; Fold strnlen(s3 + i, n) to min(strlen(s3) - i, n)
 
 define i64 @fold_strnlen_s3_pi_n(i64 %i, i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_s3_pi_n(
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* nonnull [[PTR]], i64 [[N:%.*]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 3, [[I:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP1]], i64 [[N:%.*]])
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 
   %ptr = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 %n)
   ret i64 %len
 }
 
 

llvm/test/Transforms/InstCombine/strnlen-4.ll

 @s5_3 = constant [10 x i8] c"12345\00abc\00"
 
 
 ; Fold strnlen (C ? s3 + i : s5, %n) to min(C ? 3 : 5, i) if s3 + i is
 ; marked inbounds.
 
 define i64 @fold_strnlen_s3_pi_s5_n(i1 %C, i64 %i, i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_s3_pi_s5_n(
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], i8* [[PTR]], i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0)
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[SEL]], i64 [[N:%.*]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 3, [[I:%.*]]
+; CHECK-NEXT:    [[MINMAXOP:%.*]] = select i1 [[C:%.*]], i64 [[TMP1]], i64 5
+; CHECK-NEXT:    [[TMP2:%.*]] = call i64 @llvm.umin.i64(i64 [[MINMAXOP]], i64 [[N:%.*]])
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 
   %ptr = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %i
   %sel = select i1 %C, i8* %ptr, i8* getelementptr ([6 x i8], [6 x i8]* @s5, i64 0, i64 0)
   %len = call i64 @strnlen(i8* %sel, i64 %n)
   ret i64 %len
 }
 

llvm/test/Transforms/InstCombine/strnlen-5.ll

;
   ret i1 %eqz
 }
 
 
 ; Fold strnlen(s5 + i, n) == 0 to min(5 - i, n) == 0.
 
 define i1 @fold_strnlen_s5_pi_n_eqz(i64 %i, i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_s5_pi_n_eqz(
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* nonnull [[PTR]], i64 [[N:%.*]])
-; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[LEN]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 5, [[I:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP1]], i64 [[N:%.*]])
+; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[TMP2]], 0
 ; CHECK-NEXT:    ret i1 [[EQZ]]
 ;
 
   %ptr = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 %n)
   %eqz = icmp eq i64 %len, 0
   ret i1 %eqz
 }