Go to the documentation of this file.
38 #ifndef LLVM_ANALYSIS_LOOPINFO_H
39 #define LLVM_ANALYSIS_LOOPINFO_H
58 class InductionDescriptor;
63 class MemorySSAUpdater;
64 class ScalarEvolution;
74 template <
class BlockT,
class LoopT>
class LoopBase {
77 std::vector<LoopT *> SubLoops;
80 std::vector<BlockT *> Blocks;
84 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
86 bool IsInvalid =
false;
100 for (
const LoopT *CurLoop = ParentLoop; CurLoop;
101 CurLoop = CurLoop->ParentLoop)
119 const LoopT *L =
static_cast<const LoopT *
>(
this);
120 while (L->ParentLoop)
126 LoopT *L =
static_cast<LoopT *
>(
this);
127 while (L->ParentLoop)
145 return contains(L->getParentLoop());
151 return DenseBlockSet.
count(
BB);
155 template <
class InstT>
bool contains(
const InstT *Inst)
const {
168 typedef typename std::vector<LoopT *>::const_iterator
iterator;
204 return Blocks.size();
217 return DenseBlockSet;
223 return DenseBlockSet;
233 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
245 for (
const auto *Succ : children<const BlockT *>(
BB)) {
263 return std::find(PredBegin, PredEnd,
BB) != PredEnd;
269 unsigned NumBackEdges = 0;
326 typedef std::pair<BlockT *, BlockT *>
Edge;
356 LoopLatches.push_back(Pred);
361 template <
class Type>
365 PreOrderWorklist.
append(L.rbegin(), L.rend());
367 while (!PreOrderWorklist.empty()) {
371 PreOrderWorklist.
append(L->rbegin(), L->rend());
372 PreOrderLoops.push_back(L);
380 const LoopT *CurLoop =
static_cast<const LoopT *
>(
this);
381 PreOrderLoops.push_back(CurLoop);
383 return PreOrderLoops;
387 LoopT *CurLoop =
static_cast<LoopT *
>(
this);
388 PreOrderLoops.push_back(CurLoop);
390 return PreOrderLoops;
414 assert(!NewChild->ParentLoop &&
"NewChild already has a parent!");
415 NewChild->ParentLoop =
static_cast<LoopT *
>(
this);
416 SubLoops.push_back(NewChild);
423 assert(
I != SubLoops.end() &&
"Cannot remove end iterator!");
425 assert(Child->ParentLoop ==
this &&
"Child is not a child of this loop!");
426 SubLoops.erase(SubLoops.begin() + (
I -
begin()));
427 Child->ParentLoop =
nullptr;
442 Blocks.push_back(
BB);
455 Blocks.reserve(
size);
464 for (
unsigned i = 0;; ++
i) {
465 assert(
i != Blocks.size() &&
"Loop does not contain BB!");
466 if (Blocks[
i] ==
BB) {
467 Blocks[
i] = Blocks[0];
480 assert(
I != Blocks.end() &&
"N is not in this list!");
500 unsigned Depth = 0)
const;
509 Blocks.push_back(
BB);
523 for (
auto *SubLoop : SubLoops)
526 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
531 DenseBlockSet.
clear();
532 ParentLoop =
nullptr;
536 template <
class BlockT,
class LoopT>
543 extern template class LoopBase<BasicBlock, Loop>;
565 explicit operator bool()
const {
return Start && End; }
569 bool isLoopInvariant(
const Value *V)
const;
573 bool hasLoopInvariantOperands(
const Instruction *
I)
const;
585 bool makeLoopInvariant(
Value *V,
bool &Changed,
612 PHINode *getCanonicalInductionVariable()
const;
619 bool getIncomingAndBackEdge(
BasicBlock *&Incoming,
668 static std::optional<Loop::LoopBounds>
731 : L(
Loop), InitialIVValue(
I), StepInst(
SI), StepValue(SV),
732 FinalIVValue(
F), SE(SE) {}
737 Value &InitialIVValue;
754 std::optional<LoopBounds> getBounds(ScalarEvolution &SE)
const;
763 PHINode *getInductionVariable(ScalarEvolution &SE)
const;
767 bool getInductionDescriptor(ScalarEvolution &SE,
768 InductionDescriptor &IndDesc)
const;
777 bool isAuxiliaryInductionVariable(PHINode &AuxIndVar,
778 ScalarEvolution &SE)
const;
798 BranchInst *getLoopGuardBranch()
const;
803 bool isGuarded()
const {
return (getLoopGuardBranch() !=
nullptr); }
811 assert(!isInvalid() &&
"Loop not in a valid state!");
813 return Latch && isLoopExiting(Latch);
822 bool isLCSSAForm(
const DominatorTree &DT,
bool IgnoreTokens =
true)
const;
828 bool IgnoreTokens =
true)
const;
832 bool isLoopSimplifyForm()
const;
835 bool isSafeToClone()
const;
849 bool isAnnotatedParallel()
const;
857 MDNode *getLoopID()
const;
865 void setLoopID(
MDNode *LoopID)
const;
873 void setLoopAlreadyUnrolled();
876 void setLoopMustProgress();
879 void dumpVerbose()
const;
889 LocRange getLocRange()
const;
893 if (Header->hasName())
894 return Header->getName();
895 return "<unnamed loop>";
912 template <
class BlockT,
class LoopT>
class LoopInfoBase {
914 DenseMap<const BlockT *, LoopT *> BBMap;
915 std::vector<LoopT *> TopLevelLoops;
933 Arg.TopLevelLoops.clear();
938 for (
auto *L : TopLevelLoops)
943 RHS.TopLevelLoops.clear();
950 for (
auto *L : TopLevelLoops)
952 TopLevelLoops.clear();
953 LoopAllocator.Reset();
957 LoopT *Storage = LoopAllocator.Allocate<LoopT>();
958 return new (Storage) LoopT(std::forward<ArgsTy>(
Args)...);
964 typedef typename std::vector<LoopT *>::const_iterator
iterator;
971 bool empty()
const {
return TopLevelLoops.empty(); }
1000 const LoopT *L = getLoopFor(
BB);
1001 return L ? L->getLoopDepth() : 0;
1006 const LoopT *L = getLoopFor(
BB);
1007 return L && L->getHeader() ==
BB;
1020 assert(
I !=
end() &&
"Cannot remove end iterator!");
1022 assert(L->isOutermost() &&
"Not a top-level loop!");
1023 TopLevelLoops.erase(TopLevelLoops.begin() + (
I -
begin()));
1041 auto I =
find(TopLevelLoops, OldLoop);
1042 assert(
I != TopLevelLoops.end() &&
"Old loop not at top level!");
1044 assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
1045 "Loops already embedded into a subloop!");
1050 assert(New->isOutermost() &&
"Loop already in subloop!");
1051 TopLevelLoops.push_back(New);
1058 auto I = BBMap.find(
BB);
1059 if (
I != BBMap.end()) {
1060 for (LoopT *L =
I->second; L; L = L->getParentLoop())
1061 L->removeBlockFromLoop(
BB);
1070 const LoopT *ParentLoop) {
1073 if (SubLoop == ParentLoop)
1075 return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
1101 LoopAllocator.Deallocate(L);
1106 extern template class LoopInfoBase<BasicBlock, Loop>;
1113 void operator=(
const LoopInfo &) =
delete;
1136 void erase(
Loop *L);
1148 if (
I->getParent() ==
From->getParent())
1152 Loop *ToLoop = getLoopFor(
I->getParent());
1158 return ToLoop->
contains(getLoopFor(
From->getParent()));
1168 "Can't reason about IPO!");
1178 auto *OldLoop = getLoopFor(OldBB);
1179 auto *NewLoop = getLoopFor(NewBB);
1181 if (OldLoop == NewLoop)
1186 auto Contains = [](
const Loop *Outer,
const Loop *Inner) {
1187 return !Outer || Outer->contains(Inner);
1197 if (!Contains(NewLoop, OldLoop)) {
1199 auto *UI = cast<Instruction>(U.getUser());
1200 auto *UBB = isa<PHINode>(UI) ? cast<PHINode>(UI)->getIncomingBlock(U)
1202 if (UBB != NewBB && getLoopFor(UBB) != NewLoop)
1210 if (!Contains(OldLoop, NewLoop)) {
1212 if (isa<PHINode>(Inst))
1216 auto *DefI = dyn_cast<Instruction>(U.get());
1223 auto *DefBlock = DefI->getParent();
1224 if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop)
1236 bool wouldBeOutOfLoopUseRequiringLCSSA(
const Value *V,
1307 void verifyAnalysis()
const override;
1317 void printLoop(Loop &L, raw_ostream &OS,
const std::string &Banner =
"");
A set of analyses that are preserved following a run of a transformation pass.
reverse_iterator rend() const
RTTIExtends< ObjectLinkingLayer, ObjectLayer > BaseT
bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc)
Checks if moving a specific instruction can break LCSSA in any loop.
bool contains(const BlockT *BB) const
Return true if the specified basic block is in this loop.
const DebugLoc & getEnd() const
static ChildIteratorType child_begin(NodeRef N)
This is an optimization pass for GlobalISel generic memory operations.
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
std::pair< BlockT *, BlockT * > Edge
Edge type.
Value & getFinalIVValue() const
Get the final value of the loop induction variable.
const LoopT * getOutermostLoop() const
Get the outermost loop in which this loop is contained.
Represents a single loop in the control flow graph.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
std::vector< LoopT * >::const_reverse_iterator reverse_iterator
Instances of this class are used to represent loops that are detected in the flow graph.
static NodeRef getEntryNode(Loop *L)
bool VerifyLoopInfo
Enable verification of loop info.
The main scalar evolution driver.
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
int getIntLoopAttribute(const Loop *TheLoop, StringRef Name, int Default=0)
Find named metadata for a loop with an integer value.
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
const_iterator end(StringRef path)
Get end iterator over path.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
The legacy pass manager's analysis pass to compute loop information.
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool isLoopLatch(const BlockT *BB) const
bool contains(const InstT *Inst) const
Return true if the specified instruction is in this loop.
std::vector< LoopT * > & getTopLevelLoopsVector()
Return the top-level loops.
const_pointer const_iterator
static ChildIteratorType child_begin(NodeRef N)
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
block_iterator block_end() const
LLVM Basic Block Representation.
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.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
const std::vector< LoopT * > & getSubLoops() const
Return the loops contained entirely within this loop.
void getLoopLatches(SmallVectorImpl< BlockT * > &LoopLatches) const
Return all loop latch blocks of this loop.
void reverseBlock(unsigned from)
interface to reverse Blocks[from, end of loop] in this loop
static bool isNotAlreadyContainedIn(const LoopT *SubLoop, const LoopT *ParentLoop)
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Represent the analysis usage information of a pass.
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
iterator_range< block_iterator > blocks() const
void destroy(LoopT *L)
Destroy a loop that has been removed from the LoopInfo nest.
iterator_range< use_iterator > uses()
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner="")
Function to print a loop's contents as LLVM's text IR assembly.
LoopInfoBase & operator=(LoopInfoBase &&RHS)
void verifyLoop() const
Verify loop structure.
std::pair< NodeId, LaneBitmask > NodeRef
This class implements an extremely fast bulk output stream that can only output to a stream.
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
SmallVector< const LoopT *, 4 > getLoopsInPreorder() const
Return all loops in the loop nest rooted by the loop in preorder, with siblings in forward program or...
void verifyLoopNest(DenseSet< const LoopT * > *Loops) const
Verify loop structure of this loop and all nested loops.
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
API to communicate dependencies between analyses during invalidation.
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
void removeBlockFromLoop(BlockT *BB)
This removes the specified basic block from the current loop, updating the Blocks as appropriate.
StringRef getName() const
LoopT * removeChildLoop(LoopT *Child)
This removes the specified child from being a subloop of this loop.
Direction
An enum for the direction of the loop.
static ChildIteratorType child_end(NodeRef N)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
LoopT * AllocateLoop(ArgsTy &&... Args)
Verifier pass for the LoopAnalysis results.
block_iterator block_begin() const
const LoopInfo & getLoopInfo() const
Implements a dense probed hash-table based set.
ArrayRef< BlockT * >::const_iterator block_iterator
bool isGuarded() const
Return true iff the loop is.
This instruction compares its operands according to the predicate given to the constructor.
void moveToHeader(BlockT *BB)
This method is used to move BB (which must be part of this loop) to be the loop header of the loop (t...
void setParentLoop(LoopT *L)
This is a raw interface for bypassing addChildLoop.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
#define LLVM_EXTERNAL_VISIBILITY
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
std::optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for loop.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
SmallVector< LoopT *, 4 > getLoopsInPreorder()
This is an important class for using LLVM in a threaded context.
A special type used by analysis passes to provide an address that identifies that particular analysis...
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Instruction & getStepInst() const
Get the instruction that updates the loop induction variable.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
A range representing the start and end location of a loop.
static void getInnerLoopsInPreorder(const LoopT &L, SmallVectorImpl< Type > &PreOrderLoops)
Return all inner loops in the loop nest rooted by the loop in preorder, with siblings in forward prog...
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isFinite(const Loop *L)
Return true if this loop can be assumed to run for a finite number of iterations.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
unsigned getLoopDepth() const
Return the nesting level of this loop.
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
std::vector< BlockT * > & getBlocksVector()
Return a direct, mutable handle to the blocks vector so that we can mutate it efficiently with techni...
A Module instance is used to store all the information related to an LLVM module.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
LoopInfoBase(LoopInfoBase &&Arg)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
std::vector< LoopT * > & getSubLoopsVector()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
StringRef - Represent a constant reference to a string, i.e.
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
void reserveBlocks(unsigned size)
interface to do reserve() for Blocks
const Function * getFunction() const
Return the function this instruction belongs to.
void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild)
This is used when splitting loops up.
Core dominator tree base class.
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
LoopBase()
This creates an empty loop.
void getUniqueNonLatchExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop except successors from Latch block are not considered...
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
LoopInfo::iterator ChildIteratorType
const DebugLoc & getStart() const
std::optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)
static bool runOnFunction(Function &F, bool PostInlining)
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
LoopInfo::iterator ChildIteratorType
bool isLoopHeader(const BlockT *BB) const
Below are some utilities to get the loop guard, loop bounds and induction variable,...
bool isValidAsAccessGroup(MDNode *AccGroup)
Return whether an MDNode might represent an access group.
const SmallPtrSetImpl< const BlockT * > & getBlocksSet() const
Return a direct, immutable handle to the blocks set.
static ChildIteratorType child_end(NodeRef N)
const LoopT * operator[](const BlockT *BB) const
Same as getLoopFor.
Value & getInitialIVValue() const
Get the initial value of the loop induction variable.
This class builds and contains all of the top-level loop structures in the specified function.
SmallPtrSetImpl< const BlockT * > & getBlocksSet()
Return a direct, mutable handle to the blocks set so that we can mutate it efficiently.
bool isInvalid() const
Return true if this loop is no longer valid.
Loop::LoopBounds::Direction Direction
reverse_iterator rbegin() const
BlockT * getHeader() const
bool isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
LoopT * getOutermostLoop()
Printer pass for the LoopAnalysis results.
std::vector< LoopT * >::const_reverse_iterator reverse_iterator
void addBlockEntry(BlockT *BB)
This adds a basic block directly to the basic block list.
unsigned getNumBackEdges() const
Calculate the number of back edges to the loop header.
bool hasNoExitBlocks() const
Return true if this loop does not have any exit blocks.
LoopPrinterPass(raw_ostream &OS)
reverse_iterator rend() const
bool hasMustProgress(const Loop *L)
Look for the loop attribute that requires progress within the loop.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
std::vector< LoopT * >::const_iterator iterator
void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop)
Replace the specified loop in the top-level loops list with the indicated loop.
bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)
Returns true if Name is applied to TheLoop and enabled.
const BasicBlock * getParent() const
reverse_iterator rbegin() const
A range adaptor for a pair of iterators.
std::vector< LoopT * >::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
auto reverse(ContainerTy &&C)
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
void print(raw_ostream &OS, bool Verbose=false, bool PrintNested=true, unsigned Depth=0) const
Print loop with all the BBs inside it.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
static NodeRef getEntryNode(const Loop *L)
BlockVerifier::State From
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
bool isRotatedForm() const
Return true if the loop is in rotated form.
LocRange(DebugLoc Start, DebugLoc End)
const typedef Loop * NodeRef
Value * getStepValue() const
Get the step that the loop induction variable gets updated by in each loop iteration.
LLVM Value Representation.
const std::vector< LoopT * > & getTopLevelLoops() const
Return the top-level loops.
LoopInfo & operator=(LoopInfo &&RHS)
Analysis pass that exposes the LoopInfo for a function.
A Use represents the edge between a Value definition and its users.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.