14#ifndef LLVM_TRANSFORMS_INSTRUMENTATION_CFGMST_H
15#define LLVM_TRANSFORMS_INSTRUMENTATION_CFGMST_H
29#define DEBUG_TYPE "cfgmst"
39template <
class Edge,
class BBInfo>
class CFGMST {
58 return static_cast<BBInfo *
>(
G->Group);
71 if (BB1G->Rank < BB2G->Rank)
76 if (BB1G->Rank == BB2G->Rank)
85 assert(It->second.get() !=
nullptr);
86 return *It->second.get();
94 return It->second.get();
108 Edge *EntryIncoming =
nullptr, *EntryOutgoing =
nullptr,
109 *ExitOutgoing =
nullptr, *ExitIncoming =
nullptr;
110 uint64_t MaxEntryOutWeight = 0, MaxExitOutWeight = 0, MaxExitInWeight = 0;
113 EntryIncoming = &
addEdge(
nullptr, Entry, EntryWeight);
114 LLVM_DEBUG(
dbgs() <<
" Edge: from fake node to " << Entry->getName()
115 <<
" w = " << EntryWeight <<
"\n");
119 addEdge(Entry,
nullptr, EntryWeight);
123 static const uint32_t CriticalEdgeMultiplier = 1000;
136 if (scaleFactor <
UINT64_MAX / CriticalEdgeMultiplier)
137 scaleFactor *= CriticalEdgeMultiplier;
145 auto *
E = &
addEdge(&BB, TargetBB, Weight);
146 E->IsCritical = Critical;
148 << TargetBB->
getName() <<
" w=" << Weight <<
"\n");
152 if (Weight > MaxEntryOutWeight) {
153 MaxEntryOutWeight = Weight;
159 if (TargetTI && !TargetTI->getNumSuccessors()) {
160 if (Weight > MaxExitInWeight) {
161 MaxExitInWeight = Weight;
168 Edge *ExitO = &
addEdge(&BB,
nullptr, BBWeight);
169 if (BBWeight > MaxExitOutWeight) {
170 MaxExitOutWeight = BBWeight;
171 ExitOutgoing = ExitO;
173 LLVM_DEBUG(
dbgs() <<
" Edge: from " << BB.getName() <<
" to fake exit"
174 <<
" w = " << BBWeight <<
"\n");
188 uint64_t EntryInWeight = EntryWeight;
190 if (EntryInWeight >= MaxExitOutWeight &&
191 EntryInWeight * 2 < MaxExitOutWeight * 3) {
192 EntryIncoming->Weight = MaxExitOutWeight;
193 ExitOutgoing->Weight = EntryInWeight + 1;
196 if (MaxEntryOutWeight >= MaxExitInWeight &&
197 MaxEntryOutWeight * 2 < MaxExitInWeight * 3) {
198 EntryOutgoing->Weight = MaxExitInWeight;
199 ExitIncoming->Weight = MaxEntryOutWeight + 1;
206 const std::unique_ptr<Edge> &Edge2) {
207 return Edge1->Weight > Edge2->Weight;
220 if (Ei->IsCritical) {
221 if (Ei->DestBB && Ei->DestBB->isLandingPad()) {
242 if (!Message.
str().empty())
243 OS << Message <<
"\n";
244 OS <<
" Number of Basic Blocks: " <<
BBInfos.size() <<
"\n";
247 OS <<
" BB: " << (BB ==
nullptr ?
"FakeNode" : BB->
getName()) <<
" "
248 << BI.second->infoString() <<
"\n";
252 <<
" (*: Instrument, C: CriticalEdge, -: Removed)\n";
255 OS <<
" Edge " << Count++ <<
": " <<
getBBInfo(EI->SrcBB).Index <<
"-->"
256 <<
getBBInfo(EI->DestBB).Index << EI->infoString() <<
"\n";
264 std::tie(Iter, Inserted) =
BBInfos.insert(std::make_pair(Src,
nullptr));
267 Iter->second = std::move(std::make_unique<BBInfo>(
Index));
270 std::tie(Iter, Inserted) =
BBInfos.insert(std::make_pair(Dest,
nullptr));
273 Iter->second = std::move(std::make_unique<BBInfo>(
Index));
274 AllEdges.emplace_back(
new Edge(Src, Dest, W));
288 :
F(Func),
BPI(BPI_),
BFI(BFI_),
294 std::iter_swap(std::move(
AllEdges.begin()),
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Basic Block Representation.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
uint64_t getEntryFreq() const
BlockFrequency getBlockFreq(const BasicBlock *BB) const
getblockFreq - Return block frequency.
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
Analysis providing branch probability information.
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
uint64_t scale(uint64_t Num) const
Scale a large integer.
An union-find based Minimum Spanning Tree for CFG.
void computeMinimumSpanningTree()
Edge & addEdge(BasicBlock *Src, BasicBlock *Dest, uint64_t W)
BranchProbabilityInfo * BPI
std::vector< std::unique_ptr< Edge > > AllEdges
bool unionGroups(const BasicBlock *BB1, const BasicBlock *BB2)
BBInfo * findBBInfo(const BasicBlock *BB) const
BBInfo & getBBInfo(const BasicBlock *BB) const
DenseMap< const BasicBlock *, std::unique_ptr< BBInfo > > BBInfos
CFGMST(Function &Func, bool InstrumentFuncEntry_, BranchProbabilityInfo *BPI_=nullptr, BlockFrequencyInfo *BFI_=nullptr)
BBInfo * findAndCompressGroup(BBInfo *G)
void dumpEdges(raw_ostream &OS, const Twine &Message) const
const BasicBlock & getEntryBlock() const
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
std::string str() const
Return the twine contents as a std::string.
StringRef getName() const
Return a constant reference to the value's name.
This class implements an extremely fast bulk output stream that can only output to a stream.
This is an optimization pass for GlobalISel generic memory operations.
void stable_sort(R &&Range)
bool succ_empty(const Instruction *I)
auto successors(const MachineBasicBlock *BB)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.