This class builds and contains all of the top-level loop structures in the specified function. More...

#include "llvm/Support/GenericLoopInfo.h"

Inheritance diagram for llvm::LoopInfoBase< BlockT, LoopT >:

[legend]

Public Types
typedef std::vector< LoopT * >::const_iterator	iterator
	iterator/begin/end - The interface to the top-level loops in the current function.

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

Public Member Functions
	LoopInfoBase ()=default

	~LoopInfoBase ()

	LoopInfoBase (LoopInfoBase &&Arg)

LoopInfoBase &	operator= (LoopInfoBase &&RHS)

void	releaseMemory ()

template<typename... ArgsTy>
LoopT *	AllocateLoop (ArgsTy &&...Args)

iterator	begin () const

iterator	end () const

reverse_iterator	rbegin () const

reverse_iterator	rend () const

bool	empty () const

SmallVector< LoopT *, 4 >	getLoopsInPreorder () const
	Return all of the loops in the function in preorder across the loop nests, with siblings in forward program order.

SmallVector< LoopT *, 4 >	getLoopsInReverseSiblingPreorder () const
	Return all of the loops in the function in preorder across the loop nests, with siblings in reverse program order.

LoopT *	getLoopFor (const BlockT *BB) const
	Return the inner most loop that BB lives in.

const LoopT *	operator[] (const BlockT *BB) const
	Same as getLoopFor.

unsigned	getLoopDepth (const BlockT *BB) const
	Return the loop nesting level of the specified block.

bool	isLoopHeader (const BlockT *BB) const

const std::vector< LoopT * > &	getTopLevelLoops () const
	Return the top-level loops.

std::vector< LoopT * > &	getTopLevelLoopsVector ()
	Return the top-level loops.

LoopT *	removeLoop (iterator I)
	This removes the specified top-level loop from this loop info object.

void	changeLoopFor (BlockT BB, LoopT L)
	Change the top-level loop that contains BB to the specified loop.

void	changeTopLevelLoop (LoopT OldLoop, LoopT NewLoop)
	Replace the specified loop in the top-level loops list with the indicated loop.

void	addTopLevelLoop (LoopT *New)
	This adds the specified loop to the collection of top-level loops.

void	removeBlock (BlockT *BB)
	This method completely removes BB from all data structures, including all of the Loop objects it is nested in and our mapping from BasicBlocks to loops.

void	analyze (const DominatorTreeBase< BlockT, false > &DomTree)
	Create the loop forest using a stable algorithm.

void	print (raw_ostream &OS) const

void	verify (const DominatorTreeBase< BlockT, false > &DomTree) const

void	destroy (LoopT *L)
	Destroy a loop that has been removed from the `LoopInfo` nest.

Static Public Member Functions
static bool	isNotAlreadyContainedIn (const LoopT SubLoop, const LoopT ParentLoop)

Friends
class	LoopBase< BlockT, LoopT >

class	LoopInfo

Detailed Description

template<class BlockT, class LoopT>
class llvm::LoopInfoBase< BlockT, LoopT >

This class builds and contains all of the top-level loop structures in the specified function.

Definition at line 532 of file GenericLoopInfo.h.

Member Typedef Documentation

◆ iterator

template<class BlockT , class LoopT >

typedef std::vector<LoopT*>::const_iterator llvm::LoopInfoBase< BlockT, LoopT >::iterator

iterator/begin/end - The interface to the top-level loops in the current function.

Definition at line 584 of file GenericLoopInfo.h.

◆ reverse_iterator

template<class BlockT , class LoopT >

typedef std::vector<LoopT*>::const_reverse_iterator llvm::LoopInfoBase< BlockT, LoopT >::reverse_iterator

Definition at line 586 of file GenericLoopInfo.h.

Constructor & Destructor Documentation

◆ LoopInfoBase() [1/2]

template<class BlockT , class LoopT >

llvm::LoopInfoBase< BlockT, LoopT >::LoopInfoBase ( )

