[llvm-profdata] Convert nested profile to CS flat profile.

[hoy]

Summary

Support of convert a regular nested profile to CS flat profile. This is useful for comparing the calling contexts in two different types of profiles.

[wenlei]

Some linter seems legit.

llvm/lib/ProfileData/SampleProf.cpp

499

I'm a bit confused by the name convertToCSFlatProfiles, looking at the implementation isn't this converting to nested profile?

545

Here the caller name is convertToCSNestedProfiles, but the callee on line 552 is convertToCSFlatProfiles.

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

1

Add round trip test for conversion?

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

735

Are the two flags (GenCSNestedProfile/GenCSFlatProfile and the corresponding switches) supposed to be mutually exclusive? If yes, perhaps we should make it explicit?

one way to make then mutual exclusive is to use a single switch: gen-cs-nested-profile==true means nested, false means flat. Or we can have -gen-cs-profile={nest|flat}.

[hoy]

Updating D121651: [llvm-profdata] Convert nested profile to CS flat profile.

[hoy]

llvm/lib/ProfileData/SampleProf.cpp

545

Sorry, bad auto renaming.

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

1

Done.

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

735

Introduced a --sample-profile-layout=cs|nest switch.

[hoy]

Updating D121651: [llvm-profdata] Convert nested profile to CS flat profile.

[wenlei]

llvm/include/llvm/ProfileData/SampleProf.h

102

I think flat vs nest is better here (than cs vs nest).

368–369

addCalledTarget does not add to NumSamples, but removeCalledTarget subtracts NumSamples. What's the reason for the inconsistency?

llvm/lib/ProfileData/SampleProf.cpp

512

nit: 0->ContextNone

520–521

It looks like the discrepancy comes from the fact that flat profile has target counts included in total samples, but nest profile doesn't? Is this something that should be unified? I don't remember why we choose to include target counts (rather than SampleRecord::NumSamples) in total counts for flat profile. Was it intentional?

[hoy]

llvm/include/llvm/ProfileData/SampleProf.h

102

Sounds good.

368–369

I think. It's due to the implementation of the profile generator. Callsite block samples are computed by analyzing LBR ranges, and NumSamples is updated there, while call target samples are computed based on branch samples. D122609 provides an option to make them consistent.

removeCalledTarget handles both in one place.

llvm/lib/ProfileData/SampleProf.cpp

512

Done.

520–521

The profile generator, for both flat and nest profiles, only includes callsite counts in the total count but not target counts. Ideally they would be the same. Here we are excluding target counts from callsite counts, which in turn excluded from total counts.

[hoy]

Updating D121651: [llvm-profdata] Convert nested profile to CS flat profile.

[hoy]

Rebasing

[hoy]

Rebasing.

[wenlei]

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

821

The boolean conversion seem to point to hasValue? I think the convention is mostly *ProfileIsCS.

constexpr explicit operator bool() const { return hasValue(); }

1018

nit: name this convert-sample-profile-layout. otherwise having SPL_None as default can be confusing as there's no None layout. But it makes sense for conversion to be None.

[hoy]

Updating D121651: [llvm-profdata] Convert nested profile to CS flat profile.

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

821

Here ProfileLayout is a function parameter of type SampleProfileLayout .

1018

Sounds good.

[hoy]

Updating D121651: [llvm-profdata] Convert nested profile to CS flat profile.

[wenlei]

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

821

I was talking about Optional<bool> ProfileIsCS.

[hoy]

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

821

Oh I see. Yes, *ProfileIsCS should be used instead.

Also fixed another place like this.

[hoy]

Updating D121651: [llvm-profdata] Convert nested profile to CS flat profile.

llvm/include/llvm/ProfileData/SampleProf.h

