X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FIVUsers.cpp;h=e0c5d8fa5f5a6d8c008892d99c152b39412abed3;hb=33624191afee63657cfbc68be041299060ee59d2;hp=e2b67e8365e44efb8d42cf69487f17cf573ac050;hpb=1f74590e9d1b9cf0f1f81a156efea73f76546e05;p=oota-llvm.git diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp index e2b67e8365e..e0c5d8fa5f5 100644 --- a/lib/Analysis/IVUsers.cpp +++ b/lib/Analysis/IVUsers.cpp @@ -12,24 +12,36 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "iv-users" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/CodeMetrics.h" #include "llvm/Analysis/IVUsers.h" -#include "llvm/Constants.h" -#include "llvm/Instructions.h" -#include "llvm/Type.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/Assembly/AsmAnnotationWriter.h" -#include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/Type.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include using namespace llvm; +#define DEBUG_TYPE "iv-users" + char IVUsers::ID = 0; -INITIALIZE_PASS(IVUsers, "iv-users", "Induction Variable Users", false, true); +INITIALIZE_PASS_BEGIN(IVUsers, "iv-users", + "Induction Variable Users", false, true) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) +INITIALIZE_PASS_END(IVUsers, "iv-users", + "Induction Variable Users", false, true) Pass *llvm::createIVUsersPass() { return new IVUsers(); @@ -38,66 +50,131 @@ Pass *llvm::createIVUsersPass() { /// 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) { - // Anything loop-invariant is interesting. - if (!isa(S) && S->isLoopInvariant(L)) - return true; - +static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L, + ScalarEvolution *SE, LoopInfo *LI) { // 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. + // Keep things simple. Don't touch loop-variant strides unless they're + // only used outside the loop and we can simplify them. if (AR->getLoop() == L) - return AR->isAffine() || !L->contains(I); - // Otherwise recurse to see if the start value is interesting. - return isInteresting(AR->getStart(), I, L); + return AR->isAffine() || + (!L->contains(I) && + SE->getSCEVAtScope(AR, LI->getLoopFor(I->getParent())) != AR); + // 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, LI) && + !isInteresting(AR->getStepRecurrence(*SE), I, L, SE, LI); } - // An add is interesting if any of its operands is. + // 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)) - return true; - return false; + if (isInteresting(*OI, I, L, SE, LI)) { + if (AnyInterestingYet) + return false; + AnyInterestingYet = true; + } + return AnyInterestingYet; } // Nothing else is interesting here. return false; } -/// AddUsersIfInteresting - Inspect the specified instruction. If it is a +/// Return true if all loop headers that dominate this block are in simplified +/// form. +static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT, + const LoopInfo *LI, + SmallPtrSetImpl &SimpleLoopNests) { + 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 the domtree walk reaches a loop with no preheader, return false. + if (!DomLoop->isLoopSimplifyForm()) + return false; + // If we have already checked this loop nest, stop checking. + if (SimpleLoopNests.count(DomLoop)) + break; + // 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) + SimpleLoopNests.insert(NearestLoop); + 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::AddUsersIfInteresting(Instruction *I) { +bool IVUsers::AddUsersImpl(Instruction *I, + SmallPtrSetImpl &SimpleLoopNests) { + const DataLayout &DL = I->getModule()->getDataLayout(); + + // Add this IV user to the Processed set before returning false to ensure that + // all IV users are members of the set. See IVUsers::isIVUserOrOperand. + if (!Processed.insert(I).second) + return true; // Instruction already handled. + if (!SE->isSCEVable(I->getType())) return false; // Void and FP expressions cannot be reduced. + // IVUsers is used by LSR which assumes that all SCEV expressions are safe to + // pass to SCEVExpander. Expressions are not safe to expand if they represent + // operations that are not safe to speculate, namely integer division. + if (!isa(I) && !isSafeToSpeculativelyExecute(I)) + return false; + // LSR is not APInt clean, do not touch integers bigger than 64-bits. - if (SE->getTypeSizeInBits(I->getType()) > 64) + // Also avoid creating IVs of non-native types. For example, we don't want a + // 64-bit IV in 32-bit code just because the loop has one 64-bit cast. + uint64_t Width = SE->getTypeSizeInBits(I->getType()); + if (Width > 64 || !DL.isLegalInteger(Width)) return false; - if (!Processed.insert(I)) - return true; // Instruction already handled. + // Don't attempt to promote ephemeral values to indvars. They will be removed + // later anyway. + if (EphValues.count(I)) + return false; // Get the symbolic expression for this instruction. const SCEV *ISE = SE->getSCEV(I); // If we've come to an uninteresting expression, stop the traversal and // call this a user. - if (!isInteresting(ISE, I, L)) + if (!isInteresting(ISE, I, L, SE, LI)) return false; 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)) + for (Use &U : I->uses()) { + Instruction *User = cast(U.getUser()); + if (!UniqueUsers.insert(User).second) continue; // Do not infinitely recurse on PHI nodes. 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 (!isSimplifiedLoopNest(UseBB, DT, LI, SimpleLoopNests)) + 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 @@ -107,13 +184,12 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) { bool AddUserToIVUsers = false; if (LI->getLoopFor(User->getParent()) != L) { if (isa(User) || Processed.count(User) || - !AddUsersIfInteresting(User)) { + !AddUsersImpl(User, SimpleLoopNests)) { DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n' << " OF SCEV: " << *ISE << '\n'); AddUserToIVUsers = true; } - } else if (Processed.count(User) || - !AddUsersIfInteresting(User)) { + } else if (Processed.count(User) || !AddUsersImpl(User, SimpleLoopNests)) { DEBUG(dbgs() << "FOUND USER: " << *User << '\n' << " OF SCEV: " << *ISE << '\n'); AddUserToIVUsers = true; @@ -121,84 +197,125 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) { 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. + IVStrideUse &NewUse = AddUser(User, I); + // Autodetect the post-inc loop set, populating NewUse.PostIncLoops. + // The regular return value here is discarded; instead of recording + // it, we just recompute it when we need it. + const SCEV *OriginalISE = ISE; ISE = TransformForPostIncUse(NormalizeAutodetect, ISE, User, I, NewUse.PostIncLoops, *SE, *DT); - DEBUG(dbgs() << " NORMALIZED TO: " << *ISE << '\n'); + + // PostIncNormalization effectively simplifies the expression under + // pre-increment assumptions. Those assumptions (no wrapping) might not + // hold for the post-inc value. Catch such cases by making sure the + // transformation is invertible. + if (OriginalISE != ISE) { + const SCEV *DenormalizedISE = + TransformForPostIncUse(Denormalize, ISE, User, I, + NewUse.PostIncLoops, *SE, *DT); + + // If we normalized the expression, but denormalization doesn't give the + // original one, discard this user. + if (OriginalISE != DenormalizedISE) { + DEBUG(dbgs() << " DISCARDING (NORMALIZATION ISN'T INVERTIBLE): " + << *ISE << '\n'); + IVUses.pop_back(); + return false; + } + } + DEBUG(if (SE->getSCEV(I) != ISE) + dbgs() << " NORMALIZED TO: " << *ISE << '\n'); } } return true; } +bool IVUsers::AddUsersIfInteresting(Instruction *I) { + // SCEVExpander can only handle users that are dominated by simplified loop + // entries. Keep track of all loops that are only dominated by other simple + // loops so we don't traverse the domtree for each user. + SmallPtrSet SimpleLoopNests; + + return AddUsersImpl(I, SimpleLoopNests); +} + IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) { IVUses.push_back(new IVStrideUse(this, User, Operand)); return IVUses.back(); } IVUsers::IVUsers() - : LoopPass(&ID) { + : LoopPass(ID) { + initializeIVUsersPass(*PassRegistry::getPassRegistry()); } void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); - AU.addRequired(); - AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { L = l; - LI = &getAnalysis(); - DT = &getAnalysis(); - SE = &getAnalysis(); + AC = &getAnalysis().getAssumptionCache( + *L->getHeader()->getParent()); + LI = &getAnalysis().getLoopInfo(); + DT = &getAnalysis().getDomTree(); + SE = &getAnalysis().getSE(); + + // Collect ephemeral values so that AddUsersIfInteresting skips them. + EphValues.clear(); + CodeMetrics::collectEphemeralValues(L, AC, EphValues); // Find all uses of induction variables in this loop, and categorize // 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); + (void)AddUsersIfInteresting(&*I); return false; } void IVUsers::print(raw_ostream &OS, const Module *M) const { OS << "IV Users for loop "; - WriteAsOperand(OS, L->getHeader(), false); + L->getHeader()->printAsOperand(OS, false); if (SE->hasLoopInvariantBackedgeTakenCount(L)) { OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L); } OS << ":\n"; - // Use a default AssemblyAnnotationWriter to suppress the default info - // comments, which aren't relevant here. - AssemblyAnnotationWriter Annotator; for (ilist::const_iterator UI = IVUses.begin(), E = IVUses.end(); UI != E; ++UI) { OS << " "; - WriteAsOperand(OS, UI->getOperandValToReplace(), false); + UI->getOperandValToReplace()->printAsOperand(OS, false); OS << " = " << *getReplacementExpr(*UI); for (PostIncLoopSet::const_iterator I = UI->PostIncLoops.begin(), E = UI->PostIncLoops.end(); I != E; ++I) { OS << " (post-inc with loop "; - WriteAsOperand(OS, (*I)->getHeader(), false); + (*I)->getHeader()->printAsOperand(OS, false); OS << ")"; } OS << " in "; - UI->getUser()->print(OS, &Annotator); + if (UI->getUser()) + UI->getUser()->print(OS); + else + OS << "Printing User"; OS << '\n'; } } +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void IVUsers::dump() const { print(dbgs()); } +#endif void IVUsers::releaseMemory() { Processed.clear(); @@ -232,16 +349,16 @@ static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) { I != E; ++I) if (const SCEVAddRecExpr *AR = findAddRecForLoop(*I, L)) return AR; - return 0; + return nullptr; } - return 0; + return nullptr; } const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const { if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L)) return AR->getStepRecurrence(*SE); - return 0; + return nullptr; } void IVStrideUse::transformToPostInc(const Loop *L) { @@ -250,6 +367,7 @@ void IVStrideUse::transformToPostInc(const Loop *L) { void IVStrideUse::deleted() { // Remove this user from the list. + Parent->Processed.erase(this->getUser()); Parent->IVUses.erase(this); // this now dangles! }