From eaa40ff74e41176250bd6b50116ab03b0c596d5e Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Sun, 29 Aug 2010 16:40:03 +0000 Subject: Make IVUsers iterative instead of recursive. This has the side effect of reversing the order of most of IVUser's results. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@112442 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/IVUsers.cpp | 167 +++++++++++++++++++++++++---------------------- 1 file changed, 89 insertions(+), 78 deletions(-) (limited to 'lib/Analysis/IVUsers.cpp') diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp index fd514336be..d9bdf5cbb0 100644 --- a/lib/Analysis/IVUsers.cpp +++ b/lib/Analysis/IVUsers.cpp @@ -35,112 +35,123 @@ Pass *llvm::createIVUsersPass() { return new IVUsers(); } -/// isInteresting - Test whether the given expression is "interesting" when -/// used by the given expression, within the context of analyzing the -/// given loop. -static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L, - ScalarEvolution *SE) { +/// findInterestingAddRec - Test whether the given expression is interesting. +/// Return the addrec with the current loop which makes it interesting, or +/// null if it is not interesting. +const SCEVAddRecExpr *IVUsers::findInterestingAddRec(const SCEV *S) const { // An addrec is interesting if it's affine or if it has an interesting start. if (const SCEVAddRecExpr *AR = dyn_cast(S)) { // Keep things simple. Don't touch loop-variant strides. if (AR->getLoop() == L) - return AR->isAffine() || !L->contains(I); - // Otherwise recurse to see if the start value is interesting, and that - // the step value is not interesting, since we don't yet know how to - // do effective SCEV expansions for addrecs with interesting steps. - return isInteresting(AR->getStart(), I, L, SE) && - !isInteresting(AR->getStepRecurrence(*SE), I, L, SE); + return AR; + // We don't yet know how to do effective SCEV expansions for addrecs + // with interesting steps. + if (findInterestingAddRec(AR->getStepRecurrence(*SE))) + return 0; + // Otherwise recurse to see if the start value is interesting. + return findInterestingAddRec(AR->getStart()); } // An add is interesting if exactly one of its operands is interesting. if (const SCEVAddExpr *Add = dyn_cast(S)) { - bool AnyInterestingYet = false; for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end(); OI != OE; ++OI) - if (isInteresting(*OI, I, L, SE)) { - if (AnyInterestingYet) - return false; - AnyInterestingYet = true; - } - return AnyInterestingYet; + if (const SCEVAddRecExpr *AR = findInterestingAddRec(*OI)) + return AR; + return 0; } // Nothing else is interesting here. - return false; + return 0; } -/// AddUsersIfInteresting - 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) { - if (!SE->isSCEVable(I->getType())) - return false; // Void and FP expressions cannot be reduced. +bool IVUsers::isInterestingUser(const Instruction *User) const { + // Void and FP expressions cannot be reduced. + if (!SE->isSCEVable(User->getType())) + return false; // LSR is not APInt clean, do not touch integers bigger than 64-bits. - if (SE->getTypeSizeInBits(I->getType()) > 64) + if (SE->getTypeSizeInBits(User->getType()) > 64) return false; - if (!Processed.insert(I)) - return true; // Instruction already handled. + // Don't descend into PHI nodes outside the current loop. + if (LI->getLoopFor(User->getParent()) != L && + isa(User)) + return false; - // Get the symbolic expression for this instruction. - const SCEV *ISE = SE->getSCEV(I); + // Otherwise, it may be interesting. + return true; +} - // If we've come to an uninteresting expression, stop the traversal and - // call this a user. - if (!isInteresting(ISE, I, L, SE)) - return false; +/// AddUsersIfInteresting - Inspect the specified instruction. If it is a +/// reducible SCEV, recursively add its users to the IVUsesByStride set and +/// return true. Otherwise, return false. +void IVUsers::AddUsersIfInteresting(Instruction *I) { + // Stop if we've seen this before. + if (!Processed.insert(I)) + return; - SmallPtrSet UniqueUsers; - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); - UI != E; ++UI) { - Instruction *User = cast(*UI); - if (!UniqueUsers.insert(User)) - continue; - - // Do not infinitely recurse on PHI nodes. - if (isa(User) && Processed.count(User)) - continue; - - // 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 - // consider references outside the loop in all cases. - // If User is already in Processed, we don't want to recurse into it again, - // but do want to record a second reference in the same instruction. - bool AddUserToIVUsers = false; - if (LI->getLoopFor(User->getParent()) != L) { - if (isa(User) || Processed.count(User) || - !AddUsersIfInteresting(User)) { - DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n' - << " OF SCEV: " << *ISE << '\n'); - AddUserToIVUsers = true; + // If this PHI node is not SCEVable, ignore it. + if (!SE->isSCEVable(I->getType())) + return; + + // If this PHI node is not an addrec for this loop, ignore it. + const SCEVAddRecExpr *Expr = findInterestingAddRec(SE->getSCEV(I)); + if (!Expr) + return; + + // Walk the def-use graph. + SmallVector, 16> Worklist; + Worklist.push_back(std::make_pair(I, Expr)); + do { + std::pair P = + Worklist.pop_back_val(); + Instruction *Op = P.first; + const SCEVAddRecExpr *OpAR = P.second; + + // Visit Op's users. + SmallPtrSet VisitedUsers; + for (Value::use_iterator UI = Op->use_begin(), E = Op->use_end(); + UI != E; ++UI) { + // Don't visit any individual user more than once. + Instruction *User = cast(*UI); + if (!VisitedUsers.insert(User)) + continue; + + // If it's an affine addrec (which we can pretty safely re-expand) inside + // the loop, or a potentially non-affine addrec outside the loop (which + // we can evaluate outside of the loop), follow it. + if (OpAR->isAffine() || !L->contains(User)) { + if (isInterestingUser(User)) { + const SCEV *UserExpr = SE->getSCEV(User); + + if (const SCEVAddRecExpr *AR = findInterestingAddRec(UserExpr)) { + // Interesting. Keep searching. + if (Processed.insert(User)) + Worklist.push_back(std::make_pair(User, AR)); + continue; + } + } } - } else if (Processed.count(User) || - !AddUsersIfInteresting(User)) { - DEBUG(dbgs() << "FOUND USER: " << *User << '\n' - << " OF SCEV: " << *ISE << '\n'); - AddUserToIVUsers = true; - } - if (AddUserToIVUsers) { - // Okay, we found a user that we cannot reduce. - IVUses.push_back(new IVStrideUse(this, User, I)); - IVStrideUse &NewUse = IVUses.back(); - // Transform the expression into a normalized form. - ISE = TransformForPostIncUse(NormalizeAutodetect, - ISE, User, I, - NewUse.PostIncLoops, - *SE, *DT); - DEBUG(dbgs() << " NORMALIZED TO: " << *ISE << '\n'); + // Otherwise, this is the point where the def-use chain + // becomes uninteresting. Call it an IV User. + AddUser(User, Op); } - } - return true; + } while (!Worklist.empty()); } IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) { IVUses.push_back(new IVStrideUse(this, User, Operand)); - return IVUses.back(); + IVStrideUse &NewUse = IVUses.back(); + + // Auto-detect and remember post-inc loops for this expression. + const SCEV *S = SE->getSCEV(Operand); + (void)TransformForPostIncUse(NormalizeAutodetect, + S, User, Operand, + NewUse.PostIncLoops, + *SE, *DT); + return NewUse; } IVUsers::IVUsers() @@ -165,7 +176,7 @@ bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { // them by stride. Start by finding all of the PHI nodes in the header for // this loop. If they are induction variables, inspect their uses. for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ++I) - (void)AddUsersIfInteresting(I); + AddUsersIfInteresting(I); return false; } -- cgit v1.2.3