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