1 //===-- PGOInstrumentation.cpp - MST-based PGO Instrumentation ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements PGO instrumentation using a minimum spanning tree based
11 // on the following paper:
12 // [1] Donald E. Knuth, Francis R. Stevenson. Optimal measurement of points
13 // for program frequency counts. BIT Numerical Mathematics 1973, Volume 13,
14 // Issue 3, pp 313-322
15 // The idea of the algorithm based on the fact that for each node (except for
16 // the entry and exit), the sum of incoming edge counts equals the sum of
17 // outgoing edge counts. The count of edge on spanning tree can be derived from
18 // those edges not on the spanning tree. Knuth proves this method instruments
19 // the minimum number of edges.
21 // The minimal spanning tree here is actually a maximum weight tree -- on-tree
22 // edges have higher frequencies (more likely to execute). The idea is to
23 // instrument those less frequently executed edges to reduce the runtime
24 // overhead of instrumented binaries.
26 // This file contains two passes:
27 // (1) Pass PGOInstrumentationGen which instruments the IR to generate edge
28 // count profile, and generates the instrumentation for indirect call
30 // (2) Pass PGOInstrumentationUse which reads the edge count profile and
31 // annotates the branch weights. It also reads the indirect call value
32 // profiling records and annotate the indirect call instructions.
34 // To get the precise counter information, These two passes need to invoke at
35 // the same compilation point (so they see the same IR). For pass
36 // PGOInstrumentationGen, the real work is done in instrumentOneFunc(). For
37 // pass PGOInstrumentationUse, the real work in done in class PGOUseFunc and
38 // the profile is opened in module level and passed to each PGOUseFunc instance.
39 // The shared code for PGOInstrumentationGen and PGOInstrumentationUse is put
40 // in class FuncPGOInstrumentation.
42 // Class PGOEdge represents a CFG edge and some auxiliary information. Class
43 // BBInfo contains auxiliary information for each BB. These two classes are used
44 // in pass PGOInstrumentationGen. Class PGOUseEdge and UseBBInfo are the derived
45 // class of PGOEdge and BBInfo, respectively. They contains extra data structure
46 // used in populating profile counters.
47 // The MST implementation is in Class CFGMST (CFGMST.h).
49 //===----------------------------------------------------------------------===//
51 #include "llvm/Transforms/PGOInstrumentation.h"
53 #include "llvm/ADT/STLExtras.h"
54 #include "llvm/ADT/SmallVector.h"
55 #include "llvm/ADT/Statistic.h"
56 #include "llvm/ADT/Triple.h"
57 #include "llvm/Analysis/BlockFrequencyInfo.h"
58 #include "llvm/Analysis/BranchProbabilityInfo.h"
59 #include "llvm/Analysis/CFG.h"
60 #include "llvm/Analysis/IndirectCallSiteVisitor.h"
61 #include "llvm/IR/CallSite.h"
62 #include "llvm/IR/DiagnosticInfo.h"
63 #include "llvm/IR/GlobalValue.h"
64 #include "llvm/IR/IRBuilder.h"
65 #include "llvm/IR/InstIterator.h"
66 #include "llvm/IR/Instructions.h"
67 #include "llvm/IR/IntrinsicInst.h"
68 #include "llvm/IR/MDBuilder.h"
69 #include "llvm/IR/Module.h"
70 #include "llvm/Pass.h"
71 #include "llvm/ProfileData/InstrProfReader.h"
72 #include "llvm/ProfileData/ProfileCommon.h"
73 #include "llvm/Support/BranchProbability.h"
74 #include "llvm/Support/Debug.h"
75 #include "llvm/Support/JamCRC.h"
76 #include "llvm/Transforms/Instrumentation.h"
77 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
80 #include <unordered_map>
86 #define DEBUG_TYPE "pgo-instrumentation"
88 STATISTIC(NumOfPGOInstrument, "Number of edges instrumented.");
89 STATISTIC(NumOfPGOSelectInsts, "Number of select instruction instrumented.");
90 STATISTIC(NumOfPGOEdge, "Number of edges.");
91 STATISTIC(NumOfPGOBB, "Number of basic-blocks.");
92 STATISTIC(NumOfPGOSplit, "Number of critical edge splits.");
93 STATISTIC(NumOfPGOFunc, "Number of functions having valid profile counts.");
94 STATISTIC(NumOfPGOMismatch, "Number of functions having mismatch profile.");
95 STATISTIC(NumOfPGOMissing, "Number of functions without profile.");
96 STATISTIC(NumOfPGOICall, "Number of indirect call value instrumentations.");
98 // Command line option to specify the file to read profile from. This is
99 // mainly used for testing.
100 static cl::opt<std::string>
101 PGOTestProfileFile("pgo-test-profile-file", cl::init(""), cl::Hidden,
102 cl::value_desc("filename"),
103 cl::desc("Specify the path of profile data file. This is"
104 "mainly for test purpose."));
106 // Command line option to disable value profiling. The default is false:
107 // i.e. value profiling is enabled by default. This is for debug purpose.
108 static cl::opt<bool> DisableValueProfiling("disable-vp", cl::init(false),
110 cl::desc("Disable Value Profiling"));
112 // Command line option to set the maximum number of VP annotations to write to
113 // the metadata for a single indirect call callsite.
114 static cl::opt<unsigned> MaxNumAnnotations(
115 "icp-max-annotations", cl::init(3), cl::Hidden, cl::ZeroOrMore,
116 cl::desc("Max number of annotations for a single indirect "
119 // Command line option to control appending FunctionHash to the name of a COMDAT
120 // function. This is to avoid the hash mismatch caused by the preinliner.
121 static cl::opt<bool> DoComdatRenaming(
122 "do-comdat-renaming", cl::init(true), cl::Hidden,
123 cl::desc("Append function hash to the name of COMDAT function to avoid "
124 "function hash mismatch due to the preinliner"));
126 // Command line option to enable/disable the warning about missing profile
128 static cl::opt<bool> PGOWarnMissing("pgo-warn-missing-function",
132 // Command line option to enable/disable the warning about a hash mismatch in
134 static cl::opt<bool> NoPGOWarnMismatch("no-pgo-warn-mismatch", cl::init(false),
137 // Command line option to enable/disable select instruction instrumentation.
138 static cl::opt<bool> PGOInstrSelect("pgo-instr-select", cl::init(true),
142 /// The select instruction visitor plays three roles specified
143 /// by the mode. In \c VM_counting mode, it simply counts the number of
144 /// select instructions. In \c VM_instrument mode, it inserts code to count
145 /// the number times TrueValue of select is taken. In \c VM_annotate mode,
146 /// it reads the profile data and annotate the select instruction with metadata.
147 enum VisitMode { VM_counting, VM_instrument, VM_annotate };
150 /// Instruction Visitor class to visit select instructions.
151 struct SelectInstVisitor : public InstVisitor<SelectInstVisitor> {
153 unsigned NSIs = 0; // Number of select instructions instrumented.
154 VisitMode Mode = VM_counting; // Visiting mode.
155 unsigned *CurCtrIdx = nullptr; // Pointer to current counter index.
156 unsigned TotalNumCtrs = 0; // Total number of counters
157 GlobalVariable *FuncNameVar = nullptr;
158 uint64_t FuncHash = 0;
159 PGOUseFunc *UseFunc = nullptr;
161 SelectInstVisitor(Function &Func) : F(Func) {}
163 void countSelects(Function &Func) {
167 // Visit the IR stream and instrument all select instructions. \p
168 // Ind is a pointer to the counter index variable; \p TotalNC
169 // is the total number of counters; \p FNV is the pointer to the
170 // PGO function name var; \p FHash is the function hash.
171 void instrumentSelects(Function &Func, unsigned *Ind, unsigned TotalNC,
172 GlobalVariable *FNV, uint64_t FHash) {
173 Mode = VM_instrument;
175 TotalNumCtrs = TotalNC;
181 // Visit the IR stream and annotate all select instructions.
182 void annotateSelects(Function &Func, PGOUseFunc *UF, unsigned *Ind) {
189 void instrumentOneSelectInst(SelectInst &SI);
190 void annotateOneSelectInst(SelectInst &SI);
191 // Visit \p SI instruction and perform tasks according to visit mode.
192 void visitSelectInst(SelectInst &SI);
193 unsigned getNumOfSelectInsts() const { return NSIs; }
196 class PGOInstrumentationGenLegacyPass : public ModulePass {
200 PGOInstrumentationGenLegacyPass() : ModulePass(ID) {
201 initializePGOInstrumentationGenLegacyPassPass(
202 *PassRegistry::getPassRegistry());
205 StringRef getPassName() const override { return "PGOInstrumentationGenPass"; }
208 bool runOnModule(Module &M) override;
210 void getAnalysisUsage(AnalysisUsage &AU) const override {
211 AU.addRequired<BlockFrequencyInfoWrapperPass>();
215 class PGOInstrumentationUseLegacyPass : public ModulePass {
219 // Provide the profile filename as the parameter.
220 PGOInstrumentationUseLegacyPass(std::string Filename = "")
221 : ModulePass(ID), ProfileFileName(std::move(Filename)) {
222 if (!PGOTestProfileFile.empty())
223 ProfileFileName = PGOTestProfileFile;
224 initializePGOInstrumentationUseLegacyPassPass(
225 *PassRegistry::getPassRegistry());
228 StringRef getPassName() const override { return "PGOInstrumentationUsePass"; }
231 std::string ProfileFileName;
233 bool runOnModule(Module &M) override;
234 void getAnalysisUsage(AnalysisUsage &AU) const override {
235 AU.addRequired<BlockFrequencyInfoWrapperPass>();
239 } // end anonymous namespace
241 char PGOInstrumentationGenLegacyPass::ID = 0;
242 INITIALIZE_PASS_BEGIN(PGOInstrumentationGenLegacyPass, "pgo-instr-gen",
243 "PGO instrumentation.", false, false)
244 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
245 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
246 INITIALIZE_PASS_END(PGOInstrumentationGenLegacyPass, "pgo-instr-gen",
247 "PGO instrumentation.", false, false)
249 ModulePass *llvm::createPGOInstrumentationGenLegacyPass() {
250 return new PGOInstrumentationGenLegacyPass();
253 char PGOInstrumentationUseLegacyPass::ID = 0;
254 INITIALIZE_PASS_BEGIN(PGOInstrumentationUseLegacyPass, "pgo-instr-use",
255 "Read PGO instrumentation profile.", false, false)
256 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
257 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
258 INITIALIZE_PASS_END(PGOInstrumentationUseLegacyPass, "pgo-instr-use",
259 "Read PGO instrumentation profile.", false, false)
261 ModulePass *llvm::createPGOInstrumentationUseLegacyPass(StringRef Filename) {
262 return new PGOInstrumentationUseLegacyPass(Filename.str());
266 /// \brief An MST based instrumentation for PGO
268 /// Implements a Minimum Spanning Tree (MST) based instrumentation for PGO
269 /// in the function level.
271 // This class implements the CFG edges. Note the CFG can be a multi-graph.
272 // So there might be multiple edges with same SrcBB and DestBB.
273 const BasicBlock *SrcBB;
274 const BasicBlock *DestBB;
279 PGOEdge(const BasicBlock *Src, const BasicBlock *Dest, unsigned W = 1)
280 : SrcBB(Src), DestBB(Dest), Weight(W), InMST(false), Removed(false),
282 // Return the information string of an edge.
283 const std::string infoString() const {
284 return (Twine(Removed ? "-" : " ") + (InMST ? " " : "*") +
285 (IsCritical ? "c" : " ") + " W=" + Twine(Weight)).str();
289 // This class stores the auxiliary information for each BB.
295 BBInfo(unsigned IX) : Group(this), Index(IX), Rank(0) {}
297 // Return the information string of this object.
298 const std::string infoString() const {
299 return (Twine("Index=") + Twine(Index)).str();
303 // This class implements the CFG edges. Note the CFG can be a multi-graph.
304 template <class Edge, class BBInfo> class FuncPGOInstrumentation {
307 void computeCFGHash();
308 void renameComdatFunction();
309 // A map that stores the Comdat group in function F.
310 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers;
313 std::vector<Instruction *> IndirectCallSites;
314 SelectInstVisitor SIVisitor;
315 std::string FuncName;
316 GlobalVariable *FuncNameVar;
317 // CFG hash value for this function.
318 uint64_t FunctionHash;
320 // The Minimum Spanning Tree of function CFG.
321 CFGMST<Edge, BBInfo> MST;
323 // Give an edge, find the BB that will be instrumented.
324 // Return nullptr if there is no BB to be instrumented.
325 BasicBlock *getInstrBB(Edge *E);
327 // Return the auxiliary BB information.
328 BBInfo &getBBInfo(const BasicBlock *BB) const { return MST.getBBInfo(BB); }
330 // Return the auxiliary BB information if available.
331 BBInfo *findBBInfo(const BasicBlock *BB) const { return MST.findBBInfo(BB); }
333 // Dump edges and BB information.
334 void dumpInfo(std::string Str = "") const {
335 MST.dumpEdges(dbgs(), Twine("Dump Function ") + FuncName + " Hash: " +
336 Twine(FunctionHash) + "\t" + Str);
339 FuncPGOInstrumentation(
341 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers,
342 bool CreateGlobalVar = false, BranchProbabilityInfo *BPI = nullptr,
343 BlockFrequencyInfo *BFI = nullptr)
344 : F(Func), ComdatMembers(ComdatMembers), SIVisitor(Func), FunctionHash(0),
347 // This should be done before CFG hash computation.
348 SIVisitor.countSelects(Func);
349 NumOfPGOSelectInsts += SIVisitor.getNumOfSelectInsts();
350 IndirectCallSites = findIndirectCallSites(Func);
352 FuncName = getPGOFuncName(F);
354 if (ComdatMembers.size())
355 renameComdatFunction();
356 DEBUG(dumpInfo("after CFGMST"));
358 NumOfPGOBB += MST.BBInfos.size();
359 for (auto &E : MST.AllEdges) {
364 NumOfPGOInstrument++;
368 FuncNameVar = createPGOFuncNameVar(F, FuncName);
371 // Return the number of profile counters needed for the function.
372 unsigned getNumCounters() {
373 unsigned NumCounters = 0;
374 for (auto &E : this->MST.AllEdges) {
375 if (!E->InMST && !E->Removed)
378 return NumCounters + SIVisitor.getNumOfSelectInsts();
382 // Compute Hash value for the CFG: the lower 32 bits are CRC32 of the index
383 // value of each BB in the CFG. The higher 32 bits record the number of edges.
384 template <class Edge, class BBInfo>
385 void FuncPGOInstrumentation<Edge, BBInfo>::computeCFGHash() {
386 std::vector<char> Indexes;
389 const TerminatorInst *TI = BB.getTerminator();
390 for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) {
391 BasicBlock *Succ = TI->getSuccessor(I);
392 auto BI = findBBInfo(Succ);
395 uint32_t Index = BI->Index;
396 for (int J = 0; J < 4; J++)
397 Indexes.push_back((char)(Index >> (J * 8)));
401 FunctionHash = (uint64_t)SIVisitor.getNumOfSelectInsts() << 56 |
402 (uint64_t)IndirectCallSites.size() << 48 |
403 (uint64_t)MST.AllEdges.size() << 32 | JC.getCRC();
406 // Check if we can safely rename this Comdat function.
407 static bool canRenameComdat(
409 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers) {
410 if (F.getName().empty())
412 if (!needsComdatForCounter(F, *(F.getParent())))
414 // Only safe to do if this function may be discarded if it is not used
415 // in the compilation unit.
416 if (!GlobalValue::isDiscardableIfUnused(F.getLinkage()))
419 // For AvailableExternallyLinkage functions.
420 if (!F.hasComdat()) {
421 assert(F.getLinkage() == GlobalValue::AvailableExternallyLinkage);
425 // FIXME: Current only handle those Comdat groups that only containing one
426 // function and function aliases.
427 // (1) For a Comdat group containing multiple functions, we need to have a
428 // unique postfix based on the hashes for each function. There is a
429 // non-trivial code refactoring to do this efficiently.
430 // (2) Variables can not be renamed, so we can not rename Comdat function in a
431 // group including global vars.
432 Comdat *C = F.getComdat();
433 for (auto &&CM : make_range(ComdatMembers.equal_range(C))) {
434 if (dyn_cast<GlobalAlias>(CM.second))
436 Function *FM = dyn_cast<Function>(CM.second);
443 // Append the CFGHash to the Comdat function name.
444 template <class Edge, class BBInfo>
445 void FuncPGOInstrumentation<Edge, BBInfo>::renameComdatFunction() {
446 if (!canRenameComdat(F, ComdatMembers))
448 std::string OrigName = F.getName().str();
449 std::string NewFuncName =
450 Twine(F.getName() + "." + Twine(FunctionHash)).str();
451 F.setName(Twine(NewFuncName));
452 GlobalAlias::create(GlobalValue::WeakAnyLinkage, OrigName, &F);
453 FuncName = Twine(FuncName + "." + Twine(FunctionHash)).str();
455 Module *M = F.getParent();
456 // For AvailableExternallyLinkage functions, change the linkage to
457 // LinkOnceODR and put them into comdat. This is because after renaming, there
458 // is no backup external copy available for the function.
459 if (!F.hasComdat()) {
460 assert(F.getLinkage() == GlobalValue::AvailableExternallyLinkage);
461 NewComdat = M->getOrInsertComdat(StringRef(NewFuncName));
462 F.setLinkage(GlobalValue::LinkOnceODRLinkage);
463 F.setComdat(NewComdat);
467 // This function belongs to a single function Comdat group.
468 Comdat *OrigComdat = F.getComdat();
469 std::string NewComdatName =
470 Twine(OrigComdat->getName() + "." + Twine(FunctionHash)).str();
471 NewComdat = M->getOrInsertComdat(StringRef(NewComdatName));
472 NewComdat->setSelectionKind(OrigComdat->getSelectionKind());
474 for (auto &&CM : make_range(ComdatMembers.equal_range(OrigComdat))) {
475 if (GlobalAlias *GA = dyn_cast<GlobalAlias>(CM.second)) {
476 // For aliases, change the name directly.
477 assert(dyn_cast<Function>(GA->getAliasee()->stripPointerCasts()) == &F);
478 std::string OrigGAName = GA->getName().str();
479 GA->setName(Twine(GA->getName() + "." + Twine(FunctionHash)));
480 GlobalAlias::create(GlobalValue::WeakAnyLinkage, OrigGAName, GA);
483 // Must be a function.
484 Function *CF = dyn_cast<Function>(CM.second);
486 CF->setComdat(NewComdat);
490 // Given a CFG E to be instrumented, find which BB to place the instrumented
491 // code. The function will split the critical edge if necessary.
492 template <class Edge, class BBInfo>
493 BasicBlock *FuncPGOInstrumentation<Edge, BBInfo>::getInstrBB(Edge *E) {
494 if (E->InMST || E->Removed)
497 BasicBlock *SrcBB = const_cast<BasicBlock *>(E->SrcBB);
498 BasicBlock *DestBB = const_cast<BasicBlock *>(E->DestBB);
499 // For a fake edge, instrument the real BB.
500 if (SrcBB == nullptr)
502 if (DestBB == nullptr)
505 // Instrument the SrcBB if it has a single successor,
506 // otherwise, the DestBB if this is not a critical edge.
507 TerminatorInst *TI = SrcBB->getTerminator();
508 if (TI->getNumSuccessors() <= 1)
513 // For a critical edge, we have to split. Instrument the newly
516 DEBUG(dbgs() << "Split critical edge: " << getBBInfo(SrcBB).Index << " --> "
517 << getBBInfo(DestBB).Index << "\n");
518 unsigned SuccNum = GetSuccessorNumber(SrcBB, DestBB);
519 BasicBlock *InstrBB = SplitCriticalEdge(TI, SuccNum);
520 assert(InstrBB && "Critical edge is not split");
526 // Visit all edge and instrument the edges not in MST, and do value profiling.
527 // Critical edges will be split.
528 static void instrumentOneFunc(
529 Function &F, Module *M, BranchProbabilityInfo *BPI, BlockFrequencyInfo *BFI,
530 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers) {
531 FuncPGOInstrumentation<PGOEdge, BBInfo> FuncInfo(F, ComdatMembers, true, BPI,
533 unsigned NumCounters = FuncInfo.getNumCounters();
536 Type *I8PtrTy = Type::getInt8PtrTy(M->getContext());
537 for (auto &E : FuncInfo.MST.AllEdges) {
538 BasicBlock *InstrBB = FuncInfo.getInstrBB(E.get());
542 IRBuilder<> Builder(InstrBB, InstrBB->getFirstInsertionPt());
543 assert(Builder.GetInsertPoint() != InstrBB->end() &&
544 "Cannot get the Instrumentation point");
546 Intrinsic::getDeclaration(M, Intrinsic::instrprof_increment),
547 {llvm::ConstantExpr::getBitCast(FuncInfo.FuncNameVar, I8PtrTy),
548 Builder.getInt64(FuncInfo.FunctionHash), Builder.getInt32(NumCounters),
549 Builder.getInt32(I++)});
552 // Now instrument select instructions:
553 FuncInfo.SIVisitor.instrumentSelects(F, &I, NumCounters, FuncInfo.FuncNameVar,
554 FuncInfo.FunctionHash);
555 assert(I == NumCounters);
557 if (DisableValueProfiling)
560 unsigned NumIndirectCallSites = 0;
561 for (auto &I : FuncInfo.IndirectCallSites) {
563 Value *Callee = CS.getCalledValue();
564 DEBUG(dbgs() << "Instrument one indirect call: CallSite Index = "
565 << NumIndirectCallSites << "\n");
566 IRBuilder<> Builder(I);
567 assert(Builder.GetInsertPoint() != I->getParent()->end() &&
568 "Cannot get the Instrumentation point");
570 Intrinsic::getDeclaration(M, Intrinsic::instrprof_value_profile),
571 {llvm::ConstantExpr::getBitCast(FuncInfo.FuncNameVar, I8PtrTy),
572 Builder.getInt64(FuncInfo.FunctionHash),
573 Builder.CreatePtrToInt(Callee, Builder.getInt64Ty()),
574 Builder.getInt32(llvm::InstrProfValueKind::IPVK_IndirectCallTarget),
575 Builder.getInt32(NumIndirectCallSites++)});
577 NumOfPGOICall += NumIndirectCallSites;
580 // This class represents a CFG edge in profile use compilation.
581 struct PGOUseEdge : public PGOEdge {
584 PGOUseEdge(const BasicBlock *Src, const BasicBlock *Dest, unsigned W = 1)
585 : PGOEdge(Src, Dest, W), CountValid(false), CountValue(0) {}
587 // Set edge count value
588 void setEdgeCount(uint64_t Value) {
593 // Return the information string for this object.
594 const std::string infoString() const {
596 return PGOEdge::infoString();
597 return (Twine(PGOEdge::infoString()) + " Count=" + Twine(CountValue))
602 typedef SmallVector<PGOUseEdge *, 2> DirectEdges;
604 // This class stores the auxiliary information for each BB.
605 struct UseBBInfo : public BBInfo {
608 int32_t UnknownCountInEdge;
609 int32_t UnknownCountOutEdge;
611 DirectEdges OutEdges;
612 UseBBInfo(unsigned IX)
613 : BBInfo(IX), CountValue(0), CountValid(false), UnknownCountInEdge(0),
614 UnknownCountOutEdge(0) {}
615 UseBBInfo(unsigned IX, uint64_t C)
616 : BBInfo(IX), CountValue(C), CountValid(true), UnknownCountInEdge(0),
617 UnknownCountOutEdge(0) {}
619 // Set the profile count value for this BB.
620 void setBBInfoCount(uint64_t Value) {
625 // Return the information string of this object.
626 const std::string infoString() const {
628 return BBInfo::infoString();
629 return (Twine(BBInfo::infoString()) + " Count=" + Twine(CountValue)).str();
633 // Sum up the count values for all the edges.
634 static uint64_t sumEdgeCount(const ArrayRef<PGOUseEdge *> Edges) {
636 for (auto &E : Edges) {
639 Total += E->CountValue;
646 PGOUseFunc(Function &Func, Module *Modu,
647 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers,
648 BranchProbabilityInfo *BPI = nullptr,
649 BlockFrequencyInfo *BFI = nullptr)
650 : F(Func), M(Modu), FuncInfo(Func, ComdatMembers, false, BPI, BFI),
651 CountPosition(0), ProfileCountSize(0), FreqAttr(FFA_Normal) {}
653 // Read counts for the instrumented BB from profile.
654 bool readCounters(IndexedInstrProfReader *PGOReader);
656 // Populate the counts for all BBs.
657 void populateCounters();
659 // Set the branch weights based on the count values.
660 void setBranchWeights();
662 // Annotate the indirect call sites.
663 void annotateIndirectCallSites();
665 // The hotness of the function from the profile count.
666 enum FuncFreqAttr { FFA_Normal, FFA_Cold, FFA_Hot };
668 // Return the function hotness from the profile.
669 FuncFreqAttr getFuncFreqAttr() const { return FreqAttr; }
671 // Return the function hash.
672 uint64_t getFuncHash() const { return FuncInfo.FunctionHash; }
673 // Return the profile record for this function;
674 InstrProfRecord &getProfileRecord() { return ProfileRecord; }
676 // Return the auxiliary BB information.
677 UseBBInfo &getBBInfo(const BasicBlock *BB) const {
678 return FuncInfo.getBBInfo(BB);
681 // Return the auxiliary BB information if available.
682 UseBBInfo *findBBInfo(const BasicBlock *BB) const {
683 return FuncInfo.findBBInfo(BB);
689 // This member stores the shared information with class PGOGenFunc.
690 FuncPGOInstrumentation<PGOUseEdge, UseBBInfo> FuncInfo;
692 // The maximum count value in the profile. This is only used in PGO use
694 uint64_t ProgramMaxCount;
696 // Position of counter that remains to be read.
697 uint32_t CountPosition;
699 // Total size of the profile count for this function.
700 uint32_t ProfileCountSize;
702 // ProfileRecord for this function.
703 InstrProfRecord ProfileRecord;
705 // Function hotness info derived from profile.
706 FuncFreqAttr FreqAttr;
708 // Find the Instrumented BB and set the value.
709 void setInstrumentedCounts(const std::vector<uint64_t> &CountFromProfile);
711 // Set the edge counter value for the unknown edge -- there should be only
713 void setEdgeCount(DirectEdges &Edges, uint64_t Value);
715 // Return FuncName string;
716 const std::string getFuncName() const { return FuncInfo.FuncName; }
718 // Set the hot/cold inline hints based on the count values.
719 // FIXME: This function should be removed once the functionality in
720 // the inliner is implemented.
721 void markFunctionAttributes(uint64_t EntryCount, uint64_t MaxCount) {
722 if (ProgramMaxCount == 0)
724 // Threshold of the hot functions.
725 const BranchProbability HotFunctionThreshold(1, 100);
726 // Threshold of the cold functions.
727 const BranchProbability ColdFunctionThreshold(2, 10000);
728 if (EntryCount >= HotFunctionThreshold.scale(ProgramMaxCount))
730 else if (MaxCount <= ColdFunctionThreshold.scale(ProgramMaxCount))
735 // Visit all the edges and assign the count value for the instrumented
737 void PGOUseFunc::setInstrumentedCounts(
738 const std::vector<uint64_t> &CountFromProfile) {
740 assert(FuncInfo.getNumCounters() == CountFromProfile.size());
741 // Use a worklist as we will update the vector during the iteration.
742 std::vector<PGOUseEdge *> WorkList;
743 for (auto &E : FuncInfo.MST.AllEdges)
744 WorkList.push_back(E.get());
747 for (auto &E : WorkList) {
748 BasicBlock *InstrBB = FuncInfo.getInstrBB(E);
751 uint64_t CountValue = CountFromProfile[I++];
753 getBBInfo(InstrBB).setBBInfoCount(CountValue);
754 E->setEdgeCount(CountValue);
758 // Need to add two new edges.
759 BasicBlock *SrcBB = const_cast<BasicBlock *>(E->SrcBB);
760 BasicBlock *DestBB = const_cast<BasicBlock *>(E->DestBB);
761 // Add new edge of SrcBB->InstrBB.
762 PGOUseEdge &NewEdge = FuncInfo.MST.addEdge(SrcBB, InstrBB, 0);
763 NewEdge.setEdgeCount(CountValue);
764 // Add new edge of InstrBB->DestBB.
765 PGOUseEdge &NewEdge1 = FuncInfo.MST.addEdge(InstrBB, DestBB, 0);
766 NewEdge1.setEdgeCount(CountValue);
767 NewEdge1.InMST = true;
768 getBBInfo(InstrBB).setBBInfoCount(CountValue);
770 ProfileCountSize = CountFromProfile.size();
774 // Set the count value for the unknown edge. There should be one and only one
775 // unknown edge in Edges vector.
776 void PGOUseFunc::setEdgeCount(DirectEdges &Edges, uint64_t Value) {
777 for (auto &E : Edges) {
780 E->setEdgeCount(Value);
782 getBBInfo(E->SrcBB).UnknownCountOutEdge--;
783 getBBInfo(E->DestBB).UnknownCountInEdge--;
786 llvm_unreachable("Cannot find the unknown count edge");
789 // Read the profile from ProfileFileName and assign the value to the
790 // instrumented BB and the edges. This function also updates ProgramMaxCount.
791 // Return true if the profile are successfully read, and false on errors.
792 bool PGOUseFunc::readCounters(IndexedInstrProfReader *PGOReader) {
793 auto &Ctx = M->getContext();
794 Expected<InstrProfRecord> Result =
795 PGOReader->getInstrProfRecord(FuncInfo.FuncName, FuncInfo.FunctionHash);
796 if (Error E = Result.takeError()) {
797 handleAllErrors(std::move(E), [&](const InstrProfError &IPE) {
798 auto Err = IPE.get();
799 bool SkipWarning = false;
800 if (Err == instrprof_error::unknown_function) {
802 SkipWarning = !PGOWarnMissing;
803 } else if (Err == instrprof_error::hash_mismatch ||
804 Err == instrprof_error::malformed) {
806 SkipWarning = NoPGOWarnMismatch;
812 std::string Msg = IPE.message() + std::string(" ") + F.getName().str();
814 DiagnosticInfoPGOProfile(M->getName().data(), Msg, DS_Warning));
818 ProfileRecord = std::move(Result.get());
819 std::vector<uint64_t> &CountFromProfile = ProfileRecord.Counts;
822 DEBUG(dbgs() << CountFromProfile.size() << " counts\n");
823 uint64_t ValueSum = 0;
824 for (unsigned I = 0, S = CountFromProfile.size(); I < S; I++) {
825 DEBUG(dbgs() << " " << I << ": " << CountFromProfile[I] << "\n");
826 ValueSum += CountFromProfile[I];
829 DEBUG(dbgs() << "SUM = " << ValueSum << "\n");
831 getBBInfo(nullptr).UnknownCountOutEdge = 2;
832 getBBInfo(nullptr).UnknownCountInEdge = 2;
834 setInstrumentedCounts(CountFromProfile);
835 ProgramMaxCount = PGOReader->getMaximumFunctionCount();
839 // Populate the counters from instrumented BBs to all BBs.
840 // In the end of this operation, all BBs should have a valid count value.
841 void PGOUseFunc::populateCounters() {
842 // First set up Count variable for all BBs.
843 for (auto &E : FuncInfo.MST.AllEdges) {
847 const BasicBlock *SrcBB = E->SrcBB;
848 const BasicBlock *DestBB = E->DestBB;
849 UseBBInfo &SrcInfo = getBBInfo(SrcBB);
850 UseBBInfo &DestInfo = getBBInfo(DestBB);
851 SrcInfo.OutEdges.push_back(E.get());
852 DestInfo.InEdges.push_back(E.get());
853 SrcInfo.UnknownCountOutEdge++;
854 DestInfo.UnknownCountInEdge++;
858 DestInfo.UnknownCountInEdge--;
859 SrcInfo.UnknownCountOutEdge--;
863 unsigned NumPasses = 0;
868 // For efficient traversal, it's better to start from the end as most
869 // of the instrumented edges are at the end.
870 for (auto &BB : reverse(F)) {
871 UseBBInfo *Count = findBBInfo(&BB);
872 if (Count == nullptr)
874 if (!Count->CountValid) {
875 if (Count->UnknownCountOutEdge == 0) {
876 Count->CountValue = sumEdgeCount(Count->OutEdges);
877 Count->CountValid = true;
879 } else if (Count->UnknownCountInEdge == 0) {
880 Count->CountValue = sumEdgeCount(Count->InEdges);
881 Count->CountValid = true;
885 if (Count->CountValid) {
886 if (Count->UnknownCountOutEdge == 1) {
888 uint64_t OutSum = sumEdgeCount(Count->OutEdges);
889 // If the one of the successor block can early terminate (no-return),
890 // we can end up with situation where out edge sum count is larger as
891 // the source BB's count is collected by a post-dominated block.
892 if (Count->CountValue > OutSum)
893 Total = Count->CountValue - OutSum;
894 setEdgeCount(Count->OutEdges, Total);
897 if (Count->UnknownCountInEdge == 1) {
899 uint64_t InSum = sumEdgeCount(Count->InEdges);
900 if (Count->CountValue > InSum)
901 Total = Count->CountValue - InSum;
902 setEdgeCount(Count->InEdges, Total);
909 DEBUG(dbgs() << "Populate counts in " << NumPasses << " passes.\n");
911 // Assert every BB has a valid counter.
913 auto BI = findBBInfo(&BB);
916 assert(BI->CountValid && "BB count is not valid");
919 uint64_t FuncEntryCount = getBBInfo(&*F.begin()).CountValue;
920 F.setEntryCount(FuncEntryCount);
921 uint64_t FuncMaxCount = FuncEntryCount;
923 auto BI = findBBInfo(&BB);
926 FuncMaxCount = std::max(FuncMaxCount, BI->CountValue);
928 markFunctionAttributes(FuncEntryCount, FuncMaxCount);
930 // Now annotate select instructions
931 FuncInfo.SIVisitor.annotateSelects(F, this, &CountPosition);
932 assert(CountPosition == ProfileCountSize);
934 DEBUG(FuncInfo.dumpInfo("after reading profile."));
937 static void setProfMetadata(Module *M, Instruction *TI,
938 ArrayRef<uint64_t> EdgeCounts, uint64_t MaxCount) {
939 MDBuilder MDB(M->getContext());
940 assert(MaxCount > 0 && "Bad max count");
941 uint64_t Scale = calculateCountScale(MaxCount);
942 SmallVector<unsigned, 4> Weights;
943 for (const auto &ECI : EdgeCounts)
944 Weights.push_back(scaleBranchCount(ECI, Scale));
946 DEBUG(dbgs() << "Weight is: ";
947 for (const auto &W : Weights) { dbgs() << W << " "; }
949 TI->setMetadata(llvm::LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
952 // Assign the scaled count values to the BB with multiple out edges.
953 void PGOUseFunc::setBranchWeights() {
954 // Generate MD_prof metadata for every branch instruction.
955 DEBUG(dbgs() << "\nSetting branch weights.\n");
957 TerminatorInst *TI = BB.getTerminator();
958 if (TI->getNumSuccessors() < 2)
960 if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
962 if (getBBInfo(&BB).CountValue == 0)
965 // We have a non-zero Branch BB.
966 const UseBBInfo &BBCountInfo = getBBInfo(&BB);
967 unsigned Size = BBCountInfo.OutEdges.size();
968 SmallVector<uint64_t, 2> EdgeCounts(Size, 0);
969 uint64_t MaxCount = 0;
970 for (unsigned s = 0; s < Size; s++) {
971 const PGOUseEdge *E = BBCountInfo.OutEdges[s];
972 const BasicBlock *SrcBB = E->SrcBB;
973 const BasicBlock *DestBB = E->DestBB;
974 if (DestBB == nullptr)
976 unsigned SuccNum = GetSuccessorNumber(SrcBB, DestBB);
977 uint64_t EdgeCount = E->CountValue;
978 if (EdgeCount > MaxCount)
979 MaxCount = EdgeCount;
980 EdgeCounts[SuccNum] = EdgeCount;
982 setProfMetadata(M, TI, EdgeCounts, MaxCount);
986 void SelectInstVisitor::instrumentOneSelectInst(SelectInst &SI) {
987 Module *M = F.getParent();
988 IRBuilder<> Builder(&SI);
989 Type *Int64Ty = Builder.getInt64Ty();
990 Type *I8PtrTy = Builder.getInt8PtrTy();
991 auto *Step = Builder.CreateZExt(SI.getCondition(), Int64Ty);
993 Intrinsic::getDeclaration(M, Intrinsic::instrprof_increment_step),
994 {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
995 Builder.getInt64(FuncHash),
996 Builder.getInt32(TotalNumCtrs), Builder.getInt32(*CurCtrIdx), Step});
1000 void SelectInstVisitor::annotateOneSelectInst(SelectInst &SI) {
1001 std::vector<uint64_t> &CountFromProfile = UseFunc->getProfileRecord().Counts;
1002 assert(*CurCtrIdx < CountFromProfile.size() &&
1003 "Out of bound access of counters");
1004 uint64_t SCounts[2];
1005 SCounts[0] = CountFromProfile[*CurCtrIdx]; // True count
1007 uint64_t TotalCount = 0;
1008 auto BI = UseFunc->findBBInfo(SI.getParent());
1010 TotalCount = BI->CountValue;
1012 SCounts[1] = (TotalCount > SCounts[0] ? TotalCount - SCounts[0] : 0);
1013 uint64_t MaxCount = std::max(SCounts[0], SCounts[1]);
1015 setProfMetadata(F.getParent(), &SI, SCounts, MaxCount);
1018 void SelectInstVisitor::visitSelectInst(SelectInst &SI) {
1019 if (!PGOInstrSelect)
1021 // FIXME: do not handle this yet.
1022 if (SI.getCondition()->getType()->isVectorTy())
1030 instrumentOneSelectInst(SI);
1033 annotateOneSelectInst(SI);
1037 llvm_unreachable("Unknown visiting mode");
1040 // Traverse all the indirect callsites and annotate the instructions.
1041 void PGOUseFunc::annotateIndirectCallSites() {
1042 if (DisableValueProfiling)
1045 // Create the PGOFuncName meta data.
1046 createPGOFuncNameMetadata(F, FuncInfo.FuncName);
1048 unsigned IndirectCallSiteIndex = 0;
1049 auto &IndirectCallSites = FuncInfo.IndirectCallSites;
1050 unsigned NumValueSites =
1051 ProfileRecord.getNumValueSites(IPVK_IndirectCallTarget);
1052 if (NumValueSites != IndirectCallSites.size()) {
1054 std::string("Inconsistent number of indirect call sites: ") +
1056 auto &Ctx = M->getContext();
1058 DiagnosticInfoPGOProfile(M->getName().data(), Msg, DS_Warning));
1062 for (auto &I : IndirectCallSites) {
1063 DEBUG(dbgs() << "Read one indirect call instrumentation: Index="
1064 << IndirectCallSiteIndex << " out of " << NumValueSites
1066 annotateValueSite(*M, *I, ProfileRecord, IPVK_IndirectCallTarget,
1067 IndirectCallSiteIndex, MaxNumAnnotations);
1068 IndirectCallSiteIndex++;
1071 } // end anonymous namespace
1073 // Create a COMDAT variable INSTR_PROF_RAW_VERSION_VAR to make the runtime
1074 // aware this is an ir_level profile so it can set the version flag.
1075 static void createIRLevelProfileFlagVariable(Module &M) {
1076 Type *IntTy64 = Type::getInt64Ty(M.getContext());
1077 uint64_t ProfileVersion = (INSTR_PROF_RAW_VERSION | VARIANT_MASK_IR_PROF);
1078 auto IRLevelVersionVariable = new GlobalVariable(
1079 M, IntTy64, true, GlobalVariable::ExternalLinkage,
1080 Constant::getIntegerValue(IntTy64, APInt(64, ProfileVersion)),
1081 INSTR_PROF_QUOTE(INSTR_PROF_RAW_VERSION_VAR));
1082 IRLevelVersionVariable->setVisibility(GlobalValue::DefaultVisibility);
1083 Triple TT(M.getTargetTriple());
1084 if (!TT.supportsCOMDAT())
1085 IRLevelVersionVariable->setLinkage(GlobalValue::WeakAnyLinkage);
1087 IRLevelVersionVariable->setComdat(M.getOrInsertComdat(
1088 StringRef(INSTR_PROF_QUOTE(INSTR_PROF_RAW_VERSION_VAR))));
1091 // Collect the set of members for each Comdat in module M and store
1092 // in ComdatMembers.
1093 static void collectComdatMembers(
1095 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers) {
1096 if (!DoComdatRenaming)
1098 for (Function &F : M)
1099 if (Comdat *C = F.getComdat())
1100 ComdatMembers.insert(std::make_pair(C, &F));
1101 for (GlobalVariable &GV : M.globals())
1102 if (Comdat *C = GV.getComdat())
1103 ComdatMembers.insert(std::make_pair(C, &GV));
1104 for (GlobalAlias &GA : M.aliases())
1105 if (Comdat *C = GA.getComdat())
1106 ComdatMembers.insert(std::make_pair(C, &GA));
1109 static bool InstrumentAllFunctions(
1110 Module &M, function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
1111 function_ref<BlockFrequencyInfo *(Function &)> LookupBFI) {
1112 createIRLevelProfileFlagVariable(M);
1113 std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
1114 collectComdatMembers(M, ComdatMembers);
1117 if (F.isDeclaration())
1119 auto *BPI = LookupBPI(F);
1120 auto *BFI = LookupBFI(F);
1121 instrumentOneFunc(F, &M, BPI, BFI, ComdatMembers);
1126 bool PGOInstrumentationGenLegacyPass::runOnModule(Module &M) {
1130 auto LookupBPI = [this](Function &F) {
1131 return &this->getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
1133 auto LookupBFI = [this](Function &F) {
1134 return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
1136 return InstrumentAllFunctions(M, LookupBPI, LookupBFI);
1139 PreservedAnalyses PGOInstrumentationGen::run(Module &M,
1140 ModuleAnalysisManager &AM) {
1142 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
1143 auto LookupBPI = [&FAM](Function &F) {
1144 return &FAM.getResult<BranchProbabilityAnalysis>(F);
1147 auto LookupBFI = [&FAM](Function &F) {
1148 return &FAM.getResult<BlockFrequencyAnalysis>(F);
1151 if (!InstrumentAllFunctions(M, LookupBPI, LookupBFI))
1152 return PreservedAnalyses::all();
1154 return PreservedAnalyses::none();
1157 static bool annotateAllFunctions(
1158 Module &M, StringRef ProfileFileName,
1159 function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
1160 function_ref<BlockFrequencyInfo *(Function &)> LookupBFI) {
1161 DEBUG(dbgs() << "Read in profile counters: ");
1162 auto &Ctx = M.getContext();
1163 // Read the counter array from file.
1164 auto ReaderOrErr = IndexedInstrProfReader::create(ProfileFileName);
1165 if (Error E = ReaderOrErr.takeError()) {
1166 handleAllErrors(std::move(E), [&](const ErrorInfoBase &EI) {
1168 DiagnosticInfoPGOProfile(ProfileFileName.data(), EI.message()));
1173 std::unique_ptr<IndexedInstrProfReader> PGOReader =
1174 std::move(ReaderOrErr.get());
1176 Ctx.diagnose(DiagnosticInfoPGOProfile(ProfileFileName.data(),
1177 StringRef("Cannot get PGOReader")));
1180 // TODO: might need to change the warning once the clang option is finalized.
1181 if (!PGOReader->isIRLevelProfile()) {
1182 Ctx.diagnose(DiagnosticInfoPGOProfile(
1183 ProfileFileName.data(), "Not an IR level instrumentation profile"));
1187 std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
1188 collectComdatMembers(M, ComdatMembers);
1189 std::vector<Function *> HotFunctions;
1190 std::vector<Function *> ColdFunctions;
1192 if (F.isDeclaration())
1194 auto *BPI = LookupBPI(F);
1195 auto *BFI = LookupBFI(F);
1196 PGOUseFunc Func(F, &M, ComdatMembers, BPI, BFI);
1197 if (!Func.readCounters(PGOReader.get()))
1199 Func.populateCounters();
1200 Func.setBranchWeights();
1201 Func.annotateIndirectCallSites();
1202 PGOUseFunc::FuncFreqAttr FreqAttr = Func.getFuncFreqAttr();
1203 if (FreqAttr == PGOUseFunc::FFA_Cold)
1204 ColdFunctions.push_back(&F);
1205 else if (FreqAttr == PGOUseFunc::FFA_Hot)
1206 HotFunctions.push_back(&F);
1208 M.setProfileSummary(PGOReader->getSummary().getMD(M.getContext()));
1209 // Set function hotness attribute from the profile.
1210 // We have to apply these attributes at the end because their presence
1211 // can affect the BranchProbabilityInfo of any callers, resulting in an
1212 // inconsistent MST between prof-gen and prof-use.
1213 for (auto &F : HotFunctions) {
1214 F->addFnAttr(llvm::Attribute::InlineHint);
1215 DEBUG(dbgs() << "Set inline attribute to function: " << F->getName()
1218 for (auto &F : ColdFunctions) {
1219 F->addFnAttr(llvm::Attribute::Cold);
1220 DEBUG(dbgs() << "Set cold attribute to function: " << F->getName() << "\n");
1225 PGOInstrumentationUse::PGOInstrumentationUse(std::string Filename)
1226 : ProfileFileName(std::move(Filename)) {
1227 if (!PGOTestProfileFile.empty())
1228 ProfileFileName = PGOTestProfileFile;
1231 PreservedAnalyses PGOInstrumentationUse::run(Module &M,
1232 ModuleAnalysisManager &AM) {
1234 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
1235 auto LookupBPI = [&FAM](Function &F) {
1236 return &FAM.getResult<BranchProbabilityAnalysis>(F);
1239 auto LookupBFI = [&FAM](Function &F) {
1240 return &FAM.getResult<BlockFrequencyAnalysis>(F);
1243 if (!annotateAllFunctions(M, ProfileFileName, LookupBPI, LookupBFI))
1244 return PreservedAnalyses::all();
1246 return PreservedAnalyses::none();
1249 bool PGOInstrumentationUseLegacyPass::runOnModule(Module &M) {
1253 auto LookupBPI = [this](Function &F) {
1254 return &this->getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
1256 auto LookupBFI = [this](Function &F) {
1257 return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
1260 return annotateAllFunctions(M, ProfileFileName, LookupBPI, LookupBFI);