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