[AutoFDO] Use flattened profiles for profile staleness metrics

[wlei]

Summary

For profile staleness report, before it only counts for the top-level function samples in the nested profile, the samples in the inlinees are ignored. This could affect the quality of the metrics when there are heavily inlined functions. This change adds a feature to flatten the nested profile and we're changing to use flatten profile as the input for stale profile detection and matching.
Example for profile flattening:

Original profile:
_Z3bazi:20301:1000
 1: 1000
 3: 2000
 5: inline1:1600
   1: 600
   3: inline2:500
     1: 500

Flattened profile:
_Z3bazi:18701:1000
 1: 1000
 3: 2000
 5: 600 inline1:600
inline1:1100:600
 1: 600
 3: 500 inline2: 500
inline2:500:500
 1: 500

This feature could be useful for offline analysis, like understanding the hotness of each individual function. So I'm adding the support to llvm-profdata merge under --gen-flattened-profile.

[davidxl]

Document the new llvm-profdata option in the Commandline guide.

llvm/include/llvm/ProfileData/SampleProf.h

1293

Remove 'CS'

llvm/lib/Transforms/IPO/SampleProfile.cpp

145

Can you add a test case of using the new option for state profile detection?

[mingmingl]

llvm/include/llvm/ProfileData/SampleProf.h

1316

nit: const SampleProfileMap

1319

nit: I'm wondering if it's simpler to pass 'ProfileMap' as opposed to use std::move

llvm/lib/Transforms/IPO/SampleProfile.cpp

2077–2078

for my information, is it intended that flattening is true if it's not set (num occurrences = 0)? ask since it seems to change existing behavior.

2089–2093

If I read correctly, FunctionSamples::ProfileIsCS is a per-reader instance bool (correct me if I miss anything). So it might be useful to add tests for context-sensitive profile and non-CS profiles.

[wlei]

llvm/include/llvm/ProfileData/SampleProf.h

1316

As mentioned below, it's intentional to change the input.

1319

It's a bit tricky to update the map while iterating its element, it could insert a new FunctionSamples. We had an internal patch to do it in-place, it ended up using an additional map, later we still needed to make copies to the original ProfileMap. IMO, that's more complicated than this version.

llvm/lib/Transforms/IPO/SampleProfile.cpp

145

Test added

2077–2078

Yeah, it's intended to set true, maybe I can just set the default value to true. I was thinking to use different value for pre-link and post-link here, but that's not ready, will leave it later.

2089–2093

Sounds good, full CS test is added.

[wlei]

addressing reviewers' feedback: updated docs, added tests, other fixs.

[hoy]

llvm/include/llvm/ProfileData/SampleProf.h

1293

Update the comment correspondingly.

1293–1296

nit: name it convertCSProfiles .

1322

nit: swap the parameter declarations

llvm/lib/Transforms/IPO/SampleProfile.cpp

461

nit: name it getFlattenedSamples?

2089

Does it make sense to incorporate the CS path into ProfileConverter::flattenProfile?

[wlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

2089

Good idea, done! I just found it needs to clear the context to make llvm-profdata sample writer pass the context check. Also added the llvm-profdata test for full cs profile.

[wlei]

addressing Hongtao's feedback

[wenlei]

llvm/include/llvm/ProfileData/SampleProf.h

1339

This function doesn't have check on whether input is CS or profile or not, and it relies on caller to pass in the right kind of profile. Should we make it private and only expose flattenProfile as API which can take any kind of profile as input.

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

1039

this check seems unnecessary

1249

do we need to make sure gen-flattened-profile and gen-cs-nested-profile won't/can't be used at the same time?

also wondering if we should consolidate them into one flag, something like profile-structure=<cs-nested|flat>.

[wenlei]

llvm/include/llvm/ProfileData/SampleProf.h

1359–1362

Is the total samples populated this way going to be consistent with total samples from profiles generated directly from llvm-profgen?

[hoy]

llvm/include/llvm/ProfileData/SampleProf.h

1357

nit: assert CallsiteSamples is empty?

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

1249

also wondering if we should consolidate them into one flag, something like profile-structure=<cs-nested|flat>.

This is a good point. There's a similar term SampleProfileLayout introduced https://reviews.llvm.org/D121651 . Consider unifying them like below?

enum SampleProfileLayout {
  SPL_None = 0,
  SPL_Nest = 0x1,
  SPL_Flat = 0x2,
  SPL_CSFlat = 0x3,
};

[wlei]

llvm/include/llvm/ProfileData/SampleProf.h

1339

Sounds good, moved to private scope.

1357

Sounds good, assertion added

1359–1362

I think so. Supposing TotalSamples = TotalBodySamples + TotalCallsiteSamples. Remembering we discussed this while implementing llvm-profgen, the TotalBodySamples usually is not the sum of all bodySamples, we can't sum the bodySamples at the end for this, so here use the reversed way: use TotalSamples minus TotalCallsiteSamples to recover the totalBodySamples.

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

1039

removed.

1249

Good idea! The implementation in https://reviews.llvm.org/D121651 looks good to me, so I copied that (except the "CSFlat", will leave it to the original patch), but I have scratching my head with the term nest, CS-nested, flat, cs-flat...I will follow your decision.

[wlei]

Updating D146452: [AutoFDO] Use flattened profiles for profile staleness metrics

[wenlei]

lgtm, thanks.

[hoy]

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

1249

Thanks. Nest and Flat sound good to me for now.

[mingmingl]

llvm/include/llvm/ProfileData/SampleProf.h

1319

thanks! It's true that updating map while iterating the elements are complicated; and the current way of writing looks reasonable then (I tend to be cautious when seeing std::move but obviously over cautious here :))

llvm/lib/Transforms/IPO/SampleProfile.cpp

2077–2078

thanks for confirming!

[bjope]

llvm/test/tools/llvm-profdata/sample-flatten-profile.test

6

Downstream I got this when building with expensive checks:

Command Output (stderr):
--
/repo/bbiswjenk/fem2s10-eiffel176/workspace/llvm/llvm-main-expensive-checks/llvm/test/tools/llvm-profdata/sample-flatten-profile.test:13:14: error: CHECK-NEXT: expected string not found in input
; CHECK-NEXT: !CFGChecksum: 1
             ^
<stdin>:6:7: note: scanning from here
 10: 1
      ^
<stdin>:7:2: note: possible intended match here
 !CFGChecksum: 0
 ^

Input file: <stdin>
Check file: /repo/bbiswjenk/fem2s10-eiffel176/workspace/llvm/llvm-main-expensive-checks/llvm/test/tools/llvm-profdata/sample-flatten-profile.test

-dump-input=help explains the following input dump.

Input was:
<<<<<<
           1: baz:169:10 
           2:  1: 10 
           3:  3: 20 
           4:  5: 20 foo:20 
           5:  6: 2 bar:2 
           6:  10: 1 
next:13'0           X error: no match found
           7:  !CFGChecksum: 0 
next:13'0     ~~~~~~~~~~~~~~~~~
next:13'1      ?                possible intended match
           8: foo:134:21 
next:13'0     ~~~~~~~~~~~
           9:  1: 21 
next:13'0     ~~~~~~~
          10:  3: 12 bar:11 
next:13'0     ~~~~~~~~~~~~~~
          11:  4: 1 
next:13'0     ~~~~~~
          12:  !CFGChecksum: 3 
next:13'0     ~~~~~~~~~~~~~~~~~
           .
           .
           .
>>>>>>

Although I haven't seen that in any upstream buildbot.

Could it perhaps be that the order in which things are outputted is sensitive to iteration order of some maps?
FWIW, SampleProfileMap is an UnorderedMap and you are at least iterating over such maps in a few places (and I think SampleProfReader/SampleProfWriter is using sortFuncProfiles to sort map entries when needed).

[wlei]

llvm/test/tools/llvm-profdata/sample-flatten-profile.test

6

Thanks for the comment. You're right, the checksum num should be the same for the same func name profile, I missed adding one checksum, it should be fixed by https://reviews.llvm.org/rG3520f6d66645.

llvm/docs/CommandGuide/llvm-profdata.rst

  This option can only be used with sample-based profile in extbinary format.
 
 .. option:: --gen-partial-profile=[true|false]
 
  Mark the profile to be a partial profile which only provides partial profile
  coverage for the optimized target. This option can only be used with
  sample-based profile in extbinary format.
 
+.. option:: --convert-sample-profile-layout=[nest|flat]
+
+ Convert the merged profile into a profile with a new layout. Supported
+ layout are ``nest``(Nested profile, the input should be CS flat profile) and
+ ``flat``(Profile with nested inlinees flattened out).
+
 .. option:: --supplement-instr-with-sample=<file>
 
  Supplement an instrumentation profile with sample profile. The sample profile
  is the input of the flag. Output will be in instrumentation format (only works
  with -instr).
 
 .. option:: --zero-counter-threshold=<float>
 

llvm/include/llvm/ProfileData/SampleProf.h

enum SampleProfileFormat {
   SPF_None = 0,
   SPF_Text = 0x1,
   SPF_Compact_Binary = 0x2,
   SPF_GCC = 0x3,
   SPF_Ext_Binary = 0x4,
   SPF_Binary = 0xff
 };
 
+enum SampleProfileLayout {
+  SPL_None = 0,
+  SPL_Nest = 0x1,
+  SPL_Flat = 0x2,
+};
+
 static inline uint64_t SPMagic(SampleProfileFormat Format = SPF_Binary) {
   return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
          uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
          uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
          uint64_t('2') << (64 - 56) | uint64_t(Format);
 }
 
 /// Get the proper representation of a string according to whether the
void removeTotalSamples(uint64_t Num) {
     if (TotalSamples < Num)
       TotalSamples = 0;
     else
       TotalSamples -= Num;
   }
 
   void setTotalSamples(uint64_t Num) { TotalSamples = Num; }
 
+  void setHeadSamples(uint64_t Num) { TotalHeadSamples = Num; }
+
   sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) {
     bool Overflowed;
     TotalHeadSamples =
         SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed);
     return Overflowed ? sampleprof_error::counter_overflow
                       : sampleprof_error::success;
   }
 
public:
   /// Return all the samples collected in the body of the function.
   const BodySampleMap &getBodySamples() const { return BodySamples; }
 
   /// Return all the callsite samples collected in the body of the function.
   const CallsiteSampleMap &getCallsiteSamples() const {
     return CallsiteSamples;
   }
 
+  CallsiteSampleMap &getCallsiteSamples() { return CallsiteSamples; }
+
   /// Return the maximum of sample counts in a function body. When SkipCallSite
   /// is false, which is the default, the return count includes samples in the
   /// inlined functions. When SkipCallSite is true, the return count only
   /// considers the body samples.
   uint64_t getMaxCountInside(bool SkipCallSite = false) const {
     uint64_t MaxCount = 0;
     for (const auto &L : getBodySamples())
       MaxCount = std::max(MaxCount, L.second.getSamples());
void trimAndMergeColdContextProfiles(uint64_t ColdCountThreshold,
                                        bool TrimBaseProfileOnly);
   // Canonicalize context profile name and attributes.
   void canonicalizeContextProfiles();
 
 private:
   SampleProfileMap &ProfileMap;
 };
 
