xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/IPO/SampleProfileProbe.cpp (revision 833a452e9f082a7982a31c21f0da437dbbe0a39d)
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/TargetLibraryInfo.h"
17 #include "llvm/IR/BasicBlock.h"
18 #include "llvm/IR/CFG.h"
19 #include "llvm/IR/Constant.h"
20 #include "llvm/IR/Constants.h"
21 #include "llvm/IR/DebugInfoMetadata.h"
22 #include "llvm/IR/GlobalValue.h"
23 #include "llvm/IR/GlobalVariable.h"
24 #include "llvm/IR/IRBuilder.h"
25 #include "llvm/IR/Instruction.h"
26 #include "llvm/IR/MDBuilder.h"
27 #include "llvm/ProfileData/SampleProf.h"
28 #include "llvm/Support/CRC.h"
29 #include "llvm/Support/CommandLine.h"
30 #include "llvm/Transforms/Instrumentation.h"
31 #include "llvm/Transforms/Utils/ModuleUtils.h"
32 #include <unordered_set>
33 #include <vector>
34 
35 using namespace llvm;
36 #define DEBUG_TYPE "sample-profile-probe"
37 
38 STATISTIC(ArtificialDbgLine,
39           "Number of probes that have an artificial debug line");
40 
41 static cl::opt<bool>
42     VerifyPseudoProbe("verify-pseudo-probe", cl::init(false), cl::Hidden,
43                       cl::desc("Do pseudo probe verification"));
44 
45 static cl::list<std::string> VerifyPseudoProbeFuncList(
46     "verify-pseudo-probe-funcs", cl::Hidden,
47     cl::desc("The option to specify the name of the functions to verify."));
48 
49 static cl::opt<bool>
50     UpdatePseudoProbe("update-pseudo-probe", cl::init(true), cl::Hidden,
51                       cl::desc("Update pseudo probe distribution factor"));
52 
53 static uint64_t getCallStackHash(const DILocation *DIL) {
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     const DISubprogram *SP = InlinedAt->getScope()->getSubprogram();
60     // Use linkage name for C++ if possible.
61     auto Name = SP->getLinkageName();
62     if (Name.empty())
63       Name = SP->getName();
64     Hash ^= MD5Hash(Name);
65     InlinedAt = InlinedAt->getInlinedAt();
66   }
67   return Hash;
68 }
69 
70 static uint64_t computeCallStackHash(const Instruction &Inst) {
71   return getCallStackHash(Inst.getDebugLoc());
72 }
73 
74 bool PseudoProbeVerifier::shouldVerifyFunction(const Function *F) {
75   // Skip function declaration.
76   if (F->isDeclaration())
77     return false;
78   // Skip function that will not be emitted into object file. The prevailing
79   // defintion will be verified instead.
80   if (F->hasAvailableExternallyLinkage())
81     return false;
82   // Do a name matching.
83   static std::unordered_set<std::string> VerifyFuncNames(
84       VerifyPseudoProbeFuncList.begin(), VerifyPseudoProbeFuncList.end());
85   return VerifyFuncNames.empty() || VerifyFuncNames.count(F->getName().str());
86 }
87 
88 void PseudoProbeVerifier::registerCallbacks(PassInstrumentationCallbacks &PIC) {
89   if (VerifyPseudoProbe) {
90     PIC.registerAfterPassCallback(
91         [this](StringRef P, Any IR, const PreservedAnalyses &) {
92           this->runAfterPass(P, IR);
93         });
94   }
95 }
96 
97 // Callback to run after each transformation for the new pass manager.
98 void PseudoProbeVerifier::runAfterPass(StringRef PassID, Any IR) {
99   std::string Banner =
100       "\n*** Pseudo Probe Verification After " + PassID.str() + " ***\n";
101   dbgs() << Banner;
102   if (any_isa<const Module *>(IR))
103     runAfterPass(any_cast<const Module *>(IR));
104   else if (any_isa<const Function *>(IR))
105     runAfterPass(any_cast<const Function *>(IR));
106   else if (any_isa<const LazyCallGraph::SCC *>(IR))
107     runAfterPass(any_cast<const LazyCallGraph::SCC *>(IR));
108   else if (any_isa<const Loop *>(IR))
109     runAfterPass(any_cast<const Loop *>(IR));
110   else
111     llvm_unreachable("Unknown IR unit");
112 }
113 
114 void PseudoProbeVerifier::runAfterPass(const Module *M) {
115   for (const Function &F : *M)
116     runAfterPass(&F);
117 }
118 
119 void PseudoProbeVerifier::runAfterPass(const LazyCallGraph::SCC *C) {
120   for (const LazyCallGraph::Node &N : *C)
121     runAfterPass(&N.getFunction());
122 }
123 
124 void PseudoProbeVerifier::runAfterPass(const Function *F) {
125   if (!shouldVerifyFunction(F))
126     return;
127   ProbeFactorMap ProbeFactors;
128   for (const auto &BB : *F)
129     collectProbeFactors(&BB, ProbeFactors);
130   verifyProbeFactors(F, ProbeFactors);
131 }
132 
133 void PseudoProbeVerifier::runAfterPass(const Loop *L) {
134   const Function *F = L->getHeader()->getParent();
135   runAfterPass(F);
136 }
137 
138 void PseudoProbeVerifier::collectProbeFactors(const BasicBlock *Block,
139                                               ProbeFactorMap &ProbeFactors) {
140   for (const auto &I : *Block) {
141     if (Optional<PseudoProbe> Probe = extractProbe(I)) {
142       uint64_t Hash = computeCallStackHash(I);
143       ProbeFactors[{Probe->Id, Hash}] += Probe->Factor;
144     }
145   }
146 }
147 
148 void PseudoProbeVerifier::verifyProbeFactors(
149     const Function *F, const ProbeFactorMap &ProbeFactors) {
150   bool BannerPrinted = false;
151   auto &PrevProbeFactors = FunctionProbeFactors[F->getName()];
152   for (const auto &I : ProbeFactors) {
153     float CurProbeFactor = I.second;
154     if (PrevProbeFactors.count(I.first)) {
155       float PrevProbeFactor = PrevProbeFactors[I.first];
156       if (std::abs(CurProbeFactor - PrevProbeFactor) >
157           DistributionFactorVariance) {
158         if (!BannerPrinted) {
159           dbgs() << "Function " << F->getName() << ":\n";
160           BannerPrinted = true;
161         }
162         dbgs() << "Probe " << I.first.first << "\tprevious factor "
163                << format("%0.2f", PrevProbeFactor) << "\tcurrent factor "
164                << format("%0.2f", CurProbeFactor) << "\n";
165       }
166     }
167 
168     // Update
169     PrevProbeFactors[I.first] = I.second;
170   }
171 }
172 
173 PseudoProbeManager::PseudoProbeManager(const Module &M) {
174   if (NamedMDNode *FuncInfo = M.getNamedMetadata(PseudoProbeDescMetadataName)) {
175     for (const auto *Operand : FuncInfo->operands()) {
176       const auto *MD = cast<MDNode>(Operand);
177       auto GUID =
178           mdconst::dyn_extract<ConstantInt>(MD->getOperand(0))->getZExtValue();
179       auto Hash =
180           mdconst::dyn_extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
181       GUIDToProbeDescMap.try_emplace(GUID, PseudoProbeDescriptor(GUID, Hash));
182     }
183   }
184 }
185 
186 const PseudoProbeDescriptor *
187 PseudoProbeManager::getDesc(const Function &F) const {
188   auto I = GUIDToProbeDescMap.find(
189       Function::getGUID(FunctionSamples::getCanonicalFnName(F)));
190   return I == GUIDToProbeDescMap.end() ? nullptr : &I->second;
191 }
192 
193 bool PseudoProbeManager::moduleIsProbed(const Module &M) const {
194   return M.getNamedMetadata(PseudoProbeDescMetadataName);
195 }
196 
197 bool PseudoProbeManager::profileIsValid(const Function &F,
198                                         const FunctionSamples &Samples) const {
199   const auto *Desc = getDesc(F);
200   if (!Desc) {
201     LLVM_DEBUG(dbgs() << "Probe descriptor missing for Function " << F.getName()
202                       << "\n");
203     return false;
204   } else {
205     if (Desc->getFunctionHash() != Samples.getFunctionHash()) {
206       LLVM_DEBUG(dbgs() << "Hash mismatch for Function " << F.getName()
207                         << "\n");
208       return false;
209     }
210   }
211   return true;
212 }
213 
214 SampleProfileProber::SampleProfileProber(Function &Func,
215                                          const std::string &CurModuleUniqueId)
216     : F(&Func), CurModuleUniqueId(CurModuleUniqueId) {
217   BlockProbeIds.clear();
218   CallProbeIds.clear();
219   LastProbeId = (uint32_t)PseudoProbeReservedId::Last;
220   computeProbeIdForBlocks();
221   computeProbeIdForCallsites();
222   computeCFGHash();
223 }
224 
225 // Compute Hash value for the CFG: the lower 32 bits are CRC32 of the index
226 // value of each BB in the CFG. The higher 32 bits record the number of edges
227 // preceded by the number of indirect calls.
228 // This is derived from FuncPGOInstrumentation<Edge, BBInfo>::computeCFGHash().
229 void SampleProfileProber::computeCFGHash() {
230   std::vector<uint8_t> Indexes;
231   JamCRC JC;
232   for (auto &BB : *F) {
233     auto *TI = BB.getTerminator();
234     for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) {
235       auto *Succ = TI->getSuccessor(I);
236       auto Index = getBlockId(Succ);
237       for (int J = 0; J < 4; J++)
238         Indexes.push_back((uint8_t)(Index >> (J * 8)));
239     }
240   }
241 
242   JC.update(Indexes);
243 
244   FunctionHash = (uint64_t)CallProbeIds.size() << 48 |
245                  (uint64_t)Indexes.size() << 32 | JC.getCRC();
246   // Reserve bit 60-63 for other information purpose.
247   FunctionHash &= 0x0FFFFFFFFFFFFFFF;
248   assert(FunctionHash && "Function checksum should not be zero");
249   LLVM_DEBUG(dbgs() << "\nFunction Hash Computation for " << F->getName()
250                     << ":\n"
251                     << " CRC = " << JC.getCRC() << ", Edges = "
252                     << Indexes.size() << ", ICSites = " << CallProbeIds.size()
253                     << ", Hash = " << FunctionHash << "\n");
254 }
255 
256 void SampleProfileProber::computeProbeIdForBlocks() {
257   for (auto &BB : *F) {
258     BlockProbeIds[&BB] = ++LastProbeId;
259   }
260 }
261 
262 void SampleProfileProber::computeProbeIdForCallsites() {
263   for (auto &BB : *F) {
264     for (auto &I : BB) {
265       if (!isa<CallBase>(I))
266         continue;
267       if (isa<IntrinsicInst>(&I))
268         continue;
269       CallProbeIds[&I] = ++LastProbeId;
270     }
271   }
272 }
273 
274 uint32_t SampleProfileProber::getBlockId(const BasicBlock *BB) const {
275   auto I = BlockProbeIds.find(const_cast<BasicBlock *>(BB));
276   return I == BlockProbeIds.end() ? 0 : I->second;
277 }
278 
279 uint32_t SampleProfileProber::getCallsiteId(const Instruction *Call) const {
280   auto Iter = CallProbeIds.find(const_cast<Instruction *>(Call));
281   return Iter == CallProbeIds.end() ? 0 : Iter->second;
282 }
283 
284 void SampleProfileProber::instrumentOneFunc(Function &F, TargetMachine *TM) {
285   Module *M = F.getParent();
286   MDBuilder MDB(F.getContext());
287   // Compute a GUID without considering the function's linkage type. This is
288   // fine since function name is the only key in the profile database.
289   uint64_t Guid = Function::getGUID(F.getName());
290 
291   // Assign an artificial debug line to a probe that doesn't come with a real
292   // line. A probe not having a debug line will get an incomplete inline
293   // context. This will cause samples collected on the probe to be counted
294   // into the base profile instead of a context profile. The line number
295   // itself is not important though.
296   auto AssignDebugLoc = [&](Instruction *I) {
297     assert((isa<PseudoProbeInst>(I) || isa<CallBase>(I)) &&
298            "Expecting pseudo probe or call instructions");
299     if (!I->getDebugLoc()) {
300       if (auto *SP = F.getSubprogram()) {
301         auto DIL = DILocation::get(SP->getContext(), 0, 0, SP);
302         I->setDebugLoc(DIL);
303         ArtificialDbgLine++;
304         LLVM_DEBUG({
305           dbgs() << "\nIn Function " << F.getName()
306                  << " Probe gets an artificial debug line\n";
307           I->dump();
308         });
309       }
310     }
311   };
312 
313   // Probe basic blocks.
314   for (auto &I : BlockProbeIds) {
315     BasicBlock *BB = I.first;
316     uint32_t Index = I.second;
317     // Insert a probe before an instruction with a valid debug line number which
318     // will be assigned to the probe. The line number will be used later to
319     // model the inline context when the probe is inlined into other functions.
320     // Debug instructions, phi nodes and lifetime markers do not have an valid
321     // line number. Real instructions generated by optimizations may not come
322     // with a line number either.
323     auto HasValidDbgLine = [](Instruction *J) {
324       return !isa<PHINode>(J) && !isa<DbgInfoIntrinsic>(J) &&
325              !J->isLifetimeStartOrEnd() && J->getDebugLoc();
326     };
327 
328     Instruction *J = &*BB->getFirstInsertionPt();
329     while (J != BB->getTerminator() && !HasValidDbgLine(J)) {
330       J = J->getNextNode();
331     }
332 
333     IRBuilder<> Builder(J);
334     assert(Builder.GetInsertPoint() != BB->end() &&
335            "Cannot get the probing point");
336     Function *ProbeFn =
337         llvm::Intrinsic::getDeclaration(M, Intrinsic::pseudoprobe);
338     Value *Args[] = {Builder.getInt64(Guid), Builder.getInt64(Index),
339                      Builder.getInt32(0),
340                      Builder.getInt64(PseudoProbeFullDistributionFactor)};
341     auto *Probe = Builder.CreateCall(ProbeFn, Args);
342     AssignDebugLoc(Probe);
343   }
344 
345   // Probe both direct calls and indirect calls. Direct calls are probed so that
346   // their probe ID can be used as an call site identifier to represent a
347   // calling context.
348   for (auto &I : CallProbeIds) {
349     auto *Call = I.first;
350     uint32_t Index = I.second;
351     uint32_t Type = cast<CallBase>(Call)->getCalledFunction()
352                         ? (uint32_t)PseudoProbeType::DirectCall
353                         : (uint32_t)PseudoProbeType::IndirectCall;
354     AssignDebugLoc(Call);
355     // Levarge the 32-bit discriminator field of debug data to store the ID and
356     // type of a callsite probe. This gets rid of the dependency on plumbing a
357     // customized metadata through the codegen pipeline.
358     uint32_t V = PseudoProbeDwarfDiscriminator::packProbeData(
359         Index, Type, 0, PseudoProbeDwarfDiscriminator::FullDistributionFactor);
360     if (auto DIL = Call->getDebugLoc()) {
361       DIL = DIL->cloneWithDiscriminator(V);
362       Call->setDebugLoc(DIL);
363     }
364   }
365 
366   // Create module-level metadata that contains function info necessary to
367   // synthesize probe-based sample counts,  which are
368   // - FunctionGUID
369   // - FunctionHash.
370   // - FunctionName
371   auto Hash = getFunctionHash();
372   auto *MD = MDB.createPseudoProbeDesc(Guid, Hash, &F);
373   auto *NMD = M->getNamedMetadata(PseudoProbeDescMetadataName);
374   assert(NMD && "llvm.pseudo_probe_desc should be pre-created");
375   NMD->addOperand(MD);
376 
377   // Preserve a comdat group to hold all probes materialized later. This
378   // allows that when the function is considered dead and removed, the
379   // materialized probes are disposed too.
380   // Imported functions are defined in another module. They do not need
381   // the following handling since same care will be taken for them in their
382   // original module. The pseudo probes inserted into an imported functions
383   // above will naturally not be emitted since the imported function is free
384   // from object emission. However they will be emitted together with the
385   // inliner functions that the imported function is inlined into. We are not
386   // creating a comdat group for an import function since it's useless anyway.
387   if (!F.isDeclarationForLinker()) {
388     if (TM) {
389       auto Triple = TM->getTargetTriple();
390       if (Triple.supportsCOMDAT() && TM->getFunctionSections())
391         getOrCreateFunctionComdat(F, Triple);
392     }
393   }
394 }
395 
396 PreservedAnalyses SampleProfileProbePass::run(Module &M,
397                                               ModuleAnalysisManager &AM) {
398   auto ModuleId = getUniqueModuleId(&M);
399   // Create the pseudo probe desc metadata beforehand.
400   // Note that modules with only data but no functions will require this to
401   // be set up so that they will be known as probed later.
402   M.getOrInsertNamedMetadata(PseudoProbeDescMetadataName);
403 
404   for (auto &F : M) {
405     if (F.isDeclaration())
406       continue;
407     SampleProfileProber ProbeManager(F, ModuleId);
408     ProbeManager.instrumentOneFunc(F, TM);
409   }
410 
411   return PreservedAnalyses::none();
412 }
413 
414 void PseudoProbeUpdatePass::runOnFunction(Function &F,
415                                           FunctionAnalysisManager &FAM) {
416   BlockFrequencyInfo &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
417   auto BBProfileCount = [&BFI](BasicBlock *BB) {
418     return BFI.getBlockProfileCount(BB)
419                ? BFI.getBlockProfileCount(BB).getValue()
420                : 0;
421   };
422 
423   // Collect the sum of execution weight for each probe.
424   ProbeFactorMap ProbeFactors;
425   for (auto &Block : F) {
426     for (auto &I : Block) {
427       if (Optional<PseudoProbe> Probe = extractProbe(I)) {
428         uint64_t Hash = computeCallStackHash(I);
429         ProbeFactors[{Probe->Id, Hash}] += BBProfileCount(&Block);
430       }
431     }
432   }
433 
434   // Fix up over-counted probes.
435   for (auto &Block : F) {
436     for (auto &I : Block) {
437       if (Optional<PseudoProbe> Probe = extractProbe(I)) {
438         uint64_t Hash = computeCallStackHash(I);
439         float Sum = ProbeFactors[{Probe->Id, Hash}];
440         if (Sum != 0)
441           setProbeDistributionFactor(I, BBProfileCount(&Block) / Sum);
442       }
443     }
444   }
445 }
446 
447 PreservedAnalyses PseudoProbeUpdatePass::run(Module &M,
448                                              ModuleAnalysisManager &AM) {
449   if (UpdatePseudoProbe) {
450     for (auto &F : M) {
451       if (F.isDeclaration())
452         continue;
453       FunctionAnalysisManager &FAM =
454           AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
455       runOnFunction(F, FAM);
456     }
457   }
458   return PreservedAnalyses::none();
459 }
460