SampleProfileProbe.cpp 16 KB

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