enum SampleProfileFormat {
   SPF_GCC = 0x3,
   SPF_Ext_Binary = 0x4,
   SPF_Binary = 0xff
 };
 
 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
 /// current Format uses MD5 to represent the string.
 static inline StringRef getRepInFormat(StringRef Name, bool UseMD5,
                                        std::string &GUIDBuf) {
   if (Name.empty() || !UseMD5)
public:
 
   /// Return true if this sample record contains function calls.
   bool hasCalls() const { return !CallTargets.empty(); }
 
   uint64_t getSamples() const { return NumSamples; }
   const CallTargetMap &getCallTargets() const { return CallTargets; }
   const SortedCallTargetSet getSortedCallTargets() const {
     return SortCallTargets(CallTargets);
   }
 
   /// Sort call targets in descending order of call frequency.
   static const SortedCallTargetSet SortCallTargets(const CallTargetMap &Targets) {
     SortedCallTargetSet SortedTargets;
     for (const auto &I : Targets) {
       SortedTargets.emplace(I.first(), I.second);
     }
     return SortedTargets;
   }
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 including functions
   /// inlined in it.
   uint64_t getMaxCountInside() const {
     uint64_t MaxCount = 0;
     for (const auto &L : getBodySamples())
       MaxCount = std::max(MaxCount, L.second.getSamples());
     for (const auto &C : getCallsiteSamples())
       for (const FunctionSamplesMap::value_type &F : C.second)
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.
+// a nested context-sensitive sample profile, or the other way around from a regular
+// or CS nested profile to a CS flat profile.
 class CSProfileConverter {
 public:
-  CSProfileConverter(SampleProfileMap &Profiles);
-  void convertProfiles();
+  CSProfileConverter(SampleProfileMap &Profiles,
+                     std::list<SampleContextFrameVector>* Contexts = nullptr);
+  void convertToCSNestedProfiles();
+  void convertToCSFlatProfiles();
   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);
   };
 
 private:
   // Nest all children profiles into the profile of Node.
-  void convertProfiles(FrameNode &Node);
+  void convertToCSFlatProfiles(FrameNode &Node);
+  void convertToCSFlatProfiles(FunctionSamples &FProfile,
+                       SampleProfileMap &NewProfileMap,
+                       SampleContextFrameVector &Context);
   FrameNode *getOrCreateContextPath(const SampleContext &Context);
 
   SampleProfileMap &ProfileMap;
+
+  // Underlying context table serves for sample profile writer when
+  // converting a nested profile to a CS profile.
+  std::list<SampleContextFrameVector> *Contexts;
   FrameNode RootFrame;
 };
 
 /// 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 {

llvm/lib/ProfileData/SampleProf.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/raw_ostream.h"
 #include <string>
 #include <system_error>
+#include <utility>
 
 using namespace llvm;
 using namespace sampleprof;
 
 static cl::opt<uint64_t> ProfileSymbolListCutOff(
     "profile-symbol-list-cutoff", cl::Hidden, cl::init(-1), cl::ZeroOrMore,
     cl::desc("Cutoff value about how many symbols in profile symbol list "
              "will be used. This is very useful for performance debugging"));
llvm::stable_sort(SortedProfiles, [](const NameFunctionSamples &A,
     if (A.second->getTotalSamples() == B.second->getTotalSamples())
       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;
 }
 
 LineLocation FunctionSamples::getCallSiteIdentifier(const DILocation *DIL,
                                                     bool ProfileIsFS) {
   if (FunctionSamples::ProfileIsProbeBased) {
     // In a pseudo-probe based profile, a callsite is simply represented by the
     // ID of the probe associated with the call instruction. The probe ID is
     // encoded in the Discriminator field of the call instruction's debug
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)
-    : 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::CSProfileConverter(
+    SampleProfileMap &Profiles, std::list<SampleContextFrameVector> *Contexts)
+    : ProfileMap(Profiles), Contexts(Contexts) {}
 
 CSProfileConverter::FrameNode *
 CSProfileConverter::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 CSProfileConverter::convertToCSFlatProfiles(CSProfileConverter::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);
+    convertToCSFlatProfiles(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.
       auto &SamplesMap = NodeProfile->functionSamplesAt(ChildNode.CallSiteLoc);
       SamplesMap.emplace(OrigChildContext.getName().str(), *ChildProfile);
       NodeProfile->addTotalSamples(ChildProfile->getTotalSamples());
     }
 
     // Separate child profile to be a standalone profile, if the current parent
     // profile doesn't exist. This is a duplicating operation when the child
     // profile is already incorporated into the parent which is still useful and
     // thus done optionally. It is seen that duplicating context profiles into
     // base profiles improves the code quality for thinlto build by allowing a
     // profile in the prelink phase for to-be-fully-inlined functions.
     if (!NodeProfile) {
       ProfileMap[ChildProfile->getContext()].merge(*ChildProfile);
     } else if (GenerateMergedBaseProfiles) {
       ProfileMap[ChildProfile->getContext()].merge(*ChildProfile);
       auto &SamplesMap = NodeProfile->functionSamplesAt(ChildNode.CallSiteLoc);
       SamplesMap[ChildProfile->getName().str()].getContext().setAttribute(
           ContextDuplicatedIntoBase);
     }
 
     // Contexts coming with a `ContextShouldBeInlined` attribute indicate this
     // is a preinliner-computed profile.
     if (OrigChildContext.hasAttribute(ContextShouldBeInlined))
       FunctionSamples::ProfileIsCSNested = true;
 
     // Remove the original child profile.
     ProfileMap.erase(OrigChildContext);
   }
 }
 
