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