[SampleFDO] Add a new compact binary format for sample profile

[wmi]

Summary

Name table occupies a big chunk of size in current binary format sample profile. In order to reduce its size, the patch changes the sample writer/reader to save/restore MD5Hash of names in the name table. Sample annotation phase will also use MD5Hash of name to query samples accordingly.

Experiment shows compact binary format can reduce the size of sample profile by 2/3 compared with binary format generally.

[wmi]

Update with a minor refactoring change.

[danielcdh]

This is great stuff!

[dyung]

llvm/trunk/tools/llvm-profdata/llvm-profdata.cpp

478 ↗

(On Diff #150864)

This description has two items that claim to be the default, is this a typo?

[llvm-commits]

• msg-839-131.txt162 BDownload

include/llvm/ProfileData/SampleProf.h

 template <>
 struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {};
 
 } // end namespace std
 
 namespace llvm {
 namespace sampleprof {
 
-static inline uint64_t SPMagic() {
+enum SampleProfileFormat {
+  SPF_None = 0,
+  SPF_Text = 0x1,
+  SPF_Compact_Binary = 0x2,
+  SPF_GCC = 0x3,
+  SPF_Raw_Binary = 0xff
+};
+
+static inline uint64_t SPMagic(SampleProfileFormat Format = SPF_Raw_Binary) {
   return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
          uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
          uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
-         uint64_t('2') << (64 - 56) | uint64_t(0xff);
+         uint64_t('2') << (64 - 56) | uint64_t(Format);
+}
+
+// Get the proper representation of a string in the input Format.
+static inline StringRef getRepInFormat(StringRef Name,
+                                       SampleProfileFormat Format,
+                                       std::string &GUIDBuf) {
+  GUIDBuf = std::to_string(Function::getGUID(Name));
+  return (Format == SPF_Compact_Binary) ? StringRef(GUIDBuf) : Name;
 }
 
 static inline uint64_t SPVersion() { return 103; }
 
 /// Represents the relative location of an instruction.
 ///
 /// Instruction locations are specified by the line offset from the
 /// beginning of the function (marked by the line where the function
sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
     return Result;
   }
 
   /// Recursively traverses all children, if the total sample count of the
   /// corresponding function is no less than \p Threshold, add its corresponding
   /// GUID to \p S. Also traverse the BodySamples to add hot CallTarget's GUID
   /// to \p S.
   void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
-                            uint64_t Threshold) const {
+                            uint64_t Threshold, bool isCompact) const {
     if (TotalSamples <= Threshold)
       return;
     S.insert(Function::getGUID(Name));
     // Import hot CallTargets, which may not be available in IR because full
     // profile annotation cannot be done until backend compilation in ThinLTO.
     for (const auto &BS : BodySamples)
       for (const auto &TS : BS.second.getCallTargets())
         if (TS.getValue() > Threshold) {
           Function *Callee = M->getFunction(TS.getKey());
           if (!Callee || !Callee->getSubprogram())
-            S.insert(Function::getGUID(TS.getKey()));
+            S.insert(isCompact ? std::stol(TS.getKey().data())
+                               : Function::getGUID(TS.getKey()));
         }
     for (const auto &CS : CallsiteSamples)
       for (const auto &NameFS : CS.second)
-        NameFS.second.findInlinedFunctions(S, M, Threshold);
+        NameFS.second.findInlinedFunctions(S, M, Threshold, isCompact);
   }
 
   /// Set the name of the function.
   void setName(StringRef FunctionName) { Name = FunctionName; }
 
   /// Return the function name.
   const StringRef &getName() const { return Name; }
 

include/llvm/ProfileData/SampleProfReader.h

 ///      protection against source code shuffling, line numbers should
 ///      be relative to the start of the function.
 ///
 /// The reader supports two file formats: text and binary. The text format
 /// is useful for debugging and testing, while the binary format is more
 /// compact and I/O efficient. They can both be used interchangeably.
 class SampleProfileReader {
 public:
-  SampleProfileReader(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
-      : Profiles(0), Ctx(C), Buffer(std::move(B)) {}
+  SampleProfileReader(std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
+                      SampleProfileFormat Format = SPF_None)
+      : Profiles(0), Ctx(C), Buffer(std::move(B)), Format(Format) {}
 
   virtual ~SampleProfileReader() = default;
 
   /// Read and validate the file header.
   virtual std::error_code readHeader() = 0;
 
   /// Read sample profiles from the associated file.
   virtual std::error_code read() = 0;
 
   /// Print the profile for \p FName on stream \p OS.
   void dumpFunctionProfile(StringRef FName, raw_ostream &OS = dbgs());
 
   /// Print all the profiles on stream \p OS.
   void dump(raw_ostream &OS = dbgs());
 
   /// Return the samples collected for function \p F.
   FunctionSamples *getSamplesFor(const Function &F) {
     // The function name may have been updated by adding suffix. In sample
     // profile, the function names are all stripped, so we need to strip
     // the function name suffix before matching with profile.
-    if (Profiles.count(F.getName().split('.').first))
-      return &Profiles[(F.getName().split('.').first)];
+    StringRef Fname = F.getName().split('.').first;
+    std::string FGUID;
+    Fname = getRepInFormat(Fname, getFormat(), FGUID);
+    if (Profiles.count(Fname))
+      return &Profiles[Fname];
     return nullptr;
   }
 
   /// Return all the profiles.
   StringMap<FunctionSamples> &getProfiles() { return Profiles; }
 
   /// Report a parse error message.
   void reportError(int64_t LineNumber, Twine Msg) const {
     Ctx.diagnose(DiagnosticInfoSampleProfile(Buffer->getBufferIdentifier(),
                                              LineNumber, Msg));
   }
 
   /// Create a sample profile reader appropriate to the file format.
   static ErrorOr<std::unique_ptr<SampleProfileReader>>
   create(const Twine &Filename, LLVMContext &C);
 
   /// Create a sample profile reader from the supplied memory buffer.
   static ErrorOr<std::unique_ptr<SampleProfileReader>>
   create(std::unique_ptr<MemoryBuffer> &B, LLVMContext &C);
 
   /// Return the profile summary.
   ProfileSummary &getSummary() { return *(Summary.get()); }
 
+  /// \brief Return the profile format.
+  SampleProfileFormat getFormat() { return Format; }
+
 protected:
   /// Map every function to its associated profile.
   ///
   /// The profile of every function executed at runtime is collected
   /// in the structure FunctionSamples. This maps function objects
   /// to their corresponding profiles.
   StringMap<FunctionSamples> Profiles;
 
   /// LLVM context used to emit diagnostics.
   LLVMContext &Ctx;
 
   /// Memory buffer holding the profile file.
   std::unique_ptr<MemoryBuffer> Buffer;
 
   /// Profile summary information.
   std::unique_ptr<ProfileSummary> Summary;
 
   /// Compute summary for this profile.
   void computeSummary();
+
+  /// \brief The format of sample.
+  SampleProfileFormat Format = SPF_None;
 };
 
 class SampleProfileReaderText : public SampleProfileReader {
 public:
   SampleProfileReaderText(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
-      : SampleProfileReader(std::move(B), C) {}
+      : SampleProfileReader(std::move(B), C, SPF_Text) {}
 
   /// Read and validate the file header.
   std::error_code readHeader() override { return sampleprof_error::success; }
 
   /// Read sample profiles from the associated file.
   std::error_code read() override;
 
   /// Return true if \p Buffer is in the format supported by this class.
   static bool hasFormat(const MemoryBuffer &Buffer);
 };
 
 class SampleProfileReaderBinary : public SampleProfileReader {
 public:
-  SampleProfileReaderBinary(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
-      : SampleProfileReader(std::move(B), C) {}
+  SampleProfileReaderBinary(std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
+                            SampleProfileFormat Format = SPF_None)
+      : SampleProfileReader(std::move(B), C, Format) {}
 
   /// Read and validate the file header.
   std::error_code readHeader() override;
 
   /// Read sample profiles from the associated file.
   std::error_code read() override;
 
-  /// Return true if \p Buffer is in the format supported by this class.
-  static bool hasFormat(const MemoryBuffer &Buffer);
-
 protected:
   /// Read a numeric value of type T from the profile.
   ///
   /// If an error occurs during decoding, a diagnostic message is emitted and
   /// EC is set.
   ///
   /// \returns the read value.
   template <typename T> ErrorOr<T> readNumber();
 
   /// Read a string from the profile.
   ///
   /// If an error occurs during decoding, a diagnostic message is emitted and
   /// EC is set.
   ///
   /// \returns the read value.
   ErrorOr<StringRef> readString();
 
-  /// Read a string indirectly via the name table.
-  ErrorOr<StringRef> readStringFromTable();
+  /// Read the string index and check whether it overflows the table.
+  template <typename T> inline ErrorOr<uint32_t> readStringIndex(T &Table);
 
   /// Return true if we've reached the end of file.
   bool at_eof() const { return Data >= End; }
 
   /// Read the contents of the given profile instance.
   std::error_code readProfile(FunctionSamples &FProfile);
 
   /// Points to the current location in the buffer.
   const uint8_t *Data = nullptr;
 
   /// Points to the end of the buffer.
   const uint8_t *End = nullptr;
 
-  /// Function name table.
-  std::vector<StringRef> NameTable;
-
 private:
   std::error_code readSummaryEntry(std::vector<ProfileSummaryEntry> &Entries);
+  virtual std::error_code verifySPMagic(uint64_t Magic) = 0;
 
   /// Read profile summary.
   std::error_code readSummary();
+
+  /// Read the whole name table.
+  virtual std::error_code readNameTable() = 0;
+
+  /// Read a string indirectly via the name table.
+  virtual ErrorOr<StringRef> readStringFromTable() = 0;
+};
+
+class SampleProfileReaderRawBinary : public SampleProfileReaderBinary {
+private:
+  /// Function name table.
+  std::vector<StringRef> NameTable;
+  virtual std::error_code verifySPMagic(uint64_t Magic) override;
+  virtual std::error_code readNameTable() override;
+  /// Read a string indirectly via the name table.
+  virtual ErrorOr<StringRef> readStringFromTable() override;
+
+public:
+  SampleProfileReaderRawBinary(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
+      : SampleProfileReaderBinary(std::move(B), C, SPF_Raw_Binary) {}
+
+  /// \brief Return true if \p Buffer is in the format supported by this class.
+  static bool hasFormat(const MemoryBuffer &Buffer);
+};
+
+class SampleProfileReaderCompactBinary : public SampleProfileReaderBinary {
+private:
+  /// Function name table.
+  std::vector<std::string> NameTable;
+  virtual std::error_code verifySPMagic(uint64_t Magic) override;
+  virtual std::error_code readNameTable() override;
+  /// Read a string indirectly via the name table.
+  virtual ErrorOr<StringRef> readStringFromTable() override;
+
+public:
+  SampleProfileReaderCompactBinary(std::unique_ptr<MemoryBuffer> B,
+                                   LLVMContext &C)
+      : SampleProfileReaderBinary(std::move(B), C, SPF_Compact_Binary) {}
+
+  /// \brief Return true if \p Buffer is in the format supported by this class.
+  static bool hasFormat(const MemoryBuffer &Buffer);
 };
 
 using InlineCallStack = SmallVector<FunctionSamples *, 10>;
 
 // Supported histogram types in GCC.  Currently, we only need support for
 // call target histograms.
 enum HistType {
   HIST_TYPE_INTERVAL,
   HIST_TYPE_POW2,
   HIST_TYPE_SINGLE_VALUE,
   HIST_TYPE_CONST_DELTA,
   HIST_TYPE_INDIR_CALL,
   HIST_TYPE_AVERAGE,
   HIST_TYPE_IOR,
   HIST_TYPE_INDIR_CALL_TOPN
 };
 
 class SampleProfileReaderGCC : public SampleProfileReader {
 public:
   SampleProfileReaderGCC(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
-      : SampleProfileReader(std::move(B), C), GcovBuffer(Buffer.get()) {}
+      : SampleProfileReader(std::move(B), C, SPF_GCC),
+        GcovBuffer(Buffer.get()) {}
 
   /// Read and validate the file header.
   std::error_code readHeader() override;
 
   /// Read sample profiles from the associated file.
   std::error_code read() override;
 
   /// Return true if \p Buffer is in the format supported by this class.

include/llvm/ProfileData/SampleProfWriter.h

 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/ProfileSummary.h"
 #include "llvm/ProfileData/SampleProf.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cstdint>
 #include <memory>
+#include <set>
 #include <system_error>
 
 namespace llvm {
 namespace sampleprof {
 
-enum SampleProfileFormat { SPF_None = 0, SPF_Text, SPF_Binary, SPF_GCC };
-
 /// Sample-based profile writer. Base class.
 class SampleProfileWriter {
 public:
   virtual ~SampleProfileWriter() = default;
 
   /// Write sample profiles in \p S.
   ///
   /// \returns status code of the file update operation.
private:
   SampleProfileWriter::create(std::unique_ptr<raw_ostream> &OS,
                               SampleProfileFormat Format);
 };
 
 /// Sample-based profile writer (binary format).
 class SampleProfileWriterBinary : public SampleProfileWriter {
 public:
   std::error_code write(const FunctionSamples &S) override;
-
-protected:
   SampleProfileWriterBinary(std::unique_ptr<raw_ostream> &OS)
       : SampleProfileWriter(OS) {}
 
-  std::error_code
-  writeHeader(const StringMap<FunctionSamples> &ProfileMap) override;
+protected:
+  virtual std::error_code writeNameTable() = 0;
+  virtual std::error_code writeMagicIdent() = 0;
+  std::error_code writeHeader(const StringMap<FunctionSamples> &ProfileMap);
   std::error_code writeSummary();
   std::error_code writeNameIdx(StringRef FName);
   std::error_code writeBody(const FunctionSamples &S);
+  inline void stablizeNameTable(std::set<StringRef> &V);
+
+  MapVector<StringRef, uint32_t> NameTable;
 
 private:
   void addName(StringRef FName);
   void addNames(const FunctionSamples &S);
 
-  MapVector<StringRef, uint32_t> NameTable;
-
   friend ErrorOr<std::unique_ptr<SampleProfileWriter>>
   SampleProfileWriter::create(std::unique_ptr<raw_ostream> &OS,
                               SampleProfileFormat Format);
 };
 
+class SampleProfileWriterRawBinary : public SampleProfileWriterBinary {
+  using SampleProfileWriterBinary::SampleProfileWriterBinary;
+
+protected:
+  virtual std::error_code writeNameTable() override;
+  virtual std::error_code writeMagicIdent() override;
+};
+
+class SampleProfileWriterCompactBinary : public SampleProfileWriterBinary {
+  using SampleProfileWriterBinary::SampleProfileWriterBinary;
+
+protected:
+  virtual std::error_code writeNameTable() override;
+  virtual std::error_code writeMagicIdent() override;
+};
+
 } // end namespace sampleprof
 } // end namespace llvm
 
 #endif // LLVM_PROFILEDATA_SAMPLEPROFWRITER_H

lib/ProfileData/SampleProfReader.cpp

if (Data + Str.size() + 1 > End) {
     reportError(0, EC.message());
     return EC;
   }
 
   Data += Str.size() + 1;
   return Str;
 }
 
-ErrorOr<StringRef> SampleProfileReaderBinary::readStringFromTable() {
+template <typename T>
+inline ErrorOr<uint32_t> SampleProfileReaderBinary::readStringIndex(T &Table) {
   std::error_code EC;
   auto Idx = readNumber<uint32_t>();
   if (std::error_code EC = Idx.getError())
     return EC;
-  if (*Idx >= NameTable.size())
+  if (*Idx >= Table.size())
     return sampleprof_error::truncated_name_table;
+  return *Idx;
+}
+
+ErrorOr<StringRef> SampleProfileReaderRawBinary::readStringFromTable() {
+  auto Idx = readStringIndex(NameTable);
+  if (std::error_code EC = Idx.getError())
+    return EC;
+
   return NameTable[*Idx];
 }
 
+ErrorOr<StringRef> SampleProfileReaderCompactBinary::readStringFromTable() {
+  auto Idx = readStringIndex(NameTable);
+  if (std::error_code EC = Idx.getError())
+    return EC;
+
+  return StringRef(NameTable[*Idx]);
+}
+
 std::error_code
 SampleProfileReaderBinary::readProfile(FunctionSamples &FProfile) {
   auto NumSamples = readNumber<uint64_t>();
   if (std::error_code EC = NumSamples.getError())
     return EC;
   FProfile.addTotalSamples(*NumSamples);
 
   // Read the samples in the body.
while (!at_eof()) {
 
     if (std::error_code EC = readProfile(FProfile))
       return EC;
   }
 
   return sampleprof_error::success;
 }
 
+std::error_code SampleProfileReaderRawBinary::verifySPMagic(uint64_t Magic) {
+  if (Magic == SPMagic())
+    return sampleprof_error::success;
+  return sampleprof_error::bad_magic;
+}
+
+std::error_code
+SampleProfileReaderCompactBinary::verifySPMagic(uint64_t Magic) {
+  if (Magic == SPMagic(SPF_Compact_Binary))
+    return sampleprof_error::success;
+  return sampleprof_error::bad_magic;
+}
+
+std::error_code SampleProfileReaderRawBinary::readNameTable() {
+  auto Size = readNumber<uint32_t>();
+  if (std::error_code EC = Size.getError())
+    return EC;
+  NameTable.reserve(*Size);
+  for (uint32_t I = 0; I < *Size; ++I) {
+    auto Name(readString());
+    if (std::error_code EC = Name.getError())
+      return EC;
+    NameTable.push_back(*Name);
+  }
+
+  return sampleprof_error::success;
+}
+
+std::error_code SampleProfileReaderCompactBinary::readNameTable() {
+  auto Size = readNumber<uint64_t>();
+  if (std::error_code EC = Size.getError())
+    return EC;
+  NameTable.reserve(*Size);
+  for (uint32_t I = 0; I < *Size; ++I) {
+    auto FID = readNumber<uint64_t>();
+    if (std::error_code EC = FID.getError())
+      return EC;
+    NameTable.push_back(std::to_string(*FID));
+  }
+  return sampleprof_error::success;
+}
+
 std::error_code SampleProfileReaderBinary::readHeader() {
   Data = reinterpret_cast<const uint8_t *>(Buffer->getBufferStart());
   End = Data + Buffer->getBufferSize();
 
   // Read and check the magic identifier.
   auto Magic = readNumber<uint64_t>();
   if (std::error_code EC = Magic.getError())
     return EC;
-  else if (*Magic != SPMagic())
+  else if (std::error_code EC = verifySPMagic(*Magic))
     return sampleprof_error::bad_magic;
 
   // Read the version number.
   auto Version = readNumber<uint64_t>();
   if (std::error_code EC = Version.getError())
     return EC;
   else if (*Version != SPVersion())
     return sampleprof_error::unsupported_version;
 
   if (std::error_code EC = readSummary())
     return EC;
 
-  // Read the name table.
-  auto Size = readNumber<uint32_t>();
-  if (std::error_code EC = Size.getError())
-    return EC;
-  NameTable.reserve(*Size);
-  for (uint32_t I = 0; I < *Size; ++I) {
-    auto Name(readString());
-    if (std::error_code EC = Name.getError())
-      return EC;
-    NameTable.push_back(*Name);
-  }
-
+  if (std::error_code EC = readNameTable())
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileReaderBinary::readSummaryEntry(
     std::vector<ProfileSummaryEntry> &Entries) {
   auto Cutoff = readNumber<uint64_t>();
   if (std::error_code EC = Cutoff.getError())
     return EC;
std::error_code SampleProfileReaderBinary::readSummary() {
   }
   Summary = llvm::make_unique<ProfileSummary>(
       ProfileSummary::PSK_Sample, Entries, *TotalCount, *MaxBlockCount, 0,
       *MaxFunctionCount, *NumBlocks, *NumFunctions);
 
   return sampleprof_error::success;
 }
 
-bool SampleProfileReaderBinary::hasFormat(const MemoryBuffer &Buffer) {
+bool SampleProfileReaderRawBinary::hasFormat(const MemoryBuffer &Buffer) {
   const uint8_t *Data =
       reinterpret_cast<const uint8_t *>(Buffer.getBufferStart());
   uint64_t Magic = decodeULEB128(Data);
   return Magic == SPMagic();
 }
 
+bool SampleProfileReaderCompactBinary::hasFormat(const MemoryBuffer &Buffer) {
+  const uint8_t *Data =
+      reinterpret_cast<const uint8_t *>(Buffer.getBufferStart());
+  uint64_t Magic = decodeULEB128(Data);
+  return Magic == SPMagic(SPF_Compact_Binary);
+}
+
 std::error_code SampleProfileReaderGCC::skipNextWord() {
   uint32_t dummy;
   if (!GcovBuffer.readInt(dummy))
     return sampleprof_error::truncated;
   return sampleprof_error::success;
 }
 
 template <typename T> ErrorOr<T> SampleProfileReaderGCC::readNumber() {

 /// \param B The memory buffer to create the reader from (assumes ownership).
 ///
 /// \param C The LLVM context to use to emit diagnostics.
 ///
 /// \returns an error code indicating the status of the created reader.
 ErrorOr<std::unique_ptr<SampleProfileReader>>
 SampleProfileReader::create(std::unique_ptr<MemoryBuffer> &B, LLVMContext &C) {
   std::unique_ptr<SampleProfileReader> Reader;
-  if (SampleProfileReaderBinary::hasFormat(*B))
-    Reader.reset(new SampleProfileReaderBinary(std::move(B), C));
+  if (SampleProfileReaderRawBinary::hasFormat(*B))
+    Reader.reset(new SampleProfileReaderRawBinary(std::move(B), C));
+  else if (SampleProfileReaderCompactBinary::hasFormat(*B))
+    Reader.reset(new SampleProfileReaderCompactBinary(std::move(B), C));
   else if (SampleProfileReaderGCC::hasFormat(*B))
     Reader.reset(new SampleProfileReaderGCC(std::move(B), C));
   else if (SampleProfileReaderText::hasFormat(*B))
     Reader.reset(new SampleProfileReaderText(std::move(B), C));
   else
     return sampleprof_error::unrecognized_format;
 
   if (std::error_code EC = Reader->readHeader())

lib/ProfileData/SampleProfWriter.cpp

 
 #include "llvm/ProfileData/SampleProfWriter.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ProfileData/ProfileCommon.h"
 #include "llvm/ProfileData/SampleProf.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/LEB128.h"
+#include "llvm/Support/MD5.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cstdint>
 #include <memory>
 #include <set>
 #include <system_error>
 #include <utility>
 #include <vector>
void SampleProfileWriterBinary::addNames(const FunctionSamples &S) {
   for (const auto &J : S.getCallsiteSamples())
     for (const auto &FS : J.second) {
       const FunctionSamples &CalleeSamples = FS.second;
       addName(CalleeSamples.getName());
       addNames(CalleeSamples);
     }
 }
 
-std::error_code SampleProfileWriterBinary::writeHeader(
-    const StringMap<FunctionSamples> &ProfileMap) {
+void SampleProfileWriterBinary::stablizeNameTable(std::set<StringRef> &V) {
+  // Sort the names to make NameTable deterministic.
+  for (const auto &I : NameTable)
+    V.insert(I.first);
+  int i = 0;
+  for (const StringRef &N : V)
+    NameTable[N] = i++;
+}
+
+std::error_code SampleProfileWriterRawBinary::writeNameTable() {
   auto &OS = *OutputStream;
+  std::set<StringRef> V;
+  stablizeNameTable(V);
+
+  // Write out the name table.
+  encodeULEB128(NameTable.size(), OS);
+  for (auto N : V) {
+    OS << N;
+    encodeULEB128(0, OS);
+  }
+  return sampleprof_error::success;
+}
+
+std::error_code SampleProfileWriterCompactBinary::writeNameTable() {
+  auto &OS = *OutputStream;
+  std::set<StringRef> V;
+  stablizeNameTable(V);
+
+  // Write out the name table.
+  encodeULEB128(NameTable.size(), OS);
+  for (auto N : V) {
+    encodeULEB128(MD5Hash(N), OS);
+  }
+  return sampleprof_error::success;
+}
 
+std::error_code SampleProfileWriterRawBinary::writeMagicIdent() {
+  auto &OS = *OutputStream;
   // Write file magic identifier.
   encodeULEB128(SPMagic(), OS);
   encodeULEB128(SPVersion(), OS);
+  return sampleprof_error::success;
+}
+
+std::error_code SampleProfileWriterCompactBinary::writeMagicIdent() {
+  auto &OS = *OutputStream;
+  // Write file magic identifier.
+  encodeULEB128(SPMagic(SPF_Compact_Binary), OS);
+  encodeULEB128(SPVersion(), OS);
+  return sampleprof_error::success;
+}
+
+std::error_code SampleProfileWriterBinary::writeHeader(
+    const StringMap<FunctionSamples> &ProfileMap) {
+  writeMagicIdent();
 
   computeSummary(ProfileMap);
   if (auto EC = writeSummary())
     return EC;
 
   // Generate the name table for all the functions referenced in the profile.
   for (const auto &I : ProfileMap) {
     addName(I.first());
     addNames(I.second);
   }
 
-  // Sort the names to make NameTable is deterministic.
-  std::set<StringRef> V;
-  for (const auto &I : NameTable)
-    V.insert(I.first);
-  int i = 0;
-  for (const StringRef &N : V)
-    NameTable[N] = i++;
-
-  // Write out the name table.
-  encodeULEB128(NameTable.size(), OS);
-  for (auto N : V) {
-    OS << N;
-    encodeULEB128(0, OS);
-  }
+  writeNameTable();
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileWriterBinary::writeSummary() {
   auto &OS = *OutputStream;
   encodeULEB128(Summary->getTotalCount(), OS);
   encodeULEB128(Summary->getMaxCount(), OS);
   encodeULEB128(Summary->getMaxFunctionCount(), OS);

 ///
 /// \param Format Encoding format for the profile file.
 ///
 /// \returns an error code indicating the status of the created writer.
 ErrorOr<std::unique_ptr<SampleProfileWriter>>
 SampleProfileWriter::create(StringRef Filename, SampleProfileFormat Format) {
   std::error_code EC;
   std::unique_ptr<raw_ostream> OS;
-  if (Format == SPF_Binary)
+  if (Format == SPF_Raw_Binary || Format == SPF_Compact_Binary)
     OS.reset(new raw_fd_ostream(Filename, EC, sys::fs::F_None));
   else
     OS.reset(new raw_fd_ostream(Filename, EC, sys::fs::F_Text));
   if (EC)
     return EC;
 
   return create(OS, Format);
 }
 
 /// Create a sample profile stream writer based on the specified format.
 ///
 /// \param OS The output stream to store the profile data to.
 ///
 /// \param Format Encoding format for the profile file.
 ///
 /// \returns an error code indicating the status of the created writer.
 ErrorOr<std::unique_ptr<SampleProfileWriter>>
 SampleProfileWriter::create(std::unique_ptr<raw_ostream> &OS,
                             SampleProfileFormat Format) {
   std::error_code EC;
   std::unique_ptr<SampleProfileWriter> Writer;
 
-  if (Format == SPF_Binary)
-    Writer.reset(new SampleProfileWriterBinary(OS));
+  if (Format == SPF_Raw_Binary)
+    Writer.reset(new SampleProfileWriterRawBinary(OS));
+  else if (Format == SPF_Compact_Binary)
+    Writer.reset(new SampleProfileWriterCompactBinary(OS));
   else if (Format == SPF_Text)
     Writer.reset(new SampleProfileWriterText(OS));
   else if (Format == SPF_GCC)
     EC = sampleprof_error::unsupported_writing_format;
   else
     EC = sampleprof_error::unrecognized_format;
 
   if (EC)

lib/Transforms/IPO/SampleProfile.cpp

SampleProfileLoader::findCalleeFunctionSamples(const Instruction &Inst) const {
   if (const CallInst *CI = dyn_cast<CallInst>(&Inst))
     if (Function *Callee = CI->getCalledFunction())
       CalleeName = Callee->getName();
 
   const FunctionSamples *FS = findFunctionSamples(Inst);
   if (FS == nullptr)
     return nullptr;
 
+  std::string CalleeGUID;
+  CalleeName = getRepInFormat(CalleeName, Reader->getFormat(), CalleeGUID);
   return FS->findFunctionSamplesAt(LineLocation(FunctionSamples::getOffset(DIL),
                                                 DIL->getBaseDiscriminator()),
                                    CalleeName);
 }
 
 /// Returns a vector of FunctionSamples that are the indirect call targets
 /// of \p Inst. The vector is sorted by the total number of samples. Stores
 /// the total call count of the indirect call in \p Sum.

 /// \param InlinedGUIDs a set to be updated to include all GUIDs that are
 ///     inlined in the profiled binary.
 ///
 /// \returns True if there is any inline happened.
 bool SampleProfileLoader::inlineHotFunctions(
     Function &F, DenseSet<GlobalValue::GUID> &InlinedGUIDs) {
   DenseSet<Instruction *> PromotedInsns;
   bool Changed = false;
+  bool isCompact = (Reader->getFormat() == SPF_Compact_Binary);
   while (true) {
     bool LocalChanged = false;
     SmallVector<Instruction *, 10> CIS;
     for (auto &BB : F) {
       bool Hot = false;
       SmallVector<Instruction *, 10> Candidates;
       for (auto &I : BB.getInstList()) {
         const FunctionSamples *FS = nullptr;
for (auto I : CIS) {
         continue;
       if (CallSite(I).isIndirectCall()) {
         if (PromotedInsns.count(I))
           continue;
         uint64_t Sum;
         for (const auto *FS : findIndirectCallFunctionSamples(*I, Sum)) {
           if (IsThinLTOPreLink) {
             FS->findInlinedFunctions(InlinedGUIDs, F.getParent(),
-                                     PSI->getOrCompHotCountThreshold());
+                                     PSI->getOrCompHotCountThreshold(),
+                                     isCompact);
             continue;
           }
           auto CalleeFunctionName = FS->getName();
           // If it is a recursive call, we do not inline it as it could bloat
           // the code exponentially. There is way to better handle this, e.g.
           // clone the caller first, and inline the cloned caller if it is
           // recursive. As llvm does not inline recursive calls, we will
           // simply ignore it instead of handling it explicitly.
-          if (CalleeFunctionName == F.getName())
+          std::string FGUID;
+          auto Fname = getRepInFormat(F.getName(), Reader->getFormat(), FGUID);
+          if (CalleeFunctionName == Fname)
             continue;
 
           const char *Reason = "Callee function not available";
           auto R = SymbolMap.find(CalleeFunctionName);
           if (R != SymbolMap.end() && R->getValue() &&
               !R->getValue()->isDeclaration() &&
               R->getValue()->getSubprogram() &&
               isLegalToPromote(CallSite(I), R->getValue(), &Reason)) {
for (auto I : CIS) {
           }
         }
       } else if (CalledFunction && CalledFunction->getSubprogram() &&
                  !CalledFunction->isDeclaration()) {
         if (inlineCallInstruction(I))
           LocalChanged = true;
       } else if (IsThinLTOPreLink) {
         findCalleeFunctionSamples(*I)->findInlinedFunctions(
-            InlinedGUIDs, F.getParent(), PSI->getOrCompHotCountThreshold());
+            InlinedGUIDs, F.getParent(), PSI->getOrCompHotCountThreshold(),
+            isCompact);
       }
     }
     if (LocalChanged) {
       Changed = true;
     } else {
       break;
     }
   }

test/Transforms/SampleProfile/compact-binary-profile.ll

+; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/inline.prof -S | FileCheck %s
+; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/inline.prof -S | FileCheck %s
+; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/inline.compactbinary.afdo -S | FileCheck %s
+; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/inline.compactbinary.afdo -S | FileCheck %s
+
+; Original C++ test case
+;
+; #include <stdio.h>
+;
+; int sum(int x, int y) {
+;   return x + y;
+; }
+;
+; int main() {
+;   int s, i = 0;
+;   while (i++ < 20000 * 20000)
+;     if (i != 100) s = sum(i, s); else s = 30;
+;   printf("sum is %d\n", s);
+;   return 0;
+; }
+;
+@.str = private unnamed_addr constant [11 x i8] c"sum is %d\0A\00", align 1
+
+; Check sample-profile phase using compactbinary format profile will annotate
+; the IR with exactly the same result as using text format.
+; CHECK: br i1 %cmp, label %while.body, label %while.end{{.*}} !prof ![[IDX1:[0-9]*]]
+; CHECK: br i1 %cmp1, label %if.then, label %if.else{{.*}} !prof ![[IDX2:[0-9]*]]
+; CHECK: call i32 (i8*, ...) @printf{{.*}} !prof ![[IDX3:[0-9]*]]
+; CHECK: = !{!"TotalCount", i64 10944}
+; CHECK: = !{!"MaxCount", i64 5553}
+; CHECK: ![[IDX1]] = !{!"branch_weights", i32 5392, i32 163}
+; CHECK: ![[IDX2]] = !{!"branch_weights", i32 5280, i32 113}
+; CHECK: ![[IDX3]] = !{!"branch_weights", i32 1}
+
+; Function Attrs: nounwind uwtable
+define i32 @_Z3sumii(i32 %x, i32 %y) !dbg !4 {
+entry:
+  %x.addr = alloca i32, align 4
+  %y.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  store i32 %y, i32* %y.addr, align 4
+  %0 = load i32, i32* %x.addr, align 4, !dbg !11
+  %1 = load i32, i32* %y.addr, align 4, !dbg !11
+  %add = add nsw i32 %0, %1, !dbg !11
+  ret i32 %add, !dbg !11
+}
+
+; Function Attrs: uwtable
+define i32 @main() !dbg !7 {
+entry:
+  %retval = alloca i32, align 4
+  %s = alloca i32, align 4
+  %i = alloca i32, align 4
+  store i32 0, i32* %retval
+  store i32 0, i32* %i, align 4, !dbg !12
+  br label %while.cond, !dbg !13
+
+while.cond:                                       ; preds = %if.end, %entry
+  %0 = load i32, i32* %i, align 4, !dbg !14
+  %inc = add nsw i32 %0, 1, !dbg !14
+  store i32 %inc, i32* %i, align 4, !dbg !14
+  %cmp = icmp slt i32 %0, 400000000, !dbg !14
+  br i1 %cmp, label %while.body, label %while.end, !dbg !14
+
+while.body:                                       ; preds = %while.cond
+  %1 = load i32, i32* %i, align 4, !dbg !16
+  %cmp1 = icmp ne i32 %1, 100, !dbg !16
+  br i1 %cmp1, label %if.then, label %if.else, !dbg !16
+
+
+if.then:                                          ; preds = %while.body
+  %2 = load i32, i32* %i, align 4, !dbg !18
+  %3 = load i32, i32* %s, align 4, !dbg !18
+  %call = call i32 @_Z3sumii(i32 %2, i32 %3), !dbg !18
+  store i32 %call, i32* %s, align 4, !dbg !18
+  br label %if.end, !dbg !18
+
+if.else:                                          ; preds = %while.body
+  store i32 30, i32* %s, align 4, !dbg !20
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  br label %while.cond, !dbg !22
+
+while.end:                                        ; preds = %while.cond
+  %4 = load i32, i32* %s, align 4, !dbg !24
+  %call2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([11 x i8], [11 x i8]* @.str, i32 0, i32 0), i32 %4), !dbg !24
+  ret i32 0, !dbg !25
+}
+
+declare i32 @printf(i8*, ...) #2
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!8, !9}
+!llvm.ident = !{!10}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, producer: "clang version 3.5 ", isOptimized: false, emissionKind: NoDebug, file: !1, enums: !2, retainedTypes: !2, globals: !2, imports: !2)
+!1 = !DIFile(filename: "calls.cc", directory: ".")
+!2 = !{}
+!4 = distinct !DISubprogram(name: "sum", line: 3, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, unit: !0, scopeLine: 3, file: !1, scope: !5, type: !6, retainedNodes: !2)
+!5 = !DIFile(filename: "calls.cc", directory: ".")
+!6 = !DISubroutineType(types: !2)
+!7 = distinct !DISubprogram(name: "main", line: 7, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, unit: !0, scopeLine: 7, file: !1, scope: !5, type: !6, retainedNodes: !2)
+!8 = !{i32 2, !"Dwarf Version", i32 4}
+!9 = !{i32 1, !"Debug Info Version", i32 3}
+!10 = !{!"clang version 3.5 "}
+!11 = !DILocation(line: 4, scope: !4)
+!12 = !DILocation(line: 8, scope: !7)
+!13 = !DILocation(line: 9, scope: !7)
+!14 = !DILocation(line: 9, scope: !15)
+!15 = !DILexicalBlockFile(discriminator: 2, file: !1, scope: !7)
+!16 = !DILocation(line: 10, scope: !17)
+!17 = distinct !DILexicalBlock(line: 10, column: 0, file: !1, scope: !7)
+!18 = !DILocation(line: 10, scope: !19)
+!19 = !DILexicalBlockFile(discriminator: 2, file: !1, scope: !17)
+!20 = !DILocation(line: 10, scope: !21)
+!21 = !DILexicalBlockFile(discriminator: 4, file: !1, scope: !17)
+!22 = !DILocation(line: 10, scope: !23)
+!23 = !DILexicalBlockFile(discriminator: 6, file: !1, scope: !17)
+!24 = !DILocation(line: 11, scope: !7)
+!25 = !DILocation(line: 12, scope: !7)

tools/llvm-profdata/llvm-profdata.cpp

 #include "llvm/Support/Path.h"
 #include "llvm/Support/WithColor.h"
 #include "llvm/Support/ThreadPool.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 
 using namespace llvm;
 
-enum ProfileFormat { PF_None = 0, PF_Text, PF_Binary, PF_GCC };
+enum ProfileFormat {
+  PF_None = 0,
+  PF_Text,
+  PF_Compact_Binary,
+  PF_GCC,
+  PF_Raw_Binary
+};
 
 static void warn(Twine Message, std::string Whence = "",
                  std::string Hint = "") {
   WithColor::warning();
   if (!Whence.empty())
     errs() << Whence << ": ";
   errs() << Message << "\n";
   if (!Hint.empty())

 
 static void mergeInstrProfile(const WeightedFileVector &Inputs,
                               StringRef OutputFilename,
                               ProfileFormat OutputFormat, bool OutputSparse,
                               unsigned NumThreads) {
   if (OutputFilename.compare("-") == 0)
     exitWithError("Cannot write indexed profdata format to stdout.");
 
-  if (OutputFormat != PF_Binary && OutputFormat != PF_Text)
+  if (OutputFormat != PF_Raw_Binary && OutputFormat != PF_Compact_Binary &&
+      OutputFormat != PF_Text)
     exitWithError("Unknown format is specified.");
 
   std::error_code EC;
   raw_fd_ostream Output(OutputFilename.data(), EC, sys::fs::F_None);
   if (EC)
     exitWithErrorCode(EC, OutputFilename);
 
   std::mutex ErrorLock;
if (OutputFormat == PF_Text) {
     if (Error E = Writer.writeText(Output))
       exitWithError(std::move(E));
   } else {
     Writer.write(Output);
   }
 }
 
 static sampleprof::SampleProfileFormat FormatMap[] = {
-    sampleprof::SPF_None, sampleprof::SPF_Text, sampleprof::SPF_Binary,
-    sampleprof::SPF_GCC};
+    sampleprof::SPF_None, sampleprof::SPF_Text, sampleprof::SPF_Compact_Binary,
+    sampleprof::SPF_GCC, sampleprof::SPF_Raw_Binary};
 
 static void mergeSampleProfile(const WeightedFileVector &Inputs,
                                StringRef OutputFilename,
                                ProfileFormat OutputFormat) {
   using namespace sampleprof;
   auto WriterOrErr =
       SampleProfileWriter::create(OutputFilename, FormatMap[OutputFormat]);
   if (std::error_code EC = WriterOrErr.getError())
cl::opt<std::string> OutputFilename("output", cl::value_desc("output"),
                                       cl::desc("Output file"));
   cl::alias OutputFilenameA("o", cl::desc("Alias for --output"),
                             cl::aliasopt(OutputFilename));
   cl::opt<ProfileKinds> ProfileKind(
       cl::desc("Profile kind:"), cl::init(instr),
       cl::values(clEnumVal(instr, "Instrumentation profile (default)"),
                  clEnumVal(sample, "Sample profile")));
   cl::opt<ProfileFormat> OutputFormat(
-      cl::desc("Format of output profile"), cl::init(PF_Binary),
-      cl::values(clEnumValN(PF_Binary, "binary", "Binary encoding (default)"),
-                 clEnumValN(PF_Text, "text", "Text encoding"),
-                 clEnumValN(PF_GCC, "gcc",
-                            "GCC encoding (only meaningful for -sample)")));
+      cl::desc("Format of output profile"), cl::init(PF_Raw_Binary),
+      cl::values(
+          clEnumValN(PF_Raw_Binary, "binary", "Binary encoding (default)"),
+          clEnumValN(PF_Compact_Binary, "compbinary",
+                     "Compact binary encoding (default)"),
   cl::opt<bool> OutputSparse("sparse", cl::init(false),
       cl::desc("Generate a sparse profile (only meaningful for -instr)"));
   cl::opt<unsigned> NumThreads(
       "num-threads", cl::init(0),
       cl::desc("Number of merge threads to use (default: autodetect)"));
   cl::alias NumThreadsA("j", cl::desc("Alias for --num-threads"),
                         cl::aliasopt(NumThreads));
 

unittests/ProfileData/SampleProfTest.cpp

void testRoundTrip(SampleProfileFormat Format) {
     FooSamples.addBodySamples(10, 0, 605);
 
     StringRef BarName("_Z3bari");
     FunctionSamples BarSamples;
     BarSamples.setName(BarName);
     BarSamples.addTotalSamples(20301);
     BarSamples.addHeadSamples(1437);
     BarSamples.addBodySamples(1, 0, 1437);
-    BarSamples.addCalledTargetSamples(1, 0, "_M_construct<char *>", 1000);
-    BarSamples.addCalledTargetSamples(
-        1, 0, "string_view<std::allocator<char> >", 437);
+    // Test how reader/writer handles unmangled names.
+    StringRef MconstructName("_M_construct<char *>");
+    StringRef StringviewName("string_view<std::allocator<char> >");
+    BarSamples.addCalledTargetSamples(1, 0, MconstructName, 1000);
+    BarSamples.addCalledTargetSamples(1, 0, StringviewName, 437);
 
     StringMap<FunctionSamples> Profiles;
     Profiles[FooName] = std::move(FooSamples);
     Profiles[BarName] = std::move(BarSamples);
 
     std::error_code EC;
     EC = Writer->write(Profiles);
     ASSERT_TRUE(NoError(EC));
 
     Writer->getOutputStream().flush();
 
     auto Profile = MemoryBuffer::getMemBufferCopy(Data);
     readProfile(Profile);
 
     EC = Reader->read();
     ASSERT_TRUE(NoError(EC));
 
     StringMap<FunctionSamples> &ReadProfiles = Reader->getProfiles();
     ASSERT_EQ(2u, ReadProfiles.size());
 
-    FunctionSamples &ReadFooSamples = ReadProfiles[FooName];
+    std::string FooGUID;
+    StringRef FooRep = getRepInFormat(FooName, Format, FooGUID);
+    FunctionSamples &ReadFooSamples = ReadProfiles[FooRep];
     ASSERT_EQ(7711u, ReadFooSamples.getTotalSamples());
     ASSERT_EQ(610u, ReadFooSamples.getHeadSamples());
 
-    FunctionSamples &ReadBarSamples = ReadProfiles[BarName];
+    std::string BarGUID;
+    StringRef BarRep = getRepInFormat(BarName, Format, BarGUID);
+    FunctionSamples &ReadBarSamples = ReadProfiles[BarRep];
     ASSERT_EQ(20301u, ReadBarSamples.getTotalSamples());
     ASSERT_EQ(1437u, ReadBarSamples.getHeadSamples());
     ErrorOr<SampleRecord::CallTargetMap> CTMap =
         ReadBarSamples.findCallTargetMapAt(1, 0);
     ASSERT_FALSE(CTMap.getError());
-    ASSERT_EQ(1000u, CTMap.get()["_M_construct<char *>"]);
-    ASSERT_EQ(437u, CTMap.get()["string_view<std::allocator<char> >"]);
+
+    std::string MconstructGUID;
+    StringRef MconstructRep =
+        getRepInFormat(MconstructName, Format, MconstructGUID);
+    std::string StringviewGUID;
+    StringRef StringviewRep =
+        getRepInFormat(StringviewName, Format, StringviewGUID);
+    ASSERT_EQ(1000u, CTMap.get()[MconstructRep]);
+    ASSERT_EQ(437u, CTMap.get()[StringviewRep]);
 
     auto VerifySummary = [](ProfileSummary &Summary) mutable {
       ASSERT_EQ(ProfileSummary::PSK_Sample, Summary.getKind());
       ASSERT_EQ(123603u, Summary.getTotalCount());
       ASSERT_EQ(6u, Summary.getNumCounts());
       ASSERT_EQ(2u, Summary.getNumFunctions());
       ASSERT_EQ(1437u, Summary.getMaxFunctionCount());
       ASSERT_EQ(60351u, Summary.getMaxCount());
void testRoundTrip(SampleProfileFormat Format) {
     delete PS;
   }
 };
 
 TEST_F(SampleProfTest, roundtrip_text_profile) {
   testRoundTrip(SampleProfileFormat::SPF_Text);
 }
 
-TEST_F(SampleProfTest, roundtrip_binary_profile) {
-  testRoundTrip(SampleProfileFormat::SPF_Binary);
+TEST_F(SampleProfTest, roundtrip_raw_binary_profile) {
+  testRoundTrip(SampleProfileFormat::SPF_Raw_Binary);
+}
+
+TEST_F(SampleProfTest, roundtrip_compact_binary_profile) {
+  testRoundTrip(SampleProfileFormat::SPF_Compact_Binary);
 }
 
 TEST_F(SampleProfTest, sample_overflow_saturation) {
   const uint64_t Max = std::numeric_limits<uint64_t>::max();
   sampleprof_error Result;
 
   StringRef FooName("_Z3fooi");
   FunctionSamples FooSamples;