1 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===// 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 file defines the LoopInfo class that is used to identify natural loops 11 // and determine the loop depth of various nodes of the CFG. Note that the 12 // loops identified may actually be several natural loops that share the same 13 // header node... not just a single natural loop. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "llvm/Analysis/LoopInfo.h" 18 #include "llvm/Constants.h" 19 #include "llvm/Instructions.h" 20 #include "llvm/Analysis/Dominators.h" 21 #include "llvm/Analysis/LoopInfoImpl.h" 22 #include "llvm/Analysis/LoopIterator.h" 23 #include "llvm/Analysis/ValueTracking.h" 24 #include "llvm/Assembly/Writer.h" 25 #include "llvm/Support/CFG.h" 26 #include "llvm/Support/CommandLine.h" 27 #include "llvm/Support/Debug.h" 28 #include "llvm/ADT/DepthFirstIterator.h" 29 #include "llvm/ADT/SmallPtrSet.h" 30 #include <algorithm> 31 using namespace llvm; 32 33 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops. 34 template class llvm::LoopBase<BasicBlock, Loop>; 35 template class llvm::LoopInfoBase<BasicBlock, Loop>; 36 37 // Always verify loopinfo if expensive checking is enabled. 38 #ifdef XDEBUG 39 static bool VerifyLoopInfo = true; 40 #else 41 static bool VerifyLoopInfo = false; 42 #endif 43 static cl::opt<bool,true> 44 VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), 45 cl::desc("Verify loop info (time consuming)")); 46 47 char LoopInfo::ID = 0; 48 INITIALIZE_PASS_BEGIN(LoopInfo, "loops", "Natural Loop Information", true, true) 49 INITIALIZE_PASS_DEPENDENCY(DominatorTree) 50 INITIALIZE_PASS_END(LoopInfo, "loops", "Natural Loop Information", true, true) 51 52 //===----------------------------------------------------------------------===// 53 // Loop implementation 54 // 55 56 /// isLoopInvariant - Return true if the specified value is loop invariant 57 /// 58 bool Loop::isLoopInvariant(Value *V) const { 59 if (Instruction *I = dyn_cast<Instruction>(V)) 60 return !contains(I); 61 return true; // All non-instructions are loop invariant 62 } 63 64 /// hasLoopInvariantOperands - Return true if all the operands of the 65 /// specified instruction are loop invariant. 66 bool Loop::hasLoopInvariantOperands(Instruction *I) const { 67 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 68 if (!isLoopInvariant(I->getOperand(i))) 69 return false; 70 71 return true; 72 } 73 74 /// makeLoopInvariant - If the given value is an instruciton inside of the 75 /// loop and it can be hoisted, do so to make it trivially loop-invariant. 76 /// Return true if the value after any hoisting is loop invariant. This 77 /// function can be used as a slightly more aggressive replacement for 78 /// isLoopInvariant. 79 /// 80 /// If InsertPt is specified, it is the point to hoist instructions to. 81 /// If null, the terminator of the loop preheader is used. 82 /// 83 bool Loop::makeLoopInvariant(Value *V, bool &Changed, 84 Instruction *InsertPt) const { 85 if (Instruction *I = dyn_cast<Instruction>(V)) 86 return makeLoopInvariant(I, Changed, InsertPt); 87 return true; // All non-instructions are loop-invariant. 88 } 89 90 /// makeLoopInvariant - If the given instruction is inside of the 91 /// loop and it can be hoisted, do so to make it trivially loop-invariant. 92 /// Return true if the instruction after any hoisting is loop invariant. This 93 /// function can be used as a slightly more aggressive replacement for 94 /// isLoopInvariant. 95 /// 96 /// If InsertPt is specified, it is the point to hoist instructions to. 97 /// If null, the terminator of the loop preheader is used. 98 /// 99 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, 100 Instruction *InsertPt) const { 101 // Test if the value is already loop-invariant. 102 if (isLoopInvariant(I)) 103 return true; 104 if (!isSafeToSpeculativelyExecute(I)) 105 return false; 106 if (I->mayReadFromMemory()) 107 return false; 108 // The landingpad instruction is immobile. 109 if (isa<LandingPadInst>(I)) 110 return false; 111 // Determine the insertion point, unless one was given. 112 if (!InsertPt) { 113 BasicBlock *Preheader = getLoopPreheader(); 114 // Without a preheader, hoisting is not feasible. 115 if (!Preheader) 116 return false; 117 InsertPt = Preheader->getTerminator(); 118 } 119 // Don't hoist instructions with loop-variant operands. 120 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 121 if (!makeLoopInvariant(I->getOperand(i), Changed, InsertPt)) 122 return false; 123 124 // Hoist. 125 I->moveBefore(InsertPt); 126 Changed = true; 127 return true; 128 } 129 130 /// getCanonicalInductionVariable - Check to see if the loop has a canonical 131 /// induction variable: an integer recurrence that starts at 0 and increments 132 /// by one each time through the loop. If so, return the phi node that 133 /// corresponds to it. 134 /// 135 /// The IndVarSimplify pass transforms loops to have a canonical induction 136 /// variable. 137 /// 138 PHINode *Loop::getCanonicalInductionVariable() const { 139 BasicBlock *H = getHeader(); 140 141 BasicBlock *Incoming = 0, *Backedge = 0; 142 pred_iterator PI = pred_begin(H); 143 assert(PI != pred_end(H) && 144 "Loop must have at least one backedge!"); 145 Backedge = *PI++; 146 if (PI == pred_end(H)) return 0; // dead loop 147 Incoming = *PI++; 148 if (PI != pred_end(H)) return 0; // multiple backedges? 149 150 if (contains(Incoming)) { 151 if (contains(Backedge)) 152 return 0; 153 std::swap(Incoming, Backedge); 154 } else if (!contains(Backedge)) 155 return 0; 156 157 // Loop over all of the PHI nodes, looking for a canonical indvar. 158 for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) { 159 PHINode *PN = cast<PHINode>(I); 160 if (ConstantInt *CI = 161 dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming))) 162 if (CI->isNullValue()) 163 if (Instruction *Inc = 164 dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge))) 165 if (Inc->getOpcode() == Instruction::Add && 166 Inc->getOperand(0) == PN) 167 if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1))) 168 if (CI->equalsInt(1)) 169 return PN; 170 } 171 return 0; 172 } 173 174 /// isLCSSAForm - Return true if the Loop is in LCSSA form 175 bool Loop::isLCSSAForm(DominatorTree &DT) const { 176 // Sort the blocks vector so that we can use binary search to do quick 177 // lookups. 178 SmallPtrSet<BasicBlock*, 16> LoopBBs(block_begin(), block_end()); 179 180 for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { 181 BasicBlock *BB = *BI; 182 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) 183 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 184 ++UI) { 185 User *U = *UI; 186 BasicBlock *UserBB = cast<Instruction>(U)->getParent(); 187 if (PHINode *P = dyn_cast<PHINode>(U)) 188 UserBB = P->getIncomingBlock(UI); 189 190 // Check the current block, as a fast-path, before checking whether 191 // the use is anywhere in the loop. Most values are used in the same 192 // block they are defined in. Also, blocks not reachable from the 193 // entry are special; uses in them don't need to go through PHIs. 194 if (UserBB != BB && 195 !LoopBBs.count(UserBB) && 196 DT.isReachableFromEntry(UserBB)) 197 return false; 198 } 199 } 200 201 return true; 202 } 203 204 /// isLoopSimplifyForm - Return true if the Loop is in the form that 205 /// the LoopSimplify form transforms loops to, which is sometimes called 206 /// normal form. 207 bool Loop::isLoopSimplifyForm() const { 208 // Normal-form loops have a preheader, a single backedge, and all of their 209 // exits have all their predecessors inside the loop. 210 return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); 211 } 212 213 /// isSafeToClone - Return true if the loop body is safe to clone in practice. 214 /// Routines that reform the loop CFG and split edges often fail on indirectbr. 215 bool Loop::isSafeToClone() const { 216 // Return false if any loop blocks contain indirectbrs. 217 for (Loop::block_iterator I = block_begin(), E = block_end(); I != E; ++I) { 218 if (isa<IndirectBrInst>((*I)->getTerminator())) 219 return false; 220 } 221 return true; 222 } 223 224 /// hasDedicatedExits - Return true if no exit block for the loop 225 /// has a predecessor that is outside the loop. 226 bool Loop::hasDedicatedExits() const { 227 // Sort the blocks vector so that we can use binary search to do quick 228 // lookups. 229 SmallPtrSet<BasicBlock *, 16> LoopBBs(block_begin(), block_end()); 230 // Each predecessor of each exit block of a normal loop is contained 231 // within the loop. 232 SmallVector<BasicBlock *, 4> ExitBlocks; 233 getExitBlocks(ExitBlocks); 234 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 235 for (pred_iterator PI = pred_begin(ExitBlocks[i]), 236 PE = pred_end(ExitBlocks[i]); PI != PE; ++PI) 237 if (!LoopBBs.count(*PI)) 238 return false; 239 // All the requirements are met. 240 return true; 241 } 242 243 /// getUniqueExitBlocks - Return all unique successor blocks of this loop. 244 /// These are the blocks _outside of the current loop_ which are branched to. 245 /// This assumes that loop exits are in canonical form. 246 /// 247 void 248 Loop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const { 249 assert(hasDedicatedExits() && 250 "getUniqueExitBlocks assumes the loop has canonical form exits!"); 251 252 // Sort the blocks vector so that we can use binary search to do quick 253 // lookups. 254 SmallVector<BasicBlock *, 128> LoopBBs(block_begin(), block_end()); 255 std::sort(LoopBBs.begin(), LoopBBs.end()); 256 257 SmallVector<BasicBlock *, 32> switchExitBlocks; 258 259 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { 260 261 BasicBlock *current = *BI; 262 switchExitBlocks.clear(); 263 264 for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I) { 265 // If block is inside the loop then it is not a exit block. 266 if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 267 continue; 268 269 pred_iterator PI = pred_begin(*I); 270 BasicBlock *firstPred = *PI; 271 272 // If current basic block is this exit block's first predecessor 273 // then only insert exit block in to the output ExitBlocks vector. 274 // This ensures that same exit block is not inserted twice into 275 // ExitBlocks vector. 276 if (current != firstPred) 277 continue; 278 279 // If a terminator has more then two successors, for example SwitchInst, 280 // then it is possible that there are multiple edges from current block 281 // to one exit block. 282 if (std::distance(succ_begin(current), succ_end(current)) <= 2) { 283 ExitBlocks.push_back(*I); 284 continue; 285 } 286 287 // In case of multiple edges from current block to exit block, collect 288 // only one edge in ExitBlocks. Use switchExitBlocks to keep track of 289 // duplicate edges. 290 if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) 291 == switchExitBlocks.end()) { 292 switchExitBlocks.push_back(*I); 293 ExitBlocks.push_back(*I); 294 } 295 } 296 } 297 } 298 299 /// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one 300 /// block, return that block. Otherwise return null. 301 BasicBlock *Loop::getUniqueExitBlock() const { 302 SmallVector<BasicBlock *, 8> UniqueExitBlocks; 303 getUniqueExitBlocks(UniqueExitBlocks); 304 if (UniqueExitBlocks.size() == 1) 305 return UniqueExitBlocks[0]; 306 return 0; 307 } 308 309 #ifndef NDEBUG 310 void Loop::dump() const { 311 print(dbgs()); 312 } 313 #endif 314 315 //===----------------------------------------------------------------------===// 316 // UnloopUpdater implementation 317 // 318 319 namespace { 320 /// Find the new parent loop for all blocks within the "unloop" whose last 321 /// backedges has just been removed. 322 class UnloopUpdater { 323 Loop *Unloop; 324 LoopInfo *LI; 325 326 LoopBlocksDFS DFS; 327 328 // Map unloop's immediate subloops to their nearest reachable parents. Nested 329 // loops within these subloops will not change parents. However, an immediate 330 // subloop's new parent will be the nearest loop reachable from either its own 331 // exits *or* any of its nested loop's exits. 332 DenseMap<Loop*, Loop*> SubloopParents; 333 334 // Flag the presence of an irreducible backedge whose destination is a block 335 // directly contained by the original unloop. 336 bool FoundIB; 337 338 public: 339 UnloopUpdater(Loop *UL, LoopInfo *LInfo) : 340 Unloop(UL), LI(LInfo), DFS(UL), FoundIB(false) {} 341 342 void updateBlockParents(); 343 344 void removeBlocksFromAncestors(); 345 346 void updateSubloopParents(); 347 348 protected: 349 Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop); 350 }; 351 } // end anonymous namespace 352 353 /// updateBlockParents - Update the parent loop for all blocks that are directly 354 /// contained within the original "unloop". 355 void UnloopUpdater::updateBlockParents() { 356 if (Unloop->getNumBlocks()) { 357 // Perform a post order CFG traversal of all blocks within this loop, 358 // propagating the nearest loop from sucessors to predecessors. 359 LoopBlocksTraversal Traversal(DFS, LI); 360 for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), 361 POE = Traversal.end(); POI != POE; ++POI) { 362 363 Loop *L = LI->getLoopFor(*POI); 364 Loop *NL = getNearestLoop(*POI, L); 365 366 if (NL != L) { 367 // For reducible loops, NL is now an ancestor of Unloop. 368 assert((NL != Unloop && (!NL || NL->contains(Unloop))) && 369 "uninitialized successor"); 370 LI->changeLoopFor(*POI, NL); 371 } 372 else { 373 // Or the current block is part of a subloop, in which case its parent 374 // is unchanged. 375 assert((FoundIB || Unloop->contains(L)) && "uninitialized successor"); 376 } 377 } 378 } 379 // Each irreducible loop within the unloop induces a round of iteration using 380 // the DFS result cached by Traversal. 381 bool Changed = FoundIB; 382 for (unsigned NIters = 0; Changed; ++NIters) { 383 assert(NIters < Unloop->getNumBlocks() && "runaway iterative algorithm"); 384 385 // Iterate over the postorder list of blocks, propagating the nearest loop 386 // from successors to predecessors as before. 387 Changed = false; 388 for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(), 389 POE = DFS.endPostorder(); POI != POE; ++POI) { 390 391 Loop *L = LI->getLoopFor(*POI); 392 Loop *NL = getNearestLoop(*POI, L); 393 if (NL != L) { 394 assert(NL != Unloop && (!NL || NL->contains(Unloop)) && 395 "uninitialized successor"); 396 LI->changeLoopFor(*POI, NL); 397 Changed = true; 398 } 399 } 400 } 401 } 402 403 /// removeBlocksFromAncestors - Remove unloop's blocks from all ancestors below 404 /// their new parents. 405 void UnloopUpdater::removeBlocksFromAncestors() { 406 // Remove all unloop's blocks (including those in nested subloops) from 407 // ancestors below the new parent loop. 408 for (Loop::block_iterator BI = Unloop->block_begin(), 409 BE = Unloop->block_end(); BI != BE; ++BI) { 410 Loop *OuterParent = LI->getLoopFor(*BI); 411 if (Unloop->contains(OuterParent)) { 412 while (OuterParent->getParentLoop() != Unloop) 413 OuterParent = OuterParent->getParentLoop(); 414 OuterParent = SubloopParents[OuterParent]; 415 } 416 // Remove blocks from former Ancestors except Unloop itself which will be 417 // deleted. 418 for (Loop *OldParent = Unloop->getParentLoop(); OldParent != OuterParent; 419 OldParent = OldParent->getParentLoop()) { 420 assert(OldParent && "new loop is not an ancestor of the original"); 421 OldParent->removeBlockFromLoop(*BI); 422 } 423 } 424 } 425 426 /// updateSubloopParents - Update the parent loop for all subloops directly 427 /// nested within unloop. 428 void UnloopUpdater::updateSubloopParents() { 429 while (!Unloop->empty()) { 430 Loop *Subloop = *llvm::prior(Unloop->end()); 431 Unloop->removeChildLoop(llvm::prior(Unloop->end())); 432 433 assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop"); 434 if (Loop *Parent = SubloopParents[Subloop]) 435 Parent->addChildLoop(Subloop); 436 else 437 LI->addTopLevelLoop(Subloop); 438 } 439 } 440 441 /// getNearestLoop - Return the nearest parent loop among this block's 442 /// successors. If a successor is a subloop header, consider its parent to be 443 /// the nearest parent of the subloop's exits. 444 /// 445 /// For subloop blocks, simply update SubloopParents and return NULL. 446 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { 447 448 // Initially for blocks directly contained by Unloop, NearLoop == Unloop and 449 // is considered uninitialized. 450 Loop *NearLoop = BBLoop; 451 452 Loop *Subloop = 0; 453 if (NearLoop != Unloop && Unloop->contains(NearLoop)) { 454 Subloop = NearLoop; 455 // Find the subloop ancestor that is directly contained within Unloop. 456 while (Subloop->getParentLoop() != Unloop) { 457 Subloop = Subloop->getParentLoop(); 458 assert(Subloop && "subloop is not an ancestor of the original loop"); 459 } 460 // Get the current nearest parent of the Subloop exits, initially Unloop. 461 NearLoop = 462 SubloopParents.insert(std::make_pair(Subloop, Unloop)).first->second; 463 } 464 465 succ_iterator I = succ_begin(BB), E = succ_end(BB); 466 if (I == E) { 467 assert(!Subloop && "subloop blocks must have a successor"); 468 NearLoop = 0; // unloop blocks may now exit the function. 469 } 470 for (; I != E; ++I) { 471 if (*I == BB) 472 continue; // self loops are uninteresting 473 474 Loop *L = LI->getLoopFor(*I); 475 if (L == Unloop) { 476 // This successor has not been processed. This path must lead to an 477 // irreducible backedge. 478 assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB"); 479 FoundIB = true; 480 } 481 if (L != Unloop && Unloop->contains(L)) { 482 // Successor is in a subloop. 483 if (Subloop) 484 continue; // Branching within subloops. Ignore it. 485 486 // BB branches from the original into a subloop header. 487 assert(L->getParentLoop() == Unloop && "cannot skip into nested loops"); 488 489 // Get the current nearest parent of the Subloop's exits. 490 L = SubloopParents[L]; 491 // L could be Unloop if the only exit was an irreducible backedge. 492 } 493 if (L == Unloop) { 494 continue; 495 } 496 // Handle critical edges from Unloop into a sibling loop. 497 if (L && !L->contains(Unloop)) { 498 L = L->getParentLoop(); 499 } 500 // Remember the nearest parent loop among successors or subloop exits. 501 if (NearLoop == Unloop || !NearLoop || NearLoop->contains(L)) 502 NearLoop = L; 503 } 504 if (Subloop) { 505 SubloopParents[Subloop] = NearLoop; 506 return BBLoop; 507 } 508 return NearLoop; 509 } 510 511 //===----------------------------------------------------------------------===// 512 // LoopInfo implementation 513 // 514 bool LoopInfo::runOnFunction(Function &) { 515 releaseMemory(); 516 LI.Analyze(getAnalysis<DominatorTree>().getBase()); 517 return false; 518 } 519 520 /// updateUnloop - The last backedge has been removed from a loop--now the 521 /// "unloop". Find a new parent for the blocks contained within unloop and 522 /// update the loop tree. We don't necessarily have valid dominators at this 523 /// point, but LoopInfo is still valid except for the removal of this loop. 524 /// 525 /// Note that Unloop may now be an empty loop. Calling Loop::getHeader without 526 /// checking first is illegal. 527 void LoopInfo::updateUnloop(Loop *Unloop) { 528 529 // First handle the special case of no parent loop to simplify the algorithm. 530 if (!Unloop->getParentLoop()) { 531 // Since BBLoop had no parent, Unloop blocks are no longer in a loop. 532 for (Loop::block_iterator I = Unloop->block_begin(), 533 E = Unloop->block_end(); I != E; ++I) { 534 535 // Don't reparent blocks in subloops. 536 if (getLoopFor(*I) != Unloop) 537 continue; 538 539 // Blocks no longer have a parent but are still referenced by Unloop until 540 // the Unloop object is deleted. 541 LI.changeLoopFor(*I, 0); 542 } 543 544 // Remove the loop from the top-level LoopInfo object. 545 for (LoopInfo::iterator I = LI.begin();; ++I) { 546 assert(I != LI.end() && "Couldn't find loop"); 547 if (*I == Unloop) { 548 LI.removeLoop(I); 549 break; 550 } 551 } 552 553 // Move all of the subloops to the top-level. 554 while (!Unloop->empty()) 555 LI.addTopLevelLoop(Unloop->removeChildLoop(llvm::prior(Unloop->end()))); 556 557 return; 558 } 559 560 // Update the parent loop for all blocks within the loop. Blocks within 561 // subloops will not change parents. 562 UnloopUpdater Updater(Unloop, this); 563 Updater.updateBlockParents(); 564 565 // Remove blocks from former ancestor loops. 566 Updater.removeBlocksFromAncestors(); 567 568 // Add direct subloops as children in their new parent loop. 569 Updater.updateSubloopParents(); 570 571 // Remove unloop from its parent loop. 572 Loop *ParentLoop = Unloop->getParentLoop(); 573 for (Loop::iterator I = ParentLoop->begin();; ++I) { 574 assert(I != ParentLoop->end() && "Couldn't find loop"); 575 if (*I == Unloop) { 576 ParentLoop->removeChildLoop(I); 577 break; 578 } 579 } 580 } 581 582 void LoopInfo::verifyAnalysis() const { 583 // LoopInfo is a FunctionPass, but verifying every loop in the function 584 // each time verifyAnalysis is called is very expensive. The 585 // -verify-loop-info option can enable this. In order to perform some 586 // checking by default, LoopPass has been taught to call verifyLoop 587 // manually during loop pass sequences. 588 589 if (!VerifyLoopInfo) return; 590 591 DenseSet<const Loop*> Loops; 592 for (iterator I = begin(), E = end(); I != E; ++I) { 593 assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); 594 (*I)->verifyLoopNest(&Loops); 595 } 596 597 // Verify that blocks are mapped to valid loops. 598 for (DenseMap<BasicBlock*, Loop*>::const_iterator I = LI.BBMap.begin(), 599 E = LI.BBMap.end(); I != E; ++I) { 600 assert(Loops.count(I->second) && "orphaned loop"); 601 assert(I->second->contains(I->first) && "orphaned block"); 602 } 603 } 604 605 void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { 606 AU.setPreservesAll(); 607 AU.addRequired<DominatorTree>(); 608 } 609 610 void LoopInfo::print(raw_ostream &OS, const Module*) const { 611 LI.print(OS); 612 } 613 614 //===----------------------------------------------------------------------===// 615 // LoopBlocksDFS implementation 616 // 617 618 /// Traverse the loop blocks and store the DFS result. 619 /// Useful for clients that just want the final DFS result and don't need to 620 /// visit blocks during the initial traversal. 621 void LoopBlocksDFS::perform(LoopInfo *LI) { 622 LoopBlocksTraversal Traversal(*this, LI); 623 for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), 624 POE = Traversal.end(); POI != POE; ++POI) ; 625 } 626