GenericLoopInfo.h

Go to the documentation of this file.

//===- GenericLoopInfo - Generic Loop Info for graphs -----------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the LoopInfoBase class that is used to identify natural
// loops and determine the loop depth of various nodes in a generic graph of
// blocks.  A natural loop has exactly one entry-point, which is called the
// header. Note that natural loops may actually be several loops that share the
// same header node.
//
// This analysis calculates the nesting structure of loops in a function.  For
// each natural loop identified, this analysis identifies natural loops
// contained entirely within the loop and the basic blocks that make up the
// loop.
//
// It can calculate on the fly various bits of information, for example:
//
//  * whether there is a preheader for the loop
//  * the number of back edges to the header
//  * whether or not a particular block branches out of the loop
//  * the successor blocks of the loop
//  * the loop depth
//  * etc...
//
// Note that this analysis specifically identifies *Loops* not cycles or SCCs
// in the graph.  There can be strongly connected components in the graph which
// this analysis will not recognize and that will not be represented by a Loop
// instance.  In particular, a Loop might be inside such a non-loop SCC, or a
// non-loop SCC might contain a sub-SCC which is a Loop.
//
// For an overview of terminology used in this API (and thus all of our loop
// analyses or transforms), see docs/LoopTerminology.md.
//
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_SUPPORT_GENERICLOOPINFO_H
#define LLVM_SUPPORT_GENERICLOOPINFO_H
 
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/GenericDomTree.h"
 
