Index: llvm/include/llvm/Transforms/Utils/SimplifyLibCalls.h
===================================================================
--- llvm/include/llvm/Transforms/Utils/SimplifyLibCalls.h
+++ llvm/include/llvm/Transforms/Utils/SimplifyLibCalls.h
@@ -163,6 +163,7 @@
   Value *optimizeStpCpy(CallInst *CI, IRBuilderBase &B);
   Value *optimizeStrNCpy(CallInst *CI, IRBuilderBase &B);
   Value *optimizeStrLen(CallInst *CI, IRBuilderBase &B);
+  Value *optimizeStrnLen(CallInst *CI, IRBuilderBase &B);
   Value *optimizeStrPBrk(CallInst *CI, IRBuilderBase &B);
   Value *optimizeStrTo(CallInst *CI, IRBuilderBase &B);
   Value *optimizeStrSpn(CallInst *CI, IRBuilderBase &B);
@@ -236,9 +237,18 @@
   /// function by checking for an existing function with name FuncName + f
   bool hasFloatVersion(StringRef FuncName);
 
-  /// Shared code to optimize strlen+wcslen.
-  Value *optimizeStringLength(CallInst *CI, IRBuilderBase &B, unsigned CharSize);
+  /// Shared code to optimize strlen+wcslen and strnlen+wcsnlen.
+  Value *optimizeStringLength(CallInst *CI, IRBuilderBase &B, unsigned CharSize,
+                              Value *Bound = nullptr);
+
+  /// Recursively compute strnlen(Src, Bound), returning the sequence
+  /// of instructions as a function object to evaluate to insert into
+  /// the IR.
+  typedef std::function<Value *()> CreateInsnFuncTy;
+  CreateInsnFuncTy minStringLength(CallInst *CI, Value *Src, IRBuilderBase &B,
+                                   unsigned CharSize, uint64_t MaxLen,
+                                   Value *Bound);
 };
-} // End llvm namespace
+} // namespace llvm
 
 #endif
Index: llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
===================================================================
--- llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
+++ llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
@@ -628,13 +628,18 @@
   return Dst;
 }
 
-Value *LibCallSimplifier::optimizeStringLength(CallInst *CI, IRBuilderBase &B,
-                                               unsigned CharSize) {
-  Value *Src = CI->getArgOperand(0);
-
-  // Constant folding: strlen("xyz") -> 3
-  if (uint64_t Len = GetStringLength(Src, CharSize))
-    return ConstantInt::get(CI->getType(), Len - 1);
+LibCallSimplifier::CreateInsnFuncTy
+LibCallSimplifier::minStringLength(CallInst *CI, Value *Src, IRBuilderBase &B,
+                                   unsigned CharSize, uint64_t MaxLen,
+                                   Value *Bound) {
+  if (uint64_t Len = GetStringLength(Src, CharSize)) {
+    Value *Min = ConstantInt::get(CI->getType(), Len - 1);
+    // Fold strlen("xyz") -> 3 and strnlen("xyz", 2) -> 2
+    // and strnlen("xyz", Bound) -> min(3, Bound)
+    return [&B, Min, Bound]() {
+      return Bound ? B.CreateBinaryIntrinsic(Intrinsic::umin, Min, Bound) : Min;
+    };
+  }
 
   // If s is a constant pointer pointing to a string literal, we can fold
   // strlen(s + x) to strlen(s) - x, when x is known to be in the range
@@ -661,13 +666,17 @@
             break;
           }
         }
-        // If the string does not have '\0', leave it to strlen to compute
-        // its length.
-        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 with an excessive Bound to compute its length.
           return nullptr;
       }
 
       Value *Offset = GEP->getOperand(2);
+      if (!dyn_cast<Constant>(Offset) && Bound)
+	// Avoid handling strnlen with a nonconstant offset for now.
+	return nullptr;
+
       KnownBits Known = computeKnownBits(Offset, DL, 0, nullptr, CI, nullptr);
       Known.Zero.flipAllBits();
       uint64_t ArrSize =
