llvm-project

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 DWARFFormValue &RefValue,
556
    const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
557
    DWARFUnit *&RefCU, DWARFDebugInfoEntry &DwarfDebugInfoEntry) {
558
  assert(RefValue.isFormClass(DWARFFormValue::FC_Reference));
559
  uint64_t RefOffset = *RefValue.getAsReference();
560
  return resolveDIEReference(AttrSpec, RefOffset, RefCU, DwarfDebugInfoEntry);
561
}
562

563
DWARFDie DIEBuilder::resolveDIEReference(
564
    const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
565
    const uint64_t RefOffset, DWARFUnit *&RefCU,
566
    DWARFDebugInfoEntry &DwarfDebugInfoEntry) {
567
  uint64_t TmpRefOffset = RefOffset;
568
  if ((RefCU =
569
           getUnitForOffset(*this, *DwarfContext, TmpRefOffset, AttrSpec))) {
570
    /// Trying to add to current working set in case it's cross CU reference.
571
    registerUnit(*RefCU, true);
572
    DWARFDataExtractor DebugInfoData = RefCU->getDebugInfoExtractor();
573
    if (DwarfDebugInfoEntry.extractFast(*RefCU, &TmpRefOffset, DebugInfoData,
574
                                        RefCU->getNextUnitOffset(), 0)) {
575
      // In a file with broken references, an attribute might point to a NULL
576
      // DIE.
577
      DWARFDie RefDie = DWARFDie(RefCU, &DwarfDebugInfoEntry);
578
      if (!RefDie.isNULL()) {
579
        std::optional<uint32_t> UnitId = getUnitId(*RefCU);
580

581
        // forward reference
582
        if (UnitId && !getState().CloneUnitCtxMap[*UnitId].IsConstructed &&
583
            !getAllocDIEId(*RefCU, RefDie))
584
          allocDIE(*RefCU, RefDie, getState().DIEAlloc, *UnitId);
585
        return RefDie;
586
      }
587
      BC.errs()
588
          << "BOLT-WARNING: [internal-dwarf-error]: invalid referenced DIE "
589
             "at offset: "
590
          << Twine::utohexstr(RefOffset) << ".\n";
591

592
    } else {
593
      BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: could not parse "
594
                   "referenced DIE at offset: "
595
                << Twine::utohexstr(RefOffset) << ".\n";
596
    }
597
  } else {
598
    BC.errs()
599
        << "BOLT-WARNING: [internal-dwarf-error]: could not find referenced "
600
           "CU. Referenced DIE offset: "
601
        << Twine::utohexstr(RefOffset) << ".\n";
602
  }
603
  return DWARFDie();
604
}
605

606
void DIEBuilder::cloneDieReferenceAttribute(
607
    DIE &Die, const DWARFUnit &U, const DWARFDie &InputDIE,
608
    const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
609
    const DWARFFormValue &Val) {
610
  const uint64_t Ref = *Val.getAsReference();
611

612
  DIE *NewRefDie = nullptr;
613
  DWARFUnit *RefUnit = nullptr;
614

615
  DWARFDebugInfoEntry DDIEntry;
616
  const DWARFDie RefDie = resolveDIEReference(Val, AttrSpec, RefUnit, DDIEntry);
617

618
  if (!RefDie)
619
    return;
620

621
  const std::optional<uint32_t> UnitId = getUnitId(*RefUnit);
622
  const std::optional<uint32_t> IsAllocId = getAllocDIEId(*RefUnit, RefDie);
623
  assert(IsAllocId.has_value() && "Encountered unexpected unallocated DIE.");
624
  const uint32_t DIEId = *IsAllocId;
625
  DIEInfo &DieInfo = getDIEInfo(*UnitId, DIEId);
626

627
  if (!DieInfo.Die) {
628
    assert(Ref > InputDIE.getOffset());
629
    (void)Ref;
630
    BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: encounter unexpected "
631
                 "unallocated DIE. Should be alloc!\n";
632
    // We haven't cloned this DIE yet. Just create an empty one and
633
    // store it. It'll get really cloned when we process it.
634
    DieInfo.Die = DIE::get(getState().DIEAlloc, dwarf::Tag(RefDie.getTag()));
635
  }
636
  NewRefDie = DieInfo.Die;
637

638
  if (AttrSpec.Form == dwarf::DW_FORM_ref_addr) {
639
    // Adding referenced DIE to DebugNames to be used when entries are created
640
    // that contain cross cu references.
641
    if (DebugNamesTable.canGenerateEntryWithCrossCUReference(U, Die, AttrSpec))
642
      DebugNamesTable.addCrossCUDie(DieInfo.Die);
643
    // no matter forward reference or backward reference, we are supposed
644
    // to calculate them in `finish` due to the possible modification of
645
    // the DIE.
646
    DWARFDie CurDie = const_cast<DWARFDie &>(InputDIE);
647
    DIEInfo *CurDieInfo = &getDIEInfoByDwarfDie(CurDie);
648
    getState().AddrReferences.push_back(
649
        std::make_pair(CurDieInfo, AddrReferenceInfo(&DieInfo, AttrSpec)));
650

651
    Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_ref_addr,
652
                 DIEInteger(DieInfo.Die->getOffset()));
653
    return;
654
  }
