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(Val: 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(Val: 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(Color: raw_ostream::RED); |
104 | else if (outs().has_colors() && Perc < 0.0) |
105 | outs().changeColor(Color: raw_ostream::GREEN); |
106 | else if (outs().has_colors()) |
107 | outs().changeColor(Color: raw_ostream::YELLOW); |
108 | outs() << format(Fmt: "%.2f", Vals: Perc) << "%"; |
109 | if (outs().has_colors()) |
110 | outs().resetColor(); |
111 | } |
112 | |
113 | void setLightColor() { |
114 | if (opts::PrintDiffBBs && outs().has_colors()) |
115 | outs().changeColor(Color: raw_ostream::CYAN); |
116 | } |
117 | |
118 | void setTitleColor() { |
119 | if (outs().has_colors()) |
120 | outs().changeColor(Color: 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, Ctx: RI1); |
212 | LargestBin1.insert(x: std::make_pair<>(x: Score, y: &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(Key: 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, Ctx: RI2); |
232 | LargestBin2.insert(x: std::make_pair<>(x: Score, y: &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(Key: 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(Key: Name); |
257 | if (std::optional<StringRef> OptionalLTOName = getLTOCommonName(Name)) |
258 | LTOName = *OptionalLTOName; |
259 | if (Iter == NameLookup.end()) |
260 | continue; |
261 | FuncMap.insert(x: std::make_pair<>(x: &Function2, y&: Iter->second)); |
262 | Bin1MappedFuncs.insert(x: Iter->second); |
263 | Bin2MappedFuncs.insert(x: &Function2); |
264 | if (Function2.hasValidProfile() && Iter->second->hasValidProfile()) { |
265 | ++BothHaveProfile; |
266 | Bin1ProfiledMapped.insert(x: Iter->second); |
267 | } |
268 | Match = true; |
269 | break; |
270 | } |
271 | if (Match || !Function2.hasCFG()) |
272 | continue; |
273 | auto Iter = HashLookup.find(Val: Function2.computeHash(/*UseDFS*/ true)); |
274 | if (Iter != HashLookup.end()) { |
275 | FuncMap.insert(x: std::make_pair<>(x: &Function2, y&: Iter->second)); |
276 | Bin1MappedFuncs.insert(x: Iter->second); |
277 | Bin2MappedFuncs.insert(x: &Function2); |
278 | if (Function2.hasValidProfile() && Iter->second->hasValidProfile()) { |
279 | ++BothHaveProfile; |
280 | Bin1ProfiledMapped.insert(x: Iter->second); |
281 | } |
282 | continue; |
283 | } |
284 | if (LTOName.empty()) |
285 | continue; |
286 | auto LTOIter = LTONameLookup1.find(Key: LTOName); |
287 | if (LTOIter != LTONameLookup1.end()) { |
288 | FuncMap.insert(x: std::make_pair<>(x: &Function2, y&: LTOIter->second)); |
289 | Bin1MappedFuncs.insert(x: LTOIter->second); |
290 | Bin2MappedFuncs.insert(x: &Function2); |
291 | if (Function2.hasValidProfile() && LTOIter->second->hasValidProfile()) { |
292 | ++BothHaveProfile; |
293 | Bin1ProfiledMapped.insert(x: 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(E: PPS.runOnFunctions(BC&: *RI1.BC)); |
300 | outs() << "* BOLT-DIFF: Starting print program stats pass for binary 2\n"; |
301 | RI1.BC->logBOLTErrorsAndQuitOnFatal(E: PPS.runOnFunctions(BC&: *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(x: &Function)) |
311 | continue; |
312 | Unmapped.emplace_back(args: &Function); |
313 | } |
314 | llvm::sort(C&: Unmapped, |
315 | Comp: [&](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(BB1: **Iter1, BB2: **Iter2)) { |
368 | Match = false; |
369 | break; |
370 | } |
371 | Map.insert(x: std::make_pair<>(x: *Iter2, y: *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(BIIter: BIIter1, Ctx: RI1); |
383 | const double ScoreEdge2 = getNormalizedScore(BIIter: BIIter2, Ctx: RI2); |
384 | EMap.insert(x: std::make_pair<>( |
385 | x: std::abs(x: ScoreEdge2 - ScoreEdge1), |
386 | y: std::make_pair<>( |
387 | x: std::make_tuple<>(args: *Iter2, args&: *SuccIter2, args: ScoreEdge2), |
388 | y: std::make_tuple<>(args: *Iter1, args&: *SuccIter1, args: 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(first: Map.begin(), last: Map.end()); |
409 | EdgeMap.insert(first: EMap.begin(), last: 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 | x: std::make_pair<>(x: std::abs(x: getNormalizedScore(BB: *BB2, Ctx: RI2) - |
422 | getNormalizedScore(BB: *BB1, Ctx: RI1)), |
423 | y&: 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(c: llvm::reverse(C&: LargestDiffs))) { |
436 | const double Score2 = getNormalizedScore(BB: *BB2, Ctx: RI2); |
437 | const double Score1 = getNormalizedScore(BB: *BBMap[BB2], Ctx: 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(Fmt: "%.4f", Vals: Score1 * 100.0) |
443 | << "%\n\tScore bin2 = "<< format(Fmt: "%.4f", Vals: Score2 * 100.0); |
444 | outs() << "%\t(Difference: "; |
445 | printColoredPercentage(Perc: (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(c: llvm::reverse(C&: EdgeMap))) { |
468 | EdgeTy &Edge2 = EI.first; |
469 | EdgeTy &Edge1 = EI.second; |
470 | const double Score2 = std::get<2>(t&: Edge2); |
471 | const double Score1 = std::get<2>(t&: Edge1); |
472 | const BinaryFunction *Func = BBToFuncMap[std::get<0>(t&: Edge2)]; |
473 | if (opts::SkipNonSimple && !Func->isSimple()) |
474 | continue; |
475 | outs() << "Edge ("<< std::get<0>(t&: Edge2)->getName() << " -> " |
476 | << std::get<1>(t&: Edge2)->getName() << ") in " |
477 | << Func->getDemangledName() |
478 | << "\n\tScore bin1 = "<< format(Fmt: "%.4f", Vals: Score1 * 100.0) |
479 | << "%\n\tScore bin2 = "<< format(Fmt: "%.4f", Vals: Score2 * 100.0); |
480 | outs() << "%\t(Difference: "; |
481 | printColoredPercentage(Perc: (Score2 - Score1) * 100.0); |
482 | outs() << ")\n"; |
483 | if (opts::PrintDiffBBs) { |
484 | setLightColor(); |
485 | std::get<0>(t&: Edge2)->dump(); |
486 | std::get<1>(t&: 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, Ctx: RI1); |
503 | auto Iter = LTOMap1.find(x: &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(x: &Function) != FuncMap.end(); |
513 | double Score = getNormalizedScore(Function, Ctx: RI2); |
514 | auto Iter = LTOMap2.find(x: &Function); |
515 | if (Iter == LTOMap2.end()) { |
516 | if (!Matched) |
517 | UnmappedScore += Score; |
518 | continue; |
519 | } |
520 | LTOAggregatedScore2[Iter->second] += Score; |
521 | if (FuncMap.find(x: 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(Fmt: "%.2f", Vals: 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(Function: *Func1, Ctx: RI1); |
543 | auto Iter1 = LTOMap1.find(x: Func1); |
544 | if (Iter1 != LTOMap1.end()) |
545 | Score1 = LTOAggregatedScore1[Iter1->second]; |
546 | double Score2 = getNormalizedScore(Function: *Func2, Ctx: RI2); |
547 | auto Iter2 = LTOMap2.find(x: 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 | x: std::make_pair<>(x: std::abs(x: Score1 - Score2), y: MapEntry)); |
556 | ScoreMap[Func2] = std::make_pair<>(x&: Score1, y&: 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(c: llvm::reverse(C&: 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(Fmt: "%.2f", Vals: Scores.first * 100.0) |
577 | << "%\n\tScore bin2 = "<< format(Fmt: "%.2f", Vals: Scores.second * 100.0) |
578 | << "%\t(Difference: "; |
579 | printColoredPercentage(Perc: (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(C&: LargestBin2)) { |
611 | outs() << "Function "<< MapEntry.second->getDemangledName() << "\n"; |
612 | auto Iter = ScoreMap.find(Val: MapEntry.second); |
613 | if (Iter != ScoreMap.end()) |
614 | outs() << "\tScore bin1 = " |
615 | << format(Fmt: "%.2f", Vals: Iter->second.first * 100.0) << "%\n"; |
616 | outs() << "\tScore bin2 = "<< format(Fmt: "%.2f", Vals: 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(C&: LargestBin1)) { |
630 | outs() << "Function "<< MapEntry.second->getDemangledName() |
631 | << "\n\tScore bin1 = "<< format(Fmt: "%.2f", Vals: 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(x: &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(Perc: 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(E: ICF.runOnFunctions(BC&: *BC)); |
706 | outs() << "BOLT-DIFF: Starting ICF pass for binary 2"; |
707 | BC->logBOLTErrorsAndQuitOnFatal(E: ICF.runOnFunctions(BC&: *RI2.BC)); |
708 | } |
709 | |
710 | RewriteInstanceDiff RID(*this, RI2); |
711 | } |
712 |
Definitions
- IgnoreLTOSuffix
- PrintUnmapped
- PrintProfiledUnmapped
- PrintDiffCFG
- PrintDiffBBs
- MatchByHash
- IgnoreUnchanged
- DisplayCount
- NormalizeByBin1
- SkipNonSimple
- printColoredPercentage
- setLightColor
- setTitleColor
- setRegularColor
- RewriteInstanceDiff
- getNormalizedScore
- getNormalizedScore
- getNormalizedScore
- buildLookupMaps
- matchFunctions
- compareBBs
- matchBasicBlocks
- reportHottestBBDiffs
- reportHottestEdgeDiffs
- computeAggregatedLTOScore
- reportHottestFuncDiffs
- reportHottestFuncs
- reportUnmapped
- compareAndReport
- RewriteInstanceDiff
Update your C++ knowledge – Modern C++11/14/17 Training
Find out more