[llvm-profdata] Handle internal linkage functions in profile supplementation

[xur]

Summary

This patch has the following changes:
(1) Handling of internal linkage functions (static functions)
Static functions in FDO have a prefix of source file name, while they do not
have one in SampleFDO. Current implementation does not handle this and we are
not updating the profile for static functions. This patch fixes this.

(2) Handling of -funique-internal-linakge-symbols
Again this is for the internal linkage functions. Option
-funique-internal-linakge-symbols can now be applied to both FDO and SampleFDO
compilation. When it is used, it demangles internal linkage function names and
adds a hash value as the postfix.

When both SampleFDO and FDO profiles use this option, or both
not use this option, changes in (1) should handle this.

Here we also handle when the SampleFDO profile using this option while FDO
profile not using this option, or vice versa.

There is one case where this patch won't work: If one of the profiles used
mangled name and the other does not. For example, if the SampleFDO profile
uses clang c-compiler and without -funique-internal-linakge-symbols, while
the FDO profile uses -funique-internal-linakge-symbols. The SampleFDO profile
contains unmangled names while the FDO profile contains mangled names. If
both profiles use c++ compiler, this won't happen. We think this use case
is rare and does not justify the effort to fix.

[davidxl]

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

612

define a macro for the marker string.

663

Skip to the next (using continue) when FS is not interesting (cold etc)

674

continue when Itr == end or when Itr is not cold

[xur]

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

612

Will do.

663

OK.

674

Will change.

[xur]

Integrated David's review commends.

[davidxl]

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

566

no need for & for StringRef

[xur]

Fixed unneeded &

[davidxl]

lgtm

[tmsriram]

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

591

Maybe rewrite this slightly as:

// If Sample Profile and Instrumented Profile do not agree on symbol uniqification.
if (SampleProfileHasFunique != ProfileHasFUnique) {

if (ProfileHasFUnique) {
   // trim
} else {
   // Build Map
}

}

[xur]

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

591

Good point. I will change to this form.

[xur]

Integrated Sriraman's suggestion.

clang/lib/CodeGen/CodeGenModule.cpp

 #include "llvm/Frontend/OpenMP/OMPIRBuilder.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ProfileSummary.h"
 #include "llvm/ProfileData/InstrProfReader.h"
+#include "llvm/ProfileData/SampleProf.h"
 #include "llvm/Support/CRC.h"
 #include "llvm/Support/CodeGen.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ConvertUTF.h"
 #include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/MD5.h"
 #include "llvm/Support/TimeProfiler.h"
 #include "llvm/Support/X86TargetParser.h"
 #include "llvm/Support/xxhash.h"
 
 using namespace clang;
 using namespace CodeGen;
 
 static llvm::cl::opt<bool> LimitedCoverage(
if (CodeGenOpts.UniqueInternalLinkageNames &&
       !getModule().getSourceFileName().empty()) {
     std::string Path = getModule().getSourceFileName();
     // Check if a path substitution is needed from the MacroPrefixMap.
     for (const auto &Entry : LangOpts.MacroPrefixMap)
       if (Path.rfind(Entry.first, 0) != std::string::npos) {
         Path = Entry.second + Path.substr(Entry.first.size());
         break;
       }
-    llvm::MD5 Md5;
-    Md5.update(Path);
-    llvm::MD5::MD5Result R;
-    Md5.final(R);
-    SmallString<32> Str;
-    llvm::MD5::stringifyResult(R, Str);
-    // Convert MD5hash to Decimal. Demangler suffixes can either contain
-    // numbers or characters but not both.
-    llvm::APInt IntHash(128, Str.str(), 16);
-    // Prepend "__uniq" before the hash for tools like profilers to understand
-    // that this symbol is of internal linkage type.  The "__uniq" is the
-    // pre-determined prefix that is used to tell tools that this symbol was
-    // created with -funique-internal-linakge-symbols and the tools can strip or
-    // keep the prefix as needed.
-    ModuleNameHash = (Twine(".__uniq.") +
-        Twine(toString(IntHash, /* Radix = */ 10, /* Signed = */false))).str();
+    ModuleNameHash = llvm::getUniqueInternalLinkagePostfix(Path);
   }
 }
 
 CodeGenModule::~CodeGenModule() {}
 
 void CodeGenModule::createObjCRuntime() {
   // This is just isGNUFamily(), but we want to force implementors of
   // new ABIs to decide how best to do this.

llvm/include/llvm/ProfileData/SampleProf.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_PROFILEDATA_SAMPLEPROF_H
 #define LLVM_PROFILEDATA_SAMPLEPROF_H
 
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MathExtras.h"
template <> struct DenseMapInfo<SampleContext> {
   static unsigned getHashValue(const SampleContext &Val) {
     return Val.getHashCode();
   }
 
   static bool isEqual(const SampleContext &LHS, const SampleContext &RHS) {
     return LHS == RHS;
   }
 };
+
+// Prepend "__uniq" before the hash for tools like profilers to understand
+// that this symbol is of internal linkage type.  The "__uniq" is the
+// pre-determined prefix that is used to tell tools that this symbol was
+// created with -funique-internal-linakge-symbols and the tools can strip or
+// keep the prefix as needed.
+inline std::string getUniqueInternalLinkagePostfix(const StringRef &FName) {
+  llvm::MD5 Md5;
+  Md5.update(FName);
+  llvm::MD5::MD5Result R;
+  Md5.final(R);
+  SmallString<32> Str;
+  llvm::MD5::stringifyResult(R, Str);
+  // Convert MD5hash to Decimal. Demangler suffixes can either contain
+  // numbers or characters but not both.
+  llvm::APInt IntHash(128, Str.str(), 16);
+  return toString(IntHash, /* Radix = */ 10, /* Signed = */ false)
+      .insert(0, FunctionSamples::UniqSuffix);
+};
+
 } // end namespace llvm
 
 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H