default

◆ ~LoopInfoBase()

template<class BlockT , class LoopT >

llvm::LoopInfoBase< BlockT, LoopT >::~LoopInfoBase ( )

inline

Definition at line 546 of file GenericLoopInfo.h.

References llvm::LoopInfoBase< BlockT, LoopT >::releaseMemory().

◆ LoopInfoBase() [2/2]

template<class BlockT , class LoopT >

llvm::LoopInfoBase< BlockT, LoopT >::LoopInfoBase ( LoopInfoBase< BlockT, LoopT > && Arg )

inline

Definition at line 548 of file GenericLoopInfo.h.

Member Function Documentation

◆ addTopLevelLoop()

template<class BlockT , class LoopT >

void llvm::LoopInfoBase< BlockT, LoopT >::addTopLevelLoop ( LoopT * New )

inline

This adds the specified loop to the collection of top-level loops.

Definition at line 669 of file GenericLoopInfo.h.

References assert().

Referenced by llvm::addClonedBlockToLoopInfo(), llvm::MachineLoopInfo::addTopLevelLoop(), buildClonedLoops(), llvm::cloneLoop(), cloneLoopNest(), llvm::cloneLoopWithPreheader(), createNaturalLoopInternal(), llvm::TileInfo::CreateTiledLoops(), llvm::VPRegionBlock::execute(), hoistLoopToNewParent(), llvm::PopulateLoopsDFS< BlockT, LoopT >::insertIntoLoop(), and rebuildLoopAfterUnswitch().

◆ AllocateLoop()

template<class BlockT , class LoopT >

template<typename... ArgsTy>

LoopT * llvm::LoopInfoBase< BlockT, LoopT >::AllocateLoop ( ArgsTy &&... Args )

inline

Definition at line 576 of file GenericLoopInfo.h.

References llvm::BumpPtrAllocatorImpl< AllocatorT, SlabSize, SizeThreshold, GrowthDelay >::Allocate().

Referenced by llvm::addClonedBlockToLoopInfo(), buildClonedLoops(), llvm::cloneLoop(), cloneLoopNest(), llvm::cloneLoopWithPreheader(), createNaturalLoopInternal(), llvm::TileInfo::CreateTiledLoops(), llvm::VPRegionBlock::execute(), and separateNestedLoop().

◆ analyze()

template<class BlockT , class LoopT >

void llvm::LoopInfoBase< BlockT, LoopT >::analyze ( const DominatorTreeBase< BlockT, false > & DomTree )

Create the loop forest using a stable algorithm.

Analyze LoopInfo discovers loops during a postorder DominatorTree traversal interleaved with backward CFG traversals within each subloop (discoverAndMapSubloop).

The backward traversal skips inner subloops, so this part of the algorithm is linear in the number of CFG edges. Subloop and Block vectors are then populated during a single forward CFG traversal (PopulateLoopDFS).

During the two CFG traversals each block is seen three times: 1) Discovered and mapped by a reverse CFG traversal. 2) Visited during a forward DFS CFG traversal. 3) Reverse-inserted in the loop in postorder following forward DFS.

The Block vectors are inclusive, so step 3 requires loop-depth number of insertions per block.

Definition at line 573 of file GenericLoopInfoImpl.h.

