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