1 //===-- InstrProfCorrelator.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 #include "llvm/ProfileData/InstrProfCorrelator.h"
10 #include "llvm/DebugInfo/DIContext.h"
11 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
12 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
13 #include "llvm/DebugInfo/DWARF/DWARFExpression.h"
14 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
15 #include "llvm/DebugInfo/DWARF/DWARFLocationExpression.h"
16 #include "llvm/DebugInfo/DWARF/DWARFUnit.h"
17 #include "llvm/Object/MachO.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/Format.h"
20 #include "llvm/Support/WithColor.h"
21 #include <optional>
22 
23 #define DEBUG_TYPE "correlator"
24 
25 using namespace llvm;
26 
27 /// Get profile section.
28 Expected<object::SectionRef> getInstrProfSection(const object::ObjectFile &Obj,
29                                                  InstrProfSectKind IPSK) {
30   // On COFF, the getInstrProfSectionName returns the section names may followed
31   // by "$M". The linker removes the dollar and everything after it in the final
32   // binary. Do the same to match.
33   Triple::ObjectFormatType ObjFormat = Obj.getTripleObjectFormat();
34   auto StripSuffix = [ObjFormat](StringRef N) {
35     return ObjFormat == Triple::COFF ? N.split('$').first : N;
36   };
37   std::string ExpectedSectionName =
38       getInstrProfSectionName(IPSK, ObjFormat,
39                               /*AddSegmentInfo=*/false);
40   ExpectedSectionName = StripSuffix(ExpectedSectionName);
41   for (auto &Section : Obj.sections()) {
42     if (auto SectionName = Section.getName())
43       if (*SectionName == ExpectedSectionName)
44         return Section;
45   }
46   return make_error<InstrProfError>(
47       instrprof_error::unable_to_correlate_profile,
48       "could not find section (" + Twine(ExpectedSectionName) + ")");
49 }
50 
51 const char *InstrProfCorrelator::FunctionNameAttributeName = "Function Name";
52 const char *InstrProfCorrelator::CFGHashAttributeName = "CFG Hash";
53 const char *InstrProfCorrelator::NumCountersAttributeName = "Num Counters";
54 
55 llvm::Expected<std::unique_ptr<InstrProfCorrelator::Context>>
56 InstrProfCorrelator::Context::get(std::unique_ptr<MemoryBuffer> Buffer,
57                                   const object::ObjectFile &Obj,
58                                   ProfCorrelatorKind FileKind) {
59   auto C = std::make_unique<Context>();
60   auto CountersSection = getInstrProfSection(Obj, IPSK_cnts);
61   if (auto Err = CountersSection.takeError())
62     return std::move(Err);
63   if (FileKind == InstrProfCorrelator::BINARY) {
64     auto DataSection = getInstrProfSection(Obj, IPSK_covdata);
65     if (auto Err = DataSection.takeError())
66       return std::move(Err);
67     auto DataOrErr = DataSection->getContents();
68     if (!DataOrErr)
69       return DataOrErr.takeError();
70     auto NameSection = getInstrProfSection(Obj, IPSK_covname);
71     if (auto Err = NameSection.takeError())
72       return std::move(Err);
73     auto NameOrErr = NameSection->getContents();
74     if (!NameOrErr)
75       return NameOrErr.takeError();
76     C->DataStart = DataOrErr->data();
77     C->DataEnd = DataOrErr->data() + DataOrErr->size();
78     C->NameStart = NameOrErr->data();
79     C->NameSize = NameOrErr->size();
80   }
81   C->Buffer = std::move(Buffer);
82   C->CountersSectionStart = CountersSection->getAddress();
83   C->CountersSectionEnd = C->CountersSectionStart + CountersSection->getSize();
84   // In COFF object file, there's a null byte at the beginning of the counter
85   // section which doesn't exist in raw profile.
86   if (Obj.getTripleObjectFormat() == Triple::COFF)
87     ++C->CountersSectionStart;
88 
89   C->ShouldSwapBytes = Obj.isLittleEndian() != sys::IsLittleEndianHost;
90   return Expected<std::unique_ptr<Context>>(std::move(C));
91 }
92 
93 llvm::Expected<std::unique_ptr<InstrProfCorrelator>>
94 InstrProfCorrelator::get(StringRef Filename, ProfCorrelatorKind FileKind) {
95   if (FileKind == DEBUG_INFO) {
96     auto DsymObjectsOrErr =
97         object::MachOObjectFile::findDsymObjectMembers(Filename);
98     if (auto Err = DsymObjectsOrErr.takeError())
99       return std::move(Err);
100     if (!DsymObjectsOrErr->empty()) {
101       // TODO: Enable profile correlation when there are multiple objects in a
102       // dSYM bundle.
103       if (DsymObjectsOrErr->size() > 1)
104         return make_error<InstrProfError>(
105             instrprof_error::unable_to_correlate_profile,
106             "using multiple objects is not yet supported");
107       Filename = *DsymObjectsOrErr->begin();
108     }
109     auto BufferOrErr = errorOrToExpected(MemoryBuffer::getFile(Filename));
110     if (auto Err = BufferOrErr.takeError())
111       return std::move(Err);
112 
113     return get(std::move(*BufferOrErr), FileKind);
114   }
115   if (FileKind == BINARY) {
116     auto BufferOrErr = errorOrToExpected(MemoryBuffer::getFile(Filename));
117     if (auto Err = BufferOrErr.takeError())
118       return std::move(Err);
119 
120     return get(std::move(*BufferOrErr), FileKind);
121   }
122   return make_error<InstrProfError>(
123       instrprof_error::unable_to_correlate_profile,
124       "unsupported correlation kind (only DWARF debug info and Binary format "
125       "(ELF/COFF) are supported)");
126 }
127 
128 llvm::Expected<std::unique_ptr<InstrProfCorrelator>>
129 InstrProfCorrelator::get(std::unique_ptr<MemoryBuffer> Buffer,
130                          ProfCorrelatorKind FileKind) {
131   auto BinOrErr = object::createBinary(*Buffer);
132   if (auto Err = BinOrErr.takeError())
133     return std::move(Err);
134 
135   if (auto *Obj = dyn_cast<object::ObjectFile>(BinOrErr->get())) {
136     auto CtxOrErr = Context::get(std::move(Buffer), *Obj, FileKind);
137     if (auto Err = CtxOrErr.takeError())
138       return std::move(Err);
139     auto T = Obj->makeTriple();
140     if (T.isArch64Bit())
141       return InstrProfCorrelatorImpl<uint64_t>::get(std::move(*CtxOrErr), *Obj,
142                                                     FileKind);
143     if (T.isArch32Bit())
144       return InstrProfCorrelatorImpl<uint32_t>::get(std::move(*CtxOrErr), *Obj,
145                                                     FileKind);
146   }
147   return make_error<InstrProfError>(
148       instrprof_error::unable_to_correlate_profile, "not an object file");
149 }
150 
151 std::optional<size_t> InstrProfCorrelator::getDataSize() const {
152   if (auto *C = dyn_cast<InstrProfCorrelatorImpl<uint32_t>>(this)) {
153     return C->getDataSize();
154   } else if (auto *C = dyn_cast<InstrProfCorrelatorImpl<uint64_t>>(this)) {
155     return C->getDataSize();
156   }
157   return {};
158 }
159 
160 namespace llvm {
161 
162 template <>
163 InstrProfCorrelatorImpl<uint32_t>::InstrProfCorrelatorImpl(
164     std::unique_ptr<InstrProfCorrelator::Context> Ctx)
165     : InstrProfCorrelatorImpl(InstrProfCorrelatorKind::CK_32Bit,
166                               std::move(Ctx)) {}
167 template <>
168 InstrProfCorrelatorImpl<uint64_t>::InstrProfCorrelatorImpl(
169     std::unique_ptr<InstrProfCorrelator::Context> Ctx)
170     : InstrProfCorrelatorImpl(InstrProfCorrelatorKind::CK_64Bit,
171                               std::move(Ctx)) {}
172 template <>
173 bool InstrProfCorrelatorImpl<uint32_t>::classof(const InstrProfCorrelator *C) {
174   return C->getKind() == InstrProfCorrelatorKind::CK_32Bit;
175 }
176 template <>
177 bool InstrProfCorrelatorImpl<uint64_t>::classof(const InstrProfCorrelator *C) {
178   return C->getKind() == InstrProfCorrelatorKind::CK_64Bit;
179 }
180 
181 } // end namespace llvm
182 
183 template <class IntPtrT>
184 llvm::Expected<std::unique_ptr<InstrProfCorrelatorImpl<IntPtrT>>>
185 InstrProfCorrelatorImpl<IntPtrT>::get(
186     std::unique_ptr<InstrProfCorrelator::Context> Ctx,
187     const object::ObjectFile &Obj, ProfCorrelatorKind FileKind) {
188   if (FileKind == DEBUG_INFO) {
189     if (Obj.isELF() || Obj.isMachO()) {
190       auto DICtx = DWARFContext::create(Obj);
191       return std::make_unique<DwarfInstrProfCorrelator<IntPtrT>>(
192           std::move(DICtx), std::move(Ctx));
193     }
194     return make_error<InstrProfError>(
195         instrprof_error::unable_to_correlate_profile,
196         "unsupported debug info format (only DWARF is supported)");
197   }
198   if (Obj.isELF() || Obj.isCOFF())
199     return std::make_unique<BinaryInstrProfCorrelator<IntPtrT>>(std::move(Ctx));
200   return make_error<InstrProfError>(
201       instrprof_error::unable_to_correlate_profile,
202       "unsupported binary format (only ELF and COFF are supported)");
203 }
204 
205 template <class IntPtrT>
206 Error InstrProfCorrelatorImpl<IntPtrT>::correlateProfileData(int MaxWarnings) {
207   assert(Data.empty() && Names.empty() && NamesVec.empty());
208   correlateProfileDataImpl(MaxWarnings);
209   if (this->Data.empty())
210     return make_error<InstrProfError>(
211         instrprof_error::unable_to_correlate_profile,
212         "could not find any profile data metadata in correlated file");
213   Error Result = correlateProfileNameImpl();
214   this->CounterOffsets.clear();
215   this->NamesVec.clear();
216   return Result;
217 }
218 
219 template <> struct yaml::MappingTraits<InstrProfCorrelator::CorrelationData> {
220   static void mapping(yaml::IO &io,
221                       InstrProfCorrelator::CorrelationData &Data) {
222     io.mapRequired("Probes", Data.Probes);
223   }
224 };
225 
226 template <> struct yaml::MappingTraits<InstrProfCorrelator::Probe> {
227   static void mapping(yaml::IO &io, InstrProfCorrelator::Probe &P) {
228     io.mapRequired("Function Name", P.FunctionName);
229     io.mapOptional("Linkage Name", P.LinkageName);
230     io.mapRequired("CFG Hash", P.CFGHash);
231     io.mapRequired("Counter Offset", P.CounterOffset);
232     io.mapRequired("Num Counters", P.NumCounters);
233     io.mapOptional("File", P.FilePath);
234     io.mapOptional("Line", P.LineNumber);
235   }
236 };
237 
238 template <> struct yaml::SequenceElementTraits<InstrProfCorrelator::Probe> {
239   static const bool flow = false;
240 };
241 
242 template <class IntPtrT>
243 Error InstrProfCorrelatorImpl<IntPtrT>::dumpYaml(int MaxWarnings,
244                                                  raw_ostream &OS) {
245   InstrProfCorrelator::CorrelationData Data;
246   correlateProfileDataImpl(MaxWarnings, &Data);
247   if (Data.Probes.empty())
248     return make_error<InstrProfError>(
249         instrprof_error::unable_to_correlate_profile,
250         "could not find any profile data metadata in debug info");
251   yaml::Output YamlOS(OS);
252   YamlOS << Data;
253   return Error::success();
254 }
255 
256 template <class IntPtrT>
257 void InstrProfCorrelatorImpl<IntPtrT>::addDataProbe(uint64_t NameRef,
258                                                     uint64_t CFGHash,
259                                                     IntPtrT CounterOffset,
260                                                     IntPtrT FunctionPtr,
261                                                     uint32_t NumCounters) {
262   // Check if a probe was already added for this counter offset.
263   if (!CounterOffsets.insert(CounterOffset).second)
264     return;
265   Data.push_back({
266       maybeSwap<uint64_t>(NameRef),
267       maybeSwap<uint64_t>(CFGHash),
268       // In this mode, CounterPtr actually stores the section relative address
269       // of the counter.
270       maybeSwap<IntPtrT>(CounterOffset),
271       // TODO: MC/DC is not yet supported.
272       /*BitmapOffset=*/maybeSwap<IntPtrT>(0),
273       maybeSwap<IntPtrT>(FunctionPtr),
274       // TODO: Value profiling is not yet supported.
275       /*ValuesPtr=*/maybeSwap<IntPtrT>(0),
276       maybeSwap<uint32_t>(NumCounters),
277       /*NumValueSites=*/{maybeSwap<uint16_t>(0), maybeSwap<uint16_t>(0)},
278       // TODO: MC/DC is not yet supported.
279       /*NumBitmapBytes=*/maybeSwap<uint32_t>(0),
280   });
281 }
282 
283 template <class IntPtrT>
284 std::optional<uint64_t>
285 DwarfInstrProfCorrelator<IntPtrT>::getLocation(const DWARFDie &Die) const {
286   auto Locations = Die.getLocations(dwarf::DW_AT_location);
287   if (!Locations) {
288     consumeError(Locations.takeError());
289     return {};
290   }
291   auto &DU = *Die.getDwarfUnit();
292   auto AddressSize = DU.getAddressByteSize();
293   for (auto &Location : *Locations) {
294     DataExtractor Data(Location.Expr, DICtx->isLittleEndian(), AddressSize);
295     DWARFExpression Expr(Data, AddressSize);
296     for (auto &Op : Expr) {
297       if (Op.getCode() == dwarf::DW_OP_addr) {
298         return Op.getRawOperand(0);
299       } else if (Op.getCode() == dwarf::DW_OP_addrx) {
300         uint64_t Index = Op.getRawOperand(0);
301         if (auto SA = DU.getAddrOffsetSectionItem(Index))
302           return SA->Address;
303       }
304     }
305   }
306   return {};
307 }
308 
309 template <class IntPtrT>
310 bool DwarfInstrProfCorrelator<IntPtrT>::isDIEOfProbe(const DWARFDie &Die) {
311   const auto &ParentDie = Die.getParent();
312   if (!Die.isValid() || !ParentDie.isValid() || Die.isNULL())
313     return false;
314   if (Die.getTag() != dwarf::DW_TAG_variable)
315     return false;
316   if (!ParentDie.isSubprogramDIE())
317     return false;
318   if (!Die.hasChildren())
319     return false;
320   if (const char *Name = Die.getName(DINameKind::ShortName))
321     return StringRef(Name).starts_with(getInstrProfCountersVarPrefix());
322   return false;
323 }
324 
325 template <class IntPtrT>
326 void DwarfInstrProfCorrelator<IntPtrT>::correlateProfileDataImpl(
327     int MaxWarnings, InstrProfCorrelator::CorrelationData *Data) {
328   bool UnlimitedWarnings = (MaxWarnings == 0);
329   // -N suppressed warnings means we can emit up to N (unsuppressed) warnings
330   int NumSuppressedWarnings = -MaxWarnings;
331   auto maybeAddProbe = [&](DWARFDie Die) {
332     if (!isDIEOfProbe(Die))
333       return;
334     std::optional<const char *> FunctionName;
335     std::optional<uint64_t> CFGHash;
336     std::optional<uint64_t> CounterPtr = getLocation(Die);
337     auto FnDie = Die.getParent();
338     auto FunctionPtr = dwarf::toAddress(FnDie.find(dwarf::DW_AT_low_pc));
339     std::optional<uint64_t> NumCounters;
340     for (const DWARFDie &Child : Die.children()) {
341       if (Child.getTag() != dwarf::DW_TAG_LLVM_annotation)
342         continue;
343       auto AnnotationFormName = Child.find(dwarf::DW_AT_name);
344       auto AnnotationFormValue = Child.find(dwarf::DW_AT_const_value);
345       if (!AnnotationFormName || !AnnotationFormValue)
346         continue;
347       auto AnnotationNameOrErr = AnnotationFormName->getAsCString();
348       if (auto Err = AnnotationNameOrErr.takeError()) {
349         consumeError(std::move(Err));
350         continue;
351       }
352       StringRef AnnotationName = *AnnotationNameOrErr;
353       if (AnnotationName.compare(
354               InstrProfCorrelator::FunctionNameAttributeName) == 0) {
355         if (auto EC =
356                 AnnotationFormValue->getAsCString().moveInto(FunctionName))
357           consumeError(std::move(EC));
358       } else if (AnnotationName.compare(
359                      InstrProfCorrelator::CFGHashAttributeName) == 0) {
360         CFGHash = AnnotationFormValue->getAsUnsignedConstant();
361       } else if (AnnotationName.compare(
362                      InstrProfCorrelator::NumCountersAttributeName) == 0) {
363         NumCounters = AnnotationFormValue->getAsUnsignedConstant();
364       }
365     }
366     if (!FunctionName || !CFGHash || !CounterPtr || !NumCounters) {
367       if (UnlimitedWarnings || ++NumSuppressedWarnings < 1) {
368         WithColor::warning()
369             << "Incomplete DIE for function " << FunctionName
370             << ": CFGHash=" << CFGHash << "  CounterPtr=" << CounterPtr
371             << "  NumCounters=" << NumCounters << "\n";
372         LLVM_DEBUG(Die.dump(dbgs()));
373       }
374       return;
375     }
376     uint64_t CountersStart = this->Ctx->CountersSectionStart;
377     uint64_t CountersEnd = this->Ctx->CountersSectionEnd;
378     if (*CounterPtr < CountersStart || *CounterPtr >= CountersEnd) {
379       if (UnlimitedWarnings || ++NumSuppressedWarnings < 1) {
380         WithColor::warning()
381             << format("CounterPtr out of range for function %s: Actual=0x%x "
382                       "Expected=[0x%x, 0x%x)\n",
383                       *FunctionName, *CounterPtr, CountersStart, CountersEnd);
384         LLVM_DEBUG(Die.dump(dbgs()));
385       }
386       return;
387     }
388     if (!FunctionPtr && (UnlimitedWarnings || ++NumSuppressedWarnings < 1)) {
389       WithColor::warning() << format("Could not find address of function %s\n",
390                                      *FunctionName);
391       LLVM_DEBUG(Die.dump(dbgs()));
392     }
393     // In debug info correlation mode, the CounterPtr is an absolute address of
394     // the counter, but it's expected to be relative later when iterating Data.
395     IntPtrT CounterOffset = *CounterPtr - CountersStart;
396     if (Data) {
397       InstrProfCorrelator::Probe P;
398       P.FunctionName = *FunctionName;
399       if (auto Name = FnDie.getName(DINameKind::LinkageName))
400         P.LinkageName = Name;
401       P.CFGHash = *CFGHash;
402       P.CounterOffset = CounterOffset;
403       P.NumCounters = *NumCounters;
404       auto FilePath = FnDie.getDeclFile(
405           DILineInfoSpecifier::FileLineInfoKind::RelativeFilePath);
406       if (!FilePath.empty())
407         P.FilePath = FilePath;
408       if (auto LineNumber = FnDie.getDeclLine())
409         P.LineNumber = LineNumber;
410       Data->Probes.push_back(P);
411     } else {
412       this->addDataProbe(IndexedInstrProf::ComputeHash(*FunctionName), *CFGHash,
413                          CounterOffset, FunctionPtr.value_or(0), *NumCounters);
414       this->NamesVec.push_back(*FunctionName);
415     }
416   };
417   for (auto &CU : DICtx->normal_units())
418     for (const auto &Entry : CU->dies())
419       maybeAddProbe(DWARFDie(CU.get(), &Entry));
420   for (auto &CU : DICtx->dwo_units())
421     for (const auto &Entry : CU->dies())
422       maybeAddProbe(DWARFDie(CU.get(), &Entry));
423 
424   if (!UnlimitedWarnings && NumSuppressedWarnings > 0)
425     WithColor::warning() << format("Suppressed %d additional warnings\n",
426                                    NumSuppressedWarnings);
427 }
428 
429 template <class IntPtrT>
430 Error DwarfInstrProfCorrelator<IntPtrT>::correlateProfileNameImpl() {
431   if (this->NamesVec.empty()) {
432     return make_error<InstrProfError>(
433         instrprof_error::unable_to_correlate_profile,
434         "could not find any profile name metadata in debug info");
435   }
436   auto Result =
437       collectGlobalObjectNameStrings(this->NamesVec,
438                                      /*doCompression=*/false, this->Names);
439   return Result;
440 }
441 
442 template <class IntPtrT>
443 void BinaryInstrProfCorrelator<IntPtrT>::correlateProfileDataImpl(
444     int MaxWarnings, InstrProfCorrelator::CorrelationData *CorrelateData) {
445   using RawProfData = RawInstrProf::ProfileData<IntPtrT>;
446   bool UnlimitedWarnings = (MaxWarnings == 0);
447   // -N suppressed warnings means we can emit up to N (unsuppressed) warnings
448   int NumSuppressedWarnings = -MaxWarnings;
449 
450   const RawProfData *DataStart = (const RawProfData *)this->Ctx->DataStart;
451   const RawProfData *DataEnd = (const RawProfData *)this->Ctx->DataEnd;
452   // We need to use < here because the last data record may have no padding.
453   for (const RawProfData *I = DataStart; I < DataEnd; ++I) {
454     uint64_t CounterPtr = this->template maybeSwap<IntPtrT>(I->CounterPtr);
455     uint64_t CountersStart = this->Ctx->CountersSectionStart;
456     uint64_t CountersEnd = this->Ctx->CountersSectionEnd;
457     if (CounterPtr < CountersStart || CounterPtr >= CountersEnd) {
458       if (UnlimitedWarnings || ++NumSuppressedWarnings < 1) {
459         WithColor::warning()
460             << format("CounterPtr out of range for function: Actual=0x%x "
461                       "Expected=[0x%x, 0x%x) at data offset=0x%x\n",
462                       CounterPtr, CountersStart, CountersEnd,
463                       (I - DataStart) * sizeof(RawProfData));
464       }
465     }
466     // In binary correlation mode, the CounterPtr is an absolute address of the
467     // counter, but it's expected to be relative later when iterating Data.
468     IntPtrT CounterOffset = CounterPtr - CountersStart;
469     this->addDataProbe(I->NameRef, I->FuncHash, CounterOffset,
470                        I->FunctionPointer, I->NumCounters);
471   }
472 }
473 
474 template <class IntPtrT>
475 Error BinaryInstrProfCorrelator<IntPtrT>::correlateProfileNameImpl() {
476   if (this->Ctx->NameSize == 0) {
477     return make_error<InstrProfError>(
478         instrprof_error::unable_to_correlate_profile,
479         "could not find any profile data metadata in object file");
480   }
481   this->Names.append(this->Ctx->NameStart, this->Ctx->NameSize);
482   return Error::success();
483 }
484