namespace llvm {
 
template <class N, class M> class LoopInfoBase;
template <class N, class M> class LoopBase;
 
//===----------------------------------------------------------------------===//
/// Instances of this class are used to represent loops that are detected in the
/// flow graph.
///
template <class BlockT, class LoopT> class LoopBase {
  LoopT *ParentLoop;
  // Loops contained entirely within this one.
  std::vector<LoopT *> SubLoops;
 
  // The list of blocks in this loop; first entry is the header. Either borrows
  // a slice of the owning LoopInfo's BlockLayout, marked by the
  // BorrowedCapacity sentinel, or is a private allocation of BlockCapacity
  // slots from its allocator.
  //
  // Until analyze()'s layout carve runs, PendingHeader stashes the loop header
  // (see pendingHeader()).
  union {
    BlockT *PendingHeader;
    BlockT **BlockData = nullptr;
  };
  unsigned BlockLen = 0;
  unsigned BlockCapacity = 0;
 
  static constexpr unsigned BorrowedCapacity = -1u;
 
  // The LoopInfo that owns this loop. Used to answer contains(BlockT *) from
  // the central block-to-loop map.
  LoopInfoBase<BlockT, LoopT> *LI = nullptr;
 
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
  /// Indicator that this loop is no longer a valid loop.
  bool IsInvalid = false;
#endif
 
  LoopBase(const LoopBase<BlockT, LoopT> &) = delete;
  const LoopBase<BlockT, LoopT> &
  operator=(const LoopBase<BlockT, LoopT> &) = delete;
 
public:
  /// Return the nesting level of this loop.  An outer-most loop has depth 1,
  /// for consistency with loop depth values used for basic blocks, where depth
  /// 0 is used for blocks not inside any loops.
  unsigned getLoopDepth() const {
    assert(!isInvalid() && "Loop not in a valid state!");
    unsigned D = 1;
    for (const LoopT *CurLoop = ParentLoop; CurLoop;
         CurLoop = CurLoop->ParentLoop)
      ++D;
    return D;
  }
  BlockT *getHeader() const { return getBlocks().front(); }
  /// Return the parent loop if it exists or nullptr for top
  /// level loops.
 
  /// A loop is either top-level in a function (that is, it is not
  /// contained in any other loop) or it is entirely enclosed in
  /// some other loop.
  /// If a loop is top-level, it has no parent, otherwise its
  /// parent is the innermost loop in which it is enclosed.
  LoopT *getParentLoop() const { return ParentLoop; }
 
  /// Get the outermost loop in which this loop is contained.
  /// This may be the loop itself, if it already is the outermost loop.
  const LoopT *getOutermostLoop() const {
    const LoopT *L = static_cast<const LoopT *>(this);
    while (L->ParentLoop)
      L = L->ParentLoop;
    return L;
  }
 
  LoopT *getOutermostLoop() {
    LoopT *L = static_cast<LoopT *>(this);
    while (L->ParentLoop)
      L = L->ParentLoop;
    return L;
  }
 
  /// This is a raw interface for bypassing addChildLoop.
  void setParentLoop(LoopT *L) {
    assert(!isInvalid() && "Loop not in a valid state!");
    ParentLoop = L;
  }
 
  /// Return true if the specified loop is contained within this loop.
  ///
  /// This walks the parent chain and is O(depth). Deep nesting is not a
  /// performance target (yet).
  bool contains(const LoopT *L) const {
    assert(!isInvalid() && "Loop not in a valid state!");
    for (;;) {
      if (L == this)
        return true;
      if (!L)
        return false;
      L = L->getParentLoop();
    }
  }
 
  /// Return true if the specified basic block is in this loop, using LoopInfo's
  /// block-to-loop map.
  ///
  /// This is only valid when that map agrees with the block lists. Avoid when
  /// the loop nest is being restructured, when a block may appear in a loop's
  /// block list before it is mapped to that loop. Code in such a transient
  /// state must scan getBlocks() directly instead.
  bool contains(const BlockT *BB) const {
    assert(!isInvalid() && "Loop not in a valid state!");
    // A block from another function is never contained, and its number would
    // otherwise index this function's map.
    if (BB->getParent() != LI->ParentPtr)
      return false;
    return contains(LI->lookupLoopFor(BB));
  }
 
  /// Return true if the specified instruction is in this loop.
  template <class InstT> bool contains(const InstT *Inst) const {
    return contains(Inst->getParent());
  }
 
  /// Return the loops contained entirely within this loop.
  const std::vector<LoopT *> &getSubLoops() const {
    assert(!isInvalid() && "Loop not in a valid state!");
    return SubLoops;
  }
  using iterator = typename std::vector<LoopT *>::const_iterator;
  using reverse_iterator =
      typename std::vector<LoopT *>::const_reverse_iterator;
  iterator begin() const { return getSubLoops().begin(); }
  iterator end() const { return getSubLoops().end(); }
  reverse_iterator rbegin() const { return getSubLoops().rbegin(); }
  reverse_iterator rend() const { return getSubLoops().rend(); }
 
  // LoopInfo does not detect irreducible control flow, just natural
  // loops. That is, it is possible that there is cyclic control
  // flow within the "innermost loop" or around the "outermost
  // loop".
 
  /// Return true if the loop does not contain any (natural) loops.
  bool isInnermost() const { return getSubLoops().empty(); }
  /// Return true if the loop does not have a parent (natural) loop
  // (i.e. it is outermost, which is the same as top-level).
  bool isOutermost() const { return getParentLoop() == nullptr; }
 
  /// Get a list of the basic blocks which make up this loop.
  ArrayRef<BlockT *> getBlocks() const {
    assert(!isInvalid() && "Loop not in a valid state!");
    return ArrayRef<BlockT *>(BlockData, BlockLen);
  }
  using block_iterator = typename ArrayRef<BlockT *>::const_iterator;
  block_iterator block_begin() const { return getBlocks().begin(); }
  block_iterator block_end() const { return getBlocks().end(); }
  inline iterator_range<block_iterator> blocks() const {
    assert(!isInvalid() && "Loop not in a valid state!");
    return make_range(block_begin(), block_end());
  }
 
  /// Get the number of blocks in this loop in constant time.
  /// Invalidate the loop, indicating that it is no longer a loop.
  unsigned getNumBlocks() const {
    assert(!isInvalid() && "Loop not in a valid state!");
    return BlockLen;
  }
 
  /// Return true if this loop is no longer valid.  The only valid use of this
  /// helper is "assert(L.isInvalid())" or equivalent, since IsInvalid is set to
  /// true by the destructor.  In other words, if this accessor returns true,
  /// the caller has already triggered UB by calling this accessor; and so it
  /// can only be called in a context where a return value of true indicates a
  /// programmer error.
  bool isInvalid() const {
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
    return IsInvalid;
#else
    return false;
#endif
  }
 
  /// True if terminator in the block can branch to another block that is
  /// outside of the current loop. \p BB must be inside the loop.
  bool isLoopExiting(const BlockT *BB) const {
    assert(!isInvalid() && "Loop not in a valid state!");
    assert(contains(BB) && "Exiting block must be part of the loop");
    for (const auto *Succ : children<const BlockT *>(BB)) {
      if (!contains(Succ))
        return true;
    }
    return false;
  }
 
  /// Returns true if \p BB is a loop-latch.
  /// A latch block is a block that contains a branch back to the header.
  /// This function is useful when there are multiple latches in a loop
  /// because \fn getLoopLatch will return nullptr in that case.
  bool isLoopLatch(const BlockT *BB) const {
    assert(!isInvalid() && "Loop not in a valid state!");
    assert(contains(BB) && "block does not belong to the loop");
    return llvm::is_contained(inverse_children<BlockT *>(getHeader()), BB);
  }
 
  /// Calculate the number of back edges to the loop header.
  unsigned getNumBackEdges() const {
    assert(!isInvalid() && "Loop not in a valid state!");
    return llvm::count_if(inverse_children<BlockT *>(getHeader()),
                          [&](BlockT *Pred) { return contains(Pred); });
  }
 
  //===--------------------------------------------------------------------===//
  // APIs for simple analysis of the loop.
  //
  // Note that all of these methods can fail on general loops (ie, there may not
  // be a preheader, etc).  For best success, the loop simplification and
  // induction variable canonicalization pass should be used to normalize loops
  // for easy analysis.  These methods assume canonical loops.
 
  /// Return all blocks inside the loop that have successors outside of the
  /// loop. These are the blocks _inside of the current loop_ which branch out.
  /// The returned list is always unique.
  void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const;
 
  /// If getExitingBlocks would return exactly one block, return that block.
  /// Otherwise return null.
  BlockT *getExitingBlock() const;
 
  /// Return all of the successor blocks of this loop. These are the blocks
  /// _outside of the current loop_ which are branched to.
  void getExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
 
  /// If getExitBlocks would return exactly one block, return that block.
  /// Otherwise return null.
  BlockT *getExitBlock() const;
 
  /// Return true if no exit block for the loop has a predecessor that is
  /// outside the loop.
  bool hasDedicatedExits() const;
 
  /// Return all unique successor blocks of this loop.
  /// These are the blocks _outside of the current loop_ which are branched to.
  void getUniqueExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
 
  /// Return all unique successor blocks of this loop except successors from
  /// Latch block are not considered. If the exit comes from Latch has also
  /// non Latch predecessor in a loop it will be added to ExitBlocks.
  /// These are the blocks _outside of the current loop_ which are branched to.
  void getUniqueNonLatchExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
 
  /// If getUniqueExitBlocks would return exactly one block, return that block.
  /// Otherwise return null.
  BlockT *getUniqueExitBlock() const;
 
  /// If there is a preheader for this loop, return it. A loop has a preheader
  /// if there is only one edge to the header of the loop from outside of the
  /// loop. If this is the case, the block branching to the header of the loop
  /// is the preheader node.
  ///
  /// This method returns null if there is no preheader for the loop.
  BlockT *getLoopPreheader() const;
 
  /// If the given loop's header has exactly one unique predecessor outside the
  /// loop, return it. Otherwise return null.
  ///  This is less strict that the loop "preheader" concept, which requires
  /// the predecessor to have exactly one successor.
  BlockT *getLoopPredecessor() const;
 
  /// If there is a single latch block for this loop, return it.
  /// A latch block is a block that contains a branch back to the header.
  BlockT *getLoopLatch() const;
 
  /// Return all loop latch blocks of this loop. A latch block is a block that
  /// contains a branch back to the header.
  void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
    assert(!isInvalid() && "Loop not in a valid state!");
    BlockT *H = getHeader();
    for (const auto Pred : inverse_children<BlockT *>(H))
      if (contains(Pred))
        LoopLatches.push_back(Pred);
  }
 
