[memprof] Deduplicate and outline frame storage in the memprof profile.

[snehasish]

Summary

The current implementation of memprof information in the indexed profile
format stores the representation of each calling context fram inline.
This patch uses an interned representation where the frame contents are
stored in a separate on-disk hash table. The table is indexed via a hash
of the contents of the frame. With this patch, the compressed size of a
large memprof profile reduces by ~22%.

[tejohnson]

Great! Few minor comments/questions.

llvm/include/llvm/ProfileData/InstrProfWriter.h

48

From the declaration it looks like it is the reverse: holds memprof frame id to frame mappings.

llvm/include/llvm/ProfileData/MemProf.h

231

Out of curiosity, how did you choose the hashing algorithm and the value 0x9e3779b9? Is it worth documenting?

Also, the shifts on Result are unnecessary on this line since it is init to 0 just above, although if you think it is clearer to leave all the lines the same that's fine.

llvm/lib/ProfileData/InstrProfReader.cpp

972

RecordTableGenerator?

977

FrameTableGenerator?

llvm/lib/ProfileData/InstrProfWriter.cpp

258

Why not change the function signature to not take this parameter and then not pass it everywhere? Or do we plan to use this in the future? In the latter case, add a TODO.

408

Missing documentation for the FramePayloadOffset emitted above FrameTableOffset?

llvm/unittests/ProfileData/InstrProfTest.cpp

260

Not clear to me why a lambda is needed here since it is only invoked once directly below. Is it just for readability?

llvm/unittests/ProfileData/MemProfTest.cpp

179

Should this commented code line be here?

[snehasish]

Address comments.

[snehasish]

Thanks for the review, ptal!

llvm/include/llvm/ProfileData/MemProf.h

231

This is inspired by boost::hash_combine. :)
Updated the code a bit here to reduce the verbosity, updated the constant to a 64-bit value (since at least one element is 64-bit) and added a comment to make things clear. There is some more info about the constant here: https://softwareengineering.stackexchange.com/a/402543

llvm/unittests/ProfileData/InstrProfTest.cpp

260

Using the Equals lambda in the prior diff allowed me to have a single place for the printing code. In this diff, I've refactored out the print code as a lambda and inlined the comparison. I don't have a strong preference for either, let me know what you think.

llvm/unittests/ProfileData/MemProfTest.cpp

179

Leftover from a prior iteration, removed.

[tejohnson]

lgtm, couple minor things noted below.

llvm/include/llvm/ProfileData/InstrProfWriter.h

48

s/memprof id/frame id/ ?

llvm/unittests/ProfileData/InstrProfTest.cpp

260

Ah ok, that makes sense. I like the way you have it organized in the new version, it is a little clearer.

272

Nit, remove the braces around single line bodies here and below.

llvm/unittests/ProfileData/MemProfTest.cpp

179

Is the comment relevant here or should that be removed too?

[snehasish]

Address comments.

[snehasish]

Thanks for the detailed review as always. :)

llvm/include/llvm/ProfileData/InstrProfReader.h

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>;
+using MemProfRecordHashTable =
+    OnDiskIterableChainedHashTable<memprof::RecordLookupTrait>;
+using MemProfFrameHashTable =
+    OnDiskIterableChainedHashTable<memprof::FrameLookupTrait>;
 
 template <typename HashTableImpl>
 class InstrProfReaderItaniumRemapper;
 
 template <typename HashTableImpl>
 class InstrProfReaderIndex : public InstrProfReaderIndexBase {
 private:
   std::unique_ptr<HashTableImpl> HashTable;
private:
   /// 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;
+  /// MemProf record profile data on-disk indexed via llvm::md5(FunctionName).
+  std::unique_ptr<MemProfRecordHashTable> MemProfRecordTable;
+  /// MemProf frame profile data on-disk indexed via frame id.
+  std::unique_ptr<MemProfFrameHashTable> MemProfFrameTable;
 
   // 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,
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
+  /// Return the memprof record for the function identified by
   /// llvm::md5(Name).
-  Expected<ArrayRef<memprof::MemProfRecord>>
-  getMemProfRecord(uint64_t FuncNameHash);
+  Expected<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) {

llvm/include/llvm/ProfileData/InstrProfWriter.h

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.
-  llvm::MapVector<GlobalValue::GUID, memprof::MemProfRecord> MemProfData;
+  llvm::MapVector<GlobalValue::GUID, memprof::IndexedMemProfRecord>
+      MemProfRecordData;
+  // A map to hold memprof frame to id mappings. The mappings are used to
+  // convert IndexedMemProfRecord to MemProfRecords with frame information
+  // inline.
+  llvm::MapVector<memprof::FrameId, memprof::Frame> MemProfFrameData;
 
   // 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 GlobalValue::GUID Id,
-                 const memprof::MemProfRecord &Record,
+  /// Add a memprof record for a function identified by its \p Id.
+  void addMemProfRecord(const GlobalValue::GUID Id,
+                        const memprof::IndexedMemProfRecord &Record,
+                        function_ref<void(Error)> Warn);
+
+  /// Add a memprof frame identified by the hash of the contents of the frame in
+  /// \p FrameId.
+  bool addMemProfFrame(const memprof::FrameId, const memprof::Frame &F,
                        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);
 

llvm/include/llvm/ProfileData/MemProf.h

 #ifndef LLVM_PROFILEDATA_MEMPROF_H_
 #define LLVM_PROFILEDATA_MEMPROF_H_
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLFunctionalExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/ProfileData/MemProfData.inc"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/EndianStream.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include <cstdint>
#undef MIBEntryDef
   }
 
 private:
 #define MIBEntryDef(NameTag, Name, Type) Type Name = Type();
 #include "llvm/ProfileData/MIBEntryDef.inc"
 #undef MIBEntryDef
 };
 
-// Holds the memprof profile information for a function.
-struct MemProfRecord {
-  // 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.
-  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;
+// A type representing the id generated by hashing the contents of the Frame.
+using FrameId = uint64_t;
 
-    Frame(uint64_t Hash, uint32_t Off, uint32_t Col, bool Inline)
-        : Function(Hash), LineOffset(Off), Column(Col), IsInlineFrame(Inline) {}
+  Frame(const Frame &Other) {
+    Function = Other.Function;
+    LineOffset = Other.LineOffset;
+    Column = Other.Column;
+    IsInlineFrame = Other.IsInlineFrame;
+  }
+
 
-    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); }
+  Frame &operator=(const Frame &Other) {
+    Function = Other.Function;
+    LineOffset = Other.LineOffset;
+    Column = Other.Column;
+    IsInlineFrame = Other.IsInlineFrame;
+    return *this;
+  }
+
 
-    // Write the contents of the frame to the ostream \p OS.
-    void serialize(raw_ostream & OS) const {
-      using namespace support;
+  void serialize(raw_ostream &OS) const {
 
-      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);
-    }
 
-    // Read a frame from char data which has been serialized as little endian.
-    static Frame deserialize(const unsigned char *Ptr) {
-      using namespace support;
 
-      const uint64_t F = endian::readNext<uint64_t, little, unaligned>(Ptr);
-      const uint32_t L = endian::readNext<uint32_t, little, unaligned>(Ptr);
-      const uint32_t C = endian::readNext<uint32_t, little, unaligned>(Ptr);
-      const bool I = endian::readNext<bool, little, unaligned>(Ptr);
-      return Frame(/*Function=*/F, /*LineOffset=*/L, /*Column=*/C,
-                   /*IsInlineFrame=*/I);
-    }
 
-    // Returns the size of the frame information.
-    static constexpr size_t serializedSize() {
-      return sizeof(Frame::Function) + sizeof(Frame::LineOffset) +
-             sizeof(Frame::Column) + sizeof(Frame::IsInlineFrame);
-    }
 
