[CSSPGO] Split context string to deduplicate function name used in the context.

[hoy]

Summary

Currently context strings contain a lot of duplicated function names and that significantly increase the profile size. This change split the context into a series of {name, offset, discriminator} tuples so function names used in the context can be replaced by the index into the name table and that significantly reduce the size consumed by context.

A follow-up improvement made in the compiler and profiling tools is to avoid reconstructing full context strings which is time- and memory- consuming. Instead a context vector of StringRef is adopted to represent the full context in all scenarios. As a result, the previous prevalent profile map which was implemented as a StringRef is now engineered as an unordered map keyed by SampleContext. SampleContext is reshaped to using an ArrayRef to represent a full context for CS profile. For non-CS profile, it falls back to use StringRef to represent a contextless function name. Both the ArrayRef and StringRef objects are underpinned by real array and string objects that are stored in producer buffers. For compiler, they are maintained by the sample reader. For llvm-profgen, they are maintained in ProfiledBinary and ProfileGenerator. Full context strings can be generated only in those cases of debugging and printing.

When it comes to profile format, nothing has changed to the text format, though internally CS context is implemented as a vector. Extbinary format is only changed for CS profile, with an additional SecCSNameTable section which stores all full contexts logically in the form of vector<int>, which each element as an offset points to SecNameTable. All occurrences of contexts elsewhere are redirected to using the offset of SecCSNameTable.

Testing
This is no-diff change in terms of code quality and profile content (for text profile).

For our internal large service (aka ads), the profile generation is cut to half, with a 20x smaller string-based extbinary format generated.

The compile time of ads is dropped by 25%.

[hoy]

Updating D107299: [SampleFDO] split context string to deduplicate function name used in the context.

[wmi]

Thanks Hongtao. The compile time result looks great. The patch is large. Is it possible to split it into smaller ones, SampleContext related change and SecCSNameTable related change for example?

[hoy]

In D107299#2955079, @wmi wrote:

Thanks Hongtao. The compile time result looks great. The patch is large. Is it possible to split it into smaller ones, SampleContext related change and SecCSNameTable related change for example?

Thanks for the suggestion. The separation may not be complete. The point is that the previous StringRef context is used in both reader/writer, and now we are changing it to be an ArrayRef which relies on an underlying array buffer (i.e., the CSName the reader builds up). Separating SecCSNameTable from this patch will still require the reader to build the underlying CSName table to bridge full string contexts in profile to ArrayRef contexts used elsewhere. Does this sound good to you?

[wmi]

In D107299#2955596, @hoy wrote:

In D107299#2955079, @wmi wrote:

Thanks Hongtao. The compile time result looks great. The patch is large. Is it possible to split it into smaller ones, SampleContext related change and SecCSNameTable related change for example?

Thanks for the suggestion. The separation may not be complete. The point is that the previous StringRef context is used in both reader/writer, and now we are changing it to be an ArrayRef which relies on an underlying array buffer (i.e., the CSName the reader builds up). Separating SecCSNameTable from this patch will still require the reader to build the underlying CSName table to bridge full string contexts in profile to ArrayRef contexts used elsewhere. Does this sound good to you?

I understand it is not easy to split them into two patches to be committed separately. It needs the bridge you described above which is only useful to make the temporary first part of the patch work and will be immediately thrown away after the rest of the patch is committed. That is unnecessary. Maybe just split the patches for easier review. After all the parts are ok, still commit all the parts in one shot.

[hoy]

This comment was removed by hoy.

[hoy]

Updating D107299: [CSSPGO] Split context string to deduplicate function name used in the context.

[hoy]

In D107299#2955913, @wmi wrote:

In D107299#2955596, @hoy wrote:

In D107299#2955079, @wmi wrote:

Thanks Hongtao. The compile time result looks great. The patch is large. Is it possible to split it into smaller ones, SampleContext related change and SecCSNameTable related change for example?

Thanks for the suggestion. The separation may not be complete. The point is that the previous StringRef context is used in both reader/writer, and now we are changing it to be an ArrayRef which relies on an underlying array buffer (i.e., the CSName the reader builds up). Separating SecCSNameTable from this patch will still require the reader to build the underlying CSName table to bridge full string contexts in profile to ArrayRef contexts used elsewhere. Does this sound good to you?

I understand it is not easy to split them into two patches to be committed separately. It needs the bridge you described above which is only useful to make the temporary first part of the patch work and will be immediately thrown away after the rest of the patch is committed. That is unnecessary. Maybe just split the patches for easier review. After all the parts are ok, still commit all the parts in one shot.

Sounds good. I separated this patch into three D108433 D108435 D108437. Please let me know if they are good for review.

[hoy]

Updating D107299: [CSSPGO] Split context string to deduplicate function name used in the context.

[hoy]

Updating D107299: [CSSPGO] Split context string to deduplicate function name used in the context.

llvm/include/llvm/MC/MCPseudoProbe.h

MCPseudoProbe(MCSymbol *Label, uint64_t Guid, uint64_t Index, uint64_t Type,
     assert(Attributes <= 0xFF &&
            "Probe attributes too big to encode, exceeding 2^16");
   }
 
   MCSymbol *getLabel() const { return Label; }
   void emit(MCObjectStreamer *MCOS, const MCPseudoProbe *LastProbe) const;
 };
 
