xref: /llvm-project/bolt/lib/Core/DebugNames.cpp (revision 331c2dd8b482e441d8ccddc09f21a02cc9454786) 
1 //===- bolt/Rewrite/DebugNames.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 "bolt/Core/DebugNames.h"
10 #include "bolt/Core/BinaryContext.h"
11 #include "llvm/DebugInfo/DWARF/DWARFExpression.h"
12 #include "llvm/DebugInfo/DWARF/DWARFTypeUnit.h"
13 #include "llvm/Support/EndianStream.h"
14 #include "llvm/Support/LEB128.h"
15 #include <cstdint>
16 #include <optional>
17 
18 namespace llvm {
19 namespace bolt {
20 DWARF5AcceleratorTable::DWARF5AcceleratorTable(
21     const bool CreateDebugNames, BinaryContext &BC,
22     DebugStrWriter &MainBinaryStrWriter)
23     : BC(BC), MainBinaryStrWriter(MainBinaryStrWriter) {
24   NeedToCreate = CreateDebugNames || BC.getDebugNamesSection();
25   if (!NeedToCreate)
26     return;
27   FullTableBuffer = std::make_unique<DebugStrBufferVector>();
28   FullTableStream = std::make_unique<raw_svector_ostream>(*FullTableBuffer);
29   StrBuffer = std::make_unique<DebugStrBufferVector>();
30   StrStream = std::make_unique<raw_svector_ostream>(*StrBuffer);
31   EntriesBuffer = std::make_unique<DebugStrBufferVector>();
32   Entriestream = std::make_unique<raw_svector_ostream>(*EntriesBuffer);
33   AugStringBuffer = std::make_unique<DebugStrBufferVector>();
34   AugStringtream = std::make_unique<raw_svector_ostream>(*AugStringBuffer);
35 
36   // Binary has split-dwarf CUs.
37   // Even thought for non-skeleton-cu all names are in .debug_str.dwo section,
38   // for the .debug_names contributions they are in .debug_str section.
39   if (BC.getNumDWOCUs()) {
40     DataExtractor StrData(BC.DwCtx->getDWARFObj().getStrSection(),
41                           BC.DwCtx->isLittleEndian(), 0);
42     uint64_t Offset = 0;
43     uint64_t StrOffset = 0;
44     while (StrData.isValidOffset(Offset)) {
45       Error Err = Error::success();
46       const char *CStr = StrData.getCStr(&Offset, &Err);
47       if (Err) {
48         NeedToCreate = false;
49         BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: Could not extract "
50                      "string from .debug_str section at offset: "
51                   << Twine::utohexstr(StrOffset) << ".\n";
52         return;
53       }
54       auto R = StrCacheToOffsetMap.try_emplace(
55           llvm::hash_value(llvm::StringRef(CStr)), StrOffset);
56       if (!R.second)
57         BC.errs()
58             << "BOLT-WARNING: [internal-dwarf-error]: collision occured on "
59             << CStr << " at offset : 0x" << Twine::utohexstr(StrOffset)
60             << ". Previous string offset is: 0x"
61             << Twine::utohexstr(R.first->second) << ".\n";
62       StrOffset = Offset;
63     }
64   }
65 }
66 
67 void DWARF5AcceleratorTable::setCurrentUnit(DWARFUnit &Unit,
68                                             const uint64_t UnitStartOffset) {
69   CurrentUnit = nullptr;
70   CurrentUnitOffset = UnitStartOffset;
71   std::optional<uint64_t> DWOID = Unit.getDWOId();
72   // We process skeleton CUs after DWO Units for it.
73   // Patching offset in CU list to correct one.
74   if (!Unit.isDWOUnit() && DWOID) {
75     auto Iter = CUOffsetsToPatch.find(*DWOID);
76     // Check in case no entries were added from non skeleton DWO section.
77     if (Iter != CUOffsetsToPatch.end())
78       CUList[Iter->second] = UnitStartOffset;
79   }
80 }
81 
82 void DWARF5AcceleratorTable::addUnit(DWARFUnit &Unit,
83                                      const std::optional<uint64_t> &DWOID) {
84   constexpr uint32_t BADCUOFFSET = 0xBADBAD;
85   StrSection = Unit.getStringSection();
86   if (Unit.isTypeUnit()) {
87     if (DWOID) {
88       // We adding an entry for a DWO TU. The DWO CU might not have any entries,
89       // so need to add it to the list pre-emptively.
90       auto Iter = CUOffsetsToPatch.insert({*DWOID, CUList.size()});
91       if (Iter.second)
92         CUList.push_back(BADCUOFFSET);
93       const uint64_t TUHash = cast<DWARFTypeUnit>(&Unit)->getTypeHash();
94       if (!TUHashToIndexMap.count(TUHash)) {
95         TUHashToIndexMap.insert({TUHash, ForeignTUList.size()});
96         ForeignTUList.push_back(TUHash);
97       }
98     } else {
99       LocalTUList.push_back(CurrentUnitOffset);
100     }
101   } else {
102     if (DWOID) {
103       // This is a path for split dwarf without type units.
104       // We process DWO Units before Skeleton CU. So at this point we don't know
105       // the offset of Skeleton CU. Adding CULit index to a map to patch later
106       // with the correct offset.
107       auto Iter = CUOffsetsToPatch.insert({*DWOID, CUList.size()});
108       if (Iter.second)
109         CUList.push_back(BADCUOFFSET);
110     } else {
111       CUList.push_back(CurrentUnitOffset);
112     }
113   }
114 }
115 
116 // Returns true if DW_TAG_variable should be included in .debug-names based on
117 // section 6.1.1.1 for DWARF5 spec.
118 static bool shouldIncludeVariable(const DWARFUnit &Unit, const DIE &Die) {
119   const DIEValue LocAttrInfo =
120       Die.findAttribute(dwarf::Attribute::DW_AT_location);
121   if (!LocAttrInfo)
122     return false;
123   if (!(doesFormBelongToClass(LocAttrInfo.getForm(), DWARFFormValue::FC_Exprloc,
124                               Unit.getVersion()) ||
125         doesFormBelongToClass(LocAttrInfo.getForm(), DWARFFormValue::FC_Block,
126                               Unit.getVersion())))
127     return false;
128   std::vector<uint8_t> Sblock;
129   auto constructVect =
130       [&](const DIEValueList::const_value_range &Iter) -> void {
131     for (const DIEValue &Val : Iter)
132       Sblock.push_back(Val.getDIEInteger().getValue());
133   };
134   if (doesFormBelongToClass(LocAttrInfo.getForm(), DWARFFormValue::FC_Exprloc,
135                             Unit.getVersion()))
136     constructVect(LocAttrInfo.getDIELoc().values());
137   else
138     constructVect(LocAttrInfo.getDIEBlock().values());
139   ArrayRef<uint8_t> Expr = ArrayRef<uint8_t>(Sblock);
140   DataExtractor Data(StringRef((const char *)Expr.data(), Expr.size()),
141                      Unit.getContext().isLittleEndian(), 0);
142   DWARFExpression LocExpr(Data, Unit.getAddressByteSize(),
143                           Unit.getFormParams().Format);
144   for (const DWARFExpression::Operation &Expr : LocExpr)
145     if (Expr.getCode() == dwarf::DW_OP_addrx ||
146         Expr.getCode() == dwarf::DW_OP_form_tls_address ||
147         Expr.getCode() == dwarf::DW_OP_GNU_push_tls_address)
148       return true;
149   return false;
150 }
151 
152 bool static canProcess(const DWARFUnit &Unit, const DIE &Die,
153                        std::string &NameToUse, const bool TagsOnly) {
154   if (Die.findAttribute(dwarf::Attribute::DW_AT_declaration))
155     return false;
156   switch (Die.getTag()) {
157   case dwarf::DW_TAG_base_type:
158   case dwarf::DW_TAG_class_type:
159   case dwarf::DW_TAG_enumeration_type:
160   case dwarf::DW_TAG_imported_declaration:
161   case dwarf::DW_TAG_pointer_type:
162   case dwarf::DW_TAG_structure_type:
163   case dwarf::DW_TAG_typedef:
164   case dwarf::DW_TAG_unspecified_type:
165   case dwarf::DW_TAG_union_type:
166     if (TagsOnly || Die.findAttribute(dwarf::Attribute::DW_AT_name))
167       return true;
168     return false;
169   case dwarf::DW_TAG_namespace:
170     // According to DWARF5 spec namespaces without DW_AT_name needs to have
171     // "(anonymous namespace)"
172     if (!Die.findAttribute(dwarf::Attribute::DW_AT_name))
173       NameToUse = "(anonymous namespace)";
174     return true;
175   case dwarf::DW_TAG_inlined_subroutine:
176   case dwarf::DW_TAG_label:
177   case dwarf::DW_TAG_subprogram:
178     if (TagsOnly || Die.findAttribute(dwarf::Attribute::DW_AT_low_pc) ||
179         Die.findAttribute(dwarf::Attribute::DW_AT_high_pc) ||
180         Die.findAttribute(dwarf::Attribute::DW_AT_ranges) ||
181         Die.findAttribute(dwarf::Attribute::DW_AT_entry_pc))
182       return true;
183     return false;
184   case dwarf::DW_TAG_variable:
185     return TagsOnly || shouldIncludeVariable(Unit, Die);
186   default:
187     break;
188   }
189   return false;
190 }
191 
192 bool DWARF5AcceleratorTable::canGenerateEntryWithCrossCUReference(
193     const DWARFUnit &Unit, const DIE &Die,
194     const DWARFAbbreviationDeclaration::AttributeSpec &AttrSpec) {
195   if (!isCreated())
196     return false;
197   std::string NameToUse = "";
198   if (!canProcess(Unit, Die, NameToUse, true))
199     return false;
200   return (AttrSpec.Attr == dwarf::Attribute::DW_AT_abstract_origin ||
201           AttrSpec.Attr == dwarf::Attribute::DW_AT_specification) &&
202          AttrSpec.Form == dwarf::DW_FORM_ref_addr;
203 }
204 /// Returns name offset in String Offset section.
205 static uint64_t getNameOffset(BinaryContext &BC, DWARFUnit &Unit,
206                               const uint64_t Index) {
207   const DWARFSection &StrOffsetsSection = Unit.getStringOffsetSection();
208   const std::optional<StrOffsetsContributionDescriptor> &Contr =
209       Unit.getStringOffsetsTableContribution();
210   if (!Contr) {
211     BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not get "
212                  "StringOffsetsTableContribution for unit at offset: "
213               << Twine::utohexstr(Unit.getOffset()) << ".\n";
214     return 0;
215   }
216 
217   const uint8_t DwarfOffsetByteSize = Contr->getDwarfOffsetByteSize();
218   return support::endian::read32le(StrOffsetsSection.Data.data() + Contr->Base +
219                                    Index * DwarfOffsetByteSize);
220 }
221 
222 static uint64_t getEntryID(const BOLTDWARF5AccelTableData &Entry) {
223   return reinterpret_cast<uint64_t>(&Entry);
224 }
225 
226 uint32_t DWARF5AcceleratorTable::getUnitID(const DWARFUnit &Unit,
227                                            const std::optional<uint64_t> &DWOID,
228                                            bool &IsTU) {
229   IsTU = Unit.isTypeUnit();
230   if (IsTU) {
231     if (DWOID) {
232       const uint64_t TUHash = cast<DWARFTypeUnit>(&Unit)->getTypeHash();
233       auto Iter = TUHashToIndexMap.find(TUHash);
234       assert(Iter != TUHashToIndexMap.end() && "Could not find TU hash in map");
235       return Iter->second;
236     }
237     return LocalTUList.size() - 1;
238   }
239   return CUList.size() - 1;
240 }
241 
242 std::optional<std::string> DWARF5AcceleratorTable::getName(
243     DWARFUnit &Unit, const std::optional<uint64_t> &DWOID,
244     const std::string &NameToUse, DIEValue ValName) {
245   if ((!ValName || ValName.getForm() == dwarf::DW_FORM_string) &&
246       NameToUse.empty())
247     return std::nullopt;
248   std::string Name = "";
249   uint64_t NameIndexOffset = 0;
250   if (NameToUse.empty()) {
251     NameIndexOffset = ValName.getDIEInteger().getValue();
252     if (ValName.getForm() != dwarf::DW_FORM_strp)
253       NameIndexOffset = getNameOffset(BC, Unit, NameIndexOffset);
254     // Counts on strings end with '\0'.
255     Name = std::string(&StrSection.data()[NameIndexOffset]);
256   } else {
257     Name = NameToUse;
258   }
259   auto &It = Entries[Name];
260   if (It.Values.empty()) {
261     if (DWOID && NameToUse.empty()) {
262       // For DWO Unit the offset is in the .debug_str.dwo section.
263       // Need to find offset for the name in the .debug_str section.
264       llvm::hash_code Hash = llvm::hash_value(llvm::StringRef(Name));
265       auto ItCache = StrCacheToOffsetMap.find(Hash);
266       if (ItCache == StrCacheToOffsetMap.end())
267         NameIndexOffset = MainBinaryStrWriter.addString(Name);
268       else
269         NameIndexOffset = ItCache->second;
270     }
271     if (!NameToUse.empty())
272       NameIndexOffset = MainBinaryStrWriter.addString(Name);
273     It.StrOffset = NameIndexOffset;
274     // This is the same hash function used in DWARF5AccelTableData.
275     It.HashValue = caseFoldingDjbHash(Name);
276   }
277   return Name;
278 }
279 
280 std::optional<BOLTDWARF5AccelTableData *> DWARF5AcceleratorTable::addEntry(
281     DWARFUnit &DU, const DIE &CurrDie, const std::optional<uint64_t> &DWOID,
282     const std::optional<BOLTDWARF5AccelTableData *> &Parent,
283     const std::optional<std::string> &Name,
284     const uint32_t NumberParentsInChain) {
285   if (!Name)
286     return std::nullopt;
287 
288   auto &It = Entries[*Name];
289   bool IsTU = false;
290   uint32_t DieTag = CurrDie.getTag();
291   uint32_t UnitID = getUnitID(DU, DWOID, IsTU);
292   std::optional<unsigned> SecondIndex = std::nullopt;
293   if (IsTU && DWOID) {
294     auto Iter = CUOffsetsToPatch.find(*DWOID);
295     if (Iter == CUOffsetsToPatch.end())
296       BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not find "
297                    "DWO ID in CU offsets for second Unit Index "
298                 << *Name << ". For DIE at offset: "
299                 << Twine::utohexstr(CurrentUnitOffset + CurrDie.getOffset())
300                 << ".\n";
301     SecondIndex = Iter->second;
302   }
303   std::optional<uint64_t> ParentOffset =
304       (Parent ? std::optional<uint64_t>(getEntryID(**Parent)) : std::nullopt);
305   // This will be only populated in writeEntry, in order to keep only the parent
306   // entries, and keep the footprint down.
307   if (ParentOffset)
308     EntryRelativeOffsets.insert({*ParentOffset, 0});
309   bool IsParentRoot = false;
310   // If there is no parent and no valid Entries in parent chain this is a root
311   // to be marked with a flag.
312   if (!Parent && !NumberParentsInChain)
313     IsParentRoot = true;
314   It.Values.push_back(new (Allocator) BOLTDWARF5AccelTableData(
315       CurrDie.getOffset(), ParentOffset, DieTag, UnitID, IsParentRoot, IsTU,
316       SecondIndex));
317   return It.Values.back();
318 }
319 
320 std::optional<BOLTDWARF5AccelTableData *>
321 DWARF5AcceleratorTable::processReferencedDie(
322     DWARFUnit &Unit, const DIE &Die, const std::optional<uint64_t> &DWOID,
323     const std::optional<BOLTDWARF5AccelTableData *> &Parent,
324     const std::string &NameToUse, const uint32_t NumberParentsInChain,
325     const dwarf::Attribute &Attr) {
326   DIEValue Value = Die.findAttribute(Attr);
327   if (!Value)
328     return std::nullopt;
329   auto getReferenceDie = [&](const DIEValue &Value, const DIE *RefDieUsed)
330       -> std::optional<std::pair<DWARFUnit *, const DIE *>> {
331     if (!Value)
332       return std::nullopt;
333     if (Value.getForm() == dwarf::DW_FORM_ref_addr) {
334       auto Iter = CrossCUDies.find(Value.getDIEInteger().getValue());
335       if (Iter == CrossCUDies.end()) {
336         BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not find "
337                      "referenced DIE in CrossCUDies for "
338                   << Twine::utohexstr(Value.getDIEInteger().getValue())
339                   << ".\n";
340         return std::nullopt;
341       }
342       return Iter->second;
343     }
344     const DIEEntry &DIEENtry = Value.getDIEEntry();
345     return {{&Unit, &DIEENtry.getEntry()}};
346   };
347 
348   DIEValue AttrValLinkageName;
349   DIEValue AttrValName = Die.findAttribute(dwarf::Attribute::DW_AT_name);
350   DWARFUnit *RefUnit = &Unit;
351   const DIE *RefDieUsed = &Die;
352   // It is possible to have DW_TAG_subprogram only with  DW_AT_linkage_name that
353   // DW_AT_abstract_origin/DW_AT_specification point to.
354   while (!AttrValName) {
355     std::optional<std::pair<DWARFUnit *, const DIE *>> RefDUDie =
356         getReferenceDie(Value, RefDieUsed);
357     if (!RefDUDie)
358       break;
359     RefUnit = RefDUDie->first;
360     const DIE &RefDie = *RefDUDie->second;
361     RefDieUsed = &RefDie;
362     if (!AttrValLinkageName)
363       AttrValLinkageName =
364           RefDie.findAttribute(dwarf::Attribute::DW_AT_linkage_name);
365     AttrValName = RefDie.findAttribute(dwarf::Attribute::DW_AT_name);
366     Value = RefDie.findAttribute(dwarf::Attribute::DW_AT_abstract_origin);
367     if (!Value)
368       Value = RefDie.findAttribute(dwarf::Attribute::DW_AT_specification);
369   }
370   addEntry(Unit, Die, DWOID, Parent,
371            getName(*RefUnit, DWOID, NameToUse, AttrValLinkageName),
372            NumberParentsInChain);
373   return addEntry(Unit, Die, DWOID, Parent,
374                   getName(*RefUnit, DWOID, NameToUse, AttrValName),
375                   NumberParentsInChain);
376 }
377 
378 std::optional<BOLTDWARF5AccelTableData *>
379 DWARF5AcceleratorTable::addAccelTableEntry(
380     DWARFUnit &Unit, const DIE &Die, const std::optional<uint64_t> &DWOID,
381     const uint32_t NumberParentsInChain,
382     std::optional<BOLTDWARF5AccelTableData *> &Parent) {
383   if (Unit.getVersion() < 5 || !NeedToCreate)
384     return std::nullopt;
385   std::string NameToUse = "";
386 
387   if (!canProcess(Unit, Die, NameToUse, false))
388     return std::nullopt;
389 
390   // Adds a Unit to either CU, LocalTU or ForeignTU list the first time we
391   // encounter it.
392   // Invoking it here so that we don't add Units that don't have any entries.
393   if (&Unit != CurrentUnit) {
394     CurrentUnit = &Unit;
395     addUnit(Unit, DWOID);
396   }
397 
398   // Minor optimization not to add entry twice for DW_TAG_namespace if it has no
399   // DW_AT_name.
400   std::optional<BOLTDWARF5AccelTableData *> LinkageEntry = std::nullopt;
401   DIEValue NameVal = Die.findAttribute(dwarf::Attribute::DW_AT_name);
402   DIEValue LinkageNameVal =
403       Die.findAttribute(dwarf::Attribute::DW_AT_linkage_name);
404   if (!(Die.getTag() == dwarf::DW_TAG_namespace && !NameVal))
405     LinkageEntry = addEntry(Unit, Die, DWOID, Parent,
406                             getName(Unit, DWOID, NameToUse, LinkageNameVal),
407                             NumberParentsInChain);
408 
409   std::optional<BOLTDWARF5AccelTableData *> NameEntry =
410       addEntry(Unit, Die, DWOID, Parent,
411                getName(Unit, DWOID, NameToUse, NameVal), NumberParentsInChain);
412   if (NameEntry)
413     return NameEntry;
414 
415   // The DIE doesn't have DW_AT_name or DW_AT_linkage_name, so we need to see if
416   // we can follow other attributes to find them. For the purposes of
417   // determining whether a debug information entry has a particular
418   // attribute (such as DW_AT_name), if debug information entry A has a
419   // DW_AT_specification or DW_AT_abstract_origin attribute pointing to another
420   // debug information entry B, any attributes of B are considered to be
421   // part of A.
422   if (std::optional<BOLTDWARF5AccelTableData *> Entry = processReferencedDie(
423           Unit, Die, DWOID, Parent, NameToUse, NumberParentsInChain,
424           dwarf::Attribute::DW_AT_abstract_origin))
425     return *Entry;
426   if (std::optional<BOLTDWARF5AccelTableData *> Entry = processReferencedDie(
427           Unit, Die, DWOID, Parent, NameToUse, NumberParentsInChain,
428           dwarf::Attribute::DW_AT_specification))
429     return *Entry;
430 
431   // This point can be hit by DW_TAG_varialbe that has no DW_AT_name.
432   return std::nullopt;
433 }
434 
435 /// Algorithm from llvm implementation.
436 void DWARF5AcceleratorTable::computeBucketCount() {
437   // First get the number of unique hashes.
438   std::vector<uint32_t> Uniques;
439   Uniques.reserve(Entries.size());
440   for (const auto &E : Entries)
441     Uniques.push_back(E.second.HashValue);
442   array_pod_sort(Uniques.begin(), Uniques.end());
443   std::vector<uint32_t>::iterator P =
444       std::unique(Uniques.begin(), Uniques.end());
445 
446   UniqueHashCount = std::distance(Uniques.begin(), P);
447 
448   if (UniqueHashCount > 1024)
449     BucketCount = UniqueHashCount / 4;
450   else if (UniqueHashCount > 16)
451     BucketCount = UniqueHashCount / 2;
452   else
453     BucketCount = std::max<uint32_t>(UniqueHashCount, 1);
454 }
455 
456 /// Bucket code as in: AccelTableBase::finalize()
457 void DWARF5AcceleratorTable::finalize() {
458   if (!NeedToCreate)
459     return;
460   // Figure out how many buckets we need, then compute the bucket contents and
461   // the final ordering. The hashes and offsets can be emitted by walking these
462   // data structures.
463   computeBucketCount();
464 
465   // Compute bucket contents and final ordering.
466   Buckets.resize(BucketCount);
467   for (auto &E : Entries) {
468     uint32_t Bucket = E.second.HashValue % BucketCount;
469     Buckets[Bucket].push_back(&E.second);
470   }
471 
472   // Sort the contents of the buckets by hash value so that hash collisions end
473   // up together. Stable sort makes testing easier and doesn't cost much more.
474   for (HashList &Bucket : Buckets) {
475     llvm::stable_sort(Bucket, [](const HashData *LHS, const HashData *RHS) {
476       return LHS->HashValue < RHS->HashValue;
477     });
478     for (HashData *H : Bucket)
479       llvm::stable_sort(H->Values, [](const BOLTDWARF5AccelTableData *LHS,
480                                       const BOLTDWARF5AccelTableData *RHS) {
481         return LHS->getDieOffset() < RHS->getDieOffset();
482       });
483   }
484 
485   CUIndexForm = DIEInteger::BestForm(/*IsSigned*/ false, CUList.size() - 1);
486   TUIndexForm = DIEInteger::BestForm(
487       /*IsSigned*/ false, LocalTUList.size() + ForeignTUList.size() - 1);
488   const dwarf::FormParams FormParams{5, 4, dwarf::DwarfFormat::DWARF32, false};
489   CUIndexEncodingSize = *dwarf::getFixedFormByteSize(CUIndexForm, FormParams);
490   TUIndexEncodingSize = *dwarf::getFixedFormByteSize(TUIndexForm, FormParams);
491 }
492 
493 std::optional<DWARF5AccelTable::UnitIndexAndEncoding>
494 DWARF5AcceleratorTable::getIndexForEntry(
495     const BOLTDWARF5AccelTableData &Value) const {
496   // The foreign TU list immediately follows the local TU list and they both
497   // use the same index, so that if there are N local TU entries, the index for
498   // the first foreign TU is N.
499   if (Value.isTU())
500     return {{(Value.getSecondUnitID() ? (unsigned)LocalTUList.size() : 0) +
501                  Value.getUnitID(),
502              {dwarf::DW_IDX_type_unit, TUIndexForm}}};
503   if (CUList.size() > 1)
504     return {{Value.getUnitID(), {dwarf::DW_IDX_compile_unit, CUIndexForm}}};
505   return std::nullopt;
506 }
507 
508 std::optional<DWARF5AccelTable::UnitIndexAndEncoding>
509 DWARF5AcceleratorTable::getSecondIndexForEntry(
510     const BOLTDWARF5AccelTableData &Value) const {
511   if (Value.isTU() && CUList.size() > 1 && Value.getSecondUnitID())
512     return {
513         {*Value.getSecondUnitID(), {dwarf::DW_IDX_compile_unit, CUIndexForm}}};
514   return std::nullopt;
515 }
516 
517 void DWARF5AcceleratorTable::populateAbbrevsMap() {
518   for (auto &Bucket : getBuckets()) {
519     for (DWARF5AcceleratorTable::HashData *Hash : Bucket) {
520       for (BOLTDWARF5AccelTableData *Value : Hash->Values) {
521         const std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet =
522             getIndexForEntry(*Value);
523         // For entries that need to refer to the foreign type units and to
524         // the CU.
525         const std::optional<DWARF5AccelTable::UnitIndexAndEncoding>
526             SecondEntryRet = getSecondIndexForEntry(*Value);
527         DebugNamesAbbrev Abbrev(Value->getDieTag());
528         if (EntryRet)
529           Abbrev.addAttribute(EntryRet->Encoding);
530         if (SecondEntryRet)
531           Abbrev.addAttribute(SecondEntryRet->Encoding);
532         Abbrev.addAttribute({dwarf::DW_IDX_die_offset, dwarf::DW_FORM_ref4});
533         if (std::optional<uint64_t> Offset = Value->getParentDieOffset())
534           Abbrev.addAttribute({dwarf::DW_IDX_parent, dwarf::DW_FORM_ref4});
535         else if (Value->isParentRoot())
536           Abbrev.addAttribute(
537               {dwarf::DW_IDX_parent, dwarf::DW_FORM_flag_present});
538         FoldingSetNodeID ID;
539         Abbrev.Profile(ID);
540         void *InsertPos;
541         if (DebugNamesAbbrev *Existing =
542                 AbbreviationsSet.FindNodeOrInsertPos(ID, InsertPos)) {
543           Value->setAbbrevNumber(Existing->getNumber());
544           continue;
545         }
546         DebugNamesAbbrev *NewAbbrev =
547             new (Alloc) DebugNamesAbbrev(std::move(Abbrev));
548         AbbreviationsVector.push_back(NewAbbrev);
549         NewAbbrev->setNumber(AbbreviationsVector.size());
550         AbbreviationsSet.InsertNode(NewAbbrev, InsertPos);
551         Value->setAbbrevNumber(NewAbbrev->getNumber());
552       }
553     }
554   }
555 }
556 
557 void DWARF5AcceleratorTable::writeEntry(BOLTDWARF5AccelTableData &Entry) {
558   const uint64_t EntryID = getEntryID(Entry);
559   if (EntryRelativeOffsets.find(EntryID) != EntryRelativeOffsets.end())
560     EntryRelativeOffsets[EntryID] = EntriesBuffer->size();
561 
562   const std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet =
563       getIndexForEntry(Entry);
564   // For forgeign type (FTU) units that need to refer to the FTU and to the CU.
565   const std::optional<DWARF5AccelTable::UnitIndexAndEncoding> SecondEntryRet =
566       getSecondIndexForEntry(Entry);
567   const unsigned AbbrevIndex = Entry.getAbbrevNumber() - 1;
568   assert(AbbrevIndex < AbbreviationsVector.size() &&
569          "Entry abbrev index is outside of abbreviations vector range.");
570   const DebugNamesAbbrev *Abbrev = AbbreviationsVector[AbbrevIndex];
571   encodeULEB128(Entry.getAbbrevNumber(), *Entriestream);
572   auto writeIndex = [&](uint32_t Index, uint32_t IndexSize) -> void {
573     switch (IndexSize) {
574     default:
575       llvm_unreachable("Unsupported Index Size!");
576       break;
577     case 1:
578       support::endian::write(*Entriestream, static_cast<uint8_t>(Index),
579                              llvm::endianness::little);
580       break;
581     case 2:
582       support::endian::write(*Entriestream, static_cast<uint16_t>(Index),
583                              llvm::endianness::little);
584       break;
585     case 4:
586       support::endian::write(*Entriestream, static_cast<uint32_t>(Index),
587                              llvm::endianness::little);
588       break;
589     };
590   };
591 
592   for (const DebugNamesAbbrev::AttributeEncoding &AttrEnc :
593        Abbrev->getAttributes()) {
594     switch (AttrEnc.Index) {
595     default: {
596       llvm_unreachable("Unexpected index attribute!");
597       break;
598     }
599     case dwarf::DW_IDX_compile_unit: {
600       const unsigned CUIndex =
601           SecondEntryRet ? SecondEntryRet->Index : EntryRet->Index;
602       writeIndex(CUIndex, CUIndexEncodingSize);
603       break;
604     }
605     case dwarf::DW_IDX_type_unit: {
606       writeIndex(EntryRet->Index, TUIndexEncodingSize);
607       break;
608     }
609     case dwarf::DW_IDX_die_offset: {
610       assert(AttrEnc.Form == dwarf::DW_FORM_ref4);
611       support::endian::write(*Entriestream,
612                              static_cast<uint32_t>(Entry.getDieOffset()),
613                              llvm::endianness::little);
614       break;
615     }
616     case dwarf::DW_IDX_parent: {
617       assert(
618           (AttrEnc.Form == dwarf::DW_FORM_ref4 && Entry.getParentDieOffset()) ||
619           AttrEnc.Form == dwarf::DW_FORM_flag_present);
620       if (std::optional<uint64_t> ParentOffset = Entry.getParentDieOffset()) {
621         Entry.setPatchOffset(EntriesBuffer->size());
622         support::endian::write(*Entriestream, static_cast<uint32_t>(UINT32_MAX),
623                                llvm::endianness::little);
624       }
625       break;
626     }
627     }
628   }
629 }
630 
631 void DWARF5AcceleratorTable::writeEntries() {
632   for (auto &Bucket : getBuckets()) {
633     for (DWARF5AcceleratorTable::HashData *Hash : Bucket) {
634       Hash->EntryOffset = EntriesBuffer->size();
635       for (BOLTDWARF5AccelTableData *Value : Hash->Values) {
636         writeEntry(*Value);
637       }
638       support::endian::write(*Entriestream, static_cast<uint8_t>(0),
639                              llvm::endianness::little);
640     }
641   }
642   // Patching parent offsets.
643   for (auto &Bucket : getBuckets()) {
644     for (DWARF5AcceleratorTable::HashData *Hash : Bucket) {
645       for (BOLTDWARF5AccelTableData *Entry : Hash->Values) {
646         std::optional<uint64_t> ParentOffset = Entry->getParentDieOffset();
647         if (!ParentOffset)
648           continue;
649         if (const auto Iter = EntryRelativeOffsets.find(*ParentOffset);
650             Iter != EntryRelativeOffsets.end()) {
651           const uint64_t PatchOffset = Entry->getPatchOffset();
652           uint32_t *Ptr = reinterpret_cast<uint32_t *>(
653               &EntriesBuffer.get()->data()[PatchOffset]);
654           *Ptr = Iter->second;
655         } else {
656           BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not find "
657                        "entry with offset "
658                     << *ParentOffset << "\n";
659         }
660       }
661     }
662   }
663 }
664 
665 void DWARF5AcceleratorTable::writeAugmentationString() {
666   // String needs to be multiple of 4 bytes.
667   *AugStringtream << "BOLT";
668   AugmentationStringSize = AugStringBuffer->size();
669 }
670 
671 /// Calculates size of .debug_names header without Length field.
672 static constexpr uint32_t getDebugNamesHeaderSize() {
673   constexpr uint16_t VersionLength = sizeof(uint16_t);
674   constexpr uint16_t PaddingLength = sizeof(uint16_t);
675   constexpr uint32_t CompUnitCountLength = sizeof(uint32_t);
676   constexpr uint32_t LocalTypeUnitCountLength = sizeof(uint32_t);
677   constexpr uint32_t ForeignTypeUnitCountLength = sizeof(uint32_t);
678   constexpr uint32_t BucketCountLength = sizeof(uint32_t);
679   constexpr uint32_t NameCountLength = sizeof(uint32_t);
680   constexpr uint32_t AbbrevTableSizeLength = sizeof(uint32_t);
681   constexpr uint32_t AugmentationStringSizeLenght = sizeof(uint32_t);
682   return VersionLength + PaddingLength + CompUnitCountLength +
683          LocalTypeUnitCountLength + ForeignTypeUnitCountLength +
684          BucketCountLength + NameCountLength + AbbrevTableSizeLength +
685          AugmentationStringSizeLenght;
686 }
687 
688 void DWARF5AcceleratorTable::emitHeader() const {
689   constexpr uint32_t HeaderSize = getDebugNamesHeaderSize();
690   // Header Length
691   support::endian::write(*FullTableStream,
692                          static_cast<uint32_t>(HeaderSize + StrBuffer->size() +
693                                                AugmentationStringSize),
694                          llvm::endianness::little);
695   // Version
696   support::endian::write(*FullTableStream, static_cast<uint16_t>(5),
697                          llvm::endianness::little);
698   // Padding
699   support::endian::write(*FullTableStream, static_cast<uint16_t>(0),
700                          llvm::endianness::little);
701   // Compilation Unit Count
702   support::endian::write(*FullTableStream, static_cast<uint32_t>(CUList.size()),
703                          llvm::endianness::little);
704   // Local Type Unit Count
705   support::endian::write(*FullTableStream,
706                          static_cast<uint32_t>(LocalTUList.size()),
707                          llvm::endianness::little);
708   // Foreign Type Unit Count
709   support::endian::write(*FullTableStream,
710                          static_cast<uint32_t>(ForeignTUList.size()),
711                          llvm::endianness::little);
712   // Bucket Count
713   support::endian::write(*FullTableStream, static_cast<uint32_t>(BucketCount),
714                          llvm::endianness::little);
715   // Name Count
716   support::endian::write(*FullTableStream,
717                          static_cast<uint32_t>(Entries.size()),
718                          llvm::endianness::little);
719   // Abbrev Table Size
720   support::endian::write(*FullTableStream,
721                          static_cast<uint32_t>(AbbrevTableSize),
722                          llvm::endianness::little);
723   // Augmentation String Size
724   support::endian::write(*FullTableStream,
725                          static_cast<uint32_t>(AugmentationStringSize),
726                          llvm::endianness::little);
727 
728   emitAugmentationString();
729   FullTableStream->write(StrBuffer->data(), StrBuffer->size());
730 }
731 
732 void DWARF5AcceleratorTable::emitCUList() const {
733   for (const uint32_t CUID : CUList)
734     support::endian::write(*StrStream, CUID, llvm::endianness::little);
735 }
736 void DWARF5AcceleratorTable::emitTUList() const {
737   for (const uint32_t TUID : LocalTUList)
738     support::endian::write(*StrStream, TUID, llvm::endianness::little);
739 
740   for (const uint64_t TUID : ForeignTUList)
741     support::endian::write(*StrStream, TUID, llvm::endianness::little);
742 }
743 void DWARF5AcceleratorTable::emitBuckets() const {
744   uint32_t Index = 1;
745   for (const auto &Bucket : enumerate(getBuckets())) {
746     const uint32_t TempIndex = Bucket.value().empty() ? 0 : Index;
747     support::endian::write(*StrStream, TempIndex, llvm::endianness::little);
748     Index += Bucket.value().size();
749   }
750 }
751 void DWARF5AcceleratorTable::emitHashes() const {
752   for (const auto &Bucket : getBuckets()) {
753     for (const DWARF5AcceleratorTable::HashData *Hash : Bucket)
754       support::endian::write(*StrStream, Hash->HashValue,
755                              llvm::endianness::little);
756   }
757 }
758 void DWARF5AcceleratorTable::emitStringOffsets() const {
759   for (const auto &Bucket : getBuckets()) {
760     for (const DWARF5AcceleratorTable::HashData *Hash : Bucket)
761       support::endian::write(*StrStream, static_cast<uint32_t>(Hash->StrOffset),
762                              llvm::endianness::little);
763   }
764 }
765 void DWARF5AcceleratorTable::emitOffsets() const {
766   for (const auto &Bucket : getBuckets()) {
767     for (const DWARF5AcceleratorTable::HashData *Hash : Bucket)
768       support::endian::write(*StrStream,
769                              static_cast<uint32_t>(Hash->EntryOffset),
770                              llvm::endianness::little);
771   }
772 }
773 void DWARF5AcceleratorTable::emitAbbrevs() {
774   const uint32_t AbbrevTableStart = StrBuffer->size();
775   for (const auto *Abbrev : AbbreviationsVector) {
776     encodeULEB128(Abbrev->getNumber(), *StrStream);
777     encodeULEB128(Abbrev->getDieTag(), *StrStream);
778     for (const auto &AttrEnc : Abbrev->getAttributes()) {
779       encodeULEB128(AttrEnc.Index, *StrStream);
780       encodeULEB128(AttrEnc.Form, *StrStream);
781     }
782     encodeULEB128(0, *StrStream);
783     encodeULEB128(0, *StrStream);
784   }
785   encodeULEB128(0, *StrStream);
786   AbbrevTableSize = StrBuffer->size() - AbbrevTableStart;
787 }
788 void DWARF5AcceleratorTable::emitData() {
789   StrStream->write(EntriesBuffer->data(), EntriesBuffer->size());
790 }
791 void DWARF5AcceleratorTable::emitAugmentationString() const {
792   FullTableStream->write(AugStringBuffer->data(), AugStringBuffer->size());
793 }
794 void DWARF5AcceleratorTable::emitAccelTable() {
795   if (!NeedToCreate)
796     return;
797   finalize();
798   populateAbbrevsMap();
799   writeEntries();
800   writeAugmentationString();
801   emitCUList();
802   emitTUList();
803   emitBuckets();
804   emitHashes();
805   emitStringOffsets();
806   emitOffsets();
807   emitAbbrevs();
808   emitData();
809   emitHeader();
810 }
811 } // namespace bolt
812 } // namespace llvm
813