Cycle information for a function. More...

#include "llvm/ADT/GenericCycleInfo.h"

Inheritance diagram for llvm::GenericCycleInfo< ContextT >:

Classes
struct	const_child_iterator
	Iteration over child cycles, yielding handles. More...

Public Types
using	BlockT = typename ContextT::BlockT
using	FunctionT = typename ContextT::FunctionT
using	const_toplevel_iterator = const_child_iterator
	Iteration over top-level cycles.

Public Member Functions
	GenericCycleInfo ()=default
	GenericCycleInfo (GenericCycleInfo &&)=default
GenericCycleInfo &	operator= (GenericCycleInfo &&)=default
void	clear ()
	Reset the object to its initial state.
void	compute (FunctionT &F)
	Compute the cycle info for a function.
void	splitCriticalEdge (BlockT Pred, BlockT Succ, BlockT *New)
const FunctionT *	getFunction () const
const ContextT &	getSSAContext () const
auto	cycles () const
	All cycles in forest preorder.
CycleRef	getCycle (const BlockT *Block) const
	Find the innermost cycle containing `Block`.
BlockT *	getHeader (CycleRef C) const
bool	isReducible (CycleRef C) const
CycleRef	getParentCycle (CycleRef C) const
unsigned	getDepth (CycleRef C) const
size_t	getNumBlocks (CycleRef C) const
ArrayRef< BlockT * >	getEntries (CycleRef C) const
bool	isEntry (CycleRef C, const BlockT *Block) const
void	setSingleEntry (CycleRef C, BlockT *Block)
bool	contains (CycleRef Outer, CycleRef Inner) const
	Returns true iff `Outer` contains `Inner`. O(1). Non-strict.
iterator_range< const_child_iterator >	children (CycleRef C) const
Printable	printEntries (CycleRef C, const ContextT &Ctx) const
bool	contains (CycleRef C, const BlockT *Block) const
	Return whether `Block` is contained in `C`. O(1).
ArrayRef< BlockT * >	getBlocks (CycleRef C) const
	Return the blocks of `C`, including those of nested cycles.
CycleRef	getSmallestCommonCycle (CycleRef A, CycleRef B) const
	Find the innermost cycle containing both given cycles.
CycleRef	getSmallestCommonCycle (BlockT A, BlockT B) const
	Find the innermost cycle containing both given blocks.
unsigned	getCycleDepth (const BlockT *Block) const
	Return the depth of the innermost cycle containing `Block`, or 0 if it is not contained in any cycle.
CycleRef	getTopLevelParentCycle (const BlockT *Block) const
void	getExitBlocks (CycleRef C, SmallVectorImpl< BlockT * > &TmpStorage) const
	Return all of the successor blocks of `C:` the blocks outside of `C` which are branched to from within it.
void	getExitingBlocks (CycleRef C, SmallVectorImpl< BlockT * > &TmpStorage) const
	Return all blocks of `C` that have a successor outside of `C`.
BlockT *	getCyclePreheader (CycleRef C) const
	Return the preheader block for `C`.
BlockT *	getCyclePredecessor (CycleRef C) const
	If `C` has exactly one entry with exactly one predecessor, return it, otherwise return nullptr.
void	verifyCycle (CycleRef C, SmallPtrSetImpl< BlockT * > &Reachable) const
	Verify that `C` is actually a well-formed cycle in the CFG.
void	verifyCycleNest (CycleRef C) const
	Verify the parent-child relations of `C`.
void	addBlockToCycle (BlockT *Block, CycleRef C)
	Assumes that `C` is the innermost cycle containing `Block`.
void	verifyCycleNest (bool VerifyFull=false) const
	Methods for debug and self-test.
void	verify () const
	Verify that the entire cycle tree well-formed.
void	print (raw_ostream &Out) const
	Print the cycle info.
void	dump () const
Printable	print (CycleRef C) const
	Print a single cycle: its depth, entries, and remaining blocks.
