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 declares a GenericLoopInfo instantiation for LLVM IR. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_ANALYSIS_LOOPINFO_H 14 #define LLVM_ANALYSIS_LOOPINFO_H 15 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/DenseSet.h" 18 #include "llvm/ADT/GraphTraits.h" 19 #include "llvm/ADT/SmallPtrSet.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/IR/CFG.h" 22 #include "llvm/IR/Instructions.h" 23 #include "llvm/IR/PassManager.h" 24 #include "llvm/Pass.h" 25 #include "llvm/Support/GenericLoopInfo.h" 26 #include <algorithm> 27 #include <optional> 28 #include <utility> 29 30 namespace llvm { 31 32 class DominatorTree; 33 class InductionDescriptor; 34 class Instruction; 35 class LoopInfo; 36 class Loop; 37 class MDNode; 38 class MemorySSAUpdater; 39 class ScalarEvolution; 40 class raw_ostream; 41 42 // Implementation in Support/GenericLoopInfoImpl.h 43 extern template class LoopBase<BasicBlock, Loop>; 44 45 /// Represents a single loop in the control flow graph. Note that not all SCCs 46 /// in the CFG are necessarily loops. 47 class LLVM_EXTERNAL_VISIBILITY Loop : public LoopBase<BasicBlock, Loop> { 48 public: 49 /// A range representing the start and end location of a loop. 50 class LocRange { 51 DebugLoc Start; 52 DebugLoc End; 53 54 public: 55 LocRange() = default; 56 LocRange(DebugLoc Start) : Start(Start), End(Start) {} 57 LocRange(DebugLoc Start, DebugLoc End) 58 : Start(std::move(Start)), End(std::move(End)) {} 59 60 const DebugLoc &getStart() const { return Start; } 61 const DebugLoc &getEnd() const { return End; } 62 63 /// Check for null. 64 /// 65 explicit operator bool() const { return Start && End; } 66 }; 67 68 /// Return true if the specified value is loop invariant. 69 bool isLoopInvariant(const Value *V) const; 70 71 /// Return true if all the operands of the specified instruction are loop 72 /// invariant. 73 bool hasLoopInvariantOperands(const Instruction *I) const; 74 75 /// If the given value is an instruction inside of the loop and it can be 76 /// hoisted, do so to make it trivially loop-invariant. 77 /// Return true if \c V is already loop-invariant, and false if \c V can't 78 /// be made loop-invariant. If \c V is made loop-invariant, \c Changed is 79 /// set to true. This function can be used as a slightly more aggressive 80 /// replacement for isLoopInvariant. 81 /// 82 /// If InsertPt is specified, it is the point to hoist instructions to. 83 /// If null, the terminator of the loop preheader is used. 84 /// 85 bool makeLoopInvariant(Value *V, bool &Changed, 86 Instruction *InsertPt = nullptr, 87 MemorySSAUpdater *MSSAU = nullptr, 88 ScalarEvolution *SE = nullptr) const; 89 90 /// If the given instruction is inside of the loop and it can be hoisted, do 91 /// so to make it trivially loop-invariant. 92 /// Return true if \c I is already loop-invariant, and false if \c I can't 93 /// be made loop-invariant. If \c I is made loop-invariant, \c Changed is 94 /// set to true. This function can be used as a slightly more aggressive 95 /// replacement for isLoopInvariant. 96 /// 97 /// If InsertPt is specified, it is the point to hoist instructions to. 98 /// If null, the terminator of the loop preheader is used. 99 /// 100 bool makeLoopInvariant(Instruction *I, bool &Changed, 101 Instruction *InsertPt = nullptr, 102 MemorySSAUpdater *MSSAU = nullptr, 103 ScalarEvolution *SE = nullptr) const; 104 105 /// Check to see if the loop has a canonical induction variable: an integer 106 /// recurrence that starts at 0 and increments by one each time through the 107 /// loop. If so, return the phi node that corresponds to it. 108 /// 109 /// The IndVarSimplify pass transforms loops to have a canonical induction 110 /// variable. 111 /// 112 PHINode *getCanonicalInductionVariable() const; 113 114 /// Get the latch condition instruction. 115 ICmpInst *getLatchCmpInst() const; 116 117 /// Obtain the unique incoming and back edge. Return false if they are 118 /// non-unique or the loop is dead; otherwise, return true. 119 bool getIncomingAndBackEdge(BasicBlock *&Incoming, 120 BasicBlock *&Backedge) const; 121 122 /// Below are some utilities to get the loop guard, loop bounds and induction 123 /// variable, and to check if a given phinode is an auxiliary induction 124 /// variable, if the loop is guarded, and if the loop is canonical. 125 /// 126 /// Here is an example: 127 /// \code 128 /// for (int i = lb; i < ub; i+=step) 129 /// <loop body> 130 /// --- pseudo LLVMIR --- 131 /// beforeloop: 132 /// guardcmp = (lb < ub) 133 /// if (guardcmp) goto preheader; else goto afterloop 134 /// preheader: 135 /// loop: 136 /// i_1 = phi[{lb, preheader}, {i_2, latch}] 137 /// <loop body> 138 /// i_2 = i_1 + step 139 /// latch: 140 /// cmp = (i_2 < ub) 141 /// if (cmp) goto loop 142 /// exit: 143 /// afterloop: 144 /// \endcode 145 /// 146 /// - getBounds 147 /// - getInitialIVValue --> lb 148 /// - getStepInst --> i_2 = i_1 + step 149 /// - getStepValue --> step 150 /// - getFinalIVValue --> ub 151 /// - getCanonicalPredicate --> '<' 152 /// - getDirection --> Increasing 153 /// 154 /// - getInductionVariable --> i_1 155 /// - isAuxiliaryInductionVariable(x) --> true if x == i_1 156 /// - getLoopGuardBranch() 157 /// --> `if (guardcmp) goto preheader; else goto afterloop` 158 /// - isGuarded() --> true 159 /// - isCanonical --> false 160 struct LoopBounds { 161 /// Return the LoopBounds object if 162 /// - the given \p IndVar is an induction variable 163 /// - the initial value of the induction variable can be found 164 /// - the step instruction of the induction variable can be found 165 /// - the final value of the induction variable can be found 166 /// 167 /// Else std::nullopt. 168 static std::optional<Loop::LoopBounds> 169 getBounds(const Loop &L, PHINode &IndVar, ScalarEvolution &SE); 170 171 /// Get the initial value of the loop induction variable. 172 Value &getInitialIVValue() const { return InitialIVValue; } 173 174 /// Get the instruction that updates the loop induction variable. 175 Instruction &getStepInst() const { return StepInst; } 176 177 /// Get the step that the loop induction variable gets updated by in each 178 /// loop iteration. Return nullptr if not found. 179 Value *getStepValue() const { return StepValue; } 180 181 /// Get the final value of the loop induction variable. 182 Value &getFinalIVValue() const { return FinalIVValue; } 183 184 /// Return the canonical predicate for the latch compare instruction, if 185 /// able to be calcuated. Else BAD_ICMP_PREDICATE. 186 /// 187 /// A predicate is considered as canonical if requirements below are all 188 /// satisfied: 189 /// 1. The first successor of the latch branch is the loop header 190 /// If not, inverse the predicate. 191 /// 2. One of the operands of the latch comparison is StepInst 192 /// If not, and 193 /// - if the current calcuated predicate is not ne or eq, flip the 194 /// predicate. 195 /// - else if the loop is increasing, return slt 196 /// (notice that it is safe to change from ne or eq to sign compare) 197 /// - else if the loop is decreasing, return sgt 198 /// (notice that it is safe to change from ne or eq to sign compare) 199 /// 200 /// Here is an example when both (1) and (2) are not satisfied: 201 /// \code 202 /// loop.header: 203 /// %iv = phi [%initialiv, %loop.preheader], [%inc, %loop.header] 204 /// %inc = add %iv, %step 205 /// %cmp = slt %iv, %finaliv 206 /// br %cmp, %loop.exit, %loop.header 207 /// loop.exit: 208 /// \endcode 209 /// - The second successor of the latch branch is the loop header instead 210 /// of the first successor (slt -> sge) 211 /// - The first operand of the latch comparison (%cmp) is the IndVar (%iv) 212 /// instead of the StepInst (%inc) (sge -> sgt) 213 /// 214 /// The predicate would be sgt if both (1) and (2) are satisfied. 215 /// getCanonicalPredicate() returns sgt for this example. 216 /// Note: The IR is not changed. 217 ICmpInst::Predicate getCanonicalPredicate() const; 218 219 /// An enum for the direction of the loop 220 /// - for (int i = 0; i < ub; ++i) --> Increasing 221 /// - for (int i = ub; i > 0; --i) --> Descresing 222 /// - for (int i = x; i != y; i+=z) --> Unknown 223 enum class Direction { Increasing, Decreasing, Unknown }; 224 225 /// Get the direction of the loop. 226 Direction getDirection() const; 227 228 private: 229 LoopBounds(const Loop &Loop, Value &I, Instruction &SI, Value *SV, Value &F, 230 ScalarEvolution &SE) 231 : L(Loop), InitialIVValue(I), StepInst(SI), StepValue(SV), 232 FinalIVValue(F), SE(SE) {} 233 234 const Loop &L; 235 236 // The initial value of the loop induction variable 237 Value &InitialIVValue; 238 239 // The instruction that updates the loop induction variable 240 Instruction &StepInst; 241 242 // The value that the loop induction variable gets updated by in each loop 243 // iteration 244 Value *StepValue; 245 246 // The final value of the loop induction variable 247 Value &FinalIVValue; 248 249 ScalarEvolution &SE; 250 }; 251 252 /// Return the struct LoopBounds collected if all struct members are found, 253 /// else std::nullopt. 254 std::optional<LoopBounds> getBounds(ScalarEvolution &SE) const; 255 256 /// Return the loop induction variable if found, else return nullptr. 257 /// An instruction is considered as the loop induction variable if 258 /// - it is an induction variable of the loop; and 259 /// - it is used to determine the condition of the branch in the loop latch 260 /// 261 /// Note: the induction variable doesn't need to be canonical, i.e. starts at 262 /// zero and increments by one each time through the loop (but it can be). 263 PHINode *getInductionVariable(ScalarEvolution &SE) const; 264 265 /// Get the loop induction descriptor for the loop induction variable. Return 266 /// true if the loop induction variable is found. 267 bool getInductionDescriptor(ScalarEvolution &SE, 268 InductionDescriptor &IndDesc) const; 269 270 /// Return true if the given PHINode \p AuxIndVar is 271 /// - in the loop header 272 /// - not used outside of the loop 273 /// - incremented by a loop invariant step for each loop iteration 274 /// - step instruction opcode should be add or sub 275 /// Note: auxiliary induction variable is not required to be used in the 276 /// conditional branch in the loop latch. (but it can be) 277 bool isAuxiliaryInductionVariable(PHINode &AuxIndVar, 278 ScalarEvolution &SE) const; 279 280 /// Return the loop guard branch, if it exists. 281 /// 282 /// This currently only works on simplified loop, as it requires a preheader 283 /// and a latch to identify the guard. It will work on loops of the form: 284 /// \code 285 /// GuardBB: 286 /// br cond1, Preheader, ExitSucc <== GuardBranch 287 /// Preheader: 288 /// br Header 289 /// Header: 290 /// ... 291 /// br Latch 292 /// Latch: 293 /// br cond2, Header, ExitBlock 294 /// ExitBlock: 295 /// br ExitSucc 296 /// ExitSucc: 297 /// \endcode 298 BranchInst *getLoopGuardBranch() const; 299 300 /// Return true iff the loop is 301 /// - in simplify rotated form, and 302 /// - guarded by a loop guard branch. 303 bool isGuarded() const { return (getLoopGuardBranch() != nullptr); } 304 305 /// Return true if the loop is in rotated form. 306 /// 307 /// This does not check if the loop was rotated by loop rotation, instead it 308 /// only checks if the loop is in rotated form (has a valid latch that exists 309 /// the loop). 310 bool isRotatedForm() const { 311 assert(!isInvalid() && "Loop not in a valid state!"); 312 BasicBlock *Latch = getLoopLatch(); 313 return Latch && isLoopExiting(Latch); 314 } 315 316 /// Return true if the loop induction variable starts at zero and increments 317 /// by one each time through the loop. 318 bool isCanonical(ScalarEvolution &SE) const; 319 320 /// Return true if the Loop is in LCSSA form. If \p IgnoreTokens is set to 321 /// true, token values defined inside loop are allowed to violate LCSSA form. 322 bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens = true) const; 323 324 /// Return true if this Loop and all inner subloops are in LCSSA form. If \p 325 /// IgnoreTokens is set to true, token values defined inside loop are allowed 326 /// to violate LCSSA form. 327 bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI, 328 bool IgnoreTokens = true) const; 329 330 /// Return true if the Loop is in the form that the LoopSimplify form 331 /// transforms loops to, which is sometimes called normal form. 332 bool isLoopSimplifyForm() const; 333 334 /// Return true if the loop body is safe to clone in practice. 335 bool isSafeToClone() const; 336 337 /// Returns true if the loop is annotated parallel. 338 /// 339 /// A parallel loop can be assumed to not contain any dependencies between 340 /// iterations by the compiler. That is, any loop-carried dependency checking 341 /// can be skipped completely when parallelizing the loop on the target 342 /// machine. Thus, if the parallel loop information originates from the 343 /// programmer, e.g. via the OpenMP parallel for pragma, it is the 344 /// programmer's responsibility to ensure there are no loop-carried 345 /// dependencies. The final execution order of the instructions across 346 /// iterations is not guaranteed, thus, the end result might or might not 347 /// implement actual concurrent execution of instructions across multiple 348 /// iterations. 349 bool isAnnotatedParallel() const; 350 351 /// Return the llvm.loop loop id metadata node for this loop if it is present. 352 /// 353 /// If this loop contains the same llvm.loop metadata on each branch to the 354 /// header then the node is returned. If any latch instruction does not 355 /// contain llvm.loop or if multiple latches contain different nodes then 356 /// 0 is returned. 357 MDNode *getLoopID() const; 358 /// Set the llvm.loop loop id metadata for this loop. 359 /// 360 /// The LoopID metadata node will be added to each terminator instruction in 361 /// the loop that branches to the loop header. 362 /// 363 /// The LoopID metadata node should have one or more operands and the first 364 /// operand should be the node itself. 365 void setLoopID(MDNode *LoopID) const; 366 367 /// Add llvm.loop.unroll.disable to this loop's loop id metadata. 368 /// 369 /// Remove existing unroll metadata and add unroll disable metadata to 370 /// indicate the loop has already been unrolled. This prevents a loop 371 /// from being unrolled more than is directed by a pragma if the loop 372 /// unrolling pass is run more than once (which it generally is). 373 void setLoopAlreadyUnrolled(); 374 375 /// Add llvm.loop.mustprogress to this loop's loop id metadata. 376 void setLoopMustProgress(); 377 378 void dump() const; 379 void dumpVerbose() const; 380 381 /// Return the debug location of the start of this loop. 382 /// This looks for a BB terminating instruction with a known debug 383 /// location by looking at the preheader and header blocks. If it 384 /// cannot find a terminating instruction with location information, 385 /// it returns an unknown location. 386 DebugLoc getStartLoc() const; 387 388 /// Return the source code span of the loop. 389 LocRange getLocRange() const; 390 391 StringRef getName() const { 392 if (BasicBlock *Header = getHeader()) 393 if (Header->hasName()) 394 return Header->getName(); 395 return "<unnamed loop>"; 396 } 397 398 private: 399 Loop() = default; 400 401 friend class LoopInfoBase<BasicBlock, Loop>; 402 friend class LoopBase<BasicBlock, Loop>; 403 explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {} 404 ~Loop() = default; 405 }; 406 407 // Implementation in Support/GenericLoopInfoImpl.h 408 extern template class LoopInfoBase<BasicBlock, Loop>; 409 410 class LoopInfo : public LoopInfoBase<BasicBlock, Loop> { 411 typedef LoopInfoBase<BasicBlock, Loop> BaseT; 412 413 friend class LoopBase<BasicBlock, Loop>; 414 415 void operator=(const LoopInfo &) = delete; 416 LoopInfo(const LoopInfo &) = delete; 417 418 public: 419 LoopInfo() = default; 420 explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree); 421 422 LoopInfo(LoopInfo &&Arg) : BaseT(std::move(static_cast<BaseT &>(Arg))) {} 423 LoopInfo &operator=(LoopInfo &&RHS) { 424 BaseT::operator=(std::move(static_cast<BaseT &>(RHS))); 425 return *this; 426 } 427 428 /// Handle invalidation explicitly. 429 bool invalidate(Function &F, const PreservedAnalyses &PA, 430 FunctionAnalysisManager::Invalidator &); 431 432 // Most of the public interface is provided via LoopInfoBase. 433 434 /// Update LoopInfo after removing the last backedge from a loop. This updates 435 /// the loop forest and parent loops for each block so that \c L is no longer 436 /// referenced, but does not actually delete \c L immediately. The pointer 437 /// will remain valid until this LoopInfo's memory is released. 438 void erase(Loop *L); 439 440 /// Returns true if replacing From with To everywhere is guaranteed to 441 /// preserve LCSSA form. 442 bool replacementPreservesLCSSAForm(Instruction *From, Value *To) { 443 // Preserving LCSSA form is only problematic if the replacing value is an 444 // instruction. 445 Instruction *I = dyn_cast<Instruction>(To); 446 if (!I) 447 return true; 448 // If both instructions are defined in the same basic block then replacement 449 // cannot break LCSSA form. 450 if (I->getParent() == From->getParent()) 451 return true; 452 // If the instruction is not defined in a loop then it can safely replace 453 // anything. 454 Loop *ToLoop = getLoopFor(I->getParent()); 455 if (!ToLoop) 456 return true; 457 // If the replacing instruction is defined in the same loop as the original 458 // instruction, or in a loop that contains it as an inner loop, then using 459 // it as a replacement will not break LCSSA form. 460 return ToLoop->contains(getLoopFor(From->getParent())); 461 } 462 463 /// Checks if moving a specific instruction can break LCSSA in any loop. 464 /// 465 /// Return true if moving \p Inst to before \p NewLoc will break LCSSA, 466 /// assuming that the function containing \p Inst and \p NewLoc is currently 467 /// in LCSSA form. 468 bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) { 469 assert(Inst->getFunction() == NewLoc->getFunction() && 470 "Can't reason about IPO!"); 471 472 auto *OldBB = Inst->getParent(); 473 auto *NewBB = NewLoc->getParent(); 474 475 // Movement within the same loop does not break LCSSA (the equality check is 476 // to avoid doing a hashtable lookup in case of intra-block movement). 477 if (OldBB == NewBB) 478 return true; 479 480 auto *OldLoop = getLoopFor(OldBB); 481 auto *NewLoop = getLoopFor(NewBB); 482 483 if (OldLoop == NewLoop) 484 return true; 485 486 // Check if Outer contains Inner; with the null loop counting as the 487 // "outermost" loop. 488 auto Contains = [](const Loop *Outer, const Loop *Inner) { 489 return !Outer || Outer->contains(Inner); 490 }; 491 492 // To check that the movement of Inst to before NewLoc does not break LCSSA, 493 // we need to check two sets of uses for possible LCSSA violations at 494 // NewLoc: the users of NewInst, and the operands of NewInst. 495 496 // If we know we're hoisting Inst out of an inner loop to an outer loop, 497 // then the uses *of* Inst don't need to be checked. 498 499 if (!Contains(NewLoop, OldLoop)) { 500 for (Use &U : Inst->uses()) { 501 auto *UI = cast<Instruction>(U.getUser()); 502 auto *UBB = isa<PHINode>(UI) ? cast<PHINode>(UI)->getIncomingBlock(U) 503 : UI->getParent(); 504 if (UBB != NewBB && getLoopFor(UBB) != NewLoop) 505 return false; 506 } 507 } 508 509 // If we know we're sinking Inst from an outer loop into an inner loop, then 510 // the *operands* of Inst don't need to be checked. 511 512 if (!Contains(OldLoop, NewLoop)) { 513 // See below on why we can't handle phi nodes here. 514 if (isa<PHINode>(Inst)) 515 return false; 516 517 for (Use &U : Inst->operands()) { 518 auto *DefI = dyn_cast<Instruction>(U.get()); 519 if (!DefI) 520 return false; 521 522 // This would need adjustment if we allow Inst to be a phi node -- the 523 // new use block won't simply be NewBB. 524 525 auto *DefBlock = DefI->getParent(); 526 if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop) 527 return false; 528 } 529 } 530 531 return true; 532 } 533 534 // Return true if a new use of V added in ExitBB would require an LCSSA PHI 535 // to be inserted at the begining of the block. Note that V is assumed to 536 // dominate ExitBB, and ExitBB must be the exit block of some loop. The 537 // IR is assumed to be in LCSSA form before the planned insertion. 538 bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V, 539 const BasicBlock *ExitBB) const; 540 }; 541 542 /// Enable verification of loop info. 543 /// 544 /// The flag enables checks which are expensive and are disabled by default 545 /// unless the `EXPENSIVE_CHECKS` macro is defined. The `-verify-loop-info` 546 /// flag allows the checks to be enabled selectively without re-compilation. 547 extern bool VerifyLoopInfo; 548 549 // Allow clients to walk the list of nested loops... 550 template <> struct GraphTraits<const Loop *> { 551 typedef const Loop *NodeRef; 552 typedef LoopInfo::iterator ChildIteratorType; 553 554 static NodeRef getEntryNode(const Loop *L) { return L; } 555 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 556 static ChildIteratorType child_end(NodeRef N) { return N->end(); } 557 }; 558 559 template <> struct GraphTraits<Loop *> { 560 typedef Loop *NodeRef; 561 typedef LoopInfo::iterator ChildIteratorType; 562 563 static NodeRef getEntryNode(Loop *L) { return L; } 564 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 565 static ChildIteratorType child_end(NodeRef N) { return N->end(); } 566 }; 567 568 /// Analysis pass that exposes the \c LoopInfo for a function. 569 class LoopAnalysis : public AnalysisInfoMixin<LoopAnalysis> { 570 friend AnalysisInfoMixin<LoopAnalysis>; 571 static AnalysisKey Key; 572 573 public: 574 typedef LoopInfo Result; 575 576 LoopInfo run(Function &F, FunctionAnalysisManager &AM); 577 }; 578 579 /// Printer pass for the \c LoopAnalysis results. 580 class LoopPrinterPass : public PassInfoMixin<LoopPrinterPass> { 581 raw_ostream &OS; 582 583 public: 584 explicit LoopPrinterPass(raw_ostream &OS) : OS(OS) {} 585 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 586 }; 587 588 /// Verifier pass for the \c LoopAnalysis results. 589 struct LoopVerifierPass : public PassInfoMixin<LoopVerifierPass> { 590 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 591 }; 592 593 /// The legacy pass manager's analysis pass to compute loop information. 594 class LoopInfoWrapperPass : public FunctionPass { 595 LoopInfo LI; 596 597 public: 598 static char ID; // Pass identification, replacement for typeid 599 600 LoopInfoWrapperPass(); 601 602 LoopInfo &getLoopInfo() { return LI; } 603 const LoopInfo &getLoopInfo() const { return LI; } 604 605 /// Calculate the natural loop information for a given function. 606 bool runOnFunction(Function &F) override; 607 608 void verifyAnalysis() const override; 609 610 void releaseMemory() override { LI.releaseMemory(); } 611 612 void print(raw_ostream &O, const Module *M = nullptr) const override; 613 614 void getAnalysisUsage(AnalysisUsage &AU) const override; 615 }; 616 617 /// Function to print a loop's contents as LLVM's text IR assembly. 618 void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner = ""); 619 620 /// Find and return the loop attribute node for the attribute @p Name in 621 /// @p LoopID. Return nullptr if there is no such attribute. 622 MDNode *findOptionMDForLoopID(MDNode *LoopID, StringRef Name); 623 624 /// Find string metadata for a loop. 625 /// 626 /// Returns the MDNode where the first operand is the metadata's name. The 627 /// following operands are the metadata's values. If no metadata with @p Name is 628 /// found, return nullptr. 629 MDNode *findOptionMDForLoop(const Loop *TheLoop, StringRef Name); 630 631 std::optional<bool> getOptionalBoolLoopAttribute(const Loop *TheLoop, 632 StringRef Name); 633 634 /// Returns true if Name is applied to TheLoop and enabled. 635 bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name); 636 637 /// Find named metadata for a loop with an integer value. 638 std::optional<int> getOptionalIntLoopAttribute(const Loop *TheLoop, 639 StringRef Name); 640 641 /// Find named metadata for a loop with an integer value. Return \p Default if 642 /// not set. 643 int getIntLoopAttribute(const Loop *TheLoop, StringRef Name, int Default = 0); 644 645 /// Find string metadata for loop 646 /// 647 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an 648 /// operand or null otherwise. If the string metadata is not found return 649 /// Optional's not-a-value. 650 std::optional<const MDOperand *> findStringMetadataForLoop(const Loop *TheLoop, 651 StringRef Name); 652 653 /// Look for the loop attribute that requires progress within the loop. 654 /// Note: Most consumers probably want "isMustProgress" which checks 655 /// the containing function attribute too. 656 bool hasMustProgress(const Loop *L); 657 658 /// Return true if this loop can be assumed to make progress. (i.e. can't 659 /// be infinite without side effects without also being undefined) 660 bool isMustProgress(const Loop *L); 661 662 /// Return true if this loop can be assumed to run for a finite number of 663 /// iterations. 664 bool isFinite(const Loop *L); 665 666 /// Return whether an MDNode might represent an access group. 667 /// 668 /// Access group metadata nodes have to be distinct and empty. Being 669 /// always-empty ensures that it never needs to be changed (which -- because 670 /// MDNodes are designed immutable -- would require creating a new MDNode). Note 671 /// that this is not a sufficient condition: not every distinct and empty NDNode 672 /// is representing an access group. 673 bool isValidAsAccessGroup(MDNode *AccGroup); 674 675 /// Create a new LoopID after the loop has been transformed. 676 /// 677 /// This can be used when no follow-up loop attributes are defined 678 /// (llvm::makeFollowupLoopID returning None) to stop transformations to be 679 /// applied again. 680 /// 681 /// @param Context The LLVMContext in which to create the new LoopID. 682 /// @param OrigLoopID The original LoopID; can be nullptr if the original 683 /// loop has no LoopID. 684 /// @param RemovePrefixes Remove all loop attributes that have these prefixes. 685 /// Use to remove metadata of the transformation that has 686 /// been applied. 687 /// @param AddAttrs Add these loop attributes to the new LoopID. 688 /// 689 /// @return A new LoopID that can be applied using Loop::setLoopID(). 690 llvm::MDNode * 691 makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID, 692 llvm::ArrayRef<llvm::StringRef> RemovePrefixes, 693 llvm::ArrayRef<llvm::MDNode *> AddAttrs); 694 695 } // namespace llvm 696 697 #endif 698