Go to the documentation of this file.
14 #ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H
15 #define LLVM_ANALYSIS_LOOPINFOIMPL_H
32 template <
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))
40 ExitingBlocks.push_back(
BB);
47 template <
class BlockT,
class LoopT>
49 assert(!isInvalid() &&
"Loop not in a valid state!");
51 getExitingBlocks(ExitingBlocks);
52 if (ExitingBlocks.size() == 1)
53 return ExitingBlocks[0];
60 template <
class BlockT,
class LoopT>
63 assert(!isInvalid() &&
"Loop not in a valid state!");
64 for (
const auto BB : blocks())
65 for (
auto *Succ : children<BlockT *>(
BB))
68 ExitBlocks.push_back(Succ);
71 template <
class BlockT,
class LoopT>
74 getExitBlocks(ExitBlocks);
75 return ExitBlocks.empty();
80 template <
class BlockT,
class LoopT>
82 assert(!isInvalid() &&
"Loop not in a valid state!");
84 getExitBlocks(ExitBlocks);
85 if (ExitBlocks.size() == 1)
90 template <
class BlockT,
class LoopT>
95 getUniqueExitBlocks(UniqueExitBlocks);
96 for (BlockT *EB : UniqueExitBlocks)
106 template <
class BlockT,
class LoopT,
typename PredicateT>
110 assert(!L->isInvalid() &&
"Loop not in a valid state!");
113 for (BlockT *
BB : Filtered)
120 template <
class BlockT,
class LoopT>
124 [](
const BlockT *
BB) {
return true; });
127 template <
class BlockT,
class LoopT>
130 const BlockT *Latch = getLoopLatch();
131 assert(Latch &&
"Latch block must exists");
133 [Latch](
const BlockT *
BB) {
return BB != Latch; });
136 template <
class BlockT,
class LoopT>
139 getUniqueExitBlocks(UniqueExitBlocks);
140 if (UniqueExitBlocks.size() == 1)
141 return UniqueExitBlocks[0];
146 template <
class BlockT,
class LoopT>
149 assert(!isInvalid() &&
"Loop not in a valid state!");
150 for (
const auto BB : blocks())
151 for (
auto *Succ : children<BlockT *>(
BB))
165 template <
class BlockT,
class LoopT>
167 assert(!isInvalid() &&
"Loop not in a valid state!");
169 BlockT *Out = getLoopPredecessor();
174 if (!Out->isLegalToHoistInto())
179 typename BlockTraits::ChildIteratorType
SI = BlockTraits::child_begin(Out);
181 if (
SI != BlockTraits::child_end(Out))
193 template <
class BlockT,
class LoopT>
195 assert(!isInvalid() &&
"Loop not in a valid state!");
197 BlockT *Out =
nullptr;
200 BlockT *Header = getHeader();
203 if (Out && Out != Pred)
214 template <
class BlockT,
class LoopT>
216 assert(!isInvalid() &&
"Loop not in a valid state!");
217 BlockT *Header = getHeader();
218 BlockT *Latch =
nullptr;
240 template <
class BlockT,
class LoopT>
243 assert(!isInvalid() &&
"Loop not in a valid state!");
245 if (!Blocks.empty()) {
246 auto SameHeader = LIB[getHeader()];
247 assert(
contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
248 "Incorrect LI specified for this loop!");
251 assert(NewBB &&
"Cannot add a null basic block to the loop!");
252 assert(!LIB[NewBB] &&
"BasicBlock already in the loop!");
254 LoopT *L =
static_cast<LoopT *
>(
this);
257 LIB.BBMap[NewBB] = L;
261 L->addBlockEntry(NewBB);
262 L = L->getParentLoop();
270 template <
class BlockT,
class LoopT>
273 assert(!isInvalid() &&
"Loop not in a valid state!");
274 assert(OldChild->ParentLoop ==
this &&
"This loop is already broken!");
275 assert(!NewChild->ParentLoop &&
"NewChild already has a parent!");
276 typename std::vector<LoopT *>::iterator
I =
find(SubLoops, OldChild);
277 assert(
I != SubLoops.end() &&
"OldChild not in loop!");
279 OldChild->ParentLoop =
nullptr;
280 NewChild->ParentLoop =
static_cast<LoopT *
>(
this);
284 template <
class BlockT,
class LoopT>
286 assert(!isInvalid() &&
"Loop not in a valid state!");
288 assert(!Blocks.empty() &&
"Loop header is missing");
292 getExitBlocks(ExitBBs);
294 VisitSet.
insert(ExitBBs.begin(), ExitBBs.end());
303 for (; BI != BE; ++BI) {
309 "Loop block has no in-loop successors!");
314 "Loop block has no in-loop predecessors!");
321 OutsideLoopPreds.push_back(
B);
323 if (
BB == getHeader()) {
324 assert(!OutsideLoopPreds.empty() &&
"Loop is unreachable!");
325 }
else if (!OutsideLoopPreds.empty()) {
329 BlockT *EntryBB = &
BB->getParent()->front();
331 for (
unsigned i = 0,
e = OutsideLoopPreds.size();
i !=
e; ++
i)
332 assert(CB != OutsideLoopPreds[
i] &&
333 "Loop has multiple entry points!");
336 "Loop contains function entry block!");
341 if (VisitedBBs.
size() != getNumBlocks()) {
342 dbgs() <<
"The following blocks are unreachable in the loop: ";
343 for (
auto BB : Blocks) {
348 assert(
false &&
"Unreachable block in loop");
354 for (
block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
357 "Loop does not contain all the blocks of a subloop!");
363 "Loop is not a subloop of its parent!");
369 template <
class BlockT,
class LoopT>
372 assert(!isInvalid() &&
"Loop not in a valid state!");
373 Loops->insert(
static_cast<const LoopT *
>(
this));
378 (*I)->verifyLoopNest(
Loops);
381 template <
class BlockT,
class LoopT>
383 bool PrintNested,
unsigned Depth)
const {
385 if (
static_cast<const LoopT *
>(
this)->isAnnotatedParallel())
387 OS <<
"Loop at depth " << getLoopDepth() <<
" containing: ";
389 BlockT *
H = getHeader();
390 for (
unsigned i = 0;
i < getBlocks().size(); ++
i) {
391 BlockT *
BB = getBlocks()[
i];
395 BB->printAsOperand(OS,
false);
403 if (isLoopExiting(
BB))
413 (*I)->print(OS,
false, PrintNested,
Depth + 2);
425 template <
class BlockT,
class LoopT>
431 unsigned NumBlocks = 0;
432 unsigned NumSubloops = 0;
435 std::vector<BlockT *> ReverseCFGWorklist(Backedges.
begin(), Backedges.
end());
436 while (!ReverseCFGWorklist.empty()) {
437 BlockT *PredBB = ReverseCFGWorklist.back();
438 ReverseCFGWorklist.pop_back();
448 if (PredBB == L->getHeader())
451 ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
452 InvBlockTraits::child_begin(PredBB),
453 InvBlockTraits::child_end(PredBB));
456 Subloop = Subloop->getOutermostLoop();
463 Subloop->setParentLoop(L);
465 NumBlocks += Subloop->getBlocksVector().capacity();
466 PredBB = Subloop->getHeader();
473 ReverseCFGWorklist.push_back(Pred);
477 L->getSubLoopsVector().reserve(NumSubloops);
478 L->reserveBlocks(NumBlocks);
484 typedef typename BlockTraits::ChildIteratorType SuccIterTy;
498 template <
class BlockT,
class LoopT>
507 template <
class BlockT,
class LoopT>
509 LoopT *Subloop = LI->getLoopFor(Block);
510 if (Subloop && Block == Subloop->getHeader()) {
513 if (!Subloop->isOutermost())
514 Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
516 LI->addTopLevelLoop(Subloop);
520 Subloop->reverseBlock(1);
522 Subloop->getSubLoopsVector().end());
524 Subloop = Subloop->getParentLoop();
526 for (; Subloop; Subloop = Subloop->getParentLoop())
527 Subloop->addBlockEntry(Block);
544 template <
class BlockT,
class LoopT>
550 BlockT *Header = DomNode->getBlock();
556 if (DomTree.
dominates(Header, Backedge) &&
558 Backedges.push_back(Backedge);
562 if (!Backedges.empty()) {
563 LoopT *L = AllocateLoop(Header);
573 template <
class BlockT,
class LoopT>
582 for (LoopT *RootL :
reverse(*
this)) {
583 auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder();
584 PreOrderLoops.
append(PreOrderLoopsInRootL.begin(),
585 PreOrderLoopsInRootL.end());
588 return PreOrderLoops;
591 template <
class BlockT,
class LoopT>
600 for (LoopT *RootL : *
this) {
601 assert(PreOrderWorklist.empty() &&
602 "Must start with an empty preorder walk worklist.");
603 PreOrderWorklist.push_back(RootL);
608 PreOrderWorklist.
append(L->begin(), L->end());
609 PreOrderLoops.push_back(L);
610 }
while (!PreOrderWorklist.empty());
613 return PreOrderLoops;
617 template <
class BlockT,
class LoopT>
619 for (
unsigned i = 0;
i < TopLevelLoops.size(); ++
i)
620 TopLevelLoops[
i]->
print(OS);
623 E = BBMap.end();
I !=
E; ++
I)
624 OS <<
"BB '" <<
I->first->getName() <<
"' level = "
625 <<
I->second->getLoopDepth() <<
"\n";
629 template <
typename T>
636 template <
class BlockT,
class LoopT>
640 LoopHeaders[L.getHeader()] = &L;
646 template <
class BlockT,
class LoopT>
649 BlockT *
H = L->getHeader();
650 BlockT *OtherH = OtherL->getHeader();
652 "Mismatched headers even though found in the same map entry!");
654 assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
655 "Mismatched loop depth!");
656 const LoopT *ParentL = L, *OtherParentL = OtherL;
658 assert(ParentL->getHeader() == OtherParentL->getHeader() &&
659 "Mismatched parent loop headers!");
660 ParentL = ParentL->getParentLoop();
661 OtherParentL = OtherParentL->getParentLoop();
664 for (
const LoopT *SubL : *L) {
665 BlockT *SubH = SubL->getHeader();
666 const LoopT *OtherSubL = OtherLoopHeaders.
lookup(SubH);
667 assert(OtherSubL &&
"Inner loop is missing in computed loop info!");
668 OtherLoopHeaders.
erase(SubH);
672 std::vector<BlockT *> BBs = L->getBlocks();
673 std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
675 "Mismatched basic blocks in the loops!");
679 OtherL->getBlocksSet();
682 "Mismatched basic blocks in BlocksSets!");
686 template <
class BlockT,
class LoopT>
691 assert((*I)->isOutermost() &&
"Top-level loop has a parent!");
692 (*I)->verifyLoopNest(&
Loops);
697 for (
auto &Entry : BBMap) {
698 const BlockT *
BB = Entry.first;
699 LoopT *L = Entry.second;
701 assert(L->contains(
BB) &&
"orphaned block");
702 for (LoopT *ChildLoop : *L)
704 "BBMap should point to the innermost loop containing BB");
715 for (LoopT *L : OtherLI)
721 for (LoopT *L : *
this) {
722 BlockT *Header = L->getHeader();
723 const LoopT *OtherL = OtherLoopHeaders.
lookup(Header);
724 assert(OtherL &&
"Top level loop is missing in computed loop info!");
726 OtherLoopHeaders.
erase(Header);
733 if (!OtherLoopHeaders.
empty()) {
734 for (
const auto &HeaderAndLoop : OtherLoopHeaders)
735 dbgs() <<
"Found new loop: " << *HeaderAndLoop.second <<
"\n";
This is an optimization pass for GlobalISel generic memory operations.
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool isReachableFromEntry(const NodeT *A) const
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
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...
return AArch64::GPR64RegClass contains(Reg)
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
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...
Populate all loop data in a stable order during a single forward DFS.
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
void print(raw_ostream &OS) const
bool erase(const KeyT &Val)
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
const_iterator end(StringRef path)
Get end iterator over path.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
PopulateLoopsDFS(LoopInfoBase< BlockT, LoopT > *li)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
LLVM_NODISCARD T pop_back_val()
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
df_ext_iterator< T, SetTy > df_ext_begin(const T &G, SetTy &S)
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void verifyLoop() const
Verify loop structure.
This class implements an extremely fast bulk output stream that can only output to a stream.
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
bool compareVectors(std::vector< T > &BB1, std::vector< T > &BB2)
void verifyLoopNest(DenseSet< const LoopT * > *Loops) const
Verify loop structure of this loop and all nested loops.
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Implements a dense probed hash-table based set.
ArrayRef< BasicBlock * >::const_iterator block_iterator
void traverse(BlockT *EntryBlock)
Top-level driver for the forward DFS within the loop.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StandardInstrumentations SI(Debug, VerifyEach)
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
std::pair< iterator, bool > insert(NodeRef N)
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void getUniqueExitBlocksHelper(const LoopT *L, SmallVectorImpl< BlockT * > &ExitBlocks, PredicateT Pred)
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static const Function * getParent(const Value *V)
void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild)
This is used when splitting loops up.
Core dominator tree base class.
Base class for the actual dominator tree node.
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
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...
void getUniqueNonLatchExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop except successors from Latch block are not considered...
df_ext_iterator< T, SetTy > df_ext_end(const T &G, SetTy &S)
LLVM_NODISCARD bool empty() const
iterator_range< df_iterator< T > > depth_first(const T &G)
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 addInnerLoopsToHeadersMap(DenseMap< BlockT *, const LoopT * > &LoopHeaders, const LoopInfoBase< BlockT, LoopT > &LI, const LoopT &L)
static void compareLoops(const LoopT *L, const LoopT *OtherL, DenseMap< BlockT *, const LoopT * > &OtherLoopHeaders)
This class builds and contains all of the top-level loop structures in the specified function.
iterator_range< po_iterator< T > > post_order(const T &G)
void sort(IteratorTy Start, IteratorTy End)
bool hasNoExitBlocks() const
Return true if this loop does not have any exit blocks.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
std::vector< Loop * >::const_iterator iterator
std::vector< Loop * >::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
void print(raw_ostream &OS, bool Verbose=false, bool PrintNested=true, unsigned Depth=0) const
Print loop with all the BBs inside it.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
void insertIntoLoop(BlockT *Block)
Add a single Block to its ancestor loops in PostOrder.
SmallVector< LoopT *, 4 > getLoopsInReverseSiblingPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in reverse p...
reference emplace_back(ArgTypes &&... Args)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.