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 <fstream> 26 #include <mutex> 27 #include <unordered_map> 28 29 using namespace llvm; 30 using namespace llvm::yaml::bolt; 31 32 namespace opts { 33 34 cl::OptionCategory MergeFdataCategory("merge-fdata options"); 35 36 enum 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 42 static cl::list<std::string> 43 InputDataFilenames( 44 cl::Positional, 45 cl::CommaSeparated, 46 cl::desc("<fdata1> [<fdata2>]..."), 47 cl::OneOrMore, 48 cl::cat(MergeFdataCategory)); 49 50 static cl::opt<SortType> 51 PrintFunctionList("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 65 static cl::opt<bool> 66 SuppressMergedDataOutput("q", 67 cl::desc("do not print merged data to stdout"), 68 cl::init(false), 69 cl::Optional, 70 cl::cat(MergeFdataCategory)); 71 72 static cl::opt<std::string> 73 OutputFilePath("o", 74 cl::value_desc("file"), 75 cl::desc("Write output to <file>"), 76 cl::cat(MergeFdataCategory)); 77 78 } // namespace opts 79 80 namespace { 81 82 static StringRef ToolName; 83 84 static void report_error(StringRef Message, std::error_code EC) { 85 assert(EC); 86 errs() << ToolName << ": '" << Message << "': " << EC.message() << ".\n"; 87 exit(1); 88 } 89 90 static void report_error(Twine Message, StringRef CustomError) { 91 errs() << ToolName << ": '" << Message << "': " << CustomError << ".\n"; 92 exit(1); 93 } 94 95 static 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 107 void 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.FileName 115 << " 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 LBR profile. 124 if (!MergedHeader.Flags) 125 MergedHeader.Flags = Header.Flags; 126 127 constexpr auto Mask = llvm::bolt::BinaryFunction::PF_LBR | 128 llvm::bolt::BinaryFunction::PF_SAMPLE; 129 if ((MergedHeader.Flags & Mask) != (Header.Flags & Mask)) { 130 errs() << "ERROR: cannot merge LBR profile with non-LBR 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 155 void 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 217 void 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 255 bool 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 266 void 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 line 302 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 line 309 checkMode("boltedcollection", BoltedCollection); 310 // Check if the string "no_lbr" is in the first line 311 // (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 field 323 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 at 336 // 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 namespace 368 369 int 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 ? ExecCountFunc 499 : 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