1 //===- PGOInstrumentation.cpp - MST-based PGO Instrumentation -------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements PGO instrumentation using a minimum spanning tree based
10 // on the following paper:
11 // [1] Donald E. Knuth, Francis R. Stevenson. Optimal measurement of points
12 // for program frequency counts. BIT Numerical Mathematics 1973, Volume 13,
13 // Issue 3, pp 313-322
14 // The idea of the algorithm based on the fact that for each node (except for
15 // the entry and exit), the sum of incoming edge counts equals the sum of
16 // outgoing edge counts. The count of edge on spanning tree can be derived from
17 // those edges not on the spanning tree. Knuth proves this method instruments
18 // the minimum number of edges.
20 // The minimal spanning tree here is actually a maximum weight tree -- on-tree
21 // edges have higher frequencies (more likely to execute). The idea is to
22 // instrument those less frequently executed edges to reduce the runtime
23 // overhead of instrumented binaries.
25 // This file contains two passes:
26 // (1) Pass PGOInstrumentationGen which instruments the IR to generate edge
27 // count profile, and generates the instrumentation for indirect call
29 // (2) Pass PGOInstrumentationUse which reads the edge count profile and
30 // annotates the branch weights. It also reads the indirect call value
31 // profiling records and annotate the indirect call instructions.
33 // To get the precise counter information, These two passes need to invoke at
34 // the same compilation point (so they see the same IR). For pass
35 // PGOInstrumentationGen, the real work is done in instrumentOneFunc(). For
36 // pass PGOInstrumentationUse, the real work in done in class PGOUseFunc and
37 // the profile is opened in module level and passed to each PGOUseFunc instance.
38 // The shared code for PGOInstrumentationGen and PGOInstrumentationUse is put
39 // in class FuncPGOInstrumentation.
41 // Class PGOEdge represents a CFG edge and some auxiliary information. Class
42 // BBInfo contains auxiliary information for each BB. These two classes are used
43 // in pass PGOInstrumentationGen. Class PGOUseEdge and UseBBInfo are the derived
44 // class of PGOEdge and BBInfo, respectively. They contains extra data structure
45 // used in populating profile counters.
46 // The MST implementation is in Class CFGMST (CFGMST.h).
48 //===----------------------------------------------------------------------===//
50 #include "llvm/Transforms/Instrumentation/PGOInstrumentation.h"
52 #include "ValueProfileCollector.h"
53 #include "llvm/ADT/APInt.h"
54 #include "llvm/ADT/ArrayRef.h"
55 #include "llvm/ADT/MapVector.h"
56 #include "llvm/ADT/STLExtras.h"
57 #include "llvm/ADT/SmallVector.h"
58 #include "llvm/ADT/Statistic.h"
59 #include "llvm/ADT/StringRef.h"
60 #include "llvm/ADT/Triple.h"
61 #include "llvm/ADT/Twine.h"
62 #include "llvm/ADT/iterator.h"
63 #include "llvm/ADT/iterator_range.h"
64 #include "llvm/Analysis/BlockFrequencyInfo.h"
65 #include "llvm/Analysis/BranchProbabilityInfo.h"
66 #include "llvm/Analysis/CFG.h"
67 #include "llvm/Analysis/EHPersonalities.h"
68 #include "llvm/Analysis/LoopInfo.h"
69 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
70 #include "llvm/Analysis/ProfileSummaryInfo.h"
71 #include "llvm/IR/Attributes.h"
72 #include "llvm/IR/BasicBlock.h"
73 #include "llvm/IR/CFG.h"
74 #include "llvm/IR/Comdat.h"
75 #include "llvm/IR/Constant.h"
76 #include "llvm/IR/Constants.h"
77 #include "llvm/IR/DiagnosticInfo.h"
78 #include "llvm/IR/Dominators.h"
79 #include "llvm/IR/Function.h"
80 #include "llvm/IR/GlobalAlias.h"
81 #include "llvm/IR/GlobalValue.h"
82 #include "llvm/IR/GlobalVariable.h"
83 #include "llvm/IR/IRBuilder.h"
84 #include "llvm/IR/InstVisitor.h"
85 #include "llvm/IR/InstrTypes.h"
86 #include "llvm/IR/Instruction.h"
87 #include "llvm/IR/Instructions.h"
88 #include "llvm/IR/IntrinsicInst.h"
89 #include "llvm/IR/Intrinsics.h"
90 #include "llvm/IR/LLVMContext.h"
91 #include "llvm/IR/MDBuilder.h"
92 #include "llvm/IR/Module.h"
93 #include "llvm/IR/PassManager.h"
94 #include "llvm/IR/ProfileSummary.h"
95 #include "llvm/IR/Type.h"
96 #include "llvm/IR/Value.h"
97 #include "llvm/InitializePasses.h"
98 #include "llvm/Pass.h"
99 #include "llvm/ProfileData/InstrProf.h"
100 #include "llvm/ProfileData/InstrProfReader.h"
101 #include "llvm/Support/BranchProbability.h"
102 #include "llvm/Support/CRC.h"
103 #include "llvm/Support/Casting.h"
104 #include "llvm/Support/CommandLine.h"
105 #include "llvm/Support/DOTGraphTraits.h"
106 #include "llvm/Support/Debug.h"
107 #include "llvm/Support/Error.h"
108 #include "llvm/Support/ErrorHandling.h"
109 #include "llvm/Support/GraphWriter.h"
110 #include "llvm/Support/raw_ostream.h"
111 #include "llvm/Transforms/Instrumentation.h"
112 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
113 #include "llvm/Transforms/Utils/ModuleUtils.h"
120 #include <unordered_map>
124 using namespace llvm;
125 using ProfileCount = Function::ProfileCount;
126 using VPCandidateInfo = ValueProfileCollector::CandidateInfo;
128 #define DEBUG_TYPE "pgo-instrumentation"
130 STATISTIC(NumOfPGOInstrument, "Number of edges instrumented.");
131 STATISTIC(NumOfPGOSelectInsts, "Number of select instruction instrumented.");
132 STATISTIC(NumOfPGOMemIntrinsics, "Number of mem intrinsics instrumented.");
133 STATISTIC(NumOfPGOEdge, "Number of edges.");
134 STATISTIC(NumOfPGOBB, "Number of basic-blocks.");
135 STATISTIC(NumOfPGOSplit, "Number of critical edge splits.");
136 STATISTIC(NumOfPGOFunc, "Number of functions having valid profile counts.");
137 STATISTIC(NumOfPGOMismatch, "Number of functions having mismatch profile.");
138 STATISTIC(NumOfPGOMissing, "Number of functions without profile.");
139 STATISTIC(NumOfPGOICall, "Number of indirect call value instrumentations.");
140 STATISTIC(NumOfCSPGOInstrument, "Number of edges instrumented in CSPGO.");
141 STATISTIC(NumOfCSPGOSelectInsts,
142 "Number of select instruction instrumented in CSPGO.");
143 STATISTIC(NumOfCSPGOMemIntrinsics,
144 "Number of mem intrinsics instrumented in CSPGO.");
145 STATISTIC(NumOfCSPGOEdge, "Number of edges in CSPGO.");
146 STATISTIC(NumOfCSPGOBB, "Number of basic-blocks in CSPGO.");
147 STATISTIC(NumOfCSPGOSplit, "Number of critical edge splits in CSPGO.");
148 STATISTIC(NumOfCSPGOFunc,
149 "Number of functions having valid profile counts in CSPGO.");
150 STATISTIC(NumOfCSPGOMismatch,
151 "Number of functions having mismatch profile in CSPGO.");
152 STATISTIC(NumOfCSPGOMissing, "Number of functions without profile in CSPGO.");
154 // Command line option to specify the file to read profile from. This is
155 // mainly used for testing.
156 static cl::opt<std::string>
157 PGOTestProfileFile("pgo-test-profile-file", cl::init(""), cl::Hidden,
158 cl::value_desc("filename"),
159 cl::desc("Specify the path of profile data file. This is"
160 "mainly for test purpose."));
161 static cl::opt<std::string> PGOTestProfileRemappingFile(
162 "pgo-test-profile-remapping-file", cl::init(""), cl::Hidden,
163 cl::value_desc("filename"),
164 cl::desc("Specify the path of profile remapping file. This is mainly for "
167 // Command line option to disable value profiling. The default is false:
168 // i.e. value profiling is enabled by default. This is for debug purpose.
169 static cl::opt<bool> DisableValueProfiling("disable-vp", cl::init(false),
171 cl::desc("Disable Value Profiling"));
173 // Command line option to set the maximum number of VP annotations to write to
174 // the metadata for a single indirect call callsite.
175 static cl::opt<unsigned> MaxNumAnnotations(
176 "icp-max-annotations", cl::init(3), cl::Hidden, cl::ZeroOrMore,
177 cl::desc("Max number of annotations for a single indirect "
180 // Command line option to set the maximum number of value annotations
181 // to write to the metadata for a single memop intrinsic.
182 static cl::opt<unsigned> MaxNumMemOPAnnotations(
183 "memop-max-annotations", cl::init(4), cl::Hidden, cl::ZeroOrMore,
184 cl::desc("Max number of preicise value annotations for a single memop"
187 // Command line option to control appending FunctionHash to the name of a COMDAT
188 // function. This is to avoid the hash mismatch caused by the preinliner.
189 static cl::opt<bool> DoComdatRenaming(
190 "do-comdat-renaming", cl::init(false), cl::Hidden,
191 cl::desc("Append function hash to the name of COMDAT function to avoid "
192 "function hash mismatch due to the preinliner"));
194 // Command line option to enable/disable the warning about missing profile
197 PGOWarnMissing("pgo-warn-missing-function", cl::init(false), cl::Hidden,
198 cl::desc("Use this option to turn on/off "
199 "warnings about missing profile data for "
203 // Command line option to enable/disable the warning about a hash mismatch in
206 NoPGOWarnMismatch("no-pgo-warn-mismatch", cl::init(false), cl::Hidden,
207 cl::desc("Use this option to turn off/on "
208 "warnings about profile cfg mismatch."));
211 // Command line option to enable/disable the warning about a hash mismatch in
212 // the profile data for Comdat functions, which often turns out to be false
213 // positive due to the pre-instrumentation inline.
215 NoPGOWarnMismatchComdat("no-pgo-warn-mismatch-comdat", cl::init(true),
217 cl::desc("The option is used to turn on/off "
218 "warnings about hash mismatch for comdat "
221 // Command line option to enable/disable select instruction instrumentation.
223 PGOInstrSelect("pgo-instr-select", cl::init(true), cl::Hidden,
224 cl::desc("Use this option to turn on/off SELECT "
225 "instruction instrumentation. "));
227 // Command line option to turn on CFG dot or text dump of raw profile counts
228 static cl::opt<PGOViewCountsType> PGOViewRawCounts(
229 "pgo-view-raw-counts", cl::Hidden,
230 cl::desc("A boolean option to show CFG dag or text "
231 "with raw profile counts from "
232 "profile data. See also option "
233 "-pgo-view-counts. To limit graph "
234 "display to only one function, use "
235 "filtering option -view-bfi-func-name."),
236 cl::values(clEnumValN(PGOVCT_None, "none", "do not show."),
237 clEnumValN(PGOVCT_Graph, "graph", "show a graph."),
238 clEnumValN(PGOVCT_Text, "text", "show in text.")));
240 // Command line option to enable/disable memop intrinsic call.size profiling.
242 PGOInstrMemOP("pgo-instr-memop", cl::init(true), cl::Hidden,
243 cl::desc("Use this option to turn on/off "
244 "memory intrinsic size profiling."));
246 // Emit branch probability as optimization remarks.
248 EmitBranchProbability("pgo-emit-branch-prob", cl::init(false), cl::Hidden,
249 cl::desc("When this option is on, the annotated "
250 "branch probability will be emitted as "
251 "optimization remarks: -{Rpass|"
252 "pass-remarks}=pgo-instrumentation"));
254 static cl::opt<bool> PGOInstrumentEntry(
255 "pgo-instrument-entry", cl::init(false), cl::Hidden,
256 cl::desc("Force to instrument function entry basicblock."));
259 PGOFixEntryCount("pgo-fix-entry-count", cl::init(true), cl::Hidden,
260 cl::desc("Fix function entry count in profile use."));
262 static cl::opt<bool> PGOVerifyHotBFI(
263 "pgo-verify-hot-bfi", cl::init(false), cl::Hidden,
264 cl::desc("Print out the non-match BFI count if a hot raw profile count "
265 "becomes non-hot, or a cold raw profile count becomes hot. "
266 "The print is enabled under -Rpass-analysis=pgo, or "
267 "internal option -pass-remakrs-analysis=pgo."));
269 static cl::opt<bool> PGOVerifyBFI(
270 "pgo-verify-bfi", cl::init(false), cl::Hidden,
271 cl::desc("Print out mismatched BFI counts after setting profile metadata "
272 "The print is enabled under -Rpass-analysis=pgo, or "
273 "internal option -pass-remakrs-analysis=pgo."));
275 static cl::opt<unsigned> PGOVerifyBFIRatio(
276 "pgo-verify-bfi-ratio", cl::init(2), cl::Hidden,
277 cl::desc("Set the threshold for pgo-verify-bfi: only print out "
278 "mismatched BFI if the difference percentage is greater than "
279 "this value (in percentage)."));
281 static cl::opt<unsigned> PGOVerifyBFICutoff(
282 "pgo-verify-bfi-cutoff", cl::init(5), cl::Hidden,
283 cl::desc("Set the threshold for pgo-verify-bfi: skip the counts whose "
284 "profile count value is below."));
287 // Command line option to turn on CFG dot dump after profile annotation.
288 // Defined in Analysis/BlockFrequencyInfo.cpp: -pgo-view-counts
289 extern cl::opt<PGOViewCountsType> PGOViewCounts;
291 // Command line option to specify the name of the function for CFG dump
292 // Defined in Analysis/BlockFrequencyInfo.cpp: -view-bfi-func-name=
293 extern cl::opt<std::string> ViewBlockFreqFuncName;
295 extern cl::opt<bool> DebugInfoCorrelate;
299 PGOOldCFGHashing("pgo-instr-old-cfg-hashing", cl::init(false), cl::Hidden,
300 cl::desc("Use the old CFG function hashing"));
302 // Return a string describing the branch condition that can be
303 // used in static branch probability heuristics:
304 static std::string getBranchCondString(Instruction *TI) {
305 BranchInst *BI = dyn_cast<BranchInst>(TI);
306 if (!BI || !BI->isConditional())
307 return std::string();
309 Value *Cond = BI->getCondition();
310 ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
312 return std::string();
315 raw_string_ostream OS(result);
316 OS << CmpInst::getPredicateName(CI->getPredicate()) << "_";
317 CI->getOperand(0)->getType()->print(OS, true);
319 Value *RHS = CI->getOperand(1);
320 ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
324 else if (CV->isOne())
326 else if (CV->isMinusOne())
335 static const char *ValueProfKindDescr[] = {
336 #define VALUE_PROF_KIND(Enumerator, Value, Descr) Descr,
337 #include "llvm/ProfileData/InstrProfData.inc"
342 /// The select instruction visitor plays three roles specified
343 /// by the mode. In \c VM_counting mode, it simply counts the number of
344 /// select instructions. In \c VM_instrument mode, it inserts code to count
345 /// the number times TrueValue of select is taken. In \c VM_annotate mode,
346 /// it reads the profile data and annotate the select instruction with metadata.
347 enum VisitMode { VM_counting, VM_instrument, VM_annotate };
350 /// Instruction Visitor class to visit select instructions.
351 struct SelectInstVisitor : public InstVisitor<SelectInstVisitor> {
353 unsigned NSIs = 0; // Number of select instructions instrumented.
354 VisitMode Mode = VM_counting; // Visiting mode.
355 unsigned *CurCtrIdx = nullptr; // Pointer to current counter index.
356 unsigned TotalNumCtrs = 0; // Total number of counters
357 GlobalVariable *FuncNameVar = nullptr;
358 uint64_t FuncHash = 0;
359 PGOUseFunc *UseFunc = nullptr;
361 SelectInstVisitor(Function &Func) : F(Func) {}
363 void countSelects(Function &Func) {
369 // Visit the IR stream and instrument all select instructions. \p
370 // Ind is a pointer to the counter index variable; \p TotalNC
371 // is the total number of counters; \p FNV is the pointer to the
372 // PGO function name var; \p FHash is the function hash.
373 void instrumentSelects(Function &Func, unsigned *Ind, unsigned TotalNC,
374 GlobalVariable *FNV, uint64_t FHash) {
375 Mode = VM_instrument;
377 TotalNumCtrs = TotalNC;
383 // Visit the IR stream and annotate all select instructions.
384 void annotateSelects(Function &Func, PGOUseFunc *UF, unsigned *Ind) {
391 void instrumentOneSelectInst(SelectInst &SI);
392 void annotateOneSelectInst(SelectInst &SI);
394 // Visit \p SI instruction and perform tasks according to visit mode.
395 void visitSelectInst(SelectInst &SI);
397 // Return the number of select instructions. This needs be called after
399 unsigned getNumOfSelectInsts() const { return NSIs; }
403 class PGOInstrumentationGenLegacyPass : public ModulePass {
407 PGOInstrumentationGenLegacyPass(bool IsCS = false)
408 : ModulePass(ID), IsCS(IsCS) {
409 initializePGOInstrumentationGenLegacyPassPass(
410 *PassRegistry::getPassRegistry());
413 StringRef getPassName() const override { return "PGOInstrumentationGenPass"; }
416 // Is this is context-sensitive instrumentation.
418 bool runOnModule(Module &M) override;
420 void getAnalysisUsage(AnalysisUsage &AU) const override {
421 AU.addRequired<BlockFrequencyInfoWrapperPass>();
422 AU.addRequired<TargetLibraryInfoWrapperPass>();
426 class PGOInstrumentationUseLegacyPass : public ModulePass {
430 // Provide the profile filename as the parameter.
431 PGOInstrumentationUseLegacyPass(std::string Filename = "", bool IsCS = false)
432 : ModulePass(ID), ProfileFileName(std::move(Filename)), IsCS(IsCS) {
433 if (!PGOTestProfileFile.empty())
434 ProfileFileName = PGOTestProfileFile;
435 initializePGOInstrumentationUseLegacyPassPass(
436 *PassRegistry::getPassRegistry());
439 StringRef getPassName() const override { return "PGOInstrumentationUsePass"; }
442 std::string ProfileFileName;
443 // Is this is context-sensitive instrumentation use.
446 bool runOnModule(Module &M) override;
448 void getAnalysisUsage(AnalysisUsage &AU) const override {
449 AU.addRequired<ProfileSummaryInfoWrapperPass>();
450 AU.addRequired<BlockFrequencyInfoWrapperPass>();
451 AU.addRequired<TargetLibraryInfoWrapperPass>();
455 class PGOInstrumentationGenCreateVarLegacyPass : public ModulePass {
458 StringRef getPassName() const override {
459 return "PGOInstrumentationGenCreateVarPass";
461 PGOInstrumentationGenCreateVarLegacyPass(std::string CSInstrName = "")
462 : ModulePass(ID), InstrProfileOutput(CSInstrName) {
463 initializePGOInstrumentationGenCreateVarLegacyPassPass(
464 *PassRegistry::getPassRegistry());
468 bool runOnModule(Module &M) override {
469 createProfileFileNameVar(M, InstrProfileOutput);
470 // The variable in a comdat may be discarded by LTO. Ensure the
471 // declaration will be retained.
472 appendToCompilerUsed(M, createIRLevelProfileFlagVar(M, /*IsCS=*/true,
474 DebugInfoCorrelate));
477 std::string InstrProfileOutput;
480 } // end anonymous namespace
482 char PGOInstrumentationGenLegacyPass::ID = 0;
484 INITIALIZE_PASS_BEGIN(PGOInstrumentationGenLegacyPass, "pgo-instr-gen",
485 "PGO instrumentation.", false, false)
486 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
487 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
488 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
489 INITIALIZE_PASS_END(PGOInstrumentationGenLegacyPass, "pgo-instr-gen",
490 "PGO instrumentation.", false, false)
492 ModulePass *llvm::createPGOInstrumentationGenLegacyPass(bool IsCS) {
493 return new PGOInstrumentationGenLegacyPass(IsCS);
496 char PGOInstrumentationUseLegacyPass::ID = 0;
498 INITIALIZE_PASS_BEGIN(PGOInstrumentationUseLegacyPass, "pgo-instr-use",
499 "Read PGO instrumentation profile.", false, false)
500 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
501 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
502 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
503 INITIALIZE_PASS_END(PGOInstrumentationUseLegacyPass, "pgo-instr-use",
504 "Read PGO instrumentation profile.", false, false)
506 ModulePass *llvm::createPGOInstrumentationUseLegacyPass(StringRef Filename,
508 return new PGOInstrumentationUseLegacyPass(Filename.str(), IsCS);
511 char PGOInstrumentationGenCreateVarLegacyPass::ID = 0;
513 INITIALIZE_PASS(PGOInstrumentationGenCreateVarLegacyPass,
514 "pgo-instr-gen-create-var",
515 "Create PGO instrumentation version variable for CSPGO.", false,
519 llvm::createPGOInstrumentationGenCreateVarLegacyPass(StringRef CSInstrName) {
520 return new PGOInstrumentationGenCreateVarLegacyPass(std::string(CSInstrName));
525 /// An MST based instrumentation for PGO
527 /// Implements a Minimum Spanning Tree (MST) based instrumentation for PGO
528 /// in the function level.
530 // This class implements the CFG edges. Note the CFG can be a multi-graph.
531 // So there might be multiple edges with same SrcBB and DestBB.
532 const BasicBlock *SrcBB;
533 const BasicBlock *DestBB;
536 bool Removed = false;
537 bool IsCritical = false;
539 PGOEdge(const BasicBlock *Src, const BasicBlock *Dest, uint64_t W = 1)
540 : SrcBB(Src), DestBB(Dest), Weight(W) {}
542 // Return the information string of an edge.
543 std::string infoString() const {
544 return (Twine(Removed ? "-" : " ") + (InMST ? " " : "*") +
545 (IsCritical ? "c" : " ") + " W=" + Twine(Weight)).str();
549 // This class stores the auxiliary information for each BB.
555 BBInfo(unsigned IX) : Group(this), Index(IX) {}
557 // Return the information string of this object.
558 std::string infoString() const {
559 return (Twine("Index=") + Twine(Index)).str();
562 // Empty function -- only applicable to UseBBInfo.
563 void addOutEdge(PGOEdge *E LLVM_ATTRIBUTE_UNUSED) {}
565 // Empty function -- only applicable to UseBBInfo.
566 void addInEdge(PGOEdge *E LLVM_ATTRIBUTE_UNUSED) {}
569 // This class implements the CFG edges. Note the CFG can be a multi-graph.
570 template <class Edge, class BBInfo> class FuncPGOInstrumentation {
574 // Is this is context-sensitive instrumentation.
577 // A map that stores the Comdat group in function F.
578 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers;
580 ValueProfileCollector VPC;
582 void computeCFGHash();
583 void renameComdatFunction();
586 std::vector<std::vector<VPCandidateInfo>> ValueSites;
587 SelectInstVisitor SIVisitor;
588 std::string FuncName;
589 GlobalVariable *FuncNameVar;
591 // CFG hash value for this function.
592 uint64_t FunctionHash = 0;
594 // The Minimum Spanning Tree of function CFG.
595 CFGMST<Edge, BBInfo> MST;
597 // Collect all the BBs that will be instrumented, and store them in
599 void getInstrumentBBs(std::vector<BasicBlock *> &InstrumentBBs);
601 // Give an edge, find the BB that will be instrumented.
602 // Return nullptr if there is no BB to be instrumented.
603 BasicBlock *getInstrBB(Edge *E);
605 // Return the auxiliary BB information.
606 BBInfo &getBBInfo(const BasicBlock *BB) const { return MST.getBBInfo(BB); }
608 // Return the auxiliary BB information if available.
609 BBInfo *findBBInfo(const BasicBlock *BB) const { return MST.findBBInfo(BB); }
611 // Dump edges and BB information.
612 void dumpInfo(std::string Str = "") const {
613 MST.dumpEdges(dbgs(), Twine("Dump Function ") + FuncName + " Hash: " +
614 Twine(FunctionHash) + "\t" + Str);
617 FuncPGOInstrumentation(
618 Function &Func, TargetLibraryInfo &TLI,
619 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers,
620 bool CreateGlobalVar = false, BranchProbabilityInfo *BPI = nullptr,
621 BlockFrequencyInfo *BFI = nullptr, bool IsCS = false,
622 bool InstrumentFuncEntry = true)
623 : F(Func), IsCS(IsCS), ComdatMembers(ComdatMembers), VPC(Func, TLI),
624 ValueSites(IPVK_Last + 1), SIVisitor(Func),
625 MST(F, InstrumentFuncEntry, BPI, BFI) {
626 // This should be done before CFG hash computation.
627 SIVisitor.countSelects(Func);
628 ValueSites[IPVK_MemOPSize] = VPC.get(IPVK_MemOPSize);
630 NumOfPGOSelectInsts += SIVisitor.getNumOfSelectInsts();
631 NumOfPGOMemIntrinsics += ValueSites[IPVK_MemOPSize].size();
632 NumOfPGOBB += MST.BBInfos.size();
633 ValueSites[IPVK_IndirectCallTarget] = VPC.get(IPVK_IndirectCallTarget);
635 NumOfCSPGOSelectInsts += SIVisitor.getNumOfSelectInsts();
636 NumOfCSPGOMemIntrinsics += ValueSites[IPVK_MemOPSize].size();
637 NumOfCSPGOBB += MST.BBInfos.size();
640 FuncName = getPGOFuncName(F);
642 if (!ComdatMembers.empty())
643 renameComdatFunction();
644 LLVM_DEBUG(dumpInfo("after CFGMST"));
646 for (auto &E : MST.AllEdges) {
649 IsCS ? NumOfCSPGOEdge++ : NumOfPGOEdge++;
651 IsCS ? NumOfCSPGOInstrument++ : NumOfPGOInstrument++;
655 FuncNameVar = createPGOFuncNameVar(F, FuncName);
659 } // end anonymous namespace
661 // Compute Hash value for the CFG: the lower 32 bits are CRC32 of the index
662 // value of each BB in the CFG. The higher 32 bits are the CRC32 of the numbers
663 // of selects, indirect calls, mem ops and edges.
664 template <class Edge, class BBInfo>
665 void FuncPGOInstrumentation<Edge, BBInfo>::computeCFGHash() {
666 std::vector<uint8_t> Indexes;
669 const Instruction *TI = BB.getTerminator();
670 for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) {
671 BasicBlock *Succ = TI->getSuccessor(I);
672 auto BI = findBBInfo(Succ);
675 uint32_t Index = BI->Index;
676 for (int J = 0; J < 4; J++)
677 Indexes.push_back((uint8_t)(Index >> (J * 8)));
683 if (PGOOldCFGHashing) {
684 // Hash format for context sensitive profile. Reserve 4 bits for other
686 FunctionHash = (uint64_t)SIVisitor.getNumOfSelectInsts() << 56 |
687 (uint64_t)ValueSites[IPVK_IndirectCallTarget].size() << 48 |
688 //(uint64_t)ValueSites[IPVK_MemOPSize].size() << 40 |
689 (uint64_t)MST.AllEdges.size() << 32 | JC.getCRC();
691 // The higher 32 bits.
692 auto updateJCH = [&JCH](uint64_t Num) {
694 support::endian::write64le(Data, Num);
697 updateJCH((uint64_t)SIVisitor.getNumOfSelectInsts());
698 updateJCH((uint64_t)ValueSites[IPVK_IndirectCallTarget].size());
699 updateJCH((uint64_t)ValueSites[IPVK_MemOPSize].size());
700 updateJCH((uint64_t)MST.AllEdges.size());
702 // Hash format for context sensitive profile. Reserve 4 bits for other
704 FunctionHash = (((uint64_t)JCH.getCRC()) << 28) + JC.getCRC();
707 // Reserve bit 60-63 for other information purpose.
708 FunctionHash &= 0x0FFFFFFFFFFFFFFF;
710 NamedInstrProfRecord::setCSFlagInHash(FunctionHash);
711 LLVM_DEBUG(dbgs() << "Function Hash Computation for " << F.getName() << ":\n"
712 << " CRC = " << JC.getCRC()
713 << ", Selects = " << SIVisitor.getNumOfSelectInsts()
714 << ", Edges = " << MST.AllEdges.size() << ", ICSites = "
715 << ValueSites[IPVK_IndirectCallTarget].size());
716 if (!PGOOldCFGHashing) {
717 LLVM_DEBUG(dbgs() << ", Memops = " << ValueSites[IPVK_MemOPSize].size()
718 << ", High32 CRC = " << JCH.getCRC());
720 LLVM_DEBUG(dbgs() << ", Hash = " << FunctionHash << "\n";);
723 // Check if we can safely rename this Comdat function.
724 static bool canRenameComdat(
726 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers) {
727 if (!DoComdatRenaming || !canRenameComdatFunc(F, true))
730 // FIXME: Current only handle those Comdat groups that only containing one
732 // (1) For a Comdat group containing multiple functions, we need to have a
733 // unique postfix based on the hashes for each function. There is a
734 // non-trivial code refactoring to do this efficiently.
735 // (2) Variables can not be renamed, so we can not rename Comdat function in a
736 // group including global vars.
737 Comdat *C = F.getComdat();
738 for (auto &&CM : make_range(ComdatMembers.equal_range(C))) {
739 assert(!isa<GlobalAlias>(CM.second));
740 Function *FM = dyn_cast<Function>(CM.second);
747 // Append the CFGHash to the Comdat function name.
748 template <class Edge, class BBInfo>
749 void FuncPGOInstrumentation<Edge, BBInfo>::renameComdatFunction() {
750 if (!canRenameComdat(F, ComdatMembers))
752 std::string OrigName = F.getName().str();
753 std::string NewFuncName =
754 Twine(F.getName() + "." + Twine(FunctionHash)).str();
755 F.setName(Twine(NewFuncName));
756 GlobalAlias::create(GlobalValue::WeakAnyLinkage, OrigName, &F);
757 FuncName = Twine(FuncName + "." + Twine(FunctionHash)).str();
759 Module *M = F.getParent();
760 // For AvailableExternallyLinkage functions, change the linkage to
761 // LinkOnceODR and put them into comdat. This is because after renaming, there
762 // is no backup external copy available for the function.
763 if (!F.hasComdat()) {
764 assert(F.getLinkage() == GlobalValue::AvailableExternallyLinkage);
765 NewComdat = M->getOrInsertComdat(StringRef(NewFuncName));
766 F.setLinkage(GlobalValue::LinkOnceODRLinkage);
767 F.setComdat(NewComdat);
771 // This function belongs to a single function Comdat group.
772 Comdat *OrigComdat = F.getComdat();
773 std::string NewComdatName =
774 Twine(OrigComdat->getName() + "." + Twine(FunctionHash)).str();
775 NewComdat = M->getOrInsertComdat(StringRef(NewComdatName));
776 NewComdat->setSelectionKind(OrigComdat->getSelectionKind());
778 for (auto &&CM : make_range(ComdatMembers.equal_range(OrigComdat))) {
779 // Must be a function.
780 cast<Function>(CM.second)->setComdat(NewComdat);
784 // Collect all the BBs that will be instruments and return them in
785 // InstrumentBBs and setup InEdges/OutEdge for UseBBInfo.
786 template <class Edge, class BBInfo>
787 void FuncPGOInstrumentation<Edge, BBInfo>::getInstrumentBBs(
788 std::vector<BasicBlock *> &InstrumentBBs) {
789 // Use a worklist as we will update the vector during the iteration.
790 std::vector<Edge *> EdgeList;
791 EdgeList.reserve(MST.AllEdges.size());
792 for (auto &E : MST.AllEdges)
793 EdgeList.push_back(E.get());
795 for (auto &E : EdgeList) {
796 BasicBlock *InstrBB = getInstrBB(E);
798 InstrumentBBs.push_back(InstrBB);
801 // Set up InEdges/OutEdges for all BBs.
802 for (auto &E : MST.AllEdges) {
805 const BasicBlock *SrcBB = E->SrcBB;
806 const BasicBlock *DestBB = E->DestBB;
807 BBInfo &SrcInfo = getBBInfo(SrcBB);
808 BBInfo &DestInfo = getBBInfo(DestBB);
809 SrcInfo.addOutEdge(E.get());
810 DestInfo.addInEdge(E.get());
814 // Given a CFG E to be instrumented, find which BB to place the instrumented
815 // code. The function will split the critical edge if necessary.
816 template <class Edge, class BBInfo>
817 BasicBlock *FuncPGOInstrumentation<Edge, BBInfo>::getInstrBB(Edge *E) {
818 if (E->InMST || E->Removed)
821 BasicBlock *SrcBB = const_cast<BasicBlock *>(E->SrcBB);
822 BasicBlock *DestBB = const_cast<BasicBlock *>(E->DestBB);
823 // For a fake edge, instrument the real BB.
824 if (SrcBB == nullptr)
826 if (DestBB == nullptr)
829 auto canInstrument = [](BasicBlock *BB) -> BasicBlock * {
830 // There are basic blocks (such as catchswitch) cannot be instrumented.
831 // If the returned first insertion point is the end of BB, skip this BB.
832 if (BB->getFirstInsertionPt() == BB->end())
837 // Instrument the SrcBB if it has a single successor,
838 // otherwise, the DestBB if this is not a critical edge.
839 Instruction *TI = SrcBB->getTerminator();
840 if (TI->getNumSuccessors() <= 1)
841 return canInstrument(SrcBB);
843 return canInstrument(DestBB);
845 // Some IndirectBr critical edges cannot be split by the previous
846 // SplitIndirectBrCriticalEdges call. Bail out.
847 unsigned SuccNum = GetSuccessorNumber(SrcBB, DestBB);
848 BasicBlock *InstrBB =
849 isa<IndirectBrInst>(TI) ? nullptr : SplitCriticalEdge(TI, SuccNum);
852 dbgs() << "Fail to split critical edge: not instrument this edge.\n");
855 // For a critical edge, we have to split. Instrument the newly
857 IsCS ? NumOfCSPGOSplit++ : NumOfPGOSplit++;
858 LLVM_DEBUG(dbgs() << "Split critical edge: " << getBBInfo(SrcBB).Index
859 << " --> " << getBBInfo(DestBB).Index << "\n");
860 // Need to add two new edges. First one: Add new edge of SrcBB->InstrBB.
861 MST.addEdge(SrcBB, InstrBB, 0);
862 // Second one: Add new edge of InstrBB->DestBB.
863 Edge &NewEdge1 = MST.addEdge(InstrBB, DestBB, 0);
864 NewEdge1.InMST = true;
867 return canInstrument(InstrBB);
870 // When generating value profiling calls on Windows routines that make use of
871 // handler funclets for exception processing an operand bundle needs to attached
872 // to the called function. This routine will set \p OpBundles to contain the
873 // funclet information, if any is needed, that should be placed on the generated
874 // value profiling call for the value profile candidate call.
876 populateEHOperandBundle(VPCandidateInfo &Cand,
877 DenseMap<BasicBlock *, ColorVector> &BlockColors,
878 SmallVectorImpl<OperandBundleDef> &OpBundles) {
879 auto *OrigCall = dyn_cast<CallBase>(Cand.AnnotatedInst);
880 if (OrigCall && !isa<IntrinsicInst>(OrigCall)) {
881 // The instrumentation call should belong to the same funclet as a
882 // non-intrinsic call, so just copy the operand bundle, if any exists.
883 Optional<OperandBundleUse> ParentFunclet =
884 OrigCall->getOperandBundle(LLVMContext::OB_funclet);
886 OpBundles.emplace_back(OperandBundleDef(*ParentFunclet));
888 // Intrinsics or other instructions do not get funclet information from the
889 // front-end. Need to use the BlockColors that was computed by the routine
890 // colorEHFunclets to determine whether a funclet is needed.
891 if (!BlockColors.empty()) {
892 const ColorVector &CV = BlockColors.find(OrigCall->getParent())->second;
893 assert(CV.size() == 1 && "non-unique color for block!");
894 Instruction *EHPad = CV.front()->getFirstNonPHI();
895 if (EHPad->isEHPad())
896 OpBundles.emplace_back("funclet", EHPad);
901 // Visit all edge and instrument the edges not in MST, and do value profiling.
902 // Critical edges will be split.
903 static void instrumentOneFunc(
904 Function &F, Module *M, TargetLibraryInfo &TLI, BranchProbabilityInfo *BPI,
905 BlockFrequencyInfo *BFI,
906 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers,
908 // Split indirectbr critical edges here before computing the MST rather than
909 // later in getInstrBB() to avoid invalidating it.
910 SplitIndirectBrCriticalEdges(F, BPI, BFI);
912 FuncPGOInstrumentation<PGOEdge, BBInfo> FuncInfo(
913 F, TLI, ComdatMembers, true, BPI, BFI, IsCS, PGOInstrumentEntry);
914 std::vector<BasicBlock *> InstrumentBBs;
915 FuncInfo.getInstrumentBBs(InstrumentBBs);
916 unsigned NumCounters =
917 InstrumentBBs.size() + FuncInfo.SIVisitor.getNumOfSelectInsts();
920 Type *I8PtrTy = Type::getInt8PtrTy(M->getContext());
921 for (auto *InstrBB : InstrumentBBs) {
922 IRBuilder<> Builder(InstrBB, InstrBB->getFirstInsertionPt());
923 assert(Builder.GetInsertPoint() != InstrBB->end() &&
924 "Cannot get the Instrumentation point");
926 Intrinsic::getDeclaration(M, Intrinsic::instrprof_increment),
927 {ConstantExpr::getBitCast(FuncInfo.FuncNameVar, I8PtrTy),
928 Builder.getInt64(FuncInfo.FunctionHash), Builder.getInt32(NumCounters),
929 Builder.getInt32(I++)});
932 // Now instrument select instructions:
933 FuncInfo.SIVisitor.instrumentSelects(F, &I, NumCounters, FuncInfo.FuncNameVar,
934 FuncInfo.FunctionHash);
935 assert(I == NumCounters);
937 if (DisableValueProfiling)
940 NumOfPGOICall += FuncInfo.ValueSites[IPVK_IndirectCallTarget].size();
942 // Intrinsic function calls do not have funclet operand bundles needed for
943 // Windows exception handling attached to them. However, if value profiling is
944 // inserted for one of these calls, then a funclet value will need to be set
945 // on the instrumentation call based on the funclet coloring.
946 DenseMap<BasicBlock *, ColorVector> BlockColors;
947 if (F.hasPersonalityFn() &&
948 isFuncletEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
949 BlockColors = colorEHFunclets(F);
951 // For each VP Kind, walk the VP candidates and instrument each one.
952 for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) {
953 unsigned SiteIndex = 0;
954 if (Kind == IPVK_MemOPSize && !PGOInstrMemOP)
957 for (VPCandidateInfo Cand : FuncInfo.ValueSites[Kind]) {
958 LLVM_DEBUG(dbgs() << "Instrument one VP " << ValueProfKindDescr[Kind]
959 << " site: CallSite Index = " << SiteIndex << "\n");
961 IRBuilder<> Builder(Cand.InsertPt);
962 assert(Builder.GetInsertPoint() != Cand.InsertPt->getParent()->end() &&
963 "Cannot get the Instrumentation point");
965 Value *ToProfile = nullptr;
966 if (Cand.V->getType()->isIntegerTy())
967 ToProfile = Builder.CreateZExtOrTrunc(Cand.V, Builder.getInt64Ty());
968 else if (Cand.V->getType()->isPointerTy())
969 ToProfile = Builder.CreatePtrToInt(Cand.V, Builder.getInt64Ty());
970 assert(ToProfile && "value profiling Value is of unexpected type");
972 SmallVector<OperandBundleDef, 1> OpBundles;
973 populateEHOperandBundle(Cand, BlockColors, OpBundles);
975 Intrinsic::getDeclaration(M, Intrinsic::instrprof_value_profile),
976 {ConstantExpr::getBitCast(FuncInfo.FuncNameVar, I8PtrTy),
977 Builder.getInt64(FuncInfo.FunctionHash), ToProfile,
978 Builder.getInt32(Kind), Builder.getInt32(SiteIndex++)},
981 } // IPVK_First <= Kind <= IPVK_Last
986 // This class represents a CFG edge in profile use compilation.
987 struct PGOUseEdge : public PGOEdge {
988 bool CountValid = false;
989 uint64_t CountValue = 0;
991 PGOUseEdge(const BasicBlock *Src, const BasicBlock *Dest, uint64_t W = 1)
992 : PGOEdge(Src, Dest, W) {}
994 // Set edge count value
995 void setEdgeCount(uint64_t Value) {
1000 // Return the information string for this object.
1001 std::string infoString() const {
1003 return PGOEdge::infoString();
1004 return (Twine(PGOEdge::infoString()) + " Count=" + Twine(CountValue))
1009 using DirectEdges = SmallVector<PGOUseEdge *, 2>;
1011 // This class stores the auxiliary information for each BB.
1012 struct UseBBInfo : public BBInfo {
1013 uint64_t CountValue = 0;
1015 int32_t UnknownCountInEdge = 0;
1016 int32_t UnknownCountOutEdge = 0;
1017 DirectEdges InEdges;
1018 DirectEdges OutEdges;
1020 UseBBInfo(unsigned IX) : BBInfo(IX), CountValid(false) {}
1022 UseBBInfo(unsigned IX, uint64_t C)
1023 : BBInfo(IX), CountValue(C), CountValid(true) {}
1025 // Set the profile count value for this BB.
1026 void setBBInfoCount(uint64_t Value) {
1031 // Return the information string of this object.
1032 std::string infoString() const {
1034 return BBInfo::infoString();
1035 return (Twine(BBInfo::infoString()) + " Count=" + Twine(CountValue)).str();
1038 // Add an OutEdge and update the edge count.
1039 void addOutEdge(PGOUseEdge *E) {
1040 OutEdges.push_back(E);
1041 UnknownCountOutEdge++;
1044 // Add an InEdge and update the edge count.
1045 void addInEdge(PGOUseEdge *E) {
1046 InEdges.push_back(E);
1047 UnknownCountInEdge++;
1051 } // end anonymous namespace
1053 // Sum up the count values for all the edges.
1054 static uint64_t sumEdgeCount(const ArrayRef<PGOUseEdge *> Edges) {
1056 for (auto &E : Edges) {
1059 Total += E->CountValue;
1068 PGOUseFunc(Function &Func, Module *Modu, TargetLibraryInfo &TLI,
1069 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers,
1070 BranchProbabilityInfo *BPI, BlockFrequencyInfo *BFIin,
1071 ProfileSummaryInfo *PSI, bool IsCS, bool InstrumentFuncEntry)
1072 : F(Func), M(Modu), BFI(BFIin), PSI(PSI),
1073 FuncInfo(Func, TLI, ComdatMembers, false, BPI, BFIin, IsCS,
1074 InstrumentFuncEntry),
1075 FreqAttr(FFA_Normal), IsCS(IsCS) {}
1077 // Read counts for the instrumented BB from profile.
1078 bool readCounters(IndexedInstrProfReader *PGOReader, bool &AllZeros,
1079 bool &AllMinusOnes);
1081 // Populate the counts for all BBs.
1082 void populateCounters();
1084 // Set the branch weights based on the count values.
1085 void setBranchWeights();
1087 // Annotate the value profile call sites for all value kind.
1088 void annotateValueSites();
1090 // Annotate the value profile call sites for one value kind.
1091 void annotateValueSites(uint32_t Kind);
1093 // Annotate the irreducible loop header weights.
1094 void annotateIrrLoopHeaderWeights();
1096 // The hotness of the function from the profile count.
1097 enum FuncFreqAttr { FFA_Normal, FFA_Cold, FFA_Hot };
1099 // Return the function hotness from the profile.
1100 FuncFreqAttr getFuncFreqAttr() const { return FreqAttr; }
1102 // Return the function hash.
1103 uint64_t getFuncHash() const { return FuncInfo.FunctionHash; }
1105 // Return the profile record for this function;
1106 InstrProfRecord &getProfileRecord() { return ProfileRecord; }
1108 // Return the auxiliary BB information.
1109 UseBBInfo &getBBInfo(const BasicBlock *BB) const {
1110 return FuncInfo.getBBInfo(BB);
1113 // Return the auxiliary BB information if available.
1114 UseBBInfo *findBBInfo(const BasicBlock *BB) const {
1115 return FuncInfo.findBBInfo(BB);
1118 Function &getFunc() const { return F; }
1120 void dumpInfo(std::string Str = "") const {
1121 FuncInfo.dumpInfo(Str);
1124 uint64_t getProgramMaxCount() const { return ProgramMaxCount; }
1128 BlockFrequencyInfo *BFI;
1129 ProfileSummaryInfo *PSI;
1131 // This member stores the shared information with class PGOGenFunc.
1132 FuncPGOInstrumentation<PGOUseEdge, UseBBInfo> FuncInfo;
1134 // The maximum count value in the profile. This is only used in PGO use
1136 uint64_t ProgramMaxCount;
1138 // Position of counter that remains to be read.
1139 uint32_t CountPosition = 0;
1141 // Total size of the profile count for this function.
1142 uint32_t ProfileCountSize = 0;
1144 // ProfileRecord for this function.
1145 InstrProfRecord ProfileRecord;
1147 // Function hotness info derived from profile.
1148 FuncFreqAttr FreqAttr;
1150 // Is to use the context sensitive profile.
1153 // Find the Instrumented BB and set the value. Return false on error.
1154 bool setInstrumentedCounts(const std::vector<uint64_t> &CountFromProfile);
1156 // Set the edge counter value for the unknown edge -- there should be only
1157 // one unknown edge.
1158 void setEdgeCount(DirectEdges &Edges, uint64_t Value);
1160 // Return FuncName string;
1161 std::string getFuncName() const { return FuncInfo.FuncName; }
1163 // Set the hot/cold inline hints based on the count values.
1164 // FIXME: This function should be removed once the functionality in
1165 // the inliner is implemented.
1166 void markFunctionAttributes(uint64_t EntryCount, uint64_t MaxCount) {
1167 if (PSI->isHotCount(EntryCount))
1169 else if (PSI->isColdCount(MaxCount))
1170 FreqAttr = FFA_Cold;
1174 } // end anonymous namespace
1176 // Visit all the edges and assign the count value for the instrumented
1177 // edges and the BB. Return false on error.
1178 bool PGOUseFunc::setInstrumentedCounts(
1179 const std::vector<uint64_t> &CountFromProfile) {
1181 std::vector<BasicBlock *> InstrumentBBs;
1182 FuncInfo.getInstrumentBBs(InstrumentBBs);
1183 unsigned NumCounters =
1184 InstrumentBBs.size() + FuncInfo.SIVisitor.getNumOfSelectInsts();
1185 // The number of counters here should match the number of counters
1186 // in profile. Return if they mismatch.
1187 if (NumCounters != CountFromProfile.size()) {
1190 auto *FuncEntry = &*F.begin();
1192 // Set the profile count to the Instrumented BBs.
1194 for (BasicBlock *InstrBB : InstrumentBBs) {
1195 uint64_t CountValue = CountFromProfile[I++];
1196 UseBBInfo &Info = getBBInfo(InstrBB);
1197 // If we reach here, we know that we have some nonzero count
1198 // values in this function. The entry count should not be 0.
1199 // Fix it if necessary.
1200 if (InstrBB == FuncEntry && CountValue == 0)
1202 Info.setBBInfoCount(CountValue);
1204 ProfileCountSize = CountFromProfile.size();
1207 // Set the edge count and update the count of unknown edges for BBs.
1208 auto setEdgeCount = [this](PGOUseEdge *E, uint64_t Value) -> void {
1209 E->setEdgeCount(Value);
1210 this->getBBInfo(E->SrcBB).UnknownCountOutEdge--;
1211 this->getBBInfo(E->DestBB).UnknownCountInEdge--;
1214 // Set the profile count the Instrumented edges. There are BBs that not in
1215 // MST but not instrumented. Need to set the edge count value so that we can
1216 // populate the profile counts later.
1217 for (auto &E : FuncInfo.MST.AllEdges) {
1218 if (E->Removed || E->InMST)
1220 const BasicBlock *SrcBB = E->SrcBB;
1221 UseBBInfo &SrcInfo = getBBInfo(SrcBB);
1223 // If only one out-edge, the edge profile count should be the same as BB
1225 if (SrcInfo.CountValid && SrcInfo.OutEdges.size() == 1)
1226 setEdgeCount(E.get(), SrcInfo.CountValue);
1228 const BasicBlock *DestBB = E->DestBB;
1229 UseBBInfo &DestInfo = getBBInfo(DestBB);
1230 // If only one in-edge, the edge profile count should be the same as BB
1232 if (DestInfo.CountValid && DestInfo.InEdges.size() == 1)
1233 setEdgeCount(E.get(), DestInfo.CountValue);
1237 // E's count should have been set from profile. If not, this meenas E skips
1238 // the instrumentation. We set the count to 0.
1239 setEdgeCount(E.get(), 0);
1244 // Set the count value for the unknown edge. There should be one and only one
1245 // unknown edge in Edges vector.
1246 void PGOUseFunc::setEdgeCount(DirectEdges &Edges, uint64_t Value) {
1247 for (auto &E : Edges) {
1250 E->setEdgeCount(Value);
1252 getBBInfo(E->SrcBB).UnknownCountOutEdge--;
1253 getBBInfo(E->DestBB).UnknownCountInEdge--;
1256 llvm_unreachable("Cannot find the unknown count edge");
1259 // Emit function metadata indicating PGO profile mismatch.
1260 static void annotateFunctionWithHashMismatch(Function &F,
1262 const char MetadataName[] = "instr_prof_hash_mismatch";
1263 SmallVector<Metadata *, 2> Names;
1264 // If this metadata already exists, ignore.
1265 auto *Existing = F.getMetadata(LLVMContext::MD_annotation);
1267 MDTuple *Tuple = cast<MDTuple>(Existing);
1268 for (auto &N : Tuple->operands()) {
1269 if (cast<MDString>(N.get())->getString() == MetadataName)
1271 Names.push_back(N.get());
1276 Names.push_back(MDB.createString(MetadataName));
1277 MDNode *MD = MDTuple::get(ctx, Names);
1278 F.setMetadata(LLVMContext::MD_annotation, MD);
1281 // Read the profile from ProfileFileName and assign the value to the
1282 // instrumented BB and the edges. This function also updates ProgramMaxCount.
1283 // Return true if the profile are successfully read, and false on errors.
1284 bool PGOUseFunc::readCounters(IndexedInstrProfReader *PGOReader, bool &AllZeros,
1285 bool &AllMinusOnes) {
1286 auto &Ctx = M->getContext();
1287 Expected<InstrProfRecord> Result =
1288 PGOReader->getInstrProfRecord(FuncInfo.FuncName, FuncInfo.FunctionHash);
1289 if (Error E = Result.takeError()) {
1290 handleAllErrors(std::move(E), [&](const InstrProfError &IPE) {
1291 auto Err = IPE.get();
1292 bool SkipWarning = false;
1293 LLVM_DEBUG(dbgs() << "Error in reading profile for Func "
1294 << FuncInfo.FuncName << ": ");
1295 if (Err == instrprof_error::unknown_function) {
1296 IsCS ? NumOfCSPGOMissing++ : NumOfPGOMissing++;
1297 SkipWarning = !PGOWarnMissing;
1298 LLVM_DEBUG(dbgs() << "unknown function");
1299 } else if (Err == instrprof_error::hash_mismatch ||
1300 Err == instrprof_error::malformed) {
1301 IsCS ? NumOfCSPGOMismatch++ : NumOfPGOMismatch++;
1303 NoPGOWarnMismatch ||
1304 (NoPGOWarnMismatchComdat &&
1306 F.getLinkage() == GlobalValue::AvailableExternallyLinkage));
1307 LLVM_DEBUG(dbgs() << "hash mismatch (skip=" << SkipWarning << ")");
1308 // Emit function metadata indicating PGO profile mismatch.
1309 annotateFunctionWithHashMismatch(F, M->getContext());
1312 LLVM_DEBUG(dbgs() << " IsCS=" << IsCS << "\n");
1316 std::string Msg = IPE.message() + std::string(" ") + F.getName().str() +
1317 std::string(" Hash = ") +
1318 std::to_string(FuncInfo.FunctionHash);
1321 DiagnosticInfoPGOProfile(M->getName().data(), Msg, DS_Warning));
1325 ProfileRecord = std::move(Result.get());
1326 std::vector<uint64_t> &CountFromProfile = ProfileRecord.Counts;
1328 IsCS ? NumOfCSPGOFunc++ : NumOfPGOFunc++;
1329 LLVM_DEBUG(dbgs() << CountFromProfile.size() << " counts\n");
1330 AllMinusOnes = (CountFromProfile.size() > 0);
1331 uint64_t ValueSum = 0;
1332 for (unsigned I = 0, S = CountFromProfile.size(); I < S; I++) {
1333 LLVM_DEBUG(dbgs() << " " << I << ": " << CountFromProfile[I] << "\n");
1334 ValueSum += CountFromProfile[I];
1335 if (CountFromProfile[I] != (uint64_t)-1)
1336 AllMinusOnes = false;
1338 AllZeros = (ValueSum == 0);
1340 LLVM_DEBUG(dbgs() << "SUM = " << ValueSum << "\n");
1342 getBBInfo(nullptr).UnknownCountOutEdge = 2;
1343 getBBInfo(nullptr).UnknownCountInEdge = 2;
1345 if (!setInstrumentedCounts(CountFromProfile)) {
1347 dbgs() << "Inconsistent number of counts, skipping this function");
1348 Ctx.diagnose(DiagnosticInfoPGOProfile(
1349 M->getName().data(),
1350 Twine("Inconsistent number of counts in ") + F.getName().str()
1351 + Twine(": the profile may be stale or there is a function name collision."),
1355 ProgramMaxCount = PGOReader->getMaximumFunctionCount(IsCS);
1359 // Populate the counters from instrumented BBs to all BBs.
1360 // In the end of this operation, all BBs should have a valid count value.
1361 void PGOUseFunc::populateCounters() {
1362 bool Changes = true;
1363 unsigned NumPasses = 0;
1368 // For efficient traversal, it's better to start from the end as most
1369 // of the instrumented edges are at the end.
1370 for (auto &BB : reverse(F)) {
1371 UseBBInfo *Count = findBBInfo(&BB);
1372 if (Count == nullptr)
1374 if (!Count->CountValid) {
1375 if (Count->UnknownCountOutEdge == 0) {
1376 Count->CountValue = sumEdgeCount(Count->OutEdges);
1377 Count->CountValid = true;
1379 } else if (Count->UnknownCountInEdge == 0) {
1380 Count->CountValue = sumEdgeCount(Count->InEdges);
1381 Count->CountValid = true;
1385 if (Count->CountValid) {
1386 if (Count->UnknownCountOutEdge == 1) {
1388 uint64_t OutSum = sumEdgeCount(Count->OutEdges);
1389 // If the one of the successor block can early terminate (no-return),
1390 // we can end up with situation where out edge sum count is larger as
1391 // the source BB's count is collected by a post-dominated block.
1392 if (Count->CountValue > OutSum)
1393 Total = Count->CountValue - OutSum;
1394 setEdgeCount(Count->OutEdges, Total);
1397 if (Count->UnknownCountInEdge == 1) {
1399 uint64_t InSum = sumEdgeCount(Count->InEdges);
1400 if (Count->CountValue > InSum)
1401 Total = Count->CountValue - InSum;
1402 setEdgeCount(Count->InEdges, Total);
1409 LLVM_DEBUG(dbgs() << "Populate counts in " << NumPasses << " passes.\n");
1411 // Assert every BB has a valid counter.
1412 for (auto &BB : F) {
1413 auto BI = findBBInfo(&BB);
1416 assert(BI->CountValid && "BB count is not valid");
1419 uint64_t FuncEntryCount = getBBInfo(&*F.begin()).CountValue;
1420 uint64_t FuncMaxCount = FuncEntryCount;
1421 for (auto &BB : F) {
1422 auto BI = findBBInfo(&BB);
1425 FuncMaxCount = std::max(FuncMaxCount, BI->CountValue);
1428 // Fix the obviously inconsistent entry count.
1429 if (FuncMaxCount > 0 && FuncEntryCount == 0)
1431 F.setEntryCount(ProfileCount(FuncEntryCount, Function::PCT_Real));
1432 markFunctionAttributes(FuncEntryCount, FuncMaxCount);
1434 // Now annotate select instructions
1435 FuncInfo.SIVisitor.annotateSelects(F, this, &CountPosition);
1436 assert(CountPosition == ProfileCountSize);
1438 LLVM_DEBUG(FuncInfo.dumpInfo("after reading profile."));
1441 // Assign the scaled count values to the BB with multiple out edges.
1442 void PGOUseFunc::setBranchWeights() {
1443 // Generate MD_prof metadata for every branch instruction.
1444 LLVM_DEBUG(dbgs() << "\nSetting branch weights for func " << F.getName()
1445 << " IsCS=" << IsCS << "\n");
1446 for (auto &BB : F) {
1447 Instruction *TI = BB.getTerminator();
1448 if (TI->getNumSuccessors() < 2)
1450 if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) ||
1451 isa<IndirectBrInst>(TI) || isa<InvokeInst>(TI)))
1454 if (getBBInfo(&BB).CountValue == 0)
1457 // We have a non-zero Branch BB.
1458 const UseBBInfo &BBCountInfo = getBBInfo(&BB);
1459 unsigned Size = BBCountInfo.OutEdges.size();
1460 SmallVector<uint64_t, 2> EdgeCounts(Size, 0);
1461 uint64_t MaxCount = 0;
1462 for (unsigned s = 0; s < Size; s++) {
1463 const PGOUseEdge *E = BBCountInfo.OutEdges[s];
1464 const BasicBlock *SrcBB = E->SrcBB;
1465 const BasicBlock *DestBB = E->DestBB;
1466 if (DestBB == nullptr)
1468 unsigned SuccNum = GetSuccessorNumber(SrcBB, DestBB);
1469 uint64_t EdgeCount = E->CountValue;
1470 if (EdgeCount > MaxCount)
1471 MaxCount = EdgeCount;
1472 EdgeCounts[SuccNum] = EdgeCount;
1474 setProfMetadata(M, TI, EdgeCounts, MaxCount);
1478 static bool isIndirectBrTarget(BasicBlock *BB) {
1479 for (BasicBlock *Pred : predecessors(BB)) {
1480 if (isa<IndirectBrInst>(Pred->getTerminator()))
1486 void PGOUseFunc::annotateIrrLoopHeaderWeights() {
1487 LLVM_DEBUG(dbgs() << "\nAnnotating irreducible loop header weights.\n");
1488 // Find irr loop headers
1489 for (auto &BB : F) {
1490 // As a heuristic also annotate indrectbr targets as they have a high chance
1491 // to become an irreducible loop header after the indirectbr tail
1493 if (BFI->isIrrLoopHeader(&BB) || isIndirectBrTarget(&BB)) {
1494 Instruction *TI = BB.getTerminator();
1495 const UseBBInfo &BBCountInfo = getBBInfo(&BB);
1496 setIrrLoopHeaderMetadata(M, TI, BBCountInfo.CountValue);
1501 void SelectInstVisitor::instrumentOneSelectInst(SelectInst &SI) {
1502 Module *M = F.getParent();
1503 IRBuilder<> Builder(&SI);
1504 Type *Int64Ty = Builder.getInt64Ty();
1505 Type *I8PtrTy = Builder.getInt8PtrTy();
1506 auto *Step = Builder.CreateZExt(SI.getCondition(), Int64Ty);
1508 Intrinsic::getDeclaration(M, Intrinsic::instrprof_increment_step),
1509 {ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
1510 Builder.getInt64(FuncHash), Builder.getInt32(TotalNumCtrs),
1511 Builder.getInt32(*CurCtrIdx), Step});
1515 void SelectInstVisitor::annotateOneSelectInst(SelectInst &SI) {
1516 std::vector<uint64_t> &CountFromProfile = UseFunc->getProfileRecord().Counts;
1517 assert(*CurCtrIdx < CountFromProfile.size() &&
1518 "Out of bound access of counters");
1519 uint64_t SCounts[2];
1520 SCounts[0] = CountFromProfile[*CurCtrIdx]; // True count
1522 uint64_t TotalCount = 0;
1523 auto BI = UseFunc->findBBInfo(SI.getParent());
1525 TotalCount = BI->CountValue;
1527 SCounts[1] = (TotalCount > SCounts[0] ? TotalCount - SCounts[0] : 0);
1528 uint64_t MaxCount = std::max(SCounts[0], SCounts[1]);
1530 setProfMetadata(F.getParent(), &SI, SCounts, MaxCount);
1533 void SelectInstVisitor::visitSelectInst(SelectInst &SI) {
1534 if (!PGOInstrSelect)
1536 // FIXME: do not handle this yet.
1537 if (SI.getCondition()->getType()->isVectorTy())
1545 instrumentOneSelectInst(SI);
1548 annotateOneSelectInst(SI);
1552 llvm_unreachable("Unknown visiting mode");
1555 // Traverse all valuesites and annotate the instructions for all value kind.
1556 void PGOUseFunc::annotateValueSites() {
1557 if (DisableValueProfiling)
1560 // Create the PGOFuncName meta data.
1561 createPGOFuncNameMetadata(F, FuncInfo.FuncName);
1563 for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
1564 annotateValueSites(Kind);
1567 // Annotate the instructions for a specific value kind.
1568 void PGOUseFunc::annotateValueSites(uint32_t Kind) {
1569 assert(Kind <= IPVK_Last);
1570 unsigned ValueSiteIndex = 0;
1571 auto &ValueSites = FuncInfo.ValueSites[Kind];
1572 unsigned NumValueSites = ProfileRecord.getNumValueSites(Kind);
1573 if (NumValueSites != ValueSites.size()) {
1574 auto &Ctx = M->getContext();
1575 Ctx.diagnose(DiagnosticInfoPGOProfile(
1576 M->getName().data(),
1577 Twine("Inconsistent number of value sites for ") +
1578 Twine(ValueProfKindDescr[Kind]) +
1579 Twine(" profiling in \"") + F.getName().str() +
1580 Twine("\", possibly due to the use of a stale profile."),
1585 for (VPCandidateInfo &I : ValueSites) {
1586 LLVM_DEBUG(dbgs() << "Read one value site profile (kind = " << Kind
1587 << "): Index = " << ValueSiteIndex << " out of "
1588 << NumValueSites << "\n");
1589 annotateValueSite(*M, *I.AnnotatedInst, ProfileRecord,
1590 static_cast<InstrProfValueKind>(Kind), ValueSiteIndex,
1591 Kind == IPVK_MemOPSize ? MaxNumMemOPAnnotations
1592 : MaxNumAnnotations);
1597 // Collect the set of members for each Comdat in module M and store
1598 // in ComdatMembers.
1599 static void collectComdatMembers(
1601 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers) {
1602 if (!DoComdatRenaming)
1604 for (Function &F : M)
1605 if (Comdat *C = F.getComdat())
1606 ComdatMembers.insert(std::make_pair(C, &F));
1607 for (GlobalVariable &GV : M.globals())
1608 if (Comdat *C = GV.getComdat())
1609 ComdatMembers.insert(std::make_pair(C, &GV));
1610 for (GlobalAlias &GA : M.aliases())
1611 if (Comdat *C = GA.getComdat())
1612 ComdatMembers.insert(std::make_pair(C, &GA));
1615 static bool InstrumentAllFunctions(
1616 Module &M, function_ref<TargetLibraryInfo &(Function &)> LookupTLI,
1617 function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
1618 function_ref<BlockFrequencyInfo *(Function &)> LookupBFI, bool IsCS) {
1619 // For the context-sensitve instrumentation, we should have a separated pass
1620 // (before LTO/ThinLTO linking) to create these variables.
1622 createIRLevelProfileFlagVar(M, /*IsCS=*/false, PGOInstrumentEntry,
1623 DebugInfoCorrelate);
1624 std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
1625 collectComdatMembers(M, ComdatMembers);
1628 if (F.isDeclaration())
1630 if (F.hasFnAttribute(llvm::Attribute::NoProfile))
1632 auto &TLI = LookupTLI(F);
1633 auto *BPI = LookupBPI(F);
1634 auto *BFI = LookupBFI(F);
1635 instrumentOneFunc(F, &M, TLI, BPI, BFI, ComdatMembers, IsCS);
1641 PGOInstrumentationGenCreateVar::run(Module &M, ModuleAnalysisManager &AM) {
1642 createProfileFileNameVar(M, CSInstrName);
1643 // The variable in a comdat may be discarded by LTO. Ensure the declaration
1644 // will be retained.
1645 appendToCompilerUsed(M, createIRLevelProfileFlagVar(M, /*IsCS=*/true,
1647 DebugInfoCorrelate));
1648 return PreservedAnalyses::all();
1651 bool PGOInstrumentationGenLegacyPass::runOnModule(Module &M) {
1655 auto LookupTLI = [this](Function &F) -> TargetLibraryInfo & {
1656 return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1658 auto LookupBPI = [this](Function &F) {
1659 return &this->getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
1661 auto LookupBFI = [this](Function &F) {
1662 return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
1664 return InstrumentAllFunctions(M, LookupTLI, LookupBPI, LookupBFI, IsCS);
1667 PreservedAnalyses PGOInstrumentationGen::run(Module &M,
1668 ModuleAnalysisManager &AM) {
1669 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
1670 auto LookupTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
1671 return FAM.getResult<TargetLibraryAnalysis>(F);
1673 auto LookupBPI = [&FAM](Function &F) {
1674 return &FAM.getResult<BranchProbabilityAnalysis>(F);
1676 auto LookupBFI = [&FAM](Function &F) {
1677 return &FAM.getResult<BlockFrequencyAnalysis>(F);
1680 if (!InstrumentAllFunctions(M, LookupTLI, LookupBPI, LookupBFI, IsCS))
1681 return PreservedAnalyses::all();
1683 return PreservedAnalyses::none();
1686 // Using the ratio b/w sums of profile count values and BFI count values to
1687 // adjust the func entry count.
1688 static void fixFuncEntryCount(PGOUseFunc &Func, LoopInfo &LI,
1689 BranchProbabilityInfo &NBPI) {
1690 Function &F = Func.getFunc();
1691 BlockFrequencyInfo NBFI(F, NBPI, LI);
1693 auto BFIEntryCount = F.getEntryCount();
1694 assert(BFIEntryCount.hasValue() && (BFIEntryCount->getCount() > 0) &&
1695 "Invalid BFI Entrycount");
1697 auto SumCount = APFloat::getZero(APFloat::IEEEdouble());
1698 auto SumBFICount = APFloat::getZero(APFloat::IEEEdouble());
1699 for (auto &BBI : F) {
1700 uint64_t CountValue = 0;
1701 uint64_t BFICountValue = 0;
1702 if (!Func.findBBInfo(&BBI))
1704 auto BFICount = NBFI.getBlockProfileCount(&BBI);
1705 CountValue = Func.getBBInfo(&BBI).CountValue;
1706 BFICountValue = BFICount.getValue();
1707 SumCount.add(APFloat(CountValue * 1.0), APFloat::rmNearestTiesToEven);
1708 SumBFICount.add(APFloat(BFICountValue * 1.0), APFloat::rmNearestTiesToEven);
1710 if (SumCount.isZero())
1713 assert(SumBFICount.compare(APFloat(0.0)) == APFloat::cmpGreaterThan &&
1714 "Incorrect sum of BFI counts");
1715 if (SumBFICount.compare(SumCount) == APFloat::cmpEqual)
1717 double Scale = (SumCount / SumBFICount).convertToDouble();
1718 if (Scale < 1.001 && Scale > 0.999)
1721 uint64_t FuncEntryCount = Func.getBBInfo(&*F.begin()).CountValue;
1722 uint64_t NewEntryCount = 0.5 + FuncEntryCount * Scale;
1723 if (NewEntryCount == 0)
1725 if (NewEntryCount != FuncEntryCount) {
1726 F.setEntryCount(ProfileCount(NewEntryCount, Function::PCT_Real));
1727 LLVM_DEBUG(dbgs() << "FixFuncEntryCount: in " << F.getName()
1728 << ", entry_count " << FuncEntryCount << " --> "
1729 << NewEntryCount << "\n");
1733 // Compare the profile count values with BFI count values, and print out
1734 // the non-matching ones.
1735 static void verifyFuncBFI(PGOUseFunc &Func, LoopInfo &LI,
1736 BranchProbabilityInfo &NBPI,
1737 uint64_t HotCountThreshold,
1738 uint64_t ColdCountThreshold) {
1739 Function &F = Func.getFunc();
1740 BlockFrequencyInfo NBFI(F, NBPI, LI);
1741 // bool PrintFunc = false;
1742 bool HotBBOnly = PGOVerifyHotBFI;
1744 OptimizationRemarkEmitter ORE(&F);
1746 unsigned BBNum = 0, BBMisMatchNum = 0, NonZeroBBNum = 0;
1747 for (auto &BBI : F) {
1748 uint64_t CountValue = 0;
1749 uint64_t BFICountValue = 0;
1751 if (Func.getBBInfo(&BBI).CountValid)
1752 CountValue = Func.getBBInfo(&BBI).CountValue;
1757 auto BFICount = NBFI.getBlockProfileCount(&BBI);
1759 BFICountValue = BFICount.getValue();
1762 bool rawIsHot = CountValue >= HotCountThreshold;
1763 bool BFIIsHot = BFICountValue >= HotCountThreshold;
1764 bool rawIsCold = CountValue <= ColdCountThreshold;
1765 bool ShowCount = false;
1766 if (rawIsHot && !BFIIsHot) {
1767 Msg = "raw-Hot to BFI-nonHot";
1769 } else if (rawIsCold && BFIIsHot) {
1770 Msg = "raw-Cold to BFI-Hot";
1776 if ((CountValue < PGOVerifyBFICutoff) &&
1777 (BFICountValue < PGOVerifyBFICutoff))
1779 uint64_t Diff = (BFICountValue >= CountValue)
1780 ? BFICountValue - CountValue
1781 : CountValue - BFICountValue;
1782 if (Diff <= CountValue / 100 * PGOVerifyBFIRatio)
1788 OptimizationRemarkAnalysis Remark(DEBUG_TYPE, "bfi-verify",
1789 F.getSubprogram(), &BBI);
1790 Remark << "BB " << ore::NV("Block", BBI.getName())
1791 << " Count=" << ore::NV("Count", CountValue)
1792 << " BFI_Count=" << ore::NV("Count", BFICountValue);
1794 Remark << " (" << Msg << ")";
1800 return OptimizationRemarkAnalysis(DEBUG_TYPE, "bfi-verify",
1801 F.getSubprogram(), &F.getEntryBlock())
1802 << "In Func " << ore::NV("Function", F.getName())
1803 << ": Num_of_BB=" << ore::NV("Count", BBNum)
1804 << ", Num_of_non_zerovalue_BB=" << ore::NV("Count", NonZeroBBNum)
1805 << ", Num_of_mis_matching_BB=" << ore::NV("Count", BBMisMatchNum);
1809 static bool annotateAllFunctions(
1810 Module &M, StringRef ProfileFileName, StringRef ProfileRemappingFileName,
1811 function_ref<TargetLibraryInfo &(Function &)> LookupTLI,
1812 function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
1813 function_ref<BlockFrequencyInfo *(Function &)> LookupBFI,
1814 ProfileSummaryInfo *PSI, bool IsCS) {
1815 LLVM_DEBUG(dbgs() << "Read in profile counters: ");
1816 auto &Ctx = M.getContext();
1817 // Read the counter array from file.
1819 IndexedInstrProfReader::create(ProfileFileName, ProfileRemappingFileName);
1820 if (Error E = ReaderOrErr.takeError()) {
1821 handleAllErrors(std::move(E), [&](const ErrorInfoBase &EI) {
1823 DiagnosticInfoPGOProfile(ProfileFileName.data(), EI.message()));
1828 std::unique_ptr<IndexedInstrProfReader> PGOReader =
1829 std::move(ReaderOrErr.get());
1831 Ctx.diagnose(DiagnosticInfoPGOProfile(ProfileFileName.data(),
1832 StringRef("Cannot get PGOReader")));
1835 if (!PGOReader->hasCSIRLevelProfile() && IsCS)
1838 // TODO: might need to change the warning once the clang option is finalized.
1839 if (!PGOReader->isIRLevelProfile()) {
1840 Ctx.diagnose(DiagnosticInfoPGOProfile(
1841 ProfileFileName.data(), "Not an IR level instrumentation profile"));
1845 // Add the profile summary (read from the header of the indexed summary) here
1846 // so that we can use it below when reading counters (which checks if the
1847 // function should be marked with a cold or inlinehint attribute).
1848 M.setProfileSummary(PGOReader->getSummary(IsCS).getMD(M.getContext()),
1849 IsCS ? ProfileSummary::PSK_CSInstr
1850 : ProfileSummary::PSK_Instr);
1853 std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
1854 collectComdatMembers(M, ComdatMembers);
1855 std::vector<Function *> HotFunctions;
1856 std::vector<Function *> ColdFunctions;
1858 // If the profile marked as always instrument the entry BB, do the
1859 // same. Note this can be overwritten by the internal option in CFGMST.h
1860 bool InstrumentFuncEntry = PGOReader->instrEntryBBEnabled();
1861 if (PGOInstrumentEntry.getNumOccurrences() > 0)
1862 InstrumentFuncEntry = PGOInstrumentEntry;
1864 if (F.isDeclaration())
1866 auto &TLI = LookupTLI(F);
1867 auto *BPI = LookupBPI(F);
1868 auto *BFI = LookupBFI(F);
1869 // Split indirectbr critical edges here before computing the MST rather than
1870 // later in getInstrBB() to avoid invalidating it.
1871 SplitIndirectBrCriticalEdges(F, BPI, BFI);
1872 PGOUseFunc Func(F, &M, TLI, ComdatMembers, BPI, BFI, PSI, IsCS,
1873 InstrumentFuncEntry);
1874 // When AllMinusOnes is true, it means the profile for the function
1875 // is unrepresentative and this function is actually hot. Set the
1876 // entry count of the function to be multiple times of hot threshold
1877 // and drop all its internal counters.
1878 bool AllMinusOnes = false;
1879 bool AllZeros = false;
1880 if (!Func.readCounters(PGOReader.get(), AllZeros, AllMinusOnes))
1883 F.setEntryCount(ProfileCount(0, Function::PCT_Real));
1884 if (Func.getProgramMaxCount() != 0)
1885 ColdFunctions.push_back(&F);
1888 const unsigned MultiplyFactor = 3;
1890 uint64_t HotThreshold = PSI->getHotCountThreshold();
1893 ProfileCount(HotThreshold * MultiplyFactor, Function::PCT_Real));
1894 HotFunctions.push_back(&F);
1897 Func.populateCounters();
1898 Func.setBranchWeights();
1899 Func.annotateValueSites();
1900 Func.annotateIrrLoopHeaderWeights();
1901 PGOUseFunc::FuncFreqAttr FreqAttr = Func.getFuncFreqAttr();
1902 if (FreqAttr == PGOUseFunc::FFA_Cold)
1903 ColdFunctions.push_back(&F);
1904 else if (FreqAttr == PGOUseFunc::FFA_Hot)
1905 HotFunctions.push_back(&F);
1906 if (PGOViewCounts != PGOVCT_None &&
1907 (ViewBlockFreqFuncName.empty() ||
1908 F.getName().equals(ViewBlockFreqFuncName))) {
1909 LoopInfo LI{DominatorTree(F)};
1910 std::unique_ptr<BranchProbabilityInfo> NewBPI =
1911 std::make_unique<BranchProbabilityInfo>(F, LI);
1912 std::unique_ptr<BlockFrequencyInfo> NewBFI =
1913 std::make_unique<BlockFrequencyInfo>(F, *NewBPI, LI);
1914 if (PGOViewCounts == PGOVCT_Graph)
1916 else if (PGOViewCounts == PGOVCT_Text) {
1917 dbgs() << "pgo-view-counts: " << Func.getFunc().getName() << "\n";
1918 NewBFI->print(dbgs());
1921 if (PGOViewRawCounts != PGOVCT_None &&
1922 (ViewBlockFreqFuncName.empty() ||
1923 F.getName().equals(ViewBlockFreqFuncName))) {
1924 if (PGOViewRawCounts == PGOVCT_Graph)
1925 if (ViewBlockFreqFuncName.empty())
1926 WriteGraph(&Func, Twine("PGORawCounts_") + Func.getFunc().getName());
1928 ViewGraph(&Func, Twine("PGORawCounts_") + Func.getFunc().getName());
1929 else if (PGOViewRawCounts == PGOVCT_Text) {
1930 dbgs() << "pgo-view-raw-counts: " << Func.getFunc().getName() << "\n";
1935 if (PGOVerifyBFI || PGOVerifyHotBFI || PGOFixEntryCount) {
1936 LoopInfo LI{DominatorTree(F)};
1937 BranchProbabilityInfo NBPI(F, LI);
1939 // Fix func entry count.
1940 if (PGOFixEntryCount)
1941 fixFuncEntryCount(Func, LI, NBPI);
1943 // Verify BlockFrequency information.
1944 uint64_t HotCountThreshold = 0, ColdCountThreshold = 0;
1945 if (PGOVerifyHotBFI) {
1946 HotCountThreshold = PSI->getOrCompHotCountThreshold();
1947 ColdCountThreshold = PSI->getOrCompColdCountThreshold();
1949 verifyFuncBFI(Func, LI, NBPI, HotCountThreshold, ColdCountThreshold);
1953 // Set function hotness attribute from the profile.
1954 // We have to apply these attributes at the end because their presence
1955 // can affect the BranchProbabilityInfo of any callers, resulting in an
1956 // inconsistent MST between prof-gen and prof-use.
1957 for (auto &F : HotFunctions) {
1958 F->addFnAttr(Attribute::InlineHint);
1959 LLVM_DEBUG(dbgs() << "Set inline attribute to function: " << F->getName()
1962 for (auto &F : ColdFunctions) {
1963 // Only set when there is no Attribute::Hot set by the user. For Hot
1964 // attribute, user's annotation has the precedence over the profile.
1965 if (F->hasFnAttribute(Attribute::Hot)) {
1966 auto &Ctx = M.getContext();
1967 std::string Msg = std::string("Function ") + F->getName().str() +
1968 std::string(" is annotated as a hot function but"
1969 " the profile is cold");
1971 DiagnosticInfoPGOProfile(M.getName().data(), Msg, DS_Warning));
1974 F->addFnAttr(Attribute::Cold);
1975 LLVM_DEBUG(dbgs() << "Set cold attribute to function: " << F->getName()
1981 PGOInstrumentationUse::PGOInstrumentationUse(std::string Filename,
1982 std::string RemappingFilename,
1984 : ProfileFileName(std::move(Filename)),
1985 ProfileRemappingFileName(std::move(RemappingFilename)), IsCS(IsCS) {
1986 if (!PGOTestProfileFile.empty())
1987 ProfileFileName = PGOTestProfileFile;
1988 if (!PGOTestProfileRemappingFile.empty())
1989 ProfileRemappingFileName = PGOTestProfileRemappingFile;
1992 PreservedAnalyses PGOInstrumentationUse::run(Module &M,
1993 ModuleAnalysisManager &AM) {
1995 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
1996 auto LookupTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
1997 return FAM.getResult<TargetLibraryAnalysis>(F);
1999 auto LookupBPI = [&FAM](Function &F) {
2000 return &FAM.getResult<BranchProbabilityAnalysis>(F);
2002 auto LookupBFI = [&FAM](Function &F) {
2003 return &FAM.getResult<BlockFrequencyAnalysis>(F);
2006 auto *PSI = &AM.getResult<ProfileSummaryAnalysis>(M);
2008 if (!annotateAllFunctions(M, ProfileFileName, ProfileRemappingFileName,
2009 LookupTLI, LookupBPI, LookupBFI, PSI, IsCS))
2010 return PreservedAnalyses::all();
2012 return PreservedAnalyses::none();
2015 bool PGOInstrumentationUseLegacyPass::runOnModule(Module &M) {
2019 auto LookupTLI = [this](Function &F) -> TargetLibraryInfo & {
2020 return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
2022 auto LookupBPI = [this](Function &F) {
2023 return &this->getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
2025 auto LookupBFI = [this](Function &F) {
2026 return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
2029 auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
2030 return annotateAllFunctions(M, ProfileFileName, "", LookupTLI, LookupBPI,
2031 LookupBFI, PSI, IsCS);
2034 static std::string getSimpleNodeName(const BasicBlock *Node) {
2035 if (!Node->getName().empty())
2036 return std::string(Node->getName());
2038 std::string SimpleNodeName;
2039 raw_string_ostream OS(SimpleNodeName);
2040 Node->printAsOperand(OS, false);
2044 void llvm::setProfMetadata(Module *M, Instruction *TI,
2045 ArrayRef<uint64_t> EdgeCounts,
2046 uint64_t MaxCount) {
2047 MDBuilder MDB(M->getContext());
2048 assert(MaxCount > 0 && "Bad max count");
2049 uint64_t Scale = calculateCountScale(MaxCount);
2050 SmallVector<unsigned, 4> Weights;
2051 for (const auto &ECI : EdgeCounts)
2052 Weights.push_back(scaleBranchCount(ECI, Scale));
2054 LLVM_DEBUG(dbgs() << "Weight is: "; for (const auto &W
2059 TI->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
2060 if (EmitBranchProbability) {
2061 std::string BrCondStr = getBranchCondString(TI);
2062 if (BrCondStr.empty())
2066 std::accumulate(Weights.begin(), Weights.end(), (uint64_t)0,
2067 [](uint64_t w1, uint64_t w2) { return w1 + w2; });
2068 uint64_t TotalCount =
2069 std::accumulate(EdgeCounts.begin(), EdgeCounts.end(), (uint64_t)0,
2070 [](uint64_t c1, uint64_t c2) { return c1 + c2; });
2071 Scale = calculateCountScale(WSum);
2072 BranchProbability BP(scaleBranchCount(Weights[0], Scale),
2073 scaleBranchCount(WSum, Scale));
2074 std::string BranchProbStr;
2075 raw_string_ostream OS(BranchProbStr);
2077 OS << " (total count : " << TotalCount << ")";
2079 Function *F = TI->getParent()->getParent();
2080 OptimizationRemarkEmitter ORE(F);
2082 return OptimizationRemark(DEBUG_TYPE, "pgo-instrumentation", TI)
2083 << BrCondStr << " is true with probability : " << BranchProbStr;
2090 void setIrrLoopHeaderMetadata(Module *M, Instruction *TI, uint64_t Count) {
2091 MDBuilder MDB(M->getContext());
2092 TI->setMetadata(llvm::LLVMContext::MD_irr_loop,
2093 MDB.createIrrLoopHeaderWeight(Count));
2096 template <> struct GraphTraits<PGOUseFunc *> {
2097 using NodeRef = const BasicBlock *;
2098 using ChildIteratorType = const_succ_iterator;
2099 using nodes_iterator = pointer_iterator<Function::const_iterator>;
2101 static NodeRef getEntryNode(const PGOUseFunc *G) {
2102 return &G->getFunc().front();
2105 static ChildIteratorType child_begin(const NodeRef N) {
2106 return succ_begin(N);
2109 static ChildIteratorType child_end(const NodeRef N) { return succ_end(N); }
2111 static nodes_iterator nodes_begin(const PGOUseFunc *G) {
2112 return nodes_iterator(G->getFunc().begin());
2115 static nodes_iterator nodes_end(const PGOUseFunc *G) {
2116 return nodes_iterator(G->getFunc().end());
2120 template <> struct DOTGraphTraits<PGOUseFunc *> : DefaultDOTGraphTraits {
2121 explicit DOTGraphTraits(bool isSimple = false)
2122 : DefaultDOTGraphTraits(isSimple) {}
2124 static std::string getGraphName(const PGOUseFunc *G) {
2125 return std::string(G->getFunc().getName());
2128 std::string getNodeLabel(const BasicBlock *Node, const PGOUseFunc *Graph) {
2130 raw_string_ostream OS(Result);
2132 OS << getSimpleNodeName(Node) << ":\\l";
2133 UseBBInfo *BI = Graph->findBBInfo(Node);
2135 if (BI && BI->CountValid)
2136 OS << BI->CountValue << "\\l";
2140 if (!PGOInstrSelect)
2143 for (const Instruction &I : *Node) {
2144 if (!isa<SelectInst>(&I))
2146 // Display scaled counts for SELECT instruction:
2147 OS << "SELECT : { T = ";
2149 bool HasProf = I.extractProfMetadata(TC, FC);
2151 OS << "Unknown, F = Unknown }\\l";
2153 OS << TC << ", F = " << FC << " }\\l";
2159 } // end namespace llvm