[CSSPGO] Enable loading MD5 CS profile.

[hoy]

Summary

Adding the compiler support of MD5 CS profile based on pervious context split work D107299. A MD5 CS profile is about 40% smaller than the string-based extbinary profile. As a result, the compilation is 15% faster.

There are a few conversion from real names to md5 names that have been made on the sample loader and context tracker side to get it work.

[hoy]

Updating D108342: [CSSPGO] Enable md5-based CS profile.

[wenlei]

The work on llvm-profgen side is not included. Currently I'm relying on llvm-profdata to get a md5 cs profile.

Is there blocker for this to be done in llvm-profgen? I imagine if llvm-profdata can generate md5 cs profile, llvm-profgen should be no different by reusing the writer to handle this?

llvm/lib/ProfileData/SampleProfReader.cpp

762

As we discussed, use SampleProfileReader::ProfileIsCS instead.

766

OrderedNames -> OrderedContexts

994

Can we move FunctionSamples::UseMD5 = useMD5() to be before readImpl() inside read() and then avoid this extra UseMD5 setting?

llvm/lib/Transforms/IPO/SampleContextTracker.cpp

487

Remove copies:

MD5Names.emplace_back();
getRepInFormat(Location.second, FunctionSamples::UseMD5, MD5Names.back());

llvm/lib/Transforms/IPO/SampleProfile.cpp

987

Good catch here and below.

llvm/tools/llvm-profgen/CSPreInliner.cpp

42–43

I think this would break preinliner when building profiled call graph - ContextTracker.getFuncNameFor would fail.

Add a test case for md5 pre-inliner? perhaps just add md5 version for an existing test case.

[hoy]

In D108342#2971668, @wenlei wrote:

The work on llvm-profgen side is not included. Currently I'm relying on llvm-profdata to get a md5 cs profile.

Is there blocker for this to be done in llvm-profgen? I imagine if llvm-profdata can generate md5 cs profile, llvm-profgen should be no different by reusing the writer to handle this?

Yes, that's the way we were using previously. There is an optimization we can do before it comes to the writer for pseudo probe. Pseudo probe comes with GUID so we can use that inside in the profile generator and unwinder. I think @wlei had a change for that which we can land separately.

llvm/lib/ProfileData/SampleProfReader.cpp

994

Actually useMD5 relies on readImpl() to be set. It is until the reader actually reads the SecNameTable we know we are reading a md5 profile or not. The reader checks the SecFlagMD5Name flag to see if SecNameTable is filled with real names or md5 names.

llvm/lib/Transforms/IPO/SampleContextTracker.cpp

487

Sounds good.

llvm/tools/llvm-profgen/CSPreInliner.cpp

42–43

md5 is not enabled with llvm-profgen for now. Will a test when it is enabled.

It also depends on how we achieve md5 profile generation. If we rely on the writer to convert real names to md5, then CSPreliner should see real names here. Otherwise, it can see md5 codes and we need to build a guid map for it.

[hoy]

Addressing Wenlei's comment.

[wlei]

In D108342#2973176, @hoy wrote:

In D108342#2971668, @wenlei wrote:

The work on llvm-profgen side is not included. Currently I'm relying on llvm-profdata to get a md5 cs profile.

Is there blocker for this to be done in llvm-profgen? I imagine if llvm-profdata can generate md5 cs profile, llvm-profgen should be no different by reusing the writer to handle this?

Yes, that's the way we were using previously. There is an optimization we can do before it comes to the writer for pseudo probe. Pseudo probe comes with GUID so we can use that inside in the profile generator and unwinder. I think @wlei had a change for that which we can land separately.

Yes, it's in https://reviews.llvm.org/D107779 (TODO: change the writer to convert MD5 back to std::string), I can continue with it when we check in this.

[wenlei]

llvm/lib/ProfileData/SampleProfReader.cpp

994

Ok.. Taking another look, where in reader do we depend on FunctionSamples::UseMD5 though? With the current definition (pasted below) for useMD5(), we could check useMD5() within reader, then we avoid this special case here?

Similar to ProfileIsCS, in general it's more consistent to use reader flag while we're in reader.

bool useMD5() override { return MD5StringBuf.get(); }

llvm/tools/llvm-profgen/CSPreInliner.cpp

42–43

Sounds good, add a TODO here then?

[wenlei]

In D108342#2973176, @hoy wrote:

In D108342#2971668, @wenlei wrote:

The work on llvm-profgen side is not included. Currently I'm relying on llvm-profdata to get a md5 cs profile.

Is there blocker for this to be done in llvm-profgen? I imagine if llvm-profdata can generate md5 cs profile, llvm-profgen should be no different by reusing the writer to handle this?

Yes, that's the way we were using previously. There is an optimization we can do before it comes to the writer for pseudo probe. Pseudo probe comes with GUID so we can use that inside in the profile generator and unwinder. I think @wlei had a change for that which we can land separately.

