X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FAnalysis%2FLoopInfo.cpp;h=0d0b193f5beae47042efe2576c2b7e33c3158587;hp=5939dea4c0de3f44cb02b711b92e8744eaae6ba5;hb=56e1394c8861ecdc551815ae875d2c3db2fa9cdb;hpb=45cfe545ec8177262dabc70580ce05feaa1c3880 diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp index 5939dea4c0d..0d0b193f5be 100644 --- a/lib/Analysis/LoopInfo.cpp +++ b/lib/Analysis/LoopInfo.cpp @@ -15,20 +15,42 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LoopInfo.h" -#include "llvm/Constants.h" -#include "llvm/Instructions.h" -#include "llvm/Analysis/Dominators.h" -#include "llvm/Assembly/Writer.h" -#include "llvm/Support/CFG.h" -#include "llvm/Support/Streams.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/LoopInfoImpl.h" +#include "llvm/Analysis/LoopIterator.h" +#include "llvm/Analysis/ValueTracking.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 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; +#else +static bool VerifyLoopInfo = false; +#endif +static cl::opt +VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), + cl::desc("Verify loop info (time consuming)")); + char LoopInfo::ID = 0; -static RegisterPass -X("loops", "Natural Loop Information", true, true); +INITIALIZE_PASS_BEGIN(LoopInfo, "loops", "Natural Loop Information", true, true) +INITIALIZE_PASS_DEPENDENCY(DominatorTree) +INITIALIZE_PASS_END(LoopInfo, "loops", "Natural Loop Information", true, true) + +// Loop identifier metadata name. +static const char *const LoopMDName = "llvm.loop"; //===----------------------------------------------------------------------===// // Loop implementation @@ -38,15 +60,18 @@ X("loops", "Natural Loop Information", true, true); /// bool Loop::isLoopInvariant(Value *V) const { if (Instruction *I = dyn_cast(V)) - return isLoopInvariant(I); + return !contains(I); return true; // All non-instructions are loop invariant } -/// isLoopInvariant - Return true if the specified instruction is -/// loop-invariant. -/// -bool Loop::isLoopInvariant(Instruction *I) const { - return !contains(I->getParent()); +/// hasLoopInvariantOperands - Return true if all the operands of the +/// specified instruction are loop invariant. +bool Loop::hasLoopInvariantOperands(Instruction *I) const { + for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) + if (!isLoopInvariant(I->getOperand(i))) + return false; + + return true; } /// makeLoopInvariant - If the given value is an instruciton inside of the @@ -79,10 +104,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(); @@ -95,6 +123,7 @@ bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) if (!makeLoopInvariant(I->getOperand(i), Changed, InsertPt)) return false; + // Hoist. I->moveBefore(InsertPt); Changed = true; @@ -113,14 +142,13 @@ PHINode *Loop::getCanonicalInductionVariable() const { BasicBlock *H = getHeader(); BasicBlock *Incoming = 0, *Backedge = 0; - typedef GraphTraits > InvBlockTraits; - InvBlockTraits::ChildIteratorType PI = InvBlockTraits::child_begin(H); - assert(PI != InvBlockTraits::child_end(H) && + pred_iterator PI = pred_begin(H); + assert(PI != pred_end(H) && "Loop must have at least one backedge!"); Backedge = *PI++; - if (PI == InvBlockTraits::child_end(H)) return 0; // dead loop + if (PI == pred_end(H)) return 0; // dead loop Incoming = *PI++; - if (PI != InvBlockTraits::child_end(H)) return 0; // multiple backedges? + if (PI != pred_end(H)) return 0; // multiple backedges? if (contains(Incoming)) { if (contains(Backedge)) @@ -146,142 +174,164 @@ PHINode *Loop::getCanonicalInductionVariable() const { return 0; } -/// getCanonicalInductionVariableIncrement - Return the LLVM value that holds -/// the canonical induction variable value for the "next" iteration of the -/// loop. This always succeeds if getCanonicalInductionVariable succeeds. -/// -Instruction *Loop::getCanonicalInductionVariableIncrement() const { - if (PHINode *PN = getCanonicalInductionVariable()) { - bool P1InLoop = contains(PN->getIncomingBlock(1)); - return cast(PN->getIncomingValue(P1InLoop)); - } - return 0; -} +/// isLCSSAForm - Return true if the Loop is in LCSSA form +bool Loop::isLCSSAForm(DominatorTree &DT) const { + 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); -/// 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. - Instruction *Inc = getCanonicalInductionVariableIncrement(); - if (Inc == 0) return 0; - PHINode *IV = cast(Inc->getOperand(0)); - - BasicBlock *BackedgeBlock = - IV->getIncomingBlock(contains(IV->getIncomingBlock(1))); - - 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); - } - } + // 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 && + !contains(UserBB) && + DT.isReachableFromEntry(UserBB)) + return false; } - } + } - return 0; + return true; +} + +/// isLoopSimplifyForm - Return true if the Loop is in the form that +/// the LoopSimplify form transforms loops to, which is sometimes called +/// normal form. +bool Loop::isLoopSimplifyForm() const { + // Normal-form loops have a preheader, a single backedge, and all of their + // exits have all their predecessors inside the loop. + return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); } -/// getSmallConstantTripCount - Returns the trip count of this loop as a -/// normal unsigned value, if possible. Returns 0 if the trip count is unknown -/// of 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(); +/// 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->hasFnAttr(Attribute::NoDuplicate)) + 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)) + return false; } } } - return 0; + return true; } -/// 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; - default: +MDNode *Loop::getLoopID() const { + MDNode *LoopID = 0; + 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 = 0; + + // 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 0; + + if (!LoopID) + LoopID = MD; + else if (MD != LoopID) + return 0; + } } - // Guard against huge trip counts. - if (Result && Result->getValue().getActiveBits() <= 32) { - return (unsigned)Result->getZExtValue(); - } else { - return 1; + if (!LoopID || LoopID->getNumOperands() == 0 || + LoopID->getOperand(0) != LoopID) + return 0; + 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); + } } } -/// isLCSSAForm - Return true if the Loop is in LCSSA form -bool Loop::isLCSSAForm() const { - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallPtrSet LoopBBs(block_begin(), block_end()); +bool Loop::isAnnotatedParallel() const { + MDNode *desiredLoopIdMetadata = getLoopID(); - 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) { - BasicBlock *UserBB = cast(*UI)->getParent(); - if (PHINode *P = dyn_cast(*UI)) { - UserBB = P->getIncomingBlock(UI); - } + if (!desiredLoopIdMetadata) + return false; - // Check the current block, as a fast-path. Most values are used in - // the same block they are defined in. - if (UserBB != BB && !LoopBBs.count(UserBB)) - 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("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) { + loopIdMDFound = true; + break; + } } - } + if (!loopIdMDFound) + return false; + } + } return true; } -/// isLoopSimplifyForm - Return true if the Loop is in the form that -/// the LoopSimplify form transforms loops to, which is sometimes called -/// normal form. -bool Loop::isLoopSimplifyForm() const { - // Normal-form loops have a preheader. - if (!getLoopPreheader()) - return false; - // Normal-form loops have a single backedge. - if (!getLoopLatch()) - return false; + +/// hasDedicatedExits - Return true if no exit block for the loop +/// has a predecessor that is outside the loop. +bool Loop::hasDedicatedExits() const { // Each predecessor of each exit block of a normal loop is contained // within the loop. SmallVector ExitBlocks; @@ -295,15 +345,363 @@ bool Loop::isLoopSimplifyForm() const { return true; } +/// getUniqueExitBlocks - Return all unique successor blocks of this loop. +/// These are the blocks _outside of the current loop_ which are branched to. +/// This assumes that loop exits are in canonical form. +/// +void +Loop::getUniqueExitBlocks(SmallVectorImpl &ExitBlocks) const { + assert(hasDedicatedExits() && + "getUniqueExitBlocks assumes the loop has canonical form exits!"); + + SmallVector switchExitBlocks; + + for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { + + BasicBlock *current = *BI; + switchExitBlocks.clear(); + + 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 (contains(*I)) + continue; + + pred_iterator PI = pred_begin(*I); + BasicBlock *firstPred = *PI; + + // If current basic block is this exit block's first predecessor + // then only insert exit block in to the output ExitBlocks vector. + // This ensures that same exit block is not inserted twice into + // ExitBlocks vector. + if (current != firstPred) + continue; + + // If a terminator has more then two successors, for example SwitchInst, + // then it is possible that there are multiple edges from current block + // to one exit block. + if (std::distance(succ_begin(current), succ_end(current)) <= 2) { + ExitBlocks.push_back(*I); + continue; + } + + // In case of multiple edges from current block to exit block, collect + // only one edge in ExitBlocks. Use switchExitBlocks to keep track of + // duplicate edges. + if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) + == switchExitBlocks.end()) { + switchExitBlocks.push_back(*I); + ExitBlocks.push_back(*I); + } + } + } +} + +/// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one +/// block, return that block. Otherwise return null. +BasicBlock *Loop::getUniqueExitBlock() const { + SmallVector UniqueExitBlocks; + getUniqueExitBlocks(UniqueExitBlocks); + if (UniqueExitBlocks.size() == 1) + return UniqueExitBlocks[0]; + return 0; +} + +#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 { + Loop *Unloop; + LoopInfo *LI; + + LoopBlocksDFS DFS; + + // Map unloop's immediate subloops to their nearest reachable parents. Nested + // loops within these subloops will not change parents. However, an immediate + // subloop's new parent will be the nearest loop reachable from either its own + // exits *or* any of its nested loop's exits. + DenseMap SubloopParents; + + // Flag the presence of an irreducible backedge whose destination is a block + // directly contained by the original unloop. + bool FoundIB; + +public: + UnloopUpdater(Loop *UL, LoopInfo *LInfo) : + Unloop(UL), LI(LInfo), DFS(UL), FoundIB(false) {} + + void updateBlockParents(); + + void removeBlocksFromAncestors(); + + void updateSubloopParents(); + +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". +void UnloopUpdater::updateBlockParents() { + if (Unloop->getNumBlocks()) { + // Perform a post order CFG traversal of all blocks within this loop, + // propagating the nearest loop from sucessors to predecessors. + LoopBlocksTraversal Traversal(DFS, LI); + for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), + POE = Traversal.end(); POI != POE; ++POI) { + + Loop *L = LI->getLoopFor(*POI); + Loop *NL = getNearestLoop(*POI, L); + + if (NL != L) { + // For reducible loops, NL is now an ancestor of Unloop. + assert((NL != Unloop && (!NL || NL->contains(Unloop))) && + "uninitialized successor"); + LI->changeLoopFor(*POI, NL); + } + else { + // Or the current block is part of a subloop, in which case its parent + // is unchanged. + assert((FoundIB || Unloop->contains(L)) && "uninitialized successor"); + } + } + } + // Each irreducible loop within the unloop induces a round of iteration using + // the DFS result cached by Traversal. + bool Changed = FoundIB; + for (unsigned NIters = 0; Changed; ++NIters) { + assert(NIters < Unloop->getNumBlocks() && "runaway iterative algorithm"); + + // Iterate over the postorder list of blocks, propagating the nearest loop + // from successors to predecessors as before. + Changed = false; + for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(), + POE = DFS.endPostorder(); POI != POE; ++POI) { + + Loop *L = LI->getLoopFor(*POI); + Loop *NL = getNearestLoop(*POI, L); + if (NL != L) { + assert(NL != Unloop && (!NL || NL->contains(Unloop)) && + "uninitialized successor"); + LI->changeLoopFor(*POI, NL); + Changed = true; + } + } + } +} + +/// removeBlocksFromAncestors - Remove unloop's blocks from all ancestors below +/// their new parents. +void UnloopUpdater::removeBlocksFromAncestors() { + // 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 *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 != OuterParent; + OldParent = OldParent->getParentLoop()) { + assert(OldParent && "new loop is not an ancestor of the original"); + OldParent->removeBlockFromLoop(*BI); + } + } +} + +/// updateSubloopParents - Update the parent loop for all subloops directly +/// nested within unloop. +void UnloopUpdater::updateSubloopParents() { + while (!Unloop->empty()) { + Loop *Subloop = *llvm::prior(Unloop->end()); + Unloop->removeChildLoop(llvm::prior(Unloop->end())); + + assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop"); + if (Loop *Parent = SubloopParents[Subloop]) + Parent->addChildLoop(Subloop); + else + LI->addTopLevelLoop(Subloop); + } +} + +/// getNearestLoop - Return the nearest parent loop among this block's +/// successors. If a successor is a subloop header, consider its parent to be +/// the nearest parent of the subloop's exits. +/// +/// For subloop blocks, simply update SubloopParents and return NULL. +Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { + + // Initially for blocks directly contained by Unloop, NearLoop == Unloop and + // is considered uninitialized. + Loop *NearLoop = BBLoop; + + Loop *Subloop = 0; + if (NearLoop != Unloop && Unloop->contains(NearLoop)) { + Subloop = NearLoop; + // Find the subloop ancestor that is directly contained within Unloop. + while (Subloop->getParentLoop() != Unloop) { + Subloop = Subloop->getParentLoop(); + assert(Subloop && "subloop is not an ancestor of the original loop"); + } + // Get the current nearest parent of the Subloop exits, initially Unloop. + 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. + } + for (; I != E; ++I) { + if (*I == BB) + continue; // self loops are uninteresting + + Loop *L = LI->getLoopFor(*I); + if (L == Unloop) { + // This successor has not been processed. This path must lead to an + // irreducible backedge. + assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB"); + FoundIB = true; + } + if (L != Unloop && Unloop->contains(L)) { + // Successor is in a subloop. + if (Subloop) + continue; // Branching within subloops. Ignore it. + + // BB branches from the original into a subloop header. + assert(L->getParentLoop() == Unloop && "cannot skip into nested loops"); + + // Get the current nearest parent of the Subloop's exits. + L = SubloopParents[L]; + // L could be Unloop if the only exit was an irreducible backedge. + } + if (L == Unloop) { + continue; + } + // Handle critical edges from Unloop into a sibling loop. + if (L && !L->contains(Unloop)) { + L = L->getParentLoop(); + } + // Remember the nearest parent loop among successors or subloop exits. + if (NearLoop == Unloop || !NearLoop || NearLoop->contains(L)) + NearLoop = L; + } + if (Subloop) { + SubloopParents[Subloop] = NearLoop; + return BBLoop; + } + return NearLoop; +} + //===----------------------------------------------------------------------===// // LoopInfo implementation // bool LoopInfo::runOnFunction(Function &) { releaseMemory(); - LI.Calculate(getAnalysis().getBase()); // Update + LI.Analyze(getAnalysis().getBase()); return false; } +/// updateUnloop - The last backedge has been removed from a loop--now the +/// "unloop". Find a new parent for the blocks contained within unloop and +/// update the loop tree. We don't necessarily have valid dominators at this +/// point, but LoopInfo is still valid except for the removal of this loop. +/// +/// Note that Unloop may now be an empty loop. Calling Loop::getHeader without +/// checking first is illegal. +void LoopInfo::updateUnloop(Loop *Unloop) { + + // First handle the special case of no parent loop to simplify the algorithm. + if (!Unloop->getParentLoop()) { + // Since BBLoop had no parent, Unloop blocks are no longer in a loop. + for (Loop::block_iterator I = Unloop->block_begin(), + E = Unloop->block_end(); I != E; ++I) { + + // Don't reparent blocks in subloops. + if (getLoopFor(*I) != Unloop) + continue; + + // Blocks no longer have a parent but are still referenced by Unloop until + // the Unloop object is deleted. + LI.changeLoopFor(*I, 0); + } + + // Remove the loop from the top-level LoopInfo object. + for (LoopInfo::iterator I = LI.begin();; ++I) { + assert(I != LI.end() && "Couldn't find loop"); + if (*I == Unloop) { + LI.removeLoop(I); + break; + } + } + + // Move all of the subloops to the top-level. + while (!Unloop->empty()) + LI.addTopLevelLoop(Unloop->removeChildLoop(llvm::prior(Unloop->end()))); + + return; + } + + // Update the parent loop for all blocks within the loop. Blocks within + // subloops will not change parents. + UnloopUpdater Updater(Unloop, this); + Updater.updateBlockParents(); + + // Remove blocks from former ancestor loops. + Updater.removeBlocksFromAncestors(); + + // Add direct subloops as children in their new parent loop. + Updater.updateSubloopParents(); + + // Remove unloop from its parent loop. + Loop *ParentLoop = Unloop->getParentLoop(); + for (Loop::iterator I = ParentLoop->begin();; ++I) { + assert(I != ParentLoop->end() && "Couldn't find loop"); + if (*I == Unloop) { + ParentLoop->removeChildLoop(I); + break; + } + } +} + +void LoopInfo::verifyAnalysis() const { + // LoopInfo is a FunctionPass, but verifying every loop in the function + // each time verifyAnalysis is called is very expensive. The + // -verify-loop-info option can enable this. In order to perform some + // checking by default, LoopPass has been taught to call verifyLoop + // manually during loop pass sequences. + + 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(&Loops); + } + + // 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(); @@ -313,3 +711,15 @@ void LoopInfo::print(raw_ostream &OS, const Module*) const { LI.print(OS); } +//===----------------------------------------------------------------------===// +// LoopBlocksDFS implementation +// + +/// Traverse the loop blocks and store the DFS result. +/// Useful for clients that just want the final DFS result and don't need to +/// visit blocks during the initial traversal. +void LoopBlocksDFS::perform(LoopInfo *LI) { + LoopBlocksTraversal Traversal(*this, LI); + for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), + POE = Traversal.end(); POI != POE; ++POI) ; +}