655

656
  Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
657
               DIEEntry(*NewRefDie));
658
}
659

660
void DIEBuilder::cloneStringAttribute(
661
    DIE &Die, const DWARFUnit &U,
662
    const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
663
    const DWARFFormValue &Val) {
664
  if (AttrSpec.Form == dwarf::DW_FORM_string) {
665
    Expected<const char *> StrAddr = Val.getAsCString();
666
    if (!StrAddr) {
667
      consumeError(StrAddr.takeError());
668
      return;
669
    }
670
    Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_string,
671
                 new (getState().DIEAlloc)
672
                     DIEInlineString(StrAddr.get(), getState().DIEAlloc));
673
  } else {
674
    std::optional<uint64_t> OffsetIndex = Val.getRawUValue();
675
    Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
676
                 DIEInteger(*OffsetIndex));
677
  }
678
}
679

680
bool DIEBuilder::cloneExpression(const DataExtractor &Data,
681
                                 const DWARFExpression &Expression,
682
                                 DWARFUnit &U,
683
                                 SmallVectorImpl<uint8_t> &OutputBuffer,
684
                                 const CloneExpressionStage &Stage) {
685
  using Encoding = DWARFExpression::Operation::Encoding;
686
  using Descr = DWARFExpression::Operation::Description;
687
  uint64_t OpOffset = 0;
688
  bool DoesContainReference = false;
689
  for (const DWARFExpression::Operation &Op : Expression) {
690
    const Descr &Description = Op.getDescription();
691
    // DW_OP_const_type is variable-length and has 3
692
    // operands. Thus far we only support 2.
693
    if ((Description.Op.size() == 2 &&
694
         Description.Op[0] == Encoding::BaseTypeRef) ||
695
        (Description.Op.size() == 2 &&
696
         Description.Op[1] == Encoding::BaseTypeRef &&
697
         Description.Op[0] != Encoding::Size1))
698
      BC.outs() << "BOLT-WARNING: [internal-dwarf-error]: unsupported DW_OP "
699
                   "encoding.\n";
700

701
    if ((Description.Op.size() == 1 &&
702
         Description.Op[0] == Encoding::BaseTypeRef) ||
703
        (Description.Op.size() == 2 &&
704
         Description.Op[1] == Encoding::BaseTypeRef &&
705
         Description.Op[0] == Encoding::Size1)) {
706
      // This code assumes that the other non-typeref operand fits into 1
707
      // byte.
708
      assert(OpOffset < Op.getEndOffset());
709
      const uint32_t ULEBsize = Op.getEndOffset() - OpOffset - 1;
710
      (void)ULEBsize;
711
      assert(ULEBsize <= 16);
712

713
      // Copy over the operation.
714
      OutputBuffer.push_back(Op.getCode());
715
      uint64_t RefOffset;
716
      if (Description.Op.size() == 1) {
717
        RefOffset = Op.getRawOperand(0);
718
      } else {
719
        OutputBuffer.push_back(Op.getRawOperand(0));
720
        RefOffset = Op.getRawOperand(1);
721
      }
722
      uint32_t Offset = 0;
723
      if (RefOffset > 0 || Op.getCode() != dwarf::DW_OP_convert) {
724
        DoesContainReference = true;
725
        std::optional<uint32_t> RefDieID =
726
            getAllocDIEId(U, U.getOffset() + RefOffset);
727
        std::optional<uint32_t> RefUnitID = getUnitId(U);
728
        if (RefDieID.has_value() && RefUnitID.has_value()) {
729
          DIEInfo &RefDieInfo = getDIEInfo(*RefUnitID, *RefDieID);
730
          if (DIE *Clone = RefDieInfo.Die)
731
            Offset = Stage == CloneExpressionStage::INIT ? RefOffset
732
                                                         : Clone->getOffset();
733
          else
734
            BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: base type ref "
735
                         "doesn't point to "
736
                         "DW_TAG_base_type.\n";
737
        }
738
      }
739
      uint8_t ULEB[16];
740
      // Hard coding to max size so size doesn't change when we update the
741
      // offset.
742
      encodeULEB128(Offset, ULEB, 4);
743
      ArrayRef<uint8_t> ULEBbytes(ULEB, 4);
744
      OutputBuffer.append(ULEBbytes.begin(), ULEBbytes.end());
745
    } else {
746
      // Copy over everything else unmodified.
747
      const StringRef Bytes = Data.getData().slice(OpOffset, Op.getEndOffset());
748
      OutputBuffer.append(Bytes.begin(), Bytes.end());
749
    }
750
    OpOffset = Op.getEndOffset();
751
  }
752
  return DoesContainReference;
753
}
754

