1 //===- GenericLoopInfo - Generic Loop Info for graphs -----------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the LoopInfoBase class that is used to identify natural 10 // loops and determine the loop depth of various nodes in a generic graph of 11 // blocks. A natural loop has exactly one entry-point, which is called the 12 // header. Note that natural loops may actually be several loops that share the 13 // same header node. 14 // 15 // This analysis calculates the nesting structure of loops in a function. For 16 // each natural loop identified, this analysis identifies natural loops 17 // contained entirely within the loop and the basic blocks that make up the 18 // loop. 19 // 20 // It can calculate on the fly various bits of information, for example: 21 // 22 // * whether there is a preheader for the loop 23 // * the number of back edges to the header 24 // * whether or not a particular block branches out of the loop 25 // * the successor blocks of the loop 26 // * the loop depth 27 // * etc... 28 // 29 // Note that this analysis specifically identifies *Loops* not cycles or SCCs 30 // in the graph. There can be strongly connected components in the graph which 31 // this analysis will not recognize and that will not be represented by a Loop 32 // instance. In particular, a Loop might be inside such a non-loop SCC, or a 33 // non-loop SCC might contain a sub-SCC which is a Loop. 34 // 35 // For an overview of terminology used in this API (and thus all of our loop 36 // analyses or transforms), see docs/LoopTerminology.rst. 37 // 38 //===----------------------------------------------------------------------===// 39 40 #ifndef LLVM_SUPPORT_GENERICLOOPINFO_H 41 #define LLVM_SUPPORT_GENERICLOOPINFO_H 42 43 #include "llvm/ADT/DenseSet.h" 44 #include "llvm/ADT/PostOrderIterator.h" 45 #include "llvm/ADT/STLExtras.h" 46 #include "llvm/ADT/SetOperations.h" 47 #include "llvm/Support/Allocator.h" 48 #include "llvm/Support/GenericDomTree.h" 49 50 namespace llvm { 51 52 template <class N, class M> class LoopInfoBase; 53 template <class N, class M> class LoopBase; 54 55 //===----------------------------------------------------------------------===// 56 /// Instances of this class are used to represent loops that are detected in the 57 /// flow graph. 58 /// 59 template <class BlockT, class LoopT> class LoopBase { 60 LoopT *ParentLoop; 61 // Loops contained entirely within this one. 62 std::vector<LoopT *> SubLoops; 63 64 // The list of blocks in this loop. First entry is the header node. 65 std::vector<BlockT *> Blocks; 66 67 SmallPtrSet<const BlockT *, 8> DenseBlockSet; 68 69 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 70 /// Indicator that this loop is no longer a valid loop. 71 bool IsInvalid = false; 72 #endif 73 74 LoopBase(const LoopBase<BlockT, LoopT> &) = delete; 75 const LoopBase<BlockT, LoopT> & 76 operator=(const LoopBase<BlockT, LoopT> &) = delete; 77 78 public: 79 /// Return the nesting level of this loop. An outer-most loop has depth 1, 80 /// for consistency with loop depth values used for basic blocks, where depth 81 /// 0 is used for blocks not inside any loops. 82 unsigned getLoopDepth() const { 83 assert(!isInvalid() && "Loop not in a valid state!"); 84 unsigned D = 1; 85 for (const LoopT *CurLoop = ParentLoop; CurLoop; 86 CurLoop = CurLoop->ParentLoop) 87 ++D; 88 return D; 89 } 90 BlockT *getHeader() const { return getBlocks().front(); } 91 /// Return the parent loop if it exists or nullptr for top 92 /// level loops. 93 94 /// A loop is either top-level in a function (that is, it is not 95 /// contained in any other loop) or it is entirely enclosed in 96 /// some other loop. 97 /// If a loop is top-level, it has no parent, otherwise its 98 /// parent is the innermost loop in which it is enclosed. 99 LoopT *getParentLoop() const { return ParentLoop; } 100 101 /// Get the outermost loop in which this loop is contained. 102 /// This may be the loop itself, if it already is the outermost loop. 103 const LoopT *getOutermostLoop() const { 104 const LoopT *L = static_cast<const LoopT *>(this); 105 while (L->ParentLoop) 106 L = L->ParentLoop; 107 return L; 108 } 109 110 LoopT *getOutermostLoop() { 111 LoopT *L = static_cast<LoopT *>(this); 112 while (L->ParentLoop) 113 L = L->ParentLoop; 114 return L; 115 } 116 117 /// This is a raw interface for bypassing addChildLoop. 118 void setParentLoop(LoopT *L) { 119 assert(!isInvalid() && "Loop not in a valid state!"); 120 ParentLoop = L; 121 } 122 123 /// Return true if the specified loop is contained within in this loop. 124 bool contains(const LoopT *L) const { 125 assert(!isInvalid() && "Loop not in a valid state!"); 126 if (L == this) 127 return true; 128 if (!L) 129 return false; 130 return contains(L->getParentLoop()); 131 } 132 133 /// Return true if the specified basic block is in this loop. 134 bool contains(const BlockT *BB) const { 135 assert(!isInvalid() && "Loop not in a valid state!"); 136 return DenseBlockSet.count(BB); 137 } 138 139 /// Return true if the specified instruction is in this loop. 140 template <class InstT> bool contains(const InstT *Inst) const { 141 return contains(Inst->getParent()); 142 } 143 144 /// Return the loops contained entirely within this loop. 145 const std::vector<LoopT *> &getSubLoops() const { 146 assert(!isInvalid() && "Loop not in a valid state!"); 147 return SubLoops; 148 } 149 std::vector<LoopT *> &getSubLoopsVector() { 150 assert(!isInvalid() && "Loop not in a valid state!"); 151 return SubLoops; 152 } 153 typedef typename std::vector<LoopT *>::const_iterator iterator; 154 typedef 155 typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator; 156 iterator begin() const { return getSubLoops().begin(); } 157 iterator end() const { return getSubLoops().end(); } 158 reverse_iterator rbegin() const { return getSubLoops().rbegin(); } 159 reverse_iterator rend() const { return getSubLoops().rend(); } 160 161 // LoopInfo does not detect irreducible control flow, just natural 162 // loops. That is, it is possible that there is cyclic control 163 // flow within the "innermost loop" or around the "outermost 164 // loop". 165 166 /// Return true if the loop does not contain any (natural) loops. 167 bool isInnermost() const { return getSubLoops().empty(); } 168 /// Return true if the loop does not have a parent (natural) loop 169 // (i.e. it is outermost, which is the same as top-level). 170 bool isOutermost() const { return getParentLoop() == nullptr; } 171 172 /// Get a list of the basic blocks which make up this loop. 173 ArrayRef<BlockT *> getBlocks() const { 174 assert(!isInvalid() && "Loop not in a valid state!"); 175 return Blocks; 176 } 177 typedef typename ArrayRef<BlockT *>::const_iterator block_iterator; 178 block_iterator block_begin() const { return getBlocks().begin(); } 179 block_iterator block_end() const { return getBlocks().end(); } 180 inline iterator_range<block_iterator> blocks() const { 181 assert(!isInvalid() && "Loop not in a valid state!"); 182 return make_range(block_begin(), block_end()); 183 } 184 185 /// Get the number of blocks in this loop in constant time. 186 /// Invalidate the loop, indicating that it is no longer a loop. 187 unsigned getNumBlocks() const { 188 assert(!isInvalid() && "Loop not in a valid state!"); 189 return Blocks.size(); 190 } 191 192 /// Return a direct, mutable handle to the blocks vector so that we can 193 /// mutate it efficiently with techniques like `std::remove`. 194 std::vector<BlockT *> &getBlocksVector() { 195 assert(!isInvalid() && "Loop not in a valid state!"); 196 return Blocks; 197 } 198 /// Return a direct, mutable handle to the blocks set so that we can 199 /// mutate it efficiently. 200 SmallPtrSetImpl<const BlockT *> &getBlocksSet() { 201 assert(!isInvalid() && "Loop not in a valid state!"); 202 return DenseBlockSet; 203 } 204 205 /// Return a direct, immutable handle to the blocks set. 206 const SmallPtrSetImpl<const BlockT *> &getBlocksSet() const { 207 assert(!isInvalid() && "Loop not in a valid state!"); 208 return DenseBlockSet; 209 } 210 211 /// Return true if this loop is no longer valid. The only valid use of this 212 /// helper is "assert(L.isInvalid())" or equivalent, since IsInvalid is set to 213 /// true by the destructor. In other words, if this accessor returns true, 214 /// the caller has already triggered UB by calling this accessor; and so it 215 /// can only be called in a context where a return value of true indicates a 216 /// programmer error. 217 bool isInvalid() const { 218 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 219 return IsInvalid; 220 #else 221 return false; 222 #endif 223 } 224 225 /// True if terminator in the block can branch to another block that is 226 /// outside of the current loop. \p BB must be inside the loop. 227 bool isLoopExiting(const BlockT *BB) const { 228 assert(!isInvalid() && "Loop not in a valid state!"); 229 assert(contains(BB) && "Exiting block must be part of the loop"); 230 for (const auto *Succ : children<const BlockT *>(BB)) { 231 if (!contains(Succ)) 232 return true; 233 } 234 return false; 235 } 236 237 /// Returns true if \p BB is a loop-latch. 238 /// A latch block is a block that contains a branch back to the header. 239 /// This function is useful when there are multiple latches in a loop 240 /// because \fn getLoopLatch will return nullptr in that case. 241 bool isLoopLatch(const BlockT *BB) const { 242 assert(!isInvalid() && "Loop not in a valid state!"); 243 assert(contains(BB) && "block does not belong to the loop"); 244 245 BlockT *Header = getHeader(); 246 auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header); 247 auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header); 248 return std::find(PredBegin, PredEnd, BB) != PredEnd; 249 } 250 251 /// Calculate the number of back edges to the loop header. 252 unsigned getNumBackEdges() const { 253 assert(!isInvalid() && "Loop not in a valid state!"); 254 unsigned NumBackEdges = 0; 255 BlockT *H = getHeader(); 256 257 for (const auto Pred : children<Inverse<BlockT *>>(H)) 258 if (contains(Pred)) 259 ++NumBackEdges; 260 261 return NumBackEdges; 262 } 263 264 //===--------------------------------------------------------------------===// 265 // APIs for simple analysis of the loop. 266 // 267 // Note that all of these methods can fail on general loops (ie, there may not 268 // be a preheader, etc). For best success, the loop simplification and 269 // induction variable canonicalization pass should be used to normalize loops 270 // for easy analysis. These methods assume canonical loops. 271 272 /// Return all blocks inside the loop that have successors outside of the 273 /// loop. These are the blocks _inside of the current loop_ which branch out. 274 /// The returned list is always unique. 275 void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const; 276 277 /// If getExitingBlocks would return exactly one block, return that block. 278 /// Otherwise return null. 279 BlockT *getExitingBlock() const; 280 281 /// Return all of the successor blocks of this loop. These are the blocks 282 /// _outside of the current loop_ which are branched to. 283 void getExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const; 284 285 /// If getExitBlocks would return exactly one block, return that block. 286 /// Otherwise return null. 287 BlockT *getExitBlock() const; 288 289 /// Return true if no exit block for the loop has a predecessor that is 290 /// outside the loop. 291 bool hasDedicatedExits() const; 292 293 /// Return all unique successor blocks of this loop. 294 /// These are the blocks _outside of the current loop_ which are branched to. 295 void getUniqueExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const; 296 297 /// Return all unique successor blocks of this loop except successors from 298 /// Latch block are not considered. If the exit comes from Latch has also 299 /// non Latch predecessor in a loop it will be added to ExitBlocks. 300 /// These are the blocks _outside of the current loop_ which are branched to. 301 void getUniqueNonLatchExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const; 302 303 /// If getUniqueExitBlocks would return exactly one block, return that block. 304 /// Otherwise return null. 305 BlockT *getUniqueExitBlock() const; 306 307 /// Return true if this loop does not have any exit blocks. 308 bool hasNoExitBlocks() const; 309 310 /// Edge type. 311 typedef std::pair<BlockT *, BlockT *> Edge; 312 313 /// Return all pairs of (_inside_block_,_outside_block_). 314 void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const; 315 316 /// If there is a preheader for this loop, return it. A loop has a preheader 317 /// if there is only one edge to the header of the loop from outside of the 318 /// loop. If this is the case, the block branching to the header of the loop 319 /// is the preheader node. 320 /// 321 /// This method returns null if there is no preheader for the loop. 322 BlockT *getLoopPreheader() const; 323 324 /// If the given loop's header has exactly one unique predecessor outside the 325 /// loop, return it. Otherwise return null. 326 /// This is less strict that the loop "preheader" concept, which requires 327 /// the predecessor to have exactly one successor. 328 BlockT *getLoopPredecessor() const; 329 330 /// If there is a single latch block for this loop, return it. 331 /// A latch block is a block that contains a branch back to the header. 332 BlockT *getLoopLatch() const; 333 334 /// Return all loop latch blocks of this loop. A latch block is a block that 335 /// contains a branch back to the header. 336 void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const { 337 assert(!isInvalid() && "Loop not in a valid state!"); 338 BlockT *H = getHeader(); 339 for (const auto Pred : children<Inverse<BlockT *>>(H)) 340 if (contains(Pred)) 341 LoopLatches.push_back(Pred); 342 } 343 344 /// Return all inner loops in the loop nest rooted by the loop in preorder, 345 /// with siblings in forward program order. 346 template <class Type> 347 static void getInnerLoopsInPreorder(const LoopT &L, 348 SmallVectorImpl<Type> &PreOrderLoops) { 349 SmallVector<LoopT *, 4> PreOrderWorklist; 350 PreOrderWorklist.append(L.rbegin(), L.rend()); 351 352 while (!PreOrderWorklist.empty()) { 353 LoopT *L = PreOrderWorklist.pop_back_val(); 354 // Sub-loops are stored in forward program order, but will process the 355 // worklist backwards so append them in reverse order. 356 PreOrderWorklist.append(L->rbegin(), L->rend()); 357 PreOrderLoops.push_back(L); 358 } 359 } 360 361 /// Return all loops in the loop nest rooted by the loop in preorder, with 362 /// siblings in forward program order. 363 SmallVector<const LoopT *, 4> getLoopsInPreorder() const { 364 SmallVector<const LoopT *, 4> PreOrderLoops; 365 const LoopT *CurLoop = static_cast<const LoopT *>(this); 366 PreOrderLoops.push_back(CurLoop); 367 getInnerLoopsInPreorder(*CurLoop, PreOrderLoops); 368 return PreOrderLoops; 369 } 370 SmallVector<LoopT *, 4> getLoopsInPreorder() { 371 SmallVector<LoopT *, 4> PreOrderLoops; 372 LoopT *CurLoop = static_cast<LoopT *>(this); 373 PreOrderLoops.push_back(CurLoop); 374 getInnerLoopsInPreorder(*CurLoop, PreOrderLoops); 375 return PreOrderLoops; 376 } 377 378 //===--------------------------------------------------------------------===// 379 // APIs for updating loop information after changing the CFG 380 // 381 382 /// This method is used by other analyses to update loop information. 383 /// NewBB is set to be a new member of the current loop. 384 /// Because of this, it is added as a member of all parent loops, and is added 385 /// to the specified LoopInfo object as being in the current basic block. It 386 /// is not valid to replace the loop header with this method. 387 void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI); 388 389 /// This is used when splitting loops up. It replaces the OldChild entry in 390 /// our children list with NewChild, and updates the parent pointer of 391 /// OldChild to be null and the NewChild to be this loop. 392 /// This updates the loop depth of the new child. 393 void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild); 394 395 /// Add the specified loop to be a child of this loop. 396 /// This updates the loop depth of the new child. 397 void addChildLoop(LoopT *NewChild) { 398 assert(!isInvalid() && "Loop not in a valid state!"); 399 assert(!NewChild->ParentLoop && "NewChild already has a parent!"); 400 NewChild->ParentLoop = static_cast<LoopT *>(this); 401 SubLoops.push_back(NewChild); 402 } 403 404 /// This removes the specified child from being a subloop of this loop. The 405 /// loop is not deleted, as it will presumably be inserted into another loop. 406 LoopT *removeChildLoop(iterator I) { 407 assert(!isInvalid() && "Loop not in a valid state!"); 408 assert(I != SubLoops.end() && "Cannot remove end iterator!"); 409 LoopT *Child = *I; 410 assert(Child->ParentLoop == this && "Child is not a child of this loop!"); 411 SubLoops.erase(SubLoops.begin() + (I - begin())); 412 Child->ParentLoop = nullptr; 413 return Child; 414 } 415 416 /// This removes the specified child from being a subloop of this loop. The 417 /// loop is not deleted, as it will presumably be inserted into another loop. 418 LoopT *removeChildLoop(LoopT *Child) { 419 return removeChildLoop(llvm::find(*this, Child)); 420 } 421 422 /// This adds a basic block directly to the basic block list. 423 /// This should only be used by transformations that create new loops. Other 424 /// transformations should use addBasicBlockToLoop. 425 void addBlockEntry(BlockT *BB) { 426 assert(!isInvalid() && "Loop not in a valid state!"); 427 Blocks.push_back(BB); 428 DenseBlockSet.insert(BB); 429 } 430 431 /// interface to reverse Blocks[from, end of loop] in this loop 432 void reverseBlock(unsigned from) { 433 assert(!isInvalid() && "Loop not in a valid state!"); 434 std::reverse(Blocks.begin() + from, Blocks.end()); 435 } 436 437 /// interface to do reserve() for Blocks 438 void reserveBlocks(unsigned size) { 439 assert(!isInvalid() && "Loop not in a valid state!"); 440 Blocks.reserve(size); 441 } 442 443 /// This method is used to move BB (which must be part of this loop) to be the 444 /// loop header of the loop (the block that dominates all others). 445 void moveToHeader(BlockT *BB) { 446 assert(!isInvalid() && "Loop not in a valid state!"); 447 if (Blocks[0] == BB) 448 return; 449 for (unsigned i = 0;; ++i) { 450 assert(i != Blocks.size() && "Loop does not contain BB!"); 451 if (Blocks[i] == BB) { 452 Blocks[i] = Blocks[0]; 453 Blocks[0] = BB; 454 return; 455 } 456 } 457 } 458 459 /// This removes the specified basic block from the current loop, updating the 460 /// Blocks as appropriate. This does not update the mapping in the LoopInfo 461 /// class. 462 void removeBlockFromLoop(BlockT *BB) { 463 assert(!isInvalid() && "Loop not in a valid state!"); 464 auto I = find(Blocks, BB); 465 assert(I != Blocks.end() && "N is not in this list!"); 466 Blocks.erase(I); 467 468 DenseBlockSet.erase(BB); 469 } 470 471 /// Verify loop structure 472 void verifyLoop() const; 473 474 /// Verify loop structure of this loop and all nested loops. 475 void verifyLoopNest(DenseSet<const LoopT *> *Loops) const; 476 477 /// Returns true if the loop is annotated parallel. 478 /// 479 /// Derived classes can override this method using static template 480 /// polymorphism. 481 bool isAnnotatedParallel() const { return false; } 482 483 /// Print loop with all the BBs inside it. 484 void print(raw_ostream &OS, bool Verbose = false, bool PrintNested = true, 485 unsigned Depth = 0) const; 486 487 protected: 488 friend class LoopInfoBase<BlockT, LoopT>; 489 490 /// This creates an empty loop. 491 LoopBase() : ParentLoop(nullptr) {} 492 493 explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) { 494 Blocks.push_back(BB); 495 DenseBlockSet.insert(BB); 496 } 497 498 // Since loop passes like SCEV are allowed to key analysis results off of 499 // `Loop` pointers, we cannot re-use pointers within a loop pass manager. 500 // This means loop passes should not be `delete` ing `Loop` objects directly 501 // (and risk a later `Loop` allocation re-using the address of a previous one) 502 // but should be using LoopInfo::markAsRemoved, which keeps around the `Loop` 503 // pointer till the end of the lifetime of the `LoopInfo` object. 504 // 505 // To make it easier to follow this rule, we mark the destructor as 506 // non-public. 507 ~LoopBase() { 508 for (auto *SubLoop : SubLoops) 509 SubLoop->~LoopT(); 510 511 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 512 IsInvalid = true; 513 #endif 514 SubLoops.clear(); 515 Blocks.clear(); 516 DenseBlockSet.clear(); 517 ParentLoop = nullptr; 518 } 519 }; 520 521 template <class BlockT, class LoopT> 522 raw_ostream &operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) { 523 Loop.print(OS); 524 return OS; 525 } 526 527 //===----------------------------------------------------------------------===// 528 /// This class builds and contains all of the top-level loop 529 /// structures in the specified function. 530 /// 531 532 template <class BlockT, class LoopT> class LoopInfoBase { 533 // BBMap - Mapping of basic blocks to the inner most loop they occur in 534 DenseMap<const BlockT *, LoopT *> BBMap; 535 std::vector<LoopT *> TopLevelLoops; 536 BumpPtrAllocator LoopAllocator; 537 538 friend class LoopBase<BlockT, LoopT>; 539 friend class LoopInfo; 540 541 void operator=(const LoopInfoBase &) = delete; 542 LoopInfoBase(const LoopInfoBase &) = delete; 543 544 public: 545 LoopInfoBase() = default; 546 ~LoopInfoBase() { releaseMemory(); } 547 548 LoopInfoBase(LoopInfoBase &&Arg) 549 : BBMap(std::move(Arg.BBMap)), 550 TopLevelLoops(std::move(Arg.TopLevelLoops)), 551 LoopAllocator(std::move(Arg.LoopAllocator)) { 552 // We have to clear the arguments top level loops as we've taken ownership. 553 Arg.TopLevelLoops.clear(); 554 } 555 LoopInfoBase &operator=(LoopInfoBase &&RHS) { 556 BBMap = std::move(RHS.BBMap); 557 558 for (auto *L : TopLevelLoops) 559 L->~LoopT(); 560 561 TopLevelLoops = std::move(RHS.TopLevelLoops); 562 LoopAllocator = std::move(RHS.LoopAllocator); 563 RHS.TopLevelLoops.clear(); 564 return *this; 565 } 566 567 void releaseMemory() { 568 BBMap.clear(); 569 570 for (auto *L : TopLevelLoops) 571 L->~LoopT(); 572 TopLevelLoops.clear(); 573 LoopAllocator.Reset(); 574 } 575 576 template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&...Args) { 577 LoopT *Storage = LoopAllocator.Allocate<LoopT>(); 578 return new (Storage) LoopT(std::forward<ArgsTy>(Args)...); 579 } 580 581 /// iterator/begin/end - The interface to the top-level loops in the current 582 /// function. 583 /// 584 typedef typename std::vector<LoopT *>::const_iterator iterator; 585 typedef 586 typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator; 587 iterator begin() const { return TopLevelLoops.begin(); } 588 iterator end() const { return TopLevelLoops.end(); } 589 reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); } 590 reverse_iterator rend() const { return TopLevelLoops.rend(); } 591 bool empty() const { return TopLevelLoops.empty(); } 592 593 /// Return all of the loops in the function in preorder across the loop 594 /// nests, with siblings in forward program order. 595 /// 596 /// Note that because loops form a forest of trees, preorder is equivalent to 597 /// reverse postorder. 598 SmallVector<LoopT *, 4> getLoopsInPreorder() const; 599 600 /// Return all of the loops in the function in preorder across the loop 601 /// nests, with siblings in *reverse* program order. 602 /// 603 /// Note that because loops form a forest of trees, preorder is equivalent to 604 /// reverse postorder. 605 /// 606 /// Also note that this is *not* a reverse preorder. Only the siblings are in 607 /// reverse program order. 608 SmallVector<LoopT *, 4> getLoopsInReverseSiblingPreorder() const; 609 610 /// Return the inner most loop that BB lives in. If a basic block is in no 611 /// loop (for example the entry node), null is returned. 612 LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); } 613 614 /// Same as getLoopFor. 615 const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); } 616 617 /// Return the loop nesting level of the specified block. A depth of 0 means 618 /// the block is not inside any loop. 619 unsigned getLoopDepth(const BlockT *BB) const { 620 const LoopT *L = getLoopFor(BB); 621 return L ? L->getLoopDepth() : 0; 622 } 623 624 // True if the block is a loop header node 625 bool isLoopHeader(const BlockT *BB) const { 626 const LoopT *L = getLoopFor(BB); 627 return L && L->getHeader() == BB; 628 } 629 630 /// Return the top-level loops. 631 const std::vector<LoopT *> &getTopLevelLoops() const { return TopLevelLoops; } 632 633 /// Return the top-level loops. 634 std::vector<LoopT *> &getTopLevelLoopsVector() { return TopLevelLoops; } 635 636 /// This removes the specified top-level loop from this loop info object. 637 /// The loop is not deleted, as it will presumably be inserted into 638 /// another loop. 639 LoopT *removeLoop(iterator I) { 640 assert(I != end() && "Cannot remove end iterator!"); 641 LoopT *L = *I; 642 assert(L->isOutermost() && "Not a top-level loop!"); 643 TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin())); 644 return L; 645 } 646 647 /// Change the top-level loop that contains BB to the specified loop. 648 /// This should be used by transformations that restructure the loop hierarchy 649 /// tree. 650 void changeLoopFor(BlockT *BB, LoopT *L) { 651 if (!L) { 652 BBMap.erase(BB); 653 return; 654 } 655 BBMap[BB] = L; 656 } 657 658 /// Replace the specified loop in the top-level loops list with the indicated 659 /// loop. 660 void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) { 661 auto I = find(TopLevelLoops, OldLoop); 662 assert(I != TopLevelLoops.end() && "Old loop not at top level!"); 663 *I = NewLoop; 664 assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop && 665 "Loops already embedded into a subloop!"); 666 } 667 668 /// This adds the specified loop to the collection of top-level loops. 669 void addTopLevelLoop(LoopT *New) { 670 assert(New->isOutermost() && "Loop already in subloop!"); 671 TopLevelLoops.push_back(New); 672 } 673 674 /// This method completely removes BB from all data structures, 675 /// including all of the Loop objects it is nested in and our mapping from 676 /// BasicBlocks to loops. 677 void removeBlock(BlockT *BB) { 678 auto I = BBMap.find(BB); 679 if (I != BBMap.end()) { 680 for (LoopT *L = I->second; L; L = L->getParentLoop()) 681 L->removeBlockFromLoop(BB); 682 683 BBMap.erase(I); 684 } 685 } 686 687 // Internals 688 689 static bool isNotAlreadyContainedIn(const LoopT *SubLoop, 690 const LoopT *ParentLoop) { 691 if (!SubLoop) 692 return true; 693 if (SubLoop == ParentLoop) 694 return false; 695 return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop); 696 } 697 698 /// Create the loop forest using a stable algorithm. 699 void analyze(const DominatorTreeBase<BlockT, false> &DomTree); 700 701 // Debugging 702 void print(raw_ostream &OS) const; 703 704 void verify(const DominatorTreeBase<BlockT, false> &DomTree) const; 705 706 /// Destroy a loop that has been removed from the `LoopInfo` nest. 707 /// 708 /// This runs the destructor of the loop object making it invalid to 709 /// reference afterward. The memory is retained so that the *pointer* to the 710 /// loop remains valid. 711 /// 712 /// The caller is responsible for removing this loop from the loop nest and 713 /// otherwise disconnecting it from the broader `LoopInfo` data structures. 714 /// Callers that don't naturally handle this themselves should probably call 715 /// `erase' instead. 716 void destroy(LoopT *L) { 717 L->~LoopT(); 718 719 // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons 720 // \c L, but the pointer remains valid for non-dereferencing uses. 721 LoopAllocator.Deallocate(L); 722 } 723 }; 724 725 } // namespace llvm 726 727 #endif // LLVM_SUPPORT_GENERICLOOPINFO_H 728