1 | //===- bolt/Profile/DataReader.h - Perf data reader -------------*- 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 family of functions reads profile data written by the perf2bolt |
10 | // utility and stores it in memory for llvm-bolt consumption. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef BOLT_PROFILE_DATA_READER_H |
15 | #define BOLT_PROFILE_DATA_READER_H |
16 | |
17 | #include "bolt/Profile/ProfileReaderBase.h" |
18 | #include "llvm/ADT/DenseMap.h" |
19 | #include "llvm/ADT/StringMap.h" |
20 | #include "llvm/ADT/StringSet.h" |
21 | #include "llvm/Support/ErrorOr.h" |
22 | #include "llvm/Support/MemoryBuffer.h" |
23 | #include "llvm/Support/raw_ostream.h" |
24 | #include <map> |
25 | #include <unordered_map> |
26 | #include <vector> |
27 | |
28 | namespace llvm { |
29 | class MCSymbol; |
30 | |
31 | namespace bolt { |
32 | |
33 | class BinaryFunction; |
34 | |
35 | struct LBREntry { |
36 | uint64_t From; |
37 | uint64_t To; |
38 | bool Mispred; |
39 | }; |
40 | |
41 | inline raw_ostream &operator<<(raw_ostream &OS, const LBREntry &LBR) { |
42 | OS << "0x" << Twine::utohexstr(Val: LBR.From) << " -> 0x" |
43 | << Twine::utohexstr(Val: LBR.To); |
44 | return OS; |
45 | } |
46 | |
47 | struct Location { |
48 | bool IsSymbol; |
49 | StringRef Name; |
50 | uint64_t Offset; |
51 | |
52 | explicit Location(uint64_t Offset) |
53 | : IsSymbol(false), Name("[unknown]" ), Offset(Offset) {} |
54 | |
55 | Location(bool IsSymbol, StringRef Name, uint64_t Offset) |
56 | : IsSymbol(IsSymbol), Name(Name), Offset(Offset) {} |
57 | |
58 | bool operator==(const Location &RHS) const { |
59 | return IsSymbol == RHS.IsSymbol && Name == RHS.Name && |
60 | (Name == "[heap]" || Offset == RHS.Offset); |
61 | } |
62 | |
63 | bool operator<(const Location &RHS) const { |
64 | if (IsSymbol != RHS.IsSymbol) |
65 | return IsSymbol < RHS.IsSymbol; |
66 | |
67 | if (Name != RHS.Name) |
68 | return Name < RHS.Name; |
69 | |
70 | return Name != "[heap]" && Offset < RHS.Offset; |
71 | } |
72 | |
73 | friend raw_ostream &operator<<(raw_ostream &OS, const Location &Loc); |
74 | }; |
75 | |
76 | typedef std::vector<std::pair<Location, Location>> BranchContext; |
77 | |
78 | struct BranchInfo { |
79 | Location From; |
80 | Location To; |
81 | int64_t Mispreds; |
82 | int64_t Branches; |
83 | |
84 | BranchInfo(Location From, Location To, int64_t Mispreds, int64_t Branches) |
85 | : From(std::move(From)), To(std::move(To)), Mispreds(Mispreds), |
86 | Branches(Branches) {} |
87 | |
88 | bool operator==(const BranchInfo &RHS) const { |
89 | return From == RHS.From && To == RHS.To; |
90 | } |
91 | |
92 | bool operator<(const BranchInfo &RHS) const { |
93 | if (From < RHS.From) |
94 | return true; |
95 | |
96 | if (From == RHS.From) |
97 | return (To < RHS.To); |
98 | |
99 | return false; |
100 | } |
101 | |
102 | /// Merges branch and misprediction counts of \p BI with those of this object. |
103 | void mergeWith(const BranchInfo &BI); |
104 | |
105 | void print(raw_ostream &OS) const; |
106 | }; |
107 | |
108 | struct FuncBranchData { |
109 | typedef std::vector<BranchInfo> ContainerTy; |
110 | |
111 | StringRef Name; |
112 | ContainerTy Data; |
113 | ContainerTy EntryData; |
114 | |
115 | /// Total execution count for the function. |
116 | int64_t ExecutionCount{0}; |
117 | |
118 | /// Indicate if the data was used. |
119 | bool Used{false}; |
120 | |
121 | FuncBranchData() {} |
122 | |
123 | FuncBranchData(StringRef Name, ContainerTy Data) |
124 | : Name(Name), Data(std::move(Data)) {} |
125 | |
126 | FuncBranchData(StringRef Name, ContainerTy Data, ContainerTy EntryData) |
127 | : Name(Name), Data(std::move(Data)), EntryData(std::move(EntryData)) {} |
128 | |
129 | ErrorOr<const BranchInfo &> getBranch(uint64_t From, uint64_t To) const; |
130 | |
131 | /// Returns the branch info object associated with a direct call originating |
132 | /// from the given offset. If no branch info object is found, an error is |
133 | /// returned. If the offset corresponds to an indirect call the behavior is |
134 | /// undefined. |
135 | ErrorOr<const BranchInfo &> getDirectCallBranch(uint64_t From) const; |
136 | |
137 | /// Append the branch data of another function located \p Offset bytes away |
138 | /// from the entry of this function. |
139 | void appendFrom(const FuncBranchData &FBD, uint64_t Offset); |
140 | |
141 | /// Returns the total number of executed branches in this function |
142 | /// by counting the number of executed branches for each BranchInfo |
143 | uint64_t getNumExecutedBranches() const; |
144 | |
145 | /// Aggregation helpers |
146 | DenseMap<uint64_t, DenseMap<uint64_t, size_t>> IntraIndex; |
147 | DenseMap<uint64_t, DenseMap<Location, size_t>> InterIndex; |
148 | DenseMap<uint64_t, DenseMap<Location, size_t>> EntryIndex; |
149 | |
150 | void bumpBranchCount(uint64_t OffsetFrom, uint64_t OffsetTo, uint64_t Count, |
151 | uint64_t Mispreds); |
152 | void bumpCallCount(uint64_t OffsetFrom, const Location &To, uint64_t Count, |
153 | uint64_t Mispreds); |
154 | void bumpEntryCount(const Location &From, uint64_t OffsetTo, uint64_t Count, |
155 | uint64_t Mispreds); |
156 | }; |
157 | |
158 | /// MemInfo represents a single memory load from an address \p Addr at an \p |
159 | /// Offset within a function. \p Count represents how many times a particular |
160 | /// address was seen. |
161 | struct MemInfo { |
162 | Location Offset; |
163 | Location Addr; |
164 | uint64_t Count; |
165 | |
166 | bool operator==(const MemInfo &RHS) const { |
167 | return Offset == RHS.Offset && Addr == RHS.Addr; |
168 | } |
169 | |
170 | bool operator<(const MemInfo &RHS) const { |
171 | if (Offset < RHS.Offset) |
172 | return true; |
173 | |
174 | if (Offset == RHS.Offset) |
175 | return (Addr < RHS.Addr); |
176 | |
177 | return false; |
178 | } |
179 | |
180 | void mergeWith(const MemInfo &MI) { Count += MI.Count; } |
181 | |
182 | void print(raw_ostream &OS) const; |
183 | void prettyPrint(raw_ostream &OS) const; |
184 | |
185 | MemInfo(const Location &Offset, const Location &Addr, uint64_t Count = 0) |
186 | : Offset(Offset), Addr(Addr), Count(Count) {} |
187 | |
188 | friend raw_ostream &operator<<(raw_ostream &OS, const MemInfo &MI) { |
189 | MI.prettyPrint(OS); |
190 | return OS; |
191 | } |
192 | }; |
193 | |
194 | /// Helper class to store memory load events recorded in the address space of |
195 | /// a given function, analogous to FuncBranchData but for memory load events |
196 | /// instead of branches. |
197 | struct FuncMemData { |
198 | typedef std::vector<MemInfo> ContainerTy; |
199 | |
200 | StringRef Name; |
201 | ContainerTy Data; |
202 | |
203 | /// Indicate if the data was used. |
204 | bool Used{false}; |
205 | |
206 | DenseMap<uint64_t, DenseMap<Location, size_t>> EventIndex; |
207 | |
208 | /// Update \p Data with a memory event. Events with the same |
209 | /// \p Offset and \p Addr will be coalesced. |
210 | void update(const Location &Offset, const Location &Addr); |
211 | |
212 | FuncMemData() {} |
213 | |
214 | FuncMemData(StringRef Name, ContainerTy Data) |
215 | : Name(Name), Data(std::move(Data)) {} |
216 | }; |
217 | |
218 | /// Similar to BranchInfo, but instead of recording from-to address (an edge), |
219 | /// it records the address of a perf event and the number of times samples hit |
220 | /// this address. |
221 | struct SampleInfo { |
222 | Location Loc; |
223 | int64_t Hits; |
224 | |
225 | SampleInfo(Location Loc, int64_t Hits) : Loc(std::move(Loc)), Hits(Hits) {} |
226 | |
227 | bool operator==(const SampleInfo &RHS) const { return Loc == RHS.Loc; } |
228 | |
229 | bool operator<(const SampleInfo &RHS) const { |
230 | if (Loc < RHS.Loc) |
231 | return true; |
232 | |
233 | return false; |
234 | } |
235 | |
236 | void print(raw_ostream &OS) const; |
237 | |
238 | void mergeWith(const SampleInfo &SI); |
239 | }; |
240 | |
241 | /// Helper class to store samples recorded in the address space of a given |
242 | /// function, analogous to FuncBranchData but for samples instead of branches. |
243 | struct FuncSampleData { |
244 | typedef std::vector<SampleInfo> ContainerTy; |
245 | |
246 | StringRef Name; |
247 | ContainerTy Data; |
248 | |
249 | FuncSampleData(StringRef Name, ContainerTy Data) |
250 | : Name(Name), Data(std::move(Data)) {} |
251 | |
252 | /// Get the number of samples recorded in [Start, End) |
253 | uint64_t getSamples(uint64_t Start, uint64_t End) const; |
254 | |
255 | /// Aggregation helper |
256 | DenseMap<uint64_t, size_t> Index; |
257 | |
258 | void bumpCount(uint64_t Offset, uint64_t Count); |
259 | }; |
260 | |
261 | /// DataReader Class |
262 | /// |
263 | class DataReader : public ProfileReaderBase { |
264 | public: |
265 | explicit DataReader(StringRef Filename) |
266 | : ProfileReaderBase(Filename), Diag(errs()) {} |
267 | |
268 | StringRef getReaderName() const override { return "branch profile reader" ; } |
269 | |
270 | bool isTrustedSource() const override { return false; } |
271 | |
272 | Error preprocessProfile(BinaryContext &BC) override; |
273 | |
274 | Error readProfilePreCFG(BinaryContext &BC) override; |
275 | |
276 | Error readProfile(BinaryContext &BC) override; |
277 | |
278 | bool hasLocalsWithFileName() const override; |
279 | |
280 | bool mayHaveProfileData(const BinaryFunction &BF) override; |
281 | |
282 | /// Return all event names used to collect this profile |
283 | StringSet<> getEventNames() const override { return EventNames; } |
284 | |
285 | protected: |
286 | /// Read profile information available for the function. |
287 | void readProfile(BinaryFunction &BF); |
288 | |
289 | /// In functions with multiple entry points, the profile collection records |
290 | /// data for other entry points in a different function entry. This function |
291 | /// attempts to fetch extra profile data for each secondary entry point. |
292 | bool fetchProfileForOtherEntryPoints(BinaryFunction &BF); |
293 | |
294 | /// Find the best matching profile for a function after the creation of basic |
295 | /// blocks. |
296 | void matchProfileData(BinaryFunction &BF); |
297 | |
298 | /// Find the best matching memory data profile for a function before the |
299 | /// creation of basic blocks. |
300 | void matchProfileMemData(BinaryFunction &BF); |
301 | |
302 | /// Check how closely \p BranchData matches the function \p BF. |
303 | /// Return accuracy (ranging from 0.0 to 1.0) of the matching. |
304 | float evaluateProfileData(BinaryFunction &BF, |
305 | const FuncBranchData &BranchData) const; |
306 | |
307 | /// If our profile data comes from sample addresses instead of LBR entries, |
308 | /// collect sample count for all addresses in this function address space, |
309 | /// aggregating them per basic block and assigning an execution count to each |
310 | /// basic block based on the number of samples recorded at those addresses. |
311 | /// The last step is to infer edge counts based on BB execution count. Note |
312 | /// this is the opposite of the LBR way, where we infer BB execution count |
313 | /// based on edge counts. |
314 | void readSampleData(BinaryFunction &BF); |
315 | |
316 | /// Convert function-level branch data into instruction annotations. |
317 | void convertBranchData(BinaryFunction &BF) const; |
318 | |
319 | /// Update function \p BF profile with a taken branch. |
320 | /// \p Count could be 0 if verification of the branch is required. |
321 | /// |
322 | /// Return true if the branch is valid, false otherwise. |
323 | bool recordBranch(BinaryFunction &BF, uint64_t From, uint64_t To, |
324 | uint64_t Count = 1, uint64_t Mispreds = 0) const; |
325 | |
326 | /// Parses the input bolt data file into internal data structures. We expect |
327 | /// the file format to follow the syntax below. |
328 | /// |
329 | /// <is symbol?> <closest elf symbol or DSO name> <relative FROM address> |
330 | /// <is symbol?> <closest elf symbol or DSO name> <relative TO address> |
331 | /// <number of mispredictions> <number of branches> |
332 | /// |
333 | /// In <is symbol?> field we record 0 if our closest address is a DSO load |
334 | /// address or 1 if our closest address is an ELF symbol. |
335 | /// |
336 | /// Examples: |
337 | /// |
338 | /// 1 main 3fb 0 /lib/ld-2.21.so 12 4 221 |
339 | /// |
340 | /// The example records branches from symbol main, offset 3fb, to DSO ld-2.21, |
341 | /// offset 12, with 4 mispredictions and 221 branches. |
342 | /// |
343 | /// 2 t2.c/func 11 1 globalfunc 1d 0 1775 2 |
344 | /// 0 1002 2 |
345 | /// 2 t2.c/func 31 2 t2.c/func d |
346 | /// 2 t2.c/func 18 2 t2.c/func 20 |
347 | /// 0 773 2 |
348 | /// 2 t2.c/func 71 2 t2.c/func d |
349 | /// 2 t2.c/func 18 2 t2.c/func 60 |
350 | /// |
351 | /// The examples records branches from local symbol func (from t2.c), offset |
352 | /// 11, to global symbol globalfunc, offset 1d, with 1775 branches, no |
353 | /// mispreds. Of these branches, 1002 were preceded by a sequence of |
354 | /// branches from func, offset 18 to offset 20 and then from offset 31 to |
355 | /// offset d. The rest 773 branches were preceded by a different sequence |
356 | /// of branches, from func, offset 18 to offset 60 and then from offset 71 to |
357 | /// offset d. |
358 | std::error_code parse(); |
359 | |
360 | /// When no_lbr is the first line of the file, activate No LBR mode. In this |
361 | /// mode we read the addresses where samples were recorded directly instead of |
362 | /// LBR entries. The line format is almost the same, except for a missing <to> |
363 | /// triple and a missing mispredictions field: |
364 | /// |
365 | /// no_lbr |
366 | /// <is symbol?> <closest elf symbol or DSO name> <relative address> <count> |
367 | /// ... |
368 | /// |
369 | /// Example: |
370 | /// |
371 | /// no_lbr # First line of fdata file |
372 | /// 1 BZ2_compressBlock 466c 3 |
373 | /// 1 BZ2_hbMakeCodeLengths 29c 1 |
374 | /// |
375 | std::error_code parseInNoLBRMode(); |
376 | |
377 | /// Return branch data matching one of the names in \p FuncNames. |
378 | FuncBranchData * |
379 | getBranchDataForNames(const std::vector<StringRef> &FuncNames); |
380 | |
381 | /// Return branch data matching one of the \p Symbols. |
382 | FuncBranchData * |
383 | getBranchDataForSymbols(const std::vector<MCSymbol *> &Symbols); |
384 | |
385 | /// Return mem data matching one of the names in \p FuncNames. |
386 | FuncMemData *getMemDataForNames(const std::vector<StringRef> &FuncNames); |
387 | |
388 | FuncSampleData *getFuncSampleData(const std::vector<StringRef> &FuncNames); |
389 | |
390 | /// Return a vector of all FuncBranchData matching the list of names. |
391 | /// Internally use fuzzy matching to match special names like LTO-generated |
392 | /// function names. |
393 | std::vector<FuncBranchData *> |
394 | getBranchDataForNamesRegex(const std::vector<StringRef> &FuncNames); |
395 | |
396 | /// Return a vector of all FuncMemData matching the list of names. |
397 | /// Internally use fuzzy matching to match special names like LTO-generated |
398 | /// function names. |
399 | std::vector<FuncMemData *> |
400 | getMemDataForNamesRegex(const std::vector<StringRef> &FuncNames); |
401 | |
402 | /// Return branch data profile associated with function \p BF or nullptr |
403 | /// if the function has no associated profile. |
404 | FuncBranchData *getBranchData(const BinaryFunction &BF) const { |
405 | auto FBDI = FuncsToBranches.find(x: &BF); |
406 | if (FBDI == FuncsToBranches.end()) |
407 | return nullptr; |
408 | return FBDI->second; |
409 | } |
410 | |
411 | /// Updates branch profile data associated with function \p BF. |
412 | void setBranchData(const BinaryFunction &BF, FuncBranchData *FBD) { |
413 | FuncsToBranches[&BF] = FBD; |
414 | } |
415 | |
416 | /// Return memory profile data associated with function \p BF, or nullptr |
417 | /// if the function has no associated profile. |
418 | FuncMemData *getMemData(const BinaryFunction &BF) const { |
419 | auto FMDI = FuncsToMemData.find(x: &BF); |
420 | if (FMDI == FuncsToMemData.end()) |
421 | return nullptr; |
422 | return FMDI->second; |
423 | } |
424 | |
425 | /// Updates the memory profile data associated with function \p BF. |
426 | void setMemData(const BinaryFunction &BF, FuncMemData *FMD) { |
427 | FuncsToMemData[&BF] = FMD; |
428 | } |
429 | |
430 | using NamesToBranchesMapTy = std::map<StringRef, FuncBranchData>; |
431 | using NamesToSamplesMapTy = std::map<StringRef, FuncSampleData>; |
432 | using NamesToMemEventsMapTy = std::map<StringRef, FuncMemData>; |
433 | using FuncsToBranchesMapTy = |
434 | std::unordered_map<const BinaryFunction *, FuncBranchData *>; |
435 | using FuncsToMemDataMapTy = |
436 | std::unordered_map<const BinaryFunction *, FuncMemData *>; |
437 | |
438 | /// Dumps the entire data structures parsed. Used for debugging. |
439 | void dump() const; |
440 | |
441 | /// Return false only if we are running with profiling data that lacks LBR. |
442 | bool hasLBR() const { return !NoLBRMode; } |
443 | |
444 | /// Return true if the profiling data was collected in a bolted binary. This |
445 | /// means we lose the ability to identify stale data at some branch locations, |
446 | /// since we have to be more permissive in some cases. |
447 | bool collectedInBoltedBinary() const { return BATMode; } |
448 | |
449 | /// Return true if event named \p Name was used to collect this profile data. |
450 | bool usesEvent(StringRef Name) const { |
451 | for (auto I = EventNames.begin(), E = EventNames.end(); I != E; ++I) { |
452 | StringRef Event = I->getKey(); |
453 | if (Event.contains(Other: Name)) |
454 | return true; |
455 | } |
456 | return false; |
457 | } |
458 | |
459 | /// Open the file and parse the contents. |
460 | std::error_code parseInput(); |
461 | |
462 | /// Build suffix map once the profile data is parsed. |
463 | void buildLTONameMaps(); |
464 | |
465 | void reportError(StringRef ErrorMsg); |
466 | bool expectAndConsumeFS(); |
467 | void consumeAllRemainingFS(); |
468 | bool checkAndConsumeNewLine(); |
469 | ErrorOr<StringRef> parseString(char EndChar, bool EndNl = false); |
470 | ErrorOr<int64_t> parseNumberField(char EndChar, bool EndNl = false); |
471 | ErrorOr<uint64_t> parseHexField(char EndChar, bool EndNl = false); |
472 | ErrorOr<Location> parseLocation(char EndChar, bool EndNl, bool ExpectMemLoc); |
473 | ErrorOr<Location> parseLocation(char EndChar, bool EndNl = false) { |
474 | return parseLocation(EndChar, EndNl, ExpectMemLoc: false); |
475 | } |
476 | ErrorOr<Location> parseMemLocation(char EndChar, bool EndNl = false) { |
477 | return parseLocation(EndChar, EndNl, ExpectMemLoc: true); |
478 | } |
479 | ErrorOr<BranchInfo> parseBranchInfo(); |
480 | ErrorOr<SampleInfo> parseSampleInfo(); |
481 | ErrorOr<MemInfo> parseMemInfo(); |
482 | ErrorOr<bool> maybeParseNoLBRFlag(); |
483 | ErrorOr<bool> maybeParseBATFlag(); |
484 | bool hasBranchData(); |
485 | bool hasMemData(); |
486 | |
487 | /// An in-memory copy of the input data file - owns strings used in reader. |
488 | std::unique_ptr<MemoryBuffer> FileBuf; |
489 | raw_ostream &Diag; |
490 | StringRef ParsingBuf; |
491 | unsigned Line{0}; |
492 | unsigned Col{0}; |
493 | NamesToBranchesMapTy NamesToBranches; |
494 | NamesToSamplesMapTy NamesToSamples; |
495 | NamesToMemEventsMapTy NamesToMemEvents; |
496 | FuncsToBranchesMapTy FuncsToBranches; |
497 | FuncsToMemDataMapTy FuncsToMemData; |
498 | bool NoLBRMode{false}; |
499 | bool BATMode{false}; |
500 | StringSet<> EventNames; |
501 | static const char FieldSeparator = ' '; |
502 | |
503 | /// Maps of common LTO names to possible matching profiles. |
504 | StringMap<std::vector<FuncBranchData *>> LTOCommonNameMap; |
505 | StringMap<std::vector<FuncMemData *>> LTOCommonNameMemMap; |
506 | |
507 | public: |
508 | void setParsingBuffer(StringRef Buffer) { ParsingBuf = Buffer; } |
509 | }; |
510 | |
511 | } // namespace bolt |
512 | |
513 | /// DenseMapInfo allows us to use the DenseMap LLVM data structure to store |
514 | /// Locations |
515 | template <> struct DenseMapInfo<bolt::Location> { |
516 | static inline bolt::Location getEmptyKey() { |
517 | return bolt::Location(true, StringRef(), static_cast<uint64_t>(-1LL)); |
518 | } |
519 | static inline bolt::Location getTombstoneKey() { |
520 | return bolt::Location(true, StringRef(), static_cast<uint64_t>(-2LL)); |
521 | ; |
522 | } |
523 | static unsigned getHashValue(const bolt::Location &L) { |
524 | return (unsigned(DenseMapInfo<StringRef>::getHashValue(Val: L.Name)) >> 4) ^ |
525 | (unsigned(L.Offset)); |
526 | } |
527 | static bool isEqual(const bolt::Location &LHS, const bolt::Location &RHS) { |
528 | return LHS.IsSymbol == RHS.IsSymbol && LHS.Name == RHS.Name && |
529 | LHS.Offset == RHS.Offset; |
530 | } |
531 | }; |
532 | |
533 | } // namespace llvm |
534 | |
535 | #endif |
536 | |