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"
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/Instructions.h"
48 #include "llvm/IR/PassManager.h"
49 #include "llvm/Pass.h"
50 #include "llvm/Support/Allocator.h"
51 #include <algorithm>
52 #include <optional>
53 #include <utility>
54 
55 namespace llvm {
56 
57 class DominatorTree;
58 class InductionDescriptor;
59 class Instruction;
60 class LoopInfo;
61 class Loop;
62 class MDNode;
63 class MemorySSAUpdater;
64 class ScalarEvolution;
65 class raw_ostream;
66 template <class N, bool IsPostDom> class DominatorTreeBase;
67 template <class N, class M> class LoopInfoBase;
68 template <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 ///
74 template <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 
82  SmallPtrSet<const BlockT *, 8> DenseBlockSet;
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 
93 public:
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 
125  LoopT *getOutermostLoop() {
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 
502 protected:
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 
536 template <class BlockT, class LoopT>
538  Loop.print(OS);
539  return OS;
540 }
541 
542 // Implementation in LoopInfoImpl.h
543 extern 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.
548 public:
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 
891  StringRef getName() const {
892  if (BasicBlock *Header = getHeader())
893  if (Header->hasName())
894  return Header->getName();
895  return "<unnamed loop>";
896  }
897 
898 private:
899  Loop() = default;
900 
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 
912 template <class BlockT, class LoopT> class LoopInfoBase {
913  // BBMap - Mapping of basic blocks to the inner most loop they occur in
914  DenseMap<const BlockT *, LoopT *> BBMap;
915  std::vector<LoopT *> TopLevelLoops;
916  BumpPtrAllocator LoopAllocator;
917 
919  friend class LoopInfo;
920 
921  void operator=(const LoopInfoBase &) = delete;
922  LoopInfoBase(const LoopInfoBase &) = delete;
923 
924 public:
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 
947  void releaseMemory() {
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
1106 extern template class LoopInfoBase<BasicBlock, Loop>;
1107 
1110 
1112 
1113  void operator=(const LoopInfo &) = delete;
1114  LoopInfo(const LoopInfo &) = delete;
1115 
1116 public:
1117  LoopInfo() = default;
1118  explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree);
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.
1246 extern bool VerifyLoopInfo;
1247 
1248 // Allow clients to walk the list of nested loops...
1249 template <> 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 
1258 template <> 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 
1272 public:
1273  typedef LoopInfo Result;
1274 
1276 };
1277 
1278 /// Printer pass for the \c LoopAnalysis results.
1280  raw_ostream &OS;
1281 
1282 public:
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 
1296 public:
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.
1317 void 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.
1321 MDNode *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.
1328 MDNode *findOptionMDForLoop(const Loop *TheLoop, StringRef Name);
1329 
1330 std::optional<bool> getOptionalBoolLoopAttribute(const Loop *TheLoop,
1331  StringRef Name);
1332 
1333 /// Returns true if Name is applied to TheLoop and enabled.
1334 bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name);
1335 
1336 /// Find named metadata for a loop with an integer value.
1337 std::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.
1342 int 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.
1349 std::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.
1355 bool 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)
1359 bool isMustProgress(const Loop *L);
1360 
1361 /// Return true if this loop can be assumed to run for a finite number of
1362 /// iterations.
1363 bool 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.
1372 bool 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().
1389 llvm::MDNode *
1391  llvm::ArrayRef<llvm::StringRef> RemovePrefixes,
1393 
1394 } // End llvm namespace
1395 
1396 #endif
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::LoopBase::rend
reverse_iterator rend() const
Definition: LoopInfo.h:174
llvm::orc::BaseT
RTTIExtends< ObjectLinkingLayer, ObjectLayer > BaseT
Definition: ObjectLinkingLayer.cpp:604
llvm::LoopInfo::movementPreservesLCSSAForm
bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc)
Checks if moving a specific instruction can break LCSSA in any loop.
Definition: LoopInfo.h:1166
llvm::LoopBase::contains
bool contains(const BlockT *BB) const
Return true if the specified basic block is in this loop.
Definition: LoopInfo.h:149
llvm::Loop::LocRange::getEnd
const DebugLoc & getEnd() const
Definition: LoopInfo.h:561
llvm::GraphTraits< Loop * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: LoopInfo.h:1263
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LoopBase::getUniqueExitBlock
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:158
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::LoopBase::getExitBlocks
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:64
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:379
llvm::LoopBase::getExitBlock
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:107
llvm::GraphTraits< Loop * >
Definition: LoopInfo.h:1258
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::LoopBase::Edge
std::pair< BlockT *, BlockT * > Edge
Edge type.
Definition: LoopInfo.h:326
llvm::Loop::LoopBounds::getFinalIVValue
Value & getFinalIVValue() const
Get the final value of the loop induction variable.
Definition: LoopInfo.h:682
llvm::LoopBase::getOutermostLoop
const LoopT * getOutermostLoop() const
Get the outermost loop in which this loop is contained.
Definition: LoopInfo.h:118
llvm::PassInfoMixin< LoopPrinterPass >
llvm::Function
Definition: Function.h:59
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::LoopInfo::LoopInfo
LoopInfo(LoopInfo &&Arg)
Definition: LoopInfo.h:1120
Pass.h
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:139
llvm::LoopBase::~LoopBase
~LoopBase()
Definition: LoopInfo.h:522
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:374
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::LoopBase::getLoopPredecessor
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
Definition: LoopInfoImpl.h:211
llvm::LoopBase::reverse_iterator
std::vector< LoopT * >::const_reverse_iterator reverse_iterator
Definition: LoopInfo.h:170
llvm::LoopInfoBase::~LoopInfoBase
~LoopInfoBase()
Definition: LoopInfo.h:926
llvm::LoopBase
Instances of this class are used to represent loops that are detected in the flow graph.
Definition: LoopInfo.h:68
llvm::GraphTraits< Loop * >::getEntryNode
static NodeRef getEntryNode(Loop *L)
Definition: LoopInfo.h:1262
llvm::VerifyLoopInfo
bool VerifyLoopInfo
Enable verification of loop info.
Definition: LoopInfo.cpp:50
Allocator.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:452
llvm::LoopInfoBase::changeLoopFor
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1030
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::getIntLoopAttribute
int getIntLoopAttribute(const Loop *TheLoop, StringRef Name, int Default=0)
Find named metadata for a loop with an integer value.
Definition: LoopInfo.cpp:1103
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::LoopInfoBase::removeBlock
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
DenseMap.h
llvm::LoopInfoWrapperPass::releaseMemory
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
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1293
llvm::LoopBase::getExitEdges
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
Definition: LoopInfoImpl.h:164
llvm::BumpPtrAllocator
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:375
llvm::LoopBase::begin
iterator begin() const
Definition: LoopInfo.h:171
llvm::SmallPtrSet< const BlockT *, 8 >
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
llvm::LoopBase::isLoopLatch
bool isLoopLatch(const BlockT *BB) const
Definition: LoopInfo.h:256
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::LoopBase::contains
bool contains(const InstT *Inst) const
Return true if the specified instruction is in this loop.
Definition: LoopInfo.h:155
llvm::LoopInfoBase::getTopLevelLoopsVector
std::vector< LoopT * > & getTopLevelLoopsVector()
Return the top-level loops.
Definition: LoopInfo.h:1014
llvm::ArrayRef::const_iterator
const_pointer const_iterator
Definition: ArrayRef.h:49
llvm::GraphTraits< const Loop * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: LoopInfo.h:1254
llvm::findOptionMDForLoopID
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Definition: LoopInfo.cpp:1017
llvm::LoopBase::getNumBlocks
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
Definition: LoopInfo.h:202
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::LoopBase::block_end
block_iterator block_end() const
Definition: LoopInfo.h:194
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::makePostTransformationMetadata
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
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
GraphTraits.h
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:114
llvm::LoopBase::getSubLoops
const std::vector< LoopT * > & getSubLoops() const
Return the loops contained entirely within this loop.
Definition: LoopInfo.h:160
llvm::LoopBase::getLoopLatches
void getLoopLatches(SmallVectorImpl< BlockT * > &LoopLatches) const
Return all loop latch blocks of this loop.
Definition: LoopInfo.h:351
llvm::LoopBase::reverseBlock
void reverseBlock(unsigned from)
interface to reverse Blocks[from, end of loop] in this loop
Definition: LoopInfo.h:447
llvm::LoopInfoBase::isNotAlreadyContainedIn
static bool isNotAlreadyContainedIn(const LoopT *SubLoop, const LoopT *ParentLoop)
Definition: LoopInfo.h:1069
llvm::GraphTraits< const Loop * >
Definition: LoopInfo.h:1249
llvm::LoopBase::addChildLoop
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:412
llvm::LoopInfoWrapperPass::getLoopInfo
LoopInfo & getLoopInfo()
Definition: LoopInfo.h:1301
SI
@ SI
Definition: SIInstrInfo.cpp:7993
llvm::LoopAnalysis::Result
LoopInfo Result
Definition: LoopInfo.h:1273
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LoopInfoBase::addTopLevelLoop
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:1049
llvm::LoopBase::end
iterator end() const
Definition: LoopInfo.h:172
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:195
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
llvm::LoopInfoBase::destroy
void destroy(LoopT *L)
Destroy a loop that has been removed from the LoopInfo nest.
Definition: LoopInfo.h:1096
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
llvm::LoopInfo::replacementPreservesLCSSAForm
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
Definition: LoopInfo.h:1140
DenseSet.h
llvm::LoopBase::getBlocks
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:188
llvm::printLoop
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
llvm::Instruction
Definition: Instruction.h:41
llvm::LoopInfoBase::operator=
LoopInfoBase & operator=(LoopInfoBase &&RHS)
Definition: LoopInfo.h:935
llvm::LoopBase::verifyLoop
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:302
llvm::GraphTraits< Loop * >::NodeRef
Loop * NodeRef
Definition: LoopInfo.h:1259
llvm::rdf::detail::NodeRef
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
llvm::LoopBase::getExitingBlocks
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:33
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
llvm::isMustProgress
bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
Definition: LoopInfo.cpp:1118
SmallPtrSet.h
llvm::LoopBase::getLoopsInPreorder
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
llvm::LoopBase::verifyLoopNest
void verifyLoopNest(DenseSet< const LoopT * > *Loops) const
Verify loop structure of this loop and all nested loops.
Definition: LoopInfoImpl.h:382
llvm::SmallVectorImpl::append
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
CombinerObjective::Default
@ Default
llvm::LoopBase::getExitingBlock
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:48
llvm::Loop::LocRange::LocRange
LocRange(DebugLoc Start)
Definition: LoopInfo.h:556
llvm::LoopBase::removeBlockFromLoop
void removeBlockFromLoop(BlockT *BB)
This removes the specified basic block from the current loop, updating the Blocks as appropriate.
Definition: LoopInfo.h:477
llvm::Loop::getName
StringRef getName() const
Definition: LoopInfo.h:891
llvm::LoopBase::removeChildLoop
LoopT * removeChildLoop(LoopT *Child)
This removes the specified child from being a subloop of this loop.
Definition: LoopInfo.h:433
llvm::Loop::LoopBounds::Direction
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:723
llvm::GraphTraits< const Loop * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: LoopInfo.h:1255
CFG.h
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
llvm::LoopInfoBase::AllocateLoop
LoopT * AllocateLoop(ArgsTy &&... Args)
Definition: LoopInfo.h:956
llvm::LoopVerifierPass
Verifier pass for the LoopAnalysis results.
Definition: LoopInfo.h:1288
llvm::LoopBase::block_begin
block_iterator block_begin() const
Definition: LoopInfo.h:193
llvm::LoopInfoWrapperPass::getLoopInfo
const LoopInfo & getLoopInfo() const
Definition: LoopInfo.h:1302
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::LoopBase::block_iterator
ArrayRef< BlockT * >::const_iterator block_iterator
Definition: LoopInfo.h:192
llvm::LoopInfoBase::LoopInfo
friend class LoopInfo
Definition: LoopInfo.h:919
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:274
llvm::Loop::isGuarded
bool isGuarded() const
Return true iff the loop is.
Definition: LoopInfo.h:803
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1197
llvm::LoopBase::moveToHeader
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
llvm::LoopBase::setParentLoop
void setParentLoop(LoopT *L)
This is a raw interface for bypassing addChildLoop.
Definition: LoopInfo.h:133
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::find
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
LLVM_EXTERNAL_VISIBILITY
#define LLVM_EXTERNAL_VISIBILITY
Definition: Compiler.h:127
llvm::LoopBase::getUniqueExitBlocks
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfoImpl.h:142
llvm::findStringMetadataForLoop
std::optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for loop.
Definition: LoopInfo.cpp:1053
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::LoopBase::getLoopsInPreorder
SmallVector< LoopT *, 4 > getLoopsInPreorder()
Definition: LoopInfo.h:385
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
Domain::Unknown
@ Unknown
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
llvm::LoopBase::LoopBase
LoopBase(BlockT *BB)
Definition: LoopInfo.h:508
llvm::Loop::LoopBounds::getStepInst
Instruction & getStepInst() const
Get the instruction that updates the loop induction variable.
Definition: LoopInfo.h:675
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:232
llvm::Loop::LocRange
A range representing the start and end location of a loop.
Definition: LoopInfo.h:550
llvm::LoopBase::getInnerLoopsInPreorder
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
llvm::LoopBase::hasDedicatedExits
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:112
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::isFinite
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
llvm::move
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::LoopBase::getLoopDepth
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:97
llvm::children
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:123
llvm::LoopBase::getBlocksVector
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
llvm::LoopInfoBase::begin
iterator begin() const
Definition: LoopInfo.h:967
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::MDNode
Metadata node.
Definition: Metadata.h:943
llvm::AnalysisInfoMixin< LoopAnalysis >
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::LoopInfoBase::LoopInfoBase
LoopInfoBase(LoopInfoBase &&Arg)
Definition: LoopInfo.h:928
llvm::print
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Definition: GCNRegPressure.cpp:138
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1716
llvm::getOptionalIntLoopAttribute
std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
Definition: LoopInfo.cpp:1089
llvm::LoopInfoBase::getLoopDepth
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
Definition: LoopInfo.h:999
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
llvm::LoopBase::removeChildLoop
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
Definition: LoopInfo.h:421
llvm::LoopBase::getSubLoopsVector
std::vector< LoopT * > & getSubLoopsVector()
Definition: LoopInfo.h:164
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:33
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::LoopBase::isOutermost
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
Definition: LoopInfo.h:185
llvm::LoopBase::reserveBlocks
void reserveBlocks(unsigned size)
interface to do reserve() for Blocks
Definition: LoopInfo.h:453
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:74
llvm::LoopBase::replaceChildLoopWith
void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild)
This is used when splitting loops up.
Definition: LoopInfoImpl.h:288
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:66
llvm::findOptionMDForLoop
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
Definition: LoopInfo.cpp:1043
llvm::LoopBase::LoopBase
LoopBase()
This creates an empty loop.
Definition: LoopInfo.h:506
llvm::LoopBase::getUniqueNonLatchExitBlocks
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
llvm::LoopInfoBase::removeLoop
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
Definition: LoopInfo.h:1019
llvm::GraphTraits< Loop * >::ChildIteratorType
LoopInfo::iterator ChildIteratorType
Definition: LoopInfo.h:1260
llvm::Loop::LocRange::getStart
const DebugLoc & getStart() const
Definition: LoopInfo.h:560
llvm::getOptionalBoolLoopAttribute
std::optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)
Definition: LoopInfo.cpp:1067
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
llvm::LoopBase::isInnermost
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
Definition: LoopInfo.h:182
llvm::GraphTraits< const Loop * >::ChildIteratorType
LoopInfo::iterator ChildIteratorType
Definition: LoopInfo.h:1251
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:1005
llvm::Loop::LoopBounds
Below are some utilities to get the loop guard, loop bounds and induction variable,...
Definition: LoopInfo.h:660
llvm::isValidAsAccessGroup
bool isValidAsAccessGroup(MDNode *AccGroup)
Return whether an MDNode might represent an access group.
Definition: LoopInfo.cpp:1122
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
std
Definition: BitVector.h:851
llvm::LoopBase::getBlocksSet
const SmallPtrSetImpl< const BlockT * > & getBlocksSet() const
Return a direct, immutable handle to the blocks set.
Definition: LoopInfo.h:221
H
#define H(x, y, z)
Definition: MD5.cpp:57
llvm::GraphTraits< Loop * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: LoopInfo.h:1264
llvm::LoopInfoBase::operator[]
const LoopT * operator[](const BlockT *BB) const
Same as getLoopFor.
Definition: LoopInfo.h:995
llvm::Loop::LoopBounds::getInitialIVValue
Value & getInitialIVValue() const
Get the initial value of the loop induction variable.
Definition: LoopInfo.h:672
llvm::LoopInfoBase
This class builds and contains all of the top-level loop structures in the specified function.
Definition: LoopInfo.h:67
llvm::LoopBase::getBlocksSet
SmallPtrSetImpl< const BlockT * > & getBlocksSet()
Return a direct, mutable handle to the blocks set so that we can mutate it efficiently.
Definition: LoopInfo.h:215
llvm::LoopBase::isInvalid
bool isInvalid() const
Return true if this loop is no longer valid.
Definition: LoopInfo.h:232
Direction
Loop::LoopBounds::Direction Direction
Definition: LoopInfo.cpp:230
llvm::LoopInfoBase::rbegin
reverse_iterator rbegin() const
Definition: LoopInfo.h:969
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:105
PassManager.h
llvm::LoopBase::isAnnotatedParallel
bool isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
Definition: LoopInfo.h:496
llvm::LoopBase::getOutermostLoop
LoopT * getOutermostLoop()
Definition: LoopInfo.h:125
llvm::LoopPrinterPass
Printer pass for the LoopAnalysis results.
Definition: LoopInfo.h:1279
llvm::LoopInfoBase::reverse_iterator
std::vector< LoopT * >::const_reverse_iterator reverse_iterator
Definition: LoopInfo.h:966
verify
ppc ctr loops verify
Definition: PPCCTRLoopsVerify.cpp:76
llvm::LoopBase::addBlockEntry
void addBlockEntry(BlockT *BB)
This adds a basic block directly to the basic block list.
Definition: LoopInfo.h:440
llvm::LoopBase::getNumBackEdges
unsigned getNumBackEdges() const
Calculate the number of back edges to the loop header.
Definition: LoopInfo.h:267
llvm::Inverse
Definition: GraphTraits.h:97
llvm::LoopBase::hasNoExitBlocks
bool hasNoExitBlocks() const
Return true if this loop does not have any exit blocks.
Definition: LoopInfoImpl.h:95
llvm::LoopPrinterPass::LoopPrinterPass
LoopPrinterPass(raw_ostream &OS)
Definition: LoopInfo.h:1283
llvm::LoopInfoBase::end
iterator end() const
Definition: LoopInfo.h:968
llvm::LoopInfoBase::rend
reverse_iterator rend() const
Definition: LoopInfo.h:970
Instructions.h
llvm::hasMustProgress
bool hasMustProgress(const Loop *L)
Look for the loop attribute that requires progress within the loop.
Definition: LoopInfo.cpp:1114
SmallVector.h
llvm::LoopBase::addBasicBlockToLoop
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:258
llvm::LoopBase::iterator
std::vector< LoopT * >::const_iterator iterator
Definition: LoopInfo.h:168
llvm::LoopInfoBase::changeTopLevelLoop
void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop)
Replace the specified loop in the top-level loops list with the indicated loop.
Definition: LoopInfo.h:1040
llvm::LoopInfoBase::releaseMemory
void releaseMemory()
Definition: LoopInfo.h:947
N
#define N
llvm::getBooleanLoopAttribute
bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)
Returns true if Name is applied to TheLoop and enabled.
Definition: LoopInfo.cpp:1085
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:90
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::LoopBase::rbegin
reverse_iterator rbegin() const
Definition: LoopInfo.h:173
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::PHINode
Definition: Instructions.h:2708
llvm::LoopInfoBase::iterator
std::vector< LoopT * >::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:964
llvm::LoopInfoBase::empty
bool empty() const
Definition: LoopInfo.h:971
llvm::SmallVectorImpl< BlockT * >
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:484
llvm::SmallPtrSetImpl< const BlockT * >
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
isCanonical
static bool isCanonical(const MDString *S)
Definition: DebugInfoMetadata.cpp:315
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::LoopBase::isLoopExiting
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
llvm::LoopBase::print
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
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::GraphTraits< const Loop * >::getEntryNode
static NodeRef getEntryNode(const Loop *L)
Definition: LoopInfo.h:1253
llvm::GraphTraits
Definition: GraphTraits.h:37
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:394
llvm::Loop::isRotatedForm
bool isRotatedForm() const
Return true if the loop is in rotated form.
Definition: LoopInfo.h:810
llvm::Loop::LocRange::LocRange
LocRange(DebugLoc Start, DebugLoc End)
Definition: LoopInfo.h:557
llvm::GraphTraits< const Loop * >::NodeRef
const typedef Loop * NodeRef
Definition: LoopInfo.h:1250
llvm::Loop::LoopBounds::getStepValue
Value * getStepValue() const
Get the step that the loop induction variable gets updated by in each loop iteration.
Definition: LoopInfo.h:679
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::LoopInfoBase::getTopLevelLoops
const std::vector< LoopT * > & getTopLevelLoops() const
Return the top-level loops.
Definition: LoopInfo.h:1011
llvm::LoopInfo::operator=
LoopInfo & operator=(LoopInfo &&RHS)
Definition: LoopInfo.h:1121
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268
llvm::LoopInfoWrapperPass::ID
static char ID
Definition: LoopInfo.h:1297
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
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