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