Okay, but is it not working at at all without Lei's optimization, or is it too slow? Asking because I'm wondering why you had to use llvm-profdata to generate md5 profile, instead of just let writer take care of md5 from llvm-profgen directly.

[hoy]

In D108342#2973234, @wenlei wrote:

In D108342#2973176, @hoy wrote:

In D108342#2971668, @wenlei wrote:

The work on llvm-profgen side is not included. Currently I'm relying on llvm-profdata to get a md5 cs profile.

Is there blocker for this to be done in llvm-profgen? I imagine if llvm-profdata can generate md5 cs profile, llvm-profgen should be no different by reusing the writer to handle this?

Yes, that's the way we were using previously. There is an optimization we can do before it comes to the writer for pseudo probe. Pseudo probe comes with GUID so we can use that inside in the profile generator and unwinder. I think @wlei had a change for that which we can land separately.

Okay, but is it not working at at all without Lei's optimization, or is it too slow? Asking because I'm wondering why you had to use llvm-profdata to generate md5 profile, instead of just let writer take care of md5 from llvm-profgen directly.

I had to use llvm-profdata simply because of the support of md5 in llvm-profgen was not ready. It shouldn't be too slow now for llvm-profgen to use real names with the context split work. We could give Lei's approach a shot to see how much win can be get.

llvm/lib/ProfileData/SampleProfReader.cpp

994

Good question. The dependency is from using FunctionSamples::getGUID when loading func profiles. That method checks if FunctionSamples::UseMD5 is set.

// Assume the input \p Name is a name coming from FunctionSamples itself.
// If UseMD5 is true, the name is already a GUID and we
// don't want to return the GUID of GUID.
static uint64_t getGUID(StringRef Name) {
  return UseMD5 ? std::stoull(Name.data()) : Function::getGUID(Name);
}

We can just use std::stoull(Name.data()) instead to avoid this change.

[hoy]

Updating D108342: [CSSPGO] Enable loading MD5 CS profile.

[wenlei]

lgtm, thanks!

[wenlei]

I had to use llvm-profdata simply because of the support of md5 in llvm-profgen was not ready. It shouldn't be too slow now for llvm-profgen to use real names with the context split work. We could give Lei's approach a shot to see how much win can be get.

What I was wondering is what does it take for md5 support to be ready for llvm-profgen? I thought it's close to a no-op as llvm-profgen use the same writer, and the handling md5 is in the writer. Of course we can use Lei's change to make it faster, but that's just optimization.

[hoy]

In D108342#2973777, @wenlei wrote:

I had to use llvm-profdata simply because of the support of md5 in llvm-profgen was not ready. It shouldn't be too slow now for llvm-profgen to use real names with the context split work. We could give Lei's approach a shot to see how much win can be get.

What I was wondering is what does it take for md5 support to be ready for llvm-profgen? I thought it's close to a no-op as llvm-profgen use the same writer, and the handling md5 is in the writer. Of course we can use Lei's change to make it faster, but that's just optimization.

I see. It should be straightforward to add md5 support to llvm-profgen. I just added here.

[hoy]

Adding md5 support to llvm-profgen.

[hoy]

Updating D108342: [CSSPGO] Enable loading MD5 CS profile.

[wenlei]

In D108342#2973929, @hoy wrote:

In D108342#2973777, @wenlei wrote:

I had to use llvm-profdata simply because of the support of md5 in llvm-profgen was not ready. It shouldn't be too slow now for llvm-profgen to use real names with the context split work. We could give Lei's approach a shot to see how much win can be get.

What I was wondering is what does it take for md5 support to be ready for llvm-profgen? I thought it's close to a no-op as llvm-profgen use the same writer, and the handling md5 is in the writer. Of course we can use Lei's change to make it faster, but that's just optimization.

I see. It should be straightforward to add md5 support to llvm-profgen. I just added here.

Ok, thanks. Yeah this is what I'm trying to understand - why not adding it here since it should be one-liner. :)

Can you add md5 test case for llvm-profgen too? (We also need to address preinliner with md5 asap, ok for a later patch)

llvm/tools/llvm-profgen/ProfileGenerator.cpp

32

Similar to llvm-profdata, call out in description that this is only meaningful for -extbinary.

[hoy]

Updating D108342: [CSSPGO] Enable loading MD5 CS profile.

[hoy]

In D108342#2973938, @wenlei wrote:

In D108342#2973929, @hoy wrote:

In D108342#2973777, @wenlei wrote:

I had to use llvm-profdata simply because of the support of md5 in llvm-profgen was not ready. It shouldn't be too slow now for llvm-profgen to use real names with the context split work. We could give Lei's approach a shot to see how much win can be get.

