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
13#include "llvm/Transforms/IPO/SampleProfileProbe.h"
14#include "llvm/ADT/Statistic.h"
15#include "llvm/Analysis/BlockFrequencyInfo.h"
16#include "llvm/Analysis/EHUtils.h"
17#include "llvm/Analysis/LoopInfo.h"
18#include "llvm/IR/BasicBlock.h"
19#include "llvm/IR/DebugInfoMetadata.h"
20#include "llvm/IR/DiagnosticInfo.h"
21#include "llvm/IR/IRBuilder.h"
22#include "llvm/IR/Instruction.h"
23#include "llvm/IR/IntrinsicInst.h"
24#include "llvm/IR/MDBuilder.h"
25#include "llvm/IR/Module.h"
26#include "llvm/IR/PseudoProbe.h"
27#include "llvm/ProfileData/SampleProf.h"
28#include "llvm/Support/CRC.h"
29#include "llvm/Support/CommandLine.h"
30#include "llvm/Target/TargetMachine.h"
31#include "llvm/Transforms/Utils/Instrumentation.h"
32#include "llvm/Transforms/Utils/ModuleUtils.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(Val: false), cl::Hidden,
44 cl::desc("Do pseudo probe verification"));
45
46static cl::list<std::string> VerifyPseudoProbeFuncList(
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(Val: true), cl::Hidden,
52 cl::desc("Update pseudo probe distribution factor"));
53
54static uint64_t getCallStackHash(const DILocation *DIL) {
55 uint64_t Hash = 0;
56 const DILocation *InlinedAt = DIL ? DIL->getInlinedAt() : nullptr;
57 while (InlinedAt) {
58 Hash ^= MD5Hash(Str: std::to_string(val: InlinedAt->getLine()));
59 Hash ^= MD5Hash(Str: std::to_string(val: InlinedAt->getColumn()));
60 auto Name = InlinedAt->getSubprogramLinkageName();
61 Hash ^= MD5Hash(Str: Name);
62 InlinedAt = InlinedAt->getInlinedAt();
63 }
64 return Hash;
65}
66
67static uint64_t computeCallStackHash(const Instruction &Inst) {
68 return getCallStackHash(DIL: 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(
81 VerifyPseudoProbeFuncList.begin(), VerifyPseudoProbeFuncList.end());
82 return VerifyFuncNames.empty() || VerifyFuncNames.count(x: F->getName().str());
83}
84
85void PseudoProbeVerifier::registerCallbacks(PassInstrumentationCallbacks &PIC) {
86 if (VerifyPseudoProbe) {
87 PIC.registerAfterPassCallback(
88 C: [this](StringRef P, Any IR, const PreservedAnalyses &) {
89 this->runAfterPass(PassID: P, IR);
90 });
91 }
92}
93
94// Callback to run after each transformation for the new pass manager.
95void PseudoProbeVerifier::runAfterPass(StringRef PassID, Any IR) {
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 *>(Value: &IR))
100 runAfterPass(M: *M);
101 else if (const auto **F = llvm::any_cast<const Function *>(Value: &IR))
102 runAfterPass(F: *F);
103 else if (const auto **C = llvm::any_cast<const LazyCallGraph::SCC *>(Value: &IR))
104 runAfterPass(C: *C);
105 else if (const auto **L = llvm::any_cast<const Loop *>(Value: &IR))
106 runAfterPass(L: *L);
107 else
108 llvm_unreachable("Unknown IR unit");
109}
110
111void PseudoProbeVerifier::runAfterPass(const Module *M) {
112 for (const Function &F : *M)
113 runAfterPass(F: &F);
114}
115
116void PseudoProbeVerifier::runAfterPass(const LazyCallGraph::SCC *C) {
117 for (const LazyCallGraph::Node &N : *C)
118 runAfterPass(F: &N.getFunction());
119}
120
121void PseudoProbeVerifier::runAfterPass(const Function *F) {
122 if (!shouldVerifyFunction(F))
123 return;
124 ProbeFactorMap ProbeFactors;
125 for (const auto &BB : *F)
126 collectProbeFactors(BB: &BB, ProbeFactors);
127 verifyProbeFactors(F, ProbeFactors);
128}
129
130void PseudoProbeVerifier::runAfterPass(const Loop *L) {
131 const Function *F = L->getHeader()->getParent();
132 runAfterPass(F);
133}
134
135void PseudoProbeVerifier::collectProbeFactors(const BasicBlock *Block,
136 ProbeFactorMap &ProbeFactors) {
137 for (const auto &I : *Block) {
138 if (std::optional<PseudoProbe> Probe = extractProbe(Inst: I)) {
139 uint64_t Hash = computeCallStackHash(Inst: 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 auto [It, Inserted] = PrevProbeFactors.try_emplace(k: I.first);
152 if (!Inserted) {
153 float PrevProbeFactor = It->second;
154 if (std::abs(x: CurProbeFactor - PrevProbeFactor) >
155 DistributionFactorVariance) {
156 if (!BannerPrinted) {
157 dbgs() << "Function " << F->getName() << ":\n";
158 BannerPrinted = true;
159 }
160 dbgs() << "Probe " << I.first.first << "\tprevious factor "
161 << format(Fmt: "%0.2f", Vals: PrevProbeFactor) << "\tcurrent factor "
162 << format(Fmt: "%0.2f", Vals: CurProbeFactor) << "\n";
163 }
164 }
165
166 // Update
167 It->second = I.second;
168 }
169}
170
171SampleProfileProber::SampleProfileProber(Function &Func) : F(&Func) {
172 BlockProbeIds.clear();
173 CallProbeIds.clear();
174 LastProbeId = (uint32_t)PseudoProbeReservedId::Last;
175
176 DenseSet<BasicBlock *> BlocksToIgnore;
177 DenseSet<BasicBlock *> BlocksAndCallsToIgnore;
178 computeBlocksToIgnore(BlocksToIgnore, BlocksAndCallsToIgnore);
179
180 computeProbeId(BlocksToIgnore, BlocksAndCallsToIgnore);
181 computeCFGHash(BlocksToIgnore);
182}
183
184// Two purposes to compute the blocks to ignore:
185// 1. Reduce the IR size.
186// 2. Make the instrumentation(checksum) stable. e.g. the frondend may
187// generate unstable IR while optimizing nounwind attribute, some versions are
188// optimized with the call-to-invoke conversion, while other versions do not.
189// This discrepancy in probe ID could cause profile mismatching issues.
190// Note that those ignored blocks are either cold blocks or new split blocks
191// whose original blocks are instrumented, so it shouldn't degrade the profile
192// quality.
193void SampleProfileProber::computeBlocksToIgnore(
194 DenseSet<BasicBlock *> &BlocksToIgnore,
195 DenseSet<BasicBlock *> &BlocksAndCallsToIgnore) {
196 // Ignore the cold EH and unreachable blocks and calls.
197 computeEHOnlyBlocks(F&: *F, EHBlocks&: BlocksAndCallsToIgnore);
198 findUnreachableBlocks(BlocksToIgnore&: BlocksAndCallsToIgnore);
199
200 BlocksToIgnore.insert_range(R&: BlocksAndCallsToIgnore);
201
202 // Handle the call-to-invoke conversion case: make sure that the probe id and
203 // callsite id are consistent before and after the block split. For block
204 // probe, we only keep the head block probe id and ignore the block ids of the
205 // normal dests. For callsite probe, it's different to block probe, there is
206 // no additional callsite in the normal dests, so we don't ignore the
207 // callsites.
208 findInvokeNormalDests(InvokeNormalDests&: BlocksToIgnore);
209}
210
211// Unreachable blocks and calls are always cold, ignore them.
212void SampleProfileProber::findUnreachableBlocks(
213 DenseSet<BasicBlock *> &BlocksToIgnore) {
214 for (auto &BB : *F) {
215 if (&BB != &F->getEntryBlock() && pred_size(BB: &BB) == 0)
216 BlocksToIgnore.insert(V: &BB);
217 }
218}
219
220// In call-to-invoke conversion, basic block can be split into multiple blocks,
221// only instrument probe in the head block, ignore the normal dests.
222void SampleProfileProber::findInvokeNormalDests(
223 DenseSet<BasicBlock *> &InvokeNormalDests) {
224 for (auto &BB : *F) {
225 auto *TI = BB.getTerminator();
226 if (auto *II = dyn_cast<InvokeInst>(Val: TI)) {
227 auto *ND = II->getNormalDest();
228 InvokeNormalDests.insert(V: ND);
229
230 // The normal dest and the try/catch block are connected by an
231 // unconditional branch.
232 while (pred_size(BB: ND) == 1) {
233 auto *Pred = *pred_begin(BB: ND);
234 if (succ_size(BB: Pred) == 1) {
235 InvokeNormalDests.insert(V: Pred);
236 ND = Pred;
237 } else
238 break;
239 }
240 }
241 }
242}
243
244// The call-to-invoke conversion splits the original block into a list of block,
245// we need to compute the hash using the original block's successors to keep the
246// CFG Hash consistent. For a given head block, we keep searching the
247// succesor(normal dest or unconditional branch dest) to find the tail block,
248// the tail block's successors are the original block's successors.
249const Instruction *SampleProfileProber::getOriginalTerminator(
250 const BasicBlock *Head, const DenseSet<BasicBlock *> &BlocksToIgnore) {
251 auto *TI = Head->getTerminator();
252 if (auto *II = dyn_cast<InvokeInst>(Val: TI)) {
253 return getOriginalTerminator(Head: II->getNormalDest(), BlocksToIgnore);
254 } else if (succ_size(BB: Head) == 1 &&
255 BlocksToIgnore.contains(V: *succ_begin(BB: Head))) {
256 // Go to the unconditional branch dest.
257 return getOriginalTerminator(Head: *succ_begin(BB: Head), BlocksToIgnore);
258 }
259 return TI;
260}
261
262// Compute Hash value for the CFG: the lower 32 bits are CRC32 of the index
263// value of each BB in the CFG. The higher 32 bits record the number of edges
264// preceded by the number of indirect calls.
265// This is derived from FuncPGOInstrumentation<Edge, BBInfo>::computeCFGHash().
266void SampleProfileProber::computeCFGHash(
267 const DenseSet<BasicBlock *> &BlocksToIgnore) {
268 std::vector<uint8_t> Indexes;
269 JamCRC JC;
270 for (auto &BB : *F) {
271 if (BlocksToIgnore.contains(V: &BB))
272 continue;
273
274 auto *TI = getOriginalTerminator(Head: &BB, BlocksToIgnore);
275 for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) {
276 auto *Succ = TI->getSuccessor(Idx: I);
277 auto Index = getBlockId(BB: Succ);
278 // Ingore ignored-block(zero ID) to avoid unstable checksum.
279 if (Index == 0)
280 continue;
281 for (int J = 0; J < 4; J++)
282 Indexes.push_back(x: (uint8_t)(Index >> (J * 8)));
283 }
284 }
285
286 JC.update(Data: Indexes);
287
288 FunctionHash = (uint64_t)CallProbeIds.size() << 48 |
289 (uint64_t)Indexes.size() << 32 | JC.getCRC();
290 // Reserve bit 60-63 for other information purpose.
291 FunctionHash &= 0x0FFFFFFFFFFFFFFF;
292 assert(FunctionHash && "Function checksum should not be zero");
293 LLVM_DEBUG(dbgs() << "\nFunction Hash Computation for " << F->getName()
294 << ":\n"
295 << " CRC = " << JC.getCRC() << ", Edges = "
296 << Indexes.size() << ", ICSites = " << CallProbeIds.size()
297 << ", Hash = " << FunctionHash << "\n");
298}
299
300void SampleProfileProber::computeProbeId(
301 const DenseSet<BasicBlock *> &BlocksToIgnore,
302 const DenseSet<BasicBlock *> &BlocksAndCallsToIgnore) {
303 LLVMContext &Ctx = F->getContext();
304 Module *M = F->getParent();
305
306 for (auto &BB : *F) {
307 if (!BlocksToIgnore.contains(V: &BB))
308 BlockProbeIds[&BB] = ++LastProbeId;
309
310 if (BlocksAndCallsToIgnore.contains(V: &BB))
311 continue;
312 for (auto &I : BB) {
313 if (!isa<CallBase>(Val: I) || isa<IntrinsicInst>(Val: &I))
314 continue;
315
316 // The current implementation uses the lower 16 bits of the discriminator
317 // so anything larger than 0xFFFF will be ignored.
318 if (LastProbeId >= 0xFFFF) {
319 std::string Msg = "Pseudo instrumentation incomplete for " +
320 std::string(F->getName()) + " because it's too large";
321 Ctx.diagnose(
322 DI: DiagnosticInfoSampleProfile(M->getName().data(), Msg, DS_Warning));
323 return;
324 }
325
326 CallProbeIds[&I] = ++LastProbeId;
327 }
328 }
329}
330
331uint32_t SampleProfileProber::getBlockId(const BasicBlock *BB) const {
332 auto I = BlockProbeIds.find(x: const_cast<BasicBlock *>(BB));
333 return I == BlockProbeIds.end() ? 0 : I->second;
334}
335
336uint32_t SampleProfileProber::getCallsiteId(const Instruction *Call) const {
337 auto Iter = CallProbeIds.find(x: const_cast<Instruction *>(Call));
338 return Iter == CallProbeIds.end() ? 0 : Iter->second;
339}
340
341void SampleProfileProber::instrumentOneFunc(Function &F, TargetMachine *TM) {
342 Module *M = F.getParent();
343 MDBuilder MDB(F.getContext());
344 // Since the GUID from probe desc and inline stack are computed separately, we
345 // need to make sure their names are consistent, so here also use the name
346 // from debug info.
347 StringRef FName = F.getName();
348 if (auto *SP = F.getSubprogram()) {
349 FName = SP->getLinkageName();
350 if (FName.empty())
351 FName = SP->getName();
352 }
353 uint64_t Guid = Function::getGUIDAssumingExternalLinkage(GlobalName: FName);
354
355 // Assign an artificial debug line to a probe that doesn't come with a real
356 // line. A probe not having a debug line will get an incomplete inline
357 // context. This will cause samples collected on the probe to be counted
358 // into the base profile instead of a context profile. The line number
359 // itself is not important though.
360 auto AssignDebugLoc = [&](Instruction *I) {
361 assert((isa<PseudoProbeInst>(I) || isa<CallBase>(I)) &&
362 "Expecting pseudo probe or call instructions");
363 if (!I->getDebugLoc()) {
364 if (auto *SP = F.getSubprogram()) {
365 auto DIL = DILocation::get(Context&: SP->getContext(), Line: 0, Column: 0, Scope: SP);
366 I->setDebugLoc(DIL);
367 ArtificialDbgLine++;
368 LLVM_DEBUG({
369 dbgs() << "\nIn Function " << F.getName()
370 << " Probe gets an artificial debug line\n";
371 I->dump();
372 });
373 }
374 }
375 };
376
377 // Probe basic blocks.
378 for (auto &I : BlockProbeIds) {
379 BasicBlock *BB = I.first;
380 uint32_t Index = I.second;
381 // Insert a probe before an instruction with a valid debug line number which
382 // will be assigned to the probe. The line number will be used later to
383 // model the inline context when the probe is inlined into other functions.
384 // Debug instructions, phi nodes and lifetime markers do not have an valid
385 // line number. Real instructions generated by optimizations may not come
386 // with a line number either.
387 auto HasValidDbgLine = [](Instruction *J) {
388 return !isa<PHINode>(Val: J) && !J->isLifetimeStartOrEnd() && J->getDebugLoc();
389 };
390
391 Instruction *J = &*BB->getFirstInsertionPt();
392 while (J != BB->getTerminator() && !HasValidDbgLine(J)) {
393 J = J->getNextNode();
394 }
395
396 IRBuilder<> Builder(J);
397 assert(Builder.GetInsertPoint() != BB->end() &&
398 "Cannot get the probing point");
399 Function *ProbeFn =
400 llvm::Intrinsic::getOrInsertDeclaration(M, id: Intrinsic::pseudoprobe);
401 Value *Args[] = {Builder.getInt64(C: Guid), Builder.getInt64(C: Index),
402 Builder.getInt32(C: 0),
403 Builder.getInt64(C: PseudoProbeFullDistributionFactor)};
404 auto *Probe = Builder.CreateCall(Callee: ProbeFn, Args);
405 AssignDebugLoc(Probe);
406 // Reset the dwarf discriminator if the debug location comes with any. The
407 // discriminator field may be used by FS-AFDO later in the pipeline.
408 if (auto DIL = Probe->getDebugLoc()) {
409 if (DIL->getDiscriminator()) {
410 DIL = DIL->cloneWithDiscriminator(Discriminator: 0);
411 Probe->setDebugLoc(DIL);
412 }
413 }
414 }
415
416 // Probe both direct calls and indirect calls. Direct calls are probed so that
417 // their probe ID can be used as an call site identifier to represent a
418 // calling context.
419 for (auto &I : CallProbeIds) {
420 auto *Call = I.first;
421 uint32_t Index = I.second;
422 uint32_t Type = cast<CallBase>(Val: Call)->getCalledFunction()
423 ? (uint32_t)PseudoProbeType::DirectCall
424 : (uint32_t)PseudoProbeType::IndirectCall;
425 AssignDebugLoc(Call);
426 if (auto DIL = Call->getDebugLoc()) {
427 // Levarge the 32-bit discriminator field of debug data to store the ID
428 // and type of a callsite probe. This gets rid of the dependency on
429 // plumbing a customized metadata through the codegen pipeline.
430 uint32_t V = PseudoProbeDwarfDiscriminator::packProbeData(
431 Index, Type, Flags: 0, Factor: PseudoProbeDwarfDiscriminator::FullDistributionFactor,
432 DwarfBaseDiscriminator: DIL->getBaseDiscriminator());
433 DIL = DIL->cloneWithDiscriminator(Discriminator: V);
434 Call->setDebugLoc(DIL);
435 }
436 }
437
438 // Create module-level metadata that contains function info necessary to
439 // synthesize probe-based sample counts, which are
440 // - FunctionGUID
441 // - FunctionHash.
442 // - FunctionName
443 auto Hash = getFunctionHash();
444 auto *MD = MDB.createPseudoProbeDesc(GUID: Guid, Hash, FName);
445 auto *NMD = M->getNamedMetadata(Name: PseudoProbeDescMetadataName);
446 assert(NMD && "llvm.pseudo_probe_desc should be pre-created");
447 NMD->addOperand(M: MD);
448}
449
450PreservedAnalyses SampleProfileProbePass::run(Module &M,
451 ModuleAnalysisManager &AM) {
452 // Create the pseudo probe desc metadata beforehand.
453 // Note that modules with only data but no functions will require this to
454 // be set up so that they will be known as probed later.
455 M.getOrInsertNamedMetadata(Name: PseudoProbeDescMetadataName);
456
457 for (auto &F : M) {
458 if (F.isDeclaration())
459 continue;
460 SampleProfileProber ProbeManager(F);
461 ProbeManager.instrumentOneFunc(F, TM);
462 }
463
464 return PreservedAnalyses::none();
465}
466
467void PseudoProbeUpdatePass::runOnFunction(Function &F,
468 FunctionAnalysisManager &FAM) {
469 BlockFrequencyInfo &BFI = FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
470 auto BBProfileCount = [&BFI](BasicBlock *BB) {
471 return BFI.getBlockProfileCount(BB).value_or(u: 0);
472 };
473
474 // Collect the sum of execution weight for each probe.
475 ProbeFactorMap ProbeFactors;
476 for (auto &Block : F) {
477 for (auto &I : Block) {
478 if (std::optional<PseudoProbe> Probe = extractProbe(Inst: I)) {
479 uint64_t Hash = computeCallStackHash(Inst: I);
480 ProbeFactors[{Probe->Id, Hash}] += BBProfileCount(&Block);
481 }
482 }
483 }
484
485 // Fix up over-counted probes.
486 for (auto &Block : F) {
487 for (auto &I : Block) {
488 if (std::optional<PseudoProbe> Probe = extractProbe(Inst: I)) {
489 uint64_t Hash = computeCallStackHash(Inst: I);
490 float Sum = ProbeFactors[{Probe->Id, Hash}];
491 if (Sum != 0)
492 setProbeDistributionFactor(Inst&: I, Factor: BBProfileCount(&Block) / Sum);
493 }
494 }
495 }
496}
497
498PreservedAnalyses PseudoProbeUpdatePass::run(Module &M,
499 ModuleAnalysisManager &AM) {
500 if (UpdatePseudoProbe) {
501 for (auto &F : M) {
502 if (F.isDeclaration())
503 continue;
504 FunctionAnalysisManager &FAM =
505 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
506 runOnFunction(F, FAM);
507 }
508 }
509 return PreservedAnalyses::none();
510}
511