-    // Print the frame information in YAML format.
-    void printYAML(raw_ostream &OS) const {
-      OS << "      -\n"
-         << "        Function: " << Function << "\n"
-         << "        LineOffset: " << LineOffset << "\n"
-         << "        Column: " << Column << "\n"
-         << "        Inline: " << IsInlineFrame << "\n";
-    }
-  };
+
+  // Return a hash value based on the contents of the frame. Here we don't use
+  // hashing from llvm ADT since we are going to persist the hash id, the hash
+  // combine algorithm in ADT uses a new randomized seed each time.
+  inline FrameId hash() const {
+    std::hash<uint64_t> U64Hasher;
+    std::hash<uint32_t> U32Hasher;
+    std::hash<bool> BoolHasher;
+
+    size_t Result = 0;
+    Result ^= U64Hasher(Function) + 0x9e3779b9 + (Result << 6) + (Result >> 2);
+    Result ^=
+        U32Hasher(LineOffset) + 0x9e3779b9 + (Result << 6) + (Result >> 2);
+    Result ^= U32Hasher(Column) + 0x9e3779b9 + (Result << 6) + (Result >> 2);
+    Result ^=
+        BoolHasher(IsInlineFrame) + 0x9e3779b9 + (Result << 6) + (Result >> 2);
+    return static_cast<FrameId>(Result);
+  }
 
