X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FIVUsers.cpp;h=24655aa002c8aae6f78131ae3d3e13882b3d54c0;hb=ec7ee070369dd4074f7ad3ac4555ebb9421b8c1a;hp=308729fcf124a0dface5cccebb593fd47100480d;hpb=f9492288bbc51e5d34f19ba53dc778bc83be807c;p=oota-llvm.git diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp index 308729fcf12..24655aa002c 100644 --- a/lib/Analysis/IVUsers.cpp +++ b/lib/Analysis/IVUsers.cpp @@ -12,28 +12,29 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "iv-users" #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/ADT/STLExtras.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/Target/TargetData.h" -#include "llvm/Assembly/Writer.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/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(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) INITIALIZE_PASS_END(IVUsers, "iv-users", "Induction Variable Users", false, true) @@ -84,7 +85,7 @@ static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L, static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT, const LoopInfo *LI, SmallPtrSet &SimpleLoopNests) { - Loop *NearestLoop = 0; + Loop *NearestLoop = nullptr; for (DomTreeNode *Rung = DT->getNode(BB); Rung; Rung = Rung->getIDom()) { BasicBlock *DomBB = Rung->getBlock(); @@ -107,11 +108,11 @@ static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT, return true; } -/// AddUsersIfInteresting - Inspect the specified instruction. If it is a +/// 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, - SmallPtrSet &SimpleLoopNests) { +bool IVUsers::AddUsersImpl(Instruction *I, + SmallPtrSet &SimpleLoopNests) { // 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)) @@ -120,11 +121,17 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I, 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, DL)) + 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 && !DL->isLegalInteger(Width))) return false; // Get the symbolic expression for this instruction. @@ -136,9 +143,8 @@ bool IVUsers::AddUsersIfInteresting(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); + for (Use &U : I->uses()) { + Instruction *User = cast(U.getUser()); if (!UniqueUsers.insert(User)) continue; @@ -148,7 +154,14 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I, // Only consider IVUsers that are dominated by simplified loop // headers. Otherwise, SCEVExpander will crash. - if (!isSimplifiedLoopNest(User->getParent(), DT, LI, SimpleLoopNests)) + 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. @@ -160,13 +173,12 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I, bool AddUserToIVUsers = false; if (LI->getLoopFor(User->getParent()) != L) { if (isa(User) || Processed.count(User) || - !AddUsersIfInteresting(User, SimpleLoopNests)) { + !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, SimpleLoopNests)) { + } else if (Processed.count(User) || !AddUsersImpl(User, SimpleLoopNests)) { DEBUG(dbgs() << "FOUND USER: " << *User << '\n' << " OF SCEV: " << *ISE << '\n'); AddUserToIVUsers = true; @@ -174,15 +186,34 @@ 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(); + 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'); } @@ -190,6 +221,15 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I, 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(); @@ -202,7 +242,7 @@ IVUsers::IVUsers() void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); - AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.setPreservesAll(); } @@ -211,27 +251,23 @@ bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { L = l; LI = &getAnalysis(); - DT = &getAnalysis(); + DT = &getAnalysis().getDomTree(); SE = &getAnalysis(); - TD = getAnalysisIfAvailable(); - - // 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; + DataLayoutPass *DLP = getAnalysisIfAvailable(); + DL = DLP ? &DLP->getDataLayout() : nullptr; // 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, SimpleLoopNests); + (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); @@ -241,24 +277,29 @@ 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'; } } +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void IVUsers::dump() const { print(dbgs()); } +#endif void IVUsers::releaseMemory() { Processed.clear(); @@ -292,16 +333,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) {