@@ -683,36 +692,94 @@
       // 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.Zero.isNonNegative() && Known.Zero.ule(NullTermIdx)) ||
           (GEP->isInBounds() && isa<GlobalVariable>(GEP->getOperand(0)) &&
-           NullTermIdx == ArrSize - 1)) {
+           (NullTermIdx == ArrSize - 1 ||
+            (NullTermIdx == UINT64_MAX && MaxLen <= ArrSize)))) {
         Offset = B.CreateSExtOrTrunc(Offset, CI->getType());
-        return B.CreateSub(ConstantInt::get(CI->getType(), NullTermIdx),
-                           Offset);
+        uint64_t Max = std::min(NullTermIdx, ArrSize);
+        if (!Bound)
+          return [&B, CI, Max, Offset]() {
+            return B.CreateSub(ConstantInt::get(CI->getType(), Max), Offset);
+          };
+
+        // Fold strnlen(s + x, Bound) -> min(strlen(s) - x, Bound)
+        // for both constant and variable Bound.
+        return [&B, CI, Max, Offset, Bound]() {
+          Value *Res =
+              B.CreateSub(ConstantInt::get(CI->getType(), Max), Offset);
+          return B.CreateBinaryIntrinsic(Intrinsic::umin, Res, Bound);
+        };
       }
     }
   }
 
-  // strlen(x?"foo":"bars") --> x ? 3 : 4
   if (SelectInst *SI = dyn_cast<SelectInst>(Src)) {
-    uint64_t LenTrue = GetStringLength(SI->getTrueValue(), CharSize);
-    uint64_t LenFalse = GetStringLength(SI->getFalseValue(), CharSize);
-    if (LenTrue && LenFalse) {
-      ORE.emit([&]() {
-        return OptimizationRemark("instcombine", "simplify-libcalls", CI)
-               << "folded strlen(select) to select of constants";
-      });
-      return B.CreateSelect(SI->getCondition(),
-                            ConstantInt::get(CI->getType(), LenTrue - 1),
-                            ConstantInt::get(CI->getType(), LenFalse - 1));
-    }
+    Value *SrcTrue = SI->getTrueValue();
+    Value *SrcFalse = SI->getFalseValue();
+
+    auto MinTrue = minStringLength(CI, SrcTrue, B, CharSize, MaxLen, Bound);
+    if (!MinTrue)
+      return nullptr;
+
+    auto MinFalse = minStringLength(CI, SrcFalse, B, CharSize, MaxLen, Bound);
+    if (!MinFalse)
+      return nullptr;
+
+    ORE.emit([&]() {
+      return OptimizationRemark("instcombine", "simplify-libcalls", CI)
+             << "folded strlen(select) to select of constants";
+    });
+
+    if (!Bound)
+      // Fold strlen(x?"foo":"bars") --> x ? 3 : 4
+      return [&B, SI, MinTrue, MinFalse]() {
+        return B.CreateSelect(SI->getCondition(), MinTrue(), MinFalse());
+      };
+
+    // Fold strnlen(x?"foo":"bars", Bound) --> min(x ? 3 : 4, Bound)
+    return [&B, SI, MinTrue, MinFalse, Bound]() {
+      // Since MinTrue and MinFalse are already constrained to Bound there
+      // is no need to do that again here.
+      return B.CreateSelect(SI->getCondition(), MinTrue(), MinFalse());
+    };
   }
 
-  // strlen(x) != 0 --> *x != 0
-  // strlen(x) == 0 --> *x == 0
-  if (isOnlyUsedInZeroEqualityComparison(CI))
+  return nullptr;
+}
+
+Value *LibCallSimplifier::optimizeStringLength(CallInst *CI, IRBuilderBase &B,
+                                               unsigned CharSize,
+                                               Value *Bound) {
+  // For strnlen, set to the constant bound.  Otherwise, for strlen
+  // or strnlen with nonconstant bound, set to the maximum.
+  uint64_t MaxLen;
+  if (!Bound || !match(Bound, m_ConstantInt(MaxLen)))
+    MaxLen = UINT64_MAX;
+
+  if (MaxLen == 0)
+    // Fold strnlen(s, 0) -> 0 for any s, constant or otherwise.
+    return ConstantInt::get(CI->getType(), 0);
+
+  Value *Src = CI->getArgOperand(0);
+  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(B.getIntNTy(CharSize), Src, "strlenfirst"),
                         CI->getType());
+  }
+
+  if (auto Insns = minStringLength(CI, Src, B, CharSize, MaxLen, Bound))
+    // Invoke the returned lambdas to create and insert the simplified
+    // instructions or constants into the IR and return the result.
+    return Insns();
 
   return nullptr;
 }
@@ -724,6 +791,16 @@
   return nullptr;
 }
 