const_toplevel_iterator	toplevel_begin () const
const_toplevel_iterator	toplevel_end () const
iterator_range< const_toplevel_iterator >	toplevel_cycles () const

Friends
template<typename>
class	GenericCycleInfoCompute

Detailed Description

template<typename ContextT>
class llvm::GenericCycleInfo< ContextT >

Cycle information for a function.

Definition at line 80 of file GenericCycleInfo.h.

Member Typedef Documentation

◆ BlockT

template<typename ContextT>

using llvm::GenericCycleInfo< ContextT >::BlockT = typename ContextT::BlockT

Definition at line 82 of file GenericCycleInfo.h.

◆ const_toplevel_iterator

template<typename ContextT>

using llvm::GenericCycleInfo< ContextT >::const_toplevel_iterator = const_child_iterator

Iteration over top-level cycles.

Definition at line 344 of file GenericCycleInfo.h.

◆ FunctionT

template<typename ContextT>

using llvm::GenericCycleInfo< ContextT >::FunctionT = typename ContextT::FunctionT

Definition at line 83 of file GenericCycleInfo.h.

Constructor & Destructor Documentation

◆ GenericCycleInfo() [1/2]

template<typename ContextT>

llvm::GenericCycleInfo< ContextT >::GenericCycleInfo ( )

default

Referenced by llvm::GenericCycleInfo< ContextT >::const_child_iterator::const_child_iterator(), GenericCycleInfo(), and operator=().

◆ GenericCycleInfo() [2/2]

template<typename ContextT>

llvm::GenericCycleInfo< ContextT >::GenericCycleInfo ( GenericCycleInfo< ContextT > && )

default

References GenericCycleInfo().

Member Function Documentation

◆ addBlockToCycle()

template<typename ContextT>

void llvm::GenericCycleInfo< ContextT >::addBlockToCycle	(	BlockT *	Block,
		CycleRef	C )

Assumes that C is the innermost cycle containing Block.

Block will be appended to C and all of its parent cycles. Block will be added to BlockMap with C.

Definition at line 316 of file GenericCycleImpl.h.

References llvm::Block, C(), and llvm::Number.

Referenced by fixIrreducible(), and splitCriticalEdge().

◆ children()

template<typename ContextT>

iterator_range< const_child_iterator > llvm::GenericCycleInfo< ContextT >::children ( CycleRef C ) const

inline

Definition at line 252 of file GenericCycleInfo.h.

References C(), llvm::First, and llvm::make_range().

◆ clear()

template<typename ContextT>

void llvm::GenericCycleInfo< ContextT >::clear ( )

Reset the object to its initial state.

Definition at line 555 of file GenericCycleImpl.h.

◆ compute()

template<typename ContextT>

void llvm::GenericCycleInfo< ContextT >::compute ( FunctionT & F )

Compute the cycle info for a function.

Definition at line 565 of file GenericCycleImpl.h.

References llvm::dbgs(), F, GenericCycleInfoCompute, LLVM_DEBUG, and llvm::GenericCycleInfoCompute< ContextT >::run().

Referenced by annotateAllFunctions(), llvm::buildModuleSummaryIndex(), llvm::PreRARematStage::ScoredRemat::FreqInfo::FreqInfo(), llvm::OptimizationRemarkEmitter::OptimizationRemarkEmitter(), llvm::CycleAnalysis::run(), and llvm::MachineCycleAnalysis::run().

◆ contains() [1/2]

template<typename ContextT>

bool llvm::GenericCycleInfo< ContextT >::contains	(	CycleRef	C,
		const BlockT *	Block ) const

inline

Return whether Block is contained in C. O(1).

Definition at line 267 of file GenericCycleInfo.h.

References llvm::Block, C(), contains(), getCycle(), and llvm::CycleRef::isValid().

◆ contains() [2/2]

template<typename ContextT>

bool llvm::GenericCycleInfo< ContextT >::contains	(	CycleRef	Outer,
		CycleRef	Inner ) const

inline

Returns true iff Outer contains Inner. O(1). Non-strict.

