//
//===----------------------------------------------------------------------===//
-#ifndef LLVM_ANALYSIS_LOOP_INFO_IMPL_H
-#define LLVM_ANALYSIS_LOOP_INFO_IMPL_H
+#ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H
+#define LLVM_ANALYSIS_LOOPINFOIMPL_H
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/STLExtras.h"
#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/Dominators.h"
namespace llvm {
template<class BlockT, class LoopT>
void LoopBase<BlockT, LoopT>::
getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {
- // Sort the blocks vector so that we can use binary search to do quick
- // lookups.
- SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
- std::sort(LoopBBs.begin(), LoopBBs.end());
-
typedef GraphTraits<BlockT*> BlockTraits;
for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
for (typename BlockTraits::ChildIteratorType I =
BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
I != E; ++I)
- if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) {
+ if (!contains(*I)) {
// Not in current loop? It must be an exit block.
ExitingBlocks.push_back(*BI);
break;
getExitingBlocks(ExitingBlocks);
if (ExitingBlocks.size() == 1)
return ExitingBlocks[0];
- return 0;
+ return nullptr;
}
/// getExitBlocks - Return all of the successor blocks of this loop. These
template<class BlockT, class LoopT>
void LoopBase<BlockT, LoopT>::
getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
- // Sort the blocks vector so that we can use binary search to do quick
- // lookups.
- SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
- std::sort(LoopBBs.begin(), LoopBBs.end());
-
typedef GraphTraits<BlockT*> BlockTraits;
for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
for (typename BlockTraits::ChildIteratorType I =
BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
I != E; ++I)
- if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
+ if (!contains(*I))
// Not in current loop? It must be an exit block.
ExitBlocks.push_back(*I);
}
getExitBlocks(ExitBlocks);
if (ExitBlocks.size() == 1)
return ExitBlocks[0];
- return 0;
+ return nullptr;
}
/// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
template<class BlockT, class LoopT>
void LoopBase<BlockT, LoopT>::
getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const {
- // Sort the blocks vector so that we can use binary search to do quick
- // lookups.
- SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
- array_pod_sort(LoopBBs.begin(), LoopBBs.end());
-
typedef GraphTraits<BlockT*> BlockTraits;
for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
for (typename BlockTraits::ChildIteratorType I =
BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
I != E; ++I)
- if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
+ if (!contains(*I))
// Not in current loop? It must be an exit block.
ExitEdges.push_back(Edge(*BI, *I));
}
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
// Keep track of nodes outside the loop branching to the header...
BlockT *Out = getLoopPredecessor();
- if (!Out) return 0;
+ if (!Out) return nullptr;
// Make sure there is only one exit out of the preheader.
typedef GraphTraits<BlockT*> BlockTraits;
typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
++SI;
if (SI != BlockTraits::child_end(Out))
- return 0; // Multiple exits from the block, must not be a preheader.
+ return nullptr; // Multiple exits from the block, must not be a preheader.
// The predecessor has exactly one successor, so it is a preheader.
return Out;
template<class BlockT, class LoopT>
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
// Keep track of nodes outside the loop branching to the header...
- BlockT *Out = 0;
+ BlockT *Out = nullptr;
// Loop over the predecessors of the header node...
BlockT *Header = getHeader();
- typedef GraphTraits<BlockT*> BlockTraits;
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
for (typename InvBlockTraits::ChildIteratorType PI =
InvBlockTraits::child_begin(Header),
typename InvBlockTraits::NodeType *N = *PI;
if (!contains(N)) { // If the block is not in the loop...
if (Out && Out != N)
- return 0; // Multiple predecessors outside the loop
+ return nullptr; // Multiple predecessors outside the loop
Out = N;
}
}
InvBlockTraits::child_begin(Header);
typename InvBlockTraits::ChildIteratorType PE =
InvBlockTraits::child_end(Header);
- BlockT *Latch = 0;
+ BlockT *Latch = nullptr;
for (; PI != PE; ++PI) {
typename InvBlockTraits::NodeType *N = *PI;
if (contains(N)) {
- if (Latch) return 0;
+ if (Latch) return nullptr;
Latch = N;
}
}
assert((Blocks.empty() || LIB[getHeader()] == this) &&
"Incorrect LI specified for this loop!");
assert(NewBB && "Cannot add a null basic block to the loop!");
- assert(LIB[NewBB] == 0 && "BasicBlock already in the loop!");
+ assert(!LIB[NewBB] && "BasicBlock already in the loop!");
LoopT *L = static_cast<LoopT *>(this);
// Add the basic block to this loop and all parent loops...
while (L) {
- L->Blocks.push_back(NewBB);
+ L->addBlockEntry(NewBB);
L = L->getParentLoop();
}
}
void LoopBase<BlockT, LoopT>::
replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild) {
assert(OldChild->ParentLoop == this && "This loop is already broken!");
- assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
+ assert(!NewChild->ParentLoop && "NewChild already has a parent!");
typename std::vector<LoopT *>::iterator I =
std::find(SubLoops.begin(), SubLoops.end(), OldChild);
assert(I != SubLoops.end() && "OldChild not in loop!");
*I = NewChild;
- OldChild->ParentLoop = 0;
+ OldChild->ParentLoop = nullptr;
NewChild->ParentLoop = static_cast<LoopT *>(this);
}
// Keep track of the number of BBs visited.
unsigned NumVisited = 0;
- // Sort the blocks vector so that we can use binary search to do quick
- // lookups.
- SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
- std::sort(LoopBBs.begin(), LoopBBs.end());
-
// Check the individual blocks.
for ( ; BI != BE; ++BI) {
BlockT *BB = *BI;
for (typename BlockTraits::ChildIteratorType SI =
BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB);
SI != SE; ++SI)
- if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *SI)) {
+ if (contains(*SI)) {
HasInsideLoopSuccs = true;
break;
}
InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);
PI != PE; ++PI) {
BlockT *N = *PI;
- if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), N))
+ if (contains(N))
HasInsideLoopPreds = true;
else
OutsideLoopPreds.push_back(N);
// A non-header loop shouldn't be reachable from outside the loop,
// though it is permitted if the predecessor is not itself actually
// reachable.
- BlockT *EntryBB = BB->getParent()->begin();
- for (df_iterator<BlockT *> NI = df_begin(EntryBB),
- NE = df_end(EntryBB); NI != NE; ++NI)
- for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
- assert(*NI != OutsideLoopPreds[i] &&
- "Loop has multiple entry points!");
+ BlockT *EntryBB = &BB->getParent()->front();
+ for (BlockT *CB : depth_first(EntryBB))
+ for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
+ assert(CB != OutsideLoopPreds[i] &&
+ "Loop has multiple entry points!");
}
assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!");
assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!");
// Each block in each subloop should be contained within this loop.
for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
BI != BE; ++BI) {
- assert(std::binary_search(LoopBBs.begin(), LoopBBs.end(), *BI) &&
+ assert(contains(*BI) &&
"Loop does not contain all the blocks of a subloop!");
}
for (unsigned i = 0; i < getBlocks().size(); ++i) {
if (i) OS << ",";
BlockT *BB = getBlocks()[i];
- WriteAsOperand(OS, BB, false);
+ BB->printAsOperand(OS, false);
if (BB == getHeader()) OS << "<header>";
if (BB == getLoopLatch()) OS << "<latch>";
if (isLoopExiting(BB)) OS << "<exiting>";
}
//===----------------------------------------------------------------------===//
-/// LoopInfo - This class builds and contains all of the top level loop
-/// structures in the specified function.
+/// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
+/// result does / not depend on use list (block predecessor) order.
///
+/// Discover a subloop with the specified backedges such that: All blocks within
+/// this loop are mapped to this loop or a subloop. And all subloops within this
+/// loop have their parent loop set to this loop or a subloop.
template<class BlockT, class LoopT>
-void LoopInfoBase<BlockT, LoopT>::Calculate(DominatorTreeBase<BlockT> &DT) {
- BlockT *RootNode = DT.getRootNode()->getBlock();
+static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT*> Backedges,
+ LoopInfoBase<BlockT, LoopT> *LI,
+ const DominatorTreeBase<BlockT> &DomTree) {
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
- for (df_iterator<BlockT*> NI = df_begin(RootNode),
- NE = df_end(RootNode); NI != NE; ++NI)
- if (LoopT *L = ConsiderForLoop(*NI, DT))
- TopLevelLoops.push_back(L);
+ unsigned NumBlocks = 0;
+ unsigned NumSubloops = 0;
+
+ // Perform a backward CFG traversal using a worklist.
+ std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
+ while (!ReverseCFGWorklist.empty()) {
+ BlockT *PredBB = ReverseCFGWorklist.back();
+ ReverseCFGWorklist.pop_back();
+
+ LoopT *Subloop = LI->getLoopFor(PredBB);
+ if (!Subloop) {
+ if (!DomTree.isReachableFromEntry(PredBB))
+ continue;
+
+ // This is an undiscovered block. Map it to the current loop.
+ LI->changeLoopFor(PredBB, L);
+ ++NumBlocks;
+ if (PredBB == L->getHeader())
+ continue;
+ // Push all block predecessors on the worklist.
+ ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
+ InvBlockTraits::child_begin(PredBB),
+ InvBlockTraits::child_end(PredBB));
+ }
+ else {
+ // This is a discovered block. Find its outermost discovered loop.
+ while (LoopT *Parent = Subloop->getParentLoop())
+ Subloop = Parent;
+
+ // If it is already discovered to be a subloop of this loop, continue.
+ if (Subloop == L)
+ continue;
+
+ // Discover a subloop of this loop.
+ Subloop->setParentLoop(L);
+ ++NumSubloops;
+ NumBlocks += Subloop->getBlocks().capacity();
+ PredBB = Subloop->getHeader();
+ // Continue traversal along predecessors that are not loop-back edges from
+ // within this subloop tree itself. Note that a predecessor may directly
+ // reach another subloop that is not yet discovered to be a subloop of
+ // this loop, which we must traverse.
+ for (typename InvBlockTraits::ChildIteratorType PI =
+ InvBlockTraits::child_begin(PredBB),
+ PE = InvBlockTraits::child_end(PredBB); PI != PE; ++PI) {
+ if (LI->getLoopFor(*PI) != Subloop)
+ ReverseCFGWorklist.push_back(*PI);
+ }
+ }
+ }
+ L->getSubLoopsVector().reserve(NumSubloops);
+ L->reserveBlocks(NumBlocks);
}
+/// Populate all loop data in a stable order during a single forward DFS.
template<class BlockT, class LoopT>
-LoopT *LoopInfoBase<BlockT, LoopT>::
-ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) {
- if (BBMap.count(BB)) return 0; // Haven't processed this node?
+class PopulateLoopsDFS {
+ typedef GraphTraits<BlockT*> BlockTraits;
+ typedef typename BlockTraits::ChildIteratorType SuccIterTy;
- std::vector<BlockT *> TodoStack;
+ LoopInfoBase<BlockT, LoopT> *LI;
+public:
+ PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li):
+ LI(li) {}
- // Scan the predecessors of BB, checking to see if BB dominates any of
- // them. This identifies backedges which target this node...
- typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
- for (typename InvBlockTraits::ChildIteratorType I =
- InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB);
- I != E; ++I) {
- typename InvBlockTraits::NodeType *N = *I;
- // If BB dominates its predecessor...
- if (DT.dominates(BB, N) && DT.isReachableFromEntry(N))
- TodoStack.push_back(N);
- }
+ void traverse(BlockT *EntryBlock);
- if (TodoStack.empty()) return 0; // No backedges to this block...
-
- // Create a new loop to represent this basic block...
- LoopT *L = new LoopT(BB);
- BBMap[BB] = L;
-
- while (!TodoStack.empty()) { // Process all the nodes in the loop
- BlockT *X = TodoStack.back();
- TodoStack.pop_back();
-
- if (!L->contains(X) && // As of yet unprocessed??
- DT.isReachableFromEntry(X)) {
- // Check to see if this block already belongs to a loop. If this occurs
- // then we have a case where a loop that is supposed to be a child of
- // the current loop was processed before the current loop. When this
- // occurs, this child loop gets added to a part of the current loop,
- // making it a sibling to the current loop. We have to reparent this
- // loop.
- if (LoopT *SubLoop =
- const_cast<LoopT *>(getLoopFor(X)))
- if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){
- // Remove the subloop from its current parent...
- assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L);
- LoopT *SLP = SubLoop->ParentLoop; // SubLoopParent
- typename std::vector<LoopT *>::iterator I =
- std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop);
- assert(I != SLP->SubLoops.end() &&"SubLoop not a child of parent?");
- SLP->SubLoops.erase(I); // Remove from parent...
-
- // Add the subloop to THIS loop...
- SubLoop->ParentLoop = L;
- L->SubLoops.push_back(SubLoop);
- }
-
- // Normal case, add the block to our loop...
- L->Blocks.push_back(X);
-
- typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
-
- // Add all of the predecessors of X to the end of the work stack...
- TodoStack.insert(TodoStack.end(), InvBlockTraits::child_begin(X),
- InvBlockTraits::child_end(X));
- }
- }
+protected:
+ void insertIntoLoop(BlockT *Block);
+};
- // If there are any loops nested within this loop, create them now!
- for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),
- E = L->Blocks.end(); I != E; ++I)
- if (LoopT *NewLoop = ConsiderForLoop(*I, DT)) {
- L->SubLoops.push_back(NewLoop);
- NewLoop->ParentLoop = L;
- }
+/// Top-level driver for the forward DFS within the loop.
+template<class BlockT, class LoopT>
+void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
+ for (BlockT *BB : post_order(EntryBlock))
+ insertIntoLoop(BB);
+}
- // Add the basic blocks that comprise this loop to the BBMap so that this
- // loop can be found for them.
- //
- for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),
- E = L->Blocks.end(); I != E; ++I)
- BBMap.insert(std::make_pair(*I, L));
-
- // Now that we have a list of all of the child loops of this loop, check to
- // see if any of them should actually be nested inside of each other. We
- // can accidentally pull loops our of their parents, so we must make sure to
- // organize the loop nests correctly now.
- {
- std::map<BlockT *, LoopT *> ContainingLoops;
- for (unsigned i = 0; i != L->SubLoops.size(); ++i) {
- LoopT *Child = L->SubLoops[i];
- assert(Child->getParentLoop() == L && "Not proper child loop?");
-
- if (LoopT *ContainingLoop = ContainingLoops[Child->getHeader()]) {
- // If there is already a loop which contains this loop, move this loop
- // into the containing loop.
- MoveSiblingLoopInto(Child, ContainingLoop);
- --i; // The loop got removed from the SubLoops list.
- } else {
- // This is currently considered to be a top-level loop. Check to see
- // if any of the contained blocks are loop headers for subloops we
- // have already processed.
- for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) {
- LoopT *&BlockLoop = ContainingLoops[Child->Blocks[b]];
- if (BlockLoop == 0) { // Child block not processed yet...
- BlockLoop = Child;
- } else if (BlockLoop != Child) {
- LoopT *SubLoop = BlockLoop;
- // Reparent all of the blocks which used to belong to BlockLoops
- for (unsigned j = 0, f = SubLoop->Blocks.size(); j != f; ++j)
- ContainingLoops[SubLoop->Blocks[j]] = Child;
-
- // There is already a loop which contains this block, that means
- // that we should reparent the loop which the block is currently
- // considered to belong to to be a child of this loop.
- MoveSiblingLoopInto(SubLoop, Child);
- --i; // We just shrunk the SubLoops list.
- }
- }
- }
- }
+/// Add a single Block to its ancestor loops in PostOrder. If the block is a
+/// subloop header, add the subloop to its parent in PostOrder, then reverse the
+/// Block and Subloop vectors of the now complete subloop to achieve RPO.
+template<class BlockT, class LoopT>
+void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
+ LoopT *Subloop = LI->getLoopFor(Block);
+ if (Subloop && Block == Subloop->getHeader()) {
+ // We reach this point once per subloop after processing all the blocks in
+ // the subloop.
+ if (Subloop->getParentLoop())
+ Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
+ else
+ LI->addTopLevelLoop(Subloop);
+
+ // For convenience, Blocks and Subloops are inserted in postorder. Reverse
+ // the lists, except for the loop header, which is always at the beginning.
+ Subloop->reverseBlock(1);
+ std::reverse(Subloop->getSubLoopsVector().begin(),
+ Subloop->getSubLoopsVector().end());
+
+ Subloop = Subloop->getParentLoop();
}
-
- return L;
+ for (; Subloop; Subloop = Subloop->getParentLoop())
+ Subloop->addBlockEntry(Block);
}
-/// MoveSiblingLoopInto - This method moves the NewChild loop to live inside
-/// of the NewParent Loop, instead of being a sibling of it.
+/// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
+/// interleaved with backward CFG traversals within each subloop
+/// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
+/// this part of the algorithm is linear in the number of CFG edges. Subloop and
+/// Block vectors are then populated during a single forward CFG traversal
+/// (PopulateLoopDFS).
+///
+/// During the two CFG traversals each block is seen three times:
+/// 1) Discovered and mapped by a reverse CFG traversal.
+/// 2) Visited during a forward DFS CFG traversal.
+/// 3) Reverse-inserted in the loop in postorder following forward DFS.
+///
+/// The Block vectors are inclusive, so step 3 requires loop-depth number of
+/// insertions per block.
template<class BlockT, class LoopT>
void LoopInfoBase<BlockT, LoopT>::
-MoveSiblingLoopInto(LoopT *NewChild, LoopT *NewParent) {
- LoopT *OldParent = NewChild->getParentLoop();
- assert(OldParent && OldParent == NewParent->getParentLoop() &&
- NewChild != NewParent && "Not sibling loops!");
+analyze(const DominatorTreeBase<BlockT> &DomTree) {
- // Remove NewChild from being a child of OldParent
- typename std::vector<LoopT *>::iterator I =
- std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(),
- NewChild);
- assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??");
- OldParent->SubLoops.erase(I); // Remove from parent's subloops list
- NewChild->ParentLoop = 0;
+ // Postorder traversal of the dominator tree.
+ const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
+ for (auto DomNode : post_order(DomRoot)) {
- InsertLoopInto(NewChild, NewParent);
-}
+ BlockT *Header = DomNode->getBlock();
+ SmallVector<BlockT *, 4> Backedges;
-/// InsertLoopInto - This inserts loop L into the specified parent loop. If
-/// the parent loop contains a loop which should contain L, the loop gets
-/// inserted into L instead.
-template<class BlockT, class LoopT>
-void LoopInfoBase<BlockT, LoopT>::InsertLoopInto(LoopT *L, LoopT *Parent) {
- BlockT *LHeader = L->getHeader();
- assert(Parent->contains(LHeader) &&
- "This loop should not be inserted here!");
-
- // Check to see if it belongs in a child loop...
- for (unsigned i = 0, e = static_cast<unsigned>(Parent->SubLoops.size());
- i != e; ++i)
- if (Parent->SubLoops[i]->contains(LHeader)) {
- InsertLoopInto(L, Parent->SubLoops[i]);
- return;
- }
+ // Check each predecessor of the potential loop header.
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+ for (typename InvBlockTraits::ChildIteratorType PI =
+ InvBlockTraits::child_begin(Header),
+ PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {
+
+ BlockT *Backedge = *PI;
- // If not, insert it here!
- Parent->SubLoops.push_back(L);
- L->ParentLoop = Parent;
+ // If Header dominates predBB, this is a new loop. Collect the backedges.
+ if (DomTree.dominates(Header, Backedge)
+ && DomTree.isReachableFromEntry(Backedge)) {
+ Backedges.push_back(Backedge);
+ }
+ }
+ // Perform a backward CFG traversal to discover and map blocks in this loop.
+ if (!Backedges.empty()) {
+ LoopT *L = new LoopT(Header);
+ discoverAndMapSubloop(L, ArrayRef<BlockT*>(Backedges), this, DomTree);
+ }
+ }
+ // Perform a single forward CFG traversal to populate block and subloop
+ // vectors for all loops.
+ PopulateLoopsDFS<BlockT, LoopT> DFS(this);
+ DFS.traverse(DomRoot->getBlock());
}
// Debugging
#endif
}
+template<class BlockT, class LoopT>
+void LoopInfoBase<BlockT, LoopT>::verify() const {
+ DenseSet<const LoopT*> 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.
+#ifndef NDEBUG
+ for (auto &Entry : BBMap) {
+ const BlockT *BB = Entry.first;
+ LoopT *L = Entry.second;
+ assert(Loops.count(L) && "orphaned loop");
+ assert(L->contains(BB) && "orphaned block");
+ }
+#endif
+}
+
} // End llvm namespace
#endif
projects / oota-llvm.git / blobdiff