LLVM: llvm::Loop Class Reference (original) (raw)

Represents a single loop in the control flow graph. More...

#include "[llvm/Analysis/LoopInfo.h](LoopInfo%5F8h%5Fsource.html)"

Classes
class	LocRange
	A range representing the start and end location of a loop. More...

struct	LoopBounds
	Below are some utilities to get the loop guard, loop bounds and induction variable, and to check if a given phinode is an auxiliary induction variable, if the loop is guarded, and if the loop is canonical. More...

Public Member Functions
bool	isLoopInvariant (const Value *V) const
	Return true if the specified value is loop invariant.

bool	hasLoopInvariantOperands (const Instruction *I) const
	Return true if all the operands of the specified instruction are loop invariant.

bool	makeLoopInvariant (Value V, bool &Changed, Instruction InsertPt=nullptr, MemorySSAUpdater MSSAU=nullptr, ScalarEvolution SE=nullptr) const
	If the given value is an instruction inside of the loop and it can be hoisted, do so to make it trivially loop-invariant.

bool	makeLoopInvariant (Instruction I, bool &Changed, Instruction InsertPt=nullptr, MemorySSAUpdater MSSAU=nullptr, ScalarEvolution SE=nullptr) const
	If the given instruction is inside of the loop and it can be hoisted, do so to make it trivially loop-invariant.

PHINode *	getCanonicalInductionVariable () const
	Check to see if the loop has a canonical induction variable: an integer recurrence that starts at 0 and increments by one each time through the loop.

ICmpInst *	getLatchCmpInst () const
	Get the latch condition instruction.

bool	getIncomingAndBackEdge (BasicBlock &Incoming, BasicBlock &Backedge) const
	Obtain the unique incoming and back edge.

std::optional< LoopBounds >	getBounds (ScalarEvolution &SE) const
	Return the struct LoopBounds collected if all struct members are found, else std::nullopt.

PHINode *	getInductionVariable (ScalarEvolution &SE) const
	Return the loop induction variable if found, else return nullptr.

bool	getInductionDescriptor (ScalarEvolution &SE, InductionDescriptor &IndDesc) const
	Get the loop induction descriptor for the loop induction variable.

bool	isAuxiliaryInductionVariable (PHINode &AuxIndVar, ScalarEvolution &SE) const
	Return true if the given PHINode AuxIndVar is.

BranchInst *	getLoopGuardBranch () const
	Return the loop guard branch, if it exists.

bool	isGuarded () const
	Return true iff the loop is.

bool	isRotatedForm () const
	Return true if the loop is in rotated form.

bool	isCanonical (ScalarEvolution &SE) const
	Return true if the loop induction variable starts at zero and increments by one each time through the loop.

bool	isLCSSAForm (const DominatorTree &DT, bool IgnoreTokens=true) const
	Return true if the Loop is in LCSSA form.

bool	isRecursivelyLCSSAForm (const DominatorTree &DT, const LoopInfo &LI, bool IgnoreTokens=true) const
	Return true if this Loop and all inner subloops are in LCSSA form.

bool	isLoopSimplifyForm () const
	Return true if the Loop is in the form that the LoopSimplify form transforms loops to, which is sometimes called normal form.

bool	isSafeToClone () const
	Return true if the loop body is safe to clone in practice.

bool	isAnnotatedParallel () const
	Returns true if the loop is annotated parallel.

MDNode *	getLoopID () const
	Return the llvm.loop loop id metadata node for this loop if it is present.

void	setLoopID (MDNode *LoopID) const
	Set the llvm.loop loop id metadata for this loop.

void	setLoopAlreadyUnrolled ()
	Add llvm.loop.unroll.disable to this loop's loop id metadata.

void	setLoopMustProgress ()
	Add llvm.loop.mustprogress to this loop's loop id metadata.

void	dump () const

void	dumpVerbose () const

DebugLoc	getStartLoc () const
	Return the debug location of the start of this loop.

LocRange	getLocRange () const
	Return the source code span of the loop.

std::string	getLocStr () const
	Return a string containing the debug location of the loop (file name + line number if present, otherwise module name).

StringRef	getName () const

Public Member Functions inherited from llvm::LoopBase< BasicBlock, Loop >
unsigned	getLoopDepth () const
	Return the nesting level of this loop.

