Index: include/llvm/Analysis/ScalarEvolution.h =================================================================== --- include/llvm/Analysis/ScalarEvolution.h +++ include/llvm/Analysis/ScalarEvolution.h @@ -1433,7 +1433,7 @@ /// Compute the number of times the backedge of the specified loop will /// execute if its exit condition were a conditional branch of ExitCond, - /// TBB, and FBB. + /// and ExitByCond. /// /// \p ControlsExit is true if ExitCond directly controls the exit /// branch. In this case, we can assume that the loop exits only if the @@ -1443,15 +1443,14 @@ /// If \p AllowPredicates is set, this call will try to use a minimal set of /// SCEV predicates in order to return an exact answer. ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, - BasicBlock *TBB, BasicBlock *FBB, - bool ControlsExit, + bool ExitByCond, bool ControlsExit, bool AllowPredicates = false); // Helper functions for computeExitLimitFromCond to avoid exponential time // complexity. class ExitLimitCache { - // It may look like we need key on the whole (L, TBB, FBB, ControlsExit, + // It may look like we need key on the whole (L, ExitByCond, ControlsExit, // AllowPredicates) tuple, but recursive calls to // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only // vary the in \c ExitCond and \c ControlsExit parameters. We remember the @@ -1459,43 +1458,39 @@ SmallDenseMap, ExitLimit> TripCountMap; const Loop *L; - BasicBlock *TBB; - BasicBlock *FBB; + bool ExitByCond; bool AllowPredicates; public: - ExitLimitCache(const Loop *L, BasicBlock *TBB, BasicBlock *FBB, - bool AllowPredicates) - : L(L), TBB(TBB), FBB(FBB), AllowPredicates(AllowPredicates) {} + ExitLimitCache(const Loop *L, bool ExitByCond, bool AllowPredicates) + : L(L), ExitByCond(ExitByCond), AllowPredicates(AllowPredicates) {} - Optional find(const Loop *L, Value *ExitCond, BasicBlock *TBB, - BasicBlock *FBB, bool ControlsExit, - bool AllowPredicates); + Optional find(const Loop *L, Value *ExitCond, bool ExitByCond, + bool ControlsExit, bool AllowPredicates); - void insert(const Loop *L, Value *ExitCond, BasicBlock *TBB, - BasicBlock *FBB, bool ControlsExit, bool AllowPredicates, - const ExitLimit &EL); + void insert(const Loop *L, Value *ExitCond, bool ExitByCond, + bool ControlsExit, bool AllowPredicates, const ExitLimit &EL); }; using ExitLimitCacheTy = ExitLimitCache; ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, - BasicBlock *TBB, BasicBlock *FBB, + bool ExitByCond, bool ControlsExit, bool AllowPredicates); ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L, - Value *ExitCond, BasicBlock *TBB, - BasicBlock *FBB, bool ControlsExit, + Value *ExitCond, bool ExitByCond, + bool ControlsExit, bool AllowPredicates); /// Compute the number of times the backedge of the specified loop will /// execute if its exit condition were a conditional branch of the ICmpInst - /// ExitCond, TBB, and FBB. If AllowPredicates is set, this call will try + /// ExitCond and ExitByCond. If AllowPredicates is set, this call will try /// to use a minimal set of SCEV predicates in order to return an exact /// answer. ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, - BasicBlock *TBB, BasicBlock *FBB, + bool ExitByCond, bool IsSubExpr, bool AllowPredicates = false); Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -6942,9 +6942,12 @@ TerminatorInst *Term = ExitingBlock->getTerminator(); if (BranchInst *BI = dyn_cast(Term)) { assert(BI->isConditional() && "If unconditional, it can't be in loop!"); + bool ExitByCond = !L->contains(BI->getSuccessor(0)); + assert(ExitByCond == L->contains(BI->getSuccessor(1)) && + "It should have one successor in loop and one exit block!"); // Proceed to the next level to examine the exit condition expression. return computeExitLimitFromCond( - L, BI->getCondition(), BI->getSuccessor(0), BI->getSuccessor(1), + L, BI->getCondition(), ExitByCond, /*ControlsExit=*/IsOnlyExit, AllowPredicates); } @@ -6956,23 +6959,21 @@ } ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCond( - const Loop *L, Value *ExitCond, BasicBlock *TBB, BasicBlock *FBB, + const Loop *L, Value *ExitCond, bool ExitByCond, bool ControlsExit, bool AllowPredicates) { - ScalarEvolution::ExitLimitCacheTy Cache(L, TBB, FBB, AllowPredicates); - return computeExitLimitFromCondCached(Cache, L, ExitCond, TBB, FBB, + ScalarEvolution::ExitLimitCacheTy Cache(L, ExitByCond, AllowPredicates); + return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitByCond, ControlsExit, AllowPredicates); } Optional ScalarEvolution::ExitLimitCache::find(const Loop *L, Value *ExitCond, - BasicBlock *TBB, BasicBlock *FBB, - bool ControlsExit, bool AllowPredicates) { + bool ExitByCond, bool ControlsExit, + bool AllowPredicates) { (void)this->L; - (void)this->TBB; - (void)this->FBB; (void)this->AllowPredicates; - assert(this->L == L && this->TBB == TBB && this->FBB == FBB && + assert(this->L == L && this->ExitByCond == ExitByCond && this->AllowPredicates == AllowPredicates && "Variance in assumed invariant key components!"); auto Itr = TripCountMap.find({ExitCond, ControlsExit}); @@ -6982,11 +6983,11 @@ } void ScalarEvolution::ExitLimitCache::insert(const Loop *L, Value *ExitCond, - BasicBlock *TBB, BasicBlock *FBB, + bool ExitByCond, bool ControlsExit, bool AllowPredicates, const ExitLimit &EL) { - assert(this->L == L && this->TBB == TBB && this->FBB == FBB && + assert(this->L == L && this->ExitByCond == ExitByCond && this->AllowPredicates == AllowPredicates && "Variance in assumed invariant key components!"); @@ -6996,36 +6997,35 @@ } ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached( - ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, BasicBlock *TBB, - BasicBlock *FBB, bool ControlsExit, bool AllowPredicates) { + ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitByCond, + bool ControlsExit, bool AllowPredicates) { if (auto MaybeEL = - Cache.find(L, ExitCond, TBB, FBB, ControlsExit, AllowPredicates)) + Cache.find(L, ExitCond, ExitByCond, ControlsExit, AllowPredicates)) return *MaybeEL; - ExitLimit EL = computeExitLimitFromCondImpl(Cache, L, ExitCond, TBB, FBB, + ExitLimit EL = computeExitLimitFromCondImpl(Cache, L, ExitCond, ExitByCond, ControlsExit, AllowPredicates); - Cache.insert(L, ExitCond, TBB, FBB, ControlsExit, AllowPredicates, EL); + Cache.insert(L, ExitCond, ExitByCond, ControlsExit, AllowPredicates, EL); return EL; } ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl( - ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, BasicBlock *TBB, - BasicBlock *FBB, bool ControlsExit, bool AllowPredicates) { + ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitByCond, + bool ControlsExit, bool AllowPredicates) { // Check if the controlling expression for this loop is an And or Or. if (BinaryOperator *BO = dyn_cast(ExitCond)) { if (BO->getOpcode() == Instruction::And) { // Recurse on the operands of the and. - bool EitherMayExit = L->contains(TBB); ExitLimit EL0 = computeExitLimitFromCondCached( - Cache, L, BO->getOperand(0), TBB, FBB, ControlsExit && !EitherMayExit, + Cache, L, BO->getOperand(0), ExitByCond, ControlsExit && ExitByCond, AllowPredicates); ExitLimit EL1 = computeExitLimitFromCondCached( - Cache, L, BO->getOperand(1), TBB, FBB, ControlsExit && !EitherMayExit, + Cache, L, BO->getOperand(1), ExitByCond, ControlsExit && ExitByCond, AllowPredicates); const SCEV *BECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute(); - if (EitherMayExit) { + if (!ExitByCond) { // Both conditions must be true for the loop to continue executing. // Choose the less conservative count. if (EL0.ExactNotTaken == getCouldNotCompute() || @@ -7044,7 +7044,6 @@ } else { // Both conditions must be true at the same time for the loop to exit. // For now, be conservative. - assert(L->contains(FBB) && "Loop block has no successor in loop!"); if (EL0.MaxNotTaken == EL1.MaxNotTaken) MaxBECount = EL0.MaxNotTaken; if (EL0.ExactNotTaken == EL1.ExactNotTaken) @@ -7065,16 +7064,15 @@ } if (BO->getOpcode() == Instruction::Or) { // Recurse on the operands of the or. - bool EitherMayExit = L->contains(FBB); ExitLimit EL0 = computeExitLimitFromCondCached( - Cache, L, BO->getOperand(0), TBB, FBB, ControlsExit && !EitherMayExit, + Cache, L, BO->getOperand(0), ExitByCond, ControlsExit && !ExitByCond, AllowPredicates); ExitLimit EL1 = computeExitLimitFromCondCached( - Cache, L, BO->getOperand(1), TBB, FBB, ControlsExit && !EitherMayExit, + Cache, L, BO->getOperand(1), ExitByCond, ControlsExit && !ExitByCond, AllowPredicates); const SCEV *BECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute(); - if (EitherMayExit) { + if (ExitByCond) { // Both conditions must be false for the loop to continue executing. // Choose the less conservative count. if (EL0.ExactNotTaken == getCouldNotCompute() || @@ -7093,7 +7091,6 @@ } else { // Both conditions must be false at the same time for the loop to exit. // For now, be conservative. - assert(L->contains(TBB) && "Loop block has no successor in loop!"); if (EL0.MaxNotTaken == EL1.MaxNotTaken) MaxBECount = EL0.MaxNotTaken; if (EL0.ExactNotTaken == EL1.ExactNotTaken) @@ -7109,12 +7106,12 @@ // Proceed to the next level to examine the icmp. if (ICmpInst *ExitCondICmp = dyn_cast(ExitCond)) { ExitLimit EL = - computeExitLimitFromICmp(L, ExitCondICmp, TBB, FBB, ControlsExit); + computeExitLimitFromICmp(L, ExitCondICmp, ExitByCond, ControlsExit); if (EL.hasFullInfo() || !AllowPredicates) return EL; // Try again, but use SCEV predicates this time. - return computeExitLimitFromICmp(L, ExitCondICmp, TBB, FBB, ControlsExit, + return computeExitLimitFromICmp(L, ExitCondICmp, ExitByCond, ControlsExit, /*AllowPredicates=*/true); } @@ -7123,7 +7120,7 @@ // preserve the CFG and is temporarily leaving constant conditions // in place. if (ConstantInt *CI = dyn_cast(ExitCond)) { - if (L->contains(FBB) == !CI->getZExtValue()) + if (ExitByCond == !CI->getZExtValue()) // The backedge is always taken. return getCouldNotCompute(); else @@ -7132,19 +7129,18 @@ } // If it's not an integer or pointer comparison then compute it the hard way. - return computeExitCountExhaustively(L, ExitCond, !L->contains(TBB)); + return computeExitCountExhaustively(L, ExitCond, ExitByCond); } ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, - BasicBlock *TBB, - BasicBlock *FBB, + bool ExitByCond, bool ControlsExit, bool AllowPredicates) { // If the condition was exit on true, convert the condition to exit on false ICmpInst::Predicate Pred; - if (!L->contains(FBB)) + if (!ExitByCond) Pred = ExitCond->getPredicate(); else Pred = ExitCond->getInversePredicate(); @@ -7226,7 +7222,7 @@ } auto *ExhaustiveCount = - computeExitCountExhaustively(L, ExitCond, !L->contains(TBB)); + computeExitCountExhaustively(L, ExitCond, ExitByCond); if (!isa(ExhaustiveCount)) return ExhaustiveCount;