[BOLT][NFC] Speedup YAML profile processing

[Amir]

Summary

Reduce YAML profile processing times:

• preprocessProfile: speed up buildNameMaps by replacing ProfileNameToProfile mapping with ProfileFunctionNames set and ProfileBFs vector. Pre-look up YamlBF->BF correspondence, memoize in ProfileBFs.
• readProfile: replace iteration over all functions in the binary by iteration over profile functions (strict match and LTO name match).

On a large binary (1.9M functions) and large YAML profile (121MB, 30k functions)
reduces profile steps runtime:
pre-process profile data: 12.4953s -> 10.7123s
process profile data: 9.8195s -> 5.6639s

Compared to fdata profile reading:
pre-process profile data: 8.0268s
process profile data: 1.0265s
process profile data pre-CFG: 0.1644s

[maksfb]

Nice - good improvement. Do you know where the majority of the profile-processing time is spent with this change?

bolt/include/bolt/Profile/YAMLProfileReader.h

84

Is the change to always return true necessary?

bolt/lib/Profile/YAMLProfileReader.cpp

52

This should always return non-null value.

[Amir]

Address comments

[Amir]

bolt/include/bolt/Profile/YAMLProfileReader.h

84

Not really, just to avoid curly braces in matchProfile lambda. Reverted this change back to returning void and added curly braces down below.

[Amir]

In D159460#4643578, @maksfb wrote:

Nice - good improvement. Do you know where the majority of the profile-processing time is spent with this change?

Here's what perf report shows when narrowed down to YAMLProfileReader class:

Samples: 49M of event 'cycles', Event count (approx.): 19618

