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"
44#include "llvm/ADT/PostOrderIterator.h"
45#include "llvm/ADT/STLExtras.h"
46#include "llvm/ADT/SetOperations.h"
47#include "llvm/Support/Allocator.h"
48#include "llvm/Support/GenericDomTree.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
67 SmallPtrSet<const BlockT *, 8> DenseBlockSet;
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;
75 const LoopBase<BlockT, LoopT> &
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
110 LoopT *getOutermostLoop() {
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.
173 ArrayRef<BlockT *> getBlocks() const {
174 assert(!isInvalid() && "Loop not in a valid state!");
175 return Blocks;
176 }
177 typedef typename ArrayRef<BlockT *>::const_iterator block_iterator;
178 block_iterator block_begin() const { return getBlocks().begin(); }
179 block_iterator block_end() const { return getBlocks().end(); }
180 inline iterator_range<block_iterator> blocks() const {
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.
200 SmallPtrSetImpl<const BlockT *> &getBlocksSet() {
201 assert(!isInvalid() && "Loop not in a valid state!");
202 return DenseBlockSet;
203 }
204
205 /// Return a direct, immutable handle to the blocks set.
206 const SmallPtrSetImpl<const BlockT *> &getBlocksSet() const {
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.
291 void getUniqueNonLatchExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
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.
353 SmallVector<const LoopT *, 4> getLoopsInPreorder() const {
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 }
360 SmallVector<LoopT *, 4> getLoopsInPreorder() {
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.
396 LoopT *removeChildLoop(iterator I) {
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.
465 void verifyLoopNest(DenseSet<const LoopT *> *Loops) const;
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.
497 ~LoopBase() {
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>
512raw_ostream &operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
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
524 DenseMap<const BlockT *, LoopT *> BBMap;
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;
536 ~LoopInfoBase() { releaseMemory(); }
537
538 LoopInfoBase(LoopInfoBase &&Arg)
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 }
545 LoopInfoBase &operator=(LoopInfoBase &&RHS) {
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
557 void releaseMemory() {
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.
588 SmallVector<LoopT *, 4> getLoopsInPreorder() const;
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.
598 SmallVector<LoopT *, 4> getLoopsInReverseSiblingPreorder() const;
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.
629 LoopT *removeLoop(iterator I) {
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: 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
718

source code of llvm/include/llvm/Support/GenericLoopInfo.h