LLVM 18.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
245 BlockT *Header = getHeader();
246 auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header);
247 auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header);
248 return std::find(PredBegin, PredEnd, BB) != PredEnd;
249 }
250
251 /// Calculate the number of back edges to the loop header.
252 unsigned getNumBackEdges() const {
253 assert(!isInvalid() && "Loop not in a valid state!");
254 unsigned NumBackEdges = 0;
255 BlockT *H = getHeader();
256
257 for (const auto Pred : children<Inverse<BlockT *>>(H))
258 if (contains(Pred))
259 ++NumBackEdges;
260
261 return NumBackEdges;
262 }
263
264 //===--------------------------------------------------------------------===//
265 // APIs for simple analysis of the loop.
266 //
267 // Note that all of these methods can fail on general loops (ie, there may not
268 // be a preheader, etc). For best success, the loop simplification and
269 // induction variable canonicalization pass should be used to normalize loops
270 // for easy analysis. These methods assume canonical loops.
271
272 /// Return all blocks inside the loop that have successors outside of the
273 /// loop. These are the blocks _inside of the current loop_ which branch out.
274 /// The returned list is always unique.
275 void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const;
276
277 /// If getExitingBlocks would return exactly one block, return that block.
278 /// Otherwise return null.
279 BlockT *getExitingBlock() const;
280
281 /// Return all of the successor blocks of this loop. These are the blocks
282 /// _outside of the current loop_ which are branched to.
283 void getExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
284
285 /// If getExitBlocks would return exactly one block, return that block.
286 /// Otherwise return null.
287 BlockT *getExitBlock() const;
288
289 /// Return true if no exit block for the loop has a predecessor that is
290 /// outside the loop.
291 bool hasDedicatedExits() const;
292
293 /// Return all unique successor blocks of this loop.
294 /// These are the blocks _outside of the current loop_ which are branched to.
295 void getUniqueExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
296
297 /// Return all unique successor blocks of this loop except successors from
298 /// Latch block are not considered. If the exit comes from Latch has also
299 /// non Latch predecessor in a loop it will be added to ExitBlocks.
300 /// These are the blocks _outside of the current loop_ which are branched to.
302
303 /// If getUniqueExitBlocks would return exactly one block, return that block.
304 /// Otherwise return null.
305 BlockT *getUniqueExitBlock() const;
306
307 /// Return true if this loop does not have any exit blocks.
308 bool hasNoExitBlocks() const;
309
310 /// Edge type.
311 typedef std::pair<BlockT *, BlockT *> Edge;
312
313 /// Return all pairs of (_inside_block_,_outside_block_).
314 void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const;
315
316 /// If there is a preheader for this loop, return it. A loop has a preheader
317 /// if there is only one edge to the header of the loop from outside of the
318 /// loop. If this is the case, the block branching to the header of the loop
319 /// is the preheader node.
320 ///
321 /// This method returns null if there is no preheader for the loop.
322 BlockT *getLoopPreheader() const;
323
324 /// If the given loop's header has exactly one unique predecessor outside the
325 /// loop, return it. Otherwise return null.
326 /// This is less strict that the loop "preheader" concept, which requires
327 /// the predecessor to have exactly one successor.
328 BlockT *getLoopPredecessor() const;
329
330 /// If there is a single latch block for this loop, return it.
331 /// A latch block is a block that contains a branch back to the header.
332 BlockT *getLoopLatch() const;
333
334 /// Return all loop latch blocks of this loop. A latch block is a block that
335 /// contains a branch back to the header.
336 void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
337 assert(!isInvalid() && "Loop not in a valid state!");
338 BlockT *H = getHeader();
339 for (const auto Pred : children<Inverse<BlockT *>>(H))
340 if (contains(Pred))
341 LoopLatches.push_back(Pred);
342 }
343
344 /// Return all inner loops in the loop nest rooted by the loop in preorder,
345 /// with siblings in forward program order.
346 template <class Type>
347 static void getInnerLoopsInPreorder(const LoopT &L,
348 SmallVectorImpl<Type> &PreOrderLoops) {
349 SmallVector<LoopT *, 4> PreOrderWorklist;
350 PreOrderWorklist.append(L.rbegin(), L.rend());
351
352 while (!PreOrderWorklist.empty()) {
353 LoopT *L = PreOrderWorklist.pop_back_val();
354 // Sub-loops are stored in forward program order, but will process the
355 // worklist backwards so append them in reverse order.
356 PreOrderWorklist.append(L->rbegin(), L->rend());
357 PreOrderLoops.push_back(L);
358 }
359 }
360
361 /// Return all loops in the loop nest rooted by the loop in preorder, with
362 /// siblings in forward program order.
364 SmallVector<const LoopT *, 4> PreOrderLoops;
365 const LoopT *CurLoop = static_cast<const LoopT *>(this);
366 PreOrderLoops.push_back(CurLoop);
367 getInnerLoopsInPreorder(*CurLoop, PreOrderLoops);
368 return PreOrderLoops;
369 }
371 SmallVector<LoopT *, 4> PreOrderLoops;
372 LoopT *CurLoop = static_cast<LoopT *>(this);
373 PreOrderLoops.push_back(CurLoop);
374 getInnerLoopsInPreorder(*CurLoop, PreOrderLoops);
375 return PreOrderLoops;
376 }
377
378 //===--------------------------------------------------------------------===//
379 // APIs for updating loop information after changing the CFG
380 //
381
382 /// This method is used by other analyses to update loop information.
383 /// NewBB is set to be a new member of the current loop.
384 /// Because of this, it is added as a member of all parent loops, and is added
385 /// to the specified LoopInfo object as being in the current basic block. It
386 /// is not valid to replace the loop header with this method.
387 void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI);
388
389 /// This is used when splitting loops up. It replaces the OldChild entry in
390 /// our children list with NewChild, and updates the parent pointer of
391 /// OldChild to be null and the NewChild to be this loop.
392 /// This updates the loop depth of the new child.
393 void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild);
394
395 /// Add the specified loop to be a child of this loop.
396 /// This updates the loop depth of the new child.
397 void addChildLoop(LoopT *NewChild) {
398 assert(!isInvalid() && "Loop not in a valid state!");
399 assert(!NewChild->ParentLoop && "NewChild already has a parent!");
400 NewChild->ParentLoop = static_cast<LoopT *>(this);
401 SubLoops.push_back(NewChild);
402 }
403
404 /// This removes the specified child from being a subloop of this loop. The
405 /// loop is not deleted, as it will presumably be inserted into another loop.
407 assert(!isInvalid() && "Loop not in a valid state!");
408 assert(I != SubLoops.end() && "Cannot remove end iterator!");
409 LoopT *Child = *I;
410 assert(Child->ParentLoop == this && "Child is not a child of this loop!");
411 SubLoops.erase(SubLoops.begin() + (I - begin()));
412 Child->ParentLoop = nullptr;
413 return Child;
414 }
415
416 /// This removes the specified child from being a subloop of this loop. The
417 /// loop is not deleted, as it will presumably be inserted into another loop.
418 LoopT *removeChildLoop(LoopT *Child) {
419 return removeChildLoop(llvm::find(*this, Child));
420 }
421
422 /// This adds a basic block directly to the basic block list.
423 /// This should only be used by transformations that create new loops. Other
424 /// transformations should use addBasicBlockToLoop.
425 void addBlockEntry(BlockT *BB) {
426 assert(!isInvalid() && "Loop not in a valid state!");
427 Blocks.push_back(BB);
428 DenseBlockSet.insert(BB);
429 }
430
431 /// interface to reverse Blocks[from, end of loop] in this loop
432 void reverseBlock(unsigned from) {
433 assert(!isInvalid() && "Loop not in a valid state!");
434 std::reverse(Blocks.begin() + from, Blocks.end());
435 }
436
437 /// interface to do reserve() for Blocks
438 void reserveBlocks(unsigned size) {
439 assert(!isInvalid() && "Loop not in a valid state!");
440 Blocks.reserve(size);
441 }
442
443 /// This method is used to move BB (which must be part of this loop) to be the
444 /// loop header of the loop (the block that dominates all others).
445 void moveToHeader(BlockT *BB) {
446 assert(!isInvalid() && "Loop not in a valid state!");
447 if (Blocks[0] == BB)
448 return;
449 for (unsigned i = 0;; ++i) {
450 assert(i != Blocks.size() && "Loop does not contain BB!");
451 if (Blocks[i] == BB) {
452 Blocks[i] = Blocks[0];
453 Blocks[0] = BB;
454 return;
455 }
456 }
457 }
458
459 /// This removes the specified basic block from the current loop, updating the
460 /// Blocks as appropriate. This does not update the mapping in the LoopInfo
461 /// class.
462 void removeBlockFromLoop(BlockT *BB) {
463 assert(!isInvalid() && "Loop not in a valid state!");
464 auto I = find(Blocks, BB);
465 assert(I != Blocks.end() && "N is not in this list!");
466 Blocks.erase(I);
467
468 DenseBlockSet.erase(BB);
469 }
470
471 /// Verify loop structure
472 void verifyLoop() const;
473
474 /// Verify loop structure of this loop and all nested loops.
476
477 /// Returns true if the loop is annotated parallel.
478 ///
479 /// Derived classes can override this method using static template
480 /// polymorphism.
481 bool isAnnotatedParallel() const { return false; }
482
483 /// Print loop with all the BBs inside it.
484 void print(raw_ostream &OS, bool Verbose = false, bool PrintNested = true,
485 unsigned Depth = 0) const;
486
487protected:
488 friend class LoopInfoBase<BlockT, LoopT>;
489
490 /// This creates an empty loop.
491 LoopBase() : ParentLoop(nullptr) {}
492
493 explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
494 Blocks.push_back(BB);
495 DenseBlockSet.insert(BB);
496 }
497
498 // Since loop passes like SCEV are allowed to key analysis results off of
499 // `Loop` pointers, we cannot re-use pointers within a loop pass manager.
500 // This means loop passes should not be `delete` ing `Loop` objects directly
501 // (and risk a later `Loop` allocation re-using the address of a previous one)
502 // but should be using LoopInfo::markAsRemoved, which keeps around the `Loop`
503 // pointer till the end of the lifetime of the `LoopInfo` object.
504 //
505 // To make it easier to follow this rule, we mark the destructor as
506 // non-public.
508 for (auto *SubLoop : SubLoops)
509 SubLoop->~LoopT();
510
511#if LLVM_ENABLE_ABI_BREAKING_CHECKS
512 IsInvalid = true;
513#endif
514 SubLoops.clear();
515 Blocks.clear();
516 DenseBlockSet.clear();
517 ParentLoop = nullptr;
518 }
519};
520
521template <class BlockT, class LoopT>
523 Loop.print(OS);
524 return OS;
525}
526
527//===----------------------------------------------------------------------===//
528/// This class builds and contains all of the top-level loop
529/// structures in the specified function.
530///
531
532template <class BlockT, class LoopT> class LoopInfoBase {
533 // BBMap - Mapping of basic blocks to the inner most loop they occur in
535 std::vector<LoopT *> TopLevelLoops;
536 BumpPtrAllocator LoopAllocator;
537
538 friend class LoopBase<BlockT, LoopT>;
539 friend class LoopInfo;
540
541 void operator=(const LoopInfoBase &) = delete;
542 LoopInfoBase(const LoopInfoBase &) = delete;
543
544public:
545 LoopInfoBase() = default;
547
549 : BBMap(std::move(Arg.BBMap)),
550 TopLevelLoops(std::move(Arg.TopLevelLoops)),
551 LoopAllocator(std::move(Arg.LoopAllocator)) {
552 // We have to clear the arguments top level loops as we've taken ownership.
553 Arg.TopLevelLoops.clear();
554 }
556 BBMap = std::move(RHS.BBMap);
557
558 for (auto *L : TopLevelLoops)
559 L->~LoopT();
560
561 TopLevelLoops = std::move(RHS.TopLevelLoops);
562 LoopAllocator = std::move(RHS.LoopAllocator);
563 RHS.TopLevelLoops.clear();
564 return *this;
565 }
566
568 BBMap.clear();
569
570 for (auto *L : TopLevelLoops)
571 L->~LoopT();
572 TopLevelLoops.clear();
573 LoopAllocator.Reset();
574 }
575
576 template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&...Args) {
577 LoopT *Storage = LoopAllocator.Allocate<LoopT>();
578 return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
579 }
580
581 /// iterator/begin/end - The interface to the top-level loops in the current
582 /// function.
583 ///
584 typedef typename std::vector<LoopT *>::const_iterator iterator;
585 typedef
586 typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
587 iterator begin() const { return TopLevelLoops.begin(); }
588 iterator end() const { return TopLevelLoops.end(); }
589 reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
590 reverse_iterator rend() const { return TopLevelLoops.rend(); }
591 bool empty() const { return TopLevelLoops.empty(); }
592
593 /// Return all of the loops in the function in preorder across the loop
594 /// nests, with siblings in forward program order.
595 ///
596 /// Note that because loops form a forest of trees, preorder is equivalent to
597 /// reverse postorder.
599
600 /// Return all of the loops in the function in preorder across the loop
601 /// nests, with siblings in *reverse* program order.
602 ///
603 /// Note that because loops form a forest of trees, preorder is equivalent to
604 /// reverse postorder.
605 ///
606 /// Also note that this is *not* a reverse preorder. Only the siblings are in
607 /// reverse program order.
609
610 /// Return the inner most loop that BB lives in. If a basic block is in no
611 /// loop (for example the entry node), null is returned.
612 LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
613
614 /// Same as getLoopFor.
615 const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); }
616
617 /// Return the loop nesting level of the specified block. A depth of 0 means
618 /// the block is not inside any loop.
619 unsigned getLoopDepth(const BlockT *BB) const {
620 const LoopT *L = getLoopFor(BB);
621 return L ? L->getLoopDepth() : 0;
622 }
623
624 // True if the block is a loop header node
625 bool isLoopHeader(const BlockT *BB) const {
626 const LoopT *L = getLoopFor(BB);
627 return L && L->getHeader() == BB;
628 }
629
630 /// Return the top-level loops.
631 const std::vector<LoopT *> &getTopLevelLoops() const { return TopLevelLoops; }
632
633 /// Return the top-level loops.
634 std::vector<LoopT *> &getTopLevelLoopsVector() { return TopLevelLoops; }
635
636 /// This removes the specified top-level loop from this loop info object.
637 /// The loop is not deleted, as it will presumably be inserted into
638 /// another loop.
640 assert(I != end() && "Cannot remove end iterator!");
641 LoopT *L = *I;
642 assert(L->isOutermost() && "Not a top-level loop!");
643 TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));
644 return L;
645 }
646
647 /// Change the top-level loop that contains BB to the specified loop.
648 /// This should be used by transformations that restructure the loop hierarchy
649 /// tree.
650 void changeLoopFor(BlockT *BB, LoopT *L) {
651 if (!L) {
652 BBMap.erase(BB);
653 return;
654 }
655 BBMap[BB] = L;
656 }
657
658 /// Replace the specified loop in the top-level loops list with the indicated
659 /// loop.
660 void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) {
661 auto I = find(TopLevelLoops, OldLoop);
662 assert(I != TopLevelLoops.end() && "Old loop not at top level!");
663 *I = NewLoop;
664 assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
665 "Loops already embedded into a subloop!");
666 }
667
668 /// This adds the specified loop to the collection of top-level loops.
669 void addTopLevelLoop(LoopT *New) {
670 assert(New->isOutermost() && "Loop already in subloop!");
671 TopLevelLoops.push_back(New);
672 }
673
674 /// This method completely removes BB from all data structures,
675 /// including all of the Loop objects it is nested in and our mapping from
676 /// BasicBlocks to loops.
677 void removeBlock(BlockT *BB) {
678 auto I = BBMap.find(BB);
679 if (I != BBMap.end()) {
680 for (LoopT *L = I->second; L; L = L->getParentLoop())
681 L->removeBlockFromLoop(BB);
682
683 BBMap.erase(I);
684 }
685 }
686
687 // Internals
688
689 static bool isNotAlreadyContainedIn(const LoopT *SubLoop,
690 const LoopT *ParentLoop) {
691 if (!SubLoop)
692 return true;
693 if (SubLoop == ParentLoop)
694 return false;
695 return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
696 }
697
698 /// Create the loop forest using a stable algorithm.
699 void analyze(const DominatorTreeBase<BlockT, false> &DomTree);
700
701 // Debugging
702 void print(raw_ostream &OS) const;
703
704 void verify(const DominatorTreeBase<BlockT, false> &DomTree) const;
705
706 /// Destroy a loop that has been removed from the `LoopInfo` nest.
707 ///
708 /// This runs the destructor of the loop object making it invalid to
709 /// reference afterward. The memory is retained so that the *pointer* to the
710 /// loop remains valid.
711 ///
712 /// The caller is responsible for removing this loop from the loop nest and
713 /// otherwise disconnecting it from the broader `LoopInfo` data structures.
714 /// Callers that don't naturally handle this themselves should probably call
715 /// `erase' instead.
716 void destroy(LoopT *L) {
717 L->~LoopT();
718
719 // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons
720 // \c L, but the pointer remains valid for non-dereferencing uses.
721 LoopAllocator.Deallocate(L);
722 }
723};
724
725} // namespace llvm
726
727#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:496
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:218
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:202
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
bool erase(const KeyT &Val)
Definition: DenseMap.h:329
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:47
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:380
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:384
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
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
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:1747
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:1685
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:292
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:1854
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:123
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858