1 //===- llvm/Analysis/LoopInfoImpl.h - Natural Loop Calculator ---*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This is the generic implementation of LoopInfo used for both Loops and
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_ANALYSIS_LOOP_INFO_IMPL_H
16 #define LLVM_ANALYSIS_LOOP_INFO_IMPL_H
18 #include "llvm/Analysis/LoopInfo.h"
22 //===----------------------------------------------------------------------===//
23 // APIs for simple analysis of the loop. See header notes.
25 /// getExitingBlocks - Return all blocks inside the loop that have successors
26 /// outside of the loop. These are the blocks _inside of the current loop_
27 /// which branch out. The returned list is always unique.
29 template<class BlockT, class LoopT>
30 void LoopBase<BlockT, LoopT>::
31 getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {
32 // Sort the blocks vector so that we can use binary search to do quick
34 SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
35 std::sort(LoopBBs.begin(), LoopBBs.end());
37 typedef GraphTraits<BlockT*> BlockTraits;
38 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
39 for (typename BlockTraits::ChildIteratorType I =
40 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
42 if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) {
43 // Not in current loop? It must be an exit block.
44 ExitingBlocks.push_back(*BI);
49 /// getExitingBlock - If getExitingBlocks would return exactly one block,
50 /// return that block. Otherwise return null.
51 template<class BlockT, class LoopT>
52 BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
53 SmallVector<BlockT*, 8> ExitingBlocks;
54 getExitingBlocks(ExitingBlocks);
55 if (ExitingBlocks.size() == 1)
56 return ExitingBlocks[0];
60 /// getExitBlocks - Return all of the successor blocks of this loop. These
61 /// are the blocks _outside of the current loop_ which are branched to.
63 template<class BlockT, class LoopT>
64 void LoopBase<BlockT, LoopT>::
65 getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
66 // Sort the blocks vector so that we can use binary search to do quick
68 SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
69 std::sort(LoopBBs.begin(), LoopBBs.end());
71 typedef GraphTraits<BlockT*> BlockTraits;
72 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
73 for (typename BlockTraits::ChildIteratorType I =
74 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
76 if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
77 // Not in current loop? It must be an exit block.
78 ExitBlocks.push_back(*I);
81 /// getExitBlock - If getExitBlocks would return exactly one block,
82 /// return that block. Otherwise return null.
83 template<class BlockT, class LoopT>
84 BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
85 SmallVector<BlockT*, 8> ExitBlocks;
86 getExitBlocks(ExitBlocks);
87 if (ExitBlocks.size() == 1)
92 /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
93 template<class BlockT, class LoopT>
94 void LoopBase<BlockT, LoopT>::
95 getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const {
96 // Sort the blocks vector so that we can use binary search to do quick
98 SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
99 array_pod_sort(LoopBBs.begin(), LoopBBs.end());
101 typedef GraphTraits<BlockT*> BlockTraits;
102 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
103 for (typename BlockTraits::ChildIteratorType I =
104 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
106 if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
107 // Not in current loop? It must be an exit block.
108 ExitEdges.push_back(Edge(*BI, *I));
111 /// getLoopPreheader - If there is a preheader for this loop, return it. A
112 /// loop has a preheader if there is only one edge to the header of the loop
113 /// from outside of the loop. If this is the case, the block branching to the
114 /// header of the loop is the preheader node.
116 /// This method returns null if there is no preheader for the loop.
118 template<class BlockT, class LoopT>
119 BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
120 // Keep track of nodes outside the loop branching to the header...
121 BlockT *Out = getLoopPredecessor();
124 // Make sure there is only one exit out of the preheader.
125 typedef GraphTraits<BlockT*> BlockTraits;
126 typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
128 if (SI != BlockTraits::child_end(Out))
129 return 0; // Multiple exits from the block, must not be a preheader.
131 // The predecessor has exactly one successor, so it is a preheader.
135 /// getLoopPredecessor - If the given loop's header has exactly one unique
136 /// predecessor outside the loop, return it. Otherwise return null.
137 /// This is less strict that the loop "preheader" concept, which requires
138 /// the predecessor to have exactly one successor.
140 template<class BlockT, class LoopT>
141 BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
142 // Keep track of nodes outside the loop branching to the header...
145 // Loop over the predecessors of the header node...
146 BlockT *Header = getHeader();
147 typedef GraphTraits<BlockT*> BlockTraits;
148 typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
149 for (typename InvBlockTraits::ChildIteratorType PI =
150 InvBlockTraits::child_begin(Header),
151 PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {
152 typename InvBlockTraits::NodeType *N = *PI;
153 if (!contains(N)) { // If the block is not in the loop...
155 return 0; // Multiple predecessors outside the loop
160 // Make sure there is only one exit out of the preheader.
161 assert(Out && "Header of loop has no predecessors from outside loop?");
165 /// getLoopLatch - If there is a single latch block for this loop, return it.
166 /// A latch block is a block that contains a branch back to the header.
167 template<class BlockT, class LoopT>
168 BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
169 BlockT *Header = getHeader();
170 typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
171 typename InvBlockTraits::ChildIteratorType PI =
172 InvBlockTraits::child_begin(Header);
173 typename InvBlockTraits::ChildIteratorType PE =
174 InvBlockTraits::child_end(Header);
176 for (; PI != PE; ++PI) {
177 typename InvBlockTraits::NodeType *N = *PI;
187 //===----------------------------------------------------------------------===//
188 // APIs for updating loop information after changing the CFG
191 /// addBasicBlockToLoop - This method is used by other analyses to update loop
192 /// information. NewBB is set to be a new member of the current loop.
193 /// Because of this, it is added as a member of all parent loops, and is added
194 /// to the specified LoopInfo object as being in the current basic block. It
195 /// is not valid to replace the loop header with this method.
197 template<class BlockT, class LoopT>
198 void LoopBase<BlockT, LoopT>::
199 addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
200 assert((Blocks.empty() || LIB[getHeader()] == this) &&
201 "Incorrect LI specified for this loop!");
202 assert(NewBB && "Cannot add a null basic block to the loop!");
203 assert(LIB[NewBB] == 0 && "BasicBlock already in the loop!");
205 LoopT *L = static_cast<LoopT *>(this);
207 // Add the loop mapping to the LoopInfo object...
208 LIB.BBMap[NewBB] = L;
210 // Add the basic block to this loop and all parent loops...
212 L->Blocks.push_back(NewBB);
213 L = L->getParentLoop();
217 /// replaceChildLoopWith - This is used when splitting loops up. It replaces
218 /// the OldChild entry in our children list with NewChild, and updates the
219 /// parent pointer of OldChild to be null and the NewChild to be this loop.
220 /// This updates the loop depth of the new child.
221 template<class BlockT, class LoopT>
222 void LoopBase<BlockT, LoopT>::
223 replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild) {
224 assert(OldChild->ParentLoop == this && "This loop is already broken!");
225 assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
226 typename std::vector<LoopT *>::iterator I =
227 std::find(SubLoops.begin(), SubLoops.end(), OldChild);
228 assert(I != SubLoops.end() && "OldChild not in loop!");
230 OldChild->ParentLoop = 0;
231 NewChild->ParentLoop = static_cast<LoopT *>(this);
234 /// verifyLoop - Verify loop structure
235 template<class BlockT, class LoopT>
236 void LoopBase<BlockT, LoopT>::verifyLoop() const {
238 assert(!Blocks.empty() && "Loop header is missing");
240 // Setup for using a depth-first iterator to visit every block in the loop.
241 SmallVector<BlockT*, 8> ExitBBs;
242 getExitBlocks(ExitBBs);
243 llvm::SmallPtrSet<BlockT*, 8> VisitSet;
244 VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
245 df_ext_iterator<BlockT*, llvm::SmallPtrSet<BlockT*, 8> >
246 BI = df_ext_begin(getHeader(), VisitSet),
247 BE = df_ext_end(getHeader(), VisitSet);
249 // Keep track of the number of BBs visited.
250 unsigned NumVisited = 0;
252 // Sort the blocks vector so that we can use binary search to do quick
254 SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
255 std::sort(LoopBBs.begin(), LoopBBs.end());
257 // Check the individual blocks.
258 for ( ; BI != BE; ++BI) {
260 bool HasInsideLoopSuccs = false;
261 bool HasInsideLoopPreds = false;
262 SmallVector<BlockT *, 2> OutsideLoopPreds;
264 typedef GraphTraits<BlockT*> BlockTraits;
265 for (typename BlockTraits::ChildIteratorType SI =
266 BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB);
268 if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *SI)) {
269 HasInsideLoopSuccs = true;
272 typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
273 for (typename InvBlockTraits::ChildIteratorType PI =
274 InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);
277 if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), N))
278 HasInsideLoopPreds = true;
280 OutsideLoopPreds.push_back(N);
283 if (BB == getHeader()) {
284 assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
285 } else if (!OutsideLoopPreds.empty()) {
286 // A non-header loop shouldn't be reachable from outside the loop,
287 // though it is permitted if the predecessor is not itself actually
289 BlockT *EntryBB = BB->getParent()->begin();
290 for (df_iterator<BlockT *> NI = df_begin(EntryBB),
291 NE = df_end(EntryBB); NI != NE; ++NI)
292 for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
293 assert(*NI != OutsideLoopPreds[i] &&
294 "Loop has multiple entry points!");
296 assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!");
297 assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!");
298 assert(BB != getHeader()->getParent()->begin() &&
299 "Loop contains function entry block!");
304 assert(NumVisited == getNumBlocks() && "Unreachable block in loop");
306 // Check the subloops.
307 for (iterator I = begin(), E = end(); I != E; ++I)
308 // Each block in each subloop should be contained within this loop.
309 for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
311 assert(std::binary_search(LoopBBs.begin(), LoopBBs.end(), *BI) &&
312 "Loop does not contain all the blocks of a subloop!");
315 // Check the parent loop pointer.
317 assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) !=
319 "Loop is not a subloop of its parent!");
324 /// verifyLoop - Verify loop structure of this loop and all nested loops.
325 template<class BlockT, class LoopT>
326 void LoopBase<BlockT, LoopT>::verifyLoopNest(
327 DenseSet<const LoopT*> *Loops) const {
328 Loops->insert(static_cast<const LoopT *>(this));
331 // Verify the subloops.
332 for (iterator I = begin(), E = end(); I != E; ++I)
333 (*I)->verifyLoopNest(Loops);
336 template<class BlockT, class LoopT>
337 void LoopBase<BlockT, LoopT>::print(raw_ostream &OS, unsigned Depth) const {
338 OS.indent(Depth*2) << "Loop at depth " << getLoopDepth()
341 for (unsigned i = 0; i < getBlocks().size(); ++i) {
343 BlockT *BB = getBlocks()[i];
344 WriteAsOperand(OS, BB, false);
345 if (BB == getHeader()) OS << "<header>";
346 if (BB == getLoopLatch()) OS << "<latch>";
347 if (isLoopExiting(BB)) OS << "<exiting>";
351 for (iterator I = begin(), E = end(); I != E; ++I)
352 (*I)->print(OS, Depth+2);
355 //===----------------------------------------------------------------------===//
356 /// LoopInfo - This class builds and contains all of the top level loop
357 /// structures in the specified function.
360 template<class BlockT, class LoopT>
361 void LoopInfoBase<BlockT, LoopT>::Calculate(DominatorTreeBase<BlockT> &DT) {
362 BlockT *RootNode = DT.getRootNode()->getBlock();
364 for (df_iterator<BlockT*> NI = df_begin(RootNode),
365 NE = df_end(RootNode); NI != NE; ++NI)
366 if (LoopT *L = ConsiderForLoop(*NI, DT))
367 TopLevelLoops.push_back(L);
370 template<class BlockT, class LoopT>
371 LoopT *LoopInfoBase<BlockT, LoopT>::
372 ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) {
373 if (BBMap.count(BB)) return 0; // Haven't processed this node?
375 std::vector<BlockT *> TodoStack;
377 // Scan the predecessors of BB, checking to see if BB dominates any of
378 // them. This identifies backedges which target this node...
379 typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
380 for (typename InvBlockTraits::ChildIteratorType I =
381 InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB);
383 typename InvBlockTraits::NodeType *N = *I;
384 // If BB dominates its predecessor...
385 if (DT.dominates(BB, N) && DT.isReachableFromEntry(N))
386 TodoStack.push_back(N);
389 if (TodoStack.empty()) return 0; // No backedges to this block...
391 // Create a new loop to represent this basic block...
392 LoopT *L = new LoopT(BB);
395 while (!TodoStack.empty()) { // Process all the nodes in the loop
396 BlockT *X = TodoStack.back();
397 TodoStack.pop_back();
399 if (!L->contains(X) && // As of yet unprocessed??
400 DT.isReachableFromEntry(X)) {
401 // Check to see if this block already belongs to a loop. If this occurs
402 // then we have a case where a loop that is supposed to be a child of
403 // the current loop was processed before the current loop. When this
404 // occurs, this child loop gets added to a part of the current loop,
405 // making it a sibling to the current loop. We have to reparent this
408 const_cast<LoopT *>(getLoopFor(X)))
409 if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){
410 // Remove the subloop from its current parent...
411 assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L);
412 LoopT *SLP = SubLoop->ParentLoop; // SubLoopParent
413 typename std::vector<LoopT *>::iterator I =
414 std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop);
415 assert(I != SLP->SubLoops.end() &&"SubLoop not a child of parent?");
416 SLP->SubLoops.erase(I); // Remove from parent...
418 // Add the subloop to THIS loop...
419 SubLoop->ParentLoop = L;
420 L->SubLoops.push_back(SubLoop);
423 // Normal case, add the block to our loop...
424 L->Blocks.push_back(X);
426 typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
428 // Add all of the predecessors of X to the end of the work stack...
429 TodoStack.insert(TodoStack.end(), InvBlockTraits::child_begin(X),
430 InvBlockTraits::child_end(X));
434 // If there are any loops nested within this loop, create them now!
435 for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),
436 E = L->Blocks.end(); I != E; ++I)
437 if (LoopT *NewLoop = ConsiderForLoop(*I, DT)) {
438 L->SubLoops.push_back(NewLoop);
439 NewLoop->ParentLoop = L;
442 // Add the basic blocks that comprise this loop to the BBMap so that this
443 // loop can be found for them.
445 for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),
446 E = L->Blocks.end(); I != E; ++I)
447 BBMap.insert(std::make_pair(*I, L));
449 // Now that we have a list of all of the child loops of this loop, check to
450 // see if any of them should actually be nested inside of each other. We
451 // can accidentally pull loops our of their parents, so we must make sure to
452 // organize the loop nests correctly now.
454 std::map<BlockT *, LoopT *> ContainingLoops;
455 for (unsigned i = 0; i != L->SubLoops.size(); ++i) {
456 LoopT *Child = L->SubLoops[i];
457 assert(Child->getParentLoop() == L && "Not proper child loop?");
459 if (LoopT *ContainingLoop = ContainingLoops[Child->getHeader()]) {
460 // If there is already a loop which contains this loop, move this loop
461 // into the containing loop.
462 MoveSiblingLoopInto(Child, ContainingLoop);
463 --i; // The loop got removed from the SubLoops list.
465 // This is currently considered to be a top-level loop. Check to see
466 // if any of the contained blocks are loop headers for subloops we
467 // have already processed.
468 for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) {
469 LoopT *&BlockLoop = ContainingLoops[Child->Blocks[b]];
470 if (BlockLoop == 0) { // Child block not processed yet...
472 } else if (BlockLoop != Child) {
473 LoopT *SubLoop = BlockLoop;
474 // Reparent all of the blocks which used to belong to BlockLoops
475 for (unsigned j = 0, f = SubLoop->Blocks.size(); j != f; ++j)
476 ContainingLoops[SubLoop->Blocks[j]] = Child;
478 // There is already a loop which contains this block, that means
479 // that we should reparent the loop which the block is currently
480 // considered to belong to to be a child of this loop.
481 MoveSiblingLoopInto(SubLoop, Child);
482 --i; // We just shrunk the SubLoops list.
492 /// MoveSiblingLoopInto - This method moves the NewChild loop to live inside
493 /// of the NewParent Loop, instead of being a sibling of it.
494 template<class BlockT, class LoopT>
495 void LoopInfoBase<BlockT, LoopT>::
496 MoveSiblingLoopInto(LoopT *NewChild, LoopT *NewParent) {
497 LoopT *OldParent = NewChild->getParentLoop();
498 assert(OldParent && OldParent == NewParent->getParentLoop() &&
499 NewChild != NewParent && "Not sibling loops!");
501 // Remove NewChild from being a child of OldParent
502 typename std::vector<LoopT *>::iterator I =
503 std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(),
505 assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??");
506 OldParent->SubLoops.erase(I); // Remove from parent's subloops list
507 NewChild->ParentLoop = 0;
509 InsertLoopInto(NewChild, NewParent);
512 /// InsertLoopInto - This inserts loop L into the specified parent loop. If
513 /// the parent loop contains a loop which should contain L, the loop gets
514 /// inserted into L instead.
515 template<class BlockT, class LoopT>
516 void LoopInfoBase<BlockT, LoopT>::InsertLoopInto(LoopT *L, LoopT *Parent) {
517 BlockT *LHeader = L->getHeader();
518 assert(Parent->contains(LHeader) &&
519 "This loop should not be inserted here!");
521 // Check to see if it belongs in a child loop...
522 for (unsigned i = 0, e = static_cast<unsigned>(Parent->SubLoops.size());
524 if (Parent->SubLoops[i]->contains(LHeader)) {
525 InsertLoopInto(L, Parent->SubLoops[i]);
529 // If not, insert it here!
530 Parent->SubLoops.push_back(L);
531 L->ParentLoop = Parent;
535 template<class BlockT, class LoopT>
536 void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const {
537 for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
538 TopLevelLoops[i]->print(OS);
540 for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
541 E = BBMap.end(); I != E; ++I)
542 OS << "BB '" << I->first->getName() << "' level = "
543 << I->second->getLoopDepth() << "\n";
547 } // End llvm namespace