[memprof] Extend the index prof format to include memory profiles.

[snehasish]

Summary

This patch adds support for optional memory profile information to be
included with and indexed profile. The indexed profile header adds a new
field which points to the offset of the memory profile section (if
present) in the indexed profile. For users who do not utilize this
feature the only overhead is a 64-bit offset in the header.

The memory profile section contains (1) profile metadata describing the
information recorded for each entry (2) an on-disk hashtable containing
the profile records indexed via llvm::md5(function_name). We chose to
introduce a separate hash table instead of the existing one since the
indexing for the instrumented fdo hash table is based on a CFG hash
which itself is perturbed by memprof instrumentation.

[snehasish]

Rebase and fix error handling in llvm-profdata.

[snehasish]

Found an issue with llvm-profdata merge. I'll update the patch with the fix and more tests.

[snehasish]

Changes:

• Removed summary for memprof for now. We will add a custom summary later.
• Fixed issue, added llvm-profdata merge lit test.

[snehasish]

Remove some more leftover code from reverted summary changes.

[snehasish]

Add static checks to header reading code for v8.

[snehasish]

Updated the patch with a llvm-profdata test and some cleanup. PTAL, thanks!

[tejohnson]

llvm/include/llvm/ProfileData/InstrProfData.inc

665

I noticed this change and the one below are not in compiler-rt/include/profile/InstrProfData.inc, I assume these two files should be identical?

llvm/include/llvm/ProfileData/InstrProfReader.h

621

typo: recrods

llvm/include/llvm/ProfileData/MemProf.h

65

Note the return value?

143

You could just return false if they are unequal, then return true if we fall through, to avoid extra comparisons

275

expected that second parameter unused?

279

ditto - will we get unused warnings about N?

331

expected that last parameter not used (here and in EmitData)?

llvm/lib/ProfileData/InstrProfReader.cpp

1042

Maybe include the hash value in the error?

llvm/lib/ProfileData/InstrProfWriter.cpp

267

What is the intention of the code - this will overwrite Key for every non-inline frame. Should it break after Key is assigned the first time? Or do we want the last one, in which case you could walk the CallStack in reverse order and again break when Key is set for the first time.

359

"these fields"

371

s/spec/space/ ?

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

255

When would this fail?

[davidxl]

llvm/include/llvm/ProfileData/InstrProfData.inc

665

yes.

llvm/include/llvm/ProfileData/InstrProfReader.h

624

single line?

llvm/include/llvm/ProfileData/InstrProfWriter.h

44

Why not StringMap?

66

Should there be a merge interface like the addRecord for Edge profile data above?

llvm/include/llvm/ProfileData/MemProf.h

139

Document type -- MD5 Hash

llvm/test/tools/llvm-profdata/memprof-merge.test

40

Requires text format reader and writer for memprof

[tejohnson]

llvm/include/llvm/ProfileData/MemProf.h

139

Can we use GlobalValue::GUID as the type (which is uint64_t)? That's already used elsewhere in this directory (at least in the SampleProfiler). If so, then the later md5 hash computation can call the static helper Function::getGUID on the string (which is just a wrapper around MD5Hash but matches the type name).

[snehasish]

Address comments.

[snehasish]

Remove whitespace.

[snehasish]

Thanks for the detailed review. PTAL!

llvm/include/llvm/ProfileData/InstrProfReader.h

624

clang-format puts it on a separate line since the length is 85 chars.

llvm/include/llvm/ProfileData/InstrProfWriter.h

44

The memprof data is indexed via uint64_t obtained from llvm::md5(FunctionName). The instrprof data is first indexed by function name as string and then via the cfg hash thus uses a StringMap.

66

The existing mergeRecordsFromWriter function defined below has been extended to merge memprof data if necessary. See the changes in lib/ProfileData/InstrProfWriter.cpp:L287.

llvm/include/llvm/ProfileData/MemProf.h

65

I decided to rewrite this function to accept raw_ostream& OS instead of char *Ptr. This allowed me to remove a memory allocation TODO in a higher up callee. The function no longer returns a value.

139

Documented the frame and all the members.

Changed the type to GlobalValue::GUID. While I don't expect the type to change, I added a static assert in the writer to ensure that the writer and reader code does not bitrot in case it does.

275

Yes, added /*Unused*/ for everywhere this is applicable to make it clear.

279

No warnings for unused parameters AFAICT.

llvm/lib/ProfileData/InstrProfWriter.cpp

267

It is the latter. I changed the loop to iterate in reverse and break early.

llvm/test/tools/llvm-profdata/memprof-merge.test

40

We have a text format writer, it prints it to YAML right now. The reader from YAML has not been implemented yet. This comment however alludes to the lack of the iterator interface to the memprof data. That requires a little bit of code which I wanted to keep separate to minimize the size of this patch.

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

255

For now, when clang frontend profiles are merged with memprof. Updated the comment to clarify.

[tejohnson]

lgtm. Slight preference for using Function::getGUID instead of llvm::MD5Hash to obfuscate the details of what a GUID is, but ok as is if you want to be explicit.

[snehasish]

Rebase after landing D116784.
Use Function::getGUID instead of llvm::MD5 directly.

[snehasish]

Seems like a good idea to keep it consistent so I updated the code and test to use Function::getGUID. Added a comment to note that it is effectively llvm::md5. Thanks!

[snehasish]

Update PortableMemInfoBlock::deserialize to remove ub when reading unaligned 32b types.

[snehasish]

I tried this out on an internal workload. Sharing some characteristics of the new indexed profile containing IR-level instr profiling data and memprof data:

Raw file sizes (directly written out from the runtime)
Instr prof: 264M
MemProf: 215M
Instr prof zip: 80M
MemProf zip: 45M

Indexed format file sizes (after running llvm-profdata merge)
Indexed instr prof data only: 505M
Indexed instr prof data only zip: 139M
Indexed instr + memprof: 1010M
Indexed instr + memprof zip: 247M

llvm-profdata merge runtime
Indexed instr prof data only: 10s
Indexed instr + memprof data: 1m 53s

Looking into the profile using perf record -e cycles:up, I found that (unsurprisingly) a significant amount is spent in symbolization. We can significantly reduce the runtime here with caching of PC -> Frame symbolization.

llvm-profdata merge peak memory usage
Indexed instr prof data only: 1.4G
Indexed instr + memprof data: 8.16G

Looking into the profile of memory allocations using massif, I saw that it is from DwarfContext::create in the initialize method. This is a little concerning so I'll have to investigate further how we can reduce the reduce the overhead. The debug info generated for this binary is the same as what is used for Sample FDO (-gmlt and -fdebug-info-for-profiling). The debug information was stored separately using -gsplit-dwarf (fission).

I'll follow up after submitting this patch to improve upon the runtime and peak memory usage.

[davidxl]

lgtm

[snehasish]

Rebase and cleanup.

• Use 0x40 for MemProf in InstrProf.h
• Sync minor differences MemProfData.inc.

[snehasish]

Rebase after moving some PortableMemInfoBlock changes to D117256.

compiler-rt/include/profile/InstrProfData.inc

 #define INSTR_PROF_RAW_MAGIC_32 (uint64_t)255 << 56 | (uint64_t)'l' << 48 | \
        (uint64_t)'p' << 40 | (uint64_t)'r' << 32 | (uint64_t)'o' << 24 |  \
         (uint64_t)'f' << 16 | (uint64_t)'R' << 8 | (uint64_t)129
 
 /* FIXME: Please remedy the fixme in the header before bumping the version. */
 /* Raw profile format version (start from 1). */
 #define INSTR_PROF_RAW_VERSION 8
 /* Indexed profile format version (start from 1). */
-#define INSTR_PROF_INDEX_VERSION 7
+#define INSTR_PROF_INDEX_VERSION 8
 /* Coverage mapping format version (start from 0). */
 #define INSTR_PROF_COVMAP_VERSION 5
 
 /* Profile version is always of type uint64_t. Reserve the upper 8 bits in the
  * version for other variants of profile. We set the lowest bit of the upper 8
  * bits (i.e. bit 56) to 1 to indicate if this is an IR-level instrumentation
  * generated profile, and 0 if this is a Clang FE generated profile.
  * 1 in bit 57 indicates there are context-sensitive records in the profile.
  * The 59th bit indicates whether to use debug info to correlate profiles.
  * The 60th bit indicates single byte coverage instrumentation.
  * The 61st bit indicates function entry instrumentation only.
+ * The 62nd bit indicates whether memory profile information is present.
  */
 #define VARIANT_MASKS_ALL 0xff00000000000000ULL
 #define GET_VERSION(V) ((V) & ~VARIANT_MASKS_ALL)
 #define VARIANT_MASK_IR_PROF (0x1ULL << 56)
 #define VARIANT_MASK_CSIR_PROF (0x1ULL << 57)
 #define VARIANT_MASK_INSTR_ENTRY (0x1ULL << 58)
 #define VARIANT_MASK_DBG_CORRELATE (0x1ULL << 59)
 #define VARIANT_MASK_BYTE_COVERAGE (0x1ULL << 60)
 #define VARIANT_MASK_FUNCTION_ENTRY_ONLY (0x1ULL << 61)
