106c3fb27SDimitry Andric //===- GenericLoopInfoImp.h - Generic Loop Info Implementation --*- 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 fle contains the implementation of GenericLoopInfo. It should only be
1006c3fb27SDimitry Andric // included in files that explicitly instantiate a GenericLoopInfo.
1106c3fb27SDimitry Andric //
1206c3fb27SDimitry Andric //===----------------------------------------------------------------------===//
1306c3fb27SDimitry Andric
1406c3fb27SDimitry Andric #ifndef LLVM_SUPPORT_GENERICLOOPINFOIMPL_H
1506c3fb27SDimitry Andric #define LLVM_SUPPORT_GENERICLOOPINFOIMPL_H
1606c3fb27SDimitry Andric
1706c3fb27SDimitry Andric #include "llvm/ADT/DepthFirstIterator.h"
1806c3fb27SDimitry Andric #include "llvm/ADT/PostOrderIterator.h"
1906c3fb27SDimitry Andric #include "llvm/ADT/STLExtras.h"
2006c3fb27SDimitry Andric #include "llvm/ADT/SetOperations.h"
2106c3fb27SDimitry Andric #include "llvm/Support/GenericLoopInfo.h"
2206c3fb27SDimitry Andric
2306c3fb27SDimitry Andric namespace llvm {
2406c3fb27SDimitry Andric
2506c3fb27SDimitry Andric //===----------------------------------------------------------------------===//
2606c3fb27SDimitry Andric // APIs for simple analysis of the loop. See header notes.
2706c3fb27SDimitry Andric
2806c3fb27SDimitry Andric /// getExitingBlocks - Return all blocks inside the loop that have successors
2906c3fb27SDimitry Andric /// outside of the loop. These are the blocks _inside of the current loop_
3006c3fb27SDimitry Andric /// which branch out. The returned list is always unique.
3106c3fb27SDimitry Andric ///
3206c3fb27SDimitry Andric template <class BlockT, class LoopT>
getExitingBlocks(SmallVectorImpl<BlockT * > & ExitingBlocks)3306c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::getExitingBlocks(
3406c3fb27SDimitry Andric SmallVectorImpl<BlockT *> &ExitingBlocks) const {
3506c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!");
3606c3fb27SDimitry Andric for (const auto BB : blocks())
3706c3fb27SDimitry Andric for (auto *Succ : children<BlockT *>(BB))
3806c3fb27SDimitry Andric if (!contains(Succ)) {
3906c3fb27SDimitry Andric // Not in current loop? It must be an exit block.
4006c3fb27SDimitry Andric ExitingBlocks.push_back(BB);
4106c3fb27SDimitry Andric break;
4206c3fb27SDimitry Andric }
4306c3fb27SDimitry Andric }
4406c3fb27SDimitry Andric
4506c3fb27SDimitry Andric /// getExitingBlock - If getExitingBlocks would return exactly one block,
4606c3fb27SDimitry Andric /// return that block. Otherwise return null.
4706c3fb27SDimitry Andric template <class BlockT, class LoopT>
getExitingBlock()4806c3fb27SDimitry Andric BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
4906c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!");
5006c3fb27SDimitry Andric auto notInLoop = [&](BlockT *BB) { return !contains(BB); };
5106c3fb27SDimitry Andric auto isExitBlock = [&](BlockT *BB, bool AllowRepeats) -> BlockT * {
5206c3fb27SDimitry Andric assert(!AllowRepeats && "Unexpected parameter value.");
5306c3fb27SDimitry Andric // Child not in current loop? It must be an exit block.
5406c3fb27SDimitry Andric return any_of(children<BlockT *>(BB), notInLoop) ? BB : nullptr;
5506c3fb27SDimitry Andric };
5606c3fb27SDimitry Andric
5706c3fb27SDimitry Andric return find_singleton<BlockT>(blocks(), isExitBlock);
5806c3fb27SDimitry Andric }
5906c3fb27SDimitry Andric
6006c3fb27SDimitry Andric /// getExitBlocks - Return all of the successor blocks of this loop. These
6106c3fb27SDimitry Andric /// are the blocks _outside of the current loop_ which are branched to.
6206c3fb27SDimitry Andric ///
6306c3fb27SDimitry Andric template <class BlockT, class LoopT>
getExitBlocks(SmallVectorImpl<BlockT * > & ExitBlocks)6406c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::getExitBlocks(
6506c3fb27SDimitry Andric SmallVectorImpl<BlockT *> &ExitBlocks) const {
6606c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!");
6706c3fb27SDimitry Andric for (const auto BB : blocks())
6806c3fb27SDimitry Andric for (auto *Succ : children<BlockT *>(BB))
6906c3fb27SDimitry Andric if (!contains(Succ))
7006c3fb27SDimitry Andric // Not in current loop? It must be an exit block.
7106c3fb27SDimitry Andric ExitBlocks.push_back(Succ);
7206c3fb27SDimitry Andric }
7306c3fb27SDimitry Andric
7406c3fb27SDimitry Andric /// getExitBlock - If getExitBlocks would return exactly one block,
7506c3fb27SDimitry Andric /// return that block. Otherwise return null.
7606c3fb27SDimitry Andric template <class BlockT, class LoopT>
getExitBlockHelper(const LoopBase<BlockT,LoopT> * L,bool Unique)7706c3fb27SDimitry Andric std::pair<BlockT *, bool> getExitBlockHelper(const LoopBase<BlockT, LoopT> *L,
7806c3fb27SDimitry Andric bool Unique) {
7906c3fb27SDimitry Andric assert(!L->isInvalid() && "Loop not in a valid state!");
8006c3fb27SDimitry Andric auto notInLoop = [&](BlockT *BB,
8106c3fb27SDimitry Andric bool AllowRepeats) -> std::pair<BlockT *, bool> {
8206c3fb27SDimitry Andric assert(AllowRepeats == Unique && "Unexpected parameter value.");
8306c3fb27SDimitry Andric return {!L->contains(BB) ? BB : nullptr, false};
8406c3fb27SDimitry Andric };
8506c3fb27SDimitry Andric auto singleExitBlock = [&](BlockT *BB,
8606c3fb27SDimitry Andric bool AllowRepeats) -> std::pair<BlockT *, bool> {
8706c3fb27SDimitry Andric assert(AllowRepeats == Unique && "Unexpected parameter value.");
8806c3fb27SDimitry Andric return find_singleton_nested<BlockT>(children<BlockT *>(BB), notInLoop,
8906c3fb27SDimitry Andric AllowRepeats);
9006c3fb27SDimitry Andric };
9106c3fb27SDimitry Andric return find_singleton_nested<BlockT>(L->blocks(), singleExitBlock, Unique);
9206c3fb27SDimitry Andric }
9306c3fb27SDimitry Andric
9406c3fb27SDimitry Andric template <class BlockT, class LoopT>
hasNoExitBlocks()9506c3fb27SDimitry Andric bool LoopBase<BlockT, LoopT>::hasNoExitBlocks() const {
9606c3fb27SDimitry Andric auto RC = getExitBlockHelper(this, false);
9706c3fb27SDimitry Andric if (RC.second)
9806c3fb27SDimitry Andric // found multiple exit blocks
9906c3fb27SDimitry Andric return false;
10006c3fb27SDimitry Andric // return true if there is no exit block
10106c3fb27SDimitry Andric return !RC.first;
10206c3fb27SDimitry Andric }
10306c3fb27SDimitry Andric
10406c3fb27SDimitry Andric /// getExitBlock - If getExitBlocks would return exactly one block,
10506c3fb27SDimitry Andric /// return that block. Otherwise return null.
10606c3fb27SDimitry Andric template <class BlockT, class LoopT>
getExitBlock()10706c3fb27SDimitry Andric BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
10806c3fb27SDimitry Andric return getExitBlockHelper(this, false).first;
10906c3fb27SDimitry Andric }
11006c3fb27SDimitry Andric
11106c3fb27SDimitry Andric template <class BlockT, class LoopT>
hasDedicatedExits()11206c3fb27SDimitry Andric bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
11306c3fb27SDimitry Andric // Each predecessor of each exit block of a normal loop is contained
11406c3fb27SDimitry Andric // within the loop.
11506c3fb27SDimitry Andric SmallVector<BlockT *, 4> UniqueExitBlocks;
11606c3fb27SDimitry Andric getUniqueExitBlocks(UniqueExitBlocks);
11706c3fb27SDimitry Andric for (BlockT *EB : UniqueExitBlocks)
118*7a6dacacSDimitry Andric for (BlockT *Predecessor : inverse_children<BlockT *>(EB))
11906c3fb27SDimitry Andric if (!contains(Predecessor))
12006c3fb27SDimitry Andric return false;
12106c3fb27SDimitry Andric // All the requirements are met.
12206c3fb27SDimitry Andric return true;
12306c3fb27SDimitry Andric }
12406c3fb27SDimitry Andric
12506c3fb27SDimitry Andric // Helper function to get unique loop exits. Pred is a predicate pointing to
12606c3fb27SDimitry Andric // BasicBlocks in a loop which should be considered to find loop exits.
12706c3fb27SDimitry Andric template <class BlockT, class LoopT, typename PredicateT>
getUniqueExitBlocksHelper(const LoopT * L,SmallVectorImpl<BlockT * > & ExitBlocks,PredicateT Pred)12806c3fb27SDimitry Andric void getUniqueExitBlocksHelper(const LoopT *L,
12906c3fb27SDimitry Andric SmallVectorImpl<BlockT *> &ExitBlocks,
13006c3fb27SDimitry Andric PredicateT Pred) {
13106c3fb27SDimitry Andric assert(!L->isInvalid() && "Loop not in a valid state!");
13206c3fb27SDimitry Andric SmallPtrSet<BlockT *, 32> Visited;
13306c3fb27SDimitry Andric auto Filtered = make_filter_range(L->blocks(), Pred);
13406c3fb27SDimitry Andric for (BlockT *BB : Filtered)
13506c3fb27SDimitry Andric for (BlockT *Successor : children<BlockT *>(BB))
13606c3fb27SDimitry Andric if (!L->contains(Successor))
13706c3fb27SDimitry Andric if (Visited.insert(Successor).second)
13806c3fb27SDimitry Andric ExitBlocks.push_back(Successor);
13906c3fb27SDimitry Andric }
14006c3fb27SDimitry Andric
14106c3fb27SDimitry Andric template <class BlockT, class LoopT>
getUniqueExitBlocks(SmallVectorImpl<BlockT * > & ExitBlocks)14206c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::getUniqueExitBlocks(
14306c3fb27SDimitry Andric SmallVectorImpl<BlockT *> &ExitBlocks) const {
14406c3fb27SDimitry Andric getUniqueExitBlocksHelper(this, ExitBlocks,
14506c3fb27SDimitry Andric [](const BlockT *BB) { return true; });
14606c3fb27SDimitry Andric }
14706c3fb27SDimitry Andric
14806c3fb27SDimitry Andric template <class BlockT, class LoopT>
getUniqueNonLatchExitBlocks(SmallVectorImpl<BlockT * > & ExitBlocks)14906c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::getUniqueNonLatchExitBlocks(
15006c3fb27SDimitry Andric SmallVectorImpl<BlockT *> &ExitBlocks) const {
15106c3fb27SDimitry Andric const BlockT *Latch = getLoopLatch();
15206c3fb27SDimitry Andric assert(Latch && "Latch block must exists");
15306c3fb27SDimitry Andric getUniqueExitBlocksHelper(this, ExitBlocks,
15406c3fb27SDimitry Andric [Latch](const BlockT *BB) { return BB != Latch; });
15506c3fb27SDimitry Andric }
15606c3fb27SDimitry Andric
15706c3fb27SDimitry Andric template <class BlockT, class LoopT>
getUniqueExitBlock()15806c3fb27SDimitry Andric BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const {
15906c3fb27SDimitry Andric return getExitBlockHelper(this, true).first;
16006c3fb27SDimitry Andric }
16106c3fb27SDimitry Andric
16206c3fb27SDimitry Andric /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
16306c3fb27SDimitry Andric template <class BlockT, class LoopT>
getExitEdges(SmallVectorImpl<Edge> & ExitEdges)16406c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::getExitEdges(
16506c3fb27SDimitry Andric SmallVectorImpl<Edge> &ExitEdges) const {
16606c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!");
16706c3fb27SDimitry Andric for (const auto BB : blocks())
16806c3fb27SDimitry Andric for (auto *Succ : children<BlockT *>(BB))
16906c3fb27SDimitry Andric if (!contains(Succ))
17006c3fb27SDimitry Andric // Not in current loop? It must be an exit block.
17106c3fb27SDimitry Andric ExitEdges.emplace_back(BB, Succ);
17206c3fb27SDimitry Andric }
17306c3fb27SDimitry Andric
17406c3fb27SDimitry Andric namespace detail {
17506c3fb27SDimitry Andric template <class BlockT>
17606c3fb27SDimitry Andric using has_hoist_check = decltype(&BlockT::isLegalToHoistInto);
17706c3fb27SDimitry Andric
17806c3fb27SDimitry Andric template <class BlockT>
17906c3fb27SDimitry Andric using detect_has_hoist_check = llvm::is_detected<has_hoist_check, BlockT>;
18006c3fb27SDimitry Andric
18106c3fb27SDimitry Andric /// SFINAE functions that dispatch to the isLegalToHoistInto member function or
18206c3fb27SDimitry Andric /// return false, if it doesn't exist.
isLegalToHoistInto(BlockT * Block)18306c3fb27SDimitry Andric template <class BlockT> bool isLegalToHoistInto(BlockT *Block) {
18406c3fb27SDimitry Andric if constexpr (detect_has_hoist_check<BlockT>::value)
18506c3fb27SDimitry Andric return Block->isLegalToHoistInto();
18606c3fb27SDimitry Andric return false;
18706c3fb27SDimitry Andric }
18806c3fb27SDimitry Andric } // namespace detail
18906c3fb27SDimitry Andric
19006c3fb27SDimitry Andric /// getLoopPreheader - If there is a preheader for this loop, return it. A
19106c3fb27SDimitry Andric /// loop has a preheader if there is only one edge to the header of the loop
19206c3fb27SDimitry Andric /// from outside of the loop and it is legal to hoist instructions into the
19306c3fb27SDimitry Andric /// predecessor. If this is the case, the block branching to the header of the
19406c3fb27SDimitry Andric /// loop is the preheader node.
19506c3fb27SDimitry Andric ///
19606c3fb27SDimitry Andric /// This method returns null if there is no preheader for the loop.
19706c3fb27SDimitry Andric ///
19806c3fb27SDimitry Andric template <class BlockT, class LoopT>
getLoopPreheader()19906c3fb27SDimitry Andric BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
20006c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!");
20106c3fb27SDimitry Andric // Keep track of nodes outside the loop branching to the header...
20206c3fb27SDimitry Andric BlockT *Out = getLoopPredecessor();
20306c3fb27SDimitry Andric if (!Out)
20406c3fb27SDimitry Andric return nullptr;
20506c3fb27SDimitry Andric
20606c3fb27SDimitry Andric // Make sure we are allowed to hoist instructions into the predecessor.
20706c3fb27SDimitry Andric if (!detail::isLegalToHoistInto(Out))
20806c3fb27SDimitry Andric return nullptr;
20906c3fb27SDimitry Andric
21006c3fb27SDimitry Andric // Make sure there is only one exit out of the preheader.
211*7a6dacacSDimitry Andric if (llvm::size(llvm::children<BlockT *>(Out)) != 1)
21206c3fb27SDimitry Andric return nullptr; // Multiple exits from the block, must not be a preheader.
21306c3fb27SDimitry Andric
21406c3fb27SDimitry Andric // The predecessor has exactly one successor, so it is a preheader.
21506c3fb27SDimitry Andric return Out;
21606c3fb27SDimitry Andric }
21706c3fb27SDimitry Andric
21806c3fb27SDimitry Andric /// getLoopPredecessor - If the given loop's header has exactly one unique
21906c3fb27SDimitry Andric /// predecessor outside the loop, return it. Otherwise return null.
22006c3fb27SDimitry Andric /// This is less strict that the loop "preheader" concept, which requires
22106c3fb27SDimitry Andric /// the predecessor to have exactly one successor.
22206c3fb27SDimitry Andric ///
22306c3fb27SDimitry Andric template <class BlockT, class LoopT>
getLoopPredecessor()22406c3fb27SDimitry Andric BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
22506c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!");
22606c3fb27SDimitry Andric // Keep track of nodes outside the loop branching to the header...
22706c3fb27SDimitry Andric BlockT *Out = nullptr;
22806c3fb27SDimitry Andric
22906c3fb27SDimitry Andric // Loop over the predecessors of the header node...
23006c3fb27SDimitry Andric BlockT *Header = getHeader();
231*7a6dacacSDimitry Andric for (const auto Pred : inverse_children<BlockT *>(Header)) {
23206c3fb27SDimitry Andric if (!contains(Pred)) { // If the block is not in the loop...
23306c3fb27SDimitry Andric if (Out && Out != Pred)
23406c3fb27SDimitry Andric return nullptr; // Multiple predecessors outside the loop
23506c3fb27SDimitry Andric Out = Pred;
23606c3fb27SDimitry Andric }
23706c3fb27SDimitry Andric }
23806c3fb27SDimitry Andric
23906c3fb27SDimitry Andric return Out;
24006c3fb27SDimitry Andric }
24106c3fb27SDimitry Andric
24206c3fb27SDimitry Andric /// getLoopLatch - If there is a single latch block for this loop, return it.
24306c3fb27SDimitry Andric /// A latch block is a block that contains a branch back to the header.
24406c3fb27SDimitry Andric template <class BlockT, class LoopT>
getLoopLatch()24506c3fb27SDimitry Andric BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
24606c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!");
24706c3fb27SDimitry Andric BlockT *Header = getHeader();
24806c3fb27SDimitry Andric BlockT *Latch = nullptr;
249*7a6dacacSDimitry Andric for (const auto Pred : inverse_children<BlockT *>(Header)) {
25006c3fb27SDimitry Andric if (contains(Pred)) {
25106c3fb27SDimitry Andric if (Latch)
25206c3fb27SDimitry Andric return nullptr;
25306c3fb27SDimitry Andric Latch = Pred;
25406c3fb27SDimitry Andric }
25506c3fb27SDimitry Andric }
25606c3fb27SDimitry Andric
25706c3fb27SDimitry Andric return Latch;
25806c3fb27SDimitry Andric }
25906c3fb27SDimitry Andric
26006c3fb27SDimitry Andric //===----------------------------------------------------------------------===//
26106c3fb27SDimitry Andric // APIs for updating loop information after changing the CFG
26206c3fb27SDimitry Andric //
26306c3fb27SDimitry Andric
26406c3fb27SDimitry Andric /// addBasicBlockToLoop - This method is used by other analyses to update loop
26506c3fb27SDimitry Andric /// information. NewBB is set to be a new member of the current loop.
26606c3fb27SDimitry Andric /// Because of this, it is added as a member of all parent loops, and is added
26706c3fb27SDimitry Andric /// to the specified LoopInfo object as being in the current basic block. It
26806c3fb27SDimitry Andric /// is not valid to replace the loop header with this method.
26906c3fb27SDimitry Andric ///
27006c3fb27SDimitry Andric template <class BlockT, class LoopT>
addBasicBlockToLoop(BlockT * NewBB,LoopInfoBase<BlockT,LoopT> & LIB)27106c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::addBasicBlockToLoop(
27206c3fb27SDimitry Andric BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
27306c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!");
27406c3fb27SDimitry Andric #ifndef NDEBUG
27506c3fb27SDimitry Andric if (!Blocks.empty()) {
27606c3fb27SDimitry Andric auto SameHeader = LIB[getHeader()];
27706c3fb27SDimitry Andric assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
27806c3fb27SDimitry Andric "Incorrect LI specified for this loop!");
27906c3fb27SDimitry Andric }
28006c3fb27SDimitry Andric #endif
28106c3fb27SDimitry Andric assert(NewBB && "Cannot add a null basic block to the loop!");
28206c3fb27SDimitry Andric assert(!LIB[NewBB] && "BasicBlock already in the loop!");
28306c3fb27SDimitry Andric
28406c3fb27SDimitry Andric LoopT *L = static_cast<LoopT *>(this);
28506c3fb27SDimitry Andric
28606c3fb27SDimitry Andric // Add the loop mapping to the LoopInfo object...
28706c3fb27SDimitry Andric LIB.BBMap[NewBB] = L;
28806c3fb27SDimitry Andric
28906c3fb27SDimitry Andric // Add the basic block to this loop and all parent loops...
29006c3fb27SDimitry Andric while (L) {
29106c3fb27SDimitry Andric L->addBlockEntry(NewBB);
29206c3fb27SDimitry Andric L = L->getParentLoop();
29306c3fb27SDimitry Andric }
29406c3fb27SDimitry Andric }
29506c3fb27SDimitry Andric
29606c3fb27SDimitry Andric /// replaceChildLoopWith - This is used when splitting loops up. It replaces
29706c3fb27SDimitry Andric /// the OldChild entry in our children list with NewChild, and updates the
29806c3fb27SDimitry Andric /// parent pointer of OldChild to be null and the NewChild to be this loop.
29906c3fb27SDimitry Andric /// This updates the loop depth of the new child.
30006c3fb27SDimitry Andric template <class BlockT, class LoopT>
replaceChildLoopWith(LoopT * OldChild,LoopT * NewChild)30106c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::replaceChildLoopWith(LoopT *OldChild,
30206c3fb27SDimitry Andric LoopT *NewChild) {
30306c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!");
30406c3fb27SDimitry Andric assert(OldChild->ParentLoop == this && "This loop is already broken!");
30506c3fb27SDimitry Andric assert(!NewChild->ParentLoop && "NewChild already has a parent!");
30606c3fb27SDimitry Andric typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
30706c3fb27SDimitry Andric assert(I != SubLoops.end() && "OldChild not in loop!");
30806c3fb27SDimitry Andric *I = NewChild;
30906c3fb27SDimitry Andric OldChild->ParentLoop = nullptr;
31006c3fb27SDimitry Andric NewChild->ParentLoop = static_cast<LoopT *>(this);
31106c3fb27SDimitry Andric }
31206c3fb27SDimitry Andric
31306c3fb27SDimitry Andric /// verifyLoop - Verify loop structure
31406c3fb27SDimitry Andric template <class BlockT, class LoopT>
verifyLoop()31506c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::verifyLoop() const {
31606c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!");
31706c3fb27SDimitry Andric #ifndef NDEBUG
31806c3fb27SDimitry Andric assert(!Blocks.empty() && "Loop header is missing");
31906c3fb27SDimitry Andric
32006c3fb27SDimitry Andric // Setup for using a depth-first iterator to visit every block in the loop.
32106c3fb27SDimitry Andric SmallVector<BlockT *, 8> ExitBBs;
32206c3fb27SDimitry Andric getExitBlocks(ExitBBs);
32306c3fb27SDimitry Andric df_iterator_default_set<BlockT *> VisitSet;
32406c3fb27SDimitry Andric VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
32506c3fb27SDimitry Andric
32606c3fb27SDimitry Andric // Keep track of the BBs visited.
32706c3fb27SDimitry Andric SmallPtrSet<BlockT *, 8> VisitedBBs;
32806c3fb27SDimitry Andric
32906c3fb27SDimitry Andric // Check the individual blocks.
33006c3fb27SDimitry Andric for (BlockT *BB : depth_first_ext(getHeader(), VisitSet)) {
331*7a6dacacSDimitry Andric assert(llvm::any_of(children<BlockT *>(BB),
33206c3fb27SDimitry Andric [&](BlockT *B) { return contains(B); }) &&
33306c3fb27SDimitry Andric "Loop block has no in-loop successors!");
33406c3fb27SDimitry Andric
335*7a6dacacSDimitry Andric assert(llvm::any_of(inverse_children<BlockT *>(BB),
33606c3fb27SDimitry Andric [&](BlockT *B) { return contains(B); }) &&
33706c3fb27SDimitry Andric "Loop block has no in-loop predecessors!");
33806c3fb27SDimitry Andric
33906c3fb27SDimitry Andric SmallVector<BlockT *, 2> OutsideLoopPreds;
340*7a6dacacSDimitry Andric for (BlockT *B : inverse_children<BlockT *>(BB))
34106c3fb27SDimitry Andric if (!contains(B))
34206c3fb27SDimitry Andric OutsideLoopPreds.push_back(B);
34306c3fb27SDimitry Andric
34406c3fb27SDimitry Andric if (BB == getHeader()) {
34506c3fb27SDimitry Andric assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
34606c3fb27SDimitry Andric } else if (!OutsideLoopPreds.empty()) {
34706c3fb27SDimitry Andric // A non-header loop shouldn't be reachable from outside the loop,
34806c3fb27SDimitry Andric // though it is permitted if the predecessor is not itself actually
34906c3fb27SDimitry Andric // reachable.
35006c3fb27SDimitry Andric BlockT *EntryBB = &BB->getParent()->front();
35106c3fb27SDimitry Andric for (BlockT *CB : depth_first(EntryBB))
35206c3fb27SDimitry Andric for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
35306c3fb27SDimitry Andric assert(CB != OutsideLoopPreds[i] &&
35406c3fb27SDimitry Andric "Loop has multiple entry points!");
35506c3fb27SDimitry Andric }
35606c3fb27SDimitry Andric assert(BB != &getHeader()->getParent()->front() &&
35706c3fb27SDimitry Andric "Loop contains function entry block!");
35806c3fb27SDimitry Andric
35906c3fb27SDimitry Andric VisitedBBs.insert(BB);
36006c3fb27SDimitry Andric }
36106c3fb27SDimitry Andric
36206c3fb27SDimitry Andric if (VisitedBBs.size() != getNumBlocks()) {
36306c3fb27SDimitry Andric dbgs() << "The following blocks are unreachable in the loop: ";
36406c3fb27SDimitry Andric for (auto *BB : Blocks) {
36506c3fb27SDimitry Andric if (!VisitedBBs.count(BB)) {
36606c3fb27SDimitry Andric dbgs() << *BB << "\n";
36706c3fb27SDimitry Andric }
36806c3fb27SDimitry Andric }
36906c3fb27SDimitry Andric assert(false && "Unreachable block in loop");
37006c3fb27SDimitry Andric }
37106c3fb27SDimitry Andric
37206c3fb27SDimitry Andric // Check the subloops.
37306c3fb27SDimitry Andric for (iterator I = begin(), E = end(); I != E; ++I)
37406c3fb27SDimitry Andric // Each block in each subloop should be contained within this loop.
37506c3fb27SDimitry Andric for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
37606c3fb27SDimitry Andric BI != BE; ++BI) {
37706c3fb27SDimitry Andric assert(contains(*BI) &&
37806c3fb27SDimitry Andric "Loop does not contain all the blocks of a subloop!");
37906c3fb27SDimitry Andric }
38006c3fb27SDimitry Andric
38106c3fb27SDimitry Andric // Check the parent loop pointer.
38206c3fb27SDimitry Andric if (ParentLoop) {
38306c3fb27SDimitry Andric assert(is_contained(ParentLoop->getSubLoops(), this) &&
38406c3fb27SDimitry Andric "Loop is not a subloop of its parent!");
38506c3fb27SDimitry Andric }
38606c3fb27SDimitry Andric #endif
38706c3fb27SDimitry Andric }
38806c3fb27SDimitry Andric
38906c3fb27SDimitry Andric /// verifyLoop - Verify loop structure of this loop and all nested loops.
39006c3fb27SDimitry Andric template <class BlockT, class LoopT>
verifyLoopNest(DenseSet<const LoopT * > * Loops)39106c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::verifyLoopNest(
39206c3fb27SDimitry Andric DenseSet<const LoopT *> *Loops) const {
39306c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!");
39406c3fb27SDimitry Andric Loops->insert(static_cast<const LoopT *>(this));
39506c3fb27SDimitry Andric // Verify this loop.
39606c3fb27SDimitry Andric verifyLoop();
39706c3fb27SDimitry Andric // Verify the subloops.
39806c3fb27SDimitry Andric for (iterator I = begin(), E = end(); I != E; ++I)
39906c3fb27SDimitry Andric (*I)->verifyLoopNest(Loops);
40006c3fb27SDimitry Andric }
40106c3fb27SDimitry Andric
40206c3fb27SDimitry Andric template <class BlockT, class LoopT>
print(raw_ostream & OS,bool Verbose,bool PrintNested,unsigned Depth)40306c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::print(raw_ostream &OS, bool Verbose,
40406c3fb27SDimitry Andric bool PrintNested, unsigned Depth) const {
40506c3fb27SDimitry Andric OS.indent(Depth * 2);
40606c3fb27SDimitry Andric if (static_cast<const LoopT *>(this)->isAnnotatedParallel())
40706c3fb27SDimitry Andric OS << "Parallel ";
40806c3fb27SDimitry Andric OS << "Loop at depth " << getLoopDepth() << " containing: ";
40906c3fb27SDimitry Andric
41006c3fb27SDimitry Andric BlockT *H = getHeader();
41106c3fb27SDimitry Andric for (unsigned i = 0; i < getBlocks().size(); ++i) {
41206c3fb27SDimitry Andric BlockT *BB = getBlocks()[i];
41306c3fb27SDimitry Andric if (!Verbose) {
41406c3fb27SDimitry Andric if (i)
41506c3fb27SDimitry Andric OS << ",";
41606c3fb27SDimitry Andric BB->printAsOperand(OS, false);
41706c3fb27SDimitry Andric } else
41806c3fb27SDimitry Andric OS << "\n";
41906c3fb27SDimitry Andric
42006c3fb27SDimitry Andric if (BB == H)
42106c3fb27SDimitry Andric OS << "<header>";
42206c3fb27SDimitry Andric if (isLoopLatch(BB))
42306c3fb27SDimitry Andric OS << "<latch>";
42406c3fb27SDimitry Andric if (isLoopExiting(BB))
42506c3fb27SDimitry Andric OS << "<exiting>";
42606c3fb27SDimitry Andric if (Verbose)
42706c3fb27SDimitry Andric BB->print(OS);
42806c3fb27SDimitry Andric }
42906c3fb27SDimitry Andric
43006c3fb27SDimitry Andric if (PrintNested) {
43106c3fb27SDimitry Andric OS << "\n";
43206c3fb27SDimitry Andric
43306c3fb27SDimitry Andric for (iterator I = begin(), E = end(); I != E; ++I)
43406c3fb27SDimitry Andric (*I)->print(OS, /*Verbose*/ false, PrintNested, Depth + 2);
43506c3fb27SDimitry Andric }
43606c3fb27SDimitry Andric }
43706c3fb27SDimitry Andric
43806c3fb27SDimitry Andric //===----------------------------------------------------------------------===//
43906c3fb27SDimitry Andric /// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
44006c3fb27SDimitry Andric /// result does / not depend on use list (block predecessor) order.
44106c3fb27SDimitry Andric ///
44206c3fb27SDimitry Andric
44306c3fb27SDimitry Andric /// Discover a subloop with the specified backedges such that: All blocks within
44406c3fb27SDimitry Andric /// this loop are mapped to this loop or a subloop. And all subloops within this
44506c3fb27SDimitry Andric /// loop have their parent loop set to this loop or a subloop.
44606c3fb27SDimitry Andric template <class BlockT, class LoopT>
discoverAndMapSubloop(LoopT * L,ArrayRef<BlockT * > Backedges,LoopInfoBase<BlockT,LoopT> * LI,const DomTreeBase<BlockT> & DomTree)44706c3fb27SDimitry Andric static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges,
44806c3fb27SDimitry Andric LoopInfoBase<BlockT, LoopT> *LI,
44906c3fb27SDimitry Andric const DomTreeBase<BlockT> &DomTree) {
45006c3fb27SDimitry Andric typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
45106c3fb27SDimitry Andric
45206c3fb27SDimitry Andric unsigned NumBlocks = 0;
45306c3fb27SDimitry Andric unsigned NumSubloops = 0;
45406c3fb27SDimitry Andric
45506c3fb27SDimitry Andric // Perform a backward CFG traversal using a worklist.
45606c3fb27SDimitry Andric std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
45706c3fb27SDimitry Andric while (!ReverseCFGWorklist.empty()) {
45806c3fb27SDimitry Andric BlockT *PredBB = ReverseCFGWorklist.back();
45906c3fb27SDimitry Andric ReverseCFGWorklist.pop_back();
46006c3fb27SDimitry Andric
46106c3fb27SDimitry Andric LoopT *Subloop = LI->getLoopFor(PredBB);
46206c3fb27SDimitry Andric if (!Subloop) {
46306c3fb27SDimitry Andric if (!DomTree.isReachableFromEntry(PredBB))
46406c3fb27SDimitry Andric continue;
46506c3fb27SDimitry Andric
46606c3fb27SDimitry Andric // This is an undiscovered block. Map it to the current loop.
46706c3fb27SDimitry Andric LI->changeLoopFor(PredBB, L);
46806c3fb27SDimitry Andric ++NumBlocks;
46906c3fb27SDimitry Andric if (PredBB == L->getHeader())
47006c3fb27SDimitry Andric continue;
47106c3fb27SDimitry Andric // Push all block predecessors on the worklist.
47206c3fb27SDimitry Andric ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
47306c3fb27SDimitry Andric InvBlockTraits::child_begin(PredBB),
47406c3fb27SDimitry Andric InvBlockTraits::child_end(PredBB));
47506c3fb27SDimitry Andric } else {
47606c3fb27SDimitry Andric // This is a discovered block. Find its outermost discovered loop.
47706c3fb27SDimitry Andric Subloop = Subloop->getOutermostLoop();
47806c3fb27SDimitry Andric
47906c3fb27SDimitry Andric // If it is already discovered to be a subloop of this loop, continue.
48006c3fb27SDimitry Andric if (Subloop == L)
48106c3fb27SDimitry Andric continue;
48206c3fb27SDimitry Andric
48306c3fb27SDimitry Andric // Discover a subloop of this loop.
48406c3fb27SDimitry Andric Subloop->setParentLoop(L);
48506c3fb27SDimitry Andric ++NumSubloops;
48606c3fb27SDimitry Andric NumBlocks += Subloop->getBlocksVector().capacity();
48706c3fb27SDimitry Andric PredBB = Subloop->getHeader();
48806c3fb27SDimitry Andric // Continue traversal along predecessors that are not loop-back edges from
48906c3fb27SDimitry Andric // within this subloop tree itself. Note that a predecessor may directly
49006c3fb27SDimitry Andric // reach another subloop that is not yet discovered to be a subloop of
49106c3fb27SDimitry Andric // this loop, which we must traverse.
492*7a6dacacSDimitry Andric for (const auto Pred : inverse_children<BlockT *>(PredBB)) {
49306c3fb27SDimitry Andric if (LI->getLoopFor(Pred) != Subloop)
49406c3fb27SDimitry Andric ReverseCFGWorklist.push_back(Pred);
49506c3fb27SDimitry Andric }
49606c3fb27SDimitry Andric }
49706c3fb27SDimitry Andric }
49806c3fb27SDimitry Andric L->getSubLoopsVector().reserve(NumSubloops);
49906c3fb27SDimitry Andric L->reserveBlocks(NumBlocks);
50006c3fb27SDimitry Andric }
50106c3fb27SDimitry Andric
50206c3fb27SDimitry Andric /// Populate all loop data in a stable order during a single forward DFS.
50306c3fb27SDimitry Andric template <class BlockT, class LoopT> class PopulateLoopsDFS {
50406c3fb27SDimitry Andric typedef GraphTraits<BlockT *> BlockTraits;
50506c3fb27SDimitry Andric typedef typename BlockTraits::ChildIteratorType SuccIterTy;
50606c3fb27SDimitry Andric
50706c3fb27SDimitry Andric LoopInfoBase<BlockT, LoopT> *LI;
50806c3fb27SDimitry Andric
50906c3fb27SDimitry Andric public:
PopulateLoopsDFS(LoopInfoBase<BlockT,LoopT> * li)51006c3fb27SDimitry Andric PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {}
51106c3fb27SDimitry Andric
51206c3fb27SDimitry Andric void traverse(BlockT *EntryBlock);
51306c3fb27SDimitry Andric
51406c3fb27SDimitry Andric protected:
51506c3fb27SDimitry Andric void insertIntoLoop(BlockT *Block);
51606c3fb27SDimitry Andric };
51706c3fb27SDimitry Andric
51806c3fb27SDimitry Andric /// Top-level driver for the forward DFS within the loop.
51906c3fb27SDimitry Andric template <class BlockT, class LoopT>
traverse(BlockT * EntryBlock)52006c3fb27SDimitry Andric void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
52106c3fb27SDimitry Andric for (BlockT *BB : post_order(EntryBlock))
52206c3fb27SDimitry Andric insertIntoLoop(BB);
52306c3fb27SDimitry Andric }
52406c3fb27SDimitry Andric
52506c3fb27SDimitry Andric /// Add a single Block to its ancestor loops in PostOrder. If the block is a
52606c3fb27SDimitry Andric /// subloop header, add the subloop to its parent in PostOrder, then reverse the
52706c3fb27SDimitry Andric /// Block and Subloop vectors of the now complete subloop to achieve RPO.
52806c3fb27SDimitry Andric template <class BlockT, class LoopT>
insertIntoLoop(BlockT * Block)52906c3fb27SDimitry Andric void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
53006c3fb27SDimitry Andric LoopT *Subloop = LI->getLoopFor(Block);
53106c3fb27SDimitry Andric if (Subloop && Block == Subloop->getHeader()) {
53206c3fb27SDimitry Andric // We reach this point once per subloop after processing all the blocks in
53306c3fb27SDimitry Andric // the subloop.
53406c3fb27SDimitry Andric if (!Subloop->isOutermost())
53506c3fb27SDimitry Andric Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
53606c3fb27SDimitry Andric else
53706c3fb27SDimitry Andric LI->addTopLevelLoop(Subloop);
53806c3fb27SDimitry Andric
53906c3fb27SDimitry Andric // For convenience, Blocks and Subloops are inserted in postorder. Reverse
54006c3fb27SDimitry Andric // the lists, except for the loop header, which is always at the beginning.
54106c3fb27SDimitry Andric Subloop->reverseBlock(1);
54206c3fb27SDimitry Andric std::reverse(Subloop->getSubLoopsVector().begin(),
54306c3fb27SDimitry Andric Subloop->getSubLoopsVector().end());
54406c3fb27SDimitry Andric
54506c3fb27SDimitry Andric Subloop = Subloop->getParentLoop();
54606c3fb27SDimitry Andric }
54706c3fb27SDimitry Andric for (; Subloop; Subloop = Subloop->getParentLoop())
54806c3fb27SDimitry Andric Subloop->addBlockEntry(Block);
54906c3fb27SDimitry Andric }
55006c3fb27SDimitry Andric
55106c3fb27SDimitry Andric /// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
55206c3fb27SDimitry Andric /// interleaved with backward CFG traversals within each subloop
55306c3fb27SDimitry Andric /// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
55406c3fb27SDimitry Andric /// this part of the algorithm is linear in the number of CFG edges. Subloop and
55506c3fb27SDimitry Andric /// Block vectors are then populated during a single forward CFG traversal
55606c3fb27SDimitry Andric /// (PopulateLoopDFS).
55706c3fb27SDimitry Andric ///
55806c3fb27SDimitry Andric /// During the two CFG traversals each block is seen three times:
55906c3fb27SDimitry Andric /// 1) Discovered and mapped by a reverse CFG traversal.
56006c3fb27SDimitry Andric /// 2) Visited during a forward DFS CFG traversal.
56106c3fb27SDimitry Andric /// 3) Reverse-inserted in the loop in postorder following forward DFS.
56206c3fb27SDimitry Andric ///
56306c3fb27SDimitry Andric /// The Block vectors are inclusive, so step 3 requires loop-depth number of
56406c3fb27SDimitry Andric /// insertions per block.
56506c3fb27SDimitry Andric template <class BlockT, class LoopT>
analyze(const DomTreeBase<BlockT> & DomTree)56606c3fb27SDimitry Andric void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
56706c3fb27SDimitry Andric // Postorder traversal of the dominator tree.
56806c3fb27SDimitry Andric const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
56906c3fb27SDimitry Andric for (auto DomNode : post_order(DomRoot)) {
57006c3fb27SDimitry Andric
57106c3fb27SDimitry Andric BlockT *Header = DomNode->getBlock();
57206c3fb27SDimitry Andric SmallVector<BlockT *, 4> Backedges;
57306c3fb27SDimitry Andric
57406c3fb27SDimitry Andric // Check each predecessor of the potential loop header.
575*7a6dacacSDimitry Andric for (const auto Backedge : inverse_children<BlockT *>(Header)) {
57606c3fb27SDimitry Andric // If Header dominates predBB, this is a new loop. Collect the backedges.
5775f757f3fSDimitry Andric const DomTreeNodeBase<BlockT> *BackedgeNode = DomTree.getNode(Backedge);
5785f757f3fSDimitry Andric if (BackedgeNode && DomTree.dominates(DomNode, BackedgeNode))
57906c3fb27SDimitry Andric Backedges.push_back(Backedge);
58006c3fb27SDimitry Andric }
58106c3fb27SDimitry Andric // Perform a backward CFG traversal to discover and map blocks in this loop.
58206c3fb27SDimitry Andric if (!Backedges.empty()) {
58306c3fb27SDimitry Andric LoopT *L = AllocateLoop(Header);
58406c3fb27SDimitry Andric discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
58506c3fb27SDimitry Andric }
58606c3fb27SDimitry Andric }
58706c3fb27SDimitry Andric // Perform a single forward CFG traversal to populate block and subloop
58806c3fb27SDimitry Andric // vectors for all loops.
58906c3fb27SDimitry Andric PopulateLoopsDFS<BlockT, LoopT> DFS(this);
59006c3fb27SDimitry Andric DFS.traverse(DomRoot->getBlock());
59106c3fb27SDimitry Andric }
59206c3fb27SDimitry Andric
59306c3fb27SDimitry Andric template <class BlockT, class LoopT>
59406c3fb27SDimitry Andric SmallVector<LoopT *, 4>
getLoopsInPreorder()59506c3fb27SDimitry Andric LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() const {
59606c3fb27SDimitry Andric SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
59706c3fb27SDimitry Andric // The outer-most loop actually goes into the result in the same relative
59806c3fb27SDimitry Andric // order as we walk it. But LoopInfo stores the top level loops in reverse
59906c3fb27SDimitry Andric // program order so for here we reverse it to get forward program order.
60006c3fb27SDimitry Andric // FIXME: If we change the order of LoopInfo we will want to remove the
60106c3fb27SDimitry Andric // reverse here.
60206c3fb27SDimitry Andric for (LoopT *RootL : reverse(*this)) {
60306c3fb27SDimitry Andric auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder();
60406c3fb27SDimitry Andric PreOrderLoops.append(PreOrderLoopsInRootL.begin(),
60506c3fb27SDimitry Andric PreOrderLoopsInRootL.end());
60606c3fb27SDimitry Andric }
60706c3fb27SDimitry Andric
60806c3fb27SDimitry Andric return PreOrderLoops;
60906c3fb27SDimitry Andric }
61006c3fb27SDimitry Andric
61106c3fb27SDimitry Andric template <class BlockT, class LoopT>
61206c3fb27SDimitry Andric SmallVector<LoopT *, 4>
getLoopsInReverseSiblingPreorder()61306c3fb27SDimitry Andric LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() const {
61406c3fb27SDimitry Andric SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
61506c3fb27SDimitry Andric // The outer-most loop actually goes into the result in the same relative
61606c3fb27SDimitry Andric // order as we walk it. LoopInfo stores the top level loops in reverse
61706c3fb27SDimitry Andric // program order so we walk in order here.
61806c3fb27SDimitry Andric // FIXME: If we change the order of LoopInfo we will want to add a reverse
61906c3fb27SDimitry Andric // here.
62006c3fb27SDimitry Andric for (LoopT *RootL : *this) {
62106c3fb27SDimitry Andric assert(PreOrderWorklist.empty() &&
62206c3fb27SDimitry Andric "Must start with an empty preorder walk worklist.");
62306c3fb27SDimitry Andric PreOrderWorklist.push_back(RootL);
62406c3fb27SDimitry Andric do {
62506c3fb27SDimitry Andric LoopT *L = PreOrderWorklist.pop_back_val();
62606c3fb27SDimitry Andric // Sub-loops are stored in forward program order, but will process the
62706c3fb27SDimitry Andric // worklist backwards so we can just append them in order.
62806c3fb27SDimitry Andric PreOrderWorklist.append(L->begin(), L->end());
62906c3fb27SDimitry Andric PreOrderLoops.push_back(L);
63006c3fb27SDimitry Andric } while (!PreOrderWorklist.empty());
63106c3fb27SDimitry Andric }
63206c3fb27SDimitry Andric
63306c3fb27SDimitry Andric return PreOrderLoops;
63406c3fb27SDimitry Andric }
63506c3fb27SDimitry Andric
63606c3fb27SDimitry Andric // Debugging
63706c3fb27SDimitry Andric template <class BlockT, class LoopT>
print(raw_ostream & OS)63806c3fb27SDimitry Andric void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const {
63906c3fb27SDimitry Andric for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
64006c3fb27SDimitry Andric TopLevelLoops[i]->print(OS);
64106c3fb27SDimitry Andric #if 0
64206c3fb27SDimitry Andric for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
64306c3fb27SDimitry Andric E = BBMap.end(); I != E; ++I)
64406c3fb27SDimitry Andric OS << "BB '" << I->first->getName() << "' level = "
64506c3fb27SDimitry Andric << I->second->getLoopDepth() << "\n";
64606c3fb27SDimitry Andric #endif
64706c3fb27SDimitry Andric }
64806c3fb27SDimitry Andric
64906c3fb27SDimitry Andric template <typename T>
compareVectors(std::vector<T> & BB1,std::vector<T> & BB2)65006c3fb27SDimitry Andric bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) {
65106c3fb27SDimitry Andric llvm::sort(BB1);
65206c3fb27SDimitry Andric llvm::sort(BB2);
65306c3fb27SDimitry Andric return BB1 == BB2;
65406c3fb27SDimitry Andric }
65506c3fb27SDimitry Andric
65606c3fb27SDimitry Andric template <class BlockT, class LoopT>
addInnerLoopsToHeadersMap(DenseMap<BlockT *,const LoopT * > & LoopHeaders,const LoopInfoBase<BlockT,LoopT> & LI,const LoopT & L)65706c3fb27SDimitry Andric void addInnerLoopsToHeadersMap(DenseMap<BlockT *, const LoopT *> &LoopHeaders,
65806c3fb27SDimitry Andric const LoopInfoBase<BlockT, LoopT> &LI,
65906c3fb27SDimitry Andric const LoopT &L) {
66006c3fb27SDimitry Andric LoopHeaders[L.getHeader()] = &L;
66106c3fb27SDimitry Andric for (LoopT *SL : L)
66206c3fb27SDimitry Andric addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL);
66306c3fb27SDimitry Andric }
66406c3fb27SDimitry Andric
66506c3fb27SDimitry Andric #ifndef NDEBUG
66606c3fb27SDimitry Andric template <class BlockT, class LoopT>
compareLoops(const LoopT * L,const LoopT * OtherL,DenseMap<BlockT *,const LoopT * > & OtherLoopHeaders)66706c3fb27SDimitry Andric static void compareLoops(const LoopT *L, const LoopT *OtherL,
66806c3fb27SDimitry Andric DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) {
66906c3fb27SDimitry Andric BlockT *H = L->getHeader();
67006c3fb27SDimitry Andric BlockT *OtherH = OtherL->getHeader();
67106c3fb27SDimitry Andric assert(H == OtherH &&
67206c3fb27SDimitry Andric "Mismatched headers even though found in the same map entry!");
67306c3fb27SDimitry Andric
67406c3fb27SDimitry Andric assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
67506c3fb27SDimitry Andric "Mismatched loop depth!");
67606c3fb27SDimitry Andric const LoopT *ParentL = L, *OtherParentL = OtherL;
67706c3fb27SDimitry Andric do {
67806c3fb27SDimitry Andric assert(ParentL->getHeader() == OtherParentL->getHeader() &&
67906c3fb27SDimitry Andric "Mismatched parent loop headers!");
68006c3fb27SDimitry Andric ParentL = ParentL->getParentLoop();
68106c3fb27SDimitry Andric OtherParentL = OtherParentL->getParentLoop();
68206c3fb27SDimitry Andric } while (ParentL);
68306c3fb27SDimitry Andric
68406c3fb27SDimitry Andric for (const LoopT *SubL : *L) {
68506c3fb27SDimitry Andric BlockT *SubH = SubL->getHeader();
68606c3fb27SDimitry Andric const LoopT *OtherSubL = OtherLoopHeaders.lookup(SubH);
68706c3fb27SDimitry Andric assert(OtherSubL && "Inner loop is missing in computed loop info!");
68806c3fb27SDimitry Andric OtherLoopHeaders.erase(SubH);
68906c3fb27SDimitry Andric compareLoops(SubL, OtherSubL, OtherLoopHeaders);
69006c3fb27SDimitry Andric }
69106c3fb27SDimitry Andric
69206c3fb27SDimitry Andric std::vector<BlockT *> BBs = L->getBlocks();
69306c3fb27SDimitry Andric std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
69406c3fb27SDimitry Andric assert(compareVectors(BBs, OtherBBs) &&
69506c3fb27SDimitry Andric "Mismatched basic blocks in the loops!");
69606c3fb27SDimitry Andric
69706c3fb27SDimitry Andric const SmallPtrSetImpl<const BlockT *> &BlocksSet = L->getBlocksSet();
69806c3fb27SDimitry Andric const SmallPtrSetImpl<const BlockT *> &OtherBlocksSet =
69906c3fb27SDimitry Andric OtherL->getBlocksSet();
70006c3fb27SDimitry Andric assert(BlocksSet.size() == OtherBlocksSet.size() &&
70106c3fb27SDimitry Andric llvm::set_is_subset(BlocksSet, OtherBlocksSet) &&
70206c3fb27SDimitry Andric "Mismatched basic blocks in BlocksSets!");
70306c3fb27SDimitry Andric }
70406c3fb27SDimitry Andric #endif
70506c3fb27SDimitry Andric
70606c3fb27SDimitry Andric template <class BlockT, class LoopT>
verify(const DomTreeBase<BlockT> & DomTree)70706c3fb27SDimitry Andric void LoopInfoBase<BlockT, LoopT>::verify(
70806c3fb27SDimitry Andric const DomTreeBase<BlockT> &DomTree) const {
70906c3fb27SDimitry Andric DenseSet<const LoopT *> Loops;
71006c3fb27SDimitry Andric for (iterator I = begin(), E = end(); I != E; ++I) {
71106c3fb27SDimitry Andric assert((*I)->isOutermost() && "Top-level loop has a parent!");
71206c3fb27SDimitry Andric (*I)->verifyLoopNest(&Loops);
71306c3fb27SDimitry Andric }
71406c3fb27SDimitry Andric
71506c3fb27SDimitry Andric // Verify that blocks are mapped to valid loops.
71606c3fb27SDimitry Andric #ifndef NDEBUG
71706c3fb27SDimitry Andric for (auto &Entry : BBMap) {
71806c3fb27SDimitry Andric const BlockT *BB = Entry.first;
71906c3fb27SDimitry Andric LoopT *L = Entry.second;
72006c3fb27SDimitry Andric assert(Loops.count(L) && "orphaned loop");
72106c3fb27SDimitry Andric assert(L->contains(BB) && "orphaned block");
72206c3fb27SDimitry Andric for (LoopT *ChildLoop : *L)
72306c3fb27SDimitry Andric assert(!ChildLoop->contains(BB) &&
72406c3fb27SDimitry Andric "BBMap should point to the innermost loop containing BB");
72506c3fb27SDimitry Andric }
72606c3fb27SDimitry Andric
72706c3fb27SDimitry Andric // Recompute LoopInfo to verify loops structure.
72806c3fb27SDimitry Andric LoopInfoBase<BlockT, LoopT> OtherLI;
72906c3fb27SDimitry Andric OtherLI.analyze(DomTree);
73006c3fb27SDimitry Andric
73106c3fb27SDimitry Andric // Build a map we can use to move from our LI to the computed one. This
73206c3fb27SDimitry Andric // allows us to ignore the particular order in any layer of the loop forest
73306c3fb27SDimitry Andric // while still comparing the structure.
73406c3fb27SDimitry Andric DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
73506c3fb27SDimitry Andric for (LoopT *L : OtherLI)
73606c3fb27SDimitry Andric addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
73706c3fb27SDimitry Andric
73806c3fb27SDimitry Andric // Walk the top level loops and ensure there is a corresponding top-level
73906c3fb27SDimitry Andric // loop in the computed version and then recursively compare those loop
74006c3fb27SDimitry Andric // nests.
74106c3fb27SDimitry Andric for (LoopT *L : *this) {
74206c3fb27SDimitry Andric BlockT *Header = L->getHeader();
74306c3fb27SDimitry Andric const LoopT *OtherL = OtherLoopHeaders.lookup(Header);
74406c3fb27SDimitry Andric assert(OtherL && "Top level loop is missing in computed loop info!");
74506c3fb27SDimitry Andric // Now that we've matched this loop, erase its header from the map.
74606c3fb27SDimitry Andric OtherLoopHeaders.erase(Header);
74706c3fb27SDimitry Andric // And recursively compare these loops.
74806c3fb27SDimitry Andric compareLoops(L, OtherL, OtherLoopHeaders);
74906c3fb27SDimitry Andric }
75006c3fb27SDimitry Andric
75106c3fb27SDimitry Andric // Any remaining entries in the map are loops which were found when computing
75206c3fb27SDimitry Andric // a fresh LoopInfo but not present in the current one.
75306c3fb27SDimitry Andric if (!OtherLoopHeaders.empty()) {
75406c3fb27SDimitry Andric for (const auto &HeaderAndLoop : OtherLoopHeaders)
75506c3fb27SDimitry Andric dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
75606c3fb27SDimitry Andric llvm_unreachable("Found new loops when recomputing LoopInfo!");
75706c3fb27SDimitry Andric }
75806c3fb27SDimitry Andric #endif
75906c3fb27SDimitry Andric }
76006c3fb27SDimitry Andric
76106c3fb27SDimitry Andric } // namespace llvm
76206c3fb27SDimitry Andric
76306c3fb27SDimitry Andric #endif // LLVM_SUPPORT_GENERICLOOPINFOIMPL_H
764