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