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