[InstCombine] Fold strlen and strnlen recursively.

[msebor]

Summary

This patch in the strnlen series introduces a recursive function, LibCallSimplifier::minStringLength(), to handle calls with pointer arguments involving nested conditional expressions. This also enhances the folding of strlen. For strnlen, only constant bounds are handled.

Depends on D123818.

[msebor]

Patch rebased on top of the latest trunk, including all dependencies.

[nikic]

As mentioned on the original review, I think we would be better off not passing the Bound to minStringLength() and instead doing one umin at the end -- this avoids the need to handle this in each branch. Though possibly I forgot some reason why that doesn't work from the previous discussion.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

714

Why is this condition needed?

[nikic]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

635

Can pass in IRBuilderBase by-reference? It seems like part of the changes here are just B. to B->.

[msebor]

In D123819#3487880, @nikic wrote:

As mentioned on the original review, I think we would be better off not passing the Bound to minStringLength() and instead doing one umin at the end -- this avoids the need to handle this in each branch. Though possibly I forgot some reason why that doesn't work from the previous discussion.

You made this suggestion in the context of the select statement where I implemented it (see line 748). Removing the Bound (and MaxLen) from the function completely would prevent handling variable offsets in strlen while punting on them in strnlen as you requested in D122686. It would also prevent ultimately handling it in strnlen as proposed D123820 in cases that the strlen folding cannot handle (arrays with embedded nuls where the bound is less than the length of any of the substrings).

Splitting up the variable offset handling between two patches makes the work harder to think about and, it seems, also harder to review, rather than easier as you'd hoped. Would it help if I merged them into one?

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

635

Passing it by reference means the lambda capture cannot be simply by value. Instead, each lambda must explicitly specify the capture for each variable, making it more verbose, harder to read, etc.

714

To prevent folding strnlen calls with variable offsets as you requested in the previous review. See for example fold_strnlen_s3_pi_n in strnlen-3.ll and others. The folding is enabled in D123820.

[msebor]

...cases that the strlen folding cannot handle (arrays with embedded nuls where the bound is less than the length of any of the substrings).

Whoops, that was a thinko. Those are cases that strnlen cannot safely handle. Those it can handle that strlen can't are unterminated arrays with variable offsets.

[nikic]

In D123819#3488750, @msebor wrote:

In D123819#3487880, @nikic wrote:

As mentioned on the original review, I think we would be better off not passing the Bound to minStringLength() and instead doing one umin at the end -- this avoids the need to handle this in each branch. Though possibly I forgot some reason why that doesn't work from the previous discussion.

You made this suggestion in the context of the select statement where I implemented it (see line 748). Removing the Bound (and MaxLen) from the function completely would prevent handling variable offsets in strlen while punting on them in strnlen as you requested in D122686. It would also prevent ultimately handling it in strnlen as proposed D123820 in cases that the strlen folding cannot handle (arrays with embedded nuls where the bound is less than the length of any of the substrings).

Splitting up the variable offset handling between two patches makes the work harder to think about and, it seems, also harder to review, rather than easier as you'd hoped. Would it help if I merged them into one?

Okay, I think I have made things a bit confusing here: The bit I was originally concerned about is the special handling for the NullTermIdx == ~((uint64_t)0) case -- I don't think the implementation from D123820 really makes sense. I don't think there's a strong need to split off the handling of variable bounds as long as that special case is not included.

Basically, what I would expect is something along these two patches:
https://gist.github.com/nikic/d847d507ee89f9a2ccb07e39c18ea356 - This extends strnlen support to all the cases strlen supports
https://gist.github.com/nikic/dfa8018bc82ab6347887c8c65249f084 - This adds handling for the special "null not contained in string" case

The latter patch doesn't make a distinction between strlen and strnlen: If there is no null in the string, we just return -1, which will result in the bound getting picked as the final result for the strnlen case, which is the only possible non-UB result. The strlen case is always UB, thus returning -1 is fine there as well. Passing the Bound does allow us to distinguish these and avoid optimizing some UB cases -- but it also does cause additional complexity in this case, because it means the Bound is not handled in a single place.

[msebor]

I'm not sure where this stands now. Are you expecting me to submit your patches for review and then incorporate the recursion part separately?

[xbolva00]

Cases like strlen (x ? s1 : s2) should be handled in more general fashion and rewrite fn (x ? s1 : s2) as x ? fn(s1) : fn(s2) if fn(s1) and (or?) fn(s2) can be optimized to just some (constant) value.

