1413 lines · cpp
1//===-- ProfileGenerator.cpp - Profile Generator ---------------*- C++ -*-===//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#include "ProfileGenerator.h"9#include "ErrorHandling.h"10#include "MissingFrameInferrer.h"11#include "Options.h"12#include "PerfReader.h"13#include "ProfiledBinary.h"14#include "llvm/DebugInfo/Symbolize/SymbolizableModule.h"15#include "llvm/ProfileData/ProfileCommon.h"16#include <algorithm>17#include <float.h>18#include <unordered_set>19#include <utility>20 21namespace llvm {22 23cl::opt<std::string> OutputFilename("output", cl::value_desc("output"),24 cl::Required,25 cl::desc("Output profile file"),26 cl::cat(ProfGenCategory));27static cl::alias OutputA("o", cl::desc("Alias for --output"),28 cl::aliasopt(OutputFilename));29 30static cl::opt<SampleProfileFormat> OutputFormat(31 "format", cl::desc("Format of output profile"), cl::init(SPF_Ext_Binary),32 cl::values(clEnumValN(SPF_Binary, "binary", "Binary encoding (default)"),33 clEnumValN(SPF_Ext_Binary, "extbinary",34 "Extensible binary encoding"),35 clEnumValN(SPF_Text, "text", "Text encoding"),36 clEnumValN(SPF_GCC, "gcc",37 "GCC encoding (only meaningful for -sample)")),38 cl::cat(ProfGenCategory));39 40static cl::opt<bool> UseMD5(41 "use-md5", cl::Hidden,42 cl::desc("Use md5 to represent function names in the output profile (only "43 "meaningful for -extbinary)"));44 45static cl::opt<bool> PopulateProfileSymbolList(46 "populate-profile-symbol-list", cl::init(false), cl::Hidden,47 cl::desc("Populate profile symbol list (only meaningful for -extbinary)"));48 49static cl::opt<bool> FillZeroForAllFuncs(50 "fill-zero-for-all-funcs", cl::init(false), cl::Hidden,51 cl::desc("Attribute all functions' range with zero count "52 "even it's not hit by any samples."));53 54static cl::opt<int32_t, true> RecursionCompression(55 "compress-recursion",56 cl::desc("Compressing recursion by deduplicating adjacent frame "57 "sequences up to the specified size. -1 means no size limit."),58 cl::Hidden,59 cl::location(llvm::sampleprof::CSProfileGenerator::MaxCompressionSize));60 61static cl::opt<bool>62 TrimColdProfile("trim-cold-profile",63 cl::desc("If the total count of the profile is smaller "64 "than threshold, it will be trimmed."),65 cl::cat(ProfGenCategory));66 67static cl::opt<bool> MarkAllContextPreinlined(68 "mark-all-context-preinlined",69 cl::desc("Mark all function samples as preinlined(set "70 "ContextShouldBeInlined attribute)."),71 cl::init(false));72 73static cl::opt<bool> CSProfMergeColdContext(74 "csprof-merge-cold-context", cl::init(true),75 cl::desc("If the total count of context profile is smaller than "76 "the threshold, it will be merged into context-less base "77 "profile."),78 cl::cat(ProfGenCategory));79 80static cl::opt<uint32_t> CSProfMaxColdContextDepth(81 "csprof-max-cold-context-depth", cl::init(1),82 cl::desc("Keep the last K contexts while merging cold profile. 1 means the "83 "context-less base profile"),84 cl::cat(ProfGenCategory));85 86static cl::opt<int, true> CSProfMaxContextDepth(87 "csprof-max-context-depth",88 cl::desc("Keep the last K contexts while merging profile. -1 means no "89 "depth limit."),90 cl::location(llvm::sampleprof::CSProfileGenerator::MaxContextDepth),91 cl::cat(ProfGenCategory));92 93static cl::opt<double> ProfileDensityThreshold(94 "profile-density-threshold", cl::init(50),95 cl::desc("If the profile density is below the given threshold, it "96 "will be suggested to increase the sampling rate."),97 cl::Optional, cl::cat(ProfGenCategory));98static cl::opt<bool> ShowDensity("show-density", cl::init(false),99 cl::desc("show profile density details"),100 cl::Optional, cl::cat(ProfGenCategory));101static cl::opt<int> ProfileDensityCutOffHot(102 "profile-density-cutoff-hot", cl::init(990000),103 cl::desc("Total samples cutoff for functions used to calculate "104 "profile density."),105 cl::cat(ProfGenCategory));106 107static cl::opt<bool> UpdateTotalSamples(108 "update-total-samples", cl::init(false),109 cl::desc("Update total samples by accumulating all its body samples."),110 cl::Optional, cl::cat(ProfGenCategory));111 112static cl::opt<bool> GenCSNestedProfile(113 "gen-cs-nested-profile", cl::Hidden, cl::init(true),114 cl::desc("Generate nested function profiles for CSSPGO"));115 116cl::opt<bool> InferMissingFrames(117 "infer-missing-frames", cl::init(true),118 cl::desc(119 "Infer missing call frames due to compiler tail call elimination."),120 cl::Optional, cl::cat(ProfGenCategory));121 122namespace sampleprof {123 124// Initialize the MaxCompressionSize to -1 which means no size limit125int32_t CSProfileGenerator::MaxCompressionSize = -1;126 127int CSProfileGenerator::MaxContextDepth = -1;128 129bool ProfileGeneratorBase::UseFSDiscriminator = false;130 131std::unique_ptr<ProfileGeneratorBase>132ProfileGeneratorBase::create(ProfiledBinary *Binary,133 const ContextSampleCounterMap *SampleCounters,134 bool ProfileIsCS) {135 std::unique_ptr<ProfileGeneratorBase> Generator;136 if (ProfileIsCS) {137 Generator.reset(new CSProfileGenerator(Binary, SampleCounters));138 } else {139 Generator.reset(new ProfileGenerator(Binary, SampleCounters));140 }141 ProfileGeneratorBase::UseFSDiscriminator = Binary->useFSDiscriminator();142 FunctionSamples::ProfileIsFS = Binary->useFSDiscriminator();143 144 return Generator;145}146 147std::unique_ptr<ProfileGeneratorBase>148ProfileGeneratorBase::create(ProfiledBinary *Binary, SampleProfileMap &Profiles,149 bool ProfileIsCS) {150 std::unique_ptr<ProfileGeneratorBase> Generator;151 if (ProfileIsCS) {152 Generator.reset(new CSProfileGenerator(Binary, Profiles));153 } else {154 Generator.reset(new ProfileGenerator(Binary, std::move(Profiles)));155 }156 ProfileGeneratorBase::UseFSDiscriminator = Binary->useFSDiscriminator();157 FunctionSamples::ProfileIsFS = Binary->useFSDiscriminator();158 159 return Generator;160}161 162void ProfileGeneratorBase::write(std::unique_ptr<SampleProfileWriter> Writer,163 SampleProfileMap &ProfileMap) {164 // Populate profile symbol list if extended binary format is used.165 ProfileSymbolList SymbolList;166 167 if (PopulateProfileSymbolList && OutputFormat == SPF_Ext_Binary) {168 Binary->populateSymbolListFromDWARF(SymbolList);169 Writer->setProfileSymbolList(&SymbolList);170 }171 172 if (std::error_code EC = Writer->write(ProfileMap))173 exitWithError(std::move(EC));174}175 176void ProfileGeneratorBase::write() {177 auto WriterOrErr = SampleProfileWriter::create(OutputFilename, OutputFormat);178 if (std::error_code EC = WriterOrErr.getError())179 exitWithError(EC, OutputFilename);180 181 if (UseMD5) {182 if (OutputFormat != SPF_Ext_Binary)183 WithColor::warning() << "-use-md5 is ignored. Specify "184 "--format=extbinary to enable it\n";185 else186 WriterOrErr.get()->setUseMD5();187 }188 189 write(std::move(WriterOrErr.get()), ProfileMap);190}191 192void ProfileGeneratorBase::showDensitySuggestion(double Density) {193 if (Density == 0.0)194 WithColor::warning() << "The output profile is empty or the "195 "--profile-density-cutoff-hot option is "196 "set too low. Please check your command.\n";197 else if (Density < ProfileDensityThreshold)198 WithColor::warning()199 << "Sample PGO is estimated to optimize better with "200 << format("%.1f", ProfileDensityThreshold / Density)201 << "x more samples. Please consider increasing sampling rate or "202 "profiling for longer duration to get more samples.\n";203 204 if (ShowDensity)205 outs() << "Functions with density >= " << format("%.1f", Density)206 << " account for "207 << format("%.2f",208 static_cast<double>(ProfileDensityCutOffHot) / 10000)209 << "% total sample counts.\n";210}211 212bool ProfileGeneratorBase::filterAmbiguousProfile(FunctionSamples &FS) {213 for (const auto &Prefix : FuncPrefixsToFilter) {214 if (FS.getFuncName().starts_with(Prefix))215 return true;216 }217 218 // Filter the function profiles for the inlinees. It's useful for fuzzy219 // profile matching which flattens the profile and inlinees' samples are220 // merged into top-level function.221 for (auto &Callees :222 const_cast<CallsiteSampleMap &>(FS.getCallsiteSamples())) {223 auto &CalleesMap = Callees.second;224 for (auto I = CalleesMap.begin(); I != CalleesMap.end();) {225 auto FS = I++;226 if (filterAmbiguousProfile(FS->second))227 CalleesMap.erase(FS);228 }229 }230 return false;231}232 233// For built-in local initialization function such as __cxx_global_var_init,234// __tls_init prefix function, there could be multiple versions of the functions235// in the final binary. However, in the profile generation, we call236// getCanonicalFnName to canonicalize the names which strips the suffixes.237// Therefore, samples from different functions queries the same profile and the238// samples are merged. As the functions are essentially different, entries of239// the merged profile are ambiguous. In sample loader, the IR from one version240// would be attributed towards a merged entries, which is inaccurate. Especially241// for fuzzy profile matching, it gets multiple callsites(from different242// function) but used to match one callsite, which misleads the matching and243// causes a lot of false positives report. Hence, we want to filter them out244// from the profile map during the profile generation time. The profiles are all245// cold functions, it won't have perf impact.246void ProfileGeneratorBase::filterAmbiguousProfile(SampleProfileMap &Profiles) {247 for (auto I = ProfileMap.begin(); I != ProfileMap.end();) {248 auto FS = I++;249 if (filterAmbiguousProfile(FS->second))250 ProfileMap.erase(FS);251 }252}253 254void ProfileGeneratorBase::findDisjointRanges(RangeSample &DisjointRanges,255 const RangeSample &Ranges) {256 257 /*258 Regions may overlap with each other. Using the boundary info, find all259 disjoint ranges and their sample count. BoundaryPoint contains the count260 multiple samples begin/end at this points.261 262 |<--100-->| Sample1263 |<------200------>| Sample2264 A B C265 266 In the example above,267 Sample1 begins at A, ends at B, its value is 100.268 Sample2 beings at A, ends at C, its value is 200.269 For A, BeginCount is the sum of sample begins at A, which is 300 and no270 samples ends at A, so EndCount is 0.271 Then boundary points A, B, and C with begin/end counts are:272 A: (300, 0)273 B: (0, 100)274 C: (0, 200)275 */276 struct BoundaryPoint {277 // Sum of sample counts beginning at this point278 uint64_t BeginCount = UINT64_MAX;279 // Sum of sample counts ending at this point280 uint64_t EndCount = UINT64_MAX;281 // Is the begin point of a zero range.282 bool IsZeroRangeBegin = false;283 // Is the end point of a zero range.284 bool IsZeroRangeEnd = false;285 286 void addBeginCount(uint64_t Count) {287 if (BeginCount == UINT64_MAX)288 BeginCount = 0;289 BeginCount += Count;290 }291 292 void addEndCount(uint64_t Count) {293 if (EndCount == UINT64_MAX)294 EndCount = 0;295 EndCount += Count;296 }297 };298 299 /*300 For the above example. With boundary points, follwing logic finds two301 disjoint region of302 303 [A,B]: 300304 [B+1,C]: 200305 306 If there is a boundary point that both begin and end, the point itself307 becomes a separate disjoint region. For example, if we have original308 ranges of309 310 |<--- 100 --->|311 |<--- 200 --->|312 A B C313 314 there are three boundary points with their begin/end counts of315 316 A: (100, 0)317 B: (200, 100)318 C: (0, 200)319 320 the disjoint ranges would be321 322 [A, B-1]: 100323 [B, B]: 300324 [B+1, C]: 200.325 326 Example for zero value range:327 328 |<--- 100 --->|329 |<--- 200 --->|330 |<--------------- 0 ----------------->|331 A B C D E F332 333 [A, B-1] : 0334 [B, C] : 100335 [C+1, D-1]: 0336 [D, E] : 200337 [E+1, F] : 0338 */339 std::map<uint64_t, BoundaryPoint> Boundaries;340 341 for (const auto &Item : Ranges) {342 assert(Item.first.first <= Item.first.second &&343 "Invalid instruction range");344 auto &BeginPoint = Boundaries[Item.first.first];345 auto &EndPoint = Boundaries[Item.first.second];346 uint64_t Count = Item.second;347 348 BeginPoint.addBeginCount(Count);349 EndPoint.addEndCount(Count);350 if (Count == 0) {351 BeginPoint.IsZeroRangeBegin = true;352 EndPoint.IsZeroRangeEnd = true;353 }354 }355 356 // Use UINT64_MAX to indicate there is no existing range between BeginAddress357 // and the next valid address358 uint64_t BeginAddress = UINT64_MAX;359 int ZeroRangeDepth = 0;360 uint64_t Count = 0;361 for (const auto &Item : Boundaries) {362 uint64_t Address = Item.first;363 const BoundaryPoint &Point = Item.second;364 if (Point.BeginCount != UINT64_MAX) {365 if (BeginAddress != UINT64_MAX)366 DisjointRanges[{BeginAddress, Address - 1}] = Count;367 Count += Point.BeginCount;368 BeginAddress = Address;369 ZeroRangeDepth += Point.IsZeroRangeBegin;370 }371 if (Point.EndCount != UINT64_MAX) {372 assert((BeginAddress != UINT64_MAX) &&373 "First boundary point cannot be 'end' point");374 DisjointRanges[{BeginAddress, Address}] = Count;375 assert(Count >= Point.EndCount && "Mismatched live ranges");376 Count -= Point.EndCount;377 BeginAddress = Address + 1;378 ZeroRangeDepth -= Point.IsZeroRangeEnd;379 // If the remaining count is zero and it's no longer in a zero range, this380 // means we consume all the ranges before, thus mark BeginAddress as381 // UINT64_MAX. e.g. supposing we have two non-overlapping ranges:382 // [<---- 10 ---->]383 // [<---- 20 ---->]384 // A B C D385 // The BeginAddress(B+1) will reset to invalid(UINT64_MAX), so we won't386 // have the [B+1, C-1] zero range.387 if (Count == 0 && ZeroRangeDepth == 0)388 BeginAddress = UINT64_MAX;389 }390 }391}392 393void ProfileGeneratorBase::updateBodySamplesforFunctionProfile(394 FunctionSamples &FunctionProfile, const SampleContextFrame &LeafLoc,395 uint64_t Count) {396 // Use the maximum count of samples with same line location397 uint32_t Discriminator = getBaseDiscriminator(LeafLoc.Location.Discriminator);398 399 // Use duplication factor to compensated for loop unroll/vectorization.400 // Note that this is only needed when we're taking MAX of the counts at401 // the location instead of SUM.402 Count *= getDuplicationFactor(LeafLoc.Location.Discriminator);403 404 ErrorOr<uint64_t> R =405 FunctionProfile.findSamplesAt(LeafLoc.Location.LineOffset, Discriminator);406 407 uint64_t PreviousCount = R ? R.get() : 0;408 if (PreviousCount <= Count) {409 FunctionProfile.addBodySamples(LeafLoc.Location.LineOffset, Discriminator,410 Count - PreviousCount);411 }412}413 414void ProfileGeneratorBase::updateTotalSamples() {415 for (auto &Item : ProfileMap) {416 FunctionSamples &FunctionProfile = Item.second;417 FunctionProfile.updateTotalSamples();418 }419}420 421void ProfileGeneratorBase::updateCallsiteSamples() {422 for (auto &Item : ProfileMap) {423 FunctionSamples &FunctionProfile = Item.second;424 FunctionProfile.updateCallsiteSamples();425 }426}427 428void ProfileGeneratorBase::updateFunctionSamples() {429 updateCallsiteSamples();430 431 if (UpdateTotalSamples)432 updateTotalSamples();433}434 435void ProfileGeneratorBase::collectProfiledFunctions() {436 std::unordered_set<const BinaryFunction *> ProfiledFunctions;437 if (collectFunctionsFromRawProfile(ProfiledFunctions))438 Binary->setProfiledFunctions(ProfiledFunctions);439 else if (collectFunctionsFromLLVMProfile(ProfiledFunctions))440 Binary->setProfiledFunctions(ProfiledFunctions);441 else442 llvm_unreachable("Unsupported input profile");443}444 445bool ProfileGeneratorBase::collectFunctionsFromRawProfile(446 std::unordered_set<const BinaryFunction *> &ProfiledFunctions) {447 if (!SampleCounters)448 return false;449 // Go through all the stacks, ranges and branches in sample counters, use450 // the start of the range to look up the function it belongs and record the451 // function.452 for (const auto &CI : *SampleCounters) {453 if (const auto *CtxKey = dyn_cast<AddrBasedCtxKey>(CI.first.getPtr())) {454 for (auto StackAddr : CtxKey->Context) {455 if (FuncRange *FRange = Binary->findFuncRange(StackAddr))456 ProfiledFunctions.insert(FRange->Func);457 }458 }459 460 for (auto Item : CI.second.RangeCounter) {461 uint64_t StartAddress = Item.first.first;462 if (FuncRange *FRange = Binary->findFuncRange(StartAddress))463 ProfiledFunctions.insert(FRange->Func);464 }465 466 for (auto Item : CI.second.BranchCounter) {467 uint64_t SourceAddress = Item.first.first;468 uint64_t TargetAddress = Item.first.second;469 if (FuncRange *FRange = Binary->findFuncRange(SourceAddress))470 ProfiledFunctions.insert(FRange->Func);471 if (FuncRange *FRange = Binary->findFuncRange(TargetAddress))472 ProfiledFunctions.insert(FRange->Func);473 }474 }475 return true;476}477 478bool ProfileGenerator::collectFunctionsFromLLVMProfile(479 std::unordered_set<const BinaryFunction *> &ProfiledFunctions) {480 for (const auto &FS : ProfileMap) {481 if (auto *Func = Binary->getBinaryFunction(FS.second.getFunction()))482 ProfiledFunctions.insert(Func);483 }484 return true;485}486 487bool CSProfileGenerator::collectFunctionsFromLLVMProfile(488 std::unordered_set<const BinaryFunction *> &ProfiledFunctions) {489 for (auto *Node : ContextTracker) {490 if (!Node->getFuncName().empty())491 if (auto *Func = Binary->getBinaryFunction(Node->getFuncName()))492 ProfiledFunctions.insert(Func);493 }494 return true;495}496 497FunctionSamples &498ProfileGenerator::getTopLevelFunctionProfile(FunctionId FuncName) {499 SampleContext Context(FuncName);500 return ProfileMap.create(Context);501}502 503void ProfileGenerator::generateProfile() {504 collectProfiledFunctions();505 506 if (Binary->usePseudoProbes())507 Binary->decodePseudoProbe();508 509 if (SampleCounters) {510 if (Binary->usePseudoProbes()) {511 generateProbeBasedProfile();512 } else {513 generateLineNumBasedProfile();514 }515 }516 517 postProcessProfiles();518}519 520void ProfileGeneratorBase::markAllContextPreinlined(521 SampleProfileMap &ProfileMap) {522 for (auto &I : ProfileMap)523 I.second.setContextAttribute(ContextShouldBeInlined);524 FunctionSamples::ProfileIsPreInlined = true;525}526 527void ProfileGenerator::postProcessProfiles() {528 computeSummaryAndThreshold(ProfileMap);529 trimColdProfiles(ProfileMap, ColdCountThreshold);530 filterAmbiguousProfile(ProfileMap);531 if (MarkAllContextPreinlined)532 markAllContextPreinlined(ProfileMap);533 calculateAndShowDensity(ProfileMap);534}535 536void ProfileGenerator::trimColdProfiles(const SampleProfileMap &Profiles,537 uint64_t ColdCntThreshold) {538 if (!TrimColdProfile)539 return;540 541 // Move cold profiles into a tmp container.542 std::vector<hash_code> ColdProfileHashes;543 for (const auto &I : ProfileMap) {544 if (I.second.getTotalSamples() < ColdCntThreshold)545 ColdProfileHashes.emplace_back(I.first);546 }547 548 // Remove the cold profile from ProfileMap.549 for (const auto &I : ColdProfileHashes)550 ProfileMap.erase(I);551}552 553void ProfileGenerator::generateLineNumBasedProfile() {554 assert(SampleCounters->size() == 1 &&555 "Must have one entry for profile generation.");556 const SampleCounter &SC = SampleCounters->begin()->second;557 // Fill in function body samples558 populateBodySamplesForAllFunctions(SC.RangeCounter);559 // Fill in boundary sample counts as well as call site samples for calls560 populateBoundarySamplesForAllFunctions(SC.BranchCounter);561 populateTypeSamplesForAllFunctions(SC.DataAccessCounter);562 563 updateFunctionSamples();564}565 566void ProfileGenerator::generateProbeBasedProfile() {567 assert(SampleCounters->size() == 1 &&568 "Must have one entry for profile generation.");569 // Enable pseudo probe functionalities in SampleProf570 FunctionSamples::ProfileIsProbeBased = true;571 const SampleCounter &SC = SampleCounters->begin()->second;572 // Fill in function body samples573 populateBodySamplesWithProbesForAllFunctions(SC.RangeCounter);574 // Fill in boundary sample counts as well as call site samples for calls575 populateBoundarySamplesWithProbesForAllFunctions(SC.BranchCounter);576 577 updateFunctionSamples();578}579 580void ProfileGenerator::populateBodySamplesWithProbesForAllFunctions(581 const RangeSample &RangeCounter) {582 ProbeCounterMap ProbeCounter;583 // preprocessRangeCounter returns disjoint ranges, so no longer to redo it584 // inside extractProbesFromRange.585 extractProbesFromRange(preprocessRangeCounter(RangeCounter), ProbeCounter,586 false);587 588 for (const auto &PI : ProbeCounter) {589 const MCDecodedPseudoProbe *Probe = PI.first;590 uint64_t Count = PI.second;591 SampleContextFrameVector FrameVec;592 Binary->getInlineContextForProbe(Probe, FrameVec, true);593 FunctionSamples &FunctionProfile =594 getLeafProfileAndAddTotalSamples(FrameVec, Count);595 FunctionProfile.addBodySamples(Probe->getIndex(), Probe->getDiscriminator(),596 Count);597 if (Probe->isEntry())598 FunctionProfile.addHeadSamples(Count);599 }600}601 602void ProfileGenerator::populateBoundarySamplesWithProbesForAllFunctions(603 const BranchSample &BranchCounters) {604 for (const auto &Entry : BranchCounters) {605 uint64_t SourceAddress = Entry.first.first;606 uint64_t TargetAddress = Entry.first.second;607 uint64_t Count = Entry.second;608 assert(Count != 0 && "Unexpected zero weight branch");609 610 StringRef CalleeName = getCalleeNameForAddress(TargetAddress);611 if (CalleeName.size() == 0)612 continue;613 614 const MCDecodedPseudoProbe *CallProbe =615 Binary->getCallProbeForAddr(SourceAddress);616 if (CallProbe == nullptr)617 continue;618 619 // Record called target sample and its count.620 SampleContextFrameVector FrameVec;621 Binary->getInlineContextForProbe(CallProbe, FrameVec, true);622 623 if (!FrameVec.empty()) {624 FunctionSamples &FunctionProfile =625 getLeafProfileAndAddTotalSamples(FrameVec, 0);626 FunctionProfile.addCalledTargetSamples(627 FrameVec.back().Location.LineOffset,628 FrameVec.back().Location.Discriminator, FunctionId(CalleeName),629 Count);630 }631 }632}633 634FunctionSamples &ProfileGenerator::getLeafProfileAndAddTotalSamples(635 const SampleContextFrameVector &FrameVec, uint64_t Count) {636 // Get top level profile637 FunctionSamples *FunctionProfile =638 &getTopLevelFunctionProfile(FrameVec[0].Func);639 FunctionProfile->addTotalSamples(Count);640 if (Binary->usePseudoProbes()) {641 const auto *FuncDesc = Binary->getFuncDescForGUID(642 FunctionProfile->getFunction().getHashCode());643 FunctionProfile->setFunctionHash(FuncDesc->FuncHash);644 }645 646 for (size_t I = 1; I < FrameVec.size(); I++) {647 LineLocation Callsite(648 FrameVec[I - 1].Location.LineOffset,649 getBaseDiscriminator(FrameVec[I - 1].Location.Discriminator));650 FunctionSamplesMap &SamplesMap =651 FunctionProfile->functionSamplesAt(Callsite);652 auto Ret = SamplesMap.emplace(FrameVec[I].Func, FunctionSamples());653 if (Ret.second) {654 SampleContext Context(FrameVec[I].Func);655 Ret.first->second.setContext(Context);656 }657 FunctionProfile = &Ret.first->second;658 FunctionProfile->addTotalSamples(Count);659 if (Binary->usePseudoProbes()) {660 const auto *FuncDesc = Binary->getFuncDescForGUID(661 FunctionProfile->getFunction().getHashCode());662 FunctionProfile->setFunctionHash(FuncDesc->FuncHash);663 }664 }665 666 return *FunctionProfile;667}668 669RangeSample670ProfileGenerator::preprocessRangeCounter(const RangeSample &RangeCounter) {671 RangeSample Ranges(RangeCounter.begin(), RangeCounter.end());672 if (FillZeroForAllFuncs) {673 for (auto &FuncI : Binary->getAllBinaryFunctions()) {674 for (auto &R : FuncI.second.Ranges) {675 Ranges[{R.first, R.second - 1}] += 0;676 }677 }678 } else {679 // For each range, we search for all ranges of the function it belongs to680 // and initialize it with zero count, so it remains zero if doesn't hit any681 // samples. This is to be consistent with compiler that interpret zero count682 // as unexecuted(cold).683 for (const auto &I : RangeCounter) {684 uint64_t StartAddress = I.first.first;685 for (const auto &Range : Binary->getRanges(StartAddress))686 Ranges[{Range.first, Range.second - 1}] += 0;687 }688 }689 RangeSample DisjointRanges;690 findDisjointRanges(DisjointRanges, Ranges);691 return DisjointRanges;692}693 694void ProfileGenerator::populateBodySamplesForAllFunctions(695 const RangeSample &RangeCounter) {696 for (const auto &Range : preprocessRangeCounter(RangeCounter)) {697 uint64_t RangeBegin = Range.first.first;698 uint64_t RangeEnd = Range.first.second;699 uint64_t Count = Range.second;700 701 InstructionPointer IP(Binary, RangeBegin, true);702 // Disjoint ranges may have range in the middle of two instr,703 // e.g. If Instr1 at Addr1, and Instr2 at Addr2, disjoint range704 // can be Addr1+1 to Addr2-1. We should ignore such range.705 if (IP.Address > RangeEnd)706 continue;707 708 do {709 const SampleContextFrameVector FrameVec =710 Binary->getFrameLocationStack(IP.Address);711 if (!FrameVec.empty()) {712 // FIXME: As accumulating total count per instruction caused some713 // regression, we changed to accumulate total count per byte as a714 // workaround. Tuning hotness threshold on the compiler side might be715 // necessary in the future.716 FunctionSamples &FunctionProfile = getLeafProfileAndAddTotalSamples(717 FrameVec, Count * Binary->getInstSize(IP.Address));718 updateBodySamplesforFunctionProfile(FunctionProfile, FrameVec.back(),719 Count);720 }721 } while (IP.advance() && IP.Address <= RangeEnd);722 }723}724 725StringRef726ProfileGeneratorBase::getCalleeNameForAddress(uint64_t TargetAddress) {727 // Get the function range by branch target if it's a call branch.728 auto *FRange = Binary->findFuncRangeForStartAddr(TargetAddress);729 730 // We won't accumulate sample count for a range whose start is not the real731 // function entry such as outlined function or inner labels.732 if (!FRange || !FRange->IsFuncEntry)733 return StringRef();734 735 return FunctionSamples::getCanonicalFnName(FRange->getFuncName());736}737 738void ProfileGenerator::populateBoundarySamplesForAllFunctions(739 const BranchSample &BranchCounters) {740 for (const auto &Entry : BranchCounters) {741 uint64_t SourceAddress = Entry.first.first;742 uint64_t TargetAddress = Entry.first.second;743 uint64_t Count = Entry.second;744 assert(Count != 0 && "Unexpected zero weight branch");745 746 StringRef CalleeName = getCalleeNameForAddress(TargetAddress);747 if (CalleeName.size() == 0)748 continue;749 // Record called target sample and its count.750 const SampleContextFrameVector &FrameVec =751 Binary->getCachedFrameLocationStack(SourceAddress);752 if (!FrameVec.empty()) {753 FunctionSamples &FunctionProfile =754 getLeafProfileAndAddTotalSamples(FrameVec, 0);755 FunctionProfile.addCalledTargetSamples(756 FrameVec.back().Location.LineOffset,757 getBaseDiscriminator(FrameVec.back().Location.Discriminator),758 FunctionId(CalleeName), Count);759 }760 // Add head samples for callee.761 FunctionSamples &CalleeProfile =762 getTopLevelFunctionProfile(FunctionId(CalleeName));763 CalleeProfile.addHeadSamples(Count);764 }765}766 767void ProfileGenerator::populateTypeSamplesForAllFunctions(768 const DataAccessSample &DataAccessSamples) {769 // For each instruction with vtable accesses, get its symbolized inline770 // stack, and add the vtable counters to the function samples.771 for (const auto &[IpData, Count] : DataAccessSamples) {772 uint64_t InstAddr = IpData.first;773 const SampleContextFrameVector &FrameVec =774 Binary->getCachedFrameLocationStack(InstAddr,775 /* UseProbeDiscriminator= */ false);776 if (!FrameVec.empty()) {777 FunctionSamples &FunctionProfile =778 getLeafProfileAndAddTotalSamples(FrameVec, /* Count= */ 0);779 LineLocation Loc(780 FrameVec.back().Location.LineOffset,781 getBaseDiscriminator(FrameVec.back().Location.Discriminator));782 FunctionProfile.addTypeSamplesAt(Loc, FunctionId(IpData.second), Count);783 }784 }785}786 787void ProfileGeneratorBase::calculateBodySamplesAndSize(788 const FunctionSamples &FSamples, uint64_t &TotalBodySamples,789 uint64_t &FuncBodySize) {790 // Note that ideally the size should be the number of function instruction.791 // However, for probe-based profile, we don't have the accurate instruction792 // count for each probe, instead, the probe sample is the samples count for793 // the block, which is equivelant to794 // total_instruction_samples/num_of_instruction in one block. Hence, we use795 // the number of probe as a proxy for the function's size.796 FuncBodySize += FSamples.getBodySamples().size();797 798 // The accumulated body samples re-calculated here could be different from the799 // TotalSamples(getTotalSamples) field of FunctionSamples for line-number800 // based profile. The reason is that TotalSamples is the sum of all the801 // samples of the machine instruction in one source-code line, however, the802 // entry of Bodysamples is the only max number of them, so the TotalSamples is803 // usually much bigger than the accumulated body samples as one souce-code804 // line can emit many machine instructions. We observed a regression when we805 // switched to use the accumulated body samples(by using806 // -update-total-samples). Hence, it's safer to re-calculate here to avoid807 // such discrepancy. There is no problem for probe-based profile, as the808 // TotalSamples is exactly the same as the accumulated body samples.809 for (const auto &I : FSamples.getBodySamples())810 TotalBodySamples += I.second.getSamples();811 812 for (const auto &CallsiteSamples : FSamples.getCallsiteSamples())813 for (const auto &Callee : CallsiteSamples.second) {814 // For binary-level density, the inlinees' samples and size should be815 // included in the calculation.816 calculateBodySamplesAndSize(Callee.second, TotalBodySamples,817 FuncBodySize);818 }819}820 821// Calculate Profile-density:822// Calculate the density for each function and sort them in descending order,823// keep accumulating their total samples unitl it exceeds the824// percentage_threshold(cut-off) of total profile samples, the profile-density825// is the last(minimum) function-density of the processed functions, which means826// all the functions hot to perf are on good density if the profile-density is827// good. The percentage_threshold(--profile-density-cutoff-hot) is configurable828// depending on how much regression the system want to tolerate.829double830ProfileGeneratorBase::calculateDensity(const SampleProfileMap &Profiles) {831 double ProfileDensity = 0.0;832 833 uint64_t TotalProfileSamples = 0;834 // A list of the function profile density and its total samples.835 std::vector<std::pair<double, uint64_t>> FuncDensityList;836 for (const auto &I : Profiles) {837 uint64_t TotalBodySamples = 0;838 uint64_t FuncBodySize = 0;839 calculateBodySamplesAndSize(I.second, TotalBodySamples, FuncBodySize);840 841 if (FuncBodySize == 0)842 continue;843 844 double FuncDensity = static_cast<double>(TotalBodySamples) / FuncBodySize;845 TotalProfileSamples += TotalBodySamples;846 FuncDensityList.emplace_back(FuncDensity, TotalBodySamples);847 }848 849 // Sorted by the density in descending order.850 llvm::stable_sort(FuncDensityList, [&](const std::pair<double, uint64_t> &A,851 const std::pair<double, uint64_t> &B) {852 if (A.first != B.first)853 return A.first > B.first;854 return A.second < B.second;855 });856 857 uint64_t AccumulatedSamples = 0;858 uint32_t I = 0;859 assert(ProfileDensityCutOffHot <= 1000000 &&860 "The cutoff value is greater than 1000000(100%)");861 while (AccumulatedSamples < TotalProfileSamples *862 static_cast<float>(ProfileDensityCutOffHot) /863 1000000 &&864 I < FuncDensityList.size()) {865 AccumulatedSamples += FuncDensityList[I].second;866 ProfileDensity = FuncDensityList[I].first;867 I++;868 }869 870 return ProfileDensity;871}872 873void ProfileGeneratorBase::calculateAndShowDensity(874 const SampleProfileMap &Profiles) {875 double Density = calculateDensity(Profiles);876 showDensitySuggestion(Density);877}878 879FunctionSamples *880CSProfileGenerator::getOrCreateFunctionSamples(ContextTrieNode *ContextNode,881 bool WasLeafInlined) {882 FunctionSamples *FProfile = ContextNode->getFunctionSamples();883 if (!FProfile) {884 FSamplesList.emplace_back();885 FProfile = &FSamplesList.back();886 FProfile->setFunction(ContextNode->getFuncName());887 ContextNode->setFunctionSamples(FProfile);888 }889 // Update ContextWasInlined attribute for existing contexts.890 // The current function can be called in two ways:891 // - when processing a probe of the current frame892 // - when processing the entry probe of an inlinee's frame, which893 // is then used to update the callsite count of the current frame.894 // The two can happen in any order, hence here we are making sure895 // `ContextWasInlined` is always set as expected.896 // TODO: Note that the former does not always happen if no probes of the897 // current frame has samples, and if the latter happens, we could lose the898 // attribute. This should be fixed.899 if (WasLeafInlined)900 FProfile->getContext().setAttribute(ContextWasInlined);901 return FProfile;902}903 904ContextTrieNode *905CSProfileGenerator::getOrCreateContextNode(const SampleContextFrames Context,906 bool WasLeafInlined) {907 ContextTrieNode *ContextNode =908 ContextTracker.getOrCreateContextPath(Context, true);909 getOrCreateFunctionSamples(ContextNode, WasLeafInlined);910 return ContextNode;911}912 913void CSProfileGenerator::generateProfile() {914 FunctionSamples::ProfileIsCS = true;915 916 collectProfiledFunctions();917 918 if (Binary->usePseudoProbes()) {919 Binary->decodePseudoProbe();920 if (InferMissingFrames)921 initializeMissingFrameInferrer();922 }923 924 if (SampleCounters) {925 if (Binary->usePseudoProbes()) {926 generateProbeBasedProfile();927 } else {928 generateLineNumBasedProfile();929 }930 }931 932 if (Binary->getTrackFuncContextSize())933 computeSizeForProfiledFunctions();934 935 postProcessProfiles();936}937 938void CSProfileGenerator::initializeMissingFrameInferrer() {939 Binary->getMissingContextInferrer()->initialize(SampleCounters);940}941 942void CSProfileGenerator::inferMissingFrames(943 const SmallVectorImpl<uint64_t> &Context,944 SmallVectorImpl<uint64_t> &NewContext) {945 Binary->inferMissingFrames(Context, NewContext);946}947 948void CSProfileGenerator::computeSizeForProfiledFunctions() {949 for (auto *Func : Binary->getProfiledFunctions())950 Binary->computeInlinedContextSizeForFunc(Func);951 952 // Flush the symbolizer to save memory.953 Binary->flushSymbolizer();954}955 956void CSProfileGenerator::updateFunctionSamples() {957 for (auto *Node : ContextTracker) {958 FunctionSamples *FSamples = Node->getFunctionSamples();959 if (FSamples) {960 if (UpdateTotalSamples)961 FSamples->updateTotalSamples();962 FSamples->updateCallsiteSamples();963 }964 }965}966 967void CSProfileGenerator::generateLineNumBasedProfile() {968 for (const auto &CI : *SampleCounters) {969 const auto *CtxKey = cast<StringBasedCtxKey>(CI.first.getPtr());970 971 ContextTrieNode *ContextNode = &getRootContext();972 // Sample context will be empty if the jump is an external-to-internal call973 // pattern, the head samples should be added for the internal function.974 if (!CtxKey->Context.empty()) {975 // Get or create function profile for the range976 ContextNode =977 getOrCreateContextNode(CtxKey->Context, CtxKey->WasLeafInlined);978 // Fill in function body samples979 populateBodySamplesForFunction(*ContextNode->getFunctionSamples(),980 CI.second.RangeCounter);981 }982 // Fill in boundary sample counts as well as call site samples for calls983 populateBoundarySamplesForFunction(ContextNode, CI.second.BranchCounter);984 }985 // Fill in call site value sample for inlined calls and also use context to986 // infer missing samples. Since we don't have call count for inlined987 // functions, we estimate it from inlinee's profile using the entry of the988 // body sample.989 populateInferredFunctionSamples(getRootContext());990 991 updateFunctionSamples();992}993 994void CSProfileGenerator::populateBodySamplesForFunction(995 FunctionSamples &FunctionProfile, const RangeSample &RangeCounter) {996 // Compute disjoint ranges first, so we can use MAX997 // for calculating count for each location.998 RangeSample Ranges;999 findDisjointRanges(Ranges, RangeCounter);1000 for (const auto &Range : Ranges) {1001 uint64_t RangeBegin = Range.first.first;1002 uint64_t RangeEnd = Range.first.second;1003 uint64_t Count = Range.second;1004 // Disjoint ranges have introduce zero-filled gap that1005 // doesn't belong to current context, filter them out.1006 if (Count == 0)1007 continue;1008 1009 InstructionPointer IP(Binary, RangeBegin, true);1010 // Disjoint ranges may have range in the middle of two instr,1011 // e.g. If Instr1 at Addr1, and Instr2 at Addr2, disjoint range1012 // can be Addr1+1 to Addr2-1. We should ignore such range.1013 if (IP.Address > RangeEnd)1014 continue;1015 1016 do {1017 auto LeafLoc = Binary->getInlineLeafFrameLoc(IP.Address);1018 if (LeafLoc) {1019 // Recording body sample for this specific context1020 updateBodySamplesforFunctionProfile(FunctionProfile, *LeafLoc, Count);1021 FunctionProfile.addTotalSamples(Count);1022 }1023 } while (IP.advance() && IP.Address <= RangeEnd);1024 }1025}1026 1027void CSProfileGenerator::populateBoundarySamplesForFunction(1028 ContextTrieNode *Node, const BranchSample &BranchCounters) {1029 1030 for (const auto &Entry : BranchCounters) {1031 uint64_t SourceAddress = Entry.first.first;1032 uint64_t TargetAddress = Entry.first.second;1033 uint64_t Count = Entry.second;1034 assert(Count != 0 && "Unexpected zero weight branch");1035 1036 StringRef CalleeName = getCalleeNameForAddress(TargetAddress);1037 if (CalleeName.size() == 0)1038 continue;1039 1040 ContextTrieNode *CallerNode = Node;1041 LineLocation CalleeCallSite(0, 0);1042 if (CallerNode != &getRootContext()) {1043 // Record called target sample and its count1044 auto LeafLoc = Binary->getInlineLeafFrameLoc(SourceAddress);1045 if (LeafLoc) {1046 CallerNode->getFunctionSamples()->addCalledTargetSamples(1047 LeafLoc->Location.LineOffset,1048 getBaseDiscriminator(LeafLoc->Location.Discriminator),1049 FunctionId(CalleeName),1050 Count);1051 // Record head sample for called target(callee)1052 CalleeCallSite = LeafLoc->Location;1053 }1054 }1055 1056 ContextTrieNode *CalleeNode =1057 CallerNode->getOrCreateChildContext(CalleeCallSite,1058 FunctionId(CalleeName));1059 FunctionSamples *CalleeProfile = getOrCreateFunctionSamples(CalleeNode);1060 CalleeProfile->addHeadSamples(Count);1061 }1062}1063 1064void CSProfileGenerator::populateInferredFunctionSamples(1065 ContextTrieNode &Node) {1066 // There is no call jmp sample between the inliner and inlinee, we need to use1067 // the inlinee's context to infer inliner's context, i.e. parent(inliner)'s1068 // sample depends on child(inlinee)'s sample, so traverse the tree in1069 // post-order.1070 for (auto &It : Node.getAllChildContext())1071 populateInferredFunctionSamples(It.second);1072 1073 FunctionSamples *CalleeProfile = Node.getFunctionSamples();1074 if (!CalleeProfile)1075 return;1076 // If we already have head sample counts, we must have value profile1077 // for call sites added already. Skip to avoid double counting.1078 if (CalleeProfile->getHeadSamples())1079 return;1080 ContextTrieNode *CallerNode = Node.getParentContext();1081 // If we don't have context, nothing to do for caller's call site.1082 // This could happen for entry point function.1083 if (CallerNode == &getRootContext())1084 return;1085 1086 LineLocation CallerLeafFrameLoc = Node.getCallSiteLoc();1087 FunctionSamples &CallerProfile = *getOrCreateFunctionSamples(CallerNode);1088 // Since we don't have call count for inlined functions, we1089 // estimate it from inlinee's profile using entry body sample.1090 uint64_t EstimatedCallCount = CalleeProfile->getHeadSamplesEstimate();1091 // If we don't have samples with location, use 1 to indicate live.1092 if (!EstimatedCallCount && !CalleeProfile->getBodySamples().size())1093 EstimatedCallCount = 1;1094 CallerProfile.addCalledTargetSamples(CallerLeafFrameLoc.LineOffset,1095 CallerLeafFrameLoc.Discriminator,1096 Node.getFuncName(), EstimatedCallCount);1097 CallerProfile.addBodySamples(CallerLeafFrameLoc.LineOffset,1098 CallerLeafFrameLoc.Discriminator,1099 EstimatedCallCount);1100 CallerProfile.addTotalSamples(EstimatedCallCount);1101}1102 1103void CSProfileGenerator::convertToProfileMap(1104 ContextTrieNode &Node, SampleContextFrameVector &Context) {1105 FunctionSamples *FProfile = Node.getFunctionSamples();1106 if (FProfile) {1107 Context.emplace_back(Node.getFuncName(), LineLocation(0, 0));1108 // Save the new context for future references.1109 SampleContextFrames NewContext = *Contexts.insert(Context).first;1110 auto Ret = ProfileMap.emplace(NewContext, std::move(*FProfile));1111 FunctionSamples &NewProfile = Ret.first->second;1112 NewProfile.getContext().setContext(NewContext);1113 Context.pop_back();1114 }1115 1116 for (auto &It : Node.getAllChildContext()) {1117 ContextTrieNode &ChildNode = It.second;1118 Context.emplace_back(Node.getFuncName(), ChildNode.getCallSiteLoc());1119 convertToProfileMap(ChildNode, Context);1120 Context.pop_back();1121 }1122}1123 1124void CSProfileGenerator::convertToProfileMap() {1125 assert(ProfileMap.empty() &&1126 "ProfileMap should be empty before converting from the trie");1127 assert(IsProfileValidOnTrie &&1128 "Do not convert the trie twice, it's already destroyed");1129 1130 SampleContextFrameVector Context;1131 for (auto &It : getRootContext().getAllChildContext())1132 convertToProfileMap(It.second, Context);1133 1134 IsProfileValidOnTrie = false;1135}1136 1137void CSProfileGenerator::postProcessProfiles() {1138 // Compute hot/cold threshold based on profile. This will be used for cold1139 // context profile merging/trimming.1140 computeSummaryAndThreshold();1141 1142 // Run global pre-inliner to adjust/merge context profile based on estimated1143 // inline decisions.1144 if (EnableCSPreInliner) {1145 ContextTracker.populateFuncToCtxtMap();1146 CSPreInliner(ContextTracker, *Binary, Summary.get()).run();1147 // Turn off the profile merger by default unless it is explicitly enabled.1148 if (!CSProfMergeColdContext.getNumOccurrences())1149 CSProfMergeColdContext = false;1150 }1151 1152 convertToProfileMap();1153 1154 // Trim and merge cold context profile using cold threshold above.1155 if (TrimColdProfile || CSProfMergeColdContext) {1156 SampleContextTrimmer(ProfileMap)1157 .trimAndMergeColdContextProfiles(1158 HotCountThreshold, TrimColdProfile, CSProfMergeColdContext,1159 CSProfMaxColdContextDepth, EnableCSPreInliner);1160 }1161 1162 if (GenCSNestedProfile) {1163 ProfileConverter CSConverter(ProfileMap);1164 CSConverter.convertCSProfiles();1165 FunctionSamples::ProfileIsCS = false;1166 }1167 filterAmbiguousProfile(ProfileMap);1168 if (MarkAllContextPreinlined)1169 markAllContextPreinlined(ProfileMap);1170 ProfileGeneratorBase::calculateAndShowDensity(ProfileMap);1171}1172 1173void ProfileGeneratorBase::computeSummaryAndThreshold(1174 SampleProfileMap &Profiles) {1175 SampleProfileSummaryBuilder Builder(ProfileSummaryBuilder::DefaultCutoffs);1176 Summary = Builder.computeSummaryForProfiles(Profiles);1177 HotCountThreshold = ProfileSummaryBuilder::getHotCountThreshold(1178 (Summary->getDetailedSummary()));1179 ColdCountThreshold = ProfileSummaryBuilder::getColdCountThreshold(1180 (Summary->getDetailedSummary()));1181}1182 1183void CSProfileGenerator::computeSummaryAndThreshold() {1184 // Always merge and use context-less profile map to compute summary.1185 SampleProfileMap ContextLessProfiles;1186 ContextTracker.createContextLessProfileMap(ContextLessProfiles);1187 1188 // Set the flag below to avoid merging the profile again in1189 // computeSummaryAndThreshold1190 FunctionSamples::ProfileIsCS = false;1191 assert(1192 (!UseContextLessSummary.getNumOccurrences() || UseContextLessSummary) &&1193 "Don't set --profile-summary-contextless to false for profile "1194 "generation");1195 ProfileGeneratorBase::computeSummaryAndThreshold(ContextLessProfiles);1196 // Recover the old value.1197 FunctionSamples::ProfileIsCS = true;1198}1199 1200void ProfileGeneratorBase::extractProbesFromRange(1201 const RangeSample &RangeCounter, ProbeCounterMap &ProbeCounter,1202 bool FindDisjointRanges) {1203 const RangeSample *PRanges = &RangeCounter;1204 RangeSample Ranges;1205 if (FindDisjointRanges) {1206 findDisjointRanges(Ranges, RangeCounter);1207 PRanges = &Ranges;1208 }1209 1210 for (const auto &Range : *PRanges) {1211 uint64_t RangeBegin = Range.first.first;1212 uint64_t RangeEnd = Range.first.second;1213 uint64_t Count = Range.second;1214 1215 InstructionPointer IP(Binary, RangeBegin, true);1216 // Disjoint ranges may have range in the middle of two instr,1217 // e.g. If Instr1 at Addr1, and Instr2 at Addr2, disjoint range1218 // can be Addr1+1 to Addr2-1. We should ignore such range.1219 if (IP.Address > RangeEnd)1220 continue;1221 1222 do {1223 const AddressProbesMap &Address2ProbesMap =1224 Binary->getAddress2ProbesMap();1225 for (const MCDecodedPseudoProbe &Probe :1226 Address2ProbesMap.find(IP.Address)) {1227 ProbeCounter[&Probe] += Count;1228 }1229 } while (IP.advance() && IP.Address <= RangeEnd);1230 }1231}1232 1233static void extractPrefixContextStack(SampleContextFrameVector &ContextStack,1234 const SmallVectorImpl<uint64_t> &AddrVec,1235 ProfiledBinary *Binary) {1236 SmallVector<const MCDecodedPseudoProbe *, 16> Probes;1237 for (auto Address : reverse(AddrVec)) {1238 const MCDecodedPseudoProbe *CallProbe =1239 Binary->getCallProbeForAddr(Address);1240 // These could be the cases when a probe is not found at a calliste. Cutting1241 // off the context from here since the inliner will not know how to consume1242 // a context with unknown callsites.1243 // 1. for functions that are not sampled when1244 // --decode-probe-for-profiled-functions-only is on.1245 // 2. for a merged callsite. Callsite merging may cause the loss of original1246 // probe IDs.1247 // 3. for an external callsite.1248 if (!CallProbe)1249 break;1250 Probes.push_back(CallProbe);1251 }1252 1253 std::reverse(Probes.begin(), Probes.end());1254 1255 // Extract context stack for reusing, leaf context stack will be added1256 // compressed while looking up function profile.1257 for (const auto *P : Probes) {1258 Binary->getInlineContextForProbe(P, ContextStack, true);1259 }1260}1261 1262void CSProfileGenerator::generateProbeBasedProfile() {1263 // Enable pseudo probe functionalities in SampleProf1264 FunctionSamples::ProfileIsProbeBased = true;1265 for (const auto &CI : *SampleCounters) {1266 const AddrBasedCtxKey *CtxKey =1267 dyn_cast<AddrBasedCtxKey>(CI.first.getPtr());1268 // Fill in function body samples from probes, also infer caller's samples1269 // from callee's probe1270 populateBodySamplesWithProbes(CI.second.RangeCounter, CtxKey);1271 // Fill in boundary samples for a call probe1272 populateBoundarySamplesWithProbes(CI.second.BranchCounter, CtxKey);1273 }1274}1275 1276void CSProfileGenerator::populateBodySamplesWithProbes(1277 const RangeSample &RangeCounter, const AddrBasedCtxKey *CtxKey) {1278 ProbeCounterMap ProbeCounter;1279 // Extract the top frame probes by looking up each address among the range in1280 // the Address2ProbeMap1281 extractProbesFromRange(RangeCounter, ProbeCounter);1282 std::unordered_map<MCDecodedPseudoProbeInlineTree *,1283 std::unordered_set<FunctionSamples *>>1284 FrameSamples;1285 for (const auto &PI : ProbeCounter) {1286 const MCDecodedPseudoProbe *Probe = PI.first;1287 uint64_t Count = PI.second;1288 // Disjoint ranges have introduce zero-filled gap that1289 // doesn't belong to current context, filter them out.1290 if (!Probe->isBlock() || Count == 0)1291 continue;1292 1293 ContextTrieNode *ContextNode = getContextNodeForLeafProbe(CtxKey, Probe);1294 FunctionSamples &FunctionProfile = *ContextNode->getFunctionSamples();1295 // Record the current frame and FunctionProfile whenever samples are1296 // collected for non-danglie probes. This is for reporting all of the1297 // zero count probes of the frame later.1298 FrameSamples[Probe->getInlineTreeNode()].insert(&FunctionProfile);1299 FunctionProfile.addBodySamples(Probe->getIndex(), Probe->getDiscriminator(),1300 Count);1301 FunctionProfile.addTotalSamples(Count);1302 if (Probe->isEntry()) {1303 FunctionProfile.addHeadSamples(Count);1304 // Look up for the caller's function profile1305 const auto *InlinerDesc = Binary->getInlinerDescForProbe(Probe);1306 ContextTrieNode *CallerNode = ContextNode->getParentContext();1307 if (InlinerDesc != nullptr && CallerNode != &getRootContext()) {1308 // Since the context id will be compressed, we have to use callee's1309 // context id to infer caller's context id to ensure they share the1310 // same context prefix.1311 uint64_t CallerIndex = ContextNode->getCallSiteLoc().LineOffset;1312 uint64_t CallerDiscriminator = ContextNode->getCallSiteLoc().Discriminator;1313 assert(CallerIndex &&1314 "Inferred caller's location index shouldn't be zero!");1315 assert(!CallerDiscriminator &&1316 "Callsite probe should not have a discriminator!");1317 FunctionSamples &CallerProfile =1318 *getOrCreateFunctionSamples(CallerNode);1319 CallerProfile.setFunctionHash(InlinerDesc->FuncHash);1320 CallerProfile.addBodySamples(CallerIndex, CallerDiscriminator, Count);1321 CallerProfile.addTotalSamples(Count);1322 CallerProfile.addCalledTargetSamples(CallerIndex, CallerDiscriminator,1323 ContextNode->getFuncName(), Count);1324 }1325 }1326 }1327 1328 // Assign zero count for remaining probes without sample hits to1329 // differentiate from probes optimized away, of which the counts are unknown1330 // and will be inferred by the compiler.1331 for (auto &I : FrameSamples) {1332 for (auto *FunctionProfile : I.second) {1333 for (const MCDecodedPseudoProbe &Probe : I.first->getProbes()) {1334 FunctionProfile->addBodySamples(Probe.getIndex(),1335 Probe.getDiscriminator(), 0);1336 }1337 }1338 }1339}1340 1341void CSProfileGenerator::populateBoundarySamplesWithProbes(1342 const BranchSample &BranchCounter, const AddrBasedCtxKey *CtxKey) {1343 for (const auto &BI : BranchCounter) {1344 uint64_t SourceAddress = BI.first.first;1345 uint64_t TargetAddress = BI.first.second;1346 uint64_t Count = BI.second;1347 const MCDecodedPseudoProbe *CallProbe =1348 Binary->getCallProbeForAddr(SourceAddress);1349 if (CallProbe == nullptr)1350 continue;1351 FunctionSamples &FunctionProfile =1352 getFunctionProfileForLeafProbe(CtxKey, CallProbe);1353 FunctionProfile.addBodySamples(CallProbe->getIndex(), 0, Count);1354 FunctionProfile.addTotalSamples(Count);1355 StringRef CalleeName = getCalleeNameForAddress(TargetAddress);1356 if (CalleeName.size() == 0)1357 continue;1358 FunctionProfile.addCalledTargetSamples(CallProbe->getIndex(),1359 CallProbe->getDiscriminator(),1360 FunctionId(CalleeName), Count);1361 }1362}1363 1364ContextTrieNode *CSProfileGenerator::getContextNodeForLeafProbe(1365 const AddrBasedCtxKey *CtxKey, const MCDecodedPseudoProbe *LeafProbe) {1366 1367 const SmallVectorImpl<uint64_t> *PContext = &CtxKey->Context;1368 SmallVector<uint64_t, 16> NewContext;1369 1370 if (InferMissingFrames) {1371 SmallVector<uint64_t, 16> Context = CtxKey->Context;1372 // Append leaf frame for a complete inference.1373 Context.push_back(LeafProbe->getAddress());1374 inferMissingFrames(Context, NewContext);1375 // Pop out the leaf probe that was pushed in above.1376 NewContext.pop_back();1377 PContext = &NewContext;1378 }1379 1380 SampleContextFrameVector ContextStack;1381 extractPrefixContextStack(ContextStack, *PContext, Binary);1382 1383 // Explicitly copy the context for appending the leaf context1384 SampleContextFrameVector NewContextStack(ContextStack.begin(),1385 ContextStack.end());1386 Binary->getInlineContextForProbe(LeafProbe, NewContextStack, true);1387 // For leaf inlined context with the top frame, we should strip off the top1388 // frame's probe id, like:1389 // Inlined stack: [foo:1, bar:2], the ContextId will be "foo:1 @ bar"1390 auto LeafFrame = NewContextStack.back();1391 LeafFrame.Location = LineLocation(0, 0);1392 NewContextStack.pop_back();1393 // Compress the context string except for the leaf frame1394 CSProfileGenerator::compressRecursionContext(NewContextStack);1395 CSProfileGenerator::trimContext(NewContextStack);1396 NewContextStack.push_back(LeafFrame);1397 1398 const auto *FuncDesc = Binary->getFuncDescForGUID(LeafProbe->getGuid());1399 bool WasLeafInlined = LeafProbe->getInlineTreeNode()->hasInlineSite();1400 ContextTrieNode *ContextNode =1401 getOrCreateContextNode(NewContextStack, WasLeafInlined);1402 ContextNode->getFunctionSamples()->setFunctionHash(FuncDesc->FuncHash);1403 return ContextNode;1404}1405 1406FunctionSamples &CSProfileGenerator::getFunctionProfileForLeafProbe(1407 const AddrBasedCtxKey *CtxKey, const MCDecodedPseudoProbe *LeafProbe) {1408 return *getContextNodeForLeafProbe(CtxKey, LeafProbe)->getFunctionSamples();1409}1410 1411} // end namespace sampleprof1412} // end namespace llvm1413