-  100.00%              llvm-bolt
   -  100.00%              llvm-bolt
      -   49.06%              [.] llvm::bolt::YAMLProfileReader::mayHaveProfileData
         +   18.37%              [.] llvm::StringMapImpl::FindKey
         +   15.31%              [.] llvm::bolt::YAMLProfileReader::mayHaveProfileDat
         +    6.72%              [.] llvm::bolt::BinaryFunction::forEachName<llvm::bo
         +    3.94%              [.] operator delete@plt
         +    2.66%              [.] llvm::bolt::RewriteInstance::selectFunctionsToPr
         +    2.06%              [.] llvm::bolt::getLTOCommonName
         +    0.01%              [k] asm_sysvec_apic_timer_interrupt
      +   25.63%              [.] llvm::bolt::YAMLProfileReader::parseFunctionProfile
      +   22.19%              [.] llvm::bolt::YAMLProfileReader::buildNameMaps
      +    1.56%              [.] llvm::bolt::YAMLProfileReader::readProfile
      +    0.68%              [.] llvm::bolt::YAMLProfileReader::matchProfileToFunction
      +    0.32%              [.] llvm::bolt::YAMLProfileReader::parseFunctionProfile(llvm::bolt::BinaryFunction&
      +    0.32%              [.] llvm::bolt::YAMLProfileReader::~YAMLProfileReader
      +    0.24%              [.] llvm::bolt::YAMLProfileReader::preprocessProfile

Quick analysis:

• mayHaveProfileData is not called from profile {pre-,}processing. It's only called from RI::selectFunctionsToProcess.
• parseFunctionProfile is invoked once per profile function and does the heavy lifting attaching the profile to CFG.
• buildNameMaps loops over profile functions and binary functions, hence the cost. I tried to reduce overhead per summary.
• readProfile actually reads YAML profile, but the bulk of overhead is in llvm::yaml code - see below.

llvm::yaml methods:

Samples: 49M of event 'cycles', Event count (approx.): 298169

-  100.00%              llvm-bolt
   -  100.00%              llvm-bolt
      +   15.42%              [.] llvm::yaml::Scanner::peekNext
      +    8.81%              [.] llvm::yaml::Scanner::scanPlainScalar
      +    8.18%              [.] llvm::yaml::Scanner::removeStaleSimpleKeyCandidates
      +    7.88%              [.] llvm::yaml::Scanner::fetchMoreTokens
      +    4.94%              [.] llvm::yaml::Document::parseBlockNode
      +    4.86%              [.] llvm::yaml::Scanner::getNext
      +    4.53%              [.] llvm::yaml::Scanner::scanToNextToken
      +    4.49%              [.] llvm::yaml::Input::createHNodes

As you can see createHNodes is no longer the most expensive part. I don't see easy optimization opportunities here.

bolt/include/bolt/Profile/YAMLProfileReader.h

private:
   /// is attributed.
   FunctionSet ProfiledFunctions;
 
   /// For LTO symbol resolution.
   /// Map a common LTO prefix to a list of YAML profiles matching the prefix.
   StringMap<std::vector<yaml::bolt::BinaryFunctionProfile *>> LTOCommonNameMap;
 
   /// Map a common LTO prefix to a set of binary functions.
-  StringMap<FunctionSet> LTOCommonNameFunctionMap;
+  StringMap<std::unordered_set<BinaryFunction *>> LTOCommonNameFunctionMap;
 
-  /// Strict matching of a name in a profile to its contents.
-  StringMap<yaml::bolt::BinaryFunctionProfile *> ProfileNameToProfile;
+  /// Function names in profile.
+  StringSet<> ProfileFunctionNames;
+
+  /// BinaryFunction pointers indexed by YamlBP functions.
+  std::vector<BinaryFunction *> ProfileBFs;
 
   /// Populate \p Function profile with the one supplied in YAML format.
   bool parseFunctionProfile(BinaryFunction &Function,
                             const yaml::bolt::BinaryFunctionProfile &YamlBF);
 
   /// Infer function profile from stale data (collected on older binaries).
   bool inferStaleProfile(BinaryFunction &Function,
                          const yaml::bolt::BinaryFunctionProfile &YamlBF);
 
   /// Initialize maps for profile matching.
-  void buildNameMaps(std::map<uint64_t, BinaryFunction> &Functions);
+  void buildNameMaps(BinaryContext &BC);
 
   /// Update matched YAML -> BinaryFunction pair.
   void matchProfileToFunction(yaml::bolt::BinaryFunctionProfile &YamlBF,
                               BinaryFunction &BF) {
     if (YamlBF.Id >= YamlProfileToFunction.size())
       YamlProfileToFunction.resize(YamlBF.Id + 1);
     YamlProfileToFunction[YamlBF.Id] = &BF;
     YamlBF.Used = true;
 
     assert(!ProfiledFunctions.count(&BF) &&
            "function already has an assigned profile");

bolt/lib/Profile/YAMLProfileReader.cpp

 //===- bolt/Profile/YAMLProfileReader.cpp - YAML profile de-serializer ----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Profile/YAMLProfileReader.h"
 #include "bolt/Core/BinaryBasicBlock.h"
 #include "bolt/Core/BinaryFunction.h"
 #include "bolt/Passes/MCF.h"
 #include "bolt/Profile/ProfileYAMLMapping.h"
 #include "bolt/Utils/Utils.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/CommandLine.h"
 
 using namespace llvm;
 
 namespace opts {
 
 extern cl::opt<unsigned> Verbosity;
 extern cl::OptionCategory BoltOptCategory;
if (auto MB = MemoryBuffer::getFileOrSTDIN(Filename)) {
     StringRef Buffer = (*MB)->getBuffer();
     return Buffer.startswith("---\n");
   } else {
     report_error(Filename, MB.getError());
   }
   return false;
 }
 
-void YAMLProfileReader::buildNameMaps(
-    std::map<uint64_t, BinaryFunction> &Functions) {
+void YAMLProfileReader::buildNameMaps(BinaryContext &BC) {
+  auto lookupFunction = [&](StringRef Name) -> BinaryFunction * {
+    if (BinaryData *BD = BC.getBinaryDataByName(Name))
+      return BC.getFunctionForSymbol(BD->getSymbol());
+    return nullptr;
+  };
+
+  ProfileBFs.reserve(YamlBP.Functions.size());
+
   for (yaml::bolt::BinaryFunctionProfile &YamlBF : YamlBP.Functions) {
     StringRef Name = YamlBF.Name;
     const size_t Pos = Name.find("(*");
     if (Pos != StringRef::npos)
       Name = Name.substr(0, Pos);
-    ProfileNameToProfile[Name] = &YamlBF;
+    ProfileFunctionNames.insert(Name);
+    ProfileBFs.push_back(lookupFunction(Name));
     if (const std::optional<StringRef> CommonName = getLTOCommonName(Name))
       LTOCommonNameMap[*CommonName].push_back(&YamlBF);
   }
-  for (auto &BFI : Functions) {
-    const BinaryFunction &Function = BFI.second;
-    for (StringRef Name : Function.getNames())
-      if (const std::optional<StringRef> CommonName = getLTOCommonName(Name))
-        LTOCommonNameFunctionMap[*CommonName].insert(&Function);
+  for (auto &[Symbol, BF] : BC.SymbolToFunctionMap) {
+    StringRef Name = Symbol->getName();
+      LTOCommonNameFunctionMap[*CommonName].insert(BF);
   }
 }
 
 bool YAMLProfileReader::hasLocalsWithFileName() const {
-  return llvm::any_of(ProfileNameToProfile.keys(), [](StringRef FuncName) {
+  return llvm::any_of(ProfileFunctionNames.keys(), [](StringRef FuncName) {
     return FuncName.count('/') == 2 && FuncName[0] != '/';
   });
 }
 
 bool YAMLProfileReader::parseFunctionProfile(
     BinaryFunction &BF, const yaml::bolt::BinaryFunctionProfile &YamlBF) {
   BinaryContext &BC = BF.getBinaryContext();
 
return make_error<StringError>(
         inconvertibleErrorCode());
 
   if (YamlBP.Header.EventNames.find(',') != StringRef::npos)
     return make_error<StringError>(
         Twine("multiple events in profile are not supported"),
         inconvertibleErrorCode());
 
   // Match profile to function based on a function name.
-  buildNameMaps(BC.getBinaryFunctions());
+  buildNameMaps(BC);
 
   // Preliminary assign function execution count.
-  for (auto &KV : BC.getBinaryFunctions()) {
-    BinaryFunction &BF = KV.second;
-    for (StringRef Name : BF.getNames()) {
-      auto PI = ProfileNameToProfile.find(Name);
-      if (PI != ProfileNameToProfile.end()) {
-        yaml::bolt::BinaryFunctionProfile &YamlBF = *PI->getValue();
-        BF.setExecutionCount(YamlBF.ExecCount);
-        break;
-      }
-    }
-  }
+  for (auto [YamlBF, BF] : llvm::zip_equal(YamlBP.Functions, ProfileBFs))
+    if (BF)
+      BF->setExecutionCount(YamlBF.ExecCount);
 
   return Error::success();
 }
 
 bool YAMLProfileReader::mayHaveProfileData(const BinaryFunction &BF) {
-  for (StringRef Name : BF.getNames()) {
-    if (ProfileNameToProfile.contains(Name))
+  for (StringRef Name : BF.getNames())
+    if (ProfileFunctionNames.contains(Name))
       return true;
+  for (StringRef Name : BF.getNames()) {
     if (const std::optional<StringRef> CommonName = getLTOCommonName(Name)) {
       if (LTOCommonNameMap.contains(*CommonName))
         return true;
     }
   }
 
   return false;
 }
 
 Error YAMLProfileReader::readProfile(BinaryContext &BC) {
   YamlProfileToFunction.resize(YamlBP.Functions.size() + 1);
 
   auto profileMatches = [](const yaml::bolt::BinaryFunctionProfile &Profile,
                            BinaryFunction &BF) {
     if (opts::IgnoreHash)
       return Profile.NumBasicBlocks == BF.size();
     return Profile.Hash == static_cast<uint64_t>(BF.getHash());
   };
 
   // We have to do 2 passes since LTO introduces an ambiguity in function
   // names. The first pass assigns profiles that match 100% by name and
   // by hash. The second pass allows name ambiguity for LTO private functions.
-  for (auto &BFI : BC.getBinaryFunctions()) {
-    BinaryFunction &Function = BFI.second;
-
+  for (auto [YamlBF, BF] : llvm::zip_equal(YamlBP.Functions, ProfileBFs)) {
+    if (!BF)
+      continue;
+    BinaryFunction &Function = *BF;
     // Clear function call count that may have been set while pre-processing
     // the profile.
     Function.setExecutionCount(BinaryFunction::COUNT_NO_PROFILE);
 
     // Recompute hash once per function.
     if (!opts::IgnoreHash)
       Function.computeHash(YamlBP.Header.IsDFSOrder);
 
-    for (StringRef FunctionName : Function.getNames()) {
-      auto PI = ProfileNameToProfile.find(FunctionName);
-      if (PI == ProfileNameToProfile.end())
-        continue;
-
-      yaml::bolt::BinaryFunctionProfile &YamlBF = *PI->getValue();
-      if (profileMatches(YamlBF, Function)) {
-        matchProfileToFunction(YamlBF, Function);
-        break;
-      }
-    }
-  }
-
-  for (auto &BFI : BC.getBinaryFunctions()) {
-    BinaryFunction &Function = BFI.second;
+    if (profileMatches(YamlBF, Function))
 
-    if (ProfiledFunctions.count(&Function))
+  for (auto &[CommonName, LTOProfiles]: LTOCommonNameMap) {
+    if (!LTOCommonNameFunctionMap.contains(CommonName))
       continue;
-
-    for (StringRef FunctionName : Function.getNames()) {
-      const std::optional<StringRef> CommonName =
-          getLTOCommonName(FunctionName);
-      if (CommonName) {
-        auto I = LTOCommonNameMap.find(*CommonName);
-        if (I == LTOCommonNameMap.end())
-          continue;
-
-        bool ProfileMatched = false;
-        std::vector<yaml::bolt::BinaryFunctionProfile *> &LTOProfiles =
-            I->getValue();
-        for (yaml::bolt::BinaryFunctionProfile *YamlBF : LTOProfiles) {
-          if (YamlBF->Used)
-            continue;
-          if ((ProfileMatched = profileMatches(*YamlBF, Function))) {
-            matchProfileToFunction(*YamlBF, Function);
-            break;
-          }
-        }
-        if (ProfileMatched)
-          break;
+    std::unordered_set<BinaryFunction *> &Functions =
+        LTOCommonNameFunctionMap[CommonName];
+    // Return true if a given profile is matched to one of BinaryFunctions with
+    // matching LTO common name.
+    auto matchProfile = [&](yaml::bolt::BinaryFunctionProfile *YamlBF) {
+        return false;
+      for (BinaryFunction *BF : Functions) {
+        if (!ProfiledFunctions.count(BF) && profileMatches(*YamlBF, *BF)) {
+          matchProfileToFunction(*YamlBF, *BF);
+          return true;
+      return false;
+    };
+    bool ProfileMatched = llvm::any_of(LTOProfiles, matchProfile);
 
-        // If there's only one function with a given name, try to
-        // match it partially.
-        if (LTOProfiles.size() == 1 &&
-            LTOCommonNameFunctionMap[*CommonName].size() == 1 &&
-            !LTOProfiles.front()->Used) {
-          matchProfileToFunction(*LTOProfiles.front(), Function);
-          break;
-        }
-      } else {
-        auto PI = ProfileNameToProfile.find(FunctionName);
-        if (PI == ProfileNameToProfile.end())
-          continue;
+    // If there's only one function with a given name, try to match it
+    // partially.
+    if (!ProfileMatched && LTOProfiles.size() == 1 && Functions.size() == 1 &&
+        !LTOProfiles.front()->Used &&
+        !ProfiledFunctions.count(*Functions.begin()))
+      matchProfileToFunction(*LTOProfiles.front(), **Functions.begin());
 
-        yaml::bolt::BinaryFunctionProfile &YamlBF = *PI->getValue();
-        if (!YamlBF.Used) {
-          matchProfileToFunction(YamlBF, Function);
-          break;
-        }
-      }
-    }
-  }
+  for (auto [YamlBF, BF] : llvm::zip_equal(YamlBP.Functions, ProfileBFs))
+    if (!YamlBF.Used && BF && !ProfiledFunctions.count(BF))
+      matchProfileToFunction(YamlBF, *BF);
 
   for (yaml::bolt::BinaryFunctionProfile &YamlBF : YamlBP.Functions)
     if (!YamlBF.Used && opts::Verbosity >= 1)
       errs() << "BOLT-WARNING: profile ignored for function " << YamlBF.Name
              << '\n';
 
   // Set for parseFunctionProfile().
   NormalizeByInsnCount = usesEvent("cycles") || usesEvent("instructions");