Base class for BlockFrequencyInfoImpl. More...

#include <BlockFrequencyInfoImpl.h>

Inheritance diagram for llvm::BlockFrequencyInfoImplBase:

Collaboration diagram for llvm::BlockFrequencyInfoImplBase:

Classes
struct	BlockNode
	Representative of a block. More...
struct	Distribution
	Distribution of unscaled probability weight. More...
struct	FrequencyData
	Stats about a block itself. More...
struct	LoopData
	Data about a loop. More...
struct	Weight
	Unscaled probability weight. More...
struct	WorkingData
	Index of loop information. More...
Public Types
typedef ScaledNumber< uint64_t >	Scaled64
typedef bfi_detail::BlockMass	BlockMass
Public Member Functions
bool	addLoopSuccessorsToDist (const LoopData *OuterLoop, LoopData &Loop, Distribution &Dist)
	Add all edges out of a packaged loop to the distribution.
bool	addToDist (Distribution &Dist, const LoopData *OuterLoop, const BlockNode &Pred, const BlockNode &Succ, uint64_t Weight)
	Add an edge to the distribution.
LoopData &	getLoopPackage (const BlockNode &Head)
iterator_range< std::list < LoopData >::iterator >	analyzeIrreducible (const bfi_detail::IrreducibleGraph &G, LoopData *OuterLoop, std::list< LoopData >::iterator Insert)
	Analyze irreducible SCCs.
void	updateLoopWithIrreducible (LoopData &OuterLoop)
	Update a loop after packaging irreducible SCCs inside of it.
void	distributeMass (const BlockNode &Source, LoopData *OuterLoop, Distribution &Dist)
	Distribute mass according to a distribution.
void	computeLoopScale (LoopData &Loop)
	Compute the loop scale for a loop.
void	packageLoop (LoopData &Loop)
	Package up a loop.
void	unwrapLoops ()
	Unwrap loops.
void	finalizeMetrics ()
	Finalize frequency metrics.
void	clear ()
	Clear all memory.
virtual std::string	getBlockName (const BlockNode &Node) const
std::string	getLoopName (const LoopData &Loop) const
virtual raw_ostream &	print (raw_ostream &OS) const
void	dump () const
Scaled64	getFloatingBlockFreq (const BlockNode &Node) const
BlockFrequency	getBlockFreq (const BlockNode &Node) const
raw_ostream &	printBlockFreq (raw_ostream &OS, const BlockNode &Node) const
raw_ostream &	printBlockFreq (raw_ostream &OS, const BlockFrequency &Freq) const
uint64_t	getEntryFreq () const
virtual	~BlockFrequencyInfoImplBase ()
	Virtual destructor.
Public Attributes
std::vector< FrequencyData >	Freqs
	Data about each block. This is used downstream.
std::vector< WorkingData >	Working
	Loop data: see initializeLoops().
std::list< LoopData >	Loops
	Indexed information about loops.

Detailed Description

Base class for BlockFrequencyInfoImpl.

BlockFrequencyInfoImplBase has supporting data structures and some algorithms for BlockFrequencyInfoImplBase. Only algorithms that depend on the block type (or that call such algorithms) are skipped here.

Nevertheless, the majority of the overall algorithm documention lives with BlockFrequencyInfoImpl. See there for details.

Definition at line 156 of file BlockFrequencyInfoImpl.h.

Member Typedef Documentation

typedef bfi_detail::BlockMass llvm::BlockFrequencyInfoImplBase::BlockMass

Definition at line 159 of file BlockFrequencyInfoImpl.h.

typedef ScaledNumber<uint64_t> llvm::BlockFrequencyInfoImplBase::Scaled64

Definition at line 158 of file BlockFrequencyInfoImpl.h.

Constructor & Destructor Documentation

virtual llvm::BlockFrequencyInfoImplBase::~BlockFrequencyInfoImplBase ( ) [inline, virtual]

Virtual destructor.

Need a virtual destructor to mask the compiler warning about getBlockName().

Definition at line 471 of file BlockFrequencyInfoImpl.h.

Member Function Documentation

bool BlockFrequencyInfoImplBase::addLoopSuccessorsToDist	(	const LoopData *	OuterLoop,
		LoopData &	Loop,
		Distribution &	Dist
	)

