lib/ProfileData/SampleProfReader.cpp

   1 //===- SampleProfReader.cpp - Read LLVM sample profile data ---------------===//
   2 //
   3 //                      The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  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.
  15 //
  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.
  19 //
  20 // Text format
  21 // -----------
  22 //
  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
  26 //
  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 ... ]
  30 //      ...
  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 ... ]
  34 //       ...
  35 //
  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.
  40 //
  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.
  44 //
  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.
  51 //
  52 // There are two types of lines in the function body.
  53 //
  54 // * Sampled line represents the profile information of a source location.
  55 // * Callsite line represents the profile inofrmation of a callsite.
  56 //
  57 // Each sampled line may contain several items. Some are optional (marked
  58 // below):
  59 //
  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.
  65 //
  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
  72 //    in the macro).
  73 //
  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.
  80 //
  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
  87 //    frequently.
  88 //
  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``.
  93 //
  94 // c. Number of samples. This is an integer quantity representing the
  95 //    number of samples collected by the profiler at this source
  96 //    location.
  97 //
  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,
 101 //
 102 //      130: 7  foo:3  bar:2  baz:7
 103 //
 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.
 107 //
 108 // Each callsite line may contain several items. Some are optional.
 109 //
 110 // a. Source line offset. This number represents the line number of the
 111 //    callsite that is inlined in the profiled binary.
 112 //
 113 // b. [OPTIONAL] Discriminator. Same as the discriminator for sampled line.
 114 //
 115 // c. Number of samples. This is an integer quantity representing the
 116 //    total number of samples collected for the inlined instance at this
 117 //    callsite
 118 //===----------------------------------------------------------------------===//
 119
 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"
 128
 129 using namespace llvm::sampleprof;
 130 using namespace llvm;
 131
 132 /// \brief Print the samples collected for a function on stream \p OS.
 133 ///
 134 /// \param OS Stream to emit the output to.
 135 void FunctionSamples::print(raw_ostream &OS, unsigned Indent) const {
 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.indent(Indent);
 142     OS << "line offset: " << Loc.LineOffset
 143        << ", discriminator: " << Loc.Discriminator
 144        << ", number of samples: " << Sample.getSamples();
 145     if (Sample.hasCalls()) {
 146       OS << ", calls:";
 147       for (const auto &I : Sample.getCallTargets())
 148         OS << " " << I.first() << ":" << I.second;
 149     }
 150     OS << "\n";
 151   }
 152   for (const auto &CS : CallsiteSamples) {
 153     CallsiteLocation Loc = CS.first;
 154     const FunctionSamples &CalleeSamples = CS.second;
 155     OS.indent(Indent);
 156     OS << "line offset: " << Loc.LineOffset
 157        << ", discriminator: " << Loc.Discriminator
 158        << ", inlined callee: " << Loc.CalleeName << ": ";
 159     CalleeSamples.print(OS, Indent + 2);
 160   }
 161 }
 162
 163 /// \brief Dump the function profile for \p FName.
 164 ///
 165 /// \param FName Name of the function to print.
 166 /// \param OS Stream to emit the output to.
 167 void SampleProfileReader::dumpFunctionProfile(StringRef FName,
 168                                               raw_ostream &OS) {
 169   OS << "Function: " << FName << ": ";
 170   Profiles[FName].print(OS);
 171 }
 172
 173 /// \brief Dump all the function profiles found on stream \p OS.
 174 void SampleProfileReader::dump(raw_ostream &OS) {
 175   for (const auto &I : Profiles)
 176     dumpFunctionProfile(I.getKey(), OS);
 177 }
 178
 179 /// \brief Parse \p Input as function head.
 180 ///
 181 /// Parse one line of \p Input, and update function name in \p FName,
 182 /// function's total sample count in \p NumSamples, function's entry
 183 /// count in \p NumHeadSamples.
 184 ///
 185 /// \returns true if parsing is successful.
 186 static bool ParseHead(const StringRef &Input, StringRef &FName,
 187                       unsigned &NumSamples, unsigned &NumHeadSamples) {
 188   if (Input[0] == ' ')
 189     return false;
 190   size_t n2 = Input.rfind(':');
 191   size_t n1 = Input.rfind(':', n2 - 1);
 192   FName = Input.substr(0, n1);
 193   if (Input.substr(n1 + 1, n2 - n1 - 1).getAsInteger(10, NumSamples))
 194     return false;
 195   if (Input.substr(n2 + 1).getAsInteger(10, NumHeadSamples))
 196     return false;
 197   return true;
 198 }
 199
 200 /// \brief Parse \p Input as line sample.
 201 ///
 202 /// \param Input input line.
 203 /// \param IsCallsite true if the line represents an inlined callsite.
 204 /// \param Depth the depth of the inline stack.
 205 /// \param NumSamples total samples of the line/inlined callsite.
 206 /// \param LineOffset line offset to the start of the function.
 207 /// \param Discriminator discriminator of the line.
 208 /// \param TargetCountMap map from indirect call target to count.
 209 ///
 210 /// returns true if parsing is successful.
 211 static bool ParseLine(const StringRef &Input, bool &IsCallsite, unsigned &Depth,
 212                       unsigned &NumSamples, unsigned &LineOffset,
 213                       unsigned &Discriminator, StringRef &CalleeName,
 214                       DenseMap<StringRef, unsigned> &TargetCountMap) {
 215   for (Depth = 0; Input[Depth] == ' '; Depth++)
 216     ;
 217   if (Depth == 0)
 218     return false;
 219
 220   size_t n1 = Input.find(':');
 221   StringRef Loc = Input.substr(Depth, n1 - Depth);
 222   size_t n2 = Loc.find('.');
 223   if (n2 == StringRef::npos) {
 224     if (Loc.getAsInteger(10, LineOffset))
 225       return false;
 226     Discriminator = 0;
 227   } else {
 228     if (Loc.substr(0, n2).getAsInteger(10, LineOffset))
 229       return false;
 230     if (Loc.substr(n2 + 1).getAsInteger(10, Discriminator))
 231       return false;
 232   }
 233
 234   StringRef Rest = Input.substr(n1 + 2);
 235   if (Rest[0] >= '0' && Rest[0] <= '9') {
 236     IsCallsite = false;
 237     size_t n3 = Rest.find(' ');
 238     if (n3 == StringRef::npos) {
 239       if (Rest.getAsInteger(10, NumSamples))
 240         return false;
 241     } else {
 242       if (Rest.substr(0, n3).getAsInteger(10, NumSamples))
 243         return false;
 244     }
 245     while (n3 != StringRef::npos) {
 246       n3 += Rest.substr(n3).find_first_not_of(' ');
 247       Rest = Rest.substr(n3);
 248       n3 = Rest.find(' ');
 249       StringRef pair = Rest;
 250       if (n3 != StringRef::npos) {
 251         pair = Rest.substr(0, n3);
 252       }
 253       int n4 = pair.find(':');
 254       unsigned count;
 255       if (pair.substr(n4 + 1).getAsInteger(10, count))
 256         return false;
 257       TargetCountMap[pair.substr(0, n4)] = count;
 258     }
 259   } else {
 260     IsCallsite = true;
 261     int n3 = Rest.find_last_of(':');
 262     CalleeName = Rest.substr(0, n3);
 263     if (Rest.substr(n3 + 1).getAsInteger(10, NumSamples))
 264       return false;
 265   }
 266   return true;
 267 }
 268
 269 /// \brief Load samples from a text file.
 270 ///
 271 /// See the documentation at the top of the file for an explanation of
 272 /// the expected format.
 273 ///
 274 /// \returns true if the file was loaded successfully, false otherwise.
 275 std::error_code SampleProfileReaderText::read() {
 276   line_iterator LineIt(*Buffer, /*SkipBlanks=*/true, '#');
 277
 278   InlineCallStack InlineStack;
 279
 280   for (; !LineIt.is_at_eof(); ++LineIt) {
 281     if ((*LineIt)[(*LineIt).find_first_not_of(' ')] == '#')
 282       continue;
 283     // Read the header of each function.
 284     //
 285     // Note that for function identifiers we are actually expecting
 286     // mangled names, but we may not always get them. This happens when
 287     // the compiler decides not to emit the function (e.g., it was inlined
 288     // and removed). In this case, the binary will not have the linkage
 289     // name for the function, so the profiler will emit the function's
 290     // unmangled name, which may contain characters like ':' and '>' in its
 291     // name (member functions, templates, etc).
 292     //
 293     // The only requirement we place on the identifier, then, is that it
 294     // should not begin with a number.
 295     if ((*LineIt)[0] != ' ') {
 296       unsigned NumSamples, NumHeadSamples;
 297       StringRef FName;
 298       if (!ParseHead(*LineIt, FName, NumSamples, NumHeadSamples)) {
 299         reportError(LineIt.line_number(),
 300                     "Expected 'mangled_name:NUM:NUM', found " + *LineIt);
 301         return sampleprof_error::malformed;
 302       }
 303       Profiles[FName] = FunctionSamples();
 304       FunctionSamples &FProfile = Profiles[FName];
 305       FProfile.addTotalSamples(NumSamples);
 306       FProfile.addHeadSamples(NumHeadSamples);
 307       InlineStack.clear();
 308       InlineStack.push_back(&FProfile);
 309     } else {
 310       unsigned NumSamples;
 311       StringRef FName;
 312       DenseMap<StringRef, unsigned> TargetCountMap;
 313       bool IsCallsite;
 314       unsigned Depth, LineOffset, Discriminator;
 315       if (!ParseLine(*LineIt, IsCallsite, Depth, NumSamples, LineOffset,
 316                      Discriminator, FName, TargetCountMap)) {
 317         reportError(LineIt.line_number(),
 318                     "Expected 'NUM[.NUM]: NUM[ mangled_name:NUM]*', found " +
 319                         *LineIt);
 320         return sampleprof_error::malformed;
 321       }
 322       if (IsCallsite) {
 323         while (InlineStack.size() > Depth) {
 324           InlineStack.pop_back();
 325         }
 326         FunctionSamples &FSamples = InlineStack.back()->functionSamplesAt(
 327             CallsiteLocation(LineOffset, Discriminator, FName));
 328         FSamples.addTotalSamples(NumSamples);
 329         InlineStack.push_back(&FSamples);
 330       } else {
 331         while (InlineStack.size() > Depth) {
 332           InlineStack.pop_back();
 333         }
 334         FunctionSamples &FProfile = *InlineStack.back();
 335         for (const auto &name_count : TargetCountMap) {
 336           FProfile.addCalledTargetSamples(LineOffset, Discriminator,
 337                                           name_count.first, name_count.second);
 338         }
 339         FProfile.addBodySamples(LineOffset, Discriminator, NumSamples);
 340       }
 341     }
 342   }
 343
 344   return sampleprof_error::success;
 345 }
 346
 347 template <typename T> ErrorOr<T> SampleProfileReaderBinary::readNumber() {
 348   unsigned NumBytesRead = 0;
 349   std::error_code EC;
 350   uint64_t Val = decodeULEB128(Data, &NumBytesRead);
 351
 352   if (Val > std::numeric_limits<T>::max())
 353     EC = sampleprof_error::malformed;
 354   else if (Data + NumBytesRead > End)
 355     EC = sampleprof_error::truncated;
 356   else
 357     EC = sampleprof_error::success;
 358
 359   if (EC) {
 360     reportError(0, EC.message());
 361     return EC;
 362   }
 363
 364   Data += NumBytesRead;
 365   return static_cast<T>(Val);
 366 }
 367
 368 ErrorOr<StringRef> SampleProfileReaderBinary::readString() {
 369   std::error_code EC;
 370   StringRef Str(reinterpret_cast<const char *>(Data));
 371   if (Data + Str.size() + 1 > End) {
 372     EC = sampleprof_error::truncated;
 373     reportError(0, EC.message());
 374     return EC;
 375   }
 376
 377   Data += Str.size() + 1;
 378   return Str;
 379 }
 380
 381 std::error_code
 382 SampleProfileReaderBinary::readProfile(FunctionSamples &FProfile) {
 383   auto Val = readNumber<unsigned>();
 384   if (std::error_code EC = Val.getError())
 385     return EC;
 386   FProfile.addTotalSamples(*Val);
 387
 388   Val = readNumber<unsigned>();
 389   if (std::error_code EC = Val.getError())
 390     return EC;
 391   FProfile.addHeadSamples(*Val);
 392
 393   // Read the samples in the body.
 394   auto NumRecords = readNumber<unsigned>();
 395   if (std::error_code EC = NumRecords.getError())
 396     return EC;
 397
 398   for (unsigned I = 0; I < *NumRecords; ++I) {
 399     auto LineOffset = readNumber<uint64_t>();
 400     if (std::error_code EC = LineOffset.getError())
 401       return EC;
 402
 403     auto Discriminator = readNumber<uint64_t>();
 404     if (std::error_code EC = Discriminator.getError())
 405       return EC;
 406
 407     auto NumSamples = readNumber<uint64_t>();
 408     if (std::error_code EC = NumSamples.getError())
 409       return EC;
 410
 411     auto NumCalls = readNumber<unsigned>();
 412     if (std::error_code EC = NumCalls.getError())
 413       return EC;
 414
 415     for (unsigned J = 0; J < *NumCalls; ++J) {
 416       auto CalledFunction(readString());
 417       if (std::error_code EC = CalledFunction.getError())
 418         return EC;
 419
 420       auto CalledFunctionSamples = readNumber<uint64_t>();
 421       if (std::error_code EC = CalledFunctionSamples.getError())
 422         return EC;
 423
 424       FProfile.addCalledTargetSamples(*LineOffset, *Discriminator,
 425                                       *CalledFunction, *CalledFunctionSamples);
 426     }
 427
 428     FProfile.addBodySamples(*LineOffset, *Discriminator, *NumSamples);
 429   }
 430
 431   // Read all the samples for inlined function calls.
 432   auto NumCallsites = readNumber<unsigned>();
 433   if (std::error_code EC = NumCallsites.getError())
 434     return EC;
 435
 436   for (unsigned J = 0; J < *NumCallsites; ++J) {
 437     auto LineOffset = readNumber<uint64_t>();
 438     if (std::error_code EC = LineOffset.getError())
 439       return EC;
 440
 441     auto Discriminator = readNumber<uint64_t>();
 442     if (std::error_code EC = Discriminator.getError())
 443       return EC;
 444
 445     auto FName(readString());
 446     if (std::error_code EC = FName.getError())
 447       return EC;
 448
 449     FunctionSamples &CalleeProfile = FProfile.functionSamplesAt(
 450         CallsiteLocation(*LineOffset, *Discriminator, *FName));
 451     if (std::error_code EC = readProfile(CalleeProfile))
 452       return EC;
 453   }
 454
 455   return sampleprof_error::success;
 456 }
 457
 458 std::error_code SampleProfileReaderBinary::read() {
 459   while (!at_eof()) {
 460     auto FName(readString());
 461     if (std::error_code EC = FName.getError())
 462       return EC;
 463
 464     Profiles[*FName] = FunctionSamples();
 465     FunctionSamples &FProfile = Profiles[*FName];
 466
 467     if (std::error_code EC = readProfile(FProfile))
 468       return EC;
 469   }
 470
 471   return sampleprof_error::success;
 472 }
 473
 474 std::error_code SampleProfileReaderBinary::readHeader() {
 475   Data = reinterpret_cast<const uint8_t *>(Buffer->getBufferStart());
 476   End = Data + Buffer->getBufferSize();
 477
 478   // Read and check the magic identifier.
 479   auto Magic = readNumber<uint64_t>();
 480   if (std::error_code EC = Magic.getError())
 481     return EC;
 482   else if (*Magic != SPMagic())
 483     return sampleprof_error::bad_magic;
 484
 485   // Read the version number.
 486   auto Version = readNumber<uint64_t>();
 487   if (std::error_code EC = Version.getError())
 488     return EC;
 489   else if (*Version != SPVersion())
 490     return sampleprof_error::unsupported_version;
 491
 492   return sampleprof_error::success;
 493 }
 494
 495 bool SampleProfileReaderBinary::hasFormat(const MemoryBuffer &Buffer) {
 496   const uint8_t *Data =
 497       reinterpret_cast<const uint8_t *>(Buffer.getBufferStart());
 498   uint64_t Magic = decodeULEB128(Data);
 499   return Magic == SPMagic();
 500 }
 501
 502 bool SourceInfo::operator<(const SourceInfo &P) const {
 503   if (Line != P.Line)
 504     return Line < P.Line;
 505   if (StartLine != P.StartLine)
 506     return StartLine < P.StartLine;
 507   if (Discriminator != P.Discriminator)
 508     return Discriminator < P.Discriminator;
 509   return FuncName < P.FuncName;
 510 }
 511
 512 std::error_code SampleProfileReaderGCC::skipNextWord() {
 513   uint32_t dummy;
 514   if (!GcovBuffer.readInt(dummy))
 515     return sampleprof_error::truncated;
 516   return sampleprof_error::success;
 517 }
 518
 519 template <typename T> ErrorOr<T> SampleProfileReaderGCC::readNumber() {
 520   if (sizeof(T) <= sizeof(uint32_t)) {
 521     uint32_t Val;
 522     if (GcovBuffer.readInt(Val) && Val <= std::numeric_limits<T>::max())
 523       return static_cast<T>(Val);
 524   } else if (sizeof(T) <= sizeof(uint64_t)) {
 525     uint64_t Val;
 526     if (GcovBuffer.readInt64(Val) && Val <= std::numeric_limits<T>::max())
 527       return static_cast<T>(Val);
 528   }
 529
 530   std::error_code EC = sampleprof_error::malformed;
 531   reportError(0, EC.message());
 532   return EC;
 533 }
 534
 535 ErrorOr<StringRef> SampleProfileReaderGCC::readString() {
 536   StringRef Str;
 537   if (!GcovBuffer.readString(Str))
 538     return sampleprof_error::truncated;
 539   return Str;
 540 }
 541
 542 std::error_code SampleProfileReaderGCC::readHeader() {
 543   // Read the magic identifier.
 544   if (!GcovBuffer.readGCDAFormat())
 545     return sampleprof_error::unrecognized_format;
 546
 547   // Read the version number. Note - the GCC reader does not validate this
 548   // version, but the profile creator generates v704.
 549   GCOV::GCOVVersion version;
 550   if (!GcovBuffer.readGCOVVersion(version))
 551     return sampleprof_error::unrecognized_format;
 552
 553   if (version != GCOV::V704)
 554     return sampleprof_error::unsupported_version;
 555
 556   // Skip the empty integer.
 557   if (std::error_code EC = skipNextWord())
 558     return EC;
 559
 560   return sampleprof_error::success;
 561 }
 562
 563 std::error_code SampleProfileReaderGCC::readSectionTag(uint32_t Expected) {
 564   uint32_t Tag;
 565   if (!GcovBuffer.readInt(Tag))
 566     return sampleprof_error::truncated;
 567
 568   if (Tag != Expected)
 569     return sampleprof_error::malformed;
 570
 571   if (std::error_code EC = skipNextWord())
 572     return EC;
 573
 574   return sampleprof_error::success;
 575 }
 576
 577 std::error_code SampleProfileReaderGCC::readNameTable() {
 578   if (std::error_code EC = readSectionTag(GCOVTagAFDOFileNames))
 579     return EC;
 580
 581   uint32_t Size;
 582   if (!GcovBuffer.readInt(Size))
 583     return sampleprof_error::truncated;
 584
 585   for (uint32_t I = 0; I < Size; ++I) {
 586     StringRef Str;
 587     if (!GcovBuffer.readString(Str))
 588       return sampleprof_error::truncated;
 589     Names.push_back(Str);
 590   }
 591
 592   return sampleprof_error::success;
 593 }
 594
 595 std::error_code SampleProfileReaderGCC::readFunctionProfiles() {
 596   if (std::error_code EC = readSectionTag(GCOVTagAFDOFunction))
 597     return EC;
 598
 599   uint32_t NumFunctions;
 600   if (!GcovBuffer.readInt(NumFunctions))
 601     return sampleprof_error::truncated;
 602
 603   InlineCallStack Stack;
 604   for (uint32_t I = 0; I < NumFunctions; ++I)
 605     if (std::error_code EC = readOneFunctionProfile(Stack, true, 0))
 606       return EC;
 607
 608   return sampleprof_error::success;
 609 }
 610
 611 std::error_code SampleProfileReaderGCC::readOneFunctionProfile(
 612     const InlineCallStack &InlineStack, bool Update, uint32_t Offset) {
 613   uint64_t HeadCount = 0;
 614   if (InlineStack.size() == 0)
 615     if (!GcovBuffer.readInt64(HeadCount))
 616       return sampleprof_error::truncated;
 617
 618   uint32_t NameIdx;
 619   if (!GcovBuffer.readInt(NameIdx))
 620     return sampleprof_error::truncated;
 621
 622   StringRef Name(Names[NameIdx]);
 623
 624   uint32_t NumPosCounts;
 625   if (!GcovBuffer.readInt(NumPosCounts))
 626     return sampleprof_error::truncated;
 627
 628   uint32_t NumCallsites;
 629   if (!GcovBuffer.readInt(NumCallsites))
 630     return sampleprof_error::truncated;
 631
 632   FunctionSamples *FProfile = nullptr;
 633   if (InlineStack.size() == 0) {
 634     // If this is a top function that we have already processed, do not
 635     // update its profile again.  This happens in the presence of
 636     // function aliases.  Since these aliases share the same function
 637     // body, there will be identical replicated profiles for the
 638     // original function.  In this case, we simply not bother updating
 639     // the profile of the original function.
 640     FProfile = &Profiles[Name];
 641     FProfile->addHeadSamples(HeadCount);
 642     if (FProfile->getTotalSamples() > 0)
 643       Update = false;
 644   } else {
 645     // Otherwise, we are reading an inlined instance. The top of the
 646     // inline stack contains the profile of the caller. Insert this
 647     // callee in the caller's CallsiteMap.
 648     FunctionSamples *CallerProfile = InlineStack.front();
 649     uint32_t LineOffset = Offset >> 16;
 650     uint32_t Discriminator = Offset & 0xffff;
 651     FProfile = &CallerProfile->functionSamplesAt(
 652         CallsiteLocation(LineOffset, Discriminator, Name));
 653   }
 654
 655   for (uint32_t I = 0; I < NumPosCounts; ++I) {
 656     uint32_t Offset;
 657     if (!GcovBuffer.readInt(Offset))
 658       return sampleprof_error::truncated;
 659
 660     uint32_t NumTargets;
 661     if (!GcovBuffer.readInt(NumTargets))
 662       return sampleprof_error::truncated;
 663
 664     uint64_t Count;
 665     if (!GcovBuffer.readInt64(Count))
 666       return sampleprof_error::truncated;
 667
 668     // The line location is encoded in the offset as:
 669     //   high 16 bits: line offset to the start of the function.
 670     //   low 16 bits: discriminator.
 671     uint32_t LineOffset = Offset >> 16;
 672     uint32_t Discriminator = Offset & 0xffff;
 673
 674     InlineCallStack NewStack;
 675     NewStack.push_back(FProfile);
 676     NewStack.insert(NewStack.end(), InlineStack.begin(), InlineStack.end());
 677     if (Update) {
 678       // Walk up the inline stack, adding the samples on this line to
 679       // the total sample count of the callers in the chain.
 680       for (auto CallerProfile : NewStack)
 681         CallerProfile->addTotalSamples(Count);
 682
 683       // Update the body samples for the current profile.
 684       FProfile->addBodySamples(LineOffset, Discriminator, Count);
 685     }
 686
 687     // Process the list of functions called at an indirect call site.
 688     // These are all the targets that a function pointer (or virtual
 689     // function) resolved at runtime.
 690     for (uint32_t J = 0; J < NumTargets; J++) {
 691       uint32_t HistVal;
 692       if (!GcovBuffer.readInt(HistVal))
 693         return sampleprof_error::truncated;
 694
 695       if (HistVal != HIST_TYPE_INDIR_CALL_TOPN)
 696         return sampleprof_error::malformed;
 697
 698       uint64_t TargetIdx;
 699       if (!GcovBuffer.readInt64(TargetIdx))
 700         return sampleprof_error::truncated;
 701       StringRef TargetName(Names[TargetIdx]);
 702
 703       uint64_t TargetCount;
 704       if (!GcovBuffer.readInt64(TargetCount))
 705         return sampleprof_error::truncated;
 706
 707       if (Update) {
 708         FunctionSamples &TargetProfile = Profiles[TargetName];
 709         TargetProfile.addCalledTargetSamples(LineOffset, Discriminator,
 710                                              TargetName, TargetCount);
 711       }
 712     }
 713   }
 714
 715   // Process all the inlined callers into the current function. These
 716   // are all the callsites that were inlined into this function.
 717   for (uint32_t I = 0; I < NumCallsites; I++) {
 718     // The offset is encoded as:
 719     //   high 16 bits: line offset to the start of the function.
 720     //   low 16 bits: discriminator.
 721     uint32_t Offset;
 722     if (!GcovBuffer.readInt(Offset))
 723       return sampleprof_error::truncated;
 724     InlineCallStack NewStack;
 725     NewStack.push_back(FProfile);
 726     NewStack.insert(NewStack.end(), InlineStack.begin(), InlineStack.end());
 727     if (std::error_code EC = readOneFunctionProfile(NewStack, Update, Offset))
 728       return EC;
 729   }
 730
 731   return sampleprof_error::success;
 732 }
 733
 734 /// \brief Read a GCC AutoFDO profile.
 735 ///
 736 /// This format is generated by the Linux Perf conversion tool at
 737 /// https://github.com/google/autofdo.
 738 std::error_code SampleProfileReaderGCC::read() {
 739   // Read the string table.
 740   if (std::error_code EC = readNameTable())
 741     return EC;
 742
 743   // Read the source profile.
 744   if (std::error_code EC = readFunctionProfiles())
 745     return EC;
 746
 747   return sampleprof_error::success;
 748 }
 749
 750 bool SampleProfileReaderGCC::hasFormat(const MemoryBuffer &Buffer) {
 751   StringRef Magic(reinterpret_cast<const char *>(Buffer.getBufferStart()));
 752   return Magic == "adcg*704";
 753 }
 754
 755 /// \brief Prepare a memory buffer for the contents of \p Filename.
 756 ///
 757 /// \returns an error code indicating the status of the buffer.
 758 static ErrorOr<std::unique_ptr<MemoryBuffer>>
 759 setupMemoryBuffer(std::string Filename) {
 760   auto BufferOrErr = MemoryBuffer::getFileOrSTDIN(Filename);
 761   if (std::error_code EC = BufferOrErr.getError())
 762     return EC;
 763   auto Buffer = std::move(BufferOrErr.get());
 764
 765   // Sanity check the file.
 766   if (Buffer->getBufferSize() > std::numeric_limits<unsigned>::max())
 767     return sampleprof_error::too_large;
 768
 769   return std::move(Buffer);
 770 }
 771
 772 /// \brief Create a sample profile reader based on the format of the input file.
 773 ///
 774 /// \param Filename The file to open.
 775 ///
 776 /// \param Reader The reader to instantiate according to \p Filename's format.
 777 ///
 778 /// \param C The LLVM context to use to emit diagnostics.
 779 ///
 780 /// \returns an error code indicating the status of the created reader.
 781 ErrorOr<std::unique_ptr<SampleProfileReader>>
 782 SampleProfileReader::create(StringRef Filename, LLVMContext &C) {
 783   auto BufferOrError = setupMemoryBuffer(Filename);
 784   if (std::error_code EC = BufferOrError.getError())
 785     return EC;
 786
 787   auto Buffer = std::move(BufferOrError.get());
 788   std::unique_ptr<SampleProfileReader> Reader;
 789   if (SampleProfileReaderBinary::hasFormat(*Buffer))
 790     Reader.reset(new SampleProfileReaderBinary(std::move(Buffer), C));
 791   else if (SampleProfileReaderGCC::hasFormat(*Buffer))
 792     Reader.reset(new SampleProfileReaderGCC(std::move(Buffer), C));
 793   else
 794     Reader.reset(new SampleProfileReaderText(std::move(Buffer), C));
 795
 796   if (std::error_code EC = Reader->readHeader())
 797     return EC;
 798
 799   return std::move(Reader);
 800 }