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