diff --git a/llvm/include/llvm/Analysis/IVUsers.h b/llvm/include/llvm/Analysis/IVUsers.h --- a/llvm/include/llvm/Analysis/IVUsers.h +++ b/llvm/include/llvm/Analysis/IVUsers.h @@ -157,9 +157,6 @@ /// dump - This method is used for debugging. void dump() const; - -protected: - bool AddUsersImpl(Instruction *I, SmallPtrSetImpl &SimpleLoopNests); }; Pass *createIVUsersPass(); diff --git a/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h b/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h --- a/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h +++ b/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h @@ -32,8 +32,10 @@ /// Return true if the given expression is safe to expand in the sense that /// all materialized values are safe to speculate anywhere their operands are -/// defined. -bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE); +/// defined, and the expander is capable of expanding the expression. +/// CanonicalMode indicates whether the expander will be used in canonical mode. +bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE, + bool CanonicalMode = true); /// Return true if the given expression is safe to expand in the sense that /// all materialized values are defined and safe to speculate at the specified diff --git a/llvm/lib/Analysis/IVUsers.cpp b/llvm/lib/Analysis/IVUsers.cpp --- a/llvm/lib/Analysis/IVUsers.cpp +++ b/llvm/lib/Analysis/IVUsers.cpp @@ -90,33 +90,6 @@ return false; } -/// Return true if all loop headers that dominate this block have a preheader. -static bool isPreheaderLoopNest(BasicBlock *BB, const DominatorTree *DT, - const LoopInfo *LI, - SmallPtrSetImpl &PreheaderLoopNests) { - Loop *NearestLoop = nullptr; - for (DomTreeNode *Rung = DT->getNode(BB); - Rung; Rung = Rung->getIDom()) { - BasicBlock *DomBB = Rung->getBlock(); - Loop *DomLoop = LI->getLoopFor(DomBB); - if (DomLoop && DomLoop->getHeader() == DomBB) { - // If we have already checked this loop nest, stop checking. - if (PreheaderLoopNests.count(DomLoop)) - break; - // If the domtree walk reaches a loop with no preheader, return false. - if (!DomLoop->getLoopPreheader()) - return false; - // If we have not already checked this loop nest, remember the loop - // header nearest to BB. The nearest loop may not contain BB. - if (!NearestLoop) - NearestLoop = DomLoop; - } - } - if (NearestLoop) - PreheaderLoopNests.insert(NearestLoop); - return true; -} - /// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression /// and now we need to decide whether the user should use the preinc or post-inc /// value. If this user should use the post-inc version of the IV, return true. @@ -161,11 +134,10 @@ return true; } -/// AddUsersImpl - Inspect the specified instruction. If it is a -/// reducible SCEV, recursively add its users to the IVUsesByStride set and -/// return true. Otherwise, return false. -bool IVUsers::AddUsersImpl(Instruction *I, - SmallPtrSetImpl &PreheaderLoopNests) { +/// Inspect the specified instruction. If it is a reducible SCEV, recursively +/// add its users to the IVUsesByStride set and return true. Otherwise, return +/// false. +bool IVUsers::AddUsersIfInteresting(Instruction *I) { const DataLayout &DL = I->getModule()->getDataLayout(); // Add this IV user to the Processed set before returning false to ensure that @@ -212,18 +184,6 @@ if (isa(User) && Processed.count(User)) continue; - // Only consider IVUsers that are dominated by simplified loop - // headers. Otherwise, SCEVExpander will crash. - BasicBlock *UseBB = User->getParent(); - // A phi's use is live out of its predecessor block. - if (PHINode *PHI = dyn_cast(User)) { - unsigned OperandNo = U.getOperandNo(); - unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo); - UseBB = PHI->getIncomingBlock(ValNo); - } - if (!isPreheaderLoopNest(UseBB, DT, LI, PreheaderLoopNests)) - return false; - // Descend recursively, but not into PHI nodes outside the current loop. // It's important to see the entire expression outside the loop to get // choices that depend on addressing mode use right, although we won't @@ -233,13 +193,12 @@ bool AddUserToIVUsers = false; if (LI->getLoopFor(User->getParent()) != L) { if (isa(User) || Processed.count(User) || - !AddUsersImpl(User, PreheaderLoopNests)) { + !AddUsersIfInteresting(User)) { LLVM_DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n' << " OF SCEV: " << *ISE << '\n'); AddUserToIVUsers = true; } - } else if (Processed.count(User) || - !AddUsersImpl(User, PreheaderLoopNests)) { + } else if (Processed.count(User) || !AddUsersIfInteresting(User)) { LLVM_DEBUG(dbgs() << "FOUND USER: " << *User << '\n' << " OF SCEV: " << *ISE << '\n'); AddUserToIVUsers = true; @@ -288,15 +247,6 @@ return true; } -bool IVUsers::AddUsersIfInteresting(Instruction *I) { - // SCEVExpander can only handle users that are dominated by loops with - // preheaders. Keep track of all loops that are only dominated by preheader - // loops so we don't traverse the domtree for each user. - SmallPtrSet PreheaderLoopNests; - - return AddUsersImpl(I, PreheaderLoopNests); -} - IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) { IVUses.push_back(new IVStrideUse(this, User, Operand)); return IVUses.back(); diff --git a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp --- a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -3391,7 +3391,7 @@ void LSRInstance::InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx) { // Mark uses whose expressions cannot be expanded. - if (!isSafeToExpand(S, SE)) + if (!isSafeToExpand(S, SE, /*CanonicalMode*/ false)) LU.RigidFormula = true; Formula F; @@ -5706,23 +5706,6 @@ } } -#ifndef NDEBUG - // All dominating loops must have preheaders, or SCEVExpander may not be able - // to materialize an AddRecExpr whose Start is an outer AddRecExpr. - // - // IVUsers analysis should only create users that are dominated by simple loop - // headers. Since this loop should dominate all of its users, its user list - // should be empty if this loop itself is not within a simple loop nest. - for (DomTreeNode *Rung = DT.getNode(L->getLoopPreheader()); - Rung; Rung = Rung->getIDom()) { - BasicBlock *BB = Rung->getBlock(); - const Loop *DomLoop = LI.getLoopFor(BB); - if (DomLoop && DomLoop->getHeader() == BB) { - assert(DomLoop->getLoopPreheader() && "LSR needs a simplified loop nest"); - } - } -#endif // DEBUG - LLVM_DEBUG(dbgs() << "\nLSR on loop "; L->getHeader()->printAsOperand(dbgs(), /*PrintType=*/false); dbgs() << ":\n"); diff --git a/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp b/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp --- a/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp +++ b/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp @@ -2618,9 +2618,11 @@ // perfectly reduced form, which can't be guaranteed. struct SCEVFindUnsafe { ScalarEvolution &SE; + bool CanonicalMode; bool IsUnsafe; - SCEVFindUnsafe(ScalarEvolution &se): SE(se), IsUnsafe(false) {} + SCEVFindUnsafe(ScalarEvolution &SE, bool CanonicalMode) + : SE(SE), CanonicalMode(CanonicalMode), IsUnsafe(false) {} bool follow(const SCEV *S) { if (const SCEVUDivExpr *D = dyn_cast(S)) { @@ -2636,6 +2638,14 @@ IsUnsafe = true; return false; } + + // For non-affine addrecs or in non-canonical mode we need a preheader + // to insert into. + if (!AR->getLoop()->getLoopPreheader() && + (!CanonicalMode || !AR->isAffine())) { + IsUnsafe = true; + return false; + } } return true; } @@ -2644,8 +2654,8 @@ } namespace llvm { -bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE) { - SCEVFindUnsafe Search(SE); +bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE, bool CanonicalMode) { + SCEVFindUnsafe Search(SE, CanonicalMode); visitAll(S, Search); return !Search.IsUnsafe; }