Same for more chains like fn (x == 3 ? s3 : x == 5 ? s5 : s7) to x == 3 ? fn(s3) : x == 5 ? fn(s2) : fn(s5).

[msebor]

In D123819#3542702, @xbolva00 wrote:

Cases like strlen (x ? s1 : s2) should be handled in more general fashion

Agreed. Such a general rewrite seems outside the scope of the simple transformations done by the folder (when either s1 or s2 is not constant). Does that mean we don't want the proposed change and should instead wait for the more general transform?

For what it's worth, GCC does this transform in its Partial Redundancy Elimination pass that sits on top of Global Value Numbering. I don't see a PRE pass in LLVM and its GVN pass documents its purpose as "to eliminate fully redundant instructions." So it seems like the transformation we're looking for might be a suitable enhancement for that pass.

[nikic]

In D123819#3542661, @msebor wrote:

I'm not sure where this stands now. Are you expecting me to submit your patches for review and then incorporate the recursion part separately?

Yeah, that's what I'd suggest. Maybe not exactly those patches, but something that's functionally similar.

For the recursion part, there are a few additional issues we'd want to consider: a) reused operands in nested selects, b) potential infinite loops in unreachable code (not sure if SLC can run on unreachable code), c) potentially non-profitable transform for multi-use selects, d) potentially deep recursion without limit. (Some of those have a common solution.)

In D123819#3542702, @xbolva00 wrote:

Cases like strlen (x ? s1 : s2) should be handled in more general fashion and rewrite fn (x ? s1 : s2) as x ? fn(s1) : fn(s2) if fn(s1) and (or?) fn(s2) can be optimized to just some (constant) value.

Same for more chains like fn (x == 3 ? s3 : x == 5 ? s5 : s7) to x == 3 ? fn(s3) : x == 5 ? fn(s2) : fn(s5).

We generally cannot optimize fn(x ? s1 : s2) to x ? fn(s1) : fn(s2), because this would unconditionally execute fn() on both inputs. We can only do this if both sides fold to a speculatable result. Otherwise this is only possible by introducing a branch, which is not possible in SLC (and has unclear profitability).

In D123819#3542796, @msebor wrote:

For what it's worth, GCC does this transform in its Partial Redundancy Elimination pass that sits on top of Global Value Numbering. I don't see a PRE pass in LLVM and its GVN pass documents its purpose as "to eliminate fully redundant instructions." So it seems like the transformation we're looking for might be a suitable enhancement for that pass.

GVN does perform PRE as well. Though I believe it is only performed for phis, not selects (at least for scalar PRE, I think load PRE does handle select). Though to be honest I don't really understand why this particular transform would fall under the purview of PRE.

[msebor]

@nikic, it doesn't make sense to me to submit your work for your review. Please feel free to submit the patches yourself. I'll work on the recursive approach separately.

llvm/include/llvm/Transforms/Utils/SimplifyLibCalls.h

private:
 
   /// hasFloatVersion - Checks if there is a float version of the specified
   /// function by checking for an existing function with name FuncName + f
   bool hasFloatVersion(StringRef FuncName);
 
   /// 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

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

Value *LibCallSimplifier::optimizeStrNCpy(CallInst *CI, IRBuilderBase &B) {
   CallInst *NewCI = B.CreateMemCpy(Dst, Align(1), Src, Align(1),
                                    ConstantInt::get(DL.getIntPtrType(PT), Len));
   NewCI->setAttributes(CI->getAttributes());
   NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(NewCI->getType()));
   copyFlags(*CI, NewCI);
   return Dst;
 }
 
