LLVM 18.0.0git
GenericLoopInfoImpl.h
Go to the documentation of this file.
1//===- GenericLoopInfoImp.h - Generic Loop Info Implementation --*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This fle contains the implementation of GenericLoopInfo. It should only be
10// included in files that explicitly instantiate a GenericLoopInfo.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_SUPPORT_GENERICLOOPINFOIMPL_H
15#define LLVM_SUPPORT_GENERICLOOPINFOIMPL_H
16
19#include "llvm/ADT/STLExtras.h"
22
23namespace llvm {
24
25//===----------------------------------------------------------------------===//
26// APIs for simple analysis of the loop. See header notes.
27
28/// getExitingBlocks - Return all blocks inside the loop that have successors
29/// outside of the loop. These are the blocks _inside of the current loop_
30/// which branch out. The returned list is always unique.
31///
32template <class BlockT, class LoopT>
34 SmallVectorImpl<BlockT *> &ExitingBlocks) const {
35 assert(!isInvalid() && "Loop not in a valid state!");
36 for (const auto BB : blocks())
37 for (auto *Succ : children<BlockT *>(BB))
38 if (!contains(Succ)) {
39 // Not in current loop? It must be an exit block.
40 ExitingBlocks.push_back(BB);
41 break;
42 }
43}
44
45/// getExitingBlock - If getExitingBlocks would return exactly one block,
46/// return that block. Otherwise return null.
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.");
53 // Child not in current loop? It must be an exit block.
54 return any_of(children<BlockT *>(BB), notInLoop) ? BB : nullptr;
55 };
56
57 return find_singleton<BlockT>(blocks(), isExitBlock);
58}
59
60/// getExitBlocks - Return all of the successor blocks of this loop. These
61/// are the blocks _outside of the current loop_ which are branched to.
62///
63template <class BlockT, class LoopT>
65 SmallVectorImpl<BlockT *> &ExitBlocks) const {
66 assert(!isInvalid() && "Loop not in a valid state!");
67 for (const auto BB : blocks())
68 for (auto *Succ : children<BlockT *>(BB))
69 if (!contains(Succ))
70 // Not in current loop? It must be an exit block.
71 ExitBlocks.push_back(Succ);
72}
73
74/// getExitBlock - If getExitBlocks would return exactly one block,
75/// return that block. Otherwise return null.
76template <class BlockT, class LoopT>
77std::pair<BlockT *, bool> getExitBlockHelper(const LoopBase<BlockT, LoopT> *L,
78 bool Unique) {
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};
84 };
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,
89 AllowRepeats);
90 };
91 return find_singleton_nested<BlockT>(L->blocks(), singleExitBlock, Unique);
92}
93
94template <class BlockT, class LoopT>
96 auto RC = getExitBlockHelper(this, false);
97 if (RC.second)
98 // found multiple exit blocks
99 return false;
100 // return true if there is no exit block
101 return !RC.first;
102}
103
104/// getExitBlock - If getExitBlocks would return exactly one block,
105/// return that block. Otherwise return null.
106template <class BlockT, class LoopT>
108 return getExitBlockHelper(this, false).first;
109}
110
111template <class BlockT, class LoopT>
113 // Each predecessor of each exit block of a normal loop is contained
114 // within the loop.
115 SmallVector<BlockT *, 4> UniqueExitBlocks;
116 getUniqueExitBlocks(UniqueExitBlocks);
117 for (BlockT *EB : UniqueExitBlocks)
118 for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
119 if (!contains(Predecessor))
120 return false;
121 // All the requirements are met.
122 return true;
123}
124
125// Helper function to get unique loop exits. Pred is a predicate pointing to
126// BasicBlocks in a loop which should be considered to find loop exits.
127template <class BlockT, class LoopT, typename PredicateT>
128void getUniqueExitBlocksHelper(const LoopT *L,
129 SmallVectorImpl<BlockT *> &ExitBlocks,
130 PredicateT Pred) {
131 assert(!L->isInvalid() && "Loop not in a valid state!");
133 auto Filtered = make_filter_range(L->blocks(), Pred);
134 for (BlockT *BB : Filtered)
135 for (BlockT *Successor : children<BlockT *>(BB))
136 if (!L->contains(Successor))
137 if (Visited.insert(Successor).second)
138 ExitBlocks.push_back(Successor);
139}
140
141template <class BlockT, class LoopT>
143 SmallVectorImpl<BlockT *> &ExitBlocks) const {
144 getUniqueExitBlocksHelper(this, ExitBlocks,
145 [](const BlockT *BB) { return true; });
146}
147
148template <class BlockT, class LoopT>
150 SmallVectorImpl<BlockT *> &ExitBlocks) const {
151 const BlockT *Latch = getLoopLatch();
152 assert(Latch && "Latch block must exists");
153 getUniqueExitBlocksHelper(this, ExitBlocks,
154 [Latch](const BlockT *BB) { return BB != Latch; });
155}
156
157template <class BlockT, class LoopT>
159 return getExitBlockHelper(this, true).first;
160}
161
162/// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
163template <class BlockT, class LoopT>
165 SmallVectorImpl<Edge> &ExitEdges) const {
166 assert(!isInvalid() && "Loop not in a valid state!");
167 for (const auto BB : blocks())
168 for (auto *Succ : children<BlockT *>(BB))
169 if (!contains(Succ))
170 // Not in current loop? It must be an exit block.
171 ExitEdges.emplace_back(BB, Succ);
172}
173
174namespace detail {
175template <class BlockT>
176using has_hoist_check = decltype(&BlockT::isLegalToHoistInto);
177
178template <class BlockT>
180
181/// SFINAE functions that dispatch to the isLegalToHoistInto member function or
182/// return false, if it doesn't exist.
183template <class BlockT> bool isLegalToHoistInto(BlockT *Block) {
185 return Block->isLegalToHoistInto();
186 return false;
187}
188} // namespace detail
189
190/// getLoopPreheader - If there is a preheader for this loop, return it. A
191/// loop has a preheader if there is only one edge to the header of the loop
192/// from outside of the loop and it is legal to hoist instructions into the
193/// predecessor. If this is the case, the block branching to the header of the
194/// loop is the preheader node.
195///
196/// This method returns null if there is no preheader for the loop.
197///
198template <class BlockT, class LoopT>
200 assert(!isInvalid() && "Loop not in a valid state!");
201 // Keep track of nodes outside the loop branching to the header...
202 BlockT *Out = getLoopPredecessor();
203 if (!Out)
204 return nullptr;
205
206 // Make sure we are allowed to hoist instructions into the predecessor.
208 return nullptr;
209
210 // Make sure there is only one exit out of the preheader.
211 typedef GraphTraits<BlockT *> BlockTraits;
212 typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
213 ++SI;
214 if (SI != BlockTraits::child_end(Out))
215 return nullptr; // Multiple exits from the block, must not be a preheader.
216
217 // The predecessor has exactly one successor, so it is a preheader.
218 return Out;
219}
220
221/// getLoopPredecessor - If the given loop's header has exactly one unique
222/// predecessor outside the loop, return it. Otherwise return null.
223/// This is less strict that the loop "preheader" concept, which requires
224/// the predecessor to have exactly one successor.
225///
226template <class BlockT, class LoopT>
228 assert(!isInvalid() && "Loop not in a valid state!");
229 // Keep track of nodes outside the loop branching to the header...
230 BlockT *Out = nullptr;
231
232 // Loop over the predecessors of the header node...
233 BlockT *Header = getHeader();
234 for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
235 if (!contains(Pred)) { // If the block is not in the loop...
236 if (Out && Out != Pred)
237 return nullptr; // Multiple predecessors outside the loop
238 Out = Pred;
239 }
240 }
241
242 return Out;
243}
244
245/// getLoopLatch - If there is a single latch block for this loop, return it.
246/// A latch block is a block that contains a branch back to the header.
247template <class BlockT, class LoopT>
249 assert(!isInvalid() && "Loop not in a valid state!");
250 BlockT *Header = getHeader();
251 BlockT *Latch = nullptr;
252 for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
253 if (contains(Pred)) {
254 if (Latch)
255 return nullptr;
256 Latch = Pred;
257 }
258 }
259
260 return Latch;
261}
262
263//===----------------------------------------------------------------------===//
264// APIs for updating loop information after changing the CFG
265//
266
267/// addBasicBlockToLoop - This method is used by other analyses to update loop
268/// information. NewBB is set to be a new member of the current loop.
269/// Because of this, it is added as a member of all parent loops, and is added
270/// to the specified LoopInfo object as being in the current basic block. It
271/// is not valid to replace the loop header with this method.
272///
273template <class BlockT, class LoopT>
275 BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
276 assert(!isInvalid() && "Loop not in a valid state!");
277#ifndef NDEBUG
278 if (!Blocks.empty()) {
279 auto SameHeader = LIB[getHeader()];
280 assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
281 "Incorrect LI specified for this loop!");
282 }
283#endif
284 assert(NewBB && "Cannot add a null basic block to the loop!");
285 assert(!LIB[NewBB] && "BasicBlock already in the loop!");
286
287 LoopT *L = static_cast<LoopT *>(this);
288
289 // Add the loop mapping to the LoopInfo object...
290 LIB.BBMap[NewBB] = L;
292 // Add the basic block to this loop and all parent loops...
293 while (L) {
294 L->addBlockEntry(NewBB);
295 L = L->getParentLoop();
296 }
297}
298
299/// replaceChildLoopWith - This is used when splitting loops up. It replaces
300/// the OldChild entry in our children list with NewChild, and updates the
301/// parent pointer of OldChild to be null and the NewChild to be this loop.
302/// This updates the loop depth of the new child.
303template <class BlockT, class LoopT>
305 LoopT *NewChild) {
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!");
311 *I = NewChild;
312 OldChild->ParentLoop = nullptr;
313 NewChild->ParentLoop = static_cast<LoopT *>(this);
315
316/// verifyLoop - Verify loop structure
317template <class BlockT, class LoopT>
319 assert(!isInvalid() && "Loop not in a valid state!");
320#ifndef NDEBUG
321 assert(!Blocks.empty() && "Loop header is missing");
323 // Setup for using a depth-first iterator to visit every block in the loop.
325 getExitBlocks(ExitBBs);
327 VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
329 // Keep track of the BBs visited.
330 SmallPtrSet<BlockT *, 8> VisitedBBs;
331
332 // Check the individual blocks.
333 for (BlockT *BB : depth_first_ext(getHeader(), VisitSet)) {
336 [&](BlockT *B) { return contains(B); }) &&
337 "Loop block has no in-loop successors!");
338
339 assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
340 GraphTraits<Inverse<BlockT *>>::child_end(BB),
341 [&](BlockT *B) { return contains(B); }) &&
342 "Loop block has no in-loop predecessors!");
343
344 SmallVector<BlockT *, 2> OutsideLoopPreds;
345 for (BlockT *B :
347 GraphTraits<Inverse<BlockT *>>::child_end(BB)))
348 if (!contains(B))
349 OutsideLoopPreds.push_back(B);
350
351 if (BB == getHeader()) {
352 assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
353 } else if (!OutsideLoopPreds.empty()) {
354 // A non-header loop shouldn't be reachable from outside the loop,
355 // though it is permitted if the predecessor is not itself actually
356 // reachable.
357 BlockT *EntryBB = &BB->getParent()->front();
358 for (BlockT *CB : depth_first(EntryBB))
359 for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
360 assert(CB != OutsideLoopPreds[i] &&
361 "Loop has multiple entry points!");
362 }
363 assert(BB != &getHeader()->getParent()->front() &&
364 "Loop contains function entry block!");
365
366 VisitedBBs.insert(BB);
367 }
368
369 if (VisitedBBs.size() != getNumBlocks()) {
370 dbgs() << "The following blocks are unreachable in the loop: ";
371 for (auto *BB : Blocks) {
372 if (!VisitedBBs.count(BB)) {
373 dbgs() << *BB << "\n";
374 }
375 }
376 assert(false && "Unreachable block in loop");
377 }
378
379 // Check the subloops.
380 for (iterator I = begin(), E = end(); I != E; ++I)
381 // Each block in each subloop should be contained within this loop.
382 for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
383 BI != BE; ++BI) {
384 assert(contains(*BI) &&
385 "Loop does not contain all the blocks of a subloop!");
386 }
388 // Check the parent loop pointer.
389 if (ParentLoop) {
390 assert(is_contained(ParentLoop->getSubLoops(), this) &&
391 "Loop is not a subloop of its parent!");
392 }
393#endif
394}
395
396/// verifyLoop - Verify loop structure of this loop and all nested loops.
397template <class BlockT, class LoopT>
400 assert(!isInvalid() && "Loop not in a valid state!");
401 Loops->insert(static_cast<const LoopT *>(this));
402 // Verify this loop.
403 verifyLoop();
404 // Verify the subloops.
405 for (iterator I = begin(), E = end(); I != E; ++I)
406 (*I)->verifyLoopNest(Loops);
407}
408
409template <class BlockT, class LoopT>
411 bool PrintNested, unsigned Depth) const {
412 OS.indent(Depth * 2);
413 if (static_cast<const LoopT *>(this)->isAnnotatedParallel())
414 OS << "Parallel ";
415 OS << "Loop at depth " << getLoopDepth() << " containing: ";
416
417 BlockT *H = getHeader();
418 for (unsigned i = 0; i < getBlocks().size(); ++i) {
419 BlockT *BB = getBlocks()[i];
420 if (!Verbose) {
421 if (i)
422 OS << ",";
423 BB->printAsOperand(OS, false);
424 } else
425 OS << "\n";
426
427 if (BB == H)
428 OS << "<header>";
429 if (isLoopLatch(BB))
430 OS << "<latch>";
431 if (isLoopExiting(BB))
432 OS << "<exiting>";
433 if (Verbose)
434 BB->print(OS);
435 }
436
437 if (PrintNested) {
438 OS << "\n";
439
440 for (iterator I = begin(), E = end(); I != E; ++I)
441 (*I)->print(OS, /*Verbose*/ false, PrintNested, Depth + 2);
442 }
443}
444
445//===----------------------------------------------------------------------===//
446/// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
447/// result does / not depend on use list (block predecessor) order.
448///
449
450/// Discover a subloop with the specified backedges such that: All blocks within
451/// this loop are mapped to this loop or a subloop. And all subloops within this
452/// loop have their parent loop set to this loop or a subloop.
453template <class BlockT, class LoopT>
454static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges,
456 const DomTreeBase<BlockT> &DomTree) {
457 typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
458
459 unsigned NumBlocks = 0;
460 unsigned NumSubloops = 0;
461
462 // Perform a backward CFG traversal using a worklist.
463 std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
464 while (!ReverseCFGWorklist.empty()) {
465 BlockT *PredBB = ReverseCFGWorklist.back();
466 ReverseCFGWorklist.pop_back();
467
468 LoopT *Subloop = LI->getLoopFor(PredBB);
469 if (!Subloop) {
470 if (!DomTree.isReachableFromEntry(PredBB))
471 continue;
473 // This is an undiscovered block. Map it to the current loop.
474 LI->changeLoopFor(PredBB, L);
475 ++NumBlocks;
476 if (PredBB == L->getHeader())
477 continue;
478 // Push all block predecessors on the worklist.
479 ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
480 InvBlockTraits::child_begin(PredBB),
481 InvBlockTraits::child_end(PredBB));
482 } else {
483 // This is a discovered block. Find its outermost discovered loop.
484 Subloop = Subloop->getOutermostLoop();
485
486 // If it is already discovered to be a subloop of this loop, continue.
487 if (Subloop == L)
488 continue;
489
490 // Discover a subloop of this loop.
491 Subloop->setParentLoop(L);
492 ++NumSubloops;
493 NumBlocks += Subloop->getBlocksVector().capacity();
494 PredBB = Subloop->getHeader();
495 // Continue traversal along predecessors that are not loop-back edges from
496 // within this subloop tree itself. Note that a predecessor may directly
497 // reach another subloop that is not yet discovered to be a subloop of
498 // this loop, which we must traverse.
499 for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
500 if (LI->getLoopFor(Pred) != Subloop)
501 ReverseCFGWorklist.push_back(Pred);
502 }
503 }
504 }
505 L->getSubLoopsVector().reserve(NumSubloops);
506 L->reserveBlocks(NumBlocks);
507}
508
509/// Populate all loop data in a stable order during a single forward DFS.
510template <class BlockT, class LoopT> class PopulateLoopsDFS {
512 typedef typename BlockTraits::ChildIteratorType SuccIterTy;
513
515
516public:
518
519 void traverse(BlockT *EntryBlock);
520
521protected:
522 void insertIntoLoop(BlockT *Block);
523};
524
525/// Top-level driver for the forward DFS within the loop.
526template <class BlockT, class LoopT>
528 for (BlockT *BB : post_order(EntryBlock))
529 insertIntoLoop(BB);
530}
531
532/// Add a single Block to its ancestor loops in PostOrder. If the block is a
533/// subloop header, add the subloop to its parent in PostOrder, then reverse the
534/// Block and Subloop vectors of the now complete subloop to achieve RPO.
535template <class BlockT, class LoopT>
537 LoopT *Subloop = LI->getLoopFor(Block);
538 if (Subloop && Block == Subloop->getHeader()) {
539 // We reach this point once per subloop after processing all the blocks in
540 // the subloop.
541 if (!Subloop->isOutermost())
542 Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
543 else
544 LI->addTopLevelLoop(Subloop);
545
546 // For convenience, Blocks and Subloops are inserted in postorder. Reverse
547 // the lists, except for the loop header, which is always at the beginning.
548 Subloop->reverseBlock(1);
549 std::reverse(Subloop->getSubLoopsVector().begin(),
550 Subloop->getSubLoopsVector().end());
551
552 Subloop = Subloop->getParentLoop();
553 }
554 for (; Subloop; Subloop = Subloop->getParentLoop())
555 Subloop->addBlockEntry(Block);
556}
557
558/// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
559/// interleaved with backward CFG traversals within each subloop
560/// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
561/// this part of the algorithm is linear in the number of CFG edges. Subloop and
562/// Block vectors are then populated during a single forward CFG traversal
563/// (PopulateLoopDFS).
564///
565/// During the two CFG traversals each block is seen three times:
566/// 1) Discovered and mapped by a reverse CFG traversal.
567/// 2) Visited during a forward DFS CFG traversal.
568/// 3) Reverse-inserted in the loop in postorder following forward DFS.
569///
570/// The Block vectors are inclusive, so step 3 requires loop-depth number of
571/// insertions per block.
572template <class BlockT, class LoopT>
574 // Postorder traversal of the dominator tree.
575 const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
576 for (auto DomNode : post_order(DomRoot)) {
577
578 BlockT *Header = DomNode->getBlock();
579 SmallVector<BlockT *, 4> Backedges;
580
581 // Check each predecessor of the potential loop header.
582 for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
583 // If Header dominates predBB, this is a new loop. Collect the backedges.
584 if (DomTree.dominates(Header, Backedge) &&
585 DomTree.isReachableFromEntry(Backedge)) {
586 Backedges.push_back(Backedge);
587 }
588 }
589 // Perform a backward CFG traversal to discover and map blocks in this loop.
590 if (!Backedges.empty()) {
591 LoopT *L = AllocateLoop(Header);
592 discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
593 }
594 }
595 // Perform a single forward CFG traversal to populate block and subloop
596 // vectors for all loops.
598 DFS.traverse(DomRoot->getBlock());
599}
600
601template <class BlockT, class LoopT>
604 SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
605 // The outer-most loop actually goes into the result in the same relative
606 // order as we walk it. But LoopInfo stores the top level loops in reverse
607 // program order so for here we reverse it to get forward program order.
608 // FIXME: If we change the order of LoopInfo we will want to remove the
609 // reverse here.
610 for (LoopT *RootL : reverse(*this)) {
611 auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder();
612 PreOrderLoops.append(PreOrderLoopsInRootL.begin(),
613 PreOrderLoopsInRootL.end());
614 }
615
616 return PreOrderLoops;
617}
618
619template <class BlockT, class LoopT>
620SmallVector<LoopT *, 4>
622 SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
623 // The outer-most loop actually goes into the result in the same relative
624 // order as we walk it. LoopInfo stores the top level loops in reverse
625 // program order so we walk in order here.
626 // FIXME: If we change the order of LoopInfo we will want to add a reverse
627 // here.
628 for (LoopT *RootL : *this) {
629 assert(PreOrderWorklist.empty() &&
630 "Must start with an empty preorder walk worklist.");
631 PreOrderWorklist.push_back(RootL);
632 do {
633 LoopT *L = PreOrderWorklist.pop_back_val();
634 // Sub-loops are stored in forward program order, but will process the
635 // worklist backwards so we can just append them in order.
636 PreOrderWorklist.append(L->begin(), L->end());
637 PreOrderLoops.push_back(L);
638 } while (!PreOrderWorklist.empty());
639 }
640
641 return PreOrderLoops;
642}
643
644// Debugging
645template <class BlockT, class LoopT>
647 for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
648 TopLevelLoops[i]->print(OS);
649#if 0
651 E = BBMap.end(); I != E; ++I)
652 OS << "BB '" << I->first->getName() << "' level = "
653 << I->second->getLoopDepth() << "\n";
654#endif
655}
656
657template <typename T>
658bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) {
659 llvm::sort(BB1);
660 llvm::sort(BB2);
661 return BB1 == BB2;
662}
663
664template <class BlockT, class LoopT>
667 const LoopT &L) {
668 LoopHeaders[L.getHeader()] = &L;
669 for (LoopT *SL : L)
670 addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL);
671}
672
673#ifndef NDEBUG
674template <class BlockT, class LoopT>
675static void compareLoops(const LoopT *L, const LoopT *OtherL,
676 DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) {
677 BlockT *H = L->getHeader();
678 BlockT *OtherH = OtherL->getHeader();
679 assert(H == OtherH &&
680 "Mismatched headers even though found in the same map entry!");
681
682 assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
683 "Mismatched loop depth!");
684 const LoopT *ParentL = L, *OtherParentL = OtherL;
685 do {
686 assert(ParentL->getHeader() == OtherParentL->getHeader() &&
687 "Mismatched parent loop headers!");
688 ParentL = ParentL->getParentLoop();
689 OtherParentL = OtherParentL->getParentLoop();
690 } while (ParentL);
691
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);
697 compareLoops(SubL, OtherSubL, OtherLoopHeaders);
698 }
700 std::vector<BlockT *> BBs = L->getBlocks();
701 std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
702 assert(compareVectors(BBs, OtherBBs) &&
703 "Mismatched basic blocks in the loops!");
705 const SmallPtrSetImpl<const BlockT *> &BlocksSet = L->getBlocksSet();
706 const SmallPtrSetImpl<const BlockT *> &OtherBlocksSet =
707 OtherL->getBlocksSet();
708 assert(BlocksSet.size() == OtherBlocksSet.size() &&
709 llvm::set_is_subset(BlocksSet, OtherBlocksSet) &&
710 "Mismatched basic blocks in BlocksSets!");
711}
712#endif
713
714template <class BlockT, class LoopT>
716 const DomTreeBase<BlockT> &DomTree) const {
718 for (iterator I = begin(), E = end(); I != E; ++I) {
719 assert((*I)->isOutermost() && "Top-level loop has a parent!");
720 (*I)->verifyLoopNest(&Loops);
721 }
722
723// Verify that blocks are mapped to valid loops.
724#ifndef NDEBUG
725 for (auto &Entry : BBMap) {
726 const BlockT *BB = Entry.first;
727 LoopT *L = Entry.second;
728 assert(Loops.count(L) && "orphaned loop");
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");
733 }
734
735 // Recompute LoopInfo to verify loops structure.
737 OtherLI.analyze(DomTree);
738
739 // Build a map we can use to move from our LI to the computed one. This
740 // allows us to ignore the particular order in any layer of the loop forest
741 // while still comparing the structure.
742 DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
743 for (LoopT *L : OtherLI)
744 addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
745
746 // Walk the top level loops and ensure there is a corresponding top-level
747 // loop in the computed version and then recursively compare those loop
748 // nests.
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!");
753 // Now that we've matched this loop, erase its header from the map.
754 OtherLoopHeaders.erase(Header);
755 // And recursively compare these loops.
756 compareLoops(L, OtherL, OtherLoopHeaders);
757 }
758
759 // Any remaining entries in the map are loops which were found when computing
760 // a fresh LoopInfo but not present in the current one.
761 if (!OtherLoopHeaders.empty()) {
762 for (const auto &HeaderAndLoop : OtherLoopHeaders)
763 dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
764 llvm_unreachable("Found new loops when recomputing LoopInfo!");
765 }
766#endif
767}
768
769} // namespace llvm
770
771#endif // LLVM_SUPPORT_GENERICLOOPINFOIMPL_H
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
Definition: ELF_riscv.cpp:496
Hexagon Hardware Loops
static bool isExitBlock(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &ExitBlocks)
Return true if the specified block is in the list.
Definition: LCSSA.cpp:69
#define I(x, y, z)
Definition: MD5.cpp:58
#define H(x, y, z)
Definition: MD5.cpp:57
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 contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
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)
Definition: Value.cpp:470
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
iterator end() const
Definition: ArrayRef.h:154
iterator begin() const
Definition: ArrayRef.h:153
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...
Definition: DenseMap.h:202
bool erase(const KeyT &Val)
Definition: DenseMap.h:329
bool empty() const
Definition: DenseMap.h:98
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Base class for the actual dominator tree node.
NodeT * getBlock() const
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.
size_type size() const
Definition: SmallPtrSet.h:93
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:384
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
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.
Definition: Path.cpp:228
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:237
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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.
Definition: STLExtras.h:1747
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'.
Definition: STLExtras.h:80
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1734
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:429
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1652
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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...
Definition: STLExtras.h:582
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)
Definition: GraphTraits.h:123
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1884
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)