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