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-exception
6//
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/ProfileData/ProfileCommon.h"
15#include "llvm/Support/Timer.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(Val: 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(Val: 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(Val: 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(L&: 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(Val: false));
72
73static cl::opt<bool> CSProfMergeColdContext(
74 "csprof-merge-cold-context", cl::init(Val: 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(Val: 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(L&: llvm::sampleprof::CSProfileGenerator::MaxContextDepth),
91 cl::cat(ProfGenCategory));
92
93static cl::opt<double> ProfileDensityThreshold(
94 "profile-density-threshold", cl::init(Val: 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::cat(ProfGenCategory));
98static cl::opt<bool> ShowDensity("show-density", cl::init(Val: false),
99 cl::desc("show profile density details"),
100 cl::cat(ProfGenCategory));
101static cl::opt<int> ProfileDensityCutOffHot(
102 "profile-density-cutoff-hot", cl::init(Val: 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(Val: false),
109 cl::desc("Update total samples by accumulating all its body samples."),
110 cl::cat(ProfGenCategory));
111
112static cl::opt<bool> GenCSNestedProfile(
113 "gen-cs-nested-profile", cl::Hidden, cl::init(Val: true),
114 cl::desc("Generate nested function profiles for CSSPGO"));
115
116cl::opt<bool> InferMissingFrames(
117 "infer-missing-frames", cl::init(Val: true),
118 cl::desc(
119 "Infer missing call frames due to compiler tail call elimination."),
120 cl::cat(ProfGenCategory));
121
122namespace sampleprof {
123
124// Initialize the MaxCompressionSize to -1 which means no size limit
125int32_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(p: new CSProfileGenerator(Binary, SampleCounters));
138 } else {
139 Generator.reset(p: 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(p: new CSProfileGenerator(Binary, Profiles));
153 } else {
154 Generator.reset(p: 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(EC: std::move(EC));
174}
175
176void ProfileGeneratorBase::write() {
177 auto WriterOrErr = SampleProfileWriter::create(Filename: OutputFilename, Format: OutputFormat);
178 if (std::error_code EC = WriterOrErr.getError())
179 exitWithError(EC, Whence: 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 else
186 WriterOrErr.get()->setUseMD5();
187 }
188
189 write(Writer: 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(Fmt: "%.1f", Vals: 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(Fmt: "%.1f", Vals: Density)
206 << " account for "
207 << format(Fmt: "%.2f",
208 Vals: 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 fuzzy
219 // profile matching which flattens the profile and inlinees' samples are
220 // 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&: FS->second))
227 CalleesMap.erase(position: 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 functions
235// in the final binary. However, in the profile generation, we call
236// getCanonicalFnName to canonicalize the names which strips the suffixes.
237// Therefore, samples from different functions queries the same profile and the
238// samples are merged. As the functions are essentially different, entries of
239// the merged profile are ambiguous. In sample loader, the IR from one version
240// would be attributed towards a merged entries, which is inaccurate. Especially
241// for fuzzy profile matching, it gets multiple callsites(from different
242// function) but used to match one callsite, which misleads the matching and
243// causes a lot of false positives report. Hence, we want to filter them out
244// from the profile map during the profile generation time. The profiles are all
245// cold functions, it won't have perf impact.
246void ProfileGeneratorBase::filterAmbiguousProfile(SampleProfileMap &Profiles) {
247 for (auto I = Profiles.begin(); I != Profiles.end();) {
248 auto FS = I++;
249 if (filterAmbiguousProfile(FS&: FS->second))
250 Profiles.erase(It: 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 all
259 disjoint ranges and their sample count. BoundaryPoint contains the count
260 multiple samples begin/end at this points.
261
262 |<--100-->| Sample1
263 |<------200------>| Sample2
264 A B C
265
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 no
270 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 point
278 uint64_t BeginCount = UINT64_MAX;
279 // Sum of sample counts ending at this point
280 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 two
301 disjoint region of
302
303 [A,B]: 300
304 [B+1,C]: 200
305
306 If there is a boundary point that both begin and end, the point itself
307 becomes a separate disjoint region. For example, if we have original
308 ranges of
309
310 |<--- 100 --->|
311 |<--- 200 --->|
312 A B C
313
314 there are three boundary points with their begin/end counts of
315
316 A: (100, 0)
317 B: (200, 100)
318 C: (0, 200)
319
320 the disjoint ranges would be
321
322 [A, B-1]: 100
323 [B, B]: 300
324 [B+1, C]: 200.
325
326 Example for zero value range:
327
328 |<--- 100 --->|
329 |<--- 200 --->|
330 |<--------------- 0 ----------------->|
331 A B C D E F
332
333 [A, B-1] : 0
334 [B, C] : 100
335 [C+1, D-1]: 0
336 [D, E] : 200
337 [E+1, F] : 0
338 */
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 BeginAddress
357 // and the next valid address
358 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, this
380 // means we consume all the ranges before, thus mark BeginAddress as
381 // UINT64_MAX. e.g. supposing we have two non-overlapping ranges:
382 // [<---- 10 ---->]
383 // [<---- 20 ---->]
384 // A B C D
385 // The BeginAddress(B+1) will reset to invalid(UINT64_MAX), so we won't
386 // 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 location
397 uint32_t Discriminator = getBaseDiscriminator(Discriminator: 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 at
401 // the location instead of SUM.
402 Count *= getDuplicationFactor(Discriminator: LeafLoc.Location.Discriminator);
403
404 ErrorOr<uint64_t> R =
405 FunctionProfile.findSamplesAt(LineOffset: LeafLoc.Location.LineOffset, Discriminator);
406
407 uint64_t PreviousCount = R ? R.get() : 0;
408 if (PreviousCount <= Count) {
409 FunctionProfile.addBodySamples(LineOffset: LeafLoc.Location.LineOffset, Discriminator,
410 Num: 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 SmallPtrSet<const BinaryFunction *, 0> ProfiledFunctions;
437 if (collectFunctionsFromRawProfile(ProfiledFunctions))
438 Binary->setProfiledFunctions(ProfiledFunctions);
439 else if (collectFunctionsFromLLVMProfile(ProfiledFunctions))
440 Binary->setProfiledFunctions(ProfiledFunctions);
441 else
442 llvm_unreachable("Unsupported input profile");
443}
444
445bool ProfileGeneratorBase::collectFunctionsFromRawProfile(
446 SmallPtrSetImpl<const BinaryFunction *> &ProfiledFunctions) {
447 if (!SampleCounters)
448 return false;
449 // Go through all the stacks, ranges and branches in sample counters, use
450 // the start of the range to look up the function it belongs and record the
451 // function.
452 for (const auto &CI : *SampleCounters) {
453 if (const auto *CtxKey = dyn_cast<AddrBasedCtxKey>(Val: CI.first.getPtr())) {
454 for (auto StackAddr : CtxKey->Context) {
455 if (FuncRange *FRange = Binary->findFuncRange(Address: StackAddr))
456 ProfiledFunctions.insert(Ptr: 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(Address: StartAddress))
463 ProfiledFunctions.insert(Ptr: 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(Address: SourceAddress))
470 ProfiledFunctions.insert(Ptr: FRange->Func);
471 if (FuncRange *FRange = Binary->findFuncRange(Address: TargetAddress))
472 ProfiledFunctions.insert(Ptr: FRange->Func);
473 }
474 }
475 return true;
476}
477
478bool ProfileGenerator::collectFunctionsFromLLVMProfile(
479 SmallPtrSetImpl<const BinaryFunction *> &ProfiledFunctions) {
480 for (const auto &FS : ProfileMap) {
481 if (auto *Func = Binary->getBinaryFunction(FName: FS.second.getFunction()))
482 ProfiledFunctions.insert(Ptr: Func);
483 }
484 return true;
485}
486
487bool CSProfileGenerator::collectFunctionsFromLLVMProfile(
488 SmallPtrSetImpl<const BinaryFunction *> &ProfiledFunctions) {
489 for (auto *Node : ContextTracker) {
490 if (!Node->getFuncName().empty())
491 if (auto *Func = Binary->getBinaryFunction(FName: Node->getFuncName()))
492 ProfiledFunctions.insert(Ptr: Func);
493 }
494 return true;
495}
496
497FunctionSamples &
498ProfileGenerator::getTopLevelFunctionProfile(FunctionId FuncName) {
499 SampleContext Context(FuncName);
500 return ProfileMap.create(Ctx: Context);
501}
502
503void ProfileGenerator::generateProfile() {
504 NamedRegionTimer T("generate", "Generate profile", "profgen", "llvm-profgen",
505 TimeProfGen);
506 collectProfiledFunctions();
507
508 if (Binary->usePseudoProbes()) {
509 Binary->decodePseudoProbe();
510 if (LoadFunctionFromSymbol)
511 Binary->loadSymbolsFromPseudoProbe();
512 }
513
514 if (SampleCounters) {
515 if (Binary->usePseudoProbes()) {
516 generateProbeBasedProfile();
517 } else {
518 generateLineNumBasedProfile();
519 }
520 }
521
522 postProcessProfiles();
523}
524
525void ProfileGeneratorBase::markAllContextPreinlined(
526 SampleProfileMap &ProfileMap) {
527 for (auto &I : ProfileMap)
528 I.second.setContextAttribute(ContextShouldBeInlined);
529 FunctionSamples::ProfileIsPreInlined = true;
530}
531
532void ProfileGenerator::postProcessProfiles() {
533 computeSummaryAndThreshold(ProfileMap);
534 trimColdProfiles(ColdCntThreshold: ColdCountThreshold);
535 filterAmbiguousProfile(Profiles&: ProfileMap);
536 if (MarkAllContextPreinlined)
537 markAllContextPreinlined(ProfileMap);
538 calculateAndShowDensity(Profiles: ProfileMap);
539}
540
541void ProfileGenerator::trimColdProfiles(uint64_t ColdCntThreshold) {
542 if (!TrimColdProfile)
543 return;
544
545 // Move cold profiles into a tmp container.
546 std::vector<hash_code> ColdProfileHashes;
547 for (const auto &I : ProfileMap) {
548 if (I.second.getTotalSamples() < ColdCntThreshold)
549 ColdProfileHashes.emplace_back(args: I.first);
550 }
551
552 // Remove the cold profile from ProfileMap.
553 for (const auto &I : ColdProfileHashes)
554 ProfileMap.erase(Key: I);
555}
556
557void ProfileGenerator::generateLineNumBasedProfile() {
558 assert(SampleCounters->size() == 1 &&
559 "Must have one entry for profile generation.");
560 const SampleCounter &SC = SampleCounters->begin()->second;
561 // Fill in function body samples
562 populateBodySamplesForAllFunctions(RangeCounter: SC.RangeCounter);
563 // Fill in boundary sample counts as well as call site samples for calls
564 populateBoundarySamplesForAllFunctions(BranchCounters: SC.BranchCounter);
565 populateTypeSamplesForAllFunctions(DataAccessSamples: SC.DataAccessCounter);
566
567 updateFunctionSamples();
568}
569
570void ProfileGenerator::generateProbeBasedProfile() {
571 assert(SampleCounters->size() == 1 &&
572 "Must have one entry for profile generation.");
573 // Enable pseudo probe functionalities in SampleProf
574 FunctionSamples::ProfileIsProbeBased = true;
575 const SampleCounter &SC = SampleCounters->begin()->second;
576 // Fill in function body samples
577 populateBodySamplesWithProbesForAllFunctions(RangeCounter: SC.RangeCounter);
578 // Fill in boundary sample counts as well as call site samples for calls
579 populateBoundarySamplesWithProbesForAllFunctions(BranchCounters: SC.BranchCounter);
580
581 updateFunctionSamples();
582}
583
584void ProfileGenerator::populateBodySamplesWithProbesForAllFunctions(
585 const RangeSample &RangeCounter) {
586 ProbeCounterMap ProbeCounter;
587 // preprocessRangeCounter returns disjoint ranges, so no longer to redo it
588 // inside extractProbesFromRange.
589 extractProbesFromRange(RangeCounter: preprocessRangeCounter(RangeCounter), ProbeCounter,
590 FindDisjointRanges: false);
591
592 for (const auto &PI : ProbeCounter) {
593 const MCDecodedPseudoProbe *Probe = PI.first;
594 uint64_t Count = PI.second;
595 SampleContextFrameVector FrameVec;
596 Binary->getInlineContextForProbe(Probe, InlineContextStack&: FrameVec, IncludeLeaf: true);
597 FunctionSamples &FunctionProfile =
598 getLeafProfileAndAddTotalSamples(FrameVec, Count);
599 FunctionProfile.addBodySamples(LineOffset: Probe->getIndex(), Discriminator: Probe->getDiscriminator(),
600 Num: Count);
601 if (Probe->isEntry())
602 FunctionProfile.addHeadSamples(Num: Count);
603 }
604}
605
606void ProfileGenerator::populateBoundarySamplesWithProbesForAllFunctions(
607 const BranchSample &BranchCounters) {
608 for (const auto &Entry : BranchCounters) {
609 uint64_t SourceAddress = Entry.first.first;
610 uint64_t TargetAddress = Entry.first.second;
611 uint64_t Count = Entry.second;
612 assert(Count != 0 && "Unexpected zero weight branch");
613
614 StringRef CalleeName = getCalleeNameForAddress(TargetAddress);
615 if (CalleeName.size() == 0)
616 continue;
617
618 const MCDecodedPseudoProbe *CallProbe =
619 Binary->getCallProbeForAddr(Address: SourceAddress);
620 if (CallProbe == nullptr)
621 continue;
622
623 // Record called target sample and its count.
624 SampleContextFrameVector FrameVec;
625 Binary->getInlineContextForProbe(Probe: CallProbe, InlineContextStack&: FrameVec, IncludeLeaf: true);
626
627 if (!FrameVec.empty()) {
628 FunctionSamples &FunctionProfile =
629 getLeafProfileAndAddTotalSamples(FrameVec, Count: 0);
630 FunctionProfile.addCalledTargetSamples(
631 LineOffset: FrameVec.back().Location.LineOffset,
632 Discriminator: FrameVec.back().Location.Discriminator, Func: FunctionId(CalleeName),
633 Num: Count);
634 }
635 }
636}
637
638FunctionSamples &ProfileGenerator::getLeafProfileAndAddTotalSamples(
639 const SampleContextFrameVector &FrameVec, uint64_t Count) {
640 // Get top level profile
641 FunctionSamples *FunctionProfile =
642 &getTopLevelFunctionProfile(FuncName: FrameVec[0].Func);
643 FunctionProfile->addTotalSamples(Num: Count);
644 if (Binary->usePseudoProbes()) {
645 const auto *FuncDesc = Binary->getFuncDescForGUID(
646 GUID: FunctionProfile->getFunction().getHashCode());
647 FunctionProfile->setFunctionHash(FuncDesc->FuncHash);
648 }
649
650 for (size_t I = 1; I < FrameVec.size(); I++) {
651 LineLocation Callsite(
652 FrameVec[I - 1].Location.LineOffset,
653 getBaseDiscriminator(Discriminator: FrameVec[I - 1].Location.Discriminator));
654 FunctionSamplesMap &SamplesMap =
655 FunctionProfile->functionSamplesAt(Loc: Callsite);
656 auto Ret = SamplesMap.emplace(args: FrameVec[I].Func, args: FunctionSamples());
657 if (Ret.second) {
658 SampleContext Context(FrameVec[I].Func);
659 Ret.first->second.setContext(Context);
660 }
661 FunctionProfile = &Ret.first->second;
662 FunctionProfile->addTotalSamples(Num: Count);
663 if (Binary->usePseudoProbes()) {
664 const auto *FuncDesc = Binary->getFuncDescForGUID(
665 GUID: FunctionProfile->getFunction().getHashCode());
666 FunctionProfile->setFunctionHash(FuncDesc->FuncHash);
667 }
668 }
669
670 return *FunctionProfile;
671}
672
673RangeSample
674ProfileGenerator::preprocessRangeCounter(const RangeSample &RangeCounter) {
675 RangeSample Ranges(RangeCounter.begin(), RangeCounter.end());
676 if (FillZeroForAllFuncs) {
677 for (auto &FuncI : Binary->getAllBinaryFunctions()) {
678 for (auto &R : FuncI.second.Ranges) {
679 Ranges[{R.first, R.second - 1}] += 0;
680 }
681 }
682 } else {
683 // For each range, we search for all ranges of the function it belongs to
684 // and initialize it with zero count, so it remains zero if doesn't hit any
685 // samples. This is to be consistent with compiler that interpret zero count
686 // as unexecuted(cold).
687 for (const auto &I : RangeCounter) {
688 uint64_t StartAddress = I.first.first;
689 for (const auto &Range : Binary->getRanges(Address: StartAddress))
690 Ranges[{Range.first, Range.second - 1}] += 0;
691 }
692 }
693 RangeSample DisjointRanges;
694 findDisjointRanges(DisjointRanges, Ranges);
695 return DisjointRanges;
696}
697
698void ProfileGenerator::populateBodySamplesForAllFunctions(
699 const RangeSample &RangeCounter) {
700 for (const auto &Range : preprocessRangeCounter(RangeCounter)) {
701 uint64_t RangeBegin = Range.first.first;
702 uint64_t RangeEnd = Range.first.second;
703 uint64_t Count = Range.second;
704
705 InstructionPointer IP(Binary, RangeBegin, true);
706 // Disjoint ranges may have range in the middle of two instr,
707 // e.g. If Instr1 at Addr1, and Instr2 at Addr2, disjoint range
708 // can be Addr1+1 to Addr2-1. We should ignore such range.
709 if (IP.Address > RangeEnd)
710 continue;
711
712 do {
713 const SampleContextFrameVector FrameVec =
714 Binary->getFrameLocationStack(Address: IP.Address);
715 if (!FrameVec.empty()) {
716 // FIXME: As accumulating total count per instruction caused some
717 // regression, we changed to accumulate total count per byte as a
718 // workaround. Tuning hotness threshold on the compiler side might be
719 // necessary in the future.
720 FunctionSamples &FunctionProfile = getLeafProfileAndAddTotalSamples(
721 FrameVec, Count: Count * Binary->getInstSize(Address: IP.Address));
722 updateBodySamplesforFunctionProfile(FunctionProfile, LeafLoc: FrameVec.back(),
723 Count);
724 }
725 } while (IP.advance() && IP.Address <= RangeEnd);
726 }
727}
728
729StringRef
730ProfileGeneratorBase::getCalleeNameForAddress(uint64_t TargetAddress) {
731 // Get the function range by branch target if it's a call branch.
732 auto *FRange = Binary->findFuncRangeForStartAddr(Address: TargetAddress);
733
734 // We won't accumulate sample count for a range whose start is not the real
735 // function entry such as outlined function or inner labels.
736 if (!FRange || !FRange->IsFuncEntry)
737 return StringRef();
738
739 // DWARF and symbol table may have mismatching function names. Instead, we'll
740 // try to use its pseudo probe name first.
741 if (Binary->usePseudoProbes()) {
742 auto FuncName = Binary->findPseudoProbeName(Func: FRange->Func);
743 if (FuncName.size())
744 return FunctionSamples::getCanonicalFnName(FnName: FuncName);
745 }
746
747 return FunctionSamples::getCanonicalFnName(FnName: FRange->getFuncName());
748}
749
750void ProfileGenerator::populateBoundarySamplesForAllFunctions(
751 const BranchSample &BranchCounters) {
752 for (const auto &Entry : BranchCounters) {
753 uint64_t SourceAddress = Entry.first.first;
754 uint64_t TargetAddress = Entry.first.second;
755 uint64_t Count = Entry.second;
756 assert(Count != 0 && "Unexpected zero weight branch");
757
758 StringRef CalleeName = getCalleeNameForAddress(TargetAddress);
759 if (CalleeName.size() == 0)
760 continue;
761 // Record called target sample and its count.
762 const SampleContextFrameVector &FrameVec =
763 Binary->getCachedFrameLocationStack(Address: SourceAddress);
764 if (!FrameVec.empty()) {
765 FunctionSamples &FunctionProfile =
766 getLeafProfileAndAddTotalSamples(FrameVec, Count: 0);
767 FunctionProfile.addCalledTargetSamples(
768 LineOffset: FrameVec.back().Location.LineOffset,
769 Discriminator: getBaseDiscriminator(Discriminator: FrameVec.back().Location.Discriminator),
770 Func: FunctionId(CalleeName), Num: Count);
771 }
772 // Add head samples for callee.
773 FunctionSamples &CalleeProfile =
774 getTopLevelFunctionProfile(FuncName: FunctionId(CalleeName));
775 CalleeProfile.addHeadSamples(Num: Count);
776 }
777}
778
779void ProfileGenerator::populateTypeSamplesForAllFunctions(
780 const DataAccessSample &DataAccessSamples) {
781 // For each instruction with vtable accesses, get its symbolized inline
782 // stack, and add the vtable counters to the function samples.
783 for (const auto &[IpData, Count] : DataAccessSamples) {
784 uint64_t InstAddr = IpData.first;
785 const SampleContextFrameVector &FrameVec =
786 Binary->getCachedFrameLocationStack(Address: InstAddr,
787 /* UseProbeDiscriminator= */ false);
788 if (!FrameVec.empty()) {
789 FunctionSamples &FunctionProfile =
790 getLeafProfileAndAddTotalSamples(FrameVec, /* Count= */ 0);
791 LineLocation Loc(
792 FrameVec.back().Location.LineOffset,
793 getBaseDiscriminator(Discriminator: FrameVec.back().Location.Discriminator));
794 FunctionProfile.addTypeSamplesAt(Loc, Type: FunctionId(IpData.second), Count);
795 }
796 }
797}
798
799void ProfileGeneratorBase::calculateBodySamplesAndSize(
800 const FunctionSamples &FSamples, uint64_t &TotalBodySamples,
801 uint64_t &FuncBodySize) {
802 // Note that ideally the size should be the number of function instruction.
803 // However, for probe-based profile, we don't have the accurate instruction
804 // count for each probe, instead, the probe sample is the samples count for
805 // the block, which is equivelant to
806 // total_instruction_samples/num_of_instruction in one block. Hence, we use
807 // the number of probe as a proxy for the function's size.
808 FuncBodySize += FSamples.getBodySamples().size();
809
810 // The accumulated body samples re-calculated here could be different from the
811 // TotalSamples(getTotalSamples) field of FunctionSamples for line-number
812 // based profile. The reason is that TotalSamples is the sum of all the
813 // samples of the machine instruction in one source-code line, however, the
814 // entry of Bodysamples is the only max number of them, so the TotalSamples is
815 // usually much bigger than the accumulated body samples as one souce-code
816 // line can emit many machine instructions. We observed a regression when we
817 // switched to use the accumulated body samples(by using
818 // -update-total-samples). Hence, it's safer to re-calculate here to avoid
819 // such discrepancy. There is no problem for probe-based profile, as the
820 // TotalSamples is exactly the same as the accumulated body samples.
821 for (const auto &I : FSamples.getBodySamples())
822 TotalBodySamples += I.second.getSamples();
823
824 for (const auto &CallsiteSamples : FSamples.getCallsiteSamples())
825 for (const auto &Callee : CallsiteSamples.second) {
826 // For binary-level density, the inlinees' samples and size should be
827 // included in the calculation.
828 calculateBodySamplesAndSize(FSamples: Callee.second, TotalBodySamples,
829 FuncBodySize);
830 }
831}
832
833// Calculate Profile-density:
834// Calculate the density for each function and sort them in descending order,
835// keep accumulating their total samples unitl it exceeds the
836// percentage_threshold(cut-off) of total profile samples, the profile-density
837// is the last(minimum) function-density of the processed functions, which means
838// all the functions hot to perf are on good density if the profile-density is
839// good. The percentage_threshold(--profile-density-cutoff-hot) is configurable
840// depending on how much regression the system want to tolerate.
841double
842ProfileGeneratorBase::calculateDensity(const SampleProfileMap &Profiles) {
843 double ProfileDensity = 0.0;
844
845 uint64_t TotalProfileSamples = 0;
846 // A list of the function profile density and its total samples.
847 std::vector<std::pair<double, uint64_t>> FuncDensityList;
848 for (const auto &I : Profiles) {
849 uint64_t TotalBodySamples = 0;
850 uint64_t FuncBodySize = 0;
851 calculateBodySamplesAndSize(FSamples: I.second, TotalBodySamples, FuncBodySize);
852
853 if (FuncBodySize == 0)
854 continue;
855
856 double FuncDensity = static_cast<double>(TotalBodySamples) / FuncBodySize;
857 TotalProfileSamples += TotalBodySamples;
858 FuncDensityList.emplace_back(args&: FuncDensity, args&: TotalBodySamples);
859 }
860
861 // Sorted by the density in descending order.
862 llvm::stable_sort(Range&: FuncDensityList, C: [&](const std::pair<double, uint64_t> &A,
863 const std::pair<double, uint64_t> &B) {
864 if (A.first != B.first)
865 return A.first > B.first;
866 return A.second < B.second;
867 });
868
869 uint64_t AccumulatedSamples = 0;
870 uint32_t I = 0;
871 assert(ProfileDensityCutOffHot <= 1000000 &&
872 "The cutoff value is greater than 1000000(100%)");
873 while (AccumulatedSamples < TotalProfileSamples *
874 static_cast<float>(ProfileDensityCutOffHot) /
875 1000000 &&
876 I < FuncDensityList.size()) {
877 AccumulatedSamples += FuncDensityList[I].second;
878 ProfileDensity = FuncDensityList[I].first;
879 I++;
880 }
881
882 return ProfileDensity;
883}
884
885void ProfileGeneratorBase::calculateAndShowDensity(
886 const SampleProfileMap &Profiles) {
887 double Density = calculateDensity(Profiles);
888 showDensitySuggestion(Density);
889}
890
891FunctionSamples *
892CSProfileGenerator::getOrCreateFunctionSamples(ContextTrieNode *ContextNode,
893 bool WasLeafInlined) {
894 FunctionSamples *FProfile = ContextNode->getFunctionSamples();
895 if (!FProfile) {
896 FSamplesList.emplace_back();
897 FProfile = &FSamplesList.back();
898 FProfile->setFunction(ContextNode->getFuncName());
899 ContextNode->setFunctionSamples(FProfile);
900 }
901 // Update ContextWasInlined attribute for existing contexts.
902 // The current function can be called in two ways:
903 // - when processing a probe of the current frame
904 // - when processing the entry probe of an inlinee's frame, which
905 // is then used to update the callsite count of the current frame.
906 // The two can happen in any order, hence here we are making sure
907 // `ContextWasInlined` is always set as expected.
908 // TODO: Note that the former does not always happen if no probes of the
909 // current frame has samples, and if the latter happens, we could lose the
910 // attribute. This should be fixed.
911 if (WasLeafInlined)
912 FProfile->getContext().setAttribute(ContextWasInlined);
913 return FProfile;
914}
915
916ContextTrieNode *
917CSProfileGenerator::getOrCreateContextNode(const SampleContextFrames Context,
918 bool WasLeafInlined) {
919 ContextTrieNode *ContextNode =
920 ContextTracker.getOrCreateContextPath(Context, AllowCreate: true);
921 getOrCreateFunctionSamples(ContextNode, WasLeafInlined);
922 return ContextNode;
923}
924
925void CSProfileGenerator::generateProfile() {
926 NamedRegionTimer T("generate", "Generate CS profile", "profgen",
927 "llvm-profgen", TimeProfGen);
928 FunctionSamples::ProfileIsCS = true;
929
930 collectProfiledFunctions();
931
932 if (Binary->usePseudoProbes()) {
933 Binary->decodePseudoProbe();
934 if (InferMissingFrames)
935 initializeMissingFrameInferrer();
936 if (LoadFunctionFromSymbol)
937 Binary->loadSymbolsFromPseudoProbe();
938 }
939
940 if (SampleCounters) {
941 if (Binary->usePseudoProbes()) {
942 generateProbeBasedProfile();
943 } else {
944 generateLineNumBasedProfile();
945 }
946 }
947
948 if (Binary->getTrackFuncContextSize())
949 computeSizeForProfiledFunctions();
950
951 postProcessProfiles();
952}
953
954void CSProfileGenerator::initializeMissingFrameInferrer() {
955 Binary->getMissingContextInferrer()->initialize(SampleCounters);
956}
957
958void CSProfileGenerator::inferMissingFrames(
959 const SmallVectorImpl<uint64_t> &Context,
960 SmallVectorImpl<uint64_t> &NewContext) {
961 Binary->inferMissingFrames(Context, NewContext);
962}
963
964void CSProfileGenerator::computeSizeForProfiledFunctions() {
965 for (auto *Func : Binary->getProfiledFunctions())
966 Binary->computeInlinedContextSizeForFunc(Func);
967
968 // Flush the symbolizer to save memory.
969 Binary->flushSymbolizer();
970}
971
972void CSProfileGenerator::updateFunctionSamples() {
973 for (auto *Node : ContextTracker) {
974 FunctionSamples *FSamples = Node->getFunctionSamples();
975 if (FSamples) {
976 if (UpdateTotalSamples)
977 FSamples->updateTotalSamples();
978 FSamples->updateCallsiteSamples();
979 }
980 }
981}
982
983void CSProfileGenerator::generateLineNumBasedProfile() {
984 for (const auto &CI : *SampleCounters) {
985 const auto *CtxKey = cast<StringBasedCtxKey>(Val: CI.first.getPtr());
986
987 ContextTrieNode *ContextNode = &getRootContext();
988 // Sample context will be empty if the jump is an external-to-internal call
989 // pattern, the head samples should be added for the internal function.
990 if (!CtxKey->Context.empty()) {
991 // Get or create function profile for the range
992 ContextNode =
993 getOrCreateContextNode(Context: CtxKey->Context, WasLeafInlined: CtxKey->WasLeafInlined);
994 // Fill in function body samples
995 populateBodySamplesForFunction(FunctionProfile&: *ContextNode->getFunctionSamples(),
996 RangeCounters: CI.second.RangeCounter);
997 }
998 // Fill in boundary sample counts as well as call site samples for calls
999 populateBoundarySamplesForFunction(CallerNode: ContextNode, BranchCounters: CI.second.BranchCounter);
1000 }
1001 // Fill in call site value sample for inlined calls and also use context to
1002 // infer missing samples. Since we don't have call count for inlined
1003 // functions, we estimate it from inlinee's profile using the entry of the
1004 // body sample.
1005 populateInferredFunctionSamples(Node&: getRootContext());
1006
1007 updateFunctionSamples();
1008}
1009
1010void CSProfileGenerator::populateBodySamplesForFunction(
1011 FunctionSamples &FunctionProfile, const RangeSample &RangeCounter) {
1012 // Compute disjoint ranges first, so we can use MAX
1013 // for calculating count for each location.
1014 RangeSample Ranges;
1015 findDisjointRanges(DisjointRanges&: Ranges, Ranges: RangeCounter);
1016 for (const auto &Range : Ranges) {
1017 uint64_t RangeBegin = Range.first.first;
1018 uint64_t RangeEnd = Range.first.second;
1019 uint64_t Count = Range.second;
1020 // Disjoint ranges have introduce zero-filled gap that
1021 // doesn't belong to current context, filter them out.
1022 if (Count == 0)
1023 continue;
1024
1025 InstructionPointer IP(Binary, RangeBegin, true);
1026 // Disjoint ranges may have range in the middle of two instr,
1027 // e.g. If Instr1 at Addr1, and Instr2 at Addr2, disjoint range
1028 // can be Addr1+1 to Addr2-1. We should ignore such range.
1029 if (IP.Address > RangeEnd)
1030 continue;
1031
1032 do {
1033 auto LeafLoc = Binary->getInlineLeafFrameLoc(Address: IP.Address);
1034 if (LeafLoc) {
1035 // Recording body sample for this specific context
1036 updateBodySamplesforFunctionProfile(FunctionProfile, LeafLoc: *LeafLoc, Count);
1037 FunctionProfile.addTotalSamples(Num: Count);
1038 }
1039 } while (IP.advance() && IP.Address <= RangeEnd);
1040 }
1041}
1042
1043void CSProfileGenerator::populateBoundarySamplesForFunction(
1044 ContextTrieNode *Node, const BranchSample &BranchCounters) {
1045
1046 for (const auto &Entry : BranchCounters) {
1047 uint64_t SourceAddress = Entry.first.first;
1048 uint64_t TargetAddress = Entry.first.second;
1049 uint64_t Count = Entry.second;
1050 assert(Count != 0 && "Unexpected zero weight branch");
1051
1052 StringRef CalleeName = getCalleeNameForAddress(TargetAddress);
1053 if (CalleeName.size() == 0)
1054 continue;
1055
1056 ContextTrieNode *CallerNode = Node;
1057 LineLocation CalleeCallSite(0, 0);
1058 if (CallerNode != &getRootContext()) {
1059 // Record called target sample and its count
1060 auto LeafLoc = Binary->getInlineLeafFrameLoc(Address: SourceAddress);
1061 if (LeafLoc) {
1062 CallerNode->getFunctionSamples()->addCalledTargetSamples(
1063 LineOffset: LeafLoc->Location.LineOffset,
1064 Discriminator: getBaseDiscriminator(Discriminator: LeafLoc->Location.Discriminator),
1065 Func: FunctionId(CalleeName),
1066 Num: Count);
1067 // Record head sample for called target(callee)
1068 CalleeCallSite = LeafLoc->Location;
1069 }
1070 }
1071
1072 ContextTrieNode *CalleeNode =
1073 CallerNode->getOrCreateChildContext(CallSite: CalleeCallSite,
1074 ChildName: FunctionId(CalleeName));
1075 FunctionSamples *CalleeProfile = getOrCreateFunctionSamples(ContextNode: CalleeNode);
1076 CalleeProfile->addHeadSamples(Num: Count);
1077 }
1078}
1079
1080void CSProfileGenerator::populateInferredFunctionSamples(
1081 ContextTrieNode &Node) {
1082 // There is no call jmp sample between the inliner and inlinee, we need to use
1083 // the inlinee's context to infer inliner's context, i.e. parent(inliner)'s
1084 // sample depends on child(inlinee)'s sample, so traverse the tree in
1085 // post-order.
1086 for (auto &It : Node.getAllChildContext())
1087 populateInferredFunctionSamples(Node&: It.second);
1088
1089 FunctionSamples *CalleeProfile = Node.getFunctionSamples();
1090 if (!CalleeProfile)
1091 return;
1092 // If we already have head sample counts, we must have value profile
1093 // for call sites added already. Skip to avoid double counting.
1094 if (CalleeProfile->getHeadSamples())
1095 return;
1096 ContextTrieNode *CallerNode = Node.getParentContext();
1097 // If we don't have context, nothing to do for caller's call site.
1098 // This could happen for entry point function.
1099 if (CallerNode == &getRootContext())
1100 return;
1101
1102 LineLocation CallerLeafFrameLoc = Node.getCallSiteLoc();
1103 FunctionSamples &CallerProfile = *getOrCreateFunctionSamples(ContextNode: CallerNode);
1104 // Since we don't have call count for inlined functions, we
1105 // estimate it from inlinee's profile using entry body sample.
1106 uint64_t EstimatedCallCount = CalleeProfile->getHeadSamplesEstimate();
1107 // If we don't have samples with location, use 1 to indicate live.
1108 if (!EstimatedCallCount && !CalleeProfile->getBodySamples().size())
1109 EstimatedCallCount = 1;
1110 CallerProfile.addCalledTargetSamples(LineOffset: CallerLeafFrameLoc.LineOffset,
1111 Discriminator: CallerLeafFrameLoc.Discriminator,
1112 Func: Node.getFuncName(), Num: EstimatedCallCount);
1113 CallerProfile.addBodySamples(LineOffset: CallerLeafFrameLoc.LineOffset,
1114 Discriminator: CallerLeafFrameLoc.Discriminator,
1115 Num: EstimatedCallCount);
1116 CallerProfile.addTotalSamples(Num: EstimatedCallCount);
1117}
1118
1119void CSProfileGenerator::convertToProfileMap(
1120 ContextTrieNode &Node, SampleContextFrameVector &Context) {
1121 FunctionSamples *FProfile = Node.getFunctionSamples();
1122 if (FProfile) {
1123 Context.emplace_back(Args: Node.getFuncName(), Args: LineLocation(0, 0));
1124 // Save the new context for future references.
1125 SampleContextFrames NewContext = *Contexts.insert(x: Context).first;
1126 auto Ret = ProfileMap.emplace(Args&: NewContext, Args: std::move(*FProfile));
1127 FunctionSamples &NewProfile = Ret.first->second;
1128 NewProfile.getContext().setContext(Context: NewContext);
1129 Context.pop_back();
1130 }
1131
1132 for (auto &It : Node.getAllChildContext()) {
1133 ContextTrieNode &ChildNode = It.second;
1134 Context.emplace_back(Args: Node.getFuncName(), Args: ChildNode.getCallSiteLoc());
1135 convertToProfileMap(Node&: ChildNode, Context);
1136 Context.pop_back();
1137 }
1138}
1139
1140void CSProfileGenerator::convertToProfileMap() {
1141 assert(ProfileMap.empty() &&
1142 "ProfileMap should be empty before converting from the trie");
1143 assert(IsProfileValidOnTrie &&
1144 "Do not convert the trie twice, it's already destroyed");
1145
1146 SampleContextFrameVector Context;
1147 for (auto &It : getRootContext().getAllChildContext())
1148 convertToProfileMap(Node&: It.second, Context);
1149
1150 IsProfileValidOnTrie = false;
1151}
1152
1153void CSProfileGenerator::postProcessProfiles() {
1154 // Compute hot/cold threshold based on profile. This will be used for cold
1155 // context profile merging/trimming.
1156 computeSummaryAndThreshold();
1157
1158 // Run global pre-inliner to adjust/merge context profile based on estimated
1159 // inline decisions.
1160 if (EnableCSPreInliner) {
1161 ContextTracker.populateFuncToCtxtMap();
1162 CSPreInliner(ContextTracker, *Binary, Summary.get()).run();
1163 // Turn off the profile merger by default unless it is explicitly enabled.
1164 if (!CSProfMergeColdContext.getNumOccurrences())
1165 CSProfMergeColdContext = false;
1166 }
1167
1168 convertToProfileMap();
1169
1170 // Trim and merge cold context profile using cold threshold above.
1171 if (TrimColdProfile || CSProfMergeColdContext) {
1172 SampleContextTrimmer(ProfileMap)
1173 .trimAndMergeColdContextProfiles(
1174 ColdCountThreshold: HotCountThreshold, TrimColdContext: TrimColdProfile, MergeColdContext: CSProfMergeColdContext,
1175 ColdContextFrameLength: CSProfMaxColdContextDepth, TrimBaseProfileOnly: EnableCSPreInliner);
1176 }
1177
1178 if (GenCSNestedProfile) {
1179 ProfileConverter CSConverter(ProfileMap);
1180 CSConverter.convertCSProfiles();
1181 FunctionSamples::ProfileIsCS = false;
1182 }
1183 filterAmbiguousProfile(Profiles&: ProfileMap);
1184 if (MarkAllContextPreinlined)
1185 markAllContextPreinlined(ProfileMap);
1186 ProfileGeneratorBase::calculateAndShowDensity(Profiles: ProfileMap);
1187}
1188
1189void ProfileGeneratorBase::computeSummaryAndThreshold(
1190 SampleProfileMap &Profiles) {
1191 SampleProfileSummaryBuilder Builder(ProfileSummaryBuilder::DefaultCutoffs);
1192 Summary = Builder.computeSummaryForProfiles(Profiles);
1193 HotCountThreshold = ProfileSummaryBuilder::getHotCountThreshold(
1194 DS: (Summary->getDetailedSummary()));
1195 ColdCountThreshold = ProfileSummaryBuilder::getColdCountThreshold(
1196 DS: (Summary->getDetailedSummary()));
1197}
1198
1199void CSProfileGenerator::computeSummaryAndThreshold() {
1200 // Always merge and use context-less profile map to compute summary.
1201 SampleProfileMap ContextLessProfiles;
1202 ContextTracker.createContextLessProfileMap(ContextLessProfiles);
1203
1204 // Set the flag below to avoid merging the profile again in
1205 // computeSummaryAndThreshold
1206 FunctionSamples::ProfileIsCS = false;
1207 assert(
1208 (!UseContextLessSummary.getNumOccurrences() || UseContextLessSummary) &&
1209 "Don't set --profile-summary-contextless to false for profile "
1210 "generation");
1211 ProfileGeneratorBase::computeSummaryAndThreshold(Profiles&: ContextLessProfiles);
1212 // Recover the old value.
1213 FunctionSamples::ProfileIsCS = true;
1214}
1215
1216void ProfileGeneratorBase::extractProbesFromRange(
1217 const RangeSample &RangeCounter, ProbeCounterMap &ProbeCounter,
1218 bool FindDisjointRanges) {
1219 const RangeSample *PRanges = &RangeCounter;
1220 RangeSample Ranges;
1221 if (FindDisjointRanges) {
1222 findDisjointRanges(DisjointRanges&: Ranges, Ranges: RangeCounter);
1223 PRanges = &Ranges;
1224 }
1225
1226 for (const auto &Range : *PRanges) {
1227 uint64_t RangeBegin = Range.first.first;
1228 uint64_t RangeEnd = Range.first.second;
1229 uint64_t Count = Range.second;
1230
1231 InstructionPointer IP(Binary, RangeBegin, true);
1232 // Disjoint ranges may have range in the middle of two instr,
1233 // e.g. If Instr1 at Addr1, and Instr2 at Addr2, disjoint range
1234 // can be Addr1+1 to Addr2-1. We should ignore such range.
1235 if (IP.Address > RangeEnd)
1236 continue;
1237
1238 do {
1239 const AddressProbesMap &Address2ProbesMap =
1240 Binary->getAddress2ProbesMap();
1241 for (const MCDecodedPseudoProbe &Probe :
1242 Address2ProbesMap.find(Address: IP.Address)) {
1243 ProbeCounter[&Probe] += Count;
1244 }
1245 } while (IP.advance() && IP.Address <= RangeEnd);
1246 }
1247}
1248
1249static void extractPrefixContextStack(SampleContextFrameVector &ContextStack,
1250 const SmallVectorImpl<uint64_t> &AddrVec,
1251 ProfiledBinary *Binary) {
1252 SmallVector<const MCDecodedPseudoProbe *, 16> Probes;
1253 for (auto Address : reverse(C: AddrVec)) {
1254 const MCDecodedPseudoProbe *CallProbe =
1255 Binary->getCallProbeForAddr(Address);
1256 // These could be the cases when a probe is not found at a calliste. Cutting
1257 // off the context from here since the inliner will not know how to consume
1258 // a context with unknown callsites.
1259 // 1. for functions that are not sampled when
1260 // --decode-probe-for-profiled-functions-only is on.
1261 // 2. for a merged callsite. Callsite merging may cause the loss of original
1262 // probe IDs.
1263 // 3. for an external callsite.
1264 if (!CallProbe)
1265 break;
1266 Probes.push_back(Elt: CallProbe);
1267 }
1268
1269 std::reverse(first: Probes.begin(), last: Probes.end());
1270
1271 // Extract context stack for reusing, leaf context stack will be added
1272 // compressed while looking up function profile.
1273 for (const auto *P : Probes) {
1274 Binary->getInlineContextForProbe(Probe: P, InlineContextStack&: ContextStack, IncludeLeaf: true);
1275 }
1276}
1277
1278void CSProfileGenerator::generateProbeBasedProfile() {
1279 // Enable pseudo probe functionalities in SampleProf
1280 FunctionSamples::ProfileIsProbeBased = true;
1281 for (const auto &CI : *SampleCounters) {
1282 const AddrBasedCtxKey *CtxKey =
1283 dyn_cast<AddrBasedCtxKey>(Val: CI.first.getPtr());
1284 // Fill in function body samples from probes, also infer caller's samples
1285 // from callee's probe
1286 populateBodySamplesWithProbes(RangeCounter: CI.second.RangeCounter, CtxKey);
1287 // Fill in boundary samples for a call probe
1288 populateBoundarySamplesWithProbes(BranchCounter: CI.second.BranchCounter, CtxKey);
1289 }
1290}
1291
1292void CSProfileGenerator::populateBodySamplesWithProbes(
1293 const RangeSample &RangeCounter, const AddrBasedCtxKey *CtxKey) {
1294 ProbeCounterMap ProbeCounter;
1295 // Extract the top frame probes by looking up each address among the range in
1296 // the Address2ProbeMap
1297 extractProbesFromRange(RangeCounter, ProbeCounter);
1298 DenseMap<MCDecodedPseudoProbeInlineTree *, SmallPtrSet<FunctionSamples *, 0>>
1299 FrameSamples;
1300 for (const auto &PI : ProbeCounter) {
1301 const MCDecodedPseudoProbe *Probe = PI.first;
1302 uint64_t Count = PI.second;
1303 // Disjoint ranges have introduce zero-filled gap that
1304 // doesn't belong to current context, filter them out.
1305 if (!Probe->isBlock() || Count == 0)
1306 continue;
1307
1308 ContextTrieNode *ContextNode = getContextNodeForLeafProbe(CtxKey, LeafProbe: Probe);
1309 FunctionSamples &FunctionProfile = *ContextNode->getFunctionSamples();
1310 // Record the current frame and FunctionProfile whenever samples are
1311 // collected for non-danglie probes. This is for reporting all of the
1312 // zero count probes of the frame later.
1313 FrameSamples[Probe->getInlineTreeNode()].insert(Ptr: &FunctionProfile);
1314 FunctionProfile.addBodySamples(LineOffset: Probe->getIndex(), Discriminator: Probe->getDiscriminator(),
1315 Num: Count);
1316 FunctionProfile.addTotalSamples(Num: Count);
1317 if (Probe->isEntry()) {
1318 FunctionProfile.addHeadSamples(Num: Count);
1319 // Look up for the caller's function profile
1320 const auto *InlinerDesc = Binary->getInlinerDescForProbe(Probe);
1321 ContextTrieNode *CallerNode = ContextNode->getParentContext();
1322 if (InlinerDesc != nullptr && CallerNode != &getRootContext()) {
1323 // Since the context id will be compressed, we have to use callee's
1324 // context id to infer caller's context id to ensure they share the
1325 // same context prefix.
1326 uint64_t CallerIndex = ContextNode->getCallSiteLoc().LineOffset;
1327 uint64_t CallerDiscriminator = ContextNode->getCallSiteLoc().Discriminator;
1328 assert(CallerIndex &&
1329 "Inferred caller's location index shouldn't be zero!");
1330 assert(!CallerDiscriminator &&
1331 "Callsite probe should not have a discriminator!");
1332 FunctionSamples &CallerProfile =
1333 *getOrCreateFunctionSamples(ContextNode: CallerNode);
1334 CallerProfile.setFunctionHash(InlinerDesc->FuncHash);
1335 CallerProfile.addBodySamples(LineOffset: CallerIndex, Discriminator: CallerDiscriminator, Num: Count);
1336 CallerProfile.addTotalSamples(Num: Count);
1337 CallerProfile.addCalledTargetSamples(LineOffset: CallerIndex, Discriminator: CallerDiscriminator,
1338 Func: ContextNode->getFuncName(), Num: Count);
1339 }
1340 }
1341 }
1342
1343 // Assign zero count for remaining probes without sample hits to
1344 // differentiate from probes optimized away, of which the counts are unknown
1345 // and will be inferred by the compiler.
1346 for (auto &I : FrameSamples) {
1347 for (auto *FunctionProfile : I.second) {
1348 for (const MCDecodedPseudoProbe &Probe : I.first->getProbes()) {
1349 FunctionProfile->addBodySamples(LineOffset: Probe.getIndex(),
1350 Discriminator: Probe.getDiscriminator(), Num: 0);
1351 }
1352 }
1353 }
1354}
1355
1356void CSProfileGenerator::populateBoundarySamplesWithProbes(
1357 const BranchSample &BranchCounter, const AddrBasedCtxKey *CtxKey) {
1358 for (const auto &BI : BranchCounter) {
1359 uint64_t SourceAddress = BI.first.first;
1360 uint64_t TargetAddress = BI.first.second;
1361 uint64_t Count = BI.second;
1362 const MCDecodedPseudoProbe *CallProbe =
1363 Binary->getCallProbeForAddr(Address: SourceAddress);
1364 if (CallProbe == nullptr)
1365 continue;
1366 FunctionSamples &FunctionProfile =
1367 getFunctionProfileForLeafProbe(CtxKey, LeafProbe: CallProbe);
1368 FunctionProfile.addBodySamples(LineOffset: CallProbe->getIndex(), Discriminator: 0, Num: Count);
1369 FunctionProfile.addTotalSamples(Num: Count);
1370 StringRef CalleeName = getCalleeNameForAddress(TargetAddress);
1371 if (CalleeName.size() == 0)
1372 continue;
1373 FunctionProfile.addCalledTargetSamples(LineOffset: CallProbe->getIndex(),
1374 Discriminator: CallProbe->getDiscriminator(),
1375 Func: FunctionId(CalleeName), Num: Count);
1376 }
1377}
1378
1379ContextTrieNode *CSProfileGenerator::getContextNodeForLeafProbe(
1380 const AddrBasedCtxKey *CtxKey, const MCDecodedPseudoProbe *LeafProbe) {
1381
1382 const SmallVectorImpl<uint64_t> *PContext = &CtxKey->Context;
1383 SmallVector<uint64_t, 16> NewContext;
1384
1385 if (InferMissingFrames) {
1386 SmallVector<uint64_t, 16> Context = CtxKey->Context;
1387 // Append leaf frame for a complete inference.
1388 Context.push_back(Elt: LeafProbe->getAddress());
1389 inferMissingFrames(Context, NewContext);
1390 // Pop out the leaf probe that was pushed in above.
1391 NewContext.pop_back();
1392 PContext = &NewContext;
1393 }
1394
1395 SampleContextFrameVector ContextStack;
1396 extractPrefixContextStack(ContextStack, AddrVec: *PContext, Binary);
1397
1398 // Explicitly copy the context for appending the leaf context
1399 SampleContextFrameVector NewContextStack(ContextStack.begin(),
1400 ContextStack.end());
1401 Binary->getInlineContextForProbe(Probe: LeafProbe, InlineContextStack&: NewContextStack, IncludeLeaf: true);
1402 // For leaf inlined context with the top frame, we should strip off the top
1403 // frame's probe id, like:
1404 // Inlined stack: [foo:1, bar:2], the ContextId will be "foo:1 @ bar"
1405 auto LeafFrame = NewContextStack.back();
1406 LeafFrame.Location = LineLocation(0, 0);
1407 NewContextStack.pop_back();
1408 // Compress the context string except for the leaf frame
1409 CSProfileGenerator::compressRecursionContext(Context&: NewContextStack);
1410 CSProfileGenerator::trimContext(S&: NewContextStack);
1411 NewContextStack.push_back(Elt: LeafFrame);
1412
1413 const auto *FuncDesc = Binary->getFuncDescForGUID(GUID: LeafProbe->getGuid());
1414 bool WasLeafInlined = LeafProbe->getInlineTreeNode()->hasInlineSite();
1415 ContextTrieNode *ContextNode =
1416 getOrCreateContextNode(Context: NewContextStack, WasLeafInlined);
1417 ContextNode->getFunctionSamples()->setFunctionHash(FuncDesc->FuncHash);
1418 return ContextNode;
1419}
1420
1421FunctionSamples &CSProfileGenerator::getFunctionProfileForLeafProbe(
1422 const AddrBasedCtxKey *CtxKey, const MCDecodedPseudoProbe *LeafProbe) {
1423 return *getContextNodeForLeafProbe(CtxKey, LeafProbe)->getFunctionSamples();
1424}
1425
1426} // end namespace sampleprof
1427} // end namespace llvm
1428