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