-Value *LibCallSimplifier::optimizeStringLength(CallInst *CI, IRBuilderBase &B,
-                                               unsigned CharSize,
-                                               Value *Bound) {
-  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, "char0"),
-                        CI->getType());
-  }
+LibCallSimplifier::CreateInsnFuncTy
+LibCallSimplifier::minStringLength(CallInst *CI, Value *Src, IRBuilderBase *B,
+                                   unsigned CharSize, uint64_t MaxLen,
+  Type *CharTy = B->getIntNTy(CharSize);
 
   if (Bound) {
     if (ConstantInt *BoundCst = dyn_cast<ConstantInt>(Bound)) {
       if (BoundCst->isZero())
         // Fold strnlen(s, 0) -> 0 for any s, constant or otherwise.
+        return [=]() {
           return ConstantInt::get(CI->getType(), 0);
+        };
 
       if (BoundCst->isOne()) {
         // Fold strnlen(s, 1) -> *s ? 1 : 0 for any s.
-        Value *CharVal = B.CreateLoad(CharTy, Src, "strnlen.char0");
+        return [=]() {
+          Value *CharVal = B->CreateLoad(CharTy, Src, "strnlen.char0");
           Value *ZeroChar = ConstantInt::get(CharTy, 0);
-        Value *Cmp = B.CreateICmpNE(CharVal, ZeroChar, "strnlen.char0cmp");
-        return B.CreateZExt(Cmp, CI->getType());
+          Value *Cmp = B->CreateICmpNE(CharVal, ZeroChar, "strnlen.char0cmp");
+          return B->CreateZExt(Cmp, CI->getType());
+        };
       }
     }
   }
 
   if (uint64_t Len = GetStringLength(Src, CharSize)) {
     Value *LenC = ConstantInt::get(CI->getType(), Len - 1);
     // Fold strlen("xyz") -> 3 and strnlen("xyz", 2) -> 2
     // and strnlen("xyz", Bound) -> min(3, Bound) for nonconstant Bound.
-    if (Bound)
-      return B.CreateBinaryIntrinsic(Intrinsic::umin, LenC, Bound);
-    return LenC;
+    return [=]() {
+      return Bound
+        ? B->CreateBinaryIntrinsic(Intrinsic::umin, LenC, Bound) : LenC;
+    };
   }
 
-  if (Bound)
-    // Punt for strnlen for now.
-    return nullptr;
-
   // 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
   // [0, strlen(s)] or the string has a single null terminator '\0' at the end.
   // We only try to simplify strlen when the pointer s points to an array
   // of i8. Otherwise, we would need to scale the offset x before doing the
   // subtraction. This will make the optimization more complex, and it's not
   // very useful because calling strlen for a pointer of other types is
   // very uncommon.
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 the string does not have '\0', leave it to strlen to compute
-        // its length.
         if (NullTermIdx == ~((uint64_t)0))
+          // If the array does not have '\0', leave it to either strlen
+          // or strnlen 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)) ||
           (isa<GlobalVariable>(GEP->getOperand(0)) &&
-           NullTermIdx == ArrSize - 1)) {
-        Offset = B.CreateSExtOrTrunc(Offset, CI->getType());
-        return B.CreateSub(ConstantInt::get(CI->getType(), NullTermIdx),
-                           Offset);
+           (NullTermIdx == ArrSize - 1) && (!Bound || MaxLen < UINT64_MAX))) {
+        // Fold strnlen(s + x, Bound) -> min(strlen(s) - x, Bound)
+        // for both constant and variable Bound.
+        return [=]() {
+          uint64_t Max = std::min(NullTermIdx, ArrSize);
+          Value *MaxVal = ConstantInt::get(CI->getType(), Max);
+          Value *Sub = B->CreateSub(MaxVal, Offset);
+          return Bound ?
+            B->CreateBinaryIntrinsic(Intrinsic::umin, Sub, Bound) : Sub;
+        };
       }
     }
+    return nullptr;
   }
 
