X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FIVUsers.cpp;h=b88b2496b875e76d89d89e3f05f8c325dd7e128c;hb=9584e07a9cf5261011e70951a3e6286d54643bb1;hp=b33e2cb9999e86236494f60ac2e9a99fb08a2913;hpb=0b8c9a80f20772c3793201ab5b251d3520b9cea3;p=oota-llvm.git diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp index b33e2cb9999..b88b2496b87 100644 --- a/lib/Analysis/IVUsers.cpp +++ b/lib/Analysis/IVUsers.cpp @@ -12,29 +12,30 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "iv-users" #include "llvm/Analysis/IVUsers.h" #include "llvm/ADT/STLExtras.h" -#include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ValueTracking.h" -#include "llvm/Assembly/Writer.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_BEGIN(IVUsers, "iv-users", "Induction Variable Users", false, true) -INITIALIZE_PASS_DEPENDENCY(LoopInfo) -INITIALIZE_PASS_DEPENDENCY(DominatorTree) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) INITIALIZE_PASS_END(IVUsers, "iv-users", "Induction Variable Users", false, true) @@ -84,8 +85,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(); @@ -112,10 +113,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())) @@ -124,14 +127,14 @@ 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, TD)) + 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 || (TD && !TD->isLegalInteger(Width))) + if (Width > 64 || !DL.isLegalInteger(Width)) return false; // Get the symbolic expression for this instruction. @@ -143,10 +146,9 @@ bool IVUsers::AddUsersImpl(Instruction *I, 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. @@ -158,7 +160,7 @@ bool IVUsers::AddUsersImpl(Instruction *I, BasicBlock *UseBB = User->getParent(); // A phi's use is live out of its predecessor block. if (PHINode *PHI = dyn_cast(User)) { - unsigned OperandNo = UI.getOperandNo(); + unsigned OperandNo = U.getOperandNo(); unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo); UseBB = PHI->getIncomingBlock(ValNo); } @@ -187,15 +189,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'); } @@ -223,8 +244,8 @@ IVUsers::IVUsers() } void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); - AU.addRequired(); + AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.setPreservesAll(); } @@ -232,10 +253,9 @@ void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const { bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { L = l; - LI = &getAnalysis(); - DT = &getAnalysis(); + LI = &getAnalysis().getLoopInfo(); + DT = &getAnalysis().getDomTree(); SE = &getAnalysis(); - TD = getAnalysisIfAvailable(); // 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 @@ -248,7 +268,7 @@ bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { 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); @@ -258,17 +278,20 @@ void IVUsers::print(raw_ostream &OS, const Module *M) const { 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); + if (UI->getUser()) + UI->getUser()->print(OS); + else + OS << "Printing User"; OS << '\n'; } } @@ -311,16 +334,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) {