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() {} 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 the value after any hoisting is loop invariant. This 561 /// function can be used as a slightly more aggressive replacement for 562 /// isLoopInvariant. 563 /// 564 /// If InsertPt is specified, it is the point to hoist instructions to. 565 /// If null, the terminator of the loop preheader is used. 566 bool makeLoopInvariant(Value *V, bool &Changed, 567 Instruction *InsertPt = nullptr, 568 MemorySSAUpdater *MSSAU = nullptr) const; 569 570 /// If the given instruction is inside of the loop and it can be hoisted, do 571 /// so to make it trivially loop-invariant. 572 /// Return true if the instruction after any hoisting is loop invariant. This 573 /// function can be used as a slightly more aggressive replacement for 574 /// isLoopInvariant. 575 /// 576 /// If InsertPt is specified, it is the point to hoist instructions to. 577 /// If null, the terminator of the loop preheader is used. 578 /// 579 bool makeLoopInvariant(Instruction *I, bool &Changed, 580 Instruction *InsertPt = nullptr, 581 MemorySSAUpdater *MSSAU = nullptr) const; 582 583 /// Check to see if the loop has a canonical induction variable: an integer 584 /// recurrence that starts at 0 and increments by one each time through the 585 /// loop. If so, return the phi node that corresponds to it. 586 /// 587 /// The IndVarSimplify pass transforms loops to have a canonical induction 588 /// variable. 589 /// 590 PHINode *getCanonicalInductionVariable() const; 591 592 /// Get the latch condition instruction. 593 ICmpInst *getLatchCmpInst() const; 594 595 /// Obtain the unique incoming and back edge. Return false if they are 596 /// non-unique or the loop is dead; otherwise, return true. 597 bool getIncomingAndBackEdge(BasicBlock *&Incoming, 598 BasicBlock *&Backedge) const; 599 600 /// Below are some utilities to get the loop guard, loop bounds and induction 601 /// variable, and to check if a given phinode is an auxiliary induction 602 /// variable, if the loop is guarded, and if the loop is canonical. 603 /// 604 /// Here is an example: 605 /// \code 606 /// for (int i = lb; i < ub; i+=step) 607 /// <loop body> 608 /// --- pseudo LLVMIR --- 609 /// beforeloop: 610 /// guardcmp = (lb < ub) 611 /// if (guardcmp) goto preheader; else goto afterloop 612 /// preheader: 613 /// loop: 614 /// i_1 = phi[{lb, preheader}, {i_2, latch}] 615 /// <loop body> 616 /// i_2 = i_1 + step 617 /// latch: 618 /// cmp = (i_2 < ub) 619 /// if (cmp) goto loop 620 /// exit: 621 /// afterloop: 622 /// \endcode 623 /// 624 /// - getBounds 625 /// - getInitialIVValue --> lb 626 /// - getStepInst --> i_2 = i_1 + step 627 /// - getStepValue --> step 628 /// - getFinalIVValue --> ub 629 /// - getCanonicalPredicate --> '<' 630 /// - getDirection --> Increasing 631 /// 632 /// - getInductionVariable --> i_1 633 /// - isAuxiliaryInductionVariable(x) --> true if x == i_1 634 /// - getLoopGuardBranch() 635 /// --> `if (guardcmp) goto preheader; else goto afterloop` 636 /// - isGuarded() --> true 637 /// - isCanonical --> false 638 struct LoopBounds { 639 /// Return the LoopBounds object if 640 /// - the given \p IndVar is an induction variable 641 /// - the initial value of the induction variable can be found 642 /// - the step instruction of the induction variable can be found 643 /// - the final value of the induction variable can be found 644 /// 645 /// Else None. 646 static Optional<Loop::LoopBounds> getBounds(const Loop &L, PHINode &IndVar, 647 ScalarEvolution &SE); 648 649 /// Get the initial value of the loop induction variable. 650 Value &getInitialIVValue() const { return InitialIVValue; } 651 652 /// Get the instruction that updates the loop induction variable. 653 Instruction &getStepInst() const { return StepInst; } 654 655 /// Get the step that the loop induction variable gets updated by in each 656 /// loop iteration. Return nullptr if not found. 657 Value *getStepValue() const { return StepValue; } 658 659 /// Get the final value of the loop induction variable. 660 Value &getFinalIVValue() const { return FinalIVValue; } 661 662 /// Return the canonical predicate for the latch compare instruction, if 663 /// able to be calcuated. Else BAD_ICMP_PREDICATE. 664 /// 665 /// A predicate is considered as canonical if requirements below are all 666 /// satisfied: 667 /// 1. The first successor of the latch branch is the loop header 668 /// If not, inverse the predicate. 669 /// 2. One of the operands of the latch comparison is StepInst 670 /// If not, and 671 /// - if the current calcuated predicate is not ne or eq, flip the 672 /// predicate. 673 /// - else if the loop is increasing, return slt 674 /// (notice that it is safe to change from ne or eq to sign compare) 675 /// - else if the loop is decreasing, return sgt 676 /// (notice that it is safe to change from ne or eq to sign compare) 677 /// 678 /// Here is an example when both (1) and (2) are not satisfied: 679 /// \code 680 /// loop.header: 681 /// %iv = phi [%initialiv, %loop.preheader], [%inc, %loop.header] 682 /// %inc = add %iv, %step 683 /// %cmp = slt %iv, %finaliv 684 /// br %cmp, %loop.exit, %loop.header 685 /// loop.exit: 686 /// \endcode 687 /// - The second successor of the latch branch is the loop header instead 688 /// of the first successor (slt -> sge) 689 /// - The first operand of the latch comparison (%cmp) is the IndVar (%iv) 690 /// instead of the StepInst (%inc) (sge -> sgt) 691 /// 692 /// The predicate would be sgt if both (1) and (2) are satisfied. 693 /// getCanonicalPredicate() returns sgt for this example. 694 /// Note: The IR is not changed. 695 ICmpInst::Predicate getCanonicalPredicate() const; 696 697 /// An enum for the direction of the loop 698 /// - for (int i = 0; i < ub; ++i) --> Increasing 699 /// - for (int i = ub; i > 0; --i) --> Descresing 700 /// - for (int i = x; i != y; i+=z) --> Unknown 701 enum class Direction { Increasing, Decreasing, Unknown }; 702 703 /// Get the direction of the loop. 704 Direction getDirection() const; 705 706 private: 707 LoopBounds(const Loop &Loop, Value &I, Instruction &SI, Value *SV, Value &F, 708 ScalarEvolution &SE) 709 : L(Loop), InitialIVValue(I), StepInst(SI), StepValue(SV), 710 FinalIVValue(F), SE(SE) {} 711 712 const Loop &L; 713 714 // The initial value of the loop induction variable 715 Value &InitialIVValue; 716 717 // The instruction that updates the loop induction variable 718 Instruction &StepInst; 719 720 // The value that the loop induction variable gets updated by in each loop 721 // iteration 722 Value *StepValue; 723 724 // The final value of the loop induction variable 725 Value &FinalIVValue; 726 727 ScalarEvolution &SE; 728 }; 729 730 /// Return the struct LoopBounds collected if all struct members are found, 731 /// else None. 732 Optional<LoopBounds> getBounds(ScalarEvolution &SE) const; 733 734 /// Return the loop induction variable if found, else return nullptr. 735 /// An instruction is considered as the loop induction variable if 736 /// - it is an induction variable of the loop; and 737 /// - it is used to determine the condition of the branch in the loop latch 738 /// 739 /// Note: the induction variable doesn't need to be canonical, i.e. starts at 740 /// zero and increments by one each time through the loop (but it can be). 741 PHINode *getInductionVariable(ScalarEvolution &SE) const; 742 743 /// Get the loop induction descriptor for the loop induction variable. Return 744 /// true if the loop induction variable is found. 745 bool getInductionDescriptor(ScalarEvolution &SE, 746 InductionDescriptor &IndDesc) const; 747 748 /// Return true if the given PHINode \p AuxIndVar is 749 /// - in the loop header 750 /// - not used outside of the loop 751 /// - incremented by a loop invariant step for each loop iteration 752 /// - step instruction opcode should be add or sub 753 /// Note: auxiliary induction variable is not required to be used in the 754 /// conditional branch in the loop latch. (but it can be) 755 bool isAuxiliaryInductionVariable(PHINode &AuxIndVar, 756 ScalarEvolution &SE) const; 757 758 /// Return the loop guard branch, if it exists. 759 /// 760 /// This currently only works on simplified loop, as it requires a preheader 761 /// and a latch to identify the guard. It will work on loops of the form: 762 /// \code 763 /// GuardBB: 764 /// br cond1, Preheader, ExitSucc <== GuardBranch 765 /// Preheader: 766 /// br Header 767 /// Header: 768 /// ... 769 /// br Latch 770 /// Latch: 771 /// br cond2, Header, ExitBlock 772 /// ExitBlock: 773 /// br ExitSucc 774 /// ExitSucc: 775 /// \endcode 776 BranchInst *getLoopGuardBranch() const; 777 778 /// Return true iff the loop is 779 /// - in simplify rotated form, and 780 /// - guarded by a loop guard branch. 781 bool isGuarded() const { return (getLoopGuardBranch() != nullptr); } 782 783 /// Return true if the loop is in rotated form. 784 /// 785 /// This does not check if the loop was rotated by loop rotation, instead it 786 /// only checks if the loop is in rotated form (has a valid latch that exists 787 /// the loop). 788 bool isRotatedForm() const { 789 assert(!isInvalid() && "Loop not in a valid state!"); 790 BasicBlock *Latch = getLoopLatch(); 791 return Latch && isLoopExiting(Latch); 792 } 793 794 /// Return true if the loop induction variable starts at zero and increments 795 /// by one each time through the loop. 796 bool isCanonical(ScalarEvolution &SE) const; 797 798 /// Return true if the Loop is in LCSSA form. 799 bool isLCSSAForm(const DominatorTree &DT) const; 800 801 /// Return true if this Loop and all inner subloops are in LCSSA form. 802 bool isRecursivelyLCSSAForm(const DominatorTree &DT, 803 const LoopInfo &LI) const; 804 805 /// Return true if the Loop is in the form that the LoopSimplify form 806 /// transforms loops to, which is sometimes called normal form. 807 bool isLoopSimplifyForm() const; 808 809 /// Return true if the loop body is safe to clone in practice. 810 bool isSafeToClone() const; 811 812 /// Returns true if the loop is annotated parallel. 813 /// 814 /// A parallel loop can be assumed to not contain any dependencies between 815 /// iterations by the compiler. That is, any loop-carried dependency checking 816 /// can be skipped completely when parallelizing the loop on the target 817 /// machine. Thus, if the parallel loop information originates from the 818 /// programmer, e.g. via the OpenMP parallel for pragma, it is the 819 /// programmer's responsibility to ensure there are no loop-carried 820 /// dependencies. The final execution order of the instructions across 821 /// iterations is not guaranteed, thus, the end result might or might not 822 /// implement actual concurrent execution of instructions across multiple 823 /// iterations. 824 bool isAnnotatedParallel() const; 825 826 /// Return the llvm.loop loop id metadata node for this loop if it is present. 827 /// 828 /// If this loop contains the same llvm.loop metadata on each branch to the 829 /// header then the node is returned. If any latch instruction does not 830 /// contain llvm.loop or if multiple latches contain different nodes then 831 /// 0 is returned. 832 MDNode *getLoopID() const; 833 /// Set the llvm.loop loop id metadata for this loop. 834 /// 835 /// The LoopID metadata node will be added to each terminator instruction in 836 /// the loop that branches to the loop header. 837 /// 838 /// The LoopID metadata node should have one or more operands and the first 839 /// operand should be the node itself. 840 void setLoopID(MDNode *LoopID) const; 841 842 /// Add llvm.loop.unroll.disable to this loop's loop id metadata. 843 /// 844 /// Remove existing unroll metadata and add unroll disable metadata to 845 /// indicate the loop has already been unrolled. This prevents a loop 846 /// from being unrolled more than is directed by a pragma if the loop 847 /// unrolling pass is run more than once (which it generally is). 848 void setLoopAlreadyUnrolled(); 849 850 /// Add llvm.loop.mustprogress to this loop's loop id metadata. 851 void setLoopMustProgress(); 852 853 void dump() const; 854 void dumpVerbose() const; 855 856 /// Return the debug location of the start of this loop. 857 /// This looks for a BB terminating instruction with a known debug 858 /// location by looking at the preheader and header blocks. If it 859 /// cannot find a terminating instruction with location information, 860 /// it returns an unknown location. 861 DebugLoc getStartLoc() const; 862 863 /// Return the source code span of the loop. 864 LocRange getLocRange() const; 865 866 StringRef getName() const { 867 if (BasicBlock *Header = getHeader()) 868 if (Header->hasName()) 869 return Header->getName(); 870 return "<unnamed loop>"; 871 } 872 873 private: 874 Loop() = default; 875 876 friend class LoopInfoBase<BasicBlock, Loop>; 877 friend class LoopBase<BasicBlock, Loop>; 878 explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {} 879 ~Loop() = default; 880 }; 881 882 //===----------------------------------------------------------------------===// 883 /// This class builds and contains all of the top-level loop 884 /// structures in the specified function. 885 /// 886 887 template <class BlockT, class LoopT> class LoopInfoBase { 888 // BBMap - Mapping of basic blocks to the inner most loop they occur in 889 DenseMap<const BlockT *, LoopT *> BBMap; 890 std::vector<LoopT *> TopLevelLoops; 891 BumpPtrAllocator LoopAllocator; 892 893 friend class LoopBase<BlockT, LoopT>; 894 friend class LoopInfo; 895 896 void operator=(const LoopInfoBase &) = delete; 897 LoopInfoBase(const LoopInfoBase &) = delete; 898 899 public: 900 LoopInfoBase() {} 901 ~LoopInfoBase() { releaseMemory(); } 902 903 LoopInfoBase(LoopInfoBase &&Arg) 904 : BBMap(std::move(Arg.BBMap)), 905 TopLevelLoops(std::move(Arg.TopLevelLoops)), 906 LoopAllocator(std::move(Arg.LoopAllocator)) { 907 // We have to clear the arguments top level loops as we've taken ownership. 908 Arg.TopLevelLoops.clear(); 909 } 910 LoopInfoBase &operator=(LoopInfoBase &&RHS) { 911 BBMap = std::move(RHS.BBMap); 912 913 for (auto *L : TopLevelLoops) 914 L->~LoopT(); 915 916 TopLevelLoops = std::move(RHS.TopLevelLoops); 917 LoopAllocator = std::move(RHS.LoopAllocator); 918 RHS.TopLevelLoops.clear(); 919 return *this; 920 } 921 922 void releaseMemory() { 923 BBMap.clear(); 924 925 for (auto *L : TopLevelLoops) 926 L->~LoopT(); 927 TopLevelLoops.clear(); 928 LoopAllocator.Reset(); 929 } 930 931 template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) { 932 LoopT *Storage = LoopAllocator.Allocate<LoopT>(); 933 return new (Storage) LoopT(std::forward<ArgsTy>(Args)...); 934 } 935 936 /// iterator/begin/end - The interface to the top-level loops in the current 937 /// function. 938 /// 939 typedef typename std::vector<LoopT *>::const_iterator iterator; 940 typedef 941 typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator; 942 iterator begin() const { return TopLevelLoops.begin(); } 943 iterator end() const { return TopLevelLoops.end(); } 944 reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); } 945 reverse_iterator rend() const { return TopLevelLoops.rend(); } 946 bool empty() const { return TopLevelLoops.empty(); } 947 948 /// Return all of the loops in the function in preorder across the loop 949 /// nests, with siblings in forward program order. 950 /// 951 /// Note that because loops form a forest of trees, preorder is equivalent to 952 /// reverse postorder. 953 SmallVector<LoopT *, 4> getLoopsInPreorder(); 954 955 /// Return all of the loops in the function in preorder across the loop 956 /// nests, with siblings in *reverse* program order. 957 /// 958 /// Note that because loops form a forest of trees, preorder is equivalent to 959 /// reverse postorder. 960 /// 961 /// Also note that this is *not* a reverse preorder. Only the siblings are in 962 /// reverse program order. 963 SmallVector<LoopT *, 4> getLoopsInReverseSiblingPreorder(); 964 965 /// Return the inner most loop that BB lives in. If a basic block is in no 966 /// loop (for example the entry node), null is returned. 967 LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); } 968 969 /// Same as getLoopFor. 970 const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); } 971 972 /// Return the loop nesting level of the specified block. A depth of 0 means 973 /// the block is not inside any loop. 974 unsigned getLoopDepth(const BlockT *BB) const { 975 const LoopT *L = getLoopFor(BB); 976 return L ? L->getLoopDepth() : 0; 977 } 978 979 // True if the block is a loop header node 980 bool isLoopHeader(const BlockT *BB) const { 981 const LoopT *L = getLoopFor(BB); 982 return L && L->getHeader() == BB; 983 } 984 985 /// Return the top-level loops. 986 const std::vector<LoopT *> &getTopLevelLoops() const { return TopLevelLoops; } 987 988 /// Return the top-level loops. 989 std::vector<LoopT *> &getTopLevelLoopsVector() { return TopLevelLoops; } 990 991 /// This removes the specified top-level loop from this loop info object. 992 /// The loop is not deleted, as it will presumably be inserted into 993 /// another loop. 994 LoopT *removeLoop(iterator I) { 995 assert(I != end() && "Cannot remove end iterator!"); 996 LoopT *L = *I; 997 assert(L->isOutermost() && "Not a top-level loop!"); 998 TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin())); 999 return L; 1000 } 1001 1002 /// Change the top-level loop that contains BB to the specified loop. 1003 /// This should be used by transformations that restructure the loop hierarchy 1004 /// tree. 1005 void changeLoopFor(BlockT *BB, LoopT *L) { 1006 if (!L) { 1007 BBMap.erase(BB); 1008 return; 1009 } 1010 BBMap[BB] = L; 1011 } 1012 1013 /// Replace the specified loop in the top-level loops list with the indicated 1014 /// loop. 1015 void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) { 1016 auto I = find(TopLevelLoops, OldLoop); 1017 assert(I != TopLevelLoops.end() && "Old loop not at top level!"); 1018 *I = NewLoop; 1019 assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop && 1020 "Loops already embedded into a subloop!"); 1021 } 1022 1023 /// This adds the specified loop to the collection of top-level loops. 1024 void addTopLevelLoop(LoopT *New) { 1025 assert(New->isOutermost() && "Loop already in subloop!"); 1026 TopLevelLoops.push_back(New); 1027 } 1028 1029 /// This method completely removes BB from all data structures, 1030 /// including all of the Loop objects it is nested in and our mapping from 1031 /// BasicBlocks to loops. 1032 void removeBlock(BlockT *BB) { 1033 auto I = BBMap.find(BB); 1034 if (I != BBMap.end()) { 1035 for (LoopT *L = I->second; L; L = L->getParentLoop()) 1036 L->removeBlockFromLoop(BB); 1037 1038 BBMap.erase(I); 1039 } 1040 } 1041 1042 // Internals 1043 1044 static bool isNotAlreadyContainedIn(const LoopT *SubLoop, 1045 const LoopT *ParentLoop) { 1046 if (!SubLoop) 1047 return true; 1048 if (SubLoop == ParentLoop) 1049 return false; 1050 return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop); 1051 } 1052 1053 /// Create the loop forest using a stable algorithm. 1054 void analyze(const DominatorTreeBase<BlockT, false> &DomTree); 1055 1056 // Debugging 1057 void print(raw_ostream &OS) const; 1058 1059 void verify(const DominatorTreeBase<BlockT, false> &DomTree) const; 1060 1061 /// Destroy a loop that has been removed from the `LoopInfo` nest. 1062 /// 1063 /// This runs the destructor of the loop object making it invalid to 1064 /// reference afterward. The memory is retained so that the *pointer* to the 1065 /// loop remains valid. 1066 /// 1067 /// The caller is responsible for removing this loop from the loop nest and 1068 /// otherwise disconnecting it from the broader `LoopInfo` data structures. 1069 /// Callers that don't naturally handle this themselves should probably call 1070 /// `erase' instead. 1071 void destroy(LoopT *L) { 1072 L->~LoopT(); 1073 1074 // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons 1075 // \c L, but the pointer remains valid for non-dereferencing uses. 1076 LoopAllocator.Deallocate(L); 1077 } 1078 }; 1079 1080 // Implementation in LoopInfoImpl.h 1081 extern template class LoopInfoBase<BasicBlock, Loop>; 1082 1083 class LoopInfo : public LoopInfoBase<BasicBlock, Loop> { 1084 typedef LoopInfoBase<BasicBlock, Loop> BaseT; 1085 1086 friend class LoopBase<BasicBlock, Loop>; 1087 1088 void operator=(const LoopInfo &) = delete; 1089 LoopInfo(const LoopInfo &) = delete; 1090 1091 public: 1092 LoopInfo() {} 1093 explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree); 1094 1095 LoopInfo(LoopInfo &&Arg) : BaseT(std::move(static_cast<BaseT &>(Arg))) {} 1096 LoopInfo &operator=(LoopInfo &&RHS) { 1097 BaseT::operator=(std::move(static_cast<BaseT &>(RHS))); 1098 return *this; 1099 } 1100 1101 /// Handle invalidation explicitly. 1102 bool invalidate(Function &F, const PreservedAnalyses &PA, 1103 FunctionAnalysisManager::Invalidator &); 1104 1105 // Most of the public interface is provided via LoopInfoBase. 1106 1107 /// Update LoopInfo after removing the last backedge from a loop. This updates 1108 /// the loop forest and parent loops for each block so that \c L is no longer 1109 /// referenced, but does not actually delete \c L immediately. The pointer 1110 /// will remain valid until this LoopInfo's memory is released. 1111 void erase(Loop *L); 1112 1113 /// Returns true if replacing From with To everywhere is guaranteed to 1114 /// preserve LCSSA form. 1115 bool replacementPreservesLCSSAForm(Instruction *From, Value *To) { 1116 // Preserving LCSSA form is only problematic if the replacing value is an 1117 // instruction. 1118 Instruction *I = dyn_cast<Instruction>(To); 1119 if (!I) 1120 return true; 1121 // If both instructions are defined in the same basic block then replacement 1122 // cannot break LCSSA form. 1123 if (I->getParent() == From->getParent()) 1124 return true; 1125 // If the instruction is not defined in a loop then it can safely replace 1126 // anything. 1127 Loop *ToLoop = getLoopFor(I->getParent()); 1128 if (!ToLoop) 1129 return true; 1130 // If the replacing instruction is defined in the same loop as the original 1131 // instruction, or in a loop that contains it as an inner loop, then using 1132 // it as a replacement will not break LCSSA form. 1133 return ToLoop->contains(getLoopFor(From->getParent())); 1134 } 1135 1136 /// Checks if moving a specific instruction can break LCSSA in any loop. 1137 /// 1138 /// Return true if moving \p Inst to before \p NewLoc will break LCSSA, 1139 /// assuming that the function containing \p Inst and \p NewLoc is currently 1140 /// in LCSSA form. 1141 bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) { 1142 assert(Inst->getFunction() == NewLoc->getFunction() && 1143 "Can't reason about IPO!"); 1144 1145 auto *OldBB = Inst->getParent(); 1146 auto *NewBB = NewLoc->getParent(); 1147 1148 // Movement within the same loop does not break LCSSA (the equality check is 1149 // to avoid doing a hashtable lookup in case of intra-block movement). 1150 if (OldBB == NewBB) 1151 return true; 1152 1153 auto *OldLoop = getLoopFor(OldBB); 1154 auto *NewLoop = getLoopFor(NewBB); 1155 1156 if (OldLoop == NewLoop) 1157 return true; 1158 1159 // Check if Outer contains Inner; with the null loop counting as the 1160 // "outermost" loop. 1161 auto Contains = [](const Loop *Outer, const Loop *Inner) { 1162 return !Outer || Outer->contains(Inner); 1163 }; 1164 1165 // To check that the movement of Inst to before NewLoc does not break LCSSA, 1166 // we need to check two sets of uses for possible LCSSA violations at 1167 // NewLoc: the users of NewInst, and the operands of NewInst. 1168 1169 // If we know we're hoisting Inst out of an inner loop to an outer loop, 1170 // then the uses *of* Inst don't need to be checked. 1171 1172 if (!Contains(NewLoop, OldLoop)) { 1173 for (Use &U : Inst->uses()) { 1174 auto *UI = cast<Instruction>(U.getUser()); 1175 auto *UBB = isa<PHINode>(UI) ? cast<PHINode>(UI)->getIncomingBlock(U) 1176 : UI->getParent(); 1177 if (UBB != NewBB && getLoopFor(UBB) != NewLoop) 1178 return false; 1179 } 1180 } 1181 1182 // If we know we're sinking Inst from an outer loop into an inner loop, then 1183 // the *operands* of Inst don't need to be checked. 1184 1185 if (!Contains(OldLoop, NewLoop)) { 1186 // See below on why we can't handle phi nodes here. 1187 if (isa<PHINode>(Inst)) 1188 return false; 1189 1190 for (Use &U : Inst->operands()) { 1191 auto *DefI = dyn_cast<Instruction>(U.get()); 1192 if (!DefI) 1193 return false; 1194 1195 // This would need adjustment if we allow Inst to be a phi node -- the 1196 // new use block won't simply be NewBB. 1197 1198 auto *DefBlock = DefI->getParent(); 1199 if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop) 1200 return false; 1201 } 1202 } 1203 1204 return true; 1205 } 1206 1207 // Return true if a new use of V added in ExitBB would require an LCSSA PHI 1208 // to be inserted at the begining of the block. Note that V is assumed to 1209 // dominate ExitBB, and ExitBB must be the exit block of some loop. The 1210 // IR is assumed to be in LCSSA form before the planned insertion. 1211 bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V, 1212 const BasicBlock *ExitBB) const; 1213 1214 }; 1215 1216 // Allow clients to walk the list of nested loops... 1217 template <> struct GraphTraits<const Loop *> { 1218 typedef const Loop *NodeRef; 1219 typedef LoopInfo::iterator ChildIteratorType; 1220 1221 static NodeRef getEntryNode(const Loop *L) { return L; } 1222 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 1223 static ChildIteratorType child_end(NodeRef N) { return N->end(); } 1224 }; 1225 1226 template <> struct GraphTraits<Loop *> { 1227 typedef Loop *NodeRef; 1228 typedef LoopInfo::iterator ChildIteratorType; 1229 1230 static NodeRef getEntryNode(Loop *L) { return L; } 1231 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 1232 static ChildIteratorType child_end(NodeRef N) { return N->end(); } 1233 }; 1234 1235 /// Analysis pass that exposes the \c LoopInfo for a function. 1236 class LoopAnalysis : public AnalysisInfoMixin<LoopAnalysis> { 1237 friend AnalysisInfoMixin<LoopAnalysis>; 1238 static AnalysisKey Key; 1239 1240 public: 1241 typedef LoopInfo Result; 1242 1243 LoopInfo run(Function &F, FunctionAnalysisManager &AM); 1244 }; 1245 1246 /// Printer pass for the \c LoopAnalysis results. 1247 class LoopPrinterPass : public PassInfoMixin<LoopPrinterPass> { 1248 raw_ostream &OS; 1249 1250 public: 1251 explicit LoopPrinterPass(raw_ostream &OS) : OS(OS) {} 1252 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 1253 }; 1254 1255 /// Verifier pass for the \c LoopAnalysis results. 1256 struct LoopVerifierPass : public PassInfoMixin<LoopVerifierPass> { 1257 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 1258 }; 1259 1260 /// The legacy pass manager's analysis pass to compute loop information. 1261 class LoopInfoWrapperPass : public FunctionPass { 1262 LoopInfo LI; 1263 1264 public: 1265 static char ID; // Pass identification, replacement for typeid 1266 1267 LoopInfoWrapperPass(); 1268 1269 LoopInfo &getLoopInfo() { return LI; } 1270 const LoopInfo &getLoopInfo() const { return LI; } 1271 1272 /// Calculate the natural loop information for a given function. 1273 bool runOnFunction(Function &F) override; 1274 1275 void verifyAnalysis() const override; 1276 1277 void releaseMemory() override { LI.releaseMemory(); } 1278 1279 void print(raw_ostream &O, const Module *M = nullptr) const override; 1280 1281 void getAnalysisUsage(AnalysisUsage &AU) const override; 1282 }; 1283 1284 /// Function to print a loop's contents as LLVM's text IR assembly. 1285 void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner = ""); 1286 1287 /// Find and return the loop attribute node for the attribute @p Name in 1288 /// @p LoopID. Return nullptr if there is no such attribute. 1289 MDNode *findOptionMDForLoopID(MDNode *LoopID, StringRef Name); 1290 1291 /// Find string metadata for a loop. 1292 /// 1293 /// Returns the MDNode where the first operand is the metadata's name. The 1294 /// following operands are the metadata's values. If no metadata with @p Name is 1295 /// found, return nullptr. 1296 MDNode *findOptionMDForLoop(const Loop *TheLoop, StringRef Name); 1297 1298 Optional<bool> getOptionalBoolLoopAttribute(const Loop *TheLoop, 1299 StringRef Name); 1300 1301 /// Returns true if Name is applied to TheLoop and enabled. 1302 bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name); 1303 1304 /// Find named metadata for a loop with an integer value. 1305 llvm::Optional<int> 1306 getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name); 1307 1308 /// Find string metadata for loop 1309 /// 1310 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an 1311 /// operand or null otherwise. If the string metadata is not found return 1312 /// Optional's not-a-value. 1313 Optional<const MDOperand *> findStringMetadataForLoop(const Loop *TheLoop, 1314 StringRef Name); 1315 1316 /// Look for the loop attribute that requires progress within the loop. 1317 /// Note: Most consumers probably want "isMustProgress" which checks 1318 /// the containing function attribute too. 1319 bool hasMustProgress(const Loop *L); 1320 1321 /// Return true if this loop can be assumed to make progress. (i.e. can't 1322 /// be infinite without side effects without also being undefined) 1323 bool isMustProgress(const Loop *L); 1324 1325 /// Return whether an MDNode might represent an access group. 1326 /// 1327 /// Access group metadata nodes have to be distinct and empty. Being 1328 /// always-empty ensures that it never needs to be changed (which -- because 1329 /// MDNodes are designed immutable -- would require creating a new MDNode). Note 1330 /// that this is not a sufficient condition: not every distinct and empty NDNode 1331 /// is representing an access group. 1332 bool isValidAsAccessGroup(MDNode *AccGroup); 1333 1334 /// Create a new LoopID after the loop has been transformed. 1335 /// 1336 /// This can be used when no follow-up loop attributes are defined 1337 /// (llvm::makeFollowupLoopID returning None) to stop transformations to be 1338 /// applied again. 1339 /// 1340 /// @param Context The LLVMContext in which to create the new LoopID. 1341 /// @param OrigLoopID The original LoopID; can be nullptr if the original 1342 /// loop has no LoopID. 1343 /// @param RemovePrefixes Remove all loop attributes that have these prefixes. 1344 /// Use to remove metadata of the transformation that has 1345 /// been applied. 1346 /// @param AddAttrs Add these loop attributes to the new LoopID. 1347 /// 1348 /// @return A new LoopID that can be applied using Loop::setLoopID(). 1349 llvm::MDNode * 1350 makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID, 1351 llvm::ArrayRef<llvm::StringRef> RemovePrefixes, 1352 llvm::ArrayRef<llvm::MDNode *> AddAttrs); 1353 1354 } // End llvm namespace 1355 1356 #endif 1357