What I was wondering is what does it take for md5 support to be ready for llvm-profgen? I thought it's close to a no-op as llvm-profgen use the same writer, and the handling md5 is in the writer. Of course we can use Lei's change to make it faster, but that's just optimization.

I see. It should be straightforward to add md5 support to llvm-profgen. I just added here.

Ok, thanks. Yeah this is what I'm trying to understand - why not adding it here since it should be one-liner. :)

Can you add md5 test case for llvm-profgen too? (We also need to address preinliner with md5 asap, ok for a later patch)

A test is already added to noinline-cs-noprobe.test. Do you mean in another form? Since md5 profile is not text, I'm not sure what's a good way to check its content.

llvm/tools/llvm-profgen/ProfileGenerator.cpp

32

Done.

[wenlei]

In D108342#2973944, @hoy wrote:

In D108342#2973938, @wenlei wrote:

In D108342#2973929, @hoy wrote:

In D108342#2973777, @wenlei wrote:

I had to use llvm-profdata simply because of the support of md5 in llvm-profgen was not ready. It shouldn't be too slow now for llvm-profgen to use real names with the context split work. We could give Lei's approach a shot to see how much win can be get.

What I was wondering is what does it take for md5 support to be ready for llvm-profgen? I thought it's close to a no-op as llvm-profgen use the same writer, and the handling md5 is in the writer. Of course we can use Lei's change to make it faster, but that's just optimization.

I see. It should be straightforward to add md5 support to llvm-profgen. I just added here.

Ok, thanks. Yeah this is what I'm trying to understand - why not adding it here since it should be one-liner. :)

Can you add md5 test case for llvm-profgen too? (We also need to address preinliner with md5 asap, ok for a later patch)

A test is already added to noinline-cs-noprobe.test. Do you mean in another form? Since md5 profile is not text, I'm not sure what's a good way to check its content.

Ok, I didn't notice that one. But looking at it, I think we could check the profile summary (detailed summary) is the same as non-md5 profile?

[hoy]

In D108342#2974015, @wenlei wrote:

In D108342#2973944, @hoy wrote:

In D108342#2973938, @wenlei wrote:

In D108342#2973929, @hoy wrote:

In D108342#2973777, @wenlei wrote:

I had to use llvm-profdata simply because of the support of md5 in llvm-profgen was not ready. It shouldn't be too slow now for llvm-profgen to use real names with the context split work. We could give Lei's approach a shot to see how much win can be get.

What I was wondering is what does it take for md5 support to be ready for llvm-profgen? I thought it's close to a no-op as llvm-profgen use the same writer, and the handling md5 is in the writer. Of course we can use Lei's change to make it faster, but that's just optimization.

I see. It should be straightforward to add md5 support to llvm-profgen. I just added here.

Ok, thanks. Yeah this is what I'm trying to understand - why not adding it here since it should be one-liner. :)

Can you add md5 test case for llvm-profgen too? (We also need to address preinliner with md5 asap, ok for a later patch)

A test is already added to noinline-cs-noprobe.test. Do you mean in another form? Since md5 profile is not text, I'm not sure what's a good way to check its content.

Ok, I didn't notice that one. But looking at it, I think we could check the profile summary (detailed summary) is the same as non-md5 profile?

That should work.

[hoy]

Updating D108342: [CSSPGO] Enable loading MD5 CS profile.

[wmi]

llvm/lib/ProfileData/SampleProfReader.cpp

762

Since Function in non context profile can also be represented using SampleContext, can we merge the case for cs and non-cs profile cases here?

785–786

It can be collapsed into one if.
if (useMD() && !FuncGuidsToUse.count(std::stoull(FuncName.data())) ||

   (!FuncsToUse.count(FuncName) &&
            (!Remapper || !Remapper->exist(FuncName))))
continue;

llvm/lib/Transforms/IPO/SampleProfile.cpp

987

+1 for the good catch.

[hoy]

llvm/lib/ProfileData/SampleProfReader.cpp

762

The processing of cs profile is a bit different from non-cs in that cs profile needs to be loaded in some order that profiles should be loaded for not only functions in the current module, but also for the callee functions out of current module. Note that OrderedContexts used only in the cs case diverges from non-cs case. I'm also changing how to load profiles for cs profiles in another patch which makes them diverged even more.

785–786

Currently in both Md5 and string case, FuncsToUse contains the function real names computed by FunctionSamples::getCanonicalFnName. We could change that to include md5 names for the md5 case to unify the two paths. However, the md5 name string for a function needs to be stored somewhere before added to FuncsToUse which only takes a stringRef. That seems a bit complicated. What do you think?

[wmi]

llvm/lib/ProfileData/SampleProfReader.cpp

762

Ok, if we can come up with a solution to differentiate them in a query function or shrink the guarded range of ProfileIsCS, that will be ideal. I thought a bit but didn't get it right.