-  struct AllocationInfo {
-    // The dynamic calling context for the allocation.
-    llvm::SmallVector<Frame> CallStack;
-    // The statistics obtained from the runtime for the allocation.
-    PortableMemInfoBlock Info;
+// Holds allocation information in a space efficient format where frames are
+// represented using unique identifiers.
+struct IndexedAllocationInfo {
+  // The dynamic calling context for the allocation in bottom-up (leaf-to-root)
+  // order. Frame contents are stored out-of-line.
+  llvm::SmallVector<FrameId> CallStack;
 
-    AllocationInfo() = default;
-    AllocationInfo(ArrayRef<Frame> CS, const MemInfoBlock &MB)
-        : CallStack(CS.begin(), CS.end()), Info(MB) {}
+  IndexedAllocationInfo() = default;
+  IndexedAllocationInfo(ArrayRef<FrameId> CS, const MemInfoBlock &MB)
 
-    void printYAML(raw_ostream &OS) const {
-      OS << "    -\n";
-      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)
-        Frame.printYAML(OS);
-      Info.printYAML(OS);
-    }
-
-    size_t serializedSize() const {
-      return sizeof(uint64_t) + // The number of frames to serialize.
-             Frame::serializedSize() *
-                 CallStack.size() + // The contents of the frames.
-             PortableMemInfoBlock::serializedSize(); // The size of the payload.
-    }
+  // Returns the size in bytes when this allocation info struct is serialized.
+           sizeof(FrameId) * CallStack.size() +    // The callstack frame ids.
 
-    bool operator==(const AllocationInfo &Other) const {
-      if (Other.Info != Info)
-        return false;
+  bool operator==(const IndexedAllocationInfo &Other) const {
 
-      if (Other.CallStack.size() != CallStack.size())
-        return false;
 
-      for (size_t J = 0; J < Other.CallStack.size(); J++) {
-        if (Other.CallStack[J] != CallStack[J])
-          return false;
-      }
-      return true;
-    }
 
-    bool operator!=(const AllocationInfo &Other) const {
-      return !operator==(Other);
-    }
-  };
+  bool operator!=(const IndexedAllocationInfo &Other) const {
 
-  // Memory allocation sites in this function for which we have memory profiling
-  // data.
-  llvm::SmallVector<AllocationInfo> AllocSites;
-  // Holds call sites in this function which are part of some memory allocation
-  // context. We store this as a list of locations, each with its list of
-  // inline locations in bottom-up order i.e. from leaf to root. The inline
-  // location list may include additional entries, users should pick the last
-  // entry in the list with the same function GUID.
-  llvm::SmallVector<llvm::SmallVector<Frame>> CallSites;
+// Holds allocation information with frame contents inline. The type should
+// be used for temporary in-memory instances.
+struct AllocationInfo {
+  // Same as IndexedAllocationInfo::CallStack with the frame contents inline.
+  llvm::SmallVector<Frame> CallStack;
+  // Same as IndexedAllocationInfo::Info;
+  PortableMemInfoBlock Info;
+
+  AllocationInfo() = default;
+  AllocationInfo(
+      const IndexedAllocationInfo &IndexedAI,
+      llvm::function_ref<const Frame(const FrameId)> IdToFrameCallback) {
+    for (const FrameId &Id : IndexedAI.CallStack) {
+      CallStack.push_back(IdToFrameCallback(Id));
+    }
+    Info = IndexedAI.Info;
+  }
+
+  void printYAML(raw_ostream &OS) const {
+    OS << "    -\n";
+    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 Frame &F : CallStack) {
+      F.printYAML(OS);
+    }
+    Info.printYAML(OS);
+  }
+};
+
+// Holds the memprof profile information for a function. The internal
+// representation stores frame ids for efficiency. This representation should
+// be used in the profile conversion and manipulation tools.
+struct IndexedMemProfRecord {
+  // Memory allocation sites in this function for which we have memory
+  // profiling data.
+  llvm::SmallVector<IndexedAllocationInfo> AllocSites;
+  // Holds call sites in this function which are part of some memory
+  // allocation context. We store this as a list of locations, each with its
+  // list of inline locations in bottom-up order i.e. from leaf to root. The
+  // inline location list may include additional entries, users should pick
+  // the last entry in the list with the same function GUID.
+  llvm::SmallVector<llvm::SmallVector<FrameId>> CallSites;
 
   void clear() {
     AllocSites.clear();
     CallSites.clear();
   }
 
-  void merge(const MemProfRecord &Other) {
-    // TODO: Filter out duplicates which may occur if multiple memprof profiles
-    // are merged together using llvm-profdata.
+  void merge(const IndexedMemProfRecord &Other) {
+    // TODO: Filter out duplicates which may occur if multiple memprof
+    // profiles are merged together using llvm-profdata.
     AllocSites.append(Other.AllocSites);
     CallSites.append(Other.CallSites);
   }
 
   size_t serializedSize() const {
     size_t Result = sizeof(GlobalValue::GUID);
-    for (const AllocationInfo &N : AllocSites)
+    for (const IndexedAllocationInfo &N : AllocSites)
       Result += N.serializedSize();
 
     // The number of callsites we have information for.
     Result += sizeof(uint64_t);
     for (const auto &Frames : CallSites) {
-      // The number of frames to serialize.
+      // The number of frame ids to serialize.
       Result += sizeof(uint64_t);
-      for (const Frame &F : Frames)
-        Result += F.serializedSize();
+      Result += Frames.size() * sizeof(FrameId);
     }
     return Result;
   }
 
-  // Prints out the contents of the memprof record in YAML.
-  void print(llvm::raw_ostream &OS) const {
-    if (!AllocSites.empty()) {
-      OS << "    AllocSites:\n";
-      for (const AllocationInfo &N : AllocSites)
-        N.printYAML(OS);
-    }
-
-    if (!CallSites.empty()) {
-      OS << "    CallSites:\n";
-      for (const auto &Frames : CallSites) {
-        for (const auto &F : Frames) {
-          OS << "    -\n";
-          F.printYAML(OS);
-        }
-      }
-    }
-  }
-
-  bool operator==(const MemProfRecord &Other) const {
+  bool operator==(const IndexedMemProfRecord &Other) const {
     if (Other.AllocSites.size() != AllocSites.size())
       return false;
 
     if (Other.CallSites.size() != CallSites.size())
       return false;
 
     for (size_t I = 0; I < AllocSites.size(); I++) {
       if (AllocSites[I] != Other.AllocSites[I])
         return false;
     }
 
     for (size_t I = 0; I < CallSites.size(); I++) {
       if (CallSites[I] != Other.CallSites[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.
+  // Serializes the memprof records in \p Records to the ostream \p OS based
+  // on the schema provided in \p Schema.
   void serialize(const MemProfSchema &Schema, raw_ostream &OS);
 
   // Deserializes memprof records from the Buffer.
-  static MemProfRecord deserialize(const MemProfSchema &Schema,
+  static IndexedMemProfRecord deserialize(const MemProfSchema &Schema,
                                           const unsigned char *Buffer);
 
-  // Returns the GUID for the function name after canonicalization. For memprof,
-  // we remove any .llvm suffix added by LTO. MemProfRecords are mapped to
-  // functions using this GUID.
+  // Returns the GUID for the function name after canonicalization. For
+  // memprof, we remove any .llvm suffix added by LTO. MemProfRecords are
+  // mapped to functions using this GUID.
   static GlobalValue::GUID getGUID(const StringRef FunctionName);
 };
 
+// Holds the memprof profile information for a function. The internal
+// representation stores frame contents inline. This representation should
+// be used for small amount of temporary, in memory instances.
+struct MemProfRecord {
+  // Same as IndexedMemProfRecord::AllocSites with frame contents inline.
+  llvm::SmallVector<AllocationInfo> AllocSites;
+  // Same as IndexedMemProfRecord::CallSites with frame contents inline.
+  llvm::SmallVector<llvm::SmallVector<Frame>> CallSites;
+
+  MemProfRecord() = default;
+  MemProfRecord(
+      const IndexedMemProfRecord &Record,
+      llvm::function_ref<const Frame(const FrameId Id)> IdToFrameCallback) {
+    for (const IndexedAllocationInfo &IndexedAI : Record.AllocSites) {
+      AllocSites.emplace_back(IndexedAI, IdToFrameCallback);
+    }
+    for (const ArrayRef<FrameId> Site : Record.CallSites) {
+      llvm::SmallVector<Frame> Frames;
+      for (const FrameId Id : Site) {
+        Frames.push_back(IdToFrameCallback(Id));
+      }
+      CallSites.push_back(Frames);
+    }
+  }
+
+  // Prints out the contents of the memprof record in YAML.
+  void print(llvm::raw_ostream &OS) const {
+    if (!AllocSites.empty()) {
+      OS << "    AllocSites:\n";
+      for (const AllocationInfo &N : AllocSites)
+        N.printYAML(OS);
+    }
+
+    if (!CallSites.empty()) {
+      OS << "    CallSites:\n";
+      for (const llvm::SmallVector<Frame> &Frames : CallSites) {
+        for (const Frame &F : Frames) {
+          OS << "    -\n";
+          F.printYAML(OS);
+        }
+      }
+    }
+  }
+};
+
 // 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);
 
-/// Trait for lookups into the on-disk hash table for memprof format in the
-/// indexed profile.
-class MemProfRecordLookupTrait {
+// Trait for reading IndexedMemProfRecord data from the on-disk hash table.
+class RecordLookupTrait {
 public:
-  using data_type = const MemProfRecord &;
+  using data_type = const IndexedMemProfRecord &;
   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) {}
+  RecordLookupTrait() = delete;
+  RecordLookupTrait(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*/) {
-    Record = MemProfRecord::deserialize(Schema, D);
+    Record = IndexedMemProfRecord::deserialize(Schema, D);
     return Record;
   }
 
 private:
   // Holds the memprof schema used to deserialize records.
   MemProfSchema Schema;
   // Holds the records from one function deserialized from the indexed format.
-  MemProfRecord Record;
+  IndexedMemProfRecord Record;
 };
 
-class MemProfRecordWriterTrait {
+// Trait for writing IndexedMemProfRecord data to the on-disk hash table.
+class RecordWriterTrait {
 public:
   using key_type = uint64_t;
   using key_type_ref = uint64_t;
 
-  using data_type = MemProfRecord;
-  using data_type_ref = MemProfRecord &;
+  using data_type = IndexedMemProfRecord;
+  using data_type_ref = IndexedMemProfRecord &;
 
   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;
+  RecordWriterTrait() = 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);
public:
 
   void EmitData(raw_ostream &Out, key_type_ref /*Unused*/, data_type_ref V,
                 offset_type /*Unused*/) {
     assert(Schema != nullptr && "MemProf schema is not initialized!");
     V.serialize(*Schema, Out);
   }
 };
 
+// Trait for writing frame mappings to the on-disk hash table.
+class FrameWriterTrait {
+public:
+  using key_type = FrameId;
+  using key_type_ref = FrameId;
+
+  using data_type = Frame;
+  using data_type_ref = Frame &;
+
+  using hash_value_type = FrameId;
+  using offset_type = uint64_t;
+
+  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 = V.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<key_type>(K);
+  }
+
+  void EmitData(raw_ostream &Out, key_type_ref /*Unused*/, data_type_ref V,
+                offset_type /*Unused*/) {
+    V.serialize(Out);
+  }
+};
+
+// Trait for reading frame mappings from the on-disk hash table.
+class FrameLookupTrait {
+public:
+  using data_type = const Frame;
+  using internal_key_type = FrameId;
+  using external_key_type = FrameId;
+  using hash_value_type = FrameId;
+  using offset_type = uint64_t;
+
+  static bool EqualKey(internal_key_type A, internal_key_type B) {
+    return A == B;
+  }
+  static uint64_t GetInternalKey(internal_key_type K) { return K; }
+  static uint64_t GetExternalKey(external_key_type K) { return K; }
+
+  hash_value_type ComputeHash(internal_key_type 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*/) {
+    return Frame::deserialize(D);
+  }
+};
 } // namespace memprof
 } // namespace llvm
 
 #endif // LLVM_PROFILEDATA_MEMPROF_H_

llvm/include/llvm/ProfileData/RawMemProfReader.h

RawMemProfReader(std::unique_ptr<llvm::symbolize::SymbolizableModule> Sym,
     // If there is an error here then the mock symbolizer has not been
     // initialized properly.
     if (Error E = symbolizeAndFilterStackFrames())
       report_fatal_error(std::move(E));
     if (Error E = mapRawProfileToRecords())
       report_fatal_error(std::move(E));
   }
 
+  // Return a const reference to the internal Id to Frame mappings.
+  const llvm::DenseMap<FrameId, Frame> &getFrameMapping() const {
+    return IdToFrame;
+  }
+
+  // Return a const reference to the internal function profile data.
+  const llvm::MapVector<GlobalValue::GUID, IndexedMemProfRecord> &
+  getProfileData() const {
+    return FunctionProfileData;
+  }
+
 private:
   RawMemProfReader(std::unique_ptr<MemoryBuffer> DataBuffer,
                    object::OwningBinary<object::Binary> &&Bin)
       : DataBuffer(std::move(DataBuffer)), Binary(std::move(Bin)) {}
   Error initialize();
   Error readRawProfile();
   // Symbolize and cache all the virtual addresses we encounter in the
   // callstacks from the raw profile. Also prune callstack frames which we can't
   // symbolize or those that belong to the runtime. For profile entries where
   // the entire callstack is pruned, we drop the entry from the profile.
   Error symbolizeAndFilterStackFrames();
   // Construct memprof records for each function and store it in the
   // `FunctionProfileData` map. A function may have allocation profile data or
   // callsite data or both.
   Error mapRawProfileToRecords();
 
+  // A helper method to extract the frame from the IdToFrame map.
+  const Frame &idToFrame(const FrameId Id) const {
+    auto It = IdToFrame.find(Id);
+    assert(It != IdToFrame.end() && "Id not found in map.");
+    return It->getSecond();
+  }
+
   object::SectionedAddress getModuleOffset(uint64_t VirtualAddress);
   // Prints aggregate counts for each raw profile parsed from the DataBuffer in
   // YAML format.
   void printSummaries(raw_ostream &OS) const;
 
   std::unique_ptr<MemoryBuffer> DataBuffer;
   object::OwningBinary<object::Binary> Binary;
   std::unique_ptr<llvm::symbolize::SymbolizableModule> Symbolizer;
 
   // The contents of the raw profile.
   llvm::SmallVector<SegmentEntry, 16> SegmentInfo;
   // A map from callstack id (same as key in CallStackMap below) to the heap
   // information recorded for that allocation context.
   llvm::MapVector<uint64_t, MemInfoBlock> CallstackProfileData;
   CallStackMap StackMap;
 
   // Cached symbolization from PC to Frame.
-  llvm::DenseMap<uint64_t, llvm::SmallVector<MemProfRecord::Frame>>
-      SymbolizedFrame;
+  llvm::DenseMap<uint64_t, llvm::SmallVector<FrameId>> SymbolizedFrame;
+  llvm::DenseMap<FrameId, Frame> IdToFrame;
 
-  llvm::MapVector<GlobalValue::GUID, MemProfRecord> FunctionProfileData;
-  llvm::MapVector<GlobalValue::GUID, MemProfRecord>::iterator Iter;
+  llvm::MapVector<GlobalValue::GUID, IndexedMemProfRecord> FunctionProfileData;
+  llvm::MapVector<GlobalValue::GUID, IndexedMemProfRecord>::iterator Iter;
 };
 
 } // namespace memprof
 } // namespace llvm
 
 #endif // LLVM_PROFILEDATA_RAWMEMPROFREADER_H_

llvm/lib/ProfileData/InstrProfReader.cpp

Error IndexedInstrProfReader::readHeader() {
   // 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->formatVersion()) >= 8 &&
       Header->formatVersion() & 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 =
+    // The value returned from RecordGenerator.Emit.
+    const uint64_t RecordTableOffset =
+        support::endian::readNext<uint64_t, little, unaligned>(Ptr);
+    const uint64_t FramePayloadOffset =
+        support::endian::readNext<uint64_t, little, unaligned>(Ptr);
+    // The value returned from FrameGenerator.Emit.
+    const uint64_t FrameTableOffset =
         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,
+    MemProfRecordTable.reset(MemProfRecordHashTable::Create(
+        /*Buckets=*/Start + RecordTableOffset,
         /*Payload=*/Ptr,
-        /*Base=*/Start, memprof::MemProfRecordLookupTrait(Schema)));
+        /*Base=*/Start, memprof::RecordLookupTrait(Schema)));
+
+    // Initialize the frame table reader with the payload and bucket offsets.
+    MemProfFrameTable.reset(MemProfFrameHashTable::Create(
+        /*Buckets=*/Start + FrameTableOffset,
+        /*Payload=*/Start + FramePayloadOffset,
+        /*Base=*/Start, memprof::FrameLookupTrait()));
   }
 
   // Load the remapping table now if requested.
   if (RemappingBuffer) {
     Remapper = std::make_unique<
         InstrProfReaderItaniumRemapper<OnDiskHashTableImplV3>>(
         std::move(RemappingBuffer), *IndexPtr);
     if (Error E = Remapper->populateRemappings())
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>>
+Expected<memprof::MemProfRecord>
 IndexedInstrProfReader::getMemProfRecord(const uint64_t FuncNameHash) {
   // TODO: Add memprof specific errors.
-  if (MemProfTable == nullptr)
+  if (MemProfRecordTable == nullptr)
     return make_error<InstrProfError>(instrprof_error::invalid_prof,
                                       "no memprof data available in profile");
-  auto Iter = MemProfTable->find(FuncNameHash);
-  if (Iter == MemProfTable->end())
+  auto Iter = MemProfRecordTable->find(FuncNameHash);
+  if (Iter == MemProfRecordTable->end())
     return make_error<InstrProfError>(instrprof_error::hash_mismatch,
                                       "memprof record not found for hash " +
                                           Twine(FuncNameHash));
-  return *Iter;
+
+  // Setup a callback to convert from frame ids to frame using the on-disk
+  // FrameData hash table.
+  memprof::FrameId LastUnmappedFrameId = 0;
+  bool HasFrameMappingError = false;
+  auto IdToFrameCallback = [&](const memprof::FrameId Id) {
+    auto FrIter = MemProfFrameTable->find(Id);
+    if (FrIter == MemProfFrameTable->end()) {
+      LastUnmappedFrameId = Id;
+      HasFrameMappingError = true;
+      return memprof::Frame(0, 0, 0, false);
+    }
+    return *FrIter;
+  };
+
+  memprof::MemProfRecord Record(*Iter, IdToFrameCallback);
+
+  // Check that all frame ids were successfully converted to frames.
+  if (HasFrameMappingError) {
+    return make_error<InstrProfError>(instrprof_error::hash_mismatch,
+                                      "memprof frame not found for frame id " +
+                                          Twine(LastUnmappedFrameId));
+  }
+  return Record;
 }
 
 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));