llvm/test/tools/llvm-profdata/Inputs/FUnique.afdotext

+_ZL3foom.__uniq.276699478366846449772231447066107882794:14064855:0
+ 0: 0
+ 2.1: 0
+ 2.2: 290944
+ 2.3073: 290944
+ 3: 290944
+ 4: 256 bar:256
+ 5: 304048 bar:307919
+ 7: 0
+_Z3barmi:6447198:308175
+ 1: 302866
+ 2: 5551
+ 3: 296598
+ 3.13824: 5551
+ 3.2952803840: 296598
+ 4: 5551
+ 4.4160749568: 296598

llvm/test/tools/llvm-profdata/Inputs/FUnique.proftext

+# IR level Instrumentation Flag
+:ir
+_Z3barmi
+# Func Hash:
+784007056844089447
+# Num Counters:
+2
+# Counter Values:
+0
+0
+
+main
+# Func Hash:
+784007059655560962
+# Num Counters:
+2
+# Counter Values:
+1
+0
+
+test.c:_ZL3foom.__uniq.276699478366846449772231447066107882794
+# Func Hash:
+1124680652115249575
+# Num Counters:
+3
+# Counter Values:
+0
+0
+0
+

llvm/test/tools/llvm-profdata/Inputs/NoFUnique.afdotext

+_ZL3foom:14064855:0
+ 0: 0
+ 2.1: 0
+ 2.2: 290944
+ 2.3073: 290944
+ 3: 290944
+ 4: 256 bar:256
+ 5: 304048 bar:307919
+ 7: 0
+_Z3barmi:6447198:308175
+ 1: 302866
+ 2: 5551
+ 3: 296598
+ 3.13824: 5551
+ 3.2952803840: 296598
+ 4: 5551
+ 4.4160749568: 296598

llvm/test/tools/llvm-profdata/Inputs/NoFUnique.proftext

+# IR level Instrumentation Flag
+:ir
+_Z3barmi
+# Func Hash:
+784007056844089447
+# Num Counters:
+2
+# Counter Values:
+0
+0
+
+main
+# Func Hash:
+784007059655560962
+# Num Counters:
+2
+# Counter Values:
+1
+0
+
+test.c:_ZL3foom
+# Func Hash:
+1124680652115249575
+# Num Counters:
+3
+# Counter Values:
+0
+0
+0
+

llvm/test/tools/llvm-profdata/suppl-instr-with-sample-static-func.test

