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 
9 #include "ProfileGenerator.h"
10 
11 static cl::opt<std::string> OutputFilename("output", cl::value_desc("output"),
12                                            cl::Required,
13                                            cl::desc("Output profile file"));
14 static cl::alias OutputA("o", cl::desc("Alias for --output"),
15                          cl::aliasopt(OutputFilename));
16 
17 static cl::opt<SampleProfileFormat> OutputFormat(
18     "format", cl::desc("Format of output profile"), cl::init(SPF_Text),
19     cl::values(
20         clEnumValN(SPF_Binary, "binary", "Binary encoding (default)"),
21         clEnumValN(SPF_Compact_Binary, "compbinary", "Compact binary encoding"),
22         clEnumValN(SPF_Ext_Binary, "extbinary", "Extensible binary encoding"),
23         clEnumValN(SPF_Text, "text", "Text encoding"),
24         clEnumValN(SPF_GCC, "gcc",
25                    "GCC encoding (only meaningful for -sample)")));
26 
27 static cl::opt<int32_t, true> RecursionCompression(
28     "compress-recursion",
29     cl::desc("Compressing recursion by deduplicating adjacent frame "
30              "sequences up to the specified size. -1 means no size limit."),
31     cl::Hidden,
32     cl::location(llvm::sampleprof::CSProfileGenerator::MaxCompressionSize));
33 
34 static cl::opt<uint64_t> CSProfColdThres(
35     "csprof-cold-thres", cl::init(100), cl::ZeroOrMore,
36     cl::desc("Specify the total samples threshold for a context profile to "
37              "be considered cold, any cold profiles will be merged into "
38              "context-less base profiles"));
39 
40 static cl::opt<bool> CSProfKeepCold(
41     "csprof-keep-cold", cl::init(false), cl::ZeroOrMore,
42     cl::desc("This works together with --csprof-cold-thres. If the total count "
43              "of the profile after all merge is done is still smaller than the "
44              "csprof-cold-thres, it will be trimmed unless csprof-keep-cold "
45              "flag is specified."));
46 
47 using namespace llvm;
48 using namespace sampleprof;
49 
50 namespace llvm {
51 namespace sampleprof {
52 
53 // Initialize the MaxCompressionSize to -1 which means no size limit
54 int32_t CSProfileGenerator::MaxCompressionSize = -1;
55 
56 static bool
57 usePseudoProbes(const BinarySampleCounterMap &BinarySampleCounters) {
58   return BinarySampleCounters.size() &&
59          BinarySampleCounters.begin()->first->usePseudoProbes();
60 }
61 
62 std::unique_ptr<ProfileGenerator>
63 ProfileGenerator::create(const BinarySampleCounterMap &BinarySampleCounters,
64                          enum PerfScriptType SampleType) {
65   std::unique_ptr<ProfileGenerator> ProfileGenerator;
66   if (SampleType == PERF_LBR_STACK) {
67     if (usePseudoProbes(BinarySampleCounters)) {
68       ProfileGenerator.reset(
69           new PseudoProbeCSProfileGenerator(BinarySampleCounters));
70     } else {
71       ProfileGenerator.reset(new CSProfileGenerator(BinarySampleCounters));
72     }
73   } else {
74     // TODO:
75     llvm_unreachable("Unsupported perfscript!");
76   }
77 
78   return ProfileGenerator;
79 }
80 
81 void ProfileGenerator::write(std::unique_ptr<SampleProfileWriter> Writer,
82                              StringMap<FunctionSamples> &ProfileMap) {
83   Writer->write(ProfileMap);
84 }
85 
86 void ProfileGenerator::write() {
87   auto WriterOrErr = SampleProfileWriter::create(OutputFilename, OutputFormat);
88   if (std::error_code EC = WriterOrErr.getError())
89     exitWithError(EC, OutputFilename);
90   write(std::move(WriterOrErr.get()), ProfileMap);
91 }
92 
93 void ProfileGenerator::findDisjointRanges(RangeSample &DisjointRanges,
94                                           const RangeSample &Ranges) {
95 
96   /*
97   Regions may overlap with each other. Using the boundary info, find all
98   disjoint ranges and their sample count. BoundaryPoint contains the count
99   multiple samples begin/end at this points.
100 
101   |<--100-->|           Sample1
102   |<------200------>|   Sample2
103   A         B       C
104 
105   In the example above,
106   Sample1 begins at A, ends at B, its value is 100.
107   Sample2 beings at A, ends at C, its value is 200.
108   For A, BeginCount is the sum of sample begins at A, which is 300 and no
109   samples ends at A, so EndCount is 0.
110   Then boundary points A, B, and C with begin/end counts are:
111   A: (300, 0)
112   B: (0, 100)
113   C: (0, 200)
114   */
115   struct BoundaryPoint {
116     // Sum of sample counts beginning at this point
117     uint64_t BeginCount;
118     // Sum of sample counts ending at this point
119     uint64_t EndCount;
120 
121     BoundaryPoint() : BeginCount(0), EndCount(0){};
122 
123     void addBeginCount(uint64_t Count) { BeginCount += Count; }
124 
125     void addEndCount(uint64_t Count) { EndCount += Count; }
126   };
127 
128   /*
129   For the above example. With boundary points, follwing logic finds two
130   disjoint region of
131 
132   [A,B]:   300
133   [B+1,C]: 200
134 
135   If there is a boundary point that both begin and end, the point itself
136   becomes a separate disjoint region. For example, if we have original
137   ranges of
138 
139   |<--- 100 --->|
140                 |<--- 200 --->|
141   A             B             C
142 
143   there are three boundary points with their begin/end counts of
144 
145   A: (100, 0)
146   B: (200, 100)
147   C: (0, 200)
148 
149   the disjoint ranges would be
150 
151   [A, B-1]: 100
152   [B, B]:   300
153   [B+1, C]: 200.
154   */
155   std::map<uint64_t, BoundaryPoint> Boundaries;
156 
157   for (auto Item : Ranges) {
158     uint64_t Begin = Item.first.first;
159     uint64_t End = Item.first.second;
160     uint64_t Count = Item.second;
161     if (Boundaries.find(Begin) == Boundaries.end())
162       Boundaries[Begin] = BoundaryPoint();
163     Boundaries[Begin].addBeginCount(Count);
164 
165     if (Boundaries.find(End) == Boundaries.end())
166       Boundaries[End] = BoundaryPoint();
167     Boundaries[End].addEndCount(Count);
168   }
169 
170   uint64_t BeginAddress = 0;
171   int Count = 0;
172   for (auto Item : Boundaries) {
173     uint64_t Address = Item.first;
174     BoundaryPoint &Point = Item.second;
175     if (Point.BeginCount) {
176       if (BeginAddress)
177         DisjointRanges[{BeginAddress, Address - 1}] = Count;
178       Count += Point.BeginCount;
179       BeginAddress = Address;
180     }
181     if (Point.EndCount) {
182       assert(BeginAddress && "First boundary point cannot be 'end' point");
183       DisjointRanges[{BeginAddress, Address}] = Count;
184       Count -= Point.EndCount;
185       BeginAddress = Address + 1;
186     }
187   }
188 }
189 
190 FunctionSamples &
191 CSProfileGenerator::getFunctionProfileForContext(StringRef ContextStr) {
192   auto Ret = ProfileMap.try_emplace(ContextStr, FunctionSamples());
193   if (Ret.second) {
194     SampleContext FContext(Ret.first->first(), RawContext);
195     FunctionSamples &FProfile = Ret.first->second;
196     FProfile.setContext(FContext);
197   }
198   return Ret.first->second;
199 }
200 
201 void CSProfileGenerator::updateBodySamplesforFunctionProfile(
202     FunctionSamples &FunctionProfile, const FrameLocation &LeafLoc,
203     uint64_t Count) {
204   // Filter out invalid negative(int type) lineOffset
205   if (LeafLoc.second.LineOffset & 0x80000000)
206     return;
207   // Use the maximum count of samples with same line location
208   ErrorOr<uint64_t> R = FunctionProfile.findSamplesAt(
209       LeafLoc.second.LineOffset, LeafLoc.second.Discriminator);
210   uint64_t PreviousCount = R ? R.get() : 0;
211   if (PreviousCount < Count) {
212     FunctionProfile.addBodySamples(LeafLoc.second.LineOffset,
213                                    LeafLoc.second.Discriminator,
214                                    Count - PreviousCount);
215   }
216 }
217 
218 void CSProfileGenerator::populateFunctionBodySamples(
219     FunctionSamples &FunctionProfile, const RangeSample &RangeCounter,
220     ProfiledBinary *Binary) {
221   // Compute disjoint ranges first, so we can use MAX
222   // for calculating count for each location.
223   RangeSample Ranges;
224   findDisjointRanges(Ranges, RangeCounter);
225   for (auto Range : Ranges) {
226     uint64_t RangeBegin = Binary->offsetToVirtualAddr(Range.first.first);
227     uint64_t RangeEnd = Binary->offsetToVirtualAddr(Range.first.second);
228     uint64_t Count = Range.second;
229     // Disjoint ranges have introduce zero-filled gap that
230     // doesn't belong to current context, filter them out.
231     if (Count == 0)
232       continue;
233 
234     InstructionPointer IP(Binary, RangeBegin, true);
235 
236     // Disjoint ranges may have range in the middle of two instr,
237     // e.g. If Instr1 at Addr1, and Instr2 at Addr2, disjoint range
238     // can be Addr1+1 to Addr2-1. We should ignore such range.
239     if (IP.Address > RangeEnd)
240       continue;
241 
242     while (IP.Address <= RangeEnd) {
243       uint64_t Offset = Binary->virtualAddrToOffset(IP.Address);
244       auto LeafLoc = Binary->getInlineLeafFrameLoc(Offset);
245       if (LeafLoc.hasValue()) {
246         // Recording body sample for this specific context
247         updateBodySamplesforFunctionProfile(FunctionProfile, *LeafLoc, Count);
248       }
249       // Accumulate total sample count even it's a line with invalid debug info
250       FunctionProfile.addTotalSamples(Count);
251       // Move to next IP within the range
252       IP.advance();
253     }
254   }
255 }
256 
257 void CSProfileGenerator::populateFunctionBoundarySamples(
258     StringRef ContextId, FunctionSamples &FunctionProfile,
259     const BranchSample &BranchCounters, ProfiledBinary *Binary) {
260 
261   for (auto Entry : BranchCounters) {
262     uint64_t SourceOffset = Entry.first.first;
263     uint64_t TargetOffset = Entry.first.second;
264     uint64_t Count = Entry.second;
265     // Get the callee name by branch target if it's a call branch
266     StringRef CalleeName = FunctionSamples::getCanonicalFnName(
267         Binary->getFuncFromStartOffset(TargetOffset));
268     if (CalleeName.size() == 0)
269       continue;
270 
271     // Record called target sample and its count
272     auto LeafLoc = Binary->getInlineLeafFrameLoc(SourceOffset);
273     if (!LeafLoc.hasValue())
274       continue;
275     FunctionProfile.addCalledTargetSamples(LeafLoc->second.LineOffset,
276                                            LeafLoc->second.Discriminator,
277                                            CalleeName, Count);
278 
279     // Record head sample for called target(callee)
280     std::ostringstream OCalleeCtxStr;
281     if (ContextId.find(" @ ") != StringRef::npos) {
282       OCalleeCtxStr << ContextId.rsplit(" @ ").first.str();
283       OCalleeCtxStr << " @ ";
284     }
285     OCalleeCtxStr << getCallSite(*LeafLoc) << " @ " << CalleeName.str();
286 
287     FunctionSamples &CalleeProfile =
288         getFunctionProfileForContext(OCalleeCtxStr.str());
289     assert(Count != 0 && "Unexpected zero weight branch");
290     CalleeProfile.addHeadSamples(Count);
291   }
292 }
293 
294 static FrameLocation getCallerContext(StringRef CalleeContext,
295                                       StringRef &CallerNameWithContext) {
296   StringRef CallerContext = CalleeContext.rsplit(" @ ").first;
297   CallerNameWithContext = CallerContext.rsplit(':').first;
298   auto ContextSplit = CallerContext.rsplit(" @ ");
299   StringRef CallerFrameStr = ContextSplit.second.size() == 0
300                                  ? ContextSplit.first
301                                  : ContextSplit.second;
302   FrameLocation LeafFrameLoc = {"", {0, 0}};
303   StringRef Funcname;
304   SampleContext::decodeContextString(CallerFrameStr, Funcname,
305                                      LeafFrameLoc.second);
306   LeafFrameLoc.first = Funcname.str();
307   return LeafFrameLoc;
308 }
309 
310 void CSProfileGenerator::populateInferredFunctionSamples() {
311   for (const auto &Item : ProfileMap) {
312     const StringRef CalleeContext = Item.first();
313     const FunctionSamples &CalleeProfile = Item.second;
314 
315     // If we already have head sample counts, we must have value profile
316     // for call sites added already. Skip to avoid double counting.
317     if (CalleeProfile.getHeadSamples())
318       continue;
319     // If we don't have context, nothing to do for caller's call site.
320     // This could happen for entry point function.
321     if (CalleeContext.find(" @ ") == StringRef::npos)
322       continue;
323 
324     // Infer Caller's frame loc and context ID through string splitting
325     StringRef CallerContextId;
326     FrameLocation &&CallerLeafFrameLoc =
327         getCallerContext(CalleeContext, CallerContextId);
328 
329     // It's possible that we haven't seen any sample directly in the caller,
330     // in which case CallerProfile will not exist. But we can't modify
331     // ProfileMap while iterating it.
332     // TODO: created function profile for those callers too
333     if (ProfileMap.find(CallerContextId) == ProfileMap.end())
334       continue;
335     FunctionSamples &CallerProfile = ProfileMap[CallerContextId];
336 
337     // Since we don't have call count for inlined functions, we
338     // estimate it from inlinee's profile using entry body sample.
339     uint64_t EstimatedCallCount = CalleeProfile.getEntrySamples();
340     // If we don't have samples with location, use 1 to indicate live.
341     if (!EstimatedCallCount && !CalleeProfile.getBodySamples().size())
342       EstimatedCallCount = 1;
343     CallerProfile.addCalledTargetSamples(
344         CallerLeafFrameLoc.second.LineOffset,
345         CallerLeafFrameLoc.second.Discriminator,
346         CalleeProfile.getContext().getNameWithoutContext(), EstimatedCallCount);
347     CallerProfile.addBodySamples(CallerLeafFrameLoc.second.LineOffset,
348                                  CallerLeafFrameLoc.second.Discriminator,
349                                  EstimatedCallCount);
350     CallerProfile.addTotalSamples(EstimatedCallCount);
351   }
352 }
353 
354 void CSProfileGenerator::mergeAndTrimColdProfile(
355     StringMap<FunctionSamples> &ProfileMap) {
356   // Nothing to merge if sample threshold is zero
357   if (!CSProfColdThres)
358     return;
359 
360   // Filter the cold profiles from ProfileMap and move them into a tmp
361   // container
362   std::vector<std::pair<StringRef, const FunctionSamples *>> ToRemoveVec;
363   for (const auto &I : ProfileMap) {
364     const FunctionSamples &FunctionProfile = I.second;
365     if (FunctionProfile.getTotalSamples() >= CSProfColdThres)
366       continue;
367     ToRemoveVec.emplace_back(I.getKey(), &I.second);
368   }
369 
370   // Remove the code profile from ProfileMap and merge them into BaseProileMap
371   StringMap<FunctionSamples> BaseProfileMap;
372   for (const auto &I : ToRemoveVec) {
373     auto Ret = BaseProfileMap.try_emplace(
374         I.second->getContext().getNameWithoutContext(), FunctionSamples());
375     FunctionSamples &BaseProfile = Ret.first->second;
376     BaseProfile.merge(*I.second);
377     ProfileMap.erase(I.first);
378   }
379 
380   // Merge the base profiles into ProfileMap;
381   for (const auto &I : BaseProfileMap) {
382     // Filter the cold base profile
383     if (!CSProfKeepCold && I.second.getTotalSamples() < CSProfColdThres &&
384         ProfileMap.find(I.getKey()) == ProfileMap.end())
385       continue;
386     // Merge the profile if the original profile exists, otherwise just insert
387     // as a new profile
388     FunctionSamples &OrigProfile = getFunctionProfileForContext(I.getKey());
389     OrigProfile.merge(I.second);
390   }
391 }
392 
393 void CSProfileGenerator::write(std::unique_ptr<SampleProfileWriter> Writer,
394                                StringMap<FunctionSamples> &ProfileMap) {
395   mergeAndTrimColdProfile(ProfileMap);
396   // Add bracket for context key to support different profile binary format
397   StringMap<FunctionSamples> CxtWithBracketPMap;
398   for (const auto &Item : ProfileMap) {
399     std::string ContextWithBracket = "[" + Item.first().str() + "]";
400     auto Ret = CxtWithBracketPMap.try_emplace(ContextWithBracket, Item.second);
401     assert(Ret.second && "Must be a unique context");
402     SampleContext FContext(Ret.first->first(), RawContext);
403     FunctionSamples &FProfile = Ret.first->second;
404     FProfile.setName(FContext.getNameWithContext(true));
405     FProfile.setContext(FContext);
406   }
407   Writer->write(CxtWithBracketPMap);
408 }
409 
410 // Helper function to extract context prefix string stack
411 // Extract context stack for reusing, leaf context stack will
412 // be added compressed while looking up function profile
413 static void
414 extractPrefixContextStack(SmallVectorImpl<std::string> &ContextStrStack,
415                           const SmallVectorImpl<const PseudoProbe *> &Probes,
416                           ProfiledBinary *Binary) {
417   for (const auto *P : Probes) {
418     Binary->getInlineContextForProbe(P, ContextStrStack, true);
419   }
420 }
421 
422 void PseudoProbeCSProfileGenerator::generateProfile() {
423   // Enable pseudo probe functionalities in SampleProf
424   FunctionSamples::ProfileIsProbeBased = true;
425   for (const auto &BI : BinarySampleCounters) {
426     ProfiledBinary *Binary = BI.first;
427     for (const auto &CI : BI.second) {
428       const ProbeBasedCtxKey *CtxKey =
429           dyn_cast<ProbeBasedCtxKey>(CI.first.getPtr());
430       SmallVector<std::string, 16> ContextStrStack;
431       extractPrefixContextStack(ContextStrStack, CtxKey->Probes, Binary);
432       // Fill in function body samples from probes, also infer caller's samples
433       // from callee's probe
434       populateBodySamplesWithProbes(CI.second.RangeCounter, ContextStrStack,
435                                     Binary);
436       // Fill in boundary samples for a call probe
437       populateBoundarySamplesWithProbes(CI.second.BranchCounter,
438                                         ContextStrStack, Binary);
439     }
440   }
441 }
442 
443 void PseudoProbeCSProfileGenerator::extractProbesFromRange(
444     const RangeSample &RangeCounter, ProbeCounterMap &ProbeCounter,
445     ProfiledBinary *Binary) {
446   RangeSample Ranges;
447   findDisjointRanges(Ranges, RangeCounter);
448   for (const auto &Range : Ranges) {
449     uint64_t RangeBegin = Binary->offsetToVirtualAddr(Range.first.first);
450     uint64_t RangeEnd = Binary->offsetToVirtualAddr(Range.first.second);
451     uint64_t Count = Range.second;
452     // Disjoint ranges have introduce zero-filled gap that
453     // doesn't belong to current context, filter them out.
454     if (Count == 0)
455       continue;
456 
457     InstructionPointer IP(Binary, RangeBegin, true);
458 
459     // Disjoint ranges may have range in the middle of two instr,
460     // e.g. If Instr1 at Addr1, and Instr2 at Addr2, disjoint range
461     // can be Addr1+1 to Addr2-1. We should ignore such range.
462     if (IP.Address > RangeEnd)
463       continue;
464 
465     while (IP.Address <= RangeEnd) {
466       const AddressProbesMap &Address2ProbesMap =
467           Binary->getAddress2ProbesMap();
468       auto It = Address2ProbesMap.find(IP.Address);
469       if (It != Address2ProbesMap.end()) {
470         for (const auto &Probe : It->second) {
471           if (!Probe.isBlock())
472             continue;
473           ProbeCounter[&Probe] += Count;
474         }
475       }
476 
477       IP.advance();
478     }
479   }
480 }
481 
482 void PseudoProbeCSProfileGenerator::populateBodySamplesWithProbes(
483     const RangeSample &RangeCounter,
484     SmallVectorImpl<std::string> &ContextStrStack, ProfiledBinary *Binary) {
485   ProbeCounterMap ProbeCounter;
486   // Extract the top frame probes by looking up each address among the range in
487   // the Address2ProbeMap
488   extractProbesFromRange(RangeCounter, ProbeCounter, Binary);
489   for (auto PI : ProbeCounter) {
490     const PseudoProbe *Probe = PI.first;
491     uint64_t Count = PI.second;
492     FunctionSamples &FunctionProfile =
493         getFunctionProfileForLeafProbe(ContextStrStack, Probe, Binary);
494 
495     // Use InvalidProbeCount(UINT64_MAX) to mark sample count for a dangling
496     // probe. Dangling probes are the probes associated to an empty block. With
497     // this place holder, sample count on dangling probe will not be trusted by
498     // the compiler and it will rely on the counts inference algorithm to get
499     // the probe a reasonable count.
500     if (Probe->isDangling()) {
501       FunctionProfile.addBodySamplesForProbe(
502           Probe->Index, FunctionSamples::InvalidProbeCount);
503       continue;
504     }
505     FunctionProfile.addBodySamplesForProbe(Probe->Index, Count);
506     FunctionProfile.addTotalSamples(Count);
507     if (Probe->isEntry()) {
508       FunctionProfile.addHeadSamples(Count);
509       // Look up for the caller's function profile
510       const auto *InlinerDesc = Binary->getInlinerDescForProbe(Probe);
511       if (InlinerDesc != nullptr) {
512         // Since the context id will be compressed, we have to use callee's
513         // context id to infer caller's context id to ensure they share the
514         // same context prefix.
515         StringRef CalleeContextId =
516             FunctionProfile.getContext().getNameWithContext(true);
517         StringRef CallerContextId;
518         FrameLocation &&CallerLeafFrameLoc =
519             getCallerContext(CalleeContextId, CallerContextId);
520         uint64_t CallerIndex = CallerLeafFrameLoc.second.LineOffset;
521         assert(CallerIndex &&
522                "Inferred caller's location index shouldn't be zero!");
523         FunctionSamples &CallerProfile =
524             getFunctionProfileForContext(CallerContextId);
525         CallerProfile.setFunctionHash(InlinerDesc->FuncHash);
526         CallerProfile.addBodySamples(CallerIndex, 0, Count);
527         CallerProfile.addTotalSamples(Count);
528         CallerProfile.addCalledTargetSamples(
529             CallerIndex, 0,
530             FunctionProfile.getContext().getNameWithoutContext(), Count);
531       }
532     }
533   }
534 }
535 
536 void PseudoProbeCSProfileGenerator::populateBoundarySamplesWithProbes(
537     const BranchSample &BranchCounter,
538     SmallVectorImpl<std::string> &ContextStrStack, ProfiledBinary *Binary) {
539   for (auto BI : BranchCounter) {
540     uint64_t SourceOffset = BI.first.first;
541     uint64_t TargetOffset = BI.first.second;
542     uint64_t Count = BI.second;
543     uint64_t SourceAddress = Binary->offsetToVirtualAddr(SourceOffset);
544     const PseudoProbe *CallProbe = Binary->getCallProbeForAddr(SourceAddress);
545     if (CallProbe == nullptr)
546       continue;
547     FunctionSamples &FunctionProfile =
548         getFunctionProfileForLeafProbe(ContextStrStack, CallProbe, Binary);
549     FunctionProfile.addBodySamples(CallProbe->Index, 0, Count);
550     FunctionProfile.addTotalSamples(Count);
551     StringRef CalleeName = FunctionSamples::getCanonicalFnName(
552         Binary->getFuncFromStartOffset(TargetOffset));
553     if (CalleeName.size() == 0)
554       continue;
555     FunctionProfile.addCalledTargetSamples(CallProbe->Index, 0, CalleeName,
556                                            Count);
557   }
558 }
559 
560 FunctionSamples &PseudoProbeCSProfileGenerator::getFunctionProfileForLeafProbe(
561     SmallVectorImpl<std::string> &ContextStrStack,
562     const PseudoProbeFuncDesc *LeafFuncDesc) {
563   assert(ContextStrStack.size() && "Profile context must have the leaf frame");
564   // Compress the context string except for the leaf frame
565   std::string LeafFrame = ContextStrStack.back();
566   ContextStrStack.pop_back();
567   CSProfileGenerator::compressRecursionContext(ContextStrStack);
568 
569   std::ostringstream OContextStr;
570   for (uint32_t I = 0; I < ContextStrStack.size(); I++) {
571     if (OContextStr.str().size())
572       OContextStr << " @ ";
573     OContextStr << ContextStrStack[I];
574   }
575   // For leaf inlined context with the top frame, we should strip off the top
576   // frame's probe id, like:
577   // Inlined stack: [foo:1, bar:2], the ContextId will be "foo:1 @ bar"
578   if (OContextStr.str().size())
579     OContextStr << " @ ";
580   OContextStr << StringRef(LeafFrame).split(":").first.str();
581 
582   FunctionSamples &FunctionProile =
583       getFunctionProfileForContext(OContextStr.str());
584   FunctionProile.setFunctionHash(LeafFuncDesc->FuncHash);
585   return FunctionProile;
586 }
587 
588 FunctionSamples &PseudoProbeCSProfileGenerator::getFunctionProfileForLeafProbe(
589     SmallVectorImpl<std::string> &ContextStrStack, const PseudoProbe *LeafProbe,
590     ProfiledBinary *Binary) {
591   // Explicitly copy the context for appending the leaf context
592   SmallVector<std::string, 16> ContextStrStackCopy(ContextStrStack.begin(),
593                                                    ContextStrStack.end());
594   Binary->getInlineContextForProbe(LeafProbe, ContextStrStackCopy);
595   // Note that the context from probe doesn't include leaf frame,
596   // hence we need to retrieve and append the leaf frame.
597   const auto *FuncDesc = Binary->getFuncDescForGUID(LeafProbe->GUID);
598   ContextStrStackCopy.emplace_back(FuncDesc->FuncName + ":" +
599                                    Twine(LeafProbe->Index).str());
600   return getFunctionProfileForLeafProbe(ContextStrStackCopy, FuncDesc);
601 }
602 
603 } // end namespace sampleprof
604 } // end namespace llvm
605