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 // EH block instructions are immobile. 106 if (I->isEHPad()) 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 124 // There is possibility of hoisting this instruction above some arbitrary 125 // condition. Any metadata defined on it can be control dependent on this 126 // condition. Conservatively strip it here so that we don't give any wrong 127 // information to the optimizer. 128 I->dropUnknownNonDebugMetadata(); 129 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 = nullptr, *Backedge = nullptr; 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 nullptr; // dead loop 151 Incoming = *PI++; 152 if (PI != pred_end(H)) return nullptr; // multiple backedges? 153 154 if (contains(Incoming)) { 155 if (contains(Backedge)) 156 return nullptr; 157 std::swap(Incoming, Backedge); 158 } else if (!contains(Backedge)) 159 return nullptr; 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 nullptr; 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 // Tokens can't be used in PHI nodes and live-out tokens prevent loop 184 // optimizations, so for the purposes of considered LCSSA form, we 185 // can ignore them. 186 if (I->getType()->isTokenTy()) 187 continue; 188 189 for (Use &U : I->uses()) { 190 Instruction *UI = cast<Instruction>(U.getUser()); 191 BasicBlock *UserBB = UI->getParent(); 192 if (PHINode *P = dyn_cast<PHINode>(UI)) 193 UserBB = P->getIncomingBlock(U); 194 195 // Check the current block, as a fast-path, before checking whether 196 // the use is anywhere in the loop. Most values are used in the same 197 // block they are defined in. Also, blocks not reachable from the 198 // entry are special; uses in them don't need to go through PHIs. 199 if (UserBB != BB && 200 !contains(UserBB) && 201 DT.isReachableFromEntry(UserBB)) 202 return false; 203 } 204 } 205 } 206 207 return true; 208} 209 210bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT) const { 211 if (!isLCSSAForm(DT)) 212 return false; 213 214 return std::all_of(begin(), end(), [&](const Loop *L) { 215 return L->isRecursivelyLCSSAForm(DT); 216 }); 217} 218 219/// isLoopSimplifyForm - Return true if the Loop is in the form that 220/// the LoopSimplify form transforms loops to, which is sometimes called 221/// normal form. 222bool Loop::isLoopSimplifyForm() const { 223 // Normal-form loops have a preheader, a single backedge, and all of their 224 // exits have all their predecessors inside the loop. 225 return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); 226} 227 228/// isSafeToClone - Return true if the loop body is safe to clone in practice. 229/// Routines that reform the loop CFG and split edges often fail on indirectbr. 230bool Loop::isSafeToClone() const { 231 // Return false if any loop blocks contain indirectbrs, or there are any calls 232 // to noduplicate functions. 233 for (Loop::block_iterator I = block_begin(), E = block_end(); I != E; ++I) { 234 if (isa<IndirectBrInst>((*I)->getTerminator())) 235 return false; 236 237 if (const InvokeInst *II = dyn_cast<InvokeInst>((*I)->getTerminator())) { 238 if (II->cannotDuplicate()) 239 return false; 240 // Return false if any loop blocks contain invokes to EH-pads other than 241 // landingpads; we don't know how to split those edges yet. 242 auto *FirstNonPHI = II->getUnwindDest()->getFirstNonPHI(); 243 if (FirstNonPHI->isEHPad() && !isa<LandingPadInst>(FirstNonPHI)) 244 return false; 245 } 246 247 for (BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end(); BI != BE; ++BI) { 248 if (const CallInst *CI = dyn_cast<CallInst>(BI)) { 249 if (CI->cannotDuplicate()) 250 return false; 251 } 252 if (BI->getType()->isTokenTy() && BI->isUsedOutsideOfBlock(*I)) 253 return false; 254 } 255 } 256 return true; 257} 258 259MDNode *Loop::getLoopID() const { 260 MDNode *LoopID = nullptr; 261 if (isLoopSimplifyForm()) { 262 LoopID = getLoopLatch()->getTerminator()->getMetadata(LoopMDName); 263 } else { 264 // Go through each predecessor of the loop header and check the 265 // terminator for the metadata. 266 BasicBlock *H = getHeader(); 267 for (block_iterator I = block_begin(), IE = block_end(); I != IE; ++I) { 268 TerminatorInst *TI = (*I)->getTerminator(); 269 MDNode *MD = nullptr; 270 271 // Check if this terminator branches to the loop header. 272 for (unsigned i = 0, ie = TI->getNumSuccessors(); i != ie; ++i) { 273 if (TI->getSuccessor(i) == H) { 274 MD = TI->getMetadata(LoopMDName); 275 break; 276 } 277 } 278 if (!MD) 279 return nullptr; 280 281 if (!LoopID) 282 LoopID = MD; 283 else if (MD != LoopID) 284 return nullptr; 285 } 286 } 287 if (!LoopID || LoopID->getNumOperands() == 0 || 288 LoopID->getOperand(0) != LoopID) 289 return nullptr; 290 return LoopID; 291} 292 293void Loop::setLoopID(MDNode *LoopID) const { 294 assert(LoopID && "Loop ID should not be null"); 295 assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand"); 296 assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself"); 297 298 if (isLoopSimplifyForm()) { 299 getLoopLatch()->getTerminator()->setMetadata(LoopMDName, LoopID); 300 return; 301 } 302 303 BasicBlock *H = getHeader(); 304 for (block_iterator I = block_begin(), IE = block_end(); I != IE; ++I) { 305 TerminatorInst *TI = (*I)->getTerminator(); 306 for (unsigned i = 0, ie = TI->getNumSuccessors(); i != ie; ++i) { 307 if (TI->getSuccessor(i) == H) 308 TI->setMetadata(LoopMDName, LoopID); 309 } 310 } 311} 312 313bool Loop::isAnnotatedParallel() const { 314 MDNode *desiredLoopIdMetadata = getLoopID(); 315 316 if (!desiredLoopIdMetadata) 317 return false; 318 319 // The loop branch contains the parallel loop metadata. In order to ensure 320 // that any parallel-loop-unaware optimization pass hasn't added loop-carried 321 // dependencies (thus converted the loop back to a sequential loop), check 322 // that all the memory instructions in the loop contain parallelism metadata 323 // that point to the same unique "loop id metadata" the loop branch does. 324 for (block_iterator BB = block_begin(), BE = block_end(); BB != BE; ++BB) { 325 for (BasicBlock::iterator II = (*BB)->begin(), EE = (*BB)->end(); 326 II != EE; II++) { 327 328 if (!II->mayReadOrWriteMemory()) 329 continue; 330 331 // The memory instruction can refer to the loop identifier metadata 332 // directly or indirectly through another list metadata (in case of 333 // nested parallel loops). The loop identifier metadata refers to 334 // itself so we can check both cases with the same routine. 335 MDNode *loopIdMD = 336 II->getMetadata(LLVMContext::MD_mem_parallel_loop_access); 337 338 if (!loopIdMD) 339 return false; 340 341 bool loopIdMDFound = false; 342 for (unsigned i = 0, e = loopIdMD->getNumOperands(); i < e; ++i) { 343 if (loopIdMD->getOperand(i) == desiredLoopIdMetadata) { 344 loopIdMDFound = true; 345 break; 346 } 347 } 348 349 if (!loopIdMDFound) 350 return false; 351 } 352 } 353 return true; 354} 355 356 357/// hasDedicatedExits - Return true if no exit block for the loop 358/// has a predecessor that is outside the loop. 359bool Loop::hasDedicatedExits() const { 360 // Each predecessor of each exit block of a normal loop is contained 361 // within the loop. 362 SmallVector<BasicBlock *, 4> ExitBlocks; 363 getExitBlocks(ExitBlocks); 364 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 365 for (pred_iterator PI = pred_begin(ExitBlocks[i]), 366 PE = pred_end(ExitBlocks[i]); PI != PE; ++PI) 367 if (!contains(*PI)) 368 return false; 369 // All the requirements are met. 370 return true; 371} 372 373/// getUniqueExitBlocks - Return all unique successor blocks of this loop. 374/// These are the blocks _outside of the current loop_ which are branched to. 375/// This assumes that loop exits are in canonical form. 376/// 377void 378Loop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const { 379 assert(hasDedicatedExits() && 380 "getUniqueExitBlocks assumes the loop has canonical form exits!"); 381 382 SmallVector<BasicBlock *, 32> switchExitBlocks; 383 384 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { 385 386 BasicBlock *current = *BI; 387 switchExitBlocks.clear(); 388 389 for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I) { 390 // If block is inside the loop then it is not a exit block. 391 if (contains(*I)) 392 continue; 393 394 pred_iterator PI = pred_begin(*I); 395 BasicBlock *firstPred = *PI; 396 397 // If current basic block is this exit block's first predecessor 398 // then only insert exit block in to the output ExitBlocks vector. 399 // This ensures that same exit block is not inserted twice into 400 // ExitBlocks vector. 401 if (current != firstPred) 402 continue; 403 404 // If a terminator has more then two successors, for example SwitchInst, 405 // then it is possible that there are multiple edges from current block 406 // to one exit block. 407 if (std::distance(succ_begin(current), succ_end(current)) <= 2) { 408 ExitBlocks.push_back(*I); 409 continue; 410 } 411 412 // In case of multiple edges from current block to exit block, collect 413 // only one edge in ExitBlocks. Use switchExitBlocks to keep track of 414 // duplicate edges. 415 if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) 416 == switchExitBlocks.end()) { 417 switchExitBlocks.push_back(*I); 418 ExitBlocks.push_back(*I); 419 } 420 } 421 } 422} 423 424/// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one 425/// block, return that block. Otherwise return null. 426BasicBlock *Loop::getUniqueExitBlock() const { 427 SmallVector<BasicBlock *, 8> UniqueExitBlocks; 428 getUniqueExitBlocks(UniqueExitBlocks); 429 if (UniqueExitBlocks.size() == 1) 430 return UniqueExitBlocks[0]; 431 return nullptr; 432} 433 434#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 435void Loop::dump() const { 436 print(dbgs()); 437} 438#endif 439 440//===----------------------------------------------------------------------===// 441// UnloopUpdater implementation 442// 443 444namespace { 445/// Find the new parent loop for all blocks within the "unloop" whose last 446/// backedges has just been removed. 447class UnloopUpdater { 448 Loop *Unloop; 449 LoopInfo *LI; 450 451 LoopBlocksDFS DFS; 452 453 // Map unloop's immediate subloops to their nearest reachable parents. Nested 454 // loops within these subloops will not change parents. However, an immediate 455 // subloop's new parent will be the nearest loop reachable from either its own 456 // exits *or* any of its nested loop's exits. 457 DenseMap<Loop*, Loop*> SubloopParents; 458 459 // Flag the presence of an irreducible backedge whose destination is a block 460 // directly contained by the original unloop. 461 bool FoundIB; 462 463public: 464 UnloopUpdater(Loop *UL, LoopInfo *LInfo) : 465 Unloop(UL), LI(LInfo), DFS(UL), FoundIB(false) {} 466 467 void updateBlockParents(); 468 469 void removeBlocksFromAncestors(); 470 471 void updateSubloopParents(); 472 473protected: 474 Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop); 475}; 476} // end anonymous namespace 477 478/// updateBlockParents - Update the parent loop for all blocks that are directly 479/// contained within the original "unloop". 480void UnloopUpdater::updateBlockParents() { 481 if (Unloop->getNumBlocks()) { 482 // Perform a post order CFG traversal of all blocks within this loop, 483 // propagating the nearest loop from sucessors to predecessors. 484 LoopBlocksTraversal Traversal(DFS, LI); 485 for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), 486 POE = Traversal.end(); POI != POE; ++POI) { 487 488 Loop *L = LI->getLoopFor(*POI); 489 Loop *NL = getNearestLoop(*POI, L); 490 491 if (NL != L) { 492 // For reducible loops, NL is now an ancestor of Unloop. 493 assert((NL != Unloop && (!NL || NL->contains(Unloop))) && 494 "uninitialized successor"); 495 LI->changeLoopFor(*POI, NL); 496 } 497 else { 498 // Or the current block is part of a subloop, in which case its parent 499 // is unchanged. 500 assert((FoundIB || Unloop->contains(L)) && "uninitialized successor"); 501 } 502 } 503 } 504 // Each irreducible loop within the unloop induces a round of iteration using 505 // the DFS result cached by Traversal. 506 bool Changed = FoundIB; 507 for (unsigned NIters = 0; Changed; ++NIters) { 508 assert(NIters < Unloop->getNumBlocks() && "runaway iterative algorithm"); 509 510 // Iterate over the postorder list of blocks, propagating the nearest loop 511 // from successors to predecessors as before. 512 Changed = false; 513 for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(), 514 POE = DFS.endPostorder(); POI != POE; ++POI) { 515 516 Loop *L = LI->getLoopFor(*POI); 517 Loop *NL = getNearestLoop(*POI, L); 518 if (NL != L) { 519 assert(NL != Unloop && (!NL || NL->contains(Unloop)) && 520 "uninitialized successor"); 521 LI->changeLoopFor(*POI, NL); 522 Changed = true; 523 } 524 } 525 } 526} 527 528/// removeBlocksFromAncestors - Remove unloop's blocks from all ancestors below 529/// their new parents. 530void UnloopUpdater::removeBlocksFromAncestors() { 531 // Remove all unloop's blocks (including those in nested subloops) from 532 // ancestors below the new parent loop. 533 for (Loop::block_iterator BI = Unloop->block_begin(), 534 BE = Unloop->block_end(); BI != BE; ++BI) { 535 Loop *OuterParent = LI->getLoopFor(*BI); 536 if (Unloop->contains(OuterParent)) { 537 while (OuterParent->getParentLoop() != Unloop) 538 OuterParent = OuterParent->getParentLoop(); 539 OuterParent = SubloopParents[OuterParent]; 540 } 541 // Remove blocks from former Ancestors except Unloop itself which will be 542 // deleted. 543 for (Loop *OldParent = Unloop->getParentLoop(); OldParent != OuterParent; 544 OldParent = OldParent->getParentLoop()) { 545 assert(OldParent && "new loop is not an ancestor of the original"); 546 OldParent->removeBlockFromLoop(*BI); 547 } 548 } 549} 550 551/// updateSubloopParents - Update the parent loop for all subloops directly 552/// nested within unloop. 553void UnloopUpdater::updateSubloopParents() { 554 while (!Unloop->empty()) { 555 Loop *Subloop = *std::prev(Unloop->end()); 556 Unloop->removeChildLoop(std::prev(Unloop->end())); 557 558 assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop"); 559 if (Loop *Parent = SubloopParents[Subloop]) 560 Parent->addChildLoop(Subloop); 561 else 562 LI->addTopLevelLoop(Subloop); 563 } 564} 565 566/// getNearestLoop - Return the nearest parent loop among this block's 567/// successors. If a successor is a subloop header, consider its parent to be 568/// the nearest parent of the subloop's exits. 569/// 570/// For subloop blocks, simply update SubloopParents and return NULL. 571Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { 572 573 // Initially for blocks directly contained by Unloop, NearLoop == Unloop and 574 // is considered uninitialized. 575 Loop *NearLoop = BBLoop; 576 577 Loop *Subloop = nullptr; 578 if (NearLoop != Unloop && Unloop->contains(NearLoop)) { 579 Subloop = NearLoop; 580 // Find the subloop ancestor that is directly contained within Unloop. 581 while (Subloop->getParentLoop() != Unloop) { 582 Subloop = Subloop->getParentLoop(); 583 assert(Subloop && "subloop is not an ancestor of the original loop"); 584 } 585 // Get the current nearest parent of the Subloop exits, initially Unloop. 586 NearLoop = 587 SubloopParents.insert(std::make_pair(Subloop, Unloop)).first->second; 588 } 589 590 succ_iterator I = succ_begin(BB), E = succ_end(BB); 591 if (I == E) { 592 assert(!Subloop && "subloop blocks must have a successor"); 593 NearLoop = nullptr; // unloop blocks may now exit the function. 594 } 595 for (; I != E; ++I) { 596 if (*I == BB) 597 continue; // self loops are uninteresting 598 599 Loop *L = LI->getLoopFor(*I); 600 if (L == Unloop) { 601 // This successor has not been processed. This path must lead to an 602 // irreducible backedge. 603 assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB"); 604 FoundIB = true; 605 } 606 if (L != Unloop && Unloop->contains(L)) { 607 // Successor is in a subloop. 608 if (Subloop) 609 continue; // Branching within subloops. Ignore it. 610 611 // BB branches from the original into a subloop header. 612 assert(L->getParentLoop() == Unloop && "cannot skip into nested loops"); 613 614 // Get the current nearest parent of the Subloop's exits. 615 L = SubloopParents[L]; 616 // L could be Unloop if the only exit was an irreducible backedge. 617 } 618 if (L == Unloop) { 619 continue; 620 } 621 // Handle critical edges from Unloop into a sibling loop. 622 if (L && !L->contains(Unloop)) { 623 L = L->getParentLoop(); 624 } 625 // Remember the nearest parent loop among successors or subloop exits. 626 if (NearLoop == Unloop || !NearLoop || NearLoop->contains(L)) 627 NearLoop = L; 628 } 629 if (Subloop) { 630 SubloopParents[Subloop] = NearLoop; 631 return BBLoop; 632 } 633 return NearLoop; 634} 635 636LoopInfo::LoopInfo(const DominatorTreeBase<BasicBlock> &DomTree) { 637 analyze(DomTree); 638} 639 640void LoopInfo::markAsRemoved(Loop *Unloop) { 641 assert(!Unloop->isInvalid() && "Loop has already been removed"); 642 Unloop->invalidate(); 643 RemovedLoops.push_back(Unloop); 644 645 // First handle the special case of no parent loop to simplify the algorithm. 646 if (!Unloop->getParentLoop()) { 647 // Since BBLoop had no parent, Unloop blocks are no longer in a loop. 648 for (Loop::block_iterator I = Unloop->block_begin(), 649 E = Unloop->block_end(); 650 I != E; ++I) { 651 652 // Don't reparent blocks in subloops. 653 if (getLoopFor(*I) != Unloop) 654 continue; 655 656 // Blocks no longer have a parent but are still referenced by Unloop until 657 // the Unloop object is deleted. 658 changeLoopFor(*I, nullptr); 659 } 660 661 // Remove the loop from the top-level LoopInfo object. 662 for (iterator I = begin();; ++I) { 663 assert(I != end() && "Couldn't find loop"); 664 if (*I == Unloop) { 665 removeLoop(I); 666 break; 667 } 668 } 669 670 // Move all of the subloops to the top-level. 671 while (!Unloop->empty()) 672 addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end()))); 673 674 return; 675 } 676 677 // Update the parent loop for all blocks within the loop. Blocks within 678 // subloops will not change parents. 679 UnloopUpdater Updater(Unloop, this); 680 Updater.updateBlockParents(); 681 682 // Remove blocks from former ancestor loops. 683 Updater.removeBlocksFromAncestors(); 684 685 // Add direct subloops as children in their new parent loop. 686 Updater.updateSubloopParents(); 687 688 // Remove unloop from its parent loop. 689 Loop *ParentLoop = Unloop->getParentLoop(); 690 for (Loop::iterator I = ParentLoop->begin();; ++I) { 691 assert(I != ParentLoop->end() && "Couldn't find loop"); 692 if (*I == Unloop) { 693 ParentLoop->removeChildLoop(I); 694 break; 695 } 696 } 697} 698 699char LoopAnalysis::PassID; 700 701LoopInfo LoopAnalysis::run(Function &F, AnalysisManager<Function> *AM) { 702 // FIXME: Currently we create a LoopInfo from scratch for every function. 703 // This may prove to be too wasteful due to deallocating and re-allocating 704 // memory each time for the underlying map and vector datastructures. At some 705 // point it may prove worthwhile to use a freelist and recycle LoopInfo 706 // objects. I don't want to add that kind of complexity until the scope of 707 // the problem is better understood. 708 LoopInfo LI; 709 LI.analyze(AM->getResult<DominatorTreeAnalysis>(F)); 710 return LI; 711} 712 713PreservedAnalyses LoopPrinterPass::run(Function &F, 714 AnalysisManager<Function> *AM) { 715 AM->getResult<LoopAnalysis>(F).print(OS); 716 return PreservedAnalyses::all(); 717} 718 719PrintLoopPass::PrintLoopPass() : OS(dbgs()) {} 720PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner) 721 : OS(OS), Banner(Banner) {} 722 723PreservedAnalyses PrintLoopPass::run(Loop &L) { 724 OS << Banner; 725 for (auto *Block : L.blocks()) 726 if (Block) 727 Block->print(OS); 728 else 729 OS << "Printing <null> block"; 730 return PreservedAnalyses::all(); 731} 732 733//===----------------------------------------------------------------------===// 734// LoopInfo implementation 735// 736 737char LoopInfoWrapperPass::ID = 0; 738INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information", 739 true, true) 740INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 741INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information", 742 true, true) 743 744bool LoopInfoWrapperPass::runOnFunction(Function &) { 745 releaseMemory(); 746 LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree()); 747 return false; 748} 749 750void LoopInfoWrapperPass::verifyAnalysis() const { 751 // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the 752 // function each time verifyAnalysis is called is very expensive. The 753 // -verify-loop-info option can enable this. In order to perform some 754 // checking by default, LoopPass has been taught to call verifyLoop manually 755 // during loop pass sequences. 756 if (VerifyLoopInfo) 757 LI.verify(); 758} 759 760void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 761 AU.setPreservesAll(); 762 AU.addRequired<DominatorTreeWrapperPass>(); 763} 764 765void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const { 766 LI.print(OS); 767} 768 769//===----------------------------------------------------------------------===// 770// LoopBlocksDFS implementation 771// 772 773/// Traverse the loop blocks and store the DFS result. 774/// Useful for clients that just want the final DFS result and don't need to 775/// visit blocks during the initial traversal. 776void LoopBlocksDFS::perform(LoopInfo *LI) { 777 LoopBlocksTraversal Traversal(*this, LI); 778 for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), 779 POE = Traversal.end(); POI != POE; ++POI) ; 780} 781