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