diff --git a/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp b/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
--- a/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
@@ -689,9 +689,9 @@
             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;
       }
 
@@ -708,7 +708,8 @@
       // 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.
diff --git a/llvm/test/Transforms/InstCombine/strnlen-3.ll b/llvm/test/Transforms/InstCombine/strnlen-3.ll
--- a/llvm/test/Transforms/InstCombine/strnlen-3.ll
+++ b/llvm/test/Transforms/InstCombine/strnlen-3.ll
@@ -46,9 +46,9 @@
 
 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
@@ -61,9 +61,9 @@
 
 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
@@ -184,9 +184,9 @@
 
 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
diff --git a/llvm/test/Transforms/InstCombine/strnlen-4.ll b/llvm/test/Transforms/InstCombine/strnlen-4.ll
--- a/llvm/test/Transforms/InstCombine/strnlen-4.ll
+++ b/llvm/test/Transforms/InstCombine/strnlen-4.ll
@@ -17,10 +17,10 @@
 
 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
diff --git a/llvm/test/Transforms/InstCombine/strnlen-5.ll b/llvm/test/Transforms/InstCombine/strnlen-5.ll
--- a/llvm/test/Transforms/InstCombine/strnlen-5.ll
+++ b/llvm/test/Transforms/InstCombine/strnlen-5.ll
@@ -178,9 +178,9 @@
 
 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]]
 ;