1 //===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===//
33 class Loop;  variable
40 extern template class LoopBase<BasicBlock, Loop>;
42 /// Represents a single loop in the control flow graph.  Note that not all SCCs
44 class LLVM_EXTERNAL_VISIBILITY Loop : public LoopBase<BasicBlock, Loop> {
46   /// A range representing the start and end location of a loop.
65   /// Return true if the specified value is loop invariant.
68   /// Return true if all the operands of the specified instruction are loop
72   /// If the given value is an instruction inside of the loop and it can be
73   /// hoisted, do so to make it trivially loop-invariant.
74   /// Return true if \c V is already loop-invariant, and false if \c V can't
75   /// be made loop-invariant. If \c V is made loop-invariant, \c Changed is
80   /// If null, the terminator of the loop preheader is used.
87   /// If the given instruction is inside of the loop and it can be hoisted, do
88   /// so to make it trivially loop-invariant.
89   /// Return true if \c I is already loop-invariant, and false if \c I can't
90   /// be made loop-invariant. If \c I is made loop-invariant, \c Changed is
95   /// If null, the terminator of the loop preheader is used.
102   /// Check to see if the loop has a canonical induction variable: an integer
104   /// loop. If so, return the phi node that corresponds to it.
115   /// non-unique or the loop is dead; otherwise, return true.
119   /// Below are some utilities to get the loop guard, loop bounds and induction
121   /// variable, if the loop is guarded, and if the loop is canonical.
126   ///   <loop body>
132   /// loop:
134   ///   <loop body>
138   ///   if (cmp) goto loop
165     static std::optional<Loop::LoopBounds>
166     getBounds(const Loop &L, PHINode &IndVar, ScalarEvolution &SE);
168     /// Get the initial value of the loop induction variable.
171     /// Get the instruction that updates the loop induction variable.
174     /// Get the step that the loop induction variable gets updated by in each
175     /// loop iteration. Return nullptr if not found.
178     /// Get the final value of the loop induction variable.
186     /// 1. The first successor of the latch branch is the loop header
192     ///    - else if the loop is increasing, return slt
194     ///    - else if the loop is decreasing, return sgt
199     /// loop.header:
200     ///  %iv = phi [%initialiv, %loop.preheader], [%inc, %loop.header]
203     ///  br %cmp, %loop.exit, %loop.header
204     /// loop.exit:
206     /// - The second successor of the latch branch is the loop header instead
216     /// An enum for the direction of the loop
222     /// Get the direction of the loop.
226     LoopBounds(const Loop &Loop, Value &I, Instruction &SI, Value *SV, Value &F,  in LoopBounds()
228         : L(Loop), InitialIVValue(I), StepInst(SI), StepValue(SV),  in LoopBounds()
231     const Loop &L;
233     // The initial value of the loop induction variable
236     // The instruction that updates the loop induction variable
239     // The value that the loop induction variable gets updated by in each loop
243     // The final value of the loop induction variable
253   /// Return the loop induction variable if found, else return nullptr.
254   /// An instruction is considered as the loop induction variable if
255   /// - it is an induction variable of the loop; and
256   /// - it is used to determine the condition of the branch in the loop latch
259   /// zero and increments by one each time through the loop (but it can be).
262   /// Get the loop induction descriptor for the loop induction variable. Return
263   /// true if the loop induction variable is found.
268   /// - in the loop header
269   /// - not used outside of the loop
270   /// - incremented by a loop invariant step for each loop iteration
273   ///       conditional branch in the loop latch. (but it can be)
277   /// Return the loop guard branch, if it exists.
279   /// This currently only works on simplified loop, as it requires a preheader
297   /// Return true iff the loop is
299   /// - guarded by a loop guard branch.
302   /// Return true if the loop is in rotated form.
304   /// This does not check if the loop was rotated by loop rotation, instead it
305   /// only checks if the loop is in rotated form (has a valid latch that exists
306   /// the loop).
308     assert(!isInvalid() && "Loop not in a valid state!");  in isRotatedForm()
313   /// Return true if the loop induction variable starts at zero and increments
314   /// by one each time through the loop.
317   /// Return true if the Loop is in LCSSA form. If \p IgnoreTokens is set to
318   /// true, token values defined inside loop are allowed to violate LCSSA form.
321   /// Return true if this Loop and all inner subloops are in LCSSA form. If \p
322   /// IgnoreTokens is set to true, token values defined inside loop are allowed
327   /// Return true if the Loop is in the form that the LoopSimplify form
331   /// Return true if the loop body is safe to clone in practice.
334   /// Returns true if the loop is annotated parallel.
336   /// A parallel loop can be assumed to not contain any dependencies between
337   /// iterations by the compiler. That is, any loop-carried dependency checking
338   /// can be skipped completely when parallelizing the loop on the target
339   /// machine. Thus, if the parallel loop information originates from the
341   /// programmer's responsibility to ensure there are no loop-carried
348   /// Return the llvm.loop loop id metadata node for this loop if it is present.
350   /// If this loop contains the same llvm.loop metadata on each branch to the
352   /// contain llvm.loop or if multiple latches contain different nodes then
355   /// Set the llvm.loop loop id metadata for this loop.
358   /// the loop that branches to the loop header.
364   /// Add llvm.loop.unroll.disable to this loop's loop id metadata.
367   /// indicate the loop has already been unrolled.  This prevents a loop
368   /// from being unrolled more than is directed by a pragma if the loop
372   /// Add llvm.loop.mustprogress to this loop's loop id metadata.
378   /// Return the debug location of the start of this loop.
385   /// Return the source code span of the loop.
388   /// Return a string containing the debug location of the loop (file name +
397     return "<unnamed loop>";  in getName()
401   Loop() = default;
403   friend class LoopInfoBase<BasicBlock, Loop>;
404   friend class LoopBase<BasicBlock, Loop>;
405   explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {}  in Loop()  function
406   ~Loop() = default;
410 extern template class LoopInfoBase<BasicBlock, Loop>;
412 class LoopInfo : public LoopInfoBase<BasicBlock, Loop> {
413   typedef LoopInfoBase<BasicBlock, Loop> BaseT;
415   friend class LoopBase<BasicBlock, Loop>;
436   /// Update LoopInfo after removing the last backedge from a loop. This updates
437   /// the loop forest and parent loops for each block so that \c L is no longer
440   void erase(Loop *L);
454     // If the instruction is not defined in a loop then it can safely replace  in replacementPreservesLCSSAForm()
456     Loop *ToLoop = getLoopFor(I->getParent());  in replacementPreservesLCSSAForm()
459     // If the replacing instruction is defined in the same loop as the original  in replacementPreservesLCSSAForm()
460     // instruction, or in a loop that contains it as an inner loop, then using  in replacementPreservesLCSSAForm()
465   /// Checks if moving a specific instruction can break LCSSA in any loop.
477     // Movement within the same loop does not break LCSSA (the equality check is  in movementPreservesLCSSAForm()
488     // Check if Outer contains Inner; with the null loop counting as the  in movementPreservesLCSSAForm()
489     // "outermost" loop.  in movementPreservesLCSSAForm()
490     auto Contains = [](const Loop *Outer, const Loop *Inner) {  in movementPreservesLCSSAForm()
498     // If we know we're hoisting Inst out of an inner loop to an outer loop,  in movementPreservesLCSSAForm()
511     // If we know we're sinking Inst from an outer loop into an inner loop, then  in movementPreservesLCSSAForm()
538   // dominate ExitBB, and ExitBB must be the exit block of some loop.  The
544 /// Enable verification of loop info.
547 /// unless the `EXPENSIVE_CHECKS` macro is defined.  The `-verify-loop-info`
552 template <> struct GraphTraits<const Loop *> {
553   typedef const Loop *NodeRef;
556   static NodeRef getEntryNode(const Loop *L) { return L; }
561 template <> struct GraphTraits<Loop *> {
562   typedef Loop *NodeRef;
565   static NodeRef getEntryNode(Loop *L) { return L; }
597 /// The legacy pass manager's analysis pass to compute loop information.
609   /// Calculate the natural loop information for a given function.
621 /// Function to print a loop's contents as LLVM's text IR assembly.
622 void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner = "");
624 /// Find and return the loop attribute node for the attribute @p Name in
628 /// Find string metadata for a loop.
633 MDNode *findOptionMDForLoop(const Loop *TheLoop, StringRef Name);
635 std::optional<bool> getOptionalBoolLoopAttribute(const Loop *TheLoop,
639 bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name);
641 /// Find named metadata for a loop with an integer value.
642 std::optional<int> getOptionalIntLoopAttribute(const Loop *TheLoop,
645 /// Find named metadata for a loop with an integer value. Return \p Default if
647 int getIntLoopAttribute(const Loop *TheLoop, StringRef Name, int Default = 0);
649 /// Find string metadata for loop
654 std::optional<const MDOperand *> findStringMetadataForLoop(const Loop *TheLoop,
657 /// Find the convergence heart of the loop.
658 CallBase *getLoopConvergenceHeart(const Loop *TheLoop);
660 /// Look for the loop attribute that requires progress within the loop.
663 bool hasMustProgress(const Loop *L);
665 /// Return true if this loop can be assumed to make progress.  (i.e. can't
667 bool isMustProgress(const Loop *L);
669 /// Return true if this loop can be assumed to run for a finite number of
671 bool isFinite(const Loop *L);
682 /// Create a new LoopID after the loop has been transformed.
684 /// This can be used when no follow-up loop attributes are defined
690 ///                       loop has no LoopID.
691 /// @param RemovePrefixes Remove all loop attributes that have these prefixes.
694 /// @param AddAttrs       Add these loop attributes to the new LoopID.
696 /// @return A new LoopID that can be applied using Loop::setLoopID().