LLVM 19.0.0git
Classes | Public Types | Public Member Functions | Public Attributes | List of all members
llvm::BlockFrequencyInfoImplBase Class Reference

Base class for BlockFrequencyInfoImpl. More...

#include "llvm/Analysis/BlockFrequencyInfoImpl.h"

Inheritance diagram for llvm::BlockFrequencyInfoImplBase:
Inheritance graph


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.
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.
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 adjustLoopHeaderMass (LoopData &Loop)
 Adjust the mass of all headers in an irreducible loop.
void distributeIrrLoopHeaderMass (Distribution &Dist)
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_ostreamprint (raw_ostream &OS) const
void dump () const
Scaled64 getFloatingBlockFreq (const BlockNode &Node) const
BlockFrequency getBlockFreq (const BlockNode &Node) const
std::optional< uint64_tgetBlockProfileCount (const Function &F, const BlockNode &Node, bool AllowSynthetic=false) const
std::optional< uint64_tgetProfileCountFromFreq (const Function &F, BlockFrequency Freq, bool AllowSynthetic=false) const
bool isIrrLoopHeader (const BlockNode &Node)
void setBlockFreq (const BlockNode &Node, BlockFrequency Freq)
BlockFrequency getEntryFreq () const

Public Attributes

std::vector< FrequencyDataFreqs
 Data about each block. This is used downstream.
SparseBitVector IsIrrLoopHeader
 Whether each block is an irreducible loop header.
std::vector< WorkingDataWorking
 Loop data: see initializeLoops().
std::list< LoopDataLoops
 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 documentation lives with BlockFrequencyInfoImpl. See there for details.

Definition at line 180 of file BlockFrequencyInfoImpl.h.

Member Typedef Documentation

◆ BlockMass

Definition at line 183 of file BlockFrequencyInfoImpl.h.

◆ Scaled64

Definition at line 182 of file BlockFrequencyInfoImpl.h.

Constructor & Destructor Documentation

◆ ~BlockFrequencyInfoImplBase()

virtual llvm::BlockFrequencyInfoImplBase::~BlockFrequencyInfoImplBase ( )

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.

true unless there's an irreducible backedge.

Definition at line 374 of file BlockFrequencyInfoImpl.cpp.

References llvm::LoopBase< BlockT, LoopT >::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).

true unless aborted due to an irreducible backedge.

Definition at line 312 of file BlockFrequencyInfoImpl.cpp.

References llvm::BlockFrequencyInfoImplBase::Distribution::addBackedge(), llvm::BlockFrequencyInfoImplBase::Distribution::addExit(), llvm::BlockFrequencyInfoImplBase::Distribution::addLocal(), assert(), llvm::dbgs(), llvm::bfi_detail::getBlockName(), llvm::BlockFrequencyInfoImplBase::BlockNode::Index, llvm::BlockFrequencyInfoImplBase::LoopData::isHeader(), llvm::BlockFrequencyInfoImplBase::LoopData::isIrreducible(), and LLVM_DEBUG.

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

References llvm::BlockFrequencyInfoImplBase::Distribution::addLocal(), assert(), D, llvm::dbgs(), debugAssign(), llvm::bfi_detail::getBlockName(), llvm::bfi_detail::BlockMass::getFull(), H, LLVM_DEBUG, and llvm::BlockFrequencyInfoImplBase::Distribution::Weights.

◆ 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 explicit graph of OuterLoop (or the top-level function, if OuterLoop is nullptr). Insert them into Loops before Insert.

the LoopData nodes representing the irreducible SCCs.

Definition at line 781 of file BlockFrequencyInfoImpl.cpp.

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

◆ clear()

void BlockFrequencyInfoImplBase::clear ( )

Clear all memory.

Definition at line 292 of file BlockFrequencyInfoImpl.cpp.

References Loops.

Referenced by llvm::BlockFrequencyInfoImpl< BT >::calculate().

◆ computeLoopScale()

void BlockFrequencyInfoImplBase::computeLoopScale ( LoopData Loop)

◆ distributeIrrLoopHeaderMass()

