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