785–786

Ok, then can we have

if (useMD() && !FuncGuidsToUse.count(std::stoull(FuncName.data())) ||
    (!useMD() && !FuncsToUse.count(FuncName) &&
            (!Remapper || !Remapper->exist(FuncName))))
continue;

[hoy]

llvm/lib/ProfileData/SampleProfReader.cpp

762

Sure, let me see if I can merge them with upcoming work that is based on a presorted func offset table.

785–786

Sounds good.

[hoy]

Addressing Wei's comment.

[wmi]

LGTM.

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

public:
 
   // Constructor for CS profile.
   ProfiledCallGraph(SampleContextTracker &ContextTracker) {
     // BFS traverse the context profile trie to add call edges for calls shown
     // in context.
     std::queue<ContextTrieNode *> Queue;
     for (auto &Child : ContextTracker.getRootContext().getAllChildContext()) {
       ContextTrieNode *Callee = &Child.second;
-      addProfiledFunction(Callee->getFuncName());
+      addProfiledFunction(ContextTracker.getFuncNameFor(Callee));
       Queue.push(Callee);
     }
 
     while (!Queue.empty()) {
       ContextTrieNode *Caller = Queue.front();
       Queue.pop();
       // Add calls for context. When AddNodeWithSamplesOnly is true, both caller
       // and callee need to have context profile.
       // Note that callsite target samples are completely ignored since they can
       // conflict with the context edges, which are formed by context
       // compression during profile generation, for cyclic SCCs. This may
       // further result in an SCC order incompatible with the purely
       // context-based one, which may in turn block context-based inlining.
       for (auto &Child : Caller->getAllChildContext()) {
         ContextTrieNode *Callee = &Child.second;
-        addProfiledFunction(Callee->getFuncName());
+        addProfiledFunction(ContextTracker.getFuncNameFor(Callee));
         Queue.push(Callee);
-        addProfiledCall(Caller->getFuncName(), Callee->getFuncName());
+        addProfiledCall(ContextTracker.getFuncNameFor(Caller),
+                        ContextTracker.getFuncNameFor(Callee));
       }
     }
   }
 
   iterator begin() { return Root.Callees.begin(); }
   iterator end() { return Root.Callees.end(); }
   ProfiledCallGraphNode *getEntryNode() { return &Root; }
   void addProfiledFunction(StringRef Name) {

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

bool operator()(FunctionSamples *A, FunctionSamples *B) const {
       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(SampleProfileMap &Profiles);
+  SampleContextTracker(SampleProfileMap &Profiles,
+                       const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap);
   // 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
   // is identified by input DILocation.
   FunctionSamples *getContextSamplesFor(const DILocation *DIL);
   // Query context profile for a given sample contxt of a function.
   FunctionSamples *getContextSamplesFor(const SampleContext &Context);
   // Get all context profile for given function.
   ContextSamplesTy &getAllContextSamplesFor(const Function &Func);
   ContextSamplesTy &getAllContextSamplesFor(StringRef Name);
   // Query base profile for a given function. A base profile is a merged view
   // of all context profiles for contexts that are not inlined.
   FunctionSamples *getBaseSamplesFor(const Function &Func,
                                      bool MergeContext = true);
   // Query base profile for a given function by name.
   FunctionSamples *getBaseSamplesFor(StringRef Name, bool MergeContext = true);
   // Retrieve the context trie node for given profile context
   ContextTrieNode *getContextFor(const SampleContext &Context);
+  // Get real function name for a given trie node.
+  StringRef getFuncNameFor(ContextTrieNode *Node) const;
   // Mark a context profile as inlined when function is inlined.
   // This makes sure that inlined context profile will be excluded in
   // function's base profile.
   void markContextSamplesInlined(const FunctionSamples *InlinedSamples);
   ContextTrieNode &getRootContext();
   void promoteMergeContextSamplesTree(const Instruction &Inst,
                                       StringRef CalleeName);
   // Dump the internal context profile trie.
private:
   ContextTrieNode &
   promoteMergeContextSamplesTree(ContextTrieNode &FromNode,
                                  ContextTrieNode &ToNodeParent,
                                  uint32_t ContextFramesToRemove);
 
   // Map from function name to context profiles (excluding base profile)
   StringMap<ContextSamplesTy> FuncToCtxtProfiles;
 
+  // Map from function guid to real function names. Only used in md5 mode.
+  const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap;
+
   // Root node for context trie tree
   ContextTrieNode RootContext;
 };
 
 } // end namespace llvm
 #endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H

llvm/lib/ProfileData/SampleProfReader.cpp