+Value *LibCallSimplifier::optimizeStrnLen(CallInst *CI, IRBuilderBase &B) {
+  Value *Bound = CI->getArgOperand(1);
+  if (Value *V = optimizeStringLength(CI, B, 8, Bound))
+    return V;
+
+  if (isKnownNonZero(Bound, DL))
+    annotateNonNullNoUndefBasedOnAccess(CI, 0);
+  return nullptr;
+}
+
 Value *LibCallSimplifier::optimizeWcslen(CallInst *CI, IRBuilderBase &B) {
   Module &M = *CI->getModule();
   unsigned WCharSize = TLI->getWCharSize(M) * 8;
@@ -2866,6 +2943,8 @@
       return optimizeStrNCpy(CI, Builder);
     case LibFunc_strlen:
       return optimizeStrLen(CI, Builder);
+    case LibFunc_strnlen:
+      return optimizeStrnLen(CI, Builder);
     case LibFunc_strpbrk:
       return optimizeStrPBrk(CI, Builder);
     case LibFunc_strndup:
Index: llvm/test/Transforms/InstCombine/strlen-4.ll
===================================================================
--- llvm/test/Transforms/InstCombine/strlen-4.ll
+++ llvm/test/Transforms/InstCombine/strlen-4.ll
@@ -18,10 +18,9 @@
 
 define i64 @fold_strlen_s3_pi_s5(i1 %0, i64 %1) {
 ; CHECK-LABEL: @fold_strlen_s3_pi_s5(
-; CHECK-NEXT:    [[PS3_PI:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 [[TMP1:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[TMP0:%.*]], i8* [[PS3_PI]], i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0)
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strlen(i8* noundef nonnull dereferenceable(1) [[SEL]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 3, [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP0:%.*]], i64 [[TMP3]], i64 5
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
 
   %ps3_pi = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %1
@@ -81,10 +80,9 @@
 
 define i64 @call_strlen_s5_3_s5_pj(i1 %0, i64 %1) {
 ; CHECK-LABEL: @call_strlen_s5_3_s5_pj(
-; CHECK-NEXT:    [[PS5:%.*]] = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 [[TMP1:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[TMP0:%.*]], i8* getelementptr inbounds ([10 x i8], [10 x i8]* @s5_3, i64 0, i64 0), i8* [[PS5]]
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strlen(i8* noundef nonnull dereferenceable(1) [[SEL]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 5, [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP0:%.*]], i64 5, i64 [[TMP3]]
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
 
   %ps5_3_pi = getelementptr [10 x i8], [10 x i8]* @s5_3, i64 0, i64 0
@@ -99,10 +97,9 @@
 
 define i64 @fold_strlen_s3_s5_pj(i1 %0, i64 %1) {
 ; CHECK-LABEL: @fold_strlen_s3_s5_pj(
-; CHECK-NEXT:    [[PS5_PJ:%.*]] = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 [[TMP1:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[TMP0:%.*]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* [[PS5_PJ]]
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strlen(i8* noundef nonnull dereferenceable(1) [[SEL]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 5, [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP0:%.*]], i64 3, i64 [[TMP3]]
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
 
   %ps3 = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 0
@@ -137,11 +134,12 @@
 
 define i64 @fold_strlen_s3_pi_s5_pj(i1 %0, i64 %1, i64 %2) {
 ; CHECK-LABEL: @fold_strlen_s3_pi_s5_pj(
-; CHECK-NEXT:    [[PS3_PI:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 [[TMP1:%.*]]
-; CHECK-NEXT:    [[PS5_PJ:%.*]] = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 [[TMP2:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[TMP0:%.*]], i8* [[PS3_PI]], i8* [[PS5_PJ]]
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strlen(i8* noundef nonnull [[SEL]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; Use CHECK-DAG since the two instructions below might be emitted in reverse
+; order.
+; CHECK-DAG:     [[TMP4:%.*]] = sub i64 5, [[TMP2:%.*]]
+; CHECK-DAG:     [[TMP5:%.*]] = sub i64 3, [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP6:%.*]] = select i1 [[TMP0:%.*]], i64 [[TMPX:%.*]], i64 [[TMPY:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP6]]
 ;
 
   %ps3_pi = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %1
@@ -159,10 +157,9 @@
 ; CHECK-LABEL: @fold_strlen_s3_s5_s7(
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP0:%.*]], 3
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP0]], 5
-; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr inbounds ([8 x i8], [8 x i8]* @s7, i64 0, i64 0)
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* [[TMP4]]
-; CHECK-NEXT:    [[TMP6:%.*]] = tail call i64 @strlen(i8* noundef nonnull dereferenceable(1) [[TMP5]])
-; CHECK-NEXT:    ret i64 [[TMP6]]
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i64 5, i64 7
+; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP2]], i64 3, i64 [[TMP4]]
+; CHECK-NEXT:    ret i64 [[TMP5]]
 ;
 
   %2 = icmp eq i32 %0, 3
Index: llvm/test/Transforms/InstCombine/strnlen-1.ll
===================================================================
--- llvm/test/Transforms/InstCombine/strnlen-1.ll
+++ llvm/test/Transforms/InstCombine/strnlen-1.ll
@@ -14,8 +14,7 @@
 
 define i64 @fold_strnlen_s5_0() {
 ; CHECK-LABEL: @fold_strnlen_s5_0(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i64 0)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
   %ptr = getelementptr [6 x i8], [6 x i8]* @s5, i32 0, i32 0
   %len = call i64 @strnlen(i8* %ptr, i64 0)
@@ -27,8 +26,7 @@
 
 define i64 @fold_strnlen_s5_4() {
 ; CHECK-LABEL: @fold_strnlen_s5_4(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i64 4)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 4
 ;
   %ptr = getelementptr [6 x i8], [6 x i8]* @s5, i32 0, i32 0
   %len = call i64 @strnlen(i8* %ptr, i64 4)
@@ -40,8 +38,7 @@
 
 define i64 @fold_strnlen_s5_5() {
 ; CHECK-LABEL: @fold_strnlen_s5_5(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i64 5)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 5
 ;
   %ptr = getelementptr [6 x i8], [6 x i8]* @s5, i32 0, i32 0
   %len = call i64 @strnlen(i8* %ptr, i64 5)
@@ -53,8 +50,7 @@
 
 define i64 @fold_strnlen_s5_m1() {
 ; CHECK-LABEL: @fold_strnlen_s5_m1(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i64 -1)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 5
 ;
   %ptr = getelementptr [6 x i8], [6 x i8]* @s5, i32 0, i32 0
   %len = call i64 @strnlen(i8* %ptr, i64 -1)
@@ -66,8 +62,7 @@
 
 define i64 @fold_strnlen_s5_3_p4_5() {
 ; CHECK-LABEL: @fold_strnlen_s5_3_p4_5(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([9 x i8], [9 x i8]* @s5_3, i64 0, i64 4), i64 5)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 1
 ;
   %ptr = getelementptr [9 x i8], [9 x i8]* @s5_3, i32 0, i32 4
   %len = call i64 @strnlen(i8* %ptr, i64 5)
@@ -79,8 +74,7 @@
 
 define i64 @fold_strnlen_s5_3_p5_5() {
 ; CHECK-LABEL: @fold_strnlen_s5_3_p5_5(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([9 x i8], [9 x i8]* @s5_3, i64 0, i64 5), i64 5)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
   %ptr = getelementptr [9 x i8], [9 x i8]* @s5_3, i32 0, i32 5
   %len = call i64 @strnlen(i8* %ptr, i64 5)
@@ -92,8 +86,7 @@
 
 define i64 @fold_strnlen_s5_3_p6_5() {
 ; CHECK-LABEL: @fold_strnlen_s5_3_p6_5(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([9 x i8], [9 x i8]* @s5_3, i64 0, i64 6), i64 5)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 3
 ;
   %ptr = getelementptr [9 x i8], [9 x i8]* @s5_3, i32 0, i32 6
   %len = call i64 @strnlen(i8* %ptr, i64 5)
Index: llvm/test/Transforms/InstCombine/strnlen-2.ll
===================================================================
--- llvm/test/Transforms/InstCombine/strnlen-2.ll
+++ llvm/test/Transforms/InstCombine/strnlen-2.ll
@@ -17,9 +17,7 @@
 
 define i64 @fold_strnlen_s3_s5_0(i1 %0) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_0(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[TMP0:%.*]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr inbounds ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 0)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
   %ptr = select i1 %0, i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
 
@@ -32,9 +30,7 @@
 
 define i64 @fold_strnlen_s3_s5_1(i1 %0) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_1(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[TMP0:%.*]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr inbounds ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 1)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 1
 ;
   %ptr = select i1 %0, i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
 
@@ -47,9 +43,7 @@
 
 define i64 @fold_strnlen_s3_s5_3(i1 %0) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_3(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[TMP0:%.*]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr inbounds ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 3)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 3
 ;
   %ptr = select i1 %0, i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
 
@@ -62,9 +56,8 @@
 
 define i64 @fold_strnlen_s3_s5_4(i1 %0) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_4(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[TMP0:%.*]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr inbounds ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 4)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP0:%.*]], i64 3, i64 4
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
   %ptr = select i1 %0, i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
 
@@ -77,9 +70,8 @@
 
 define i64 @fold_strnlen_s3_s5_5(i1 %0) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_5(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[TMP0:%.*]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr inbounds ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 5)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP0:%.*]], i64 3, i64 5
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
   %ptr = select i1 %0, i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
 
@@ -92,9 +84,8 @@
 
 define i64 @fold_strnlen_s5_6(i1 %0) {
 ; CHECK-LABEL: @fold_strnlen_s5_6(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[TMP0:%.*]], i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr inbounds ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 6)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP0:%.*]], i64 5, i64 6
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 
   %ptr = select i1 %0, i8* getelementptr ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
@@ -110,11 +101,8 @@
 define i64 @fold_strnlen_s3_s5_s7_4(i32 %0) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_s7_4(
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP0:%.*]], 3
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP0]], 5
-; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr inbounds ([8 x i8], [8 x i8]* @s7, i64 0, i64 0)
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* [[TMP4]]
-; CHECK-NEXT:    [[TMP6:%.*]] = tail call i64 @strnlen(i8* [[TMP5]], i64 4)
-; CHECK-NEXT:    ret i64 [[TMP6]]
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i64 3, i64 4
+; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
 
   %2 = icmp eq i32 %0, 3
@@ -134,10 +122,9 @@
 ; CHECK-LABEL: @fold_strnlen_s3_s5_s7_6(
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP0:%.*]], 3
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP0]], 5
-; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr inbounds ([8 x i8], [8 x i8]* @s7, i64 0, i64 0)
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* [[TMP4]]
-; CHECK-NEXT:    [[TMP6:%.*]] = tail call i64 @strnlen(i8* [[TMP5]], i64 6)
-; CHECK-NEXT:    ret i64 [[TMP6]]
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i64 5, i64 6
+; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP2]], i64 3, i64 [[TMP4]]
+; CHECK-NEXT:    ret i64 [[TMP5]]
 ;
 
   %2 = icmp eq i32 %0, 3
@@ -157,10 +144,9 @@
 ; CHECK-LABEL: @fold_strnlen_s3_s5_s7_8(
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP0:%.*]], 3
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP0]], 5
-; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr inbounds ([8 x i8], [8 x i8]* @s7, i64 0, i64 0)
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP2]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* [[TMP4]]
-; CHECK-NEXT:    [[TMP6:%.*]] = tail call i64 @strnlen(i8* [[TMP5]], i64 8)
-; CHECK-NEXT:    ret i64 [[TMP6]]
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i64 5, i64 7
+; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP2]], i64 3, i64 [[TMP4]]
+; CHECK-NEXT:    ret i64 [[TMP5]]
 ;
 
   %2 = icmp eq i32 %0, 3
Index: llvm/test/Transforms/InstCombine/strnlen-3.ll
===================================================================
--- llvm/test/Transforms/InstCombine/strnlen-3.ll
+++ llvm/test/Transforms/InstCombine/strnlen-3.ll
@@ -18,9 +18,7 @@
 
 define i64 @fold_strnlen_sx_pi_0(i64 %0) {
 ; CHECK-LABEL: @fold_strnlen_sx_pi_0(
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr [0 x i8], [0 x i8]* @sx, i64 0, i64 [[TMP0:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 0)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
 
   %ptr = getelementptr [0 x i8], [0 x i8]* @sx, i64 0, i64 %0
@@ -49,7 +47,7 @@
 define i64 @call_strnlen_a3_pi_2(i64 %0) {
 ; CHECK-LABEL: @call_strnlen_a3_pi_2(
 ; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [3 x i8], [3 x i8]* @a3, i64 0, i64 [[TMP0:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* nonnull [[PTR]], i64 2)
+; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull [[PTR]], i64 2)
 ; CHECK-NEXT:    ret i64 [[LEN]]
 ;
 
@@ -64,7 +62,7 @@
 define i64 @call_strnlen_a3_pi_3(i64 %0) {
 ; CHECK-LABEL: @call_strnlen_a3_pi_3(
 ; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [3 x i8], [3 x i8]* @a3, i64 0, i64 [[TMP0:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* nonnull [[PTR]], i64 3)
+; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull [[PTR]], i64 3)
 ; CHECK-NEXT:    ret i64 [[LEN]]
 ;
 
@@ -78,9 +76,7 @@
 
 define i64 @fold_strnlen_s3_pi_0(i64 %0) {
 ; CHECK-LABEL: @fold_strnlen_s3_pi_0(
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 [[TMP0:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* nonnull [[PTR]], i64 0)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
   %ptr = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %0
   %len = call i64 @strnlen(i8* %ptr, i64 0)
@@ -92,8 +88,7 @@
 
 define i64 @call_strnlen_s5_pi_0(i64 zeroext %0) {
 ; CHECK-LABEL: @call_strnlen_s5_pi_0(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i64 0)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
   %ptr = getelementptr [6 x i8], [6 x i8]* @s5, i32 0, i32 0
   %len = call i64 @strnlen(i8* %ptr, i64 0)
@@ -105,9 +100,7 @@
 
 define i64 @fold_strnlen_s5_3_pi_0(i64 zeroext %0) {
 ; CHECK-LABEL: @fold_strnlen_s5_3_pi_0(
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr [10 x i8], [10 x i8]* @s5_3, i64 0, i64 [[TMP0:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 0)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
   %ptr = getelementptr [10 x i8], [10 x i8]* @s5_3, i32 0, i64 %0
   %len = call i64 @strnlen(i8* %ptr, i64 0)
@@ -133,8 +126,8 @@
 
 define i64 @fold_strnlen_a3_n(i64 %0) {
 ; CHECK-LABEL: @fold_strnlen_a3_n(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @a3, i64 0, i64 0), i64 [[TMP0:%.*]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP0:%.*]], i64 3)
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 
   %ptr = getelementptr [3 x i8], [3 x i8]* @a3, i64 0, i64 0
@@ -147,8 +140,8 @@
 
 define i64 @fold_strnlen_s3_n(i64 %0) {
 ; CHECK-LABEL: @fold_strnlen_s3_n(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i64 [[TMP0:%.*]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP0:%.*]], i64 3)
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 
   %ptr = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 0
@@ -162,7 +155,7 @@
 define i64 @fold_strnlen_a3_pi_2(i64 %0) {
 ; CHECK-LABEL: @fold_strnlen_a3_pi_2(
 ; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [3 x i8], [3 x i8]* @a3, i64 0, i64 [[TMP0:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* nonnull [[PTR]], i64 2)
+; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull [[PTR]], i64 2)
 ; CHECK-NEXT:    ret i64 [[LEN]]
 ;
 
@@ -177,7 +170,7 @@
 define i64 @fold_strnlen_s3_pi_2(i64 %0) {
 ; CHECK-LABEL: @fold_strnlen_s3_pi_2(
 ; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 [[TMP0:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* nonnull [[PTR]], i64 2)
+; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull [[PTR]], i64 2)
 ; CHECK-NEXT:    ret i64 [[LEN]]
 ;
 
@@ -192,7 +185,7 @@
 define i64 @fold_strnlen_s3_pi_3(i64 %0) {
 ; CHECK-LABEL: @fold_strnlen_s3_pi_3(
 ; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 [[TMP0:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* nonnull [[PTR]], i64 3)
+; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull [[PTR]], i64 3)
 ; CHECK-NEXT:    ret i64 [[LEN]]
 ;
 
@@ -223,7 +216,7 @@
 define i64 @call_strnlen_s5_3_pi_2(i64 %0) {
 ; CHECK-LABEL: @call_strnlen_s5_3_pi_2(
 ; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [10 x i8], [10 x i8]* @s5_3, i64 0, i64 [[TMP0:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* nonnull [[PTR]], i64 2)
+; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull [[PTR]], i64 2)
 ; CHECK-NEXT:    ret i64 [[LEN]]
 ;
 
Index: llvm/test/Transforms/InstCombine/strnlen-4.ll
===================================================================
--- llvm/test/Transforms/InstCombine/strnlen-4.ll
+++ llvm/test/Transforms/InstCombine/strnlen-4.ll
@@ -74,9 +74,9 @@
 
 define i64 @fold_strnlen_s3_s5_pi_n(i1 %0, i64 %1, i64 %2) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_pi_n(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[TMP0:%.*]], i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0)
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 [[TMP1:%.*]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[MINMAXOP:%.*]] = select i1 [[TMP0:%.*]], i64 5, i64 3
+; CHECK-NEXT:    [[TMP4:%.*]] = call i64 @llvm.umin.i64(i64 [[MINMAXOP]], i64 [[TMP1:%.*]])
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
 
   %ptr = select i1 %0, i8* getelementptr ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0)
Index: llvm/test/Transforms/InstCombine/strnlen-5.ll
===================================================================
--- llvm/test/Transforms/InstCombine/strnlen-5.ll
+++ llvm/test/Transforms/InstCombine/strnlen-5.ll
@@ -15,9 +15,7 @@
 
 define i1 @fold_strnlen_ax_0_eqz() {
 ; CHECK-LABEL: @fold_strnlen_ax_0_eqz(
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i64 0)
-; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[LEN]], 0
-; CHECK-NEXT:    ret i1 [[EQZ]]
+; CHECK-NEXT:    ret i1 true
 ;
 
   %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0
@@ -31,9 +29,7 @@
 
 define i1 @fold_strnlen_ax_0_gtz() {
 ; CHECK-LABEL: @fold_strnlen_ax_0_gtz(
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i64 0)
-; CHECK-NEXT:    [[GTZ:%.*]] = icmp ne i64 [[LEN]], 0
-; CHECK-NEXT:    ret i1 [[GTZ]]
+; CHECK-NEXT:    ret i1 false
 ;
 
   %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0
@@ -47,8 +43,8 @@
 
 define i1 @fold_strnlen_ax_1_eqz() {
 ; CHECK-LABEL: @fold_strnlen_ax_1_eqz(
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i64 1)
-; 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]]
 ;
 
@@ -63,8 +59,8 @@
 
 define i1 @fold_strnlen_ax_1_neqz() {
 ; CHECK-LABEL: @fold_strnlen_ax_1_neqz(
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i64 1)
-; CHECK-NEXT:    [[NEZ:%.*]] = 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:    [[NEZ:%.*]] = icmp ne i8 [[STRLENFIRST]], 0
 ; CHECK-NEXT:    ret i1 [[NEZ]]
 ;
 
@@ -79,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* 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]]
 ;
 
@@ -111,9 +107,8 @@
 
 define i1 @fold_strnlen_ax_nz_eqz(i64 %0) {
 ; CHECK-LABEL: @fold_strnlen_ax_nz_eqz(
-; CHECK-NEXT:    [[MAX:%.*]] = or i64 [[TMP0:%.*]], 1
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* 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]]
 ;
 
@@ -129,9 +124,8 @@
 
 define i1 @fold_strnlen_ax_nz_gtz(i64 %0) {
 ; CHECK-LABEL: @fold_strnlen_ax_nz_gtz(
-; CHECK-NEXT:    [[MAX:%.*]] = or i64 [[TMP0:%.*]], 1
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* 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]]
 ;
 
@@ -148,10 +142,9 @@
 
 define i1 @fold_strnlen_a5_pi_nz_eqz(i64 %0, i64 %1) {
 ; CHECK-LABEL: @fold_strnlen_a5_pi_nz_eqz(
-; CHECK-NEXT:    [[NZ:%.*]] = or i64 [[TMP1:%.*]], 1
 ; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [5 x i8], [5 x i8]* @a5, i64 0, i64 [[TMP0:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* 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]]
 ;
 
@@ -169,11 +162,8 @@
 
 define i1 @fold_strnlen_s5_pi_nz_eqz(i64 %0, i64 %1) {
 ; CHECK-LABEL: @fold_strnlen_s5_pi_nz_eqz(
-; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[TMP1:%.*]], 1
-; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 [[TMP0:%.*]]
-; CHECK-NEXT:    [[TMP5:%.*]] = call i64 @strnlen(i8* nonnull [[TMP4]], i64 [[TMP3]])
-; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i64 [[TMP5]], 0
-; CHECK-NEXT:    ret i1 [[TMP6]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i64 [[TMP0:%.*]], 5
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
 
   %3 = or i64 %1, 1
@@ -184,7 +174,7 @@
 }
 
 
-; Do not fold strnlen(s5 + %0, %1) for a constant s5 when %1 might be zero.
+; TODO: Fold strnlen(s5 + %0, %1) == 0 to min(5 - %0, %1).
 
 define i1 @call_strnlen_s5_pi_n_eqz(i64 %0, i64 %1) {
 ; CHECK-LABEL: @call_strnlen_s5_pi_n_eqz(
Index: llvm/test/Transforms/InstCombine/strnlen-6.ll
===================================================================
--- llvm/test/Transforms/InstCombine/strnlen-6.ll
+++ llvm/test/Transforms/InstCombine/strnlen-6.ll
@@ -16,7 +16,7 @@
 define i64 @deref_strnlen_ecp_3() {
 ; CHECK-LABEL: @deref_strnlen_ecp_3(
 ; CHECK-NEXT:    [[PTR:%.*]] = load i8*, i8** @ecp, align 8
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 3)
+; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull dereferenceable(1) [[PTR]], i64 3)
 ; CHECK-NEXT:    ret i64 [[LEN]]
 ;
   %ptr = load i8*, i8** @ecp
@@ -32,7 +32,7 @@
 ; CHECK-LABEL: @deref_strnlen_ecp_nz(
 ; CHECK-NEXT:    [[NONZERO:%.*]] = or i64 [[N:%.*]], 1
 ; CHECK-NEXT:    [[PTR:%.*]] = load i8*, i8** @ecp, align 8
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 [[NONZERO]])
+; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull dereferenceable(1) [[PTR]], i64 [[NONZERO]])
 ; CHECK-NEXT:    ret i64 [[LEN]]
 ;
   %nonzero = or i64 %n, 1
Index: llvm/test/Transforms/InstCombine/wcslen-5.ll
===================================================================
--- llvm/test/Transforms/InstCombine/wcslen-5.ll
+++ llvm/test/Transforms/InstCombine/wcslen-5.ll
@@ -19,10 +19,9 @@
 
 define dso_local i64 @fold_wcslen_s3_pi_s5(i1 zeroext %0, i64 %1) {
 ; CHECK-LABEL: @fold_wcslen_s3_pi_s5(
-; CHECK-NEXT:    [[PS3_PI:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @ws3, i64 0, i64 [[TMP1:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[TMP0:%.*]], i32* [[PS3_PI]], i32* getelementptr inbounds ([6 x i32], [6 x i32]* @ws5, i64 0, i64 0)
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @wcslen(i32* [[SEL]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 3, [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP0:%.*]], i64 [[TMP3]], i64 5
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
 
   %ps3_pi = getelementptr inbounds [4 x i32], [4 x i32]* @ws3, i64 0, i64 %1
@@ -82,10 +81,9 @@
 
 define dso_local i64 @call_wcslen_s5_3_s5_pj(i1 zeroext %0, i64 %1) {
 ; CHECK-LABEL: @call_wcslen_s5_3_s5_pj(
-; CHECK-NEXT:    [[PS5:%.*]] = getelementptr inbounds [6 x i32], [6 x i32]* @ws5, i64 0, i64 [[TMP1:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[TMP0:%.*]], i32* getelementptr inbounds ([10 x i32], [10 x i32]* @ws5_3, i64 0, i64 0), i32* [[PS5]]
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @wcslen(i32* [[SEL]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 5, [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP0:%.*]], i64 5, i64 [[TMP3]]
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
 
   %ps5_3_pi = getelementptr inbounds [10 x i32], [10 x i32]* @ws5_3, i64 0, i64 0
@@ -100,10 +98,9 @@
 
 define dso_local i64 @fold_wcslen_s3_s5_pj(i1 zeroext %0, i64 %1) {
 ; CHECK-LABEL: @fold_wcslen_s3_s5_pj(
-; CHECK-NEXT:    [[PS5_PJ:%.*]] = getelementptr inbounds [6 x i32], [6 x i32]* @ws5, i64 0, i64 [[TMP1:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[TMP0:%.*]], i32* getelementptr inbounds ([4 x i32], [4 x i32]* @ws3, i64 0, i64 0), i32* [[PS5_PJ]]
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @wcslen(i32* [[SEL]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 5, [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP0:%.*]], i64 3, i64 [[TMP3]]
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
 
   %ps3 = getelementptr inbounds [4 x i32], [4 x i32]* @ws3, i64 0, i64 0
@@ -138,11 +135,12 @@
 
 define dso_local i64 @fold_wcslen_s3_pi_s5_pj(i1 zeroext %0, i64 %1, i64 %2) {
 ; CHECK-LABEL: @fold_wcslen_s3_pi_s5_pj(
-; CHECK-NEXT:    [[PS3_PI:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @ws3, i64 0, i64 [[TMP1:%.*]]
-; CHECK-NEXT:    [[PS5_PJ:%.*]] = getelementptr inbounds [6 x i32], [6 x i32]* @ws5, i64 0, i64 [[TMP2:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[TMP0:%.*]], i32* [[PS3_PI]], i32* [[PS5_PJ]]
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @wcslen(i32* nonnull [[SEL]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; Use CHECK-DAG since the two instructions below might be emitted in reverse
+; order.
+; CHECK-DAG:     [[TMP4:%.*]] = sub i64 3, [[TMP2:%.*]]
+; CHECK-DAG:     [[TMP5:%.*]] = sub i64 5, [[TMP1:%.*]]
+; CHECK:         [[TMP6:%.*]] = select i1 [[TMP0:%.*]], i64 [[TMPX:%.*]], i64 [[TMPY:%.*]]
+; CHECK:         ret i64 [[TMP6]]
 ;
 
   %ps3_pi = getelementptr inbounds [4 x i32], [4 x i32]* @ws3, i64 0, i64 %1