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