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 ... ]
33 // The file may contain blank lines between sections and within a
34 // section. However, the spacing within a single line is fixed. Additional
35 // spaces will result in an error while reading the file.
37 // Function names must be mangled in order for the profile loader to
38 // match them in the current translation unit. The two numbers in the
39 // function header specify how many total samples were accumulated in the
40 // function (first number), and the total number of samples accumulated
41 // in the prologue of the function (second number). This head sample
42 // count provides an indicator of how frequently the function is invoked.
44 // Each sampled line may contain several items. Some are optional (marked
47 // a. Source line offset. This number represents the line number
48 // in the function where the sample was collected. The line number is
49 // always relative to the line where symbol of the function is
50 // defined. So, if the function has its header at line 280, the offset
51 // 13 is at line 293 in the file.
53 // Note that this offset should never be a negative number. This could
54 // happen in cases like macros. The debug machinery will register the
55 // line number at the point of macro expansion. So, if the macro was
56 // expanded in a line before the start of the function, the profile
57 // converter should emit a 0 as the offset (this means that the optimizers
58 // will not be able to associate a meaningful weight to the instructions
61 // b. [OPTIONAL] Discriminator. This is used if the sampled program
62 // was compiled with DWARF discriminator support
63 // (http://wiki.dwarfstd.org/index.php?title=Path_Discriminators).
64 // DWARF discriminators are unsigned integer values that allow the
65 // compiler to distinguish between multiple execution paths on the
66 // same source line location.
68 // For example, consider the line of code ``if (cond) foo(); else bar();``.
69 // If the predicate ``cond`` is true 80% of the time, then the edge
70 // into function ``foo`` should be considered to be taken most of the
71 // time. But both calls to ``foo`` and ``bar`` are at the same source
72 // line, so a sample count at that line is not sufficient. The
73 // compiler needs to know which part of that line is taken more
76 // This is what discriminators provide. In this case, the calls to
77 // ``foo`` and ``bar`` will be at the same line, but will have
78 // different discriminator values. This allows the compiler to correctly
79 // set edge weights into ``foo`` and ``bar``.
81 // c. Number of samples. This is an integer quantity representing the
82 // number of samples collected by the profiler at this source
85 // d. [OPTIONAL] Potential call targets and samples. If present, this
86 // line contains a call instruction. This models both direct and
87 // number of samples. For example,
89 // 130: 7 foo:3 bar:2 baz:7
91 // The above means that at relative line offset 130 there is a call
92 // instruction that calls one of ``foo()``, ``bar()`` and ``baz()``,
93 // with ``baz()`` being the relatively more frequently called target.
95 //===----------------------------------------------------------------------===//
97 #include "llvm/ProfileData/SampleProfReader.h"
98 #include "llvm/Support/Debug.h"
99 #include "llvm/Support/ErrorOr.h"
100 #include "llvm/Support/LEB128.h"
101 #include "llvm/Support/LineIterator.h"
102 #include "llvm/Support/MemoryBuffer.h"
103 #include "llvm/Support/Regex.h"
105 using namespace llvm::sampleprof;
106 using namespace llvm;
108 /// \brief Print the samples collected for a function on stream \p OS.
110 /// \param OS Stream to emit the output to.
111 void FunctionSamples::print(raw_ostream &OS) {
112 OS << TotalSamples << ", " << TotalHeadSamples << ", " << BodySamples.size()
113 << " sampled lines\n";
114 for (const auto &SI : BodySamples) {
115 LineLocation Loc = SI.first;
116 const SampleRecord &Sample = SI.second;
117 OS << "\tline offset: " << Loc.LineOffset
118 << ", discriminator: " << Loc.Discriminator
119 << ", number of samples: " << Sample.getSamples();
120 if (Sample.hasCalls()) {
122 for (const auto &I : Sample.getCallTargets())
123 OS << " " << I.first() << ":" << I.second;
130 /// \brief Dump the function profile for \p FName.
132 /// \param FName Name of the function to print.
133 /// \param OS Stream to emit the output to.
134 void SampleProfileReader::dumpFunctionProfile(StringRef FName,
136 OS << "Function: " << FName << ": ";
137 Profiles[FName].print(OS);
140 /// \brief Dump all the function profiles found on stream \p OS.
141 void SampleProfileReader::dump(raw_ostream &OS) {
142 for (const auto &I : Profiles)
143 dumpFunctionProfile(I.getKey(), OS);
146 /// \brief Load samples from a text file.
148 /// See the documentation at the top of the file for an explanation of
149 /// the expected format.
151 /// \returns true if the file was loaded successfully, false otherwise.
152 std::error_code SampleProfileReaderText::read() {
153 line_iterator LineIt(*Buffer, /*SkipBlanks=*/true, '#');
155 // Read the profile of each function. Since each function may be
156 // mentioned more than once, and we are collecting flat profiles,
157 // accumulate samples as we parse them.
158 Regex HeadRE("^([^0-9].*):([0-9]+):([0-9]+)$");
159 Regex LineSampleRE("^([0-9]+)\\.?([0-9]+)?: ([0-9]+)(.*)$");
160 Regex CallSampleRE(" +([^0-9 ][^ ]*):([0-9]+)");
161 while (!LineIt.is_at_eof()) {
162 // Read the header of each function.
164 // Note that for function identifiers we are actually expecting
165 // mangled names, but we may not always get them. This happens when
166 // the compiler decides not to emit the function (e.g., it was inlined
167 // and removed). In this case, the binary will not have the linkage
168 // name for the function, so the profiler will emit the function's
169 // unmangled name, which may contain characters like ':' and '>' in its
170 // name (member functions, templates, etc).
172 // The only requirement we place on the identifier, then, is that it
173 // should not begin with a number.
174 SmallVector<StringRef, 4> Matches;
175 if (!HeadRE.match(*LineIt, &Matches)) {
176 reportError(LineIt.line_number(),
177 "Expected 'mangled_name:NUM:NUM', found " + *LineIt);
178 return sampleprof_error::malformed;
180 assert(Matches.size() == 4);
181 StringRef FName = Matches[1];
182 unsigned NumSamples, NumHeadSamples;
183 Matches[2].getAsInteger(10, NumSamples);
184 Matches[3].getAsInteger(10, NumHeadSamples);
185 Profiles[FName] = FunctionSamples();
186 FunctionSamples &FProfile = Profiles[FName];
187 FProfile.addTotalSamples(NumSamples);
188 FProfile.addHeadSamples(NumHeadSamples);
191 // Now read the body. The body of the function ends when we reach
192 // EOF or when we see the start of the next function.
193 while (!LineIt.is_at_eof() && isdigit((*LineIt)[0])) {
194 if (!LineSampleRE.match(*LineIt, &Matches)) {
195 reportError(LineIt.line_number(),
196 "Expected 'NUM[.NUM]: NUM[ mangled_name:NUM]*', found " +
198 return sampleprof_error::malformed;
200 assert(Matches.size() == 5);
201 unsigned LineOffset, NumSamples, Discriminator = 0;
202 Matches[1].getAsInteger(10, LineOffset);
203 if (Matches[2] != "")
204 Matches[2].getAsInteger(10, Discriminator);
205 Matches[3].getAsInteger(10, NumSamples);
207 // If there are function calls in this line, generate a call sample
208 // entry for each call.
209 std::string CallsLine(Matches[4]);
210 while (CallsLine != "") {
211 SmallVector<StringRef, 3> CallSample;
212 if (!CallSampleRE.match(CallsLine, &CallSample)) {
213 reportError(LineIt.line_number(),
214 "Expected 'mangled_name:NUM', found " + CallsLine);
215 return sampleprof_error::malformed;
217 StringRef CalledFunction = CallSample[1];
218 unsigned CalledFunctionSamples;
219 CallSample[2].getAsInteger(10, CalledFunctionSamples);
220 FProfile.addCalledTargetSamples(LineOffset, Discriminator,
221 CalledFunction, CalledFunctionSamples);
222 CallsLine = CallSampleRE.sub("", CallsLine);
225 FProfile.addBodySamples(LineOffset, Discriminator, NumSamples);
230 return sampleprof_error::success;
233 template <typename T> ErrorOr<T> SampleProfileReaderBinary::readNumber() {
234 unsigned NumBytesRead = 0;
236 uint64_t Val = decodeULEB128(Data, &NumBytesRead);
238 if (Val > std::numeric_limits<T>::max())
239 EC = sampleprof_error::malformed;
240 else if (Data + NumBytesRead > End)
241 EC = sampleprof_error::truncated;
243 EC = sampleprof_error::success;
246 reportError(0, EC.message());
250 Data += NumBytesRead;
251 return static_cast<T>(Val);
254 ErrorOr<StringRef> SampleProfileReaderBinary::readString() {
256 StringRef Str(reinterpret_cast<const char *>(Data));
257 if (Data + Str.size() + 1 > End) {
258 EC = sampleprof_error::truncated;
259 reportError(0, EC.message());
263 Data += Str.size() + 1;
267 std::error_code SampleProfileReaderBinary::read() {
269 auto FName(readString());
270 if (std::error_code EC = FName.getError())
273 Profiles[*FName] = FunctionSamples();
274 FunctionSamples &FProfile = Profiles[*FName];
276 auto Val = readNumber<unsigned>();
277 if (std::error_code EC = Val.getError())
279 FProfile.addTotalSamples(*Val);
281 Val = readNumber<unsigned>();
282 if (std::error_code EC = Val.getError())
284 FProfile.addHeadSamples(*Val);
286 // Read the samples in the body.
287 auto NumRecords = readNumber<unsigned>();
288 if (std::error_code EC = NumRecords.getError())
290 for (unsigned I = 0; I < *NumRecords; ++I) {
291 auto LineOffset = readNumber<uint64_t>();
292 if (std::error_code EC = LineOffset.getError())
295 auto Discriminator = readNumber<uint64_t>();
296 if (std::error_code EC = Discriminator.getError())
299 auto NumSamples = readNumber<uint64_t>();
300 if (std::error_code EC = NumSamples.getError())
303 auto NumCalls = readNumber<unsigned>();
304 if (std::error_code EC = NumCalls.getError())
307 for (unsigned J = 0; J < *NumCalls; ++J) {
308 auto CalledFunction(readString());
309 if (std::error_code EC = CalledFunction.getError())
312 auto CalledFunctionSamples = readNumber<uint64_t>();
313 if (std::error_code EC = CalledFunctionSamples.getError())
316 FProfile.addCalledTargetSamples(*LineOffset, *Discriminator,
318 *CalledFunctionSamples);
321 FProfile.addBodySamples(*LineOffset, *Discriminator, *NumSamples);
325 return sampleprof_error::success;
328 std::error_code SampleProfileReaderBinary::readHeader() {
329 Data = reinterpret_cast<const uint8_t *>(Buffer->getBufferStart());
330 End = Data + Buffer->getBufferSize();
332 // Read and check the magic identifier.
333 auto Magic = readNumber<uint64_t>();
334 if (std::error_code EC = Magic.getError())
336 else if (*Magic != SPMagic())
337 return sampleprof_error::bad_magic;
339 // Read the version number.
340 auto Version = readNumber<uint64_t>();
341 if (std::error_code EC = Version.getError())
343 else if (*Version != SPVersion())
344 return sampleprof_error::unsupported_version;
346 return sampleprof_error::success;
349 bool SampleProfileReaderBinary::hasFormat(const MemoryBuffer &Buffer) {
350 const uint8_t *Data =
351 reinterpret_cast<const uint8_t *>(Buffer.getBufferStart());
352 uint64_t Magic = decodeULEB128(Data);
353 return Magic == SPMagic();
356 bool SourceInfo::operator<(const SourceInfo &P) const {
358 return Line < P.Line;
359 if (StartLine != P.StartLine)
360 return StartLine < P.StartLine;
361 if (Discriminator != P.Discriminator)
362 return Discriminator < P.Discriminator;
363 return FuncName < P.FuncName;
366 std::error_code SampleProfileReaderGCC::skipNextWord() {
368 if (!GcovBuffer.readInt(dummy))
369 return sampleprof_error::truncated;
370 return sampleprof_error::success;
373 template <typename T> ErrorOr<T> SampleProfileReaderGCC::readNumber() {
374 if (sizeof(T) <= sizeof(uint32_t)) {
376 if (GcovBuffer.readInt(Val) && Val <= std::numeric_limits<T>::max())
377 return static_cast<T>(Val);
378 } else if (sizeof(T) <= sizeof(uint64_t)) {
380 if (GcovBuffer.readInt64(Val) && Val <= std::numeric_limits<T>::max())
381 return static_cast<T>(Val);
384 std::error_code EC = sampleprof_error::malformed;
385 reportError(0, EC.message());
389 ErrorOr<StringRef> SampleProfileReaderGCC::readString() {
391 if (!GcovBuffer.readString(Str))
392 return sampleprof_error::truncated;
396 std::error_code SampleProfileReaderGCC::readHeader() {
397 // Read the magic identifier.
398 if (!GcovBuffer.readGCDAFormat())
399 return sampleprof_error::unrecognized_format;
401 // Read the version number. Note - the GCC reader does not validate this
402 // version, but the profile creator generates v704.
403 GCOV::GCOVVersion version;
404 if (!GcovBuffer.readGCOVVersion(version))
405 return sampleprof_error::unrecognized_format;
407 if (version != GCOV::V704)
408 return sampleprof_error::unsupported_version;
410 // Skip the empty integer.
411 if (std::error_code EC = skipNextWord())
414 return sampleprof_error::success;
417 std::error_code SampleProfileReaderGCC::readSectionTag(uint32_t Expected) {
419 if (!GcovBuffer.readInt(Tag))
420 return sampleprof_error::truncated;
423 return sampleprof_error::malformed;
425 if (std::error_code EC = skipNextWord())
428 return sampleprof_error::success;
431 std::error_code SampleProfileReaderGCC::readNameTable() {
432 if (std::error_code EC = readSectionTag(GCOVTagAFDOFileNames))
436 if (!GcovBuffer.readInt(Size))
437 return sampleprof_error::truncated;
439 for (uint32_t I = 0; I < Size; ++I) {
441 if (!GcovBuffer.readString(Str))
442 return sampleprof_error::truncated;
443 Names.push_back(Str);
446 return sampleprof_error::success;
449 std::error_code SampleProfileReaderGCC::readFunctionProfiles() {
450 if (std::error_code EC = readSectionTag(GCOVTagAFDOFunction))
453 uint32_t NumFunctions;
454 if (!GcovBuffer.readInt(NumFunctions))
455 return sampleprof_error::truncated;
458 for (uint32_t I = 0; I < NumFunctions; ++I)
459 if (std::error_code EC = readOneFunctionProfile(Stack, true))
462 return sampleprof_error::success;
465 std::error_code SampleProfileReaderGCC::addSourceCount(StringRef Name,
466 const SourceStack &Src,
468 if (Src.size() == 0 || Src[0].Malformed())
469 return sampleprof_error::malformed;
470 FunctionSamples &FProfile = Profiles[Name];
471 FProfile.addTotalSamples(Count);
472 // FIXME(dnovillo) - Properly update inline stack for FnName.
473 FProfile.addBodySamples(Src[0].Line, Src[0].Discriminator, Count);
474 return sampleprof_error::success;
479 SampleProfileReaderGCC::readOneFunctionProfile(const SourceStack &Stack,
481 uint64_t HeadCount = 0;
482 if (Stack.size() == 0)
483 if (!GcovBuffer.readInt64(HeadCount))
484 return sampleprof_error::truncated;
487 if (!GcovBuffer.readInt(NameIdx))
488 return sampleprof_error::truncated;
490 StringRef Name(Names[NameIdx]);
492 uint32_t NumPosCounts;
493 if (!GcovBuffer.readInt(NumPosCounts))
494 return sampleprof_error::truncated;
496 uint32_t NumCallSites;
497 if (!GcovBuffer.readInt(NumCallSites))
498 return sampleprof_error::truncated;
500 if (Stack.size() == 0) {
501 FunctionSamples &FProfile = Profiles[Name];
502 FProfile.addHeadSamples(HeadCount);
503 if (FProfile.getTotalSamples() > 0)
507 for (uint32_t I = 0; I < NumPosCounts; ++I) {
509 if (!GcovBuffer.readInt(Offset))
510 return sampleprof_error::truncated;
513 if (!GcovBuffer.readInt(NumTargets))
514 return sampleprof_error::truncated;
517 if (!GcovBuffer.readInt64(Count))
518 return sampleprof_error::truncated;
520 SourceInfo Info(Name, "", "", 0, Offset >> 16, Offset & 0xffff);
521 SourceStack NewStack;
522 NewStack.push_back(Info);
523 NewStack.insert(NewStack.end(), Stack.begin(), Stack.end());
525 addSourceCount(NewStack[NewStack.size() - 1].FuncName, NewStack, Count);
527 for (uint32_t J = 0; J < NumTargets; J++) {
529 if (!GcovBuffer.readInt(HistVal))
530 return sampleprof_error::truncated;
532 if (HistVal != HIST_TYPE_INDIR_CALL_TOPN)
533 return sampleprof_error::malformed;
536 if (!GcovBuffer.readInt64(TargetIdx))
537 return sampleprof_error::truncated;
538 StringRef TargetName(Names[TargetIdx]);
540 uint64_t TargetCount;
541 if (!GcovBuffer.readInt64(TargetCount))
542 return sampleprof_error::truncated;
545 FunctionSamples &TargetProfile = Profiles[TargetName];
546 TargetProfile.addBodySamples(NewStack[0].Line,
547 NewStack[0].Discriminator, TargetCount);
552 for (uint32_t I = 0; I < NumCallSites; I++) {
553 // The offset is encoded as:
554 // high 16 bits: line offset to the start of the function.
555 // low 16 bits: discriminator.
557 if (!GcovBuffer.readInt(Offset))
558 return sampleprof_error::truncated;
559 SourceInfo Info(Name, "", "", 0, Offset >> 16, Offset & 0xffff);
560 SourceStack NewStack;
561 NewStack.push_back(Info);
562 NewStack.insert(NewStack.end(), Stack.begin(), Stack.end());
563 if (std::error_code EC = readOneFunctionProfile(NewStack, Update))
567 return sampleprof_error::success;
570 std::error_code SampleProfileReaderGCC::readModuleGroup() {
571 // FIXME(dnovillo) - Module support still not implemented.
572 return sampleprof_error::not_implemented;
575 std::error_code SampleProfileReaderGCC::readWorkingSet() {
576 // FIXME(dnovillo) - Working sets still not implemented.
577 return sampleprof_error::not_implemented;
581 /// \brief Read a GCC AutoFDO profile.
583 /// This format is generated by the Linux Perf conversion tool at
584 /// https://github.com/google/autofdo.
585 std::error_code SampleProfileReaderGCC::read() {
586 // Read the string table.
587 if (std::error_code EC = readNameTable())
590 // Read the source profile.
591 if (std::error_code EC = readFunctionProfiles())
594 // FIXME(dnovillo) - Module groups and working set support are not
597 // Read the module group file.
598 if (std::error_code EC = readModuleGroup())
601 // Read the working set.
602 if (std::error_code EC = readWorkingSet())
606 return sampleprof_error::success;
609 bool SampleProfileReaderGCC::hasFormat(const MemoryBuffer &Buffer) {
610 StringRef Magic(reinterpret_cast<const char *>(Buffer.getBufferStart()));
611 return Magic == "adcg*704";
614 /// \brief Prepare a memory buffer for the contents of \p Filename.
616 /// \returns an error code indicating the status of the buffer.
617 static ErrorOr<std::unique_ptr<MemoryBuffer>>
618 setupMemoryBuffer(std::string Filename) {
619 auto BufferOrErr = MemoryBuffer::getFileOrSTDIN(Filename);
620 if (std::error_code EC = BufferOrErr.getError())
622 auto Buffer = std::move(BufferOrErr.get());
624 // Sanity check the file.
625 if (Buffer->getBufferSize() > std::numeric_limits<unsigned>::max())
626 return sampleprof_error::too_large;
628 return std::move(Buffer);
631 /// \brief Create a sample profile reader based on the format of the input file.
633 /// \param Filename The file to open.
635 /// \param Reader The reader to instantiate according to \p Filename's format.
637 /// \param C The LLVM context to use to emit diagnostics.
639 /// \returns an error code indicating the status of the created reader.
640 ErrorOr<std::unique_ptr<SampleProfileReader>>
641 SampleProfileReader::create(StringRef Filename, LLVMContext &C) {
642 auto BufferOrError = setupMemoryBuffer(Filename);
643 if (std::error_code EC = BufferOrError.getError())
646 auto Buffer = std::move(BufferOrError.get());
647 std::unique_ptr<SampleProfileReader> Reader;
648 if (SampleProfileReaderBinary::hasFormat(*Buffer))
649 Reader.reset(new SampleProfileReaderBinary(std::move(Buffer), C));
650 else if (SampleProfileReaderGCC::hasFormat(*Buffer))
651 Reader.reset(new SampleProfileReaderGCC(std::move(Buffer), C));
653 Reader.reset(new SampleProfileReaderText(std::move(Buffer), C));
655 if (std::error_code EC = Reader->readHeader())
658 return std::move(Reader);