  /// Return all inner loops in the loop nest rooted by the loop in preorder,
  /// with siblings in forward program order.
  template <class Type>
  static void getInnerLoopsInPreorder(const LoopT &L,
                                      SmallVectorImpl<Type> &PreOrderLoops) {
    SmallVector<LoopT *, 4> PreOrderWorklist;
    PreOrderWorklist.append(L.rbegin(), L.rend());
 
    while (!PreOrderWorklist.empty()) {
      LoopT *L = PreOrderWorklist.pop_back_val();
      // Sub-loops are stored in forward program order, but will process the
      // worklist backwards so append them in reverse order.
      PreOrderWorklist.append(L->rbegin(), L->rend());
      PreOrderLoops.push_back(L);
    }
  }
 
  /// Return all loops in the loop nest rooted by the loop in preorder, with
  /// siblings in forward program order.
  SmallVector<const LoopT *, 4> getLoopsInPreorder() const {
    SmallVector<const LoopT *, 4> PreOrderLoops;
    const LoopT *CurLoop = static_cast<const LoopT *>(this);
    PreOrderLoops.push_back(CurLoop);
    getInnerLoopsInPreorder(*CurLoop, PreOrderLoops);
    return PreOrderLoops;
  }
  SmallVector<LoopT *, 4> getLoopsInPreorder() {
    SmallVector<LoopT *, 4> PreOrderLoops;
    LoopT *CurLoop = static_cast<LoopT *>(this);
    PreOrderLoops.push_back(CurLoop);
    getInnerLoopsInPreorder(*CurLoop, PreOrderLoops);
    return PreOrderLoops;
  }
 
