1 //===- SampleProfReader.cpp - Read LLVM sample profile data ---------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the class that reads LLVM sample profiles. It
11 // supports two file formats: text and binary. The textual representation
12 // is useful for debugging and testing purposes. The binary representation
13 // is more compact, resulting in smaller file sizes. However, they can
14 // both be used interchangeably.
16 // NOTE: If you are making changes to the file format, please remember
17 // to document them in the Clang documentation at
18 // tools/clang/docs/UsersManual.rst.
23 // Sample profiles are written as ASCII text. The file is divided into
24 // sections, which correspond to each of the functions executed at runtime.
25 // Each section has the following format
27 // function1:total_samples:total_head_samples
28 // offset1[.discriminator]: number_of_samples [fn1:num fn2:num ... ]
29 // offset2[.discriminator]: number_of_samples [fn3:num fn4:num ... ]
31 // offsetN[.discriminator]: number_of_samples [fn5:num fn6:num ... ]
32 // offsetA[.discriminator]: fnA:num_of_total_samples
33 // offsetA1[.discriminator]: number_of_samples [fn7:num fn8:num ... ]
36 // This is a nested tree in which the identation represent the nest level
37 // of the inline stack. There is no blank line in the file. And the spacing
38 // within a single line is fixed. Additional spaces will result in an error
39 // while reading the file.
41 // Inline stack is a stack of source locations in which the top of the stack
42 // represents the leaf function, and the bottom of the stack represents the
43 // actual symbol in which the instruction belongs.
45 // Function names must be mangled in order for the profile loader to
46 // match them in the current translation unit. The two numbers in the
47 // function header specify how many total samples were accumulated in the
48 // function (first number), and the total number of samples accumulated
49 // in the prologue of the function (second number). This head sample
50 // count provides an indicator of how frequently the function is invoked.
52 // There are two types of lines in the function body.
54 // * Sampled line represents the profile information of a source location.
55 // * Callsite line represents the profile inofrmation of a callsite.
57 // Each sampled line may contain several items. Some are optional (marked
60 // a. Source line offset. This number represents the line number
61 // in the function where the sample was collected. The line number is
62 // always relative to the line where symbol of the function is
63 // defined. So, if the function has its header at line 280, the offset
64 // 13 is at line 293 in the file.
66 // Note that this offset should never be a negative number. This could
67 // happen in cases like macros. The debug machinery will register the
68 // line number at the point of macro expansion. So, if the macro was
69 // expanded in a line before the start of the function, the profile
70 // converter should emit a 0 as the offset (this means that the optimizers
71 // will not be able to associate a meaningful weight to the instructions
74 // b. [OPTIONAL] Discriminator. This is used if the sampled program
75 // was compiled with DWARF discriminator support
76 // (http://wiki.dwarfstd.org/index.php?title=Path_Discriminators).
77 // DWARF discriminators are unsigned integer values that allow the
78 // compiler to distinguish between multiple execution paths on the
79 // same source line location.
81 // For example, consider the line of code ``if (cond) foo(); else bar();``.
82 // If the predicate ``cond`` is true 80% of the time, then the edge
83 // into function ``foo`` should be considered to be taken most of the
84 // time. But both calls to ``foo`` and ``bar`` are at the same source
85 // line, so a sample count at that line is not sufficient. The
86 // compiler needs to know which part of that line is taken more
89 // This is what discriminators provide. In this case, the calls to
90 // ``foo`` and ``bar`` will be at the same line, but will have
91 // different discriminator values. This allows the compiler to correctly
92 // set edge weights into ``foo`` and ``bar``.
94 // c. Number of samples. This is an integer quantity representing the
95 // number of samples collected by the profiler at this source
98 // d. [OPTIONAL] Potential call targets and samples. If present, this
99 // line contains a call instruction. This models both direct and
100 // number of samples. For example,
102 // 130: 7 foo:3 bar:2 baz:7
104 // The above means that at relative line offset 130 there is a call
105 // instruction that calls one of ``foo()``, ``bar()`` and ``baz()``,
106 // with ``baz()`` being the relatively more frequently called target.
108 // Each callsite line may contain several items. Some are optional.
110 // a. Source line offset. This number represents the line number of the
111 // callsite that is inlined in the profiled binary.
113 // b. [OPTIONAL] Discriminator. Same as the discriminator for sampled line.
115 // c. Number of samples. This is an integer quantity representing the
116 // total number of samples collected for the inlined instance at this
118 //===----------------------------------------------------------------------===//
120 #include "llvm/ProfileData/SampleProfReader.h"
121 #include "llvm/Support/Debug.h"
122 #include "llvm/Support/ErrorOr.h"
123 #include "llvm/Support/LEB128.h"
124 #include "llvm/Support/LineIterator.h"
125 #include "llvm/Support/MemoryBuffer.h"
126 #include "llvm/ADT/DenseMap.h"
127 #include "llvm/ADT/SmallVector.h"
129 using namespace llvm::sampleprof;
130 using namespace llvm;
132 /// \brief Print the samples collected for a function on stream \p OS.
134 /// \param OS Stream to emit the output to.
135 void FunctionSamples::print(raw_ostream &OS) {
136 OS << TotalSamples << ", " << TotalHeadSamples << ", " << BodySamples.size()
137 << " sampled lines\n";
138 for (const auto &SI : BodySamples) {
139 LineLocation Loc = SI.first;
140 const SampleRecord &Sample = SI.second;
141 OS << "\tline offset: " << Loc.LineOffset
142 << ", discriminator: " << Loc.Discriminator
143 << ", number of samples: " << Sample.getSamples();
144 if (Sample.hasCalls()) {
146 for (const auto &I : Sample.getCallTargets())
147 OS << " " << I.first() << ":" << I.second;
154 /// \brief Dump the function profile for \p FName.
156 /// \param FName Name of the function to print.
157 /// \param OS Stream to emit the output to.
158 void SampleProfileReader::dumpFunctionProfile(StringRef FName,
160 OS << "Function: " << FName << ": ";
161 Profiles[FName].print(OS);
164 /// \brief Dump all the function profiles found on stream \p OS.
165 void SampleProfileReader::dump(raw_ostream &OS) {
166 for (const auto &I : Profiles)
167 dumpFunctionProfile(I.getKey(), OS);
170 /// \brief Parse \p Input as function head.
172 /// Parse one line of \p Input, and update function name in \p FName,
173 /// function's total sample count in \p NumSamples, function's entry
174 /// count in \p NumHeadSamples.
176 /// \returns true if parsing is successful.
177 static bool ParseHead(const StringRef &Input, StringRef &FName,
178 unsigned &NumSamples, unsigned &NumHeadSamples) {
181 size_t n2 = Input.rfind(':');
182 size_t n1 = Input.rfind(':', n2 - 1);
183 FName = Input.substr(0, n1);
184 if (Input.substr(n1 + 1, n2 - n1 - 1).getAsInteger(10, NumSamples))
186 if (Input.substr(n2 + 1).getAsInteger(10, NumHeadSamples))
191 /// \brief Parse \p Input as line sample.
193 /// \param Input input line.
194 /// \param IsCallsite true if the line represents an inlined callsite.
195 /// \param Depth the depth of the inline stack.
196 /// \param NumSamples total samples of the line/inlined callsite.
197 /// \param LineOffset line offset to the start of the function.
198 /// \param Discriminator discriminator of the line.
199 /// \param TargetCountMap map from indirect call target to count.
201 /// returns true if parsing is successful.
202 static bool ParseLine(const StringRef &Input, bool &IsCallsite, unsigned &Depth,
203 unsigned &NumSamples, unsigned &LineOffset,
204 unsigned &Discriminator, StringRef &CalleeName,
205 DenseMap<StringRef, unsigned> &TargetCountMap) {
206 for (Depth = 0; Input[Depth] == ' '; Depth++)
211 size_t n1 = Input.find(':');
212 StringRef Loc = Input.substr(Depth, n1 - Depth);
213 size_t n2 = Loc.find('.');
214 if (n2 == StringRef::npos) {
215 if (Loc.getAsInteger(10, LineOffset))
219 if (Loc.substr(0, n2).getAsInteger(10, LineOffset))
221 if (Loc.substr(n2 + 1).getAsInteger(10, Discriminator))
225 StringRef Rest = Input.substr(n1 + 2);
226 if (Rest[0] >= '0' && Rest[0] <= '9') {
228 size_t n3 = Rest.find(' ');
229 if (n3 == StringRef::npos) {
230 if (Rest.getAsInteger(10, NumSamples))
233 if (Rest.substr(0, n3).getAsInteger(10, NumSamples))
236 while (n3 != StringRef::npos) {
237 n3 += Rest.substr(n3).find_first_not_of(' ');
238 Rest = Rest.substr(n3);
240 StringRef pair = Rest;
241 if (n3 != StringRef::npos) {
242 pair = Rest.substr(0, n3);
244 int n4 = pair.find(':');
246 if (pair.substr(n4 + 1).getAsInteger(10, count))
248 TargetCountMap[pair.substr(0, n4)] = count;
252 int n3 = Rest.find_last_of(':');
253 CalleeName = Rest.substr(0, n3);
254 if (Rest.substr(n3 + 1).getAsInteger(10, NumSamples))
260 /// \brief Load samples from a text file.
262 /// See the documentation at the top of the file for an explanation of
263 /// the expected format.
265 /// \returns true if the file was loaded successfully, false otherwise.
266 std::error_code SampleProfileReaderText::read() {
267 line_iterator LineIt(*Buffer, /*SkipBlanks=*/true, '#');
269 SmallVector<FunctionSamples *, 10> InlineStack;
271 for (; !LineIt.is_at_eof(); ++LineIt) {
272 if ((*LineIt)[(*LineIt).find_first_not_of(' ')] == '#')
274 // Read the header of each function.
276 // Note that for function identifiers we are actually expecting
277 // mangled names, but we may not always get them. This happens when
278 // the compiler decides not to emit the function (e.g., it was inlined
279 // and removed). In this case, the binary will not have the linkage
280 // name for the function, so the profiler will emit the function's
281 // unmangled name, which may contain characters like ':' and '>' in its
282 // name (member functions, templates, etc).
284 // The only requirement we place on the identifier, then, is that it
285 // should not begin with a number.
286 if ((*LineIt)[0] != ' ') {
287 unsigned NumSamples, NumHeadSamples;
289 if (!ParseHead(*LineIt, FName, NumSamples, NumHeadSamples)) {
290 reportError(LineIt.line_number(),
291 "Expected 'mangled_name:NUM:NUM', found " + *LineIt);
292 return sampleprof_error::malformed;
294 Profiles[FName] = FunctionSamples();
295 FunctionSamples &FProfile = Profiles[FName];
296 FProfile.addTotalSamples(NumSamples);
297 FProfile.addHeadSamples(NumHeadSamples);
299 InlineStack.push_back(&FProfile);
303 DenseMap<StringRef, unsigned> TargetCountMap;
305 unsigned Depth, LineOffset, Discriminator;
306 if (!ParseLine(*LineIt, IsCallsite, Depth, NumSamples, LineOffset,
307 Discriminator, FName, TargetCountMap)) {
308 reportError(LineIt.line_number(),
309 "Expected 'NUM[.NUM]: NUM[ mangled_name:NUM]*', found " +
311 return sampleprof_error::malformed;
314 while (InlineStack.size() > Depth) {
315 InlineStack.pop_back();
317 FunctionSamples &FSamples = InlineStack.back()->functionSamplesAt(
318 CallsiteLocation(LineOffset, Discriminator, FName));
319 FSamples.addTotalSamples(NumSamples);
320 InlineStack.push_back(&FSamples);
322 while (InlineStack.size() > Depth) {
323 InlineStack.pop_back();
325 FunctionSamples &FProfile = *InlineStack.back();
326 for (const auto &name_count : TargetCountMap) {
327 FProfile.addCalledTargetSamples(LineOffset, Discriminator,
328 name_count.first, name_count.second);
330 FProfile.addBodySamples(LineOffset, Discriminator, NumSamples);
335 return sampleprof_error::success;
338 template <typename T> ErrorOr<T> SampleProfileReaderBinary::readNumber() {
339 unsigned NumBytesRead = 0;
341 uint64_t Val = decodeULEB128(Data, &NumBytesRead);
343 if (Val > std::numeric_limits<T>::max())
344 EC = sampleprof_error::malformed;
345 else if (Data + NumBytesRead > End)
346 EC = sampleprof_error::truncated;
348 EC = sampleprof_error::success;
351 reportError(0, EC.message());
355 Data += NumBytesRead;
356 return static_cast<T>(Val);
359 ErrorOr<StringRef> SampleProfileReaderBinary::readString() {
361 StringRef Str(reinterpret_cast<const char *>(Data));
362 if (Data + Str.size() + 1 > End) {
363 EC = sampleprof_error::truncated;
364 reportError(0, EC.message());
368 Data += Str.size() + 1;
372 std::error_code SampleProfileReaderBinary::read() {
374 auto FName(readString());
375 if (std::error_code EC = FName.getError())
378 Profiles[*FName] = FunctionSamples();
379 FunctionSamples &FProfile = Profiles[*FName];
381 auto Val = readNumber<unsigned>();
382 if (std::error_code EC = Val.getError())
384 FProfile.addTotalSamples(*Val);
386 Val = readNumber<unsigned>();
387 if (std::error_code EC = Val.getError())
389 FProfile.addHeadSamples(*Val);
391 // Read the samples in the body.
392 auto NumRecords = readNumber<unsigned>();
393 if (std::error_code EC = NumRecords.getError())
395 for (unsigned I = 0; I < *NumRecords; ++I) {
396 auto LineOffset = readNumber<uint64_t>();
397 if (std::error_code EC = LineOffset.getError())
400 auto Discriminator = readNumber<uint64_t>();
401 if (std::error_code EC = Discriminator.getError())
404 auto NumSamples = readNumber<uint64_t>();
405 if (std::error_code EC = NumSamples.getError())
408 auto NumCalls = readNumber<unsigned>();
409 if (std::error_code EC = NumCalls.getError())
412 for (unsigned J = 0; J < *NumCalls; ++J) {
413 auto CalledFunction(readString());
414 if (std::error_code EC = CalledFunction.getError())
417 auto CalledFunctionSamples = readNumber<uint64_t>();
418 if (std::error_code EC = CalledFunctionSamples.getError())
421 FProfile.addCalledTargetSamples(*LineOffset, *Discriminator,
423 *CalledFunctionSamples);
426 FProfile.addBodySamples(*LineOffset, *Discriminator, *NumSamples);
430 return sampleprof_error::success;
433 std::error_code SampleProfileReaderBinary::readHeader() {
434 Data = reinterpret_cast<const uint8_t *>(Buffer->getBufferStart());
435 End = Data + Buffer->getBufferSize();
437 // Read and check the magic identifier.
438 auto Magic = readNumber<uint64_t>();
439 if (std::error_code EC = Magic.getError())
441 else if (*Magic != SPMagic())
442 return sampleprof_error::bad_magic;
444 // Read the version number.
445 auto Version = readNumber<uint64_t>();
446 if (std::error_code EC = Version.getError())
448 else if (*Version != SPVersion())
449 return sampleprof_error::unsupported_version;
451 return sampleprof_error::success;
454 bool SampleProfileReaderBinary::hasFormat(const MemoryBuffer &Buffer) {
455 const uint8_t *Data =
456 reinterpret_cast<const uint8_t *>(Buffer.getBufferStart());
457 uint64_t Magic = decodeULEB128(Data);
458 return Magic == SPMagic();
461 bool SourceInfo::operator<(const SourceInfo &P) const {
463 return Line < P.Line;
464 if (StartLine != P.StartLine)
465 return StartLine < P.StartLine;
466 if (Discriminator != P.Discriminator)
467 return Discriminator < P.Discriminator;
468 return FuncName < P.FuncName;
471 std::error_code SampleProfileReaderGCC::skipNextWord() {
473 if (!GcovBuffer.readInt(dummy))
474 return sampleprof_error::truncated;
475 return sampleprof_error::success;
478 template <typename T> ErrorOr<T> SampleProfileReaderGCC::readNumber() {
479 if (sizeof(T) <= sizeof(uint32_t)) {
481 if (GcovBuffer.readInt(Val) && Val <= std::numeric_limits<T>::max())
482 return static_cast<T>(Val);
483 } else if (sizeof(T) <= sizeof(uint64_t)) {
485 if (GcovBuffer.readInt64(Val) && Val <= std::numeric_limits<T>::max())
486 return static_cast<T>(Val);
489 std::error_code EC = sampleprof_error::malformed;
490 reportError(0, EC.message());
494 ErrorOr<StringRef> SampleProfileReaderGCC::readString() {
496 if (!GcovBuffer.readString(Str))
497 return sampleprof_error::truncated;
501 std::error_code SampleProfileReaderGCC::readHeader() {
502 // Read the magic identifier.
503 if (!GcovBuffer.readGCDAFormat())
504 return sampleprof_error::unrecognized_format;
506 // Read the version number. Note - the GCC reader does not validate this
507 // version, but the profile creator generates v704.
508 GCOV::GCOVVersion version;
509 if (!GcovBuffer.readGCOVVersion(version))
510 return sampleprof_error::unrecognized_format;
512 if (version != GCOV::V704)
513 return sampleprof_error::unsupported_version;
515 // Skip the empty integer.
516 if (std::error_code EC = skipNextWord())
519 return sampleprof_error::success;
522 std::error_code SampleProfileReaderGCC::readSectionTag(uint32_t Expected) {
524 if (!GcovBuffer.readInt(Tag))
525 return sampleprof_error::truncated;
528 return sampleprof_error::malformed;
530 if (std::error_code EC = skipNextWord())
533 return sampleprof_error::success;
536 std::error_code SampleProfileReaderGCC::readNameTable() {
537 if (std::error_code EC = readSectionTag(GCOVTagAFDOFileNames))
541 if (!GcovBuffer.readInt(Size))
542 return sampleprof_error::truncated;
544 for (uint32_t I = 0; I < Size; ++I) {
546 if (!GcovBuffer.readString(Str))
547 return sampleprof_error::truncated;
548 Names.push_back(Str);
551 return sampleprof_error::success;
554 std::error_code SampleProfileReaderGCC::readFunctionProfiles() {
555 if (std::error_code EC = readSectionTag(GCOVTagAFDOFunction))
558 uint32_t NumFunctions;
559 if (!GcovBuffer.readInt(NumFunctions))
560 return sampleprof_error::truncated;
563 for (uint32_t I = 0; I < NumFunctions; ++I)
564 if (std::error_code EC = readOneFunctionProfile(Stack, true))
567 return sampleprof_error::success;
570 std::error_code SampleProfileReaderGCC::addSourceCount(StringRef Name,
571 const SourceStack &Src,
573 if (Src.size() == 0 || Src[0].Malformed())
574 return sampleprof_error::malformed;
575 FunctionSamples &FProfile = Profiles[Name];
576 FProfile.addTotalSamples(Count);
577 // FIXME(dnovillo) - Properly update inline stack for FnName.
578 FProfile.addBodySamples(Src[0].Line, Src[0].Discriminator, Count);
579 return sampleprof_error::success;
583 SampleProfileReaderGCC::readOneFunctionProfile(const SourceStack &Stack,
585 uint64_t HeadCount = 0;
586 if (Stack.size() == 0)
587 if (!GcovBuffer.readInt64(HeadCount))
588 return sampleprof_error::truncated;
591 if (!GcovBuffer.readInt(NameIdx))
592 return sampleprof_error::truncated;
594 StringRef Name(Names[NameIdx]);
596 uint32_t NumPosCounts;
597 if (!GcovBuffer.readInt(NumPosCounts))
598 return sampleprof_error::truncated;
600 uint32_t NumCallSites;
601 if (!GcovBuffer.readInt(NumCallSites))
602 return sampleprof_error::truncated;
604 if (Stack.size() == 0) {
605 FunctionSamples &FProfile = Profiles[Name];
606 FProfile.addHeadSamples(HeadCount);
607 if (FProfile.getTotalSamples() > 0)
611 for (uint32_t I = 0; I < NumPosCounts; ++I) {
613 if (!GcovBuffer.readInt(Offset))
614 return sampleprof_error::truncated;
617 if (!GcovBuffer.readInt(NumTargets))
618 return sampleprof_error::truncated;
621 if (!GcovBuffer.readInt64(Count))
622 return sampleprof_error::truncated;
624 SourceInfo Info(Name, "", "", 0, Offset >> 16, Offset & 0xffff);
625 SourceStack NewStack;
626 NewStack.push_back(Info);
627 NewStack.insert(NewStack.end(), Stack.begin(), Stack.end());
629 addSourceCount(NewStack[NewStack.size() - 1].FuncName, NewStack, Count);
631 for (uint32_t J = 0; J < NumTargets; J++) {
633 if (!GcovBuffer.readInt(HistVal))
634 return sampleprof_error::truncated;
636 if (HistVal != HIST_TYPE_INDIR_CALL_TOPN)
637 return sampleprof_error::malformed;
640 if (!GcovBuffer.readInt64(TargetIdx))
641 return sampleprof_error::truncated;
642 StringRef TargetName(Names[TargetIdx]);
644 uint64_t TargetCount;
645 if (!GcovBuffer.readInt64(TargetCount))
646 return sampleprof_error::truncated;
649 FunctionSamples &TargetProfile = Profiles[TargetName];
650 TargetProfile.addBodySamples(NewStack[0].Line,
651 NewStack[0].Discriminator, TargetCount);
656 for (uint32_t I = 0; I < NumCallSites; I++) {
657 // The offset is encoded as:
658 // high 16 bits: line offset to the start of the function.
659 // low 16 bits: discriminator.
661 if (!GcovBuffer.readInt(Offset))
662 return sampleprof_error::truncated;
663 SourceInfo Info(Name, "", "", 0, Offset >> 16, Offset & 0xffff);
664 SourceStack NewStack;
665 NewStack.push_back(Info);
666 NewStack.insert(NewStack.end(), Stack.begin(), Stack.end());
667 if (std::error_code EC = readOneFunctionProfile(NewStack, Update))
671 return sampleprof_error::success;
674 /// \brief Read a GCC AutoFDO profile.
676 /// This format is generated by the Linux Perf conversion tool at
677 /// https://github.com/google/autofdo.
678 std::error_code SampleProfileReaderGCC::read() {
679 // Read the string table.
680 if (std::error_code EC = readNameTable())
683 // Read the source profile.
684 if (std::error_code EC = readFunctionProfiles())
687 return sampleprof_error::success;
690 bool SampleProfileReaderGCC::hasFormat(const MemoryBuffer &Buffer) {
691 StringRef Magic(reinterpret_cast<const char *>(Buffer.getBufferStart()));
692 return Magic == "adcg*704";
695 /// \brief Prepare a memory buffer for the contents of \p Filename.
697 /// \returns an error code indicating the status of the buffer.
698 static ErrorOr<std::unique_ptr<MemoryBuffer>>
699 setupMemoryBuffer(std::string Filename) {
700 auto BufferOrErr = MemoryBuffer::getFileOrSTDIN(Filename);
701 if (std::error_code EC = BufferOrErr.getError())
703 auto Buffer = std::move(BufferOrErr.get());
705 // Sanity check the file.
706 if (Buffer->getBufferSize() > std::numeric_limits<unsigned>::max())
707 return sampleprof_error::too_large;
709 return std::move(Buffer);
712 /// \brief Create a sample profile reader based on the format of the input file.
714 /// \param Filename The file to open.
716 /// \param Reader The reader to instantiate according to \p Filename's format.
718 /// \param C The LLVM context to use to emit diagnostics.
720 /// \returns an error code indicating the status of the created reader.
721 ErrorOr<std::unique_ptr<SampleProfileReader>>
722 SampleProfileReader::create(StringRef Filename, LLVMContext &C) {
723 auto BufferOrError = setupMemoryBuffer(Filename);
724 if (std::error_code EC = BufferOrError.getError())
727 auto Buffer = std::move(BufferOrError.get());
728 std::unique_ptr<SampleProfileReader> Reader;
729 if (SampleProfileReaderBinary::hasFormat(*Buffer))
730 Reader.reset(new SampleProfileReaderBinary(std::move(Buffer), C));
731 else if (SampleProfileReaderGCC::hasFormat(*Buffer))
732 Reader.reset(new SampleProfileReaderGCC(std::move(Buffer), C));
734 Reader.reset(new SampleProfileReaderText(std::move(Buffer), C));
736 if (std::error_code EC = Reader->readHeader())
739 return std::move(Reader);