BasicBlock *	getHeader () const

Loop *	getParentLoop () const
	Return the parent loop if it exists or nullptr for top level loops.

const Loop *	getOutermostLoop () const
	Get the outermost loop in which this loop is contained.

Loop *	getOutermostLoop ()

void	setParentLoop (Loop *L)
	This is a raw interface for bypassing addChildLoop.

bool	contains (const Loop *L) const
	Return true if the specified loop is contained within in this loop.

bool	contains (const BasicBlock *BB) const
	Return true if the specified basic block is in this loop.

bool	contains (const InstT *Inst) const
	Return true if the specified instruction is in this loop.

const std::vector< Loop * > &	getSubLoops () const
	Return the loops contained entirely within this loop.

std::vector< Loop * > &	getSubLoopsVector ()

iterator	begin () const

iterator	end () const

reverse_iterator	rbegin () const

reverse_iterator	rend () const

bool	isInnermost () const
	Return true if the loop does not contain any (natural) loops.

bool	isOutermost () const
	Return true if the loop does not have a parent (natural) loop.

ArrayRef< BasicBlock * >	getBlocks () const
	Get a list of the basic blocks which make up this loop.

block_iterator	block_begin () const

block_iterator	block_end () const

iterator_range< block_iterator >	blocks () const

unsigned	getNumBlocks () const
	Get the number of blocks in this loop in constant time.

std::vector< BasicBlock * > &	getBlocksVector ()
	Return a direct, mutable handle to the blocks vector so that we can mutate it efficiently with techniques like std::remove.

SmallPtrSetImpl< const BasicBlock * > &	getBlocksSet ()
	Return a direct, mutable handle to the blocks set so that we can mutate it efficiently.

const SmallPtrSetImpl< const BasicBlock * > &	getBlocksSet () const
	Return a direct, immutable handle to the blocks set.

bool	isInvalid () const
	Return true if this loop is no longer valid.

bool	isLoopExiting (const BasicBlock *BB) const
	True if terminator in the block can branch to another block that is outside of the current loop.

bool	isLoopLatch (const BasicBlock *BB) const

unsigned	getNumBackEdges () const
	Calculate the number of back edges to the loop header.

void	getExitingBlocks (SmallVectorImpl< BasicBlock * > &ExitingBlocks) const
	Return all blocks inside the loop that have successors outside of the loop.

BasicBlock *	getExitingBlock () const
	If getExitingBlocks would return exactly one block, return that block.

void	getExitBlocks (SmallVectorImpl< BasicBlock * > &ExitBlocks) const
	Return all of the successor blocks of this loop.

BasicBlock *	getExitBlock () const
	If getExitBlocks would return exactly one block, return that block.

bool	hasDedicatedExits () const
	Return true if no exit block for the loop has a predecessor that is outside the loop.

void	getUniqueExitBlocks (SmallVectorImpl< BasicBlock * > &ExitBlocks) const
	Return all unique successor blocks of this loop.

void	getUniqueNonLatchExitBlocks (SmallVectorImpl< BasicBlock * > &ExitBlocks) const
	Return all unique successor blocks of this loop except successors from Latch block are not considered.

BasicBlock *	getUniqueExitBlock () const
	If getUniqueExitBlocks would return exactly one block, return that block.

BasicBlock *	getUniqueLatchExitBlock () const
	Return the unique exit block for the latch, or null if there are multiple different exit blocks or the latch is not exiting.

bool	hasNoExitBlocks () const
	Return true if this loop does not have any exit blocks.

void	getExitEdges (SmallVectorImpl< Edge > &ExitEdges) const
	Return all pairs of (inside_block,outside_block).

BasicBlock *	getLoopPreheader () const
	If there is a preheader for this loop, return it.

BasicBlock *	getLoopPredecessor () const
	If the given loop's header has exactly one unique predecessor outside the loop, return it.

BasicBlock *	getLoopLatch () const
	If there is a single latch block for this loop, return it.

void	getLoopLatches (SmallVectorImpl< BasicBlock * > &LoopLatches) const
	Return all loop latch blocks of this loop.

SmallVector< const Loop *, 4 >	getLoopsInPreorder () const
	Return all loops in the loop nest rooted by the loop in preorder, with siblings in forward program order.