std::error_code SampleProfileReaderExtBinaryBase::readFuncProfiles() {
   } else {
     // Load function profiles on demand.
     if (Remapper) {
       for (auto Name : FuncsToUse) {
         Remapper->insert(Name);
       }
     }
 
-    if (useMD5()) {
-      for (auto Name : FuncsToUse) {
-        auto GUID = std::to_string(MD5Hash(Name));
-        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 (ProfileIsCS) {
+    if (ProfileIsCS) {
       // Compute the ordered set of names, so we can
       // get all context profiles under a subtree by
       // iterating through the ordered names.
       std::set<SampleContext> OrderedContexts;
       for (auto Name : FuncOffsetTable) {
         OrderedContexts.insert(Name.first);
       }
 
+      DenseSet<uint64_t> FuncGuidsToUse;
+      if (useMD5()) {
+        for (auto Name : FuncsToUse)
+          FuncGuidsToUse.insert(Function::getGUID(Name));
+      }
+
       // For each function in current module, load all
       // context profiles for the function.
       for (auto NameOffset : FuncOffsetTable) {
         SampleContext FContext = NameOffset.first;
         auto FuncName = FContext.getName();
-        if (!FuncsToUse.count(FuncName) &&
-            (!Remapper || !Remapper->exist(FuncName)))
+        if ((useMD5() && !FuncGuidsToUse.count(std::stoull(FuncName.data()))) ||
+            (!useMD5() && !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 = 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 = OrderedContexts.erase(It);
         }
       }
     } else {
+      if (useMD5()) {
+        for (auto Name : FuncsToUse) {
+          auto GUID = std::to_string(MD5Hash(Name));
+          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 {
         for (auto NameOffset : FuncOffsetTable) {
           SampleContext FContext(NameOffset.first);
           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;
         }
       }
+    }
     Data = End;
   }
   assert((CSProfileCount == 0 || CSProfileCount == Profiles.size()) &&
          "Cannot have both context-sensitive and regular profile");
   assert((!CSProfileCount || ProfileIsCS) &&
          "Section flag should be consistent with actual profile");
   return sampleprof_error::success;
 }
std::error_code SampleProfileReaderBinary::readNameTable() {
 
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileReaderExtBinaryBase::readMD5NameTable() {
   auto Size = readNumber<uint64_t>();
   if (std::error_code EC = Size.getError())
     return EC;
   MD5StringBuf = std::make_unique<std::vector<std::string>>();
   MD5StringBuf->reserve(*Size);
   if (FixedLengthMD5) {
     // Preallocate and initialize NameTable so we can check whether a name
     // index has been read before by checking whether the element in the
     // NameTable is empty, meanwhile readStringIndex can do the boundary
     // check using the size of NameTable.
     NameTable.resize(*Size + NameTable.size());
 

llvm/lib/Transforms/IPO/SampleContextTracker.cpp

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(SampleProfileMap &Profiles) {
+SampleContextTracker::SampleContextTracker(
+    SampleProfileMap &Profiles,
+    const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap)
+    : GUIDToFuncNameMap(GUIDToFuncNameMap) {
   for (auto &FuncSample : Profiles) {
     FunctionSamples *FSamples = &FuncSample.second;
     SampleContext Context = FuncSample.first;
     LLVM_DEBUG(dbgs() << "Tracking Context for function: " << Context.toString()
                       << "\n");
     if (!Context.isBaseContext())
       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);
+  // Convert real function names to MD5 names, if the input profile is
+  // MD5-based.
+  std::string FGUID;
+  CalleeName = getRepInFormat(CalleeName, FunctionSamples::UseMD5, FGUID);
 
   // 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().toString()
FunctionSamples *SampleContextTracker::getBaseSamplesFor(const Function &Func,
                                                          bool MergeContext) {
   StringRef CanonName = FunctionSamples::getCanonicalFnName(Func);
   return getBaseSamplesFor(CanonName, MergeContext);
 }
 
 FunctionSamples *SampleContextTracker::getBaseSamplesFor(StringRef Name,
                                                          bool MergeContext) {
   LLVM_DEBUG(dbgs() << "Getting base profile for function: " << Name << "\n");
+  // Convert real function names to MD5 names, if the input profile is
+  // MD5-based.
+  std::string FGUID;
+  Name = getRepInFormat(Name, FunctionSamples::UseMD5, FGUID);
+
   // Base profile is top-level node (child of root node), so try to retrieve
   // existing top-level node for given function first. If it exists, it could be
   // that we've merged base profile before, or there's actually context-less
   // profile from the input (e.g. due to unreliable stack walking).
   ContextTrieNode *Node = getTopLevelContextNode(Name);
   if (MergeContext) {
     LLVM_DEBUG(dbgs() << "  Merging context profile into base profile: " << Name
                       << "\n");
ContextTrieNode &SampleContextTracker::promoteMergeContextSamplesTree(
   uint32_t ContextFramesToRemove =
       FromSamples->getContext().getContextFrames().size() - 1;
   return promoteMergeContextSamplesTree(NodeToPromo, RootContext,
                                         ContextFramesToRemove);
 }
 
 void SampleContextTracker::dump() { RootContext.dumpTree(); }
 
+StringRef SampleContextTracker::getFuncNameFor(ContextTrieNode *Node) const {
+  if (!FunctionSamples::UseMD5)
+    return Node->getFuncName();
+  assert(GUIDToFuncNameMap && "GUIDToFuncNameMap needs to be populated first");
+  return GUIDToFuncNameMap->lookup(std::stoull(Node->getFuncName().data()));
+}
+
 ContextTrieNode *
 SampleContextTracker::getContextFor(const SampleContext &Context) {
   return getOrCreateContextPath(Context, false);
 }
 
 ContextTrieNode *
 SampleContextTracker::getCalleeContextFor(const DILocation *DIL,
                                           StringRef CalleeName) {
ContextTrieNode *SampleContextTracker::getContextFor(const DILocation *DIL) {
 
   // Push root node, note that root node like main may only
   // a name, but not linkage name.
   StringRef RootName = PrevDIL->getScope()->getSubprogram()->getLinkageName();
   if (RootName.empty())
     RootName = PrevDIL->getScope()->getSubprogram()->getName();
   S.push_back(std::make_pair(LineLocation(0, 0), RootName));
 
+  // Convert real function names to MD5 names, if the input profile is
+  // MD5-based.
+  std::vector<std::string> MD5Names;
+  if (FunctionSamples::UseMD5) {
+    for (auto &Location : S) {
+      MD5Names.emplace_back();
+      getRepInFormat(Location.second, FunctionSamples::UseMD5, MD5Names.back());
+      Location.second = MD5Names.back();
+    }
+  }
+
   ContextTrieNode *ContextNode = &RootContext;
   int I = S.size();
   while (--I >= 0 && ContextNode) {
     LineLocation &CallSite = S[I].first;
     StringRef &CalleeName = S[I].second;
     ContextNode = ContextNode->getChildContext(CallSite, CalleeName);
   }
 

llvm/lib/Transforms/IPO/SampleProfile.cpp

while (!CalleeList.empty()) {
     // even if callee doesn't have a corresponding context profile.
     if (!CalleeSample || CalleeSample->getEntrySamples() < Threshold)
       continue;
 
     StringRef Name = CalleeSample->getFuncName();
     Function *Func = SymbolMap.lookup(Name);
     // Add to the import list only when it's defined out of module.
     if (!Func || Func->isDeclaration())
-      InlinedGUIDs.insert(FunctionSamples::getGUID(Name));
+      InlinedGUIDs.insert(FunctionSamples::getGUID(CalleeSample->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 : CalleeSample->getBodySamples())
       for (const auto &TS : BS.second.getCallTargets())
         if (TS.getValue() > Threshold) {
           StringRef CalleeName = CalleeSample->getFuncName(TS.getKey());
           const Function *Callee = SymbolMap.lookup(CalleeName);
           if (!Callee || Callee->isDeclaration())
-            InlinedGUIDs.insert(FunctionSamples::getGUID(CalleeName));
+            InlinedGUIDs.insert(FunctionSamples::getGUID(TS.getKey()));
         }
 
     // Import hot child context profile associted with callees. Note that this
     // may have some overlap with the call target loop above, but doing this
     // based child context profile again effectively allow us to use the max of
     // entry count and call target count to determine importing.
     for (auto &Child : Node->getAllChildContext()) {
       ContextTrieNode *CalleeNode = &Child.second;
if (Reader->profileIsCS()) {
     if (!CallsitePrioritizedInline.getNumOccurrences())
       CallsitePrioritizedInline = true;
 
     // Enable iterative-BFI by default for CSSPGO.
     if (!UseIterativeBFIInference.getNumOccurrences())
       UseIterativeBFIInference = true;
 
     // Tracker for profiles under different context
-    ContextTracker =
-        std::make_unique<SampleContextTracker>(Reader->getProfiles());
+    ContextTracker = std::make_unique<SampleContextTracker>(
+        Reader->getProfiles(), &GUIDToFuncNameMap);
   }
 
   // Load pseudo probe descriptors for probe-based function samples.
   if (Reader->profileIsProbeBased()) {
     ProbeManager = std::make_unique<PseudoProbeManager>(M);
     if (!ProbeManager->moduleIsProbed(M)) {
       const char *Msg =
           "Pseudo-probe-based profile requires SampleProfileProbePass";

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: 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
+; RUN: llvm-profdata merge --sample --extbinary --use-md5 %S/Inputs/csspgo-import-list.prof -o %t.md5
+; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=pgo-sample-use-pipeline -sample-profile-file=%t.md5 -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/csspgo-inline-icall.ll

 ; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/indirect-call-csspgo.prof -sample-profile-icp-relative-hotness=1 -pass-remarks=sample-profile -S -o /dev/null 2>&1 | FileCheck -check-prefix=ICP-ALL %s
 ; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/indirect-call-csspgo.prof -sample-profile-icp-relative-hotness=1  -pass-remarks=sample-profile -S -o /dev/null 2>&1 | FileCheck -check-prefix=ICP-ALL %s
 ; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/indirect-call-csspgo.prof -sample-profile-icp-relative-hotness=1  -pass-remarks=sample-profile -sample-profile-inline-size=0 -S -o /dev/null 2>&1 | FileCheck -check-prefix=ICP-HOT %s
 ; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/indirect-call-csspgo.prof -sample-profile-icp-relative-hotness=1  -pass-remarks=sample-profile -sample-profile-inline-size=0 -S -o /dev/null 2>&1 | FileCheck -check-prefix=ICP-HOT %s
+; RUN: llvm-profdata merge --sample --extbinary --use-md5 %S/Inputs/indirect-call-csspgo.prof -o %t.md5
+; RUN: opt < %s -passes=sample-profile -sample-profile-file=%t.md5 -sample-profile-icp-relative-hotness=1  -pass-remarks=sample-profile -sample-profile-inline-size=0 -S -o /dev/null 2>&1 | FileCheck -check-prefix=ICP-HOT %s
+
 
 define void @test(void ()*) #0 !dbg !3 {
 ;; Add two direct call to force top-down order for sample profile loader
   call void @_Z3foov(), !dbg !7
   call void @_Z3barv(), !dbg !7
   call void @_Z3bazv(), !dbg !7
   %2 = alloca void ()*
   store void ()* %0, void ()** %2

llvm/test/Transforms/SampleProfile/csspgo-inline.ll

 ; Test for CSSPGO's new early inliner using priority queue
 
 ; Note that we need new pass manager to enable top-down processing for sample profile loader
 ; Test we inlined the following in top-down order with old inliner
 ;   main:3 @ _Z5funcAi
 ;   main:3 @ _Z5funcAi:1 @ _Z8funcLeafi
 ;   _Z5funcBi:1 @ _Z8funcLeafi
 ; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/profile-context-tracker.prof -sample-profile-inline-size -sample-profile-prioritized-inline=0 -profile-sample-accurate -S -pass-remarks=inline -o /dev/null 2>&1 | FileCheck %s --check-prefix=INLINE-BASE
-;
+
+; RUN: llvm-profdata merge --sample --extbinary --use-md5 %S/Inputs/profile-context-tracker.prof -o %t.md5
+; RUN: opt < %s -passes=sample-profile -sample-profile-file=%t.md5 -sample-profile-inline-size -sample-profile-prioritized-inline=0 -profile-sample-accurate -S -pass-remarks=inline -o /dev/null 2>&1 | FileCheck %s --check-prefix=INLINE-BASE
+
 ; With new FDO early inliner, callee entry count is used to drive inlining instead of callee total samples, so we get less inlining for given profile
 ; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/profile-context-tracker.prof -sample-profile-inline-size -profile-sample-accurate -S -pass-remarks=inline -o /dev/null 2>&1 | FileCheck %s --check-prefix=INLINE-NEW
 ;
 ; With new FDO early inliner, callee entry count is used to drive inlining instead of callee total samples, tuning hot cutoff can get us the same inlining
 ; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/profile-context-tracker.prof -sample-profile-inline-size -profile-summary-cutoff-hot=999900 -profile-sample-accurate -S -pass-remarks=inline -o /dev/null 2>&1 | FileCheck %s --check-prefix=INLINE-BASE
 ;
 ; With new FDO early inliner, callee entry count is used to drive inlining instead of callee total samples, tuning cold sample profile inline threshold can get us the same inlining
 ; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/profile-context-tracker.prof -sample-profile-inline-size -sample-profile-cold-inline-threshold=200 -profile-sample-accurate -S -pass-remarks=inline -o /dev/null 2>&1 | FileCheck %s --check-prefix=INLINE-BASE

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 --skip-symbolization --profile-summary-cold-count=0
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-UNWINDER
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/noinline-cs-noprobe.perfscript --binary=%S/Inputs/noinline-cs-noprobe.perfbin --output=%t --profile-summary-cold-count=0
 ; 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 --skip-symbolization --profile-summary-cold-count=0
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-AGG-UNWINDER
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/noinline-cs-noprobe.aggperfscript --binary=%S/Inputs/noinline-cs-noprobe.perfbin --output=%t --profile-summary-cold-count=0
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-AGG
 
+; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/noinline-cs-noprobe.perfscript --binary=%S/Inputs/noinline-cs-noprobe.perfbin --output=%t1 --profile-summary-cold-count=0
+; RUN: llvm-profgen --format=extbinary --perfscript=%S/Inputs/noinline-cs-noprobe.perfscript --binary=%S/Inputs/noinline-cs-noprobe.perfbin --output=%t2 --profile-summary-cold-count=0 -use-md5
+; RUN: llvm-profdata show --sample -show-sec-info-only %t2 | FileCheck %s --check-prefix=CHECK-MD5
+; RUN: llvm-profdata show --sample -detailed-summary --function=dummy %t1 > %t.summary
+; RUN: llvm-profdata show --sample -detailed-summary --function=dummy %t2 > %t2.summary
+; RUN: diff -b %t.summary %t2.summary
+
 
 ; CHECK-AGG:[main:1 @ foo]:108:0
 ; CHECK-AGG: 2: 6
 ; CHECK-AGG: 3: 6 bar:6
 ; CHECK-AGG:[main:1 @ foo:3 @ bar]:100:6
 ; CHECK-AGG: 0: 6
 ; CHECK-AGG: 1: 6
 ; CHECK-AGG: 2: 4

 ; CHECK-UNWINDER:   (62f, 5b0): 3
 ; CHECK-UNWINDER:   (637, 645): 3
 ; CHECK-UNWINDER:   (645, 5ff): 3
 ; CHECK-UNWINDER: main:1 @ foo:3 @ bar
 ; CHECK-UNWINDER:   (5c8, 5dc): 2
 ; CHECK-UNWINDER:   (5d7, 5e5): 2
 ; CHECK-UNWINDER:   (5e9, 634): 3
 
+; CHECK-MD5: NameTableSection {{.*}} {fixlenmd5}
 
 
 
 
 
 ; original code:
 ; clang -O0 -g test.c -o a.out
 #include <stdio.h>

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(SampleProfileMap &Profiles, ProfiledBinary &Binary,
                            uint64_t HotThreshold, uint64_t ColdThreshold)
-    : UseContextCost(UseContextCostForPreInliner), ContextTracker(Profiles),
-      ProfileMap(Profiles), Binary(Binary), HotCountThreshold(HotThreshold),
-      ColdCountThreshold(ColdThreshold) {}
+    : UseContextCost(UseContextCostForPreInliner),
+      // TODO: Pass in a guid-to-name map in order for
+      // ContextTracker.getFuncNameFor to work, if `Profiles` can have md5 codes
+      // as their profile context.
+      ContextTracker(Profiles, nullptr), ProfileMap(Profiles), Binary(Binary),
+      HotCountThreshold(HotThreshold), ColdCountThreshold(ColdThreshold) {}
 
 std::vector<StringRef> CSPreInliner::buildTopDownOrder() {
   std::vector<StringRef> Order;
   ProfiledCallGraph ProfiledCG(ContextTracker);
 
   // Now that we have a profiled call graph, construct top-down order
   // by building up SCC and reversing SCC order.
   scc_iterator<ProfiledCallGraph *> I = scc_begin(&ProfiledCG);

llvm/tools/llvm-profgen/ProfileGenerator.cpp

static cl::opt<SampleProfileFormat> OutputFormat(
     cl::values(
         clEnumValN(SPF_Binary, "binary", "Binary encoding (default)"),
         clEnumValN(SPF_Compact_Binary, "compbinary", "Compact binary encoding"),
         clEnumValN(SPF_Ext_Binary, "extbinary", "Extensible binary encoding"),
         clEnumValN(SPF_Text, "text", "Text encoding"),
         clEnumValN(SPF_GCC, "gcc",
                    "GCC encoding (only meaningful for -sample)")));
 
+cl::opt<bool> UseMD5(
+    "use-md5", cl::init(false), cl::Hidden,
+    cl::desc("Use md5 to represent function names in the output profile (only "
+             "meaningful for -extbinary)"));
+
 static cl::opt<int32_t, true> RecursionCompression(
     "compress-recursion",
     cl::desc("Compressing recursion by deduplicating adjacent frame "
              "sequences up to the specified size. -1 means no size limit."),
     cl::Hidden,
     cl::location(llvm::sampleprof::CSProfileGenerator::MaxCompressionSize));
 
 static cl::opt<bool> CSProfMergeColdContext(
void ProfileGenerator::write(std::unique_ptr<SampleProfileWriter> Writer,
   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 (UseMD5) {
+    if (OutputFormat != SPF_Ext_Binary)
+      WithColor::warning() << "-use-md5 is ignored. Specify "
+                              "--format=extbinary to enable it\n";
+    else
+      WriterOrErr.get()->setUseMD5();
+  }
+
   write(std::move(WriterOrErr.get()), ProfileMap);
 }
 
 void ProfileGenerator::findDisjointRanges(RangeSample &DisjointRanges,
                                           const RangeSample &Ranges) {
 
   /*
   Regions may overlap with each other. Using the boundary info, find all