-// CSProfileConverter converts a full context-sensitive flat sample profile into
-// a nested context-sensitive sample profile.
-class CSProfileConverter {
+/// Helper class for profile conversion.
+///
+/// It supports full context-sensitive profile to nested profile conversion,
+/// nested profile to flatten profile conversion, etc.
+class ProfileConverter {
 public:
-  CSProfileConverter(SampleProfileMap &Profiles);
-  void convertProfiles();
+  ProfileConverter(SampleProfileMap &Profiles);
+  // Convert a full context-sensitive flat sample profile into a nested sample
+  // profile.
+  void convertCSProfiles();
   struct FrameNode {
     FrameNode(StringRef FName = StringRef(),
               FunctionSamples *FSamples = nullptr,
               LineLocation CallLoc = {0, 0})
         : FuncName(FName), FuncSamples(FSamples), CallSiteLoc(CallLoc){};
 
     // Map line+discriminator location to child frame
     std::map<uint64_t, FrameNode> AllChildFrames;
     // Function name for current frame
     StringRef FuncName;
     // Function Samples for current frame
     FunctionSamples *FuncSamples;
     // Callsite location in parent context
     LineLocation CallSiteLoc;
 
     FrameNode *getOrCreateChildFrame(const LineLocation &CallSite,
                                      StringRef CalleeName);
   };
 
+  static void flattenProfile(SampleProfileMap &ProfileMap,
+                             bool ProfileIsCS = false) {
+    SampleProfileMap TmpProfiles;
+    flattenProfile(ProfileMap, TmpProfiles, ProfileIsCS);
+    ProfileMap = std::move(TmpProfiles);
+  }
+
+  static void flattenProfile(const SampleProfileMap &InputProfiles,
+                             SampleProfileMap &OutputProfiles,
+                             bool ProfileIsCS = false) {
+    if (ProfileIsCS) {
+      for (const auto &I : InputProfiles)
+        OutputProfiles[I.second.getName()].merge(I.second);
+      // Retain the profile name and clear the full context for each function
+      // profile.
+      for (auto &I : OutputProfiles)
+        I.second.setContext(SampleContext(I.first));
+    } else {
+      for (const auto &I : InputProfiles)
+        flattenNestedProfile(OutputProfiles, I.second);
+    }
+  }
+
 private:
+  static void flattenNestedProfile(SampleProfileMap &OutputProfiles,
+                                   const FunctionSamples &FS) {
+    // To retain the context, checksum, attributes of the original profile, make
+    // a copy of it if no profile is found.
+    SampleContext &Context = FS.getContext();
+    auto Ret = OutputProfiles.emplace(Context, FS);
+    FunctionSamples &Profile = Ret.first->second;
+    if (Ret.second) {
+      // When it's the copy of the old profile, just clear all the inlinees'
+      // samples.
+      Profile.getCallsiteSamples().clear();
+      // We recompute TotalSamples later, so here set to zero.
+      Profile.setTotalSamples(0);
+    } else {
+      for (const auto &Line : FS.getBodySamples()) {
+        Profile.addBodySamples(Line.first.LineOffset, Line.first.Discriminator,
+                               Line.second.getSamples());
+      }
+    }
+
+    assert(Profile.getCallsiteSamples().empty() &&
+           "There should be no inlinees' profiles after flattening.");
+
+    // TotalSamples might not be equal to the sum of all samples from
+    // BodySamples and CallsiteSamples. So here we use "TotalSamples =
+    // Original_TotalSamples - All_of_Callsite_TotalSamples +
+    // All_of_Callsite_HeadSamples" to compute the new TotalSamples.
+    uint64_t TotalSamples = FS.getTotalSamples();
+
+    for (const auto &I : FS.getCallsiteSamples()) {
+      for (const auto &Callee : I.second) {
+        const auto &CalleeProfile = Callee.second;
+        // Add body sample.
+        Profile.addBodySamples(I.first.LineOffset, I.first.Discriminator,
+                               CalleeProfile.getHeadSamplesEstimate());
+        // Add callsite sample.
+        Profile.addCalledTargetSamples(
+            I.first.LineOffset, I.first.Discriminator, CalleeProfile.getName(),
+            CalleeProfile.getHeadSamplesEstimate());
+        // Update total samples.
+        TotalSamples = TotalSamples >= CalleeProfile.getTotalSamples()
+                           ? TotalSamples - CalleeProfile.getTotalSamples()
+                           : 0;
+        TotalSamples += CalleeProfile.getHeadSamplesEstimate();
+        // Recursively convert callee profile.
+        flattenNestedProfile(OutputProfiles, CalleeProfile);
+      }
+    }
+    Profile.addTotalSamples(TotalSamples);
+
+    Profile.setHeadSamples(Profile.getHeadSamplesEstimate());
+  }
+
   // Nest all children profiles into the profile of Node.
-  void convertProfiles(FrameNode &Node);
+  void convertCSProfiles(FrameNode &Node);
   FrameNode *getOrCreateContextPath(const SampleContext &Context);
 
   SampleProfileMap &ProfileMap;
   FrameNode RootFrame;
 };
 
 /// ProfileSymbolList records the list of function symbols shown up
 /// in the binary used to generate the profile. It is useful to

llvm/lib/ProfileData/SampleProf.cpp

void ProfileSymbolList::dump(raw_ostream &OS) const {
   OS << "======== Dump profile symbol list ========\n";
   std::vector<StringRef> SortedList(Syms.begin(), Syms.end());
   llvm::sort(SortedList);
 
   for (auto &Sym : SortedList)
     OS << Sym << "\n";
 }
 
-CSProfileConverter::FrameNode *
-CSProfileConverter::FrameNode::getOrCreateChildFrame(
-    const LineLocation &CallSite, StringRef CalleeName) {
+ProfileConverter::FrameNode *
+ProfileConverter::FrameNode::getOrCreateChildFrame(const LineLocation &CallSite,
+                                                   StringRef CalleeName) {
   uint64_t Hash = FunctionSamples::getCallSiteHash(CalleeName, CallSite);
   auto It = AllChildFrames.find(Hash);
   if (It != AllChildFrames.end()) {
     assert(It->second.FuncName == CalleeName &&
            "Hash collision for child context node");
     return &It->second;
   }
 
   AllChildFrames[Hash] = FrameNode(CalleeName, nullptr, CallSite);
   return &AllChildFrames[Hash];
 }
 
-CSProfileConverter::CSProfileConverter(SampleProfileMap &Profiles)
+ProfileConverter::ProfileConverter(SampleProfileMap &Profiles)
     : ProfileMap(Profiles) {
   for (auto &FuncSample : Profiles) {
     FunctionSamples *FSamples = &FuncSample.second;
     auto *NewNode = getOrCreateContextPath(FSamples->getContext());
     assert(!NewNode->FuncSamples && "New node cannot have sample profile");
     NewNode->FuncSamples = FSamples;
   }
 }
 
-CSProfileConverter::FrameNode *
-CSProfileConverter::getOrCreateContextPath(const SampleContext &Context) {
+ProfileConverter::FrameNode *
+ProfileConverter::getOrCreateContextPath(const SampleContext &Context) {
   auto Node = &RootFrame;
   LineLocation CallSiteLoc(0, 0);
   for (auto &Callsite : Context.getContextFrames()) {
     Node = Node->getOrCreateChildFrame(CallSiteLoc, Callsite.FuncName);
     CallSiteLoc = Callsite.Location;
   }
   return Node;
 }
 
-void CSProfileConverter::convertProfiles(CSProfileConverter::FrameNode &Node) {
+void ProfileConverter::convertCSProfiles(ProfileConverter::FrameNode &Node) {
   // Process each child profile. Add each child profile to callsite profile map
   // of the current node `Node` if `Node` comes with a profile. Otherwise
   // promote the child profile to a standalone profile.
   auto *NodeProfile = Node.FuncSamples;
   for (auto &It : Node.AllChildFrames) {
     auto &ChildNode = It.second;
-    convertProfiles(ChildNode);
+    convertCSProfiles(ChildNode);
     auto *ChildProfile = ChildNode.FuncSamples;
     if (!ChildProfile)
       continue;
     SampleContext OrigChildContext = ChildProfile->getContext();
     // Reset the child context to be contextless.
     ChildProfile->getContext().setName(OrigChildContext.getName());
     if (NodeProfile) {
       // Add child profile to the callsite profile map.
if (!NodeProfile) {
           ContextDuplicatedIntoBase);
     }
 
     // Remove the original child profile.
     ProfileMap.erase(OrigChildContext);
   }
 }
 
-void CSProfileConverter::convertProfiles() { convertProfiles(RootFrame); }
+void ProfileConverter::convertCSProfiles() { convertCSProfiles(RootFrame); }

llvm/lib/Transforms/IPO/SampleProfile.cpp

static cl::opt<bool> ReportProfileStaleness(
     "report-profile-staleness", cl::Hidden, cl::init(false),
     cl::desc("Compute and report stale profile statistical metrics."));
 
 static cl::opt<bool> PersistProfileStaleness(
     "persist-profile-staleness", cl::Hidden, cl::init(false),
     cl::desc("Compute stale profile statistical metrics and write it into the "
              "native object file(.llvm_stats section)."));
 
+static cl::opt<bool> FlattenProfileForMatching(
+    "flatten-profile-for-matching", cl::Hidden, cl::init(true),
+    cl::desc(
+        "Use flattened profile for stale profile detection and matching."));
+
 static cl::opt<bool> ProfileSampleAccurate(
     "profile-sample-accurate", cl::Hidden, cl::init(false),
     cl::desc("If the sample profile is accurate, we will mark all un-sampled "
              "callsite and function as having 0 samples. Otherwise, treat "
              "un-sampled callsites and functions conservatively as unknown. "));
 
 static cl::opt<bool> ProfileSampleBlockAccurate(
     "profile-sample-block-accurate", cl::Hidden, cl::init(false),
using CandidateQueue =
     PriorityQueue<InlineCandidate, std::vector<InlineCandidate>,
                   CandidateComparer>;
 
 // Sample profile matching - fuzzy match.
 class SampleProfileMatcher {
   Module &M;
   SampleProfileReader &Reader;
   const PseudoProbeManager *ProbeManager;
+  SampleProfileMap FlattenedProfiles;
 
   // Profile mismatching statstics.
   uint64_t TotalProfiledCallsites = 0;
   uint64_t NumMismatchedCallsites = 0;
   uint64_t MismatchedCallsiteSamples = 0;
   uint64_t TotalCallsiteSamples = 0;
   uint64_t TotalProfiledFunc = 0;
   uint64_t NumMismatchedFuncHash = 0;
   uint64_t MismatchedFuncHashSamples = 0;
   uint64_t TotalFuncHashSamples = 0;
 
 public:
   SampleProfileMatcher(Module &M, SampleProfileReader &Reader,
                        const PseudoProbeManager *ProbeManager)
-      : M(M), Reader(Reader), ProbeManager(ProbeManager) {}
+      : M(M), Reader(Reader), ProbeManager(ProbeManager) {
+    if (FlattenProfileForMatching) {
+      ProfileConverter::flattenProfile(Reader.getProfiles(), FlattenedProfiles,
+                                       FunctionSamples::ProfileIsCS);
+    }
+  }
+
+  FunctionSamples *getFlattenedSamplesFor(const Function &F) {
+    StringRef CanonFName = FunctionSamples::getCanonicalFnName(F);
+    auto It = FlattenedProfiles.find(CanonFName);
+    if (It != FlattenedProfiles.end())
+      return &It->second;
+    return nullptr;
+  }
+
   void detectProfileMismatch();
   void detectProfileMismatch(const Function &F, const FunctionSamples &FS);
 };
 
 /// Sample profile pass.
 ///
 /// This pass reads profile data from the file specified by
 /// -sample-profile-file and annotates every affected function with the
if (!ProbeManager->moduleIsProbed(M)) {
           "Pseudo-probe-based profile requires SampleProfileProbePass";
       Ctx.diagnose(DiagnosticInfoSampleProfile(M.getModuleIdentifier(), Msg,
                                                DS_Warning));
       return false;
     }
   }
 
   if (ReportProfileStaleness || PersistProfileStaleness) {
     MatchingManager =
         std::make_unique<SampleProfileMatcher>(M, *Reader, ProbeManager.get());
   }
 
   return true;
 }
 
 void SampleProfileMatcher::detectProfileMismatch(const Function &F,
                                                  const FunctionSamples &FS) {
   if (FunctionSamples::ProfileIsProbeBased) {
     uint64_t Count = FS.getTotalSamples();
     TotalFuncHashSamples += Count;
     TotalProfiledFunc++;
     if (!ProbeManager->profileIsValid(F, FS)) {
       MismatchedFuncHashSamples += Count;
       NumMismatchedFuncHash++;
       return;
     }
   }
 
   std::unordered_set<LineLocation, LineLocationHash> MatchedCallsiteLocs;
 
   // Go through all the callsites on the IR and flag the callsite if the target
   // name is the same as the one in the profile.
   for (auto &BB : F) {
for (auto &I : FS.getCallsiteSamples()) {
     }
   }
 }
 
 void SampleProfileMatcher::detectProfileMismatch() {
   for (auto &F : M) {
     if (F.isDeclaration() || !F.hasFnAttribute("use-sample-profile"))
       continue;
-    FunctionSamples *FS = Reader.getSamplesFor(F);
+    FunctionSamples *FS = nullptr;
+    if (FlattenProfileForMatching)
+      FS = getFlattenedSamplesFor(F);
+    else
+      FS = Reader.getSamplesFor(F);
     if (!FS)
       continue;
     detectProfileMismatch(F, *FS);
   }
 
   if (ReportProfileStaleness) {
     if (FunctionSamples::ProfileIsProbeBased) {
       errs() << "(" << NumMismatchedFuncHash << "/" << TotalProfiledFunc << ")"

llvm/test/Transforms/SampleProfile/Inputs/profile-mismatch-cs.prof

+[main]:30:0
+ 0: 0
+ 1.1: 0
+ 3: 10 matched:10
+ 4: 10
+ 5: 10 bar_mismatch:10
+ 7: 5 foo:5
+ 8: 0
+[main:7 @ foo]:15:5
+ 1: 5
+ 2: 5
+ 3: 5 inlinee_mismatch:5
+[bar]:10:10
+ 1: 10
+[matched]:10:10
+ 1: 10
+[main:7 @ foo:3 @ inlinee_mismatch]:5:5
+ 1: 5

llvm/test/Transforms/SampleProfile/Inputs/profile-mismatch.prof

 main:30:0
  0: 0
  1.1: 0
  3: 10 matched:10
  4: 10
  5: 10 bar_mismatch:10
  8: 0
- 7: foo:10
+ 7: foo:15
   1: 5
   2: 5
+  3: inlinee_mismatch:5
+   1: 5
 bar:10:10
  1: 10
 matched:10:10
  1: 10

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
 
-; RUN: llvm-profdata merge --sample --text --gen-cs-nested-profile %S/Inputs/profile-context-tracker.prof -o %t.prof
+; RUN: llvm-profdata merge --sample --text --convert-sample-profile-layout=nest  %S/Inputs/profile-context-tracker.prof -o %t.prof
 ; RUN: opt < %s -passes=sample-profile -sample-profile-file=%t.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
 
 ; 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
 ; RUN: opt < %s -passes=sample-profile -sample-profile-file=%t.prof -sample-profile-prioritized-inline -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=999990 -profile-sample-accurate -S -pass-remarks=inline -o /dev/null 2>&1 | FileCheck %s --check-prefix=INLINE-BASE

llvm/test/Transforms/SampleProfile/csspgo-use-preinliner.ll

 ; Test for CSSPGO's sample loader inlining to make sure it can use llvm-profgen preinliner's decision
 
 ; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/csspgo-use-preinliner.prof -pass-remarks=inline -sample-profile-prioritized-inline -profile-sample-accurate -sample-profile-use-preinliner=0 -S 2>&1 | FileCheck %s --check-prefix=DEFAULT
 ; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/csspgo-use-preinliner.prof -pass-remarks=inline -sample-profile-prioritized-inline -profile-sample-accurate -sample-profile-use-preinliner=1 -S 2>&1 | FileCheck %s --check-prefix=PREINLINE
 
-; RUN: llvm-profdata merge --sample --text --gen-cs-nested-profile -generate-merged-base-profiles=0 %S/Inputs/csspgo-use-preinliner.prof -o %t.prof
+; RUN: llvm-profdata merge --sample --text --convert-sample-profile-layout=nest  -generate-merged-base-profiles=0 %S/Inputs/csspgo-use-preinliner.prof -o %t.prof
 ; RUN: opt < %s -passes=sample-profile -sample-profile-file=%t.prof -pass-remarks=inline -sample-profile-prioritized-inline -profile-sample-accurate -sample-profile-use-preinliner=0 -S 2>&1 | FileCheck %s --check-prefix=DEFAULT
 ; RUN: opt < %s -passes=sample-profile -sample-profile-file=%t.prof -pass-remarks=inline -sample-profile-prioritized-inline -profile-sample-accurate -sample-profile-use-preinliner=1 -S 2>&1 | FileCheck %s --check-prefix=PREINLINE
 
 ; DEFAULT: '_Z5funcAi' inlined into 'main'
 ; DEFAULT-NOT: inlined into
 
 ; PREINLINE-NOT: inlined into
 ; `[main:3 @ _Z5funcAi]` does not have preinline decision, so it's up for loader inliner to decided.

llvm/test/Transforms/SampleProfile/profile-mismatch-flattened-profile.ll

+; REQUIRES: x86_64-linux
+; RUN: opt < %S/profile-mismatch.ll -passes=sample-profile -sample-profile-file=%S/Inputs/profile-mismatch.prof -report-profile-staleness -persist-profile-staleness -flatten-profile-for-matching=1 -S 2>%t -o %t.ll
+; RUN: FileCheck %s --input-file %t
+; RUN: FileCheck %s --input-file %t.ll -check-prefix=CHECK-MD
+
+; RUN: opt < %S/profile-mismatch.ll -passes=sample-profile -sample-profile-file=%S/Inputs/profile-mismatch-cs.prof -report-profile-staleness -persist-profile-staleness -flatten-profile-for-matching=1 -S 2>%t -o %t.ll
+; RUN: FileCheck %s --input-file %t
+; RUN: FileCheck %s --input-file %t.ll -check-prefix=CHECK-MD
+
+
+; CHECK: (3/4) of callsites' profile are invalid and (20/30) of samples are discarded due to callsite location mismatch.
+
+; CHECK-MD: ![[#]] = !{!"NumMismatchedCallsites", i64 3, !"TotalProfiledCallsites", i64 4, !"MismatchedCallsiteSamples", i64 20, !"TotalCallsiteSamples", i64 30}

llvm/test/Transforms/SampleProfile/profile-mismatch.ll

 ; REQUIRES: x86_64-linux
-; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/profile-mismatch.prof -report-profile-staleness -persist-profile-staleness -S 2>%t -o %t.ll
+; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/profile-mismatch.prof -report-profile-staleness -persist-profile-staleness -flatten-profile-for-matching=0 -S 2>%t -o %t.ll
 ; RUN: FileCheck %s --input-file %t
 ; RUN: FileCheck %s --input-file %t.ll -check-prefix=CHECK-MD
 ; RUN: llc < %t.ll -filetype=obj -o %t.obj
 ; RUN: llvm-objdump --section-headers %t.obj | FileCheck %s --check-prefix=CHECK-OBJ
 ; RUN: llc < %t.ll -filetype=asm -o - | FileCheck %s --check-prefix=CHECK-ASM
 
 ; CHECK: (2/3) of callsites' profile are invalid and (15/25) of samples are discarded due to callsite location mismatch.
 

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

+[baz]:150:10
+ 1: 10
+ 3: 20
+ 5: 20 foo:20
+[foo]:102:1
+ 1: 1
+ 3: 1
+[main]:91:1
+ 4: 1
+ 4.2: 1
+ 7: 1
+ 9: 3 bar:2 foo:1
+ 10: 3 baz:2 foo:1
+[main:10 @ foo]:2:1
+ 3: 1 bar:1
+ 4: 1
+[bar]:1:1
+ 1: 1
+[main:10 @ foo:3 @ bar]:1:1
+ 1: 1

llvm/test/tools/llvm-profdata/Inputs/sample-flatten-profile.proftext

+baz:160:10
+ 1: 10
+ 3: 20
+ 5: foo:30
+  1: 20
+  3: bar:10
+   1: 10
+   !CFGChecksum: 4
+   !Attributes: 4
+  !CFGChecksum: 3
+  !Attributes: 3
+ !CFGChecksum: 1
+ !Attributes: 1
+main:110:1
+ 4: 1
+ 4.2: 1
+ 7: 1
+ 9: 3 bar:2 foo:1
+ 10: foo:2
+  4: 1
+  3: bar:1
+   1: 1
+   !CFGChecksum: 4
+   !Attributes: 4
+  !CFGChecksum: 3
+  !Attributes: 3
+ 10: baz:20
+  10: 1
+  6: bar:3
+   1: 2
+   7: 1
+   !CFGChecksum: 4
+   !Attributes: 4
+ !CFGChecksum: 2
+ !Attributes: 2
+foo:102:1
+ 1: 1
+ 3: 1
+ !CFGChecksum: 3
+ !Attributes: 3
+bar:1:1
+ 1: 1
+ !CFGChecksum: 4
+ !Attributes: 4

llvm/test/tools/llvm-profdata/cs-sample-nested-profile.test

-RUN: llvm-profdata merge --sample --text -output=%t.proftext %S/Inputs/cs-sample-preinline.proftext --gen-cs-nested-profile=1 -generate-merged-base-profiles=0
+RUN: llvm-profdata merge --sample --text -output=%t.proftext %S/Inputs/cs-sample-preinline.proftext --convert-sample-profile-layout=nest  -generate-merged-base-profiles=0
 RUN: FileCheck %s < %t.proftext --match-full-lines --strict-whitespace
-RUN: llvm-profdata merge --sample --text -output=%t.probe.proftext %S/Inputs/cs-sample-preinline-probe.proftext --gen-cs-nested-profile=1 -generate-merged-base-profiles=0
+RUN: llvm-profdata merge --sample --text -output=%t.probe.proftext %S/Inputs/cs-sample-preinline-probe.proftext --convert-sample-profile-layout=nest  -generate-merged-base-profiles=0
 RUN: FileCheck %s < %t.probe.proftext --match-full-lines --strict-whitespace -check-prefix=PROBE
-RUN: llvm-profdata merge --sample --extbinary -output=%t.profbin %S/Inputs/cs-sample-preinline.proftext --gen-cs-nested-profile=1 -generate-merged-base-profiles=0
+RUN: llvm-profdata merge --sample --extbinary -output=%t.profbin %S/Inputs/cs-sample-preinline.proftext --convert-sample-profile-layout=nest  -generate-merged-base-profiles=0
 RUN: llvm-profdata merge --sample --text -output=%t2.proftext %t.profbin
 RUN: FileCheck %s < %t2.proftext --match-full-lines --strict-whitespace
 RUN: llvm-profdata show --sample -show-sec-info-only %t.profbin | FileCheck %s -check-prefix=PREINLINE
-RUN: llvm-profdata merge --sample --text -output=%t3.proftext %S/Inputs/cs-sample-preinline.proftext --gen-cs-nested-profile=1 -generate-merged-base-profiles=1
+RUN: llvm-profdata merge --sample --text -output=%t3.proftext %S/Inputs/cs-sample-preinline.proftext --convert-sample-profile-layout=nest  -generate-merged-base-profiles=1
 RUN: FileCheck %s < %t3.proftext --match-full-lines --strict-whitespace -check-prefix=RECOUNT
-RUN: llvm-profdata merge --sample --extbinary -output=%t2.profbin %S/Inputs/cs-sample-preinline.proftext --gen-cs-nested-profile=1 -generate-merged-base-profiles=1
+RUN: llvm-profdata merge --sample --extbinary -output=%t2.profbin %S/Inputs/cs-sample-preinline.proftext --convert-sample-profile-layout=nest  -generate-merged-base-profiles=1
 RUN: llvm-profdata show -sample -detailed-summary %S/Inputs/cs-sample-preinline.proftext | FileCheck %s -check-prefix=SUMMARY
 RUN: llvm-profdata show -sample -detailed-summary %t2.profbin | FileCheck %s -check-prefix=SUMMARY-NEST
 RUN: llvm-profdata show -sample -detailed-summary %t3.proftext | FileCheck %s -check-prefix=SUMMARY-NEST
 
 
 ; CHECK:main:1968621:12
 ; CHECK-NEXT: 2: 24
 ; CHECK-NEXT: 3: 17 _Z5funcAi:7

llvm/test/tools/llvm-profdata/sample-flatten-profile.test

+; RUN: llvm-profdata merge --sample --convert-sample-profile-layout=flat --text %S/Inputs/sample-flatten-profile.proftext -o - | FileCheck %s --match-full-lines --strict-whitespace
+; RUN: llvm-profdata merge --sample --extbinary %S/Inputs/sample-flatten-profile.proftext -o %t2 && llvm-profdata merge --sample --convert-sample-profile-layout=flat --text %t2 -o - | FileCheck %s --match-full-lines --strict-whitespace
+
+; RUN: llvm-profdata merge --sample --convert-sample-profile-layout=flat --text %S/Inputs/sample-flatten-profile-cs.proftext -o - | FileCheck %s --match-full-lines --strict-whitespace --check-prefix=CHECK-CS
+; RUN: llvm-profdata merge --sample --extbinary %S/Inputs/sample-flatten-profile-cs.proftext -o %t2 && llvm-profdata merge --sample --convert-sample-profile-layout=flat --text %t2 -o - | FileCheck %s --match-full-lines --strict-whitespace --check-prefix=CHECK-CS
+
+; CHECK:baz:169:10
+; CHECK-NEXT: 1: 10
+; CHECK-NEXT: 3: 20
+; CHECK-NEXT: 5: 20 foo:20
+; CHECK-NEXT: 6: 2 bar:2
+; CHECK-NEXT: 10: 1
+; CHECK-NEXT: !CFGChecksum: 1
+; CHECK-NEXT: !Attributes: 1
+; CHECK-NEXT:foo:134:21
+; CHECK-NEXT: 1: 21
+; CHECK-NEXT: 3: 12 bar:11
+; CHECK-NEXT: 4: 1
+; CHECK-NEXT: !CFGChecksum: 3
+; CHECK-NEXT: !Attributes: 3
+; CHECK-NEXT:main:91:1
+; CHECK-NEXT: 4: 1
+; CHECK-NEXT: 4.2: 1
+; CHECK-NEXT: 7: 1
+; CHECK-NEXT: 9: 3 bar:2 foo:1
+; CHECK-NEXT: 10: 3 baz:2 foo:1
+; CHECK-NEXT: !CFGChecksum: 2
+; CHECK-NEXT: !Attributes: 2
+; CHECK-NEXT:bar:15:14
+; CHECK-NEXT: 1: 14
+; CHECK-NEXT: 7: 1
+; CHECK-NEXT: !CFGChecksum: 4
+; CHECK-NEXT: !Attributes: 4
+
+; CHECK-CS:baz:150:10
+; CHECK-CS-NEXT: 1: 10
+; CHECK-CS-NEXT: 3: 20
+; CHECK-CS-NEXT: 5: 20 foo:20
+; CHECK-CS-NEXT:foo:104:2
+; CHECK-CS-NEXT: 1: 1
+; CHECK-CS-NEXT: 3: 2 bar:1
+; CHECK-CS-NEXT: 4: 1
+; CHECK-CS-NEXT:main:91:1
+; CHECK-CS-NEXT: 4: 1
+; CHECK-CS-NEXT: 4.2: 1
+; CHECK-CS-NEXT: 7: 1
+; CHECK-CS-NEXT: 9: 3 bar:2 foo:1
+; CHECK-CS-NEXT: 10: 3 baz:2 foo:1
+; CHECK-CS-NEXT:bar:2:2
+; CHECK-CS-NEXT: 1: 2

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

else
       Writer.setPartialProfile();
   }
 }
 
 static void
 mergeSampleProfile(const WeightedFileVector &Inputs, SymbolRemapper *Remapper,
                    StringRef OutputFilename, ProfileFormat OutputFormat,
                    StringRef ProfileSymbolListFile, bool CompressAllSections,
-                   bool UseMD5, bool GenPartialProfile, bool GenCSNestedProfile,
+                   bool UseMD5, bool GenPartialProfile,
+                   SampleProfileLayout ProfileLayout,
                    bool SampleMergeColdContext, bool SampleTrimColdContext,
                    bool SampleColdContextFrameDepth, FailureMode FailMode,
                    bool DropProfileSymbolList, size_t OutputSizeLimit) {
   using namespace sampleprof;
   SampleProfileMap ProfileMap;
   SmallVector<std::unique_ptr<sampleprof::SampleProfileReader>, 5> Readers;
   LLVMContext Context;
   sampleprof::ProfileSymbolList WriterList;
if (!DropProfileSymbolList) {
           Reader->getProfileSymbolList();
       if (ReaderList)
         WriterList.merge(*ReaderList);
     }
   }
 
   if (ProfileIsCS && (SampleMergeColdContext || SampleTrimColdContext)) {
     // Use threshold calculated from profile summary unless specified.
     SampleProfileSummaryBuilder Builder(ProfileSummaryBuilder::DefaultCutoffs);
     auto Summary = Builder.computeSummaryForProfiles(ProfileMap);
     uint64_t SampleProfColdThreshold =
         ProfileSummaryBuilder::getColdCountThreshold(
             (Summary->getDetailedSummary()));
 
     // Trim and merge cold context profile using cold threshold above;
     SampleContextTrimmer(ProfileMap)
         .trimAndMergeColdContextProfiles(
             SampleProfColdThreshold, SampleTrimColdContext,
             SampleMergeColdContext, SampleColdContextFrameDepth, false);
   }
 
-  if (ProfileIsCS && GenCSNestedProfile) {
-    CSProfileConverter CSConverter(ProfileMap);
-    CSConverter.convertProfiles();
+  if (ProfileLayout == llvm::sampleprof::SPL_Flat) {
+    ProfileConverter::flattenProfile(ProfileMap, FunctionSamples::ProfileIsCS);
+    ProfileIsCS = FunctionSamples::ProfileIsCS = false;
+  } else if (ProfileIsCS && ProfileLayout == llvm::sampleprof::SPL_Nest) {
+    ProfileConverter CSConverter(ProfileMap);
+    CSConverter.convertCSProfiles();
     ProfileIsCS = FunctionSamples::ProfileIsCS = false;
   }
 
   auto WriterOrErr =
       SampleProfileWriter::create(OutputFilename, FormatMap[OutputFormat]);
   if (std::error_code EC = WriterOrErr.getError())
     exitWithErrorCode(EC, OutputFilename);
 
cl::opt<unsigned> SupplMinSizeThreshold(
       "suppl-min-size-threshold", cl::init(10), cl::Hidden,
       cl::desc("If the size of a function is smaller than the threshold, "
                "assume it can be inlined by PGO early inliner and it won't "
                "be adjusted based on sample profile."));
   cl::opt<unsigned> InstrProfColdThreshold(
       "instr-prof-cold-threshold", cl::init(0), cl::Hidden,
       cl::desc("User specified cold threshold for instr profile which will "
                "override the cold threshold got from profile summary. "));
-  cl::opt<bool> GenCSNestedProfile(
-      "gen-cs-nested-profile", cl::Hidden, cl::init(false),
-      cl::desc("Generate nested function profiles for CSSPGO"));
+  cl::opt<SampleProfileLayout> ProfileLayout(
+      "convert-sample-profile-layout",
+      cl::desc("Convert the generated profile to a profile with a new layout"),
+      cl::init(SPL_None),
+      cl::values(
+          clEnumValN(SPL_Nest, "nest",
+                     "Nested profile, the input should be CS flat profile"),
+          clEnumValN(SPL_Flat, "flat",
+                     "Profile with nested inlinee flatten out")));
   cl::opt<std::string> DebugInfoFilename(
       "debug-info", cl::init(""),
       cl::desc("Use the provided debug info to correlate the raw profile."));
   cl::opt<std::string> ProfiledBinary(
       "profiled-binary", cl::init(""),
       cl::desc("Path to binary from which the profile was collected."));
   cl::opt<bool> DropProfileSymbolList(
       "drop-profile-symbol-list", cl::init(false), cl::Hidden,
if (!SupplInstrWithSample.empty()) {
     return 0;
   }
 
   if (ProfileKind == instr)
     mergeInstrProfile(WeightedInputs, DebugInfoFilename, Remapper.get(),
                       OutputFilename, OutputFormat, OutputSparse, NumThreads,
                       FailureMode, ProfiledBinary);
   else
-    mergeSampleProfile(
-        WeightedInputs, Remapper.get(), OutputFilename, OutputFormat,
-        ProfileSymbolListFile, CompressAllSections, UseMD5, GenPartialProfile,
-        GenCSNestedProfile, SampleMergeColdContext, SampleTrimColdContext,
-        SampleColdContextFrameDepth, FailureMode, DropProfileSymbolList,
-        OutputSizeLimit);
+    mergeSampleProfile(WeightedInputs, Remapper.get(), OutputFilename,
+                       OutputFormat, ProfileSymbolListFile, CompressAllSections,
+                       UseMD5, GenPartialProfile, ProfileLayout,
+                       SampleMergeColdContext, SampleTrimColdContext,
+                       SampleColdContextFrameDepth, FailureMode,
+                       DropProfileSymbolList, OutputSizeLimit);
   return 0;
 }
 
 /// Computer the overlap b/w profile BaseFilename and profile TestFilename.
 static void overlapInstrProfile(const std::string &BaseFilename,
                                 const std::string &TestFilename,
                                 const OverlapFuncFilters &FuncFilter,
                                 raw_fd_ostream &OS, bool IsCS) {

llvm/tools/llvm-profgen/ProfileGenerator.cpp

void CSProfileGenerator::postProcessProfiles() {
   // Merge function samples of CS profile to calculate profile density.
   sampleprof::SampleProfileMap ContextLessProfiles;
   for (const auto &I : ProfileMap) {
     ContextLessProfiles[I.second.getName()].merge(I.second);
   }
 
   calculateAndShowDensity(ContextLessProfiles);
   if (GenCSNestedProfile) {
-    CSProfileConverter CSConverter(ProfileMap);
-    CSConverter.convertProfiles();
+    ProfileConverter CSConverter(ProfileMap);
+    CSConverter.convertCSProfiles();
     FunctionSamples::ProfileIsCS = false;
   }
 }
 
 void ProfileGeneratorBase::computeSummaryAndThreshold(
     SampleProfileMap &Profiles) {
   SampleProfileSummaryBuilder Builder(ProfileSummaryBuilder::DefaultCutoffs);
   Summary = Builder.computeSummaryForProfiles(Profiles);