diff --git a/llvm/include/llvm/ProfileData/InstrProfReader.h b/llvm/include/llvm/ProfileData/InstrProfReader.h
--- a/llvm/include/llvm/ProfileData/InstrProfReader.h
+++ b/llvm/include/llvm/ProfileData/InstrProfReader.h
@@ -473,8 +473,10 @@
 using OnDiskHashTableImplV3 =
     OnDiskIterableChainedHashTable<InstrProfLookupTrait>;
 
-using MemProfHashTable =
-    OnDiskIterableChainedHashTable<memprof::MemProfRecordLookupTrait>;
+using MemProfRecordHashTable =
+    OnDiskIterableChainedHashTable<memprof::RecordLookupTrait>;
+using MemProfFrameHashTable =
+    OnDiskIterableChainedHashTable<memprof::FrameLookupTrait>;
 
 template <typename HashTableImpl>
 class InstrProfReaderItaniumRemapper;
@@ -563,8 +565,10 @@
   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;
@@ -619,10 +623,9 @@
   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,
diff --git a/llvm/include/llvm/ProfileData/InstrProfWriter.h b/llvm/include/llvm/ProfileData/InstrProfWriter.h
--- a/llvm/include/llvm/ProfileData/InstrProfWriter.h
+++ b/llvm/include/llvm/ProfileData/InstrProfWriter.h
@@ -43,7 +43,12 @@
 
   // 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;
@@ -65,9 +70,15 @@
     addRecord(std::move(I), 1, Warn);
   }
 
-  void addRecord(const GlobalValue::GUID Id,
-                 const memprof::MemProfRecord &Record,
-                 function_ref<void(Error)> Warn);
+  /// 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,
diff --git a/llvm/include/llvm/ProfileData/MemProf.h b/llvm/include/llvm/ProfileData/MemProf.h
--- a/llvm/include/llvm/ProfileData/MemProf.h
+++ b/llvm/include/llvm/ProfileData/MemProf.h
@@ -2,6 +2,7 @@
 #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"
@@ -132,182 +133,222 @@
 #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;
-
-    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;
-    }
+// A type representing the id generated by hashing the contents of the Frame.
+using FrameId = uint64_t;
+// 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;
+
+  Frame(const Frame &Other) {
+    Function = Other.Function;
+    LineOffset = Other.LineOffset;
+    Column = Other.Column;
+    IsInlineFrame = Other.IsInlineFrame;
+  }
 
-    bool operator!=(const Frame &Other) const { return !operator==(Other); }
+  Frame(uint64_t Hash, uint32_t Off, uint32_t Col, bool Inline)
+      : Function(Hash), LineOffset(Off), Column(Col), IsInlineFrame(Inline) {}
 
-    // Write the contents of the frame to the ostream \p OS.
-    void serialize(raw_ostream & OS) const {
-      using namespace support;
+  bool operator==(const Frame &Other) const {
+    return Other.Function == Function && Other.LineOffset == LineOffset &&
+           Other.Column == Column && Other.IsInlineFrame == IsInlineFrame;
+  }
 
-      endian::Writer LE(OS, little);
+  Frame &operator=(const Frame &Other) {
+    Function = Other.Function;
+    LineOffset = Other.LineOffset;
+    Column = Other.Column;
+    IsInlineFrame = Other.IsInlineFrame;
+    return *this;
+  }
 
-      // 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);
+  bool operator!=(const Frame &Other) const { return !operator==(Other); }
 
-      LE.write<uint32_t>(LineOffset);
-      LE.write<uint32_t>(Column);
-      LE.write<bool>(IsInlineFrame);
-    }
+  // Write the contents of the frame to the ostream \p OS.
+  void serialize(raw_ostream &OS) const {
+    using namespace support;
 
-    // Read a frame from char data which has been serialized as little endian.
-    static Frame deserialize(const unsigned char *Ptr) {
-      using namespace support;
+    endian::Writer LE(OS, little);
 
-      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);
-    }
+    // 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);
 