-  // 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));
-    }
-  }
+    // Fold strlen(x?"foo":"bars") --> x ? 3 : 4
+    // and strnlen(x?"foo":"bars", Bound) --> min(x ? 3 : 4, Bound)
+    Value *SrcTrue = SI->getTrueValue();
+    auto MinTrue = minStringLength(CI, SrcTrue, B, CharSize, MaxLen, Bound);
+    if (!MinTrue)
+      return nullptr;
+
+    Value *SrcFalse = SI->getFalseValue();
+    auto MinFalse = minStringLength(CI, SrcFalse, B, CharSize, MaxLen, Bound);
+    if (!MinFalse)
+      return nullptr;
+
+
+    return [=]() {
+      // Since MinTrue and MinFalse have already been constrained to Bound
+      // above, simply return the conditional selection of the two.
+      return B->CreateSelect(SI->getCondition(), MinTrue(), MinFalse());
+    };
+
+  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, "char0"),
+                        CI->getType());
+  }
+
+  if (auto Insns = minStringLength(CI, Src, &B, CharSize, MaxLen, Bound))
+    return Insns();
+
   return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeStrLen(CallInst *CI, IRBuilderBase &B) {
   if (Value *V = optimizeStringLength(CI, B, 8))
     return V;
   annotateNonNullNoUndefBasedOnAccess(CI, 0);
   return nullptr;

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

 
 @s5_3 = constant [10 x i8] c"12345\00123\00"
 
 
 ; Fold strlen (x ? s3 + i : s5) to x ? 3 - i : 5.
 
 define i64 @fold_strlen_s3_pi_s5(i1 %X, i64 %I) {
 ; CHECK-LABEL: @fold_strlen_s3_pi_s5(
-; CHECK-NEXT:    [[PS3_PI:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[X:%.*]], 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:    [[TMP1:%.*]] = sub i64 3, [[I:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[X:%.*]], i64 [[TMP1]], i64 5
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 
   %ps3_pi = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %I
   %ps5 = getelementptr [6 x i8], [6 x i8]* @s5, i64 0, i64 0
   %sel = select i1 %X, i8* %ps3_pi, i8* %ps5
   %len = tail call i64 @strlen(i8* %sel)
   ret i64 %len
 }
;
   ret i64 %len
 }
 
 
 ; But do fold strlen (x ? s5_3 : s5 + j) to x ? 5 : 5 - j.
 
 define i64 @call_strlen_s5_3_s5_pj(i1 %X, i64 %J) {
 ; CHECK-LABEL: @call_strlen_s5_3_s5_pj(
-; CHECK-NEXT:    [[PS5:%.*]] = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 [[J:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[X:%.*]], 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:    [[TMP1:%.*]] = sub i64 5, [[J:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[X:%.*]], i64 5, i64 [[TMP1]]
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 
   %ps5_3_pi = getelementptr [10 x i8], [10 x i8]* @s5_3, i64 0, i64 0
   %ps5 = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 %J
   %sel = select i1 %X, i8* %ps5_3_pi, i8* %ps5
   %len = tail call i64 @strlen(i8* %sel)
   ret i64 %len
 }
 
 
-; Fold strlen (x ? s3: s5 + j) to x ? 3 : 5 - j.
+; Fold strlen (x ? s3 : s5 + j) to x ? 3 : 5 - j.
 
 define i64 @fold_strlen_s3_s5_pj(i1 %X, i64 %J) {
 ; CHECK-LABEL: @fold_strlen_s3_s5_pj(
-; CHECK-NEXT:    [[PS5_PJ:%.*]] = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 [[J:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[X:%.*]], 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:    [[TMP1:%.*]] = sub i64 5, [[J:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[X:%.*]], i64 3, i64 [[TMP1]]
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 
   %ps3 = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 0
   %ps5_pj = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 %J
   %sel = select i1 %X, i8* %ps3, i8* %ps5_pj
   %len = tail call i64 @strlen(i8* %sel)
   ret i64 %len
 }
;
   %ps3 = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 0
   %ps5_3_pj = getelementptr inbounds [10 x i8], [10 x i8]* @s5_3, i64 0, i64 %1
   %sel = select i1 %0, i8* %ps3, i8* %ps5_3_pj
   %len = tail call i64 @strlen(i8* %sel)
   ret i64 %len
 }
 
 
-; Fold strlen (x ? s3 + i: s5 + j) to x ? 3 - i : 5 - j.
+; Fold strlen (x ? s3 + i : s5 + j) to x ? 3 - i : 5 - j.
+; Use CHECK-DAG since the first two instructions below might be emitted
+; in reverse order.
 
 define i64 @fold_strlen_s3_pi_s5_pj(i1 %X, i64 %I, i64 %J) {
 ; CHECK-LABEL: @fold_strlen_s3_pi_s5_pj(
-; CHECK-NEXT:    [[PS3_PI:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[PS5_PJ:%.*]] = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 [[J:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[X:%.*]], i8* [[PS3_PI]], i8* [[PS5_PJ]]
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strlen(i8* noundef nonnull [[SEL]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-DAG:     [[TMP1:%.*]] = sub i64 5, [[J:%.*]]
+; CHECK-DAG:     [[TMP2:%.*]] = sub i64 3, [[I:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[X:%.*]], i64 [[TMP2]], i64 [[TMP1]]
+; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
-; Use CHECK-DAG since the two instructions below might be emitted in reverse
-; order.
 
   %ps3_pi = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %I
   %ps5_pj = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 %J
   %sel = select i1 %X, i8* %ps3_pi, i8* %ps5_pj
   %len = tail call i64 @strlen(i8* %sel)
   ret i64 %len
 }
 
 
 ; Fold strlen(E) with E being two conditional expressions:
 ;   strlen (x == 3 ? s3 : x == 5 ? s5 : s7) to x == 3 ? 3 : x == 5 ? 5 : 7.
 
 define i64 @fold_strlen_s3_s5_s7(i32 %X) {
 ; CHECK-LABEL: @fold_strlen_s3_s5_s7(
-; CHECK-NEXT:    [[X_EQ_3:%.*]] = icmp eq i32 [[X:%.*]], 3
-; CHECK-NEXT:    [[X_EQ_5:%.*]] = icmp eq i32 [[X]], 5
-; CHECK-NEXT:    [[SEL_X_EQ_5:%.*]] = select i1 [[X_EQ_5]], 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:    [[SEL:%.*]] = select i1 [[X_EQ_3]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* [[SEL_X_EQ_5]]
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strlen(i8* noundef nonnull dereferenceable(1) [[SEL]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-DAG:     [[X_EQ_3:%.*]] = icmp eq i32 [[X:%.*]], 3
+; CHECK-DAG:     [[X_EQ_5:%.*]] = icmp eq i32 [[X]], 5
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X_EQ_5]], i64 5, i64 7
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[X_EQ_3]], i64 3, i64 [[TMP1]]
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 
   %x_eq_3 = icmp eq i32 %X, 3
   %x_eq_5 = icmp eq i32 %X, 5
   %sel_x_eq_5 = select i1 %x_eq_5, i8* getelementptr ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr ([8 x i8], [8 x i8]* @s7, i64 0, i64 0)
   %sel = select i1 %x_eq_3, i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* %sel_x_eq_5
   %len = tail call i64 @strlen(i8* %sel)
   ret i64 %len
 }
 
 
 ; Do not fold strlen (x == 3 ? sx : x == 5 ? s5 : s7).
 
 define i64 @call_strlen_sx_s5_s7(i32 %X) {
 ; CHECK-LABEL: @call_strlen_sx_s5_s7(
-; CHECK-NEXT:    [[X_EQ_3:%.*]] = icmp eq i32 [[X:%.*]], 3
-; CHECK-NEXT:    [[X_EQ_5:%.*]] = icmp eq i32 [[X]], 5
+; CHECK-DAG:     [[X_EQ_3:%.*]] = icmp eq i32 [[X:%.*]], 3
+; CHECK-DAG:     [[X_EQ_5:%.*]] = icmp eq i32 [[X]], 5
 ; CHECK-NEXT:    [[SEL_X_EQ_5:%.*]] = select i1 [[X_EQ_5]], 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:    [[SEL:%.*]] = select i1 [[X_EQ_3]], i8* getelementptr inbounds ([0 x i8], [0 x i8]* @sx, i64 0, i64 0), i8* [[SEL_X_EQ_5]]
 ; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strlen(i8* noundef nonnull dereferenceable(1) [[SEL]])
 ; CHECK-NEXT:    ret i64 [[LEN]]
 ;
 
   %x_eq_3 = icmp eq i32 %X, 3
   %x_eq_5 = icmp eq i32 %X, 5
   %sel_x_eq_5 = select i1 %x_eq_5, i8* getelementptr ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr ([8 x i8], [8 x i8]* @s7, i64 0, i64 0)
   %sel = select i1 %x_eq_3, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @sx, i64 0, i64 0), i8* %sel_x_eq_5
   %len = tail call i64 @strlen(i8* %sel)
   ret i64 %len
 }

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; Verify that strnlen calls with conditional expressions involving constant
 ; string arguments and constant bounds are folded correctly.
 ;
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare i64 @strnlen(i8*, i64)
 
 @s3 = constant [4 x i8] c"123\00"
 @s5 = constant [6 x i8] c"12345\00"
 @s5_3 = constant [10 x i8] c"12345\00678\00"
-@s6 = constant [7 x i8] c"123456\00"
 @s7 = constant [8 x i8] c"1234567\00"
 
 
 ; Fold strnlen (C ? s3 : s5, 0) to 0.
 
 define i64 @fold_strnlen_s3_s5_0(i1 %C) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_0(
 ; CHECK-NEXT:    ret i64 0
 ;
-  %ptr = select i1 %C, 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)
 
+  %ps3 = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 0
+  %ps5 = getelementptr [6 x i8], [6 x i8]* @s5, i64 0, i64 0
+  %ptr = select i1 %C, i8* %ps3, i8* %ps5
   %len = call i64 @strnlen(i8* %ptr, i64 0)
   ret i64 %len
 }
 
 
 ; Fold strnlen (C ? s3 : s5, 1) to 1.
 
 define i64 @fold_strnlen_s3_s5_1(i1 %C) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_1(
 ; CHECK-NEXT:    ret i64 1
 ;
-  %ptr = select i1 %C, 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)
 
+  %ps3 = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 0
+  %ps5 = getelementptr [6 x i8], [6 x i8]* @s5, i64 0, i64 0
+  %ptr = select i1 %C, i8* %ps3, i8* %ps5
   %len = call i64 @strnlen(i8* %ptr, i64 1)
   ret i64 %len
 }
 
 
 ; Fold strnlen (C ? s3 : s5, 3) to 3.
 
 define i64 @fold_strnlen_s3_s5_3(i1 %C) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_3(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[C:%.*]], 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* noundef nonnull dereferenceable(1) [[PTR]], i64 3)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 3
 ;
-  %ptr = select i1 %C, 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)
 
+  %ps3 = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 0
+  %ps5 = getelementptr [6 x i8], [6 x i8]* @s5, i64 0, i64 0
+  %ptr = select i1 %C, i8* %ps3, i8* %ps5
   %len = call i64 @strnlen(i8* %ptr, i64 3)
   ret i64 %len
 }
 
 
 ; Fold strnlen (C ? s3 : s5, 4) to C ? 3 : 4.
 
 define i64 @fold_strnlen_s3_s5_4(i1 %C) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_4(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[C:%.*]], 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* noundef nonnull dereferenceable(1) [[PTR]], i64 4)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[C:%.*]], i64 3, i64 4
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
-  %ptr = select i1 %C, 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)
 
+  %ps3 = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 0
+  %ps5 = getelementptr [6 x i8], [6 x i8]* @s5, i64 0, i64 0
+  %ptr = select i1 %C, i8* %ps3, i8* %ps5
   %len = call i64 @strnlen(i8* %ptr, i64 4)
   ret i64 %len
 }
 
 
 ; Fold strnlen (C ? s3 : s5, 5) to C ? 3 : 5.
 
 define i64 @fold_strnlen_s3_s5_5(i1 %C) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_5(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[C:%.*]], 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* noundef nonnull dereferenceable(1) [[PTR]], i64 5)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[C:%.*]], i64 3, i64 5
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
-  %ptr = select i1 %C, 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)
 
+  %ps3 = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 0
+  %ps5 = getelementptr [6 x i8], [6 x i8]* @s5, i64 0, i64 0
+  %ptr = select i1 %C, i8* %ps3, i8* %ps5
   %len = call i64 @strnlen(i8* %ptr, i64 5)
   ret i64 %len
 }
 
 
 ; Fold strnlen (C ? s3 : s5, 6) to C ? 3 : 5.
 
-define i64 @fold_strnlen_s5_6(i1 %C) {
-; CHECK-LABEL: @fold_strnlen_s5_6(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[C:%.*]], 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* noundef nonnull dereferenceable(1) [[PTR]], i64 6)
-; CHECK-NEXT:    ret i64 [[LEN]]
+define i64 @fold_strnlen_s3_s5_6(i1 %C) {
+; CHECK-LABEL: @fold_strnlen_s3_s5_6(
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[C:%.*]], i64 3, i64 5
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
 
-  %ptr = select i1 %C, 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)
-
+  %ps3 = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 0
+  %ps5 = getelementptr [6 x i8], [6 x i8]* @s5, i64 0, i64 0
+  %ptr = select i1 %C, i8* %ps3, i8* %ps5
   %len = call i64 @strnlen(i8* %ptr, i64 6)
   ret i64 %len
 }
 
 
 ; Fold strnlen(E, N) with E being two conditional expressions:
 ;   strlen (x == 3 ? s3 : x == 5 ? s5 : s7, 4) to x == 3 ? 3 : 4.
 
 define i64 @fold_strnlen_s3_s5_s7_4(i32 %X) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_s7_4(
 ; CHECK-NEXT:    [[X_EQ_3:%.*]] = icmp eq i32 [[X:%.*]], 3
-; CHECK-NEXT:    [[X_EQ_5:%.*]] = icmp eq i32 [[X]], 5
-; CHECK-NEXT:    [[SEL_X_EQ_5:%.*]] = select i1 [[X_EQ_5]], 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:    [[SEL_X_EQ_3:%.*]] = select i1 [[X_EQ_3]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* [[SEL_X_EQ_5]]
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* noundef nonnull dereferenceable(1) [[SEL_X_EQ_3]], i64 4)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X_EQ_3]], i64 3, i64 4
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
 
   %x_eq_3 = icmp eq i32 %X, 3
   %x_eq_5 = icmp eq i32 %X, 5
   %sel_x_eq_5 = select i1 %x_eq_5, i8* getelementptr ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr ([8 x i8], [8 x i8]* @s7, i64 0, i64 0)
   %sel_x_eq_3 = select i1 %x_eq_3, i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* %sel_x_eq_5
   %len = tail call i64 @strnlen(i8* %sel_x_eq_3, i64 4)
   ret i64 %len
 }
 
 
 ; As above, fold strnlen(E, N) with E being two conditional expressions
 ; but with N == 6:
 ;   strlen (x == 3 ? s3 : x == 5 ? s5 : s7, 6) to x == 3 ? 3 : x == 5 ? 5 : 6.
 
 define i64 @fold_strnlen_s3_s5_s7_6(i32 %X) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_s7_6(
 ; CHECK-NEXT:    [[X_EQ_3:%.*]] = icmp eq i32 [[X:%.*]], 3
 ; CHECK-NEXT:    [[X_EQ_5:%.*]] = icmp eq i32 [[X]], 5
-; CHECK-NEXT:    [[SEL_X_EQ_5:%.*]] = select i1 [[X_EQ_5]], 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:    [[SEL_X_EQ_3:%.*]] = select i1 [[X_EQ_3]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* [[SEL_X_EQ_5]]
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* noundef nonnull dereferenceable(1) [[SEL_X_EQ_3]], i64 6)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X_EQ_5]], i64 5, i64 6
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[X_EQ_3]], i64 3, i64 [[TMP1]]
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 
   %x_eq_3 = icmp eq i32 %X, 3
   %x_eq_5 = icmp eq i32 %X, 5
   %sel_x_eq_5 = select i1 %x_eq_5, i8* getelementptr ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr ([8 x i8], [8 x i8]* @s7, i64 0, i64 0)
   %sel_x_eq_3 = select i1 %x_eq_3, i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* %sel_x_eq_5
   %len = tail call i64 @strnlen(i8* %sel_x_eq_3, i64 6)
   ret i64 %len
 }
 
 
 ; And again, fold strnlen(E, N) with E being two conditional expressions
 ; but with N == 8:
 ;   strlen (x == 3 ? s3 : x == 5 ? s5 : s7, 8) to x == 3 ? 3 : x == 5 ? 5 : 7.
 
 define i64 @fold_strnlen_s3_s5_s7_8(i32 %X) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_s7_8(
 ; CHECK-NEXT:    [[X_EQ_3:%.*]] = icmp eq i32 [[X:%.*]], 3
 ; CHECK-NEXT:    [[X_EQ_5:%.*]] = icmp eq i32 [[X]], 5
-; CHECK-NEXT:    [[SEL_X_EQ_5:%.*]] = select i1 [[X_EQ_5]], 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:    [[SEL_X_EQ_3:%.*]] = select i1 [[X_EQ_3]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* [[SEL_X_EQ_5]]
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* noundef nonnull dereferenceable(1) [[SEL_X_EQ_3]], i64 8)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X_EQ_5]], i64 5, i64 7
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[X_EQ_3]], i64 3, i64 [[TMP1]]
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
 
   %x_eq_3 = icmp eq i32 %X, 3
   %x_eq_5 = icmp eq i32 %X, 5
   %sel_x_eq_5 = select i1 %x_eq_5, i8* getelementptr ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr ([8 x i8], [8 x i8]* @s7, i64 0, i64 0)
   %sel_x_eq_3 = select i1 %x_eq_3, i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* %sel_x_eq_5
   %len = tail call i64 @strnlen(i8* %sel_x_eq_3, i64 8)
   ret i64 %len
 }

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