Definition at line 247 of file GenericCycleInfo.h.

References I.

Referenced by contains(), fixIrreducible(), llvm::isCycleInvariant(), and llvm::SIInstrInfo::isSafeToSink().

◆ cycles()

template<typename ContextT>

auto llvm::GenericCycleInfo< ContextT >::cycles ( ) const

inline

All cycles in forest preorder.

Definition at line 201 of file GenericCycleInfo.h.

References I, llvm::map_range(), and llvm::seq().

Referenced by FixIrreducibleImpl().

◆ dump()

template<typename ContextT>

void llvm::GenericCycleInfo< ContextT >::dump ( ) const

inline

Definition at line 338 of file GenericCycleInfo.h.

References llvm::dbgs(), and print().

◆ getBlocks()

template<typename ContextT>

ArrayRef< BlockT * > llvm::GenericCycleInfo< ContextT >::getBlocks ( CycleRef C ) const

inline

Return the blocks of C, including those of nested cycles.

Definition at line 273 of file GenericCycleInfo.h.

References llvm::ArrayRef(), and C().

Referenced by getExitBlocks(), getExitingBlocks(), print(), updateLoopInfo(), verifyCycle(), verifyCycleNest(), and verifyCycleNest().

◆ getCycle()

template<typename ContextT>

CycleRef llvm::GenericCycleInfo< ContextT >::getCycle ( const BlockT * Block ) const

inline

Find the innermost cycle containing Block.

Returns: the innermost cycle containing Block or an invalid handle if it is not contained in any cycle.

Definition at line 210 of file GenericCycleInfo.h.

References llvm::Block, and llvm::Number.

Referenced by contains(), getCycleDepth(), getSmallestCommonCycle(), getTopLevelParentCycle(), isNotInCycle(), llvm::isPotentiallyReachable(), llvm::SIInstrInfo::isSafeToSink(), mayBeInCycle(), splitCriticalEdge(), and verifyCycleNest().

◆ getCycleDepth()

template<typename ContextT>

unsigned llvm::GenericCycleInfo< ContextT >::getCycleDepth ( const BlockT * Block ) const

inline

Return the depth of the innermost cycle containing Block, or 0 if it is not contained in any cycle.

Definition at line 284 of file GenericCycleInfo.h.

References llvm::Block, C(), getCycle(), and getDepth().

◆ getCyclePredecessor()

template<typename ContextT>

auto llvm::GenericCycleInfo< ContextT >::getCyclePredecessor ( CycleRef C ) const

If C has exactly one entry with exactly one predecessor, return it, otherwise return nullptr.

Definition at line 87 of file GenericCycleImpl.h.

References C(), contains(), getHeader(), isReducible(), and llvm::predecessors().

Referenced by getCyclePreheader().

◆ getCyclePreheader()

template<typename ContextT>

auto llvm::GenericCycleInfo< ContextT >::getCyclePreheader ( CycleRef C ) const

Return the preheader block for C.

Pre-header is well-defined for reducible cycle in docs/LoopTerminology.md as: the only one entering block and its only edge is to the entry block. Return null for irreducible cycles.

Definition at line 68 of file GenericCycleImpl.h.

References assert(), C(), getCyclePredecessor(), isReducible(), and llvm::succ_size().

◆ getDepth()

template<typename ContextT>

unsigned llvm::GenericCycleInfo< ContextT >::getDepth ( CycleRef C ) const

inline

Definition at line 225 of file GenericCycleInfo.h.

References C().

Referenced by getCycleDepth(), getSmallestCommonCycle(), print(), and print().

◆ getEntries()

template<typename ContextT>

ArrayRef< BlockT * > llvm::GenericCycleInfo< ContextT >::getEntries ( CycleRef C ) const

inline

Definition at line 231 of file GenericCycleInfo.h.

References llvm::ArrayRef(), and C().

Referenced by fixIrreducible(), llvm::isCycleInvariant(), isEntry(), printEntries(), and verifyCycle().

◆ getExitBlocks()

template<typename ContextT>

