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