1//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the LoopInfo class that is used to identify natural loops
10// and determine the loop depth of various nodes of the CFG. A natural loop
11// has exactly one entry-point, which is called the header. Note that natural
12// loops may actually be several loops that share the same header node.
13//
14// This analysis calculates the nesting structure of loops in a function. For
15// each natural loop identified, this analysis identifies natural loops
16// contained entirely within the loop and the basic blocks the make up the loop.
17//
18// It can calculate on the fly various bits of information, for example:
19//
20// * whether there is a preheader for the loop
21// * the number of back edges to the header
22// * whether or not a particular block branches out of the loop
23// * the successor blocks of the loop
24// * the loop depth
25// * etc...
26//
27// Note that this analysis specifically identifies *Loops* not cycles or SCCs
28// in the CFG. There can be strongly connected components in the CFG which
29// this analysis will not recognize and that will not be represented by a Loop
30// instance. In particular, a Loop might be inside such a non-loop SCC, or a
31// non-loop SCC might contain a sub-SCC which is a Loop.
32//
33// For an overview of terminology used in this API (and thus all of our loop
34// analyses or transforms), see docs/LoopTerminology.rst.
35//
36//===----------------------------------------------------------------------===//
37
38#ifndef LLVM_ANALYSIS_LOOPINFO_H
39#define LLVM_ANALYSIS_LOOPINFO_H
40
41#include "llvm/ADT/DenseMap.h"
42#include "llvm/ADT/DenseSet.h"
43#include "llvm/ADT/GraphTraits.h"
44#include "llvm/ADT/SmallPtrSet.h"
45#include "llvm/ADT/SmallVector.h"
46#include "llvm/IR/CFG.h"
47#include "llvm/IR/Instruction.h"
48#include "llvm/IR/Instructions.h"
49#include "llvm/IR/PassManager.h"
50#include "llvm/Pass.h"
51#include "llvm/Support/Allocator.h"
52#include <algorithm>
53#include <utility>
54
55namespace llvm {
56
57class DominatorTree;
58class LoopInfo;
59class Loop;
60class InductionDescriptor;
61class MDNode;
62class MemorySSAUpdater;
63class ScalarEvolution;
64class raw_ostream;
65template <class N, bool IsPostDom> class DominatorTreeBase;
66template <class N, class M> class LoopInfoBase;
67template <class N, class M> class LoopBase;
68
69//===----------------------------------------------------------------------===//
70/// Instances of this class are used to represent loops that are detected in the
71/// flow graph.
72///
73template <class BlockT, class LoopT> class LoopBase {
74 LoopT *ParentLoop;
75 // Loops contained entirely within this one.
76 std::vector<LoopT *> SubLoops;
77
78 // The list of blocks in this loop. First entry is the header node.
79 std::vector<BlockT *> Blocks;
80
81 SmallPtrSet<const BlockT *, 8> DenseBlockSet;
82
83#if LLVM_ENABLE_ABI_BREAKING_CHECKS
84 /// Indicator that this loop is no longer a valid loop.
85 bool IsInvalid = false;
86#endif
87
88 LoopBase(const LoopBase<BlockT, LoopT> &) = delete;
89 const LoopBase<BlockT, LoopT> &
90 operator=(const LoopBase<BlockT, LoopT> &) = delete;
91
92public:
93 /// Return the nesting level of this loop. An outer-most loop has depth 1,
94 /// for consistency with loop depth values used for basic blocks, where depth
95 /// 0 is used for blocks not inside any loops.
96 unsigned getLoopDepth() const {
97 assert(!isInvalid() && "Loop not in a valid state!");
98 unsigned D = 1;
99 for (const LoopT *CurLoop = ParentLoop; CurLoop;
100 CurLoop = CurLoop->ParentLoop)
101 ++D;
102 return D;
103 }
104 BlockT *getHeader() const { return getBlocks().front(); }
105 /// Return the parent loop if it exists or nullptr for top
106 /// level loops.
107
108 /// A loop is either top-level in a function (that is, it is not
109 /// contained in any other loop) or it is entirely enclosed in
110 /// some other loop.
111 /// If a loop is top-level, it has no parent, otherwise its
112 /// parent is the innermost loop in which it is enclosed.
113 LoopT *getParentLoop() const { return ParentLoop; }
114
115 /// This is a raw interface for bypassing addChildLoop.
116 void setParentLoop(LoopT *L) {
117 assert(!isInvalid() && "Loop not in a valid state!");
118 ParentLoop = L;
119 }
120
121 /// Return true if the specified loop is contained within in this loop.
122 bool contains(const LoopT *L) const {
123 assert(!isInvalid() && "Loop not in a valid state!");
124 if (L == this)
125 return true;
126 if (!L)
127 return false;
128 return contains(L->getParentLoop());
129 }
130
131 /// Return true if the specified basic block is in this loop.
132 bool contains(const BlockT *BB) const {
133 assert(!isInvalid() && "Loop not in a valid state!");
134 return DenseBlockSet.count(BB);
135 }
136
137 /// Return true if the specified instruction is in this loop.
138 template <class InstT> bool contains(const InstT *Inst) const {
139 return contains(Inst->getParent());
140 }
141
142 /// Return the loops contained entirely within this loop.
143 const std::vector<LoopT *> &getSubLoops() const {
144 assert(!isInvalid() && "Loop not in a valid state!");
145 return SubLoops;
146 }
147 std::vector<LoopT *> &getSubLoopsVector() {
148 assert(!isInvalid() && "Loop not in a valid state!");
149 return SubLoops;
150 }
151 typedef typename std::vector<LoopT *>::const_iterator iterator;
152 typedef
153 typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
154 iterator begin() const { return getSubLoops().begin(); }
155 iterator end() const { return getSubLoops().end(); }
156 reverse_iterator rbegin() const { return getSubLoops().rbegin(); }
157 reverse_iterator rend() const { return getSubLoops().rend(); }
158
159 // LoopInfo does not detect irreducible control flow, just natural
160 // loops. That is, it is possible that there is cyclic control
161 // flow within the "innermost loop" or around the "outermost
162 // loop".
163
164 /// Return true if the loop does not contain any (natural) loops.
165 bool isInnermost() const { return getSubLoops().empty(); }
166 /// Return true if the loop does not have a parent (natural) loop
167 // (i.e. it is outermost, which is the same as top-level).
168 bool isOutermost() const { return getParentLoop() == nullptr; }
169
170 /// Get a list of the basic blocks which make up this loop.
171 ArrayRef<BlockT *> getBlocks() const {
172 assert(!isInvalid() && "Loop not in a valid state!");
173 return Blocks;
174 }
175 typedef typename ArrayRef<BlockT *>::const_iterator block_iterator;
176 block_iterator block_begin() const { return getBlocks().begin(); }
177 block_iterator block_end() const { return getBlocks().end(); }
178 inline iterator_range<block_iterator> blocks() const {
179 assert(!isInvalid() && "Loop not in a valid state!");
180 return make_range(block_begin(), block_end());
181 }
182
183 /// Get the number of blocks in this loop in constant time.
184 /// Invalidate the loop, indicating that it is no longer a loop.
185 unsigned getNumBlocks() const {
186 assert(!isInvalid() && "Loop not in a valid state!");
187 return Blocks.size();
188 }
189
190 /// Return a direct, mutable handle to the blocks vector so that we can
191 /// mutate it efficiently with techniques like `std::remove`.
192 std::vector<BlockT *> &getBlocksVector() {
193 assert(!isInvalid() && "Loop not in a valid state!");
194 return Blocks;
195 }
196 /// Return a direct, mutable handle to the blocks set so that we can
197 /// mutate it efficiently.
198 SmallPtrSetImpl<const BlockT *> &getBlocksSet() {
199 assert(!isInvalid() && "Loop not in a valid state!");
200 return DenseBlockSet;
201 }
202
203 /// Return a direct, immutable handle to the blocks set.
204 const SmallPtrSetImpl<const BlockT *> &getBlocksSet() const {
205 assert(!isInvalid() && "Loop not in a valid state!");
206 return DenseBlockSet;
207 }
208
209 /// Return true if this loop is no longer valid. The only valid use of this
210 /// helper is "assert(L.isInvalid())" or equivalent, since IsInvalid is set to
211 /// true by the destructor. In other words, if this accessor returns true,
212 /// the caller has already triggered UB by calling this accessor; and so it
213 /// can only be called in a context where a return value of true indicates a
214 /// programmer error.
215 bool isInvalid() const {
216#if LLVM_ENABLE_ABI_BREAKING_CHECKS
217 return IsInvalid;
218#else
219 return false;
220#endif
221 }
222
223 /// True if terminator in the block can branch to another block that is
224 /// outside of the current loop. \p BB must be inside the loop.
225 bool isLoopExiting(const BlockT *BB) const {
226 assert(!isInvalid() && "Loop not in a valid state!");
227 assert(contains(BB) && "Exiting block must be part of the loop");
228 for (const auto *Succ : children<const BlockT *>(BB)) {
229 if (!contains(Succ))
230 return true;
231 }
232 return false;
233 }
234
235 /// Returns true if \p BB is a loop-latch.
236 /// A latch block is a block that contains a branch back to the header.
237 /// This function is useful when there are multiple latches in a loop
238 /// because \fn getLoopLatch will return nullptr in that case.
239 bool isLoopLatch(const BlockT *BB) const {
240 assert(!isInvalid() && "Loop not in a valid state!");
241 assert(contains(BB) && "block does not belong to the loop");
242
243 BlockT *Header = getHeader();
244 auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header);
245 auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header);
246 return std::find(PredBegin, PredEnd, BB) != PredEnd;
247 }
248
249 /// Calculate the number of back edges to the loop header.
250 unsigned getNumBackEdges() const {
251 assert(!isInvalid() && "Loop not in a valid state!");
252 unsigned NumBackEdges = 0;
253 BlockT *H = getHeader();
254
255 for (const auto Pred : children<Inverse<BlockT *>>(H))
256 if (contains(Pred))
257 ++NumBackEdges;
258
259 return NumBackEdges;
260 }
261
262 //===--------------------------------------------------------------------===//
263 // APIs for simple analysis of the loop.
264 //
265 // Note that all of these methods can fail on general loops (ie, there may not
266 // be a preheader, etc). For best success, the loop simplification and
267 // induction variable canonicalization pass should be used to normalize loops
268 // for easy analysis. These methods assume canonical loops.
269
270 /// Return all blocks inside the loop that have successors outside of the
271 /// loop. These are the blocks _inside of the current loop_ which branch out.
272 /// The returned list is always unique.
273 void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const;
274
275 /// If getExitingBlocks would return exactly one block, return that block.
276 /// Otherwise return null.
277 BlockT *getExitingBlock() const;
278
279 /// Return all of the successor blocks of this loop. These are the blocks
280 /// _outside of the current loop_ which are branched to.
281 void getExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
282
283 /// If getExitBlocks would return exactly one block, return that block.
284 /// Otherwise return null.
285 BlockT *getExitBlock() const;
286
287 /// Return true if no exit block for the loop has a predecessor that is
288 /// outside the loop.
289 bool hasDedicatedExits() const;
290
291 /// Return all unique successor blocks of this loop.
292 /// These are the blocks _outside of the current loop_ which are branched to.
293 void getUniqueExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
294
295 /// Return all unique successor blocks of this loop except successors from
296 /// Latch block are not considered. If the exit comes from Latch has also
297 /// non Latch predecessor in a loop it will be added to ExitBlocks.
298 /// These are the blocks _outside of the current loop_ which are branched to.
299 void getUniqueNonLatchExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
300
301 /// If getUniqueExitBlocks would return exactly one block, return that block.
302 /// Otherwise return null.
303 BlockT *getUniqueExitBlock() const;
304
305 /// Return true if this loop does not have any exit blocks.
306 bool hasNoExitBlocks() const;
307
308 /// Edge type.
309 typedef std::pair<BlockT *, BlockT *> Edge;
310
311 /// Return all pairs of (_inside_block_,_outside_block_).
312 void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const;
313
314 /// If there is a preheader for this loop, return it. A loop has a preheader
315 /// if there is only one edge to the header of the loop from outside of the
316 /// loop. If this is the case, the block branching to the header of the loop
317 /// is the preheader node.
318 ///
319 /// This method returns null if there is no preheader for the loop.
320 BlockT *getLoopPreheader() const;
321
322 /// If the given loop's header has exactly one unique predecessor outside the
323 /// loop, return it. Otherwise return null.
324 /// This is less strict that the loop "preheader" concept, which requires
325 /// the predecessor to have exactly one successor.
326 BlockT *getLoopPredecessor() const;
327
328 /// If there is a single latch block for this loop, return it.
329 /// A latch block is a block that contains a branch back to the header.
330 BlockT *getLoopLatch() const;
331
332 /// Return all loop latch blocks of this loop. A latch block is a block that
333 /// contains a branch back to the header.
334 void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
335 assert(!isInvalid() && "Loop not in a valid state!");
336 BlockT *H = getHeader();
337 for (const auto Pred : children<Inverse<BlockT *>>(H))
338 if (contains(Pred))
339 LoopLatches.push_back(Pred);
340 }
341
342 /// Return all inner loops in the loop nest rooted by the loop in preorder,
343 /// with siblings in forward program order.
344 template <class Type>
345 static void getInnerLoopsInPreorder(const LoopT &L,
346 SmallVectorImpl<Type> &PreOrderLoops) {
347 SmallVector<LoopT *, 4> PreOrderWorklist;
348 PreOrderWorklist.append(L.rbegin(), L.rend());
349
350 while (!PreOrderWorklist.empty()) {
351 LoopT *L = PreOrderWorklist.pop_back_val();
352 // Sub-loops are stored in forward program order, but will process the
353 // worklist backwards so append them in reverse order.
354 PreOrderWorklist.append(L->rbegin(), L->rend());
355 PreOrderLoops.push_back(L);
356 }
357 }
358
359 /// Return all loops in the loop nest rooted by the loop in preorder, with
360 /// siblings in forward program order.
361 SmallVector<const LoopT *, 4> getLoopsInPreorder() const {
362 SmallVector<const LoopT *, 4> PreOrderLoops;
363 const LoopT *CurLoop = static_cast<const LoopT *>(this);
364 PreOrderLoops.push_back(CurLoop);
365 getInnerLoopsInPreorder(*CurLoop, PreOrderLoops);
366 return PreOrderLoops;
367 }
368 SmallVector<LoopT *, 4> getLoopsInPreorder() {
369 SmallVector<LoopT *, 4> PreOrderLoops;
370 LoopT *CurLoop = static_cast<LoopT *>(this);
371 PreOrderLoops.push_back(CurLoop);
372 getInnerLoopsInPreorder(*CurLoop, PreOrderLoops);
373 return PreOrderLoops;
374 }
375
376 //===--------------------------------------------------------------------===//
377 // APIs for updating loop information after changing the CFG
378 //
379
380 /// This method is used by other analyses to update loop information.
381 /// NewBB is set to be a new member of the current loop.
382 /// Because of this, it is added as a member of all parent loops, and is added
383 /// to the specified LoopInfo object as being in the current basic block. It
384 /// is not valid to replace the loop header with this method.
385 void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI);
386
387 /// This is used when splitting loops up. It replaces the OldChild entry in
388 /// our children list with NewChild, and updates the parent pointer of
389 /// OldChild to be null and the NewChild to be this loop.
390 /// This updates the loop depth of the new child.
391 void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild);
392
393 /// Add the specified loop to be a child of this loop.
394 /// This updates the loop depth of the new child.
395 void addChildLoop(LoopT *NewChild) {
396 assert(!isInvalid() && "Loop not in a valid state!");
397 assert(!NewChild->ParentLoop && "NewChild already has a parent!");
398 NewChild->ParentLoop = static_cast<LoopT *>(this);
399 SubLoops.push_back(NewChild);
400 }
401
402 /// This removes the specified child from being a subloop of this loop. The
403 /// loop is not deleted, as it will presumably be inserted into another loop.
404 LoopT *removeChildLoop(iterator I) {
405 assert(!isInvalid() && "Loop not in a valid state!");
406 assert(I != SubLoops.end() && "Cannot remove end iterator!");
407 LoopT *Child = *I;
408 assert(Child->ParentLoop == this && "Child is not a child of this loop!");
409 SubLoops.erase(SubLoops.begin() + (I - begin()));
410 Child->ParentLoop = nullptr;
411 return Child;
412 }
413
414 /// This removes the specified child from being a subloop of this loop. The
415 /// loop is not deleted, as it will presumably be inserted into another loop.
416 LoopT *removeChildLoop(LoopT *Child) {
417 return removeChildLoop(llvm::find(*this, Child));
418 }
419
420 /// This adds a basic block directly to the basic block list.
421 /// This should only be used by transformations that create new loops. Other
422 /// transformations should use addBasicBlockToLoop.
423 void addBlockEntry(BlockT *BB) {
424 assert(!isInvalid() && "Loop not in a valid state!");
425 Blocks.push_back(BB);
426 DenseBlockSet.insert(BB);
427 }
428
429 /// interface to reverse Blocks[from, end of loop] in this loop
430 void reverseBlock(unsigned from) {
431 assert(!isInvalid() && "Loop not in a valid state!");
432 std::reverse(Blocks.begin() + from, Blocks.end());
433 }
434
435 /// interface to do reserve() for Blocks
436 void reserveBlocks(unsigned size) {
437 assert(!isInvalid() && "Loop not in a valid state!");
438 Blocks.reserve(size);
439 }
440
441 /// This method is used to move BB (which must be part of this loop) to be the
442 /// loop header of the loop (the block that dominates all others).
443 void moveToHeader(BlockT *BB) {
444 assert(!isInvalid() && "Loop not in a valid state!");
445 if (Blocks[0] == BB)
446 return;
447 for (unsigned i = 0;; ++i) {
448 assert(i != Blocks.size() && "Loop does not contain BB!");
449 if (Blocks[i] == BB) {
450 Blocks[i] = Blocks[0];
451 Blocks[0] = BB;
452 return;
453 }
454 }
455 }
456
457 /// This removes the specified basic block from the current loop, updating the
458 /// Blocks as appropriate. This does not update the mapping in the LoopInfo
459 /// class.
460 void removeBlockFromLoop(BlockT *BB) {
461 assert(!isInvalid() && "Loop not in a valid state!");
462 auto I = find(Blocks, BB);
463 assert(I != Blocks.end() && "N is not in this list!");
464 Blocks.erase(I);
465
466 DenseBlockSet.erase(BB);
467 }
468
469 /// Verify loop structure
470 void verifyLoop() const;
471
472 /// Verify loop structure of this loop and all nested loops.
473 void verifyLoopNest(DenseSet<const LoopT *> *Loops) const;
474
475 /// Returns true if the loop is annotated parallel.
476 ///
477 /// Derived classes can override this method using static template
478 /// polymorphism.
479 bool isAnnotatedParallel() const { return false; }
480
481 /// Print loop with all the BBs inside it.
482 void print(raw_ostream &OS, bool Verbose = false, bool PrintNested = true,
483 unsigned Depth = 0) const;
484
485protected:
486 friend class LoopInfoBase<BlockT, LoopT>;
487
488 /// This creates an empty loop.
489 LoopBase() : ParentLoop(nullptr) {}
490
491 explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
492 Blocks.push_back(BB);
493 DenseBlockSet.insert(BB);
494 }
495
496 // Since loop passes like SCEV are allowed to key analysis results off of
497 // `Loop` pointers, we cannot re-use pointers within a loop pass manager.
498 // This means loop passes should not be `delete` ing `Loop` objects directly
499 // (and risk a later `Loop` allocation re-using the address of a previous one)
500 // but should be using LoopInfo::markAsRemoved, which keeps around the `Loop`
501 // pointer till the end of the lifetime of the `LoopInfo` object.
502 //
503 // To make it easier to follow this rule, we mark the destructor as
504 // non-public.
505 ~LoopBase() {
506 for (auto *SubLoop : SubLoops)
507 SubLoop->~LoopT();
508
509#if LLVM_ENABLE_ABI_BREAKING_CHECKS
510 IsInvalid = true;
511#endif
512 SubLoops.clear();
513 Blocks.clear();
514 DenseBlockSet.clear();
515 ParentLoop = nullptr;
516 }
517};
518
519template <class BlockT, class LoopT>
520raw_ostream &operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
521 Loop.print(OS);
522 return OS;
523}
524
525// Implementation in LoopInfoImpl.h
526extern template class LoopBase<BasicBlock, Loop>;
527
528/// Represents a single loop in the control flow graph. Note that not all SCCs
529/// in the CFG are necessarily loops.
530class Loop : public LoopBase<BasicBlock, Loop> {
531public:
532 /// A range representing the start and end location of a loop.
533 class LocRange {
534 DebugLoc Start;
535 DebugLoc End;
536
537 public:
538 LocRange() {}
539 LocRange(DebugLoc Start) : Start(Start), End(Start) {}
540 LocRange(DebugLoc Start, DebugLoc End)
541 : Start(std::move(Start)), End(std::move(End)) {}
542
543 const DebugLoc &getStart() const { return Start; }
544 const DebugLoc &getEnd() const { return End; }
545
546 /// Check for null.
547 ///
548 explicit operator bool() const { return Start && End; }
549 };
550
551 /// Return true if the specified value is loop invariant.
552 bool isLoopInvariant(const Value *V) const;
553
554 /// Return true if all the operands of the specified instruction are loop
555 /// invariant.
556 bool hasLoopInvariantOperands(const Instruction *I) const;
557
558 /// If the given value is an instruction inside of the loop and it can be
559 /// hoisted, do so to make it trivially loop-invariant.
560 /// Return true if the value after any hoisting is loop invariant. This
561 /// function can be used as a slightly more aggressive replacement for
562 /// isLoopInvariant.
563 ///
564 /// If InsertPt is specified, it is the point to hoist instructions to.
565 /// If null, the terminator of the loop preheader is used.
566 bool makeLoopInvariant(Value *V, bool &Changed,
567 Instruction *InsertPt = nullptr,
568 MemorySSAUpdater *MSSAU = nullptr) const;
569
570 /// If the given instruction is inside of the loop and it can be hoisted, do
571 /// so to make it trivially loop-invariant.
572 /// Return true if the instruction after any hoisting is loop invariant. This
573 /// function can be used as a slightly more aggressive replacement for
574 /// isLoopInvariant.
575 ///
576 /// If InsertPt is specified, it is the point to hoist instructions to.
577 /// If null, the terminator of the loop preheader is used.
578 ///
579 bool makeLoopInvariant(Instruction *I, bool &Changed,
580 Instruction *InsertPt = nullptr,
581 MemorySSAUpdater *MSSAU = nullptr) const;
582
583 /// Check to see if the loop has a canonical induction variable: an integer
584 /// recurrence that starts at 0 and increments by one each time through the
585 /// loop. If so, return the phi node that corresponds to it.
586 ///
587 /// The IndVarSimplify pass transforms loops to have a canonical induction
588 /// variable.
589 ///
590 PHINode *getCanonicalInductionVariable() const;
591
592 /// Obtain the unique incoming and back edge. Return false if they are
593 /// non-unique or the loop is dead; otherwise, return true.
594 bool getIncomingAndBackEdge(BasicBlock *&Incoming,
595 BasicBlock *&Backedge) const;
596
597 /// Below are some utilities to get the loop guard, loop bounds and induction
598 /// variable, and to check if a given phinode is an auxiliary induction
599 /// variable, if the loop is guarded, and if the loop is canonical.
600 ///
601 /// Here is an example:
602 /// \code
603 /// for (int i = lb; i < ub; i+=step)
604 /// <loop body>
605 /// --- pseudo LLVMIR ---
606 /// beforeloop:
607 /// guardcmp = (lb < ub)
608 /// if (guardcmp) goto preheader; else goto afterloop
609 /// preheader:
610 /// loop:
611 /// i_1 = phi[{lb, preheader}, {i_2, latch}]
612 /// <loop body>
613 /// i_2 = i_1 + step
614 /// latch:
615 /// cmp = (i_2 < ub)
616 /// if (cmp) goto loop
617 /// exit:
618 /// afterloop:
619 /// \endcode
620 ///
621 /// - getBounds
622 /// - getInitialIVValue --> lb
623 /// - getStepInst --> i_2 = i_1 + step
624 /// - getStepValue --> step
625 /// - getFinalIVValue --> ub
626 /// - getCanonicalPredicate --> '<'
627 /// - getDirection --> Increasing
628 ///
629 /// - getInductionVariable --> i_1
630 /// - isAuxiliaryInductionVariable(x) --> true if x == i_1
631 /// - getLoopGuardBranch()
632 /// --> `if (guardcmp) goto preheader; else goto afterloop`
633 /// - isGuarded() --> true
634 /// - isCanonical --> false
635 struct LoopBounds {
636 /// Return the LoopBounds object if
637 /// - the given \p IndVar is an induction variable
638 /// - the initial value of the induction variable can be found
639 /// - the step instruction of the induction variable can be found
640 /// - the final value of the induction variable can be found
641 ///
642 /// Else None.
643 static Optional<Loop::LoopBounds> getBounds(const Loop &L, PHINode &IndVar,
644 ScalarEvolution &SE);
645
646 /// Get the initial value of the loop induction variable.
647 Value &getInitialIVValue() const { return InitialIVValue; }
648
649 /// Get the instruction that updates the loop induction variable.
650 Instruction &getStepInst() const { return StepInst; }
651
652 /// Get the step that the loop induction variable gets updated by in each
653 /// loop iteration. Return nullptr if not found.
654 Value *getStepValue() const { return StepValue; }
655
656 /// Get the final value of the loop induction variable.
657 Value &getFinalIVValue() const { return FinalIVValue; }
658
659 /// Return the canonical predicate for the latch compare instruction, if
660 /// able to be calcuated. Else BAD_ICMP_PREDICATE.
661 ///
662 /// A predicate is considered as canonical if requirements below are all
663 /// satisfied:
664 /// 1. The first successor of the latch branch is the loop header
665 /// If not, inverse the predicate.
666 /// 2. One of the operands of the latch comparison is StepInst
667 /// If not, and
668 /// - if the current calcuated predicate is not ne or eq, flip the
669 /// predicate.
670 /// - else if the loop is increasing, return slt
671 /// (notice that it is safe to change from ne or eq to sign compare)
672 /// - else if the loop is decreasing, return sgt
673 /// (notice that it is safe to change from ne or eq to sign compare)
674 ///
675 /// Here is an example when both (1) and (2) are not satisfied:
676 /// \code
677 /// loop.header:
678 /// %iv = phi [%initialiv, %loop.preheader], [%inc, %loop.header]
679 /// %inc = add %iv, %step
680 /// %cmp = slt %iv, %finaliv
681 /// br %cmp, %loop.exit, %loop.header
682 /// loop.exit:
683 /// \endcode
684 /// - The second successor of the latch branch is the loop header instead
685 /// of the first successor (slt -> sge)
686 /// - The first operand of the latch comparison (%cmp) is the IndVar (%iv)
687 /// instead of the StepInst (%inc) (sge -> sgt)
688 ///
689 /// The predicate would be sgt if both (1) and (2) are satisfied.
690 /// getCanonicalPredicate() returns sgt for this example.
691 /// Note: The IR is not changed.
692 ICmpInst::Predicate getCanonicalPredicate() const;
693
694 /// An enum for the direction of the loop
695 /// - for (int i = 0; i < ub; ++i) --> Increasing
696 /// - for (int i = ub; i > 0; --i) --> Descresing
697 /// - for (int i = x; i != y; i+=z) --> Unknown
698 enum class Direction { Increasing, Decreasing, Unknown };
699
700 /// Get the direction of the loop.
701 Direction getDirection() const;
702
703 private:
704 LoopBounds(const Loop &Loop, Value &I, Instruction &SI, Value *SV, Value &F,
705 ScalarEvolution &SE)
706 : L(Loop), InitialIVValue(I), StepInst(SI), StepValue(SV),
707 FinalIVValue(F), SE(SE) {}
708
709 const Loop &L;
710
711 // The initial value of the loop induction variable
712 Value &InitialIVValue;
713
714 // The instruction that updates the loop induction variable
715 Instruction &StepInst;
716
717 // The value that the loop induction variable gets updated by in each loop
718 // iteration
719 Value *StepValue;
720
721 // The final value of the loop induction variable
722 Value &FinalIVValue;
723
724 ScalarEvolution &SE;
725 };
726
727 /// Return the struct LoopBounds collected if all struct members are found,
728 /// else None.
729 Optional<LoopBounds> getBounds(ScalarEvolution &SE) const;
730
731 /// Return the loop induction variable if found, else return nullptr.
732 /// An instruction is considered as the loop induction variable if
733 /// - it is an induction variable of the loop; and
734 /// - it is used to determine the condition of the branch in the loop latch
735 ///
736 /// Note: the induction variable doesn't need to be canonical, i.e. starts at
737 /// zero and increments by one each time through the loop (but it can be).
738 PHINode *getInductionVariable(ScalarEvolution &SE) const;
739
740 /// Get the loop induction descriptor for the loop induction variable. Return
741 /// true if the loop induction variable is found.
742 bool getInductionDescriptor(ScalarEvolution &SE,
743 InductionDescriptor &IndDesc) const;
744
745 /// Return true if the given PHINode \p AuxIndVar is
746 /// - in the loop header
747 /// - not used outside of the loop
748 /// - incremented by a loop invariant step for each loop iteration
749 /// - step instruction opcode should be add or sub
750 /// Note: auxiliary induction variable is not required to be used in the
751 /// conditional branch in the loop latch. (but it can be)
752 bool isAuxiliaryInductionVariable(PHINode &AuxIndVar,
753 ScalarEvolution &SE) const;
754
755 /// Return the loop guard branch, if it exists.
756 ///
757 /// This currently only works on simplified loop, as it requires a preheader
758 /// and a latch to identify the guard. It will work on loops of the form:
759 /// \code
760 /// GuardBB:
761 /// br cond1, Preheader, ExitSucc <== GuardBranch
762 /// Preheader:
763 /// br Header
764 /// Header:
765 /// ...
766 /// br Latch
767 /// Latch:
768 /// br cond2, Header, ExitBlock
769 /// ExitBlock:
770 /// br ExitSucc
771 /// ExitSucc:
772 /// \endcode
773 BranchInst *getLoopGuardBranch() const;
774
775 /// Return true iff the loop is
776 /// - in simplify rotated form, and
777 /// - guarded by a loop guard branch.
778 bool isGuarded() const { return (getLoopGuardBranch() != nullptr); }
779
780 /// Return true if the loop is in rotated form.
781 ///
782 /// This does not check if the loop was rotated by loop rotation, instead it
783 /// only checks if the loop is in rotated form (has a valid latch that exists
784 /// the loop).
785 bool isRotatedForm() const {
786 assert(!isInvalid() && "Loop not in a valid state!");
787 BasicBlock *Latch = getLoopLatch();
788 return Latch && isLoopExiting(Latch);
789 }
790
791 /// Return true if the loop induction variable starts at zero and increments
792 /// by one each time through the loop.
793 bool isCanonical(ScalarEvolution &SE) const;
794
795 /// Return true if the Loop is in LCSSA form.
796 bool isLCSSAForm(const DominatorTree &DT) const;
797
798 /// Return true if this Loop and all inner subloops are in LCSSA form.
799 bool isRecursivelyLCSSAForm(const DominatorTree &DT,
800 const LoopInfo &LI) const;
801
802 /// Return true if the Loop is in the form that the LoopSimplify form
803 /// transforms loops to, which is sometimes called normal form.
804 bool isLoopSimplifyForm() const;
805
806 /// Return true if the loop body is safe to clone in practice.
807 bool isSafeToClone() const;
808
809 /// Returns true if the loop is annotated parallel.
810 ///
811 /// A parallel loop can be assumed to not contain any dependencies between
812 /// iterations by the compiler. That is, any loop-carried dependency checking
813 /// can be skipped completely when parallelizing the loop on the target
814 /// machine. Thus, if the parallel loop information originates from the
815 /// programmer, e.g. via the OpenMP parallel for pragma, it is the
816 /// programmer's responsibility to ensure there are no loop-carried
817 /// dependencies. The final execution order of the instructions across
818 /// iterations is not guaranteed, thus, the end result might or might not
819 /// implement actual concurrent execution of instructions across multiple
820 /// iterations.
821 bool isAnnotatedParallel() const;
822
823 /// Return the llvm.loop loop id metadata node for this loop if it is present.
824 ///
825 /// If this loop contains the same llvm.loop metadata on each branch to the
826 /// header then the node is returned. If any latch instruction does not
827 /// contain llvm.loop or if multiple latches contain different nodes then
828 /// 0 is returned.
829 MDNode *getLoopID() const;
830 /// Set the llvm.loop loop id metadata for this loop.
831 ///
832 /// The LoopID metadata node will be added to each terminator instruction in
833 /// the loop that branches to the loop header.
834 ///
835 /// The LoopID metadata node should have one or more operands and the first
836 /// operand should be the node itself.
837 void setLoopID(MDNode *LoopID) const;
838
839 /// Add llvm.loop.unroll.disable to this loop's loop id metadata.
840 ///
841 /// Remove existing unroll metadata and add unroll disable metadata to
842 /// indicate the loop has already been unrolled. This prevents a loop
843 /// from being unrolled more than is directed by a pragma if the loop
844 /// unrolling pass is run more than once (which it generally is).
845 void setLoopAlreadyUnrolled();
846
847 /// Add llvm.loop.mustprogress to this loop's loop id metadata.
848 void setLoopMustProgress();
849
850 void dump() const;
851 void dumpVerbose() const;
852
853 /// Return the debug location of the start of this loop.
854 /// This looks for a BB terminating instruction with a known debug
855 /// location by looking at the preheader and header blocks. If it
856 /// cannot find a terminating instruction with location information,
857 /// it returns an unknown location.
858 DebugLoc getStartLoc() const;
859
860 /// Return the source code span of the loop.
861 LocRange getLocRange() const;
862
863 StringRef getName() const {
864 if (BasicBlock *Header = getHeader())
865 if (Header->hasName())
866 return Header->getName();
867 return "<unnamed loop>";
868 }
869
870private:
871 Loop() = default;
872
873 friend class LoopInfoBase<BasicBlock, Loop>;
874 friend class LoopBase<BasicBlock, Loop>;
875 explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {}
876 ~Loop() = default;
877};
878
879//===----------------------------------------------------------------------===//
880/// This class builds and contains all of the top-level loop
881/// structures in the specified function.
882///
883
884template <class BlockT, class LoopT> class LoopInfoBase {
885 // BBMap - Mapping of basic blocks to the inner most loop they occur in
886 DenseMap<const BlockT *, LoopT *> BBMap;
887 std::vector<LoopT *> TopLevelLoops;
888 BumpPtrAllocator LoopAllocator;
889
890 friend class LoopBase<BlockT, LoopT>;
891 friend class LoopInfo;
892
893 void operator=(const LoopInfoBase &) = delete;
894 LoopInfoBase(const LoopInfoBase &) = delete;
895
896public:
897 LoopInfoBase() {}
898 ~LoopInfoBase() { releaseMemory(); }
899
900 LoopInfoBase(LoopInfoBase &&Arg)
901 : BBMap(std::move(Arg.BBMap)),
902 TopLevelLoops(std::move(Arg.TopLevelLoops)),
903 LoopAllocator(std::move(Arg.LoopAllocator)) {
904 // We have to clear the arguments top level loops as we've taken ownership.
905 Arg.TopLevelLoops.clear();
906 }
907 LoopInfoBase &operator=(LoopInfoBase &&RHS) {
908 BBMap = std::move(RHS.BBMap);
909
910 for (auto *L : TopLevelLoops)
911 L->~LoopT();
912
913 TopLevelLoops = std::move(RHS.TopLevelLoops);
914 LoopAllocator = std::move(RHS.LoopAllocator);
915 RHS.TopLevelLoops.clear();
916 return *this;
917 }
918
919 void releaseMemory() {
920 BBMap.clear();
921
922 for (auto *L : TopLevelLoops)
923 L->~LoopT();
924 TopLevelLoops.clear();
925 LoopAllocator.Reset();
926 }
927
928 template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
929 LoopT *Storage = LoopAllocator.Allocate<LoopT>();
930 return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
931 }
932
933 /// iterator/begin/end - The interface to the top-level loops in the current
934 /// function.
935 ///
936 typedef typename std::vector<LoopT *>::const_iterator iterator;
937 typedef
938 typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
939 iterator begin() const { return TopLevelLoops.begin(); }
940 iterator end() const { return TopLevelLoops.end(); }
941 reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
942 reverse_iterator rend() const { return TopLevelLoops.rend(); }
943 bool empty() const { return TopLevelLoops.empty(); }
944
945 /// Return all of the loops in the function in preorder across the loop
946 /// nests, with siblings in forward program order.
947 ///
948 /// Note that because loops form a forest of trees, preorder is equivalent to
949 /// reverse postorder.
950 SmallVector<LoopT *, 4> getLoopsInPreorder();
951
952 /// Return all of the loops in the function in preorder across the loop
953 /// nests, with siblings in *reverse* program order.
954 ///
955 /// Note that because loops form a forest of trees, preorder is equivalent to
956 /// reverse postorder.
957 ///
958 /// Also note that this is *not* a reverse preorder. Only the siblings are in
959 /// reverse program order.
960 SmallVector<LoopT *, 4> getLoopsInReverseSiblingPreorder();
961
962 /// Return the inner most loop that BB lives in. If a basic block is in no
963 /// loop (for example the entry node), null is returned.
964 LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
965
966 /// Same as getLoopFor.
967 const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); }
968
969 /// Return the loop nesting level of the specified block. A depth of 0 means
970 /// the block is not inside any loop.
971 unsigned getLoopDepth(const BlockT *BB) const {
972 const LoopT *L = getLoopFor(BB);
973 return L ? L->getLoopDepth() : 0;
974 }
975
976 // True if the block is a loop header node
977 bool isLoopHeader(const BlockT *BB) const {
978 const LoopT *L = getLoopFor(BB);
979 return L && L->getHeader() == BB;
980 }
981
982 /// Return the top-level loops.
983 const std::vector<LoopT *> &getTopLevelLoops() const { return TopLevelLoops; }
984
985 /// Return the top-level loops.
986 std::vector<LoopT *> &getTopLevelLoopsVector() { return TopLevelLoops; }
987
988 /// This removes the specified top-level loop from this loop info object.
989 /// The loop is not deleted, as it will presumably be inserted into
990 /// another loop.
991 LoopT *removeLoop(iterator I) {
992 assert(I != end() && "Cannot remove end iterator!");
993 LoopT *L = *I;
994 assert(L->isOutermost() && "Not a top-level loop!");
995 TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));
996 return L;
997 }
998
999 /// Change the top-level loop that contains BB to the specified loop.
1000 /// This should be used by transformations that restructure the loop hierarchy
1001 /// tree.
1002 void changeLoopFor(BlockT *BB, LoopT *L) {
1003 if (!L) {
1004 BBMap.erase(BB);
1005 return;
1006 }
1007 BBMap[BB] = L;
1008 }
1009
1010 /// Replace the specified loop in the top-level loops list with the indicated
1011 /// loop.
1012 void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) {
1013 auto I = find(TopLevelLoops, OldLoop);
1014 assert(I != TopLevelLoops.end() && "Old loop not at top level!");
1015 *I = NewLoop;
1016 assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
1017 "Loops already embedded into a subloop!");
1018 }
1019
1020 /// This adds the specified loop to the collection of top-level loops.
1021 void addTopLevelLoop(LoopT *New) {
1022 assert(New->isOutermost() && "Loop already in subloop!");
1023 TopLevelLoops.push_back(New);
1024 }
1025
1026 /// This method completely removes BB from all data structures,
1027 /// including all of the Loop objects it is nested in and our mapping from
1028 /// BasicBlocks to loops.
1029 void removeBlock(BlockT *BB) {
1030 auto I = BBMap.find(BB);
1031 if (I != BBMap.end()) {
1032 for (LoopT *L = I->second; L; L = L->getParentLoop())
1033 L->removeBlockFromLoop(BB);
1034
1035 BBMap.erase(I);
1036 }
1037 }
1038
1039 // Internals
1040
1041 static bool isNotAlreadyContainedIn(const LoopT *SubLoop,
1042 const LoopT *ParentLoop) {
1043 if (!SubLoop)
1044 return true;
1045 if (SubLoop == ParentLoop)
1046 return false;
1047 return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
1048 }
1049
1050 /// Create the loop forest using a stable algorithm.
1051 void analyze(const DominatorTreeBase<BlockT, false> &DomTree);
1052
1053 // Debugging
1054 void print(raw_ostream &OS) const;
1055
1056 void verify(const DominatorTreeBase<BlockT, false> &DomTree) const;
1057
1058 /// Destroy a loop that has been removed from the `LoopInfo` nest.
1059 ///
1060 /// This runs the destructor of the loop object making it invalid to
1061 /// reference afterward. The memory is retained so that the *pointer* to the
1062 /// loop remains valid.
1063 ///
1064 /// The caller is responsible for removing this loop from the loop nest and
1065 /// otherwise disconnecting it from the broader `LoopInfo` data structures.
1066 /// Callers that don't naturally handle this themselves should probably call
1067 /// `erase' instead.
1068 void destroy(LoopT *L) {
1069 L->~LoopT();
1070
1071 // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons
1072 // \c L, but the pointer remains valid for non-dereferencing uses.
1073 LoopAllocator.Deallocate(L);
1074 }
1075};
1076
1077// Implementation in LoopInfoImpl.h
1078extern template class LoopInfoBase<BasicBlock, Loop>;
1079
1080class LoopInfo : public LoopInfoBase<BasicBlock, Loop> {
1081 typedef LoopInfoBase<BasicBlock, Loop> BaseT;
1082
1083 friend class LoopBase<BasicBlock, Loop>;
1084
1085 void operator=(const LoopInfo &) = delete;
1086 LoopInfo(const LoopInfo &) = delete;
1087
1088public:
1089 LoopInfo() {}
1090 explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree);
1091
1092 LoopInfo(LoopInfo &&Arg) : BaseT(std::move(static_cast<BaseT &>(Arg))) {}
1093 LoopInfo &operator=(LoopInfo &&RHS) {
1094 BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
1095 return *this;
1096 }
1097
1098 /// Handle invalidation explicitly.
1099 bool invalidate(Function &F, const PreservedAnalyses &PA,
1100 FunctionAnalysisManager::Invalidator &);
1101
1102 // Most of the public interface is provided via LoopInfoBase.
1103
1104 /// Update LoopInfo after removing the last backedge from a loop. This updates
1105 /// the loop forest and parent loops for each block so that \c L is no longer
1106 /// referenced, but does not actually delete \c L immediately. The pointer
1107 /// will remain valid until this LoopInfo's memory is released.
1108 void erase(Loop *L);
1109
1110 /// Returns true if replacing From with To everywhere is guaranteed to
1111 /// preserve LCSSA form.
1112 bool replacementPreservesLCSSAForm(Instruction *From, Value *To) {
1113 // Preserving LCSSA form is only problematic if the replacing value is an
1114 // instruction.
1115 Instruction *I = dyn_cast<Instruction>(To);
1116 if (!I)
1117 return true;
1118 // If both instructions are defined in the same basic block then replacement
1119 // cannot break LCSSA form.
1120 if (I->getParent() == From->getParent())
1121 return true;
1122 // If the instruction is not defined in a loop then it can safely replace
1123 // anything.
1124 Loop *ToLoop = getLoopFor(I->getParent());
1125 if (!ToLoop)
1126 return true;
1127 // If the replacing instruction is defined in the same loop as the original
1128 // instruction, or in a loop that contains it as an inner loop, then using
1129 // it as a replacement will not break LCSSA form.
1130 return ToLoop->contains(getLoopFor(From->getParent()));
1131 }
1132
1133 /// Checks if moving a specific instruction can break LCSSA in any loop.
1134 ///
1135 /// Return true if moving \p Inst to before \p NewLoc will break LCSSA,
1136 /// assuming that the function containing \p Inst and \p NewLoc is currently
1137 /// in LCSSA form.
1138 bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) {
1139 assert(Inst->getFunction() == NewLoc->getFunction() &&
1140 "Can't reason about IPO!");
1141
1142 auto *OldBB = Inst->getParent();
1143 auto *NewBB = NewLoc->getParent();
1144
1145 // Movement within the same loop does not break LCSSA (the equality check is
1146 // to avoid doing a hashtable lookup in case of intra-block movement).
1147 if (OldBB == NewBB)
1148 return true;
1149
1150 auto *OldLoop = getLoopFor(OldBB);
1151 auto *NewLoop = getLoopFor(NewBB);
1152
1153 if (OldLoop == NewLoop)
1154 return true;
1155
1156 // Check if Outer contains Inner; with the null loop counting as the
1157 // "outermost" loop.
1158 auto Contains = [](const Loop *Outer, const Loop *Inner) {
1159 return !Outer || Outer->contains(Inner);
1160 };
1161
1162 // To check that the movement of Inst to before NewLoc does not break LCSSA,
1163 // we need to check two sets of uses for possible LCSSA violations at
1164 // NewLoc: the users of NewInst, and the operands of NewInst.
1165
1166 // If we know we're hoisting Inst out of an inner loop to an outer loop,
1167 // then the uses *of* Inst don't need to be checked.
1168
1169 if (!Contains(NewLoop, OldLoop)) {
1170 for (Use &U : Inst->uses()) {
1171 auto *UI = cast<Instruction>(U.getUser());
1172 auto *UBB = isa<PHINode>(UI) ? cast<PHINode>(UI)->getIncomingBlock(U)
1173 : UI->getParent();
1174 if (UBB != NewBB && getLoopFor(UBB) != NewLoop)
1175 return false;
1176 }
1177 }
1178
1179 // If we know we're sinking Inst from an outer loop into an inner loop, then
1180 // the *operands* of Inst don't need to be checked.
1181
1182 if (!Contains(OldLoop, NewLoop)) {
1183 // See below on why we can't handle phi nodes here.
1184 if (isa<PHINode>(Inst))
1185 return false;
1186
1187 for (Use &U : Inst->operands()) {
1188 auto *DefI = dyn_cast<Instruction>(U.get());
1189 if (!DefI)
1190 return false;
1191
1192 // This would need adjustment if we allow Inst to be a phi node -- the
1193 // new use block won't simply be NewBB.
1194
1195 auto *DefBlock = DefI->getParent();
1196 if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop)
1197 return false;
1198 }
1199 }
1200
1201 return true;
1202 }
1203
1204 // Return true if a new use of V added in ExitBB would require an LCSSA PHI
1205 // to be inserted at the begining of the block. Note that V is assumed to
1206 // dominate ExitBB, and ExitBB must be the exit block of some loop. The
1207 // IR is assumed to be in LCSSA form before the planned insertion.
1208 bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V,
1209 const BasicBlock *ExitBB) const;
1210
1211};
1212
1213// Allow clients to walk the list of nested loops...
1214template <> struct GraphTraits<const Loop *> {
1215 typedef const Loop *NodeRef;
1216 typedef LoopInfo::iterator ChildIteratorType;
1217
1218 static NodeRef getEntryNode(const Loop *L) { return L; }
1219 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
1220 static ChildIteratorType child_end(NodeRef N) { return N->end(); }
1221};
1222
1223template <> struct GraphTraits<Loop *> {
1224 typedef Loop *NodeRef;
1225 typedef LoopInfo::iterator ChildIteratorType;
1226
1227 static NodeRef getEntryNode(Loop *L) { return L; }
1228 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
1229 static ChildIteratorType child_end(NodeRef N) { return N->end(); }
1230};
1231
1232/// Analysis pass that exposes the \c LoopInfo for a function.
1233class LoopAnalysis : public AnalysisInfoMixin<LoopAnalysis> {
1234 friend AnalysisInfoMixin<LoopAnalysis>;
1235 static AnalysisKey Key;
1236
1237public:
1238 typedef LoopInfo Result;
1239
1240 LoopInfo run(Function &F, FunctionAnalysisManager &AM);
1241};
1242
1243/// Printer pass for the \c LoopAnalysis results.
1244class LoopPrinterPass : public PassInfoMixin<LoopPrinterPass> {
1245 raw_ostream &OS;
1246
1247public:
1248 explicit LoopPrinterPass(raw_ostream &OS) : OS(OS) {}
1249 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
1250};
1251
1252/// Verifier pass for the \c LoopAnalysis results.
1253struct LoopVerifierPass : public PassInfoMixin<LoopVerifierPass> {
1254 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
1255};
1256
1257/// The legacy pass manager's analysis pass to compute loop information.
1258class LoopInfoWrapperPass : public FunctionPass {
1259 LoopInfo LI;
1260
1261public:
1262 static char ID; // Pass identification, replacement for typeid
1263
1264 LoopInfoWrapperPass();
1265
1266 LoopInfo &getLoopInfo() { return LI; }
1267 const LoopInfo &getLoopInfo() const { return LI; }
1268
1269 /// Calculate the natural loop information for a given function.
1270 bool runOnFunction(Function &F) override;
1271
1272 void verifyAnalysis() const override;
1273
1274 void releaseMemory() override { LI.releaseMemory(); }
1275
1276 void print(raw_ostream &O, const Module *M = nullptr) const override;
1277
1278 void getAnalysisUsage(AnalysisUsage &AU) const override;
1279};
1280
1281/// Function to print a loop's contents as LLVM's text IR assembly.
1282void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner = "");
1283
1284/// Find and return the loop attribute node for the attribute @p Name in
1285/// @p LoopID. Return nullptr if there is no such attribute.
1286MDNode *findOptionMDForLoopID(MDNode *LoopID, StringRef Name);
1287
1288/// Find string metadata for a loop.
1289///
1290/// Returns the MDNode where the first operand is the metadata's name. The
1291/// following operands are the metadata's values. If no metadata with @p Name is
1292/// found, return nullptr.
1293MDNode *findOptionMDForLoop(const Loop *TheLoop, StringRef Name);
1294
1295/// Return whether an MDNode might represent an access group.
1296///
1297/// Access group metadata nodes have to be distinct and empty. Being
1298/// always-empty ensures that it never needs to be changed (which -- because
1299/// MDNodes are designed immutable -- would require creating a new MDNode). Note
1300/// that this is not a sufficient condition: not every distinct and empty NDNode
1301/// is representing an access group.
1302bool isValidAsAccessGroup(MDNode *AccGroup);
1303
1304/// Create a new LoopID after the loop has been transformed.
1305///
1306/// This can be used when no follow-up loop attributes are defined
1307/// (llvm::makeFollowupLoopID returning None) to stop transformations to be
1308/// applied again.
1309///
1310/// @param Context The LLVMContext in which to create the new LoopID.
1311/// @param OrigLoopID The original LoopID; can be nullptr if the original
1312/// loop has no LoopID.
1313/// @param RemovePrefixes Remove all loop attributes that have these prefixes.
1314/// Use to remove metadata of the transformation that has
1315/// been applied.
1316/// @param AddAttrs Add these loop attributes to the new LoopID.
1317///
1318/// @return A new LoopID that can be applied using Loop::setLoopID().
1319llvm::MDNode *
1320makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID,
1321 llvm::ArrayRef<llvm::StringRef> RemovePrefixes,
1322 llvm::ArrayRef<llvm::MDNode *> AddAttrs);
1323
1324} // End llvm namespace
1325
1326#endif
1327