-void CSProfileConverter::convertProfiles() { convertProfiles(RootFrame); }
+void CSProfileConverter::convertToCSNestedProfiles() {
+  for (auto &FuncSample : ProfileMap) {
+    FunctionSamples *FSamples = &FuncSample.second;
+    auto *NewNode = getOrCreateContextPath(FSamples->getContext());
+    assert(!NewNode->FuncSamples && "New node cannot have sample profile");
+    NewNode->FuncSamples = FSamples;
+  }
+  convertToCSFlatProfiles(RootFrame);
+}
+
+void CSProfileConverter::convertToCSFlatProfiles(FunctionSamples &FProfile,
+                                         SampleProfileMap &NewProfileMap,
+                                         SampleContextFrameVector &ParentContext) {
+  // Push current frame.
+  ParentContext.emplace_back(FProfile.getName(), LineLocation(0, 0));
+
+  // Recursively promote callee profiles to a standalone top-level profiles with
+  // a flattened context.
+  while (!FProfile.getCallsiteSamples().empty()) {
+    auto I = FProfile.getCallsiteSamples().begin();
+    ParentContext.back().Location = I->first;
+    for (auto &Callee : I->second) {
+      auto &CalleeProfile = Callee.second;
+      // Add body sample.
+      FProfile.addBodySamples(I->first.LineOffset, I->first.Discriminator,
+                              CalleeProfile.getEntrySamples());
+      // Add callsite sample.
+      FProfile.addCalledTargetSamples(
+          I->first.LineOffset, I->first.Discriminator, CalleeProfile.getName(),
+          CalleeProfile.getEntrySamples());
+      // Recursively convert callee profile.
+      convertToCSFlatProfiles(CalleeProfile, NewProfileMap, ParentContext);
+    }
+
+    // Remove callee profile
+    FProfile.getCallsiteSamples().erase(I);
+    ParentContext.back().Location = LineLocation(0, 0);
+  }
+
+  // Update total sample since callee samples are withdrawn.
+  FProfile.updateTotalSamples();
+
+  // Update head samples for callee profiles.
+  if (ParentContext.size() > 1)
+    FProfile.addHeadSamples(FProfile.getEntrySamples());
+
+  // Update current context.
+  Contexts->push_back(ParentContext);
+  SampleContext NewContext(Contexts->back());
+  FProfile.setContext(NewContext);
+  NewProfileMap.emplace(NewContext, FProfile);
+
+  // Pop current frame.
+  ParentContext.pop_back();
+}
+
+void CSProfileConverter::convertToCSFlatProfiles() {
+  SampleProfileMap NewProfileMap;
+  SampleContextFrameVector Context;
+  for (auto &FuncSample : ProfileMap)
+    convertToCSFlatProfiles(FuncSample.second, NewProfileMap, Context);
+  ProfileMap = std::move(NewProfileMap);
+}

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