  //===--------------------------------------------------------------------===//
  // APIs for updating loop information after changing the CFG
  //
 
  /// This method is used by other analyses to update loop information.
  /// NewBB is set to be a new member of the current loop.
  /// Because of this, it is added as a member of all parent loops, and is added
  /// to the specified LoopInfo object as being in the current basic block.  It
  /// is not valid to replace the loop header with this method.
  void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI);
 
  /// Add the specified loop to be a child of this loop.
  /// This updates the loop depth of the new child.
  void addChildLoop(LoopT *NewChild) {
    assert(!isInvalid() && "Loop not in a valid state!");
    assert(!NewChild->ParentLoop && "NewChild already has a parent!");
    NewChild->ParentLoop = static_cast<LoopT *>(this);
    SubLoops.push_back(NewChild);
  }
 
  /// This removes the specified child from being a subloop of this loop. The
  /// loop is not deleted, as it will presumably be inserted into another loop.
  LoopT *removeChildLoop(iterator I) {
    assert(!isInvalid() && "Loop not in a valid state!");
    assert(I != SubLoops.end() && "Cannot remove end iterator!");
    LoopT *Child = *I;
    assert(Child->ParentLoop == this && "Child is not a child of this loop!");
    SubLoops.erase(SubLoops.begin() + (I - begin()));
    Child->ParentLoop = nullptr;
    return Child;
  }
 
  /// This removes the specified child from being a subloop of this loop. The
  /// loop is not deleted, as it will presumably be inserted into another loop.
  LoopT *removeChildLoop(LoopT *Child) {
    return removeChildLoop(llvm::find(*this, Child));
  }
 
  /// This adds a basic block directly to the basic block list.
  /// This should only be used by transformations that create new loops.  Other
  /// transformations should use addBasicBlockToLoop.
  void addBlockEntry(BlockT *BB) {
    assert(!isInvalid() && "Loop not in a valid state!");
    // A borrowed slice or a full private allocation grows into fresh private
    // storage before appending.
    if (BlockCapacity == BorrowedCapacity || BlockLen == BlockCapacity)
      LI->reallocBlocks(*static_cast<LoopT *>(this),
                        std::max(2 * BlockLen, 4u));
    BlockData[BlockLen++] = BB;
  }
 
  /// interface to do reserve() for Blocks
  void reserveBlocks(unsigned Size) {
    assert(!isInvalid() && "Loop not in a valid state!");
    if (BlockCapacity < Size)
      LI->reallocBlocks(*static_cast<LoopT *>(this), Size);
  }
 
  /// This method is used to move BB (which must be part of this loop) to be the
  /// loop header of the loop (the block that dominates all others).
  void moveToHeader(BlockT *BB) {
    assert(!isInvalid() && "Loop not in a valid state!");
    if (BlockData[0] == BB)
      return;
    LI->materializeBlocks(*static_cast<LoopT *>(this));
    for (unsigned i = 0;; ++i) {
      assert(i != BlockLen && "Loop does not contain BB!");
      if (BlockData[i] == BB) {
        BlockData[i] = BlockData[0];
        BlockData[0] = BB;
        return;
      }
    }
  }
 
  /// This removes the specified basic block from the current loop, updating the
  /// Blocks as appropriate. This does not update the mapping in the LoopInfo
  /// class.
  void removeBlockFromLoop(BlockT *BB) {
    assert(!isInvalid() && "Loop not in a valid state!");
    LI->materializeBlocks(*static_cast<LoopT *>(this));
    MutableArrayRef<BlockT *> Blocks(BlockData, BlockLen);
    auto *I = llvm::find(Blocks, BB);
    assert(I != Blocks.end() && "N is not in this list!");
    std::move(I + 1, Blocks.end(), I);
    --BlockLen;
  }
 
  /// Verify loop structure
  void verifyLoop() const;
 
  /// Verify loop structure of this loop and all nested loops.
  void verifyLoopNest(DenseSet<const LoopT *> *Loops) const;
 
  /// Returns true if the loop is annotated parallel.
  ///
  /// Derived classes can override this method using static template
  /// polymorphism.
  bool isAnnotatedParallel() const { return false; }
 
  /// Print loop with all the BBs inside it.
  void print(raw_ostream &OS, bool Verbose = false, bool PrintNested = true,
             unsigned Depth = 0) const;
 
