bolt/lib/Core/DIEBuilder.cpp

   1 //===- bolt/Core/DIEBuilder.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/DIEBuilder.h"
  10 #include "bolt/Core/BinaryContext.h"
  11 #include "bolt/Core/ParallelUtilities.h"
  12 #include "llvm/ADT/StringRef.h"
  13 #include "llvm/BinaryFormat/Dwarf.h"
  14 #include "llvm/CodeGen/DIE.h"
  15 #include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h"
  16 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
  17 #include "llvm/DebugInfo/DWARF/DWARFExpression.h"
  18 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
  19 #include "llvm/DebugInfo/DWARF/DWARFTypeUnit.h"
  20 #include "llvm/DebugInfo/DWARF/DWARFUnit.h"
  21 #include "llvm/DebugInfo/DWARF/DWARFUnitIndex.h"
  22 #include "llvm/Support/Casting.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/ErrorHandling.h"
  25 #include "llvm/Support/FileSystem.h"
  26 #include "llvm/Support/LEB128.h"
  27
  28 #include <algorithm>
  29 #include <cstdint>
  30 #include <memory>
  31 #include <mutex>
  32 #include <optional>
  33 #include <unordered_map>
  34 #include <utility>
  35 #include <vector>
  36
  37 #undef DEBUG_TYPE
  38 #define DEBUG_TYPE "bolt"
  39 namespace opts {
  40 extern cl::opt<unsigned> Verbosity;
  41 }
  42 namespace llvm {
  43 namespace bolt {
  44
  45 /// Returns DWO Name to be used to update DW_AT_dwo_name/DW_AT_GNU_dwo_name
  46 /// either in CU or TU unit die. Handles case where user specifies output DWO
  47 /// directory, and there are duplicate names. Assumes DWO ID is unique.
  48 static std::string
  49 getDWOName(llvm::DWARFUnit &CU,
  50            std::unordered_map<std::string, uint32_t> &NameToIndexMap,
  51            std::optional<StringRef> &DwarfOutputPath) {
  52   assert(CU.getDWOId() && "DWO ID not found.");
  53   std::string DWOName = dwarf::toString(
  54       CU.getUnitDIE().find({dwarf::DW_AT_dwo_name, dwarf::DW_AT_GNU_dwo_name}),
  55       "");
  56   assert(!DWOName.empty() &&
  57          "DW_AT_dwo_name/DW_AT_GNU_dwo_name does not exist.");
  58   if (DwarfOutputPath) {
  59     DWOName = std::string(sys::path::filename(DWOName));
  60     auto Iter = NameToIndexMap.find(DWOName);
  61     if (Iter == NameToIndexMap.end())
  62       Iter = NameToIndexMap.insert({DWOName, 0}).first;
  63     DWOName.append(std::to_string(Iter->second));
  64     ++Iter->second;
  65   }
  66   DWOName.append(".dwo");
  67   return DWOName;
  68 }
  69
  70 /// Adds a \p Str to .debug_str section.
  71 /// Uses \p AttrInfoVal to either update entry in a DIE for legacy DWARF using
  72 /// \p DebugInfoPatcher, or for DWARF5 update an index in .debug_str_offsets
  73 /// for this contribution of \p Unit.
  74 static void addStringHelper(DebugStrOffsetsWriter &StrOffstsWriter,
  75                             DebugStrWriter &StrWriter, DIEBuilder &DIEBldr,
  76                             DIE &Die, const DWARFUnit &Unit,
  77                             DIEValue &DIEAttrInfo, StringRef Str) {
  78   uint32_t NewOffset = StrWriter.addString(Str);
  79   if (Unit.getVersion() >= 5) {
  80     StrOffstsWriter.updateAddressMap(DIEAttrInfo.getDIEInteger().getValue(),
  81                                      NewOffset);
  82     return;
  83   }
  84   DIEBldr.replaceValue(&Die, DIEAttrInfo.getAttribute(), DIEAttrInfo.getForm(),
  85                        DIEInteger(NewOffset));
  86 }
  87
  88 std::string DIEBuilder::updateDWONameCompDir(
  89     DebugStrOffsetsWriter &StrOffstsWriter, DebugStrWriter &StrWriter,
  90     DWARFUnit &SkeletonCU, std::optional<StringRef> DwarfOutputPath,
  91     std::optional<StringRef> DWONameToUse) {
  92   DIE &UnitDIE = *getUnitDIEbyUnit(SkeletonCU);
  93   DIEValue DWONameAttrInfo = UnitDIE.findAttribute(dwarf::DW_AT_dwo_name);
  94   if (!DWONameAttrInfo)
  95     DWONameAttrInfo = UnitDIE.findAttribute(dwarf::DW_AT_GNU_dwo_name);
  96   if (!DWONameAttrInfo)
  97     return "";
  98   std::string ObjectName;
  99   if (DWONameToUse)
 100     ObjectName = *DWONameToUse;
 101   else
 102     ObjectName = getDWOName(SkeletonCU, NameToIndexMap, DwarfOutputPath);
 103   addStringHelper(StrOffstsWriter, StrWriter, *this, UnitDIE, SkeletonCU,
 104                   DWONameAttrInfo, ObjectName);
 105
 106   DIEValue CompDirAttrInfo = UnitDIE.findAttribute(dwarf::DW_AT_comp_dir);
 107   assert(CompDirAttrInfo && "DW_AT_comp_dir is not in Skeleton CU.");
 108
 109   if (DwarfOutputPath) {
 110     if (!sys::fs::exists(*DwarfOutputPath))
 111       sys::fs::create_directory(*DwarfOutputPath);
 112     addStringHelper(StrOffstsWriter, StrWriter, *this, UnitDIE, SkeletonCU,
 113                     CompDirAttrInfo, *DwarfOutputPath);
 114   }
 115   return ObjectName;
 116 }
 117
 118 void DIEBuilder::updateDWONameCompDirForTypes(
 119     DebugStrOffsetsWriter &StrOffstsWriter, DebugStrWriter &StrWriter,
 120     DWARFUnit &Unit, std::optional<StringRef> DwarfOutputPath,
 121     const StringRef DWOName) {
 122   for (DWARFUnit *DU : getState().DWARF5TUVector)
 123     updateDWONameCompDir(StrOffstsWriter, StrWriter, *DU, DwarfOutputPath,
 124                          DWOName);
 125   if (StrOffstsWriter.isStrOffsetsSectionModified())
 126     StrOffstsWriter.finalizeSection(Unit, *this);
 127 }
 128
 129 void DIEBuilder::updateReferences() {
 130   for (auto &[SrcDIEInfo, ReferenceInfo] : getState().AddrReferences) {
 131     DIEInfo *DstDIEInfo = ReferenceInfo.Dst;
 132     DWARFUnitInfo &DstUnitInfo = getUnitInfo(DstDIEInfo->UnitId);
 133     dwarf::Attribute Attr = ReferenceInfo.AttrSpec.Attr;
 134     dwarf::Form Form = ReferenceInfo.AttrSpec.Form;
 135
 136     const uint64_t NewAddr =
 137         DstDIEInfo->Die->getOffset() + DstUnitInfo.UnitOffset;
 138     SrcDIEInfo->Die->replaceValue(getState().DIEAlloc, Attr, Form,
 139                                   DIEInteger(NewAddr));
 140   }
 141
 142   // Handling referenes in location expressions.
 143   for (LocWithReference &LocExpr : getState().LocWithReferencesToProcess) {
 144     SmallVector<uint8_t, 32> Buffer;
 145     DataExtractor Data(StringRef((const char *)LocExpr.BlockData.data(),
 146                                  LocExpr.BlockData.size()),
 147                        LocExpr.U.isLittleEndian(),
 148                        LocExpr.U.getAddressByteSize());
 149     DWARFExpression Expr(Data, LocExpr.U.getAddressByteSize(),
 150                          LocExpr.U.getFormParams().Format);
 151     cloneExpression(Data, Expr, LocExpr.U, Buffer, CloneExpressionStage::PATCH);
 152
 153     DIEValueList *AttrVal;
 154     if (LocExpr.Form == dwarf::DW_FORM_exprloc) {
 155       DIELoc *DL = new (getState().DIEAlloc) DIELoc;
 156       DL->setSize(Buffer.size());
 157       AttrVal = static_cast<DIEValueList *>(DL);
 158     } else {
 159       DIEBlock *DBL = new (getState().DIEAlloc) DIEBlock;
 160       DBL->setSize(Buffer.size());
 161       AttrVal = static_cast<DIEValueList *>(DBL);
 162     }
 163     for (auto Byte : Buffer)
 164       AttrVal->addValue(getState().DIEAlloc, static_cast<dwarf::Attribute>(0),
 165                         dwarf::DW_FORM_data1, DIEInteger(Byte));
 166
 167     DIEValue Value;
 168     if (LocExpr.Form == dwarf::DW_FORM_exprloc)
 169       Value =
 170           DIEValue(dwarf::Attribute(LocExpr.Attr), dwarf::Form(LocExpr.Form),
 171                    static_cast<DIELoc *>(AttrVal));
 172     else
 173       Value =
 174           DIEValue(dwarf::Attribute(LocExpr.Attr), dwarf::Form(LocExpr.Form),
 175                    static_cast<DIEBlock *>(AttrVal));
 176
 177     LocExpr.Die.replaceValue(getState().DIEAlloc, LocExpr.Attr, LocExpr.Form,
 178                              Value);
 179   }
 180
 181   return;
 182 }
 183
 184 uint32_t DIEBuilder::allocDIE(const DWARFUnit &DU, const DWARFDie &DDie,
 185                               BumpPtrAllocator &Alloc, const uint32_t UId) {
 186   DWARFUnitInfo &DWARFUnitInfo = getUnitInfo(UId);
 187   const uint64_t DDieOffset = DDie.getOffset();
 188   if (DWARFUnitInfo.DIEIDMap.count(DDieOffset))
 189     return DWARFUnitInfo.DIEIDMap[DDieOffset];
 190
 191   DIE *Die = DIE::get(Alloc, dwarf::Tag(DDie.getTag()));
 192   // This handles the case where there is a DIE ref which points to
 193   // invalid DIE. This prevents assert when IR is written out.
 194   // Also it makes debugging easier.
 195   // DIE dump is not very useful.
 196   // It's nice to know original offset from which this DIE was constructed.
 197   Die->setOffset(DDie.getOffset());
 198   if (opts::Verbosity >= 1)
 199     getState().DWARFDieAddressesParsed.insert(DDie.getOffset());
 200   const uint32_t DId = DWARFUnitInfo.DieInfoVector.size();
 201   DWARFUnitInfo.DIEIDMap[DDieOffset] = DId;
 202   DWARFUnitInfo.DieInfoVector.emplace_back(
 203       std::make_unique<DIEInfo>(DIEInfo{Die, DId, UId}));
 204   return DId;
 205 }
 206
 207 void DIEBuilder::constructFromUnit(DWARFUnit &DU) {
 208   std::optional<uint32_t> UnitId = getUnitId(DU);
 209   if (!UnitId) {
 210     BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: "
 211               << "Skip Unit at " << Twine::utohexstr(DU.getOffset()) << "\n";
 212     return;
 213   }
 214
 215   const uint32_t UnitHeaderSize = DU.getHeaderSize();
 216   uint64_t DIEOffset = DU.getOffset() + UnitHeaderSize;
 217   uint64_t NextCUOffset = DU.getNextUnitOffset();
 218   DWARFDataExtractor DebugInfoData = DU.getDebugInfoExtractor();
 219   DWARFDebugInfoEntry DIEEntry;
 220   std::vector<DIE *> CurParentDIEStack;
 221   std::vector<uint32_t> Parents;
 222   uint32_t TUTypeOffset = 0;
 223
 224   if (DWARFTypeUnit *TU = dyn_cast_or_null<DWARFTypeUnit>(&DU))
 225     TUTypeOffset = TU->getTypeOffset();
 226
 227   assert(DebugInfoData.isValidOffset(NextCUOffset - 1));
 228   Parents.push_back(UINT32_MAX);
 229   do {
 230     const bool IsTypeDIE = (TUTypeOffset == DIEOffset - DU.getOffset());
 231     if (!DIEEntry.extractFast(DU, &DIEOffset, DebugInfoData, NextCUOffset,
 232                               Parents.back()))
 233       break;
 234
 235     if (const DWARFAbbreviationDeclaration *AbbrDecl =
 236             DIEEntry.getAbbreviationDeclarationPtr()) {
 237       DWARFDie DDie(&DU, &DIEEntry);
 238
 239       DIE *CurDIE = constructDIEFast(DDie, DU, *UnitId);
 240       DWARFUnitInfo &UI = getUnitInfo(*UnitId);
 241       // Can't rely on first element in DieVector due to cross CU forward
 242       // references.
 243       if (!UI.UnitDie)
 244         UI.UnitDie = CurDIE;
 245       if (IsTypeDIE)
 246         getState().TypeDIEMap[&DU] = CurDIE;
 247
 248       if (!CurParentDIEStack.empty())
 249         CurParentDIEStack.back()->addChild(CurDIE);
 250
 251       if (AbbrDecl->hasChildren())
 252         CurParentDIEStack.push_back(CurDIE);
 253     } else {
 254       // NULL DIE: finishes current children scope.
 255       CurParentDIEStack.pop_back();
 256     }
 257   } while (CurParentDIEStack.size() > 0);
 258
 259   getState().CloneUnitCtxMap[*UnitId].IsConstructed = true;
 260 }
 261
 262 DIEBuilder::DIEBuilder(BinaryContext &BC, DWARFContext *DwarfContext,
 263                        DWARF5AcceleratorTable &DebugNamesTable,
 264                        DWARFUnit *SkeletonCU)
 265     : BC(BC), DwarfContext(DwarfContext), SkeletonCU(SkeletonCU),
 266       DebugNamesTable(DebugNamesTable) {}
 267
 268 static unsigned int getCUNum(DWARFContext *DwarfContext, bool IsDWO) {
 269   unsigned int CUNum = IsDWO ? DwarfContext->getNumDWOCompileUnits()
 270                              : DwarfContext->getNumCompileUnits();
 271   CUNum += IsDWO ? DwarfContext->getNumDWOTypeUnits()
 272                  : DwarfContext->getNumTypeUnits();
 273   return CUNum;
 274 }
 275
 276 void DIEBuilder::buildTypeUnits(DebugStrOffsetsWriter *StrOffsetWriter,
 277                                 const bool Init) {
 278   if (Init)
 279     BuilderState.reset(new State());
 280
 281   const DWARFUnitIndex &TUIndex = DwarfContext->getTUIndex();
 282   if (!TUIndex.getRows().empty()) {
 283     for (auto &Row : TUIndex.getRows()) {
 284       uint64_t Signature = Row.getSignature();
 285       // manually populate TypeUnit to UnitVector
 286       DwarfContext->getTypeUnitForHash(DwarfContext->getMaxVersion(), Signature,
 287                                        true);
 288     }
 289   }
 290   const unsigned int CUNum = getCUNum(DwarfContext, isDWO());
 291   getState().CloneUnitCtxMap.resize(CUNum);
 292   DWARFContext::unit_iterator_range CU4TURanges =
 293       isDWO() ? DwarfContext->dwo_types_section_units()
 294               : DwarfContext->types_section_units();
 295
 296   getState().Type = ProcessingType::DWARF4TUs;
 297   for (std::unique_ptr<DWARFUnit> &DU : CU4TURanges)
 298     registerUnit(*DU.get(), false);
 299
 300   for (std::unique_ptr<DWARFUnit> &DU : CU4TURanges)
 301     constructFromUnit(*DU.get());
 302
 303   DWARFContext::unit_iterator_range CURanges =
 304       isDWO() ? DwarfContext->dwo_info_section_units()
 305               : DwarfContext->info_section_units();
 306
 307   // This handles DWARF4 CUs and DWARF5 CU/TUs.
 308   // Creating a vector so that for reference handling only DWARF5 CU/TUs are
 309   // used, and not DWARF4 TUs.
 310   getState().Type = ProcessingType::DWARF5TUs;
 311   for (std::unique_ptr<DWARFUnit> &DU : CURanges) {
 312     if (!DU->isTypeUnit())
 313       continue;
 314     registerUnit(*DU.get(), false);
 315   }
 316
 317   for (DWARFUnit *DU : getState().DWARF5TUVector) {
 318     constructFromUnit(*DU);
 319     if (StrOffsetWriter)
 320       StrOffsetWriter->finalizeSection(*DU, *this);
 321   }
 322 }
 323
 324 void DIEBuilder::buildCompileUnits(const bool Init) {
 325   if (Init)
 326     BuilderState.reset(new State());
 327
 328   unsigned int CUNum = getCUNum(DwarfContext, isDWO());
 329   getState().CloneUnitCtxMap.resize(CUNum);
 330   DWARFContext::unit_iterator_range CURanges =
 331       isDWO() ? DwarfContext->dwo_info_section_units()
 332               : DwarfContext->info_section_units();
 333
 334   // This handles DWARF4 CUs and DWARF5 CU/TUs.
 335   // Creating a vector so that for reference handling only DWARF5 CU/TUs are
 336   // used, and not DWARF4 TUs.getState().DUList
 337   getState().Type = ProcessingType::CUs;
 338   for (std::unique_ptr<DWARFUnit> &DU : CURanges) {
 339     if (DU->isTypeUnit())
 340       continue;
 341     registerUnit(*DU.get(), false);
 342   }
 343
 344   // Using DULIst since it can be modified by cross CU refrence resolution.
 345   for (DWARFUnit *DU : getState().DUList) {
 346     if (DU->isTypeUnit())
 347       continue;
 348     constructFromUnit(*DU);
 349   }
 350 }
 351 void DIEBuilder::buildCompileUnits(const std::vector<DWARFUnit *> &CUs) {
 352   BuilderState.reset(new State());
 353   // Allocating enough for current batch being processed.
 354   // In real use cases we either processing a batch of CUs with no cross
 355   // references, or if they do have them it is due to LTO. With clang they will
 356   // share the same abbrev table. In either case this vector will not grow.
 357   getState().CloneUnitCtxMap.resize(CUs.size());
 358   getState().Type = ProcessingType::CUs;
 359   for (DWARFUnit *CU : CUs)
 360     registerUnit(*CU, false);
 361
 362   for (DWARFUnit *DU : getState().DUList)
 363     constructFromUnit(*DU);
 364 }
 365
 366 void DIEBuilder::buildDWOUnit(DWARFUnit &U) {
 367   BuilderState.release();
 368   BuilderState = std::make_unique<State>();
 369   buildTypeUnits(nullptr, false);
 370   getState().Type = ProcessingType::CUs;
 371   registerUnit(U, false);
 372   constructFromUnit(U);
 373 }
 374
 375 DIE *DIEBuilder::constructDIEFast(DWARFDie &DDie, DWARFUnit &U,
 376                                   uint32_t UnitId) {
 377
 378   std::optional<uint32_t> Idx = getAllocDIEId(U, DDie);
 379   if (Idx) {
 380     DWARFUnitInfo &DWARFUnitInfo = getUnitInfo(UnitId);
 381     DIEInfo &DieInfo = getDIEInfo(UnitId, *Idx);
 382     if (DWARFUnitInfo.IsConstructed && DieInfo.Die)
 383       return DieInfo.Die;
 384   } else {
 385     Idx = allocDIE(U, DDie, getState().DIEAlloc, UnitId);
 386   }
 387
 388   DIEInfo &DieInfo = getDIEInfo(UnitId, *Idx);
 389
 390   uint64_t Offset = DDie.getOffset();
 391   uint64_t NextOffset = Offset;
 392   DWARFDataExtractor Data = U.getDebugInfoExtractor();
 393   DWARFDebugInfoEntry DDIEntry;
 394
 395   if (DDIEntry.extractFast(U, &NextOffset, Data, U.getNextUnitOffset(), 0))
 396     assert(NextOffset - U.getOffset() <= Data.getData().size() &&
 397            "NextOffset OOB");
 398
 399   SmallString<40> DIECopy(Data.getData().substr(Offset, NextOffset - Offset));
 400   Data =
 401       DWARFDataExtractor(DIECopy, Data.isLittleEndian(), Data.getAddressSize());
 402
 403   const DWARFAbbreviationDeclaration *Abbrev =
 404       DDie.getAbbreviationDeclarationPtr();
 405   uint64_t AttrOffset = getULEB128Size(Abbrev->getCode());
 406
 407   using AttrSpec = DWARFAbbreviationDeclaration::AttributeSpec;
 408   for (const AttrSpec &AttrSpec : Abbrev->attributes()) {
 409     DWARFFormValue Val(AttrSpec.Form);
 410     Val.extractValue(Data, &AttrOffset, U.getFormParams(), &U);
 411     cloneAttribute(*DieInfo.Die, DDie, U, Val, AttrSpec);
 412   }
 413   return DieInfo.Die;
 414 }
 415
 416 static DWARFUnit *
 417 getUnitForOffset(DIEBuilder &Builder, DWARFContext &DWCtx,
 418                  const uint64_t Offset,
 419                  const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec) {
 420   auto findUnit = [&](std::vector<DWARFUnit *> &Units) -> DWARFUnit * {
 421     auto CUIter = llvm::upper_bound(Units, Offset,
 422                                     [](uint64_t LHS, const DWARFUnit *RHS) {
 423                                       return LHS < RHS->getNextUnitOffset();
 424                                     });
 425     static std::vector<DWARFUnit *> CUOffsets;
 426     static std::once_flag InitVectorFlag;
 427     auto initCUVector = [&]() {
 428       CUOffsets.reserve(DWCtx.getNumCompileUnits());
 429       for (const std::unique_ptr<DWARFUnit> &CU : DWCtx.compile_units())
 430         CUOffsets.emplace_back(CU.get());
 431     };
 432     DWARFUnit *CU = CUIter != Units.end() ? *CUIter : nullptr;
 433     // Above algorithm breaks when there is only one CU, and reference is
 434     // outside of it. Fall through slower path, that searches all the CUs.
 435     // For example when src and destination of cross CU references have
 436     // different abbrev section.
 437     if (!CU ||
 438         (CU && AttrSpec.Form == dwarf::DW_FORM_ref_addr &&
 439          !(CU->getOffset() < Offset && CU->getNextUnitOffset() > Offset))) {
 440       // This is a work around for XCode clang. There is a build error when we
 441       // pass DWCtx.compile_units() to llvm::upper_bound
 442       std::call_once(InitVectorFlag, initCUVector);
 443       auto CUIter = std::upper_bound(CUOffsets.begin(), CUOffsets.end(), Offset,
 444                                      [](uint64_t LHS, const DWARFUnit *RHS) {
 445                                        return LHS < RHS->getNextUnitOffset();
 446                                      });
 447       CU = CUIter != CUOffsets.end() ? (*CUIter) : nullptr;
 448     }
 449     return CU;
 450   };
 451
 452   switch (Builder.getCurrentProcessingState()) {
 453   case DIEBuilder::ProcessingType::DWARF4TUs:
 454     return findUnit(Builder.getDWARF4TUVector());
 455   case DIEBuilder::ProcessingType::DWARF5TUs:
 456     return findUnit(Builder.getDWARF5TUVector());
 457   case DIEBuilder::ProcessingType::CUs:
 458     return findUnit(Builder.getDWARFCUVector());
 459   };
 460
 461   return nullptr;
 462 }
 463
 464 uint32_t
 465 DIEBuilder::finalizeDIEs(DWARFUnit &CU, DIE &Die,
 466                          std::optional<BOLTDWARF5AccelTableData *> Parent,
 467                          uint32_t NumberParentsInChain, uint32_t &CurOffset) {
 468   getState().DWARFDieAddressesParsed.erase(Die.getOffset());
 469   uint32_t CurSize = 0;
 470   Die.setOffset(CurOffset);
 471   std::optional<BOLTDWARF5AccelTableData *> NameEntry =
 472       DebugNamesTable.addAccelTableEntry(
 473           CU, Die, SkeletonCU ? SkeletonCU->getDWOId() : std::nullopt,
 474           NumberParentsInChain, Parent);
 475   // It is possible that an indexed debugging information entry has a parent
 476   // that is not indexed (for example, if its parent does not have a name
 477   // attribute). In such a case, a parent attribute may point to a nameless
 478   // index entry (that is, one that cannot be reached from any entry in the name
 479   // table), or it may point to the nearest ancestor that does have an index
 480   // entry.
 481   // Skipping entry is not very useful for LLDB. This follows clang where
 482   // children of forward declaration won't have DW_IDX_parent.
 483   // https://github.com/llvm/llvm-project/pull/91808
 484
 485   // If Parent is nullopt and NumberParentsInChain is not zero, then forward
 486   // declaration was encountered in this DF traversal. Propagating nullopt for
 487   // Parent to children.
 488   if (!Parent && NumberParentsInChain)
 489     NameEntry = std::nullopt;
 490   if (NameEntry)
 491     ++NumberParentsInChain;
 492   for (DIEValue &Val : Die.values())
 493     CurSize += Val.sizeOf(CU.getFormParams());
 494   CurSize += getULEB128Size(Die.getAbbrevNumber());
 495   CurOffset += CurSize;
 496
 497   for (DIE &Child : Die.children()) {
 498     uint32_t ChildSize =
 499         finalizeDIEs(CU, Child, NameEntry, NumberParentsInChain, CurOffset);
 500     CurSize += ChildSize;
 501   }
 502   // for children end mark.
 503   if (Die.hasChildren()) {
 504     CurSize += sizeof(uint8_t);
 505     CurOffset += sizeof(uint8_t);
 506   }
 507
 508   Die.setSize(CurSize);
 509   return CurSize;
 510 }
 511
 512 void DIEBuilder::finish() {
 513   auto finalizeCU = [&](DWARFUnit &CU, uint64_t &UnitStartOffset) -> void {
 514     DIE *UnitDIE = getUnitDIEbyUnit(CU);
 515     uint32_t HeaderSize = CU.getHeaderSize();
 516     uint32_t CurOffset = HeaderSize;
 517     DebugNamesTable.setCurrentUnit(CU, UnitStartOffset);
 518     std::vector<std::optional<BOLTDWARF5AccelTableData *>> Parents;
 519     Parents.push_back(std::nullopt);
 520     finalizeDIEs(CU, *UnitDIE, std::nullopt, 0, CurOffset);
 521
 522     DWARFUnitInfo &CurUnitInfo = getUnitInfoByDwarfUnit(CU);
 523     CurUnitInfo.UnitOffset = UnitStartOffset;
 524     CurUnitInfo.UnitLength = HeaderSize + UnitDIE->getSize();
 525     UnitStartOffset += CurUnitInfo.UnitLength;
 526   };
 527   // Computing offsets for .debug_types section.
 528   // It's processed first when CU is registered so will be at the begginnig of
 529   // the vector.
 530   uint64_t TypeUnitStartOffset = 0;
 531   for (DWARFUnit *CU : getState().DUList) {
 532     // We process DWARF$ types first.
 533     if (!(CU->getVersion() < 5 && CU->isTypeUnit()))
 534       break;
 535     finalizeCU(*CU, TypeUnitStartOffset);
 536   }
 537
 538   for (DWARFUnit *CU : getState().DUList) {
 539     // Skipping DWARF4 types.
 540     if (CU->getVersion() < 5 && CU->isTypeUnit())
 541       continue;
 542     finalizeCU(*CU, UnitSize);
 543   }
 544   if (opts::Verbosity >= 1) {
 545     if (!getState().DWARFDieAddressesParsed.empty())
 546       dbgs() << "Referenced DIE offsets not in .debug_info\n";
 547     for (const uint64_t Address : getState().DWARFDieAddressesParsed) {
 548       dbgs() << Twine::utohexstr(Address) << "\n";
 549     }
 550   }
 551   updateReferences();
 552 }
 553
 554 DWARFDie DIEBuilder::resolveDIEReference(
 555     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 556     const uint64_t RefOffset, DWARFUnit *&RefCU,
 557     DWARFDebugInfoEntry &DwarfDebugInfoEntry) {
 558   uint64_t TmpRefOffset = RefOffset;
 559   if ((RefCU =
 560            getUnitForOffset(*this, *DwarfContext, TmpRefOffset, AttrSpec))) {
 561     /// Trying to add to current working set in case it's cross CU reference.
 562     registerUnit(*RefCU, true);
 563     DWARFDataExtractor DebugInfoData = RefCU->getDebugInfoExtractor();
 564     if (DwarfDebugInfoEntry.extractFast(*RefCU, &TmpRefOffset, DebugInfoData,
 565                                         RefCU->getNextUnitOffset(), 0)) {
 566       // In a file with broken references, an attribute might point to a NULL
 567       // DIE.
 568       DWARFDie RefDie = DWARFDie(RefCU, &DwarfDebugInfoEntry);
 569       if (!RefDie.isNULL()) {
 570         std::optional<uint32_t> UnitId = getUnitId(*RefCU);
 571
 572         // forward reference
 573         if (UnitId && !getState().CloneUnitCtxMap[*UnitId].IsConstructed &&
 574             !getAllocDIEId(*RefCU, RefDie))
 575           allocDIE(*RefCU, RefDie, getState().DIEAlloc, *UnitId);
 576         return RefDie;
 577       }
 578       BC.errs()
 579           << "BOLT-WARNING: [internal-dwarf-error]: invalid referenced DIE "
 580              "at offset: "
 581           << Twine::utohexstr(RefOffset) << ".\n";
 582
 583     } else {
 584       BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: could not parse "
 585                    "referenced DIE at offset: "
 586                 << Twine::utohexstr(RefOffset) << ".\n";
 587     }
 588   } else {
 589     BC.errs()
 590         << "BOLT-WARNING: [internal-dwarf-error]: could not find referenced "
 591            "CU. Referenced DIE offset: "
 592         << Twine::utohexstr(RefOffset) << ".\n";
 593   }
 594   return DWARFDie();
 595 }
 596
 597 void DIEBuilder::cloneDieOffsetReferenceAttribute(
 598     DIE &Die, const DWARFUnit &U, const DWARFDie &InputDIE,
 599     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec, uint64_t Ref) {
 600   DIE *NewRefDie = nullptr;
 601   DWARFUnit *RefUnit = nullptr;
 602
 603   DWARFDebugInfoEntry DDIEntry;
 604   const DWARFDie RefDie = resolveDIEReference(AttrSpec, Ref, RefUnit, DDIEntry);
 605
 606   if (!RefDie)
 607     return;
 608
 609   const std::optional<uint32_t> UnitId = getUnitId(*RefUnit);
 610   const std::optional<uint32_t> IsAllocId = getAllocDIEId(*RefUnit, RefDie);
 611   assert(IsAllocId.has_value() && "Encountered unexpected unallocated DIE.");
 612   const uint32_t DIEId = *IsAllocId;
 613   DIEInfo &DieInfo = getDIEInfo(*UnitId, DIEId);
 614
 615   if (!DieInfo.Die) {
 616     assert(Ref > InputDIE.getOffset());
 617     (void)Ref;
 618     BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: encounter unexpected "
 619                  "unallocated DIE. Should be alloc!\n";
 620     // We haven't cloned this DIE yet. Just create an empty one and
 621     // store it. It'll get really cloned when we process it.
 622     DieInfo.Die = DIE::get(getState().DIEAlloc, dwarf::Tag(RefDie.getTag()));
 623   }
 624   NewRefDie = DieInfo.Die;
 625
 626   if (AttrSpec.Form == dwarf::DW_FORM_ref_addr) {
 627     // Adding referenced DIE to DebugNames to be used when entries are created
 628     // that contain cross cu references.
 629     if (DebugNamesTable.canGenerateEntryWithCrossCUReference(U, Die, AttrSpec))
 630       DebugNamesTable.addCrossCUDie(DieInfo.Die);
 631     // no matter forward reference or backward reference, we are supposed
 632     // to calculate them in `finish` due to the possible modification of
 633     // the DIE.
 634     DWARFDie CurDie = const_cast<DWARFDie &>(InputDIE);
 635     DIEInfo *CurDieInfo = &getDIEInfoByDwarfDie(CurDie);
 636     getState().AddrReferences.push_back(
 637         std::make_pair(CurDieInfo, AddrReferenceInfo(&DieInfo, AttrSpec)));
 638
 639     Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_ref_addr,
 640                  DIEInteger(DieInfo.Die->getOffset()));
 641     return;
 642   }
 643
 644   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 645                DIEEntry(*NewRefDie));
 646 }
 647
 648 void DIEBuilder::cloneStringAttribute(
 649     DIE &Die, const DWARFUnit &U,
 650     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 651     const DWARFFormValue &Val) {
 652   if (AttrSpec.Form == dwarf::DW_FORM_string) {
 653     Expected<const char *> StrAddr = Val.getAsCString();
 654     if (!StrAddr) {
 655       consumeError(StrAddr.takeError());
 656       return;
 657     }
 658     Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_string,
 659                  new (getState().DIEAlloc)
 660                      DIEInlineString(StrAddr.get(), getState().DIEAlloc));
 661   } else {
 662     std::optional<uint64_t> OffsetIndex = Val.getRawUValue();
 663     Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 664                  DIEInteger(*OffsetIndex));
 665   }
 666 }
 667
 668 bool DIEBuilder::cloneExpression(const DataExtractor &Data,
 669                                  const DWARFExpression &Expression,
 670                                  DWARFUnit &U,
 671                                  SmallVectorImpl<uint8_t> &OutputBuffer,
 672                                  const CloneExpressionStage &Stage) {
 673   using Encoding = DWARFExpression::Operation::Encoding;
 674   using Descr = DWARFExpression::Operation::Description;
 675   uint64_t OpOffset = 0;
 676   bool DoesContainReference = false;
 677   for (const DWARFExpression::Operation &Op : Expression) {
 678     const Descr &Description = Op.getDescription();
 679     // DW_OP_const_type is variable-length and has 3
 680     // operands. Thus far we only support 2.
 681     if ((Description.Op.size() == 2 &&
 682          Description.Op[0] == Encoding::BaseTypeRef) ||
 683         (Description.Op.size() == 2 &&
 684          Description.Op[1] == Encoding::BaseTypeRef &&
 685          Description.Op[0] != Encoding::Size1))
 686       BC.outs() << "BOLT-WARNING: [internal-dwarf-error]: unsupported DW_OP "
 687                    "encoding.\n";
 688
 689     if ((Description.Op.size() == 1 &&
 690          Description.Op[0] == Encoding::BaseTypeRef) ||
 691         (Description.Op.size() == 2 &&
 692          Description.Op[1] == Encoding::BaseTypeRef &&
 693          Description.Op[0] == Encoding::Size1)) {
 694       // This code assumes that the other non-typeref operand fits into 1
 695       // byte.
 696       assert(OpOffset < Op.getEndOffset());
 697       const uint32_t ULEBsize = Op.getEndOffset() - OpOffset - 1;
 698       (void)ULEBsize;
 699       assert(ULEBsize <= 16);
 700
 701       // Copy over the operation.
 702       OutputBuffer.push_back(Op.getCode());
 703       uint64_t RefOffset;
 704       if (Description.Op.size() == 1) {
 705         RefOffset = Op.getRawOperand(0);
 706       } else {
 707         OutputBuffer.push_back(Op.getRawOperand(0));
 708         RefOffset = Op.getRawOperand(1);
 709       }
 710       uint32_t Offset = 0;
 711       if (RefOffset > 0 || Op.getCode() != dwarf::DW_OP_convert) {
 712         DoesContainReference = true;
 713         std::optional<uint32_t> RefDieID =
 714             getAllocDIEId(U, U.getOffset() + RefOffset);
 715         std::optional<uint32_t> RefUnitID = getUnitId(U);
 716         if (RefDieID.has_value() && RefUnitID.has_value()) {
 717           DIEInfo &RefDieInfo = getDIEInfo(*RefUnitID, *RefDieID);
 718           if (DIE *Clone = RefDieInfo.Die)
 719             Offset = Stage == CloneExpressionStage::INIT ? RefOffset
 720                                                          : Clone->getOffset();
 721           else
 722             BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: base type ref "
 723                          "doesn't point to "
 724                          "DW_TAG_base_type.\n";
 725         }
 726       }
 727       uint8_t ULEB[16];
 728       // Hard coding to max size so size doesn't change when we update the
 729       // offset.
 730       encodeULEB128(Offset, ULEB, 4);
 731       ArrayRef<uint8_t> ULEBbytes(ULEB, 4);
 732       OutputBuffer.append(ULEBbytes.begin(), ULEBbytes.end());
 733     } else {
 734       // Copy over everything else unmodified.
 735       const StringRef Bytes = Data.getData().slice(OpOffset, Op.getEndOffset());
 736       OutputBuffer.append(Bytes.begin(), Bytes.end());
 737     }
 738     OpOffset = Op.getEndOffset();
 739   }
 740   return DoesContainReference;
 741 }
 742
 743 void DIEBuilder::cloneBlockAttribute(
 744     DIE &Die, DWARFUnit &U,
 745     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 746     const DWARFFormValue &Val) {
 747   DIEValueList *Attr;
 748   DIEValue Value;
 749   DIELoc *Loc = nullptr;
 750   DIEBlock *Block = nullptr;
 751
 752   if (AttrSpec.Form == dwarf::DW_FORM_exprloc) {
 753     Loc = new (getState().DIEAlloc) DIELoc;
 754   } else if (doesFormBelongToClass(AttrSpec.Form, DWARFFormValue::FC_Block,
 755                                    U.getVersion())) {
 756     Block = new (getState().DIEAlloc) DIEBlock;
 757   } else {
 758     BC.errs()
 759         << "BOLT-WARNING: [internal-dwarf-error]: Unexpected Form value in "
 760            "cloneBlockAttribute\n";
 761     return;
 762   }
 763   Attr = Loc ? static_cast<DIEValueList *>(Loc)
 764              : static_cast<DIEValueList *>(Block);
 765
 766   SmallVector<uint8_t, 32> Buffer;
 767   ArrayRef<uint8_t> Bytes = *Val.getAsBlock();
 768   if (DWARFAttribute::mayHaveLocationExpr(AttrSpec.Attr) &&
 769       (Val.isFormClass(DWARFFormValue::FC_Block) ||
 770        Val.isFormClass(DWARFFormValue::FC_Exprloc))) {
 771     DataExtractor Data(StringRef((const char *)Bytes.data(), Bytes.size()),
 772                        U.isLittleEndian(), U.getAddressByteSize());
 773     DWARFExpression Expr(Data, U.getAddressByteSize(),
 774                          U.getFormParams().Format);
 775     if (cloneExpression(Data, Expr, U, Buffer, CloneExpressionStage::INIT))
 776       getState().LocWithReferencesToProcess.emplace_back(
 777           Bytes.vec(), U, Die, AttrSpec.Form, AttrSpec.Attr);
 778     Bytes = Buffer;
 779   }
 780   for (auto Byte : Bytes)
 781     Attr->addValue(getState().DIEAlloc, static_cast<dwarf::Attribute>(0),
 782                    dwarf::DW_FORM_data1, DIEInteger(Byte));
 783
 784   if (Loc)
 785     Loc->setSize(Bytes.size());
 786   else
 787     Block->setSize(Bytes.size());
 788
 789   if (Loc)
 790     Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
 791                      dwarf::Form(AttrSpec.Form), Loc);
 792   else
 793     Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
 794                      dwarf::Form(AttrSpec.Form), Block);
 795   Die.addValue(getState().DIEAlloc, Value);
 796 }
 797
 798 void DIEBuilder::cloneAddressAttribute(
 799     DIE &Die, const DWARFUnit &U,
 800     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 801     const DWARFFormValue &Val) {
 802   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 803                DIEInteger(Val.getRawUValue()));
 804 }
 805
 806 void DIEBuilder::cloneRefsigAttribute(
 807     DIE &Die, DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 808     const DWARFFormValue &Val) {
 809   const std::optional<uint64_t> SigVal = Val.getAsSignatureReference();
 810   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_ref_sig8,
 811                DIEInteger(*SigVal));
 812 }
 813
 814 void DIEBuilder::cloneScalarAttribute(
 815     DIE &Die, const DWARFDie &InputDIE,
 816     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 817     const DWARFFormValue &Val) {
 818   uint64_t Value;
 819
 820   if (auto OptionalValue = Val.getAsUnsignedConstant())
 821     Value = *OptionalValue;
 822   else if (auto OptionalValue = Val.getAsSignedConstant())
 823     Value = *OptionalValue;
 824   else if (auto OptionalValue = Val.getAsSectionOffset())
 825     Value = *OptionalValue;
 826   else {
 827     BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported scalar "
 828                  "attribute form. Dropping "
 829                  "attribute.\n";
 830     return;
 831   }
 832
 833   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 834                DIEInteger(Value));
 835 }
 836
 837 void DIEBuilder::cloneLoclistAttrubute(
 838     DIE &Die, const DWARFDie &InputDIE,
 839     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
 840     const DWARFFormValue &Val) {
 841   std::optional<uint64_t> Value = std::nullopt;
 842
 843   if (auto OptionalValue = Val.getAsUnsignedConstant())
 844     Value = OptionalValue;
 845   else if (auto OptionalValue = Val.getAsSignedConstant())
 846     Value = OptionalValue;
 847   else if (auto OptionalValue = Val.getAsSectionOffset())
 848     Value = OptionalValue;
 849   else
 850     BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported scalar "
 851                  "attribute form. Dropping "
 852                  "attribute.\n";
 853
 854   if (!Value.has_value())
 855     return;
 856
 857   Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
 858                DIELocList(*Value));
 859 }
 860
 861 void DIEBuilder::cloneAttribute(
 862     DIE &Die, const DWARFDie &InputDIE, DWARFUnit &U, const DWARFFormValue &Val,
 863     const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec) {
 864   switch (AttrSpec.Form) {
 865   case dwarf::DW_FORM_strp:
 866   case dwarf::DW_FORM_string:
 867   case dwarf::DW_FORM_strx:
 868   case dwarf::DW_FORM_strx1:
 869   case dwarf::DW_FORM_strx2:
 870   case dwarf::DW_FORM_strx3:
 871   case dwarf::DW_FORM_strx4:
 872   case dwarf::DW_FORM_GNU_str_index:
 873   case dwarf::DW_FORM_line_strp:
 874     cloneStringAttribute(Die, U, AttrSpec, Val);
 875     break;
 876   case dwarf::DW_FORM_ref_addr:
 877     cloneDieOffsetReferenceAttribute(Die, U, InputDIE, AttrSpec,
 878                                      *Val.getAsDebugInfoReference());
 879     break;
 880   case dwarf::DW_FORM_ref1:
 881   case dwarf::DW_FORM_ref2:
 882   case dwarf::DW_FORM_ref4:
 883   case dwarf::DW_FORM_ref8:
 884     cloneDieOffsetReferenceAttribute(Die, U, InputDIE, AttrSpec,
 885                                      Val.getUnit()->getOffset() +
 886                                          *Val.getAsRelativeReference());
 887     break;
 888   case dwarf::DW_FORM_block:
 889   case dwarf::DW_FORM_block1:
 890   case dwarf::DW_FORM_block2:
 891   case dwarf::DW_FORM_block4:
 892   case dwarf::DW_FORM_exprloc:
 893     cloneBlockAttribute(Die, U, AttrSpec, Val);
 894     break;
 895   case dwarf::DW_FORM_addr:
 896   case dwarf::DW_FORM_addrx:
 897   case dwarf::DW_FORM_GNU_addr_index:
 898     cloneAddressAttribute(Die, U, AttrSpec, Val);
 899     break;
 900   case dwarf::DW_FORM_data1:
 901   case dwarf::DW_FORM_data2:
 902   case dwarf::DW_FORM_data4:
 903   case dwarf::DW_FORM_data8:
 904   case dwarf::DW_FORM_udata:
 905   case dwarf::DW_FORM_sdata:
 906   case dwarf::DW_FORM_sec_offset:
 907   case dwarf::DW_FORM_rnglistx:
 908   case dwarf::DW_FORM_flag:
 909   case dwarf::DW_FORM_flag_present:
 910   case dwarf::DW_FORM_implicit_const:
 911     cloneScalarAttribute(Die, InputDIE, AttrSpec, Val);
 912     break;
 913   case dwarf::DW_FORM_loclistx:
 914     cloneLoclistAttrubute(Die, InputDIE, AttrSpec, Val);
 915     break;
 916   case dwarf::DW_FORM_ref_sig8:
 917     cloneRefsigAttribute(Die, AttrSpec, Val);
 918     break;
 919   default:
 920     BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported attribute "
 921                  "form " +
 922                      dwarf::FormEncodingString(AttrSpec.Form).str() +
 923                      " in cloneAttribute. Dropping.";
 924   }
 925 }
 926 void DIEBuilder::assignAbbrev(DIEAbbrev &Abbrev) {
 927   // Check the set for priors.
 928   FoldingSetNodeID ID;
 929   Abbrev.Profile(ID);
 930   void *InsertToken;
 931   DIEAbbrev *InSet = AbbreviationsSet.FindNodeOrInsertPos(ID, InsertToken);
 932
 933   // If it's newly added.
 934   if (InSet) {
 935     // Assign existing abbreviation number.
 936     Abbrev.setNumber(InSet->getNumber());
 937   } else {
 938     // Add to abbreviation list.
 939     Abbreviations.push_back(
 940         std::make_unique<DIEAbbrev>(Abbrev.getTag(), Abbrev.hasChildren()));
 941     for (const auto &Attr : Abbrev.getData())
 942       Abbreviations.back()->AddAttribute(Attr.getAttribute(), Attr.getForm());
 943     AbbreviationsSet.InsertNode(Abbreviations.back().get(), InsertToken);
 944     // Assign the unique abbreviation number.
 945     Abbrev.setNumber(Abbreviations.size());
 946     Abbreviations.back()->setNumber(Abbreviations.size());
 947   }
 948 }
 949
 950 void DIEBuilder::generateAbbrevs() {
 951   if (isEmpty())
 952     return;
 953
 954   for (DWARFUnit *DU : getState().DUList) {
 955     DIE *UnitDIE = getUnitDIEbyUnit(*DU);
 956     generateUnitAbbrevs(UnitDIE);
 957   }
 958 }
 959
 960 void DIEBuilder::generateUnitAbbrevs(DIE *Die) {
 961   DIEAbbrev NewAbbrev = Die->generateAbbrev();
 962
 963   if (Die->hasChildren())
 964     NewAbbrev.setChildrenFlag(dwarf::DW_CHILDREN_yes);
 965   assignAbbrev(NewAbbrev);
 966   Die->setAbbrevNumber(NewAbbrev.getNumber());
 967
 968   for (auto &Child : Die->children()) {
 969     generateUnitAbbrevs(&Child);
 970   }
 971 }
 972
 973 static uint64_t getHash(const DWARFUnit &DU) {
 974   // Before DWARF5 TU units are in their own section, so at least one offset,
 975   // first one, will be the same as CUs in .debug_info.dwo section
 976   if (DU.getVersion() < 5 && DU.isTypeUnit()) {
 977     const uint64_t TypeUnitHash =
 978         cast_or_null<DWARFTypeUnit>(&DU)->getTypeHash();
 979     const uint64_t Offset = DU.getOffset();
 980     return llvm::hash_combine(llvm::hash_value(TypeUnitHash),
 981                               llvm::hash_value(Offset));
 982   }
 983   return DU.getOffset();
 984 }
 985
 986 void DIEBuilder::registerUnit(DWARFUnit &DU, bool NeedSort) {
 987   auto IterGlobal = AllProcessed.insert(getHash(DU));
 988   // If DU is already in a current working set or was already processed we can
 989   // skip it.
 990   if (!IterGlobal.second)
 991     return;
 992   if (getState().Type == ProcessingType::DWARF4TUs) {
 993     getState().DWARF4TUVector.push_back(&DU);
 994   } else if (getState().Type == ProcessingType::DWARF5TUs) {
 995     getState().DWARF5TUVector.push_back(&DU);
 996   } else {
 997     getState().DWARFCUVector.push_back(&DU);
 998     /// Sorting for cross CU reference resolution.
 999     if (NeedSort)
1000       std::sort(getState().DWARFCUVector.begin(),
1001                 getState().DWARFCUVector.end(),
1002                 [](const DWARFUnit *A, const DWARFUnit *B) {
1003                   return A->getOffset() < B->getOffset();
1004                 });
1005   }
1006   getState().UnitIDMap[getHash(DU)] = getState().DUList.size();
1007   // This handles the case where we do have cross cu references, but CUs do not
1008   // share the same abbrev table.
1009   if (getState().DUList.size() == getState().CloneUnitCtxMap.size())
1010     getState().CloneUnitCtxMap.emplace_back();
1011   getState().DUList.push_back(&DU);
1012 }
1013
1014 std::optional<uint32_t> DIEBuilder::getUnitId(const DWARFUnit &DU) {
1015   auto Iter = getState().UnitIDMap.find(getHash(DU));
1016   if (Iter != getState().UnitIDMap.end())
1017     return Iter->second;
1018   return std::nullopt;
1019 }
1020
1021 } // namespace bolt
1022 } // namespace llvm