Base class for BlockFrequencyInfoImpl. More...

#include "llvm/Analysis/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
using	Scaled64 = ScaledNumber< uint64_t >

using	BlockMass = bfi_detail::BlockMass

Public Member Functions
virtual	~BlockFrequencyInfoImplBase ()=default
	Virtual destructor. More...

bool	addLoopSuccessorsToDist (const LoopData *OuterLoop, LoopData &Loop, Distribution &Dist)
	Add all edges out of a packaged loop to the distribution. More...

bool	addToDist (Distribution &Dist, const LoopData *OuterLoop, const BlockNode &Pred, const BlockNode &Succ, uint64_t Weight)
	Add an edge to the distribution. More...

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. More...

void	updateLoopWithIrreducible (LoopData &OuterLoop)
	Update a loop after packaging irreducible SCCs inside of it. More...

void	distributeMass (const BlockNode &Source, LoopData *OuterLoop, Distribution &Dist)
	Distribute mass according to a distribution. More...

void	computeLoopScale (LoopData &Loop)
	Compute the loop scale for a loop. More...

void	adjustLoopHeaderMass (LoopData &Loop)
	Adjust the mass of all headers in an irreducible loop. More...

void	distributeIrrLoopHeaderMass (Distribution &Dist)

void	packageLoop (LoopData &Loop)
	Package up a loop. More...

void	unwrapLoops ()
	Unwrap loops. More...

void	finalizeMetrics ()
	Finalize frequency metrics. More...

void	clear ()
	Clear all memory. More...

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

Optional< uint64_t >	getBlockProfileCount (const Function &F, const BlockNode &Node) const

Optional< uint64_t >	getProfileCountFromFreq (const Function &F, uint64_t Freq) const

bool	isIrrLoopHeader (const BlockNode &Node)

void	setBlockFreq (const BlockNode &Node, uint64_t Freq)

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

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

uint64_t	getEntryFreq () const

Public Attributes
std::vector< FrequencyData >	Freqs
	Data about each block. This is used downstream. More...

SparseBitVector	IsIrrLoopHeader
	Whether each block is an irreducible loop header. More...

std::vector< WorkingData >	Working
	Loop data: see initializeLoops(). More...

std::list< LoopData >	Loops
	Indexed information about loops. More...

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 175 of file BlockFrequencyInfoImpl.h.

Member Typedef Documentation

◆ BlockMass

using llvm::BlockFrequencyInfoImplBase::BlockMass = bfi_detail::BlockMass

Definition at line 178 of file BlockFrequencyInfoImpl.h.

◆ Scaled64

using llvm::BlockFrequencyInfoImplBase::Scaled64 = ScaledNumber<uint64_t>

Definition at line 177 of file BlockFrequencyInfoImpl.h.

Constructor & Destructor Documentation

◆ ~BlockFrequencyInfoImplBase()

virtual llvm::BlockFrequencyInfoImplBase::~BlockFrequencyInfoImplBase ( )

virtualdefault

Virtual destructor.

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

Member Function Documentation

◆ addLoopSuccessorsToDist()

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 353 of file BlockFrequencyInfoImpl.cpp.

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

◆ addToDist()

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 291 of file BlockFrequencyInfoImpl.cpp.

◆ adjustLoopHeaderMass()

void BlockFrequencyInfoImplBase::adjustLoopHeaderMass ( LoopData & Loop )

Adjust the mass of all headers in an irreducible loop.

Initially, irreducible loops are assumed to distribute their mass equally among its headers. This can lead to wrong frequency estimates since some headers may be executed more frequently than others.

This adjusts header mass distribution so it matches the weights of the backedges going into each of the loop headers.

Definition at line 803 of file BlockFrequencyInfoImpl.cpp.

◆ analyzeIrreducible()

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 772 of file BlockFrequencyInfoImpl.cpp.

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

◆ clear()

void BlockFrequencyInfoImplBase::clear ( )

Clear all memory.

Definition at line 271 of file BlockFrequencyInfoImpl.cpp.

References Loops, and std::swap().

Referenced by llvm::BlockFrequencyInfoImpl< llvm::BitTracker >::calculate(), and cleanup().

◆ computeLoopScale()

void BlockFrequencyInfoImplBase::computeLoopScale ( LoopData & Loop )

