1//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===// 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 7//===----------------------------------------------------------------------===// 9// This file declares a GenericLoopInfo instantiation for LLVM IR. 11//===----------------------------------------------------------------------===// 13#ifndef LLVM_ANALYSIS_LOOPINFO_H 14#define LLVM_ANALYSIS_LOOPINFO_H 27classInductionDescriptor;
34// Implementation in Support/GenericLoopInfoImpl.h 35externtemplateclassLoopBase<BasicBlock, Loop>;
37/// Represents a single loop in the control flow graph. Note that not all SCCs 38/// in the CFG are necessarily loops. 41 /// A range representing the start and end location of a loop. 57explicitoperatorbool()
const{
return Start &&
End; }
60 /// Return true if the specified value is loop invariant. 61bool isLoopInvariant(
constValue *V)
const;
63 /// Return true if all the operands of the specified instruction are loop 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. 74 /// If InsertPt is specified, it is the point to hoist instructions to. 75 /// If null, the terminator of the loop preheader is used. 77bool makeLoopInvariant(
Value *V,
bool &Changed,
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. 89 /// If InsertPt is specified, it is the point to hoist instructions to. 90 /// If null, the terminator of the loop preheader is used. 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. 101 /// The IndVarSimplify pass transforms loops to have a canonical induction 104PHINode *getCanonicalInductionVariable()
const;
106 /// Get the latch condition instruction. 109 /// Obtain the unique incoming and back edge. Return false if they are 110 /// non-unique or the loop is dead; otherwise, return true. 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. 118 /// Here is an example: 120 /// for (int i = lb; i < ub; i+=step) 122 /// --- pseudo LLVMIR --- 124 /// guardcmp = (lb < ub) 125 /// if (guardcmp) goto preheader; else goto afterloop 128 /// i_1 = phi[{lb, preheader}, {i_2, latch}] 133 /// if (cmp) goto loop 139 /// - getInitialIVValue --> lb 140 /// - getStepInst --> i_2 = i_1 + step 141 /// - getStepValue --> step 142 /// - getFinalIVValue --> ub 143 /// - getCanonicalPredicate --> '<' 144 /// - getDirection --> Increasing 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 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 159 /// Else std::nullopt. 160static std::optional<Loop::LoopBounds>
163 /// Get the initial value of the loop induction variable. 166 /// Get the instruction that updates the loop induction variable. 169 /// Get the step that the loop induction variable gets updated by in each 170 /// loop iteration. Return nullptr if not found. 173 /// Get the final value of the loop induction variable. 176 /// Return the canonical predicate for the latch compare instruction, if 177 /// able to be calcuated. Else BAD_ICMP_PREDICATE. 179 /// A predicate is considered as canonical if requirements below are all 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 185 /// - if the current calcuated predicate is not ne or eq, flip the 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) 192 /// Here is an example when both (1) and (2) are not satisfied: 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 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) 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. 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 217 /// Get the direction of the loop. 223 : L(
Loop), InitialIVValue(
I), StepInst(
SI), StepValue(SV),
224 FinalIVValue(
F), SE(SE) {}
228// The initial value of the loop induction variable 229Value &InitialIVValue;
231// The instruction that updates the loop induction variable 234// The value that the loop induction variable gets updated by in each loop 238// The final value of the loop induction variable 244 /// Return the struct LoopBounds collected if all struct members are found, 245 /// else std::nullopt. 246 std::optional<LoopBounds> getBounds(ScalarEvolution &SE)
const;
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 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;
257 /// Get the loop induction descriptor for the loop induction variable. Return 258 /// true if the loop induction variable is found. 259bool getInductionDescriptor(ScalarEvolution &SE,
260 InductionDescriptor &IndDesc)
const;
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) 269bool isAuxiliaryInductionVariable(PHINode &AuxIndVar,
270 ScalarEvolution &SE)
const;
272 /// Return the loop guard branch, if it exists. 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: 278 /// br cond1, Preheader, ExitSucc <== GuardBranch 285 /// br cond2, Header, ExitBlock 290 BranchInst *getLoopGuardBranch()
const;
292 /// Return true iff the loop is 293 /// - in simplify rotated form, and 294 /// - guarded by a loop guard branch. 295boolisGuarded()
const{
return (getLoopGuardBranch() !=
nullptr); }
297 /// Return true if the loop is in rotated form. 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 303assert(!isInvalid() &&
"Loop not in a valid state!");
305return Latch && isLoopExiting(Latch);
308 /// Return true if the loop induction variable starts at zero and increments 309 /// by one each time through the loop. 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. 314bool isLCSSAForm(
constDominatorTree &DT,
bool IgnoreTokens =
true)
const;
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. 320bool IgnoreTokens =
true)
const;
322 /// Return true if the Loop is in the form that the LoopSimplify form 323 /// transforms loops to, which is sometimes called normal form. 324bool isLoopSimplifyForm()
const;
326 /// Return true if the loop body is safe to clone in practice. 327bool isSafeToClone()
const;
329 /// Returns true if the loop is annotated parallel. 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 341bool isAnnotatedParallel()
const;
343 /// Return the llvm.loop loop id metadata node for this loop if it is present. 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 350 /// Set the llvm.loop loop id metadata for this loop. 352 /// The LoopID metadata node will be added to each terminator instruction in 353 /// the loop that branches to the loop header. 355 /// The LoopID metadata node should have one or more operands and the first 356 /// operand should be the node itself. 357void setLoopID(
MDNode *LoopID)
const;
359 /// Add llvm.loop.unroll.disable to this loop's loop id metadata. 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). 365void setLoopAlreadyUnrolled();
367 /// Add llvm.loop.mustprogress to this loop's loop id metadata. 368void setLoopMustProgress();
371void dumpVerbose()
const;
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. 380 /// Return the source code span of the loop. 381 LocRange getLocRange()
const;
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;
390if (Header->hasName())
391return Header->getName();
392return"<unnamed loop>";
404// Implementation in Support/GenericLoopInfoImpl.h 405externtemplateclassLoopInfoBase<BasicBlock, Loop>;
412void operator=(
constLoopInfo &) =
delete;
421 BaseT::operator=(std::move(
static_cast<BaseT &
>(
RHS)));
425 /// Handle invalidation explicitly. 429// Most of the public interface is provided via LoopInfoBase. 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. 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 445// If both instructions are defined in the same basic block then replacement 446// cannot break LCSSA form. 447if (
I->getParent() ==
From->getParent())
449// If the instruction is not defined in a loop then it can safely replace 451Loop *ToLoop = getLoopFor(
I->getParent());
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. 460 /// Checks if moving a specific instruction can break LCSSA in any loop. 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 467"Can't reason about IPO!");
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). 477auto *OldLoop = getLoopFor(OldBB);
478auto *NewLoop = getLoopFor(NewBB);
480if (OldLoop == NewLoop)
483// Check if Outer contains Inner; with the null loop counting as the 485auto Contains = [](
constLoop *Outer,
constLoop *Inner) {
486return !Outer || Outer->contains(Inner);
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. 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. 496if (!Contains(NewLoop, OldLoop)) {
498auto *UI = cast<Instruction>(U.getUser());
499auto *UBB = isa<PHINode>(UI) ? cast<PHINode>(UI)->getIncomingBlock(U)
501if (UBB != NewBB && getLoopFor(UBB) != NewLoop)
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. 509if (!Contains(OldLoop, NewLoop)) {
510// See below on why we can't handle phi nodes here. 511if (isa<PHINode>(Inst))
515auto *DefI = dyn_cast<Instruction>(U.get());
519// This would need adjustment if we allow Inst to be a phi node -- the 520// new use block won't simply be NewBB. 522auto *DefBlock = DefI->getParent();
523if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop)
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. 535bool wouldBeOutOfLoopUseRequiringLCSSA(
constValue *V,
539/// Enable verification of loop info. 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. 546// Allow clients to walk the list of nested loops... 565/// Analysis pass that exposes the \c LoopInfo for a function. 576/// Printer pass for the \c LoopAnalysis results. 586/// Verifier pass for the \c LoopAnalysis results. 592/// The legacy pass manager's analysis pass to compute loop information. 597staticcharID;
// Pass identification, replacement for typeid 604 /// Calculate the natural loop information for a given function. 607void verifyAnalysis()
const override;
616/// Function to print a loop's contents as LLVM's text IR assembly. 617voidprintLoop(Loop &L, raw_ostream &
OS,
const std::string &Banner =
"");
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. 623/// Find string metadata for a loop. 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. 633/// Returns true if Name is applied to TheLoop and enabled. 636/// Find named metadata for a loop with an integer value. 640/// Find named metadata for a loop with an integer value. Return \p Default if 644/// Find string metadata for loop 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. 652/// Find the convergence heart of the loop. 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. 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) 664/// Return true if this loop can be assumed to run for a finite number of 668/// Return whether an MDNode might represent an access group. 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. 677/// Create a new LoopID after the loop has been transformed. 679/// This can be used when no follow-up loop attributes are defined 680/// (llvm::makeFollowupLoopID returning None) to stop transformations to be 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 689/// @param AddAttrs Add these loop attributes to the new LoopID. 691/// @return A new LoopID that can be applied using Loop::setLoopID(). BlockVerifier::State From
static bool isCanonical(const MDString *S)
static bool runOnFunction(Function &F, bool PostInlining)
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
This header defines various interfaces for pass management in LLVM.
Loop::LoopBounds::Direction Direction
StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Core dominator tree base class.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionPass class - This class is used to implement most global optimizations.
This instruction compares its operands according to the predicate given to the constructor.
const Function * getFunction() const
Return the function this instruction belongs to.
This is an important class for using LLVM in a threaded context.
Analysis pass that exposes the LoopInfo for a function.
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.
const LoopInfo & getLoopInfo() const
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
LoopInfo & operator=(LoopInfo &&RHS)
LoopInfo(const DominatorTreeBase< BasicBlock, false > &DomTree)
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc)
Checks if moving a specific instruction can break LCSSA in any loop.
Printer pass for the LoopAnalysis results.
LoopPrinterPass(raw_ostream &OS)
A range representing the start and end location of a loop.
LocRange(DebugLoc Start, DebugLoc End)
const DebugLoc & getStart() const
const DebugLoc & getEnd() const
Represents a single loop in the control flow graph.
bool isGuarded() const
Return true iff the loop is.
StringRef getName() const
bool isRotatedForm() const
Return true if the loop is in rotated form.
A Module instance is used to store all the information related to an LLVM module.
A set of analyses that are preserved following a run of a transformation pass.
The main scalar evolution driver.
StringRef - Represent a constant reference to a string, i.e.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
iterator_range< use_iterator > uses()
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
This is an optimization pass for GlobalISel generic memory operations.
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.
std::optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)
int getIntLoopAttribute(const Loop *TheLoop, StringRef Name, int Default=0)
Find named metadata for a loop with an integer value.
std::optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for loop.
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
bool hasMustProgress(const Loop *L)
Look for the loop attribute that requires progress within the loop.
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
CallBase * getLoopConvergenceHeart(const Loop *TheLoop)
Find the convergence heart of the loop.
bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
bool VerifyLoopInfo
Enable verification of loop info.
std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
bool isValidAsAccessGroup(MDNode *AccGroup)
Return whether an MDNode might represent an access group.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
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.
@ 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.
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Implement std::hash so that hash_code can be used in STL containers.
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static NodeRef getEntryNode(Loop *L)
LoopInfo::iterator ChildIteratorType
static ChildIteratorType child_begin(NodeRef N)
static ChildIteratorType child_end(NodeRef N)
static ChildIteratorType child_begin(NodeRef N)
static ChildIteratorType child_end(NodeRef N)
static NodeRef getEntryNode(const Loop *L)
LoopInfo::iterator ChildIteratorType
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
Verifier pass for the LoopAnalysis results.
Below are some utilities to get the loop guard, loop bounds and induction variable,...
Direction
An enum for the direction of the loop.
Value & getFinalIVValue() const
Get the final value of the loop induction variable.
Value * getStepValue() const
Get the step that the loop induction variable gets updated by in each loop iteration.
Instruction & getStepInst() const
Get the instruction that updates the loop induction variable.
Value & getInitialIVValue() const
Get the initial value of the loop induction variable.
A CRTP mix-in to automatically provide informational APIs needed for passes.
