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