LLVM 20.0.0git
GenericLoopInfo.h
Go to the documentation of this file.
1//===- GenericLoopInfo - Generic Loop Info for graphs -----------*- 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 file defines the LoopInfoBase class that is used to identify natural
10// loops and determine the loop depth of various nodes in a generic graph of
11// blocks. A natural loop has exactly one entry-point, which is called the
12// header. Note that natural loops may actually be several loops that share the
13// same header node.
14//
15// This analysis calculates the nesting structure of loops in a function. For
16// each natural loop identified, this analysis identifies natural loops
17// contained entirely within the loop and the basic blocks that make up the
18// loop.
19//
20// It can calculate on the fly various bits of information, for example:
21//
22// * whether there is a preheader for the loop
23// * the number of back edges to the header
24// * whether or not a particular block branches out of the loop
25// * the successor blocks of the loop
26// * the loop depth
27// * etc...
28//
29// Note that this analysis specifically identifies *Loops* not cycles or SCCs
30// in the graph. There can be strongly connected components in the graph which
31// this analysis will not recognize and that will not be represented by a Loop
32// instance. In particular, a Loop might be inside such a non-loop SCC, or a
33// non-loop SCC might contain a sub-SCC which is a Loop.
34//
35// For an overview of terminology used in this API (and thus all of our loop
36// analyses or transforms), see docs/LoopTerminology.rst.
37//
38//===----------------------------------------------------------------------===//
39
40#ifndef LLVM_SUPPORT_GENERICLOOPINFO_H
41#define LLVM_SUPPORT_GENERICLOOPINFO_H
42
43#include "llvm/ADT/DenseSet.h"
45#include "llvm/ADT/STLExtras.h"
49
50namespace llvm {
51
52template <class N, class M> class LoopInfoBase;
53template <class N, class M> class LoopBase;
54
55//===----------------------------------------------------------------------===//
56/// Instances of this class are used to represent loops that are detected in the
57/// flow graph.
58///
59template <class BlockT, class LoopT> class LoopBase {
60 LoopT *ParentLoop;
61 // Loops contained entirely within this one.
62 std::vector<LoopT *> SubLoops;
63
64 // The list of blocks in this loop. First entry is the header node.
65 std::vector<BlockT *> Blocks;
66
68
69#if LLVM_ENABLE_ABI_BREAKING_CHECKS
70 /// Indicator that this loop is no longer a valid loop.
71 bool IsInvalid = false;
72#endif
73
74 LoopBase(const LoopBase<BlockT, LoopT> &) = delete;
76 operator=(const LoopBase<BlockT, LoopT> &) = delete;
77
78public:
79 /// Return the nesting level of this loop. An outer-most loop has depth 1,
80 /// for consistency with loop depth values used for basic blocks, where depth
81 /// 0 is used for blocks not inside any loops.
82 unsigned getLoopDepth() const {
83 assert(!isInvalid() && "Loop not in a valid state!");
84 unsigned D = 1;
85 for (const LoopT *CurLoop = ParentLoop; CurLoop;
86 CurLoop = CurLoop->ParentLoop)
87 ++D;
88 return D;
89 }
90 BlockT *getHeader() const { return getBlocks().front(); }
91 /// Return the parent loop if it exists or nullptr for top
92 /// level loops.
93
94 /// A loop is either top-level in a function (that is, it is not
95 /// contained in any other loop) or it is entirely enclosed in
96 /// some other loop.
97 /// If a loop is top-level, it has no parent, otherwise its
98 /// parent is the innermost loop in which it is enclosed.
99 LoopT *getParentLoop() const { return ParentLoop; }
100
101 /// Get the outermost loop in which this loop is contained.
102 /// This may be the loop itself, if it already is the outermost loop.
103 const LoopT *getOutermostLoop() const {
104 const LoopT *L = static_cast<const LoopT *>(this);
105 while (L->ParentLoop)
106 L = L->ParentLoop;
107 return L;
108 }
109
111 LoopT *L = static_cast<LoopT *>(this);
112 while (L->ParentLoop)
113 L = L->ParentLoop;
114 return L;
115 }
116
117 /// This is a raw interface for bypassing addChildLoop.
118 void setParentLoop(LoopT *L) {
119 assert(!isInvalid() && "Loop not in a valid state!");
120 ParentLoop = L;
121 }
122
123 /// Return true if the specified loop is contained within in this loop.
124 bool contains(const LoopT *L) const {
125 assert(!isInvalid() && "Loop not in a valid state!");
126 if (L == this)
127 return true;
128 if (!L)
129 return false;
130 return contains(L->getParentLoop());
131 }
132
133 /// Return true if the specified basic block is in this loop.
134 bool contains(const BlockT *BB) const {
135 assert(!isInvalid() && "Loop not in a valid state!");
136 return DenseBlockSet.count(BB);
137 }
138
139 /// Return true if the specified instruction is in this loop.
140 template <class InstT> bool contains(const InstT *Inst) const {
141 return contains(Inst->getParent());
142 }
143
144 /// Return the loops contained entirely within this loop.
145 const std::vector<LoopT *> &getSubLoops() const {
146 assert(!isInvalid() && "Loop not in a valid state!");
147 return SubLoops;
148 }
149 std::vector<LoopT *> &getSubLoopsVector() {
150 assert(!isInvalid() && "Loop not in a valid state!");
151 return SubLoops;
152 }
153 typedef typename std::vector<LoopT *>::const_iterator iterator;
154 typedef
155 typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
156 iterator begin() const { return getSubLoops().begin(); }
157 iterator end() const { return getSubLoops().end(); }
158 reverse_iterator rbegin() const { return getSubLoops().rbegin(); }
159 reverse_iterator rend() const { return getSubLoops().rend(); }
160
161 // LoopInfo does not detect irreducible control flow, just natural
162 // loops. That is, it is possible that there is cyclic control
163 // flow within the "innermost loop" or around the "outermost
164 // loop".
165
166 /// Return true if the loop does not contain any (natural) loops.
167 bool isInnermost() const { return getSubLoops().empty(); }
168 /// Return true if the loop does not have a parent (natural) loop
169 // (i.e. it is outermost, which is the same as top-level).
170 bool isOutermost() const { return getParentLoop() == nullptr; }
171
172 /// Get a list of the basic blocks which make up this loop.
174 assert(!isInvalid() && "Loop not in a valid state!");
175 return Blocks;
176 }
178 block_iterator block_begin() const { return getBlocks().begin(); }
179 block_iterator block_end() const { return getBlocks().end(); }
181 assert(!isInvalid() && "Loop not in a valid state!");
182 return make_range(block_begin(), block_end());
183 }
184
185 /// Get the number of blocks in this loop in constant time.
186 /// Invalidate the loop, indicating that it is no longer a loop.
187 unsigned getNumBlocks() const {
188 assert(!isInvalid() && "Loop not in a valid state!");
189 return Blocks.size();
190 }
191
192 /// Return a direct, mutable handle to the blocks vector so that we can
193 /// mutate it efficiently with techniques like `std::remove`.
194 std::vector<BlockT *> &getBlocksVector() {
195 assert(!isInvalid() && "Loop not in a valid state!");
196 return Blocks;
197 }
198 /// Return a direct, mutable handle to the blocks set so that we can
199 /// mutate it efficiently.
201 assert(!isInvalid() && "Loop not in a valid state!");
202 return DenseBlockSet;
203 }
204
205 /// Return a direct, immutable handle to the blocks set.
207 assert(!isInvalid() && "Loop not in a valid state!");
208 return DenseBlockSet;
209 }
210
211 /// Return true if this loop is no longer valid. The only valid use of this
212 /// helper is "assert(L.isInvalid())" or equivalent, since IsInvalid is set to
213 /// true by the destructor. In other words, if this accessor returns true,
214 /// the caller has already triggered UB by calling this accessor; and so it
215 /// can only be called in a context where a return value of true indicates a
216 /// programmer error.
217 bool isInvalid() const {
218#if LLVM_ENABLE_ABI_BREAKING_CHECKS
219 return IsInvalid;
220#else
221 return false;
222#endif
223 }
224
225 /// True if terminator in the block can branch to another block that is
226 /// outside of the current loop. \p BB must be inside the loop.
227 bool isLoopExiting(const BlockT *BB) const {
228 assert(!isInvalid() && "Loop not in a valid state!");
229 assert(contains(BB) && "Exiting block must be part of the loop");
230 for (const auto *Succ : children<const BlockT *>(BB)) {
231 if (!contains(Succ))
232 return true;
233 }
234 return false;
235 }
236
237 /// Returns true if \p BB is a loop-latch.
238 /// A latch block is a block that contains a branch back to the header.
239 /// This function is useful when there are multiple latches in a loop
240 /// because \fn getLoopLatch will return nullptr in that case.
241 bool isLoopLatch(const BlockT *BB) const {
242 assert(!isInvalid() && "Loop not in a valid state!");
243 assert(contains(BB) && "block does not belong to the loop");
244 return llvm::is_contained(inverse_children<BlockT *>(getHeader()), BB);
245 }
246
247 /// Calculate the number of back edges to the loop header.
248 unsigned getNumBackEdges() const {
249 assert(!isInvalid() && "Loop not in a valid state!");
250 return llvm::count_if(inverse_children<BlockT *>(getHeader()),
251 [&](BlockT *Pred) { return contains(Pred); });
252 }
253
254 //===--------------------------------------------------------------------===//
255 // APIs for simple analysis of the loop.
256 //
257 // Note that all of these methods can fail on general loops (ie, there may not
258 // be a preheader, etc). For best success, the loop simplification and
259 // induction variable canonicalization pass should be used to normalize loops
260 // for easy analysis. These methods assume canonical loops.
261
262 /// Return all blocks inside the loop that have successors outside of the
263 /// loop. These are the blocks _inside of the current loop_ which branch out.
264 /// The returned list is always unique.
265 void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const;
266
267 /// If getExitingBlocks would return exactly one block, return that block.
268 /// Otherwise return null.
269 BlockT *getExitingBlock() const;
270
271 /// Return all of the successor blocks of this loop. These are the blocks
272 /// _outside of the current loop_ which are branched to.
273 void getExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
274
275 /// If getExitBlocks would return exactly one block, return that block.
276 /// Otherwise return null.
277 BlockT *getExitBlock() const;
278
279 /// Return true if no exit block for the loop has a predecessor that is
280 /// outside the loop.
281 bool hasDedicatedExits() const;
282
283 /// Return all unique successor blocks of this loop.
284 /// These are the blocks _outside of the current loop_ which are branched to.
285 void getUniqueExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
286
287 /// Return all unique successor blocks of this loop except successors from
288 /// Latch block are not considered. If the exit comes from Latch has also
289 /// non Latch predecessor in a loop it will be added to ExitBlocks.
290 /// These are the blocks _outside of the current loop_ which are branched to.
292
293 /// If getUniqueExitBlocks would return exactly one block, return that block.
294 /// Otherwise return null.
295 BlockT *getUniqueExitBlock() const;
296
297 /// Return true if this loop does not have any exit blocks.
298 bool hasNoExitBlocks() const;
299
300 /// Edge type.
301 typedef std::pair<BlockT *, BlockT *> Edge;
302
303 /// Return all pairs of (_inside_block_,_outside_block_).
304 void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const;
305
306 /// If there is a preheader for this loop, return it. A loop has a preheader
307 /// if there is only one edge to the header of the loop from outside of the
308 /// loop. If this is the case, the block branching to the header of the loop
309 /// is the preheader node.
310 ///
311 /// This method returns null if there is no preheader for the loop.
312 BlockT *getLoopPreheader() const;
313
314 /// If the given loop's header has exactly one unique predecessor outside the
315 /// loop, return it. Otherwise return null.
316 /// This is less strict that the loop "preheader" concept, which requires
317 /// the predecessor to have exactly one successor.
318 BlockT *getLoopPredecessor() const;
319
320 /// If there is a single latch block for this loop, return it.
321 /// A latch block is a block that contains a branch back to the header.
322 BlockT *getLoopLatch() const;
323
324 /// Return all loop latch blocks of this loop. A latch block is a block that
325 /// contains a branch back to the header.
326 void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
327 assert(!isInvalid() && "Loop not in a valid state!");
328 BlockT *H = getHeader();
329 for (const auto Pred : inverse_children<BlockT *>(H))
330 if (contains(Pred))
331 LoopLatches.push_back(Pred);
332 }
333
334 /// Return all inner loops in the loop nest rooted by the loop in preorder,
335 /// with siblings in forward program order.
336 template <class Type>
337 static void getInnerLoopsInPreorder(const LoopT &L,
338 SmallVectorImpl<Type> &PreOrderLoops) {
339 SmallVector<LoopT *, 4> PreOrderWorklist;
340 PreOrderWorklist.append(L.rbegin(), L.rend());
341
342 while (!PreOrderWorklist.empty()) {
343 LoopT *L = PreOrderWorklist.pop_back_val();
344 // Sub-loops are stored in forward program order, but will process the
345 // worklist backwards so append them in reverse order.
346 PreOrderWorklist.append(L->rbegin(), L->rend());
347 PreOrderLoops.push_back(L);
348 }
349 }
350
351 /// Return all loops in the loop nest rooted by the loop in preorder, with
352 /// siblings in forward program order.
354 SmallVector<const LoopT *, 4> PreOrderLoops;
355 const LoopT *CurLoop = static_cast<const LoopT *>(this);
356 PreOrderLoops.push_back(CurLoop);
357 getInnerLoopsInPreorder(*CurLoop, PreOrderLoops);
358 return PreOrderLoops;
359 }
361 SmallVector<LoopT *, 4> PreOrderLoops;
362 LoopT *CurLoop = static_cast<LoopT *>(this);
363 PreOrderLoops.push_back(CurLoop);
364 getInnerLoopsInPreorder(*CurLoop, PreOrderLoops);
365 return PreOrderLoops;
366 }
367
368 //===--------------------------------------------------------------------===//
369 // APIs for updating loop information after changing the CFG
370 //
371
372 /// This method is used by other analyses to update loop information.
373 /// NewBB is set to be a new member of the current loop.
374 /// Because of this, it is added as a member of all parent loops, and is added
375 /// to the specified LoopInfo object as being in the current basic block. It
376 /// is not valid to replace the loop header with this method.
377 void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI);
378
379 /// This is used when splitting loops up. It replaces the OldChild entry in
380 /// our children list with NewChild, and updates the parent pointer of
381 /// OldChild to be null and the NewChild to be this loop.
382 /// This updates the loop depth of the new child.
383 void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild);
384
385 /// Add the specified loop to be a child of this loop.
386 /// This updates the loop depth of the new child.
387 void addChildLoop(LoopT *NewChild) {
388 assert(!isInvalid() && "Loop not in a valid state!");
389 assert(!NewChild->ParentLoop && "NewChild already has a parent!");
390 NewChild->ParentLoop = static_cast<LoopT *>(this);
391 SubLoops.push_back(NewChild);
392 }
393
394 /// This removes the specified child from being a subloop of this loop. The
395 /// loop is not deleted, as it will presumably be inserted into another loop.
397 assert(!isInvalid() && "Loop not in a valid state!");
398 assert(I != SubLoops.end() && "Cannot remove end iterator!");
399 LoopT *Child = *I;
400 assert(Child->ParentLoop == this && "Child is not a child of this loop!");
401 SubLoops.erase(SubLoops.begin() + (I - begin()));
402 Child->ParentLoop = nullptr;
403 return Child;
404 }
405
406 /// This removes the specified child from being a subloop of this loop. The
407 /// loop is not deleted, as it will presumably be inserted into another loop.
408 LoopT *removeChildLoop(LoopT *Child) {
409 return removeChildLoop(llvm::find(*this, Child));
410 }
411
412 /// This adds a basic block directly to the basic block list.
413 /// This should only be used by transformations that create new loops. Other
414 /// transformations should use addBasicBlockToLoop.
415 void addBlockEntry(BlockT *BB) {
416 assert(!isInvalid() && "Loop not in a valid state!");
417 Blocks.push_back(BB);
418 DenseBlockSet.insert(BB);
419 }
420
421 /// interface to reverse Blocks[from, end of loop] in this loop
422 void reverseBlock(unsigned from) {
423 assert(!isInvalid() && "Loop not in a valid state!");
424 std::reverse(Blocks.begin() + from, Blocks.end());
425 }
426
427 /// interface to do reserve() for Blocks
428 void reserveBlocks(unsigned size) {
429 assert(!isInvalid() && "Loop not in a valid state!");
430 Blocks.reserve(size);
431 }
432
433 /// This method is used to move BB (which must be part of this loop) to be the
434 /// loop header of the loop (the block that dominates all others).
435 void moveToHeader(BlockT *BB) {
436 assert(!isInvalid() && "Loop not in a valid state!");
437 if (Blocks[0] == BB)
438 return;
439 for (unsigned i = 0;; ++i) {
440 assert(i != Blocks.size() && "Loop does not contain BB!");
441 if (Blocks[i] == BB) {
442 Blocks[i] = Blocks[0];
443 Blocks[0] = BB;
444 return;
445 }
446 }
447 }
448
449 /// This removes the specified basic block from the current loop, updating the
450 /// Blocks as appropriate. This does not update the mapping in the LoopInfo
451 /// class.
452 void removeBlockFromLoop(BlockT *BB) {
453 assert(!isInvalid() && "Loop not in a valid state!");
454 auto I = find(Blocks, BB);
455 assert(I != Blocks.end() && "N is not in this list!");
456 Blocks.erase(I);
457
458 DenseBlockSet.erase(BB);
459 }
460
461 /// Verify loop structure
462 void verifyLoop() const;
463
464 /// Verify loop structure of this loop and all nested loops.
466
467 /// Returns true if the loop is annotated parallel.
468 ///
469 /// Derived classes can override this method using static template
470 /// polymorphism.
471 bool isAnnotatedParallel() const { return false; }
472
473 /// Print loop with all the BBs inside it.
474 void print(raw_ostream &OS, bool Verbose = false, bool PrintNested = true,
475 unsigned Depth = 0) const;
476
477protected:
478 friend class LoopInfoBase<BlockT, LoopT>;
479
480 /// This creates an empty loop.
481 LoopBase() : ParentLoop(nullptr) {}
482
483 explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
484 Blocks.push_back(BB);
485 DenseBlockSet.insert(BB);
486 }
487
488 // Since loop passes like SCEV are allowed to key analysis results off of
489 // `Loop` pointers, we cannot re-use pointers within a loop pass manager.
490 // This means loop passes should not be `delete` ing `Loop` objects directly
491 // (and risk a later `Loop` allocation re-using the address of a previous one)
492 // but should be using LoopInfo::markAsRemoved, which keeps around the `Loop`
493 // pointer till the end of the lifetime of the `LoopInfo` object.
494 //
495 // To make it easier to follow this rule, we mark the destructor as
496 // non-public.
498 for (auto *SubLoop : SubLoops)
499 SubLoop->~LoopT();
500
501#if LLVM_ENABLE_ABI_BREAKING_CHECKS
502 IsInvalid = true;
503#endif
504 SubLoops.clear();
505 Blocks.clear();
506 DenseBlockSet.clear();
507 ParentLoop = nullptr;
508 }
509};
510
511template <class BlockT, class LoopT>
513 Loop.print(OS);
514 return OS;
515}
516
517//===----------------------------------------------------------------------===//
518/// This class builds and contains all of the top-level loop
519/// structures in the specified function.
520///
521
522template <class BlockT, class LoopT> class LoopInfoBase {
523 // BBMap - Mapping of basic blocks to the inner most loop they occur in
525 std::vector<LoopT *> TopLevelLoops;
526 BumpPtrAllocator LoopAllocator;
527
528 friend class LoopBase<BlockT, LoopT>;
529 friend class LoopInfo;
530
531 void operator=(const LoopInfoBase &) = delete;
532 LoopInfoBase(const LoopInfoBase &) = delete;
533
534public:
535 LoopInfoBase() = default;
537
539 : BBMap(std::move(Arg.BBMap)),
540 TopLevelLoops(std::move(Arg.TopLevelLoops)),
541 LoopAllocator(std::move(Arg.LoopAllocator)) {
542 // We have to clear the arguments top level loops as we've taken ownership.
543 Arg.TopLevelLoops.clear();
544 }
546 BBMap = std::move(RHS.BBMap);
547
548 for (auto *L : TopLevelLoops)
549 L->~LoopT();
550
551 TopLevelLoops = std::move(RHS.TopLevelLoops);
552 LoopAllocator = std::move(RHS.LoopAllocator);
553 RHS.TopLevelLoops.clear();
554 return *this;
555 }
556
558 BBMap.clear();
559
560 for (auto *L : TopLevelLoops)
561 L->~LoopT();
562 TopLevelLoops.clear();
563 LoopAllocator.Reset();
564 }
565
566 template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&...Args) {
567 LoopT *Storage = LoopAllocator.Allocate<LoopT>();
568 return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
569 }
570
571 /// iterator/begin/end - The interface to the top-level loops in the current
572 /// function.
573 ///
574 typedef typename std::vector<LoopT *>::const_iterator iterator;
575 typedef
576 typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
577 iterator begin() const { return TopLevelLoops.begin(); }
578 iterator end() const { return TopLevelLoops.end(); }
579 reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
580 reverse_iterator rend() const { return TopLevelLoops.rend(); }
581 bool empty() const { return TopLevelLoops.empty(); }
582
583 /// Return all of the loops in the function in preorder across the loop
584 /// nests, with siblings in forward program order.
585 ///
586 /// Note that because loops form a forest of trees, preorder is equivalent to
587 /// reverse postorder.
589
590 /// Return all of the loops in the function in preorder across the loop
591 /// nests, with siblings in *reverse* program order.
592 ///
593 /// Note that because loops form a forest of trees, preorder is equivalent to
594 /// reverse postorder.
595 ///
596 /// Also note that this is *not* a reverse preorder. Only the siblings are in
597 /// reverse program order.
599
600 /// Return the inner most loop that BB lives in. If a basic block is in no
601 /// loop (for example the entry node), null is returned.
602 LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
603
604 /// Same as getLoopFor.
605 const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); }
606
607 /// Return the loop nesting level of the specified block. A depth of 0 means
608 /// the block is not inside any loop.
609 unsigned getLoopDepth(const BlockT *BB) const {
610 const LoopT *L = getLoopFor(BB);
611 return L ? L->getLoopDepth() : 0;
612 }
613
614 // True if the block is a loop header node
615 bool isLoopHeader(const BlockT *BB) const {
616 const LoopT *L = getLoopFor(BB);
617 return L && L->getHeader() == BB;
618 }
619
620 /// Return the top-level loops.
621 const std::vector<LoopT *> &getTopLevelLoops() const { return TopLevelLoops; }
622
623 /// Return the top-level loops.
624 std::vector<LoopT *> &getTopLevelLoopsVector() { return TopLevelLoops; }
625
626 /// This removes the specified top-level loop from this loop info object.
627 /// The loop is not deleted, as it will presumably be inserted into
628 /// another loop.
630 assert(I != end() && "Cannot remove end iterator!");
631 LoopT *L = *I;
632 assert(L->isOutermost() && "Not a top-level loop!");
633 TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));
634 return L;
635 }
636
637 /// Change the top-level loop that contains BB to the specified loop.
638 /// This should be used by transformations that restructure the loop hierarchy
639 /// tree.
640 void changeLoopFor(BlockT *BB, LoopT *L) {
641 if (!L) {
642 BBMap.erase(BB);
643 return;
644 }
645 BBMap[BB] = L;
646 }
647
648 /// Replace the specified loop in the top-level loops list with the indicated
649 /// loop.
650 void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) {
651 auto I = find(TopLevelLoops, OldLoop);
652 assert(I != TopLevelLoops.end() && "Old loop not at top level!");
653 *I = NewLoop;
654 assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
655 "Loops already embedded into a subloop!");
656 }
657
658 /// This adds the specified loop to the collection of top-level loops.
659 void addTopLevelLoop(LoopT *New) {
660 assert(New->isOutermost() && "Loop already in subloop!");
661 TopLevelLoops.push_back(New);
662 }
663
664 /// This method completely removes BB from all data structures,
665 /// including all of the Loop objects it is nested in and our mapping from
666 /// BasicBlocks to loops.
667 void removeBlock(BlockT *BB) {
668 auto I = BBMap.find(BB);
669 if (I != BBMap.end()) {
670 for (LoopT *L = I->second; L; L = L->getParentLoop())
671 L->removeBlockFromLoop(BB);
672
673 BBMap.erase(I);
674 }
675 }
676
677 // Internals
678
679 static bool isNotAlreadyContainedIn(const LoopT *SubLoop,
680 const LoopT *ParentLoop) {
681 if (!SubLoop)
682 return true;
683 if (SubLoop == ParentLoop)
684 return false;
685 return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
686 }
687
688 /// Create the loop forest using a stable algorithm.
689 void analyze(const DominatorTreeBase<BlockT, false> &DomTree);
690
691 // Debugging
692 void print(raw_ostream &OS) const;
693
694 void verify(const DominatorTreeBase<BlockT, false> &DomTree) const;
695
696 /// Destroy a loop that has been removed from the `LoopInfo` nest.
697 ///
698 /// This runs the destructor of the loop object making it invalid to
699 /// reference afterward. The memory is retained so that the *pointer* to the
700 /// loop remains valid.
701 ///
702 /// The caller is responsible for removing this loop from the loop nest and
703 /// otherwise disconnecting it from the broader `LoopInfo` data structures.
704 /// Callers that don't naturally handle this themselves should probably call
705 /// `erase' instead.
706 void destroy(LoopT *L) {
707 L->~LoopT();
708
709 // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons
710 // \c L, but the pointer remains valid for non-dereferencing uses.
711 LoopAllocator.Deallocate(L);
712 }
713};
714
715} // namespace llvm
716
717#endif // LLVM_SUPPORT_GENERICLOOPINFO_H
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
This file defines the DenseSet and SmallDenseSet classes.
DenseMap< Block *, BlockRelaxAux > Blocks
Definition: ELF_riscv.cpp:507
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
Hexagon Hardware Loops
#define I(x, y, z)
Definition: MD5.cpp:58
#define H(x, y, z)
Definition: MD5.cpp:57
ppc ctr loops verify
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,...
Value * RHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:148
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
Definition: Allocator.h:123
void Deallocate(const void *Ptr, size_t Size, size_t)
Definition: Allocator.h:225
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
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
bool erase(const KeyT &Val)
Definition: DenseMap.h:336
iterator end()
Definition: DenseMap.h:84
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Core dominator tree base class.
Instances of this class are used to represent loops that are detected in the flow graph.
bool isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
SmallPtrSetImpl< const BlockT * > & getBlocksSet()
Return a direct, mutable handle to the blocks set so that we can mutate it efficiently.
static void getInnerLoopsInPreorder(const LoopT &L, SmallVectorImpl< Type > &PreOrderLoops)
Return all inner loops in the loop nest rooted by the loop in preorder, with siblings in forward prog...
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
void removeBlockFromLoop(BlockT *BB)
This removes the specified basic block from the current loop, updating the Blocks as appropriate.
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
bool contains(const InstT *Inst) const
Return true if the specified instruction is in this loop.
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
void verifyLoop() const
Verify loop structure.
void verifyLoopNest(DenseSet< const LoopT * > *Loops) const
Verify loop structure of this loop and all nested loops.
SmallVector< LoopT *, 4 > getLoopsInPreorder()
unsigned getNumBackEdges() const
Calculate the number of back edges to the loop header.
void reverseBlock(unsigned from)
interface to reverse Blocks[from, end of loop] in this loop
SmallVector< const LoopT *, 4 > getLoopsInPreorder() const
Return all loops in the loop nest rooted by the loop in preorder, with siblings in forward program or...
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
LoopBase(BlockT *BB)
const std::vector< LoopT * > & getSubLoops() const
Return the loops contained entirely within this loop.
BlockT * getHeader() const
const LoopT * getOutermostLoop() const
Get the outermost loop in which this loop is contained.
void getLoopLatches(SmallVectorImpl< BlockT * > &LoopLatches) const
Return all loop latch blocks of this loop.
unsigned getLoopDepth() const
Return the nesting level of this loop.
LoopBase()
This creates an empty 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< BlockT * > & getBlocksVector()
Return a direct, mutable handle to the blocks vector so that we can mutate it efficiently with techni...
std::vector< LoopT * >::const_reverse_iterator reverse_iterator
LoopT * removeChildLoop(LoopT *Child)
This removes the specified child from being a subloop of this loop.
std::vector< LoopT * >::const_iterator iterator
void reserveBlocks(unsigned size)
interface to do reserve() for Blocks
iterator_range< block_iterator > blocks() const
block_iterator block_end() const
std::pair< BlockT *, BlockT * > Edge
Edge type.
bool isInvalid() const
Return true if this loop is no longer valid.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
bool contains(const BlockT *BB) const
Return true if the specified basic block is in this loop.
bool isLoopLatch(const BlockT *BB) const
iterator end() const
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
void addBlockEntry(BlockT *BB)
This adds a basic block directly to the basic block list.
ArrayRef< BlockT * >::const_iterator block_iterator
std::vector< LoopT * > & getSubLoopsVector()
reverse_iterator rbegin() const
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.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
reverse_iterator rend() const
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
LoopT * getOutermostLoop()
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
void setParentLoop(LoopT *L)
This is a raw interface for bypassing addChildLoop.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
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...
iterator begin() const
const SmallPtrSetImpl< const BlockT * > & getBlocksSet() const
Return a direct, immutable handle to the blocks set.
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
block_iterator block_begin() const
void moveToHeader(BlockT *BB)
This method is used to move BB (which must be part of this loop) to be the loop header of the loop (t...
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
This class builds and contains all of the top-level loop structures in the specified function.
const std::vector< LoopT * > & getTopLevelLoops() const
Return the top-level loops.
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
reverse_iterator rend() const
void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop)
Replace the specified loop in the top-level loops list with the indicated loop.
iterator end() const
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
LoopInfoBase(LoopInfoBase &&Arg)
LoopT * AllocateLoop(ArgsTy &&...Args)
const LoopT * operator[](const BlockT *BB) const
Same as getLoopFor.
bool isLoopHeader(const BlockT *BB) const
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
LoopInfoBase()=default
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.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
std::vector< LoopT * > & getTopLevelLoopsVector()
Return the top-level loops.
iterator begin() const
static bool isNotAlreadyContainedIn(const LoopT *SubLoop, const LoopT *ParentLoop)
std::vector< LoopT * >::const_reverse_iterator reverse_iterator
reverse_iterator rbegin() const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
LoopInfoBase & operator=(LoopInfoBase &&RHS)
void destroy(LoopT *L)
Destroy a loop that has been removed from the LoopInfo nest.
std::vector< LoopT * >::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:347
bool erase(PtrType Ptr)
Remove pointer from the set.
Definition: SmallPtrSet.h:385
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
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
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1680
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1849
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:1921
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858