LLVM 17.0.0git
SampleProfileProbe.cpp
Go to the documentation of this file.
1//===- SampleProfileProbe.cpp - Pseudo probe 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 the SampleProfileProber transformation.
10//
11//===----------------------------------------------------------------------===//
12
14#include "llvm/ADT/Statistic.h"
18#include "llvm/IR/BasicBlock.h"
19#include "llvm/IR/Constants.h"
21#include "llvm/IR/IRBuilder.h"
22#include "llvm/IR/Instruction.h"
24#include "llvm/IR/MDBuilder.h"
25#include "llvm/IR/PseudoProbe.h"
27#include "llvm/Support/CRC.h"
32#include <unordered_set>
33#include <vector>
34
35using namespace llvm;
36#define DEBUG_TYPE "pseudo-probe"
37
38STATISTIC(ArtificialDbgLine,
39 "Number of probes that have an artificial debug line");
40
41static cl::opt<bool>
42 VerifyPseudoProbe("verify-pseudo-probe", cl::init(false), cl::Hidden,
43 cl::desc("Do pseudo probe verification"));
44
46 "verify-pseudo-probe-funcs", cl::Hidden,
47 cl::desc("The option to specify the name of the functions to verify."));
48
49static cl::opt<bool>
50 UpdatePseudoProbe("update-pseudo-probe", cl::init(true), cl::Hidden,
51 cl::desc("Update pseudo probe distribution factor"));
52
54 uint64_t Hash = 0;
55 const DILocation *InlinedAt = DIL ? DIL->getInlinedAt() : nullptr;
56 while (InlinedAt) {
57 Hash ^= MD5Hash(std::to_string(InlinedAt->getLine()));
58 Hash ^= MD5Hash(std::to_string(InlinedAt->getColumn()));
59 auto Name = InlinedAt->getSubprogramLinkageName();
60 Hash ^= MD5Hash(Name);
61 InlinedAt = InlinedAt->getInlinedAt();
62 }
63 return Hash;
64}
65
67 return getCallStackHash(Inst.getDebugLoc());
68}
69
70bool PseudoProbeVerifier::shouldVerifyFunction(const Function *F) {
71 // Skip function declaration.
72 if (F->isDeclaration())
73 return false;
74 // Skip function that will not be emitted into object file. The prevailing
75 // defintion will be verified instead.
76 if (F->hasAvailableExternallyLinkage())
77 return false;
78 // Do a name matching.
79 static std::unordered_set<std::string> VerifyFuncNames(
81 return VerifyFuncNames.empty() || VerifyFuncNames.count(F->getName().str());
82}
83
87 [this](StringRef P, Any IR, const PreservedAnalyses &) {
88 this->runAfterPass(P, IR);
89 });
90 }
91}
92
93// Callback to run after each transformation for the new pass manager.
95 std::string Banner =
96 "\n*** Pseudo Probe Verification After " + PassID.str() + " ***\n";
97 dbgs() << Banner;
98 if (const auto **M = any_cast<const Module *>(&IR))
99 runAfterPass(*M);
100 else if (const auto **F = any_cast<const Function *>(&IR))
101 runAfterPass(*F);
102 else if (const auto **C = any_cast<const LazyCallGraph::SCC *>(&IR))
103 runAfterPass(*C);
104 else if (const auto **L = any_cast<const Loop *>(&IR))
105 runAfterPass(*L);
106 else
107 llvm_unreachable("Unknown IR unit");
108}
109
111 for (const Function &F : *M)
112 runAfterPass(&F);
113}
114
116 for (const LazyCallGraph::Node &N : *C)
117 runAfterPass(&N.getFunction());
118}
119
121 if (!shouldVerifyFunction(F))
122 return;
123 ProbeFactorMap ProbeFactors;
124 for (const auto &BB : *F)
125 collectProbeFactors(&BB, ProbeFactors);
126 verifyProbeFactors(F, ProbeFactors);
127}
128
130 const Function *F = L->getHeader()->getParent();
132}
133
134void PseudoProbeVerifier::collectProbeFactors(const BasicBlock *Block,
135 ProbeFactorMap &ProbeFactors) {
136 for (const auto &I : *Block) {
137 if (std::optional<PseudoProbe> Probe = extractProbe(I)) {
139 ProbeFactors[{Probe->Id, Hash}] += Probe->Factor;
140 }
141 }
142}
143
144void PseudoProbeVerifier::verifyProbeFactors(
145 const Function *F, const ProbeFactorMap &ProbeFactors) {
146 bool BannerPrinted = false;
147 auto &PrevProbeFactors = FunctionProbeFactors[F->getName()];
148 for (const auto &I : ProbeFactors) {
149 float CurProbeFactor = I.second;
150 if (PrevProbeFactors.count(I.first)) {
151 float PrevProbeFactor = PrevProbeFactors[I.first];
152 if (std::abs(CurProbeFactor - PrevProbeFactor) >
153 DistributionFactorVariance) {
154 if (!BannerPrinted) {
155 dbgs() << "Function " << F->getName() << ":\n";
156 BannerPrinted = true;
157 }
158 dbgs() << "Probe " << I.first.first << "\tprevious factor "
159 << format("%0.2f", PrevProbeFactor) << "\tcurrent factor "
160 << format("%0.2f", CurProbeFactor) << "\n";
161 }
162 }
163
164 // Update
165 PrevProbeFactors[I.first] = I.second;
166 }
167}
168
170 if (NamedMDNode *FuncInfo = M.getNamedMetadata(PseudoProbeDescMetadataName)) {
171 for (const auto *Operand : FuncInfo->operands()) {
172 const auto *MD = cast<MDNode>(Operand);
173 auto GUID =
174 mdconst::dyn_extract<ConstantInt>(MD->getOperand(0))->getZExtValue();
175 auto Hash =
176 mdconst::dyn_extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
177 GUIDToProbeDescMap.try_emplace(GUID, PseudoProbeDescriptor(GUID, Hash));
178 }
179 }
180}
181
183PseudoProbeManager::getDesc(const Function &F) const {
184 auto I = GUIDToProbeDescMap.find(
186 return I == GUIDToProbeDescMap.end() ? nullptr : &I->second;
187}
188
190 return M.getNamedMetadata(PseudoProbeDescMetadataName);
191}
192
194 const FunctionSamples &Samples) const {
195 const auto *Desc = getDesc(F);
196 if (!Desc) {
197 LLVM_DEBUG(dbgs() << "Probe descriptor missing for Function " << F.getName()
198 << "\n");
199 return false;
200 } else {
201 if (Desc->getFunctionHash() != Samples.getFunctionHash()) {
202 LLVM_DEBUG(dbgs() << "Hash mismatch for Function " << F.getName()
203 << "\n");
204 return false;
205 }
206 }
207 return true;
208}
209
211 const std::string &CurModuleUniqueId)
212 : F(&Func), CurModuleUniqueId(CurModuleUniqueId) {
213 BlockProbeIds.clear();
214 CallProbeIds.clear();
216 computeProbeIdForBlocks();
217 computeProbeIdForCallsites();
218 computeCFGHash();
219}
220
221// Compute Hash value for the CFG: the lower 32 bits are CRC32 of the index
222// value of each BB in the CFG. The higher 32 bits record the number of edges
223// preceded by the number of indirect calls.
224// This is derived from FuncPGOInstrumentation<Edge, BBInfo>::computeCFGHash().
225void SampleProfileProber::computeCFGHash() {
226 std::vector<uint8_t> Indexes;
227 JamCRC JC;
228 for (auto &BB : *F) {
229 auto *TI = BB.getTerminator();
230 for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) {
231 auto *Succ = TI->getSuccessor(I);
232 auto Index = getBlockId(Succ);
233 for (int J = 0; J < 4; J++)
234 Indexes.push_back((uint8_t)(Index >> (J * 8)));
235 }
236 }
237
238 JC.update(Indexes);
239
240 FunctionHash = (uint64_t)CallProbeIds.size() << 48 |
241 (uint64_t)Indexes.size() << 32 | JC.getCRC();
242 // Reserve bit 60-63 for other information purpose.
243 FunctionHash &= 0x0FFFFFFFFFFFFFFF;
244 assert(FunctionHash && "Function checksum should not be zero");
245 LLVM_DEBUG(dbgs() << "\nFunction Hash Computation for " << F->getName()
246 << ":\n"
247 << " CRC = " << JC.getCRC() << ", Edges = "
248 << Indexes.size() << ", ICSites = " << CallProbeIds.size()
249 << ", Hash = " << FunctionHash << "\n");
250}
251
252void SampleProfileProber::computeProbeIdForBlocks() {
253 DenseSet<BasicBlock *> KnownColdBlocks;
254 computeEHOnlyBlocks(*F, KnownColdBlocks);
255 // Insert pseudo probe to non-cold blocks only. This will reduce IR size as
256 // well as the binary size while retaining the profile quality.
257 for (auto &BB : *F) {
258 ++LastProbeId;
259 if (!KnownColdBlocks.contains(&BB))
260 BlockProbeIds[&BB] = LastProbeId;
261 }
262}
263
264void SampleProfileProber::computeProbeIdForCallsites() {
265 for (auto &BB : *F) {
266 for (auto &I : BB) {
267 if (!isa<CallBase>(I))
268 continue;
269 if (isa<IntrinsicInst>(&I))
270 continue;
271 CallProbeIds[&I] = ++LastProbeId;
272 }
273 }
274}
275
276uint32_t SampleProfileProber::getBlockId(const BasicBlock *BB) const {
277 auto I = BlockProbeIds.find(const_cast<BasicBlock *>(BB));
278 return I == BlockProbeIds.end() ? 0 : I->second;
279}
280
281uint32_t SampleProfileProber::getCallsiteId(const Instruction *Call) const {
282 auto Iter = CallProbeIds.find(const_cast<Instruction *>(Call));
283 return Iter == CallProbeIds.end() ? 0 : Iter->second;
284}
285
287 Module *M = F.getParent();
288 MDBuilder MDB(F.getContext());
289 // Since the GUID from probe desc and inline stack are computed seperately, we
290 // need to make sure their names are consistent, so here also use the name
291 // from debug info.
292 StringRef FName = F.getName();
293 if (auto *SP = F.getSubprogram()) {
294 FName = SP->getLinkageName();
295 if (FName.empty())
296 FName = SP->getName();
297 }
298 uint64_t Guid = Function::getGUID(FName);
299
300 // Assign an artificial debug line to a probe that doesn't come with a real
301 // line. A probe not having a debug line will get an incomplete inline
302 // context. This will cause samples collected on the probe to be counted
303 // into the base profile instead of a context profile. The line number
304 // itself is not important though.
305 auto AssignDebugLoc = [&](Instruction *I) {
306 assert((isa<PseudoProbeInst>(I) || isa<CallBase>(I)) &&
307 "Expecting pseudo probe or call instructions");
308 if (!I->getDebugLoc()) {
309 if (auto *SP = F.getSubprogram()) {
310 auto DIL = DILocation::get(SP->getContext(), 0, 0, SP);
311 I->setDebugLoc(DIL);
312 ArtificialDbgLine++;
313 LLVM_DEBUG({
314 dbgs() << "\nIn Function " << F.getName()
315 << " Probe gets an artificial debug line\n";
316 I->dump();
317 });
318 }
319 }
320 };
321
322 // Probe basic blocks.
323 for (auto &I : BlockProbeIds) {
324 BasicBlock *BB = I.first;
325 uint32_t Index = I.second;
326 // Insert a probe before an instruction with a valid debug line number which
327 // will be assigned to the probe. The line number will be used later to
328 // model the inline context when the probe is inlined into other functions.
329 // Debug instructions, phi nodes and lifetime markers do not have an valid
330 // line number. Real instructions generated by optimizations may not come
331 // with a line number either.
332 auto HasValidDbgLine = [](Instruction *J) {
333 return !isa<PHINode>(J) && !isa<DbgInfoIntrinsic>(J) &&
334 !J->isLifetimeStartOrEnd() && J->getDebugLoc();
335 };
336
337 Instruction *J = &*BB->getFirstInsertionPt();
338 while (J != BB->getTerminator() && !HasValidDbgLine(J)) {
339 J = J->getNextNode();
340 }
341
343 assert(Builder.GetInsertPoint() != BB->end() &&
344 "Cannot get the probing point");
345 Function *ProbeFn =
346 llvm::Intrinsic::getDeclaration(M, Intrinsic::pseudoprobe);
347 Value *Args[] = {Builder.getInt64(Guid), Builder.getInt64(Index),
348 Builder.getInt32(0),
350 auto *Probe = Builder.CreateCall(ProbeFn, Args);
351 AssignDebugLoc(Probe);
352 }
353
354 // Probe both direct calls and indirect calls. Direct calls are probed so that
355 // their probe ID can be used as an call site identifier to represent a
356 // calling context.
357 for (auto &I : CallProbeIds) {
358 auto *Call = I.first;
359 uint32_t Index = I.second;
360 uint32_t Type = cast<CallBase>(Call)->getCalledFunction()
363 AssignDebugLoc(Call);
364 // Levarge the 32-bit discriminator field of debug data to store the ID and
365 // type of a callsite probe. This gets rid of the dependency on plumbing a
366 // customized metadata through the codegen pipeline.
369 if (auto DIL = Call->getDebugLoc()) {
370 DIL = DIL->cloneWithDiscriminator(V);
371 Call->setDebugLoc(DIL);
372 }
373 }
374
375 // Create module-level metadata that contains function info necessary to
376 // synthesize probe-based sample counts, which are
377 // - FunctionGUID
378 // - FunctionHash.
379 // - FunctionName
380 auto Hash = getFunctionHash();
381 auto *MD = MDB.createPseudoProbeDesc(Guid, Hash, FName);
382 auto *NMD = M->getNamedMetadata(PseudoProbeDescMetadataName);
383 assert(NMD && "llvm.pseudo_probe_desc should be pre-created");
384 NMD->addOperand(MD);
385
386 // Preserve a comdat group to hold all probes materialized later. This
387 // allows that when the function is considered dead and removed, the
388 // materialized probes are disposed too.
389 // Imported functions are defined in another module. They do not need
390 // the following handling since same care will be taken for them in their
391 // original module. The pseudo probes inserted into an imported functions
392 // above will naturally not be emitted since the imported function is free
393 // from object emission. However they will be emitted together with the
394 // inliner functions that the imported function is inlined into. We are not
395 // creating a comdat group for an import function since it's useless anyway.
396 if (!F.isDeclarationForLinker()) {
397 if (TM) {
398 auto Triple = TM->getTargetTriple();
399 if (Triple.supportsCOMDAT() && TM->getFunctionSections())
401 }
402 }
403}
404
407 auto ModuleId = getUniqueModuleId(&M);
408 // Create the pseudo probe desc metadata beforehand.
409 // Note that modules with only data but no functions will require this to
410 // be set up so that they will be known as probed later.
411 M.getOrInsertNamedMetadata(PseudoProbeDescMetadataName);
412
413 for (auto &F : M) {
414 if (F.isDeclaration())
415 continue;
416 SampleProfileProber ProbeManager(F, ModuleId);
417 ProbeManager.instrumentOneFunc(F, TM);
418 }
419
421}
422
423void PseudoProbeUpdatePass::runOnFunction(Function &F,
426 auto BBProfileCount = [&BFI](BasicBlock *BB) {
427 return BFI.getBlockProfileCount(BB).value_or(0);
428 };
429
430 // Collect the sum of execution weight for each probe.
431 ProbeFactorMap ProbeFactors;
432 for (auto &Block : F) {
433 for (auto &I : Block) {
434 if (std::optional<PseudoProbe> Probe = extractProbe(I)) {
436 ProbeFactors[{Probe->Id, Hash}] += BBProfileCount(&Block);
437 }
438 }
439 }
440
441 // Fix up over-counted probes.
442 for (auto &Block : F) {
443 for (auto &I : Block) {
444 if (std::optional<PseudoProbe> Probe = extractProbe(I)) {
446 float Sum = ProbeFactors[{Probe->Id, Hash}];
447 if (Sum != 0)
448 setProbeDistributionFactor(I, BBProfileCount(&Block) / Sum);
449 }
450 }
451 }
452}
453
456 if (UpdatePseudoProbe) {
457 for (auto &F : M) {
458 if (F.isDeclaration())
459 continue;
462 runOnFunction(F, FAM);
463 }
464 }
466}
assume Assume Builder
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
std::string Name
Statically lint checks LLVM IR
Definition: Lint.cpp:746
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
typename CallsiteContextGraph< DerivedCCG, FuncTy, CallTy >::FuncInfo FuncInfo
#define P(N)
FunctionAnalysisManager FAM
const char LLVMTargetMachineRef TM
PassInstrumentationCallbacks PIC
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static cl::opt< bool > UpdatePseudoProbe("update-pseudo-probe", cl::init(true), cl::Hidden, cl::desc("Update pseudo probe distribution factor"))
static cl::opt< bool > VerifyPseudoProbe("verify-pseudo-probe", cl::init(false), cl::Hidden, cl::desc("Do pseudo probe verification"))
static cl::list< std::string > VerifyPseudoProbeFuncList("verify-pseudo-probe-funcs", cl::Hidden, cl::desc("The option to specify the name of the functions to verify."))
static uint64_t computeCallStackHash(const Instruction &Inst)
static uint64_t getCallStackHash(const DILocation *DIL)
This file provides the interface for the pseudo probe implementation for AutoFDO.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Definition: Any.h:28
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator end()
Definition: BasicBlock.h:316
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:245
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:127
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Debug location.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
GUID getGUID() const
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:591
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2558
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:933
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:358
uint32_t getCRC() const
Definition: CRC.h:52
void update(ArrayRef< uint8_t > Data)
Definition: CRC.cpp:103
A node in the call graph.
An SCC of the call graph.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
MDNode * createPseudoProbeDesc(uint64_t GUID, uint64_t Hash, StringRef FName)
Return metadata containing the pseudo probe descriptor for a function.
Definition: MDBuilder.cpp:338
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1399
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
A tuple of MDNodes.
Definition: Metadata.h:1587
This class manages callbacks registration, as well as provides a way for PassInstrumentation to pass ...
void registerAfterPassCallback(CallableT C, bool ToFront=false)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
bool profileIsValid(const Function &F, const FunctionSamples &Samples) const
PseudoProbeManager(const Module &M)
bool moduleIsProbed(const Module &M) const
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
void registerCallbacks(PassInstrumentationCallbacks &PIC)
void runAfterPass(StringRef PassID, Any IR)
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Sample profile pseudo prober.
SampleProfileProber(Function &F, const std::string &CurModuleUniqueId)
void instrumentOneFunc(Function &F, TargetMachine *TM)
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:222
constexpr bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:134
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:78
Triple - Helper class for working with autoconf configuration names.
Definition: Triple.h:44
bool supportsCOMDAT() const
Tests whether the target supports comdat.
Definition: Triple.h:976
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
LLVM Value Representation.
Definition: Value.h:74
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:185
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
Representation of the samples collected for a function.
Definition: SampleProf.h:726
static StringRef getCanonicalFnName(const Function &F)
Return the canonical name for a function, taking into account suffix elision policy attributes.
Definition: SampleProf.h:1036
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1506
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
static constexpr uint64_t PseudoProbeFullDistributionFactor
Definition: PseudoProbe.h:37
void setProbeDistributionFactor(Instruction &Inst, float Factor)
Definition: PseudoProbe.cpp:66
std::string getUniqueModuleId(Module *M)
Produce a unique identifier for this module by taking the MD5 sum of the names of the module's strong...
std::optional< PseudoProbe > extractProbe(const Instruction &Inst)
Definition: PseudoProbe.cpp:49
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
static void computeEHOnlyBlocks(FunctionT &F, DenseSet< BlockT * > &EHBlocks)
Compute a list of blocks that are only reachable via EH paths.
Definition: EHUtils.h:18
Comdat * getOrCreateFunctionComdat(Function &F, Triple &T)
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
std::unordered_map< std::pair< uint64_t, uint64_t >, float, pair_hash< uint64_t, uint64_t > > ProbeFactorMap
uint64_t MD5Hash(StringRef Str)
Helper to compute and return lower 64 bits of the given string's MD5 hash.
Definition: MD5.h:109
constexpr const char * PseudoProbeDescMetadataName
Definition: PseudoProbe.h:25
#define N
static constexpr uint8_t FullDistributionFactor
Definition: PseudoProbe.h:77
static uint32_t packProbeData(uint32_t Index, uint32_t Type, uint32_t Flags, uint32_t Factor)
Definition: PseudoProbe.h:50