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
28namespace llvm {
29class MCSymbol;
30
31namespace bolt {
32
33class BinaryFunction;
34
35struct LBREntry {
36 uint64_t From;
37 uint64_t To;
38 bool Mispred;
39};
40
41inline 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
47struct 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
76typedef std::vector<std::pair<Location, Location>> BranchContext;
77
78struct 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
108struct 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.
161struct 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.
197struct 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.
221struct 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.
243struct 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///
263class DataReader : public ProfileReaderBase {
264public:
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
285protected:
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
507public:
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
515template <> 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

source code of bolt/include/bolt/Profile/DataReader.h