+RUN: llvm-profdata merge --sample --text -output=%t.proftext %S/Inputs/sample-profile.proftext --gen-cs-flat-profile=1
+RUN: FileCheck %s < %t.proftext
+
+
+; CHECK:      [main]:10896:0
+; CHECK-NEXT:  4: 534
+; CHECK-NEXT:  4.2: 534
+; CHECK-NEXT:  5: 1075
+; CHECK-NEXT:  5.1: 1075
+; CHECK-NEXT:  6: 2080
+; CHECK-NEXT:  7: 534
+; CHECK-NEXT:  9: 2064 _Z3bari:1471 _Z3fooi:631
+; CHECK-NEXT:  10: 3000 inline2:2000 inline1:1000
+; CHECK-NEXT: [main:10 @ inline2]:2000:2000
+; CHECK-NEXT:  1: 2000
+; CHECK-NEXT: [_Z3bari]:1437:1437
+; CHECK-NEXT:  1: 1437
+; CHECK-NEXT: [main:10 @ inline1]:1000:1000
+; CHECK-NEXT:  1: 1000
+; CHECK-NEXT: [_Z3fooi]:610:610
+; CHECK-NEXT:  1: 610

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, bool GenCSNestedProfile, bool GenCSFlatProfile,
                    bool SampleMergeColdContext, bool SampleTrimColdContext,
                    bool SampleColdContextFrameDepth, FailureMode FailMode) {
   using namespace sampleprof;
   SampleProfileMap ProfileMap;
   SmallVector<std::unique_ptr<sampleprof::SampleProfileReader>, 5> Readers;
   LLVMContext Context;
   sampleprof::ProfileSymbolList WriterList;
   Optional<bool> ProfileIsProbeBased;
if (ProfileIsCSFlat && (SampleMergeColdContext || SampleTrimColdContext)) {
 
     // Trim and merge cold context profile using cold threshold above;
     SampleContextTrimmer(ProfileMap)
         .trimAndMergeColdContextProfiles(
             SampleProfColdThreshold, SampleTrimColdContext,
             SampleMergeColdContext, SampleColdContextFrameDepth, false);
   }
 
+
+  // Underlying context table serves for sample profile writer when
+  // converting a nested profile to a CS profile.
+  std::list<SampleContextFrameVector> Contexts;
+
   if (ProfileIsCSFlat && GenCSNestedProfile) {
     CSProfileConverter CSConverter(ProfileMap);
-    CSConverter.convertProfiles();
+    CSConverter.convertToCSNestedProfiles();
     ProfileIsCSFlat = FunctionSamples::ProfileIsCSFlat = false;
+  } else if (!ProfileIsCSFlat.getValue() && GenCSFlatProfile) {
+    CSProfileConverter CSConverter(ProfileMap, &Contexts);
+    CSConverter.convertToCSFlatProfiles();
+    ProfileIsCSFlat = FunctionSamples::ProfileIsCSFlat = true;
   }
 
   auto WriterOrErr =
       SampleProfileWriter::create(OutputFilename, FormatMap[OutputFormat]);
   if (std::error_code EC = WriterOrErr.getError())
     exitWithErrorCode(EC, OutputFilename);
 
   auto Writer = std::move(WriterOrErr.get());
cl::opt<unsigned> SupplMinSizeThreshold(
                "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<bool> GenCSFlatProfile(
+      "gen-cs-flat-profile", cl::init(false),
+      cl::desc("Generate a CS flat profile from a nested profile."));
   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::ParseCommandLineOptions(argc, argv, "LLVM profile data merger\n");
 
   WeightedFileVector WeightedInputs;
   for (StringRef Filename : InputFilenames)
     addWeightedInput(WeightedInputs, {std::string(Filename), 1});
   for (StringRef WeightedFilename : WeightedInputFilenames)
     addWeightedInput(WeightedInputs, parseWeightedFile(WeightedFilename));
 
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,
+                       UseMD5, GenPartialProfile, GenCSNestedProfile, GenCSFlatProfile,
                        SampleMergeColdContext, SampleTrimColdContext,
                        SampleColdContextFrameDepth, FailureMode);
   return 0;
 }
 
 /// Computer the overlap b/w profile BaseFilename and profile TestFilename.
 static void overlapInstrProfile(const std::string &BaseFilename,
                                 const std::string &TestFilename,

llvm/tools/llvm-profgen/ProfileGenerator.cpp

void CSProfileGenerator::postProcessProfiles() {
   sampleprof::SampleProfileMap ContextLessProfiles;
   for (const auto &I : ProfileMap) {
     ContextLessProfiles[I.second.getName()].merge(I.second);
   }
 
   calculateAndShowDensity(ContextLessProfiles);
   if (GenCSNestedProfile) {
     CSProfileConverter CSConverter(ProfileMap);
-    CSConverter.convertProfiles();
+    CSConverter.convertToCSNestedProfiles();
     FunctionSamples::ProfileIsCSFlat = false;
     FunctionSamples::ProfileIsCSNested = EnableCSPreInliner;
   }
 }
 
 void ProfileGeneratorBase::computeSummaryAndThreshold() {
   SampleProfileSummaryBuilder Builder(ProfileSummaryBuilder::DefaultCutoffs);
   auto Summary = Builder.computeSummaryForProfiles(ProfileMap);