-    // 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);
-    }
+    LE.write<uint32_t>(LineOffset);
+    LE.write<uint32_t>(Column);
+    LE.write<bool>(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";
-    }
-  };
-
-  struct AllocationInfo {
-    // The dynamic calling context for the allocation.
-    llvm::SmallVector<Frame> CallStack;
-    // The statistics obtained from the runtime for the allocation.
-    PortableMemInfoBlock Info;
-
-    AllocationInfo() = default;
-    AllocationInfo(ArrayRef<Frame> CS, const MemInfoBlock &MB)
-        : CallStack(CS.begin(), CS.end()), Info(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);
-    }
+  // Read a frame from char data which has been serialized as little endian.
+  static Frame deserialize(const unsigned char *Ptr) {
+    using namespace support;
 
-    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.
-    }
+    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);
+  }
 
-    bool operator==(const AllocationInfo &Other) const {
-      if (Other.Info != Info)
-        return false;
+  // 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);
+  }
 
-      if (Other.CallStack.size() != CallStack.size())
+  // 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);
+  }
+};
+
+// 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;
+  // The statistics obtained from the runtime for the allocation.
+  PortableMemInfoBlock Info;
+
+  IndexedAllocationInfo() = default;
+  IndexedAllocationInfo(ArrayRef<FrameId> CS, const MemInfoBlock &MB)
+      : CallStack(CS.begin(), CS.end()), Info(MB) {}
+
+  // Returns the size in bytes when this allocation info struct is serialized.
+  size_t serializedSize() const {
+    return sizeof(uint64_t) + // The number of frames to serialize.
+           sizeof(FrameId) * CallStack.size() +    // The callstack frame ids.
+           PortableMemInfoBlock::serializedSize(); // The size of the payload.
+  }
+
+  bool operator==(const IndexedAllocationInfo &Other) const {
+    if (Other.Info != Info)
+      return false;
+
+    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;
+  }
 
-      for (size_t J = 0; J < Other.CallStack.size(); J++) {
-        if (Other.CallStack[J] != CallStack[J])
-          return false;
-      }
-      return true;
+  bool operator!=(const IndexedAllocationInfo &Other) const {
+    return !operator==(Other);
+  }
+};
+
+// 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;
+  }
 
-    bool operator!=(const AllocationInfo &Other) const {
-      return !operator==(Other);
+  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);
+  }
+};
 
-  // 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 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;
 
@@ -326,20 +367,65 @@
     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,
-                                   const unsigned char *Buffer);
+  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
@@ -347,18 +433,17 @@
 // 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; }
@@ -382,7 +467,7 @@
 
   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;
   }
 
@@ -390,16 +475,17 @@
   // 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;
@@ -409,7 +495,7 @@
   // 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; }
 
@@ -438,6 +524,79 @@
   }
 };
 
+// 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
 
diff --git a/llvm/include/llvm/ProfileData/RawMemProfReader.h b/llvm/include/llvm/ProfileData/RawMemProfReader.h
--- a/llvm/include/llvm/ProfileData/RawMemProfReader.h
+++ b/llvm/include/llvm/ProfileData/RawMemProfReader.h
@@ -90,6 +90,17 @@
       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)
@@ -106,6 +117,13 @@
   // 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.
@@ -123,11 +141,11 @@
   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
diff --git a/llvm/lib/ProfileData/InstrProfReader.cpp b/llvm/lib/ProfileData/InstrProfReader.cpp
--- a/llvm/lib/ProfileData/InstrProfReader.cpp
+++ b/llvm/lib/ProfileData/InstrProfReader.cpp
@@ -969,8 +969,13 @@
         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.
@@ -980,10 +985,16 @@
     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.
@@ -1030,18 +1041,41 @@
   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,
diff --git a/llvm/lib/ProfileData/InstrProfWriter.cpp b/llvm/lib/ProfileData/InstrProfWriter.cpp
--- a/llvm/lib/ProfileData/InstrProfWriter.cpp
+++ b/llvm/lib/ProfileData/InstrProfWriter.cpp
@@ -253,24 +253,49 @@
   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);
   }
 }
 
@@ -379,17 +404,21 @@
 
   // 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()));
@@ -397,20 +426,36 @@
       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.
