Index: include/llvm/Analysis/ScalarEvolution.h =================================================================== --- include/llvm/Analysis/ScalarEvolution.h +++ include/llvm/Analysis/ScalarEvolution.h @@ -750,6 +750,19 @@ /// SCEVCouldNotCompute object. const SCEV *getMaxBackedgeTakenCount(const Loop *L); + /// Returns precise number of iterations which it takes for \p AR to reach the + /// bound of signed/unsigned range (which one is defined by \p Signed), or + /// SCEVCouldNotCompute if it fails to compute this number. + const SCEV *getNumberOfIterationsToLimit(const SCEVAddRecExpr *AR, + bool Signed); + + /// Returns true if the \p AR does not have signed/unsigned wrap + /// (which one is defined by \p Signed) even if the loop exits by latch + /// condition and no abnormal exit is taken. In other words, that it does not + /// overflow if the loop makes the number of iterations returned by + /// getBackedgeTakenCount(). + bool isProvedNoOverflowOnNormalExit(const SCEVAddRecExpr *AR, bool Signed); + /// Return true if the backedge taken count is either the value returned by /// getMaxBackedgeTakenCount or zero. bool isBackedgeTakenCountMaxOrZero(const Loop *L); Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -6406,6 +6406,66 @@ return getBackedgeTakenInfo(L).getMax(this); } +const SCEV * +ScalarEvolution::getNumberOfIterationsToLimit(const SCEVAddRecExpr *AR, + bool Signed) { + unsigned BitWidth = getTypeSizeInBits(AR->getType()); + + // We assume that MinLimit <= Start <= MaxLimit (signed/unsigned comparison is + // defined by Signed flag), so (Maxlimit - Start) and (Start - MinLimit) can + // be interpreted as unsigned non-negative values. + const SCEV *Start = AR->getStart(); + const SCEV *Step = AR->getStepRecurrence(*this); + if (!isAvailableAtLoopEntry(Step, AR->getLoop())) + return getCouldNotCompute(); + + // [LeftBorder, RightBorder] represent a range where the AR iterates without + // overflow. + const SCEV *LeftBorder = nullptr; + const SCEV *RightBorder = nullptr; + if (isKnownNegative(Step)) { + Step = getNegativeSCEV(Step); + LeftBorder = Signed ? getConstant(APInt::getSignedMinValue(BitWidth)) + : getConstant(APInt::getMinValue(BitWidth)); + RightBorder = Start; + } else if (isKnownPositive(Step)) { + LeftBorder = Start; + RightBorder = Signed ? getConstant(APInt::getSignedMaxValue(BitWidth)) + : getConstant(APInt::getMaxValue(BitWidth)); + } else + return getCouldNotCompute(); + + return getUDivExpr(getMinusSCEV(RightBorder, LeftBorder), Step); +} + +bool ScalarEvolution::isProvedNoOverflowOnNormalExit(const SCEVAddRecExpr *AR, + bool Signed) { + const Loop *L = AR->getLoop(); + // The nsw/nuw flag for monotonicity could have been proved via some guard + // within the loop. Make sure that we do not actually overflow. + const SCEV *NumIters = getBackedgeTakenCount(L); + if (isa(NumIters)) + return false; + + const SCEV *ItersToLimit = getNumberOfIterationsToLimit(AR, Signed); + if (isa(ItersToLimit)) + return false; + + // Use the fact that we are in the loop to strip negative parts of ranges. + Type *WiderType = getWiderType(NumIters->getType(), ItersToLimit->getType()); + auto StripOffNegativePart = [&](const SCEV *S) { + S = getNoopOrZeroExtend(S, WiderType); + const SCEV *Zero = getZero(WiderType); + if (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, S, Zero)) + return getSMaxExpr(S, Zero); + return S; + }; + + return isLoopEntryGuardedByCond(L, ICmpInst::ICMP_ULE, + StripOffNegativePart(NumIters), + StripOffNegativePart(ItersToLimit)); +} + bool ScalarEvolution::isBackedgeTakenCountMaxOrZero(const Loop *L) { return getBackedgeTakenInfo(L).isMaxOrZero(this); } Index: unittests/Analysis/ScalarEvolutionTest.cpp =================================================================== --- unittests/Analysis/ScalarEvolutionTest.cpp +++ unittests/Analysis/ScalarEvolutionTest.cpp @@ -1390,5 +1390,217 @@ EXPECT_FALSE(I->hasNoSignedWrap()); } +// Make sure that SCEV correctly identifies which Phis cannot overflow on normal +// exit. Loop with positive step. +TEST_F(ScalarEvolutionsTest, SCEVNoOverflowOnNormalExitInc) { + /* + * Create the following code: + * func(i64 addrspace(10)* %arg) + * top: + * br label %L.ph + * L.ph: + * br label %L + * L: + * %phi = phi i64 [ i64 0, %L.ph ], [ %add, %L2 ] + * %iv1 = phi i64 [ i64 SINT_MIN ], [ i64 %iv1.inc ] ; Does not wrap + * %iv2 = phi i64 [ i64 SINT_MAX - 1000 ], [ i64 %iv2.inc ] ; Does not wrap + * %iv3 = phi i64 [ i64 SINT_MAX - 999 ], [ i64 %iv3.inc ] ; Wraps + * %iv1.inc = add i64 %iv1, 1 + * %iv2.inc = add i64 %iv2, 1 + * %iv3.inc = add i64 %iv3, 1 + * %add = add i64 %phi2, 1 + * %cond = icmp slt i64 %phi, 1000. + * br i1 %cond, label %post, label %L2 + * post: + * ret void + * + */ + + // Create a module with non-integral pointers in it's datalayout + Module NIM("nonintegral", Context); + std::string DataLayout = M.getDataLayoutStr(); + if (!DataLayout.empty()) + DataLayout += "-"; + DataLayout += "ni:10"; + NIM.setDataLayout(DataLayout); + + Type *T_int64 = Type::getInt64Ty(Context); + Type *T_pint64 = T_int64->getPointerTo(10); + + FunctionType *FTy = + FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); + Function *F = cast(NIM.getOrInsertFunction("foo", FTy)); + + BasicBlock *Top = BasicBlock::Create(Context, "top", F); + BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F); + BasicBlock *L = BasicBlock::Create(Context, "L", F); + BasicBlock *Post = BasicBlock::Create(Context, "post", F); + + IRBuilder<> Builder(Top); + Builder.CreateBr(LPh); + + Builder.SetInsertPoint(LPh); + Builder.CreateBr(L); + + Builder.SetInsertPoint(L); + PHINode *Phi = Builder.CreatePHI(T_int64, 2); + PHINode *IV1 = Builder.CreatePHI(T_int64, 2); + PHINode *IV2 = Builder.CreatePHI(T_int64, 2); + PHINode *IV3 = Builder.CreatePHI(T_int64, 2); + + uint64_t Min = std::numeric_limits::min(); + uint64_t Max = std::numeric_limits::max(); + + auto *Add = cast( + Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add")); + auto *IV1Inc = cast( + Builder.CreateAdd(IV1, ConstantInt::get(T_int64, 1), "inc")); + auto *IV2Inc = cast( + Builder.CreateAdd(IV2, ConstantInt::get(T_int64, 1), "inc")); + auto *IV3Inc = cast( + Builder.CreateAdd(IV3, ConstantInt::get(T_int64, 1), "inc")); + auto *Cond = cast(Builder.CreateICmp( + ICmpInst::ICMP_SLT, Phi, ConstantInt::get(T_int64, 1000), "cond")); + Builder.CreateCondBr(Cond, L, Post); + + Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh); + Phi->addIncoming(Add, L); + + IV1->addIncoming(ConstantInt::get(T_int64, Min), LPh); + IV2->addIncoming(ConstantInt::get(T_int64, Max - 1000), LPh); + IV3->addIncoming(ConstantInt::get(T_int64, Max - 999), LPh); + + IV1->addIncoming(IV1Inc, L); + IV2->addIncoming(IV2Inc, L); + IV3->addIncoming(IV3Inc, L); + + Builder.SetInsertPoint(Post); + Builder.CreateRetVoid(); + + ScalarEvolution SE = buildSE(*F); + auto *Loop = LI->getLoopFor(L); + const SCEV *EC = SE.getBackedgeTakenCount(Loop); + EXPECT_TRUE(isa(EC)); + EXPECT_EQ(1000u, cast(EC)->getAPInt().getLimitedValue()); + auto *AR1 = dyn_cast(SE.getSCEV(IV1)); + auto *AR2 = dyn_cast(SE.getSCEV(IV2)); + auto *AR3 = dyn_cast(SE.getSCEV(IV3)); + EXPECT_NE(nullptr, AR1); + EXPECT_NE(nullptr, AR2); + EXPECT_NE(nullptr, AR3); + EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR1, /* Signed */ true)); + EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR2, /* Signed */ true)); + EXPECT_FALSE(SE.isProvedNoOverflowOnNormalExit(AR3, /* Signed */ true)); + EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR1, /* Signed */ false)); + EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR2, /* Signed */ false)); + EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR3, /* Signed */ false)); +} + +// Make sure that SCEV correctly identifies which Phis cannot overflow on normal +// exit. Loop with negative step. +TEST_F(ScalarEvolutionsTest, SCEVNoOverflowOnNormalExitDec) { + /* + * Create the following code: + * func(i64 addrspace(10)* %arg) + * top: + * br label %L.ph + * L.ph: + * br label %L + * L: + * %phi = phi i64 [ i64 0, %L.ph ], [ %add, %L2 ] + * %iv1 = phi i64 [ i64 SINT_MAX ], [ i64 %iv1.inc ] ; Does not wrap + * %iv2 = phi i64 [ i64 SINT_MIN + 1000 ], [ i64 %iv2.inc ] ; Does not wrap + * %iv3 = phi i64 [ i64 SINT_MIN + 999 ], [ i64 %iv3.inc ] ; Wraps + * %iv1.inc = add i64 %iv1, -1 + * %iv2.inc = add i64 %iv2, -1 + * %iv3.inc = add i64 %iv3, -1 + * %add = add i64 %phi2, 1 + * %cond = icmp slt i64 %phi, 1000. + * br i1 %cond, label %post, label %L2 + * post: + * ret void + * + */ + + // Create a module with non-integral pointers in it's datalayout + Module NIM("nonintegral", Context); + std::string DataLayout = M.getDataLayoutStr(); + if (!DataLayout.empty()) + DataLayout += "-"; + DataLayout += "ni:10"; + NIM.setDataLayout(DataLayout); + + Type *T_int64 = Type::getInt64Ty(Context); + Type *T_pint64 = T_int64->getPointerTo(10); + + FunctionType *FTy = + FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); + Function *F = cast(NIM.getOrInsertFunction("foo", FTy)); + + BasicBlock *Top = BasicBlock::Create(Context, "top", F); + BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F); + BasicBlock *L = BasicBlock::Create(Context, "L", F); + BasicBlock *Post = BasicBlock::Create(Context, "post", F); + + IRBuilder<> Builder(Top); + Builder.CreateBr(LPh); + + Builder.SetInsertPoint(LPh); + Builder.CreateBr(L); + + Builder.SetInsertPoint(L); + PHINode *Phi = Builder.CreatePHI(T_int64, 2); + PHINode *IV1 = Builder.CreatePHI(T_int64, 2); + PHINode *IV2 = Builder.CreatePHI(T_int64, 2); + PHINode *IV3 = Builder.CreatePHI(T_int64, 2); + + uint64_t Min = std::numeric_limits::min(); + uint64_t Max = std::numeric_limits::max(); + + auto *Add = cast( + Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add")); + auto *IV1Inc = cast( + Builder.CreateAdd(IV1, ConstantInt::get(T_int64, -1), "dec")); + auto *IV2Inc = cast( + Builder.CreateAdd(IV2, ConstantInt::get(T_int64, -1), "dec")); + auto *IV3Inc = cast( + Builder.CreateAdd(IV3, ConstantInt::get(T_int64, -1), "dec")); + auto *Cond = cast(Builder.CreateICmp( + ICmpInst::ICMP_SLT, Phi, ConstantInt::get(T_int64, 1000), "cond")); + Builder.CreateCondBr(Cond, L, Post); + + Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh); + Phi->addIncoming(Add, L); + + IV1->addIncoming(ConstantInt::get(T_int64, Max), LPh); + IV2->addIncoming(ConstantInt::get(T_int64, Min + 1000), LPh); + IV3->addIncoming(ConstantInt::get(T_int64, Min + 999), LPh); + + IV1->addIncoming(IV1Inc, L); + IV2->addIncoming(IV2Inc, L); + IV3->addIncoming(IV3Inc, L); + + Builder.SetInsertPoint(Post); + Builder.CreateRetVoid(); + + ScalarEvolution SE = buildSE(*F); + auto *Loop = LI->getLoopFor(L); + const SCEV *EC = SE.getBackedgeTakenCount(Loop); + EXPECT_TRUE(isa(EC)); + EXPECT_EQ(1000u, cast(EC)->getAPInt().getLimitedValue()); + auto *AR1 = dyn_cast(SE.getSCEV(IV1)); + auto *AR2 = dyn_cast(SE.getSCEV(IV2)); + auto *AR3 = dyn_cast(SE.getSCEV(IV3)); + EXPECT_NE(nullptr, AR1); + EXPECT_NE(nullptr, AR2); + EXPECT_NE(nullptr, AR3); + EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR1, /* Signed */ true)); + EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR2, /* Signed */ true)); + EXPECT_FALSE(SE.isProvedNoOverflowOnNormalExit(AR3, /* Signed */ true)); + EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR1, /* Signed */ false)); + EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR2, /* Signed */ false)); + EXPECT_TRUE(SE.isProvedNoOverflowOnNormalExit(AR3, /* Signed */ false)); +} + } // end anonymous namespace } // end namespace llvm