LLVM 17.0.0git
LoopInfoImpl.h
Go to the documentation of this file.
1//===- llvm/Analysis/LoopInfoImpl.h - Natural Loop Calculator ---*- 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 is the generic implementation of LoopInfo used for both Loops and
10// MachineLoops.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H
15#define LLVM_ANALYSIS_LOOPINFOIMPL_H
16
18#include "llvm/ADT/STLExtras.h"
21#include "llvm/IR/Dominators.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
174/// getLoopPreheader - If there is a preheader for this loop, return it. A
175/// loop has a preheader if there is only one edge to the header of the loop
176/// from outside of the loop and it is legal to hoist instructions into the
177/// predecessor. If this is the case, the block branching to the header of the
178/// loop is the preheader node.
179///
180/// This method returns null if there is no preheader for the loop.
181///
182template <class BlockT, class LoopT>
184 assert(!isInvalid() && "Loop not in a valid state!");
185 // Keep track of nodes outside the loop branching to the header...
186 BlockT *Out = getLoopPredecessor();
187 if (!Out)
188 return nullptr;
189
190 // Make sure we are allowed to hoist instructions into the predecessor.
191 if (!Out->isLegalToHoistInto())
192 return nullptr;
193
194 // Make sure there is only one exit out of the preheader.
195 typedef GraphTraits<BlockT *> BlockTraits;
196 typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
197 ++SI;
198 if (SI != BlockTraits::child_end(Out))
199 return nullptr; // Multiple exits from the block, must not be a preheader.
200
201 // The predecessor has exactly one successor, so it is a preheader.
202 return Out;
203}
204
205/// getLoopPredecessor - If the given loop's header has exactly one unique
206/// predecessor outside the loop, return it. Otherwise return null.
207/// This is less strict that the loop "preheader" concept, which requires
208/// the predecessor to have exactly one successor.
209///
210template <class BlockT, class LoopT>
212 assert(!isInvalid() && "Loop not in a valid state!");
213 // Keep track of nodes outside the loop branching to the header...
214 BlockT *Out = nullptr;
215
216 // Loop over the predecessors of the header node...
217 BlockT *Header = getHeader();
218 for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
219 if (!contains(Pred)) { // If the block is not in the loop...
220 if (Out && Out != Pred)
221 return nullptr; // Multiple predecessors outside the loop
222 Out = Pred;
223 }
224 }
225
226 return Out;
227}
228
229/// getLoopLatch - If there is a single latch block for this loop, return it.
230/// A latch block is a block that contains a branch back to the header.
231template <class BlockT, class LoopT>
233 assert(!isInvalid() && "Loop not in a valid state!");
234 BlockT *Header = getHeader();
235 BlockT *Latch = nullptr;
236 for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
237 if (contains(Pred)) {
238 if (Latch)
239 return nullptr;
240 Latch = Pred;
241 }
242 }
243
244 return Latch;
245}
246
247//===----------------------------------------------------------------------===//
248// APIs for updating loop information after changing the CFG
249//
250
251/// addBasicBlockToLoop - This method is used by other analyses to update loop
252/// information. NewBB is set to be a new member of the current loop.
253/// Because of this, it is added as a member of all parent loops, and is added
254/// to the specified LoopInfo object as being in the current basic block. It
255/// is not valid to replace the loop header with this method.
256///
257template <class BlockT, class LoopT>
259 BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
260 assert(!isInvalid() && "Loop not in a valid state!");
261#ifndef NDEBUG
262 if (!Blocks.empty()) {
263 auto SameHeader = LIB[getHeader()];
264 assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
265 "Incorrect LI specified for this loop!");
266 }
267#endif
268 assert(NewBB && "Cannot add a null basic block to the loop!");
269 assert(!LIB[NewBB] && "BasicBlock already in the loop!");
270
271 LoopT *L = static_cast<LoopT *>(this);
272
273 // Add the loop mapping to the LoopInfo object...
274 LIB.BBMap[NewBB] = L;
275
276 // Add the basic block to this loop and all parent loops...
277 while (L) {
278 L->addBlockEntry(NewBB);
279 L = L->getParentLoop();
280 }
281}
282
283/// replaceChildLoopWith - This is used when splitting loops up. It replaces
284/// the OldChild entry in our children list with NewChild, and updates the
285/// parent pointer of OldChild to be null and the NewChild to be this loop.
286/// This updates the loop depth of the new child.
287template <class BlockT, class LoopT>
289 LoopT *NewChild) {
290 assert(!isInvalid() && "Loop not in a valid state!");
291 assert(OldChild->ParentLoop == this && "This loop is already broken!");
292 assert(!NewChild->ParentLoop && "NewChild already has a parent!");
293 typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
294 assert(I != SubLoops.end() && "OldChild not in loop!");
295 *I = NewChild;
296 OldChild->ParentLoop = nullptr;
297 NewChild->ParentLoop = static_cast<LoopT *>(this);
299
300/// verifyLoop - Verify loop structure
301template <class BlockT, class LoopT>
303 assert(!isInvalid() && "Loop not in a valid state!");
304#ifndef NDEBUG
305 assert(!Blocks.empty() && "Loop header is missing");
307 // Setup for using a depth-first iterator to visit every block in the loop.
309 getExitBlocks(ExitBBs);
311 VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
312
313 // Keep track of the BBs visited.
314 SmallPtrSet<BlockT *, 8> VisitedBBs;
315
316 // Check the individual blocks.
317 for (BlockT *BB : depth_first_ext(getHeader(), VisitSet)) {
320 [&](BlockT *B) { return contains(B); }) &&
321 "Loop block has no in-loop successors!");
322
323 assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
324 GraphTraits<Inverse<BlockT *>>::child_end(BB),
325 [&](BlockT *B) { return contains(B); }) &&
326 "Loop block has no in-loop predecessors!");
327
328 SmallVector<BlockT *, 2> OutsideLoopPreds;
329 for (BlockT *B :
331 GraphTraits<Inverse<BlockT *>>::child_end(BB)))
332 if (!contains(B))
333 OutsideLoopPreds.push_back(B);
334
335 if (BB == getHeader()) {
336 assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
337 } else if (!OutsideLoopPreds.empty()) {
338 // A non-header loop shouldn't be reachable from outside the loop,
339 // though it is permitted if the predecessor is not itself actually
340 // reachable.
341 BlockT *EntryBB = &BB->getParent()->front();
342 for (BlockT *CB : depth_first(EntryBB))
343 for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
344 assert(CB != OutsideLoopPreds[i] &&
345 "Loop has multiple entry points!");
346 }
347 assert(BB != &getHeader()->getParent()->front() &&
348 "Loop contains function entry block!");
349
350 VisitedBBs.insert(BB);
351 }
352
353 if (VisitedBBs.size() != getNumBlocks()) {
354 dbgs() << "The following blocks are unreachable in the loop: ";
355 for (auto *BB : Blocks) {
356 if (!VisitedBBs.count(BB)) {
357 dbgs() << *BB << "\n";
358 }
359 }
360 assert(false && "Unreachable block in loop");
361 }
362
363 // Check the subloops.
364 for (iterator I = begin(), E = end(); I != E; ++I)
365 // Each block in each subloop should be contained within this loop.
366 for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
367 BI != BE; ++BI) {
368 assert(contains(*BI) &&
369 "Loop does not contain all the blocks of a subloop!");
370 }
371
372 // Check the parent loop pointer.
373 if (ParentLoop) {
374 assert(is_contained(*ParentLoop, this) &&
375 "Loop is not a subloop of its parent!");
376 }
377#endif
378}
379
380/// verifyLoop - Verify loop structure of this loop and all nested loops.
381template <class BlockT, class LoopT>
384 assert(!isInvalid() && "Loop not in a valid state!");
385 Loops->insert(static_cast<const LoopT *>(this));
386 // Verify this loop.
387 verifyLoop();
388 // Verify the subloops.
389 for (iterator I = begin(), E = end(); I != E; ++I)
390 (*I)->verifyLoopNest(Loops);
391}
392
393template <class BlockT, class LoopT>
395 bool PrintNested, unsigned Depth) const {
396 OS.indent(Depth * 2);
397 if (static_cast<const LoopT *>(this)->isAnnotatedParallel())
398 OS << "Parallel ";
399 OS << "Loop at depth " << getLoopDepth() << " containing: ";
400
401 BlockT *H = getHeader();
402 for (unsigned i = 0; i < getBlocks().size(); ++i) {
403 BlockT *BB = getBlocks()[i];
404 if (!Verbose) {
405 if (i)
406 OS << ",";
407 BB->printAsOperand(OS, false);
408 } else
409 OS << "\n";
410
411 if (BB == H)
412 OS << "<header>";
413 if (isLoopLatch(BB))
414 OS << "<latch>";
415 if (isLoopExiting(BB))
416 OS << "<exiting>";
417 if (Verbose)
418 BB->print(OS);
419 }
420
421 if (PrintNested) {
422 OS << "\n";
423
424 for (iterator I = begin(), E = end(); I != E; ++I)
425 (*I)->print(OS, /*Verbose*/ false, PrintNested, Depth + 2);
426 }
427}
428
429//===----------------------------------------------------------------------===//
430/// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
431/// result does / not depend on use list (block predecessor) order.
432///
433
434/// Discover a subloop with the specified backedges such that: All blocks within
435/// this loop are mapped to this loop or a subloop. And all subloops within this
436/// loop have their parent loop set to this loop or a subloop.
437template <class BlockT, class LoopT>
438static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges,
440 const DomTreeBase<BlockT> &DomTree) {
441 typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
442
443 unsigned NumBlocks = 0;
444 unsigned NumSubloops = 0;
445
446 // Perform a backward CFG traversal using a worklist.
447 std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
448 while (!ReverseCFGWorklist.empty()) {
449 BlockT *PredBB = ReverseCFGWorklist.back();
450 ReverseCFGWorklist.pop_back();
451
452 LoopT *Subloop = LI->getLoopFor(PredBB);
453 if (!Subloop) {
454 if (!DomTree.isReachableFromEntry(PredBB))
455 continue;
456
457 // This is an undiscovered block. Map it to the current loop.
458 LI->changeLoopFor(PredBB, L);
459 ++NumBlocks;
460 if (PredBB == L->getHeader())
461 continue;
462 // Push all block predecessors on the worklist.
463 ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
464 InvBlockTraits::child_begin(PredBB),
465 InvBlockTraits::child_end(PredBB));
466 } else {
467 // This is a discovered block. Find its outermost discovered loop.
468 Subloop = Subloop->getOutermostLoop();
469
470 // If it is already discovered to be a subloop of this loop, continue.
471 if (Subloop == L)
472 continue;
473
474 // Discover a subloop of this loop.
475 Subloop->setParentLoop(L);
476 ++NumSubloops;
477 NumBlocks += Subloop->getBlocksVector().capacity();
478 PredBB = Subloop->getHeader();
479 // Continue traversal along predecessors that are not loop-back edges from
480 // within this subloop tree itself. Note that a predecessor may directly
481 // reach another subloop that is not yet discovered to be a subloop of
482 // this loop, which we must traverse.
483 for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
484 if (LI->getLoopFor(Pred) != Subloop)
485 ReverseCFGWorklist.push_back(Pred);
486 }
488 }
489 L->getSubLoopsVector().reserve(NumSubloops);
490 L->reserveBlocks(NumBlocks);
491}
492
493/// Populate all loop data in a stable order during a single forward DFS.
494template <class BlockT, class LoopT> class PopulateLoopsDFS {
496 typedef typename BlockTraits::ChildIteratorType SuccIterTy;
497
500public:
502
503 void traverse(BlockT *EntryBlock);
504
505protected:
506 void insertIntoLoop(BlockT *Block);
507};
508
509/// Top-level driver for the forward DFS within the loop.
510template <class BlockT, class LoopT>
512 for (BlockT *BB : post_order(EntryBlock))
513 insertIntoLoop(BB);
514}
515
516/// Add a single Block to its ancestor loops in PostOrder. If the block is a
517/// subloop header, add the subloop to its parent in PostOrder, then reverse the
518/// Block and Subloop vectors of the now complete subloop to achieve RPO.
519template <class BlockT, class LoopT>
521 LoopT *Subloop = LI->getLoopFor(Block);
522 if (Subloop && Block == Subloop->getHeader()) {
523 // We reach this point once per subloop after processing all the blocks in
524 // the subloop.
525 if (!Subloop->isOutermost())
526 Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
527 else
528 LI->addTopLevelLoop(Subloop);
529
530 // For convenience, Blocks and Subloops are inserted in postorder. Reverse
531 // the lists, except for the loop header, which is always at the beginning.
532 Subloop->reverseBlock(1);
533 std::reverse(Subloop->getSubLoopsVector().begin(),
534 Subloop->getSubLoopsVector().end());
535
536 Subloop = Subloop->getParentLoop();
537 }
538 for (; Subloop; Subloop = Subloop->getParentLoop())
539 Subloop->addBlockEntry(Block);
540}
541
542/// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
543/// interleaved with backward CFG traversals within each subloop
544/// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
545/// this part of the algorithm is linear in the number of CFG edges. Subloop and
546/// Block vectors are then populated during a single forward CFG traversal
547/// (PopulateLoopDFS).
548///
549/// During the two CFG traversals each block is seen three times:
550/// 1) Discovered and mapped by a reverse CFG traversal.
551/// 2) Visited during a forward DFS CFG traversal.
552/// 3) Reverse-inserted in the loop in postorder following forward DFS.
553///
554/// The Block vectors are inclusive, so step 3 requires loop-depth number of
555/// insertions per block.
556template <class BlockT, class LoopT>
558 // Postorder traversal of the dominator tree.
559 const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
560 for (auto DomNode : post_order(DomRoot)) {
561
562 BlockT *Header = DomNode->getBlock();
563 SmallVector<BlockT *, 4> Backedges;
564
565 // Check each predecessor of the potential loop header.
566 for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
567 // If Header dominates predBB, this is a new loop. Collect the backedges.
568 if (DomTree.dominates(Header, Backedge) &&
569 DomTree.isReachableFromEntry(Backedge)) {
570 Backedges.push_back(Backedge);
571 }
572 }
573 // Perform a backward CFG traversal to discover and map blocks in this loop.
574 if (!Backedges.empty()) {
575 LoopT *L = AllocateLoop(Header);
576 discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
577 }
578 }
579 // Perform a single forward CFG traversal to populate block and subloop
580 // vectors for all loops.
582 DFS.traverse(DomRoot->getBlock());
583}
584
585template <class BlockT, class LoopT>
588 SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
589 // The outer-most loop actually goes into the result in the same relative
590 // order as we walk it. But LoopInfo stores the top level loops in reverse
591 // program order so for here we reverse it to get forward program order.
592 // FIXME: If we change the order of LoopInfo we will want to remove the
593 // reverse here.
594 for (LoopT *RootL : reverse(*this)) {
595 auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder();
596 PreOrderLoops.append(PreOrderLoopsInRootL.begin(),
597 PreOrderLoopsInRootL.end());
598 }
599
600 return PreOrderLoops;
601}
602
603template <class BlockT, class LoopT>
606 SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
607 // The outer-most loop actually goes into the result in the same relative
608 // order as we walk it. LoopInfo stores the top level loops in reverse
609 // program order so we walk in order here.
610 // FIXME: If we change the order of LoopInfo we will want to add a reverse
611 // here.
612 for (LoopT *RootL : *this) {
613 assert(PreOrderWorklist.empty() &&
614 "Must start with an empty preorder walk worklist.");
615 PreOrderWorklist.push_back(RootL);
616 do {
617 LoopT *L = PreOrderWorklist.pop_back_val();
618 // Sub-loops are stored in forward program order, but will process the
619 // worklist backwards so we can just append them in order.
620 PreOrderWorklist.append(L->begin(), L->end());
621 PreOrderLoops.push_back(L);
622 } while (!PreOrderWorklist.empty());
623 }
624
625 return PreOrderLoops;
626}
627
628// Debugging
629template <class BlockT, class LoopT>
631 for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
632 TopLevelLoops[i]->print(OS);
633#if 0
635 E = BBMap.end(); I != E; ++I)
636 OS << "BB '" << I->first->getName() << "' level = "
637 << I->second->getLoopDepth() << "\n";
638#endif
639}
640
641template <typename T>
642bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) {
643 llvm::sort(BB1);
644 llvm::sort(BB2);
645 return BB1 == BB2;
646}
647
648template <class BlockT, class LoopT>
651 const LoopT &L) {
652 LoopHeaders[L.getHeader()] = &L;
653 for (LoopT *SL : L)
654 addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL);
655}
656
657#ifndef NDEBUG
658template <class BlockT, class LoopT>
659static void compareLoops(const LoopT *L, const LoopT *OtherL,
660 DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) {
661 BlockT *H = L->getHeader();
662 BlockT *OtherH = OtherL->getHeader();
663 assert(H == OtherH &&
664 "Mismatched headers even though found in the same map entry!");
665
666 assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
667 "Mismatched loop depth!");
668 const LoopT *ParentL = L, *OtherParentL = OtherL;
669 do {
670 assert(ParentL->getHeader() == OtherParentL->getHeader() &&
671 "Mismatched parent loop headers!");
672 ParentL = ParentL->getParentLoop();
673 OtherParentL = OtherParentL->getParentLoop();
674 } while (ParentL);
675
676 for (const LoopT *SubL : *L) {
677 BlockT *SubH = SubL->getHeader();
678 const LoopT *OtherSubL = OtherLoopHeaders.lookup(SubH);
679 assert(OtherSubL && "Inner loop is missing in computed loop info!");
680 OtherLoopHeaders.erase(SubH);
681 compareLoops(SubL, OtherSubL, OtherLoopHeaders);
682 }
683
684 std::vector<BlockT *> BBs = L->getBlocks();
685 std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
686 assert(compareVectors(BBs, OtherBBs) &&
687 "Mismatched basic blocks in the loops!");
688
689 const SmallPtrSetImpl<const BlockT *> &BlocksSet = L->getBlocksSet();
690 const SmallPtrSetImpl<const BlockT *> &OtherBlocksSet =
691 OtherL->getBlocksSet();
692 assert(BlocksSet.size() == OtherBlocksSet.size() &&
693 llvm::set_is_subset(BlocksSet, OtherBlocksSet) &&
694 "Mismatched basic blocks in BlocksSets!");
695}
696#endif
697
698template <class BlockT, class LoopT>
700 const DomTreeBase<BlockT> &DomTree) const {
702 for (iterator I = begin(), E = end(); I != E; ++I) {
703 assert((*I)->isOutermost() && "Top-level loop has a parent!");
704 (*I)->verifyLoopNest(&Loops);
705 }
706
707// Verify that blocks are mapped to valid loops.
708#ifndef NDEBUG
709 for (auto &Entry : BBMap) {
710 const BlockT *BB = Entry.first;
711 LoopT *L = Entry.second;
712 assert(Loops.count(L) && "orphaned loop");
713 assert(L->contains(BB) && "orphaned block");
714 for (LoopT *ChildLoop : *L)
715 assert(!ChildLoop->contains(BB) &&
716 "BBMap should point to the innermost loop containing BB");
717 }
718
719 // Recompute LoopInfo to verify loops structure.
721 OtherLI.analyze(DomTree);
722
723 // Build a map we can use to move from our LI to the computed one. This
724 // allows us to ignore the particular order in any layer of the loop forest
725 // while still comparing the structure.
726 DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
727 for (LoopT *L : OtherLI)
728 addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
729
730 // Walk the top level loops and ensure there is a corresponding top-level
731 // loop in the computed version and then recursively compare those loop
732 // nests.
733 for (LoopT *L : *this) {
734 BlockT *Header = L->getHeader();
735 const LoopT *OtherL = OtherLoopHeaders.lookup(Header);
736 assert(OtherL && "Top level loop is missing in computed loop info!");
737 // Now that we've matched this loop, erase its header from the map.
738 OtherLoopHeaders.erase(Header);
739 // And recursively compare these loops.
740 compareLoops(L, OtherL, OtherLoopHeaders);
741 }
742
743 // Any remaining entries in the map are loops which were found when computing
744 // a fresh LoopInfo but not present in the current one.
745 if (!OtherLoopHeaders.empty()) {
746 for (const auto &HeaderAndLoop : OtherLoopHeaders)
747 dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
748 llvm_unreachable("Found new loops when recomputing LoopInfo!");
749 }
750#endif
751}
752
753} // End llvm namespace
754
755#endif
static const Function * getParent(const Value *V)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:70
#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.
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
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:467
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:152
iterator begin() const
Definition: ArrayRef.h:151
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:197
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
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.
Definition: LoopInfo.h:74
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:139
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:232
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:64
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:302
void verifyLoopNest(DenseSet< const LoopT * > *Loops) const
Verify loop structure of this loop and all nested loops.
Definition: LoopInfoImpl.h:382
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:33
void print(raw_ostream &OS, bool Verbose=false, bool PrintNested=true, unsigned Depth=0) const
Print loop with all the BBs inside it.
Definition: LoopInfoImpl.h:394
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:258
std::vector< LoopT * >::const_iterator iterator
Definition: LoopInfo.h:168
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:195
bool isInvalid() const
Return true if this loop is no longer valid.
Definition: LoopInfo.h:232
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
Definition: LoopInfoImpl.h:211
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
Definition: LoopInfoImpl.h:164
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:107
bool hasNoExitBlocks() const
Return true if this loop does not have any exit blocks.
Definition: LoopInfoImpl.h:95
void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild)
This is used when splitting loops up.
Definition: LoopInfoImpl.h:288
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:48
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfoImpl.h:142
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:112
void getUniqueNonLatchExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop except successors from Latch block are not considered...
Definition: LoopInfoImpl.h:149
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:158
This class builds and contains all of the top-level loop structures in the specified function.
Definition: LoopInfo.h:912
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:699
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:1049
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:557
SmallVector< LoopT *, 4 > getLoopsInReverseSiblingPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in reverse p...
Definition: LoopInfoImpl.h:605
void print(raw_ostream &OS) const
Definition: LoopInfoImpl.h:630
SmallVector< LoopT *, 4 > getLoopsInPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
Definition: LoopInfoImpl.h:587
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1030
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
std::vector< LoopT * >::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:964
Populate all loop data in a stable order during a single forward DFS.
Definition: LoopInfoImpl.h:494
void traverse(BlockT *EntryBlock)
Top-level driver for the forward DFS within the loop.
Definition: LoopInfoImpl.h:511
PopulateLoopsDFS(LoopInfoBase< BlockT, LoopT > *li)
Definition: LoopInfoImpl.h:501
void insertIntoLoop(BlockT *Block)
Add a single Block to its ancestor loops in PostOrder.
Definition: LoopInfoImpl.h:520
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:344
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
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:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
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:1755
static void compareLoops(const LoopT *L, const LoopT *OtherL, DenseMap< BlockT *, const LoopT * > &OtherLoopHeaders)
Definition: LoopInfoImpl.h:659
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
Definition: SetOperations.h:72
iterator_range< po_iterator< T > > post_order(const T &G)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1742
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:484
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1683
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:637
std::pair< BlockT *, bool > getExitBlockHelper(const LoopBase< BlockT, LoopT > *L, bool Unique)
getExitBlock - If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:77
void addInnerLoopsToHeadersMap(DenseMap< BlockT *, const LoopT * > &LoopHeaders, const LoopInfoBase< BlockT, LoopT > &LI, const LoopT &L)
Definition: LoopInfoImpl.h:649
void getUniqueExitBlocksHelper(const LoopT *L, SmallVectorImpl< BlockT * > &ExitBlocks, PredicateT Pred)
Definition: LoopInfoImpl.h:128
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)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1869
bool compareVectors(std::vector< T > &BB1, std::vector< T > &BB2)
Definition: LoopInfoImpl.h:642
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...
Definition: LoopInfoImpl.h:438
std::pair< iterator, bool > insert(NodeRef N)