LLVM 19.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"
22#include "llvm/IR/IRBuilder.h"
23#include "llvm/IR/Instruction.h"
25#include "llvm/IR/MDBuilder.h"
26#include "llvm/IR/PseudoProbe.h"
28#include "llvm/Support/CRC.h"
33#include <unordered_set>
34#include <vector>
35
36using namespace llvm;
37#define DEBUG_TYPE "pseudo-probe"
38
39STATISTIC(ArtificialDbgLine,
40 "Number of probes that have an artificial debug line");
41
42static cl::opt<bool>
43 VerifyPseudoProbe("verify-pseudo-probe", cl::init(false), cl::Hidden,
44 cl::desc("Do pseudo probe verification"));
45
47 "verify-pseudo-probe-funcs", cl::Hidden,
48 cl::desc("The option to specify the name of the functions to verify."));
49
50static cl::opt<bool>
51 UpdatePseudoProbe("update-pseudo-probe", cl::init(true), cl::Hidden,
52 cl::desc("Update pseudo probe distribution factor"));
53
55 uint64_t Hash = 0;
56 const DILocation *InlinedAt = DIL ? DIL->getInlinedAt() : nullptr;
57 while (InlinedAt) {
58 Hash ^= MD5Hash(std::to_string(InlinedAt->getLine()));
59 Hash ^= MD5Hash(std::to_string(InlinedAt->getColumn()));
60 auto Name = InlinedAt->getSubprogramLinkageName();
61 Hash ^= MD5Hash(Name);
62 InlinedAt = InlinedAt->getInlinedAt();
63 }
64 return Hash;
65}
66
68 return getCallStackHash(Inst.getDebugLoc());
69}
70
71bool PseudoProbeVerifier::shouldVerifyFunction(const Function *F) {
72 // Skip function declaration.
73 if (F->isDeclaration())
74 return false;
75 // Skip function that will not be emitted into object file. The prevailing
76 // defintion will be verified instead.
77 if (F->hasAvailableExternallyLinkage())
78 return false;
79 // Do a name matching.
80 static std::unordered_set<std::string> VerifyFuncNames(
82 return VerifyFuncNames.empty() || VerifyFuncNames.count(F->getName().str());
83}
84
88 [this](StringRef P, Any IR, const PreservedAnalyses &) {
89 this->runAfterPass(P, IR);
90 });
91 }
92}
93
94// Callback to run after each transformation for the new pass manager.
96 std::string Banner =
97 "\n*** Pseudo Probe Verification After " + PassID.str() + " ***\n";
98 dbgs() << Banner;
99 if (const auto **M = llvm::any_cast<const Module *>(&IR))
100 runAfterPass(*M);
101 else if (const auto **F = llvm::any_cast<const Function *>(&IR))
102 runAfterPass(*F);
103 else if (const auto **C = llvm::any_cast<const LazyCallGraph::SCC *>(&IR))
104 runAfterPass(*C);
105 else if (const auto **L = llvm::any_cast<const Loop *>(&IR))
106 runAfterPass(*L);
107 else
108 llvm_unreachable("Unknown IR unit");
109}
110
112 for (const Function &F : *M)
113 runAfterPass(&F);
114}
115
117 for (const LazyCallGraph::Node &N : *C)
118 runAfterPass(&N.getFunction());
119}
120
122 if (!shouldVerifyFunction(F))
123 return;
124 ProbeFactorMap ProbeFactors;
125 for (const auto &BB : *F)
126 collectProbeFactors(&BB, ProbeFactors);
127 verifyProbeFactors(F, ProbeFactors);
128}
129
131 const Function *F = L->getHeader()->getParent();
133}
134
135void PseudoProbeVerifier::collectProbeFactors(const BasicBlock *Block,
136 ProbeFactorMap &ProbeFactors) {
137 for (const auto &I : *Block) {
138 if (std::optional<PseudoProbe> Probe = extractProbe(I)) {
140 ProbeFactors[{Probe->Id, Hash}] += Probe->Factor;
141 }
142 }
143}
144
145void PseudoProbeVerifier::verifyProbeFactors(
146 const Function *F, const ProbeFactorMap &ProbeFactors) {
147 bool BannerPrinted = false;
148 auto &PrevProbeFactors = FunctionProbeFactors[F->getName()];
149 for (const auto &I : ProbeFactors) {
150 float CurProbeFactor = I.second;
151 if (PrevProbeFactors.count(I.first)) {
152 float PrevProbeFactor = PrevProbeFactors[I.first];
153 if (std::abs(CurProbeFactor - PrevProbeFactor) >
154 DistributionFactorVariance) {
155 if (!BannerPrinted) {
156 dbgs() << "Function " << F->getName() << ":\n";
157 BannerPrinted = true;
158 }
159 dbgs() << "Probe " << I.first.first << "\tprevious factor "
160 << format("%0.2f", PrevProbeFactor) << "\tcurrent factor "
161 << format("%0.2f", CurProbeFactor) << "\n";
162 }
163 }
164
165 // Update
166 PrevProbeFactors[I.first] = I.second;
167 }
168}
169
171 const std::string &CurModuleUniqueId)
172 : F(&Func), CurModuleUniqueId(CurModuleUniqueId) {
173 BlockProbeIds.clear();
174 CallProbeIds.clear();
176 computeProbeIdForBlocks();
177 computeProbeIdForCallsites();
178 computeCFGHash();
179}
180
181// Compute Hash value for the CFG: the lower 32 bits are CRC32 of the index
182// value of each BB in the CFG. The higher 32 bits record the number of edges
183// preceded by the number of indirect calls.
184// This is derived from FuncPGOInstrumentation<Edge, BBInfo>::computeCFGHash().
185void SampleProfileProber::computeCFGHash() {
186 std::vector<uint8_t> Indexes;
187 JamCRC JC;
188 for (auto &BB : *F) {
189 for (BasicBlock *Succ : successors(&BB)) {
190 auto Index = getBlockId(Succ);
191 for (int J = 0; J < 4; J++)
192 Indexes.push_back((uint8_t)(Index >> (J * 8)));
193 }
194 }
195
196 JC.update(Indexes);
197
198 FunctionHash = (uint64_t)CallProbeIds.size() << 48 |
199 (uint64_t)Indexes.size() << 32 | JC.getCRC();
200 // Reserve bit 60-63 for other information purpose.
201 FunctionHash &= 0x0FFFFFFFFFFFFFFF;
202 assert(FunctionHash && "Function checksum should not be zero");
203 LLVM_DEBUG(dbgs() << "\nFunction Hash Computation for " << F->getName()
204 << ":\n"
205 << " CRC = " << JC.getCRC() << ", Edges = "
206 << Indexes.size() << ", ICSites = " << CallProbeIds.size()
207 << ", Hash = " << FunctionHash << "\n");
208}
209
210void SampleProfileProber::computeProbeIdForBlocks() {
211 DenseSet<BasicBlock *> KnownColdBlocks;
212 computeEHOnlyBlocks(*F, KnownColdBlocks);
213 // Insert pseudo probe to non-cold blocks only. This will reduce IR size as
214 // well as the binary size while retaining the profile quality.
215 for (auto &BB : *F) {
216 ++LastProbeId;
217 if (!KnownColdBlocks.contains(&BB))
218 BlockProbeIds[&BB] = LastProbeId;
219 }
220}
221
222void SampleProfileProber::computeProbeIdForCallsites() {
223 LLVMContext &Ctx = F->getContext();
224 Module *M = F->getParent();
225
226 for (auto &BB : *F) {
227 for (auto &I : BB) {
228 if (!isa<CallBase>(I))
229 continue;
230 if (isa<IntrinsicInst>(&I))
231 continue;
232
233 // The current implementation uses the lower 16 bits of the discriminator
234 // so anything larger than 0xFFFF will be ignored.
235 if (LastProbeId >= 0xFFFF) {
236 std::string Msg = "Pseudo instrumentation incomplete for " +
237 std::string(F->getName()) + " because it's too large";
238 Ctx.diagnose(
239 DiagnosticInfoSampleProfile(M->getName().data(), Msg, DS_Warning));
240 return;
241 }
242
243 CallProbeIds[&I] = ++LastProbeId;
244 }
245 }
246}
247
248uint32_t SampleProfileProber::getBlockId(const BasicBlock *BB) const {
249 auto I = BlockProbeIds.find(const_cast<BasicBlock *>(BB));
250 return I == BlockProbeIds.end() ? 0 : I->second;
251}
252
253uint32_t SampleProfileProber::getCallsiteId(const Instruction *Call) const {
254 auto Iter = CallProbeIds.find(const_cast<Instruction *>(Call));
255 return Iter == CallProbeIds.end() ? 0 : Iter->second;
256}
257
259 Module *M = F.getParent();
260 MDBuilder MDB(F.getContext());
261 // Since the GUID from probe desc and inline stack are computed seperately, we
262 // need to make sure their names are consistent, so here also use the name
263 // from debug info.
264 StringRef FName = F.getName();
265 if (auto *SP = F.getSubprogram()) {
266 FName = SP->getLinkageName();
267 if (FName.empty())
268 FName = SP->getName();
269 }
270 uint64_t Guid = Function::getGUID(FName);
271
272 // Assign an artificial debug line to a probe that doesn't come with a real
273 // line. A probe not having a debug line will get an incomplete inline
274 // context. This will cause samples collected on the probe to be counted
275 // into the base profile instead of a context profile. The line number
276 // itself is not important though.
277 auto AssignDebugLoc = [&](Instruction *I) {
278 assert((isa<PseudoProbeInst>(I) || isa<CallBase>(I)) &&
279 "Expecting pseudo probe or call instructions");
280 if (!I->getDebugLoc()) {
281 if (auto *SP = F.getSubprogram()) {
282 auto DIL = DILocation::get(SP->getContext(), 0, 0, SP);
283 I->setDebugLoc(DIL);
284 ArtificialDbgLine++;
285 LLVM_DEBUG({
286 dbgs() << "\nIn Function " << F.getName()
287 << " Probe gets an artificial debug line\n";
288 I->dump();
289 });
290 }
291 }
292 };
293
294 // Probe basic blocks.
295 for (auto &I : BlockProbeIds) {
296 BasicBlock *BB = I.first;
297 uint32_t Index = I.second;
298 // Insert a probe before an instruction with a valid debug line number which
299 // will be assigned to the probe. The line number will be used later to
300 // model the inline context when the probe is inlined into other functions.
301 // Debug instructions, phi nodes and lifetime markers do not have an valid
302 // line number. Real instructions generated by optimizations may not come
303 // with a line number either.
304 auto HasValidDbgLine = [](Instruction *J) {
305 return !isa<PHINode>(J) && !isa<DbgInfoIntrinsic>(J) &&
306 !J->isLifetimeStartOrEnd() && J->getDebugLoc();
307 };
308
309 Instruction *J = &*BB->getFirstInsertionPt();
310 while (J != BB->getTerminator() && !HasValidDbgLine(J)) {
311 J = J->getNextNode();
312 }
313
314 IRBuilder<> Builder(J);
315 assert(Builder.GetInsertPoint() != BB->end() &&
316 "Cannot get the probing point");
317 Function *ProbeFn =
318 llvm::Intrinsic::getDeclaration(M, Intrinsic::pseudoprobe);
319 Value *Args[] = {Builder.getInt64(Guid), Builder.getInt64(Index),
320 Builder.getInt32(0),
322 auto *Probe = Builder.CreateCall(ProbeFn, Args);
323 AssignDebugLoc(Probe);
324 // Reset the dwarf discriminator if the debug location comes with any. The
325 // discriminator field may be used by FS-AFDO later in the pipeline.
326 if (auto DIL = Probe->getDebugLoc()) {
327 if (DIL->getDiscriminator()) {
328 DIL = DIL->cloneWithDiscriminator(0);
329 Probe->setDebugLoc(DIL);
330 }
331 }
332 }
333
334 // Probe both direct calls and indirect calls. Direct calls are probed so that
335 // their probe ID can be used as an call site identifier to represent a
336 // calling context.
337 for (auto &I : CallProbeIds) {
338 auto *Call = I.first;
339 uint32_t Index = I.second;
340 uint32_t Type = cast<CallBase>(Call)->getCalledFunction()
343 AssignDebugLoc(Call);
344 if (auto DIL = Call->getDebugLoc()) {
345 // Levarge the 32-bit discriminator field of debug data to store the ID
346 // and type of a callsite probe. This gets rid of the dependency on
347 // plumbing a customized metadata through the codegen pipeline.
349 Index, Type, 0,
351 DIL = DIL->cloneWithDiscriminator(V);
352 Call->setDebugLoc(DIL);
353 }
354 }
355
356 // Create module-level metadata that contains function info necessary to
357 // synthesize probe-based sample counts, which are
358 // - FunctionGUID
359 // - FunctionHash.
360 // - FunctionName
361 auto Hash = getFunctionHash();
362 auto *MD = MDB.createPseudoProbeDesc(Guid, Hash, FName);
363 auto *NMD = M->getNamedMetadata(PseudoProbeDescMetadataName);
364 assert(NMD && "llvm.pseudo_probe_desc should be pre-created");
365 NMD->addOperand(MD);
366}
367
370 auto ModuleId = getUniqueModuleId(&M);
371 // Create the pseudo probe desc metadata beforehand.
372 // Note that modules with only data but no functions will require this to
373 // be set up so that they will be known as probed later.
374 M.getOrInsertNamedMetadata(PseudoProbeDescMetadataName);
375
376 for (auto &F : M) {
377 if (F.isDeclaration())
378 continue;
379 SampleProfileProber ProbeManager(F, ModuleId);
380 ProbeManager.instrumentOneFunc(F, TM);
381 }
382
384}
385
386void PseudoProbeUpdatePass::runOnFunction(Function &F,
389 auto BBProfileCount = [&BFI](BasicBlock *BB) {
390 return BFI.getBlockProfileCount(BB).value_or(0);
391 };
392
393 // Collect the sum of execution weight for each probe.
394 ProbeFactorMap ProbeFactors;
395 for (auto &Block : F) {
396 for (auto &I : Block) {
397 if (std::optional<PseudoProbe> Probe = extractProbe(I)) {
399 ProbeFactors[{Probe->Id, Hash}] += BBProfileCount(&Block);
400 }
401 }
402 }
403
404 // Fix up over-counted probes.
405 for (auto &Block : F) {
406 for (auto &I : Block) {
407 if (std::optional<PseudoProbe> Probe = extractProbe(I)) {
409 float Sum = ProbeFactors[{Probe->Id, Hash}];
410 if (Sum != 0)
411 setProbeDistributionFactor(I, BBProfileCount(&Block) / Sum);
412 }
413 }
414 }
415}
416
419 if (UpdatePseudoProbe) {
420 for (auto &F : M) {
421 if (F.isDeclaration())
422 continue;
425 runOnFunction(F, FAM);
426 }
427 }
429}
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
Legalize the Machine IR a function s Machine IR
Definition: Legalizer.cpp:81
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#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:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
Definition: Any.h:28
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator end()
Definition: BasicBlock.h:451
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:454
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:229
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
Diagnostic information for the sample profiler.
GUID getGUID() const
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:594
BasicBlock::iterator GetInsertPoint() const
Definition: IRBuilder.h:175
ConstantInt * getInt64(uint64_t C)
Get a constant 64-bit value.
Definition: IRBuilder.h:485
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:480
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args=std::nullopt, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2395
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2649
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:658
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:452
uint32_t getCRC() const
Definition: CRC.h:52
void update(ArrayRef< uint8_t > Data)
Definition: CRC.cpp:103
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
void diagnose(const DiagnosticInfo &DI)
Report a message to the currently installed diagnostic handler.
A node in the call graph.
An SCC of the call graph.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
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:1541
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
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: Analysis.h:109
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: Analysis.h:112
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:76
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:316
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
const CustomOperand< const MCSubtargetInfo & > Msg[]
@ 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:1447
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
uint64_t MD5Hash(const FunctionId &Obj)
Definition: FunctionId.h:167
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
static constexpr uint64_t PseudoProbeFullDistributionFactor
Definition: PseudoProbe.h:38
auto successors(const MachineBasicBlock *BB)
void setProbeDistributionFactor(Instruction &Inst, float Factor)
Definition: PseudoProbe.cpp:76
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:56
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
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:125
std::unordered_map< std::pair< uint64_t, uint64_t >, float, pair_hash< uint64_t, uint64_t > > ProbeFactorMap
@ DS_Warning
constexpr const char * PseudoProbeDescMetadataName
Definition: PseudoProbe.h:25
#define N
static constexpr uint8_t FullDistributionFactor
Definition: PseudoProbe.h:78
static uint32_t packProbeData(uint32_t Index, uint32_t Type, uint32_t Flags, uint32_t Factor)
Definition: PseudoProbe.h:51