LLVM 19.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/CFG.h"
20#include "llvm/IR/PassManager.h"
21#include "llvm/Pass.h"
23#include <algorithm>
24#include <optional>
25#include <utility>
26
27namespace llvm {
28
29class DominatorTree;
30class InductionDescriptor;
31class Instruction;
32class LoopInfo;
33class Loop;
34class MDNode;
35class MemorySSAUpdater;
36class ScalarEvolution;
37class raw_ostream;
38
39// Implementation in Support/GenericLoopInfoImpl.h
40extern template class LoopBase<BasicBlock, Loop>;
41
42/// Represents a single loop in the control flow graph. Note that not all SCCs
43/// in the CFG are necessarily loops.
45public:
46 /// A range representing the start and end location of a loop.
47 class LocRange {
48 DebugLoc Start;
50
51 public:
52 LocRange() = default;
53 LocRange(DebugLoc Start) : Start(Start), End(Start) {}
55 : Start(std::move(Start)), End(std::move(End)) {}
56
57 const DebugLoc &getStart() const { return Start; }
58 const DebugLoc &getEnd() const { return End; }
59
60 /// Check for null.
61 ///
62 explicit operator bool() const { return Start && End; }
63 };
64
65 /// Return true if the specified value is loop invariant.
66 bool isLoopInvariant(const Value *V) const;
67
68 /// Return true if all the operands of the specified instruction are loop
69 /// invariant.
70 bool hasLoopInvariantOperands(const Instruction *I) const;
71
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
76 /// set to true. This function can be used as a slightly more aggressive
77 /// replacement for isLoopInvariant.
78 ///
79 /// If InsertPt is specified, it is the point to hoist instructions to.
80 /// If null, the terminator of the loop preheader is used.
81 ///
82 bool makeLoopInvariant(Value *V, bool &Changed,
83 Instruction *InsertPt = nullptr,
84 MemorySSAUpdater *MSSAU = nullptr,
85 ScalarEvolution *SE = nullptr) const;
86
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
91 /// set to true. This function can be used as a slightly more aggressive
92 /// replacement for isLoopInvariant.
93 ///
94 /// If InsertPt is specified, it is the point to hoist instructions to.
95 /// If null, the terminator of the loop preheader is used.
96 ///
97 bool makeLoopInvariant(Instruction *I, bool &Changed,
98 Instruction *InsertPt = nullptr,
99 MemorySSAUpdater *MSSAU = nullptr,
100 ScalarEvolution *SE = nullptr) const;
101
102 /// Check to see if the loop has a canonical induction variable: an integer
103 /// recurrence that starts at 0 and increments by one each time through the
104 /// loop. If so, return the phi node that corresponds to it.
105 ///
106 /// The IndVarSimplify pass transforms loops to have a canonical induction
107 /// variable.
108 ///
109 PHINode *getCanonicalInductionVariable() const;
110
111 /// Get the latch condition instruction.
112 ICmpInst *getLatchCmpInst() const;
113
114 /// Obtain the unique incoming and back edge. Return false if they are
115 /// non-unique or the loop is dead; otherwise, return true.
116 bool getIncomingAndBackEdge(BasicBlock *&Incoming,
117 BasicBlock *&Backedge) const;
118
119 /// Below are some utilities to get the loop guard, loop bounds and induction
120 /// variable, and to check if a given phinode is an auxiliary induction
121 /// variable, if the loop is guarded, and if the loop is canonical.
122 ///
123 /// Here is an example:
124 /// \code
125 /// for (int i = lb; i < ub; i+=step)
126 /// <loop body>
127 /// --- pseudo LLVMIR ---
128 /// beforeloop:
129 /// guardcmp = (lb < ub)
130 /// if (guardcmp) goto preheader; else goto afterloop
131 /// preheader:
132 /// loop:
133 /// i_1 = phi[{lb, preheader}, {i_2, latch}]
134 /// <loop body>
135 /// i_2 = i_1 + step
136 /// latch:
137 /// cmp = (i_2 < ub)
138 /// if (cmp) goto loop
139 /// exit:
140 /// afterloop:
141 /// \endcode
142 ///
143 /// - getBounds
144 /// - getInitialIVValue --> lb
145 /// - getStepInst --> i_2 = i_1 + step
146 /// - getStepValue --> step
147 /// - getFinalIVValue --> ub
148 /// - getCanonicalPredicate --> '<'
149 /// - getDirection --> Increasing
150 ///
151 /// - getInductionVariable --> i_1
152 /// - isAuxiliaryInductionVariable(x) --> true if x == i_1
153 /// - getLoopGuardBranch()
154 /// --> `if (guardcmp) goto preheader; else goto afterloop`
155 /// - isGuarded() --> true
156 /// - isCanonical --> false
157 struct LoopBounds {
158 /// Return the LoopBounds object if
159 /// - the given \p IndVar is an induction variable
160 /// - the initial value of the induction variable can be found
161 /// - the step instruction of the induction variable can be found
162 /// - the final value of the induction variable can be found
163 ///
164 /// Else std::nullopt.
165 static std::optional<Loop::LoopBounds>
166 getBounds(const Loop &L, PHINode &IndVar, ScalarEvolution &SE);
167
168 /// Get the initial value of the loop induction variable.
169 Value &getInitialIVValue() const { return InitialIVValue; }
170
171 /// Get the instruction that updates the loop induction variable.
172 Instruction &getStepInst() const { return StepInst; }
173
174 /// Get the step that the loop induction variable gets updated by in each
175 /// loop iteration. Return nullptr if not found.
176 Value *getStepValue() const { return StepValue; }
177
178 /// Get the final value of the loop induction variable.
179 Value &getFinalIVValue() const { return FinalIVValue; }
180
181 /// Return the canonical predicate for the latch compare instruction, if
182 /// able to be calcuated. Else BAD_ICMP_PREDICATE.
183 ///
184 /// A predicate is considered as canonical if requirements below are all
185 /// satisfied:
186 /// 1. The first successor of the latch branch is the loop header
187 /// If not, inverse the predicate.
188 /// 2. One of the operands of the latch comparison is StepInst
189 /// If not, and
190 /// - if the current calcuated predicate is not ne or eq, flip the
191 /// predicate.
192 /// - else if the loop is increasing, return slt
193 /// (notice that it is safe to change from ne or eq to sign compare)
194 /// - else if the loop is decreasing, return sgt
195 /// (notice that it is safe to change from ne or eq to sign compare)
196 ///
197 /// Here is an example when both (1) and (2) are not satisfied:
198 /// \code
199 /// loop.header:
200 /// %iv = phi [%initialiv, %loop.preheader], [%inc, %loop.header]
201 /// %inc = add %iv, %step
202 /// %cmp = slt %iv, %finaliv
203 /// br %cmp, %loop.exit, %loop.header
204 /// loop.exit:
205 /// \endcode
206 /// - The second successor of the latch branch is the loop header instead
207 /// of the first successor (slt -> sge)
208 /// - The first operand of the latch comparison (%cmp) is the IndVar (%iv)
209 /// instead of the StepInst (%inc) (sge -> sgt)
210 ///
211 /// The predicate would be sgt if both (1) and (2) are satisfied.
212 /// getCanonicalPredicate() returns sgt for this example.
213 /// Note: The IR is not changed.
214 ICmpInst::Predicate getCanonicalPredicate() const;
215
216 /// An enum for the direction of the loop
217 /// - for (int i = 0; i < ub; ++i) --> Increasing
218 /// - for (int i = ub; i > 0; --i) --> Descresing
219 /// - for (int i = x; i != y; i+=z) --> Unknown
220 enum class Direction { Increasing, Decreasing, Unknown };
221
222 /// Get the direction of the loop.
223 Direction getDirection() const;
224
225 private:
226 LoopBounds(const Loop &Loop, Value &I, Instruction &SI, Value *SV, Value &F,
227 ScalarEvolution &SE)
228 : L(Loop), InitialIVValue(I), StepInst(SI), StepValue(SV),
229 FinalIVValue(F), SE(SE) {}
230
231 const Loop &L;
232
233 // The initial value of the loop induction variable
234 Value &InitialIVValue;
235
236 // The instruction that updates the loop induction variable
237 Instruction &StepInst;
238
239 // The value that the loop induction variable gets updated by in each loop
240 // iteration
241 Value *StepValue;
242
243 // The final value of the loop induction variable
244 Value &FinalIVValue;
245
246 ScalarEvolution &SE;
247 };
248
249 /// Return the struct LoopBounds collected if all struct members are found,
250 /// else std::nullopt.
251 std::optional<LoopBounds> getBounds(ScalarEvolution &SE) const;
252
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
257 ///
258 /// Note: the induction variable doesn't need to be canonical, i.e. starts at
259 /// zero and increments by one each time through the loop (but it can be).
260 PHINode *getInductionVariable(ScalarEvolution &SE) const;
261
262 /// Get the loop induction descriptor for the loop induction variable. Return
263 /// true if the loop induction variable is found.
264 bool getInductionDescriptor(ScalarEvolution &SE,
265 InductionDescriptor &IndDesc) const;
266
267 /// Return true if the given PHINode \p AuxIndVar is
268 /// - in the loop header
269 /// - not used outside of the loop
270 /// - incremented by a loop invariant step for each loop iteration
271 /// - step instruction opcode should be add or sub
272 /// Note: auxiliary induction variable is not required to be used in the
273 /// conditional branch in the loop latch. (but it can be)
274 bool isAuxiliaryInductionVariable(PHINode &AuxIndVar,
275 ScalarEvolution &SE) const;
276
277 /// Return the loop guard branch, if it exists.
278 ///
279 /// This currently only works on simplified loop, as it requires a preheader
280 /// and a latch to identify the guard. It will work on loops of the form:
281 /// \code
282 /// GuardBB:
283 /// br cond1, Preheader, ExitSucc <== GuardBranch
284 /// Preheader:
285 /// br Header
286 /// Header:
287 /// ...
288 /// br Latch
289 /// Latch:
290 /// br cond2, Header, ExitBlock
291 /// ExitBlock:
292 /// br ExitSucc
293 /// ExitSucc:
294 /// \endcode
295 BranchInst *getLoopGuardBranch() const;
296
297 /// Return true iff the loop is
298 /// - in simplify rotated form, and
299 /// - guarded by a loop guard branch.
300 bool isGuarded() const { return (getLoopGuardBranch() != nullptr); }
301
302 /// Return true if the loop is in rotated form.
303 ///
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).
307 bool isRotatedForm() const {
308 assert(!isInvalid() && "Loop not in a valid state!");
309 BasicBlock *Latch = getLoopLatch();
310 return Latch && isLoopExiting(Latch);
311 }
312
313 /// Return true if the loop induction variable starts at zero and increments
314 /// by one each time through the loop.
315 bool isCanonical(ScalarEvolution &SE) const;
316
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.
319 bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens = true) const;
320
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
323 /// to violate LCSSA form.
324 bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI,
325 bool IgnoreTokens = true) const;
326
327 /// Return true if the Loop is in the form that the LoopSimplify form
328 /// transforms loops to, which is sometimes called normal form.
329 bool isLoopSimplifyForm() const;
330
331 /// Return true if the loop body is safe to clone in practice.
332 bool isSafeToClone() const;
333
334 /// Returns true if the loop is annotated parallel.
335 ///
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
340 /// programmer, e.g. via the OpenMP parallel for pragma, it is the
341 /// programmer's responsibility to ensure there are no loop-carried
342 /// dependencies. The final execution order of the instructions across
343 /// iterations is not guaranteed, thus, the end result might or might not
344 /// implement actual concurrent execution of instructions across multiple
345 /// iterations.
346 bool isAnnotatedParallel() const;
347
348 /// Return the llvm.loop loop id metadata node for this loop if it is present.
349 ///
350 /// If this loop contains the same llvm.loop metadata on each branch to the
351 /// header then the node is returned. If any latch instruction does not
352 /// contain llvm.loop or if multiple latches contain different nodes then
353 /// 0 is returned.
354 MDNode *getLoopID() const;
355 /// Set the llvm.loop loop id metadata for this loop.
356 ///
357 /// The LoopID metadata node will be added to each terminator instruction in
358 /// the loop that branches to the loop header.
359 ///
360 /// The LoopID metadata node should have one or more operands and the first
361 /// operand should be the node itself.
362 void setLoopID(MDNode *LoopID) const;
363
364 /// Add llvm.loop.unroll.disable to this loop's loop id metadata.
365 ///
366 /// Remove existing unroll metadata and add unroll disable metadata to
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
369 /// unrolling pass is run more than once (which it generally is).
370 void setLoopAlreadyUnrolled();
371
372 /// Add llvm.loop.mustprogress to this loop's loop id metadata.
373 void setLoopMustProgress();
374
375 void dump() const;
376 void dumpVerbose() const;
377
378 /// Return the debug location of the start of this loop.
379 /// This looks for a BB terminating instruction with a known debug
380 /// location by looking at the preheader and header blocks. If it
381 /// cannot find a terminating instruction with location information,
382 /// it returns an unknown location.
383 DebugLoc getStartLoc() const;
384
385 /// Return the source code span of the loop.
386 LocRange getLocRange() 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/// Look for the loop attribute that requires progress within the loop.
653/// Note: Most consumers probably want "isMustProgress" which checks
654/// the containing function attribute too.
655bool hasMustProgress(const Loop *L);
656
657/// Return true if this loop can be assumed to make progress. (i.e. can't
658/// be infinite without side effects without also being undefined)
659bool isMustProgress(const Loop *L);
660
661/// Return true if this loop can be assumed to run for a finite number of
662/// iterations.
663bool isFinite(const Loop *L);
664
665/// Return whether an MDNode might represent an access group.
666///
667/// Access group metadata nodes have to be distinct and empty. Being
668/// always-empty ensures that it never needs to be changed (which -- because
669/// MDNodes are designed immutable -- would require creating a new MDNode). Note
670/// that this is not a sufficient condition: not every distinct and empty NDNode
671/// is representing an access group.
672bool isValidAsAccessGroup(MDNode *AccGroup);
673
674/// Create a new LoopID after the loop has been transformed.
675///
676/// This can be used when no follow-up loop attributes are defined
677/// (llvm::makeFollowupLoopID returning None) to stop transformations to be
678/// applied again.
679///
680/// @param Context The LLVMContext in which to create the new LoopID.
681/// @param OrigLoopID The original LoopID; can be nullptr if the original
682/// loop has no LoopID.
683/// @param RemovePrefixes Remove all loop attributes that have these prefixes.
684/// Use to remove metadata of the transformation that has
685/// been applied.
686/// @param AddAttrs Add these loop attributes to the new LoopID.
687///
688/// @return A new LoopID that can be applied using Loop::setLoopID().
690makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID,
691 llvm::ArrayRef<llvm::StringRef> RemovePrefixes,
693
694} // namespace llvm
695
696#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...
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Loop::LoopBounds::Direction Direction
Definition: LoopInfo.cpp:230
#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
This file defines the SmallVector class.
Value * RHS
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:387
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
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:60
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:965
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:311
This instruction compares its operands according to the predicate given to the constructor.
const BasicBlock * getParent() const
Definition: Instruction.h:151
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:84
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:47
LocRange(DebugLoc Start, DebugLoc End)
Definition: LoopInfo.h:54
const DebugLoc & getStart() const
Definition: LoopInfo.h:57
LocRange(DebugLoc Start)
Definition: LoopInfo.h:53
const DebugLoc & getEnd() const
Definition: LoopInfo.h:58
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
bool isGuarded() const
Return true iff the loop is.
Definition: LoopInfo.h:300
StringRef getName() const
Definition: LoopInfo.h:388
bool isRotatedForm() const
Return true if the loop is in rotated form.
Definition: LoopInfo.h:307
Metadata node.
Definition: Metadata.h:1067
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:109
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
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:1085
std::optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)
Definition: LoopInfo.cpp:1067
int getIntLoopAttribute(const Loop *TheLoop, StringRef Name, int Default=0)
Find named metadata for a loop with an integer value.
Definition: LoopInfo.cpp:1103
std::optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for loop.
Definition: LoopInfo.cpp:1053
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
Definition: LoopInfo.cpp:1043
bool hasMustProgress(const Loop *L)
Look for the loop attribute that requires progress within the loop.
Definition: LoopInfo.cpp:1114
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:2068
bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
Definition: LoopInfo.cpp:1118
bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
Definition: LoopInfo.cpp:1108
bool VerifyLoopInfo
Enable verification of loop info.
Definition: LoopInfo.cpp:50
std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
Definition: LoopInfo.cpp:1089
bool isValidAsAccessGroup(MDNode *AccGroup)
Return whether an MDNode might represent an access group.
Definition: LoopInfo.cpp:1122
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:1858
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:1126
@ 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:977
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Definition: LoopInfo.cpp:1017
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:114
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
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:157
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:220
Value & getFinalIVValue() const
Get the final value of the loop induction variable.
Definition: LoopInfo.h:179
Value * getStepValue() const
Get the step that the loop induction variable gets updated by in each loop iteration.
Definition: LoopInfo.h:176
Instruction & getStepInst() const
Get the instruction that updates the loop induction variable.
Definition: LoopInfo.h:172
Value & getInitialIVValue() const
Get the initial value of the loop induction variable.
Definition: LoopInfo.h:169
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:91