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