SmallVector< Loop *, 4 >	getLoopsInPreorder ()

void	addBasicBlockToLoop (BasicBlock *NewBB, LoopInfoBase< BasicBlock, Loop > &LI)
	This method is used by other analyses to update loop information.

void	replaceChildLoopWith (Loop OldChild, Loop NewChild)
	This is used when splitting loops up.

void	addChildLoop (Loop *NewChild)
	Add the specified loop to be a child of this loop.

Loop *	removeChildLoop (iterator I)
	This removes the specified child from being a subloop of this loop.

Loop *	removeChildLoop (Loop *Child)
	This removes the specified child from being a subloop of this loop.

void	addBlockEntry (BasicBlock *BB)
	This adds a basic block directly to the basic block list.

void	reverseBlock (unsigned from)
	interface to reverse Blocks[from, end of loop] in this loop

void	reserveBlocks (unsigned size)
	interface to do reserve() for Blocks

void	moveToHeader (BasicBlock *BB)
	This method is used to move BB (which must be part of this loop) to be the loop header of the loop (the block that dominates all others).

void	removeBlockFromLoop (BasicBlock *BB)
	This removes the specified basic block from the current loop, updating the Blocks as appropriate.

void	verifyLoop () const
	Verify loop structure.

void	verifyLoopNest (DenseSet< const Loop * > *Loops) const
	Verify loop structure of this loop and all nested loops.

bool	isAnnotatedParallel () const
	Returns true if the loop is annotated parallel.

void	print (raw_ostream &OS, bool Verbose=false, bool PrintNested=true, unsigned Depth=0) const
	Print loop with all the BBs inside it.

Additional Inherited Members
Public Types inherited from llvm::LoopBase< BasicBlock, Loop >
typedef std::vector< Loop * >::const_iterator	iterator

typedef std::vector< Loop * >::const_reverse_iterator	reverse_iterator

typedef ArrayRef< BasicBlock * >::const_iterator	block_iterator

typedef std::pair< BasicBlock , BasicBlock >	Edge
	Edge type.

Static Public Member Functions inherited from llvm::LoopBase< BasicBlock, Loop >
static void	getInnerLoopsInPreorder (const Loop &L, SmallVectorImpl< Type > &PreOrderLoops)
	Return all inner loops in the loop nest rooted by the loop in preorder, with siblings in forward program order.

Protected Member Functions inherited from llvm::LoopBase< BasicBlock, Loop >
	LoopBase ()
	This creates an empty loop.

	LoopBase (BasicBlock *BB)

	~LoopBase ()

Represents a single loop in the control flow graph.

Note that not all SCCs in the CFG are necessarily loops.

Definition at line 39 of file LoopInfo.h.

◆ dump()

◆ dumpVerbose()

◆ getBounds()

◆ getCanonicalInductionVariable()

PHINode * Loop::getCanonicalInductionVariable	(	)	const

◆ getIncomingAndBackEdge()

◆ getInductionDescriptor()

◆ getInductionVariable()

Return the loop induction variable if found, else return nullptr.

An instruction is considered as the loop induction variable if

it is an induction variable of the loop; and
it is used to determine the condition of the branch in the loop latch

Note: the induction variable doesn't need to be canonical, i.e. starts at zero and increments by one each time through the loop (but it can be).

Definition at line 295 of file LoopInfo.cpp.

References assert(), llvm::LoopBase< BasicBlock, Loop >::getHeader(), getLatchCmpInst(), llvm::LoopBase< BasicBlock, Loop >::getLoopLatch(), llvm::User::getOperand(), llvm::InductionDescriptor::isInductionPHI(), and isLoopSimplifyForm().

Referenced by getBounds(), and getInductionDescriptor().

◆ getLatchCmpInst()

ICmpInst * Loop::getLatchCmpInst	(	)	const

◆ getLocRange()

◆ getLocStr()

std::string Loop::getLocStr	(	)	const

◆ getLoopGuardBranch()

Return the loop guard branch, if it exists.

This currently only works on simplified loop, as it requires a preheader and a latch to identify the guard. It will work on loops of the form:

GuardBB:

br cond1, Preheader, ExitSucc <== GuardBranch

Preheader:

br Header

Header:

...

br Latch

Latch:

