Go to the documentation of this file.
14 #ifndef LLVM_LIB_TRANSFORMS_INSTRUMENTATION_CFGMST_H
15 #define LLVM_LIB_TRANSFORMS_INSTRUMENTATION_CFGMST_H
29 #define DEBUG_TYPE "cfgmst"
39 template <
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;
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;
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";
251 OS <<
" Number of Edges: " <<
AllEdges.size()
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_),
301 #undef DEBUG_TYPE // "cfgmst"
303 #endif // LLVM_LIB_TRANSFORMS_INSTRUMENTATION_CFGMST_H
This is an optimization pass for GlobalISel generic memory operations.
BBInfo & getBBInfo(const BasicBlock *BB) const
BranchProbabilityInfo * BPI
const BasicBlock & getEntryBlock() const
std::vector< std::unique_ptr< Edge > > AllEdges
BBInfo * findAndCompressGroup(BBInfo *G)
auto successors(MachineBasicBlock *BB)
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
bool succ_empty(const Instruction *I)
uint64_t scale(uint64_t Num) const
Scale a large integer.
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
uint64_t getEntryFreq() const
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Analysis providing branch probability information.
bool unionGroups(const BasicBlock *BB1, const BasicBlock *BB2)
This class implements an extremely fast bulk output stream that can only output to a stream.
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
An union-find based Minimum Spanning Tree for CFG.
std::string str() const
Return the twine contents as a std::string.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
CFGMST(Function &Func, bool InstrumentFuncEntry_, BranchProbabilityInfo *BPI_=nullptr, BlockFrequencyInfo *BFI_=nullptr)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void computeMinimumSpanningTree()
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
StringRef getName() const
Return a constant reference to the value's name.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
void stable_sort(R &&Range)
DenseMap< const BasicBlock *, std::unique_ptr< BBInfo > > BBInfos
Edge & addEdge(const BasicBlock *Src, const BasicBlock *Dest, uint64_t W)
BlockFrequency getBlockFreq(const BasicBlock *BB) const
getblockFreq - Return block frequency.
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...
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
void dumpEdges(raw_ostream &OS, const Twine &Message) const
BBInfo * findBBInfo(const BasicBlock *BB) const