14#ifndef LLVM_SUPPORT_GENERICLOOPINFOIMPL_H
15#define LLVM_SUPPORT_GENERICLOOPINFOIMPL_H
32template <
class BlockT,
class LoopT>
35 assert(!isInvalid() &&
"Loop not in a valid state!");
36 for (
const auto BB :
blocks())
37 for (
auto *Succ : children<BlockT *>(BB))
47template <
class BlockT,
class LoopT>
49 assert(!isInvalid() &&
"Loop not in a valid state!");
50 auto notInLoop = [&](BlockT *BB) {
return !
contains(BB); };
51 auto isExitBlock = [&](BlockT *BB,
bool AllowRepeats) -> BlockT * {
52 assert(!AllowRepeats &&
"Unexpected parameter value.");
54 return any_of(children<BlockT *>(BB), notInLoop) ? BB :
nullptr;
63template <
class BlockT,
class LoopT>
66 assert(!isInvalid() &&
"Loop not in a valid state!");
67 for (
const auto BB :
blocks())
68 for (
auto *Succ : children<BlockT *>(BB))
76template <
class BlockT,
class LoopT>
79 assert(!L->isInvalid() &&
"Loop not in a valid state!");
80 auto notInLoop = [&](BlockT *BB,
81 bool AllowRepeats) -> std::pair<BlockT *, bool> {
82 assert(AllowRepeats == Unique &&
"Unexpected parameter value.");
83 return {!L->contains(BB) ? BB :
nullptr,
false};
85 auto singleExitBlock = [&](BlockT *BB,
86 bool AllowRepeats) -> std::pair<BlockT *, bool> {
87 assert(AllowRepeats == Unique &&
"Unexpected parameter value.");
88 return find_singleton_nested<BlockT>(children<BlockT *>(BB), notInLoop,
91 return find_singleton_nested<BlockT>(L->blocks(), singleExitBlock, Unique);
94template <
class BlockT,
class LoopT>
106template <
class BlockT,
class LoopT>
111template <
class BlockT,
class LoopT>
116 getUniqueExitBlocks(UniqueExitBlocks);
117 for (BlockT *EB : UniqueExitBlocks)
127template <
class BlockT,
class LoopT,
typename PredicateT>
131 assert(!L->isInvalid() &&
"Loop not in a valid state!");
134 for (BlockT *BB : Filtered)
135 for (BlockT *
Successor : children<BlockT *>(BB))
141template <
class BlockT,
class LoopT>
145 [](
const BlockT *BB) {
return true; });
148template <
class BlockT,
class LoopT>
151 const BlockT *Latch = getLoopLatch();
152 assert(Latch &&
"Latch block must exists");
154 [Latch](
const BlockT *BB) {
return BB != Latch; });
157template <
class BlockT,
class LoopT>
163template <
class BlockT,
class LoopT>
166 assert(!isInvalid() &&
"Loop not in a valid state!");
167 for (
const auto BB :
blocks())
168 for (
auto *Succ : children<BlockT *>(BB))
175template <
class BlockT>
178template <
class BlockT>
185 return Block->isLegalToHoistInto();
198template <
class BlockT,
class LoopT>
200 assert(!isInvalid() &&
"Loop not in a valid state!");
202 BlockT *Out = getLoopPredecessor();
212 typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
214 if (SI != BlockTraits::child_end(Out))
226template <
class BlockT,
class LoopT>
228 assert(!isInvalid() &&
"Loop not in a valid state!");
230 BlockT *Out =
nullptr;
233 BlockT *Header = getHeader();
236 if (Out && Out != Pred)
247template <
class BlockT,
class LoopT>
249 assert(!isInvalid() &&
"Loop not in a valid state!");
250 BlockT *Header = getHeader();
251 BlockT *Latch =
nullptr;
273template <
class BlockT,
class LoopT>
276 assert(!isInvalid() &&
"Loop not in a valid state!");
279 auto SameHeader = LIB[getHeader()];
280 assert(
contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
281 "Incorrect LI specified for this loop!");
284 assert(NewBB &&
"Cannot add a null basic block to the loop!");
285 assert(!LIB[NewBB] &&
"BasicBlock already in the loop!");
287 LoopT *L =
static_cast<LoopT *
>(
this);
290 LIB.BBMap[NewBB] = L;
294 L->addBlockEntry(NewBB);
295 L = L->getParentLoop();
303template <
class BlockT,
class LoopT>
306 assert(!isInvalid() &&
"Loop not in a valid state!");
307 assert(OldChild->ParentLoop ==
this &&
"This loop is already broken!");
308 assert(!NewChild->ParentLoop &&
"NewChild already has a parent!");
309 typename std::vector<LoopT *>::iterator
I =
find(SubLoops, OldChild);
310 assert(
I != SubLoops.end() &&
"OldChild not in loop!");
312 OldChild->ParentLoop =
nullptr;
313 NewChild->ParentLoop =
static_cast<LoopT *
>(
this);
317template <
class BlockT,
class LoopT>
319 assert(!isInvalid() &&
"Loop not in a valid state!");
325 getExitBlocks(ExitBBs);
337 "Loop block has no in-loop successors!");
342 "Loop block has no in-loop predecessors!");
351 if (BB == getHeader()) {
352 assert(!OutsideLoopPreds.
empty() &&
"Loop is unreachable!");
353 }
else if (!OutsideLoopPreds.
empty()) {
357 BlockT *EntryBB = &BB->getParent()->front();
359 for (
unsigned i = 0, e = OutsideLoopPreds.
size(); i != e; ++i)
360 assert(CB != OutsideLoopPreds[i] &&
361 "Loop has multiple entry points!");
364 "Loop contains function entry block!");
369 if (VisitedBBs.
size() != getNumBlocks()) {
370 dbgs() <<
"The following blocks are unreachable in the loop: ";
372 if (!VisitedBBs.
count(BB)) {
373 dbgs() << *BB <<
"\n";
376 assert(
false &&
"Unreachable block in loop");
382 for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
385 "Loop does not contain all the blocks of a subloop!");
391 "Loop is not a subloop of its parent!");
397template <
class BlockT,
class LoopT>
400 assert(!isInvalid() &&
"Loop not in a valid state!");
401 Loops->insert(
static_cast<const LoopT *
>(
this));
406 (*I)->verifyLoopNest(
Loops);
409template <
class BlockT,
class LoopT>
411 bool PrintNested,
unsigned Depth)
const {
413 if (
static_cast<const LoopT *
>(
this)->isAnnotatedParallel())
415 OS <<
"Loop at depth " << getLoopDepth() <<
" containing: ";
417 BlockT *
H = getHeader();
418 for (
unsigned i = 0; i < getBlocks().size(); ++i) {
419 BlockT *BB = getBlocks()[i];
423 BB->printAsOperand(
OS,
false);
431 if (isLoopExiting(BB))
441 (*I)->print(
OS,
false, PrintNested,
Depth + 2);
453template <
class BlockT,
class LoopT>
459 unsigned NumBlocks = 0;
460 unsigned NumSubloops = 0;
463 std::vector<BlockT *> ReverseCFGWorklist(Backedges.
begin(), Backedges.
end());
464 while (!ReverseCFGWorklist.empty()) {
465 BlockT *PredBB = ReverseCFGWorklist.back();
466 ReverseCFGWorklist.pop_back();
476 if (PredBB == L->getHeader())
479 ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
480 InvBlockTraits::child_begin(PredBB),
481 InvBlockTraits::child_end(PredBB));
484 Subloop = Subloop->getOutermostLoop();
491 Subloop->setParentLoop(L);
493 NumBlocks += Subloop->getBlocksVector().capacity();
494 PredBB = Subloop->getHeader();
501 ReverseCFGWorklist.push_back(Pred);
505 L->getSubLoopsVector().reserve(NumSubloops);
506 L->reserveBlocks(NumBlocks);
512 typedef typename BlockTraits::ChildIteratorType SuccIterTy;
526template <
class BlockT,
class LoopT>
535template <
class BlockT,
class LoopT>
538 if (Subloop &&
Block == Subloop->getHeader()) {
541 if (!Subloop->isOutermost())
542 Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
548 Subloop->reverseBlock(1);
549 std::reverse(Subloop->getSubLoopsVector().begin(),
550 Subloop->getSubLoopsVector().end());
552 Subloop = Subloop->getParentLoop();
554 for (; Subloop; Subloop = Subloop->getParentLoop())
555 Subloop->addBlockEntry(
Block);
572template <
class BlockT,
class LoopT>
578 BlockT *Header = DomNode->getBlock();
584 if (DomTree.
dominates(Header, Backedge) &&
590 if (!Backedges.
empty()) {
591 LoopT *L = AllocateLoop(Header);
601template <
class BlockT,
class LoopT>
610 for (LoopT *RootL :
reverse(*
this)) {
611 auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder();
612 PreOrderLoops.
append(PreOrderLoopsInRootL.begin(),
613 PreOrderLoopsInRootL.end());
616 return PreOrderLoops;
619template <
class BlockT,
class LoopT>
620SmallVector<LoopT *, 4>
628 for (LoopT *RootL : *
this) {
630 "Must start with an empty preorder walk worklist.");
636 PreOrderWorklist.
append(L->begin(), L->end());
638 }
while (!PreOrderWorklist.
empty());
641 return PreOrderLoops;
645template <
class BlockT,
class LoopT>
647 for (
unsigned i = 0; i < TopLevelLoops.size(); ++i)
651 E = BBMap.end();
I !=
E; ++
I)
652 OS <<
"BB '" <<
I->first->getName() <<
"' level = "
653 <<
I->second->getLoopDepth() <<
"\n";
664template <
class BlockT,
class LoopT>
668 LoopHeaders[L.getHeader()] = &L;
674template <
class BlockT,
class LoopT>
677 BlockT *
H = L->getHeader();
678 BlockT *OtherH = OtherL->getHeader();
680 "Mismatched headers even though found in the same map entry!");
682 assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
683 "Mismatched loop depth!");
684 const LoopT *ParentL = L, *OtherParentL = OtherL;
686 assert(ParentL->getHeader() == OtherParentL->getHeader() &&
687 "Mismatched parent loop headers!");
688 ParentL = ParentL->getParentLoop();
689 OtherParentL = OtherParentL->getParentLoop();
692 for (
const LoopT *SubL : *L) {
693 BlockT *SubH = SubL->getHeader();
694 const LoopT *OtherSubL = OtherLoopHeaders.
lookup(SubH);
695 assert(OtherSubL &&
"Inner loop is missing in computed loop info!");
696 OtherLoopHeaders.
erase(SubH);
700 std::vector<BlockT *> BBs = L->getBlocks();
701 std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
703 "Mismatched basic blocks in the loops!");
707 OtherL->getBlocksSet();
710 "Mismatched basic blocks in BlocksSets!");
714template <
class BlockT,
class LoopT>
719 assert((*I)->isOutermost() &&
"Top-level loop has a parent!");
720 (*I)->verifyLoopNest(&
Loops);
725 for (
auto &Entry : BBMap) {
726 const BlockT *BB = Entry.first;
727 LoopT *L = Entry.second;
729 assert(L->contains(BB) &&
"orphaned block");
730 for (LoopT *ChildLoop : *L)
731 assert(!ChildLoop->contains(BB) &&
732 "BBMap should point to the innermost loop containing BB");
743 for (LoopT *L : OtherLI)
749 for (LoopT *L : *
this) {
750 BlockT *Header = L->getHeader();
751 const LoopT *OtherL = OtherLoopHeaders.
lookup(Header);
752 assert(OtherL &&
"Top level loop is missing in computed loop info!");
754 OtherLoopHeaders.
erase(Header);
761 if (!OtherLoopHeaders.
empty()) {
762 for (
const auto &HeaderAndLoop : OtherLoopHeaders)
763 dbgs() <<
"Found new loop: " << *HeaderAndLoop.second <<
"\n";
static const Function * getParent(const Value *V)
bbsections Prepares for basic block by splitting functions into clusters of basic blocks
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
DenseMap< Block *, BlockRelaxAux > Blocks
static bool isExitBlock(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &ExitBlocks)
Return true if the specified block is in the list.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines generic set operations that may be used on set's of different types,...
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
bool erase(const KeyT &Val)
Implements a dense probed hash-table based set.
Base class for the actual dominator tree node.
Core dominator tree base class.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
bool isReachableFromEntry(const NodeT *A) const
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
Instances of this class are used to represent loops that are detected in the flow graph.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
void verifyLoop() const
Verify loop structure.
void verifyLoopNest(DenseSet< const LoopT * > *Loops) const
Verify loop structure of this loop and all nested loops.
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
void print(raw_ostream &OS, bool Verbose=false, bool PrintNested=true, unsigned Depth=0) const
Print loop with all the BBs inside it.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
std::vector< LoopT * >::const_iterator iterator
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
bool hasNoExitBlocks() const
Return true if this loop does not have any exit blocks.
void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild)
This is used when splitting loops up.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
void getUniqueNonLatchExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop except successors from Latch block are not considered...
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
This class builds and contains all of the top-level loop structures in the specified function.
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
SmallVector< LoopT *, 4 > getLoopsInReverseSiblingPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in reverse p...
void print(raw_ostream &OS) const
SmallVector< LoopT *, 4 > getLoopsInPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
std::vector< LoopT * >::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Populate all loop data in a stable order during a single forward DFS.
void traverse(BlockT *EntryBlock)
Top-level driver for the forward DFS within the loop.
PopulateLoopsDFS(LoopInfoBase< BlockT, LoopT > *li)
void insertIntoLoop(BlockT *Block)
Add a single Block to its ancestor loops in PostOrder.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
decltype(&BlockT::isLegalToHoistInto) has_hoist_check
llvm::is_detected< has_hoist_check, BlockT > detect_has_hoist_check
bool isLegalToHoistInto(BlockT *Block)
SFINAE functions that dispatch to the isLegalToHoistInto member function or return false,...
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
static void compareLoops(const LoopT *L, const LoopT *OtherL, DenseMap< BlockT *, const LoopT * > &OtherLoopHeaders)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
iterator_range< po_iterator< T > > post_order(const T &G)
typename detail::detector< void, Op, Args... >::value_t is_detected
Detects if a given trait holds for some set of arguments 'Args'.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
auto reverse(ContainerTy &&C)
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
std::pair< BlockT *, bool > getExitBlockHelper(const LoopBase< BlockT, LoopT > *L, bool Unique)
getExitBlock - If getExitBlocks would return exactly one block, return that block.
void addInnerLoopsToHeadersMap(DenseMap< BlockT *, const LoopT * > &LoopHeaders, const LoopInfoBase< BlockT, LoopT > &LI, const LoopT &L)
void getUniqueExitBlocksHelper(const LoopT *L, SmallVectorImpl< BlockT * > &ExitBlocks, PredicateT Pred)
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool compareVectors(std::vector< T > &BB1, std::vector< T > &BB2)
iterator_range< df_iterator< T > > depth_first(const T &G)
static void discoverAndMapSubloop(LoopT *L, ArrayRef< BlockT * > Backedges, LoopInfoBase< BlockT, LoopT > *LI, const DomTreeBase< BlockT > &DomTree)
Stable LoopInfo Analysis - Build a loop tree using stable iterators so the result does / not depend o...
std::pair< iterator, bool > insert(NodeRef N)