bolt/tools/merge-fdata/merge-fdata.cpp

   1 //===- bolt/tools/merge-fdata/merge-fdata.cpp -----------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Tool for merging profile in fdata format:
  10 //
  11 //   $ merge-fdata 1.fdata 2.fdata 3.fdata > merged.fdata
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "bolt/Profile/ProfileYAMLMapping.h"
  16 #include "llvm/ADT/STLExtras.h"
  17 #include "llvm/ADT/StringMap.h"
  18 #include "llvm/Support/CommandLine.h"
  19 #include "llvm/Support/FileSystem.h"
  20 #include "llvm/Support/ManagedStatic.h"
  21 #include "llvm/Support/PrettyStackTrace.h"
  22 #include "llvm/Support/Signals.h"
  23 #include "llvm/Support/ThreadPool.h"
  24 #include <algorithm>
  25 #include <mutex>
  26 #include <unordered_map>
  27
  28 using namespace llvm;
  29 using namespace llvm::yaml::bolt;
  30
  31 namespace opts {
  32
  33 cl::OptionCategory MergeFdataCategory("merge-fdata options");
  34
  35 enum SortType : char {
  36   ST_NONE,
  37   ST_EXEC_COUNT,      /// Sort based on function execution count.
  38   ST_TOTAL_BRANCHES,  /// Sort based on all branches in the function.
  39 };
  40
  41 static cl::list<std::string>
  42 InputDataFilenames(
  43   cl::Positional,
  44   cl::CommaSeparated,
  45   cl::desc("<fdata1> [<fdata2>]..."),
  46   cl::OneOrMore,
  47   cl::cat(MergeFdataCategory));
  48
  49 static cl::opt<SortType>
  50 PrintFunctionList("print",
  51   cl::desc("print the list of objects with count to stderr"),
  52   cl::init(ST_NONE),
  53   cl::values(clEnumValN(ST_NONE,
  54       "none",
  55       "do not print objects/functions"),
  56     clEnumValN(ST_EXEC_COUNT,
  57       "exec",
  58       "print functions sorted by execution count"),
  59     clEnumValN(ST_TOTAL_BRANCHES,
  60       "branches",
  61       "print functions sorted by total branch count")),
  62   cl::cat(MergeFdataCategory));
  63
  64 static cl::opt<bool>
  65 SuppressMergedDataOutput("q",
  66   cl::desc("do not print merged data to stdout"),
  67   cl::init(false),
  68   cl::Optional,
  69   cl::cat(MergeFdataCategory));
  70
  71 static cl::opt<std::string>
  72 OutputFilePath("o",
  73   cl::value_desc("file"),
  74   cl::desc("Write output to <file>"),
  75   cl::cat(MergeFdataCategory));
  76
  77 } // namespace opts
  78
  79 namespace {
  80
  81 static StringRef ToolName;
  82
  83 static void report_error(StringRef Message, std::error_code EC) {
  84   assert(EC);
  85   errs() << ToolName << ": '" << Message << "': " << EC.message() << ".\n";
  86   exit(1);
  87 }
  88
  89 static void report_error(Twine Message, StringRef CustomError) {
  90   errs() << ToolName << ": '" << Message << "': " << CustomError << ".\n";
  91   exit(1);
  92 }
  93
  94 static raw_fd_ostream &output() {
  95   if (opts::OutputFilePath.empty() || opts::OutputFilePath == "-")
  96     return outs();
  97   else {
  98     std::error_code EC;
  99     static raw_fd_ostream Output(opts::OutputFilePath, EC);
 100     if (EC)
 101       report_error(opts::OutputFilePath, EC);
 102     return Output;
 103   }
 104 }
 105
 106 void mergeProfileHeaders(BinaryProfileHeader &MergedHeader,
 107                          const BinaryProfileHeader &Header) {
 108   if (MergedHeader.FileName.empty())
 109     MergedHeader.FileName = Header.FileName;
 110
 111   if (!MergedHeader.FileName.empty() &&
 112       MergedHeader.FileName != Header.FileName)
 113     errs() << "WARNING: merging profile from a binary for " << Header.FileName
 114            << " into a profile for binary " << MergedHeader.FileName << '\n';
 115
 116   if (MergedHeader.Id.empty())
 117     MergedHeader.Id = Header.Id;
 118
 119   if (!MergedHeader.Id.empty() && (MergedHeader.Id != Header.Id))
 120     errs() << "WARNING: build-ids in merged profiles do not match\n";
 121
 122   // Cannot merge samples profile with LBR profile.
 123   if (!MergedHeader.Flags)
 124     MergedHeader.Flags = Header.Flags;
 125
 126   constexpr auto Mask = llvm::bolt::BinaryFunction::PF_LBR |
 127                         llvm::bolt::BinaryFunction::PF_SAMPLE;
 128   if ((MergedHeader.Flags & Mask) != (Header.Flags & Mask)) {
 129     errs() << "ERROR: cannot merge LBR profile with non-LBR profile\n";
 130     exit(1);
 131   }
 132   MergedHeader.Flags = MergedHeader.Flags | Header.Flags;
 133
 134   if (!Header.Origin.empty()) {
 135     if (MergedHeader.Origin.empty())
 136       MergedHeader.Origin = Header.Origin;
 137     else if (MergedHeader.Origin != Header.Origin)
 138       MergedHeader.Origin += "; " + Header.Origin;
 139   }
 140
 141   if (MergedHeader.EventNames.empty())
 142     MergedHeader.EventNames = Header.EventNames;
 143
 144   if (MergedHeader.EventNames != Header.EventNames) {
 145     errs() << "WARNING: merging profiles with different sampling events\n";
 146     MergedHeader.EventNames += "," + Header.EventNames;
 147   }
 148
 149   if (MergedHeader.HashFunction != Header.HashFunction)
 150     report_error("merge conflict",
 151                  "cannot merge profiles with different hash functions");
 152 }
 153
 154 void mergeBasicBlockProfile(BinaryBasicBlockProfile &MergedBB,
 155                             BinaryBasicBlockProfile &&BB,
 156                             const BinaryFunctionProfile &BF) {
 157   // Verify that the blocks match.
 158   if (BB.NumInstructions != MergedBB.NumInstructions)
 159     report_error(BF.Name + " : BB #" + Twine(BB.Index),
 160                  "number of instructions in block mismatch");
 161   if (BB.Hash != MergedBB.Hash)
 162     report_error(BF.Name + " : BB #" + Twine(BB.Index),
 163                  "basic block hash mismatch");
 164
 165   // Update the execution count.
 166   MergedBB.ExecCount += BB.ExecCount;
 167
 168   // Update the event count.
 169   MergedBB.EventCount += BB.EventCount;
 170
 171   // Merge calls sites.
 172   std::unordered_map<uint32_t, CallSiteInfo *> CSByOffset;
 173   for (CallSiteInfo &CS : BB.CallSites)
 174     CSByOffset.emplace(std::make_pair(CS.Offset, &CS));
 175
 176   for (CallSiteInfo &MergedCS : MergedBB.CallSites) {
 177     auto CSI = CSByOffset.find(MergedCS.Offset);
 178     if (CSI == CSByOffset.end())
 179       continue;
 180     yaml::bolt::CallSiteInfo &CS = *CSI->second;
 181     if (CS != MergedCS)
 182       continue;
 183
 184     MergedCS.Count += CS.Count;
 185     MergedCS.Mispreds += CS.Mispreds;
 186
 187     CSByOffset.erase(CSI);
 188   }
 189
 190   // Append the rest of call sites.
 191   for (std::pair<const uint32_t, CallSiteInfo *> CSI : CSByOffset)
 192     MergedBB.CallSites.emplace_back(std::move(*CSI.second));
 193
 194   // Merge successor info.
 195   std::vector<SuccessorInfo *> SIByIndex(BF.NumBasicBlocks);
 196   for (SuccessorInfo &SI : BB.Successors) {
 197     if (SI.Index >= BF.NumBasicBlocks)
 198       report_error(BF.Name, "bad successor index");
 199     SIByIndex[SI.Index] = &SI;
 200   }
 201   for (SuccessorInfo &MergedSI : MergedBB.Successors) {
 202     if (!SIByIndex[MergedSI.Index])
 203       continue;
 204     SuccessorInfo &SI = *SIByIndex[MergedSI.Index];
 205
 206     MergedSI.Count += SI.Count;
 207     MergedSI.Mispreds += SI.Mispreds;
 208
 209     SIByIndex[MergedSI.Index] = nullptr;
 210   }
 211   for (SuccessorInfo *SI : SIByIndex)
 212     if (SI)
 213       MergedBB.Successors.emplace_back(std::move(*SI));
 214 }
 215
 216 void mergeFunctionProfile(BinaryFunctionProfile &MergedBF,
 217                           BinaryFunctionProfile &&BF) {
 218   // Validate that we are merging the correct function.
 219   if (BF.NumBasicBlocks != MergedBF.NumBasicBlocks)
 220     report_error(BF.Name, "number of basic blocks mismatch");
 221   if (BF.Id != MergedBF.Id)
 222     report_error(BF.Name, "ID mismatch");
 223   if (BF.Hash != MergedBF.Hash)
 224     report_error(BF.Name, "hash mismatch");
 225
 226   // Update the execution count.
 227   MergedBF.ExecCount += BF.ExecCount;
 228
 229   // Merge basic blocks profile.
 230   std::vector<BinaryBasicBlockProfile *> BlockByIndex(BF.NumBasicBlocks);
 231   for (BinaryBasicBlockProfile &BB : BF.Blocks) {
 232     if (BB.Index >= BF.NumBasicBlocks)
 233       report_error(BF.Name + " : BB #" + Twine(BB.Index),
 234                    "bad basic block index");
 235     BlockByIndex[BB.Index] = &BB;
 236   }
 237   for (BinaryBasicBlockProfile &MergedBB : MergedBF.Blocks) {
 238     if (!BlockByIndex[MergedBB.Index])
 239       continue;
 240     BinaryBasicBlockProfile &BB = *BlockByIndex[MergedBB.Index];
 241
 242     mergeBasicBlockProfile(MergedBB, std::move(BB), MergedBF);
 243
 244     // Ignore this block in the future.
 245     BlockByIndex[MergedBB.Index] = nullptr;
 246   }
 247
 248   // Append blocks unique to BF (i.e. those that are not in MergedBF).
 249   for (BinaryBasicBlockProfile *BB : BlockByIndex)
 250     if (BB)
 251       MergedBF.Blocks.emplace_back(std::move(*BB));
 252 }
 253
 254 bool isYAML(const StringRef Filename) {
 255   ErrorOr<std::unique_ptr<MemoryBuffer>> MB =
 256       MemoryBuffer::getFileOrSTDIN(Filename);
 257   if (std::error_code EC = MB.getError())
 258     report_error(Filename, EC);
 259   StringRef Buffer = MB.get()->getBuffer();
 260   if (Buffer.starts_with("---\n"))
 261     return true;
 262   return false;
 263 }
 264
 265 void mergeLegacyProfiles(const SmallVectorImpl<std::string> &Filenames) {
 266   errs() << "Using legacy profile format.\n";
 267   std::optional<bool> BoltedCollection;
 268   std::mutex BoltedCollectionMutex;
 269   typedef StringMap<uint64_t> ProfileTy;
 270
 271   auto ParseProfile = [&](const std::string &Filename, auto &Profiles) {
 272     const llvm::thread::id tid = llvm::this_thread::get_id();
 273
 274     if (isYAML(Filename))
 275       report_error(Filename, "cannot mix YAML and legacy formats");
 276     ErrorOr<std::unique_ptr<MemoryBuffer>> MB =
 277         MemoryBuffer::getFileOrSTDIN(Filename);
 278     if (std::error_code EC = MB.getError())
 279       report_error(Filename, EC);
 280
 281     StringRef Buf = MB.get()->getBuffer();
 282     ProfileTy *Profile;
 283     {
 284       std::lock_guard<std::mutex> Lock(BoltedCollectionMutex);
 285       // Check if the string "boltedcollection" is in the first line
 286       if (Buf.starts_with("boltedcollection\n")) {
 287         if (!BoltedCollection.value_or(true))
 288           report_error(
 289               Filename,
 290               "cannot mix profile collected in BOLT and non-BOLT deployments");
 291         BoltedCollection = true;
 292         Buf = Buf.drop_front(17);
 293       } else {
 294         if (BoltedCollection.value_or(false))
 295           report_error(
 296               Filename,
 297               "cannot mix profile collected in BOLT and non-BOLT deployments");
 298         BoltedCollection = false;
 299       }
 300
 301       Profile = &Profiles[tid];
 302     }
 303
 304     SmallVector<StringRef> Lines;
 305     SplitString(Buf, Lines, "\n");
 306     for (StringRef Line : Lines) {
 307       size_t Pos = Line.rfind(" ");
 308       if (Pos == StringRef::npos)
 309         report_error(Filename, "Malformed / corrupted profile");
 310       StringRef Signature = Line.substr(0, Pos);
 311       uint64_t Count;
 312       if (Line.substr(Pos + 1, Line.size() - Pos).getAsInteger(10, Count))
 313         report_error(Filename, "Malformed / corrupted profile counter");
 314       Count += Profile->lookup(Signature);
 315       Profile->insert_or_assign(Signature, Count);
 316     }
 317   };
 318
 319   // The final reduction has non-trivial cost, make sure each thread has at
 320   // least 4 tasks.
 321   ThreadPoolStrategy S = optimal_concurrency(
 322       std::max(Filenames.size() / 4, static_cast<size_t>(1)));
 323   DefaultThreadPool Pool(S);
 324   DenseMap<llvm::thread::id, ProfileTy> ParsedProfiles(
 325       Pool.getMaxConcurrency());
 326   for (const auto &Filename : Filenames)
 327     Pool.async(ParseProfile, std::cref(Filename), std::ref(ParsedProfiles));
 328   Pool.wait();
 329
 330   ProfileTy MergedProfile;
 331   for (const auto &[Thread, Profile] : ParsedProfiles)
 332     for (const auto &[Key, Value] : Profile) {
 333       uint64_t Count = MergedProfile.lookup(Key) + Value;
 334       MergedProfile.insert_or_assign(Key, Count);
 335     }
 336
 337   if (BoltedCollection.value_or(false))
 338     output() << "boltedcollection\n";
 339   for (const auto &[Key, Value] : MergedProfile)
 340     output() << Key << " " << Value << "\n";
 341
 342   errs() << "Profile from " << Filenames.size() << " files merged.\n";
 343 }
 344
 345 } // anonymous namespace
 346
 347 int main(int argc, char **argv) {
 348   // Print a stack trace if we signal out.
 349   sys::PrintStackTraceOnErrorSignal(argv[0]);
 350   PrettyStackTraceProgram X(argc, argv);
 351
 352   llvm_shutdown_obj Y; // Call llvm_shutdown() on exit.
 353
 354   cl::HideUnrelatedOptions(opts::MergeFdataCategory);
 355
 356   cl::ParseCommandLineOptions(argc, argv,
 357                               "merge multiple fdata into a single file");
 358
 359   ToolName = argv[0];
 360
 361   // Recursively expand input directories into input file lists.
 362   SmallVector<std::string> Inputs;
 363   for (std::string &InputDataFilename : opts::InputDataFilenames) {
 364     if (!llvm::sys::fs::exists(InputDataFilename))
 365       report_error(InputDataFilename,
 366                    std::make_error_code(std::errc::no_such_file_or_directory));
 367     if (llvm::sys::fs::is_regular_file(InputDataFilename))
 368       Inputs.emplace_back(InputDataFilename);
 369     else if (llvm::sys::fs::is_directory(InputDataFilename)) {
 370       std::error_code EC;
 371       for (llvm::sys::fs::recursive_directory_iterator F(InputDataFilename, EC),
 372            E;
 373            F != E && !EC; F.increment(EC))
 374         if (llvm::sys::fs::is_regular_file(F->path()))
 375           Inputs.emplace_back(F->path());
 376       if (EC)
 377         report_error(InputDataFilename, EC);
 378     }
 379   }
 380
 381   if (!isYAML(Inputs.front())) {
 382     mergeLegacyProfiles(Inputs);
 383     return 0;
 384   }
 385
 386   // Merged header.
 387   BinaryProfileHeader MergedHeader;
 388   MergedHeader.Version = 1;
 389
 390   // Merged information for all functions.
 391   StringMap<BinaryFunctionProfile> MergedBFs;
 392
 393   bool FirstHeader = true;
 394   for (std::string &InputDataFilename : Inputs) {
 395     ErrorOr<std::unique_ptr<MemoryBuffer>> MB =
 396         MemoryBuffer::getFileOrSTDIN(InputDataFilename);
 397     if (std::error_code EC = MB.getError())
 398       report_error(InputDataFilename, EC);
 399     yaml::Input YamlInput(MB.get()->getBuffer());
 400     YamlInput.setAllowUnknownKeys(true);
 401
 402     errs() << "Merging data from " << InputDataFilename << "...\n";
 403
 404     BinaryProfile BP;
 405     YamlInput >> BP;
 406     if (YamlInput.error())
 407       report_error(InputDataFilename, YamlInput.error());
 408
 409     // Sanity check.
 410     if (BP.Header.Version != 1) {
 411       errs() << "Unable to merge data from profile using version "
 412              << BP.Header.Version << '\n';
 413       exit(1);
 414     }
 415
 416     // Merge the header.
 417     if (FirstHeader) {
 418       MergedHeader = BP.Header;
 419       FirstHeader = false;
 420     } else {
 421       mergeProfileHeaders(MergedHeader, BP.Header);
 422     }
 423
 424     // Do the function merge.
 425     for (BinaryFunctionProfile &BF : BP.Functions) {
 426       if (!MergedBFs.count(BF.Name)) {
 427         MergedBFs.insert(std::make_pair(BF.Name, BF));
 428         continue;
 429       }
 430
 431       BinaryFunctionProfile &MergedBF = MergedBFs.find(BF.Name)->second;
 432       mergeFunctionProfile(MergedBF, std::move(BF));
 433     }
 434   }
 435
 436   if (!opts::SuppressMergedDataOutput) {
 437     yaml::Output YamlOut(output());
 438
 439     BinaryProfile MergedProfile;
 440     MergedProfile.Header = MergedHeader;
 441     MergedProfile.Functions.resize(MergedBFs.size());
 442     llvm::copy(llvm::make_second_range(MergedBFs),
 443                MergedProfile.Functions.begin());
 444
 445     // For consistency, sort functions by their IDs.
 446     llvm::sort(MergedProfile.Functions,
 447                [](const BinaryFunctionProfile &A,
 448                   const BinaryFunctionProfile &B) { return A.Id < B.Id; });
 449
 450     YamlOut << MergedProfile;
 451   }
 452
 453   errs() << "Data for " << MergedBFs.size()
 454          << " unique objects successfully merged.\n";
 455
 456   if (opts::PrintFunctionList != opts::ST_NONE) {
 457     // List of function names with execution count.
 458     std::vector<std::pair<uint64_t, StringRef>> FunctionList(MergedBFs.size());
 459     using CountFuncType = std::function<std::pair<uint64_t, StringRef>(
 460         const StringMapEntry<BinaryFunctionProfile> &)>;
 461     CountFuncType ExecCountFunc =
 462         [](const StringMapEntry<BinaryFunctionProfile> &V) {
 463           return std::make_pair(V.second.ExecCount, StringRef(V.second.Name));
 464         };
 465     CountFuncType BranchCountFunc =
 466         [](const StringMapEntry<BinaryFunctionProfile> &V) {
 467           // Return total branch count.
 468           uint64_t BranchCount = 0;
 469           for (const BinaryBasicBlockProfile &BI : V.second.Blocks)
 470             for (const SuccessorInfo &SI : BI.Successors)
 471               BranchCount += SI.Count;
 472           return std::make_pair(BranchCount, StringRef(V.second.Name));
 473         };
 474
 475     CountFuncType CountFunc = (opts::PrintFunctionList == opts::ST_EXEC_COUNT)
 476                                   ? ExecCountFunc
 477                                   : BranchCountFunc;
 478     llvm::transform(MergedBFs, FunctionList.begin(), CountFunc);
 479     llvm::stable_sort(reverse(FunctionList));
 480     errs() << "Functions sorted by "
 481            << (opts::PrintFunctionList == opts::ST_EXEC_COUNT ? "execution"
 482                                                               : "total branch")
 483            << " count:\n";
 484     for (std::pair<uint64_t, StringRef> &FI : FunctionList)
 485       errs() << FI.second << " : " << FI.first << '\n';
 486   }
 487
 488   return 0;
 489 }