;
   %ptr = getelementptr inbounds [0 x i8], [0 x i8]* @sx, i64 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 %n)
   ret i64 %len
 }
 
 
 ; Fold strnlen(a3 + i, 2) to min(3 - i, 2).
 
-define i64 @call_strnlen_a3_pi_2(i64 %i) {
-; CHECK-LABEL: @call_strnlen_a3_pi_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]]
 ;
 
   %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 @call_strnlen_a3_pi_3(i64 %i) {
-; CHECK-LABEL: @call_strnlen_a3_pi_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]]
 ;
 
   %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
;
   %ptr = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 0)
   ret i64 %len
 }
 
 
 ; Fold strnlen(s5 + i, 0) to 0.
 
-define i64 @call_strnlen_s5_pi_0(i64 zeroext %i) {
-; CHECK-LABEL: @call_strnlen_s5_pi_0(
+define i64 @fold_strnlen_s5_pi_0(i64 zeroext %i) {
+; CHECK-LABEL: @fold_strnlen_s5_pi_0(
 ; 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)
   ret i64 %len
 }
 
 

 ;
 
   %ptr = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 0
   %len = call i64 @strnlen(i8* %ptr, i64 %n)
   ret i64 %len
 }
 
 
-; Fold strnlen(a3 + i, 2) to min(sizeof(a3) - 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]]
-;
-
-  %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(s3 + i, 2) to min(strlen(s3) - i, 2)
 
 define i64 @fold_strnlen_s3_pi_2(i64 %i) {
 ; CHECK-LABEL: @fold_strnlen_s3_pi_2(
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, 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 [4 x i8], [4 x i8]* @s3, i64 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 2)
   ret i64 %len
 }
 
 
 ; Fold strnlen(s3 + i, 3) to min(strlen(s3) - i, 3)
 
 define i64 @fold_strnlen_s3_pi_3(i64 %i) {
 ; CHECK-LABEL: @fold_strnlen_s3_pi_3(
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, 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 [4 x i8], [4 x i8]* @s3, i64 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 3)
   ret i64 %len
 }
 
 

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; Verify that strnlen calls with conditional expressions involving constant
 ; string arguments with nonconstant bounds are folded correctly.
 ;
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare i64 @strnlen(i8*, i64)
 
 @sx = external global [0 x i8]
 @s3 = constant [4 x i8] c"123\00"
 @s5 = constant [6 x i8] c"12345\00"
 @s5_3 = constant [10 x i8] c"12345\00abc\00"
 
 