755
void DIEBuilder::cloneBlockAttribute(
756
    DIE &Die, DWARFUnit &U,
757
    const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
758
    const DWARFFormValue &Val) {
759
  DIEValueList *Attr;
760
  DIEValue Value;
761
  DIELoc *Loc = nullptr;
762
  DIEBlock *Block = nullptr;
763

764
  if (AttrSpec.Form == dwarf::DW_FORM_exprloc) {
765
    Loc = new (getState().DIEAlloc) DIELoc;
766
  } else if (doesFormBelongToClass(AttrSpec.Form, DWARFFormValue::FC_Block,
767
                                   U.getVersion())) {
768
    Block = new (getState().DIEAlloc) DIEBlock;
769
  } else {
770
    BC.errs()
771
        << "BOLT-WARNING: [internal-dwarf-error]: Unexpected Form value in "
772
           "cloneBlockAttribute\n";
773
    return;
774
  }
775
  Attr = Loc ? static_cast<DIEValueList *>(Loc)
776
             : static_cast<DIEValueList *>(Block);
777

778
  SmallVector<uint8_t, 32> Buffer;
779
  ArrayRef<uint8_t> Bytes = *Val.getAsBlock();
780
  if (DWARFAttribute::mayHaveLocationExpr(AttrSpec.Attr) &&
781
      (Val.isFormClass(DWARFFormValue::FC_Block) ||
782
       Val.isFormClass(DWARFFormValue::FC_Exprloc))) {
783
    DataExtractor Data(StringRef((const char *)Bytes.data(), Bytes.size()),
784
                       U.isLittleEndian(), U.getAddressByteSize());
785
    DWARFExpression Expr(Data, U.getAddressByteSize(),
786
                         U.getFormParams().Format);
787
    if (cloneExpression(Data, Expr, U, Buffer, CloneExpressionStage::INIT))
788
      getState().LocWithReferencesToProcess.emplace_back(
789
          Bytes.vec(), U, Die, AttrSpec.Form, AttrSpec.Attr);
790
    Bytes = Buffer;
791
  }
792
  for (auto Byte : Bytes)
793
    Attr->addValue(getState().DIEAlloc, static_cast<dwarf::Attribute>(0),
794
                   dwarf::DW_FORM_data1, DIEInteger(Byte));
795

796
  if (Loc)
797
    Loc->setSize(Bytes.size());
798
  else
799
    Block->setSize(Bytes.size());
800

801
  if (Loc)
802
    Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
803
                     dwarf::Form(AttrSpec.Form), Loc);
804
  else
805
    Value = DIEValue(dwarf::Attribute(AttrSpec.Attr),
806
                     dwarf::Form(AttrSpec.Form), Block);
807
  Die.addValue(getState().DIEAlloc, Value);
808
}
809

810
void DIEBuilder::cloneAddressAttribute(
811
    DIE &Die, const DWARFUnit &U,
812
    const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
813
    const DWARFFormValue &Val) {
814
  Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
815
               DIEInteger(Val.getRawUValue()));
816
}
817

818
void DIEBuilder::cloneRefsigAttribute(
819
    DIE &Die, DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
820
    const DWARFFormValue &Val) {
821
  const std::optional<uint64_t> SigVal = Val.getRawUValue();
822
  Die.addValue(getState().DIEAlloc, AttrSpec.Attr, dwarf::DW_FORM_ref_sig8,
823
               DIEInteger(*SigVal));
824
}
825

