An union-find based Minimum Spanning Tree for CFG. More...
#include "Transforms/Instrumentation/CFGMST.h"
Public Member Functions | |
| BBInfo * | findAndCompressGroup (BBInfo *G) |
| bool | unionGroups (const BasicBlock *BB1, const BasicBlock *BB2) |
| BBInfo & | getBBInfo (const BasicBlock *BB) const |
| BBInfo * | findBBInfo (const BasicBlock *BB) const |
| void | buildEdges () |
| void | sortEdgesByWeight () |
| void | computeMinimumSpanningTree () |
| void | dumpEdges (raw_ostream &OS, const Twine &Message) const |
| Edge & | addEdge (const BasicBlock *Src, const BasicBlock *Dest, uint64_t W) |
| CFGMST (Function &Func, BranchProbabilityInfo *BPI_=nullptr, BlockFrequencyInfo *BFI_=nullptr) | |
Public Attributes | |
| Function & | F |
| std::vector< std::unique_ptr< Edge > > | AllEdges |
| DenseMap< const BasicBlock *, std::unique_ptr< BBInfo > > | BBInfos |
| bool | ExitBlockFound = false |
| BranchProbabilityInfo * | BPI |
| BlockFrequencyInfo * | BFI |
Detailed Description
template<class Edge, class BBInfo>
class llvm::CFGMST< Edge, BBInfo >
An union-find based Minimum Spanning Tree for CFG.
Implements a Union-find algorithm to compute Minimum Spanning Tree for a given CFG.
Constructor & Destructor Documentation
◆ CFGMST()
|
inline |
Definition at line 277 of file CFGMST.h.
References llvm::CFGMST< Edge, BBInfo >::buildEdges(), llvm::CFGMST< Edge, BBInfo >::computeMinimumSpanningTree(), and llvm::CFGMST< Edge, BBInfo >::sortEdgesByWeight().
Member Function Documentation
◆ addEdge()
|
inline |
Definition at line 255 of file CFGMST.h.
References llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), and llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::size().
Referenced by llvm::CFGMST< Edge, BBInfo >::buildEdges().
◆ buildEdges()
|
inline |
Definition at line 99 of file CFGMST.h.
References llvm::CFGMST< Edge, BBInfo >::addEdge(), llvm::Function::begin(), llvm::CFGMST< Edge, BBInfo >::BFI, llvm::CFGMST< Edge, BBInfo >::BPI, llvm::dbgs(), E, llvm::Function::end(), llvm::BlockFrequencyInfo::getBlockFreq(), llvm::BranchProbabilityInfo::getEdgeProbability(), llvm::Function::getEntryBlock(), llvm::BlockFrequencyInfo::getEntryFreq(), llvm::BlockFrequency::getFrequency(), llvm::Value::getName(), llvm::Instruction::getNumSuccessors(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::isCriticalEdge(), LLVM_DEBUG, llvm::BranchProbability::scale(), llvm::succ_empty(), llvm::successors(), and UINT64_MAX.
Referenced by llvm::CFGMST< Edge, BBInfo >::CFGMST().
◆ computeMinimumSpanningTree()
|
inline |
Definition at line 208 of file CFGMST.h.
References llvm::CFGMST< Edge, BBInfo >::unionGroups().
Referenced by llvm::CFGMST< Edge, BBInfo >::CFGMST().
◆ dumpEdges()
|
inline |
Definition at line 236 of file CFGMST.h.
References llvm::CFGMST< Edge, BBInfo >::getBBInfo(), llvm::Value::getName(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::size(), and llvm::Twine::str().
Referenced by llvm::createPGOInstrumentationUseLegacyPass().
◆ findAndCompressGroup()
|
inline |
Definition at line 54 of file CFGMST.h.
Referenced by llvm::CFGMST< Edge, BBInfo >::unionGroups().
◆ findBBInfo()
|
inline |
Definition at line 89 of file CFGMST.h.
References llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), and llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find().
Referenced by llvm::createPGOInstrumentationUseLegacyPass().
◆ getBBInfo()
|
inline |
Definition at line 82 of file CFGMST.h.
References assert(), and llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find().
Referenced by llvm::createPGOInstrumentationUseLegacyPass(), llvm::CFGMST< Edge, BBInfo >::dumpEdges(), and llvm::CFGMST< Edge, BBInfo >::unionGroups().
◆ sortEdgesByWeight()
|
inline |
Definition at line 198 of file CFGMST.h.
Referenced by llvm::CFGMST< Edge, BBInfo >::CFGMST().
◆ unionGroups()
|
inline |
Definition at line 62 of file CFGMST.h.
References llvm::CFGMST< Edge, BBInfo >::findAndCompressGroup(), and llvm::CFGMST< Edge, BBInfo >::getBBInfo().
Referenced by llvm::CFGMST< Edge, BBInfo >::computeMinimumSpanningTree().
Member Data Documentation
◆ AllEdges
| std::vector<std::unique_ptr<Edge> > llvm::CFGMST< Edge, BBInfo >::AllEdges |
Definition at line 44 of file CFGMST.h.
Referenced by llvm::createPGOInstrumentationUseLegacyPass().
◆ BBInfos
| DenseMap<const BasicBlock *, std::unique_ptr<BBInfo> > llvm::CFGMST< Edge, BBInfo >::BBInfos |
Definition at line 47 of file CFGMST.h.
Referenced by llvm::createPGOInstrumentationUseLegacyPass().
◆ BFI
| BlockFrequencyInfo* llvm::CFGMST< Edge, BBInfo >::BFI |
Definition at line 274 of file CFGMST.h.
Referenced by llvm::CFGMST< Edge, BBInfo >::buildEdges().
◆ BPI
| BranchProbabilityInfo* llvm::CFGMST< Edge, BBInfo >::BPI |
Definition at line 273 of file CFGMST.h.
Referenced by llvm::CFGMST< Edge, BBInfo >::buildEdges().
◆ ExitBlockFound
| bool llvm::CFGMST< Edge, BBInfo >::ExitBlockFound = false |
◆ F
| Function& llvm::CFGMST< Edge, BBInfo >::F |
The documentation for this class was generated from the following file:
- lib/Transforms/Instrumentation/CFGMST.h
