1//===- PGOInstrumentation.cpp - MST-based PGO Instrumentation -------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements 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.
19//
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.
24//
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
28// profiling.
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.
32//
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.
40//
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).
47//
48//===----------------------------------------------------------------------===//
49
50#include "llvm/Transforms/Instrumentation/PGOInstrumentation.h"
51#include "InstrumentationOptions.h"
52#include "ValueProfileCollector.h"
53#include "llvm/ADT/APInt.h"
54#include "llvm/ADT/ArrayRef.h"
55#include "llvm/ADT/STLExtras.h"
56#include "llvm/ADT/SmallVector.h"
57#include "llvm/ADT/Statistic.h"
58#include "llvm/ADT/StringRef.h"
59#include "llvm/ADT/StringSet.h"
60#include "llvm/ADT/Twine.h"
61#include "llvm/ADT/iterator.h"
62#include "llvm/ADT/iterator_range.h"
63#include "llvm/Analysis/BlockFrequencyInfo.h"
64#include "llvm/Analysis/BranchProbabilityInfo.h"
65#include "llvm/Analysis/CFG.h"
66#include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
67#include "llvm/Analysis/LoopInfo.h"
68#include "llvm/Analysis/OptimizationRemarkEmitter.h"
69#include "llvm/Analysis/ProfileSummaryInfo.h"
70#include "llvm/Analysis/TargetLibraryInfo.h"
71#include "llvm/Analysis/ValueTracking.h"
72#include "llvm/IR/Attributes.h"
73#include "llvm/IR/BasicBlock.h"
74#include "llvm/IR/CFG.h"
75#include "llvm/IR/Comdat.h"
76#include "llvm/IR/Constant.h"
77#include "llvm/IR/Constants.h"
78#include "llvm/IR/CycleInfo.h"
79#include "llvm/IR/DiagnosticInfo.h"
80#include "llvm/IR/EHPersonalities.h"
81#include "llvm/IR/Function.h"
82#include "llvm/IR/GlobalAlias.h"
83#include "llvm/IR/GlobalValue.h"
84#include "llvm/IR/GlobalVariable.h"
85#include "llvm/IR/IRBuilder.h"
86#include "llvm/IR/InstVisitor.h"
87#include "llvm/IR/InstrTypes.h"
88#include "llvm/IR/Instruction.h"
89#include "llvm/IR/Instructions.h"
90#include "llvm/IR/IntrinsicInst.h"
91#include "llvm/IR/Intrinsics.h"
92#include "llvm/IR/LLVMContext.h"
93#include "llvm/IR/MDBuilder.h"
94#include "llvm/IR/Module.h"
95#include "llvm/IR/PassManager.h"
96#include "llvm/IR/ProfDataUtils.h"
97#include "llvm/IR/ProfileSummary.h"
98#include "llvm/IR/Type.h"
99#include "llvm/IR/Value.h"
100#include "llvm/ProfileData/InstrProf.h"
101#include "llvm/ProfileData/InstrProfReader.h"
102#include "llvm/Support/BranchProbability.h"
103#include "llvm/Support/CRC.h"
104#include "llvm/Support/Casting.h"
105#include "llvm/Support/CommandLine.h"
106#include "llvm/Support/Compiler.h"
107#include "llvm/Support/DOTGraphTraits.h"
108#include "llvm/Support/Debug.h"
109#include "llvm/Support/Error.h"
110#include "llvm/Support/ErrorHandling.h"
111#include "llvm/Support/GraphWriter.h"
112#include "llvm/Support/VirtualFileSystem.h"
113#include "llvm/Support/raw_ostream.h"
114#include "llvm/TargetParser/Triple.h"
115#include "llvm/Transforms/Instrumentation/BlockCoverageInference.h"
116#include "llvm/Transforms/Instrumentation/CFGMST.h"
117#include "llvm/Transforms/Utils/BasicBlockUtils.h"
118#include "llvm/Transforms/Utils/Instrumentation.h"
119#include "llvm/Transforms/Utils/MisExpect.h"
120#include "llvm/Transforms/Utils/ModuleUtils.h"
121#include <algorithm>
122#include <cassert>
123#include <cstdint>
124#include <memory>
125#include <numeric>
126#include <optional>
127#include <stack>
128#include <string>
129#include <unordered_map>
130#include <utility>
131#include <vector>
132
133using namespace llvm;
134using VPCandidateInfo = ValueProfileCollector::CandidateInfo;
135
136#define DEBUG_TYPE "pgo-instrumentation"
137
138STATISTIC(NumOfPGOInstrument, "Number of edges instrumented.");
139STATISTIC(NumOfPGOSelectInsts, "Number of select instruction instrumented.");
140STATISTIC(NumOfPGOMemIntrinsics, "Number of mem intrinsics instrumented.");
141STATISTIC(NumOfPGOEdge, "Number of edges.");
142STATISTIC(NumOfPGOBB, "Number of basic-blocks.");
143STATISTIC(NumOfPGOSplit, "Number of critical edge splits.");
144STATISTIC(NumOfPGOFunc, "Number of functions having valid profile counts.");
145STATISTIC(NumOfPGOMismatch, "Number of functions having mismatch profile.");
146STATISTIC(NumOfPGOMissing, "Number of functions without profile.");
147STATISTIC(NumOfPGOICall, "Number of indirect call value instrumentations.");
148STATISTIC(NumOfCSPGOInstrument, "Number of edges instrumented in CSPGO.");
149STATISTIC(NumOfCSPGOSelectInsts,
150 "Number of select instruction instrumented in CSPGO.");
151STATISTIC(NumOfCSPGOMemIntrinsics,
152 "Number of mem intrinsics instrumented in CSPGO.");
153STATISTIC(NumOfCSPGOEdge, "Number of edges in CSPGO.");
154STATISTIC(NumOfCSPGOBB, "Number of basic-blocks in CSPGO.");
155STATISTIC(NumOfCSPGOSplit, "Number of critical edge splits in CSPGO.");
156STATISTIC(NumOfCSPGOFunc,
157 "Number of functions having valid profile counts in CSPGO.");
158STATISTIC(NumOfCSPGOMismatch,
159 "Number of functions having mismatch profile in CSPGO.");
160STATISTIC(NumOfCSPGOMissing, "Number of functions without profile in CSPGO.");
161STATISTIC(NumCoveredBlocks, "Number of basic blocks that were executed");
162
163namespace llvm {
164
165// Command line option to enable/disable the warning about a hash mismatch in
166// the profile data.
167cl::opt<bool>
168 NoPGOWarnMismatch("no-pgo-warn-mismatch", cl::init(Val: false), cl::Hidden,
169 cl::desc("Use this option to turn off/on "
170 "warnings about profile cfg mismatch."));
171
172// Command line option to enable vtable value profiling. Defined in
173// ProfileData/InstrProf.cpp: -enable-vtable-value-profiling=
174extern cl::opt<bool> EnableVTableValueProfiling;
175extern cl::opt<bool> EnableVTableProfileUse;
176} // namespace llvm
177
178bool llvm::isPGOInstrumentColdFunctionOnly(
179 const cl::LibraryOptionsContext &LibraryOptions) {
180 return LibraryOptions.get<InstrumentationOptions>()
181 .pgo_instrument_cold_function_only;
182}
183
184namespace {
185class FunctionInstrumenter final {
186 const InstrumentationOptions &Opts;
187 Module &M;
188 Function &F;
189 TargetLibraryInfo &TLI;
190 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers;
191 BranchProbabilityInfo *const BPI;
192 BlockFrequencyInfo *const BFI;
193 LoopInfo *const LI;
194
195 const PGOInstrumentationType InstrumentationType;
196
197 // FIXME(mtrofin): re-enable this for ctx profiling, for non-indirect calls.
198 // Ctx profiling implicitly captures indirect call cases, but not other
199 // values. Supporting other values is relatively straight-forward - just
200 // another counter range within the context.
201 bool isValueProfilingDisabled() const {
202 // Value profiling is disabled for GPU targets because the device-side
203 // profiling runtime does not yet implement
204 // __llvm_profile_instrument_target. The existing compiler-rt implementation
205 // uses a linked-list with locks and eviction policy that is not efficient
206 // for massively parallel GPU execution. A GPU-optimized implementation is
207 // left as future work.
208 return Opts.disable_vp ||
209 InstrumentationType == PGOInstrumentationType::CTXPROF ||
210 isGPUProfTarget(M);
211 }
212
213 bool shouldInstrumentEntryBB() const {
214 return valueOr(X: Opts.pgo_instrument_entry, Default: false) ||
215 InstrumentationType == PGOInstrumentationType::CTXPROF;
216 }
217
218 bool shouldInstrumentLoopEntries() const {
219 return valueOr(X: Opts.pgo_instrument_loop_entries, Default: false);
220 }
221
222public:
223 FunctionInstrumenter(
224 const InstrumentationOptions &Opts, Module &M, Function &F,
225 TargetLibraryInfo &TLI,
226 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers,
227 BranchProbabilityInfo *BPI = nullptr, BlockFrequencyInfo *BFI = nullptr,
228 LoopInfo *LI = nullptr,
229 PGOInstrumentationType InstrumentationType = PGOInstrumentationType::FDO)
230 : Opts(Opts), M(M), F(F), TLI(TLI), ComdatMembers(ComdatMembers),
231 BPI(BPI), BFI(BFI), LI(LI), InstrumentationType(InstrumentationType) {}
232
233 void instrument();
234};
235} // namespace
236
237// Return a string describing the branch condition that can be
238// used in static branch probability heuristics:
239static std::string getBranchCondString(Instruction *TI) {
240 CondBrInst *BI = dyn_cast<CondBrInst>(Val: TI);
241 if (!BI)
242 return std::string();
243
244 Value *Cond = BI->getCondition();
245 ICmpInst *CI = dyn_cast<ICmpInst>(Val: Cond);
246 if (!CI)
247 return std::string();
248
249 std::string result;
250 raw_string_ostream OS(result);
251 OS << CI->getPredicate() << "_";
252 CI->getOperand(i_nocapture: 0)->getType()->print(O&: OS, IsForDebug: true);
253
254 Value *RHS = CI->getOperand(i_nocapture: 1);
255 ConstantInt *CV = dyn_cast<ConstantInt>(Val: RHS);
256 if (CV) {
257 if (CV->isZero())
258 OS << "_Zero";
259 else if (CV->isOne())
260 OS << "_One";
261 else if (CV->isMinusOne())
262 OS << "_MinusOne";
263 else
264 OS << "_Const";
265 }
266 return result;
267}
268
269static const char *ValueProfKindDescr[] = {
270#define VALUE_PROF_KIND(Enumerator, Value, Descr) Descr,
271#include "llvm/ProfileData/InstrProfData.inc"
272};
273
274// Create a COMDAT variable INSTR_PROF_RAW_VERSION_VAR to make the runtime
275// aware this is an ir_level profile so it can set the version flag.
276static GlobalVariable *
277createIRLevelProfileFlagVar(const InstrumentationOptions &Opts, Module &M,
278 PGOInstrumentationType InstrumentationType) {
279 const StringRef VarName(INSTR_PROF_QUOTE(INSTR_PROF_RAW_VERSION_VAR));
280 Type *IntTy64 = Type::getInt64Ty(C&: M.getContext());
281 uint64_t ProfileVersion = (INSTR_PROF_RAW_VERSION | VARIANT_MASK_IR_PROF);
282 if (InstrumentationType == PGOInstrumentationType::CSFDO)
283 ProfileVersion |= VARIANT_MASK_CSIR_PROF;
284 if (valueOr(X: Opts.pgo_instrument_entry, Default: false) ||
285 InstrumentationType == PGOInstrumentationType::CTXPROF)
286 ProfileVersion |= VARIANT_MASK_INSTR_ENTRY;
287 if (valueOr(X: Opts.pgo_instrument_loop_entries, Default: false))
288 ProfileVersion |= VARIANT_MASK_INSTR_LOOP_ENTRIES;
289 if (Opts.profile_correlate == ProfCorrelatorKind::DebugInfo)
290 ProfileVersion |= VARIANT_MASK_DBG_CORRELATE;
291 if (Opts.pgo_function_entry_coverage)
292 ProfileVersion |=
293 VARIANT_MASK_BYTE_COVERAGE | VARIANT_MASK_FUNCTION_ENTRY_ONLY;
294 if (Opts.pgo_block_coverage)
295 ProfileVersion |= VARIANT_MASK_BYTE_COVERAGE;
296 if (Opts.pgo_temporal_instrumentation)
297 ProfileVersion |= VARIANT_MASK_TEMPORAL_PROF;
298 auto IRLevelVersionVariable = new GlobalVariable(
299 M, IntTy64, true, GlobalValue::WeakAnyLinkage,
300 Constant::getIntegerValue(Ty: IntTy64, V: APInt(64, ProfileVersion)), VarName);
301 Triple TT(M.getTargetTriple());
302 IRLevelVersionVariable->setVisibility(TT.isGPU()
303 ? GlobalValue::ProtectedVisibility
304 : GlobalValue::HiddenVisibility);
305 if (TT.supportsCOMDAT()) {
306 IRLevelVersionVariable->setLinkage(GlobalValue::ExternalLinkage);
307 IRLevelVersionVariable->setComdat(M.getOrInsertComdat(Name: VarName));
308 }
309 return IRLevelVersionVariable;
310}
311
312namespace {
313
314/// The select instruction visitor plays three roles specified
315/// by the mode. In \c VM_counting mode, it simply counts the number of
316/// select instructions. In \c VM_instrument mode, it inserts code to count
317/// the number times TrueValue of select is taken. In \c VM_annotate mode,
318/// it reads the profile data and annotate the select instruction with metadata.
319enum VisitMode { VM_counting, VM_instrument, VM_annotate };
320class PGOUseFunc;
321
322/// Instruction Visitor class to visit select instructions.
323struct SelectInstVisitor : public InstVisitor<SelectInstVisitor> {
324 const InstrumentationOptions &Opts;
325 Function &F;
326 unsigned NSIs = 0; // Number of select instructions instrumented.
327 VisitMode Mode = VM_counting; // Visiting mode.
328 unsigned *CurCtrIdx = nullptr; // Pointer to current counter index.
329 unsigned TotalNumCtrs = 0; // Total number of counters
330 GlobalValue *FuncNameVar = nullptr;
331 uint64_t FuncHash = 0;
332 PGOUseFunc *UseFunc = nullptr;
333 bool HasSingleByteCoverage;
334
335 SelectInstVisitor(const InstrumentationOptions &Opts, Function &Func,
336 bool HasSingleByteCoverage)
337 : Opts(Opts), F(Func), HasSingleByteCoverage(HasSingleByteCoverage) {}
338
339 void countSelects() {
340 NSIs = 0;
341 Mode = VM_counting;
342 visit(F);
343 }
344
345 // Visit the IR stream and instrument all select instructions. \p
346 // Ind is a pointer to the counter index variable; \p TotalNC
347 // is the total number of counters; \p FNV is the pointer to the
348 // PGO function name var; \p FHash is the function hash.
349 void instrumentSelects(unsigned *Ind, unsigned TotalNC, GlobalValue *FNV,
350 uint64_t FHash) {
351 Mode = VM_instrument;
352 CurCtrIdx = Ind;
353 TotalNumCtrs = TotalNC;
354 FuncHash = FHash;
355 FuncNameVar = FNV;
356 visit(F);
357 }
358
359 // Visit the IR stream and annotate all select instructions.
360 void annotateSelects(PGOUseFunc *UF, unsigned *Ind) {
361 Mode = VM_annotate;
362 UseFunc = UF;
363 CurCtrIdx = Ind;
364 visit(F);
365 }
366
367 void instrumentOneSelectInst(SelectInst &SI);
368 void annotateOneSelectInst(SelectInst &SI);
369
370 // Visit \p SI instruction and perform tasks according to visit mode.
371 void visitSelectInst(SelectInst &SI);
372
373 // Return the number of select instructions. This needs be called after
374 // countSelects().
375 unsigned getNumOfSelectInsts() const { return NSIs; }
376};
377
378/// This class implements the CFG edges for the Minimum Spanning Tree (MST)
379/// based instrumentation.
380/// Note that the CFG can be a multi-graph. So there might be multiple edges
381/// with the same SrcBB and DestBB.
382struct PGOEdge {
383 BasicBlock *SrcBB;
384 BasicBlock *DestBB;
385 uint64_t Weight;
386 bool InMST = false;
387 bool Removed = false;
388 bool IsCritical = false;
389
390 PGOEdge(BasicBlock *Src, BasicBlock *Dest, uint64_t W = 1)
391 : SrcBB(Src), DestBB(Dest), Weight(W) {}
392
393 /// Return the information string of an edge.
394 std::string infoString() const {
395 return (Twine(Removed ? "-" : " ") + (InMST ? " " : "*") +
396 (IsCritical ? "c" : " ") + " W=" + Twine(Weight))
397 .str();
398 }
399};
400
401/// This class stores the auxiliary information for each BB in the MST.
402struct PGOBBInfo {
403 PGOBBInfo *Group;
404 uint32_t Index;
405 uint32_t Rank = 0;
406
407 PGOBBInfo(unsigned IX) : Group(this), Index(IX) {}
408
409 /// Return the information string of this object.
410 std::string infoString() const {
411 return (Twine("Index=") + Twine(Index)).str();
412 }
413};
414
415// This class implements the CFG edges. Note the CFG can be a multi-graph.
416template <class Edge, class BBInfo> class FuncPGOInstrumentation {
417private:
418 const InstrumentationOptions &Opts;
419 Function &F;
420
421 // Is this is context-sensitive instrumentation.
422 bool IsCS;
423
424 // A map that stores the Comdat group in function F.
425 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers;
426
427 ValueProfileCollector VPC;
428
429 void computeCFGHash();
430 void renameComdatFunction();
431
432public:
433 const TargetLibraryInfo &TLI;
434 std::vector<std::vector<VPCandidateInfo>> ValueSites;
435 SelectInstVisitor SIVisitor;
436 std::string FuncName;
437 std::string DeprecatedFuncName;
438 GlobalVariable *FuncNameVar;
439
440 // CFG hash value for this function.
441 uint64_t FunctionHash = 0;
442
443 // The Minimum Spanning Tree of function CFG.
444 CFGMST<Edge, BBInfo> MST;
445
446 const std::optional<BlockCoverageInference> BCI;
447
448 static std::optional<BlockCoverageInference>
449 constructBCI(Function &Func, bool HasSingleByteCoverage,
450 bool InstrumentFuncEntry) {
451 if (HasSingleByteCoverage)
452 return BlockCoverageInference(Func, InstrumentFuncEntry);
453 return {};
454 }
455
456 // Collect all the BBs that will be instrumented, and store them in
457 // InstrumentBBs.
458 void getInstrumentBBs(std::vector<BasicBlock *> &InstrumentBBs);
459
460 // Give an edge, find the BB that will be instrumented.
461 // Return nullptr if there is no BB to be instrumented.
462 BasicBlock *getInstrBB(Edge *E);
463
464 // Return the auxiliary BB information.
465 BBInfo &getBBInfo(const BasicBlock *BB) const { return MST.getBBInfo(BB); }
466
467 // Return the auxiliary BB information if available.
468 BBInfo *findBBInfo(const BasicBlock *BB) const { return MST.findBBInfo(BB); }
469
470 // Dump edges and BB information.
471 void dumpInfo(StringRef Str = "") const {
472 MST.dumpEdges(dbgs(), Twine("Dump Function ") + FuncName +
473 " Hash: " + Twine(FunctionHash) + "\t" + Str);
474 }
475
476 FuncPGOInstrumentation(
477 const InstrumentationOptions &Opts, Function &Func,
478 TargetLibraryInfo &TLI,
479 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers,
480 bool CreateGlobalVar = false, BranchProbabilityInfo *BPI = nullptr,
481 BlockFrequencyInfo *BFI = nullptr, LoopInfo *LI = nullptr,
482 bool IsCS = false, bool InstrumentFuncEntry = true,
483 bool InstrumentLoopEntries = false, bool HasSingleByteCoverage = false)
484 : Opts(Opts), F(Func), IsCS(IsCS), ComdatMembers(ComdatMembers),
485 VPC(Func, TLI), TLI(TLI), ValueSites(IPVK_Last + 1),
486 SIVisitor(Opts, Func, HasSingleByteCoverage),
487 MST(F, InstrumentFuncEntry, InstrumentLoopEntries, BPI, BFI, LI),
488 BCI(constructBCI(Func, HasSingleByteCoverage, InstrumentFuncEntry)) {
489 if (BCI && Opts.pgo_view_block_coverage_graph)
490 BCI->viewBlockCoverageGraph();
491 // This should be done before CFG hash computation.
492 SIVisitor.countSelects();
493 ValueSites[IPVK_MemOPSize] = VPC.get(Kind: IPVK_MemOPSize);
494 if (!IsCS) {
495 NumOfPGOSelectInsts += SIVisitor.getNumOfSelectInsts();
496 NumOfPGOMemIntrinsics += ValueSites[IPVK_MemOPSize].size();
497 NumOfPGOBB += MST.bbInfoSize();
498 ValueSites[IPVK_IndirectCallTarget] = VPC.get(Kind: IPVK_IndirectCallTarget);
499 if (EnableVTableValueProfiling)
500 ValueSites[IPVK_VTableTarget] = VPC.get(Kind: IPVK_VTableTarget);
501 } else {
502 NumOfCSPGOSelectInsts += SIVisitor.getNumOfSelectInsts();
503 NumOfCSPGOMemIntrinsics += ValueSites[IPVK_MemOPSize].size();
504 NumOfCSPGOBB += MST.bbInfoSize();
505 }
506
507 FuncName = getIRPGOObjectName(GO: F);
508 DeprecatedFuncName = getPGOFuncName(F);
509 computeCFGHash();
510 if (!ComdatMembers.empty())
511 renameComdatFunction();
512 LLVM_DEBUG(dumpInfo("after CFGMST"));
513
514 for (const auto &E : MST.allEdges()) {
515 if (E->Removed)
516 continue;
517 IsCS ? NumOfCSPGOEdge++ : NumOfPGOEdge++;
518 if (!E->InMST)
519 IsCS ? NumOfCSPGOInstrument++ : NumOfPGOInstrument++;
520 }
521
522 if (CreateGlobalVar)
523 FuncNameVar = createPGOFuncNameVar(F, PGOFuncName: FuncName);
524 }
525};
526
527} // end anonymous namespace
528
529// Compute Hash value for the CFG: the lower 32 bits are CRC32 of the index
530// value of each BB in the CFG. The higher 32 bits are the CRC32 of the numbers
531// of selects, indirect calls, mem ops and edges.
532template <class Edge, class BBInfo>
533void FuncPGOInstrumentation<Edge, BBInfo>::computeCFGHash() {
534 std::vector<uint8_t> Indexes;
535 JamCRC JC;
536 for (auto &BB : F) {
537 for (BasicBlock *Succ : successors(BB: &BB)) {
538 auto BI = findBBInfo(BB: Succ);
539 if (BI == nullptr)
540 continue;
541 uint32_t Index = BI->Index;
542 for (int J = 0; J < 4; J++)
543 Indexes.push_back(x: (uint8_t)(Index >> (J * 8)));
544 }
545 }
546 JC.update(Data: Indexes);
547
548 JamCRC JCH;
549 // The higher 32 bits.
550 auto updateJCH = [&JCH](uint64_t Num) {
551 uint8_t Data[8];
552 support::endian::write64le(P: Data, V: Num);
553 JCH.update(Data);
554 };
555 updateJCH((uint64_t)SIVisitor.getNumOfSelectInsts());
556 updateJCH((uint64_t)ValueSites[IPVK_IndirectCallTarget].size());
557 updateJCH((uint64_t)ValueSites[IPVK_MemOPSize].size());
558 if (BCI) {
559 updateJCH(BCI->getInstrumentedBlocksHash());
560 } else {
561 updateJCH((uint64_t)MST.numEdges());
562 }
563
564 // Hash format for context sensitive profile. Reserve 4 bits for other
565 // information.
566 FunctionHash = (((uint64_t)JCH.getCRC()) << 28) + JC.getCRC();
567
568 // Reserve bit 60-63 for other information purpose.
569 FunctionHash &= NamedInstrProfRecord::FUNC_HASH_MASK;
570 if (IsCS)
571 NamedInstrProfRecord::setCSFlagInHash(FunctionHash);
572 LLVM_DEBUG(dbgs() << "Function Hash Computation for " << F.getName() << ":\n"
573 << " CRC = " << JC.getCRC()
574 << ", Selects = " << SIVisitor.getNumOfSelectInsts()
575 << ", Edges = " << MST.numEdges() << ", ICSites = "
576 << ValueSites[IPVK_IndirectCallTarget].size()
577 << ", Memops = " << ValueSites[IPVK_MemOPSize].size()
578 << ", High32 CRC = " << JCH.getCRC()
579 << ", Hash = " << FunctionHash << "\n";);
580
581 if (Opts.pgo_trace_func_hash != "-" &&
582 F.getName().contains(Other: Opts.pgo_trace_func_hash))
583 dbgs() << "Funcname=" << F.getName() << ", Hash=" << FunctionHash
584 << " in building " << F.getParent()->getSourceFileName() << "\n";
585}
586
587// Check if we can safely rename this Comdat function.
588static bool canRenameComdat(
589 const InstrumentationOptions &Opts, Function &F,
590 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers) {
591 if (!Opts.do_comdat_renaming || !canRenameComdatFunc(F, CheckAddressTaken: true))
592 return false;
593
594 // FIXME: Current only handle those Comdat groups that only containing one
595 // function.
596 // (1) For a Comdat group containing multiple functions, we need to have a
597 // unique postfix based on the hashes for each function. There is a
598 // non-trivial code refactoring to do this efficiently.
599 // (2) Variables can not be renamed, so we can not rename Comdat function in a
600 // group including global vars.
601 Comdat *C = F.getComdat();
602 for (auto &&CM : make_range(p: ComdatMembers.equal_range(x: C))) {
603 assert(!isa<GlobalAlias>(CM.second));
604 Function *FM = dyn_cast<Function>(Val: CM.second);
605 if (FM != &F)
606 return false;
607 }
608 return true;
609}
610
611// Append the CFGHash to the Comdat function name.
612template <class Edge, class BBInfo>
613void FuncPGOInstrumentation<Edge, BBInfo>::renameComdatFunction() {
614 if (!canRenameComdat(Opts, F, ComdatMembers))
615 return;
616 std::string OrigName = F.getName().str();
617 std::string NewFuncName =
618 Twine(F.getName() + "." + Twine(FunctionHash)).str();
619 F.setName(Twine(NewFuncName));
620 GlobalAlias::create(Linkage: GlobalValue::WeakAnyLinkage, Name: OrigName, Aliasee: &F);
621 FuncName = Twine(FuncName + "." + Twine(FunctionHash)).str();
622 Comdat *NewComdat;
623 Module *M = F.getParent();
624 // For AvailableExternallyLinkage functions, change the linkage to
625 // LinkOnceODR and put them into comdat. This is because after renaming, there
626 // is no backup external copy available for the function.
627 if (!F.hasComdat()) {
628 assert(F.getLinkage() == GlobalValue::AvailableExternallyLinkage);
629 NewComdat = M->getOrInsertComdat(Name: StringRef(NewFuncName));
630 F.setLinkage(GlobalValue::LinkOnceODRLinkage);
631 F.setComdat(NewComdat);
632 return;
633 }
634
635 // This function belongs to a single function Comdat group.
636 Comdat *OrigComdat = F.getComdat();
637 std::string NewComdatName =
638 Twine(OrigComdat->getName() + "." + Twine(FunctionHash)).str();
639 NewComdat = M->getOrInsertComdat(Name: StringRef(NewComdatName));
640 NewComdat->setSelectionKind(OrigComdat->getSelectionKind());
641
642 for (auto &&CM : make_range(p: ComdatMembers.equal_range(x: OrigComdat))) {
643 // Must be a function.
644 cast<Function>(Val: CM.second)->setComdat(NewComdat);
645 }
646}
647
648/// Collect all the BBs that will be instruments and add them to
649/// `InstrumentBBs`.
650template <class Edge, class BBInfo>
651void FuncPGOInstrumentation<Edge, BBInfo>::getInstrumentBBs(
652 std::vector<BasicBlock *> &InstrumentBBs) {
653 if (BCI) {
654 for (auto &BB : F)
655 if (BCI->shouldInstrumentBlock(BB))
656 InstrumentBBs.push_back(x: &BB);
657 return;
658 }
659
660 // Use a worklist as we will update the vector during the iteration.
661 std::vector<Edge *> EdgeList;
662 EdgeList.reserve(MST.numEdges());
663 for (const auto &E : MST.allEdges())
664 EdgeList.push_back(E.get());
665
666 for (auto &E : EdgeList) {
667 BasicBlock *InstrBB = getInstrBB(E);
668 if (InstrBB)
669 InstrumentBBs.push_back(x: InstrBB);
670 }
671}
672
673// Given a CFG E to be instrumented, find which BB to place the instrumented
674// code. The function will split the critical edge if necessary.
675template <class Edge, class BBInfo>
676BasicBlock *FuncPGOInstrumentation<Edge, BBInfo>::getInstrBB(Edge *E) {
677 if (E->InMST || E->Removed)
678 return nullptr;
679
680 BasicBlock *SrcBB = E->SrcBB;
681 BasicBlock *DestBB = E->DestBB;
682 // For a fake edge, instrument the real BB.
683 if (SrcBB == nullptr)
684 return DestBB;
685 if (DestBB == nullptr)
686 return SrcBB;
687
688 auto canInstrument = [](BasicBlock *BB) -> BasicBlock * {
689 // There are basic blocks (such as catchswitch) cannot be instrumented.
690 // If the returned first insertion point is the end of BB, skip this BB.
691 if (BB->getFirstNonPHIOrAlloca() == BB->end())
692 return nullptr;
693 return BB;
694 };
695
696 // Instrument the SrcBB if it has a single successor,
697 // otherwise, the DestBB if this is not a critical edge.
698 Instruction *TI = SrcBB->getTerminator();
699 if (TI->getNumSuccessors() <= 1)
700 return canInstrument(SrcBB);
701 if (!E->IsCritical)
702 return canInstrument(DestBB);
703
704 // Some IndirectBr critical edges cannot be split by the previous
705 // SplitIndirectBrCriticalEdges call. Bail out.
706 unsigned SuccNum = GetSuccessorNumber(BB: SrcBB, Succ: DestBB);
707 BasicBlock *InstrBB =
708 isa<IndirectBrInst>(Val: TI) ? nullptr : SplitCriticalEdge(TI, SuccNum);
709 if (!InstrBB) {
710 LLVM_DEBUG(
711 dbgs() << "Fail to split critical edge: not instrument this edge.\n");
712 return nullptr;
713 }
714 // For a critical edge, we have to split. Instrument the newly
715 // created BB.
716 IsCS ? NumOfCSPGOSplit++ : NumOfPGOSplit++;
717 LLVM_DEBUG(dbgs() << "Split critical edge: " << getBBInfo(SrcBB).Index
718 << " --> " << getBBInfo(DestBB).Index << "\n");
719 // Need to add two new edges. First one: Add new edge of SrcBB->InstrBB.
720 MST.addEdge(SrcBB, InstrBB, 0);
721 // Second one: Add new edge of InstrBB->DestBB.
722 Edge &NewEdge1 = MST.addEdge(InstrBB, DestBB, 0);
723 NewEdge1.InMST = true;
724 E->Removed = true;
725
726 return canInstrument(InstrBB);
727}
728
729// When generating value profiling calls on Windows routines that make use of
730// handler funclets for exception processing an operand bundle needs to attached
731// to the called function. This routine will set \p OpBundles to contain the
732// funclet information, if any is needed, that should be placed on the generated
733// value profiling call for the value profile candidate call.
734static void
735populateEHOperandBundle(VPCandidateInfo &Cand,
736 DenseMap<BasicBlock *, ColorVector> &BlockColors,
737 SmallVectorImpl<OperandBundleDef> &OpBundles) {
738 auto *OrigCall = dyn_cast<CallBase>(Val: Cand.AnnotatedInst);
739 if (!OrigCall)
740 return;
741
742 if (!isa<IntrinsicInst>(Val: OrigCall)) {
743 // The instrumentation call should belong to the same funclet as a
744 // non-intrinsic call, so just copy the operand bundle, if any exists.
745 std::optional<OperandBundleUse> ParentFunclet =
746 OrigCall->getOperandBundle(ID: LLVMContext::OB_funclet);
747 if (ParentFunclet)
748 OpBundles.emplace_back(Args: OperandBundleDef(*ParentFunclet));
749 } else {
750 // Intrinsics or other instructions do not get funclet information from the
751 // front-end. Need to use the BlockColors that was computed by the routine
752 // colorEHFunclets to determine whether a funclet is needed.
753 if (!BlockColors.empty()) {
754 const ColorVector &CV = BlockColors.find(Val: OrigCall->getParent())->second;
755 assert(CV.size() == 1 && "non-unique color for block!");
756 BasicBlock::iterator EHPadIt = CV.front()->getFirstNonPHIIt();
757 if (EHPadIt->isEHPad())
758 OpBundles.emplace_back(Args: "funclet", Args: &*EHPadIt);
759 }
760 }
761}
762
763// Visit all edge and instrument the edges not in MST, and do value profiling.
764// Critical edges will be split.
765void FunctionInstrumenter::instrument() {
766 if (!Opts.pgo_block_coverage) {
767 // Split indirectbr critical edges here before computing the MST rather than
768 // later in getInstrBB() to avoid invalidating it.
769 SplitIndirectBrCriticalEdges(F, /*IgnoreBlocksWithoutPHI=*/false, BPI, BFI);
770 }
771
772 const bool IsCtxProf = InstrumentationType == PGOInstrumentationType::CTXPROF;
773 FuncPGOInstrumentation<PGOEdge, PGOBBInfo> FuncInfo(
774 Opts, F, TLI, ComdatMembers, /*CreateGlobalVar=*/!IsCtxProf, BPI, BFI, LI,
775 InstrumentationType == PGOInstrumentationType::CSFDO,
776 shouldInstrumentEntryBB(), shouldInstrumentLoopEntries(),
777 Opts.pgo_block_coverage);
778
779 auto *const Name = IsCtxProf ? cast<GlobalValue>(Val: &F) : FuncInfo.FuncNameVar;
780 auto *const CFGHash =
781 ConstantInt::get(Ty: Type::getInt64Ty(C&: M.getContext()), V: FuncInfo.FunctionHash);
782 // Make sure that pointer to global is passed in with zero addrspace
783 // This is relevant during GPU profiling
784 auto *NormalizedNamePtr = ConstantExpr::getPointerBitCastOrAddrSpaceCast(
785 C: Name, Ty: PointerType::get(C&: M.getContext(), AddressSpace: 0));
786 if (Opts.pgo_function_entry_coverage) {
787 auto &EntryBB = F.getEntryBlock();
788 IRBuilder<> Builder(EntryBB.getFirstNonPHIOrAlloca());
789 // llvm.instrprof.cover(i8* <name>, i64 <hash>, i32 <num-counters>,
790 // i32 <index>)
791 Builder.CreateIntrinsic(
792 ID: Intrinsic::instrprof_cover,
793 Args: {NormalizedNamePtr, CFGHash, Builder.getInt32(C: 1), Builder.getInt32(C: 0)});
794 return;
795 }
796
797 std::vector<BasicBlock *> InstrumentBBs;
798 FuncInfo.getInstrumentBBs(InstrumentBBs);
799 unsigned NumCounters =
800 InstrumentBBs.size() + FuncInfo.SIVisitor.getNumOfSelectInsts();
801
802 if (IsCtxProf) {
803 StringSet<> SkipCSInstr(llvm::from_range,
804 Opts.ctx_prof_skip_callsite_instr);
805
806 auto *CSIntrinsic =
807 Intrinsic::getOrInsertDeclaration(M: &M, id: Intrinsic::instrprof_callsite);
808 // We want to count the instrumentable callsites, then instrument them. This
809 // is because the llvm.instrprof.callsite intrinsic has an argument (like
810 // the other instrprof intrinsics) capturing the total number of
811 // instrumented objects (counters, or callsites, in this case). In this
812 // case, we want that value so we can readily pass it to the compiler-rt
813 // APIs that may have to allocate memory based on the nr of callsites.
814 // The traversal logic is the same for both counting and instrumentation,
815 // just needs to be done in succession.
816 auto Visit = [&](llvm::function_ref<void(CallBase * CB)> Visitor) {
817 for (auto &BB : F)
818 for (auto &Instr : BB)
819 if (auto *CS = dyn_cast<CallBase>(Val: &Instr)) {
820 if (!InstrProfCallsite::canInstrumentCallsite(CB: *CS))
821 continue;
822 if (CS->getCalledFunction() &&
823 SkipCSInstr.contains(key: CS->getCalledFunction()->getName()))
824 continue;
825 Visitor(CS);
826 }
827 };
828 // First, count callsites.
829 uint32_t TotalNumCallsites = 0;
830 Visit([&TotalNumCallsites](auto *) { ++TotalNumCallsites; });
831
832 // Now instrument.
833 uint32_t CallsiteIndex = 0;
834 Visit([&](auto *CB) {
835 IRBuilder<> Builder(CB);
836 Builder.CreateCall(CSIntrinsic,
837 {Name, CFGHash, Builder.getInt32(C: TotalNumCallsites),
838 Builder.getInt32(C: CallsiteIndex++),
839 CB->getCalledOperand()});
840 });
841 }
842
843 uint32_t I = 0;
844 if (Opts.pgo_temporal_instrumentation) {
845 NumCounters += Opts.pgo_block_coverage ? 8 : 1;
846 auto &EntryBB = F.getEntryBlock();
847 IRBuilder<> Builder(EntryBB.getFirstNonPHIOrAlloca());
848 // llvm.instrprof.timestamp(i8* <name>, i64 <hash>, i32 <num-counters>,
849 // i32 <index>)
850 Builder.CreateIntrinsic(ID: Intrinsic::instrprof_timestamp,
851 Args: {NormalizedNamePtr, CFGHash,
852 Builder.getInt32(C: NumCounters),
853 Builder.getInt32(C: I)});
854 I += Opts.pgo_block_coverage ? 8 : 1;
855 }
856
857 for (auto *InstrBB : InstrumentBBs) {
858 IRBuilder<> Builder(InstrBB->getFirstNonPHIOrAlloca());
859 assert(Builder.GetInsertPoint() != InstrBB->end() &&
860 "Cannot get the Instrumentation point");
861 // llvm.instrprof.increment(i8* <name>, i64 <hash>, i32 <num-counters>,
862 // i32 <index>)
863 Builder.CreateIntrinsic(
864 ID: Opts.pgo_block_coverage ? Intrinsic::instrprof_cover
865 : Intrinsic::instrprof_increment,
866 Args: {NormalizedNamePtr, CFGHash, Builder.getInt32(C: NumCounters),
867 Builder.getInt32(C: I++)});
868 }
869
870 // Now instrument select instructions:
871 FuncInfo.SIVisitor.instrumentSelects(Ind: &I, TotalNC: NumCounters, FNV: Name,
872 FHash: FuncInfo.FunctionHash);
873 assert(I == NumCounters);
874
875 if (isValueProfilingDisabled())
876 return;
877
878 NumOfPGOICall += FuncInfo.ValueSites[IPVK_IndirectCallTarget].size();
879
880 // Intrinsic function calls do not have funclet operand bundles needed for
881 // Windows exception handling attached to them. However, if value profiling is
882 // inserted for one of these calls, then a funclet value will need to be set
883 // on the instrumentation call based on the funclet coloring.
884 DenseMap<BasicBlock *, ColorVector> BlockColors;
885 if (F.hasPersonalityFn() &&
886 isScopedEHPersonality(Pers: classifyEHPersonality(Pers: F.getPersonalityFn())))
887 BlockColors = colorEHFunclets(F);
888
889 // For each VP Kind, walk the VP candidates and instrument each one.
890 for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) {
891 unsigned SiteIndex = 0;
892 if (Kind == IPVK_MemOPSize && !Opts.pgo_instr_memop)
893 continue;
894
895 for (VPCandidateInfo Cand : FuncInfo.ValueSites[Kind]) {
896 LLVM_DEBUG(dbgs() << "Instrument one VP " << ValueProfKindDescr[Kind]
897 << " site: CallSite Index = " << SiteIndex << "\n");
898
899 IRBuilder<> Builder(Cand.InsertPt);
900 assert(Builder.GetInsertPoint() != Cand.InsertPt->getParent()->end() &&
901 "Cannot get the Instrumentation point");
902
903 Value *ToProfile = nullptr;
904 if (Cand.V->getType()->isIntegerTy())
905 ToProfile = Builder.CreateZExtOrTrunc(V: Cand.V, DestTy: Builder.getInt64Ty());
906 else if (Cand.V->getType()->isPointerTy())
907 ToProfile = Builder.CreatePtrToInt(V: Cand.V, DestTy: Builder.getInt64Ty());
908 assert(ToProfile && "value profiling Value is of unexpected type");
909
910 auto *NormalizedNamePtr = ConstantExpr::getPointerBitCastOrAddrSpaceCast(
911 C: Name, Ty: PointerType::get(C&: M.getContext(), AddressSpace: 0));
912
913 SmallVector<OperandBundleDef, 1> OpBundles;
914 populateEHOperandBundle(Cand, BlockColors, OpBundles);
915 Builder.CreateCall(
916 Callee: Intrinsic::getOrInsertDeclaration(M: &M,
917 id: Intrinsic::instrprof_value_profile),
918 Args: {NormalizedNamePtr, Builder.getInt64(C: FuncInfo.FunctionHash),
919 ToProfile, Builder.getInt32(C: Kind), Builder.getInt32(C: SiteIndex++)},
920 OpBundles);
921 }
922 } // IPVK_First <= Kind <= IPVK_Last
923}
924
925namespace {
926
927// This class represents a CFG edge in profile use compilation.
928struct PGOUseEdge : public PGOEdge {
929 using PGOEdge::PGOEdge;
930
931 std::optional<uint64_t> Count;
932
933 // Set edge count value
934 void setEdgeCount(uint64_t Value) { Count = Value; }
935
936 // Return the information string for this object.
937 std::string infoString() const {
938 if (!Count)
939 return PGOEdge::infoString();
940 return (Twine(PGOEdge::infoString()) + " Count=" + Twine(*Count)).str();
941 }
942};
943
944using DirectEdges = SmallVector<PGOUseEdge *, 2>;
945
946// This class stores the auxiliary information for each BB.
947struct PGOUseBBInfo : public PGOBBInfo {
948 std::optional<uint64_t> Count;
949 int32_t UnknownCountInEdge = 0;
950 int32_t UnknownCountOutEdge = 0;
951 DirectEdges InEdges;
952 DirectEdges OutEdges;
953
954 PGOUseBBInfo(unsigned IX) : PGOBBInfo(IX) {}
955
956 // Set the profile count value for this BB.
957 void setBBInfoCount(uint64_t Value) { Count = Value; }
958
959 // Return the information string of this object.
960 std::string infoString() const {
961 if (!Count)
962 return PGOBBInfo::infoString();
963 return (Twine(PGOBBInfo::infoString()) + " Count=" + Twine(*Count)).str();
964 }
965
966 // Add an OutEdge and update the edge count.
967 void addOutEdge(PGOUseEdge *E) {
968 OutEdges.push_back(Elt: E);
969 UnknownCountOutEdge++;
970 }
971
972 // Add an InEdge and update the edge count.
973 void addInEdge(PGOUseEdge *E) {
974 InEdges.push_back(Elt: E);
975 UnknownCountInEdge++;
976 }
977};
978
979} // end anonymous namespace
980
981// Sum up the count values for all the edges.
982static uint64_t sumEdgeCount(const ArrayRef<PGOUseEdge *> Edges) {
983 uint64_t Total = 0;
984 for (const auto &E : Edges) {
985 if (E->Removed)
986 continue;
987 if (E->Count)
988 Total += *E->Count;
989 }
990 return Total;
991}
992
993namespace {
994
995class PGOUseFunc {
996public:
997 PGOUseFunc(const InstrumentationOptions &Opts, Function &Func, Module *Modu,
998 TargetLibraryInfo &TLI,
999 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers,
1000 BranchProbabilityInfo *BPI, BlockFrequencyInfo *BFIin,
1001 LoopInfo *LI, ProfileSummaryInfo *PSI, bool IsCS,
1002 bool InstrumentFuncEntry, bool InstrumentLoopEntries,
1003 bool HasSingleByteCoverage)
1004 : Opts(Opts), F(Func), M(Modu), BFI(BFIin), PSI(PSI),
1005 FuncInfo(Opts, Func, TLI, ComdatMembers, false, BPI, BFIin, LI, IsCS,
1006 InstrumentFuncEntry, InstrumentLoopEntries,
1007 HasSingleByteCoverage),
1008 FreqAttr(FFA_Normal), IsCS(IsCS), VPC(Func, TLI) {}
1009
1010 void handleInstrProfError(Error Err, uint64_t MismatchedFuncSum);
1011
1012 /// Get the profile record, assign it to \p ProfileRecord, handle errors if
1013 /// necessary, and assign \p ProgramMaxCount. \returns true if there are no
1014 /// errors.
1015 bool getRecord(IndexedInstrProfReader *PGOReader);
1016
1017 // Read counts for the instrumented BB from profile.
1018 bool readCounters(bool &AllZeros,
1019 InstrProfRecord::CountPseudoKind &PseudoKind);
1020
1021 // Populate the counts for all BBs.
1022 void populateCounters();
1023
1024 // Set block coverage based on profile coverage values.
1025 void populateCoverage();
1026
1027 // Set the branch weights based on the count values.
1028 void setBranchWeights();
1029
1030 // Annotate the value profile call sites for all value kind.
1031 void annotateValueSites();
1032
1033 // Annotate the value profile call sites for one value kind.
1034 void annotateValueSites(uint32_t Kind);
1035
1036 // Annotate the irreducible loop header weights.
1037 void annotateIrrLoopHeaderWeights();
1038
1039 // Annotate per-block uniformity info for offload profiling.
1040 void setBlockUniformityAttribute();
1041
1042 // The hotness of the function from the profile count.
1043 enum FuncFreqAttr { FFA_Normal, FFA_Cold, FFA_Hot };
1044
1045 // Return the function hotness from the profile.
1046 FuncFreqAttr getFuncFreqAttr() const { return FreqAttr; }
1047
1048 // Return the function hash.
1049 uint64_t getFuncHash() const { return FuncInfo.FunctionHash; }
1050
1051 // Return the profile record for this function;
1052 NamedInstrProfRecord &getProfileRecord() { return ProfileRecord; }
1053
1054 // Return the auxiliary BB information.
1055 PGOUseBBInfo &getBBInfo(const BasicBlock *BB) const {
1056 return FuncInfo.getBBInfo(BB);
1057 }
1058
1059 // Return the auxiliary BB information if available.
1060 PGOUseBBInfo *findBBInfo(const BasicBlock *BB) const {
1061 return FuncInfo.findBBInfo(BB);
1062 }
1063
1064 Function &getFunc() const { return F; }
1065
1066 void dumpInfo(StringRef Str = "") const { FuncInfo.dumpInfo(Str); }
1067
1068 uint64_t getProgramMaxCount() const { return ProgramMaxCount; }
1069
1070private:
1071 const InstrumentationOptions &Opts;
1072 Function &F;
1073 Module *M;
1074 BlockFrequencyInfo *BFI;
1075 ProfileSummaryInfo *PSI;
1076
1077 // This member stores the shared information with class PGOGenFunc.
1078 FuncPGOInstrumentation<PGOUseEdge, PGOUseBBInfo> FuncInfo;
1079
1080 // The maximum count value in the profile. This is only used in PGO use
1081 // compilation.
1082 uint64_t ProgramMaxCount;
1083
1084 // Position of counter that remains to be read.
1085 uint32_t CountPosition = 0;
1086
1087 // Total size of the profile count for this function.
1088 uint32_t ProfileCountSize = 0;
1089
1090 // ProfileRecord for this function.
1091 NamedInstrProfRecord ProfileRecord;
1092
1093 // Function hotness info derived from profile.
1094 FuncFreqAttr FreqAttr;
1095
1096 // Is to use the context sensitive profile.
1097 bool IsCS;
1098
1099 ValueProfileCollector VPC;
1100
1101 // Find the Instrumented BB and set the value. Return false on error.
1102 bool setInstrumentedCounts(const std::vector<uint64_t> &CountFromProfile);
1103
1104 // Set the edge counter value for the unknown edge -- there should be only
1105 // one unknown edge.
1106 void setEdgeCount(DirectEdges &Edges, uint64_t Value);
1107
1108 // Set the hot/cold inline hints based on the count values.
1109 // FIXME: This function should be removed once the functionality in
1110 // the inliner is implemented.
1111 void markFunctionAttributes(uint64_t EntryCount, uint64_t MaxCount) {
1112 if (PSI->isHotCount(C: EntryCount))
1113 FreqAttr = FFA_Hot;
1114 else if (PSI->isColdCount(C: MaxCount))
1115 FreqAttr = FFA_Cold;
1116 }
1117};
1118
1119} // end anonymous namespace
1120
1121/// Set up InEdges/OutEdges for all BBs in the MST.
1122static void setupBBInfoEdges(
1123 const FuncPGOInstrumentation<PGOUseEdge, PGOUseBBInfo> &FuncInfo) {
1124 // This is not required when there is block coverage inference.
1125 if (FuncInfo.BCI)
1126 return;
1127 for (const auto &E : FuncInfo.MST.allEdges()) {
1128 if (E->Removed)
1129 continue;
1130 const BasicBlock *SrcBB = E->SrcBB;
1131 const BasicBlock *DestBB = E->DestBB;
1132 PGOUseBBInfo &SrcInfo = FuncInfo.getBBInfo(BB: SrcBB);
1133 PGOUseBBInfo &DestInfo = FuncInfo.getBBInfo(BB: DestBB);
1134 SrcInfo.addOutEdge(E: E.get());
1135 DestInfo.addInEdge(E: E.get());
1136 }
1137}
1138
1139// Visit all the edges and assign the count value for the instrumented
1140// edges and the BB. Return false on error.
1141bool PGOUseFunc::setInstrumentedCounts(
1142 const std::vector<uint64_t> &CountFromProfile) {
1143
1144 std::vector<BasicBlock *> InstrumentBBs;
1145 FuncInfo.getInstrumentBBs(InstrumentBBs);
1146
1147 setupBBInfoEdges(FuncInfo);
1148
1149 unsigned NumInstrumentedBBs = InstrumentBBs.size();
1150 unsigned NumSelects = FuncInfo.SIVisitor.getNumOfSelectInsts();
1151 unsigned NumCounters = NumInstrumentedBBs + NumSelects;
1152 // The number of counters here should match the number of counters
1153 // in profile. Return if they mismatch.
1154 if (NumCounters != CountFromProfile.size()) {
1155 LLVM_DEBUG({
1156 dbgs() << "PGO COUNTER MISMATCH for function " << F.getName() << ":\n";
1157 dbgs() << " Expected counters: " << NumCounters << "\n";
1158 dbgs() << " - From instrumented edges: " << NumInstrumentedBBs << "\n";
1159 for (size_t i = 0; i < InstrumentBBs.size(); ++i) {
1160 dbgs() << " " << i << ": ";
1161 InstrumentBBs[i]->printAsOperand(dbgs(), false);
1162 dbgs() << "\n";
1163 }
1164 dbgs() << " - From select instructions: " << NumSelects << "\n";
1165 dbgs() << " Actual counters from profile: " << CountFromProfile.size()
1166 << "\n";
1167 });
1168 return false;
1169 }
1170 auto *FuncEntry = &*F.begin();
1171
1172 // Set the profile count to the Instrumented BBs.
1173 uint32_t I = 0;
1174 for (BasicBlock *InstrBB : InstrumentBBs) {
1175 uint64_t CountValue = CountFromProfile[I++];
1176 PGOUseBBInfo &Info = getBBInfo(BB: InstrBB);
1177 // If we reach here, we know that we have some nonzero count
1178 // values in this function. The entry count should not be 0.
1179 // Fix it if necessary.
1180 if (InstrBB == FuncEntry && CountValue == 0)
1181 CountValue = 1;
1182 Info.setBBInfoCount(CountValue);
1183 }
1184 ProfileCountSize = CountFromProfile.size();
1185 CountPosition = I;
1186
1187 // Set the edge count and update the count of unknown edges for BBs.
1188 auto setEdgeCount = [this](PGOUseEdge *E, uint64_t Value) -> void {
1189 E->setEdgeCount(Value);
1190 this->getBBInfo(BB: E->SrcBB).UnknownCountOutEdge--;
1191 this->getBBInfo(BB: E->DestBB).UnknownCountInEdge--;
1192 };
1193
1194 // Set the profile count the Instrumented edges. There are BBs that not in
1195 // MST but not instrumented. Need to set the edge count value so that we can
1196 // populate the profile counts later.
1197 for (const auto &E : FuncInfo.MST.allEdges()) {
1198 if (E->Removed || E->InMST)
1199 continue;
1200 const BasicBlock *SrcBB = E->SrcBB;
1201 PGOUseBBInfo &SrcInfo = getBBInfo(BB: SrcBB);
1202
1203 // If only one out-edge, the edge profile count should be the same as BB
1204 // profile count.
1205 if (SrcInfo.Count && SrcInfo.OutEdges.size() == 1)
1206 setEdgeCount(E.get(), *SrcInfo.Count);
1207 else {
1208 const BasicBlock *DestBB = E->DestBB;
1209 PGOUseBBInfo &DestInfo = getBBInfo(BB: DestBB);
1210 // If only one in-edge, the edge profile count should be the same as BB
1211 // profile count.
1212 if (DestInfo.Count && DestInfo.InEdges.size() == 1)
1213 setEdgeCount(E.get(), *DestInfo.Count);
1214 }
1215 if (E->Count)
1216 continue;
1217 // E's count should have been set from profile. If not, this meenas E skips
1218 // the instrumentation. We set the count to 0.
1219 setEdgeCount(E.get(), 0);
1220 }
1221 return true;
1222}
1223
1224// Set the count value for the unknown edge. There should be one and only one
1225// unknown edge in Edges vector.
1226void PGOUseFunc::setEdgeCount(DirectEdges &Edges, uint64_t Value) {
1227 for (auto &E : Edges) {
1228 if (E->Count)
1229 continue;
1230 E->setEdgeCount(Value);
1231
1232 getBBInfo(BB: E->SrcBB).UnknownCountOutEdge--;
1233 getBBInfo(BB: E->DestBB).UnknownCountInEdge--;
1234 return;
1235 }
1236 llvm_unreachable("Cannot find the unknown count edge");
1237}
1238
1239// Emit function metadata indicating PGO profile mismatch.
1240static void annotateFunctionWithHashMismatch(Function &F, LLVMContext &ctx) {
1241 const char MetadataName[] = "instr_prof_hash_mismatch";
1242 SmallVector<Metadata *, 2> Names;
1243 // If this metadata already exists, ignore.
1244 auto *Existing = F.getMetadata(KindID: LLVMContext::MD_annotation);
1245 if (Existing) {
1246 MDTuple *Tuple = cast<MDTuple>(Val: Existing);
1247 for (const auto &N : Tuple->operands()) {
1248 if (N.equalsStr(Str: MetadataName))
1249 return;
1250 Names.push_back(Elt: N.get());
1251 }
1252 }
1253
1254 MDBuilder MDB(ctx);
1255 Names.push_back(Elt: MDB.createString(Str: MetadataName));
1256 MDNode *MD = MDTuple::get(Context&: ctx, MDs: Names);
1257 F.setMetadata(KindID: LLVMContext::MD_annotation, Node: MD);
1258}
1259
1260void PGOUseFunc::handleInstrProfError(Error Err, uint64_t MismatchedFuncSum) {
1261 handleAllErrors(E: std::move(Err), Handlers: [&](const InstrProfError &IPE) {
1262 auto &Ctx = M->getContext();
1263 auto Err = IPE.get();
1264 bool SkipWarning = false;
1265 LLVM_DEBUG(dbgs() << "Error in reading profile for Func "
1266 << FuncInfo.FuncName << ": ");
1267 if (Err == instrprof_error::unknown_function) {
1268 IsCS ? NumOfCSPGOMissing++ : NumOfPGOMissing++;
1269 SkipWarning = !Opts.pgo_warn_missing_function;
1270 LLVM_DEBUG(dbgs() << "unknown function");
1271 } else if (Err == instrprof_error::hash_mismatch ||
1272 Err == instrprof_error::malformed) {
1273 IsCS ? NumOfCSPGOMismatch++ : NumOfPGOMismatch++;
1274 SkipWarning =
1275 NoPGOWarnMismatch ||
1276 (Opts.no_pgo_warn_mismatch_comdat_weak &&
1277 (F.hasComdat() || F.getLinkage() == GlobalValue::WeakAnyLinkage ||
1278 F.getLinkage() == GlobalValue::AvailableExternallyLinkage));
1279 LLVM_DEBUG(dbgs() << "hash mismatch (hash= " << FuncInfo.FunctionHash
1280 << " skip=" << SkipWarning << ")");
1281 // Emit function metadata indicating PGO profile mismatch.
1282 annotateFunctionWithHashMismatch(F, ctx&: M->getContext());
1283 }
1284
1285 LLVM_DEBUG(dbgs() << " IsCS=" << IsCS << "\n");
1286 if (SkipWarning)
1287 return;
1288
1289 std::string Msg =
1290 IPE.message() + std::string(" ") + F.getName().str() +
1291 std::string(" Hash = ") + std::to_string(val: FuncInfo.FunctionHash) +
1292 std::string(" up to ") + std::to_string(val: MismatchedFuncSum) +
1293 std::string(" count discarded");
1294
1295 Ctx.diagnose(
1296 DI: DiagnosticInfoPGOProfile(M->getName().data(), Msg, DS_Warning));
1297 });
1298}
1299
1300bool PGOUseFunc::getRecord(IndexedInstrProfReader *PGOReader) {
1301 uint64_t MismatchedFuncSum = 0;
1302 auto Result = PGOReader->getInstrProfRecord(
1303 FuncName: FuncInfo.FuncName, FuncHash: FuncInfo.FunctionHash, DeprecatedFuncName: FuncInfo.DeprecatedFuncName,
1304 MismatchedFuncSum: &MismatchedFuncSum);
1305 if (Error E = Result.takeError()) {
1306 handleInstrProfError(Err: std::move(E), MismatchedFuncSum);
1307 return false;
1308 }
1309 ProfileRecord = std::move(Result.get());
1310 ProgramMaxCount = PGOReader->getMaximumFunctionCount(UseCS: IsCS);
1311 return true;
1312}
1313
1314// Read the profile from ProfileFileName and assign the value to the
1315// instrumented BB and the edges. Return true if the profile are successfully
1316// read, and false on errors.
1317bool PGOUseFunc::readCounters(bool &AllZeros,
1318 InstrProfRecord::CountPseudoKind &PseudoKind) {
1319 auto &Ctx = M->getContext();
1320 PseudoKind = ProfileRecord.getCountPseudoKind();
1321 if (PseudoKind != InstrProfRecord::NotPseudo) {
1322 return true;
1323 }
1324 std::vector<uint64_t> &CountFromProfile = ProfileRecord.Counts;
1325
1326 IsCS ? NumOfCSPGOFunc++ : NumOfPGOFunc++;
1327 LLVM_DEBUG(dbgs() << CountFromProfile.size() << " counts\n");
1328
1329 uint64_t ValueSum = 0;
1330 for (unsigned I = 0, S = CountFromProfile.size(); I < S; I++) {
1331 LLVM_DEBUG(dbgs() << " " << I << ": " << CountFromProfile[I] << "\n");
1332 ValueSum += CountFromProfile[I];
1333 }
1334 AllZeros = (ValueSum == 0);
1335
1336 LLVM_DEBUG(dbgs() << "SUM = " << ValueSum << "\n");
1337
1338 getBBInfo(BB: nullptr).UnknownCountOutEdge = 2;
1339 getBBInfo(BB: nullptr).UnknownCountInEdge = 2;
1340
1341 if (!setInstrumentedCounts(CountFromProfile)) {
1342 LLVM_DEBUG(
1343 dbgs() << "Inconsistent number of counts, skipping this function");
1344 Ctx.diagnose(DI: DiagnosticInfoPGOProfile(
1345 M->getName().data(),
1346 Twine("Inconsistent number of counts in ") + F.getName().str() +
1347 Twine(": the profile may be stale or there is a function name "
1348 "collision."),
1349 DS_Warning));
1350 return false;
1351 }
1352 return true;
1353}
1354
1355void PGOUseFunc::populateCoverage() {
1356 IsCS ? NumOfCSPGOFunc++ : NumOfPGOFunc++;
1357
1358 ArrayRef<uint64_t> CountsFromProfile = ProfileRecord.Counts;
1359 DenseMap<const BasicBlock *, bool> Coverage;
1360 unsigned Index = 0;
1361 for (auto &BB : F)
1362 if (FuncInfo.BCI->shouldInstrumentBlock(BB))
1363 Coverage[&BB] = (CountsFromProfile[Index++] != 0);
1364 assert(Index == CountsFromProfile.size());
1365
1366 // For each B in InverseDependencies[A], if A is covered then B is covered.
1367 DenseMap<const BasicBlock *, DenseSet<const BasicBlock *>>
1368 InverseDependencies;
1369 for (auto &BB : F) {
1370 for (auto *Dep : FuncInfo.BCI->getDependencies(BB)) {
1371 // If Dep is covered then BB is covered.
1372 InverseDependencies[Dep].insert(V: &BB);
1373 }
1374 }
1375
1376 // Infer coverage of the non-instrumented blocks using a flood-fill algorithm.
1377 std::stack<const BasicBlock *> CoveredBlocksToProcess;
1378 for (auto &[BB, IsCovered] : Coverage)
1379 if (IsCovered)
1380 CoveredBlocksToProcess.push(x: BB);
1381
1382 while (!CoveredBlocksToProcess.empty()) {
1383 auto *CoveredBlock = CoveredBlocksToProcess.top();
1384 assert(Coverage[CoveredBlock]);
1385 CoveredBlocksToProcess.pop();
1386 for (auto *BB : InverseDependencies[CoveredBlock]) {
1387 // If CoveredBlock is covered then BB is covered.
1388 bool &Cov = Coverage[BB];
1389 if (Cov)
1390 continue;
1391 Cov = true;
1392 CoveredBlocksToProcess.push(x: BB);
1393 }
1394 }
1395
1396 // Annotate block coverage.
1397 MDBuilder MDB(F.getContext());
1398 // We set the entry count to 10000 if the entry block is covered so that BFI
1399 // can propagate a fraction of this count to the other covered blocks.
1400 F.setEntryCount(Count: Coverage[&F.getEntryBlock()] ? 10000 : 0);
1401 for (auto &BB : F) {
1402 // For a block A and its successor B, we set the edge weight as follows:
1403 // If A is covered and B is covered, set weight=1.
1404 // If A is covered and B is uncovered, set weight=0.
1405 // If A is uncovered, set weight=1.
1406 // This setup will allow BFI to give nonzero profile counts to only covered
1407 // blocks.
1408 SmallVector<uint32_t, 4> Weights;
1409 for (auto *Succ : successors(BB: &BB))
1410 Weights.push_back(Elt: (Coverage[Succ] || !Coverage[&BB]) ? 1 : 0);
1411 if (Weights.size() >= 2)
1412 llvm::setBranchWeights(I&: *BB.getTerminator(), Weights,
1413 /*IsExpected=*/false);
1414 }
1415
1416 unsigned NumCorruptCoverage = 0;
1417 CycleInfo CI;
1418 CI.compute(F);
1419 BranchProbabilityInfo BPI(F, CI);
1420 BlockFrequencyInfo BFI(F, BPI, CI);
1421 auto IsBlockDead = [&](const BasicBlock &BB) -> std::optional<bool> {
1422 if (auto C = BFI.getBlockProfileCount(BB: &BB))
1423 return C == 0;
1424 return {};
1425 };
1426 LLVM_DEBUG(dbgs() << "Block Coverage: (Instrumented=*, Covered=X)\n");
1427 for (auto &BB : F) {
1428 LLVM_DEBUG(dbgs() << (FuncInfo.BCI->shouldInstrumentBlock(BB) ? "* " : " ")
1429 << (Coverage[&BB] ? "X " : " ") << " " << BB.getName()
1430 << "\n");
1431 // In some cases it is possible to find a covered block that has no covered
1432 // successors, e.g., when a block calls a function that may call exit(). In
1433 // those cases, BFI could find its successor to be covered while BCI could
1434 // find its successor to be dead.
1435 const bool &Cov = Coverage[&BB];
1436 if (Cov == IsBlockDead(BB).value_or(u: false)) {
1437 LLVM_DEBUG(
1438 dbgs() << "Found inconsistent block covearge for " << BB.getName()
1439 << ": BCI=" << (Cov ? "Covered" : "Dead") << " BFI="
1440 << (IsBlockDead(BB).value() ? "Dead" : "Covered") << "\n");
1441 ++NumCorruptCoverage;
1442 }
1443 if (Cov)
1444 ++NumCoveredBlocks;
1445 }
1446 if (Opts.pgo_verify_bfi && NumCorruptCoverage) {
1447 auto &Ctx = M->getContext();
1448 Ctx.diagnose(DI: DiagnosticInfoPGOProfile(
1449 M->getName().data(),
1450 Twine("Found inconsistent block coverage for function ") + F.getName() +
1451 " in " + Twine(NumCorruptCoverage) + " blocks.",
1452 DS_Warning));
1453 }
1454 if (Opts.pgo_view_block_coverage_graph)
1455 FuncInfo.BCI->viewBlockCoverageGraph(Coverage: &Coverage);
1456}
1457
1458// Populate the counters from instrumented BBs to all BBs.
1459// In the end of this operation, all BBs should have a valid count value.
1460void PGOUseFunc::populateCounters() {
1461 bool Changes = true;
1462 unsigned NumPasses = 0;
1463 while (Changes) {
1464 NumPasses++;
1465 Changes = false;
1466
1467 // For efficient traversal, it's better to start from the end as most
1468 // of the instrumented edges are at the end.
1469 for (auto &BB : reverse(C&: F)) {
1470 PGOUseBBInfo *UseBBInfo = findBBInfo(BB: &BB);
1471 if (UseBBInfo == nullptr)
1472 continue;
1473 if (!UseBBInfo->Count) {
1474 if (UseBBInfo->UnknownCountOutEdge == 0) {
1475 UseBBInfo->Count = sumEdgeCount(Edges: UseBBInfo->OutEdges);
1476 Changes = true;
1477 } else if (UseBBInfo->UnknownCountInEdge == 0) {
1478 UseBBInfo->Count = sumEdgeCount(Edges: UseBBInfo->InEdges);
1479 Changes = true;
1480 }
1481 }
1482 if (UseBBInfo->Count) {
1483 if (UseBBInfo->UnknownCountOutEdge == 1) {
1484 uint64_t Total = 0;
1485 uint64_t OutSum = sumEdgeCount(Edges: UseBBInfo->OutEdges);
1486 // If the one of the successor block can early terminate (no-return),
1487 // we can end up with situation where out edge sum count is larger as
1488 // the source BB's count is collected by a post-dominated block.
1489 if (*UseBBInfo->Count > OutSum)
1490 Total = *UseBBInfo->Count - OutSum;
1491 setEdgeCount(Edges&: UseBBInfo->OutEdges, Value: Total);
1492 Changes = true;
1493 }
1494 if (UseBBInfo->UnknownCountInEdge == 1) {
1495 uint64_t Total = 0;
1496 uint64_t InSum = sumEdgeCount(Edges: UseBBInfo->InEdges);
1497 if (*UseBBInfo->Count > InSum)
1498 Total = *UseBBInfo->Count - InSum;
1499 setEdgeCount(Edges&: UseBBInfo->InEdges, Value: Total);
1500 Changes = true;
1501 }
1502 }
1503 }
1504 }
1505
1506 LLVM_DEBUG(dbgs() << "Populate counts in " << NumPasses << " passes.\n");
1507 (void)NumPasses;
1508#ifndef NDEBUG
1509 // Assert every BB has a valid counter.
1510 for (auto &BB : F) {
1511 auto BI = findBBInfo(&BB);
1512 if (BI == nullptr)
1513 continue;
1514 assert(BI->Count && "BB count is not valid");
1515 }
1516#endif
1517 // Now annotate select instructions. This may fixup impossible block counts.
1518 FuncInfo.SIVisitor.annotateSelects(UF: this, Ind: &CountPosition);
1519 assert(CountPosition == ProfileCountSize);
1520
1521 uint64_t FuncEntryCount = *getBBInfo(BB: &*F.begin()).Count;
1522 uint64_t FuncMaxCount = FuncEntryCount;
1523 for (auto &BB : F) {
1524 auto BI = findBBInfo(BB: &BB);
1525 if (BI == nullptr)
1526 continue;
1527 FuncMaxCount = std::max(a: FuncMaxCount, b: *BI->Count);
1528 }
1529
1530 // Fix the obviously inconsistent entry count.
1531 if (FuncMaxCount > 0 && FuncEntryCount == 0)
1532 FuncEntryCount = 1;
1533 F.setEntryCount(Count: FuncEntryCount);
1534 markFunctionAttributes(EntryCount: FuncEntryCount, MaxCount: FuncMaxCount);
1535
1536 LLVM_DEBUG(FuncInfo.dumpInfo("after reading profile."));
1537}
1538
1539// Assign the scaled count values to the BB with multiple out edges.
1540void PGOUseFunc::setBranchWeights() {
1541 // Generate MD_prof metadata for every branch instruction.
1542 LLVM_DEBUG(dbgs() << "\nSetting branch weights for func " << F.getName()
1543 << " IsCS=" << IsCS << "\n");
1544 for (auto &BB : F) {
1545 Instruction *TI = BB.getTerminator();
1546 if (TI->getNumSuccessors() < 2)
1547 continue;
1548 if (!(isa<CondBrInst>(Val: TI) || isa<SwitchInst>(Val: TI) ||
1549 isa<IndirectBrInst>(Val: TI) || isa<InvokeInst>(Val: TI) ||
1550 isa<CallBrInst>(Val: TI)))
1551 continue;
1552
1553 const PGOUseBBInfo &BBCountInfo = getBBInfo(BB: &BB);
1554 if (!*BBCountInfo.Count)
1555 continue;
1556
1557 // We have a non-zero Branch BB.
1558
1559 // SuccessorCount can be greater than OutEdgesCount, because
1560 // removed edges don't appear in OutEdges.
1561 unsigned OutEdgesCount = BBCountInfo.OutEdges.size();
1562 unsigned SuccessorCount = BB.getTerminator()->getNumSuccessors();
1563 assert(OutEdgesCount <= SuccessorCount);
1564
1565 SmallVector<uint64_t, 2> EdgeCounts(SuccessorCount, 0);
1566 uint64_t MaxCount = 0;
1567 for (unsigned It = 0; It < OutEdgesCount; It++) {
1568 const PGOUseEdge *E = BBCountInfo.OutEdges[It];
1569 const BasicBlock *SrcBB = E->SrcBB;
1570 const BasicBlock *DestBB = E->DestBB;
1571 if (DestBB == nullptr)
1572 continue;
1573 unsigned SuccNum = GetSuccessorNumber(BB: SrcBB, Succ: DestBB);
1574 uint64_t EdgeCount = *E->Count;
1575 if (EdgeCount > MaxCount)
1576 MaxCount = EdgeCount;
1577 EdgeCounts[SuccNum] = EdgeCount;
1578 }
1579
1580 if (MaxCount)
1581 setProfMetadata(TI, EdgeCounts, MaxCount);
1582 else {
1583 // A zero MaxCount can come about when we have a BB with a positive
1584 // count, and whose successor blocks all have 0 count. This can happen
1585 // when there is no exit block and the code exits via a noreturn function.
1586 auto &Ctx = M->getContext();
1587 Ctx.diagnose(DI: DiagnosticInfoPGOProfile(
1588 M->getName().data(),
1589 Twine("Profile in ") + F.getName().str() +
1590 Twine(" partially ignored") +
1591 Twine(", possibly due to the lack of a return path."),
1592 DS_Warning));
1593 }
1594 }
1595}
1596
1597static bool isIndirectBrTarget(BasicBlock *BB) {
1598 for (BasicBlock *Pred : predecessors(BB)) {
1599 if (isa<IndirectBrInst>(Val: Pred->getTerminator()))
1600 return true;
1601 }
1602 return false;
1603}
1604
1605void PGOUseFunc::annotateIrrLoopHeaderWeights() {
1606 LLVM_DEBUG(dbgs() << "\nAnnotating irreducible loop header weights.\n");
1607 // Find irr loop headers
1608 for (auto &BB : F) {
1609 // As a heuristic also annotate indrectbr targets as they have a high chance
1610 // to become an irreducible loop header after the indirectbr tail
1611 // duplication.
1612 if (BFI->isIrrLoopHeader(BB: &BB) || isIndirectBrTarget(BB: &BB)) {
1613 Instruction *TI = BB.getTerminator();
1614 const PGOUseBBInfo &BBCountInfo = getBBInfo(BB: &BB);
1615 setIrrLoopHeaderMetadata(M, TI, Count: *BBCountInfo.Count);
1616 }
1617 }
1618}
1619
1620void PGOUseFunc::setBlockUniformityAttribute() {
1621 if (ProfileRecord.UniformityBits.empty())
1622 return;
1623
1624 // Annotate uniformity on each instrumented IR basic block so later codegen
1625 // passes (MachineFunction) can consume it without relying on fragile block
1626 // numbering heuristics.
1627 //
1628 // Metadata kind: LLVMContext::MD_block_uniformity_profile
1629 // Payload: i1 (true = uniform, false = divergent)
1630
1631 std::vector<BasicBlock *> InstrumentBBs;
1632 FuncInfo.getInstrumentBBs(InstrumentBBs);
1633
1634 LLVMContext &Ctx = F.getContext();
1635 Type *Int1Ty = Type::getInt1Ty(C&: Ctx);
1636
1637 for (size_t I = 0, E = InstrumentBBs.size(); I < E; ++I) {
1638 BasicBlock *BB = InstrumentBBs[I];
1639 if (!BB)
1640 continue;
1641 bool IsUniform = ProfileRecord.isBlockUniform(BlockIdx: I);
1642 auto *MD = MDNode::get(
1643 Context&: Ctx, MDs: ConstantAsMetadata::get(C: ConstantInt::get(Ty: Int1Ty, V: IsUniform)));
1644 BB->getTerminator()->setMetadata(KindID: LLVMContext::MD_block_uniformity_profile,
1645 Node: MD);
1646 }
1647
1648 LLVM_DEBUG({
1649 dbgs() << "PGO: Set block uniformity profile for " << F.getName() << ": ";
1650 for (size_t I = 0, E = InstrumentBBs.size(); I < E; ++I)
1651 dbgs() << (ProfileRecord.isBlockUniform(I) ? 'U' : 'D');
1652 dbgs() << "\n";
1653 });
1654}
1655
1656void SelectInstVisitor::instrumentOneSelectInst(SelectInst &SI) {
1657 Module *M = F.getParent();
1658 IRBuilder<> Builder(&SI);
1659 Type *Int64Ty = Builder.getInt64Ty();
1660 Value *Cond = SI.getCondition();
1661 // Freeze the condition so that a poison condition can only increment by
1662 // 0 or 1, but not some other value.
1663 if (!isGuaranteedNotToBePoison(V: Cond))
1664 Cond = Builder.CreateFreeze(V: Cond);
1665 auto *Step = Builder.CreateZExt(V: Cond, DestTy: Int64Ty);
1666 auto *NormalizedFuncNameVarPtr =
1667 ConstantExpr::getPointerBitCastOrAddrSpaceCast(
1668 C: FuncNameVar, Ty: PointerType::get(C&: M->getContext(), AddressSpace: 0));
1669 Builder.CreateIntrinsic(ID: Intrinsic::instrprof_increment_step,
1670 Args: {NormalizedFuncNameVarPtr, Builder.getInt64(C: FuncHash),
1671 Builder.getInt32(C: TotalNumCtrs),
1672 Builder.getInt32(C: *CurCtrIdx), Step});
1673 ++(*CurCtrIdx);
1674}
1675
1676void SelectInstVisitor::annotateOneSelectInst(SelectInst &SI) {
1677 std::vector<uint64_t> &CountFromProfile = UseFunc->getProfileRecord().Counts;
1678 assert(*CurCtrIdx < CountFromProfile.size() &&
1679 "Out of bound access of counters");
1680 uint64_t SCounts[2];
1681 SCounts[0] = CountFromProfile[*CurCtrIdx]; // True count
1682 ++(*CurCtrIdx);
1683 uint64_t TotalCount = 0;
1684 auto BI = UseFunc->findBBInfo(BB: SI.getParent());
1685 if (BI != nullptr) {
1686 TotalCount = *BI->Count;
1687
1688 // Fix the block count if it is impossible.
1689 if (TotalCount < SCounts[0])
1690 BI->Count = SCounts[0];
1691 }
1692 // False Count
1693 SCounts[1] = (TotalCount > SCounts[0] ? TotalCount - SCounts[0] : 0);
1694 uint64_t MaxCount = std::max(a: SCounts[0], b: SCounts[1]);
1695 if (MaxCount)
1696 setProfMetadata(TI: &SI, EdgeCounts: SCounts, MaxCount);
1697}
1698
1699void SelectInstVisitor::visitSelectInst(SelectInst &SI) {
1700 if (!Opts.pgo_instr_select || Opts.pgo_function_entry_coverage ||
1701 HasSingleByteCoverage)
1702 return;
1703 // FIXME: do not handle this yet.
1704 if (SI.getCondition()->getType()->isVectorTy())
1705 return;
1706
1707 switch (Mode) {
1708 case VM_counting:
1709 NSIs++;
1710 return;
1711 case VM_instrument:
1712 instrumentOneSelectInst(SI);
1713 return;
1714 case VM_annotate:
1715 annotateOneSelectInst(SI);
1716 return;
1717 }
1718
1719 llvm_unreachable("Unknown visiting mode");
1720}
1721
1722static uint32_t getMaxNumAnnotations(const InstrumentationOptions &Opts,
1723 const LLVMContext &C,
1724 InstrProfValueKind ValueProfKind) {
1725 if (ValueProfKind == IPVK_MemOPSize)
1726 return Opts.memop_max_annotations;
1727 if (ValueProfKind == llvm::IPVK_VTableTarget)
1728 return getMaxNumVTableAnnotations(C);
1729 return Opts.icp_max_annotations;
1730}
1731
1732// Traverse all valuesites and annotate the instructions for all value kind.
1733void PGOUseFunc::annotateValueSites() {
1734 if (Opts.disable_vp)
1735 return;
1736
1737 for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
1738 annotateValueSites(Kind);
1739}
1740
1741// Annotate the instructions for a specific value kind.
1742void PGOUseFunc::annotateValueSites(uint32_t Kind) {
1743 assert(Kind <= IPVK_Last);
1744 unsigned ValueSiteIndex = 0;
1745
1746 unsigned NumValueSites = ProfileRecord.getNumValueSites(ValueKind: Kind);
1747
1748 // Since there isn't a reliable or fast way for profile reader to tell if a
1749 // profile is generated with `-enable-vtable-value-profiling` on, we run the
1750 // value profile collector over the function IR to find the instrumented sites
1751 // iff function profile records shows the number of instrumented vtable sites
1752 // is not zero. Function cfg already takes the number of instrumented
1753 // indirect call sites into account so it doesn't hash the number of
1754 // instrumented vtables; as a side effect it makes it easier to enable
1755 // profiling and profile use in two steps if needed.
1756 // TODO: Remove this if/when -enable-vtable-value-profiling is on by default.
1757 if (NumValueSites > 0 && Kind == IPVK_VTableTarget &&
1758 NumValueSites != FuncInfo.ValueSites[IPVK_VTableTarget].size() &&
1759 getMaxNumVTableAnnotations(C: M->getContext()) != 0)
1760 FuncInfo.ValueSites[IPVK_VTableTarget] = VPC.get(Kind: IPVK_VTableTarget);
1761 auto &ValueSites = FuncInfo.ValueSites[Kind];
1762 if (NumValueSites != ValueSites.size()) {
1763 auto &Ctx = M->getContext();
1764 Ctx.diagnose(DI: DiagnosticInfoPGOProfile(
1765 M->getName().data(),
1766 Twine("Inconsistent number of value sites for ") +
1767 Twine(ValueProfKindDescr[Kind]) + Twine(" profiling in \"") +
1768 F.getName().str() +
1769 Twine("\", possibly due to the use of a stale profile."),
1770 DS_Warning));
1771 return;
1772 }
1773
1774 for (VPCandidateInfo &I : ValueSites) {
1775 LLVM_DEBUG(dbgs() << "Read one value site profile (kind = " << Kind
1776 << "): Index = " << ValueSiteIndex << " out of "
1777 << NumValueSites << "\n");
1778 annotateValueSite(
1779 M&: *M, Inst&: *I.AnnotatedInst, InstrProfR: ProfileRecord,
1780 ValueKind: static_cast<InstrProfValueKind>(Kind), SiteIndx: ValueSiteIndex,
1781 MaxMDCount: getMaxNumAnnotations(Opts, C: M->getContext(),
1782 ValueProfKind: static_cast<InstrProfValueKind>(Kind)));
1783 ValueSiteIndex++;
1784 }
1785}
1786
1787// Collect the set of members for each Comdat in module M and store
1788// in ComdatMembers.
1789static void collectComdatMembers(
1790 const InstrumentationOptions &Opts, Module &M,
1791 std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers) {
1792 if (!Opts.do_comdat_renaming)
1793 return;
1794 for (Function &F : M)
1795 if (Comdat *C = F.getComdat())
1796 ComdatMembers.insert(x: std::make_pair(x&: C, y: &F));
1797 for (GlobalVariable &GV : M.globals())
1798 if (Comdat *C = GV.getComdat())
1799 ComdatMembers.insert(x: std::make_pair(x&: C, y: &GV));
1800 for (GlobalAlias &GA : M.aliases())
1801 if (Comdat *C = GA.getComdat())
1802 ComdatMembers.insert(x: std::make_pair(x&: C, y: &GA));
1803}
1804
1805// Return true if we should not find instrumentation data for this function
1806static bool skipPGOUse(const InstrumentationOptions &Opts, const Function &F) {
1807 if (F.isDeclaration())
1808 return true;
1809 // If there are too many critical edges, PGO might cause
1810 // compiler time problem. Skip PGO if the number of
1811 // critical edges execeed the threshold.
1812 unsigned NumCriticalEdges = 0;
1813 for (auto &BB : F) {
1814 const Instruction *TI = BB.getTerminator();
1815 for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) {
1816 if (isCriticalEdge(TI, SuccNum: I))
1817 NumCriticalEdges++;
1818 }
1819 }
1820 if (NumCriticalEdges > Opts.pgo_critical_edge_threshold) {
1821 LLVM_DEBUG(dbgs() << "In func " << F.getName()
1822 << ", NumCriticalEdges=" << NumCriticalEdges
1823 << " exceed the threshold. Skip PGO.\n");
1824 return true;
1825 }
1826 return false;
1827}
1828
1829// Return true if we should not instrument this function
1830static bool skipPGOGen(const InstrumentationOptions &Opts, const Function &F) {
1831 if (skipPGOUse(Opts, F))
1832 return true;
1833 if (F.hasFnAttribute(Kind: llvm::Attribute::Naked))
1834 return true;
1835 if (F.hasFnAttribute(Kind: llvm::Attribute::NoProfile))
1836 return true;
1837 if (F.hasFnAttribute(Kind: llvm::Attribute::SkipProfile))
1838 return true;
1839 if (F.getInstructionCount() < Opts.pgo_function_size_threshold)
1840 return true;
1841 if (Opts.pgo_instrument_cold_function_only) {
1842 if (auto EntryCount = F.getEntryCount())
1843 return *EntryCount > Opts.pgo_cold_instrument_entry_threshold;
1844 return !Opts.pgo_treat_unknown_as_cold;
1845 }
1846 return false;
1847}
1848
1849static bool instrumentAllFunctions(
1850 const InstrumentationOptions &Opts, Module &M,
1851 function_ref<TargetLibraryInfo &(Function &)> LookupTLI,
1852 function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
1853 function_ref<BlockFrequencyInfo *(Function &)> LookupBFI,
1854 function_ref<LoopInfo *(Function &)> LookupLI,
1855 PGOInstrumentationType InstrumentationType) {
1856 // For the context-sensitive instrumentation, we should have a separated pass
1857 // (before LTO/ThinLTO linking) to create these variables.
1858 if (InstrumentationType == PGOInstrumentationType::FDO)
1859 createIRLevelProfileFlagVar(Opts, M, InstrumentationType);
1860
1861 Triple TT(M.getTargetTriple());
1862 LLVMContext &Ctx = M.getContext();
1863 if (!TT.isOSBinFormatELF() && EnableVTableValueProfiling)
1864 Ctx.diagnose(DI: DiagnosticInfoPGOProfile(
1865 M.getName().data(),
1866 Twine("VTable value profiling is presently not "
1867 "supported for non-ELF object formats"),
1868 DS_Warning));
1869 std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
1870 collectComdatMembers(Opts, M, ComdatMembers);
1871
1872 for (auto &F : M) {
1873 if (skipPGOGen(Opts, F))
1874 continue;
1875 TargetLibraryInfo &TLI = LookupTLI(F);
1876 BranchProbabilityInfo *BPI = LookupBPI(F);
1877 BlockFrequencyInfo *BFI = LookupBFI(F);
1878 LoopInfo *LI = LookupLI(F);
1879 FunctionInstrumenter FI(Opts, M, F, TLI, ComdatMembers, BPI, BFI, LI,
1880 InstrumentationType);
1881 FI.instrument();
1882 }
1883 return true;
1884}
1885
1886PreservedAnalyses
1887PGOInstrumentationGenCreateVar::run(Module &M, ModuleAnalysisManager &MAM) {
1888 createProfileFileNameVar(M, InstrProfileOutput: CSInstrName);
1889 const InstrumentationOptions &Opts = getInstrumentationOptions(M);
1890 // The variable in a comdat may be discarded by LTO. Ensure the declaration
1891 // will be retained.
1892 appendToCompilerUsed(
1893 M, Values: createIRLevelProfileFlagVar(Opts, M, InstrumentationType: PGOInstrumentationType::CSFDO));
1894 if (ProfileSampling)
1895 createProfileSamplingVar(M);
1896 PreservedAnalyses PA;
1897 PA.preserve<FunctionAnalysisManagerModuleProxy>();
1898 PA.preserveSet<AllAnalysesOn<Function>>();
1899 return PA;
1900}
1901
1902PreservedAnalyses PGOInstrumentationGen::run(Module &M,
1903 ModuleAnalysisManager &MAM) {
1904 auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
1905 auto LookupTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
1906 return FAM.getResult<TargetLibraryAnalysis>(IR&: F);
1907 };
1908 auto LookupBPI = [&FAM](Function &F) {
1909 return &FAM.getResult<BranchProbabilityAnalysis>(IR&: F);
1910 };
1911 auto LookupBFI = [&FAM](Function &F) {
1912 return &FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
1913 };
1914 auto LookupLI = [&FAM](Function &F) {
1915 return &FAM.getResult<LoopAnalysis>(IR&: F);
1916 };
1917
1918 const InstrumentationOptions &Opts = getInstrumentationOptions(M);
1919 if (!instrumentAllFunctions(Opts, M, LookupTLI, LookupBPI, LookupBFI,
1920 LookupLI, InstrumentationType))
1921 return PreservedAnalyses::all();
1922
1923 return PreservedAnalyses::none();
1924}
1925
1926// Using the ratio b/w sums of profile count values and BFI count values to
1927// adjust the func entry count.
1928static void fixFuncEntryCount(PGOUseFunc &Func, CycleInfo &CI,
1929 BranchProbabilityInfo &NBPI) {
1930 Function &F = Func.getFunc();
1931 BlockFrequencyInfo NBFI(F, NBPI, CI);
1932#ifndef NDEBUG
1933 auto BFIEntryCount = F.getEntryCount();
1934 assert(BFIEntryCount && (*BFIEntryCount > 0) && "Invalid BFI Entrycount");
1935#endif
1936 auto SumCount = APFloat::getZero(Sem: APFloat::IEEEdouble());
1937 auto SumBFICount = APFloat::getZero(Sem: APFloat::IEEEdouble());
1938 for (auto &BBI : F) {
1939 uint64_t CountValue = 0;
1940 uint64_t BFICountValue = 0;
1941 if (!Func.findBBInfo(BB: &BBI))
1942 continue;
1943 auto BFICount = NBFI.getBlockProfileCount(BB: &BBI);
1944 CountValue = *Func.getBBInfo(BB: &BBI).Count;
1945 BFICountValue = *BFICount;
1946 SumCount.add(RHS: APFloat(CountValue * 1.0), RM: APFloat::rmNearestTiesToEven);
1947 SumBFICount.add(RHS: APFloat(BFICountValue * 1.0), RM: APFloat::rmNearestTiesToEven);
1948 }
1949 if (SumCount.isZero())
1950 return;
1951
1952 assert(SumBFICount.compare(APFloat(0.0)) == APFloat::cmpGreaterThan &&
1953 "Incorrect sum of BFI counts");
1954 if (SumBFICount.compare(RHS: SumCount) == APFloat::cmpEqual)
1955 return;
1956 double Scale = (SumCount / SumBFICount).convertToDouble();
1957 if (Scale < 1.001 && Scale > 0.999)
1958 return;
1959
1960 uint64_t FuncEntryCount = *Func.getBBInfo(BB: &*F.begin()).Count;
1961 uint64_t NewEntryCount = 0.5 + FuncEntryCount * Scale;
1962 if (NewEntryCount == 0)
1963 NewEntryCount = 1;
1964 if (NewEntryCount != FuncEntryCount) {
1965 F.setEntryCount(Count: NewEntryCount);
1966 LLVM_DEBUG(dbgs() << "FixFuncEntryCount: in " << F.getName()
1967 << ", entry_count " << FuncEntryCount << " --> "
1968 << NewEntryCount << "\n");
1969 }
1970}
1971
1972// Compare the profile count values with BFI count values, and print out
1973// the non-matching ones.
1974static void verifyFuncBFI(const InstrumentationOptions &Opts, PGOUseFunc &Func,
1975 CycleInfo &CI, BranchProbabilityInfo &NBPI,
1976 uint64_t HotCountThreshold,
1977 uint64_t ColdCountThreshold) {
1978 Function &F = Func.getFunc();
1979 BlockFrequencyInfo NBFI(F, NBPI, CI);
1980 // bool PrintFunc = false;
1981 bool HotBBOnly = Opts.pgo_verify_hot_bfi;
1982 StringRef Msg;
1983 OptimizationRemarkEmitter ORE(&F);
1984
1985 unsigned BBNum = 0, BBMisMatchNum = 0, NonZeroBBNum = 0;
1986 for (auto &BBI : F) {
1987 PGOUseBBInfo *BBInfo = Func.findBBInfo(BB: &BBI);
1988 if (!BBInfo)
1989 continue;
1990
1991 uint64_t CountValue = BBInfo->Count.value_or(u&: CountValue);
1992 uint64_t BFICountValue = 0;
1993
1994 BBNum++;
1995 if (CountValue)
1996 NonZeroBBNum++;
1997 auto BFICount = NBFI.getBlockProfileCount(BB: &BBI);
1998 if (BFICount)
1999 BFICountValue = *BFICount;
2000
2001 if (HotBBOnly) {
2002 bool rawIsHot = CountValue >= HotCountThreshold;
2003 bool BFIIsHot = BFICountValue >= HotCountThreshold;
2004 bool rawIsCold = CountValue <= ColdCountThreshold;
2005 bool ShowCount = false;
2006 if (rawIsHot && !BFIIsHot) {
2007 Msg = "raw-Hot to BFI-nonHot";
2008 ShowCount = true;
2009 } else if (rawIsCold && BFIIsHot) {
2010 Msg = "raw-Cold to BFI-Hot";
2011 ShowCount = true;
2012 }
2013 if (!ShowCount)
2014 continue;
2015 } else {
2016 if ((CountValue < Opts.pgo_verify_bfi_cutoff) &&
2017 (BFICountValue < Opts.pgo_verify_bfi_cutoff))
2018 continue;
2019 uint64_t Diff = (BFICountValue >= CountValue)
2020 ? BFICountValue - CountValue
2021 : CountValue - BFICountValue;
2022 if (Diff <= CountValue / 100 * Opts.pgo_verify_bfi_ratio)
2023 continue;
2024 }
2025 BBMisMatchNum++;
2026
2027 ORE.emit(RemarkBuilder: [&]() {
2028 OptimizationRemarkAnalysis Remark(DEBUG_TYPE, "bfi-verify",
2029 F.getSubprogram(), &BBI);
2030 Remark << "BB " << ore::NV("Block", BBI.getName())
2031 << " Count=" << ore::NV("Count", CountValue)
2032 << " BFI_Count=" << ore::NV("Count", BFICountValue);
2033 if (!Msg.empty())
2034 Remark << " (" << Msg << ")";
2035 return Remark;
2036 });
2037 }
2038 if (BBMisMatchNum)
2039 ORE.emit(RemarkBuilder: [&]() {
2040 return OptimizationRemarkAnalysis(DEBUG_TYPE, "bfi-verify",
2041 F.getSubprogram(), &F.getEntryBlock())
2042 << "In Func " << ore::NV("Function", F.getName())
2043 << ": Num_of_BB=" << ore::NV("Count", BBNum)
2044 << ", Num_of_non_zerovalue_BB=" << ore::NV("Count", NonZeroBBNum)
2045 << ", Num_of_mis_matching_BB=" << ore::NV("Count", BBMisMatchNum);
2046 });
2047}
2048
2049static bool annotateAllFunctions(
2050 const InstrumentationOptions &Opts, Module &M, StringRef ProfileFileName,
2051 StringRef ProfileRemappingFileName, vfs::FileSystem &FS,
2052 function_ref<TargetLibraryInfo &(Function &)> LookupTLI,
2053 function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
2054 function_ref<BlockFrequencyInfo *(Function &)> LookupBFI,
2055 function_ref<LoopInfo *(Function &)> LookupLI, ProfileSummaryInfo *PSI,
2056 bool IsCS) {
2057 LLVM_DEBUG(dbgs() << "Read in profile counters: ");
2058 auto &Ctx = M.getContext();
2059 // Read the counter array from file.
2060 auto ReaderOrErr = IndexedInstrProfReader::create(Path: ProfileFileName, FS,
2061 RemappingPath: ProfileRemappingFileName);
2062 if (Error E = ReaderOrErr.takeError()) {
2063 handleAllErrors(E: std::move(E), Handlers: [&](const ErrorInfoBase &EI) {
2064 Ctx.diagnose(
2065 DI: DiagnosticInfoPGOProfile(ProfileFileName.data(), EI.message()));
2066 });
2067 return false;
2068 }
2069
2070 std::unique_ptr<IndexedInstrProfReader> PGOReader =
2071 std::move(ReaderOrErr.get());
2072 if (!PGOReader) {
2073 Ctx.diagnose(DI: DiagnosticInfoPGOProfile(ProfileFileName.data(),
2074 StringRef("Cannot get PGOReader")));
2075 return false;
2076 }
2077 if (!PGOReader->hasCSIRLevelProfile() && IsCS)
2078 return false;
2079
2080 // TODO: might need to change the warning once the clang option is finalized.
2081 if (!PGOReader->isIRLevelProfile()) {
2082 Ctx.diagnose(DI: DiagnosticInfoPGOProfile(
2083 ProfileFileName.data(), "Not an IR level instrumentation profile"));
2084 return false;
2085 }
2086 if (PGOReader->functionEntryOnly()) {
2087 Ctx.diagnose(DI: DiagnosticInfoPGOProfile(
2088 ProfileFileName.data(),
2089 "Function entry profiles are not yet supported for optimization"));
2090 return false;
2091 }
2092
2093 // Add the profile summary (read from the header of the indexed summary) here
2094 // so that we can use it below when reading counters (which checks if the
2095 // function should be marked with a cold or inlinehint attribute).
2096 M.setProfileSummary(M: PGOReader->getSummary(UseCS: IsCS).getMD(Context&: M.getContext()),
2097 Kind: IsCS ? ProfileSummary::PSK_CSInstr
2098 : ProfileSummary::PSK_Instr);
2099 PSI->refresh();
2100
2101 std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
2102 collectComdatMembers(Opts, M, ComdatMembers);
2103 std::vector<Function *> HotFunctions;
2104 std::vector<Function *> ColdFunctions;
2105
2106 // If the profile marked as always instrument the entry BB, do the
2107 // same. Note this can be overwritten by the internal option in CFGMST.h
2108 bool InstrumentFuncEntry =
2109 valueOr(X: Opts.pgo_instrument_entry, Default: PGOReader->instrEntryBBEnabled());
2110 bool InstrumentLoopEntries = valueOr(X: Opts.pgo_instrument_loop_entries,
2111 Default: PGOReader->instrLoopEntriesEnabled());
2112
2113 bool HasSingleByteCoverage = PGOReader->hasSingleByteCoverage();
2114 for (auto &F : M) {
2115 if (skipPGOUse(Opts, F))
2116 continue;
2117 TargetLibraryInfo &TLI = LookupTLI(F);
2118 BranchProbabilityInfo *BPI = LookupBPI(F);
2119 BlockFrequencyInfo *BFI = LookupBFI(F);
2120 LoopInfo *LI = LookupLI(F);
2121 if (!HasSingleByteCoverage) {
2122 // Split indirectbr critical edges here before computing the MST rather
2123 // than later in getInstrBB() to avoid invalidating it.
2124 SplitIndirectBrCriticalEdges(F, /*IgnoreBlocksWithoutPHI=*/false, BPI,
2125 BFI);
2126 }
2127 PGOUseFunc Func(Opts, F, &M, TLI, ComdatMembers, BPI, BFI, LI, PSI, IsCS,
2128 InstrumentFuncEntry, InstrumentLoopEntries,
2129 HasSingleByteCoverage);
2130 if (!Func.getRecord(PGOReader: PGOReader.get()))
2131 continue;
2132 if (HasSingleByteCoverage) {
2133 Func.populateCoverage();
2134 continue;
2135 }
2136 // When PseudoKind is set to a value other than InstrProfRecord::NotPseudo,
2137 // it means the profile for the function is unrepresentative and this
2138 // function is actually hot / warm. We will reset the function hot / cold
2139 // attribute and drop all the profile counters.
2140 InstrProfRecord::CountPseudoKind PseudoKind = InstrProfRecord::NotPseudo;
2141 bool AllZeros = false;
2142 if (!Func.readCounters(AllZeros, PseudoKind))
2143 continue;
2144 if (AllZeros) {
2145 F.setEntryCount(Count: 0);
2146 if (Func.getProgramMaxCount() != 0)
2147 ColdFunctions.push_back(x: &F);
2148 continue;
2149 }
2150 if (PseudoKind != InstrProfRecord::NotPseudo) {
2151 // Clear function attribute cold.
2152 if (F.hasFnAttribute(Kind: Attribute::Cold))
2153 F.removeFnAttr(Kind: Attribute::Cold);
2154 // Set function attribute as hot.
2155 if (PseudoKind == InstrProfRecord::PseudoHot)
2156 F.addFnAttr(Kind: Attribute::Hot);
2157 continue;
2158 }
2159 Func.populateCounters();
2160 Func.setBranchWeights();
2161 Func.annotateValueSites();
2162 Func.annotateIrrLoopHeaderWeights();
2163 Func.setBlockUniformityAttribute();
2164 PGOUseFunc::FuncFreqAttr FreqAttr = Func.getFuncFreqAttr();
2165 if (FreqAttr == PGOUseFunc::FFA_Cold)
2166 ColdFunctions.push_back(x: &F);
2167 else if (FreqAttr == PGOUseFunc::FFA_Hot)
2168 HotFunctions.push_back(x: &F);
2169 PGOViewCountsType ViewCounts = getPGOViewCounts(C: F.getContext());
2170 StringRef ViewFuncName = getViewBlockFreqFuncName(C: F.getContext());
2171 if (ViewCounts != PGOViewCountsType::None &&
2172 (ViewFuncName.empty() || F.getName() == ViewFuncName)) {
2173 CycleInfo CI;
2174 CI.compute(F);
2175 std::unique_ptr<BranchProbabilityInfo> NewBPI =
2176 std::make_unique<BranchProbabilityInfo>(args&: F, args&: CI);
2177 std::unique_ptr<BlockFrequencyInfo> NewBFI =
2178 std::make_unique<BlockFrequencyInfo>(args&: F, args&: *NewBPI, args&: CI);
2179 if (ViewCounts == PGOViewCountsType::Graph)
2180 NewBFI->view();
2181 else if (ViewCounts == PGOViewCountsType::Text) {
2182 dbgs() << "pgo-view-counts: " << Func.getFunc().getName() << "\n";
2183 NewBFI->print(OS&: dbgs());
2184 }
2185 }
2186 if (Opts.pgo_view_raw_counts != PGOViewCountsType::None &&
2187 (ViewFuncName.empty() || F.getName() == ViewFuncName)) {
2188 if (Opts.pgo_view_raw_counts == PGOViewCountsType::Graph)
2189 if (ViewFuncName.empty())
2190 WriteGraph(G: &Func, Name: Twine("PGORawCounts_") + Func.getFunc().getName());
2191 else
2192 ViewGraph(G: &Func, Name: Twine("PGORawCounts_") + Func.getFunc().getName());
2193 else if (Opts.pgo_view_raw_counts == PGOViewCountsType::Text) {
2194 dbgs() << "pgo-view-raw-counts: " << Func.getFunc().getName() << "\n";
2195 Func.dumpInfo();
2196 }
2197 }
2198
2199 if (Opts.pgo_verify_bfi || Opts.pgo_verify_hot_bfi ||
2200 Opts.pgo_fix_entry_count) {
2201 CycleInfo CI;
2202 CI.compute(F);
2203 BranchProbabilityInfo NBPI(F, CI);
2204
2205 // Fix func entry count.
2206 if (Opts.pgo_fix_entry_count)
2207 fixFuncEntryCount(Func, CI, NBPI);
2208
2209 // Verify BlockFrequency information.
2210 uint64_t HotCountThreshold = 0, ColdCountThreshold = 0;
2211 if (Opts.pgo_verify_hot_bfi) {
2212 HotCountThreshold = PSI->getOrCompHotCountThreshold();
2213 ColdCountThreshold = PSI->getOrCompColdCountThreshold();
2214 }
2215 verifyFuncBFI(Opts, Func, CI, NBPI, HotCountThreshold,
2216 ColdCountThreshold);
2217 }
2218 }
2219
2220 // Set function hotness attribute from the profile.
2221 // We have to apply these attributes at the end because their presence
2222 // can affect the BranchProbabilityInfo of any callers, resulting in an
2223 // inconsistent MST between prof-gen and prof-use.
2224 for (auto &F : HotFunctions) {
2225 F->addFnAttr(Kind: Attribute::InlineHint);
2226 LLVM_DEBUG(dbgs() << "Set inline attribute to function: " << F->getName()
2227 << "\n");
2228 }
2229 for (auto &F : ColdFunctions) {
2230 // Only set when there is no Attribute::Hot set by the user. For Hot
2231 // attribute, user's annotation has the precedence over the profile.
2232 if (F->hasFnAttribute(Kind: Attribute::Hot)) {
2233 auto &Ctx = M.getContext();
2234 std::string Msg = std::string("Function ") + F->getName().str() +
2235 std::string(" is annotated as a hot function but"
2236 " the profile is cold");
2237 Ctx.diagnose(
2238 DI: DiagnosticInfoPGOProfile(M.getName().data(), Msg, DS_Warning));
2239 continue;
2240 }
2241 F->addFnAttr(Kind: Attribute::Cold);
2242 LLVM_DEBUG(dbgs() << "Set cold attribute to function: " << F->getName()
2243 << "\n");
2244 }
2245 return true;
2246}
2247
2248PGOInstrumentationUse::PGOInstrumentationUse(
2249 std::string Filename, std::string RemappingFilename, bool IsCS,
2250 IntrusiveRefCntPtr<vfs::FileSystem> VFS)
2251 : ProfileFileName(std::move(Filename)),
2252 ProfileRemappingFileName(std::move(RemappingFilename)), IsCS(IsCS),
2253 FS(std::move(VFS)) {
2254 if (!FS)
2255 FS = vfs::getRealFileSystem();
2256}
2257
2258PreservedAnalyses PGOInstrumentationUse::run(Module &M,
2259 ModuleAnalysisManager &MAM) {
2260
2261 auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
2262 auto LookupTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
2263 return FAM.getResult<TargetLibraryAnalysis>(IR&: F);
2264 };
2265 auto LookupBPI = [&FAM](Function &F) {
2266 return &FAM.getResult<BranchProbabilityAnalysis>(IR&: F);
2267 };
2268 auto LookupBFI = [&FAM](Function &F) {
2269 return &FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
2270 };
2271 auto LookupLI = [&FAM](Function &F) {
2272 return &FAM.getResult<LoopAnalysis>(IR&: F);
2273 };
2274
2275 auto *PSI = &MAM.getResult<ProfileSummaryAnalysis>(IR&: M);
2276 const InstrumentationOptions &Opts = getInstrumentationOptions(M);
2277 StringRef ProfileFile = ProfileFileName;
2278 if (!Opts.pgo_test_profile_file.empty())
2279 ProfileFile = Opts.pgo_test_profile_file;
2280 StringRef RemappingFile = ProfileRemappingFileName;
2281 if (!Opts.pgo_test_profile_remapping_file.empty())
2282 RemappingFile = Opts.pgo_test_profile_remapping_file;
2283 if (!annotateAllFunctions(Opts, M, ProfileFileName: ProfileFile, ProfileRemappingFileName: RemappingFile, FS&: *FS, LookupTLI,
2284 LookupBPI, LookupBFI, LookupLI, PSI, IsCS))
2285 return PreservedAnalyses::all();
2286
2287 return PreservedAnalyses::none();
2288}
2289
2290static std::string getSimpleNodeName(const BasicBlock *Node) {
2291 if (!Node->getName().empty())
2292 return Node->getName().str();
2293
2294 std::string SimpleNodeName;
2295 raw_string_ostream OS(SimpleNodeName);
2296 Node->printAsOperand(O&: OS, PrintType: false);
2297 return SimpleNodeName;
2298}
2299
2300void llvm::setProfMetadata(Instruction *TI, ArrayRef<uint64_t> EdgeCounts,
2301 uint64_t MaxCount) {
2302 auto Weights = downscaleWeights(Weights: EdgeCounts, KnownMaxCount: MaxCount);
2303
2304 LLVM_DEBUG(dbgs() << "Weight is: "; for (const auto &W : Weights) {
2305 dbgs() << W << " ";
2306 } dbgs() << "\n");
2307
2308 misexpect::checkExpectAnnotations(I: *TI, ExistingWeights: Weights, /*IsFrontend=*/false);
2309
2310 setBranchWeights(I&: *TI, Weights, /*IsExpected=*/false);
2311
2312 const InstrumentationOptions &Opts =
2313 getInstrumentationOptions(F: *TI->getFunction());
2314 if (Opts.pgo_emit_branch_prob) {
2315 std::string BrCondStr = getBranchCondString(TI);
2316 if (BrCondStr.empty())
2317 return;
2318
2319 uint64_t WSum =
2320 std::accumulate(first: Weights.begin(), last: Weights.end(), init: (uint64_t)0,
2321 binary_op: [](uint64_t w1, uint64_t w2) { return w1 + w2; });
2322 uint64_t TotalCount =
2323 std::accumulate(first: EdgeCounts.begin(), last: EdgeCounts.end(), init: (uint64_t)0,
2324 binary_op: [](uint64_t c1, uint64_t c2) { return c1 + c2; });
2325 uint64_t Scale = calculateCountScale(MaxCount: WSum);
2326 BranchProbability BP(scaleBranchCount(Count: Weights[0], Scale),
2327 scaleBranchCount(Count: WSum, Scale));
2328 std::string BranchProbStr;
2329 raw_string_ostream OS(BranchProbStr);
2330 OS << BP;
2331 OS << " (total count : " << TotalCount << ")";
2332 Function *F = TI->getParent()->getParent();
2333 OptimizationRemarkEmitter ORE(F);
2334 ORE.emit(RemarkBuilder: [&]() {
2335 return OptimizationRemark(DEBUG_TYPE, "pgo-instrumentation", TI)
2336 << BrCondStr << " is true with probability : " << BranchProbStr;
2337 });
2338 }
2339}
2340
2341namespace llvm {
2342
2343void setIrrLoopHeaderMetadata(Module *M, Instruction *TI, uint64_t Count) {
2344 MDBuilder MDB(M->getContext());
2345 TI->setMetadata(KindID: llvm::LLVMContext::MD_irr_loop,
2346 Node: MDB.createIrrLoopHeaderWeight(Weight: Count));
2347}
2348
2349template <> struct GraphTraits<PGOUseFunc *> {
2350 using NodeRef = const BasicBlock *;
2351 using ChildIteratorType = const_succ_iterator;
2352 using nodes_iterator = pointer_iterator<Function::const_iterator>;
2353
2354 static NodeRef getEntryNode(const PGOUseFunc *G) {
2355 return &G->getFunc().front();
2356 }
2357
2358 static ChildIteratorType child_begin(const NodeRef N) {
2359 return succ_begin(BB: N);
2360 }
2361
2362 static ChildIteratorType child_end(const NodeRef N) { return succ_end(BB: N); }
2363
2364 static nodes_iterator nodes_begin(const PGOUseFunc *G) {
2365 return nodes_iterator(G->getFunc().begin());
2366 }
2367
2368 static nodes_iterator nodes_end(const PGOUseFunc *G) {
2369 return nodes_iterator(G->getFunc().end());
2370 }
2371};
2372
2373template <> struct DOTGraphTraits<PGOUseFunc *> : DefaultDOTGraphTraits {
2374 explicit DOTGraphTraits(bool isSimple = false)
2375 : DefaultDOTGraphTraits(isSimple) {}
2376
2377 static std::string getGraphName(const PGOUseFunc *G) {
2378 return std::string(G->getFunc().getName());
2379 }
2380
2381 std::string getNodeLabel(const BasicBlock *Node, const PGOUseFunc *Graph) {
2382 std::string Result;
2383 raw_string_ostream OS(Result);
2384
2385 OS << getSimpleNodeName(Node) << ":\\l";
2386 PGOUseBBInfo *BI = Graph->findBBInfo(BB: Node);
2387 OS << "Count : ";
2388 if (BI && BI->Count)
2389 OS << *BI->Count << "\\l";
2390 else
2391 OS << "Unknown\\l";
2392
2393 const InstrumentationOptions &Opts =
2394 getInstrumentationOptions(F: *Node->getParent());
2395 if (!Opts.pgo_instr_select)
2396 return Result;
2397
2398 for (const Instruction &I : *Node) {
2399 if (!isa<SelectInst>(Val: &I))
2400 continue;
2401 // Display scaled counts for SELECT instruction:
2402 OS << "SELECT : { T = ";
2403 uint64_t TC, FC;
2404 bool HasProf = extractBranchWeights(I, TrueVal&: TC, FalseVal&: FC);
2405 if (!HasProf)
2406 OS << "Unknown, F = Unknown }\\l";
2407 else
2408 OS << TC << ", F = " << FC << " }\\l";
2409 }
2410 return Result;
2411 }
2412};
2413
2414} // end namespace llvm
2415