1 //===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the LoopInfo class that is used to identify natural loops 11 // and determine the loop depth of various nodes of the CFG. A natural loop 12 // has exactly one entry-point, which is called the header. Note that natural 13 // loops may actually be several loops that share the same header node. 14 // 15 // This analysis calculates the nesting structure of loops in a function. For 16 // each natural loop identified, this analysis identifies natural loops 17 // contained entirely within the loop and the basic blocks the make up the loop. 18 // 19 // It can calculate on the fly various bits of information, for example: 20 // 21 // * whether there is a preheader for the loop 22 // * the number of back edges to the header 23 // * whether or not a particular block branches out of the loop 24 // * the successor blocks of the loop 25 // * the loop depth 26 // * etc... 27 // 28 // Note that this analysis specifically identifies *Loops* not cycles or SCCs 29 // in the CFG. There can be strongly connected components in the CFG which 30 // this analysis will not recognize and that will not be represented by a Loop 31 // instance. In particular, a Loop might be inside such a non-loop SCC, or a 32 // non-loop SCC might contain a sub-SCC which is a Loop. 33 // 34 //===----------------------------------------------------------------------===// 35 36 #ifndef LLVM_ANALYSIS_LOOPINFO_H 37 #define LLVM_ANALYSIS_LOOPINFO_H 38 39 #include "llvm/ADT/DenseMap.h" 40 #include "llvm/ADT/DenseSet.h" 41 #include "llvm/ADT/GraphTraits.h" 42 #include "llvm/ADT/SmallPtrSet.h" 43 #include "llvm/ADT/SmallVector.h" 44 #include "llvm/IR/CFG.h" 45 #include "llvm/IR/Instruction.h" 46 #include "llvm/IR/Instructions.h" 47 #include "llvm/IR/PassManager.h" 48 #include "llvm/Pass.h" 49 #include "llvm/Support/Allocator.h" 50 #include <algorithm> 51 #include <utility> 52 53 namespace llvm { 54 55 class DominatorTree; 56 class LoopInfo; 57 class Loop; 58 class MDNode; 59 class PHINode; 60 class raw_ostream; 61 template <class N, bool IsPostDom> class DominatorTreeBase; 62 template <class N, class M> class LoopInfoBase; 63 template <class N, class M> class LoopBase; 64 65 //===----------------------------------------------------------------------===// 66 /// Instances of this class are used to represent loops that are detected in the 67 /// flow graph. 68 /// 69 template <class BlockT, class LoopT> class LoopBase { 70 LoopT *ParentLoop; 71 // Loops contained entirely within this one. 72 std::vector<LoopT *> SubLoops; 73 74 // The list of blocks in this loop. First entry is the header node. 75 std::vector<BlockT *> Blocks; 76 77 SmallPtrSet<const BlockT *, 8> DenseBlockSet; 78 79 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 80 /// Indicator that this loop is no longer a valid loop. 81 bool IsInvalid = false; 82 #endif 83 84 LoopBase(const LoopBase<BlockT, LoopT> &) = delete; 85 const LoopBase<BlockT, LoopT> & 86 operator=(const LoopBase<BlockT, LoopT> &) = delete; 87 88 public: 89 /// Return the nesting level of this loop. An outer-most loop has depth 1, 90 /// for consistency with loop depth values used for basic blocks, where depth 91 /// 0 is used for blocks not inside any loops. 92 unsigned getLoopDepth() const { 93 assert(!isInvalid() && "Loop not in a valid state!"); 94 unsigned D = 1; 95 for (const LoopT *CurLoop = ParentLoop; CurLoop; 96 CurLoop = CurLoop->ParentLoop) 97 ++D; 98 return D; 99 } 100 BlockT *getHeader() const { return getBlocks().front(); } 101 LoopT *getParentLoop() const { return ParentLoop; } 102 103 /// This is a raw interface for bypassing addChildLoop. 104 void setParentLoop(LoopT *L) { 105 assert(!isInvalid() && "Loop not in a valid state!"); 106 ParentLoop = L; 107 } 108 109 /// Return true if the specified loop is contained within in this loop. 110 bool contains(const LoopT *L) const { 111 assert(!isInvalid() && "Loop not in a valid state!"); 112 if (L == this) 113 return true; 114 if (!L) 115 return false; 116 return contains(L->getParentLoop()); 117 } 118 119 /// Return true if the specified basic block is in this loop. 120 bool contains(const BlockT *BB) const { 121 assert(!isInvalid() && "Loop not in a valid state!"); 122 return DenseBlockSet.count(BB); 123 } 124 125 /// Return true if the specified instruction is in this loop. 126 template <class InstT> bool contains(const InstT *Inst) const { 127 return contains(Inst->getParent()); 128 } 129 130 /// Return the loops contained entirely within this loop. 131 const std::vector<LoopT *> &getSubLoops() const { 132 assert(!isInvalid() && "Loop not in a valid state!"); 133 return SubLoops; 134 } 135 std::vector<LoopT *> &getSubLoopsVector() { 136 assert(!isInvalid() && "Loop not in a valid state!"); 137 return SubLoops; 138 } 139 typedef typename std::vector<LoopT *>::const_iterator iterator; 140 typedef 141 typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator; 142 iterator begin() const { return getSubLoops().begin(); } 143 iterator end() const { return getSubLoops().end(); } 144 reverse_iterator rbegin() const { return getSubLoops().rbegin(); } 145 reverse_iterator rend() const { return getSubLoops().rend(); } 146 bool empty() const { return getSubLoops().empty(); } 147 148 /// Get a list of the basic blocks which make up this loop. 149 const std::vector<BlockT *> &getBlocks() const { 150 assert(!isInvalid() && "Loop not in a valid state!"); 151 return Blocks; 152 } 153 typedef typename std::vector<BlockT *>::const_iterator block_iterator; 154 block_iterator block_begin() const { return getBlocks().begin(); } 155 block_iterator block_end() const { return getBlocks().end(); } 156 inline iterator_range<block_iterator> blocks() const { 157 assert(!isInvalid() && "Loop not in a valid state!"); 158 return make_range(block_begin(), block_end()); 159 } 160 161 /// Get the number of blocks in this loop in constant time. 162 /// Invalidate the loop, indicating that it is no longer a loop. 163 unsigned getNumBlocks() const { 164 assert(!isInvalid() && "Loop not in a valid state!"); 165 return Blocks.size(); 166 } 167 168 /// Return true if this loop is no longer valid. The only valid use of this 169 /// helper is "assert(L.isInvalid())" or equivalent, since IsInvalid is set to 170 /// true by the destructor. In other words, if this accessor returns true, 171 /// the caller has already triggered UB by calling this accessor; and so it 172 /// can only be called in a context where a return value of true indicates a 173 /// programmer error. 174 bool isInvalid() const { 175 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 176 return IsInvalid; 177 #else 178 return false; 179 #endif 180 } 181 182 /// True if terminator in the block can branch to another block that is 183 /// outside of the current loop. 184 bool isLoopExiting(const BlockT *BB) const { 185 assert(!isInvalid() && "Loop not in a valid state!"); 186 for (const auto &Succ : children<const BlockT *>(BB)) { 187 if (!contains(Succ)) 188 return true; 189 } 190 return false; 191 } 192 193 /// Returns true if \p BB is a loop-latch. 194 /// A latch block is a block that contains a branch back to the header. 195 /// This function is useful when there are multiple latches in a loop 196 /// because \fn getLoopLatch will return nullptr in that case. 197 bool isLoopLatch(const BlockT *BB) const { 198 assert(!isInvalid() && "Loop not in a valid state!"); 199 assert(contains(BB) && "block does not belong to the loop"); 200 201 BlockT *Header = getHeader(); 202 auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header); 203 auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header); 204 return std::find(PredBegin, PredEnd, BB) != PredEnd; 205 } 206 207 /// Calculate the number of back edges to the loop header. 208 unsigned getNumBackEdges() const { 209 assert(!isInvalid() && "Loop not in a valid state!"); 210 unsigned NumBackEdges = 0; 211 BlockT *H = getHeader(); 212 213 for (const auto Pred : children<Inverse<BlockT *>>(H)) 214 if (contains(Pred)) 215 ++NumBackEdges; 216 217 return NumBackEdges; 218 } 219 220 //===--------------------------------------------------------------------===// 221 // APIs for simple analysis of the loop. 222 // 223 // Note that all of these methods can fail on general loops (ie, there may not 224 // be a preheader, etc). For best success, the loop simplification and 225 // induction variable canonicalization pass should be used to normalize loops 226 // for easy analysis. These methods assume canonical loops. 227 228 /// Return all blocks inside the loop that have successors outside of the 229 /// loop. These are the blocks _inside of the current loop_ which branch out. 230 /// The returned list is always unique. 231 void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const; 232 233 /// If getExitingBlocks would return exactly one block, return that block. 234 /// Otherwise return null. 235 BlockT *getExitingBlock() const; 236 237 /// Return all of the successor blocks of this loop. These are the blocks 238 /// _outside of the current loop_ which are branched to. 239 void getExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const; 240 241 /// If getExitBlocks would return exactly one block, return that block. 242 /// Otherwise return null. 243 BlockT *getExitBlock() const; 244 245 /// Edge type. 246 typedef std::pair<const BlockT *, const BlockT *> Edge; 247 248 /// Return all pairs of (_inside_block_,_outside_block_). 249 void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const; 250 251 /// If there is a preheader for this loop, return it. A loop has a preheader 252 /// if there is only one edge to the header of the loop from outside of the 253 /// loop. If this is the case, the block branching to the header of the loop 254 /// is the preheader node. 255 /// 256 /// This method returns null if there is no preheader for the loop. 257 BlockT *getLoopPreheader() const; 258 259 /// If the given loop's header has exactly one unique predecessor outside the 260 /// loop, return it. Otherwise return null. 261 /// This is less strict that the loop "preheader" concept, which requires 262 /// the predecessor to have exactly one successor. 263 BlockT *getLoopPredecessor() const; 264 265 /// If there is a single latch block for this loop, return it. 266 /// A latch block is a block that contains a branch back to the header. 267 BlockT *getLoopLatch() const; 268 269 /// Return all loop latch blocks of this loop. A latch block is a block that 270 /// contains a branch back to the header. 271 void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const { 272 assert(!isInvalid() && "Loop not in a valid state!"); 273 BlockT *H = getHeader(); 274 for (const auto Pred : children<Inverse<BlockT *>>(H)) 275 if (contains(Pred)) 276 LoopLatches.push_back(Pred); 277 } 278 279 //===--------------------------------------------------------------------===// 280 // APIs for updating loop information after changing the CFG 281 // 282 283 /// This method is used by other analyses to update loop information. 284 /// NewBB is set to be a new member of the current loop. 285 /// Because of this, it is added as a member of all parent loops, and is added 286 /// to the specified LoopInfo object as being in the current basic block. It 287 /// is not valid to replace the loop header with this method. 288 void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI); 289 290 /// This is used when splitting loops up. It replaces the OldChild entry in 291 /// our children list with NewChild, and updates the parent pointer of 292 /// OldChild to be null and the NewChild to be this loop. 293 /// This updates the loop depth of the new child. 294 void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild); 295 296 /// Add the specified loop to be a child of this loop. 297 /// This updates the loop depth of the new child. 298 void addChildLoop(LoopT *NewChild) { 299 assert(!isInvalid() && "Loop not in a valid state!"); 300 assert(!NewChild->ParentLoop && "NewChild already has a parent!"); 301 NewChild->ParentLoop = static_cast<LoopT *>(this); 302 SubLoops.push_back(NewChild); 303 } 304 305 /// This removes the specified child from being a subloop of this loop. The 306 /// loop is not deleted, as it will presumably be inserted into another loop. 307 LoopT *removeChildLoop(iterator I) { 308 assert(!isInvalid() && "Loop not in a valid state!"); 309 assert(I != SubLoops.end() && "Cannot remove end iterator!"); 310 LoopT *Child = *I; 311 assert(Child->ParentLoop == this && "Child is not a child of this loop!"); 312 SubLoops.erase(SubLoops.begin() + (I - begin())); 313 Child->ParentLoop = nullptr; 314 return Child; 315 } 316 317 /// This adds a basic block directly to the basic block list. 318 /// This should only be used by transformations that create new loops. Other 319 /// transformations should use addBasicBlockToLoop. 320 void addBlockEntry(BlockT *BB) { 321 assert(!isInvalid() && "Loop not in a valid state!"); 322 Blocks.push_back(BB); 323 DenseBlockSet.insert(BB); 324 } 325 326 /// interface to reverse Blocks[from, end of loop] in this loop 327 void reverseBlock(unsigned from) { 328 assert(!isInvalid() && "Loop not in a valid state!"); 329 std::reverse(Blocks.begin() + from, Blocks.end()); 330 } 331 332 /// interface to do reserve() for Blocks 333 void reserveBlocks(unsigned size) { 334 assert(!isInvalid() && "Loop not in a valid state!"); 335 Blocks.reserve(size); 336 } 337 338 /// This method is used to move BB (which must be part of this loop) to be the 339 /// loop header of the loop (the block that dominates all others). 340 void moveToHeader(BlockT *BB) { 341 assert(!isInvalid() && "Loop not in a valid state!"); 342 if (Blocks[0] == BB) 343 return; 344 for (unsigned i = 0;; ++i) { 345 assert(i != Blocks.size() && "Loop does not contain BB!"); 346 if (Blocks[i] == BB) { 347 Blocks[i] = Blocks[0]; 348 Blocks[0] = BB; 349 return; 350 } 351 } 352 } 353 354 /// This removes the specified basic block from the current loop, updating the 355 /// Blocks as appropriate. This does not update the mapping in the LoopInfo 356 /// class. 357 void removeBlockFromLoop(BlockT *BB) { 358 assert(!isInvalid() && "Loop not in a valid state!"); 359 auto I = find(Blocks, BB); 360 assert(I != Blocks.end() && "N is not in this list!"); 361 Blocks.erase(I); 362 363 DenseBlockSet.erase(BB); 364 } 365 366 /// Verify loop structure 367 void verifyLoop() const; 368 369 /// Verify loop structure of this loop and all nested loops. 370 void verifyLoopNest(DenseSet<const LoopT *> *Loops) const; 371 372 /// Print loop with all the BBs inside it. 373 void print(raw_ostream &OS, unsigned Depth = 0, bool Verbose = false) const; 374 375 protected: 376 friend class LoopInfoBase<BlockT, LoopT>; 377 378 /// This creates an empty loop. 379 LoopBase() : ParentLoop(nullptr) {} 380 381 explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) { 382 Blocks.push_back(BB); 383 DenseBlockSet.insert(BB); 384 } 385 386 // Since loop passes like SCEV are allowed to key analysis results off of 387 // `Loop` pointers, we cannot re-use pointers within a loop pass manager. 388 // This means loop passes should not be `delete` ing `Loop` objects directly 389 // (and risk a later `Loop` allocation re-using the address of a previous one) 390 // but should be using LoopInfo::markAsRemoved, which keeps around the `Loop` 391 // pointer till the end of the lifetime of the `LoopInfo` object. 392 // 393 // To make it easier to follow this rule, we mark the destructor as 394 // non-public. 395 ~LoopBase() { 396 for (auto *SubLoop : SubLoops) 397 SubLoop->~LoopT(); 398 399 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 400 IsInvalid = true; 401 #endif 402 SubLoops.clear(); 403 Blocks.clear(); 404 DenseBlockSet.clear(); 405 ParentLoop = nullptr; 406 } 407 }; 408 409 template <class BlockT, class LoopT> 410 raw_ostream &operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) { 411 Loop.print(OS); 412 return OS; 413 } 414 415 // Implementation in LoopInfoImpl.h 416 extern template class LoopBase<BasicBlock, Loop>; 417 418 /// Represents a single loop in the control flow graph. Note that not all SCCs 419 /// in the CFG are necessarily loops. 420 class Loop : public LoopBase<BasicBlock, Loop> { 421 public: 422 /// \brief A range representing the start and end location of a loop. 423 class LocRange { 424 DebugLoc Start; 425 DebugLoc End; 426 427 public: 428 LocRange() {} 429 LocRange(DebugLoc Start) : Start(std::move(Start)), End(std::move(Start)) {} 430 LocRange(DebugLoc Start, DebugLoc End) 431 : Start(std::move(Start)), End(std::move(End)) {} 432 433 const DebugLoc &getStart() const { return Start; } 434 const DebugLoc &getEnd() const { return End; } 435 436 /// \brief Check for null. 437 /// 438 explicit operator bool() const { return Start && End; } 439 }; 440 441 /// Return true if the specified value is loop invariant. 442 bool isLoopInvariant(const Value *V) const; 443 444 /// Return true if all the operands of the specified instruction are loop 445 /// invariant. 446 bool hasLoopInvariantOperands(const Instruction *I) const; 447 448 /// If the given value is an instruction inside of the loop and it can be 449 /// hoisted, do so to make it trivially loop-invariant. 450 /// Return true if the value after any hoisting is loop invariant. This 451 /// function can be used as a slightly more aggressive replacement for 452 /// isLoopInvariant. 453 /// 454 /// If InsertPt is specified, it is the point to hoist instructions to. 455 /// If null, the terminator of the loop preheader is used. 456 bool makeLoopInvariant(Value *V, bool &Changed, 457 Instruction *InsertPt = nullptr) const; 458 459 /// If the given instruction is inside of the loop and it can be hoisted, do 460 /// so to make it trivially loop-invariant. 461 /// Return true if the instruction after any hoisting is loop invariant. This 462 /// function can be used as a slightly more aggressive replacement for 463 /// isLoopInvariant. 464 /// 465 /// If InsertPt is specified, it is the point to hoist instructions to. 466 /// If null, the terminator of the loop preheader is used. 467 /// 468 bool makeLoopInvariant(Instruction *I, bool &Changed, 469 Instruction *InsertPt = nullptr) const; 470 471 /// Check to see if the loop has a canonical induction variable: an integer 472 /// recurrence that starts at 0 and increments by one each time through the 473 /// loop. If so, return the phi node that corresponds to it. 474 /// 475 /// The IndVarSimplify pass transforms loops to have a canonical induction 476 /// variable. 477 /// 478 PHINode *getCanonicalInductionVariable() const; 479 480 /// Return true if the Loop is in LCSSA form. 481 bool isLCSSAForm(DominatorTree &DT) const; 482 483 /// Return true if this Loop and all inner subloops are in LCSSA form. 484 bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const; 485 486 /// Return true if the Loop is in the form that the LoopSimplify form 487 /// transforms loops to, which is sometimes called normal form. 488 bool isLoopSimplifyForm() const; 489 490 /// Return true if the loop body is safe to clone in practice. 491 bool isSafeToClone() const; 492 493 /// Returns true if the loop is annotated parallel. 494 /// 495 /// A parallel loop can be assumed to not contain any dependencies between 496 /// iterations by the compiler. That is, any loop-carried dependency checking 497 /// can be skipped completely when parallelizing the loop on the target 498 /// machine. Thus, if the parallel loop information originates from the 499 /// programmer, e.g. via the OpenMP parallel for pragma, it is the 500 /// programmer's responsibility to ensure there are no loop-carried 501 /// dependencies. The final execution order of the instructions across 502 /// iterations is not guaranteed, thus, the end result might or might not 503 /// implement actual concurrent execution of instructions across multiple 504 /// iterations. 505 bool isAnnotatedParallel() const; 506 507 /// Return the llvm.loop loop id metadata node for this loop if it is present. 508 /// 509 /// If this loop contains the same llvm.loop metadata on each branch to the 510 /// header then the node is returned. If any latch instruction does not 511 /// contain llvm.loop or or if multiple latches contain different nodes then 512 /// 0 is returned. 513 MDNode *getLoopID() const; 514 /// Set the llvm.loop loop id metadata for this loop. 515 /// 516 /// The LoopID metadata node will be added to each terminator instruction in 517 /// the loop that branches to the loop header. 518 /// 519 /// The LoopID metadata node should have one or more operands and the first 520 /// operand should be the node itself. 521 void setLoopID(MDNode *LoopID) const; 522 523 /// Add llvm.loop.unroll.disable to this loop's loop id metadata. 524 /// 525 /// Remove existing unroll metadata and add unroll disable metadata to 526 /// indicate the loop has already been unrolled. This prevents a loop 527 /// from being unrolled more than is directed by a pragma if the loop 528 /// unrolling pass is run more than once (which it generally is). 529 void setLoopAlreadyUnrolled(); 530 531 /// Return true if no exit block for the loop has a predecessor that is 532 /// outside the loop. 533 bool hasDedicatedExits() const; 534 535 /// Return all unique successor blocks of this loop. 536 /// These are the blocks _outside of the current loop_ which are branched to. 537 /// This assumes that loop exits are in canonical form, i.e. all exits are 538 /// dedicated exits. 539 void getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const; 540 541 /// If getUniqueExitBlocks would return exactly one block, return that block. 542 /// Otherwise return null. 543 BasicBlock *getUniqueExitBlock() const; 544 545 void dump() const; 546 void dumpVerbose() const; 547 548 /// Return the debug location of the start of this loop. 549 /// This looks for a BB terminating instruction with a known debug 550 /// location by looking at the preheader and header blocks. If it 551 /// cannot find a terminating instruction with location information, 552 /// it returns an unknown location. 553 DebugLoc getStartLoc() const; 554 555 /// Return the source code span of the loop. 556 LocRange getLocRange() const; 557 558 StringRef getName() const { 559 if (BasicBlock *Header = getHeader()) 560 if (Header->hasName()) 561 return Header->getName(); 562 return "<unnamed loop>"; 563 } 564 565 private: 566 Loop() = default; 567 568 friend class LoopInfoBase<BasicBlock, Loop>; 569 friend class LoopBase<BasicBlock, Loop>; 570 explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {} 571 ~Loop() = default; 572 }; 573 574 //===----------------------------------------------------------------------===// 575 /// This class builds and contains all of the top-level loop 576 /// structures in the specified function. 577 /// 578 579 template <class BlockT, class LoopT> class LoopInfoBase { 580 // BBMap - Mapping of basic blocks to the inner most loop they occur in 581 DenseMap<const BlockT *, LoopT *> BBMap; 582 std::vector<LoopT *> TopLevelLoops; 583 BumpPtrAllocator LoopAllocator; 584 585 friend class LoopBase<BlockT, LoopT>; 586 friend class LoopInfo; 587 588 void operator=(const LoopInfoBase &) = delete; 589 LoopInfoBase(const LoopInfoBase &) = delete; 590 591 public: 592 LoopInfoBase() {} 593 ~LoopInfoBase() { releaseMemory(); } 594 595 LoopInfoBase(LoopInfoBase &&Arg) 596 : BBMap(std::move(Arg.BBMap)), 597 TopLevelLoops(std::move(Arg.TopLevelLoops)), 598 LoopAllocator(std::move(Arg.LoopAllocator)) { 599 // We have to clear the arguments top level loops as we've taken ownership. 600 Arg.TopLevelLoops.clear(); 601 } 602 LoopInfoBase &operator=(LoopInfoBase &&RHS) { 603 BBMap = std::move(RHS.BBMap); 604 605 for (auto *L : TopLevelLoops) 606 L->~LoopT(); 607 608 TopLevelLoops = std::move(RHS.TopLevelLoops); 609 LoopAllocator = std::move(RHS.LoopAllocator); 610 RHS.TopLevelLoops.clear(); 611 return *this; 612 } 613 614 void releaseMemory() { 615 BBMap.clear(); 616 617 for (auto *L : TopLevelLoops) 618 L->~LoopT(); 619 TopLevelLoops.clear(); 620 LoopAllocator.Reset(); 621 } 622 623 template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) { 624 LoopT *Storage = LoopAllocator.Allocate<LoopT>(); 625 return new (Storage) LoopT(std::forward<ArgsTy>(Args)...); 626 } 627 628 /// iterator/begin/end - The interface to the top-level loops in the current 629 /// function. 630 /// 631 typedef typename std::vector<LoopT *>::const_iterator iterator; 632 typedef 633 typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator; 634 iterator begin() const { return TopLevelLoops.begin(); } 635 iterator end() const { return TopLevelLoops.end(); } 636 reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); } 637 reverse_iterator rend() const { return TopLevelLoops.rend(); } 638 bool empty() const { return TopLevelLoops.empty(); } 639 640 /// Return all of the loops in the function in preorder across the loop 641 /// nests, with siblings in forward program order. 642 /// 643 /// Note that because loops form a forest of trees, preorder is equivalent to 644 /// reverse postorder. 645 SmallVector<LoopT *, 4> getLoopsInPreorder(); 646 647 /// Return all of the loops in the function in preorder across the loop 648 /// nests, with siblings in *reverse* program order. 649 /// 650 /// Note that because loops form a forest of trees, preorder is equivalent to 651 /// reverse postorder. 652 /// 653 /// Also note that this is *not* a reverse preorder. Only the siblings are in 654 /// reverse program order. 655 SmallVector<LoopT *, 4> getLoopsInReverseSiblingPreorder(); 656 657 /// Return the inner most loop that BB lives in. If a basic block is in no 658 /// loop (for example the entry node), null is returned. 659 LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); } 660 661 /// Same as getLoopFor. 662 const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); } 663 664 /// Return the loop nesting level of the specified block. A depth of 0 means 665 /// the block is not inside any loop. 666 unsigned getLoopDepth(const BlockT *BB) const { 667 const LoopT *L = getLoopFor(BB); 668 return L ? L->getLoopDepth() : 0; 669 } 670 671 // True if the block is a loop header node 672 bool isLoopHeader(const BlockT *BB) const { 673 const LoopT *L = getLoopFor(BB); 674 return L && L->getHeader() == BB; 675 } 676 677 /// This removes the specified top-level loop from this loop info object. 678 /// The loop is not deleted, as it will presumably be inserted into 679 /// another loop. 680 LoopT *removeLoop(iterator I) { 681 assert(I != end() && "Cannot remove end iterator!"); 682 LoopT *L = *I; 683 assert(!L->getParentLoop() && "Not a top-level loop!"); 684 TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin())); 685 return L; 686 } 687 688 /// Change the top-level loop that contains BB to the specified loop. 689 /// This should be used by transformations that restructure the loop hierarchy 690 /// tree. 691 void changeLoopFor(BlockT *BB, LoopT *L) { 692 if (!L) { 693 BBMap.erase(BB); 694 return; 695 } 696 BBMap[BB] = L; 697 } 698 699 /// Replace the specified loop in the top-level loops list with the indicated 700 /// loop. 701 void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) { 702 auto I = find(TopLevelLoops, OldLoop); 703 assert(I != TopLevelLoops.end() && "Old loop not at top level!"); 704 *I = NewLoop; 705 assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop && 706 "Loops already embedded into a subloop!"); 707 } 708 709 /// This adds the specified loop to the collection of top-level loops. 710 void addTopLevelLoop(LoopT *New) { 711 assert(!New->getParentLoop() && "Loop already in subloop!"); 712 TopLevelLoops.push_back(New); 713 } 714 715 /// This method completely removes BB from all data structures, 716 /// including all of the Loop objects it is nested in and our mapping from 717 /// BasicBlocks to loops. 718 void removeBlock(BlockT *BB) { 719 auto I = BBMap.find(BB); 720 if (I != BBMap.end()) { 721 for (LoopT *L = I->second; L; L = L->getParentLoop()) 722 L->removeBlockFromLoop(BB); 723 724 BBMap.erase(I); 725 } 726 } 727 728 // Internals 729 730 static bool isNotAlreadyContainedIn(const LoopT *SubLoop, 731 const LoopT *ParentLoop) { 732 if (!SubLoop) 733 return true; 734 if (SubLoop == ParentLoop) 735 return false; 736 return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop); 737 } 738 739 /// Create the loop forest using a stable algorithm. 740 void analyze(const DominatorTreeBase<BlockT, false> &DomTree); 741 742 // Debugging 743 void print(raw_ostream &OS) const; 744 745 void verify(const DominatorTreeBase<BlockT, false> &DomTree) const; 746 747 protected: 748 // Calls the destructor for \p L but keeps the memory for \p L around so that 749 // the pointer value does not get re-used. 750 void destroy(LoopT *L) { 751 L->~LoopT(); 752 753 // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons 754 // \c L, but the pointer remains valid for non-dereferencing uses. 755 LoopAllocator.Deallocate(L); 756 } 757 }; 758 759 // Implementation in LoopInfoImpl.h 760 extern template class LoopInfoBase<BasicBlock, Loop>; 761 762 class LoopInfo : public LoopInfoBase<BasicBlock, Loop> { 763 typedef LoopInfoBase<BasicBlock, Loop> BaseT; 764 765 friend class LoopBase<BasicBlock, Loop>; 766 767 void operator=(const LoopInfo &) = delete; 768 LoopInfo(const LoopInfo &) = delete; 769 770 public: 771 LoopInfo() {} 772 explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree); 773 774 LoopInfo(LoopInfo &&Arg) : BaseT(std::move(static_cast<BaseT &>(Arg))) {} 775 LoopInfo &operator=(LoopInfo &&RHS) { 776 BaseT::operator=(std::move(static_cast<BaseT &>(RHS))); 777 return *this; 778 } 779 780 /// Handle invalidation explicitly. 781 bool invalidate(Function &F, const PreservedAnalyses &PA, 782 FunctionAnalysisManager::Invalidator &); 783 784 // Most of the public interface is provided via LoopInfoBase. 785 786 /// Update LoopInfo after removing the last backedge from a loop. This updates 787 /// the loop forest and parent loops for each block so that \c L is no longer 788 /// referenced, but does not actually delete \c L immediately. The pointer 789 /// will remain valid until this LoopInfo's memory is released. 790 void erase(Loop *L); 791 792 /// Returns true if replacing From with To everywhere is guaranteed to 793 /// preserve LCSSA form. 794 bool replacementPreservesLCSSAForm(Instruction *From, Value *To) { 795 // Preserving LCSSA form is only problematic if the replacing value is an 796 // instruction. 797 Instruction *I = dyn_cast<Instruction>(To); 798 if (!I) 799 return true; 800 // If both instructions are defined in the same basic block then replacement 801 // cannot break LCSSA form. 802 if (I->getParent() == From->getParent()) 803 return true; 804 // If the instruction is not defined in a loop then it can safely replace 805 // anything. 806 Loop *ToLoop = getLoopFor(I->getParent()); 807 if (!ToLoop) 808 return true; 809 // If the replacing instruction is defined in the same loop as the original 810 // instruction, or in a loop that contains it as an inner loop, then using 811 // it as a replacement will not break LCSSA form. 812 return ToLoop->contains(getLoopFor(From->getParent())); 813 } 814 815 /// Checks if moving a specific instruction can break LCSSA in any loop. 816 /// 817 /// Return true if moving \p Inst to before \p NewLoc will break LCSSA, 818 /// assuming that the function containing \p Inst and \p NewLoc is currently 819 /// in LCSSA form. 820 bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) { 821 assert(Inst->getFunction() == NewLoc->getFunction() && 822 "Can't reason about IPO!"); 823 824 auto *OldBB = Inst->getParent(); 825 auto *NewBB = NewLoc->getParent(); 826 827 // Movement within the same loop does not break LCSSA (the equality check is 828 // to avoid doing a hashtable lookup in case of intra-block movement). 829 if (OldBB == NewBB) 830 return true; 831 832 auto *OldLoop = getLoopFor(OldBB); 833 auto *NewLoop = getLoopFor(NewBB); 834 835 if (OldLoop == NewLoop) 836 return true; 837 838 // Check if Outer contains Inner; with the null loop counting as the 839 // "outermost" loop. 840 auto Contains = [](const Loop *Outer, const Loop *Inner) { 841 return !Outer || Outer->contains(Inner); 842 }; 843 844 // To check that the movement of Inst to before NewLoc does not break LCSSA, 845 // we need to check two sets of uses for possible LCSSA violations at 846 // NewLoc: the users of NewInst, and the operands of NewInst. 847 848 // If we know we're hoisting Inst out of an inner loop to an outer loop, 849 // then the uses *of* Inst don't need to be checked. 850 851 if (!Contains(NewLoop, OldLoop)) { 852 for (Use &U : Inst->uses()) { 853 auto *UI = cast<Instruction>(U.getUser()); 854 auto *UBB = isa<PHINode>(UI) ? cast<PHINode>(UI)->getIncomingBlock(U) 855 : UI->getParent(); 856 if (UBB != NewBB && getLoopFor(UBB) != NewLoop) 857 return false; 858 } 859 } 860 861 // If we know we're sinking Inst from an outer loop into an inner loop, then 862 // the *operands* of Inst don't need to be checked. 863 864 if (!Contains(OldLoop, NewLoop)) { 865 // See below on why we can't handle phi nodes here. 866 if (isa<PHINode>(Inst)) 867 return false; 868 869 for (Use &U : Inst->operands()) { 870 auto *DefI = dyn_cast<Instruction>(U.get()); 871 if (!DefI) 872 return false; 873 874 // This would need adjustment if we allow Inst to be a phi node -- the 875 // new use block won't simply be NewBB. 876 877 auto *DefBlock = DefI->getParent(); 878 if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop) 879 return false; 880 } 881 } 882 883 return true; 884 } 885 }; 886 887 // Allow clients to walk the list of nested loops... 888 template <> struct GraphTraits<const Loop *> { 889 typedef const Loop *NodeRef; 890 typedef LoopInfo::iterator ChildIteratorType; 891 892 static NodeRef getEntryNode(const Loop *L) { return L; } 893 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 894 static ChildIteratorType child_end(NodeRef N) { return N->end(); } 895 }; 896 897 template <> struct GraphTraits<Loop *> { 898 typedef Loop *NodeRef; 899 typedef LoopInfo::iterator ChildIteratorType; 900 901 static NodeRef getEntryNode(Loop *L) { return L; } 902 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 903 static ChildIteratorType child_end(NodeRef N) { return N->end(); } 904 }; 905 906 /// \brief Analysis pass that exposes the \c LoopInfo for a function. 907 class LoopAnalysis : public AnalysisInfoMixin<LoopAnalysis> { 908 friend AnalysisInfoMixin<LoopAnalysis>; 909 static AnalysisKey Key; 910 911 public: 912 typedef LoopInfo Result; 913 914 LoopInfo run(Function &F, FunctionAnalysisManager &AM); 915 }; 916 917 /// \brief Printer pass for the \c LoopAnalysis results. 918 class LoopPrinterPass : public PassInfoMixin<LoopPrinterPass> { 919 raw_ostream &OS; 920 921 public: 922 explicit LoopPrinterPass(raw_ostream &OS) : OS(OS) {} 923 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 924 }; 925 926 /// \brief Verifier pass for the \c LoopAnalysis results. 927 struct LoopVerifierPass : public PassInfoMixin<LoopVerifierPass> { 928 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 929 }; 930 931 /// \brief The legacy pass manager's analysis pass to compute loop information. 932 class LoopInfoWrapperPass : public FunctionPass { 933 LoopInfo LI; 934 935 public: 936 static char ID; // Pass identification, replacement for typeid 937 938 LoopInfoWrapperPass() : FunctionPass(ID) { 939 initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry()); 940 } 941 942 LoopInfo &getLoopInfo() { return LI; } 943 const LoopInfo &getLoopInfo() const { return LI; } 944 945 /// \brief Calculate the natural loop information for a given function. 946 bool runOnFunction(Function &F) override; 947 948 void verifyAnalysis() const override; 949 950 void releaseMemory() override { LI.releaseMemory(); } 951 952 void print(raw_ostream &O, const Module *M = nullptr) const override; 953 954 void getAnalysisUsage(AnalysisUsage &AU) const override; 955 }; 956 957 /// Function to print a loop's contents as LLVM's text IR assembly. 958 void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner = ""); 959 960 } // End llvm namespace 961 962 #endif 963