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