<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Moving to cfe-dev to catch the attention of people who know something about this...<div><br><div><div>On Jun 19, 2012, at 10:55 PM, Chandler Carruth <<a href="mailto:chandlerc@google.com">chandlerc@google.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div style="font-family: arial, helvetica, sans-serif"><font size="2"><div class="gmail_quote">On Tue, Jun 19, 2012 at 8:42 PM, Andrew Trick <span dir="ltr"><<a href="mailto:atrick@apple.com" target="_blank">atrick@apple.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; position: static; z-index: auto; ">Author: atrick<br>
Date: Tue Jun 19 22:42:09 2012<br>
New Revision: 158787<br>
<br>
URL: <a href="http://llvm.org/viewvc/llvm-project?rev=158787&view=rev" target="_blank">http://llvm.org/viewvc/llvm-project?rev=158787&view=rev</a><br>
Log:<br>
Move the implementation of LoopInfo into LoopInfoImpl.h.<br>
<br>
The implementation only needs inclusion from LoopInfo.cpp and<br>
MachineLoopInfo.cpp. Clients of the interface should only include the<br>
interface. This makes the interface readable and speeds up rebuilds<br>
after modifying the implementation.<br></blockquote><div><br></div><div>Technically speaking, I think you need to declare the templates as 'extern' for this to be valid (<a href="http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=549">http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=549</a> is the best link I have).</div>
<div><br></div><div>This is a C++11 feature, but it is available with GCC since ~forever as an extension. It often "just works" without it, but my understanding is that technically it isn't valid as any old TU that uses these constructs is supposed to have a definition available.</div>
<div><br></div><div>At least for compilers that support it putting the various things like:</div><div><br></div><div>__extension__ extern template class LoopInfoBase<BasicBlock, Loop>;</div><div><br></div><div>Into the header would make me happier...</div>
<div><br></div><div>I'm OK relying on compilers to make this "just work" if they don't support the extension (MSVC likely, dunno), but where the do, this will make sure everything works together nicely.</div></div></font></div></blockquote><div><br></div><div>I thought the "extern template" was purely an optimization and unlikely to have any benefit with clang in this limited setting. But I'm glad you pointed it out, because I was hoping someone could explain the situation to me.</div><div><br></div><div>My basis for making the change to explicit instantiation is that we've been using the pattern for a year now elsewhere in LLVM and no one has complained. I didn't mess with "extern template" because I didn't want to introduce something confusing and compiler-specific without a good reason.</div><div><br></div><div>-Andy</div><div><br></div><blockquote type="cite"><div style="font-family: arial, helvetica, sans-serif"><font size="2"><div class="gmail_quote"><div> </div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; position: static; z-index: auto; ">
<br>
Added:<br>
llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h<br>
Modified:<br>
llvm/trunk/include/llvm/Analysis/LoopInfo.h<br>
llvm/trunk/lib/Analysis/LoopInfo.cpp<br>
llvm/trunk/lib/CodeGen/MachineLoopInfo.cpp<br>
<br>
Modified: llvm/trunk/include/llvm/Analysis/LoopInfo.h<br>
URL: <a href="http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Analysis/LoopInfo.h?rev=158787&r1=158786&r2=158787&view=diff" target="_blank">http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Analysis/LoopInfo.h?rev=158787&r1=158786&r2=158787&view=diff</a><br>
==============================================================================<br>
--- llvm/trunk/include/llvm/Analysis/LoopInfo.h (original)<br>
+++ llvm/trunk/include/llvm/Analysis/LoopInfo.h Tue Jun 19 22:42:09 2012<br>
@@ -181,83 +181,26 @@<br>
/// outside of the loop. These are the blocks _inside of the current loop_<br>
/// which branch out. The returned list is always unique.<br>
///<br>
- void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {<br>
- // Sort the blocks vector so that we can use binary search to do quick<br>
- // lookups.<br>
- SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());<br>
- std::sort(LoopBBs.begin(), LoopBBs.end());<br>
-<br>
- typedef GraphTraits<BlockT*> BlockTraits;<br>
- for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)<br>
- for (typename BlockTraits::ChildIteratorType I =<br>
- BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);<br>
- I != E; ++I)<br>
- if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) {<br>
- // Not in current loop? It must be an exit block.<br>
- ExitingBlocks.push_back(*BI);<br>
- break;<br>
- }<br>
- }<br>
+ void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const;<br>
<br>
/// getExitingBlock - If getExitingBlocks would return exactly one block,<br>
/// return that block. Otherwise return null.<br>
- BlockT *getExitingBlock() const {<br>
- SmallVector<BlockT*, 8> ExitingBlocks;<br>
- getExitingBlocks(ExitingBlocks);<br>
- if (ExitingBlocks.size() == 1)<br>
- return ExitingBlocks[0];<br>
- return 0;<br>
- }<br>
+ BlockT *getExitingBlock() const;<br>
<br>
/// getExitBlocks - Return all of the successor blocks of this loop. These<br>
/// are the blocks _outside of the current loop_ which are branched to.<br>
///<br>
- void getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {<br>
- // Sort the blocks vector so that we can use binary search to do quick<br>
- // lookups.<br>
- SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());<br>
- std::sort(LoopBBs.begin(), LoopBBs.end());<br>
-<br>
- typedef GraphTraits<BlockT*> BlockTraits;<br>
- for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)<br>
- for (typename BlockTraits::ChildIteratorType I =<br>
- BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);<br>
- I != E; ++I)<br>
- if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))<br>
- // Not in current loop? It must be an exit block.<br>
- ExitBlocks.push_back(*I);<br>
- }<br>
+ void getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const;<br>
<br>
/// getExitBlock - If getExitBlocks would return exactly one block,<br>
/// return that block. Otherwise return null.<br>
- BlockT *getExitBlock() const {<br>
- SmallVector<BlockT*, 8> ExitBlocks;<br>
- getExitBlocks(ExitBlocks);<br>
- if (ExitBlocks.size() == 1)<br>
- return ExitBlocks[0];<br>
- return 0;<br>
- }<br>
+ BlockT *getExitBlock() const;<br>
<br>
/// Edge type.<br>
- typedef std::pair<BlockT*, BlockT*> Edge;<br>
+ typedef std::pair<const BlockT*, const BlockT*> Edge;<br>
<br>
/// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).<br>
- template <typename EdgeT><br>
- void getExitEdges(SmallVectorImpl<EdgeT> &ExitEdges) const {<br>
- // Sort the blocks vector so that we can use binary search to do quick<br>
- // lookups.<br>
- SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());<br>
- array_pod_sort(LoopBBs.begin(), LoopBBs.end());<br>
-<br>
- typedef GraphTraits<BlockT*> BlockTraits;<br>
- for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)<br>
- for (typename BlockTraits::ChildIteratorType I =<br>
- BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);<br>
- I != E; ++I)<br>
- if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))<br>
- // Not in current loop? It must be an exit block.<br>
- ExitEdges.push_back(EdgeT(*BI, *I));<br>
- }<br>
+ void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const;<br>
<br>
/// getLoopPreheader - If there is a preheader for this loop, return it. A<br>
/// loop has a preheader if there is only one edge to the header of the loop<br>
@@ -266,71 +209,18 @@<br>
///<br>
/// This method returns null if there is no preheader for the loop.<br>
///<br>
- BlockT *getLoopPreheader() const {<br>
- // Keep track of nodes outside the loop branching to the header...<br>
- BlockT *Out = getLoopPredecessor();<br>
- if (!Out) return 0;<br>
-<br>
- // Make sure there is only one exit out of the preheader.<br>
- typedef GraphTraits<BlockT*> BlockTraits;<br>
- typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);<br>
- ++SI;<br>
- if (SI != BlockTraits::child_end(Out))<br>
- return 0; // Multiple exits from the block, must not be a preheader.<br>
-<br>
- // The predecessor has exactly one successor, so it is a preheader.<br>
- return Out;<br>
- }<br>
+ BlockT *getLoopPreheader() const;<br>
<br>
/// getLoopPredecessor - If the given loop's header has exactly one unique<br>
/// predecessor outside the loop, return it. Otherwise return null.<br>
/// This is less strict that the loop "preheader" concept, which requires<br>
/// the predecessor to have exactly one successor.<br>
///<br>
- BlockT *getLoopPredecessor() const {<br>
- // Keep track of nodes outside the loop branching to the header...<br>
- BlockT *Out = 0;<br>
-<br>
- // Loop over the predecessors of the header node...<br>
- BlockT *Header = getHeader();<br>
- typedef GraphTraits<BlockT*> BlockTraits;<br>
- typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;<br>
- for (typename InvBlockTraits::ChildIteratorType PI =<br>
- InvBlockTraits::child_begin(Header),<br>
- PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {<br>
- typename InvBlockTraits::NodeType *N = *PI;<br>
- if (!contains(N)) { // If the block is not in the loop...<br>
- if (Out && Out != N)<br>
- return 0; // Multiple predecessors outside the loop<br>
- Out = N;<br>
- }<br>
- }<br>
-<br>
- // Make sure there is only one exit out of the preheader.<br>
- assert(Out && "Header of loop has no predecessors from outside loop?");<br>
- return Out;<br>
- }<br>
+ BlockT *getLoopPredecessor() const;<br>
<br>
/// getLoopLatch - If there is a single latch block for this loop, return it.<br>
/// A latch block is a block that contains a branch back to the header.<br>
- BlockT *getLoopLatch() const {<br>
- BlockT *Header = getHeader();<br>
- typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;<br>
- typename InvBlockTraits::ChildIteratorType PI =<br>
- InvBlockTraits::child_begin(Header);<br>
- typename InvBlockTraits::ChildIteratorType PE =<br>
- InvBlockTraits::child_end(Header);<br>
- BlockT *Latch = 0;<br>
- for (; PI != PE; ++PI) {<br>
- typename InvBlockTraits::NodeType *N = *PI;<br>
- if (contains(N)) {<br>
- if (Latch) return 0;<br>
- Latch = N;<br>
- }<br>
- }<br>
-<br>
- return Latch;<br>
- }<br>
+ BlockT *getLoopLatch() const;<br>
<br>
//===--------------------------------------------------------------------===//<br>
// APIs for updating loop information after changing the CFG<br>
@@ -348,17 +238,7 @@<br>
/// the OldChild entry in our children list with NewChild, and updates the<br>
/// parent pointer of OldChild to be null and the NewChild to be this loop.<br>
/// This updates the loop depth of the new child.<br>
- void replaceChildLoopWith(LoopT *OldChild,<br>
- LoopT *NewChild) {<br>
- assert(OldChild->ParentLoop == this && "This loop is already broken!");<br>
- assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");<br>
- typename std::vector<LoopT *>::iterator I =<br>
- std::find(SubLoops.begin(), SubLoops.end(), OldChild);<br>
- assert(I != SubLoops.end() && "OldChild not in loop!");<br>
- *I = NewChild;<br>
- OldChild->ParentLoop = 0;<br>
- NewChild->ParentLoop = static_cast<LoopT *>(this);<br>
- }<br>
+ void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild);<br>
<br>
/// addChildLoop - Add the specified loop to be a child of this loop. This<br>
/// updates the loop depth of the new child.<br>
@@ -411,121 +291,12 @@<br>
}<br>
<br>
/// verifyLoop - Verify loop structure<br>
- void verifyLoop() const {<br>
-#ifndef NDEBUG<br>
- assert(!Blocks.empty() && "Loop header is missing");<br>
-<br>
- // Setup for using a depth-first iterator to visit every block in the loop.<br>
- SmallVector<BlockT*, 8> ExitBBs;<br>
- getExitBlocks(ExitBBs);<br>
- llvm::SmallPtrSet<BlockT*, 8> VisitSet;<br>
- VisitSet.insert(ExitBBs.begin(), ExitBBs.end());<br>
- df_ext_iterator<BlockT*, llvm::SmallPtrSet<BlockT*, 8> ><br>
- BI = df_ext_begin(getHeader(), VisitSet),<br>
- BE = df_ext_end(getHeader(), VisitSet);<br>
-<br>
- // Keep track of the number of BBs visited.<br>
- unsigned NumVisited = 0;<br>
-<br>
- // Sort the blocks vector so that we can use binary search to do quick<br>
- // lookups.<br>
- SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());<br>
- std::sort(LoopBBs.begin(), LoopBBs.end());<br>
-<br>
- // Check the individual blocks.<br>
- for ( ; BI != BE; ++BI) {<br>
- BlockT *BB = *BI;<br>
- bool HasInsideLoopSuccs = false;<br>
- bool HasInsideLoopPreds = false;<br>
- SmallVector<BlockT *, 2> OutsideLoopPreds;<br>
-<br>
- typedef GraphTraits<BlockT*> BlockTraits;<br>
- for (typename BlockTraits::ChildIteratorType SI =<br>
- BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB);<br>
- SI != SE; ++SI)<br>
- if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *SI)) {<br>
- HasInsideLoopSuccs = true;<br>
- break;<br>
- }<br>
- typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;<br>
- for (typename InvBlockTraits::ChildIteratorType PI =<br>
- InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);<br>
- PI != PE; ++PI) {<br>
- BlockT *N = *PI;<br>
- if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), N))<br>
- HasInsideLoopPreds = true;<br>
- else<br>
- OutsideLoopPreds.push_back(N);<br>
- }<br>
-<br>
- if (BB == getHeader()) {<br>
- assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");<br>
- } else if (!OutsideLoopPreds.empty()) {<br>
- // A non-header loop shouldn't be reachable from outside the loop,<br>
- // though it is permitted if the predecessor is not itself actually<br>
- // reachable.<br>
- BlockT *EntryBB = BB->getParent()->begin();<br>
- for (df_iterator<BlockT *> NI = df_begin(EntryBB),<br>
- NE = df_end(EntryBB); NI != NE; ++NI)<br>
- for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)<br>
- assert(*NI != OutsideLoopPreds[i] &&<br>
- "Loop has multiple entry points!");<br>
- }<br>
- assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!");<br>
- assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!");<br>
- assert(BB != getHeader()->getParent()->begin() &&<br>
- "Loop contains function entry block!");<br>
-<br>
- NumVisited++;<br>
- }<br>
-<br>
- assert(NumVisited == getNumBlocks() && "Unreachable block in loop");<br>
-<br>
- // Check the subloops.<br>
- for (iterator I = begin(), E = end(); I != E; ++I)<br>
- // Each block in each subloop should be contained within this loop.<br>
- for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();<br>
- BI != BE; ++BI) {<br>
- assert(std::binary_search(LoopBBs.begin(), LoopBBs.end(), *BI) &&<br>
- "Loop does not contain all the blocks of a subloop!");<br>
- }<br>
-<br>
- // Check the parent loop pointer.<br>
- if (ParentLoop) {<br>
- assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) !=<br>
- ParentLoop->end() &&<br>
- "Loop is not a subloop of its parent!");<br>
- }<br>
-#endif<br>
- }<br>
+ void verifyLoop() const;<br>
<br>
/// verifyLoop - Verify loop structure of this loop and all nested loops.<br>
- void verifyLoopNest(DenseSet<const LoopT*> *Loops) const {<br>
- Loops->insert(static_cast<const LoopT *>(this));<br>
- // Verify this loop.<br>
- verifyLoop();<br>
- // Verify the subloops.<br>
- for (iterator I = begin(), E = end(); I != E; ++I)<br>
- (*I)->verifyLoopNest(Loops);<br>
- }<br>
-<br>
- void print(raw_ostream &OS, unsigned Depth = 0) const {<br>
- OS.indent(Depth*2) << "Loop at depth " << getLoopDepth()<br>
- << " containing: ";<br>
-<br>
- for (unsigned i = 0; i < getBlocks().size(); ++i) {<br>
- if (i) OS << ",";<br>
- BlockT *BB = getBlocks()[i];<br>
- WriteAsOperand(OS, BB, false);<br>
- if (BB == getHeader()) OS << "<header>";<br>
- if (BB == getLoopLatch()) OS << "<latch>";<br>
- if (isLoopExiting(BB)) OS << "<exiting>";<br>
- }<br>
- OS << "\n";<br>
+ void verifyLoopNest(DenseSet<const LoopT*> *Loops) const;<br>
<br>
- for (iterator I = begin(), E = end(); I != E; ++I)<br>
- (*I)->print(OS, Depth+2);<br>
- }<br>
+ void print(raw_ostream &OS, unsigned Depth = 0) const;<br>
<br>
protected:<br>
friend class LoopInfoBase<BlockT, LoopT>;<br>
@@ -744,187 +515,22 @@<br>
return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);<br>
}<br>
<br>
- void Calculate(DominatorTreeBase<BlockT> &DT) {<br>
- BlockT *RootNode = DT.getRootNode()->getBlock();<br>
-<br>
- for (df_iterator<BlockT*> NI = df_begin(RootNode),<br>
- NE = df_end(RootNode); NI != NE; ++NI)<br>
- if (LoopT *L = ConsiderForLoop(*NI, DT))<br>
- TopLevelLoops.push_back(L);<br>
- }<br>
-<br>
- LoopT *ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) {<br>
- if (BBMap.count(BB)) return 0; // Haven't processed this node?<br>
-<br>
- std::vector<BlockT *> TodoStack;<br>
-<br>
- // Scan the predecessors of BB, checking to see if BB dominates any of<br>
- // them. This identifies backedges which target this node...<br>
- typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;<br>
- for (typename InvBlockTraits::ChildIteratorType I =<br>
- InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB);<br>
- I != E; ++I) {<br>
- typename InvBlockTraits::NodeType *N = *I;<br>
- // If BB dominates its predecessor...<br>
- if (DT.dominates(BB, N) && DT.isReachableFromEntry(N))<br>
- TodoStack.push_back(N);<br>
- }<br>
-<br>
- if (TodoStack.empty()) return 0; // No backedges to this block...<br>
-<br>
- // Create a new loop to represent this basic block...<br>
- LoopT *L = new LoopT(BB);<br>
- BBMap[BB] = L;<br>
-<br>
- while (!TodoStack.empty()) { // Process all the nodes in the loop<br>
- BlockT *X = TodoStack.back();<br>
- TodoStack.pop_back();<br>
-<br>
- if (!L->contains(X) && // As of yet unprocessed??<br>
- DT.isReachableFromEntry(X)) {<br>
- // Check to see if this block already belongs to a loop. If this occurs<br>
- // then we have a case where a loop that is supposed to be a child of<br>
- // the current loop was processed before the current loop. When this<br>
- // occurs, this child loop gets added to a part of the current loop,<br>
- // making it a sibling to the current loop. We have to reparent this<br>
- // loop.<br>
- if (LoopT *SubLoop =<br>
- const_cast<LoopT *>(getLoopFor(X)))<br>
- if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){<br>
- // Remove the subloop from its current parent...<br>
- assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L);<br>
- LoopT *SLP = SubLoop->ParentLoop; // SubLoopParent<br>
- typename std::vector<LoopT *>::iterator I =<br>
- std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop);<br>
- assert(I != SLP->SubLoops.end() &&"SubLoop not a child of parent?");<br>
- SLP->SubLoops.erase(I); // Remove from parent...<br>
-<br>
- // Add the subloop to THIS loop...<br>
- SubLoop->ParentLoop = L;<br>
- L->SubLoops.push_back(SubLoop);<br>
- }<br>
-<br>
- // Normal case, add the block to our loop...<br>
- L->Blocks.push_back(X);<br>
-<br>
- typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;<br>
-<br>
- // Add all of the predecessors of X to the end of the work stack...<br>
- TodoStack.insert(TodoStack.end(), InvBlockTraits::child_begin(X),<br>
- InvBlockTraits::child_end(X));<br>
- }<br>
- }<br>
-<br>
- // If there are any loops nested within this loop, create them now!<br>
- for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),<br>
- E = L->Blocks.end(); I != E; ++I)<br>
- if (LoopT *NewLoop = ConsiderForLoop(*I, DT)) {<br>
- L->SubLoops.push_back(NewLoop);<br>
- NewLoop->ParentLoop = L;<br>
- }<br>
-<br>
- // Add the basic blocks that comprise this loop to the BBMap so that this<br>
- // loop can be found for them.<br>
- //<br>
- for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),<br>
- E = L->Blocks.end(); I != E; ++I)<br>
- BBMap.insert(std::make_pair(*I, L));<br>
-<br>
- // Now that we have a list of all of the child loops of this loop, check to<br>
- // see if any of them should actually be nested inside of each other. We<br>
- // can accidentally pull loops our of their parents, so we must make sure to<br>
- // organize the loop nests correctly now.<br>
- {<br>
- std::map<BlockT *, LoopT *> ContainingLoops;<br>
- for (unsigned i = 0; i != L->SubLoops.size(); ++i) {<br>
- LoopT *Child = L->SubLoops[i];<br>
- assert(Child->getParentLoop() == L && "Not proper child loop?");<br>
-<br>
- if (LoopT *ContainingLoop = ContainingLoops[Child->getHeader()]) {<br>
- // If there is already a loop which contains this loop, move this loop<br>
- // into the containing loop.<br>
- MoveSiblingLoopInto(Child, ContainingLoop);<br>
- --i; // The loop got removed from the SubLoops list.<br>
- } else {<br>
- // This is currently considered to be a top-level loop. Check to see<br>
- // if any of the contained blocks are loop headers for subloops we<br>
- // have already processed.<br>
- for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) {<br>
- LoopT *&BlockLoop = ContainingLoops[Child->Blocks[b]];<br>
- if (BlockLoop == 0) { // Child block not processed yet...<br>
- BlockLoop = Child;<br>
- } else if (BlockLoop != Child) {<br>
- LoopT *SubLoop = BlockLoop;<br>
- // Reparent all of the blocks which used to belong to BlockLoops<br>
- for (unsigned j = 0, f = SubLoop->Blocks.size(); j != f; ++j)<br>
- ContainingLoops[SubLoop->Blocks[j]] = Child;<br>
-<br>
- // There is already a loop which contains this block, that means<br>
- // that we should reparent the loop which the block is currently<br>
- // considered to belong to to be a child of this loop.<br>
- MoveSiblingLoopInto(SubLoop, Child);<br>
- --i; // We just shrunk the SubLoops list.<br>
- }<br>
- }<br>
- }<br>
- }<br>
- }<br>
+ void Calculate(DominatorTreeBase<BlockT> &DT);<br>
<br>
- return L;<br>
- }<br>
+ LoopT *ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT);<br>
<br>
/// MoveSiblingLoopInto - This method moves the NewChild loop to live inside<br>
/// of the NewParent Loop, instead of being a sibling of it.<br>
- void MoveSiblingLoopInto(LoopT *NewChild,<br>
- LoopT *NewParent) {<br>
- LoopT *OldParent = NewChild->getParentLoop();<br>
- assert(OldParent && OldParent == NewParent->getParentLoop() &&<br>
- NewChild != NewParent && "Not sibling loops!");<br>
-<br>
- // Remove NewChild from being a child of OldParent<br>
- typename std::vector<LoopT *>::iterator I =<br>
- std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(),<br>
- NewChild);<br>
- assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??");<br>
- OldParent->SubLoops.erase(I); // Remove from parent's subloops list<br>
- NewChild->ParentLoop = 0;<br>
-<br>
- InsertLoopInto(NewChild, NewParent);<br>
- }<br>
+ void MoveSiblingLoopInto(LoopT *NewChild, LoopT *NewParent);<br>
<br>
/// InsertLoopInto - This inserts loop L into the specified parent loop. If<br>
/// the parent loop contains a loop which should contain L, the loop gets<br>
/// inserted into L instead.<br>
- void InsertLoopInto(LoopT *L, LoopT *Parent) {<br>
- BlockT *LHeader = L->getHeader();<br>
- assert(Parent->contains(LHeader) &&<br>
- "This loop should not be inserted here!");<br>
-<br>
- // Check to see if it belongs in a child loop...<br>
- for (unsigned i = 0, e = static_cast<unsigned>(Parent->SubLoops.size());<br>
- i != e; ++i)<br>
- if (Parent->SubLoops[i]->contains(LHeader)) {<br>
- InsertLoopInto(L, Parent->SubLoops[i]);<br>
- return;<br>
- }<br>
-<br>
- // If not, insert it here!<br>
- Parent->SubLoops.push_back(L);<br>
- L->ParentLoop = Parent;<br>
- }<br>
+ void InsertLoopInto(LoopT *L, LoopT *Parent);<br>
<br>
// Debugging<br>
<br>
- void print(raw_ostream &OS) const {<br>
- for (unsigned i = 0; i < TopLevelLoops.size(); ++i)<br>
- TopLevelLoops[i]->print(OS);<br>
- #if 0<br>
- for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),<br>
- E = BBMap.end(); I != E; ++I)<br>
- OS << "BB '" << I->first->getName() << "' level = "<br>
- << I->second->getLoopDepth() << "\n";<br>
- #endif<br>
- }<br>
+ void print(raw_ostream &OS) const;<br>
};<br>
<br>
class LoopInfo : public FunctionPass {<br>
@@ -1074,27 +680,6 @@<br>
}<br>
};<br>
<br>
-template<class BlockT, class LoopT><br>
-void<br>
-LoopBase<BlockT, LoopT>::addBasicBlockToLoop(BlockT *NewBB,<br>
- LoopInfoBase<BlockT, LoopT> &LIB) {<br>
- assert((Blocks.empty() || LIB[getHeader()] == this) &&<br>
- "Incorrect LI specified for this loop!");<br>
- assert(NewBB && "Cannot add a null basic block to the loop!");<br>
- assert(LIB[NewBB] == 0 && "BasicBlock already in the loop!");<br>
-<br>
- LoopT *L = static_cast<LoopT *>(this);<br>
-<br>
- // Add the loop mapping to the LoopInfo object...<br>
- LIB.BBMap[NewBB] = L;<br>
-<br>
- // Add the basic block to this loop and all parent loops...<br>
- while (L) {<br>
- L->Blocks.push_back(NewBB);<br>
- L = L->getParentLoop();<br>
- }<br>
-}<br>
-<br>
} // End llvm namespace<br>
<br>
#endif<br>
<br>
Added: llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h<br>
URL: <a href="http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h?rev=158787&view=auto" target="_blank">http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h?rev=158787&view=auto</a><br>
==============================================================================<br>
--- llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h (added)<br>
+++ llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h Tue Jun 19 22:42:09 2012<br>
@@ -0,0 +1,549 @@<br>
+//===- llvm/Analysis/LoopInfoImpl.h - Natural Loop Calculator ---*- C++ -*-===//<br>
+//<br>
+// The LLVM Compiler Infrastructure<br>
+//<br>
+// This file is distributed under the University of Illinois Open Source<br>
+// License. See LICENSE.TXT for details.<br>
+//<br>
+//===----------------------------------------------------------------------===//<br>
+//<br>
+// This is the generic implementation of LoopInfo used for both Loops and<br>
+// MachineLoops.<br>
+//<br>
+//===----------------------------------------------------------------------===//<br>
+<br>
+#ifndef LLVM_ANALYSIS_LOOP_INFO_IMPL_H<br>
+#define LLVM_ANALYSIS_LOOP_INFO_IMPL_H<br>
+<br>
+#include "llvm/Analysis/LoopInfo.h"<br>
+<br>
+namespace llvm {<br>
+<br>
+//===----------------------------------------------------------------------===//<br>
+// APIs for simple analysis of the loop. See header notes.<br>
+<br>
+/// getExitingBlocks - Return all blocks inside the loop that have successors<br>
+/// outside of the loop. These are the blocks _inside of the current loop_<br>
+/// which branch out. The returned list is always unique.<br>
+///<br>
+template<class BlockT, class LoopT><br>
+void LoopBase<BlockT, LoopT>::<br>
+getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {<br>
+ // Sort the blocks vector so that we can use binary search to do quick<br>
+ // lookups.<br>
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());<br>
+ std::sort(LoopBBs.begin(), LoopBBs.end());<br>
+<br>
+ typedef GraphTraits<BlockT*> BlockTraits;<br>
+ for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)<br>
+ for (typename BlockTraits::ChildIteratorType I =<br>
+ BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);<br>
+ I != E; ++I)<br>
+ if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) {<br>
+ // Not in current loop? It must be an exit block.<br>
+ ExitingBlocks.push_back(*BI);<br>
+ break;<br>
+ }<br>
+}<br>
+<br>
+/// getExitingBlock - If getExitingBlocks would return exactly one block,<br>
+/// return that block. Otherwise return null.<br>
+template<class BlockT, class LoopT><br>
+BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {<br>
+ SmallVector<BlockT*, 8> ExitingBlocks;<br>
+ getExitingBlocks(ExitingBlocks);<br>
+ if (ExitingBlocks.size() == 1)<br>
+ return ExitingBlocks[0];<br>
+ return 0;<br>
+}<br>
+<br>
+/// getExitBlocks - Return all of the successor blocks of this loop. These<br>
+/// are the blocks _outside of the current loop_ which are branched to.<br>
+///<br>
+template<class BlockT, class LoopT><br>
+void LoopBase<BlockT, LoopT>::<br>
+getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {<br>
+ // Sort the blocks vector so that we can use binary search to do quick<br>
+ // lookups.<br>
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());<br>
+ std::sort(LoopBBs.begin(), LoopBBs.end());<br>
+<br>
+ typedef GraphTraits<BlockT*> BlockTraits;<br>
+ for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)<br>
+ for (typename BlockTraits::ChildIteratorType I =<br>
+ BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);<br>
+ I != E; ++I)<br>
+ if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))<br>
+ // Not in current loop? It must be an exit block.<br>
+ ExitBlocks.push_back(*I);<br>
+}<br>
+<br>
+/// getExitBlock - If getExitBlocks would return exactly one block,<br>
+/// return that block. Otherwise return null.<br>
+template<class BlockT, class LoopT><br>
+BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {<br>
+ SmallVector<BlockT*, 8> ExitBlocks;<br>
+ getExitBlocks(ExitBlocks);<br>
+ if (ExitBlocks.size() == 1)<br>
+ return ExitBlocks[0];<br>
+ return 0;<br>
+}<br>
+<br>
+/// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).<br>
+template<class BlockT, class LoopT><br>
+void LoopBase<BlockT, LoopT>::<br>
+getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const {<br>
+ // Sort the blocks vector so that we can use binary search to do quick<br>
+ // lookups.<br>
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());<br>
+ array_pod_sort(LoopBBs.begin(), LoopBBs.end());<br>
+<br>
+ typedef GraphTraits<BlockT*> BlockTraits;<br>
+ for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)<br>
+ for (typename BlockTraits::ChildIteratorType I =<br>
+ BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);<br>
+ I != E; ++I)<br>
+ if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))<br>
+ // Not in current loop? It must be an exit block.<br>
+ ExitEdges.push_back(Edge(*BI, *I));<br>
+}<br>
+<br>
+/// getLoopPreheader - If there is a preheader for this loop, return it. A<br>
+/// loop has a preheader if there is only one edge to the header of the loop<br>
+/// from outside of the loop. If this is the case, the block branching to the<br>
+/// header of the loop is the preheader node.<br>
+///<br>
+/// This method returns null if there is no preheader for the loop.<br>
+///<br>
+template<class BlockT, class LoopT><br>
+BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {<br>
+ // Keep track of nodes outside the loop branching to the header...<br>
+ BlockT *Out = getLoopPredecessor();<br>
+ if (!Out) return 0;<br>
+<br>
+ // Make sure there is only one exit out of the preheader.<br>
+ typedef GraphTraits<BlockT*> BlockTraits;<br>
+ typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);<br>
+ ++SI;<br>
+ if (SI != BlockTraits::child_end(Out))<br>
+ return 0; // Multiple exits from the block, must not be a preheader.<br>
+<br>
+ // The predecessor has exactly one successor, so it is a preheader.<br>
+ return Out;<br>
+}<br>
+<br>
+/// getLoopPredecessor - If the given loop's header has exactly one unique<br>
+/// predecessor outside the loop, return it. Otherwise return null.<br>
+/// This is less strict that the loop "preheader" concept, which requires<br>
+/// the predecessor to have exactly one successor.<br>
+///<br>
+template<class BlockT, class LoopT><br>
+BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {<br>
+ // Keep track of nodes outside the loop branching to the header...<br>
+ BlockT *Out = 0;<br>
+<br>
+ // Loop over the predecessors of the header node...<br>
+ BlockT *Header = getHeader();<br>
+ typedef GraphTraits<BlockT*> BlockTraits;<br>
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;<br>
+ for (typename InvBlockTraits::ChildIteratorType PI =<br>
+ InvBlockTraits::child_begin(Header),<br>
+ PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {<br>
+ typename InvBlockTraits::NodeType *N = *PI;<br>
+ if (!contains(N)) { // If the block is not in the loop...<br>
+ if (Out && Out != N)<br>
+ return 0; // Multiple predecessors outside the loop<br>
+ Out = N;<br>
+ }<br>
+ }<br>
+<br>
+ // Make sure there is only one exit out of the preheader.<br>
+ assert(Out && "Header of loop has no predecessors from outside loop?");<br>
+ return Out;<br>
+}<br>
+<br>
+/// getLoopLatch - If there is a single latch block for this loop, return it.<br>
+/// A latch block is a block that contains a branch back to the header.<br>
+template<class BlockT, class LoopT><br>
+BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {<br>
+ BlockT *Header = getHeader();<br>
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;<br>
+ typename InvBlockTraits::ChildIteratorType PI =<br>
+ InvBlockTraits::child_begin(Header);<br>
+ typename InvBlockTraits::ChildIteratorType PE =<br>
+ InvBlockTraits::child_end(Header);<br>
+ BlockT *Latch = 0;<br>
+ for (; PI != PE; ++PI) {<br>
+ typename InvBlockTraits::NodeType *N = *PI;<br>
+ if (contains(N)) {<br>
+ if (Latch) return 0;<br>
+ Latch = N;<br>
+ }<br>
+ }<br>
+<br>
+ return Latch;<br>
+}<br>
+<br>
+//===----------------------------------------------------------------------===//<br>
+// APIs for updating loop information after changing the CFG<br>
+//<br>
+<br>
+/// addBasicBlockToLoop - This method is used by other analyses to update loop<br>
+/// information. NewBB is set to be a new member of the current loop.<br>
+/// Because of this, it is added as a member of all parent loops, and is added<br>
+/// to the specified LoopInfo object as being in the current basic block. It<br>
+/// is not valid to replace the loop header with this method.<br>
+///<br>
+template<class BlockT, class LoopT><br>
+void LoopBase<BlockT, LoopT>::<br>
+addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {<br>
+ assert((Blocks.empty() || LIB[getHeader()] == this) &&<br>
+ "Incorrect LI specified for this loop!");<br>
+ assert(NewBB && "Cannot add a null basic block to the loop!");<br>
+ assert(LIB[NewBB] == 0 && "BasicBlock already in the loop!");<br>
+<br>
+ LoopT *L = static_cast<LoopT *>(this);<br>
+<br>
+ // Add the loop mapping to the LoopInfo object...<br>
+ LIB.BBMap[NewBB] = L;<br>
+<br>
+ // Add the basic block to this loop and all parent loops...<br>
+ while (L) {<br>
+ L->Blocks.push_back(NewBB);<br>
+ L = L->getParentLoop();<br>
+ }<br>
+}<br>
+<br>
+/// replaceChildLoopWith - This is used when splitting loops up. It replaces<br>
+/// the OldChild entry in our children list with NewChild, and updates the<br>
+/// parent pointer of OldChild to be null and the NewChild to be this loop.<br>
+/// This updates the loop depth of the new child.<br>
+template<class BlockT, class LoopT><br>
+void LoopBase<BlockT, LoopT>::<br>
+replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild) {<br>
+ assert(OldChild->ParentLoop == this && "This loop is already broken!");<br>
+ assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");<br>
+ typename std::vector<LoopT *>::iterator I =<br>
+ std::find(SubLoops.begin(), SubLoops.end(), OldChild);<br>
+ assert(I != SubLoops.end() && "OldChild not in loop!");<br>
+ *I = NewChild;<br>
+ OldChild->ParentLoop = 0;<br>
+ NewChild->ParentLoop = static_cast<LoopT *>(this);<br>
+}<br>
+<br>
+/// verifyLoop - Verify loop structure<br>
+template<class BlockT, class LoopT><br>
+void LoopBase<BlockT, LoopT>::verifyLoop() const {<br>
+#ifndef NDEBUG<br>
+ assert(!Blocks.empty() && "Loop header is missing");<br>
+<br>
+ // Setup for using a depth-first iterator to visit every block in the loop.<br>
+ SmallVector<BlockT*, 8> ExitBBs;<br>
+ getExitBlocks(ExitBBs);<br>
+ llvm::SmallPtrSet<BlockT*, 8> VisitSet;<br>
+ VisitSet.insert(ExitBBs.begin(), ExitBBs.end());<br>
+ df_ext_iterator<BlockT*, llvm::SmallPtrSet<BlockT*, 8> ><br>
+ BI = df_ext_begin(getHeader(), VisitSet),<br>
+ BE = df_ext_end(getHeader(), VisitSet);<br>
+<br>
+ // Keep track of the number of BBs visited.<br>
+ unsigned NumVisited = 0;<br>
+<br>
+ // Sort the blocks vector so that we can use binary search to do quick<br>
+ // lookups.<br>
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());<br>
+ std::sort(LoopBBs.begin(), LoopBBs.end());<br>
+<br>
+ // Check the individual blocks.<br>
+ for ( ; BI != BE; ++BI) {<br>
+ BlockT *BB = *BI;<br>
+ bool HasInsideLoopSuccs = false;<br>
+ bool HasInsideLoopPreds = false;<br>
+ SmallVector<BlockT *, 2> OutsideLoopPreds;<br>
+<br>
+ typedef GraphTraits<BlockT*> BlockTraits;<br>
+ for (typename BlockTraits::ChildIteratorType SI =<br>
+ BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB);<br>
+ SI != SE; ++SI)<br>
+ if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *SI)) {<br>
+ HasInsideLoopSuccs = true;<br>
+ break;<br>
+ }<br>
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;<br>
+ for (typename InvBlockTraits::ChildIteratorType PI =<br>
+ InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);<br>
+ PI != PE; ++PI) {<br>
+ BlockT *N = *PI;<br>
+ if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), N))<br>
+ HasInsideLoopPreds = true;<br>
+ else<br>
+ OutsideLoopPreds.push_back(N);<br>
+ }<br>
+<br>
+ if (BB == getHeader()) {<br>
+ assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");<br>
+ } else if (!OutsideLoopPreds.empty()) {<br>
+ // A non-header loop shouldn't be reachable from outside the loop,<br>
+ // though it is permitted if the predecessor is not itself actually<br>
+ // reachable.<br>
+ BlockT *EntryBB = BB->getParent()->begin();<br>
+ for (df_iterator<BlockT *> NI = df_begin(EntryBB),<br>
+ NE = df_end(EntryBB); NI != NE; ++NI)<br>
+ for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)<br>
+ assert(*NI != OutsideLoopPreds[i] &&<br>
+ "Loop has multiple entry points!");<br>
+ }<br>
+ assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!");<br>
+ assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!");<br>
+ assert(BB != getHeader()->getParent()->begin() &&<br>
+ "Loop contains function entry block!");<br>
+<br>
+ NumVisited++;<br>
+ }<br>
+<br>
+ assert(NumVisited == getNumBlocks() && "Unreachable block in loop");<br>
+<br>
+ // Check the subloops.<br>
+ for (iterator I = begin(), E = end(); I != E; ++I)<br>
+ // Each block in each subloop should be contained within this loop.<br>
+ for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();<br>
+ BI != BE; ++BI) {<br>
+ assert(std::binary_search(LoopBBs.begin(), LoopBBs.end(), *BI) &&<br>
+ "Loop does not contain all the blocks of a subloop!");<br>
+ }<br>
+<br>
+ // Check the parent loop pointer.<br>
+ if (ParentLoop) {<br>
+ assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) !=<br>
+ ParentLoop->end() &&<br>
+ "Loop is not a subloop of its parent!");<br>
+ }<br>
+#endif<br>
+}<br>
+<br>
+/// verifyLoop - Verify loop structure of this loop and all nested loops.<br>
+template<class BlockT, class LoopT><br>
+void LoopBase<BlockT, LoopT>::verifyLoopNest(<br>
+ DenseSet<const LoopT*> *Loops) const {<br>
+ Loops->insert(static_cast<const LoopT *>(this));<br>
+ // Verify this loop.<br>
+ verifyLoop();<br>
+ // Verify the subloops.<br>
+ for (iterator I = begin(), E = end(); I != E; ++I)<br>
+ (*I)->verifyLoopNest(Loops);<br>
+}<br>
+<br>
+template<class BlockT, class LoopT><br>
+void LoopBase<BlockT, LoopT>::print(raw_ostream &OS, unsigned Depth) const {<br>
+ OS.indent(Depth*2) << "Loop at depth " << getLoopDepth()<br>
+ << " containing: ";<br>
+<br>
+ for (unsigned i = 0; i < getBlocks().size(); ++i) {<br>
+ if (i) OS << ",";<br>
+ BlockT *BB = getBlocks()[i];<br>
+ WriteAsOperand(OS, BB, false);<br>
+ if (BB == getHeader()) OS << "<header>";<br>
+ if (BB == getLoopLatch()) OS << "<latch>";<br>
+ if (isLoopExiting(BB)) OS << "<exiting>";<br>
+ }<br>
+ OS << "\n";<br>
+<br>
+ for (iterator I = begin(), E = end(); I != E; ++I)<br>
+ (*I)->print(OS, Depth+2);<br>
+}<br>
+<br>
+//===----------------------------------------------------------------------===//<br>
+/// LoopInfo - This class builds and contains all of the top level loop<br>
+/// structures in the specified function.<br>
+///<br>
+<br>
+template<class BlockT, class LoopT><br>
+void LoopInfoBase<BlockT, LoopT>::Calculate(DominatorTreeBase<BlockT> &DT) {<br>
+ BlockT *RootNode = DT.getRootNode()->getBlock();<br>
+<br>
+ for (df_iterator<BlockT*> NI = df_begin(RootNode),<br>
+ NE = df_end(RootNode); NI != NE; ++NI)<br>
+ if (LoopT *L = ConsiderForLoop(*NI, DT))<br>
+ TopLevelLoops.push_back(L);<br>
+}<br>
+<br>
+template<class BlockT, class LoopT><br>
+LoopT *LoopInfoBase<BlockT, LoopT>::<br>
+ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) {<br>
+ if (BBMap.count(BB)) return 0; // Haven't processed this node?<br>
+<br>
+ std::vector<BlockT *> TodoStack;<br>
+<br>
+ // Scan the predecessors of BB, checking to see if BB dominates any of<br>
+ // them. This identifies backedges which target this node...<br>
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;<br>
+ for (typename InvBlockTraits::ChildIteratorType I =<br>
+ InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB);<br>
+ I != E; ++I) {<br>
+ typename InvBlockTraits::NodeType *N = *I;<br>
+ // If BB dominates its predecessor...<br>
+ if (DT.dominates(BB, N) && DT.isReachableFromEntry(N))<br>
+ TodoStack.push_back(N);<br>
+ }<br>
+<br>
+ if (TodoStack.empty()) return 0; // No backedges to this block...<br>
+<br>
+ // Create a new loop to represent this basic block...<br>
+ LoopT *L = new LoopT(BB);<br>
+ BBMap[BB] = L;<br>
+<br>
+ while (!TodoStack.empty()) { // Process all the nodes in the loop<br>
+ BlockT *X = TodoStack.back();<br>
+ TodoStack.pop_back();<br>
+<br>
+ if (!L->contains(X) && // As of yet unprocessed??<br>
+ DT.isReachableFromEntry(X)) {<br>
+ // Check to see if this block already belongs to a loop. If this occurs<br>
+ // then we have a case where a loop that is supposed to be a child of<br>
+ // the current loop was processed before the current loop. When this<br>
+ // occurs, this child loop gets added to a part of the current loop,<br>
+ // making it a sibling to the current loop. We have to reparent this<br>
+ // loop.<br>
+ if (LoopT *SubLoop =<br>
+ const_cast<LoopT *>(getLoopFor(X)))<br>
+ if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){<br>
+ // Remove the subloop from its current parent...<br>
+ assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L);<br>
+ LoopT *SLP = SubLoop->ParentLoop; // SubLoopParent<br>
+ typename std::vector<LoopT *>::iterator I =<br>
+ std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop);<br>
+ assert(I != SLP->SubLoops.end() &&"SubLoop not a child of parent?");<br>
+ SLP->SubLoops.erase(I); // Remove from parent...<br>
+<br>
+ // Add the subloop to THIS loop...<br>
+ SubLoop->ParentLoop = L;<br>
+ L->SubLoops.push_back(SubLoop);<br>
+ }<br>
+<br>
+ // Normal case, add the block to our loop...<br>
+ L->Blocks.push_back(X);<br>
+<br>
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;<br>
+<br>
+ // Add all of the predecessors of X to the end of the work stack...<br>
+ TodoStack.insert(TodoStack.end(), InvBlockTraits::child_begin(X),<br>
+ InvBlockTraits::child_end(X));<br>
+ }<br>
+ }<br>
+<br>
+ // If there are any loops nested within this loop, create them now!<br>
+ for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),<br>
+ E = L->Blocks.end(); I != E; ++I)<br>
+ if (LoopT *NewLoop = ConsiderForLoop(*I, DT)) {<br>
+ L->SubLoops.push_back(NewLoop);<br>
+ NewLoop->ParentLoop = L;<br>
+ }<br>
+<br>
+ // Add the basic blocks that comprise this loop to the BBMap so that this<br>
+ // loop can be found for them.<br>
+ //<br>
+ for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),<br>
+ E = L->Blocks.end(); I != E; ++I)<br>
+ BBMap.insert(std::make_pair(*I, L));<br>
+<br>
+ // Now that we have a list of all of the child loops of this loop, check to<br>
+ // see if any of them should actually be nested inside of each other. We<br>
+ // can accidentally pull loops our of their parents, so we must make sure to<br>
+ // organize the loop nests correctly now.<br>
+ {<br>
+ std::map<BlockT *, LoopT *> ContainingLoops;<br>
+ for (unsigned i = 0; i != L->SubLoops.size(); ++i) {<br>
+ LoopT *Child = L->SubLoops[i];<br>
+ assert(Child->getParentLoop() == L && "Not proper child loop?");<br>
+<br>
+ if (LoopT *ContainingLoop = ContainingLoops[Child->getHeader()]) {<br>
+ // If there is already a loop which contains this loop, move this loop<br>
+ // into the containing loop.<br>
+ MoveSiblingLoopInto(Child, ContainingLoop);<br>
+ --i; // The loop got removed from the SubLoops list.<br>
+ } else {<br>
+ // This is currently considered to be a top-level loop. Check to see<br>
+ // if any of the contained blocks are loop headers for subloops we<br>
+ // have already processed.<br>
+ for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) {<br>
+ LoopT *&BlockLoop = ContainingLoops[Child->Blocks[b]];<br>
+ if (BlockLoop == 0) { // Child block not processed yet...<br>
+ BlockLoop = Child;<br>
+ } else if (BlockLoop != Child) {<br>
+ LoopT *SubLoop = BlockLoop;<br>
+ // Reparent all of the blocks which used to belong to BlockLoops<br>
+ for (unsigned j = 0, f = SubLoop->Blocks.size(); j != f; ++j)<br>
+ ContainingLoops[SubLoop->Blocks[j]] = Child;<br>
+<br>
+ // There is already a loop which contains this block, that means<br>
+ // that we should reparent the loop which the block is currently<br>
+ // considered to belong to to be a child of this loop.<br>
+ MoveSiblingLoopInto(SubLoop, Child);<br>
+ --i; // We just shrunk the SubLoops list.<br>
+ }<br>
+ }<br>
+ }<br>
+ }<br>
+ }<br>
+<br>
+ return L;<br>
+}<br>
+<br>
+/// MoveSiblingLoopInto - This method moves the NewChild loop to live inside<br>
+/// of the NewParent Loop, instead of being a sibling of it.<br>
+template<class BlockT, class LoopT><br>
+void LoopInfoBase<BlockT, LoopT>::<br>
+MoveSiblingLoopInto(LoopT *NewChild, LoopT *NewParent) {<br>
+ LoopT *OldParent = NewChild->getParentLoop();<br>
+ assert(OldParent && OldParent == NewParent->getParentLoop() &&<br>
+ NewChild != NewParent && "Not sibling loops!");<br>
+<br>
+ // Remove NewChild from being a child of OldParent<br>
+ typename std::vector<LoopT *>::iterator I =<br>
+ std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(),<br>
+ NewChild);<br>
+ assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??");<br>
+ OldParent->SubLoops.erase(I); // Remove from parent's subloops list<br>
+ NewChild->ParentLoop = 0;<br>
+<br>
+ InsertLoopInto(NewChild, NewParent);<br>
+}<br>
+<br>
+/// InsertLoopInto - This inserts loop L into the specified parent loop. If<br>
+/// the parent loop contains a loop which should contain L, the loop gets<br>
+/// inserted into L instead.<br>
+template<class BlockT, class LoopT><br>
+void LoopInfoBase<BlockT, LoopT>::InsertLoopInto(LoopT *L, LoopT *Parent) {<br>
+ BlockT *LHeader = L->getHeader();<br>
+ assert(Parent->contains(LHeader) &&<br>
+ "This loop should not be inserted here!");<br>
+<br>
+ // Check to see if it belongs in a child loop...<br>
+ for (unsigned i = 0, e = static_cast<unsigned>(Parent->SubLoops.size());<br>
+ i != e; ++i)<br>
+ if (Parent->SubLoops[i]->contains(LHeader)) {<br>
+ InsertLoopInto(L, Parent->SubLoops[i]);<br>
+ return;<br>
+ }<br>
+<br>
+ // If not, insert it here!<br>
+ Parent->SubLoops.push_back(L);<br>
+ L->ParentLoop = Parent;<br>
+}<br>
+<br>
+// Debugging<br>
+template<class BlockT, class LoopT><br>
+void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const {<br>
+ for (unsigned i = 0; i < TopLevelLoops.size(); ++i)<br>
+ TopLevelLoops[i]->print(OS);<br>
+#if 0<br>
+ for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),<br>
+ E = BBMap.end(); I != E; ++I)<br>
+ OS << "BB '" << I->first->getName() << "' level = "<br>
+ << I->second->getLoopDepth() << "\n";<br>
+#endif<br>
+}<br>
+<br>
+} // End llvm namespace<br>
+<br>
+#endif<br>
<br>
Modified: llvm/trunk/lib/Analysis/LoopInfo.cpp<br>
URL: <a href="http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Analysis/LoopInfo.cpp?rev=158787&r1=158786&r2=158787&view=diff" target="_blank">http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Analysis/LoopInfo.cpp?rev=158787&r1=158786&r2=158787&view=diff</a><br>
==============================================================================<br>
--- llvm/trunk/lib/Analysis/LoopInfo.cpp (original)<br>
+++ llvm/trunk/lib/Analysis/LoopInfo.cpp Tue Jun 19 22:42:09 2012<br>
@@ -18,6 +18,7 @@<br>
#include "llvm/Constants.h"<br>
#include "llvm/Instructions.h"<br>
#include "llvm/Analysis/Dominators.h"<br>
+#include "llvm/Analysis/LoopInfoImpl.h"<br>
#include "llvm/Analysis/LoopIterator.h"<br>
#include "llvm/Analysis/ValueTracking.h"<br>
#include "llvm/Assembly/Writer.h"<br>
@@ -29,6 +30,10 @@<br>
#include <algorithm><br>
using namespace llvm;<br>
<br>
+// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.<br>
+template class llvm::LoopBase<BasicBlock, Loop>;<br>
+template class llvm::LoopInfoBase<BasicBlock, Loop>;<br>
+<br>
// Always verify loopinfo if expensive checking is enabled.<br>
#ifdef XDEBUG<br>
static bool VerifyLoopInfo = true;<br>
<br>
Modified: llvm/trunk/lib/CodeGen/MachineLoopInfo.cpp<br>
URL: <a href="http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/CodeGen/MachineLoopInfo.cpp?rev=158787&r1=158786&r2=158787&view=diff" target="_blank">http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/CodeGen/MachineLoopInfo.cpp?rev=158787&r1=158786&r2=158787&view=diff</a><br>
==============================================================================<br>
--- llvm/trunk/lib/CodeGen/MachineLoopInfo.cpp (original)<br>
+++ llvm/trunk/lib/CodeGen/MachineLoopInfo.cpp Tue Jun 19 22:42:09 2012<br>
@@ -9,7 +9,7 @@<br>
//<br>
// This file defines the MachineLoopInfo class that is used to identify natural<br>
// loops and determine the loop depth of various nodes of the CFG. Note that<br>
-// the loops identified may actually be several natural loops that share the<br>
+// the loops identified may actually be several natural loops that share the<br>
// same header node... not just a single natural loop.<br>
//<br>
//===----------------------------------------------------------------------===//<br>
@@ -17,17 +17,13 @@<br>
#include "llvm/CodeGen/MachineLoopInfo.h"<br>
#include "llvm/CodeGen/MachineDominators.h"<br>
#include "llvm/CodeGen/Passes.h"<br>
+#include "llvm/Analysis/LoopInfoImpl.h"<br>
#include "llvm/Support/Debug.h"<br>
using namespace llvm;<br>
<br>
-namespace llvm {<br>
-#define MLB class LoopBase<MachineBasicBlock, MachineLoop><br>
-TEMPLATE_INSTANTIATION(MLB);<br>
-#undef MLB<br>
-#define MLIB class LoopInfoBase<MachineBasicBlock, MachineLoop><br>
-TEMPLATE_INSTANTIATION(MLIB);<br>
-#undef MLIB<br>
-}<br>
+// Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.<br>
+template class llvm::LoopBase<MachineBasicBlock, MachineLoop>;<br>
+template class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;<br>
<br>
char MachineLoopInfo::ID = 0;<br>
INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops",<br>
<br>
<br>
_______________________________________________<br>
llvm-commits mailing list<br>
<a href="mailto:llvm-commits@cs.uiuc.edu">llvm-commits@cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits</a><br>
</blockquote></div><br></font></div>
</blockquote></div><br></div></body></html>