106c3fb27SDimitry Andric //===- GenericLoopInfo - Generic Loop Info for graphs -----------*- C++ -*-===// 206c3fb27SDimitry Andric // 306c3fb27SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 406c3fb27SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 506c3fb27SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 606c3fb27SDimitry Andric // 706c3fb27SDimitry Andric //===----------------------------------------------------------------------===// 806c3fb27SDimitry Andric // 906c3fb27SDimitry Andric // This file defines the LoopInfoBase class that is used to identify natural 1006c3fb27SDimitry Andric // loops and determine the loop depth of various nodes in a generic graph of 1106c3fb27SDimitry Andric // blocks. A natural loop has exactly one entry-point, which is called the 1206c3fb27SDimitry Andric // header. Note that natural loops may actually be several loops that share the 1306c3fb27SDimitry Andric // same header node. 1406c3fb27SDimitry Andric // 1506c3fb27SDimitry Andric // This analysis calculates the nesting structure of loops in a function. For 1606c3fb27SDimitry Andric // each natural loop identified, this analysis identifies natural loops 1706c3fb27SDimitry Andric // contained entirely within the loop and the basic blocks that make up the 1806c3fb27SDimitry Andric // loop. 1906c3fb27SDimitry Andric // 2006c3fb27SDimitry Andric // It can calculate on the fly various bits of information, for example: 2106c3fb27SDimitry Andric // 2206c3fb27SDimitry Andric // * whether there is a preheader for the loop 2306c3fb27SDimitry Andric // * the number of back edges to the header 2406c3fb27SDimitry Andric // * whether or not a particular block branches out of the loop 2506c3fb27SDimitry Andric // * the successor blocks of the loop 2606c3fb27SDimitry Andric // * the loop depth 2706c3fb27SDimitry Andric // * etc... 2806c3fb27SDimitry Andric // 2906c3fb27SDimitry Andric // Note that this analysis specifically identifies *Loops* not cycles or SCCs 3006c3fb27SDimitry Andric // in the graph. There can be strongly connected components in the graph which 3106c3fb27SDimitry Andric // this analysis will not recognize and that will not be represented by a Loop 3206c3fb27SDimitry Andric // instance. In particular, a Loop might be inside such a non-loop SCC, or a 3306c3fb27SDimitry Andric // non-loop SCC might contain a sub-SCC which is a Loop. 3406c3fb27SDimitry Andric // 3506c3fb27SDimitry Andric // For an overview of terminology used in this API (and thus all of our loop 3606c3fb27SDimitry Andric // analyses or transforms), see docs/LoopTerminology.rst. 3706c3fb27SDimitry Andric // 3806c3fb27SDimitry Andric //===----------------------------------------------------------------------===// 3906c3fb27SDimitry Andric 4006c3fb27SDimitry Andric #ifndef LLVM_SUPPORT_GENERICLOOPINFO_H 4106c3fb27SDimitry Andric #define LLVM_SUPPORT_GENERICLOOPINFO_H 4206c3fb27SDimitry Andric 4306c3fb27SDimitry Andric #include "llvm/ADT/DenseSet.h" 4406c3fb27SDimitry Andric #include "llvm/ADT/PostOrderIterator.h" 4506c3fb27SDimitry Andric #include "llvm/ADT/STLExtras.h" 4606c3fb27SDimitry Andric #include "llvm/ADT/SetOperations.h" 4706c3fb27SDimitry Andric #include "llvm/Support/Allocator.h" 4806c3fb27SDimitry Andric #include "llvm/Support/GenericDomTree.h" 4906c3fb27SDimitry Andric 5006c3fb27SDimitry Andric namespace llvm { 5106c3fb27SDimitry Andric 5206c3fb27SDimitry Andric template <class N, class M> class LoopInfoBase; 5306c3fb27SDimitry Andric template <class N, class M> class LoopBase; 5406c3fb27SDimitry Andric 5506c3fb27SDimitry Andric //===----------------------------------------------------------------------===// 5606c3fb27SDimitry Andric /// Instances of this class are used to represent loops that are detected in the 5706c3fb27SDimitry Andric /// flow graph. 5806c3fb27SDimitry Andric /// 5906c3fb27SDimitry Andric template <class BlockT, class LoopT> class LoopBase { 6006c3fb27SDimitry Andric LoopT *ParentLoop; 6106c3fb27SDimitry Andric // Loops contained entirely within this one. 6206c3fb27SDimitry Andric std::vector<LoopT *> SubLoops; 6306c3fb27SDimitry Andric 6406c3fb27SDimitry Andric // The list of blocks in this loop. First entry is the header node. 6506c3fb27SDimitry Andric std::vector<BlockT *> Blocks; 6606c3fb27SDimitry Andric 6706c3fb27SDimitry Andric SmallPtrSet<const BlockT *, 8> DenseBlockSet; 6806c3fb27SDimitry Andric 6906c3fb27SDimitry Andric #if LLVM_ENABLE_ABI_BREAKING_CHECKS 7006c3fb27SDimitry Andric /// Indicator that this loop is no longer a valid loop. 7106c3fb27SDimitry Andric bool IsInvalid = false; 7206c3fb27SDimitry Andric #endif 7306c3fb27SDimitry Andric 7406c3fb27SDimitry Andric LoopBase(const LoopBase<BlockT, LoopT> &) = delete; 7506c3fb27SDimitry Andric const LoopBase<BlockT, LoopT> & 7606c3fb27SDimitry Andric operator=(const LoopBase<BlockT, LoopT> &) = delete; 7706c3fb27SDimitry Andric 7806c3fb27SDimitry Andric public: 7906c3fb27SDimitry Andric /// Return the nesting level of this loop. An outer-most loop has depth 1, 8006c3fb27SDimitry Andric /// for consistency with loop depth values used for basic blocks, where depth 8106c3fb27SDimitry Andric /// 0 is used for blocks not inside any loops. getLoopDepth()8206c3fb27SDimitry Andric unsigned getLoopDepth() const { 8306c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 8406c3fb27SDimitry Andric unsigned D = 1; 8506c3fb27SDimitry Andric for (const LoopT *CurLoop = ParentLoop; CurLoop; 8606c3fb27SDimitry Andric CurLoop = CurLoop->ParentLoop) 8706c3fb27SDimitry Andric ++D; 8806c3fb27SDimitry Andric return D; 8906c3fb27SDimitry Andric } getHeader()9006c3fb27SDimitry Andric BlockT *getHeader() const { return getBlocks().front(); } 9106c3fb27SDimitry Andric /// Return the parent loop if it exists or nullptr for top 9206c3fb27SDimitry Andric /// level loops. 9306c3fb27SDimitry Andric 9406c3fb27SDimitry Andric /// A loop is either top-level in a function (that is, it is not 9506c3fb27SDimitry Andric /// contained in any other loop) or it is entirely enclosed in 9606c3fb27SDimitry Andric /// some other loop. 9706c3fb27SDimitry Andric /// If a loop is top-level, it has no parent, otherwise its 9806c3fb27SDimitry Andric /// parent is the innermost loop in which it is enclosed. getParentLoop()9906c3fb27SDimitry Andric LoopT *getParentLoop() const { return ParentLoop; } 10006c3fb27SDimitry Andric 10106c3fb27SDimitry Andric /// Get the outermost loop in which this loop is contained. 10206c3fb27SDimitry Andric /// This may be the loop itself, if it already is the outermost loop. getOutermostLoop()10306c3fb27SDimitry Andric const LoopT *getOutermostLoop() const { 10406c3fb27SDimitry Andric const LoopT *L = static_cast<const LoopT *>(this); 10506c3fb27SDimitry Andric while (L->ParentLoop) 10606c3fb27SDimitry Andric L = L->ParentLoop; 10706c3fb27SDimitry Andric return L; 10806c3fb27SDimitry Andric } 10906c3fb27SDimitry Andric getOutermostLoop()11006c3fb27SDimitry Andric LoopT *getOutermostLoop() { 11106c3fb27SDimitry Andric LoopT *L = static_cast<LoopT *>(this); 11206c3fb27SDimitry Andric while (L->ParentLoop) 11306c3fb27SDimitry Andric L = L->ParentLoop; 11406c3fb27SDimitry Andric return L; 11506c3fb27SDimitry Andric } 11606c3fb27SDimitry Andric 11706c3fb27SDimitry Andric /// This is a raw interface for bypassing addChildLoop. setParentLoop(LoopT * L)11806c3fb27SDimitry Andric void setParentLoop(LoopT *L) { 11906c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 12006c3fb27SDimitry Andric ParentLoop = L; 12106c3fb27SDimitry Andric } 12206c3fb27SDimitry Andric 12306c3fb27SDimitry Andric /// Return true if the specified loop is contained within in this loop. contains(const LoopT * L)12406c3fb27SDimitry Andric bool contains(const LoopT *L) const { 12506c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 12606c3fb27SDimitry Andric if (L == this) 12706c3fb27SDimitry Andric return true; 12806c3fb27SDimitry Andric if (!L) 12906c3fb27SDimitry Andric return false; 13006c3fb27SDimitry Andric return contains(L->getParentLoop()); 13106c3fb27SDimitry Andric } 13206c3fb27SDimitry Andric 13306c3fb27SDimitry Andric /// Return true if the specified basic block is in this loop. contains(const BlockT * BB)13406c3fb27SDimitry Andric bool contains(const BlockT *BB) const { 13506c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 13606c3fb27SDimitry Andric return DenseBlockSet.count(BB); 13706c3fb27SDimitry Andric } 13806c3fb27SDimitry Andric 13906c3fb27SDimitry Andric /// Return true if the specified instruction is in this loop. contains(const InstT * Inst)14006c3fb27SDimitry Andric template <class InstT> bool contains(const InstT *Inst) const { 14106c3fb27SDimitry Andric return contains(Inst->getParent()); 14206c3fb27SDimitry Andric } 14306c3fb27SDimitry Andric 14406c3fb27SDimitry Andric /// Return the loops contained entirely within this loop. getSubLoops()14506c3fb27SDimitry Andric const std::vector<LoopT *> &getSubLoops() const { 14606c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 14706c3fb27SDimitry Andric return SubLoops; 14806c3fb27SDimitry Andric } getSubLoopsVector()14906c3fb27SDimitry Andric std::vector<LoopT *> &getSubLoopsVector() { 15006c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 15106c3fb27SDimitry Andric return SubLoops; 15206c3fb27SDimitry Andric } 15306c3fb27SDimitry Andric typedef typename std::vector<LoopT *>::const_iterator iterator; 15406c3fb27SDimitry Andric typedef 15506c3fb27SDimitry Andric typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator; begin()15606c3fb27SDimitry Andric iterator begin() const { return getSubLoops().begin(); } end()15706c3fb27SDimitry Andric iterator end() const { return getSubLoops().end(); } rbegin()15806c3fb27SDimitry Andric reverse_iterator rbegin() const { return getSubLoops().rbegin(); } rend()15906c3fb27SDimitry Andric reverse_iterator rend() const { return getSubLoops().rend(); } 16006c3fb27SDimitry Andric 16106c3fb27SDimitry Andric // LoopInfo does not detect irreducible control flow, just natural 16206c3fb27SDimitry Andric // loops. That is, it is possible that there is cyclic control 16306c3fb27SDimitry Andric // flow within the "innermost loop" or around the "outermost 16406c3fb27SDimitry Andric // loop". 16506c3fb27SDimitry Andric 16606c3fb27SDimitry Andric /// Return true if the loop does not contain any (natural) loops. isInnermost()16706c3fb27SDimitry Andric bool isInnermost() const { return getSubLoops().empty(); } 16806c3fb27SDimitry Andric /// Return true if the loop does not have a parent (natural) loop 16906c3fb27SDimitry Andric // (i.e. it is outermost, which is the same as top-level). isOutermost()17006c3fb27SDimitry Andric bool isOutermost() const { return getParentLoop() == nullptr; } 17106c3fb27SDimitry Andric 17206c3fb27SDimitry Andric /// Get a list of the basic blocks which make up this loop. getBlocks()17306c3fb27SDimitry Andric ArrayRef<BlockT *> getBlocks() const { 17406c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 17506c3fb27SDimitry Andric return Blocks; 17606c3fb27SDimitry Andric } 17706c3fb27SDimitry Andric typedef typename ArrayRef<BlockT *>::const_iterator block_iterator; block_begin()17806c3fb27SDimitry Andric block_iterator block_begin() const { return getBlocks().begin(); } block_end()17906c3fb27SDimitry Andric block_iterator block_end() const { return getBlocks().end(); } blocks()18006c3fb27SDimitry Andric inline iterator_range<block_iterator> blocks() const { 18106c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 18206c3fb27SDimitry Andric return make_range(block_begin(), block_end()); 18306c3fb27SDimitry Andric } 18406c3fb27SDimitry Andric 18506c3fb27SDimitry Andric /// Get the number of blocks in this loop in constant time. 18606c3fb27SDimitry Andric /// Invalidate the loop, indicating that it is no longer a loop. getNumBlocks()18706c3fb27SDimitry Andric unsigned getNumBlocks() const { 18806c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 18906c3fb27SDimitry Andric return Blocks.size(); 19006c3fb27SDimitry Andric } 19106c3fb27SDimitry Andric 19206c3fb27SDimitry Andric /// Return a direct, mutable handle to the blocks vector so that we can 19306c3fb27SDimitry Andric /// mutate it efficiently with techniques like `std::remove`. getBlocksVector()19406c3fb27SDimitry Andric std::vector<BlockT *> &getBlocksVector() { 19506c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 19606c3fb27SDimitry Andric return Blocks; 19706c3fb27SDimitry Andric } 19806c3fb27SDimitry Andric /// Return a direct, mutable handle to the blocks set so that we can 19906c3fb27SDimitry Andric /// mutate it efficiently. getBlocksSet()20006c3fb27SDimitry Andric SmallPtrSetImpl<const BlockT *> &getBlocksSet() { 20106c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 20206c3fb27SDimitry Andric return DenseBlockSet; 20306c3fb27SDimitry Andric } 20406c3fb27SDimitry Andric 20506c3fb27SDimitry Andric /// Return a direct, immutable handle to the blocks set. getBlocksSet()20606c3fb27SDimitry Andric const SmallPtrSetImpl<const BlockT *> &getBlocksSet() const { 20706c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 20806c3fb27SDimitry Andric return DenseBlockSet; 20906c3fb27SDimitry Andric } 21006c3fb27SDimitry Andric 21106c3fb27SDimitry Andric /// Return true if this loop is no longer valid. The only valid use of this 21206c3fb27SDimitry Andric /// helper is "assert(L.isInvalid())" or equivalent, since IsInvalid is set to 21306c3fb27SDimitry Andric /// true by the destructor. In other words, if this accessor returns true, 21406c3fb27SDimitry Andric /// the caller has already triggered UB by calling this accessor; and so it 21506c3fb27SDimitry Andric /// can only be called in a context where a return value of true indicates a 21606c3fb27SDimitry Andric /// programmer error. isInvalid()21706c3fb27SDimitry Andric bool isInvalid() const { 21806c3fb27SDimitry Andric #if LLVM_ENABLE_ABI_BREAKING_CHECKS 21906c3fb27SDimitry Andric return IsInvalid; 22006c3fb27SDimitry Andric #else 22106c3fb27SDimitry Andric return false; 22206c3fb27SDimitry Andric #endif 22306c3fb27SDimitry Andric } 22406c3fb27SDimitry Andric 22506c3fb27SDimitry Andric /// True if terminator in the block can branch to another block that is 22606c3fb27SDimitry Andric /// outside of the current loop. \p BB must be inside the loop. isLoopExiting(const BlockT * BB)22706c3fb27SDimitry Andric bool isLoopExiting(const BlockT *BB) const { 22806c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 22906c3fb27SDimitry Andric assert(contains(BB) && "Exiting block must be part of the loop"); 23006c3fb27SDimitry Andric for (const auto *Succ : children<const BlockT *>(BB)) { 23106c3fb27SDimitry Andric if (!contains(Succ)) 23206c3fb27SDimitry Andric return true; 23306c3fb27SDimitry Andric } 23406c3fb27SDimitry Andric return false; 23506c3fb27SDimitry Andric } 23606c3fb27SDimitry Andric 23706c3fb27SDimitry Andric /// Returns true if \p BB is a loop-latch. 23806c3fb27SDimitry Andric /// A latch block is a block that contains a branch back to the header. 23906c3fb27SDimitry Andric /// This function is useful when there are multiple latches in a loop 24006c3fb27SDimitry Andric /// because \fn getLoopLatch will return nullptr in that case. isLoopLatch(const BlockT * BB)24106c3fb27SDimitry Andric bool isLoopLatch(const BlockT *BB) const { 24206c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 24306c3fb27SDimitry Andric assert(contains(BB) && "block does not belong to the loop"); 244*7a6dacacSDimitry Andric return llvm::is_contained(inverse_children<BlockT *>(getHeader()), BB); 24506c3fb27SDimitry Andric } 24606c3fb27SDimitry Andric 24706c3fb27SDimitry Andric /// Calculate the number of back edges to the loop header. getNumBackEdges()24806c3fb27SDimitry Andric unsigned getNumBackEdges() const { 24906c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 250*7a6dacacSDimitry Andric return llvm::count_if(inverse_children<BlockT *>(getHeader()), 251*7a6dacacSDimitry Andric [&](BlockT *Pred) { return contains(Pred); }); 25206c3fb27SDimitry Andric } 25306c3fb27SDimitry Andric 25406c3fb27SDimitry Andric //===--------------------------------------------------------------------===// 25506c3fb27SDimitry Andric // APIs for simple analysis of the loop. 25606c3fb27SDimitry Andric // 25706c3fb27SDimitry Andric // Note that all of these methods can fail on general loops (ie, there may not 25806c3fb27SDimitry Andric // be a preheader, etc). For best success, the loop simplification and 25906c3fb27SDimitry Andric // induction variable canonicalization pass should be used to normalize loops 26006c3fb27SDimitry Andric // for easy analysis. These methods assume canonical loops. 26106c3fb27SDimitry Andric 26206c3fb27SDimitry Andric /// Return all blocks inside the loop that have successors outside of the 26306c3fb27SDimitry Andric /// loop. These are the blocks _inside of the current loop_ which branch out. 26406c3fb27SDimitry Andric /// The returned list is always unique. 26506c3fb27SDimitry Andric void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const; 26606c3fb27SDimitry Andric 26706c3fb27SDimitry Andric /// If getExitingBlocks would return exactly one block, return that block. 26806c3fb27SDimitry Andric /// Otherwise return null. 26906c3fb27SDimitry Andric BlockT *getExitingBlock() const; 27006c3fb27SDimitry Andric 27106c3fb27SDimitry Andric /// Return all of the successor blocks of this loop. These are the blocks 27206c3fb27SDimitry Andric /// _outside of the current loop_ which are branched to. 27306c3fb27SDimitry Andric void getExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const; 27406c3fb27SDimitry Andric 27506c3fb27SDimitry Andric /// If getExitBlocks would return exactly one block, return that block. 27606c3fb27SDimitry Andric /// Otherwise return null. 27706c3fb27SDimitry Andric BlockT *getExitBlock() const; 27806c3fb27SDimitry Andric 27906c3fb27SDimitry Andric /// Return true if no exit block for the loop has a predecessor that is 28006c3fb27SDimitry Andric /// outside the loop. 28106c3fb27SDimitry Andric bool hasDedicatedExits() const; 28206c3fb27SDimitry Andric 28306c3fb27SDimitry Andric /// Return all unique successor blocks of this loop. 28406c3fb27SDimitry Andric /// These are the blocks _outside of the current loop_ which are branched to. 28506c3fb27SDimitry Andric void getUniqueExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const; 28606c3fb27SDimitry Andric 28706c3fb27SDimitry Andric /// Return all unique successor blocks of this loop except successors from 28806c3fb27SDimitry Andric /// Latch block are not considered. If the exit comes from Latch has also 28906c3fb27SDimitry Andric /// non Latch predecessor in a loop it will be added to ExitBlocks. 29006c3fb27SDimitry Andric /// These are the blocks _outside of the current loop_ which are branched to. 29106c3fb27SDimitry Andric void getUniqueNonLatchExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const; 29206c3fb27SDimitry Andric 29306c3fb27SDimitry Andric /// If getUniqueExitBlocks would return exactly one block, return that block. 29406c3fb27SDimitry Andric /// Otherwise return null. 29506c3fb27SDimitry Andric BlockT *getUniqueExitBlock() const; 29606c3fb27SDimitry Andric 29706c3fb27SDimitry Andric /// Return true if this loop does not have any exit blocks. 29806c3fb27SDimitry Andric bool hasNoExitBlocks() const; 29906c3fb27SDimitry Andric 30006c3fb27SDimitry Andric /// Edge type. 30106c3fb27SDimitry Andric typedef std::pair<BlockT *, BlockT *> Edge; 30206c3fb27SDimitry Andric 30306c3fb27SDimitry Andric /// Return all pairs of (_inside_block_,_outside_block_). 30406c3fb27SDimitry Andric void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const; 30506c3fb27SDimitry Andric 30606c3fb27SDimitry Andric /// If there is a preheader for this loop, return it. A loop has a preheader 30706c3fb27SDimitry Andric /// if there is only one edge to the header of the loop from outside of the 30806c3fb27SDimitry Andric /// loop. If this is the case, the block branching to the header of the loop 30906c3fb27SDimitry Andric /// is the preheader node. 31006c3fb27SDimitry Andric /// 31106c3fb27SDimitry Andric /// This method returns null if there is no preheader for the loop. 31206c3fb27SDimitry Andric BlockT *getLoopPreheader() const; 31306c3fb27SDimitry Andric 31406c3fb27SDimitry Andric /// If the given loop's header has exactly one unique predecessor outside the 31506c3fb27SDimitry Andric /// loop, return it. Otherwise return null. 31606c3fb27SDimitry Andric /// This is less strict that the loop "preheader" concept, which requires 31706c3fb27SDimitry Andric /// the predecessor to have exactly one successor. 31806c3fb27SDimitry Andric BlockT *getLoopPredecessor() const; 31906c3fb27SDimitry Andric 32006c3fb27SDimitry Andric /// If there is a single latch block for this loop, return it. 32106c3fb27SDimitry Andric /// A latch block is a block that contains a branch back to the header. 32206c3fb27SDimitry Andric BlockT *getLoopLatch() const; 32306c3fb27SDimitry Andric 32406c3fb27SDimitry Andric /// Return all loop latch blocks of this loop. A latch block is a block that 32506c3fb27SDimitry Andric /// contains a branch back to the header. getLoopLatches(SmallVectorImpl<BlockT * > & LoopLatches)32606c3fb27SDimitry Andric void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const { 32706c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 32806c3fb27SDimitry Andric BlockT *H = getHeader(); 329*7a6dacacSDimitry Andric for (const auto Pred : inverse_children<BlockT *>(H)) 33006c3fb27SDimitry Andric if (contains(Pred)) 33106c3fb27SDimitry Andric LoopLatches.push_back(Pred); 33206c3fb27SDimitry Andric } 33306c3fb27SDimitry Andric 33406c3fb27SDimitry Andric /// Return all inner loops in the loop nest rooted by the loop in preorder, 33506c3fb27SDimitry Andric /// with siblings in forward program order. 33606c3fb27SDimitry Andric template <class Type> getInnerLoopsInPreorder(const LoopT & L,SmallVectorImpl<Type> & PreOrderLoops)33706c3fb27SDimitry Andric static void getInnerLoopsInPreorder(const LoopT &L, 33806c3fb27SDimitry Andric SmallVectorImpl<Type> &PreOrderLoops) { 33906c3fb27SDimitry Andric SmallVector<LoopT *, 4> PreOrderWorklist; 34006c3fb27SDimitry Andric PreOrderWorklist.append(L.rbegin(), L.rend()); 34106c3fb27SDimitry Andric 34206c3fb27SDimitry Andric while (!PreOrderWorklist.empty()) { 34306c3fb27SDimitry Andric LoopT *L = PreOrderWorklist.pop_back_val(); 34406c3fb27SDimitry Andric // Sub-loops are stored in forward program order, but will process the 34506c3fb27SDimitry Andric // worklist backwards so append them in reverse order. 34606c3fb27SDimitry Andric PreOrderWorklist.append(L->rbegin(), L->rend()); 34706c3fb27SDimitry Andric PreOrderLoops.push_back(L); 34806c3fb27SDimitry Andric } 34906c3fb27SDimitry Andric } 35006c3fb27SDimitry Andric 35106c3fb27SDimitry Andric /// Return all loops in the loop nest rooted by the loop in preorder, with 35206c3fb27SDimitry Andric /// siblings in forward program order. getLoopsInPreorder()35306c3fb27SDimitry Andric SmallVector<const LoopT *, 4> getLoopsInPreorder() const { 35406c3fb27SDimitry Andric SmallVector<const LoopT *, 4> PreOrderLoops; 35506c3fb27SDimitry Andric const LoopT *CurLoop = static_cast<const LoopT *>(this); 35606c3fb27SDimitry Andric PreOrderLoops.push_back(CurLoop); 35706c3fb27SDimitry Andric getInnerLoopsInPreorder(*CurLoop, PreOrderLoops); 35806c3fb27SDimitry Andric return PreOrderLoops; 35906c3fb27SDimitry Andric } getLoopsInPreorder()36006c3fb27SDimitry Andric SmallVector<LoopT *, 4> getLoopsInPreorder() { 36106c3fb27SDimitry Andric SmallVector<LoopT *, 4> PreOrderLoops; 36206c3fb27SDimitry Andric LoopT *CurLoop = static_cast<LoopT *>(this); 36306c3fb27SDimitry Andric PreOrderLoops.push_back(CurLoop); 36406c3fb27SDimitry Andric getInnerLoopsInPreorder(*CurLoop, PreOrderLoops); 36506c3fb27SDimitry Andric return PreOrderLoops; 36606c3fb27SDimitry Andric } 36706c3fb27SDimitry Andric 36806c3fb27SDimitry Andric //===--------------------------------------------------------------------===// 36906c3fb27SDimitry Andric // APIs for updating loop information after changing the CFG 37006c3fb27SDimitry Andric // 37106c3fb27SDimitry Andric 37206c3fb27SDimitry Andric /// This method is used by other analyses to update loop information. 37306c3fb27SDimitry Andric /// NewBB is set to be a new member of the current loop. 37406c3fb27SDimitry Andric /// Because of this, it is added as a member of all parent loops, and is added 37506c3fb27SDimitry Andric /// to the specified LoopInfo object as being in the current basic block. It 37606c3fb27SDimitry Andric /// is not valid to replace the loop header with this method. 37706c3fb27SDimitry Andric void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI); 37806c3fb27SDimitry Andric 37906c3fb27SDimitry Andric /// This is used when splitting loops up. It replaces the OldChild entry in 38006c3fb27SDimitry Andric /// our children list with NewChild, and updates the parent pointer of 38106c3fb27SDimitry Andric /// OldChild to be null and the NewChild to be this loop. 38206c3fb27SDimitry Andric /// This updates the loop depth of the new child. 38306c3fb27SDimitry Andric void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild); 38406c3fb27SDimitry Andric 38506c3fb27SDimitry Andric /// Add the specified loop to be a child of this loop. 38606c3fb27SDimitry Andric /// This updates the loop depth of the new child. addChildLoop(LoopT * NewChild)38706c3fb27SDimitry Andric void addChildLoop(LoopT *NewChild) { 38806c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 38906c3fb27SDimitry Andric assert(!NewChild->ParentLoop && "NewChild already has a parent!"); 39006c3fb27SDimitry Andric NewChild->ParentLoop = static_cast<LoopT *>(this); 39106c3fb27SDimitry Andric SubLoops.push_back(NewChild); 39206c3fb27SDimitry Andric } 39306c3fb27SDimitry Andric 39406c3fb27SDimitry Andric /// This removes the specified child from being a subloop of this loop. The 39506c3fb27SDimitry Andric /// loop is not deleted, as it will presumably be inserted into another loop. removeChildLoop(iterator I)39606c3fb27SDimitry Andric LoopT *removeChildLoop(iterator I) { 39706c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 39806c3fb27SDimitry Andric assert(I != SubLoops.end() && "Cannot remove end iterator!"); 39906c3fb27SDimitry Andric LoopT *Child = *I; 40006c3fb27SDimitry Andric assert(Child->ParentLoop == this && "Child is not a child of this loop!"); 40106c3fb27SDimitry Andric SubLoops.erase(SubLoops.begin() + (I - begin())); 40206c3fb27SDimitry Andric Child->ParentLoop = nullptr; 40306c3fb27SDimitry Andric return Child; 40406c3fb27SDimitry Andric } 40506c3fb27SDimitry Andric 40606c3fb27SDimitry Andric /// This removes the specified child from being a subloop of this loop. The 40706c3fb27SDimitry Andric /// loop is not deleted, as it will presumably be inserted into another loop. removeChildLoop(LoopT * Child)40806c3fb27SDimitry Andric LoopT *removeChildLoop(LoopT *Child) { 40906c3fb27SDimitry Andric return removeChildLoop(llvm::find(*this, Child)); 41006c3fb27SDimitry Andric } 41106c3fb27SDimitry Andric 41206c3fb27SDimitry Andric /// This adds a basic block directly to the basic block list. 41306c3fb27SDimitry Andric /// This should only be used by transformations that create new loops. Other 41406c3fb27SDimitry Andric /// transformations should use addBasicBlockToLoop. addBlockEntry(BlockT * BB)41506c3fb27SDimitry Andric void addBlockEntry(BlockT *BB) { 41606c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 41706c3fb27SDimitry Andric Blocks.push_back(BB); 41806c3fb27SDimitry Andric DenseBlockSet.insert(BB); 41906c3fb27SDimitry Andric } 42006c3fb27SDimitry Andric 42106c3fb27SDimitry Andric /// interface to reverse Blocks[from, end of loop] in this loop reverseBlock(unsigned from)42206c3fb27SDimitry Andric void reverseBlock(unsigned from) { 42306c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 42406c3fb27SDimitry Andric std::reverse(Blocks.begin() + from, Blocks.end()); 42506c3fb27SDimitry Andric } 42606c3fb27SDimitry Andric 42706c3fb27SDimitry Andric /// interface to do reserve() for Blocks reserveBlocks(unsigned size)42806c3fb27SDimitry Andric void reserveBlocks(unsigned size) { 42906c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 43006c3fb27SDimitry Andric Blocks.reserve(size); 43106c3fb27SDimitry Andric } 43206c3fb27SDimitry Andric 43306c3fb27SDimitry Andric /// This method is used to move BB (which must be part of this loop) to be the 43406c3fb27SDimitry Andric /// loop header of the loop (the block that dominates all others). moveToHeader(BlockT * BB)43506c3fb27SDimitry Andric void moveToHeader(BlockT *BB) { 43606c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 43706c3fb27SDimitry Andric if (Blocks[0] == BB) 43806c3fb27SDimitry Andric return; 43906c3fb27SDimitry Andric for (unsigned i = 0;; ++i) { 44006c3fb27SDimitry Andric assert(i != Blocks.size() && "Loop does not contain BB!"); 44106c3fb27SDimitry Andric if (Blocks[i] == BB) { 44206c3fb27SDimitry Andric Blocks[i] = Blocks[0]; 44306c3fb27SDimitry Andric Blocks[0] = BB; 44406c3fb27SDimitry Andric return; 44506c3fb27SDimitry Andric } 44606c3fb27SDimitry Andric } 44706c3fb27SDimitry Andric } 44806c3fb27SDimitry Andric 44906c3fb27SDimitry Andric /// This removes the specified basic block from the current loop, updating the 45006c3fb27SDimitry Andric /// Blocks as appropriate. This does not update the mapping in the LoopInfo 45106c3fb27SDimitry Andric /// class. removeBlockFromLoop(BlockT * BB)45206c3fb27SDimitry Andric void removeBlockFromLoop(BlockT *BB) { 45306c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 45406c3fb27SDimitry Andric auto I = find(Blocks, BB); 45506c3fb27SDimitry Andric assert(I != Blocks.end() && "N is not in this list!"); 45606c3fb27SDimitry Andric Blocks.erase(I); 45706c3fb27SDimitry Andric 45806c3fb27SDimitry Andric DenseBlockSet.erase(BB); 45906c3fb27SDimitry Andric } 46006c3fb27SDimitry Andric 46106c3fb27SDimitry Andric /// Verify loop structure 46206c3fb27SDimitry Andric void verifyLoop() const; 46306c3fb27SDimitry Andric 46406c3fb27SDimitry Andric /// Verify loop structure of this loop and all nested loops. 46506c3fb27SDimitry Andric void verifyLoopNest(DenseSet<const LoopT *> *Loops) const; 46606c3fb27SDimitry Andric 46706c3fb27SDimitry Andric /// Returns true if the loop is annotated parallel. 46806c3fb27SDimitry Andric /// 46906c3fb27SDimitry Andric /// Derived classes can override this method using static template 47006c3fb27SDimitry Andric /// polymorphism. isAnnotatedParallel()47106c3fb27SDimitry Andric bool isAnnotatedParallel() const { return false; } 47206c3fb27SDimitry Andric 47306c3fb27SDimitry Andric /// Print loop with all the BBs inside it. 47406c3fb27SDimitry Andric void print(raw_ostream &OS, bool Verbose = false, bool PrintNested = true, 47506c3fb27SDimitry Andric unsigned Depth = 0) const; 47606c3fb27SDimitry Andric 47706c3fb27SDimitry Andric protected: 47806c3fb27SDimitry Andric friend class LoopInfoBase<BlockT, LoopT>; 47906c3fb27SDimitry Andric 48006c3fb27SDimitry Andric /// This creates an empty loop. LoopBase()48106c3fb27SDimitry Andric LoopBase() : ParentLoop(nullptr) {} 48206c3fb27SDimitry Andric LoopBase(BlockT * BB)48306c3fb27SDimitry Andric explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) { 48406c3fb27SDimitry Andric Blocks.push_back(BB); 48506c3fb27SDimitry Andric DenseBlockSet.insert(BB); 48606c3fb27SDimitry Andric } 48706c3fb27SDimitry Andric 48806c3fb27SDimitry Andric // Since loop passes like SCEV are allowed to key analysis results off of 48906c3fb27SDimitry Andric // `Loop` pointers, we cannot re-use pointers within a loop pass manager. 49006c3fb27SDimitry Andric // This means loop passes should not be `delete` ing `Loop` objects directly 49106c3fb27SDimitry Andric // (and risk a later `Loop` allocation re-using the address of a previous one) 49206c3fb27SDimitry Andric // but should be using LoopInfo::markAsRemoved, which keeps around the `Loop` 49306c3fb27SDimitry Andric // pointer till the end of the lifetime of the `LoopInfo` object. 49406c3fb27SDimitry Andric // 49506c3fb27SDimitry Andric // To make it easier to follow this rule, we mark the destructor as 49606c3fb27SDimitry Andric // non-public. ~LoopBase()49706c3fb27SDimitry Andric ~LoopBase() { 49806c3fb27SDimitry Andric for (auto *SubLoop : SubLoops) 49906c3fb27SDimitry Andric SubLoop->~LoopT(); 50006c3fb27SDimitry Andric 50106c3fb27SDimitry Andric #if LLVM_ENABLE_ABI_BREAKING_CHECKS 50206c3fb27SDimitry Andric IsInvalid = true; 50306c3fb27SDimitry Andric #endif 50406c3fb27SDimitry Andric SubLoops.clear(); 50506c3fb27SDimitry Andric Blocks.clear(); 50606c3fb27SDimitry Andric DenseBlockSet.clear(); 50706c3fb27SDimitry Andric ParentLoop = nullptr; 50806c3fb27SDimitry Andric } 50906c3fb27SDimitry Andric }; 51006c3fb27SDimitry Andric 51106c3fb27SDimitry Andric template <class BlockT, class LoopT> 51206c3fb27SDimitry Andric raw_ostream &operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) { 51306c3fb27SDimitry Andric Loop.print(OS); 51406c3fb27SDimitry Andric return OS; 51506c3fb27SDimitry Andric } 51606c3fb27SDimitry Andric 51706c3fb27SDimitry Andric //===----------------------------------------------------------------------===// 51806c3fb27SDimitry Andric /// This class builds and contains all of the top-level loop 51906c3fb27SDimitry Andric /// structures in the specified function. 52006c3fb27SDimitry Andric /// 52106c3fb27SDimitry Andric 52206c3fb27SDimitry Andric template <class BlockT, class LoopT> class LoopInfoBase { 52306c3fb27SDimitry Andric // BBMap - Mapping of basic blocks to the inner most loop they occur in 52406c3fb27SDimitry Andric DenseMap<const BlockT *, LoopT *> BBMap; 52506c3fb27SDimitry Andric std::vector<LoopT *> TopLevelLoops; 52606c3fb27SDimitry Andric BumpPtrAllocator LoopAllocator; 52706c3fb27SDimitry Andric 52806c3fb27SDimitry Andric friend class LoopBase<BlockT, LoopT>; 52906c3fb27SDimitry Andric friend class LoopInfo; 53006c3fb27SDimitry Andric 53106c3fb27SDimitry Andric void operator=(const LoopInfoBase &) = delete; 53206c3fb27SDimitry Andric LoopInfoBase(const LoopInfoBase &) = delete; 53306c3fb27SDimitry Andric 53406c3fb27SDimitry Andric public: 53506c3fb27SDimitry Andric LoopInfoBase() = default; ~LoopInfoBase()53606c3fb27SDimitry Andric ~LoopInfoBase() { releaseMemory(); } 53706c3fb27SDimitry Andric LoopInfoBase(LoopInfoBase && Arg)53806c3fb27SDimitry Andric LoopInfoBase(LoopInfoBase &&Arg) 53906c3fb27SDimitry Andric : BBMap(std::move(Arg.BBMap)), 54006c3fb27SDimitry Andric TopLevelLoops(std::move(Arg.TopLevelLoops)), 54106c3fb27SDimitry Andric LoopAllocator(std::move(Arg.LoopAllocator)) { 54206c3fb27SDimitry Andric // We have to clear the arguments top level loops as we've taken ownership. 54306c3fb27SDimitry Andric Arg.TopLevelLoops.clear(); 54406c3fb27SDimitry Andric } 54506c3fb27SDimitry Andric LoopInfoBase &operator=(LoopInfoBase &&RHS) { 54606c3fb27SDimitry Andric BBMap = std::move(RHS.BBMap); 54706c3fb27SDimitry Andric 54806c3fb27SDimitry Andric for (auto *L : TopLevelLoops) 54906c3fb27SDimitry Andric L->~LoopT(); 55006c3fb27SDimitry Andric 55106c3fb27SDimitry Andric TopLevelLoops = std::move(RHS.TopLevelLoops); 55206c3fb27SDimitry Andric LoopAllocator = std::move(RHS.LoopAllocator); 55306c3fb27SDimitry Andric RHS.TopLevelLoops.clear(); 55406c3fb27SDimitry Andric return *this; 55506c3fb27SDimitry Andric } 55606c3fb27SDimitry Andric releaseMemory()55706c3fb27SDimitry Andric void releaseMemory() { 55806c3fb27SDimitry Andric BBMap.clear(); 55906c3fb27SDimitry Andric 56006c3fb27SDimitry Andric for (auto *L : TopLevelLoops) 56106c3fb27SDimitry Andric L->~LoopT(); 56206c3fb27SDimitry Andric TopLevelLoops.clear(); 56306c3fb27SDimitry Andric LoopAllocator.Reset(); 56406c3fb27SDimitry Andric } 56506c3fb27SDimitry Andric AllocateLoop(ArgsTy &&...Args)56606c3fb27SDimitry Andric template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&...Args) { 56706c3fb27SDimitry Andric LoopT *Storage = LoopAllocator.Allocate<LoopT>(); 56806c3fb27SDimitry Andric return new (Storage) LoopT(std::forward<ArgsTy>(Args)...); 56906c3fb27SDimitry Andric } 57006c3fb27SDimitry Andric 57106c3fb27SDimitry Andric /// iterator/begin/end - The interface to the top-level loops in the current 57206c3fb27SDimitry Andric /// function. 57306c3fb27SDimitry Andric /// 57406c3fb27SDimitry Andric typedef typename std::vector<LoopT *>::const_iterator iterator; 57506c3fb27SDimitry Andric typedef 57606c3fb27SDimitry Andric typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator; begin()57706c3fb27SDimitry Andric iterator begin() const { return TopLevelLoops.begin(); } end()57806c3fb27SDimitry Andric iterator end() const { return TopLevelLoops.end(); } rbegin()57906c3fb27SDimitry Andric reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); } rend()58006c3fb27SDimitry Andric reverse_iterator rend() const { return TopLevelLoops.rend(); } empty()58106c3fb27SDimitry Andric bool empty() const { return TopLevelLoops.empty(); } 58206c3fb27SDimitry Andric 58306c3fb27SDimitry Andric /// Return all of the loops in the function in preorder across the loop 58406c3fb27SDimitry Andric /// nests, with siblings in forward program order. 58506c3fb27SDimitry Andric /// 58606c3fb27SDimitry Andric /// Note that because loops form a forest of trees, preorder is equivalent to 58706c3fb27SDimitry Andric /// reverse postorder. 58806c3fb27SDimitry Andric SmallVector<LoopT *, 4> getLoopsInPreorder() const; 58906c3fb27SDimitry Andric 59006c3fb27SDimitry Andric /// Return all of the loops in the function in preorder across the loop 59106c3fb27SDimitry Andric /// nests, with siblings in *reverse* program order. 59206c3fb27SDimitry Andric /// 59306c3fb27SDimitry Andric /// Note that because loops form a forest of trees, preorder is equivalent to 59406c3fb27SDimitry Andric /// reverse postorder. 59506c3fb27SDimitry Andric /// 59606c3fb27SDimitry Andric /// Also note that this is *not* a reverse preorder. Only the siblings are in 59706c3fb27SDimitry Andric /// reverse program order. 59806c3fb27SDimitry Andric SmallVector<LoopT *, 4> getLoopsInReverseSiblingPreorder() const; 59906c3fb27SDimitry Andric 60006c3fb27SDimitry Andric /// Return the inner most loop that BB lives in. If a basic block is in no 60106c3fb27SDimitry Andric /// loop (for example the entry node), null is returned. getLoopFor(const BlockT * BB)60206c3fb27SDimitry Andric LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); } 60306c3fb27SDimitry Andric 60406c3fb27SDimitry Andric /// Same as getLoopFor. 60506c3fb27SDimitry Andric const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); } 60606c3fb27SDimitry Andric 60706c3fb27SDimitry Andric /// Return the loop nesting level of the specified block. A depth of 0 means 60806c3fb27SDimitry Andric /// the block is not inside any loop. getLoopDepth(const BlockT * BB)60906c3fb27SDimitry Andric unsigned getLoopDepth(const BlockT *BB) const { 61006c3fb27SDimitry Andric const LoopT *L = getLoopFor(BB); 61106c3fb27SDimitry Andric return L ? L->getLoopDepth() : 0; 61206c3fb27SDimitry Andric } 61306c3fb27SDimitry Andric 61406c3fb27SDimitry Andric // True if the block is a loop header node isLoopHeader(const BlockT * BB)61506c3fb27SDimitry Andric bool isLoopHeader(const BlockT *BB) const { 61606c3fb27SDimitry Andric const LoopT *L = getLoopFor(BB); 61706c3fb27SDimitry Andric return L && L->getHeader() == BB; 61806c3fb27SDimitry Andric } 61906c3fb27SDimitry Andric 62006c3fb27SDimitry Andric /// Return the top-level loops. getTopLevelLoops()62106c3fb27SDimitry Andric const std::vector<LoopT *> &getTopLevelLoops() const { return TopLevelLoops; } 62206c3fb27SDimitry Andric 62306c3fb27SDimitry Andric /// Return the top-level loops. getTopLevelLoopsVector()62406c3fb27SDimitry Andric std::vector<LoopT *> &getTopLevelLoopsVector() { return TopLevelLoops; } 62506c3fb27SDimitry Andric 62606c3fb27SDimitry Andric /// This removes the specified top-level loop from this loop info object. 62706c3fb27SDimitry Andric /// The loop is not deleted, as it will presumably be inserted into 62806c3fb27SDimitry Andric /// another loop. removeLoop(iterator I)62906c3fb27SDimitry Andric LoopT *removeLoop(iterator I) { 63006c3fb27SDimitry Andric assert(I != end() && "Cannot remove end iterator!"); 63106c3fb27SDimitry Andric LoopT *L = *I; 63206c3fb27SDimitry Andric assert(L->isOutermost() && "Not a top-level loop!"); 63306c3fb27SDimitry Andric TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin())); 63406c3fb27SDimitry Andric return L; 63506c3fb27SDimitry Andric } 63606c3fb27SDimitry Andric 63706c3fb27SDimitry Andric /// Change the top-level loop that contains BB to the specified loop. 63806c3fb27SDimitry Andric /// This should be used by transformations that restructure the loop hierarchy 63906c3fb27SDimitry Andric /// tree. changeLoopFor(BlockT * BB,LoopT * L)64006c3fb27SDimitry Andric void changeLoopFor(BlockT *BB, LoopT *L) { 64106c3fb27SDimitry Andric if (!L) { 64206c3fb27SDimitry Andric BBMap.erase(BB); 64306c3fb27SDimitry Andric return; 64406c3fb27SDimitry Andric } 64506c3fb27SDimitry Andric BBMap[BB] = L; 64606c3fb27SDimitry Andric } 64706c3fb27SDimitry Andric 64806c3fb27SDimitry Andric /// Replace the specified loop in the top-level loops list with the indicated 64906c3fb27SDimitry Andric /// loop. changeTopLevelLoop(LoopT * OldLoop,LoopT * NewLoop)65006c3fb27SDimitry Andric void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) { 65106c3fb27SDimitry Andric auto I = find(TopLevelLoops, OldLoop); 65206c3fb27SDimitry Andric assert(I != TopLevelLoops.end() && "Old loop not at top level!"); 65306c3fb27SDimitry Andric *I = NewLoop; 65406c3fb27SDimitry Andric assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop && 65506c3fb27SDimitry Andric "Loops already embedded into a subloop!"); 65606c3fb27SDimitry Andric } 65706c3fb27SDimitry Andric 65806c3fb27SDimitry Andric /// This adds the specified loop to the collection of top-level loops. addTopLevelLoop(LoopT * New)65906c3fb27SDimitry Andric void addTopLevelLoop(LoopT *New) { 66006c3fb27SDimitry Andric assert(New->isOutermost() && "Loop already in subloop!"); 66106c3fb27SDimitry Andric TopLevelLoops.push_back(New); 66206c3fb27SDimitry Andric } 66306c3fb27SDimitry Andric 66406c3fb27SDimitry Andric /// This method completely removes BB from all data structures, 66506c3fb27SDimitry Andric /// including all of the Loop objects it is nested in and our mapping from 66606c3fb27SDimitry Andric /// BasicBlocks to loops. removeBlock(BlockT * BB)66706c3fb27SDimitry Andric void removeBlock(BlockT *BB) { 66806c3fb27SDimitry Andric auto I = BBMap.find(BB); 66906c3fb27SDimitry Andric if (I != BBMap.end()) { 67006c3fb27SDimitry Andric for (LoopT *L = I->second; L; L = L->getParentLoop()) 67106c3fb27SDimitry Andric L->removeBlockFromLoop(BB); 67206c3fb27SDimitry Andric 67306c3fb27SDimitry Andric BBMap.erase(I); 67406c3fb27SDimitry Andric } 67506c3fb27SDimitry Andric } 67606c3fb27SDimitry Andric 67706c3fb27SDimitry Andric // Internals 67806c3fb27SDimitry Andric isNotAlreadyContainedIn(const LoopT * SubLoop,const LoopT * ParentLoop)67906c3fb27SDimitry Andric static bool isNotAlreadyContainedIn(const LoopT *SubLoop, 68006c3fb27SDimitry Andric const LoopT *ParentLoop) { 68106c3fb27SDimitry Andric if (!SubLoop) 68206c3fb27SDimitry Andric return true; 68306c3fb27SDimitry Andric if (SubLoop == ParentLoop) 68406c3fb27SDimitry Andric return false; 68506c3fb27SDimitry Andric return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop); 68606c3fb27SDimitry Andric } 68706c3fb27SDimitry Andric 68806c3fb27SDimitry Andric /// Create the loop forest using a stable algorithm. 68906c3fb27SDimitry Andric void analyze(const DominatorTreeBase<BlockT, false> &DomTree); 69006c3fb27SDimitry Andric 69106c3fb27SDimitry Andric // Debugging 69206c3fb27SDimitry Andric void print(raw_ostream &OS) const; 69306c3fb27SDimitry Andric 69406c3fb27SDimitry Andric void verify(const DominatorTreeBase<BlockT, false> &DomTree) const; 69506c3fb27SDimitry Andric 69606c3fb27SDimitry Andric /// Destroy a loop that has been removed from the `LoopInfo` nest. 69706c3fb27SDimitry Andric /// 69806c3fb27SDimitry Andric /// This runs the destructor of the loop object making it invalid to 69906c3fb27SDimitry Andric /// reference afterward. The memory is retained so that the *pointer* to the 70006c3fb27SDimitry Andric /// loop remains valid. 70106c3fb27SDimitry Andric /// 70206c3fb27SDimitry Andric /// The caller is responsible for removing this loop from the loop nest and 70306c3fb27SDimitry Andric /// otherwise disconnecting it from the broader `LoopInfo` data structures. 70406c3fb27SDimitry Andric /// Callers that don't naturally handle this themselves should probably call 70506c3fb27SDimitry Andric /// `erase' instead. destroy(LoopT * L)70606c3fb27SDimitry Andric void destroy(LoopT *L) { 70706c3fb27SDimitry Andric L->~LoopT(); 70806c3fb27SDimitry Andric 70906c3fb27SDimitry Andric // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons 71006c3fb27SDimitry Andric // \c L, but the pointer remains valid for non-dereferencing uses. 71106c3fb27SDimitry Andric LoopAllocator.Deallocate(L); 71206c3fb27SDimitry Andric } 71306c3fb27SDimitry Andric }; 71406c3fb27SDimitry Andric 71506c3fb27SDimitry Andric } // namespace llvm 71606c3fb27SDimitry Andric 71706c3fb27SDimitry Andric #endif // LLVM_SUPPORT_GENERICLOOPINFO_H 718