Compute the loop scale for a loop.

Definition at line 366 of file BlockFrequencyInfoImpl.cpp.

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

◆ distributeIrrLoopHeaderMass()

void BlockFrequencyInfoImplBase::distributeIrrLoopHeaderMass ( Distribution & Dist )

Definition at line 840 of file BlockFrequencyInfoImpl.cpp.

References llvm::BlockFrequencyInfoImplBase::Weight::Amount, assert(), D, debugAssign(), llvm::bfi_detail::BlockMass::getFull(), llvm::BlockFrequencyInfoImplBase::BlockNode::Index, LLVM_DEBUG, llvm::BlockFrequencyInfoImplBase::Weight::TargetNode, llvm::BlockFrequencyInfoImplBase::Weight::Type, llvm::RISCVFenceField::W, and llvm::BlockFrequencyInfoImplBase::Distribution::Weights.

◆ distributeMass()

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 426 of file BlockFrequencyInfoImpl.cpp.

◆ dump()

void llvm::BlockFrequencyInfoImplBase::dump ( ) const

inline

Definition at line 522 of file BlockFrequencyInfoImpl.h.

References llvm::dbgs(), F(), and llvm::bfi_detail::BlockMass::print().

Referenced by llvm::BlockFrequencyInfoImpl< llvm::BitTracker >::getBPI().

◆ finalizeMetrics()

void BlockFrequencyInfoImplBase::finalizeMetrics ( )

Finalize frequency metrics.

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

Definition at line 531 of file BlockFrequencyInfoImpl.cpp.

References cleanup(), convertFloatingToInteger(), llvm::bfi_detail::BlockMass::dump(), LLVM_DEBUG, and llvm::max().

◆ getBlockFreq()

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

Definition at line 553 of file BlockFrequencyInfoImpl.cpp.

Referenced by llvm::BlockFrequencyInfoImpl< llvm::BitTracker >::getBlockFreq().

◆ getBlockName()

std::string BlockFrequencyInfoImplBase::getBlockName ( const BlockNode & Node ) const

virtual

Definition at line 604 of file BlockFrequencyInfoImpl.cpp.

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

◆ getBlockProfileCount()

Optional< uint64_t > BlockFrequencyInfoImplBase::getBlockProfileCount	(	const Function &	F,
		const BlockNode &	Node
	)		const

Definition at line 560 of file BlockFrequencyInfoImpl.cpp.

Referenced by llvm::BlockFrequencyInfoImpl< llvm::BitTracker >::getBlockProfileCount(), and llvm::BlockFrequencyInfoImpl< llvm::BitTracker >::print().

◆ getEntryFreq()

uint64_t llvm::BlockFrequencyInfoImplBase::getEntryFreq ( ) const

inline

Definition at line 539 of file BlockFrequencyInfoImpl.h.

References assert().

Referenced by llvm::BlockFrequencyInfoImpl< llvm::BitTracker >::getFunction().

◆ getFloatingBlockFreq()

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

Definition at line 590 of file BlockFrequencyInfoImpl.cpp.

Referenced by llvm::BlockFrequencyInfoImpl< llvm::BitTracker >::getFloatingBlockFreq().

◆ getLoopName()

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

Definition at line 609 of file BlockFrequencyInfoImpl.cpp.

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

Referenced by unwrapLoop().

◆ getLoopPackage()

LoopData& llvm::BlockFrequencyInfoImplBase::getLoopPackage ( const BlockNode & Head )

inline

Definition at line 454 of file BlockFrequencyInfoImpl.h.

References assert(), clear(), G, llvm::bfi_detail::getBlockName(), llvm::BlockFrequencyInfoImplBase::BlockNode::Index, and llvm::Sched::Source.

◆ getProfileCountFromFreq()

Optional< uint64_t > BlockFrequencyInfoImplBase::getProfileCountFromFreq	(	const Function &	F,
		uint64_t	Freq
	)		const

Definition at line 566 of file BlockFrequencyInfoImpl.cpp.

References llvm::Function::getEntryCount(), llvm::APInt::lshr(), and llvm::None.

Referenced by llvm::BlockFrequencyInfoImpl< llvm::BitTracker >::getProfileCountFromFreq().

◆ isIrrLoopHeader()

bool BlockFrequencyInfoImplBase::isIrrLoopHeader ( const BlockNode & Node )

