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