Go to the documentation of this file.
14 #ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H
15 #define LLVM_ANALYSIS_LOOPINFOIMPL_H
33 template <
class BlockT,
class LoopT>
36 assert(!isInvalid() &&
"Loop not in a valid state!");
37 for (
const auto BB : blocks())
38 for (
auto *Succ : children<BlockT *>(
BB))
41 ExitingBlocks.push_back(
BB);
48 template <
class BlockT,
class LoopT>
50 assert(!isInvalid() &&
"Loop not in a valid state!");
52 getExitingBlocks(ExitingBlocks);
53 if (ExitingBlocks.size() == 1)
54 return ExitingBlocks[0];
61 template <
class BlockT,
class LoopT>
64 assert(!isInvalid() &&
"Loop not in a valid state!");
65 for (
const auto BB : blocks())
66 for (
auto *Succ : children<BlockT *>(
BB))
69 ExitBlocks.push_back(Succ);
72 template <
class BlockT,
class LoopT>
75 getExitBlocks(ExitBlocks);
76 return ExitBlocks.empty();
81 template <
class BlockT,
class LoopT>
83 assert(!isInvalid() &&
"Loop not in a valid state!");
85 getExitBlocks(ExitBlocks);
86 if (ExitBlocks.size() == 1)
91 template <
class BlockT,
class LoopT>
96 getUniqueExitBlocks(UniqueExitBlocks);
97 for (BlockT *EB : UniqueExitBlocks)
107 template <
class BlockT,
class LoopT,
typename PredicateT>
111 assert(!L->isInvalid() &&
"Loop not in a valid state!");
114 for (BlockT *
BB : Filtered)
121 template <
class BlockT,
class LoopT>
125 [](
const BlockT *
BB) {
return true; });
128 template <
class BlockT,
class LoopT>
131 const BlockT *Latch = getLoopLatch();
132 assert(Latch &&
"Latch block must exists");
134 [Latch](
const BlockT *
BB) {
return BB != Latch; });
137 template <
class BlockT,
class LoopT>
140 getUniqueExitBlocks(UniqueExitBlocks);
141 if (UniqueExitBlocks.size() == 1)
142 return UniqueExitBlocks[0];
147 template <
class BlockT,
class LoopT>
150 assert(!isInvalid() &&
"Loop not in a valid state!");
151 for (
const auto BB : blocks())
152 for (
auto *Succ : children<BlockT *>(
BB))
166 template <
class BlockT,
class LoopT>
168 assert(!isInvalid() &&
"Loop not in a valid state!");
170 BlockT *Out = getLoopPredecessor();
175 if (!Out->isLegalToHoistInto())
180 typename BlockTraits::ChildIteratorType
SI = BlockTraits::child_begin(Out);
182 if (
SI != BlockTraits::child_end(Out))
194 template <
class BlockT,
class LoopT>
196 assert(!isInvalid() &&
"Loop not in a valid state!");
198 BlockT *Out =
nullptr;
201 BlockT *Header = getHeader();
204 if (Out && Out != Pred)
215 template <
class BlockT,
class LoopT>
217 assert(!isInvalid() &&
"Loop not in a valid state!");
218 BlockT *Header = getHeader();
219 BlockT *Latch =
nullptr;
241 template <
class BlockT,
class LoopT>
244 assert(!isInvalid() &&
"Loop not in a valid state!");
246 if (!Blocks.empty()) {
247 auto SameHeader = LIB[getHeader()];
248 assert(
contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
249 "Incorrect LI specified for this loop!");
252 assert(NewBB &&
"Cannot add a null basic block to the loop!");
253 assert(!LIB[NewBB] &&
"BasicBlock already in the loop!");
255 LoopT *L =
static_cast<LoopT *
>(
this);
258 LIB.BBMap[NewBB] = L;
262 L->addBlockEntry(NewBB);
263 L = L->getParentLoop();
271 template <
class BlockT,
class LoopT>
274 assert(!isInvalid() &&
"Loop not in a valid state!");
275 assert(OldChild->ParentLoop ==
this &&
"This loop is already broken!");
276 assert(!NewChild->ParentLoop &&
"NewChild already has a parent!");
277 typename std::vector<LoopT *>::iterator
I =
find(SubLoops, OldChild);
278 assert(
I != SubLoops.end() &&
"OldChild not in loop!");
280 OldChild->ParentLoop =
nullptr;
281 NewChild->ParentLoop =
static_cast<LoopT *
>(
this);
285 template <
class BlockT,
class LoopT>
287 assert(!isInvalid() &&
"Loop not in a valid state!");
289 assert(!Blocks.empty() &&
"Loop header is missing");
293 getExitBlocks(ExitBBs);
295 VisitSet.
insert(ExitBBs.begin(), ExitBBs.end());
304 for (; BI != BE; ++BI) {
310 "Loop block has no in-loop successors!");
315 "Loop block has no in-loop predecessors!");
322 OutsideLoopPreds.push_back(
B);
325 if (
BB == getHeader()) {
326 assert(!OutsideLoopPreds.empty() &&
"Loop is unreachable!");
327 }
else if (!OutsideLoopPreds.empty()) {
331 BlockT *EntryBB = &
BB->getParent()->front();
333 for (
unsigned i = 0,
e = OutsideLoopPreds.size();
i !=
e; ++
i)
334 assert(CB != OutsideLoopPreds[
i] &&
335 "Loop has multiple entry points!");
338 "Loop contains function entry block!");
343 if (VisitedBBs.
size() != getNumBlocks()) {
344 dbgs() <<
"The following blocks are unreachable in the loop: ";
345 for (
auto BB : Blocks) {
350 assert(
false &&
"Unreachable block in loop");
356 for (
block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
359 "Loop does not contain all the blocks of a subloop!");
365 "Loop is not a subloop of its parent!");
371 template <
class BlockT,
class LoopT>
374 assert(!isInvalid() &&
"Loop not in a valid state!");
375 Loops->insert(
static_cast<const LoopT *
>(
this));
380 (*I)->verifyLoopNest(
Loops);
383 template <
class BlockT,
class LoopT>
385 bool Verbose)
const {
387 if (
static_cast<const LoopT *
>(
this)->isAnnotatedParallel())
389 OS <<
"Loop at depth " << getLoopDepth() <<
" containing: ";
391 BlockT *
H = getHeader();
392 for (
unsigned i = 0;
i < getBlocks().size(); ++
i) {
393 BlockT *
BB = getBlocks()[
i];
397 BB->printAsOperand(OS,
false);
405 if (isLoopExiting(
BB))
413 (*I)->print(OS,
Depth + 2);
424 template <
class BlockT,
class LoopT>
430 unsigned NumBlocks = 0;
431 unsigned NumSubloops = 0;
434 std::vector<BlockT *> ReverseCFGWorklist(Backedges.
begin(), Backedges.
end());
435 while (!ReverseCFGWorklist.empty()) {
436 BlockT *PredBB = ReverseCFGWorklist.back();
437 ReverseCFGWorklist.pop_back();
447 if (PredBB == L->getHeader())
450 ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
451 InvBlockTraits::child_begin(PredBB),
452 InvBlockTraits::child_end(PredBB));
455 while (LoopT *Parent = Subloop->getParentLoop())
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>
581 for (LoopT *RootL :
reverse(*
this)) {
582 auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder();
583 PreOrderLoops.
append(PreOrderLoopsInRootL.begin(),
584 PreOrderLoopsInRootL.end());
587 return PreOrderLoops;
590 template <
class BlockT,
class LoopT>
599 for (LoopT *RootL : *
this) {
600 assert(PreOrderWorklist.empty() &&
601 "Must start with an empty preorder walk worklist.");
602 PreOrderWorklist.push_back(RootL);
607 PreOrderWorklist.
append(L->begin(), L->end());
608 PreOrderLoops.push_back(L);
609 }
while (!PreOrderWorklist.empty());
612 return PreOrderLoops;
616 template <
class BlockT,
class LoopT>
618 for (
unsigned i = 0;
i < TopLevelLoops.size(); ++
i)
619 TopLevelLoops[
i]->
print(OS);
622 E = BBMap.end();
I !=
E; ++
I)
623 OS <<
"BB '" <<
I->first->getName() <<
"' level = "
624 <<
I->second->getLoopDepth() <<
"\n";
628 template <
typename T>
635 template <
class BlockT,
class LoopT>
639 LoopHeaders[L.getHeader()] = &L;
645 template <
class BlockT,
class LoopT>
648 BlockT *
H = L->getHeader();
649 BlockT *OtherH = OtherL->getHeader();
651 "Mismatched headers even though found in the same map entry!");
653 assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
654 "Mismatched loop depth!");
655 const LoopT *ParentL = L, *OtherParentL = OtherL;
657 assert(ParentL->getHeader() == OtherParentL->getHeader() &&
658 "Mismatched parent loop headers!");
659 ParentL = ParentL->getParentLoop();
660 OtherParentL = OtherParentL->getParentLoop();
663 for (
const LoopT *SubL : *L) {
664 BlockT *SubH = SubL->getHeader();
665 const LoopT *OtherSubL = OtherLoopHeaders.
lookup(SubH);
666 assert(OtherSubL &&
"Inner loop is missing in computed loop info!");
667 OtherLoopHeaders.
erase(SubH);
671 std::vector<BlockT *> BBs = L->getBlocks();
672 std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
674 "Mismatched basic blocks in the loops!");
678 OtherL->getBlocksSet();
681 "Mismatched basic blocks in BlocksSets!");
685 template <
class BlockT,
class LoopT>
690 assert((*I)->isOutermost() &&
"Top-level loop has a parent!");
691 (*I)->verifyLoopNest(&
Loops);
696 for (
auto &Entry : BBMap) {
697 const BlockT *
BB = Entry.first;
698 LoopT *L = Entry.second;
700 assert(L->contains(
BB) &&
"orphaned block");
701 for (LoopT *ChildLoop : *L)
703 "BBMap should point to the innermost loop containing BB");
714 for (LoopT *L : OtherLI)
720 for (LoopT *L : *
this) {
721 BlockT *Header = L->getHeader();
722 const LoopT *OtherL = OtherLoopHeaders.
lookup(Header);
723 assert(OtherL &&
"Top level loop is missing in computed loop info!");
725 OtherLoopHeaders.
erase(Header);
732 if (!OtherLoopHeaders.
empty()) {
733 for (
const auto &HeaderAndLoop : OtherLoopHeaders)
734 dbgs() <<
"Found new loop: " << *HeaderAndLoop.second <<
"\n";
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
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)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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)
SmallVector< LoopT *, 4 > getLoopsInPreorder()
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
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.
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
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())
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),...
void print(raw_ostream &OS, unsigned Depth=0, bool Verbose=false) const
Print loop with all the BBs inside it.
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)
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)
SmallVector< LoopT *, 4 > getLoopsInReverseSiblingPreorder()
Return all of the loops in the function in preorder across the loop nests, with siblings in reverse p...
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.
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.
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.