+// Represents a callsite with caller function name and probe id
+using MCPseduoProbeFrameLocation = std::pair<StringRef, uint32_t>;
+
 class MCDecodedPseudoProbe : public MCPseudoProbeBase {
   uint64_t Address;
   MCDecodedPseudoProbeInlineTree *InlineTree;
 
 public:
   MCDecodedPseudoProbe(uint64_t Ad, uint64_t G, uint32_t I, PseudoProbeType K,
                        uint8_t At, MCDecodedPseudoProbeInlineTree *Tree)
       : MCPseudoProbeBase(G, I, At, static_cast<uint8_t>(K)), Address(Ad),
         InlineTree(Tree){};
 
   uint64_t getAddress() const { return Address; }
 
   void setAddress(uint64_t Addr) { Address = Addr; }
 
   MCDecodedPseudoProbeInlineTree *getInlineTreeNode() const {
     return InlineTree;
   }
 
   // Get the inlined context by traversing current inline tree backwards,
   // each tree node has its InlineSite which is taken as the context.
   // \p ContextStack is populated in root to leaf order
-  void getInlineContext(SmallVectorImpl<std::string> &ContextStack,
-                        const GUIDProbeFunctionMap &GUID2FuncMAP,
-                        bool ShowName) const;
+  void
+  getInlineContext(SmallVectorImpl<MCPseduoProbeFrameLocation> &ContextStack,
+                   const GUIDProbeFunctionMap &GUID2FuncMAP) const;
 
   // Helper function to get the string from context stack
-  std::string getInlineContextStr(const GUIDProbeFunctionMap &GUID2FuncMAP,
-                                  bool ShowName) const;
+  std::string
+  getInlineContextStr(const GUIDProbeFunctionMap &GUID2FuncMAP) const;
 
   // Print pseudo probe while disassembling
   void print(raw_ostream &OS, const GUIDProbeFunctionMap &GUID2FuncMAP,
              bool ShowName) const;
 };
 
 template <typename ProbeType, typename DerivedProbeInlineTreeType>
 class MCPseudoProbeInlineTreeBase {
public:
 
   // Helper function to populate one probe's inline stack into
   // \p InlineContextStack.
   // Current leaf location info will be added if IncludeLeaf is true
   // Example:
   //  Current probe(bar:3) inlined at foo:2 then inlined at main:1
   //  IncludeLeaf = true,  Output: [main:1, foo:2, bar:3]
   //  IncludeLeaf = false, Output: [main:1, foo:2]
-  void
-  getInlineContextForProbe(const MCDecodedPseudoProbe *Probe,
-                           SmallVectorImpl<std::string> &InlineContextStack,
-                           bool IncludeLeaf) const;
+  void getInlineContextForProbe(
+      const MCDecodedPseudoProbe *Probe,
+      SmallVectorImpl<MCPseduoProbeFrameLocation> &InlineContextStack,
 
   const AddressProbesMap &getAddress2ProbesMap() const {
     return Address2ProbesMap;
   }
 
   AddressProbesMap &getAddress2ProbesMap() { return Address2ProbesMap; }
 
   const GUIDProbeFunctionMap &getGUID2FuncDescMap() const {

llvm/include/llvm/ProfileData/ProfileCommon.h

 
 class SampleProfileSummaryBuilder final : public ProfileSummaryBuilder {
 public:
   SampleProfileSummaryBuilder(std::vector<uint32_t> Cutoffs)
       : ProfileSummaryBuilder(std::move(Cutoffs)) {}
 
   void addRecord(const sampleprof::FunctionSamples &FS,
                  bool isCallsiteSample = false);
-  std::unique_ptr<ProfileSummary> computeSummaryForProfiles(
-      const StringMap<sampleprof::FunctionSamples> &Profiles);
+  std::unique_ptr<ProfileSummary>
+  computeSummaryForProfiles(const sampleprof::SampleProfileMap &Profiles);
   std::unique_ptr<ProfileSummary> getSummary();
 };
 
 /// This is called when a count is seen in the profile.
 void ProfileSummaryBuilder::addCount(uint64_t Count) {
   TotalCount += Count;
   if (Count > MaxCount)
     MaxCount = Count;
   NumCounts++;
   CountFrequencies[Count]++;
 }
 
 } // end namespace llvm
 
 #endif // LLVM_PROFILEDATA_PROFILECOMMON_H

llvm/include/llvm/ProfileData/SampleProf.h

 #include "llvm/IR/Module.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cstdint>
+#include <list>
 #include <map>
 #include <set>
+#include <sstream>
 #include <string>
 #include <system_error>
+#include <unordered_map>
 #include <utility>
 
 namespace llvm {
 
 const std::error_category &sampleprof_category();
 
 enum class sampleprof_error {
   success = 0,

 // value of enum. Only append new ones.
 enum SecType {
   SecInValid = 0,
   SecProfSummary = 1,
   SecNameTable = 2,
   SecProfileSymbolList = 3,
   SecFuncOffsetTable = 4,
   SecFuncMetadata = 5,
+  SecCSNameTable = 6,
   // marker for the first type of profile.
   SecFuncProfileFirst = 32,
   SecLBRProfile = SecFuncProfileFirst
 };
 
 static inline std::string getSecName(SecType Type) {
   switch (Type) {
   case SecInValid:
     return "InvalidSection";
   case SecProfSummary:
     return "ProfileSummarySection";
   case SecNameTable:
     return "NameTableSection";
   case SecProfileSymbolList:
     return "ProfileSymbolListSection";
   case SecFuncOffsetTable:
     return "FuncOffsetTableSection";
   case SecFuncMetadata:
     return "FunctionMetadata";
+  case SecCSNameTable:
+    return "CSNameTableSection";
   case SecLBRProfile:
     return "LBRProfileSection";
   }
   llvm_unreachable("A SecType has no name for output");
 }
 
 // Entry type of section header table used by SampleProfileExtBinaryBaseReader
 // and SampleProfileExtBinaryBaseWriter.

 
 // Attribute of context associated with FunctionSamples
 enum ContextAttributeMask {
   ContextNone = 0x0,
   ContextWasInlined = 0x1,      // Leaf of context was inlined in previous build
   ContextShouldBeInlined = 0x2, // Leaf of context should be inlined
 };
 
+// Represents a callsite with caller function name and line location
+struct SampleContextFrame {
+  StringRef CallerName;
+  LineLocation Callsite;
+
+  SampleContextFrame() : Callsite(0, 0) {}
+
+  SampleContextFrame(StringRef CallerName, LineLocation Callsite)
+      : CallerName(CallerName), Callsite(Callsite) {}
+
+  bool operator==(const SampleContextFrame &That) const {
+    return Callsite == That.Callsite && CallerName == That.CallerName;
+  }
+
+  bool operator!=(const SampleContextFrame &That) const {
+    return !(*this == That);
+  }
+
+  std::string toString(bool OutputLineLocation) const {
+    std::ostringstream OContextStr;
+    OContextStr << CallerName.str();
+    if (OutputLineLocation) {
+      OContextStr << ":" << Callsite.LineOffset;
+      if (Callsite.Discriminator)
+        OContextStr << "." << Callsite.Discriminator;
+    }
+    return OContextStr.str();
+  }
+};
+
+static inline hash_code hash_value(const SampleContextFrame &arg) {
+  return hash_combine(arg.CallerName, arg.Callsite.LineOffset,
+                      arg.Callsite.Discriminator);
+}
+
+using SampleContextFrameVector = SmallVector<SampleContextFrame, 10>;
+using SampleContextFrames = ArrayRef<SampleContextFrame>;
+
+struct SampleContextFrameHash {
+  uint64_t operator()(const SampleContextFrameVector &S) const {
+    return hash_combine_range(S.begin(), S.end());
+  }
+};
+
 // Sample context for FunctionSamples. It consists of the calling context,
 // the function name and context state. Internally sample context is represented
-// using StringRef, which is also the input for constructing a `SampleContext`.
+// using ArrayRef, which is also the input for constructing a `SampleContext`.
 // It can accept and represent both full context string as well as context-less
 // function name.
-// Example of full context string (note the wrapping `[]`):
-//    `[main:3 @ _Z5funcAi:1 @ _Z8funcLeafi]`
-// Example of context-less function name (same as AutoFDO):
-//    `_Z8funcLeafi`
+// For a CS profile, a full context vector can look like:
+//    `main:3 _Z5funcAi:1 _Z8funcLeafi`
+// For a base CS profile without calling context, the context vector should only
+// contain the leaf frame name.
+// For a non-CS profile, the context vector should be empty.
 class SampleContext {
 public:
   SampleContext() : State(UnknownContext), Attributes(ContextNone) {}
-  SampleContext(StringRef ContextStr, ContextStateMask CState = UnknownContext)
-      : Attributes(ContextNone) {
-    setContext(ContextStr, CState);
-  }
-
-  // Promote context by removing top frames (represented by `ContextStrToRemove`).
-  // Note that with string representation of context, the promotion is effectively
-  // a substr operation with `ContextStrToRemove` removed from left.
-  void promoteOnPath(StringRef ContextStrToRemove) {
-    assert(FullContext.startswith(ContextStrToRemove));
 
-    // Remove leading context and frame separator " @ ".
-    FullContext = FullContext.substr(ContextStrToRemove.size() + 3);
-    CallingContext = CallingContext.substr(ContextStrToRemove.size() + 3);
-  }
+  SampleContext(StringRef Name)
+      : Name(Name), State(UnknownContext), Attributes(ContextNone) {}
 
-  // Split the top context frame (left-most substr) from context.
-  static std::pair<StringRef, StringRef>
-  splitContextString(StringRef ContextStr) {
-    return ContextStr.split(" @ ");
+  SampleContext(SampleContextFrames Context,
+                ContextStateMask CState = RawContext)
+      : Attributes(ContextNone) {
+    assert(!Context.empty() && "Context is empty");
+    setContext(Context, CState);
   }
 
-  // Split the leaf context frame (right-most substr) from context.
-  static std::pair<StringRef, StringRef>
-  rsplitContextString(StringRef ContextStr) {
-    auto ContextSplit = ContextStr.rsplit(" @ ");
-    if (ContextSplit.second.empty()) {
-      std::swap(ContextSplit.first, ContextSplit.second);
+  // Give a context string, decode and populate internal states like
+  // Function name, Calling context and context state. Example of input
+  // `ContextStr`: `[main:3 @ _Z5funcAi:1 @ _Z8funcLeafi]`
+  SampleContext(StringRef ContextStr,
+                std::list<SampleContextFrameVector> &CSNameTable,
+                ContextStateMask CState = RawContext)
+      : Attributes(ContextNone) {
+    assert(!ContextStr.empty());
+    // Note that `[]` wrapped input indicates a full context string, otherwise
+    // it's treated as context-less function name only.
+    bool HasContext = ContextStr.startswith("[");
+    if (!HasContext) {
+      State = UnknownContext;
+      Name = ContextStr;
+    } else {
+      // Remove encapsulating '[' and ']' if any
+      ContextStr = ContextStr.substr(1, ContextStr.size() - 2);
+      CSNameTable.emplace_back();
+      SampleContextFrameVector &Context = CSNameTable.back();
+      /// Create a context vector from a given context string and save it in
+      /// `Context`.
+      StringRef ContextRemain = ContextStr;
+      StringRef ChildContext;
+      StringRef CalleeName;
+      while (!ContextRemain.empty()) {
+        auto ContextSplit = ContextRemain.split(" @ ");
+        ChildContext = ContextSplit.first;
+        ContextRemain = ContextSplit.second;
+        LineLocation CallSiteLoc(0, 0);
+        decodeContextString(ChildContext, CalleeName, CallSiteLoc);
+        Context.emplace_back(CalleeName, CallSiteLoc);
+      }
+
+      setContext(Context, CState);
     }
-    return ContextSplit;
   }
 
-  // Reconstruct a new context with the last k frames, return the context-less
-  // name if K = 1
-  StringRef getContextWithLastKFrames(uint32_t K) {
-    if (K == 1)
-      return getNameWithoutContext();
-
-    size_t I = FullContext.size();
-    while (K--) {
-      I = FullContext.find_last_of(" @ ", I);
-      if (I == StringRef::npos)
-        return FullContext;
-      I -= 2;
-    }
-    return FullContext.slice(I + 3, StringRef::npos);
+  // Promote context by removing top frames with the length of
+  // `ContextFramesToRemove`. Note that with array representation of context,
+  // the promotion is effectively a slice operation with first
+  // `ContextFramesToRemove` elements removed from left.
+  void promoteOnPath(uint32_t ContextFramesToRemove) {
+    assert(ContextFramesToRemove <= FullContext.size() &&
+           "Cannot remove more than the whole context");
+    FullContext = FullContext.drop_front(ContextFramesToRemove);
   }
 
   // Decode context string for a frame to get function name and location.
   // `ContextStr` is in the form of `FuncName:StartLine.Discriminator`.
   static void decodeContextString(StringRef ContextStr, StringRef &FName,
                                   LineLocation &LineLoc) {
     // Get function name
     auto EntrySplit = ContextStr.split(':');
if (!EntrySplit.second.empty()) {
       LineLoc.LineOffset = LineOffset;
 
       // Get discriminator
       if (!LocSplit.second.empty())
         LocSplit.second.getAsInteger(10, LineLoc.Discriminator);
     }
   }
 
-  operator StringRef() const { return FullContext; }
+  operator SampleContextFrames() const { return FullContext; }
   bool hasAttribute(ContextAttributeMask A) { return Attributes & (uint32_t)A; }
   void setAttribute(ContextAttributeMask A) { Attributes |= (uint32_t)A; }
   uint32_t getAllAttributes() { return Attributes; }
   void setAllAttributes(uint32_t A) { Attributes = A; }
   bool hasState(ContextStateMask S) { return State & (uint32_t)S; }
   void setState(ContextStateMask S) { State |= (uint32_t)S; }
   void clearState(ContextStateMask S) { State &= (uint32_t)~S; }
   bool hasContext() const { return State != UnknownContext; }
-  bool isBaseContext() const { return CallingContext.empty(); }
-  StringRef getNameWithoutContext() const { return Name; }
-  StringRef getCallingContext() const { return CallingContext; }
-  StringRef getNameWithContext() const { return FullContext; }
+  bool isBaseContext() const { return FullContext.size() == 1; }
+  StringRef getName() const { return Name; }
+  SampleContextFrames getContextFrames() const { return FullContext; }
 
-private:
-  // Give a context string, decode and populate internal states like
-  // Function name, Calling context and context state. Example of input
-  // `ContextStr`: `[main:3 @ _Z5funcAi:1 @ _Z8funcLeafi]`
-  void setContext(StringRef ContextStr, ContextStateMask CState) {
-    assert(!ContextStr.empty());
-    // Note that `[]` wrapped input indicates a full context string, otherwise
-    // it's treated as context-less function name only.
-    bool HasContext = ContextStr.startswith("[");
-    if (!HasContext && CState == UnknownContext) {
-      State = UnknownContext;
-      Name = FullContext = ContextStr;
-    } else {
-      // Assume raw context profile if unspecified
-      if (CState == UnknownContext)
-        State = RawContext;
-      else
-        State = CState;
+  static std::string getContextString(SampleContextFrames Context,
+                                      bool IncludeLeafLineLocation = false) {
+    std::ostringstream OContextStr;
+    for (uint32_t I = 0; I < Context.size(); I++) {
+      if (OContextStr.str().size()) {
+        OContextStr << " @ ";
+      }
+      OContextStr << Context[I].toString(I != Context.size() - 1 ||
+                                         IncludeLeafLineLocation);
+    }
+    return OContextStr.str();
+  }
+
+  std::string toString() const {
+    if (!hasContext())
+      return Name.str();
+    return getContextString(FullContext, false);
+  }
+
+  uint64_t getHashCode() const {
+    return hasContext() ? hash_value(getContextFrames())
+                        : hash_value(getName());
+  }
+
+  /// Set the name of the function.
+  void setName(StringRef FunctionName) {
+    assert(FullContext.empty() &&
+           "setName should only be called for non-CS profile");
+    Name = FunctionName;
+  }
+
+  void setContext(SampleContextFrames Context,
+                  ContextStateMask CState = RawContext) {
+    assert(CState != UnknownContext);
+    FullContext = Context;
+    Name = Context.back().CallerName;
+  }
 
-      // Remove encapsulating '[' and ']' if any
-      if (HasContext)
-        FullContext = ContextStr.substr(1, ContextStr.size() - 2);
-      else
-        FullContext = ContextStr;
-
-      // Caller is to the left of callee in context string
-      auto NameContext = FullContext.rsplit(" @ ");
-      if (NameContext.second.empty()) {
-        Name = NameContext.first;
-        CallingContext = NameContext.second;
-      } else {
-        Name = NameContext.second;
-        CallingContext = NameContext.first;
-      }
+  bool operator==(const SampleContext &That) const {
+    return State == That.State && Name == That.Name &&
+           FullContext == That.FullContext;
+  }
+
+  bool operator!=(const SampleContext &That) const { return !(*this == That); }
+
+  bool operator<(const SampleContext &That) const {
+    if (State != That.State)
+      return State < That.State;
+
+    if (!hasContext()) {
+      return (Name.compare(That.Name)) == -1;
+    }
+
+    uint64_t I = 0;
+    while (I < std::min(FullContext.size(), That.FullContext.size())) {
+      auto &Context1 = FullContext[I];
+      auto &Context2 = That.FullContext[I];
+      auto V = Context1.CallerName.compare(Context2.CallerName);
+      if (V)
+        return V == -1;
+      if (Context1.Callsite != Context2.Callsite)
+        return Context1.Callsite < Context2.Callsite;
+      I++;
+    }
+
+    return FullContext.size() < That.FullContext.size();
+
+  struct Hash {
+    uint64_t operator()(const SampleContext &Context) const {
+      return Context.getHashCode();
     }
+  };
+
+  bool IsPrefixOf(const SampleContext &That) const {
+    auto ThisContext = FullContext;
+    auto ThatContext = That.FullContext;
+    if (ThatContext.size() < ThisContext.size())
+      return false;
+    ThatContext = ThatContext.take_front(ThisContext.size());
+    // Compare Leaf frame first
+    if (ThisContext.back().CallerName != ThatContext.back().CallerName)
+      return false;
+    // Compare leading context
+    return ThisContext.drop_back() == ThatContext.drop_back();
   }
 
-  // Full context string including calling context and leaf function name
-  StringRef FullContext;
-  // Function name for the associated sample profile
+private:
+  /// Mangled name of the function.
   StringRef Name;
-  // Calling context (leaf function excluded) for the associated sample profile
-  StringRef CallingContext;
+  // Full context including calling context and leaf function name
+  SampleContextFrames FullContext;
   // State of the associated sample profile
   uint32_t State;
   // Attribute of the associated sample profile
   uint32_t Attributes;
 };
 
+static inline hash_code hash_value(const SampleContext &arg) {
+  return arg.hasContext() ? hash_value(arg.getContextFrames())
+                          : hash_value(arg.getName());
+}
+
 class FunctionSamples;
 class SampleProfileReaderItaniumRemapper;
 
 using BodySampleMap = std::map<LineLocation, SampleRecord>;
 // NOTE: Using a StringMap here makes parsed profiles consume around 17% more
 // memory, which is *very* significant for large profiles.
 using FunctionSamplesMap = std::map<std::string, FunctionSamples, std::less<>>;
 using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>;
for (const auto &C : getCallsiteSamples())
         MaxCount = std::max(MaxCount, F.second.getMaxCountInside());
     return MaxCount;
   }
 
   /// Merge the samples in \p Other into this one.
   /// Optionally scale samples by \p Weight.
   sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
     sampleprof_error Result = sampleprof_error::success;
-    Name = Other.getName();
     if (!GUIDToFuncNameMap)
       GUIDToFuncNameMap = Other.GUIDToFuncNameMap;
-    if (Context.getNameWithContext().empty())
+    if (Context.getName().empty())
       Context = Other.getContext();
     if (FunctionHash == 0) {
       // Set the function hash code for the target profile.
       FunctionHash = Other.getFunctionHash();
     } else if (FunctionHash != Other.getFunctionHash()) {
       // The two profiles coming with different valid hash codes indicates
       // either:
       // 1. They are same-named static functions from different compilation
void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S,
                             uint64_t Threshold) const {
     if (TotalSamples <= Threshold)
       return;
     auto isDeclaration = [](const Function *F) {
       return !F || F->isDeclaration();
     };
     if (isDeclaration(SymbolMap.lookup(getFuncName()))) {
       // Add to the import list only when it's defined out of module.
-      S.insert(getGUID(Name));
+      S.insert(getGUID(getName()));
     }
     // Import hot CallTargets, which may not be available in IR because full
     // profile annotation cannot be done until backend compilation in ThinLTO.
     for (const auto &BS : BodySamples)
       for (const auto &TS : BS.second.getCallTargets())
         if (TS.getValue() > Threshold) {
           const Function *Callee = SymbolMap.lookup(getFuncName(TS.getKey()));
           if (isDeclaration(Callee))
             S.insert(getGUID(TS.getKey()));
         }
     for (const auto &CS : CallsiteSamples)
       for (const auto &NameFS : CS.second)
         NameFS.second.findInlinedFunctions(S, SymbolMap, Threshold);
   }
 
   /// Set the name of the function.
-  void setName(StringRef FunctionName) { Name = FunctionName; }
+  void setName(StringRef FunctionName) { Context.setName(FunctionName); }
 
   /// Return the function name.
-  StringRef getName() const { return Name; }
-
-  /// Return function name with context.
-  StringRef getNameWithContext() const {
-    return FunctionSamples::ProfileIsCS ? Context.getNameWithContext() : Name;
-  }
+  StringRef getName() const { return Context.getName(); }
 
   /// Return the original function name.
-  StringRef getFuncName() const { return getFuncName(Name); }
+  StringRef getFuncName() const { return getFuncName(getName()); }
 
   void setFunctionHash(uint64_t Hash) { FunctionHash = Hash; }
 
   uint64_t getFunctionHash() const { return FunctionHash; }
 
   /// Return the canonical name for a function, taking into account
   /// suffix elision policy attributes.
   static StringRef getCanonicalFnName(const Function &F) {
static uint64_t getGUID(StringRef Name) {
     return UseMD5 ? std::stoull(Name.data()) : Function::getGUID(Name);
   }
 
   // Find all the names in the current FunctionSamples including names in
   // all the inline instances and names of call targets.
   void findAllNames(DenseSet<StringRef> &NameSet) const;
 
 private:
-  /// Mangled name of the function.
-  StringRef Name;
-
   /// CFG hash value for the function.
   uint64_t FunctionHash = 0;
 
   /// Calling context for function profile
   mutable SampleContext Context;
 
   /// Total number of samples collected inside this function.
   ///
private:
   /// map will contain two entries.  One for all the samples collected
   /// in the call to bar() at line offset 1, the other for all the samples
   /// collected in the call to baz() at line offset 8.
   CallsiteSampleMap CallsiteSamples;
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS);
 
-using NameFunctionSamples = std::pair<StringRef, const FunctionSamples *>;
+using SampleProfileMap =
+    std::unordered_map<SampleContext, FunctionSamples, SampleContext::Hash>;
 
-void sortFuncProfiles(const StringMap<FunctionSamples> &ProfileMap,
+using NameFunctionSamples = std::pair<SampleContext, const FunctionSamples *>;
+
+void sortFuncProfiles(const SampleProfileMap &ProfileMap,
                       std::vector<NameFunctionSamples> &SortedProfiles);
 
 /// Sort a LocationT->SampleT map by LocationT.
 ///
 /// It produces a sorted list of <LocationT, SampleT> records by ascending
 /// order of LocationT.
 template <class LocationT, class SampleT> class SampleSorter {
 public:
private:
   SamplesWithLocList V;
 };
 
 /// SampleContextTrimmer impelements helper functions to trim, merge cold
 /// context profiles. It also supports context profile canonicalization to make
 /// sure ProfileMap's key is consistent with FunctionSample's name/context.
 class SampleContextTrimmer {
 public:
-  SampleContextTrimmer(StringMap<FunctionSamples> &Profiles)
-      : ProfileMap(Profiles){};
+  SampleContextTrimmer(SampleProfileMap &Profiles) : ProfileMap(Profiles){};
   // Trim and merge cold context profile when requested.
   void trimAndMergeColdContextProfiles(uint64_t ColdCountThreshold,
                                        bool TrimColdContext,
                                        bool MergeColdContext,
                                        uint32_t ColdContextFrameLength);
   // Canonicalize context profile name and attributes.
   void canonicalizeContextProfiles();
 
 private:
-  StringMap<FunctionSamples> &ProfileMap;
+  SampleProfileMap &ProfileMap;
 };
 
 /// ProfileSymbolList records the list of function symbols shown up
 /// in the binary used to generate the profile. It is useful to
 /// to discriminate a function being so cold as not to shown up
 /// in the profile and a function newly added.
 class ProfileSymbolList {
 public:
private:
   // writing it into profile. The variable is unused when the symbol
   // list is read from an existing profile.
   bool ToCompress = false;
   DenseSet<StringRef> Syms;
   BumpPtrAllocator Allocator;
 };
 
 } // end namespace sampleprof
+
+using namespace sampleprof;
+// Provide DenseMapInfo for SampleContext.
+template <> struct DenseMapInfo<SampleContext> {
+  static inline SampleContext getEmptyKey() { return SampleContext(); }
+
+  static inline SampleContext getTombstoneKey() { return SampleContext("@"); }
+
+  static unsigned getHashValue(const SampleContext &Val) {
+    return Val.getHashCode();
+  }
+
+  static bool isEqual(const SampleContext &LHS, const SampleContext &RHS) {
+    return LHS == RHS;
+  }
+};
 } // end namespace llvm
 
 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H

llvm/include/llvm/ProfileData/SampleProfReader.h

 #include "llvm/ProfileData/SampleProf.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Discriminator.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/SymbolRemappingReader.h"
 #include <algorithm>
 #include <cstdint>
+#include <list>
 #include <memory>
 #include <string>
 #include <system_error>
 #include <unordered_set>
 #include <vector>
 
 namespace llvm {
 
if (Remapper)
       Remapper->applyRemapping(Ctx);
     FunctionSamples::UseMD5 = useMD5();
     return sampleprof_error::success;
   }
 
   /// The implementaion to read sample profiles from the associated file.
   virtual std::error_code readImpl() = 0;
 
-  /// Print the profile for \p FName on stream \p OS.
-  void dumpFunctionProfile(StringRef FName, raw_ostream &OS = dbgs());
+  /// Print the profile for \p FContext on stream \p OS.
+  void dumpFunctionProfile(SampleContext FContext, raw_ostream &OS = dbgs());
 
   /// Collect functions with definitions in Module M. For reader which
   /// support loading function profiles on demand, return true when the
   /// reader has been given a module. Always return false for reader
   /// which doesn't support loading function profiles on demand.
   virtual bool collectFuncsFromModule() { return false; }
 
   /// Print all the profiles on stream \p OS.
if (Remapper) {
         if (It != Profiles.end())
           return &It->second;
       }
     }
     return nullptr;
   }
 
   /// Return all the profiles.
-  StringMap<FunctionSamples> &getProfiles() { return Profiles; }
+  SampleProfileMap &getProfiles() { return Profiles; }
 
   /// Report a parse error message.
   void reportError(int64_t LineNumber, const Twine &Msg) const {
     Ctx.diagnose(DiagnosticInfoSampleProfile(Buffer->getBufferIdentifier(),
                                              LineNumber, Msg));
   }
 
   /// Create a sample profile reader appropriate to the file format.
public:
   void setModule(const Module *Mod) { M = Mod; }
 
 protected:
   /// Map every function to its associated profile.
   ///
   /// The profile of every function executed at runtime is collected
   /// in the structure FunctionSamples. This maps function objects
   /// to their corresponding profiles.
-  StringMap<FunctionSamples> Profiles;
+  SampleProfileMap Profiles;
 
   /// LLVM context used to emit diagnostics.
   LLVMContext &Ctx;
 
   /// Memory buffer holding the profile file.
   std::unique_ptr<MemoryBuffer> Buffer;
 
   /// Extra name buffer holding names created on demand.
public:
   /// Read and validate the file header.
   std::error_code readHeader() override { return sampleprof_error::success; }
 
   /// Read sample profiles from the associated file.
   std::error_code readImpl() override;
 
   /// Return true if \p Buffer is in the format supported by this class.
   static bool hasFormat(const MemoryBuffer &Buffer);
+
+private:
+  /// CSNameTable is used to save full context vectors. This serves as an
+  /// underlying immutable buffer for all clients.
+  std::list<SampleContextFrameVector> CSNameTable;
 };
 
 class SampleProfileReaderBinary : public SampleProfileReader {
 public:
   SampleProfileReaderBinary(std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
                             SampleProfileFormat Format = SPF_None)
       : SampleProfileReader(std::move(B), C, Format) {}
 
protected:
   /// Points to the end of the buffer.
   const uint8_t *End = nullptr;
 
   /// Function name table.
   std::vector<StringRef> NameTable;
 
   /// Read a string indirectly via the name table.
   virtual ErrorOr<StringRef> readStringFromTable();
+  virtual ErrorOr<SampleContext> readSampleContextFromTable();
 
 private:
   std::error_code readSummaryEntry(std::vector<ProfileSummaryEntry> &Entries);
   virtual std::error_code verifySPMagic(uint64_t Magic) = 0;
 };
 
 class SampleProfileReaderRawBinary : public SampleProfileReaderBinary {
 private:
protected:
   std::error_code readSecHdrTableEntry(uint32_t Idx);
   std::error_code readSecHdrTable();
 
   std::error_code readFuncMetadata(bool ProfileHasAttribute);
   std::error_code readFuncOffsetTable();
   std::error_code readFuncProfiles();
   std::error_code readMD5NameTable();
   std::error_code readNameTableSec(bool IsMD5);
+  std::error_code readCSNameTableSec();
   std::error_code readProfileSymbolList();
 
   virtual std::error_code readHeader() override;
   virtual std::error_code verifySPMagic(uint64_t Magic) override = 0;
   virtual std::error_code readOneSection(const uint8_t *Start, uint64_t Size,
                                          const SecHdrTableEntry &Entry);
   // placeholder for subclasses to dispatch their own section readers.
   virtual std::error_code readCustomSection(const SecHdrTableEntry &Entry) = 0;
   virtual ErrorOr<StringRef> readStringFromTable() override;
+  virtual ErrorOr<SampleContext> readSampleContextFromTable() override;
+  ErrorOr<SampleContextFrames> readContextFromTable();
 
   std::unique_ptr<ProfileSymbolList> ProfSymList;
 
-  /// The table mapping from function name to the offset of its FunctionSample
-  /// towards file start.
-  DenseMap<StringRef, uint64_t> FuncOffsetTable;
+  /// The table mapping from function context to the offset of its
+  /// FunctionSample towards file start.
+  DenseMap<SampleContext, uint64_t> FuncOffsetTable;
   /// The set containing the functions to use when compiling a module.
   DenseSet<StringRef> FuncsToUse;
 
   /// Use fixed length MD5 instead of ULEB128 encoding so NameTable doesn't
   /// need to be read in up front and can be directly accessed using index.
   bool FixedLengthMD5 = false;
   /// The starting address of NameTable containing fixed length MD5.
   const uint8_t *MD5NameMemStart = nullptr;
 
   /// If MD5 is used in NameTable section, the section saves uint64_t data.
   /// The uint64_t data has to be converted to a string and then the string
   /// will be used to initialize StringRef in NameTable.
   /// Note NameTable contains StringRef so it needs another buffer to own
   /// the string data. MD5StringBuf serves as the string buffer that is
   /// referenced by NameTable (vector of StringRef). We make sure
   /// the lifetime of MD5StringBuf is not shorter than that of NameTable.
   std::unique_ptr<std::vector<std::string>> MD5StringBuf;
 
+  /// CSNameTable is used to save full context vectors. This serves as an
+  /// underlying immutable buffer for all clients.
+  std::unique_ptr<const std::vector<SampleContextFrameVector>> CSNameTable;
+
   /// If SkipFlatProf is true, skip the sections with
   /// SecFlagFlat flag.
   bool SkipFlatProf = false;
 
 public:
   SampleProfileReaderExtBinaryBase(std::unique_ptr<MemoryBuffer> B,
                                    LLVMContext &C, SampleProfileFormat Format)
       : SampleProfileReaderBinary(std::move(B), C, Format) {}

llvm/include/llvm/ProfileData/SampleProfWriter.h

public:
   /// Write sample profiles in \p S.
   ///
   /// \returns status code of the file update operation.
   virtual std::error_code writeSample(const FunctionSamples &S) = 0;
 
   /// Write all the sample profiles in the given map of samples.
   ///
   /// \returns status code of the file update operation.
-  virtual std::error_code write(const StringMap<FunctionSamples> &ProfileMap);
+  virtual std::error_code write(const SampleProfileMap &ProfileMap);
 
   raw_ostream &getOutputStream() { return *OutputStream; }
 
   /// Profile writer factory.
   ///
   /// Create a new file writer based on the value of \p Format.
   static ErrorOr<std::unique_ptr<SampleProfileWriter>>
   create(StringRef Filename, SampleProfileFormat Format);
public:
   virtual void setPartialProfile() {}
   virtual void resetSecLayout(SectionLayout SL) {}
 
 protected:
   SampleProfileWriter(std::unique_ptr<raw_ostream> &OS)
       : OutputStream(std::move(OS)) {}
 
   /// Write a file header for the profile file.
-  virtual std::error_code
-  writeHeader(const StringMap<FunctionSamples> &ProfileMap) = 0;
+  virtual std::error_code writeHeader(const SampleProfileMap &ProfileMap) = 0;
 
   // Write function profiles to the profile file.
-  virtual std::error_code
-  writeFuncProfiles(const StringMap<FunctionSamples> &ProfileMap);
+  virtual std::error_code writeFuncProfiles(const SampleProfileMap &ProfileMap);
 
   /// Output stream where to emit the profile to.
   std::unique_ptr<raw_ostream> OutputStream;
 
   /// Profile summary.
   std::unique_ptr<ProfileSummary> Summary;
 
   /// Compute summary for this profile.
-  void computeSummary(const StringMap<FunctionSamples> &ProfileMap);
+  void computeSummary(const SampleProfileMap &ProfileMap);
 
   /// Profile format.
   SampleProfileFormat Format = SPF_None;
 };
 
 /// Sample-based profile writer (text format).
 class SampleProfileWriterText : public SampleProfileWriter {
 public:
   std::error_code writeSample(const FunctionSamples &S) override;
 
 protected:
   SampleProfileWriterText(std::unique_ptr<raw_ostream> &OS)
       : SampleProfileWriter(OS), Indent(0) {}
 
-  std::error_code
-  writeHeader(const StringMap<FunctionSamples> &ProfileMap) override {
+  std::error_code writeHeader(const SampleProfileMap &ProfileMap) override {
     return sampleprof_error::success;
   }
 
 private:
   /// Indent level to use when writing.
   ///
   /// This is used when printing inlined callees.
   unsigned Indent;
 
   friend ErrorOr<std::unique_ptr<SampleProfileWriter>>
   SampleProfileWriter::create(std::unique_ptr<raw_ostream> &OS,
                               SampleProfileFormat Format);
 };
 
 /// Sample-based profile writer (binary format).
 class SampleProfileWriterBinary : public SampleProfileWriter {
 public:
   SampleProfileWriterBinary(std::unique_ptr<raw_ostream> &OS)
       : SampleProfileWriter(OS) {}
 
   virtual std::error_code writeSample(const FunctionSamples &S) override;
 
 protected:
+  virtual MapVector<StringRef, uint32_t> &getNameTable() { return NameTable; }
   virtual std::error_code writeMagicIdent(SampleProfileFormat Format);
   virtual std::error_code writeNameTable();
   virtual std::error_code
-  writeHeader(const StringMap<FunctionSamples> &ProfileMap) override;
+  writeHeader(const SampleProfileMap &ProfileMap) override;
   std::error_code writeSummary();
-  std::error_code writeNameIdx(StringRef FName, bool IsContextName = false);
+  virtual std::error_code writeContextIdx(const SampleContext &Context);
+  std::error_code writeNameIdx(StringRef FName);
   std::error_code writeBody(const FunctionSamples &S);
-  inline void stablizeNameTable(std::set<StringRef> &V);
+  inline void stablizeNameTable(MapVector<StringRef, uint32_t> &NameTable,
+                                std::set<StringRef> &V);
 
   MapVector<StringRef, uint32_t> NameTable;
-  std::unordered_set<std::string> BracketedContextStr;
 
-  void addName(StringRef FName, bool IsContextName = false);
+  void addName(StringRef FName);
+  virtual void addContext(const SampleContext &Context);
   void addNames(const FunctionSamples &S);
 
 private:
   friend ErrorOr<std::unique_ptr<SampleProfileWriter>>
   SampleProfileWriter::create(std::unique_ptr<raw_ostream> &OS,
                               SampleProfileFormat Format);
 };
 
 class SampleProfileWriterRawBinary : public SampleProfileWriterBinary {
   using SampleProfileWriterBinary::SampleProfileWriterBinary;
 };
 
 const std::array<SmallVector<SecHdrTableEntry, 8>, NumOfLayout>
     ExtBinaryHdrLayoutTable = {
         // Note that SecFuncOffsetTable section is written after SecLBRProfile
         // in the profile, but is put before SecLBRProfile in SectionHdrLayout.
         // This is because sample reader follows the order in SectionHdrLayout
         // to read each section. To read function profiles on demand, sample
         // reader need to get the offset of each function profile first.
         //
         // DefaultLayout
         SmallVector<SecHdrTableEntry, 8>({{SecProfSummary, 0, 0, 0, 0},
                                           {SecNameTable, 0, 0, 0, 0},
+                                          {SecCSNameTable, 0, 0, 0, 0},
                                           {SecFuncOffsetTable, 0, 0, 0, 0},
                                           {SecLBRProfile, 0, 0, 0, 0},
                                           {SecProfileSymbolList, 0, 0, 0, 0},
                                           {SecFuncMetadata, 0, 0, 0, 0}}),
         // CtxSplitLayout
         SmallVector<SecHdrTableEntry, 8>({{SecProfSummary, 0, 0, 0, 0},
                                           {SecNameTable, 0, 0, 0, 0},
                                           // profile with context
                                           // for next two sections
                                           {SecFuncOffsetTable, 0, 0, 0, 0},
                                           {SecLBRProfile, 0, 0, 0, 0},
                                           // profile without context
                                           // for next two sections
                                           {SecFuncOffsetTable, 0, 0, 0, 0},
                                           {SecLBRProfile, 0, 0, 0, 0},
                                           {SecProfileSymbolList, 0, 0, 0, 0},
                                           {SecFuncMetadata, 0, 0, 0, 0}}),
 };
 
 class SampleProfileWriterExtBinaryBase : public SampleProfileWriterBinary {
   using SampleProfileWriterBinary::SampleProfileWriterBinary;
 public:
-  virtual std::error_code
-  write(const StringMap<FunctionSamples> &ProfileMap) override;
+  virtual std::error_code write(const SampleProfileMap &ProfileMap) override;
 
   virtual void setToCompressAllSections() override;
   void setToCompressSection(SecType Type);
   virtual std::error_code writeSample(const FunctionSamples &S) override;
 
   // Set to use MD5 to represent string in NameTable.
   virtual void setUseMD5() override {
     UseMD5 = true;
for (auto &Entry : SectionHdrLayout) {
         addSecFlag(Entry, Flag);
     }
   }
   template <class SecFlagType>
   void addSectionFlag(uint32_t SectionIdx, SecFlagType Flag) {
     addSecFlag(SectionHdrLayout[SectionIdx], Flag);
   }
 
+  virtual void addContext(const SampleContext &Context) override;
+
   // placeholder for subclasses to dispatch their own section writers.
   virtual std::error_code writeCustomSection(SecType Type) = 0;
   // Verify the SecLayout is supported by the format.
   virtual void verifySecLayout(SectionLayout SL) = 0;
 
   // specify the order to write sections.
-  virtual std::error_code
-  writeSections(const StringMap<FunctionSamples> &ProfileMap) = 0;
+  virtual std::error_code writeSections(const SampleProfileMap &ProfileMap) = 0;
 
   // Dispatch section writer for each section. \p LayoutIdx is the sequence
   // number indicating where the section is located in SectionHdrLayout.
-  virtual std::error_code
-  writeOneSection(SecType Type, uint32_t LayoutIdx,
-                  const StringMap<FunctionSamples> &ProfileMap);
+  virtual std::error_code writeOneSection(SecType Type, uint32_t LayoutIdx,
+                                          const SampleProfileMap &ProfileMap);
 
   // Helper function to write name table.
   virtual std::error_code writeNameTable() override;
+  virtual std::error_code
+  writeContextIdx(const SampleContext &Context) override;
+  std::error_code writeCSNameIdx(const SampleContext &Context);
+  std::error_code writeCSNameTableSection();
 
-  std::error_code writeFuncMetadata(const StringMap<FunctionSamples> &Profiles);
+  std::error_code writeFuncMetadata(const SampleProfileMap &Profiles);
 
   // Functions to write various kinds of sections.
-  std::error_code
-  writeNameTableSection(const StringMap<FunctionSamples> &ProfileMap);
+  std::error_code writeNameTableSection(const SampleProfileMap &ProfileMap);
   std::error_code writeFuncOffsetTable();
   std::error_code writeProfileSymbolListSection();
 
   SectionLayout SecLayout = DefaultLayout;
   // Specifiy the order of sections in section header table. Note
   // the order of sections in SecHdrTable may be different that the
   // order in SectionHdrLayout. sample Reader will follow the order
   // in SectionHdrLayout to read each section.
   SmallVector<SecHdrTableEntry, 8> SectionHdrLayout =
       ExtBinaryHdrLayoutTable[DefaultLayout];
 
   // Save the start of SecLBRProfile so we can compute the offset to the
   // start of SecLBRProfile for each Function's Profile and will keep it
   // in FuncOffsetTable.
   uint64_t SecLBRProfileStart = 0;
 
 private:
   void allocSecHdrTable();
   std::error_code writeSecHdrTable();
   virtual std::error_code
-  writeHeader(const StringMap<FunctionSamples> &ProfileMap) override;
+  writeHeader(const SampleProfileMap &ProfileMap) override;
   std::error_code compressAndOutput();
 
   // We will swap the raw_ostream held by LocalBufStream and that
   // held by OutputStream if we try to add a section which needs
   // compression. After the swap, all the data written to output
   // will be temporarily buffered into the underlying raw_string_ostream
   // originally held by LocalBufStream. After the data writing for the
   // section is completed, compress the data in the local buffer,
   // swap the raw_ostream back and write the compressed data to the
   // real output.
   std::unique_ptr<raw_ostream> LocalBufStream;
   // The location where the output stream starts.
   uint64_t FileStart;
   // The location in the output stream where the SecHdrTable should be
   // written to.
   uint64_t SecHdrTableOffset;
   // The table contains SecHdrTableEntry entries in order of how they are
   // populated in the writer. It may be different from the order in
   // SectionHdrLayout which specifies the sequence in which sections will
   // be read.
   std::vector<SecHdrTableEntry> SecHdrTable;
 
-  // FuncOffsetTable maps function name to its profile offset in SecLBRProfile
-  // section. It is used to load function profile on demand.
-  MapVector<StringRef, uint64_t> FuncOffsetTable;
+  // FuncOffsetTable maps function context to its profile offset in
+  // SecLBRProfile section. It is used to load function profile on demand.
+  MapVector<SampleContext, uint64_t> FuncOffsetTable;
   // Whether to use MD5 to represent string.
   bool UseMD5 = false;
 
+  /// CSNameTable maps function context to its offset in SecCSNameTable section.
+  /// The offset will be used everywhere where the context is referenced.
+  MapVector<SampleContext, uint32_t> CSNameTable;
+
   ProfileSymbolList *ProfSymList = nullptr;
 };
 
 class SampleProfileWriterExtBinary : public SampleProfileWriterExtBinaryBase {
 public:
   SampleProfileWriterExtBinary(std::unique_ptr<raw_ostream> &OS)
       : SampleProfileWriterExtBinaryBase(OS) {}
 
 private:
-  std::error_code
-  writeDefaultLayout(const StringMap<FunctionSamples> &ProfileMap);
-  std::error_code
-  writeCtxSplitLayout(const StringMap<FunctionSamples> &ProfileMap);
+  std::error_code writeDefaultLayout(const SampleProfileMap &ProfileMap);
+  std::error_code writeCtxSplitLayout(const SampleProfileMap &ProfileMap);
 
   virtual std::error_code
-  writeSections(const StringMap<FunctionSamples> &ProfileMap) override;
+  writeSections(const SampleProfileMap &ProfileMap) override;
 
   virtual std::error_code writeCustomSection(SecType Type) override {
     return sampleprof_error::success;
   };
 
   virtual void verifySecLayout(SectionLayout SL) override {
     assert((SL == DefaultLayout || SL == CtxSplitLayout) &&
            "Unsupported layout");

 //
 // We need Part2 because profile reader can use it to find out and read
 // function offset table without reading Part3 first.
 class SampleProfileWriterCompactBinary : public SampleProfileWriterBinary {
   using SampleProfileWriterBinary::SampleProfileWriterBinary;
 
 public:
   virtual std::error_code writeSample(const FunctionSamples &S) override;
-  virtual std::error_code
-  write(const StringMap<FunctionSamples> &ProfileMap) override;
+  virtual std::error_code write(const SampleProfileMap &ProfileMap) override;
 
 protected:
   /// The table mapping from function name to the offset of its FunctionSample
   /// towards profile start.
   MapVector<StringRef, uint64_t> FuncOffsetTable;
   /// The offset of the slot to be filled with the offset of FuncOffsetTable
   /// towards profile start.
   uint64_t TableOffset;
   virtual std::error_code writeNameTable() override;
   virtual std::error_code
-  writeHeader(const StringMap<FunctionSamples> &ProfileMap) override;
+  writeHeader(const SampleProfileMap &ProfileMap) override;
   std::error_code writeFuncOffsetTable();
 };
 
 } // end namespace sampleprof
 } // end namespace llvm
 
 #endif // LLVM_PROFILEDATA_SAMPLEPROFWRITER_H

llvm/include/llvm/Transforms/IPO/ProfiledCallGraph.h

struct ProfiledCallGraphNode {
   std::set<ProfiledCallGraphNode *, ProfiledCallGraphNodeComparer> Callees;
 };
 
 class ProfiledCallGraph {
 public:
   using iterator = std::set<ProfiledCallGraphNode *>::iterator;
 
   // Constructor for non-CS profile.
-  ProfiledCallGraph(StringMap<FunctionSamples> &ProfileMap) {
+  ProfiledCallGraph(SampleProfileMap &ProfileMap) {
     assert(!FunctionSamples::ProfileIsCS && "CS profile is not handled here");
     for (const auto &Samples : ProfileMap) {
       addProfiledCalls(Samples.second);
     }
   }
 
   // Constructor for CS profile.
   ProfiledCallGraph(SampleContextTracker &ContextTracker) {

llvm/include/llvm/Transforms/IPO/SampleContextTracker.h

ContextTrieNode *getChildContext(const LineLocation &CallSite,
                                    StringRef ChildName);
   ContextTrieNode *getHottestChildContext(const LineLocation &CallSite);
   ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite,
                                            StringRef ChildName,
                                            bool AllowCreate = true);
 
   ContextTrieNode &moveToChildContext(const LineLocation &CallSite,
                                       ContextTrieNode &&NodeToMove,
-                                      StringRef ContextStrToRemove,
+                                      uint32_t ContextFramesToRemove,
                                       bool DeleteNode = true);
   void removeChildContext(const LineLocation &CallSite, StringRef ChildName);
   std::map<uint32_t, ContextTrieNode> &getAllChildContext();
   StringRef getFuncName() const;
   FunctionSamples *getFunctionSamples() const;
   void setFunctionSamples(FunctionSamples *FSamples);
   Optional<uint32_t> getFunctionSize() const;
   void addFunctionSize(uint32_t FSize);

 // provides interfaces used by sample profile loader to query context profile or
 // base profile for given function or location; it also manages context tree
 // manipulation that is needed to accommodate inline decisions so we have
 // accurate post-inline profile for functions. Internally context profiles
 // are organized in a trie, with each node representing profile for specific
 // calling context and the context is identified by path from root to the node.
 class SampleContextTracker {
 public:
-  using ContextSamplesTy = SmallVector<FunctionSamples *, 16>;
+  struct ProfileComparer {
+    bool operator()(FunctionSamples *A, FunctionSamples *B) const {
+      // Sort function profiles by the number of total samples and their
+      // contexts.
+      if (A->getTotalSamples() == B->getTotalSamples())
+        return A->getContext() < B->getContext();
+      return A->getTotalSamples() > B->getTotalSamples();
+    }
+  };
+
+  // Keep profiles of a function sorted so that they will be processed/promoted
+  // deterministically.
+  using ContextSamplesTy = std::set<FunctionSamples *, ProfileComparer>;
 
-  SampleContextTracker(StringMap<FunctionSamples> &Profiles);
+  SampleContextTracker(SampleProfileMap &Profiles);
   // Query context profile for a specific callee with given name at a given
   // call-site. The full context is identified by location of call instruction.
   FunctionSamples *getCalleeContextSamplesFor(const CallBase &Inst,
                                               StringRef CalleeName);
   // Get samples for indirect call targets for call site at given location.
   std::vector<const FunctionSamples *>
   getIndirectCalleeContextSamplesFor(const DILocation *DIL);
   // Query context profile for a given location. The full context
private:
   ContextTrieNode *getCalleeContextFor(const DILocation *DIL,
                                        StringRef CalleeName);
   ContextTrieNode *getOrCreateContextPath(const SampleContext &Context,
                                           bool AllowCreate);
   ContextTrieNode *getTopLevelContextNode(StringRef FName);
   ContextTrieNode &addTopLevelContextNode(StringRef FName);
   ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &NodeToPromo);
   void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode,
-                        StringRef ContextStrToRemove);
-  ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &FromNode,
-                                                  ContextTrieNode &ToNodeParent,
-                                                  StringRef ContextStrToRemove);
+                        uint32_t ContextFramesToRemove);
+  ContextTrieNode &
+  promoteMergeContextSamplesTree(ContextTrieNode &FromNode,
+                                 uint32_t ContextFramesToRemove);
 
   // Map from function name to context profiles (excluding base profile)
   StringMap<ContextSamplesTy> FuncToCtxtProfiles;
 
   // Root node for context trie tree
   ContextTrieNode RootContext;
 };
 
 } // end namespace llvm
 #endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H

llvm/lib/MC/MCPseudoProbe.cpp

 }
 
 void MCPseudoProbeFuncDesc::print(raw_ostream &OS) {
   OS << "GUID: " << FuncGUID << " Name: " << FuncName << "\n";
   OS << "Hash: " << FuncHash << "\n";
 }
 
 void MCDecodedPseudoProbe::getInlineContext(
-    SmallVectorImpl<std::string> &ContextStack,
-    const GUIDProbeFunctionMap &GUID2FuncMAP, bool ShowName) const {
+    SmallVectorImpl<MCPseduoProbeFrameLocation> &ContextStack,
+    const GUIDProbeFunctionMap &GUID2FuncMAP) const {
   uint32_t Begin = ContextStack.size();
   MCDecodedPseudoProbeInlineTree *Cur = InlineTree;
   // It will add the string of each node's inline site during iteration.
   // Note that it won't include the probe's belonging function(leaf location)
   while (Cur->hasInlineSite()) {
-    std::string ContextStr;
-    if (ShowName) {
-      StringRef FuncName =
-          getProbeFNameForGUID(GUID2FuncMAP, std::get<0>(Cur->ISite));
-      ContextStr += FuncName.str();
-    } else {
-      ContextStr += Twine(std::get<0>(Cur->ISite)).str();
-    }
-    ContextStr += ":";
-    ContextStr += Twine(std::get<1>(Cur->ISite)).str();
-    ContextStack.emplace_back(ContextStr);
+    ContextStack.emplace_back(
+        MCPseduoProbeFrameLocation(FuncName, std::get<1>(Cur->ISite)));
     Cur = static_cast<MCDecodedPseudoProbeInlineTree *>(Cur->Parent);
   }
   // Make the ContextStack in caller-callee order
   std::reverse(ContextStack.begin() + Begin, ContextStack.end());
 }
 
 std::string MCDecodedPseudoProbe::getInlineContextStr(
-    const GUIDProbeFunctionMap &GUID2FuncMAP, bool ShowName) const {
+    const GUIDProbeFunctionMap &GUID2FuncMAP) const {
   std::ostringstream OContextStr;
-  SmallVector<std::string, 16> ContextStack;
-  getInlineContext(ContextStack, GUID2FuncMAP, ShowName);
-  for (auto &CxtStr : ContextStack) {
+  SmallVector<MCPseduoProbeFrameLocation, 16> ContextStack;
+  getInlineContext(ContextStack, GUID2FuncMAP);
+  for (auto &Cxt : ContextStack) {
     if (OContextStr.str().size())
       OContextStr << " @ ";
-    OContextStr << CxtStr;
+    OContextStr << Cxt.first.str() << ":" << Cxt.second;
   }
   return OContextStr.str();
 }
 
 static const char *PseudoProbeTypeStr[3] = {"Block", "IndirectCall",
                                             "DirectCall"};
 
 void MCDecodedPseudoProbe::print(raw_ostream &OS,
                                  const GUIDProbeFunctionMap &GUID2FuncMAP,
                                  bool ShowName) const {
   OS << "FUNC: ";
   if (ShowName) {
     StringRef FuncName = getProbeFNameForGUID(GUID2FuncMAP, Guid);
     OS << FuncName.str() << " ";
   } else {
     OS << Guid << " ";
   }
   OS << "Index: " << Index << "  ";
   OS << "Type: " << PseudoProbeTypeStr[static_cast<uint8_t>(Type)] << "  ";
-  std::string InlineContextStr = getInlineContextStr(GUID2FuncMAP, ShowName);
+  std::string InlineContextStr = getInlineContextStr(GUID2FuncMAP);
   if (InlineContextStr.size()) {
     OS << "Inlined: @ ";
     OS << InlineContextStr;
   }
   OS << "\n";
 }
 
 template <typename T> ErrorOr<T> MCPseudoProbeDecoder::readUnencodedNumber() {

 MCPseudoProbeDecoder::getFuncDescForGUID(uint64_t GUID) const {
   auto It = GUID2FuncDescMap.find(GUID);
   assert(It != GUID2FuncDescMap.end() && "Function descriptor doesn't exist");
   return &It->second;
 }
 
 void MCPseudoProbeDecoder::getInlineContextForProbe(
     const MCDecodedPseudoProbe *Probe,
-    SmallVectorImpl<std::string> &InlineContextStack, bool IncludeLeaf) const {
-  Probe->getInlineContext(InlineContextStack, GUID2FuncDescMap, true);
+    SmallVectorImpl<MCPseduoProbeFrameLocation> &InlineContextStack,
+    bool IncludeLeaf) const {
+  Probe->getInlineContext(InlineContextStack, GUID2FuncDescMap);
   if (!IncludeLeaf)
     return;
   // Note that the context from probe doesn't include leaf frame,
   // hence we need to retrieve and prepend leaf if requested.
   const auto *FuncDesc = getFuncDescForGUID(Probe->getGuid());
-  InlineContextStack.emplace_back(FuncDesc->FuncName + ":" +
-                                  Twine(Probe->getIndex()).str());
+  InlineContextStack.emplace_back(
+      MCPseduoProbeFrameLocation(FuncDesc->FuncName, Probe->getIndex()));
 }
 
 const MCPseudoProbeFuncDesc *MCPseudoProbeDecoder::getInlinerDescForProbe(
     const MCDecodedPseudoProbe *Probe) const {
   MCDecodedPseudoProbeInlineTree *InlinerNode = Probe->getInlineTreeNode();
   if (!InlinerNode->hasInlineSite())
     return nullptr;
   return getFuncDescForGUID(std::get<0>(InlinerNode->ISite));
 }

llvm/lib/ProfileData/ProfileSummaryBuilder.cpp

std::unique_ptr<ProfileSummary> SampleProfileSummaryBuilder::getSummary() {
   computeDetailedSummary();
   return std::make_unique<ProfileSummary>(
       ProfileSummary::PSK_Sample, DetailedSummary, TotalCount, MaxCount, 0,
       MaxFunctionCount, NumCounts, NumFunctions);
 }
 
 std::unique_ptr<ProfileSummary>
 SampleProfileSummaryBuilder::computeSummaryForProfiles(
-    const StringMap<sampleprof::FunctionSamples> &Profiles) {
+    const SampleProfileMap &Profiles) {
   assert(NumFunctions == 0 &&
          "This can only be called on an empty summary builder");
-  StringMap<sampleprof::FunctionSamples> ContextLessProfiles;
-  const StringMap<sampleprof::FunctionSamples> *ProfilesToUse = &Profiles;
+  sampleprof::SampleProfileMap ContextLessProfiles;
+  const sampleprof::SampleProfileMap *ProfilesToUse = &Profiles;
   // For CSSPGO, context-sensitive profile effectively split a function profile
   // into many copies each representing the CFG profile of a particular calling
   // context. That makes the count distribution looks more flat as we now have
   // more function profiles each with lower counts, which in turn leads to lower
   // hot thresholds. To compensate for that, by defauly we merge context
-  // profiles before coumputing profile summary.
+  // profiles before computing profile summary.
   if (UseContextLessSummary || (sampleprof::FunctionSamples::ProfileIsCS &&
                                 !UseContextLessSummary.getNumOccurrences())) {
     for (const auto &I : Profiles) {
       ContextLessProfiles[I.second.getName()].merge(I.second);
     }
     ProfilesToUse = &ContextLessProfiles;
   }
 

llvm/lib/ProfileData/SampleProf.cpp

 
 raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,
                                           const FunctionSamples &FS) {
   FS.print(OS);
   return OS;
 }
 
 void sampleprof::sortFuncProfiles(
-    const StringMap<FunctionSamples> &ProfileMap,
+    const SampleProfileMap &ProfileMap,
     std::vector<NameFunctionSamples> &SortedProfiles) {
   for (const auto &I : ProfileMap) {
-    assert(I.getKey() == I.second.getNameWithContext() &&
-           "Inconsistent profile map");
-    SortedProfiles.push_back(
-        std::make_pair(I.second.getNameWithContext(), &I.second));
+    assert(I.first == I.second.getContext() && "Inconsistent profile map");
+    SortedProfiles.push_back(std::make_pair(I.second.getContext(), &I.second));
   }
   llvm::stable_sort(SortedProfiles, [](const NameFunctionSamples &A,
                                        const NameFunctionSamples &B) {
     if (A.second->getTotalSamples() == B.second->getTotalSamples())
-      return A.first > B.first;
+      return A.first < B.first;
     return A.second->getTotalSamples() > B.second->getTotalSamples();
   });
 }
 
 unsigned FunctionSamples::getOffset(const DILocation *DIL) {
   return (DIL->getLine() - DIL->getScope()->getSubprogram()->getLine()) &
       0xffff;
 }
const FunctionSamples *FunctionSamples::findFunctionSamples(
   const FunctionSamples *FS = this;
   for (int i = S.size() - 1; i >= 0 && FS != nullptr; i--) {
     FS = FS->findFunctionSamplesAt(S[i].first, S[i].second, Remapper);
   }
   return FS;
 }
 
 void FunctionSamples::findAllNames(DenseSet<StringRef> &NameSet) const {
-  NameSet.insert(Name);
+  NameSet.insert(getName());
   for (const auto &BS : BodySamples)
     for (const auto &TS : BS.second.getCallTargets())
       NameSet.insert(TS.getKey());
 
   for (const auto &CS : CallsiteSamples) {
     for (const auto &NameFS : CS.second) {
       NameSet.insert(NameFS.first);
       NameFS.second.findAllNames(NameSet);
if (!TrimColdContext && !MergeColdContext)
     return;
 
   // Nothing to merge if sample threshold is zero
   if (ColdCountThreshold == 0)
     return;
 
   // Filter the cold profiles from ProfileMap and move them into a tmp
   // container
-  std::vector<std::pair<StringRef, const FunctionSamples *>> ColdProfiles;
+  std::vector<std::pair<SampleContext, const FunctionSamples *>> ColdProfiles;
   for (const auto &I : ProfileMap) {
     const FunctionSamples &FunctionProfile = I.second;
     if (FunctionProfile.getTotalSamples() >= ColdCountThreshold)
       continue;
-    ColdProfiles.emplace_back(I.getKey(), &I.second);
+    ColdProfiles.emplace_back(I.first, &I.second);
   }
 
   // Remove the cold profile from ProfileMap and merge them into
   // MergedProfileMap by the last K frames of context
-  StringMap<FunctionSamples> MergedProfileMap;
+  SampleProfileMap MergedProfileMap;
   for (const auto &I : ColdProfiles) {
     if (MergeColdContext) {
-      auto Ret = MergedProfileMap.try_emplace(
-          I.second->getContext().getContextWithLastKFrames(
-              ColdContextFrameLength),
-          FunctionSamples());
+      auto MergedContext = I.second->getContext().getContextFrames();
+      if (ColdContextFrameLength < MergedContext.size())
+        MergedContext = MergedContext.take_back(ColdContextFrameLength);
+      auto Ret = MergedProfileMap.emplace(MergedContext, FunctionSamples());
       FunctionSamples &MergedProfile = Ret.first->second;
       MergedProfile.merge(*I.second);
     }
     ProfileMap.erase(I.first);
   }
 
   // Move the merged profiles into ProfileMap;
   for (const auto &I : MergedProfileMap) {
     // Filter the cold merged profile
     if (TrimColdContext && I.second.getTotalSamples() < ColdCountThreshold &&
-        ProfileMap.find(I.getKey()) == ProfileMap.end())
+        ProfileMap.find(I.first) == ProfileMap.end())
       continue;
     // Merge the profile if the original profile exists, otherwise just insert
     // as a new profile
-    auto Ret = ProfileMap.try_emplace(I.getKey(), FunctionSamples());
+    auto Ret = ProfileMap.emplace(I.first, FunctionSamples());
     if (Ret.second) {
-      SampleContext FContext(Ret.first->first(), RawContext);
+      SampleContext FContext(Ret.first->first, RawContext);
       FunctionSamples &FProfile = Ret.first->second;
       FProfile.setContext(FContext);
-      FProfile.setName(FContext.getNameWithoutContext());
     }
     FunctionSamples &OrigProfile = Ret.first->second;
     OrigProfile.merge(I.second);
   }
 }
 
 void SampleContextTrimmer::canonicalizeContextProfiles() {
-  std::vector<StringRef> ProfilesToBeRemoved;
-  StringMap<FunctionSamples> ProfilesToBeAdded;
+  std::vector<SampleContext> ProfilesToBeRemoved;
+  SampleProfileMap ProfilesToBeAdded;
   for (auto &I : ProfileMap) {
     FunctionSamples &FProfile = I.second;
-    StringRef ContextStr = FProfile.getNameWithContext();
-    if (I.first() == ContextStr)
+    SampleContext &Context = FProfile.getContext();
+    if (I.first == Context)
       continue;
 
     // Use the context string from FunctionSamples to update the keys of
     // ProfileMap. They can get out of sync after context profile promotion
     // through pre-inliner.
     // Duplicate the function profile for later insertion to avoid a conflict
     // caused by a context both to be add and to be removed. This could happen
     // when a context is promoted to another context which is also promoted to
     // the third context. For example, given an original context A @ B @ C that
     // is promoted to B @ C and the original context B @ C which is promoted to
     // just C, adding B @ C to the profile map while removing same context (but
     // with different profiles) from the map can cause a conflict if they are
     // not handled in a right order. This can be solved by just caching the
     // profiles to be added.
-    auto Ret = ProfilesToBeAdded.try_emplace(ContextStr, FProfile);
+    auto Ret = ProfilesToBeAdded.emplace(Context, FProfile);
     (void)Ret;
     assert(Ret.second && "Context conflict during canonicalization");
-    ProfilesToBeRemoved.push_back(I.first());
+    ProfilesToBeRemoved.push_back(I.first);
   }
 
   for (auto &I : ProfilesToBeRemoved) {
     ProfileMap.erase(I);
   }
 
   for (auto &I : ProfilesToBeAdded) {
-    ProfileMap.try_emplace(I.first(), I.second);
+    ProfileMap.emplace(I.first, I.second);
   }
 }
 
 std::error_code ProfileSymbolList::write(raw_ostream &OS) {
   // Sort the symbols before output. If doing compression.
   // It will make the compression much more effective.
   std::vector<StringRef> SortedList(Syms.begin(), Syms.end());
   llvm::sort(SortedList);

llvm/lib/ProfileData/SampleProfReader.cpp

 static cl::opt<bool> ProfileIsFSDisciminator(
     "profile-isfs", cl::Hidden, cl::init(false),
     cl::desc("Profile uses flow sensitive discriminators"));
 
 /// Dump the function profile for \p FName.
 ///
 /// \param FName Name of the function to print.
 /// \param OS Stream to emit the output to.
-void SampleProfileReader::dumpFunctionProfile(StringRef FName,
+void SampleProfileReader::dumpFunctionProfile(SampleContext FContext,
                                               raw_ostream &OS) {
-  OS << "Function: " << FName << ": " << Profiles[FName];
+  OS << "Function: " << FContext.toString() << ": " << Profiles[FContext];
 }
 
 /// Dump all the function profiles found on stream \p OS.
 void SampleProfileReader::dump(raw_ostream &OS) {
   std::vector<NameFunctionSamples> V;
   sortFuncProfiles(Profiles, V);
   for (const auto &I : V)
     dumpFunctionProfile(I.first, OS);
if ((*LineIt)[0] != ' ') {
       uint64_t NumSamples, NumHeadSamples;
       StringRef FName;
       if (!ParseHead(*LineIt, FName, NumSamples, NumHeadSamples)) {
         reportError(LineIt.line_number(),
                     "Expected 'mangled_name:NUM:NUM', found " + *LineIt);
         return sampleprof_error::malformed;
       }
       SeenMetadata = false;
-      SampleContext FContext(FName);
+      SampleContext FContext(FName, CSNameTable);
       if (FContext.hasContext())
         ++CSProfileCount;
       Profiles[FContext] = FunctionSamples();
       FunctionSamples &FProfile = Profiles[FContext];
-      FProfile.setName(FContext.getNameWithoutContext());
       FProfile.setContext(FContext);
       MergeResult(Result, FProfile.addTotalSamples(NumSamples));
       MergeResult(Result, FProfile.addHeadSamples(NumHeadSamples));
       InlineStack.clear();
       InlineStack.push_back(&FProfile);
     } else {
       uint64_t NumSamples;
       StringRef FName;

 ErrorOr<StringRef> SampleProfileReaderBinary::readStringFromTable() {
   auto Idx = readStringIndex(NameTable);
   if (std::error_code EC = Idx.getError())
     return EC;
 
   return NameTable[*Idx];
 }
 
+ErrorOr<SampleContext> SampleProfileReaderBinary::readSampleContextFromTable() {
+  auto FName(readStringFromTable());
+  if (std::error_code EC = FName.getError())
+    return EC;
+  return SampleContext(*FName);
+}
+
 ErrorOr<StringRef> SampleProfileReaderExtBinaryBase::readStringFromTable() {
   if (!FixedLengthMD5)
     return SampleProfileReaderBinary::readStringFromTable();
 
   // read NameTable index.
   auto Idx = readStringIndex(NameTable);
   if (std::error_code EC = Idx.getError())
     return EC;

 
 std::error_code
 SampleProfileReaderBinary::readFuncProfile(const uint8_t *Start) {
   Data = Start;
   auto NumHeadSamples = readNumber<uint64_t>();
   if (std::error_code EC = NumHeadSamples.getError())
     return EC;
 
-  auto FName(readStringFromTable());
-  if (std::error_code EC = FName.getError())
+  ErrorOr<SampleContext> FContext(readSampleContextFromTable());
+  if (std::error_code EC = FContext.getError())
     return EC;
 
-  SampleContext FContext(*FName);
-  Profiles[FContext] = FunctionSamples();
-  FunctionSamples &FProfile = Profiles[FContext];
-  FProfile.setName(FContext.getNameWithoutContext());
-  FProfile.setContext(FContext);
+  Profiles[*FContext] = FunctionSamples();
+  FunctionSamples &FProfile = Profiles[*FContext];
+  FProfile.setContext(*FContext);
   FProfile.addHeadSamples(*NumHeadSamples);
 
-  if (FContext.hasContext())
+  if (FContext->hasContext())
     CSProfileCount++;
 
   if (std::error_code EC = readProfile(FProfile))
     return EC;
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileReaderBinary::readImpl() {
   ProfileIsFS = ProfileIsFSDisciminator;
   FunctionSamples::ProfileIsFS = ProfileIsFS;
   while (!at_eof()) {
     if (std::error_code EC = readFuncProfile(Data))
       return EC;
   }
 
   return sampleprof_error::success;
 }
 
+ErrorOr<SampleContextFrames>
+SampleProfileReaderExtBinaryBase::readContextFromTable() {
+  auto ContextIdx = readNumber<uint32_t>();
+  if (std::error_code EC = ContextIdx.getError())
+    return EC;
+  if (*ContextIdx >= CSNameTable->size())
+    return sampleprof_error::truncated_name_table;
+  return (*CSNameTable)[*ContextIdx];
+}
+
+ErrorOr<SampleContext>
+SampleProfileReaderExtBinaryBase::readSampleContextFromTable() {
+  if (ProfileIsCS) {
+    auto FContext(readContextFromTable());
+    if (std::error_code EC = FContext.getError())
+      return EC;
+    return SampleContext(*FContext);
+  } else {
+    auto FName(readStringFromTable());
+    if (std::error_code EC = FName.getError())
+      return EC;
+    return SampleContext(*FName);
+  }
+}
+
 std::error_code SampleProfileReaderExtBinaryBase::readOneSection(
     const uint8_t *Start, uint64_t Size, const SecHdrTableEntry &Entry) {
   Data = Start;
   End = Start + Size;
   switch (Entry.Type) {
   case SecProfSummary:
     if (std::error_code EC = readSummary())
       return EC;
case SecNameTable: {
     assert((!FixedLengthMD5 || UseMD5) &&
            "If FixedLengthMD5 is true, UseMD5 has to be true");
     FunctionSamples::HasUniqSuffix =
         hasSecFlag(Entry, SecNameTableFlags::SecFlagUniqSuffix);
     if (std::error_code EC = readNameTableSec(UseMD5))
       return EC;
     break;
   }
+  case SecCSNameTable: {
+    if (std::error_code EC = readCSNameTableSec())
+      return EC;
+    break;
+  }
   case SecLBRProfile:
     if (std::error_code EC = readFuncProfiles())
       return EC;
     break;
   case SecFuncOffsetTable:
     if (std::error_code EC = readFuncOffsetTable())
       return EC;
     break;
std::error_code SampleProfileReaderExtBinaryBase::readFuncOffsetTable() {
   FuncOffsetTable.clear();
 
   auto Size = readNumber<uint64_t>();
   if (std::error_code EC = Size.getError())
     return EC;
 
   FuncOffsetTable.reserve(*Size);
   for (uint32_t I = 0; I < *Size; ++I) {
-    auto FName(readStringFromTable());
+    auto FName(readSampleContextFromTable());
     if (std::error_code EC = FName.getError())
       return EC;
 
     auto Offset = readNumber<uint64_t>();
     if (std::error_code EC = Offset.getError())
       return EC;
 
     FuncOffsetTable[*FName] = *Offset;
if (useMD5()) {
         auto iter = FuncOffsetTable.find(StringRef(GUID));
         if (iter == FuncOffsetTable.end())
           continue;
         const uint8_t *FuncProfileAddr = Start + iter->second;
         assert(FuncProfileAddr < End && "out of LBRProfile section");
         if (std::error_code EC = readFuncProfile(FuncProfileAddr))
           return EC;
       }
-    } else if (FunctionSamples::ProfileIsCS) {
+    } else if (ProfileIsCS) {
       // Compute the ordered set of names, so we can
       // get all context profiles under a subtree by
       // iterating through the ordered names.
-      struct Comparer {
-        // Ignore the closing ']' when ordering context
-        bool operator()(const StringRef &L, const StringRef &R) const {
-          return L.substr(0, L.size() - 1) < R.substr(0, R.size() - 1);
-        }
-      };
-      std::set<StringRef, Comparer> OrderedNames;
+      std::set<SampleContext> OrderedContexts;
       for (auto Name : FuncOffsetTable) {
-        OrderedNames.insert(Name.first);
+        OrderedContexts.insert(Name.first);
       }
 
       // For each function in current module, load all
       // context profiles for the function.
       for (auto NameOffset : FuncOffsetTable) {
-        StringRef ContextName = NameOffset.first;
-        SampleContext FContext(ContextName);
-        auto FuncName = FContext.getNameWithoutContext();
+        SampleContext FContext = NameOffset.first;
+        auto FuncName = FContext.getName();
         if (!FuncsToUse.count(FuncName) &&
             (!Remapper || !Remapper->exist(FuncName)))
           continue;
 
         // For each context profile we need, try to load
         // all context profile in the subtree. This can
         // help profile guided importing for ThinLTO.
-        auto It = OrderedNames.find(ContextName);
-        while (It != OrderedNames.end() &&
-               It->startswith(ContextName.substr(0, ContextName.size() - 1))) {
+        auto It = OrderedContexts.find(FContext);
+        while (It != OrderedContexts.end() && FContext.IsPrefixOf(*It)) {
           const uint8_t *FuncProfileAddr = Start + FuncOffsetTable[*It];
           assert(FuncProfileAddr < End && "out of LBRProfile section");
           if (std::error_code EC = readFuncProfile(FuncProfileAddr))
             return EC;
           // Remove loaded context profile so we won't
           // load it repeatedly.
-          It = OrderedNames.erase(It);
+          It = OrderedContexts.erase(It);
         }
       }
     } else {
       for (auto NameOffset : FuncOffsetTable) {
         SampleContext FContext(NameOffset.first);
-        auto FuncName = FContext.getNameWithoutContext();
+        auto FuncName = FContext.getName();
         if (!FuncsToUse.count(FuncName) &&
             (!Remapper || !Remapper->exist(FuncName)))
           continue;
         const uint8_t *FuncProfileAddr = Start + NameOffset.second;
         assert(FuncProfileAddr < End && "out of LBRProfile section");
         if (std::error_code EC = readFuncProfile(FuncProfileAddr))
           return EC;
       }

 }
 
 std::error_code SampleProfileReaderExtBinaryBase::readNameTableSec(bool IsMD5) {
   if (IsMD5)
     return readMD5NameTable();
   return SampleProfileReaderBinary::readNameTable();
 }
 
-std::error_code
-SampleProfileReaderExtBinaryBase::readFuncMetadata(bool ProfileHasAttribute) {
-  while (Data < End) {
+// Read in the CS name table section, which basically contains a list of context
+// vectors. Each element of a context vector, aka a frame, refers to the
+// underlying raw function names that are stored in the name table, as well as
+// a callsite identifier that only makes sense for non-leaf frames.
+std::error_code SampleProfileReaderExtBinaryBase::readCSNameTableSec() {
+  auto Size = readNumber<uint32_t>();
+  if (std::error_code EC = Size.getError())
+    return EC;
+
+  std::vector<SampleContextFrameVector> *PNameVec =
+      new std::vector<SampleContextFrameVector>();
+  PNameVec->reserve(*Size);
+  for (uint32_t I = 0; I < *Size; ++I) {
+    PNameVec->emplace_back(SampleContextFrameVector());
+    auto ContextSize = readNumber<uint32_t>();
+    if (std::error_code EC = ContextSize.getError())
+      return EC;
+    for (uint32_t J = 0; J < *ContextSize; ++J) {
       auto FName(readStringFromTable());
       if (std::error_code EC = FName.getError())
         return EC;
+      auto LineOffset = readNumber<uint64_t>();
+      if (std::error_code EC = LineOffset.getError())
+        return EC;
+
+      if (!isOffsetLegal(*LineOffset))
+        return std::error_code();
+
+      auto Discriminator = readNumber<uint64_t>();
+      if (std::error_code EC = Discriminator.getError())
+        return EC;
+
+      PNameVec->back().emplace_back(
+          FName.get(), LineLocation(LineOffset.get(), Discriminator.get()));
+    }
+  }
 
-    SampleContext FContext(*FName);
-    bool ProfileInMap = Profiles.count(FContext);
+  // From this point the underlying object of CSNameTable should be immutable.
+  CSNameTable.reset(PNameVec);
+  return sampleprof_error::success;
+}
+
+std::error_code
+SampleProfileReaderExtBinaryBase::readFuncMetadata(bool ProfileHasAttribute) {
+  while (Data < End) {
+    auto FContext(readSampleContextFromTable());
+    if (std::error_code EC = FContext.getError())
+      return EC;
 
+    bool ProfileInMap = Profiles.count(*FContext);
     if (ProfileIsProbeBased) {
       auto Checksum = readNumber<uint64_t>();
       if (std::error_code EC = Checksum.getError())
         return EC;
       if (ProfileInMap)
-        Profiles[FContext].setFunctionHash(*Checksum);
+        Profiles[*FContext].setFunctionHash(*Checksum);
     }
 
     if (ProfileHasAttribute) {
       auto Attributes = readNumber<uint32_t>();
       if (std::error_code EC = Attributes.getError())
         return EC;
       if (ProfileInMap)
-        Profiles[FContext].getContext().setAllAttributes(*Attributes);
+        Profiles[*FContext].getContext().setAllAttributes(*Attributes);
     }
   }
 
   assert(Data == End && "More data is read than expected");
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileReaderCompactBinary::readNameTable() {

llvm/lib/ProfileData/SampleProfWriter.cpp

 #include <set>
 #include <system_error>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 using namespace sampleprof;
 
-std::error_code SampleProfileWriter::writeFuncProfiles(
-    const StringMap<FunctionSamples> &ProfileMap) {
+std::error_code
+SampleProfileWriter::writeFuncProfiles(const SampleProfileMap &ProfileMap) {
   std::vector<NameFunctionSamples> V;
   sortFuncProfiles(ProfileMap, V);
   for (const auto &I : V) {
     if (std::error_code EC = writeSample(*I.second))
       return EC;
   }
   return sampleprof_error::success;
 }
 
-std::error_code
-SampleProfileWriter::write(const StringMap<FunctionSamples> &ProfileMap) {
+std::error_code SampleProfileWriter::write(const SampleProfileMap &ProfileMap) {
   if (std::error_code EC = writeHeader(ProfileMap))
     return EC;
 
   if (std::error_code EC = writeFuncProfiles(ProfileMap))
     return EC;
 
   return sampleprof_error::success;
 }
if (hasSecFlag(Entry, SecCommonFlags::SecFlagCompress)) {
     if (std::error_code EC = compressAndOutput())
       return EC;
   }
   SecHdrTable.push_back({Type, Entry.Flags, SectionStart - FileStart,
                          OutputStream->tell() - SectionStart, LayoutIdx});
   return sampleprof_error::success;
 }
 
-std::error_code SampleProfileWriterExtBinaryBase::write(
-    const StringMap<FunctionSamples> &ProfileMap) {
+std::error_code
+SampleProfileWriterExtBinaryBase::write(const SampleProfileMap &ProfileMap) {
   if (std::error_code EC = writeHeader(ProfileMap))
     return EC;
 
   std::string LocalBuf;
   LocalBufStream = std::make_unique<raw_string_ostream>(LocalBuf);
   if (std::error_code EC = writeSections(ProfileMap))
     return EC;
 
   if (std::error_code EC = writeSecHdrTable())
     return EC;
 
   return sampleprof_error::success;
 }
 
+std::error_code SampleProfileWriterExtBinaryBase::writeContextIdx(
+    const SampleContext &Context) {
+  if (Context.hasContext())
+    return writeCSNameIdx(Context);
+  else
+    return SampleProfileWriterBinary::writeNameIdx(Context.getName());
+}
+
+std::error_code
+SampleProfileWriterExtBinaryBase::writeCSNameIdx(const SampleContext &Context) {
+  const auto &Ret = CSNameTable.find(Context);
+  if (Ret == CSNameTable.end())
+    return sampleprof_error::truncated_name_table;
+  encodeULEB128(Ret->second, *OutputStream);
+  return sampleprof_error::success;
+}
+
 std::error_code
 SampleProfileWriterExtBinaryBase::writeSample(const FunctionSamples &S) {
   uint64_t Offset = OutputStream->tell();
-  StringRef Name = S.getNameWithContext();
-  FuncOffsetTable[Name] = Offset - SecLBRProfileStart;
+  auto &Context = S.getContext();
+  FuncOffsetTable[Context] = Offset - SecLBRProfileStart;
   encodeULEB128(S.getHeadSamples(), *OutputStream);
   return writeBody(S);
 }
 
 std::error_code SampleProfileWriterExtBinaryBase::writeFuncOffsetTable() {
   auto &OS = *OutputStream;
 
   // Write out the table size.
   encodeULEB128(FuncOffsetTable.size(), OS);
 
   // Write out FuncOffsetTable.
   for (auto Entry : FuncOffsetTable) {
-    if (std::error_code EC =
-            writeNameIdx(Entry.first, FunctionSamples::ProfileIsCS))
+    if (std::error_code EC = writeContextIdx(Entry.first))
       return EC;
     encodeULEB128(Entry.second, OS);
   }
   FuncOffsetTable.clear();
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileWriterExtBinaryBase::writeFuncMetadata(
-    const StringMap<FunctionSamples> &Profiles) {
+    const SampleProfileMap &Profiles) {
   if (!FunctionSamples::ProfileIsProbeBased && !FunctionSamples::ProfileIsCS)
     return sampleprof_error::success;
   auto &OS = *OutputStream;
   for (const auto &Entry : Profiles) {
-    if (std::error_code EC = writeNameIdx(Entry.second.getNameWithContext(),
-                                          FunctionSamples::ProfileIsCS))
+    if (std::error_code EC = writeContextIdx(Entry.second.getContext()))
       return EC;
     if (FunctionSamples::ProfileIsProbeBased)
       encodeULEB128(Entry.second.getFunctionHash(), OS);
     if (FunctionSamples::ProfileIsCS)
       encodeULEB128(Entry.second.getContext().getAllAttributes(), OS);
   }
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileWriterExtBinaryBase::writeNameTable() {
   if (!UseMD5)
     return SampleProfileWriterBinary::writeNameTable();
 
   auto &OS = *OutputStream;
   std::set<StringRef> V;
-  stablizeNameTable(V);
+  stablizeNameTable(NameTable, V);
 
   // Write out the MD5 name table. We wrote unencoded MD5 so reader can
   // retrieve the name using the name index without having to read the
   // whole name table.
   encodeULEB128(NameTable.size(), OS);
   support::endian::Writer Writer(OS, support::little);
   for (auto N : V)
     Writer.write(MD5Hash(N));
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileWriterExtBinaryBase::writeNameTableSection(
-    const StringMap<FunctionSamples> &ProfileMap) {
+    const SampleProfileMap &ProfileMap) {
   for (const auto &I : ProfileMap) {
-    assert(I.first() == I.second.getNameWithContext() &&
-           "Inconsistent profile map");
-    addName(I.second.getNameWithContext(), FunctionSamples::ProfileIsCS);
+    assert(I.first == I.second.getContext() && "Inconsistent profile map");
+    addContext(I.second.getContext());
     addNames(I.second);
   }
 
   // If NameTable contains ".__uniq." suffix, set SecFlagUniqSuffix flag
   // so compiler won't strip the suffix during profile matching after
   // seeing the flag in the profile.
   for (const auto &I : NameTable) {
     if (I.first.find(FunctionSamples::UniqSuffix) != StringRef::npos) {
       addSectionFlag(SecNameTable, SecNameTableFlags::SecFlagUniqSuffix);
       break;
     }
   }
 
   if (auto EC = writeNameTable())
     return EC;
   return sampleprof_error::success;
 }
 
+std::error_code SampleProfileWriterExtBinaryBase::writeCSNameTableSection() {
+  // Sort the names to make CSNameTable deterministic.
+  std::set<SampleContext> OrderedContexts;
+  for (const auto &I : CSNameTable)
+    OrderedContexts.insert(I.first);
+  assert(OrderedContexts.size() == CSNameTable.size() &&
+         "Unmatched ordered and unordered contexts");
+  uint64_t I = 0;
+  for (auto &Context : OrderedContexts)
+    CSNameTable[Context] = I++;
+
+  auto &OS = *OutputStream;
+  encodeULEB128(OrderedContexts.size(), OS);
+  support::endian::Writer Writer(OS, support::little);
+  for (auto Context : OrderedContexts) {
+    auto Frames = Context.getContextFrames();
+    encodeULEB128(Frames.size(), OS);
+    for (auto &Callsite : Frames) {
+      if (std::error_code EC = writeNameIdx(Callsite.CallerName))
+        return EC;
+      encodeULEB128(Callsite.Callsite.LineOffset, OS);
+      encodeULEB128(Callsite.Callsite.Discriminator, OS);
+    }
+  }
+
+  return sampleprof_error::success;
+}
+
 std::error_code
 SampleProfileWriterExtBinaryBase::writeProfileSymbolListSection() {
   if (ProfSymList && ProfSymList->size() > 0)
     if (std::error_code EC = ProfSymList->write(*OutputStream))
       return EC;
 
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileWriterExtBinaryBase::writeOneSection(
-    SecType Type, uint32_t LayoutIdx,
-    const StringMap<FunctionSamples> &ProfileMap) {
+    SecType Type, uint32_t LayoutIdx, const SampleProfileMap &ProfileMap) {
   // The setting of SecFlagCompress should happen before markSectionStart.
   if (Type == SecProfileSymbolList && ProfSymList && ProfSymList->toCompress())
     setToCompressSection(SecProfileSymbolList);
   if (Type == SecFuncMetadata && FunctionSamples::ProfileIsProbeBased)
     addSectionFlag(SecFuncMetadata, SecFuncMetadataFlags::SecFlagIsProbeBased);
   if (Type == SecProfSummary && FunctionSamples::ProfileIsCS)
     addSectionFlag(SecProfSummary, SecProfSummaryFlags::SecFlagFullContext);
   if (Type == SecFuncMetadata && FunctionSamples::ProfileIsCS)
     addSectionFlag(SecFuncMetadata, SecFuncMetadataFlags::SecFlagHasAttribute);
   if (Type == SecProfSummary && FunctionSamples::ProfileIsFS)
     addSectionFlag(SecProfSummary, SecProfSummaryFlags::SecFlagFSDiscriminator);
 
   uint64_t SectionStart = markSectionStart(Type, LayoutIdx);
   switch (Type) {
   case SecProfSummary:
     computeSummary(ProfileMap);
     if (auto EC = writeSummary())
       return EC;
     break;
   case SecNameTable:
     if (auto EC = writeNameTableSection(ProfileMap))
       return EC;
     break;
+  case SecCSNameTable:
+    if (auto EC = writeCSNameTableSection())
+      return EC;
+    break;
   case SecLBRProfile:
     SecLBRProfileStart = OutputStream->tell();
     if (std::error_code EC = writeFuncProfiles(ProfileMap))
       return EC;
     break;
   case SecFuncOffsetTable:
     if (auto EC = writeFuncOffsetTable())
       return EC;
default:
     break;
   }
   if (std::error_code EC = addNewSection(Type, LayoutIdx, SectionStart))
     return EC;
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileWriterExtBinary::writeDefaultLayout(
-    const StringMap<FunctionSamples> &ProfileMap) {
+    const SampleProfileMap &ProfileMap) {
   // The const indices passed to writeOneSection below are specifying the
   // positions of the sections in SectionHdrLayout. Look at
   // initSectionHdrLayout to find out where each section is located in
   // SectionHdrLayout.
   if (auto EC = writeOneSection(SecProfSummary, 0, ProfileMap))
     return EC;
   if (auto EC = writeOneSection(SecNameTable, 1, ProfileMap))
     return EC;
-  if (auto EC = writeOneSection(SecLBRProfile, 3, ProfileMap))
+  if (auto EC = writeOneSection(SecCSNameTable, 2, ProfileMap))
+    return EC;
+  if (auto EC = writeOneSection(SecLBRProfile, 4, ProfileMap))
     return EC;
-  if (auto EC = writeOneSection(SecProfileSymbolList, 4, ProfileMap))
+  if (auto EC = writeOneSection(SecProfileSymbolList, 5, ProfileMap))
     return EC;
-  if (auto EC = writeOneSection(SecFuncOffsetTable, 2, ProfileMap))
+  if (auto EC = writeOneSection(SecFuncOffsetTable, 3, ProfileMap))
     return EC;
-  if (auto EC = writeOneSection(SecFuncMetadata, 5, ProfileMap))
+  if (auto EC = writeOneSection(SecFuncMetadata, 6, ProfileMap))
     return EC;
   return sampleprof_error::success;
 }
 
-static void
-splitProfileMapToTwo(const StringMap<FunctionSamples> &ProfileMap,
-                     StringMap<FunctionSamples> &ContextProfileMap,
-                     StringMap<FunctionSamples> &NoContextProfileMap) {
+static void splitProfileMapToTwo(const SampleProfileMap &ProfileMap,
+                                 SampleProfileMap &ContextProfileMap,
+                                 SampleProfileMap &NoContextProfileMap) {
   for (const auto &I : ProfileMap) {
     if (I.second.getCallsiteSamples().size())
-      ContextProfileMap.insert({I.first(), I.second});
+      ContextProfileMap.insert({I.first, I.second});
     else
-      NoContextProfileMap.insert({I.first(), I.second});
+      NoContextProfileMap.insert({I.first, I.second});
   }
 }
 
 std::error_code SampleProfileWriterExtBinary::writeCtxSplitLayout(
-    const StringMap<FunctionSamples> &ProfileMap) {
-  StringMap<FunctionSamples> ContextProfileMap, NoContextProfileMap;
+    const SampleProfileMap &ProfileMap) {
+  SampleProfileMap ContextProfileMap, NoContextProfileMap;
   splitProfileMapToTwo(ProfileMap, ContextProfileMap, NoContextProfileMap);
 
   if (auto EC = writeOneSection(SecProfSummary, 0, ProfileMap))
     return EC;
   if (auto EC = writeOneSection(SecNameTable, 1, ProfileMap))
     return EC;
   if (auto EC = writeOneSection(SecLBRProfile, 3, ContextProfileMap))
     return EC;
if (auto EC = writeOneSection(SecProfileSymbolList, 6, ProfileMap))
     return EC;
   if (auto EC = writeOneSection(SecFuncMetadata, 7, ProfileMap))
     return EC;
 
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileWriterExtBinary::writeSections(
-    const StringMap<FunctionSamples> &ProfileMap) {
+    const SampleProfileMap &ProfileMap) {
   std::error_code EC;
   if (SecLayout == DefaultLayout)
     EC = writeDefaultLayout(ProfileMap);
   else if (SecLayout == CtxSplitLayout)
     EC = writeCtxSplitLayout(ProfileMap);
   else
     llvm_unreachable("Unsupported layout");
   return EC;
 }
 
-std::error_code SampleProfileWriterCompactBinary::write(
-    const StringMap<FunctionSamples> &ProfileMap) {
+std::error_code
+SampleProfileWriterCompactBinary::write(const SampleProfileMap &ProfileMap) {
   if (std::error_code EC = SampleProfileWriter::write(ProfileMap))
     return EC;
   if (std::error_code EC = writeFuncOffsetTable())
     return EC;
   return sampleprof_error::success;
 }
 
 /// Write samples to a text file.
 ///
 /// Note: it may be tempting to implement this in terms of
 /// FunctionSamples::print().  Please don't.  The dump functionality is intended
 /// for debugging and has no specified form.
 ///
 /// The format used here is more structured and deliberate because
 /// it needs to be parsed by the SampleProfileReaderText class.
 std::error_code SampleProfileWriterText::writeSample(const FunctionSamples &S) {
   auto &OS = *OutputStream;
   if (FunctionSamples::ProfileIsCS)
-    OS << "[" << S.getNameWithContext() << "]:" << S.getTotalSamples();
+    OS << "[" << S.getContext().toString() << "]:" << S.getTotalSamples();
   else
     OS << S.getName() << ":" << S.getTotalSamples();
 
   if (Indent == 0)
     OS << ":" << S.getHeadSamples();
   OS << "\n";
 
   SampleSorter<LineLocation, SampleRecord> SortedSamples(S.getBodySamples());
if (FunctionSamples::ProfileIsCS) {
       OS.indent(Indent + 1);
       OS << "!Attributes: " << S.getContext().getAllAttributes() << "\n";
     }
   }
 
   return sampleprof_error::success;
 }
 
-std::error_code SampleProfileWriterBinary::writeNameIdx(StringRef FName,
-                                                        bool IsContextName) {
-  std::string BracketedName;
-  if (IsContextName) {
-    BracketedName = "[" + FName.str() + "]";
-    FName = StringRef(BracketedName);
-  }
+std::error_code
+SampleProfileWriterBinary::writeContextIdx(const SampleContext &Context) {
+  assert(!Context.hasContext() && "cs profile is not supported");
+  return writeNameIdx(Context.getName());
 
-  const auto &Ret = NameTable.find(FName);
-  if (Ret == NameTable.end())
+std::error_code SampleProfileWriterBinary::writeNameIdx(StringRef FName) {
+  auto &NTable = getNameTable();
+  const auto &Ret = NTable.find(FName);
+  if (Ret == NTable.end())
     return sampleprof_error::truncated_name_table;
   encodeULEB128(Ret->second, *OutputStream);
   return sampleprof_error::success;
 }
 
-void SampleProfileWriterBinary::addName(StringRef FName, bool IsContextName) {
-  if (IsContextName) {
-    auto It = BracketedContextStr.insert("[" + FName.str() + "]");
-    FName = StringRef(*It.first);
-  }
-  NameTable.insert(std::make_pair(FName, 0));
+void SampleProfileWriterBinary::addName(StringRef FName) {
+  auto &NTable = getNameTable();
+  NTable.insert(std::make_pair(FName, 0));
+
+void SampleProfileWriterBinary::addContext(const SampleContext &Context) {
+  addName(Context.getName());
 }
 
 void SampleProfileWriterBinary::addNames(const FunctionSamples &S) {
   // Add all the names in indirect call targets.
   for (const auto &I : S.getBodySamples()) {
     const SampleRecord &Sample = I.second;
     for (const auto &J : Sample.getCallTargets())
       addName(J.first());
   }
 
   // Recursively add all the names for inlined callsites.
   for (const auto &J : S.getCallsiteSamples())
     for (const auto &FS : J.second) {
       const FunctionSamples &CalleeSamples = FS.second;
       addName(CalleeSamples.getName());
       addNames(CalleeSamples);
     }
 }
 
-void SampleProfileWriterBinary::stablizeNameTable(std::set<StringRef> &V) {
+void SampleProfileWriterExtBinaryBase::addContext(
+    const SampleContext &Context) {
+  if (Context.hasContext()) {
+    for (auto &Callsite : Context.getContextFrames())
+      SampleProfileWriterBinary::addName(Callsite.CallerName);
+    CSNameTable.insert(std::make_pair(Context, 0));
+  } else {
+    SampleProfileWriterBinary::addName(Context.getName());
+  }
+}
+
+void SampleProfileWriterBinary::stablizeNameTable(
+    MapVector<StringRef, uint32_t> &NameTable, std::set<StringRef> &V) {
   // Sort the names to make NameTable deterministic.
   for (const auto &I : NameTable)
     V.insert(I.first);
   int i = 0;
   for (const StringRef &N : V)
     NameTable[N] = i++;
 }
 
 std::error_code SampleProfileWriterBinary::writeNameTable() {
   auto &OS = *OutputStream;
   std::set<StringRef> V;
-  stablizeNameTable(V);
+  stablizeNameTable(NameTable, V);
 
   // Write out the name table.
   encodeULEB128(NameTable.size(), OS);
   for (auto N : V) {
     OS << N;
     encodeULEB128(0, OS);
   }
   return sampleprof_error::success;
std::error_code SampleProfileWriterCompactBinary::writeFuncOffsetTable() {
   if (OFS.seek(FuncOffsetTableStart) == (uint64_t)-1)
     return sampleprof_error::ostream_seek_unsupported;
 
   // Write out the table size.
   encodeULEB128(FuncOffsetTable.size(), OS);
 
   // Write out FuncOffsetTable.
   for (auto Entry : FuncOffsetTable) {
-    if (std::error_code EC =
-            writeNameIdx(Entry.first, FunctionSamples::ProfileIsCS))
+    if (std::error_code EC = writeNameIdx(Entry.first))
       return EC;
     encodeULEB128(Entry.second, OS);
   }
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileWriterCompactBinary::writeNameTable() {
   auto &OS = *OutputStream;
   std::set<StringRef> V;
-  stablizeNameTable(V);
+  stablizeNameTable(NameTable, V);
 
   // Write out the name table.
   encodeULEB128(NameTable.size(), OS);
   for (auto N : V) {
     encodeULEB128(MD5Hash(N), OS);
   }
   return sampleprof_error::success;
 }
 
 std::error_code
 SampleProfileWriterBinary::writeMagicIdent(SampleProfileFormat Format) {
   auto &OS = *OutputStream;
   // Write file magic identifier.
   encodeULEB128(SPMagic(Format), OS);
   encodeULEB128(SPVersion(), OS);
   return sampleprof_error::success;
 }
 
-std::error_code SampleProfileWriterBinary::writeHeader(
-    const StringMap<FunctionSamples> &ProfileMap) {
+std::error_code
+SampleProfileWriterBinary::writeHeader(const SampleProfileMap &ProfileMap) {
   writeMagicIdent(Format);
 
   computeSummary(ProfileMap);
   if (auto EC = writeSummary())
     return EC;
 
   // Generate the name table for all the functions referenced in the profile.
   for (const auto &I : ProfileMap) {
-    assert(I.first() == I.second.getNameWithContext() &&
-           "Inconsistent profile map");
-    addName(I.first(), FunctionSamples::ProfileIsCS);
+    assert(I.first == I.second.getContext() && "Inconsistent profile map");
+    addContext(I.first);
     addNames(I.second);
   }
 
   writeNameTable();
   return sampleprof_error::success;
 }
 
 void SampleProfileWriterExtBinaryBase::setToCompressAllSections() {
std::error_code SampleProfileWriterExtBinaryBase::writeSecHdrTable() {
   // Reset OutputStream.
   if (OFS.seek(Saved) == (uint64_t)-1)
     return sampleprof_error::ostream_seek_unsupported;
 
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileWriterExtBinaryBase::writeHeader(
-    const StringMap<FunctionSamples> &ProfileMap) {
+    const SampleProfileMap &ProfileMap) {
   auto &OS = *OutputStream;
   FileStart = OS.tell();
   writeMagicIdent(Format);
 
   allocSecHdrTable();
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileWriterCompactBinary::writeHeader(
-    const StringMap<FunctionSamples> &ProfileMap) {
+    const SampleProfileMap &ProfileMap) {
   support::endian::Writer Writer(*OutputStream, support::little);
   if (auto EC = SampleProfileWriterBinary::writeHeader(ProfileMap))
     return EC;
 
   // Reserve a slot for the offset of function offset table. The slot will
   // be populated with the offset of FuncOffsetTable later.
   TableOffset = OutputStream->tell();
   Writer.write(static_cast<uint64_t>(-2));
for (auto Entry : Entries) {
     encodeULEB128(Entry.Cutoff, OS);
     encodeULEB128(Entry.MinCount, OS);
     encodeULEB128(Entry.NumCounts, OS);
   }
   return sampleprof_error::success;
 }
 std::error_code SampleProfileWriterBinary::writeBody(const FunctionSamples &S) {
   auto &OS = *OutputStream;
-
-  if (std::error_code EC =
-          writeNameIdx(S.getNameWithContext(), FunctionSamples::ProfileIsCS))
+  if (std::error_code EC = writeContextIdx(S.getContext()))
     return EC;
 
   encodeULEB128(S.getTotalSamples(), OS);
 
   // Emit all the body samples.
   encodeULEB128(S.getBodySamples().size(), OS);
   for (const auto &I : S.getBodySamples()) {
     LineLocation Loc = I.first;
SampleProfileWriter::create(std::unique_ptr<raw_ostream> &OS,
 
   if (EC)
     return EC;
 
   Writer->Format = Format;
   return std::move(Writer);
 }
 
-void SampleProfileWriter::computeSummary(
-    const StringMap<FunctionSamples> &ProfileMap) {
+void SampleProfileWriter::computeSummary(const SampleProfileMap &ProfileMap) {
   SampleProfileSummaryBuilder Builder(ProfileSummaryBuilder::DefaultCutoffs);
   Summary = Builder.computeSummaryForProfiles(ProfileMap);
 }

llvm/lib/Transforms/IPO/SampleContextTracker.cpp

for (auto &It : AllChildContext) {
     }
   }
 
   return ChildNodeRet;
 }
 
 ContextTrieNode &ContextTrieNode::moveToChildContext(
     const LineLocation &CallSite, ContextTrieNode &&NodeToMove,
-    StringRef ContextStrToRemove, bool DeleteNode) {
+    uint32_t ContextFramesToRemove, bool DeleteNode) {
   uint32_t Hash = nodeHash(NodeToMove.getFuncName(), CallSite);
   assert(!AllChildContext.count(Hash) && "Node to remove must exist");
   LineLocation OldCallSite = NodeToMove.CallSiteLoc;
   ContextTrieNode &OldParentContext = *NodeToMove.getParentContext();
   AllChildContext[Hash] = NodeToMove;
   ContextTrieNode &NewNode = AllChildContext[Hash];
   NewNode.CallSiteLoc = CallSite;
 
   // Walk through nodes in the moved the subtree, and update
   // FunctionSamples' context as for the context promotion.
   // We also need to set new parant link for all children.
   std::queue<ContextTrieNode *> NodeToUpdate;
   NewNode.setParentContext(this);
   NodeToUpdate.push(&NewNode);
 
   while (!NodeToUpdate.empty()) {
     ContextTrieNode *Node = NodeToUpdate.front();
     NodeToUpdate.pop();
     FunctionSamples *FSamples = Node->getFunctionSamples();
 
     if (FSamples) {
-      FSamples->getContext().promoteOnPath(ContextStrToRemove);
+      FSamples->getContext().promoteOnPath(ContextFramesToRemove);
       FSamples->getContext().setState(SyntheticContext);
-      LLVM_DEBUG(dbgs() << "  Context promoted to: " << FSamples->getContext()
-                        << "\n");
+      LLVM_DEBUG(dbgs() << "  Context promoted to: "
+                        << FSamples->getContext().toString() << "\n");
     }
 
     for (auto &It : Node->getAllChildContext()) {
       ContextTrieNode *ChildNode = &It.second;
       ChildNode->setParentContext(Node);
       NodeToUpdate.push(ChildNode);
     }
   }
ContextTrieNode *ContextTrieNode::getOrCreateChildContext(
   if (!AllowCreate)
     return nullptr;
 
   AllChildContext[Hash] = ContextTrieNode(this, CalleeName, nullptr, CallSite);
   return &AllChildContext[Hash];
 }
 
 // Profiler tracker than manages profiles and its associated context
-SampleContextTracker::SampleContextTracker(
-    StringMap<FunctionSamples> &Profiles) {
+SampleContextTracker::SampleContextTracker(SampleProfileMap &Profiles) {
   for (auto &FuncSample : Profiles) {
     FunctionSamples *FSamples = &FuncSample.second;
-    SampleContext Context(FuncSample.first(), RawContext);
-    LLVM_DEBUG(dbgs() << "Tracking Context for function: " << Context << "\n");
+    SampleContext Context = FuncSample.first;
+    LLVM_DEBUG(dbgs() << "Tracking Context for function: " << Context.toString()
+                      << "\n");
     if (!Context.isBaseContext())
-      FuncToCtxtProfiles[Context.getNameWithoutContext()].push_back(FSamples);
+      FuncToCtxtProfiles[Context.getName()].insert(FSamples);
     ContextTrieNode *NewNode = getOrCreateContextPath(Context, true);
     assert(!NewNode->getFunctionSamples() &&
            "New node can't have sample profile");
     NewNode->setFunctionSamples(FSamples);
   }
 }
 
 FunctionSamples *
 SampleContextTracker::getCalleeContextSamplesFor(const CallBase &Inst,
                                                  StringRef CalleeName) {
   LLVM_DEBUG(dbgs() << "Getting callee context for instr: " << Inst << "\n");
   DILocation *DIL = Inst.getDebugLoc();
   if (!DIL)
     return nullptr;
 
   CalleeName = FunctionSamples::getCanonicalFnName(CalleeName);
 
   // For indirect call, CalleeName will be empty, in which case the context
   // profile for callee with largest total samples will be returned.
   ContextTrieNode *CalleeContext = getCalleeContextFor(DIL, CalleeName);
   if (CalleeContext) {
     FunctionSamples *FSamples = CalleeContext->getFunctionSamples();
     LLVM_DEBUG(if (FSamples) {
-      dbgs() << "  Callee context found: " << FSamples->getContext() << "\n";
+      dbgs() << "  Callee context found: " << FSamples->getContext().toString()
+             << "\n";
     });
     return FSamples;
   }
 
   return nullptr;
 }
 
 std::vector<const FunctionSamples *>
if (MergeContext) {
     LLVM_DEBUG(dbgs() << "  Merging context profile into base profile: " << Name
                       << "\n");
 
     // We have profile for function under different contexts,
     // create synthetic base profile and merge context profiles
     // into base profile.
     for (auto *CSamples : FuncToCtxtProfiles[Name]) {
       SampleContext &Context = CSamples->getContext();
-      ContextTrieNode *FromNode = getContextFor(Context);
-      if (FromNode == Node)
-        continue;
-
       // Skip inlined context profile and also don't re-merge any context
       if (Context.hasState(InlinedContext) || Context.hasState(MergedContext))
         continue;
 
+      ContextTrieNode *FromNode = getContextFor(Context);
+      if (FromNode == Node)
+        continue;
+
       ContextTrieNode &ToNode = promoteMergeContextSamplesTree(*FromNode);
       assert((!Node || Node == &ToNode) && "Expect only one base profile");
       Node = &ToNode;
     }
   }
 
   // Still no profile even after merge/promotion (if allowed)
   if (!Node)
     return nullptr;
 
   return Node->getFunctionSamples();
 }
 
 void SampleContextTracker::markContextSamplesInlined(
     const FunctionSamples *InlinedSamples) {
   assert(InlinedSamples && "Expect non-null inlined samples");
   LLVM_DEBUG(dbgs() << "Marking context profile as inlined: "
-                    << InlinedSamples->getContext() << "\n");
+                    << InlinedSamples->getContext().toString() << "\n");
   InlinedSamples->getContext().setState(InlinedContext);
 }
 
 ContextTrieNode &SampleContextTracker::getRootContext() { return RootContext; }
 
 void SampleContextTracker::promoteMergeContextSamplesTree(
     const Instruction &Inst, StringRef CalleeName) {
   LLVM_DEBUG(dbgs() << "Promoting and merging context tree for instr: \n"
ContextTrieNode &SampleContextTracker::promoteMergeContextSamplesTree(
     ContextTrieNode &NodeToPromo) {
   // Promote the input node to be directly under root. This can happen
   // when we decided to not inline a function under context represented
   // by the input node. The promote and merge is then needed to reflect
   // the context profile in the base (context-less) profile.
   FunctionSamples *FromSamples = NodeToPromo.getFunctionSamples();
   assert(FromSamples && "Shouldn't promote a context without profile");
   LLVM_DEBUG(dbgs() << "  Found context tree root to promote: "
-                    << FromSamples->getContext() << "\n");
+                    << FromSamples->getContext().toString() << "\n");
 
   assert(!FromSamples->getContext().hasState(InlinedContext) &&
          "Shouldn't promote inlined context profile");
-  StringRef ContextStrToRemove = FromSamples->getContext().getCallingContext();
+  uint32_t ContextFramesToRemove =
+      FromSamples->getContext().getContextFrames().size() - 1;
   return promoteMergeContextSamplesTree(NodeToPromo, RootContext,
-                                        ContextStrToRemove);
+                                        ContextFramesToRemove);
 }
 
 void SampleContextTracker::dump() { RootContext.dumpTree(); }
 
 ContextTrieNode *
 SampleContextTracker::getContextFor(const SampleContext &Context) {
   return getOrCreateContextPath(Context, false);
 }
ContextTrieNode *SampleContextTracker::getContextFor(const DILocation *DIL) {
 
   return nullptr;
 }
 
 ContextTrieNode *
 SampleContextTracker::getOrCreateContextPath(const SampleContext &Context,
                                              bool AllowCreate) {
   ContextTrieNode *ContextNode = &RootContext;
-  StringRef ContextRemain = Context;
-  StringRef ChildContext;
-  StringRef CalleeName;
   LineLocation CallSiteLoc(0, 0);
 
-  while (ContextNode && !ContextRemain.empty()) {
-    auto ContextSplit = SampleContext::splitContextString(ContextRemain);
-    ChildContext = ContextSplit.first;
-    ContextRemain = ContextSplit.second;
-    LineLocation NextCallSiteLoc(0, 0);
-    SampleContext::decodeContextString(ChildContext, CalleeName,
-                                       NextCallSiteLoc);
-
+  for (auto &Callsite : Context.getContextFrames()) {
     // Create child node at parent line/disc location
     if (AllowCreate) {
-      ContextNode =
-          ContextNode->getOrCreateChildContext(CallSiteLoc, CalleeName);
+      ContextNode = ContextNode->getOrCreateChildContext(CallSiteLoc,
+                                                         Callsite.CallerName);
     } else {
-      ContextNode = ContextNode->getChildContext(CallSiteLoc, CalleeName);
+      ContextNode =
+          ContextNode->getChildContext(CallSiteLoc, Callsite.CallerName);
     }
-    CallSiteLoc = NextCallSiteLoc;
+    CallSiteLoc = Callsite.Callsite;
   }
 
   assert((!AllowCreate || ContextNode) &&
          "Node must exist if creation is allowed");
   return ContextNode;
 }
 
 ContextTrieNode *SampleContextTracker::getTopLevelContextNode(StringRef FName) {
   assert(!FName.empty() && "Top level node query must provide valid name");
   return RootContext.getChildContext(LineLocation(0, 0), FName);
 }
 
 ContextTrieNode &SampleContextTracker::addTopLevelContextNode(StringRef FName) {
   assert(!getTopLevelContextNode(FName) && "Node to add must not exist");
   return *RootContext.getOrCreateChildContext(LineLocation(0, 0), FName);
 }
 
 void SampleContextTracker::mergeContextNode(ContextTrieNode &FromNode,
                                             ContextTrieNode &ToNode,
-                                            StringRef ContextStrToRemove) {
+                                            uint32_t ContextFramesToRemove) {
   FunctionSamples *FromSamples = FromNode.getFunctionSamples();
   FunctionSamples *ToSamples = ToNode.getFunctionSamples();
   if (FromSamples && ToSamples) {
     // Merge/duplicate FromSamples into ToSamples
     ToSamples->merge(*FromSamples);
     ToSamples->getContext().setState(SyntheticContext);
     FromSamples->getContext().setState(MergedContext);
   } else if (FromSamples) {
     // Transfer FromSamples from FromNode to ToNode
     ToNode.setFunctionSamples(FromSamples);
     FromSamples->getContext().setState(SyntheticContext);
-    FromSamples->getContext().promoteOnPath(ContextStrToRemove);
+    FromSamples->getContext().promoteOnPath(ContextFramesToRemove);
     FromNode.setFunctionSamples(nullptr);
   }
 }
 
 ContextTrieNode &SampleContextTracker::promoteMergeContextSamplesTree(
     ContextTrieNode &FromNode, ContextTrieNode &ToNodeParent,
-    StringRef ContextStrToRemove) {
-  assert(!ContextStrToRemove.empty() && "Context to remove can't be empty");
+    uint32_t ContextFramesToRemove) {
+  assert(ContextFramesToRemove && "Context to remove can't be empty");
 
   // Ignore call site location if destination is top level under root
   LineLocation NewCallSiteLoc = LineLocation(0, 0);
   LineLocation OldCallSiteLoc = FromNode.getCallSiteLoc();
   ContextTrieNode &FromNodeParent = *FromNode.getParentContext();
   ContextTrieNode *ToNode = nullptr;
   bool MoveToRoot = (&ToNodeParent == &RootContext);
   if (!MoveToRoot) {
     NewCallSiteLoc = OldCallSiteLoc;
   }
 
   // Locate destination node, create/move if not existing
   ToNode = ToNodeParent.getChildContext(NewCallSiteLoc, FromNode.getFuncName());
   if (!ToNode) {
     // Do not delete node to move from its parent here because
     // caller is iterating over children of that parent node.
     ToNode = &ToNodeParent.moveToChildContext(
-        NewCallSiteLoc, std::move(FromNode), ContextStrToRemove, false);
+        NewCallSiteLoc, std::move(FromNode), ContextFramesToRemove, false);
   } else {
     // Destination node exists, merge samples for the context tree
-    mergeContextNode(FromNode, *ToNode, ContextStrToRemove);
+    mergeContextNode(FromNode, *ToNode, ContextFramesToRemove);
     LLVM_DEBUG({
       if (ToNode->getFunctionSamples())
         dbgs() << "  Context promoted and merged to: "
-               << ToNode->getFunctionSamples()->getContext() << "\n";
+               << ToNode->getFunctionSamples()->getContext().toString() << "\n";
     });
 
     // Recursively promote and merge children
     for (auto &It : FromNode.getAllChildContext()) {
       ContextTrieNode &FromChildNode = It.second;
       promoteMergeContextSamplesTree(FromChildNode, *ToNode,
-                                     ContextStrToRemove);
+                                     ContextFramesToRemove);
     }
 
     // Remove children once they're all merged
     FromNode.getAllChildContext().clear();
   }
 
   // For root of subtree, remove itself from old parent too
   if (MoveToRoot)
     FromNodeParent.removeChildContext(OldCallSiteLoc, ToNode->getFuncName());
 
   return *ToNode;
 }
 } // namespace llvm

llvm/test/Transforms/SampleProfile/csspgo-import-list.ll

 ; Make sure Import GUID list for ThinLTO properly set for CSSPGO
 ; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=pgo-sample-use-pipeline -sample-profile-file=%S/Inputs/csspgo-import-list.prof -S | FileCheck %s
-; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=pgo-sample-use-pipeline -sample-profile-file=%S/Inputs/csspgo-import-list.prof.extbin -S | FileCheck %s
+; RUN: llvm-profdata merge --sample --extbinary %S/Inputs/csspgo-import-list.prof -o %t.prof
+; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=pgo-sample-use-pipeline -sample-profile-file=%t.prof -S | FileCheck %s
 
 declare i32 @_Z5funcBi(i32 %x)
 declare i32 @_Z5funcAi(i32 %x)
 
 define dso_local i32 @main() local_unnamed_addr #0 !dbg !18 {
 entry:
   br label %for.body, !dbg !25
 

llvm/test/Transforms/SampleProfile/profile-context-tracker-debug.ll

 ; INLINE-ALL-NEXT: Getting callee context for instr:   %call.i1 = tail call i32 @_Z3fibi
 ; INLINE-ALL-NEXT: Getting callee context for instr:   %call5.i = tail call i32 @_Z3fibi
 ; INLINE-ALL-DAG:  Getting base profile for function: _Z5funcAi
 ; INLINE-ALL-DAG-NEXT:   Merging context profile into base profile: _Z5funcAi
 ; INLINE-ALL-DAG:  Getting base profile for function: _Z5funcBi
 ; INLINE-ALL-DAG-NEXT:   Merging context profile into base profile: _Z5funcBi
 ; INLINE-ALL-DAG-NEXT:   Found context tree root to promote: external:10 @ _Z5funcBi
 ; INLINE-ALL-DAG-NEXT:   Context promoted to: _Z5funcBi
+; INLINE-ALL-DAG-NEXT:   Found context tree root to promote: externalA:17 @ _Z5funcBi
+; INLINE-ALL-DAG-NEXT:   Context promoted and merged to: _Z5funcBi
 ; INLINE-ALL-DAG-NEXT:   Found context tree root to promote: main:3.1 @ _Z5funcBi
 ; INLINE-ALL-DAG-NEXT:   Context promoted and merged to: _Z5funcBi
 ; INLINE-ALL-DAG-NEXT:   Context promoted to: _Z5funcBi:1 @ _Z8funcLeafi
-; INLINE-ALL-DAG-NEXT:   Found context tree root to promote: externalA:17 @ _Z5funcBi
-; INLINE-ALL-DAG-NEXT:   Context promoted and merged to: _Z5funcBi
 ; INLINE-ALL-DAG-NEXT:   Getting callee context for instr:   %call = tail call i32 @_Z8funcLeafi
 ; INLINE-ALL-DAG-NEXT:   Callee context found: _Z5funcBi:1 @ _Z8funcLeafi
 ; INLINE-ALL-DAG-NEXT:   Marking context profile as inlined: _Z5funcBi:1 @ _Z8funcLeafi
 ; INLINE-ALL-DAG-NEXT:   Getting callee context for instr:   %call.i = tail call i32 @_Z3fibi
 ; INLINE-ALL-DAG-NEXT:   Getting callee context for instr:   %call5.i = tail call i32 @_Z3fibi
 ; INLINE-ALL:     Getting base profile for function: _Z8funcLeafi
 ; INLINE-ALL-NEXT:   Merging context profile into base profile: _Z8funcLeafi
 

 ; INLINE-HOT-DAG-NEXT:   Callee context found: _Z5funcAi:1 @ _Z8funcLeafi
 ; INLINE-HOT-DAG-NEXT:   Marking context profile as inlined: _Z5funcAi:1 @ _Z8funcLeafi
 ; INLINE-HOT-DAG-NEXT:   Getting callee context for instr:   %call.i = tail call i32 @_Z3fibi(i32 %tmp.i) #2, !dbg !62
 ; INLINE-HOT-DAG-NEXT:   Getting callee context for instr:   %call5.i = tail call i32 @_Z3fibi(i32 %tmp1.i) #2, !dbg !69
 ; INLINE-HOT-DAG: Getting base profile for function: _Z5funcBi
 ; INLINE-HOT-DAG-NEXT:   Merging context profile into base profile: _Z5funcBi
 ; INLINE-HOT-DAG-NEXT:   Found context tree root to promote: external:10 @ _Z5funcBi
 ; INLINE-HOT-DAG-NEXT:   Context promoted to: _Z5funcBi
+; INLINE-HOT-DAG-NEXT:   Found context tree root to promote: externalA:17 @ _Z5funcBi
+; INLINE-HOT-DAG-NEXT:   Context promoted and merged to: _Z5funcBi
 ; INLINE-HOT-DAG-NEXT:   Found context tree root to promote: main:3.1 @ _Z5funcBi
 ; INLINE-HOT-DAG-NEXT:   Context promoted and merged to: _Z5funcBi
 ; INLINE-HOT-DAG-NEXT:   Context promoted to: _Z5funcBi:1 @ _Z8funcLeafi
-; INLINE-HOT-DAG-NEXT:   Found context tree root to promote: externalA:17 @ _Z5funcBi
-; INLINE-HOT-DAG-NEXT:   Context promoted and merged to: _Z5funcBi
 ; INLINE-HOT-DAG-NEXT:   Getting callee context for instr:   %call = tail call i32 @_Z8funcLeafi
 ; INLINE-HOT-DAG-NEXT:   Callee context found: _Z5funcBi:1 @ _Z8funcLeafi
 ; INLINE-HOT-DAG-NEXT:   Marking context profile as inlined: _Z5funcBi:1 @ _Z8funcLeafi
 ; INLINE-HOT-DAG-NEXT:   Getting callee context for instr:   %call.i = tail call i32 @_Z3fibi
 ; INLINE-HOT-DAG-NEXT:   Getting callee context for instr:   %call5.i = tail call i32 @_Z3fibi
 ; INLINE-HOT:      Getting base profile for function: _Z8funcLeafi
 ; INLINE-HOT-NEXT:   Merging context profile into base profile: _Z8funcLeafi
 

llvm/test/tools/llvm-profdata/Inputs/cs-sample.proftext

 [main:3 @ _Z5funcAi:1 @ _Z8funcLeafi]:1467299:11
  0: 6
  1: 6
  3: 287884
  4: 287864 _Z3fibi:315608
  15: 23
  !Attributes: 0
 [main:3.1 @ _Z5funcBi:1 @ _Z8funcLeafi]:500853:20
  0: 15
  1: 15
  3: 74946
  4: 74941 _Z3fibi:82359
  10: 23324
  11: 23327 _Z3fibi:25228
  15: 11
  !Attributes: 1
+[external:12 @ main]:154:12
+ 2: 12
+ 3: 10 _Z5funcAi:7
+ 3.1: 10 _Z5funcBi:11
+ !Attributes: 0
 [main]:154:0
  2: 12
  3: 18 _Z5funcAi:11
  3.1: 18 _Z5funcBi:19
  !Attributes: 0
-[external:12 @ main]:154:12
- 2: 12
- 3: 10 _Z5funcAi:7
- 3.1: 10 _Z5funcBi:11
+[external:10 @ _Z5funcBi]:120:10
+ 0: 10
+ 1: 10
+ !Attributes: 0
+[externalA:17 @ _Z5funcBi]:120:3
+ 0: 3
+ 1: 3
  !Attributes: 0
 [main:3.1 @ _Z5funcBi]:120:19
  0: 19
  1: 19 _Z8funcLeafi:20
  3: 12
  !Attributes: 1
-[externalA:17 @ _Z5funcBi]:120:3
- 0: 3
- 1: 3
- !Attributes: 0
-[external:10 @ _Z5funcBi]:120:10
- 0: 10
- 1: 10
- !Attributes: 0
 [main:3 @ _Z5funcAi]:99:11
  0: 10
  1: 10 _Z8funcLeafi:11
  3: 24
- !Attributes: 0
+ !Attributes: 0
 No newline at end of file

llvm/test/tools/llvm-profgen/cs-interrupt.test

+;; The test fails on Windows. Fix it before removing the following requirement.
+; REQUIRES: x86_64-linux
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/cs-interrupt.perfscript --binary=%S/Inputs/noinline-cs-noprobe.perfbin --output=%t --show-unwinder-output --profile-summary-cold-count=0 | FileCheck %s --check-prefix=CHECK-UNWINDER
 ; RUN: FileCheck %s --input-file %t
 
 ; CHECK:[main:1 @ foo]:88:0
 ; CHECK: 2: 5
 ; CHECK: 3: 5 bar:5
 ; CHECK:[main:1 @ foo:3 @ bar]:74:5
 ; CHECK: 0: 5

llvm/test/tools/llvm-profgen/noinline-cs-noprobe.test

+;; The test fails on Windows. Fix it before removing the following requirement.
+; REQUIRES: x86_64-linux
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/noinline-cs-noprobe.perfscript --binary=%S/Inputs/noinline-cs-noprobe.perfbin --output=%t --show-unwinder-output --profile-summary-cold-count=0 | FileCheck %s --check-prefix=CHECK-UNWINDER
 ; RUN: FileCheck %s --input-file %t
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/noinline-cs-noprobe.aggperfscript --binary=%S/Inputs/noinline-cs-noprobe.perfbin --output=%t --show-unwinder-output --profile-summary-cold-count=0 | FileCheck %s --check-prefix=CHECK-AGG-UNWINDER
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-AGG
 
 ; CHECK-AGG:[main:1 @ foo]:108:0
 ; CHECK-AGG: 2: 6
 ; CHECK-AGG: 3: 6 bar:6

llvm/test/tools/llvm-profgen/recursion-compression-noprobe.test

 ; Firstly test uncompression(--compress-recursion=0)
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/recursion-compression-noprobe.perfscript --binary=%S/Inputs/recursion-compression-noprobe.perfbin --output=%t --compress-recursion=0 --profile-summary-cold-count=0
 ; RUN: FileCheck %s --input-file %t -check-prefix=CHECK-UNCOMPRESS
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/recursion-compression-noprobe.perfscript --binary=%S/Inputs/recursion-compression-noprobe.perfbin --output=%t --profile-summary-cold-count=0
 ; RUN: FileCheck %s --input-file %t
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/recursion-compression-noprobe.perfscript --binary=%S/Inputs/recursion-compression-noprobe.perfbin --output=%t --compress-recursion=0 --profile-summary-cold-count=0 --csprof-max-context-depth=2
 ; RUN: FileCheck %s --input-file %t -check-prefix=CHECK-MAX-CTX-DEPTH
 
 ; CHECK-UNCOMPRESS:[main:1 @ foo:3 @ fa:2 @ fb]:48:0
 ; CHECK-UNCOMPRESS: 1: 11
 ; CHECK-UNCOMPRESS: 2: 1 fa:1
 ; CHECK-UNCOMPRESS:[main:1 @ foo:3 @ fa]:24:0
 ; CHECK-UNCOMPRESS: 1: 1
 ; CHECK-UNCOMPRESS: 2: 13 fb:11
-; CHECK-UNCOMPRESS:[main:1 @ foo:3 @ fa:2 @ fb:2 @ fa]:7:0
-; CHECK-UNCOMPRESS: 1: 1
-; CHECK-UNCOMPRESS: 2: 2 fb:1
 ; CHECK-UNCOMPRESS:[main:1 @ foo]:7:0
 ; CHECK-UNCOMPRESS: 2: 1
 ; CHECK-UNCOMPRESS: 3: 2 fa:1
-; CHECK-UNCOMPRESS:[main:1 @ foo:3 @ fa:2 @ fb:2 @ fa:2 @ fb:2 @ fa]:2:0
-; CHECK-UNCOMPRESS: 4: 1
+; CHECK-UNCOMPRESS:[main:1 @ foo:3 @ fa:2 @ fb:2 @ fa]:7:0
+; CHECK-UNCOMPRESS: 1: 1
+; CHECK-UNCOMPRESS: 2: 2 fb:1
 ; CHECK-UNCOMPRESS:[main:1 @ foo:3 @ fa:2 @ fb:2 @ fa:2 @ fb]:2:0
 ; CHECK-UNCOMPRESS: 2: 1 fa:1
+; CHECK-UNCOMPRESS:[main:1 @ foo:3 @ fa:2 @ fb:2 @ fa:2 @ fb:2 @ fa]:2:0
+; CHECK-UNCOMPRESS: 4: 1
 
 ; CHECK-MAX-CTX-DEPTH:[foo:3 @ fa:2 @ fb]:47:0
 ; CHECK-MAX-CTX-DEPTH: 1: 11
 ; CHECK-MAX-CTX-DEPTH:[main:1 @ foo:3 @ fa]:13:0
 ; CHECK-MAX-CTX-DEPTH: 1: 1
 ; CHECK-MAX-CTX-DEPTH: 2: 2
 ; CHECK-MAX-CTX-DEPTH:[fa:2 @ fb:2 @ fa]:8:0
 ; CHECK-MAX-CTX-DEPTH: 1: 1

llvm/test/tools/llvm-profgen/recursion-compression-pseudoprobe.test

 ; Firstly test uncompression(--compress-recursion=0)
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/recursion-compression-pseudoprobe.perfscript --binary=%S/Inputs/recursion-compression-pseudoprobe.perfbin --output=%t --compress-recursion=0 --profile-summary-cold-count=0
 ; RUN: FileCheck %s --input-file %t -check-prefix=CHECK-UNCOMPRESS
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/recursion-compression-pseudoprobe.perfscript --binary=%S/Inputs/recursion-compression-pseudoprobe.perfbin --output=%t --show-unwinder-output --profile-summary-cold-count=0 | FileCheck %s --check-prefix=CHECK-UNWINDER
 ; RUN: FileCheck %s --input-file %t
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/recursion-compression-pseudoprobe-nommap.perfscript --binary=%S/Inputs/recursion-compression-pseudoprobe.perfbin --output=%t --show-unwinder-output --profile-summary-cold-count=0 | FileCheck %s --check-prefix=CHECK-UNWINDER
 ; RUN: FileCheck %s --input-file %t
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/recursion-compression-pseudoprobe.perfscript --binary=%S/Inputs/recursion-compression-pseudoprobe.perfbin --output=%t --compress-recursion=0 --profile-summary-cold-count=0 --csprof-max-context-depth=0
 ; RUN: FileCheck %s --input-file %t -check-prefix=CHECK-MAX-CTX-DEPTH
 
-; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa]:4:1
+
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa]:4:1
 ; CHECK-UNCOMPRESS:  1: 1
 ; CHECK-UNCOMPRESS:  3: 1
-; CHECK-UNCOMPRESS:  4: 1
-; CHECK-UNCOMPRESS:  7: 1 fb:1
+; CHECK-UNCOMPRESS:  5: 1
+; CHECK-UNCOMPRESS:  8: 1 fa:1
 ; CHECK-UNCOMPRESS:  !CFGChecksum: 563070469352221
 ; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa:8 @ fa]:4:1
 ; CHECK-UNCOMPRESS:  1: 1
 ; CHECK-UNCOMPRESS:  3: 1
 ; CHECK-UNCOMPRESS:  4: 1
 ; CHECK-UNCOMPRESS:  7: 1 fb:1
 ; CHECK-UNCOMPRESS:  !CFGChecksum: 563070469352221
-; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa]:4:1
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa]:4:1
 ; CHECK-UNCOMPRESS:  1: 1
 ; CHECK-UNCOMPRESS:  3: 1
-; CHECK-UNCOMPRESS:  5: 1
-; CHECK-UNCOMPRESS:  8: 1 fa:1
+; CHECK-UNCOMPRESS:  4: 1
+; CHECK-UNCOMPRESS:  7: 1 fb:1
 ; CHECK-UNCOMPRESS:  !CFGChecksum: 563070469352221
-; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa:7 @ fb]:3:1
-; CHECK-UNCOMPRESS:  1: 1
-; CHECK-UNCOMPRESS:  3: 1
-; CHECK-UNCOMPRESS:  6: 1 fa:1
-; CHECK-UNCOMPRESS:  !CFGChecksum: 563022570642068
-; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb]:3:1
-; CHECK-UNCOMPRESS:  1: 1
-; CHECK-UNCOMPRESS:  3: 1
-; CHECK-UNCOMPRESS:  6: 1 fa:1
-; CHECK-UNCOMPRESS:  !CFGChecksum: 563022570642068
-; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb]:3:1
-; CHECK-UNCOMPRESS:  1: 1
-; CHECK-UNCOMPRESS:  3: 1
-; CHECK-UNCOMPRESS:  6: 1 fa:1
-; CHECK-UNCOMPRESS:  !CFGChecksum: 563022570642068
-; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb]:3:1
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb]:3:1
 ; CHECK-UNCOMPRESS:  1: 1
 ; CHECK-UNCOMPRESS:  2: 1
 ; CHECK-UNCOMPRESS:  5: 1 fb:1
 ; CHECK-UNCOMPRESS:  !CFGChecksum: 563022570642068
 ; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb]:3:1
 ; CHECK-UNCOMPRESS:  1: 1
 ; CHECK-UNCOMPRESS:  2: 1
 ; CHECK-UNCOMPRESS:  5: 1 fb:1
 ; CHECK-UNCOMPRESS:  !CFGChecksum: 563022570642068
-; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb]:3:1
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb]:3:1
 ; CHECK-UNCOMPRESS:  1: 1
 ; CHECK-UNCOMPRESS:  2: 1
 ; CHECK-UNCOMPRESS:  5: 1 fb:1
 ; CHECK-UNCOMPRESS:  !CFGChecksum: 563022570642068
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb]:3:1
+; CHECK-UNCOMPRESS:  1: 1
+; CHECK-UNCOMPRESS:  3: 1
+; CHECK-UNCOMPRESS:  6: 1 fa:1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 563022570642068
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb]:3:1
+; CHECK-UNCOMPRESS:  1: 1
+; CHECK-UNCOMPRESS:  3: 1
+; CHECK-UNCOMPRESS:  6: 1 fa:1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 563022570642068
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa:7 @ fb]:3:1
+; CHECK-UNCOMPRESS:  1: 1
+; CHECK-UNCOMPRESS:  3: 1
+; CHECK-UNCOMPRESS:  6: 1 fa:1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 563022570642068
 ; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa:7 @ fb:6 @ fa]:2:1
 ; CHECK-UNCOMPRESS:  1: 1
 ; CHECK-UNCOMPRESS:  3: 1
 ; CHECK-UNCOMPRESS:  !CFGChecksum: 563070469352221
 ; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb]:1:0
 ; CHECK-UNCOMPRESS:  5: 1 fb:1
 ; CHECK-UNCOMPRESS:  !CFGChecksum: 563022570642068
-
-
 ; CHECK-MAX-CTX-DEPTH: [fb]:19:6
 ; CHECK-MAX-CTX-DEPTH:  1: 6
 ; CHECK-MAX-CTX-DEPTH:  2: 3
 ; CHECK-MAX-CTX-DEPTH:  3: 3
 ; CHECK-MAX-CTX-DEPTH:  4: 0
 ; CHECK-MAX-CTX-DEPTH:  5: 4 fb:4
 ; CHECK-MAX-CTX-DEPTH:  6: 3 fa:3
 ; CHECK-MAX-CTX-DEPTH:  !CFGChecksum: 563022570642068

 ; CHECK:  6: 1 fa:1
 ; CHECK !CFGChecksum: 563022570642068
 ; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa]:6:2
 ; CHECK:  1: 2
 ; CHECK:  3: 2
 ; CHECK:  4: 1
 ; CHECK:  7: 1 fb:1
 ; CHECK:  !CFGChecksum: 563070469352221
-; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa]:4:1
+ CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa]:4:1
 ; CHECK:  1: 1
 ; CHECK:  3: 1
-; CHECK:  4: 1
-; CHECK:  7: 1 fb:1
+; CHECK:  5: 1
+; CHECK:  8: 1 fa:1
 ; CHECK:  !CFGChecksum: 563070469352221
-; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa]:4:1
+; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa]:4:1
 ; CHECK:  1: 1
 ; CHECK:  3: 1
-; CHECK:  5: 1
-; CHECK:  8: 1 fa:1
+; CHECK:  4: 1
+; CHECK:  7: 1 fb:1
 ; CHECK:  !CFGChecksum: 563070469352221
-; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa:7 @ fb]:3:1
+; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb]:3:1
 ; CHECK:  1: 1
 ; CHECK:  3: 1
 ; CHECK:  6: 1 fa:1
 ; CHECK:  !CFGChecksum: 563022570642068
-; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb]:3:1
+; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa:7 @ fb]:3:1
 ; CHECK:  1: 1
 ; CHECK:  3: 1
 ; CHECK:  6: 1 fa:1
 ; CHECK:  !CFGChecksum: 563022570642068
 
 
 
-
 ; CHECK-UNWINDER: Binary(recursion-compression-pseudoprobe.perfbin)'s Range Counter:
 ; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5
 ; CHECK-UNWINDER:   (7a0, 7a7): 1
 ; CHECK-UNWINDER:   (7a0, 7ab): 3
 ; CHECK-UNWINDER:   (7b2, 7b5): 1
 ; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6
 ; CHECK-UNWINDER:   (7c0, 7d4): 1
 ; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8

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

uint64_t ColdInstrThreshold =
           : ProfileSummaryBuilder::getEntryForPercentile(
                 InstrPS.getDetailedSummary(),
                 ProfileSummaryBuilder::DefaultCutoffs[ColdPercentileIdx])
                 .MinCount;
 
   // Find hot/warm functions in sample profile which is cold in instr profile
   // and adjust the profiles of those functions in the instr profile.
   for (const auto &PD : Reader->getProfiles()) {
-    StringRef FName = PD.getKey();
-    const sampleprof::FunctionSamples &FS = PD.getValue();
-    auto It = InstrProfileMap.find(FName);
+    auto &FContext = PD.first;
+    const sampleprof::FunctionSamples &FS = PD.second;
+    auto It = InstrProfileMap.find(FContext.toString());
     if (FS.getHeadSamples() > ColdSampleThreshold &&
         It != InstrProfileMap.end() &&
         It->second.MaxCount <= ColdInstrThreshold &&
         FS.getBodySamples().size() >= SupplMinSizeThreshold) {
       updateInstrProfileEntry(It->second, HotInstrThreshold,
                               ZeroCounterThreshold);
     }
   }

 static void
 mergeSampleProfile(const WeightedFileVector &Inputs, SymbolRemapper *Remapper,
                    StringRef OutputFilename, ProfileFormat OutputFormat,
                    StringRef ProfileSymbolListFile, bool CompressAllSections,
                    bool UseMD5, bool GenPartialProfile,
                    bool SampleMergeColdContext, bool SampleTrimColdContext,
                    bool SampleColdContextFrameDepth, FailureMode FailMode) {
   using namespace sampleprof;
-  StringMap<FunctionSamples> ProfileMap;
+  SampleProfileMap ProfileMap;
   SmallVector<std::unique_ptr<sampleprof::SampleProfileReader>, 5> Readers;
   LLVMContext Context;
   sampleprof::ProfileSymbolList WriterList;
   Optional<bool> ProfileIsProbeBased;
   Optional<bool> ProfileIsCS;
   for (const auto &Input : Inputs) {
     auto ReaderOrErr = SampleProfileReader::create(Input.Filename, Context,
                                                    FSDiscriminatorPassOption);
for (const auto &Input : Inputs) {
     Readers.push_back(std::move(ReaderOrErr.get()));
     const auto Reader = Readers.back().get();
     if (std::error_code EC = Reader->read()) {
       warnOrExitGivenError(FailMode, EC, Input.Filename);
       Readers.pop_back();
       continue;
     }
 
-    StringMap<FunctionSamples> &Profiles = Reader->getProfiles();
+    SampleProfileMap &Profiles = Reader->getProfiles();
     if (ProfileIsProbeBased.hasValue() &&
         ProfileIsProbeBased != FunctionSamples::ProfileIsProbeBased)
       exitWithError(
           "cannot merge probe-based profile with non-probe-based profile");
     ProfileIsProbeBased = FunctionSamples::ProfileIsProbeBased;
     if (ProfileIsCS.hasValue() && ProfileIsCS != FunctionSamples::ProfileIsCS)
       exitWithError("cannot merge CS profile with non-CS profile");
     ProfileIsCS = FunctionSamples::ProfileIsCS;
-    for (StringMap<FunctionSamples>::iterator I = Profiles.begin(),
-                                              E = Profiles.end();
+    for (SampleProfileMap::iterator I = Profiles.begin(), E = Profiles.end();
          I != E; ++I) {
       sampleprof_error Result = sampleprof_error::success;
       FunctionSamples Remapped =
           Remapper ? remapSamples(I->second, *Remapper, Result)
                    : FunctionSamples();
       FunctionSamples &Samples = Remapper ? Remapped : I->second;
-      StringRef FName = Samples.getNameWithContext();
-      MergeResult(Result, ProfileMap[FName].merge(Samples, Input.Weight));
+      SampleContext FContext = Samples.getContext();
+      MergeResult(Result, ProfileMap[FContext].merge(Samples, Input.Weight));
       if (Result != sampleprof_error::success) {
         std::error_code EC = make_error_code(Result);
-        handleMergeWriterError(errorCodeToError(EC), Input.Filename, FName);
+        handleMergeWriterError(errorCodeToError(EC), Input.Filename,
+                               FContext.toString());
       }
     }
 
     std::unique_ptr<sampleprof::ProfileSymbolList> ReaderList =
         Reader->getProfileSymbolList();
     if (ReaderList)
       WriterList.merge(*ReaderList);
   }
static void overlapInstrProfile(const std::string &BaseFilename,
   loadInput(WeightedInput, nullptr, &Context);
   overlapInput(BaseFilename, TestFilename, &Context, Overlap, FuncFilter, OS,
                IsCS);
   Overlap.dump(OS);
 }
 
 namespace {
 struct SampleOverlapStats {
-  StringRef BaseName;
-  StringRef TestName;
+  SampleContext BaseName;
+  SampleContext TestName;
   // Number of overlap units
   uint64_t OverlapCount;
   // Total samples of overlap units
   uint64_t OverlapSample;
   // Number of and total samples of units that only present in base or test
   // profile
   uint64_t BaseUniqueCount;
   uint64_t BaseUniqueSample;
public:
   /// profiles. This function also computes and keeps the sum of samples and
   /// max sample counts of each function in BaseStats and TestStats for later
   /// use to avoid re-computations.
   void initializeSampleProfileOverlap();
 
   /// Load profiles specified by BaseFilename and TestFilename.
   std::error_code loadProfiles();
 
+  using FuncSampleStatsMap =
+      std::unordered_map<SampleContext, FuncSampleStats, SampleContext::Hash>;
+
 private:
   SampleOverlapStats ProfOverlap;
   SampleOverlapStats HotFuncOverlap;
   SampleOverlapStats HotBlockOverlap;
   std::string BaseFilename;
   std::string TestFilename;
   std::unique_ptr<sampleprof::SampleProfileReader> BaseReader;
   std::unique_ptr<sampleprof::SampleProfileReader> TestReader;
   // BaseStats and TestStats hold FuncSampleStats for each function, with
   // function name as the key.
-  StringMap<FuncSampleStats> BaseStats;
-  StringMap<FuncSampleStats> TestStats;
+  FuncSampleStatsMap BaseStats;
+  FuncSampleStatsMap TestStats;
   // Low similarity threshold in floating point number
   double LowSimilarityThreshold;
   // Block samples above BaseHotThreshold or TestHotThreshold are considered hot
   // for tracking hot blocks.
   uint64_t BaseHotThreshold;
   uint64_t TestHotThreshold;
   // A small threshold used to round the results of floating point accumulations
   // to resolve imprecision.
private:
   ///    this function in test profile ST, compute BS(i) = 1.0 - fabs(BB(i)/SB -
   ///    BT(i)/ST), ranging in [0.0f to 1.0f] with 0.0 meaning no-overlap.
   double computeBlockSimilarity(uint64_t BaseSample, uint64_t TestSample,
                                 const SampleOverlapStats &FuncOverlap) const;
 
   void updateHotBlockOverlap(uint64_t BaseSample, uint64_t TestSample,
                              uint64_t HotBlockCount);
 
-  void getHotFunctions(const StringMap<FuncSampleStats> &ProfStats,
-                       StringMap<FuncSampleStats> &HotFunc,
+  void getHotFunctions(const FuncSampleStatsMap &ProfStats,
+                       FuncSampleStatsMap &HotFunc,
                        uint64_t HotThreshold) const;
 
   void computeHotFuncOverlap();
 
   /// This function updates statistics in FuncOverlap, HotBlockOverlap, and
   /// Difference for two sample units in a matched function according to the
   /// given match status.
   void updateOverlapStatsForFunction(uint64_t BaseSample, uint64_t TestSample,
if (IsBaseHot)
     HotBlockOverlap.BaseCount += HotBlockCount;
   if (IsTestHot)
     HotBlockOverlap.TestCount += HotBlockCount;
   if (IsBaseHot && IsTestHot)
     HotBlockOverlap.OverlapCount += HotBlockCount;
 }
 
 void SampleOverlapAggregator::getHotFunctions(
-    const StringMap<FuncSampleStats> &ProfStats,
-    StringMap<FuncSampleStats> &HotFunc, uint64_t HotThreshold) const {
+    const FuncSampleStatsMap &ProfStats, FuncSampleStatsMap &HotFunc,
+    uint64_t HotThreshold) const {
   for (const auto &F : ProfStats) {
     if (isFunctionHot(F.second, HotThreshold))
-      HotFunc.try_emplace(F.first(), F.second);
+      HotFunc.emplace(F.first, F.second);
   }
 }
 
 void SampleOverlapAggregator::computeHotFuncOverlap() {
-  StringMap<FuncSampleStats> BaseHotFunc;
+  FuncSampleStatsMap BaseHotFunc;
   getHotFunctions(BaseStats, BaseHotFunc, BaseHotThreshold);
   HotFuncOverlap.BaseCount = BaseHotFunc.size();
 
-  StringMap<FuncSampleStats> TestHotFunc;
+  FuncSampleStatsMap TestHotFunc;
   getHotFunctions(TestStats, TestHotFunc, TestHotThreshold);
   HotFuncOverlap.TestCount = TestHotFunc.size();
   HotFuncOverlap.UnionCount = HotFuncOverlap.TestCount;
 
   for (const auto &F : BaseHotFunc) {
-    if (TestHotFunc.count(F.first()))
+    if (TestHotFunc.count(F.first))
       ++HotFuncOverlap.OverlapCount;
     else
       ++HotFuncOverlap.UnionCount;
   }
 }
 
 void SampleOverlapAggregator::updateOverlapStatsForFunction(
     uint64_t BaseSample, uint64_t TestSample, uint64_t HotBlockCount,
double SampleOverlapAggregator::computeSampleFunctionOverlap(
   FuncSimilarity = weightForFuncSimilarity(FuncInternalSimilarity,
                                            BaseFuncSample, TestFuncSample);
   return FuncSimilarity;
 }
 
 void SampleOverlapAggregator::computeSampleProfileOverlap(raw_fd_ostream &OS) {
   using namespace sampleprof;
 
-  StringMap<const FunctionSamples *> BaseFuncProf;
+  std::unordered_map<SampleContext, const FunctionSamples *,
+                     SampleContext::Hash>
+      BaseFuncProf;
   const auto &BaseProfiles = BaseReader->getProfiles();
   for (const auto &BaseFunc : BaseProfiles) {
-    BaseFuncProf.try_emplace(BaseFunc.second.getNameWithContext(),
-                             &(BaseFunc.second));
+    BaseFuncProf.emplace(BaseFunc.second.getContext(), &(BaseFunc.second));
   }
   ProfOverlap.UnionCount = BaseFuncProf.size();
 
   const auto &TestProfiles = TestReader->getProfiles();
   for (const auto &TestFunc : TestProfiles) {
     SampleOverlapStats FuncOverlap;
-    FuncOverlap.TestName = TestFunc.second.getNameWithContext();
+    FuncOverlap.TestName = TestFunc.second.getContext();
     assert(TestStats.count(FuncOverlap.TestName) &&
            "TestStats should have records for all functions in test profile "
            "except inlinees");
     FuncOverlap.TestSample = TestStats[FuncOverlap.TestName].SampleSum;
 
     const auto Match = BaseFuncProf.find(FuncOverlap.TestName);
     if (Match == BaseFuncProf.end()) {
       const FuncSampleStats &FuncStats = TestStats[FuncOverlap.TestName];
if (Match == BaseFuncProf.end()) {
 
       ++ProfOverlap.UnionCount;
       ProfOverlap.UnionSample += FuncStats.SampleSum;
     } else {
       ++ProfOverlap.OverlapCount;
 
       // Two functions match with each other. Compute function-level overlap and
       // aggregate them into profile-level overlap.
-      FuncOverlap.BaseName = Match->second->getNameWithContext();
+      FuncOverlap.BaseName = Match->second->getContext();
       assert(BaseStats.count(FuncOverlap.BaseName) &&
              "BaseStats should have records for all functions in base profile "
              "except inlinees");
       FuncOverlap.BaseSample = BaseStats[FuncOverlap.BaseName].SampleSum;
 
       FuncOverlap.Similarity = computeSampleFunctionOverlap(
           Match->second, &TestFunc.second, &FuncOverlap, FuncOverlap.BaseSample,
           FuncOverlap.TestSample);
for (const auto &TestFunc : TestProfiles) {
     // Print function-level similarity information if specified by options.
     assert(TestStats.count(FuncOverlap.TestName) &&
            "TestStats should have records for all functions in test profile "
            "except inlinees");
     if (TestStats[FuncOverlap.TestName].MaxSample >= FuncFilter.ValueCutoff ||
         (Match != BaseFuncProf.end() &&
          FuncOverlap.Similarity < LowSimilarityThreshold) ||
         (Match != BaseFuncProf.end() && !FuncFilter.NameFilter.empty() &&
-         FuncOverlap.BaseName.find(FuncFilter.NameFilter) !=
-             FuncOverlap.BaseName.npos)) {
+         FuncOverlap.BaseName.toString().find(FuncFilter.NameFilter) !=
+             std::string::npos)) {
       assert(ProfOverlap.BaseSample > 0 &&
              "Total samples in base profile should be greater than 0");
       FuncOverlap.BaseWeight =
           static_cast<double>(FuncOverlap.BaseSample) / ProfOverlap.BaseSample;
       assert(ProfOverlap.TestSample > 0 &&
              "Total samples in test profile should be greater than 0");
       FuncOverlap.TestWeight =
           static_cast<double>(FuncOverlap.TestSample) / ProfOverlap.TestSample;
       FuncSimilarityDump.emplace(FuncOverlap.BaseWeight, FuncOverlap);
     }
   }
 
   // Traverse through functions in base profile but not in test profile.
   for (const auto &F : BaseFuncProf) {
-    assert(BaseStats.count(F.second->getNameWithContext()) &&
+    assert(BaseStats.count(F.second->getContext()) &&
            "BaseStats should have records for all functions in base profile "
            "except inlinees");
-    const FuncSampleStats &FuncStats =
-        BaseStats[F.second->getNameWithContext()];
+    const FuncSampleStats &FuncStats = BaseStats[F.second->getContext()];
     ++ProfOverlap.BaseUniqueCount;
     ProfOverlap.BaseUniqueSample += FuncStats.SampleSum;
 
     updateHotBlockOverlap(FuncStats.SampleSum, 0, FuncStats.HotBlockCount);
 
     double FuncSimilarity = computeSampleFunctionOverlap(
         nullptr, nullptr, nullptr, FuncStats.SampleSum, 0);
     ProfOverlap.Similarity +=

 
 void SampleOverlapAggregator::initializeSampleProfileOverlap() {
   const auto &BaseProf = BaseReader->getProfiles();
   for (const auto &I : BaseProf) {
     ++ProfOverlap.BaseCount;
     FuncSampleStats FuncStats;
     getFuncSampleStats(I.second, FuncStats, BaseHotThreshold);
     ProfOverlap.BaseSample += FuncStats.SampleSum;
-    BaseStats.try_emplace(I.second.getNameWithContext(), FuncStats);
+    BaseStats.emplace(I.second.getContext(), FuncStats);
   }
 
   const auto &TestProf = TestReader->getProfiles();
   for (const auto &I : TestProf) {
     ++ProfOverlap.TestCount;
     FuncSampleStats FuncStats;
     getFuncSampleStats(I.second, FuncStats, TestHotThreshold);
     ProfOverlap.TestSample += FuncStats.SampleSum;
-    TestStats.try_emplace(I.second.getNameWithContext(), FuncStats);
+    TestStats.emplace(I.second.getContext(), FuncStats);
   }
 
   ProfOverlap.BaseName = StringRef(BaseFilename);
   ProfOverlap.TestName = StringRef(TestFilename);
 }
 
 void SampleOverlapAggregator::dumpFuncSimilarity(raw_fd_ostream &OS) const {
   using namespace sampleprof;
for (const auto &F : FuncSimilarityDump) {
     FOS << format("%.2f%%", BaseUniquePercent * 100);
     FOS.PadToColumn(TestUniqueCol);
     FOS << format("%.2f%%", TestUniquePercent * 100);
     FOS.PadToColumn(BaseSampleCol);
     FOS << F.second.BaseSample;
     FOS.PadToColumn(TestSampleCol);
     FOS << F.second.TestSample;
     FOS.PadToColumn(FuncNameCol);
-    FOS << F.second.TestName << "\n";
+    FOS << F.second.TestName.toString() << "\n";
   }
 }
 
 void SampleOverlapAggregator::dumpProgramSummary(raw_fd_ostream &OS) const {
-  OS << "Profile overlap infomation for base_profile: " << ProfOverlap.BaseName
-     << " and test_profile: " << ProfOverlap.TestName << "\nProgram level:\n";
+  OS << "Profile overlap infomation for base_profile: "
+     << ProfOverlap.BaseName.toString()
+     << " and test_profile: " << ProfOverlap.TestName.toString()
+     << "\nProgram level:\n";
 
   OS << "  Whole program profile similarity: "
      << format("%.3f%%", ProfOverlap.Similarity * 100) << "\n";
 
   assert(ProfOverlap.UnionSample > 0 &&
          "Total samples in two profile should be greater than 0");
   double OverlapPercent =
       static_cast<double>(ProfOverlap.OverlapSample) / ProfOverlap.UnionSample;
WithColor::warning() << "-show-sec-info-only is only supported for "
                          << "sample profile in extbinary format and is "
                          << "ignored for other formats.\n";
     return;
   }
 }
 
 namespace {
 struct HotFuncInfo {
-  StringRef FuncName;
+  std::string FuncName;
   uint64_t TotalCount;
   double TotalCountPercent;
   uint64_t MaxCount;
   uint64_t EntryCount;
 
   HotFuncInfo()
       : FuncName(), TotalCount(0), TotalCountPercent(0.0f), MaxCount(0),
         EntryCount(0) {}
 
   HotFuncInfo(StringRef FN, uint64_t TS, double TSP, uint64_t MS, uint64_t ES)
-      : FuncName(FN), TotalCount(TS), TotalCountPercent(TSP), MaxCount(MS),
-        EntryCount(ES) {}
+      : FuncName(FN.begin(), FN.end()), TotalCount(TS), TotalCountPercent(TSP),
+        MaxCount(MS), EntryCount(ES) {}
 };
 } // namespace
 
 // Print out detailed information about hot functions in PrintValues vector.
 // Users specify titles and offset of every columns through ColumnTitle and
 // ColumnOffset. The size of ColumnTitle and ColumnOffset need to be the same
 // and at least 4. Besides, users can optionally give a HotFuncMetric string to
 // print out or let it be an empty string.
for (const HotFuncInfo &R : PrintValues) {
     FOS << R.MaxCount;
     FOS.PadToColumn(ColumnOffset[2]);
     FOS << R.EntryCount;
     FOS.PadToColumn(ColumnOffset[3]);
     FOS << R.FuncName << "\n";
   }
 }
 
-static int
-showHotFunctionList(const StringMap<sampleprof::FunctionSamples> &Profiles,
+static int showHotFunctionList(const sampleprof::SampleProfileMap &Profiles,
                                ProfileSummary &PS, raw_fd_ostream &OS) {
   using namespace sampleprof;
 
   const uint32_t HotFuncCutoff = 990000;
   auto &SummaryVector = PS.getDetailedSummary();
   uint64_t MinCountThreshold = 0;
   for (const ProfileSummaryEntry &SummaryEntry : SummaryVector) {
     if (SummaryEntry.Cutoff == HotFuncCutoff) {
       MinCountThreshold = SummaryEntry.MinCount;
static int showHotFunctionList(const sampleprof::SampleProfileMap &Profiles,
   std::vector<HotFuncInfo> PrintValues;
   for (const auto &FuncPair : HotFunc) {
     const FunctionSamples &Func = *FuncPair.second.first;
     double TotalSamplePercent =
         (ProfileTotalSample > 0)
             ? (Func.getTotalSamples() * 100.0) / ProfileTotalSample
             : 0;
     PrintValues.emplace_back(HotFuncInfo(
-        Func.getNameWithContext(), Func.getTotalSamples(), TotalSamplePercent,
-        FuncPair.second.second, Func.getEntrySamples()));
+        Func.getContext().toString(), Func.getTotalSamples(),
+        TotalSamplePercent, FuncPair.second.second, Func.getEntrySamples()));
   }
   dumpHotFunctionList(ColumnTitle, ColumnOffset, PrintValues, HotFuncCount,
                       Profiles.size(), HotFuncSample, ProfileTotalSample,
                       Metric, OS);
 
   return 0;
 }
 
static int showSampleProfile(const std::string &Filename, bool ShowCounts,
   }
 
   if (std::error_code EC = Reader->read())
     exitWithErrorCode(EC, Filename);
 
   if (ShowAllFunctions || ShowFunction.empty())
     Reader->dump(OS);
   else
-    Reader->dumpFunctionProfile(ShowFunction, OS);
+    // TODO: parse context string to support filtering by contexts.
+    Reader->dumpFunctionProfile(StringRef(ShowFunction), OS);
 
   if (ShowProfileSymbolList) {
     std::unique_ptr<sampleprof::ProfileSymbolList> ReaderList =
         Reader->getProfileSymbolList();
     ReaderList->dump(OS);
   }
 
   if (ShowDetailedSummary) {

llvm/tools/llvm-profgen/CSPreInliner.h

 // Pre-compilation inliner based on context-sensitive profile.
 // The PreInliner estimates inline decision using hotness from profile
 // and cost estimation from machine code size. It helps merges context
 // profile globally and achieves better post-inine profile quality, which
 // otherwise won't be possible for ThinLTO. It also reduce context profile
 // size by only keep context that is estimated to be inlined.
 class CSPreInliner {
 public:
-  CSPreInliner(StringMap<FunctionSamples> &Profiles, ProfiledBinary &Binary,
+  CSPreInliner(SampleProfileMap &Profiles, ProfiledBinary &Binary,
                uint64_t HotThreshold, uint64_t ColdThreshold);
   void run();
 
 private:
   bool getInlineCandidates(ProfiledCandidateQueue &CQueue,
                            const FunctionSamples *FCallerContextSamples);
   std::vector<StringRef> buildTopDownOrder();
   void processFunction(StringRef Name);
   bool shouldInline(ProfiledInlineCandidate &Candidate);
   uint32_t getFuncSize(const FunctionSamples &FSamples);
   bool UseContextCost;
   SampleContextTracker ContextTracker;
-  StringMap<FunctionSamples> &ProfileMap;
+  SampleProfileMap &ProfileMap;
   ProfiledBinary &Binary;
 
   // Count thresholds to answer isHotCount and isColdCount queries.
   // Mirrors the threshold in ProfileSummaryInfo.
   uint64_t HotCountThreshold;
   uint64_t ColdCountThreshold;
 };
 
 } // end namespace sampleprof
 } // end namespace llvm
 
 #endif

llvm/tools/llvm-profgen/CSPreInliner.cpp

cl::opt<bool> UseContextCostForPreInliner(
     "use-context-cost-for-preinliner", cl::Hidden, cl::init(false),
     cl::desc("Use context-sensitive byte size cost for preinliner decisions"));
 
 static cl::opt<bool> SamplePreInlineReplay(
     "csspgo-replay-preinline", cl::Hidden, cl::init(false),
     cl::desc(
         "Replay previous inlining and adjust context profile accordingly"));
 
-CSPreInliner::CSPreInliner(StringMap<FunctionSamples> &Profiles,
-                           ProfiledBinary &Binary, uint64_t HotThreshold,
-                           uint64_t ColdThreshold)
+CSPreInliner::CSPreInliner(SampleProfileMap &Profiles, ProfiledBinary &Binary,
+                           uint64_t HotThreshold, uint64_t ColdThreshold)
     : UseContextCost(UseContextCostForPreInliner), ContextTracker(Profiles),
       ProfileMap(Profiles), Binary(Binary), HotCountThreshold(HotThreshold),
       ColdCountThreshold(ColdThreshold) {}
 
 std::vector<StringRef> CSPreInliner::buildTopDownOrder() {
   std::vector<StringRef> Order;
   ProfiledCallGraph ProfiledCG(ContextTracker);
 
if ((ShouldInline = shouldInline(Candidate))) {
       ContextTracker.markContextSamplesInlined(Candidate.CalleeSamples);
       Candidate.CalleeSamples->getContext().setAttribute(
           ContextShouldBeInlined);
       FuncFinalSize += Candidate.SizeCost;
       getInlineCandidates(CQueue, Candidate.CalleeSamples);
     }
     LLVM_DEBUG(dbgs() << (ShouldInline ? "  Inlined" : "  Outlined")
                       << " context profile for: "
-                      << Candidate.CalleeSamples->getNameWithContext()
+                      << Candidate.CalleeSamples->getContext().toString()
                       << " (callee size: " << Candidate.SizeCost
                       << ", call count:" << Candidate.CallsiteCount << ")\n");
   }
 
   LLVM_DEBUG({
     if (!CQueue.empty())
       dbgs() << "  Inline candidates ignored due to size limit (inliner "
                 "original size: "
              << FuncSize << ", inliner final size: " << FuncFinalSize
              << ", size limit: " << SizeLimit << ")\n";
 
     while (!CQueue.empty()) {
       ProfiledInlineCandidate Candidate = CQueue.top();
       CQueue.pop();
       bool WasInlined =
           Candidate.CalleeSamples->getContext().hasAttribute(ContextWasInlined);
-      dbgs() << "    " << Candidate.CalleeSamples->getNameWithContext()
+      dbgs() << "    " << Candidate.CalleeSamples->getContext().toString()
              << " (candidate size:" << Candidate.SizeCost
              << ", call count: " << Candidate.CallsiteCount << ", previously "
              << (WasInlined ? "inlined)\n" : "not inlined)\n");
     }
   });
 }
 
 void CSPreInliner::run() {
 #ifndef NDEBUG
-  auto printProfileNames = [](StringMap<FunctionSamples> &Profiles,
-                              bool IsInput) {
+  auto printProfileNames = [](SampleProfileMap &Profiles, bool IsInput) {
     dbgs() << (IsInput ? "Input" : "Output") << " context-sensitive profiles ("
            << Profiles.size() << " total):\n";
     for (auto &It : Profiles) {
       const FunctionSamples &Samples = It.second;
-      dbgs() << "  [" << Samples.getNameWithContext() << "] "
+      dbgs() << "  [" << Samples.getContext().toString() << "] "
              << Samples.getTotalSamples() << ":" << Samples.getHeadSamples()
              << "\n";
     }
   };
 #endif
 
   LLVM_DEBUG(printProfileNames(ProfileMap, true));
 
   // Execute global pre-inliner to estimate a global top-down inline
   // decision and merge profiles accordingly. This helps with profile
   // merge for ThinLTO otherwise we won't be able to merge profiles back
   // to base profile across module/thin-backend boundaries.
   // It also helps better compress context profile to control profile
   // size, as we now only need context profile for functions going to
   // be inlined.
   for (StringRef FuncName : buildTopDownOrder()) {
     processFunction(FuncName);
   }
 
   // Not inlined context profiles are merged into its base, so we can
   // trim out such profiles from the output.
-  std::vector<StringRef> ProfilesToBeRemoved;
+  std::vector<SampleContext> ProfilesToBeRemoved;
   for (auto &It : ProfileMap) {
     SampleContext Context = It.second.getContext();
     if (!Context.isBaseContext() && !Context.hasState(InlinedContext)) {
       assert(Context.hasState(MergedContext) &&
              "Not inlined context profile should be merged already");
-      ProfilesToBeRemoved.push_back(It.first());
+      ProfilesToBeRemoved.push_back(It.first);
     }
   }
 
-  for (StringRef ContextName : ProfilesToBeRemoved) {
+  for (auto &ContextName : ProfilesToBeRemoved) {
     ProfileMap.erase(ContextName);
   }
 
   // Make sure ProfileMap's key is consistent with FunctionSamples' name.
   SampleContextTrimmer(ProfileMap).canonicalizeContextProfiles();
 
   LLVM_DEBUG(printProfileNames(ProfileMap, false));
 }

llvm/tools/llvm-profgen/CallContext.h

 #include "llvm/ProfileData/SampleProf.h"
 #include <sstream>
 #include <string>
 #include <vector>
 
 namespace llvm {
 namespace sampleprof {
 
-// Function name, LineLocation
-typedef std::pair<std::string, LineLocation> FrameLocation;
-
-typedef SmallVector<FrameLocation, 4> FrameLocationStack;
-
-inline std::string getCallSite(const FrameLocation &Callsite) {
-  std::string CallsiteStr = Callsite.first;
+inline std::string getCallSite(const SampleContextFrame &Callsite) {
+  std::string CallsiteStr = Callsite.CallerName.str();
   CallsiteStr += ":";
-  CallsiteStr += Twine(Callsite.second.LineOffset).str();
-  if (Callsite.second.Discriminator > 0) {
+  CallsiteStr += Twine(Callsite.Callsite.LineOffset).str();
+  if (Callsite.Callsite.Discriminator > 0) {
     CallsiteStr += ".";
-    CallsiteStr += Twine(Callsite.second.Discriminator).str();
+    CallsiteStr += Twine(Callsite.Callsite.Discriminator).str();
   }
   return CallsiteStr;
 }
 
 // TODO: This operation is expansive. If it ever gets called multiple times we
 // may think of making a class wrapper with internal states for it.
-inline std::string getLocWithContext(const FrameLocationStack &Context) {
+inline std::string getLocWithContext(const SampleContextFrameVector &Context) {
   std::ostringstream OContextStr;
   for (const auto &Callsite : Context) {
     if (OContextStr.str().size())
       OContextStr << " @ ";
     OContextStr << getCallSite(Callsite);
   }
   return OContextStr.str();
 }
 
 // Reverse call context, i.e., in the order of callee frames to caller frames,
 // is useful during instruction printing or pseudo probe printing.
 inline std::string
-getReversedLocWithContext(const FrameLocationStack &Context) {
+getReversedLocWithContext(const SampleContextFrameVector &Context) {
   std::ostringstream OContextStr;
   for (const auto &Callsite : reverse(Context)) {
     if (OContextStr.str().size())
       OContextStr << " @ ";
     OContextStr << getCallSite(Callsite);
   }
   return OContextStr.str();
 }
 
 } // end namespace sampleprof
 } // end namespace llvm
 
 #endif

llvm/tools/llvm-profgen/PerfReader.h

struct ContextKey {
   enum ContextKind { CK_StringBased, CK_ProbeBased };
   const ContextKind Kind;
   ContextKind getKind() const { return Kind; }
   ContextKey(ContextKind K) : Kind(K){};
 };
 
 // String based context id
 struct StringBasedCtxKey : public ContextKey {
-  std::string Context;
+  SampleContextFrameVector Context;
+
   bool WasLeafInlined;
   StringBasedCtxKey() : ContextKey(CK_StringBased), WasLeafInlined(false){};
   static bool classof(const ContextKey *K) {
     return K->getKind() == CK_StringBased;
   }
 
   bool isEqual(const ContextKey *K) const override {
     const StringBasedCtxKey *Other = dyn_cast<StringBasedCtxKey>(K);
     return Context == Other->Context;
   }
 
-  void genHashCode() { HashCode = hash_value(Context); }
+  void genHashCode() { HashCode = hash_value(SampleContextFrames(Context)); }
 };
 
 // Probe based context key as the intermediate key of context
 // String based context key will introduce redundant string handling
 // since the callee context is inferred from the context string which
 // need to be splitted by '@' to get the last location frame, so we
 // can just use probe instead and generate the string in the end.
 struct ProbeBasedCtxKey : public ContextKey {

llvm/tools/llvm-profgen/PerfReader.cpp

void VirtualUnwinder::unwindBranchWithinFrame(UnwindState &State) {
   uint64_t Source = State.getCurrentLBRSource();
   State.switchToFrame(Source);
   State.InstPtr.update(Source);
 }
 
 std::shared_ptr<StringBasedCtxKey> FrameStack::getContextKey() {
   std::shared_ptr<StringBasedCtxKey> KeyStr =
       std::make_shared<StringBasedCtxKey>();
-  KeyStr->Context =
-      Binary->getExpandedContextStr(Stack, KeyStr->WasLeafInlined);
+  KeyStr->Context = Binary->getExpandedContext(Stack, KeyStr->WasLeafInlined);
   if (KeyStr->Context.empty())
     return nullptr;
   KeyStr->genHashCode();
   return KeyStr;
 }
 
 std::shared_ptr<ProbeBasedCtxKey> ProbeStack::getContextKey() {
   std::shared_ptr<ProbeBasedCtxKey> ProbeBasedKey =
for (auto I : Range.second) {
       outs() << "  (" << format("%" PRIx64, I.first.first) << ", "
              << format("%" PRIx64, I.first.second) << "): " << I.second << "\n";
     }
   }
 }
 
 static std::string getContextKeyStr(ContextKey *K,
                                     const ProfiledBinary *Binary) {
-  std::string ContextStr;
   if (const auto *CtxKey = dyn_cast<StringBasedCtxKey>(K)) {
-    return CtxKey->Context;
+    return SampleContext::getContextString(CtxKey->Context);
   } else if (const auto *CtxKey = dyn_cast<ProbeBasedCtxKey>(K)) {
-    SmallVector<std::string, 16> ContextStack;
+    SampleContextFrameVector ContextStack;
     for (const auto *Probe : CtxKey->Probes) {
       Binary->getInlineContextForProbe(Probe, ContextStack, true);
     }
-    for (const auto &Context : ContextStack) {
-      if (ContextStr.size())
-        ContextStr += " @ ";
-      ContextStr += Context;
-    }
+    // Probe context key at this point does not have leaf probe, so do not
+    // include the leaf inline location.
+    return SampleContext::getContextString(ContextStack, true);
+  } else {
+    llvm_unreachable("unexpected key type");
   }
-  return ContextStr;
 }
 
 static void printRangeCounter(ContextSampleCounterMap &Counter,
                               const ProfiledBinary *Binary) {
   OrderedCounterForPrint OrderedCounter;
   for (auto &CI : Counter) {
     OrderedCounter[getContextKeyStr(CI.first.getPtr(), Binary)] =
         CI.second.RangeCounter;

llvm/tools/llvm-profgen/ProfileGenerator.h

public:
   ProfileGenerator(ProfiledBinary *B) : Binary(B){};
   virtual ~ProfileGenerator() = default;
   static std::unique_ptr<ProfileGenerator>
   create(ProfiledBinary *Binary, const ContextSampleCounterMap &SampleCounters,
          enum PerfScriptType SampleType);
   virtual void generateProfile() = 0;
   // Use SampleProfileWriter to serialize profile map
   virtual void write(std::unique_ptr<SampleProfileWriter> Writer,
-                     StringMap<FunctionSamples> &ProfileMap);
+                     SampleProfileMap &ProfileMap);
   void write();
 
 protected:
   /*
   For each region boundary point, mark if it is begin or end (or both) of
   the region. Boundary points are inclusive. Log the sample count as well
   so we can use it when we compute the sample count of each disjoint region
   later. Note that there might be multiple ranges with different sample
   count that share same begin/end point. We need to accumulate the sample
   count for the boundary point for such case, because for the example
   below,
 
   |<--100-->|
   |<------200------>|
   A         B       C
 
   sample count for disjoint region [A,B] would be 300.
   */
   void findDisjointRanges(RangeSample &DisjointRanges,
                           const RangeSample &Ranges);
 
   // Used by SampleProfileWriter
-  StringMap<FunctionSamples> ProfileMap;
+  SampleProfileMap ProfileMap;
 
   ProfiledBinary *Binary = nullptr;
 };
 
 class CSProfileGenerator : public ProfileGenerator {
 protected:
   const ContextSampleCounterMap &SampleCounters;
 
while (I <= MaxDedupSize) {
       I++;
       Context.resize(End);
       MaxDedupSize = std::min(static_cast<uint32_t>(End / 2), MaxDedupSize);
     }
   }
 
 protected:
   // Lookup or create FunctionSamples for the context
-  FunctionSamples &getFunctionProfileForContext(StringRef ContextId,
+  FunctionSamples &getFunctionProfileForContext(SampleContextFrames ContextId,
                                                 bool WasLeafInlined = false);
   // Post processing for profiles before writing out, such as mermining
   // and trimming cold profiles, running preinliner on profiles.
   void postProcessProfiles();
   void computeSummaryAndThreshold();
   void write(std::unique_ptr<SampleProfileWriter> Writer,
-             StringMap<FunctionSamples> &ProfileMap) override;
+             SampleProfileMap &ProfileMap) override;
 
   // Thresholds from profile summary to answer isHotCount/isColdCount queries.
   uint64_t HotCountThreshold;
   uint64_t ColdCountThreshold;
 
-  // String table owning context strings created from profile generation.
-  std::unordered_set<std::string> ContextStrings;
-
 private:
   // Helper function for updating body sample for a leaf location in
   // FunctionProfile
   void updateBodySamplesforFunctionProfile(FunctionSamples &FunctionProfile,
-                                           const FrameLocation &LeafLoc,
+                                           const SampleContextFrame &LeafLoc,
                                            uint64_t Count);
   void populateFunctionBodySamples(FunctionSamples &FunctionProfile,
                                    const RangeSample &RangeCounters);
-  void populateFunctionBoundarySamples(StringRef ContextId,
+  void populateFunctionBoundarySamples(SampleContextFrames ContextId,
                                        FunctionSamples &FunctionProfile,
                                        const BranchSample &BranchCounters);
   void populateInferredFunctionSamples();
 
 public:
   // Deduplicate adjacent repeated context sequences up to a given sequence
   // length. -1 means no size limit.
   static int32_t MaxCompressionSize;
public:
   void generateProfile() override;
 
 private:
   // Go through each address from range to extract the top frame probe by
   // looking up in the Address2ProbeMap
   void extractProbesFromRange(const RangeSample &RangeCounter,
                               ProbeCounterMap &ProbeCounter);
   // Fill in function body samples from probes
-  void
-  populateBodySamplesWithProbes(const RangeSample &RangeCounter,
-                                SmallVectorImpl<std::string> &ContextStrStack);
+  void populateBodySamplesWithProbes(const RangeSample &RangeCounter,
+                                     SampleContextFrames ContextStack);
   // Fill in boundary samples for a call probe
-  void populateBoundarySamplesWithProbes(
-      const BranchSample &BranchCounter,
-      SmallVectorImpl<std::string> &ContextStrStack);
-  // Helper function to get FunctionSamples for the leaf inlined context
-  FunctionSamples &
-  getFunctionProfileForLeafProbe(SmallVectorImpl<std::string> &ContextStrStack,
-                                 const MCPseudoProbeFuncDesc *LeafFuncDesc,
-                                 bool WasLeafInlined);
+  void populateBoundarySamplesWithProbes(const BranchSample &BranchCounter,
+                                         SampleContextFrames ContextStack);
   // Helper function to get FunctionSamples for the leaf probe
   FunctionSamples &
-  getFunctionProfileForLeafProbe(SmallVectorImpl<std::string> &ContextStrStack,
+  getFunctionProfileForLeafProbe(SampleContextFrames ContextStack,
                                  const MCDecodedPseudoProbe *LeafProbe);
+
+  // Underlying context table serves for sample profile writer.
+  std::unordered_set<SampleContextFrameVector, SampleContextFrameHash> Contexts;
 };
 
 } // end namespace sampleprof
 } // end namespace llvm
 
 #endif

llvm/tools/llvm-profgen/ProfileGenerator.cpp

if (SampleType == PERF_LBR_STACK) {
     // TODO:
     llvm_unreachable("Unsupported perfscript!");
   }
 
   return ProfileGenerator;
 }
 
 void ProfileGenerator::write(std::unique_ptr<SampleProfileWriter> Writer,
-                             StringMap<FunctionSamples> &ProfileMap) {
+                             SampleProfileMap &ProfileMap) {
   if (std::error_code EC = Writer->write(ProfileMap))
     exitWithError(std::move(EC));
 }
 
 void ProfileGenerator::write() {
   auto WriterOrErr = SampleProfileWriter::create(OutputFilename, OutputFormat);
   if (std::error_code EC = WriterOrErr.getError())
     exitWithError(EC, OutputFilename);
if (Point.EndCount) {
       DisjointRanges[{BeginAddress, Address}] = Count;
       Count -= Point.EndCount;
       BeginAddress = Address + 1;
     }
   }
 }
 
 FunctionSamples &
-CSProfileGenerator::getFunctionProfileForContext(StringRef ContextStr,
+CSProfileGenerator::getFunctionProfileForContext(SampleContextFrames Context,
                                                  bool WasLeafInlined) {
-  auto Ret = ProfileMap.try_emplace(ContextStr, FunctionSamples());
+  SampleContext FContext(Context);
+  auto Ret = ProfileMap.emplace(Context, FunctionSamples());
   if (Ret.second) {
-    // Make a copy of the underlying context string in string table
-    // before StringRef wrapper is used for context.
-    auto It = ContextStrings.insert(ContextStr.str());
-    SampleContext FContext(*It.first, RawContext);
+    SampleContext FContext(Context, RawContext);
     if (WasLeafInlined)
       FContext.setAttribute(ContextWasInlined);
     FunctionSamples &FProfile = Ret.first->second;
     FProfile.setContext(FContext);
-    FProfile.setName(FContext.getNameWithoutContext());
   }
   return Ret.first->second;
 }
 
 void CSProfileGenerator::generateProfile() {
   FunctionSamples::ProfileIsCS = true;
   for (const auto &CI : SampleCounters) {
     const StringBasedCtxKey *CtxKey =
         dyn_cast<StringBasedCtxKey>(CI.first.getPtr());
-    StringRef ContextId(CtxKey->Context);
     // Get or create function profile for the range
     FunctionSamples &FunctionProfile =
-        getFunctionProfileForContext(ContextId, CtxKey->WasLeafInlined);
+        getFunctionProfileForContext(CtxKey->Context, CtxKey->WasLeafInlined);
 
     // Fill in function body samples
     populateFunctionBodySamples(FunctionProfile, CI.second.RangeCounter);
     // Fill in boundary sample counts as well as call site samples for calls
-    populateFunctionBoundarySamples(ContextId, FunctionProfile,
+    populateFunctionBoundarySamples(CtxKey->Context, FunctionProfile,
                                     CI.second.BranchCounter);
   }
   // Fill in call site value sample for inlined calls and also use context to
   // infer missing samples. Since we don't have call count for inlined
   // functions, we estimate it from inlinee's profile using the entry of the
   // body sample.
   populateInferredFunctionSamples();
 
   postProcessProfiles();
 }
 
 void CSProfileGenerator::updateBodySamplesforFunctionProfile(
-    FunctionSamples &FunctionProfile, const FrameLocation &LeafLoc,
+    FunctionSamples &FunctionProfile, const SampleContextFrame &LeafLoc,
     uint64_t Count) {
   // Filter out invalid negative(int type) lineOffset
-  if (LeafLoc.second.LineOffset & 0x80000000)
+  if (LeafLoc.Callsite.LineOffset & 0x80000000)
     return;
   // Use the maximum count of samples with same line location
   ErrorOr<uint64_t> R = FunctionProfile.findSamplesAt(
-      LeafLoc.second.LineOffset, LeafLoc.second.Discriminator);
+      LeafLoc.Callsite.LineOffset, LeafLoc.Callsite.Discriminator);
   uint64_t PreviousCount = R ? R.get() : 0;
   if (PreviousCount < Count) {
-    FunctionProfile.addBodySamples(LeafLoc.second.LineOffset,
-                                   LeafLoc.second.Discriminator,
+    FunctionProfile.addBodySamples(LeafLoc.Callsite.LineOffset,
+                                   LeafLoc.Callsite.Discriminator,
                                    Count - PreviousCount);
   }
 }
 
 void CSProfileGenerator::populateFunctionBodySamples(
     FunctionSamples &FunctionProfile, const RangeSample &RangeCounter) {
   // Compute disjoint ranges first, so we can use MAX
   // for calculating count for each location.
while (IP.Address <= RangeEnd) {
       FunctionProfile.addTotalSamples(Count);
       // Move to next IP within the range
       IP.advance();
     }
   }
 }
 
 void CSProfileGenerator::populateFunctionBoundarySamples(
-    StringRef ContextId, FunctionSamples &FunctionProfile,
+    SampleContextFrames ContextId, FunctionSamples &FunctionProfile,
     const BranchSample &BranchCounters) {
 
   for (auto Entry : BranchCounters) {
     uint64_t SourceOffset = Entry.first.first;
     uint64_t TargetOffset = Entry.first.second;
     uint64_t Count = Entry.second;
     // Get the callee name by branch target if it's a call branch
     StringRef CalleeName = FunctionSamples::getCanonicalFnName(
         Binary->getFuncFromStartOffset(TargetOffset));
     if (CalleeName.size() == 0)
       continue;
 
     // Record called target sample and its count
     auto LeafLoc = Binary->getInlineLeafFrameLoc(SourceOffset);
     if (!LeafLoc.hasValue())
       continue;
-    FunctionProfile.addCalledTargetSamples(LeafLoc->second.LineOffset,
-                                           LeafLoc->second.Discriminator,
+    FunctionProfile.addCalledTargetSamples(LeafLoc->Callsite.LineOffset,
+                                           LeafLoc->Callsite.Discriminator,
                                            CalleeName, Count);
 
     // Record head sample for called target(callee)
-    std::ostringstream OCalleeCtxStr;
-    if (ContextId.find(" @ ") != StringRef::npos) {
-      OCalleeCtxStr << ContextId.rsplit(" @ ").first.str();
-      OCalleeCtxStr << " @ ";
-    }
-    OCalleeCtxStr << getCallSite(*LeafLoc) << " @ " << CalleeName.str();
-
-    FunctionSamples &CalleeProfile =
-        getFunctionProfileForContext(OCalleeCtxStr.str());
+    SampleContextFrameVector CalleeCtx(ContextId.begin(), ContextId.end());
+    assert(CalleeCtx.back().CallerName == LeafLoc->CallerName &&
+           "Leaf function name doesn't match");
+    CalleeCtx.back() = *LeafLoc;
+    CalleeCtx.emplace_back(CalleeName, LineLocation(0, 0));
+    FunctionSamples &CalleeProfile = getFunctionProfileForContext(CalleeCtx);
     assert(Count != 0 && "Unexpected zero weight branch");
     CalleeProfile.addHeadSamples(Count);
   }
 }
 
-static FrameLocation getCallerContext(StringRef CalleeContext,
-                                      StringRef &CallerNameWithContext) {
-  StringRef CallerContext = CalleeContext.rsplit(" @ ").first;
-  CallerNameWithContext = CallerContext.rsplit(':').first;
-  auto ContextSplit = CallerContext.rsplit(" @ ");
-  StringRef CallerFrameStr = ContextSplit.second.size() == 0
-                                 ? ContextSplit.first
-                                 : ContextSplit.second;
-  FrameLocation LeafFrameLoc = {"", {0, 0}};
-  StringRef Funcname;
-  SampleContext::decodeContextString(CallerFrameStr, Funcname,
-                                     LeafFrameLoc.second);
-  LeafFrameLoc.first = Funcname.str();
-  return LeafFrameLoc;
+static SampleContextFrame
+getCallerContext(SampleContextFrames CalleeContext,
+                 SampleContextFrameVector &CallerContext) {
+  assert(CalleeContext.size() > 1 && "Unexpected empty context");
+  CalleeContext = CalleeContext.drop_back();
+  CallerContext.assign(CalleeContext.begin(), CalleeContext.end());
+  SampleContextFrame CallerFrame = CallerContext.back();
+  CallerContext.back().Callsite = LineLocation(0, 0);
+  return CallerFrame;
 }
 
 void CSProfileGenerator::populateInferredFunctionSamples() {
   for (const auto &Item : ProfileMap) {
-    const StringRef CalleeContext = Item.first();
+    const auto &CalleeContext = Item.first;
     const FunctionSamples &CalleeProfile = Item.second;
 
     // If we already have head sample counts, we must have value profile
     // for call sites added already. Skip to avoid double counting.
     if (CalleeProfile.getHeadSamples())
       continue;
     // If we don't have context, nothing to do for caller's call site.
     // This could happen for entry point function.
-    if (CalleeContext.find(" @ ") == StringRef::npos)
+    if (CalleeContext.isBaseContext())
       continue;
 
     // Infer Caller's frame loc and context ID through string splitting
-    StringRef CallerContextId;
-    FrameLocation &&CallerLeafFrameLoc =
-        getCallerContext(CalleeContext, CallerContextId);
+    SampleContextFrameVector CallerContextId;
+    SampleContextFrame &&CallerLeafFrameLoc =
+        getCallerContext(CalleeContext.getContextFrames(), CallerContextId);
+    SampleContextFrames CallerContext(CallerContextId);
 
     // It's possible that we haven't seen any sample directly in the caller,
     // in which case CallerProfile will not exist. But we can't modify
     // ProfileMap while iterating it.
     // TODO: created function profile for those callers too
-    if (ProfileMap.find(CallerContextId) == ProfileMap.end())
+    if (ProfileMap.find(CallerContext) == ProfileMap.end())
       continue;
-    FunctionSamples &CallerProfile = ProfileMap[CallerContextId];
+    FunctionSamples &CallerProfile = ProfileMap[CallerContext];
 
     // Since we don't have call count for inlined functions, we
     // estimate it from inlinee's profile using entry body sample.
     uint64_t EstimatedCallCount = CalleeProfile.getEntrySamples();
     // If we don't have samples with location, use 1 to indicate live.
     if (!EstimatedCallCount && !CalleeProfile.getBodySamples().size())
       EstimatedCallCount = 1;
     CallerProfile.addCalledTargetSamples(
-        CallerLeafFrameLoc.second.LineOffset,
-        CallerLeafFrameLoc.second.Discriminator,
-        CalleeProfile.getContext().getNameWithoutContext(), EstimatedCallCount);
-    CallerProfile.addBodySamples(CallerLeafFrameLoc.second.LineOffset,
-                                 CallerLeafFrameLoc.second.Discriminator,
+        CallerLeafFrameLoc.Callsite.LineOffset,
+        CallerLeafFrameLoc.Callsite.Discriminator,
+        CalleeProfile.getContext().getName(), EstimatedCallCount);
+    CallerProfile.addBodySamples(CallerLeafFrameLoc.Callsite.LineOffset,
+                                 CallerLeafFrameLoc.Callsite.Discriminator,
                                  EstimatedCallCount);
     CallerProfile.addTotalSamples(EstimatedCallCount);
   }
 }
 
 void CSProfileGenerator::postProcessProfiles() {
   // Compute hot/cold threshold based on profile. This will be used for cold
   // context profile merging/trimming.
void CSProfileGenerator::computeSummaryAndThreshold() {
   auto Summary = Builder.computeSummaryForProfiles(ProfileMap);
   HotCountThreshold = ProfileSummaryBuilder::getHotCountThreshold(
       (Summary->getDetailedSummary()));
   ColdCountThreshold = ProfileSummaryBuilder::getColdCountThreshold(
       (Summary->getDetailedSummary()));
 }
 
 void CSProfileGenerator::write(std::unique_ptr<SampleProfileWriter> Writer,
-                               StringMap<FunctionSamples> &ProfileMap) {
+                               SampleProfileMap &ProfileMap) {
   if (std::error_code EC = Writer->write(ProfileMap))
     exitWithError(std::move(EC));
 }
 
 // Helper function to extract context prefix string stack
 // Extract context stack for reusing, leaf context stack will
 // be added compressed while looking up function profile
 static void extractPrefixContextStack(
-    SmallVectorImpl<std::string> &ContextStrStack,
+    SampleContextFrameVector &ContextStack,
     const SmallVectorImpl<const MCDecodedPseudoProbe *> &Probes,
     ProfiledBinary *Binary) {
   for (const auto *P : Probes) {
-    Binary->getInlineContextForProbe(P, ContextStrStack, true);
+    Binary->getInlineContextForProbe(P, ContextStack, true);
   }
 }
 
 void PseudoProbeCSProfileGenerator::generateProfile() {
   // Enable pseudo probe functionalities in SampleProf
   FunctionSamples::ProfileIsProbeBased = true;
   FunctionSamples::ProfileIsCS = true;
   for (const auto &CI : SampleCounters) {
     const ProbeBasedCtxKey *CtxKey =
         dyn_cast<ProbeBasedCtxKey>(CI.first.getPtr());
-    SmallVector<std::string, 16> ContextStrStack;
-    extractPrefixContextStack(ContextStrStack, CtxKey->Probes, Binary);
+    SampleContextFrameVector ContextStack;
+    extractPrefixContextStack(ContextStack, CtxKey->Probes, Binary);
     // Fill in function body samples from probes, also infer caller's samples
     // from callee's probe
-    populateBodySamplesWithProbes(CI.second.RangeCounter, ContextStrStack);
+    populateBodySamplesWithProbes(CI.second.RangeCounter, ContextStack);
     // Fill in boundary samples for a call probe
-    populateBoundarySamplesWithProbes(CI.second.BranchCounter, ContextStrStack);
+    populateBoundarySamplesWithProbes(CI.second.BranchCounter, ContextStack);
   }
 
   postProcessProfiles();
 }
 
 void PseudoProbeCSProfileGenerator::extractProbesFromRange(
     const RangeSample &RangeCounter, ProbeCounterMap &ProbeCounter) {
   RangeSample Ranges;
while (IP.Address <= RangeEnd) {
       }
 
       IP.advance();
     }
   }
 }
 
 void PseudoProbeCSProfileGenerator::populateBodySamplesWithProbes(
-    const RangeSample &RangeCounter,
-    SmallVectorImpl<std::string> &ContextStrStack) {
+    const RangeSample &RangeCounter, SampleContextFrames ContextStack) {
   ProbeCounterMap ProbeCounter;
   // Extract the top frame probes by looking up each address among the range in
   // the Address2ProbeMap
   extractProbesFromRange(RangeCounter, ProbeCounter);
   std::unordered_map<MCDecodedPseudoProbeInlineTree *,
                      std::unordered_set<FunctionSamples *>>
       FrameSamples;
   for (auto PI : ProbeCounter) {
     const MCDecodedPseudoProbe *Probe = PI.first;
     uint64_t Count = PI.second;
     FunctionSamples &FunctionProfile =
-        getFunctionProfileForLeafProbe(ContextStrStack, Probe);
+        getFunctionProfileForLeafProbe(ContextStack, Probe);
     // Record the current frame and FunctionProfile whenever samples are
     // collected for non-danglie probes. This is for reporting all of the
     // zero count probes of the frame later.
     FrameSamples[Probe->getInlineTreeNode()].insert(&FunctionProfile);
     FunctionProfile.addBodySamplesForProbe(Probe->getIndex(), Count);
     FunctionProfile.addTotalSamples(Count);
     if (Probe->isEntry()) {
       FunctionProfile.addHeadSamples(Count);
       // Look up for the caller's function profile
       const auto *InlinerDesc = Binary->getInlinerDescForProbe(Probe);
       if (InlinerDesc != nullptr) {
         // Since the context id will be compressed, we have to use callee's
         // context id to infer caller's context id to ensure they share the
         // same context prefix.
-        StringRef CalleeContextId =
-            FunctionProfile.getContext().getNameWithContext();
-        StringRef CallerContextId;
-        FrameLocation &&CallerLeafFrameLoc =
+        SampleContextFrames CalleeContextId =
+            FunctionProfile.getContext().getContextFrames();
+        SampleContextFrameVector CallerContextId;
+        SampleContextFrame &&CallerLeafFrameLoc =
             getCallerContext(CalleeContextId, CallerContextId);
-        uint64_t CallerIndex = CallerLeafFrameLoc.second.LineOffset;
+        uint64_t CallerIndex = CallerLeafFrameLoc.Callsite.LineOffset;
         assert(CallerIndex &&
                "Inferred caller's location index shouldn't be zero!");
+        // Save the new context for future references.
+        SampleContextFrames CallerContext =
+            *Contexts.insert(CallerContextId).first;
         FunctionSamples &CallerProfile =
-            getFunctionProfileForContext(CallerContextId);
+            getFunctionProfileForContext(CallerContext);
         CallerProfile.setFunctionHash(InlinerDesc->FuncHash);
         CallerProfile.addBodySamples(CallerIndex, 0, Count);
         CallerProfile.addTotalSamples(Count);
         CallerProfile.addCalledTargetSamples(
-            CallerIndex, 0,
-            FunctionProfile.getContext().getNameWithoutContext(), Count);
+            CallerIndex, 0, FunctionProfile.getContext().getName(), Count);
       }
     }
   }
 
   // Assign zero count for remaining probes without sample hits to
   // differentiate from probes optimized away, of which the counts are unknown
   // and will be inferred by the compiler.
   for (auto &I : FrameSamples) {
     for (auto *FunctionProfile : I.second) {
       for (auto *Probe : I.first->getProbes()) {
         FunctionProfile->addBodySamplesForProbe(Probe->getIndex(), 0);
       }
     }
   }
 }
 
 void PseudoProbeCSProfileGenerator::populateBoundarySamplesWithProbes(
-    const BranchSample &BranchCounter,
-    SmallVectorImpl<std::string> &ContextStrStack) {
+    const BranchSample &BranchCounter, SampleContextFrames ContextStack) {
   for (auto BI : BranchCounter) {
     uint64_t SourceOffset = BI.first.first;
     uint64_t TargetOffset = BI.first.second;
     uint64_t Count = BI.second;
     uint64_t SourceAddress = Binary->offsetToVirtualAddr(SourceOffset);
     const MCDecodedPseudoProbe *CallProbe =
         Binary->getCallProbeForAddr(SourceAddress);
     if (CallProbe == nullptr)
       continue;
     FunctionSamples &FunctionProfile =
-        getFunctionProfileForLeafProbe(ContextStrStack, CallProbe);
+        getFunctionProfileForLeafProbe(ContextStack, CallProbe);
     FunctionProfile.addBodySamples(CallProbe->getIndex(), 0, Count);
     FunctionProfile.addTotalSamples(Count);
     StringRef CalleeName = FunctionSamples::getCanonicalFnName(
         Binary->getFuncFromStartOffset(TargetOffset));
     if (CalleeName.size() == 0)
       continue;
     FunctionProfile.addCalledTargetSamples(CallProbe->getIndex(), 0, CalleeName,
                                            Count);
   }
 }
 
 FunctionSamples &PseudoProbeCSProfileGenerator::getFunctionProfileForLeafProbe(
-    SmallVectorImpl<std::string> &ContextStrStack,
-    const MCPseudoProbeFuncDesc *LeafFuncDesc, bool WasLeafInlined) {
-  assert(ContextStrStack.size() && "Profile context must have the leaf frame");
-  // Compress the context string except for the leaf frame
-  std::string LeafFrame = ContextStrStack.back();
-  ContextStrStack.pop_back();
-  CSProfileGenerator::compressRecursionContext(ContextStrStack);
-  CSProfileGenerator::trimContext(ContextStrStack);
-
-  std::ostringstream OContextStr;
-  for (uint32_t I = 0; I < ContextStrStack.size(); I++) {
-    if (OContextStr.str().size())
-      OContextStr << " @ ";
-    OContextStr << ContextStrStack[I];
-  }
+    SampleContextFrames ContextStack, const MCDecodedPseudoProbe *LeafProbe) {
+
+  // Explicitly copy the context for appending the leaf context
+  SampleContextFrameVector NewContextStack(ContextStack.begin(),
+                                           ContextStack.end());
+  Binary->getInlineContextForProbe(LeafProbe, NewContextStack, true);
   // For leaf inlined context with the top frame, we should strip off the top
   // frame's probe id, like:
   // Inlined stack: [foo:1, bar:2], the ContextId will be "foo:1 @ bar"
-  if (OContextStr.str().size())
-    OContextStr << " @ ";
-  OContextStr << StringRef(LeafFrame).split(":").first.str();
-
-  FunctionSamples &FunctionProile =
-      getFunctionProfileForContext(OContextStr.str(), WasLeafInlined);
-  FunctionProile.setFunctionHash(LeafFuncDesc->FuncHash);
-  return FunctionProile;
-}
-
-FunctionSamples &PseudoProbeCSProfileGenerator::getFunctionProfileForLeafProbe(
-    SmallVectorImpl<std::string> &ContextStrStack,
-    const MCDecodedPseudoProbe *LeafProbe) {
+  auto LeafFrame = NewContextStack.back();
+  LeafFrame.Callsite = LineLocation(0, 0);
+  NewContextStack.pop_back();
+  // Compress the context string except for the leaf frame
+  CSProfileGenerator::compressRecursionContext(NewContextStack);
+  CSProfileGenerator::trimContext(NewContextStack);
+  NewContextStack.push_back(LeafFrame);
+  // Save the new context for future references.
+  SampleContextFrames NewContext = *Contexts.insert(NewContextStack).first;
 
-  // Explicitly copy the context for appending the leaf context
-  SmallVector<std::string, 16> ContextStrStackCopy(ContextStrStack.begin(),
-                                                   ContextStrStack.end());
-  Binary->getInlineContextForProbe(LeafProbe, ContextStrStackCopy, true);
   const auto *FuncDesc = Binary->getFuncDescForGUID(LeafProbe->getGuid());
   bool WasLeafInlined = LeafProbe->getInlineTreeNode()->hasInlineSite();
-  return getFunctionProfileForLeafProbe(ContextStrStackCopy, FuncDesc,
-                                        WasLeafInlined);
+  FunctionSamples &FunctionProile =
+      getFunctionProfileForContext(NewContext, WasLeafInlined);
+  FunctionProile.setFunctionHash(FuncDesc->FuncHash);
+  return FunctionProile;
 }
 
 } // end namespace sampleprof
 } // end namespace llvm

llvm/tools/llvm-profgen/ProfiledBinary.h

 // accurate post-optimization size to make decisions.
 // TODO: If an inlinee is completely optimized away, ideally we should have zero
 // for its context size, currently we would misss such context since it doesn't
 // have instructions. To fix this, we need to mark all inlinee with entry probe
 // but without instructions as having zero size.
 class BinarySizeContextTracker {
 public:
   // Add instruction with given size to a context
-  void addInstructionForContext(const FrameLocationStack &Context,
+  void addInstructionForContext(const SampleContextFrameVector &Context,
                                 uint32_t InstrSize);
 
   // Get function size with a specific context. When there's no exact match
   // for the given context, try to retrieve the size of that function from
   // closest matching context.
   uint32_t getFuncSizeForContext(const SampleContext &Context);
 
   // For inlinees that are full optimized away, we can establish zero size using
class ProfiledBinary {
   std::unique_ptr<const MCInstrAnalysis> MIA;
   std::unique_ptr<MCInstPrinter> IPrinter;
   // A list of text sections sorted by start RVA and size. Used to check
   // if a given RVA is a valid code address.
   std::set<std::pair<uint64_t, uint64_t>> TextSections;
   // Function offset to name mapping.
   std::unordered_map<uint64_t, std::string> FuncStartAddrMap;
   // Offset to context location map. Used to expand the context.
-  std::unordered_map<uint64_t, FrameLocationStack> Offset2LocStackMap;
+  std::unordered_map<uint64_t, SampleContextFrameVector> Offset2LocStackMap;
   // An array of offsets of all instructions sorted in increasing order. The
   // sorting is needed to fast advance to the next forward/backward instruction.
   std::vector<uint64_t> CodeAddrs;
   // A set of call instruction offsets. Used by virtual unwinding.
   std::unordered_set<uint64_t> CallAddrs;
   // A set of return instruction offsets. Used by virtual unwinding.
   std::unordered_set<uint64_t> RetAddrs;
 
   // Estimate and track function prolog and epilog ranges.
   PrologEpilogTracker ProEpilogTracker;
 
   // Track function sizes under different context
   BinarySizeContextTracker FuncSizeTracker;
 
   // The symbolizer used to get inline context for an instruction.
   std::unique_ptr<symbolize::LLVMSymbolizer> Symbolizer;
 
+  // String table owning function name strings created from the symbolizer.
+  std::unordered_set<std::string> NameStrings;
+
   // Pseudo probe decoder
   MCPseudoProbeDecoder ProbeDecoder;
 
   bool UsePseudoProbes = false;
 
   // Whether we need to symbolize all instructions to get function context size.
   bool TrackFuncContextSize = false;
 
class ProfiledBinary {
 
   /// Dissassemble the text section and build various address maps.
   void disassemble(const ELFObjectFileBase *O);
 
   /// Helper function to dissassemble the symbol and extract info for unwinding
   bool dissassembleSymbol(std::size_t SI, ArrayRef<uint8_t> Bytes,
                           SectionSymbolsTy &Symbols, const SectionRef &Section);
   /// Symbolize a given instruction pointer and return a full call context.
-  FrameLocationStack symbolize(const InstructionPointer &IP,
+  SampleContextFrameVector symbolize(const InstructionPointer &IP,
                                      bool UseCanonicalFnName = false,
                                      bool UseProbeDiscriminator = false);
 
   /// Decode the interesting parts of the binary and build internal data
   /// structures. On high level, the parts of interest are:
   ///   1. Text sections, including the main code section and the PLT
   ///   entries that will be used to handle cross-module call transitions.
   ///   2. The .debug_line section, used by Dwarf-based profile generation.
   ///   3. Pseudo probe related sections, used by probe-based profile
   ///   generation.
   void load();
-  const FrameLocationStack &getFrameLocationStack(uint64_t Offset) const {
+  const SampleContextFrameVector &getFrameLocationStack(uint64_t Offset) const {
     auto I = Offset2LocStackMap.find(Offset);
     assert(I != Offset2LocStackMap.end() &&
            "Can't find location for offset in the binary");
     return I->second;
   }
 
 public:
   ProfiledBinary(const StringRef Path)
public:
   StringRef getFuncFromStartOffset(uint64_t Offset) {
     return FuncStartAddrMap[Offset];
   }
 
   uint32_t getFuncSizeForContext(SampleContext &Context) {
     return FuncSizeTracker.getFuncSizeForContext(Context);
   }
 
-  Optional<FrameLocation> getInlineLeafFrameLoc(uint64_t Offset) {
+  Optional<SampleContextFrame> getInlineLeafFrameLoc(uint64_t Offset) {
     const auto &Stack = getFrameLocationStack(Offset);
     if (Stack.empty())
       return {};
     return Stack.back();
   }
 
   // Compare two addresses' inline context
   bool inlineContextEqual(uint64_t Add1, uint64_t Add2) const;
 
-  // Get the context string of the current stack with inline context filled in.
+  // Get the full context of the current stack with inline context filled in.
   // It will search the disassembling info stored in Offset2LocStackMap. This is
   // used as the key of function sample map
-  std::string getExpandedContextStr(const SmallVectorImpl<uint64_t> &Stack,
-                                    bool &WasLeafInlined) const;
+  SampleContextFrameVector
+  getExpandedContext(const SmallVectorImpl<uint64_t> &Stack,
 
   const MCDecodedPseudoProbe *getCallProbeForAddr(uint64_t Address) const {
     return ProbeDecoder.getCallProbeForAddr(Address);
   }
 
-  void
-  getInlineContextForProbe(const MCDecodedPseudoProbe *Probe,
-                           SmallVectorImpl<std::string> &InlineContextStack,
+  void getInlineContextForProbe(const MCDecodedPseudoProbe *Probe,
+                                SampleContextFrameVector &InlineContextStack,
                                 bool IncludeLeaf = false) const {
-    return ProbeDecoder.getInlineContextForProbe(Probe, InlineContextStack,
-                                                 IncludeLeaf);
+    SmallVector<MCPseduoProbeFrameLocation, 16> ProbeInlineContext;
+    ProbeDecoder.getInlineContextForProbe(Probe, ProbeInlineContext,
+    for (auto &Callsite : ProbeInlineContext) {
+      InlineContextStack.emplace_back(Callsite.first,
+                                      LineLocation(Callsite.second, 0));
+    }
   }
   const AddressProbesMap &getAddress2ProbesMap() const {
     return ProbeDecoder.getAddress2ProbesMap();
   }
   const MCPseudoProbeFuncDesc *getFuncDescForGUID(uint64_t GUID) {
     return ProbeDecoder.getFuncDescForGUID(GUID);
   }
 

llvm/tools/llvm-profgen/ProfiledBinary.cpp

static const Target *getTarget(const ObjectFile *Obj) {
   const Target *TheTarget =
       TargetRegistry::lookupTarget(ArchName, TheTriple, Error);
   if (!TheTarget)
     exitWithError(Error, Obj->getFileName());
   return TheTarget;
 }
 
 void BinarySizeContextTracker::addInstructionForContext(
-    const FrameLocationStack &Context, uint32_t InstrSize) {
+    const SampleContextFrameVector &Context, uint32_t InstrSize) {
   ContextTrieNode *CurNode = &RootContext;
   bool IsLeaf = true;
   for (const auto &Callsite : reverse(Context)) {
-    StringRef CallerName = Callsite.first;
-    LineLocation CallsiteLoc = IsLeaf ? LineLocation(0, 0) : Callsite.second;
+    StringRef CallerName = Callsite.CallerName;
+    LineLocation CallsiteLoc = IsLeaf ? LineLocation(0, 0) : Callsite.Callsite;
     CurNode = CurNode->getOrCreateChildContext(CallsiteLoc, CallerName);
     IsLeaf = false;
   }
 
   CurNode->addFunctionSize(InstrSize);
 }
 
 uint32_t
 BinarySizeContextTracker::getFuncSizeForContext(const SampleContext &Context) {
   ContextTrieNode *CurrNode = &RootContext;
   ContextTrieNode *PrevNode = nullptr;
-  StringRef ContextRemain = Context;
-  StringRef ChildContext;
-  StringRef CallerName;
+  SampleContextFrames Frames = Context.getContextFrames();
+  int32_t I = Frames.size() - 1;
   Optional<uint32_t> Size;
 
-  // Start from top-level context-less function, travese down the reverse
+  // Start from top-level context-less function, traverse down the reverse
   // context trie to find the best/longest match for given context, then
   // retrieve the size.
-  while (CurrNode && !ContextRemain.empty()) {
-    // rsplit so we process from leaf function to callers (added to context).
-    auto ContextSplit = SampleContext::rsplitContextString(ContextRemain);
-    ChildContext = ContextSplit.second;
-    ContextRemain = ContextSplit.first;
-    LineLocation CallSiteLoc(0, 0);
-    SampleContext::decodeContextString(ChildContext, CallerName, CallSiteLoc);
+
+  while (CurrNode && I >= 0) {
+    // Process from leaf function to callers (added to context).
+    const auto &ChildFrame = Frames[I--];
     PrevNode = CurrNode;
-    CurrNode = CurrNode->getChildContext(CallSiteLoc, CallerName);
+    CurrNode =
+        CurrNode->getChildContext(ChildFrame.Callsite, ChildFrame.CallerName);
     if (CurrNode && CurrNode->getFunctionSize().hasValue())
       Size = CurrNode->getFunctionSize().getValue();
   }
 
   // If we traversed all nodes along the path of the context and haven't
   // found a size yet, pivot to look for size from sibling nodes, i.e size
   // of inlinee under different context.
   if (!Size.hasValue()) {
void ProfiledBinary::load() {
 
   // TODO: decode other sections.
 }
 
 bool ProfiledBinary::inlineContextEqual(uint64_t Address1,
                                         uint64_t Address2) const {
   uint64_t Offset1 = virtualAddrToOffset(Address1);
   uint64_t Offset2 = virtualAddrToOffset(Address2);
-  const FrameLocationStack &Context1 = getFrameLocationStack(Offset1);
-  const FrameLocationStack &Context2 = getFrameLocationStack(Offset2);
+  const SampleContextFrameVector &Context1 = getFrameLocationStack(Offset1);
+  const SampleContextFrameVector &Context2 = getFrameLocationStack(Offset2);
   if (Context1.size() != Context2.size())
     return false;
   if (Context1.empty())
     return false;
   // The leaf frame contains location within the leaf, and it
   // needs to be remove that as it's not part of the calling context
   return std::equal(Context1.begin(), Context1.begin() + Context1.size() - 1,
                     Context2.begin(), Context2.begin() + Context2.size() - 1);
 }
 
-std::string
-ProfiledBinary::getExpandedContextStr(const SmallVectorImpl<uint64_t> &Stack,
-                                      bool &WasLeafInlined) const {
-  std::string ContextStr;
-  SmallVector<std::string, 16> ContextVec;
+SampleContextFrameVector
+ProfiledBinary::getExpandedContext(const SmallVectorImpl<uint64_t> &Stack,
+  SampleContextFrameVector ContextVec;
   // Process from frame root to leaf
   for (auto Address : Stack) {
     uint64_t Offset = virtualAddrToOffset(Address);
-    const FrameLocationStack &ExpandedContext = getFrameLocationStack(Offset);
+    const SampleContextFrameVector &ExpandedContext =
+        getFrameLocationStack(Offset);
     // An instruction without a valid debug line will be ignored by sample
     // processing
     if (ExpandedContext.empty())
-      return std::string();
+      return SampleContextFrameVector();
     // Set WasLeafInlined to the size of inlined frame count for the last
     // address which is leaf
     WasLeafInlined = (ExpandedContext.size() > 1);
-    for (const auto &Loc : ExpandedContext) {
-      ContextVec.push_back(getCallSite(Loc));
-    }
+    ContextVec.append(ExpandedContext);
   }
 
-  assert(ContextVec.size() && "Context length should be at least 1");
   // Compress the context string except for the leaf frame
-  std::string LeafFrame = ContextVec.back();
+  auto LeafFrame = ContextVec.back();
+  LeafFrame.Callsite = LineLocation(0, 0);
   ContextVec.pop_back();
-  CSProfileGenerator::compressRecursionContext<std::string>(ContextVec);
-  CSProfileGenerator::trimContext<std::string>(ContextVec);
-
-  std::ostringstream OContextStr;
-  for (uint32_t I = 0; I < (uint32_t)ContextVec.size(); I++) {
-    if (OContextStr.str().size()) {
-      OContextStr << " @ ";
-    }
-    OContextStr << ContextVec[I];
-  }
-  // Only keep the function name for the leaf frame
-  if (OContextStr.str().size())
-    OContextStr << " @ ";
-  OContextStr << StringRef(LeafFrame).split(":").first.str();
-  return OContextStr.str();
+  assert(ContextVec.size() && "Context length should be at least 1");
+  CSProfileGenerator::compressRecursionContext(ContextVec);
+  CSProfileGenerator::trimContext(ContextVec);
+  ContextVec.push_back(LeafFrame);
+  return ContextVec;
 }
 
 template <class ELFT>
 void ProfiledBinary::setPreferredTextSegmentAddresses(const ELFFile<ELFT> &Obj, StringRef FileName) {
   const auto &PhdrRange = unwrapOrError(Obj.program_headers(), FileName);
   for (const typename ELFT::Phdr &Phdr : PhdrRange) {
     if ((Phdr.p_type == ELF::PT_LOAD) && (Phdr.p_flags & ELF::PF_X)) {
         // Segments will always be loaded at a page boundary.
if (ShowDisassemblyOnly) {
       outs() << "\n";
     }
 
     if (Disassembled) {
       const MCInstrDesc &MCDesc = MII->get(Inst.getOpcode());
       // Populate a vector of the symbolized callsite at this location
       // We don't need symbolized info for probe-based profile, just use an
       // empty stack as an entry to indicate a valid binary offset
-
+      SampleContextFrameVector SymbolizedCallStack;
       if (!UsePseudoProbes || TrackFuncContextSize) {
         InstructionPointer IP(this, Offset);
         // TODO: reallocation of Offset2LocStackMap will lead to dangling
         // strings We need ProfiledBinary to owned these string.
         Offset2LocStackMap[Offset] = symbolize(IP, true, UsePseudoProbes);
-        FrameLocationStack &SymbolizedCallStack = Offset2LocStackMap[Offset];
+        SampleContextFrameVector &SymbolizedCallStack =
+            Offset2LocStackMap[Offset];
         // Record instruction size for the corresponding context
         if (TrackFuncContextSize && !SymbolizedCallStack.empty())
           FuncSizeTracker.addInstructionForContext(Offset2LocStackMap[Offset],
                                                    Size);
       } else {
-        Offset2LocStackMap[Offset] = FrameLocationStack();
+        Offset2LocStackMap[Offset] = SampleContextFrameVector();
       }
 
       // Populate address maps.
       CodeAddrs.push_back(Offset);
       if (MCDesc.isCall())
         CallAddrs.insert(Offset);
       else if (MCDesc.isReturn())
         RetAddrs.insert(Offset);
SymbolizerOpts.PrintFunctions =
       DILineInfoSpecifier::FunctionNameKind::LinkageName;
   SymbolizerOpts.Demangle = false;
   SymbolizerOpts.DefaultArch = TheTriple.getArchName().str();
   SymbolizerOpts.UseSymbolTable = false;
   SymbolizerOpts.RelativeAddresses = false;
   Symbolizer = std::make_unique<symbolize::LLVMSymbolizer>(SymbolizerOpts);
 }
 
-FrameLocationStack ProfiledBinary::symbolize(const InstructionPointer &IP,
+SampleContextFrameVector ProfiledBinary::symbolize(const InstructionPointer &IP,
                                                    bool UseCanonicalFnName,
                                                    bool UseProbeDiscriminator) {
   assert(this == IP.Binary &&
          "Binary should only symbolize its own instruction");
   auto Addr = object::SectionedAddress{IP.Offset + getPreferredBaseAddress(),
                                        object::SectionedAddress::UndefSection};
   DIInliningInfo InlineStack =
       unwrapOrError(Symbolizer->symbolizeInlinedCode(Path, Addr), getName());
 
-  FrameLocationStack CallStack;
+  SampleContextFrameVector CallStack;
   for (int32_t I = InlineStack.getNumberOfFrames() - 1; I >= 0; I--) {
     const auto &CallerFrame = InlineStack.getFrame(I);
     if (CallerFrame.FunctionName == "<invalid>")
       break;
 
     StringRef FunctionName(CallerFrame.FunctionName);
     if (UseCanonicalFnName)
       FunctionName = FunctionSamples::getCanonicalFnName(FunctionName);
 
     uint32_t Discriminator = CallerFrame.Discriminator;
     uint32_t LineOffset = CallerFrame.Line - CallerFrame.StartLine;
     if (UseProbeDiscriminator) {
       LineOffset =
           PseudoProbeDwarfDiscriminator::extractProbeIndex(Discriminator);
       Discriminator = 0;
     } else {
       Discriminator = DILocation::getBaseDiscriminatorFromDiscriminator(
           CallerFrame.Discriminator,
           /* IsFSDiscriminator */ false);
     }
 
     LineLocation Line(LineOffset, Discriminator);
-    FrameLocation Callsite(FunctionName.str(), Line);
-    CallStack.push_back(Callsite);
+    auto It = NameStrings.insert(FunctionName.str());
+    CallStack.emplace_back(*It.first, Line);
   }
 
   return CallStack;
 }
 
 InstructionPointer::InstructionPointer(ProfiledBinary *Binary, uint64_t Address,
                                        bool RoundToNext)
     : Binary(Binary), Address(Address) {

llvm/unittests/ProfileData/SampleProfTest.cpp

void testRoundTrip(SampleProfileFormat Format, bool Remap, bool UseMD5) {
 
     StringRef BooName("_Z3booi");
     FunctionSamples BooSamples;
     BooSamples.setName(BooName);
     BooSamples.addTotalSamples(1232);
     BooSamples.addHeadSamples(1);
     BooSamples.addBodySamples(1, 0, 1232);
 
-    StringMap<FunctionSamples> Profiles;
+    SampleProfileMap Profiles;
     Profiles[FooName] = std::move(FooSamples);
     Profiles[BarName] = std::move(BarSamples);
     Profiles[BazName] = std::move(BazSamples);
     Profiles[BooName] = std::move(BooSamples);
 
     Module M("my_module", Context);
     FunctionType *fn_type =
         FunctionType::get(Type::getVoidTy(Context), {}, false);
void testRoundTrip(SampleProfileFormat Format, bool Remap, bool UseMD5) {
 
     verifyProfileSummary(Summary, M, false, false);
 
     Summary.setPartialProfile(true);
     Summary.setPartialProfileRatio(0.5);
     verifyProfileSummary(Summary, M, true, true);
   }
 
-  void addFunctionSamples(StringMap<FunctionSamples> *Smap, const char *Fname,
+  void addFunctionSamples(SampleProfileMap *Smap, const char *Fname,
                           uint64_t TotalSamples, uint64_t HeadSamples) {
     StringRef Name(Fname);
     FunctionSamples FcnSamples;
     FcnSamples.setName(Name);
     FcnSamples.addTotalSamples(TotalSamples);
     FcnSamples.addHeadSamples(HeadSamples);
     FcnSamples.addBodySamples(1, 0, HeadSamples);
     (*Smap)[Name] = FcnSamples;
   }
 
-  StringMap<FunctionSamples> setupFcnSamplesForElisionTest(StringRef Policy) {
-    StringMap<FunctionSamples> Smap;
+  SampleProfileMap setupFcnSamplesForElisionTest(StringRef Policy) {
+    SampleProfileMap Smap;
     addFunctionSamples(&Smap, "foo", uint64_t(20301), uint64_t(1437));
     if (Policy == "" || Policy == "all")
       return Smap;
     addFunctionSamples(&Smap, "foo.bar", uint64_t(20303), uint64_t(1439));
     if (Policy == "selected")
       return Smap;
     addFunctionSamples(&Smap, "foo.llvm.2465", uint64_t(20305), uint64_t(1441));
     return Smap;
struct SampleProfTest : ::testing::Test {
   }
 
   void testSuffixElisionPolicy(SampleProfileFormat Format, StringRef Policy,
                                const StringMap<uint64_t> &Expected) {
     TempFile ProfileFile("profile", "", "", /*Unique*/ true);
 
     Module M("my_module", Context);
     setupModuleForElisionTest(&M, Policy);
-    StringMap<FunctionSamples> ProfMap = setupFcnSamplesForElisionTest(Policy);
+    SampleProfileMap ProfMap = setupFcnSamplesForElisionTest(Policy);
 
     // write profile
     createWriter(Format, ProfileFile.path());
     std::error_code EC;
     EC = Writer->write(ProfMap);
     ASSERT_TRUE(NoError(EC));
     Writer->getOutputStream().flush();