bolt/lib/Rewrite/BoltDiff.cpp

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