LLVM  14.0.0git
CFGMST.h
Go to the documentation of this file.
1 //===-- CFGMST.h - Minimum Spanning Tree for CFG ----------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements a Union-find algorithm to compute Minimum Spanning Tree
10 // for a given CFG.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_LIB_TRANSFORMS_INSTRUMENTATION_CFGMST_H
15 #define LLVM_LIB_TRANSFORMS_INSTRUMENTATION_CFGMST_H
16 
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/Analysis/CFG.h"
23 #include "llvm/Support/Debug.h"
26 #include <utility>
27 #include <vector>
28 
29 #define DEBUG_TYPE "cfgmst"
30 
31 using namespace llvm;
32 
33 namespace llvm {
34 
35 /// An union-find based Minimum Spanning Tree for CFG
36 ///
37 /// Implements a Union-find algorithm to compute Minimum Spanning Tree
38 /// for a given CFG.
39 template <class Edge, class BBInfo> class CFGMST {
40 public:
42 
43  // Store all the edges in CFG. It may contain some stale edges
44  // when Removed is set.
45  std::vector<std::unique_ptr<Edge>> AllEdges;
46 
47  // This map records the auxiliary information for each BB.
49 
50  // Whehter the function has an exit block with no successors.
51  // (For function with an infinite loop, this block may be absent)
52  bool ExitBlockFound = false;
53 
54  // Find the root group of the G and compress the path from G to the root.
55  BBInfo *findAndCompressGroup(BBInfo *G) {
56  if (G->Group != G)
57  G->Group = findAndCompressGroup(static_cast<BBInfo *>(G->Group));
58  return static_cast<BBInfo *>(G->Group);
59  }
60 
61  // Union BB1 and BB2 into the same group and return true.
62  // Returns false if BB1 and BB2 are already in the same group.
63  bool unionGroups(const BasicBlock *BB1, const BasicBlock *BB2) {
64  BBInfo *BB1G = findAndCompressGroup(&getBBInfo(BB1));
65  BBInfo *BB2G = findAndCompressGroup(&getBBInfo(BB2));
66 
67  if (BB1G == BB2G)
68  return false;
69 
70  // Make the smaller rank tree a direct child or the root of high rank tree.
71  if (BB1G->Rank < BB2G->Rank)
72  BB1G->Group = BB2G;
73  else {
74  BB2G->Group = BB1G;
75  // If the ranks are the same, increment root of one tree by one.
76  if (BB1G->Rank == BB2G->Rank)
77  BB1G->Rank++;
78  }
79  return true;
80  }
81 
82  // Give BB, return the auxiliary information.
83  BBInfo &getBBInfo(const BasicBlock *BB) const {
84  auto It = BBInfos.find(BB);
85  assert(It->second.get() != nullptr);
86  return *It->second.get();
87  }
88 
89  // Give BB, return the auxiliary information if it's available.
90  BBInfo *findBBInfo(const BasicBlock *BB) const {
91  auto It = BBInfos.find(BB);
92  if (It == BBInfos.end())
93  return nullptr;
94  return It->second.get();
95  }
96 
97  // Traverse the CFG using a stack. Find all the edges and assign the weight.
98  // Edges with large weight will be put into MST first so they are less likely
99  // to be instrumented.
100  void buildEdges() {
101  LLVM_DEBUG(dbgs() << "Build Edge on " << F.getName() << "\n");
102 
103  const BasicBlock *Entry = &(F.getEntryBlock());
104  uint64_t EntryWeight = (BFI != nullptr ? BFI->getEntryFreq() : 2);
105  // If we want to instrument the entry count, lower the weight to 0.
107  EntryWeight = 0;
108  Edge *EntryIncoming = nullptr, *EntryOutgoing = nullptr,
109  *ExitOutgoing = nullptr, *ExitIncoming = nullptr;
110  uint64_t MaxEntryOutWeight = 0, MaxExitOutWeight = 0, MaxExitInWeight = 0;
111 
112  // Add a fake edge to the entry.
113  EntryIncoming = &addEdge(nullptr, Entry, EntryWeight);
114  LLVM_DEBUG(dbgs() << " Edge: from fake node to " << Entry->getName()
115  << " w = " << EntryWeight << "\n");
116 
117  // Special handling for single BB functions.
118  if (succ_empty(Entry)) {
119  addEdge(Entry, nullptr, EntryWeight);
120  return;
121  }
122 
123  static const uint32_t CriticalEdgeMultiplier = 1000;
124 
125  for (BasicBlock &BB : F) {
126  Instruction *TI = BB.getTerminator();
127  uint64_t BBWeight =
128  (BFI != nullptr ? BFI->getBlockFreq(&BB).getFrequency() : 2);
129  uint64_t Weight = 2;
130  if (int successors = TI->getNumSuccessors()) {
131  for (int i = 0; i != successors; ++i) {
132  BasicBlock *TargetBB = TI->getSuccessor(i);
133  bool Critical = isCriticalEdge(TI, i);
134  uint64_t scaleFactor = BBWeight;
135  if (Critical) {
136  if (scaleFactor < UINT64_MAX / CriticalEdgeMultiplier)
137  scaleFactor *= CriticalEdgeMultiplier;
138  else
139  scaleFactor = UINT64_MAX;
140  }
141  if (BPI != nullptr)
142  Weight = BPI->getEdgeProbability(&BB, TargetBB).scale(scaleFactor);
143  if (Weight == 0)
144  Weight++;
145  auto *E = &addEdge(&BB, TargetBB, Weight);
146  E->IsCritical = Critical;
147  LLVM_DEBUG(dbgs() << " Edge: from " << BB.getName() << " to "
148  << TargetBB->getName() << " w=" << Weight << "\n");
149 
150  // Keep track of entry/exit edges:
151  if (&BB == Entry) {
152  if (Weight > MaxEntryOutWeight) {
153  MaxEntryOutWeight = Weight;
154  EntryOutgoing = E;
155  }
156  }
157 
158  auto *TargetTI = TargetBB->getTerminator();
159  if (TargetTI && !TargetTI->getNumSuccessors()) {
160  if (Weight > MaxExitInWeight) {
161  MaxExitInWeight = Weight;
162  ExitIncoming = E;
163  }
164  }
165  }
166  } else {
167  ExitBlockFound = true;
168  Edge *ExitO = &addEdge(&BB, nullptr, BBWeight);
169  if (BBWeight > MaxExitOutWeight) {
170  MaxExitOutWeight = BBWeight;
171  ExitOutgoing = ExitO;
172  }
173  LLVM_DEBUG(dbgs() << " Edge: from " << BB.getName() << " to fake exit"
174  << " w = " << BBWeight << "\n");
175  }
176  }
177 
178  // Entry/exit edge adjustment heurisitic:
179  // prefer instrumenting entry edge over exit edge
180  // if possible. Those exit edges may never have a chance to be
181  // executed (for instance the program is an event handling loop)
182  // before the profile is asynchronously dumped.
183  //
184  // If EntryIncoming and ExitOutgoing has similar weight, make sure
185  // ExitOutging is selected as the min-edge. Similarly, if EntryOutgoing
186  // and ExitIncoming has similar weight, make sure ExitIncoming becomes
187  // the min-edge.
188  uint64_t EntryInWeight = EntryWeight;
189 
190  if (EntryInWeight >= MaxExitOutWeight &&
191  EntryInWeight * 2 < MaxExitOutWeight * 3) {
192  EntryIncoming->Weight = MaxExitOutWeight;
193  ExitOutgoing->Weight = EntryInWeight + 1;
194  }
195 
196  if (MaxEntryOutWeight >= MaxExitInWeight &&
197  MaxEntryOutWeight * 2 < MaxExitInWeight * 3) {
198  EntryOutgoing->Weight = MaxExitInWeight;
199  ExitIncoming->Weight = MaxEntryOutWeight + 1;
200  }
201  }
202 
203  // Sort CFG edges based on its weight.
205  llvm::stable_sort(AllEdges, [](const std::unique_ptr<Edge> &Edge1,
206  const std::unique_ptr<Edge> &Edge2) {
207  return Edge1->Weight > Edge2->Weight;
208  });
209  }
210 
211  // Traverse all the edges and compute the Minimum Weight Spanning Tree
212  // using union-find algorithm.
214  // First, put all the critical edge with landing-pad as the Dest to MST.
215  // This works around the insufficient support of critical edges split
216  // when destination BB is a landing pad.
217  for (auto &Ei : AllEdges) {
218  if (Ei->Removed)
219  continue;
220  if (Ei->IsCritical) {
221  if (Ei->DestBB && Ei->DestBB->isLandingPad()) {
222  if (unionGroups(Ei->SrcBB, Ei->DestBB))
223  Ei->InMST = true;
224  }
225  }
226  }
227 
228  for (auto &Ei : AllEdges) {
229  if (Ei->Removed)
230  continue;
231  // If we detect infinite loops, force
232  // instrumenting the entry edge:
233  if (!ExitBlockFound && Ei->SrcBB == nullptr)
234  continue;
235  if (unionGroups(Ei->SrcBB, Ei->DestBB))
236  Ei->InMST = true;
237  }
238  }
239 
240  // Dump the Debug information about the instrumentation.
241  void dumpEdges(raw_ostream &OS, const Twine &Message) const {
242  if (!Message.str().empty())
243  OS << Message << "\n";
244  OS << " Number of Basic Blocks: " << BBInfos.size() << "\n";
245  for (auto &BI : BBInfos) {
246  const BasicBlock *BB = BI.first;
247  OS << " BB: " << (BB == nullptr ? "FakeNode" : BB->getName()) << " "
248  << BI.second->infoString() << "\n";
249  }
250 
251  OS << " Number of Edges: " << AllEdges.size()
252  << " (*: Instrument, C: CriticalEdge, -: Removed)\n";
253  uint32_t Count = 0;
254  for (auto &EI : AllEdges)
255  OS << " Edge " << Count++ << ": " << getBBInfo(EI->SrcBB).Index << "-->"
256  << getBBInfo(EI->DestBB).Index << EI->infoString() << "\n";
257  }
258 
259  // Add an edge to AllEdges with weight W.
260  Edge &addEdge(const BasicBlock *Src, const BasicBlock *Dest, uint64_t W) {
261  uint32_t Index = BBInfos.size();
262  auto Iter = BBInfos.end();
263  bool Inserted;
264  std::tie(Iter, Inserted) = BBInfos.insert(std::make_pair(Src, nullptr));
265  if (Inserted) {
266  // Newly inserted, update the real info.
267  Iter->second = std::move(std::make_unique<BBInfo>(Index));
268  Index++;
269  }
270  std::tie(Iter, Inserted) = BBInfos.insert(std::make_pair(Dest, nullptr));
271  if (Inserted)
272  // Newly inserted, update the real info.
273  Iter->second = std::move(std::make_unique<BBInfo>(Index));
274  AllEdges.emplace_back(new Edge(Src, Dest, W));
275  return *AllEdges.back();
276  }
277 
280 
281  // If function entry will be always instrumented.
283 
284 public:
285  CFGMST(Function &Func, bool InstrumentFuncEntry_,
286  BranchProbabilityInfo *BPI_ = nullptr,
287  BlockFrequencyInfo *BFI_ = nullptr)
288  : F(Func), BPI(BPI_), BFI(BFI_),
289  InstrumentFuncEntry(InstrumentFuncEntry_) {
290  buildEdges();
293  if (AllEdges.size() > 1 && InstrumentFuncEntry)
294  std::iter_swap(std::move(AllEdges.begin()),
295  std::move(AllEdges.begin() + AllEdges.size() - 1));
296  }
297 };
298 
299 } // end namespace llvm
300 
301 #undef DEBUG_TYPE // "cfgmst"
302 
303 #endif // LLVM_LIB_TRANSFORMS_INSTRUMENTATION_CFGMST_H
i
i
Definition: README.txt:29
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::CFGMST::getBBInfo
BBInfo & getBBInfo(const BasicBlock *BB) const
Definition: CFGMST.h:83
llvm::Function
Definition: Function.h:61
llvm::RISCVFenceField::W
@ W
Definition: RISCVBaseInfo.h:199
llvm::CFGMST::BPI
BranchProbabilityInfo * BPI
Definition: CFGMST.h:278
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:717
DenseMap.h
llvm::CFGMST::AllEdges
std::vector< std::unique_ptr< Edge > > AllEdges
Definition: CFGMST.h:45
llvm::CFGMST::findAndCompressGroup
BBInfo * findAndCompressGroup(BBInfo *G)
Definition: CFGMST.h:55
llvm::isCriticalEdge
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:95
STLExtras.h
llvm::CFGMST::F
Function & F
Definition: CFGMST.h:41
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::succ_empty
bool succ_empty(const Instruction *I)
Definition: CFG.h:256
llvm::BranchProbability::scale
uint64_t scale(uint64_t Num) const
Scale a large integer.
Definition: BranchProbability.cpp:107
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::BlockFrequencyInfo::getEntryFreq
uint64_t getEntryFreq() const
Definition: BlockFrequencyInfo.cpp:281
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:765
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::BranchProbabilityInfo
Analysis providing branch probability information.
Definition: BranchProbabilityInfo.h:115
llvm::CFGMST::unionGroups
bool unionGroups(const BasicBlock *BB1, const BasicBlock *BB2)
Definition: CFGMST.h:63
UINT64_MAX
#define UINT64_MAX
Definition: DataTypes.h:77
llvm::CFGMST::InstrumentFuncEntry
bool InstrumentFuncEntry
Definition: CFGMST.h:282
llvm::Instruction
Definition: Instruction.h:45
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:777
llvm::CFGMST
An union-find based Minimum Spanning Tree for CFG.
Definition: CFGMST.h:39
llvm::CFGMST::sortEdgesByWeight
void sortEdgesByWeight()
Definition: CFGMST.h:204
BranchProbability.h
llvm::Twine::str
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
BranchProbabilityInfo.h
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
uint64_t
move
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
Definition: README.txt:546
llvm::DenseMap
Definition: DenseMap.h:714
llvm::BlockFrequency::getFrequency
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
Definition: BlockFrequency.h:35
llvm::CFGMST::CFGMST
CFGMST(Function &Func, bool InstrumentFuncEntry_, BranchProbabilityInfo *BPI_=nullptr, BlockFrequencyInfo *BFI_=nullptr)
Definition: CFGMST.h:285
llvm::CFGMST::ExitBlockFound
bool ExitBlockFound
Definition: CFGMST.h:52
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CFGMST::computeMinimumSpanningTree
void computeMinimumSpanningTree()
Definition: CFGMST.h:213
llvm::BranchProbabilityInfo::getEdgeProbability
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
Definition: BranchProbabilityInfo.cpp:1113
CFG.h
uint32_t
BlockFrequencyInfo.h
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::BasicBlock::getTerminator
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...
Definition: BasicBlock.cpp:148
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1686
llvm::CFGMST::buildEdges
void buildEdges()
Definition: CFGMST.h:100
llvm::CFGMST::BBInfos
DenseMap< const BasicBlock *, std::unique_ptr< BBInfo > > BBInfos
Definition: CFGMST.h:48
llvm::CFGMST::addEdge
Edge & addEdge(const BasicBlock *Src, const BasicBlock *Dest, uint64_t W)
Definition: CFGMST.h:260
llvm::BlockFrequencyInfo::getBlockFreq
BlockFrequency getBlockFreq(const BasicBlock *BB) const
getblockFreq - Return block frequency.
Definition: BlockFrequencyInfo.cpp:204
llvm::CFGMST::BFI
BlockFrequencyInfo * BFI
Definition: CFGMST.h:279
BB
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
Definition: README.txt:39
raw_ostream.h
BasicBlockUtils.h
llvm::CFGMST::dumpEdges
void dumpEdges(raw_ostream &OS, const Twine &Message) const
Definition: CFGMST.h:241
llvm::CFGMST::findBBInfo
BBInfo * findBBInfo(const BasicBlock *BB) const
Definition: CFGMST.h:90
Debug.h