-; Fold strnlen (C ? s3 + i : s5, %n) to min(C ? 3 : 5, i) when
-; s3 + i is guaranteed to be within the bounds of s3.
+; 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]]
 ;
 
   %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
 }
 
 
-; Do not fold the same expression as above when s3 + i is not guaranteed
-; to be within the bounds of s3.  Also verify that the call is not marked
-; noundef, nonnull, or dereferenceable because a zero bound implies no
-; access.
+; Also fold the above with no inbounds.  See also
+; test_simplify10_no_inbounds in strlen-1.ll.
 
-define i64 @call_strnlen_s3_pi_xbounds_s5_n(i1 %C, i64 %i, i64 %n) {
-; CHECK-LABEL: @call_strnlen_s3_pi_xbounds_s5_n(
+define i64 @fold_strnlen_s3_pi_no_inbounds_s5_n(i1 %C, i64 %i, i64 %n) {
+; CHECK-LABEL: @fold_strnlen_s3_pi_no_inbounds_s5_n(
 ; CHECK-NEXT:    [[PTR:%.*]] = getelementptr [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]]
 ;
 
   %ptr = getelementptr [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)
;
   ret i64 %len
 }
 
 
 ; Fold strnlen (C ? s3 : s5 + i, n) to min(C ? 3 : 5, i).
 
 define i64 @fold_strnlen_s3_s5_pi_n(i1 %C, i64 %i, i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_pi_n(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[C:%.*]], 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 [[I:%.*]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[MINMAXOP:%.*]] = select i1 [[C:%.*]], i64 5, i64 3
+; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @llvm.umin.i64(i64 [[MINMAXOP]], i64 [[I:%.*]])
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
 
   %ptr = select i1 %C, 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)
   %len = call i64 @strnlen(i8* %ptr, i64 %i)
   ret i64 %len
 }

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

;
   %len = call i64 @strnlen(i8* %ptr, i64 %nz)
   %eqz = icmp eq i64 %len, 0
   ret i1 %eqz
 }
 
 
 ; Fold strnlen(s5 + i, n) == 0 for a constant s5 and nonzero n.
 ; This is first folded to s5[i] == 0 like the above and then finally
-; to %0 == 5.
+; to i == 5.
 
 define i1 @fold_strnlen_s5_pi_nz_eqz(i64 %i, i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_s5_pi_nz_eqz(
 ; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[I:%.*]], 5
 ; CHECK-NEXT:    ret i1 [[EQZ]]
 ;
 
   %nz = or i64 %n, 1
   %ptr = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 %nz)
   %eqz = icmp eq i64 %len, 0
   ret i1 %eqz
 }
 
 
-; Do not fold strnlen(s5 + i, n) for a constant s5 when n might be zero.
+; Fold strnlen(s5 + i, n) == 0 to min(5 - i, n) == 0.
 
-define i1 @call_strnlen_s5_pi_n_eqz(i64 %i, i64 %n) {
-; CHECK-LABEL: @call_strnlen_s5_pi_n_eqz(
+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:    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
 }