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