Add all edges out of a packaged loop to the distribution.

Adds all edges from LocalLoopHead to Dist. Calls addToDist() to add each successor edge.

Returns:: true unless there's an irreducible backedge.

Definition at line 310 of file BlockFrequencyInfoImpl.cpp.

References llvm::BlockFrequencyInfoImplBase::LoopData::Exits, llvm::BlockFrequencyInfoImplBase::LoopData::getHeader(), and I.

bool BlockFrequencyInfoImplBase::addToDist	(	Distribution &	Dist,
		const LoopData *	OuterLoop,
		const BlockNode &	Pred,
		const BlockNode &	Succ,
		uint64_t	Weight
	)

Add an edge to the distribution.

Adds an edge to Succ to Dist. If LoopHead.isValid(), then whether the edge is local/exit/backedge is in the context of LoopHead. Otherwise, every edge should be a local edge (since all the loops are packaged up).

Returns:: true unless aborted due to an irreducible backedge.

Definition at line 248 of file BlockFrequencyInfoImpl.cpp.

References llvm::BlockFrequencyInfoImplBase::Distribution::addBackedge(), llvm::BlockFrequencyInfoImplBase::Distribution::addExit(), llvm::BlockFrequencyInfoImplBase::Distribution::addLocal(), llvm::dbgs(), DEBUG, getBlockName(), llvm::BlockFrequencyInfoImplBase::LoopData::getHeader(), llvm::BlockFrequencyInfoImplBase::BlockNode::Index, llvm::BlockFrequencyInfoImplBase::LoopData::isHeader(), llvm::BlockFrequencyInfoImplBase::LoopData::isIrreducible(), Node, and Type.

iterator_range< std::list< LoopData >::iterator > BlockFrequencyInfoImplBase::analyzeIrreducible	(	const bfi_detail::IrreducibleGraph &	G,
		LoopData *	OuterLoop,
		std::list< LoopData >::iterator	Insert
	)

Analyze irreducible SCCs.

Separate irreducible SCCs from G, which is an explict graph of OuterLoop (or the top-level function, if OuterLoop is nullptr). Insert them into Loops before Insert.

Returns:: the LoopData nodes representing the irreducible SCCs.

Definition at line 669 of file BlockFrequencyInfoImpl.cpp.

References createIrreducibleLoop(), I, Loops, llvm::make_range(), and llvm::scc_begin().

void BlockFrequencyInfoImplBase::clear ( )

Clear all memory.

Definition at line 231 of file BlockFrequencyInfoImpl.cpp.

References Loops, and std::swap().

Referenced by cleanup(), and llvm::BlockFrequencyInfoImpl< BT >::doFunction().

void BlockFrequencyInfoImplBase::computeLoopScale ( LoopData & Loop )

Compute the loop scale for a loop.

Definition at line 329 of file BlockFrequencyInfoImpl.cpp.

References llvm::BlockFrequencyInfoImplBase::LoopData::BackedgeMass, llvm::dbgs(), DEBUG, getMaxLoopScale(), llvm::ScaledNumber< DigitsT >::inverse(), llvm::BlockFrequencyInfoImplBase::LoopData::Scale, and llvm::bfi_detail::BlockMass::toScaled().

void BlockFrequencyInfoImplBase::distributeMass	(	const BlockNode &	Source,
		LoopData *	OuterLoop,
		Distribution &	Dist
	)

Distribute mass according to a distribution.

Distributes the mass in Source according to Dist. If LoopHead.isValid(), backedges and exits are stored in its entry in Loops.

Mass is distributed in parallel from two copies of the source mass.

Definition at line 363 of file BlockFrequencyInfoImpl.cpp.

void llvm::BlockFrequencyInfoImplBase::dump ( ) const [inline]

Definition at line 453 of file BlockFrequencyInfoImpl.h.

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

void BlockFrequencyInfoImplBase::finalizeMetrics ( )

Finalize frequency metrics.

Calculates final frequencies and cleans up no-longer-needed data structures.

Definition at line 472 of file BlockFrequencyInfoImpl.cpp.

References cleanup(), convertFloatingToInteger(), DEBUG, and llvm::dump().

BlockFrequency BlockFrequencyInfoImplBase::getBlockFreq ( const BlockNode & Node ) const

