LLVM 17.0.0git
Public Member Functions | Public Attributes | List of all members
llvm::CFGMST< Edge, BBInfo > Class Template Reference

An union-find based Minimum Spanning Tree for CFG. More...

#include "llvm/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 (BasicBlock *Src, BasicBlock *Dest, uint64_t W)
 
 CFGMST (Function &Func, bool InstrumentFuncEntry_, 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
 
bool InstrumentFuncEntry
 

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.

Definition at line 39 of file CFGMST.h.

Constructor & Destructor Documentation

◆ CFGMST()

template<class Edge , class BBInfo >
llvm::CFGMST< Edge, BBInfo >::CFGMST ( Function &  Func,
bool  InstrumentFuncEntry_,
BranchProbabilityInfo *  BPI_ = nullptr,
BlockFrequencyInfo *  BFI_ = nullptr 
)
inline

Definition at line 285 of file CFGMST.h.

References llvm::CFGMST< Edge, BBInfo >::AllEdges, llvm::CFGMST< Edge, BBInfo >::buildEdges(), llvm::CFGMST< Edge, BBInfo >::computeMinimumSpanningTree(), llvm::CFGMST< Edge, BBInfo >::InstrumentFuncEntry, and llvm::CFGMST< Edge, BBInfo >::sortEdgesByWeight().

Member Function Documentation

◆ addEdge()

template<class Edge , class BBInfo >
Edge & llvm::CFGMST< Edge, BBInfo >::addEdge ( BasicBlock *  Src,
BasicBlock *  Dest,
uint64_t  W 
)
inline

Definition at line 260 of file CFGMST.h.

References llvm::CFGMST< Edge, BBInfo >::AllEdges, and llvm::CFGMST< Edge, BBInfo >::BBInfos.

Referenced by llvm::CFGMST< Edge, BBInfo >::buildEdges(), and getInstrBB().

◆ buildEdges()

template<class Edge , class BBInfo >
void llvm::CFGMST< Edge, BBInfo >::buildEdges ( )
inline

Definition at line 100 of file CFGMST.h.

References llvm::CFGMST< Edge, BBInfo >::addEdge(), llvm::CFGMST< Edge, BBInfo >::BFI, llvm::CFGMST< Edge, BBInfo >::BPI, llvm::dbgs(), E, llvm::CFGMST< Edge, BBInfo >::ExitBlockFound, llvm::CFGMST< Edge, BBInfo >::F, 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::CFGMST< Edge, BBInfo >::InstrumentFuncEntry, llvm::isCriticalEdge(), LLVM_DEBUG, llvm::BranchProbability::scale(), llvm::succ_empty(), llvm::successors(), and UINT64_MAX.

Referenced by llvm::CFGMST< Edge, BBInfo >::CFGMST().

◆ computeMinimumSpanningTree()

template<class Edge , class BBInfo >
void llvm::CFGMST< Edge, BBInfo >::computeMinimumSpanningTree ( )
inline

Definition at line 213 of file CFGMST.h.

References llvm::CFGMST< Edge, BBInfo >::AllEdges, llvm::CFGMST< Edge, BBInfo >::ExitBlockFound, and llvm::CFGMST< Edge, BBInfo >::unionGroups().

Referenced by llvm::CFGMST< Edge, BBInfo >::CFGMST().

◆ dumpEdges()

template<class Edge , class BBInfo >
void llvm::CFGMST< Edge, BBInfo >::dumpEdges ( raw_ostream &  OS,
const Twine &  Message 
) const
inline

Definition at line 241 of file CFGMST.h.

References llvm::CFGMST< Edge, BBInfo >::AllEdges, llvm::CFGMST< Edge, BBInfo >::BBInfos, llvm::CFGMST< Edge, BBInfo >::getBBInfo(), llvm::Value::getName(), OS, and llvm::Twine::str().

◆ findAndCompressGroup()

template<class Edge , class BBInfo >
BBInfo * llvm::CFGMST< Edge, BBInfo >::findAndCompressGroup ( BBInfo *  G)
inline

Definition at line 55 of file CFGMST.h.

References llvm::CFGMST< Edge, BBInfo >::findAndCompressGroup(), and G.

Referenced by llvm::CFGMST< Edge, BBInfo >::findAndCompressGroup(), and llvm::CFGMST< Edge, BBInfo >::unionGroups().

◆ findBBInfo()

template<class Edge , class BBInfo >
BBInfo * llvm::CFGMST< Edge, BBInfo >::findBBInfo ( const BasicBlock *  BB) const
inline

Definition at line 90 of file CFGMST.h.

References llvm::CFGMST< Edge, BBInfo >::BBInfos.

◆ getBBInfo()

template<class Edge , class BBInfo >
BBInfo & llvm::CFGMST< Edge, BBInfo >::getBBInfo ( const BasicBlock *  BB) const
inline

Definition at line 83 of file CFGMST.h.

References assert(), and llvm::CFGMST< Edge, BBInfo >::BBInfos.

Referenced by llvm::CFGMST< Edge, BBInfo >::dumpEdges(), and llvm::CFGMST< Edge, BBInfo >::unionGroups().

◆ sortEdgesByWeight()

template<class Edge , class BBInfo >
void llvm::CFGMST< Edge, BBInfo >::sortEdgesByWeight ( )
inline

Definition at line 204 of file CFGMST.h.

References llvm::CFGMST< Edge, BBInfo >::AllEdges, and llvm::stable_sort().

Referenced by llvm::CFGMST< Edge, BBInfo >::CFGMST().

◆ unionGroups()

template<class Edge , class BBInfo >
bool llvm::CFGMST< Edge, BBInfo >::unionGroups ( const BasicBlock *  BB1,
const BasicBlock *  BB2 
)
inline

Definition at line 63 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

template<class Edge , class BBInfo >
std::vector<std::unique_ptr<Edge> > llvm::CFGMST< Edge, BBInfo >::AllEdges

Definition at line 45 of file CFGMST.h.

Referenced by llvm::CFGMST< Edge, BBInfo >::addEdge(), llvm::CFGMST< Edge, BBInfo >::CFGMST(), llvm::CFGMST< Edge, BBInfo >::computeMinimumSpanningTree(), dumpEdges(), llvm::CFGMST< Edge, BBInfo >::dumpEdges(), and llvm::CFGMST< Edge, BBInfo >::sortEdgesByWeight().

◆ BBInfos

template<class Edge , class BBInfo >
DenseMap<const BasicBlock *, std::unique_ptr<BBInfo> > llvm::CFGMST< Edge, BBInfo >::BBInfos

Definition at line 48 of file CFGMST.h.

Referenced by llvm::CFGMST< Edge, BBInfo >::addEdge(), llvm::CFGMST< Edge, BBInfo >::dumpEdges(), llvm::CFGMST< Edge, BBInfo >::findBBInfo(), and llvm::CFGMST< Edge, BBInfo >::getBBInfo().

◆ BFI

template<class Edge , class BBInfo >
BlockFrequencyInfo* llvm::CFGMST< Edge, BBInfo >::BFI

Definition at line 279 of file CFGMST.h.

Referenced by llvm::CFGMST< Edge, BBInfo >::buildEdges().

◆ BPI

template<class Edge , class BBInfo >
BranchProbabilityInfo* llvm::CFGMST< Edge, BBInfo >::BPI

Definition at line 278 of file CFGMST.h.

Referenced by llvm::CFGMST< Edge, BBInfo >::buildEdges().

◆ ExitBlockFound

template<class Edge , class BBInfo >
bool llvm::CFGMST< Edge, BBInfo >::ExitBlockFound = false

Definition at line 52 of file CFGMST.h.

Referenced by llvm::CFGMST< Edge, BBInfo >::buildEdges(), and llvm::CFGMST< Edge, BBInfo >::computeMinimumSpanningTree().

◆ F

template<class Edge , class BBInfo >
Function& llvm::CFGMST< Edge, BBInfo >::F

Definition at line 41 of file CFGMST.h.

Referenced by llvm::CFGMST< Edge, BBInfo >::buildEdges().

◆ InstrumentFuncEntry

template<class Edge , class BBInfo >
bool llvm::CFGMST< Edge, BBInfo >::InstrumentFuncEntry

Definition at line 282 of file CFGMST.h.

Referenced by llvm::CFGMST< Edge, BBInfo >::buildEdges(), and llvm::CFGMST< Edge, BBInfo >::CFGMST().

The documentation for this class was generated from the following file:
Generated on Thu Jun 8 2023 16:25:16 for LLVM by doxygen 1.9.6