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       return true;
 148   return false;
 149 }
 150
 151 bool static canProcess(const DWARFUnit &Unit, const DIE &Die,
 152                        std::string &NameToUse, const bool TagsOnly) {
 153   if (Die.findAttribute(dwarf::Attribute::DW_AT_declaration))
 154     return false;
 155   switch (Die.getTag()) {
 156   case dwarf::DW_TAG_base_type:
 157   case dwarf::DW_TAG_class_type:
 158   case dwarf::DW_TAG_enumeration_type:
 159   case dwarf::DW_TAG_imported_declaration:
 160   case dwarf::DW_TAG_pointer_type:
 161   case dwarf::DW_TAG_structure_type:
 162   case dwarf::DW_TAG_typedef:
 163   case dwarf::DW_TAG_unspecified_type:
 164     if (TagsOnly || Die.findAttribute(dwarf::Attribute::DW_AT_name))
 165       return true;
 166     return false;
 167   case dwarf::DW_TAG_namespace:
 168     // According to DWARF5 spec namespaces without DW_AT_name needs to have
 169     // "(anonymous namespace)"
 170     if (!Die.findAttribute(dwarf::Attribute::DW_AT_name))
 171       NameToUse = "(anonymous namespace)";
 172     return true;
 173   case dwarf::DW_TAG_inlined_subroutine:
 174   case dwarf::DW_TAG_label:
 175   case dwarf::DW_TAG_subprogram:
 176     if (TagsOnly || Die.findAttribute(dwarf::Attribute::DW_AT_low_pc) ||
 177         Die.findAttribute(dwarf::Attribute::DW_AT_high_pc) ||
 178         Die.findAttribute(dwarf::Attribute::DW_AT_ranges) ||
 179         Die.findAttribute(dwarf::Attribute::DW_AT_entry_pc))
 180       return true;
 181     return false;
 182   case dwarf::DW_TAG_variable:
 183     return TagsOnly || shouldIncludeVariable(Unit, Die);
 184   default:
 185     break;
 186   }
 187   return false;
 188 }
 189
 190 bool DWARF5AcceleratorTable::canGenerateEntryWithCrossCUReference(
 191     const DWARFUnit &Unit, const DIE &Die,
 192     const DWARFAbbreviationDeclaration::AttributeSpec &AttrSpec) {
 193   if (!isCreated())
 194     return false;
 195   std::string NameToUse = "";
 196   if (!canProcess(Unit, Die, NameToUse, true))
 197     return false;
 198   return (AttrSpec.Attr == dwarf::Attribute::DW_AT_abstract_origin ||
 199           AttrSpec.Attr == dwarf::Attribute::DW_AT_specification) &&
 200          AttrSpec.Form == dwarf::DW_FORM_ref_addr;
 201 }
 202 /// Returns name offset in String Offset section.
 203 static uint64_t getNameOffset(BinaryContext &BC, DWARFUnit &Unit,
 204                               const uint64_t Index) {
 205   const DWARFSection &StrOffsetsSection = Unit.getStringOffsetSection();
 206   const std::optional<StrOffsetsContributionDescriptor> &Contr =
 207       Unit.getStringOffsetsTableContribution();
 208   if (!Contr) {
 209     BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not get "
 210                  "StringOffsetsTableContribution for unit at offset: "
 211               << Twine::utohexstr(Unit.getOffset()) << ".\n";
 212     return 0;
 213   }
 214
 215   const uint8_t DwarfOffsetByteSize = Contr->getDwarfOffsetByteSize();
 216   return support::endian::read32le(StrOffsetsSection.Data.data() + Contr->Base +
 217                                    Index * DwarfOffsetByteSize);
 218 }
 219
 220 static uint64_t getEntryID(const BOLTDWARF5AccelTableData &Entry) {
 221   return reinterpret_cast<uint64_t>(&Entry);
 222 }
 223
 224 std::optional<BOLTDWARF5AccelTableData *>
 225 DWARF5AcceleratorTable::addAccelTableEntry(
 226     DWARFUnit &Unit, const DIE &Die, const std::optional<uint64_t> &DWOID,
 227     const uint32_t NumberParentsInChain,
 228     std::optional<BOLTDWARF5AccelTableData *> &Parent) {
 229   if (Unit.getVersion() < 5 || !NeedToCreate)
 230     return std::nullopt;
 231   std::string NameToUse = "";
 232
 233   auto getUnitID = [&](const DWARFUnit &Unit, bool &IsTU,
 234                        uint32_t &DieTag) -> uint32_t {
 235     IsTU = Unit.isTypeUnit();
 236     DieTag = Die.getTag();
 237     if (IsTU) {
 238       if (DWOID) {
 239         const uint64_t TUHash = cast<DWARFTypeUnit>(&Unit)->getTypeHash();
 240         auto Iter = TUHashToIndexMap.find(TUHash);
 241         assert(Iter != TUHashToIndexMap.end() &&
 242                "Could not find TU hash in map");
 243         return Iter->second;
 244       }
 245       return LocalTUList.size() - 1;
 246     }
 247     return CUList.size() - 1;
 248   };
 249
 250   if (!canProcess(Unit, Die, NameToUse, false))
 251     return std::nullopt;
 252
 253   // Addes a Unit to either CU, LocalTU or ForeignTU list the first time we
 254   // encounter it.
 255   // Invoking it here so that we don't add Units that don't have any entries.
 256   if (&Unit != CurrentUnit) {
 257     CurrentUnit = &Unit;
 258     addUnit(Unit, DWOID);
 259   }
 260
 261   auto getName = [&](DIEValue ValName) -> std::optional<std::string> {
 262     if ((!ValName || ValName.getForm() == dwarf::DW_FORM_string) &&
 263         NameToUse.empty())
 264       return std::nullopt;
 265     std::string Name = "";
 266     uint64_t NameIndexOffset = 0;
 267     if (NameToUse.empty()) {
 268       NameIndexOffset = ValName.getDIEInteger().getValue();
 269       if (ValName.getForm() != dwarf::DW_FORM_strp)
 270         NameIndexOffset = getNameOffset(BC, Unit, NameIndexOffset);
 271       // Counts on strings end with '\0'.
 272       Name = std::string(&StrSection.data()[NameIndexOffset]);
 273     } else {
 274       Name = NameToUse;
 275     }
 276     auto &It = Entries[Name];
 277     if (It.Values.empty()) {
 278       if (DWOID && NameToUse.empty()) {
 279         // For DWO Unit the offset is in the .debug_str.dwo section.
 280         // Need to find offset for the name in the .debug_str section.
 281         llvm::hash_code Hash = llvm::hash_value(llvm::StringRef(Name));
 282         auto ItCache = StrCacheToOffsetMap.find(Hash);
 283         if (ItCache == StrCacheToOffsetMap.end())
 284           NameIndexOffset = MainBinaryStrWriter.addString(Name);
 285         else
 286           NameIndexOffset = ItCache->second;
 287       }
 288       if (!NameToUse.empty())
 289         NameIndexOffset = MainBinaryStrWriter.addString(Name);
 290       It.StrOffset = NameIndexOffset;
 291       // This the same hash function used in DWARF5AccelTableData.
 292       It.HashValue = caseFoldingDjbHash(Name);
 293     }
 294     return Name;
 295   };
 296
 297   auto addEntry =
 298       [&](DIEValue ValName) -> std::optional<BOLTDWARF5AccelTableData *> {
 299     std::optional<std::string> Name = getName(ValName);
 300     if (!Name)
 301       return std::nullopt;
 302
 303     auto &It = Entries[*Name];
 304     bool IsTU = false;
 305     uint32_t DieTag = 0;
 306     uint32_t UnitID = getUnitID(Unit, IsTU, DieTag);
 307     std::optional<unsigned> SecondIndex = std::nullopt;
 308     if (IsTU && DWOID) {
 309       auto Iter = CUOffsetsToPatch.find(*DWOID);
 310       if (Iter == CUOffsetsToPatch.end())
 311         BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not find "
 312                      "DWO ID in CU offsets for second Unit Index "
 313                   << *Name << ". For DIE at offset: "
 314                   << Twine::utohexstr(CurrentUnitOffset + Die.getOffset())
 315                   << ".\n";
 316       SecondIndex = Iter->second;
 317     }
 318     std::optional<uint64_t> ParentOffset =
 319         (Parent ? std::optional<uint64_t>(getEntryID(**Parent)) : std::nullopt);
 320     // This will be populated later in writeEntry.
 321     // This way only parent entries get tracked.
 322     // Keeping memory footprint down.
 323     if (ParentOffset)
 324       EntryRelativeOffsets.insert({*ParentOffset, 0});
 325     bool IsParentRoot = false;
 326     // If there is no parent and no valid Entries in parent chain this is a root
 327     // to be marked with a flag.
 328     if (!Parent && !NumberParentsInChain)
 329       IsParentRoot = true;
 330     It.Values.push_back(new (Allocator) BOLTDWARF5AccelTableData(
 331         Die.getOffset(), ParentOffset, DieTag, UnitID, IsParentRoot, IsTU,
 332         SecondIndex));
 333     return It.Values.back();
 334   };
 335
 336   // Minor optimization not to add entry twice for DW_TAG_namespace if it has no
 337   // DW_AT_name.
 338   if (!(Die.getTag() == dwarf::DW_TAG_namespace &&
 339         !Die.findAttribute(dwarf::Attribute::DW_AT_name)))
 340     addEntry(Die.findAttribute(dwarf::Attribute::DW_AT_linkage_name));
 341   // For the purposes of determining whether a debugging information entry has a
 342   // particular attribute (such as DW_AT_name), if debugging information entry A
 343   // has a DW_AT_specification or DW_AT_abstract_origin attribute pointing to
 344   // another debugging information entry B, any attributes of B are considered
 345   // to be part of A.
 346   auto processReferencedDie = [&](const dwarf::Attribute &Attr)
 347       -> std::optional<BOLTDWARF5AccelTableData *> {
 348     const DIEValue Value = Die.findAttribute(Attr);
 349     if (!Value)
 350       return std::nullopt;
 351     const DIE *EntryDie = nullptr;
 352     if (Value.getForm() == dwarf::DW_FORM_ref_addr) {
 353       auto Iter = CrossCUDies.find(Value.getDIEInteger().getValue());
 354       if (Iter == CrossCUDies.end()) {
 355         BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not find "
 356                      "referenced DIE in CrossCUDies for "
 357                   << Twine::utohexstr(Value.getDIEInteger().getValue())
 358                   << ".\n";
 359         return std::nullopt;
 360       }
 361       EntryDie = Iter->second;
 362     } else {
 363       const DIEEntry &DIEENtry = Value.getDIEEntry();
 364       EntryDie = &DIEENtry.getEntry();
 365     }
 366
 367     addEntry(EntryDie->findAttribute(dwarf::Attribute::DW_AT_linkage_name));
 368     return addEntry(EntryDie->findAttribute(dwarf::Attribute::DW_AT_name));
 369   };
 370
 371   if (std::optional<BOLTDWARF5AccelTableData *> Entry =
 372           processReferencedDie(dwarf::Attribute::DW_AT_abstract_origin))
 373     return *Entry;
 374   if (std::optional<BOLTDWARF5AccelTableData *> Entry =
 375           processReferencedDie(dwarf::Attribute::DW_AT_specification))
 376     return *Entry;
 377
 378   return addEntry(Die.findAttribute(dwarf::Attribute::DW_AT_name));
 379 }
 380
 381 /// Algorithm from llvm implementation.
 382 void DWARF5AcceleratorTable::computeBucketCount() {
 383   // First get the number of unique hashes.
 384   std::vector<uint32_t> Uniques;
 385   Uniques.reserve(Entries.size());
 386   for (const auto &E : Entries)
 387     Uniques.push_back(E.second.HashValue);
 388   array_pod_sort(Uniques.begin(), Uniques.end());
 389   std::vector<uint32_t>::iterator P =
 390       std::unique(Uniques.begin(), Uniques.end());
 391
 392   UniqueHashCount = std::distance(Uniques.begin(), P);
 393
 394   if (UniqueHashCount > 1024)
 395     BucketCount = UniqueHashCount / 4;
 396   else if (UniqueHashCount > 16)
 397     BucketCount = UniqueHashCount / 2;
 398   else
 399     BucketCount = std::max<uint32_t>(UniqueHashCount, 1);
 400 }
 401
 402 /// Bucket code as in: AccelTableBase::finalize()
 403 void DWARF5AcceleratorTable::finalize() {
 404   if (!NeedToCreate)
 405     return;
 406   // Figure out how many buckets we need, then compute the bucket contents and
 407   // the final ordering. The hashes and offsets can be emitted by walking these
 408   // data structures.
 409   computeBucketCount();
 410
 411   // Compute bucket contents and final ordering.
 412   Buckets.resize(BucketCount);
 413   for (auto &E : Entries) {
 414     uint32_t Bucket = E.second.HashValue % BucketCount;
 415     Buckets[Bucket].push_back(&E.second);
 416   }
 417
 418   // Sort the contents of the buckets by hash value so that hash collisions end
 419   // up together. Stable sort makes testing easier and doesn't cost much more.
 420   for (HashList &Bucket : Buckets) {
 421     llvm::stable_sort(Bucket, [](const HashData *LHS, const HashData *RHS) {
 422       return LHS->HashValue < RHS->HashValue;
 423     });
 424     for (HashData *H : Bucket)
 425       llvm::stable_sort(H->Values, [](const BOLTDWARF5AccelTableData *LHS,
 426                                       const BOLTDWARF5AccelTableData *RHS) {
 427         return LHS->getDieOffset() < RHS->getDieOffset();
 428       });
 429   }
 430
 431   CUIndexForm = DIEInteger::BestForm(/*IsSigned*/ false, CUList.size() - 1);
 432   TUIndexForm = DIEInteger::BestForm(
 433       /*IsSigned*/ false, LocalTUList.size() + ForeignTUList.size() - 1);
 434   const dwarf::FormParams FormParams{5, 4, dwarf::DwarfFormat::DWARF32, false};
 435   CUIndexEncodingSize = *dwarf::getFixedFormByteSize(CUIndexForm, FormParams);
 436   TUIndexEncodingSize = *dwarf::getFixedFormByteSize(TUIndexForm, FormParams);
 437 }
 438
 439 std::optional<DWARF5AccelTable::UnitIndexAndEncoding>
 440 DWARF5AcceleratorTable::getIndexForEntry(
 441     const BOLTDWARF5AccelTableData &Value) const {
 442   // The foreign TU list immediately follows the local TU list and they both
 443   // use the same index, so that if there are N local TU entries, the index for
 444   // the first foreign TU is N.
 445   if (Value.isTU())
 446     return {{(Value.getSecondUnitID() ? (unsigned)LocalTUList.size() : 0) +
 447                  Value.getUnitID(),
 448              {dwarf::DW_IDX_type_unit, TUIndexForm}}};
 449   if (CUList.size() > 1)
 450     return {{Value.getUnitID(), {dwarf::DW_IDX_compile_unit, CUIndexForm}}};
 451   return std::nullopt;
 452 }
 453
 454 std::optional<DWARF5AccelTable::UnitIndexAndEncoding>
 455 DWARF5AcceleratorTable::getSecondIndexForEntry(
 456     const BOLTDWARF5AccelTableData &Value) const {
 457   if (Value.isTU() && CUList.size() > 1 && Value.getSecondUnitID())
 458     return {
 459         {*Value.getSecondUnitID(), {dwarf::DW_IDX_compile_unit, CUIndexForm}}};
 460   return std::nullopt;
 461 }
 462
 463 void DWARF5AcceleratorTable::populateAbbrevsMap() {
 464   for (auto &Bucket : getBuckets()) {
 465     for (DWARF5AcceleratorTable::HashData *Hash : Bucket) {
 466       for (BOLTDWARF5AccelTableData *Value : Hash->Values) {
 467         const std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet =
 468             getIndexForEntry(*Value);
 469         // For entries that need to refer to the foreign type units and to
 470         // the CU.
 471         const std::optional<DWARF5AccelTable::UnitIndexAndEncoding>
 472             SecondEntryRet = getSecondIndexForEntry(*Value);
 473         DebugNamesAbbrev Abbrev(Value->getDieTag());
 474         if (EntryRet)
 475           Abbrev.addAttribute(EntryRet->Encoding);
 476         if (SecondEntryRet)
 477           Abbrev.addAttribute(SecondEntryRet->Encoding);
 478         Abbrev.addAttribute({dwarf::DW_IDX_die_offset, dwarf::DW_FORM_ref4});
 479         if (std::optional<uint64_t> Offset = Value->getParentDieOffset())
 480           Abbrev.addAttribute({dwarf::DW_IDX_parent, dwarf::DW_FORM_ref4});
 481         else if (Value->isParentRoot())
 482           Abbrev.addAttribute(
 483               {dwarf::DW_IDX_parent, dwarf::DW_FORM_flag_present});
 484         FoldingSetNodeID ID;
 485         Abbrev.Profile(ID);
 486         void *InsertPos;
 487         if (DebugNamesAbbrev *Existing =
 488                 AbbreviationsSet.FindNodeOrInsertPos(ID, InsertPos)) {
 489           Value->setAbbrevNumber(Existing->getNumber());
 490           continue;
 491         }
 492         DebugNamesAbbrev *NewAbbrev =
 493             new (Alloc) DebugNamesAbbrev(std::move(Abbrev));
 494         AbbreviationsVector.push_back(NewAbbrev);
 495         NewAbbrev->setNumber(AbbreviationsVector.size());
 496         AbbreviationsSet.InsertNode(NewAbbrev, InsertPos);
 497         Value->setAbbrevNumber(NewAbbrev->getNumber());
 498       }
 499     }
 500   }
 501 }
 502
 503 void DWARF5AcceleratorTable::writeEntry(BOLTDWARF5AccelTableData &Entry) {
 504   const uint64_t EntryID = getEntryID(Entry);
 505   if (EntryRelativeOffsets.find(EntryID) != EntryRelativeOffsets.end())
 506     EntryRelativeOffsets[EntryID] = EntriesBuffer->size();
 507
 508   const std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet =
 509       getIndexForEntry(Entry);
 510   // For forgeign type (FTU) units that need to refer to the FTU and to the CU.
 511   const std::optional<DWARF5AccelTable::UnitIndexAndEncoding> SecondEntryRet =
 512       getSecondIndexForEntry(Entry);
 513   const unsigned AbbrevIndex = Entry.getAbbrevNumber() - 1;
 514   assert(AbbrevIndex < AbbreviationsVector.size() &&
 515          "Entry abbrev index is outside of abbreviations vector range.");
 516   const DebugNamesAbbrev *Abbrev = AbbreviationsVector[AbbrevIndex];
 517   encodeULEB128(Entry.getAbbrevNumber(), *Entriestream);
 518   auto writeIndex = [&](uint32_t Index, uint32_t IndexSize) -> void {
 519     switch (IndexSize) {
 520     default:
 521       llvm_unreachable("Unsupported Index Size!");
 522       break;
 523     case 1:
 524       support::endian::write(*Entriestream, static_cast<uint8_t>(Index),
 525                              llvm::endianness::little);
 526       break;
 527     case 2:
 528       support::endian::write(*Entriestream, static_cast<uint16_t>(Index),
 529                              llvm::endianness::little);
 530       break;
 531     case 4:
 532       support::endian::write(*Entriestream, static_cast<uint32_t>(Index),
 533                              llvm::endianness::little);
 534       break;
 535     };
 536   };
 537
 538   for (const DebugNamesAbbrev::AttributeEncoding &AttrEnc :
 539        Abbrev->getAttributes()) {
 540     switch (AttrEnc.Index) {
 541     default: {
 542       llvm_unreachable("Unexpected index attribute!");
 543       break;
 544     }
 545     case dwarf::DW_IDX_compile_unit: {
 546       const unsigned CUIndex =
 547           SecondEntryRet ? SecondEntryRet->Index : EntryRet->Index;
 548       writeIndex(CUIndex, CUIndexEncodingSize);
 549       break;
 550     }
 551     case dwarf::DW_IDX_type_unit: {
 552       writeIndex(EntryRet->Index, TUIndexEncodingSize);
 553       break;
 554     }
 555     case dwarf::DW_IDX_die_offset: {
 556       assert(AttrEnc.Form == dwarf::DW_FORM_ref4);
 557       support::endian::write(*Entriestream,
 558                              static_cast<uint32_t>(Entry.getDieOffset()),
 559                              llvm::endianness::little);
 560       break;
 561     }
 562     case dwarf::DW_IDX_parent: {
 563       assert(
 564           (AttrEnc.Form == dwarf::DW_FORM_ref4 && Entry.getParentDieOffset()) ||
 565           AttrEnc.Form == dwarf::DW_FORM_flag_present);
 566       if (std::optional<uint64_t> ParentOffset = Entry.getParentDieOffset()) {
 567         Entry.setPatchOffset(EntriesBuffer->size());
 568         support::endian::write(*Entriestream, static_cast<uint32_t>(UINT32_MAX),
 569                                llvm::endianness::little);
 570       }
 571       break;
 572     }
 573     }
 574   }
 575 }
 576
 577 void DWARF5AcceleratorTable::writeEntries() {
 578   for (auto &Bucket : getBuckets()) {
 579     for (DWARF5AcceleratorTable::HashData *Hash : Bucket) {
 580       Hash->EntryOffset = EntriesBuffer->size();
 581       for (BOLTDWARF5AccelTableData *Value : Hash->Values) {
 582         writeEntry(*Value);
 583       }
 584       support::endian::write(*Entriestream, static_cast<uint8_t>(0),
 585                              llvm::endianness::little);
 586     }
 587   }
 588   // Patching parent offsets.
 589   for (auto &Bucket : getBuckets()) {
 590     for (DWARF5AcceleratorTable::HashData *Hash : Bucket) {
 591       for (BOLTDWARF5AccelTableData *Entry : Hash->Values) {
 592         std::optional<uint64_t> ParentOffset = Entry->getParentDieOffset();
 593         if (!ParentOffset)
 594           continue;
 595         if (const auto Iter = EntryRelativeOffsets.find(*ParentOffset);
 596             Iter != EntryRelativeOffsets.end()) {
 597           const uint64_t PatchOffset = Entry->getPatchOffset();
 598           uint32_t *Ptr = reinterpret_cast<uint32_t *>(
 599               &EntriesBuffer.get()->data()[PatchOffset]);
 600           *Ptr = Iter->second;
 601         } else {
 602           BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not find "
 603                        "entry with offset "
 604                     << *ParentOffset << "\n";
 605         }
 606       }
 607     }
 608   }
 609 }
 610
 611 void DWARF5AcceleratorTable::writeAugmentationString() {
 612   // String needs to be multiple of 4 bytes.
 613   *AugStringtream << "BOLT";
 614   AugmentationStringSize = AugStringBuffer->size();
 615 }
 616
 617 /// Calculates size of .debug_names header without Length field.
 618 static constexpr uint32_t getDebugNamesHeaderSize() {
 619   constexpr uint16_t VersionLength = sizeof(uint16_t);
 620   constexpr uint16_t PaddingLength = sizeof(uint16_t);
 621   constexpr uint32_t CompUnitCountLength = sizeof(uint32_t);
 622   constexpr uint32_t LocalTypeUnitCountLength = sizeof(uint32_t);
 623   constexpr uint32_t ForeignTypeUnitCountLength = sizeof(uint32_t);
 624   constexpr uint32_t BucketCountLength = sizeof(uint32_t);
 625   constexpr uint32_t NameCountLength = sizeof(uint32_t);
 626   constexpr uint32_t AbbrevTableSizeLength = sizeof(uint32_t);
 627   constexpr uint32_t AugmentationStringSizeLenght = sizeof(uint32_t);
 628   return VersionLength + PaddingLength + CompUnitCountLength +
 629          LocalTypeUnitCountLength + ForeignTypeUnitCountLength +
 630          BucketCountLength + NameCountLength + AbbrevTableSizeLength +
 631          AugmentationStringSizeLenght;
 632 }
 633
 634 void DWARF5AcceleratorTable::emitHeader() const {
 635   constexpr uint32_t HeaderSize = getDebugNamesHeaderSize();
 636   // Header Length
 637   support::endian::write(*FullTableStream,
 638                          static_cast<uint32_t>(HeaderSize + StrBuffer->size() +
 639                                                AugmentationStringSize),
 640                          llvm::endianness::little);
 641   // Version
 642   support::endian::write(*FullTableStream, static_cast<uint16_t>(5),
 643                          llvm::endianness::little);
 644   // Padding
 645   support::endian::write(*FullTableStream, static_cast<uint16_t>(0),
 646                          llvm::endianness::little);
 647   // Compilation Unit Count
 648   support::endian::write(*FullTableStream, static_cast<uint32_t>(CUList.size()),
 649                          llvm::endianness::little);
 650   // Local Type Unit Count
 651   support::endian::write(*FullTableStream,
 652                          static_cast<uint32_t>(LocalTUList.size()),
 653                          llvm::endianness::little);
 654   // Foreign Type Unit Count
 655   support::endian::write(*FullTableStream,
 656                          static_cast<uint32_t>(ForeignTUList.size()),
 657                          llvm::endianness::little);
 658   // Bucket Count
 659   support::endian::write(*FullTableStream, static_cast<uint32_t>(BucketCount),
 660                          llvm::endianness::little);
 661   // Name Count
 662   support::endian::write(*FullTableStream,
 663                          static_cast<uint32_t>(Entries.size()),
 664                          llvm::endianness::little);
 665   // Abbrev Table Size
 666   support::endian::write(*FullTableStream,
 667                          static_cast<uint32_t>(AbbrevTableSize),
 668                          llvm::endianness::little);
 669   // Augmentation String Size
 670   support::endian::write(*FullTableStream,
 671                          static_cast<uint32_t>(AugmentationStringSize),
 672                          llvm::endianness::little);
 673
 674   emitAugmentationString();
 675   FullTableStream->write(StrBuffer->data(), StrBuffer->size());
 676 }
 677
 678 void DWARF5AcceleratorTable::emitCUList() const {
 679   for (const uint32_t CUID : CUList)
 680     support::endian::write(*StrStream, CUID, llvm::endianness::little);
 681 }
 682 void DWARF5AcceleratorTable::emitTUList() const {
 683   for (const uint32_t TUID : LocalTUList)
 684     support::endian::write(*StrStream, TUID, llvm::endianness::little);
 685
 686   for (const uint64_t TUID : ForeignTUList)
 687     support::endian::write(*StrStream, TUID, llvm::endianness::little);
 688 }
 689 void DWARF5AcceleratorTable::emitBuckets() const {
 690   uint32_t Index = 1;
 691   for (const auto &Bucket : enumerate(getBuckets())) {
 692     const uint32_t TempIndex = Bucket.value().empty() ? 0 : Index;
 693     support::endian::write(*StrStream, TempIndex, llvm::endianness::little);
 694     Index += Bucket.value().size();
 695   }
 696 }
 697 void DWARF5AcceleratorTable::emitHashes() const {
 698   for (const auto &Bucket : getBuckets()) {
 699     for (const DWARF5AcceleratorTable::HashData *Hash : Bucket)
 700       support::endian::write(*StrStream, Hash->HashValue,
 701                              llvm::endianness::little);
 702   }
 703 }
 704 void DWARF5AcceleratorTable::emitStringOffsets() const {
 705   for (const auto &Bucket : getBuckets()) {
 706     for (const DWARF5AcceleratorTable::HashData *Hash : Bucket)
 707       support::endian::write(*StrStream, static_cast<uint32_t>(Hash->StrOffset),
 708                              llvm::endianness::little);
 709   }
 710 }
 711 void DWARF5AcceleratorTable::emitOffsets() const {
 712   for (const auto &Bucket : getBuckets()) {
 713     for (const DWARF5AcceleratorTable::HashData *Hash : Bucket)
 714       support::endian::write(*StrStream,
 715                              static_cast<uint32_t>(Hash->EntryOffset),
 716                              llvm::endianness::little);
 717   }
 718 }
 719 void DWARF5AcceleratorTable::emitAbbrevs() {
 720   const uint32_t AbbrevTableStart = StrBuffer->size();
 721   for (const auto *Abbrev : AbbreviationsVector) {
 722     encodeULEB128(Abbrev->getNumber(), *StrStream);
 723     encodeULEB128(Abbrev->getDieTag(), *StrStream);
 724     for (const auto &AttrEnc : Abbrev->getAttributes()) {
 725       encodeULEB128(AttrEnc.Index, *StrStream);
 726       encodeULEB128(AttrEnc.Form, *StrStream);
 727     }
 728     encodeULEB128(0, *StrStream);
 729     encodeULEB128(0, *StrStream);
 730   }
 731   encodeULEB128(0, *StrStream);
 732   AbbrevTableSize = StrBuffer->size() - AbbrevTableStart;
 733 }
 734 void DWARF5AcceleratorTable::emitData() {
 735   StrStream->write(EntriesBuffer->data(), EntriesBuffer->size());
 736 }
 737 void DWARF5AcceleratorTable::emitAugmentationString() const {
 738   FullTableStream->write(AugStringBuffer->data(), AugStringBuffer->size());
 739 }
 740 void DWARF5AcceleratorTable::emitAccelTable() {
 741   if (!NeedToCreate)
 742     return;
 743   finalize();
 744   populateAbbrevsMap();
 745   writeEntries();
 746   writeAugmentationString();
 747   emitCUList();
 748   emitTUList();
 749   emitBuckets();
 750   emitHashes();
 751   emitStringOffsets();
 752   emitOffsets();
 753   emitAbbrevs();
 754   emitData();
 755   emitHeader();
 756 }
 757 } // namespace bolt
 758 } // namespace llvm