826
void DIEBuilder::cloneScalarAttribute(
827
    DIE &Die, const DWARFDie &InputDIE,
828
    const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
829
    const DWARFFormValue &Val) {
830
  uint64_t Value;
831

832
  if (auto OptionalValue = Val.getAsUnsignedConstant())
833
    Value = *OptionalValue;
834
  else if (auto OptionalValue = Val.getAsSignedConstant())
835
    Value = *OptionalValue;
836
  else if (auto OptionalValue = Val.getAsSectionOffset())
837
    Value = *OptionalValue;
838
  else {
839
    BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported scalar "
840
                 "attribute form. Dropping "
841
                 "attribute.\n";
842
    return;
843
  }
844

845
  Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
846
               DIEInteger(Value));
847
}
848

849
void DIEBuilder::cloneLoclistAttrubute(
850
    DIE &Die, const DWARFDie &InputDIE,
851
    const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
852
    const DWARFFormValue &Val) {
853
  std::optional<uint64_t> Value = std::nullopt;
854

855
  if (auto OptionalValue = Val.getAsUnsignedConstant())
856
    Value = OptionalValue;
857
  else if (auto OptionalValue = Val.getAsSignedConstant())
858
    Value = OptionalValue;
859
  else if (auto OptionalValue = Val.getAsSectionOffset())
860
    Value = OptionalValue;
861
  else
862
    BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported scalar "
863
                 "attribute form. Dropping "
864
                 "attribute.\n";
865

866
  if (!Value.has_value())
867
    return;
868

869
  Die.addValue(getState().DIEAlloc, AttrSpec.Attr, AttrSpec.Form,
870
               DIELocList(*Value));
871
}
872

873
void DIEBuilder::cloneAttribute(
874
    DIE &Die, const DWARFDie &InputDIE, DWARFUnit &U, const DWARFFormValue &Val,
875
    const DWARFAbbreviationDeclaration::AttributeSpec AttrSpec) {
876
  switch (AttrSpec.Form) {
877
  case dwarf::DW_FORM_strp:
878
  case dwarf::DW_FORM_string:
879
  case dwarf::DW_FORM_strx:
880
  case dwarf::DW_FORM_strx1:
881
  case dwarf::DW_FORM_strx2:
882
  case dwarf::DW_FORM_strx3:
883
  case dwarf::DW_FORM_strx4:
884
  case dwarf::DW_FORM_GNU_str_index:
885
  case dwarf::DW_FORM_line_strp:
886
    cloneStringAttribute(Die, U, AttrSpec, Val);
887
    break;
888
  case dwarf::DW_FORM_ref_addr:
889
  case dwarf::DW_FORM_ref1:
890
  case dwarf::DW_FORM_ref2:
891
  case dwarf::DW_FORM_ref4:
892
  case dwarf::DW_FORM_ref8:
893
    cloneDieReferenceAttribute(Die, U, InputDIE, AttrSpec, Val);
894
    break;
895
  case dwarf::DW_FORM_block:
896
  case dwarf::DW_FORM_block1:
897
  case dwarf::DW_FORM_block2:
898
  case dwarf::DW_FORM_block4:
899
  case dwarf::DW_FORM_exprloc:
900
    cloneBlockAttribute(Die, U, AttrSpec, Val);
901
    break;
902
  case dwarf::DW_FORM_addr:
903
  case dwarf::DW_FORM_addrx:
904
  case dwarf::DW_FORM_GNU_addr_index:
905
    cloneAddressAttribute(Die, U, AttrSpec, Val);
906
    break;
907
  case dwarf::DW_FORM_data1:
908
  case dwarf::DW_FORM_data2:
909
  case dwarf::DW_FORM_data4:
910
  case dwarf::DW_FORM_data8:
911
  case dwarf::DW_FORM_udata:
912
  case dwarf::DW_FORM_sdata:
913
  case dwarf::DW_FORM_sec_offset:
914
  case dwarf::DW_FORM_rnglistx:
915
  case dwarf::DW_FORM_flag:
916
  case dwarf::DW_FORM_flag_present:
917
  case dwarf::DW_FORM_implicit_const:
918
    cloneScalarAttribute(Die, InputDIE, AttrSpec, Val);
919
    break;
920
  case dwarf::DW_FORM_loclistx:
921
    cloneLoclistAttrubute(Die, InputDIE, AttrSpec, Val);
922
    break;
923
  case dwarf::DW_FORM_ref_sig8:
924
    cloneRefsigAttribute(Die, AttrSpec, Val);
925
    break;
926
  default:
927
    BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: Unsupported attribute "
928
                 "form " +
929
                     dwarf::FormEncodingString(AttrSpec.Form).str() +
930
                     " in cloneAttribute. Dropping.";
931
  }
932
}
933
void DIEBuilder::assignAbbrev(DIEAbbrev &Abbrev) {
934
  // Check the set for priors.
935
  FoldingSetNodeID ID;
936
  Abbrev.Profile(ID);
937
  void *InsertToken;
938
  DIEAbbrev *InSet = AbbreviationsSet.FindNodeOrInsertPos(ID, InsertToken);
939

940
  // If it's newly added.
941
  if (InSet) {
942
    // Assign existing abbreviation number.
943
    Abbrev.setNumber(InSet->getNumber());
944
  } else {
945
    // Add to abbreviation list.
946
    Abbreviations.push_back(
947
        std::make_unique<DIEAbbrev>(Abbrev.getTag(), Abbrev.hasChildren()));
948
    for (const auto &Attr : Abbrev.getData())
949
      Abbreviations.back()->AddAttribute(Attr.getAttribute(), Attr.getForm());
950
    AbbreviationsSet.InsertNode(Abbreviations.back().get(), InsertToken);
951
    // Assign the unique abbreviation number.
952
    Abbrev.setNumber(Abbreviations.size());
953
    Abbreviations.back()->setNumber(Abbreviations.size());
954
  }
955
}
956

