Index: include/llvm/Analysis/ValueTracking.h =================================================================== --- include/llvm/Analysis/ValueTracking.h +++ include/llvm/Analysis/ValueTracking.h @@ -448,6 +448,21 @@ /// the parent of I. bool programUndefinedIfFullPoison(const Instruction *PoisonI); + /// Return true (in the first component) if \p IV can statically be + /// proved to never be poison. \p IV has to be a pre-inc or + /// post-inc induction variable in the loop \p L. + /// + /// The second component of the return value may be non-null only if + /// the first component is false. If non-null, it is the *only* + /// poison generating instruction causing \p I to (potentially) be + /// poison; and calling \c dropPoisonGeneratingFlags on it will make + /// \p I be non-poison. If there are more than one such poison + /// generating instructions, then the second component is null, + /// making {false, nullptr} the maximally conservative result + /// returned by this routine. + std::pair isIVNeverPoison(const Instruction *IV, + const Loop *L); + /// Starting with the assumption that \p I is not poison, fill \p /// NonPoison with a set of values that are also known to not be /// poison. Internally this is a simple worklist algorithm around Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -3842,6 +3842,82 @@ } } +static bool isTriviallyNotPoison(const Value *V) { + auto IsNonPoisonConstant = [](const Value *C) { + return isa(C) || isa(C) || + isa(C); + }; + + if (IsNonPoisonConstant(V)) + return true; + + auto *ConstGEP = dyn_cast_or_null(dyn_cast(V)); + if (!ConstGEP || !IsNonPoisonConstant(ConstGEP->getPointerOperand()) || + ConstGEP->getInRangeIndex()) + return false; + + return !ConstGEP->isInBounds() || ConstGEP->hasAllConstantIndices(); +} + +static std::pair +isIVPHINeverPoisonImpl(const PHINode *IV, const Loop *L) { + assert(IV->getParent() == L->getHeader() && "Invalid IV!"); + assert(IV->getNumIncomingValues() == 2 && "Invalid IV!"); + + if (!isTriviallyNotPoison( + IV->getIncomingValueForBlock(L->getLoopPreheader()))) + return {false, nullptr}; + + auto *BEVal = + cast(IV->getIncomingValueForBlock(L->getLoopLatch())); + + if (!all_of(BEVal->operands(), + [&](Value *I) { return I == IV || isa(I); })) + return {false, nullptr}; + + if (auto *OBO = dyn_cast(BEVal)) + return (OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap()) + ? std::make_pair(false, BEVal) + : std::make_pair(true, nullptr); + + if (auto *GEP = dyn_cast(BEVal)) + return GEP->isInBounds() ? std::make_pair(false, BEVal) + : std::make_pair(true, nullptr); + + return {false, nullptr}; +} + +static std::pair +isIVNeverPoisonImpl(const Instruction *I, const Loop *L) { + if (auto *PN = dyn_cast(I)) + return isIVPHINeverPoisonImpl(PN, L); + + auto IsHeaderPHI = [&](const Value *V) { + if (auto *PN = dyn_cast(V)) + return PN->getParent() == L->getHeader(); + return false; + }; + + auto PHIOpItr = find_if(I->operands(), IsHeaderPHI); + if (PHIOpItr == I->op_end()) + return {false, nullptr}; + + auto *PN = cast(*PHIOpItr); + assert(PN->getParent() == L->getHeader() && "Precondition violated!"); + if (PN->getIncomingValueForBlock(L->getLoopLatch()) != I) + return {false, nullptr}; + + return isIVPHINeverPoisonImpl(PN, L); +} + +std::pair +llvm::isIVNeverPoison(const Instruction *IV, const Loop *L) { + auto Result = isIVNeverPoisonImpl(IV, L); + assert((!Result.second || !Result.first) && + "Broken invarariant on return value!"); + return Result; +} + void llvm::propagateKnownNonPoison( const Value *I, SmallVectorImpl &NonPoison, function_ref FollowPred) { Index: unittests/Analysis/ValueTrackingTest.cpp =================================================================== --- unittests/Analysis/ValueTrackingTest.cpp +++ unittests/Analysis/ValueTrackingTest.cpp @@ -7,8 +7,10 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/AsmParser/Parser.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/LLVMContext.h" @@ -301,3 +303,124 @@ EXPECT_FALSE(is_contained(NonPoison, ArgA)); } } + +TEST(ValueTracking, isIVNeverPoison) { + StringRef Assembly = + "@data = external global [240 x i8] " + " " + "define void @f() { " + "entry: " + " br label %for.cond " + " " + "for.cond: " + " %iv_bad = phi i32 [ 0, %entry ], [ %iv_0.inc, %for.cond ] " + " %iv_0 = phi i32 [ 0, %entry ], [ %iv_0.inc, %for.cond ] " + " %iv_1 = phi i32 [ 0, %entry ], [ %iv_1.inc, %for.cond ] " + " %iv_2 = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* " + " @data, i64 0, i64 0), %entry ], [ %iv_2.inc, %for.cond ] " + " %iv_3 = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* " + " @data, i64 0, i64 0), %entry ], [ %iv_3.inc, %for.cond ] " + " %iv_4 = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* " + " @data, i64 0, i64 2), %entry ], [ %iv_2.inc, %for.cond ] " + " %iv_0.inc = add i32 %iv_0, 1 " + " %iv_1.inc = add nsw i32 %iv_1, 1 " + " %iv_2.inc = getelementptr i8, i8* %iv_2, i64 1 " + " %iv_3.inc = getelementptr inbounds i8, i8* %iv_3, i64 1 " + " %iv_4.inc = getelementptr inbounds i8, i8* %iv_4, i64 1 " + " %iv_0.offset.0 = add i32 %iv_0, 30 " + " %iv_0.offset.1 = add nsw i32 %iv_0, 1 " + " br i1 undef, label %for.cond, label %for.end " + " " + "for.end: " + " ret void " + "} "; + + LLVMContext Context; + SMDiagnostic Error; + auto M = parseAssemblyString(Assembly, Error, Context); + assert(M && "Bad assembly?"); + + auto *F = M->getFunction("f"); + assert(F && "Bad assembly?"); + + auto Itr = std::next(F->begin())->begin(); + + Instruction &iv_bad = *Itr++; + Instruction &iv_0 = *Itr++; + Instruction &iv_1 = *Itr++; + Instruction &iv_2 = *Itr++; + Instruction &iv_3 = *Itr++; + Instruction &iv_4 = *Itr++; + Instruction &iv_0_inc = *Itr++; + Instruction &iv_1_inc = *Itr++; + Instruction &iv_2_inc = *Itr++; + Instruction &iv_3_inc = *Itr++; + Instruction &iv_4_inc = *Itr++; + Instruction &iv_0_offset_0 = *Itr++; + Instruction &iv_0_offset_1 = *Itr++; + + DominatorTree DT(*F); + LoopInfo LI(DT); + Loop *L = LI.getLoopFor(iv_0.getParent()); + + typedef std::pair ResultTy; + + EXPECT_EQ(isIVNeverPoison(&iv_bad, L), ResultTy(false, nullptr)); + + EXPECT_EQ(isIVNeverPoison(&iv_0, L), ResultTy(true, nullptr)); + EXPECT_EQ(isIVNeverPoison(&iv_1, L), ResultTy(false, &iv_1_inc)); + EXPECT_EQ(isIVNeverPoison(&iv_2, L), ResultTy(true, nullptr)); + EXPECT_EQ(isIVNeverPoison(&iv_3, L), ResultTy(false, &iv_3_inc)); + EXPECT_EQ(isIVNeverPoison(&iv_4, L), ResultTy(false, nullptr)); + + EXPECT_EQ(isIVNeverPoison(&iv_0_inc, L), ResultTy(true, nullptr)); + EXPECT_EQ(isIVNeverPoison(&iv_1_inc, L), ResultTy(false, &iv_1_inc)); + EXPECT_EQ(isIVNeverPoison(&iv_2_inc, L), ResultTy(true, nullptr)); + EXPECT_EQ(isIVNeverPoison(&iv_3_inc, L), ResultTy(false, &iv_3_inc)); + EXPECT_EQ(isIVNeverPoison(&iv_4_inc, L), ResultTy(false, nullptr)); + + EXPECT_EQ(isIVNeverPoison(&iv_0_offset_0, L), ResultTy(false, nullptr)); + EXPECT_EQ(isIVNeverPoison(&iv_0_offset_1, L), ResultTy(false, nullptr)); +} + +TEST(ValueTracking, isIVNeverPoisonWithIntermediatePHI) { + StringRef Assembly = + "@data = external global [240 x i8] " + " " + "define void @f(i1 %c) { " + "entry: " + " br label %for.cond " + " " + "for.cond: " + " %iv_0 = phi i32 [ 0, %entry ], [ %iv_0.inc, %merge ] " + " br i1 %c, label %then, label %merge " + "then: " + " br label %merge " + "merge: " + " %increment_amt = phi i32 [ 0, %for.cond ], [ 5, %merge ] " + " %iv_0.inc = add i32 %increment_amt, %iv_0 " + " br i1 %c, label %for.cond, label %for.end " + " " + "for.end: " + " ret void " + "} "; + + LLVMContext Context; + SMDiagnostic Error; + auto M = parseAssemblyString(Assembly, Error, Context); + assert(M && "Bad assembly?"); + + auto *F = M->getFunction("f"); + assert(F && "Bad assembly?"); + + auto Itr = std::next(F->begin(), 3)->begin(); + const auto &iv_0_inc = *std::next(Itr); + + DominatorTree DT(*F); + LoopInfo LI(DT); + Loop *L = LI.getLoopFor(iv_0_inc.getParent()); + + typedef std::pair ResultTy; + + EXPECT_EQ(isIVNeverPoison(&iv_0_inc, L), ResultTy(false, nullptr)); +}