diff --git a/llvm/include/llvm/Transforms/Utils/SimplifyLibCalls.h b/llvm/include/llvm/Transforms/Utils/SimplifyLibCalls.h --- a/llvm/include/llvm/Transforms/Utils/SimplifyLibCalls.h +++ b/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 CreateInsnFuncTy; + CreateInsnFuncTy minStringLength(CallInst *CI, Value *Src, IRBuilderBase &B, + unsigned CharSize, uint64_t MaxLen, + Value *Bound); }; -} // End llvm namespace +} // namespace llvm #endif diff --git a/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp b/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp --- a/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp @@ -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,9 +666,9 @@ 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; } @@ -683,36 +688,98 @@ // 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(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); + }; + + if (isOnlyUsedInZeroEqualityComparison(CI)) + // Fail if the result is used to test for [in]equality to zero + // and let the caller simplify that better. + return nullptr; + + // 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(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]() { + Value *Res = B.CreateSelect(SI->getCondition(), MinTrue(), MinFalse()); + return B.CreateBinaryIntrinsic(Intrinsic::umin, Res, Bound); + }; } - // 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: diff --git a/llvm/test/Transforms/InstCombine/strlen-4.ll b/llvm/test/Transforms/InstCombine/strlen-4.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/strlen-4.ll @@ -0,0 +1,190 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; Verify that strlen calls with conditional expressions involving constant +; string arguments with nonconstant offsets are folded as expected. +; +; RUN: opt < %s -passes=instcombine -S | FileCheck %s + +declare i64 @strlen(i8* nocapture) + +@sx = external global [0 x i8] +@s3 = constant [4 x i8] c"123\00", align 1 +@s5 = constant [6 x i8] c"12345\00", align 1 +@s7 = constant [8 x i8] c"1234567\00", align 1 + +@s5_3 = constant [10 x i8] c"12345\00123\00", align 1 + + +; Fold strlen (x ? s3 + i: s5) to x ? 3 - i : 5. + +define i64 @fold_strlen_s3_pi_s5(i1 %0, i64 %1) { +; CHECK-LABEL: @fold_strlen_s3_pi_s5( +; 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 + %ps5 = getelementptr [6 x i8], [6 x i8]* @s5, i64 0, i64 0 + %sel = select i1 %0, i8* %ps3_pi, i8* %ps5 + %len = tail call i64 @strlen(i8* %sel) + ret i64 %len +} + + +; More complex expressions like the one below are not handled yet. +; Fold: strlen (x ? s3 + i + 1 : s5 + j + 2) to x ? 2 - i : 3 - j. + +define i64 @fold_strlen_s3_pi_p1_s5(i1 %0, i64 %1) { +; XFAIL-CHECK-LABEL: @fold_strlen_s3_pi_p1_s5( +; XFAIL-CHECK-NEXT: [[DIF_I:%.*]] = sub i64 2, %1 +; XFAIL-CHECK-NEXT: [[SEL:%.*]] = select i1 %0, i64 [[DIF_I]], i64 5 +; XFAIL-CHECK-NEXT: ret i64 [[SEL]] +; CHECK-LABEL: @fold_strlen_s3_pi_p1_s5( +; CHECK-NEXT: [[PS3_PI:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 [[TMP1:%.*]] +; CHECK-NEXT: [[PS3_PI_P1:%.*]] = getelementptr i8, i8* [[PS3_PI]], i64 1 +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[TMP0:%.*]], i8* [[PS3_PI_P1]], 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]] +; + + %ps3_pi = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %1 + %ps3_pi_p1 = getelementptr i8, i8* %ps3_pi, i64 1 + %ps5 = getelementptr [6 x i8], [6 x i8]* @s5, i64 0, i64 0 + %sel = select i1 %0, i8* %ps3_pi_p1, i8* %ps5 + %len = tail call i64 @strlen(i8* %sel) + ret i64 %len +} + + +; Avoid folding calls with conditional expressions involving constant +; string arguments with embedded nuls such as: +; strlen (x ? s5_3 + i : s5). + +define i64 @call_strlen_s5_3_pi_s5(i1 %0, i64 %1) { +; CHECK-LABEL: @call_strlen_s5_3_pi_s5( +; CHECK-NEXT: [[PS5_3_PI:%.*]] = getelementptr inbounds [10 x i8], [10 x i8]* @s5_3, i64 0, i64 [[TMP1:%.*]] +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[TMP0:%.*]], i8* [[PS5_3_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]] +; + + %ps5_3_pi = getelementptr inbounds [10 x i8], [10 x i8]* @s5_3, i64 0, i64 %1 + %ps5 = getelementptr [6 x i8], [6 x i8]* @s5, i64 0, i64 0 + %sel = select i1 %0, i8* %ps5_3_pi, i8* %ps5 + %len = tail call i64 @strlen(i8* %sel) + 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 %0, i64 %1) { +; CHECK-LABEL: @call_strlen_s5_3_s5_pj( +; 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 + %ps5 = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 %1 + %sel = select i1 %0, 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. + +define i64 @fold_strlen_s3_s5_pj(i1 %0, i64 %1) { +; CHECK-LABEL: @fold_strlen_s3_s5_pj( +; 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 + %ps5_pj = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 %1 + %sel = select i1 %0, i8* %ps3, i8* %ps5_pj + %len = tail call i64 @strlen(i8* %sel) + ret i64 %len +} + + +; Same as above, avoid folding calls with conditional expressions involving +; constant string arguments with embedded nuls such as: +; strlen (x ? s3 : s5_3 + j). + +define i64 @call_strlen_s3_s5_3_pj(i1 %0, i64 %1) { +; CHECK-LABEL: @call_strlen_s3_s5_3_pj( +; CHECK-NEXT: [[PS5_3_PJ:%.*]] = getelementptr inbounds [10 x i8], [10 x i8]* @s5_3, 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_3_PJ]] +; CHECK-NEXT: [[LEN:%.*]] = tail call i64 @strlen(i8* noundef nonnull dereferenceable(1) [[SEL]]) +; CHECK-NEXT: 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. + +define i64 @fold_strlen_s3_pi_s5_pj(i1 %0, i64 %1, i64 %2) { +; CHECK-LABEL: @fold_strlen_s3_pi_s5_pj( +; CHECK-NEXT: [[TMP4:%.*]] = sub i64 5, [[TMP2:%.*]] +; CHECK-NEXT: [[TMP5:%.*]] = sub i64 3, [[TMP1:%.*]] +; CHECK-NEXT: [[TMP6:%.*]] = select i1 [[TMP0:%.*]], i64 [[TMP5]], i64 [[TMP4]] +; CHECK-NEXT: ret i64 [[TMP6]] +; + + %ps3_pi = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %1 + %ps5_pj = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 %2 + %sel = select i1 %0, 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 %0) { +; 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]], 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 + %3 = icmp eq i32 %0, 5 + %4 = select i1 %3, 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) + %5 = select i1 %2, i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* %4 + %6 = tail call i64 @strlen(i8* %5) + ret i64 %6 +} + + +; Do not fold strlen (x == 3 ? sx : x == 5 ? s5 : s7). + +define i64 @call_strlen_sx_s5_s7(i32 %0) { +; CHECK-LABEL: @call_strlen_sx_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 ([0 x i8], [0 x i8]* @sx, i64 0, i64 0), i8* [[TMP4]] +; CHECK-NEXT: [[TMP6:%.*]] = tail call i64 @strlen(i8* noundef nonnull dereferenceable(1) [[TMP5]]) +; CHECK-NEXT: ret i64 [[TMP6]] +; + + %2 = icmp eq i32 %0, 3 + %3 = icmp eq i32 %0, 5 + %4 = select i1 %3, 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) + %5 = select i1 %2, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @sx, i64 0, i64 0), i8* %4 + %6 = tail call i64 @strlen(i8* %5) + ret i64 %6 +} diff --git a/llvm/test/Transforms/InstCombine/strnlen-1.ll b/llvm/test/Transforms/InstCombine/strnlen-1.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/strnlen-1.ll @@ -0,0 +1,94 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; Verify that strnlen calls with constant string arguments and offsets +; and constant bounds are folded correctly. +; +; RUN: opt < %s -passes=instcombine -S | FileCheck %s + +declare i64 @strnlen(i8*, i64) + +@s5 = constant [6 x i8] c"12345\00" +@s5_3 = constant [9 x i8] c"12345\00xyz" + + +; Fold strnlen(s5, 0) to 0. + +define i64 @fold_strnlen_s5_0() { +; CHECK-LABEL: @fold_strnlen_s5_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 +} + + +; Fold strnlen(s5, 4) to 4. + +define i64 @fold_strnlen_s5_4() { +; CHECK-LABEL: @fold_strnlen_s5_4( +; 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) + ret i64 %len +} + + +; Fold strnlen(s5, 5) to 5. + +define i64 @fold_strnlen_s5_5() { +; CHECK-LABEL: @fold_strnlen_s5_5( +; 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) + ret i64 %len +} + + +; Fold strnlen(s5, (size_t)-1) to 5. + +define i64 @fold_strnlen_s5_m1() { +; CHECK-LABEL: @fold_strnlen_s5_m1( +; 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) + ret i64 %len +} + + +; Fold strnlen(s5_3 + 4, 5) to 1. + +define i64 @fold_strnlen_s5_3_p4_5() { +; CHECK-LABEL: @fold_strnlen_s5_3_p4_5( +; 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) + ret i64 %len +} + + +; Fold strnlen(s5_3 + 5, 5) to 1. + +define i64 @fold_strnlen_s5_3_p5_5() { +; CHECK-LABEL: @fold_strnlen_s5_3_p5_5( +; 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) + ret i64 %len +} + + +; Fold strnlen(s5_3 + 6, 5) to 3. + +define i64 @fold_strnlen_s5_3_p6_5() { +; CHECK-LABEL: @fold_strnlen_s5_3_p6_5( +; 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) + ret i64 %len +} diff --git a/llvm/test/Transforms/InstCombine/strnlen-2.ll b/llvm/test/Transforms/InstCombine/strnlen-2.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/strnlen-2.ll @@ -0,0 +1,158 @@ +; 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 (%0 ? s3 : s5, 0) to 0. + +define i64 @fold_strnlen_s3_s5_0(i1 %0) { +; CHECK-LABEL: @fold_strnlen_s3_s5_0( +; 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) + + %len = call i64 @strnlen(i8* %ptr, i64 0) + ret i64 %len +} + + +; Fold strnlen (%0 ? s3 : s5, 1) to 1. + +define i64 @fold_strnlen_s3_s5_1(i1 %0) { +; CHECK-LABEL: @fold_strnlen_s3_s5_1( +; 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) + + %len = call i64 @strnlen(i8* %ptr, i64 1) + ret i64 %len +} + + +; Fold strnlen (%0 ? s3 : s5, 3) to 3. + +define i64 @fold_strnlen_s3_s5_3(i1 %0) { +; CHECK-LABEL: @fold_strnlen_s3_s5_3( +; 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) + + %len = call i64 @strnlen(i8* %ptr, i64 3) + ret i64 %len +} + + +; Fold strnlen (%0 ? s3 : s5, 4) to %0 ? 3 : 4. + +define i64 @fold_strnlen_s3_s5_4(i1 %0) { +; CHECK-LABEL: @fold_strnlen_s3_s5_4( +; 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) + + %len = call i64 @strnlen(i8* %ptr, i64 4) + ret i64 %len +} + + +; Fold strnlen (%0 ? s3 : s5, 5) to %0 ? 3 : 5. + +define i64 @fold_strnlen_s3_s5_5(i1 %0) { +; CHECK-LABEL: @fold_strnlen_s3_s5_5( +; 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) + + %len = call i64 @strnlen(i8* %ptr, i64 5) + ret i64 %len +} + + +; Fold strnlen (%0 ? s3 : s5, 6) to %0 ? 3 : 5. + +define i64 @fold_strnlen_s5_6(i1 %0) { +; CHECK-LABEL: @fold_strnlen_s5_6( +; 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) + + %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 %0) { +; CHECK-LABEL: @fold_strnlen_s3_s5_s7_4( +; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP0:%.*]], 3 +; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[TMP2]], i64 3, i64 4 +; CHECK-NEXT: ret i64 [[TMP3]] +; + + %2 = icmp eq i32 %0, 3 + %3 = icmp eq i32 %0, 5 + %4 = select i1 %3, 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) + %5 = select i1 %2, i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* %4 + %6 = tail call i64 @strnlen(i8* %5, i64 4) + ret i64 %6 +} + + +; 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 %0) { +; 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]], 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 + %3 = icmp eq i32 %0, 5 + %4 = select i1 %3, 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) + %5 = select i1 %2, i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* %4 + %6 = tail call i64 @strnlen(i8* %5, i64 6) + ret i64 %6 +} + + +; 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 %0) { +; 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]], 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 + %3 = icmp eq i32 %0, 5 + %4 = select i1 %3, 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) + %5 = select i1 %2, i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* %4 + %6 = tail call i64 @strnlen(i8* %5, i64 8) + ret i64 %6 +} diff --git a/llvm/test/Transforms/InstCombine/strnlen-3.ll b/llvm/test/Transforms/InstCombine/strnlen-3.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/strnlen-3.ll @@ -0,0 +1,226 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; Verify that strnlen calls with conditional expressions involving constant +; string arguments with nonconstant offsets and constant bounds or constant +; offsets and nonconstant bounds are folded correctly. +; +; RUN: opt < %s -passes=instcombine -S | FileCheck %s + +declare i64 @strnlen(i8*, i64) + +@sx = external global [0 x i8] +@a3 = constant [3 x i8] c"123" +@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(sx + %0, 0) to 0. + +define i64 @fold_strnlen_sx_pi_0(i64 %0) { +; CHECK-LABEL: @fold_strnlen_sx_pi_0( +; CHECK-NEXT: ret i64 0 +; + + %ptr = getelementptr [0 x i8], [0 x i8]* @sx, i64 0, i64 %0 + %len = call i64 @strnlen(i8* %ptr, i64 0) + ret i64 %len +} + + +; Do not fold strnlen(sx + %0, %1). + +define i64 @call_strnlen_sx_pi_n(i64 %0, i64 %1) { +; CHECK-LABEL: @call_strnlen_sx_pi_n( +; CHECK-NEXT: [[PTR:%.*]] = getelementptr inbounds [0 x i8], [0 x i8]* @sx, i64 0, i64 [[TMP0:%.*]] +; CHECK-NEXT: [[LEN:%.*]] = call i64 @strnlen(i8* nonnull [[PTR]], i64 [[TMP1:%.*]]) +; CHECK-NEXT: ret i64 [[LEN]] +; + + %ptr = getelementptr inbounds [0 x i8], [0 x i8]* @sx, i64 0, i64 %0 + %len = call i64 @strnlen(i8* %ptr, i64 %1) + ret i64 %len +} + + +; Fold strnlen(a3 + %0, 2) to min(3 - %0, 2). + +define i64 @call_strnlen_a3_pi_2(i64 %0) { +; CHECK-LABEL: @call_strnlen_a3_pi_2( +; CHECK-NEXT: [[TMP2:%.*]] = sub i64 3, [[TMP0:%.*]] +; CHECK-NEXT: [[TMP3:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP2]], i64 2) +; CHECK-NEXT: ret i64 [[TMP3]] +; + + %ptr = getelementptr inbounds [3 x i8], [3 x i8]* @a3, i64 0, i64 %0 + %len = call i64 @strnlen(i8* %ptr, i64 2) + ret i64 %len +} + + +; Fold strnlen(a3 + %0, 3) to min(3 - %0, 3). + +define i64 @call_strnlen_a3_pi_3(i64 %0) { +; CHECK-LABEL: @call_strnlen_a3_pi_3( +; CHECK-NEXT: [[TMP2:%.*]] = sub i64 3, [[TMP0:%.*]] +; CHECK-NEXT: [[TMP3:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP2]], i64 3) +; CHECK-NEXT: ret i64 [[TMP3]] +; + + %ptr = getelementptr inbounds [3 x i8], [3 x i8]* @a3, i64 0, i64 %0 + %len = call i64 @strnlen(i8* %ptr, i64 3) + ret i64 %len +} + + +; Fold strnlen(s3 + %0, 0) to 0. + +define i64 @fold_strnlen_s3_pi_0(i64 %0) { +; CHECK-LABEL: @fold_strnlen_s3_pi_0( +; 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) + ret i64 %len +} + + +; Fold strnlen(s5 + %0, 0) to 0. + +define i64 @call_strnlen_s5_pi_0(i64 zeroext %0) { +; CHECK-LABEL: @call_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 +} + + +; Fold strnlen(s5_3 + %0, 0) to 0. + +define i64 @fold_strnlen_s5_3_pi_0(i64 zeroext %0) { +; CHECK-LABEL: @fold_strnlen_s5_3_pi_0( +; 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) + ret i64 %len +} + + +; Do not fold strnlen(s5_3 + %0, %1). + +define i64 @fold_strnlen_s5_3_pi_n(i64 zeroext %0, i64 %1) { +; CHECK-LABEL: @fold_strnlen_s5_3_pi_n( +; 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 [[TMP1:%.*]]) +; CHECK-NEXT: ret i64 [[LEN]] +; + %ptr = getelementptr inbounds [10 x i8], [10 x i8]* @s5_3, i32 0, i64 %0 + %len = call i64 @strnlen(i8* %ptr, i64 %1) + ret i64 %len +} + + +; Fold strnlen(a3, %0) to min(sizeof(a3), %0) + +define i64 @fold_strnlen_a3_n(i64 %0) { +; CHECK-LABEL: @fold_strnlen_a3_n( +; 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 + %len = call i64 @strnlen(i8* %ptr, i64 %0) + ret i64 %len +} + + +; Fold strnlen(s3, %0) to min(strlen(s3), %0) + +define i64 @fold_strnlen_s3_n(i64 %0) { +; CHECK-LABEL: @fold_strnlen_s3_n( +; 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 + %len = call i64 @strnlen(i8* %ptr, i64 %0) + ret i64 %len +} + + +; Fold strnlen(a3 + %0, 2) to min(sizeof(a3) - %0, 2) + +define i64 @fold_strnlen_a3_pi_2(i64 %0) { +; CHECK-LABEL: @fold_strnlen_a3_pi_2( +; CHECK-NEXT: [[TMP2:%.*]] = sub i64 3, [[TMP0:%.*]] +; CHECK-NEXT: [[TMP3:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP2]], i64 2) +; CHECK-NEXT: ret i64 [[TMP3]] +; + + %ptr = getelementptr inbounds [3 x i8], [3 x i8]* @a3, i64 0, i64 %0 + %len = call i64 @strnlen(i8* %ptr, i64 2) + ret i64 %len +} + + +; Fold strnlen(s3 + %0, 2) to min(strlen(s3) - %0, 2) + +define i64 @fold_strnlen_s3_pi_2(i64 %0) { +; CHECK-LABEL: @fold_strnlen_s3_pi_2( +; CHECK-NEXT: [[TMP2:%.*]] = sub i64 3, [[TMP0:%.*]] +; CHECK-NEXT: [[TMP3:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP2]], i64 2) +; CHECK-NEXT: ret i64 [[TMP3]] +; + + %ptr = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %0 + %len = call i64 @strnlen(i8* %ptr, i64 2) + ret i64 %len +} + + +; Fold strnlen(s3 + %0, 3) to min(strlen(s3) - %0, 3) + +define i64 @fold_strnlen_s3_pi_3(i64 %0) { +; CHECK-LABEL: @fold_strnlen_s3_pi_3( +; CHECK-NEXT: [[TMP2:%.*]] = sub i64 3, [[TMP0:%.*]] +; CHECK-NEXT: [[TMP3:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP2]], i64 3) +; CHECK-NEXT: ret i64 [[TMP3]] +; + + %ptr = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %0 + %len = call i64 @strnlen(i8* %ptr, i64 3) + ret i64 %len +} + + +; Fold strnlen(s3 + %0, %1) to min(strlen(s3) - %0, %1) + +define i64 @fold_strnlen_s3_pi_n(i64 %0, i64 %1) { +; CHECK-LABEL: @fold_strnlen_s3_pi_n( +; CHECK-NEXT: [[TMP3:%.*]] = sub i64 3, [[TMP0:%.*]] +; CHECK-NEXT: [[TMP4:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP3]], i64 [[TMP1:%.*]]) +; CHECK-NEXT: ret i64 [[TMP4]] +; + + %ptr = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %0 + %len = call i64 @strnlen(i8* %ptr, i64 %1) + ret i64 %len +} + + +; Do not fold strnlen(s5_3 + %0, 2). The result is in [0, 2] but there's +; no simple way to derive its lower bound from the offset. + +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* noundef nonnull [[PTR]], i64 2) +; CHECK-NEXT: ret i64 [[LEN]] +; + + %ptr = getelementptr inbounds [10 x i8], [10 x i8]* @s5_3, i64 0, i64 %0 + %len = call i64 @strnlen(i8* %ptr, i64 2) + ret i64 %len +} diff --git a/llvm/test/Transforms/InstCombine/strnlen-4.ll b/llvm/test/Transforms/InstCombine/strnlen-4.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/strnlen-4.ll @@ -0,0 +1,85 @@ +; 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 (%0 ? s3 + %1 : s5, %2) to min(%0 ? 3 : 5, %1) when +; s3 + %1 is guaranteed to be within the bounds of s3. + +define i64 @fold_strnlen_s3_pi_s5_n(i1 %0, i64 %1, i64 %2) { +; CHECK-LABEL: @fold_strnlen_s3_pi_s5_n( +; CHECK-NEXT: [[TMP4:%.*]] = sub i64 3, [[TMP1:%.*]] +; CHECK-NEXT: [[MINMAXOP:%.*]] = select i1 [[TMP0:%.*]], i64 [[TMP4]], i64 5 +; CHECK-NEXT: [[TMP5:%.*]] = call i64 @llvm.umin.i64(i64 [[MINMAXOP]], i64 [[TMP2:%.*]]) +; CHECK-NEXT: ret i64 [[TMP5]] +; + + %ptr = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %1 + %sel = select i1 %0, i8* %ptr, i8* getelementptr ([6 x i8], [6 x i8]* @s5, i64 0, i64 0) + %len = call i64 @strnlen(i8* %sel, i64 %2) + 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. + +define i64 @call_strnlen_s3_pi_xbounds_s5_n(i1 %0, i64 %1, i64 %2) { +; CHECK-LABEL: @call_strnlen_s3_pi_xbounds_s5_n( +; CHECK-NEXT: [[PTR:%.*]] = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 [[TMP1:%.*]] +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[TMP0:%.*]], 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 [[TMP2:%.*]]) +; CHECK-NEXT: ret i64 [[LEN]] +; + + %ptr = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 %1 + %sel = select i1 %0, i8* %ptr, i8* getelementptr ([6 x i8], [6 x i8]* @s5, i64 0, i64 0) + %len = call i64 @strnlen(i8* %sel, i64 %2) + ret i64 %len +} + + +; Do not fold strnlen(%0 ? s3 + %1 : sx, %1) when sx's length and size +; are unknown. This also verifies that the folder cleans up the IR after +; successfully folding the first subexpression IR when folding the second +; subexpression fails. + +define i64 @call_strnlen_s3_pi_sx_n(i1 %0, i64 %1, i64 %2) { +; CHECK-LABEL: @call_strnlen_s3_pi_sx_n( +; CHECK-NEXT: [[PTR:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 [[TMP1:%.*]] +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[TMP0:%.*]], i8* [[PTR]], i8* getelementptr inbounds ([0 x i8], [0 x i8]* @sx, i64 0, i64 0) +; CHECK-NEXT: [[LEN:%.*]] = call i64 @strnlen(i8* [[SEL]], i64 [[TMP2:%.*]]) +; CHECK-NEXT: ret i64 [[LEN]] +; + + %ptr = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %1 + %sel = select i1 %0, i8* %ptr, i8* getelementptr ([0 x i8], [0 x i8]* @sx, i64 0, i64 0) + %len = call i64 @strnlen(i8* %sel, i64 %2) + ret i64 %len +} + + +; Fold strnlen (%0 ? s3 : s5 + %1, %2) to min(%0 ? 3 : 5, %1). + +define i64 @fold_strnlen_s3_s5_pi_n(i1 %0, i64 %1, i64 %2) { +; CHECK-LABEL: @fold_strnlen_s3_s5_pi_n( +; 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) + %len = call i64 @strnlen(i8* %ptr, i64 %1) + ret i64 %len +} diff --git a/llvm/test/Transforms/InstCombine/strnlen-5.ll b/llvm/test/Transforms/InstCombine/strnlen-5.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/strnlen-5.ll @@ -0,0 +1,191 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; Verify that equality tests of strnlen calls against zero are folded +; correctly. +; +; RUN: opt < %s -passes=instcombine -S | FileCheck %s + +declare i64 @strnlen(i8*, i64) + +@ax = external global [0 x i8] +@a5 = external global [5 x i8] +@s5 = constant [6 x i8] c"12345\00" + + +; Fold strnlen(ax, 0) == 0 to true. + +define i1 @fold_strnlen_ax_0_eqz() { +; CHECK-LABEL: @fold_strnlen_ax_0_eqz( +; CHECK-NEXT: ret i1 true +; + + %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0 + %len = tail call i64 @strnlen(i8* %ptr, i64 0) + %eqz = icmp eq i64 %len, 0 + ret i1 %eqz +} + + +; Fold strnlen(ax, 0) > 0 to false. + +define i1 @fold_strnlen_ax_0_gtz() { +; CHECK-LABEL: @fold_strnlen_ax_0_gtz( +; CHECK-NEXT: ret i1 false +; + + %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0 + %len = tail call i64 @strnlen(i8* %ptr, i64 0) + %gtz = icmp ugt i64 %len, 0 + ret i1 %gtz +} + + +; Fold strnlen(ax, 1) == 0 to *ax == 0. + +define i1 @fold_strnlen_ax_1_eqz() { +; CHECK-LABEL: @fold_strnlen_ax_1_eqz( +; CHECK-NEXT: [[STRLENFIRST:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1 +; CHECK-NEXT: [[EQZ:%.*]] = icmp eq i8 [[STRLENFIRST]], 0 +; CHECK-NEXT: ret i1 [[EQZ]] +; + + %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0 + %len = tail call i64 @strnlen(i8* %ptr, i64 1) + %eqz = icmp eq i64 %len, 0 + ret i1 %eqz +} + + +; Fold strnlen(ax, 1) != 0 to *ax != 0. + +define i1 @fold_strnlen_ax_1_neqz() { +; CHECK-LABEL: @fold_strnlen_ax_1_neqz( +; CHECK-NEXT: [[STRLENFIRST:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1 +; CHECK-NEXT: [[NEZ:%.*]] = icmp ne i8 [[STRLENFIRST]], 0 +; CHECK-NEXT: ret i1 [[NEZ]] +; + + %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0 + %len = tail call i64 @strnlen(i8* %ptr, i64 1) + %nez = icmp ne i64 %len, 0 + ret i1 %nez +} + + +; Fold strnlen(ax, 9) == 0 to *ax == 0. + +define i1 @fold_strnlen_ax_9_eqz() { +; CHECK-LABEL: @fold_strnlen_ax_9_eqz( +; CHECK-NEXT: [[STRLENFIRST:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1 +; CHECK-NEXT: [[EQZ:%.*]] = icmp eq i8 [[STRLENFIRST]], 0 +; CHECK-NEXT: ret i1 [[EQZ]] +; + + %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0 + %len = tail call i64 @strnlen(i8* %ptr, i64 9) + %eqz = icmp eq i64 %len, 0 + ret i1 %eqz +} + + +; Do not fold strnlen(ax, %0) == 0 for %0 that might be zero. + +define i1 @call_strnlen_ax_n_eqz(i64 %0) { +; CHECK-LABEL: @call_strnlen_ax_n_eqz( +; CHECK-NEXT: [[LEN:%.*]] = tail call i64 @strnlen(i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i64 [[TMP0:%.*]]) +; CHECK-NEXT: [[EQZ:%.*]] = icmp eq i64 [[LEN]], 0 +; CHECK-NEXT: ret i1 [[EQZ]] +; + + %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0 + %len = tail call i64 @strnlen(i8* %ptr, i64 %0) + %eqz = icmp eq i64 %len, 0 + ret i1 %eqz +} + + +; Fold strnlen(ax, %0) == 0 to *ax == 0 for %0 that's not zero. + +define i1 @fold_strnlen_ax_nz_eqz(i64 %0) { +; CHECK-LABEL: @fold_strnlen_ax_nz_eqz( +; 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]] +; + + %max = or i64 %0, 1 + %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0 + %len = tail call i64 @strnlen(i8* %ptr, i64 %max) + %eqz = icmp eq i64 %len, 0 + ret i1 %eqz +} + + +; Fold strnlen(ax, %0) > 0 to *ax != 0 for %0 that's not zero. + +define i1 @fold_strnlen_ax_nz_gtz(i64 %0) { +; CHECK-LABEL: @fold_strnlen_ax_nz_gtz( +; 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]] +; + + %max = or i64 %0, 1 + %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0 + %len = tail call i64 @strnlen(i8* %ptr, i64 %max) + %gtz = icmp ugt i64 %len, 0 + ret i1 %gtz +} + + +; Fold strnlen(a5 + %0, %1) == 0 to a5[%0] == 0 for a nonconstant a5 +; and a nonzero %1. + +define i1 @fold_strnlen_a5_pi_nz_eqz(i64 %0, i64 %1) { +; CHECK-LABEL: @fold_strnlen_a5_pi_nz_eqz( +; CHECK-NEXT: [[PTR:%.*]] = getelementptr inbounds [5 x i8], [5 x i8]* @a5, i64 0, i64 [[TMP0:%.*]] +; CHECK-NEXT: [[STRLENFIRST:%.*]] = load i8, i8* [[PTR]], align 1 +; CHECK-NEXT: [[EQZ:%.*]] = icmp eq i8 [[STRLENFIRST]], 0 +; CHECK-NEXT: ret i1 [[EQZ]] +; + + %nz = or i64 %1, 1 + %ptr = getelementptr inbounds [5 x i8], [5 x i8]* @a5, i64 0, i64 %0 + %len = call i64 @strnlen(i8* nonnull %ptr, i64 %nz) + %eqz = icmp eq i64 %len, 0 + ret i1 %eqz +} + + +; Fold strnlen(s5 + %0, %1) == 0 for a constant s5 and nonzero %1. +; This is first folded to s5[%0] == 0 like the above and then finally +; to %0 == 5. + +define i1 @fold_strnlen_s5_pi_nz_eqz(i64 %0, i64 %1) { +; CHECK-LABEL: @fold_strnlen_s5_pi_nz_eqz( +; CHECK-NEXT: [[TMP3:%.*]] = icmp eq i64 [[TMP0:%.*]], 5 +; CHECK-NEXT: ret i1 [[TMP3]] +; + + %3 = or i64 %1, 1 + %4 = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 %0 + %5 = call i64 @strnlen(i8* nonnull %4, i64 %3) + %6 = icmp eq i64 %5, 0 + ret i1 %6 +} + + +; Do not fold strnlen(s5 + %0, %1) for a constant s5 when %1 might be zero. + +define i1 @call_strnlen_s5_pi_n_eqz(i64 %0, i64 %1) { +; CHECK-LABEL: @call_strnlen_s5_pi_n_eqz( +; CHECK-NEXT: [[TMP3:%.*]] = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 [[TMP0:%.*]] +; CHECK-NEXT: [[TMP4:%.*]] = call i64 @strnlen(i8* nonnull [[TMP3]], i64 [[TMP1:%.*]]) +; CHECK-NEXT: [[TMP5:%.*]] = icmp eq i64 [[TMP4]], 0 +; CHECK-NEXT: ret i1 [[TMP5]] +; + + %3 = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 %0 + %4 = call i64 @strnlen(i8* nonnull %3, i64 %1) + %5 = icmp eq i64 %4, 0 + ret i1 %5 +} diff --git a/llvm/test/Transforms/InstCombine/strnlen-6.ll b/llvm/test/Transforms/InstCombine/strnlen-6.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/strnlen-6.ll @@ -0,0 +1,60 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; Verify that strnlen calls that aren't folded into constants are annotated +; with noundef, nonnull, and dereferenceable only when maxlen is known to +; to be nonzero. +; +; RUN: opt < %s -passes=instcombine -S | FileCheck %s + +declare i64 @strnlen(i8*, i64) + +@ecp = external global i8*, align 8 + + +; Annotate strnlen(ecp, 3) call with noundef, nonnull, and dereferenceable +; based on the access to *ecp. + +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* noundef nonnull dereferenceable(1) [[PTR]], i64 3) +; CHECK-NEXT: ret i64 [[LEN]] +; + %ptr = load i8*, i8** @ecp + %len = call i64 @strnlen(i8* %ptr, i64 3) + ret i64 %len +} + + +; Annotate strnlen(ecp, %n) call with nonzero %n with noundef, nonnull, and +; dereferenceable based on the access to *ecp. + +define i64 @deref_strnlen_ecp_nz(i64 %n) { +; 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* noundef nonnull dereferenceable(1) [[PTR]], i64 [[NONZERO]]) +; CHECK-NEXT: ret i64 [[LEN]] +; + %nonzero = or i64 %n, 1 + %ptr = load i8*, i8** @ecp + %len = call i64 @strnlen(i8* %ptr, i64 %nonzero) + ret i64 %len +} + + + +; Do not annotate strnlen(ecp, %n) call with nonnull etc. because it need +; not access *ecp. (Strictly, every pointer function argument must be +; noundef, so this is overly conservative.) + + +define i64 @noderef_strnlen_ecp_n(i64 %n) { +; CHECK-LABEL: @noderef_strnlen_ecp_n( +; CHECK-NEXT: [[PTR:%.*]] = load i8*, i8** @ecp, align 8 +; CHECK-NEXT: [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 [[N:%.*]]) +; CHECK-NEXT: ret i64 [[LEN]] +; + %ptr = load i8*, i8** @ecp + %len = call i64 @strnlen(i8* %ptr, i64 %n) + ret i64 %len +} diff --git a/llvm/test/Transforms/InstCombine/wcslen-5.ll b/llvm/test/Transforms/InstCombine/wcslen-5.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/wcslen-5.ll @@ -0,0 +1,149 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; Verify that wcslen calls with conditional expressions involving constant +; string arguments with nonconstant offsets are folded as expected. See +; strlen-4.ll for the corresponding strlen test. +; +; RUN: opt < %s -passes=instcombine -S | FileCheck %s + +declare i64 @wcslen(i32*) + +!0 = !{i32 1, !"wchar_size", i32 4} +!llvm.module.flags = !{!0} + +@ws3 = constant [4 x i32] [i32 1, i32 2, i32 3, i32 0] +@ws5 = constant [6 x i32] [i32 1, i32 2, i32 3, i32 4, i32 5, i32 0] +@ws5_3 = constant [10 x i32] [i32 1, i32 2, i32 3, i32 4, i32 5, i32 0, i32 6, i32 7, i32 8, i32 0] + + +; Fold wcslen (x ? s3 + i: s5) to x ? 3 - i : 5. + +define dso_local i64 @fold_wcslen_s3_pi_s5(i1 zeroext %0, i64 %1) { +; CHECK-LABEL: @fold_wcslen_s3_pi_s5( +; 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 + %ps5 = getelementptr inbounds [6 x i32], [6 x i32]* @ws5, i64 0, i64 0 + %sel = select i1 %0, i32* %ps3_pi, i32* %ps5 + %len = tail call i64 @wcslen(i32* %sel) + ret i64 %len +} + + +; More complex expressions like the one below are not handled yet. +; Fold: wcslen (x ? s3 + i + 1 : s5 + j + 2) to x ? 2 - i : 3 - j. + +define dso_local i64 @fold_wcslen_s3_pi_p1_s5(i1 zeroext %0, i64 %1) { +; XFAIL-CHECK-LABEL: @fold_wcslen_s3_pi_p1_s5( +; XFAIL-CHECK-NEXT: [[DIF_I:%.*]] = sub i64 2, %1 +; XFAIL-CHECK-NEXT: [[SEL:%.*]] = select i1 %0, i64 [[DIF_I]], i64 5 +; XFAIL-CHECK-NEXT: ret i64 [[SEL]] +; CHECK-LABEL: @fold_wcslen_s3_pi_p1_s5( +; CHECK-NEXT: [[PS3_PI:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @ws3, i64 0, i64 [[TMP1:%.*]] +; CHECK-NEXT: [[PS3_PI_P1:%.*]] = getelementptr inbounds i32, i32* [[PS3_PI]], i64 1 +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[TMP0:%.*]], i32* [[PS3_PI_P1]], 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]] +; + + %ps3_pi = getelementptr inbounds [4 x i32], [4 x i32]* @ws3, i64 0, i64 %1 + %ps3_pi_p1 = getelementptr inbounds i32, i32* %ps3_pi, i64 1 + %ps5 = getelementptr inbounds [6 x i32], [6 x i32]* @ws5, i64 0, i64 0 + %sel = select i1 %0, i32* %ps3_pi_p1, i32* %ps5 + %len = tail call i64 @wcslen(i32* %sel) + ret i64 %len +} + + +; Avoid folding calls with conditional expressions involving constant +; string arguments with embedded nuls such as: +; wcslen (x ? s5_3 + i : s5). + +define dso_local i64 @call_wcslen_s5_3_pi_s5(i1 zeroext %0, i64 %1) { +; CHECK-LABEL: @call_wcslen_s5_3_pi_s5( +; CHECK-NEXT: [[PS5_3_PI:%.*]] = getelementptr inbounds [10 x i32], [10 x i32]* @ws5_3, i64 0, i64 [[TMP1:%.*]] +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[TMP0:%.*]], i32* [[PS5_3_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]] +; + + %ps5_3_pi = getelementptr inbounds [10 x i32], [10 x i32]* @ws5_3, i64 0, i64 %1 + %ps5 = getelementptr inbounds [6 x i32], [6 x i32]* @ws5, i64 0, i64 0 + %sel = select i1 %0, i32* %ps5_3_pi, i32* %ps5 + %len = tail call i64 @wcslen(i32* %sel) + ret i64 %len +} + + +; But do fold wcslen (x ? s5_3 : s5 + j) to x ? 5 : 5 - j. + +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: [[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 + %ps5 = getelementptr inbounds [6 x i32], [6 x i32]* @ws5, i64 0, i64 %1 + %sel = select i1 %0, i32* %ps5_3_pi, i32* %ps5 + %len = tail call i64 @wcslen(i32* %sel) + ret i64 %len +} + + +; Fold wcslen (x ? s3: s5 + j) to x ? 3 : 5 - j. + +define dso_local i64 @fold_wcslen_s3_s5_pj(i1 zeroext %0, i64 %1) { +; CHECK-LABEL: @fold_wcslen_s3_s5_pj( +; 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 + %ps5_pj = getelementptr inbounds [6 x i32], [6 x i32]* @ws5, i64 0, i64 %1 + %sel = select i1 %0, i32* %ps3, i32* %ps5_pj + %len = tail call i64 @wcslen(i32* %sel) + ret i64 %len +} + + +; Same as above, avoid folding calls with conditional expressions involving +; constant string arguments with embedded nuls such as: +; wcslen (x ? s3 : s5_3 + j). + +define dso_local i64 @call_wcslen_s3_s5_3_pj(i1 zeroext %0, i64 %1) { +; CHECK-LABEL: @call_wcslen_s3_s5_3_pj( +; CHECK-NEXT: [[PS5_3_PJ:%.*]] = getelementptr inbounds [10 x i32], [10 x i32]* @ws5_3, 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_3_PJ]] +; CHECK-NEXT: [[LEN:%.*]] = tail call i64 @wcslen(i32* [[SEL]]) +; CHECK-NEXT: ret i64 [[LEN]] +; + + %ps3 = getelementptr inbounds [4 x i32], [4 x i32]* @ws3, i64 0, i64 0 + %ps5_3_pj = getelementptr inbounds [10 x i32], [10 x i32]* @ws5_3, i64 0, i64 %1 + %sel = select i1 %0, i32* %ps3, i32* %ps5_3_pj + %len = tail call i64 @wcslen(i32* %sel) + ret i64 %len +} + + +; Fold wcslen (x ? s3 + i: s5 + j) to x ? 3 - i : 5 - j. + +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: [[TMP4:%.*]] = sub i64 5, [[TMP2:%.*]] +; CHECK-NEXT: [[TMP5:%.*]] = sub i64 3, [[TMP1:%.*]] +; CHECK-NEXT: [[TMP6:%.*]] = select i1 [[TMP0:%.*]], i64 [[TMP5]], i64 [[TMP4]] +; CHECK-NEXT: ret i64 [[TMP6]] +; + + %ps3_pi = getelementptr inbounds [4 x i32], [4 x i32]* @ws3, i64 0, i64 %1 + %ps5_pj = getelementptr inbounds [6 x i32], [6 x i32]* @ws5, i64 0, i64 %2 + %sel = select i1 %0, i32* %ps3_pi, i32* %ps5_pj + %len = tail call i64 @wcslen(i32* %sel) + ret i64 %len +}