X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLoopInfo.cpp;h=b1f62c437326ab071ee29ab3e82cbb73f1e5d501;hb=92602ea18e3d3b1fb6b780a2aa0301004f2c7285;hp=af35462544e7bf9848ff6c769226048181d2e687;hpb=c12d9b9dfbba233c847f74facf3c0deafae4523f;p=oota-llvm.git diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp index af35462544e..b1f62c43732 100644 --- a/lib/Analysis/LoopInfo.cpp +++ b/lib/Analysis/LoopInfo.cpp @@ -15,19 +15,26 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LoopInfo.h" -#include "llvm/Constants.h" -#include "llvm/Instructions.h" -#include "llvm/Analysis/Dominators.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/LoopInfoImpl.h" #include "llvm/Analysis/LoopIterator.h" -#include "llvm/Assembly/Writer.h" -#include "llvm/Support/CFG.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Metadata.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" -#include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/SmallPtrSet.h" #include using namespace llvm; +// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops. +template class llvm::LoopBase; +template class llvm::LoopInfoBase; + // Always verify loopinfo if expensive checking is enabled. #ifdef XDEBUG static bool VerifyLoopInfo = true; @@ -40,9 +47,12 @@ 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 *const LoopMDName = "llvm.loop"; + //===----------------------------------------------------------------------===// // Loop implementation // @@ -95,10 +105,13 @@ bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, // Test if the value is already loop-invariant. if (isLoopInvariant(I)) return true; - if (!I->isSafeToSpeculativelyExecute()) + if (!isSafeToSpeculativelyExecute(I)) return false; if (I->mayReadFromMemory()) return false; + // The landingpad instruction is immobile. + if (isa(I)) + return false; // Determine the insertion point, unless one was given. if (!InsertPt) { BasicBlock *Preheader = getLoopPreheader(); @@ -129,21 +142,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) { @@ -159,124 +172,26 @@ PHINode *Loop::getCanonicalInductionVariable() const { if (CI->equalsInt(1)) return PN; } - return 0; -} - -/// getTripCount - Return a loop-invariant LLVM value indicating the number of -/// times the loop will be executed. Note that this means that the backedge -/// of the loop executes N-1 times. If the trip-count cannot be determined, -/// this returns null. -/// -/// The IndVarSimplify pass transforms loops to have a form that this -/// function easily understands. -/// -Value *Loop::getTripCount() const { - // Canonical loops will end with a 'cmp ne I, V', where I is the incremented - // canonical induction variable and V is the trip count of the loop. - PHINode *IV = getCanonicalInductionVariable(); - if (IV == 0 || IV->getNumIncomingValues() != 2) return 0; - - bool P0InLoop = contains(IV->getIncomingBlock(0)); - Value *Inc = IV->getIncomingValue(!P0InLoop); - BasicBlock *BackedgeBlock = IV->getIncomingBlock(!P0InLoop); - - if (BranchInst *BI = dyn_cast(BackedgeBlock->getTerminator())) - if (BI->isConditional()) { - if (ICmpInst *ICI = dyn_cast(BI->getCondition())) { - if (ICI->getOperand(0) == Inc) { - if (BI->getSuccessor(0) == getHeader()) { - if (ICI->getPredicate() == ICmpInst::ICMP_NE) - return ICI->getOperand(1); - } else if (ICI->getPredicate() == ICmpInst::ICMP_EQ) { - return ICI->getOperand(1); - } - } - } - } - - return 0; -} - -/// getSmallConstantTripCount - Returns the trip count of this loop as a -/// normal unsigned value, if possible. Returns 0 if the trip count is unknown -/// or not constant. Will also return 0 if the trip count is very large -/// (>= 2^32) -unsigned Loop::getSmallConstantTripCount() const { - Value* TripCount = this->getTripCount(); - if (TripCount) { - if (ConstantInt *TripCountC = dyn_cast(TripCount)) { - // Guard against huge trip counts. - if (TripCountC->getValue().getActiveBits() <= 32) { - return (unsigned)TripCountC->getZExtValue(); - } - } - } - return 0; -} - -/// getSmallConstantTripMultiple - Returns the largest constant divisor of the -/// trip count of this loop as a normal unsigned value, if possible. This -/// means that the actual trip count is always a multiple of the returned -/// value (don't forget the trip count could very well be zero as well!). -/// -/// Returns 1 if the trip count is unknown or not guaranteed to be the -/// multiple of a constant (which is also the case if the trip count is simply -/// constant, use getSmallConstantTripCount for that case), Will also return 1 -/// if the trip count is very large (>= 2^32). -unsigned Loop::getSmallConstantTripMultiple() const { - Value* TripCount = this->getTripCount(); - // This will hold the ConstantInt result, if any - ConstantInt *Result = NULL; - if (TripCount) { - // See if the trip count is constant itself - Result = dyn_cast(TripCount); - // if not, see if it is a multiplication - if (!Result) - if (BinaryOperator *BO = dyn_cast(TripCount)) { - switch (BO->getOpcode()) { - case BinaryOperator::Mul: - Result = dyn_cast(BO->getOperand(1)); - break; - case BinaryOperator::Shl: - if (ConstantInt *CI = dyn_cast(BO->getOperand(1))) - if (CI->getValue().getActiveBits() <= 5) - return 1u << CI->getZExtValue(); - break; - default: - break; - } - } - } - // Guard against huge trip counts. - if (Result && Result->getValue().getActiveBits() <= 32) { - return (unsigned)Result->getZExtValue(); - } else { - return 1; - } + 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; } @@ -294,12 +209,130 @@ bool Loop::isLoopSimplifyForm() const { return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); } +/// isSafeToClone - Return true if the loop body is safe to clone in practice. +/// Routines that reform the loop CFG and split edges often fail on indirectbr. +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())) + return false; + + 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->cannotDuplicate()) + return false; + } + } + } + return true; +} + +MDNode *Loop::getLoopID() const { + MDNode *LoopID = nullptr; + if (isLoopSimplifyForm()) { + LoopID = getLoopLatch()->getTerminator()->getMetadata(LoopMDName); + } else { + // Go through each predecessor of the loop header and check the + // terminator for the metadata. + BasicBlock *H = getHeader(); + for (block_iterator I = block_begin(), IE = block_end(); I != IE; ++I) { + TerminatorInst *TI = (*I)->getTerminator(); + MDNode *MD = nullptr; + + // Check if this terminator branches to the loop header. + for (unsigned i = 0, ie = TI->getNumSuccessors(); i != ie; ++i) { + if (TI->getSuccessor(i) == H) { + MD = TI->getMetadata(LoopMDName); + break; + } + } + if (!MD) + return nullptr; + + if (!LoopID) + LoopID = MD; + else if (MD != LoopID) + return nullptr; + } + } + if (!LoopID || LoopID->getNumOperands() == 0 || + LoopID->getOperand(0) != LoopID) + return nullptr; + return LoopID; +} + +void Loop::setLoopID(MDNode *LoopID) const { + assert(LoopID && "Loop ID should not be null"); + assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand"); + assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself"); + + if (isLoopSimplifyForm()) { + getLoopLatch()->getTerminator()->setMetadata(LoopMDName, LoopID); + return; + } + + BasicBlock *H = getHeader(); + for (block_iterator I = block_begin(), IE = block_end(); I != IE; ++I) { + TerminatorInst *TI = (*I)->getTerminator(); + for (unsigned i = 0, ie = TI->getNumSuccessors(); i != ie; ++i) { + if (TI->getSuccessor(i) == H) + TI->setMetadata(LoopMDName, LoopID); + } + } +} + +bool Loop::isAnnotatedParallel() const { + MDNode *desiredLoopIdMetadata = getLoopID(); + + if (!desiredLoopIdMetadata) + return false; + + // The loop branch contains the parallel loop metadata. In order to ensure + // that any parallel-loop-unaware optimization pass hasn't added loop-carried + // dependencies (thus converted the loop back to a sequential loop), check + // that all the memory instructions in the loop contain parallelism metadata + // that point to the same unique "loop id metadata" the loop branch does. + for (block_iterator BB = block_begin(), BE = block_end(); BB != BE; ++BB) { + for (BasicBlock::iterator II = (*BB)->begin(), EE = (*BB)->end(); + II != EE; II++) { + + if (!II->mayReadOrWriteMemory()) + continue; + + // 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 = + II->getMetadata(LLVMContext::MD_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) { + loopIdMDFound = true; + break; + } + } + + if (!loopIdMDFound) + return false; + } + } + return true; +} + + /// 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; @@ -307,7 +340,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; @@ -322,11 +355,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) { @@ -336,7 +364,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); @@ -376,17 +404,20 @@ BasicBlock *Loop::getUniqueExitBlock() const { getUniqueExitBlocks(UniqueExitBlocks); if (UniqueExitBlocks.size() == 1) return UniqueExitBlocks[0]; - return 0; + return nullptr; } +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void Loop::dump() const { print(dbgs()); } +#endif //===----------------------------------------------------------------------===// // UnloopUpdater implementation // +namespace { /// Find the new parent loop for all blocks within the "unloop" whose last /// backedges has just been removed. class UnloopUpdater { @@ -418,6 +449,7 @@ public: protected: Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop); }; +} // end anonymous namespace /// updateBlockParents - Update the parent loop for all blocks that are directly /// contained within the original "unloop". @@ -472,21 +504,19 @@ void UnloopUpdater::updateBlockParents() { /// removeBlocksFromAncestors - Remove unloop's blocks from all ancestors below /// their new parents. void UnloopUpdater::removeBlocksFromAncestors() { - // Remove unloop's blocks from all ancestors below their new parents. + // Remove all unloop's blocks (including those in nested subloops) from + // ancestors below the new parent loop. for (Loop::block_iterator BI = Unloop->block_begin(), BE = Unloop->block_end(); BI != BE; ++BI) { - Loop *NewParent = LI->getLoopFor(*BI); - // If this block is an immediate subloop, remove all blocks (including - // nested subloops) from ancestors below the new parent loop. - // Otherwise, if this block is in a nested subloop, skip it. - if (SubloopParents.count(NewParent)) - NewParent = SubloopParents[NewParent]; - else if (Unloop->contains(NewParent)) - continue; - + Loop *OuterParent = LI->getLoopFor(*BI); + if (Unloop->contains(OuterParent)) { + while (OuterParent->getParentLoop() != Unloop) + OuterParent = OuterParent->getParentLoop(); + OuterParent = SubloopParents[OuterParent]; + } // Remove blocks from former Ancestors except Unloop itself which will be // deleted. - for (Loop *OldParent = Unloop->getParentLoop(); OldParent != NewParent; + for (Loop *OldParent = Unloop->getParentLoop(); OldParent != OuterParent; OldParent = OldParent->getParentLoop()) { assert(OldParent && "new loop is not an ancestor of the original"); OldParent->removeBlockFromLoop(*BI); @@ -498,12 +528,14 @@ 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 (SubloopParents[Subloop]) - SubloopParents[Subloop]->addChildLoop(Subloop); + if (Loop *Parent = SubloopParents[Subloop]) + Parent->addChildLoop(Subloop); + else + LI->addTopLevelLoop(Subloop); } } @@ -518,7 +550,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. @@ -527,15 +559,14 @@ Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { assert(Subloop && "subloop is not an ancestor of the original loop"); } // Get the current nearest parent of the Subloop exits, initially Unloop. - if (!SubloopParents.count(Subloop)) - SubloopParents[Subloop] = Unloop; - NearLoop = SubloopParents[Subloop]; + NearLoop = + SubloopParents.insert(std::make_pair(Subloop, Unloop)).first->second; } 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) @@ -583,7 +614,7 @@ Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { // bool LoopInfo::runOnFunction(Function &) { releaseMemory(); - LI.Calculate(getAnalysis().getBase()); // Update + LI.Analyze(getAnalysis().getDomTree()); return false; } @@ -608,12 +639,12 @@ 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. - for (LoopInfo::iterator I = LI.begin(), E = LI.end();; ++I) { - assert(I != E && "Couldn't find loop"); + for (LoopInfo::iterator I = LI.begin();; ++I) { + assert(I != LI.end() && "Couldn't find loop"); if (*I == Unloop) { LI.removeLoop(I); break; @@ -622,7 +653,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; } @@ -640,8 +671,8 @@ void LoopInfo::updateUnloop(Loop *Unloop) { // Remove unloop from its parent loop. Loop *ParentLoop = Unloop->getParentLoop(); - for (Loop::iterator I = ParentLoop->begin(), E = ParentLoop->end();; ++I) { - assert(I != E && "Couldn't find loop"); + for (Loop::iterator I = ParentLoop->begin();; ++I) { + assert(I != ParentLoop->end() && "Couldn't find loop"); if (*I == Unloop) { ParentLoop->removeChildLoop(I); break; @@ -658,17 +689,23 @@ void LoopInfo::verifyAnalysis() const { if (!VerifyLoopInfo) return; + DenseSet Loops; for (iterator I = begin(), E = end(); I != E; ++I) { assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); - (*I)->verifyLoopNest(); + (*I)->verifyLoopNest(&Loops); } - // TODO: check BBMap consistency. + // Verify that blocks are mapped to valid loops. + for (DenseMap::const_iterator I = LI.BBMap.begin(), + E = LI.BBMap.end(); I != E; ++I) { + assert(Loops.count(I->second) && "orphaned loop"); + assert(I->second->contains(I->first) && "orphaned block"); + } } void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - AU.addRequired(); + AU.addRequired(); } void LoopInfo::print(raw_ostream &OS, const Module*) const {