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