References llvm::children(), llvm::discoverAndMapSubloop(), llvm::DominatorTreeBase< NodeT, IsPostDom >::dominates(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getRootNode(), llvm::DominatorTreeBase< NodeT, IsPostDom >::isReachableFromEntry(), llvm::post_order(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::OptimizationRemarkEmitter::OptimizationRemarkEmitter(), llvm::LoopAnalysis::run(), and llvm::LoopInfoBase< BlockT, LoopT >::verify().

◆ begin()

template<class BlockT , class LoopT >

iterator llvm::LoopInfoBase< BlockT, LoopT >::begin ( ) const

inline

Definition at line 587 of file GenericLoopInfo.h.

Referenced by llvm::MachineLoopInfo::begin(), CalculateUnswitchCostMultiplier(), llvm::LoopInfoBase< BlockT, LoopT >::removeLoop(), llvm::LoopFullUnrollPass::run(), and llvm::ScalarEvolution::verify().

◆ changeLoopFor()

template<class BlockT , class LoopT >

void llvm::LoopInfoBase< BlockT, LoopT >::changeLoopFor	(	BlockT *	BB,
		LoopT *	L
	)

inline

Change the top-level loop that contains BB to the specified loop.

This should be used by transformations that restructure the loop hierarchy tree.

Definition at line 650 of file GenericLoopInfo.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase().

Referenced by llvm::MachineLoopInfo::changeLoopFor(), cloneLoopNest(), createNaturalLoopInternal(), hoistLoopToNewParent(), rebuildLoopAfterUnswitch(), and separateNestedLoop().

◆ changeTopLevelLoop()

template<class BlockT , class LoopT >

void llvm::LoopInfoBase< BlockT, LoopT >::changeTopLevelLoop	(	LoopT *	OldLoop,
		LoopT *	NewLoop
	)

inline

Replace the specified loop in the top-level loops list with the indicated loop.

Definition at line 660 of file GenericLoopInfo.h.

References assert(), llvm::find(), and I.

Referenced by llvm::MachineLoopInfo::changeTopLevelLoop(), and separateNestedLoop().

◆ destroy()

template<class BlockT , class LoopT >

void llvm::LoopInfoBase< BlockT, LoopT >::destroy ( LoopT * L )

inline

Destroy a loop that has been removed from the LoopInfo nest.

This runs the destructor of the loop object making it invalid to reference afterward. The memory is retained so that the pointer to the loop remains valid.

The caller is responsible for removing this loop from the loop nest and otherwise disconnecting it from the broader LoopInfo data structures. Callers that don't naturally handle this themselves should probably call ‘erase’ instead.

Definition at line 716 of file GenericLoopInfo.h.

References llvm::BumpPtrAllocatorImpl< AllocatorT, SlabSize, SizeThreshold, GrowthDelay >::Deallocate().

Referenced by deleteDeadBlocksFromLoop(), llvm::deleteDeadLoop(), and rebuildLoopAfterUnswitch().

◆ empty()

template<class BlockT , class LoopT >

bool llvm::LoopInfoBase< BlockT, LoopT >::empty ( ) const

inline

Definition at line 591 of file GenericLoopInfo.h.

Referenced by llvm::MachineLoopInfo::empty(), llvm::FunctionToLoopPassAdaptor::run(), llvm::LoopUnrollPass::run(), llvm::LoopVectorizePass::run(), and llvm::LoopSinkPass::run().

◆ end()

template<class BlockT , class LoopT >

iterator llvm::LoopInfoBase< BlockT, LoopT >::end ( ) const

inline

Definition at line 588 of file GenericLoopInfo.h.

Referenced by CalculateUnswitchCostMultiplier(), llvm::deleteDeadLoop(), llvm::MachineLoopInfo::end(), llvm::LoopInfoBase< BlockT, LoopT >::removeLoop(), llvm::LoopFullUnrollPass::run(), and llvm::ScalarEvolution::verify().

◆ getLoopDepth()

template<class BlockT , class LoopT >

unsigned llvm::LoopInfoBase< BlockT, LoopT >::getLoopDepth ( const BlockT * BB ) const

inline

Return the loop nesting level of the specified block.

A depth of 0 means the block is not inside any loop.

Definition at line 619 of file GenericLoopInfo.h.

References llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor().

Referenced by CompareValueComplexity(), llvm::MachineLoopInfo::getLoopDepth(), rebuildLoopAfterUnswitch(), and runImpl().

◆ getLoopFor()

template<class BlockT , class LoopT >

LoopT * llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor ( const BlockT * BB ) const

inline

Return the inner most loop that BB lives in.

If a basic block is in no loop (for example the entry node), null is returned.

Definition at line 612 of file GenericLoopInfo.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup().

Referenced by llvm::addClonedBlockToLoopInfo(), llvm::IVUsers::AddUsersIfInteresting(), llvm::OpenMPIRBuilder::applySimd(), buildClonedLoops(), canVectorizeLoads(), checkDependencies(), llvm::cloneLoop(), cloneLoopBlocks(), cloneLoopNest(), llvm::cloneLoopWithPreheader(), collectUnswitchCandidates(), collectUnswitchCandidatesWithInjections(), computeHeuristicUnrollFactor(), ConnectProlog(), createNaturalLoopInternal(), llvm::TileInfo::CreateTiledLoops(), llvm::DependenceInfo::depends(), despeculateCountZeros(), llvm::discoverAndMapSubloop(), llvm::VPRegionBlock::execute(), llvm::LoopVectorizationPlanner::executePlan(), llvm::MustBeExecutedContextExplorer::findBackwardJoinPoint(), llvm::MustBeExecutedContextExplorer::findForwardJoinPoint(), llvm::InnerLoopVectorizer::fixVectorizedLoop(), llvm::formLCSSA(), llvm::formLCSSAForInstructions(), getInnermostLoopFor(), getInsertPointForUses(), getIVIncrement(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopDepth(), llvm::MachineLoopInfo::getLoopFor(), getOutermostLoop(), getReductionInstr(), llvm::DependenceInfo::getSplitIteration(), getTopMostExitingLoop(), hoistLoopToNewParent(), injectPendingInvariantConditions(), llvm::PopulateLoopsDFS< BlockT, LoopT >::insertIntoLoop(), inSubLoop(), IsAcceptableTarget(), llvm::ScalarEvolution::isBasicBlockEntryGuardedByCond(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), isIntegerLoopHeaderPHI(), isInteresting(), llvm::LoopInfoBase< BlockT, LoopT >::isLoopHeader(), llvm::isPotentiallyReachable(), llvm::Loop::isRecursivelyLCSSAForm(), isSameUnderlyingObjectInLoop(), mergeBlocksIntoPredecessors(), moveLCSSAPhis(), needToInsertPhisForLCSSA(), oneUseOutsideLoop(), llvm::LoopInfoBase< BlockT, LoopT >::operator[](), llvm::MachineLoopInfo::operator[](), llvm::ScalarEvolution::print(), llvm::LoopBase< BasicBlock, Loop >::print(), rebuildLoopAfterUnswitch(), recomputeLoopBlockSet(), llvm::rewriteLoopExitValues(), llvm::simplifyUsersOfIV(), sinkInstruction(), llvm::InnerLoopVectorizer::sinkScalarOperands(), llvm::SplitBlockAndInsertIfThenElse(), llvm::splitBlockBefore(), SplitBlockImpl(), SplitBlockPredecessorsImpl(), unifyLoopExits(), llvm::UnrollLoop(), llvm::UnrollRuntimeLoopRemainder(), unswitchNontrivialInvariants(), UpdateAnalysisInformation(), and llvm::LoopBlocksTraversal::visitPreorder().

◆ getLoopsInPreorder()

template<class BlockT , class LoopT >

SmallVector< LoopT *, 4 > llvm::LoopInfoBase< BlockT, LoopT >::getLoopsInPreorder

Return all of the loops in the function in preorder across the loop nests, with siblings in forward program order.

Note that because loops form a forest of trees, preorder is equivalent to reverse postorder.

Definition at line 603 of file GenericLoopInfoImpl.h.

Referenced by llvm::LoopSinkPass::run(), runImpl(), AMDGPUDAGToDAGISel::runOnMachineFunction(), and warnAboutLeftoverTransformations().

◆ getLoopsInReverseSiblingPreorder()

template<class BlockT , class LoopT >

SmallVector< LoopT *, 4 > llvm::LoopInfoBase< BlockT, LoopT >::getLoopsInReverseSiblingPreorder

Return all of the loops in the function in preorder across the loop nests, with siblings in reverse program order.

Note that because loops form a forest of trees, preorder is equivalent to reverse postorder.

Also note that this is not a reverse preorder. Only the siblings are in reverse program order.

Definition at line 621 of file GenericLoopInfoImpl.h.

References llvm::SmallVectorImpl< T >::append(), assert(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

◆ getTopLevelLoops()

template<class BlockT , class LoopT >

const std::vector< LoopT * > & llvm::LoopInfoBase< BlockT, LoopT >::getTopLevelLoops ( ) const

inline

Return the top-level loops.

Definition at line 631 of file GenericLoopInfo.h.

◆ getTopLevelLoopsVector()

template<class BlockT , class LoopT >

std::vector< LoopT * > & llvm::LoopInfoBase< BlockT, LoopT >::getTopLevelLoopsVector ( )

inline

Return the top-level loops.

Definition at line 634 of file GenericLoopInfo.h.

◆ isLoopHeader()

template<class BlockT , class LoopT >

bool llvm::LoopInfoBase< BlockT, LoopT >::isLoopHeader ( const BlockT * BB ) const

inline

Definition at line 625 of file GenericLoopInfo.h.

References llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor().

Referenced by canProveExitOnFirstIteration(), llvm::getUnderlyingObjects(), llvm::MachineLoopInfo::isLoopHeader(), makeReducible(), and SplitBlockPredecessorsImpl().

◆ isNotAlreadyContainedIn()

template<class BlockT , class LoopT >

static bool llvm::LoopInfoBase< BlockT, LoopT >::isNotAlreadyContainedIn	(	const LoopT *	SubLoop,
		const LoopT *	ParentLoop
	)

inlinestatic

Definition at line 689 of file GenericLoopInfo.h.

References llvm::LoopInfoBase< BlockT, LoopT >::isNotAlreadyContainedIn().

Referenced by llvm::LoopInfoBase< BlockT, LoopT >::isNotAlreadyContainedIn().

◆ operator=()

template<class BlockT , class LoopT >

LoopInfoBase & llvm::LoopInfoBase< BlockT, LoopT >::operator= ( LoopInfoBase< BlockT, LoopT > && RHS )

inline

Definition at line 555 of file GenericLoopInfo.h.

References RHS.

◆ operator[]()

template<class BlockT , class LoopT >

const LoopT * llvm::LoopInfoBase< BlockT, LoopT >::operator[] ( const BlockT * BB ) const

inline

Same as getLoopFor.

Definition at line 615 of file GenericLoopInfo.h.

References llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor().

◆ print()

template<class BlockT , class LoopT >

void llvm::LoopInfoBase< BlockT, LoopT >::print ( raw_ostream & OS ) const

Definition at line 646 of file GenericLoopInfoImpl.h.

References E, I, OS, and llvm::print().

Referenced by llvm::LoopInfoWrapperPass::print().

◆ rbegin()

template<class BlockT , class LoopT >

reverse_iterator llvm::LoopInfoBase< BlockT, LoopT >::rbegin ( ) const

inline

Definition at line 589 of file GenericLoopInfo.h.

◆ releaseMemory()

template<class BlockT , class LoopT >

void llvm::LoopInfoBase< BlockT, LoopT >::releaseMemory ( )

inline

Definition at line 567 of file GenericLoopInfo.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear(), and llvm::BumpPtrAllocatorImpl< AllocatorT, SlabSize, SizeThreshold, GrowthDelay >::Reset().

Referenced by llvm::LoopInfoWrapperPass::releaseMemory(), llvm::MachineLoopInfo::releaseMemory(), and llvm::LoopInfoBase< BlockT, LoopT >::~LoopInfoBase().

◆ removeBlock()

template<class BlockT , class LoopT >

void llvm::LoopInfoBase< BlockT, LoopT >::removeBlock ( BlockT * BB )

inline

This method completely removes BB from all data structures, including all of the Loop objects it is nested in and our mapping from BasicBlocks to loops.

Definition at line 677 of file GenericLoopInfo.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and I.

Referenced by llvm::deleteDeadLoop(), llvm::MergeBlockIntoPredecessor(), llvm::MachineLoopInfo::removeBlock(), and simplifyOneLoop().

◆ removeLoop()

template<class BlockT , class LoopT >

LoopT * llvm::LoopInfoBase< BlockT, LoopT >::removeLoop ( iterator I )

inline

This removes the specified top-level loop from this loop info object.

The loop is not deleted, as it will presumably be inserted into another loop.

Definition at line 639 of file GenericLoopInfo.h.

References assert(), llvm::LoopInfoBase< BlockT, LoopT >::begin(), llvm::LoopInfoBase< BlockT, LoopT >::end(), and I.

Referenced by llvm::deleteDeadLoop(), rebuildLoopAfterUnswitch(), and llvm::MachineLoopInfo::removeLoop().

◆ rend()

template<class BlockT , class LoopT >

reverse_iterator llvm::LoopInfoBase< BlockT, LoopT >::rend ( ) const

inline

Definition at line 590 of file GenericLoopInfo.h.

◆ verify()

template<class BlockT , class LoopT >

void llvm::LoopInfoBase< BlockT, LoopT >::verify ( const DominatorTreeBase< BlockT, false > & DomTree ) const

Definition at line 715 of file GenericLoopInfoImpl.h.

References llvm::addInnerLoopsToHeadersMap(), llvm::LoopInfoBase< BlockT, LoopT >::analyze(), assert(), llvm::compareLoops(), llvm::dbgs(), E, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), I, llvm_unreachable, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), and Loops.

Referenced by createNaturalLoopInternal(), llvm::hoistRegion(), injectPendingInvariantConditions(), llvm::LoopVerifierPass::run(), llvm::FunctionToLoopPassAdaptor::run(), llvm::LoopBoundSplitPass::run(), turnGuardIntoBranch(), unifyLoopExits(), llvm::UnrollAndJamLoop(), llvm::UnrollLoop(), llvm::UnrollRuntimeLoopRemainder(), unswitchNontrivialInvariants(), and llvm::LoopInfoWrapperPass::verifyAnalysis().

Friends And Related Function Documentation

◆ LoopBase< BlockT, LoopT >

template<class BlockT , class LoopT >

friend class LoopBase< BlockT, LoopT >

friend

Definition at line 536 of file GenericLoopInfo.h.

◆ LoopInfo

template<class BlockT , class LoopT >

friend class LoopInfo

friend

Definition at line 539 of file GenericLoopInfo.h.

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

include/llvm/Support/GenericLoopInfo.h
include/llvm/Support/GenericLoopInfoImpl.h

Public Types

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ iterator

◆ reverse_iterator

Constructor & Destructor Documentation

◆ LoopInfoBase() [1/2]

◆ ~LoopInfoBase()

◆ LoopInfoBase() [2/2]

Member Function Documentation

◆ addTopLevelLoop()

◆ AllocateLoop()

◆ analyze()

◆ begin()

◆ changeLoopFor()

◆ changeTopLevelLoop()

◆ destroy()

◆ empty()

◆ end()

◆ getLoopDepth()

◆ getLoopFor()

◆ getLoopsInPreorder()

◆ getLoopsInReverseSiblingPreorder()

◆ getTopLevelLoops()

◆ getTopLevelLoopsVector()

◆ isLoopHeader()

◆ isNotAlreadyContainedIn()

◆ operator=()

◆ operator[]()

◆ print()

◆ rbegin()

◆ releaseMemory()

◆ removeBlock()

◆ removeLoop()

◆ rend()

◆ verify()

Friends And Related Function Documentation

◆ LoopBase< BlockT, LoopT >

◆ LoopInfo