void BlockFrequencyInfoImplBase::distributeIrrLoopHeaderMass ( Distribution Dist)

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

References assert(), llvm::BlockFrequencyInfoImplBase::LoopData::BackedgeMass, D, llvm::dbgs(), debugAssign(), llvm::BlockFrequencyInfoImplBase::LoopData::Exits, llvm::BlockFrequencyInfoImplBase::LoopData::getHeaderIndex(), llvm::bfi_detail::BlockMass::getMass(), LLVM_DEBUG, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::BlockFrequencyInfoImplBase::Distribution::Weights.

◆ dump()

void llvm::BlockFrequencyInfoImplBase::dump ( ) const

Definition at line 521 of file BlockFrequencyInfoImpl.h.

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

◆ finalizeMetrics()

void BlockFrequencyInfoImplBase::finalizeMetrics ( )

Finalize frequency metrics.

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

Definition at line 546 of file BlockFrequencyInfoImpl.cpp.

References cleanup(), convertFloatingToInteger(), llvm::dump(), llvm::ScaledNumber< uint64_t >::getLargest(), llvm::ScaledNumber< uint64_t >::getZero(), LLVM_DEBUG, and Scaled.

◆ getBlockFreq()

BlockFrequency BlockFrequencyInfoImplBase::getBlockFreq ( const BlockNode Node) const

◆ getBlockName()

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

Definition at line 628 of file BlockFrequencyInfoImpl.cpp.

◆ getBlockProfileCount()

std::optional< uint64_t > BlockFrequencyInfoImplBase::getBlockProfileCount ( const Function F,
const BlockNode Node,
bool  AllowSynthetic = false 
) const

◆ getEntryFreq()

BlockFrequency llvm::BlockFrequencyInfoImplBase::getEntryFreq ( ) const

Definition at line 536 of file BlockFrequencyInfoImpl.h.

References assert(), Freqs, and llvm::Integer.

◆ getFloatingBlockFreq()

Scaled64 BlockFrequencyInfoImplBase::getFloatingBlockFreq ( const BlockNode Node) const

◆ getLoopName()

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

◆ getProfileCountFromFreq()

std::optional< uint64_t > BlockFrequencyInfoImplBase::getProfileCountFromFreq ( const Function F,
BlockFrequency  Freq,
bool  AllowSynthetic = false 
) const

◆ isIrrLoopHeader()

bool BlockFrequencyInfoImplBase::isIrrLoopHeader ( const BlockNode Node)

◆ packageLoop()

void BlockFrequencyInfoImplBase::packageLoop ( LoopData Loop)

Package up a loop.

Definition at line 422 of file BlockFrequencyInfoImpl.cpp.

References llvm::dbgs(), llvm::bfi_detail::getBlockName(), and LLVM_DEBUG.

◆ print()

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

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

Definition at line 520 of file BlockFrequencyInfoImpl.h.

References OS.

Referenced by dump().

◆ setBlockFreq()

void BlockFrequencyInfoImplBase::setBlockFreq ( const BlockNode Node,
BlockFrequency  Freq 

◆ unwrapLoops()

void BlockFrequencyInfoImplBase::unwrapLoops ( )

Unwrap loops.

Definition at line 537 of file BlockFrequencyInfoImpl.cpp.

References Loops, Scaled, 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 801 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, llvm::bfi_detail::BlockMass::getEmpty(), I, and llvm::BlockFrequencyInfoImplBase::LoopData::Nodes.

Member Data Documentation

◆ Freqs

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

Data about each block. This is used downstream.

Definition at line 422 of file BlockFrequencyInfoImpl.h.

Referenced by getEntryFreq().

◆ IsIrrLoopHeader

SparseBitVector llvm::BlockFrequencyInfoImplBase::IsIrrLoopHeader

Whether each block is an irreducible loop header.

This is used downstream.

Definition at line 426 of file BlockFrequencyInfoImpl.h.

◆ Loops

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

Indexed information about loops.

Definition at line 432 of file BlockFrequencyInfoImpl.h.

◆ Working

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

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