+Some basic tests for supplementing instrumentation profile with sample profile for static funcs.
+
+RUN: llvm-profdata merge -supplement-instr-with-sample=%p/Inputs/NoFUnique.afdotext -suppl-min-size-threshold=2 %p/Inputs/NoFUnique.proftext -o %t1
+RUN: llvm-profdata show -function=foo -counts %t1 | FileCheck %s
+
+RUN: llvm-profdata merge -supplement-instr-with-sample=%p/Inputs/FUnique.afdotext -suppl-min-size-threshold=2 %p/Inputs/FUnique.proftext -o %t2
+RUN: llvm-profdata show -function=foo -counts %t2 | FileCheck %s
+
+RUN: llvm-profdata merge -supplement-instr-with-sample=%p/Inputs/NoFUnique.afdotext -suppl-min-size-threshold=2 %p/Inputs/FUnique.proftext -o %t3
+RUN: llvm-profdata show -function=foo -counts %t3 | FileCheck %s
+
+RUN: llvm-profdata merge -supplement-instr-with-sample=%p/Inputs/FUnique.afdotext -suppl-min-size-threshold=2 %p/Inputs/NoFUnique.proftext -o %t4
+RUN: llvm-profdata show -function=foo -counts %t4 | FileCheck %s
+
+CHECK: Block counts: [18446744073709551615, 18446744073709551615, 18446744073709551615]

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

 #include "llvm/ProfileData/SampleProfWriter.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Discriminator.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/FormattedStream.h"
 #include "llvm/Support/InitLLVM.h"
+#include "llvm/Support/MD5.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/ThreadPool.h"
 #include "llvm/Support/Threading.h"
 #include "llvm/Support/WithColor.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <queue>
 
 using namespace llvm;
 
+// We use this string to indicate that there are
+// multiple static functions map to the same name.
+const std::string DuplicateNameStr = "----";
+
 enum ProfileFormat {
   PF_None = 0,
   PF_Text,
   PF_Compact_Binary,
   PF_Ext_Binary,
   PF_GCC,
   PF_Binary
 };
InstrProfileEntry::InstrProfileEntry(InstrProfRecord *Record) {
   for (size_t I = 0; I < CntNum; ++I) {
     MaxCount = std::max(MaxCount, Record->Counts[I]);
     ZeroCntNum += !Record->Counts[I];
   }
   ZeroCounterRatio = (float)ZeroCntNum / CntNum;
   NumEdgeCounters = CntNum;
 }
 
