14#ifndef LLVM_TRANSFORMS_INSTRUMENTATION_CFGMST_H
15#define LLVM_TRANSFORMS_INSTRUMENTATION_CFGMST_H
31#define DEBUG_TYPE "cfgmst"
39template <
class Edge,
class BBInfo>
class CFGMST {
44 std::vector<std::unique_ptr<Edge>> AllEdges;
51 bool ExitBlockFound =
false;
57 const bool InstrumentFuncEntry;
60 BBInfo *findAndCompressGroup(BBInfo *
G) {
62 G->Group = findAndCompressGroup(
static_cast<BBInfo *
>(
G->Group));
63 return static_cast<BBInfo *
>(
G->Group);
69 BBInfo *BB1G = findAndCompressGroup(&
getBBInfo(BB1));
70 BBInfo *BB2G = findAndCompressGroup(&
getBBInfo(BB2));
76 if (BB1G->Rank < BB2G->Rank)
81 if (BB1G->Rank == BB2G->Rank)
87 void handleCoroSuspendEdge(Edge *
E) {
118 (BFI !=
nullptr ? BFI->getEntryFreq().getFrequency() : 2);
120 if (InstrumentFuncEntry)
122 Edge *EntryIncoming =
nullptr, *EntryOutgoing =
nullptr,
123 *ExitOutgoing =
nullptr, *ExitIncoming =
nullptr;
124 uint64_t MaxEntryOutWeight = 0, MaxExitOutWeight = 0, MaxExitInWeight = 0;
127 EntryIncoming = &
addEdge(
nullptr, Entry, EntryWeight);
128 LLVM_DEBUG(
dbgs() <<
" Edge: from fake node to " << Entry->getName()
129 <<
" w = " << EntryWeight <<
"\n");
133 addEdge(Entry,
nullptr, EntryWeight);
137 static const uint32_t CriticalEdgeMultiplier = 1000;
142 (BFI !=
nullptr ? BFI->getBlockFreq(&BB).getFrequency() : 2);
150 if (scaleFactor <
UINT64_MAX / CriticalEdgeMultiplier)
151 scaleFactor *= CriticalEdgeMultiplier;
159 auto *
E = &
addEdge(&BB, TargetBB, Weight);
160 E->IsCritical = Critical;
161 handleCoroSuspendEdge(
E);
163 << TargetBB->
getName() <<
" w=" << Weight <<
"\n");
167 if (Weight > MaxEntryOutWeight) {
168 MaxEntryOutWeight = Weight;
174 if (TargetTI && !TargetTI->getNumSuccessors()) {
175 if (Weight > MaxExitInWeight) {
176 MaxExitInWeight = Weight;
182 ExitBlockFound =
true;
183 Edge *ExitO = &
addEdge(&BB,
nullptr, BBWeight);
184 if (BBWeight > MaxExitOutWeight) {
185 MaxExitOutWeight = BBWeight;
186 ExitOutgoing = ExitO;
188 LLVM_DEBUG(
dbgs() <<
" Edge: from " << BB.getName() <<
" to fake exit"
189 <<
" w = " << BBWeight <<
"\n");
203 uint64_t EntryInWeight = EntryWeight;
205 if (EntryInWeight >= MaxExitOutWeight &&
206 EntryInWeight * 2 < MaxExitOutWeight * 3) {
207 EntryIncoming->Weight = MaxExitOutWeight;
208 ExitOutgoing->Weight = EntryInWeight + 1;
211 if (MaxEntryOutWeight >= MaxExitInWeight &&
212 MaxEntryOutWeight * 2 < MaxExitInWeight * 3) {
213 EntryOutgoing->Weight = MaxExitInWeight;
214 ExitIncoming->Weight = MaxEntryOutWeight + 1;
219 void sortEdgesByWeight() {
221 const std::unique_ptr<Edge> &Edge2) {
222 return Edge1->Weight > Edge2->Weight;
228 void computeMinimumSpanningTree() {
232 for (
auto &Ei : AllEdges) {
235 if (Ei->IsCritical) {
236 if (Ei->DestBB && Ei->DestBB->isLandingPad()) {
237 if (unionGroups(Ei->SrcBB, Ei->DestBB))
243 for (
auto &Ei : AllEdges) {
248 if (!ExitBlockFound && Ei->SrcBB ==
nullptr)
250 if (unionGroups(Ei->SrcBB, Ei->DestBB))
258 if (!Message.
str().empty())
259 OS << Message <<
"\n";
260 OS <<
" Number of Basic Blocks: " << BBInfos.
size() <<
"\n";
261 for (
auto &BI : BBInfos) {
263 OS <<
" BB: " << (BB ==
nullptr ?
"FakeNode" : BB->
getName()) <<
" "
264 << BI.second->infoString() <<
"\n";
267 OS <<
" Number of Edges: " << AllEdges.size()
268 <<
" (*: Instrument, C: CriticalEdge, -: Removed)\n";
270 for (
auto &EI : AllEdges)
271 OS <<
" Edge " << Count++ <<
": " <<
getBBInfo(EI->SrcBB).Index <<
"-->"
272 <<
getBBInfo(EI->DestBB).Index << EI->infoString() <<
"\n";
278 auto Iter = BBInfos.
end();
280 std::tie(Iter, Inserted) = BBInfos.
insert(std::make_pair(Src,
nullptr));
283 Iter->second = std::move(std::make_unique<BBInfo>(
Index));
286 std::tie(Iter, Inserted) = BBInfos.
insert(std::make_pair(Dest,
nullptr));
289 Iter->second = std::move(std::make_unique<BBInfo>(
Index));
290 AllEdges.emplace_back(
new Edge(Src, Dest, W));
291 return *AllEdges.back();
297 :
F(Func), BPI(BPI), BFI(BFI), InstrumentFuncEntry(InstrumentFuncEntry) {
300 computeMinimumSpanningTree();
301 if (AllEdges.size() > 1 && InstrumentFuncEntry)
302 std::iter_swap(std::move(AllEdges.begin()),
303 std::move(AllEdges.begin() + AllEdges.size() - 1));
306 const std::vector<std::unique_ptr<Edge>> &
allEdges()
const {
310 std::vector<std::unique_ptr<Edge>> &
allEdges() {
return AllEdges; }
312 size_t numEdges()
const {
return AllEdges.size(); }
318 auto It = BBInfos.
find(BB);
319 assert(It->second.get() !=
nullptr);
320 return *It->second.get();
325 auto It = BBInfos.
find(BB);
326 if (It == BBInfos.
end())
328 return It->second.get();
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...
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.
std::vector< std::unique_ptr< Edge > > & allEdges()
CFGMST(Function &Func, bool InstrumentFuncEntry, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr)
Edge & addEdge(BasicBlock *Src, BasicBlock *Dest, uint64_t W)
const std::vector< std::unique_ptr< Edge > > & allEdges() const
size_t bbInfoSize() const
BBInfo * findBBInfo(const BasicBlock *BB) const
BBInfo & getBBInfo(const BasicBlock *BB) const
void dumpEdges(raw_ostream &OS, const Twine &Message) const
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
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.
bool isPresplitCoroSuspendExitEdge(const BasicBlock &Src, const BasicBlock &Dest)