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