diff --git a/llvm/lib/ProfileData/MemProf.cpp b/llvm/lib/ProfileData/MemProf.cpp
--- a/llvm/lib/ProfileData/MemProf.cpp
+++ b/llvm/lib/ProfileData/MemProf.cpp
@@ -8,16 +8,17 @@
 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);
   }
 
@@ -25,27 +26,27 @@
   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,
+                                  const unsigned char *Ptr) {
   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();
@@ -57,11 +58,11 @@
   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);
   }
@@ -69,7 +70,7 @@
   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
diff --git a/llvm/lib/ProfileData/RawMemProfReader.cpp b/llvm/lib/ProfileData/RawMemProfReader.cpp
--- a/llvm/lib/ProfileData/RawMemProfReader.cpp
+++ b/llvm/lib/ProfileData/RawMemProfReader.cpp
@@ -293,7 +293,7 @@
   // 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;
 
@@ -309,7 +309,7 @@
           "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();
@@ -317,10 +317,9 @@
       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
@@ -333,7 +332,8 @@
         // 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.
@@ -343,12 +343,13 @@
     // 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;
     }
   }
@@ -359,8 +360,8 @@
     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);
     }
@@ -405,17 +406,22 @@
 
       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,
-            // Only the last entry is not an inlined location.
-            I != NumFrames - 1);
+
+        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);
       }
     }
 
@@ -518,7 +524,11 @@
   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();
 }
diff --git a/llvm/tools/llvm-profdata/llvm-profdata.cpp b/llvm/tools/llvm-profdata/llvm-profdata.cpp
--- a/llvm/tools/llvm-profdata/llvm-profdata.cpp
+++ b/llvm/tools/llvm-profdata/llvm-profdata.cpp
@@ -266,12 +266,26 @@
       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) {
+      instrprof_error IPE = InstrProfError::take(std::move(E));
+      WC->Errors.emplace_back(make_error<InstrProfError>(IPE), Filename);
+    };
+
+    // 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;
   }
diff --git a/llvm/unittests/ProfileData/InstrProfTest.cpp b/llvm/unittests/ProfileData/InstrProfTest.cpp
--- a/llvm/unittests/ProfileData/InstrProfTest.cpp
+++ b/llvm/unittests/ProfileData/InstrProfTest.cpp
@@ -15,6 +15,7 @@
 #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"
@@ -223,15 +224,29 @@
   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>>
+        AllocFrames,
+    std::initializer_list<std::initializer_list<::llvm::memprof::FrameId>>
+        CallSiteFrames,
+    const MemInfoBlock &Block = MemInfoBlock()) {
+  llvm::memprof::IndexedMemProfRecord MR;
   for (const auto &Frames : AllocFrames)
     MR.AllocSites.emplace_back(Frames, Block);
   for (const auto &Frames : CallSiteFrames)
@@ -239,29 +254,109 @@
   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=*/
+      {
+          {0, 1},
+          {2, 3},
+      },
+      /*CallSiteFrames=*/{
+          {4, 5},
+      });
+  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 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=*/
       {
-          {{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);
+  // 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 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);
+  EXPECT_THAT_ERROR(RecordOr.takeError(), Failed());
 }
 
 TEST_F(InstrProfTest, test_memprof_merge) {
@@ -271,16 +366,21 @@
   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());
@@ -294,11 +394,27 @@
   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";
diff --git a/llvm/unittests/ProfileData/MemProfTest.cpp b/llvm/unittests/ProfileData/MemProfTest.cpp
--- a/llvm/unittests/ProfileData/MemProfTest.cpp
+++ b/llvm/unittests/ProfileData/MemProfTest.cpp
@@ -25,6 +25,9 @@
 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;
@@ -94,35 +97,21 @@
 }
 
 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);
@@ -185,8 +174,12 @@
   // 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);
@@ -202,7 +195,7 @@
   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);
@@ -222,7 +215,7 @@
   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);
@@ -233,7 +226,7 @@
   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());
@@ -275,14 +268,12 @@
                     /*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);
@@ -294,10 +285,10 @@
   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) {