1 //===- SampleProf.h - Sampling profiling format support ---------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains common definitions used in the reading and writing of
11 // sample profile data.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #ifndef LLVM_PROFILEDATA_SAMPLEPROF_H
16 #define LLVM_PROFILEDATA_SAMPLEPROF_H
17
18 #include "llvm/ADT/DenseSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringMap.h"
21 #include "llvm/ADT/StringRef.h"
22 #include "llvm/IR/Function.h"
23 #include "llvm/IR/GlobalValue.h"
24 #include "llvm/IR/Module.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/ErrorOr.h"
27 #include "llvm/Support/MathExtras.h"
28 #include <algorithm>
29 #include <cstdint>
30 #include <map>
31 #include <string>
32 #include <system_error>
33 #include <utility>
34
35 namespace llvm {
36
37 class raw_ostream;
38
39 const std::error_category &sampleprof_category();
40
41 enum class sampleprof_error {
42 success = 0,
43 bad_magic,
44 unsupported_version,
45 too_large,
46 truncated,
47 malformed,
48 unrecognized_format,
49 unsupported_writing_format,
50 truncated_name_table,
51 not_implemented,
52 counter_overflow
53 };
54
make_error_code(sampleprof_error E)55 inline std::error_code make_error_code(sampleprof_error E) {
56 return std::error_code(static_cast<int>(E), sampleprof_category());
57 }
58
MergeResult(sampleprof_error & Accumulator,sampleprof_error Result)59 inline sampleprof_error MergeResult(sampleprof_error &Accumulator,
60 sampleprof_error Result) {
61 // Prefer first error encountered as later errors may be secondary effects of
62 // the initial problem.
63 if (Accumulator == sampleprof_error::success &&
64 Result != sampleprof_error::success)
65 Accumulator = Result;
66 return Accumulator;
67 }
68
69 } // end namespace llvm
70
71 namespace std {
72
73 template <>
74 struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {};
75
76 } // end namespace std
77
78 namespace llvm {
79 namespace sampleprof {
80
81 enum SampleProfileFormat {
82 SPF_None = 0,
83 SPF_Text = 0x1,
84 SPF_Compact_Binary = 0x2,
85 SPF_GCC = 0x3,
86 SPF_Binary = 0xff
87 };
88
89 static inline uint64_t SPMagic(SampleProfileFormat Format = SPF_Binary) {
90 return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
91 uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
92 uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
93 uint64_t('2') << (64 - 56) | uint64_t(Format);
94 }
95
96 // Get the proper representation of a string in the input Format.
97 static inline StringRef getRepInFormat(StringRef Name,
98 SampleProfileFormat Format,
99 std::string &GUIDBuf) {
100 if (Name.empty())
101 return Name;
102 GUIDBuf = std::to_string(Function::getGUID(Name));
103 return (Format == SPF_Compact_Binary) ? StringRef(GUIDBuf) : Name;
104 }
105
106 static inline uint64_t SPVersion() { return 103; }
107
108 /// Represents the relative location of an instruction.
109 ///
110 /// Instruction locations are specified by the line offset from the
111 /// beginning of the function (marked by the line where the function
112 /// header is) and the discriminator value within that line.
113 ///
114 /// The discriminator value is useful to distinguish instructions
115 /// that are on the same line but belong to different basic blocks
116 /// (e.g., the two post-increment instructions in "if (p) x++; else y++;").
117 struct LineLocation {
118 LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {}
119
120 void print(raw_ostream &OS) const;
121 void dump() const;
122
123 bool operator<(const LineLocation &O) const {
124 return LineOffset < O.LineOffset ||
125 (LineOffset == O.LineOffset && Discriminator < O.Discriminator);
126 }
127
128 uint32_t LineOffset;
129 uint32_t Discriminator;
130 };
131
132 raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc);
133
134 /// Representation of a single sample record.
135 ///
136 /// A sample record is represented by a positive integer value, which
137 /// indicates how frequently was the associated line location executed.
138 ///
139 /// Additionally, if the associated location contains a function call,
140 /// the record will hold a list of all the possible called targets. For
141 /// direct calls, this will be the exact function being invoked. For
142 /// indirect calls (function pointers, virtual table dispatch), this
143 /// will be a list of one or more functions.
144 class SampleRecord {
145 public:
146 using CallTargetMap = StringMap<uint64_t>;
147
148 SampleRecord() = default;
149
150 /// Increment the number of samples for this record by \p S.
151 /// Optionally scale sample count \p S by \p Weight.
152 ///
153 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
154 /// around unsigned integers.
155 sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) {
156 bool Overflowed;
157 NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed);
158 return Overflowed ? sampleprof_error::counter_overflow
159 : sampleprof_error::success;
160 }
161
162 /// Add called function \p F with samples \p S.
163 /// Optionally scale sample count \p S by \p Weight.
164 ///
165 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
166 /// around unsigned integers.
167 sampleprof_error addCalledTarget(StringRef F, uint64_t S,
168 uint64_t Weight = 1) {
169 uint64_t &TargetSamples = CallTargets[F];
170 bool Overflowed;
171 TargetSamples =
172 SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed);
173 return Overflowed ? sampleprof_error::counter_overflow
174 : sampleprof_error::success;
175 }
176
177 /// Return true if this sample record contains function calls.
178 bool hasCalls() const { return !CallTargets.empty(); }
179
180 uint64_t getSamples() const { return NumSamples; }
181 const CallTargetMap &getCallTargets() const { return CallTargets; }
182
183 /// Merge the samples in \p Other into this record.
184 /// Optionally scale sample counts by \p Weight.
185 sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1) {
186 sampleprof_error Result = addSamples(Other.getSamples(), Weight);
187 for (const auto &I : Other.getCallTargets()) {
188 MergeResult(Result, addCalledTarget(I.first(), I.second, Weight));
189 }
190 return Result;
191 }
192
193 void print(raw_ostream &OS, unsigned Indent) const;
194 void dump() const;
195
196 private:
197 uint64_t NumSamples = 0;
198 CallTargetMap CallTargets;
199 };
200
201 raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample);
202
203 class FunctionSamples;
204
205 using BodySampleMap = std::map<LineLocation, SampleRecord>;
206 // NOTE: Using a StringMap here makes parsed profiles consume around 17% more
207 // memory, which is *very* significant for large profiles.
208 using FunctionSamplesMap = std::map<std::string, FunctionSamples>;
209 using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>;
210
211 /// Representation of the samples collected for a function.
212 ///
213 /// This data structure contains all the collected samples for the body
214 /// of a function. Each sample corresponds to a LineLocation instance
215 /// within the body of the function.
216 class FunctionSamples {
217 public:
218 FunctionSamples() = default;
219
220 void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const;
221 void dump() const;
222
223 sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) {
224 bool Overflowed;
225 TotalSamples =
226 SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed);
227 return Overflowed ? sampleprof_error::counter_overflow
228 : sampleprof_error::success;
229 }
230
231 sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) {
232 bool Overflowed;
233 TotalHeadSamples =
234 SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed);
235 return Overflowed ? sampleprof_error::counter_overflow
236 : sampleprof_error::success;
237 }
238
239 sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator,
240 uint64_t Num, uint64_t Weight = 1) {
241 return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(
242 Num, Weight);
243 }
244
245 sampleprof_error addCalledTargetSamples(uint32_t LineOffset,
246 uint32_t Discriminator,
247 StringRef FName, uint64_t Num,
248 uint64_t Weight = 1) {
249 return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(
250 FName, Num, Weight);
251 }
252
253 /// Return the number of samples collected at the given location.
254 /// Each location is specified by \p LineOffset and \p Discriminator.
255 /// If the location is not found in profile, return error.
256 ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset,
257 uint32_t Discriminator) const {
258 const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
259 if (ret == BodySamples.end())
260 return std::error_code();
261 else
262 return ret->second.getSamples();
263 }
264
265 /// Returns the call target map collected at a given location.
266 /// Each location is specified by \p LineOffset and \p Discriminator.
267 /// If the location is not found in profile, return error.
268 ErrorOr<SampleRecord::CallTargetMap>
269 findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const {
270 const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
271 if (ret == BodySamples.end())
272 return std::error_code();
273 return ret->second.getCallTargets();
274 }
275
276 /// Return the function samples at the given callsite location.
277 FunctionSamplesMap &functionSamplesAt(const LineLocation &Loc) {
278 return CallsiteSamples[Loc];
279 }
280
281 /// Returns the FunctionSamplesMap at the given \p Loc.
282 const FunctionSamplesMap *
283 findFunctionSamplesMapAt(const LineLocation &Loc) const {
284 auto iter = CallsiteSamples.find(Loc);
285 if (iter == CallsiteSamples.end())
286 return nullptr;
287 return &iter->second;
288 }
289
290 /// Returns a pointer to FunctionSamples at the given callsite location \p Loc
291 /// with callee \p CalleeName. If no callsite can be found, relax the
292 /// restriction to return the FunctionSamples at callsite location \p Loc
293 /// with the maximum total sample count.
294 const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc,
295 StringRef CalleeName) const {
296 auto iter = CallsiteSamples.find(Loc);
297 if (iter == CallsiteSamples.end())
298 return nullptr;
299 auto FS = iter->second.find(CalleeName);
300 if (FS != iter->second.end())
301 return &FS->second;
302 // If we cannot find exact match of the callee name, return the FS with
303 // the max total count.
304 uint64_t MaxTotalSamples = 0;
305 const FunctionSamples *R = nullptr;
306 for (const auto &NameFS : iter->second)
307 if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
308 MaxTotalSamples = NameFS.second.getTotalSamples();
309 R = &NameFS.second;
310 }
311 return R;
312 }
313
314 bool empty() const { return TotalSamples == 0; }
315
316 /// Return the total number of samples collected inside the function.
317 uint64_t getTotalSamples() const { return TotalSamples; }
318
319 /// Return the total number of branch samples that have the function as the
320 /// branch target. This should be equivalent to the sample of the first
321 /// instruction of the symbol. But as we directly get this info for raw
322 /// profile without referring to potentially inaccurate debug info, this
323 /// gives more accurate profile data and is preferred for standalone symbols.
324 uint64_t getHeadSamples() const { return TotalHeadSamples; }
325
326 /// Return the sample count of the first instruction of the function.
327 /// The function can be either a standalone symbol or an inlined function.
328 uint64_t getEntrySamples() const {
329 // Use either BodySamples or CallsiteSamples which ever has the smaller
330 // lineno.
331 if (!BodySamples.empty() &&
332 (CallsiteSamples.empty() ||
333 BodySamples.begin()->first < CallsiteSamples.begin()->first))
334 return BodySamples.begin()->second.getSamples();
335 if (!CallsiteSamples.empty()) {
336 uint64_t T = 0;
337 // An indirect callsite may be promoted to several inlined direct calls.
338 // We need to get the sum of them.
339 for (const auto &N_FS : CallsiteSamples.begin()->second)
340 T += N_FS.second.getEntrySamples();
341 return T;
342 }
343 return 0;
344 }
345
346 /// Return all the samples collected in the body of the function.
347 const BodySampleMap &getBodySamples() const { return BodySamples; }
348
349 /// Return all the callsite samples collected in the body of the function.
350 const CallsiteSampleMap &getCallsiteSamples() const {
351 return CallsiteSamples;
352 }
353
354 /// Merge the samples in \p Other into this one.
355 /// Optionally scale samples by \p Weight.
356 sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
357 sampleprof_error Result = sampleprof_error::success;
358 Name = Other.getName();
359 MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight));
360 MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight));
361 for (const auto &I : Other.getBodySamples()) {
362 const LineLocation &Loc = I.first;
363 const SampleRecord &Rec = I.second;
364 MergeResult(Result, BodySamples[Loc].merge(Rec, Weight));
365 }
366 for (const auto &I : Other.getCallsiteSamples()) {
367 const LineLocation &Loc = I.first;
368 FunctionSamplesMap &FSMap = functionSamplesAt(Loc);
369 for (const auto &Rec : I.second)
370 MergeResult(Result, FSMap[Rec.first].merge(Rec.second, Weight));
371 }
372 return Result;
373 }
374
375 /// Recursively traverses all children, if the total sample count of the
376 /// corresponding function is no less than \p Threshold, add its corresponding
377 /// GUID to \p S. Also traverse the BodySamples to add hot CallTarget's GUID
378 /// to \p S.
379 void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
380 uint64_t Threshold, bool isCompact) const {
381 if (TotalSamples <= Threshold)
382 return;
383 S.insert(Function::getGUID(Name));
384 // Import hot CallTargets, which may not be available in IR because full
385 // profile annotation cannot be done until backend compilation in ThinLTO.
386 for (const auto &BS : BodySamples)
387 for (const auto &TS : BS.second.getCallTargets())
388 if (TS.getValue() > Threshold) {
389 Function *Callee = M->getFunction(TS.getKey());
390 if (!Callee || !Callee->getSubprogram())
391 S.insert(isCompact ? std::stol(TS.getKey().data())
392 : Function::getGUID(TS.getKey()));
393 }
394 for (const auto &CS : CallsiteSamples)
395 for (const auto &NameFS : CS.second)
396 NameFS.second.findInlinedFunctions(S, M, Threshold, isCompact);
397 }
398
399 /// Set the name of the function.
400 void setName(StringRef FunctionName) { Name = FunctionName; }
401
402 /// Return the function name.
403 const StringRef &getName() const { return Name; }
404
405 /// Returns the line offset to the start line of the subprogram.
406 /// We assume that a single function will not exceed 65535 LOC.
407 static unsigned getOffset(const DILocation *DIL);
408
409 /// Get the FunctionSamples of the inline instance where DIL originates
410 /// from.
411 ///
412 /// The FunctionSamples of the instruction (Machine or IR) associated to
413 /// \p DIL is the inlined instance in which that instruction is coming from.
414 /// We traverse the inline stack of that instruction, and match it with the
415 /// tree nodes in the profile.
416 ///
417 /// \returns the FunctionSamples pointer to the inlined instance.
418 const FunctionSamples *findFunctionSamples(const DILocation *DIL) const;
419
420 private:
421 /// Mangled name of the function.
422 StringRef Name;
423
424 /// Total number of samples collected inside this function.
425 ///
426 /// Samples are cumulative, they include all the samples collected
427 /// inside this function and all its inlined callees.
428 uint64_t TotalSamples = 0;
429
430 /// Total number of samples collected at the head of the function.
431 /// This is an approximation of the number of calls made to this function
432 /// at runtime.
433 uint64_t TotalHeadSamples = 0;
434
435 /// Map instruction locations to collected samples.
436 ///
437 /// Each entry in this map contains the number of samples
438 /// collected at the corresponding line offset. All line locations
439 /// are an offset from the start of the function.
440 BodySampleMap BodySamples;
441
442 /// Map call sites to collected samples for the called function.
443 ///
444 /// Each entry in this map corresponds to all the samples
445 /// collected for the inlined function call at the given
446 /// location. For example, given:
447 ///
448 /// void foo() {
449 /// 1 bar();
450 /// ...
451 /// 8 baz();
452 /// }
453 ///
454 /// If the bar() and baz() calls were inlined inside foo(), this
455 /// map will contain two entries. One for all the samples collected
456 /// in the call to bar() at line offset 1, the other for all the samples
457 /// collected in the call to baz() at line offset 8.
458 CallsiteSampleMap CallsiteSamples;
459 };
460
461 raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS);
462
463 /// Sort a LocationT->SampleT map by LocationT.
464 ///
465 /// It produces a sorted list of <LocationT, SampleT> records by ascending
466 /// order of LocationT.
467 template <class LocationT, class SampleT> class SampleSorter {
468 public:
469 using SamplesWithLoc = std::pair<const LocationT, SampleT>;
470 using SamplesWithLocList = SmallVector<const SamplesWithLoc *, 20>;
471
472 SampleSorter(const std::map<LocationT, SampleT> &Samples) {
473 for (const auto &I : Samples)
474 V.push_back(&I);
475 std::stable_sort(V.begin(), V.end(),
476 [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
477 return A->first < B->first;
478 });
479 }
480
481 const SamplesWithLocList &get() const { return V; }
482
483 private:
484 SamplesWithLocList V;
485 };
486
487 } // end namespace sampleprof
488 } // end namespace llvm
489
490 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H
491