957
void DIEBuilder::generateAbbrevs() {
958
  if (isEmpty())
959
    return;
960

961
  for (DWARFUnit *DU : getState().DUList) {
962
    DIE *UnitDIE = getUnitDIEbyUnit(*DU);
963
    generateUnitAbbrevs(UnitDIE);
964
  }
965
}
966

967
void DIEBuilder::generateUnitAbbrevs(DIE *Die) {
968
  DIEAbbrev NewAbbrev = Die->generateAbbrev();
969

970
  if (Die->hasChildren())
971
    NewAbbrev.setChildrenFlag(dwarf::DW_CHILDREN_yes);
972
  assignAbbrev(NewAbbrev);
973
  Die->setAbbrevNumber(NewAbbrev.getNumber());
974

975
  for (auto &Child : Die->children()) {
976
    generateUnitAbbrevs(&Child);
977
  }
978
}
979

980
static uint64_t getHash(const DWARFUnit &DU) {
981
  // Before DWARF5 TU units are in their own section, so at least one offset,
982
  // first one, will be the same as CUs in .debug_info.dwo section
983
  if (DU.getVersion() < 5 && DU.isTypeUnit()) {
984
    const uint64_t TypeUnitHash =
985
        cast_or_null<DWARFTypeUnit>(&DU)->getTypeHash();
986
    const uint64_t Offset = DU.getOffset();
987
    return llvm::hash_combine(llvm::hash_value(TypeUnitHash),
988
                              llvm::hash_value(Offset));
989
  }
990
  return DU.getOffset();
991
}
992

993
void DIEBuilder::registerUnit(DWARFUnit &DU, bool NeedSort) {
994
  auto IterGlobal = AllProcessed.insert(getHash(DU));
995
  // If DU is already in a current working set or was already processed we can
996
  // skip it.
997
  if (!IterGlobal.second)
998
    return;
999
  if (getState().Type == ProcessingType::DWARF4TUs) {
1000
    getState().DWARF4TUVector.push_back(&DU);
1001
  } else if (getState().Type == ProcessingType::DWARF5TUs) {
1002
    getState().DWARF5TUVector.push_back(&DU);
1003
  } else {
1004
    getState().DWARFCUVector.push_back(&DU);
1005
    /// Sorting for cross CU reference resolution.
1006
    if (NeedSort)
1007
      std::sort(getState().DWARFCUVector.begin(),
1008
                getState().DWARFCUVector.end(),
1009
                [](const DWARFUnit *A, const DWARFUnit *B) {
1010
                  return A->getOffset() < B->getOffset();
1011
                });
1012
  }
1013
  getState().UnitIDMap[getHash(DU)] = getState().DUList.size();
1014
  // This handles the case where we do have cross cu references, but CUs do not
1015
  // share the same abbrev table.
1016
  if (getState().DUList.size() == getState().CloneUnitCtxMap.size())
1017
    getState().CloneUnitCtxMap.emplace_back();
1018
  getState().DUList.push_back(&DU);
1019
}
1020

1021
std::optional<uint32_t> DIEBuilder::getUnitId(const DWARFUnit &DU) {
1022
  auto Iter = getState().UnitIDMap.find(getHash(DU));
1023
  if (Iter != getState().UnitIDMap.end())
1024
    return Iter->second;
1025
  return std::nullopt;
1026
}
1027

1028
} // namespace bolt
1029
} // namespace llvm
1030