/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/ProfileData/SampleProf.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- SampleProf.h - Sampling profiling format support ---------*- 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 | | // This file contains common definitions used in the reading and writing of |
10 | | // sample profile data. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #ifndef LLVM_PROFILEDATA_SAMPLEPROF_H |
15 | | #define LLVM_PROFILEDATA_SAMPLEPROF_H |
16 | | |
17 | | #include "llvm/ADT/DenseSet.h" |
18 | | #include "llvm/ADT/SmallVector.h" |
19 | | #include "llvm/ADT/StringMap.h" |
20 | | #include "llvm/ADT/StringRef.h" |
21 | | #include "llvm/IR/Function.h" |
22 | | #include "llvm/IR/GlobalValue.h" |
23 | | #include "llvm/IR/Module.h" |
24 | | #include "llvm/Support/Debug.h" |
25 | | #include "llvm/Support/ErrorOr.h" |
26 | | #include "llvm/Support/MathExtras.h" |
27 | | #include <algorithm> |
28 | | #include <cstdint> |
29 | | #include <map> |
30 | | #include <string> |
31 | | #include <system_error> |
32 | | #include <utility> |
33 | | |
34 | | namespace llvm { |
35 | | |
36 | | class raw_ostream; |
37 | | |
38 | | const std::error_category &sampleprof_category(); |
39 | | |
40 | | enum class sampleprof_error { |
41 | | success = 0, |
42 | | bad_magic, |
43 | | unsupported_version, |
44 | | too_large, |
45 | | truncated, |
46 | | malformed, |
47 | | unrecognized_format, |
48 | | unsupported_writing_format, |
49 | | truncated_name_table, |
50 | | not_implemented, |
51 | | counter_overflow, |
52 | | ostream_seek_unsupported |
53 | | }; |
54 | | |
55 | 4.87k | inline std::error_code make_error_code(sampleprof_error E) { |
56 | 4.87k | return std::error_code(static_cast<int>(E), sampleprof_category()); |
57 | 4.87k | } |
58 | | |
59 | | inline sampleprof_error MergeResult(sampleprof_error &Accumulator, |
60 | 1.98k | sampleprof_error Result) { |
61 | 1.98k | // Prefer first error encountered as later errors may be secondary effects of |
62 | 1.98k | // the initial problem. |
63 | 1.98k | if (Accumulator == sampleprof_error::success && |
64 | 1.98k | Result != sampleprof_error::success1.98k ) |
65 | 8 | Accumulator = Result; |
66 | 1.98k | return Accumulator; |
67 | 1.98k | } |
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 | 340 | static inline uint64_t SPMagic(SampleProfileFormat Format = SPF_Binary) { |
90 | 340 | return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) | |
91 | 340 | uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) | |
92 | 340 | uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) | |
93 | 340 | uint64_t('2') << (64 - 56) | uint64_t(Format); |
94 | 340 | } Unexecuted instantiation: X86DiscriminateMemOps.cpp:llvm::sampleprof::SPMagic(llvm::sampleprof::SampleProfileFormat) Unexecuted instantiation: X86InsertPrefetch.cpp:llvm::sampleprof::SPMagic(llvm::sampleprof::SampleProfileFormat) Unexecuted instantiation: SampleProfile.cpp:llvm::sampleprof::SPMagic(llvm::sampleprof::SampleProfileFormat) Unexecuted instantiation: ProfileSummaryBuilder.cpp:llvm::sampleprof::SPMagic(llvm::sampleprof::SampleProfileFormat) Unexecuted instantiation: SampleProf.cpp:llvm::sampleprof::SPMagic(llvm::sampleprof::SampleProfileFormat) SampleProfReader.cpp:llvm::sampleprof::SPMagic(llvm::sampleprof::SampleProfileFormat) Line | Count | Source | 89 | 340 | static inline uint64_t SPMagic(SampleProfileFormat Format = SPF_Binary) { | 90 | 340 | return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) | | 91 | 340 | uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) | | 92 | 340 | uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) | | 93 | 340 | uint64_t('2') << (64 - 56) | uint64_t(Format); | 94 | 340 | } |
|
95 | | |
96 | | // Get the proper representation of a string in the input Format. |
97 | | static inline StringRef getRepInFormat(StringRef Name, |
98 | | SampleProfileFormat Format, |
99 | 560 | std::string &GUIDBuf) { |
100 | 560 | if (Name.empty()) |
101 | 84 | return Name; |
102 | 476 | GUIDBuf = std::to_string(Function::getGUID(Name)); |
103 | 476 | return (Format == SPF_Compact_Binary) ? StringRef(GUIDBuf)41 : Name435 ; |
104 | 476 | } Unexecuted instantiation: X86DiscriminateMemOps.cpp:llvm::sampleprof::getRepInFormat(llvm::StringRef, llvm::sampleprof::SampleProfileFormat, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&) Unexecuted instantiation: X86InsertPrefetch.cpp:llvm::sampleprof::getRepInFormat(llvm::StringRef, llvm::sampleprof::SampleProfileFormat, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&) SampleProfile.cpp:llvm::sampleprof::getRepInFormat(llvm::StringRef, llvm::sampleprof::SampleProfileFormat, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&) Line | Count | Source | 99 | 318 | std::string &GUIDBuf) { | 100 | 318 | if (Name.empty()) | 101 | 78 | return Name; | 102 | 240 | GUIDBuf = std::to_string(Function::getGUID(Name)); | 103 | 240 | return (Format == SPF_Compact_Binary) ? StringRef(GUIDBuf)15 : Name225 ; | 104 | 240 | } |
Unexecuted instantiation: ProfileSummaryBuilder.cpp:llvm::sampleprof::getRepInFormat(llvm::StringRef, llvm::sampleprof::SampleProfileFormat, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&) SampleProf.cpp:llvm::sampleprof::getRepInFormat(llvm::StringRef, llvm::sampleprof::SampleProfileFormat, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&) Line | Count | Source | 99 | 36 | std::string &GUIDBuf) { | 100 | 36 | if (Name.empty()) | 101 | 6 | return Name; | 102 | 30 | GUIDBuf = std::to_string(Function::getGUID(Name)); | 103 | 30 | return (Format == SPF_Compact_Binary) ? StringRef(GUIDBuf)0 : Name; | 104 | 30 | } |
SampleProfReader.cpp:llvm::sampleprof::getRepInFormat(llvm::StringRef, llvm::sampleprof::SampleProfileFormat, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&) Line | Count | Source | 99 | 206 | std::string &GUIDBuf) { | 100 | 206 | if (Name.empty()) | 101 | 0 | return Name; | 102 | 206 | GUIDBuf = std::to_string(Function::getGUID(Name)); | 103 | 206 | return (Format == SPF_Compact_Binary) ? StringRef(GUIDBuf)26 : Name180 ; | 104 | 206 | } |
|
105 | | |
106 | 25 | static inline uint64_t SPVersion() { return 103; } Unexecuted instantiation: X86DiscriminateMemOps.cpp:llvm::sampleprof::SPVersion() Unexecuted instantiation: X86InsertPrefetch.cpp:llvm::sampleprof::SPVersion() Unexecuted instantiation: SampleProfile.cpp:llvm::sampleprof::SPVersion() Unexecuted instantiation: ProfileSummaryBuilder.cpp:llvm::sampleprof::SPVersion() Unexecuted instantiation: SampleProf.cpp:llvm::sampleprof::SPVersion() SampleProfReader.cpp:llvm::sampleprof::SPVersion() Line | Count | Source | 106 | 25 | 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 | 3.55k | 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 | 11.4k | bool operator<(const LineLocation &O) const { |
124 | 11.4k | return LineOffset < O.LineOffset || |
125 | 11.4k | (7.64k LineOffset == O.LineOffset7.64k && Discriminator < O.Discriminator4.72k ); |
126 | 11.4k | } |
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 | 1.27k | 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 | 1.35k | sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) { |
156 | 1.35k | bool Overflowed; |
157 | 1.35k | NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed); |
158 | 1.35k | return Overflowed ? sampleprof_error::counter_overflow3 |
159 | 1.35k | : sampleprof_error::success1.35k ; |
160 | 1.35k | } |
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 | 176 | uint64_t Weight = 1) { |
169 | 176 | uint64_t &TargetSamples = CallTargets[F]; |
170 | 176 | bool Overflowed; |
171 | 176 | TargetSamples = |
172 | 176 | SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed); |
173 | 176 | return Overflowed ? sampleprof_error::counter_overflow2 |
174 | 176 | : sampleprof_error::success174 ; |
175 | 176 | } |
176 | | |
177 | | /// Return true if this sample record contains function calls. |
178 | 165 | bool hasCalls() const { return !CallTargets.empty(); } |
179 | | |
180 | 2.40k | uint64_t getSamples() const { return NumSamples; } |
181 | 882 | 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 | 906 | FunctionSamples() = default; |
219 | | |
220 | | void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const; |
221 | | void dump() const; |
222 | | |
223 | 758 | sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) { |
224 | 758 | bool Overflowed; |
225 | 758 | TotalSamples = |
226 | 758 | SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed); |
227 | 758 | return Overflowed ? sampleprof_error::counter_overflow3 |
228 | 758 | : sampleprof_error::success755 ; |
229 | 758 | } |
230 | | |
231 | 426 | sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) { |
232 | 426 | bool Overflowed; |
233 | 426 | TotalHeadSamples = |
234 | 426 | SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed); |
235 | 426 | return Overflowed ? sampleprof_error::counter_overflow1 |
236 | 426 | : sampleprof_error::success425 ; |
237 | 426 | } |
238 | | |
239 | | sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator, |
240 | 1.03k | uint64_t Num, uint64_t Weight = 1) { |
241 | 1.03k | return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples( |
242 | 1.03k | Num, Weight); |
243 | 1.03k | } |
244 | | |
245 | | sampleprof_error addCalledTargetSamples(uint32_t LineOffset, |
246 | | uint32_t Discriminator, |
247 | | StringRef FName, uint64_t Num, |
248 | 140 | uint64_t Weight = 1) { |
249 | 140 | return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget( |
250 | 140 | FName, Num, Weight); |
251 | 140 | } |
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 | 984 | uint32_t Discriminator) const { |
258 | 984 | const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator)); |
259 | 984 | if (ret == BodySamples.end()) |
260 | 220 | return std::error_code(); |
261 | 764 | else |
262 | 764 | return ret->second.getSamples(); |
263 | 984 | } |
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 | 72 | findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const { |
270 | 72 | const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator)); |
271 | 72 | if (ret == BodySamples.end()) |
272 | 19 | return std::error_code(); |
273 | 53 | return ret->second.getCallTargets(); |
274 | 53 | } |
275 | | |
276 | | /// Return the function samples at the given callsite location. |
277 | 224 | FunctionSamplesMap &functionSamplesAt(const LineLocation &Loc) { |
278 | 224 | return CallsiteSamples[Loc]; |
279 | 224 | } |
280 | | |
281 | | /// Returns the FunctionSamplesMap at the given \p Loc. |
282 | | const FunctionSamplesMap * |
283 | 35 | findFunctionSamplesMapAt(const LineLocation &Loc) const { |
284 | 35 | auto iter = CallsiteSamples.find(Loc); |
285 | 35 | if (iter == CallsiteSamples.end()) |
286 | 13 | return nullptr; |
287 | 22 | return &iter->second; |
288 | 22 | } |
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 | 354 | StringRef CalleeName) const { |
296 | 354 | std::string CalleeGUID; |
297 | 354 | CalleeName = getRepInFormat(CalleeName, Format, CalleeGUID); |
298 | 354 | |
299 | 354 | auto iter = CallsiteSamples.find(Loc); |
300 | 354 | if (iter == CallsiteSamples.end()) |
301 | 173 | return nullptr; |
302 | 181 | auto FS = iter->second.find(CalleeName); |
303 | 181 | if (FS != iter->second.end()) |
304 | 111 | return &FS->second; |
305 | 70 | // If we cannot find exact match of the callee name, return the FS with |
306 | 70 | // the max total count. |
307 | 70 | uint64_t MaxTotalSamples = 0; |
308 | 70 | const FunctionSamples *R = nullptr; |
309 | 70 | for (const auto &NameFS : iter->second) |
310 | 80 | if (NameFS.second.getTotalSamples() >= MaxTotalSamples) { |
311 | 74 | MaxTotalSamples = NameFS.second.getTotalSamples(); |
312 | 74 | R = &NameFS.second; |
313 | 74 | } |
314 | 70 | return R; |
315 | 70 | } |
316 | | |
317 | 124 | bool empty() const { return TotalSamples == 0; } |
318 | | |
319 | | /// Return the total number of samples collected inside the function. |
320 | 824 | uint64_t getTotalSamples() const { return TotalSamples; } |
321 | | |
322 | | /// Return the total number of branch samples that have the function as the |
323 | | /// branch target. This should be equivalent to the sample of the first |
324 | | /// instruction of the symbol. But as we directly get this info for raw |
325 | | /// profile without referring to potentially inaccurate debug info, this |
326 | | /// gives more accurate profile data and is preferred for standalone symbols. |
327 | 781 | uint64_t getHeadSamples() const { return TotalHeadSamples; } |
328 | | |
329 | | /// Return the sample count of the first instruction of the function. |
330 | | /// The function can be either a standalone symbol or an inlined function. |
331 | 157 | uint64_t getEntrySamples() const { |
332 | 157 | // Use either BodySamples or CallsiteSamples which ever has the smaller |
333 | 157 | // lineno. |
334 | 157 | if (!BodySamples.empty() && |
335 | 157 | (146 CallsiteSamples.empty()146 || |
336 | 146 | BodySamples.begin()->first < CallsiteSamples.begin()->first2 )) |
337 | 146 | return BodySamples.begin()->second.getSamples(); |
338 | 11 | if (!CallsiteSamples.empty()) { |
339 | 2 | uint64_t T = 0; |
340 | 2 | // An indirect callsite may be promoted to several inlined direct calls. |
341 | 2 | // We need to get the sum of them. |
342 | 2 | for (const auto &N_FS : CallsiteSamples.begin()->second) |
343 | 2 | T += N_FS.second.getEntrySamples(); |
344 | 2 | return T; |
345 | 2 | } |
346 | 9 | return 0; |
347 | 9 | } |
348 | | |
349 | | /// Return all the samples collected in the body of the function. |
350 | 731 | const BodySampleMap &getBodySamples() const { return BodySamples; } |
351 | | |
352 | | /// Return all the callsite samples collected in the body of the function. |
353 | 739 | const CallsiteSampleMap &getCallsiteSamples() const { |
354 | 739 | return CallsiteSamples; |
355 | 739 | } |
356 | | |
357 | | /// Merge the samples in \p Other into this one. |
358 | | /// Optionally scale samples by \p Weight. |
359 | | sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) { |
360 | | sampleprof_error Result = sampleprof_error::success; |
361 | | Name = Other.getName(); |
362 | | MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight)); |
363 | | MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight)); |
364 | | for (const auto &I : Other.getBodySamples()) { |
365 | | const LineLocation &Loc = I.first; |
366 | | const SampleRecord &Rec = I.second; |
367 | | MergeResult(Result, BodySamples[Loc].merge(Rec, Weight)); |
368 | | } |
369 | | for (const auto &I : Other.getCallsiteSamples()) { |
370 | | const LineLocation &Loc = I.first; |
371 | | FunctionSamplesMap &FSMap = functionSamplesAt(Loc); |
372 | | for (const auto &Rec : I.second) |
373 | | MergeResult(Result, FSMap[Rec.first].merge(Rec.second, Weight)); |
374 | | } |
375 | | return Result; |
376 | | } |
377 | | |
378 | | /// Recursively traverses all children, if the total sample count of the |
379 | | /// corresponding function is no less than \p Threshold, add its corresponding |
380 | | /// GUID to \p S. Also traverse the BodySamples to add hot CallTarget's GUID |
381 | | /// to \p S. |
382 | | void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M, |
383 | 14 | uint64_t Threshold) const { |
384 | 14 | if (TotalSamples <= Threshold) |
385 | 2 | return; |
386 | 12 | S.insert(getGUID(Name)); |
387 | 12 | // Import hot CallTargets, which may not be available in IR because full |
388 | 12 | // profile annotation cannot be done until backend compilation in ThinLTO. |
389 | 12 | for (const auto &BS : BodySamples) |
390 | 10 | for (const auto &TS : BS.second.getCallTargets()) |
391 | 2 | if (TS.getValue() > Threshold) { |
392 | 2 | const Function *Callee = |
393 | 2 | M->getFunction(getNameInModule(TS.getKey(), M)); |
394 | 2 | if (!Callee || !Callee->getSubprogram()0 ) |
395 | 2 | S.insert(getGUID(TS.getKey())); |
396 | 2 | } |
397 | 12 | for (const auto &CS : CallsiteSamples) |
398 | 6 | for (const auto &NameFS : CS.second) |
399 | 6 | NameFS.second.findInlinedFunctions(S, M, Threshold); |
400 | 12 | } |
401 | | |
402 | | /// Set the name of the function. |
403 | 473 | void setName(StringRef FunctionName) { Name = FunctionName; } |
404 | | |
405 | | /// Return the function name. |
406 | 372 | StringRef getName() const { return Name; } |
407 | | |
408 | | /// Return the original function name if it exists in Module \p M. |
409 | 20 | StringRef getFuncNameInModule(const Module *M) const { |
410 | 20 | return getNameInModule(Name, M); |
411 | 20 | } |
412 | | |
413 | | /// Return the canonical name for a function, taking into account |
414 | | /// suffix elision policy attributes. |
415 | 277 | static StringRef getCanonicalFnName(const Function &F) { |
416 | 277 | static const char *knownSuffixes[] = { ".llvm.", ".part." }; |
417 | 277 | auto AttrName = "sample-profile-suffix-elision-policy"; |
418 | 277 | auto Attr = F.getFnAttribute(AttrName).getValueAsString(); |
419 | 277 | if (Attr == "" || Attr == "all"6 ) { |
420 | 271 | return F.getName().split('.').first; |
421 | 271 | } else if (6 Attr == "selected"6 ) { |
422 | 3 | StringRef Cand(F.getName()); |
423 | 4 | for (const auto &Suf : knownSuffixes) { |
424 | 4 | StringRef Suffix(Suf); |
425 | 4 | auto It = Cand.rfind(Suffix); |
426 | 4 | if (It == StringRef::npos) |
427 | 3 | return Cand; |
428 | 1 | auto Dit = Cand.rfind('.'); |
429 | 1 | if (Dit == It + Suffix.size() - 1) |
430 | 1 | Cand = Cand.substr(0, It); |
431 | 1 | } |
432 | 3 | return Cand0 ; |
433 | 3 | } else if (Attr == "none") { |
434 | 3 | return F.getName(); |
435 | 3 | } else { |
436 | 0 | assert(false && "internal error: unknown suffix elision policy"); |
437 | 0 | } |
438 | 277 | return F.getName()0 ; |
439 | 277 | } |
440 | | |
441 | | /// Translate \p Name into its original name in Module. |
442 | | /// When the Format is not SPF_Compact_Binary, \p Name needs no translation. |
443 | | /// When the Format is SPF_Compact_Binary, \p Name in current FunctionSamples |
444 | | /// is actually GUID of the original function name. getNameInModule will |
445 | | /// translate \p Name in current FunctionSamples into its original name. |
446 | | /// If the original name doesn't exist in \p M, return empty StringRef. |
447 | 22 | StringRef getNameInModule(StringRef Name, const Module *M) const { |
448 | 22 | if (Format != SPF_Compact_Binary) |
449 | 13 | return Name; |
450 | 9 | // Expect CurrentModule to be initialized by GUIDToFuncNameMapper. |
451 | 9 | if (M != CurrentModule) |
452 | 9 | llvm_unreachable0 ("Input Module should be the same as CurrentModule"); |
453 | 9 | auto iter = GUIDToFuncNameMap.find(std::stoull(Name.data())); |
454 | 9 | if (iter == GUIDToFuncNameMap.end()) |
455 | 1 | return StringRef(); |
456 | 8 | return iter->second; |
457 | 8 | } |
458 | | |
459 | | /// Returns the line offset to the start line of the subprogram. |
460 | | /// We assume that a single function will not exceed 65535 LOC. |
461 | | static unsigned getOffset(const DILocation *DIL); |
462 | | |
463 | | /// Get the FunctionSamples of the inline instance where DIL originates |
464 | | /// from. |
465 | | /// |
466 | | /// The FunctionSamples of the instruction (Machine or IR) associated to |
467 | | /// \p DIL is the inlined instance in which that instruction is coming from. |
468 | | /// We traverse the inline stack of that instruction, and match it with the |
469 | | /// tree nodes in the profile. |
470 | | /// |
471 | | /// \returns the FunctionSamples pointer to the inlined instance. |
472 | | const FunctionSamples *findFunctionSamples(const DILocation *DIL) const; |
473 | | |
474 | | static SampleProfileFormat Format; |
475 | | /// GUIDToFuncNameMap saves the mapping from GUID to the symbol name, for |
476 | | /// all the function symbols defined or declared in CurrentModule. |
477 | | static DenseMap<uint64_t, StringRef> GUIDToFuncNameMap; |
478 | | static Module *CurrentModule; |
479 | | |
480 | | class GUIDToFuncNameMapper { |
481 | | public: |
482 | 94 | GUIDToFuncNameMapper(Module &M) { |
483 | 94 | if (Format != SPF_Compact_Binary) |
484 | 90 | return; |
485 | 4 | |
486 | 29 | for (const auto &F : M)4 { |
487 | 29 | StringRef OrigName = F.getName(); |
488 | 29 | GUIDToFuncNameMap.insert({Function::getGUID(OrigName), OrigName}); |
489 | 29 | /// Local to global var promotion used by optimization like thinlto |
490 | 29 | /// will rename the var and add suffix like ".llvm.xxx" to the |
491 | 29 | /// original local name. In sample profile, the suffixes of function |
492 | 29 | /// names are all stripped. Since it is possible that the mapper is |
493 | 29 | /// built in post-thin-link phase and var promotion has been done, |
494 | 29 | /// we need to add the substring of function name without the suffix |
495 | 29 | /// into the GUIDToFuncNameMap. |
496 | 29 | StringRef CanonName = getCanonicalFnName(F); |
497 | 29 | if (CanonName != OrigName) |
498 | 4 | GUIDToFuncNameMap.insert({Function::getGUID(CanonName), CanonName}); |
499 | 29 | } |
500 | 4 | CurrentModule = &M; |
501 | 4 | } |
502 | | |
503 | 94 | ~GUIDToFuncNameMapper() { |
504 | 94 | if (Format != SPF_Compact_Binary) |
505 | 90 | return; |
506 | 4 | |
507 | 4 | GUIDToFuncNameMap.clear(); |
508 | 4 | CurrentModule = nullptr; |
509 | 4 | } |
510 | | }; |
511 | | |
512 | | // Assume the input \p Name is a name coming from FunctionSamples itself. |
513 | | // If the format is SPF_Compact_Binary, the name is already a GUID and we |
514 | | // don't want to return the GUID of GUID. |
515 | 42 | static uint64_t getGUID(StringRef Name) { |
516 | 42 | return (Format == SPF_Compact_Binary) ? std::stoull(Name.data())12 |
517 | 42 | : Function::getGUID(Name)30 ; |
518 | 42 | } |
519 | | |
520 | | private: |
521 | | /// Mangled name of the function. |
522 | | StringRef Name; |
523 | | |
524 | | /// Total number of samples collected inside this function. |
525 | | /// |
526 | | /// Samples are cumulative, they include all the samples collected |
527 | | /// inside this function and all its inlined callees. |
528 | | uint64_t TotalSamples = 0; |
529 | | |
530 | | /// Total number of samples collected at the head of the function. |
531 | | /// This is an approximation of the number of calls made to this function |
532 | | /// at runtime. |
533 | | uint64_t TotalHeadSamples = 0; |
534 | | |
535 | | /// Map instruction locations to collected samples. |
536 | | /// |
537 | | /// Each entry in this map contains the number of samples |
538 | | /// collected at the corresponding line offset. All line locations |
539 | | /// are an offset from the start of the function. |
540 | | BodySampleMap BodySamples; |
541 | | |
542 | | /// Map call sites to collected samples for the called function. |
543 | | /// |
544 | | /// Each entry in this map corresponds to all the samples |
545 | | /// collected for the inlined function call at the given |
546 | | /// location. For example, given: |
547 | | /// |
548 | | /// void foo() { |
549 | | /// 1 bar(); |
550 | | /// ... |
551 | | /// 8 baz(); |
552 | | /// } |
553 | | /// |
554 | | /// If the bar() and baz() calls were inlined inside foo(), this |
555 | | /// map will contain two entries. One for all the samples collected |
556 | | /// in the call to bar() at line offset 1, the other for all the samples |
557 | | /// collected in the call to baz() at line offset 8. |
558 | | CallsiteSampleMap CallsiteSamples; |
559 | | }; |
560 | | |
561 | | raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS); |
562 | | |
563 | | /// Sort a LocationT->SampleT map by LocationT. |
564 | | /// |
565 | | /// It produces a sorted list of <LocationT, SampleT> records by ascending |
566 | | /// order of LocationT. |
567 | | template <class LocationT, class SampleT> class SampleSorter { |
568 | | public: |
569 | | using SamplesWithLoc = std::pair<const LocationT, SampleT>; |
570 | | using SamplesWithLocList = SmallVector<const SamplesWithLoc *, 20>; |
571 | | |
572 | 207 | SampleSorter(const std::map<LocationT, SampleT> &Samples) { |
573 | 207 | for (const auto &I : Samples) |
574 | 405 | V.push_back(&I); |
575 | 244 | llvm::stable_sort(V, [](const SamplesWithLoc *A, const SamplesWithLoc *B) { |
576 | 244 | return A->first < B->first; |
577 | 244 | }); llvm::sampleprof::SampleSorter<llvm::sampleprof::LineLocation, llvm::sampleprof::SampleRecord>::SampleSorter(std::__1::map<llvm::sampleprof::LineLocation, llvm::sampleprof::SampleRecord, std::__1::less<llvm::sampleprof::LineLocation>, std::__1::allocator<std::__1::pair<llvm::sampleprof::LineLocation const, llvm::sampleprof::SampleRecord> > > const&)::'lambda'(std::__1::pair<llvm::sampleprof::LineLocation const, llvm::sampleprof::SampleRecord> const*, std::__1::pair<llvm::sampleprof::LineLocation const, llvm::sampleprof::SampleRecord> const*)::operator()(std::__1::pair<llvm::sampleprof::LineLocation const, llvm::sampleprof::SampleRecord> const*, std::__1::pair<llvm::sampleprof::LineLocation const, llvm::sampleprof::SampleRecord> const*) const Line | Count | Source | 575 | 220 | llvm::stable_sort(V, [](const SamplesWithLoc *A, const SamplesWithLoc *B) { | 576 | 220 | return A->first < B->first; | 577 | 220 | }); |
llvm::sampleprof::SampleSorter<llvm::sampleprof::LineLocation, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, llvm::sampleprof::FunctionSamples, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, llvm::sampleprof::FunctionSamples> > > >::SampleSorter(std::__1::map<llvm::sampleprof::LineLocation, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, llvm::sampleprof::FunctionSamples, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, llvm::sampleprof::FunctionSamples> > >, std::__1::less<llvm::sampleprof::LineLocation>, std::__1::allocator<std::__1::pair<llvm::sampleprof::LineLocation const, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, llvm::sampleprof::FunctionSamples, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, llvm::sampleprof::FunctionSamples> > > > > > const&)::'lambda'(std::__1::pair<llvm::sampleprof::LineLocation const, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, llvm::sampleprof::FunctionSamples, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, llvm::sampleprof::FunctionSamples> > > > const*, std::__1::pair<llvm::sampleprof::LineLocation const, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, llvm::sampleprof::FunctionSamples, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, llvm::sampleprof::FunctionSamples> > > > const*)::operator()(std::__1::pair<llvm::sampleprof::LineLocation const, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, llvm::sampleprof::FunctionSamples, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, llvm::sampleprof::FunctionSamples> > > > const*, std::__1::pair<llvm::sampleprof::LineLocation const, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, llvm::sampleprof::FunctionSamples, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, llvm::sampleprof::FunctionSamples> > > > const*) const Line | Count | Source | 575 | 24 | llvm::stable_sort(V, [](const SamplesWithLoc *A, const SamplesWithLoc *B) { | 576 | 24 | return A->first < B->first; | 577 | 24 | }); |
|
578 | 207 | } llvm::sampleprof::SampleSorter<llvm::sampleprof::LineLocation, llvm::sampleprof::SampleRecord>::SampleSorter(std::__1::map<llvm::sampleprof::LineLocation, llvm::sampleprof::SampleRecord, std::__1::less<llvm::sampleprof::LineLocation>, std::__1::allocator<std::__1::pair<llvm::sampleprof::LineLocation const, llvm::sampleprof::SampleRecord> > > const&) Line | Count | Source | 572 | 128 | SampleSorter(const std::map<LocationT, SampleT> &Samples) { | 573 | 128 | for (const auto &I : Samples) | 574 | 348 | V.push_back(&I); | 575 | 128 | llvm::stable_sort(V, [](const SamplesWithLoc *A, const SamplesWithLoc *B) { | 576 | 128 | return A->first < B->first; | 577 | 128 | }); | 578 | 128 | } |
llvm::sampleprof::SampleSorter<llvm::sampleprof::LineLocation, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, llvm::sampleprof::FunctionSamples, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, llvm::sampleprof::FunctionSamples> > > >::SampleSorter(std::__1::map<llvm::sampleprof::LineLocation, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, llvm::sampleprof::FunctionSamples, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, llvm::sampleprof::FunctionSamples> > >, std::__1::less<llvm::sampleprof::LineLocation>, std::__1::allocator<std::__1::pair<llvm::sampleprof::LineLocation const, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, llvm::sampleprof::FunctionSamples, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, llvm::sampleprof::FunctionSamples> > > > > > const&) Line | Count | Source | 572 | 79 | SampleSorter(const std::map<LocationT, SampleT> &Samples) { | 573 | 79 | for (const auto &I : Samples) | 574 | 57 | V.push_back(&I); | 575 | 79 | llvm::stable_sort(V, [](const SamplesWithLoc *A, const SamplesWithLoc *B) { | 576 | 79 | return A->first < B->first; | 577 | 79 | }); | 578 | 79 | } |
|
579 | | |
580 | 207 | const SamplesWithLocList &get() const { return V; } llvm::sampleprof::SampleSorter<llvm::sampleprof::LineLocation, llvm::sampleprof::SampleRecord>::get() const Line | Count | Source | 580 | 128 | const SamplesWithLocList &get() const { return V; } |
llvm::sampleprof::SampleSorter<llvm::sampleprof::LineLocation, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, llvm::sampleprof::FunctionSamples, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, llvm::sampleprof::FunctionSamples> > > >::get() const Line | Count | Source | 580 | 79 | const SamplesWithLocList &get() const { return V; } |
|
581 | | |
582 | | private: |
583 | | SamplesWithLocList V; |
584 | | }; |
585 | | |
586 | | } // end namespace sampleprof |
587 | | } // end namespace llvm |
588 | | |
589 | | #endif // LLVM_PROFILEDATA_SAMPLEPROF_H |