llvm/llvm/include/llvm/Support/GenericLoopInfoImpl.h

//===- GenericLoopInfoImp.h - Generic Loop Info Implementation --*- 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 fle contains the implementation of GenericLoopInfo. It should only be
// included in files that explicitly instantiate a GenericLoopInfo.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_SUPPORT_GENERICLOOPINFOIMPL_H
#define LLVM_SUPPORT_GENERICLOOPINFOIMPL_H

#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/Support/GenericLoopInfo.h"

namespace llvm {

//===----------------------------------------------------------------------===//
// APIs for simple analysis of the loop. See header notes.

/// getExitingBlocks - 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.
///
template <class BlockT, class LoopT>
void LoopBase<BlockT, LoopT>::getExitingBlocks(
    SmallVectorImpl<BlockT *> &ExitingBlocks) const { … }

/// getExitingBlock - If getExitingBlocks would return exactly one block,
/// return that block. Otherwise return null.
template <class BlockT, class LoopT>
BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const { … }

/// getExitBlocks - Return all of the successor blocks of this loop.  These
/// are the blocks _outside of the current loop_ which are branched to.
///
template <class BlockT, class LoopT>
void LoopBase<BlockT, LoopT>::getExitBlocks(
    SmallVectorImpl<BlockT *> &ExitBlocks) const { … }

/// getExitBlock - If getExitBlocks would return exactly one block,
/// return that block. Otherwise return null.
template <class BlockT, class LoopT>
std::pair<BlockT *, bool> getExitBlockHelper(const LoopBase<BlockT, LoopT> *L,
                                             bool Unique) { … }

template <class BlockT, class LoopT>
bool LoopBase<BlockT, LoopT>::hasNoExitBlocks() const { … }

/// getExitBlock - If getExitBlocks would return exactly one block,
/// return that block. Otherwise return null.
template <class BlockT, class LoopT>
BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const { … }

template <class BlockT, class LoopT>
bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const { … }

// Helper function to get unique loop exits. Pred is a predicate pointing to
// BasicBlocks in a loop which should be considered to find loop exits.
template <class BlockT, class LoopT, typename PredicateT>
void getUniqueExitBlocksHelper(const LoopT *L,
                               SmallVectorImpl<BlockT *> &ExitBlocks,
                               PredicateT Pred) { … }

template <class BlockT, class LoopT>
void LoopBase<BlockT, LoopT>::getUniqueExitBlocks(
    SmallVectorImpl<BlockT *> &ExitBlocks) const { … }

template <class BlockT, class LoopT>
void LoopBase<BlockT, LoopT>::getUniqueNonLatchExitBlocks(
    SmallVectorImpl<BlockT *> &ExitBlocks) const { … }

template <class BlockT, class LoopT>
BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const { … }

/// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
template <class BlockT, class LoopT>
void LoopBase<BlockT, LoopT>::getExitEdges(
    SmallVectorImpl<Edge> &ExitEdges) const { … }

namespace detail {
has_hoist_check;

detect_has_hoist_check;

/// SFINAE functions that dispatch to the isLegalToHoistInto member function or
/// return false, if it doesn't exist.
template <class BlockT> bool isLegalToHoistInto(BlockT *Block) { … }
} // namespace detail

/// getLoopPreheader - 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 and it is legal to hoist instructions into the
/// predecessor. 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.
///
template <class BlockT, class LoopT>
BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const { … }

/// getLoopPredecessor - 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.
///
template <class BlockT, class LoopT>
BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const { … }

/// getLoopLatch - 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.
template <class BlockT, class LoopT>
BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const { … }

//===----------------------------------------------------------------------===//
// APIs for updating loop information after changing the CFG
//

/// addBasicBlockToLoop - 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.
///
template <class BlockT, class LoopT>
void LoopBase<BlockT, LoopT>::addBasicBlockToLoop(
    BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) { … }

/// replaceChildLoopWith - This is used when splitting loops up.  It replaces
/// the OldChild entry in our children list with NewChild, and updates the
/// parent pointer of OldChild to be null and the NewChild to be this loop.
/// This updates the loop depth of the new child.
template <class BlockT, class LoopT>
void LoopBase<BlockT, LoopT>::replaceChildLoopWith(LoopT *OldChild,
                                                   LoopT *NewChild) { … }

/// verifyLoop - Verify loop structure
template <class BlockT, class LoopT>
void LoopBase<BlockT, LoopT>::verifyLoop() const { … }

/// verifyLoop - Verify loop structure of this loop and all nested loops.
template <class BlockT, class LoopT>
void LoopBase<BlockT, LoopT>::verifyLoopNest(
    DenseSet<const LoopT *> *Loops) const { … }

template <class BlockT, class LoopT>
void LoopBase<BlockT, LoopT>::print(raw_ostream &OS, bool Verbose,
                                    bool PrintNested, unsigned Depth) const { … }

//===----------------------------------------------------------------------===//
/// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
/// result does / not depend on use list (block predecessor) order.
///

/// Discover a subloop with the specified backedges such that: All blocks within
/// this loop are mapped to this loop or a subloop. And all subloops within this
/// loop have their parent loop set to this loop or a subloop.
template <class BlockT, class LoopT>
static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges,
                                  LoopInfoBase<BlockT, LoopT> *LI,
                                  const DomTreeBase<BlockT> &DomTree) { … }