+#define VARIANT_MASK_MEMPROF (0x1ULL << 62)
 #define INSTR_PROF_RAW_VERSION_VAR __llvm_profile_raw_version
 #define INSTR_PROF_PROFILE_RUNTIME_VAR __llvm_profile_runtime
 #define INSTR_PROF_PROFILE_COUNTER_BIAS_VAR __llvm_profile_counter_bias
 
 /* The variable that holds the name of the profile data
  * specified via command line. */
 #define INSTR_PROF_PROFILE_NAME_VAR __llvm_profile_filename
 

llvm/include/llvm/ProfileData/InstrProf.h

 enum class InstrProfKind {
   Unknown = 0x0,
   FE = 0x1, // A frontend clang profile, incompatible with other attrs.
   IR = 0x2, // An IR-level profile (default when -fprofile-generate is used).
   BB = 0x4, // A profile with entry basic block instrumentation.
   CS = 0x8, // A context sensitive IR-level profile.
   SingleByteCoverage = 0x10, // Use single byte probes for coverage.
   FunctionEntryOnly = 0x20,  // Only instrument the function entry basic block.
-  LLVM_MARK_AS_BITMASK_ENUM(/*LargestValue=*/FunctionEntryOnly)
+  MemProf = 0x40, // A memory profile collected using -fmemory-profile.
+  LLVM_MARK_AS_BITMASK_ENUM(/*LargestValue=*/MemProf)
 };
 
 const std::error_category &instrprof_category();
 
 enum class instrprof_error {
   success = 0,
   eof,
   unrecognized_format,
enum ProfVersion {
   Version4 = 4,
   // In this version, the frontend PGO stable hash algorithm defaults to V2.
   Version5 = 5,
   // In this version, the frontend PGO stable hash algorithm got fixed and
   // may produce hashes different from Version5.
   Version6 = 6,
   // An additional counter is added around logical operators.
   Version7 = 7,
-  // The current version is 7.
+  // An additional (optional) memory profile type is added.
+  Version8 = 8,
+  // The current version is 8.
   CurrentVersion = INSTR_PROF_INDEX_VERSION
 };
 const uint64_t Version = ProfVersion::CurrentVersion;
 
 const HashT HashType = HashT::MD5;
 
 inline uint64_t ComputeHash(StringRef K) { return ComputeHash(HashType, K); }
 
 // This structure defines the file header of the LLVM profile
 // data file in indexed-format.
 struct Header {
   uint64_t Magic;
   uint64_t Version;
   uint64_t Unused; // Becomes unused since version 4
   uint64_t HashType;
   uint64_t HashOffset;
+  uint64_t MemProfOffset;
   // New fields should only be added at the end to ensure that the size
   // computation is correct. The methods below need to be updated to ensure that
   // the new field is read correctly.
 
   // Reads a header struct from the buffer.
   static Expected<Header> readFromBuffer(const unsigned char *Buffer);
 
   // Returns the size of the header in bytes for all valid fields based on the

llvm/include/llvm/ProfileData/InstrProfData.inc

 #define INSTR_PROF_RAW_MAGIC_32 (uint64_t)255 << 56 | (uint64_t)'l' << 48 | \
        (uint64_t)'p' << 40 | (uint64_t)'r' << 32 | (uint64_t)'o' << 24 |  \
         (uint64_t)'f' << 16 | (uint64_t)'R' << 8 | (uint64_t)129
 
 /* FIXME: Please remedy the fixme in the header before bumping the version. */
 /* Raw profile format version (start from 1). */
 #define INSTR_PROF_RAW_VERSION 8
 /* Indexed profile format version (start from 1). */
-#define INSTR_PROF_INDEX_VERSION 7
+#define INSTR_PROF_INDEX_VERSION 8
 /* Coverage mapping format version (start from 0). */
 #define INSTR_PROF_COVMAP_VERSION 5
 
 /* Profile version is always of type uint64_t. Reserve the upper 8 bits in the
  * version for other variants of profile. We set the lowest bit of the upper 8
  * bits (i.e. bit 56) to 1 to indicate if this is an IR-level instrumentation
  * generated profile, and 0 if this is a Clang FE generated profile.
  * 1 in bit 57 indicates there are context-sensitive records in the profile.
  * The 59th bit indicates whether to use debug info to correlate profiles.
  * The 60th bit indicates single byte coverage instrumentation.
  * The 61st bit indicates function entry instrumentation only.
+ * The 62nd bit indicates whether memory profile information is present.
  */
 #define VARIANT_MASKS_ALL 0xff00000000000000ULL
 #define GET_VERSION(V) ((V) & ~VARIANT_MASKS_ALL)
 #define VARIANT_MASK_IR_PROF (0x1ULL << 56)
 #define VARIANT_MASK_CSIR_PROF (0x1ULL << 57)
 #define VARIANT_MASK_INSTR_ENTRY (0x1ULL << 58)
 #define VARIANT_MASK_DBG_CORRELATE (0x1ULL << 59)
 #define VARIANT_MASK_BYTE_COVERAGE (0x1ULL << 60)
 #define VARIANT_MASK_FUNCTION_ENTRY_ONLY (0x1ULL << 61)
+#define VARIANT_MASK_MEMPROF (0x1ULL << 62)
 #define INSTR_PROF_RAW_VERSION_VAR __llvm_profile_raw_version
 #define INSTR_PROF_PROFILE_RUNTIME_VAR __llvm_profile_runtime
 #define INSTR_PROF_PROFILE_COUNTER_BIAS_VAR __llvm_profile_counter_bias
 
 /* The variable that holds the name of the profile data
  * specified via command line. */
 #define INSTR_PROF_PROFILE_NAME_VAR __llvm_profile_filename
 

llvm/include/llvm/ProfileData/InstrProfReader.h

 #ifndef LLVM_PROFILEDATA_INSTRPROFREADER_H
 #define LLVM_PROFILEDATA_INSTRPROFREADER_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/ProfileSummary.h"
 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/ProfileData/InstrProfCorrelator.h"
+#include "llvm/ProfileData/MemProf.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/LineIterator.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/OnDiskHashTable.h"
 #include "llvm/Support/SwapByteOrder.h"
 #include <algorithm>
 #include <cassert>
struct InstrProfReaderIndexBase {
   virtual bool functionEntryOnly() const = 0;
   virtual InstrProfKind getProfileKind() const = 0;
   virtual Error populateSymtab(InstrProfSymtab &) = 0;
 };
 
 using OnDiskHashTableImplV3 =
     OnDiskIterableChainedHashTable<InstrProfLookupTrait>;
 
+using MemProfHashTable =
+    OnDiskIterableChainedHashTable<memprof::MemProfRecordLookupTrait>;
+
 template <typename HashTableImpl>
 class InstrProfReaderItaniumRemapper;
 
 template <typename HashTableImpl>
 class InstrProfReaderIndex : public InstrProfReaderIndexBase {
 private:
   std::unique_ptr<HashTableImpl> HashTable;
   typename HashTableImpl::data_iterator RecordIterator;
private:
   /// The index into the profile data.
   std::unique_ptr<InstrProfReaderIndexBase> Index;
   /// The profile remapping file contents.
   std::unique_ptr<InstrProfReaderRemapper> Remapper;
   /// Profile summary data.
   std::unique_ptr<ProfileSummary> Summary;
   /// Context sensitive profile summary data.
   std::unique_ptr<ProfileSummary> CS_Summary;
+  /// MemProf profile schema (if available).
+  memprof::MemProfSchema Schema;
+  /// MemProf profile data on-disk indexed via llvm::md5(FunctionName).
+  std::unique_ptr<MemProfHashTable> MemProfTable;
+
   // Index to the current record in the record array.
   unsigned RecordIndex;
 
   // Read the profile summary. Return a pointer pointing to one byte past the
   // end of the summary data if it exists or the input \c Cur.
   // \c UseCS indicates whether to use the context-sensitive profile summary.
   const unsigned char *readSummary(IndexedInstrProf::ProfVersion Version,
                                    const unsigned char *Cur, bool UseCS);
public:
   Error readHeader() override;
   /// Read a single record.
   Error readNextRecord(NamedInstrProfRecord &Record) override;
 
   /// Return the NamedInstrProfRecord associated with FuncName and FuncHash
   Expected<InstrProfRecord> getInstrProfRecord(StringRef FuncName,
                                                uint64_t FuncHash);
 
+  /// Return the memprof records for the function identified by
+  /// llvm::md5(Name).
+  Expected<ArrayRef<memprof::MemProfRecord>>
+  getMemProfRecord(uint64_t FuncNameHash);
+
   /// Fill Counts with the profile data for the given function name.
   Error getFunctionCounts(StringRef FuncName, uint64_t FuncHash,
                           std::vector<uint64_t> &Counts);
 
   /// Return the maximum of all known function counts.
   /// \c UseCS indicates whether to use the context-sensitive count.
   uint64_t getMaximumFunctionCount(bool UseCS) {
     if (UseCS) {

llvm/include/llvm/ProfileData/InstrProfWriter.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_PROFILEDATA_INSTRPROFWRITER_H
 #define LLVM_PROFILEDATA_INSTRPROFWRITER_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ProfileData/InstrProf.h"
+#include "llvm/ProfileData/MemProf.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include <cstdint>
 #include <memory>
 
 namespace llvm {
 
 /// Writer for instrumentation based profile data.
 class InstrProfRecordWriterTrait;
 class ProfOStream;
 class raw_fd_ostream;
 
 class InstrProfWriter {
 public:
   using ProfilingData = SmallDenseMap<uint64_t, InstrProfRecord>;
 
 private:
   bool Sparse;
   StringMap<ProfilingData> FunctionData;
+
+  // A map to hold memprof data per function. The lower 64 bits obtained from
+  // the md5 hash of the function name is used to index into the map.
+  memprof::FunctionMemProfMap MemProfData;
+
   // An enum describing the attributes of the profile.
   InstrProfKind ProfileKind = InstrProfKind::Unknown;
   // Use raw pointer here for the incomplete type object.
   InstrProfRecordWriterTrait *InfoObj;
 
 public:
   InstrProfWriter(bool Sparse = false);
   ~InstrProfWriter();
 
   StringMap<ProfilingData> &getProfileData() { return FunctionData; }
 
   /// Add function counts for the given function. If there are already counts
   /// for this function and the hash and number of counts match, each counter is
   /// summed. Optionally scale counts by \p Weight.
   void addRecord(NamedInstrProfRecord &&I, uint64_t Weight,
                  function_ref<void(Error)> Warn);
   void addRecord(NamedInstrProfRecord &&I, function_ref<void(Error)> Warn) {
     addRecord(std::move(I), 1, Warn);
   }
 
+  void addRecord(const ::llvm::memprof::MemProfRecord &MR,
+                 function_ref<void(Error)> Warn);
+
   /// Merge existing function counts from the given writer.
   void mergeRecordsFromWriter(InstrProfWriter &&IPW,
                               function_ref<void(Error)> Warn);
 
   /// Write the profile to \c OS
   Error write(raw_fd_ostream &OS);
 
   /// Write the profile in text format to \c OS
if (testIncompatible(InstrProfKind::FunctionEntryOnly, InstrProfKind::BB)) {
           "cannot merge FunctionEntryOnly profiles and BB profiles together");
     }
 
     // Now we update the profile type with the bits that are set.
     ProfileKind |= Other;
     return Error::success();
   }
 
+  InstrProfKind getProfileKind() const { return ProfileKind; }
+
   // Internal interface for testing purpose only.
   void setValueProfDataEndianness(support::endianness Endianness);
   void setOutputSparse(bool Sparse);
   // Compute the overlap b/w this object and Other. Program level result is
   // stored in Overlap and function level result is stored in FuncLevelOverlap.
   void overlapRecord(NamedInstrProfRecord &&Other, OverlapStats &Overlap,
                      OverlapStats &FuncLevelOverlap,
                      const OverlapFuncFilters &FuncFilter);

llvm/include/llvm/ProfileData/MemProf.h

 #ifndef LLVM_PROFILEDATA_MEMPROF_H_
 #define LLVM_PROFILEDATA_MEMPROF_H_
 
 #include <cstdint>
 #include <string>
 #include <vector>
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ProfileData/MemProfData.inc"
 #include "llvm/ProfileData/ProfileCommon.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/EndianStream.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace llvm {
#undef MIBEntryDef
       default:
         llvm_unreachable("Unknown meta type id, is the profile collected from "
                          "a newer version of the runtime?");
       }
     }
   }
 
   // Write the contents of the MemInfoBlock based on the \p Schema provided to
   // the raw_ostream \p OS.
   void serialize(const MemProfSchema &Schema, raw_ostream &OS) const {
     using namespace support;
 
     endian::Writer LE(OS, little);
     for (const Meta Id : Schema) {
       switch (Id) {
 #define MIBEntryDef(NameTag, Name, Type)                                       \
   case Meta::Name: {                                                           \

 
 private:
 #define MIBEntryDef(NameTag, Name, Type) Type Name = Type();
 #include "llvm/ProfileData/MIBEntryDef.inc"
 #undef MIBEntryDef
 };
 
 struct MemProfRecord {
-  struct Frame {
-    std::string Function;
+  // Describes a call frame for a dynamic allocation context. The contents of
+  // the frame are populated by symbolizing the stack depot call frame from the
+  // compiler runtime.
+  PACKED(struct Frame {
+    // A uuid (uint64_t) identifying the function. It is obtained by
+    // llvm::md5(FunctionName) which returns the lower 64 bits.
+    GlobalValue::GUID Function;
+    // The source line offset of the call from the beginning of parent function.
     uint32_t LineOffset;
+    // The source column number of the call to help distinguish multiple calls
+    // on the same line.
     uint32_t Column;
+    // Whether the current frame is inlined.
     bool IsInlineFrame;
 
-    Frame(std::string Str, uint32_t Off, uint32_t Col, bool Inline)
-        : Function(std::move(Str)), LineOffset(Off), Column(Col),
-          IsInlineFrame(Inline) {}
-  };
+    Frame(uint64_t Hash, uint32_t Off, uint32_t Col, bool Inline)
+        : Function(Hash), LineOffset(Off), Column(Col), IsInlineFrame(Inline) {}
+
+    bool operator==(const Frame &Other) const {
+      return Other.Function == Function && Other.LineOffset == LineOffset &&
+             Other.Column == Column && Other.IsInlineFrame == IsInlineFrame;
+    }
+
+    bool operator!=(const Frame &Other) const { return !operator==(Other); }
+
+    // Write the contents of the frame to the ostream \p OS.
+    void write(raw_ostream & OS) const {
+      using namespace support;
+
+      endian::Writer LE(OS, little);
+
+      // If the type of the GlobalValue::GUID changes, then we need to update
+      // the reader and the writer.
+      static_assert(std::is_same<GlobalValue::GUID, uint64_t>::value,
+                    "Expect GUID to be uint64_t.");
+      LE.write<uint64_t>(Function);
+
+      LE.write<uint32_t>(LineOffset);
+      LE.write<uint32_t>(Column);
+      LE.write<bool>(IsInlineFrame);
+    }
+  });
 
+  // The dynamic calling context for the allocation.
   std::vector<Frame> CallStack;
+  // The statistics obtained from the runtime for the allocation.
   PortableMemInfoBlock Info;
 
   void clear() {
     CallStack.clear();
     Info.clear();
   }
 
+  size_t serializedSize() const {
+    return sizeof(uint64_t) + // The number of frames to serialize.
+           sizeof(Frame) * CallStack.size() + // The contents of the frames.
+           PortableMemInfoBlock::serializedSize(); // The size of the payload.
+  }
+
   // Prints out the contents of the memprof record in YAML.
   void print(llvm::raw_ostream &OS) const {
     OS << "    Callstack:\n";
     // TODO: Print out the frame on one line with to make it easier for deep
     // callstacks once we have a test to check valid YAML is generated.
     for (const auto &Frame : CallStack) {
       OS << "    -\n"
          << "      Function: " << Frame.Function << "\n"
          << "      LineOffset: " << Frame.LineOffset << "\n"
          << "      Column: " << Frame.Column << "\n"
          << "      Inline: " << Frame.IsInlineFrame << "\n";
     }
 
     Info.printYAML(OS);
   }
+
+  bool operator==(const MemProfRecord &Other) const {
+    if (Other.Info != Info)
+      return false;
+
+    if (Other.CallStack.size() != CallStack.size())
+      return false;
+
+    for (size_t I = 0; I < Other.CallStack.size(); I++) {
+      if (Other.CallStack[I] != CallStack[I])
+        return false;
+    }
+    return true;
+  }
+};
+
+// Serializes the memprof records in \p Records to the ostream \p OS based on
+// the schema provided in \p Schema.
+void serializeRecords(const ArrayRef<MemProfRecord> Records,
+                      const MemProfSchema &Schema, raw_ostream &OS);
+
+// Deserializes memprof records from the Buffer
+SmallVector<MemProfRecord, 4> deserializeRecords(const MemProfSchema &Schema,
+                                                 const unsigned char *Buffer);
+
+// Reads a memprof schema from a buffer. All entries in the buffer are
+// interpreted as uint64_t. The first entry in the buffer denotes the number of
+// ids in the schema. Subsequent entries are integers which map to memprof::Meta
+// enum class entries. After successfully reading the schema, the pointer is one
+// byte past the schema contents.
+Expected<MemProfSchema> readMemProfSchema(const unsigned char *&Buffer);
+
+using FunctionMemProfMap =
+    DenseMap<uint64_t, SmallVector<memprof::MemProfRecord, 4>>;
+
+/// Trait for lookups into the on-disk hash table for memprof format in the
+/// indexed profile.
+class MemProfRecordLookupTrait {
+public:
+  using data_type = ArrayRef<MemProfRecord>;
+  using internal_key_type = uint64_t;
+  using external_key_type = uint64_t;
+  using hash_value_type = uint64_t;
+  using offset_type = uint64_t;
+
+  MemProfRecordLookupTrait() = delete;
+  MemProfRecordLookupTrait(const MemProfSchema &S) : Schema(S) {}
+
+  static bool EqualKey(uint64_t A, uint64_t B) { return A == B; }
+  static uint64_t GetInternalKey(uint64_t K) { return K; }
+  static uint64_t GetExternalKey(uint64_t K) { return K; }
+
+  hash_value_type ComputeHash(uint64_t K) { return K; }
+
+  static std::pair<offset_type, offset_type>
+  ReadKeyDataLength(const unsigned char *&D) {
+    using namespace support;
+
+    offset_type KeyLen = endian::readNext<offset_type, little, unaligned>(D);
+    offset_type DataLen = endian::readNext<offset_type, little, unaligned>(D);
+    return std::make_pair(KeyLen, DataLen);
+  }
+
+  uint64_t ReadKey(const unsigned char *D, offset_type /*Unused*/) {
+    using namespace support;
+    return endian::readNext<external_key_type, little, unaligned>(D);
+  }
+
+  data_type ReadData(uint64_t K, const unsigned char *D,
+                     offset_type /*Unused*/) {
+    Records = deserializeRecords(Schema, D);
+    return Records;
+  }
+
+private:
+  // Holds the memprof schema used to deserialize records.
+  MemProfSchema Schema;
+  // Holds the records from one function deserialized from the indexed format.
+  llvm::SmallVector<MemProfRecord, 4> Records;
+};
+
+class MemProfRecordWriterTrait {
+public:
+  using key_type = uint64_t;
+  using key_type_ref = uint64_t;
+
+  using data_type = ArrayRef<MemProfRecord>;
+  using data_type_ref = ArrayRef<MemProfRecord>;
+
+  using hash_value_type = uint64_t;
+  using offset_type = uint64_t;
+
+  // Pointer to the memprof schema to use for the generator. Unlike the reader
+  // we must use a default constructor with no params for the writer trait so we
+  // have a public member which must be initialized by the user.
+  MemProfSchema *Schema = nullptr;
+
+  MemProfRecordWriterTrait() = default;
+
+  static hash_value_type ComputeHash(key_type_ref K) { return K; }
+
+  static std::pair<offset_type, offset_type>
+  EmitKeyDataLength(raw_ostream &Out, key_type_ref K, data_type_ref V) {
+    using namespace support;
+
+    endian::Writer LE(Out, little);
+
+    offset_type N = sizeof(K);
+    LE.write<offset_type>(N);
+
+    offset_type M = 0;
+
+    M += sizeof(uint64_t);
+    for (const auto &Record : V) {
+      M += Record.serializedSize();
+    }
+
+    LE.write<offset_type>(M);
+    return std::make_pair(N, M);
+  }
+
+  void EmitKey(raw_ostream &Out, key_type_ref K, offset_type /*Unused*/) {
+    using namespace support;
+    endian::Writer LE(Out, little);
+    LE.write<uint64_t>(K);
+  }
+
+  void EmitData(raw_ostream &Out, key_type_ref /*Unused*/, data_type_ref V,
+                offset_type /*Unused*/) {
+    assert(Schema != nullptr && "MemProf schema is not initialized!");
+    serializeRecords(V, *Schema, Out);
+  }
 };
 
 } // namespace memprof
 } // namespace llvm
 
 #endif // LLVM_PROFILEDATA_MEMPROF_H_

llvm/include/llvm/ProfileData/MemProfData.inc

-#ifndef LLVM_PROFILEDATA_MEMPROFDATA_INC
-#define LLVM_PROFILEDATA_MEMPROFDATA_INC
+#ifndef MEMPROF_DATA_INC
+#define MEMPROF_DATA_INC
 /*===-- MemProfData.inc - MemProf profiling runtime structures -*- C++ -*-=== *\
 |*
 |* Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 |* See https://llvm.org/LICENSE.txt for license information.
 |* SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 |*
 \*===----------------------------------------------------------------------===*/
 /*

llvm/include/llvm/ProfileData/RawMemProfReader.h

public:
 
   using Iterator = InstrProfIterator<MemProfRecord, RawMemProfReader>;
   Iterator end() { return Iterator(); }
   Iterator begin() {
     Iter = ProfileData.begin();
     return Iterator(this);
   }
 
+  // The RawMemProfReader only holds memory profile information.
+  InstrProfKind getProfileKind() const { return InstrProfKind::MemProf; }
+
   // Constructor for unittests only.
   RawMemProfReader(std::unique_ptr<llvm::symbolize::SymbolizableModule> Sym,
                    llvm::SmallVectorImpl<SegmentEntry> &Seg,
                    llvm::MapVector<uint64_t, MemInfoBlock> &Prof,
                    CallStackMap &SM)
       : Symbolizer(std::move(Sym)), SegmentInfo(Seg.begin(), Seg.end()),
         ProfileData(Prof), StackMap(SM) {}
 

llvm/lib/ProfileData/CMakeLists.txt

 add_llvm_component_library(LLVMProfileData
   GCOV.cpp
   InstrProf.cpp
   InstrProfCorrelator.cpp
   InstrProfReader.cpp
   InstrProfWriter.cpp
+  MemProf.cpp
   ProfileSummaryBuilder.cpp
   SampleProf.cpp
   SampleProfReader.cpp
   SampleProfWriter.cpp
   RawMemProfReader.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/ProfileData

llvm/lib/ProfileData/InstrProf.cpp

Expected<Header> Header::readFromBuffer(const unsigned char *Buffer) {
   // Read the version.
   H.Version = read(Buffer, offsetOf(&Header::Version));
   uint64_t FormatVersion = endian::byte_swap<uint64_t, little>(H.Version);
   if (GET_VERSION(FormatVersion) >
       IndexedInstrProf::ProfVersion::CurrentVersion)
     return make_error<InstrProfError>(instrprof_error::unsupported_version);
 
   switch (GET_VERSION(FormatVersion)) {
     // When a new field is added in the header add a case statement here to
     // populate it.
+    static_assert(
+        IndexedInstrProf::ProfVersion::CurrentVersion == Version8,
+        "Please update the reading code below if a new field has been added, "
+        "if not add a case statement to fall through to the latest version.");
+  case 8ull:
+    H.MemProfOffset = read(Buffer, offsetOf(&Header::MemProfOffset));
+    LLVM_FALLTHROUGH;
   default:
     H.HashType = read(Buffer, offsetOf(&Header::HashType));
     H.HashOffset = read(Buffer, offsetOf(&Header::HashOffset));
   }
 
   return H;
 }
 
 size_t Header::size() const {
   switch (GET_VERSION(Version)) {
     // When a new field is added to the header add a case statement here to
     // compute the size as offset of the new field + size of the new field. This
     // relies on the field being added to the end of the list.
+    static_assert(IndexedInstrProf::ProfVersion::CurrentVersion == Version8,
+                  "Please update the size computation below if a new field has "
+                  "been added to the header, if not add a case statement to "
+                  "fall through to the latest version.");
+  case 8ull:
+    return offsetOf(&Header::MemProfOffset) + sizeof(Header::MemProfOffset);
   default:
     return offsetOf(&Header::HashOffset) + sizeof(Header::HashOffset);
   }
 }
 
 } // namespace IndexedInstrProf
 
 } // end namespace llvm

llvm/lib/ProfileData/InstrProfReader.cpp

 #include "llvm/ProfileData/InstrProfReader.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/ProfileSummary.h"
 #include "llvm/ProfileData/InstrProf.h"
+#include "llvm/ProfileData/MemProf.h"
 #include "llvm/ProfileData/ProfileCommon.h"
+#include "llvm/ProfileData/RawMemProfReader.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/SwapByteOrder.h"
 #include "llvm/Support/SymbolRemappingReader.h"
 #include <algorithm>
 #include <cctype>
if (Version & VARIANT_MASK_INSTR_ENTRY) {
     ProfileKind |= InstrProfKind::BB;
   }
   if (Version & VARIANT_MASK_BYTE_COVERAGE) {
     ProfileKind |= InstrProfKind::SingleByteCoverage;
   }
   if (Version & VARIANT_MASK_FUNCTION_ENTRY_ONLY) {
     ProfileKind |= InstrProfKind::FunctionEntryOnly;
   }
+  if (Version & VARIANT_MASK_MEMPROF) {
+    ProfileKind |= InstrProfKind::MemProf;
+  }
   return ProfileKind;
 }
 
 static Expected<std::unique_ptr<MemoryBuffer>>
 setupMemoryBuffer(const Twine &Path) {
   ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOrErr =
       MemoryBuffer::getFileOrSTDIN(Path, /*IsText=*/true);
   if (std::error_code EC = BufferOrErr.getError())
Error IndexedInstrProfReader::readHeader() {
   // Read the hash type and start offset.
   IndexedInstrProf::HashT HashType = static_cast<IndexedInstrProf::HashT>(
       endian::byte_swap<uint64_t, little>(Header->HashType));
   if (HashType > IndexedInstrProf::HashT::Last)
     return error(instrprof_error::unsupported_hash_type);
 
   uint64_t HashOffset = endian::byte_swap<uint64_t, little>(Header->HashOffset);
 
-  // The rest of the file is an on disk hash table.
+  // The hash table with profile counts comes next.
   auto IndexPtr = std::make_unique<InstrProfReaderIndex<OnDiskHashTableImplV3>>(
       Start + HashOffset, Cur, Start, HashType, Header->Version);
 
+  // The MemProfOffset field in the header is only valid when the format version
+  // is higher than 8 (when it was introduced).
+  if (GET_VERSION(Header->Version) >= 8 &&
+      Header->Version & VARIANT_MASK_MEMPROF) {
+    uint64_t MemProfOffset =
+        endian::byte_swap<uint64_t, little>(Header->MemProfOffset);
+
+    const unsigned char *Ptr = Start + MemProfOffset;
+    // The value returned from Generator.Emit.
+    const uint64_t TableOffset =
+        support::endian::readNext<uint64_t, little, unaligned>(Ptr);
+
+    // Read the schema.
+    auto SchemaOr = memprof::readMemProfSchema(Ptr);
+    if (!SchemaOr)
+      return SchemaOr.takeError();
+    Schema = SchemaOr.get();
+
+    // Now initialize the table reader with a pointer into data buffer.
+    MemProfTable.reset(MemProfHashTable::Create(
+        /*Buckets=*/Start + TableOffset,
+        /*Payload=*/Ptr,
+        /*Base=*/Start, memprof::MemProfRecordLookupTrait(Schema)));
+  }
+
   // Load the remapping table now if requested.
   if (RemappingBuffer) {
     Remapper = std::make_unique<
         InstrProfReaderItaniumRemapper<OnDiskHashTableImplV3>>(
         std::move(RemappingBuffer), *IndexPtr);
     if (Error E = Remapper->populateRemappings())
       return E;
   } else {
IndexedInstrProfReader::getInstrProfRecord(StringRef FuncName,
   for (const NamedInstrProfRecord &I : Data) {
     // Check for a match and fill the vector if there is one.
     if (I.Hash == FuncHash)
       return std::move(I);
   }
   return error(instrprof_error::hash_mismatch);
 }
 
+Expected<ArrayRef<memprof::MemProfRecord>>
+IndexedInstrProfReader::getMemProfRecord(uint64_t FuncNameHash) {
+  auto Iter = MemProfTable->find(FuncNameHash);
+  if (Iter == MemProfTable->end())
+    // TODO: Add memprof specific errors.
+    return make_error<InstrProfError>(instrprof_error::hash_mismatch,
+                                      "memprof record not found for hash " +
+                                          Twine(FuncNameHash));
+  return *Iter;
+}
+
 Error IndexedInstrProfReader::getFunctionCounts(StringRef FuncName,
                                                 uint64_t FuncHash,
                                                 std::vector<uint64_t> &Counts) {
   Expected<InstrProfRecord> Record = getInstrProfRecord(FuncName, FuncHash);
   if (Error E = Record.takeError())
     return error(std::move(E));
 
   Counts = Record.get().Counts;

llvm/lib/ProfileData/InstrProfWriter.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ProfileData/InstrProfWriter.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/ProfileSummary.h"
 #include "llvm/ProfileData/InstrProf.h"
+#include "llvm/ProfileData/MemProf.h"
 #include "llvm/ProfileData/ProfileCommon.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/EndianStream.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/OnDiskHashTable.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
public:
   // \c patch can only be called when all data is written and flushed.
   // For raw_string_ostream, the patch is done on the target string
   // directly and it won't be reflected in the stream's internal buffer.
   void patch(PatchItem *P, int NItems) {
     using namespace support;
 
     if (IsFDOStream) {
       raw_fd_ostream &FDOStream = static_cast<raw_fd_ostream &>(OS);
+      const uint64_t LastPos = FDOStream.tell();
       for (int K = 0; K < NItems; K++) {
         FDOStream.seek(P[K].Pos);
         for (int I = 0; I < P[K].N; I++)
           write(P[K].D[I]);
       }
+      // Reset the stream to the last position after patching so that users
+      // don't accidentally overwrite data. This makes it consistent with
+      // the string stream below which replaces the data directly.
+      FDOStream.seek(LastPos);
     } else {
       raw_string_ostream &SOStream = static_cast<raw_string_ostream &>(OS);
       std::string &Data = SOStream.str(); // with flush
       for (int K = 0; K < NItems; K++) {
         for (int I = 0; I < P[K].N; I++) {
           uint64_t Bytes = endian::byte_swap<uint64_t, little>(P[K].D[I]);
           Data.replace(P[K].Pos + I * sizeof(uint64_t), sizeof(uint64_t),
                        (const char *)&Bytes, sizeof(uint64_t));
void InstrProfWriter::addRecord(StringRef Name, uint64_t Hash,
   } else {
     // We're updating a function we've seen before.
     Dest.merge(I, Weight, MapWarn);
   }
 
   Dest.sortValueData();
 }
 
+void InstrProfWriter::addRecord(const memprof::MemProfRecord &MR,
+                                function_ref<void(Error)> Warn) {
+  // Use 0 as a sentinel value since its highly unlikely that the lower 64-bits
+  // of a 128 bit md5 hash will be all zeros.
+  // TODO: Move this Key frame detection to the contructor to avoid having to
+  // scan all the callstacks again when adding a new record.
+  uint64_t Key = 0;
+  for (auto Iter = MR.CallStack.rbegin(), End = MR.CallStack.rend();
+       Iter != End; Iter++) {
+    if (!Iter->IsInlineFrame) {
+      Key = Iter->Function;
+      break;
+    }
+  }
+
+  if (Key == 0) {
+    Warn(make_error<InstrProfError>(
+        instrprof_error::invalid_prof,
+        "could not determine leaf function for memprof record."));
+  }
+
+  MemProfData[Key].push_back(MR);
+}
+
 void InstrProfWriter::mergeRecordsFromWriter(InstrProfWriter &&IPW,
                                              function_ref<void(Error)> Warn) {
   for (auto &I : IPW.FunctionData)
     for (auto &Func : I.getValue())
       addRecord(I.getKey(), Func.first, std::move(Func.second), 1, Warn);
+
+  for (auto &I : IPW.MemProfData)
+    for (const auto &MR : I.second)
+      addRecord(MR, Warn);
 }
 
 bool InstrProfWriter::shouldEncodeData(const ProfilingData &PD) {
   if (!Sparse)
     return true;
   for (const auto &Func : PD) {
     const InstrProfRecord &IPR = Func.second;
     if (llvm::any_of(IPR.Counts, [](uint64_t Count) { return Count > 0; }))
Error InstrProfWriter::writeImpl(ProfOStream &OS) {
   InfoObj->SummaryBuilder = &ISB;
   InstrProfSummaryBuilder CSISB(ProfileSummaryBuilder::DefaultCutoffs);
   InfoObj->CSSummaryBuilder = &CSISB;
 
   // Populate the hash table generator.
   for (const auto &I : FunctionData)
     if (shouldEncodeData(I.getValue()))
       Generator.insert(I.getKey(), &I.getValue());
+
   // Write the header.
   IndexedInstrProf::Header Header;
   Header.Magic = IndexedInstrProf::Magic;
   Header.Version = IndexedInstrProf::ProfVersion::CurrentVersion;
   if (static_cast<bool>(ProfileKind & InstrProfKind::IR))
     Header.Version |= VARIANT_MASK_IR_PROF;
   if (static_cast<bool>(ProfileKind & InstrProfKind::CS))
     Header.Version |= VARIANT_MASK_CSIR_PROF;
   if (static_cast<bool>(ProfileKind & InstrProfKind::BB))
     Header.Version |= VARIANT_MASK_INSTR_ENTRY;
   if (static_cast<bool>(ProfileKind & InstrProfKind::SingleByteCoverage))
     Header.Version |= VARIANT_MASK_BYTE_COVERAGE;
   if (static_cast<bool>(ProfileKind & InstrProfKind::FunctionEntryOnly))
     Header.Version |= VARIANT_MASK_FUNCTION_ENTRY_ONLY;
+  if (static_cast<bool>(ProfileKind & InstrProfKind::MemProf))
+    Header.Version |= VARIANT_MASK_MEMPROF;
 
   Header.Unused = 0;
   Header.HashType = static_cast<uint64_t>(IndexedInstrProf::HashType);
   Header.HashOffset = 0;
+  Header.MemProfOffset = 0;
   int N = sizeof(IndexedInstrProf::Header) / sizeof(uint64_t);
 
-  // Only write out all the fields except 'HashOffset'. We need
-  // to remember the offset of that field to allow back patching
-  // later.
-  for (int I = 0; I < N - 1; I++)
+  // Only write out all the fields except 'HashOffset' and 'MemProfOffset'. We
+  // need to remember the offset of these fields to allow back patching later.
+  for (int I = 0; I < N - 2; I++)
     OS.write(reinterpret_cast<uint64_t *>(&Header)[I]);
 
   // Save the location of Header.HashOffset field in \c OS.
   uint64_t HashTableStartFieldOffset = OS.tell();
   // Reserve the space for HashOffset field.
   OS.write(0);
 
+  // Save the location of MemProf profile data. This is stored in two parts as
+  // the schema and as a separate on-disk chained hashtable.
+  uint64_t MemProfSectionOffset = OS.tell();
+  // Reserve space for the MemProf table field to be patched later if this
+  // profile contains memory profile information.
+  OS.write(0);
+
   // Reserve space to write profile summary data.
   uint32_t NumEntries = ProfileSummaryBuilder::DefaultCutoffs.size();
   uint32_t SummarySize = Summary::getSize(Summary::NumKinds, NumEntries);
   // Remember the summary offset.
   uint64_t SummaryOffset = OS.tell();
   for (unsigned I = 0; I < SummarySize / sizeof(uint64_t); I++)
     OS.write(0);
   uint64_t CSSummaryOffset = 0;
   uint64_t CSSummarySize = 0;
   if (static_cast<bool>(ProfileKind & InstrProfKind::CS)) {
     CSSummaryOffset = OS.tell();
     CSSummarySize = SummarySize / sizeof(uint64_t);
     for (unsigned I = 0; I < CSSummarySize; I++)
       OS.write(0);
   }
 
   // Write the hash table.
   uint64_t HashTableStart = Generator.Emit(OS.OS, *InfoObj);
 
+  // Write the MemProf profile data if we have it. This includes a simple schema
+  // with the format described below followed by the hashtable:
+  // uint64_t Offset = MemProfGenerator.Emit
+  // uint64_t Num schema entries
+  // uint64_t Schema entry 0
+  // uint64_t Schema entry 1
+  // ....
+  // uint64_t Schema entry N - 1
+  // OnDiskChainedHashTable MemProfFunctionData
+  uint64_t MemProfSectionStart = 0;
+  if (static_cast<bool>(ProfileKind & InstrProfKind::MemProf)) {
+    MemProfSectionStart = OS.tell();
+    OS.write(0ULL); // Reserve space for the offset.
+
+    auto Schema = memprof::PortableMemInfoBlock::getSchema();
+    OS.write(static_cast<uint64_t>(Schema.size()));
+    for (const auto Id : Schema) {
+      OS.write(static_cast<uint64_t>(Id));
+    }
+
+    auto MemProfWriter = std::make_unique<memprof::MemProfRecordWriterTrait>();
+    MemProfWriter->Schema = &Schema;
+    OnDiskChainedHashTableGenerator<memprof::MemProfRecordWriterTrait>
+        MemProfGenerator;
+    for (const auto &I : MemProfData) {
+      // Insert the key (func hash) and value (vector of memprof records).
+      MemProfGenerator.insert(I.first, I.second);
+    }
+
+    uint64_t TableOffset = MemProfGenerator.Emit(OS.OS, *MemProfWriter);
+    PatchItem PatchItems[] = {
+        {MemProfSectionStart, &TableOffset, 1},
+    };
+    OS.patch(PatchItems, 1);
+  }
+
   // Allocate space for data to be serialized out.
   std::unique_ptr<IndexedInstrProf::Summary> TheSummary =
       IndexedInstrProf::allocSummary(SummarySize);
   // Compute the Summary and copy the data to the data
   // structure to be serialized out (to disk or buffer).
   std::unique_ptr<ProfileSummary> PS = ISB.getSummary();
   setSummary(TheSummary.get(), *PS);
   InfoObj->SummaryBuilder = nullptr;
 
   // For Context Sensitive summary.
   std::unique_ptr<IndexedInstrProf::Summary> TheCSSummary = nullptr;
   if (static_cast<bool>(ProfileKind & InstrProfKind::CS)) {
     TheCSSummary = IndexedInstrProf::allocSummary(SummarySize);
     std::unique_ptr<ProfileSummary> CSPS = CSISB.getSummary();
     setSummary(TheCSSummary.get(), *CSPS);
   }
   InfoObj->CSSummaryBuilder = nullptr;
 
   // Now do the final patch:
   PatchItem PatchItems[] = {
       // Patch the Header.HashOffset field.
       {HashTableStartFieldOffset, &HashTableStart, 1},
+      // Patch the Header.MemProfOffset (=0 for profiles without MemProf data).
+      {MemProfSectionOffset, &MemProfSectionStart, 1},
       // Patch the summary data.
       {SummaryOffset, reinterpret_cast<uint64_t *>(TheSummary.get()),
        (int)(SummarySize / sizeof(uint64_t))},
       {CSSummaryOffset, reinterpret_cast<uint64_t *>(TheCSSummary.get()),
        (int)CSSummarySize}};
 
   OS.patch(PatchItems, sizeof(PatchItems) / sizeof(*PatchItems));
 

llvm/lib/ProfileData/MemProf.cpp

+#include "llvm/ProfileData/MemProf.h"
+#include "llvm/Support/Endian.h"
+#include "llvm/Support/EndianStream.h"
+
+namespace llvm {
+namespace memprof {
+
+void serializeRecords(const ArrayRef<MemProfRecord> Records,
+                      const MemProfSchema &Schema, raw_ostream &OS) {
+  using namespace support;
+
+  endian::Writer LE(OS, little);
+
+  LE.write<uint64_t>(Records.size());
+  for (const MemProfRecord &MR : Records) {
+    LE.write<uint64_t>(MR.CallStack.size());
+    for (const MemProfRecord::Frame &F : MR.CallStack) {
+      F.write(OS);
+    }
+    MR.Info.serialize(Schema, OS);
+  }
+}
+
+SmallVector<MemProfRecord, 4> deserializeRecords(const MemProfSchema &Schema,
+                                                 const unsigned char *Ptr) {
+  using namespace support;
+
+  SmallVector<MemProfRecord, 4> Records;
+  const uint64_t NumRecords =
+      endian::readNext<uint64_t, little, unaligned>(Ptr);
+  for (uint64_t I = 0; I < NumRecords; I++) {
+    MemProfRecord MR;
+    const uint64_t NumFrames =
+        endian::readNext<uint64_t, little, unaligned>(Ptr);
+    for (uint64_t J = 0; J < NumFrames; J++) {
+      const auto F = *reinterpret_cast<const MemProfRecord::Frame *>(Ptr);
+      Ptr += sizeof(MemProfRecord::Frame);
+      MR.CallStack.push_back(F);
+    }
+    MR.Info.deserialize(Schema, Ptr);
+    Ptr += PortableMemInfoBlock::serializedSize();
+    Records.push_back(MR);
+  }
+  return Records;
+}
+
+Expected<MemProfSchema> readMemProfSchema(const unsigned char *&Buffer) {
+  using namespace support;
+
+  const unsigned char *Ptr = Buffer;
+  const uint64_t NumSchemaIds =
+      endian::readNext<uint64_t, little, unaligned>(Ptr);
+  if (NumSchemaIds > static_cast<uint64_t>(Meta::Size)) {
+    return make_error<InstrProfError>(instrprof_error::malformed,
+                                      "memprof schema invalid");
+  }
+
+  MemProfSchema Result;
+  for (size_t I = 0; I < NumSchemaIds; I++) {
+    const uint64_t Tag = endian::readNext<uint64_t, little, unaligned>(Ptr);
+    if (Tag >= static_cast<uint64_t>(Meta::Size)) {
+      return make_error<InstrProfError>(instrprof_error::malformed,
+                                        "memprof schema invalid");
+    }
+    Result.push_back(static_cast<Meta>(Tag));
+  }
+  // Advace the buffer to one past the schema if we succeeded.
+  Buffer = Ptr;
+  return Result;
+}
+
+} // namespace memprof
+} // namespace llvm

llvm/lib/ProfileData/RawMemProfReader.cpp

for (const uint64_t Address : CallStack) {
 
     if (!DIOr)
       return DIOr.takeError();
     DIInliningInfo DI = DIOr.get();
 
     for (size_t I = 0; I < DI.getNumberOfFrames(); I++) {
       const auto &Frame = DI.getFrame(I);
       Record.CallStack.emplace_back(
-          std::to_string(llvm::MD5Hash(trimSuffix(Frame.FunctionName))),
+          // We use the function guid which we expect to be a uint64_t. At this
+          // time, it is the lower 64 bits of the md5 of the function name. Any
+          // suffix with .llvm. is trimmed since these are added by thinLTO
+          // global promotion. At the time the profile is consumed, these
+          // suffixes will not be present.
+          Function::getGUID(trimSuffix(Frame.FunctionName)),
           Frame.Line - Frame.StartLine, Frame.Column,
           // Only the first entry is not an inlined location.
           I != 0);
     }
   }
   Record.Info = PortableMemInfoBlock(MIB);
   return Error::success();
 }

llvm/test/tools/llvm-profdata/memprof-merge.test

+REQUIRES: x86_64-linux
+
+The input memprof and instrumented raw profiles were generated from the following source code:
+
+```
+#include <stdlib.h>
+#include <string.h>
+int main(int argc, char **argv) {
+  char *x = (char *)malloc(10);
+  memset(x, 0, 10);
+  free(x);
+  x = (char *)malloc(10);
+  memset(x, 0, 10);
+  free(x);
+  return 0;
+}
+```
+
+Steps to collect the memprof raw profile and the instrprof raw profile:
+
+```
+# Collect instrprof profile.
+clang -fprofile-generate source.c -o instr.out
+./instr.out
+mv *.profraw basic.profraw
+
+# Collect memprof profile.
+clang -fuse-ld=lld -Wl,--no-rosegment -gmlt -fdebug-info-for-profiling \
+      -fmemory-profile -mno-omit-leaf-frame-pointer -fno-omit-frame-pointer \
+      -fno-optimize-sibling-calls -m64 -Wl,-build-id source.c -o basic.memprofexe
+
+env MEMPROF_OPTIONS=log_path=stdout ./rawprofile.out > basic.memprofraw
+```
+
+RUN: llvm-profdata merge %p/Inputs/basic.profraw %p/Inputs/basic.memprofraw --profiled-binary %p/Inputs/basic.memprofexe -o %t.prof
+RUN: llvm-profdata show %t.prof | FileCheck %s
+
+For now we only check the validity of the instrumented profile since we don't
+have a way to display the contents of the memprof indexed format yet.
+
+CHECK: Instrumentation level: IR  entry_first = 0
+CHECK: Total functions: 1
+CHECK: Maximum function count: 1
+CHECK: Maximum internal block count: 0
+
+

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

for (auto &I : *Reader) {
     WC->Writer.overlapRecord(std::move(I), Overlap, FuncOverlap, FuncFilter);
     FuncOverlap.dump(OS);
   }
 }
 
 /// Load an input into a writer context.
 static void loadInput(const WeightedFile &Input, SymbolRemapper *Remapper,
                       const InstrProfCorrelator *Correlator,
-                      WriterContext *WC) {
+                      const StringRef ProfiledBinary, WriterContext *WC) {
   std::unique_lock<std::mutex> CtxGuard{WC->Lock};
 
   // Copy the filename, because llvm::ThreadPool copied the input "const
   // WeightedFile &" by value, making a reference to the filename within it
   // invalid outside of this packaged task.
   std::string Filename = Input.Filename;
 
+  using ::llvm::memprof::RawMemProfReader;
+  if (RawMemProfReader::hasFormat(Input.Filename)) {
+    auto ReaderOrErr = RawMemProfReader::create(Input.Filename, ProfiledBinary);
+    if (!ReaderOrErr) {
+      exitWithError(ReaderOrErr.takeError(), Input.Filename);
+    }
+    std::unique_ptr<RawMemProfReader> Reader = std::move(ReaderOrErr.get());
+    // Check if the profile types can be merged, e.g. clang frontend profiles
+    // should not be merged with memprof profiles.
+    if (Error E = WC->Writer.mergeProfileKind(Reader->getProfileKind())) {
+      consumeError(std::move(E));
+      WC->Errors.emplace_back(
+          make_error<StringError>(
+              "Cannot merge MemProf profile with Clang generated profile.",
+              std::error_code()),
+          Filename);
+      return;
+    }
+
+    // Add the records into the writer context.
+    for (const memprof::MemProfRecord &MR : *Reader) {
+      WC->Writer.addRecord(MR, [&](Error E) {
+        instrprof_error IPE = InstrProfError::take(std::move(E));
+        WC->Errors.emplace_back(make_error<InstrProfError>(IPE), Filename);
+      });
+    }
+    return;
+  }
+
   auto ReaderOrErr = InstrProfReader::create(Input.Filename, Correlator);
   if (Error E = ReaderOrErr.takeError()) {
     // Skip the empty profiles by returning sliently.
     instrprof_error IPE = InstrProfError::take(std::move(E));
     if (IPE != instrprof_error::empty_raw_profile)
       WC->Errors.emplace_back(make_error<InstrProfError>(IPE), Filename);
     return;
   }
static void writeInstrProfile(StringRef OutputFilename,
   }
 }
 
 static void mergeInstrProfile(const WeightedFileVector &Inputs,
                               StringRef DebugInfoFilename,
                               SymbolRemapper *Remapper,
                               StringRef OutputFilename,
                               ProfileFormat OutputFormat, bool OutputSparse,
-                              unsigned NumThreads, FailureMode FailMode) {
+                              unsigned NumThreads, FailureMode FailMode,
+                              const StringRef ProfiledBinary) {
   if (OutputFormat != PF_Binary && OutputFormat != PF_Compact_Binary &&
       OutputFormat != PF_Ext_Binary && OutputFormat != PF_Text)
     exitWithError("unknown format is specified");
 
   std::unique_ptr<InstrProfCorrelator> Correlator;
   if (!DebugInfoFilename.empty()) {
     if (auto Err =
             InstrProfCorrelator::get(DebugInfoFilename).moveInto(Correlator))
static void mergeInstrProfile(const WeightedFileVector &Inputs,
   // Initialize the writer contexts.
   SmallVector<std::unique_ptr<WriterContext>, 4> Contexts;
   for (unsigned I = 0; I < NumThreads; ++I)
     Contexts.emplace_back(std::make_unique<WriterContext>(
         OutputSparse, ErrorLock, WriterErrorCodes));
 
   if (NumThreads == 1) {
     for (const auto &Input : Inputs)
-      loadInput(Input, Remapper, Correlator.get(), Contexts[0].get());
+      loadInput(Input, Remapper, Correlator.get(), ProfiledBinary,
+                Contexts[0].get());
   } else {
     ThreadPool Pool(hardware_concurrency(NumThreads));
 
     // Load the inputs in parallel (N/NumThreads serial steps).
     unsigned Ctx = 0;
     for (const auto &Input : Inputs) {
-      Pool.async(loadInput, Input, Remapper, Correlator.get(),
+      Pool.async(loadInput, Input, Remapper, Correlator.get(), ProfiledBinary,
                  Contexts[Ctx].get());
       Ctx = (Ctx + 1) % NumThreads;
     }
     Pool.wait();
 
     // Merge the writer contexts together (~ lg(NumThreads) serial steps).
     unsigned Mid = Contexts.size() / 2;
     unsigned End = Contexts.size();
static void supplementInstrProfile(
   if (std::error_code EC = Reader->read())
     exitWithErrorCode(EC, SampleFilename);
 
   // Read instr profile.
   std::mutex ErrorLock;
   SmallSet<instrprof_error, 4> WriterErrorCodes;
   auto WC = std::make_unique<WriterContext>(OutputSparse, ErrorLock,
                                             WriterErrorCodes);
-  loadInput(Inputs[0], nullptr, nullptr, WC.get());
+  loadInput(Inputs[0], nullptr, nullptr, /*ProfiledBinary=*/"", WC.get());
   if (WC->Errors.size() > 0)
     exitWithError(std::move(WC->Errors[0].first), InstrFilename);
 
   adjustInstrProfile(WC, Reader, SupplMinSizeThreshold, ZeroCounterThreshold,
                      InstrProfColdThreshold);
   writeInstrProfile(OutputFilename, OutputFormat, WC->Writer);
 }
 
cl::opt<unsigned> InstrProfColdThreshold(
       cl::desc("User specified cold threshold for instr profile which will "
                "override the cold threshold got from profile summary. "));
   cl::opt<bool> GenCSNestedProfile(
       "gen-cs-nested-profile", cl::Hidden, cl::init(false),
       cl::desc("Generate nested function profiles for CSSPGO"));
   cl::opt<std::string> DebugInfoFilename(
       "debug-info", cl::init(""),
       cl::desc("Use the provided debug info to correlate the raw profile."));
+  cl::opt<std::string> ProfiledBinary(
+      "profiled-binary", cl::init(""),
+      cl::desc("Path to binary from which the profile was collected."));
 
   cl::ParseCommandLineOptions(argc, argv, "LLVM profile data merger\n");
 
   WeightedFileVector WeightedInputs;
   for (StringRef Filename : InputFilenames)
     addWeightedInput(WeightedInputs, {std::string(Filename), 1});
   for (StringRef WeightedFilename : WeightedInputFilenames)
     addWeightedInput(WeightedInputs, parseWeightedFile(WeightedFilename));
supplementInstrProfile(WeightedInputs, SupplInstrWithSample, OutputFilename,
                            OutputFormat, OutputSparse, SupplMinSizeThreshold,
                            ZeroCounterThreshold, InstrProfColdThreshold);
     return 0;
   }
 
   if (ProfileKind == instr)
     mergeInstrProfile(WeightedInputs, DebugInfoFilename, Remapper.get(),
                       OutputFilename, OutputFormat, OutputSparse, NumThreads,
-                      FailureMode);
+                      FailureMode, ProfiledBinary);
   else
     mergeSampleProfile(WeightedInputs, Remapper.get(), OutputFilename,
                        OutputFormat, ProfileSymbolListFile, CompressAllSections,
                        UseMD5, GenPartialProfile, GenCSNestedProfile,
                        SampleMergeColdContext, SampleTrimColdContext,
                        SampleColdContextFrameDepth, FailureMode);
   return 0;
 }
static void overlapInstrProfile(const std::string &BaseFilename,
   if (Overlap.Base.CountSum < 1.0f) {
     OS << "Sum of edge counts for profile " << BaseFilename << " is 0.\n";
     exit(0);
   }
   if (Overlap.Test.CountSum < 1.0f) {
     OS << "Sum of edge counts for profile " << TestFilename << " is 0.\n";
     exit(0);
   }
-  loadInput(WeightedInput, nullptr, nullptr, &Context);
+  loadInput(WeightedInput, nullptr, nullptr, /*ProfiledBinary=*/"", &Context);
   overlapInput(BaseFilename, TestFilename, &Context, Overlap, FuncFilter, OS,
                IsCS);
   Overlap.dump(OS);
 }
 
 namespace {
 struct SampleOverlapStats {
   SampleContext BaseName;

llvm/unittests/ProfileData/InstrProfTest.cpp

 //===- unittest/ProfileData/InstrProfTest.cpp -------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/ProfileData/InstrProfReader.h"
 #include "llvm/ProfileData/InstrProfWriter.h"
+#include "llvm/ProfileData/MemProf.h"
 #include "llvm/Support/Compression.h"
 #include "llvm/Testing/Support/Error.h"
 #include "llvm/Testing/Support/SupportHelpers.h"
 #include "gtest/gtest.h"
 #include <cstdarg>
 
 using namespace llvm;
 
TEST_F(InstrProfTest, test_writer_merge) {
 
   R = Reader->getInstrProfRecord("func2", 0x1234);
   EXPECT_THAT_ERROR(R.takeError(), Succeeded());
   ASSERT_EQ(2U, R->Counts.size());
   ASSERT_EQ(0U, R->Counts[0]);
   ASSERT_EQ(0U, R->Counts[1]);
 }
 
+TEST_F(InstrProfTest, test_memprof) {
+  ASSERT_THAT_ERROR(Writer.mergeProfileKind(InstrProfKind::MemProf),
+                    Succeeded());
+  llvm::memprof::MemProfRecord MR;
+  MR.CallStack.push_back({0x123, 1, 2, false});
+  MR.CallStack.push_back({0x345, 3, 4, true});
+  Writer.addRecord(MR, Err);
+
+  auto Profile = Writer.writeBuffer();
+  readProfile(std::move(Profile));
+
+  auto RecordsOr = Reader->getMemProfRecord(0x123);
+  ASSERT_THAT_ERROR(RecordsOr.takeError(), Succeeded());
+  const auto Records = RecordsOr.get();
+  ASSERT_EQ(Records.size(), 1U);
+  EXPECT_EQ(Records[0], MR);
+}
+
+TEST_F(InstrProfTest, test_memprof_merge) {
+  Writer.addRecord({"func1", 0x1234, {42}}, Err);
+
+  InstrProfWriter Writer2;
+  ASSERT_THAT_ERROR(Writer2.mergeProfileKind(InstrProfKind::MemProf),
+                    Succeeded());
+
+  llvm::memprof::MemProfRecord MR;
+  MR.CallStack.push_back({0x123, 1, 2, false});
+  MR.CallStack.push_back({0x345, 3, 4, true});
+  Writer2.addRecord(MR, Err);
+
+  ASSERT_THAT_ERROR(Writer.mergeProfileKind(Writer2.getProfileKind()),
+                    Succeeded());
+  Writer.mergeRecordsFromWriter(std::move(Writer2), Err);
+
+  auto Profile = Writer.writeBuffer();
+  readProfile(std::move(Profile));
+
+  Expected<InstrProfRecord> R = Reader->getInstrProfRecord("func1", 0x1234);
+  EXPECT_THAT_ERROR(R.takeError(), Succeeded());
+  ASSERT_EQ(1U, R->Counts.size());
+  ASSERT_EQ(42U, R->Counts[0]);
+
+  auto RecordsOr = Reader->getMemProfRecord(0x123);
+  ASSERT_THAT_ERROR(RecordsOr.takeError(), Succeeded());
+  const auto Records = RecordsOr.get();
+  ASSERT_EQ(Records.size(), 1U);
+  EXPECT_EQ(Records[0], MR);
+}
+
+TEST_F(InstrProfTest, test_memprof_invalid_add_record) {
+  llvm::memprof::MemProfRecord MR;
+  // At least one of the frames should be a non-inline frame.
+  MR.CallStack.push_back({0x123, 1, 2, true});
+  MR.CallStack.push_back({0x345, 3, 4, true});
+
+  auto CheckErr = [](Error &&E) {
+    EXPECT_TRUE(ErrorEquals(instrprof_error::invalid_prof, std::move(E)));
+  };
+  Writer.addRecord(MR, CheckErr);
+}
+
 static const char callee1[] = "callee1";
 static const char callee2[] = "callee2";
 static const char callee3[] = "callee3";
 static const char callee4[] = "callee4";
 static const char callee5[] = "callee5";
 static const char callee6[] = "callee6";
 
 TEST_P(MaybeSparseInstrProfTest, get_icall_data_read_write) {

llvm/unittests/ProfileData/MemProfTest.cpp

 }
 
 const DILineInfoSpecifier specifier() {
   return DILineInfoSpecifier(
       DILineInfoSpecifier::FileLineInfoKind::RawValue,
       DILineInfoSpecifier::FunctionNameKind::LinkageName);
 }
 
-MATCHER_P4(FrameContains, Function, LineOffset, Column, Inline, "") {
-  const std::string ExpectedHash = std::to_string(llvm::MD5Hash(Function));
+MATCHER_P4(FrameContains, FunctionName, LineOffset, Column, Inline, "") {
+  const uint64_t ExpectedHash = llvm::Function::getGUID(FunctionName);
   if (arg.Function != ExpectedHash) {
     *result_listener << "Hash mismatch";
     return false;
   }
   if (arg.LineOffset == LineOffset && arg.Column == Column &&
       arg.IsInlineFrame == Inline) {
     return true;
   }
   *result_listener << "LineOffset, Column or Inline mismatch";
   return false;
 }
 
+MATCHER_P(EqualsRecord, Want, "") {
+  if (arg == Want)
+    return true;
+
+  std::string Explanation;
+  llvm::raw_string_ostream OS(Explanation);
+  OS << "\n Want: \n";
+  Want.print(OS);
+  OS << "\n Got: \n";
+  arg.print(OS);
+  OS.flush();
+
+  *result_listener << Explanation;
+  return false;
+}
+
 MemProfSchema getFullSchema() {
   MemProfSchema Schema;
 #define MIBEntryDef(NameTag, Name, Type) Schema.push_back(Meta::Name);
 #include "llvm/ProfileData/MIBEntryDef.inc"
 #undef MIBEntryDef
   return Schema;
 }
 
TEST(MemProf, PortableWrapper) {
 
   PortableMemInfoBlock ReadBlock(
       Schema, reinterpret_cast<const unsigned char *>(Buffer.data()));
 
   EXPECT_EQ(ReadBlock, WriteBlock);
   // Here we compare directly with the actual counts instead of MemInfoBlock
   // members. Since the MemInfoBlock struct is packed and the EXPECT_EQ macros
   // take a reference to the params, this results in unaligned accesses.
-  EXPECT_EQ(1, ReadBlock.getAllocCount());
-  EXPECT_EQ(7, ReadBlock.getTotalAccessCount());
-  EXPECT_EQ(3, ReadBlock.getAllocCpuId());
+  EXPECT_EQ(1UL, ReadBlock.getAllocCount());
+  EXPECT_EQ(7ULL, ReadBlock.getTotalAccessCount());
+  EXPECT_EQ(3UL, ReadBlock.getAllocCpuId());
 }
 
+TEST(MemProf, RecordSerializationRoundTrip) {
+  const MemProfSchema Schema = getFullSchema();
+
+  llvm::SmallVector<MemProfRecord, 3> Records;
+  MemProfRecord MR;
+
+  MemInfoBlock Info(/*size=*/16, /*access_count=*/7, /*alloc_timestamp=*/1000,
+                    /*dealloc_timestamp=*/2000, /*alloc_cpu=*/3,
+                    /*dealloc_cpu=*/4);
+
+  MR.Info = PortableMemInfoBlock(Info);
+  MR.CallStack.push_back({0x123, 1, 2, false});
+  MR.CallStack.push_back({0x345, 3, 4, false});
+  Records.push_back(MR);
+
+  MR.clear();
+  MR.Info = PortableMemInfoBlock(Info);
+  MR.CallStack.push_back({0x567, 5, 6, false});
+  MR.CallStack.push_back({0x789, 7, 8, false});
+  Records.push_back(MR);
+
+  std::string Buffer;
+  llvm::raw_string_ostream OS(Buffer);
+  serializeRecords(Records, Schema, OS);
+  OS.flush();
+
+  const llvm::SmallVector<MemProfRecord, 4> GotRecords = deserializeRecords(
+      Schema, reinterpret_cast<const unsigned char *>(Buffer.data()));
+
+  ASSERT_TRUE(!GotRecords.empty());
+  EXPECT_EQ(GotRecords.size(), Records.size());
+  EXPECT_THAT(GotRecords[0], EqualsRecord(Records[0]));
+  EXPECT_THAT(GotRecords[1], EqualsRecord(Records[1]));
+}
 } // namespace