14#ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H
15#define LLVM_ANALYSIS_LOOPINFOIMPL_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;
57 return find_singleton<BlockT>(blocks(),
isExitBlock);
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>
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))
182template <
class BlockT,
class LoopT>
184 assert(!isInvalid() &&
"Loop not in a valid state!");
186 BlockT *Out = getLoopPredecessor();
191 if (!Out->isLegalToHoistInto())
196 typename BlockTraits::ChildIteratorType
SI = BlockTraits::child_begin(Out);
198 if (
SI != BlockTraits::child_end(Out))
210template <
class BlockT,
class LoopT>
212 assert(!isInvalid() &&
"Loop not in a valid state!");
214 BlockT *Out =
nullptr;
217 BlockT *Header = getHeader();
220 if (Out && Out != Pred)
231template <
class BlockT,
class LoopT>
233 assert(!isInvalid() &&
"Loop not in a valid state!");
234 BlockT *Header = getHeader();
235 BlockT *Latch =
nullptr;
257template <
class BlockT,
class LoopT>
260 assert(!isInvalid() &&
"Loop not in a valid state!");
262 if (!Blocks.empty()) {
263 auto SameHeader = LIB[getHeader()];
264 assert(
contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
265 "Incorrect LI specified for this loop!");
268 assert(NewBB &&
"Cannot add a null basic block to the loop!");
269 assert(!LIB[NewBB] &&
"BasicBlock already in the loop!");
271 LoopT *L =
static_cast<LoopT *
>(
this);
274 LIB.BBMap[NewBB] = L;
278 L->addBlockEntry(NewBB);
279 L = L->getParentLoop();
287template <
class BlockT,
class LoopT>
290 assert(!isInvalid() &&
"Loop not in a valid state!");
291 assert(OldChild->ParentLoop ==
this &&
"This loop is already broken!");
292 assert(!NewChild->ParentLoop &&
"NewChild already has a parent!");
293 typename std::vector<LoopT *>::iterator
I =
find(SubLoops, OldChild);
294 assert(
I != SubLoops.end() &&
"OldChild not in loop!");
296 OldChild->ParentLoop =
nullptr;
297 NewChild->ParentLoop =
static_cast<LoopT *
>(
this);
301template <
class BlockT,
class LoopT>
303 assert(!isInvalid() &&
"Loop not in a valid state!");
305 assert(!Blocks.empty() &&
"Loop header is missing");
309 getExitBlocks(ExitBBs);
321 "Loop block has no in-loop successors!");
326 "Loop block has no in-loop predecessors!");
335 if (BB == getHeader()) {
336 assert(!OutsideLoopPreds.
empty() &&
"Loop is unreachable!");
337 }
else if (!OutsideLoopPreds.
empty()) {
341 BlockT *EntryBB = &BB->getParent()->front();
343 for (
unsigned i = 0, e = OutsideLoopPreds.
size(); i != e; ++i)
344 assert(CB != OutsideLoopPreds[i] &&
345 "Loop has multiple entry points!");
348 "Loop contains function entry block!");
353 if (VisitedBBs.
size() != getNumBlocks()) {
354 dbgs() <<
"The following blocks are unreachable in the loop: ";
355 for (
auto *BB : Blocks) {
356 if (!VisitedBBs.
count(BB)) {
357 dbgs() << *BB <<
"\n";
360 assert(
false &&
"Unreachable block in loop");
366 for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
369 "Loop does not contain all the blocks of a subloop!");
375 "Loop is not a subloop of its parent!");
381template <
class BlockT,
class LoopT>
384 assert(!isInvalid() &&
"Loop not in a valid state!");
385 Loops->insert(
static_cast<const LoopT *
>(
this));
390 (*I)->verifyLoopNest(
Loops);
393template <
class BlockT,
class LoopT>
395 bool PrintNested,
unsigned Depth)
const {
397 if (
static_cast<const LoopT *
>(
this)->isAnnotatedParallel())
399 OS <<
"Loop at depth " << getLoopDepth() <<
" containing: ";
401 BlockT *
H = getHeader();
402 for (
unsigned i = 0; i < getBlocks().size(); ++i) {
403 BlockT *BB = getBlocks()[i];
407 BB->printAsOperand(OS,
false);
415 if (isLoopExiting(BB))
424 for (iterator
I = begin(),
E = end();
I !=
E; ++
I)
425 (*I)->print(OS,
false, PrintNested,
Depth + 2);
437template <
class BlockT,
class LoopT>
443 unsigned NumBlocks = 0;
444 unsigned NumSubloops = 0;
447 std::vector<BlockT *> ReverseCFGWorklist(Backedges.
begin(), Backedges.
end());
448 while (!ReverseCFGWorklist.empty()) {
449 BlockT *PredBB = ReverseCFGWorklist.back();
450 ReverseCFGWorklist.pop_back();
460 if (PredBB == L->getHeader())
463 ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
464 InvBlockTraits::child_begin(PredBB),
465 InvBlockTraits::child_end(PredBB));
468 Subloop = Subloop->getOutermostLoop();
475 Subloop->setParentLoop(L);
477 NumBlocks += Subloop->getBlocksVector().capacity();
478 PredBB = Subloop->getHeader();
485 ReverseCFGWorklist.push_back(Pred);
489 L->getSubLoopsVector().reserve(NumSubloops);
490 L->reserveBlocks(NumBlocks);
496 typedef typename BlockTraits::ChildIteratorType SuccIterTy;
510template <
class BlockT,
class LoopT>
519template <
class BlockT,
class LoopT>
522 if (Subloop &&
Block == Subloop->getHeader()) {
525 if (!Subloop->isOutermost())
526 Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
532 Subloop->reverseBlock(1);
533 std::reverse(Subloop->getSubLoopsVector().begin(),
534 Subloop->getSubLoopsVector().end());
536 Subloop = Subloop->getParentLoop();
538 for (; Subloop; Subloop = Subloop->getParentLoop())
539 Subloop->addBlockEntry(
Block);
556template <
class BlockT,
class LoopT>
562 BlockT *Header = DomNode->getBlock();
568 if (DomTree.
dominates(Header, Backedge) &&
574 if (!Backedges.
empty()) {
575 LoopT *L = AllocateLoop(Header);
585template <
class BlockT,
class LoopT>
594 for (LoopT *RootL :
reverse(*
this)) {
595 auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder();
596 PreOrderLoops.
append(PreOrderLoopsInRootL.begin(),
597 PreOrderLoopsInRootL.end());
600 return PreOrderLoops;
603template <
class BlockT,
class LoopT>
612 for (LoopT *RootL : *
this) {
614 "Must start with an empty preorder walk worklist.");
620 PreOrderWorklist.
append(L->begin(), L->end());
622 }
while (!PreOrderWorklist.
empty());
625 return PreOrderLoops;
629template <
class BlockT,
class LoopT>
631 for (
unsigned i = 0; i < TopLevelLoops.size(); ++i)
632 TopLevelLoops[i]->
print(OS);
635 E = BBMap.end();
I !=
E; ++
I)
636 OS <<
"BB '" <<
I->first->getName() <<
"' level = "
637 <<
I->second->getLoopDepth() <<
"\n";
648template <
class BlockT,
class LoopT>
652 LoopHeaders[L.getHeader()] = &L;
658template <
class BlockT,
class LoopT>
661 BlockT *
H = L->getHeader();
662 BlockT *OtherH = OtherL->getHeader();
664 "Mismatched headers even though found in the same map entry!");
666 assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
667 "Mismatched loop depth!");
668 const LoopT *ParentL = L, *OtherParentL = OtherL;
670 assert(ParentL->getHeader() == OtherParentL->getHeader() &&
671 "Mismatched parent loop headers!");
672 ParentL = ParentL->getParentLoop();
673 OtherParentL = OtherParentL->getParentLoop();
676 for (
const LoopT *SubL : *L) {
677 BlockT *SubH = SubL->getHeader();
678 const LoopT *OtherSubL = OtherLoopHeaders.
lookup(SubH);
679 assert(OtherSubL &&
"Inner loop is missing in computed loop info!");
680 OtherLoopHeaders.
erase(SubH);
684 std::vector<BlockT *> BBs = L->getBlocks();
685 std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
687 "Mismatched basic blocks in the loops!");
691 OtherL->getBlocksSet();
694 "Mismatched basic blocks in BlocksSets!");
698template <
class BlockT,
class LoopT>
703 assert((*I)->isOutermost() &&
"Top-level loop has a parent!");
704 (*I)->verifyLoopNest(&
Loops);
709 for (
auto &Entry : BBMap) {
710 const BlockT *BB = Entry.first;
711 LoopT *L = Entry.second;
713 assert(L->contains(BB) &&
"orphaned block");
714 for (LoopT *ChildLoop : *L)
715 assert(!ChildLoop->contains(BB) &&
716 "BBMap should point to the innermost loop containing BB");
727 for (LoopT *L : OtherLI)
733 for (LoopT *L : *
this) {
734 BlockT *Header = L->getHeader();
735 const LoopT *OtherL = OtherLoopHeaders.
lookup(Header);
736 assert(OtherL &&
"Top level loop is missing in computed loop info!");
738 OtherLoopHeaders.
erase(Header);
745 if (!OtherLoopHeaders.
empty()) {
746 for (
const auto &HeaderAndLoop : OtherLoopHeaders)
747 dbgs() <<
"Found new loop: " << *HeaderAndLoop.second <<
"\n";
static const Function * getParent(const Value *V)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
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
iterator_range< block_iterator > blocks() const
bool isInvalid() const
Return true if this loop is no longer valid.
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.
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)
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)
Wrapper function around std::find to detect if an element exists in a container.
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)