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
@@ -634,6 +634,18 @@
   Value *Src = CI->getArgOperand(0);
   Type *CharTy = B.getIntNTy(CharSize);
 
+  if (isOnlyUsedInZeroEqualityComparison(CI) &&
+      (!Bound || isKnownNonZero(Bound, DL))) {
+    // Fold strlen:
+    //   strlen(x) != 0 --> *x != 0
+    //   strlen(x) == 0 --> *x == 0
+    // and likewise strnlen with constant N > 0:
+    //   strnlen(x, N) != 0 --> *x != 0
+    //   strnlen(x, N) == 0 --> *x == 0
+    return B.CreateZExt(B.CreateLoad(CharTy, Src, "strlenfirst"),
+                        CI->getType());
+  }
+
   if (Bound) {
     if (ConstantInt *BoundCst = dyn_cast<ConstantInt>(Bound)) {
       if (BoundCst->isZero())
@@ -729,12 +741,6 @@
     }
   }
 
-  // strlen(x) != 0 --> *x != 0
-  // strlen(x) == 0 --> *x == 0
-  if (isOnlyUsedInZeroEqualityComparison(CI))
-    return B.CreateZExt(B.CreateLoad(B.getIntNTy(CharSize), Src, "strlenfirst"),
-                        CI->getType());
-
   return nullptr;
 }
 
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
@@ -43,9 +43,9 @@
 
 define i1 @fold_strnlen_ax_1_eqz() {
 ; CHECK-LABEL: @fold_strnlen_ax_1_eqz(
-; CHECK-NEXT:    [[STRNLEN_CHAR0:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
-; CHECK-NEXT:    [[STRNLEN_CHAR0CMP_NOT:%.*]] = icmp ne i8 [[STRNLEN_CHAR0]], 0
-; CHECK-NEXT:    ret i1 [[STRNLEN_CHAR0CMP_NOT]]
+; CHECK-NEXT:    [[STRLENFIRST:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
+; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i8 [[STRLENFIRST]], 0
+; CHECK-NEXT:    ret i1 [[EQZ]]
 ;
 
   %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0
@@ -59,9 +59,9 @@
 
 define i1 @fold_strnlen_ax_1_neqz() {
 ; CHECK-LABEL: @fold_strnlen_ax_1_neqz(
-; CHECK-NEXT:    [[STRNLEN_CHAR0:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
-; CHECK-NEXT:    [[STRNLEN_CHAR0CMP_NOT:%.*]] = icmp eq i8 [[STRNLEN_CHAR0]], 0
-; CHECK-NEXT:    ret i1 [[STRNLEN_CHAR0CMP_NOT]]
+; CHECK-NEXT:    [[STRLENFIRST:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
+; CHECK-NEXT:    [[NEZ:%.*]] = icmp ne i8 [[STRLENFIRST]], 0
+; CHECK-NEXT:    ret i1 [[NEZ]]
 ;
 
   %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0
@@ -75,8 +75,8 @@
 
 define i1 @fold_strnlen_ax_9_eqz() {
 ; CHECK-LABEL: @fold_strnlen_ax_9_eqz(
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i64 9)
-; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[LEN]], 0
+; CHECK-NEXT:    [[STRLENFIRST:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
+; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i8 [[STRLENFIRST]], 0
 ; CHECK-NEXT:    ret i1 [[EQZ]]
 ;
 
@@ -107,9 +107,8 @@
 
 define i1 @fold_strnlen_ax_nz_eqz(i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_ax_nz_eqz(
-; CHECK-NEXT:    [[MAX:%.*]] = or i64 [[N:%.*]], 1
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i64 [[MAX]])
-; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[LEN]], 0
+; CHECK-NEXT:    [[STRLENFIRST:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
+; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i8 [[STRLENFIRST]], 0
 ; CHECK-NEXT:    ret i1 [[EQZ]]
 ;
 
@@ -125,9 +124,8 @@
 
 define i1 @fold_strnlen_ax_nz_gtz(i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_ax_nz_gtz(
-; CHECK-NEXT:    [[MAX:%.*]] = or i64 [[N:%.*]], 1
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i64 [[MAX]])
-; CHECK-NEXT:    [[GTZ:%.*]] = icmp ne i64 [[LEN]], 0
+; CHECK-NEXT:    [[STRLENFIRST:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
+; CHECK-NEXT:    [[GTZ:%.*]] = icmp ne i8 [[STRLENFIRST]], 0
 ; CHECK-NEXT:    ret i1 [[GTZ]]
 ;
 
@@ -144,10 +142,9 @@
 
 define i1 @fold_strnlen_a5_pi_nz_eqz(i64 %i, i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_a5_pi_nz_eqz(
-; CHECK-NEXT:    [[NZ:%.*]] = or i64 [[N:%.*]], 1
 ; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [5 x i8], [5 x i8]* @a5, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull [[PTR]], i64 [[NZ]])
-; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[LEN]], 0
+; CHECK-NEXT:    [[STRLENFIRST:%.*]] = load i8, i8* [[PTR]], align 1
+; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i8 [[STRLENFIRST]], 0
 ; CHECK-NEXT:    ret i1 [[EQZ]]
 ;
 
@@ -165,10 +162,7 @@
 
 define i1 @fold_strnlen_s5_pi_nz_eqz(i64 %i, i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_s5_pi_nz_eqz(
-; CHECK-NEXT:    [[NZ:%.*]] = or i64 [[N:%.*]], 1
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull [[PTR]], i64 [[NZ]])
-; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[LEN]], 0
+; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[I:%.*]], 5
 ; CHECK-NEXT:    ret i1 [[EQZ]]
 ;