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