[SampleFDO] Make sample profile loader unaware of compact format change

[wmi]

Summary

The patch tries to make sample profile loader independent of profile format change. It moves compact format related code into FunctionSamples and SampleProfileReader classes, and sample profile loader only have to interact with those two classes and will be unaware of profile format changes.

The cleanup also contain some fixes to further remove the difference between compactbinary format and binary format. After the cleanup using different formats originated from the same profile will generate exactly the same binaries, which we verified by compiling two large server benchmarks w/wo thinlto.

[davidxl]

include/llvm/ProfileData/SampleProf.h

461 ↗

(On Diff #163853)

Add comments on this code about the substr mapping.

test/Transforms/SampleProfile/Inputs/function_metadata.prof

1 ↗

(On Diff #163853)

why changing the profile data?

[wmi]

include/llvm/ProfileData/SampleProf.h

461 ↗

(On Diff #163853)

Ok, will do.

test/Transforms/SampleProfile/Inputs/function_metadata.prof

1 ↗

(On Diff #163853)

Because in function_metadata.prof, the total sample count of a function doesn't equal to the added up count of all the samples in the function body. SampleProfileReader will not care about the inconsistency and will use the incorrect total sample count directly.

However, the autofdo dumping and other conversion tool will discard the incorrect total count and recompute it according to the added up count of samples inside function body.

The test was to verify different formats converted from the same profile will generate the same results, so I needed to make the total sample count consistent with how it is computed.

[wmi]

Add comment for substr mapping.

[davidxl]

include/llvm/ProfileData/SampleProf.h

464 ↗

(On Diff #164073)

why are those suffixes stripped in sample profile?

[wmi]

include/llvm/ProfileData/SampleProf.h

464 ↗

(On Diff #164073)

It is possible that the binary sampled is built in thinlto mode and some functions are promoted. The profile generated from such binary will contain names after promotion. If such profile is used in thinlto pre-link-phase or nonthinlto build, we need to strip those names from sample before we can find a match in the module.

Indeed if there are multiple local functions with the same name are promoted, their samples will be merged together after the strip, which will introduce some imprecision. Maybe this part can be improved -- don't strip names from sample, but always promote the local names in the module before trying to match it with the name from sample. I am not sure whether the effort is worthy. Dehao may already evaluate it before?

[danielcdh]

include/llvm/ProfileData/SampleProf.h

464 ↗

(On Diff #164073)

I remember that name stripping is important as there are many different types of suffixes added to the function name which makes it impossible to match. But I do not remember the exact impact. It may be worth re-evaluate.

For the local functions, what's the promoted name look like after thinlto? If it's deterministic, then we should not strip it.

[davidxl]

include/llvm/ProfileData/SampleProf.h

464 ↗

(On Diff #164073)

How are local functions handled without thinlto for samplePGO? Instrumentatation PGO always qualify the name with module name.

[danielcdh]

include/llvm/ProfileData/SampleProf.h

464 ↗

(On Diff #164073)

They'll just share the function name have all the profiles merged, which I agree is bad, but I don't think we have a way to identify which module this function is coming from.

[davidxl]

include/llvm/ProfileData/SampleProf.h

464 ↗

(On Diff #164073)

Since this issue is not something new, we can defer this later.

[davidxl]

lgtm

llvm/trunk/include/llvm/ProfileData/SampleProf.h

public:
   }
 
   /// Returns a pointer to FunctionSamples at the given callsite location \p Loc
   /// with callee \p CalleeName. If no callsite can be found, relax the
   /// restriction to return the FunctionSamples at callsite location \p Loc
   /// with the maximum total sample count.
   const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc,
                                                StringRef CalleeName) const {
+    std::string CalleeGUID;
+    CalleeName = getRepInFormat(CalleeName, Format, CalleeGUID);
+
     auto iter = CallsiteSamples.find(Loc);
     if (iter == CallsiteSamples.end())
       return nullptr;
     auto FS = iter->second.find(CalleeName);
     if (FS != iter->second.end())
       return &FS->second;
     // If we cannot find exact match of the callee name, return the FS with
     // the max total count.
sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
     return Result;
   }
 
   /// Recursively traverses all children, if the total sample count of the
   /// corresponding function is no less than \p Threshold, add its corresponding
   /// GUID to \p S. Also traverse the BodySamples to add hot CallTarget's GUID
   /// to \p S.
   void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
-                            uint64_t Threshold, bool isCompact) const {
+                            uint64_t Threshold) const {
     if (TotalSamples <= Threshold)
       return;
-    S.insert(Function::getGUID(Name));
+    S.insert(getGUID(Name));
     // Import hot CallTargets, which may not be available in IR because full
     // profile annotation cannot be done until backend compilation in ThinLTO.
     for (const auto &BS : BodySamples)
       for (const auto &TS : BS.second.getCallTargets())
         if (TS.getValue() > Threshold) {
-          Function *Callee = M->getFunction(TS.getKey());
+          const Function *Callee =
+              M->getFunction(getNameInModule(TS.getKey(), M));
           if (!Callee || !Callee->getSubprogram())
-            S.insert(isCompact ? std::stol(TS.getKey().data())
-                               : Function::getGUID(TS.getKey()));
+            S.insert(getGUID(TS.getKey()));
         }
     for (const auto &CS : CallsiteSamples)
       for (const auto &NameFS : CS.second)
-        NameFS.second.findInlinedFunctions(S, M, Threshold, isCompact);
+        NameFS.second.findInlinedFunctions(S, M, Threshold);
   }
 
   /// Set the name of the function.
   void setName(StringRef FunctionName) { Name = FunctionName; }
 
   /// Return the function name.
   const StringRef &getName() const { return Name; }
 
+  /// Return the original function name if it exists in Module \p M.
+  StringRef getFuncNameInModule(const Module *M) const {
+    return getNameInModule(Name, M);
+  }
+
+  /// Translate \p Name into its original name in Module.
+  /// When the Format is not SPF_Compact_Binary, \p Name needs no translation.
+  /// When the Format is SPF_Compact_Binary, \p Name in current FunctionSamples
+  /// is actually GUID of the original function name. getNameInModule will
+  /// translate \p Name in current FunctionSamples into its original name.
+  /// If the original name doesn't exist in \p M, return empty StringRef.
+  StringRef getNameInModule(StringRef Name, const Module *M) const {
+    if (Format != SPF_Compact_Binary)
+      return Name;
+    // Expect CurrentModule to be initialized by GUIDToFuncNameMapper.
+    if (M != CurrentModule)
+      llvm_unreachable("Input Module should be the same as CurrentModule");
+    auto iter = GUIDToFuncNameMap.find(std::stoul(Name.data()));
+    if (iter == GUIDToFuncNameMap.end())
+      return StringRef();
+    return iter->second;
+  }
+
   /// Returns the line offset to the start line of the subprogram.
   /// We assume that a single function will not exceed 65535 LOC.
   static unsigned getOffset(const DILocation *DIL);
 
   /// Get the FunctionSamples of the inline instance where DIL originates
   /// from.
   ///
   /// The FunctionSamples of the instruction (Machine or IR) associated to
   /// \p DIL is the inlined instance in which that instruction is coming from.
   /// We traverse the inline stack of that instruction, and match it with the
   /// tree nodes in the profile.
   ///
   /// \returns the FunctionSamples pointer to the inlined instance.
   const FunctionSamples *findFunctionSamples(const DILocation *DIL) const;
 
+  static SampleProfileFormat Format;
+  /// GUIDToFuncNameMap saves the mapping from GUID to the symbol name, for
+  /// all the function symbols defined or declared in CurrentModule.
+  static DenseMap<uint64_t, StringRef> GUIDToFuncNameMap;
+  static Module *CurrentModule;
+
+  class GUIDToFuncNameMapper {
+  public:
+    GUIDToFuncNameMapper(Module &M) {
+      if (Format != SPF_Compact_Binary)
+        return;
+
+      for (const auto &F : M) {
+        StringRef OrigName = F.getName();
+        GUIDToFuncNameMap.insert({Function::getGUID(OrigName), OrigName});
+        /// Local to global var promotion used by optimization like thinlto
+        /// will rename the var and add suffix like ".llvm.xxx" to the
+        /// original local name. In sample profile, the suffixes of function
+        /// names are all stripped. Since it is possible that the mapper is
+        /// built in post-thin-link phase and var promotion has been done,
+        /// we need to add the substring of function name without the suffix
+        /// into the GUIDToFuncNameMap.
+        auto pos = OrigName.find('.');
+        if (pos != StringRef::npos) {
+          StringRef NewName = OrigName.substr(0, pos);
+          GUIDToFuncNameMap.insert({Function::getGUID(NewName), NewName});
+        }
+      }
+      CurrentModule = &M;
+    }
+
+    ~GUIDToFuncNameMapper() {
+      if (Format != SPF_Compact_Binary)
+        return;
+
+      GUIDToFuncNameMap.clear();
+      CurrentModule = nullptr;
+    }
+  };
+
+  // Assume the input \p Name is a name coming from FunctionSamples itself.
+  // If the format is SPF_Compact_Binary, the name is already a GUID and we
+  // don't want to return the GUID of GUID.
+  static uint64_t getGUID(const StringRef &Name) {
+    return (Format == SPF_Compact_Binary) ? std::stoul(Name.data())
+                                          : Function::getGUID(Name);
+  }
+
 private:
   /// Mangled name of the function.
   StringRef Name;
 
   /// Total number of samples collected inside this function.
   ///
   /// Samples are cumulative, they include all the samples collected
   /// inside this function and all its inlined callees.

llvm/trunk/lib/ProfileData/SampleProf.cpp

 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/raw_ostream.h"
 #include <string>
 #include <system_error>
 
 using namespace llvm;
 using namespace sampleprof;
 
+namespace llvm {
+namespace sampleprof {
+SampleProfileFormat FunctionSamples::Format;
+DenseMap<uint64_t, StringRef> FunctionSamples::GUIDToFuncNameMap;
+Module *FunctionSamples::CurrentModule;
+} // namespace sampleprof
+} // namespace llvm
+
 namespace {
 
 // FIXME: This class is only here to support the transition to llvm::Error. It
 // will be removed once this transition is complete. Clients should prefer to
 // deal with the Error value directly, rather than converting to error_code.
 class SampleProfErrorCategoryType : public std::error_category {
   const char *name() const noexcept override { return "llvm.sampleprof"; }
 

llvm/trunk/lib/ProfileData/SampleProfReader.cpp

else if (SampleProfileReaderCompactBinary::hasFormat(*B))
     Reader.reset(new SampleProfileReaderCompactBinary(std::move(B), C));
   else if (SampleProfileReaderGCC::hasFormat(*B))
     Reader.reset(new SampleProfileReaderGCC(std::move(B), C));
   else if (SampleProfileReaderText::hasFormat(*B))
     Reader.reset(new SampleProfileReaderText(std::move(B), C));
   else
     return sampleprof_error::unrecognized_format;
 
+  FunctionSamples::Format = Reader->getFormat();
   if (std::error_code EC = Reader->readHeader())
     return EC;
 
   return std::move(Reader);
 }
 
 // For text and GCC file formats, we compute the summary after reading the
 // profile. Binary format has the profile summary in its header.
 void SampleProfileReader::computeSummary() {
   SampleProfileSummaryBuilder Builder(ProfileSummaryBuilder::DefaultCutoffs);
   for (const auto &I : Profiles) {
     const FunctionSamples &Profile = I.second;
     Builder.addRecord(Profile);
   }
   Summary = Builder.getSummary();
 }

llvm/trunk/lib/Transforms/IPO/SampleProfile.cpp

SampleProfileLoader::findCalleeFunctionSamples(const Instruction &Inst) const {
   if (const CallInst *CI = dyn_cast<CallInst>(&Inst))
     if (Function *Callee = CI->getCalledFunction())
       CalleeName = Callee->getName();
 
   const FunctionSamples *FS = findFunctionSamples(Inst);
   if (FS == nullptr)
     return nullptr;
 
-  std::string CalleeGUID;
-  CalleeName = getRepInFormat(CalleeName, Reader->getFormat(), CalleeGUID);
   return FS->findFunctionSamplesAt(LineLocation(FunctionSamples::getOffset(DIL),
                                                 DIL->getBaseDiscriminator()),
                                    CalleeName);
 }
 
 /// Returns a vector of FunctionSamples that are the indirect call targets
 /// of \p Inst. The vector is sorted by the total number of samples. Stores
 /// the total call count of the indirect call in \p Sum.
if (const FunctionSamplesMap *M = FS->findFunctionSamplesMapAt(LineLocation(
     if (M->empty())
       return R;
     for (const auto &NameFS : *M) {
       Sum += NameFS.second.getEntrySamples();
       R.push_back(&NameFS.second);
     }
     llvm::sort(R.begin(), R.end(),
                [](const FunctionSamples *L, const FunctionSamples *R) {
+                 if (L->getEntrySamples() != R->getEntrySamples())
                    return L->getEntrySamples() > R->getEntrySamples();
+                 return FunctionSamples::getGUID(L->getName()) <
+                        FunctionSamples::getGUID(R->getName());
                });
   }
   return R;
 }
 
 /// Get the FunctionSamples for an instruction.
 ///
 /// The FunctionSamples of an instruction \p Inst is the inlined instance

 /// \param InlinedGUIDs a set to be updated to include all GUIDs that are
 ///     inlined in the profiled binary.
 ///
 /// \returns True if there is any inline happened.
 bool SampleProfileLoader::inlineHotFunctions(
     Function &F, DenseSet<GlobalValue::GUID> &InlinedGUIDs) {
   DenseSet<Instruction *> PromotedInsns;
   bool Changed = false;
-  bool isCompact = (Reader->getFormat() == SPF_Compact_Binary);
   while (true) {
     bool LocalChanged = false;
     SmallVector<Instruction *, 10> CIS;
     for (auto &BB : F) {
       bool Hot = false;
       SmallVector<Instruction *, 10> Candidates;
       for (auto &I : BB.getInstList()) {
         const FunctionSamples *FS = nullptr;
for (auto I : CIS) {
         continue;
       if (CallSite(I).isIndirectCall()) {
         if (PromotedInsns.count(I))
           continue;
         uint64_t Sum;
         for (const auto *FS : findIndirectCallFunctionSamples(*I, Sum)) {
           if (IsThinLTOPreLink) {
             FS->findInlinedFunctions(InlinedGUIDs, F.getParent(),
-                                     PSI->getOrCompHotCountThreshold(),
-                                     isCompact);
+                                     PSI->getOrCompHotCountThreshold());
             continue;
           }
-          auto CalleeFunctionName = FS->getName();
+          auto CalleeFunctionName = FS->getFuncNameInModule(F.getParent());
           // If it is a recursive call, we do not inline it as it could bloat
           // the code exponentially. There is way to better handle this, e.g.
           // clone the caller first, and inline the cloned caller if it is
           // recursive. As llvm does not inline recursive calls, we will
           // simply ignore it instead of handling it explicitly.
-          std::string FGUID;
-          auto Fname = getRepInFormat(F.getName(), Reader->getFormat(), FGUID);
-          if (CalleeFunctionName == Fname)
+          if (CalleeFunctionName == F.getName())
             continue;
 
           const char *Reason = "Callee function not available";
           auto R = SymbolMap.find(CalleeFunctionName);
           if (R != SymbolMap.end() && R->getValue() &&
               !R->getValue()->isDeclaration() &&
               R->getValue()->getSubprogram() &&
               isLegalToPromote(CallSite(I), R->getValue(), &Reason)) {
for (auto I : CIS) {
           }
         }
       } else if (CalledFunction && CalledFunction->getSubprogram() &&
                  !CalledFunction->isDeclaration()) {
         if (inlineCallInstruction(I))
           LocalChanged = true;
       } else if (IsThinLTOPreLink) {
         findCalleeFunctionSamples(*I)->findInlinedFunctions(
-            InlinedGUIDs, F.getParent(), PSI->getOrCompHotCountThreshold(),
-            isCompact);
+            InlinedGUIDs, F.getParent(), PSI->getOrCompHotCountThreshold());
       }
     }
     if (LocalChanged) {
       Changed = true;
     } else {
       break;
     }
   }
void SampleProfileLoader::buildEdges(Function &F) {
   }
 }
 
 /// Returns the sorted CallTargetMap \p M by count in descending order.
 static SmallVector<InstrProfValueData, 2> SortCallTargets(
     const SampleRecord::CallTargetMap &M) {
   SmallVector<InstrProfValueData, 2> R;
   for (auto I = M.begin(); I != M.end(); ++I)
-    R.push_back({Function::getGUID(I->getKey()), I->getValue()});
+    R.push_back({FunctionSamples::getGUID(I->getKey()), I->getValue()});
   llvm::sort(R.begin(), R.end(),
              [](const InstrProfValueData &L, const InstrProfValueData &R) {
                if (L.Count == R.Count)
                  return L.Value > R.Value;
                else
                  return L.Count > R.Count;
              });
   return R;

 }
 
 ModulePass *llvm::createSampleProfileLoaderPass(StringRef Name) {
   return new SampleProfileLoaderLegacyPass(Name);
 }
 
 bool SampleProfileLoader::runOnModule(Module &M, ModuleAnalysisManager *AM,
                                       ProfileSummaryInfo *_PSI) {
+  FunctionSamples::GUIDToFuncNameMapper Mapper(M);
   if (!ProfileIsValid)
     return false;
 
   PSI = _PSI;
   if (M.getProfileSummary() == nullptr)
     M.setProfileSummary(Reader->getSummary().getMD(M.getContext()));
 
   // Compute the total number of samples collected in this profile.

llvm/trunk/test/Transforms/SampleProfile/Inputs/function_metadata.prof

-test:10000:0
+test:3200:0
+ 1: 100
  2: 100
- 3: 100
  3: foo:1000
+  1: 800
   3: bar:200
+   2: 190
    4: baz:10
+    2: 10
  4: foo1:1000
   1: 1000
  4: foo2:1000
   1: 1000 foo3:1000
-test_liveness:10000:0
+test_liveness:1000:0
  1: foo:1000
   1: foo_available:1000
+   2: 1000

llvm/trunk/test/Transforms/SampleProfile/function_metadata.ll

 ; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=new-pm-pgo-sample-use-pipeline -profile-file=%S/Inputs/function_metadata.prof -S | FileCheck %s
+; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=new-pm-pgo-sample-use-pipeline -profile-file=%S/Inputs/function_metadata.compact.afdo -S | FileCheck %s
 
 ; Tests whether the functions in the inline stack are added to the
 ; function_entry_count metadata.
 
 declare void @foo()
 
 define void @foo_available() !dbg !11 {
   ret void

llvm/trunk/test/Transforms/SampleProfile/indirect-call.ll

 ; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/indirect-call.prof -S | FileCheck %s
+; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/indirect-call.compact.afdo -S | FileCheck %s
 
 ; CHECK-LABEL: @test
 define void @test(void ()*) !dbg !3 {
   %2 = alloca void ()*
   store void ()* %0, void ()** %2
   %3 = load void ()*, void ()** %2
   ; CHECK: call {{.*}}, !prof ![[PROF:[0-9]+]]
   call void %3(), !dbg !4