Index: llvm/include/llvm/Transforms/Utils/SimplifyLibCalls.h =================================================================== --- llvm/include/llvm/Transforms/Utils/SimplifyLibCalls.h +++ llvm/include/llvm/Transforms/Utils/SimplifyLibCalls.h @@ -240,7 +240,15 @@ /// 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 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 @@ -631,36 +631,28 @@ 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, + Value *Bound) { + Type *CharTy = B->getIntNTy(CharSize); if (Bound) { if (ConstantInt *BoundCst = dyn_cast(Bound)) { if (BoundCst->isZero()) // Fold strnlen(s, 0) -> 0 for any s, constant or otherwise. - return ConstantInt::get(CI->getType(), 0); + 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"); - Value *ZeroChar = ConstantInt::get(CharTy, 0); - Value *Cmp = B.CreateICmpNE(CharVal, ZeroChar, "strnlen.char0cmp"); - return B.CreateZExt(Cmp, CI->getType()); + 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()); + }; } } } @@ -669,15 +661,12 @@ 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. @@ -703,9 +692,9 @@ 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; } @@ -718,34 +707,86 @@ // 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(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(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; + + ORE.emit([&]() { + return OptimizationRemark("instcombine", "simplify-libcalls", CI) + << "folded strlen(select) to select of constants"; + }); + + 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; 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 %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 @@ -81,10 +80,9 @@ 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 @@ -95,14 +93,13 @@ } -; 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 @@ -133,18 +130,17 @@ } -; 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 @@ -159,12 +155,11 @@ 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 @@ -180,8 +175,8 @@ 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]]) Index: llvm/test/Transforms/InstCombine/strnlen-2.ll =================================================================== --- llvm/test/Transforms/InstCombine/strnlen-2.ll +++ llvm/test/Transforms/InstCombine/strnlen-2.ll @@ -9,7 +9,6 @@ @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" @@ -19,8 +18,10 @@ ; 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 } @@ -32,8 +33,10 @@ ; 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 } @@ -43,12 +46,12 @@ 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 } @@ -58,12 +61,13 @@ 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 } @@ -73,12 +77,13 @@ 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 } @@ -86,15 +91,15 @@ ; 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 } @@ -106,11 +111,8 @@ 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 @@ -130,10 +132,9 @@ ; 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 @@ -153,10 +154,9 @@ ; 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 Index: llvm/test/Transforms/InstCombine/strnlen-3.ll =================================================================== --- llvm/test/Transforms/InstCombine/strnlen-3.ll +++ llvm/test/Transforms/InstCombine/strnlen-3.ll @@ -44,8 +44,8 @@ ; 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]] @@ -59,8 +59,8 @@ ; 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]] @@ -86,8 +86,8 @@ ; 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 @@ -150,28 +150,13 @@ } -; 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 @@ -184,9 +169,9 @@ 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 Index: llvm/test/Transforms/InstCombine/strnlen-4.ll =================================================================== --- llvm/test/Transforms/InstCombine/strnlen-4.ll +++ llvm/test/Transforms/InstCombine/strnlen-4.ll @@ -12,8 +12,8 @@ @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( @@ -30,13 +30,11 @@ } -; 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:%.*]]) @@ -74,9 +72,9 @@ 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) Index: llvm/test/Transforms/InstCombine/strnlen-5.ll =================================================================== --- llvm/test/Transforms/InstCombine/strnlen-5.ll +++ llvm/test/Transforms/InstCombine/strnlen-5.ll @@ -190,7 +190,7 @@ ; 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( @@ -206,10 +206,10 @@ } -; 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