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