X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FAnalysis%2FIVUsers.cpp;h=e0c5d8fa5f5a6d8c008892d99c152b39412abed3;hp=7eade544578d5be0cbb2d94054ac59e2d2035a6a;hb=HEAD;hpb=36b699f2b139a30a2dfa4448223d6985b55daa8a diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp index 7eade544578..e0c5d8fa5f5 100644 --- a/lib/Analysis/IVUsers.cpp +++ b/lib/Analysis/IVUsers.cpp @@ -12,9 +12,10 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "iv-users" -#include "llvm/Analysis/IVUsers.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/CodeMetrics.h" +#include "llvm/Analysis/IVUsers.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ValueTracking.h" @@ -23,18 +24,22 @@ #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_BEGIN(IVUsers, "iv-users", "Induction Variable Users", false, true) -INITIALIZE_PASS_DEPENDENCY(LoopInfo) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) INITIALIZE_PASS_END(IVUsers, "iv-users", "Induction Variable Users", false, true) @@ -83,8 +88,8 @@ static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L, /// form. static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT, const LoopInfo *LI, - SmallPtrSet &SimpleLoopNests) { - Loop *NearestLoop = 0; + SmallPtrSetImpl &SimpleLoopNests) { + Loop *NearestLoop = nullptr; for (DomTreeNode *Rung = DT->getNode(BB); Rung; Rung = Rung->getIDom()) { BasicBlock *DomBB = Rung->getBlock(); @@ -111,10 +116,12 @@ static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT, /// reducible SCEV, recursively add its users to the IVUsesByStride set and /// return true. Otherwise, return false. bool IVUsers::AddUsersImpl(Instruction *I, - SmallPtrSet &SimpleLoopNests) { + 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)) + if (!Processed.insert(I).second) return true; // Instruction already handled. if (!SE->isSCEVable(I->getType())) @@ -123,14 +130,19 @@ bool IVUsers::AddUsersImpl(Instruction *I, // 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, DL)) + if (!isa(I) && !isSafeToSpeculativelyExecute(I)) return false; // LSR is not APInt clean, do not touch integers bigger than 64-bits. // 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 && !DL->isLegalInteger(Width))) + if (Width > 64 || !DL.isLegalInteger(Width)) + return false; + + // 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. @@ -144,7 +156,7 @@ bool IVUsers::AddUsersImpl(Instruction *I, SmallPtrSet UniqueUsers; for (Use &U : I->uses()) { Instruction *User = cast(U.getUser()); - if (!UniqueUsers.insert(User)) + if (!UniqueUsers.insert(User).second) continue; // Do not infinitely recurse on PHI nodes. @@ -185,15 +197,34 @@ bool IVUsers::AddUsersImpl(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(); + 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); + + // 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'); } @@ -221,26 +252,31 @@ IVUsers::IVUsers() } void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const { - 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(); + AC = &getAnalysis().getAssumptionCache( + *L->getHeader()->getParent()); + LI = &getAnalysis().getLoopInfo(); DT = &getAnalysis().getDomTree(); - SE = &getAnalysis(); - DataLayoutPass *DLP = getAnalysisIfAvailable(); - DL = DLP ? &DLP->getDataLayout() : 0; + 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; } @@ -267,7 +303,10 @@ void IVUsers::print(raw_ostream &OS, const Module *M) const { OS << ")"; } OS << " in "; - UI->getUser()->print(OS); + if (UI->getUser()) + UI->getUser()->print(OS); + else + OS << "Printing User"; OS << '\n'; } } @@ -310,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) {