Definition at line 583 of file BlockFrequencyInfoImpl.cpp.

Referenced by llvm::BlockFrequencyInfoImpl< llvm::BitTracker >::isIrrLoopHeader().

◆ packageLoop()

void BlockFrequencyInfoImplBase::packageLoop ( LoopData & Loop )

Package up a loop.

Definition at line 401 of file BlockFrequencyInfoImpl.cpp.

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

◆ print()

virtual raw_ostream& llvm::BlockFrequencyInfoImplBase::print ( raw_ostream & OS ) const

inlinevirtual

Reimplemented in llvm::BlockFrequencyInfoImpl< BT >, and llvm::BlockFrequencyInfoImpl< llvm::BitTracker >.

Definition at line 521 of file BlockFrequencyInfoImpl.h.

◆ printBlockFreq() [1/2]

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

Definition at line 614 of file BlockFrequencyInfoImpl.cpp.

Referenced by llvm::BlockFrequencyInfoImpl< llvm::BitTracker >::getBPI(), and llvm::BlockFrequencyInfoImpl< llvm::BitTracker >::printBlockFreq().

◆ printBlockFreq() [2/2]

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

Definition at line 620 of file BlockFrequencyInfoImpl.cpp.

References llvm::BlockFrequency::getFrequency().

◆ setBlockFreq()

void BlockFrequencyInfoImplBase::setBlockFreq	(	const BlockNode &	Node,
		uint64_t	Freq
	)

Definition at line 596 of file BlockFrequencyInfoImpl.cpp.

Referenced by llvm::BlockFrequencyInfoImpl< llvm::BitTracker >::setBlockFreq().

◆ unwrapLoops()

void BlockFrequencyInfoImplBase::unwrapLoops ( )

Unwrap loops.

Definition at line 522 of file BlockFrequencyInfoImpl.cpp.

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

◆ updateLoopWithIrreducible()

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 792 of file BlockFrequencyInfoImpl.cpp.

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

Member Data Documentation

◆ Freqs

std::vector<FrequencyData> llvm::BlockFrequencyInfoImplBase::Freqs

Data about each block. This is used downstream.

Definition at line 417 of file BlockFrequencyInfoImpl.h.

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

◆ IsIrrLoopHeader

SparseBitVector llvm::BlockFrequencyInfoImplBase::IsIrrLoopHeader

Whether each block is an irreducible loop header.

This is used downstream.

Definition at line 421 of file BlockFrequencyInfoImpl.h.

Referenced by cleanup().

◆ Loops

std::list<LoopData> llvm::BlockFrequencyInfoImplBase::Loops

Indexed information about loops.

Definition at line 427 of file BlockFrequencyInfoImpl.h.

Referenced by createIrreducibleLoop().

◆ Working

std::vector<WorkingData> llvm::BlockFrequencyInfoImplBase::Working

Loop data: see initializeLoops().

Definition at line 424 of file BlockFrequencyInfoImpl.h.

Referenced by createIrreducibleLoop(), and unwrapLoop().

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

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

Classes

Public Types

Public Member Functions

Public Attributes

Detailed Description

Member Typedef Documentation

◆ BlockMass

◆ Scaled64

Constructor & Destructor Documentation

◆ ~BlockFrequencyInfoImplBase()

Member Function Documentation

◆ addLoopSuccessorsToDist()

◆ addToDist()

◆ adjustLoopHeaderMass()

◆ analyzeIrreducible()

◆ clear()

◆ computeLoopScale()

◆ distributeIrrLoopHeaderMass()

◆ distributeMass()

◆ dump()

◆ finalizeMetrics()

◆ getBlockFreq()

◆ getBlockName()

◆ getBlockProfileCount()

◆ getEntryFreq()

◆ getFloatingBlockFreq()

◆ getLoopName()

◆ getLoopPackage()

◆ getProfileCountFromFreq()

◆ isIrrLoopHeader()

◆ packageLoop()

◆ print()

◆ printBlockFreq() [1/2]

◆ printBlockFreq() [2/2]

◆ setBlockFreq()

◆ unwrapLoops()

◆ updateLoopWithIrreducible()

Member Data Documentation

◆ Freqs

◆ IsIrrLoopHeader

◆ Loops

◆ Working