LLVM 22.0.0git
|
Base class for BlockFrequencyInfoImpl. More...
#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
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 Attributes | |
std::vector< FrequencyData > | Freqs |
Data about each block. This is used downstream. | |
SparseBitVector | IsIrrLoopHeader |
Whether each block is an irreducible loop header. | |
std::vector< WorkingData > | Working |
Loop data: see initializeLoops(). | |
std::list< LoopData > | Loops |
Indexed information about loops. |
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 177 of file BlockFrequencyInfoImpl.h.
Definition at line 180 of file BlockFrequencyInfoImpl.h.
Definition at line 179 of file BlockFrequencyInfoImpl.h.
|
virtualdefault |
Virtual destructor.
Need a virtual destructor to mask the compiler warning about getBlockName().
References G.
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 addToDist(), llvm::LoopBase< BlockT, LoopT >::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).
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(), LLVM_DEBUG, and Working.
Referenced by addLoopSuccessorsToDist().
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, llvm::BlockFrequencyInfoImplBase::Weight::Local, llvm::BlockFrequencyInfoImplBase::Distribution::Weights, and Working.
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
.
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().
void BlockFrequencyInfoImplBase::clear | ( | ) |
Clear all memory.
Definition at line 292 of file BlockFrequencyInfoImpl.cpp.
References Freqs, IsIrrLoopHeader, Loops, and Working.
Referenced by llvm::BlockFrequencyInfoImpl< BT >::calculate().
void BlockFrequencyInfoImplBase::computeLoopScale | ( | LoopData & | Loop | ) |
Compute the loop scale for a loop.
Definition at line 387 of file BlockFrequencyInfoImpl.cpp.
References llvm::dbgs(), llvm::bfi_detail::BlockMass::getFull(), getLoopName(), llvm::ScaledNumber< DigitsT >::inverse(), llvm::bfi_detail::BlockMass::isEmpty(), LLVM_DEBUG, and llvm::bfi_detail::BlockMass::toScaled().
void BlockFrequencyInfoImplBase::distributeIrrLoopHeaderMass | ( | Distribution & | Dist | ) |
Definition at line 849 of file BlockFrequencyInfoImpl.cpp.
References assert(), D(), debugAssign(), llvm::bfi_detail::BlockMass::getFull(), LLVM_DEBUG, llvm::BlockFrequencyInfoImplBase::Weight::Local, llvm::BlockFrequencyInfoImplBase::Distribution::Weights, and Working.
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::Weight::Backedge, llvm::BlockFrequencyInfoImplBase::LoopData::BackedgeMass, D(), llvm::dbgs(), debugAssign(), llvm::BlockFrequencyInfoImplBase::Weight::Exit, llvm::BlockFrequencyInfoImplBase::LoopData::Exits, llvm::BlockFrequencyInfoImplBase::LoopData::getHeaderIndex(), LLVM_DEBUG, llvm::BlockFrequencyInfoImplBase::Weight::Local, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::BlockFrequencyInfoImplBase::Distribution::Weights, and Working.
|
inline |
Definition at line 518 of file BlockFrequencyInfoImpl.h.
References llvm::dbgs(), and print().
Referenced by llvm::BlockFrequencyInfoImpl< BasicBlock >::print().
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(), Freqs, llvm::ScaledNumber< uint64_t >::getLargest(), llvm::ScaledNumber< uint64_t >::getZero(), LLVM_DEBUG, Scaled, and Working.
Referenced by llvm::BlockFrequencyInfoImpl< BT >::calculate().
BlockFrequency BlockFrequencyInfoImplBase::getBlockFreq | ( | const BlockNode & | Node | ) | const |
Definition at line 568 of file BlockFrequencyInfoImpl.cpp.
References llvm::CheckBFIUnknownBlockQueries, Freqs, llvm::bfi_detail::getBlockName(), llvm::report_fatal_error(), and llvm::raw_svector_ostream::str().
Referenced by llvm::BlockFrequencyInfoImpl< BasicBlock >::getBlockFreq(), and getBlockProfileCount().
Definition at line 628 of file BlockFrequencyInfoImpl.cpp.
std::optional< uint64_t > BlockFrequencyInfoImplBase::getBlockProfileCount | ( | const Function & | F, |
const BlockNode & | Node, | ||
bool | AllowSynthetic = false ) const |
Definition at line 584 of file BlockFrequencyInfoImpl.cpp.
References F, getBlockFreq(), and getProfileCountFromFreq().
Referenced by llvm::BlockFrequencyInfoImpl< BasicBlock >::getBlockProfileCount(), and llvm::BlockFrequencyInfoImpl< BT >::print().
|
inline |
Definition at line 533 of file BlockFrequencyInfoImpl.h.
References assert(), Freqs, and llvm::Integer.
Referenced by llvm::BlockFrequencyInfoImpl< BasicBlock >::calculate(), and getProfileCountFromFreq().
Definition at line 614 of file BlockFrequencyInfoImpl.cpp.
References Freqs, and llvm::ScaledNumber< uint64_t >::getZero().
Referenced by llvm::BlockFrequencyInfoImpl< BasicBlock >::getFloatingBlockFreq().
Definition at line 633 of file BlockFrequencyInfoImpl.cpp.
References llvm::bfi_detail::getBlockName(), and llvm::LoopBase< BlockT, LoopT >::getHeader().
Referenced by computeLoopScale(), and packageLoop().
std::optional< uint64_t > BlockFrequencyInfoImplBase::getProfileCountFromFreq | ( | const Function & | F, |
BlockFrequency | Freq, | ||
bool | AllowSynthetic = false ) const |
Definition at line 590 of file BlockFrequencyInfoImpl.cpp.
References F, getEntryFreq(), llvm::BlockFrequency::getFrequency(), llvm::APInt::getLimitedValue(), llvm::APInt::lshr(), and llvm::APInt::udiv().
Referenced by getBlockProfileCount(), and llvm::BlockFrequencyInfoImpl< BasicBlock >::getProfileCountFromFreq().
Definition at line 607 of file BlockFrequencyInfoImpl.cpp.
References IsIrrLoopHeader.
Referenced by llvm::BlockFrequencyInfoImpl< BasicBlock >::isIrrLoopHeader().
void BlockFrequencyInfoImplBase::packageLoop | ( | LoopData & | Loop | ) |
Package up a loop.
Definition at line 422 of file BlockFrequencyInfoImpl.cpp.
References llvm::dbgs(), llvm::bfi_detail::getBlockName(), getLoopName(), LLVM_DEBUG, and Working.
|
inlinevirtual |
Reimplemented in llvm::BlockFrequencyInfoImpl< BT >, llvm::BlockFrequencyInfoImpl< BasicBlock >, and llvm::BlockFrequencyInfoImpl< MachineBasicBlock >.
Definition at line 517 of file BlockFrequencyInfoImpl.h.
Referenced by dump().
void BlockFrequencyInfoImplBase::setBlockFreq | ( | const BlockNode & | Node, |
BlockFrequency | Freq ) |
Definition at line 620 of file BlockFrequencyInfoImpl.cpp.
References assert(), Freqs, and llvm::BlockFrequency::getFrequency().
Referenced by llvm::BlockFrequencyInfoImpl< BT >::setBlockFreq().
void BlockFrequencyInfoImplBase::unwrapLoops | ( | ) |
Unwrap loops.
Definition at line 537 of file BlockFrequencyInfoImpl.cpp.
References Freqs, Loops, Scaled, llvm::bfi_detail::BlockMass::toScaled(), unwrapLoop(), and Working.
Referenced by llvm::BlockFrequencyInfoImpl< BT >::calculate().
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, llvm::BlockFrequencyInfoImplBase::LoopData::Nodes, and Working.
std::vector<FrequencyData> llvm::BlockFrequencyInfoImplBase::Freqs |
Data about each block. This is used downstream.
Definition at line 419 of file BlockFrequencyInfoImpl.h.
Referenced by clear(), finalizeMetrics(), getBlockFreq(), getEntryFreq(), getFloatingBlockFreq(), llvm::BlockFrequencyInfoImpl< BT >::setBlockFreq(), setBlockFreq(), unwrapLoops(), and llvm::BlockFrequencyInfoImpl< BT >::verifyMatch().
SparseBitVector llvm::BlockFrequencyInfoImplBase::IsIrrLoopHeader |
Whether each block is an irreducible loop header.
This is used downstream.
Definition at line 423 of file BlockFrequencyInfoImpl.h.
Referenced by clear(), and isIrrLoopHeader().
std::list<LoopData> llvm::BlockFrequencyInfoImplBase::Loops |
Indexed information about loops.
Definition at line 429 of file BlockFrequencyInfoImpl.h.
Referenced by analyzeIrreducible(), clear(), and unwrapLoops().
std::vector<WorkingData> llvm::BlockFrequencyInfoImplBase::Working |
Loop data: see initializeLoops().
Definition at line 426 of file BlockFrequencyInfoImpl.h.
Referenced by addToDist(), adjustLoopHeaderMass(), clear(), distributeIrrLoopHeaderMass(), distributeMass(), finalizeMetrics(), packageLoop(), unwrapLoops(), and updateLoopWithIrreducible().