1 //===--- BoltDiff.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 // RewriteInstance methods related to comparing one instance to another, used
10 // by the boltdiff tool to print a report.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "bolt/Passes/IdenticalCodeFolding.h"
15 #include "bolt/Profile/ProfileReaderBase.h"
16 #include "bolt/Rewrite/RewriteInstance.h"
17 #include "llvm/Support/CommandLine.h"
18 
19 #undef  DEBUG_TYPE
20 #define DEBUG_TYPE "boltdiff"
21 
22 using namespace llvm;
23 using namespace object;
24 using namespace bolt;
25 
26 namespace opts {
27 extern cl::OptionCategory BoltDiffCategory;
28 extern cl::opt<bool> NeverPrint;
29 extern cl::opt<bool> ICF;
30 
31 static cl::opt<bool>
32 IgnoreLTOSuffix("ignore-lto-suffix",
33   cl::desc("ignore lto_priv or const suffixes when matching functions"),
34   cl::init(true),
35   cl::ZeroOrMore,
36   cl::cat(BoltDiffCategory));
37 
38 static cl::opt<bool>
39 PrintUnmapped("print-unmapped",
40   cl::desc("print functions of binary 2 that were not matched to any "
41            "function in binary 1"),
42   cl::init(false),
43   cl::ZeroOrMore,
44   cl::cat(BoltDiffCategory));
45 
46 static cl::opt<bool>
47 PrintProfiledUnmapped("print-profiled-unmapped",
48   cl::desc("print functions that have profile in binary 1 but do not "
49            "in binary 2"),
50   cl::init(false),
51   cl::ZeroOrMore,
52   cl::cat(BoltDiffCategory));
53 
54 static cl::opt<bool>
55 PrintDiffCFG("print-diff-cfg",
56   cl::desc("print the CFG of important functions that changed in "
57            "binary 2"),
58   cl::init(false),
59   cl::ZeroOrMore,
60   cl::cat(BoltDiffCategory));
61 
62 static cl::opt<bool>
63 PrintDiffBBs("print-diff-bbs",
64   cl::desc("print the basic blocks showed in top differences"),
65   cl::init(false),
66   cl::ZeroOrMore,
67   cl::cat(BoltDiffCategory));
68 
69 static cl::opt<bool>
70 MatchByHash("match-by-hash",
71   cl::desc("match functions in binary 2 to binary 1 if they have the same "
72            "hash of a function in binary 1"),
73   cl::init(false),
74   cl::ZeroOrMore,
75   cl::cat(BoltDiffCategory));
76 
77 static cl::opt<bool>
78 IgnoreUnchanged("ignore-unchanged",
79   cl::desc("do not diff functions whose contents have not been changed from "
80            "one binary to another"),
81   cl::init(false),
82   cl::ZeroOrMore,
83   cl::cat(BoltDiffCategory));
84 
85 static cl::opt<unsigned>
86 DisplayCount("display-count",
87   cl::desc("number of functions to display when printing the top largest "
88            "differences in function activity"),
89   cl::init(10),
90   cl::ZeroOrMore,
91   cl::cat(BoltDiffCategory));
92 
93 static cl::opt<bool>
94 NormalizeByBin1("normalize-by-bin1",
95   cl::desc("show execution count of functions in binary 2 as a ratio of the "
96            "total samples in binary 1 - make sure both profiles have equal "
97            "collection time and sampling rate for this to make sense"),
98   cl::init(false),
99   cl::ZeroOrMore,
100   cl::cat(BoltDiffCategory));
101 
102 } // end namespace opts
103 
104 namespace llvm {
105 namespace bolt {
106 
107 namespace {
108 
109 /// Helper used to print colored numbers
110 void printColoredPercentage(double Perc) {
111   if (outs().has_colors() && Perc > 0.0)
112     outs().changeColor(raw_ostream::RED);
113   else if (outs().has_colors() && Perc < 0.0)
114     outs().changeColor(raw_ostream::GREEN);
115   else if (outs().has_colors())
116     outs().changeColor(raw_ostream::YELLOW);
117   outs() << format("%.2f", Perc) << "%";
118   if (outs().has_colors())
119     outs().resetColor();
120 }
121 
122 void setLightColor() {
123   if (opts::PrintDiffBBs && outs().has_colors())
124     outs().changeColor(raw_ostream::CYAN);
125 }
126 
127 void setTitleColor() {
128   if (outs().has_colors())
129     outs().changeColor(raw_ostream::WHITE, /*Bold=*/true);
130 }
131 
132 void setRegularColor() {
133   if (outs().has_colors())
134     outs().resetColor();
135 }
136 
137 } // end anonymous namespace
138 
139 /// Perform the comparison between two binaries with profiling information
140 class RewriteInstanceDiff {
141   typedef std::tuple<const BinaryBasicBlock *, const BinaryBasicBlock *, double>
142       EdgeTy;
143 
144   RewriteInstance &RI1;
145   RewriteInstance &RI2;
146 
147   // The map of functions keyed by functions in binary 2, providing its
148   // corresponding function in binary 1
149   std::map<const BinaryFunction *, const BinaryFunction *> FuncMap;
150 
151   // The map of basic blocks correspondence, analogue to FuncMap for BBs,
152   // sorted by score difference
153   std::map<const BinaryBasicBlock *, const BinaryBasicBlock *> BBMap;
154 
155   // The map of edge correspondence
156   std::map<double, std::pair<EdgeTy, EdgeTy>> EdgeMap;
157 
158   // Maps all known basic blocks back to their parent function
159   std::map<const BinaryBasicBlock *, const BinaryFunction *> BBToFuncMap;
160 
161   // Accounting which functions were matched
162   std::set<const BinaryFunction *> Bin1MappedFuncs;
163   std::set<const BinaryFunction *> Bin2MappedFuncs;
164 
165   // Structures for our 3 matching strategies: by name, by hash and by lto name,
166   // from the strongest to the weakest bind between two functions
167   StringMap<const BinaryFunction *> NameLookup;
168   DenseMap<size_t, const BinaryFunction *> HashLookup;
169   StringMap<const BinaryFunction *> LTONameLookup1;
170   StringMap<const BinaryFunction *> LTONameLookup2;
171 
172   // Score maps used to order and find hottest functions
173   std::multimap<double, const BinaryFunction *> LargestBin1;
174   std::multimap<double, const BinaryFunction *> LargestBin2;
175 
176   // Map multiple functions in the same LTO bucket to a single parent function
177   // representing all functions sharing the same prefix
178   std::map<const BinaryFunction *, const BinaryFunction *> LTOMap1;
179   std::map<const BinaryFunction *, const BinaryFunction *> LTOMap2;
180   std::map<const BinaryFunction *, double> LTOAggregatedScore1;
181   std::map<const BinaryFunction *, double> LTOAggregatedScore2;
182 
183   // Map scores in bin2 and 1 keyed by a binary 2 function - post-matching
184   DenseMap<const BinaryFunction *, std::pair<double, double>> ScoreMap;
185 
186   double getNormalizedScore(const BinaryFunction &Function,
187                             const RewriteInstance &Ctx) {
188     if (!opts::NormalizeByBin1)
189       return static_cast<double>(Function.getFunctionScore()) / Ctx.getTotalScore();
190     return static_cast<double>(Function.getFunctionScore()) / RI1.getTotalScore();
191   }
192 
193   double getNormalizedScore(const BinaryBasicBlock &BB,
194                             const RewriteInstance &Ctx) {
195     if (!opts::NormalizeByBin1)
196       return static_cast<double>(BB.getKnownExecutionCount()) / Ctx.getTotalScore();
197     return static_cast<double>(BB.getKnownExecutionCount()) / RI1.getTotalScore();
198   }
199 
200   double getNormalizedScore(BinaryBasicBlock::branch_info_iterator BIIter,
201                             const RewriteInstance &Ctx) {
202     double Score =
203               BIIter->Count == BinaryBasicBlock::COUNT_NO_PROFILE
204                   ? 0
205                   : BIIter->Count;
206     if (!opts::NormalizeByBin1)
207       return Score / Ctx.getTotalScore();
208     return Score / RI1.getTotalScore();
209   }
210 
211   /// Initialize data structures used for function lookup in binary 1, used
212   /// later when matching functions in binary 2 to corresponding functions
213   /// in binary 1
214   void buildLookupMaps() {
215     for (const auto &BFI : RI1.BC->getBinaryFunctions()) {
216       StringRef LTOName;
217       const BinaryFunction &Function = BFI.second;
218       const double Score = getNormalizedScore(Function, RI1);
219       LargestBin1.insert(std::make_pair<>(Score, &Function));
220       for (const StringRef Name : Function.getNames()) {
221         if (Optional<StringRef> OptionalLTOName = getLTOCommonName(Name))
222           LTOName = *OptionalLTOName;
223         NameLookup[Name] = &Function;
224       }
225       if (opts::MatchByHash && Function.hasCFG())
226         HashLookup[Function.computeHash(/*UseDFS=*/true)] = &Function;
227       if (opts::IgnoreLTOSuffix && !LTOName.empty()) {
228         if (!LTONameLookup1.count(LTOName))
229           LTONameLookup1[LTOName] = &Function;
230         LTOMap1[&Function] = LTONameLookup1[LTOName];
231       }
232     }
233 
234     // Compute LTONameLookup2 and LargestBin2
235     for (const auto &BFI : RI2.BC->getBinaryFunctions()) {
236       StringRef LTOName;
237       const BinaryFunction &Function = BFI.second;
238       const double Score = getNormalizedScore(Function, RI2);
239       LargestBin2.insert(std::make_pair<>(Score, &Function));
240       for (const StringRef Name : Function.getNames()) {
241         if (Optional<StringRef> OptionalLTOName = getLTOCommonName(Name))
242           LTOName = *OptionalLTOName;
243       }
244       if (opts::IgnoreLTOSuffix && !LTOName.empty()) {
245         if (!LTONameLookup2.count(LTOName))
246           LTONameLookup2[LTOName] = &Function;
247         LTOMap2[&Function] = LTONameLookup2[LTOName];
248       }
249     }
250   }
251 
252   /// Match functions in binary 2 with functions in binary 1
253   void matchFunctions() {
254     outs() << "BOLT-DIFF: Mapping functions in Binary2 to Binary1\n";
255     uint64_t BothHaveProfile = 0ull;
256     std::set<const BinaryFunction *> Bin1ProfiledMapped;
257 
258     for (const auto &BFI2 : RI2.BC->getBinaryFunctions()) {
259       const BinaryFunction &Function2 = BFI2.second;
260       StringRef LTOName;
261       bool Match = false;
262       for (const StringRef Name : Function2.getNames()) {
263         auto Iter = NameLookup.find(Name);
264         if (Optional<StringRef> OptionalLTOName = getLTOCommonName(Name))
265           LTOName = *OptionalLTOName;
266         if (Iter == NameLookup.end())
267           continue;
268         FuncMap.insert(std::make_pair<>(&Function2, Iter->second));
269         Bin1MappedFuncs.insert(Iter->second);
270         Bin2MappedFuncs.insert(&Function2);
271         if (Function2.hasValidProfile() && Iter->second->hasValidProfile()) {
272           ++BothHaveProfile;
273           Bin1ProfiledMapped.insert(Iter->second);
274         }
275         Match = true;
276         break;
277       }
278       if (Match || !Function2.hasCFG())
279         continue;
280       auto Iter = HashLookup.find(Function2.computeHash(/*UseDFS*/true));
281       if (Iter != HashLookup.end()) {
282         FuncMap.insert(std::make_pair<>(&Function2, Iter->second));
283         Bin1MappedFuncs.insert(Iter->second);
284         Bin2MappedFuncs.insert(&Function2);
285         if (Function2.hasValidProfile() && Iter->second->hasValidProfile()) {
286           ++BothHaveProfile;
287           Bin1ProfiledMapped.insert(Iter->second);
288         }
289         continue;
290       }
291       if (LTOName.empty())
292         continue;
293       auto LTOIter = LTONameLookup1.find(LTOName);
294       if (LTOIter != LTONameLookup1.end()) {
295         FuncMap.insert(std::make_pair<>(&Function2, LTOIter->second));
296         Bin1MappedFuncs.insert(LTOIter->second);
297         Bin2MappedFuncs.insert(&Function2);
298         if (Function2.hasValidProfile() && LTOIter->second->hasValidProfile()) {
299           ++BothHaveProfile;
300           Bin1ProfiledMapped.insert(LTOIter->second);
301         }
302       }
303     }
304     PrintProgramStats PPS(opts::NeverPrint);
305     outs() << "* BOLT-DIFF: Starting print program stats pass for binary 1\n";
306     PPS.runOnFunctions(*RI1.BC);
307     outs() << "* BOLT-DIFF: Starting print program stats pass for binary 2\n";
308     PPS.runOnFunctions(*RI2.BC);
309     outs() << "=====\n";
310     outs() << "Inputs share " << BothHaveProfile
311            << " functions with valid profile.\n";
312     if (opts::PrintProfiledUnmapped) {
313       outs() << "\nFunctions in profile 1 that are missing in the profile 2:\n";
314       std::vector<const BinaryFunction *> Unmapped;
315       for (const auto &BFI : RI1.BC->getBinaryFunctions()) {
316         const BinaryFunction &Function = BFI.second;
317         if (!Function.hasValidProfile() || Bin1ProfiledMapped.count(&Function))
318           continue;
319         Unmapped.emplace_back(&Function);
320       }
321       std::sort(Unmapped.begin(), Unmapped.end(),
322                 [&](const BinaryFunction *A, const BinaryFunction *B) {
323                   return A->getFunctionScore() > B->getFunctionScore();
324                 });
325       for (const BinaryFunction *Function : Unmapped) {
326         outs() << Function->getPrintName() << " : ";
327         outs() << Function->getFunctionScore() << "\n";
328       }
329       outs() << "=====\n";
330     }
331   }
332 
333   /// Check if opcodes in BB1 match those in BB2
334   bool compareBBs(const BinaryBasicBlock &BB1,
335                   const BinaryBasicBlock &BB2) const {
336     auto Iter1 = BB1.begin();
337     auto Iter2 = BB2.begin();
338     if ((Iter1 == BB1.end() && Iter2 != BB2.end()) ||
339         (Iter1 != BB1.end() && Iter2 == BB2.end()))
340       return false;
341 
342     while (Iter1 != BB1.end()) {
343       if (Iter2 == BB2.end() ||
344           Iter1->getOpcode() != Iter2->getOpcode())
345         return false;
346 
347       ++Iter1;
348       ++Iter2;
349     }
350 
351     if (Iter2 != BB2.end())
352       return false;
353     return true;
354   }
355 
356   /// For a function in binary 2 that matched one in binary 1, now match each
357   /// individual basic block in it to its corresponding blocks in binary 1.
358   /// Also match each edge in binary 2 to the corresponding ones in binary 1.
359   void matchBasicBlocks() {
360     for (const auto &MapEntry : FuncMap) {
361       const BinaryFunction *const &Func1 = MapEntry.second;
362       const BinaryFunction *const &Func2 = MapEntry.first;
363 
364       auto Iter1 = Func1->layout_begin();
365       auto Iter2 = Func2->layout_begin();
366 
367       bool Match = true;
368       std::map<const BinaryBasicBlock *, const BinaryBasicBlock *> Map;
369       std::map<double, std::pair<EdgeTy, EdgeTy>> EMap;
370       while (Iter1 != Func1->layout_end()) {
371         if (Iter2 == Func2->layout_end()) {
372           Match = false;
373           break;
374         }
375         if (!compareBBs(**Iter1, **Iter2)) {
376           Match = false;
377           break;
378         }
379         Map.insert(std::make_pair<>(*Iter2, *Iter1));
380 
381         auto SuccIter1 = (*Iter1)->succ_begin();
382         auto SuccIter2 = (*Iter2)->succ_begin();
383         auto BIIter1 = (*Iter1)->branch_info_begin();
384         auto BIIter2 = (*Iter2)->branch_info_begin();
385         while (SuccIter1 != (*Iter1)->succ_end()) {
386           if (SuccIter2 == (*Iter2)->succ_end()) {
387             Match = false;
388             break;
389           }
390           const double ScoreEdge1 = getNormalizedScore(BIIter1, RI1);
391           const double ScoreEdge2 = getNormalizedScore(BIIter2, RI2);
392           EMap.insert(std::make_pair<>(
393               std::abs(ScoreEdge2 - ScoreEdge1),
394               std::make_pair<>(
395                   std::make_tuple<>(*Iter2, *SuccIter2, ScoreEdge2),
396                   std::make_tuple<>(*Iter1, *SuccIter1, ScoreEdge1))));
397 
398           ++SuccIter1;
399           ++SuccIter2;
400           ++BIIter1;
401           ++BIIter2;
402         }
403         if (SuccIter2 != (*Iter2)->succ_end())
404           Match = false;
405         if (!Match)
406           break;
407 
408         BBToFuncMap[*Iter1] = Func1;
409         BBToFuncMap[*Iter2] = Func2;
410         ++Iter1;
411         ++Iter2;
412       }
413       if (!Match || Iter2 != Func2->layout_end())
414         continue;
415 
416       BBMap.insert(Map.begin(), Map.end());
417       EdgeMap.insert(EMap.begin(), EMap.end());
418     }
419   }
420 
421   /// Print the largest differences in basic block performance from binary 1
422   /// to binary 2
423   void reportHottestBBDiffs() {
424     std::map<double, const BinaryBasicBlock *> LargestDiffs;
425     for (const auto &MapEntry : BBMap) {
426       const BinaryBasicBlock *BB2 = MapEntry.first;
427       const BinaryBasicBlock *BB1 = MapEntry.second;
428       LargestDiffs.insert(
429           std::make_pair<>(std::abs(getNormalizedScore(*BB2, RI2) -
430                                     getNormalizedScore(*BB1, RI1)),
431                            BB2));
432     }
433 
434     unsigned Printed = 0;
435     setTitleColor();
436     outs()
437         << "\nTop " << opts::DisplayCount
438         << " largest differences in basic block performance bin 2 -> bin 1:\n";
439     outs() << "=========================================================\n";
440     setRegularColor();
441     outs() << " * Functions with different contents do not appear here\n\n";
442     for (auto I = LargestDiffs.rbegin(), E = LargestDiffs.rend(); I != E; ++I) {
443       const BinaryBasicBlock *BB2 = I->second;
444       const double Score2 = getNormalizedScore(*BB2, RI2);
445       const double Score1 = getNormalizedScore(*BBMap[BB2], RI1);
446       outs() << "BB " << BB2->getName() << " from "
447              << BBToFuncMap[BB2]->getDemangledName()
448              << "\n\tScore bin1 = " << format("%.4f", Score1 * 100.0)
449              << "%\n\tScore bin2 = " << format("%.4f", Score2 * 100.0);
450       outs() << "%\t(Difference: ";
451       printColoredPercentage((Score2 - Score1) * 100.0);
452       outs() << ")\n";
453       if (opts::PrintDiffBBs) {
454         setLightColor();
455         BB2->dump();
456         setRegularColor();
457       }
458       if (Printed++ == opts::DisplayCount)
459         break;
460     }
461   }
462 
463   /// Print the largest differences in edge counts from one binary to another
464   void reportHottestEdgeDiffs() {
465     unsigned Printed = 0;
466     setTitleColor();
467     outs()
468         << "\nTop " << opts::DisplayCount
469         << " largest differences in edge hotness bin 2 -> bin 1:\n";
470     outs() << "=========================================================\n";
471     setRegularColor();
472     outs() << " * Functions with different contents do not appear here\n";
473     for (auto I = EdgeMap.rbegin(), E = EdgeMap.rend(); I != E; ++I) {
474       std::tuple<const BinaryBasicBlock *, const BinaryBasicBlock *, double>
475           &Edge2 = I->second.first;
476       std::tuple<const BinaryBasicBlock *, const BinaryBasicBlock *, double>
477           &Edge1 = I->second.second;
478       const double Score2 = std::get<2>(Edge2);
479       const double Score1 = std::get<2>(Edge1);
480       outs() << "Edge (" << std::get<0>(Edge2)->getName() << " -> "
481              << std::get<1>(Edge2)->getName() << ") in "
482              << BBToFuncMap[std::get<0>(Edge2)]->getDemangledName()
483              << "\n\tScore bin1 = " << format("%.4f", Score1 * 100.0)
484              << "%\n\tScore bin2 = " << format("%.4f", Score2 * 100.0);
485       outs() << "%\t(Difference: ";
486       printColoredPercentage((Score2 - Score1) * 100.0);
487       outs() << ")\n";
488       if (opts::PrintDiffBBs) {
489         setLightColor();
490         std::get<0>(Edge2)->dump();
491         std::get<1>(Edge2)->dump();
492         setRegularColor();
493       }
494       if (Printed++ == opts::DisplayCount)
495         break;
496     }
497  }
498 
499   /// For LTO functions sharing the same prefix (for example, func1.lto_priv.1
500   /// and func1.lto_priv.2 share the func1.lto_priv prefix), compute aggregated
501   /// scores for them. This is used to avoid reporting all LTO functions as
502   /// having a large difference in performance because hotness shifted from
503   /// LTO variant 1 to variant 2, even though they represent the same function.
504   void computeAggregatedLTOScore() {
505     for (const auto &BFI : RI1.BC->getBinaryFunctions()) {
506       const BinaryFunction &Function = BFI.second;
507       double Score = getNormalizedScore(Function, RI1);
508       auto Iter = LTOMap1.find(&Function);
509       if (Iter == LTOMap1.end())
510         continue;
511       LTOAggregatedScore1[Iter->second] += Score;
512     }
513 
514     double UnmappedScore = 0;
515     for (const auto &BFI : RI2.BC->getBinaryFunctions()) {
516       const BinaryFunction &Function = BFI.second;
517       bool Matched = FuncMap.find(&Function) != FuncMap.end();
518       double Score = getNormalizedScore(Function, RI2);
519       auto Iter = LTOMap2.find(&Function);
520       if (Iter == LTOMap2.end()) {
521         if (!Matched)
522           UnmappedScore += Score;
523         continue;
524       }
525       LTOAggregatedScore2[Iter->second] += Score;
526       if (FuncMap.find(Iter->second) == FuncMap.end())
527         UnmappedScore += Score;
528     }
529     int64_t Unmapped =
530       RI2.BC->getBinaryFunctions().size() - Bin2MappedFuncs.size();
531     outs() << "BOLT-DIFF: " << Unmapped
532            << " functions in Binary2 have no correspondence to any other "
533               "function in Binary1.\n";
534 
535     // Print the hotness score of functions in binary 2 that were not matched
536     // to any function in binary 1
537     outs() << "BOLT-DIFF: These unmapped functions in Binary2 represent "
538            << format("%.2f", UnmappedScore * 100.0) << "% of execution.\n";
539   }
540 
541   /// Print the largest hotness differences from binary 2 to binary 1
542   void reportHottestFuncDiffs() {
543     std::multimap<double, decltype(FuncMap)::value_type> LargestDiffs;
544     for (const auto &MapEntry : FuncMap) {
545       const BinaryFunction *const &Func1 = MapEntry.second;
546       const BinaryFunction *const &Func2 = MapEntry.first;
547       double Score1 = getNormalizedScore(*Func1, RI1);
548       auto Iter1 = LTOMap1.find(Func1);
549       if (Iter1 != LTOMap1.end()) {
550         Score1 = LTOAggregatedScore1[Iter1->second];
551       }
552       double Score2 = getNormalizedScore(*Func2, RI2);
553       auto Iter2 = LTOMap2.find(Func2);
554       if (Iter2 != LTOMap2.end()) {
555         Score2 = LTOAggregatedScore2[Iter2->second];
556       }
557       if (Score1 == 0.0 || Score2 == 0.0)
558         continue;
559       LargestDiffs.insert(
560           std::make_pair<>(std::abs(Score1 - Score2), MapEntry));
561       ScoreMap[Func2] = std::make_pair<>(Score1, Score2);
562     }
563 
564     unsigned Printed = 0;
565     setTitleColor();
566     outs() << "\nTop " << opts::DisplayCount
567            << " largest differences in performance bin 2 -> bin 1:\n";
568     outs() << "=========================================================\n";
569     setRegularColor();
570     for (auto I = LargestDiffs.rbegin(), E = LargestDiffs.rend(); I != E; ++I) {
571       const std::pair<const BinaryFunction *const, const BinaryFunction *>
572           &MapEntry = I->second;
573       if (opts::IgnoreUnchanged &&
574           MapEntry.second->computeHash(/*UseDFS=*/true) ==
575           MapEntry.first->computeHash(/*UseDFS=*/true))
576         continue;
577       const std::pair<double, double> &Scores = ScoreMap[MapEntry.first];
578       outs() << "Function " << MapEntry.first->getDemangledName();
579       if (MapEntry.first->getDemangledName() !=
580           MapEntry.second->getDemangledName())
581         outs() << "\nmatched  " << MapEntry.second->getDemangledName();
582       outs() << "\n\tScore bin1 = " << format("%.2f", Scores.first * 100.0)
583              << "%\n\tScore bin2 = " << format("%.2f", Scores.second * 100.0)
584              << "%\t(Difference: ";
585       printColoredPercentage((Scores.second - Scores.first) * 100.0);
586       outs() << ")";
587       if (MapEntry.second->computeHash(/*UseDFS=*/true) !=
588           MapEntry.first->computeHash(/*UseDFS=*/true)) {
589         outs() << "\t[Functions have different contents]";
590         if (opts::PrintDiffCFG) {
591           outs() << "\n *** CFG for function in binary 1:\n";
592           setLightColor();
593           MapEntry.second->dump();
594           setRegularColor();
595           outs() << "\n *** CFG for function in binary 2:\n";
596           setLightColor();
597           MapEntry.first->dump();
598           setRegularColor();
599         }
600       }
601       outs() << "\n";
602       if (Printed++ == opts::DisplayCount)
603         break;
604     }
605   }
606 
607   /// Print hottest functions from each binary
608   void reportHottestFuncs() {
609     unsigned Printed = 0;
610     setTitleColor();
611     outs() << "\nTop " << opts::DisplayCount
612            << " hottest functions in binary 2:\n";
613     outs() << "=====================================\n";
614     setRegularColor();
615     for (auto I = LargestBin2.rbegin(), E = LargestBin2.rend(); I != E; ++I) {
616       const std::pair<const double, const BinaryFunction *> &MapEntry = *I;
617       outs() << "Function " << MapEntry.second->getDemangledName() << "\n";
618       auto Iter = ScoreMap.find(MapEntry.second);
619       if (Iter != ScoreMap.end()) {
620         outs() << "\tScore bin1 = "
621                << format("%.2f", Iter->second.first * 100.0) << "%\n";
622       }
623       outs() << "\tScore bin2 = " << format("%.2f", MapEntry.first * 100.0)
624              << "%\n";
625       if (Printed++ == opts::DisplayCount)
626         break;
627     }
628 
629     Printed = 0;
630     setTitleColor();
631     outs() << "\nTop " << opts::DisplayCount
632            << " hottest functions in binary 1:\n";
633     outs() << "=====================================\n";
634     setRegularColor();
635     for (auto I = LargestBin1.rbegin(), E = LargestBin1.rend(); I != E; ++I) {
636       const std::pair<const double, const BinaryFunction *> &MapEntry = *I;
637       outs() << "Function " << MapEntry.second->getDemangledName()
638              << "\n\tScore bin1 = " << format("%.2f", MapEntry.first * 100.0)
639              << "%\n";
640       if (Printed++ == opts::DisplayCount)
641         break;
642     }
643   }
644 
645   /// Print functions in binary 2 that did not match anything in binary 1.
646   /// Unfortunately, in an LTO build, even a small change can lead to several
647   /// LTO variants being unmapped, corresponding to local functions that never
648   /// appear in one of the binaries because they were previously inlined.
649   void reportUnmapped() {
650     outs() << "List of functions from binary 2 that were not matched with any "
651            << "function in binary 1:\n";
652     for (const auto &BFI2 : RI2.BC->getBinaryFunctions()) {
653       const BinaryFunction &Function2 = BFI2.second;
654       if (Bin2MappedFuncs.count(&Function2))
655         continue;
656       outs() << Function2.getPrintName() << "\n";
657     }
658   }
659 
660 public:
661   /// Main entry point: coordinate all tasks necessary to compare two binaries
662   void compareAndReport() {
663     buildLookupMaps();
664     matchFunctions();
665     if (opts::IgnoreLTOSuffix)
666       computeAggregatedLTOScore();
667     matchBasicBlocks();
668     reportHottestFuncDiffs();
669     reportHottestBBDiffs();
670     reportHottestEdgeDiffs();
671     reportHottestFuncs();
672     if (!opts::PrintUnmapped)
673       return;
674     reportUnmapped();
675   }
676 
677   RewriteInstanceDiff(RewriteInstance &RI1, RewriteInstance &RI2)
678       : RI1(RI1), RI2(RI2) {
679     compareAndReport();
680   }
681 
682 };
683 
684 } // end nampespace bolt
685 } // end namespace llvm
686 
687 void RewriteInstance::compare(RewriteInstance &RI2) {
688   outs() << "BOLT-DIFF: ======== Binary1 vs. Binary2 ========\n";
689   outs() << "Trace for binary 1 has " << this->getTotalScore()
690          << " instructions executed.\n";
691   outs() << "Trace for binary 2 has " << RI2.getTotalScore()
692          << " instructions executed.\n";
693   if (opts::NormalizeByBin1) {
694     double Diff2to1 = static_cast<double>(RI2.getTotalScore() - this->getTotalScore()) /
695                        this->getTotalScore();
696     outs() << "Binary2 change in score with respect to Binary1: ";
697     printColoredPercentage(Diff2to1 * 100.0);
698     outs() << "\n";
699   }
700 
701   if (!this->getTotalScore() || !RI2.getTotalScore()) {
702     outs() << "BOLT-DIFF: Both binaries must have recorded activity in known "
703               "functions.\n";
704     return;
705   }
706 
707   // Pre-pass ICF
708   if (opts::ICF) {
709     IdenticalCodeFolding ICF(opts::NeverPrint);
710     outs() << "BOLT-DIFF: Starting ICF pass for binary 1";
711     ICF.runOnFunctions(*BC);
712     outs() << "BOLT-DIFF: Starting ICF pass for binary 2";
713     ICF.runOnFunctions(*RI2.BC);
714   }
715 
716   RewriteInstanceDiff RID(*this, RI2);
717 }
718