511 lines · cpp
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-exception6//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(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(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(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 67static uint64_t computeCallStackHash(const Instruction &Inst) {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 prevailing76 // 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(F->getName().str());83}84 85void PseudoProbeVerifier::registerCallbacks(PassInstrumentationCallbacks &PIC) {86 if (VerifyPseudoProbe) {87 PIC.registerAfterPassCallback(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.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 *>(&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 else108 llvm_unreachable("Unknown IR unit");109}110 111void PseudoProbeVerifier::runAfterPass(const Module *M) {112 for (const Function &F : *M)113 runAfterPass(&F);114}115 116void PseudoProbeVerifier::runAfterPass(const LazyCallGraph::SCC *C) {117 for (const LazyCallGraph::Node &N : *C)118 runAfterPass(&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, 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(I)) {139 uint64_t Hash = computeCallStackHash(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(I.first);152 if (!Inserted) {153 float PrevProbeFactor = It->second;154 if (std::abs(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("%0.2f", PrevProbeFactor) << "\tcurrent factor "162 << format("%0.2f", CurProbeFactor) << "\n";163 }164 }165 166 // Update167 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 may187// generate unstable IR while optimizing nounwind attribute, some versions are188// 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 blocks191// whose original blocks are instrumented, so it shouldn't degrade the profile192// 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, BlocksAndCallsToIgnore);198 findUnreachableBlocks(BlocksAndCallsToIgnore);199 200 BlocksToIgnore.insert_range(BlocksAndCallsToIgnore);201 202 // Handle the call-to-invoke conversion case: make sure that the probe id and203 // callsite id are consistent before and after the block split. For block204 // probe, we only keep the head block probe id and ignore the block ids of the205 // normal dests. For callsite probe, it's different to block probe, there is206 // no additional callsite in the normal dests, so we don't ignore the207 // callsites.208 findInvokeNormalDests(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) == 0)216 BlocksToIgnore.insert(&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>(TI)) {227 auto *ND = II->getNormalDest();228 InvokeNormalDests.insert(ND);229 230 // The normal dest and the try/catch block are connected by an231 // unconditional branch.232 while (pred_size(ND) == 1) {233 auto *Pred = *pred_begin(ND);234 if (succ_size(Pred) == 1) {235 InvokeNormalDests.insert(Pred);236 ND = Pred;237 } else238 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 the246// CFG Hash consistent. For a given head block, we keep searching the247// 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>(TI)) {253 return getOriginalTerminator(II->getNormalDest(), BlocksToIgnore);254 } else if (succ_size(Head) == 1 &&255 BlocksToIgnore.contains(*succ_begin(Head))) {256 // Go to the unconditional branch dest.257 return getOriginalTerminator(*succ_begin(Head), BlocksToIgnore);258 }259 return TI;260}261 262// Compute Hash value for the CFG: the lower 32 bits are CRC32 of the index263// value of each BB in the CFG. The higher 32 bits record the number of edges264// 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(&BB))272 continue;273 274 auto *TI = getOriginalTerminator(&BB, BlocksToIgnore);275 for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) {276 auto *Succ = TI->getSuccessor(I);277 auto Index = getBlockId(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((uint8_t)(Index >> (J * 8)));283 }284 }285 286 JC.update(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(&BB))308 BlockProbeIds[&BB] = ++LastProbeId;309 310 if (BlocksAndCallsToIgnore.contains(&BB))311 continue;312 for (auto &I : BB) {313 if (!isa<CallBase>(I) || isa<IntrinsicInst>(&I))314 continue;315 316 // The current implementation uses the lower 16 bits of the discriminator317 // 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 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(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(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, we345 // need to make sure their names are consistent, so here also use the name346 // 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(FName);354 355 // Assign an artificial debug line to a probe that doesn't come with a real356 // line. A probe not having a debug line will get an incomplete inline357 // context. This will cause samples collected on the probe to be counted358 // into the base profile instead of a context profile. The line number359 // 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(SP->getContext(), 0, 0, 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 which382 // will be assigned to the probe. The line number will be used later to383 // model the inline context when the probe is inlined into other functions.384 // Debug instructions, phi nodes and lifetime markers do not have an valid385 // line number. Real instructions generated by optimizations may not come386 // with a line number either.387 auto HasValidDbgLine = [](Instruction *J) {388 return !isa<PHINode>(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, Intrinsic::pseudoprobe);401 Value *Args[] = {Builder.getInt64(Guid), Builder.getInt64(Index),402 Builder.getInt32(0),403 Builder.getInt64(PseudoProbeFullDistributionFactor)};404 auto *Probe = Builder.CreateCall(ProbeFn, Args);405 AssignDebugLoc(Probe);406 // Reset the dwarf discriminator if the debug location comes with any. The407 // 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(0);411 Probe->setDebugLoc(DIL);412 }413 }414 }415 416 // Probe both direct calls and indirect calls. Direct calls are probed so that417 // their probe ID can be used as an call site identifier to represent a418 // calling context.419 for (auto &I : CallProbeIds) {420 auto *Call = I.first;421 uint32_t Index = I.second;422 uint32_t Type = cast<CallBase>(Call)->getCalledFunction()423 ? (uint32_t)PseudoProbeType::DirectCall424 : (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 ID428 // and type of a callsite probe. This gets rid of the dependency on429 // plumbing a customized metadata through the codegen pipeline.430 uint32_t V = PseudoProbeDwarfDiscriminator::packProbeData(431 Index, Type, 0, PseudoProbeDwarfDiscriminator::FullDistributionFactor,432 DIL->getBaseDiscriminator());433 DIL = DIL->cloneWithDiscriminator(V);434 Call->setDebugLoc(DIL);435 }436 }437 438 // Create module-level metadata that contains function info necessary to439 // synthesize probe-based sample counts, which are440 // - FunctionGUID441 // - FunctionHash.442 // - FunctionName443 auto Hash = getFunctionHash();444 auto *MD = MDB.createPseudoProbeDesc(Guid, Hash, FName);445 auto *NMD = M->getNamedMetadata(PseudoProbeDescMetadataName);446 assert(NMD && "llvm.pseudo_probe_desc should be pre-created");447 NMD->addOperand(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 to454 // be set up so that they will be known as probed later.455 M.getOrInsertNamedMetadata(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>(F);470 auto BBProfileCount = [&BFI](BasicBlock *BB) {471 return BFI.getBlockProfileCount(BB).value_or(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(I)) {479 uint64_t Hash = computeCallStackHash(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(I)) {489 uint64_t Hash = computeCallStackHash(I);490 float Sum = ProbeFactors[{Probe->Id, Hash}];491 if (Sum != 0)492 setProbeDistributionFactor(I, 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>(M).getManager();506 runOnFunction(F, FAM);507 }508 }509 return PreservedAnalyses::none();510}511