X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLoopInfo.cpp;h=46c0eaabe1a3102e59ecc1b18f430800944b7dd4;hb=66b380b6b60f96816346fa50f049b5463512387f;hp=f1f02a8c0a11c62b9300f219d013b4684e2b74c2;hpb=ee21b6f7b41e3fc19031f6d410b2ebe6a1a2f361;p=oota-llvm.git diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp index f1f02a8c0a1..46c0eaabe1a 100644 --- a/lib/Analysis/LoopInfo.cpp +++ b/lib/Analysis/LoopInfo.cpp @@ -17,15 +17,14 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SmallPtrSet.h" -#include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopInfoImpl.h" #include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/ValueTracking.h" -#include "llvm/Assembly/Writer.h" +#include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Metadata.h" -#include "llvm/Support/CFG.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include @@ -47,11 +46,11 @@ VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), char LoopInfo::ID = 0; INITIALIZE_PASS_BEGIN(LoopInfo, "loops", "Natural Loop Information", true, true) -INITIALIZE_PASS_DEPENDENCY(DominatorTree) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_END(LoopInfo, "loops", "Natural Loop Information", true, true) // Loop identifier metadata name. -static const char* LoopMDName = "llvm.loop"; +static const char *const LoopMDName = "llvm.loop"; //===----------------------------------------------------------------------===// // Loop implementation @@ -142,21 +141,21 @@ bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, PHINode *Loop::getCanonicalInductionVariable() const { BasicBlock *H = getHeader(); - BasicBlock *Incoming = 0, *Backedge = 0; + BasicBlock *Incoming = nullptr, *Backedge = nullptr; pred_iterator PI = pred_begin(H); assert(PI != pred_end(H) && "Loop must have at least one backedge!"); Backedge = *PI++; - if (PI == pred_end(H)) return 0; // dead loop + if (PI == pred_end(H)) return nullptr; // dead loop Incoming = *PI++; - if (PI != pred_end(H)) return 0; // multiple backedges? + if (PI != pred_end(H)) return nullptr; // multiple backedges? if (contains(Incoming)) { if (contains(Backedge)) - return 0; + return nullptr; std::swap(Incoming, Backedge); } else if (!contains(Backedge)) - return 0; + return nullptr; // Loop over all of the PHI nodes, looking for a canonical indvar. for (BasicBlock::iterator I = H->begin(); isa(I); ++I) { @@ -172,31 +171,26 @@ PHINode *Loop::getCanonicalInductionVariable() const { if (CI->equalsInt(1)) return PN; } - return 0; + return nullptr; } /// isLCSSAForm - Return true if the Loop is in LCSSA form bool Loop::isLCSSAForm(DominatorTree &DT) const { - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallPtrSet LoopBBs(block_begin(), block_end()); - for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { BasicBlock *BB = *BI; for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; - ++UI) { - User *U = *UI; - BasicBlock *UserBB = cast(U)->getParent(); - if (PHINode *P = dyn_cast(U)) - UserBB = P->getIncomingBlock(UI); + for (Use &U : I->uses()) { + Instruction *UI = cast(U.getUser()); + BasicBlock *UserBB = UI->getParent(); + if (PHINode *P = dyn_cast(UI)) + UserBB = P->getIncomingBlock(U); // Check the current block, as a fast-path, before checking whether // the use is anywhere in the loop. Most values are used in the same // block they are defined in. Also, blocks not reachable from the // entry are special; uses in them don't need to go through PHIs. if (UserBB != BB && - !LoopBBs.count(UserBB) && + !contains(UserBB) && DT.isReachableFromEntry(UserBB)) return false; } @@ -220,16 +214,16 @@ bool Loop::isSafeToClone() const { // Return false if any loop blocks contain indirectbrs, or there are any calls // to noduplicate functions. for (Loop::block_iterator I = block_begin(), E = block_end(); I != E; ++I) { - if (isa((*I)->getTerminator())) { + if (isa((*I)->getTerminator())) return false; - } else if (const InvokeInst *II = dyn_cast((*I)->getTerminator())) { - if (II->hasFnAttr(Attribute::NoDuplicate)) + + if (const InvokeInst *II = dyn_cast((*I)->getTerminator())) + if (II->cannotDuplicate()) return false; - } for (BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end(); BI != BE; ++BI) { if (const CallInst *CI = dyn_cast(BI)) { - if (CI->hasFnAttr(Attribute::NoDuplicate)) + if (CI->cannotDuplicate()) return false; } } @@ -238,7 +232,7 @@ bool Loop::isSafeToClone() const { } MDNode *Loop::getLoopID() const { - MDNode *LoopID = 0; + MDNode *LoopID = nullptr; if (isLoopSimplifyForm()) { LoopID = getLoopLatch()->getTerminator()->getMetadata(LoopMDName); } else { @@ -247,7 +241,7 @@ MDNode *Loop::getLoopID() const { BasicBlock *H = getHeader(); for (block_iterator I = block_begin(), IE = block_end(); I != IE; ++I) { TerminatorInst *TI = (*I)->getTerminator(); - MDNode *MD = 0; + MDNode *MD = nullptr; // Check if this terminator branches to the loop header. for (unsigned i = 0, ie = TI->getNumSuccessors(); i != ie; ++i) { @@ -257,17 +251,17 @@ MDNode *Loop::getLoopID() const { } } if (!MD) - return 0; + return nullptr; if (!LoopID) LoopID = MD; else if (MD != LoopID) - return 0; + return nullptr; } } if (!LoopID || LoopID->getNumOperands() == 0 || LoopID->getOperand(0) != LoopID) - return 0; + return nullptr; return LoopID; } @@ -309,15 +303,15 @@ bool Loop::isAnnotatedParallel() const { if (!II->mayReadOrWriteMemory()) continue; - if (!II->getMetadata("llvm.mem.parallel_loop_access")) - return false; - // The memory instruction can refer to the loop identifier metadata // directly or indirectly through another list metadata (in case of // nested parallel loops). The loop identifier metadata refers to // itself so we can check both cases with the same routine. - MDNode *loopIdMD = - dyn_cast(II->getMetadata("llvm.mem.parallel_loop_access")); + MDNode *loopIdMD = II->getMetadata("llvm.mem.parallel_loop_access"); + + if (!loopIdMD) + return false; + bool loopIdMDFound = false; for (unsigned i = 0, e = loopIdMD->getNumOperands(); i < e; ++i) { if (loopIdMD->getOperand(i) == desiredLoopIdMetadata) { @@ -337,9 +331,6 @@ bool Loop::isAnnotatedParallel() const { /// hasDedicatedExits - Return true if no exit block for the loop /// has a predecessor that is outside the loop. bool Loop::hasDedicatedExits() const { - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallPtrSet LoopBBs(block_begin(), block_end()); // Each predecessor of each exit block of a normal loop is contained // within the loop. SmallVector ExitBlocks; @@ -347,7 +338,7 @@ bool Loop::hasDedicatedExits() const { for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) for (pred_iterator PI = pred_begin(ExitBlocks[i]), PE = pred_end(ExitBlocks[i]); PI != PE; ++PI) - if (!LoopBBs.count(*PI)) + if (!contains(*PI)) return false; // All the requirements are met. return true; @@ -362,11 +353,6 @@ Loop::getUniqueExitBlocks(SmallVectorImpl &ExitBlocks) const { assert(hasDedicatedExits() && "getUniqueExitBlocks assumes the loop has canonical form exits!"); - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallVector LoopBBs(block_begin(), block_end()); - std::sort(LoopBBs.begin(), LoopBBs.end()); - SmallVector switchExitBlocks; for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { @@ -376,7 +362,7 @@ Loop::getUniqueExitBlocks(SmallVectorImpl &ExitBlocks) const { for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I) { // If block is inside the loop then it is not a exit block. - if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) + if (contains(*I)) continue; pred_iterator PI = pred_begin(*I); @@ -416,7 +402,7 @@ BasicBlock *Loop::getUniqueExitBlock() const { getUniqueExitBlocks(UniqueExitBlocks); if (UniqueExitBlocks.size() == 1) return UniqueExitBlocks[0]; - return 0; + return nullptr; } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) @@ -540,8 +526,8 @@ void UnloopUpdater::removeBlocksFromAncestors() { /// nested within unloop. void UnloopUpdater::updateSubloopParents() { while (!Unloop->empty()) { - Loop *Subloop = *llvm::prior(Unloop->end()); - Unloop->removeChildLoop(llvm::prior(Unloop->end())); + Loop *Subloop = *std::prev(Unloop->end()); + Unloop->removeChildLoop(std::prev(Unloop->end())); assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop"); if (Loop *Parent = SubloopParents[Subloop]) @@ -562,7 +548,7 @@ Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { // is considered uninitialized. Loop *NearLoop = BBLoop; - Loop *Subloop = 0; + Loop *Subloop = nullptr; if (NearLoop != Unloop && Unloop->contains(NearLoop)) { Subloop = NearLoop; // Find the subloop ancestor that is directly contained within Unloop. @@ -578,7 +564,7 @@ Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { succ_iterator I = succ_begin(BB), E = succ_end(BB); if (I == E) { assert(!Subloop && "subloop blocks must have a successor"); - NearLoop = 0; // unloop blocks may now exit the function. + NearLoop = nullptr; // unloop blocks may now exit the function. } for (; I != E; ++I) { if (*I == BB) @@ -626,7 +612,7 @@ Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { // bool LoopInfo::runOnFunction(Function &) { releaseMemory(); - LI.Analyze(getAnalysis().getBase()); + LI.Analyze(getAnalysis().getDomTree()); return false; } @@ -651,7 +637,7 @@ void LoopInfo::updateUnloop(Loop *Unloop) { // Blocks no longer have a parent but are still referenced by Unloop until // the Unloop object is deleted. - LI.changeLoopFor(*I, 0); + LI.changeLoopFor(*I, nullptr); } // Remove the loop from the top-level LoopInfo object. @@ -665,7 +651,7 @@ void LoopInfo::updateUnloop(Loop *Unloop) { // Move all of the subloops to the top-level. while (!Unloop->empty()) - LI.addTopLevelLoop(Unloop->removeChildLoop(llvm::prior(Unloop->end()))); + LI.addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end()))); return; } @@ -717,7 +703,7 @@ void LoopInfo::verifyAnalysis() const { void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - AU.addRequired(); + AU.addRequired(); } void LoopInfo::print(raw_ostream &OS, const Module*) const {