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 | |
50 | namespace llvm { |
51 | |
52 | template <class N, class M> class LoopInfoBase; |
53 | template <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 | /// |
59 | template <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 | |
78 | public: |
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 *() 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 *() 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 (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 | |
477 | protected: |
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 | |
511 | template <class BlockT, class LoopT> |
512 | raw_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 | |
522 | template <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 | |
534 | public: |
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 (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 | |