br cond2, Header, ExitBlock

ExitBlock:

br ExitSucc

ExitSucc:

Definition at line 368 of file LoopInfo.cpp.

References assert(), llvm::LoopBase< BasicBlock, Loop >::getLoopLatch(), llvm::LoopBase< BasicBlock, Loop >::getLoopPreheader(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::LoopBase< BasicBlock, Loop >::getUniqueExitBlock(), llvm::BasicBlock::getUniquePredecessor(), isLoopSimplifyForm(), isRotatedForm(), llvm::BranchInst::isUnconditional(), and llvm::LoopNest::skipEmptyBlockUntil().

Referenced by getInnerLoopGuardCmp().

◆ getLoopID()

MDNode * Loop::getLoopID	(	)	const

Return the llvm.loop loop id metadata node for this loop if it is present.

If this loop contains the same llvm.loop metadata on each branch to the header then the node is returned. If any latch instruction does not contain llvm.loop or if multiple latches contain different nodes then 0 is returned.

Definition at line 502 of file LoopInfo.cpp.

References llvm::LoopBase< BasicBlock, Loop >::getLoopLatches(), llvm::Instruction::getMetadata(), llvm::MDNode::getNumOperands(), and llvm::MDNode::getOperand().

Referenced by llvm::addStringMetadataToLoop(), CloneLoopBlocks(), llvm::LoopVectorizationPlanner::executePlan(), llvm::findOptionMDForLoop(), getLocRange(), isAnnotatedParallel(), llvm::LoopVectorizeHints::setAlreadyVectorized(), setLoopAlreadyUnrolled(), setLoopMustProgress(), and tryToUnrollAndJamLoop().

◆ getName()

StringRef llvm::Loop::getName ( ) const	inline

◆ getStartLoc()

◆ hasLoopInvariantOperands()

◆ isAnnotatedParallel()

bool Loop::isAnnotatedParallel	(	)	const

Returns true if the loop is annotated parallel.

A parallel loop can be assumed to not contain any dependencies between iterations by the compiler. That is, any loop-carried dependency checking can be skipped completely when parallelizing the loop on the target machine. Thus, if the parallel loop information originates from the programmer, e.g. via the OpenMP parallel for pragma, it is the programmer's responsibility to ensure there are no loop-carried dependencies. The final execution order of the instructions across iterations is not guaranteed, thus, the end result might or might not implement actual concurrent execution of instructions across multiple iterations.

Definition at line 565 of file LoopInfo.cpp.

References assert(), llvm::LoopBase< BasicBlock, Loop >::blocks(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::drop_begin(), llvm::findOptionMDForLoop(), getLoopID(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::is_contained(), llvm::isValidAsAccessGroup(), and llvm::MDNode::operands().

◆ isAuxiliaryInductionVariable()

Return true if the given PHINode AuxIndVar is.

in the loop header
not used outside of the loop
incremented by a loop invariant step for each loop iteration
step instruction opcode should be add or sub Note: auxiliary induction variable is not required to be used in the conditional branch in the loop latch. (but it can be)

Definition at line 342 of file LoopInfo.cpp.

References llvm::LoopBase< BasicBlock, Loop >::contains(), llvm::LoopBase< BasicBlock, Loop >::getHeader(), llvm::InductionDescriptor::getInductionOpcode(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::InductionDescriptor::getStep(), I, llvm::InductionDescriptor::isInductionPHI(), llvm::ScalarEvolution::isLoopInvariant(), and llvm::Value::users().

◆ isCanonical()

◆ isGuarded()

bool llvm::Loop::isGuarded ( ) const	inline

Return true iff the loop is.

in simplify rotated form, and
guarded by a loop guard branch.

Definition at line 295 of file LoopInfo.h.

◆ isLCSSAForm()

◆ isLoopInvariant()

Return true if the specified value is loop invariant.

Definition at line 61 of file LoopInfo.cpp.

References llvm::LoopBase< BasicBlock, Loop >::contains(), and I.

Referenced by llvm::canSinkOrHoistInst(), detectShiftUntilBitTestIdiom(), llvm::findHistogram(), llvm::LoopVectorizationCostModel::getReductionPatternCost(), llvm::hoistRegion(), llvm::RecurrenceDescriptor::isAnyOfPattern(), llvm::LoopVectorizationCostModel::isPredicatedInst(), isSafeToExecuteUnconditionally(), llvm::isUniformLoop(), makeLoopInvariant(), and llvm::LoopVectorizationCostModel::setCostBasedWideningDecision().

◆ isLoopSimplifyForm()

bool Loop::isLoopSimplifyForm	(	)	const

Return true if the Loop is in the form that the LoopSimplify form transforms loops to, which is sometimes called normal form.

Definition at line 480 of file LoopInfo.cpp.

References llvm::LoopBase< BasicBlock, Loop >::getLoopLatch(), llvm::LoopBase< BasicBlock, Loop >::getLoopPreheader(), and llvm::LoopBase< BasicBlock, Loop >::hasDedicatedExits().

Referenced by checkLoopsStructure(), getInductionVariable(), getLoopGuardBranch(), llvm::UnrollAndJamLoop(), and llvm::LoopVersioning::versionLoop().

◆ isRecursivelyLCSSAForm()

◆ isRotatedForm()

bool llvm::Loop::isRotatedForm ( ) const	inline

Return true if the loop is in rotated form.

This does not check if the loop was rotated by loop rotation, instead it only checks if the loop is in rotated form (has a valid latch that exists the loop).

Definition at line 302 of file LoopInfo.h.

References assert().

Referenced by getLoopGuardBranch().

◆ isSafeToClone()

bool Loop::isSafeToClone	(	)	const

◆ makeLoopInvariant() [1/2]

If the given instruction is inside of the loop and it can be hoisted, do so to make it trivially loop-invariant.

Return true if I is already loop-invariant, and false if I can't be made loop-invariant. If I is made loop-invariant, Changed is set to true. This function can be used as a slightly more aggressive replacement for isLoopInvariant.

If InsertPt is specified, it is the point to hoist instructions to. If null, the terminator of the loop preheader is used.

Definition at line 79 of file LoopInfo.cpp.

References llvm::MemorySSA::BeforeTerminator, llvm::ScalarEvolution::forgetBlockAndLoopDispositions(), llvm::LoopBase< BasicBlock, Loop >::getLoopPreheader(), llvm::MemorySSA::getMemoryAccess(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getTerminator(), I, isLoopInvariant(), llvm::isSafeToSpeculativelyExecute(), makeLoopInvariant(), and llvm::MemorySSAUpdater::moveToPlace().

◆ makeLoopInvariant() [2/2]

If the given value is an instruction inside of the loop and it can be hoisted, do so to make it trivially loop-invariant.

Return true if V is already loop-invariant, and false if V can't be made loop-invariant. If V is made loop-invariant, Changed is set to true. This function can be used as a slightly more aggressive replacement for isLoopInvariant.

If InsertPt is specified, it is the point to hoist instructions to. If null, the terminator of the loop preheader is used.

Definition at line 71 of file LoopInfo.cpp.

References I, and makeLoopInvariant().

Referenced by makeLoopInvariant().

◆ setLoopAlreadyUnrolled()

void Loop::setLoopAlreadyUnrolled	(	)

◆ setLoopID()

void Loop::setLoopID	(	MDNode *	LoopID	)	const

Set the llvm.loop loop id metadata for this loop.

The LoopID metadata node will be added to each terminator instruction in the loop that branches to the loop header.

The LoopID metadata node should have one or more operands and the first operand should be the node itself.

Definition at line 526 of file LoopInfo.cpp.

References assert(), llvm::LoopBase< BasicBlock, Loop >::getLoopLatches(), llvm::MDNode::getNumOperands(), and llvm::MDNode::getOperand().

Referenced by llvm::addStringMetadataToLoop(), CloneLoopBlocks(), llvm::LoopVectorizeHints::setAlreadyVectorized(), setLoopAlreadyUnrolled(), setLoopMustProgress(), tryToUnrollAndJamLoop(), and tryToUnrollLoop().

◆ setLoopMustProgress()

void Loop::setLoopMustProgress	(	)

◆ LoopBase< BasicBlock, Loop >

◆ LoopInfoBase< BasicBlock, Loop >

The documentation for this class was generated from the following files:

include/llvm/Analysis/LoopInfo.h
lib/Analysis/LoopInfo.cpp