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