llvm/lib/ProfileData/InstrProfWriter.cpp

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 Function::GUID Id,
-                                const memprof::MemProfRecord &Record,
-                                function_ref<void(Error)> Warn) {
-  auto Result = MemProfData.insert({Id, Record});
+void InstrProfWriter::addMemProfRecord(
+    const Function::GUID Id, const memprof::IndexedMemProfRecord &Record,
+    function_ref<void(Error)> /*Unused*/) {
+  auto Result = MemProfRecordData.insert({Id, Record});
   if (!Result.second) {
-    memprof::MemProfRecord &Existing = Result.first->second;
+    memprof::IndexedMemProfRecord &Existing = Result.first->second;
     Existing.merge(Record);
   }
 }
 
+bool InstrProfWriter::addMemProfFrame(const memprof::FrameId Id,
+                                      const memprof::Frame &Frame,
+                                      function_ref<void(Error)> Warn) {
+  auto Result = MemProfFrameData.insert({Id, Frame});
+  // If a mapping already exists for the current frame id and it does not
+  // match the new mapping provided then reset the existing contents and bail
+  // out. We don't support the merging of memprof data whose Frame -> Id
+  // mapping across profiles is inconsistent.
+  if (!Result.second && Result.first->second != Frame) {
+    Warn(make_error<InstrProfError>(instrprof_error::malformed,
+                                    "frame to id mapping mismatch"));
+    return false;
+  }
+  return true;
+}
+
 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) {
-    addRecord(I.first, I.second, Warn);
+  MemProfFrameData.reserve(IPW.MemProfFrameData.size());
+  for (auto &I : IPW.MemProfFrameData) {
+    // If we weren't able to add the frame mappings then it doesn't make sense
+    // to try to merge the records from this profile.
+    if (!addMemProfFrame(I.first, I.second, Warn))
+      return;
+  }
+
+  MemProfRecordData.reserve(IPW.MemProfRecordData.size());
+  for (auto &I : IPW.MemProfRecordData) {
+    addMemProfRecord(I.first, I.second, Warn);
   }
 }
 
 bool InstrProfWriter::shouldEncodeData(const ProfilingData &PD) {
   if (!Sparse)
     return true;
   for (const auto &Func : PD) {
     const InstrProfRecord &IPR = Func.second;
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 RecordTableOffset = RecordTableGenerator.Emit
+  // uint64_t FrameTableOffset = FrameTableGenerator.Emit
   // uint64_t Num schema entries
   // uint64_t Schema entry 0
   // uint64_t Schema entry 1
   // ....
   // uint64_t Schema entry N - 1
-  // OnDiskChainedHashTable MemProfFunctionData
+  // OnDiskChainedHashTable MemProfRecordData
+  // OnDiskChainedHashTable MemProfFrameData
   uint64_t MemProfSectionStart = 0;
   if (static_cast<bool>(ProfileKind & InstrProfKind::MemProf)) {
     MemProfSectionStart = OS.tell();
-    OS.write(0ULL); // Reserve space for the offset.
+    OS.write(0ULL); // Reserve space for the memprof record table offset.
+    OS.write(0ULL); // Reserve space for the memprof frame payload offset.
+    OS.write(0ULL); // Reserve space for the memprof frame table 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 (auto &I : MemProfData) {
+    auto RecordWriter = std::make_unique<memprof::RecordWriterTrait>();
+    RecordWriter->Schema = &Schema;
+    OnDiskChainedHashTableGenerator<memprof::RecordWriterTrait>
+        RecordTableGenerator;
+    for (auto &I : MemProfRecordData) {
       // Insert the key (func hash) and value (memprof record).
-      MemProfGenerator.insert(I.first, I.second);
+      RecordTableGenerator.insert(I.first, I.second);
     }
 
-    uint64_t TableOffset = MemProfGenerator.Emit(OS.OS, *MemProfWriter);
+    uint64_t RecordTableOffset =
+        RecordTableGenerator.Emit(OS.OS, *RecordWriter);
+
+    uint64_t FramePayloadOffset = OS.tell();
+
+    auto FrameWriter = std::make_unique<memprof::FrameWriterTrait>();
+    OnDiskChainedHashTableGenerator<memprof::FrameWriterTrait>
+        FrameTableGenerator;
+    for (auto &I : MemProfFrameData) {
+      // Insert the key (frame id) and value (frame contents).
+      FrameTableGenerator.insert(I.first, I.second);
+    }
+
+    uint64_t FrameTableOffset = FrameTableGenerator.Emit(OS.OS, *FrameWriter);
+
     PatchItem PatchItems[] = {
-        {MemProfSectionStart, &TableOffset, 1},
+        {MemProfSectionStart, &RecordTableOffset, 1},
+        {MemProfSectionStart + sizeof(uint64_t), &FramePayloadOffset, 1},
+        {MemProfSectionStart + 2 * sizeof(uint64_t), &FrameTableOffset, 1},
     };
-    OS.patch(PatchItems, 1);
+    OS.patch(PatchItems, 3);
   }
 
   // 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();

llvm/lib/ProfileData/MemProf.cpp

 #include "llvm/ProfileData/MemProf.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/Function.h"
 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/EndianStream.h"
 
 namespace llvm {
 namespace memprof {
 
-void MemProfRecord::serialize(const MemProfSchema &Schema, raw_ostream &OS) {
+void IndexedMemProfRecord::serialize(const MemProfSchema &Schema,
+                                     raw_ostream &OS) {
   using namespace support;
 
   endian::Writer LE(OS, little);
 
   LE.write<uint64_t>(AllocSites.size());
-  for (const AllocationInfo &N : AllocSites) {
+  for (const IndexedAllocationInfo &N : AllocSites) {
     LE.write<uint64_t>(N.CallStack.size());
-    for (const Frame &F : N.CallStack)
-      F.serialize(OS);
+    for (const FrameId &Id : N.CallStack)
+      LE.write<FrameId>(Id);
     N.Info.serialize(Schema, OS);
   }
 
   // Related contexts.
   LE.write<uint64_t>(CallSites.size());
   for (const auto &Frames : CallSites) {
     LE.write<uint64_t>(Frames.size());
-    for (const Frame &F : Frames)
-      F.serialize(OS);
+    for (const FrameId &Id : Frames)
+      LE.write<FrameId>(Id);
   }
 }
 
-MemProfRecord MemProfRecord::deserialize(const MemProfSchema &Schema,
-                                         const unsigned char *Ptr) {
+IndexedMemProfRecord
+IndexedMemProfRecord::deserialize(const MemProfSchema &Schema,
   using namespace support;
 
-  MemProfRecord Record;
+  IndexedMemProfRecord Record;
 
   // Read the meminfo nodes.
   const uint64_t NumNodes = endian::readNext<uint64_t, little, unaligned>(Ptr);
   for (uint64_t I = 0; I < NumNodes; I++) {
-    MemProfRecord::AllocationInfo Node;
+    IndexedAllocationInfo Node;
     const uint64_t NumFrames =
         endian::readNext<uint64_t, little, unaligned>(Ptr);
     for (uint64_t J = 0; J < NumFrames; J++) {
-      const auto F = MemProfRecord::Frame::deserialize(Ptr);
-      Ptr += MemProfRecord::Frame::serializedSize();
-      Node.CallStack.push_back(F);
+      const FrameId Id = endian::readNext<FrameId, little, unaligned>(Ptr);
+      Node.CallStack.push_back(Id);
     }
     Node.Info.deserialize(Schema, Ptr);
     Ptr += PortableMemInfoBlock::serializedSize();
     Record.AllocSites.push_back(Node);
   }
 
   // Read the callsite information.
   const uint64_t NumCtxs = endian::readNext<uint64_t, little, unaligned>(Ptr);
   for (uint64_t J = 0; J < NumCtxs; J++) {
     const uint64_t NumFrames =
         endian::readNext<uint64_t, little, unaligned>(Ptr);
-    llvm::SmallVector<Frame> Frames;
+    llvm::SmallVector<FrameId> Frames;
+    Frames.reserve(NumFrames);
     for (uint64_t K = 0; K < NumFrames; K++) {
-      const auto F = MemProfRecord::Frame::deserialize(Ptr);
-      Ptr += MemProfRecord::Frame::serializedSize();
-      Frames.push_back(F);
+      const FrameId Id = endian::readNext<FrameId, little, unaligned>(Ptr);
+      Frames.push_back(Id);
     }
     Record.CallSites.push_back(Frames);
   }
 
   return Record;
 }
 
-GlobalValue::GUID MemProfRecord::getGUID(const StringRef FunctionName) {
+GlobalValue::GUID IndexedMemProfRecord::getGUID(const StringRef FunctionName) {
   const auto Pos = FunctionName.find(".llvm.");
 
   // 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.
   return Function::getGUID(FunctionName.take_front(Pos));

llvm/lib/ProfileData/RawMemProfReader.cpp

Error RawMemProfReader::initialize() {
 
   return mapRawProfileToRecords();
 }
 
 Error RawMemProfReader::mapRawProfileToRecords() {
   // Hold a mapping from function to each callsite location we encounter within
   // it that is part of some dynamic allocation context. The location is stored
   // as a pointer to a symbolized list of inline frames.
-  using LocationPtr = const llvm::SmallVector<MemProfRecord::Frame> *;
+  using LocationPtr = const llvm::SmallVector<FrameId> *;
   llvm::DenseMap<GlobalValue::GUID, llvm::SetVector<LocationPtr>>
       PerFunctionCallSites;
 
   // Convert the raw profile callstack data into memprof records. While doing so
   // keep track of related contexts so that we can fill these in later.
   for (const auto &Entry : CallstackProfileData) {
     const uint64_t StackId = Entry.first;
 
     auto It = StackMap.find(StackId);
     if (It == StackMap.end())
       return make_error<InstrProfError>(
           instrprof_error::malformed,
           "memprof callstack record does not contain id: " + Twine(StackId));
 
     // Construct the symbolized callstack.
-    llvm::SmallVector<MemProfRecord::Frame> Callstack;
+    llvm::SmallVector<FrameId> Callstack;
     Callstack.reserve(It->getSecond().size());
 
     llvm::ArrayRef<uint64_t> Addresses = It->getSecond();
     for (size_t I = 0; I < Addresses.size(); I++) {
       const uint64_t Address = Addresses[I];
       assert(SymbolizedFrame.count(Address) > 0 &&
              "Address not found in SymbolizedFrame map");
-      const SmallVector<MemProfRecord::Frame> &Frames =
-          SymbolizedFrame[Address];
+      const SmallVector<FrameId> &Frames = SymbolizedFrame[Address];
 
-      assert(!Frames.back().IsInlineFrame &&
+      assert(!idToFrame(Frames.back()).IsInlineFrame &&
              "The last frame should not be inlined");
 
       // Record the callsites for each function. Skip the first frame of the
       // first address since it is the allocation site itself that is recorded
       // as an alloc site.
       for (size_t J = 0; J < Frames.size(); J++) {
         if (I == 0 && J == 0)
           continue;
         // We attach the entire bottom-up frame here for the callsite even
         // though we only need the frames up to and including the frame for
         // Frames[J].Function. This will enable better deduplication for
         // compression in the future.
-        PerFunctionCallSites[Frames[J].Function].insert(&Frames);
+        const GlobalValue::GUID Guid = idToFrame(Frames[J]).Function;
+        PerFunctionCallSites[Guid].insert(&Frames);
       }
 
       // Add all the frames to the current allocation callstack.
       Callstack.append(Frames.begin(), Frames.end());
     }
 
     // We attach the memprof record to each function bottom-up including the
     // first non-inline frame.
     for (size_t I = 0; /*Break out using the condition below*/; I++) {
+      const Frame &F = idToFrame(Callstack[I]);
       auto Result =
-          FunctionProfileData.insert({Callstack[I].Function, MemProfRecord()});
-      MemProfRecord &Record = Result.first->second;
+          FunctionProfileData.insert({F.Function, IndexedMemProfRecord()});
+      IndexedMemProfRecord &Record = Result.first->second;
       Record.AllocSites.emplace_back(Callstack, Entry.second);
 
-      if (!Callstack[I].IsInlineFrame)
+      if (!F.IsInlineFrame)
         break;
     }
   }
 
   // Fill in the related callsites per function.
   for (auto I = PerFunctionCallSites.begin(), E = PerFunctionCallSites.end();
        I != E; I++) {
     const GlobalValue::GUID Id = I->first;
     // Some functions may have only callsite data and no allocation data. Here
     // we insert a new entry for callsite data if we need to.
-    auto Result = FunctionProfileData.insert({Id, MemProfRecord()});
-    MemProfRecord &Record = Result.first->second;
+    auto Result = FunctionProfileData.insert({Id, IndexedMemProfRecord()});
+    IndexedMemProfRecord &Record = Result.first->second;
     for (LocationPtr Loc : I->getSecond()) {
       Record.CallSites.push_back(*Loc);
     }
   }
 
   return Error::success();
 }
 
for (const uint64_t VAddr : Entry.getSecond()) {
       if (DI.getFrame(0).FunctionName == DILineInfo::BadString ||
           isRuntimePath(DI.getFrame(0).FileName)) {
         AllVAddrsToDiscard.insert(VAddr);
         continue;
       }
 
       for (size_t I = 0, NumFrames = DI.getNumberOfFrames(); I < NumFrames;
            I++) {
-        const auto &Frame = DI.getFrame(I);
+        const auto &DIFrame = DI.getFrame(I);
         LLVM_DEBUG(
             // Print out the name to guid mapping for debugging.
-            llvm::dbgs() << "FunctionName: " << Frame.FunctionName << " GUID: "
-                         << MemProfRecord::getGUID(Frame.FunctionName)
+            llvm::dbgs() << "FunctionName: " << DIFrame.FunctionName
+                         << " GUID: "
+                         << IndexedMemProfRecord::getGUID(DIFrame.FunctionName)
                          << "\n";);
-        SymbolizedFrame[VAddr].emplace_back(
-            MemProfRecord::getGUID(Frame.FunctionName),
-            Frame.Line - Frame.StartLine, Frame.Column,
+
+        const Frame F(IndexedMemProfRecord::getGUID(DIFrame.FunctionName),
+                      DIFrame.Line - DIFrame.StartLine, DIFrame.Column,
                       // Only the last entry is not an inlined location.
                       I != NumFrames - 1);
+
+        const FrameId Id = F.hash();
+        IdToFrame.insert({Id, F});
+        SymbolizedFrame[VAddr].push_back(Id);
       }
     }
 
     auto &CallStack = Entry.getSecond();
     CallStack.erase(std::remove_if(CallStack.begin(), CallStack.end(),
                                    [&AllVAddrsToDiscard](const uint64_t A) {
                                      return AllVAddrsToDiscard.contains(A);
                                    }),

 
 Error RawMemProfReader::readNextRecord(GuidMemProfRecordPair &GuidRecord) {
   if (FunctionProfileData.empty())
     return make_error<InstrProfError>(instrprof_error::empty_raw_profile);
 
   if (Iter == FunctionProfileData.end())
     return make_error<InstrProfError>(instrprof_error::eof);
 
-  GuidRecord = {Iter->first, Iter->second};
+  auto IdToFrameCallback = [this](const FrameId Id) {
+    return this->idToFrame(Id);
+  };
+  const IndexedMemProfRecord &IndexedRecord = Iter->second;
+  GuidRecord = {Iter->first, MemProfRecord(IndexedRecord, IdToFrameCallback)};
   Iter++;
   return Error::success();
 }
 } // namespace memprof
 } // namespace llvm

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

if (Error E = WC->Writer.mergeProfileKind(Reader->getProfileKind())) {
       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 (auto I = Reader->begin(), E = Reader->end(); I != E; ++I) {
-      WC->Writer.addRecord(/*Id=*/I->first, /*Record=*/I->second, [&](Error E) {
-        instrprof_error IPE = InstrProfError::take(std::move(E));
-        WC->Errors.emplace_back(make_error<InstrProfError>(IPE), Filename);
-      });
+    auto MemProfError = [&](Error E) {
+    };
+
+    // Add the frame mappings into the writer context.
+    const auto &IdToFrame = Reader->getFrameMapping();
+    for (const auto &I : IdToFrame) {
+      bool Succeeded = WC->Writer.addMemProfFrame(
+          /*Id=*/I.first, /*Frame=*/I.getSecond(), MemProfError);
+      // If we weren't able to add the frame mappings then it doesn't make sense
+      // to try to add the records from this profile.
+      if (!Succeeded)
+        return;
+    }
+    const auto &FunctionProfileData = Reader->getProfileData();
+    // Add the memprof records into the writer context.
+    for (const auto &I : FunctionProfileData) {
+      WC->Writer.addMemProfRecord(/*Id=*/I.first, /*Record=*/I.second,
+                                  MemProfError);
     }
     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));

llvm/unittests/ProfileData/InstrProfTest.cpp

 #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/ProfileData/MemProfData.inc"
 #include "llvm/Support/Compression.h"
+#include "llvm/Support/raw_ostream.h"
 #include "llvm/Testing/Support/Error.h"
 #include "llvm/Testing/Support/SupportHelpers.h"
 #include "gtest/gtest.h"
 #include <cstdarg>
 
 using namespace llvm;
 
 LLVM_NODISCARD static ::testing::AssertionResult
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]);
 }
 
+using ::llvm::memprof::IndexedMemProfRecord;
 using ::llvm::memprof::MemInfoBlock;
-using ::llvm::memprof::MemProfRecord;
-MemProfRecord
-makeRecord(std::initializer_list<std::initializer_list<MemProfRecord::Frame>>
-               AllocFrames,
-           std::initializer_list<std::initializer_list<MemProfRecord::Frame>>
-               CallSiteFrames,
-           const MemInfoBlock &Block = MemInfoBlock()) {
-  llvm::memprof::MemProfRecord MR;
+using FrameIdMapTy =
+    llvm::DenseMap<::llvm::memprof::FrameId, ::llvm::memprof::Frame>;
+
+static FrameIdMapTy getFrameMapping() {
+  FrameIdMapTy Mapping;
+  Mapping.insert({0, {0x123, 1, 2, false}});
+  Mapping.insert({1, {0x345, 3, 4, true}});
+  Mapping.insert({2, {0x125, 5, 6, false}});
+  Mapping.insert({3, {0x567, 7, 8, true}});
+  Mapping.insert({4, {0x124, 5, 6, false}});
+  Mapping.insert({5, {0x789, 8, 9, true}});
+  return Mapping;
+}
+
+IndexedMemProfRecord makeRecord(
+    std::initializer_list<std::initializer_list<::llvm::memprof::FrameId>>
+    std::initializer_list<std::initializer_list<::llvm::memprof::FrameId>>
+  llvm::memprof::IndexedMemProfRecord MR;
   for (const auto &Frames : AllocFrames)
     MR.AllocSites.emplace_back(Frames, Block);
   for (const auto &Frames : CallSiteFrames)
     MR.CallSites.push_back(Frames);
   return MR;
 }
 
+MATCHER_P(EqualsRecord, Want, "") {
+  const memprof::MemProfRecord &Got = arg;
+
+  auto Equals = [&]() {
+    if (Want.AllocSites.size() != Got.AllocSites.size())
+      return false;
+    if (Want.CallSites.size() != Got.CallSites.size())
+      return false;
+
+    for (size_t I = 0; I < Got.AllocSites.size(); I++) {
+      if (Want.AllocSites[I].Info != Got.AllocSites[I].Info)
+        return false;
+      if (Want.AllocSites[I].CallStack != Got.AllocSites[I].CallStack)
+        return false;
+    }
+
+    for (size_t I = 0; I < Got.CallSites.size(); I++) {
+      if (Want.CallSites[I] != Got.CallSites[I])
+        return false;
+    }
+    return true;
+  };
+
+  if (Equals())
+    return true;
+
+  std::string Buffer;
+  llvm::raw_string_ostream OS(Buffer);
+  OS << "Want:\n";
+  Want.print(OS);
+  OS << "Got:\n";
+  Got.print(OS);
+  OS.flush();
+  *result_listener << "MemProf Record differs!\n" << Buffer;
+  return false;
+}
+
 TEST_F(InstrProfTest, test_memprof) {
   ASSERT_THAT_ERROR(Writer.mergeProfileKind(InstrProfKind::MemProf),
                     Succeeded());
 
-  const MemProfRecord MR = makeRecord(
+  const IndexedMemProfRecord IndexedMR = makeRecord(
       /*AllocFrames=*/
       {
-          {{0x123, 1, 2, false}, {0x345, 3, 4, true}},
-          {{0x125, 5, 6, false}, {0x567, 7, 8, true}},
+          {0, 1},
+          {2, 3},
       },
       /*CallSiteFrames=*/{
-          {{0x124, 5, 6, false}, {0x789, 8, 9, true}},
+          {4, 5},
       });
-  Writer.addRecord(/*Id=*/0x9999, MR, Err);
+  const FrameIdMapTy IdToFrameMap = getFrameMapping();
+  for (const auto &I : IdToFrameMap) {
+    Writer.addMemProfFrame(I.first, I.getSecond(), Err);
+  }
+  Writer.addMemProfRecord(/*Id=*/0x9999, IndexedMR, Err);
 
   auto Profile = Writer.writeBuffer();
   readProfile(std::move(Profile));
 
-  auto RecordsOr = Reader->getMemProfRecord(0x9999);
-  ASSERT_THAT_ERROR(RecordsOr.takeError(), Succeeded());
-  const auto Records = RecordsOr.get();
-  ASSERT_EQ(Records.size(), 1U);
-  EXPECT_EQ(Records[0], MR);
+  auto RecordOr = Reader->getMemProfRecord(0x9999);
+  ASSERT_THAT_ERROR(RecordOr.takeError(), Succeeded());
+  const memprof::MemProfRecord &Record = RecordOr.get();
+
+  memprof::FrameId LastUnmappedFrameId = 0;
+  bool HasFrameMappingError = false;
+  auto IdToFrameCallback = [&](const memprof::FrameId Id) {
+    auto Iter = IdToFrameMap.find(Id);
+    if (Iter == IdToFrameMap.end()) {
+      LastUnmappedFrameId = Id;
+      HasFrameMappingError = true;
+      return memprof::Frame(0, 0, 0, false);
+    }
+    return Iter->second;
+  };
+
+  const memprof::MemProfRecord WantRecord(IndexedMR, IdToFrameCallback);
+  ASSERT_FALSE(HasFrameMappingError)
+      << "could not map frame id: " << LastUnmappedFrameId;
+  EXPECT_THAT(WantRecord, EqualsRecord(Record));
+}
+
+TEST_F(InstrProfTest, test_memprof_getrecord_error) {
+  ASSERT_THAT_ERROR(Writer.mergeProfileKind(InstrProfKind::MemProf),
+                    Succeeded());
+
+  const IndexedMemProfRecord IndexedMR = makeRecord(
+      /*AllocFrames=*/
+      {
+          {0, 1},
+          {2, 3},
+      },
+      /*CallSiteFrames=*/{
+          {4, 5},
+      });
+  // We skip adding the frame mappings here unlike the test_memprof unit test
+  // above to exercise the failure path when getMemProfRecord is invoked.
+  Writer.addMemProfRecord(/*Id=*/0x9999, IndexedMR, Err);
+
+  auto Profile = Writer.writeBuffer();
+  readProfile(std::move(Profile));
+
+  auto RecordOr = Reader->getMemProfRecord(0x9999);
+  EXPECT_THAT_ERROR(RecordOr.takeError(), Failed());
 }
 
 TEST_F(InstrProfTest, test_memprof_merge) {
   Writer.addRecord({"func1", 0x1234, {42}}, Err);
 
   InstrProfWriter Writer2;
   ASSERT_THAT_ERROR(Writer2.mergeProfileKind(InstrProfKind::MemProf),
                     Succeeded());
 
-  const MemProfRecord MR = makeRecord(
+  const IndexedMemProfRecord IndexedMR = makeRecord(
       /*AllocFrames=*/
       {
-          {{0x123, 1, 2, false}, {0x345, 3, 4, true}},
-          {{0x125, 5, 6, false}, {0x567, 7, 8, true}},
+          {0, 1},
+          {2, 3},
       },
       /*CallSiteFrames=*/{
-          {{0x124, 5, 6, false}, {0x789, 8, 9, true}},
+          {4, 5},
       });
-  Writer2.addRecord(/*Id=*/0x9999, MR, Err);
+
+  const FrameIdMapTy IdToFrameMap = getFrameMapping();
+  for (const auto &I : IdToFrameMap) {
+    Writer.addMemProfFrame(I.first, I.getSecond(), Err);
+  }
+  Writer2.addMemProfRecord(/*Id=*/0x9999, IndexedMR, 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(0x9999);
-  ASSERT_THAT_ERROR(RecordsOr.takeError(), Succeeded());
-  const auto Records = RecordsOr.get();
-  ASSERT_EQ(Records.size(), 1U);
-  EXPECT_EQ(Records[0], MR);
+  auto RecordOr = Reader->getMemProfRecord(0x9999);
+  ASSERT_THAT_ERROR(RecordOr.takeError(), Succeeded());
+  const memprof::MemProfRecord &Record = RecordOr.get();
+
+  memprof::FrameId LastUnmappedFrameId = 0;
+  bool HasFrameMappingError = false;
+
+  auto IdToFrameCallback = [&](const memprof::FrameId Id) {
+    auto Iter = IdToFrameMap.find(Id);
+    if (Iter == IdToFrameMap.end()) {
+      LastUnmappedFrameId = Id;
+      HasFrameMappingError = true;
+      return memprof::Frame(0, 0, 0, false);
+    }
+    return Iter->second;
+  };
+
+  const memprof::MemProfRecord WantRecord(IndexedMR, IdToFrameCallback);
+  ASSERT_FALSE(HasFrameMappingError)
+      << "could not map frame id: " << LastUnmappedFrameId;
+  EXPECT_THAT(WantRecord, EqualsRecord(Record));
 }
 
 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";

llvm/unittests/ProfileData/MemProfTest.cpp

 namespace {
 
 using ::llvm::DIGlobal;
 using ::llvm::DIInliningInfo;
 using ::llvm::DILineInfo;
 using ::llvm::DILineInfoSpecifier;
 using ::llvm::DILocal;
 using ::llvm::memprof::CallStackMap;
+using ::llvm::memprof::Frame;
+using ::llvm::memprof::FrameId;
+using ::llvm::memprof::IndexedMemProfRecord;
 using ::llvm::memprof::MemInfoBlock;
 using ::llvm::memprof::MemProfRecord;
 using ::llvm::memprof::MemProfSchema;
 using ::llvm::memprof::Meta;
 using ::llvm::memprof::PortableMemInfoBlock;
 using ::llvm::memprof::RawMemProfReader;
 using ::llvm::memprof::SegmentEntry;
 using ::llvm::object::SectionedAddress;

 
 const DILineInfoSpecifier specifier() {
   return DILineInfoSpecifier(
       DILineInfoSpecifier::FileLineInfoKind::RawValue,
       DILineInfoSpecifier::FunctionNameKind::LinkageName);
 }
 
 MATCHER_P4(FrameContains, FunctionName, LineOffset, Column, Inline, "") {
+  const Frame &F = arg;
+
   const uint64_t ExpectedHash = llvm::Function::getGUID(FunctionName);
-  if (arg.Function != ExpectedHash) {
+  if (F.Function != ExpectedHash) {
     *result_listener << "Hash mismatch";
     return false;
   }
-  if (arg.LineOffset == LineOffset && arg.Column == Column &&
-      arg.IsInlineFrame == Inline) {
+  if (F.LineOffset == LineOffset && F.Column == Column &&
+      F.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, FillsValue) {
   // inline xyz() { bar(); }         N               Y
   // abc() { xyz(); }                N               Y
 
   // We expect 4 records. We attach alloc site data to foo and bar, i.e.
   // all frames bottom up until we find a non-inline frame. We attach call site
   // data to bar, xyz and abc.
   ASSERT_EQ(Records.size(), 4U);
 
+  // The actual frame data is stored out of line in a separate map so we pass
+  // the mappings to the matcher to extract the frame and match the contents.
+  // const auto &IdToFrame = Reader.getFrameMapping();
+
   // Check the memprof record for foo.
-  const llvm::GlobalValue::GUID FooId = MemProfRecord::getGUID("foo");
+  const llvm::GlobalValue::GUID FooId = IndexedMemProfRecord::getGUID("foo");
   ASSERT_EQ(Records.count(FooId), 1U);
   const MemProfRecord &Foo = Records[FooId];
   ASSERT_EQ(Foo.AllocSites.size(), 1U);
   EXPECT_EQ(Foo.AllocSites[0].Info.getAllocCount(), 1U);
   EXPECT_THAT(Foo.AllocSites[0].CallStack[0],
               FrameContains("foo", 5U, 30U, true));
   EXPECT_THAT(Foo.AllocSites[0].CallStack[1],
               FrameContains("bar", 51U, 20U, false));
   EXPECT_THAT(Foo.AllocSites[0].CallStack[2],
               FrameContains("xyz", 5U, 30U, true));
   EXPECT_THAT(Foo.AllocSites[0].CallStack[3],
               FrameContains("abc", 5U, 30U, false));
   EXPECT_TRUE(Foo.CallSites.empty());
 
   // Check the memprof record for bar.
-  const llvm::GlobalValue::GUID BarId = MemProfRecord::getGUID("bar");
+  const llvm::GlobalValue::GUID BarId = IndexedMemProfRecord::getGUID("bar");
   ASSERT_EQ(Records.count(BarId), 1U);
   const MemProfRecord &Bar = Records[BarId];
   ASSERT_EQ(Bar.AllocSites.size(), 1U);
   EXPECT_EQ(Bar.AllocSites[0].Info.getAllocCount(), 1U);
   EXPECT_THAT(Bar.AllocSites[0].CallStack[0],
               FrameContains("foo", 5U, 30U, true));
   EXPECT_THAT(Bar.AllocSites[0].CallStack[1],
               FrameContains("bar", 51U, 20U, false));
   EXPECT_THAT(Bar.AllocSites[0].CallStack[2],
               FrameContains("xyz", 5U, 30U, true));
   EXPECT_THAT(Bar.AllocSites[0].CallStack[3],
               FrameContains("abc", 5U, 30U, false));
 
   ASSERT_EQ(Bar.CallSites.size(), 1U);
   ASSERT_EQ(Bar.CallSites[0].size(), 2U);
   EXPECT_THAT(Bar.CallSites[0][0], FrameContains("foo", 5U, 30U, true));
   EXPECT_THAT(Bar.CallSites[0][1], FrameContains("bar", 51U, 20U, false));
 
   // Check the memprof record for xyz.
-  const llvm::GlobalValue::GUID XyzId = MemProfRecord::getGUID("xyz");
+  const llvm::GlobalValue::GUID XyzId = IndexedMemProfRecord::getGUID("xyz");
   ASSERT_EQ(Records.count(XyzId), 1U);
   const MemProfRecord &Xyz = Records[XyzId];
   ASSERT_EQ(Xyz.CallSites.size(), 1U);
   ASSERT_EQ(Xyz.CallSites[0].size(), 2U);
   // Expect the entire frame even though in practice we only need the first
   // entry here.
   EXPECT_THAT(Xyz.CallSites[0][0], FrameContains("xyz", 5U, 30U, true));
   EXPECT_THAT(Xyz.CallSites[0][1], FrameContains("abc", 5U, 30U, false));
 
   // Check the memprof record for abc.
-  const llvm::GlobalValue::GUID AbcId = MemProfRecord::getGUID("abc");
+  const llvm::GlobalValue::GUID AbcId = IndexedMemProfRecord::getGUID("abc");
   ASSERT_EQ(Records.count(AbcId), 1U);
   const MemProfRecord &Abc = Records[AbcId];
   EXPECT_TRUE(Abc.AllocSites.empty());
   ASSERT_EQ(Abc.CallSites.size(), 1U);
   ASSERT_EQ(Abc.CallSites[0].size(), 2U);
   EXPECT_THAT(Abc.CallSites[0][0], FrameContains("xyz", 5U, 30U, true));
   EXPECT_THAT(Abc.CallSites[0][1], FrameContains("abc", 5U, 30U, false));
 }

 
 TEST(MemProf, RecordSerializationRoundTrip) {
   const MemProfSchema Schema = getFullSchema();
 
   MemInfoBlock Info(/*size=*/16, /*access_count=*/7, /*alloc_timestamp=*/1000,
                     /*dealloc_timestamp=*/2000, /*alloc_cpu=*/3,
                     /*dealloc_cpu=*/4);
 
-  llvm::SmallVector<llvm::SmallVector<MemProfRecord::Frame>> AllocCallStacks = {
-      {{0x123, 1, 2, false}, {0x345, 3, 4, false}},
-      {{0x123, 1, 2, false}, {0x567, 5, 6, false}}};
+  llvm::SmallVector<llvm::SmallVector<FrameId>> AllocCallStacks = {
+      {0x123, 0x345}, {0x123, 0x567}};
 
-  llvm::SmallVector<llvm::SmallVector<MemProfRecord::Frame>> CallSites = {
-      {{0x333, 1, 2, false}, {0x777, 3, 4, true}}};
+  llvm::SmallVector<llvm::SmallVector<FrameId>> CallSites = {{0x333, 0x777}};
 
-  MemProfRecord Record;
+  IndexedMemProfRecord Record;
   for (const auto &ACS : AllocCallStacks) {
     // Use the same info block for both allocation sites.
     Record.AllocSites.emplace_back(ACS, Info);
   }
   Record.CallSites.assign(CallSites);
 
   std::string Buffer;
   llvm::raw_string_ostream OS(Buffer);
   Record.serialize(Schema, OS);
   OS.flush();
 
-  const MemProfRecord GotRecord = MemProfRecord::deserialize(
+  const IndexedMemProfRecord GotRecord = IndexedMemProfRecord::deserialize(
       Schema, reinterpret_cast<const unsigned char *>(Buffer.data()));
 
-  EXPECT_THAT(GotRecord, EqualsRecord(Record));
+  EXPECT_EQ(Record, GotRecord);
 }
 
 TEST(MemProf, SymbolizationFilter) {
   std::unique_ptr<MockSymbolizer> Symbolizer(new MockSymbolizer());
 
   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x1000},
                                                 specifier(), false))
       .Times(1) // once since we don't lookup invalid PCs repeatedly.