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