bolt/lib/Core/DebugNames.cpp

   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