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

source code of llvm/include/llvm/Analysis/LoopInfo.h