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