LLVM 20.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 : inverse_children<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 if (!llvm::hasSingleElement(llvm::children<BlockT *>(Out)))
212 return nullptr; // Multiple exits from the block, must not be a preheader.
213
214 // The predecessor has exactly one successor, so it is a preheader.
215 return Out;
216}
217
218/// getLoopPredecessor - If the given loop's header has exactly one unique
219/// predecessor outside the loop, return it. Otherwise return null.
220/// This is less strict that the loop "preheader" concept, which requires
221/// the predecessor to have exactly one successor.
222///
223template <class BlockT, class LoopT>
225 assert(!isInvalid() && "Loop not in a valid state!");
226 // Keep track of nodes outside the loop branching to the header...
227 BlockT *Out = nullptr;
228
229 // Loop over the predecessors of the header node...
230 BlockT *Header = getHeader();
231 for (const auto Pred : inverse_children<BlockT *>(Header)) {
232 if (!contains(Pred)) { // If the block is not in the loop...
233 if (Out && Out != Pred)
234 return nullptr; // Multiple predecessors outside the loop
235 Out = Pred;
236 }
237 }
238
239 return Out;
240}
241
242/// getLoopLatch - If there is a single latch block for this loop, return it.
243/// A latch block is a block that contains a branch back to the header.
244template <class BlockT, class LoopT>
246 assert(!isInvalid() && "Loop not in a valid state!");
247 BlockT *Header = getHeader();
248 BlockT *Latch = nullptr;
249 for (const auto Pred : inverse_children<BlockT *>(Header)) {
250 if (contains(Pred)) {
251 if (Latch)
252 return nullptr;
253 Latch = Pred;
254 }
255 }
256
257 return Latch;
258}
259
260//===----------------------------------------------------------------------===//
261// APIs for updating loop information after changing the CFG
262//
263
264/// addBasicBlockToLoop - This method is used by other analyses to update loop
265/// information. NewBB is set to be a new member of the current loop.
266/// Because of this, it is added as a member of all parent loops, and is added
267/// to the specified LoopInfo object as being in the current basic block. It
268/// is not valid to replace the loop header with this method.
269///
270template <class BlockT, class LoopT>
272 BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
273 assert(!isInvalid() && "Loop not in a valid state!");
274#ifndef NDEBUG
275 if (!Blocks.empty()) {
276 auto SameHeader = LIB[getHeader()];
277 assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
278 "Incorrect LI specified for this loop!");
279 }
280#endif
281 assert(NewBB && "Cannot add a null basic block to the loop!");
282 assert(!LIB[NewBB] && "BasicBlock already in the loop!");
283
284 LoopT *L = static_cast<LoopT *>(this);
286 // Add the loop mapping to the LoopInfo object...
287 LIB.BBMap[NewBB] = L;
288
289 // Add the basic block to this loop and all parent loops...
290 while (L) {
291 L->addBlockEntry(NewBB);
292 L = L->getParentLoop();
293 }
294}
296/// replaceChildLoopWith - This is used when splitting loops up. It replaces
297/// the OldChild entry in our children list with NewChild, and updates the
298/// parent pointer of OldChild to be null and the NewChild to be this loop.
299/// This updates the loop depth of the new child.
300template <class BlockT, class LoopT>
302 LoopT *NewChild) {
303 assert(!isInvalid() && "Loop not in a valid state!");
304 assert(OldChild->ParentLoop == this && "This loop is already broken!");
305 assert(!NewChild->ParentLoop && "NewChild already has a parent!");
306 typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
307 assert(I != SubLoops.end() && "OldChild not in loop!");
308 *I = NewChild;
309 OldChild->ParentLoop = nullptr;
310 NewChild->ParentLoop = static_cast<LoopT *>(this);
311}
313/// verifyLoop - Verify loop structure
314template <class BlockT, class LoopT>
316 assert(!isInvalid() && "Loop not in a valid state!");
317#ifndef NDEBUG
318 assert(!Blocks.empty() && "Loop header is missing");
319
320 // Setup for using a depth-first iterator to visit every block in the loop.
322 getExitBlocks(ExitBBs);
324 VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
325
326 // Keep track of the BBs visited.
327 SmallPtrSet<BlockT *, 8> VisitedBBs;
328
329 // Check the individual blocks.
330 for (BlockT *BB : depth_first_ext(getHeader(), VisitSet)) {
331 assert(llvm::any_of(children<BlockT *>(BB),
332 [&](BlockT *B) { return contains(B); }) &&
333 "Loop block has no in-loop successors!");
334
335 assert(llvm::any_of(inverse_children<BlockT *>(BB),
336 [&](BlockT *B) { return contains(B); }) &&
337 "Loop block has no in-loop predecessors!");
338
339 SmallVector<BlockT *, 2> OutsideLoopPreds;
340 for (BlockT *B : inverse_children<BlockT *>(BB))
341 if (!contains(B))
342 OutsideLoopPreds.push_back(B);
343
344 if (BB == getHeader()) {
345 assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
346 } else if (!OutsideLoopPreds.empty()) {
347 // A non-header loop shouldn't be reachable from outside the loop,
348 // though it is permitted if the predecessor is not itself actually
349 // reachable.
350 BlockT *EntryBB = &BB->getParent()->front();
351 for (BlockT *CB : depth_first(EntryBB))
352 for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
353 assert(CB != OutsideLoopPreds[i] &&
354 "Loop has multiple entry points!");
355 }
356 assert(BB != &getHeader()->getParent()->front() &&
357 "Loop contains function entry block!");
358
359 VisitedBBs.insert(BB);
360 }
361
362 if (VisitedBBs.size() != getNumBlocks()) {
363 dbgs() << "The following blocks are unreachable in the loop: ";
364 for (auto *BB : Blocks) {
365 if (!VisitedBBs.count(BB)) {
366 dbgs() << *BB << "\n";
367 }
368 }
369 assert(false && "Unreachable block in loop");
370 }
371
372 // Check the subloops.
373 for (iterator I = begin(), E = end(); I != E; ++I)
374 // Each block in each subloop should be contained within this loop.
375 for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
376 BI != BE; ++BI) {
378 "Loop does not contain all the blocks of a subloop!");
379 }
380
381 // Check the parent loop pointer.
382 if (ParentLoop) {
383 assert(is_contained(ParentLoop->getSubLoops(), this) &&
384 "Loop is not a subloop of its parent!");
385 }
386#endif
387}
388
389/// verifyLoop - Verify loop structure of this loop and all nested loops.
390template <class BlockT, class LoopT>
393 assert(!isInvalid() && "Loop not in a valid state!");
394 Loops->insert(static_cast<const LoopT *>(this));
395 // Verify this loop.
396 verifyLoop();
397 // Verify the subloops.
398 for (iterator I = begin(), E = end(); I != E; ++I)
399 (*I)->verifyLoopNest(Loops);
400}
401
402template <class BlockT, class LoopT>
404 bool PrintNested, unsigned Depth) const {
405 OS.indent(Depth * 2);
406 if (static_cast<const LoopT *>(this)->isAnnotatedParallel())
407 OS << "Parallel ";
408 OS << "Loop at depth " << getLoopDepth() << " containing: ";
409
410 BlockT *H = getHeader();
411 for (unsigned i = 0; i < getBlocks().size(); ++i) {
412 BlockT *BB = getBlocks()[i];
413 if (!Verbose) {
414 if (i)
415 OS << ",";
416 BB->printAsOperand(OS, false);
417 } else
418 OS << "\n";
419
420 if (BB == H)
421 OS << "<header>";
422 if (isLoopLatch(BB))
423 OS << "<latch>";
424 if (isLoopExiting(BB))
425 OS << "<exiting>";
426 if (Verbose)
427 BB->print(OS);
428 }
429
430 if (PrintNested) {
431 OS << "\n";
432
433 for (iterator I = begin(), E = end(); I != E; ++I)
434 (*I)->print(OS, /*Verbose*/ false, PrintNested, Depth + 2);
435 }
436}
437
438//===----------------------------------------------------------------------===//
439/// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
440/// result does / not depend on use list (block predecessor) order.
441///
442
443/// Discover a subloop with the specified backedges such that: All blocks within
444/// this loop are mapped to this loop or a subloop. And all subloops within this
445/// loop have their parent loop set to this loop or a subloop.
446template <class BlockT, class LoopT>
447static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges,
449 const DomTreeBase<BlockT> &DomTree) {
450 typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
451
452 unsigned NumBlocks = 0;
453 unsigned NumSubloops = 0;
454
455 // Perform a backward CFG traversal using a worklist.
456 std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
457 while (!ReverseCFGWorklist.empty()) {
458 BlockT *PredBB = ReverseCFGWorklist.back();
459 ReverseCFGWorklist.pop_back();
460
461 LoopT *Subloop = LI->getLoopFor(PredBB);
462 if (!Subloop) {
463 if (!DomTree.isReachableFromEntry(PredBB))
464 continue;
466 // This is an undiscovered block. Map it to the current loop.
467 LI->changeLoopFor(PredBB, L);
468 ++NumBlocks;
469 if (PredBB == L->getHeader())
470 continue;
471 // Push all block predecessors on the worklist.
472 ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
473 InvBlockTraits::child_begin(PredBB),
474 InvBlockTraits::child_end(PredBB));
475 } else {
476 // This is a discovered block. Find its outermost discovered loop.
477 Subloop = Subloop->getOutermostLoop();
478
479 // If it is already discovered to be a subloop of this loop, continue.
480 if (Subloop == L)
481 continue;
482
483 // Discover a subloop of this loop.
484 Subloop->setParentLoop(L);
485 ++NumSubloops;
486 NumBlocks += Subloop->getBlocksVector().capacity();
487 PredBB = Subloop->getHeader();
488 // Continue traversal along predecessors that are not loop-back edges from
489 // within this subloop tree itself. Note that a predecessor may directly
490 // reach another subloop that is not yet discovered to be a subloop of
491 // this loop, which we must traverse.
492 for (const auto Pred : inverse_children<BlockT *>(PredBB)) {
493 if (LI->getLoopFor(Pred) != Subloop)
494 ReverseCFGWorklist.push_back(Pred);
495 }
496 }
497 }
498 L->getSubLoopsVector().reserve(NumSubloops);
499 L->reserveBlocks(NumBlocks);
500}
501
502/// Populate all loop data in a stable order during a single forward DFS.
503template <class BlockT, class LoopT> class PopulateLoopsDFS {
505 typedef typename BlockTraits::ChildIteratorType SuccIterTy;
506
508
509public:
511
512 void traverse(BlockT *EntryBlock);
513
514protected:
515 void insertIntoLoop(BlockT *Block);
516};
517
518/// Top-level driver for the forward DFS within the loop.
519template <class BlockT, class LoopT>
521 for (BlockT *BB : post_order(EntryBlock))
522 insertIntoLoop(BB);
523}
524
525/// Add a single Block to its ancestor loops in PostOrder. If the block is a
526/// subloop header, add the subloop to its parent in PostOrder, then reverse the
527/// Block and Subloop vectors of the now complete subloop to achieve RPO.
528template <class BlockT, class LoopT>
530 LoopT *Subloop = LI->getLoopFor(Block);
531 if (Subloop && Block == Subloop->getHeader()) {
532 // We reach this point once per subloop after processing all the blocks in
533 // the subloop.
534 if (!Subloop->isOutermost())
535 Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
536 else
537 LI->addTopLevelLoop(Subloop);
538
539 // For convenience, Blocks and Subloops are inserted in postorder. Reverse
540 // the lists, except for the loop header, which is always at the beginning.
541 Subloop->reverseBlock(1);
542 std::reverse(Subloop->getSubLoopsVector().begin(),
543 Subloop->getSubLoopsVector().end());
544
545 Subloop = Subloop->getParentLoop();
546 }
547 for (; Subloop; Subloop = Subloop->getParentLoop())
548 Subloop->addBlockEntry(Block);
549}
550
551/// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
552/// interleaved with backward CFG traversals within each subloop
553/// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
554/// this part of the algorithm is linear in the number of CFG edges. Subloop and
555/// Block vectors are then populated during a single forward CFG traversal
556/// (PopulateLoopDFS).
557///
558/// During the two CFG traversals each block is seen three times:
559/// 1) Discovered and mapped by a reverse CFG traversal.
560/// 2) Visited during a forward DFS CFG traversal.
561/// 3) Reverse-inserted in the loop in postorder following forward DFS.
562///
563/// The Block vectors are inclusive, so step 3 requires loop-depth number of
564/// insertions per block.
565template <class BlockT, class LoopT>
567 // Postorder traversal of the dominator tree.
568 const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
569 for (auto DomNode : post_order(DomRoot)) {
570
571 BlockT *Header = DomNode->getBlock();
572 SmallVector<BlockT *, 4> Backedges;
573
574 // Check each predecessor of the potential loop header.
575 for (const auto Backedge : inverse_children<BlockT *>(Header)) {
576 // If Header dominates predBB, this is a new loop. Collect the backedges.
577 const DomTreeNodeBase<BlockT> *BackedgeNode = DomTree.getNode(Backedge);
578 if (BackedgeNode && DomTree.dominates(DomNode, BackedgeNode))
579 Backedges.push_back(Backedge);
580 }
581 // Perform a backward CFG traversal to discover and map blocks in this loop.
582 if (!Backedges.empty()) {
583 LoopT *L = AllocateLoop(Header);
584 discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
585 }
586 }
587 // Perform a single forward CFG traversal to populate block and subloop
588 // vectors for all loops.
590 DFS.traverse(DomRoot->getBlock());
591}
592
593template <class BlockT, class LoopT>
596 SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
597 // The outer-most loop actually goes into the result in the same relative
598 // order as we walk it. But LoopInfo stores the top level loops in reverse
599 // program order so for here we reverse it to get forward program order.
600 // FIXME: If we change the order of LoopInfo we will want to remove the
601 // reverse here.
602 for (LoopT *RootL : reverse(*this)) {
603 auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder();
604 PreOrderLoops.append(PreOrderLoopsInRootL.begin(),
605 PreOrderLoopsInRootL.end());
606 }
607
608 return PreOrderLoops;
609}
610
611template <class BlockT, class LoopT>
612SmallVector<LoopT *, 4>
614 SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
615 // The outer-most loop actually goes into the result in the same relative
616 // order as we walk it. LoopInfo stores the top level loops in reverse
617 // program order so we walk in order here.
618 // FIXME: If we change the order of LoopInfo we will want to add a reverse
619 // here.
620 for (LoopT *RootL : *this) {
621 assert(PreOrderWorklist.empty() &&
622 "Must start with an empty preorder walk worklist.");
623 PreOrderWorklist.push_back(RootL);
624 do {
625 LoopT *L = PreOrderWorklist.pop_back_val();
626 // Sub-loops are stored in forward program order, but will process the
627 // worklist backwards so we can just append them in order.
628 PreOrderWorklist.append(L->begin(), L->end());
629 PreOrderLoops.push_back(L);
630 } while (!PreOrderWorklist.empty());
631 }
632
633 return PreOrderLoops;
634}
635
636// Debugging
637template <class BlockT, class LoopT>
639 for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
640 TopLevelLoops[i]->print(OS);
641#if 0
643 E = BBMap.end(); I != E; ++I)
644 OS << "BB '" << I->first->getName() << "' level = "
645 << I->second->getLoopDepth() << "\n";
646#endif
647}
648
649template <typename T>
650bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) {
651 llvm::sort(BB1);
652 llvm::sort(BB2);
653 return BB1 == BB2;
654}
655
656template <class BlockT, class LoopT>
659 const LoopT &L) {
660 LoopHeaders[L.getHeader()] = &L;
661 for (LoopT *SL : L)
662 addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL);
663}
664
665#ifndef NDEBUG
666template <class BlockT, class LoopT>
667static void compareLoops(const LoopT *L, const LoopT *OtherL,
668 DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) {
669 BlockT *H = L->getHeader();
670 BlockT *OtherH = OtherL->getHeader();
671 assert(H == OtherH &&
672 "Mismatched headers even though found in the same map entry!");
673
674 assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
675 "Mismatched loop depth!");
676 const LoopT *ParentL = L, *OtherParentL = OtherL;
677 do {
678 assert(ParentL->getHeader() == OtherParentL->getHeader() &&
679 "Mismatched parent loop headers!");
680 ParentL = ParentL->getParentLoop();
681 OtherParentL = OtherParentL->getParentLoop();
682 } while (ParentL);
683
684 for (const LoopT *SubL : *L) {
685 BlockT *SubH = SubL->getHeader();
686 const LoopT *OtherSubL = OtherLoopHeaders.lookup(SubH);
687 assert(OtherSubL && "Inner loop is missing in computed loop info!");
688 OtherLoopHeaders.erase(SubH);
689 compareLoops(SubL, OtherSubL, OtherLoopHeaders);
690 }
691
692 std::vector<BlockT *> BBs = L->getBlocks();
693 std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
694 assert(compareVectors(BBs, OtherBBs) &&
695 "Mismatched basic blocks in the loops!");
696
697 const SmallPtrSetImpl<const BlockT *> &BlocksSet = L->getBlocksSet();
698 const SmallPtrSetImpl<const BlockT *> &OtherBlocksSet =
699 OtherL->getBlocksSet();
700 assert(BlocksSet.size() == OtherBlocksSet.size() &&
701 llvm::set_is_subset(BlocksSet, OtherBlocksSet) &&
702 "Mismatched basic blocks in BlocksSets!");
703}
704#endif
705
706template <class BlockT, class LoopT>
708 const DomTreeBase<BlockT> &DomTree) const {
710 for (iterator I = begin(), E = end(); I != E; ++I) {
711 assert((*I)->isOutermost() && "Top-level loop has a parent!");
712 (*I)->verifyLoopNest(&Loops);
713 }
714
715// Verify that blocks are mapped to valid loops.
716#ifndef NDEBUG
717 for (auto &Entry : BBMap) {
718 const BlockT *BB = Entry.first;
719 LoopT *L = Entry.second;
720 assert(Loops.count(L) && "orphaned loop");
721 assert(L->contains(BB) && "orphaned block");
722 for (LoopT *ChildLoop : *L)
723 assert(!ChildLoop->contains(BB) &&
724 "BBMap should point to the innermost loop containing BB");
725 }
726
727 // Recompute LoopInfo to verify loops structure.
729 OtherLI.analyze(DomTree);
730
731 // Build a map we can use to move from our LI to the computed one. This
732 // allows us to ignore the particular order in any layer of the loop forest
733 // while still comparing the structure.
734 DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
735 for (LoopT *L : OtherLI)
736 addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
737
738 // Walk the top level loops and ensure there is a corresponding top-level
739 // loop in the computed version and then recursively compare those loop
740 // nests.
741 for (LoopT *L : *this) {
742 BlockT *Header = L->getHeader();
743 const LoopT *OtherL = OtherLoopHeaders.lookup(Header);
744 assert(OtherL && "Top level loop is missing in computed loop info!");
745 // Now that we've matched this loop, erase its header from the map.
746 OtherLoopHeaders.erase(Header);
747 // And recursively compare these loops.
748 compareLoops(L, OtherL, OtherLoopHeaders);
749 }
750
751 // Any remaining entries in the map are loops which were found when computing
752 // a fresh LoopInfo but not present in the current one.
753 if (!OtherLoopHeaders.empty()) {
754 for (const auto &HeaderAndLoop : OtherLoopHeaders)
755 dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
756 llvm_unreachable("Found new loops when recomputing LoopInfo!");
757 }
758#endif
759}
760
761} // namespace llvm
762
763#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:507
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:469
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:194
bool erase(const KeyT &Val)
Definition: DenseMap.h:336
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...
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
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:96
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:347
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:436
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:368
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:503
bool empty() const
Definition: SmallVector.h:95
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:587
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:951
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:697
void push_back(const T &Elt)
Definition: SmallVector.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
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:227
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:236
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:1742
static void compareLoops(const LoopT *L, const LoopT *OtherL, DenseMap< BlockT *, const LoopT * > &OtherLoopHeaders)
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)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
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:79
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:1729
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1647
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool hasSingleElement(ContainerTy &&C)
Returns true if the given container only contains a single element.
Definition: STLExtras.h:322
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:572
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)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879
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)