1 //===- llvm/Analysis/LoopInfoImpl.h - Natural Loop Calculator ---*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This is the generic implementation of LoopInfo used for both Loops and 11 // MachineLoops. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_ANALYSIS_LOOP_INFO_IMPL_H 16 #define LLVM_ANALYSIS_LOOP_INFO_IMPL_H 17 18 #include "llvm/Analysis/LoopInfo.h" 19 #include "llvm/ADT/PostOrderIterator.h" 20 21 namespace llvm { 22 23 //===----------------------------------------------------------------------===// 24 // APIs for simple analysis of the loop. See header notes. 25 26 /// getExitingBlocks - Return all blocks inside the loop that have successors 27 /// outside of the loop. These are the blocks _inside of the current loop_ 28 /// which branch out. The returned list is always unique. 29 /// 30 template<class BlockT, class LoopT> 31 void LoopBase<BlockT, LoopT>:: 32 getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const { 33 // Sort the blocks vector so that we can use binary search to do quick 34 // lookups. 35 SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 36 std::sort(LoopBBs.begin(), LoopBBs.end()); 37 38 typedef GraphTraits<BlockT*> BlockTraits; 39 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) 40 for (typename BlockTraits::ChildIteratorType I = 41 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 42 I != E; ++I) 43 if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) { 44 // Not in current loop? It must be an exit block. 45 ExitingBlocks.push_back(*BI); 46 break; 47 } 48 } 49 50 /// getExitingBlock - If getExitingBlocks would return exactly one block, 51 /// return that block. Otherwise return null. 52 template<class BlockT, class LoopT> 53 BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const { 54 SmallVector<BlockT*, 8> ExitingBlocks; 55 getExitingBlocks(ExitingBlocks); 56 if (ExitingBlocks.size() == 1) 57 return ExitingBlocks[0]; 58 return 0; 59 } 60 61 /// getExitBlocks - Return all of the successor blocks of this loop. These 62 /// are the blocks _outside of the current loop_ which are branched to. 63 /// 64 template<class BlockT, class LoopT> 65 void LoopBase<BlockT, LoopT>:: 66 getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const { 67 // Sort the blocks vector so that we can use binary search to do quick 68 // lookups. 69 SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 70 std::sort(LoopBBs.begin(), LoopBBs.end()); 71 72 typedef GraphTraits<BlockT*> BlockTraits; 73 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) 74 for (typename BlockTraits::ChildIteratorType I = 75 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 76 I != E; ++I) 77 if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 78 // Not in current loop? It must be an exit block. 79 ExitBlocks.push_back(*I); 80 } 81 82 /// getExitBlock - If getExitBlocks would return exactly one block, 83 /// return that block. Otherwise return null. 84 template<class BlockT, class LoopT> 85 BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const { 86 SmallVector<BlockT*, 8> ExitBlocks; 87 getExitBlocks(ExitBlocks); 88 if (ExitBlocks.size() == 1) 89 return ExitBlocks[0]; 90 return 0; 91 } 92 93 /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_). 94 template<class BlockT, class LoopT> 95 void LoopBase<BlockT, LoopT>:: 96 getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const { 97 // Sort the blocks vector so that we can use binary search to do quick 98 // lookups. 99 SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 100 array_pod_sort(LoopBBs.begin(), LoopBBs.end()); 101 102 typedef GraphTraits<BlockT*> BlockTraits; 103 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) 104 for (typename BlockTraits::ChildIteratorType I = 105 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 106 I != E; ++I) 107 if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 108 // Not in current loop? It must be an exit block. 109 ExitEdges.push_back(Edge(*BI, *I)); 110 } 111 112 /// getLoopPreheader - If there is a preheader for this loop, return it. A 113 /// loop has a preheader if there is only one edge to the header of the loop 114 /// from outside of the loop. If this is the case, the block branching to the 115 /// header of the loop is the preheader node. 116 /// 117 /// This method returns null if there is no preheader for the loop. 118 /// 119 template<class BlockT, class LoopT> 120 BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const { 121 // Keep track of nodes outside the loop branching to the header... 122 BlockT *Out = getLoopPredecessor(); 123 if (!Out) return 0; 124 125 // Make sure there is only one exit out of the preheader. 126 typedef GraphTraits<BlockT*> BlockTraits; 127 typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out); 128 ++SI; 129 if (SI != BlockTraits::child_end(Out)) 130 return 0; // Multiple exits from the block, must not be a preheader. 131 132 // The predecessor has exactly one successor, so it is a preheader. 133 return Out; 134 } 135 136 /// getLoopPredecessor - If the given loop's header has exactly one unique 137 /// predecessor outside the loop, return it. Otherwise return null. 138 /// This is less strict that the loop "preheader" concept, which requires 139 /// the predecessor to have exactly one successor. 140 /// 141 template<class BlockT, class LoopT> 142 BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const { 143 // Keep track of nodes outside the loop branching to the header... 144 BlockT *Out = 0; 145 146 // Loop over the predecessors of the header node... 147 BlockT *Header = getHeader(); 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... 154 if (Out && Out != N) 155 return 0; // Multiple predecessors outside the loop 156 Out = N; 157 } 158 } 159 160 // Make sure there is only one exit out of the preheader. 161 assert(Out && "Header of loop has no predecessors from outside loop?"); 162 return Out; 163 } 164 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); 175 BlockT *Latch = 0; 176 for (; PI != PE; ++PI) { 177 typename InvBlockTraits::NodeType *N = *PI; 178 if (contains(N)) { 179 if (Latch) return 0; 180 Latch = N; 181 } 182 } 183 184 return Latch; 185 } 186 187 //===----------------------------------------------------------------------===// 188 // APIs for updating loop information after changing the CFG 189 // 190 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. 196 /// 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!"); 204 205 LoopT *L = static_cast<LoopT *>(this); 206 207 // Add the loop mapping to the LoopInfo object... 208 LIB.BBMap[NewBB] = L; 209 210 // Add the basic block to this loop and all parent loops... 211 while (L) { 212 L->Blocks.push_back(NewBB); 213 L = L->getParentLoop(); 214 } 215 } 216 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!"); 229 *I = NewChild; 230 OldChild->ParentLoop = 0; 231 NewChild->ParentLoop = static_cast<LoopT *>(this); 232 } 233 234 /// verifyLoop - Verify loop structure 235 template<class BlockT, class LoopT> 236 void LoopBase<BlockT, LoopT>::verifyLoop() const { 237 #ifndef NDEBUG 238 assert(!Blocks.empty() && "Loop header is missing"); 239 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); 248 249 // Keep track of the number of BBs visited. 250 unsigned NumVisited = 0; 251 252 // Sort the blocks vector so that we can use binary search to do quick 253 // lookups. 254 SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 255 std::sort(LoopBBs.begin(), LoopBBs.end()); 256 257 // Check the individual blocks. 258 for ( ; BI != BE; ++BI) { 259 BlockT *BB = *BI; 260 bool HasInsideLoopSuccs = false; 261 bool HasInsideLoopPreds = false; 262 SmallVector<BlockT *, 2> OutsideLoopPreds; 263 264 typedef GraphTraits<BlockT*> BlockTraits; 265 for (typename BlockTraits::ChildIteratorType SI = 266 BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB); 267 SI != SE; ++SI) 268 if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *SI)) { 269 HasInsideLoopSuccs = true; 270 break; 271 } 272 typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 273 for (typename InvBlockTraits::ChildIteratorType PI = 274 InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB); 275 PI != PE; ++PI) { 276 BlockT *N = *PI; 277 if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), N)) 278 HasInsideLoopPreds = true; 279 else 280 OutsideLoopPreds.push_back(N); 281 } 282 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 288 // reachable. 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!"); 295 } 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!"); 300 301 NumVisited++; 302 } 303 304 assert(NumVisited == getNumBlocks() && "Unreachable block in loop"); 305 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(); 310 BI != BE; ++BI) { 311 assert(std::binary_search(LoopBBs.begin(), LoopBBs.end(), *BI) && 312 "Loop does not contain all the blocks of a subloop!"); 313 } 314 315 // Check the parent loop pointer. 316 if (ParentLoop) { 317 assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) != 318 ParentLoop->end() && 319 "Loop is not a subloop of its parent!"); 320 } 321 #endif 322 } 323 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)); 329 // Verify this loop. 330 verifyLoop(); 331 // Verify the subloops. 332 for (iterator I = begin(), E = end(); I != E; ++I) 333 (*I)->verifyLoopNest(Loops); 334 } 335 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() 339 << " containing: "; 340 341 for (unsigned i = 0; i < getBlocks().size(); ++i) { 342 if (i) OS << ","; 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>"; 348 } 349 OS << "\n"; 350 351 for (iterator I = begin(), E = end(); I != E; ++I) 352 (*I)->print(OS, Depth+2); 353 } 354 355 //===----------------------------------------------------------------------===// 356 /// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the 357 /// result does / not depend on use list (block predecessor) order. 358 /// 359 360 /// Discover a subloop with the specified backedges such that: All blocks within 361 /// this loop are mapped to this loop or a subloop. And all subloops within this 362 /// loop have their parent loop set to this loop or a subloop. 363 template<class BlockT, class LoopT> 364 static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT*> Backedges, 365 LoopInfoBase<BlockT, LoopT> *LI, 366 DominatorTreeBase<BlockT> &DomTree) { 367 typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 368 369 unsigned NumBlocks = 0; 370 unsigned NumSubloops = 0; 371 372 // Perform a backward CFG traversal using a worklist. 373 std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end()); 374 while (!ReverseCFGWorklist.empty()) { 375 BlockT *PredBB = ReverseCFGWorklist.back(); 376 ReverseCFGWorklist.pop_back(); 377 378 LoopT *Subloop = LI->getLoopFor(PredBB); 379 if (!Subloop) { 380 if (!DomTree.isReachableFromEntry(PredBB)) 381 continue; 382 383 // This is an undiscovered block. Map it to the current loop. 384 LI->changeLoopFor(PredBB, L); 385 ++NumBlocks; 386 if (PredBB == L->getHeader()) 387 continue; 388 // Push all block predecessors on the worklist. 389 ReverseCFGWorklist.insert(ReverseCFGWorklist.end(), 390 InvBlockTraits::child_begin(PredBB), 391 InvBlockTraits::child_end(PredBB)); 392 } 393 else { 394 // This is a discovered block. Find its outermost discovered loop. 395 while (LoopT *Parent = Subloop->getParentLoop()) 396 Subloop = Parent; 397 398 // If it is already discovered to be a subloop of this loop, continue. 399 if (Subloop == L) 400 continue; 401 402 // Discover a subloop of this loop. 403 Subloop->setParentLoop(L); 404 ++NumSubloops; 405 NumBlocks += Subloop->getBlocks().capacity(); 406 PredBB = Subloop->getHeader(); 407 // Continue traversal along predecessors that are not loop-back edges from 408 // within this subloop tree itself. Note that a predecessor may directly 409 // reach another subloop that is not yet discovered to be a subloop of 410 // this loop, which we must traverse. 411 for (typename InvBlockTraits::ChildIteratorType PI = 412 InvBlockTraits::child_begin(PredBB), 413 PE = InvBlockTraits::child_end(PredBB); PI != PE; ++PI) { 414 if (LI->getLoopFor(*PI) != Subloop) 415 ReverseCFGWorklist.push_back(*PI); 416 } 417 } 418 } 419 L->getSubLoopsVector().reserve(NumSubloops); 420 L->getBlocksVector().reserve(NumBlocks); 421 } 422 423 namespace { 424 /// Populate all loop data in a stable order during a single forward DFS. 425 template<class BlockT, class LoopT> 426 class PopulateLoopsDFS { 427 typedef GraphTraits<BlockT*> BlockTraits; 428 typedef typename BlockTraits::ChildIteratorType SuccIterTy; 429 430 LoopInfoBase<BlockT, LoopT> *LI; 431 DenseSet<const BlockT *> VisitedBlocks; 432 std::vector<std::pair<BlockT*, SuccIterTy> > DFSStack; 433 434 public: 435 PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li): 436 LI(li) {} 437 438 void traverse(BlockT *EntryBlock); 439 440 protected: 441 void insertIntoLoop(BlockT *Block); 442 443 BlockT *dfsSource() { return DFSStack.back().first; } 444 SuccIterTy &dfsSucc() { return DFSStack.back().second; } 445 SuccIterTy dfsSuccEnd() { return BlockTraits::child_end(dfsSource()); } 446 447 void pushBlock(BlockT *Block) { 448 DFSStack.push_back(std::make_pair(Block, BlockTraits::child_begin(Block))); 449 } 450 }; 451 } // anonymous 452 453 /// Top-level driver for the forward DFS within the loop. 454 template<class BlockT, class LoopT> 455 void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) { 456 pushBlock(EntryBlock); 457 VisitedBlocks.insert(EntryBlock); 458 while (!DFSStack.empty()) { 459 // Traverse the leftmost path as far as possible. 460 while (dfsSucc() != dfsSuccEnd()) { 461 BlockT *BB = *dfsSucc(); 462 ++dfsSucc(); 463 if (!VisitedBlocks.insert(BB).second) 464 continue; 465 466 // Push the next DFS successor onto the stack. 467 pushBlock(BB); 468 } 469 // Visit the top of the stack in postorder and backtrack. 470 insertIntoLoop(dfsSource()); 471 DFSStack.pop_back(); 472 } 473 } 474 475 /// Add a single Block to its ancestor loops in PostOrder. If the block is a 476 /// subloop header, add the subloop to its parent in PostOrder, then reverse the 477 /// Block and Subloop vectors of the now complete subloop to achieve RPO. 478 template<class BlockT, class LoopT> 479 void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) { 480 LoopT *Subloop = LI->getLoopFor(Block); 481 if (Subloop && Block == Subloop->getHeader()) { 482 // We reach this point once per subloop after processing all the blocks in 483 // the subloop. 484 if (Subloop->getParentLoop()) 485 Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop); 486 else 487 LI->addTopLevelLoop(Subloop); 488 489 // For convenience, Blocks and Subloops are inserted in postorder. Reverse 490 // the lists, except for the loop header, which is always at the beginning. 491 std::reverse(Subloop->getBlocksVector().begin()+1, 492 Subloop->getBlocksVector().end()); 493 std::reverse(Subloop->getSubLoopsVector().begin(), 494 Subloop->getSubLoopsVector().end()); 495 496 Subloop = Subloop->getParentLoop(); 497 } 498 for (; Subloop; Subloop = Subloop->getParentLoop()) 499 Subloop->getBlocksVector().push_back(Block); 500 } 501 502 /// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal 503 /// interleaved with backward CFG traversals within each subloop 504 /// (discoverAndMapSubloop). The backward traversal skips inner subloops, so 505 /// this part of the algorithm is linear in the number of CFG edges. Subloop and 506 /// Block vectors are then populated during a single forward CFG traversal 507 /// (PopulateLoopDFS). 508 /// 509 /// During the two CFG traversals each block is seen three times: 510 /// 1) Discovered and mapped by a reverse CFG traversal. 511 /// 2) Visited during a forward DFS CFG traversal. 512 /// 3) Reverse-inserted in the loop in postorder following forward DFS. 513 /// 514 /// The Block vectors are inclusive, so step 3 requires loop-depth number of 515 /// insertions per block. 516 template<class BlockT, class LoopT> 517 void LoopInfoBase<BlockT, LoopT>:: 518 Analyze(DominatorTreeBase<BlockT> &DomTree) { 519 520 // Postorder traversal of the dominator tree. 521 DomTreeNodeBase<BlockT>* DomRoot = DomTree.getRootNode(); 522 for (po_iterator<DomTreeNodeBase<BlockT>*> DomIter = po_begin(DomRoot), 523 DomEnd = po_end(DomRoot); DomIter != DomEnd; ++DomIter) { 524 525 BlockT *Header = DomIter->getBlock(); 526 SmallVector<BlockT *, 4> Backedges; 527 528 // Check each predecessor of the potential loop header. 529 typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 530 for (typename InvBlockTraits::ChildIteratorType PI = 531 InvBlockTraits::child_begin(Header), 532 PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) { 533 534 BlockT *Backedge = *PI; 535 536 // If Header dominates predBB, this is a new loop. Collect the backedges. 537 if (DomTree.dominates(Header, Backedge) 538 && DomTree.isReachableFromEntry(Backedge)) { 539 Backedges.push_back(Backedge); 540 } 541 } 542 // Perform a backward CFG traversal to discover and map blocks in this loop. 543 if (!Backedges.empty()) { 544 LoopT *L = new LoopT(Header); 545 discoverAndMapSubloop(L, ArrayRef<BlockT*>(Backedges), this, DomTree); 546 } 547 } 548 // Perform a single forward CFG traversal to populate block and subloop 549 // vectors for all loops. 550 PopulateLoopsDFS<BlockT, LoopT> DFS(this); 551 DFS.traverse(DomRoot->getBlock()); 552 } 553 554 // Debugging 555 template<class BlockT, class LoopT> 556 void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const { 557 for (unsigned i = 0; i < TopLevelLoops.size(); ++i) 558 TopLevelLoops[i]->print(OS); 559 #if 0 560 for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(), 561 E = BBMap.end(); I != E; ++I) 562 OS << "BB '" << I->first->getName() << "' level = " 563 << I->second->getLoopDepth() << "\n"; 564 #endif 565 } 566 567 } // End llvm namespace 568 569 #endif 570