void llvm::GenericCycleInfo< ContextT >::getExitBlocks	(	CycleRef	C,
		SmallVectorImpl< BlockT * > &	TmpStorage ) const

Return all of the successor blocks of C: the blocks outside of C which are branched to from within it.

Definition at line 39 of file GenericCycleImpl.h.

References llvm::SmallVectorImpl< T >::append(), llvm::Block, C(), contains(), getBlocks(), llvm::SmallPtrSetImpl< PtrType >::insert(), and llvm::successors().

Referenced by isReachableImpl(), and verifyCycle().

◆ getExitingBlocks()

template<typename ContextT>

void llvm::GenericCycleInfo< ContextT >::getExitingBlocks	(	CycleRef	C,
		SmallVectorImpl< BlockT * > &	TmpStorage ) const

Return all blocks of C that have a successor outside of C.

Definition at line 55 of file GenericCycleImpl.h.

References llvm::Block, C(), contains(), getBlocks(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::successors().

Referenced by llvm::SIInstrInfo::isSafeToSink().

◆ getFunction()

template<typename ContextT>

const FunctionT * llvm::GenericCycleInfo< ContextT >::getFunction ( ) const

inline

Definition at line 197 of file GenericCycleInfo.h.

◆ getHeader()

template<typename ContextT>

BlockT * llvm::GenericCycleInfo< ContextT >::getHeader ( CycleRef C ) const

inline

Definition at line 220 of file GenericCycleInfo.h.

References C().

Referenced by fixIrreducible(), getCyclePredecessor(), mayBeInCycle(), updateLoopInfo(), verifyCycle(), and verifyCycleNest().

◆ getNumBlocks()

template<typename ContextT>

size_t llvm::GenericCycleInfo< ContextT >::getNumBlocks ( CycleRef C ) const

inline

Definition at line 226 of file GenericCycleInfo.h.

References C().

Referenced by verifyCycle().

◆ getParentCycle()

template<typename ContextT>

CycleRef llvm::GenericCycleInfo< ContextT >::getParentCycle ( CycleRef C ) const

inline

Definition at line 224 of file GenericCycleInfo.h.

References C().

Referenced by fixIrreducible(), getSmallestCommonCycle(), getTopLevelParentCycle(), and llvm::SIInstrInfo::isSafeToSink().

◆ getSmallestCommonCycle() [1/2]

template<typename ContextT>

auto llvm::GenericCycleInfo< ContextT >::getSmallestCommonCycle	(	BlockT *	A,
		BlockT *	B ) const

Find the innermost cycle containing both given blocks.

Returns: the innermost cycle containing both A and B or nullptr if there is no such cycle.

Definition at line 625 of file GenericCycleImpl.h.

References A(), B(), getCycle(), and getSmallestCommonCycle().

◆ getSmallestCommonCycle() [2/2]

template<typename ContextT>

auto llvm::GenericCycleInfo< ContextT >::getSmallestCommonCycle	(	CycleRef	A,
		CycleRef	B ) const

Find the innermost cycle containing both given cycles.

Returns: the innermost cycle containing both A and B or nullptr if there is no such cycle.

Definition at line 596 of file GenericCycleImpl.h.

References A(), B(), getDepth(), and getParentCycle().

Referenced by getSmallestCommonCycle(), and splitCriticalEdge().

◆ getSSAContext()

template<typename ContextT>

const ContextT & llvm::GenericCycleInfo< ContextT >::getSSAContext ( ) const

inline

Definition at line 198 of file GenericCycleInfo.h.

◆ getTopLevelParentCycle()

template<typename ContextT>

CycleRef llvm::GenericCycleInfo< ContextT >::getTopLevelParentCycle ( const BlockT * Block ) const

inline

Definition at line 289 of file GenericCycleInfo.h.

References llvm::Block, C(), getCycle(), getParentCycle(), and P.

Referenced by isReachableImpl().

◆ isEntry()

template<typename ContextT>

bool llvm::GenericCycleInfo< ContextT >::isEntry	(	CycleRef	C,
		const BlockT *	Block ) const

inline

Definition at line 235 of file GenericCycleInfo.h.

References llvm::Block, C(), getEntries(), and llvm::is_contained().

Referenced by print().

◆ isReducible()

template<typename ContextT>

bool llvm::GenericCycleInfo< ContextT >::isReducible ( CycleRef C ) const

inline

Definition at line 223 of file GenericCycleInfo.h.

References C().

Referenced by fixIrreducible(), getCyclePredecessor(), and getCyclePreheader().

◆ operator=()

template<typename ContextT>

GenericCycleInfo & llvm::GenericCycleInfo< ContextT >::operator= ( GenericCycleInfo< ContextT > && )

default

References F, and GenericCycleInfo().

◆ print() [1/2]

template<typename ContextT>

Printable llvm::GenericCycleInfo< ContextT >::print ( CycleRef C ) const

Print a single cycle: its depth, entries, and remaining blocks.

Definition at line 676 of file GenericCycleImpl.h.

References llvm::Block, C(), getBlocks(), getDepth(), isEntry(), and printEntries().

◆ print() [2/2]

template<typename ContextT>

void llvm::GenericCycleInfo< ContextT >::print ( raw_ostream & Out ) const

Print the cycle info.

Definition at line 665 of file GenericCycleImpl.h.

References C(), cycles, llvm::Depth, getDepth(), I, and llvm::print().

Referenced by dump(), fixIrreducible(), and llvm::MachineBlockFrequencyInfo::print().

◆ printEntries()

template<typename ContextT>

Printable llvm::GenericCycleInfo< ContextT >::printEntries	(	CycleRef	C,
		const ContextT &	Ctx ) const

inline

Definition at line 258 of file GenericCycleInfo.h.

References C(), and getEntries().

Referenced by print().

◆ setSingleEntry()

template<typename ContextT>

void llvm::GenericCycleInfo< ContextT >::setSingleEntry	(	CycleRef	C,
		BlockT *	Block )

inline

Definition at line 240 of file GenericCycleInfo.h.

References llvm::Block, and C().

Referenced by fixIrreducible().

◆ splitCriticalEdge()

template<typename ContextT>

void llvm::GenericCycleInfo< ContextT >::splitCriticalEdge	(	BlockT *	Pred,
		BlockT *	Succ,
		BlockT *	New )

Definition at line 577 of file GenericCycleImpl.h.

References addBlockToCycle(), C(), getCycle(), getSmallestCommonCycle(), and verifyCycleNest().

◆ toplevel_begin()

template<typename ContextT>

const_toplevel_iterator llvm::GenericCycleInfo< ContextT >::toplevel_begin ( ) const

inline

Definition at line 346 of file GenericCycleInfo.h.

Referenced by toplevel_cycles().

◆ toplevel_cycles()

template<typename ContextT>

iterator_range< const_toplevel_iterator > llvm::GenericCycleInfo< ContextT >::toplevel_cycles ( ) const

inline

Definition at line 353 of file GenericCycleInfo.h.

References llvm::make_range(), toplevel_begin(), and toplevel_end().

◆ toplevel_end()

template<typename ContextT>

const_toplevel_iterator llvm::GenericCycleInfo< ContextT >::toplevel_end ( ) const

inline

Definition at line 349 of file GenericCycleInfo.h.

Referenced by toplevel_cycles().

◆ verify()

template<typename ContextT>

void llvm::GenericCycleInfo< ContextT >::verify ( ) const

Verify that the entire cycle tree well-formed.

Definition at line 659 of file GenericCycleImpl.h.

References verifyCycleNest().

Referenced by FixIrreducibleImpl(), and llvm::CycleInfoVerifierPass::run().

◆ verifyCycle()

template<typename ContextT>

void llvm::GenericCycleInfo< ContextT >::verifyCycle	(	CycleRef	C,
		SmallPtrSetImpl< BlockT * > &	Reachable ) const

Verify that C is actually a well-formed cycle in the CFG.

Reachable caches the blocks reachable from the function entry. It is computed on first use if empty, so that verifying many cycles walks the whole function at most once. It must not be reused after the CFG changes.

Definition at line 108 of file GenericCycleImpl.h.

References llvm::any_of(), assert(), B(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), C(), llvm::children(), contains(), llvm::detail::DenseSetImpl< ValueT, MapTy >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::depth_first(), llvm::depth_first_ext(), llvm::SmallVectorTemplateCommon< T, typename >::end(), getBlocks(), getEntries(), getExitBlocks(), getHeader(), getNumBlocks(), getParent(), llvm::detail::DenseSetImpl< ValueT, MapTy >::insert(), llvm::df_iterator_default_set< NodeRef, SmallSize >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::inverse_children(), llvm_unreachable, llvm::SmallPtrSetImplBase::size(), and verifyCycleNest().

Referenced by fixIrreducible(), and verifyCycleNest().

◆ verifyCycleNest() [1/2]

template<typename ContextT>

void llvm::GenericCycleInfo< ContextT >::verifyCycleNest ( bool VerifyFull = false ) const

Methods for debug and self-test.

Verify the internal consistency of the cycle tree.

Note that this does not check that cycles are really cycles in the CFG, or that the right set of cycles in the CFG were found.

Definition at line 636 of file GenericCycleImpl.h.

References assert(), C(), contains(), cycles, getBlocks(), getCycle(), getHeader(), llvm::detail::DenseSetImpl< ValueT, MapTy >::insert(), llvm::CycleRef::isValid(), verifyCycle(), and verifyCycleNest().

◆ verifyCycleNest() [2/2]

template<typename ContextT>

void llvm::GenericCycleInfo< ContextT >::verifyCycleNest ( CycleRef C ) const

Verify the parent-child relations of C.

Note that this does not check that C is really a cycle in the CFG.

Definition at line 186 of file GenericCycleImpl.h.

References C(), llvm::children(), and getBlocks().

Referenced by splitCriticalEdge(), verify(), verifyCycle(), and verifyCycleNest().

◆ GenericCycleInfoCompute

template<typename ContextT>

template<typename>

friend class GenericCycleInfoCompute

friend

Definition at line 84 of file GenericCycleInfo.h.

References llvm::Depth, and GenericCycleInfoCompute.

Referenced by compute(), and GenericCycleInfoCompute.

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

include/llvm/ADT/GenericCycleInfo.h
include/llvm/ADT/GenericCycleImpl.h

Classes

Public Types

Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ BlockT

◆ const_toplevel_iterator

◆ FunctionT

Constructor & Destructor Documentation

◆ GenericCycleInfo() [1/2]

◆ GenericCycleInfo() [2/2]

Member Function Documentation

◆ addBlockToCycle()

◆ children()

◆ clear()

◆ compute()

◆ contains() [1/2]

◆ contains() [2/2]

◆ cycles()

◆ dump()

◆ getBlocks()

◆ getCycle()

◆ getCycleDepth()

◆ getCyclePredecessor()

◆ getCyclePreheader()

◆ getDepth()

◆ getEntries()

◆ getExitBlocks()

◆ getExitingBlocks()

◆ getFunction()

◆ getHeader()

◆ getNumBlocks()

◆ getParentCycle()

◆ getSmallestCommonCycle() [1/2]

◆ getSmallestCommonCycle() [2/2]

◆ getSSAContext()

◆ getTopLevelParentCycle()

◆ isEntry()

◆ isReducible()

◆ operator=()

◆ print() [1/2]

◆ print() [2/2]

◆ printEntries()

◆ setSingleEntry()

◆ splitCriticalEdge()

◆ toplevel_begin()

◆ toplevel_cycles()

◆ toplevel_end()

◆ verify()

◆ verifyCycle()

◆ verifyCycleNest() [1/2]

◆ verifyCycleNest() [2/2]

Friends And Related Symbol Documentation

◆ GenericCycleInfoCompute