protected:
  friend class LoopInfoBase<BlockT, LoopT>;
 
  /// This creates an empty loop.
  LoopBase() : ParentLoop(nullptr) {}
 
  // ScalarEvolution and others key results off `Loop` pointers, so an address
  // must never come to name a different loop. Passes call LoopInfo::destroy()
  // rather than `delete`, retaining the memory until the owning LoopInfo dies;
  // the non-public destructor enforces that.
  ~LoopBase() {
    for (auto *SubLoop : SubLoops)
      SubLoop->~LoopT();
 
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
    IsInvalid = true;
#endif
    clear();
  }
 
  void clear() {
    SubLoops.clear();
    // The block storage is reclaimed by the owning LoopInfo.
    BlockData = nullptr;
    BlockLen = 0;
    BlockCapacity = 0;
    ParentLoop = nullptr;
  }
};
 
template <class BlockT, class LoopT>
raw_ostream &operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
  Loop.print(OS);
  return OS;
}
 
//===----------------------------------------------------------------------===//
/// This class builds and contains all of the top-level loop
/// structures in the specified function.
///
 
template <class BlockT, class LoopT> class LoopInfoBase {
  static_assert(GraphHasNodeNumbers<const BlockT *>,
                "LoopInfo requires GraphTraits<BlockT *>::getNumber (see "
                "GraphHasNodeNumbers)");
 
  // Mapping of each block, indexed by its number, to the innermost loop it
  // occurs in (or null).
  SmallVector<LoopT *> BBMap;
 
  using ParentT = decltype(std::declval<BlockT *>()->getParent());
  ParentT ParentPtr = nullptr;
  unsigned BlockNumberEpoch;
 
  std::vector<LoopT *> TopLevelLoops;
 
  // Shared reverse postorder layout of the in-loop blocks. Each initial loop is
  // a slice of this array, subloop slices nested inside their parent's.
  std::unique_ptr<BlockT *[]> BlockLayout;
 
  BumpPtrAllocator LoopAllocator;
 
  friend class LoopBase<BlockT, LoopT>;
  friend class LoopInfo;
 
  void operator=(const LoopInfoBase &) = delete;
  LoopInfoBase(const LoopInfoBase &) = delete;
 
public:
  LoopInfoBase() = default;
  ~LoopInfoBase() { releaseMemory(); }
 
  LoopInfoBase(LoopInfoBase &&Arg)
      : BBMap(std::move(Arg.BBMap)),
        TopLevelLoops(std::move(Arg.TopLevelLoops)),
        BlockLayout(std::move(Arg.BlockLayout)),
        LoopAllocator(std::move(Arg.LoopAllocator)) {
    ParentPtr = Arg.ParentPtr;
    BlockNumberEpoch = Arg.BlockNumberEpoch;
    resetLoopInfoOwners();
    // We have to clear the arguments top level loops as we've taken ownership.
    Arg.TopLevelLoops.clear();
  }
  LoopInfoBase &operator=(LoopInfoBase &&RHS) {
    BBMap = std::move(RHS.BBMap);
    ParentPtr = RHS.ParentPtr;
    BlockNumberEpoch = RHS.BlockNumberEpoch;
 
    for (auto *L : TopLevelLoops)
      L->~LoopT();
 
    TopLevelLoops = std::move(RHS.TopLevelLoops);
    BlockLayout = std::move(RHS.BlockLayout);
    LoopAllocator = std::move(RHS.LoopAllocator);
    resetLoopInfoOwners();
    RHS.TopLevelLoops.clear();
    return *this;
  }
 
  void releaseMemory() {
    BBMap.clear();
 
    for (auto *L : TopLevelLoops)
      L->~LoopT();
    TopLevelLoops.clear();
    BlockLayout.reset();
    LoopAllocator.Reset();
  }
 
  LoopT *AllocateLoop() {
    LoopT *Storage = LoopAllocator.Allocate<LoopT>();
    LoopT *L = new (Storage) LoopT();
    L->LI = this;
    return L;
  }
 
  /// iterator/begin/end - The interface to the top-level loops in the current
  /// function.
  ///
  using iterator = typename std::vector<LoopT *>::const_iterator;
  using reverse_iterator =
      typename std::vector<LoopT *>::const_reverse_iterator;
  iterator begin() const { return TopLevelLoops.begin(); }
  iterator end() const { return TopLevelLoops.end(); }
  reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
  reverse_iterator rend() const { return TopLevelLoops.rend(); }
  bool empty() const { return TopLevelLoops.empty(); }
 
  /// Return all of the loops in the function in preorder across the loop
  /// nests, with siblings in forward program order.
  ///
  /// Note that because loops form a forest of trees, preorder is equivalent to
  /// reverse postorder.
  SmallVector<LoopT *, 4> getLoopsInPreorder() const;
 
  /// Return all of the loops in the function in preorder across the loop
  /// nests, with siblings in *reverse* program order.
  ///
  /// Note that because loops form a forest of trees, preorder is equivalent to
  /// reverse postorder.
  ///
  /// Also note that this is *not* a reverse preorder. Only the siblings are in
  /// reverse program order.
  SmallVector<LoopT *, 4> getLoopsInReverseSiblingPreorder() const;
 
private:
  // Point every loop's owning-LoopInfo back-pointer at this object. Called
  // after a move.
  void resetLoopInfoOwners() {
    SmallVector<LoopT *, 8> Worklist(TopLevelLoops.begin(),
                                     TopLevelLoops.end());
    while (!Worklist.empty()) {
      LoopT *L = Worklist.pop_back_val();
      L->LI = this;
      Worklist.append(L->begin(), L->end());
    }
  }
 
  /// Verify that used block numbers are still valid.
  void
  verifyBlockNumberEpoch(const std::remove_pointer_t<ParentT> *BBParent) const {
    assert(ParentPtr == BBParent &&
           "loop info queried with block of other function");
    assert(BlockNumberEpoch ==
               GraphTraits<ParentT>::getNumberEpoch(ParentPtr) &&
           "loop info used with outdated block numbers");
  }
 
  // Look up BB's innermost loop in the block-to-loop map; BB must belong to
  // this function.
  LoopT *lookupLoopFor(const BlockT *BB) const {
    unsigned Number = GraphTraits<const BlockT *>::getNumber(BB);
    return Number < BBMap.size() ? BBMap[Number] : nullptr;
  }
 
  /// Maps a header to the loop recompute() refills for it, if any.
  using ReuseLoopT = function_ref<LoopT *(BlockT *)>;
 
  /// AllocateLoop for analyze(): stash \p Header (see pendingHeader).
  /// getHeader() only works once the layout carve has replaced the stash with
  /// the loop's block list. \p ReuseLoop, if specified, returns an existing
  /// loop rather than a fresh one for LoopInfoBase::recompute.
  LoopT *allocateLoop(BlockT *Header, ReuseLoopT ReuseLoop) {
    LoopT *L = ReuseLoop ? ReuseLoop(Header) : nullptr;
    if (!L)
      L = AllocateLoop();
    L->PendingHeader = Header;
    return L;
  }
 
  void analyzeImpl(
      ParentT F,
      function_ref<const DominatorTreeBase<BlockT, false> &()> GetDomTree,
      ReuseLoopT ReuseLoop);
  void analyzeImpl(const DominatorTreeBase<BlockT, false> &DomTree,
                   ReuseLoopT ReuseLoop);
 
  /// The header of a loop under construction, stashed until the layout carve
  /// builds the block list.
  static BlockT *pendingHeader(const LoopT *L) { return L->PendingHeader; }
 
  /// True if \p L borrows its block list from BlockLayout.
  static bool hasBorrowedBlocks(const LoopT &L) {
    return L.BlockCapacity == LoopT::BorrowedCapacity;
  }
 
  /// Replace \p L's block list with a private allocation of NewCapacity
  /// slots. The old storage is abandoned in place so slices sharing it stay
  /// intact; it is reclaimed when this LoopInfo is cleared.
  void reallocBlocks(LoopT &L, unsigned NewCapacity) {
    assert(NewCapacity >= L.BlockLen && "capacity below size");
    BlockT **New = LoopAllocator.Allocate<BlockT *>(NewCapacity);
    llvm::copy(L.getBlocks(), New);
    L.BlockData = New;
    L.BlockCapacity = NewCapacity;
  }
 
  /// Copy \p L's borrowed block list into private storage before a mutation.
  void materializeBlocks(LoopT &L) {
    if (hasBorrowedBlocks(L))
      reallocBlocks(L, L.BlockLen);
  }
 
public:
  /// Return the inner most loop that BB lives in. If a basic block is in no
  /// loop (for example the entry node), null is returned.
  LoopT *getLoopFor(const BlockT *BB) const {
    verifyBlockNumberEpoch(BB->getParent());
    return lookupLoopFor(BB);
  }
 
  /// Same as getLoopFor.
  const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); }
 
  /// Return the loop nesting level of the specified block. A depth of 0 means
  /// the block is not inside any loop.
  unsigned getLoopDepth(const BlockT *BB) const {
    const LoopT *L = getLoopFor(BB);
    return L ? L->getLoopDepth() : 0;
  }
 
  /// Edge type.
  using Edge = std::pair<BlockT *, BlockT *>;
 
  /// Return true if \p L does not have any exit blocks.
  bool hasNoExitBlocks(const LoopT &L) const;
 
  /// Return all pairs of (_inside_block_,_outside_block_).
  void getExitEdges(const LoopT &L, SmallVectorImpl<Edge> &ExitEdges) const;
 
  /// Return the unique exit block for the latch of \p L, or null if there are
  /// multiple different exit blocks or the latch is not exiting.
  BlockT *getUniqueLatchExitBlock(const LoopT &L) const;
 
  /// Remove every block satisfying \p Pred from \p L's block list, preserving
  /// the order of the remaining blocks. Only \p L itself is updated, not its
  /// ancestors or descendants, and not the block-to-loop mapping.
  template <typename PredicateT>
  void removeBlocksIf(LoopT &L, PredicateT Pred) {
    materializeBlocks(L);
    L.BlockLen = llvm::remove_if(
                     MutableArrayRef<BlockT *>(L.BlockData, L.BlockLen), Pred) -
                 L.BlockData;
  }
 
  /// Detach and return the children of \p Parent (the top-level loops if
  /// \p Parent is null) that satisfy \p Pred, clearing their parent pointers.
  /// Both the remaining and the returned children keep their relative order.
  template <typename PredicateT>
  SmallVector<LoopT *, 4> takeChildrenIf(LoopT *Parent, PredicateT Pred) {
    std::vector<LoopT *> &List = Parent ? Parent->SubLoops : TopLevelLoops;
    SmallVector<LoopT *, 4> Taken;
    llvm::erase_if(List, [&](LoopT *Child) {
      if (!Pred(Child))
        return false;
      Child->ParentLoop = nullptr;
      Taken.push_back(Child);
      return true;
    });
    return Taken;
  }
 
  /// \brief Find the innermost loop containing both given loops.
  ///
  /// \returns the innermost loop containing both \p A and \p B
  ///          or nullptr if there is no such loop.
  LoopT *getSmallestCommonLoop(LoopT *A, LoopT *B) const;
  /// \brief Find the innermost loop containing both given blocks.
  ///
  /// \returns the innermost loop containing both \p A and \p B
  ///          or nullptr if there is no such loop.
  LoopT *getSmallestCommonLoop(BlockT *A, BlockT *B) const;
 
  // True if the block is a loop header node
  bool isLoopHeader(const BlockT *BB) const {
    const LoopT *L = getLoopFor(BB);
    return L && L->getHeader() == BB;
  }
 
  /// Return the top-level loops.
  const std::vector<LoopT *> &getTopLevelLoops() const { return TopLevelLoops; }
 
  /// This removes the specified top-level loop from this loop info object.
  /// The loop is not deleted, as it will presumably be inserted into
  /// another loop.
  LoopT *removeLoop(iterator I) {
    assert(I != end() && "Cannot remove end iterator!");
    LoopT *L = *I;
    assert(L->isOutermost() && "Not a top-level loop!");
    TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));
    return L;
  }
 
  /// Change the top-level loop that contains BB to the specified loop.
  /// This should be used by transformations that restructure the loop hierarchy
  /// tree.
  void changeLoopFor(const BlockT *BB, LoopT *L) {
    verifyBlockNumberEpoch(BB->getParent());
    unsigned Number = GraphTraits<const BlockT *>::getNumber(BB);
    if (Number >= BBMap.size()) {
      unsigned Max =
          GraphTraits<decltype(BB->getParent())>::getMaxNumber(BB->getParent());
      assert(Number < Max);
      BBMap.resize(Max);
    }
    BBMap[Number] = L;
  }
 
  /// Replace a loop among its siblings (a parent loop's child list or the
  /// top-level list) with a new loop.
  void replaceLoop(LoopT *Old, LoopT *New) {
    assert(!New->ParentLoop && "New loop already has a parent!");
    LoopT *Parent = Old->ParentLoop;
    auto &Siblings = Parent ? Parent->SubLoops : TopLevelLoops;
    auto I = find(Siblings, Old);
    assert(I != Siblings.end() && "Old loop is not among its siblings!");
    *I = New;
    Old->ParentLoop = nullptr;
    New->ParentLoop = Parent;
  }
 
  /// This adds the specified loop to the collection of top-level loops.
  void addTopLevelLoop(LoopT *New) {
    assert(New->isOutermost() && "Loop already in subloop!");
    TopLevelLoops.push_back(New);
  }
 
  /// This method completely removes BB from all data structures,
  /// including all of the Loop objects it is nested in and our mapping from
  /// BasicBlocks to loops.
  void removeBlock(BlockT *BB) {
    verifyBlockNumberEpoch(BB->getParent());
    unsigned Number = GraphTraits<BlockT *>::getNumber(BB);
    if (Number >= BBMap.size())
      return;
 
    for (LoopT *L = BBMap[Number]; L; L = L->getParentLoop())
      L->removeBlockFromLoop(BB);
    BBMap[Number] = nullptr;
  }
 
  // Internals
 
  static bool isNotAlreadyContainedIn(const LoopT *SubLoop,
                                      const LoopT *ParentLoop) {
    if (!SubLoop)
      return true;
    if (SubLoop == ParentLoop)
      return false;
    return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
  }
 
  /// Create the loop forest for a function. A dominator tree is needed only for
  /// an irreducible CFG, where dominance reduces a loop that an edge re-enters
  /// to the natural loop of its header's backedges.
  ///@{
  /// Build a dominator tree if one is needed.
  void analyze(ParentT F);
  /// Call \p GetDomTree if a dominator tree is needed.
  void
  analyze(ParentT F,
          function_ref<const DominatorTreeBase<BlockT, false> &()> GetDomTree);
  /// Analyze the function \p DomTree describes.
  void analyze(const DominatorTreeBase<BlockT, false> &DomTree);
  ///@}
 
  /// Rebuild the loop forest from the CFG, refilling the existing loop object
  /// of every block that still heads a loop, so that analyses keyed on loop
  /// pointers stay valid for the survivors.
  ///
  /// Returns the loops whose header no longer heads one, each with its former
  /// header, in a deterministic order. They are left empty and unlinked; the
  /// caller must run its deletion callbacks on them and then destroy() them.
  ///
  /// Every loop's header must still belong to the function.
  SmallVector<std::pair<LoopT *, BlockT *>, 4>
  recompute(const DominatorTreeBase<BlockT, false> &DomTree);
 
  // Debugging
  void print(raw_ostream &OS) const;
 
  void verify() const;
 
  /// Destroy a loop that has been removed from the `LoopInfo` nest.
  ///
  /// This runs the destructor of the loop object making it invalid to
  /// reference afterward. The memory is retained so that the *pointer* to the
  /// loop remains valid.
  ///
  /// The caller is responsible for removing this loop from the loop nest and
  /// otherwise disconnecting it from the broader `LoopInfo` data structures.
  /// Callers that don't naturally handle this themselves should probably call
  /// `erase' instead.
  void destroy(LoopT *L) {
    L->~LoopT();
 
    // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons
    // \c L, but the pointer remains valid for non-dereferencing uses.
    LoopAllocator.Deallocate(L);
  }
};
 
} // namespace llvm
 
#endif // LLVM_SUPPORT_GENERICLOOPINFO_H