/// Populate all loop data in a stable order during a single forward DFS.
template <class BlockT, class LoopT> class PopulateLoopsDFS { … };

/// Top-level driver for the forward DFS within the loop.
template <class BlockT, class LoopT>
void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) { … }

/// Add a single Block to its ancestor loops in PostOrder. If the block is a
/// subloop header, add the subloop to its parent in PostOrder, then reverse the
/// Block and Subloop vectors of the now complete subloop to achieve RPO.
template <class BlockT, class LoopT>
void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) { … }

/// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
/// interleaved with backward CFG traversals within each subloop
/// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
/// this part of the algorithm is linear in the number of CFG edges. Subloop and
/// Block vectors are then populated during a single forward CFG traversal
/// (PopulateLoopDFS).
///
/// During the two CFG traversals each block is seen three times:
/// 1) Discovered and mapped by a reverse CFG traversal.
/// 2) Visited during a forward DFS CFG traversal.
/// 3) Reverse-inserted in the loop in postorder following forward DFS.
///
/// The Block vectors are inclusive, so step 3 requires loop-depth number of
/// insertions per block.
template <class BlockT, class LoopT>
void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) { … }

template <class BlockT, class LoopT>
SmallVector<LoopT *, 4>
LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() const { … }

template <class BlockT, class LoopT>
SmallVector<LoopT *, 4>
LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() const { … }

// Debugging
template <class BlockT, class LoopT>
void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const { … }

template <typename T>
bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) { … }

template <class BlockT, class LoopT>
void addInnerLoopsToHeadersMap(DenseMap<BlockT *, const LoopT *> &LoopHeaders,
                               const LoopInfoBase<BlockT, LoopT> &LI,
                               const LoopT &L) { … }

#ifndef NDEBUG
template <class BlockT, class LoopT>
static void compareLoops(const LoopT *L, const LoopT *OtherL,
                         DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) {
  BlockT *H = L->getHeader();
  BlockT *OtherH = OtherL->getHeader();
  assert(H == OtherH &&
         "Mismatched headers even though found in the same map entry!");

  assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
         "Mismatched loop depth!");
  const LoopT *ParentL = L, *OtherParentL = OtherL;
  do {
    assert(ParentL->getHeader() == OtherParentL->getHeader() &&
           "Mismatched parent loop headers!");
    ParentL = ParentL->getParentLoop();
    OtherParentL = OtherParentL->getParentLoop();
  } while (ParentL);

  for (const LoopT *SubL : *L) {
    BlockT *SubH = SubL->getHeader();
    const LoopT *OtherSubL = OtherLoopHeaders.lookup(SubH);
    assert(OtherSubL && "Inner loop is missing in computed loop info!");
    OtherLoopHeaders.erase(SubH);
    compareLoops(SubL, OtherSubL, OtherLoopHeaders);
  }

  std::vector<BlockT *> BBs = L->getBlocks();
  std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
  assert(compareVectors(BBs, OtherBBs) &&
         "Mismatched basic blocks in the loops!");

  const SmallPtrSetImpl<const BlockT *> &BlocksSet = L->getBlocksSet();
  const SmallPtrSetImpl<const BlockT *> &OtherBlocksSet =
      OtherL->getBlocksSet();
  assert(BlocksSet.size() == OtherBlocksSet.size() &&
         llvm::set_is_subset(BlocksSet, OtherBlocksSet) &&
         "Mismatched basic blocks in BlocksSets!");
}
#endif

template <class BlockT, class LoopT>
void LoopInfoBase<BlockT, LoopT>::verify(
    const DomTreeBase<BlockT> &DomTree) const { … }

} // namespace llvm

#endif // LLVM_SUPPORT_GENERICLOOPINFOIMPL_H