-/// Either set all the counters in the instr profile entry \p IFE to -1
+// Either set all the counters in the instr profile entry \p IFE to -1
 /// in order to drop the profile or scale up the counters in \p IFP to
 /// be above hot threshold. We use the ratio of zero counters in the
 /// profile of a function to decide the profile is helpful or harmful
 /// for performance, and to choose whether to scale up or drop it.
 static void updateInstrProfileEntry(InstrProfileEntry &IFE,
                                     uint64_t HotInstrThreshold,
                                     float ZeroCounterThreshold) {
   InstrProfRecord *ProfRecord = IFE.ProfRecord;

 /// \p Reader.
 static void
 adjustInstrProfile(std::unique_ptr<WriterContext> &WC,
                    std::unique_ptr<sampleprof::SampleProfileReader> &Reader,
                    unsigned SupplMinSizeThreshold, float ZeroCounterThreshold,
                    unsigned InstrProfColdThreshold) {
   // Function to its entry in instr profile.
   StringMap<InstrProfileEntry> InstrProfileMap;
+  StringMap<StringRef> StaticFuncMap;
   InstrProfSummaryBuilder IPBuilder(ProfileSummaryBuilder::DefaultCutoffs);
+
+  auto checkSampleProfileHasFUnique = [&Reader]() {
+    for (const auto &PD : Reader->getProfiles()) {
+      auto &FContext = PD.first;
+      if (FContext.toString().find(FunctionSamples::UniqSuffix) !=
+          std::string::npos) {
+        return true;
+      }
+    }
+    return false;
+  };
+
+  bool SampleProfileHasFUnique = checkSampleProfileHasFUnique();
+
+  auto buildStaticFuncMap = [&StaticFuncMap,
+                             SampleProfileHasFUnique](const StringRef Name) {
+    std::string Prefixes[] = {".cpp:", "cc:", ".c:", ".hpp:", ".h:"};
+    size_t PrefixPos = StringRef::npos;
+    for (auto &Prefix : Prefixes) {
+      PrefixPos = Name.find_insensitive(Prefix);
+      if (PrefixPos == StringRef::npos)
+        continue;
+      PrefixPos += Prefix.size();
+      break;
+    }
+
+    if (PrefixPos == StringRef::npos) {
+      return;
+    }
+
+    StringRef NewName = Name.drop_front(PrefixPos);
+    StringRef FName = Name.substr(0, PrefixPos - 1);
+    if (NewName.size() == 0) {
+      return;
+    }
+
+    // This name should have a static linkage.
+    size_t PostfixPos = NewName.find(FunctionSamples::UniqSuffix);
+    bool ProfileHasFUnique = (PostfixPos != StringRef::npos);
+
+    // If sample profile and instrumented profile do not agree on symbol
+    // uniqification.
+    if (SampleProfileHasFUnique != ProfileHasFUnique) {
+      // If instrumented profile uses -funique-internal-linakge-symbols,
+      // we need to trim the name.
+      if (ProfileHasFUnique) {
+        NewName = NewName.substr(0, PostfixPos);
+      } else {
+        // If sample profile uses -funique-internal-linakge-symbols,
+        // we build the map.
+        std::string NStr =
+            NewName.str() + getUniqueInternalLinkagePostfix(FName);
+        NewName = StringRef(NStr);
+        StaticFuncMap[NewName] = Name;
+        return;
+      }
+    }
+
+    if (StaticFuncMap.find(NewName) == StaticFuncMap.end()) {
+      StaticFuncMap[NewName] = Name;
+    } else {
+      StaticFuncMap[NewName] = DuplicateNameStr;
+    }
+  };
+
   for (auto &PD : WC->Writer.getProfileData()) {
     // Populate IPBuilder.
     for (const auto &PDV : PD.getValue()) {
       InstrProfRecord Record = PDV.second;
       IPBuilder.addRecord(Record);
     }
 
     // If a function has multiple entries in instr profile, skip it.
     if (PD.getValue().size() != 1)
       continue;
 
     // Initialize InstrProfileMap.
     InstrProfRecord *R = &PD.getValue().begin()->second;
-    InstrProfileMap[PD.getKey()] = InstrProfileEntry(R);
+    StringRef FullName = PD.getKey();
+    InstrProfileMap[FullName] = InstrProfileEntry(R);
+    buildStaticFuncMap(FullName);
   }
 
   ProfileSummary InstrPS = *IPBuilder.getSummary();
   ProfileSummary SamplePS = Reader->getSummary();
 
   // Compute cold thresholds for instr profile and sample profile.
   uint64_t ColdSampleThreshold =
       ProfileSummaryBuilder::getEntryForPercentile(
uint64_t ColdInstrThreshold =
           : ProfileSummaryBuilder::getEntryForPercentile(
                 InstrPS.getDetailedSummary(),
                 ProfileSummaryBuilder::DefaultCutoffs[ColdPercentileIdx])
                 .MinCount;
 
   // Find hot/warm functions in sample profile which is cold in instr profile
   // and adjust the profiles of those functions in the instr profile.
   for (const auto &PD : Reader->getProfiles()) {
-    auto &FContext = PD.first;
     const sampleprof::FunctionSamples &FS = PD.second;
+    if (FS.getMaxCountInside() <= ColdSampleThreshold)
+      continue;
+    auto &FContext = PD.first;
     auto It = InstrProfileMap.find(FContext.toString());
-    if (FS.getMaxCountInside() > ColdSampleThreshold &&
-        It != InstrProfileMap.end() &&
-        It->second.MaxCount <= ColdInstrThreshold &&
-        It->second.NumEdgeCounters >= SupplMinSizeThreshold) {
-      updateInstrProfileEntry(It->second, HotInstrThreshold,
-                              ZeroCounterThreshold);
-    }
-  }
-}
+    if (It == InstrProfileMap.end()) {
+      auto NewName = StaticFuncMap.find(FContext.toString());
+      if (NewName != StaticFuncMap.end()) {
+        It = InstrProfileMap.find(NewName->second.str());
+        if (NewName->second == DuplicateNameStr) {
+          WithColor::warning()
+              << "Static function " << FContext.toString()
+              << " has multiple promoted names, cannot adjust profile.\n";
+        }
+      }
+    }
+    if (It == InstrProfileMap.end() ||
+        It->second.MaxCount > ColdInstrThreshold ||
+        It->second.NumEdgeCounters < SupplMinSizeThreshold)
+      continue;
 
 /// The main function to supplement instr profile with sample profile.
 /// \Inputs contains the instr profile. \p SampleFilename specifies the
 /// sample profile. \p OutputFilename specifies the output profile name.
 /// \p OutputFormat specifies the output profile format. \p OutputSparse
 /// specifies whether to generate sparse profile. \p SupplMinSizeThreshold
 /// specifies the minimal size for the functions whose profile will be
 /// adjusted. \p ZeroCounterThreshold is the threshold to check whether