Definition at line 494 of file BlockFrequencyInfoImpl.cpp.

References llvm::BlockFrequencyInfoImplBase::BlockNode::Index, and llvm::BlockFrequencyInfoImplBase::BlockNode::isValid().

std::string BlockFrequencyInfoImplBase::getBlockName ( const BlockNode & Node ) const [virtual]

Definition at line 507 of file BlockFrequencyInfoImpl.cpp.

Referenced by convertFloatingToInteger(), findIrreducibleHeaders(), and unwrapLoop().

uint64_t llvm::BlockFrequencyInfoImplBase::getEntryFreq ( ) const [inline]

Definition at line 463 of file BlockFrequencyInfoImpl.h.

References Freqs.

Scaled64 BlockFrequencyInfoImplBase::getFloatingBlockFreq ( const BlockNode & Node ) const

Definition at line 500 of file BlockFrequencyInfoImpl.cpp.

References llvm::BlockFrequencyInfoImplBase::BlockNode::Index, and llvm::BlockFrequencyInfoImplBase::BlockNode::isValid().

std::string BlockFrequencyInfoImplBase::getLoopName ( const LoopData & Loop ) const

Definition at line 511 of file BlockFrequencyInfoImpl.cpp.

References getBlockName(), llvm::BlockFrequencyInfoImplBase::LoopData::getHeader(), and llvm::BlockFrequencyInfoImplBase::LoopData::isIrreducible().

Referenced by unwrapLoop().

LoopData& llvm::BlockFrequencyInfoImplBase::getLoopPackage ( const BlockNode & Head ) [inline]

Definition at line 397 of file BlockFrequencyInfoImpl.h.

References llvm::BlockFrequencyInfoImplBase::BlockNode::Index, and Working.

void BlockFrequencyInfoImplBase::packageLoop ( LoopData & Loop )

Package up a loop.

Definition at line 351 of file BlockFrequencyInfoImpl.cpp.

References llvm::SmallVectorImpl< T >::clear(), llvm::dbgs(), DEBUG, llvm::BlockFrequencyInfoImplBase::LoopData::Exits, getBlockName(), llvm::BlockFrequencyInfoImplBase::BlockNode::Index, llvm::BlockFrequencyInfoImplBase::LoopData::IsPackaged, and llvm::BlockFrequencyInfoImplBase::LoopData::Nodes.

virtual raw_ostream& llvm::BlockFrequencyInfoImplBase::print ( raw_ostream & OS ) const [inline, virtual]

Reimplemented in llvm::BlockFrequencyInfoImpl< BT >.

Definition at line 452 of file BlockFrequencyInfoImpl.h.

Referenced by dump().

raw_ostream & BlockFrequencyInfoImplBase::printBlockFreq	(	raw_ostream &	OS,
		const BlockNode &	Node
	)		const

Definition at line 516 of file BlockFrequencyInfoImpl.cpp.

raw_ostream & BlockFrequencyInfoImplBase::printBlockFreq	(	raw_ostream &	OS,
		const BlockFrequency &	Freq
	)		const

Definition at line 522 of file BlockFrequencyInfoImpl.cpp.

References llvm::BlockFrequency::getFrequency().

void BlockFrequencyInfoImplBase::unwrapLoops ( )

Unwrap loops.

Definition at line 463 of file BlockFrequencyInfoImpl.cpp.

References Loops, llvm::bfi_detail::BlockMass::toScaled(), and unwrapLoop().

void BlockFrequencyInfoImplBase::updateLoopWithIrreducible ( LoopData & OuterLoop )

Update a loop after packaging irreducible SCCs inside of it.

Update OuterLoop. Before finding irreducible control flow, it was partway through computeMassInLoop(), so LoopData::Exits and LoopData::BackedgeMass need to be reset. Also, nodes that were packaged up need to be removed from OuterLoop::Nodes.

Definition at line 689 of file BlockFrequencyInfoImpl.cpp.

References llvm::BlockFrequencyInfoImplBase::LoopData::BackedgeMass, llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::SmallVectorImpl< T >::erase(), llvm::BlockFrequencyInfoImplBase::LoopData::Exits, I, and llvm::BlockFrequencyInfoImplBase::LoopData::Nodes.