1 //===- bolt/Profile/YAMLProfileReader.cpp - YAML profile de-serializer ----===//
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 #include "bolt/Profile/YAMLProfileReader.h"
10 #include "bolt/Core/BinaryBasicBlock.h"
11 #include "bolt/Core/BinaryFunction.h"
12 #include "bolt/Passes/MCF.h"
13 #include "bolt/Profile/ProfileYAMLMapping.h"
14 #include "bolt/Utils/Utils.h"
15 #include "llvm/Support/CommandLine.h"
16 
17 using namespace llvm;
18 
19 namespace opts {
20 
21 extern cl::opt<unsigned> Verbosity;
22 extern cl::OptionCategory BoltOptCategory;
23 
24 static llvm::cl::opt<bool>
25     IgnoreHash("profile-ignore-hash",
26                cl::desc("ignore hash while reading function profile"),
27                cl::Hidden, cl::cat(BoltOptCategory));
28 }
29 
30 namespace llvm {
31 namespace bolt {
32 
isYAML(const StringRef Filename)33 bool YAMLProfileReader::isYAML(const StringRef Filename) {
34   ErrorOr<std::unique_ptr<MemoryBuffer>> MB =
35       MemoryBuffer::getFileOrSTDIN(Filename);
36   if (std::error_code EC = MB.getError())
37     report_error(Filename, EC);
38   StringRef Buffer = MB.get()->getBuffer();
39   if (Buffer.startswith("---\n"))
40     return true;
41   return false;
42 }
43 
buildNameMaps(std::map<uint64_t,BinaryFunction> & Functions)44 void YAMLProfileReader::buildNameMaps(
45     std::map<uint64_t, BinaryFunction> &Functions) {
46   for (yaml::bolt::BinaryFunctionProfile &YamlBF : YamlBP.Functions) {
47     StringRef Name = YamlBF.Name;
48     const size_t Pos = Name.find("(*");
49     if (Pos != StringRef::npos)
50       Name = Name.substr(0, Pos);
51     ProfileNameToProfile[Name] = &YamlBF;
52     if (const Optional<StringRef> CommonName = getLTOCommonName(Name))
53       LTOCommonNameMap[*CommonName].push_back(&YamlBF);
54   }
55   for (auto &BFI : Functions) {
56     const BinaryFunction &Function = BFI.second;
57     for (StringRef Name : Function.getNames())
58       if (const Optional<StringRef> CommonName = getLTOCommonName(Name))
59         LTOCommonNameFunctionMap[*CommonName].insert(&Function);
60   }
61 }
62 
hasLocalsWithFileName() const63 bool YAMLProfileReader::hasLocalsWithFileName() const {
64   for (const StringMapEntry<yaml::bolt::BinaryFunctionProfile *> &KV :
65        ProfileNameToProfile) {
66     const StringRef &FuncName = KV.getKey();
67     if (FuncName.count('/') == 2 && FuncName[0] != '/')
68       return true;
69   }
70   return false;
71 }
72 
parseFunctionProfile(BinaryFunction & BF,const yaml::bolt::BinaryFunctionProfile & YamlBF)73 bool YAMLProfileReader::parseFunctionProfile(
74     BinaryFunction &BF, const yaml::bolt::BinaryFunctionProfile &YamlBF) {
75   BinaryContext &BC = BF.getBinaryContext();
76 
77   bool ProfileMatched = true;
78   uint64_t MismatchedBlocks = 0;
79   uint64_t MismatchedCalls = 0;
80   uint64_t MismatchedEdges = 0;
81 
82   uint64_t FunctionExecutionCount = 0;
83 
84   BF.setExecutionCount(YamlBF.ExecCount);
85 
86   if (!opts::IgnoreHash && YamlBF.Hash != BF.computeHash(/*UseDFS=*/true)) {
87     if (opts::Verbosity >= 1)
88       errs() << "BOLT-WARNING: function hash mismatch\n";
89     ProfileMatched = false;
90   }
91 
92   if (YamlBF.NumBasicBlocks != BF.size()) {
93     if (opts::Verbosity >= 1)
94       errs() << "BOLT-WARNING: number of basic blocks mismatch\n";
95     ProfileMatched = false;
96   }
97 
98   BinaryFunction::BasicBlockOrderType DFSOrder = BF.dfs();
99 
100   for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF.Blocks) {
101     if (YamlBB.Index >= DFSOrder.size()) {
102       if (opts::Verbosity >= 2)
103         errs() << "BOLT-WARNING: index " << YamlBB.Index
104                << " is out of bounds\n";
105       ++MismatchedBlocks;
106       continue;
107     }
108 
109     BinaryBasicBlock &BB = *DFSOrder[YamlBB.Index];
110 
111     // Basic samples profile (without LBR) does not have branches information
112     // and needs a special processing.
113     if (YamlBP.Header.Flags & BinaryFunction::PF_SAMPLE) {
114       if (!YamlBB.EventCount) {
115         BB.setExecutionCount(0);
116         continue;
117       }
118       uint64_t NumSamples = YamlBB.EventCount * 1000;
119       if (NormalizeByInsnCount && BB.getNumNonPseudos())
120         NumSamples /= BB.getNumNonPseudos();
121       else if (NormalizeByCalls)
122         NumSamples /= BB.getNumCalls() + 1;
123 
124       BB.setExecutionCount(NumSamples);
125       if (BB.isEntryPoint())
126         FunctionExecutionCount += NumSamples;
127       continue;
128     }
129 
130     BB.setExecutionCount(YamlBB.ExecCount);
131 
132     for (const yaml::bolt::CallSiteInfo &YamlCSI : YamlBB.CallSites) {
133       BinaryFunction *Callee = YamlCSI.DestId < YamlProfileToFunction.size()
134                                    ? YamlProfileToFunction[YamlCSI.DestId]
135                                    : nullptr;
136       bool IsFunction = Callee ? true : false;
137       MCSymbol *CalleeSymbol = nullptr;
138       if (IsFunction)
139         CalleeSymbol = Callee->getSymbolForEntryID(YamlCSI.EntryDiscriminator);
140 
141       BF.getAllCallSites().emplace_back(CalleeSymbol, YamlCSI.Count,
142                                         YamlCSI.Mispreds, YamlCSI.Offset);
143 
144       if (YamlCSI.Offset >= BB.getOriginalSize()) {
145         if (opts::Verbosity >= 2)
146           errs() << "BOLT-WARNING: offset " << YamlCSI.Offset
147                  << " out of bounds in block " << BB.getName() << '\n';
148         ++MismatchedCalls;
149         continue;
150       }
151 
152       MCInst *Instr =
153           BF.getInstructionAtOffset(BB.getInputOffset() + YamlCSI.Offset);
154       if (!Instr) {
155         if (opts::Verbosity >= 2)
156           errs() << "BOLT-WARNING: no instruction at offset " << YamlCSI.Offset
157                  << " in block " << BB.getName() << '\n';
158         ++MismatchedCalls;
159         continue;
160       }
161       if (!BC.MIB->isCall(*Instr) && !BC.MIB->isIndirectBranch(*Instr)) {
162         if (opts::Verbosity >= 2)
163           errs() << "BOLT-WARNING: expected call at offset " << YamlCSI.Offset
164                  << " in block " << BB.getName() << '\n';
165         ++MismatchedCalls;
166         continue;
167       }
168 
169       auto setAnnotation = [&](StringRef Name, uint64_t Count) {
170         if (BC.MIB->hasAnnotation(*Instr, Name)) {
171           if (opts::Verbosity >= 1)
172             errs() << "BOLT-WARNING: ignoring duplicate " << Name
173                    << " info for offset 0x" << Twine::utohexstr(YamlCSI.Offset)
174                    << " in function " << BF << '\n';
175           return;
176         }
177         BC.MIB->addAnnotation(*Instr, Name, Count);
178       };
179 
180       if (BC.MIB->isIndirectCall(*Instr) || BC.MIB->isIndirectBranch(*Instr)) {
181         auto &CSP = BC.MIB->getOrCreateAnnotationAs<IndirectCallSiteProfile>(
182             *Instr, "CallProfile");
183         CSP.emplace_back(CalleeSymbol, YamlCSI.Count, YamlCSI.Mispreds);
184       } else if (BC.MIB->getConditionalTailCall(*Instr)) {
185         setAnnotation("CTCTakenCount", YamlCSI.Count);
186         setAnnotation("CTCMispredCount", YamlCSI.Mispreds);
187       } else {
188         setAnnotation("Count", YamlCSI.Count);
189       }
190     }
191 
192     for (const yaml::bolt::SuccessorInfo &YamlSI : YamlBB.Successors) {
193       if (YamlSI.Index >= DFSOrder.size()) {
194         if (opts::Verbosity >= 1)
195           errs() << "BOLT-WARNING: index out of bounds for profiled block\n";
196         ++MismatchedEdges;
197         continue;
198       }
199 
200       BinaryBasicBlock &SuccessorBB = *DFSOrder[YamlSI.Index];
201       if (!BB.getSuccessor(SuccessorBB.getLabel())) {
202         if (opts::Verbosity >= 1)
203           errs() << "BOLT-WARNING: no successor for block " << BB.getName()
204                  << " that matches index " << YamlSI.Index << " or block "
205                  << SuccessorBB.getName() << '\n';
206         ++MismatchedEdges;
207         continue;
208       }
209 
210       BinaryBasicBlock::BinaryBranchInfo &BI = BB.getBranchInfo(SuccessorBB);
211       BI.Count += YamlSI.Count;
212       BI.MispredictedCount += YamlSI.Mispreds;
213     }
214   }
215 
216   // If basic block profile wasn't read it should be 0.
217   for (BinaryBasicBlock &BB : BF)
218     if (BB.getExecutionCount() == BinaryBasicBlock::COUNT_NO_PROFILE)
219       BB.setExecutionCount(0);
220 
221   if (YamlBP.Header.Flags & BinaryFunction::PF_SAMPLE) {
222     BF.setExecutionCount(FunctionExecutionCount);
223     estimateEdgeCounts(BF);
224   }
225 
226   ProfileMatched &= !MismatchedBlocks && !MismatchedCalls && !MismatchedEdges;
227 
228   if (ProfileMatched)
229     BF.markProfiled(YamlBP.Header.Flags);
230 
231   if (!ProfileMatched && opts::Verbosity >= 1)
232     errs() << "BOLT-WARNING: " << MismatchedBlocks << " blocks, "
233            << MismatchedCalls << " calls, and " << MismatchedEdges
234            << " edges in profile did not match function " << BF << '\n';
235 
236   return ProfileMatched;
237 }
238 
preprocessProfile(BinaryContext & BC)239 Error YAMLProfileReader::preprocessProfile(BinaryContext &BC) {
240   ErrorOr<std::unique_ptr<MemoryBuffer>> MB =
241       MemoryBuffer::getFileOrSTDIN(Filename);
242   if (std::error_code EC = MB.getError()) {
243     errs() << "ERROR: cannot open " << Filename << ": " << EC.message() << "\n";
244     return errorCodeToError(EC);
245   }
246   yaml::Input YamlInput(MB.get()->getBuffer());
247 
248   // Consume YAML file.
249   YamlInput >> YamlBP;
250   if (YamlInput.error()) {
251     errs() << "BOLT-ERROR: syntax error parsing profile in " << Filename
252            << " : " << YamlInput.error().message() << '\n';
253     return errorCodeToError(YamlInput.error());
254   }
255 
256   // Sanity check.
257   if (YamlBP.Header.Version != 1)
258     return make_error<StringError>(
259         Twine("cannot read profile : unsupported version"),
260         inconvertibleErrorCode());
261 
262   if (YamlBP.Header.EventNames.find(',') != StringRef::npos)
263     return make_error<StringError>(
264         Twine("multiple events in profile are not supported"),
265         inconvertibleErrorCode());
266 
267   // Match profile to function based on a function name.
268   buildNameMaps(BC.getBinaryFunctions());
269 
270   // Preliminary assign function execution count.
271   for (auto &KV : BC.getBinaryFunctions()) {
272     BinaryFunction &BF = KV.second;
273     for (StringRef Name : BF.getNames()) {
274       auto PI = ProfileNameToProfile.find(Name);
275       if (PI != ProfileNameToProfile.end()) {
276         yaml::bolt::BinaryFunctionProfile &YamlBF = *PI->getValue();
277         BF.setExecutionCount(YamlBF.ExecCount);
278         break;
279       }
280     }
281   }
282 
283   return Error::success();
284 }
285 
mayHaveProfileData(const BinaryFunction & BF)286 bool YAMLProfileReader::mayHaveProfileData(const BinaryFunction &BF) {
287   for (StringRef Name : BF.getNames()) {
288     if (ProfileNameToProfile.find(Name) != ProfileNameToProfile.end())
289       return true;
290     if (const Optional<StringRef> CommonName = getLTOCommonName(Name)) {
291       if (LTOCommonNameMap.find(*CommonName) != LTOCommonNameMap.end())
292         return true;
293     }
294   }
295 
296   return false;
297 }
298 
readProfile(BinaryContext & BC)299 Error YAMLProfileReader::readProfile(BinaryContext &BC) {
300   YamlProfileToFunction.resize(YamlBP.Functions.size() + 1);
301 
302   auto profileMatches = [](const yaml::bolt::BinaryFunctionProfile &Profile,
303                            BinaryFunction &BF) {
304     if (opts::IgnoreHash && Profile.NumBasicBlocks == BF.size())
305       return true;
306     if (!opts::IgnoreHash &&
307         Profile.Hash == static_cast<uint64_t>(BF.getHash()))
308       return true;
309     return false;
310   };
311 
312   // We have to do 2 passes since LTO introduces an ambiguity in function
313   // names. The first pass assigns profiles that match 100% by name and
314   // by hash. The second pass allows name ambiguity for LTO private functions.
315   for (auto &BFI : BC.getBinaryFunctions()) {
316     BinaryFunction &Function = BFI.second;
317 
318     // Clear function call count that may have been set while pre-processing
319     // the profile.
320     Function.setExecutionCount(BinaryFunction::COUNT_NO_PROFILE);
321 
322     // Recompute hash once per function.
323     if (!opts::IgnoreHash)
324       Function.computeHash(/*UseDFS=*/true);
325 
326     for (StringRef FunctionName : Function.getNames()) {
327       auto PI = ProfileNameToProfile.find(FunctionName);
328       if (PI == ProfileNameToProfile.end())
329         continue;
330 
331       yaml::bolt::BinaryFunctionProfile &YamlBF = *PI->getValue();
332       if (profileMatches(YamlBF, Function))
333         matchProfileToFunction(YamlBF, Function);
334     }
335   }
336 
337   for (auto &BFI : BC.getBinaryFunctions()) {
338     BinaryFunction &Function = BFI.second;
339 
340     if (ProfiledFunctions.count(&Function))
341       continue;
342 
343     for (StringRef FunctionName : Function.getNames()) {
344       const Optional<StringRef> CommonName = getLTOCommonName(FunctionName);
345       if (CommonName) {
346         auto I = LTOCommonNameMap.find(*CommonName);
347         if (I == LTOCommonNameMap.end())
348           continue;
349 
350         bool ProfileMatched = false;
351         std::vector<yaml::bolt::BinaryFunctionProfile *> &LTOProfiles =
352             I->getValue();
353         for (yaml::bolt::BinaryFunctionProfile *YamlBF : LTOProfiles) {
354           if (YamlBF->Used)
355             continue;
356           if ((ProfileMatched = profileMatches(*YamlBF, Function))) {
357             matchProfileToFunction(*YamlBF, Function);
358             break;
359           }
360         }
361         if (ProfileMatched)
362           break;
363 
364         // If there's only one function with a given name, try to
365         // match it partially.
366         if (LTOProfiles.size() == 1 &&
367             LTOCommonNameFunctionMap[*CommonName].size() == 1 &&
368             !LTOProfiles.front()->Used) {
369           matchProfileToFunction(*LTOProfiles.front(), Function);
370           break;
371         }
372       } else {
373         auto PI = ProfileNameToProfile.find(FunctionName);
374         if (PI == ProfileNameToProfile.end())
375           continue;
376 
377         yaml::bolt::BinaryFunctionProfile &YamlBF = *PI->getValue();
378         if (!YamlBF.Used) {
379           matchProfileToFunction(YamlBF, Function);
380           break;
381         }
382       }
383     }
384   }
385 
386   for (yaml::bolt::BinaryFunctionProfile &YamlBF : YamlBP.Functions)
387     if (!YamlBF.Used && opts::Verbosity >= 1)
388       errs() << "BOLT-WARNING: profile ignored for function " << YamlBF.Name
389              << '\n';
390 
391   // Set for parseFunctionProfile().
392   NormalizeByInsnCount = usesEvent("cycles") || usesEvent("instructions");
393   NormalizeByCalls = usesEvent("branches");
394 
395   uint64_t NumUnused = 0;
396   for (yaml::bolt::BinaryFunctionProfile &YamlBF : YamlBP.Functions) {
397     if (YamlBF.Id >= YamlProfileToFunction.size()) {
398       // Such profile was ignored.
399       ++NumUnused;
400       continue;
401     }
402     if (BinaryFunction *BF = YamlProfileToFunction[YamlBF.Id])
403       parseFunctionProfile(*BF, YamlBF);
404     else
405       ++NumUnused;
406   }
407 
408   BC.setNumUnusedProfiledObjects(NumUnused);
409 
410   return Error::success();
411 }
412 
usesEvent(StringRef Name) const413 bool YAMLProfileReader::usesEvent(StringRef Name) const {
414   return YamlBP.Header.EventNames.find(std::string(Name)) != StringRef::npos;
415 }
416 
417 } // end namespace bolt
418 } // end namespace llvm
419