LLVM  13.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/Instruction.h"
48 #include "llvm/IR/Instructions.h"
49 #include "llvm/IR/PassManager.h"
50 #include "llvm/Pass.h"
51 #include "llvm/Support/Allocator.h"
52 #include <algorithm>
53 #include <utility>
54 
55 namespace llvm {
56 
57 class DominatorTree;
58 class LoopInfo;
59 class Loop;
60 class InductionDescriptor;
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() {}
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 the value after any hoisting is loop invariant. This
561  /// function can be used as a slightly more aggressive replacement for
562  /// isLoopInvariant.
563  ///
564  /// If InsertPt is specified, it is the point to hoist instructions to.
565  /// If null, the terminator of the loop preheader is used.
566  bool makeLoopInvariant(Value *V, bool &Changed,
567  Instruction *InsertPt = nullptr,
568  MemorySSAUpdater *MSSAU = nullptr) const;
569 
570  /// If the given instruction is inside of the loop and it can be hoisted, do
571  /// so to make it trivially loop-invariant.
572  /// Return true if the instruction after any hoisting is loop invariant. This
573  /// function can be used as a slightly more aggressive replacement for
574  /// isLoopInvariant.
575  ///
576  /// If InsertPt is specified, it is the point to hoist instructions to.
577  /// If null, the terminator of the loop preheader is used.
578  ///
579  bool makeLoopInvariant(Instruction *I, bool &Changed,
580  Instruction *InsertPt = nullptr,
581  MemorySSAUpdater *MSSAU = nullptr) const;
582 
583  /// Check to see if the loop has a canonical induction variable: an integer
584  /// recurrence that starts at 0 and increments by one each time through the
585  /// loop. If so, return the phi node that corresponds to it.
586  ///
587  /// The IndVarSimplify pass transforms loops to have a canonical induction
588  /// variable.
589  ///
590  PHINode *getCanonicalInductionVariable() const;
591 
592  /// Obtain the unique incoming and back edge. Return false if they are
593  /// non-unique or the loop is dead; otherwise, return true.
594  bool getIncomingAndBackEdge(BasicBlock *&Incoming,
595  BasicBlock *&Backedge) const;
596 
597  /// Below are some utilities to get the loop guard, loop bounds and induction
598  /// variable, and to check if a given phinode is an auxiliary induction
599  /// variable, if the loop is guarded, and if the loop is canonical.
600  ///
601  /// Here is an example:
602  /// \code
603  /// for (int i = lb; i < ub; i+=step)
604  /// <loop body>
605  /// --- pseudo LLVMIR ---
606  /// beforeloop:
607  /// guardcmp = (lb < ub)
608  /// if (guardcmp) goto preheader; else goto afterloop
609  /// preheader:
610  /// loop:
611  /// i_1 = phi[{lb, preheader}, {i_2, latch}]
612  /// <loop body>
613  /// i_2 = i_1 + step
614  /// latch:
615  /// cmp = (i_2 < ub)
616  /// if (cmp) goto loop
617  /// exit:
618  /// afterloop:
619  /// \endcode
620  ///
621  /// - getBounds
622  /// - getInitialIVValue --> lb
623  /// - getStepInst --> i_2 = i_1 + step
624  /// - getStepValue --> step
625  /// - getFinalIVValue --> ub
626  /// - getCanonicalPredicate --> '<'
627  /// - getDirection --> Increasing
628  ///
629  /// - getInductionVariable --> i_1
630  /// - isAuxiliaryInductionVariable(x) --> true if x == i_1
631  /// - getLoopGuardBranch()
632  /// --> `if (guardcmp) goto preheader; else goto afterloop`
633  /// - isGuarded() --> true
634  /// - isCanonical --> false
635  struct LoopBounds {
636  /// Return the LoopBounds object if
637  /// - the given \p IndVar is an induction variable
638  /// - the initial value of the induction variable can be found
639  /// - the step instruction of the induction variable can be found
640  /// - the final value of the induction variable can be found
641  ///
642  /// Else None.
643  static Optional<Loop::LoopBounds> getBounds(const Loop &L, PHINode &IndVar,
644  ScalarEvolution &SE);
645 
646  /// Get the initial value of the loop induction variable.
647  Value &getInitialIVValue() const { return InitialIVValue; }
648 
649  /// Get the instruction that updates the loop induction variable.
650  Instruction &getStepInst() const { return StepInst; }
651 
652  /// Get the step that the loop induction variable gets updated by in each
653  /// loop iteration. Return nullptr if not found.
654  Value *getStepValue() const { return StepValue; }
655 
656  /// Get the final value of the loop induction variable.
657  Value &getFinalIVValue() const { return FinalIVValue; }
658 
659  /// Return the canonical predicate for the latch compare instruction, if
660  /// able to be calcuated. Else BAD_ICMP_PREDICATE.
661  ///
662  /// A predicate is considered as canonical if requirements below are all
663  /// satisfied:
664  /// 1. The first successor of the latch branch is the loop header
665  /// If not, inverse the predicate.
666  /// 2. One of the operands of the latch comparison is StepInst
667  /// If not, and
668  /// - if the current calcuated predicate is not ne or eq, flip the
669  /// predicate.
670  /// - else if the loop is increasing, return slt
671  /// (notice that it is safe to change from ne or eq to sign compare)
672  /// - else if the loop is decreasing, return sgt
673  /// (notice that it is safe to change from ne or eq to sign compare)
674  ///
675  /// Here is an example when both (1) and (2) are not satisfied:
676  /// \code
677  /// loop.header:
678  /// %iv = phi [%initialiv, %loop.preheader], [%inc, %loop.header]
679  /// %inc = add %iv, %step
680  /// %cmp = slt %iv, %finaliv
681  /// br %cmp, %loop.exit, %loop.header
682  /// loop.exit:
683  /// \endcode
684  /// - The second successor of the latch branch is the loop header instead
685  /// of the first successor (slt -> sge)
686  /// - The first operand of the latch comparison (%cmp) is the IndVar (%iv)
687  /// instead of the StepInst (%inc) (sge -> sgt)
688  ///
689  /// The predicate would be sgt if both (1) and (2) are satisfied.
690  /// getCanonicalPredicate() returns sgt for this example.
691  /// Note: The IR is not changed.
692  ICmpInst::Predicate getCanonicalPredicate() const;
693 
694  /// An enum for the direction of the loop
695  /// - for (int i = 0; i < ub; ++i) --> Increasing
696  /// - for (int i = ub; i > 0; --i) --> Descresing
697  /// - for (int i = x; i != y; i+=z) --> Unknown
698  enum class Direction { Increasing, Decreasing, Unknown };
699 
700  /// Get the direction of the loop.
701  Direction getDirection() const;
702 
703  private:
704  LoopBounds(const Loop &Loop, Value &I, Instruction &SI, Value *SV, Value &F,
705  ScalarEvolution &SE)
706  : L(Loop), InitialIVValue(I), StepInst(SI), StepValue(SV),
707  FinalIVValue(F), SE(SE) {}
708 
709  const Loop &L;
710 
711  // The initial value of the loop induction variable
712  Value &InitialIVValue;
713 
714  // The instruction that updates the loop induction variable
715  Instruction &StepInst;
716 
717  // The value that the loop induction variable gets updated by in each loop
718  // iteration
719  Value *StepValue;
720 
721  // The final value of the loop induction variable
722  Value &FinalIVValue;
723 
724  ScalarEvolution &SE;
725  };
726 
727  /// Return the struct LoopBounds collected if all struct members are found,
728  /// else None.
729  Optional<LoopBounds> getBounds(ScalarEvolution &SE) const;
730 
731  /// Return the loop induction variable if found, else return nullptr.
732  /// An instruction is considered as the loop induction variable if
733  /// - it is an induction variable of the loop; and
734  /// - it is used to determine the condition of the branch in the loop latch
735  ///
736  /// Note: the induction variable doesn't need to be canonical, i.e. starts at
737  /// zero and increments by one each time through the loop (but it can be).
738  PHINode *getInductionVariable(ScalarEvolution &SE) const;
739 
740  /// Get the loop induction descriptor for the loop induction variable. Return
741  /// true if the loop induction variable is found.
742  bool getInductionDescriptor(ScalarEvolution &SE,
743  InductionDescriptor &IndDesc) const;
744 
745  /// Return true if the given PHINode \p AuxIndVar is
746  /// - in the loop header
747  /// - not used outside of the loop
748  /// - incremented by a loop invariant step for each loop iteration
749  /// - step instruction opcode should be add or sub
750  /// Note: auxiliary induction variable is not required to be used in the
751  /// conditional branch in the loop latch. (but it can be)
752  bool isAuxiliaryInductionVariable(PHINode &AuxIndVar,
753  ScalarEvolution &SE) const;
754 
755  /// Return the loop guard branch, if it exists.
756  ///
757  /// This currently only works on simplified loop, as it requires a preheader
758  /// and a latch to identify the guard. It will work on loops of the form:
759  /// \code
760  /// GuardBB:
761  /// br cond1, Preheader, ExitSucc <== GuardBranch
762  /// Preheader:
763  /// br Header
764  /// Header:
765  /// ...
766  /// br Latch
767  /// Latch:
768  /// br cond2, Header, ExitBlock
769  /// ExitBlock:
770  /// br ExitSucc
771  /// ExitSucc:
772  /// \endcode
773  BranchInst *getLoopGuardBranch() const;
774 
775  /// Return true iff the loop is
776  /// - in simplify rotated form, and
777  /// - guarded by a loop guard branch.
778  bool isGuarded() const { return (getLoopGuardBranch() != nullptr); }
779 
780  /// Return true if the loop is in rotated form.
781  ///
782  /// This does not check if the loop was rotated by loop rotation, instead it
783  /// only checks if the loop is in rotated form (has a valid latch that exists
784  /// the loop).
785  bool isRotatedForm() const {
786  assert(!isInvalid() && "Loop not in a valid state!");
787  BasicBlock *Latch = getLoopLatch();
788  return Latch && isLoopExiting(Latch);
789  }
790 
791  /// Return true if the loop induction variable starts at zero and increments
792  /// by one each time through the loop.
793  bool isCanonical(ScalarEvolution &SE) const;
794 
795  /// Return true if the Loop is in LCSSA form.
796  bool isLCSSAForm(const DominatorTree &DT) const;
797 
798  /// Return true if this Loop and all inner subloops are in LCSSA form.
799  bool isRecursivelyLCSSAForm(const DominatorTree &DT,
800  const LoopInfo &LI) const;
801 
802  /// Return true if the Loop is in the form that the LoopSimplify form
803  /// transforms loops to, which is sometimes called normal form.
804  bool isLoopSimplifyForm() const;
805 
806  /// Return true if the loop body is safe to clone in practice.
807  bool isSafeToClone() const;
808 
809  /// Returns true if the loop is annotated parallel.
810  ///
811  /// A parallel loop can be assumed to not contain any dependencies between
812  /// iterations by the compiler. That is, any loop-carried dependency checking
813  /// can be skipped completely when parallelizing the loop on the target
814  /// machine. Thus, if the parallel loop information originates from the
815  /// programmer, e.g. via the OpenMP parallel for pragma, it is the
816  /// programmer's responsibility to ensure there are no loop-carried
817  /// dependencies. The final execution order of the instructions across
818  /// iterations is not guaranteed, thus, the end result might or might not
819  /// implement actual concurrent execution of instructions across multiple
820  /// iterations.
821  bool isAnnotatedParallel() const;
822 
823  /// Return the llvm.loop loop id metadata node for this loop if it is present.
824  ///
825  /// If this loop contains the same llvm.loop metadata on each branch to the
826  /// header then the node is returned. If any latch instruction does not
827  /// contain llvm.loop or if multiple latches contain different nodes then
828  /// 0 is returned.
829  MDNode *getLoopID() const;
830  /// Set the llvm.loop loop id metadata for this loop.
831  ///
832  /// The LoopID metadata node will be added to each terminator instruction in
833  /// the loop that branches to the loop header.
834  ///
835  /// The LoopID metadata node should have one or more operands and the first
836  /// operand should be the node itself.
837  void setLoopID(MDNode *LoopID) const;
838 
839  /// Add llvm.loop.unroll.disable to this loop's loop id metadata.
840  ///
841  /// Remove existing unroll metadata and add unroll disable metadata to
842  /// indicate the loop has already been unrolled. This prevents a loop
843  /// from being unrolled more than is directed by a pragma if the loop
844  /// unrolling pass is run more than once (which it generally is).
845  void setLoopAlreadyUnrolled();
846 
847  /// Add llvm.loop.mustprogress to this loop's loop id metadata.
848  void setLoopMustProgress();
849 
850  void dump() const;
851  void dumpVerbose() const;
852 
853  /// Return the debug location of the start of this loop.
854  /// This looks for a BB terminating instruction with a known debug
855  /// location by looking at the preheader and header blocks. If it
856  /// cannot find a terminating instruction with location information,
857  /// it returns an unknown location.
858  DebugLoc getStartLoc() const;
859 
860  /// Return the source code span of the loop.
861  LocRange getLocRange() const;
862 
863  StringRef getName() const {
864  if (BasicBlock *Header = getHeader())
865  if (Header->hasName())
866  return Header->getName();
867  return "<unnamed loop>";
868  }
869 
870 private:
871  Loop() = default;
872 
875  explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {}
876  ~Loop() = default;
877 };
878 
879 //===----------------------------------------------------------------------===//
880 /// This class builds and contains all of the top-level loop
881 /// structures in the specified function.
882 ///
883 
884 template <class BlockT, class LoopT> class LoopInfoBase {
885  // BBMap - Mapping of basic blocks to the inner most loop they occur in
886  DenseMap<const BlockT *, LoopT *> BBMap;
887  std::vector<LoopT *> TopLevelLoops;
888  BumpPtrAllocator LoopAllocator;
889 
891  friend class LoopInfo;
892 
893  void operator=(const LoopInfoBase &) = delete;
894  LoopInfoBase(const LoopInfoBase &) = delete;
895 
896 public:
898  ~LoopInfoBase() { releaseMemory(); }
899 
901  : BBMap(std::move(Arg.BBMap)),
902  TopLevelLoops(std::move(Arg.TopLevelLoops)),
903  LoopAllocator(std::move(Arg.LoopAllocator)) {
904  // We have to clear the arguments top level loops as we've taken ownership.
905  Arg.TopLevelLoops.clear();
906  }
908  BBMap = std::move(RHS.BBMap);
909 
910  for (auto *L : TopLevelLoops)
911  L->~LoopT();
912 
913  TopLevelLoops = std::move(RHS.TopLevelLoops);
914  LoopAllocator = std::move(RHS.LoopAllocator);
915  RHS.TopLevelLoops.clear();
916  return *this;
917  }
918 
919  void releaseMemory() {
920  BBMap.clear();
921 
922  for (auto *L : TopLevelLoops)
923  L->~LoopT();
924  TopLevelLoops.clear();
925  LoopAllocator.Reset();
926  }
927 
928  template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
929  LoopT *Storage = LoopAllocator.Allocate<LoopT>();
930  return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
931  }
932 
933  /// iterator/begin/end - The interface to the top-level loops in the current
934  /// function.
935  ///
936  typedef typename std::vector<LoopT *>::const_iterator iterator;
937  typedef
938  typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
939  iterator begin() const { return TopLevelLoops.begin(); }
940  iterator end() const { return TopLevelLoops.end(); }
941  reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
942  reverse_iterator rend() const { return TopLevelLoops.rend(); }
943  bool empty() const { return TopLevelLoops.empty(); }
944 
945  /// Return all of the loops in the function in preorder across the loop
946  /// nests, with siblings in forward program order.
947  ///
948  /// Note that because loops form a forest of trees, preorder is equivalent to
949  /// reverse postorder.
950  SmallVector<LoopT *, 4> getLoopsInPreorder();
951 
952  /// Return all of the loops in the function in preorder across the loop
953  /// nests, with siblings in *reverse* program order.
954  ///
955  /// Note that because loops form a forest of trees, preorder is equivalent to
956  /// reverse postorder.
957  ///
958  /// Also note that this is *not* a reverse preorder. Only the siblings are in
959  /// reverse program order.
960  SmallVector<LoopT *, 4> getLoopsInReverseSiblingPreorder();
961 
962  /// Return the inner most loop that BB lives in. If a basic block is in no
963  /// loop (for example the entry node), null is returned.
964  LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
965 
966  /// Same as getLoopFor.
967  const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); }
968 
969  /// Return the loop nesting level of the specified block. A depth of 0 means
970  /// the block is not inside any loop.
971  unsigned getLoopDepth(const BlockT *BB) const {
972  const LoopT *L = getLoopFor(BB);
973  return L ? L->getLoopDepth() : 0;
974  }
975 
976  // True if the block is a loop header node
977  bool isLoopHeader(const BlockT *BB) const {
978  const LoopT *L = getLoopFor(BB);
979  return L && L->getHeader() == BB;
980  }
981 
982  /// Return the top-level loops.
983  const std::vector<LoopT *> &getTopLevelLoops() const { return TopLevelLoops; }
984 
985  /// Return the top-level loops.
986  std::vector<LoopT *> &getTopLevelLoopsVector() { return TopLevelLoops; }
987 
988  /// This removes the specified top-level loop from this loop info object.
989  /// The loop is not deleted, as it will presumably be inserted into
990  /// another loop.
992  assert(I != end() && "Cannot remove end iterator!");
993  LoopT *L = *I;
994  assert(L->isOutermost() && "Not a top-level loop!");
995  TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));
996  return L;
997  }
998 
999  /// Change the top-level loop that contains BB to the specified loop.
1000  /// This should be used by transformations that restructure the loop hierarchy
1001  /// tree.
1002  void changeLoopFor(BlockT *BB, LoopT *L) {
1003  if (!L) {
1004  BBMap.erase(BB);
1005  return;
1006  }
1007  BBMap[BB] = L;
1008  }
1009 
1010  /// Replace the specified loop in the top-level loops list with the indicated
1011  /// loop.
1012  void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) {
1013  auto I = find(TopLevelLoops, OldLoop);
1014  assert(I != TopLevelLoops.end() && "Old loop not at top level!");
1015  *I = NewLoop;
1016  assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
1017  "Loops already embedded into a subloop!");
1018  }
1019 
1020  /// This adds the specified loop to the collection of top-level loops.
1021  void addTopLevelLoop(LoopT *New) {
1022  assert(New->isOutermost() && "Loop already in subloop!");
1023  TopLevelLoops.push_back(New);
1024  }
1025 
1026  /// This method completely removes BB from all data structures,
1027  /// including all of the Loop objects it is nested in and our mapping from
1028  /// BasicBlocks to loops.
1029  void removeBlock(BlockT *BB) {
1030  auto I = BBMap.find(BB);
1031  if (I != BBMap.end()) {
1032  for (LoopT *L = I->second; L; L = L->getParentLoop())
1033  L->removeBlockFromLoop(BB);
1034 
1035  BBMap.erase(I);
1036  }
1037  }
1038 
1039  // Internals
1040 
1041  static bool isNotAlreadyContainedIn(const LoopT *SubLoop,
1042  const LoopT *ParentLoop) {
1043  if (!SubLoop)
1044  return true;
1045  if (SubLoop == ParentLoop)
1046  return false;
1047  return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
1048  }
1049 
1050  /// Create the loop forest using a stable algorithm.
1051  void analyze(const DominatorTreeBase<BlockT, false> &DomTree);
1052 
1053  // Debugging
1054  void print(raw_ostream &OS) const;
1055 
1056  void verify(const DominatorTreeBase<BlockT, false> &DomTree) const;
1057 
1058  /// Destroy a loop that has been removed from the `LoopInfo` nest.
1059  ///
1060  /// This runs the destructor of the loop object making it invalid to
1061  /// reference afterward. The memory is retained so that the *pointer* to the
1062  /// loop remains valid.
1063  ///
1064  /// The caller is responsible for removing this loop from the loop nest and
1065  /// otherwise disconnecting it from the broader `LoopInfo` data structures.
1066  /// Callers that don't naturally handle this themselves should probably call
1067  /// `erase' instead.
1068  void destroy(LoopT *L) {
1069  L->~LoopT();
1070 
1071  // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons
1072  // \c L, but the pointer remains valid for non-dereferencing uses.
1073  LoopAllocator.Deallocate(L);
1074  }
1075 };
1076 
1077 // Implementation in LoopInfoImpl.h
1078 extern template class LoopInfoBase<BasicBlock, Loop>;
1079 
1082 
1084 
1085  void operator=(const LoopInfo &) = delete;
1086  LoopInfo(const LoopInfo &) = delete;
1087 
1088 public:
1090  explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree);
1091 
1092  LoopInfo(LoopInfo &&Arg) : BaseT(std::move(static_cast<BaseT &>(Arg))) {}
1094  BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
1095  return *this;
1096  }
1097 
1098  /// Handle invalidation explicitly.
1099  bool invalidate(Function &F, const PreservedAnalyses &PA,
1101 
1102  // Most of the public interface is provided via LoopInfoBase.
1103 
1104  /// Update LoopInfo after removing the last backedge from a loop. This updates
1105  /// the loop forest and parent loops for each block so that \c L is no longer
1106  /// referenced, but does not actually delete \c L immediately. The pointer
1107  /// will remain valid until this LoopInfo's memory is released.
1108  void erase(Loop *L);
1109 
1110  /// Returns true if replacing From with To everywhere is guaranteed to
1111  /// preserve LCSSA form.
1113  // Preserving LCSSA form is only problematic if the replacing value is an
1114  // instruction.
1115  Instruction *I = dyn_cast<Instruction>(To);
1116  if (!I)
1117  return true;
1118  // If both instructions are defined in the same basic block then replacement
1119  // cannot break LCSSA form.
1120  if (I->getParent() == From->getParent())
1121  return true;
1122  // If the instruction is not defined in a loop then it can safely replace
1123  // anything.
1124  Loop *ToLoop = getLoopFor(I->getParent());
1125  if (!ToLoop)
1126  return true;
1127  // If the replacing instruction is defined in the same loop as the original
1128  // instruction, or in a loop that contains it as an inner loop, then using
1129  // it as a replacement will not break LCSSA form.
1130  return ToLoop->contains(getLoopFor(From->getParent()));
1131  }
1132 
1133  /// Checks if moving a specific instruction can break LCSSA in any loop.
1134  ///
1135  /// Return true if moving \p Inst to before \p NewLoc will break LCSSA,
1136  /// assuming that the function containing \p Inst and \p NewLoc is currently
1137  /// in LCSSA form.
1139  assert(Inst->getFunction() == NewLoc->getFunction() &&
1140  "Can't reason about IPO!");
1141 
1142  auto *OldBB = Inst->getParent();
1143  auto *NewBB = NewLoc->getParent();
1144 
1145  // Movement within the same loop does not break LCSSA (the equality check is
1146  // to avoid doing a hashtable lookup in case of intra-block movement).
1147  if (OldBB == NewBB)
1148  return true;
1149 
1150  auto *OldLoop = getLoopFor(OldBB);
1151  auto *NewLoop = getLoopFor(NewBB);
1152 
1153  if (OldLoop == NewLoop)
1154  return true;
1155 
1156  // Check if Outer contains Inner; with the null loop counting as the
1157  // "outermost" loop.
1158  auto Contains = [](const Loop *Outer, const Loop *Inner) {
1159  return !Outer || Outer->contains(Inner);
1160  };
1161 
1162  // To check that the movement of Inst to before NewLoc does not break LCSSA,
1163  // we need to check two sets of uses for possible LCSSA violations at
1164  // NewLoc: the users of NewInst, and the operands of NewInst.
1165 
1166  // If we know we're hoisting Inst out of an inner loop to an outer loop,
1167  // then the uses *of* Inst don't need to be checked.
1168 
1169  if (!Contains(NewLoop, OldLoop)) {
1170  for (Use &U : Inst->uses()) {
1171  auto *UI = cast<Instruction>(U.getUser());
1172  auto *UBB = isa<PHINode>(UI) ? cast<PHINode>(UI)->getIncomingBlock(U)
1173  : UI->getParent();
1174  if (UBB != NewBB && getLoopFor(UBB) != NewLoop)
1175  return false;
1176  }
1177  }
1178 
1179  // If we know we're sinking Inst from an outer loop into an inner loop, then
1180  // the *operands* of Inst don't need to be checked.
1181 
1182  if (!Contains(OldLoop, NewLoop)) {
1183  // See below on why we can't handle phi nodes here.
1184  if (isa<PHINode>(Inst))
1185  return false;
1186 
1187  for (Use &U : Inst->operands()) {
1188  auto *DefI = dyn_cast<Instruction>(U.get());
1189  if (!DefI)
1190  return false;
1191 
1192  // This would need adjustment if we allow Inst to be a phi node -- the
1193  // new use block won't simply be NewBB.
1194 
1195  auto *DefBlock = DefI->getParent();
1196  if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop)
1197  return false;
1198  }
1199  }
1200 
1201  return true;
1202  }
1203 
1204  // Return true if a new use of V added in ExitBB would require an LCSSA PHI
1205  // to be inserted at the begining of the block. Note that V is assumed to
1206  // dominate ExitBB, and ExitBB must be the exit block of some loop. The
1207  // IR is assumed to be in LCSSA form before the planned insertion.
1208  bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V,
1209  const BasicBlock *ExitBB) const;
1210 
1211 };
1212 
1213 // Allow clients to walk the list of nested loops...
1214 template <> struct GraphTraits<const Loop *> {
1215  typedef const Loop *NodeRef;
1217 
1218  static NodeRef getEntryNode(const Loop *L) { return L; }
1219  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
1220  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
1221 };
1222 
1223 template <> struct GraphTraits<Loop *> {
1224  typedef Loop *NodeRef;
1226 
1227  static NodeRef getEntryNode(Loop *L) { return L; }
1228  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
1229  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
1230 };
1231 
1232 /// Analysis pass that exposes the \c LoopInfo for a function.
1235  static AnalysisKey Key;
1236 
1237 public:
1238  typedef LoopInfo Result;
1239 
1241 };
1242 
1243 /// Printer pass for the \c LoopAnalysis results.
1245  raw_ostream &OS;
1246 
1247 public:
1248  explicit LoopPrinterPass(raw_ostream &OS) : OS(OS) {}
1250 };
1251 
1252 /// Verifier pass for the \c LoopAnalysis results.
1255 };
1256 
1257 /// The legacy pass manager's analysis pass to compute loop information.
1259  LoopInfo LI;
1260 
1261 public:
1262  static char ID; // Pass identification, replacement for typeid
1263 
1265 
1266  LoopInfo &getLoopInfo() { return LI; }
1267  const LoopInfo &getLoopInfo() const { return LI; }
1268 
1269  /// Calculate the natural loop information for a given function.
1270  bool runOnFunction(Function &F) override;
1271 
1272  void verifyAnalysis() const override;
1273 
1274  void releaseMemory() override { LI.releaseMemory(); }
1275 
1276  void print(raw_ostream &O, const Module *M = nullptr) const override;
1277 
1278  void getAnalysisUsage(AnalysisUsage &AU) const override;
1279 };
1280 
1281 /// Function to print a loop's contents as LLVM's text IR assembly.
1282 void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner = "");
1283 
1284 /// Find and return the loop attribute node for the attribute @p Name in
1285 /// @p LoopID. Return nullptr if there is no such attribute.
1286 MDNode *findOptionMDForLoopID(MDNode *LoopID, StringRef Name);
1287 
1288 /// Find string metadata for a loop.
1289 ///
1290 /// Returns the MDNode where the first operand is the metadata's name. The
1291 /// following operands are the metadata's values. If no metadata with @p Name is
1292 /// found, return nullptr.
1293 MDNode *findOptionMDForLoop(const Loop *TheLoop, StringRef Name);
1294 
1295 /// Return whether an MDNode might represent an access group.
1296 ///
1297 /// Access group metadata nodes have to be distinct and empty. Being
1298 /// always-empty ensures that it never needs to be changed (which -- because
1299 /// MDNodes are designed immutable -- would require creating a new MDNode). Note
1300 /// that this is not a sufficient condition: not every distinct and empty NDNode
1301 /// is representing an access group.
1302 bool isValidAsAccessGroup(MDNode *AccGroup);
1303 
1304 /// Create a new LoopID after the loop has been transformed.
1305 ///
1306 /// This can be used when no follow-up loop attributes are defined
1307 /// (llvm::makeFollowupLoopID returning None) to stop transformations to be
1308 /// applied again.
1309 ///
1310 /// @param Context The LLVMContext in which to create the new LoopID.
1311 /// @param OrigLoopID The original LoopID; can be nullptr if the original
1312 /// loop has no LoopID.
1313 /// @param RemovePrefixes Remove all loop attributes that have these prefixes.
1314 /// Use to remove metadata of the transformation that has
1315 /// been applied.
1316 /// @param AddAttrs Add these loop attributes to the new LoopID.
1317 ///
1318 /// @return A new LoopID that can be applied using Loop::setLoopID().
1319 llvm::MDNode *
1321  llvm::ArrayRef<llvm::StringRef> RemovePrefixes,
1323 
1324 } // End llvm namespace
1325 
1326 #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:155
llvm::LoopBase::rend
reverse_iterator rend() const
Definition: LoopInfo.h:157
llvm::orc::BaseT
RTTIExtends< ObjectLinkingLayer, ObjectLayer > BaseT
Definition: ObjectLinkingLayer.cpp:471
llvm::LoopInfo::movementPreservesLCSSAForm
bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc)
Checks if moving a specific instruction can break LCSSA in any loop.
Definition: LoopInfo.h:1138
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:1228
llvm
Definition: AllocatorList.h:23
llvm::LoopBase::getUniqueExitBlock
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:138
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:62
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:378
llvm::LoopBase::getExitBlock
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:82
llvm::GraphTraits< Loop * >
Definition: LoopInfo.h:1223
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
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:657
llvm::PassInfoMixin< LoopPrinterPass >
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::LoopInfo::LoopInfo
LoopInfo(LoopInfo &&Arg)
Definition: LoopInfo.h:1092
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:1168
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:195
llvm::LoopBase::reverse_iterator
std::vector< LoopT * >::const_reverse_iterator reverse_iterator
Definition: LoopInfo.h:153
llvm::LoopInfoBase::~LoopInfoBase
~LoopInfoBase()
Definition: LoopInfo.h:898
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:1227
Allocator.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
llvm::LoopInfoBase::changeLoopFor
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1002
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:34
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:1029
DenseMap.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:338
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:1274
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1258
llvm::LoopInfo::LoopInfo
LoopInfo()
Definition: LoopInfo.h:1089
llvm::LoopBase::getExitEdges
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
Definition: LoopInfoImpl.h:148
llvm::Optional
Definition: APInt.h:34
llvm::BumpPtrAllocator
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:369
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:876
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:635
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:986
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:1219
llvm::findOptionMDForLoopID
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Definition: LoopInfo.cpp:1012
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:56
llvm::LoopBase::block_end
block_iterator block_end() const
Definition: LoopInfo.h:177
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:1046
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
GraphTraits.h
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:205
Instruction.h
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::LoopInfoBase::isNotAlreadyContainedIn
static bool isNotAlreadyContainedIn(const LoopT *SubLoop, const LoopT *ParentLoop)
Definition: LoopInfo.h:1041
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:648
llvm::GraphTraits< const Loop * >
Definition: LoopInfo.h:1214
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:1266
SI
@ SI
Definition: SIInstrInfo.cpp:7342
llvm::LoopAnalysis::Result
LoopInfo Result
Definition: LoopInfo.h:1238
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:1021
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:481
llvm::LoopInfoBase::destroy
void destroy(LoopT *L)
Destroy a loop that has been removed from the LoopInfo nest.
Definition: LoopInfo.h:1068
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:389
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:1112
DenseSet.h
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:972
llvm::Instruction
Definition: Instruction.h:45
llvm::LoopInfoBase::operator=
LoopInfoBase & operator=(LoopInfoBase &&RHS)
Definition: LoopInfo.h:907
llvm::LoopBase::verifyLoop
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:286
llvm::GraphTraits< Loop * >::NodeRef
Loop * NodeRef
Definition: LoopInfo.h:1224
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:50
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:34
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
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:372
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:670
llvm::LoopBase::getExitingBlock
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
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
getInductionVariable
static PHINode * getInductionVariable(Loop *L, ScalarEvolution *SE)
Definition: LoopInterchange.cpp:295
llvm::Loop::getName
StringRef getName() const
Definition: LoopInfo.h:863
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:698
llvm::GraphTraits< const Loop * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: LoopInfo.h:1220
CFG.h
llvm::LoopInfoBase::AllocateLoop
LoopT * AllocateLoop(ArgsTy &&... Args)
Definition: LoopInfo.h:928
llvm::LoopVerifierPass
Verifier pass for the LoopAnalysis results.
Definition: LoopInfo.h:1253
llvm::LoopBase::block_begin
block_iterator block_begin() const
Definition: LoopInfo.h:176
llvm::LoopInfoWrapperPass::getLoopInfo
const LoopInfo & getLoopInfo() const
Definition: LoopInfo.h:1267
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:175
llvm::LoopInfoBase::LoopInfo
friend class LoopInfo
Definition: LoopInfo.h:891
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:128
llvm::Loop::isGuarded
bool isGuarded() const
Return true iff the loop is.
Definition: LoopInfo.h:778
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:56
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:1525
llvm::LoopBase::getUniqueExitBlocks
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfoImpl.h:122
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:72
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:964
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
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:650
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
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:92
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:1563
llvm::Loop::LocRange::LocRange
LocRange()
Definition: LoopInfo.h:538
llvm::LoopBase::getLoopDepth
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:96
llvm::children
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:121
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:939
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::MDNode
Metadata node.
Definition: Metadata.h:897
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:382
llvm::LoopInfoBase::LoopInfoBase
LoopInfoBase(LoopInfoBase &&Arg)
Definition: LoopInfo.h:900
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:1486
llvm::LoopInfoBase::getLoopDepth
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
Definition: LoopInfo.h:971
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
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:33
llvm::LoopInfo
Definition: LoopInfo.h:1080
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
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:70
verify
ppc ctr loops verify
Definition: PPCCTRLoops.cpp:76
llvm::LoopBase::replaceChildLoopWith
void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild)
This is used when splitting loops up.
Definition: LoopInfoImpl.h:272
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:1038
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:129
llvm::LoopInfoBase::removeLoop
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
Definition: LoopInfo.h:991
llvm::GraphTraits< Loop * >::ChildIteratorType
LoopInfo::iterator ChildIteratorType
Definition: LoopInfo.h:1225
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:1216
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:977
llvm::Loop::LoopBounds
Below are some utilities to get the loop guard, loop bounds and induction variable,...
Definition: LoopInfo.h:635
llvm::isValidAsAccessGroup
bool isValidAsAccessGroup(MDNode *AccGroup)
Return whether an MDNode might represent an access group.
Definition: LoopInfo.cpp:1042
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
std
Definition: BitVector.h:838
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:58
llvm::GraphTraits< Loop * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: LoopInfo.h:1229
llvm::LoopInfoBase::LoopInfoBase
LoopInfoBase()
Definition: LoopInfo.h:897
llvm::LoopInfoBase::operator[]
const LoopT * operator[](const BlockT *BB) const
Same as getLoopFor.
Definition: LoopInfo.h:967
llvm::Loop::LoopBounds::getInitialIVValue
Value & getInitialIVValue() const
Get the initial value of the loop induction variable.
Definition: LoopInfo.h:647
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:229
llvm::LoopInfoBase::rbegin
reverse_iterator rbegin() const
Definition: LoopInfo.h:941
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:1244
llvm::LoopInfoBase::reverse_iterator
std::vector< LoopT * >::const_reverse_iterator reverse_iterator
Definition: LoopInfo.h:938
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:95
llvm::LoopBase::hasNoExitBlocks
bool hasNoExitBlocks() const
Return true if this loop does not have any exit blocks.
Definition: LoopInfoImpl.h:73
llvm::LoopPrinterPass::LoopPrinterPass
LoopPrinterPass(raw_ostream &OS)
Definition: LoopInfo.h:1248
llvm::LoopInfoBase::end
iterator end() const
Definition: LoopInfo.h:940
llvm::LoopInfoBase::rend
reverse_iterator rend() const
Definition: LoopInfo.h:942
Instructions.h
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:242
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:1012
llvm::LoopInfoBase::releaseMemory
void releaseMemory()
Definition: LoopInfo.h:919
N
#define N
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
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:2572
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:936
llvm::LoopInfoBase::empty
bool empty() const
Definition: LoopInfo.h:943
llvm::SmallVectorImpl< BlockT * >
llvm::SmallPtrSetImpl< const BlockT * >
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
isCanonical
static bool isCanonical(const MDString *S)
Definition: DebugInfoMetadata.cpp:272
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
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:384
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:1218
llvm::GraphTraits
Definition: GraphTraits.h:35
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:389
llvm::Loop::isRotatedForm
bool isRotatedForm() const
Return true if the loop is in rotated form.
Definition: LoopInfo.h:785
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:1215
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:654
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::LoopInfoBase::getTopLevelLoops
const std::vector< LoopT * > & getTopLevelLoops() const
Return the top-level loops.
Definition: LoopInfo.h:983
llvm::LoopInfo::operator=
LoopInfo & operator=(LoopInfo &&RHS)
Definition: LoopInfo.h:1093
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1233
llvm::LoopInfoWrapperPass::ID
static char ID
Definition: LoopInfo.h:1262
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
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:364