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